2
$\begingroup$

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

$\endgroup$

3 Answers 3

11
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ $A = [\lfloor n/3 \rfloor+1,\lfloor 2n/3 \rfloor]$ also works for the original problem. $\endgroup$ Commented Jun 20, 2011 at 2:43
0
$\begingroup$

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]

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .