Polynomial modulus in QuotientRing

edit

We cannot separate sage from math. So we have to do the work in both worlds.

The algebraic construction in the exercise is to first construct the ring $R=\mathbb{Z}[x]$, then to pass to the quotient $S = R/(x^8+1)$, here we consider the (class of) $3x^5 + 3x^4 + 2x^3 + 3x^2 + x + 2$, and mod out with respect to it too.

Then it is a good idea to mod out directly with respect to the two polynomials. In sage:

R.<x> = PolynomialRing( ZZ )
f = x^8 +1
g = 3*x^5 + 3*x^4 + 2*x^3 + 3*x^2 + x + 2
J = R.ideal( f, g )
S = R.quotient( J )

This is a finite ring, but the corresponding methods are not implemented. So we have to do the work on the theoretical side first. It is known, that the ideal $J$ is related to the resultant of $f$ and $g$. Since it is a short game to pop it up by using the euclidian algorithm in $R$, we will do play it. But in order to do this, we pass to rationals. (Else sage will not do much with f % g , and we need the rest.)

RQ.<x> = PolynomialRing( QQ )
f = x^8 +1
g = 3*x^5 + 3*x^4 + 2*x^3 + 3*x^2 + x + 2
J = RQ.ideal( f, g )
SQ = RQ.quotient( J )

print "SQ is", SQ
print "J is (over QQ) the ideal", J

r = f; s = g
while r.degree() > 0:
    r, s = s, r % s
    print "r = %s and s = %s" % ( r, s )

And we get:

SQ is Univariate Quotient Polynomial Ring in xbar over Rational Field with modulus 1
J is (over QQ) the ideal Principal ideal (1) of Univariate Polynomial Ring in x over Rational

And for the euclidean algorithm:

r = 3*x^5 + 3*x^4 + 2*x^3 + 3*x^2 + x + 2 and s = 10/9*x^4 - 2/9*x^3 + 11/9*x^2 + 13/9
r = 10/9*x^4 - 2/9*x^3 + 11/9*x^2 + 13/9 and s = -29/50*x^3 - 24/25*x^2 - 29/10*x - 67/25
r = -29/50*x^3 - 24/25*x^2 - 29/10*x - 67/25 and s = -775/841*x^2 + 150/29*x + 9225/841
r = -775/841*x^2 + 150/29*x + 9225/841 and s = -803996/24025*x - 253982/4805
r = -803996/24025*x - 253982/4805 and s = 96124025/192155044
r = 96124025/192155044 and s = 0

We had to introduce denominators, but it is clear how to multiply with them in each line, in order to get an operation over integers. It may happen, that some denominators "loose or win factors on the road", but the message is clear - say - up to inverting 192155044. The intermediate result in the line with r = -803996/24025x - 253982/4805 tells us, that $x$ may be replaced by the solution of the equation r=0 (for this r). We store the result x == (-755/478) obtained from: var( 'x' ); solve( -803996/24025x - 253982/4805 == 0, x )

The elegant way of doing the computations is by requiring directly:

sage: q, u, v = f.xgcd( g )    # gcd with u, v such that uf + gv is the gcd.

sage: u, v
(-717/4001*x^4 + 831/8002*x^3 - 3047/8002*x^2 - 1769/8002*x + 4276/4001,
 239/4001*x^7 - 755/8002*x^6 + 726/4001*x^5 - 837/8002*x^4 - 1193/4001*x^3 + 1425/8002*x^2 + 511/4001*x - 275/8002)

sage: U, V = u * 8002, v * 8002
sage: U, V
(-1434*x^4 + 831*x^3 - 3047*x^2 - 1769*x + 8552,
 478*x^7 - 755*x^6 + 1452*x^5 - 837*x^4 - 2386*x^3 + 1425*x^2 + 1022*x - 275)

sage: U * f + V * g
8002

We may be also interested to see:

sage: f.resultant( g ).factor()
2^2 * 4001

So which number should we trust? 2 * 4001 or rather 2^2 * 4001 ? Which are the invariant factors of the quotient, seen as a torsion module over integers. (Ignoring the ring structure first.) We will show in a second that $S$ is isomorphic as a module to $(\mathbb{Z}/2)^2\times (\mathbb{Z}/4001)$.

The map to the first copy factors as $S=\mathbb{Z}[x]/(f,g)\to (\mathbb{Z}/2)[x]/(f,g) \cong \mathbb{F}_2[x]/(x+1)^2$. To see this, we ask sage for...

R2.<x> = PolynomialRing( GF(2) )
f = x^8 +1
g = 3*x^5 + 3*x^4 + 2*x^3 + 3*x^2 + x + 2
print "f modulo 2 is %s ." % factor( f )
print "g modulo 2 is %s ." % factor( g )
print "GF(2)[ x ] is a UFD, so the gcd is seen to be: %s" % f.gcd(g).factor()

And we get:

f modulo 2 is (x + 1)^8 .
g modulo 2 is x * (x + 1)^2 * (x^2 + x + 1) .
GF(2)[ x ] is a UFD, so the gcd is seen to be: (x + 1)^2

And in a parallel manner:

R4001.<x> = PolynomialRing( GF(4001) )
f = x^8 +1
g = 3*x^5 + 3*x^4 + 2*x^3 + 3*x^2 + x + 2
print "f modulo 4001 is %s ." % factor( f )
print "g modulo 4001 is %s ." % factor( g )
print "GF(4001)[ x ] is a UFD, so the gcd is seen to be: %s" % f.gcd(g).factor()

And we get:

f modulo 4001 is (x + 1115) * (x + 1413) * (x + 1866) * (x + 1970) * (x + 2031) * (x + 2135) * (x + 2588) * (x + 2886) .
g modulo 4001 is (3) * (x + 2588) * (x^4 + 1414*x^3 + 150*x^2 + 3899*x + 1244) .
GF(4001)[ x ] is a UFD, so the gcd is seen to be: x + 2588

So we can write down a (ring) map from $S$ to $\mathbb{F_2}[x]/(x+1)^2\times \mathbb{F}_{4001}[x]/(x+2588)= \mathbb{F_2}[x]/(x+1)^2\times \mathbb{F}_{4001}$, induced by sending $x$ to (the class of) the element $(\qquad x\mod (x+1)^2\mathbb{F}_2[x]\qquad ,\qquad -2588\qquad )$.

And we can further sent this element to $\mathbb{Z}/2\times \mathbb{Z}/4001\cong \mathbb{Z}/8002$, the composition being $x\to(-1,-2588) \cong 1413$. Note also the "coincidence":

sage: Mod( (-755/478), 4001 )
1413