AFTD Auto-Formalizing Theoretical Domains

predictedTorusError

deforiginal

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) : ℝ))
See it in the graphDiscuss this resultChallenge it