This is Lemma 7 of Hofmann and Moser (TLCA 2015, p. 247), establishing that the class RF of unary resource functions is closed under pointwise addition and pointwise multiplication.
Let S be a finite nonempty constructor signature (FiniteConstructors C), and let r,r′:Value C→Q be unary resource functions (IsResourceFunction C r and IsResourceFunction C r', meaning each is the potential of a length-1 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.
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 u be an arity-indexed family of constructor symbol types in universe u. Suppose we are given:
S:FiniteConstructors(C), a structure consisting of a finite list symbols of dependent pairs (n,c)∈∑n∈NC(n) containing every constructor c∈C(n) for every n∈N, together with a proof that there exists some n∈N for which C(n) is nonempty;
two rational-valued functions r,r′:Value(C)→Q defined on the inductive type Value(C) of finite constructor trees node(c,(v0,…,vn−1));
proofs hr:IsResourceFunction(C,r) and hr’:IsResourceFunction(C,r′) that r and r′ are resource functions over C.
Here, the predicate IsResourceFunction(C,f) for a function f:Value(C)→Q is defined through the following chain of notions:
A tree automatonA:TreeAutomaton(C) has a state count K=A.stateCount∈N, a final state A.final∈{0,…,K−1}, and duplicate-free finite transition lists A.rules(n,c)⊆{0,…,K−1}n×{0,…,K−1} supported on finitely many (n,c) and nonempty for at least one (n,c). Its basic functionA.basic:Value(C)→N maps v to runCount(A,v,A.final), where
A basic functionp∈BasicFunction(C) is a function p:Value(C)→N paired with an existential proof that p=A.basic for some tree automaton A:TreeAutomaton(C).
For n∈N, an n-ary annotationQ:Annotation(C,n) is a finite list of pairs (p,q), where p=(p0,…,pn−1):{0,…,n−1}→BasicFunction(C) is an n-tuple of basic functions and q∈Q is a non-negative rational coefficient (0≤q).
For an n-ary annotation Q:Annotation(C,n) and an n-tuple of values v=(v0,…,vn−1):{0,…,n−1}→Value(C), the potentialpotential(Q,v)∈Q is the sum over all entries (p,q) in the list Q:
potential(Q,v)=(p,q)∈Q∑q⋅(i=0∏n−1pi(vi)),
where ∏i=0n−1pi(vi)=multivariateBasic(p,v)∈N is computed by a left fold of multiplication starting from 1 and then cast to Q.
5. A function f:Value(C)→Q satisfies IsResourceFunction(C,f) if and only if there exists a unary annotation Q:Annotation(C,1) such that for every v∈Value(C),
f(v)=potential(Q,(0↦v))=(p,q)∈Q∑q⋅p0(v).
Under these hypotheses, the theorem asserts the conjunction:
An annotation Q:Annotation(C,1) may be the empty list [] (giving the identically zero function v↦0∈Q) and may contain duplicate basic-function tuples or entries with weight q=0; potential sums over the list with multiplicity.
Since every coefficient q in an annotation satisfies q≥0 and every basic function takes values in N, any function satisfying IsResourceFunction(C,f) takes only non-negative rational values (f(v)≥0 for all v).
The assumption S:FiniteConstructors(C) is not referenced in the definition of IsResourceFunction itself, but is provided as a hypothesis (it is used in TreeAutomaton.product to supply finite support and nonemptiness of constructor rules).
Note that S.nonempty only requires ∃n∈N,Nonempty(C(n)), not Nonempty(C(0)); if C(0) is empty, Value(C) is empty and IsResourceFunction(C,f) holds vacuously for every f:Value(C)→Q via the empty annotation Q=[].
Confirmed by the moderator at approval.