Corollary 4.9 — Polynomial step bounds on binary lists
OpenAehligSchwichtenberg2002V2.corollary_4_9A closed term from a tuple of binary lists to a binary list normalizes on canonical inputs with disjoint token contexts. The output length is at most the sum of input lengths. The step count is bounded by a polynomial in that sum, of degree at most the larger of one and the brace nesting depth of the term.
import Definitions.Def_AehligSchwichtenberg2002V2_Bounds
namespace AehligSchwichtenberg2002V2
theorem corollary_4_9 {k : Nat} {t : Term}
(ht : HasType [] t (Ty.lolliMany (List.replicate k Ty.bin) Ty.bin)) :
∃ B : Nat → Nat,
IsPolyBoundedOfDegree B (Nat.max (braceDepth t) 1) ∧
∀ (Γ : Context) (ls : List Term) (ns : List Nat),
ls.length = k →
ValidBinListInputs Γ ls ns →
∃ (steps m : Nat) (w : Term),
RedSteps steps (Term.appMany t ls) w ∧
IsNormal w ∧
listEntryCount w = some m ∧
m ≤ sumListLengths ns ∧
steps ≤ B (sumListLengths ns) := by sorry
end AehligSchwichtenberg2002V2Read-back
What the Lean code literally says, in plain math · OpenAI Codex (GPT-6)
For every and term , assume that has, in the empty context, the iterated arrow type with argument types and result . There exists one function with a polynomial upper bound of degree parameter such that for every context , term list and natural-number list , if and the triple is valid for binary list inputs, there exist and a term with all of the following properties. A sequence of exactly single steps goes from the left-associated application to , the term is normal, returns , , and . The sum of an empty number list is zero. The case uses the binary list type itself for , the term itself as the reduction source, and the triple of empty lists, with . The step count can be zero. The types are generated by , , arrows , tensors , products , and lists . A variable is a pair of a natural-number identifier and a type. Equality of variables compares both entries. The terms are variables, constants, abstractions , pairs , applications , and braces . Successive applications associate to the left and arrow chains associate to the right. The constants and have declared type . For every type , the constants and have declared types and . For all types , has declared type . Contexts are lists of variables. A context is a union of two operand contexts if each variable belongs to the result exactly when it belongs to at least one operand. A disjoint union additionally requires that the operands have no common variable. These relations permit arbitrary ordering and repetitions within a context. The typing relation is generated by the variable rule in any context containing that variable, and the constant rule in any context with the declared constant type. An abstraction has type in if has declared type and has type in a union of and the singleton list . An application has type in a disjoint union of contexts typing at and at . The pair has type if has type and has type in the same context. A term of product type gives applications and of types and in its context. If has Boolean type and both and have type in a shared context disjoint from the context of , then has type in their disjoint union. For distinct variables of types , respectively, has type in a disjoint union of a context typing at and a context disjoint from , provided has type in a union of and . If has type and has type in the empty context, has type in the context of . The optional list entry count returns on any , returns on if returns a number, and is undefined otherwise. It looks at the rightmost tail argument of each fully applied , permits any parameters on the constructors along that chain, and ignores the contents of the other two arguments. The free occurrences of a variable term are its singleton list and a constant contributes none. An abstraction filters the occurrences of its binder from those of its body, a pair or application concatenates the two occurrence lists from left to right, and braces use the occurrence list of their contents. The list retains the first occurrence of each distinct variable in the resulting list. For a term , is the maximum of and every variable identifier in , including the identifiers of abstraction binders. For variables and a term , renaming free to in replaces each variable node equal to by , leaves constants as they are and recurses into pairs, applications and braces. At an abstraction with binder it returns that abstraction as it is. At other abstractions it keeps the binder and recurses into the body, which permits the new occurrences of to be bound by an existing binder. For a natural bound , term , variable and replacement term , the substitution auxiliary function replaces a variable node by exactly when its variable equals , preserves constants, and recurses with bound into both children of pairs and applications and into the contents of braces. At a binder it returns the whole abstraction if . If and occurs free in , it gives the binder a new identifier and keeps its type. It renames free occurrences of in the body to the new variable, and recurses on the renamed body with bound . In the remaining case it preserves the binder and recurses on the body with bound . Write for substitution of for in , starting the auxiliary function with bound . A binder may be freshened by this operation even when has no free occurrence in its body. For terms and variables , the two-variable substitution returns if is absent from the free occurrences of . If occurs free in , it chooses of 's type and identifier . It renames free to in , substitutes for in that result, then substitutes for . This function accepts any , including . The direct conversions are , , , and . They also include converting to the two-variable substitution in of for and for , for distinct with respective types . The iteration conversions are and , with the latter requiring to return a number. The term arguments in these patterns range over raw terms. A single step performs one direct conversion at the root or at a subterm reached by descending through any number of application nodes, on either side of each application. A term is normal if it has no outgoing single step. In particular, abstractions, pairs and braces are normal at the root regardless of their contents. For a context , a list of terms and a list of natural numbers , validity of binary list inputs is generated from the triple of three empty lists. A rule prepends a term to the tail term list and a number to the tail number list when the tail lists have a valid context and there is a context consisting entirely of variables of type with , normal, and returning . The new context must be a disjoint union of and . The term and number lists therefore have the same length and their entries are matched in order. In the empty case the context must be the empty list. The brace depth gives variables and constants , takes the body depth for an abstraction, the maximum of the two depths for a pair or an application, and the contents' depth plus for a brace. For a function and a degree parameter , the polynomial bound of degree parameter means there are constants such that for every . The constants can be zero, and allows a constant upper bound.