# Structure of nonaveraging sets of integers

A set of integers is said to be nonaveraging if it contains no three-term arithmetic progression. I call a nonaveraging subset of $\lbrace 1,2, \ldots ,n \rbrace$ optimal when it has maximal cardinality.

There is a regularly updated website on nonaveraging sets records at http://www.math.uni.wroc.pl/~jwr/non-ave/DATABASE.TXT. Most of the research done on upper bounds for nonaveraging subsets of $\lbrace 1,2, \ldots ,n \rbrace$ (by Roth, Bourgain, Gowers, Tao, Green and others) involves randomness one way or another (be it in the form of Fourier analysis, extremal graph theory or ergodic theory) , and Behrend's lower bound is nonconstructive.

Despite the randomness, the optimal nonaveraging sets display some structure :

When $n=20$, there are two optimal solutions, which are $B \cup (B+5) \cup \lbrace 18 \rbrace$ and $B' \cup (B'+5) \cup \lbrace 3 \rbrace$, where $B=\lbrace 1,2,9,15 \rbrace$ and $B'=\lbrace 1,7,14,15 \rbrace$. When $n=30$, there is a unique optimal solution, $B \cup (B+19)$, where $B=\lbrace 1,3,4,8,9,11 \rbrace$. Looking at larger examples from the abovementioned website, the decomposition "two copies+error term" seems to persist, which inspires me the following list of (increasingly strong) conjectures :

** Conjecture 1. ** There is a function $E(n)$ tending to $+\infty$ when $n$ tends to infinity, such that for any optimal nonaveraging subset $X$ of $\lbrace 1,2, \ldots ,n \rbrace$ we can write $X=B \cup (B+t) \cup C$ for some nonzero integer $t$ and some $B,C \subseteq \lbrace 1,2, \ldots ,n \rbrace$ and $|B| \geq E(n)$.

** Conjecture 2. ** There is a function $\varepsilon(n)$ tending to $0$ when $n$ tends to infinity, such that for any optimal nonaveraging subset $X$ of $\lbrace 1,2, \ldots ,n \rbrace$ we can write $X=B \cup (B+t) \cup C$ for some nonzero integer $t$ and some $B,C \subseteq \lbrace 1,2, \ldots ,n \rbrace$ with $|C| \leq n\varepsilon(n)$.

** Conjecture 3. ** There is a function $\varepsilon(n)$ tending to $0$ when $n$ tends to infinity, such that for any optimal nonaveraging subset $X$ of $\lbrace 1,2, \ldots ,n \rbrace$ we can write $X=B \cup (B+t) \cup C$ for some nonzero integer $t$ and some $B,C \subseteq \lbrace 1,2, \ldots ,n \rbrace$ with $|C| \leq |X|\varepsilon(n)$.

Note that the two copies $B$ and $B+t$ are necessarily disjoint since $X$ is nonaveraging. Also, for each conjecture we have a weaker variant where "any optimal $X$" is replaced with "at least one optimal $X$".

Conjectures 2 and 3 may be out of reach but conjecture 1 seems really easier because containing no two copies of a set of size at least $k$ is a much stronger requirement than being nonavering, so that the corresponding optimal sets should be much smaller. Can anyone supply a proof?

• Please put in a question. Even something like "Is Conjecture X true?" makes the contribution an example of a preferred MathOverflow post. Gerhard "Here's Some Feedback For You" Paseman, 2011.04.02 Apr 2, 2011 at 13:51
• @Gerhard : thanks for your suggestion. Apr 2, 2011 at 15:22
• The $n=30$ solution is really for $n=119$? Apr 2, 2011 at 16:49
• @Kevin : no, of course. I corrected the typo, thanks. Apr 2, 2011 at 17:01

As to Conjecture 3, I strongly doubt it is true. If it were true, one could have decomposed any optimal progression-free subset of $[1,n]$ as $B\cup(B+t)\cup C$, where $|C|$ is small as compared to $|B|$. Now, $B$ is a progression-free subset of $[1,n-t]$ with the property that $t\notin B-B$ and $2t\notin\pm(B+B-2\ast B)$, with $2\ast B:=\{2b\colon b\in B\}$. My feeling is that these requirements are quite restrictive, forcing $|B|$ to be much smaller than (roughly) one half of the size of an optimal progression-free subset of $[1,n]$.

