— 1. The Erdős–Turán Conjecture —
In combinatorics, a set of positive integers is called large if the sum of the reciprocals of the elements of diverges. In other words, large sets are exactly those with divergent harmonic sums. Some examples of large sets include:
- The set of positive integers in a given congruence class, by comparison to the divergent harmonic series..
- Any set with positive natural density, by definition of density.
- 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 be the k-free set constructed using a greedy algorithm. (That is, construct inductively by repeatedly adding the smallest integer which maintains k-freedness.) This gives:
These sequences (and links to many more related ones) can be found on the OEIS at the following links: A003278, A005837, and A020655.
Note that no element of is divisible by five. In fact, it’s not hard to show that is exactly the set of integers for which the base-5 representation of omits the digit 4. Likewise, is the set of integers for which the base-3 representation of omits the digit 2. This pattern falls apart for ; one can show that this fractal structure develops in exactly when k is prime.
Here, having structure is a good thing, because structure in limits the ability of to form arithmetic progressions “by accident.” For this reason, and are of slow-growth and therefore have competitively-large harmonic sums (among 3-free and 5-free sets, respectively). The harmonic sum of is 3.00794 and the harmonic sum of is 7.8723.
I should mention that convergence to these harmonic sums is actually quite slow. While it is not hard to show that and 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 without fractal self-symmetry, no algorithm is known to efficiently estimate the harmonic sum. Brute-force computation using the first 10,000 terms of 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 . 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 and , we study arithmetic progressions in the residue field , with p a prime. Formally, call a set of residues an arithmetic progression modulo p if the have some representatives in in an arithmetic progression (reordered, if necessary). For example, is arithmetic progression mod 7: up to reordering, it’s equivalent to . 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 is k-free modulo p and , then the set of integers whose base-p digits are restricted to forms a k-free set.
Proof: Suppose that is k-free modulo p and that the set of integers with restricted base-p digits contains the arithmetic progression . If , then has k distinct residues in modular arithmetic progression, a contradiction. Otherwise, let be the base-p units digit of . The progression has digits restricted to and a smaller common difference. We conclude by infinite descent.
This theorem gives a quick proof of the fact that is p-free when p is prime, since the base-p digit set is clearly p-free modulo p. (Technically, 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 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 . This is of course computationally taxing (the run-time is exponential in p). In practice, I’m limited to primes , 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 . The simplest is the set of integers for which the base-11 digits of restrict to the set . This set has a harmonic sum of 4.4217, which seems to beat that of by a considerable margin. (You might argue that this sum only beats because Baillie–Schmelzer gives better sum estimation. It’s possible that outperforms, although this seems unlikely since a comparison of the first 10,000 terms in each set shows that 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
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.