prodigy.distribution.multisection¶
Multisection of univariate rational functions without roots of unity.
For f in x and a modulus q, the r-th section f_r keeps the terms x^k of the power series of f with k = r (mod q); with a primitive q-th root of unity w it is (1/q) * sum_m w^(-m r) f(w^m x). For a rational function f = P/Q this sum can be computed exactly over the coefficient field of f:
N(x) := prod_m Q(w^m x) = (-1)^(q deg Q) * Res_y(Q(y), y^q - x^q)
is a polynomial in x^q (so N(w x) = N(x)), and Q divides it. Writing f = P (N / Q) / N, the substitution x -> w^m x only changes the numerator M = P N / Q, so f_r is the r-th section of the polynomial M divided by N.