Let $f\in GF_{q}[x]$ be a squarefree univariate polynomial with coefficients in a finite field, and $\bar{Fr}: \frac{F_q}{(f)}\to \frac{F_q}{(f)}: \bar h \mapsto \bar h^q$ the Frobenius application over $GF_q$ elevated to the cocient $\frac{F_q}{(f)}$.
Then we can see $\frac{F_q}{(f)}$ as a vector space over $GF_q$, and the space of fixed points of $\bar{Fr}$, that is $W = {\bar h \in \frac{F_q}{(f)} : \bar h ^q = q }$ is a linear subspace.
The question: how do I compute the basis of $W$ in sagemath?
EDIT:
Inspired by @rburing I wrote some (incomplete) code:
def berlekamp_basis(f):
"""
INPUT: f a monic squarefree polynomial in F_q[x]
OUTPUT: a list of polynomials hi in F_q[x] that represent
a basis of the Berlekamp algebra associated to f
"""
n = f.degree()
GFX = f.parent()
GFX_quo_f = GFX.quotient(f)
g = []
for k in range(n):
basic_image = GFX(GFX_quo_f(x)^(q*k)) - GFX(x)^k
g.append(basic_image)
H = ???
return H
So I have collected in g the images of a basis of GFX_quo_f under $\bar {Fr} - \bar {id}$. How do I compel sagemath to use this information to compute the kernel of this linear application?
EDIT 2:
Following the technical hints from @rburing below, I scrapped together this code:
def berlekamp_basis(f):
"""
INPUT: f a monic squarefree polynomial in F_q[x]
OUTPUT: a list of polynomials hi in F_q[x] that represent
a basis of the Berlekamp algebra associated to f
"""
n = f.degree()
GFX = f.parent()
x = GFX.gen()
q = GFX.base().order()
GFX_quo_f = GFX.quotient(f)
g = []
for k in range(n):
basic_image = GFX_quo_f(x^(q*k)- x^k)
g.append(vector(basic_image))
H = matrix(g).right_kernel().basis()
H = [GFX(h) for h in H]
return H
When I run the following test:
GF9.<a> = GF(3^2)
GF9X.<x> = GF9[x]
f = x**3 + x**2 + x - a
assert(f.is_squarefree())
berlekamp_basis(f)
I get a big scary error:
Error in lines 42-42
Traceback (most recent call last):
File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1188, in execute
flags=compile_flags) in namespace, locals
File "", line 1, in <module>
File "", line 17, in berlekamp_basis
File "sage/structure/parent.pyx", line 921, in sage.structure.parent.Parent.__call__ (build/cythonized/sage/structure/parent.c:9679)
return mor._call_(x)
File "sage/structure/coerce_maps.pyx", line 145, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (build/cythonized/sage/structure/coerce_maps.c:4574)
raise
File "sage/structure/coerce_maps.pyx", line 140, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (build/cythonized/sage/structure/coerce_maps.c:4442)
return C._element_constructor(x)
File "/ext/sage/sage-8.4_1804/local/lib/python2.7/site-packages/sage/rings/polynomial/polynomial_ring.py", line 460, in _element_constructor_
return C(self, x, check, is_gen, construct=construct, **kwds)
File "sage/rings/polynomial/polynomial_zz_pex.pyx", line 145, in sage.rings.polynomial.polynomial_zz_pex.Polynomial_ZZ_pEX.__init__ (build/cythonized/sage/rings/polynomial/polynomial_zz_pex.cpp:15712)
Polynomial_template.__init__(self, parent, x, check, is_gen, construct)
File "sage/rings/polynomial/polynomial_template.pxi", line 176, in sage.rings.polynomial.polynomial_zz_pex.Polynomial_template.__init__ (build/cythonized/sage/rings/polynomial/polynomial_zz_pex.cpp:8595)
x = parent.base_ring()(x)
File "sage/structure/parent.pyx", line 921, in sage.structure.parent.Parent.__call__ (build/cythonized/sage/structure/parent.c:9679)
return mor._call_(x)
File "sage/structure/coerce_maps.pyx", line 145, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (build/cythonized/sage/structure/coerce_maps.c:4574)
raise
File "sage/structure/coerce_maps.pyx", line 140, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (build/cythonized/sage/structure/coerce_maps.c:4442)
return C._element_constructor(x)
File "/ext/sage/sage-8.4_1804/local/lib/python2.7/site-packages/sage/rings/finite_rings/finite_field_givaro.py", line 370, in _element_constructor_
return self._cache.element_from_data(e)
File "sage/rings/finite_rings/element_givaro.pyx", line 318, in sage.rings.finite_rings.element_givaro.Cache_givaro.element_from_data (build/cythonized/sage/rings/finite_rings/element_givaro.cpp:7809)
cpdef FiniteField_givaroElement element_from_data(self, e):
File "sage/rings/finite_rings/element_givaro.pyx", line 407, in sage.rings.finite_rings.element_givaro.Cache_givaro.element_from_data (build/cythonized/sage/rings/finite_rings/element_givaro.cpp:6166)
raise TypeError("e.parent must match self.vector_space")
TypeError: e.parent must match self.vector_space
