Polynomial enumerations and the presupposition-resolution sets d, d_l
DefinitionAutoformalisationSCI_PolyThis file formalizes the polynomial constructions at the heart of the paper's lower bounds.
cantorPair is the integer-coefficient pairing fixed in the paper (a computable injection ). ComputablePolyEnum m packages a computable enumeration of all integer-coefficient polynomials in variables: the enumerated polynomials , surjectivity, a computable coefficient function (monomials as exponent vectors ), and a computable bound on total degree. These data are equivalent to computability of the enumeration under a canonical numbering by finite coefficient lists.
B k E e n is the predicate of Eq. (A.3): for all ; dSet k E is . leastWitness is the partial number of Example 4.1 (the least such , or undefined). Bgen l k hl E e n is of Eq. (A.4), built from the alternating quantifier pattern qtype/QuantVec; dSetL is . combinedProblem k E is the decision problem over all levels (Appendix A.2.1): on input it decides whether is nonempty.
Formalization Note. Polynomials are MvPolynomial (Fin m) ℤ, evaluated at natural points via the coercion to . In Bgen, index is the parameter , indices are , and the last indices are ; the z-quantifiers alternate starting with , and the final -block is all (even , matrix ) or all (odd , matrix ).
import Mathlib
open Encodable
open scoped Classical
namespace AutoformalisationSCI
def cantorPair (x y : ℕ) : ℕ := (x + y) * (x + y + 1) + 2 * y
structure ComputablePolyEnum (m : ℕ) where
p : ℕ → MvPolynomial (Fin m) ℤ
surj : Function.Surjective p
coeff_comp : Computable₂ (fun (e : ℕ) (s : Fin m → ℕ) =>
MvPolynomial.coeff (Finsupp.equivFunOnFinite.symm s) (p e))
degBound : ℕ → ℕ
degBound_comp : Computable degBound
degBound_spec : ∀ e, (p e).totalDegree ≤ degBound e
def B (k : ℕ) (E : ComputablePolyEnum (k + 1)) (e n : ℕ) : Prop :=
∀ x : Fin k → ℕ,
MvPolynomial.eval (fun i : Fin (k + 1) =>
if h : i.val = 0 then (n : ℤ) else (x ⟨i.val - 1, by have := i.isLt; omega⟩ : ℤ)) (E.p e) ≠ 0
def dSet (k : ℕ) (E : ComputablePolyEnum (k + 1)) : Set ℕ := {e | ∃ n, B k E e n}
noncomputable def leastWitness (k : ℕ) (E : ComputablePolyEnum (k + 1)) (e : ℕ) : Option ℕ :=
if h : ∃ n, B k E e n then some (Nat.find h) else none
def qtype (l k : ℕ) (i : Fin (l - 2 + k)) : Bool :=
if (i : ℕ) < l - 2 then decide ((i : ℕ) % 2 = 0) else decide (l % 2 = 0)
def QuantVec : (r : ℕ) → (Fin r → Bool) → ((Fin r → ℕ) → Prop) → Prop
| 0, _, P => P Fin.elim0
| r + 1, q, P =>
if q 0 = true then
∀ z : ℕ, QuantVec r (fun i => q i.succ) (fun zs => P (Fin.cons z zs))
else
∃ z : ℕ, QuantVec r (fun i => q i.succ) (fun zs => P (Fin.cons z zs))
def Bgen (l k : ℕ) (hl : 2 ≤ l) (E : ComputablePolyEnum (l - 1 + k)) (e n : ℕ) : Prop :=
QuantVec (l - 2 + k) (qtype l k) (fun v : Fin (l - 2 + k) → ℕ =>
let pt : Fin (l - 1 + k) → ℕ :=
fun i =>
let j : Fin (l - 2 + k + 1) := Fin.cast (show l - 1 + k = l - 2 + k + 1 by omega) i
if h : j.val = 0 then n else v ⟨j.val - 1, by have := j.isLt; omega⟩
if l % 2 = 0 then MvPolynomial.eval (fun i => (pt i : ℤ)) (E.p e) ≠ 0
else MvPolynomial.eval (fun i => (pt i : ℤ)) (E.p e) = 0)
def dSetL (l k : ℕ) (hl : 2 ≤ l) (E : ComputablePolyEnum (l - 1 + k)) : Set ℕ :=
{e | ∃ n, Bgen l k hl E e n}
noncomputable def combinedProblem (k : ℕ) (E : ∀ l : ℕ, ComputablePolyEnum (l - 1 + k)) : ℕ → Bool :=
fun p => if (∃ n, Bgen (p.unpair.1 + 2) k (by omega) (E (p.unpair.1 + 2)) p.unpair.2 n) then true else false
end AutoformalisationSCIRead-back
What the Lean code literally says, in plain math · claude-opus-4-8
cantorPair x y = (x+y)(x+y+1)+2y. ComputablePolyEnum m is a structure with fields: p : ℕ → MvPolynomial (Fin m) ℤ; surj : Function.Surjective p; coeff_comp : Computable₂ (fun e s => MvPolynomial.coeff (Finsupp.equivFunOnFinite.symm s) (p e)); degBound : ℕ → ℕ; degBound_comp : Computable degBound; degBound_spec : ∀ e, (p e).totalDegree ≤ degBound e. B k E e n asserts that for every x : Fin k → ℕ, the evaluation of E.p e at the point Fin.cons n x (coerced to ℤ) is nonzero. dSet k E = {e | ∃ n, B k E e n}. leastWitness k E e is some (Nat.find h) if ∃ n, B k E e n (with proof h) else none. qtype l k i is decide (i % 2 = 0) when i < l-2, else decide (l % 2 = 0). QuantVec applies, coordinate by coordinate, a universal quantifier where the Bool is true and an existential where false. Bgen l k hl E e n applies QuantVec (l-2+k) (qtype l k) to the matrix that evaluates E.p e at the point with head n and tail v, asserting ≠ 0 when l % 2 = 0 and = 0 otherwise; it requires hl : 2 ≤ l. dSetL l k hl E = {e | ∃ n, Bgen l k hl E e n}. combinedProblem k E p is true iff ∃ n, Bgen (p.unpair.1+2) k (by omega) (E (p.unpair.1+2)) p.unpair.2 n, noncomputable. The case l=2 is included (hl discharged by omega).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.