All proofs
Project-declaredLean 4.31.0 · mathlib@fabf563a7c95

Galois Autₛ fixed is Unit

ArkLib.Lattices.CyclotomicModulus.galoisAutₛ_fixed_isUnit

Project documentation

Core unit lemma. In S = Z_q[X]/(X^{2^α}+1), every nonzero σ_{-1}-fixed element is a unit. If b = mk g is not a unit then g shares a factor p_i with X^{2^α}+1 = p₁p₂; the reverse identity plus the swap p₁.reverse ~ p₂ force g to be divisible by both p₁ and p₂, hence by X^{2^α}+1, so b = 0.

Exact Lean statement

theorem galoisAutₛ_fixed_isUnit (hq5 : q % 8 = 5) {α : ℕ} (hα : 1 ≤ α)
    {b : (powTwoCyclotomic (R := ZMod q) α).CyclotomicRing}
    (hbfix : galoisAutₛ α (conjExp α) (conjExp_odd α) b = b) (hb0 : b ≠ 0) :
    IsUnit b

Formal artifact

Lean source

Canonical source
Full Lean sourceLean 4
theorem galoisAutₛ_fixed_isUnit (hq5 : q % 8 = 5) {α : } (hα : 1  α)    {b : (powTwoCyclotomic (R := ZMod q) α).CyclotomicRing}    (hbfix : galoisAutₛ α (conjExp α) (conjExp_odd α) b = b) (hb0 : b  0) :    IsUnit b := by  classical  obtain p₁, p₂, hp₁, hp₂, hcop, hf := exists_irreducible_factorization q hq5 hα  have hswap12 : Associated p₁.reverse p₂ := no_selfReciprocal_factor q hq5 hα hp₁ hp₂ hf  have hswap21 : Associated p₂.reverse p₁ :=    no_selfReciprocal_factor q hq5 hα hp₂ hp₁ (by rw [hf]; ring)  set mk := Ideal.Quotient.mk (powTwoCyclotomic (R := ZMod q) α).modIdeal with hmkdef  have hmk_zero :  z : (ZMod q)[X], mk z = 0  (X ^ (2 ^ α) + 1 : (ZMod q)[X]) ∣ z := fun z => by    rw [hmkdef, Ideal.Quotient.eq_zero_iff_mem, modIdeal, powTwoCyclotomic_toPoly,      Ideal.mem_span_singleton]  -- `mk X` is a unit (`(mk X)^{2^{α+1}} = 1`)  have hmkX_unit : IsUnit (mk X) :=    IsUnit.of_mul_eq_one ((mk X) ^ (conjExp α)) (by      rw [mul_comm,  pow_succ, conjExp, Nat.sub_add_cancel Nat.one_le_two_pow,  map_pow,        mk_X_pow_conductor_eq_one α])  obtain g, rfl := Ideal.Quotient.mk_surjective b  by_contra hbnu  have hncop : ¬ IsCoprime g (X ^ (2 ^ α) + 1 : (ZMod q)[X]) := by    rintro u, v, huv    refine hbnu (IsUnit.of_mul_eq_one (mk u) ?_)    have := congrArg mk huv    rwa [map_add, map_mul, map_mul, (hmk_zero _).mpr (dvd_refl _), mul_zero, add_zero, map_one,      mul_comm] at this  -- the key step: a factor `p` of `g` forces its "reverse partner" `p'` to divide `g` too  have keystep :  (p p' : (ZMod q)[X]), Associated p.reverse p'       p' ∣ (X ^ (2 ^ α) + 1 : (ZMod q)[X])  p ∣ g  p' ∣ g := by    intro p p' hpp' hp'f hpg    have hd1 : mk p' ∣ mk p.reverse := map_dvd mk hpp'.symm.dvd    rw [mk_reverse_eq_galoisAutₛ_mul q α p] at hd1    have hd2 : mk p' ∣ galoisAutₛ α (conjExp α) (conjExp_odd α) (mk p) :=      ((hmkX_unit.pow p.natDegree).dvd_mul_right).mp hd1    have hd3 : galoisAutₛ α (conjExp α) (conjExp_odd α) (mk p) ∣ mk g := by      obtain h, hh := hpg      refine galoisAutₛ α (conjExp α) (conjExp_odd α) (mk h), ?_      rw [ map_mul,  hbfix, hh, map_mul]    obtain c, hc := hd2.trans hd3    obtain c', rfl := Ideal.Quotient.mk_surjective c    have hz : (X ^ (2 ^ α) + 1 : (ZMod q)[X]) ∣ (g - p' * c') := by      rw [ hmk_zero, map_sub, map_mul,  hc, sub_self]    have : p' ∣ (g - p' * c') := hp'f.trans hz    simpa using dvd_add this (Dvd.intro c' rfl)  rw [hf, IsCoprime.mul_right_iff, not_and_or] at hncop  have hfg : (X ^ (2 ^ α) + 1 : (ZMod q)[X]) ∣ g := by    rw [hf]    rcases hncop with h1 | h2    · have hp1g : p₁ ∣ g := by        by_contra hnd        exact h1 (isCoprime_comm.mp ((hp₁.coprime_iff_not_dvd).mpr hnd))      exact hcop.mul_dvd hp1g (keystep p₁ p₂ hswap12 (hf ▸ dvd_mul_left p₂ p₁) hp1g)    · have hp2g : p₂ ∣ g := by        by_contra hnd        exact h2 (isCoprime_comm.mp ((hp₂.coprime_iff_not_dvd).mpr hnd))      exact hcop.mul_dvd (keystep p₂ p₁ hswap21 (hf ▸ dvd_mul_right p₁ p₂) hp2g) hp2g  exact hb0 ((hmk_zero g).mpr hfg)
Project
ArkLib
License
Apache-2.0
Commit
fad5cbf80877
Source
ArkLib/Data/Lattices/CyclotomicRing/Subfield/Field.lean:218-274

Reuse this declaration

Bring the exact result into your workflow

The import identifies the source module. Your project still needs the pinned package dependency shown on this page.

What this badge means

This completion status comes from the project or community source. It has not yet been represented here as an independent rebuild and axiom audit.

Continue in this project

Related declarations

Project-declaredLean 4.31.0

Affine gaps lifted to interleaved codes

affine_gaps_lifted_to_interleaved_codes

Project documentation

This lemma proves the final algebraic step in the DG25 Theorem 3.1 proof. It shows that if R > e + 1, then e * (R / (R - 1)) < e + 1. The intuition is that the fraction R / (R - 1) is always greater than 1, but as R gets larger, it gets closer to 1. The hypothesis R > e + 1 provides a strong enough bound to ensure the product e * (fraction) do...

cryptographyproof systemscoding theory

Source project: ArkLib

Person-level attribution pending.

View proof record
Project-declaredLean 4.31.0

Gadget Decompose coeff

ArkLib.Lattices.Ajtai.gadgetDecompose_coeff

Plain-language statement

The k-th coefficient (k < deg φ) of a gadget-decomposition block is exactly the corresponding digit of the corresponding input coefficient.

cryptographyproof systemscoding theory

Source project: ArkLib

Person-level attribution pending.

View proof record
Project-declaredLean 4.31.0

Gadget Decompose lawful

ArkLib.Lattices.Ajtai.gadgetDecompose_lawful

Plain-language statement

The base-b gadget decomposition is a lawful gadget decomposition.

cryptographyproof systemscoding theory

Source project: ArkLib

Person-level attribution pending.

View proof record