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

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

share|improve this question
add comment

3 Answers

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|improve this answer
add comment

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

share|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
add comment

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|improve this answer
add comment

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.