# Bounds on pseudosquares

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.

-
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

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.

-
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
show 1 more comment