Harmonicity and invariance on slices of the Boolean cube

Yuval Filmus, Elchanan MosselProbability 2016

In the world of theoretical computer science and combinatorics, we often study functions defined on the Boolean cube—the set of all strings of 0s and 1s of length $n$. But sometimes, nature (or a specific math problem) restricts us to a slice of that cube: the subset of strings where the number of 1s is exactly fixed (for example, exactly $n/2$).

A new paper by Yuval Filmus and Elchanan Mossel, "Harmonicity and Invariance on Slices of the Boolean Cube," provides a powerful "invariance principle" that bridges these two worlds.

TL;DR

The paper proves that for "nice" functions (specifically low-degree harmonic polynomials), the statistical distribution of the function is nearly identical whether you measure it over the entire Boolean cube or just a single slice. This allows researchers to port tools from the well-understood Boolean cube to the more constrained environment of the slice without needing the "low influence" assumptions required by previous work.

What Problem Does This Paper Address?

The Boolean cube $\{0,1\}^n$ is the playground of Boolean analysis, but many combinatorial problems (like the Erdős-Ko-Rado theorem) naturally live on the slice $\binom{[n]}{k}$. The slice is harder to analyze because the coordinates are not independent—if you know there are $k$ ones in total, knowing one bit is a '1' slightly decreases the probability that another bit is a '1'.

Previous "invariance principles" attempted to show that functions behave similarly on the cube and the slice, but they usually required a "low influence" condition—meaning no single input bit could significantly change the function's output. This paper asks: Can we drop the low-influence requirement? The authors show that if we represent functions using harmonic polynomials, the answer is a resounding yes, provided the function's degree isn't too high.

Methods

The authors employ a mix of algebraic and probabilistic techniques:

  1. Harmonic Representation: They utilize a unique way to represent any function on the slice as a "harmonic multilinear polynomial." A polynomial is harmonic if it is annihilated by the operator $\sum \partial / \partial x_i$. This representation is "canonical" because it’s the natural way to "lift" a function from the slice back to the full cube.
  2. Coupling and Martingales: To compare different slices, the authors construct a "random increasing path" that moves from a slice with few 1s to a slice with many 1s.
  3. Novel Decomposition: The core technical innovation is representing the difference in function values between two slices as a sum of martingales and reverse martingales. While this "two-sided" approach has been used for stationary Markov chains, the authors successfully apply it here to a non-stationary, non-reversible setup. This allows them to use $L_2$ concentration bounds to show that the function value doesn't change much as you move between nearby slices.
  4. Representation Theory: They use the symmetry of the symmetric group $S_n$ to decompose the space of functions into irreducible components, which simplifies the analysis of how these functions behave under different probability measures.

Datasets

This is a theoretical mathematics and theoretical computer science paper; therefore, no empirical datasets were used. The results are proven mathematically for all possible functions meeting the specified criteria.

Key Insights and Ideas

  • The $\sqrt{n}$ Barrier: The invariance holds as long as the degree of the polynomial is $o(\sqrt{n})$. This makes sense physically: the "width" of the distribution of the number of 1s in a cube is roughly $\sqrt{n}$. If a function has a higher degree, it becomes sensitive enough to "notice" the global constraint of the slice.
  • Harmonicity is the "Correct" Language: The paper argues that harmonic polynomials are the mathematically "right" way to talk about functions on the slice. They show that these polynomials are the unique extensions that preserve the "degree" of the function in a way that respects the symmetry of the coordinates.
  • Independence from Influence: Unlike the landmark Mossel-O'Donnell-Oleszkiewicz (MOO) invariance principle, this result does not care about "influences." A function could depend entirely on just a few coordinates, and the invariance would still hold as long as it is harmonic.

Key Results

  • Theorem 1.2 (Main Result): For any harmonic multilinear polynomial $f$ with degree $o(\sqrt{n})$ and variance 1, the distribution of $f$ on the slice is close to its distribution on the cube in terms of Lévy distance (a measure of how close two cumulative distribution functions are).
  • Total Variation Bounds: The authors prove that for any function depending on $o(n)$ coordinates, the total variation distance between the cube measure and the slice measure is $o(1)$.
  • Circuit Lower Bounds: They provide a new, simpler proof that symmetric Boolean functions (like Majority) cannot be well-approximated by functions with low total influence, which has implications for circuit complexity.

Limitations and Future Work

  • Degree Constraints: The results break down once the degree reaches $\Omega(\sqrt{n})$. The authors explicitly demonstrate a counterexample in Section 4.2 showing that high-degree functions can behave very differently on the slice vs. the cube.
  • Lévy vs. CDF Distance: While the authors prove closeness in Lévy distance, they leave it as an open question (Question 4.8) whether the result holds for the stricter CDF distance (the maximum difference between the two cumulative distribution functions).
  • Extension to Multislices: The current work focuses on the Boolean case (0/1). Extending these harmonic tools to "multislices" (where coordinates can take more than two values, like $\{1, 2, 3\}$) is suggested as a promising future direction.

Summary updated

BibTeX
@inproceedings{filmus2016harmonicity,
  author = {Yuval Filmus and Elchanan Mossel},
  title = {{Harmonicity and invariance on slices of the Boolean cube}},
  booktitle = {Probability},
  year = {2016},
}
Figure