number_theory.legendre_symbol.gauss_sum
⟷
Mathlib.NumberTheory.LegendreSymbol.GaussSum
The following section lists changes to this file in mathlib3 and mathlib4 that occured after the initial port. Most recent changes are shown first. Hovering over a commit will show all commits associated with the same mathlib3 commit.
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(last sync)
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -3,8 +3,8 @@ Copyright (c) 2022 Michael Stoll. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Michael Stoll
-/
-import NumberTheory.LegendreSymbol.AddCharacter
-import NumberTheory.LegendreSymbol.ZmodChar
+import Algebra.Group.AddChar
+import NumberTheory.LegendreSymbol.ZModChar
import Algebra.CharP.CharAndCard
#align_import number_theory.legendre_symbol.gauss_sum from "leanprover-community/mathlib"@"08b63ab58a6ec1157ebeafcbbe6c7a3fb3c9f6d5"
@@ -193,7 +193,7 @@ theorem MulChar.IsQuadratic.gaussSum_frob_iter (n : ℕ) (hp : IsUnit (p : R)) {
induction' n with n ih
· rw [pow_zero, pow_one, pow_zero, MulChar.map_one, one_mul]
·
- rw [pow_succ, mul_comm p, pow_mul, ih, mul_pow, hχ.gauss_sum_frob _ hp, ← mul_assoc, pow_succ,
+ rw [pow_succ', mul_comm p, pow_mul, ih, mul_pow, hχ.gauss_sum_frob _ hp, ← mul_assoc, pow_succ',
mul_comm (p : R), map_mul, ← pow_apply' χ fp.1.Pos (p ^ n), hχ.pow_char p]
#align mul_char.is_quadratic.gauss_sum_frob_iter MulChar.IsQuadratic.gaussSum_frob_iter
-/
@@ -225,7 +225,7 @@ theorem Char.card_pow_char_pow {χ : MulChar R R'} (hχ : IsQuadratic χ) (ψ :
not_isUnit_prime_of_dvd_card p
((CharP.cast_eq_zero_iff R' p _).mp <| hg.resolve_left (is_unit_one.neg.map χ).NeZero) hp
rw [← hg]; apply mul_right_cancel₀ this
- rw [← hχ.gauss_sum_frob_iter p n hp ψ, ← pow_mul, mul_comm, ← pow_succ,
+ rw [← hχ.gauss_sum_frob_iter p n hp ψ, ← pow_mul, mul_comm, ← pow_succ',
Nat.two_mul_div_two_add_one_of_odd (fp.1.eq_two_or_odd'.resolve_left hp').pow]
#align char.card_pow_char_pow Char.card_pow_char_pow
-/
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -220,7 +220,7 @@ theorem Char.card_pow_char_pow {χ : MulChar R R'} (hχ : IsQuadratic χ) (ψ :
(χ (-1) * Fintype.card R) ^ (p ^ n / 2) = χ (p ^ n) :=
by
have : gaussSum χ ψ ≠ 0 := by
- intro hf; rw [hf, zero_pow (by norm_num : 0 < 2), eq_comm, mul_eq_zero] at hg
+ intro hf; rw [hf, zero_pow (by norm_num : 0 < 2), eq_comm, mul_eq_zero] at hg
exact
not_isUnit_prime_of_dvd_card p
((CharP.cast_eq_zero_iff R' p _).mp <| hg.resolve_left (is_unit_one.neg.map χ).NeZero) hp
@@ -248,7 +248,7 @@ theorem Char.card_pow_card {F : Type _} [Field F] [Fintype F] {F' : Type _} [Fie
simp only [← MulChar.ringHomComp_apply]
haveI := Fact.mk hp'
haveI := Fact.mk (hchar.subst hp')
- rw [Ne, ← Nat.prime_dvd_prime_iff_eq hp' hp, ← isUnit_iff_not_dvd_char, hchar] at hch₁
+ rw [Ne, ← Nat.prime_dvd_prime_iff_eq hp' hp, ← isUnit_iff_not_dvd_char, hchar] at hch₁
exact
Char.card_pow_char_pow (hχ₂.comp _) ψ.char (ringChar FF') n' hch₁ (hchar ▸ hch₂)
(gaussSum_sq (hχ₁.comp <| RingHom.injective _) (hχ₂.comp _) ψ.prim)
@@ -295,7 +295,7 @@ theorem FiniteField.two_pow_card {F : Type _} [Fintype F] [Field F] (hF : ringCh
have hu : IsUnit (ringChar FF : ZMod 8) :=
by
rw [isUnit_iff_not_dvd_char, ring_char_zmod_n]
- rw [Ne, ← Nat.prime_dvd_prime_iff_eq FFp Nat.prime_two] at hFF
+ rw [Ne, ← Nat.prime_dvd_prime_iff_eq FFp Nat.prime_two] at hFF
change ¬_ ∣ 2 ^ 3
exact mt FFp.dvd_of_dvd_pow hFF
-- there is a primitive additive character `ℤ/8ℤ → FF`, sending `a + 8ℤ ↦ τ^a`
@@ -340,7 +340,7 @@ theorem FiniteField.two_pow_card {F : Type _} [Fintype F] [Field F] (hF : ringCh
simpa only [hχ, one_mul, card, gaussSum, ← h₅, h₁] using h
-- this allows us to apply `card_pow_char_pow` to our situation
have h := Char.card_pow_char_pow hq ψ₈.char (ringChar FF) n hu hFF hg
- rw [card, ← hchar, hχ, one_mul, ← hc, ← Nat.cast_pow (ringChar F), ← hc] at h
+ rw [card, ← hchar, hχ, one_mul, ← hc, ← Nat.cast_pow (ringChar F), ← hc] at h
-- finally, we change `2` to `8` on the left hand side
convert_to (8 : F) ^ (Fintype.card F / 2) = _
·
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -125,11 +125,14 @@ theorem gaussSum_mul_gaussSum_eq_card {χ : MulChar R R'} (hχ : IsNontrivial χ
simp_rw [gauss_sum_mul_aux hχ ψ]
rw [Finset.sum_comm]
classical
+ -- to get `[decidable_eq R]` for `sum_mul_shift`
+ simp_rw [← Finset.mul_sum, sum_mul_shift _ hψ, sub_eq_zero, mul_ite, MulZeroClass.mul_zero]
+ rw [Finset.sum_ite_eq' Finset.univ (1 : R)]
+ simp only [Finset.mem_univ, map_one, one_mul, if_true]
#align gauss_sum_mul_gauss_sum_eq_card gaussSum_mul_gaussSum_eq_card
-/
#print gaussSum_sq /-
--- to get `[decidable_eq R]` for `sum_mul_shift`
/-- When `χ` is a nontrivial quadratic character, then the square of `gauss_sum χ ψ`
is `χ(-1)` times the cardinality of `R`. -/
theorem gaussSum_sq {χ : MulChar R R'} (hχ₁ : IsNontrivial χ) (hχ₂ : IsQuadratic χ)
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -125,14 +125,11 @@ theorem gaussSum_mul_gaussSum_eq_card {χ : MulChar R R'} (hχ : IsNontrivial χ
simp_rw [gauss_sum_mul_aux hχ ψ]
rw [Finset.sum_comm]
classical
- -- to get `[decidable_eq R]` for `sum_mul_shift`
- simp_rw [← Finset.mul_sum, sum_mul_shift _ hψ, sub_eq_zero, mul_ite, MulZeroClass.mul_zero]
- rw [Finset.sum_ite_eq' Finset.univ (1 : R)]
- simp only [Finset.mem_univ, map_one, one_mul, if_true]
#align gauss_sum_mul_gauss_sum_eq_card gaussSum_mul_gaussSum_eq_card
-/
#print gaussSum_sq /-
+-- to get `[decidable_eq R]` for `sum_mul_shift`
/-- When `χ` is a nontrivial quadratic character, then the square of `gauss_sum χ ψ`
is `χ(-1)` times the cardinality of `R`. -/
theorem gaussSum_sq {χ : MulChar R R'} (hχ₁ : IsNontrivial χ) (hχ₂ : IsQuadratic χ)
mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451
@@ -3,9 +3,9 @@ Copyright (c) 2022 Michael Stoll. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Michael Stoll
-/
-import Mathbin.NumberTheory.LegendreSymbol.AddCharacter
-import Mathbin.NumberTheory.LegendreSymbol.ZmodChar
-import Mathbin.Algebra.CharP.CharAndCard
+import NumberTheory.LegendreSymbol.AddCharacter
+import NumberTheory.LegendreSymbol.ZmodChar
+import Algebra.CharP.CharAndCard
#align_import number_theory.legendre_symbol.gauss_sum from "leanprover-community/mathlib"@"08b63ab58a6ec1157ebeafcbbe6c7a3fb3c9f6d5"
mathlib commit https://github.com/leanprover-community/mathlib/commit/8ea5598db6caeddde6cb734aa179cc2408dbd345
@@ -2,16 +2,13 @@
Copyright (c) 2022 Michael Stoll. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Michael Stoll
-
-! This file was ported from Lean 3 source module number_theory.legendre_symbol.gauss_sum
-! leanprover-community/mathlib commit 08b63ab58a6ec1157ebeafcbbe6c7a3fb3c9f6d5
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
-/
import Mathbin.NumberTheory.LegendreSymbol.AddCharacter
import Mathbin.NumberTheory.LegendreSymbol.ZmodChar
import Mathbin.Algebra.CharP.CharAndCard
+#align_import number_theory.legendre_symbol.gauss_sum from "leanprover-community/mathlib"@"08b63ab58a6ec1157ebeafcbbe6c7a3fb3c9f6d5"
+
/-!
# Gauss sums
mathlib commit https://github.com/leanprover-community/mathlib/commit/9240e8be927a0955b9a82c6c85ef499ee3a626b8
@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
Authors: Michael Stoll
! This file was ported from Lean 3 source module number_theory.legendre_symbol.gauss_sum
-! leanprover-community/mathlib commit e3f4be1fcb5376c4948d7f095bec45350bfb9d1a
+! leanprover-community/mathlib commit 08b63ab58a6ec1157ebeafcbbe6c7a3fb3c9f6d5
! Please do not edit these lines, except to modify the commit id
! if you have ported upstream changes.
-/
@@ -15,6 +15,9 @@ import Mathbin.Algebra.CharP.CharAndCard
/-!
# Gauss sums
+> THIS FILE IS SYNCHRONIZED WITH MATHLIB4.
+> Any changes to this file require a corresponding PR to mathlib4.
+
We define the Gauss sum associated to a multiplicative and an additive
character of a finite field and prove some results about them.
mathlib commit https://github.com/leanprover-community/mathlib/commit/fdc286cc6967a012f41b87f76dcd2797b53152af
@@ -70,11 +70,14 @@ variable {R' : Type v} [CommRing R']
-/
+#print gaussSum /-
/-- Definition of the Gauss sum associated to a multiplicative and an additive character. -/
def gaussSum (χ : MulChar R R') (ψ : AddChar R R') : R' :=
∑ a, χ a * ψ a
#align gauss_sum gaussSum
+-/
+#print gaussSum_mulShift /-
/-- Replacing `ψ` by `mul_shift ψ a` and multiplying the Gauss sum by `χ a` does not change it. -/
theorem gaussSum_mulShift (χ : MulChar R R') (ψ : AddChar R R') (a : Rˣ) :
χ a * gaussSum χ (mulShift ψ a) = gaussSum χ ψ :=
@@ -83,6 +86,7 @@ theorem gaussSum_mulShift (χ : MulChar R R') (ψ : AddChar R R') (a : Rˣ) :
simp_rw [← mul_assoc, ← map_mul]
exact Fintype.sum_bijective _ a.mul_left_bijective _ _ fun x => rfl
#align gauss_sum_mul_shift gaussSum_mulShift
+-/
end GaussSumDef
@@ -110,6 +114,7 @@ private theorem gauss_sum_mul_aux {χ : MulChar R R'} (hχ : IsNontrivial χ) (
refine' (Fintype.sum_bijective _ (mulLeft_bijective₀ b hb) _ _ fun x => _).symm
rw [mul_assoc, mul_comm x, ← mul_assoc, mul_inv_cancel hb, one_mul, mul_sub, mul_one]
+#print gaussSum_mul_gaussSum_eq_card /-
/-- We have `gauss_sum χ ψ * gauss_sum χ⁻¹ ψ⁻¹ = fintype.card R`
when `χ` is nontrivial and `ψ` is primitive (and `R` is a field). -/
theorem gaussSum_mul_gaussSum_eq_card {χ : MulChar R R'} (hχ : IsNontrivial χ) {ψ : AddChar R R'}
@@ -125,7 +130,9 @@ theorem gaussSum_mul_gaussSum_eq_card {χ : MulChar R R'} (hχ : IsNontrivial χ
rw [Finset.sum_ite_eq' Finset.univ (1 : R)]
simp only [Finset.mem_univ, map_one, one_mul, if_true]
#align gauss_sum_mul_gauss_sum_eq_card gaussSum_mul_gaussSum_eq_card
+-/
+#print gaussSum_sq /-
/-- When `χ` is a nontrivial quadratic character, then the square of `gauss_sum χ ψ`
is `χ(-1)` times the cardinality of `R`. -/
theorem gaussSum_sq {χ : MulChar R R'} (hχ₁ : IsNontrivial χ) (hχ₂ : IsQuadratic χ)
@@ -136,6 +143,7 @@ theorem gaussSum_sq {χ : MulChar R R'} (hχ₁ : IsNontrivial χ) (hχ₂ : IsQ
rw [mul_comm, ← gaussSum_mulShift _ _ (-1 : Rˣ), inv_mul_shift]
rfl
#align gauss_sum_sq gaussSum_sq
+-/
end GaussSumProd
@@ -151,6 +159,7 @@ variable {R : Type u} [CommRing R] [Fintype R] {R' : Type v} [CommRing R']
-- We assume that the target ring `R'` has prime characteristic `p`.
variable (p : ℕ) [fp : Fact p.Prime] [hch : CharP R' p]
+#print gaussSum_frob /-
/-- When `R'` has prime characteristic `p`, then the `p`th power of the Gauss sum
of `χ` and `ψ` is the Gauss sum of `χ^p` and `ψ^p`. -/
theorem gaussSum_frob (χ : MulChar R R') (ψ : AddChar R R') :
@@ -160,7 +169,9 @@ theorem gaussSum_frob (χ : MulChar R R') (ψ : AddChar R R') :
simp_rw [pow_apply' χ fp.1.Pos, map_mul, frobenius_def]
rfl
#align gauss_sum_frob gaussSum_frob
+-/
+#print MulChar.IsQuadratic.gaussSum_frob /-
/-- For a quadratic character `χ` and when the characteristic `p` of the target ring
is a unit in the source ring, the `p`th power of the Gauss sum of`χ` and `ψ` is
`χ p` times the original Gauss sum. -/
@@ -170,7 +181,9 @@ theorem MulChar.IsQuadratic.gaussSum_frob (hp : IsUnit (p : R)) {χ : MulChar R
hp.unit_spec, ← pow_two, ← pow_apply' _ (by norm_num : 0 < 2), hχ.sq_eq_one, ← hp.unit_spec,
one_apply_coe, one_mul]
#align mul_char.is_quadratic.gauss_sum_frob MulChar.IsQuadratic.gaussSum_frob
+-/
+#print MulChar.IsQuadratic.gaussSum_frob_iter /-
/-- For a quadratic character `χ` and when the characteristic `p` of the target ring
is a unit in the source ring and `n` is a natural number, the `p^n`th power of the Gauss
sum of`χ` and `ψ` is `χ (p^n)` times the original Gauss sum. -/
@@ -183,6 +196,7 @@ theorem MulChar.IsQuadratic.gaussSum_frob_iter (n : ℕ) (hp : IsUnit (p : R)) {
rw [pow_succ, mul_comm p, pow_mul, ih, mul_pow, hχ.gauss_sum_frob _ hp, ← mul_assoc, pow_succ,
mul_comm (p : R), map_mul, ← pow_apply' χ fp.1.Pos (p ^ n), hχ.pow_char p]
#align mul_char.is_quadratic.gauss_sum_frob_iter MulChar.IsQuadratic.gaussSum_frob_iter
+-/
end gaussSum_frob
@@ -195,6 +209,7 @@ section GaussSumValues
variable {R : Type u} [CommRing R] [Fintype R] {R' : Type v} [CommRing R'] [IsDomain R']
+#print Char.card_pow_char_pow /-
/-- If the square of the Gauss sum of a quadratic character is `χ(-1) * #R`,
then we get, for all `n : ℕ`, the relation `(χ(-1) * #R) ^ (p^n/2) = χ(p^n)`,
where `p` is the (odd) characteristic of the target ring `R'`.
@@ -213,7 +228,9 @@ theorem Char.card_pow_char_pow {χ : MulChar R R'} (hχ : IsQuadratic χ) (ψ :
rw [← hχ.gauss_sum_frob_iter p n hp ψ, ← pow_mul, mul_comm, ← pow_succ,
Nat.two_mul_div_two_add_one_of_odd (fp.1.eq_two_or_odd'.resolve_left hp').pow]
#align char.card_pow_char_pow Char.card_pow_char_pow
+-/
+#print Char.card_pow_card /-
/-- When `F` and `F'` are finite fields and `χ : F → F'` is a nontrivial quadratic character,
then `(χ(-1) * #F)^(#F'/2) = χ(#F')`. -/
theorem Char.card_pow_card {F : Type _} [Field F] [Fintype F] {F' : Type _} [Field F'] [Fintype F']
@@ -236,6 +253,7 @@ theorem Char.card_pow_card {F : Type _} [Field F] [Fintype F] {F' : Type _} [Fie
Char.card_pow_char_pow (hχ₂.comp _) ψ.char (ringChar FF') n' hch₁ (hchar ▸ hch₂)
(gaussSum_sq (hχ₁.comp <| RingHom.injective _) (hχ₂.comp _) ψ.prim)
#align char.card_pow_card Char.card_pow_card
+-/
end GaussSumValues
@@ -257,6 +275,7 @@ in this way, the result is reduced to `card_pow_char_pow`.
open ZMod
+#print FiniteField.two_pow_card /-
/-- For every finite field `F` of odd characteristic, we have `2^(#F/2) = χ₈(#F)` in `F`. -/
theorem FiniteField.two_pow_card {F : Type _} [Fintype F] [Field F] (hF : ringChar F ≠ 2) :
(2 : F) ^ (Fintype.card F / 2) = χ₈ (Fintype.card F) :=
@@ -331,6 +350,7 @@ theorem FiniteField.two_pow_card {F : Type _} [Fintype F] [Field F] (hF : ringCh
simp only [map_pow, map_bit0, map_one, map_intCast]
convert h; norm_num
#align finite_field.two_pow_card FiniteField.two_pow_card
+-/
end GaussSumTwo
mathlib commit https://github.com/leanprover-community/mathlib/commit/d30d31261cdb4d2f5e612eabc3c4bf45556350d5
@@ -286,7 +286,7 @@ theorem FiniteField.two_pow_card {F : Type _} [Fintype F] [Field F] (hF : ringCh
have τ_spec : τ ^ 4 = -1 := by
refine' (sq_eq_one_iff.1 _).resolve_left _ <;>
· simp only [τ, ← map_nsmul_pow]
- erw [AddChar.IsPrimitive.zMod_char_eq_one_iff 8 ψ₈.prim]
+ erw [AddChar.IsPrimitive.zmod_char_eq_one_iff 8 ψ₈.prim]
decide
-- we consider `χ₈` as a multiplicative character `ℤ/8ℤ → FF`
let χ := χ₈.ring_hom_comp (Int.castRingHom FF)
mathlib commit https://github.com/leanprover-community/mathlib/commit/bf9bbbcf0c1c1ead18280b0d010e417b10abb1b6
@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
Authors: Michael Stoll
! This file was ported from Lean 3 source module number_theory.legendre_symbol.gauss_sum
-! leanprover-community/mathlib commit d11893b411025250c8e61ff2f12ccbd7ee35ab15
+! leanprover-community/mathlib commit e3f4be1fcb5376c4948d7f095bec45350bfb9d1a
! Please do not edit these lines, except to modify the commit id
! if you have ported upstream changes.
-/
@@ -295,17 +295,30 @@ theorem FiniteField.two_pow_card {F : Type _} [Fintype F] [Field F] (hF : ringCh
-- we now show that the Gauss sum of `χ` and `ψ₈` has the relevant property
have hg : gaussSum χ ψ₈.char ^ 2 = χ (-1) * Fintype.card (ZMod 8) :=
by
- rw [hχ, one_mul, card, gaussSum]
- convert ← congr_arg (· ^ 2) (Fin.sum_univ_eight fun x => (χ₈ x : FF) * τ ^ x.val)
- · ext; congr; apply pow_one
- convert_to (0 + 1 * τ ^ 1 + 0 + -1 * τ ^ 3 + 0 + -1 * τ ^ 5 + 0 + 1 * τ ^ 7) ^ 2 = _
- · simp only [χ₈_apply, Matrix.cons_val_zero, Matrix.cons_val_one, Matrix.head_cons,
- Matrix.cons_vec_bit0_eq_alt0, Matrix.cons_vec_bit1_eq_alt1, Matrix.cons_vecAppend,
- Matrix.cons_vecAlt0, Matrix.cons_vecAlt1, Int.cast_zero, Int.cast_one, Int.cast_neg,
- MulZeroClass.zero_mul]
- rfl
- convert_to 8 + (τ ^ 4 + 1) * (τ ^ 10 - 2 * τ ^ 8 - 2 * τ ^ 6 + 6 * τ ^ 4 + τ ^ 2 - 8) = _
- · ring; · rw [τ_spec]; norm_num
+ have h := congr_arg (· ^ 2) (Fin.sum_univ_eight fun x => (χ₈ x : FF) * τ ^ x.1)
+ have h₁ : (fun i : Fin 8 => ↑(χ₈ i) * τ ^ i.val) = fun a : ZMod 8 => χ a * ψ₈.char a := by ext;
+ congr; apply pow_one
+ have h₂ :
+ (0 + 1 * τ ^ 1 + 0 + -1 * τ ^ 3 + 0 + -1 * τ ^ 5 + 0 + 1 * τ ^ 7) ^ 2 =
+ 8 + (τ ^ 4 + 1) * (τ ^ 10 - 2 * τ ^ 8 - 2 * τ ^ 6 + 6 * τ ^ 4 + τ ^ 2 - 8) :=
+ by ring
+ have h₃ : 8 + (τ ^ 4 + 1) * (τ ^ 10 - 2 * τ ^ 8 - 2 * τ ^ 6 + 6 * τ ^ 4 + τ ^ 2 - 8) = ↑8 := by
+ rw [τ_spec]; norm_num
+ have h₄ : (0 + 1 * τ ^ 1 + 0 + -1 * τ ^ 3 + 0 + -1 * τ ^ 5 + 0 + 1 * τ ^ 7) ^ 2 = ↑8 := by
+ rw [← h₃, ← h₂]
+ have h₅ :
+ (fun x : FF => x ^ 2)
+ (↑(χ₈ 0) * τ ^ 0 + ↑(χ₈ 1) * τ ^ 1 + ↑(χ₈ 2) * τ ^ 2 + ↑(χ₈ 3) * τ ^ 3 + ↑(χ₈ 4) * τ ^ 4 +
+ ↑(χ₈ 5) * τ ^ 5 +
+ ↑(χ₈ 6) * τ ^ 6 +
+ ↑(χ₈ 7) * τ ^ 7) =
+ ↑8 :=
+ by
+ simp only [← h₄, χ₈_apply, Matrix.cons_val_zero, algebraMap.coe_zero, MulZeroClass.zero_mul,
+ Matrix.cons_val_one, Matrix.head_cons, algebraMap.coe_one, Matrix.cons_vec_bit0_eq_alt0,
+ Matrix.cons_vecAppend, Matrix.cons_vecAlt0, Matrix.cons_vec_bit1_eq_alt1,
+ Matrix.cons_vecAlt1, Int.cast_neg]
+ simpa only [hχ, one_mul, card, gaussSum, ← h₅, h₁] using h
-- this allows us to apply `card_pow_char_pow` to our situation
have h := Char.card_pow_char_pow hq ψ₈.char (ringChar FF) n hu hFF hg
rw [card, ← hchar, hχ, one_mul, ← hc, ← Nat.cast_pow (ringChar F), ← hc] at h
mathlib commit https://github.com/leanprover-community/mathlib/commit/9fb8964792b4237dac6200193a0d533f1b3f7423
@@ -151,8 +151,6 @@ variable {R : Type u} [CommRing R] [Fintype R] {R' : Type v} [CommRing R']
-- We assume that the target ring `R'` has prime characteristic `p`.
variable (p : ℕ) [fp : Fact p.Prime] [hch : CharP R' p]
-include fp hch
-
/-- When `R'` has prime characteristic `p`, then the `p`th power of the Gauss sum
of `χ` and `ψ` is the Gauss sum of `χ^p` and `ψ^p`. -/
theorem gaussSum_frob (χ : MulChar R R') (ψ : AddChar R R') :
mathlib commit https://github.com/leanprover-community/mathlib/commit/a3e83f0fa4391c8740f7d773a7a9b74e311ae2a3
@@ -99,7 +99,7 @@ variable {R : Type u} [Field R] [Fintype R] {R' : Type v} [CommRing R'] [IsDomai
-- A helper lemma for `gauss_sum_mul_gauss_sum_eq_card` below
-- Is this useful enough in other contexts to be public?
private theorem gauss_sum_mul_aux {χ : MulChar R R'} (hχ : IsNontrivial χ) (ψ : AddChar R R')
- (b : R) : (∑ a, χ (a * b⁻¹) * ψ (a - b)) = ∑ c, χ c * ψ (b * (c - 1)) :=
+ (b : R) : ∑ a, χ (a * b⁻¹) * ψ (a - b) = ∑ c, χ c * ψ (b * (c - 1)) :=
by
cases' eq_or_ne b 0 with hb hb
· -- case `b = 0`
mathlib commit https://github.com/leanprover-community/mathlib/commit/5f25c089cb34db4db112556f23c50d12da81b297
@@ -120,10 +120,10 @@ theorem gaussSum_mul_gaussSum_eq_card {χ : MulChar R R'} (hχ : IsNontrivial χ
simp_rw [gauss_sum_mul_aux hχ ψ]
rw [Finset.sum_comm]
classical
- -- to get `[decidable_eq R]` for `sum_mul_shift`
- simp_rw [← Finset.mul_sum, sum_mul_shift _ hψ, sub_eq_zero, mul_ite, MulZeroClass.mul_zero]
- rw [Finset.sum_ite_eq' Finset.univ (1 : R)]
- simp only [Finset.mem_univ, map_one, one_mul, if_true]
+ -- to get `[decidable_eq R]` for `sum_mul_shift`
+ simp_rw [← Finset.mul_sum, sum_mul_shift _ hψ, sub_eq_zero, mul_ite, MulZeroClass.mul_zero]
+ rw [Finset.sum_ite_eq' Finset.univ (1 : R)]
+ simp only [Finset.mem_univ, map_one, one_mul, if_true]
#align gauss_sum_mul_gauss_sum_eq_card gaussSum_mul_gaussSum_eq_card
/-- When `χ` is a nontrivial quadratic character, then the square of `gauss_sum χ ψ`
@@ -298,9 +298,9 @@ theorem FiniteField.two_pow_card {F : Type _} [Fintype F] [Field F] (hF : ringCh
have hg : gaussSum χ ψ₈.char ^ 2 = χ (-1) * Fintype.card (ZMod 8) :=
by
rw [hχ, one_mul, card, gaussSum]
- convert← congr_arg (· ^ 2) (Fin.sum_univ_eight fun x => (χ₈ x : FF) * τ ^ x.val)
+ convert ← congr_arg (· ^ 2) (Fin.sum_univ_eight fun x => (χ₈ x : FF) * τ ^ x.val)
· ext; congr; apply pow_one
- convert_to(0 + 1 * τ ^ 1 + 0 + -1 * τ ^ 3 + 0 + -1 * τ ^ 5 + 0 + 1 * τ ^ 7) ^ 2 = _
+ convert_to (0 + 1 * τ ^ 1 + 0 + -1 * τ ^ 3 + 0 + -1 * τ ^ 5 + 0 + 1 * τ ^ 7) ^ 2 = _
· simp only [χ₈_apply, Matrix.cons_val_zero, Matrix.cons_val_one, Matrix.head_cons,
Matrix.cons_vec_bit0_eq_alt0, Matrix.cons_vec_bit1_eq_alt1, Matrix.cons_vecAppend,
Matrix.cons_vecAlt0, Matrix.cons_vecAlt1, Int.cast_zero, Int.cast_one, Int.cast_neg,
@@ -312,7 +312,7 @@ theorem FiniteField.two_pow_card {F : Type _} [Fintype F] [Field F] (hF : ringCh
have h := Char.card_pow_char_pow hq ψ₈.char (ringChar FF) n hu hFF hg
rw [card, ← hchar, hχ, one_mul, ← hc, ← Nat.cast_pow (ringChar F), ← hc] at h
-- finally, we change `2` to `8` on the left hand side
- convert_to(8 : F) ^ (Fintype.card F / 2) = _
+ convert_to (8 : F) ^ (Fintype.card F / 2) = _
·
rw [(by norm_num : (8 : F) = 2 ^ 2 * 2), mul_pow,
(FiniteField.isSquare_iff hF <| hp2 2).mp ⟨2, pow_two 2⟩, one_mul]
mathlib commit https://github.com/leanprover-community/mathlib/commit/cca40788df1b8755d5baf17ab2f27dacc2e17acb
@@ -207,7 +207,7 @@ theorem Char.card_pow_char_pow {χ : MulChar R R'} (hχ : IsQuadratic χ) (ψ :
(χ (-1) * Fintype.card R) ^ (p ^ n / 2) = χ (p ^ n) :=
by
have : gaussSum χ ψ ≠ 0 := by
- intro hf; rw [hf, zero_pow (by norm_num : 0 < 2), eq_comm, mul_eq_zero] at hg
+ intro hf; rw [hf, zero_pow (by norm_num : 0 < 2), eq_comm, mul_eq_zero] at hg
exact
not_isUnit_prime_of_dvd_card p
((CharP.cast_eq_zero_iff R' p _).mp <| hg.resolve_left (is_unit_one.neg.map χ).NeZero) hp
@@ -233,7 +233,7 @@ theorem Char.card_pow_card {F : Type _} [Field F] [Fintype F] {F' : Type _} [Fie
simp only [← MulChar.ringHomComp_apply]
haveI := Fact.mk hp'
haveI := Fact.mk (hchar.subst hp')
- rw [Ne, ← Nat.prime_dvd_prime_iff_eq hp' hp, ← isUnit_iff_not_dvd_char, hchar] at hch₁
+ rw [Ne, ← Nat.prime_dvd_prime_iff_eq hp' hp, ← isUnit_iff_not_dvd_char, hchar] at hch₁
exact
Char.card_pow_char_pow (hχ₂.comp _) ψ.char (ringChar FF') n' hch₁ (hchar ▸ hch₂)
(gaussSum_sq (hχ₁.comp <| RingHom.injective _) (hχ₂.comp _) ψ.prim)
@@ -278,7 +278,7 @@ theorem FiniteField.two_pow_card {F : Type _} [Fintype F] [Field F] (hF : ringCh
have hu : IsUnit (ringChar FF : ZMod 8) :=
by
rw [isUnit_iff_not_dvd_char, ring_char_zmod_n]
- rw [Ne, ← Nat.prime_dvd_prime_iff_eq FFp Nat.prime_two] at hFF
+ rw [Ne, ← Nat.prime_dvd_prime_iff_eq FFp Nat.prime_two] at hFF
change ¬_ ∣ 2 ^ 3
exact mt FFp.dvd_of_dvd_pow hFF
-- there is a primitive additive character `ℤ/8ℤ → FF`, sending `a + 8ℤ ↦ τ^a`
@@ -299,7 +299,7 @@ theorem FiniteField.two_pow_card {F : Type _} [Fintype F] [Field F] (hF : ringCh
by
rw [hχ, one_mul, card, gaussSum]
convert← congr_arg (· ^ 2) (Fin.sum_univ_eight fun x => (χ₈ x : FF) * τ ^ x.val)
- · ext; congr ; apply pow_one
+ · ext; congr; apply pow_one
convert_to(0 + 1 * τ ^ 1 + 0 + -1 * τ ^ 3 + 0 + -1 * τ ^ 5 + 0 + 1 * τ ^ 7) ^ 2 = _
· simp only [χ₈_apply, Matrix.cons_val_zero, Matrix.cons_val_one, Matrix.head_cons,
Matrix.cons_vec_bit0_eq_alt0, Matrix.cons_vec_bit1_eq_alt1, Matrix.cons_vecAppend,
@@ -310,7 +310,7 @@ theorem FiniteField.two_pow_card {F : Type _} [Fintype F] [Field F] (hF : ringCh
· ring; · rw [τ_spec]; norm_num
-- this allows us to apply `card_pow_char_pow` to our situation
have h := Char.card_pow_char_pow hq ψ₈.char (ringChar FF) n hu hFF hg
- rw [card, ← hchar, hχ, one_mul, ← hc, ← Nat.cast_pow (ringChar F), ← hc] at h
+ rw [card, ← hchar, hχ, one_mul, ← hc, ← Nat.cast_pow (ringChar F), ← hc] at h
-- finally, we change `2` to `8` on the left hand side
convert_to(8 : F) ^ (Fintype.card F / 2) = _
·
mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb
@@ -53,7 +53,7 @@ additive character, multiplicative character, Gauss sum
universe u v
-open BigOperators
+open scoped BigOperators
open AddChar MulChar
mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb
@@ -207,13 +207,11 @@ theorem Char.card_pow_char_pow {χ : MulChar R R'} (hχ : IsQuadratic χ) (ψ :
(χ (-1) * Fintype.card R) ^ (p ^ n / 2) = χ (p ^ n) :=
by
have : gaussSum χ ψ ≠ 0 := by
- intro hf
- rw [hf, zero_pow (by norm_num : 0 < 2), eq_comm, mul_eq_zero] at hg
+ intro hf; rw [hf, zero_pow (by norm_num : 0 < 2), eq_comm, mul_eq_zero] at hg
exact
not_isUnit_prime_of_dvd_card p
((CharP.cast_eq_zero_iff R' p _).mp <| hg.resolve_left (is_unit_one.neg.map χ).NeZero) hp
- rw [← hg]
- apply mul_right_cancel₀ this
+ rw [← hg]; apply mul_right_cancel₀ this
rw [← hχ.gauss_sum_frob_iter p n hp ψ, ← pow_mul, mul_comm, ← pow_succ,
Nat.two_mul_div_two_add_one_of_odd (fp.1.eq_two_or_odd'.resolve_left hp').pow]
#align char.card_pow_char_pow Char.card_pow_char_pow
@@ -301,9 +299,7 @@ theorem FiniteField.two_pow_card {F : Type _} [Fintype F] [Field F] (hF : ringCh
by
rw [hχ, one_mul, card, gaussSum]
convert← congr_arg (· ^ 2) (Fin.sum_univ_eight fun x => (χ₈ x : FF) * τ ^ x.val)
- · ext
- congr
- apply pow_one
+ · ext; congr ; apply pow_one
convert_to(0 + 1 * τ ^ 1 + 0 + -1 * τ ^ 3 + 0 + -1 * τ ^ 5 + 0 + 1 * τ ^ 7) ^ 2 = _
· simp only [χ₈_apply, Matrix.cons_val_zero, Matrix.cons_val_one, Matrix.head_cons,
Matrix.cons_vec_bit0_eq_alt0, Matrix.cons_vec_bit1_eq_alt1, Matrix.cons_vecAppend,
@@ -311,9 +307,7 @@ theorem FiniteField.two_pow_card {F : Type _} [Fintype F] [Field F] (hF : ringCh
MulZeroClass.zero_mul]
rfl
convert_to 8 + (τ ^ 4 + 1) * (τ ^ 10 - 2 * τ ^ 8 - 2 * τ ^ 6 + 6 * τ ^ 4 + τ ^ 2 - 8) = _
- · ring
- · rw [τ_spec]
- norm_num
+ · ring; · rw [τ_spec]; norm_num
-- this allows us to apply `card_pow_char_pow` to our situation
have h := Char.card_pow_char_pow hq ψ₈.char (ringChar FF) n hu hFF hg
rw [card, ← hchar, hχ, one_mul, ← hc, ← Nat.cast_pow (ringChar F), ← hc] at h
@@ -324,8 +318,7 @@ theorem FiniteField.two_pow_card {F : Type _} [Fintype F] [Field F] (hF : ringCh
(FiniteField.isSquare_iff hF <| hp2 2).mp ⟨2, pow_two 2⟩, one_mul]
apply (algebraMap F FF).Injective
simp only [map_pow, map_bit0, map_one, map_intCast]
- convert h
- norm_num
+ convert h; norm_num
#align finite_field.two_pow_card FiniteField.two_pow_card
end GaussSumTwo
mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb
@@ -109,7 +109,6 @@ private theorem gauss_sum_mul_aux {χ : MulChar R R'} (hχ : IsNontrivial χ) (
· -- case `b ≠ 0`
refine' (Fintype.sum_bijective _ (mulLeft_bijective₀ b hb) _ _ fun x => _).symm
rw [mul_assoc, mul_comm x, ← mul_assoc, mul_inv_cancel hb, one_mul, mul_sub, mul_one]
-#align gauss_sum_mul_aux gauss_sum_mul_aux
/-- We have `gauss_sum χ ψ * gauss_sum χ⁻¹ ψ⁻¹ = fintype.card R`
when `χ` is nontrivial and `ψ` is primitive (and `R` is a field). -/
mathlib commit https://github.com/leanprover-community/mathlib/commit/2651125b48fc5c170ab1111afd0817c903b1fc6c
@@ -107,7 +107,7 @@ private theorem gauss_sum_mul_aux {χ : MulChar R R'} (hχ : IsNontrivial χ) (
Finset.sum_const_zero, map_zero_one, mul_one]
exact hχ.sum_eq_zero.symm
· -- case `b ≠ 0`
- refine' (Fintype.sum_bijective _ (Equiv.mulLeft_bijective₀ b hb) _ _ fun x => _).symm
+ refine' (Fintype.sum_bijective _ (mulLeft_bijective₀ b hb) _ _ fun x => _).symm
rw [mul_assoc, mul_comm x, ← mul_assoc, mul_inv_cancel hb, one_mul, mul_sub, mul_one]
#align gauss_sum_mul_aux gauss_sum_mul_aux
mathlib commit https://github.com/leanprover-community/mathlib/commit/d11893b411025250c8e61ff2f12ccbd7ee35ab15
@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
Authors: Michael Stoll
! This file was ported from Lean 3 source module number_theory.legendre_symbol.gauss_sum
-! leanprover-community/mathlib commit 91288e351d51b3f0748f0a38faa7613fb0ae2ada
+! leanprover-community/mathlib commit d11893b411025250c8e61ff2f12ccbd7ee35ab15
! Please do not edit these lines, except to modify the commit id
! if you have ported upstream changes.
-/
@@ -221,7 +221,7 @@ theorem Char.card_pow_char_pow {χ : MulChar R R'} (hχ : IsQuadratic χ) (ψ :
/-- When `F` and `F'` are finite fields and `χ : F → F'` is a nontrivial quadratic character,
then `(χ(-1) * #F)^(#F'/2) = χ(#F')`. -/
-theorem Char.card_pow_card {F : Type} [Field F] [Fintype F] {F' : Type} [Field F'] [Fintype F']
+theorem Char.card_pow_card {F : Type _} [Field F] [Fintype F] {F' : Type _} [Field F'] [Fintype F']
{χ : MulChar F F'} (hχ₁ : IsNontrivial χ) (hχ₂ : IsQuadratic χ)
(hch₁ : ringChar F' ≠ ringChar F) (hch₂ : ringChar F' ≠ 2) :
(χ (-1) * Fintype.card F) ^ (Fintype.card F' / 2) = χ (Fintype.card F') :=
mathlib commit https://github.com/leanprover-community/mathlib/commit/ce7e9d53d4bbc38065db3b595cd5bd73c323bc1d
@@ -301,11 +301,11 @@ theorem FiniteField.two_pow_card {F : Type _} [Fintype F] [Field F] (hF : ringCh
have hg : gaussSum χ ψ₈.char ^ 2 = χ (-1) * Fintype.card (ZMod 8) :=
by
rw [hχ, one_mul, card, gaussSum]
- convert ← congr_arg (· ^ 2) (Fin.sum_univ_eight fun x => (χ₈ x : FF) * τ ^ x.val)
+ convert← congr_arg (· ^ 2) (Fin.sum_univ_eight fun x => (χ₈ x : FF) * τ ^ x.val)
· ext
congr
apply pow_one
- convert_to (0 + 1 * τ ^ 1 + 0 + -1 * τ ^ 3 + 0 + -1 * τ ^ 5 + 0 + 1 * τ ^ 7) ^ 2 = _
+ convert_to(0 + 1 * τ ^ 1 + 0 + -1 * τ ^ 3 + 0 + -1 * τ ^ 5 + 0 + 1 * τ ^ 7) ^ 2 = _
· simp only [χ₈_apply, Matrix.cons_val_zero, Matrix.cons_val_one, Matrix.head_cons,
Matrix.cons_vec_bit0_eq_alt0, Matrix.cons_vec_bit1_eq_alt1, Matrix.cons_vecAppend,
Matrix.cons_vecAlt0, Matrix.cons_vecAlt1, Int.cast_zero, Int.cast_one, Int.cast_neg,
@@ -319,7 +319,7 @@ theorem FiniteField.two_pow_card {F : Type _} [Fintype F] [Field F] (hF : ringCh
have h := Char.card_pow_char_pow hq ψ₈.char (ringChar FF) n hu hFF hg
rw [card, ← hchar, hχ, one_mul, ← hc, ← Nat.cast_pow (ringChar F), ← hc] at h
-- finally, we change `2` to `8` on the left hand side
- convert_to (8 : F) ^ (Fintype.card F / 2) = _
+ convert_to(8 : F) ^ (Fintype.card F / 2) = _
·
rw [(by norm_num : (8 : F) = 2 ^ 2 * 2), mul_pow,
(FiniteField.isSquare_iff hF <| hp2 2).mp ⟨2, pow_two 2⟩, one_mul]
mathlib commit https://github.com/leanprover-community/mathlib/commit/3180fab693e2cee3bff62675571264cb8778b212
@@ -103,8 +103,8 @@ private theorem gauss_sum_mul_aux {χ : MulChar R R'} (hχ : IsNontrivial χ) (
by
cases' eq_or_ne b 0 with hb hb
· -- case `b = 0`
- simp only [hb, inv_zero, mul_zero, MulChar.map_zero, zero_mul, Finset.sum_const_zero,
- map_zero_one, mul_one]
+ simp only [hb, inv_zero, MulZeroClass.mul_zero, MulChar.map_zero, MulZeroClass.zero_mul,
+ Finset.sum_const_zero, map_zero_one, mul_one]
exact hχ.sum_eq_zero.symm
· -- case `b ≠ 0`
refine' (Fintype.sum_bijective _ (Equiv.mulLeft_bijective₀ b hb) _ _ fun x => _).symm
@@ -122,7 +122,7 @@ theorem gaussSum_mul_gaussSum_eq_card {χ : MulChar R R'} (hχ : IsNontrivial χ
rw [Finset.sum_comm]
classical
-- to get `[decidable_eq R]` for `sum_mul_shift`
- simp_rw [← Finset.mul_sum, sum_mul_shift _ hψ, sub_eq_zero, mul_ite, mul_zero]
+ simp_rw [← Finset.mul_sum, sum_mul_shift _ hψ, sub_eq_zero, mul_ite, MulZeroClass.mul_zero]
rw [Finset.sum_ite_eq' Finset.univ (1 : R)]
simp only [Finset.mem_univ, map_one, one_mul, if_true]
#align gauss_sum_mul_gauss_sum_eq_card gaussSum_mul_gaussSum_eq_card
@@ -309,7 +309,7 @@ theorem FiniteField.two_pow_card {F : Type _} [Fintype F] [Field F] (hF : ringCh
· simp only [χ₈_apply, Matrix.cons_val_zero, Matrix.cons_val_one, Matrix.head_cons,
Matrix.cons_vec_bit0_eq_alt0, Matrix.cons_vec_bit1_eq_alt1, Matrix.cons_vecAppend,
Matrix.cons_vecAlt0, Matrix.cons_vecAlt1, Int.cast_zero, Int.cast_one, Int.cast_neg,
- zero_mul]
+ MulZeroClass.zero_mul]
rfl
convert_to 8 + (τ ^ 4 + 1) * (τ ^ 10 - 2 * τ ^ 8 - 2 * τ ^ 6 + 6 * τ ^ 4 + τ ^ 2 - 8) = _
· ring
mathlib commit https://github.com/leanprover-community/mathlib/commit/bd9851ca476957ea4549eb19b40e7b5ade9428cc
A mix of various changes; generated with a script and manually tweaked.
@@ -219,7 +219,7 @@ theorem Char.card_pow_card {F : Type*} [Field F] [Fintype F] {F' : Type*} [Field
obtain ⟨n', hp', hc'⟩ := FiniteField.card F' (ringChar F')
let ψ := primitiveCharFiniteField F F' hch₁
-- Porting note: this was a `let` but then Lean would time out at
- -- unification so it is changed to as `set` and `FF'` is replaced by its
+ -- unification so it is changed to a `set` and `FF'` is replaced by its
-- definition before unification
set FF' := CyclotomicField ψ.n F' with FF'_def
have hchar := Algebra.ringChar_eq F' FF'
We change the following field in the definition of an additive commutative monoid:
nsmul_succ : ∀ (n : ℕ) (x : G),
- AddMonoid.nsmul (n + 1) x = x + AddMonoid.nsmul n x
+ AddMonoid.nsmul (n + 1) x = AddMonoid.nsmul n x + x
where the latter is more natural
We adjust the definitions of ^
in monoids, groups, etc.
Originally there was a warning comment about why this natural order was preferred
use
x * npowRec n x
and notnpowRec n x * x
in the definition to make sure that definitional unfolding ofnpowRec
is blocked, to avoid deep recursion issues.
but it seems to no longer apply.
Remarks on the PR :
pow_succ
and pow_succ'
have switched their meanings.Ideal.IsPrime.mul_mem_pow
which is defined in [Mathlib/RingTheory/DedekindDomain/Ideal.lean]. Changing the order of operation forced me to add the symmetric lemma Ideal.IsPrime.mem_pow_mul
.@@ -176,8 +176,9 @@ theorem MulChar.IsQuadratic.gaussSum_frob_iter (n : ℕ) (hp : IsUnit (p : R)) {
gaussSum χ ψ ^ p ^ n = χ ((p : R) ^ n) * gaussSum χ ψ := by
induction' n with n ih
· rw [pow_zero, pow_one, pow_zero, MulChar.map_one, one_mul]
- · rw [pow_succ, mul_comm p, pow_mul, ih, mul_pow, hχ.gaussSum_frob _ hp, ← mul_assoc, pow_succ,
- mul_comm (p : R), map_mul, ← pow_apply' χ fp.1.ne_zero ((p : R) ^ n), hχ.pow_char p]
+ · rw [pow_succ, pow_mul, ih, mul_pow, hχ.gaussSum_frob _ hp, ← mul_assoc,
+ pow_succ,
+ map_mul, ← pow_apply' χ fp.1.ne_zero ((p : R) ^ n), hχ.pow_char p]
#align mul_char.is_quadratic.gauss_sum_frob_iter MulChar.IsQuadratic.gaussSum_frob_iter
end gaussSum_frob
@@ -204,7 +205,7 @@ theorem Char.card_pow_char_pow {χ : MulChar R R'} (hχ : IsQuadratic χ) (ψ :
exact not_isUnit_prime_of_dvd_card p
((CharP.cast_eq_zero_iff R' p _).mp <| hg.resolve_left (isUnit_one.neg.map χ).ne_zero) hp
rw [← hg]; apply mul_right_cancel₀ this
- rw [← hχ.gaussSum_frob_iter p n hp ψ, ← pow_mul, mul_comm, ← pow_succ,
+ rw [← hχ.gaussSum_frob_iter p n hp ψ, ← pow_mul, ← pow_succ,
Nat.two_mul_div_two_add_one_of_odd (fp.1.eq_two_or_odd'.resolve_left hp').pow]
#align char.card_pow_char_pow Char.card_pow_char_pow
This is a very large PR, but it has been reviewed piecemeal already in PRs to the bump/v4.7.0
branch as we update to intermediate nightlies.
Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Kyle Miller <kmill31415@gmail.com> Co-authored-by: damiano <adomani@gmail.com>
@@ -235,7 +235,7 @@ theorem Char.card_pow_card {F : Type*} [Field F] [Fintype F] {F' : Type*} [Field
have := Char.card_pow_char_pow (hχ₂.comp (algebraMap F' FF')) ψ.char
(ringChar FF') n' hch₁ (hchar ▸ hch₂)
(gaussSum_sq (hχ₁.comp <| RingHom.injective _) (hχ₂.comp _) ψ.prim)
- simp_rw [FF'_def] at this
+ simp_rw [ψ, FF'_def] at this
exact this
#align char.card_pow_card Char.card_pow_card
@@ -333,7 +333,7 @@ theorem FiniteField.two_pow_card {F : Type*} [Fintype F] [Field F] (hF : ringCha
-- Matrix.cons_vecAlt1, Int.cast_neg]
simp_rw [χ₈_apply]
rw [← h₄]
- dsimp only
+ dsimp only [τ]
congr
· rw [Matrix.cons_val_zero]; simp
· simp only [Matrix.vecCons, ne_eq, Nat.cast_ofNat, id_eq, eq_mpr_eq_cast, mul_eq_zero,
slow / slower
porting notes (#11084)
Classifies by adding issue number #11083 to porting notes claiming anything semantically equivalent to:
attribute
because it caused extremely slow tactic
"@@ -291,7 +291,7 @@ theorem FiniteField.two_pow_card {F : Type*} [Fintype F] [Field F] (hF : ringCha
-- Porting note: The type is actually `PrimitiveAddChar (ZMod (8 : ℕ+)) F`, but this seems faster.
let ψ₈ : PrimitiveAddChar (ZMod 8) F :=
primitiveZModChar 8 F (by convert hp2 3 using 1; norm_cast)
- -- Porting note: unifying this is very slow, so only do it once.
+ -- Porting note (#11083): unifying this is very slow, so only do it once.
let ψ₈char : AddChar (ZMod 8) FF := ψ₈.char
let τ : FF := ψ₈char 1
have τ_spec : τ ^ 4 = -1 := by
f ^ n
(#9617)
This involves moving lemmas from Algebra.GroupPower.Ring
to Algebra.GroupWithZero.Basic
and changing some 0 < n
assumptions to n ≠ 0
.
From LeanAPAP
@@ -153,7 +153,7 @@ of `χ` and `ψ` is the Gauss sum of `χ^p` and `ψ^p`. -/
theorem gaussSum_frob (χ : MulChar R R') (ψ : AddChar R R') :
gaussSum χ ψ ^ p = gaussSum (χ ^ p) (ψ ^ p) := by
rw [← frobenius_def, gaussSum, gaussSum, map_sum]
- simp_rw [pow_apply' χ fp.1.pos, map_mul, frobenius_def]
+ simp_rw [pow_apply' χ fp.1.ne_zero, map_mul, frobenius_def]
rfl
#align gauss_sum_frob gaussSum_frob
@@ -164,7 +164,7 @@ is a unit in the source ring, the `p`th power of the Gauss sum of`χ` and `ψ` i
nonrec theorem MulChar.IsQuadratic.gaussSum_frob (hp : IsUnit (p : R)) {χ : MulChar R R'}
(hχ : IsQuadratic χ) (ψ : AddChar R R') : gaussSum χ ψ ^ p = χ p * gaussSum χ ψ := by
rw [gaussSum_frob, pow_mulShift, hχ.pow_char p, ← gaussSum_mulShift χ ψ hp.unit, ← mul_assoc,
- hp.unit_spec, ← pow_two, ← pow_apply' _ (by norm_num : 0 < 2), hχ.sq_eq_one, ← hp.unit_spec,
+ hp.unit_spec, ← pow_two, ← pow_apply' _ two_ne_zero, hχ.sq_eq_one, ← hp.unit_spec,
one_apply_coe, one_mul]
#align mul_char.is_quadratic.gauss_sum_frob MulChar.IsQuadratic.gaussSum_frob
@@ -177,7 +177,7 @@ theorem MulChar.IsQuadratic.gaussSum_frob_iter (n : ℕ) (hp : IsUnit (p : R)) {
induction' n with n ih
· rw [pow_zero, pow_one, pow_zero, MulChar.map_one, one_mul]
· rw [pow_succ, mul_comm p, pow_mul, ih, mul_pow, hχ.gaussSum_frob _ hp, ← mul_assoc, pow_succ,
- mul_comm (p : R), map_mul, ← pow_apply' χ fp.1.pos ((p : R) ^ n), hχ.pow_char p]
+ mul_comm (p : R), map_mul, ← pow_apply' χ fp.1.ne_zero ((p : R) ^ n), hχ.pow_char p]
#align mul_char.is_quadratic.gauss_sum_frob_iter MulChar.IsQuadratic.gaussSum_frob_iter
end gaussSum_frob
@@ -200,7 +200,7 @@ theorem Char.card_pow_char_pow {χ : MulChar R R'} (hχ : IsQuadratic χ) (ψ :
(hg : gaussSum χ ψ ^ 2 = χ (-1) * Fintype.card R) :
(χ (-1) * Fintype.card R) ^ (p ^ n / 2) = χ ((p : R) ^ n) := by
have : gaussSum χ ψ ≠ 0 := by
- intro hf; rw [hf, zero_pow (by norm_num : 0 < 2), eq_comm, mul_eq_zero] at hg
+ intro hf; rw [hf, zero_pow two_ne_zero, eq_comm, mul_eq_zero] at hg
exact not_isUnit_prime_of_dvd_card p
((CharP.cast_eq_zero_iff R' p _).mp <| hg.resolve_left (isUnit_one.neg.map χ).ne_zero) hp
rw [← hg]; apply mul_right_cancel₀ this
@@ -312,7 +312,6 @@ theorem FiniteField.two_pow_card {F : Type*} [Fintype F] [Field F] (hF : ringCha
-- we now show that the Gauss sum of `χ` and `ψ₈` has the relevant property
have hg : gaussSum χ ψ₈char ^ 2 = χ (-1) * Fintype.card (ZMod 8) := by
- have _ := congr_arg (· ^ 2) (Fin.sum_univ_eight fun x => (χ₈ x : FF) * τ ^ x.1)
have h₁ : (fun i : Fin 8 => ↑(χ₈ i) * τ ^ i.val) = (fun a : ZMod 8 => χ a * ↑(ψ₈char a)) := by
-- Porting note: original proof
-- ext; congr; apply pow_one
cases'
(#9171)
I literally went through and regex'd some uses of cases'
, replacing them with rcases
; this is meant to be a low effort PR as I hope that tools can do this in the future.
rcases
is an easier replacement than cases
, though with better tools we could in future do a second pass converting simple rcases
added here (and existing ones) to cases
.
@@ -96,7 +96,7 @@ variable {R : Type u} [Field R] [Fintype R] {R' : Type v} [CommRing R'] [IsDomai
-- Is this useful enough in other contexts to be public?
private theorem gaussSum_mul_aux {χ : MulChar R R'} (hχ : IsNontrivial χ) (ψ : AddChar R R')
(b : R) : ∑ a, χ (a * b⁻¹) * ψ (a - b) = ∑ c, χ c * ψ (b * (c - 1)) := by
- cases' eq_or_ne b 0 with hb hb
+ rcases eq_or_ne b 0 with hb | hb
· -- case `b = 0`
simp only [hb, inv_zero, mul_zero, MulChar.map_zero, zero_mul,
Finset.sum_const_zero, map_zero_one, mul_one]
AddChar
(#8803)
There are two things going on here:
AddChar G R
has two syntactically different coercions to function G → R
:
FunLike.coe
via AddChar.monoidHomClass
AddChar.toFun
via AddChar.hasCoeToFun
AddChar.hasCoeToFun
and AddChar.monoidHomClass
together create a diamond for the typeclass problem FunLike (AddChar G R) _ _
This PR fixes both problems by
HasCoeToFun
instance and the corresponding AddChar.toFun
MonoidHomClass (AddChar G R) (Multiplicative G) R
to FunLike (AddChar G R) G fun _ ↦ R
(isn't the whole point of AddChar
to go from an additive group to a multiplicative one anyway?)This PR isn't meant to be perfect. It is a stopgag to an issue that has completely startled progress on LeanAPAP. Once it is fixed, a much more thorough refactor will follow.
This breaks a rewrite downstream that now unifies to some defeq but not syntactically equal type. This is more an indication of fragility in the original proof.
@@ -296,9 +296,13 @@ theorem FiniteField.two_pow_card {F : Type*} [Fintype F] [Field F] (hF : ringCha
let τ : FF := ψ₈char 1
have τ_spec : τ ^ 4 = -1 := by
refine (sq_eq_one_iff.1 ?_).resolve_left ?_
- · rw [← pow_mul, ← map_nsmul_pow ψ₈char, AddChar.IsPrimitive.zmod_char_eq_one_iff 8 ψ₈.prim]
+ · rw [← pow_mul, ← map_nsmul_pow ψ₈char]
+ -- doesn't match syntactically for `rw`
+ refine (AddChar.IsPrimitive.zmod_char_eq_one_iff 8 ψ₈.prim _).2 ?_
decide
- · rw [← map_nsmul_pow ψ₈char, AddChar.IsPrimitive.zmod_char_eq_one_iff 8 ψ₈.prim]
+ · rw [← map_nsmul_pow ψ₈char]
+ -- doesn't match syntactically for `rw`
+ refine (AddChar.IsPrimitive.zmod_char_eq_one_iff 8 ψ₈.prim _).not.2 ?_
decide
-- we consider `χ₈` as a multiplicative character `ℤ/8ℤ → FF`
Due to recent changes in core we can reduce or remove many set_option maxHeartbeats
statements.
I have tried to be careful to not leave anything too close to the line, so don't be surprised if some of these can still be reduced further.
This reduces us from 96 maxHeartbeats
statements to 44
. (There are 10 false positives in meta or testing code.)
Co-authored-by: Scott Morrison <scott.morrison@gmail.com>
@@ -259,9 +259,6 @@ in this way, the result is reduced to `card_pow_char_pow`.
open ZMod
--- Porting note: This proof is _really_ slow, maybe it should be broken into several lemmas
--- See https://github.com/leanprover-community/mathlib4/issues/5028
-set_option maxHeartbeats 500000 in
/-- For every finite field `F` of odd characteristic, we have `2^(#F/2) = χ₈#F` in `F`. -/
theorem FiniteField.two_pow_card {F : Type*} [Fintype F] [Field F] (hF : ringChar F ≠ 2) :
(2 : F) ^ (Fintype.card F / 2) = χ₈ (Fintype.card F) := by
@@ -261,7 +261,7 @@ open ZMod
-- Porting note: This proof is _really_ slow, maybe it should be broken into several lemmas
-- See https://github.com/leanprover-community/mathlib4/issues/5028
-set_option maxHeartbeats 800000 in
+set_option maxHeartbeats 500000 in
/-- For every finite field `F` of odd characteristic, we have `2^(#F/2) = χ₈#F` in `F`. -/
theorem FiniteField.two_pow_card {F : Type*} [Fintype F] [Field F] (hF : ringChar F ≠ 2) :
(2 : F) ^ (Fintype.card F / 2) = χ₈ (Fintype.card F) := by
MulZeroClass.
in mul_zero
/zero_mul
(#6682)
Search&replace MulZeroClass.mul_zero
-> mul_zero
, MulZeroClass.zero_mul
-> zero_mul
.
These were introduced by Mathport, as the full name of mul_zero
is actually MulZeroClass.mul_zero
(it's exported with the short name).
@@ -98,7 +98,7 @@ private theorem gaussSum_mul_aux {χ : MulChar R R'} (hχ : IsNontrivial χ) (ψ
(b : R) : ∑ a, χ (a * b⁻¹) * ψ (a - b) = ∑ c, χ c * ψ (b * (c - 1)) := by
cases' eq_or_ne b 0 with hb hb
· -- case `b = 0`
- simp only [hb, inv_zero, MulZeroClass.mul_zero, MulChar.map_zero, MulZeroClass.zero_mul,
+ simp only [hb, inv_zero, mul_zero, MulChar.map_zero, zero_mul,
Finset.sum_const_zero, map_zero_one, mul_one]
exact (hχ.sum_eq_zero).symm
· -- case `b ≠ 0`
@@ -327,7 +327,7 @@ theorem FiniteField.two_pow_card {F : Type*} [Fintype F] [Field F] (hF : ringCha
(↑(χ₈ 0) * τ ^ 0 + ↑(χ₈ 1) * τ ^ 1 + ↑(χ₈ 2) * τ ^ 2 + ↑(χ₈ 3) * τ ^ 3 + ↑(χ₈ 4) * τ ^ 4 +
↑(χ₈ 5) * τ ^ 5 + ↑(χ₈ 6) * τ ^ 6 + ↑(χ₈ 7) * τ ^ 7) ^ 2 = 8 := by
-- Porting note: original proof
- -- simp [← h₄, χ₈_apply, Matrix.cons_val_zero, algebraMap.coe_zero, MulZeroClass.zero_mul,
+ -- simp [← h₄, χ₈_apply, Matrix.cons_val_zero, algebraMap.coe_zero, zero_mul,
-- Matrix.cons_val_one, Matrix.head_cons, algebraMap.coe_one, Matrix.cons_vec_bit0_eq_alt0,
-- Matrix.cons_vecAppend, Matrix.cons_vecAlt0, Matrix.cons_vec_bit1_eq_alt1,
-- Matrix.cons_vecAlt1, Int.cast_neg]
Type _
and Sort _
(#6499)
We remove all possible occurences of Type _
and Sort _
in favor of Type*
and Sort*
.
This has nice performance benefits.
@@ -210,7 +210,7 @@ theorem Char.card_pow_char_pow {χ : MulChar R R'} (hχ : IsQuadratic χ) (ψ :
/-- When `F` and `F'` are finite fields and `χ : F → F'` is a nontrivial quadratic character,
then `(χ(-1) * #F)^(#F'/2) = χ(#F')`. -/
-theorem Char.card_pow_card {F : Type _} [Field F] [Fintype F] {F' : Type _} [Field F'] [Fintype F']
+theorem Char.card_pow_card {F : Type*} [Field F] [Fintype F] {F' : Type*} [Field F'] [Fintype F']
{χ : MulChar F F'} (hχ₁ : IsNontrivial χ) (hχ₂ : IsQuadratic χ)
(hch₁ : ringChar F' ≠ ringChar F) (hch₂ : ringChar F' ≠ 2) :
(χ (-1) * Fintype.card F) ^ (Fintype.card F' / 2) = χ (Fintype.card F') := by
@@ -263,7 +263,7 @@ open ZMod
-- See https://github.com/leanprover-community/mathlib4/issues/5028
set_option maxHeartbeats 800000 in
/-- For every finite field `F` of odd characteristic, we have `2^(#F/2) = χ₈#F` in `F`. -/
-theorem FiniteField.two_pow_card {F : Type _} [Fintype F] [Field F] (hF : ringChar F ≠ 2) :
+theorem FiniteField.two_pow_card {F : Type*} [Fintype F] [Field F] (hF : ringChar F ≠ 2) :
(2 : F) ^ (Fintype.card F / 2) = χ₈ (Fintype.card F) := by
have hp2 : ∀ n : ℕ, (2 ^ n : F) ≠ 0 := fun n => pow_ne_zero n (Ring.two_ne_zero hF)
obtain ⟨n, hp, hc⟩ := FiniteField.card F (ringChar F)
@@ -2,16 +2,13 @@
Copyright (c) 2022 Michael Stoll. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Michael Stoll
-
-! This file was ported from Lean 3 source module number_theory.legendre_symbol.gauss_sum
-! leanprover-community/mathlib commit e3f4be1fcb5376c4948d7f095bec45350bfb9d1a
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
-/
import Mathlib.NumberTheory.LegendreSymbol.AddCharacter
import Mathlib.NumberTheory.LegendreSymbol.ZModChar
import Mathlib.Algebra.CharP.CharAndCard
+#align_import number_theory.legendre_symbol.gauss_sum from "leanprover-community/mathlib"@"e3f4be1fcb5376c4948d7f095bec45350bfb9d1a"
+
/-!
# Gauss sums
@@ -263,7 +263,7 @@ in this way, the result is reduced to `card_pow_char_pow`.
open ZMod
-- Porting note: This proof is _really_ slow, maybe it should be broken into several lemmas
--- See https://github.com/leanprover-community/mathlib4/issues/5028
+-- See https://github.com/leanprover-community/mathlib4/issues/5028
set_option maxHeartbeats 800000 in
/-- For every finite field `F` of odd characteristic, we have `2^(#F/2) = χ₈#F` in `F`. -/
theorem FiniteField.two_pow_card {F : Type _} [Fintype F] [Field F] (hF : ringChar F ≠ 2) :
This is still awful, but slightly less so.
@@ -264,7 +264,7 @@ open ZMod
-- Porting note: This proof is _really_ slow, maybe it should be broken into several lemmas
-- See https://github.com/leanprover-community/mathlib4/issues/5028
-set_option maxHeartbeats 1800000 in
+set_option maxHeartbeats 800000 in
/-- For every finite field `F` of odd characteristic, we have `2^(#F/2) = χ₈#F` in `F`. -/
theorem FiniteField.two_pow_card {F : Type _} [Fintype F] [Field F] (hF : ringChar F ≠ 2) :
(2 : F) ^ (Fintype.card F / 2) = χ₈ (Fintype.card F) := by
@@ -272,7 +272,12 @@ theorem FiniteField.two_pow_card {F : Type _} [Fintype F] [Field F] (hF : ringCh
obtain ⟨n, hp, hc⟩ := FiniteField.card F (ringChar F)
-- we work in `FF`, the eighth cyclotomic field extension of `F`
- let FF := (Polynomial.cyclotomic 8 F).SplittingField
+ -- Porting note: was
+ -- let FF := (Polynomial.cyclotomic 8 F).SplittingField
+ -- but we want to unify with `CyclotomicField` below.
+ let FF := CyclotomicField 8 F
+ haveI : Polynomial.IsSplittingField F FF (Polynomial.cyclotomic 8 F) :=
+ Polynomial.IsSplittingField.splittingField _
haveI : FiniteDimensional F FF :=
Polynomial.IsSplittingField.finiteDimensional FF (Polynomial.cyclotomic 8 F)
haveI : Fintype FF := FiniteDimensional.fintypeOfFintype F FF
@@ -289,13 +294,17 @@ theorem FiniteField.two_pow_card {F : Type _} [Fintype F] [Field F] (hF : ringCh
-- there is a primitive additive character `ℤ/8ℤ → FF`, sending `a + 8ℤ ↦ τ^a`
-- with a primitive eighth root of unity `τ`
- let ψ₈ := primitiveZModChar 8 F (by convert hp2 3 using 1; norm_cast)
- let τ : FF := ψ₈.char 1
+ -- Porting note: The type is actually `PrimitiveAddChar (ZMod (8 : ℕ+)) F`, but this seems faster.
+ let ψ₈ : PrimitiveAddChar (ZMod 8) F :=
+ primitiveZModChar 8 F (by convert hp2 3 using 1; norm_cast)
+ -- Porting note: unifying this is very slow, so only do it once.
+ let ψ₈char : AddChar (ZMod 8) FF := ψ₈.char
+ let τ : FF := ψ₈char 1
have τ_spec : τ ^ 4 = -1 := by
refine (sq_eq_one_iff.1 ?_).resolve_left ?_
- · rw [← pow_mul, ← map_nsmul_pow ψ₈.char, AddChar.IsPrimitive.zmod_char_eq_one_iff 8 ψ₈.prim]
+ · rw [← pow_mul, ← map_nsmul_pow ψ₈char, AddChar.IsPrimitive.zmod_char_eq_one_iff 8 ψ₈.prim]
decide
- · rw [← map_nsmul_pow ψ₈.char, AddChar.IsPrimitive.zmod_char_eq_one_iff 8 ψ₈.prim]
+ · rw [← map_nsmul_pow ψ₈char, AddChar.IsPrimitive.zmod_char_eq_one_iff 8 ψ₈.prim]
decide
-- we consider `χ₈` as a multiplicative character `ℤ/8ℤ → FF`
@@ -304,12 +313,12 @@ theorem FiniteField.two_pow_card {F : Type _} [Fintype F] [Field F] (hF : ringCh
have hq : IsQuadratic χ := isQuadratic_χ₈.comp _
-- we now show that the Gauss sum of `χ` and `ψ₈` has the relevant property
- have hg : gaussSum χ ψ₈.char ^ 2 = χ (-1) * Fintype.card (ZMod 8) := by
+ have hg : gaussSum χ ψ₈char ^ 2 = χ (-1) * Fintype.card (ZMod 8) := by
have _ := congr_arg (· ^ 2) (Fin.sum_univ_eight fun x => (χ₈ x : FF) * τ ^ x.1)
- have h₁ : (fun i : Fin 8 => ↑(χ₈ i) * τ ^ i.val) = (fun a : ZMod 8 => χ a * ↑(ψ₈.char a)) := by
+ have h₁ : (fun i : Fin 8 => ↑(χ₈ i) * τ ^ i.val) = (fun a : ZMod 8 => χ a * ↑(ψ₈char a)) := by
-- Porting note: original proof
-- ext; congr; apply pow_one
- ext (x : Fin 8); rw [← map_nsmul_pow ψ₈.char]; congr 2;
+ ext (x : Fin 8); rw [← map_nsmul_pow ψ₈char]; congr 2;
rw [Nat.smul_one_eq_coe, Fin.cast_val_eq_self x]
have h₂ : (0 + 1 * τ ^ 1 + 0 + -1 * τ ^ 3 + 0 + -1 * τ ^ 5 + 0 + 1 * τ ^ 7) ^ 2 =
8 + (τ ^ 4 + 1) * (τ ^ 10 - 2 * τ ^ 8 - 2 * τ ^ 6 + 6 * τ ^ 4 + τ ^ 2 - 8) := by ring
@@ -359,7 +368,7 @@ theorem FiniteField.two_pow_card {F : Type _} [Fintype F] [Field F] (hF : ringCh
rfl
-- this allows us to apply `card_pow_char_pow` to our situation
- have h := Char.card_pow_char_pow hq ψ₈.char (ringChar FF) n hu hFF hg
+ have h := Char.card_pow_char_pow (R := ZMod 8) hq ψ₈char (ringChar FF) n hu hFF hg
rw [ZMod.card, ← hchar, hχ, one_mul, ← hc, ← Nat.cast_pow (ringChar F), ← hc] at h
-- finally, we change `2` to `8` on the left hand side
@@ -175,11 +175,12 @@ nonrec theorem MulChar.IsQuadratic.gaussSum_frob (hp : IsUnit (p : R)) {χ : Mul
is a unit in the source ring and `n` is a natural number, the `p^n`th power of the Gauss
sum of`χ` and `ψ` is `χ (p^n)` times the original Gauss sum. -/
theorem MulChar.IsQuadratic.gaussSum_frob_iter (n : ℕ) (hp : IsUnit (p : R)) {χ : MulChar R R'}
- (hχ : IsQuadratic χ) (ψ : AddChar R R') : gaussSum χ ψ ^ p ^ n = χ (p ^ n) * gaussSum χ ψ := by
+ (hχ : IsQuadratic χ) (ψ : AddChar R R') :
+ gaussSum χ ψ ^ p ^ n = χ ((p : R) ^ n) * gaussSum χ ψ := by
induction' n with n ih
- · rw [pow_zero, pow_one, Nat.cast_one, MulChar.map_one, one_mul]
- · rw [pow_succ, mul_comm p, pow_mul, ih, mul_pow, hχ.gaussSum_frob _ hp, ← mul_assoc,
- ← pow_apply' χ fp.1.pos (p ^ n), hχ.pow_char p, ← map_mul, Nat.cast_mul]
+ · rw [pow_zero, pow_one, pow_zero, MulChar.map_one, one_mul]
+ · rw [pow_succ, mul_comm p, pow_mul, ih, mul_pow, hχ.gaussSum_frob _ hp, ← mul_assoc, pow_succ,
+ mul_comm (p : R), map_mul, ← pow_apply' χ fp.1.pos ((p : R) ^ n), hχ.pow_char p]
#align mul_char.is_quadratic.gauss_sum_frob_iter MulChar.IsQuadratic.gaussSum_frob_iter
end gaussSum_frob
@@ -200,7 +201,7 @@ This version can be used when `R` is not a field, e.g., `ℤ/8ℤ`. -/
theorem Char.card_pow_char_pow {χ : MulChar R R'} (hχ : IsQuadratic χ) (ψ : AddChar R R') (p n : ℕ)
[fp : Fact p.Prime] [hch : CharP R' p] (hp : IsUnit (p : R)) (hp' : p ≠ 2)
(hg : gaussSum χ ψ ^ 2 = χ (-1) * Fintype.card R) :
- (χ (-1) * Fintype.card R) ^ (p ^ n / 2) = χ (p ^ n) := by
+ (χ (-1) * Fintype.card R) ^ (p ^ n / 2) = χ ((p : R) ^ n) := by
have : gaussSum χ ψ ≠ 0 := by
intro hf; rw [hf, zero_pow (by norm_num : 0 < 2), eq_comm, mul_eq_zero] at hg
exact not_isUnit_prime_of_dvd_card p
@@ -232,12 +233,12 @@ theorem Char.card_pow_card {F : Type _} [Field F] [Fintype F] {F' : Type _} [Fie
rw [Ne, ← Nat.prime_dvd_prime_iff_eq hp' hp, ← isUnit_iff_not_dvd_char, hchar] at hch₁
-- Porting note: original proof is below and, as noted above, `FF'` needs to
-- be replaced by its definition before unification to avoid time out
- -- exact Char.card_pow_char_pow (hχ₂.comp _) ψ.char (ringChar FF') n' hch₁ (hchar ▸ hch₂)
+ -- exact Char.card_pow_char_pow (hχ₂.comp _) ψ.char (ringChar FF') n' hch₁ (hchar ▸ hch₂)
-- (gaussSum_sq (hχ₁.comp <| RingHom.injective _) (hχ₂.comp _) ψ.prim)
have := Char.card_pow_char_pow (hχ₂.comp (algebraMap F' FF')) ψ.char
(ringChar FF') n' hch₁ (hchar ▸ hch₂)
(gaussSum_sq (hχ₁.comp <| RingHom.injective _) (hχ₂.comp _) ψ.prim)
- simp_rw [FF'_def, Nat.cast_pow] at this
+ simp_rw [FF'_def] at this
exact this
#align char.card_pow_card Char.card_pow_card
@@ -359,7 +360,7 @@ theorem FiniteField.two_pow_card {F : Type _} [Fintype F] [Field F] (hF : ringCh
-- this allows us to apply `card_pow_char_pow` to our situation
have h := Char.card_pow_char_pow hq ψ₈.char (ringChar FF) n hu hFF hg
- rw [ZMod.card, ← hchar, hχ, one_mul, ← hc] at h
+ rw [ZMod.card, ← hchar, hχ, one_mul, ← hc, ← Nat.cast_pow (ringChar F), ← hc] at h
-- finally, we change `2` to `8` on the left hand side
convert_to (8 : F) ^ (Fintype.card F / 2) = _
@@ -367,6 +368,7 @@ theorem FiniteField.two_pow_card {F : Type _} [Fintype F] [Field F] (hF : ringCh
(FiniteField.isSquare_iff hF <| hp2 2).mp ⟨2, pow_two 2⟩, one_mul]
apply (algebraMap F FF).injective
simp only [map_pow, map_ofNat, map_intCast]
+ simp only [Nat.cast_ofNat, ringHomComp_apply, eq_intCast] at h
exact h
#align finite_field.two_pow_card FiniteField.two_pow_card
@@ -38,9 +38,9 @@ Some important results are as follows.
the Gauss sum to the `p`th power (where `p` is the characteristic of
the target ring `R'`) multiplies it by `χ p`.
* `Char.card_pow_card`: When `F` and `F'` are finite fields and `χ : F → F'`
- is a nontrivial quadratic character, then `(χ (-1) * #F)^(#F'/2) = χ (#F')`.
+ is a nontrivial quadratic character, then `(χ (-1) * #F)^(#F'/2) = χ #F'`.
* `FiniteField.two_pow_card`: For every finite field `F` of odd characteristic,
- we have `2^(#F/2) = χ₈(#F)` in `F`.
+ we have `2^(#F/2) = χ₈#F` in `F`.
This machinery can be used to derive (a generalization of) the Law of
Quadratic Reciprocity.
@@ -250,9 +250,9 @@ section GaussSumTwo
This section proves the following result.
-For every finite field `F` of odd characteristic, we have `2^(#F/2) = χ₈(#F)` in `F`.
+For every finite field `F` of odd characteristic, we have `2^(#F/2) = χ₈#F` in `F`.
This can be used to show that the quadratic character of `F` takes the value
-`χ₈(#F)` at `2`.
+`χ₈#F` at `2`.
The proof uses the Gauss sum of `χ₈` and a primitive additive character on `ℤ/8ℤ`;
in this way, the result is reduced to `card_pow_char_pow`.
@@ -264,7 +264,7 @@ open ZMod
-- Porting note: This proof is _really_ slow, maybe it should be broken into several lemmas
-- See https://github.com/leanprover-community/mathlib4/issues/5028
set_option maxHeartbeats 1800000 in
-/-- For every finite field `F` of odd characteristic, we have `2^(#F/2) = χ₈(#F)` in `F`. -/
+/-- For every finite field `F` of odd characteristic, we have `2^(#F/2) = χ₈#F` in `F`. -/
theorem FiniteField.two_pow_card {F : Type _} [Fintype F] [Field F] (hF : ringChar F ≠ 2) :
(2 : F) ^ (Fintype.card F / 2) = χ₈ (Fintype.card F) := by
have hp2 : ∀ n : ℕ, (2 ^ n : F) ≠ 0 := fun n => pow_ne_zero n (Ring.two_ne_zero hF)
Forgot to write a porting note
@@ -163,7 +163,7 @@ theorem gaussSum_frob (χ : MulChar R R') (ψ : AddChar R R') :
/-- For a quadratic character `χ` and when the characteristic `p` of the target ring
is a unit in the source ring, the `p`th power of the Gauss sum of`χ` and `ψ` is
`χ p` times the original Gauss sum. -/
--- Porting note: TODO
+-- Porting note: Added `nonrec` to avoid error `failed to prove termination`
nonrec theorem MulChar.IsQuadratic.gaussSum_frob (hp : IsUnit (p : R)) {χ : MulChar R R'}
(hχ : IsQuadratic χ) (ψ : AddChar R R') : gaussSum χ ψ ^ p = χ p * gaussSum χ ψ := by
rw [gaussSum_frob, pow_mulShift, hχ.pow_char p, ← gaussSum_mulShift χ ψ hp.unit, ← mul_assoc,
The unported dependencies are
algebra.order.module
init.core
linear_algebra.free_module.finite.rank
algebra.order.monoid.cancel.defs
algebra.abs
algebra.group_power.lemmas
init.data.list.basic
linear_algebra.free_module.rank
algebra.order.monoid.cancel.basic
init.data.list.default
topology.subset_properties
init.logic
The following 1 dependencies have changed in mathlib3 since they were ported, which may complicate porting this file