如何加速SymPy对Cori定理相关乘积展开的无限制运算？

我提出了Cori定理：基于整数n确定单位根z和对应指数k，所有线性项$(a + b \cdot z^{k)$的乘积等于$a}n + b^n$。

在使用SymPy验证该定理时，发现当$n \geq 7$时，符号展开运算会陷入长时间卡顿，甚至无法返回结果。后续通过将单位根纳入代数域优化代码，成功解决了运算效率问题，验证了定理的正确性。

定理规则 #

• a、b为SymPy变量，可替换为其他变量；
• $\zeta(n)$为n次单位根，取非平凡解$e^{(2i\pi)/n}$；
• 当n为偶数时，k取1到2n-1间的奇数，z为$\zeta(2n)$；当n为奇数时，k取0到n-1，z为$\zeta(n)$。

初始卡顿代码 #

import sympy as sp
from sympy.solvers import solve

def cycles(n):
    # a and b will be used for product
    # x will be used for unit calculation
    a, b, x = sp.symbols('a b x')
    if n % 2 == 0:
        exponents = [2*k+1 for k in range(0, n)]
        units = solve(x**n + 1, x)
    else:
        exponents = list(range(0, n))
        units = solve(x**n - 1, x)
    #z = sp.exp(sp.I * sp.pi * (1 if n % 2 == 0 else 2) / N)
    z = units[n-2]

    factors = [a + b*z**k for k in exponents]
    product = sp.expand(sp.Mul(* factors))
    return product

if __name__ == "__main__":
    for i in range(2, 10):
        c = cycles(i)
        print(c)
        """
        TODO: replace sp.simplify for something that works for big n
        """
        print(sp.simplify(c))

优化后代码 #

import sympy as sp

def cycles(n):
    
    # Use 't' as a variable
    t = sp.symbols('t', real=True)
    exponents = list(range(0, n))
    
    # Get the roots of unity
    z =  sp.exp(2 * sp.I * sp.pi / n)
    z2 = sp.exp(    sp.I * sp.pi / n)

    # Get their algebraic field
    z =  sp.Poly(z , t, domain=sp.QQ.algebraic_field(z ))
    z2 = sp.Poly(z2, t, domain=sp.QQ.algebraic_field(z2))
    
    # Multiply them
    factors = [t + z2*z**k for k in exponents]
    return sp.prod(factors).as_expr()

if __name__ == "__main__":
    for i in range(2, 10):
        print('===', i, '===')
        print(cycles(i), '\n')

内容的提问来源于stack exchange，提问作者Coda5 55