Research / 2021 –

Demurrage at constant cost

Draft · the definitions and theorems on this page are machine-checked in Lean; independent review is in progress.

A holding cost on money, applied through share accounting: only the total supply decays, so every holder is charged in proportion at constant cost per operation. Decay is independent of when updates happen exactly when it is geometric; a linear per-interval rule rewards frequent updates by exactly r²ab·S; floor rounding stays within one unit per operation and never pays out more than the supply; supply plus collected pool is conserved.

DemurrageShare accountingFunctional equations
f(a+b) = f(a)f(b)
decay is independent of the update schedule exactly when the decay factor is geometric
r²ab·S
how much more supply remains when a linear rule is applied as two updates of lengths a and b instead of one
≤ 1 unit
difference between lazily and eagerly decayed balances under floor rounding

Demurrage is a holding cost on money: a balance shrinks over time unless it is used. Charging every holder individually costs one update per holder. Share accounting avoids that: holders own shares, only the total supply decays, and a balance is the supply times the holder’s fraction of the shares. This page proves what that construction guarantees, in Lean 4.

Goal. A holding cost that is applied (i) to every holder in the same proportion, (ii) at constant cost per operation, (iii) independently of when the system happens to be updated, and (iv) without creating or losing value: everything decayed is collected in a pool.

Share accounting

Let the supply be SS, holder ii own sis_i shares, and T=∑isiT = \sum_i s_i. Holder ii‘s balance is bi=S⋅si/Tb_i = S \cdot s_i / T. Decay over an interval of length Δ\Delta replaces SS by S⋅f(Δ)S \cdot f(\Delta) for a decay factor ff, and moves the difference into a pool PP. Shares never change under decay.

Proportional fairness (fair_ratio, fair_decay). For any two holders, bi:bj=si:sjb_i : b_j = s_i : s_j whatever the supply, and a decay from SS to S′S' scales every balance by the same factor S′/SS'/S. Applying decay is one update of SS, whatever the number of holders.

When the update schedule does not matter

The supply is updated only when someone interacts with the system, so an interval of length Δ\Delta may be covered by one update or by several, Δ=l1+⋯+ln\Delta = l_1 + \dots + l_n. The rule is path independent if every such partition gives the same factor: f(l1)⋯f(ln)=f(l1+⋯+ln)f(l_1)\cdots f(l_n) = f(l_1 + \dots + l_n).

Path independence (pathIndependent_iff_cauchy, pathIndependent_iff_geometric, schedule_free_iff_geometric). Over any monoid of factors, the rule is path independent if and only if f(0)=1f(0) = 1 and f(a+b)=f(a) f(b)f(a + b) = f(a)\,f(b) for all a,ba, b, if and only if f(Δ)=f(1)Δf(\Delta) = f(1)^{\Delta} for all Δ\Delta. Equivalently, for every starting supply, applying the rule update by update over any schedule equals applying it once over the total interval exactly when the rule is geometric (schedule_free_iff_geometric; the geometric direction is also geometric_schedule_invariant).

A linear rule depends on the schedule (linear_two_split_identity, linear_two_split_strict, update_trigger_reduces_decay, linear_schedule_bounds). Let f(Δ)=1−rΔf(\Delta) = 1 - r\Delta with r≥0r \ge 0. Applying it as two updates of lengths aa and bb leaves

S(1−ra)(1−rb)=S(1−r(a+b))+r2ab S,S(1 - ra)(1 - rb) = S\bigl(1 - r(a+b)\bigr) + r^2 ab\, S,

so when r,a,b,S>0r, a, b, S > 0 splitting strictly increases the remaining supply, and the decay collected falls by exactly r2ab Sr^2 ab\,S. For any schedule with total Δ\Delta and rΔ≤1r\Delta \le 1, the remaining supply is at least the single-update result and exceeds it by at most (rΔ)2S/2(r\Delta)^2 S / 2. A party able to trigger updates can therefore lower the total decay with a linear rule, and cannot with a geometric one.

Rounding

Balances and the supply are integers, so each division rounds down.

Lazy and eager decay agree within one unit (lazy_bounds, eager_bounds, lazy_eager_close). Decaying the supply and then deriving a balance, or deriving the balance and then decaying it, each is at most the exact value and less than two units below it, and the two differ by at most one unit.

Solvency (balances_solvent). If the shares sum to TT, the rounded balances sum to at most the supply, and fall short of it by fewer units than there are holders.

Rounding favours the pool (floor_decay_ge_exact), and a rounded geometric rule over any schedule of kk updates stays within kk units of the exact value (geoFloor_bounds).

Conservation

Supply plus pool is conserved (conservation). For any sequence of decays, mints, burns and payouts from the pool, the final S+PS + P equals the initial S+PS + P plus everything minted minus everything burned.

