# Source code for sympy.polys.dispersion

from __future__ import print_function, division

from sympy.core import S
from sympy.polys import Poly

[docs]def dispersionset(p, q=None, *gens, **args): r"""Compute the *dispersion set* of two polynomials. For two polynomials f(x) and g(x) with \deg f > 0 and \deg g > 0 the dispersion set \operatorname{J}(f, g) is defined as: .. math:: \operatorname{J}(f, g) & := \{a \in \mathbb{N}_0 | \gcd(f(x), g(x+a)) \neq 1\} \\ & = \{a \in \mathbb{N}_0 | \deg \gcd(f(x), g(x+a)) \geq 1\} For a single polynomial one defines \operatorname{J}(f) := \operatorname{J}(f, f). Examples ======== >>> from sympy import poly >>> from sympy.polys.dispersion import dispersion, dispersionset >>> from sympy.abc import x Dispersion set and dispersion of a simple polynomial: >>> fp = poly((x - 3)*(x + 3), x) >>> sorted(dispersionset(fp)) [0, 6] >>> dispersion(fp) 6 Note that the definition of the dispersion is not symmetric: >>> fp = poly(x**4 - 3*x**2 + 1, x) >>> gp = fp.shift(-3) >>> sorted(dispersionset(fp, gp)) [2, 3, 4] >>> dispersion(fp, gp) 4 >>> sorted(dispersionset(gp, fp)) [] >>> dispersion(gp, fp) -oo Computing the dispersion also works over field extensions: >>> from sympy import sqrt >>> fp = poly(x**2 + sqrt(5)*x - 1, x, domain='QQ<sqrt(5)>') >>> gp = poly(x**2 + (2 + sqrt(5))*x + sqrt(5), x, domain='QQ<sqrt(5)>') >>> sorted(dispersionset(fp, gp)) [2] >>> sorted(dispersionset(gp, fp)) [1, 4] We can even perform the computations for polynomials having symbolic coefficients: >>> from sympy.abc import a >>> fp = poly(4*x**4 + (4*a + 8)*x**3 + (a**2 + 6*a + 4)*x**2 + (a**2 + 2*a)*x, x) >>> sorted(dispersionset(fp)) [0, 1] See Also ======== dispersion References ========== 1. [ManWright94]_ 2. [Koepf98]_ 3. [Abramov71]_ 4. [Man93]_ """ # Check for valid input same = False if q is not None else True if same: q = p p = Poly(p, *gens, **args) q = Poly(q, *gens, **args) if not p.is_univariate or not q.is_univariate: raise ValueError("Polynomials need to be univariate") # The generator if not p.gen == q.gen: raise ValueError("Polynomials must have the same generator") gen = p.gen # We define the dispersion of constant polynomials to be zero if p.degree() < 1 or q.degree() < 1: return set([0]) # Factor p and q over the rationals fp = p.factor_list() fq = q.factor_list() if not same else fp # Iterate over all pairs of factors J = set([]) for s, unused in fp[1]: for t, unused in fq[1]: m = s.degree() n = t.degree() if n != m: continue an = s.LC() bn = t.LC() if not (an - bn).is_zero: continue # Note that the roles of s and t below are switched # w.r.t. the original paper. This is for consistency # with the description in the book of W. Koepf. anm1 = s.coeff_monomial(gen**(m-1)) bnm1 = t.coeff_monomial(gen**(n-1)) alpha = (anm1 - bnm1) / S(n*bn) if not alpha.is_integer: continue if alpha < 0 or alpha in J: continue if n > 1 and not (s - t.shift(alpha)).is_zero: continue J.add(alpha) return J
[docs]def dispersion(p, q=None, *gens, **args): r"""Compute the *dispersion* of polynomials. For two polynomials f(x) and g(x) with \deg f > 0 and \deg g > 0 the dispersion \operatorname{dis}(f, g) is defined as: .. math:: \operatorname{dis}(f, g) & := \max\{ J(f,g) \cup \{0\} \} \\ & = \max\{ \{a \in \mathbb{N} | \gcd(f(x), g(x+a)) \neq 1\} \cup \{0\} \} and for a single polynomial \operatorname{dis}(f) := \operatorname{dis}(f, f). Note that we make the definition \max\{\} := -\infty. Examples ======== >>> from sympy import poly >>> from sympy.polys.dispersion import dispersion, dispersionset >>> from sympy.abc import x Dispersion set and dispersion of a simple polynomial: >>> fp = poly((x - 3)*(x + 3), x) >>> sorted(dispersionset(fp)) [0, 6] >>> dispersion(fp) 6 Note that the definition of the dispersion is not symmetric: >>> fp = poly(x**4 - 3*x**2 + 1, x) >>> gp = fp.shift(-3) >>> sorted(dispersionset(fp, gp)) [2, 3, 4] >>> dispersion(fp, gp) 4 >>> sorted(dispersionset(gp, fp)) [] >>> dispersion(gp, fp) -oo The maximum of an empty set is defined to be -\infty as seen in this example. Computing the dispersion also works over field extensions: >>> from sympy import sqrt >>> fp = poly(x**2 + sqrt(5)*x - 1, x, domain='QQ<sqrt(5)>') >>> gp = poly(x**2 + (2 + sqrt(5))*x + sqrt(5), x, domain='QQ<sqrt(5)>') >>> sorted(dispersionset(fp, gp)) [2] >>> sorted(dispersionset(gp, fp)) [1, 4] We can even perform the computations for polynomials having symbolic coefficients: >>> from sympy.abc import a >>> fp = poly(4*x**4 + (4*a + 8)*x**3 + (a**2 + 6*a + 4)*x**2 + (a**2 + 2*a)*x, x) >>> sorted(dispersionset(fp)) [0, 1] See Also ======== dispersionset References ========== 1. [ManWright94]_ 2. [Koepf98]_ 3. [Abramov71]_ 4. [Man93]_ """ J = dispersionset(p, q, *gens, **args) if not J: # Definition for maximum of empty set j = S.NegativeInfinity else: j = max(J) return j