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