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:
-
\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,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 "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 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)

\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)))
fricas
R==>RootOfUnity(5,RNG)
Type: Void
fricas
q:=[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] 
(2)
Type: List(RootOfUnity?(5,Expression(Complex(Integer))))
fricas
primitive?(1$R)

\label{eq3} \mbox{\rm false} (3)
Type: Boolean
fricas
pb:=[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](4)
Type: List(Boolean)
fricas
test(q.1=q.2)

\label{eq5} \mbox{\rm false} (5)
Type: Boolean
fricas
q.1^5

\label{eq6}1(6)
Type: RootOfUnity?(5,Expression(Complex(Integer)))
fricas
q.1^6

\label{eq7}\%z 0(7)
Type: RootOfUnity?(5,Expression(Complex(Integer)))
fricas
q.1^15

\label{eq8}1(8)
Type: RootOfUnity?(5,Expression(Complex(Integer)))
fricas
sample()$R

\label{eq9}1(9)
Type: RootOfUnity?(5,Expression(Complex(Integer)))
fricas
one? sample()$R

\label{eq10} \mbox{\rm true} (10)
Type: Boolean
fricas
inv(q.1)

\label{eq11}1 \over \%z 0(11)
Type: RootOfUnity?(5,Expression(Complex(Integer)))
fricas
q12:=inv(q.1*q.2)

\label{eq12}1 \over{{{\%z 0}^{2}}\  \%z 1}(12)
Type: RootOfUnity?(5,Expression(Complex(Integer)))
fricas
q12^5

\label{eq13}1(13)
Type: RootOfUnity?(5,Expression(Complex(Integer)))
fricas
principal?(q.1)

\label{eq14} \mbox{\rm false} (14)
Type: Boolean
fricas
principal?(q.3*q.1)

\label{eq15} \mbox{\rm false} (15)
Type: Boolean
fricas
-- 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 
(16)
Type: List(Equation(Expression(Complex(Integer))))
fricas
qrs5:=[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 
(17)
Type: List(RootOfUnity?(5,Expression(Complex(Integer))))
fricas
p5:=[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](18)
Type: List(Boolean)
fricas
l5:=[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](19)
Type: List(Boolean)
fricas
test (qrs5.2=q.2/q.1)

\label{eq20} \mbox{\rm true} (20)
Type: Boolean
fricas
-- 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](21)
Type: List(Expression(Complex(Integer)))
fricas
qrz5:=[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](22)
Type: List(RootOfUnity?(5,Expression(Complex(Integer))))
fricas
pz5:=[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](23)
Type: List(Boolean)
fricas
lz5:=[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](24)
Type: List(Boolean)