Lemma 12: Potential preservation under the additive constructor shift
ProvedHofmannMoser.lemma_12This is Lemma 12 of Hofmann and Moser (TLCA 2015, p. 248), proving that the additive constructor shift preserves potential exactly when a constructor term is decomposed into its arguments .
Let be a representative policy (RepPolicy C), let be an -ary constructor, let be a resource annotation of length (Annotation C (m + 1)), and let (ws : Fin m → Value C) and (vs : Fin n → Value C) be ground constructor values. Then
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 of length is represented by Fin.addCases ws (fun _ ↦ Value.node c vs), and the tuple of length by Fin.addCases ws vs.
import Definitions.Def_HofmannMoser_Potential universe u
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 HofmannMoserRead-back
What the Lean code literally says, in plain math · gemini-2.5-pro
Let be an arity-indexed family of constructor symbol types in universe , and let be natural numbers. Suppose we are given:
- , a representation policy consisting of a function that assigns a concrete tree automaton to each basic function , together with a proof that for every ;
- a constructor symbol of arity ;
- an -ary annotation ;
- an -tuple of values ;
- an -tuple of values .
Here, the constituent definitions unfold as follows:
- is the inductive type of finite constructor trees .
- A tree automaton has state space , a final state , and duplicate-free finite transition lists . Its basic function is , and for any state , is the same automaton with final state changed to . A basic function is a function equal to for some tree automaton ; is the basic function .
- For any , a -ary annotation is a finite list of pairs where and with . Its potential at a -tuple of values is
- For each -tuple of basic functions , let be the representative automaton chosen by for the last coordinate . The list is formed by filtering to those transitions with , and mapping each such transition to the concatenated -tuple of basic functions
- The additive shift is obtained by flat-mapping over all entries : each entry is replaced by all pairs for , retaining the same rational weight .
This theorem asserts the equality in :
where both value tuples are constructed via (concatenating with the -tuple on the left-hand side, and concatenating with the -tuple on the right-hand side).
Edge and degenerate cases:
- When , is the unique empty tuple on ; the left-hand side evaluates the unary annotation at , and the right-hand side evaluates at .
- When , is a leaf constructor and is the empty tuple on ; each nullary transition produces the -tuple with weight .
- When is the empty list , is and both sides equal . Similarly, if for an entry the representative automaton has no transition in ending at , that entry produces no tuples in and contributes to both sides.
- Duplicate entries in or duplicate -tuples generated in are not deduplicated; they remain in the list and are summed with multiplicity.
- Although the list depends on the representation policy (which selects a specific automaton ), the theorem states that the resulting rational potential equals the left-hand side for every .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.