14
$\begingroup$

Let $x_n$ be the smallest positive integer which is not a quadratic residue modulo any of the first $n$ odd primes. The question is: is there any bound on how quickly $x_n$ grows as a function of $n?$ Now, since the probability of being a residue modulo any given prime is very close to $1/2,$ by an independence heuristic, $x_n$ should grow roughly like $2^n.$ The problem is that independence clearly does not hold here: if you ask the "opposite" question: how big is $y_n,$ the smallest integer which is a square modulo all of the first $n$ odd primes, the answer is $y_n=1.$ When in doubt, experiment, and computing $\log x_n$ for the $n=2, \dotsc, 20$ gives the graph:enter image description here In case you wonder, the slope is around $0.8$ (so a bit bigger than $\log 2,$ but $20$ is pretty small, so $x_n \sim 2^n$ seems like a reasonable guess. Does anyone have any nontrivial bounds, even mod "standard conjectures"?

EDIT Noam Elkies points out that a few more terms have been computed (I have gotten up to 24 in the meantime, but 27 is even better :)) The slope of the log is down to $0.76,$ so the conjecture that $\log(x_n) \sim n \log 2$ seems quite reasonable.

Further Edit In fact, if you ponder Noam's comment, you will note that the heuristic will give something like $\log n 2^n$ for the conjectured growth rate...

More Values Using some of joro's ideas, and a little more, we can push the list of values to 40.

{2, 2, 17, 17, 83, 167, 227, 398, 398, 5297, 64382, 69647, 116387,
214037, 214037, 430022, 5472953, 5472953, 8062073, 8062073, 8062073,
41941577, 86374763, 163520117, 163520117, 231912722, 231912722,
231912722, 545559467, 1728061733, 2832363203, 5638787822, 5638787822, 
6154772762, 6154772762, 7012246247, 7012246247, 7012246247, 6571091781638,    7218195919667}
$\endgroup$
11
  • 1
    $\begingroup$ A few more terms, up to $x_{29} = 1728061733$: oeis.org/A206095 $\endgroup$ Sep 6 '15 at 22:24
  • 1
    $\begingroup$ One might expect the slope to start a bit above $\log 2$, because the probability of $(x/p) = -1$ for small $x$ is $(p-1) \, / \, (2p)$, which is a bit less than $1/2$, and noticeably less for $p$ small. $\endgroup$ Sep 6 '15 at 22:27
  • $\begingroup$ @NoamD.Elkies Thanks! I incorporated this into the latest edit. Sadly, oeis seems to make no further statement... $\endgroup$
    – Igor Rivin
    Sep 6 '15 at 22:32
  • $\begingroup$ @NoamD.Elkies True, but that would probably affect the intercept more than the slope. If you don't control for the intercept, it is, indeed, negative, but the slope than becomes a bit higher. Again, the numbers (be they 20 or 27) are small enough that I would not read too much into them... $\endgroup$
    – Igor Rivin
    Sep 6 '15 at 22:43
  • 1
    $\begingroup$ I think the standard conjecture is that the $n$th prime satisfies $p_n\sim n\log n\sim (\log x_n)(\log\log x_n)/\log 2$, simply transferring from pseudosquare guesses. Which is the same as what you write. $\endgroup$
    – kantelope
    Sep 7 '15 at 15:12
7
$\begingroup$

I'll try to unify all the previous answers (of GH from MO, Will Sawin and Hurkyl) and also indicate unconditional results on this problem. It turns out that one can get a surprisingly decent unconditional upper bound here, which is something I hadn't appreciated fully previously. As noted in Hurkyl's answer above, a unifying problem is the following: Given a non-trivial subgroup $H$ of $({\Bbb Z}/q{\Bbb Z})^*$ with index $h$, bound (i) the least prime $p$ lying in a given coset of $H$, or (ii) the least integer $n$ lying in a given coset of $H$. Obviously the second problem is easier than the first, and as noted in Hurkyl's answer Theorem 1.4 of Lamzouri, Li and Soundararajan gives a good bound on GRH for the first problem: the least prime is essentially bounded by $((h-1) \log q)^2$ (see the precise form) and this result unifies both the least quadratic non-residue problem and also the least prime in an arithmetic progression problem.

