predictedTorusError
For a natural number n and Boolean function f : (Fin n → Bool) → Bool on n variables, predictedTorusError n f is the real error: 1 / (2 * Nat.choose n (n / 2)) if boolAnfCoefficient f Finset.univ is true; 0 if boolAnfCoefficient f Finset.univ is false and boolNextToTopAnfCount f = 0; and 1 / (2^(n - h) * Nat.choose h (h / 2)) where h = min (boolNextToTopAnfCount f - 1) (n - boolNextToTopAnfCount f) if boolAnfCoefficient f Finset.univ is false and boolNextToTopAnfCount f > 0.
Statement
noncomputable def predictedTorusError (n : ℕ) (f : (Fin n → Bool) → Bool) : ℝ
- Related work
- arXiv:2610.19174, Majority and Torus Polynomials: Bounded-Lift Lower Bounds and Explicit Constructions
- Verified
- 30 Oct 2026
- Axioms
- none listed
- Built on 2
- boolAnfCoefficientFor a Boolean function f : (Fin n → Bool) → Bool on n variables and a subset S : Finset (Fin n), the algebraic normal form coefficient…
- boolNextToTopAnfCountFor a Boolean function f : (Fin n → Bool) → Bool on n variables, boolNextToTopAnfCount f is the number of indices i : Fin n such that the…
- Used by 1
- op_729_case_n_twoFor every Boolean function f : (Fin 2 → Bool) → Bool on 2 variables, optimalTorusError f 0 = predictedTorusError 2 f and…
Read back from the Lean
predictedTorusError n f is a definition that takes a natural number n and a Boolean function f : (Fin n → Bool) → Bool, and returns a real number defined by cases:
1. If the top-degree ANF coefficient of f is 1 (that is, if the number of inputs x : Fin n → Bool for which f x = true is odd):
it returns
$$\frac{1}{2 \cdot \binom{n}{\lfloor n / 2 \rfloor}}$$
2. Otherwise:
let $k$ be the count of indices $i \in \text{Fin } n$ such that the ANF coefficient of Finset.univ \ {i} is 1 (that is, the number of inputs x satisfying f x = true and x i = false is odd).
- If $k = 0$, it returns $0$.
- If $k \neq 0$, let $h = \min(k - 1, n - k)$ (using natural subtraction). It returns
$$\frac{1}{2^{n - h} \cdot \binom{h}{\lfloor h / 2 \rfloor}}$$
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- Predicted optimal degree-(n-2) torus approximation error from top two ANF layers. -/ noncomputable def predictedTorusError (n : ℕ) (f : (Fin n → Bool) → Bool) : ℝ := if boolAnfCoefficient f Finset.univ then 1 / (2 * (n.choose (n / 2) : ℝ)) else let k := boolNextToTopAnfCount f if k = 0 then 0 else let h := min (k - 1) (n - k) 1 / ((2 : ℝ) ^ (n - h) * (h.choose (h / 2) : ℝ))