FOCS Conference 2024 Conference Paper
A Dense Model Theorem for the Boolean Slice
- Gil Kalai
- Noam Lifshitz
- Dor Minzer
- Tamar Ziegler
The (low soundness) linearity testing problem for the middle slice of the Boolean cube is as follows. Let $\varepsilon > 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 [6], asks whether there must be an actual linear function that agrees with $f$ on $1/2+\epsilon^{\prime}$ fraction of the inputs, where $\varepsilon^{\prime}=\in^{\prime}(\in) > 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(\text{mod}\ 2^{k-1})$. Using our techniques we also give a more general ‘low degree test’ and a biased rank theorem for the slice.