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\).