Welcome to MathOverflow

Question

3

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.

edited Apr 3 2012 at 14:23

asked Mar 29 2012 at 3:47

Charles
4,139●8●26

2

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 2012 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 2012 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 Apr 3 2012 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 2012 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 Apr 4 2012 at 2:50

GH · Accepted Answer · 2012-04-03 23:29:34Z UTC

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.

Bounds on pseudosquares

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.