|
|
|
last edited 6 years ago by pagani |
Edit detail for SandBoxRootOfUnity revision 1 of 1
| 1 | ||
|
Editor: pagani
Time: 2018/07/16 20:02:31 GMT+0 |
||
| Note: | ||
changed: - \begin{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) \end{spad} 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}
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.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,
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
"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},
; /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/ROUTest flavours
- fricas
--)co rootunity
- Example
--RNG ==> Complex Expression Integer
RNG ==> Expression Complex Integer
Type: Voidfricas
z:RNG
Type: Voidfricasr:=rootsOf(z^5-1)
![\label{eq1}\begin{array}{@{}l}
\displaystyle
\left[ \%z 0, \:{\%z 0 \ \%z 1}, \:{\%z 0 \ {{\%z 1}^{2}}}, \:{\%z 0 \ {{\%z 1}^{3}}}, \: \right.
\
\
\displaystyle
\left.{-{\%z 0 \ {{\%z 1}^{3}}}-{\%z 0 \ {{\%z 1}^{2}}}-{\%z 0 \ \%z 1}- \%z 0}\right]](images/8396991247490974845-16.0px.png "\label{eq1}\begin{array}{@{}l}
\displaystyle
\left[ \%z 0, \:{\%z 0 \ \%z 1}, \:{\%z 0 \ {{\%z 1}^{2}}}, \:{\%z 0 \ {{\%z 1}^{3}}}, \: \right.
\
\
\displaystyle
\left.{-{\%z 0 \ {{\%z 1}^{3}}}-{\%z 0 \ {{\%z 1}^{2}}}-{\%z 0 \ \%z 1}- \%z 0}\right]")
(1) Type: List(Expression(Complex(Integer)))fricasR==>RootOfUnity(5,
RNG) Type: Voidfricasq:=[convert(t)$R for t in r]
![\label{eq2}\begin{array}{@{}l}
\displaystyle
\left[ \%z 0, \:{\%z 0 \ \%z 1}, \:{\%z 0 \ {{\%z 1}^{2}}}, \:{\%z 0 \ {{\%z 1}^{3}}}, \: \right.
\
\
\displaystyle
\left.{-{\%z 0 \ {{\%z 1}^{3}}}-{\%z 0 \ {{\%z 1}^{2}}}-{\%z 0 \ \%z 1}- \%z 0}\right]](images/8078204916123528402-16.0px.png "\label{eq2}\begin{array}{@{}l}
\displaystyle
\left[ \%z 0, \:{\%z 0 \ \%z 1}, \:{\%z 0 \ {{\%z 1}^{2}}}, \:{\%z 0 \ {{\%z 1}^{3}}}, \: \right.
\
\
\displaystyle
\left.{-{\%z 0 \ {{\%z 1}^{3}}}-{\%z 0 \ {{\%z 1}^{2}}}-{\%z 0 \ \%z 1}- \%z 0}\right]")
(2) Type: List(RootOfUnity?(5,Expression(Complex(Integer)))) fricasprimitive?(1$R)
(3) Type: Booleanfricaspb:=[primitive?(t) for t in q]
![\label{eq4}\left[ \mbox{\rm true} , \: \mbox{\rm true} , \: \mbox{\rm true} , \: \mbox{\rm true} , \: \mbox{\rm true} \right]](images/1330465003247214193-16.0px.png "\label{eq4}\left[ \mbox{\rm true} , \: \mbox{\rm true} , \: \mbox{\rm true} , \: \mbox{\rm true} , \: \mbox{\rm true} \right]")
(4) Type: List(Boolean)fricastest(q.1=q.2)
(5) Type: Booleanfricasq.1^5
(6) Type: RootOfUnity?(5,Expression(Complex(Integer))) fricasq.1^6
(7) Type: RootOfUnity?(5,Expression(Complex(Integer))) fricasq.1^15
(8) Type: RootOfUnity?(5,Expression(Complex(Integer))) fricassample()$R
(9) Type: RootOfUnity?(5,Expression(Complex(Integer))) fricasone? sample()$R
(10) Type: Booleanfricasinv(q.1)
(11) Type: RootOfUnity?(5,Expression(Complex(Integer))) fricasq12:=inv(q.1*q.2)
(12) Type: RootOfUnity?(5,Expression(Complex(Integer))) fricasq12^5
(13) Type: RootOfUnity?(5,Expression(Complex(Integer))) fricasprincipal?(q.1)
(14) Type: Booleanfricasprincipal?(q.3*q.1)
(15) Type: Booleanfricas-- using solve instead of rootsOf
rs5:=solve(z::RNG^5=1$RNG,'z) ![\label{eq16}\begin{array}{@{}l}
\displaystyle
\left[{z = 1}, \:{z = \%z 1}, \:{z = \%z 4}, \: \right.
\
\
\displaystyle
\left.{
\begin{array}{@{}l}
\displaystyle
z ={{\left(
\begin{array}{@{}l}
\displaystyle
{i \ {\sqrt{{3 \ {{\%z 4}^{2}}}+{{\left({2 \ \%z 1}+ 2 \right)}\ \%z 4}+{3 \ {{\%z 1}^{2}}}+{2 \ \%z 1}+ 3}}}-
\
\
\displaystyle
\%z 4 - \%z 1 - 1](images/9206817506720692809-16.0px.png "\label{eq16}\begin{array}{@{}l}
\displaystyle
\left[{z = 1}, \:{z = \%z 1}, \:{z = \%z 4}, \: \right.
\
\
\displaystyle
\left.{
\begin{array}{@{}l}
\displaystyle
z ={{\left(
\begin{array}{@{}l}
\displaystyle
{i \ {\sqrt{{3 \ {{\%z 4}^{2}}}+{{\left({2 \ \%z 1}+ 2 \right)}\ \%z 4}+{3 \ {{\%z 1}^{2}}}+{2 \ \%z 1}+ 3}}}-
\
\
\displaystyle
\%z 4 - \%z 1 - 1")
(16) Type: List(Equation(Expression(Complex(Integer))))fricasqrs5:=[convert(rhs t)$R for t in rs5]
![\label{eq17}\begin{array}{@{}l}
\displaystyle
\left[ 1, \: \%z 1, \: \%z 4, \: \right.
\
\
\displaystyle
\left.{{\left(
\begin{array}{@{}l}
\displaystyle
{i \ {\sqrt{{3 \ {{\%z 4}^{2}}}+{{\left({2 \ \%z 1}+ 2 \right)}\ \%z 4}+{3 \ {{\%z 1}^{2}}}+{2 \ \%z 1}+ 3}}}-
\
\
\displaystyle
\%z 4 - \%z 1 - 1](images/2324370568911553176-16.0px.png "\label{eq17}\begin{array}{@{}l}
\displaystyle
\left[ 1, \: \%z 1, \: \%z 4, \: \right.
\
\
\displaystyle
\left.{{\left(
\begin{array}{@{}l}
\displaystyle
{i \ {\sqrt{{3 \ {{\%z 4}^{2}}}+{{\left({2 \ \%z 1}+ 2 \right)}\ \%z 4}+{3 \ {{\%z 1}^{2}}}+{2 \ \%z 1}+ 3}}}-
\
\
\displaystyle
\%z 4 - \%z 1 - 1")
(17) Type: List(RootOfUnity?(5,Expression(Complex(Integer)))) fricasp5:=[primitive?(t) for t in qrs5]
![\label{eq18}\left[ \mbox{\rm false} , \: \mbox{\rm true} , \: \mbox{\rm true} , \: \mbox{\rm true} , \: \mbox{\rm true} \right]](images/5071536280549151367-16.0px.png "\label{eq18}\left[ \mbox{\rm false} , \: \mbox{\rm true} , \: \mbox{\rm true} , \: \mbox{\rm true} , \: \mbox{\rm true} \right]")
(18) Type: List(Boolean)fricasl5:=[principal?(t) for t in qrs5]
![\label{eq19}\left[ \mbox{\rm false} , \: \mbox{\rm true} , \: \mbox{\rm true} , \: \mbox{\rm true} , \: \mbox{\rm true} \right]](images/205568610214053954-16.0px.png "\label{eq19}\left[ \mbox{\rm false} , \: \mbox{\rm true} , \: \mbox{\rm true} , \: \mbox{\rm true} , \: \mbox{\rm true} \right]")
(19) Type: List(Boolean)fricastest (qrs5.2=q.2/q.1)
(20) Type: Booleanfricas-- using zerosOf rz5:=zerosOf(z::RNG^5-1$RNG)
![\label{eq21}\left[ 1, \: \%z 1, \:{{\%z 1}^{2}}, \:{{\%z 1}^{3}}, \:{-{{\%z 1}^{3}}-{{\%z 1}^{2}}- \%z 1 - 1}\right]](images/1195728032782707965-16.0px.png "\label{eq21}\left[ 1, \: \%z 1, \:{{\%z 1}^{2}}, \:{{\%z 1}^{3}}, \:{-{{\%z 1}^{3}}-{{\%z 1}^{2}}- \%z 1 - 1}\right]")
(21) Type: List(Expression(Complex(Integer)))fricasqrz5:=[convert(t)$R for t in rz5]
![\label{eq22}\left[ 1, \: \%z 1, \:{{\%z 1}^{2}}, \:{{\%z 1}^{3}}, \:{-{{\%z 1}^{3}}-{{\%z 1}^{2}}- \%z 1 - 1}\right]](images/790334570644819020-16.0px.png "\label{eq22}\left[ 1, \: \%z 1, \:{{\%z 1}^{2}}, \:{{\%z 1}^{3}}, \:{-{{\%z 1}^{3}}-{{\%z 1}^{2}}- \%z 1 - 1}\right]")
(22) Type: List(RootOfUnity?(5,Expression(Complex(Integer)))) fricaspz5:=[primitive?(t) for t in qrz5]
![\label{eq23}\left[ \mbox{\rm false} , \: \mbox{\rm true} , \: \mbox{\rm true} , \: \mbox{\rm true} , \: \mbox{\rm true} \right]](images/7234835071511637907-16.0px.png "\label{eq23}\left[ \mbox{\rm false} , \: \mbox{\rm true} , \: \mbox{\rm true} , \: \mbox{\rm true} , \: \mbox{\rm true} \right]")
(23) Type: List(Boolean)fricaslz5:=[principal?(t) for t in qrz5]
![\label{eq24}\left[ \mbox{\rm false} , \: \mbox{\rm true} , \: \mbox{\rm true} , \: \mbox{\rm true} , \: \mbox{\rm true} \right]](images/2333209751893379678-16.0px.png "\label{eq24}\left[ \mbox{\rm false} , \: \mbox{\rm true} , \: \mbox{\rm true} , \: \mbox{\rm true} , \: \mbox{\rm true} \right]")
(24) Type: List(Boolean)