Simplifying trigonometric constants

[Waldek Hebisch]

I recently met the problem:

: Let t := (5/9)*%pi. Simplify tan(t) + 4*sin(t)

The solution using FriCAS can be as follows. First, we want to
express this in terms of complex exponentials. Since (5/9)*%pi is
a rational multiple of %pi we get root of 1, in this case root of
degree 18. But we also need %i, which leads to root of degree 36.
Corresponding field is extention by cyclotomic polynomial, so
we build it:

cyclotomic(36)$CyclotomicUtilities
cF := SAE(FRAC(INT), SUP(FRAC(INT)), %)

Now, we can express all ingredients in terms of generator:

et := (generator()$cF)^10
ct := (et + 1/et)/2
st := (et - 1/et)/(2*(generator()$cF)^9)

and our expression is:

(4*ct + 1)*st/ct

9 3
(41) ? - 2 ?
Type: SimpleAlgebraicExtension(Fraction(Integer),SparseUnivariatePolynomial(Fraction(Integer)),?^12+(-(?^6))+1)

Now we can find minimal polynomial:

(68) -> minimalPolynomial(%)

2
(68) ? - 3
Type: SparseUnivariatePolynomial(Fraction(Integer))

and we see that the result is sqrt(3). We could also observe that
the expression above is a member of smaller cyclotomic field and from
that infer expression 2*cos(%pi/6).

I wonder how much of this is worth automating. Recognizing explicit
rational multiples of %pi is easy. From that we can infer appropriate
cyclotomic field, which may be unconfortably large, but is easy to
find. Inside cyclotomic field we get canonical form and can compute
minimal polynomial. So we can recognize when the result is say a square
root. Belonging to smaller field is easy too: we know Galois group
and can check if element is invariant. So we can find expression
in terms of smaller angles.

There is question how much coverage we get this way. That is,
are there useful simplifications that are missed by approach above?
And how frequently simplifications of that kind are applicable?

Opinions? Anybody wants to make a package based on this?

BTW: if arguments to trigonometric functions are _not_ a rational
multiple of %pi, then 'normalize' is quite good at finding canonical
form, but frequently it is different from what users want.

--
Waldek Hebisch

[Kurt Pagani]

A clever approach indeed.

>
> I wonder how much of this is worth automating. Recognizing explicit
> rational multiples of %pi is easy. From that we can infer appropriate
> cyclotomic field, which may be unconfortably large, but is easy to
> find. Inside cyclotomic field we get canonical form and can compute
> minimal polynomial. So we can recognize when the result is say a square
> root. Belonging to smaller field is easy too: we know Galois group
> and can check if element is invariant. So we can find expression
> in terms of smaller angles.

I think the theory is obvious (Trigonometric numbers ~ AlgebraicNumber)
https://en.wikipedia.org/wiki/Exact_trigonometric_values

so I tried for fun:

r:=rootsOf(z^36-1)
ct:=(r.10+1/r.10)/2
st:=(r.10-1/r.10)/(2*r.9)
xx:= (4*ct + 1)*st/ct

>> Error detected within library code:
univariate: denominator is 0 mod p

Somehow strange? When using %i instead of r.9, in st, it doesn't
complain. I'm suspecting ratDenom in AlgebraicManipulations which
handles division in AlgebraicNumber.

>
> There is question how much coverage we get this way. That is,
> are there useful simplifications that are missed by approach above?
> And how frequently simplifications of that kind are applicable?
>
> Opinions? Anybody wants to make a package based on this?

Well, nice to have but surely not a must. I guess you could provide one
in a wink of an eye (if time allows :)

[Waldek Hebisch]

Unfortunatly, 'rootsOf' is useful only in limited situations and
in other cases, like the one above leads to wrong results. Namely,
we need to work in the splitting field, which in case of roots of 1
is easy: corresponding splitting field is generated by root of
appropriate cyclotomic polynomial. In general 'rootsOf' may be
wrong for two reasons. First, 'rootOf' (used by 'rootsOf') leads
to correct result only if its argument is an irreducible polynomial.
But 'z^36 - 1' is reducible. Second, normally 'rootsOf' treats
roots in indepenent way which basically means that each single root
usually (that is for irreducible polynomial) is correct, but algebraic
structure that they generate may fail to be a field (so in particular
it is not the splitting field). In the case above, 'rootsOf'
notices that the polynomial is a binomial and uses special case code
which for irreducible polynomial would produce correct splitting
field. But first reason still applies, the polynomial is reducible
so produced algebraic structure is not a field. So you find a
zero divisor which leads to the error above.

