Small Bias: poly nat Degree le
ProvedVariableBound.SmallBias.poly_natDegree_lealgorithmsanthropic-eth-16a5ce4complexity-theory
Proof of Lemma 13 (Family of checks), «of degree at most m − 1»: for every set V′ of clauses.
Preamble
/- Copyright (c) 2026 Anthropic, PBC. All rights reserved.
Released under Apache 2.0; SPDX-License-Identifier: Apache-2.0.
Source and original notices: https://github.com/anthropics/formal-math/blob/16a5ce41304fcdaea4e0be7c132e1c361dc26da5/eth/NOTICE -/
import Definitions.Def_AppVariablesStatement
import Mathlib.Algebra.Polynomial.Eval.Defs
import Mathlib.Algebra.Polynomial.Degree.Defs
import Mathlib.Algebra.Polynomial.Roots
import Mathlib.Algebra.Polynomial.BigOperators
import Mathlib.Algebra.BigOperators.Ring.Finset
import Mathlib.Data.Fintype.BigOperators
import Mathlib.Data.ZMod.Basic
import Definitions.Def_VariableBound_Family_SmallBias
set_option autoImplicit false
section
section
open VariableBound VariableBound.SmallBias
open Finset AppVariables
variable {F : Type} [Field F] {m : ℕ}Formal statement
theorem VariableBound.SmallBias.poly_natDegree_le (V' : Finset (Fin m)) : (poly F V').natDegree ≤ m - 1 := by sorry
Source