MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


thanks to the helpers

share|cite|improve this question

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

share|cite|improve this answer

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

share|cite|improve this answer
$A = [\lfloor n/3 \rfloor+1,\lfloor 2n/3 \rfloor]$ also works for the original problem. – Douglas Zare Jun 20 '11 at 2:43

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]

share|cite|improve this answer

Your Answer


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.