Quadratic non-residue problem

Question

For a positive integer $n$, let $a(n)$ the smallest number $k>0$ such that $-n$ is not a quadratic residue modulo $k$.

Using CRT, we can prove that all values of $a(n)$ are prime powers, and every prime power except $2$ appears in the sequence.

See OEIS A354597 .

It's easy to prove that $a(n)\leqslant4n-1$ (take a prime factor $p$ of $4n-1$ such that $p\equiv-1\,(\text{mod }4)$, then $-n$ is not a square modulo $p$).

But according to the figure below, it seems that we can improve the previous inequality !

How to proceed ?

Thanks !

Remark : This question has been asked previouly on math.SE but no response was given.

Answer 1

This question is closely related to Linnik's problem on the least quadratic nonresidue for a given prime modulus.

Let us consider the quadratic Dirichlet character $\chi(m):=\left(\frac{-n}{m}\right)$ whose conductor divides $4n$. Assuming the Riemann hypothesis for $L(s,\chi)$, it follows from a result of Ankeny (see Theorems 1-2 here) that there is a prime $p=O((\log n)^2)$ such that $\chi(p)=-1$. That is, $-n$ is a quadratic non-residue modulo $p$, whence $a(n)\leq p$. We conclude that $a(n)=O((\log n)^2)$. The implied constants can be determined explicitly. The weaker Lindelöf hypothesis leads to the bound $a(n)<n^{o(1)}$, which is the analogue of Linnik's conjecture for the least quadratic nonresidue.

If we don't assume any unproven hypothesis for $L(s,\chi)$, the Pólya-Vinogradov inequality still ensures that $p<n^{\frac{1}{2\sqrt{e}}+o(1)}$, hence also that $a(n)<n^{\frac{1}{2\sqrt{e}}+o(1)}$. See Theorem 9.18 and Corollary 9.19 in Montgomery-Vaughan: Multiplicative number theory I. Furthermore, using Burgess's bound (see Theorem 2 here), the fraction $\frac{1}{2\sqrt{e}}$ in the exponent can be improved to $\frac{1}{4\sqrt{e}}$. Compare with Theorem 9.27 in the quoted book.