Cyclotomicity

Examples

This file offers 6 functions: InversePhiBound, gcdList, cyclotomic, IsCyclotomicGraeffe, IsCyclotomicIter, and IsCyclotomic.

Let f be two RingElem values representing univariate polynomials in a polynomial ring P over ZZ or QQ. Let n be a positive integer.

InversePhiBound(n) -- returns a BigInt representing an upper bound for the inverse EulerTotient of n - using OEIS sequence A355667.
gcdList(L) -- returns a RingElem, namely the gcd of a vector of RingElems.
cyclotomic(P, K) -- returns a RingElem representing the K-th cyclotomic polynomial in the ring P.
IsCyclotomicGraeffe(f) -- returns an unsigned long n indicating that f is the n-th cyclotomic polynomial - using a Graeffe transformation approach.
IsCyclotomicIter(f) -- returns an unsigned long n indicating that f is the n-th cyclotomic polynomial - using an iterative approach.
IsCyclotomic(f) -- returns an unsigned long n indicating that f is the n-th cyclotomic polynomial - choosing an approach from the above.

Details about the InversePhiBound can be found in OEIS sequence A355667.
Both approaches are taken from Bradford and Davenport (DOI:10.1007/3-540-51084-2_22).

It seems to be the case that the constant coefficient of the n-th cyclotomic polynomial is always +1 if n > 1.
The coefficients of cyclotomic polynomials are always "symmetric", i.e., rev(f) == f?
Are there any criterions when the Graeffe approach is faster?
If the input is a univariate polynomial in a multivariate ring, most functions will crash since UnivariateIndetIndex still returns the index of the variable.

2022