Variable Bound: residues
ProvedVariableBound.residuesalgorithmsanthropic-eth-16a5ce4complexity-theory
Step 1, «The residues determine the numbers»: if there are at most 2^n assignments, then 0 ≤ X(𝓛) ≤ 2^n·C(m, n̄ + 1) ≤ 2^(β − 1), where β = n + ⌈log C(m, n̄ + 1)⌉ + 1, and 0 ≤ F(𝓛) ≤ 2^n if X(𝓛) = 0.
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.residues : AppVariables.ResiduesStmt := by sorry
Source