0
$\begingroup$

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

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

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

$\endgroup$
2
  • $\begingroup$ what is the final $?$? $\endgroup$ – 1.. Aug 17 '17 at 9:15
  • $\begingroup$ 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. $\endgroup$ – reuns Aug 17 '17 at 9:17
1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ I added an answer about density of squares in a residue class $\endgroup$ – reuns Aug 17 '17 at 6:25
  • $\begingroup$ @reuns , Dear reuns you are wellcome. $\endgroup$ – Davood KHAJEHPOUR Aug 17 '17 at 6:33
  • $\begingroup$ @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. $\endgroup$ – 1.. Aug 19 '17 at 7:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.