Tate's algorithm: the output does not depend on the choices, and certifies minimality

Tate's algorithm reads the reduction symbol of a Weierstrass equation over a discrete valuation ring R with uniformiser ϖ by alternating changes of variables over R with divisibility tests (WeierstrassCurve.IsTateTerminal, WeierstrassCurve.exists_isTateTerminal). The changes of variables are not unique: at each step any one moving the singular point, or the multiple root of the residue polynomial, to the origin will do. This file proves that the symbol does not depend on these choices, nor on the uniformiser. If W and C • W are equations over R, related by a change of variables C over R, on which the algorithm stops with symbols s and s', then s = s'. Since two minimal equations of one elliptic curve over the fraction field are related by a change of variables over R, the symbol at which the algorithm stops on a minimal equation is an invariant of the curve. No minimality is needed for the first statement.

The same invariance shows that the algorithm stops only on minimal equations. A change of variables over R carries a non-minimal equation to one with ϖⁱ ∣ aᵢ for i = 1, 2, 3, 4, 6 (WeierstrassCurve.exists_variableChange_pow_dvd_a₁_a₂_a₃_a₄_a₆_of_not_isMinimal). That equation passes every test of the algorithm, Step 10's ϖ⁶ ∣ a₆ included, so the algorithm cannot have stopped on the original equation. Together with termination this says that Tate's algorithm decides minimality.

Main results

• WeierstrassCurve.dvd_r_and_dvd_t_of_dvd_a₃_a₄_a₆: a change of variables between two equations whose reductions modulo a prime are singular at the origin fixes the origin modulo that prime.
• WeierstrassCurve.IsTateTerminal.eq_of_smul: if the algorithm stops on W with a symbol s, and on C • W, for C over R, with a symbol s', then s' = s.
• WeierstrassCurve.isTateTerminal_iff_of_associated: the stopping conditions do not depend on the uniformiser.
• WeierstrassCurve.IsTateTerminal.eq_of_isMinimal_smul: the same statement for two minimal equations of one elliptic curve over the fraction field, with any uniformisers.
• WeierstrassCurve.IsTateTerminal.isMinimal_baseChange: an equation on which the algorithm stops is minimal over the fraction field.
• WeierstrassCurve.isMinimal_baseChange_iff_exists_isTateTerminal: with perfect residue field, an equation with nonzero discriminant is minimal exactly when the algorithm, run on it, stops.

Implementation notes

The algorithm applies its tests in a fixed order, and each test is invariant under the changes of variables between two equations which have passed the earlier tests and are in the normal form the test is read on:

• ϖ ∣ Δ is invariant because Δ changes by a unit;
• if both equations reduce to curves singular at the origin, C fixes the origin modulo ϖ (WeierstrassCurve.dvd_r_and_dvd_t_of_dvd_a₃_a₄_a₆), since the reduction of W has only one singular point (WeierstrassCurve.Affine.eq_of_isSingular_of_isSingular). Then b₂, a₆ modulo ϖ², b₈ modulo ϖ³ and b₆ modulo ϖ³ change by units, which gives invariance of the tests of Steps 2 to 5;
• if both equations are in the normal form of Step 6, then ϖ ∣ s and ϖ² ∣ t, and the residue cubic of C • W is v⁶ P (v⁻² T + ρ), where P is that of W, v is the reduction of u⁻¹ and ρ that of r / ϖ. So the discriminant of the residue cubic T³ + b T² + c T + d, and b² - 3c, change by units. The first is the test of I₀*; the second vanishes on the residue cubic T³ of Steps 8 to 10 and not on the residue cubics T³ + b T², b ≠ 0, of the Iₙ* branch;
• if both equations are in the normal form of Step 8, so that both residue cubics are T³, then ρ = 0. This makes b₆ modulo ϖ⁵ invariant, which is the test of IV*, and on the normal form of Step 9 also ϖ³ ∣ t, which makes a₄ modulo ϖ⁴ invariant, the test of III*, and a₆ modulo ϖ⁶ invariant, the test of II*.

If the algorithm stopped on W at an earlier test than on C • W, then W would fail a test that C • W passes, which invariance rules out. So it stops on both at the same test, and the symbol is determined by the test, except for the index of Iₙ, which is the valuation of Δ, and the index of Iₙ*, which is the stage at which the subprocedure of Step 7 stops. The same argument applies to that subprocedure: each stage implies the previous one and passes its test, and between two equations at the same stage a change of variables is close enough to the identity (ϖ^(k+2) ∣ r, ϖ ∣ s and ϖ^(k+2) ∣ t at the odd stage k, and ϖ^(k+3) ∣ t at the even stage k) that the test of the stage, ϖ^(2k+5) ∣ b₆ or ϖ^(2k+7) ∣ a₄² - 4 a₂ a₆, is invariant. The bounds are proved stage by stage from the equations for a₄ and a₆.

References

• J. H. Silverman, Advanced Topics in the Arithmetic of Elliptic Curves, GTM 151, IV.9.
• J. Tate, Algorithm for determining the type of a singular fibre in an elliptic pencil, in Modular Functions of One Variable IV, LNM 476 (1975), 33–52.

