Affine Subspace Statistics in the Hypercube

Abstract

We study the intersection statistics of affine subspaces in the hypercube ${\mathbb{F}}_2^n$, motivated by recent work of Alon, Axenovich, and Goldwasser on the intersection statistics of axis-aligned subcubes of an $n$-dimensional cube. Let $d\ge 1$ and $0\le s\le 2^d$ be nonnegative integers. For a subset $A\subseteq {\mathbb{F}}_2^n$ where $n\ge d$, define $\hat{I}{»}^{\ast }(n,d,s,A)$ to be the fraction of affine $d$-flats in ${\mathbb{F}}_2^n$ that intersect $A$ at exactly $s$ points. Let $\hat{I}{»}^{\ast }(n,d,s)={\max }_{A\subseteq {\mathbb{F}}_2^n}\hat{I}{»}^{\ast }(n,d,s,A)$ and let $\hat{I}{»}^{\ast }(d,s)={\lim }_{n\to \infty }\hat{I}{»}^{\ast }(n,d,s)$. We show that when $s=j\cdot 2^k$ with $j$ odd and $k\ge 1$, we have $\hat{I}{»}^{\ast }(d,s)\to 1-\hat{I}˜(2^{-k})$ as $d\to \infty$. This implies that $\hat{I}{»}^{\ast }(d,s)$ is controlled up to constant factors by the $2$-adic valuation of $s$ when $s$ is even. When $s$ is odd, we show that $\hat{I}{»}^{\ast }(d,s)\le \frac{1}{2}$ in contrast to the behavior of axis-aligned subcube statistics. We also present several upper and lower bounds for certain specific values of $s$.

14 pages