Ask Your Question
1

1^1 undefined

asked 2018-11-13 09:58:44 +0100

Jsevillamol gravatar image

updated 2018-11-13 10:03:40 +0100

Consider the following code snippet:

# FACTORIZATION IN F_q[x]
def my_mul(x,y):
    if x == None: return y
    if y == None: return x
    return x*y

# Squarefree Decomposition in F_q[x]
def squarefree_decomposition(GF, f):
    p = GF.characteristic()
    # base case
    if f == 1: return [1]

    # recursive case
    df = f.diff()
    i_factors = [1]
    g = gcd(f,df)
    w = GF(f / g) 
    # collect squarefree factors such that p !| i
    while(w != 1):
        w_aux = gcd(g,w)
        g = GF(g / w_aux)
        i_factor = GF(w / w_aux)
        i_factors.append(i_factor)
        w = w_aux
    # here, g = prod[f_(j)^j for p | j]
    # collect squarefree factors such that p | j
    g_root = GF(g.coefficients(sparse=False)[::p]) # pth root of g
    g_root_decomposition = squarefree_decomposition(GF, g_root)
    j_factors = [g_root_decomposition[i/p] if i%p==0 else 1 for i in xrange(p*(len(g_root_decomposition)-1)+1)]

    # combine results
    res = map(my_mul, i_factors, j_factors)

    return res

# Example in F_q[x]
GF125X = GF(5^3)[x]
f = GF125X((x^5 + x^2 + x^1 + 1)^2*x^5)
decom = squarefree_decomposition(GF125X, f)
print("{} decomposes as {}".format(f, decom))
recom = [f_i^i for f_i,i in enumerate(decom)]
recom

When I execute this, I get the following output:

x^15 + 2*x^12 + 2*x^11 + 2*x^10 + x^9 + 2*x^8 + 3*x^7 + 2*x^6 + x^5 decomposes as [1, 1, x^5 + x^2 + x + 1, 1, 1, x]
Error in lines 28-28
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 "sage/rings/polynomial/polynomial_template.pxi", line 605, in sage.rings.polynomial.polynomial_zz_pex.Polynomial_template.__pow__ (build/cythonized/sage/rings/polynomial/polynomial_zz_pex.cpp:12318)
    raise NotImplementedError("%s^%s not defined."%(ee,self))
NotImplementedError: 1^1 not defined.

I notice I am confused. AFAIK, there is only one sensible result for 1^1, namely 1. Why do I get this error?

If I try creating a 1 polynomial in a finite field and taking its 1th power it works:

id_ = GF125X(1)
id_^1

Produces as output 1, as expected.

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted
2

answered 2018-11-13 11:55:21 +0100

rburing gravatar image

updated 2018-11-13 12:12:09 +0100

The problem can be seen as follows:

int(1)^GF125X(1)

Indeed it does not make sense to raise integers to polynomial powers in general.

Maybe the error message should be more descriptive, by including the types.

In your case, it seems you have confused f_i and i: note enumerate yields a list of pairs where the first element is the index.

Also you can omit the argument "GF" (which, confusingly, is a polynomial ring): it can be obtained from f by f.parent(). Furthermore you can probably avoid using my_mul by using prod and zip. Also, you will probably find it convenient to define

GF125X.<x> = GF(5^3)[]
f = (x^5 + x^2 + x^1 + 1)^2*x^5

so that x is really the generator of a polynomial ring, and you can define f without explicit conversion.

edit flag offensive delete link more

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-13 09:58:44 +0100

Seen: 886 times

Last updated: Nov 13 '18