A counterexample to a strong variant of the Polynomial Freiman-Ruzsa conjecture

Abstract

Let $p$ be a prime. One formulation of the Polynomial Freiman-Ruzsa conjecture over ${\mathbb{F}}_p$ can be stated as follows. If $\varphi :{\mathbb{F}}_p^n\to {\mathbb{F}}_p^N$ is a function such that $\varphi (x+y)-\varphi (x)-\varphi (y)$ takes values in some set $S$, then there is a linear map $\tilde{\varphi }:{\mathbb{F}}_p^n\to {\mathbb{F}}_p^N$ with the property that $\varphi -\tilde{\varphi }$ takes at most $|S{|}^{O(1)}$ values. A strong variant of this conjecture states that, in fact, there is a linear map $\tilde{\varphi }$ such that $\varphi -\tilde{\varphi }$ takes values in $tS$ for some constant $t$. In this note, we discuss a counterexample to this conjecture.

3 pages

Cited by in corpus (1)

• Sumsets and entropy revisited