Let denote the set of all primes and, for , let denote the Legendre quadratic residue symbol mod p. Let denote the set of natural numbers and let
denote the mapping so the th component of is where denotes the th prime in . The following result is “well-known” (or, as the joke goes, it’s well-known to those who know it well:-).
Theorem: The restriction of to the subset of square-free integers is an injection.
In fact, one can be a little more precise. Let denote the set of the first primes, let denote the set of square-free integers , and let
denote the mapping
Theorem: For each , there is an such that the restriction of to the subset is an injection.
I am no expert in this field, so perhaps the following question is known.
Question: Can one give an effective upper bound on as a function of ?
I’ve done some computer computations using SageMath and it seems to me that
(i.e., there is a linear bound) is possible. On the other hand, my computations were pretty limited, so that’s just a guess.