关于使用FFT计算卷积时单位根冗余特性的疑问
嘿，我来帮你理清这个困惑——你已经抓住了多项式乘法和卷积的核心联系，也知道FFT用单位根来加速，但对“冗余”的点有点卡壳，这很正常，因为这里的“冗余”不是你一开始想的多项式幂次重置，而是单位根的周期性和对称性带来的可复用计算，我慢慢给你拆解：
首先先回顾下基础：假设我们有两个长度为n的序列，对应多项式A(x)和B(x)，它们的卷积结果就是多项式乘积C(x)=A(x)*B(x)，C的次数是2n-2，所以需要至少2n-1个点才能唯一确定C(x)。如果用普通的点值乘法，每个点计算A(x_i)*B(x_i)要遍历n个系数，n个点下来就是O(n²)，和直接做卷积复杂度一样，没什么优势。
那单位根到底带来了什么不一样的东西？
我们选的是N次单位根（通常N取大于等于2n-1的2的幂，方便FFT分治），也就是ω_Nk，其中ω_N是满足ω_NN=1的本原单位根，它有两个关键性质：
- 周期性：ω_N^(k + N) = ω_Nk，更直接的是ω_N(m) = ω_N^(m mod N)
- 对称性：ω_N^(k + N/2) = -ω_Nk，ω_N(2k) = ω_{N/2}^k
正是这两个性质创造了“冗余”——让我们在计算所有单位根处的点值时，能共享大量中间计算结果，不用每个点都从头算。
举个简单的小例子，比如N=4，ω_4=i（虚数单位），假设A(x)=a0+a1x+a2x²+a3x³：
- 计算A(i) = a0 + a1i + a2i² + a3i³ = (a0 - a2) + i(a1 - a3)
- 计算A(-i) = a0 + a1*(-i) + a2*(-i)² + a3*(-i)³ = (a0 - a2) - i*(a1 - a3)
你看，计算A(i)和A(-i)时，(a0 - a2)和(a1 - a3)这两个中间结果是完全一样的，只需要算一次就能复用两次，这就是最直观的“冗余”——重复的计算步骤被合并了，不用做两遍。
再往FFT的分治逻辑上延伸：FFT会把多项式拆成偶数项和奇数项，比如A(x) = A_even(x²) + x*A_odd(x²)，然后代入单位根ω_Nk和ω_N(k+N/2)，你会发现A(ω_N^(k+N/2)) = A_even(ω_N^(2(k+N/2))) + ω_N(k+N/2)*A_odd(ω_N(2(k+N/2))) = A_even(ω_N^(2k + N)) + (-ω_Nk)*A_odd(ω_N(2k + N))。而因为ω_NN=1，ω_N(2k+N)=ω_N(2k)=ω_{N/2}k，所以A(ω_N^(k+N/2)) = A_even(ω_{N/2}^k) - ω_Nk*A_odd(ω_{N/2}k)。
这时候你会发现，计算A在ω_Nk和ω_N(k+N/2)处的值，只需要先算出A_even和A_odd在ω_{N/2}^k处的值，就能同时得到两个结果——这就是分治的核心，把一个大小为N的问题拆成两个大小为N/2的子问题，而且子问题的结果能同时服务于原问题的两个点值计算，完全避免了重复劳动。
回到你的疑惑：“powers of x in the polynomials would be at most N, so it wouldn't reset there”——其实单位根的周期性不是让多项式的幂次“重置”，而是让多项式在单位根处的求值可以利用周期性简化计算。比如当我们把原序列补零到长度N后，多项式次数变成N-1，这时候计算a_m * ω_N(k*m)，当m=N/2时，ω_N(k*(N/2))=(ω_NN)(k/2)=1^(k/2)，k为偶数时是1，奇数时是-1，这样就能和其他项合并计算，进一步复用结果。
本质上，这里的“冗余”指的是不同单位根处的点值计算共享大量中间步骤，FFT就是利用这种冗余，把原本O(N²)的点值计算复杂度降到了O(N log N)，再通过逆FFT把点值转换回系数，就得到了卷积结果。
备注：内容来源于stack exchange，提问作者MeltedStatementRecognizing