> >
> > There is question how much coverage we get this way. That is,
> > are there useful simplifications that are missed by approach above?
> > And how frequently simplifications of that kind are applicable?
> >
> > Opinions? Anybody wants to make a package based on this?
>
> Well, nice to have but surely not a must. I guess you could provide one in a
> wink of an eye (if time allows :)
>
>
> >
> > BTW: if arguments to trigonometric functions are _not_ a rational
> > multiple of %pi, then 'normalize' is quite good at finding canonical
> > form, but frequently it is different from what users want.
> >
>

> --
> You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to fricas-devel...@googlegroups.com.
> To view this discussion visit https://groups.google.com/d/msgid/fricas-devel/5700f5e4-5711-4e83-8f18-f19a0143dc57%40gmail.com.

--
Waldek Hebisch

[Dima Pasechnik]

It seems to me that "trigonometric" numbers (i.e. sin/cos of rational
multiplies of \pi)
are merely real cyclotomic numbers, i.e. in the field Q(zeta+zeta^-1),
with zeta an n-th root of unity. A lot is known
about them, and specially coded routines to work with cyclotomic
numbers are very efficient, much more efficient
than these for general algebraic numbers (Abelian Galois groups are
much nicer than the general ones :-))

One of applications is the character theory of finite groups (their
values are cyclotomic).
E.g. GAP has arithmetic for universal cyclotomic numbers implemented
(it does not impose any hard bound on n).

Dima

>
> so I tried for fun:
>
> r:=rootsOf(z^36-1)
> ct:=(r.10+1/r.10)/2
> st:=(r.10-1/r.10)/(2*r.9)
> xx:= (4*ct + 1)*st/ct
>
> >> Error detected within library code:
> univariate: denominator is 0 mod p
>
> Somehow strange? When using %i instead of r.9, in st, it doesn't
> complain. I'm suspecting ratDenom in AlgebraicManipulations which
> handles division in AlgebraicNumber.
>
>
>
> >
> > There is question how much coverage we get this way. That is,
> > are there useful simplifications that are missed by approach above?
> > And how frequently simplifications of that kind are applicable?
> >
> > Opinions? Anybody wants to make a package based on this?
>
> Well, nice to have but surely not a must. I guess you could provide one
> in a wink of an eye (if time allows :)
>
>
> >
> > BTW: if arguments to trigonometric functions are _not_ a rational
> > multiple of %pi, then 'normalize' is quite good at finding canonical
> > form, but frequently it is different from what users want.
> >
>

[Kurt Pagani]

Oh, it was by no means my intention to give any alternative to your
'cyclotomic' method. As said, I tried rootsOf/zerosOf just from idle
curiosity. Clearly, 'rootsOf' is a mystery (which one corresponds to the
%i? etc.).
I was puzzled by the error message

>> Error detected within library code:
>> univariate: denominator is 0 mod p

I guess it's wrong, since zero? ct --> false

[Kurt Pagani]

You're right, of course ;) it was a silly idea to mention the
AlgebraicNumber domain in this connection at all. But the

"""
are closed under arithmetic operations, *every trigonometric number* is
algebraic.[3] The minimal polynomials of trigonometric numbers can be
explicitly enumerated.[4] In contrast, by

"""
inspired to have a look what happens ...

[Waldek Hebisch]

That is classic GIGO principle: input data is wrong (violates
assumptions) so you error during processing.

> > > >
> > > > There is question how much coverage we get this way. That is,
> > > > are there useful simplifications that are missed by approach above?
> > > > And how frequently simplifications of that kind are applicable?
> > > >
> > > > Opinions? Anybody wants to make a package based on this?
> > >
> > > Well, nice to have but surely not a must. I guess you could provide one in a
> > > wink of an eye (if time allows :)
> > >
> > >
> > > >
> > > > BTW: if arguments to trigonometric functions are _not_ a rational
> > > > multiple of %pi, then 'normalize' is quite good at finding canonical
> > > > form, but frequently it is different from what users want.
> > > >
> > >
> > > --
> > > You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group.
> > > To unsubscribe from this group and stop receiving emails from it, send an email to fricas-devel...@googlegroups.com.
> > > To view this discussion visit https://groups.google.com/d/msgid/fricas-devel/5700f5e4-5711-4e83-8f18-f19a0143dc57%40gmail.com.
> >
>
> --
> You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to fricas-devel...@googlegroups.com.

> To view this discussion visit https://groups.google.com/d/msgid/fricas-devel/0e317c4c-ff4e-4d40-91ed-1b9a7b123905%40gmail.com.

--
Waldek Hebisch

[Kurt Pagani]

Wait a minute ... that's too easy

AlgebraicNumber has Field --> true

