Tate's algorithm

<h2 id="notation">Notation</h2>
Assume that all the coefficients of the equation of the curve lie in a complete <a href="/facts/Discrete_valuation_ring/DaHoTBSH">discrete valuation ring</a> R with <a href="/facts/Perfect_field/0JJvr8Xx">perfect</a> <a href="/facts/Residue_field/e6nflEmB">residue field</a> K and <a href="/facts/Maximal_ideal/nf4DnKVS">maximal ideal</a> generated by a <a href="/facts/Uniformizing_element/DaHoTBSH">prime</a> π. 
The elliptic curve is given by the equation

y
          
            2
          
        
        +
        
          a
          
            1
          
        
        x
        y
        +
        
          a
          
            3
          
        
        y
        =
        
          x
          
            3
          
        
        +
        
          a
          
            2
          
        
        
          x
          
            2
          
        
        +
        
          a
          
            4
          
        
        x
        +
        
          a
          
            6
          
        
        .
      
    
    {\displaystyle y^{2}+a_{1}xy+a_{3}y=x^{3}+a_{2}x^{2}+a_{4}x+a_{6}.}

Define:

v
 (
 Δ
 )
 =
 
 
 {\displaystyle v(\Delta )=}
 
 the <a href="/facts/P-adic_valuation/wktvC3UP">p-adic valuation</a> of 
 
 
 
 π
 
 
 {\displaystyle \pi }
 
 in 
 
 
 
 Δ
 
 
 {\displaystyle \Delta }
 
, that is, exponent of 
 
 
 
 π
 
 
 {\displaystyle \pi }
 
 in prime factorization of 
 
 
 
 Δ
 
 
 {\displaystyle \Delta }
 
, or infinity if 
 
 
 
 Δ
 =
 0
 
 
 {\displaystyle \Delta =0}

a
          
            i
            ,
            m
          
        
        =
        
          a
          
            i
          
        
        
          /
        
        
          π
          
            m
          
        
      
    
    {\displaystyle a_{i,m}=a_{i}/\pi ^{m}}

b
          
            2
          
        
        =
        
          a
          
            1
          
          
            2
          
        
        +
        4
        
          a
          
            2
          
        
      
    
    {\displaystyle b_{2}=a_{1}^{2}+4a_{2}}

b
          
            4
          
        
        =
        
          a
          
            1
          
        
        
          a
          
            3
          
        
        +
        2
        
          a
          
            4

{\displaystyle b_{4}=a_{1}a_{3}+2a_{4}^{}}

b
          
            6
          
        
        =
        
          a
          
            3
          
          
            2
          
        
        +
        4
        
          a
          
            6
          
        
      
    
    {\displaystyle b_{6}=a_{3}^{2}+4a_{6}}

b
          
            8
          
        
        =
        
          a
          
            1
          
          
            2
          
        
        
          a
          
            6
          
        
        −
        
          a
          
            1
          
        
        
          a
          
            3
          
        
        
          a
          
            4
          
        
        +
        4
        
          a
          
            2
          
        
        
          a
          
            6
          
        
        +
        
          a
          
            2
          
        
        
          a
          
            3
          
          
            2
          
        
        −
        
          a
          
            4
          
          
            2
          
        
      
    
    {\displaystyle b_{8}=a_{1}^{2}a_{6}-a_{1}a_{3}a_{4}+4a_{2}a_{6}+a_{2}a_{3}^{2}-a_{4}^{2}}

c
          
            4
          
        
        =
        
          b
          
            2
          
          
            2
          
        
        −
        24
        
          b
          
            4
          
        
      
    
    {\displaystyle c_{4}=b_{2}^{2}-24b_{4}}

c
          
            6
          
        
        =
        −
        
          b
          
            2
          
          
            3
          
        
        +
        36
        
          b
          
            2
          
        
        
          b
          
            4
          
        
        −
        216
        
          b
          
            6
          
        
      
    
    {\displaystyle c_{6}=-b_{2}^{3}+36b_{2}b_{4}-216b_{6}}