Limits

  • Time is discrete (intervals are natural numbers); a continuous-time rule is outside the model.
  • The bounds are per operation; over many operations the rounding error grows with the number of operations, as stated.
  • How the pool is spent (rewards, its fairness) is not modelled beyond conservation.

Prior work

Money with a holding cost (1916); a municipal stamp-scrip experiment (1932–33); elastic-supply tokens and share-based vault accounting; the Cauchy functional equation.

The Lean development

All definitions and proofs (533 lines, Lean 4, core library only)
/-!
# Basic list arithmetic and a polynomial-normalisation tactic (Lean 4 core only)
-/
namespace Demurrage

/-- Sum of a list of naturals (interval lengths). -/
def lsum : List Nat → Nat
  | [] => 0
  | a :: l => a + lsum l

/-- Sum of a list of integers. -/
def isum : List Int → Int
  | [] => 0
  | a :: l => a + isum l

theorem two_mul' (a : Int) : 2 * a = a + a := by omega

/-- Normalise commutative-ring expressions over `Int` into sums of monomials and close the
goal by linear arithmetic over those monomials (treated as atoms). -/
macro "poly_omega" : tactic =>
  `(tactic| (try simp only [Demurrage.two_mul'] at *
             try simp only [Int.mul_sub, Int.sub_mul, Int.mul_add, Int.add_mul, Int.mul_assoc,
               Int.mul_comm, Int.mul_left_comm, Int.mul_one, Int.one_mul, Int.mul_zero,
               Int.zero_mul] at *
             omega))

/-- The same normalisation over `Nat` (sums of products only; no truncated subtraction). -/
macro "npoly_omega" : tactic =>
  `(tactic| (try simp only [Nat.succ_eq_add_one, Nat.left_distrib, Nat.right_distrib, Nat.mul_assoc,
               Nat.mul_comm, Nat.mul_left_comm, Nat.mul_one, Nat.one_mul, Nat.mul_zero,
               Nat.zero_mul] at *
             omega))

/-- Floor division bracket: `n * (m / n) ≤ m < n * (m / n) + n`. -/
theorem floor_spec (m n : Nat) (hn : 0 < n) : n * (m / n) ≤ m ∧ m < n * (m / n) + n := by
  have h1 := Nat.div_add_mod m n
  have h2 := Nat.mod_lt m hn
  omega

end Demurrage

/-!
# Path independence of a decay rule (claims 3 and 6)

A decay rule assigns to every elapsed interval `Δ : Nat` a factor `f Δ` in a monoid `M`
(for instance positive rationals under multiplication).  Applying the rule over a partition
`[Δ₁, …, Δₖ]` of an interval multiplies the supply by `f Δ₁ * ⋯ * f Δₖ`.  The rule is
*path independent* when this product depends only on `Δ₁ + ⋯ + Δₖ`.  We show path
independence is equivalent to the Cauchy-type functional equation `f (a+b) = f a * f b`
(with `f 0 = 1`) and to the geometric form `f Δ = (f 1)^Δ`.
-/
namespace Demurrage

/-- A monoid, stated with explicit laws (Lean core has no algebraic hierarchy). -/
class Monoid' (M : Type) extends Mul M where
  one : M
  mul_assoc : ∀ a b c : M, a * b * c = a * (b * c)
  one_mul : ∀ a : M, one * a = a
  mul_one : ∀ a : M, a * one = a

