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$. 



Distance between primes that are quadratic residues modulo an other prime
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).


