Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 9: Diagonalization of binary multivariate basic functions

Proved
HofmannMoser.lemma_9

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

amortized-analysiscomplexityterm-rewritingtree-automatatype-systems

This is Lemma 9 of Hofmann and Moser (TLCA 2015, p. 248), showing that evaluating a binary multivariate basic function on a duplicated argument (v,v)(v, v)(v,v) yields a unary basic function.

Let SSS be a finite nonempty constructor signature (FiniteConstructors C), and let p=(p0,p1)∈BF(2)p = (p_0, p_1) \in \mathsf{BF}(2)p=(p0​,p1​)∈BF(2) (p : Fin 2 → BasicFunction C) be a pair of basic resource functions with multivariate evaluation p(v,v)=p0(v)⋅p1(v)p(v, v) = p_0(v) \cdot p_1(v)p(v,v)=p0​(v)⋅p1​(v) (multivariateBasic p (fun _ ↦ v)). Then there exists a unary basic resource function p′∈BFp' \in \mathsf{BF}p′∈BF (p' : BasicFunction C) such that for every ground constructor value vvv (Value C),

p(v,v)=p′(v).p(v, v) = p'(v).p(v,v)=p′(v).

This lemma justifies contracting shared variables in resource annotations via the sharing operator Υ\UpsilonΥ (Lemma 13) and the typing rule Typing.share.

Preamble
import Definitions.Def_HofmannMoser_Potential

universe u
Formal statement
namespace HofmannMoser

theorem lemma_9 {C : Nat → Type u} (S : FiniteConstructors C)
    (p : Fin 2 → BasicFunction C) :
    ∃ p' : BasicFunction C, ∀ v : Value C,
      multivariateBasic p (fun _ ↦ v) = p'.val 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. 248, Lemma 9
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 ∃n∈N,Nonempty(C(n))\exists n \in \mathbb{N}, \text{Nonempty}(C(n))∃n∈N,Nonempty(C(n));
  • a pair of basic functions p=(p0,p1):{0,1}→BasicFunction(C)p = (p_0, p_1) : \{0, 1\} \to \text{BasicFunction}(C)p=(p0​,p1​):{0,1}→BasicFunction(C).

Here:

  • Value(C)\text{Value}(C)Value(C) is the inductive type of finite constructor trees node(c,(v0,…,vn−1))\text{node}(c, (v_0, \dots, v_{n-1}))node(c,(v0​,…,vn−1​)) over CCC.
  • A basic function f∈BasicFunction(C)f \in \text{BasicFunction}(C)f∈BasicFunction(C) is a function f:Value(C)→Nf : \text{Value}(C) \to \mathbb{N}f:Value(C)→N paired with an existential proof that f=A.basicf = A.\text{basic}f=A.basic for some tree automaton A:TreeAutomaton(C)A : \text{TreeAutomaton}(C)A:TreeAutomaton(C), where AAA has a positive 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)), and where A.basic(v)=runCount(A,v,A.final)A.\text{basic}(v) = \text{runCount}(A, v, A.\text{final})A.basic(v)=runCount(A,v,A.final) is defined recursively by
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​).
  • For any nnn-tuple of basic functions (f0,…,fn−1)(f_0, \dots, f_{n-1})(f0​,…,fn−1​) and nnn-tuple of values (w0,…,wn−1)(w_0, \dots, w_{n-1})(w0​,…,wn−1​), multivariateBasic((f0,…,fn−1),(w0,…,wn−1))∈N\text{multivariateBasic}((f_0, \dots, f_{n-1}), (w_0, \dots, w_{n-1})) \in \mathbb{N}multivariateBasic((f0​,…,fn−1​),(w0​,…,wn−1​))∈N is the left-folded product ∏i=0n−1fi(wi)\prod_{i=0}^{n-1} f_i(w_i)∏i=0n−1​fi​(wi​) starting from 111. For n=2n = 2n=2 and the constant pair (v,v)(v, v)(v,v), this is 1⋅p0(v)⋅p1(v)=p0(v)⋅p1(v)1 \cdot p_0(v) \cdot p_1(v) = p_0(v) \cdot p_1(v)1⋅p0​(v)⋅p1​(v)=p0​(v)⋅p1​(v).

This theorem asserts that there exists a basic function p′∈BasicFunction(C)p' \in \text{BasicFunction}(C)p′∈BasicFunction(C) such that for every value v∈Value(C)v \in \text{Value}(C)v∈Value(C),

multivariateBasic((p0,p1),(v,v))=p0(v)⋅p1(v)=p′(v).\text{multivariateBasic}\big((p_0, p_1), (v, v)\big) = p_0(v) \cdot p_1(v) = p'(v).multivariateBasic((p0​,p1​),(v,v))=p0​(v)⋅p1​(v)=p′(v).

Edge and degenerate cases:

  • The conclusion uses plain existential quantification (∃p′∈BasicFunction(C)\exists p' \in \text{BasicFunction}(C)∃p′∈BasicFunction(C), not unique existence), and does not depend on any representation policy RepPolicy(C)\text{RepPolicy}(C)RepPolicy(C) in its statement.
  • If C(0)C(0)C(0) is empty, Value(C)\text{Value}(C)Value(C) is uninhabited so the pointwise equality holds vacuously for any p′∈BasicFunction(C)p' \in \text{BasicFunction}(C)p′∈BasicFunction(C), though exhibiting an inhabitant of BasicFunction(C)\text{BasicFunction}(C)BasicFunction(C) still requires constructing a valid TreeAutomaton(C)\text{TreeAutomaton}(C)TreeAutomaton(C) (for which S:FiniteConstructors(C)S : \text{FiniteConstructors}(C)S:FiniteConstructors(C) provides finite_rules and has_rule).
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