Questions about quadratic residues

Let P denote the set of all primes and, for p \in P, let (*/p) denote the Legendre quadratic residue symbol mod p. Let {\mathbb N}=\{1,2,\dots\} denote the set of natural numbers and let

L: {\mathbb N}\to \{-1,0,1\}^P,

denote the mapping L(n)=( (n/2), (n/3), (n/5), \dots), so the kth component of L(n) is L(n)_k=(n/p_k) where p_k denotes the kth prime in P. 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 L to the subset {\mathbb S} of square-free integers is an injection.

In fact, one can be a little more precise. Let P_{\leq M} denote the set of the first M primes, let {\mathbb S}_N denote the set of square-free integers \leq N, and let

L_M: {\mathbb N}\to \{-1,0,1\}^{P_M},

denote the mapping L_M(n)=( (n/2), (n/3), (n/5), \dots, (n/p_M)).

Theorem: For each N>1, there is an M=M(N)>1 such that the restriction of L_M to the subset {\mathbb S}_N 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 M=M(N)>1 as a function of N>1?

I’ve done some computer computations using SageMath and it seems to me that

M=O(N)

(i.e., there is a linear bound) is possible. On the other hand, my computations were pretty limited, so that’s just a guess.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s