Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 5 — Fixed residual typing can exceed the budget

Open
MoserSchneckenreither.fixed_residual_counterexample

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

amortized-analysiscomplexityresource-analysisterm-rewritingtype-systems

With rootwise potential, a resource-bounded relative system admits a one-step instance between a typed source and a fixed residual term with normalised substitutions at both ends. The initial substitution satisfies closed-image and printed same-context consistency. For the fixed residual term and substitution there is no residual context, cost, or output annotation that satisfies both full typing and the rootwise resource inequality with charge one.

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

theorem fixed_residual_counterexample :
    ∃ (sig : Signature) (P : Problem sig) (F : AnnotatedSignature P) (Γ : Context)
      (σ τ : Substitution sig) (t u : Term sig) (p : Annotation) (k : ℚ≥0),
      ResourceBounded F ∧ σ.Normalised P ∧ τ.Normalised P ∧ Consistent F σ Γ ∧
      (∀ x ∈ σ.domain, ∀ q, (∃ j, Typing F .full Γ j (.var x) q) →
        ∃ j, Typing F .full Γ j (σ.apply x) q) ∧
      Typing F .full Γ k t p ∧ RelativeStep P (t.subst σ.apply) (u.subst τ.apply) ∧
      ¬ ∃ (Δ : Context) (ℓ : ℚ≥0) (q : Annotation), Typing F .full Δ ℓ u q ∧
        rootContextPotential F τ.apply Δ + ℓ + 1 ≤ rootContextPotential F σ.apply Γ + 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. Counterexample to the fixed-residual reading of Theorem 5, pp. 10–11, after replacing the potential of Definition 3 by its rootwise variant.
Read-back

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

