Structure of nonaveraging sets of integers

Question

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?

Answer 1

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]$.

Answer 2

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.

Answer 3

• 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)$.