Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 7: Closure of resource functions under addition and multiplication

Proved
HofmannMoser.lemma_7

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

amortized-analysiscomplexityterm-rewritingtree-automatatype-systems

This is Lemma 7 of Hofmann and Moser (TLCA 2015, p. 247), establishing that the class RF\mathsf{RF}RF of unary resource functions is closed under pointwise addition and pointwise multiplication.

Let SSS be a finite nonempty constructor signature (FiniteConstructors C), and let r,r′:Value C→Qr, r' : \text{Value } C \to \mathbb{Q}r,r′:Value C→Q be unary resource functions (IsResourceFunction C r and IsResourceFunction C r', meaning each is the potential of a length-111 resource annotation). Then both their pointwise sum and their pointwise product are resource functions:

(v↦r(v)+r′(v))∈RFand(v↦r(v)⋅r′(v))∈RF.(v \mapsto r(v) + r'(v)) \in \mathsf{RF} \quad\text{and}\quad (v \mapsto r(v) \cdot r'(v)) \in \mathsf{RF}.(v↦r(v)+r′(v))∈RFand(v↦r(v)⋅r′(v))∈RF.

Multiplicative closure relies on the Cartesian-product automaton construction (TreeAutomaton.product / BasicFunction.product), which multiplies accepting-run counts on every ground constructor value.

Preamble
import Definitions.Def_HofmannMoser_Potential

universe u
Formal statement
namespace HofmannMoser

