This is Lemma 13 of Hofmann and Moser (TLCA 2015, p. 249), establishing that the variable-sharing operator Υ preserves potential when the last two coordinates of a value tuple are equal.
Let S be a finite nonempty constructor signature (FiniteConstructors C), let P be a representative policy (RepPolicy C), let Q be a resource annotation of length m+2 (Annotation C (m + 2)), let w1,…,wm (ws : Fin m → Value C) be prefix values, and let v (Value C) be a shared ground constructor value. Then
Φ(w1,…,wm,v,v:Q)=Φ(w1,…,wm,v:Υ(Q)),
where Υ(Q) (annotationShare S P Q) replaces the last two basic functions of each entry in Q by their Cartesian-product basic function (BasicFunction.product S P).
Lemma 13 establishes soundness of the structural sharing rule (Typing.share) in Figure 2.
Preamble
import Definitions.Def_HofmannMoser_Potential
universe u
Formal statement
namespace HofmannMoser
theorem lemma_13 {C : Nat → Type u} {m : Nat} (S : FiniteConstructors C)
(P : RepPolicy C) (Q : Annotation C (m + 2))
(ws : Fin m → Value C) (v : Value C) :
potential Q (Fin.addCases ws (fun _ ↦ v)) =
potential (annotationShare S P Q) (Fin.addCases ws (fun _ ↦ 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. 249, Lemma 13
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, and let m∈N be a natural number. 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 ∃n∈N,Nonempty(C(n));
P:RepPolicy(C), a representation policy assigning to each basic function p∈BasicFunction(C) a tree automaton P.rep(p):TreeAutomaton(C) such that (P.rep(p)).basic=p;
an (m+2)-ary annotation Q:Annotation(C,m+2);
an m-tuple of values w=(w0,…,wm−1):{0,…,m−1}→Value(C);
a value v∈Value(C).
Here, the constituent definitions unfold as follows:
Value(C) is the inductive type of finite constructor trees node(c,(u0,…,un−1)).
A tree automatonA:TreeAutomaton(C) has state space {0,…,A.stateCount−1}, a final state A.final, and duplicate-free finite transition lists A.rules(n,c)⊆{0,…,A.stateCount−1}n×{0,…,A.stateCount−1}. Its basic function is A.basic(u)=runCount(A,u,A.final). A basic functionp∈BasicFunction(C) is a function Value(C)→N equal to A.basic for some tree automaton A.
Given two tree automata A,B:TreeAutomaton(C) with state counts a=A.stateCount and b=B.stateCount, their product automatonTreeAutomaton.product(S,A,B) has:
state count a⋅b+1, where pairs of states (i,j)∈{0,…,a−1}×{0,…,b−1} are encoded via productState(i,j)=i⋅b+j∈{0,…,a⋅b} and the extra state a⋅b serves as a padding state;
final state productState(A.final,B.final)=A.final⋅b+B.final;
for each n∈N and c∈C(n), the transition list obtained by deduplicating (dedupFinite) the list productRules A B n c, which consists of all paired transitions
((k↦productState(qk,rk)),productState(q′,r′))
for $((q_0, \dots, q_{n-1}), q') \in A.\text{rules}(n, c)$ and $((r_0, \dots, r_{n-1}), r') \in B.\text{rules}(n, c)$, followed by the padding transition $((k \mapsto a \cdot b), a \cdot b)$.
For two basic functions p1,p2∈BasicFunction(C), BasicFunction.product(S,P,p1,p2)∈BasicFunction(C) is the basic function of TreeAutomaton.product(S,P.rep(p1),P.rep(p2)).
4. For any k∈N, a k-ary annotationQ′:Annotation(C,k) is a finite list of pairs (p,q) where p=(p0,…,pk−1):{0,…,k−1}→BasicFunction(C) and q∈Q with q≥0. Its potential at u=(u0,…,uk−1) is
The shared annotationannotationShare(S,P,Q):Annotation(C,m+1) is obtained by mapping each entry (p,q)∈Q, where p=(p0,…,pm−1,pm,pm+1):{0,…,m+1}→BasicFunction(C), to the entry
which keeps the first m basic functions and the weight q unchanged and replaces the last two basic functions pm,pm+1 by their product BasicFunction.product(S,P,pm,pm+1) at coordinate m.
where (w0,…,wm−1,v,v):{0,…,m+1}→Value(C) and (w0,…,wm−1,v):{0,…,m}→Value(C) are constructed via Fin.addCases by appending to w the constant 2-tuple (v,v) on the left-hand side and the constant 1-tuple (v) on the right-hand side.
Edge and degenerate cases:
When m=0, w is the unique empty tuple on Fin 0; the left-hand side evaluates the binary annotation Q:Annotation(C,2) on (v,v), and the right-hand side evaluates the unary annotation annotationShare(S,P,Q):Annotation(C,1) on (v).
When Q=[], annotationShare(S,P,Q)=[] and both potentials equal 0∈Q.
Duplicate entries in Q are preserved one-for-one by List.map in annotationShare(S,P,Q) and summed with multiplicity.
The construction of annotationShare(S,P,Q) depends on both S:FiniteConstructors(C) and P:RepPolicy(C) to build the underlying product automata, and the equality of potentials holds for any choice of S and P.
Confirmed by the moderator at approval.