Arithmetic progressions of sums of two squares

Question

Let $E=\square+\square$ denote the set of integers of the form $a^2+b^2$. It is well-known that $n\in E$ iff for any prime $p\equiv 3\pmod{4}$ we have that $\nu_p(n)$ is even, so it is not difficult to prove that the density of $E$ is zero, or even more precise bounds like $$\left| E\cap [1,n]\right| \sim \frac{cn}{\sqrt{\log n}}. $$ On the other hand we know many subsets of $\mathbb{N}$ with density zero but containing arithmetic progressions of arbitrary length: for instance the set of primes, as shown by Green and Tao.

I was wondering if $E$ also contains APs with arbitrary length.

It is fairly trivial to prove the existence of infinite APs in $E$ with four terms, namely $$(n-8)^2+(n-1)^2,\quad (n-7)^2+(n+4)^2,\quad (n+7)^2+(n-4)^2,\quad (n+8)^2+(n+1)^2 $$ but I was not able to find longer parametric APs or a reply to my question in the literature. Any help is appreciated.

Addendum: the answer should be affirmative, for instance by applying Gowers-type attacks to the discrete Fourier transform of the indicator function of $E\cap[1,n]$, or just by considering that any long AP of primes $\equiv 1\pmod{4}$ is also a long AP in $E$. For instance $214861583621 + 37692995340n$ for $n\in[0,9]$ gives an AP with length $10$.

UPDATE: I have found parametric $5$-APs and proved the existence of infinite $6$-APs. The idea was just to identify some $n$s such that $(n+8)^2+(n+1)^2+12n = 2n^2+30n+65$ belongs to $E$. Luckily $E$ is a semigroup, hence it is enough to impose that $4n^2+60n+130=(2n+15)^2-95\in E$, or to prove that for infinite values of $m$ we have that $5m^2-19$ belongs to $E$. If we brutally compute the density of $m\in[1,N]$ such that $5m^2-19\in E$ we have that this density drops to zero, albeit very slowly (as expected). On the other hand we may try to find parametric solutions to $$ 5m^2-A^2-B^2 = 19 $$ given by quadratic forms. We have $5=2^2+1^2$ and $5\cdot 2^2-1^2=19$, hence a reasonable choice is $$ m = M^2+aM+2,\quad A=2M^2+bM,\quad B=M^2+cM+1. $$ By picking $b$ as $2a+2$ and $c$ as $a-4$ we have $$ \frac{5m^2-A^2-B^2-19}{M} = 8+18a-2M $$ hence $M=9a+4$ gives that for any $m=(9a+4)^2+a(9a+4)+2=90a^2+76a+18$ we have $5m^2-19\in E$. This implies the existence of infinite $5$-APs in $E$, for instance the previous $4$-APs with $n=100a^2-65a+10$ (these are induced by $5=2^2+1^2$ and $19=5\cdot 3^2-5^2-1^2$):

1. $(100a^2-65a+2)^2+(100a^2-65a+9)^2$
2. $(100a^2-65a+3)^2+(100a^2-65a+14)^2$
3. $(100a^2-65a+17)^2+(100a^2-65a+6)^2$
4. $(100a^2-65a+18)^2+(100a^2-65a+11)^2$
5. $(100a^2-85a+22)^2+(100a^2-45a+9)^2$

These numbers are all $\equiv 0\pmod{5}$: they lead to a $5$-AP whose first term is $(60a^2-39a+4)^2+(20a^2-13a-1)^2$ and with common difference $12(20a^2-13a+2)$.
We may impose that

$$(60a^2-39a+4)^2+(20a^2-13a-1)^2+60(20a^2-13a+2)\\=(20a^2-25a+37-3v)^2+(60a^2-35a+v)^2,$$ leading to a $6$-AP, by finding integer points on $$ 616-392a-111v+40av+5v^2 = 0.$$ Actually it is enough to find some rational point, since we may scale the elements of an AP by an arbitrary square. We have the rational point $(a,v)=(0,11)$, hence we have infinite rational points by Vieta jumping and infinite $6$-APs in $E$.

