Skip to main content
added 201 characters in body
Source Link
Seva
  • 23k
  • 2
  • 59
  • 141

Let $p$ be a (large) prime.

How large can a set $C\subset\mathbb F_p$ be given that there is a function $f\colon\mathbb F_p^\times\to\mathbb F_p$ such that for every element $g\in \mathbb F_p$, there is at most one element $c\in C$ with the property that $$ g \notin \{f(z)-cz\colon z\in\mathbb F_p^\times\}\,? $$

In plain English: I want to find a set $C\subset\mathbb F_p$ and a function $f\colon\mathbb F_p^\times\to\mathbb F_p$ such that every element of $\mathbb F_p$ is contained in the images of all $|C|$ functions $z\mapsto f(z)-cz$ with at most one exception; how large can I make $C$?


Greg Martin's answer below along with Will Sawin's comment show that $|C|\approx\sqrt p$ is possible. Can this be further improved? Is $|C|\ge cp$ with an absolute constant $c>0$ possible?

Let $p$ be a (large) prime.

How large can a set $C\subset\mathbb F_p$ be given that there is a function $f\colon\mathbb F_p^\times\to\mathbb F_p$ such that for every element $g\in \mathbb F_p$, there is at most one element $c\in C$ with the property that $$ g \notin \{f(z)-cz\colon z\in\mathbb F_p^\times\}\,? $$

In plain English: I want to find a set $C\subset\mathbb F_p$ and a function $f\colon\mathbb F_p^\times\to\mathbb F_p$ such that every element of $\mathbb F_p$ is contained in the images of all $|C|$ functions $z\mapsto f(z)-cz$ with at most one exception; how large can I make $C$?

Let $p$ be a (large) prime.

How large can a set $C\subset\mathbb F_p$ be given that there is a function $f\colon\mathbb F_p^\times\to\mathbb F_p$ such that for every element $g\in \mathbb F_p$, there is at most one element $c\in C$ with the property that $$ g \notin \{f(z)-cz\colon z\in\mathbb F_p^\times\}\,? $$

In plain English: I want to find a set $C\subset\mathbb F_p$ and a function $f\colon\mathbb F_p^\times\to\mathbb F_p$ such that every element of $\mathbb F_p$ is contained in the images of all $|C|$ functions $z\mapsto f(z)-cz$ with at most one exception; how large can I make $C$?


Greg Martin's answer below along with Will Sawin's comment show that $|C|\approx\sqrt p$ is possible. Can this be further improved? Is $|C|\ge cp$ with an absolute constant $c>0$ possible?

Source Link
Seva
  • 23k
  • 2
  • 59
  • 141

$k$-covering $\mathbb F_p$ with $k+1$ sets

Let $p$ be a (large) prime.

How large can a set $C\subset\mathbb F_p$ be given that there is a function $f\colon\mathbb F_p^\times\to\mathbb F_p$ such that for every element $g\in \mathbb F_p$, there is at most one element $c\in C$ with the property that $$ g \notin \{f(z)-cz\colon z\in\mathbb F_p^\times\}\,? $$

In plain English: I want to find a set $C\subset\mathbb F_p$ and a function $f\colon\mathbb F_p^\times\to\mathbb F_p$ such that every element of $\mathbb F_p$ is contained in the images of all $|C|$ functions $z\mapsto f(z)-cz$ with at most one exception; how large can I make $C$?