Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 2 — Footprint identity for rootwise potential

Open
MoserSchneckenreither.footprint_identity_rootwise

by kmehltretter82 · Nov 21, 2026 · Mathlib 0df444a (Lean v4.33.1)

amortized-analysiscomplexityresource-analysisterm-rewritingtype-systems

Let Γ⊢fpkt:q\Gamma\vdash_{\mathrm{fp}}^k t:qΓ⊢fpk​t:q be a footprint in which every symbol of ttt is constructor-like. For every total assignment σ\sigmaσ from variables to terms, the rootwise potential of tσt\sigmatσ at qqq equals the sum of the rootwise potentials of the substitution images at their context annotations, plus kkk. The assignment can take open terms as values.

Preamble
import Definitions.Def_MoserSchneckenreither_Typing
import Definitions.Def_MoserSchneckenreither_RootPotential
Formal statement
namespace MoserSchneckenreither

theorem footprint_identity_rootwise {sig : Signature} {P : Problem sig}
    (F : AnnotatedSignature P) {Γ : Context} {k : ℚ≥0} {t : Term sig} {q : Annotation}
    (h : Typing F .footprint Γ k t q) (hs : ∀ f ∈ t.symbols, ConstructorLike P f)
    (σ : ℕ → Term sig) :
    rootPotential F (t.subst σ) q = rootContextPotential F σ Γ + k := by sorry

end MoserSchneckenreither
Source
Georg Moser and Manuel Schneckenreither, Automated amortised resource analysis for term rewrite systems, Science of Computer Programming 185 (2020), article 102306, https://doi.org/10.1016/j.scico.2019.102306. Proposed correction to Lemma 2, pp. 8–9, using a rootwise variation of Definition 3.
Read-back

What the Lean code literally says, in plain math · GPT-6 (Codex)

footprint_identity_rootwise

