This is Theorem 16 of Hofmann and Moser (TLCA 2015, p. 252), the main soundness theorem of multivariate amortised resource analysis for term rewrite systems.
Assume the standing conditions of Sections 2–4:
S is a finite nonempty constructor signature (FiniteConstructors C), (C,D) is a finite overall signature with at least one constant (FiniteSignature C D), and P is a representative policy (RepPolicy C).
R is a finite (FiniteSystem R), syntactically orthogonal (SyntacticallyOrthogonal R), and completely defined (CompletelyDefined R) constructor term rewrite system.
F (AnnotatedSignatures C D) consists of extensional counted and cost-free annotated signatures (AnnotatedSignatureExtensional F.counted and AnnotatedSignatureExtensional F.costFree) such that R is bounded with respect to F (BoundedSignatures S P F R).
Γ=(x1,…,xn) (xs : Fin n → Nat) is a context of pairwise distinct variables (Function.Injective xs), Q is a length-n input annotation (Annotation C n), t is a term (Term C D), Q′ is a length-1 output annotation (Annotation C 1), and Γ:Q⊢t:Q′ is derivable in counted mode (Typing S P F .counted n xs Q t Q').
σ (Substitution C D) is a normalised substitution (σ.Normalised) such that every context variable xi lies in dom(σ) with σ(xi)=vi ((vs i).toTerm) for ground constructor values v1,…,vn (vs : Fin n → Value C).
If t evaluates under σ to a ground constructor value v (v.toTerm) in m∈N innermost rewrite steps (Evaluates R σ t m v.toTerm), then the difference between the input potential and the output potential bounds the step count m:
Φ(v1,…,vn:Q)−Φ(v:Q′)≥m.
This theorem guarantees that any static resource bound derived in the type system of Figure 2 is a sound upper bound on the number of innermost evaluation steps on all ground constructor inputs.
Preamble
import Definitions.Def_HofmannMoser_Syntax
import Definitions.Def_HofmannMoser_Potential
import Definitions.Def_HofmannMoser_Typing
universe u
Formal statement
namespace HofmannMoser
theorem theorem_16 {C D : Nat → Type u}
(S : FiniteConstructors C) (P : RepPolicy C)
(F : AnnotatedSignatures C D) (R : RewriteSystem C D)
(hFinSig : FiniteSignature C D)
(hFinSys : FiniteSystem R)
(hOrth : SyntacticallyOrthogonal R)
(hCompDef : CompletelyDefined R)
(hExtCounted : AnnotatedSignatureExtensional F.counted)
(hExtCostFree : AnnotatedSignatureExtensional F.costFree)
(hBounded : BoundedSignatures S P F R)
{n : Nat} (xs : Fin n → Nat) (hDistinct : Function.Injective xs)
(Q : Annotation C n) (t : Term C D) (Q' : Annotation C 1)
(hType : Typing S P F .counted n xs Q t Q')
(σ : Substitution C D) (hNorm : σ.Normalised)
(vs : Fin n → Value C)
(hDom : ∀ i, xs i ∈ σ.dom)
(hSubst : ∀ i, σ.assignment (xs i) = (vs i).toTerm)
(m : Nat) (v : Value C)
(hEval : Evaluates R σ t m v.toTerm) :
potential Q vs - potential Q' (fun _ ↦ v) ≥ (m : Rat) := by sorry
end HofmannMoser
Source
Hofmann--Moser 2015, Multivariate Amortised Resource Analysis for Term Rewrite Systems, TLCA 2015, https://doi.org/10.4230/LIPIcs.TLCA.2015.241, Section 4, p. 252, Theorem 16
Read-back
What the Lean code literally says, in plain math · gemini-2.5-pro
Read-back of HofmannMoser.theorem_16
Fix a universe level u and let C,D:N→Typeu be arity-indexed families of constructor symbols and defined function symbols, respectively. The theorem universally quantifies over the following parameters, structures, and hypotheses:
Finite constructor witness (S:FiniteConstructors(C)): A structure providing a finite list symbols of dependent arity-symbol pairs ⟨k,c⟩ (k∈N,c∈C(k)) such that every ⟨k,c⟩ with c∈C(k) belongs to symbols, together with a witness that ⋃k∈NC(k) is nonempty.
Automaton representation policy (P:RepPolicy(C)): A map rep assigning to every basic function p∈BasicFunction(C) a tree automaton P.rep(p)∈TreeAutomaton(C) whose induced run-counting function (P.rep(p)).basic equals p.
Here a ground constructor valuev∈Value(C) is an inductively defined finite tree node(c,(v0,…,vk−1)) with k∈N, c∈C(k), and children v0,…,vk−1∈Value(C).
A tree automatonA∈TreeAutomaton(C) consists of a positive state count M=A.stateCount∈N, a designated root/final state A.final∈{0,…,M−1} (forcing M≥1), and for each arity k∈N and constructor c∈C(k) a duplicate-free finite list A.rules(k,c) of transitions ((q0,…,qk−1),q)∈{0,…,M−1}k×{0,…,M−1}, such that only finitely many pairs ⟨k,c⟩ have a nonempty rule list and at least one pair ⟨k,c⟩ has a nonempty rule list.
The run countA.runCount(v,q)∈N of A on v=node(c,(v0,…,vk−1)) at state q is defined recursively by
where an empty product ($k = 0$) is $1$ and an empty sum is $0$. The function $A.\mathrm{basic} : \mathsf{Value}(C) \to \mathbb{N}$ is defined by $A.\mathrm{basic}(v) = \mathrm{runCount}(A, v, A.\mathrm{final})$.
A function f:Value(C)→N is a basic function (IsBasicFunction(C,f)) if f=A.basic for some tree automaton A, and BasicFunction(C) is the subtype of such functions.
Annotated signatures (F:AnnotatedSignatures(C,D)): A pair of relations F.counted and F.costFree, each of type (k:N)→D(k)→Annotation(C,k)→Annotation(C,1)→Prop. For a typing mode μ∈{counted,costFree}, F.get(μ) denotes F.counted when μ=counted and F.costFree when μ=costFree.
For k∈N, a k-ary annotationQ∈Annotation(C,k) is a finite list of pairs (p,q) where p=(p0,…,pk−1)∈BasicFunction(C)k is a k-tuple of basic functions and q∈Q is a rational number satisfying q≥0. (Because Q is a list, the same tuple p may appear multiple times in Q, and entries with q=0 are permitted.)
Rewrite system (R:RewriteSystem(C,D)): A predicate R:Rule(C,D)→Prop specifying a set of rewrite rules.
A termt∈Term(C,D) is inductively either a variable var(x) with x∈N, or a function application func(f,(t0,…,tk−1)) where k∈N, f∈C(k)⊕D(k) (written inl(c) for c∈C(k) and inr(d) for d∈D(k)), and t0,…,tk−1∈Term(C,D).
For a term t, t.variables∈List(N) is the list of variable indices occurring in t in left-to-right preorder traversal (with multiplicity). Simultaneous substitution t.subst(α) replaces each var(x) by α(x)∈Term(C,D), and variable renaming t.rename(ρ) for ρ:N→N replaces each var(x) by var(ρ(x)).
A ruler∈Rule(C,D) consists of an arity k=r.arity∈N, a head defined symbol r.symbol∈D(k), a pattern tuple r.patterns:{0,…,k−1}→Term(C,D), and a right-hand side term r.rhs∈Term(C,D). Its left-hand side is r.lhs=func(inr(r.symbol),r.patterns), and r.lhsVariables is the concatenation of (r.patterns(i)).variables for i=0,…,k−1.
There exists a finite list of pairs ⟨k,c⟩ containing every constructor symbol c∈C(k);
There exists a finite list of pairs ⟨k,d⟩ containing every defined symbol d∈D(k);
⋃k∈NC(k) is nonempty; and
C(0) is nonempty or D(0) is nonempty.
Finite system hypothesis (hFinSys:FiniteSystem(R)): There exists a finite list rules of rules such that for every r∈Rule(C,D), R(r) holds if and only if r∈rules.
Left-linear constructor rules: Every rule r satisfying R(r) has the property that (i) for each i, r.patterns(i) is a constructor term (IsConstructorTerm, i.e., built solely from variables and constructors inl(c) with no defined symbols inr(d)), (ii) every variable x∈r.rhs.variables also appears in r.lhsVariables, and (iii) every variable x∈N occurs at most once in the list r.lhsVariables.
No non-trivial root overlaps: For all rules r1,r2 with R(r1) and R(r2), if r1 and r2 are not α-equivalent—where α-equivalence means there exists a bijection ρ:N→N such that r1.lhs.rename(ρ)=r2.lhs and r1.rhs.rename(ρ)=r2.rhs—then r1 and r2 have no root overlap: there do not exist injective maps ρ1,ρ2:N→N and a substitution σ∈Substitution(C,D) such that ρ1(x)=ρ2(y) for all x∈r1.lhsVariables and y∈r2.lhsVariables and σ.instantiate(r1.lhs.rename(ρ1))=σ.instantiate(r2.lhs.rename(ρ2)).
Here a substitutionσ∈Substitution(C,D) consists of a domain list σ.dom∈List(N) and a total map σ.assignment:N→Term(C,D); its application map σ.apply(x) returns σ.assignment(x) if x∈σ.dom and var(x) otherwise, and σ.instantiate(t)=t.subst(σ.apply).
Completely defined hypothesis (hCompDef:CompletelyDefined(R)): For every term t∈Term(C,D) with t.variables=[], if t is in normal form with respect to R, then t satisfies IsValue(t) (i.e., t is built exclusively from constructor symbols inl(c) with no variables and no defined symbols). Here t is in normal form (NormalForm(R,t)) if there is no term s such that RewriteStep(R,t,s) holds, where RewriteStep(R,t,s) means there exist a rule r with R(r), an injective map ρ:N→N, a substitution σ, and a single-hole context ctx∈Context(C,D) such that t=ctx.plug(σ.instantiate(r.lhs.rename(ρ))) and s=ctx.plug(σ.instantiate(r.rhs.rename(ρ))).
Extensionality of counted and cost-free signatures (hExtCounted and hExtCostFree): Both F.counted and F.costFree satisfy AnnotatedSignatureExtensional: for every arity k∈N, defined symbol f∈D(k), k-ary annotations P0,P0′∈Annotation(C,k), and 1-ary annotations Q0,Q0′∈Annotation(C,1), if annotationEq(P0,P0′) and annotationEq(Q0,Q0′), then F(k,f,P0,Q0)⟺F(k,f,P0′,Q0′).
For an annotation Q∈Annotation(C,k) and a tuple p∈BasicFunction(C)k, the coefficientannotationCoefficient(Q,p)∈Q is the sum of weights q over all entries (p′,q) in the list Q with p′=p.
Two annotations P0,P0′∈Annotation(C,k) satisfy annotationEq(P0,P0′) (resp. annotationLe(P0,P0′)) if for every p∈BasicFunction(C)k, annotationCoefficient(P0,p)=annotationCoefficient(P0′,p) (resp. ≤).
Bounded signatures hypothesis (hBounded:BoundedSignatures(S,P,F,R)): Both Bounded(S,P,F,R,counted) and Bounded(S,P,F,R,costFree) hold. For a mode μ∈{counted,costFree}, Bounded(S,P,F,R,μ) states that for every rule r with R(r) and every Qr∈Annotation(C,r.arity) and Qr′∈Annotation(C,1) satisfying F.get(μ,r.arity,r.symbol,Qr,Qr′), there exist a list of variable indices vars∈List(N) of some length L and annotations P0,shifted∈Annotation(C,L) such that:
PatternExpansion(P,[r.patterns(0),…,r.patterns(r.arity−1)],Qr,vars,shifted) holds, where PatternExpansion inductively rewrites a list of pattern terms and an annotation of matching length by repeatedly choosing a position pos containing a constructor pattern func(inl(c),(s0,…,sk−1)), splicing s0,…,sk−1 in place of position pos in the term list, and replacing each annotation entry (p,q) via additiveShiftAt(P,pos,c,⋅) with the entries obtained from every transition ((q0,…,qk−1),A.final)∈A.rules(k,c) of A=P.rep(ppos) by splicing the rerooted basic functions (A.reroot(q0)).basic,…,(A.reroot(qk−1)).basic in place of ppos with weight q, until the pattern list equals [var(vars[0]),…,var(vars[L−1])];
If μ=counted, then annotationEq(addConstant(S,P0,1),shifted), where addConstant(S,P0,1) prepends the entry (uL,1) to P0 with uL being the L-tuple of canonical basic functions (induced by the 1-state automaton TreeAutomaton.canonical(S) that has transition ((0,…,0),0) for every constructor and evaluates to 1 on every value); if μ=costFree, then annotationEq(P0,shifted);
Typing context, term, and derivation (n, xs, hDistinct, Q, t, Q′, hType):
n∈N is an implicit natural number (possibly 0);
xs:{0,…,n−1}→N is an injective map (hDistinct:∀i,j,xs(i)=xs(j)⟹i=j) assigning pairwise distinct variable indices to the n context positions;
Q∈Annotation(C,n) is an n-ary input annotation, t∈Term(C,D) is a term, and Q′∈Annotation(C,1) is a 1-ary output annotation;
hType:Typing(S,P,F,counted,n,xs,Q,t,Q′) is a derivation in the inductive typing judgment Typing(S,P,F,μ,n,xs,Q,t,Q′) specialized to μ=counted. The inductive relation Typing is generated by 8 rules:
Variable (variable): Types var(x) in context (0↦x) of length 1 with input annotation Q and identical output annotation Q.
Defined symbol (defined): For f∈D(k) and injective xs:{0,…,k−1}→N, if F.get(μ,k,f,Q,Q′) holds, types func(inr(f),(i↦var(xs(i)))) with input Q and output Q′.
Constructor (constructor): For c∈C(k), injective xs:{0,…,k−1}→N, and Q∈Annotation(C,1), types func(inl(c),(i↦var(xs(i)))) with input additiveShift(P,c,Q)∈Annotation(C,k) (which expands the single coordinate of Q along transitions into A.final of A=P.rep(p0) for rule (k,c)) and output Q.
Annotation weakening (weakenAnnotations): For injective xs, weakens input P0 to Q and output P′ to Q′ whenever annotationLe(P0,Q) and annotationLe(Q′,P′).
Context exchange (exchange): Permutes the context xs and annotation coordinates of Q along any bijection ρ:{0,…,k−1}→{0,…,k−1}.
Context weakening (weakenContext): Extends a typing of t in context (xs(0),…,xs(k−1)) under annotationProject(Q,u1) (the k-ary annotation retaining entries of Q∈Annotation(C,k+1) whose last coordinate equals the canonical basic function BasicFunction.canonical(S)) to the injective context xs:{0,…,k}→N under Q.
Sharing (share): Given a typing of t in an (m+2)-variable context (xs(0),…,xs(m−1),x,y) under Q∈Annotation(C,m+2) where xs is injective, x=y, x,y,z are distinct from all xs(i), and z∈/{x,y}∪t.variables, derives a typing of t.rename(v↦if v=x∨v=y then z else v) in context (xs(0),…,xs(m−1),z) under annotationShare(S,P,Q)∈Annotation(C,m+1). Here annotationShare(S,P,Q) replaces the last two basic functions (pm,pm+1) of each entry in Q by their automaton product BasicFunction.product(S,P,pm,pm+1), which is the basic function of TreeAutomaton.product(S,P.rep(pm),P.rep(pm+1)) (an automaton with M1M2+1 states, final state q1finM2+q2fin, and transitions formed by deduplicating all paired transitions of the two automata plus a padding transition ((M1M2,…,M1M2),M1M2)).
Composition (composition): For f∈C(ℓ+1)⊕D(ℓ+1), argument terms t0,…,tℓ, variable lists Γ0,…,Γℓ whose concatenation Γ=Γ0++⋯++Γℓ is duplicate-free with (ti).variables⊆Γi for each i≤ℓ, and injective fresh variables y0,…,yℓ∈/Γ∪⋃j=0ℓ(tj).variables, combines a mode-μ typing of func(f,(i↦var(yi))) under S′∈Annotation(C,ℓ+1) and output Q′ with family typings of each ti in context Γi under input Parg(i,ι) and output Rarg(i,ι) (typed in mode listPremiseMode(S,μ,ι), which is counted if μ=counted and every basic function in ι is BasicFunction.canonical(S), and costFree otherwise) for all index lists ι of length i+∑k=i+1ℓ∣Γk∣, provided Q,S′,Parg,Rarg satisfy the coefficient chaining equations compositionCoefficients, to type func(f,(t0,…,tℓ)) in context Γ with input Q and output Q′.
Substitution, input values, and evaluation (σ, hNorm, vs, hDom, hSubst, m, v, hEval):
σ∈Substitution(C,D) is a substitution that is normalised (hNorm:∀x∈σ.dom,IsValue(σ.assignment(x)));
vs:{0,…,n−1}→Value(C) is an n-tuple of constructor values such that for every i∈{0,…,n−1}, xs(i)∈σ.dom (hDom) and σ.assignment(xs(i))=(vs(i)).toTerm (hSubst), where for any w∈Value(C), w.toTerm∈Term(C,D) is the ground constructor term obtained by replacing every node(c,…) by func(inl(c),…);
m∈N is a natural number step cost and v∈Value(C) is an output constructor value;
hEval:Evaluates(R,σ,t,m,v.toTerm) states that t evaluates under σ and R in cost m to v.toTerm, according to the 4-rule inductive big-step operational semantics Evaluates:
Variable (var): If x∈σ.dom and σ.assignment(x)=w, then var(x) evaluates under σ in cost 0 to w.
Constructor (constructor): For c∈C(k), if yi∈σ.dom and σ.assignment(yi)=wi for all i∈{0,…,k−1}, then func(inl(c),(i↦var(yi))) evaluates under σ in cost 0 to func(inl(c),(w0,…,wk−1)).
Rewrite (rewrite): For f∈D(k), if r is a rule with R(r), r.arity=k, and r.symbol=f, ρ:N→N is injective, τ is a normalised substitution whose domain is disjoint from σ.dom (∀x∈σ.dom,x∈/τ.dom), yi∈σ.dom and σ.assignment(yi)=τ.instantiate((r.patterns(i)).rename(ρ)) for all i∈{0,…,k−1}, and r.rhs.rename(ρ) evaluates under the left-biased union substitution σ∪τ in cost m0 to w, then func(inr(f),(i↦var(yi))) evaluates under σ in cost m0+1 to w.
Composition (composition): For f∈C(k)⊕D(k), argument terms s0,…,sk−1, and injective variables y0,…,yk−1 such that yi∈/σ.dom and yi∈/(sj).variables for all i,j, if each si evaluates under σ in cost ci to wi and func(f,(i↦var(yi))) evaluates under σ∪[y0↦w0,…,yk−1↦wk−1] in cost cout to w, then func(f,(s0,…,sk−1)) evaluates under σ in cost cout+∑i=0k−1ci to w.
Conclusion: Under all the above hypotheses, the rational potential difference satisfies the inequality
potential(Q,vs)−potential(Q′,(0↦v))≥(m:Q),
where for any k∈N, annotation A∈Annotation(C,k), and value tuple w:{0,…,k−1}→Value(C), the potential is the rational number
(0↦v):{0}→Value(C) is the singleton tuple with entry v, and the subtraction and ≥ comparison take place in Q.
Edge cases and boundary conditions:
The context length n=0 and evaluation cost m=0 are included in the universal quantifiers. When n=0, the product ∏i=0n−1pi(vs(i)) is the empty product 1, so potential(Q,vs) is the sum of rational weights in Q; when an annotation list is empty, its potential is 0∈Q.
The substitution domain σ.dom is only required to contain {xs(0),…,xs(n−1)}; it may contain additional variable indices outside the image of xs (whose assigned terms must also be values by hNorm) as well as duplicate entries in σ.dom, while values of σ.assignment(x) for x∈/σ.dom are unconstrained.
The ambient assumptions hFinSig, hFinSys, hOrth, hCompDef, hExtCounted, and hExtCostFree are global hypotheses on C,D,R,F alongside the explicit derivation hypotheses hType and hEval.
Confirmed by the moderator at approval.