Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 13: Potential preservation under the variable-sharing operator Υ\UpsilonΥ

Proved
HofmannMoser.lemma_13

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

amortized-analysiscomplexityterm-rewritingtree-automatatype-systems

This is Lemma 13 of Hofmann and Moser (TLCA 2015, p. 249), establishing that the variable-sharing operator Υ\UpsilonΥ preserves potential when the last two coordinates of a value tuple are equal.

Let SSS be a finite nonempty constructor signature (FiniteConstructors C), let PPP be a representative policy (RepPolicy C), let QQQ be a resource annotation of length m+2m + 2m+2 (Annotation C (m + 2)), let w1,…,wmw_1, \dots, w_mw1​,…,wm​ (ws : Fin m → Value C) be prefix values, and let vvv (Value C) be a shared ground constructor value. Then

Φ(w1,…,wm,v,v:Q)=Φ(w1,…,wm,v:Υ(Q)),\Phi(w_1, \dots, w_m, v, v : Q) = \Phi(w_1, \dots, w_m, v : \Upsilon(Q)),Φ(w1​,…,wm​,v,v:Q)=Φ(w1​,…,wm​,v:Υ(Q)),

where Υ(Q)\Upsilon(Q)Υ(Q) (annotationShare S P Q) replaces the last two basic functions of each entry in QQQ 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 uC : \mathbb{N} \to \text{Type } uC:N→Type u be an arity-indexed family of constructor symbol types in universe uuu, and let m∈Nm \in \mathbb{N}m∈N be a natural number. 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 ∃n∈N,Nonempty(C(n))\exists n \in \mathbb{N}, \text{Nonempty}(C(n))∃n∈N,Nonempty(C(n));
  • P:RepPolicy(C)P : \text{RepPolicy}(C)P:RepPolicy(C), a representation policy assigning to each basic function p∈BasicFunction(C)p \in \text{BasicFunction}(C)p∈BasicFunction(C) a tree automaton P.rep(p):TreeAutomaton(C)P.\text{rep}(p) : \text{TreeAutomaton}(C)P.rep(p):TreeAutomaton(C) such that (P.rep(p)).basic=p(P.\text{rep}(p)).\text{basic} = p(P.rep(p)).basic=p;
  • an (m+2)(m+2)(m+2)-ary annotation Q:Annotation(C,m+2)Q : \text{Annotation}(C, m+2)Q:Annotation(C,m+2);
  • an mmm-tuple of values w⃗=(w0,…,wm−1):{0,…,m−1}→Value(C)\vec{w} = (w_0, \dots, w_{m-1}) : \{0, \dots, m-1\} \to \text{Value}(C)w=(w0​,…,wm−1​):{0,…,m−1}→Value(C);
  • a value v∈Value(C)v \in \text{Value}(C)v∈Value(C).

