Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-149 | 18th August 2026 06:12

A Counting Lemma for Somewhat Restricted 3-APs

RSS-Feed

Abstract:

For a prime $p\geq 3$, a somewhat restricted $3$-AP in $\mathbb{F}_p^n$ is a triplet $(x,x+a,x+2a)$, where $x\in\mathbb{F}_p^n$ and $a\in \{0,1,2\}^n$. We prove a counting lemma for somewhat restricted $3$-APs in dense sets in $\mathbb{F}_p^n$. More precisely, we prove that for all $\alpha>0$, there exists $\beta>0$, such that for sufficiently large $n$, if a set $A\subseteq \mathbb{F}_p^n$ has density at least $\alpha$, then it contains at least $\beta$ fraction of all somewhat restricted $3$-APs.

Our proof builds on recently developed machinery from [Bhangale, Khot, Minzer, 2026]. Our main new ingredient is an arithmetic regularity lemma for patterns such as somewhat restricted 3-APs. This result is in the spirit of arithmetic regularity lemmas from the theory of Gowers uniformity norms [Green, Tao, 2010] and may be of independent interest.



ISSN 1433-8092 | Imprint