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

Suppose that $S\subseteq\mathbb{Z}[i]$ has the following properties:

For convenience, let $A_n = \{z : z\in\mathbb{Z}[i], \text{Nm}(z)\le n\}$

$$\limsup_{n\rightarrow\infty} \frac{|S\cap A_n|}{|A_n|} > 0$$

Then is it the case that $S$ contains arbitrarily long arithmetic progressions.

share|cite|improve this question
Is r=n in your convenient definition? – Włodzimierz Holsztyński Aug 10 '14 at 5:15
That was a typo. – Mayank Pandey Aug 10 '14 at 5:27
@MP, thank you. – Włodzimierz Holsztyński Aug 10 '14 at 5:39
Do you mean $S\subset\mathbb{Z}[i]$? – John Bentin Aug 10 '14 at 8:14
Yes. Another typo. – Mayank Pandey Aug 10 '14 at 16:51
up vote 24 down vote accepted

This is true, and follows from one-dimensional Szemeredi.

Fix $\delta > 0$ such that $|S\cap A_n| \geq \delta |A_n|$ infinitely often. Let $r = \lfloor \sqrt n \rfloor$, so $A_n$ is contained in the square $S_r: \{x+iy \in {\bf Z}[i] \colon |x|,|y| < r\}$. Define the additive homomorphism $h_r: {\bf Z}[i] \rightarrow {\bf Z}$ by $h_r(x+iy) = 4rx+y$. Then $h_r$ is injective on $S_r$, and any arithmetic progression in $h_r(S_r)$ lifts to $S_r$. [The point is that $h_r$ regularly lays the horizontal segments in $S_r$, each of length $2r-1$, on ${\bf Z}$, but separated by gaps of length $2r+1$, which is short enough to reduce the density by only a finite factor but long enough that any identity $2a_2=a_1+a_3$ in the image holds on each coordinate of the $h_r^{-1}(a_i)$.] Then the image $h_r(S_r)$ is a subset of $(-4r^2,4r^2)$ of density at least $\frac\pi8 \! \delta - O(1/r)$, and by Szemeredi is guaranteed to contain arbitrarily long arithmetic progressions as $r \rightarrow \infty$.

The same technique works with ${\bf Z}[i] \cong {\bf Z}^2$ replaced by ${\bf Z}^k$ for any fixed $k$.

[Added later: Naturally this stratagem is far from new. This 2008 entry from Terry Tao's blog reminds me that it's called the "Ruzsa projection trick", and the map $h_r$ (and more generally the injection from $(-r,r)^k$ to ${\bf Z}$ taking $(x_1,\ldots,x_k)$ to $\sum_{i=1}^k (4r)^{k-i} x_i$) is called a "Freiman isomorphism of order $2$" to its image ("order $2$" because coincidences between sums of $2$ elements of $S$ suffice to detect arithmetic progressions of arbitrary length).]

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.