Arithmetic progressions of length 3 in subset of Z_n of size n^d - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T02:41:03Z http://mathoverflow.net/feeds/question/68220 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/68220/arithmetic-progressions-of-length-3-in-subset-of-z-n-of-size-nd Arithmetic progressions of length 3 in subset of Z_n of size n^d elad 2011-06-19T17:16:37Z 2011-07-29T06:13:41Z <p>Let $A\subset\mathbb{Z}/n\mathbb{Z}$ such that: $|A|>n^{d}$ ($0&lt; d &lt;1$).</p> <p>Let $C=\{(x,y,2y-x)\in A\times A \times A\}$ be the set of $3$-term arithmetic progressions within $A$.</p> <p>[The original version asked about $x+y \in A$, settled by the example of Anthony Quas.]</p> <p>I need to prove (or refute) that there exists a lower bound $u(n)$ on $\frac{|C|}{|A|}$ such that </p> <p>$$\lim_{n\rightarrow\infty}\frac{\log(u(n))}{\log(n)}>0.$$</p> <p>thanks to the helpers</p> http://mathoverflow.net/questions/68220/arithmetic-progressions-of-length-3-in-subset-of-z-n-of-size-nd/68223#68223 Answer by Anthony Quas for Arithmetic progressions of length 3 in subset of Z_n of size n^d Anthony Quas 2011-06-19T18:00:51Z 2011-06-19T18:00:51Z <p>If $A$ is the set of odd numbers up to $n/2$ then $C$ is empty. </p> http://mathoverflow.net/questions/68220/arithmetic-progressions-of-length-3-in-subset-of-z-n-of-size-nd/68228#68228 Answer by elad for Arithmetic progressions of length 3 in subset of Z_n of size n^d elad 2011-06-19T18:59:30Z 2011-06-19T18:59:30Z <p>yes, you are right of course, i will correct my question: the group D is: D={(x,y)|2x-y∈A} so now C is at lesat the size of A [(a,a) is in C for every element of A]</p> http://mathoverflow.net/questions/68220/arithmetic-progressions-of-length-3-in-subset-of-z-n-of-size-nd/68234#68234 Answer by gowers for Arithmetic progressions of length 3 in subset of Z_n of size n^d gowers 2011-06-19T20:48:35Z 2011-06-20T09:48:28Z <p>With your corrected question you are asking, in a strange way, for the number of arithmetic progressions of length 3 in A. There is a well-known example of Behrend of a set of size $n/\exp(c\sqrt{\log n})$ that contains no non-degenerate APs of length 3. So the answer to your question is no.</p> <p><strong>Edit:</strong> now that you have rephrased your question explicitly to be about arithmetic progressions of length 3, the words "in a strange way" no longer apply above. Indeed, the whole of the first sentence is rendered redundant (but I'll leave it there for the historical record).</p>