variable {M : Type} [Monoid' M]

/-- Product of a list of factors. -/
def lprod : List M → M
  | [] => Monoid'.one
  | a :: l => a * lprod l

/-- Natural power `c ^ n` in a monoid. -/
def npow (c : M) : Nat → M
  | 0 => Monoid'.one
  | n + 1 => npow c n * c

/-- Apply the decay factors of a schedule (a list of elapsed intervals) to a supply `S`,
one update at a time. -/
def applySchedule (f : Nat → M) (S : M) : List Nat → M
  | [] => S
  | d :: ds => applySchedule f (S * f d) ds

theorem applySchedule_eq (f : Nat → M) (S : M) (l : List Nat) :
    applySchedule f S l = S * lprod (l.map f) := by
  induction l generalizing S with
  | nil => simp [applySchedule, lprod, Monoid'.mul_one]
  | cons d ds ih => simp [applySchedule, lprod, ih, Monoid'.mul_assoc]

/-- Path independence of the factors: every partition gives the factor of its total. -/
def PathIndependent (f : Nat → M) : Prop := ∀ l : List Nat, lprod (l.map f) = f (lsum l)

theorem npow_add (c : M) (a b : Nat) : npow c (a + b) = npow c a * npow c b := by
  induction b with
  | zero => simp [npow, Monoid'.mul_one]
  | succ b ih => rw [← Nat.add_assoc]; simp [npow, ih, Monoid'.mul_assoc]

/-- **Claim 3a.** Path independence ⇔ `f 0 = 1` and the functional equation
`f (a + b) = f a * f b`. -/
theorem pathIndependent_iff_cauchy (f : Nat → M) :
    PathIndependent f ↔ (f 0 = Monoid'.one ∧ ∀ a b, f (a + b) = f a * f b) := by
  constructor
  · intro h
    refine ⟨(h []).symm, fun a b => ?_⟩
    have := h [a, b]
    simp [lprod, lsum, Monoid'.mul_one] at this
    exact this.symm
  · rintro ⟨h0, hm⟩ l
    induction l with
    | nil => simp [lprod, lsum, h0]
    | cons d ds ih => simp [lprod, lsum, ih, hm]

/-- **Claim 3b.** Path independence ⇔ geometric form `f Δ = (f 1)^Δ`. -/
theorem pathIndependent_iff_geometric (f : Nat → M) :
    PathIndependent f ↔ ∀ n, f n = npow (f 1) n := by
  rw [pathIndependent_iff_cauchy]
  constructor
  · rintro ⟨h0, hm⟩ n
    induction n with
    | zero => simp [npow, h0]
    | succ n ih => rw [hm, ih]; rfl
  · intro hg
    refine ⟨by rw [hg]; rfl, fun a b => ?_⟩
    rw [hg (a + b), hg a, hg b, npow_add]

/-- **Claim 3c (action form).** For every starting supply, applying the rule update by update
over any schedule equals applying it once over the total interval, iff the rule is
geometric. -/
theorem schedule_free_iff_geometric (f : Nat → M) :
    (∀ (S : M) (l : List Nat), applySchedule f S l = S * f (lsum l)) ↔
      ∀ n, f n = npow (f 1) n := by
  rw [← pathIndependent_iff_geometric]
  constructor
  · intro h l
    have := h Monoid'.one l
    rw [applySchedule_eq, Monoid'.one_mul, Monoid'.one_mul] at this
    exact this
  · intro h S l
    rw [applySchedule_eq, h l]

/-- **Claim 6.** Geometric decay: every update schedule covering the same total interval
yields the same supply, so no choice of update times changes the outcome. -/
theorem geometric_schedule_invariant (c S : M) (l₁ l₂ : List Nat) (h : lsum l₁ = lsum l₂) :
    applySchedule (npow c) S l₁ = applySchedule (npow c) S l₂ := by
  have hpi : PathIndependent (npow c) := by
    rw [pathIndependent_iff_geometric]; intro n
    have : npow c 1 = c := by simp [npow, Monoid'.one_mul]
    rw [this]
  rw [applySchedule_eq, applySchedule_eq, hpi l₁, hpi l₂, h]

/-- Natural numbers under multiplication form a monoid (used for exact fraction numerators
and denominators). -/
instance : Monoid' Nat where
  one := 1
  mul_assoc := Nat.mul_assoc
  one_mul := Nat.one_mul
  mul_one := Nat.mul_one

theorem npow_nat (c n : Nat) : npow c n = c ^ n := by
  induction n with
  | zero => rfl
  | succ n ih => rw [npow, ih, Nat.pow_succ]

end Demurrage

/-!
# Linear-per-interval decay is schedule dependent (claim 4)

Linear decay removes the fraction `r·Δ` of supply over an interval of length `Δ`
(`0 ≤ r·Δ ≤ 1`).  We work with exact rationals written over a common denominator:
`r = ρ / D` with `ρ, D` integers, `D > 0`.  For a schedule of intervals `l₁, …, lₙ` the
remaining supply is `S · ∏ (D - ρ lᵢ) / Dⁿ`; applied once it is `S · (D - ρ Δ) / D`.
All statements below are the cross-multiplied (denominator-free) forms.
-/
namespace Demurrage

/-- `∏ (D - x)` over a list of scaled decay amounts `x = ρ·l`. -/
def lprodLin (D : Int) : List Int → Int
  | [] => 1
  | x :: xs => (D - x) * lprodLin D xs

theorem pow_nonneg' (D : Int) (hD : 0 ≤ D) (n : Nat) : 0 ≤ D ^ n := by
  induction n with
  | zero => show (0:Int) ≤ 1; decide
  | succ n ih => rw [Int.pow_succ]; exact Int.mul_nonneg ih hD

theorem isum_nonneg (xs : List Int) (hx : ∀ x ∈ xs, 0 ≤ x) : 0 ≤ isum xs := by
  induction xs with
  | nil => simp [isum]
  | cons y ys ih =>
    simp only [isum]
    have := hx y (List.mem_cons_self _ _)
    have := ih (fun x hm => hx x (List.mem_cons_of_mem _ hm))
    omega

/-- Product inequality `∏(1 - xᵢ) ≥ 1 - Σ xᵢ` (for `xᵢ ≥ 0`, `Σ xᵢ ≤ 1`), homogeneous form. -/
theorem prod_lower (D : Int) (xs : List Int) (hD : 0 ≤ D) (hx : ∀ x ∈ xs, 0 ≤ x)
    (hs : isum xs ≤ D) : D ^ xs.length * (D - isum xs) ≤ D * lprodLin D xs := by
  induction xs with
  | nil => simp [lprodLin, isum, Int.pow_zero]
  | cons y ys ih =>
    have hy : 0 ≤ y := hx y (List.mem_cons_self _ _)
    have hx' : ∀ x ∈ ys, 0 ≤ x := fun x hm => hx x (List.mem_cons_of_mem _ hm)
    have hX : 0 ≤ isum ys := isum_nonneg ys hx'
    simp only [isum] at hs
    have ih := ih hx' (by omega)
    have hDy : 0 ≤ D - y := by omega
    simp only [List.length_cons, Int.pow_succ, isum, lprodLin]
    have hQ := pow_nonneg' D hD ys.length
    generalize D ^ ys.length = Q at *
    generalize isum ys = X at *
    generalize lprodLin D ys = P at *
    have h2 := Int.mul_le_mul_of_nonneg_right ih hDy
    have h3 : 0 ≤ Q * X * y := Int.mul_nonneg (Int.mul_nonneg hQ hX) hy
    poly_omega

/-- Product inequality `∏(1 - xᵢ) ≤ 1 - Σ xᵢ + (Σ xᵢ)²/2` (for `0 ≤ xᵢ ≤ 1`), homogeneous
form. -/
theorem prod_upper (D : Int) (xs : List Int) (hD : 0 ≤ D) (hx : ∀ x ∈ xs, 0 ≤ x)
    (hs : isum xs ≤ D) :
    2 * D * D * lprodLin D xs ≤
      D ^ xs.length * (2 * D * D - 2 * D * isum xs + isum xs * isum xs) := by
  induction xs with
  | nil => simp [lprodLin, isum, Int.pow_zero]
  | cons y ys ih =>
    have hy : 0 ≤ y := hx y (List.mem_cons_self _ _)
    have hx' : ∀ x ∈ ys, 0 ≤ x := fun x hm => hx x (List.mem_cons_of_mem _ hm)
    have hX : 0 ≤ isum ys := isum_nonneg ys hx'
    simp only [isum] at hs
    have ih := ih hx' (by omega)
    have hDy : 0 ≤ D - y := by omega
    simp only [List.length_cons, Int.pow_succ, isum, lprodLin]
    have hQ := pow_nonneg' D hD ys.length
    generalize D ^ ys.length = Q at *
    generalize isum ys = X at *
    generalize lprodLin D ys = P at *
    have h2 := Int.mul_le_mul_of_nonneg_right ih hDy
    have h3 : 0 ≤ Q * D * y * y :=
      Int.mul_nonneg (Int.mul_nonneg (Int.mul_nonneg hQ hD) hy) hy
    have h4 : 0 ≤ Q * X * X * y :=
      Int.mul_nonneg (Int.mul_nonneg (Int.mul_nonneg hQ hX) hX) hy
    poly_omega

theorem isum_map_mul (ρ : Int) (ls : List Int) :
    isum (ls.map (fun l => ρ * l)) = ρ * isum ls := by
  induction ls with
  | nil => simp [isum]
  | cons a l ih => simp only [List.map, isum, ih, Int.mul_add]

/-- **Claim 4a (exact two-way split).** Splitting an interval `a + b` into `a` then `b` leaves
`S(1-ra)(1-rb) = S(1-r(a+b)) + r²ab·S`: in cross-multiplied form with `r = ρ/D`. -/
theorem linear_two_split_identity (S D ρ a b : Int) :
    S * (D - ρ * a) * (D - ρ * b) = D * (S * (D - ρ * (a + b))) + S * ρ * ρ * a * b := by
  poly_omega

/-- **Claim 4b (strictness).** If `r > 0`, both parts are positive and `S > 0`, splitting
strictly increases the remaining supply: `S(1-ra)(1-rb) > S(1-r(a+b))`. -/
theorem linear_two_split_strict (S D ρ a b : Int) (hS : 0 < S) (hρ : 0 < ρ) (ha : 0 < a)
    (hb : 0 < b) : D * (S * (D - ρ * (a + b))) < S * (D - ρ * a) * (D - ρ * b) := by
  have h := linear_two_split_identity S D ρ a b
  have hp : 0 < S * ρ * ρ * a * b :=
    Int.mul_pos (Int.mul_pos (Int.mul_pos (Int.mul_pos hS hρ) hρ) ha) hb
  omega

/-- **Claim 4c (decay reduction by triggering an update).** The decay collected over `a + b`
when an extra update is triggered after `a` is smaller by exactly `r²ab·S`
(all quantities over the common denominator `D²`). -/
theorem update_trigger_reduces_decay (S D ρ a b : Int) (hS : 0 < S) (hρ : 0 < ρ) (ha : 0 < a)
    (hb : 0 < b) :
    (S * D * D - S * (D - ρ * a) * (D - ρ * b)) + S * ρ * ρ * a * b = D * (S * ρ * (a + b)) ∧
    S * D * D - S * (D - ρ * a) * (D - ρ * b) < D * (S * ρ * (a + b)) := by
  have h := linear_two_split_identity S D ρ a b
  have hp : 0 < S * ρ * ρ * a * b :=
    Int.mul_pos (Int.mul_pos (Int.mul_pos (Int.mul_pos hS hρ) hρ) ha) hb
  constructor <;> poly_omega

/-- **Claim 4d (general schedule).** For any schedule `l₁,…,lₙ` with total `Δ`, `lᵢ ≥ 0`,
`ρ ≥ 0`, `ρΔ ≤ D`, the remaining supply after the schedule, `S·∏(D-ρlᵢ)/Dⁿ`, is at least the
single-update result `S(D-ρΔ)/D` and exceeds it by at most `(rΔ)²·S/2`, `r = ρ/D`. -/
theorem linear_schedule_bounds (S D ρ : Int) (ls : List Int) (hS : 0 ≤ S) (hD : 0 ≤ D)
    (hρ : 0 ≤ ρ) (hl : ∀ l ∈ ls, 0 ≤ l) (hΔ : ρ * isum ls ≤ D) :
    D ^ ls.length * (S * (D - ρ * isum ls)) ≤ D * (S * lprodLin D (ls.map (fun l => ρ * l))) ∧
    2 * D * D * (D * (S * lprodLin D (ls.map (fun l => ρ * l))) -
        D ^ ls.length * (S * (D - ρ * isum ls)))
      ≤ D ^ ls.length * D * (S * (ρ * isum ls) * (ρ * isum ls)) := by
  have hx : ∀ x ∈ ls.map (fun l => ρ * l), 0 ≤ x := by
    intro x hm
    simp only [List.mem_map] at hm
    obtain ⟨l, hl', rfl⟩ := hm
    exact Int.mul_nonneg hρ (hl l hl')
  have hs : isum (ls.map (fun l => ρ * l)) ≤ D := by rw [isum_map_mul]; exact hΔ
  have hlo := prod_lower D _ hD hx hs
  have hup := prod_upper D _ hD hx hs
  rw [isum_map_mul, List.length_map] at hlo hup
  have hQ := pow_nonneg' D hD ls.length
  generalize D ^ ls.length = Q at *
  generalize ρ * isum ls = X at *
  generalize lprodLin D (ls.map (fun l => ρ * l)) = P at *
  have h1 := Int.mul_le_mul_of_nonneg_left hlo hS
  have h2 := Int.mul_le_mul_of_nonneg_left hup (Int.mul_nonneg hS hD)
  constructor <;> poly_omega

end Demurrage

/-!
# Lazy versus eager decay under floor rounding, and solvency (claims 2 and 6b)

Integer accounting: supply `S`, holder share `sh`, total shares `T`, decay factor `p/q`
(`p ≤ q`, `q > 0`).  *Lazy* decay floors the supply once and derives each balance from it:
`⌊⌊S·p/q⌋·sh/T⌋`.  *Eager* decay floors each holder's balance and decays it:
`⌊⌊S·sh/T⌋·p/q⌋`.  The exact (rational) value of both is `S·p·sh/(q·T)`.
-/
namespace Demurrage

/-- Two successive floor divisions lose less than two units in total (one per operation). -/
theorem two_floor_bounds (x m₁ d₁ m₂ d₂ : Nat) (hd₁ : 0 < d₁) (hd₂ : 0 < d₂) (hm : m₂ ≤ d₂) :
    d₁ * d₂ * ((x * m₁ / d₁) * m₂ / d₂) ≤ x * m₁ * m₂ ∧
    x * m₁ * m₂ < d₁ * d₂ * ((x * m₁ / d₁) * m₂ / d₂ + 2) := by
  obtain ⟨a1, a2⟩ := floor_spec (x * m₁) d₁ hd₁
  generalize x * m₁ / d₁ = y₁ at *
  obtain ⟨b1, b2⟩ := floor_spec (y₁ * m₂) d₂ hd₂
  generalize y₁ * m₂ / d₂ = y at *
  generalize x * m₁ = X at *
  constructor
  · calc d₁ * d₂ * y = d₁ * (d₂ * y) := Nat.mul_assoc _ _ _
      _ ≤ d₁ * (y₁ * m₂) := Nat.mul_le_mul_left _ b1
      _ = (d₁ * y₁) * m₂ := (Nat.mul_assoc _ _ _).symm
      _ ≤ X * m₂ := Nat.mul_le_mul_right _ a1
  · have h1 : X * m₂ ≤ (d₁ * y₁ + d₁) * m₂ := Nat.mul_le_mul_right _ (Nat.le_of_lt a2)
    have h2 : d₁ * (y₁ * m₂) < d₁ * (d₂ * y + d₂) := Nat.mul_lt_mul_of_pos_left b2 hd₁
    have h3 : d₁ * m₂ ≤ d₁ * d₂ := Nat.mul_le_mul_left _ hm
    have e1 : (d₁ * y₁ + d₁) * m₂ = d₁ * (y₁ * m₂) + d₁ * m₂ := by
      rw [Nat.add_mul, Nat.mul_assoc]
    have e2 : d₁ * (d₂ * y + d₂) = d₁ * d₂ * y + d₁ * d₂ := by
      rw [Nat.mul_add, Nat.mul_assoc]
    have e3 : d₁ * d₂ * (y + 2) = d₁ * d₂ * y + d₁ * d₂ + d₁ * d₂ := by
      rw [Nat.mul_add, Nat.mul_two, Nat.add_assoc]
    omega

/-- Lazily decayed balance: floor the supply once, then derive the balance. -/
def lazyBal (S p q sh T : Nat) : Nat := (S * p / q) * sh / T
/-- Eagerly decayed balance: floor the balance, then decay it. -/
def eagerBal (S p q sh T : Nat) : Nat := (S * sh / T) * p / q

/-- **Claim 2b (lazy, rounded).** The lazily decayed balance never exceeds the exact value
`S·p·sh/(q·T)` and falls short of it by less than 2 units (< 1 per floor operation). -/
theorem lazy_bounds (S p q sh T : Nat) (hq : 0 < q) (hT : 0 < T) (hsh : sh ≤ T) :
    q * T * lazyBal S p q sh T ≤ S * p * sh ∧ S * p * sh < q * T * (lazyBal S p q sh T + 2) :=
  two_floor_bounds S p q sh T hq hT hsh

/-- **Claim 2c (eager, rounded).** The same bracket holds for eager per-holder decay. -/
theorem eager_bounds (S p q sh T : Nat) (hq : 0 < q) (hT : 0 < T) (hp : p ≤ q) :
    q * T * eagerBal S p q sh T ≤ S * p * sh ∧ S * p * sh < q * T * (eagerBal S p q sh T + 2) := by
  have h := two_floor_bounds S sh T p q hT hq hp
  rw [Nat.mul_comm T q, Nat.mul_right_comm S sh p] at h
  exact h

/-- **Claim 2d.** Under floor rounding, lazy and eager decay of any balance differ by at most
one unit. -/
theorem lazy_eager_close (S p q sh T : Nat) (hq : 0 < q) (hT : 0 < T) (hsh : sh ≤ T)
    (hp : p ≤ q) :
    lazyBal S p q sh T ≤ eagerBal S p q sh T + 1 ∧ eagerBal S p q sh T ≤ lazyBal S p q sh T + 1 := by
  obtain ⟨l1, l2⟩ := lazy_bounds S p q sh T hq hT hsh
  obtain ⟨e1, e2⟩ := eager_bounds S p q sh T hq hT hp
  have hqT : 0 < q * T := Nat.mul_pos hq hT
  constructor
  · have := Nat.lt_of_mul_lt_mul_left (Nat.lt_of_le_of_lt l1 e2); omega
  · have := Nat.lt_of_mul_lt_mul_left (Nat.lt_of_le_of_lt e1 l2); omega

theorem sum_floor_le (x T : Nat) (shs : List Nat) :
    T * lsum (shs.map (fun s => x * s / T)) ≤ x * lsum shs := by
  induction shs with
  | nil => simp [lsum]
  | cons s l ih =>
    simp only [List.map, lsum, Nat.left_distrib]
    have := Nat.div_mul_le_self (x * s) T
    rw [Nat.mul_comm] at this
    omega

theorem sum_floor_ge (x T : Nat) (hT : 0 < T) (shs : List Nat) :
    x * lsum shs + shs.length ≤ T * lsum (shs.map (fun s => x * s / T)) + T * shs.length := by
  induction shs with
  | nil => simp [lsum]
  | cons s l ih =>
    simp only [List.map, lsum, List.length_cons, Nat.left_distrib, Nat.mul_one]
    have := (floor_spec (x * s) T hT).2
    omega

/-- **Claim 2e (solvency and dust).** If the shares sum to `T > 0`, the floored balances of
all holders sum to at most the (floored) supply `x`, and the undistributed dust is less than
one unit per holder. -/
theorem balances_solvent (x T : Nat) (shs : List Nat) (hT : 0 < T) (hsum : lsum shs = T) :
    lsum (shs.map (fun s => x * s / T)) ≤ x ∧
    x < lsum (shs.map (fun s => x * s / T)) + shs.length := by
  have h1 := sum_floor_le x T shs
  have h2 := sum_floor_ge x T hT shs
  rw [hsum] at h1 h2
  have hn : 0 < shs.length := by
    cases shs with
    | nil => simp [lsum] at hsum; omega
    | cons _ _ => simp
  generalize lsum (shs.map (fun s => x * s / T)) = B at *
  constructor
  · rw [Nat.mul_comm x T] at h1; exact Nat.le_of_mul_le_mul_left h1 hT
  · have h3 : T * x < T * (B + shs.length) := by
      rw [Nat.mul_comm x T] at h2; rw [Nat.left_distrib]; omega
    exact Nat.lt_of_mul_lt_mul_left h3

/-- **Claim 2f (rounding favours the pool).** The decay collected under floor rounding,
`S - ⌊S·p/q⌋`, is at least the exact decay `S·(q-p)/q`. -/
theorem floor_decay_ge_exact (S p q : Nat) (hq : 0 < q) (hp : p ≤ q) :
    S * (q - p) ≤ q * (S - S * p / q) := by
  have hk := (floor_spec (S * p) q hq).1
  have hkS : S * p / q ≤ S :=
    Nat.div_le_of_le_mul (by rw [Nat.mul_comm q S]; exact Nat.mul_le_mul_left S hp)
  generalize S * p / q = k at *
  obtain ⟨d, rfl⟩ := Nat.exists_eq_add_of_le hp
  obtain ⟨e, rfl⟩ := Nat.exists_eq_add_of_le hkS
  rw [Nat.add_sub_cancel_left, Nat.add_sub_cancel_left]
  npoly_omega

/-- Geometric decay `(p/q)^Δ` applied over a schedule of intervals, flooring at each update. -/
def geoFloor (p q : Nat) : Nat → List Nat → Nat
  | S, [] => S
  | S, l :: ls => geoFloor p q (S * p ^ l / q ^ l) ls

/-- **Claim 6b (rounded geometric decay).** For any schedule with total interval `Δ` and `k`
updates, the floored result `R` satisfies `R ≤ S·(p/q)^Δ ≤ R + k`: rounding is always in the
pool's favour and costs less than one unit per update. -/
theorem geoFloor_bounds (p q : Nat) (hq : 0 < q) (hpq : p ≤ q) (ls : List Nat) (S : Nat) :
    geoFloor p q S ls * q ^ lsum ls ≤ S * p ^ lsum ls ∧
    S * p ^ lsum ls ≤ (geoFloor p q S ls + ls.length) * q ^ lsum ls := by
  induction ls generalizing S with
  | nil => simp [geoFloor, lsum]
  | cons l ls ih =>
    simp only [geoFloor, lsum, List.length_cons, Nat.pow_add]
    have hA : 0 < q ^ l := Nat.pos_pow_of_pos l hq
    obtain ⟨f1, f2⟩ := floor_spec (S * p ^ l) (q ^ l) hA
    obtain ⟨i1, i2⟩ := ih (S * p ^ l / q ^ l)
    have hb : p ^ lsum ls ≤ q ^ lsum ls := Nat.pow_le_pow_left hpq _
    generalize S * p ^ l / q ^ l = S₁ at *
    generalize geoFloor p q S₁ ls = R at *
    generalize q ^ l = A at *
    generalize q ^ lsum ls = B at *
    generalize p ^ l = a at *
    generalize p ^ lsum ls = b at *
    have c1 := Nat.mul_le_mul_right A i1
    have c2 := Nat.mul_le_mul_right b f1
    have c3 := Nat.mul_le_mul_right b (Nat.le_of_lt f2)
    have c4 := Nat.mul_le_mul_right A i2
    have c5 := Nat.mul_le_mul_left A hb
    constructor <;> npoly_omega

/-- **Claim 6c.** Two rounded geometric schedules covering the same total interval differ by at
most the number of updates of the other: `R₁ ≤ R₂ + k₂`. -/
theorem geoFloor_schedule_gap (p q : Nat) (hq : 0 < q) (hpq : p ≤ q) (S : Nat)
    (l₁ l₂ : List Nat) (h : lsum l₁ = lsum l₂) :
    geoFloor p q S l₁ ≤ geoFloor p q S l₂ + l₂.length := by
  have a := (geoFloor_bounds p q hq hpq l₁ S).1
  have b := (geoFloor_bounds p q hq hpq l₂ S).2
  rw [h] at a
  have c := Nat.le_trans a b
  rw [Nat.mul_comm _ (q ^ lsum l₂), Nat.mul_comm _ (q ^ lsum l₂)] at c
  exact Nat.le_of_mul_le_mul_left c (Nat.pos_pow_of_pos _ hq)

end Demurrage

/-!
# Share accounting: proportional fairness and conservation (claims 1 and 5)

Holders own shares; the supply `S` is the only quantity that decays. A holder with `sh`
of `T` total shares owns `S · sh / T` (exact rational value, compared by cross-multiplication).
-/
namespace Demurrage

/-- **Claim 1 (proportional fairness).** Decay changes only `S`, so every holder's fraction
of the supply, `(S · sh / T) / S = sh / T`, is the same before and after: for any two holders,
the ratio of their balances is the ratio of their shares, whatever the supply. -/
theorem fair_ratio (S sh₁ sh₂ : Nat) : (S * sh₁) * sh₂ = (S * sh₂) * sh₁ := by
  rw [Nat.mul_assoc, Nat.mul_assoc, Nat.mul_comm sh₁ sh₂]

/-- The decay of the supply from `S` to `S'` reduces each balance by the same fraction:
`bal' · S = bal · S'` with `bal = S · sh / T`, `bal' = S' · sh / T` (cross-multiplied by `T`). -/
theorem fair_decay (S S' sh : Nat) : (S' * sh) * S = (S * sh) * S' := by
  rw [Nat.mul_comm S' sh, Nat.mul_comm S sh, Nat.mul_assoc, Nat.mul_assoc, Nat.mul_comm S' S]

/-- Operations on the pair (circulating supply `S`, collected pool `P`). -/
inductive Op where
  | decay (d : Nat)   -- move `d` of the supply into the pool (requires `d ≤ S`)
  | mint (m : Nat)    -- issue new tokens
  | burn (b : Nat)    -- destroy circulating tokens (requires `b ≤ S`)
  | payout (r : Nat)  -- pay rewards from the pool back into circulation (requires `r ≤ P`)

/-- One step; an operation whose requirement fails is rejected (state unchanged). -/
def step : Nat × Nat → Op → Nat × Nat
  | (S, P), .decay d => if d ≤ S then (S - d, P + d) else (S, P)
  | (S, P), .mint m => (S + m, P)
  | (S, P), .burn b => if b ≤ S then (S - b, P) else (S, P)
  | (S, P), .payout r => if r ≤ P then (S + r, P - r) else (S, P)

def run (st : Nat × Nat) (ops : List Op) : Nat × Nat := ops.foldl step st

/-- Total minted and burned by a sequence, counting only accepted burns. -/
def flows : Nat × Nat → List Op → Nat × Nat
  | _, [] => (0, 0)
  | st, o :: os =>
    let (m, b) := flows (step st o) os
    match o with
    | .mint x => (m + x, b)
    | .burn x => if x ≤ st.1 then (m, b + x) else (m, b)
    | _ => (m, b)

/-- **Claim 5 (conservation).** For every sequence of operations,
`S + P` at the end equals `S + P` at the start plus everything minted minus everything burned
(written without subtraction). -/
theorem conservation (st : Nat × Nat) (ops : List Op) :
    (run st ops).1 + (run st ops).2 + (flows st ops).2 = st.1 + st.2 + (flows st ops).1 := by
  induction ops generalizing st with
  | nil => simp [run, flows]
  | cons o os ih =>
    obtain ⟨S, P⟩ := st
    have h := ih (step (S, P) o)
    simp only [run, List.foldl] at h ⊢
    cases o with
    | decay d =>
      simp only [flows, step] at h ⊢
      split <;> split at h <;> simp_all <;> omega
    | mint m => simp only [flows, step] at h ⊢; omega
    | burn b =>
      simp only [flows, step] at h ⊢
      split <;> simp_all <;> omega
    | payout r =>
      simp only [flows, step] at h ⊢
      split <;> simp_all <;> omega

example : run (1000, 0) [.decay 10, .mint 5, .payout 4, .burn 3] = (996, 6) := by decide

end Demurrage