Field extensions

Example 1, splitting field over Q

# Polynomial in Q[x]
var('x')
R.<x> = QQ[]
f = R(x^3 -7*x +7)

f.factor()

x^3 - 7*x + 7

# E = field simple field extension
E = R.quotient_by_principal_ideal(ideal(f))
E

Univariate Quotient Polynomial Ring in xbar over Rational Field with modulus x^3 - 7*x + 7

E.is_field()

True

alpha = E(x)
alpha

xbar

alpha.minpoly()

x^3 - 7*x + 7

F = f.change_ring(E)
F

x^3 - 7*x + 7

# S = E[x]
S=F.parent()
S

Univariate Polynomial Ring in x over Univariate Quotient Polynomial Ring in xbar over Rational Field with modulus x^3 - 7*x + 7

F.factor()

(x - xbar) * (x - 3*xbar^2 - 4*xbar + 14) * (x + 3*xbar^2 + 5*xbar - 14)

# So f(x) splits over E

E.degree()

f.discriminant()

Example 2, another splitting field over Q

# Change the example slightly
var('x')
R.<x> = QQ[]
f = R(x^3 -7*x +8)
f.discriminant()

-356

# E = field simple field extension
E = R.quotient_by_principal_ideal(ideal(f))
E

Univariate Quotient Polynomial Ring in xbar over Rational Field with modulus x^3 - 7*x + 8

alpha = E(x)
alpha

xbar

alpha.minpoly()

x^3 - 7*x + 8

F = f.change_ring(E)
F

x^3 - 7*x + 8

# S = E[x]
S=F.parent()
S

Univariate Polynomial Ring in x over Univariate Quotient Polynomial Ring in xbar over Rational Field with modulus x^3 - 7*x + 8

F.factor()

(x - xbar) * (x^2 + xbar*x + xbar^2 - 7)

# So f does not split over E

g = F.factor()[1][0]
g

x^2 + xbar*x + xbar^2 - 7

K = S.quotient_by_principal_ideal(ideal(g))
K

Univariate Quotient Polynomial Ring in xbar over Univariate Quotient Polynomial Ring in xbar over Rational Field with modulus x^3 - 7*x + 8 with modulus x^2 + xbar*x + xbar^2 - 7

K.is_field()

True

F2 = f.change_ring(K)
F2
G = g.change_ring(K)
F2, G

(x^3 - 7*x + 8, x^2 + xbar*x + xbar^2 - 7)

# does not work
F2.factor()

---------------------------------------------------------------------------
NotImplementedError                       Traceback (most recent call last)
/tmp/ipykernel_1906302/2714016358.py in <cell line: 2>()
      1 # does not work
----> 2 F2.factor()

~/.conda/envs/sage/lib/python3.9/site-packages/sage/rings/polynomial/polynomial_element.pyx in sage.rings.polynomial.polynomial_element.Polynomial.factor (build/cythonized/sage/rings/polynomial/polynomial_element.c:35912)()
   4348         R = self._parent.base_ring()
   4349         if hasattr(R, '_factor_univariate_polynomial'):
-> 4350             return R._factor_univariate_polynomial(self, **kwargs)
   4351 
   4352         G = None

~/.conda/envs/sage/lib/python3.9/site-packages/sage/rings/polynomial/polynomial_quotient_ring.py in _factor_univariate_polynomial(self, f)
   1800             return Factorization([(f,1)], unit=unit)
   1801         else:
-> 1802             from_isomorphic_ring, to_isomorphic_ring, isomorphic_ring = self._isomorphic_ring()
   1803             g = f.map_coefficients(to_isomorphic_ring)
   1804             F = g.factor()

~/.conda/envs/sage/lib/python3.9/site-packages/sage/misc/cachefunc.pyx in sage.misc.cachefunc.CachedMethodCallerNoArgs.__call__ (build/cythonized/sage/misc/cachefunc.c:12999)()
   2308         if self.cache is None:
   2309             f = self.f
-> 2310             self.cache = f(self._instance)
   2311         return self.cache
   2312 

~/.conda/envs/sage/lib/python3.9/site-packages/sage/rings/polynomial/polynomial_quotient_ring.py in _isomorphic_ring(self)
   1862 
   1863             # recursively try to rewrite the isomorphic_quotient
-> 1864             isomorphic_ring_to_isomorphic_quotient, isomorphic_quotient_to_isomorphic_ring, isomorphic_ring = isomorphic_quotient._isomorphic_ring()
   1865 
   1866             # the process has likely refined the category of

