# 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 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 thecolumnsof 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.