There exist a signature Σ\SigmaΣ, a problem PPP on Σ\SigmaΣ, an annotated signature FFF for PPP, a context Γ\GammaΓ, substitutions σ,τ\sigma,\tauσ,τ, terms t,ut,ut,u over Σ\SigmaΣ, an annotation ppp, and a cost k∈Q≥0k\in\mathbb Q_{\ge 0}k∈Q≥0​ with the following properties. The signature has N∈NN\in\mathbb NN∈N symbols indexed by {0,…,N−1}\{0,\ldots,N-1\}{0,…,N−1}, a natural-number arity for each symbol, a nonempty designated set of constructors, and at least one symbol of arity zero. Terms are variables indexed by N\mathbb NN or symbols applied to ordered tuples of terms of their specified arity. The problem consists of a strict list and a weak list of rules. Each rule has a left-hand side with a symbol outside the designated constructor set at its root, a tuple of arguments, and a right-hand side bbb whose variables all occur on the left. Write RRR for the strict list followed by the weak list. A symbol is constructor-like if it is a designated constructor or occurs anywhere within an argument of the left-hand side of a rule in RRR. An annotation is a finitely supported map N→Q≥0\mathbb N\to\mathbb Q_{\ge 0}N→Q≥0​, with pointwise addition, scalar multiplication, and order. The zero annotation and zero costs are allowed. A context is a list of pairs of a variable index and an annotation. The annotated signature assigns to each symbol fff a nonempty set of declarations, each with one input annotation per argument position, a nonnegative rational cost, and an output annotation. It also supplies functions If(a,i)I_f(a,i)If​(a,i) and Cf(a)C_f(a)Cf​(a), giving an input annotation at position iii and a cost for any output annotation aaa. For every constructor-like fff and every aaa, the declaration with inputs If(a,i)I_f(a,i)If​(a,i), cost Cf(a)C_f(a)Cf​(a), and output aaa belongs to the set for fff, and every declaration for fff with output aaa has those inputs and cost. For constructor-like fff, each of these input functions and the cost function preserve addition and multiplication by nonnegative rational scalars. Write Tym(D,h,s,a)\mathsf{Ty}_m(D,h,s,a)Tym​(D,h,s,a) for a typing of term sss in context DDD, at cost h∈Q≥0h\in\mathbb Q_{\ge 0}h∈Q≥0​ and output aaa, where mmm is either footprint or full. The typings are those generated by the following rules, using the same mode throughout each derivation. A variable xxx has cost zero and output aaa from the one-entry context (x,a)(x,a)(x,a). A declaration for fff types f((xi)i)f((x_i)_i)f((xi​)i​) at the declared cost and output from the input-ordered context of pairs of distinct variables xix_ixi​ and the declared input annotations. To compose a typing of f((xi)i)f((x_i)_i)f((xi​)i​) in the input-ordered context (xi,pi)i(x_i,p_i)_i(xi​,pi​)i​ with typings of argument terms sis_isi​ at outputs pip_ipi​, the xix_ixi​ must be distinct and absent from all the argument contexts, the argument contexts must have pairwise disjoint key sets, and no variable may occur more than once in f((si)i)f((s_i)_i)f((si​)i​). The resulting typing of f((si)i)f((s_i)_i)f((si​)i​) concatenates the argument contexts in input order, adds the head and argument costs, and keeps the head output. If distinct x,y,zx,y,zx,y,z are absent from a context DDD, a typing in DDD followed by (x,p1),(y,p2)(x,p_1),(y,p_2)(x,p1​),(y,p2​) gives a typing in DDD followed by (z,p1+p2)(z,p_1+p_2)(z,p1​+p2​) at the same cost and output after replacing all occurrences of xxx and yyy in the term by zzz. A typing also permits permutation of the context. Full mode additionally permits replacing the cost by a greater or equal cost, replacing the annotation at the last context entry by a greater or equal annotation, replacing the output annotation by a smaller or equal annotation, or appending a pair with a fresh key and any annotation, each leaving the other data fixed. The resource condition on FFF requires, for every strict rule at charge c=1c=1c=1 and every weak rule at charge c=0c=0c=0, the following for every declaration of the rule's head with inputs pip_ipi​, cost hhh, and output aaa. There must exist a context DDD, nonnegative rational costs L,HL,HL,H, a tuple of terms sis_isi​ with no variable index occurring more than once across the entire tuple, a single renaming ρ ⁣:N→N\rho\colon\mathbb N\to\mathbb Nρ:N→N which takes sis_isi​ to the rule's iiith argument, and contexts DiD_iDi​ and nonnegative rational costs LiL_iLi​ such that each list of keys of DiD_iDi​ is a permutation of the variable occurrence list of sis_isi​, and Tyfootprint(Di,Li,si,pi)\mathsf{Ty}_{\mathrm{footprint}}(D_i,L_i,s_i,p_i)Tyfootprint​(Di​,Li​,si​,pi​) holds. The cost LLL is ∑iLi\sum_i L_i∑i​Li​. The context DDD is obtained by concatenating the DiD_iDi​ in input order, renaming their keys by ρ\rhoρ, erasing duplicate renamed keys in the resulting key list, and pairing each remaining key with the sum of all annotations for that renamed key. One must have h+L=c+Hh+L=c+Hh+L=c+H and Tyfull(D,H,b,a)\mathsf{Ty}_{\mathrm{full}}(D,H,b,a)Tyfull​(D,H,b,a), where bbb is this rule's right-hand side. Each of the substitutions σ,τ\sigma,\tauσ,τ consists of a finite domain of variable indices and an assignment of terms to all variable indices. For θ=σ\theta=\sigmaθ=σ or θ=τ\theta=\tauθ=τ, its application θ(x)\theta(x)θ(x) returns the assigned term on its domain and the variable xxx itself elsewhere. The assigned terms on its domain must have no variable occurrences and admit no ordinary one-step rewrite by RRR. An ordinary one-step rewrite replaces an instance of a rule's left-hand side by the corresponding instance of its right-hand side, recursively applying the same arbitrary mapping of variables to terms on both sides to form the instances. This replacement takes place at the root or recursively in one argument of an application with the other arguments fixed. Write s[σ]s[\sigma]s[σ] for the term that replaces each variable xxx of sss by σ(x)\sigma(x)σ(x). The keys of Γ\GammaΓ are pairwise distinct and for every (x,a)(x,a)(x,a) in Γ\GammaΓ, the index xxx belongs to the domain of σ\sigmaσ and there exists j∈Q≥0j\in\mathbb Q_{\ge 0}j∈Q≥0​ with Tyfull([],j,σ(x),a)\mathsf{Ty}_{\mathrm{full}}([],j,\sigma(x),a)Tyfull​([],j,σ(x),a). For every xxx in the domain of σ\sigmaσ and every annotation aaa, existence of a j∈Q≥0j\in\mathbb Q_{\ge 0}j∈Q≥0​ with Tyfull(Γ,j,x,a)\mathsf{Ty}_{\mathrm{full}}(\Gamma,j,x,a)Tyfull​(Γ,j,x,a) implies existence of some j′∈Q≥0j'\in\mathbb Q_{\ge 0}j′∈Q≥0​ with Tyfull(Γ,j′,σ(x),a)\mathsf{Ty}_{\mathrm{full}}(\Gamma,j',\sigma(x),a)Tyfull​(Γ,j′,σ(x),a). This implication has no instances if the domain of σ\sigmaσ is empty, and it holds automatically at any (x,a)(x,a)(x,a) for which there is no indicated typing of xxx. In addition, Tyfull(Γ,k,t,p)\mathsf{Ty}_{\mathrm{full}}(\Gamma,k,t,p)Tyfull​(Γ,k,t,p) holds. A restricted step is an ordinary step using the strict list or the weak list as its chosen rule list, with the additional requirement that every instantiated argument of that rule's left-hand side to admit no ordinary one-step rewrite by RRR. Such a step can take place at the root or recursively in one argument of an application with the other arguments fixed. There is a chain from t[σ]t[\sigma]t[σ] to u[τ]u[\tau]u[τ], with the latter formed by recursive substitution using τ(x)\tau(x)τ(x), consisting of zero or more restricted weak steps, one restricted strict step, and zero or more restricted weak steps. To state the final condition, define A(s,a)A(s,a)A(s,a) for every term and annotation by