Unconditionally, for problem (i), by Linnik's theorem on the least prime in an arithmetic progression we always have a bound of $\ll q^{L}$, for an absolute constant $L$, and the current record here is that $L=5$ is permissible by Xylouris. When $h$ is small, then a somewhat better bound can be given: for $h=2$ (the case of the least prime that splits, or the least prime that is inert in a quadratic field) this is classical and well known, the case of split primes being harder and the bound here is $q^{\frac 14+\epsilon}$ (using Burgess for character sums and Siegel's ineffective bound for $L(1,\chi)$). For larger, but still bounded $h$, the matter was treated by Elliott in the context of the least prime $h$-th power residue, and he obtained the bound $q^{(h-1)/4+\epsilon}$. Of course for large $h$ (i.e. $h\ge 22$) this becomes inferior to Linnik's theorem. A recent paper of Pollack addresses a somewhat more general version of this question, and obtains the bound $\ll q^{(h-1)/4+\epsilon}$.

Now for unconditional results towards the easier problem (ii). Assume that $h \le q^{\epsilon}$ and express the condition of belonging to a coset of $H$ in terms of the characters that are trivial on $H$ (see the paper of Lamzouri, Li and Soundararajan for details). Then use the Burgess bounds on the character sums that arise. This argument gives that the least integer $n$ in any given coset is $\ll q^{\frac 14+\epsilon}$. This is a (modest) improvement over the trivial bound of $q$. For a general modulus $q$ the Burgess bound gives the best known result on this problem. However, for moduli $q$ that are very smooth (and this will be important for the present problem) one can obtain a better result by a $q$-van der Corput argument due to Graham and Ringrose (following Heath-Brown). From the Graham-Ringrose argument (see either the original paper, or Corollary 12.14 of Iwaniec and Kowalski, or estimate (4.1) and Lemma 4.2 from Granville and Soundararajan), one can show that if all the prime factors of $q$ are bounded by $q^{o(1)}$ then the least integer in any prescribed coset is $\ll q^{\epsilon}$ for any fixed $\epsilon >0$. Naturally there is a connection between how small $\epsilon$ can be and the smoothness of $q$, and one can find uniform bounds in the results referenced above.

Returning to the problem at hand, if $p_1, \ldots, p_n$ are the first $n$ odd primes, and we set $q=p_1\cdots p_n = n^{(1+o(1))n}$ and $H$ to be the subgroup of squares mod $q$ (which has index $2^n$) then on GRH we can find a prime $p \ll 4^n (n\log n)^2$ lying in any given coset of $H$. That is given any choice of signs $\epsilon_j = \pm 1$, there is a prime $p\ll 4^n (n\log n)^2$ with $(\frac{p}{p_j}) = \epsilon_j$ (in particular we can take all $\epsilon_j=-1$ as asked for in the problem). This was noted in Hurkyl's answer. Note now that unconditionally by the Burgess estimate we may find a number $N \ll n^{n(1/4+\epsilon)}$ with $(\frac{N}{p_j}) =\epsilon_j$. But note that we are dealing now with a modulus $q$ of size $n^n$ all of whose prime factors are of size $\ll n\log n$; in other words, $q$ is very smooth indeed and Graham-Ringrose applies and gives an unconditional upper bound of $n^{\epsilon n}$. In fact, by keeping track of uniformity, one gets an unconditional upper bound of $n^{c n/\log \log n}$ for some positive constant $c$.

Now consider lower bounds in the problem. Here we must make use of the fact that we are looking for the smallest number $N$ with $(\frac{N}{p_j})=-1$ for all $j\le n$ -- for a random choice of signs $\epsilon_j$ there may of course be a very small number $N$ (just pick the number $N$ and see what the signs are!). Note that $N$ or $4N$ would be a discriminant, and we are asking for a quadratic character $\pmod {N}$ or $\pmod {4N}$ taking value $-1$ on the first $n$ small primes. This fits our framework by taking $q=4N$, and $H$ to be the subgroup of index $2$ on which this character (say $\chi$) is trivial. On GRH we know that there is an odd prime $\ell \le (1+o(1)) (\log N)^2$ with $\chi(\ell) =1$, and so we must have $(\log N)^2 \ge (1+o(1)) n\log n$ or $$ N\ge \exp((1+o(1)) \sqrt{n\log n}). $$ This is the conditional bound mentioned in Will Sawin's answer, and what I indicated in my comment there.
Unconditionally, the Burgess bound and Siegel's theorem argument (for problem (i)) gives that there is a prime $\ell \le N^{\frac 14+\epsilon}$ with $\chi(\ell)=1$, and so $N\ge n^{4+o(1)}$.

To summarize, on GRH we know that the answer lies between $$ \exp((1+o(1)) \sqrt{n\log n} ) \text{ and } \ll 4^n (n\log n)^2 $$ and unconditionally we know that it is between $$ n^{4+o(1)} \text{ and } \ll n^{cn/\log \log n}. $$ The probabilistic conjecture that the answer should be somewhere near $2^n$ seems reasonable.

