Quadratic residues and nonresidues of arbitrary patterns

Question

Let $p_1, p_2, \dotsc, p_n$ be distinct primes, and let $\epsilon_1, \epsilon_2, \dotsc, \epsilon_n$ be an arbitrary sequence of $1$ and $-1$.

There is an integer $a$ such that $\left( \frac{a}{p_1} \right) = \epsilon_1, \left( \frac{a}{p_2} \right) = \epsilon_2, \dotsc, \left( \frac{a}{p_n} \right) = \epsilon_n$, where $\left( \frac{a}{p_i} \right)$ denotes Legendre's symbol.

What can we say about the number $a$? -- I couldn't find any results for such numbers.

In particular, I am interested in bounds for the smallest possible $|a|$.

Could you recommend any papers or books on the topic?

EDIT

It's better to write "distinct odd primes" for $p_1, p_2, \dotsc, p_n$.

I have checked for several primes $< 1000$ by using computer. The smallest $a > 0$ does not seem to go beyond the product of two largest primes.

Answer 1

Noam Elkies argument here shows that some such $A$ must occur among any consecutive $\prod (p_i+3)/2 +1$ integers. In Elkies notation, take $a_i = p_i$; take $A_i$ to be the $(p_i-1)/2$ residue classes modulo $p_i$ which are "good" and take $Z_i$ to be the $(p_i+1)/2$ residue classes which are "bad". I expect one can do better than this.

Answer 2

The number of integers $a$ in $[0, x]$ with the desired property is $$ 2^{-n}\sum_{a=1}^x\prod_{i=1}^n\left(1+\epsilon_i\left(\frac{a}{p_i}\right)\right). $$ Expand the right hand side to obtain one term $2^{-n} x$, and $2^n-1$ sums of the form $2^{-n}\sum_{a\leq x}\left(\frac{a}{q}\right)$, where $q$ is the product of some of the $p_i$. Since sums over non-trivial characters can be bounded, for $x$ sufficiently large the term $2^{-n} x$ dominates, and we obtain that some $a$ exists.

To get a bood upper bound on $a$ you need some specific bound on character sums. There are several such bounds, which to use depends on the information you have for the $p_i$. In general one can use Burgess bounds, and obtains that for any $\epsilon>0$ there exists some $C_\epsilon$, such that $a<2^{C_\epsilon n}q^{\frac{1}{4}+\epsilon}$, where $q=\prod p_i$. If the $p_i$ are all small, one should obtain better results from zero-free regions for Dirichlet $L$-series. If the $p_i$ are of different magnitude, then most of the occurring charactersums are much smaller then $\prod p_i$, thus one can reduce the influence of $n$.

Answer 3

For each $i$ pick some $b_i$ so that

$$\left( \frac{b_i}{p_i} \right)=\epsilon_i$$

Now, by the Chinese Remainder Theorem, there exists an $a$ so that

$$a \equiv b_i \mod p_i$$

I think that it follows that there are exactly $\prod \frac{p_i-1}{2}$ solutions modulo $p_1..p_n$ (of course we need $p_i \neq 2$, or $p_i=2 \Rightarrow \epsilon_i=1$ and then the formula changes slightly), so a very rough upperbound is

$$\frac{1}{2}\prod p_i - \prod \frac{p_i-1}{2}$$

Better upperbound can probably be obtained by using the formula for CRT and some upperbounds for the solutions modulo primes.