a12-euler.tex

\subsection{Pythagorean Identity}
\label{subsec:pythagorean}



\begin{figure}[!h]
    \centering
    \subfloat[Pythagorean Theorem \href{https://socratic.org/questions/58a20042b72cff17846a6feb}{(Source)}]{
  \includegraphics[width=0.3\linewidth]{figures/pythagorean-theorem.png}

  \label{fig:pythagorean-theorem}
}
    \subfloat[Pythagorean Identity \href{https://socratic.org/questions/58a20042b72cff17846a6feb}{(Source)}]{
  \includegraphics[width=0.3\linewidth]{figures/pythagorean-identity.png}

  \label{fig:pythagorean-identity}
}
  \caption{}
\end{figure}

\begin{tcolorbox}[title={\textbf{\tboxtheorem{\ref*{subsec:pythagorean}} Pythagorean Identity}}]
$\sin^2 \theta + \cos^2 \theta = 1$
\end{tcolorbox}

\begin{proof}
$ $
\begin{enumerate}

\item In \autoref{fig:pythagorean-theorem}, by Pythagorean theorem, $a^2 + b^2 = c^2$.

\item In \autoref{fig:pythagorean-identity}, by definition of sin and cosine,

$\sin\theta = \dfrac{a}{c}, \text{ } \cos\theta = \dfrac{b}{c}$

\item Combining step 1 and 2:

$\sin^2 \theta + \cos^2 \theta = \dfrac{a^2}{c^2} + \dfrac{b^2}{c^2} = \dfrac{a^2 + b^2}{c^2} = 1$


\end{enumerate}
\end{proof}

\subsection{Imaginary Number}n
\label{subsec:imaginary}


\begin{tcolorbox}[title={\textbf{\tboxdef{\ref*{subsec:imaginary}} Imaginary Number}}]

\begin{itemize}

\item \boldmath{$i$} is defined to be an imaginary number that has the property: $i^2 =-1$
\item \textbf{Complex Number} is a number of the form $a + b\,i$, where $a$ and $b$ are real numbers (e.g., $a = 5.6 + 4.3i)$

\item \textbf{Real Number} is a number that does not involve any imaginary number (e.g., $a = 13.4$)

\item $\overline{a}$ is a \textbf{Conjugate} of $a$ if $a$ and $\overline{a}$ have the same real number part and an opposite-signed imaginary number part

(e.g., $a = 3 + i\cdot3.4$, \text{ } $\overline{a} = 3 - i\cdot3.4$)

\item \textbf{Hermitian Vector} is a vector where the 2nd half of its elements is the complex conjugate of the 1st half in reverse order, as illustrated by the $n$-dimensional vector below:

$\vec{v} = (v_1, v_2, v_3, \cdots, v_{\frac{n}{2}-1}, v_{\frac{n}{2}}, \overline{v}_{\frac{n}{2}}, \overline{v}_{\frac{n}{2} - 1}, \cdots, \overline{v}_3, \overline{v}_2, \overline{v}_1)$


\end{itemize}
\end{tcolorbox}



\subsection{Euler's Formula}
\label{subsec:euler}




\begin{tcolorbox}[title={\textbf{\tboxdef{\ref*{subsec:euler}} Euler's Formula}}]

$e^{i\theta} = \cos\theta + i\cdot\sin\theta$

\end{tcolorbox}

\begin{figure}[!h]
    \centering
  \includegraphics[width=0.4\linewidth]{figures/euler-formula.png}
  \caption{The figure illustrates Euler's formula on the unit circle in the complex plane \href{https://en.wikipedia.org/wiki/Euler's_formula}{(Source)}}
\end{figure}

The value of $e^{i\theta}$ is represented as a coordinate on a circle in the complex plane in \autoref{fig:complex-plane}, where the $x$-axis encodes the value's real number part and the $y$-axis encodes the value's imaginary number part. Note that as $\theta$ increases, the imaginary part ($\sin\theta$) oscillates between $1$ and $-1$ (reaching $i$ and $-i$ on the imaginary axis), and the real part ($\cos\theta$) oscillates between $1$ and $-1$, with period $2\pi$.


\subsection{Vandermonde Matrix with Roots of Cyclotomic Polynomial over Complex Numbers}
\label{subsec:vandermonde-euler}

 
 
In this subsection, we will build a Vandermonde matrix (\autoref{subsec:vandermonde}) with the $n$ distinct roots of the $\mu$-th cyclotomic polynomial over complex numbers (where $\mu$ is a power of 2) as follows:



\begin{tcolorbox}[title={\textbf{\tboxtheorem{\ref*{subsec:vandermonde-euler}} Vandermonde Matrix with the Roots of  \text{(power-of-2)}-th Cyclotomic Polynomial over Complex Numbers}}]

Suppose we have an $n \times n$ (where $n$ is a power of 2) Vandermonde matrix comprised of $n$ distinct roots of the $\mu$-th cyclotomic polynomial (explained in Theorem~\ref*{subsec:cyclotomic-theorem}.1 in \autoref{subsec:cyclotomic-theorem}), where $\mu$ is a power of 2 and $n = \dfrac{\mu}{2}$. In other words, $V = \mathit{Vander}(x_0, x_1, \cdots, x_{n-1})$, where each $x_j = (e^{i\pi/n})^{2j-1}$ for $1 \leq j \leq n$ (i.e., the primitive $\mu$-th roots of unity). Then, the following holds:

$V \cdot V^T = \begin{bmatrix}
0 & \cdots & 0 & 0 & n\\
0 & \cdots & 0 & n & 0\\
0 & \cdots & n & 0 & 0\\
\vdots & \iddots & \vdots & \vdots & \vdots \\
n & 0 & 0 & \cdots & 0\\
\end{bmatrix} = n \cdot I^R_n$

$ $

And $V^{-1} = \dfrac{V^T \cdot I_n^R}{n}$


\end{tcolorbox}

\begin{proof}

$ $

\begin{enumerate}

\item Given $\omega = e^{i\pi/n}$, each $x_j = (\omega)^{2j-1}$. Thus, we can expand as follows:

$V \cdot V^T = \begin{bmatrix}
1 & (\omega) & (\omega)^2 & \cdots & (\omega)^{n-1}\\
1 & (\omega^3) & (\omega^3)^2 & \cdots & (\omega^3)^{n-1}\\
1 & (\omega^5) & (\omega^5)^2 & \cdots & (\omega^5)^{n-1}\\
\vdots & \vdots & \vdots & \ddots & \vdots \\
1 & (\omega^{2n-1}) & (\omega^{2n-1})^2 & \cdots & (\omega^{2n-1})^{n-1}\\
\end{bmatrix} 
\cdot 
\begin{bmatrix}
1 & 1 & 1 & \cdots & 1\\
(\omega) & (\omega^3) & (\omega^5) & \cdots & (\omega^{2n-1})\\
(\omega)^2 & (\omega^3)^2 & (\omega^5)^2 & \cdots & (\omega^{2n-1})^2\\
\vdots & \vdots & \vdots & \ddots & \vdots \\
(\omega)^{n-1} & (\omega^3)^{n-1} & (\omega^5)^{n-1} & \cdots & (\omega^{2n-1})^{n-1}\\
\end{bmatrix} $

$ $


$=
\begin{bmatrix}
\sum\limits_{k=0}^{n-1} \omega^{2k} & \sum\limits_{k=0}^{n-1} \omega^{4k}  & \sum\limits_{k=0}^{n-1} \omega^{6k} & \cdots & \sum\limits_{k=0}^{n-1} \omega^{2nk} \\

\sum\limits_{k=0}^{n-1} \omega^{4k} & \sum\limits_{k=0}^{n-1} \omega^{6k}  & \sum\limits_{k=0}^{n-1} \omega^{8k} & \cdots & \sum\limits_{k=0}^{n-1} \omega^{2k(n+1)} \\

\sum\limits_{k=0}^{n-1} \omega^{6k} & \sum\limits_{k=0}^{n-1} \omega^{8k} & \sum\limits_{k=0}^{n-1} \omega^{10k} & \cdots & \sum\limits_{k=0}^{n-1} \omega^{2k(n+2)} \\

\vdots & \vdots & \vdots & \ddots & \vdots \\
\sum\limits_{k=0}^{n-1} \omega^{2nk} & \sum\limits_{k=0}^{n-1} \omega^{2(n+1)k} & \sum\limits_{k=0}^{n-1} \omega^{2(n+2)k} & \cdots & \sum\limits_{k=0}^{n-1} \omega^{2(n+n-1)k} \\

\end{bmatrix}$

$ $

\item The $V \cdot V^T$ matrix's anti-diagonal elements are $\sum\limits_{k=0}^{n-1} \omega^{2nk}$. We can derive the following:

$\sum\limits_{k=0}^{n-1} \omega^{2nk} = \sum\limits_{k=0}^{n-1} (e^{i\pi/n})^{2nk} = \sum\limits_{k=0}^{n-1}e^{2\pi k i} = \sum\limits_{k=0}^{n-1}(\cos(2\pi k) + i\sin(2\pi k)) = \sum\limits_{k=0}^{n-1} (1 + 0) = n$

This means that The $V \cdot V^T$ matrix's anti-diagonal elements are $n$. 

$ $

\item Next, we will prove that the $V \cdot V^T$ matrix has 0 for all positions except for the anti-diagonal ones. In other words, we will prove the following: 

$\sum\limits_{k=0}^{n-1} \omega^{2k} = \sum\limits_{k=0}^{n-1} \omega^{4k} = \sum\limits_{k=0}^{n-1} \omega^{6k} = \cdots = \sum\limits_{k=0}^{n-1} \omega^{2(n-1)k} = \sum\limits_{k=0}^{n-1} \omega^{2(n+1)k} = \cdots = \sum\limits_{k=0}^{n-1} \omega^{2(2n-1)k} = 0$

For this proof, we will leverage the Geometric Sum formula $\sum\limits_{i=0}^{n-1}x^i = \dfrac{x^n - 1}{x - 1}$:

\begin{tcolorbox}[title={\textbf{\tboxtheorem{\ref*{subsec:vandermonde-euler}.1} Geometric Sum Formula}}]

Let the geometric sum $S_n = 1 + x + x^2 + \cdots + x^{n - 1}$

Then, $x \cdot S_n = x + x^2 + x^3 + \cdots + x^{n}$

$x \cdot S_n - S_n = (x + x^2 + x^3 + \cdots + x^{n}) - (1 + x + x^2 + \cdots + x^{n - 1}) = x^n - 1$

$S_n\cdot (x - 1) = x^n - 1$

$S_n = \dfrac{x^n - 1}{x - 1}$ \textcolor{red}{ $\rhd$ with the constraint that $x \neq 1$}

\end{tcolorbox}

Leveraging the Geometric Sum formula $\sum\limits_{i=0}^{n-1}x^i = \dfrac{x^n - 1}{x - 1}$, 

$\sum\limits_{k=0}^{n-1} \omega^{2mk} = \dfrac{(\omega^{2m})^n - 1}{\omega^{2m} - 1} = \dfrac{(\omega^{2n})^{m} - 1}{\omega^{2m} - 1} = \dfrac{1 - 1}{\omega^{2m} - 1} = 0$ for $1 \leq m \leq (2n - 1)$  \textcolor{red}{ $\rhd$ since $\textsf{Ord}(\omega) = 2n$}

$ $

Therefore,

$\sum\limits_{k=0}^{n-1} \omega^{2k} = \sum\limits_{k=0}^{n-1} \omega^{4k} = \sum\limits_{k=0}^{n-1} \omega^{6k} = \cdots = \sum\limits_{k=0}^{n-1} \omega^{2(n-1)k} = \sum\limits_{k=0}^{n-1} \omega^{2(n+1)k} = \cdots = \sum\limits_{k=0}^{n-1} \omega^{2(2n-1)k} = 0$

$ $

\item Based on the proof of step 2 and 3, $V \cdot V^T = 
\begin{bmatrix}
0 & \cdots & 0 & 0 & n\\
0 & \cdots & 0 & n & 0\\
0 & \cdots & n & 0 & 0\\
\vdots & \iddots & \vdots & \vdots & \vdots \\
n & 0 & 0 & \cdots & 0\\
\end{bmatrix} = n \cdot I_n^R$

\item Given $V \cdot V^T = n \cdot I_n^R$, 

$V^{-1} \cdot V \cdot V^T = V^{-1} \cdot n \cdot I_n^R$

$V^T = V^{-1} \cdot n \cdot I_n^R$

$V^T \cdot I_n^R = V^{-1} \cdot n \cdot I_n^R  \cdot I_n^R$

$V^T \cdot I_n^R = V^{-1} \cdot n$ \textcolor{red}{\text{ } \# since $I_n^R  \cdot I_n^R = I_n$}

$V^{-1} = \dfrac{V^T \cdot I_n^R}{n}$

\end{enumerate}
\end{proof}

Later in the CKKS scheme (\autoref{sec:ckks}), we will use $V^{-1}$ to encode a complex vector into a real number vector, and $V^T$ to decode a real number vector into a complex vector (\autoref{subsec:ckks-enc-dec}).

$ $

%\para{Condition for $\bm \mu$:} It's worthwhile to note that the property $V\cdot V^T = n\cdot I_n^R$ does not hold if $\mu$ (denoting the $\mu$-th cyclotomic polynomial) is not a power of 2. In particular, step 3 of the proof does not hold anymore if $\mu$ is not a power of 2:

%$\sum\limits_{k=0}^{n-1} \omega^{2k} \neq \sum\limits_{k=0}^{n-1} \omega^{4k} \neq \sum\limits_{k=0}^{n-1} \omega^{6k} \neq \cdots \neq \sum\limits_{k=0}^{n-1} \omega^{2(n-1)k} \neq \sum\limits_{k=0}^{n-1} \omega^{2(n+1)k} \neq \cdots \neq \sum\limits_{k=0}^{n-1} \omega^{2(2n-1)k} \neq 0$


\para{Condition for $\bm \mu$:} The identity $V \cdot V^T = n \cdot I_n^R$ relies only on
$\textsf{Ord}(\omega) = 2n$ (step 3), so it holds for any $\mu = 2n$ (i.e., any even number).
The nodes $\omega, \omega^3, \ldots, \omega^{2n-1}$ are likewise the $n$ roots of $X^n + 1$
for any $n$, since $(\omega^{2j-1})^n = \omega^{2nj}\cdot\omega^{-n} = 1\cdot(-1) = -1$.

Nevertheless, the reason we take $\mu$ to be a power of 2 does not come from this theorem, but
from the FHE schemes themselves. In practice, CKKS, BFV, and BGV are most commonly instantiated
over the power-of-2 cyclotomic ring $\mathbb{Z}[X]/(X^n + 1)$ with $n$ a power of 2, because this choice makes $X^n + 1 = \Phi_{2n}(X)$ irreducible over rational numbers (which holds
precisely when $n$ is a power of 2), and also enables efficient negacyclic-NTT multiplication
and a clean Ring-LWE security reduction. Once
$n$ (hence $\mu = 2n$) is fixed as a power of 2, the nodes are automatically the primitive
$\mu$-th roots of unity: by Theorem~\ref*{subsec:roots-theorem}.4 (\autoref{subsec:roots-theorem}),
$\omega^k$ is a primitive $\mu$-th root iff $\gcd(\mu, k) = 1$, and every odd exponent
$1, 3, \ldots, 2n-1$ is coprime to $\mu = 2n$ iff $2n$ has no odd prime factor---i.e.\ iff $2n$
is a power of 2. So $\{\omega, \omega^3, \ldots, \omega^{2n-1}\}$ being exactly the primitive
$(\mu=2n)$-th roots is a consequence of the power-of-2 ring choice. Meanwhile, as far as $\mu$ is an even number, $V \cdot V^T = n \cdot I_n^R$ still holds.



\subsection{Vandermonde Matrix with Roots of Cyclotomic Polynomial over Ring ($\mathbb{Z}_p$)}
\label{subsec:vandermonde-euler-integer-ring}

Theorem~\ref*{subsec:vandermonde-euler} (in \autoref{subsec:vandermonde-euler}) showed that $V \cdot V^T = n \cdot I^R_n$, where $V$ is the Vandermonde matrix $V = \mathit{Vander}(x_0, x_1, \cdots, x_{n-1})$, where each $x_i$ is the primitive $\mu$-th root of unity over $X \in \mathbb{C}$ (i.e., complex number) and $\mu$ is a power of 2. In this subsection, we will show that the relation $V \cdot V^T = n \cdot I^R_n$ holds even if each $x_i$ is the primitive $\mu$-th root of unity over $X \in \mathbb{Z}_p$ (i.e., ring). In particular, we will prove Theorem~\ref*{subsec:vandermonde-euler}: 


\begin{tcolorbox}[title={\textbf{\tboxtheorem{\ref*{subsec:vandermonde-euler-integer-ring}} Vandermonde Matrix with Roots of  \text{(power-of-2)}-th Cyclotomic Polynomial over Ring ($\mathbb{Z}_p$)}}]

The proof takes the same format as that of Theorem~\ref*{subsec:vandermonde-euler} (in \autoref{subsec:vandermonde-euler}). Suppose we have an $n \times n$ (where $n$ is a power of 2) Vandermonde matrix comprising $n$ distinct roots of the $\mu$-th cyclotomic polynomial over $X \in \mathbb{Z}_p$ (ring), where $\mu$ is a power of 2 and $n = \dfrac{\mu}{2}$. In other words, $V = \mathit{Vander}(x_0, x_1, \cdots, x_{n-1})$, where each $x_i$ is the root of $X^n + 1$ (i.e., the primitive $(\mu=2n)$-th roots of unity). Then, the following holds:

$V \cdot V^T = \begin{bmatrix}
0 & \cdots & 0 & 0 & n\\
0 & \cdots & 0 & n & 0\\
0 & \cdots & n & 0 & 0\\
\vdots & \iddots & \vdots & \vdots & \vdots \\
n & 0 & 0 & \cdots & 0\\
\end{bmatrix} = n \cdot I^R_n$

$ $

And $V^{-1} = n^{-1}\cdot V^T \cdot I_n^R$


\end{tcolorbox}
\begin{proof}
$ $
\begin{enumerate}
\item $V \cdot V^T$ is expanded as follows:

$V \cdot V^T = \begin{bmatrix}
1 & (\omega) & (\omega)^2 & \cdots & (\omega)^{n-1}\\
1 & (\omega^3) & (\omega^3)^2 & \cdots & (\omega^3)^{n-1}\\
1 & (\omega^5) & (\omega^5)^2 & \cdots & (\omega^5)^{n-1}\\
\vdots & \vdots & \vdots & \ddots & \vdots \\
1 & (\omega^{2n-1}) & (\omega^{2n-1})^2 & \cdots & (\omega^{2n-1})^{n-1}\\
\end{bmatrix} 
\cdot 
\begin{bmatrix}
1 & 1 & 1 & \cdots & 1\\
(\omega) & (\omega^3) & (\omega^5) & \cdots & (\omega^{2n-1})\\
(\omega)^2 & (\omega^3)^2 & (\omega^5)^2 & \cdots & (\omega^{2n-1})^2\\
\vdots & \vdots & \vdots & \ddots & \vdots \\
(\omega)^{n-1} & (\omega^3)^{n-1} & (\omega^5)^{n-1} & \cdots & (\omega^{2n-1})^{n-1}\\
\end{bmatrix} $

$ $


$=
\begin{bmatrix}
\sum\limits_{k=0}^{n-1} \omega^{2k} & \sum\limits_{k=0}^{n-1} \omega^{4k}  & \sum\limits_{k=0}^{n-1} \omega^{6k} & \cdots & \sum\limits_{k=0}^{n-1} \omega^{2nk} \\

\sum\limits_{k=0}^{n-1} \omega^{4k} & \sum\limits_{k=0}^{n-1} \omega^{6k}  & \sum\limits_{k=0}^{n-1} \omega^{8k} & \cdots & \sum\limits_{k=0}^{n-1} \omega^{2k(n+1)} \\

\sum\limits_{k=0}^{n-1} \omega^{6k} & \sum\limits_{k=0}^{n-1} \omega^{8k} & \sum\limits_{k=0}^{n-1} \omega^{10k} & \cdots & \sum\limits_{k=0}^{n-1} \omega^{2k(n+2)} \\

\vdots & \vdots & \vdots & \ddots & \vdots \\
\sum\limits_{k=0}^{n-1} \omega^{2nk} & \sum\limits_{k=0}^{n-1} \omega^{2(n+1)k} & \sum\limits_{k=0}^{n-1} \omega^{2(n+2)k} & \cdots & \sum\limits_{k=0}^{n-1} \omega^{2(n+n-1)k} \\

\end{bmatrix}$

$ $

, where $\omega$ (i.e., the primitive $(\mu=2n)$-th root of unity) has the order $2n$. 

$ $

\item Note that the $V \cdot V^T$ matrix's anti-diagonal elements are $\sum\limits_{k=0}^{n-1} \omega^{2nk}$. It can be seen that $\omega^{2n} \equiv 1 \bmod p$, because $\textsf{Ord}_p(\omega) = 2n$. Thus, the $V \cdot V^T$ matrix's every anti-diagonal element is $\sum\limits_{k=0}^{n-1} 1 = n$.

$ $

\item Next, we will prove that the $V \cdot V^T$ matrix has $0$ for all other positions than the anti-diagonal ones. In other words, we will prove the following: 

$\sum\limits_{k=0}^{n-1} \omega^{2k} = \sum\limits_{k=0}^{n-1} \omega^{4k} = \sum\limits_{k=0}^{n-1} \omega^{6k} = \cdots = \sum\limits_{k=0}^{n-1} \omega^{2(n-1)k} = \sum\limits_{k=0}^{n-1} \omega^{2(n+1)k} = \cdots = \sum\limits_{k=0}^{n-1} \omega^{2(2n-1)k} = 0$

$ $

The above is true by the Geometric Sum formula (Theorem~\ref*{subsec:vandermonde-euler}.1). As shown in the proof step 3 of Theorem~\ref*{subsec:vandermonde-euler}, each element is of the form $\sum_{k=0}^{n-1} (\omega^{2m})^k$ for some integer $m$ (where $2m$ is not a multiple of $2n$). Let $r = \omega^{2m}$. Then:

$\sum\limits_{k=0}^{n-1} r^k = \dfrac{r^n - 1}{r - 1} = \dfrac{(\omega^{2m})^n - 1}{\omega^{2m} - 1} = \dfrac{(\omega^n)^{2m} - 1}{\omega^{2m} - 1}$

$ $

Since $\omega$ is a root of $X^n + 1$, we know $\omega^n \equiv -1 \bmod p$. Thus:

$\dfrac{(-1)^{2m} - 1}{\omega^{2m} - 1} = \dfrac{1 - 1}{\omega^{2m} - 1} = 0$

$ $

Therefore, the sum is 0 for all off-anti-diagonal positions.

$ $

\item According to step 1 and 2, the $V \cdot V^T$ matrix has $n$ on its anti-diagonal positions and $0$ for all other positions.

\item Now we will derive the formula for $V^{-1}$. Given $V \cdot V^T = n \cdot I_n^R$, 

$V^{-1} \cdot V \cdot V^T = V^{-1} \cdot n \cdot I_n^R$

$V^T = V^{-1} \cdot n \cdot I_n^R$

$V^T \cdot I_n^R = V^{-1} \cdot n \cdot I_n^R  \cdot I_n^R$

$V^T \cdot I_n^R = V^{-1} \cdot n$ \textcolor{red}{\text{ } \# since $I_n^R  \cdot I_n^R = I_n$}

$ $

Now, there is one caveat: modulo operation does not support direct number division (as explained in \autoref{subsec:modulo-division}). This means that the formula $V^{-1} = \dfrac{V^T \cdot I_n^R}{n}$ in Theorem~\ref*{subsec:vandermonde-euler} (in \autoref{subsec:vandermonde-euler}) is inapplicable in our case, because our modulo $p$ arithmetic does not allow direct division of $V^T \cdot I_n^R$ by $n$. Therefore, we instead multiply $V^T \cdot I_n^R$ by the inverse of $n$ (i.e., $n^{-1}$). We continue as follows:

$V^T \cdot I_n^R = V^{-1} \cdot n$

$V^T \cdot I_n^R \cdot n^{-1}= V^{-1} \cdot n \cdot n^{-1}$

$V^{-1} = n^{-1}\cdot V^T \cdot I_n^R$

\end{enumerate}
\end{proof}

We finally proved that $V\cdot V^T = n \cdot I_n^R$, and $V^{-1} = n^{-1}\cdot V^T \cdot I_n^R$. Later in the BFV scheme (\autoref{sec:bfv}), we will use $V^{-1}$ to encode an integer vector into a vector of polynomial coefficients, and $V^T$ to decode it back to the integer vector (\autoref{subsec:bfv-batch-encoding}).

$ $

\para{Condition for $\bm \mu$:} Like in CKKS, it's worthwhile to note that the property $V\cdot V^T = n\cdot I_n^R$ does not hold if $\mu$ (denoting the $\mu$-th cyclotomic polynomial) is not a power of 2. In particular, step 3 of the proof does not hold anymore if $\mu$ is not a power of 2:

$\sum\limits_{k=0}^{n-1} \omega^{2k} \neq \sum\limits_{k=0}^{n-1} \omega^{4k} \neq \sum\limits_{k=0}^{n-1} \omega^{6k} \neq \cdots \neq \sum\limits_{k=0}^{n-1} \omega^{2(n-1)k} \neq \sum\limits_{k=0}^{n-1} \omega^{2(n+1)k} \neq \cdots \neq \sum\limits_{k=0}^{n-1} \omega^{2(2n-1)k} \neq 0$