单位根

定义 $\mathbb{C}$ 上 $x^n=1$ 的 $n$ 个解为 $\omega _ {n}^{0} \sim \omega _ {n}^{n-1}$,其中 $\omega _ {n}^{1}=e^{\frac{2 \pi i}{n}}$

在模 $P$ 意义下,设 $g$ 为 $P$ 的原根,则 $\omega _ {n}^{1}=g^{\frac{P-1}{n}}$

单位根反演

对于 $[n | k]$,有:

$$
[n|k]=\frac{1}{n}\sum _ {p=0}^{n-1}\omega _ {n}^{pk}
$$

证明

若 $k=nt$,则:

$$
\frac{1}{n}\sum _ {p=0}^{n-1}\omega _ {n}^{pk}=\frac{1}{n}\sum _ {p=0}^{n-1}\omega _ {n}^{(pnt) \bmod n}=\frac{1}{n}\sum _ {p=0}^{n-1}\omega _ {n}^{0}=1
$$

若 $n \not| k$,则:

$$
\frac{1}{n}\sum _ {p=0}^{n-1}\omega _ {n}^{pk}=\omega _ {n}^{0}\frac{1-\omega _ {n}^{kn}}{n(1-\omega _ {n}^{k})}=\omega _ {n}^{0}\frac{1-\omega _ {n}^{0}}{n(1-\omega _ {n}^{k})}=0
$$

应用

对于多项式 $f(x)=\sum _ {p=0}^{N-1}a _ px^p$,若要求 $g(n)=\sum _ {p=0}^{N-1}a _ p[n|p]$,则有:

$$
\begin{aligned}
\frac{\sum _ {p=0}^{n-1}f(\omega _ {n}^{p})}{n}
=& \frac{\sum _ {p=0}^{n-1}\sum _ {q=0}^{N-1}a _ q\omega _ {n}^{pq}}{n} \\
=& \sum _ {q=0}^{N-1}a _ q\frac{\left(\sum _ {p=0}^{n-1}\omega _ {n}^{pq}\right)}{n} \\
=& \sum _ {q=0}^{N-1}a _ q [n|q] \\
\end{aligned}
$$

数列合并

例 1

若有序列 ${a _ n},{b _ n}$,构造序列 ${p _ n}$ 满足:

$$
p _ {n}=\begin{cases}{a _ {n}} & {\mathrm{n \equiv 1 \pmod {2}}} \\ {b _ {n}} & {\mathrm{n \equiv 0 \pmod{2}}}\end{cases}
$$

通过单位根的性质,也可以写作:

$$
p _ {n}=\frac{1}{2}\left(\cos(\pi n)\left(b _ {n}-a _ {n}\right)+a _ {n}+b _ {n}\right)
$$

例 2

若有函数 $f(n)$ 满足:

$$
f(n)=\begin{cases}{\frac{n}{2}} & {n \equiv 0 \pmod{2}} \\ {3 n+1} & {n \equiv 1 \pmod{2}}\end{cases}
$$

则也可以写为:

$$
f(n)=\frac{1}{4}(2+7 n-\cos (\pi n)(2+5 n))
$$

例 3

若有序列 ${p _ n}$ 满足:

$$
p _ {n}=\begin{cases}{a _ {n}} & {\mathrm{n \equiv 0 \pmod{3}}} \\ {b _ {n}} & {\mathrm{n \equiv 1 \pmod{3}}} \\ {c _ {n}} & {\mathrm{n \equiv 2 \pmod{3}}}\end{cases}
$$

则也可以写为:
$$
p _ {n}=\frac{1}{3}\left(\cos \left(\frac{2 \pi n}{3}\right)\left(2 a _ {n}-b _ {n}-c _ {n}\right)+a _ {n}+\sqrt{3} \sin \left(\frac{2 \pi n}{3}\right)\left(b _ {n}-c _ {n}\right)+b _ {n}+c _ {n}\right)
$$

参考资料