A signature has symbols indexed by the integers from 000 through N−1N-1N−1 for some N∈NN\in\mathbb NN∈N, a natural-number arity nfn_fnf​ for each symbol fff, a nonempty subset of constructor symbols, and at least one symbol of arity zero. A term is a variable labelled by a natural number or an application f(t0,…,tnf−1)f(t_0,\ldots,t_{n_f-1})f(t0​,…,tnf​−1​). A problem PPP has a strict list and a weak list of rewrite rules. Each rule has left-hand side f(t0,…,tnf−1)f(t_0,\ldots,t_{n_f-1})f(t0​,…,tnf​−1​) with fff outside the constructor subset, and every variable on its right-hand side occurs on its left-hand side. Call a symbol fff constructor-like for PPP if it is in the constructor subset or occurs anywhere in a left-hand-side argument of some rule in either list. An annotation is a finitely supported sequence of nonnegative rationals indexed by N\mathbb NN, with pointwise addition and scalar multiplication. An annotated signature FFF for PPP gives each symbol fff a nonempty set of allowed declarations, each with one input annotation per argument, a nonnegative rational cost, and an output annotation. It also gives functions If(a,i)I_f(a,i)If​(a,i) and Cf(a)C_f(a)Cf​(a) on output annotations aaa and, for IfI_fIf​, argument indices iii, returning an annotation and a nonnegative rational, respectively. For each constructor-like fff and each aaa, the declaration with output aaa, inputs If(a,i)I_f(a,i)If​(a,i) and cost Cf(a)C_f(a)Cf​(a) is allowed. Every allowed declaration of such an fff with output aaa has precisely those inputs and cost. For these symbols and each applicable iii, the functions If(−,i)I_f(-,i)If​(−,i) and CfC_fCf​ preserve annotation addition and multiplication by every nonnegative rational. A context is a list of pairs (x,a)(x,a)(x,a) of a natural-number variable name and an annotation. Write Δ⊢Fcu:a\Delta\vdash^c_F u:aΔ⊢Fc​u:a for the footprint typing judgment, the relation generated by the following five rules. Any allowed declaration of fff with inputs aia_iai​, cost ccc, and output aaa gives [(xi,ai)]i⊢Fcf(x0,…,xnf−1):a[(x_i,a_i)]_i\vdash^c_F f(x_0,\ldots,x_{n_f-1}):a[(xi​,ai​)]i​⊢Fc​f(x0​,…,xnf​−1​):a for pairwise distinct variable names xix_ixi​, listing the pairs in argument order. A variable xxx has judgment [(x,a)]⊢F0x:a[(x,a)]\vdash^0_F x:a[(x,a)]⊢F0​x:a for every annotation aaa. To compose, take a judgment [(xi,ai)]i⊢Fc0f(x0,…,xnf−1):a[(x_i,a_i)]_i\vdash^{c_0}_F f(x_0,\ldots,x_{n_f-1}):a[(xi​,ai​)]i​⊢Fc0​​f(x0​,…,xnf​−1​):a with pairwise distinct xix_ixi​ and judgments Δi⊢Fciui:ai\Delta_i\vdash^{c_i}_F u_i:a_iΔi​⊢Fci​​ui​:ai​ for all iii. This gives the judgment on f(u0,…,unf−1)f(u_0,\ldots,u_{n_f-1})f(u0​,…,unf​−1​) with output aaa, cost c0+∑icic_0+\sum_i c_ic0​+∑i​ci​, and context the concatenation of Δi\Delta_iΔi​ in argument order, provided every xix_ixi​ is absent from the names in every Δj\Delta_jΔj​, different Δi\Delta_iΔi​ have disjoint name sets, and every variable occurs at most once in f(u0,…,unf−1)f(u_0,\ldots,u_{n_f-1})f(u0​,…,unf​−1​). Sharing starts with a judgment on uuu in the context Δ\DeltaΔ followed by (x,ax),(y,ay)(x,a_x),(y,a_y)(x,ax​),(y,ay​), with x,y,zx,y,zx,y,z pairwise distinct and absent from the names in Δ\DeltaΔ. It gives the judgment with the same cost and output annotation on the term obtained by renaming both xxx and yyy to zzz throughout uuu, in the context Δ\DeltaΔ followed by (z,ax+ay)(z,a_x+a_y)(z,ax​+ay​). The pairs of a context may be permuted without changing the term, cost, or output annotation. Define RF(u,a)R_F(u,a)RF​(u,a) for every term uuu and annotation aaa, with values in the nonnegative rationals. It is zero on variables and on applications whose head is outside the constructor-like symbols. At an application u=f(u0,…,unf−1)u=f(u_0,\ldots,u_{n_f-1})u=f(u0​,…,unf​−1​) with a constructor-like head, it is Cf(a)+∑i=0nf−1RF(ui,If(a,i))C_f(a)+\sum_{i=0}^{n_f-1}R_F(u_i,I_f(a,i))Cf​(a)+∑i=0nf​−1​RF​(ui​,If​(a,i)). An empty sum contributes zero, and the same recursion applies independently in each argument. For a function τ\tauτ assigning a term to each natural-number variable name, write u[τ]u[\tau]u[τ] for the term obtained by replacing each variable occurrence xxx of uuu by τ(x)\tau(x)τ(x) and retaining the application symbols and argument positions. For every signature, problem PPP on that signature, annotated signature FFF for PPP, context Γ\GammaΓ, nonnegative rational kkk, term ttt, and annotation qqq, assume Γ⊢Fkt:q\Gamma\vdash^k_F t:qΓ⊢Fk​t:q and assume that every symbol occurring anywhere in ttt is constructor-like for PPP. The constructor-like condition concerns the occurrences in ttt before substitution. For every total function σ\sigmaσ from natural-number variable names to terms, including assignments to terms containing variables, the following equality holds, with the sum taken over the entries of Γ\GammaΓ and equal to zero for the empty list.

RF(t[σ],q)=∑(x,a)∈ΓRF(σ(x),a)+k.R_F(t[\sigma],q)=\sum_{(x,a)\in\Gamma}R_F(\sigma(x),a)+k.RF​(t[σ],q)=(x,a)∈Γ∑​RF​(σ(x),a)+k.

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