Suppose $a$ is a square-free integer and $\left(\frac{a}{p}\right)=1$ for the primes $p\leq k$. I'll call $a$ a quasi-square of order $k$. What I am interested in is the maximum value of $k$ in terms of $a$. For instance if $a$ is a prime which is $1$ mod $4$ then by quadratic reciprocity, we are really asking about the least non-residue mod $a$. So on the GRH we have $k=O((\log a)^2)$. But if we think about these symbols as coin flips, then I would suspect that after about $\log_2 a$ primes we should see a $-1$. So, since the $n$'th prime is about $n\log n$ one might guess that $k$ should be not much larger than $(\log_2 a)(\log\log a)$. Is this reasonable? Is there a well-known conjecture which suggests this? Does it hold on average?

Edit: As further justification, if we look at all $N\leq a\leq 2N$ then checking that $\left(\frac{a}{p}\right)=1$ rules out half of the integers in this range. So we should be run out of integers after about $\log_2 N$ primes. Of course the squares will remain, but that should be it.

  • $\begingroup$ What you call a quasi-square is known in the literature as a pseudosquare. See, e.g., MR2282926 Wooding, Kjell; Williams, Hugh C. Doubly-focused enumeration of pseudosquares and pseudocubes. Algorithmic number theory, 208–221, Lecture Notes in Comput. Sci., 4076, Springer, Berlin, 2006. $\endgroup$ Jul 8 '15 at 0:41

For fixed $a$, the function $\big( \frac ap \big)$ defines a Dirichlet character (mod $4a$) (and often modulo a smaller modulus). More precisely, the Jacobi symbol $\big( \frac an \big)$ defines such an extension of the Legendre symbol to all odd $n$ (simply by multiplicativity), and that extension is a Dirichlet character.

So everything you know about least nonresidues of Dirichlet characters holds here: unconditionally there is a prime $p \ll a^{1/4\sqrt e+\epsilon}$ for which $\big( \frac ap \big)=-1$, and on GRH there is such a prime $p \ll \log^2 a$, as you've noted. I don't remember the heuristic for what the best possible bound should be, but the order of magnitude $\log a \cdot \log\log a$ or $\log a\cdot(\log\log a)^2$ seems plausible.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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