MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose $n\in\mathbb{Z}^+$ is a nonsquare in $\mathbb{Z}$ but is a square mod $2^2,3^2,4^2,5^2,\ldots,k^2.$ How small can $n$ be?

On the ERH, there are no small pseudosquares: $L_p>e^{\sqrt{p/2}}$. Heuristically, more is true: $\log L_p\gg p/\log p.$ I am looking for an unconditional lower bound, even if very weak. Are any known?

Even knowing that $L_p>p^3$ would be useful to me.

share|cite|improve this question
I don't know. Perhaps a good starting point wqould be R F Lukes, C D Patterson, H C Williams, Some results on pseudosquares, Math. Comp. 65 (1996), no. 213, 361–372, S25–S27, MR1322892 (96e:11010). Here are numerical results as well as conditional results and conjectures on numbers pseudosquare mod all primes up to a given $x$. – Gerry Myerson Mar 29 '12 at 4:51
@Gerry: LPW is good, and see also Sorenson's 2008/2010 preprint. But neither give unconditional lower bounds, just the standard result (due to Cobham?) on the ERH. I need only a very weak lower bound; $n>2k^2$ for $k>100$ would suffice. – Charles Mar 29 '12 at 14:09
What is the motivation behind restricting the moduli to squares? To me it would be more natural to consider $n$ modulo $1,2,\dots,k$. Note that for your purposes the two formulations are equivalent: if $n$ is a square modulo $1^2,2^2,\dots,k^2$ then it is a square modulo $1,2,\dots,k$. Conversely: if $n$ is a square modulo $1,2,\dots,k$ then it is a square modulo $1^2,2^2,\dots,[\sqrt{k}]^2$. – GH from MO Apr 3 '12 at 17:04
@GH: It was just the form that came naturally in the problem I was working on. After writing it out I saw the equivalence and titled the problem as I did. – Charles Apr 3 '12 at 17:24
@Charles: In the "EDIT" section I prove $n\geq C_\epsilon k^{3-\epsilon}$ without the coprimality assumption. Here $C_\epsilon$ is effective as in the original bound, but it is slightly harder to determine it because of the complexity of Burgess' bound. – GH from MO Apr 4 '12 at 2:50
up vote 5 down vote accepted

I will assume that $n$ is coprime to $2,3,\dots,k$. (In "EDIT" below I give a weaker bound for the case when this condition is not met.)

Let $n=m^2 d$, where $d>1$ is square-free. Then $r\mapsto (\frac{d}{r})$ is a nontrivial (quadratic) character mod $4d$. By assumption, $(\frac{d}{p})=(\frac{n}{p})=1$ for any prime $p\leq k$, hence also $(\frac{d}{r})=1$ for any integer $r\leq k$. By a result of Vinogradov (see Corollary 9.19 in Montgomery-Vaughan: Multiplicative number theory I), it follows that for any $\epsilon>0$ we have a bound $$ n\geq d > C_\epsilon \ k^{2\sqrt{e}-\epsilon}, $$ where $C_\epsilon>0$ is a constant. For example, $n$ exceeds $k^3$ for $k$ sufficiently large. One can make this bound more precise by following the proof of the mentioned result.

EDIT. The following argument gives a comparable bound without the assumption that $n$ is coprime to $2,3,\dots,k$. It incorporates a suggestion by Noam Elkies (for which I am grateful). As before, we can conclude that $(\frac{n}{r})\geq 0$ for any integer $r\leq k$. Let us assume, without loss of generality, that $n\leq k^3$. Then $(\frac{n}{p})=0$ holds for at most $O(\log k)$ primes $p$, hence $(\frac{n}{p})=1$ holds for at least half of the primes $p\leq k$. It follows, using also Burgess' bound (J. London Math. Soc. 33 (1986), 219-226), that $$ k^{1-\epsilon}\ll \sum_{r=1}^k \left(\frac{n}{r}\right) \ll k^{2/3} n^{1/9+\epsilon}, $$ where the implied constants depends only on $\epsilon>0$. As a result, for any $\epsilon>0$ we have a bound $$ n\geq C_\epsilon \ k^{3-\epsilon}, $$ where $C_\epsilon>0$ is a constant.

share|cite|improve this answer
The exponent can be doubled to $4\sqrt{e} - \epsilon > 6.5$ using the Burgess bound (at least for prime $d$, but probably composite too). But that's still much smaller than the expected exponential growth. – Noam D. Elkies Apr 3 '12 at 19:32
Would you give the weaker bound that does not assume coprimality? – Charles Apr 3 '12 at 19:56
Also, is it possible to make $C_\epsilon$ explicit, or does the method not allow that? – Charles Apr 3 '12 at 19:58
@Noam: I agree, thanks for the comment! – GH from MO Apr 3 '12 at 21:01
@Charles, it is straightforward to make $C_\epsilon$ explicit. My quick calculation shows it can be chosen as $C \epsilon^2$, where $C>0$ is a reasonable absolute constant. – GH from MO Apr 3 '12 at 21:18

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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