theorem lemma_7 {C : Nat → Type u} (S : FiniteConstructors C)
    {r r' : Value C → Rat} (hr : IsResourceFunction C r) (hr' : IsResourceFunction C r') :
    IsResourceFunction C (fun v ↦ r v + r' v) ∧
    IsResourceFunction C (fun v ↦ r v * r' v) := 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 3, p. 247, Lemma 7
Read-back

What the Lean code literally says, in plain math · gemini-2.5-pro

Let C:N→Type uC : \mathbb{N} \to \text{Type } uC:N→Type u be an arity-indexed family of constructor symbol types in universe uuu. Suppose we are given:

  • S:FiniteConstructors(C)S : \text{FiniteConstructors}(C)S:FiniteConstructors(C), a structure consisting of a finite list symbols\text{symbols}symbols of dependent pairs (n,c)∈∑n∈NC(n)(n, c) \in \sum_{n \in \mathbb{N}} C(n)(n,c)∈∑n∈N​C(n) containing every constructor c∈C(n)c \in C(n)c∈C(n) for every n∈Nn \in \mathbb{N}n∈N, together with a proof that there exists some n∈Nn \in \mathbb{N}n∈N for which C(n)C(n)C(n) is nonempty;
  • two rational-valued functions r,r′:Value(C)→Qr, r' : \text{Value}(C) \to \mathbb{Q}r,r′:Value(C)→Q defined on the inductive type Value(C)\text{Value}(C)Value(C) of finite constructor trees node(c,(v0,…,vn−1))\text{node}(c, (v_0, \dots, v_{n-1}))node(c,(v0​,…,vn−1​));
  • proofs hr:IsResourceFunction(C,r)\text{hr} : \text{IsResourceFunction}(C, r)hr:IsResourceFunction(C,r) and hr’:IsResourceFunction(C,r′)\text{hr'} : \text{IsResourceFunction}(C, r')hr’:IsResourceFunction(C,r′) that rrr and r′r'r′ are resource functions over CCC.

Here, the predicate IsResourceFunction(C,f)\text{IsResourceFunction}(C, f)IsResourceFunction(C,f) for a function f:Value(C)→Qf : \text{Value}(C) \to \mathbb{Q}f:Value(C)→Q is defined through the following chain of notions:

  1. A tree automaton A:TreeAutomaton(C)A : \text{TreeAutomaton}(C)A:TreeAutomaton(C) has a state count K=A.stateCount∈NK = A.\text{stateCount} \in \mathbb{N}K=A.stateCount∈N, a final state A.final∈{0,…,K−1}A.\text{final} \in \{0, \dots, K-1\}A.final∈{0,…,K−1}, and duplicate-free finite transition lists A.rules(n,c)⊆{0,…,K−1}n×{0,…,K−1}A.\text{rules}(n, c) \subseteq \{0, \dots, K-1\}^n \times \{0, \dots, K-1\}A.rules(n,c)⊆{0,…,K−1}n×{0,…,K−1} supported on finitely many (n,c)(n, c)(n,c) and nonempty for at least one (n,c)(n, c)(n,c). Its basic function A.basic:Value(C)→NA.\text{basic} : \text{Value}(C) \to \mathbb{N}A.basic:Value(C)→N maps vvv to runCount(A,v,A.final)\text{runCount}(A, v, A.\text{final})runCount(A,v,A.final), where
runCount(A,node(c,(v0,…,vn−1)),q)=∑((q0,…,qn−1),q′)∈A.rules(n,c)q′=q∏i=0n−1runCount(A,vi,qi).\text{runCount}\big(A, \text{node}(c, (v_0, \dots, v_{n-1})), q\big) = \sum_{\substack{((q_0, \dots, q_{n-1}), q') \in A.\text{rules}(n, c) \\ q' = q}} \prod_{i=0}^{n-1} \text{runCount}(A, v_i, q_i).runCount(A,node(c,(v0​,…,vn−1​)),q)=((q0​,…,qn−1​),q′)∈A.rules(n,c)q′=q​∑​i=0∏n−1​runCount(A,vi​,qi​).
  1. A basic function p∈BasicFunction(C)p \in \text{BasicFunction}(C)p∈BasicFunction(C) is a function p:Value(C)→Np : \text{Value}(C) \to \mathbb{N}p:Value(C)→N paired with an existential proof that p=A.basicp = A.\text{basic}p=A.basic for some tree automaton A:TreeAutomaton(C)A : \text{TreeAutomaton}(C)A:TreeAutomaton(C).
  2. For n∈Nn \in \mathbb{N}n∈N, an nnn-ary annotation Q:Annotation(C,n)Q : \text{Annotation}(C, n)Q:Annotation(C,n) is a finite list of pairs (p⃗,q)(\vec{p}, q)(p​,q), where p⃗=(p0,…,pn−1):{0,…,n−1}→BasicFunction(C)\vec{p} = (p_0, \dots, p_{n-1}) : \{0, \dots, n-1\} \to \text{BasicFunction}(C)p​=(p0​,…,pn−1​):{0,…,n−1}→BasicFunction(C) is an nnn-tuple of basic functions and q∈Qq \in \mathbb{Q}q∈Q is a non-negative rational coefficient (0≤q0 \le q0≤q).
  3. For an nnn-ary annotation Q:Annotation(C,n)Q : \text{Annotation}(C, n)Q:Annotation(C,n) and an nnn-tuple of values v⃗=(v0,…,vn−1):{0,…,n−1}→Value(C)\vec{v} = (v_0, \dots, v_{n-1}) : \{0, \dots, n-1\} \to \text{Value}(C)v=(v0​,…,vn−1​):{0,…,n−1}→Value(C), the potential potential(Q,v⃗)∈Q\text{potential}(Q, \vec{v}) \in \mathbb{Q}potential(Q,v)∈Q is the sum over all entries (p⃗,q)(\vec{p}, q)(p​,q) in the list QQQ:
potential(Q,v⃗)=∑(p⃗,q)∈Qq⋅(∏i=0n−1pi(vi)),\text{potential}(Q, \vec{v}) = \sum_{(\vec{p}, q) \in Q} q \cdot \left(\prod_{i=0}^{n-1} p_i(v_i)\right),potential(Q,v)=(p​,q)∈Q∑​q⋅(i=0∏n−1​pi​(vi​)),

where ∏i=0n−1pi(vi)=multivariateBasic(p⃗,v⃗)∈N\prod_{i=0}^{n-1} p_i(v_i) = \text{multivariateBasic}(\vec{p}, \vec{v}) \in \mathbb{N}∏i=0n−1​pi​(vi​)=multivariateBasic(p​,v)∈N is computed by a left fold of multiplication starting from 111 and then cast to Q\mathbb{Q}Q. 5. A function f:Value(C)→Qf : \text{Value}(C) \to \mathbb{Q}f:Value(C)→Q satisfies IsResourceFunction(C,f)\text{IsResourceFunction}(C, f)IsResourceFunction(C,f) if and only if there exists a unary annotation Q:Annotation(C,1)Q : \text{Annotation}(C, 1)Q:Annotation(C,1) such that for every v∈Value(C)v \in \text{Value}(C)v∈Value(C),

f(v)=potential(Q,(0↦v))=∑(p⃗,q)∈Qq⋅p0(v).f(v) = \text{potential}(Q, (0 \mapsto v)) = \sum_{(\vec{p}, q) \in Q} q \cdot p_0(v).f(v)=potential(Q,(0↦v))=(p​,q)∈Q∑​q⋅p0​(v).

Under these hypotheses, the theorem asserts the conjunction:

IsResourceFunction(C,v↦r(v)+r′(v))  ∧  IsResourceFunction(C,v↦r(v)⋅r′(v)).\text{IsResourceFunction}\big(C, v \mapsto r(v) + r'(v)\big) \;\wedge\; \text{IsResourceFunction}\big(C, v \mapsto r(v) \cdot r'(v)\big).IsResourceFunction(C,v↦r(v)+r′(v))∧IsResourceFunction(C,v↦r(v)⋅r′(v)).

Edge and degenerate cases:

  • An annotation Q:Annotation(C,1)Q : \text{Annotation}(C, 1)Q:Annotation(C,1) may be the empty list [][][] (giving the identically zero function v↦0∈Qv \mapsto 0 \in \mathbb{Q}v↦0∈Q) and may contain duplicate basic-function tuples or entries with weight q=0q = 0q=0; potential sums over the list with multiplicity.
  • Since every coefficient qqq in an annotation satisfies q≥0q \ge 0q≥0 and every basic function takes values in N\mathbb{N}N, any function satisfying IsResourceFunction(C,f)\text{IsResourceFunction}(C, f)IsResourceFunction(C,f) takes only non-negative rational values (f(v)≥0f(v) \ge 0f(v)≥0 for all vvv).
  • The assumption S:FiniteConstructors(C)S : \text{FiniteConstructors}(C)S:FiniteConstructors(C) is not referenced in the definition of IsResourceFunction\text{IsResourceFunction}IsResourceFunction itself, but is provided as a hypothesis (it is used in TreeAutomaton.product\text{TreeAutomaton.product}TreeAutomaton.product to supply finite support and nonemptiness of constructor rules).
  • Note that S.nonemptyS.\text{nonempty}S.nonempty only requires ∃n∈N,Nonempty(C(n))\exists n \in \mathbb{N}, \text{Nonempty}(C(n))∃n∈N,Nonempty(C(n)), not Nonempty(C(0))\text{Nonempty}(C(0))Nonempty(C(0)); if C(0)C(0)C(0) is empty, Value(C)\text{Value}(C)Value(C) is empty and IsResourceFunction(C,f)\text{IsResourceFunction}(C, f)IsResourceFunction(C,f) holds vacuously for every f:Value(C)→Qf : \text{Value}(C) \to \mathbb{Q}f:Value(C)→Q via the empty annotation Q=[]Q = []Q=[].
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