A(x,a)=0,A(f((si)i),a)={Cf(a)+∑iA(si,If(a,i)),f constructor-like,0,otherwise.A(x,a)=0,\qquad A(f((s_i)_i),a)= \begin{cases} C_f(a)+\sum_i A(s_i,I_f(a,i)),& f\text{ constructor-like},\\ 0,& \text{otherwise}. \end{cases}A(x,a)=0,A(f((si​)i​),a)={Cf​(a)+∑i​A(si​,If​(a,i)),0,​f constructor-like,otherwise.​

Here xxx denotes a variable, and a nullary application has an empty argument sum. For a substitution θ\thetaθ, put Aθ(D)=∑(x,a)∈DA(θ(x),a)A_\theta(D)=\sum_{(x,a)\in D}A(\theta(x),a)Aθ​(D)=∑(x,a)∈D​A(θ(x),a), summing once per list entry, with zero for an empty context. This recursion applies to arbitrary terms, including terms with variables. There do not exist a context Δ\DeltaΔ, a nonnegative rational cost ℓ\ellℓ, and an annotation aaa satisfying both Tyfull(Δ,ℓ,u,a)\mathsf{Ty}_{\mathrm{full}}(\Delta,\ell,u,a)Tyfull​(Δ,ℓ,u,a) and

Aτ(Δ)+ℓ+1≤Aσ(Γ)+k.A_\tau(\Delta)+\ell+1\le A_\sigma(\Gamma)+k.Aτ​(Δ)+ℓ+1≤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