Δ
        =
        −
        
          b
          
            2
          
          
            2
          
        
        
          b
          
            8
          
        
        −
        8
        
          b
          
            4
          
          
            3
          
        
        −
        27
        
          b
          
            6
          
          
            2
          
        
        +
        9
        
          b
          
            2
          
        
        
          b
          
            4
          
        
        
          b
          
            6
          
        
      
    
    {\displaystyle \Delta =-b_{2}^{2}b_{8}-8b_{4}^{3}-27b_{6}^{2}+9b_{2}b_{4}b_{6}}

j
        =
        
          c
          
            4
          
          
            3
          
        
        
          /
        
        Δ
        .
      
    
    {\displaystyle j=c_{4}^{3}/\Delta .}

<h2 id="the-algorithm">The algorithm</h2>
<ul><li>Step 1: If π does not divide Δ then the type is I0, c=1 and f=0.</li>
<li>Step 2: If π divides Δ but not c4 then the type is Iv with v = v(Δ), c=v, and f=1.</li>
<li>Step 3. Otherwise, change coordinates so that π divides a3,a4,a6. If π2 does not divide a6 then the type is II, c=1, and f=v(Δ);</li>
<li>Step 4. Otherwise, if π3 does not divide b8 then the type is III, c=2, and f=v(Δ)−1;</li>
<li>Step 5. Otherwise, let Q1 be the polynomial</li></ul>

Q
 
 1
 
 
 (
 Y
 )
 =
 
 Y
 
 2
 
 
 +
 
 a
 
 3
 ,
 1
 
 
 Y
 −
 
 a
 
 6
 ,
 2
 
 
 .
 
 
 {\displaystyle Q_{1}(Y)=Y^{2}+a_{3,1}Y-a_{6,2}.}
 
.
If π3 does not divide b6 then the type is IV, c=3 if 
 
 
 
 
 Q
 
 1
 
 
 (
 Y
 )
 
 
 {\displaystyle Q_{1}(Y)}
 
 has two roots in K and 1 if it has two roots outside of K, and f=v(Δ)−2.
<ul><li>Step 6. Otherwise, change coordinates so that π divides a1 and a2, π2 divides a3 and a4, and π3 divides a6. Let P be the polynomial</li></ul>

P
        (
        T
        )
        =
        
          T
          
            3
          
        
        +
        
          a
          
            2
            ,
            1
          
        
        
          T
          
            2
          
        
        +
        
          a
          
            4
            ,
            2
          
        
        T
        +
        
          a
          
            6
            ,
            3
          
        
        .
      
    
    {\displaystyle P(T)=T^{3}+a_{2,1}T^{2}+a_{4,2}T+a_{6,3}.}

If 
 
 
 
 P
 (
 T
 )
 
 
 {\displaystyle P(T)}
 
 has 3 distinct roots modulo π then the type is I0*, f=v(Δ)−4, and c is 1+(number of roots of P in K).
<ul><li>Step 7. If P has one single and one double root, then the type is Iν* for some ν>0, f=v(Δ)−4−ν, c=2 or 4: there is a "sub-algorithm" for dealing with this case.</li>
<li>Step 8. If P has a triple root, change variables so the triple root is 0, so that π2 divides a2 and π3 divides a4, and π4 divides a6. Let Q2 be the polynomial</li></ul>

Q
 
 2
 
 
 (
 Y
 )
 =
 
 Y
 
 2
 
 
 +
 
 a
 
 3
 ,
 2
 
 
 Y
 −
 
 a
 
 6
 ,
 4
 
 
 .
 
 
 {\displaystyle Q_{2}(Y)=Y^{2}+a_{3,2}Y-a_{6,4}.}
 
.
If 
 
 
 
 
 Q
 
 2
 
 
 (
 Y
 )
 
 
 {\displaystyle Q_{2}(Y)}
 
 has two distinct roots modulo π then the type is IV*, f=v(Δ)−6, and c is 3 if the roots are in K, 1 otherwise.
