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

Question

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?

Answer 1

Extending the idea from responses to your previous post (the case $k=2$), I think one can make $C$ as large as $\lfloor\sqrt[3]{p-1}\rfloor$ at least.

Let $C=\{c_1,\dots,c_k\}$. Without loss of generality we can assume $0\notin C$ (since we can add/subtract a linear function to $f(z)$). By a greedy algorithm, as long as $k^2\ell\le p-1$, one can choose a set $D=\{d_1,\dots,d_\ell\}\subset \Bbb F_p^\times$ such that $CD$ has size $k\ell$ and hence has no repeated products. In particular, if $k\le\sqrt[3]{p-1}$ then we can take $\ell=k$.

Now define $f(z)$ to be identically $0$ except that $f(d_j) = c_jd_j$ for each $1\le j\le k$. We have arranged for the value $0$ to be hit $k$ times (one more than needed, actually). Without the exceptions $f(d_j) = c_jd_j$, each nonzero value would have been hit $k$ times as well; we have removed one "hit" for each of the numbers $-c_id_j$, but since those are distinct in $\Bbb F_p$, every value is still hit at least $k-1$ times (not even counting the fact that those modified values also hit certain values).