Quadratic Nonresidues and the Combinatorics of Sign Multiplication

Abstract

Let $S$ be a finite, nonempty set of nonzero integers which contains no squares. We obtain conditions both necessary and sufficient for $S$ to have the following property: for infinitely many primes $p$, $S$ is a set of quadratic nonresidues of $p$. The conditions are expressed solely in terms of purely external (respectively, internal) combinatorial properties of the set II of all prime factors of odd multiplicity of the elements of $S$. We also calculate by means of certain purely combinatorial parameters associated with $\prod$ the density of the set of all primes $p$ such that $S$ is a set of quadratic residues of $p$ and the density of the set of all primes $p$ such that $S$ is a set of quadratic nonresidues of $p$.