Low-complexity approximations for sets defined by generalizations of affine conditions

Abstract

Let $p$ be a prime, let $S$ be a non-empty subset of ${\mathbb{F}}_p$ and let $0<\epsilon \le 1$. We show that there exists a constant $C=C(p,\epsilon )$ such that for every positive integer $k$, whenever ${\varphi }_1,\dots ,{\varphi }_k:{\mathbb{F}}_p^n\to {\mathbb{F}}_p$ are linear forms and $E_1,\dots ,E_k$ are subsets of ${\mathbb{F}}_p$, there exist linear forms ${\psi }_1,\dots ,{\psi }_C:{\mathbb{F}}_p^n\to {\mathbb{F}}_p$ and subsets $F_1,\dots ,F_C$ of ${\mathbb{F}}_p$ such that the set $U=\{x\in S^n:{\psi }_1(x)\in F_1,\dots ,{\psi }_C(x)\in F_C\}$ is contained inside the set $V=\{x\in S^n:{\varphi }_1(x)\in E_1,\dots ,{\varphi }_k(x)\in E_k\}$, and the difference $V\setminus U$ has density at most $\epsilon$ inside $S^n$. We then generalize this result to one where ${\varphi }_1,\dots ,{\varphi }_k$ are replaced by homomorphisms $G^n\to H$ for some pair of finite Abelian groups $G$ and $H$, and to another where they are replaced by polynomial maps ${\mathbb{F}}_p^n\to {\mathbb{F}}_p$ of small degree.

26 pages