Majority is least stable conjecture

DefinitionLinear threshold function#✓fully proved

A function \(f : \{-1, 1\}^n \to \mathbb{R}\) is a linear threshold function if there are reals \(w_0, w_1, \dots, w_n\) such that for every \(x \in \{-1, 1\}^n\) we have \(f(x) = \operatorname{sgn}(w_0 + w_1 x_1 + \dots + w_n x_n)\), where \(x_i \in \{-1, 1\}\) is the \(i\)-th coordinate of \(x\), \(\operatorname{sgn} z = 1\) for \(z \ge 0\) and \(\operatorname{sgn} z = -1\) for \(z < 0\).

def IsLinearThresholdFunction {n : ℕ} (f : BoolCube n → ℝ) : Prop :=
  ∃ (w₀ : ℝ) (w : Fin n → ℝ), ∀ x : BoolCube n,
    f x = if 0 ≤ w₀ + ∑ i, w i * cubeVal (x i) then 1 else -1

Uses 2 · Used by 1

Statement usesBoolean cube · Sign of a Boolean coordinate

Used byMajority Is Least Stable conjecture in \(n\) variables

DefinitionMajority function#✓fully proved

For \(n \in \mathbb{N}\), the majority function \(\mathrm{Maj}_n : \{-1, 1\}^n \to \mathbb{R}\) is given by \(\mathrm{Maj}_n(x) = 1\) if \(x_1 + \dots + x_n \ge 0\) and \(\mathrm{Maj}_n(x) = -1\) otherwise, where \(x_i \in \{-1, 1\}\) is the \(i\)-th coordinate of \(x\).

noncomputable def majority (n : ℕ) (x : BoolCube n) : ℝ :=
  if 0 ≤ ∑ i, cubeVal (x i) then 1 else -1

Uses 2 · Used by 1

Statement usesBoolean cube · Sign of a Boolean coordinate

Used byMajority Is Least Stable conjecture in \(n\) variables

DefinitionNoise stability#✓fully proved

For a real number \(\rho\) and a function \(f : \{-1, 1\}^n \to \mathbb{R}\), the noise stability of \(f\) at \(\rho\) is \(\mathrm{Stab}_\rho[f] = \sum_{S \subseteq \{1, \dots, n\}} \rho^{|S|} \hat f(S)^2\), where \(\hat f(S)\) is the Fourier coefficient of \(f\) at \(S\).

For \(-1 \le \rho \le 1\) this is the Fourier expansion of \(\mathbb{E}[f(x) f(y)]\) for uniform \(x\) and a \(\rho\)-correlated copy \(y\) of \(x\).

noncomputable def noiseStability {n : ℕ} (ρ : ℝ) (f : BoolCube n → ℝ) : ℝ :=
  ∑ S : Finset (Fin n), ρ ^ S.card * boolFourierCoeff n f S ^ 2

Uses 2 · Used by 1

Statement usesBoolean cube · Fourier coefficient on the Boolean cube

Used byMajority Is Least Stable conjecture in \(n\) variables

DefinitionMajority Is Least Stable conjecture in \(n\) variables#✓fully proved

For \(n \in \mathbb{N}\), this is the statement that every linear threshold function \(f : \{-1, 1\}^n \to \mathbb{R}\) satisfies \(\mathrm{Stab}_\rho[f] \ge \mathrm{Stab}_\rho[\mathrm{Maj}_n]\) for every real \(\rho\) with \(0 \le \rho \le 1\), where \(\mathrm{Stab}_\rho\) is the noise stability and \(\mathrm{Maj}_n\) is the majority function.

def MajorityIsLeastStableFor (n : ℕ) : Prop :=
  ∀ f : BoolCube n → ℝ, IsLinearThresholdFunction f → ∀ ρ : ℝ, 0 ≤ ρ → ρ ≤ 1 →
    noiseStability ρ (majority n) ≤ noiseStability ρ f

Uses 4 · Used by 1

Statement usesBoolean cube · Linear threshold function · Majority function · Noise stability

Used byMajority Is Least Stable in some odd dimension at least five

DefinitionMajority Is Least Stable in some odd dimension at least five#✓fully proved

There is an odd natural number \(n \ge 5\) for which the Majority Is Least Stable conjecture in \(n\) variables holds: every linear threshold function \(f : \{-1, 1\}^n \to \mathbb{R}\) satisfies \(\mathrm{Stab}_\rho[f] \ge \mathrm{Stab}_\rho[\mathrm{Maj}_n]\) for every real \(\rho\) with \(0 \le \rho \le 1\), where \(\mathrm{Stab}_\rho\) is the noise stability and \(\mathrm{Maj}_n\) is the majority function.

def majorityIsLeastStableForSomeOddAtLeastFive : Prop :=
  ∃ n : ℕ, Odd n ∧ 5 ≤ n ∧ MajorityIsLeastStableFor n

Uses 1 · Used by 1

Statement usesMajority Is Least Stable conjecture in \(n\) variables

Used byMajority Is Least Stable fails in every odd dimension at least five

TheoremMajority Is Least Stable fails in every odd dimension at least five#●ready to prove

For every odd natural number \(n \ge 5\), the Majority Is Least Stable conjecture in \(n\) variables fails: there are a linear threshold function \(f : \{-1, 1\}^n \to \mathbb{R}\) and a real number \(\rho\) with \(0 \le \rho \le 1\) such that \(\mathrm{Stab}_\rho[f] < \mathrm{Stab}_\rho[\mathrm{Maj}_n]\), where \(\mathrm{Stab}_\rho\) is the noise stability and \(\mathrm{Maj}_n\) is the majority function.

Biswas and Sarkar exhibit, for every odd \(n \ge 5\), a linear threshold function \(g_n\) with \(\mathrm{Stab}_\rho[g_n] < \mathrm{Stab}_\rho[\mathrm{Maj}_n]\) for all small \(\rho > 0\). The conjecture holds for \(n = 1\) and \(n = 3\).

public theorem_wanted majorityIsLeastStableForSomeOddAtLeastFive_refuted :
    ¬ majorityIsLeastStableForSomeOddAtLeastFive

Sources

• R. O'Donnell, Open problems in analysis of Boolean functions, arXiv:1204.6447 (2012), 'Majority Is Least Stable Conjecture' (Benjamini, Kalai, Schramm); resolution: A. Biswas, P. Sarkar, On the "majority is least stable" conjecture, Inform. Process. Lett. 179 (2023), 106295, arXiv:2202.09024, Theorem 2 of arXiv:2202.09024v2: the conjecture is true for n = 1 and n = 3 and false for every odd n ≥ 5; for odd n ≥ 5 the linear threshold function g_n(x) = sgn(2(x₁ + ⋯ + x_{n-3}) + x_{n-2} + x_{n-1} + x_n) has W⁰[g_n] = 0 and W¹[g_n] < W¹[Maj_n] (Lemmas 3 and 4), hence Stab_ρ[g_n] < Stab_ρ[Maj_n] for all small ρ > 0 (Lemma 1); the case n = 5 is V. Jain, arXiv:1703.07657, https://doi.org/10.1016/j.ipl.2022.106295.

Uses 1

Statement usesMajority Is Least Stable in some odd dimension at least five

5 fully proved1 ready to prove

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.