This also gives substance to the dream of an elementary proof. In the last lines we proved that a parametric $4$-AP (with parameter $n$) can always be extended to a parametric $5$-AP if $n$ is taken among the values of a quadratic polynomial $q(a)$. At this point it looks reasonable that by taking $a$ among the values of a quadratic polynomial $q_2(b)$ we can write down parametric $6$-APs and so on. If this actually works, the first $k$-AP has to appear before $2^{c\cdot 2^k}$.

SECOND UPDATE We may also form APs in $E$ by looking at rational points $P_k=(x_k,y_k)\in S^1$ such that $x_k+y_k$ form an AP. The range of $x_k+y_k$ over the rational points of $S^1$ is exactly given by the values of $\pm \frac{m^2-2m-1}{m^2+1}$ for $m\in\mathbb{Q}^+$ by Vieta jumping. It is possible to list the elements of $\mathbb{Q}^+$ as in the Stern-Brocot tree and check for APs in the range of $f:x\mapsto \pm\frac{x^2-2x-1}{x^2+1}$. The triple $\frac{23}{65},\frac{35}{65},\frac{47}{65}$ is easily found by hand, and leads to the fact that $$(65n-33)^2+(65n+56)^2,\quad (65n-25)^2+(65n+60)^2,\quad (65n-16)^2+(65n+63)^2$$ is a $3$-AP in $E$ (with common difference $1560n$) for any $n\geq 1$. And it looks extremely reasonable that the range of $f$ contains arbitrarily long APs, since $r_2(n)$ is unbounded.

Another interesting fact is that the "linear" $4$-AP shown at the beginning can be extended to a $6$-AP if $n$ is chosen in such a way that both $2n^2\pm 30n+65$ belong to $E$. If $2n^2+30n+65\in E$ for any $n$ in the range of an odd cubic polynomial, $n=c(m)$, then $$ 2c(m)^2+30 c(m)+65 = d(m)^2+e(m)^2 $$ automatically implies $2n^2-30n+65\in E$ via $2c(m)^2-30c(m)+65=d(-m)^2+e(-m)^2$. Actually I have not been able to find an odd cubic polynomial fulfilling this, but I managed to find an odd rational function, which up to rescaling gives parametric $6$-APs in terms of polynomials with degree $7$.

Answer 1

Yes: Green and Tao proved (Theorem 1.2 in their paper; see also this MO answer) not only that the primes contain arbitrarily long arithmetic progressions, but that the same is true of any subset of the primes with positive relative upper density. Primes congruent to $1 \pmod 4$ have relative density $1/2$, so they contain arbitrarily long APs.

Answer 2

It's easy to prove that for any common difference $k\in \mathbb{N}$ there is at least one AP of length 3 with the 3 numbers belonging to the set $E$ of sums of two squares. Here is the proof: if $k=2m+1$ we have the AP $2m^2=m^2+(m+1)^2-k, m^2+(m+1)^2, 2(m+1)^2=m^2+(m+1)^2+k$, and if $k=2m$ we have the AP $(m+3)^2+4^2, (m+4)^2+3^2, (m+5)^2$. Also note this one for $k=4m$, $2(m-1)^2, m^2+(m+1)^2, 2(m+1)^2$. This result can be further extended to prove that for some common difference $k\in \mathbb{N}$ there is an infinity of APs of length 3 in $E$. The proof involves Pell-Fermat equations. For example, for $k=1$, there is an infinity of APs of the type 8, 9, 10 given by solutions of $x^2-2y^2=1$, i.e. APs $2y^2=x^2-1, x^2, x^2+1$, and there is an infinity of APs of the type 16, 17, 18 for a similar reason. This proves that for any common difference $k\in E$ there is an infinity of APs of length 3 in $E$, indeed since $E$ is stable for the multiplication we can multiply an AP of common difference 1 by any element of $E$ to obtain an AP contained in $E$.

An infinity of APs of length 5 in $E$ is obtained from the solutions of the Pell-Fermat equation $2q^2-p^2=7$. The APs with common difference $12q$ are $N-24q, N-12q, N, N+12q, N+24q$ where $N=(3q-1)^2+(3q+1)^2\in E$. The 5 terms belong to $E$ as we have $N-24q=p^2+(4q-3)^2$, $N-12q=2(3q-1)^2$, $N+12q=2(3q+1)^2$, and $N+24q=p^2+(4q+3)^2$. The solutions $(q,p)$ are given by the two fundamental solutions $(q_0,p_0)=(2,1)$, $(q_1,p_1)=(4,5)$ and the relations $(q_k,p_k)=(3q_{k-2}+2p_{k-2},4q_{k-2}+3p_{k-2})$. The (q,p)-sequence starts with (2, 1), (4, 5), (8, 11), (22, 31), (46, 65), (128, 181), etc.

