Arithmetic progressions of length 3 in subset of Z_n of size n^d - MathOverflow

Arithmetic progressions of length 3 in subset of Z_n of size n^d

2011-06-19T17:16:37Z

Let $A\subset\mathbb{Z}/n\mathbb{Z}$ such that: $|A|>n^{d}$ ($0< d <1$).

Let $C=\{(x,y,2y-x)\in A\times A \times A\}$ be the set of $3$-term arithmetic progressions within $A$.

[The original version asked about $x+y \in A$, settled by the example of Anthony Quas.]

I need to prove (or refute) that there exists a lower bound $u(n)$ on $\frac{|C|}{|A|} $ such that

$$\lim_{n\rightarrow\infty}\frac{\log(u(n))}{\log(n)}>0.$$

thanks to the helpers

Answer by Anthony Quas for Arithmetic progressions of length 3 in subset of Z_n of size n^d

2011-06-19T18:00:51Z

If $A$ is the set of odd numbers up to $n/2$ then $C$ is empty.

Answer by elad for Arithmetic progressions of length 3 in subset of Z_n of size n^d

2011-06-19T18:59:30Z

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]

Answer by gowers for Arithmetic progressions of length 3 in subset of Z_n of size n^d

2011-06-19T20:48:35Z

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.

Edit: 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).