In the Haskell library Cyclotomic, a cyclotomic number is "encoded" as an integer called the order and a map from the integers to the rationals called the coefficients. Would you have an explanation or/and a reference of this way to implement the cyclotomic numbers? I started to port the Haskell code to the R language but even though I roughly understand the code, I don't understand the idea. I would prefer to understand how it works rather than blindly translating the code.
One can find these comments in the Haskell code:
- Step 1 of cyclotomic is gcd reduction.
- Step 2 of cyclotomic is reduction to a rational if possible.
- Step 3 of cyclotomic is base reduction.
In general:
Given some separable polynomial $p\in\mathbb{Q}[X]$. In this case, a cyclotomic polynomial.
Considering the field $\mathbb{Q}[X]/(p)$. In our case, a cyclotomic field
The elements $x\in\mathbb{Q}[X]/(p)$ of this field can be expressed uniquely as $x=x_0+x_1X+x_2X^2+x_3X^3+\cdots+x_{\mathrm{deg}p-1}X^{\mathrm{deg}p-1}$ where the $x_i$ are elements of $\mathbb{Q}$.
In the general case, you should be careful if not all zeroes of $p$ are in $\mathbb{Q}[X]/(p)$, because then the embedding into $\mathbb{C}$ is more problematic. But when $p$ is a cyclotomic polynomial, all zeroes do appear in this field.
When you want a not-exact implementation, you can take the morphism $\mathbb{Q}[X]/\Phi_n\to\mathbb{C}$ generated by $X\mapsto \zeta_n$ where $\zeta_n=e^{\frac{2\pi i}n}$ is a primitive $n$th root of unity, so you take the coefficients $(x_0,x_1,x_2,\dots,x_{\mathrm{deg}\Phi_n-1})$ and send them to $x_0\cdot1+x_1\cdot \zeta_n+x_2\cdot\zeta_n^2+\cdots+x_{\mathrm{deg}\Phi_n-1}\cdot \zeta_n^{\mathrm{deg}\Phi_n-1}$.
This is not-exact because the exponents $e^{\frac{2k\pi i}n}$ cannot trivially be implemented with infinite precision.
The order in this case is the number of the cyclotomic polynomial $p$. That is, when the order is $n$, the "number" $\zeta_n=0+1\cdot X+0\cdot X^2+\dots+0\cdot X^{\mathrm{deg}\Phi_n-1}$ is exactly a primitive $n$th root of unity.