login  home  contents  what's new  discussion  bug reports help  links  subscribe  changes  refresh  edit

# Edit detail for SandBoxRootOfUnity revision 1 of 1

 1 Editor: pagani Time: 2018/07/16 20:02:31 GMT+0 Note:

changed:
-
)abbrev domain ROU RootOfUnity
++ Author: Kurt Pagani
++ Date Created: Fri Jun 01 17:24:19 CEST 2018
++ 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)

Test flavours

\begin{axiom}
--)co rootunity
-- Example
--RNG ==> Complex Expression Integer
RNG ==> Expression Complex Integer
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]
--test (qrs5.2=q.2/q.1)

\end{axiom}


)abbrev domain ROU RootOfUnity
++ Author: Kurt Pagani
++ Date Created: Fri Jun 01 17:24:19 CEST 2018
++ 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)
   Compiling FriCAS source code from file
using old system compiler.
ROU abbreviates domain RootOfUnity
------------------------------------------------------------------------
initializing NRLIB ROU for RootOfUnity
compiling into NRLIB ROU
compiling exported convert : R -> $Time: 0.02 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.01 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: 0) ;;; *** |RootOfUnity| REDEFINED ;;; *** |RootOfUnity| REDEFINED Time: 0.01 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.06 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
--------((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 16 JUL 2018 08:02:31 PM): ; /var/aw/var/LatexWiki/ROU.NRLIB/ROU.fasl written ; compilation finished in 0:00:00.042 ------------------------------------------------------------------------ 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 fricas --)co rootunity Example --RNG ==> Complex Expression Integer RNG ==> Expression Complex Integer Type: Void fricas z:RNG Type: Void fricas r:=rootsOf(z^5-1)  (1) Type: List(Expression(Complex(Integer))) fricas R==>RootOfUnity(5,RNG) Type: Void fricas q:=[convert(t)$R for t in r]
 (2)
Type: List(RootOfUnity?(5,Expression(Complex(Integer))))
fricas
primitive?(1$R)  (3) Type: Boolean fricas pb:=[primitive?(t) for t in q]  (4) Type: List(Boolean) fricas test(q.1=q.2)  (5) Type: Boolean fricas q.1^5  (6) Type: RootOfUnity?(5,Expression(Complex(Integer))) fricas q.1^6  (7) Type: RootOfUnity?(5,Expression(Complex(Integer))) fricas q.1^15  (8) Type: RootOfUnity?(5,Expression(Complex(Integer))) fricas sample()$R
 (9)
Type: RootOfUnity?(5,Expression(Complex(Integer)))
fricas
one? sample()$R  (10) Type: Boolean fricas inv(q.1)  (11) Type: RootOfUnity?(5,Expression(Complex(Integer))) fricas q12:=inv(q.1*q.2)  (12) Type: RootOfUnity?(5,Expression(Complex(Integer))) fricas q12^5  (13) Type: RootOfUnity?(5,Expression(Complex(Integer))) fricas principal?(q.1)  (14) Type: Boolean fricas principal?(q.3*q.1)  (15) Type: Boolean fricas -- using solve instead of rootsOf rs5:=solve(z::RNG^5=1$RNG,'z)
 (16)
Type: List(Equation(Expression(Complex(Integer))))
fricas
qrs5:=[convert(rhs t)$R for t in rs5]  (17) Type: List(RootOfUnity?(5,Expression(Complex(Integer)))) fricas p5:=[primitive?(t) for t in qrs5]  (18) Type: List(Boolean) fricas l5:=[principal?(t) for t in qrs5]  (19) Type: List(Boolean) fricas test (qrs5.2=q.2/q.1)  (20) Type: Boolean fricas -- using zerosOf rz5:=zerosOf(z::RNG^5-1$RNG)
 (21)
Type: List(Expression(Complex(Integer)))
fricas
qrz5:=[convert(t)\$R for t in rz5]
 (22)
Type: List(RootOfUnity?(5,Expression(Complex(Integer))))
fricas
pz5:=[primitive?(t) for t in qrz5]
 (23)
Type: List(Boolean)
fricas
lz5:=[principal?(t) for t in qrz5]
 (24)
Type: List(Boolean)