Variable Bound: xf
ProvedVariableBound.xfalgorithmsanthropic-eth-16a5ce4complexity-theory
Display (65), for a list of r checks, β ≥ 1, M ≥ β − 1 + r and M ≥ n + r: Lemma 12 with (φ, ν) = (C(|V|, n̄ + 1), β) and with (φ, ν) = (η, n + 1), and φ(ξ) written as a sum over sets Π_0 ⊆ V(ξ).
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 Definitions.Def_ClauseBound_ParityChecks_StepOne import Definitions.Def_ClauseBound_ParityChecks_StepOne import Mathlib.Algebra.BigOperators.Fin import Mathlib.Algebra.BigOperators.ModEq import Mathlib.Algebra.Order.BigOperators.Ring.Finset import Mathlib.Data.List.GetD import Definitions.Def_VariableBound_StepParity set_option autoImplicit false section section open VariableBound open Finset ParityChecks AppVariables StepParity
Formal statement
theorem VariableBound.xf : AppVariables.XFStmt := by sorry
Source