Sharedgröbner basis calculations / Calculations for p = 3.sagewsOpen in CoCalc
Gröbner Basis Calculations for $p=3$
#E is an elliptic curve defined by E : f = 0 over QQ_3
#Aim: Find (f,fx,fy) \cap <1,x,x2>_ZZ[a1,a2,a3,a4,a6]
#Note: we do calculations over $ZZ$ and later use the fact that we are actually over ZZ_p with p = 3
from sage.rings.polynomial.toy_d_basis import d_basis
R.<y,x,a1,a2,a3,a4,a6> = PolynomialRing(ZZ, 7, order = 'lex(2),deglex(5)')
#y^2>x*y>y>...>x^2>x
#As p=3, we may assume that a1 = a3 = 0
f = y^2 - x^3 -a2*x^2- a4*x - a6
fx = f.derivative(x)
fy = f.derivative(y)
I = R.ideal(f,fx,fy)
#d_basis calculates a D-Gröbner Basis of I
I_gb = d_basis(I); I_gb

[y^2 + 2*x*a2^2 - 6*x*a4 + a2*a4 - 9*a6, y*x^2 + y*a4, 2*y, x^3 - x*a4 - 2*a6, x^2*a2 + 2*x*a2^2 - 4*x*a4 + a2*a4 - 6*a6, x^2*a4 + 6*x*a6 + 4*a2*a6 - a4^2, -3*x^2 - 2*x*a2 - a4, 4*x*a4^3 - 108*x*a6^2 - 8*a2^2*a4*a6 + 2*a2*a4^3 - 72*a2*a6^2 + 30*a4^2*a6, 4*x*a2^2 - 12*x*a4 + 2*a2*a4 - 18*a6, 2*x*a2*a4 - 18*x*a6 - 12*a2*a6 + 4*a4^2, 12*x*a2*a6 - 4*x*a4^2 + 8*a2^2*a6 - 2*a2*a4^2 - 6*a4*a6, 8*a2^3*a6 - 2*a2^2*a4^2 - 36*a2*a4*a6 + 8*a4^3 + 54*a6^2]
#We want to find I \cap <1,x,x^2>, so we:
#(1) leave out terms with higher leading monomials of I_gb
#(2) add terms of the form x^i*g < x^3 for g in I_neu
I_neu = I_gb[4:]
for el in I_neu:
if (x*el).lm() < x^3:
if x*el not in I_neu:
I_neu.append(x*el)
if (x^2*el).lm() < x^3:
if x^2*el not in I_neu:
I_neu.append(x^2*el)


#But we need only the first three elements of I_neu to generate <1,x,x^2> \cap I as a ZZ[a2,a4,a6] module.
generators = I_neu[:3]; generators
#We have to do calculations over QQ[x,y] so that we can calculate lifts of the elements in I_neu
R.<y,x,a1,a2,a3,a4,a6> = PolynomialRing(QQ, order = 'lex(2),deglex(5)')
I_neu=[R(el) for el in I_neu]
generators = [R(el) for el in generators]

#Check that I_neu[:3] generates I_neu
#The coefficients for the lifts of the elements in I_neu are stored in the list "coeff"
I_test = R.ideal(generators)
coeff = []
for el in I_neu:
if el in I_test:
lift = el.lift(I_test); #lift
coeff.append(lift)
else:
print 'not in ideal'
#This means I_neu[i] = sum_{j=0}^{3} coeff[i][j]*generators[j] for each i

[x^2*a2 + 2*x*a2^2 - 4*x*a4 + a2*a4 - 6*a6, x^2*a4 + 6*x*a6 + 4*a2*a6 - a4^2, -3*x^2 - 2*x*a2 - a4]
#The coefficients are elements of QQ[x,y,a1,a2,a3,a4,a6]. We have to check that they are actually in ZZ_3[a1,a2,a3,a4,a6]. That is for each element: 3 does not divide its denominator and the leading monomial is in QQ[a1,a2,a3,a4,a6]
for i in range(len(coeff)):
for poly in coeff[i]:
if 3.divides(poly.denominator()) or not poly.lm() < x:
print 'non-integral lift', i, poly

non-integral lift 13 3*x*a2*a4 - 6*a2*a6 + 2*a4^2 non-integral lift 13 x*a2*a4^2 - 4*a2^3*a6 + 17*a2*a4*a6 - 2*a4^3 - 18*a6^2
#We see that the "lift" function has calculated  a non-integral lift for the element I_neu[13].
I_neu[13]
coeff[13]
#But lifts are not unique. There is an integral lift:
lift_neu = [-4*a2^2*a6 + a2*a4^2 + 3*a4*a6, -6*a2*a6 + 2*a4^2, -4*a2^3*a6 + a2^2*a4^2 + 11*a2*a4*a6 - 2*a4^3 - 18*a6^2]
sum([lift_neu[i]*generators[i] for i in range(3)]) == I_neu[13]

8*x^2*a2^3*a6 - 2*x^2*a2^2*a4^2 - 36*x^2*a2*a4*a6 + 8*x^2*a4^3 + 54*x^2*a6^2 [-4*a2^2*a6 + 3*a4*a6, 3*x*a2*a4 - 6*a2*a6 + 2*a4^2, x*a2*a4^2 - 4*a2^3*a6 + 17*a2*a4*a6 - 2*a4^3 - 18*a6^2] True