# Isomorphism of Canonical Embedding

[TOC]

We prove the Canonical Embedding map $\sigma$ is an **isometric ring isomorphism** between the polynomial quotient ring and the complex vector space.

## Definition of the Map:
Let $\mathcal{K} = \mathbb{Q}[X]/(\Phi_M(X))$. The map $\sigma: \mathcal{K} \rightarrow \mathbb{C}^N$ is defined as:
$$\sigma(a(X)) = (a(\zeta_0), a(\zeta_1), \dots, a(\zeta_{N-1}))$$ where $\zeta_j$ are the distinct complex roots of $\Phi_M(X)$.

## Homomorphism (Preserves Structure)
A map is a homomorphism if it preserves addition and multiplication. Let $a(X), b(X) \in \mathcal{K}$.

### Addition
This holds because polynomial evaluation is distributive over addition.
$$\sigma(a + b) = ((a+b)(\zeta_0), \dots) = (a(\zeta_0) + b(\zeta_0), \dots) = \sigma(a) + \sigma(b)$$

### Multiplication:
This holds because evaluating the product of polynomials is the product of their evaluations. ($\odot$ is component-wise multiplication).
$$\sigma(a \cdot b) = ((a \cdot b)(\zeta_0), \dots) = (a(\zeta_0) \cdot b(\zeta_0), \dots) = \sigma(a) \odot \sigma(b)$$
Thus, $\sigma$ is a ring homomorphism.

## Bijectivity (Isomorphism)
To prove it is an isomorphism, we must show it is a bijection (one-to-one and onto). Since both $\mathcal{K}$ and $\mathbb{C}^N$ are vector spaces of dimension $N$ over $\mathbb{Q}$ (embedded in $\mathbb{C}$), it suffices to show the map is linear and invertible.

### Matrix Representation
The map $\sigma$ acts linearly on the coefficients. If $a(X) = \sum_{k=0}^{N-1} a_k X^k$, then:
$$\sigma(a)_j = \sum_{k=0}^{N-1} a_k (\zeta_j)^k$$
This can be written as a matrix-vector multiplication $\vec{v} = V \cdot \vec{a}$, where $V$ is the **Vandermonde matrix**:
$$ V = \begin{pmatrix}
1 & \zeta_0 & \zeta_0^2 & \dots & \zeta_0^{N-1} \\
1 & \zeta_1 & \zeta_1^2 & \dots & \zeta_1^{N-1} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
1 & \zeta_{N-1} & \zeta_{N-1}^2 & \dots & \zeta_{N-1}^{N-1}
\end{pmatrix} $$

### Non-Singularity
The determinant of a Vandermonde matrix is given by:
$$\det(V) = \prod_{0 \le j < k \le N-1} (\zeta_k - \zeta_j)$$
Since $\Phi_M(X)$ is separable (all roots of unity are distinct), $\zeta_k \neq \zeta_j$ for $j \neq k$.
Therefore, $\det(V) \neq 0$. The matrix $V$ is invertible. This implies the map $\sigma$ is a bijection.

## Isometry (Preserves Norms)
The **Isometric** property refers to the relationship between the norms in the two spaces. The CKKS paper establishes the canonical embedding norm $$||a||_\infty^{can} = ||\sigma(a)||_\infty$$
This is a definition rather than a derived property, but it ensures that "small" polynomials map to "small" vectors, which is crucial for error management in encryption.

## Restriction to Real Space $\mathbb{H}$
The proof above covers complex polynomials. For CKKS, we restrict the domain to $\mathbb{R}[X]$ (real coefficients).
* If coefficients $a_k$ are real, then $a(\bar{\zeta}) = \overline{a(\zeta)}$.
* The codomain restricts to vectors $\vec{z}$ where $z_j$ corresponding to $\zeta$ and $z_k$ corresponding to $\bar{\zeta}$ are conjugates.
* This subspace is exactly $\mathbb{H} = \{ \vec{z} \in \mathbb{C}^N : z_j = \overline{z_{-j}} \}$.
* The bijectivity holds for the restricted map $\sigma: \mathbb{R}[X]/(\Phi_M(X)) \rightarrow \mathbb{H}$ because the constraints match the dimensions (both have real dimension $N$).