3
$\begingroup$

Let $p$ be a (large) prime.

Does there exist a function $f\colon\mathbb F_p^\times\to\mathbb F_p$ such that the three sets $$ \{f(z)-z\colon z\in\mathbb F_p^\times\},\ \{f(z)\colon z\in\mathbb F_p^\times\},\ \text{and}\ \{f(z)+z\colon z\in\mathbb F_p^\times \} $$ form a double-cover of $\mathbb F_p$ (in the sense that any element of $\mathbb F_p$ lies in at least two of them)?

More generally,

Do there exist a function $f\colon\mathbb F_p^\times\to\mathbb F_p$ and elements $c_1,c_2,c_3\in\mathbb F_p$ such that the images of the functions $z\mapsto f(z)-c_iz\ (z\in\mathbb F_p^\times)$ double-cover $\mathbb F_p$?

I hardly believe this is a tough problem; rather, I suspect I am overlooking a simple argument.

$\endgroup$
  • 3
    $\begingroup$ If we take $f(z)=3z$, it is a triple-cover of $\mathbb{F}_p^\times$. Now change two values so that 0 becomes double-covered, but no element becomes less-than-three-times covered. This is possible for large $p$, is not it? $\endgroup$ – Fedor Petrov Nov 20 '17 at 13:28
  • $\begingroup$ @FedorPetrov: something of this sort may well work, but it is not quite clear to me exactly what will fail to be triple (and double) covered when two values get changed. May I suggest that you post your comment as an answer adding some details (what values and how exactly are to be changed)? $\endgroup$ – Seva Nov 20 '17 at 13:48
  • $\begingroup$ Fedor Petrov's suggestion works by setting $f(z) = 3z$ whenever $z \neq z_0,z_1$ and $f(z) = 0$ otherwise, as long as the values $2z_0,3z_0,4z_0, 2z_1,3z_1,4z_1$ are distinct. This is possible for $p > 5$. $\endgroup$ – js21 Nov 20 '17 at 13:57
  • $\begingroup$ @js21 in your example we cover 0 twice by the second set, while Seva asks to cover it by two different sets $\endgroup$ – Fedor Petrov Nov 20 '17 at 14:14
  • $\begingroup$ @Fedor Petrov: Oh, right. I just saw your solution. $\endgroup$ – js21 Nov 20 '17 at 15:52
6
$\begingroup$

Start with $f(z)=3z$, then all non-zero elements are covered three times. Change $f(a)$ to 0 and $f(b)$ to $b$. Now 0 is covered two times and $2a,3a,4a$, $2b,3b,4b$ are covered two times also (assume that all these 6 numbers are different, this is possible for large $p$). Some other multiplicities could increase (and they did), but this is ok for us.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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