Definitions of TypeDensity.Surfaces.Lengths
DefinitionTypeDensity_Surfaces_LengthsConcrete surfaces, chart substitutions and lengths
This file sets up the local models used throughout the surface blow-up argument: power series
k[[T,X]] in two variables, the special fibers k[[T,X]]/(T^a X^b), the concrete surfaces
O[[T,X]]/(π - u T^a X^b) over a discrete valuation ring O, the chart substitutions of the
blow-up, and the abstract SurfaceData with its state sets. It then proves the supporting
commutative algebra: ideals of k[[T,X]], Gauss's count of irreducible polynomials over a finite
field, adic completeness of local rings and their quotients, and additivity of lengths of quotients.
Main results
card_pow_eq_sum_irreducible_degrees,irreducible_count_moebius: counting irreducible polynomials over a finite field.axis_ideal_pow_mem_iff,axis_span_isPrime: ideals generated by the variables ofk[[T,X]].mvPowerSeries_fin_two_span_C_var_isPrime: primality of(c, X s)inA[[T,X]].concrete_surface_contact_eq_special_fiber_contact,concrete_crossing_state_eq_union_cells,concrete_single_state_eq_union_cells: state sets of the concrete surface via the special fiber.iInf_sup_pow_eq_of_isLocalRing,isAdicComplete_of_isAdicComplete_maximalIdeal,isAdicComplete_quotient_of_iInf_sup_pow: Krull intersection and adic completeness.length_quotient_sup_mul_eq_add,length_quotient_sup_pow_eq_mul: lengths of quotients.
Provenance: Def_SurfaceBlowupV2_{LinearTowers, ResidueIdeals, ConcreteSurfaces, KillX, SuccessorCharts, SurfaceData, TwoTermCokernels} and the Thm_SurfaceBlowupV2_* nodes named after
the theorems of this file.
-- Generated by the TypeDensity exporter from TypeDensity/Surfaces/Lengths.lean (namespace TypeDensity); do not edit.
import Definitions.Def_TypeDensity_Basic
import Definitions.Def_TypeDensity_Measure_AdicCylinders
import Definitions.Def_TypeDensity_Measure_HenselProducts
import Mathlib.FieldTheory.RatFunc.Basic
import Mathlib.MeasureTheory.Measure.Haar.Unique
import Mathlib.NumberTheory.ArithmeticFunction.Moebius
import Mathlib.NumberTheory.Padics.PadicIntegers
import Mathlib.RingTheory.IntegralClosure.IntegralRestrict
import Mathlib.RingTheory.MvPowerSeries.Basic
import Mathlib.RingTheory.RamificationInertia.Basic
import Mathlib.Topology.Algebra.Nonarchimedean.AdicTopology
import Mathlib.Topology.Algebra.MvPolynomial
import Mathlib.Algebra.Group.Pi.Units
import Mathlib.Order.CompletePartialOrder
import Mathlib.RingTheory.Henselian
import Mathlib.RingTheory.Polynomial.Resultant.Basic
import Mathlib.RingTheory.RegularLocalRing.Defs
import Mathlib.RingTheory.SimpleRing.Principal
import Mathlib.FieldTheory.Finite.Extension
import Mathlib.RingTheory.AdicCompletion.Noetherian
import Mathlib.RingTheory.MvPowerSeries.Equiv
import Mathlib.RingTheory.PicardGroup
set_option autoImplicit false
noncomputable section
namespace TypeDensity
section
variable (k : Type) [CommRing k] (V : ℕ → Type)
[∀ j, AddCommGroup (V j)] [∀ j, Module k (V j)]
/-- The difference map `x ↦ (x j - r j (x (j+1)))_j` of an inverse system `(V j, r j)`. -/
def towerDelta (r : ∀ j, V (j + 1) →ₗ[k] V j) : (∀ j, V j) →ₗ[k] (∀ j, V j) where
toFun x j := x j - r j (x (j+1))
map_add' x y := by ext j; simp only [Pi.add_apply, map_add]; abel
map_smul' a x := by ext j; simp only [Pi.smul_apply, map_smul, smul_sub, RingHom.id_apply]
/-- The compatible threads of an inverse system: the kernel of `towerDelta`. -/
def towerThreads (r : ∀ j, V (j + 1) →ₗ[k] V j) : Submodule k (∀ j, V j) :=
LinearMap.ker (towerDelta k V r)
end
/-- Power series in two variables `T = X 0`, `X = X 1` over `k`. -/
abbrev TwoSeries (k : Type) [CommRing k] := MvPowerSeries (Fin 2) k
/-- The first variable `T` of `k[[T,X]]`. -/
noncomputable def axisT (k : Type) [CommRing k] : TwoSeries k := MvPowerSeries.X 0
/-- The second variable `X` of `k[[T,X]]`. -/
noncomputable def axisX (k : Type) [CommRing k] : TwoSeries k := MvPowerSeries.X 1
/-- The principal monomial ideal `(T^a X^b)` of `k[[T,X]]`. -/
noncomputable def monomialIdeal (k : Type) [CommRing k] (a b : ℕ) : Ideal (TwoSeries k) :=
Ideal.span {axisT k ^ a * axisX k ^ b}
/-- The model special fiber `k[[T,X]] / (T^a X^b)`. -/
abbrev SpecialFiber (k : Type) [CommRing k] (a b : ℕ) := TwoSeries k ⧸ monomialIdeal k a b
/-- The image of `T` in the special fiber. -/
noncomputable def fiberT (k : Type) [CommRing k] (a b : ℕ) : SpecialFiber k a b :=
Ideal.Quotient.mk _ (axisT k)
/-- The image of `X` in the special fiber. -/
noncomputable def fiberX (k : Type) [CommRing k] (a b : ℕ) : SpecialFiber k a b :=
Ideal.Quotient.mk _ (axisX k)
/-- The contact number of `f` and `t`: the length of `B / (f, t)` as a `B`-module. -/
def contact {B : Type} [CommRing B] (f t : B) : ℕ∞ :=
Module.length B (B ⧸ Ideal.span {f,t})
/-- Principal ideals of `k[[T,X]]/(T^a)` with contact `c` against `T`. -/
def singleResidueIdeals (k : Type) [CommRing k] (a c : ℕ) :=
{I : Ideal (SpecialFiber k a 0) // ∃ f, I=Ideal.span {f} ∧ contact f (fiberT k a 0)=c}
/-- Principal ideals of `k[[T,X]]/(T^a X^b)` with contacts `c` against `T` and `h` against `X`. -/
def crossingResidueIdeals (k : Type) [CommRing k] (a b c h : ℕ) :=
{I : Ideal (SpecialFiber k a b) // ∃ f, I=Ideal.span {f} ∧
contact f (fiberT k a b)=c ∧ contact f (fiberX k a b)=h}
section Surface
variable (O : Type) [CommRing O]
/-- The defining relation `π - u T^a X^b` of the concrete surface. -/
noncomputable def surfaceRelation (pi : O) (u : (TwoSeries O)ˣ) (a b : ℕ) : TwoSeries O :=
MvPowerSeries.C pi - (u : TwoSeries O) * axisT O ^ a * axisX O ^ b
/-- The principal ideal generated by `surfaceRelation`. -/
noncomputable def surfaceIdeal (pi : O) (u : (TwoSeries O)ˣ) (a b : ℕ) : Ideal (TwoSeries O) :=
Ideal.span {surfaceRelation O pi u a b}
/-- The concrete surface `O[[T,X]] / (π - u T^a X^b)`. -/
abbrev ConcreteSurface (pi : O) (u : (TwoSeries O)ˣ) (a b : ℕ) :=
TwoSeries O ⧸ surfaceIdeal O pi u a b
/-- The quotient map onto the concrete surface. -/
noncomputable def surfaceMk (pi : O) (u : (TwoSeries O)ˣ) (a b : ℕ) :
TwoSeries O →+* ConcreteSurface O pi u a b :=
Ideal.Quotient.mk (surfaceIdeal O pi u a b)
/-- The image of `T` in the concrete surface. -/
noncomputable def surfaceT (pi : O) (u : (TwoSeries O)ˣ) (a b : ℕ) : ConcreteSurface O pi u a b :=
surfaceMk O pi u a b (axisT O)
/-- The image of `X` in the concrete surface. -/
noncomputable def surfaceX (pi : O) (u : (TwoSeries O)ˣ) (a b : ℕ) : ConcreteSurface O pi u a b :=
surfaceMk O pi u a b (axisX O)
/-- The image of the unit `u` in the concrete surface. -/
noncomputable def surfaceUnit (pi : O) (u : (TwoSeries O)ˣ) (a b : ℕ) :
(ConcreteSurface O pi u a b)ˣ :=
Units.map (surfaceMk O pi u a b).toMonoidHom u
/-- The ideal `(T, X)` of `O[[T,X]]`. -/
noncomputable def variableIdeal : Ideal (TwoSeries O) := Ideal.span {axisT O, axisX O}
/-- The ideal `(t, x)` of the concrete surface generated by the images of `T` and `X`. -/
noncomputable def surfaceParameterIdeal (pi : O) (u : (TwoSeries O)ˣ) (a b : ℕ) :
Ideal (ConcreteSurface O pi u a b) :=
Ideal.span {surfaceT O pi u a b, surfaceX O pi u a b}
/-- Reduction of coefficients `O[[T,X]] → k[[T,X]]` to the residue field `k` of `O`. -/
noncomputable def residueSeries [IsLocalRing O] :
TwoSeries O →+* TwoSeries (IsLocalRing.ResidueField O) :=
MvPowerSeries.map (IsLocalRing.residue O)
end Surface
section Basis
variable {O M : Type} [CommRing O] [AddCommGroup M] [Module O M]
/-- `β` is a basis of `M / π M` over `O / π`: it spans modulo `π`, and its relations modulo `π`
have all coefficients divisible by `π`. -/
def ResidueBasisFamily (pi : O) {N : ℕ} (β : Fin N → M) : Prop :=
(∀ m : M, ∃ z : Fin N → O, ∃ m' : M, m = (∑ i, z i • β i) + pi • m') ∧
(∀ z : Fin N → O, (∃ m' : M, (∑ i, z i • β i) = pi • m') → ∀ i, pi ∣ z i)
end Basis
section
variable (O : Type) [CommRing O]
/-- The family killing X: the first variable goes to the one-variable variable, the second to 0. -/
noncomputable def killXFamily : Fin 2 → PowerSeries O := ![PowerSeries.X, 0]
/-- The family `killXFamily` is substitutable (zero constant coefficients). -/
theorem killXFamily_hasSubst : MvPowerSeries.HasSubst (killXFamily O) := by
refine MvPowerSeries.hasSubst_of_constantCoeff_zero (fun s ↦ ?_)
fin_cases s <;> simp [killXFamily, PowerSeries.X]
/-- `killX O : O[[T,X]] → O[[Y]]`, T ↦ Y, X ↦ 0 (Y the variable of the one-variable series ring). -/
noncomputable def killX : TwoSeries O →ₐ[O] PowerSeries O :=
MvPowerSeries.substAlgHom (killXFamily_hasSubst O)
/-- `residueKillX O : O[[T,X]] → k[[Y]]`: kill the second variable, then reduce coefficients to
the residue field. -/
noncomputable def residueKillX [IsLocalRing O] :
TwoSeries O →+* PowerSeries (IsLocalRing.ResidueField O) :=
(MvPowerSeries.map (IsLocalRing.residue O)).comp (killX O).toRingHom
end
section Subst
variable (O : Type) [CommRing O]
/-- The substitution family of the t-chart point Z = α: T ↦ T, X ↦ T·(X + α) (x = tZ, Z = X + α). -/
noncomputable def tChartFamily (α : O) : Fin 2 → TwoSeries O :=
![axisT O, axisT O * (axisX O + MvPowerSeries.C α)]
/-- The family `tChartFamily` is substitutable (zero constant coefficients). -/
theorem tChartFamily_hasSubst (α : O) : MvPowerSeries.HasSubst (tChartFamily O α) := by
refine MvPowerSeries.hasSubst_of_constantCoeff_zero (fun s ↦ ?_)
fin_cases s <;> simp [tChartFamily, axisT, axisX]
/-- `chartSubst O α : O[[T,X]] → O[[T,X]]`, T ↦ T, X ↦ T·(X + α), as an O-algebra homomorphism. -/
noncomputable def chartSubst (α : O) : TwoSeries O →ₐ[O] TwoSeries O :=
MvPowerSeries.substAlgHom (tChartFamily_hasSubst O α)
/-- The substitution family of the x-chart point W = 0: T ↦ T·X, X ↦ T (t = xW, T = x, X = W). -/
noncomputable def xChartFamily : Fin 2 → TwoSeries O := ![axisT O * axisX O, axisT O]
/-- The family `xChartFamily` is substitutable (zero constant coefficients). -/
theorem xChartFamily_hasSubst : MvPowerSeries.HasSubst (xChartFamily O) := by
refine MvPowerSeries.hasSubst_of_constantCoeff_zero (fun s ↦ ?_)
fin_cases s <;> simp [xChartFamily, axisT, axisX]
/-- `xChartSubst O : O[[T,X]] → O[[T,X]]`, T ↦ T·X, X ↦ T. -/
noncomputable def xChartSubst : TwoSeries O →ₐ[O] TwoSeries O :=
MvPowerSeries.substAlgHom (xChartFamily_hasSubst O)
/-- The image of a unit under `chartSubst O α`. -/
noncomputable def substUnit (α : O) (u : (TwoSeries O)ˣ) : (TwoSeries O)ˣ :=
Units.map (chartSubst O α).toRingHom.toMonoidHom u
/-- The image of a unit under `xChartSubst O`. -/
noncomputable def xSubstUnit (u : (TwoSeries O)ˣ) : (TwoSeries O)ˣ :=
Units.map (xChartSubst O).toRingHom.toMonoidHom u
/-- `X + α` is a unit of `O[[T,X]]` when `α` is a unit of `O`. -/
theorem isUnit_axisX_add_C (α : O) (hα : IsUnit α) : IsUnit
(axisX O + MvPowerSeries.C α) := by
rw [MvPowerSeries.isUnit_iff_constantCoeff]
simpa [axisX] using hα
/-- The unit X + α of O[[T,X]] for a unit α of O. -/
noncomputable def shiftUnit (α : O) (hα : IsUnit α) : (TwoSeries O)ˣ :=
(isUnit_axisX_add_C O α hα).unit
/-- Coefficient extension of a unit of O[[T,X]] along a ring homomorphism O → O'. -/
noncomputable def baseChangeUnit {O' : Type} [CommRing O'] (ρ : O →+* O') (u : (TwoSeries O)ˣ) :
(TwoSeries O')ˣ :=
Units.map (MvPowerSeries.map ρ).toMonoidHom u
/-- The family killing T: T ↦ 0, X ↦ X, with values in one-variable power series. -/
noncomputable def killTFamily : Fin 2 → PowerSeries O := ![0, PowerSeries.X]
/-- The family `killTFamily` is substitutable (zero constant coefficients). -/
theorem killTFamily_hasSubst : MvPowerSeries.HasSubst (killTFamily O) := by
refine MvPowerSeries.hasSubst_of_constantCoeff_zero (fun s ↦ ?_)
fin_cases s <;> simp [killTFamily, PowerSeries.X]
/-- `killT O : O[[T,X]] → O[[X]]`, T ↦ 0, X ↦ X. -/
noncomputable def killT : TwoSeries O →ₐ[O] PowerSeries O :=
MvPowerSeries.substAlgHom (killTFamily_hasSubst O)
/-- `residueKillT O : O[[T,X]] → k[[X]]`: kill T, then reduce coefficients to the residue field. -/
noncomputable def residueKillT [IsLocalRing O] :
TwoSeries O →+* PowerSeries (IsLocalRing.ResidueField O) :=
(MvPowerSeries.map (IsLocalRing.residue O)).comp (killT O).toRingHom
end Subst
section Eval
variable {O S : Type} [CommRing O] [CommRing S]
/-- The constant family (e, z) of a ring S, viewed in `MvPowerSeries Unit S`. -/
noncomputable def nilpotentFamily (e z : S) : Fin 2 → MvPowerSeries Unit S :=
![MvPowerSeries.C e, MvPowerSeries.C z]
/-- A family of two nilpotent constants is substitutable. -/
theorem nilpotentFamily_hasSubst (e z : S) (he : IsNilpotent e) (hz : IsNilpotent z) :
MvPowerSeries.HasSubst (nilpotentFamily e z) := by
refine MvPowerSeries.hasSubst_of_constantCoeff_nilpotent (fun s ↦ ?_)
fin_cases s <;> simpa [nilpotentFamily]
/-- Evaluation of a series of `O[[T,X]]` at two nilpotent elements `e, z` of a ring `S` along
`φ : O → S`: `nilpotentEval φ e z he hz f = f(e, z)`, a ring homomorphism (substitution followed
by the constant coefficient of the resulting constant series in `MvPowerSeries Unit S`). -/
noncomputable def nilpotentEval (φ : O →+* S) (e z : S) (he : IsNilpotent e) (hz : IsNilpotent z) :
TwoSeries O →+* S :=
(MvPowerSeries.constantCoeff : MvPowerSeries Unit S →+* S).comp
((MvPowerSeries.substAlgHom (nilpotentFamily_hasSubst e z he hz)).toRingHom.comp
(MvPowerSeries.map φ))
end Eval
section
variable (O R : Type) [CommRing O] [IsDomain O] [IsDiscreteValuationRing O]
[CommRing R] [IsDomain R] [Algebra O R] [IsRegularLocalRing R]
/-- Data of a regular complete two-dimensional local `O`-algebra `R` with parameters `t, x`,
residue field identified with that of `O`, and vertical equation `π = unit · t^a x^b`. -/
structure SurfaceData where
pi : O
pi_irreducible : Irreducible pi
t : R
x : R
unit : Rˣ
a : ℕ
b : ℕ
a_pos : 0 < a
parameters : Ideal.span {t,x} = IsLocalRing.maximalIdeal R
dimension : ringKrullDim R = 2
complete : IsAdicComplete (IsLocalRing.maximalIdeal R) R
base_injective : Function.Injective (algebraMap O R)
residueEquiv : IsLocalRing.ResidueField O ≃+* IsLocalRing.ResidueField R
residue_compat : ∀ c : O, residueEquiv (IsLocalRing.residue O c) =
IsLocalRing.residue R (algebraMap O R c)
vertical : algebraMap O R pi = (unit : R) * t^a * x^b
/-- The contact length of an ideal `J` against `y`: the length of `R / (J + (y))`. -/
def idealContact (J : Ideal R) (y : R) : ℕ∞ :=
Module.length R (R ⧸ (J ⊔ Ideal.span {y}))
/-- The principal ideals of `R` realising the combinatorial state `s` relative to `S`. -/
def surfaceStateSet (S : SurfaceData O R) (s : State) : Set (Ideal R) :=
{J | (∃ f : R, J = Ideal.span {f}) ∧ s.Valid ∧
match s with
| .single a c => S.a = a ∧ S.b = 0 ∧ idealContact R J S.t = c
| .crossing a b c h => S.a = a ∧ S.b = b ∧
idealContact R J S.t = c ∧ idealContact R J S.x = h}
/-- `J` has multiplicity `d`: it lies in `𝔪^d` but not in `𝔪^(d+1)`. -/
def HasMultiplicity (J : Ideal R) (d : ℕ) : Prop :=
J ≤ (IsLocalRing.maximalIdeal R)^d ∧ ¬ J ≤ (IsLocalRing.maximalIdeal R)^(d+1)
end
section
variable {O A0 A1 B0 B1 : Type} [CommRing O]
[AddCommGroup A0] [Module O A0] [AddCommGroup A1] [Module O A1]
[AddCommGroup B0] [Module O B0] [AddCommGroup B1] [Module O B1]
/-- The map on cokernels induced by a morphism of two-term complexes. -/
def twoTermCokerMap (dA : A0 →ₗ[O] A1) (dB : B0 →ₗ[O] B1)
(u0 : A0 →ₗ[O] B0) (u1 : A1 →ₗ[O] B1)
(h : u1.comp dA = dB.comp u0) :
(A1 ⧸ LinearMap.range dA) →ₗ[O] (B1 ⧸ LinearMap.range dB) :=
(LinearMap.range dA).mapQ (LinearMap.range dB) u1 (by
rintro y ⟨x, rfl⟩
change u1 (dA x) ∈ LinearMap.range dB
refine ⟨u0 x, ?_⟩
exact (congrArg (fun v : A0 →ₗ[O] B1 ↦ v x) h).symm)
end
/-- Over a finite field with `q` elements, `X^(q^m) - X` is the product of the monic irreducible
polynomials whose degree divides `m`. -/
theorem X_pow_card_pow_sub_X_eq_prod_irreducible (k : Type) [Field k] [Finite k] (m : ℕ)
(hm : 0 < m) (S : Finset (Polynomial k))
(hS : ∀ g, g ∈ S ↔ g.Monic ∧ Irreducible g ∧ g.natDegree ∣ m) :
(Polynomial.X ^ (Nat.card k) ^ m - Polynomial.X : Polynomial k) = ∏ g ∈ S, g := by
classical
set P : Polynomial k := Polynomial.X ^ (Nat.card k) ^ m - Polynomial.X with hPdef
have hq : 1 < Nat.card k := Finite.one_lt_card
have hP0 : P ≠ 0 := FiniteField.X_pow_card_pow_sub_X_ne_zero k hm.ne' hq
have hPsep : Squarefree P := by
obtain ⟨p, hp⟩ := CharP.exists k
have := Fintype.ofFinite k
have : Fact p.Prime := ⟨CharP.char_is_prime k p⟩
obtain ⟨n, hn, hcard⟩ := FiniteField.card k p
have hdvd : p ∣ Nat.card k ^ m := by
rw [Nat.card_eq_fintype_card, hcard, ← pow_mul]
exact dvd_pow_self p (Nat.mul_ne_zero n.ne_zero hm.ne')
exact (galois_poly_separable p _ hdvd).squarefree
set N := UniqueFactorizationMonoid.normalizedFactors P with hN
have hnodup : N.Nodup :=
(UniqueFactorizationMonoid.squarefree_iff_nodup_normalizedFactors hP0).mp hPsep
have hmonic : ∀ g ∈ N, g.Monic ∧ Irreducible g := fun g hg ↦ by
have hirr := UniqueFactorizationMonoid.irreducible_of_normalized_factor g hg
refine ⟨?_, hirr⟩
rw [← UniqueFactorizationMonoid.normalize_normalized_factor g hg]
exact Polynomial.monic_normalize hirr.ne_zero
have hprod : N.prod = P := by
apply Polynomial.eq_of_monic_of_associated
· simpa using Polynomial.monic_multiset_prod_of_monic N id (fun g hg ↦ (hmonic g hg).1)
· rw [hPdef]
apply Polynomial.Monic.sub_of_left (Polynomial.monic_X_pow _)
rw [Polynomial.degree_X, Polynomial.degree_X_pow]
exact_mod_cast Nat.one_lt_pow hm.ne' hq
· exact UniqueFactorizationMonoid.prod_normalizedFactors hP0
have hset : N.toFinset = S := by
ext g
rw [Multiset.mem_toFinset, hS]
constructor
· intro hg
obtain ⟨h1, h2⟩ := hmonic g hg
exact ⟨h1, h2, h2.natDegree_dvd_of_dvd_X_pow_card_pow_sub_X
(UniqueFactorizationMonoid.dvd_of_mem_normalizedFactors hg)⟩
· rintro ⟨h1, h2, h3⟩
have hd : g ∣ P := h2.natDegree_dvd_iff_dvd_X_pow_card_pow_sub_X.mp h3
obtain ⟨g', hg', hass⟩ :=
UniqueFactorizationMonoid.exists_mem_normalizedFactors_of_dvd hP0 h2 hd
rwa [Polynomial.eq_of_monic_of_associated h1 (hmonic g' hg').1 hass]
rw [← hset, Finset.prod_eq_multiset_prod, Multiset.toFinset_val, Multiset.map_id',
Multiset.dedup_eq_self.mpr hnodup, hprod]
/-- Gauss's formula: `q^m = ∑_{d ∣ m} d · #{monic irreducible polynomials of degree d}`. -/
theorem card_pow_eq_sum_irreducible_degrees (k : Type) [Field k] [Finite k] (m : ℕ) (hm : 0 < m) :
(Nat.card k) ^ m = ∑ d ∈ m.divisors, d *
Nat.card {g : Polynomial k // g.Monic ∧ Irreducible g ∧ g.natDegree = d} := by
have hMD : ∀ d, ({F : Polynomial k | F.Monic ∧ F.natDegree = d} : Set _).Finite := by
intro d
rw [← Set.finite_coe_iff]
apply Nat.finite_of_card_ne_zero
change Nat.card {F : Polynomial k // F.Monic ∧ F.natDegree = d} ≠ 0
rw [monic_residue_polynomial_count]
exact pow_ne_zero _ Nat.card_pos.ne'
have hSig : ({g : Polynomial k | g.Monic ∧ Irreducible g ∧ g.natDegree ∣ m} : Set _).Finite := by
apply Set.Finite.subset ((Finset.finite_toSet m.divisors).biUnion (fun d _ ↦ hMD d))
intro g hg
simp only [Set.mem_ofPred_eq] at hg
simp only [Set.mem_iUnion, Set.mem_ofPred_eq, Finset.mem_coe, Nat.mem_divisors]
exact ⟨g.natDegree, ⟨hg.2.2, hm.ne'⟩, hg.1, rfl⟩
set S := hSig.toFinset with hSdef
have hS : ∀ g, g ∈ S ↔ g.Monic ∧ Irreducible g ∧ g.natDegree ∣ m := by
intro g; rw [hSdef, Set.Finite.mem_toFinset]; rfl
have hprod := X_pow_card_pow_sub_X_eq_prod_irreducible k m hm S hS
have hdeg := congrArg Polynomial.natDegree hprod
rw [FiniteField.X_pow_card_pow_sub_X_natDegree_eq k hm.ne' Finite.one_lt_card,
Polynomial.natDegree_prod_of_monic _ _ (fun g hg ↦ ((hS g).1 hg).1)] at hdeg
rw [hdeg, ← Finset.sum_fiberwise_of_maps_to (g := Polynomial.natDegree) (t := m.divisors)
(fun g hg ↦ Nat.mem_divisors.2 ⟨((hS g).1 hg).2.2, hm.ne'⟩)]
apply Finset.sum_congr rfl
intro d hd
have hd' := (Nat.mem_divisors.1 hd).1
rw [Finset.sum_congr rfl (g := fun _ ↦ d) (fun g hg ↦ (Finset.mem_filter.1 hg).2),
Finset.sum_const, smul_eq_mul, mul_comm]
congr 1
rw [← Nat.card_eq_finsetCard]
refine Nat.card_congr (Equiv.subtypeEquivRight fun g ↦ ?_)
rw [Finset.mem_filter, hS]
exact ⟨fun ⟨⟨h1, h2, _⟩, h4⟩ ↦ ⟨h1, h2, h4⟩, fun ⟨h1, h2, h4⟩ ↦ ⟨⟨h1, h2, h4 ▸ hd'⟩, h4⟩⟩
/-- Möbius inversion of Gauss's formula: `δ · N_δ = ∑_{j ∣ δ} μ(j) q^(δ/j)`. -/
theorem irreducible_count_moebius (k : Type) [Field k] [Finite k] (δ : ℕ) (hδ : 0 < δ) :
(δ : ℚ) * (Nat.card {g : Polynomial k // g.Monic ∧ Irreducible g ∧ g.natDegree = δ} : ℕ) =
∑ j ∈ δ.divisors, ((ArithmeticFunction.moebius j : ℤ) : ℚ) * (Nat.card k : ℚ) ^ (δ / j) := by
have h := (ArithmeticFunction.sum_eq_iff_sum_mul_moebius_eq (R := ℚ)
(f := fun d ↦
(d : ℚ) * (Nat.card {g : Polynomial k // g.Monic ∧ Irreducible g ∧ g.natDegree = d} : ℕ))
(g := fun n ↦ (Nat.card k : ℚ) ^ n)).mp (by
intro n hn
have := congrArg (fun x : ℕ ↦ (x : ℚ))
(card_pow_eq_sum_irreducible_degrees k n hn)
simpa [Nat.cast_sum, Nat.cast_mul, Nat.cast_pow] using this.symm) δ hδ
rw [← h, Nat.sum_divisorsAntidiagonal
(fun i j ↦ ((ArithmeticFunction.moebius i : ℤ) : ℚ) * (Nat.card k : ℚ) ^ j)]
noncomputable def lowOrderIdeal (k : Type) [CommRing k] (n : ℕ) : Ideal (TwoSeries k) where
carrier := {φ | ∀ m : Fin 2 →₀ ℕ, m 0 + m 1 < n → MvPowerSeries.coeff m φ = 0}
zero_mem' := by simp
add_mem' ha hb m hm := by simp [ha m hm, hb m hm]
smul_mem' c x hx m hm := by
rw [smul_eq_mul, MvPowerSeries.coeff_mul]
apply Finset.sum_eq_zero
intro p hp
rw [Finset.HasAntidiagonal.mem_antidiagonal] at hp
have h0 := congrArg (fun f ↦ f 0) hp
have h1 := congrArg (fun f ↦ f 1) hp
simp only [Finsupp.add_apply] at h0 h1
rw [hx p.2 (by omega), mul_zero]
lemma lowOrderIdeal_mul (k : Type) [CommRing k]
(a b : ℕ) : lowOrderIdeal k a * lowOrderIdeal k b ≤ lowOrderIdeal k (a + b) := by
rw [Ideal.mul_le]
intro x hx y hy m hm
rw [MvPowerSeries.coeff_mul]
apply Finset.sum_eq_zero
intro p hp
rw [Finset.HasAntidiagonal.mem_antidiagonal] at hp
have h0 := congrArg (fun f ↦ f 0) hp
have h1 := congrArg (fun f ↦ f 1) hp
simp only [Finsupp.add_apply] at h0 h1
by_cases h : p.1 0 + p.1 1 < a
· rw [hx p.1 h, zero_mul]
· rw [hy p.2 (by omega), mul_zero]
lemma lowOrderIdeal_zero (k : Type) [CommRing k] : lowOrderIdeal k 0 = ⊤ :=
eq_top_iff.2 fun _ _ _ hm ↦ by omega
lemma span_le_lowOrderIdeal_one (k : Type) [CommRing k] : Ideal.span
{axisT k, axisX k} ≤ lowOrderIdeal k 1 := by
rw [Ideal.span_le]
have key (s : Fin 2) : (MvPowerSeries.X s : TwoSeries k) ∈ lowOrderIdeal k 1 := fun m hm ↦ by
obtain rfl : m = 0 := by ext i; fin_cases i <;> simp <;> omega
exact MvPowerSeries.coeff_zero_X s
rintro x (rfl | rfl)
exacts [key 0, key 1]
lemma pow_le_lowOrderIdeal (k : Type) [CommRing k] (L : ℕ) :
(Ideal.span {axisT k, axisX k})^L ≤ lowOrderIdeal k L := by
induction L with
| zero => rw [pow_zero, Ideal.one_eq_top, lowOrderIdeal_zero]
| succ L ih =>
rw [pow_succ]
exact (Ideal.mul_mono ih (span_le_lowOrderIdeal_one k)).trans (lowOrderIdeal_mul k L 1)
lemma lowOrderIdeal_le_pow (k : Type) [CommRing k] (L : ℕ) :
lowOrderIdeal k L ≤ (Ideal.span {axisT k, axisX k})^L := by
have key (s : Fin 2) (a : TwoSeries k) (m : Fin 2 →₀ ℕ) :
MvPowerSeries.coeff (m + Finsupp.single s 1) (MvPowerSeries.X s * a) =
MvPowerSeries.coeff m a := by
rw [MvPowerSeries.X, MvPowerSeries.coeff_monomial_mul, if_pos le_add_self,
add_tsub_cancel_right, one_mul]
induction L with
| zero => simp
| succ N ih =>
intro g hg
-- split `g = T a + X b`, where `X b` collects the terms not divisible by `T`
set g1 : TwoSeries k := fun m ↦ if m 0 = 0 then MvPowerSeries.coeff m g else 0
have c1 (m) : MvPowerSeries.coeff m g1 = if m 0 = 0 then MvPowerSeries.coeff m g else 0 :=
rfl
obtain ⟨a, ha⟩ : MvPowerSeries.X 0 ∣ g - g1 := by
refine MvPowerSeries.X_dvd_iff.2 fun m hm ↦ ?_
rw [map_sub, c1, if_pos hm, sub_self]
obtain ⟨b, hb⟩ : MvPowerSeries.X 1 ∣ g1 := by
refine MvPowerSeries.X_dvd_iff.2 fun m hm ↦ ?_
rw [c1]
split_ifs with h
· exact hg m (by omega)
· rfl
have hA : a ∈ lowOrderIdeal k N := fun m hm ↦ by
rw [← key 0 a m, ← ha, map_sub, c1, if_neg (by simp), sub_zero]
exact hg _ (by simp; omega)
have hB : b ∈ lowOrderIdeal k N := fun m hm ↦ by
rw [← key 1 b m, ← hb, c1]
split_ifs with h
· exact hg _ (by simp; omega)
· rfl
rw [show g = (g - g1) + g1 by ring, ha, hb, pow_succ']
exact Ideal.add_mem _ (Ideal.mul_mem_mul (Ideal.subset_span (by simp [axisT])) (ih hA))
(Ideal.mul_mem_mul (Ideal.subset_span (by simp [axisX])) (ih hB))
/-- A series lies in `(T, X)^L` iff all its coefficients of total degree `< L` vanish. -/
theorem axis_ideal_pow_mem_iff (k : Type) [CommRing k] (L : ℕ) (φ : TwoSeries k) :
φ ∈ (Ideal.span {axisT k, axisX k})^L ↔ ∀ m : Fin 2 →₀ ℕ, m 0 + m 1 < L →
MvPowerSeries.coeff m φ = 0 :=
⟨fun h ↦ pow_le_lowOrderIdeal k L h, fun h ↦ lowOrderIdeal_le_pow k L h⟩
end TypeDensity
end