Computing the basis of the Frobenius function fixed point space
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
Could you please provide the code to construct f, Fr, W ?
Hint: a basis of $\mathbb{F}_q[x]/(f)$ is $1, x, \ldots, x^{\deg(f)-1}$ and you can write the linear map as a matrix, so you just have to do linear algebra over $\mathbb{F}_q$. For reference, this is part of Berlekamp's algorithm and $W$ is called the Berlekamp subalgebra.
Technical hints:
x = GFX.gen()
,q = GFX.base_ring().cardinality()
; then you can dobasic_image = GFX_quo_f(x^(q*k) - x^k)
and such an element in the quotient can be converted to alist
or avector
(tryvector(basic_image)
), which you can use to construct amatrix
, on which you can call the methodright_kernel()
.By trying basic debugging you see the big scary error comes from
GFX(h)
. Here you are expectingGFX
to understand that the element you passed belongs to a quotient and you want to lift it, which is kind of a tall order. Instead what works ish.lift()
. Furthermore note that by computing images of basis vectors you construct the columns of the matrix, so you want to either add a.transpose()
somewhere or construct the matrix differently. When you get it working, feel free to post it as an answer.