~/.conda/envs/sage/lib/python3.9/site-packages/sage/misc/cachefunc.pyx in sage.misc.cachefunc.CachedMethodCallerNoArgs.__call__ (build/cythonized/sage/misc/cachefunc.c:12999)()
   2308         if self.cache is None:
   2309             f = self.f
-> 2310             self.cache = f(self._instance)
   2311         return self.cache
   2312 

~/.conda/envs/sage/lib/python3.9/site-packages/sage/rings/polynomial/polynomial_quotient_ring.py in _isomorphic_ring(self)
   1955                 return from_isomorphic_ring, to_isomorphic_ring, isomorphic_ring
   1956 
-> 1957         raise NotImplementedError("cannot rewrite %r as an isomorphic ring"%(self,))
   1958 
   1959     def _test_isomorphic_ring(self, **options):

NotImplementedError: cannot rewrite Univariate Quotient Polynomial Ring in xbar over Number Field in xbar with defining polynomial x^3 - 7*x + 8 with modulus x^2 + xbar*x + xbar^2 - 7 as an isomorphic ring

# This works:
L.<y> = NumberField(f)
L

Number Field in y with defining polynomial x^3 - 7*x + 8

L.degree()

F = f.change_ring(L)
F.factor()

(x - y) * (x^2 + y*x + y^2 - 7)

g = F.factor()[1][0]
g

x^2 + y*x + y^2 - 7

K.<z> = L.extension(g)
K

Number Field in z with defining polynomial x^2 + y*x + y^2 - 7 over its base field

K.relative_degree()

K.absolute_degree()

FF = f.change_ring(K)
FF

x^3 - 7*x + 8

FF.factor()

(x - z) * (x - y) * (x + z + y)

# Cheat:
SF.<u> = f.splitting_field()
SF

Number Field in u with defining polynomial x^6 + 253*x^4 + 16*x^3 + 23812*x^2 - 4384*x + 820288

f.change_ring(SF).factor()

(x - 5/14952*u^5 + 1/3738*u^4 - 279/4984*u^3 + 517/3738*u^2 - 5374/1869*u + 3232/267) * (x + 121/2810976*u^5 + 1/702744*u^4 + 11495/936992*u^3 + 769/702744*u^2 + 527713/702744*u - 3007/25098) * (x + 39/133856*u^5 - 9/33464*u^4 + 5851/133856*u^3 - 4665/33464*u^2 + 71091/33464*u - 100267/8366)

Extensions of finite fields

Z2 = GF(2)
R.<x> = Z2[]
f=x^3+x+1
f.factor()

x^3 + x + 1

F = GF(2^3,name='a',modulus=f)
F

Finite Field in a of size 2^3

for b in F:
    print(b)

0
a
a^2
a + 1
a^2 + a
a^2 + a + 1
a^2 + 1
1

fl = f.change_ring(F)
fl

x^3 + x + 1

# f splits in F
fl.factor()

(x + a) * (x + a^2) * (x + a^2 + a)

# We study the difference eqn s(n+3) = s(n+1)+s(n), s(0)=1, s(1)=s(2)=0

# method 1, direct
def s(n):
    if (n==0):
        return Z2(1)
    elif(n==1):
        return Z2(0)
    elif(n==2):
        return Z2(0)
    else:
        return(Z2(s(n-2)+s(n-3)))

[(n,s(n)) for n in range(20)]

[(0, 1),
 (1, 0),
 (2, 0),
 (3, 1),
 (4, 0),
 (5, 1),
 (6, 1),
 (7, 1),
 (8, 0),
 (9, 0),
 (10, 1),
 (11, 0),
 (12, 1),
 (13, 1),
 (14, 1),
 (15, 0),
 (16, 0),
 (17, 1),
 (18, 0),
 (19, 1)]

# Periodic with period 2^3-1, as expected

# Method 2: images in the quotient
a=F.gen()
a,a^12

(a, a^2 + a + 1)

[(n,a^n) for n in range(20)]

[(0, 1),
 (1, a),
 (2, a^2),
 (3, a + 1),
 (4, a^2 + a),
 (5, a^2 + a + 1),
 (6, a^2 + 1),
 (7, 1),
 (8, a),
 (9, a^2),
 (10, a + 1),
 (11, a^2 + a),
 (12, a^2 + a + 1),
 (13, a^2 + 1),
 (14, 1),
 (15, a),
 (16, a^2),
 (17, a + 1),
 (18, a^2 + a),
 (19, a^2 + a + 1)]