Here, the constituent definitions unfold as follows:

  1. Value(C)\text{Value}(C)Value(C) is the inductive type of finite constructor trees node(c,(u0,…,un−1))\text{node}(c, (u_0, \dots, u_{n-1}))node(c,(u0​,…,un−1​)).
  2. A tree automaton A:TreeAutomaton(C)A : \text{TreeAutomaton}(C)A:TreeAutomaton(C) has state space {0,…,A.stateCount−1}\{0, \dots, A.\text{stateCount}-1\}{0,…,A.stateCount−1}, a final state A.finalA.\text{final}A.final, and duplicate-free finite transition lists A.rules(n,c)⊆{0,…,A.stateCount−1}n×{0,…,A.stateCount−1}A.\text{rules}(n, c) \subseteq \{0, \dots, A.\text{stateCount}-1\}^n \times \{0, \dots, A.\text{stateCount}-1\}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.\text{basic}(u) = \text{runCount}(A, u, A.\text{final})A.basic(u)=runCount(A,u,A.final). A basic function p∈BasicFunction(C)p \in \text{BasicFunction}(C)p∈BasicFunction(C) is a function Value(C)→N\text{Value}(C) \to \mathbb{N}Value(C)→N equal to A.basicA.\text{basic}A.basic for some tree automaton AAA.
  3. Given two tree automata A,B:TreeAutomaton(C)A, B : \text{TreeAutomaton}(C)A,B:TreeAutomaton(C) with state counts a=A.stateCounta = A.\text{stateCount}a=A.stateCount and b=B.stateCountb = B.\text{stateCount}b=B.stateCount, their product automaton TreeAutomaton.product(S,A,B)\text{TreeAutomaton.product}(S, A, B)TreeAutomaton.product(S,A,B) has:
    • state count a⋅b+1a \cdot b + 1a⋅b+1, where pairs of states (i,j)∈{0,…,a−1}×{0,…,b−1}(i, j) \in \{0, \dots, a-1\} \times \{0, \dots, b-1\}(i,j)∈{0,…,a−1}×{0,…,b−1} are encoded via productState(i,j)=i⋅b+j∈{0,…,a⋅b}\text{productState}(i, j) = i \cdot b + j \in \{0, \dots, a \cdot b\}productState(i,j)=i⋅b+j∈{0,…,a⋅b} and the extra state a⋅ba \cdot ba⋅b serves as a padding state;
    • final state productState(A.final,B.final)=A.final⋅b+B.final\text{productState}(A.\text{final}, B.\text{final}) = A.\text{final} \cdot b + B.\text{final}productState(A.final,B.final)=A.final⋅b+B.final;
    • for each n∈Nn \in \mathbb{N}n∈N and c∈C(n)c \in C(n)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′))\Big(\big(k \mapsto \text{productState}(q_k, r_k)\big), \text{productState}(q', r')\Big)((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)p_1, p_2 \in \text{BasicFunction}(C)p1​,p2​∈BasicFunction(C), BasicFunction.product(S,P,p1,p2)∈BasicFunction(C)\text{BasicFunction.product}(S, P, p_1, p_2) \in \text{BasicFunction}(C)BasicFunction.product(S,P,p1​,p2​)∈BasicFunction(C) is the basic function of TreeAutomaton.product(S,P.rep(p1),P.rep(p2))\text{TreeAutomaton.product}(S, P.\text{rep}(p_1), P.\text{rep}(p_2))TreeAutomaton.product(S,P.rep(p1​),P.rep(p2​)). 4. For any k∈Nk \in \mathbb{N}k∈N, a kkk-ary annotation Q′:Annotation(C,k)Q' : \text{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):{0,…,k−1}→BasicFunction(C)\vec{p} = (p_0, \dots, p_{k-1}) : \{0, \dots, k-1\} \to \text{BasicFunction}(C)p​=(p0​,…,pk−1​):{0,…,k−1}→BasicFunction(C) and q∈Qq \in \mathbb{Q}q∈Q with q≥0q \ge 0q≥0. Its potential at u⃗=(u0,…,uk−1)\vec{u} = (u_0, \dots, u_{k-1})u=(u0​,…,uk−1​) is

potential(Q′,u⃗)=∑(p⃗,q)∈Q′q⋅(∏i=0k−1pi(ui))∈Q.\text{potential}(Q', \vec{u}) = \sum_{(\vec{p}, q) \in Q'} q \cdot \left(\prod_{i=0}^{k-1} p_i(u_i)\right) \in \mathbb{Q}.potential(Q′,u)=(p​,q)∈Q′∑​q⋅(i=0∏k−1​pi​(ui​))∈Q.
  1. The shared annotation annotationShare(S,P,Q):Annotation(C,m+1)\text{annotationShare}(S, P, Q) : \text{Annotation}(C, m+1)annotationShare(S,P,Q):Annotation(C,m+1) is obtained by mapping each entry (p⃗,q)∈Q(\vec{p}, q) \in Q(p​,q)∈Q, where p⃗=(p0,…,pm−1,pm,pm+1):{0,…,m+1}→BasicFunction(C)\vec{p} = (p_0, \dots, p_{m-1}, p_m, p_{m+1}) : \{0, \dots, m+1\} \to \text{BasicFunction}(C)p​=(p0​,…,pm−1​,pm​,pm+1​):{0,…,m+1}→BasicFunction(C), to the entry
((p0,…,pm−1,BasicFunction.product(S,P,pm,pm+1)),q),\Big(\big(p_0, \dots, p_{m-1}, \text{BasicFunction.product}(S, P, p_m, p_{m+1})\big), q\Big),((p0​,…,pm−1​,BasicFunction.product(S,P,pm​,pm+1​)),q),

which keeps the first mmm basic functions and the weight qqq unchanged and replaces the last two basic functions pm,pm+1p_m, p_{m+1}pm​,pm+1​ by their product BasicFunction.product(S,P,pm,pm+1)\text{BasicFunction.product}(S, P, p_m, p_{m+1})BasicFunction.product(S,P,pm​,pm+1​) at coordinate mmm.

This theorem asserts the equality in Q\mathbb{Q}Q:

potential(Q,(w0,…,wm−1,v,v))=potential(annotationShare(S,P,Q),(w0,…,wm−1,v)),\text{potential}\big(Q, (w_0, \dots, w_{m-1}, v, v)\big) = \text{potential}\big(\text{annotationShare}(S, P, Q), (w_0, \dots, w_{m-1}, v)\big),potential(Q,(w0​,…,wm−1​,v,v))=potential(annotationShare(S,P,Q),(w0​,…,wm−1​,v)),

where (w0,…,wm−1,v,v):{0,…,m+1}→Value(C)(w_0, \dots, w_{m-1}, v, v) : \{0, \dots, m+1\} \to \text{Value}(C)(w0​,…,wm−1​,v,v):{0,…,m+1}→Value(C) and (w0,…,wm−1,v):{0,…,m}→Value(C)(w_0, \dots, w_{m-1}, v) : \{0, \dots, m\} \to \text{Value}(C)(w0​,…,wm−1​,v):{0,…,m}→Value(C) are constructed via Fin.addCases\text{Fin.addCases}Fin.addCases by appending to w⃗\vec{w}w the constant 222-tuple (v,v)(v, v)(v,v) on the left-hand side and the constant 111-tuple (v)(v)(v) on the right-hand side.

Edge and degenerate cases:

  • When m=0m = 0m=0, w⃗\vec{w}w is the unique empty tuple on Fin 0\text{Fin } 0Fin 0; the left-hand side evaluates the binary annotation Q:Annotation(C,2)Q : \text{Annotation}(C, 2)Q:Annotation(C,2) on (v,v)(v, v)(v,v), and the right-hand side evaluates the unary annotation annotationShare(S,P,Q):Annotation(C,1)\text{annotationShare}(S, P, Q) : \text{Annotation}(C, 1)annotationShare(S,P,Q):Annotation(C,1) on (v)(v)(v).
  • When Q=[]Q = []Q=[], annotationShare(S,P,Q)=[]\text{annotationShare}(S, P, Q) = []annotationShare(S,P,Q)=[] and both potentials equal 0∈Q0 \in \mathbb{Q}0∈Q.
  • Duplicate entries in QQQ are preserved one-for-one by List.map in annotationShare(S,P,Q)\text{annotationShare}(S, P, Q)annotationShare(S,P,Q) and summed with multiplicity.
  • The construction of annotationShare(S,P,Q)\text{annotationShare}(S, P, Q)annotationShare(S,P,Q) depends on both S:FiniteConstructors(C)S : \text{FiniteConstructors}(C)S:FiniteConstructors(C) and P:RepPolicy(C)P : \text{RepPolicy}(C)P:RepPolicy(C) to build the underlying product automata, and the equality of potentials holds for any choice of SSS and PPP.
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