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

I am interested in a sharp bound on the largest possible size $e_3({\boldsymbol{Z}_n})$ of a subset $S \subset \boldsymbol{Z}_n$ such that for any three distinct elements $a, b, c \in S$ we have $a+b \not= 2c$.

The best upper and lower bounds I could find through usual means such as Mathscinet were by T. Sanders, Ann. of Math. 174 (2011) 619–636 and M. Elkin, Proc. SODA (2010) 886–905 respectively, where a non-modulo version is considered, i.e., they gave bounds on the largest possible size $e_3({N})$ of a subset $S \subset N =\{1,2,\dots,n\}$ such that for any three distinct integers $a, b, c \in S$ it holds that $a+b \not= 2c$.

Any $S$ containing no $3$-term APs in the modulo $n$ sense is automatically a no-$3$-term-AP subset in the sense of the non-modulo $n$ version, so we have $e_3({\boldsymbol{Z}_n}) \leq e_3({N})$. The converse may not be true, but apparently we have $e_3({N}) \leq e_3({\boldsymbol{Z}_{2n}})$. So asymptotically speaking, $e_3({\boldsymbol{Z}_n})$, which I want to know, behaves pretty much the same way as $e_3({N})$. But to my layman eye, the actual values of these two may be ever so slightly different.

My question is, how large can this "same difference" be? Is there serious research somewhere exactly on this?

I'm sorry if I'm missing something quite obvious; the inequalities $e_3({\boldsymbol{Z}_n}) \leq e_3({N}) \leq e_3({\boldsymbol{Z}_{2n}})$ look too elementary.

Edit: Fixed minor typos. Also, as quid's comments suggest, the above inequalities may not be as "bad" as they look in the sense that it may be very tough or well into the diminishing returns zone to study nontrivial information on the structure of best possible sets or extract it from known results. At least the elementary argument does the job as far as $e_3({\boldsymbol{Z}_n})$'s asymptotic behavior goes in the Landau symbols' sense. My thanks goes to quid for the series of informative comments and also Robert for the interesting computation.

share|improve this question
1  
Just some minor remarks you might be aware of already: the upper bound for the integer case is in fact a bound for the cyclic case plus (essentially) the inequality you mention. So, Sanders's paper is (also) the best known for the cyclic case (see the final section to notice this). You could use his tech. results directly for cyclic but all this would be absorbed in the constant of the big-Oh. I think this is still best (see Gowers's blog gowers.wordpress.com/2011/02/05/polymath6-a-is-to-b-as-c-is-to for discussion on project for improve. but it seems it didn't yet suceed). –  quid Jan 2 '13 at 17:12
1  
In general, the asymptotic bounds seem presently still far away from each other so that this effect on the constant typically I think does not receive much attention, and people use the inequality you mention. It is not clear to me how much improvement (if any) one could make (abstarctly) on this inequaliy or if this was tried/succeeded. But at least I think it is not used typically. And by abstractly I mean that there is no clear conjecture for the asymtotic size or structure of extremal sets; so one would have to work only with the defining properties. –  quid Jan 2 '13 at 17:18
1  
This for the asymptotic results. If you care for explicit small values, things could/should be a bit different. Although I do not know anything right now. Sorry, for the strain of comments; but I did not want to give this as an answer and then I must not be too terse either :) –  quid Jan 2 '13 at 17:21
4  
The results I get for $e_3(Z_n)$, $n=1,2,\ldots,30$ are $1, 2, 2, 2, 2, 4, 3, 4, 4, 4, 4, 4, 4, 6, 4, 6, 5, 8, 6, 8, 6, 8, 6, 8, 7, 8, 8, 8, 8, 8$. This sequence does not seem to be in the OEIS yet, though $e_3(N)$ is (sequence A003002). –  Robert Israel Jan 2 '13 at 19:05
    
Wow. Thank you for the very informative comments, quid! You should've posted it as an answer. The general asymptotic case is as exciting as it is difficult, but I'm also interested in non-asymptotic results. So results on some restricted $n$ and computational math things are great, too. About the last sentence of your comment, you're still mad at me, aren't ya? –  Yuichiro Fujiwara Jan 2 '13 at 19:18
show 3 more comments

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.