# What are the  constant terms?
R.<a> = Z2[]
R(F.gen()^10)

a + 1

R(F.gen()^10).subs(a=0)

[(n,R(F.gen()^n).subs(a=0)) for n in range(20)]

[(0, 1),
 (1, 0),
 (2, 0),
 (3, 1),
 (4, 0),
 (5, 1),
 (6, 1),
 (7, 1),
 (8, 0),
 (9, 0),
 (10, 1),
 (11, 0),
 (12, 1),
 (13, 1),
 (14, 1),
 (15, 0),
 (16, 0),
 (17, 1),
 (18, 0),
 (19, 1)]

# Method 3: mult with a is a linear map, find its matrix
A = companion_matrix(f)
A

[0 0 1]
[1 0 1]
[0 1 0]

v = vector([Z2(1),Z2(0),Z2(0)])
v

(1, 0, 0)

# read first component
[(n,A^n*v) for n in range(20)]

[(0, (1, 0, 0)),
 (1, (0, 1, 0)),
 (2, (0, 0, 1)),
 (3, (1, 1, 0)),
 (4, (0, 1, 1)),
 (5, (1, 1, 1)),
 (6, (1, 0, 1)),
 (7, (1, 0, 0)),
 (8, (0, 1, 0)),
 (9, (0, 0, 1)),
 (10, (1, 1, 0)),
 (11, (0, 1, 1)),
 (12, (1, 1, 1)),
 (13, (1, 0, 1)),
 (14, (1, 0, 0)),
 (15, (0, 1, 0)),
 (16, (0, 0, 1)),
 (17, (1, 1, 0)),
 (18, (0, 1, 1)),
 (19, (1, 1, 1))]

# method 4: general formula
# s(n) = c0*r0^n + c1*r1^n + c2*r2^n

r=fl.roots()
r

[(a, 1), (a^2, 1), (a^2 + a, 1)]

r0 = r[0][0]
r1=r[1][0]
r2 = r[2][0]
r0,r1,r2

(a, a^2, a^2 + a)

R.<c0,c1,c2> = F[]

Multivariate Polynomial Ring in c0, c1, c2 over Finite Field in a of size 2^3

I = ideal(c0*1+ c1*1+c2*1-1, c0*r0 + c1*r1+c2*r2-0, c0*r0^2 + c1*r1^2 + c2*r2^2-0)
I

Ideal (c0 + c1 + c2 + 1, a*c0 + (a^2)*c1 + (a^2 + a)*c2, (a^2)*c0 + (a^2 + a)*c1 + a*c2) of Multivariate Polynomial Ring in c0, c1, c2 over Finite Field in a of size 2^3

I.variety()

[{c2: 1, c1: 1, c0: 1}]

[(n,1*r0^n+1*r1^n + 1*r2^n) for n in range(20)]

[(0, 1),
 (1, 0),
 (2, 0),
 (3, 1),
 (4, 0),
 (5, 1),
 (6, 1),
 (7, 1),
 (8, 0),
 (9, 0),
 (10, 1),
 (11, 0),
 (12, 1),
 (13, 1),
 (14, 1),
 (15, 0),
 (16, 0),
 (17, 1),
 (18, 0),
 (19, 1)]

# Method 4: formal power series
fl

x^3 + x + 1

R=fl.parent()
R

Univariate Polynomial Ring in x over Finite Field in a of size 2^3

fr = (x-1/r0)*(x-1/r1)*(x-1/r2)
fr

x^3 + x^2 + 1

S.<x> = PowerSeriesRing(F)
S

Power Series Ring in x over Finite Field in a of size 2^3

S(1/fr)

1 + x^2 + x^3 + x^4 + x^7 + x^9 + x^10 + x^11 + x^14 + x^16 + x^17 + x^18 + O(x^20)

# s(n) is one for 0,3,5,6,7,10,12,13,14,17,19...

G=fr.parent()((1+x^2))/fr
G

(x^2 + 1)/(x^3 + x^2 + 1)

S(G)

1 + x^3 + x^5 + x^6 + x^7 + x^10 + x^12 + x^13 + x^14 + x^17 + x^19 + O(x^20)

G.partial_fraction_decomposition()

