MathAction SandBoxRootOfUnity

Topics

FrontPage
- SandBox
  - SandBoxRootOfUnity <-- You are here.

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)

Subject: Be Bold !!

	( 14 subscribers )