sums of roots of unity = 0

[Mike Zabrocki]

I want to simplify sums of roots of unity = 0.
I am working with expressions which should always evaluate to integers
but sometimes there are terms which do not in SAGE.

The simplest example is

def sumofroots(d):
return add([exp(2*pi*I*r/d) for r in range(d)]).expand()

sage: sumofroots(4)
0

But
sage: sumofroots(5)
e^(4*I*pi/5) + e^(2*I*pi/5) + e^(-(2*I*pi/5)) + e^(-(4*I*pi/5)) + 1

In fact, for just about any odd integer this does not reduce but for
any even integer it does.

Should I be using another "expand" "simplify" or other function?

-Mike

[Robert Bradshaw]

I think this is just maxima's inability to simplify this expression,
which is easy to see by invariance under multiplication by e^(2pi i/
n), but less obvious from first principles. (The even case is easy
because the expressions come in +/- pairs.)

If you really want to work with roots of unity, you can use number
fields.

sage: K.<a> = CyclotomicField(7) # Q[a] where a is a 7th root of unity.
sage: a^7
1
sage: sum([a^r for r in range(7)])
0

- Robert

[Carl Witty]

Instead of using these symbolic expressions, you may want to
manipulate roots of unity using QQbar. Here's an example:

sage: def sumofroots(d):
....: return sum([QQbar.zeta(d)^r for r in range(d)])
....:
sage: v = sumofroots(4); v
0
sage: v = sumofroots(5); v
[-7.3183646642771550e-19 .. 7.3183646642771550e-19] +
[-5.4210108624275222e-19 .. 5.4210108624275222e-19]*I
sage: v == 0
True
sage: v
0

Note that even though the numbers print out in a floating-point
notation, computations using QQbar are exact.

Carl

[Carl Witty]

On Mar 21, 12:17 pm, Carl Witty <cwi...@newtonlabs.com> wrote:
> On Mar 21, 11:06 am, Mike Zabrocki <zabro...@mathstat.yorku.ca> wrote:
>
>
>
> > I want to simplify sums of roots of unity = 0.
> > I am working with expressions which should always evaluate to integers
> > but sometimes there are terms which do not in SAGE.
>

> Instead of using these symbolic expressions, you may want to
> manipulate roots of unity using QQbar. Here's an example:
>
> sage: def sumofroots(d):
> ....: return sum([QQbar.zeta(d)^r for r in range(d)])
> ....:
> sage: v = sumofroots(4); v
> 0
> sage: v = sumofroots(5); v
> [-7.3183646642771550e-19 .. 7.3183646642771550e-19] +
> [-5.4210108624275222e-19 .. 5.4210108624275222e-19]*I
> sage: v == 0
> True
> sage: v
> 0
>
> Note that even though the numbers print out in a floating-point
> notation, computations using QQbar are exact.

Note that Robert Bradshaw's suggestion of using a cyclotomic field is
probably better than my suggestion of using QQbar. The one advantage
of QQbar is that you don't need to know all the roots you'll be
working with ahead of time (to compute their lcm, to decide which
number field to work in). The disadvantage is that QQbar will
probably be significantly slower than just working directly in the
number field.

Carl

[Justin C. Walker]

OK, that's just weird. A test for equality changes the value?? Am I
reading that correctly?

I tried tracing this, but got lost in a maze of twisty little
passages, all subtly different...

Justin

--
Justin C. Walker, Curmudgeon-At-Large
Director
Institute for the Enhancement of the Director's Income
--------
"Weaseling out of things is what separates us from the animals.
Well, except the weasel."
- Homer J Simpson
--------

[Carl Witty]

On Mar 21, 12:43 pm, "Justin C. Walker" <jus...@mac.com> wrote:
> On Mar 21, 2008, at 12:17 PM, Carl Witty wrote:
> > sage: v = sumofroots(5); v
> > [-7.3183646642771550e-19 .. 7.3183646642771550e-19] +
> > [-5.4210108624275222e-19 .. 5.4210108624275222e-19]*I
> > sage: v == 0
> > True
> > sage: v
> > 0
>
> OK, that's just weird. A test for equality changes the value?? Am I
> reading that correctly?

