(1) -> <spad>
)abbrev domain ROU RootOfUnity ++ Author: Kurt Pagani ++ Date Created: Fri Jun 01 17:24:19 CEST 2018 ++ License: BSD ++ References: ++ https://en.wikipedia.org/wiki/Root_of_unity ++ https://en.wikipedia.org/wiki/Principal_root_of_unity ++ Description: ++ The nth roots of unity are,by definition, the roots of the polynomial ++ $P(z)=z^n−1,ドル and are therefore algebraic numbers. As the polynomial $P$ ++ is not irreducible - unless $n=1,ドル the primitive nth roots of unity are ++ roots of an irreducible polynomial of lower degree, called the cyclotomic ++ polynomial. ++ ++ Group of nth roots of unity ++ The product and the multiplicative inverse of two nth roots of unity ++ are also nth roots of unity. Therefore, the nth roots of unity form ++ a group under multiplication. ++ ++ Notes ++ Any algebraically closed field has exactly $n$ nth roots of unity if ++ $n$ is not divisible by the characteristic of the field. ++ ++ The significance of a root of unity being principal is that it is a ++ necessary condition for the theory of the discrete Fourier transform ++ to work out correctly. ++ ++ Usage and Examples ++ X ==> Expression Complex Integer ++ R ==> RootOfUnity(5, X) ++ z:X ++ r:=rootsOf(z^5-1) or zerosOf(z^5-1) or solve(z^5=1, 'z) ++ q:=[convert(t)$R for t in r] ++ [primitive?(t) for t in q] ++ [principal?(t) for t in q] ++ RootOfUnity(n, R) : Exports == Implementation where
n:PositiveInteger R:Ring
CTOF ==> CoercibleTo OutputForm
Exports == Join(Group,CTOF) with
convert : R -> % ++ Convert r:R to a n-th root of unity if r^n=1$R. retract : % -> R ++ Retract a n-th root of unity to a member of R. 1 : () -> % ++ The ring unit. primitive? : % -> Boolean ++ An nth root of unity is primitive if it is not a kth root of unity ++ for some smaller k. principal? : % -> Boolean ++ A principal n-th root of unity of a ring is an element a:R ++ satisfying the equations a^n=1$R,sum(a^(j*k), j=0..n-1)=0 ++ for all 1<=k<n. coerce : % -> OutputForm ++ Coerce to output form.
if R has ExpressionSpace then ExpressionSpace
Implementation == R add
Rep := R
convert(x) == x^n = 1$R => x error "Probably not a root of unity."
retract(x:%):R == x@Rep
primitive?(x:%):Boolean == b:List Boolean:=[test(x^m=1$R) for m in 1..n-1] not reduce(_and,b)
summ(a:R,m:PositiveInteger):R == s:List R:=[a^j for j in 0..m] reduce(_+, s)
principal?(x:%):Boolean == n=1 => false a:R:=x@Rep nn:PositiveInteger:=(n-1)::PositiveInteger b:List Boolean:=[test(summ(a^k,nn)=0$R) for k in 1..nn] reduce(_and, b)</spad>
Compiling FriCAS source code from file /var/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/1931947919832813650-25px001.spad using old system compiler. ROU abbreviates domain RootOfUnity ------------------------------------------------------------------------ initializing NRLIB ROU for RootOfUnity compiling into NRLIB ROU compiling exported convert : R -> % Time: 0.01 SEC.
compiling exported retract : % -> R ROU;retract;%R;2 is replaced by x Time: 0 SEC.
compiling exported primitive? : % -> Boolean Time: 0.02 SEC.
compiling local summ : (R,PositiveInteger) -> R Time: 0 SEC.
compiling exported principal? : % -> Boolean Time: 0 SEC.
****** Domain: % already in scope augmenting %: (RetractableTo (Integer)) ****** Domain: R already in scope augmenting R: (ExpressionSpace) ****** Domain: % already in scope augmenting %: (Ring) ****** Domain: R already in scope augmenting R: (ExpressionSpace) ****** Domain: R already in scope augmenting R: (ExpressionSpace) (time taken in buildFunctor: 4163) Time: 0 SEC.
Warnings: [1] not known that (Comparable) is of mode (CATEGORY domain (SIGNATURE convert (% R)) (SIGNATURE retract (R %)) (SIGNATURE (One) (%)) (SIGNATURE primitive? ((Boolean) %)) (SIGNATURE principal? ((Boolean) %)) (SIGNATURE coerce ((OutputForm) %)) (IF (has R (ExpressionSpace)) (ATTRIBUTE (ExpressionSpace)) noBranch))
Cumulative Statistics for Constructor RootOfUnity Time: 0.05 seconds
finalizing NRLIB ROU Processing RootOfUnity for Browser database: --------constructor--------- --------(convert (% R))--------- --->-->RootOfUnity((convert (% R))): Improper first word in comments: Convert "Convert \\spad{r:R} to a \\spad{n}-th root of unity if \\spad{r^n=1}\\$\\spad{R}." --------(retract (R %))--------- --->-->RootOfUnity((retract (R %))): Improper first word in comments: Retract "Retract a \\spad{n}-th root of unity to a member of \\spad{R}." --------((One) (%))--------- --->-->RootOfUnity(((One) (%))): Improper first word in comments: The "The ring unit." --------(primitive? ((Boolean) %))--------- --->-->RootOfUnity((primitive? ((Boolean) %))): Improper first word in comments: An "An \\spad{n}th root of unity is primitive if it is not a \\spad{k}th root of unity for some smaller \\spad{k}." --------(principal? ((Boolean) %))--------- --->-->RootOfUnity((principal? ((Boolean) %))): Improper first word in comments: A "A principal \\spad{n}-th root of unity of a ring is an element a:R satisfying the equations \\spad{a^n=1}\\$\\spad{R},{} sum(a^(\\spad{j*k}), {}\\spad{j=0}..\\spad{n}-1)\\spad{=0} for all 1<=k<n." --------(coerce ((OutputForm) %))--------- --->-->RootOfUnity((coerce ((OutputForm) %))): Improper first word in comments: Coerce "Coerce to output form." ; compiling file "/var/aw/var/LatexWiki/ROU.NRLIB/ROU.lsp" (written 04 AUG 2025 07:36:57 PM):
; wrote /var/aw/var/LatexWiki/ROU.NRLIB/ROU.fasl ; compilation finished in 0:00:00.032 ------------------------------------------------------------------------ RootOfUnity is now explicitly exposed in frame initial RootOfUnity will be automatically loaded when needed from /var/aw/var/LatexWiki/ROU.NRLIB/ROU
Test flavours
--)co rootunity
z:RNG
r:=rootsOf(z^5-1)
R==>RootOfUnity(5,RNG)
q:=[convert(t)$R for t in r]
primitive?(1$R)
pb:=[primitive?(t) for t in q]
test(q.1=q.2)
q.1^5
q.1^6
q.1^15
sample()$R
one? sample()$R
inv(q.1)
q12:=inv(q.1*q.2)
q12^5
principal?(q.1)
principal?(q.3*q.1)
-- using solve instead of rootsOf
rs5:=solve(z::RNG^5=1$RNG,'z)
qrs5:=[convert(rhs t)$R for t in rs5]
p5:=[primitive?(t) for t in qrs5]
l5:=[principal?(t) for t in qrs5]
test (qrs5.2=q.2/q.1)
-- using zerosOf rz5:=zerosOf(z::RNG^5-1$RNG)
qrz5:=[convert(t)$R for t in rz5]
pz5:=[primitive?(t) for t in qrz5]
lz5:=[principal?(t) for t in qrz5]