Yet Another Mathblog

Questions about quadratic residues

Posted on 2018/12/11 by wdjoyner

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 $k$ th component of $L(n)$ is $L(n)_k=(n/p_k)$ where $p_k$ denotes the $k$ th 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 Cancel reply

Enter your comment here...

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

Email (required) (Address never made public)

Name (required)

Website

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

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

Connecting to %s

%d bloggers like this: