Ask Your Question
2

Computing the basis of the Frobenius function fixed point space

asked 2018-11-18 10:42:36 +0100

Jsevillamol gravatar image

updated 2018-11-18 19:10:09 +0100

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 flag offensive close merge delete

Comments

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

tmonteil gravatar imagetmonteil ( 2018-11-18 12:39:38 +0100 )edit
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.

rburing gravatar imagerburing ( 2018-11-18 14:51:37 +0100 )edit
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().

rburing gravatar imagerburing ( 2018-11-18 16:40:25 +0100 )edit

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.

rburing gravatar imagerburing ( 2018-11-18 20:29:41 +0100 )edit

1 Answer

Sort by ยป oldest newest most voted
2

answered 2018-11-18 21:18:50 +0100

Jsevillamol gravatar image

updated 2018-11-18 21:28:57 +0100

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
edit flag offensive delete link more

Comments

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(...).

rburing gravatar imagerburing ( 2018-11-18 21:53:13 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2018-11-18 10:42:36 +0100

Seen: 522 times

Last updated: Nov 18 '18