Let $K$ be a number field, and $p$ be a rational prime. Then the Chebotarev Density Theorem implies we can find primes $v$ and $w$ of $K$ of degree 1 which are split and nonsplit respectively in $K[\sqrt{p}]$. What is the best known effective (upper) bound for the norms of the least such primes (not assuming GRH)? In particular, is there a bound which is asymptotically strictly less than $\sqrt{p}$ (times a constant coming from the field $K$)?
EDIT: I'd like to clarify, in response to the comments below. The situation I'm wondering about is when we fix K, and let p vary. So when K is a cyclotomic field (adjoin, say, the qth root of unity for a prime q), I'm asking about the least prime which is a quadratic nonresidue (resp. residue) mod p, which is 1 mod some fixed prime q, and I'm hoping that there is a bound of the form $\sqrt{p}$ times (something in terms of q). Under GRH this is true — in fact under GRH, we can get a bound of the shape $(\log p)^2$ times constants coming from K.
Best Answer
I assume $\sqrt{p}$ is not contained in $K$, then the bound you are looking for is available.
Let $\chi$ be the ray class character attached to the quadratic extension $K(\sqrt{p})/K$, then the $L$-function $L(s,\chi)$ has conductor essentially $p$. By a recent result of Venkatesh (Theorem 6.1 in Annals of Math. 172 (2010), 989-1094) we have the subconvex bound $L(s,\chi)\ll |s|^N p^{1/4-1/200}$ on the criticial line $\Re s=1/2$, where $N>0$ is a constant. It follows, by a simple Mellin transformation technique, that for any fixed smooth function $V:(0,\infty)\to\mathbb{C}$ of compact support we have
$$\sum_{\mathfrak{m}\subset\mathcal{O}_K}\chi(\mathfrak{m})V(N\mathfrak{m}/X)\ll p^{1/4-1/200} X^{1/2}.$$
Therefore the absolute value of the left hand side is smaller than $X$ for some $X\gg p^{1/2-1/100}$, where the implied constant depends only on $K$ and $V$. This implies that $\chi$ takes both values $\pm 1$ on prime ideals with norm $\ll p^{1/2-1/100}$.
Perhaps one can complement this with Vinogradov's trick, see Corollary 9.19 in Montgomery-Vaughan: Multiplicative number theory I.
EDIT: As the OP pointed out, all the $p$'s above should be replaced by $p^{(K:\mathbb{Q})}$.