r --> List(AlgebraicNumber)
(4*ct+1)*st --> Type: AlgebraicNumber
ct --> AlgebraicNumber
zero? ct --> false

So where is 'input data' wrong? Maybe I'm missing a point, but we're in
a "field"!

[Waldek Hebisch]

Yes.

> A lot is known
> about them, and specially coded routines to work with cyclotomic
> numbers are very efficient, much more efficient
> than these for general algebraic numbers (Abelian Galois groups are
> much nicer than the general ones :-))

Well, FriCAS SAE works with field generated by a single root of
an irreducible polynomial (parameter of the domain). It is not
clear to me that one can do cyclotomic arithmetic smarted than
the general method used by SAE. Cyclotomic Galois groups are
easier to deal with than more general groups, but SAE is not
doing Galois theory, and Galois group action can be defined on top
of operations provided by SAE.

> One of applications is the character theory of finite groups (their
> values are cyclotomic).
> E.g. GAP has arithmetic for universal cyclotomic numbers implemented
> (it does not impose any hard bound on n).

For characters one can use special tricks. I know that GAP has
special code for cyclotomic arithmetic. It is not clear to me
what is the nature of improvements implemented there and if
they gain much compared to simpler implementation. One idea that
I considered is using redundant representation. That is arithemtic
is easier if done mod x^n - 1, but to have correct equality test
one must reduce modulo minimal polynomial. In principle performing
reduction modulo minimal polynomial in lazy way could gain
some speed.

--
Waldek Hebisch

[Waldek Hebisch]

You have:

r:=rootsOf(z^36-1)

Since 'z^36-1' is reducible we are not longer in a field. That is
the input data introduced contradition. Similarly, trying to use
togeter different roots may lead to contradition.

Of course, real reason is that current 'rootsOf' is a trap:
- it does not check that its argument is irreducible (which has some
cost, but that cost may be acceptable),
- it does not do computations needed to compute splitting field
(which would be _very_ expensive).

Maybe we should replace current 'rootsOf' by version that computes
the splitting field. But in few places that algebra currently uses
'rootsOf' computing splitting field would be too expensive, so we
would need a cheaper alternative.

> > > > > >
> > > > > > There is question how much coverage we get this way. That is,
> > > > > > are there useful simplifications that are missed by approach above?
> > > > > > And how frequently simplifications of that kind are applicable?
> > > > > >
> > > > > > Opinions? Anybody wants to make a package based on this?
> > > > >
> > > > > Well, nice to have but surely not a must. I guess you could provide one in a
> > > > > wink of an eye (if time allows :)
> > > > >
> > > > >
> > > > > >
> > > > > > BTW: if arguments to trigonometric functions are _not_ a rational
> > > > > > multiple of %pi, then 'normalize' is quite good at finding canonical
> > > > > > form, but frequently it is different from what users want.
> > > > > >
> > > > >
> > > > > --
> > > > > You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group.
> > > > > To unsubscribe from this group and stop receiving emails from it, send an email to fricas-devel...@googlegroups.com.
> > > > > To view this discussion visit https://groups.google.com/d/msgid/fricas-devel/5700f5e4-5711-4e83-8f18-f19a0143dc57%40gmail.com.
> > > >
> > >
> > > --
> > > You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group.
> > > To unsubscribe from this group and stop receiving emails from it, send an email to fricas-devel...@googlegroups.com.
> > > To view this discussion visit https://groups.google.com/d/msgid/fricas-devel/0e317c4c-ff4e-4d40-91ed-1b9a7b123905%40gmail.com.
> >
>
> --
> You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to fricas-devel...@googlegroups.com.

> To view this discussion visit https://groups.google.com/d/msgid/fricas-devel/f87e40d7-8ae2-4971-83de-86d03383a7d6%40gmail.com.

--
Waldek Hebisch

[Kurt Pagani]

Ok, thanks! This explains a lot.

[Dima Pasechnik]

GAP uses a special basis for Q(zeta^n) (as a Q-vectorspace) which, as
far as I understand,
contain such bases for all Q(zeta^m), where m divides n.
This means that the reduction to a subfield is very cheap.

It's described in
Zumbroich, M.: Grundlagen einer Arithmetik in Kreisteilungsko¨rpern
und ihre Implementa-
tion in CAS. Diplomarbeit, Lehrstuhl D fu¨r Mathematik, RWTH Aachen,
Germany (1989)
and more, and the GAP implementation, is in
https://doi.org/10.1007/s002000050065

Dima

>
> --
> Waldek Hebisch

>
> --
> You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to fricas-devel...@googlegroups.com.

> To view this discussion visit https://groups.google.com/d/msgid/fricas-devel/aZSkUQzifJTHO1tb%40fricas.org.