• The $n=30$ example (where $C$ is empty) is a counterexample to your intuition. Apr 3, 2011 at 10:33
• I believe it is not; it is just that $n=30$ is too small a number (in our present context). Consider the following. If $r_3(n)$ (the largest possible size of a progression-free subset of $[1,n]$) is a reasonably smooth function, then we should expect that $r_3(cn)=(c+o(1))r_3(n)$, for any fixed $c>0$. Now, under Conjecture 3, since $B$ is a progression-free subset of $[1,n-t]$ and $|B|=(1/2+o(1))r_3(n)$, we must have $t\le(1/2+o(1))n$. However, in your example $t=19$, which is about $(2/3)n$.
– Seva
Apr 3, 2011 at 18:06

Conjecture 1 is true.

Let $A$ denote the extremal set. Consider the set $A-A$ of all pairwise differences. Suppose you can find some non-zero $t$ in $A-A$ such that $t$ has $m$ different represantations. That is $t=a_i-b_i$ for $i=1, \dots, m$ where all the pairs $(a_i,b_i)$ are distinct and $a_i,b_i \in A$. Then let $B$ equal the set of the $b_i$. As $a_i=t+b_i$ is in $A$ by assumption this would work. (Also $B$ and $t+B$ are disjoint as otherwise one would have a progression.)

Thus, it remains to show that such a $t$ exists for a sufficiently large $m$ (in dependence of $n$).

Recall that the cardinality of $A$ (for large $n$) is at least $n^{1/2 +c}$ for some positive $c$ (Behrend's bound is in fact much stronger).

There are $|A|^2$ pairs, while there are at most $2n-1$ possible differences. Further, note that $0$ has exactly $|A|$ representations. Thus there exists some non-zero $t$ having at least $$(|A|^2 - |A|)/(2n-2) \ge (n^{1 + 2c} - n)/(2n-2) = E(n)$$ representations. This $E(n)$ tends to infinity with $n$.

Using better lower bounds for the cardinality of $A$ one could of course improve on this.

• Behrend's lower bound is actually perfectly constructive (although it does not yield optimal progression-free sets).

• Conjecture 2 is also true, for a trivial reason: since $C$ is a progression-free subset of $[n]$, you have $|C|=o(n)$.

• Regarding your first point: while I also found the insistence of the questioner on the nonconstructiveness a bit surprising, I am now also surprised by your 'perfectly constructive'. As I was under the impression that (at least the proof I know of) Behrend is mildly nonconstructive; as one does not know which of the spheres is 'good' and one only gets by averaging that some radius is good (but not which one). Do you have a different argument in mind, or perhaps we just mean different things by constructive?
– user9072
Apr 2, 2011 at 20:09
• @unknown: there does not seem to be a problem with it. Indeed, presenting Behrend's construction, one usually says something like "by averaging, one of the spheres is rich", but I think this can be derandomized without any problem. Suppose we consider integers with the base-$q$ representation $a_{k-1}...a_0$, where the $q$-ary digits $a_i\in[0,q/2)$ satisfy $a_{k-1}^2+\dots+a_0^2=r$. If we just choose $r$ close to the "expected average" of $kq^2/16$, I believe it should not be difficult to show that the resulting sphere is nearly optimal.
– Seva
Apr 2, 2011 at 20:44
• @Seva: Thank you for the explanation.
– user9072
Apr 2, 2011 at 20:49
• @ Seva : your idea about derandomizing Behrend's argument looks highly doubtful to me. The function f(r)=Number of solution to x^2+y^2=r is a discontinuous function, and there is no reason to think that f(r) is close to f(s) when r is close to s. Apr 3, 2011 at 5:47
• @Ewan: although the number of representations as a sum of two squares is not a particularly smooth function, the number of representations as a sum of a large number of squares exhibits a very regular behavior. In the former case you look at the "convolution square", in the latter case at the "high convolution power".
– Seva
Apr 3, 2011 at 6:00