This is a refined version of a question I have recently posted.

For a prime $p$, let $\varphi_p\colon\mathbb Z\to\mathbb Z/p\mathbb Z$ denote the canonical homomorphism from the integers onto the group of order $p$.

Given an integer $n\ge 3$, what is the smallest $\varepsilon=\varepsilon(n)>0$ such that for any subset $A\subset\mathbb Z$ with $|A|=n$, not contained in an arithmetic progression with the difference greater than $1$, there exists a prime $p$ satisfying $(1-\varepsilon(n))n\le|\varphi_p(A)|<n$?

To put it simply, I want a prime $p$ distinguishing between the elements of $A$ ``as much as possible", but not distinguishing between all of them - subject to the assumption that $A$ is not contained in a nontrivial arithmetic progression (see this nice construction by Peter Mueller showing that the containment assumption is vital.).

As an example, $\varepsilon(3)=1/3$: for any pairwise distinct integers $a,b,c$ with $\gcd(b-a,c-b,a-c)=1$ there exists a prime $p$ dividing exactly one of $b-a$, $c-b$, and $a-c$.


1 Answer 1


The answer is $\varepsilon(n)=1-\frac{2}{n}$. Clearly, $\lvert\varphi_p(A)\rvert\ge2$ for all primes $p$. However, for every $n\ge2$ there is a set $A$ of size $n$ such that $\lvert\varphi_p(A)\rvert=2$ whenever $\varphi_p$ is not injective on $A$:

Let $P=\{2,3,\ldots,p_{n-1}\}$ be the set of the first $n-1$ primes and $\pi$ be their product. Set $$A=\{0\}\cup\{\frac{\pi}{p}\,|\,p\in P\}.$$ Then $\operatorname{gcd}(A)=1$, so $A$ is not contained in an arithmetic progression with difference $>1$.

For each $p\in P$, exactly one of the elements in $A$ is not divisible by $p$, so $\lvert\varphi_p(A)\rvert=2$.

Now let $p<q$ be distinct elements from $P$. From $\frac{\pi}{p}-\frac{\pi}{q}=\frac{\pi}{pq}(q-p)$ and $0<q-p<p_{n-1}$ we see that all the prime divisors of $\frac{\pi}{p}-\frac{\pi}{q}$ are in $P$. Thus $\lvert\varphi_p(A)\rvert=2$ for $p\in P$, and $\lvert\varphi_p(A)\rvert=n$ for each prime $p>p_{n-1}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.