Skip to content

Latest commit

 

History

History
 
 

RootsOfUnity

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
RootsOfUnity.ipynb
RootsOfUnity.ipynb
 
 
readme.md
readme.md
 
 

readme.md

title tags
Draft. 单位根
zk
abstract algebra
group theory
number theory
root of unity

WTF zk 教程第 Draft 讲：单位根

单位根是一个复数，当它构成有正整数次幂时，结果是 $1$ 。单位根与数学的许多领域有联系，包括数论、群论和多项式理论。在 zk 领域中，我们重点讨论单位根在群论和多项式理论中的应用。

1. 单位根的定义

对于任何正整数 $n$ ， $n$ 次单位根（n-th root of unity）是方程 $x^n = 1$ 的复数根。而根据代数基本定理，该方程有 $n$ 个解，因此我们这些解（ $n$ 次单位根）可以计作一个集合 $U_n$ 。

定理 1 ： 如果 $n$ 是偶数，方程 $x^n - 1 = 0$ 有 $2$ 个实解，是 $1$ 和 $-1$ ；如果 $n$ 是奇数，会有 $1$ 个实解，即 $1$。

那么除了实数解，如何求方程的所有复数解呢？

答案是：利用欧拉公式可以求解。首先回顾欧拉公式的定义： $e^{ix}=\cos(x) + i\sin(x)$ 。

定理 2 ： $n$ 阶单位根的集合为 $U_n ={e^{\frac{2k\pi i}{n}}}$ ，其中 $k \in (0, 1, \dots, n-1)$

点我展开证明 👀

根据欧拉公式，有 $e^{2\pi i} = cos(2\pi) + i\sin(2\pi) = 1$ 。令 $k$ 是任意正整数，则 $(e^{2\pi i})^{k} = 1^{k} = 1$ 。

而要求 $x^{n} = 1$ ，则有 $x^{n} = e^{2k\pi i}$ ，对等式两边同时取 $\frac{1}{n}$ 次幂，有 $x = e^{\frac{2k\pi i}{n}}$ 。

需要注意，当 $k > n$ 时，那么角度 $\frac{2k\pi}{n} = \frac{2(k-n)\pi}{n}$ 。

因此， $x^n = 1$ 有 $n$ 个不同的解，即 ${e^{\frac{2k\pi i}{n}}}$ ，其中 $k \in (0, 1, \dots, n-1)$ 。

注意与原根（primitive root）区分开来，本原根通常在模 $n$ 乘法循环群中出现，而单位根的定义不涉及模运算。回顾本原根的定义：给定正整数 $n$ ，如果对任意的与 $n$ 互素的整数 $a$ ，存在最小正整数 $k$ 满足 $g^{k}\equiv 1\pmod{n}$ ，则称 $g$ 为一个模 $n$ 本原根（primitive root modulo $n$ ）。本原根是模 $n$ 乘法群的生成元，意味着通过原根的幂可以生成模 $n$ 下所有的可逆元素。 $k$ 被称为 index 或者离散对数。当 $a=1$ 时，费马小定理告诉我们可以用欧拉公式求 $k$ 。

类似地，我们可以定义原始单位根（primitive root of unity）：原始单位根是一种特殊的单位根。如果某个单位根是阶为 $n$ 的原始单位根，那么它是满足 $x^n = 1$ 的最小正整数 $n$ 的根，并且没有任何小于 $n$ 的正整数 $m$ 使得该根的 $m$ 次幂等于 $1$。换句话说，一个阶为 $n$ 的原始单位根可以生成所有的 $n$ 次单位根，但它自身不能表示为更小次数的单位根的幂。求原始单位根的数量可以使用欧拉函数 $\varphi(n)$ 。

2. 单位根的基本性质

单位根有很多良好的性质，可以帮助我们构建更加高效的算法。比如：

  • 如果 $x$ 是一个 $n$ 阶单位根，那么 $x^k$ 也是，当 $k$ 是任何整数时。
  • 如果 $x$ 是一个 $n$ 阶单位根，那么 $x^n = 1$ 。
  • 所有的 $n$ 阶单位根之和始终为 0 。
  • 所有的 $n$ 阶单位根之积始终为 $(-1)^{n+1}$ 。
  • $1$ 和 $-1$ 是唯一的实单位根。
  • 如果一个数是单位根，那么它的共轭复数也是。
  • 所有的 n 阶单位根的绝对值之和为 n。

3. 单位根&群

