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

  • 2
    $\begingroup$ As you mostly point out, the affirmative answer does follow from the Green–Tao theorem, since their theorem applies to any set of primes of positive relative density, including the primes that are 1 mof 4. $\endgroup$ Jul 23, 2022 at 16:47
  • $\begingroup$ @GregMartin ah, you just beat me to it. $\endgroup$ Jul 23, 2022 at 16:50

3 Answers 3


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.

  • 1
    $\begingroup$ My bad, it is very explicitly stated in the last part of the article, this settles a previously unknown question. On the other hand, I still wonder if there is a more elementary way to extend $4$-APs... It is reasonable that $(n+8)^2+(n+1)^2+12n=2n^2+30n+65$ belongs to $E$ pretty often, but maybe also this innocent statement requires heavy machinery (bilinear sieves?). $\endgroup$ Jul 23, 2022 at 17:36
  • $\begingroup$ Luckily not. I have managed to prove that $2n^2+30n+65$ belongs to $E$ infinitely often, by just picking $n$ among the values of a suitable quadratic form. $\endgroup$ Jul 25, 2022 at 13:16
  • $\begingroup$ For those interested in explicit examples: this page lists the longest known APs of primes; the one currently known AP27 does not consist entirely of primes congruent to $1 \pmod 4$, but four of the 25 known AP26's do, and one of them ($465808529215122257 + 72963664 \cdot 23\# \cdot n$) can be extended to an AP27 in $E$. $\endgroup$ Jul 25, 2022 at 18:11

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

  • 1
    $\begingroup$ How did you find your 16 term progression? $\endgroup$
    – Will Jagy
    Jul 24, 2022 at 13:00
  • $\begingroup$ Computer program (VB on Excel - very simple). This is the longest AP with common difference less than 500 in the set of sums of squares less than 2000000. $\endgroup$ Jul 25, 2022 at 7:00
  • $\begingroup$ All right, if we have an AP with length $k$ we also have infinite APs with length $k$ by just multiplying the elements of the former AP by some square. On the other hand, how can we be sure that for some $n$ all the elements of $\{n,n+4,n+8,n+12,n+16\}$ belong to $E$? $\endgroup$ Jul 25, 2022 at 13:23
  • $\begingroup$ Triples of consecutive elements in $E$ are also given by $$2(16x^2+12x+2)^2,(16x^2+16x+3)^2+(16x^2+8x)^2,(16x^2+12x+3)^2+(16x^2+12x+1)^2$$ i.e. by $2n^2,2n^2+1,2n^2+2$ for any $n$ of the form $(4x+1)(4x+2)$. $\endgroup$ Jul 29, 2022 at 10:42

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$


You must log in to answer this question.

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