A Dense Model Theorem for the Boolean Slice

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.

Authors

• Gil Kalai
• Noam Lifshitz
• Dor Minzer
• Tamar Ziegler

Keywords

• Computer science
• Computational modeling
• Linearity
• Hypercubes
• Vectors
• Testing
• Density Model
• Linear Function
• Test Problems
• Input Fractions
• Boolean Function
• Hamming Weight
• Subset Of Properties
• Theoretical Computer Science
• Property Testing
• Dense Model Theorems
• Analysis of Boolean functions
• Gowers' Uniformity Norms