Fractal Sets and Arithmetic Progressions

g4_pic

Members of the 4-free set G_4, in red.

— 1. The Erdős–Turán Conjecture —

In combinatorics, a set S = \{s_1,s_2,\ldots, \} of positive integers is called large if the sum of the reciprocals of the elements of S diverges. In other words, large sets are exactly those with divergent harmonic sums. Some examples of large sets include:

  1. The set of positive integers in a given congruence class, by comparison to the divergent harmonic series..
  2. Any set with positive natural density, by definition of density.
  3. The set of primes, by a result of Euler.

The Erdős–Turán Conjecture claims that any large set of positive integers must contain arithmetic progressions of arbitrary long (finite) length. This conjecture is known to hold for the three sets above; trivially for (a), non-trivially for (b) by Szemeredi’s Theorem (1975), and non-trivially for (c) by the Green–Tao Theorem (2004).

— 2. Constructing Large Harmonic Sums —

A set of integers is called k-free if it contains no arithmetic progressions of length k. Thus the Erdős–Turán Conjecture may also be phrased in the following way: the harmonic sum of any k-free set is finite. Moreover, if the Erdős–Turán Conjecture holds, a remark of Gelver (1977) implies that these harmonic sums can be bounded, uniformly, by a function of k.

It is a natural question to ask what these maximal harmonic sums look like. Nothing concrete is known about upper bounds (which is unsurprising, since their existence implies Erdős–Turán), but lower bounds may be found through experimentation. For example, let G_k be the k-free set constructed using a greedy algorithm. (That is, construct G_k inductively by repeatedly adding the smallest integer which maintains k-freedness.) This gives:

G_3 = \{1,2,4,5,10,11,13,14,28,29,31,32,37,38,40,41, 82,83,85,\,\ldots\}

G_4 = \{1,2,3,5,6,8,9,10,15,16,17,19,26,27,29,30,31,34,37,49,\,\ldots\}

G_5 = \{1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 26, 27, 28, 29, 31,\,\ldots\}

These sequences (and links to many more related ones) can be found on the OEIS at the following links: A003278A005837, and A020655.

Note that no element of G_5 is divisible by five. In fact, it’s not hard to show that G_5 is exactly the set of integers x for which the base-5 representation of x-1 omits the digit 4. Likewise, G_3 is the set of integers x for which the base-3 representation of x-1 omits the digit 2. This pattern falls apart for G_4; one can show that this fractal structure develops in G_k exactly when k is prime.

Here, having structure is a good thing, because structure in G_k limits the ability of G_k to form arithmetic progressions “by accident.” For this reason, G_3 and G_5 are of slow-growth and therefore have competitively-large harmonic sums (among 3-free and 5-free sets, respectively). The harmonic sum of G_3 is 3.00794 and the harmonic sum of G_5 is 7.8723.

I should mention that convergence to these harmonic sums is actually quite slow. While it is not hard to show that G_3 and G_5 are small sets (i.e. have convergent harmonic sums), the problem of effectively estimating their harmonic sums remained open until the work of Baillie–Schmelzer (2008). And, for sets like G_4 without fractal self-symmetry, no algorithm is known to efficiently estimate the harmonic sum. Brute-force computation using the first 10,000 terms of G_4 shows that this harmonic sum exceeds 4.191, but does not give an error envelope.

All this leads me to suspect that we can do better than G_4. By finding a 4-free set with more structure, we can hope to (1) avoid arithmetic progressions in a more systematic (and efficient?) way and (2) better estimate the harmonic sum of what we produce.

— 3. Fractal Sets Without Long Arithmetic Progressions —

To generalize the nice properties of G_3 and G_5, we study arithmetic progressions in the residue field \mathbb{Z}/p\mathbb{Z}, with p a prime. Formally, call a set of residues \{a_1,\ldots,a_n\} \in \mathbb{Z}/p\mathbb{Z} an arithmetic progression modulo p if the a_j have some representatives in \mathbb{Z} in an arithmetic progression (reordered, if necessary). For example, \{2,3,6\} is arithmetic progression mod 7: up to reordering, it’s equivalent to \{2,6,10\}. By analogy, a set is called k-free modulo p if it contains no k-term arithmetic progressions modulo p.

The following theorem gives a reason to care about k-free sets modulo p:

Theorem: Let p be prime. If S \subsetneq [0,p-1] is k-free modulo p and 0 \in S, then the set of integers whose base-p digits are restricted to S forms a k-free set.

Proof: Suppose that S is k-free modulo p and that the set of integers with restricted base-p digits contains the arithmetic progression A = \{c + \Delta j: j \in [0,k-1]\}. If p \nmid \Delta, then A has k distinct residues in modular arithmetic progression, a contradiction. Otherwise, let c_0 be the base-p units digit of c. The progression (A-c_0)/p has digits restricted to S and a smaller common difference. We conclude by infinite descent. \square

This theorem gives a quick proof of the fact that G_p is p-free when p is prime, since the base-p digit set \{0,\ldots,p-2\} is clearly p-free modulo p. (Technically, G_p is obtained by then shifting all elements in this digit-based set up by 1, but this has no effect on the existence of arithmetic progressions.)

This theorem also provides a new avenue for constructing k-free sets of fractal type. From any digit set which is k-free mod p, we form an auxiliary set based on base-p digit restriction which is k-free. Checking k-freedness mod p is a finite problem and can be done algorithmically (and efficiently), which gives us a reasonable means for producing many examples of k-free sets. Among many examples, we hope to find a few with large harmonic sums.

— 4. Numerical Results —

In our quest to best G_4 and improve the numerical results for 4-free sets, we begin with a (weakly-pruned) brute-force search for 4-free sets modulo p within the subsets of [0,p-1]. This is of course computationally taxing (the run-time is exponential in p). In practice, I’m limited to primes p \leq 37, though more effective pruning (or completely novel techniques) could push our search a lot farther.

Fortunately, we don’t have to go very far at all before we find some sets which produce larger harmonic sums than G_4. The simplest is the set of integers x for which the base-11 digits of x-1 restrict to the set \{0,1,2,4,5,7\}. This set has a harmonic sum of 4.4217, which seems to beat that of G_4 by a considerable margin. (You might argue that this sum only beats G_4 because Baillie–Schmelzer gives better sum estimation. It’s possible that G_4 outperforms, although this seems unlikely since a comparison of the first 10,000 terms in each set shows that G_4 is already behind in harmonic sum.)

In the course of my search, I found approximately thirty other sets with harmonic sums larger than 4, of which three had harmonic sums over 4.1. These three employ the 4-free digit sets

\{0,1,2,4,5,7,8,9,16,17,20,22,26,28\} \!\! \mod 37

\{0,1,2,4,5,7,11,12,14,15,18,20,24,32\} \!\! \mod 37

\{0,1,2,4,5,7,8,9,18,20,24,26,29,30\} \!\! \mod 37

and produce the harmonic sums 4.1968, 4.1477, and 4.1267, respectively.

The lead of this base-11 set over all others in my data-set is quite striking. I doubt that that set has a maximal harmonic sum (among sets of this type), but good solutions seem sparse and it appears that new techniques are needed to advance this search.

That’s it for today. I’m open to ideas advancing this problem, both computationally and theoretically. The application of these generalized fractal sets in the Erdős–Turán Conjecture seems new and I wonder if their properties will be helpful in that context.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s