5
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ 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 $\endgroup$ Apr 2, 2011 at 13:51
  • $\begingroup$ @Gerhard : thanks for your suggestion. $\endgroup$ Apr 2, 2011 at 15:22
  • $\begingroup$ The $n=30$ solution is really for $n=119$? $\endgroup$ Apr 2, 2011 at 16:49
  • $\begingroup$ @Kevin : no, of course. I corrected the typo, thanks. $\endgroup$ Apr 2, 2011 at 17:01

3 Answers 3

3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ The $n=30$ example (where $C$ is empty) is a counterexample to your intuition. $\endgroup$ Apr 3, 2011 at 10:33
  • $\begingroup$ 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$. $\endgroup$
    – Seva
    Apr 3, 2011 at 18:06
4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$
  • 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)$.

$\endgroup$
8
  • $\begingroup$ 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? $\endgroup$
    – user9072
    Apr 2, 2011 at 20:09
  • $\begingroup$ @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. $\endgroup$
    – Seva
    Apr 2, 2011 at 20:44
  • $\begingroup$ @Seva: Thank you for the explanation. $\endgroup$
    – user9072
    Apr 2, 2011 at 20:49
  • $\begingroup$ @ 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. $\endgroup$ Apr 3, 2011 at 5:47
  • $\begingroup$ @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". $\endgroup$
    – Seva
    Apr 3, 2011 at 6:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.