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.

2more comments