<ul><li>Step 9. If 
 
 
 
 
 Q
 
 2
 
 
 (
 Y
 )
 
 
 {\displaystyle Q_{2}(Y)}
 
 has a double root, change variables so the double root is 0. Then π3 divides a3 and π5 divides a6. If π4 does not divide a4 then the type is III* and f=v(Δ)−7 and c = 2.</li>
<li>Step 10. Otherwise if π6 does not divide a6 then the type is II* and f=v(Δ)−8 and c = 1.</li>
<li>Step 11. Otherwise the equation is not minimal. Divide each an by πn and go back to step 1.</li></ul>
<h2 id="implementations">Implementations</h2>
The algorithm is implemented for algebraic number fields in the <a href="/facts/PARI/GP/JhTL8ysP">PARI/GP</a> computer algebra system, available through the function elllocalred.

<ul><li>Cremona, John (1997), <a href="http://www.warwick.ac.uk/~masgaj/book/fulltext/index.html">Algorithms for modular elliptic curves</a> (2nd ed.), Cambridge: <a href="/facts/Cambridge_University_Press/fgEBSSRq">Cambridge University Press</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-521-59820-6, <a href="/facts/Zbl_(identifier)/P6rFxKKx">Zbl</a> <a href="https://zbmath.org/?format=complete&q=an:0872.14041">0872.14041</a>, retrieved 2007-12-20</li>
<li>Laska, Michael (1982), "An Algorithm for Finding a Minimal Weierstrass Equation for an Elliptic Curve", Mathematics of Computation, 38 (157): 257–260, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.2307%2F2007483">10.2307/2007483</a>, <a href="/facts/JSTOR_(identifier)/YTeVmaJ7">JSTOR</a> <a href="https://www.jstor.org/stable/2007483">2007483</a>, <a href="/facts/Zbl_(identifier)/P6rFxKKx">Zbl</a> <a href="https://zbmath.org/?format=complete&q=an:0493.14016">0493.14016</a></li>
<li><a href="/facts/Andr%C3%A9_N%C3%A9ron/Ky1SDn7w">Néron, André</a> (1964), <a href="http://www.numdam.org/item?id=PMIHES_1964__21__5_0">"Modèles minimaux des variétés abèliennes sur les corps locaux et globaux"</a>, <a href="/facts/Publications_Math%C3%A9matiques_de_l%27IH%C3%89S/2ur5ofxL">Publications Mathématiques de l'IHÉS</a> (in French), 21: 5–128, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF02684271">10.1007/BF02684271</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0179172">0179172</a>, <a href="/facts/Zbl_(identifier)/P6rFxKKx">Zbl</a> <a href="https://zbmath.org/?format=complete&q=an:0132.41403">0132.41403</a></li>
<li><a href="/facts/Joseph_H._Silverman/acyPld7K">Silverman, Joseph H.</a> (1994), Advanced Topics in the Arithmetic of Elliptic Curves, <a href="/facts/Graduate_Texts_in_Mathematics/VTIfY29j">Graduate Texts in Mathematics</a>, vol. 151, <a href="/facts/Springer-Verlag/nAesf6nT">Springer-Verlag</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-387-94328-5, <a href="/facts/Zbl_(identifier)/P6rFxKKx">Zbl</a> <a href="https://zbmath.org/?format=complete&q=an:0911.14015">0911.14015</a></li>
<li><a href="/facts/John_Tate_(mathematician)/nBntLCG0">Tate, John</a> (1975), "Algorithm for determining the type of a singular fiber in an elliptic pencil", in <a href="/facts/Bryan_John_Birch/QVWLhz0w">Birch, B.J.</a>; Kuyk, W. (eds.), Modular Functions of One Variable IV, Lecture Notes in Mathematics, vol. 476, Berlin / Heidelberg: Springer, pp. 33–52, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBFb0097582">10.1007/BFb0097582</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-540-07392-5, <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/1617-9692">1617-9692</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0393039">0393039</a>, <a href="/facts/Zbl_(identifier)/P6rFxKKx">Zbl</a> <a href="https://zbmath.org/?format=complete&q=an:1214.14020">1214.14020</a></li></ul>

Tate's algorithm open-in-new

Tate's algorithm