# 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

edit retag close merge delete

Could you please provide the code to construct f, Fr, W ?

1

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.

1

Technical hints: x = GFX.gen(), q = GFX.base_ring().cardinality(); then you can do basic_image = GFX_quo_f(x^(q*k) - x^k) and such an element in the quotient can be converted to a list or a vector (try vector(basic_image)), which you can use to construct a matrix, on which you can call the method right_kernel().

By trying basic debugging you see the big scary error comes from GFX(h). Here you are expecting GFX 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 is h.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.

Sort by » oldest newest most voted

Thanks to the kind and patient help of @rburing this finally seems to be working!

vector2poly = lambda h: reduce(lambda a,b:a+b, [ci*x^i for i,ci in enumerate(h)])

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).transpose().right_kernel().basis()
H = [h.lift() for h in H]
H = map(vector2poly, [h.lift() for h in H])
return H

more

1

Well done. Note that vector2poly uses x from global scope (which may cause problems if you use different polynomial rings); you might want to pass x as an argument instead. Also reduce(lambda a,b: a+b, ...) is usually denoted sum(...).