It does not change the value (which is 0, before and after the test);
but it does change the print representation (and the internal
representation) of the value.

This is because elements of QQbar (and AA) attempt to compute using
numerical interval representations whenever possible, but keep enough
state internally to reconstruct an exact computation if it becomes
necessary. So in the above example, when we first print v, the QQbar
code knows that it is very very close to zero, but it does not yet
know that it is exactly equal to zero. When we test whether v is
equal to zero, then QQbar gives up on the approximate representation
(these interval computations cannot directly prove that v equals zero)
and actually performs the exact computation.

Carl

[Justin C. Walker]

Ok, I was wrong: it's not weird, it's cool!

Thanks for the explanation.

Justin

--
Justin C. Walker, Curmudgeon-At-Large, Director

Institute for the Enhancement of the Director's Income
--------

The path of least resistance:
it's not just for electricity any more.
--------

[Mike Zabrocki]

Hi,
My issue arises because I want to evaluate a symmetric polynomials at
certain roots of unity. Can I do this within QQbar then once I am
done with QQbar, is it possible to cast the result back into QQ if I
know that these evaluations must reduce to integers/rationals?

Working in QQbar seems to cause problems of its own.

example:
sage: s = SFASchur(QQ)
sage: a=s([2,2]).expand(8)(flatten([[QQbar.zeta(3)^d for d in
range(3)], [QQbar.zeta(5)^d for d in range(5)]]))
sage: a.exactify()
sage: a
0

sage: a=s([3,2]).expand(8)(flatten([[QQbar.zeta(3)^d for d in
range(3)], [QQbar.zeta(5)^d for d in range(5)]]))
sage: a.exactify()
.... lots of stuff cut ...
<type 'exceptions.RuntimeError'>: maximum recursion depth exceeded

-Mike

[Franco Saliola]

On Fri, Mar 21, 2008 at 3:17 PM, Carl Witty <cwi...@newtonlabs.com> wrote:

> Instead of using these symbolic expressions, you may want to
> manipulate roots of unity using QQbar. Here's an example:
>
> sage: def sumofroots(d):
> ....: return sum([QQbar.zeta(d)^r for r in range(d)])
> ....:
> sage: v = sumofroots(4); v
> 0
> sage: v = sumofroots(5); v
> [-7.3183646642771550e-19 .. 7.3183646642771550e-19] +
> [-5.4210108624275222e-19 .. 5.4210108624275222e-19]*I
> sage: v == 0
> True
> sage: v
> 0
>
> Note that even though the numbers print out in a floating-point
> notation, computations using QQbar are exact.

This is interesting. After playing around a bit, I'm wondering why v
can't be converted into an integer? Both Integer(v) and ZZ(v)
complain.

Franco

--

[Mike Hansen]

Hi Mike,

I would use the CyclotomicField. For example,

sage: s = SFASchur(QQ)
sage: a = s([2,2]).expand(8)

sage: C.<zeta15> = CyclotomicField(15)
sage: zeta3 = zeta15^5
sage: zeta5 = zeta15^3
sage: a([zeta3^d for d in range(3)]+[zeta5^d for d in range(5)])
0

--Mike

[Carl Witty]

On Mar 21, 2:28 pm, Mike Zabrocki <zabro...@mathstat.yorku.ca> wrote:
> Working in QQbar seems to cause problems of its own.
>
> example:
> sage: s = SFASchur(QQ)

> sage: a=s([3,2]).expand(8)(flatten([[QQbar.zeta(3)^d for d in
> range(3)], [QQbar.zeta(5)^d for d in range(5)]]))
> sage: a.exactify()
> .... lots of stuff cut ...
> <type 'exceptions.RuntimeError'>: maximum recursion depth exceeded

You'll be much happier with the CyclotomicField approach.

Thanks for the bug report. I've reported it here:
http://trac.sagemath.org/sage_trac/ticket/2638; but it's tricky to
fix, so I don't know when it might get fixed.

Carl

[Carl Witty]

Because I never got around to implementing that feature? :)

I've posted this as a bug report here: http://trac.sagemath.org/sage_trac/ticket/2639
and I will probably fix it this weekend.

Carl