$n$ 次单位根组成的群

对于任意正整数 $n$ ，任意两个 $n$ 次单位根的乘积和乘法逆元仍然是 $n$ 次单位根，并且满足乘法结合律和交换律。因此所有的 $n$ 次单位根组成的群是一个乘法运算下的 Abel 群。

并且，给定一个 $n$ 次单位根 $\omega$ ，其他的单位根都可以根据 $\omega$ 的幂计算得到。这意味着， $n$ 次单位根组成的乘法群还是一个循环群。

所有的单位根组成的群

任意两个单位根，它们的乘积和乘法逆元仍然是单位根。比如，给定 $n$ 次单位根 $x$ （满足 $x^n = 1$ ）和 $m$ 次单位根 $y$ （满足 $y^m = 1$ ），则 $(x^{-1})^{m}$ ， $(xy)^k=1$ ，其中 $k$ 是 $m$ 和 $n$ 的最小公倍数。

4. 单位根&多项式

回顾单位根的定义：对于任何正整数 $n$ ， $n$ 次单位根（n-th root of unity）是方程 $x^n = 1$ 的复数根。

那么把上述方程表示为多项式形式，即 $p(x)=x^n-1$ ，那么所有的 $n$ 次单位根都是零多项式 $p(x)=0$ 的解。

分圆多项式

在数学上， $n$ 次分圆多项式（n-th cyclotomic polynomial）被定义为：对于任意的正整数 $n$ ，分圆多项式 $f(x)$ 是 $x^n - 1$ 因式分解结果中的整系数的特定不可约多项式，满足 $f(x)|(x^n-1)$ ，但不满足 $f(x)|(x^k-1)$ ，其中 $k\lt n$ 。

简单而言，对于多项式 $x^n - 1$，它的分圆多项式就是满足所有的 $n$ 次原始单位根 $U_n ={e^{\frac{2k\pi i}{n}}}$ 也是它的零点的极小多项式，其中 $gcd(k, n)=1$ 且 $k\le n$ 。注意：k和n互素，所以不是所有的 n 次单位根都是分圆多项式的零点。数学表达式为:

$$ \Phi_{n}(x) = \prod_{1\le k \le n, gcd(k, n)=1}(x-e^{\frac{2k\pi i}{n}}) $$

分圆多项式也可以定义为整系数的一元多项式，是任何本原 $n$ 次单位根在有理数域上的最小多项式。

性质

  1. 当 $n$ 为素数时， $\Phi_{n}(x) = 1 + x + x^2 + \dots + x^{n-1} = \sum_{k=0}^{n-1} x^k$。

  2. 当 $n=2p$ 且 $p$ 为奇素数时， $\Phi_{n}=1 - x + x^2 - \dots + x^{p-1} = \sum_{k=0}^{p-1} (-x)^k = \Phi_p(-x)$ 。

  3. $x^n - 1 = \prod_{d|n} \Phi_d(x)$

更一般的性质可以参考Wikipedia

示例

下面是一个使用 Python 计算第八分圆多项式（8th cyclotomic polynomial）的例子:

    from sympy import symbols, cyclotomic_poly

    x = symbols('x')
    # Calculate the 8th cyclotomic polynomial
    cyclotomic_poly_8 = cyclotomic_poly(8, x)
    cyclotomic_poly_8

5. 单位根&有限域

有限域中的任意非零元素都是一个单位根。

证明很简单：对于每个有限域 $GF(q)$ 的非零元素 $x$ ，都有 $x^{q-1} = 1$ 。

如果域中存在 $n$ 次原始单位根，那么这个域会包含所有的 $n$ 次单位根。

一个有限域 $GF(q)$ 中如果存在 $n$ 次原始单位根，当且仅当 $n|(q-1)$ 。同样的，有限域 $GF(q)$ 中 $n$ 次原始单位根的数目需要使用欧拉函数计算 $\varphi(n)$ 。

有限域 $GF(q)$ 的 $n$ 次单位根的数目为 $gcd(n, q-1)$ 。

给定一个特征为 $p$ 的域，任意 $np$ 次单位根同时也是 $n$ 次单位根。

6. 总结

这一节主要介绍了单位根的内容，包括它的定义、与原根的区别、在数论、群论和多项式理论中的应用。这一概念将在ZK领域很多协议中发挥重要作用，因为在有限域中找到原始单位根组成的乘法子群可以帮助进行快速傅立叶变换（FFT）。