Fractal Sets and Arithmetic Progressions

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:

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 $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: A003278, A005837, 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.

a. w. walker

mathematics and miscellany

Fractal Sets and Arithmetic Progressions

Leave a Reply Cancel reply

Share this:

Like this:

Leave a Reply Cancel reply