theorem WeierstrassCurve.dvd_r_and_dvd_t_of_dvd_a₃_a₄_a₆ {R : Type u_1} [CommRing R] {ϖ : R} (hϖ : Prime ϖ) {W : WeierstrassCurve R} {C : VariableChange R} (h₃ : ϖ ∣ W.a₃) (h₄ : ϖ ∣ W.a₄) (h₆ : ϖ ∣ W.a₆) (h₃' : ϖ ∣ (C • W).a₃) (h₄' : ϖ ∣ (C • W).a₄) (h₆' : ϖ ∣ (C • W).a₆) : ϖ ∣ C.r ∧ ϖ ∣ C.t

A change of variables fixes the singular point of the reduction. If the reductions modulo a prime ϖ of W and of C • W are both singular at the origin, that is ϖ divides a₃, a₄ and a₆ of both equations, then C maps the origin to the origin modulo ϖ: ϖ ∣ r and ϖ ∣ t.

theorem WeierstrassCurve.isTateTerminal_iff_of_associated {R : Type u_1} [CommRing R] {ϖ : R} {W : WeierstrassCurve R} {ϖ' : R} (hϖ : Associated ϖ ϖ') {s : TauCeti.ReductionSymbol} : W.IsTateTerminal ϖ s ↔ W.IsTateTerminal ϖ' s

The stopping conditions of Tate's algorithm do not depend on the uniformiser.

The index of Iₙ*

The subprocedure of Step 7 runs through the stages of IsTateOddStage and IsTateEvenStage and stops at the first one whose test fails. Counting the stages from 0, as the index of Iₙ* minus one does, stage 2k is the odd stage k, with test ϖ^(2k+5) ∣ b₆, and stage 2k + 1 is the even stage k, with test ϖ^(2k+7) ∣ a₄² - 4 a₂ a₆. Each stage implies the previous one and passes its test. Between two equations at the same stage, a change of variables satisfies ϖ^(k+2) ∣ r, ϖ ∣ s and ϖ^(k+2) ∣ t at the odd stage k, and moreover ϖ^(k+3) ∣ t at the even stage k; these bounds make the test of the stage invariant.

theorem WeierstrassCurve.IsTateTerminal.eq_of_smul {R : Type u_1} [CommRing R] [IsDomain R] [IsDiscreteValuationRing R] {ϖ : R} {W : WeierstrassCurve R} (hϖ : Irreducible ϖ) {C : VariableChange R} {s s' : TauCeti.ReductionSymbol} (h : W.IsTateTerminal ϖ s) (h' : (C • W).IsTateTerminal ϖ s') : s' = s

The output of Tate's algorithm does not depend on the changes of variables. If the algorithm stops on W with a symbol s, and on C • W, for a change of variables C over R, with a symbol s', then s' = s.

theorem WeierstrassCurve.IsTateTerminal.isMinimal_baseChange {R : Type u_1} [CommRing R] [IsDomain R] [IsDiscreteValuationRing R] {ϖ : R} {W : WeierstrassCurve R} {K : Type u_2} [Field K] [Algebra R K] [IsFractionRing R K] (hϖ : Irreducible ϖ) {s : TauCeti.ReductionSymbol} (h : W.IsTateTerminal ϖ s) : IsMinimal R (W.baseChange K)

Tate's algorithm only stops on minimal equations. If the algorithm stops on an equation W over R, with any symbol, then the base change of W to the fraction field is minimal over R.

theorem WeierstrassCurve.isMinimal_baseChange_iff_exists_isTateTerminal {R : Type u_1} [CommRing R] [IsDomain R] [IsDiscreteValuationRing R] {ϖ : R} {W : WeierstrassCurve R} {K : Type u_2} [Field K] [Algebra R K] [IsFractionRing R K] [PerfectField (IsLocalRing.ResidueField R)] (hϖ : Irreducible ϖ) (hΔ : W.Δ ≠ 0) : IsMinimal R (W.baseChange K) ↔ ∃ (C : VariableChange R) (s : TauCeti.ReductionSymbol), (C • W).IsTateTerminal ϖ s

Tate's algorithm decides minimality. Over a discrete valuation ring with perfect residue field, an equation over R with nonzero discriminant is minimal over the fraction field exactly when some change of variables over R carries it to an equation on which the algorithm stops.

theorem WeierstrassCurve.IsTateTerminal.eq_of_isMinimal_smul {R : Type u_1} [CommRing R] [IsDomain R] [IsDiscreteValuationRing R] {ϖ : R} {K : Type u_2} [Field K] [Algebra R K] [IsFractionRing R K] {ϖ' : R} {W₁ W₂ : WeierstrassCurve R} [IsMinimal R (W₁.baseChange K)] [IsMinimal R (W₂.baseChange K)] [(W₁.baseChange K).IsElliptic] (hϖ : Irreducible ϖ) (hϖ' : Irreducible ϖ') (D : VariableChange K) (hD : D • W₁.baseChange K = W₂.baseChange K) {s₁ s₂ : TauCeti.ReductionSymbol} (h₁ : W₁.IsTateTerminal ϖ s₁) (h₂ : W₂.IsTateTerminal ϖ' s₂) : s₂ = s₁

The output of Tate's algorithm is an invariant of the curve. If the algorithm stops on two minimal equations of one elliptic curve over K, with any uniformisers, then it stops with the same symbol.