Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Corollary 6 — A numerical failure of the evaluation bound

Open
MoserSchneckenreither.evaluation_bound_counterexample

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

amortized-analysiscomplexityresource-analysisterm-rewritingtype-systems

There is a resource-bounded system and a typed initial term with a normalised substitution satisfying both closed-image consistency and the printed same-context condition. The instantiated term evaluates with one strict step to a normal form typable at the required annotation. One plus its whole-term potential exceeds the initial context potential plus the initial typing cost.

Preamble
import Definitions.Def_MoserSchneckenreither_Typing
Formal statement
namespace MoserSchneckenreither

theorem evaluation_bound_counterexample :
    ∃ (sig : Signature) (P : Problem sig) (F : AnnotatedSignature P) (Γ : Context)
      (σ : Substitution sig) (t v : Term sig) (q : Annotation) (k : ℚ≥0),
      ResourceBounded F ∧ σ.Normalised P ∧ Consistent F σ Γ ∧
      (∀ x ∈ σ.domain, ∀ p, (∃ j, Typing F .full Γ j (.var x) p) →
        ∃ j, Typing F .full Γ j (σ.apply x) p) ∧
      Typing F .full Γ k t q ∧ Derivation P (t.subst σ.apply) 1 v ∧ Normal P.rules v ∧
      (∃ j, Typing F .full [] j v q) ∧
      ¬ ((1 : ℚ≥0) + potential F v q ≤ contextPotential 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. Counterexample to the numerical inequality of Corollary 6, p. 11, with Definition 3, p. 7.
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Γ, a substitution σ\sigmaσ, terms t,vt,vt,v over Σ\SigmaΣ, an annotation qqq, 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. The substitution σ\sigmaσ consists of a finite domain of variable indices and an assignment of terms to all variable indices. Its application, written σ(x)\sigma(x)σ(x) for a variable xxx, returns the assigned term on its domain and the variable 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,q)\mathsf{Ty}_{\mathrm{full}}(\Gamma,k,t,q)Tyfull​(Γ,k,t,q) 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 finite derivation from t[σ]t[\sigma]t[σ] to vvv whose steps are each taken as restricted strict steps with weight one or restricted weak steps with weight zero, and whose total weight is one. Thus the derivation has one step counted as strict and any number of weak steps, including none. The term vvv admits no ordinary one-step rewrite by RRR, and there exists j∈Q≥0j\in\mathbb Q_{\ge 0}j∈Q≥0​ such that Tyfull([],j,v,q)\mathsf{Ty}_{\mathrm{full}}([],j,v,q)Tyfull​([],j,v,q). Define B(s,a)B(s,a)B(s,a) on every term and annotation by the recursion

B(x,a)=0,B(f((si)i),a)=Cf(a)+∑iB(si,If(a,i)),B(x,a)=0,\qquad B(f((s_i)_i),a)=C_f(a)+\sum_i B(s_i,I_f(a,i)),B(x,a)=0,B(f((si​)i​),a)=Cf​(a)+i∑​B(si​,If​(a,i)),

where xxx denotes a variable and a nullary application has an empty argument sum. Define Φ(s,a)\Phi(s,a)Φ(s,a) to be B(s,a)B(s,a)B(s,a) if sss has no variable occurrences and every symbol in it is constructor-like, and zero otherwise. The context potential is ∑(x,a)∈ΓΦ(σ(x),a)\sum_{(x,a)\in\Gamma}\Phi(\sigma(x),a)∑(x,a)∈Γ​Φ(σ(x),a), summed once per context entry with zero for an empty context. The following non-strict inequality of nonnegative rationals fails.

1+Φ(v,q)≤∑(x,a)∈ΓΦ(σ(x),a)+k.1+\Phi(v,q)\le\sum_{(x,a)\in\Gamma}\Phi(\sigma(x),a)+k.1+Φ(v,q)≤(x,a)∈Γ∑​Φ(σ(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