Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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 –  Gerhard Paseman Apr 2 '11 at 13:51
    
@Gerhard : thanks for your suggestion. –  Ewan Delanoy Apr 2 '11 at 15:22
    
The $n=30$ solution is really for $n=119$? –  Kevin O'Bryant Apr 2 '11 at 16:49
    
@Kevin : no, of course. I corrected the typo, thanks. –  Ewan Delanoy Apr 2 '11 at 17:01
add comment

3 Answers

up vote 3 down vote accepted

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

share|improve this answer
    
The $n=30$ example (where $C$ is empty) is a counterexample to your intuition. –  Ewan Delanoy Apr 3 '11 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 '11 at 18:06
add comment

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.

share|improve this answer
add comment
  • 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)$.

share|improve this answer
    
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? –  quid Apr 2 '11 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 '11 at 20:44
    
@Seva: Thank you for the explanation. –  quid Apr 2 '11 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. –  Ewan Delanoy Apr 3 '11 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 '11 at 6:00
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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