Distance between primes that are quadratic residues modulo an other prime

Question

Question: Is there an infinite sequence of primes $\{q_i\}_{i=1}^{\infty}$ that is not too sparse ( $q_n =O(poly(n))$ for a fixed polynomial) for which it is true that for every $k$ there is an $N(k)$ so that if $n>N$ then there is a prime $p$ in the interval $[q^{1/k}-o(q^{1/k}),q^{1/k})$ that is a quadratic residue modulo $q$? (by $o(q^{1/k})$ I mean does there exist an function that belongs to the class $o(q^{1/k})$ for which such a statement holds?) (Does the question become easier if we ask for a non-residue?)

Motivation: I need dense, regular, $C_{2k}$-free non bipartite graphs that are good expanders. There are constructions of dense, regular, $C_{2k}$-free graphs that are good expanders by Margulis and independently by Lubotzky, Phillips and Sarnak. These constructions depend on two primes, $p$ and $q$ and they give a suitable graph if $p$ is a quaratic residue modulo $q$, and an almost suitable but bipartite graph when $p$ is a quadratic non-residue.

Additional information: If we do not need $p$ to be a quadratic residue, bounds between consecutive primes does the job.

Edit: I realized that i accidentally posed a harder than necessary problem. For my purposes it is enough to have one such sequence for every $k$, and even the polynomial $poly(n)$ can depend on $k$.

Answer 1

Let $k>2$ and $0<\epsilon<1$ be fixed real numbers (see also the Added section below). Let $x$ be a large parameter. It suffices to show that there exists a prime pair $(p,q)$ such that $x<p<2x$ and $p^k<q\leq p^k(1+\epsilon)$ and $\left(\frac{p}{q}\right)=1$. Note that for primes $p\equiv 1\pmod{4}$, the last condition is equivalent to $\left(\frac{q}{p}\right)=1$. Let us now call a prime $p$ bad if $p\equiv 1\pmod{4}$ and there exists no prime $q$ such that $p^k<q\leq p^k(1+\epsilon)$ and $\left(\frac{q}{p}\right)=1$. The number of all primes $p\in(x,2x)$ with $p\equiv 1\pmod{4}$ is $\gg x/\log x$, hence it suffices to show that the number of bad primes $p\in(x,2x)$ is $\ll x/(\log x)^2$.

For a prime $p>2$, let $\chi_p$ (resp. $1_p$) denote the quadratic (resp. trivial) Dirichlet character mod $p$. If $p$ is bad, then with the usual notations we have $$\sum_{\substack{p^k<n\leq p^k(1+\epsilon)\\\chi_p(n)=1}}\Lambda(n)\ll p^{k/2}=o(p^k),$$ because the primes do not contribute to the left hand side, hence also $$\left(\psi(p^k(1+\epsilon),1_p)-\psi(p^k,1_p)\right)+\left(\psi(p^k(1+\epsilon),\chi_p)-\psi(p^k,\chi_p)\right)=o(p^k).$$ The first difference is $\gg p^k$ by Chebyshev's theorem, hence for a bad prime $p$ we have $$\left|\psi(p^k(1+\epsilon),\chi_p)-\psi(p^k,\chi_p)\right|\gg p^k,$$ hence also $$\max_{y<2^{k+1}x^k}\left|\psi(y,\chi_p)\right|\gg p^k.$$ On the other hand, by the usual proof of the Bombieri-Vinogradov theorem (see e.g. Chapter 24 in Huxley: The distribution of prime numbers) we can see that that $$\sum_{x<p<2x}\;\max_{y<2^{k+1}x^k}\left|\psi(y,\chi_p)\right|\ll\frac{x^{k+1}}{(\log x)^2},$$ using that $x$ is large and $k>2$. As we observed above, for a bad prime $p\in(x,2x)$ the corresponding term on the left hand side is $\gg x^k$, whence the number of such primes is $\ll x/(\log x)^2$. The proof is complete.

Added. In fact the original conclusion holds for all $k>0$. One can derive this in a simpler way from Theorem 1 in Heath-Brown: A mean value estimate for real character sums (Acta Arith. 72 (1995), 235-275).

Answer 2

OK. The revised form of the question which is easily resolved is: given a parameter $k$, is there a sequence of primes $q$ which satisfy a certain bound so that there correspond primes $p$ with nice_relation $(q,p)$ holding? This is slightly different from the original version (which I suspect also is true) which is: does there exist q such that for all k there exist p and N such that (statement of problem). Since the (forall k) has been removed, we get a statement of lower logical complexity, hopefully making a proof easier.

We can rewrite it as (exist p)(exist q) stuff or (exist q)(exist p) stuff. Since p will be smaller than q for the application (and since we have quadratic reciprocity) we can write it in the form (exist p)(exist q) [ (q is a qr of p) and (stuffinvolving(p,q,k))].

When we write it this way ($q$ being a quadratic residue mod $p$) instead of in the original statement ($p$ a qr mod $q$), my brain quickly jumps to ($q$ belongs to a certain set of residue classes mod $p$). So now I think of $q$ belonging to certain sets parameterized by $p$, which is easier (in the context of stuff about to appear) than trying to make $p$ belong to sets parameterized by $q$. In this case, I want $q$ sufficiently sized and belonging to one of certain residue classes mod $p$.

Now the stuff involving $k,q$ and $p$ is not too bad: we just want $p$ and $q$ prime, with $p^k \lt q \lt F$, where $F$ is some fudge factor quantity we will fill in later to get $p \gt q^{1/k} - o(q^{1/k})$. For practice, we will set $F=2p^k$, and adjust it downwards later.

So I have massaged the question to selecting a sequence of primes p so that we can find a sequence of primes $q$ (with each $q$ corresponding to $p$ is so that $q$ is) lying in a certain interval near $p^k$. We picked the interval (by our choice of $F$) large enough that we can guarantee (by Bertrand's postulate) that there is a prime $q$ in the interval. But what about $q$ being a quadratic residue mod $p$?

If we think as above of this meaning $q$ is in some residue classes mod $p$, then we can turn to some specializations of the Chebotarev density theorem, which is a statement involving algebraic number theory and abstract number fields. Fortunately, the specialization applies here and says roughly that primes are uniformly distributed among the (nonzero mod $p$) residue classes. There are effective forms (some of which are on MathOverflow) which say what to expect in the distribution in intervals. My belief (meaning work for you) is that for an interval as large as $(p^k,2p^k)$, the distribution of primes mod $p$ is very uniform, and this holds well for intervals of smaller length (say length $p^{2k/3}$).

So now, you need to select $p$ so that $q$ grows fast enough to exceed $p^k$ but not so fast that $q$ grows superpolynomially in $n$, and Chebotarev says $q$ exists not too far from $p^k$. You have a lot of freedom in choosing $p$, and not much less in choosing $q$. If you are careful (and are not asking too much), you can select the sequences of $p$ and $q$ and work the (forall k) back in so that the original statement holds for the given sequence pair $(p_n,q_n)$.

If we did not have quadratic reciprocity (and temporary freedom to pick p and then q) one would try looking for $q$ big so that one would find small $p$ with the right property, which is like using a microscope to search a haystack for a needle. If there are lots of needles, a magnet (or even a magnifying glass) is quicker.

Gerhard "Is Practicing Mathematics For Astigmatics" Paseman, 2018.11.13.