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 $\hat{I}{»}^{\ast }(d,s)$ to denote the limit of the maximum when $n$ goes to infinity. In this note, we prove tight bounds for $\hat{I}{»}^{\ast }(d,s)$ in two different regimes. For $s=j{2}^k$ where $j$ is a positive odd integer, the best known lower bound construction achieving $\hat{I}{»}^{\ast }(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 $\hat{I}{»}^{\ast }(d,1)$ exactly. We show that the random construction where each point is included with probability $2^{-d}$ is optimal.

7 pages