# Szemeredi's theorem in the Gaussian integers

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.

-
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

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