(0,
 [(a + 1)/(x + a + 1),
  (a^2 + 1)/(x + a^2 + 1),
  (a^2 + a + 1)/(x + a^2 + a + 1)])

# Explicit formula for generating function

# Given initial segment, we can guess general sequence

def partialseries(n):
    return(add(s(k)*S(x^k) for k in range(n)))

partialseries(10)

1 + x^3 + x^5 + x^6 + x^7

# now we guess...
p10=partialseries(10)
p10.pade(3,3)

(x^2 + 1)/(x^3 + x^2 + 1)

#already correct!

# Larger example, mod 3
Z3 = GF(3)
R.<t> = Z3[]
f = t^5+2*t+1
f.factor()

t^5 + 2*t + 1

F = GF(3^5,name='a',modulus=f)
F

Finite Field in a of size 3^5

A = companion_matrix(f)
A

[0 0 0 0 2]
[1 0 0 0 1]
[0 1 0 0 0]
[0 0 1 0 0]
[0 0 0 1 0]

#initial conditions
v = vector([Z3(1),Z3(0),Z3(0),Z3(1),Z3(1)])
v

(1, 0, 0, 1, 1)

# probably periodic with period 3^5 -1, to large to list
[(A^n*v)[0] for n in range(20)]

[1, 2, 2, 0, 0, 1, 0, 1, 0, 1, 2, 1, 2, 1, 1, 2, 1, 2, 0, 1]

S.<x> = PowerSeriesRing(F)

partial20 = add([x^n*(A^n*v)[0] for n in range(20)])
partial20

1 + 2*x + 2*x^2 + x^5 + x^7 + x^9 + 2*x^10 + x^11 + 2*x^12 + x^13 + x^14 + 2*x^15 + x^16 + 2*x^17 + x^19

S(partial20).pade(3,3)

(2*x^3 + x^2 + 2*x + 1)/(x^3 + 2*x^2 + 1)

t^5 + 2*t + 1

S(add([x^n*(A^n*v)[0] for n in range(40)])).pade(3,3)

(2*x^3 + x^2 + 2*x + 1)/(x^3 + 2*x^2 + 1)

S(add([x^n*(A^n*v)[0] for n in range(40)])).pade(4,4)

(2*x^3 + x^2 + 2*x + 1)/(x^3 + 2*x^2 + 1)

probablytrueres = S(add([x^n*(A^n*v)[0] for n in range(40)])).pade(4,4)
probablytrueres.partial_fraction_decomposition()

(2, [(2*x + 2)/(x^3 + 2*x^2 + 1)])

pfn=probablytrueres.numerator().change_ring(F)
pfn

2*x^3 + x^2 + 2*x + 1

pfd=probablytrueres.denominator().change_ring(F)
pfd

x^3 + 2*x^2 + 1

pfn.change_ring(F)

2*x^3 + x^2 + 2*x + 1

(pfn.change_ring(F)/pfd.change_ring(F)).partial_fraction_decomposition()

(2, [(2*x + 2)/(x^3 + 2*x^2 + 1)])

Finite Field in a of size 3^5

pfd.change_ring(F).factor()

x^3 + 2*x^2 + 1

G.<c> = pfd.splitting_field()
G

Finite Field in c of size 3^15

(pfn.change_ring(G)/pfd.change_ring(G)).partial_fraction_decomposition()

(2,
 [(2*c^14 + c^13 + c^12 + 2*c^11 + c^10 + 2*c^9 + 2*c^8 + 2*c^7 + 2*c^4 + 2*c + 2)/(x + c^13 + 2*c^12 + c^9 + c^8 + 2*c^6 + 2*c^5 + c^3 + 2*c + 2),
  (2*c^14 + c^13 + c^12 + 2*c^11 + c^10 + 2*c^9 + 2*c^8 + 2*c^7 + 2*c^4 + 2*c)/(x + c^14 + c^12 + c^11 + 2*c^10 + 2*c^9 + 2*c^8 + c^7 + 2*c^6 + 2*c^5 + c^4 + c^3),
  (2*c^14 + c^13 + c^12 + 2*c^11 + c^10 + 2*c^9 + 2*c^8 + 2*c^7 + 2*c^4 + 2*c + 1)/(x + 2*c^14 + 2*c^13 + 2*c^11 + c^10 + 2*c^7 + 2*c^6 + 2*c^5 + 2*c^4 + c^3 + c)])

# This is your "explicit" formula...