# Squares in arithmetic progression probability

Given a prime $p$ and integer $u$ with $0<u<p$, what is the probability there is a $t\in\Bbb Z$ such that there is a square of form $v=u+tp$ with $0<v<p^2$?

• How is this different from asking whether $u$ is a quadratic residue mod $p$? – Erick Wong Aug 17 '17 at 1:25

To add on Famke's answer, even if there is an elementary solution, we can solve the density of squares $\equiv a \bmod q$ using L-functions (see Apostol's book on number theory)

Let $$F(s,q,a) = \sum_{n \equiv a \bmod q} 1_{n \in \mathbb{N}^2} n^{-s}$$

As $\frac{1}{\phi(q)}\sum_{\chi \bmod q} \overline{\chi(a)}\chi(n) = 1_{n \equiv a \bmod q}$ where $\chi$ are the Dirichlet characters modulo $q$,

we obtain $$F(s;q,a) = \frac{1}{\phi(q)}\sum_{\chi \bmod q} \overline{\chi(a)}\sum_{n=1}^\infty \chi(n) 1_{n \in \mathbb{N}^2} n^{-s}= \frac{1}{\phi(q)}\sum_{\chi \bmod q} \overline{\chi(a)} L(2s,\chi^2)$$

And hence, by inverse Mellin transform and the residue theorem $$\sum_{n \le x, n \equiv a \bmod q} 1_{n \in \mathbb{N}^2} = \frac{1}{2i\pi}\int_{\sigma-i\infty}^{\sigma+i\infty} F(s;q,a)\frac{x^s}{s}ds\sim Res(F(s;q,a)\frac{x^s}s,1/2) \\ =\frac{1}{\phi(q)}\sum_{\chi \bmod q, \chi^2 = \chi_0}\overline{\chi(a)} Res(L(2s,\chi^2)\frac{x^s}s,1/2)= C\frac{x^{1/2}}{ q}$$

where $C= \sum_{\chi \bmod q, \chi^2 = \chi_0}\overline{\chi(a)} = ?$

• what is the final $?$? – 1.. Aug 17 '17 at 9:15
• Do you understand the rest ? And if $a$ is not a quadratic residue $\bmod q$ then $C= 0$. If $a$ is a quadratic residue then $C$ should be $1$, but I'm not sure. – reuns Aug 17 '17 at 9:17

First case: Let $u$ to be a quadratic non-residue module $p$; so in this case it is $\color{Red}{\text{impossible}}$ to choose a square in the arithmetic progression $\{ tp+u \}_{t \in \mathbb{N}_0}$,

and this implies that the $\color{Red}{\text{probability is equal to zero}}$.

Second case: Let $u$ to be a quadratic residue module $p$; i.e. there is an integer $A$ such that $A^2 \overset{p}{\equiv}u$. Let choose $0 < a < p$ such that it is congruent to $A$ module $p$.

In this case we have $p-1$ choices for choosing a square less than $p^2$, but we have only two choices which is congreuent to $u$ module $p$.

[ These two choices are $a^2$ and $(p-a)^2$, which have the corresponding $t$, respectively equal to $\dfrac{a^2-u}{p}$ and $\dfrac{(p-a)^2-u}{p}$. ]

So by the assumption of uniform distribution the probablity is equal to $\color{Red}{\dfrac{2}{p-1}}$.

# (II)Another question:

If we are possible to choose $v$ as large as we want;

i.e. there is no bound on $v$,

i.e. delete the restriction on $v$; then the answer is:

First case: Let $u$ to be a quadratic non-residue module $p$; so in this case it is $\color{Red}{\text{impossible}}$ to choose a square in the arithmetic progression $\{ tp+u \}_{t \in \mathbb{N}_0}$,

and this implies that the $\color{Red}{\text{probability is equal to zero}}$.

Second case: Let $u$ to be a quadratic residue module $p$; in this case by the assumption of uniform distribution the probablity is again equal to $\color{Red}{\dfrac{2}{p-1}}$.

# (III)Yet another question:

Given a prime number $p$ and an integere $u$ with $0<u<p$. We will choose number from the arithmetic progression $\{ tp+u \}_{t \in \mathbb{N}_0}$.

What is the probability that, this integer to be a square?

First case: Let $u$ to be a quadratic non-residue module $p$; so in this case it is $\color{Red}{\text{impossible}}$ to choose a square in the arithmetic progression $\{ tp+u \}_{t \in \mathbb{N}_0}$,

and this implies that the $\color{Red}{\text{probability is equal to zero}}$.

Second case: Let $u$ to be a quadratic residue module $p$; in this case by the assumption of uniform distribution the probablity (density) is equal to $\color{Red}{0}$, $\color{Red}{\text{But it is not impossible}}$ .

[ In this case there exists such integers, but the probablity (density) is equal to $\color{Red}{0}$ . ]

# (IV)Yet another question:

Given a prime number $p$ and an integere $u$ with $0<u<p$. We will choose number from the arithmetic progression $\{ tp+u \}_{t \in \mathbb{N}_0}$ such that it is smaller than $p^2$.

What is the probability that, this integer to be a square?

First case: Let $u$ to be a quadratic non-residue module $p$; so in this case it is $\color{Red}{\text{impossible}}$ to choose a square in the arithmetic progression $\{ tp+u \}_{t \in \mathbb{N}_0}$,

and this implies that the $\color{Red}{\text{probability is equal to zero}}$.

Second case: Let $u$ to be a quadratic residue module $p$; in this case we have $p-1$ choices for choosing a number from the arithmetic progression $\{ tp+u \}_{t \in \mathbb{N}_0}$ smaller than $p^2$, but we have only two choices for this integer to be a square.

[ These two choices are $\dfrac{a^2-u}{p}$ and $\dfrac{(p-a)^2-u}{p}$, which have the corresponding $v$, respectively equal to $a^2$ and $(p-a)^2$. ]

So by the assumption of uniform distribution the probablity is equal to $\color{Red}{\dfrac{2}{p-1}}$.

Lemma: Given a prime $p$ and integer $u$ with $p \nmid u$,

the probablity for $u$ to be a quadratic residue module $p$ is equal to $\color{Red}{\dfrac{1}{2}}$;

and the probablity for $u$ to be a quadratic non-residue module $p$ is equal to $\color{Red}{\dfrac{1}{2}}$.

By this lemma, without knowing that $u$ to be reside or non-reside;

i.e. without splitting in two cases

for the first and the last question the probability is equal to $\color{Blue}{\dfrac{1}{p-1}}$;

and for the second and the third question the probability is equal to $\color{Blue}{0}$.

• I added an answer about density of squares in a residue class – reuns Aug 17 '17 at 6:25
• @reuns , Dear reuns you are wellcome. – Davood KHAJEHPOUR Aug 17 '17 at 6:33
• @Famke I was actually thinking of this. If $a,b$ are integers then the class $a^2\bmod p$ contains a square in $[0,p^2]$ and the class $a^2\bmod q$ contains a square in $[0,q^2]$. And the class $a^2\bmod pq$ contains a square in $[0,p^2q^2]$. Now suppose the class $ab\bmod p$ contains a square in $[0,p^2]$ and the class $ab\bmod q$ contains a square in $[0,q^2]$ the what is the probability that the class $ab\bmod pq$ contains a square in $[0,p^2q^2]$ where $ab$ is not a perfect square? This is why I asked the query. – 1.. Aug 19 '17 at 7:35