Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 16: Soundness of multivariate amortised resource analysis (Φ(σ,Γ:Q)−Φ(v:Q′)≥m\Phi(\sigma, \Gamma : Q) - \Phi(v : Q') \ge mΦ(σ,Γ:Q)−Φ(v:Q′)≥m)

Proved
HofmannMoser.theorem_16

by kmehltretter82 · Oct 28, 2026 · Mathlib c5ea003 (Lean v4.30.0)

amortized-analysiscomplexityterm-rewritingtree-automatatype-systems

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:

  1. SSS is a finite nonempty constructor signature (FiniteConstructors C), (C,D)(\mathcal{C}, \mathcal{D})(C,D) is a finite overall signature with at least one constant (FiniteSignature C D), and PPP is a representative policy (RepPolicy C).
  2. RRR is a finite (FiniteSystem R), syntactically orthogonal (SyntacticallyOrthogonal R), and completely defined (CompletelyDefined R) constructor term rewrite system.
  3. FFF (AnnotatedSignatures C D) consists of extensional counted and cost-free annotated signatures (AnnotatedSignatureExtensional F.counted and AnnotatedSignatureExtensional F.costFree) such that RRR is bounded with respect to FFF (BoundedSignatures S P F R).
  4. Γ=(x1,…,xn)\Gamma = (x_1, \dots, x_n)Γ=(x1​,…,xn​) (xs : Fin n → Nat) is a context of pairwise distinct variables (Function.Injective xs), QQQ is a length-nnn input annotation (Annotation C n), ttt is a term (Term C D), Q′Q'Q′ is a length-111 output annotation (Annotation C 1), and Γ:Q⊢t:Q′\Gamma : Q \vdash t : Q'Γ:Q⊢t:Q′ is derivable in counted mode (Typing S P F .counted n xs Q t Q').
  5. σ\sigmaσ (Substitution C D) is a normalised substitution (σ.Normalised) such that every context variable xix_ixi​ lies in dom⁡(σ)\operatorname{dom}(\sigma)dom(σ) with σ(xi)=vi\sigma(x_i) = v_iσ(xi​)=vi​ ((vs i).toTerm) for ground constructor values v1,…,vnv_1, \dots, v_nv1​,…,vn​ (vs : Fin n → Value C).

If ttt evaluates under σ\sigmaσ to a ground constructor value vvv (v.toTerm) in m∈Nm \in \mathbb{N}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 mmm:

Φ(v1,…,vn:Q)−Φ(v:Q′)≥m.\Phi(v_1, \dots, v_n : Q) - \Phi(v : Q') \ge 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 uuu and let C,D:N→TypeuC, D : \mathbb{N} \to \mathsf{Type}_uC,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:

  1. Finite constructor witness (S:FiniteConstructors(C)S : \mathsf{FiniteConstructors}(C)S:FiniteConstructors(C)): A structure providing a finite list symbols\mathrm{symbols}symbols of dependent arity-symbol pairs ⟨k,c⟩\langle k, c \rangle⟨k,c⟩ (k∈N,c∈C(k)k \in \mathbb{N}, c \in C(k)k∈N,c∈C(k)) such that every ⟨k,c⟩\langle k, c \rangle⟨k,c⟩ with c∈C(k)c \in C(k)c∈C(k) belongs to symbols\mathrm{symbols}symbols, together with a witness that ⋃k∈NC(k)\bigcup_{k \in \mathbb{N}} C(k)⋃k∈N​C(k) is nonempty.
  2. Automaton representation policy (P:RepPolicy(C)P : \mathsf{RepPolicy}(C)P:RepPolicy(C)): A map rep\mathrm{rep}rep assigning to every basic function p∈BasicFunction(C)p \in \mathsf{BasicFunction}(C)p∈BasicFunction(C) a tree automaton P.rep(p)∈TreeAutomaton(C)P.\mathrm{rep}(p) \in \mathsf{TreeAutomaton}(C)P.rep(p)∈TreeAutomaton(C) whose induced run-counting function (P.rep(p)).basic(P.\mathrm{rep}(p)).\mathrm{basic}(P.rep(p)).basic equals ppp.
    • Here a ground constructor value v∈Value(C)v \in \mathsf{Value}(C)v∈Value(C) is an inductively defined finite tree node(c,(v0,…,vk−1))\mathsf{node}(c, (v_0, \dots, v_{k-1}))node(c,(v0​,…,vk−1​)) with k∈Nk \in \mathbb{N}k∈N, c∈C(k)c \in C(k)c∈C(k), and children v0,…,vk−1∈Value(C)v_0, \dots, v_{k-1} \in \mathsf{Value}(C)v0​,…,vk−1​∈Value(C).
    • A tree automaton A∈TreeAutomaton(C)A \in \mathsf{TreeAutomaton}(C)A∈TreeAutomaton(C) consists of a positive state count M=A.stateCount∈NM = A.\mathrm{stateCount} \in \mathbb{N}M=A.stateCount∈N, a designated root/final state A.final∈{0,…,M−1}A.\mathrm{final} \in \{0, \dots, M-1\}A.final∈{0,…,M−1} (forcing M≥1M \ge 1M≥1), and for each arity k∈Nk \in \mathbb{N}k∈N and constructor c∈C(k)c \in C(k)c∈C(k) a duplicate-free finite list A.rules(k,c)A.\mathrm{rules}(k, c)A.rules(k,c) of transitions ((q0,…,qk−1),q)∈{0,…,M−1}k×{0,…,M−1}((q_0, \dots, q_{k-1}), q) \in \{0, \dots, M-1\}^k \times \{0, \dots, M-1\}((q0​,…,qk−1​),q)∈{0,…,M−1}k×{0,…,M−1}, such that only finitely many pairs ⟨k,c⟩\langle k, c \rangle⟨k,c⟩ have a nonempty rule list and at least one pair ⟨k,c⟩\langle k, c \rangle⟨k,c⟩ has a nonempty rule list.
    • The run count A.runCount(v,q)∈NA.\mathrm{runCount}(v, q) \in \mathbb{N}A.runCount(v,q)∈N of AAA on v=node(c,(v0,…,vk−1))v = \mathsf{node}(c, (v_0, \dots, v_{k-1}))v=node(c,(v0​,…,vk−1​)) at state qqq is defined recursively by
runCount(A,node(c,(v0,…,vk−1)),q)=∑((q0,…,qk−1),q′)∈A.rules(k,c)q′=q∏i=0k−1runCount(A,vi,qi),\mathrm{runCount}(A, \mathsf{node}(c, (v_0, \dots, v_{k-1})), q) = \sum_{\substack{((q_0, \dots, q_{k-1}), q') \in A.\mathrm{rules}(k, c) \\ q' = q}} \prod_{i=0}^{k-1} \mathrm{runCount}(A, v_i, q_i),runCount(A,node(c,(v0​,…,vk−1​)),q)=((q0​,…,qk−1​),q′)∈A.rules(k,c)q′=q​∑​i=0∏k−1​runCount(A,vi​,qi​),
 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)→Nf : \mathsf{Value}(C) \to \mathbb{N}f:Value(C)→N is a basic function (IsBasicFunction(C,f)\mathsf{IsBasicFunction}(C, f)IsBasicFunction(C,f)) if f=A.basicf = A.\mathrm{basic}f=A.basic for some tree automaton AAA, and BasicFunction(C)\mathsf{BasicFunction}(C)BasicFunction(C) is the subtype of such functions.
  1. Annotated signatures (F:AnnotatedSignatures(C,D)F : \mathsf{AnnotatedSignatures}(C, D)F:AnnotatedSignatures(C,D)): A pair of relations F.countedF.\mathrm{counted}F.counted and F.costFreeF.\mathrm{costFree}F.costFree, each of type (k:N)→D(k)→Annotation(C,k)→Annotation(C,1)→Prop(k : \mathbb{N}) \to D(k) \to \mathsf{Annotation}(C, k) \to \mathsf{Annotation}(C, 1) \to \mathsf{Prop}(k:N)→D(k)→Annotation(C,k)→Annotation(C,1)→Prop. For a typing mode μ∈{counted,costFree}\mu \in \{\mathsf{counted}, \mathsf{costFree}\}μ∈{counted,costFree}, F.get(μ)F.\mathrm{get}(\mu)F.get(μ) denotes F.countedF.\mathrm{counted}F.counted when μ=counted\mu = \mathsf{counted}μ=counted and F.costFreeF.\mathrm{costFree}F.costFree when μ=costFree\mu = \mathsf{costFree}μ=costFree.
    • For k∈Nk \in \mathbb{N}k∈N, a kkk-ary annotation Q∈Annotation(C,k)Q \in \mathsf{Annotation}(C, k)Q∈Annotation(C,k) is a finite list of pairs (p⃗,q)(\vec{p}, q)(p​,q) where p⃗=(p0,…,pk−1)∈BasicFunction(C)k\vec{p} = (p_0, \dots, p_{k-1}) \in \mathsf{BasicFunction}(C)^kp​=(p0​,…,pk−1​)∈BasicFunction(C)k is a kkk-tuple of basic functions and q∈Qq \in \mathbb{Q}q∈Q is a rational number satisfying q≥0q \ge 0q≥0. (Because QQQ is a list, the same tuple p⃗\vec{p}p​ may appear multiple times in QQQ, and entries with q=0q = 0q=0 are permitted.)
  2. Rewrite system (R:RewriteSystem(C,D)R : \mathsf{RewriteSystem}(C, D)R:RewriteSystem(C,D)): A predicate R:Rule(C,D)→PropR : \mathsf{Rule}(C, D) \to \mathsf{Prop}R:Rule(C,D)→Prop specifying a set of rewrite rules.
    • A term t∈Term(C,D)t \in \mathsf{Term}(C, D)t∈Term(C,D) is inductively either a variable var(x)\mathsf{var}(x)var(x) with x∈Nx \in \mathbb{N}x∈N, or a function application func(f,(t0,…,tk−1))\mathsf{func}(f, (t_0, \dots, t_{k-1}))func(f,(t0​,…,tk−1​)) where k∈Nk \in \mathbb{N}k∈N, f∈C(k)⊕D(k)f \in C(k) \oplus D(k)f∈C(k)⊕D(k) (written inl(c)\mathsf{inl}(c)inl(c) for c∈C(k)c \in C(k)c∈C(k) and inr(d)\mathsf{inr}(d)inr(d) for d∈D(k)d \in D(k)d∈D(k)), and t0,…,tk−1∈Term(C,D)t_0, \dots, t_{k-1} \in \mathsf{Term}(C, D)t0​,…,tk−1​∈Term(C,D).
    • For a term ttt, t.variables∈List(N)t.\mathrm{variables} \in \mathsf{List}(\mathbb{N})t.variables∈List(N) is the list of variable indices occurring in ttt in left-to-right preorder traversal (with multiplicity). Simultaneous substitution t.subst(α)t.\mathrm{subst}(\alpha)t.subst(α) replaces each var(x)\mathsf{var}(x)var(x) by α(x)∈Term(C,D)\alpha(x) \in \mathsf{Term}(C, D)α(x)∈Term(C,D), and variable renaming t.rename(ρ)t.\mathrm{rename}(\rho)t.rename(ρ) for ρ:N→N\rho : \mathbb{N} \to \mathbb{N}ρ:N→N replaces each var(x)\mathsf{var}(x)var(x) by var(ρ(x))\mathsf{var}(\rho(x))var(ρ(x)).
    • A rule r∈Rule(C,D)r \in \mathsf{Rule}(C, D)r∈Rule(C,D) consists of an arity k=r.arity∈Nk = r.\mathrm{arity} \in \mathbb{N}k=r.arity∈N, a head defined symbol r.symbol∈D(k)r.\mathrm{symbol} \in D(k)r.symbol∈D(k), a pattern tuple r.patterns:{0,…,k−1}→Term(C,D)r.\mathrm{patterns} : \{0, \dots, k-1\} \to \mathsf{Term}(C, D)r.patterns:{0,…,k−1}→Term(C,D), and a right-hand side term r.rhs∈Term(C,D)r.\mathrm{rhs} \in \mathsf{Term}(C, D)r.rhs∈Term(C,D). Its left-hand side is r.lhs=func(inr(r.symbol),r.patterns)r.\mathrm{lhs} = \mathsf{func}(\mathsf{inr}(r.\mathrm{symbol}), r.\mathrm{patterns})r.lhs=func(inr(r.symbol),r.patterns), and r.lhsVariablesr.\mathrm{lhsVariables}r.lhsVariables is the concatenation of (r.patterns(i)).variables(r.\mathrm{patterns}(i)).\mathrm{variables}(r.patterns(i)).variables for i=0,…,k−1i = 0, \dots, k-1i=0,…,k−1.
  3. Finite signature hypothesis (hFinSig:FiniteSignature(C,D)\mathrm{hFinSig} : \mathsf{FiniteSignature}(C, D)hFinSig:FiniteSignature(C,D)):
    • There exists a finite list of pairs ⟨k,c⟩\langle k, c \rangle⟨k,c⟩ containing every constructor symbol c∈C(k)c \in C(k)c∈C(k);
    • There exists a finite list of pairs ⟨k,d⟩\langle k, d \rangle⟨k,d⟩ containing every defined symbol d∈D(k)d \in D(k)d∈D(k);
    • ⋃k∈NC(k)\bigcup_{k \in \mathbb{N}} C(k)⋃k∈N​C(k) is nonempty; and
    • C(0)C(0)C(0) is nonempty or D(0)D(0)D(0) is nonempty.
  4. Finite system hypothesis (hFinSys:FiniteSystem(R)\mathrm{hFinSys} : \mathsf{FiniteSystem}(R)hFinSys:FiniteSystem(R)): There exists a finite list rules\mathrm{rules}rules of rules such that for every r∈Rule(C,D)r \in \mathsf{Rule}(C, D)r∈Rule(C,D), R(r)R(r)R(r) holds if and only if r∈rulesr \in \mathrm{rules}r∈rules.
  5. Syntactic orthogonality hypothesis (hOrth:SyntacticallyOrthogonal(R)\mathrm{hOrth} : \mathsf{SyntacticallyOrthogonal}(R)hOrth:SyntacticallyOrthogonal(R)):
    • Left-linear constructor rules: Every rule rrr satisfying R(r)R(r)R(r) has the property that (i) for each iii, r.patterns(i)r.\mathrm{patterns}(i)r.patterns(i) is a constructor term (IsConstructorTerm\mathsf{IsConstructorTerm}IsConstructorTerm, i.e., built solely from variables and constructors inl(c)\mathsf{inl}(c)inl(c) with no defined symbols inr(d)\mathsf{inr}(d)inr(d)), (ii) every variable x∈r.rhs.variablesx \in r.\mathrm{rhs}.\mathrm{variables}x∈r.rhs.variables also appears in r.lhsVariablesr.\mathrm{lhsVariables}r.lhsVariables, and (iii) every variable x∈Nx \in \mathbb{N}x∈N occurs at most once in the list r.lhsVariablesr.\mathrm{lhsVariables}r.lhsVariables.
    • No non-trivial root overlaps: For all rules r1,r2r_1, r_2r1​,r2​ with R(r1)R(r_1)R(r1​) and R(r2)R(r_2)R(r2​), if r1r_1r1​ and r2r_2r2​ are not α\alphaα-equivalent—where α\alphaα-equivalence means there exists a bijection ρ:N→N\rho : \mathbb{N} \to \mathbb{N}ρ:N→N such that r1.lhs.rename(ρ)=r2.lhsr_1.\mathrm{lhs}.\mathrm{rename}(\rho) = r_2.\mathrm{lhs}r1​.lhs.rename(ρ)=r2​.lhs and r1.rhs.rename(ρ)=r2.rhsr_1.\mathrm{rhs}.\mathrm{rename}(\rho) = r_2.\mathrm{rhs}r1​.rhs.rename(ρ)=r2​.rhs—then r1r_1r1​ and r2r_2r2​ have no root overlap: there do not exist injective maps ρ1,ρ2:N→N\rho_1, \rho_2 : \mathbb{N} \to \mathbb{N}ρ1​,ρ2​:N→N and a substitution σ∈Substitution(C,D)\sigma \in \mathsf{Substitution}(C, D)σ∈Substitution(C,D) such that ρ1(x)≠ρ2(y)\rho_1(x) \ne \rho_2(y)ρ1​(x)=ρ2​(y) for all x∈r1.lhsVariablesx \in r_1.\mathrm{lhsVariables}x∈r1​.lhsVariables and y∈r2.lhsVariablesy \in r_2.\mathrm{lhsVariables}y∈r2​.lhsVariables and σ.instantiate(r1.lhs.rename(ρ1))=σ.instantiate(r2.lhs.rename(ρ2))\sigma.\mathrm{instantiate}(r_1.\mathrm{lhs}.\mathrm{rename}(\rho_1)) = \sigma.\mathrm{instantiate}(r_2.\mathrm{lhs}.\mathrm{rename}(\rho_2))σ.instantiate(r1​.lhs.rename(ρ1​))=σ.instantiate(r2​.lhs.rename(ρ2​)).
    • Here a substitution σ∈Substitution(C,D)\sigma \in \mathsf{Substitution}(C, D)σ∈Substitution(C,D) consists of a domain list σ.dom∈List(N)\sigma.\mathrm{dom} \in \mathsf{List}(\mathbb{N})σ.dom∈List(N) and a total map σ.assignment:N→Term(C,D)\sigma.\mathrm{assignment} : \mathbb{N} \to \mathsf{Term}(C, D)σ.assignment:N→Term(C,D); its application map σ.apply(x)\sigma.\mathrm{apply}(x)σ.apply(x) returns σ.assignment(x)\sigma.\mathrm{assignment}(x)σ.assignment(x) if x∈σ.domx \in \sigma.\mathrm{dom}x∈σ.dom and var(x)\mathsf{var}(x)var(x) otherwise, and σ.instantiate(t)=t.subst(σ.apply)\sigma.\mathrm{instantiate}(t) = t.\mathrm{subst}(\sigma.\mathrm{apply})σ.instantiate(t)=t.subst(σ.apply).
  6. Completely defined hypothesis (hCompDef:CompletelyDefined(R)\mathrm{hCompDef} : \mathsf{CompletelyDefined}(R)hCompDef:CompletelyDefined(R)): For every term t∈Term(C,D)t \in \mathsf{Term}(C, D)t∈Term(C,D) with t.variables=[]t.\mathrm{variables} = []t.variables=[], if ttt is in normal form with respect to RRR, then ttt satisfies IsValue(t)\mathsf{IsValue}(t)IsValue(t) (i.e., ttt is built exclusively from constructor symbols inl(c)\mathsf{inl}(c)inl(c) with no variables and no defined symbols). Here ttt is in normal form (NormalForm(R,t)\mathsf{NormalForm}(R, t)NormalForm(R,t)) if there is no term sss such that RewriteStep(R,t,s)\mathsf{RewriteStep}(R, t, s)RewriteStep(R,t,s) holds, where RewriteStep(R,t,s)\mathsf{RewriteStep}(R, t, s)RewriteStep(R,t,s) means there exist a rule rrr with R(r)R(r)R(r), an injective map ρ:N→N\rho : \mathbb{N} \to \mathbb{N}ρ:N→N, a substitution σ\sigmaσ, and a single-hole context ctx∈Context(C,D)\mathrm{ctx} \in \mathsf{Context}(C, D)ctx∈Context(C,D) such that t=ctx.plug(σ.instantiate(r.lhs.rename(ρ)))t = \mathrm{ctx}.\mathrm{plug}(\sigma.\mathrm{instantiate}(r.\mathrm{lhs}.\mathrm{rename}(\rho)))t=ctx.plug(σ.instantiate(r.lhs.rename(ρ))) and s=ctx.plug(σ.instantiate(r.rhs.rename(ρ)))s = \mathrm{ctx}.\mathrm{plug}(\sigma.\mathrm{instantiate}(r.\mathrm{rhs}.\mathrm{rename}(\rho)))s=ctx.plug(σ.instantiate(r.rhs.rename(ρ))).
  7. Extensionality of counted and cost-free signatures (hExtCounted\mathrm{hExtCounted}hExtCounted and hExtCostFree\mathrm{hExtCostFree}hExtCostFree): Both F.countedF.\mathrm{counted}F.counted and F.costFreeF.\mathrm{costFree}F.costFree satisfy AnnotatedSignatureExtensional\mathsf{AnnotatedSignatureExtensional}AnnotatedSignatureExtensional: for every arity k∈Nk \in \mathbb{N}k∈N, defined symbol f∈D(k)f \in D(k)f∈D(k), kkk-ary annotations P0,P0′∈Annotation(C,k)P_0, P'_0 \in \mathsf{Annotation}(C, k)P0​,P0′​∈Annotation(C,k), and 111-ary annotations Q0,Q0′∈Annotation(C,1)Q_0, Q'_0 \in \mathsf{Annotation}(C, 1)Q0​,Q0′​∈Annotation(C,1), if annotationEq(P0,P0′)\mathsf{annotationEq}(P_0, P'_0)annotationEq(P0​,P0′​) and annotationEq(Q0,Q0′)\mathsf{annotationEq}(Q_0, Q'_0)annotationEq(Q0​,Q0′​), then F(k,f,P0,Q0)  ⟺  F(k,f,P0′,Q0′)\mathcal{F}(k, f, P_0, Q_0) \iff \mathcal{F}(k, f, P'_0, Q'_0)F(k,f,P0​,Q0​)⟺F(k,f,P0′​,Q0′​).
    • For an annotation Q∈Annotation(C,k)Q \in \mathsf{Annotation}(C, k)Q∈Annotation(C,k) and a tuple p⃗∈BasicFunction(C)k\vec{p} \in \mathsf{BasicFunction}(C)^kp​∈BasicFunction(C)k, the coefficient annotationCoefficient(Q,p⃗)∈Q\mathsf{annotationCoefficient}(Q, \vec{p}) \in \mathbb{Q}annotationCoefficient(Q,p​)∈Q is the sum of weights qqq over all entries (p⃗′,q)(\vec{p}', q)(p​′,q) in the list QQQ with p⃗′=p⃗\vec{p}' = \vec{p}p​′=p​.
    • Two annotations P0,P0′∈Annotation(C,k)P_0, P'_0 \in \mathsf{Annotation}(C, k)P0​,P0′​∈Annotation(C,k) satisfy annotationEq(P0,P0′)\mathsf{annotationEq}(P_0, P'_0)annotationEq(P0​,P0′​) (resp. annotationLe(P0,P0′)\mathsf{annotationLe}(P_0, P'_0)annotationLe(P0​,P0′​)) if for every p⃗∈BasicFunction(C)k\vec{p} \in \mathsf{BasicFunction}(C)^kp​∈BasicFunction(C)k, annotationCoefficient(P0,p⃗)=annotationCoefficient(P0′,p⃗)\mathsf{annotationCoefficient}(P_0, \vec{p}) = \mathsf{annotationCoefficient}(P'_0, \vec{p})annotationCoefficient(P0​,p​)=annotationCoefficient(P0′​,p​) (resp. ≤\le≤).
  8. Bounded signatures hypothesis (hBounded:BoundedSignatures(S,P,F,R)\mathrm{hBounded} : \mathsf{BoundedSignatures}(S, P, F, R)hBounded:BoundedSignatures(S,P,F,R)): Both Bounded(S,P,F,R,counted)\mathsf{Bounded}(S, P, F, R, \mathsf{counted})Bounded(S,P,F,R,counted) and Bounded(S,P,F,R,costFree)\mathsf{Bounded}(S, P, F, R, \mathsf{costFree})Bounded(S,P,F,R,costFree) hold. For a mode μ∈{counted,costFree}\mu \in \{\mathsf{counted}, \mathsf{costFree}\}μ∈{counted,costFree}, Bounded(S,P,F,R,μ)\mathsf{Bounded}(S, P, F, R, \mu)Bounded(S,P,F,R,μ) states that for every rule rrr with R(r)R(r)R(r) and every Qr∈Annotation(C,r.arity)Q_r \in \mathsf{Annotation}(C, r.\mathrm{arity})Qr​∈Annotation(C,r.arity) and Qr′∈Annotation(C,1)Q'_r \in \mathsf{Annotation}(C, 1)Qr′​∈Annotation(C,1) satisfying F.get(μ,r.arity,r.symbol,Qr,Qr′)F.\mathrm{get}(\mu, r.\mathrm{arity}, r.\mathrm{symbol}, Q_r, Q'_r)F.get(μ,r.arity,r.symbol,Qr​,Qr′​), there exist a list of variable indices vars∈List(N)\mathrm{vars} \in \mathsf{List}(\mathbb{N})vars∈List(N) of some length LLL and annotations P0,shifted∈Annotation(C,L)P_0, \mathrm{shifted} \in \mathsf{Annotation}(C, L)P0​,shifted∈Annotation(C,L) such that:
    • PatternExpansion(P,[r.patterns(0),…,r.patterns(r.arity−1)],Qr,vars,shifted)\mathsf{PatternExpansion}(P, [r.\mathrm{patterns}(0), \dots, r.\mathrm{patterns}(r.\mathrm{arity}-1)], Q_r, \mathrm{vars}, \mathrm{shifted})PatternExpansion(P,[r.patterns(0),…,r.patterns(r.arity−1)],Qr​,vars,shifted) holds, where PatternExpansion\mathsf{PatternExpansion}PatternExpansion inductively rewrites a list of pattern terms and an annotation of matching length by repeatedly choosing a position pos\mathrm{pos}pos containing a constructor pattern func(inl(c),(s0,…,sk−1))\mathsf{func}(\mathsf{inl}(c), (s_0, \dots, s_{k-1}))func(inl(c),(s0​,…,sk−1​)), splicing s0,…,sk−1s_0, \dots, s_{k-1}s0​,…,sk−1​ in place of position pos\mathrm{pos}pos in the term list, and replacing each annotation entry (p⃗,q)(\vec{p}, q)(p​,q) via additiveShiftAt(P,pos,c,⋅)\mathsf{additiveShiftAt}(P, \mathrm{pos}, c, \cdot)additiveShiftAt(P,pos,c,⋅) with the entries obtained from every transition ((q0,…,qk−1),A.final)∈A.rules(k,c)((q_0, \dots, q_{k-1}), A.\mathrm{final}) \in A.\mathrm{rules}(k, c)((q0​,…,qk−1​),A.final)∈A.rules(k,c) of A=P.rep(ppos)A = P.\mathrm{rep}(p_{\mathrm{pos}})A=P.rep(ppos​) by splicing the rerooted basic functions (A.reroot(q0)).basic,…,(A.reroot(qk−1)).basic(A.\mathrm{reroot}(q_0)).\mathrm{basic}, \dots, (A.\mathrm{reroot}(q_{k-1})).\mathrm{basic}(A.reroot(q0​)).basic,…,(A.reroot(qk−1​)).basic in place of pposp_{\mathrm{pos}}ppos​ with weight qqq, until the pattern list equals [var(vars[0]),…,var(vars[L−1])][\mathsf{var}(\mathrm{vars}[0]), \dots, \mathsf{var}(\mathrm{vars}[L-1])][var(vars[0]),…,var(vars[L−1])];
    • If μ=counted\mu = \mathsf{counted}μ=counted, then annotationEq(addConstant(S,P0,1),shifted)\mathsf{annotationEq}(\mathsf{addConstant}(S, P_0, 1), \mathrm{shifted})annotationEq(addConstant(S,P0​,1),shifted), where addConstant(S,P0,1)\mathsf{addConstant}(S, P_0, 1)addConstant(S,P0​,1) prepends the entry (u⃗L,1)(\vec{u}_L, 1)(uL​,1) to P0P_0P0​ with u⃗L\vec{u}_LuL​ being the LLL-tuple of canonical basic functions (induced by the 1-state automaton TreeAutomaton.canonical(S)\mathsf{TreeAutomaton.canonical}(S)TreeAutomaton.canonical(S) that has transition ((0,…,0),0)((0,\dots,0), 0)((0,…,0),0) for every constructor and evaluates to 111 on every value); if μ=costFree\mu = \mathsf{costFree}μ=costFree, then annotationEq(P0,shifted)\mathsf{annotationEq}(P_0, \mathrm{shifted})annotationEq(P0​,shifted);
    • Typing(S,P,F,μ,L,(i↦vars[i]),P0,r.rhs,Qr′)\mathsf{Typing}(S, P, F, \mu, L, (i \mapsto \mathrm{vars}[i]), P_0, r.\mathrm{rhs}, Q'_r)Typing(S,P,F,μ,L,(i↦vars[i]),P0​,r.rhs,Qr′​) holds.
  9. Typing context, term, and derivation (nnn, xs\mathrm{xs}xs, hDistinct\mathrm{hDistinct}hDistinct, QQQ, ttt, Q′Q'Q′, hType\mathrm{hType}hType):
    • n∈Nn \in \mathbb{N}n∈N is an implicit natural number (possibly 000);
    • xs:{0,…,n−1}→N\mathrm{xs} : \{0, \dots, n-1\} \to \mathbb{N}xs:{0,…,n−1}→N is an injective map (hDistinct:∀i,j, xs(i)=xs(j)  ⟹  i=j\mathrm{hDistinct} : \forall i, j,\, \mathrm{xs}(i) = \mathrm{xs}(j) \implies i = jhDistinct:∀i,j,xs(i)=xs(j)⟹i=j) assigning pairwise distinct variable indices to the nnn context positions;
    • Q∈Annotation(C,n)Q \in \mathsf{Annotation}(C, n)Q∈Annotation(C,n) is an nnn-ary input annotation, t∈Term(C,D)t \in \mathsf{Term}(C, D)t∈Term(C,D) is a term, and Q′∈Annotation(C,1)Q' \in \mathsf{Annotation}(C, 1)Q′∈Annotation(C,1) is a 111-ary output annotation;
    • hType:Typing(S,P,F,counted,n,xs,Q,t,Q′)\mathrm{hType} : \mathsf{Typing}(S, P, F, \mathsf{counted}, n, \mathrm{xs}, Q, t, Q')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′)\mathsf{Typing}(S, P, F, \mu, n, \mathrm{xs}, Q, t, Q')Typing(S,P,F,μ,n,xs,Q,t,Q′) specialized to μ=counted\mu = \mathsf{counted}μ=counted. The inductive relation Typing\mathsf{Typing}Typing is generated by 8 rules:
      1. Variable (variable): Types var(x)\mathsf{var}(x)var(x) in context (0↦x)(0 \mapsto x)(0↦x) of length 111 with input annotation QQQ and identical output annotation QQQ.
      2. Defined symbol (defined): For f∈D(k)f \in D(k)f∈D(k) and injective xs:{0,…,k−1}→N\mathrm{xs} : \{0, \dots, k-1\} \to \mathbb{N}xs:{0,…,k−1}→N, if F.get(μ,k,f,Q,Q′)F.\mathrm{get}(\mu, k, f, Q, Q')F.get(μ,k,f,Q,Q′) holds, types func(inr(f),(i↦var(xs(i))))\mathsf{func}(\mathsf{inr}(f), (i \mapsto \mathsf{var}(\mathrm{xs}(i))))func(inr(f),(i↦var(xs(i)))) with input QQQ and output Q′Q'Q′.
      3. Constructor (constructor): For c∈C(k)c \in C(k)c∈C(k), injective xs:{0,…,k−1}→N\mathrm{xs} : \{0, \dots, k-1\} \to \mathbb{N}xs:{0,…,k−1}→N, and Q∈Annotation(C,1)Q \in \mathsf{Annotation}(C, 1)Q∈Annotation(C,1), types func(inl(c),(i↦var(xs(i))))\mathsf{func}(\mathsf{inl}(c), (i \mapsto \mathsf{var}(\mathrm{xs}(i))))func(inl(c),(i↦var(xs(i)))) with input additiveShift(P,c,Q)∈Annotation(C,k)\mathsf{additiveShift}(P, c, Q) \in \mathsf{Annotation}(C, k)additiveShift(P,c,Q)∈Annotation(C,k) (which expands the single coordinate of QQQ along transitions into A.finalA.\mathrm{final}A.final of A=P.rep(p0)A = P.\mathrm{rep}(p_0)A=P.rep(p0​) for rule (k,c)(k, c)(k,c)) and output QQQ.
      4. Annotation weakening (weakenAnnotations): For injective xs\mathrm{xs}xs, weakens input P0P_0P0​ to QQQ and output P′P'P′ to Q′Q'Q′ whenever annotationLe(P0,Q)\mathsf{annotationLe}(P_0, Q)annotationLe(P0​,Q) and annotationLe(Q′,P′)\mathsf{annotationLe}(Q', P')annotationLe(Q′,P′).
      5. Context exchange (exchange): Permutes the context xs\mathrm{xs}xs and annotation coordinates of QQQ along any bijection ρ:{0,…,k−1}→{0,…,k−1}\rho : \{0, \dots, k-1\} \to \{0, \dots, k-1\}ρ:{0,…,k−1}→{0,…,k−1}.
      6. Context weakening (weakenContext): Extends a typing of ttt in context (xs(0),…,xs(k−1))(\mathrm{xs}(0), \dots, \mathrm{xs}(k-1))(xs(0),…,xs(k−1)) under annotationProject(Q,u⃗1)\mathsf{annotationProject}(Q, \vec{u}_1)annotationProject(Q,u1​) (the kkk-ary annotation retaining entries of Q∈Annotation(C,k+1)Q \in \mathsf{Annotation}(C, k+1)Q∈Annotation(C,k+1) whose last coordinate equals the canonical basic function BasicFunction.canonical(S)\mathsf{BasicFunction.canonical}(S)BasicFunction.canonical(S)) to the injective context xs:{0,…,k}→N\mathrm{xs} : \{0, \dots, k\} \to \mathbb{N}xs:{0,…,k}→N under QQQ.
      7. Sharing (share): Given a typing of ttt in an (m+2)(m+2)(m+2)-variable context (xs(0),…,xs(m−1),x,y)(\mathrm{xs}(0), \dots, \mathrm{xs}(m-1), x, y)(xs(0),…,xs(m−1),x,y) under Q∈Annotation(C,m+2)Q \in \mathsf{Annotation}(C, m+2)Q∈Annotation(C,m+2) where xs\mathrm{xs}xs is injective, x≠yx \ne yx=y, x,y,zx, y, zx,y,z are distinct from all xs(i)\mathrm{xs}(i)xs(i), and z∉{x,y}∪t.variablesz \notin \{x, y\} \cup t.\mathrm{variables}z∈/{x,y}∪t.variables, derives a typing of t.rename(v↦if v=x∨v=y then z else v)t.\mathrm{rename}(v \mapsto \text{if } v = x \lor v = y \text{ then } z \text{ else } v)t.rename(v↦if v=x∨v=y then z else v) in context (xs(0),…,xs(m−1),z)(\mathrm{xs}(0), \dots, \mathrm{xs}(m-1), z)(xs(0),…,xs(m−1),z) under annotationShare(S,P,Q)∈Annotation(C,m+1)\mathsf{annotationShare}(S, P, Q) \in \mathsf{Annotation}(C, m+1)annotationShare(S,P,Q)∈Annotation(C,m+1). Here annotationShare(S,P,Q)\mathsf{annotationShare}(S, P, Q)annotationShare(S,P,Q) replaces the last two basic functions (pm,pm+1)(p_m, p_{m+1})(pm​,pm+1​) of each entry in QQQ by their automaton product BasicFunction.product(S,P,pm,pm+1)\mathsf{BasicFunction.product}(S, P, p_m, p_{m+1})BasicFunction.product(S,P,pm​,pm+1​), which is the basic function of TreeAutomaton.product(S,P.rep(pm),P.rep(pm+1))\mathsf{TreeAutomaton.product}(S, P.\mathrm{rep}(p_m), P.\mathrm{rep}(p_{m+1}))TreeAutomaton.product(S,P.rep(pm​),P.rep(pm+1​)) (an automaton with M1M2+1M_1 M_2 + 1M1​M2​+1 states, final state q1finM2+q2finq_1^{\mathrm{fin}} M_2 + q_2^{\mathrm{fin}}q1fin​M2​+q2fin​, and transitions formed by deduplicating all paired transitions of the two automata plus a padding transition ((M1M2,…,M1M2),M1M2)((M_1 M_2, \dots, M_1 M_2), M_1 M_2)((M1​M2​,…,M1​M2​),M1​M2​)).
      8. Composition (composition): For f∈C(ℓ+1)⊕D(ℓ+1)f \in C(\ell+1) \oplus D(\ell+1)f∈C(ℓ+1)⊕D(ℓ+1), argument terms t0,…,tℓt_0, \dots, t_\ellt0​,…,tℓ​, variable lists Γ0,…,Γℓ\Gamma_0, \dots, \Gamma_\ellΓ0​,…,Γℓ​ whose concatenation Γ=Γ0+ ⁣+⋯+ ⁣+Γℓ\Gamma = \Gamma_0 \mathbin{+\!+} \dots \mathbin{+\!+} \Gamma_\ellΓ=Γ0​++⋯++Γℓ​ is duplicate-free with (ti).variables⊆Γi(t_i).\mathrm{variables} \subseteq \Gamma_i(ti​).variables⊆Γi​ for each i≤ℓi \le \elli≤ℓ, and injective fresh variables y0,…,yℓ∉Γ∪⋃j=0ℓ(tj).variablesy_0, \dots, y_\ell \notin \Gamma \cup \bigcup_{j=0}^\ell (t_j).\mathrm{variables}y0​,…,yℓ​∈/Γ∪⋃j=0ℓ​(tj​).variables, combines a mode-μ\muμ typing of func(f,(i↦var(yi)))\mathsf{func}(f, (i \mapsto \mathsf{var}(y_i)))func(f,(i↦var(yi​))) under S′∈Annotation(C,ℓ+1)S' \in \mathsf{Annotation}(C, \ell+1)S′∈Annotation(C,ℓ+1) and output Q′Q'Q′ with family typings of each tit_iti​ in context Γi\Gamma_iΓi​ under input Parg(i,ι⃗)P_{\mathrm{arg}}(i, \vec{\iota})Parg​(i,ι) and output Rarg(i,ι⃗)R_{\mathrm{arg}}(i, \vec{\iota})Rarg​(i,ι) (typed in mode listPremiseMode(S,μ,ι⃗)\mathsf{listPremiseMode}(S, \mu, \vec{\iota})listPremiseMode(S,μ,ι), which is counted\mathsf{counted}counted if μ=counted\mu = \mathsf{counted}μ=counted and every basic function in ι⃗\vec{\iota}ι is BasicFunction.canonical(S)\mathsf{BasicFunction.canonical}(S)BasicFunction.canonical(S), and costFree\mathsf{costFree}costFree otherwise) for all index lists ι⃗\vec{\iota}ι of length i+∑k=i+1ℓ∣Γk∣i + \sum_{k=i+1}^\ell |\Gamma_k|i+∑k=i+1ℓ​∣Γk​∣, provided Q,S′,Parg,RargQ, S', P_{\mathrm{arg}}, R_{\mathrm{arg}}Q,S′,Parg​,Rarg​ satisfy the coefficient chaining equations compositionCoefficients\mathsf{compositionCoefficients}compositionCoefficients, to type func(f,(t0,…,tℓ))\mathsf{func}(f, (t_0, \dots, t_\ell))func(f,(t0​,…,tℓ​)) in context Γ\GammaΓ with input QQQ and output Q′Q'Q′.
  10. Substitution, input values, and evaluation (σ\sigmaσ, hNorm\mathrm{hNorm}hNorm, vs\mathrm{vs}vs, hDom\mathrm{hDom}hDom, hSubst\mathrm{hSubst}hSubst, mmm, vvv, hEval\mathrm{hEval}hEval):
    • σ∈Substitution(C,D)\sigma \in \mathsf{Substitution}(C, D)σ∈Substitution(C,D) is a substitution that is normalised (hNorm:∀x∈σ.dom, IsValue(σ.assignment(x))\mathrm{hNorm} : \forall x \in \sigma.\mathrm{dom},\, \mathsf{IsValue}(\sigma.\mathrm{assignment}(x))hNorm:∀x∈σ.dom,IsValue(σ.assignment(x)));
    • vs:{0,…,n−1}→Value(C)\mathrm{vs} : \{0, \dots, n-1\} \to \mathsf{Value}(C)vs:{0,…,n−1}→Value(C) is an nnn-tuple of constructor values such that for every i∈{0,…,n−1}i \in \{0, \dots, n-1\}i∈{0,…,n−1}, xs(i)∈σ.dom\mathrm{xs}(i) \in \sigma.\mathrm{dom}xs(i)∈σ.dom (hDom\mathrm{hDom}hDom) and σ.assignment(xs(i))=(vs(i)).toTerm\sigma.\mathrm{assignment}(\mathrm{xs}(i)) = (\mathrm{vs}(i)).\mathrm{toTerm}σ.assignment(xs(i))=(vs(i)).toTerm (hSubst\mathrm{hSubst}hSubst), where for any w∈Value(C)w \in \mathsf{Value}(C)w∈Value(C), w.toTerm∈Term(C,D)w.\mathrm{toTerm} \in \mathsf{Term}(C, D)w.toTerm∈Term(C,D) is the ground constructor term obtained by replacing every node(c,… )\mathsf{node}(c, \dots)node(c,…) by func(inl(c),… )\mathsf{func}(\mathsf{inl}(c), \dots)func(inl(c),…);
    • m∈Nm \in \mathbb{N}m∈N is a natural number step cost and v∈Value(C)v \in \mathsf{Value}(C)v∈Value(C) is an output constructor value;
    • hEval:Evaluates(R,σ,t,m,v.toTerm)\mathrm{hEval} : \mathsf{Evaluates}(R, \sigma, t, m, v.\mathrm{toTerm})hEval:Evaluates(R,σ,t,m,v.toTerm) states that ttt evaluates under σ\sigmaσ and RRR in cost mmm to v.toTermv.\mathrm{toTerm}v.toTerm, according to the 4-rule inductive big-step operational semantics Evaluates\mathsf{Evaluates}Evaluates:
      1. Variable (var): If x∈σ.domx \in \sigma.\mathrm{dom}x∈σ.dom and σ.assignment(x)=w\sigma.\mathrm{assignment}(x) = wσ.assignment(x)=w, then var(x)\mathsf{var}(x)var(x) evaluates under σ\sigmaσ in cost 000 to www.
      2. Constructor (constructor): For c∈C(k)c \in C(k)c∈C(k), if yi∈σ.domy_i \in \sigma.\mathrm{dom}yi​∈σ.dom and σ.assignment(yi)=wi\sigma.\mathrm{assignment}(y_i) = w_iσ.assignment(yi​)=wi​ for all i∈{0,…,k−1}i \in \{0, \dots, k-1\}i∈{0,…,k−1}, then func(inl(c),(i↦var(yi)))\mathsf{func}(\mathsf{inl}(c), (i \mapsto \mathsf{var}(y_i)))func(inl(c),(i↦var(yi​))) evaluates under σ\sigmaσ in cost 000 to func(inl(c),(w0,…,wk−1))\mathsf{func}(\mathsf{inl}(c), (w_0, \dots, w_{k-1}))func(inl(c),(w0​,…,wk−1​)).
      3. Rewrite (rewrite): For f∈D(k)f \in D(k)f∈D(k), if rrr is a rule with R(r)R(r)R(r), r.arity=kr.\mathrm{arity} = kr.arity=k, and r.symbol=fr.\mathrm{symbol} = fr.symbol=f, ρ:N→N\rho : \mathbb{N} \to \mathbb{N}ρ:N→N is injective, τ\tauτ is a normalised substitution whose domain is disjoint from σ.dom\sigma.\mathrm{dom}σ.dom (∀x∈σ.dom, x∉τ.dom\forall x \in \sigma.\mathrm{dom},\, x \notin \tau.\mathrm{dom}∀x∈σ.dom,x∈/τ.dom), yi∈σ.domy_i \in \sigma.\mathrm{dom}yi​∈σ.dom and σ.assignment(yi)=τ.instantiate((r.patterns(i)).rename(ρ))\sigma.\mathrm{assignment}(y_i) = \tau.\mathrm{instantiate}((r.\mathrm{patterns}(i)).\mathrm{rename}(\rho))σ.assignment(yi​)=τ.instantiate((r.patterns(i)).rename(ρ)) for all i∈{0,…,k−1}i \in \{0, \dots, k-1\}i∈{0,…,k−1}, and r.rhs.rename(ρ)r.\mathrm{rhs}.\mathrm{rename}(\rho)r.rhs.rename(ρ) evaluates under the left-biased union substitution σ∪τ\sigma \cup \tauσ∪τ in cost m0m_0m0​ to www, then func(inr(f),(i↦var(yi)))\mathsf{func}(\mathsf{inr}(f), (i \mapsto \mathsf{var}(y_i)))func(inr(f),(i↦var(yi​))) evaluates under σ\sigmaσ in cost m0+1m_0 + 1m0​+1 to www.
      4. Composition (composition): For f∈C(k)⊕D(k)f \in C(k) \oplus D(k)f∈C(k)⊕D(k), argument terms s0,…,sk−1s_0, \dots, s_{k-1}s0​,…,sk−1​, and injective variables y0,…,yk−1y_0, \dots, y_{k-1}y0​,…,yk−1​ such that yi∉σ.domy_i \notin \sigma.\mathrm{dom}yi​∈/σ.dom and yi∉(sj).variablesy_i \notin (s_j).\mathrm{variables}yi​∈/(sj​).variables for all i,ji, ji,j, if each sis_isi​ evaluates under σ\sigmaσ in cost cic_ici​ to wiw_iwi​ and func(f,(i↦var(yi)))\mathsf{func}(f, (i \mapsto \mathsf{var}(y_i)))func(f,(i↦var(yi​))) evaluates under σ∪[y0↦w0,…,yk−1↦wk−1]\sigma \cup [y_0 \mapsto w_0, \dots, y_{k-1} \mapsto w_{k-1}]σ∪[y0​↦w0​,…,yk−1​↦wk−1​] in cost coutc_{\mathrm{out}}cout​ to www, then func(f,(s0,…,sk−1))\mathsf{func}(f, (s_0, \dots, s_{k-1}))func(f,(s0​,…,sk−1​)) evaluates under σ\sigmaσ in cost cout+∑i=0k−1cic_{\mathrm{out}} + \sum_{i=0}^{k-1} c_icout​+∑i=0k−1​ci​ to www.

Conclusion: Under all the above hypotheses, the rational potential difference satisfies the inequality

potential(Q,vs)−potential(Q′,(0↦v))≥(m:Q),\mathsf{potential}(Q, \mathrm{vs}) - \mathsf{potential}(Q', (0 \mapsto v)) \ge (m : \mathbb{Q}),potential(Q,vs)−potential(Q′,(0↦v))≥(m:Q),

where for any k∈Nk \in \mathbb{N}k∈N, annotation A∈Annotation(C,k)A \in \mathsf{Annotation}(C, k)A∈Annotation(C,k), and value tuple w⃗:{0,…,k−1}→Value(C)\vec{w} : \{0, \dots, k-1\} \to \mathsf{Value}(C)w:{0,…,k−1}→Value(C), the potential is the rational number

potential(A,w⃗)=∑((p0,…,pk−1),q)∈Aq⋅(∏i=0k−1pi(wi))∈Q,\mathsf{potential}(A, \vec{w}) = \sum_{((p_0, \dots, p_{k-1}), q) \in A} q \cdot \left(\prod_{i=0}^{k-1} p_i(w_i)\right) \in \mathbb{Q},potential(A,w)=((p0​,…,pk−1​),q)∈A∑​q⋅(i=0∏k−1​pi​(wi​))∈Q,

(0↦v):{0}→Value(C)(0 \mapsto v) : \{0\} \to \mathsf{Value}(C)(0↦v):{0}→Value(C) is the singleton tuple with entry vvv, and the subtraction and ≥\ge≥ comparison take place in Q\mathbb{Q}Q.

Edge cases and boundary conditions:

  • The context length n=0n = 0n=0 and evaluation cost m=0m = 0m=0 are included in the universal quantifiers. When n=0n = 0n=0, the product ∏i=0n−1pi(vs(i))\prod_{i=0}^{n-1} p_i(\mathrm{vs}(i))∏i=0n−1​pi​(vs(i)) is the empty product 111, so potential(Q,vs)\mathsf{potential}(Q, \mathrm{vs})potential(Q,vs) is the sum of rational weights in QQQ; when an annotation list is empty, its potential is 0∈Q0 \in \mathbb{Q}0∈Q.
  • The substitution domain σ.dom\sigma.\mathrm{dom}σ.dom is only required to contain {xs(0),…,xs(n−1)}\{\mathrm{xs}(0), \dots, \mathrm{xs}(n-1)\}{xs(0),…,xs(n−1)}; it may contain additional variable indices outside the image of xs\mathrm{xs}xs (whose assigned terms must also be values by hNorm\mathrm{hNorm}hNorm) as well as duplicate entries in σ.dom\sigma.\mathrm{dom}σ.dom, while values of σ.assignment(x)\sigma.\mathrm{assignment}(x)σ.assignment(x) for x∉σ.domx \notin \sigma.\mathrm{dom}x∈/σ.dom are unconstrained.
  • The ambient assumptions hFinSig\mathrm{hFinSig}hFinSig, hFinSys\mathrm{hFinSys}hFinSys, hOrth\mathrm{hOrth}hOrth, hCompDef\mathrm{hCompDef}hCompDef, hExtCounted\mathrm{hExtCounted}hExtCounted, and hExtCostFree\mathrm{hExtCostFree}hExtCostFree are global hypotheses on C,D,R,FC, D, R, FC,D,R,F alongside the explicit derivation hypotheses hType\mathrm{hType}hType and hEval\mathrm{hEval}hEval.
Human review
  • Endorsed by Shuze Chen · Oct 28, 2026

    Confirmed by the moderator at approval.

  • Endorsed by kmehltretter82 · Oct 28, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me