Let a(x) be a polynomial and \omega_n be a
principal n-th root of unity. We define the DFT of a(x) as the n-tuple (\hat{a}_j) = (a(\omega_n^j)) . In other words, \hat{a}_j = \sum_{i=0}^{n-1} a_i \omega_n^{ij} \quad \text{ for all } j = 0, 1, \dots, n - 1. For simplicity, we denote the transformation as \text{DFT}_{\omega_n}. The PFA relies on a coprime factorization of n = \prod_{d = 0}^{D - 1} n_d and turns \text{DFT}_{\omega_n} into \bigotimes_d \text{DFT}_{\omega_{n_d}} for some choices of \omega_{n_d}'s where \bigotimes is the
tensor product.
Mapping based on CRT For a coprime factorization {{tmath|1= \textstyle n = \prod_{d = 0}^{D - 1} n_d }}, we have the
Chinese remainder map m \mapsto (m \bmod n_d) from \mathbb{Z}_{n} to \prod_{d = 0}^{D - 1} \mathbb{Z}_{n_d} with (m_d) \mapsto \sum_{d = 0}^{D - 1} e_d m_d as its inverse where 's are the
central orthogonal idempotent elements with \sum_{d = 0}^{D - 1} e_d = 1 \pmod{n}. Choosing \omega_{n_d} = \omega_n^{e_d} (therefore, {{tmath|1= \prod_{d = 0}^{D - 1} \omega_{n_d} = \omega_n^{\sum_{d = 0}^{D - 1} e_d} = \omega_n }}), we rewrite \text{DFT}_{\omega_n} as follows: \hat{a}_j = \sum_{i = 0}^{n - 1} a_i \omega_n^{ij} = \sum_{i = 0}^{n - 1} a_i \left( \prod_{d = 0}^{D - 1} \omega_{n_d} \right)^{ij} = \sum_{i = 0}^{n - 1} a_i \prod_{d = 0}^{D - 1} \omega_{n_d}^{ (i \bmod n_d) (j \bmod n_d)} = \sum_{i_0 = 0}^{n_0 - 1} \cdots \sum_{i_{D - 1} = 0}^{n_{D - 1} - 1} a_{\sum_{d = 0}^{D - 1} e_d i_d} \prod_{d = 0}^{D - 1} \omega_{n_d}^{i_d (j \bmod n_d)} . Finally, define a_{i_0, \dots, i_{D - 1}} = a_{\sum_{d = 0}^{D - 1} i_d e_d} and {{tmath|1= \hat{a}_{j_0, \dots, j_{D - 1} } = \hat{a}_{\sum_{d = 0}^{D - 1} j_d e_d} }}, we have \hat{a}_{j_0, \dots, j_{D - 1}} = \sum_{i_0 = 0}^{n_0 - 1} \cdots \sum_{i_{D - 1}=0}^{n_{D - 1} - 1} a_{i_0, \dots, i_{D - 1}} \prod_{d = 0}^{D - 1} \omega_{n_d}^{i_d j_d} . Therefore, we have the multi-dimensional DFT, {{tmath|1= \textstyle \otimes_{d = 0}^{D - 1} \text{DFT}_{\omega_{n_d} } }}.
As algebra isomorphisms PFA can be stated in a high-level way in terms of
algebra isomorphisms. We first recall that for a commutative ring R and a
group isomorphism from G to , we have the following algebra isomorphism R[G] \cong \bigotimes_d R[G_d] , where \bigotimes refers to the
tensor product of algebras. To see how PFA works, we choose G = (\Z_n, +, 0) and G_d = (\Z_{n_d}, +, 0) be
additive groups. We also identify R[G] as \frac{R[x]}{\langle x^n - 1 \rangle} and R[G_d] as {{tmath|1= \textstyle \frac{R[x_d]}{\langle x_d^{n_d} - 1 \rangle} }}. Choosing \eta = a \mapsto (a \bmod n_d) as the group isomorphism , we have the algebra isomorphism \eta^* : R[G] \cong \bigotimes_d R[G_d], or alternatively, \eta^* : \frac{R[x]}{\langle x^n - 1 \rangle} \cong \bigotimes_d \frac{R[x_d]}{\langle x_d^{n_d} - 1 \rangle} . Now observe that \text{DFT}_{\omega_n} is actually an algebra isomorphism from \frac{R[x]}{\langle x^n - 1 \rangle} to \prod_i \frac{R[x]}{\langle x - \omega_n^i \rangle} and each \text{DFT}_{\omega_{n_d}} is an algebra isomorphism from \frac{R[x]}{\langle {x_d}^{n_d} - 1 \rangle} to \prod_{i_d} \frac{R[x_d]}{\langle x_d - \omega_{n_d}^{i_d} \rangle}, we have an algebra isomorphism \eta' from \bigotimes_d \prod_{i_d} \frac{R[x_d]}{\langle x_d - \omega_{n_d}^{i_d} \rangle} to \prod_i \frac{R[x]}{\langle x - \omega_n^i \rangle}. What PFA tells us is that \text{DFT}_{\omega_n} = \eta' \circ \bigotimes_d \text{DFT}_{\omega_{n_d}} \circ \eta^* where \eta^* and \eta' are re-indexing without actual arithmetic in R.
Counting the number of multi-dimensional transformations Notice that the condition for transforming \text{DFT}_{\omega_n} into \eta' \circ \bigotimes_d \text{DFT}_{\omega_{n_d}} \circ \eta^* relies on "an" additive group isomorphism \eta from (\mathbb{Z}_n, +, 0) to {{tmath|1= \textstyle \prod_d (\Z_{n_d}, +, 0) }}. Any additive group isomorphism will work. To count the number of ways transforming \text{DFT}_{\omega_n} into {{tmath|1= \textstyle \eta' \circ \bigotimes_d \text{DFT}_{\omega_{n_d} } \circ \eta^* }}, we only need to count the number of additive group isomorphisms from (\mathbb{Z}_n, +, 0) to \prod_d (\mathbb{Z}_{n_d}, +, 0), or alternative, the number of additive group
automorphisms on . Since (\mathbb{Z}_n, +, 0) is
cyclic, any automorphism can be written as 1 \mapsto g where g is a
generator of (\mathbb{Z}_n, +, 0). By the definition of , g's are exactly those coprime to n. Therefore, there are exactly \varphi(n) many such maps where \varphi is the
Euler's totient function. The smallest example is n = 6 where \varphi(n) = 2, demonstrating the two maps in the literature: the "CRT mapping" and the "Ruritanian mapping". == See also ==