number_theory.legendre_symbol.add_character
⟷
Mathlib.NumberTheory.LegendreSymbol.AddCharacter
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)
(last sync)
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -365,7 +365,7 @@ theorem zmodChar_apply {n : ℕ+} {ζ : C} (hζ : ζ ^ ↑n = 1) (a : ZMod n) :
#print AddChar.zmodChar_apply' /-
theorem zmodChar_apply' {n : ℕ+} {ζ : C} (hζ : ζ ^ ↑n = 1) (a : ℕ) : zmodChar n hζ a = ζ ^ a := by
- rw [pow_eq_pow_mod a hζ, zmod_char_apply, ZMod.val_nat_cast a]
+ rw [pow_eq_pow_mod a hζ, zmod_char_apply, ZMod.val_natCast a]
#align add_char.zmod_char_apply' AddChar.zmodChar_apply'
-/
@@ -378,7 +378,7 @@ theorem zmod_char_isNontrivial_iff (n : ℕ+) (ψ : AddChar (ZMod n) C) : IsNont
refine' ⟨_, fun h => ⟨1, h⟩⟩
contrapose!
rintro h₁ ⟨a, ha⟩
- have ha₁ : a = a.val • 1 := by rw [nsmul_eq_mul, mul_one]; exact (ZMod.nat_cast_zmod_val a).symm
+ have ha₁ : a = a.val • 1 := by rw [nsmul_eq_mul, mul_one]; exact (ZMod.natCast_zmod_val a).symm
rw [ha₁, map_nsmul_pow, h₁, one_pow] at ha
exact ha rfl
#align add_char.zmod_char_is_nontrivial_iff AddChar.zmod_char_isNontrivial_iff
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -97,10 +97,10 @@ instance hasCoeToFun : CoeFun (AddChar R R') fun x => R → R'
where coe ψ x := ψ.toMonoidHom (ofAdd x)
#align add_char.has_coe_to_fun AddChar.hasCoeToFun
-#print AddChar.coe_to_fun_apply /-
-theorem coe_to_fun_apply (ψ : AddChar R R') (a : R) : ψ a = ψ.toMonoidHom (ofAdd a) :=
+#print AddChar.toMonoidHom_apply /-
+theorem toMonoidHom_apply (ψ : AddChar R R') (a : R) : ψ a = ψ.toMonoidHom (ofAdd a) :=
rfl
-#align add_char.coe_to_fun_apply AddChar.coe_to_fun_apply
+#align add_char.coe_to_fun_apply AddChar.toMonoidHom_apply
-/
instance monoidHomClass : MonoidHomClass (AddChar R R') (Multiplicative R) R' :=
@@ -138,14 +138,16 @@ open Multiplicative
variable {R : Type u} [AddCommGroup R] {R' : Type v} [CommMonoid R']
-#print AddChar.hasInv /-
+/- warning: add_char.has_inv clashes with add_char.comm_group -> AddChar.instCommGroup
+Case conversion may be inaccurate. Consider using '#align add_char.has_inv AddChar.instCommGroupₓ'. -/
+#print AddChar.instCommGroup /-
/-- An additive character on a commutative additive group has an inverse.
Note that this is a different inverse to the one provided by `monoid_hom.has_inv`,
as it acts on the domain instead of the codomain. -/
-instance hasInv : Inv (AddChar R R') :=
+instance instCommGroup : Inv (AddChar R R') :=
⟨fun ψ => ψ.comp invMonoidHom⟩
-#align add_char.has_inv AddChar.hasInv
+#align add_char.has_inv AddChar.instCommGroup
-/
#print AddChar.inv_apply /-
@@ -162,15 +164,15 @@ theorem map_zsmul_zpow {R' : Type v} [CommGroup R'] (ψ : AddChar R R') (n : ℤ
#align add_char.map_zsmul_zpow AddChar.map_zsmul_zpow
-/
-#print AddChar.commGroup /-
+#print AddChar.instCommGroup /-
/-- The additive characters on a commutative additive group form a commutative group. -/
-instance commGroup : CommGroup (AddChar R R') :=
+instance instCommGroup : CommGroup (AddChar R R') :=
{ MonoidHom.commMonoid with
inv := Inv.inv
hMul_left_inv := fun ψ => by ext;
rw [MonoidHom.mul_apply, MonoidHom.one_apply, inv_apply, ← map_add_mul, add_left_neg,
map_zero_one] }
-#align add_char.comm_group AddChar.commGroup
+#align add_char.comm_group AddChar.instCommGroup
-/
end GroupStructure
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -271,10 +271,10 @@ is injective when `ψ` is primitive. -/
theorem to_mulShift_inj_of_isPrimitive {ψ : AddChar R R'} (hψ : IsPrimitive ψ) :
Function.Injective ψ.mulShift := by
intro a b h
- apply_fun fun x => x * mul_shift ψ (-b) at h
- simp only [mul_shift_mul, mul_shift_zero, add_right_neg] at h
+ apply_fun fun x => x * mul_shift ψ (-b) at h
+ simp only [mul_shift_mul, mul_shift_zero, add_right_neg] at h
have h₂ := hψ (a + -b)
- rw [h, is_nontrivial_iff_ne_trivial, ← sub_eq_add_neg, sub_ne_zero] at h₂
+ rw [h, is_nontrivial_iff_ne_trivial, ← sub_eq_add_neg, sub_ne_zero] at h₂
exact not_not.mp fun h => h₂ h rfl
#align add_char.to_mul_shift_inj_of_is_primitive AddChar.to_mulShift_inj_of_isPrimitive
-/
@@ -377,7 +377,7 @@ theorem zmod_char_isNontrivial_iff (n : ℕ+) (ψ : AddChar (ZMod n) C) : IsNont
contrapose!
rintro h₁ ⟨a, ha⟩
have ha₁ : a = a.val • 1 := by rw [nsmul_eq_mul, mul_one]; exact (ZMod.nat_cast_zmod_val a).symm
- rw [ha₁, map_nsmul_pow, h₁, one_pow] at ha
+ rw [ha₁, map_nsmul_pow, h₁, one_pow] at ha
exact ha rfl
#align add_char.zmod_char_is_nontrivial_iff AddChar.zmod_char_isNontrivial_iff
-/
@@ -401,7 +401,7 @@ theorem zmod_char_primitive_of_eq_one_only_at_zero (n : ℕ) (ψ : AddChar (ZMod
refine' fun a ha => (is_nontrivial_iff_ne_trivial _).mpr fun hf => _
have h : mul_shift ψ a 1 = (1 : AddChar (ZMod n) C) (1 : ZMod n) :=
congr_fun (congr_arg coeFn hf) 1
- rw [mul_shift_apply, mul_one, MonoidHom.one_apply] at h
+ rw [mul_shift_apply, mul_one, MonoidHom.one_apply] at h
exact ha (hψ a h)
#align add_char.zmod_char_primitive_of_eq_one_only_at_zero AddChar.zmod_char_primitive_of_eq_one_only_at_zero
-/
@@ -414,7 +414,7 @@ theorem zmodChar_primitive_of_primitive_root (n : ℕ+) {ζ : C} (h : IsPrimitiv
by
apply zmod_char_primitive_of_eq_one_only_at_zero
intro a ha
- rw [zmod_char_apply, ← pow_zero ζ] at ha
+ rw [zmod_char_apply, ← pow_zero ζ] at ha
exact (ZMod.val_eq_zero a).mp (IsPrimitiveRoot.pow_inj h (ZMod.val_lt a) n.pos ha)
#align add_char.zmod_char_primitive_of_primitive_root AddChar.zmodChar_primitive_of_primitive_root
-/
@@ -458,7 +458,7 @@ noncomputable def primitiveCharFiniteField (F F' : Type _) [Field F] [Fintype F]
have hψ' : is_nontrivial ψ' :=
by
obtain ⟨a, ha⟩ := FiniteField.trace_to_zmod_nondegenerate F one_ne_zero
- rw [one_mul] at ha
+ rw [one_mul] at ha
exact ⟨a, fun hf => ha <| (ψ.prim.zmod_char_eq_one_iff pp <| Algebra.trace (ZMod p) F a).mp hf⟩
exact ⟨ψ.n, ψ', hψ'.is_primitive⟩
#align add_char.primitive_char_finite_field AddChar.primitiveCharFiniteField
@@ -481,9 +481,9 @@ theorem sum_eq_zero_of_isNontrivial [IsDomain R'] {ψ : AddChar R R'} (hψ : IsN
rcases hψ with ⟨b, hb⟩
have h₁ : ∑ a : R, ψ (b + a) = ∑ a : R, ψ a :=
Fintype.sum_bijective _ (AddGroup.addLeft_bijective b) _ _ fun x => rfl
- simp_rw [map_add_mul] at h₁
+ simp_rw [map_add_mul] at h₁
have h₂ : ∑ a : R, ψ a = finset.univ.sum ⇑ψ := rfl
- rw [← Finset.mul_sum, h₂] at h₁
+ rw [← Finset.mul_sum, h₂] at h₁
exact eq_zero_of_mul_eq_self_left hb h₁
#align add_char.sum_eq_zero_of_is_nontrivial AddChar.sum_eq_zero_of_isNontrivial
-/
@@ -492,8 +492,8 @@ theorem sum_eq_zero_of_isNontrivial [IsDomain R'] {ψ : AddChar R R'} (hψ : IsN
/-- The sum over the values of the trivial additive character is the cardinality of the source. -/
theorem sum_eq_card_of_is_trivial {ψ : AddChar R R'} (hψ : ¬IsNontrivial ψ) :
∑ a, ψ a = Fintype.card R := by
- simp only [is_nontrivial] at hψ
- push_neg at hψ
+ simp only [is_nontrivial] at hψ
+ push_neg at hψ
simp only [hψ, Finset.sum_const, Nat.smul_one_eq_coe]
rfl
#align add_char.sum_eq_card_of_is_trivial AddChar.sum_eq_card_of_is_trivial
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -104,7 +104,7 @@ theorem coe_to_fun_apply (ψ : AddChar R R') (a : R) : ψ a = ψ.toMonoidHom (of
-/
instance monoidHomClass : MonoidHomClass (AddChar R R') (Multiplicative R) R' :=
- MonoidHom.monoidHomClass
+ MonoidHom.instMonoidHomClass
#align add_char.monoid_hom_class AddChar.monoidHomClass
#print AddChar.map_zero_one /-
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -192,7 +192,7 @@ def IsNontrivial (ψ : AddChar R R') : Prop :=
theorem isNontrivial_iff_ne_trivial (ψ : AddChar R R') : IsNontrivial ψ ↔ ψ ≠ 1 :=
by
refine' not_forall.symm.trans (Iff.not _)
- rw [FunLike.ext_iff]
+ rw [DFunLike.ext_iff]
rfl
#align add_char.is_nontrivial_iff_ne_trivial AddChar.isNontrivial_iff_ne_trivial
-/
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -90,14 +90,12 @@ def toMonoidHom : AddChar R R' → Multiplicative R →* R' :=
open Multiplicative
-#print AddChar.hasCoeToFun /-
/-- Define coercion to a function so that it includes the move from `R` to `multiplicative R`.
After we have proved the API lemmas below, we don't need to worry about writing `of_add a`
when we want to apply an additive character. -/
instance hasCoeToFun : CoeFun (AddChar R R') fun x => R → R'
where coe ψ x := ψ.toMonoidHom (ofAdd x)
#align add_char.has_coe_to_fun AddChar.hasCoeToFun
--/
#print AddChar.coe_to_fun_apply /-
theorem coe_to_fun_apply (ψ : AddChar R R') (a : R) : ψ a = ψ.toMonoidHom (ofAdd a) :=
@@ -105,11 +103,9 @@ theorem coe_to_fun_apply (ψ : AddChar R R') (a : R) : ψ a = ψ.toMonoidHom (of
#align add_char.coe_to_fun_apply AddChar.coe_to_fun_apply
-/
-#print AddChar.monoidHomClass /-
instance monoidHomClass : MonoidHomClass (AddChar R R') (Multiplicative R) R' :=
MonoidHom.monoidHomClass
#align add_char.monoid_hom_class AddChar.monoidHomClass
--/
#print AddChar.map_zero_one /-
/-- An additive character maps `0` to `1`. -/
mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451
@@ -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 Mathbin.NumberTheory.Cyclotomic.PrimitiveRoots
-import Mathbin.FieldTheory.Finite.Trace
+import NumberTheory.Cyclotomic.PrimitiveRoots
+import FieldTheory.Finite.Trace
#align_import number_theory.legendre_symbol.add_character from "leanprover-community/mathlib"@"fdc286cc6967a012f41b87f76dcd2797b53152af"
mathlib commit https://github.com/leanprover-community/mathlib/commit/32a7e535287f9c73f2e4d2aef306a39190f0b504
@@ -171,7 +171,7 @@ theorem map_zsmul_zpow {R' : Type v} [CommGroup R'] (ψ : AddChar R R') (n : ℤ
instance commGroup : CommGroup (AddChar R R') :=
{ MonoidHom.commMonoid with
inv := Inv.inv
- mul_left_inv := fun ψ => by ext;
+ hMul_left_inv := fun ψ => by ext;
rw [MonoidHom.mul_apply, MonoidHom.one_apply, inv_apply, ← map_add_mul, add_left_neg,
map_zero_one] }
#align add_char.comm_group AddChar.commGroup
mathlib commit https://github.com/leanprover-community/mathlib/commit/8ea5598db6caeddde6cb734aa179cc2408dbd345
@@ -2,15 +2,12 @@
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.add_character
-! leanprover-community/mathlib commit fdc286cc6967a012f41b87f76dcd2797b53152af
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
-/
import Mathbin.NumberTheory.Cyclotomic.PrimitiveRoots
import Mathbin.FieldTheory.Finite.Trace
+#align_import number_theory.legendre_symbol.add_character from "leanprover-community/mathlib"@"fdc286cc6967a012f41b87f76dcd2797b53152af"
+
/-!
# Additive characters of finite rings and fields
mathlib commit https://github.com/leanprover-community/mathlib/commit/fdc286cc6967a012f41b87f76dcd2797b53152af
@@ -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.add_character
-! leanprover-community/mathlib commit 0723536a0522d24fc2f159a096fb3304bef77472
+! leanprover-community/mathlib commit fdc286cc6967a012f41b87f76dcd2797b53152af
! Please do not edit these lines, except to modify the commit id
! if you have ported upstream changes.
-/
@@ -14,6 +14,9 @@ import Mathbin.FieldTheory.Finite.Trace
/-!
# Additive characters of finite rings and fields
+> THIS FILE IS SYNCHRONIZED WITH MATHLIB4.
+> Any changes to this file require a corresponding PR to mathlib4.
+
Let `R` be a finite commutative ring. An *additive character* of `R` with values
in another commutative ring `R'` is simply a morphism from the additive group
of `R` into the multiplicative monoid of `R'`.
mathlib commit https://github.com/leanprover-community/mathlib/commit/d30d31261cdb4d2f5e612eabc3c4bf45556350d5
@@ -60,6 +60,7 @@ variable (R : Type u) [AddMonoid R]
-- The target
variable (R' : Type v) [CommMonoid R']
+#print AddChar /-
/-- Define `add_char R R'` as `(multiplicative R) →* R'`.
The definition works for an additive monoid `R` and a monoid `R'`,
but we will restrict to the case that both are commutative rings below.
@@ -70,6 +71,7 @@ def AddChar : Type max u v :=
Multiplicative R →* R'
deriving CommMonoid, Inhabited
#align add_char AddChar
+-/
end AddCharDef
@@ -79,44 +81,58 @@ section CoeToFun
variable {R : Type u} [AddMonoid R] {R' : Type v} [CommMonoid R']
+#print AddChar.toMonoidHom /-
/-- Interpret an additive character as a monoid homomorphism. -/
def toMonoidHom : AddChar R R' → Multiplicative R →* R' :=
id
#align add_char.to_monoid_hom AddChar.toMonoidHom
+-/
open Multiplicative
+#print AddChar.hasCoeToFun /-
/-- Define coercion to a function so that it includes the move from `R` to `multiplicative R`.
After we have proved the API lemmas below, we don't need to worry about writing `of_add a`
when we want to apply an additive character. -/
instance hasCoeToFun : CoeFun (AddChar R R') fun x => R → R'
where coe ψ x := ψ.toMonoidHom (ofAdd x)
#align add_char.has_coe_to_fun AddChar.hasCoeToFun
+-/
+#print AddChar.coe_to_fun_apply /-
theorem coe_to_fun_apply (ψ : AddChar R R') (a : R) : ψ a = ψ.toMonoidHom (ofAdd a) :=
rfl
#align add_char.coe_to_fun_apply AddChar.coe_to_fun_apply
+-/
+#print AddChar.monoidHomClass /-
instance monoidHomClass : MonoidHomClass (AddChar R R') (Multiplicative R) R' :=
MonoidHom.monoidHomClass
#align add_char.monoid_hom_class AddChar.monoidHomClass
+-/
+#print AddChar.map_zero_one /-
/-- An additive character maps `0` to `1`. -/
@[simp]
theorem map_zero_one (ψ : AddChar R R') : ψ 0 = 1 := by rw [coe_to_fun_apply, ofAdd_zero, map_one]
#align add_char.map_zero_one AddChar.map_zero_one
+-/
+#print AddChar.map_add_mul /-
/-- An additive character maps sums to products. -/
@[simp]
theorem map_add_mul (ψ : AddChar R R') (x y : R) : ψ (x + y) = ψ x * ψ y := by
rw [coe_to_fun_apply, coe_to_fun_apply _ x, coe_to_fun_apply _ y, ofAdd_add, map_mul]
#align add_char.map_add_mul AddChar.map_add_mul
+-/
+#print AddChar.map_nsmul_pow /-
/-- An additive character maps multiples by natural numbers to powers. -/
@[simp]
theorem map_nsmul_pow (ψ : AddChar R R') (n : ℕ) (x : R) : ψ (n • x) = ψ x ^ n := by
rw [coe_to_fun_apply, coe_to_fun_apply _ x, ofAdd_nsmul, map_pow]
#align add_char.map_nsmul_pow AddChar.map_nsmul_pow
+-/
end CoeToFun
@@ -126,6 +142,7 @@ open Multiplicative
variable {R : Type u} [AddCommGroup R] {R' : Type v} [CommMonoid R']
+#print AddChar.hasInv /-
/-- An additive character on a commutative additive group has an inverse.
Note that this is a different inverse to the one provided by `monoid_hom.has_inv`,
@@ -133,17 +150,23 @@ as it acts on the domain instead of the codomain. -/
instance hasInv : Inv (AddChar R R') :=
⟨fun ψ => ψ.comp invMonoidHom⟩
#align add_char.has_inv AddChar.hasInv
+-/
+#print AddChar.inv_apply /-
theorem inv_apply (ψ : AddChar R R') (x : R) : ψ⁻¹ x = ψ (-x) :=
rfl
#align add_char.inv_apply AddChar.inv_apply
+-/
+#print AddChar.map_zsmul_zpow /-
/-- An additive character maps multiples by integers to powers. -/
@[simp]
theorem map_zsmul_zpow {R' : Type v} [CommGroup R'] (ψ : AddChar R R') (n : ℤ) (x : R) :
ψ (n • x) = ψ x ^ n := by rw [coe_to_fun_apply, coe_to_fun_apply _ x, ofAdd_zsmul, map_zpow]
#align add_char.map_zsmul_zpow AddChar.map_zsmul_zpow
+-/
+#print AddChar.commGroup /-
/-- The additive characters on a commutative additive group form a commutative group. -/
instance commGroup : CommGroup (AddChar R R') :=
{ MonoidHom.commMonoid with
@@ -152,6 +175,7 @@ instance commGroup : CommGroup (AddChar R R') :=
rw [MonoidHom.mul_apply, MonoidHom.one_apply, inv_apply, ← map_add_mul, add_left_neg,
map_zero_one] }
#align add_char.comm_group AddChar.commGroup
+-/
end GroupStructure
@@ -160,11 +184,14 @@ section Additive
-- The domain and target of our additive characters. Now we restrict to rings on both sides.
variable {R : Type u} [CommRing R] {R' : Type v} [CommRing R']
+#print AddChar.IsNontrivial /-
/-- An additive character is *nontrivial* if it takes a value `≠ 1`. -/
def IsNontrivial (ψ : AddChar R R') : Prop :=
∃ a : R, ψ a ≠ 1
#align add_char.is_nontrivial AddChar.IsNontrivial
+-/
+#print AddChar.isNontrivial_iff_ne_trivial /-
/-- An additive character is nontrivial iff it is not the trivial character. -/
theorem isNontrivial_iff_ne_trivial (ψ : AddChar R R') : IsNontrivial ψ ↔ ψ ≠ 1 :=
by
@@ -172,37 +199,49 @@ theorem isNontrivial_iff_ne_trivial (ψ : AddChar R R') : IsNontrivial ψ ↔ ψ
rw [FunLike.ext_iff]
rfl
#align add_char.is_nontrivial_iff_ne_trivial AddChar.isNontrivial_iff_ne_trivial
+-/
+#print AddChar.mulShift /-
/-- Define the multiplicative shift of an additive character.
This satisfies `mul_shift ψ a x = ψ (a * x)`. -/
def mulShift (ψ : AddChar R R') (a : R) : AddChar R R' :=
ψ.comp (AddMonoidHom.mulLeft a).toMultiplicative
#align add_char.mul_shift AddChar.mulShift
+-/
+#print AddChar.mulShift_apply /-
@[simp]
theorem mulShift_apply {ψ : AddChar R R'} {a : R} {x : R} : mulShift ψ a x = ψ (a * x) :=
rfl
#align add_char.mul_shift_apply AddChar.mulShift_apply
+-/
+#print AddChar.inv_mulShift /-
/-- `ψ⁻¹ = mul_shift ψ (-1))`. -/
theorem inv_mulShift (ψ : AddChar R R') : ψ⁻¹ = mulShift ψ (-1) :=
by
ext
rw [inv_apply, mul_shift_apply, neg_mul, one_mul]
#align add_char.inv_mul_shift AddChar.inv_mulShift
+-/
+#print AddChar.mulShift_spec' /-
/-- If `n` is a natural number, then `mul_shift ψ n x = (ψ x) ^ n`. -/
theorem mulShift_spec' (ψ : AddChar R R') (n : ℕ) (x : R) : mulShift ψ n x = ψ x ^ n := by
rw [mul_shift_apply, ← nsmul_eq_mul, map_nsmul_pow]
#align add_char.mul_shift_spec' AddChar.mulShift_spec'
+-/
+#print AddChar.pow_mulShift /-
/-- If `n` is a natural number, then `ψ ^ n = mul_shift ψ n`. -/
theorem pow_mulShift (ψ : AddChar R R') (n : ℕ) : ψ ^ n = mulShift ψ n :=
by
ext x
rw [show (ψ ^ n) x = ψ x ^ n from rfl, ← mul_shift_spec']
#align add_char.pow_mul_shift AddChar.pow_mulShift
+-/
+#print AddChar.mulShift_mul /-
/-- The product of `mul_shift ψ a` and `mul_shift ψ b` is `mul_shift ψ (a + b)`. -/
theorem mulShift_mul (ψ : AddChar R R') (a b : R) :
mulShift ψ a * mulShift ψ b = mulShift ψ (a + b) :=
@@ -210,7 +249,9 @@ theorem mulShift_mul (ψ : AddChar R R') (a b : R) :
ext
simp only [right_distrib, MonoidHom.mul_apply, mul_shift_apply, map_add_mul]
#align add_char.mul_shift_mul AddChar.mulShift_mul
+-/
+#print AddChar.mulShift_zero /-
/-- `mul_shift ψ 0` is the trivial character. -/
@[simp]
theorem mulShift_zero (ψ : AddChar R R') : mulShift ψ 0 = 1 :=
@@ -218,13 +259,17 @@ theorem mulShift_zero (ψ : AddChar R R') : mulShift ψ 0 = 1 :=
ext
simp only [mul_shift_apply, MulZeroClass.zero_mul, map_zero_one, MonoidHom.one_apply]
#align add_char.mul_shift_zero AddChar.mulShift_zero
+-/
+#print AddChar.IsPrimitive /-
/-- An additive character is *primitive* iff all its multiplicative shifts by nonzero
elements are nontrivial. -/
def IsPrimitive (ψ : AddChar R R') : Prop :=
∀ a : R, a ≠ 0 → IsNontrivial (mulShift ψ a)
#align add_char.is_primitive AddChar.IsPrimitive
+-/
+#print AddChar.to_mulShift_inj_of_isPrimitive /-
/-- The map associating to `a : R` the multiplicative shift of `ψ` by `a`
is injective when `ψ` is primitive. -/
theorem to_mulShift_inj_of_isPrimitive {ψ : AddChar R R'} (hψ : IsPrimitive ψ) :
@@ -236,7 +281,9 @@ theorem to_mulShift_inj_of_isPrimitive {ψ : AddChar R R'} (hψ : IsPrimitive ψ
rw [h, is_nontrivial_iff_ne_trivial, ← sub_eq_add_neg, sub_ne_zero] at h₂
exact not_not.mp fun h => h₂ h rfl
#align add_char.to_mul_shift_inj_of_is_primitive AddChar.to_mulShift_inj_of_isPrimitive
+-/
+#print AddChar.IsNontrivial.isPrimitive /-
-- `add_comm_group.equiv_direct_sum_zmod_of_fintype`
-- gives the structure theorem for finite abelian groups.
-- This could be used to show that the map above is a bijection.
@@ -249,7 +296,9 @@ theorem IsNontrivial.isPrimitive {F : Type u} [Field F] {ψ : AddChar F R'} (hψ
use a⁻¹ * x
rwa [mul_shift_apply, mul_inv_cancel_left₀ ha]
#align add_char.is_nontrivial.is_primitive AddChar.IsNontrivial.isPrimitive
+-/
+#print AddChar.PrimitiveAddChar /-
-- Using `structure` gives a timeout, see
-- https://leanprover.zulipchat.com/#narrow/stream/287929-mathlib4/topic/mysterious.20finsupp.20related.20timeout/near/365719262 and
-- https://leanprover.zulipchat.com/#narrow/stream/287929-mathlib4/topic/mysterious.20finsupp.20related.20timeout
@@ -262,21 +311,28 @@ fact that the character is primitive. -/
def PrimitiveAddChar (R : Type u) [CommRing R] (R' : Type v) [Field R'] :=
Σ n : ℕ+, Σ' char : AddChar R (CyclotomicField n R'), IsPrimitive Char
#align add_char.primitive_add_char AddChar.PrimitiveAddChar
+-/
+#print AddChar.PrimitiveAddChar.n /-
/-- The first projection from `primitive_add_char`, giving the cyclotomic field. -/
noncomputable def PrimitiveAddChar.n {R : Type u} [CommRing R] {R' : Type v} [Field R'] :
PrimitiveAddChar R R' → ℕ+ := fun χ => χ.1
#align add_char.primitive_add_char.n AddChar.PrimitiveAddChar.n
+-/
+#print AddChar.PrimitiveAddChar.char /-
/-- The second projection from `primitive_add_char`, giving the character. -/
noncomputable def PrimitiveAddChar.char {R : Type u} [CommRing R] {R' : Type v} [Field R'] :
∀ χ : PrimitiveAddChar R R', AddChar R (CyclotomicField χ.n R') := fun χ => χ.2.1
#align add_char.primitive_add_char.char AddChar.PrimitiveAddChar.char
+-/
+#print AddChar.PrimitiveAddChar.prim /-
/-- The third projection from `primitive_add_char`, showing that `χ.2` is primitive. -/
theorem PrimitiveAddChar.prim {R : Type u} [CommRing R] {R' : Type v} [Field R'] :
∀ χ : PrimitiveAddChar R R', IsPrimitive χ.Char := fun χ => χ.2.2
#align add_char.primitive_add_char.prim AddChar.PrimitiveAddChar.prim
+-/
/-!
### Additive characters on `zmod n`
@@ -289,6 +345,7 @@ section ZmodCharDef
open Multiplicative
+#print AddChar.zmodChar /-
-- so we can write simply `to_add`, which we need here again
/-- We can define an additive character on `zmod n` when we have an `n`th root of unity `ζ : C`. -/
def zmodChar (n : ℕ+) {ζ : C} (hζ : ζ ^ ↑n = 1) : AddChar (ZMod n) C
@@ -298,21 +355,27 @@ def zmodChar (n : ℕ+) {ζ : C} (hζ : ζ ^ ↑n = 1) : AddChar (ZMod n) C
map_mul' x y := by
rw [toAdd_mul, ← pow_add, ZMod.val_add (to_add x) (to_add y), ← pow_eq_pow_mod _ hζ]
#align add_char.zmod_char AddChar.zmodChar
+-/
+#print AddChar.zmodChar_apply /-
/-- The additive character on `zmod n` defined using `ζ` sends `a` to `ζ^a`. -/
theorem zmodChar_apply {n : ℕ+} {ζ : C} (hζ : ζ ^ ↑n = 1) (a : ZMod n) :
zmodChar n hζ a = ζ ^ a.val :=
rfl
#align add_char.zmod_char_apply AddChar.zmodChar_apply
+-/
+#print AddChar.zmodChar_apply' /-
theorem zmodChar_apply' {n : ℕ+} {ζ : C} (hζ : ζ ^ ↑n = 1) (a : ℕ) : zmodChar n hζ a = ζ ^ a := by
rw [pow_eq_pow_mod a hζ, zmod_char_apply, ZMod.val_nat_cast a]
#align add_char.zmod_char_apply' AddChar.zmodChar_apply'
+-/
end ZmodCharDef
+#print AddChar.zmod_char_isNontrivial_iff /-
/-- An additive character on `zmod n` is nontrivial iff it takes a value `≠ 1` on `1`. -/
-theorem zMod_char_isNontrivial_iff (n : ℕ+) (ψ : AddChar (ZMod n) C) : IsNontrivial ψ ↔ ψ 1 ≠ 1 :=
+theorem zmod_char_isNontrivial_iff (n : ℕ+) (ψ : AddChar (ZMod n) C) : IsNontrivial ψ ↔ ψ 1 ≠ 1 :=
by
refine' ⟨_, fun h => ⟨1, h⟩⟩
contrapose!
@@ -320,19 +383,23 @@ theorem zMod_char_isNontrivial_iff (n : ℕ+) (ψ : AddChar (ZMod n) C) : IsNont
have ha₁ : a = a.val • 1 := by rw [nsmul_eq_mul, mul_one]; exact (ZMod.nat_cast_zmod_val a).symm
rw [ha₁, map_nsmul_pow, h₁, one_pow] at ha
exact ha rfl
-#align add_char.zmod_char_is_nontrivial_iff AddChar.zMod_char_isNontrivial_iff
+#align add_char.zmod_char_is_nontrivial_iff AddChar.zmod_char_isNontrivial_iff
+-/
+#print AddChar.IsPrimitive.zmod_char_eq_one_iff /-
/-- A primitive additive character on `zmod n` takes the value `1` only at `0`. -/
-theorem IsPrimitive.zMod_char_eq_one_iff (n : ℕ+) {ψ : AddChar (ZMod n) C} (hψ : IsPrimitive ψ)
+theorem IsPrimitive.zmod_char_eq_one_iff (n : ℕ+) {ψ : AddChar (ZMod n) C} (hψ : IsPrimitive ψ)
(a : ZMod n) : ψ a = 1 ↔ a = 0 :=
by
refine' ⟨fun h => not_imp_comm.mp (hψ a) _, fun ha => by rw [ha, map_zero_one]⟩
rw [zmod_char_is_nontrivial_iff n (mul_shift ψ a), mul_shift_apply, mul_one, h, Classical.not_not]
-#align add_char.is_primitive.zmod_char_eq_one_iff AddChar.IsPrimitive.zMod_char_eq_one_iff
+#align add_char.is_primitive.zmod_char_eq_one_iff AddChar.IsPrimitive.zmod_char_eq_one_iff
+-/
+#print AddChar.zmod_char_primitive_of_eq_one_only_at_zero /-
/-- The converse: if the additive character takes the value `1` only at `0`,
then it is primitive. -/
-theorem zMod_char_primitive_of_eq_one_only_at_zero (n : ℕ) (ψ : AddChar (ZMod n) C)
+theorem zmod_char_primitive_of_eq_one_only_at_zero (n : ℕ) (ψ : AddChar (ZMod n) C)
(hψ : ∀ a, ψ a = 1 → a = 0) : IsPrimitive ψ :=
by
refine' fun a ha => (is_nontrivial_iff_ne_trivial _).mpr fun hf => _
@@ -340,8 +407,10 @@ theorem zMod_char_primitive_of_eq_one_only_at_zero (n : ℕ) (ψ : AddChar (ZMod
congr_fun (congr_arg coeFn hf) 1
rw [mul_shift_apply, mul_one, MonoidHom.one_apply] at h
exact ha (hψ a h)
-#align add_char.zmod_char_primitive_of_eq_one_only_at_zero AddChar.zMod_char_primitive_of_eq_one_only_at_zero
+#align add_char.zmod_char_primitive_of_eq_one_only_at_zero AddChar.zmod_char_primitive_of_eq_one_only_at_zero
+-/
+#print AddChar.zmodChar_primitive_of_primitive_root /-
/-- The additive character on `zmod n` associated to a primitive `n`th root of unity
is primitive -/
theorem zmodChar_primitive_of_primitive_root (n : ℕ+) {ζ : C} (h : IsPrimitiveRoot ζ n) :
@@ -352,21 +421,25 @@ theorem zmodChar_primitive_of_primitive_root (n : ℕ+) {ζ : C} (h : IsPrimitiv
rw [zmod_char_apply, ← pow_zero ζ] at ha
exact (ZMod.val_eq_zero a).mp (IsPrimitiveRoot.pow_inj h (ZMod.val_lt a) n.pos ha)
#align add_char.zmod_char_primitive_of_primitive_root AddChar.zmodChar_primitive_of_primitive_root
+-/
+#print AddChar.primitiveZModChar /-
/-- There is a primitive additive character on `zmod n` if the characteristic of the target
does not divide `n` -/
-noncomputable def primitiveZmodChar (n : ℕ+) (F' : Type v) [Field F'] (h : (n : F') ≠ 0) :
+noncomputable def primitiveZModChar (n : ℕ+) (F' : Type v) [Field F'] (h : (n : F') ≠ 0) :
PrimitiveAddChar (ZMod n) F' :=
haveI : NeZero ((n : ℕ) : F') := ⟨h⟩
⟨n, zmod_char n (IsCyclotomicExtension.zeta_pow n F' _),
zmod_char_primitive_of_primitive_root n (IsCyclotomicExtension.zeta_spec n F' _)⟩
-#align add_char.primitive_zmod_char AddChar.primitiveZmodChar
+#align add_char.primitive_zmod_char AddChar.primitiveZModChar
+-/
/-!
### Existence of a primitive additive character on a finite field
-/
+#print AddChar.primitiveCharFiniteField /-
/-- There is a primitive additive character on the finite field `F` if the characteristic
of the target is different from that of `F`.
We obtain it as the composition of the trace from `F` to `zmod p` with a primitive
@@ -388,11 +461,12 @@ noncomputable def primitiveCharFiniteField (F F' : Type _) [Field F] [Fintype F]
let ψ' := ψ.char.comp (Algebra.trace (ZMod p) F).toAddMonoidHom.toMultiplicative
have hψ' : is_nontrivial ψ' :=
by
- obtain ⟨a, ha⟩ := FiniteField.trace_to_zMod_nondegenerate F one_ne_zero
+ obtain ⟨a, ha⟩ := FiniteField.trace_to_zmod_nondegenerate F one_ne_zero
rw [one_mul] at ha
exact ⟨a, fun hf => ha <| (ψ.prim.zmod_char_eq_one_iff pp <| Algebra.trace (ZMod p) F a).mp hf⟩
exact ⟨ψ.n, ψ', hψ'.is_primitive⟩
#align add_char.primitive_char_finite_field AddChar.primitiveCharFiniteField
+-/
/-!
### The sum of all character values
@@ -403,6 +477,7 @@ open scoped BigOperators
variable [Fintype R]
+#print AddChar.sum_eq_zero_of_isNontrivial /-
/-- The sum over the values of a nontrivial additive character vanishes if the target ring
is a domain. -/
theorem sum_eq_zero_of_isNontrivial [IsDomain R'] {ψ : AddChar R R'} (hψ : IsNontrivial ψ) :
@@ -415,7 +490,9 @@ theorem sum_eq_zero_of_isNontrivial [IsDomain R'] {ψ : AddChar R R'} (hψ : IsN
rw [← Finset.mul_sum, h₂] at h₁
exact eq_zero_of_mul_eq_self_left hb h₁
#align add_char.sum_eq_zero_of_is_nontrivial AddChar.sum_eq_zero_of_isNontrivial
+-/
+#print AddChar.sum_eq_card_of_is_trivial /-
/-- The sum over the values of the trivial additive character is the cardinality of the source. -/
theorem sum_eq_card_of_is_trivial {ψ : AddChar R R'} (hψ : ¬IsNontrivial ψ) :
∑ a, ψ a = Fintype.card R := by
@@ -424,11 +501,13 @@ theorem sum_eq_card_of_is_trivial {ψ : AddChar R R'} (hψ : ¬IsNontrivial ψ)
simp only [hψ, Finset.sum_const, Nat.smul_one_eq_coe]
rfl
#align add_char.sum_eq_card_of_is_trivial AddChar.sum_eq_card_of_is_trivial
+-/
+#print AddChar.sum_mulShift /-
/-- The sum over the values of `mul_shift ψ b` for `ψ` primitive is zero when `b ≠ 0`
and `#R` otherwise. -/
-theorem sum_mul_shift [DecidableEq R] [IsDomain R'] {ψ : AddChar R R'} (b : R)
- (hψ : IsPrimitive ψ) : ∑ x : R, ψ (x * b) = if b = 0 then Fintype.card R else 0 :=
+theorem sum_mulShift [DecidableEq R] [IsDomain R'] {ψ : AddChar R R'} (b : R) (hψ : IsPrimitive ψ) :
+ ∑ x : R, ψ (x * b) = if b = 0 then Fintype.card R else 0 :=
by
split_ifs with h
· -- case `b = 0`
@@ -437,7 +516,8 @@ theorem sum_mul_shift [DecidableEq R] [IsDomain R'] {ψ : AddChar R R'} (b : R)
· -- case `b ≠ 0`
simp_rw [mul_comm]
exact sum_eq_zero_of_is_nontrivial (hψ b h)
-#align add_char.sum_mul_shift AddChar.sum_mul_shift
+#align add_char.sum_mul_shift AddChar.sum_mulShift
+-/
end Additive
mathlib commit https://github.com/leanprover-community/mathlib/commit/0723536a0522d24fc2f159a096fb3304bef77472
@@ -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.add_character
-! leanprover-community/mathlib commit e3f4be1fcb5376c4948d7f095bec45350bfb9d1a
+! leanprover-community/mathlib commit 0723536a0522d24fc2f159a096fb3304bef77472
! Please do not edit these lines, except to modify the commit id
! if you have ported upstream changes.
-/
@@ -384,6 +384,7 @@ noncomputable def primitiveCharFiniteField (F F' : Type _) [Field F] [Fintype F]
· rw [hq]
exact fun hf => Nat.Prime.ne_zero hp.1 (zero_dvd_iff.mp hf)
let ψ := primitive_zmod_char pp F' (ne_zero_iff.mp (NeZero.of_not_dvd F' hp₂))
+ letI : Algebra (ZMod p) F := ZMod.algebra _ _
let ψ' := ψ.char.comp (Algebra.trace (ZMod p) F).toAddMonoidHom.toMultiplicative
have hψ' : is_nontrivial ψ' :=
by
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.add_character
-! leanprover-community/mathlib commit 70fd9563a21e7b963887c9360bd29b2393e6225a
+! leanprover-community/mathlib commit e3f4be1fcb5376c4948d7f095bec45350bfb9d1a
! Please do not edit these lines, except to modify the commit id
! if you have ported upstream changes.
-/
@@ -250,17 +250,34 @@ theorem IsNontrivial.isPrimitive {F : Type u} [Field F] {ψ : AddChar F R'} (hψ
rwa [mul_shift_apply, mul_inv_cancel_left₀ ha]
#align add_char.is_nontrivial.is_primitive AddChar.IsNontrivial.isPrimitive
+-- Using `structure` gives a timeout, see
+-- https://leanprover.zulipchat.com/#narrow/stream/287929-mathlib4/topic/mysterious.20finsupp.20related.20timeout/near/365719262 and
+-- https://leanprover.zulipchat.com/#narrow/stream/287929-mathlib4/topic/mysterious.20finsupp.20related.20timeout
+-- In Lean4, `set_option genInjectivity false in` may solve this issue.
-- can't prove that they always exist
-/-- Structure for a primitive additive character on a finite ring `R` into a cyclotomic extension
+/-- Definition for a primitive additive character on a finite ring `R` into a cyclotomic extension
of a field `R'`. It records which cyclotomic extension it is, the character, and the
fact that the character is primitive. -/
@[nolint has_nonempty_instance]
-structure PrimitiveAddChar (R : Type u) [CommRing R] [Fintype R] (R' : Type v) [Field R'] where
- n : ℕ+
- Char : AddChar R (CyclotomicField n R')
- prim : IsPrimitive Char
+def PrimitiveAddChar (R : Type u) [CommRing R] (R' : Type v) [Field R'] :=
+ Σ n : ℕ+, Σ' char : AddChar R (CyclotomicField n R'), IsPrimitive Char
#align add_char.primitive_add_char AddChar.PrimitiveAddChar
+/-- The first projection from `primitive_add_char`, giving the cyclotomic field. -/
+noncomputable def PrimitiveAddChar.n {R : Type u} [CommRing R] {R' : Type v} [Field R'] :
+ PrimitiveAddChar R R' → ℕ+ := fun χ => χ.1
+#align add_char.primitive_add_char.n AddChar.PrimitiveAddChar.n
+
+/-- The second projection from `primitive_add_char`, giving the character. -/
+noncomputable def PrimitiveAddChar.char {R : Type u} [CommRing R] {R' : Type v} [Field R'] :
+ ∀ χ : PrimitiveAddChar R R', AddChar R (CyclotomicField χ.n R') := fun χ => χ.2.1
+#align add_char.primitive_add_char.char AddChar.PrimitiveAddChar.char
+
+/-- The third projection from `primitive_add_char`, showing that `χ.2` is primitive. -/
+theorem PrimitiveAddChar.prim {R : Type u} [CommRing R] {R' : Type v} [Field R'] :
+ ∀ χ : PrimitiveAddChar R R', IsPrimitive χ.Char := fun χ => χ.2.2
+#align add_char.primitive_add_char.prim AddChar.PrimitiveAddChar.prim
+
/-!
### Additive characters on `zmod n`
-/
@@ -341,9 +358,8 @@ does not divide `n` -/
noncomputable def primitiveZmodChar (n : ℕ+) (F' : Type v) [Field F'] (h : (n : F') ≠ 0) :
PrimitiveAddChar (ZMod n) F' :=
haveI : NeZero ((n : ℕ) : F') := ⟨h⟩
- { n
- Char := zmod_char n (IsCyclotomicExtension.zeta_pow n F' _)
- prim := zmod_char_primitive_of_primitive_root n (IsCyclotomicExtension.zeta_spec n F' _) }
+ ⟨n, zmod_char n (IsCyclotomicExtension.zeta_pow n F' _),
+ zmod_char_primitive_of_primitive_root n (IsCyclotomicExtension.zeta_spec n F' _)⟩
#align add_char.primitive_zmod_char AddChar.primitiveZmodChar
/-!
@@ -374,10 +390,7 @@ noncomputable def primitiveCharFiniteField (F F' : Type _) [Field F] [Fintype F]
obtain ⟨a, ha⟩ := FiniteField.trace_to_zMod_nondegenerate F one_ne_zero
rw [one_mul] at ha
exact ⟨a, fun hf => ha <| (ψ.prim.zmod_char_eq_one_iff pp <| Algebra.trace (ZMod p) F a).mp hf⟩
- exact
- { n := ψ.n
- Char := ψ'
- prim := hψ'.is_primitive }
+ exact ⟨ψ.n, ψ', hψ'.is_primitive⟩
#align add_char.primitive_char_finite_field AddChar.primitiveCharFiniteField
/-!
mathlib commit https://github.com/leanprover-community/mathlib/commit/a3e83f0fa4391c8740f7d773a7a9b74e311ae2a3
@@ -392,20 +392,19 @@ variable [Fintype R]
/-- The sum over the values of a nontrivial additive character vanishes if the target ring
is a domain. -/
theorem sum_eq_zero_of_isNontrivial [IsDomain R'] {ψ : AddChar R R'} (hψ : IsNontrivial ψ) :
- (∑ a, ψ a) = 0 := by
+ ∑ a, ψ a = 0 := by
rcases hψ with ⟨b, hb⟩
- have h₁ : (∑ a : R, ψ (b + a)) = ∑ a : R, ψ a :=
+ have h₁ : ∑ a : R, ψ (b + a) = ∑ a : R, ψ a :=
Fintype.sum_bijective _ (AddGroup.addLeft_bijective b) _ _ fun x => rfl
simp_rw [map_add_mul] at h₁
- have h₂ : (∑ a : R, ψ a) = finset.univ.sum ⇑ψ := rfl
+ have h₂ : ∑ a : R, ψ a = finset.univ.sum ⇑ψ := rfl
rw [← Finset.mul_sum, h₂] at h₁
exact eq_zero_of_mul_eq_self_left hb h₁
#align add_char.sum_eq_zero_of_is_nontrivial AddChar.sum_eq_zero_of_isNontrivial
/-- The sum over the values of the trivial additive character is the cardinality of the source. -/
theorem sum_eq_card_of_is_trivial {ψ : AddChar R R'} (hψ : ¬IsNontrivial ψ) :
- (∑ a, ψ a) = Fintype.card R :=
- by
+ ∑ a, ψ a = Fintype.card R := by
simp only [is_nontrivial] at hψ
push_neg at hψ
simp only [hψ, Finset.sum_const, Nat.smul_one_eq_coe]
@@ -415,7 +414,7 @@ theorem sum_eq_card_of_is_trivial {ψ : AddChar R R'} (hψ : ¬IsNontrivial ψ)
/-- The sum over the values of `mul_shift ψ b` for `ψ` primitive is zero when `b ≠ 0`
and `#R` otherwise. -/
theorem sum_mul_shift [DecidableEq R] [IsDomain R'] {ψ : AddChar R R'} (b : R)
- (hψ : IsPrimitive ψ) : (∑ x : R, ψ (x * b)) = if b = 0 then Fintype.card R else 0 :=
+ (hψ : IsPrimitive ψ) : ∑ x : R, ψ (x * b) = if b = 0 then Fintype.card R else 0 :=
by
split_ifs with h
· -- case `b = 0`
mathlib commit https://github.com/leanprover-community/mathlib/commit/5f25c089cb34db4db112556f23c50d12da81b297
@@ -230,7 +230,7 @@ is injective when `ψ` is primitive. -/
theorem to_mulShift_inj_of_isPrimitive {ψ : AddChar R R'} (hψ : IsPrimitive ψ) :
Function.Injective ψ.mulShift := by
intro a b h
- apply_fun fun x => x * mul_shift ψ (-b) at h
+ apply_fun fun x => x * mul_shift ψ (-b) at h
simp only [mul_shift_mul, mul_shift_zero, add_right_neg] at h
have h₂ := hψ (a + -b)
rw [h, is_nontrivial_iff_ne_trivial, ← sub_eq_add_neg, sub_ne_zero] at h₂
@@ -407,7 +407,7 @@ theorem sum_eq_card_of_is_trivial {ψ : AddChar R R'} (hψ : ¬IsNontrivial ψ)
(∑ a, ψ a) = Fintype.card R :=
by
simp only [is_nontrivial] at hψ
- push_neg at hψ
+ push_neg at hψ
simp only [hψ, Finset.sum_const, Nat.smul_one_eq_coe]
rfl
#align add_char.sum_eq_card_of_is_trivial AddChar.sum_eq_card_of_is_trivial
mathlib commit https://github.com/leanprover-community/mathlib/commit/cca40788df1b8755d5baf17ab2f27dacc2e17acb
@@ -67,7 +67,8 @@ We assume right away that `R'` is commutative, so that `add_char R R'` carries
a structure of commutative monoid.
The trivial additive character (sending everything to `1`) is `(1 : add_char R R').` -/
def AddChar : Type max u v :=
- Multiplicative R →* R' deriving CommMonoid, Inhabited
+ Multiplicative R →* R'
+deriving CommMonoid, Inhabited
#align add_char AddChar
end AddCharDef
@@ -229,10 +230,10 @@ is injective when `ψ` is primitive. -/
theorem to_mulShift_inj_of_isPrimitive {ψ : AddChar R R'} (hψ : IsPrimitive ψ) :
Function.Injective ψ.mulShift := by
intro a b h
- apply_fun fun x => x * mul_shift ψ (-b) at h
- simp only [mul_shift_mul, mul_shift_zero, add_right_neg] at h
+ apply_fun fun x => x * mul_shift ψ (-b) at h
+ simp only [mul_shift_mul, mul_shift_zero, add_right_neg] at h
have h₂ := hψ (a + -b)
- rw [h, is_nontrivial_iff_ne_trivial, ← sub_eq_add_neg, sub_ne_zero] at h₂
+ rw [h, is_nontrivial_iff_ne_trivial, ← sub_eq_add_neg, sub_ne_zero] at h₂
exact not_not.mp fun h => h₂ h rfl
#align add_char.to_mul_shift_inj_of_is_primitive AddChar.to_mulShift_inj_of_isPrimitive
@@ -300,7 +301,7 @@ theorem zMod_char_isNontrivial_iff (n : ℕ+) (ψ : AddChar (ZMod n) C) : IsNont
contrapose!
rintro h₁ ⟨a, ha⟩
have ha₁ : a = a.val • 1 := by rw [nsmul_eq_mul, mul_one]; exact (ZMod.nat_cast_zmod_val a).symm
- rw [ha₁, map_nsmul_pow, h₁, one_pow] at ha
+ rw [ha₁, map_nsmul_pow, h₁, one_pow] at ha
exact ha rfl
#align add_char.zmod_char_is_nontrivial_iff AddChar.zMod_char_isNontrivial_iff
@@ -320,7 +321,7 @@ theorem zMod_char_primitive_of_eq_one_only_at_zero (n : ℕ) (ψ : AddChar (ZMod
refine' fun a ha => (is_nontrivial_iff_ne_trivial _).mpr fun hf => _
have h : mul_shift ψ a 1 = (1 : AddChar (ZMod n) C) (1 : ZMod n) :=
congr_fun (congr_arg coeFn hf) 1
- rw [mul_shift_apply, mul_one, MonoidHom.one_apply] at h
+ rw [mul_shift_apply, mul_one, MonoidHom.one_apply] at h
exact ha (hψ a h)
#align add_char.zmod_char_primitive_of_eq_one_only_at_zero AddChar.zMod_char_primitive_of_eq_one_only_at_zero
@@ -331,7 +332,7 @@ theorem zmodChar_primitive_of_primitive_root (n : ℕ+) {ζ : C} (h : IsPrimitiv
by
apply zmod_char_primitive_of_eq_one_only_at_zero
intro a ha
- rw [zmod_char_apply, ← pow_zero ζ] at ha
+ rw [zmod_char_apply, ← pow_zero ζ] at ha
exact (ZMod.val_eq_zero a).mp (IsPrimitiveRoot.pow_inj h (ZMod.val_lt a) n.pos ha)
#align add_char.zmod_char_primitive_of_primitive_root AddChar.zmodChar_primitive_of_primitive_root
@@ -371,7 +372,7 @@ noncomputable def primitiveCharFiniteField (F F' : Type _) [Field F] [Fintype F]
have hψ' : is_nontrivial ψ' :=
by
obtain ⟨a, ha⟩ := FiniteField.trace_to_zMod_nondegenerate F one_ne_zero
- rw [one_mul] at ha
+ rw [one_mul] at ha
exact ⟨a, fun hf => ha <| (ψ.prim.zmod_char_eq_one_iff pp <| Algebra.trace (ZMod p) F a).mp hf⟩
exact
{ n := ψ.n
@@ -395,9 +396,9 @@ theorem sum_eq_zero_of_isNontrivial [IsDomain R'] {ψ : AddChar R R'} (hψ : IsN
rcases hψ with ⟨b, hb⟩
have h₁ : (∑ a : R, ψ (b + a)) = ∑ a : R, ψ a :=
Fintype.sum_bijective _ (AddGroup.addLeft_bijective b) _ _ fun x => rfl
- simp_rw [map_add_mul] at h₁
+ simp_rw [map_add_mul] at h₁
have h₂ : (∑ a : R, ψ a) = finset.univ.sum ⇑ψ := rfl
- rw [← Finset.mul_sum, h₂] at h₁
+ rw [← Finset.mul_sum, h₂] at h₁
exact eq_zero_of_mul_eq_self_left hb h₁
#align add_char.sum_eq_zero_of_is_nontrivial AddChar.sum_eq_zero_of_isNontrivial
@@ -405,8 +406,8 @@ theorem sum_eq_zero_of_isNontrivial [IsDomain R'] {ψ : AddChar R R'} (hψ : IsN
theorem sum_eq_card_of_is_trivial {ψ : AddChar R R'} (hψ : ¬IsNontrivial ψ) :
(∑ a, ψ a) = Fintype.card R :=
by
- simp only [is_nontrivial] at hψ
- push_neg at hψ
+ simp only [is_nontrivial] at hψ
+ push_neg at hψ
simp only [hψ, Finset.sum_const, Nat.smul_one_eq_coe]
rfl
#align add_char.sum_eq_card_of_is_trivial AddChar.sum_eq_card_of_is_trivial
mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb
@@ -384,7 +384,7 @@ noncomputable def primitiveCharFiniteField (F F' : Type _) [Field F] [Fintype F]
-/
-open BigOperators
+open scoped BigOperators
variable [Fintype R]
mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb
@@ -147,8 +147,7 @@ theorem map_zsmul_zpow {R' : Type v} [CommGroup R'] (ψ : AddChar R R') (n : ℤ
instance commGroup : CommGroup (AddChar R R') :=
{ MonoidHom.commMonoid with
inv := Inv.inv
- mul_left_inv := fun ψ => by
- ext
+ mul_left_inv := fun ψ => by ext;
rw [MonoidHom.mul_apply, MonoidHom.one_apply, inv_apply, ← map_add_mul, add_left_neg,
map_zero_one] }
#align add_char.comm_group AddChar.commGroup
@@ -300,9 +299,7 @@ theorem zMod_char_isNontrivial_iff (n : ℕ+) (ψ : AddChar (ZMod n) C) : IsNont
refine' ⟨_, fun h => ⟨1, h⟩⟩
contrapose!
rintro h₁ ⟨a, ha⟩
- have ha₁ : a = a.val • 1 := by
- rw [nsmul_eq_mul, mul_one]
- exact (ZMod.nat_cast_zmod_val a).symm
+ have ha₁ : a = a.val • 1 := by rw [nsmul_eq_mul, mul_one]; exact (ZMod.nat_cast_zmod_val a).symm
rw [ha₁, map_nsmul_pow, h₁, one_pow] at ha
exact ha rfl
#align add_char.zmod_char_is_nontrivial_iff AddChar.zMod_char_isNontrivial_iff
mathlib commit https://github.com/leanprover-community/mathlib/commit/02ba8949f486ebecf93fe7460f1ed0564b5e442c
@@ -302,7 +302,7 @@ theorem zMod_char_isNontrivial_iff (n : ℕ+) (ψ : AddChar (ZMod n) C) : IsNont
rintro h₁ ⟨a, ha⟩
have ha₁ : a = a.val • 1 := by
rw [nsmul_eq_mul, mul_one]
- exact (ZMod.nat_cast_zMod_val a).symm
+ exact (ZMod.nat_cast_zmod_val a).symm
rw [ha₁, map_nsmul_pow, h₁, one_pow] at ha
exact ha rfl
#align add_char.zmod_char_is_nontrivial_iff AddChar.zMod_char_isNontrivial_iff
mathlib commit https://github.com/leanprover-community/mathlib/commit/3180fab693e2cee3bff62675571264cb8778b212
@@ -216,7 +216,7 @@ theorem mulShift_mul (ψ : AddChar R R') (a b : R) :
theorem mulShift_zero (ψ : AddChar R R') : mulShift ψ 0 = 1 :=
by
ext
- simp only [mul_shift_apply, zero_mul, map_zero_one, MonoidHom.one_apply]
+ simp only [mul_shift_apply, MulZeroClass.zero_mul, map_zero_one, MonoidHom.one_apply]
#align add_char.mul_shift_zero AddChar.mulShift_zero
/-- An additive character is *primitive* iff all its multiplicative shifts by nonzero
@@ -421,7 +421,7 @@ theorem sum_mul_shift [DecidableEq R] [IsDomain R'] {ψ : AddChar R R'} (b : R)
by
split_ifs with h
· -- case `b = 0`
- simp only [h, mul_zero, map_zero_one, Finset.sum_const, Nat.smul_one_eq_coe]
+ simp only [h, MulZeroClass.mul_zero, map_zero_one, Finset.sum_const, Nat.smul_one_eq_coe]
rfl
· -- case `b ≠ 0`
simp_rw [mul_comm]
mathlib commit https://github.com/leanprover-community/mathlib/commit/bd9851ca476957ea4549eb19b40e7b5ade9428cc
nat_cast
/int_cast
/rat_cast
to natCast
/intCast
/ratCast
(#11486)
Now that I am defining NNRat.cast
, I want a definitive answer to this naming issue. Plenty of lemmas in mathlib already use natCast
/intCast
/ratCast
over nat_cast
/int_cast
/rat_cast
, and this matches with the general expectation that underscore-separated name parts correspond to a single declaration.
@@ -132,7 +132,7 @@ theorem zmodChar_apply {n : ℕ+} {ζ : C} (hζ : ζ ^ (n : ℕ) = 1) (a : ZMod
theorem zmodChar_apply' {n : ℕ+} {ζ : C} (hζ : ζ ^ (n : ℕ) = 1) (a : ℕ) :
zmodChar n hζ a = ζ ^ a := by
- rw [pow_eq_pow_mod a hζ, zmodChar_apply, ZMod.val_nat_cast a]
+ rw [pow_eq_pow_mod a hζ, zmodChar_apply, ZMod.val_natCast a]
#align add_char.zmod_char_apply' AddChar.zmodChar_apply'
end ZModCharDef
@@ -144,7 +144,7 @@ theorem zmod_char_isNontrivial_iff (n : ℕ+) (ψ : AddChar (ZMod n) C) :
contrapose!
rintro h₁ ⟨a, ha⟩
have ha₁ : a = a.val • (1 : ZMod ↑n) := by
- rw [nsmul_eq_mul, mul_one]; exact (ZMod.nat_cast_zmod_val a).symm
+ rw [nsmul_eq_mul, mul_one]; exact (ZMod.natCast_zmod_val a).symm
rw [ha₁, map_nsmul_pow, h₁, one_pow] at ha
exact ha rfl
#align add_char.zmod_char_is_nontrivial_iff AddChar.zmod_char_isNontrivial_iff
@@ -85,7 +85,8 @@ theorem IsNontrivial.isPrimitive {F : Type u} [Field F] {ψ : AddChar F R'} (hψ
/-- Definition for a primitive additive character on a finite ring `R` into a cyclotomic extension
of a field `R'`. It records which cyclotomic extension it is, the character, and the
fact that the character is primitive. -/
--- @[nolint has_nonempty_instance] -- Porting note: removed
+-- Porting note(#5171): this linter isn't ported yet.
+-- @[nolint has_nonempty_instance]
def PrimitiveAddChar (R : Type u) [CommRing R] (R' : Type v) [Field R'] :=
Σ n : ℕ+, Σ' char : AddChar R (CyclotomicField n R'), IsPrimitive char
#align add_char.primitive_add_char AddChar.PrimitiveAddChar
All of these changes appear to be oversights to me.
@@ -60,7 +60,7 @@ structure AddChar where
Do not use this directly. Instead use `AddChar.map_zero_one`. -/
map_zero_one' : toFun 0 = 1
- /- The function maps addition in `A` to multiplication in `M`.
+ /-- The function maps addition in `A` to multiplication in `M`.
Do not use this directly. Instead use `AddChar.map_add_mul`. -/
map_add_mul' : ∀ a b : A, toFun (a + b) = toFun a * toFun b
Also, in some cases drop unneeded Fintype
arguments.
@@ -193,12 +193,11 @@ end Additive
### Existence of a primitive additive character on a finite field
-/
-
/-- There is a primitive additive character on the finite field `F` if the characteristic
of the target is different from that of `F`.
We obtain it as the composition of the trace from `F` to `ZMod p` with a primitive
additive character on `ZMod p`, where `p` is the characteristic of `F`. -/
-noncomputable def primitiveCharFiniteField (F F' : Type*) [Field F] [Fintype F] [Field F']
+noncomputable def primitiveCharFiniteField (F F' : Type*) [Field F] [Finite F] [Field F']
(h : ringChar F' ≠ ringChar F) : PrimitiveAddChar F F' := by
let p := ringChar F
haveI hp : Fact p.Prime := ⟨CharP.char_is_prime F _⟩
Following discussion at #11313 this is an attempt to refactor Algebra/Group/AddChar.lean
such that AddChar A M
is a structure in its own right rather than a type synonym for Multiplicative A →* M
.
We also relax typeclass assumptions considerably (only assuming commutativity, etc, where it is really needed) and add some new functionality, e.g. composition with monoid morphisms on either side (MonoidHom.compAddChar
and AddChar.compAddMonoidHom
).
@@ -115,16 +115,12 @@ variable {C : Type v} [CommMonoid C]
section ZModCharDef
-open Multiplicative
--- so we can write simply `toAdd`, which we need here again
/-- We can define an additive character on `ZMod n` when we have an `n`th root of unity `ζ : C`. -/
def zmodChar (n : ℕ+) {ζ : C} (hζ : ζ ^ (n : ℕ) = 1) : AddChar (ZMod n) C where
- toFun := fun a : Multiplicative (ZMod n) => ζ ^ a.toAdd.val
- map_one' := by simp only [toAdd_one, ZMod.val_zero, pow_zero]
- map_mul' x y := by
- dsimp only
- rw [toAdd_mul, ← pow_add, ZMod.val_add (toAdd x) (toAdd y), ← pow_eq_pow_mod _ hζ]
+ toFun a := ζ ^ a.val
+ map_zero_one' := by simp only [ZMod.val_zero, pow_zero]
+ map_add_mul' x y := by simp only [ZMod.val_add, ← pow_eq_pow_mod _ hζ, ← pow_add]
#align add_char.zmod_char AddChar.zmodChar
/-- The additive character on `ZMod n` defined using `ζ` sends `a` to `ζ^a`. -/
@@ -214,7 +210,7 @@ noncomputable def primitiveCharFiniteField (F F' : Type*) [Field F] [Fintype F]
exact fun hf => Nat.Prime.ne_zero hp.1 (zero_dvd_iff.mp hf)
let ψ := primitiveZModChar pp F' (neZero_iff.mp (NeZero.of_not_dvd F' hp₂))
letI : Algebra (ZMod p) F := ZMod.algebra _ _
- let ψ' := ψ.char.comp (AddMonoidHom.toMultiplicative (Algebra.trace (ZMod p) F).toAddMonoidHom)
+ let ψ' := ψ.char.compAddMonoidHom (Algebra.trace (ZMod p) F).toAddMonoidHom
have hψ' : IsNontrivial ψ' := by
obtain ⟨a, ha⟩ := FiniteField.trace_to_zmod_nondegenerate F one_ne_zero
rw [one_mul] at ha
Following discussion at #11313 this is an attempt to refactor Algebra/Group/AddChar.lean
such that AddChar A M
is a structure in its own right rather than a type synonym for Multiplicative A →* M
.
We also relax typeclass assumptions considerably (only assuming commutativity, etc, where it is really needed) and add some new functionality, e.g. composition with monoid morphisms on either side (MonoidHom.compAddChar
and AddChar.compAddMonoidHom
).
@@ -3,8 +3,7 @@ Copyright (c) 2022 Michael Stoll. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Michael Stoll
-/
-import Mathlib.Algebra.Group.Hom.Instances
-import Mathlib.Data.Nat.Cast.Basic
+import Mathlib.Logic.Equiv.TransferInstance
#align_import number_theory.legendre_symbol.add_character from "leanprover-community/mathlib"@"0723536a0522d24fc2f159a096fb3304bef77472"
@@ -31,170 +30,252 @@ see `Mathlib.NumberTheory.LegendreSymbol.AddCharacter`.
additive character
-/
-
-universe u v
-
/-!
### Definitions related to and results on additive characters
-/
+open Multiplicative
+
section AddCharDef
-- The domain of our additive characters
-variable (A : Type u) [AddMonoid A]
+variable (A : Type*) [AddMonoid A]
-- The target
-variable (M : Type v) [CommMonoid M]
-
-/-- Define `AddChar A M` as `(Multiplicative A) →* M`.
-The definition works for an additive monoid `A` and a monoid `M`,
-but we will restrict to the case that both are commutative rings for most applications.
-The trivial additive character (sending everything to `1`) is `(1 : AddChar A M).` -/
-def AddChar : Type max u v :=
- Multiplicative A →* M
+variable (M : Type*) [Monoid M]
+
+/-- `AddChar A M` is the type of maps `A → M`, for `A` an additive monoid and `M` a multiplicative
+monoid, which intertwine addition in `A` with multiplication in `M`.
+
+We only put the typeclasses needed for the definition, although in practice we are usually
+interested in much more specific cases (e.g. when `A` is a group and `M` a commutative ring).
+ -/
+structure AddChar where
+ /-- The underlying function.
+
+ Do not use this function directly. Instead use the coercion coming from the `FunLike`
+ instance. -/
+ toFun : A → M
+ /-- The function maps `0` to `1`.
+
+ Do not use this directly. Instead use `AddChar.map_zero_one`. -/
+ map_zero_one' : toFun 0 = 1
+ /- The function maps addition in `A` to multiplication in `M`.
+
+ Do not use this directly. Instead use `AddChar.map_add_mul`. -/
+ map_add_mul' : ∀ a b : A, toFun (a + b) = toFun a * toFun b
+
#align add_char AddChar
end AddCharDef
namespace AddChar
--- Porting note(https://github.com/leanprover-community/mathlib4/issues/5020): added
-section DerivedInstances
+section Basic
+-- results which don't require commutativity or inverses
-variable (A : Type u) [AddMonoid A] (M : Type v) [CommMonoid M]
+variable {A M : Type*} [AddMonoid A] [Monoid M]
-instance : CommMonoid (AddChar A M) :=
- inferInstanceAs (CommMonoid (Multiplicative A →* M))
+/-- Define coercion to a function. -/
+instance instFunLike : FunLike (AddChar A M) A M where
+ coe := AddChar.toFun
+ coe_injective' φ ψ h := by cases φ; cases ψ; congr
-instance : Inhabited (AddChar A M) :=
- inferInstanceAs (Inhabited (Multiplicative A →* M))
+#noalign add_char.has_coe_to_fun
-end DerivedInstances
+-- Porting note(https://github.com/leanprover-community/mathlib4/issues/5229): added.
+@[ext] lemma ext (f g : AddChar A M) (h : ∀ x : A, f x = g x) : f = g :=
+ DFunLike.ext f g h
-section CoeToFun
+@[simp] lemma coe_mk (f : A → M)
+ (map_zero_one' : f 0 = 1) (map_add_mul' : ∀ a b : A, f (a + b) = f a * f b) :
+ AddChar.mk f map_zero_one' map_add_mul' = f := by
+ rfl
+
+/-- An additive character maps `0` to `1`. -/
+@[simp] lemma map_zero_one (ψ : AddChar A M) : ψ 0 = 1 := ψ.map_zero_one'
+#align add_char.map_zero_one AddChar.map_zero_one
-variable {A : Type u} [AddMonoid A] {M : Type v} [CommMonoid M]
+/-- An additive character maps sums to products. -/
+lemma map_add_mul (ψ : AddChar A M) (x y : A) : ψ (x + y) = ψ x * ψ y := ψ.map_add_mul' x y
+#align add_char.map_add_mul AddChar.map_add_mul
/-- Interpret an additive character as a monoid homomorphism. -/
-def toMonoidHom : AddChar A M → Multiplicative A →* M :=
- id
+def toMonoidHom (φ : AddChar A M) : Multiplicative A →* M where
+ toFun := φ.toFun
+ map_one' := φ.map_zero_one'
+ map_mul' := φ.map_add_mul'
#align add_char.to_monoid_hom AddChar.toMonoidHom
-open Multiplicative
-
-/-- Define coercion to a function so that it includes the move from `A` to `Multiplicative A`.
-After we have proved the API lemmas below, we don't need to worry about writing `ofAdd a`
-when we want to apply an additive character. -/
-instance instFunLike : FunLike (AddChar A M) A M :=
- inferInstanceAs (FunLike (Multiplicative A →* M) A M)
-#noalign add_char.has_coe_to_fun
+-- this instance was a bad idea and conflicted with `instFunLike` above
+#noalign add_char.monoid_hom_class
-theorem coe_to_fun_apply (ψ : AddChar A M) (a : A) : ψ a = ψ.toMonoidHom (ofAdd a) :=
+@[simp] lemma toMonoidHom_apply (ψ : AddChar A M) (a : Multiplicative A) :
+ ψ.toMonoidHom a = ψ (Multiplicative.toAdd a) :=
rfl
-#align add_char.coe_to_fun_apply AddChar.coe_to_fun_apply
+#align add_char.coe_to_fun_apply AddChar.toMonoidHom_apply
--- Porting note: added
-theorem mul_apply (ψ φ : AddChar A M) (a : A) : (ψ * φ) a = ψ a * φ a :=
- rfl
+/-- An additive character maps multiples by natural numbers to powers. -/
+lemma map_nsmul_pow (ψ : AddChar A M) (n : ℕ) (x : A) : ψ (n • x) = ψ x ^ n :=
+ ψ.toMonoidHom.map_pow x n
+#align add_char.map_nsmul_pow AddChar.map_nsmul_pow
+
+variable (A M) in
+/-- Additive characters `A → M` are the same thing as monoid homomorphisms from `Multiplicative A`
+to `M`. -/
+def toMonoidHomEquiv : AddChar A M ≃ (Multiplicative A →* M) where
+ toFun φ := φ.toMonoidHom
+ invFun f :=
+ { toFun := f.toFun
+ map_zero_one' := f.map_one'
+ map_add_mul' := f.map_mul' }
+ left_inv _ := rfl
+ right_inv _ := rfl
+
+/-- Interpret an additive character as a monoid homomorphism. -/
+def toAddMonoidHom (φ : AddChar A M) : A →+ Additive M where
+ toFun := φ.toFun
+ map_zero' := φ.map_zero_one'
+ map_add' := φ.map_add_mul'
+
+@[simp] lemma toAddMonoidHom_apply (ψ : AddChar A M) (a : A) : ψ.toAddMonoidHom a = ψ a := rfl
+
+variable (A M) in
+/-- Additive characters `A → M` are the same thing as additive homomorphisms from `A` to
+`Additive M`. -/
+def toAddMonoidHomEquiv : AddChar A M ≃ (A →+ Additive M) where
+ toFun φ := φ.toAddMonoidHom
+ invFun f :=
+ { toFun := f.toFun
+ map_zero_one' := f.map_zero'
+ map_add_mul' := f.map_add' }
+ left_inv _ := rfl
+ right_inv _ := rfl
+
+/-- The trivial additive character (sending everything to `1`) is `(1 : AddChar A M).` -/
+instance instOne : One (AddChar A M) := (toMonoidHomEquiv A M).one
-- Porting note: added
-@[simp]
-theorem one_apply (a : A) : (1 : AddChar A M) a = 1 := rfl
+@[simp] lemma one_apply (a : A) : (1 : AddChar A M) a = 1 := rfl
--- this instance was a bad idea and conflicted with `instFunLike` above
-#noalign add_char.monoid_hom_class
+instance instInhabited : Inhabited (AddChar A M) := ⟨1⟩
--- Porting note(https://github.com/leanprover-community/mathlib4/issues/5229): added.
-@[ext]
-theorem ext (f g : AddChar A M) (h : ∀ x : A, f x = g x) : f = g :=
- MonoidHom.ext h
+/-- Composing a `MonoidHom` with an `AddChar` yields another `AddChar`. -/
+def _root_.MonoidHom.compAddChar {N : Type*} [Monoid N] (f : M →* N) (φ : AddChar A M) :
+ AddChar A N :=
+ (toMonoidHomEquiv A N).symm (f.comp φ.toMonoidHom)
-/-- An additive character maps `0` to `1`. -/
@[simp]
-theorem map_zero_one (ψ : AddChar A M) : ψ 0 = 1 := by rw [coe_to_fun_apply, ofAdd_zero, map_one]
-#align add_char.map_zero_one AddChar.map_zero_one
+lemma _root_.MonoidHom.coe_compAddChar {N : Type*} [Monoid N] (f : M →* N) (φ : AddChar A M) :
+ f.compAddChar φ = f ∘ φ :=
+ rfl
-/-- An additive character maps sums to products. -/
-@[simp]
-theorem map_add_mul (ψ : AddChar A M) (x y : A) : ψ (x + y) = ψ x * ψ y := by
- rw [coe_to_fun_apply, coe_to_fun_apply _ x, coe_to_fun_apply _ y, ofAdd_add, map_mul]
-#align add_char.map_add_mul AddChar.map_add_mul
+/-- Composing an `AddChar` with an `AddMonoidHom` yields another `AddChar`. -/
+def compAddMonoidHom {B : Type*} [AddMonoid B] (φ : AddChar B M) (f : A →+ B) : AddChar A M :=
+ (toAddMonoidHomEquiv A M).symm (φ.toAddMonoidHom.comp f)
-/-- An additive character maps multiples by natural numbers to powers. -/
-@[simp]
-theorem map_nsmul_pow (ψ : AddChar A M) (n : ℕ) (x : A) : ψ (n • x) = ψ x ^ n := by
- rw [coe_to_fun_apply, coe_to_fun_apply _ x, ofAdd_nsmul, map_pow]
-#align add_char.map_nsmul_pow AddChar.map_nsmul_pow
+@[simp] lemma coe_compAddMonoidHom {B : Type*} [AddMonoid B] (φ : AddChar B M) (f : A →+ B) :
+ φ.compAddMonoidHom f = φ ∘ f := rfl
-end CoeToFun
+/-- An additive character is *nontrivial* if it takes a value `≠ 1`. -/
+def IsNontrivial (ψ : AddChar A M) : Prop := ∃ a : A, ψ a ≠ 1
+#align add_char.is_nontrivial AddChar.IsNontrivial
-section GroupStructure
+/-- An additive character is nontrivial iff it is not the trivial character. -/
+lemma isNontrivial_iff_ne_trivial (ψ : AddChar A M) : IsNontrivial ψ ↔ ψ ≠ 1 :=
+ not_forall.symm.trans (DFunLike.ext_iff (f := ψ) (g := 1)).symm.not
-open Multiplicative
+#align add_char.is_nontrivial_iff_ne_trivial AddChar.isNontrivial_iff_ne_trivial
-variable {A : Type u} [AddCommGroup A] {M : Type v} [CommMonoid M]
+end Basic
-/-- An additive character on a commutative additive group has an inverse.
+section toCommMonoid
-Note that this is a different inverse to the one provided by `MonoidHom.inv`,
-as it acts on the domain instead of the codomain. -/
-instance hasInv : Inv (AddChar A M) :=
- ⟨fun ψ => ψ.comp invMonoidHom⟩
-#align add_char.has_inv AddChar.hasInv
+variable {A M : Type*} [AddMonoid A] [CommMonoid M]
-theorem inv_apply (ψ : AddChar A M) (x : A) : ψ⁻¹ x = ψ (-x) :=
- rfl
+/-- When `M` is commutative, `AddChar A M` is a commutative monoid. -/
+instance instCommMonoid : CommMonoid (AddChar A M) := (toMonoidHomEquiv A M).commMonoid
+
+-- Porting note: added
+@[simp] lemma mul_apply (ψ φ : AddChar A M) (a : A) : (ψ * φ) a = ψ a * φ a := rfl
+
+@[simp] lemma pow_apply (ψ : AddChar A M) (n : ℕ) (a : A) : (ψ ^ n) a = (ψ a) ^ n := rfl
+
+variable (A M)
+
+/-- The natural equivalence to `(Multiplicative A →* M)` is a monoid isomorphism. -/
+def toMonoidHomMulEquiv : AddChar A M ≃* (Multiplicative A →* M) :=
+ { toMonoidHomEquiv A M with map_mul' := fun φ ψ ↦ by rfl }
+
+/-- Additive characters `A → M` are the same thing as additive homomorphisms from `A` to
+`Additive M`. -/
+def toAddMonoidAddEquiv : Additive (AddChar A M) ≃+ (A →+ Additive M) :=
+ { toAddMonoidHomEquiv A M with map_add' := fun φ ψ ↦ by rfl }
+
+end toCommMonoid
+
+/-!
+## Additive characters of additive abelian groups
+-/
+section fromAddCommGroup
+
+variable {A M : Type*} [AddCommGroup A] [CommMonoid M]
+
+/-- The additive characters on a commutative additive group form a commutative group.
+
+Note that the inverse is defined using negation on the domain; we do not assume `M` has an
+inversion operation for the definition (but see `AddChar.map_neg_inv` below). -/
+instance instCommGroup : CommGroup (AddChar A M) :=
+ { instCommMonoid with
+ inv := fun ψ ↦ ψ.compAddMonoidHom negAddMonoidHom
+ mul_left_inv := fun ψ ↦ by ext1 x; simp [negAddMonoidHom, ← map_add_mul]}
+#align add_char.comm_group AddChar.instCommGroup
+#align add_char.has_inv AddChar.instCommGroup
+
+@[simp] lemma inv_apply (ψ : AddChar A M) (x : A) : ψ⁻¹ x = ψ (-x) := rfl
#align add_char.inv_apply AddChar.inv_apply
-/-- An additive character maps multiples by integers to powers. -/
-@[simp]
-theorem map_zsmul_zpow {M : Type v} [CommGroup M] (ψ : AddChar A M) (n : ℤ) (x : A) :
- ψ (n • x) = ψ x ^ n := by rw [coe_to_fun_apply, coe_to_fun_apply _ x, ofAdd_zsmul, map_zpow]
-#align add_char.map_zsmul_zpow AddChar.map_zsmul_zpow
+end fromAddCommGroup
-/-- The additive characters on a commutative additive group form a commutative group. -/
-instance commGroup : CommGroup (AddChar A M) :=
- { MonoidHom.commMonoid with
- inv := Inv.inv
- mul_left_inv := fun ψ => by
- ext x
- rw [AddChar.mul_apply, AddChar.one_apply, inv_apply, ← map_add_mul, add_left_neg,
- map_zero_one] }
-#align add_char.comm_group AddChar.commGroup
+section fromAddGrouptoDivisionMonoid
-end GroupStructure
+variable {A M : Type*} [AddGroup A] [DivisionMonoid M]
-section nontrivial
+/-- An additive character maps negatives to inverses (when defined) -/
+lemma map_neg_inv (ψ : AddChar A M) (a : A) : ψ (-a) = (ψ a)⁻¹ := by
+ apply eq_inv_of_mul_eq_one_left
+ simp only [← map_add_mul, add_left_neg, map_zero_one]
-variable {A : Type u} [AddMonoid A] {M : Type v} [CommMonoid M]
+/-- An additive character maps integer scalar multiples to integer powers. -/
+lemma map_zsmul_zpow (ψ : AddChar A M) (n : ℤ) (a : A) : ψ (n • a) = (ψ a) ^ n :=
+ ψ.toMonoidHom.map_zpow a n
+#align add_char.map_zsmul_zpow AddChar.map_zsmul_zpow
-/-- An additive character is *nontrivial* if it takes a value `≠ 1`. -/
-def IsNontrivial (ψ : AddChar A M) : Prop :=
- ∃ a : A, ψ a ≠ 1
-#align add_char.is_nontrivial AddChar.IsNontrivial
+end fromAddGrouptoDivisionMonoid
-/-- An additive character is nontrivial iff it is not the trivial character. -/
-theorem isNontrivial_iff_ne_trivial (ψ : AddChar A M) : IsNontrivial ψ ↔ ψ ≠ 1 := by
- refine' not_forall.symm.trans (Iff.not _)
- rw [DFunLike.ext_iff]
- rfl
-#align add_char.is_nontrivial_iff_ne_trivial AddChar.isNontrivial_iff_ne_trivial
+section fromAddGrouptoDivisionCommMonoid
+
+variable {A M : Type*} [AddCommGroup A] [DivisionCommMonoid M]
+
+lemma inv_apply' (ψ : AddChar A M) (x : A) : ψ⁻¹ x = (ψ x)⁻¹ := by rw [inv_apply, map_neg_inv]
-end nontrivial
+end fromAddGrouptoDivisionCommMonoid
+/-!
+## Additive characters of rings
+-/
section Ring
-- The domain and target of our additive characters. Now we restrict to a ring in the domain.
-variable {R : Type u} [CommRing R] {M : Type v} [CommMonoid M]
+variable {R M : Type*} [Ring R] [CommMonoid M]
/-- Define the multiplicative shift of an additive character.
This satisfies `mulShift ψ a x = ψ (a * x)`. -/
def mulShift (ψ : AddChar R M) (r : R) : AddChar R M :=
- ψ.comp (AddMonoidHom.toMultiplicative (AddMonoidHom.mulLeft r))
+ ψ.compAddMonoidHom (AddMonoidHom.mulLeft r)
#align add_char.mul_shift AddChar.mulShift
-@[simp]
-theorem mulShift_apply {ψ : AddChar R M} {r : R} {x : R} : mulShift ψ r x = ψ (r * x) :=
+@[simp] lemma mulShift_apply {ψ : AddChar R M} {r : R} {x : R} : mulShift ψ r x = ψ (r * x) :=
rfl
#align add_char.mul_shift_apply AddChar.mulShift_apply
@@ -212,7 +293,7 @@ theorem mulShift_spec' (ψ : AddChar R M) (n : ℕ) (x : R) : mulShift ψ n x =
/-- If `n` is a natural number, then `ψ ^ n = mulShift ψ n`. -/
theorem pow_mulShift (ψ : AddChar R M) (n : ℕ) : ψ ^ n = mulShift ψ n := by
ext x
- rw [show (ψ ^ n) x = ψ x ^ n from rfl, ← mulShift_spec']
+ rw [pow_apply, ← mulShift_spec']
#align add_char.pow_mul_shift AddChar.pow_mulShift
/-- The product of `mulShift ψ r` and `mulShift ψ s` is `mulShift ψ (r + s)`. -/
@@ -225,8 +306,7 @@ theorem mulShift_mul (ψ : AddChar R M) (r s : R) :
/-- `mulShift ψ 0` is the trivial character. -/
@[simp]
theorem mulShift_zero (ψ : AddChar R M) : mulShift ψ 0 = 1 := by
- ext
- rw [mulShift_apply, zero_mul, map_zero_one]; norm_cast
+ ext; rw [mulShift_apply, zero_mul, map_zero_one, one_apply]
#align add_char.mul_shift_zero AddChar.mulShift_zero
end Ring
Currently the definition of additive characters (from an additive to a multiplicative monoid) is hidden away in
NumberTheory/LegendreSymbol
. These constructions seem to be getting used more widely, e.g. in Yaël's LeanAPAP project; so this PR carves off the parts of NumberTheory/LegendreSymbol/AddCharacter
which don't depend on cyclotomic field arithmetic and moves them to Algebra/Group
.
@@ -5,25 +5,20 @@ Authors: Michael Stoll
-/
import Mathlib.NumberTheory.Cyclotomic.PrimitiveRoots
import Mathlib.FieldTheory.Finite.Trace
+import Mathlib.Algebra.Group.AddChar
#align_import number_theory.legendre_symbol.add_character from "leanprover-community/mathlib"@"0723536a0522d24fc2f159a096fb3304bef77472"
/-!
# Additive characters of finite rings and fields
-Let `R` be a finite commutative ring. An *additive character* of `R` with values
-in another commutative ring `R'` is simply a morphism from the additive group
-of `R` into the multiplicative monoid of `R'`.
-
-The additive characters on `R` with values in `R'` form a commutative group.
-
-We use the namespace `AddChar`.
+This file collects some results on additive characters whose domain is (the additive group of)
+a finite ring or field.
## Main definitions and results
-We define `mulShift ψ a`, where `ψ : AddChar R R'` and `a : R`, to be the
-character defined by `x ↦ ψ (a * x)`. An additive character `ψ` is *primitive*
-if `mulShift ψ a` is trivial only when `a = 0`.
+We define an additive character `ψ` to be *primitive* if `mulShift ψ a` is trivial only when
+`a = 0`.
We show that when `ψ` is primitive, then the map `a ↦ mulShift ψ a` is injective
(`AddChar.to_mulShift_inj_of_isPrimitive`) and that `ψ` is primitive when `R` is a field
@@ -44,204 +39,13 @@ additive character
universe u v
-/-!
-### Definitions related to and results on additive characters
--/
-
-
-section AddCharDef
-
--- The domain of our additive characters
-variable (R : Type u) [AddMonoid R]
-
--- The target
-variable (R' : Type v) [CommMonoid R']
-
-/-- Define `AddChar R R'` as `(Multiplicative R) →* R'`.
-The definition works for an additive monoid `R` and a monoid `R'`,
-but we will restrict to the case that both are commutative rings below.
-We assume right away that `R'` is commutative, so that `AddChar R R'` carries
-a structure of commutative monoid.
-The trivial additive character (sending everything to `1`) is `(1 : AddChar R R').` -/
-def AddChar : Type max u v :=
- Multiplicative R →* R'
-#align add_char AddChar
-
-end AddCharDef
-
namespace AddChar
--- Porting note(https://github.com/leanprover-community/mathlib4/issues/5020): added
-section DerivedInstances
-
-variable (R : Type u) [AddMonoid R] (R' : Type v) [CommMonoid R']
-
-instance : CommMonoid (AddChar R R') :=
- inferInstanceAs (CommMonoid (Multiplicative R →* R'))
-
-instance : Inhabited (AddChar R R') :=
- inferInstanceAs (Inhabited (Multiplicative R →* R'))
-
-end DerivedInstances
-
-section CoeToFun
-
-variable {R : Type u} [AddMonoid R] {R' : Type v} [CommMonoid R']
-
-/-- Interpret an additive character as a monoid homomorphism. -/
-def toMonoidHom : AddChar R R' → Multiplicative R →* R' :=
- id
-#align add_char.to_monoid_hom AddChar.toMonoidHom
-
-open Multiplicative
-
-/-- Define coercion to a function so that it includes the move from `R` to `Multiplicative R`.
-After we have proved the API lemmas below, we don't need to worry about writing `ofAdd a`
-when we want to apply an additive character. -/
-instance instFunLike : FunLike (AddChar R R') R R' :=
- inferInstanceAs (FunLike (Multiplicative R →* R') R R')
-#noalign add_char.has_coe_to_fun
-
-theorem coe_to_fun_apply (ψ : AddChar R R') (a : R) : ψ a = ψ.toMonoidHom (ofAdd a) :=
- rfl
-#align add_char.coe_to_fun_apply AddChar.coe_to_fun_apply
-
--- Porting note: added
-theorem mul_apply (ψ φ : AddChar R R') (a : R) : (ψ * φ) a = ψ a * φ a :=
- rfl
-
--- Porting note: added
-@[simp]
-theorem one_apply (a : R) : (1 : AddChar R R') a = 1 := rfl
-
--- this instance was a bad idea and conflicted with `instFunLike` above
-#noalign add_char.monoid_hom_class
-
--- Porting note(https://github.com/leanprover-community/mathlib4/issues/5229): added.
-@[ext]
-theorem ext (f g : AddChar R R') (h : ∀ x : R, f x = g x) : f = g :=
- MonoidHom.ext h
-
-/-- An additive character maps `0` to `1`. -/
-@[simp]
-theorem map_zero_one (ψ : AddChar R R') : ψ 0 = 1 := by rw [coe_to_fun_apply, ofAdd_zero, map_one]
-#align add_char.map_zero_one AddChar.map_zero_one
-
-/-- An additive character maps sums to products. -/
-@[simp]
-theorem map_add_mul (ψ : AddChar R R') (x y : R) : ψ (x + y) = ψ x * ψ y := by
- rw [coe_to_fun_apply, coe_to_fun_apply _ x, coe_to_fun_apply _ y, ofAdd_add, map_mul]
-#align add_char.map_add_mul AddChar.map_add_mul
-
-/-- An additive character maps multiples by natural numbers to powers. -/
-@[simp]
-theorem map_nsmul_pow (ψ : AddChar R R') (n : ℕ) (x : R) : ψ (n • x) = ψ x ^ n := by
- rw [coe_to_fun_apply, coe_to_fun_apply _ x, ofAdd_nsmul, map_pow]
-#align add_char.map_nsmul_pow AddChar.map_nsmul_pow
-
-end CoeToFun
-
-section GroupStructure
-
-open Multiplicative
-
-variable {R : Type u} [AddCommGroup R] {R' : Type v} [CommMonoid R']
-
-/-- An additive character on a commutative additive group has an inverse.
-
-Note that this is a different inverse to the one provided by `MonoidHom.inv`,
-as it acts on the domain instead of the codomain. -/
-instance hasInv : Inv (AddChar R R') :=
- ⟨fun ψ => ψ.comp invMonoidHom⟩
-#align add_char.has_inv AddChar.hasInv
-
-theorem inv_apply (ψ : AddChar R R') (x : R) : ψ⁻¹ x = ψ (-x) :=
- rfl
-#align add_char.inv_apply AddChar.inv_apply
-
-/-- An additive character maps multiples by integers to powers. -/
-@[simp]
-theorem map_zsmul_zpow {R' : Type v} [CommGroup R'] (ψ : AddChar R R') (n : ℤ) (x : R) :
- ψ (n • x) = ψ x ^ n := by rw [coe_to_fun_apply, coe_to_fun_apply _ x, ofAdd_zsmul, map_zpow]
-#align add_char.map_zsmul_zpow AddChar.map_zsmul_zpow
-
-/-- The additive characters on a commutative additive group form a commutative group. -/
-instance commGroup : CommGroup (AddChar R R') :=
- { MonoidHom.commMonoid with
- inv := Inv.inv
- mul_left_inv := fun ψ => by
- ext x
- rw [AddChar.mul_apply, AddChar.one_apply, inv_apply, ← map_add_mul, add_left_neg,
- map_zero_one] }
-#align add_char.comm_group AddChar.commGroup
-
-end GroupStructure
-
-section nontrivial
-
-variable {R : Type u} [AddMonoid R] {R' : Type v} [CommMonoid R']
-
-/-- An additive character is *nontrivial* if it takes a value `≠ 1`. -/
-def IsNontrivial (ψ : AddChar R R') : Prop :=
- ∃ a : R, ψ a ≠ 1
-#align add_char.is_nontrivial AddChar.IsNontrivial
-
-/-- An additive character is nontrivial iff it is not the trivial character. -/
-theorem isNontrivial_iff_ne_trivial (ψ : AddChar R R') : IsNontrivial ψ ↔ ψ ≠ 1 := by
- refine' not_forall.symm.trans (Iff.not _)
- rw [DFunLike.ext_iff]
- rfl
-#align add_char.is_nontrivial_iff_ne_trivial AddChar.isNontrivial_iff_ne_trivial
-
-end nontrivial
-
section Additive
-- The domain and target of our additive characters. Now we restrict to a ring in the domain.
variable {R : Type u} [CommRing R] {R' : Type v} [CommMonoid R']
-/-- Define the multiplicative shift of an additive character.
-This satisfies `mulShift ψ a x = ψ (a * x)`. -/
-def mulShift (ψ : AddChar R R') (a : R) : AddChar R R' :=
- ψ.comp (AddMonoidHom.toMultiplicative (AddMonoidHom.mulLeft a))
-#align add_char.mul_shift AddChar.mulShift
-
-@[simp]
-theorem mulShift_apply {ψ : AddChar R R'} {a : R} {x : R} : mulShift ψ a x = ψ (a * x) :=
- rfl
-#align add_char.mul_shift_apply AddChar.mulShift_apply
-
-/-- `ψ⁻¹ = mulShift ψ (-1))`. -/
-theorem inv_mulShift (ψ : AddChar R R') : ψ⁻¹ = mulShift ψ (-1) := by
- ext
- rw [inv_apply, mulShift_apply, neg_mul, one_mul]
-#align add_char.inv_mul_shift AddChar.inv_mulShift
-
-/-- If `n` is a natural number, then `mulShift ψ n x = (ψ x) ^ n`. -/
-theorem mulShift_spec' (ψ : AddChar R R') (n : ℕ) (x : R) : mulShift ψ n x = ψ x ^ n := by
- rw [mulShift_apply, ← nsmul_eq_mul, map_nsmul_pow]
-#align add_char.mul_shift_spec' AddChar.mulShift_spec'
-
-/-- If `n` is a natural number, then `ψ ^ n = mulShift ψ n`. -/
-theorem pow_mulShift (ψ : AddChar R R') (n : ℕ) : ψ ^ n = mulShift ψ n := by
- ext x
- rw [show (ψ ^ n) x = ψ x ^ n from rfl, ← mulShift_spec']
-#align add_char.pow_mul_shift AddChar.pow_mulShift
-
-/-- The product of `mulShift ψ a` and `mulShift ψ b` is `mulShift ψ (a + b)`. -/
-theorem mulShift_mul (ψ : AddChar R R') (a b : R) :
- mulShift ψ a * mulShift ψ b = mulShift ψ (a + b) := by
- ext
- rw [mulShift_apply, right_distrib, map_add_mul]; norm_cast
-#align add_char.mul_shift_mul AddChar.mulShift_mul
-
-/-- `mulShift ψ 0` is the trivial character. -/
-@[simp]
-theorem mulShift_zero (ψ : AddChar R R') : mulShift ψ 0 = 1 := by
- ext
- rw [mulShift_apply, zero_mul, map_zero_one]; norm_cast
-#align add_char.mul_shift_zero AddChar.mulShift_zero
-
/-- An additive character is *primitive* iff all its multiplicative shifts by nonzero
elements are nontrivial. -/
def IsPrimitive (ψ : AddChar R R') : Prop :=
Currently the definition of additive characters (from an additive to a multiplicative monoid) is hidden away in
NumberTheory/LegendreSymbol
. These constructions seem to be getting used more widely, e.g. in Yaël's LeanAPAP project; so this PR carves off the parts of NumberTheory/LegendreSymbol/AddCharacter
which don't depend on cyclotomic field arithmetic and moves them to Algebra/Group
.
Homogenises porting notes via capitalisation and addition of whitespace.
It makes the following changes:
@@ -106,11 +106,11 @@ theorem coe_to_fun_apply (ψ : AddChar R R') (a : R) : ψ a = ψ.toMonoidHom (of
rfl
#align add_char.coe_to_fun_apply AddChar.coe_to_fun_apply
--- porting note: added
+-- Porting note: added
theorem mul_apply (ψ φ : AddChar R R') (a : R) : (ψ * φ) a = ψ a * φ a :=
rfl
--- porting note: added
+-- Porting note: added
@[simp]
theorem one_apply (a : R) : (1 : AddChar R R') a = 1 := rfl
This is an analogue of #11012. It weakens the type class assumptions in various definitions and statements about additive characters. Prompted by this message on Zulip.
@@ -177,10 +177,9 @@ instance commGroup : CommGroup (AddChar R R') :=
end GroupStructure
-section Additive
+section nontrivial
--- The domain and target of our additive characters. Now we restrict to rings on both sides.
-variable {R : Type u} [CommRing R] {R' : Type v} [CommRing R']
+variable {R : Type u} [AddMonoid R] {R' : Type v} [CommMonoid R']
/-- An additive character is *nontrivial* if it takes a value `≠ 1`. -/
def IsNontrivial (ψ : AddChar R R') : Prop :=
@@ -194,6 +193,13 @@ theorem isNontrivial_iff_ne_trivial (ψ : AddChar R R') : IsNontrivial ψ ↔ ψ
rfl
#align add_char.is_nontrivial_iff_ne_trivial AddChar.isNontrivial_iff_ne_trivial
+end nontrivial
+
+section Additive
+
+-- The domain and target of our additive characters. Now we restrict to a ring in the domain.
+variable {R : Type u} [CommRing R] {R' : Type v} [CommMonoid R']
+
/-- Define the multiplicative shift of an additive character.
This satisfies `mulShift ψ a x = ψ (a * x)`. -/
def mulShift (ψ : AddChar R R') (a : R) : AddChar R R' :=
@@ -271,7 +277,7 @@ theorem IsNontrivial.isPrimitive {F : Type u} [Field F] {ψ : AddChar F R'} (hψ
-- https://leanprover.zulipchat.com/#narrow/stream/287929-mathlib4/topic/mysterious.20finsupp.20related.20timeout/near/365719262 and
-- https://leanprover.zulipchat.com/#narrow/stream/287929-mathlib4/topic/mysterious.20finsupp.20related.20timeout
-- In Lean4, `set_option genInjectivity false in` may solve this issue.
--- can't prove that they always exist
+-- can't prove that they always exist (referring to providing an `Inhabited` instance)
/-- Definition for a primitive additive character on a finite ring `R` into a cyclotomic extension
of a field `R'`. It records which cyclotomic extension it is, the character, and the
fact that the character is primitive. -/
@@ -290,7 +296,7 @@ noncomputable def PrimitiveAddChar.char {R : Type u} [CommRing R] {R' : Type v}
∀ χ : PrimitiveAddChar R R', AddChar R (CyclotomicField χ.n R') := fun χ => χ.2.1
#align add_char.primitive_add_char.char AddChar.PrimitiveAddChar.char
-/-- The third projection from `PrimitiveAddChar`, showing that `χ.2` is primitive. -/
+/-- The third projection from `PrimitiveAddChar`, showing that `χ.char` is primitive. -/
theorem PrimitiveAddChar.prim {R : Type u} [CommRing R] {R' : Type v} [Field R'] :
∀ χ : PrimitiveAddChar R R', IsPrimitive χ.char := fun χ => χ.2.2
#align add_char.primitive_add_char.prim AddChar.PrimitiveAddChar.prim
@@ -299,14 +305,15 @@ theorem PrimitiveAddChar.prim {R : Type u} [CommRing R] {R' : Type v} [Field R']
### Additive characters on `ZMod n`
-/
+section ZModChar
-variable {C : Type v} [CommRing C]
+variable {C : Type v} [CommMonoid C]
section ZModCharDef
open Multiplicative
-
-- so we can write simply `toAdd`, which we need here again
+
/-- We can define an additive character on `ZMod n` when we have an `n`th root of unity `ζ : C`. -/
def zmodChar (n : ℕ+) {ζ : C} (hζ : ζ ^ (n : ℕ) = 1) : AddChar (ZMod n) C where
toFun := fun a : Multiplicative (ZMod n) => ζ ^ a.toAdd.val
@@ -378,6 +385,10 @@ noncomputable def primitiveZModChar (n : ℕ+) (F' : Type v) [Field F'] (h : (n
zmodChar_primitive_of_primitive_root n (IsCyclotomicExtension.zeta_spec n F' _)⟩
#align add_char.primitive_zmod_char AddChar.primitiveZModChar
+end ZModChar
+
+end Additive
+
/-!
### Existence of a primitive additive character on a finite field
-/
@@ -412,9 +423,11 @@ noncomputable def primitiveCharFiniteField (F F' : Type*) [Field F] [Fintype F]
-/
+section sum
+
open scoped BigOperators
-variable [Fintype R]
+variable {R : Type*} [AddGroup R] [Fintype R] {R' : Type*} [CommRing R']
/-- The sum over the values of a nontrivial additive character vanishes if the target ring
is a domain. -/
@@ -438,9 +451,13 @@ theorem sum_eq_card_of_is_trivial {ψ : AddChar R R'} (hψ : ¬IsNontrivial ψ)
rfl
#align add_char.sum_eq_card_of_is_trivial AddChar.sum_eq_card_of_is_trivial
+end sum
+
+open scoped BigOperators in
/-- The sum over the values of `mulShift ψ b` for `ψ` primitive is zero when `b ≠ 0`
and `#R` otherwise. -/
-theorem sum_mulShift [DecidableEq R] [IsDomain R'] {ψ : AddChar R R'} (b : R)
+theorem sum_mulShift {R : Type*} [CommRing R] [Fintype R] [DecidableEq R]
+ {R' : Type*} [CommRing R'] [IsDomain R'] {ψ : AddChar R R'} (b : R)
(hψ : IsPrimitive ψ) : ∑ x : R, ψ (x * b) = if b = 0 then Fintype.card R else 0 := by
split_ifs with h
· -- case `b = 0`
@@ -451,6 +468,4 @@ theorem sum_mulShift [DecidableEq R] [IsDomain R'] {ψ : AddChar R R'} (b : R)
exact mod_cast sum_eq_zero_of_isNontrivial (hψ b h)
#align add_char.sum_mul_shift AddChar.sum_mulShift
-end Additive
-
end AddChar
FunLike
(#9833)
This follows up from #9785, which renamed FunLike
to DFunLike
, by introducing a new abbreviation FunLike F α β := DFunLike F α (fun _ => β)
, to make the non-dependent use of FunLike
easier.
I searched for the pattern DFunLike.*fun
and DFunLike.*λ
in all files to replace expressions of the form DFunLike F α (fun _ => β)
with FunLike F α β
. I did this everywhere except for extends
clauses for two reasons: it would conflict with #8386, and more importantly extends
must directly refer to a structure with no unfolding of def
s or abbrev
s.
@@ -98,8 +98,8 @@ open Multiplicative
/-- Define coercion to a function so that it includes the move from `R` to `Multiplicative R`.
After we have proved the API lemmas below, we don't need to worry about writing `ofAdd a`
when we want to apply an additive character. -/
-instance instDFunLike : DFunLike (AddChar R R') R fun _ ↦ R' :=
- inferInstanceAs (DFunLike (Multiplicative R →* R') R fun _ ↦ R')
+instance instFunLike : FunLike (AddChar R R') R R' :=
+ inferInstanceAs (FunLike (Multiplicative R →* R') R R')
#noalign add_char.has_coe_to_fun
theorem coe_to_fun_apply (ψ : AddChar R R') (a : R) : ψ a = ψ.toMonoidHom (ofAdd a) :=
@@ -114,7 +114,7 @@ theorem mul_apply (ψ φ : AddChar R R') (a : R) : (ψ * φ) a = ψ a * φ a :=
@[simp]
theorem one_apply (a : R) : (1 : AddChar R R') a = 1 := rfl
--- this instance was a bad idea and conflicted with `instDFunLike` above
+-- this instance was a bad idea and conflicted with `instFunLike` above
#noalign add_char.monoid_hom_class
-- Porting note(https://github.com/leanprover-community/mathlib4/issues/5229): added.
FunLike
to DFunLike
(#9785)
This prepares for the introduction of a non-dependent synonym of FunLike, which helps a lot with keeping #8386 readable.
This is entirely search-and-replace in 680197f combined with manual fixes in 4145626, e900597 and b8428f8. The commands that generated this change:
sed -i 's/\bFunLike\b/DFunLike/g' {Archive,Counterexamples,Mathlib,test}/**/*.lean
sed -i 's/\btoFunLike\b/toDFunLike/g' {Archive,Counterexamples,Mathlib,test}/**/*.lean
sed -i 's/import Mathlib.Data.DFunLike/import Mathlib.Data.FunLike/g' {Archive,Counterexamples,Mathlib,test}/**/*.lean
sed -i 's/\bHom_FunLike\b/Hom_DFunLike/g' {Archive,Counterexamples,Mathlib,test}/**/*.lean
sed -i 's/\binstFunLike\b/instDFunLike/g' {Archive,Counterexamples,Mathlib,test}/**/*.lean
sed -i 's/\bfunLike\b/instDFunLike/g' {Archive,Counterexamples,Mathlib,test}/**/*.lean
sed -i 's/\btoo many metavariables to apply `fun_like.has_coe_to_fun`/too many metavariables to apply `DFunLike.hasCoeToFun`/g' {Archive,Counterexamples,Mathlib,test}/**/*.lean
Co-authored-by: Anne Baanen <Vierkantor@users.noreply.github.com>
@@ -98,8 +98,8 @@ open Multiplicative
/-- Define coercion to a function so that it includes the move from `R` to `Multiplicative R`.
After we have proved the API lemmas below, we don't need to worry about writing `ofAdd a`
when we want to apply an additive character. -/
-instance instFunLike : FunLike (AddChar R R') R fun _ ↦ R' :=
- inferInstanceAs (FunLike (Multiplicative R →* R') R fun _ ↦ R')
+instance instDFunLike : DFunLike (AddChar R R') R fun _ ↦ R' :=
+ inferInstanceAs (DFunLike (Multiplicative R →* R') R fun _ ↦ R')
#noalign add_char.has_coe_to_fun
theorem coe_to_fun_apply (ψ : AddChar R R') (a : R) : ψ a = ψ.toMonoidHom (ofAdd a) :=
@@ -114,7 +114,7 @@ theorem mul_apply (ψ φ : AddChar R R') (a : R) : (ψ * φ) a = ψ a * φ a :=
@[simp]
theorem one_apply (a : R) : (1 : AddChar R R') a = 1 := rfl
--- this instance was a bad idea and conflicted with `instFunLike` above
+-- this instance was a bad idea and conflicted with `instDFunLike` above
#noalign add_char.monoid_hom_class
-- Porting note(https://github.com/leanprover-community/mathlib4/issues/5229): added.
@@ -190,7 +190,7 @@ def IsNontrivial (ψ : AddChar R R') : Prop :=
/-- An additive character is nontrivial iff it is not the trivial character. -/
theorem isNontrivial_iff_ne_trivial (ψ : AddChar R R') : IsNontrivial ψ ↔ ψ ≠ 1 := by
refine' not_forall.symm.trans (Iff.not _)
- rw [FunLike.ext_iff]
+ rw [DFunLike.ext_iff]
rfl
#align add_char.is_nontrivial_iff_ne_trivial AddChar.isNontrivial_iff_ne_trivial
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.
@@ -95,16 +95,12 @@ def toMonoidHom : AddChar R R' → Multiplicative R →* R' :=
open Multiplicative
--- Porting note: added.
-@[coe]
-def toFun (ψ : AddChar R R') (x : R) : R' := ψ.toMonoidHom (ofAdd x)
-
/-- Define coercion to a function so that it includes the move from `R` to `Multiplicative R`.
After we have proved the API lemmas below, we don't need to worry about writing `ofAdd a`
when we want to apply an additive character. -/
-instance hasCoeToFun : CoeFun (AddChar R R') fun _ => R → R' where
- coe := toFun
-#align add_char.has_coe_to_fun AddChar.hasCoeToFun
+instance instFunLike : FunLike (AddChar R R') R fun _ ↦ R' :=
+ inferInstanceAs (FunLike (Multiplicative R →* R') R fun _ ↦ R')
+#noalign add_char.has_coe_to_fun
theorem coe_to_fun_apply (ψ : AddChar R R') (a : R) : ψ a = ψ.toMonoidHom (ofAdd a) :=
rfl
@@ -118,9 +114,8 @@ theorem mul_apply (ψ φ : AddChar R R') (a : R) : (ψ * φ) a = ψ a * φ a :=
@[simp]
theorem one_apply (a : R) : (1 : AddChar R R') a = 1 := rfl
-instance monoidHomClass : MonoidHomClass (AddChar R R') (Multiplicative R) R' :=
- MonoidHom.monoidHomClass
-#align add_char.monoid_hom_class AddChar.monoidHomClass
+-- this instance was a bad idea and conflicted with `instFunLike` above
+#noalign add_char.monoid_hom_class
-- Porting note(https://github.com/leanprover-community/mathlib4/issues/5229): added.
@[ext]
exact_mod_cast
tactic with mod_cast
elaborator where possible (#8404)
We still have the exact_mod_cast
tactic, used in a few places, which somehow (?) works a little bit harder to prevent the expected type influencing the elaboration of the term. I would like to get to the bottom of this, and it will be easier once the only usages of exact_mod_cast
are the ones that don't work using the term elaborator by itself.
Co-authored-by: Scott Morrison <scott.morrison@gmail.com>
@@ -453,7 +453,7 @@ theorem sum_mulShift [DecidableEq R] [IsDomain R'] {ψ : AddChar R R'} (b : R)
rfl
· -- case `b ≠ 0`
simp_rw [mul_comm]
- exact_mod_cast sum_eq_zero_of_isNontrivial (hψ b h)
+ exact mod_cast sum_eq_zero_of_isNontrivial (hψ b h)
#align add_char.sum_mul_shift AddChar.sum_mulShift
end Additive
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).
@@ -449,7 +449,7 @@ theorem sum_mulShift [DecidableEq R] [IsDomain R'] {ψ : AddChar R R'} (b : R)
(hψ : IsPrimitive ψ) : ∑ x : R, ψ (x * b) = if b = 0 then Fintype.card R else 0 := by
split_ifs with h
· -- case `b = 0`
- simp only [h, MulZeroClass.mul_zero, map_zero_one, Finset.sum_const, Nat.smul_one_eq_coe]
+ simp only [h, mul_zero, map_zero_one, Finset.sum_const, Nat.smul_one_eq_coe]
rfl
· -- case `b ≠ 0`
simp_rw [mul_comm]
Type _
and Sort _
(#6499)
We remove all possible occurences of Type _
and Sort _
in favor of Type*
and Sort*
.
This has nice performance benefits.
@@ -392,7 +392,7 @@ noncomputable def primitiveZModChar (n : ℕ+) (F' : Type v) [Field F'] (h : (n
of the target is different from that of `F`.
We obtain it as the composition of the trace from `F` to `ZMod p` with a primitive
additive character on `ZMod p`, where `p` is the characteristic of `F`. -/
-noncomputable def primitiveCharFiniteField (F F' : Type _) [Field F] [Fintype F] [Field F']
+noncomputable def primitiveCharFiniteField (F F' : Type*) [Field F] [Fintype F] [Field F']
(h : ringChar F' ≠ ringChar F) : PrimitiveAddChar F F' := by
let p := ringChar F
haveI hp : Fact p.Prime := ⟨CharP.char_is_prime F _⟩
@@ -2,15 +2,12 @@
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.add_character
-! leanprover-community/mathlib commit 0723536a0522d24fc2f159a096fb3304bef77472
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
-/
import Mathlib.NumberTheory.Cyclotomic.PrimitiveRoots
import Mathlib.FieldTheory.Finite.Trace
+#align_import number_theory.legendre_symbol.add_character from "leanprover-community/mathlib"@"0723536a0522d24fc2f159a096fb3304bef77472"
+
/-!
# Additive characters of finite rings and fields
@@ -310,7 +310,7 @@ theorem PrimitiveAddChar.prim {R : Type u} [CommRing R] {R' : Type v} [Field R']
variable {C : Type v} [CommRing C]
-section ZmodCharDef
+section ZModCharDef
open Multiplicative
@@ -335,7 +335,7 @@ theorem zmodChar_apply' {n : ℕ+} {ζ : C} (hζ : ζ ^ (n : ℕ) = 1) (a : ℕ)
rw [pow_eq_pow_mod a hζ, zmodChar_apply, ZMod.val_nat_cast a]
#align add_char.zmod_char_apply' AddChar.zmodChar_apply'
-end ZmodCharDef
+end ZModCharDef
/-- An additive character on `ZMod n` is nontrivial iff it takes a value `≠ 1` on `1`. -/
theorem zmod_char_isNontrivial_iff (n : ℕ+) (ψ : AddChar (ZMod n) C) :
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