Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 12: Potential preservation under the additive constructor shift ◃c\triangleleft_c◃c​

Proved
HofmannMoser.lemma_12

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

amortized-analysiscomplexityterm-rewritingtree-automatatype-systems

This is Lemma 12 of Hofmann and Moser (TLCA 2015, p. 248), proving that the additive constructor shift ◃c\triangleleft_c◃c​ preserves potential exactly when a constructor term c(v1,…,vn)c(v_1, \dots, v_n)c(v1​,…,vn​) is decomposed into its arguments v1,…,vnv_1, \dots, v_nv1​,…,vn​.

Let PPP be a representative policy (RepPolicy C), let c∈Cnc \in \mathcal{C}_nc∈Cn​ be an nnn-ary constructor, let QQQ be a resource annotation of length m+1m + 1m+1 (Annotation C (m + 1)), and let w1,…,wmw_1, \dots, w_mw1​,…,wm​ (ws : Fin m → Value C) and v1,…,vnv_1, \dots, v_nv1​,…,vn​ (vs : Fin n → Value C) be ground constructor values. Then

Φ(w1,…,wm,c(v1,…,vn):Q)=Φ(w1,…,wm,v1,…,vn:◃c(Q)).\Phi(w_1, \dots, w_m, c(v_1, \dots, v_n) : Q) = \Phi(w_1, \dots, w_m, v_1, \dots, v_n : \triangleleft_c(Q)).Φ(w1​,…,wm​,c(v1​,…,vn​):Q)=Φ(w1​,…,wm​,v1​,…,vn​:◃c​(Q)).

Lemma 12 is the fundamental algebraic identity behind both the constructor introduction rule (Typing.constructor) and the left-hand-side pattern expansion of rewrite rules (PatternExpansion, Definition 15).

Formalization Note The tuple (w1,…,wm,c(v1,…,vn))(w_1, \dots, w_m, c(v_1, \dots, v_n))(w1​,…,wm​,c(v1​,…,vn​)) of length m+1m + 1m+1 is represented by Fin.addCases ws (fun _ ↦ Value.node c vs), and the tuple (w1,…,wm,v1,…,vn)(w_1, \dots, w_m, v_1, \dots, v_n)(w1​,…,wm​,v1​,…,vn​) of length m+nm + nm+n by Fin.addCases ws vs.

Preamble
import Definitions.Def_HofmannMoser_Potential

universe u
Formal statement
namespace HofmannMoser

