2
$\begingroup$

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$, there exists a prime $p$ satisfying $(1-\varepsilon(n))n<|\varphi_p(A)|<n$?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

Maybe I misunderstand the question, but doesn't the set $A=\{i\cdot n!\,|\,1\le i\le n\}$ have $\lvert\varphi_p(A)\rvert=1$ for all $p$ for which $\varphi_p$ is not injective on $A$?

Improve this answer
$\endgroup$
2
  • $\begingroup$ Great! Can you think of a counterexample given that $A$ is not contained in an arithmetic progression with the difference greater than $1$? $\endgroup$
    – Seva
    Commented May 9, 2023 at 19:08
  • $\begingroup$ @Seva You mean "counterexample" in the sense that $\lvert\varphi_p(A)\rvert$ is unexpectedly small, for instance $\lvert\varphi_p(A)\rvert=2$ for all $p$ where $\lvert\varphi_p(A)\rvert<n$? I believe that is a different (and more difficult) question. For small $n$ there are cases with $\lvert\varphi_p(A)\rvert=2$ for all these $p$, like $A=\{0, 15, 25, 27, 30, 45, 75\}$. But I don't see a construction which works for all $n$. $\endgroup$
    – Peter Mueller
    Commented May 10, 2023 at 9:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .