roots of unity

[Simon Burton]

Hi,

I am using the groebner basis, reduce, etc. for working
with polynomials in roots of unity. Eg. If w is a third
root of unity then:

>>> import sympy as sy
>>> w = sy.symbols("w")
>>> p = w**2 + w + 1
>>> basis = sy.groebner([p])

now we can work out polynomials in w:

>>> q = w**5 + w + 2
>>> _, q = basis.reduce(q)
>>> q
1

(And this generalizes to polynomials with multiple different
roots of unity.)

Ok, so this is all very cool, I finally found a use for
groebner bases, but it occurs to me that there might be a simpler
way of achieving this?

Simon.

[Aaron Meurer]

I'm not at my computer to check, but maybe ratsimpmodprime is what you want.

Aaron Meurer

> --
> You received this message because you are subscribed to the Google Groups "sympy" group.
> To post to this group, send email to sy...@googlegroups.com.
> To unsubscribe from this group, send email to sympy+un...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/sympy?hl=en.
>

[simon]

Thanks Aaron, but that function is actually more complicated than what I am doing now.

Given that we have ImaginaryUnit I thought it might be possible to extend this to

arbitrary roots of unity, for example.

Cheers,

Simon.

[Aaron Meurer]

Oh, I see what you want. No, I don't think we have a RootOfUnity class. You might try to write one, using ImaginaryUnit as your guide, and see how far you can get with it. However, be aware that making stuff auto combine without modifying the core is not easy and is a major problem that we're trying to solve.  

We do have RootOf, which represents an arbitrary algebraic number. Depending on what you want to do with it, it may or may not be enough. 

Aaron Meurer

--
You received this message because you are subscribed to the Google Groups "sympy" group.

To view this discussion on the web visit https://groups.google.com/d/msg/sympy/-/6PCSI_BSbpcJ.

[Aaron Meurer]

Actually, the best you could do with that is to make w**2 automatically return -w - 1. Automatic reduction would be much smarter in the polys. I'm not sure if there's support for it there yet. Unfortunately, the algebraic number support there is still in its infant stage. 

Aaron Meurer

[Calvin McPhail-Snyder]

Have there been any relevant updates since this post? I sometimes have to do matrix computations whose entries are polynomials in roots of unity, and it would be nice if there were a way to work easily with variables that have relations, i.e. in quotients of polynomial rings. Of course, I have no idea how hard that sort of thing is to implement, so maybe it's an unrealistic hope. The current solution for computations in C[x]/(f) is to apply reduce at every step of the calculation with basis f, and I suppose that works.

[Kalevi Suominen]

These computations can probably be done conveniently in fields of AlgebraicField class. Their elements are essentially coefficient lists of polynomials in a primitive element over the base field. The polynomial is automatically transformed to its lowest terms using the minimal polynomial of the primitive element. The primitive element can be given as a SymPy expression, and the field is obtained by adjoining that to the base field, typically the field of rational numbers.

>>> w = exp(2*pi*I/12)
>>> K = QQ.algebraic_field(w)
>>> type(K)
<class 'sympy.polys.domains.algebraicfield.AlgebraicField'>

The primitive element of  K  represented by  w  can be obtained by the method  'from_sympy' , and the inverse method is 'to_sympy'. All arithmetic operations are defined for the elements of  K.

>>> z = K.from_sympy(w)
>>> type(z)
<class 'sympy.polys.polyclasses.ANP'>
>>> K.to_sympy(z**6 - 1)
-2
>>> type(z**6 - 1)
<class 'sympy.polys.polyclasses.ANP'>

Working with matrices over algebraic fields is more complicated because the implementation will automatically try to 'sympify' the matrix entries, i.e., transform them to SymPy expressions. As a workaround, it should be possible to use a custom matrix class with trivial sympification routine.

 >>> class MyMatrix(Matrix):
...     _sympify = staticmethod(lambda x: x)
...

Kalevi Suominen

[Calvin McPhail-Snyder]

Thanks! I saw that there's an Algebraic Fields module, but apparently didn't read the documentation correctly.