prodigy.distribution.roots_of_unity¶
Soundness check for substitutions with roots of unity.
The residue classes of a variable x modulo q are extracted by evaluating the generating function f at w x for the q-th roots of unity w (modulo guards x % q = r, Distribution._arithmetic_progression and x % q in an assignment with an infinite marginal of x). The engines evaluate f(w x) with the principal branches of roots and logarithms, which need not agree with the power series of f: for example, sqrt(x^2*y^2) denotes the series x*y, but at -x it evaluates to sqrt(x^2*y^2) again instead of -x*y.
The substitution is exact if the closed form of f is single-valued in x, i.e. built from x and
subexpressions without x by +, *, integer powers and entire functions (exp, sin, cos,
sinh, cosh); this covers all rational generating functions. Such an f is holomorphic in x on a
punctured disk around 0 except for isolated singularities. It agrees with its power series on a
positive interval, hence by the identity theorem on that whole domain, so f(w x) and the series at
w x agree there as well and have the same power series. All other generating functions (roots,
logarithms, absolute values, or anything else) are rejected with a NotSingleValuedError.
The check is engine independent and works on SymPy expressions.
- exception NotSingleValuedError[source]¶
Bases:
ValueErrorA substitution with roots of unity was requested on a generating function that is not provably single-valued in the substituted variable.