A Dense Model Theorem for the Boolean Slice

Abstract

The (low soundness) linearity testing problem for the middle slice of the Boolean cube is as follows. Let $\epsilon >0$ and $f$ be a function on the middle slice on the Boolean cube, such that when choosing a uniformly random quadruple $(x,y,z,x\oplus y\oplus z)$ of vectors of $2n$ bits with exactly $n$ ones, the probability that $f(x\oplus y\oplus z)=f(x)\oplus f(y)\oplus f(z)$ is at least $1/2+\epsilon$. The linearity testing problem, posed by David, Dinur, Goldenberg, Kindler and Shinkar, asks whether there must be an actual linear function that agrees with $f$ on $1/2+{\epsilon }^{\prime }$ fraction of the inputs, where ${\epsilon }^{\prime }={\epsilon }^{\prime }(\epsilon )>0$. We solve this problem, showing that $f$ must indeed be correlated with a linear function. To do so, we prove a dense model theorem for the middle slice of the Boolean hypercube for Gowers uniformity norms. Specifically, we show that for every $k\in \mathbb{N}$, the normalized indicator function of the middle slice of the Boolean hypercube $\{0,1{\}}^{2n}$ is close in Gowers norm to the normalized indicator function of the union of all slices with weight $t=n(\mathrm{mod}{2}^{k-1})$. Using our techniques we also give a more general `low degree test' and a biased rank theorem for the slice.