Here is a trivial argument proving the existence of APs of length 5 of common difference $4k^2$ for any integer $k$. The numbers $\{n, n+4, n+8, n+12, n+16\}$ are all sums of two squares for $n = 1, 37,...,1009,...$, indeed we have $1009 = 15^2+28^2$, $1013=22^2+23^2$, $1017=21^2+24^2$, $1021=11^2+30^2$, and $1025=1^2+32^2$. This implies that, for any $k\geq 1$, the 5 numbers $\{m, m+4k^2, m+8k^2, m+12k^2, m+16k^2\}$ form an AP of common difference $4k^2$ and all belong to $E$ if we choose, for example, $m=1009k^2$. Using a similar approach (i.e. constructive) it should be relatively easy to prove that for any common difference $4k$, there exist at least one $n$ such that $n, n+4k, n+8k, n+12k, n+16k$ all belong to $E$.

Also note this AP of 16 terms $1138553+84k$ for $0\leq k \leq 15$. All 16 numbers are in the set $E$ of sums of two squares: $1138553=8^2+1067^2$, $1138637=211^2+1046^2$, $1138721=239^2+1040^2$, $1138805=94^2+1063^2$,$1138889=20^2+1067^2$, $113973=22^2+1067^2$, $1139057=244^2+1039^2$, $1139141=671^2+830^2$, $1139225=125^2+1060^2$, $1139309=710^2+797^2$, $1139393=452^2+967^2$, $1139477=169^2+1054^2$, $=1139561=475^2+956^2$, $1139645=34^2+1067^2$, $1139729=127^2+1060^2$, $1139813=143^2+1058^2$.

If you have an AP of $m$ terms in $E$ with common difference $d$, it immediately implies that there is an infinity of APs of length $m$ and common differences $dk$ for any $k\in E$ in $E$. The 16 term AP with common difference 84 given above, proves that there is an infinity of APs of length 16 in the set $E$.

Answer 3

As far as your length 5 progressions, you have $5 x^2 - y^2 - z^2 = 19.$ If we let $H$ be the diagonal matrix with entries $5, \, -1 , \; -1 $ we need only find elements of the automorphism group, meaning matrices $P$ of integers such that $P^T H P = H.$ One relatively easy way is to just fix one of the $-1$ entries and throw in an automophism matrix for $5 u^2 - v^2$ in the remaining variables. This comes from the Pell equation $ t^2 - 5 w^2 =1,$ or $t=9, w=4$ and resulting matrices $$ P_1 = \left( \begin{array}{ccc} 9&4&0\\ 20&9&0 \\ 0&0&1 \\ \end{array} \right) $$

$$ P_2 = \left( \begin{array}{ccc} 9&0&4\\ 0&1&0 \\ 20&0&9 \\ \end{array} \right) $$

$$ P_3 = \left( \begin{array}{ccc} 19&6&6\\ 30&9&10 \\ 30&10&9 \\ \end{array} \right) $$

As these will have determinant $\pm 1$ the $\gcd(x,y,z)$ will not change under $\vec{X} \mapsto P \vec{X}$ Also, with positive elements in enough spots, we will find $x^2 + y^2 + z^2 $ increasing as long as $\vec{X}$ began with non-negative entries.

My first impression is that this idea can be made to fit your scheme for length 6 and length 7... In general, finiding the entire automorphism group is a messy thing, but you need only a few $P$

next day: in case the next layer uses $5x^2 - y^2 - z^2 - w^2$ with half the Hessian matrix

$$ H = \left( \begin{array}{cccc} 5&0&0&0\\ 0&-1&0&0 \\ 0&0&-1&0 \\ 0&0&0&-1 \\ \end{array} \right) $$ we may use

$$ P = \left( \begin{array}{cccc} 4&1&1&1\\ 5&2&1&1 \\ 5&1&2&1 \\ 5&1&1&2 \\ \end{array} \right) $$

One may check that $P^T HP = H$