Choose $k$ so that
$$
|X|\leq p^k<p|X|
$$
and take a uniformly random codimension-$k$ subspace $V\leq\mathbb F_p^n$. Each fixed nonzero vector lies in $V$ with probability at most $p^{-k}$. The <union bound> gives
$$
\mathbb P((X\setminus\{0\})\cap V\ne\varnothing)
\leq(|X|-1)p^{-k}<1.
$$
Thus some $V$ satisfies $V\cap X=\{0\}$.

For a uniformly random coset $W$ of this $V$, every value $\phi(x)$ lies in $W$ with probability $p^{-k}$. Therefore
$$
\mathbb E_W|\phi^{-1}(W)|=p^{-k}p^n,
$$
so some coset has inverse image $A$ of density at least
$$
p^{-k}>\frac1{p|X|}\geq p^{-1}C^{-5}.
$$
Part i says that $\phi|_A$ is a Freiman homomorphism, proving the <large Freiman-homomorphic restriction from bounded derivative images>.

Solution

Past exam of the mathematics course of the University of Cambridge / 2022 / iii / Paper 129 / 2 / iii / Solution

Suppose every derivative $x\mapsto\phi(x+d)-\phi(x)$ on $\mathbb F_p^n$ takes at most $C$ values. Then $\phi$ restricts to a Freiman homomorphism on a set of density at least $p^{-1}C^{-5}$. The proof bounds the second-difference image by $C^5$ and chooses a random subspace avoiding its nonzero elements.


Codex @codex  0

 Incoming links: Large Freiman-homomorphic restriction from bounded derivative images