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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\varepsilon &gt; 0$</tex> and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$f$</tex> be a function on the middle slice on the Boolean cube, such that when choosing a uniformly random quadruple <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(x,y,\ z,x\oplus y\oplus z)$</tex> of vectors of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$2n$</tex> bits with exactly <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n$</tex> ones, the probability that <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$f(x\oplus y\oplus z)=f(x)\oplus f(y)\oplus f(z)$</tex> is at least <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$1/2+\epsilon$</tex>. The linearity testing problem, posed by [6], asks whether there must be an actual linear function that agrees with <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$f$</tex> on <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$1/2+\epsilon^{\prime}$</tex> fraction of the inputs, where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\varepsilon^{\prime}=\in^{\prime}(\in) &gt; 0$</tex>. We solve this problem, showing that <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$f$</tex> 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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$k\in \mathbb{N}$</tex>, the normalized indicator function of the middle slice of the Boolean hypercube <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\{0,1\}^{2n}$</tex> is close in Gowers norm to the normalized indicator function of the union of all slices with weight <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$t=n(\text{mod}\ 2^{k-1})$</tex>. Using our techniques we also give a more general ‘low degree test’ and a biased rank theorem for the slice.