Resource vectors, annotated signatures, and potential
DefinitionMoserSchneckenreither_AnnotationsResource annotations are finitely supported vectors of nonnegative rationals, identifying trailing zeroes. Their degree is one beyond the last nonzero index, with degree zero for the zero vector; their maximum coefficient is zero for the zero vector. An annotated signature gives a nonempty set of declarations for every function symbol. For each constructor-like symbol, the input annotations and cost are uniquely determined by the result vector, and are additive and positively homogeneous. The representation supplies these declarations for every result vector, explicitly adopting the basis-annotation convention used in the source's potential definition. Potential follows Definition 3's whole-term case distinction: any unsupported symbol makes the entire ground term's potential zero; otherwise the root cost and recursively computed child potentials are added. A context potential sums over variable assignments. Polynomial constructor constraints apply to nonzero output vectors, with the zero-vector base case supplied by homogeneity. A runtime bound is an eventual uniform bound on charged steps of all finite derivations from basic inputs, without forming a partial maximum.
import Definitions.Def_MoserSchneckenreither_Syntax
import Mathlib.Data.NNRat.Lemmas
import Mathlib.Data.Finsupp.Order
import Mathlib.Data.Finsupp.SMul
import Mathlib.Data.Finset.Lattice.Fold
/-!
Resource annotations, signatures and potentials of Moser–Schneckenreither,
arXiv:1811.09071v1, Section 4, pp. 7–10, Definitions 2–3.
Trailing zeroes are identified. Constructor-like declarations are presented as total
functions of the result annotation, making the basis-annotation convention explicit.
-/
noncomputable section
namespace MoserSchneckenreither
/-- Finite vectors of nonnegative rationals, modulo trailing zeroes. -/
abbrev Annotation := ℕ →₀ ℚ≥0
def Annotation.degree (q : Annotation) : ℕ := q.support.sup Nat.succ
def Annotation.maxCoeff (q : Annotation) : ℚ≥0 := q.support.sup q
def Annotation.scale (a : ℚ≥0) (q : Annotation) : Annotation := a • q
def Shares (p p₁ p₂ : Annotation) : Prop := p₁ + p₂ = p
structure Declaration (n : ℕ) where
inputs : Fin n → Annotation
cost : ℚ≥0
output : Annotation
/-- Resource polymorphism and the uniquely determined constructor-like annotations. -/
structure AnnotatedSignature {sig : Signature} (P : Problem sig) where
declarations : (f : Symbol sig) → Declaration (sig.arity f) → Prop
nonempty : ∀ f, ∃ d, declarations f d
input : (f : Symbol sig) → Annotation → Fin (sig.arity f) → Annotation
cost : Symbol sig → Annotation → ℚ≥0
constructor_declaration : ∀ f, ConstructorLike P f → ∀ q,
declarations f ⟨input f q, cost f q, q⟩
constructor_unique : ∀ f, ConstructorLike P f → ∀ d, declarations f d →
d.inputs = input f d.output ∧ d.cost = cost f d.output
input_add : ∀ f, ConstructorLike P f → ∀ p q i,
input f (p + q) i = input f p i + input f q i
cost_add : ∀ f, ConstructorLike P f → ∀ p q,
cost f (p + q) = cost f p + cost f q
input_scale : ∀ f, ConstructorLike P f → ∀ a q i,
input f (Annotation.scale a q) i = Annotation.scale a (input f q i)
cost_scale : ∀ f, ConstructorLike P f → ∀ a q,
cost f (Annotation.scale a q) = a * cost f q
variable {sig : Signature} {P : Problem sig}
/-- Recursive part of Definition 3; the public potential below enforces its whole-term case split. -/
def rawPotential (F : AnnotatedSignature P) : Term sig → Annotation → ℚ≥0
| .var _, _ => 0
| .app f ts, q => F.cost f q +
(List.ofFn fun i ↦ rawPotential F (ts i) (F.input f q i)).sum
/-- Definition 3: an unsupported symbol anywhere in a ground term makes its potential zero. -/
def potential (F : AnnotatedSignature P) (t : Term sig) (q : Annotation) : ℚ≥0 := by
classical
exact if Supported P t then rawPotential F t q else 0
/-- A context is a finite list representing a partial map; typing enforces distinct variable keys. -/
abbrev Context := List (ℕ × Annotation)
def Context.keys (Γ : Context) : List ℕ := Γ.map Prod.fst
def Context.Valid (Γ : Context) : Prop := Γ.keys.Nodup
def Context.lookup (Γ : Context) (x : ℕ) : Annotation :=
((Γ.filter fun a ↦ a.1 == x).map Prod.snd).sum
def Context.renameMerge (Γ : Context) (ρ : ℕ → ℕ) : Context :=
let names := (Γ.map fun a ↦ ρ a.1).eraseDups
names.map fun x ↦ (x, ((Γ.filter fun a ↦ ρ a.1 == x).map Prod.snd).sum)
def contextPotential (F : AnnotatedSignature P) (σ : Substitution sig) (Γ : Context) : ℚ≥0 :=
(Γ.map fun a ↦ potential F (σ.apply a.1) a.2).sum
/-- The polynomial side conditions, including the zero-vector base case of the proof. -/
def PolynomialConstructors (F : AnnotatedSignature P) : Prop :=
∀ c ∈ sig.constructors, ∀ q : Annotation, q ≠ 0 →
F.cost c q ≤ q.maxCoeff ∧
∀ i, ∃ r : Annotation,
F.input c q i ≤ q + r ∧ r.maxCoeff ≤ q.maxCoeff ∧ r.degree < q.degree
/-- A degree bound for one usable declaration of each defined symbol. -/
def HasAnalysisDegree (F : AnnotatedSignature P) (d : ℕ) : Prop :=
∀ f, f ∉ sig.constructors → ∃ a, F.declarations f a ∧
∀ i, (a.inputs i).degree ≤ d
/-- The finite-derivation formulation of the runtime bound in Definition 1. -/
def PolynomialRuntime (P : Problem sig) (d : ℕ) : Prop :=
∃ C : ℚ≥0, ∃ n₀ : ℕ, ∀ n ≥ n₀, ∀ t : Term sig, t.Basic → t.size ≤ n →
∀ m u, Derivation P t m u → (m : ℚ≥0) ≤ C * (n : ℚ≥0) ^ d
end MoserSchneckenreither
Read-back
What the Lean code literally says, in plain math · GPT-6 (Codex)
Annotation. An annotation is a function whose support is finite; indices start at zero, every coefficient is a nonnegative rational number, and the identically zero function with empty support is included.
Annotation.degree. For every finitely supported function , its degree is the natural number ; thus the zero annotation has degree zero, while every nonzero annotation has degree one greater than its largest nonzero index, including degree one when its only nonzero coefficient is at index zero.
Annotation.maxCoeff. For every finitely supported function , its maximum coefficient is , a nonnegative rational number; in particular , and indices outside the finite support contribute no positive value.
Annotation.scale. For every scalar and finitely supported function , scaling produces the finitely supported function given by for every ; both a zero scalar and a zero annotation are allowed and yield the zero annotation.
Shares. For arbitrary finitely supported functions , the proposition that shares into and means exactly , or equivalently for every natural-number index ; zero annotations are allowed, either summand may equal all of , and if then both summands are zero.
Declaration. For every natural number , a declaration of arity consists of an indexed family of finitely supported functions , a cost , and an output with finite support; these fields have no further constraints or relations. The case is allowed, in which the input family is empty while the cost and output remain arbitrary, including zero.
AnnotatedSignature. Let a signature consist of a natural number , the symbol set , an arity for every , a nonempty subset of constructor symbols, and the requirement that at least one symbol has arity zero; that symbol need not belong to , and nonemptiness of excludes . Terms are finite trees whose leaves may be variables indexed by and whose node labelled has exactly ordered children. Let consist of arbitrary finite lists and of rules; each rule has a left side with , an arbitrary right-side term, and the requirement that every variable occurring on the right also occurs on the left. Either rule list may be empty, and the lists need not be disjoint. Write for the finitely supported functions , with pointwise addition, scalar multiplication, and order, and write for the symbols that either belong to or occur, at any depth, in at least one argument of the left side of at least one rule in or . An annotated signature consists of a nonempty set of declaration triples for every , together with maps and . For every it is required that , that for all , and that for all and . For every such and every input index , it is additionally required that for all and that for all and . These quantifiers include zero annotations and ; for there are no such equations or required relation between and the maps, beyond nonemptiness of . Nullary symbols have empty input families, while the cost identities still apply to them when they belong to .
rawPotential. Let a signature consist of a natural number , the symbol set , an arity for every , a nonempty subset of constructor symbols, and the requirement that at least one symbol has arity zero; that symbol need not belong to , and nonemptiness of excludes . Terms are finite trees whose leaves may be variables indexed by and whose node labelled has exactly ordered children. Let consist of arbitrary finite lists and of rules; each rule has a left side with , an arbitrary right-side term, and the requirement that every variable occurring on the right also occurs on the left. Either rule list may be empty, and the lists need not be disjoint. Write for the finitely supported functions , with pointwise addition, scalar multiplication, and order, and write for the symbols that either belong to or occur, at any depth, in at least one argument of the left side of at least one rule in or . An annotated signature consists of a nonempty set of declaration triples for every , together with maps and . For every it is required that , that for all , and that for all and . For every such and every input index , it is additionally required that for all and that for all and . These quantifiers include zero annotations and ; for there are no such equations or required relation between and the maps, beyond nonemptiness of . Nullary symbols have empty input families, while the cost identities still apply to them when they belong to . Define for a variable and . This defines the nonnegative rational raw potential for every term and every annotation, whether or not the term is ground, normal under the rules, or built from symbols in ; each variable contributes zero regardless of its annotation, and a nullary symbol contributes exactly because its child sum is empty.
potential. Let a signature consist of a natural number , the symbol set , an arity for every , a nonempty subset of constructor symbols, and the requirement that at least one symbol has arity zero; that symbol need not belong to , and nonemptiness of excludes . Terms are finite trees whose leaves may be variables indexed by and whose node labelled has exactly ordered children. Let consist of arbitrary finite lists and of rules; each rule has a left side with , an arbitrary right-side term, and the requirement that every variable occurring on the right also occurs on the left. Either rule list may be empty, and the lists need not be disjoint. Write for the finitely supported functions , with pointwise addition, scalar multiplication, and order, and write for the symbols that either belong to or occur, at any depth, in at least one argument of the left side of at least one rule in or . An annotated signature consists of a nonempty set of declaration triples for every , together with maps and . For every it is required that , that for all , and that for all and . For every such and every input index , it is additionally required that for all and that for all and . These quantifiers include zero annotations and ; for there are no such equations or required relation between and the maps, beyond nonemptiness of . Nullary symbols have empty input families, while the cost identities still apply to them when they belong to . Define for a variable and . Define if contains no variables and every symbol occurring in belongs to , and define otherwise. This defines the nonnegative rational potential for every term and every , including ; the support condition applies to the whole term, so a variable anywhere in , or a single occurring symbol outside , makes its potential zero. No normality under the rule lists is required, and for a supported nullary symbol the value is because the child sum is empty.
Context. A context is a finite ordered list , where each is a natural-number variable name and each is a finitely supported function ; there is no distinctness requirement on the names, zero annotations are allowed, and the empty list is a context.
Context.keys. For any finite ordered list of natural-number names paired with finitely supported functions , its keys are the ordered list obtained by dropping every annotation; repeated names and their multiplicities are preserved, and the keys of the empty context form the empty list.
Context.Valid. For any finite ordered list of natural-number names paired with finitely supported functions , validity means that the list of names has no duplicates, equivalently whenever ; the annotation values impose no additional condition, repeated names remain invalid even if their annotations are zero, and the empty context is valid.
Context.lookup. For every finite ordered list of natural-number names paired with finitely supported functions , and every name , lookup returns the annotation , where addition is pointwise; consequently for each . No distinctness of names is assumed: every matching list occurrence is counted, and if there are no matches, including when is empty, the result is the zero annotation.
Context.renameMerge. For every finite ordered list of natural-number names paired with finitely supported functions , and every function , first form the list and retain each distinct value only at its first occurrence. For each retained name , the output context contains the pair , with pointwise annotation addition, and these pairs follow that first-occurrence order. Neither validity of nor injectivity of is assumed, so all repeated or newly colliding names are merged; names with a zero summed annotation are retained, and an empty input context produces an empty output context.
contextPotential. Let a signature consist of a natural number , the symbol set , an arity for every , a nonempty subset of constructor symbols, and the requirement that at least one symbol has arity zero; that symbol need not belong to , and nonemptiness of excludes . Terms are finite trees whose leaves may be variables indexed by and whose node labelled has exactly ordered children. Let consist of arbitrary finite lists and of rules; each rule has a left side with , an arbitrary right-side term, and the requirement that every variable occurring on the right also occurs on the left. Either rule list may be empty, and the lists need not be disjoint. Write for the finitely supported functions , with pointwise addition, scalar multiplication, and order, and write for the symbols that either belong to or occur, at any depth, in at least one argument of the left side of at least one rule in or . An annotated signature consists of a nonempty set of declaration triples for every , together with maps and . For every it is required that , that for all , and that for all and . For every such and every input index , it is additionally required that for all and that for all and . These quantifiers include zero annotations and ; for there are no such equations or required relation between and the maps, beyond nonemptiness of . Nullary symbols have empty input families, while the cost identities still apply to them when they belong to . Define for a variable and . Define if contains no variables and every symbol occurring in belongs to , and define otherwise. Let a substitution consist of a finite domain and an arbitrary assignment , acting on a name by when and by the variable otherwise; its assigned terms are not required to be ground or normal. For every finite ordered context with and , its context potential is the nonnegative rational . No distinctness of names is assumed, repeated entries contribute separately, any substituted term that contains a variable or a symbol outside contributes zero, names outside therefore contribute zero, and either an empty domain or an empty context gives context potential zero.
PolynomialConstructors. Let a signature consist of a natural number , the symbol set , an arity for every , a nonempty subset of constructor symbols, and the requirement that at least one symbol has arity zero; that symbol need not belong to , and nonemptiness of excludes . Terms are finite trees whose leaves may be variables indexed by and whose node labelled has exactly ordered children. Let consist of arbitrary finite lists and of rules; each rule has a left side with , an arbitrary right-side term, and the requirement that every variable occurring on the right also occurs on the left. Either rule list may be empty, and the lists need not be disjoint. Write for the finitely supported functions , with pointwise addition, scalar multiplication, and order, and write for the symbols that either belong to or occur, at any depth, in at least one argument of the left side of at least one rule in or . An annotated signature consists of a nonempty set of declaration triples for every , together with maps and . For every it is required that , that for all , and that for all and . For every such and every input index , it is additionally required that for all and that for all and . These quantifiers include zero annotations and ; for there are no such equations or required relation between and the maps, beyond nonemptiness of . Nullary symbols have empty input families, while the cost identities still apply to them when they belong to . For , set and , so both values are zero for . The stated property means that for every constructor symbol and every nonzero annotation , and, for every input index , there exists an annotation such that pointwise, , and . The witness may depend on and may be zero; the first inequality means for every . The predicate imposes these bounds only for and ; a nullary constructor has no input-index obligations but still has the cost bound, and when the strict degree inequality requires .
HasAnalysisDegree. Let a signature consist of a natural number , the symbol set , an arity for every , a nonempty subset of constructor symbols, and the requirement that at least one symbol has arity zero; that symbol need not belong to , and nonemptiness of excludes . Terms are finite trees whose leaves may be variables indexed by and whose node labelled has exactly ordered children. Let consist of arbitrary finite lists and of rules; each rule has a left side with , an arbitrary right-side term, and the requirement that every variable occurring on the right also occurs on the left. Either rule list may be empty, and the lists need not be disjoint. Write for the finitely supported functions , with pointwise addition, scalar multiplication, and order, and write for the symbols that either belong to or occur, at any depth, in at least one argument of the left side of at least one rule in or . An annotated signature consists of a nonempty set of declaration triples for every , together with maps and . For every it is required that , that for all , and that for all and . For every such and every input index , it is additionally required that for all and that for all and . These quantifiers include zero annotations and ; for there are no such equations or required relation between and the maps, beyond nonemptiness of . Nullary symbols have empty input families, while the cost identities still apply to them when they belong to . For any natural number , define for each . Having analysis degree means that for every symbol there exists a declaration triple such that for every input index . The declaration may depend on , its cost and output are not bounded by , and it is enough that one such declaration exists for each required symbol. The parameter is allowed and requires all inputs in each chosen declaration to be zero; nullary symbols have no degree inequalities to satisfy, and if every symbol lies in the universal condition has no instances.
PolynomialRuntime. Let a signature consist of a natural number , the symbol set , an arity for every , a nonempty subset of constructor symbols, and the requirement that at least one symbol has arity zero; that symbol need not belong to , and nonemptiness of excludes . Terms are finite trees whose leaves may be variables indexed by and whose node labelled has exactly ordered children. Let consist of arbitrary finite lists and of rules; each rule has a left side with , an arbitrary right-side term, and the requirement that every variable occurring on the right also occurs on the left. Either rule list may be empty, and the lists need not be disjoint. For every natural number , the stated property means that there exist a nonnegative rational constant and a natural-number threshold such that for every with , every term , every , and every term , the following implication holds: if with , every symbol in each argument belongs to (variables in these arguments are allowed), the total number of nodes of is at most (each variable and each symbol node counts one), and there is a finite derivation from to of count , then , interpreting and as nonnegative rationals. Such a derivation is any finite sequence of steps, including an empty sequence from a term to itself with count zero; a step may apply a rule from either list at any subterm position, replacing the simultaneously substituted left side by its substituted right side under an arbitrary assignment of terms to all natural-number variables, provided that every immediate argument of that instantiated left side is normal for all rules in and . Here normal means that no rule in either list can be applied at any subterm position under any such assignment, even if that application would return the same term; the surrounding context is preserved by the step. A step designated as using contributes one to the count, and a step designated as using contributes zero; when a step qualifies under both lists either designation is available. The bound concerns every such finite derivation and every endpoint , without requiring to be normal or requiring the initial term to be ground; a nullary nonconstructor symbol is an allowed initial term, and the argument-normality condition is empty for a nullary rule. The values , , and are allowed; exponent zero uses , including , but no term has size at most zero, so the implication has no qualifying initial term at . If there are no nonconstructor symbols there are no qualifying initial terms, and if the strict-rule list is empty every derivation has count zero.