$\endgroup$
17
$\begingroup$

I think the standard approach to this problem is to estimate the sum $$ S(x) := \sum_{m=1}^x\prod_{k=1}^n\left(1-\left(\frac{m}{p_k}\right)\right), $$ where $p_k$ is the $k$-th odd prime. Indeed, we are looking for the smallest $x$ such that $S(x)>0$.

Factoring out, we get $$ S(x) = \sum_{d\mid p_1\dots p_n}(-1)^{\omega(d)}\sum_{m=1}^x \left(\frac{m}{d}\right).$$ The inner sum equals $x$ for $d=1$, while it is much smaller for $d>1$ due to the oscillating nature of the Jacobi symbol. We can quantify this under GRH using an explicit bound of Chandee (Explicit upper bounds for $L$-functions on the critical line, Proceedings of the AMS), and we infer $$ S(x)=x+O_\epsilon\bigl(2^n e^{(3/8+\epsilon)n}\sqrt{x}\bigr).$$ In particular, under GRH, we see that $x_n$ grows at most exponentially, namely $$ x_n \ll_\epsilon 4^n e^{(3/4+\epsilon)n}.$$

Added. We can improve the above argument by restricting $m$ to prime values exceeding $p_n$ and adding the weights $\Lambda(m)$. We get, by Theorem 5.15 in Iwaniec-Kowalski: Analytic number theory, $x_n\ll 4^n n^5$ (under GRH).

$\endgroup$
15
  • $\begingroup$ Sorry, what does the second last formula mean? There must be a typo of some sort... $\endgroup$
    – Igor Rivin
    Sep 7 '15 at 0:08
  • $\begingroup$ @IgorRivin: Sorry, "$S(x)=$" was missing, I added this. $\endgroup$
    – GH from MO
    Sep 7 '15 at 0:11
  • 4
    $\begingroup$ Can we also use GRH to give a lower bound by upper bounding the sum $\sum_{k=1}^{p_{n+1}-1} \mu(k) \left( \frac{ x } {k} \right)$ for $x$ small, using the fact, from quadratic reciprocity, that $\left( \frac{ x } {k} \right)$ is a Dirichlet character? $\endgroup$
    – Will Sawin
    Sep 7 '15 at 2:48
  • $\begingroup$ @WillSawin: Good idea. I think this way we can get $\log x_n\gg(\log n)(\log\log n)$ or, using more optimistic conjectural upper bounds for $L$-functions perhaps $\log x_n\gg(\log n)^{2-o(1)}$. $\endgroup$
    – GH from MO
    Sep 7 '15 at 7:39
  • 2
    $\begingroup$ The OP's question (with his intent that none of the first $n$ odd primes divide $x_n$) is equivalent to asking for the smallest $x$ such that the first $n$ odd primes are all inert in $\mathbb{Q}(\sqrt{x})$. If you have an upper bound on the smallest odd split prime in terms of the discriminant, then you get a lower bound on $x_n$. $\endgroup$
    – user13113
    Sep 7 '15 at 22:06
8
$\begingroup$

I think one can get a lower bound more like $x_n \geq e^{ c \sqrt{n \log n}}$, or equivalent $p_{n+1} = O ( (\log x_n)^2)$, conditional on GRH. One simply reverses the sign in the argument giving the upper bound on the least quadratic nonresidue to obtain an upper bound on the first prime at which a quadratic Dirichlet character takes the value 1.

This argument is due to Ankeny, in The Least Quadratic Non-Residue. Apply the same argument from Theorem 2 to the Dirichlet character $\chi(d) = \left( \frac{x_n}{d} \right)$. The condition that $\chi(p) = 1$ for small $p$ becomes $\chi(p) = -1$ for small $p$. The same argument goes through with the sign reversed and gives the same bound.

$\endgroup$
5
  • 1
    $\begingroup$ See also Theorem 1.4 of arxiv.org/pdf/1309.3595v1.pdf for a recent explicit version. Also unconditionally, Linnik and Vinogradov knew that the least prime that splits completely in a quadratic field is $\le |D|^{1/4+o(1)}$ (see Pollack ams.org/journals/proc/2014-142-06/S0002-9939-2014-12199-X/… ) ; this follows from the Burgess bounds and Siegel's theorem. $\endgroup$
    – Lucia
    Sep 7 '15 at 14:20
  • 1
    $\begingroup$ @Lucia So you're saying that unconditionally, in Igor's notation, we have $x_n > n^{4 - o(1)}$? $\endgroup$
    – Will Sawin
    Sep 7 '15 at 14:23
  • 1
    $\begingroup$ Yes, that's right. $\endgroup$
    – Lucia
    Sep 7 '15 at 14:23
  • 1
    $\begingroup$ The result of Linnik-Vinogradov is ineffective. This is a substantial difference between the case of $\chi(p)=-1$ versus $\chi(p)=1$ for all the small primes. But under GRH it should not matter (maybe only a log factor somewhere). $\endgroup$
    – kantelope
    Sep 7 '15 at 15:06
  • 1
    $\begingroup$ Your observation is very nice, by the way. $\endgroup$
    – GH from MO
    Sep 7 '15 at 19:41