theorem lemma_12 {C : Nat → Type u} {m n : Nat} (P : RepPolicy C)
    (c : C n) (Q : Annotation C (m + 1))
    (ws : Fin m → Value C) (vs : Fin n → Value C) :
    potential Q (Fin.addCases ws (fun _ ↦ Value.node c vs)) =
      potential (additiveShift P c Q) (Fin.addCases ws vs) := 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. 248, Lemma 12
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,n∈Nm, n \in \mathbb{N}m,n∈N be natural numbers. Suppose we are given:

  • P:RepPolicy(C)P : \text{RepPolicy}(C)P:RepPolicy(C), a representation policy consisting of a function P.rep:BasicFunction(C)→TreeAutomaton(C)P.\text{rep} : \text{BasicFunction}(C) \to \text{TreeAutomaton}(C)P.rep:BasicFunction(C)→TreeAutomaton(C) that assigns a concrete tree automaton to each basic function p∈BasicFunction(C)p \in \text{BasicFunction}(C)p∈BasicFunction(C), together with a proof P.rep_basicP.\text{rep\_basic}P.rep_basic that (P.rep(p)).basic=p(P.\text{rep}(p)).\text{basic} = p(P.rep(p)).basic=p for every p∈BasicFunction(C)p \in \text{BasicFunction}(C)p∈BasicFunction(C);
  • a constructor symbol c∈C(n)c \in C(n)c∈C(n) of arity nnn;
  • an (m+1)(m+1)(m+1)-ary annotation Q:Annotation(C,m+1)Q : \text{Annotation}(C, m+1)Q:Annotation(C,m+1);
  • 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);
  • 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).

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,…,uk−1))\text{node}(c', (u_0, \dots, u_{k-1}))node(c′,(u0​,…,uk−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(k,c′)⊆{0,…,A.stateCount−1}k×{0,…,A.stateCount−1}A.\text{rules}(k, c') \subseteq \{0, \dots, A.\text{stateCount}-1\}^k \times \{0, \dots, A.\text{stateCount}-1\}A.rules(k,c′)⊆{0,…,A.stateCount−1}k×{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), and for any state qqq, A.reroot(q)A.\text{reroot}(q)A.reroot(q) is the same automaton with final state changed to qqq. 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; BasicFunction.reroot(A,q)∈BasicFunction(C)\text{BasicFunction.reroot}(A, q) \in \text{BasicFunction}(C)BasicFunction.reroot(A,q)∈BasicFunction(C) is the basic function (A.reroot(q)).basic(A.\text{reroot}(q)).\text{basic}(A.reroot(q)).basic.
  3. 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 a kkk-tuple of values 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. For each (m+1)(m+1)(m+1)-tuple of basic functions p⃗=(p0,…,pm−1,pm):{0,…,m}→BasicFunction(C)\vec{p} = (p_0, \dots, p_{m-1}, p_m) : \{0, \dots, m\} \to \text{BasicFunction}(C)p​=(p0​,…,pm−1​,pm​):{0,…,m}→BasicFunction(C), let A=P.rep(pm)A = P.\text{rep}(p_m)A=P.rep(pm​) be the representative automaton chosen by PPP for the last coordinate pmp_mpm​. The list shiftTuples(P,c,p⃗)\text{shiftTuples}(P, c, \vec{p})shiftTuples(P,c,p​) is formed by filtering A.rules(n,c)A.\text{rules}(n, c)A.rules(n,c) to those transitions tr=((q0,…,qn−1),q′)\text{tr} = ((q_0, \dots, q_{n-1}), q')tr=((q0​,…,qn−1​),q′) with q′=A.finalq' = A.\text{final}q′=A.final, and mapping each such transition to the concatenated (m+n)(m+n)(m+n)-tuple of basic functions
(p0,…,pm−1,BasicFunction.reroot(A,q0),…,BasicFunction.reroot(A,qn−1)).\big(p_0, \dots, p_{m-1}, \text{BasicFunction.reroot}(A, q_0), \dots, \text{BasicFunction.reroot}(A, q_{n-1})\big).(p0​,…,pm−1​,BasicFunction.reroot(A,q0​),…,BasicFunction.reroot(A,qn−1​)).
  1. The additive shift additiveShift(P,c,Q):Annotation(C,m+n)\text{additiveShift}(P, c, Q) : \text{Annotation}(C, m+n)additiveShift(P,c,Q):Annotation(C,m+n) is obtained by flat-mapping over all entries (p⃗,q)∈Q(\vec{p}, q) \in Q(p​,q)∈Q: each entry (p⃗,q)(\vec{p}, q)(p​,q) is replaced by all pairs (p⃗′,q)(\vec{p}', q)(p​′,q) for p⃗′∈shiftTuples(P,c,p⃗)\vec{p}' \in \text{shiftTuples}(P, c, \vec{p})p​′∈shiftTuples(P,c,p​), retaining the same rational weight qqq.

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

potential(Q,(w0,…,wm−1,node(c,(v0,…,vn−1))))=potential(additiveShift(P,c,Q),(w0,…,wm−1,v0,…,vn−1)),\text{potential}\Big(Q, \big(w_0, \dots, w_{m-1}, \text{node}(c, (v_0, \dots, v_{n-1}))\big)\Big) = \text{potential}\Big(\text{additiveShift}(P, c, Q), (w_0, \dots, w_{m-1}, v_0, \dots, v_{n-1})\Big),potential(Q,(w0​,…,wm−1​,node(c,(v0​,…,vn−1​))))=potential(additiveShift(P,c,Q),(w0​,…,wm−1​,v0​,…,vn−1​)),

where both value tuples are constructed via Fin.addCases\text{Fin.addCases}Fin.addCases (concatenating w⃗\vec{w}w with the 111-tuple (node(c,v⃗))(\text{node}(c, \vec{v}))(node(c,v)) on the left-hand side, and concatenating w⃗\vec{w}w with the nnn-tuple v⃗\vec{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 unary annotation Q:Annotation(C,1)Q : \text{Annotation}(C, 1)Q:Annotation(C,1) at (node(c,v⃗))(\text{node}(c, \vec{v}))(node(c,v)), and the right-hand side evaluates additiveShift(P,c,Q):Annotation(C,n)\text{additiveShift}(P, c, Q) : \text{Annotation}(C, n)additiveShift(P,c,Q):Annotation(C,n) at (v0,…,vn−1)(v_0, \dots, v_{n-1})(v0​,…,vn−1​).
  • When n=0n = 0n=0, c∈C(0)c \in C(0)c∈C(0) is a leaf constructor and v⃗\vec{v}v is the empty tuple on Fin 0\text{Fin } 0Fin 0; each nullary transition ((()),A.final)∈A.rules(0,c)((()), A.\text{final}) \in A.\text{rules}(0, c)((()),A.final)∈A.rules(0,c) produces the mmm-tuple (p0,…,pm−1)(p_0, \dots, p_{m-1})(p0​,…,pm−1​) with weight qqq.
  • When QQQ is the empty list [][][], additiveShift(P,c,Q)\text{additiveShift}(P, c, Q)additiveShift(P,c,Q) is [][][] and both sides equal 0∈Q0 \in \mathbb{Q}0∈Q. Similarly, if for an entry (p⃗,q)∈Q(\vec{p}, q) \in Q(p​,q)∈Q the representative automaton A=P.rep(pm)A = P.\text{rep}(p_m)A=P.rep(pm​) has no transition in A.rules(n,c)A.\text{rules}(n, c)A.rules(n,c) ending at A.finalA.\text{final}A.final, that entry produces no tuples in additiveShift(P,c,Q)\text{additiveShift}(P, c, Q)additiveShift(P,c,Q) and contributes 000 to both sides.
  • Duplicate entries in QQQ or duplicate (m+n)(m+n)(m+n)-tuples generated in additiveShift(P,c,Q)\text{additiveShift}(P, c, Q)additiveShift(P,c,Q) are not deduplicated; they remain in the list and are summed with multiplicity.
  • Although the list additiveShift(P,c,Q)\text{additiveShift}(P, c, Q)additiveShift(P,c,Q) depends on the representation policy PPP (which selects a specific automaton A=P.rep(pm)A = P.\text{rep}(p_m)A=P.rep(pm​)), the theorem states that the resulting rational potential equals the left-hand side for every P:RepPolicy(C)P : \text{RepPolicy}(C)P:RepPolicy(C).
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