Squares in arithmetic progression probability

Question

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

Answer 1

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

Answer 2

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)} = ?$