5
$\begingroup$

Very partial answer for computational approach.

I get $x_{30}=2832363203,x_{31}=x_{32}=5638787822,x_{33}=6154772762$ in relatively short time and other results agree with OEIS.

The performance likely can be greatly improved by working in something faster than sage.

The main idea is to work in many arithmetic progression with large step.

Set $M$ the product of the $k$ odd primes.

Build increasing sequence $0 \le b_i \le M-1$ s.t. $b_i$ is quadratic non-residue modulo the first $k$ odd primes.

Experimentally $|\{b_i\}|$ is significantly smaller than $M$.

Work in the arithmetic progressions $Mj+b_i$ in increasing order.

Sample sage implementation

def igorprimes1(n):
    """
    build M, b_i
    """
    pri=[]
    res=[]
    for k in [ 2 .. n+1]:
        p=nth_prime(k)
        pri += [p]
    for k in xrange(prod(pri)):
        bad=False
        for p in pri:
            if kronecker(k,p) != -1:
                bad=True
                break
        if bad:  continue
        res += [k]

    return res,prod(pri)


def igorprimes2(res,M,n):
    """
    computes x_n = A206095(n)
    """
    pri=[nth_prime(k) for k in [ 2 .. n+1] ]
    r=0
    while True:
        M1=M*r
        for a in res:
            M2=M1 + a
            bad=False
            for p in pri:
                if kronecker(M2%p,p) != -1:
                    bad=True
                    break
            if bad:  continue
            return M2
        r += 1  
$\endgroup$
12
  • $\begingroup$ Actually, my Sage complains when I run igorprimes1(20) that there is some number bigger than a C int. (my original computations were done in a completely brute force manner in Mathematica) $\endgroup$
    – Igor Rivin
    Sep 7 '15 at 13:51
  • 1
    $\begingroup$ @IgorRivin This is normal, $igorprimes1$ doesn't expect such large values (it does loop to 21#/2). Try: tt=igorprimes1(7);igorprimes2(tt[0],tt[1],33) $\endgroup$
    – joro
    Sep 7 '15 at 14:14
  • $\begingroup$ Ah, I was guessing it was something like that! $\endgroup$
    – Igor Rivin
    Sep 7 '15 at 14:23
  • $\begingroup$ You sieve first, then test, but you don't sieve all the way. $\endgroup$
    – Igor Rivin
    Sep 7 '15 at 14:33
  • $\begingroup$ @IgorRivin Something like this -- there are two stages as explained. First find M,b_i, then look for solutions in the arithmetic progressions M j+ b_i. As the code is currently written, it may lose small solutions if the first stage is sufficiently large, but this is easy to fix. $\endgroup$
    – joro
    Sep 7 '15 at 14:55
3
$\begingroup$

Lucia's comment above mentions theorem 1.4 from CONDITIONAL BOUNDS FOR THE LEAST QUADRATIC NON-RESIDUE AND RELATED PROBLEMS : assuming the GRH,

Let $q \geq 20000$, $H$ be a proper subgroup of $G = (\mathbb{Z} / q \mathbb{Z})^\times$, $h = [G : H]$, and $p$ be the smallest prime in a given coset of $H$. Then either $p \leq 10^9$ or $$ p \leq \left( (h-1) \log q + 3(h+1) + \frac{5}{2} (\log \log q)^2 \right)^2$$

If we let $q = \prod_{k=1}^n p_k$ and $H$ be the subgroup of quadratic residues, then the OP asks for the smallest positive integer in a particular coset of $H$. This is bounded above by the smallest prime in the coset, which can be bounded by the theorem.

In particular, we have $h = 2^n$ and $\log q = (1 + o(1)) n \log n$, and consequently we infer

$$ x_n = O\left( 4^n n^2 (\log n)^2 \right)$$

This is a slight improvement over the answer above.

