3
$\begingroup$

For a set $A$ with some underlying addition operator, $r_k(A)$ is the size of the maximum subset of $A$ that does not contain a $k$-term arithmetic progression.

Exercise 10.0.1 in Tao-Vu's Additive Combinatorics requires us to show that $r_k([1, N/k)) \le r_k(\mathbb{Z}_N)$. I do not know how to do this and would like some help. I'm trying to show that for every AP-free $A \subseteq [1, N/k)$, there exists an $A' \subseteq \mathbb{Z}_N$ that is also AP-free with $|A'| \ge |A|$. I know I should take advantage of the $1/k$ interval, but I'm not sure what.

Moreover, I'm curious about the minimum $t \ge 2$ such that $r_k([1, N/t)) \le r_k(\mathbb{Z}_N)$ still holds.

$\endgroup$

1 Answer 1

0
$\begingroup$

The point is that $A\subset [1,N/k)$ naturally gives a subset of $\mathbb{Z}/N\mathbb{Z}$ of the same size under the obvious identification, and $A$ being concentrated in a short interval prevents any non-trivial k-APS being created where there were none before, since there is no 'wrap-around'.

More formally, we can argue as follows.

The main trick is to consider the natural bijection $\phi:\mathbb{Z}/N\mathbb{Z}\to \{1,\ldots,N\}$ (so $x\equiv \phi(x)\pmod{N}$) and note that if $\phi(a)+\phi(b)<N$ then $\phi(a+b)=\phi(a)+\phi(b)$. More generally, if $\phi(a_1)+\cdots +\phi(a_r)< N$ then $$ \phi(a_1+\cdots+a_r)=\phi(a_1)+\cdots+\phi(a_r).$$

Let $A\subset [1,N/k)$ have no k-APs, and let $A'=\phi^{-1}(A)$, and suppose that there is a k-AP $x,\ldots,x+(k-1)d\in A'$ with $d\neq 0$. Without loss of generality, $\phi(d)\leq N/2$ (or else consider the k-AP with $x$ replaced by $x+(k-1)d$ and $d$ replaced by $-d$). I claim that $\phi(x),\ldots,\phi(x+(k-1)d)$ is also a k-AP - then we have a non-trivial k-AP in A, contradiction, and hence $A'$ is also k-AP free, and so $r_k([1,N/k))\leq r_k(\mathbb{Z}/N\mathbb{Z})$.

Indeed, we will show that $\phi(x),\ldots,\phi(x+(k-1)d)$ forms a k-AP by explicitly showing that $\phi(x+id)=\phi(x)+i\phi(d)$ for $0\leq i<k$. By the above additive property of $\phi$, it suffices to show that $\phi(x),\phi(d)<N/k$. This is trivial for $\phi(x)$ (since $\phi(x)\in A\subset [1,N/k)$).

Furthermore, we have $d\equiv \phi(x+d)-\phi(x)\pmod{N}$. If $\phi(x+d)>\phi(x)$ then $\phi(d)=\phi(x+d)-\phi(x)<N/k$ (using $\phi(x),\phi(x+d)\in A\subset [1,N/k)$). If $\phi(x)>\phi(x+d)$ then $\phi(d)=N+\phi(x+d)-\phi(x)>N-N/k>N/2$, which is a contradiction to our assumption that $\phi(d)\leq N/2$.

$\endgroup$

You must log in to answer this question.

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