Asymptotically sharp bounds for affine subspace statistics in $\mathbb F_2^n$

Abstract

Given a subset $A \subseteq \mathbb F_2^n$, we can consider the distribution of the intersection size of $A$ with a uniformly random $d$-flat $F$. Motivated by the edge statistics problem and the hypercube statistics problem, the affine subspace statistics problem concerns the maximum of $\mathbb{P}[|F\cap A|=s]$ among $A \subseteq \mathbb F_2^n$ for any fixed $s\in\{1,\dots,2^d\}$ over a uniformly random $d$-flat $F$. We use $\lambda^*(d,s)$ to denote the limit of the maximum when $n$ goes to infinity. In this note, we prove tight bounds for $\lambda^*(d,s)$ in two different regimes. For $s=j2^k$ where $j$ is a positive odd integer, the best known lower bound construction achieving $\lambda^*(d,s)\ge 1-2^{-k}$ is due to taking $A$ as the union of $j$ parallel $(n-d+k)$-flats in $\mathbb F_2^n$. Our main result is a matching upper bound with an additive error term of $O(2^{-3k/2})$. We also study the case $s=1$, where we determine $\lambda^*(d,1)$ exactly. We show that the random construction where each point is included with probability $2^{-d}$ is optimal.