$\endgroup$
3
  • $\begingroup$ Cool! By the way, if you look at the numbers (well, let your computer look at them...) about 1/2 are primes. I am not sure if this trend continues... $\endgroup$
    – Igor Rivin
    Sep 11 '15 at 12:14
  • $\begingroup$ Good observation! $\endgroup$
    – GH from MO
    Sep 11 '15 at 12:49
  • $\begingroup$ By the way, none of the answers mention any nontrivial unconditional upper bound. Is there really nothing one can say? $\endgroup$
    – Igor Rivin
    Sep 11 '15 at 12:55
2
$\begingroup$

On the possible precision of an asymptotic estimate...

At "random" we expect $x_{n+1} = x_n$ with probability 1/2. For any particular size $B$, we expect there to be some $n \sim B$ with $x_n = x_{n + \lfloor \log_2 B \rfloor}$.

Supposing that we estimate $x_n \sim 2^n \log n$, if $n$ is as above we have

$$ 2^n \log n \sim 2^{n + \log_2 n} \log(n + \log_2 n) $$

Consequently, if this is the right estimate, it is unlikely that it can be stated more precisely than

$$ x_n = 2^{n + O(\log n)} $$


If we treat a quadratic residue as a Bernoulli random trial with probability 1/2, then we can model

$$x_n \approx G_n \log n$$

Where $G_n$ is a geometric random variable with parameter $1/2^n$, and $\log n$ estimates the effect of having to be relatively prime to the first $n$ odd primes.

Recall that the cumulative distribution for a geometric random variable is given by

$$ P(G_n > m) = (1 - 1/2^n)^m \approx \exp(-m/2^n) $$

We have

$$ P(G_n < a \log n \, 2^n) \approx 1 - n^{-a} $$

If we blithely assume the $G_n$ are independent random variables, then we have

$$ P(\forall n: G_n < a \log n\, 2^n) = \prod_n (1 - n^{-a}) $$

which diverges to zero if $a=1$. Therefore:

  • $\forall n: x_n < 2^n (\log n)^2$ happens with probability zero
  • $x_n = O(2^n (\log n)^2)$ with probability 1

Similarly,

$$ P(G_n > c 2^n / n^a) \approx \exp(-c/n^a) $$ $$ P(\forall n: G_n > 2^n / n^a) \approx \exp\left (-\sum_{n=1}^{\infty} 1/n^a \right) $$

and therefore

  • $x_n = \Omega(2^n (\log n) / n)$ happens with probability zero
  • $x_n = \Omega(2^n (\log n) / n^{1+\epsilon})$ with positive probability

A more accurate model which makes the $G_n$ truly independent would be $x_n \approx x_{n-1} + B_n G_n \log n$ where the $B_n$ are independent Bernoulli random variables with parameter $1/2$. I'm pretty sure this doesn't affect the asymptotics above, but I have not verified it.

This implies that the estimate $x_n = 2^{n + O(\log n)}$ given in the initial section should be expected to happen "at random" with probability 1, and we can't expect to do better in the sense that $x_n = 2^{n + o(\log n)}$ should happen with probability 0.

$\endgroup$
6
  • $\begingroup$ Certainly, the experiments indicate that there is a lot of jumping around, so I am sure you are right. Do you think that even this level of precision is possible? $\endgroup$
    – Igor Rivin
    Sep 10 '15 at 7:10
  • $\begingroup$ See the last two data points, just added :) $\endgroup$
    – Igor Rivin
    Sep 10 '15 at 7:12
  • $\begingroup$ I'm not sure. My main tool for conjecturing these things is to model everything as random variables, but I haven't fully worked out the right model, and I feel this example is outside of the domain where I have confidence the approach I want to use will give reasonable results anyways. $\endgroup$
    – user13113
    Sep 10 '15 at 7:47
  • $\begingroup$ ... but my impression is that this approach leads to $E(x_n) \approx 2^n \log n$ and $Var(x_n) \approx 4^n (\log n)^2$, which would suggest that you can't do better than $O(2^n \log n)$ (and I haven't worked out the probability that such an expression holds for all of the random variables!). But my vague impression is that in these sorts of problems, the actual distributions tend not to vary to such great extremes as might be predicted by a simple random model. $\endgroup$
    – user13113
    Sep 10 '15 at 8:08
  • $\begingroup$ The model I used, incidentally, is that $x_n = x_{n-1} + G_n B_n \log n$, where the $G_n$ and $B_n$ are independent, $B_n$ is a bernoulli variable with parameter 1/2 (to reflect the possibility that $x_n = x_{n-1}$), and $G_n$ is geometric with parameter $1/2^n$ (to reflect the need to do more random trials until you find all non-residues). (and the $\log n$ factor represents the need to be relatively prime to the first $n$ odd primes) $\endgroup$
    – user13113
    Sep 10 '15 at 8:13

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.