1
from __future__ import print_function, division
3
from sympy.core import S
4
from sympy.polys import Poly
5
from sympy.polys.polytools import factor_list
8
def dispersionset(p, q=None, *gens, **args):
9
r"""Compute the *dispersion set* of two polynomials.
11
For two polynomials `f(x)` and `g(x)` with `\deg f > 0`
12
and `\deg g > 0` the dispersion set `\operatorname{J}(f, g)` is defined as:
15
\operatorname{J}(f, g)
16
& := \{a \in \mathbb{N}_0 | \gcd(f(x), g(x+a)) \neq 1\} \\
17
& = \{a \in \mathbb{N}_0 | \deg \gcd(f(x), g(x+a)) \geq 1\}
19
For a single polynomial one defines `\operatorname{J}(f) := \operatorname{J}(f, f)`.
24
>>> from sympy import poly
25
>>> from sympy.polys.dispersion import dispersion, dispersionset
26
>>> from sympy.abc import x
28
Dispersion set and dispersion of a simple polynomial:
30
>>> fp = poly((x - 3)*(x + 3), x)
31
>>> sorted(dispersionset(fp))
36
Note that the definition of the dispersion is not symmetric:
38
>>> fp = poly(x**4 - 3*x**2 + 1, x)
40
>>> sorted(dispersionset(fp, gp))
42
>>> dispersion(fp, gp)
44
>>> sorted(dispersionset(gp, fp))
46
>>> dispersion(gp, fp)
49
Computing the dispersion also works over field extensions:
51
>>> from sympy import sqrt
52
>>> fp = poly(x**2 + sqrt(5)*x - 1, x, domain='QQ<sqrt(5)>')
53
>>> gp = poly(x**2 + (2 + sqrt(5))*x + sqrt(5), x, domain='QQ<sqrt(5)>')
54
>>> sorted(dispersionset(fp, gp))
56
>>> sorted(dispersionset(gp, fp))
59
We can even perform the computations for polynomials
60
having symbolic coefficients:
62
>>> from sympy.abc import a
63
>>> fp = poly(4*x**4 + (4*a + 8)*x**3 + (a**2 + 6*a + 4)*x**2 + (a**2 + 2*a)*x, x)
64
>>> sorted(dispersionset(fp))
80
# Check for valid input
81
same = False if q is not None else True
85
p = Poly(p, *gens, **args)
86
q = Poly(q, *gens, **args)
88
if not p.is_univariate or not q.is_univariate:
89
raise ValueError("Polynomials need to be univariate")
92
if not p.gen == q.gen:
93
raise ValueError("Polynomials must have the same generator")
96
# We define the dispersion of constant polynomials to be zero
97
if p.degree() < 1 or q.degree() < 1:
100
# Factor p and q over the rationals
102
fq = q.factor_list() if not same else fp
104
# Iterate over all pairs of factors
106
for s, unused in fp[1]:
107
for t, unused in fq[1]:
114
if not (an - bn).is_zero:
116
# Note that the roles of `s` and `t` below are switched
117
# w.r.t. the original paper. This is for consistency
118
# with the description in the book of W. Koepf.
119
anm1 = s.coeff_monomial(gen**(m-1))
120
bnm1 = t.coeff_monomial(gen**(n-1))
121
alpha = (anm1 - bnm1) / S(n*bn)
122
if not alpha.is_integer:
124
if alpha < 0 or alpha in J:
126
if n > 1 and not (s - t.shift(alpha)).is_zero:
133
def dispersion(p, q=None, *gens, **args):
134
r"""Compute the *dispersion* of polynomials.
136
For two polynomials `f(x)` and `g(x)` with `\deg f > 0`
137
and `\deg g > 0` the dispersion `\operatorname{dis}(f, g)` is defined as:
140
\operatorname{dis}(f, g)
141
& := \max\{ J(f,g) \cup \{0\} \} \\
142
& = \max\{ \{a \in \mathbb{N} | \gcd(f(x), g(x+a)) \neq 1\} \cup \{0\} \}
144
and for a single polynomial `\operatorname{dis}(f) := \operatorname{dis}(f, f)`.
145
Note that we make the definition `\max\{\} := -\infty`.
150
>>> from sympy import poly
151
>>> from sympy.polys.dispersion import dispersion, dispersionset
152
>>> from sympy.abc import x
154
Dispersion set and dispersion of a simple polynomial:
156
>>> fp = poly((x - 3)*(x + 3), x)
157
>>> sorted(dispersionset(fp))
162
Note that the definition of the dispersion is not symmetric:
164
>>> fp = poly(x**4 - 3*x**2 + 1, x)
165
>>> gp = fp.shift(-3)
166
>>> sorted(dispersionset(fp, gp))
168
>>> dispersion(fp, gp)
170
>>> sorted(dispersionset(gp, fp))
172
>>> dispersion(gp, fp)
175
The maximum of an empty set is defined to be `-\infty`
176
as seen in this example.
178
Computing the dispersion also works over field extensions:
180
>>> from sympy import sqrt
181
>>> fp = poly(x**2 + sqrt(5)*x - 1, x, domain='QQ<sqrt(5)>')
182
>>> gp = poly(x**2 + (2 + sqrt(5))*x + sqrt(5), x, domain='QQ<sqrt(5)>')
183
>>> sorted(dispersionset(fp, gp))
185
>>> sorted(dispersionset(gp, fp))
188
We can even perform the computations for polynomials
189
having symbolic coefficients:
191
>>> from sympy.abc import a
192
>>> fp = poly(4*x**4 + (4*a + 8)*x**3 + (a**2 + 6*a + 4)*x**2 + (a**2 + 2*a)*x, x)
193
>>> sorted(dispersionset(fp))
209
J = dispersionset(p, q, *gens, **args)
211
# Definition for maximum of empty set
212
j = S.NegativeInfinity
added
removed
lib/py/sympy/polys/dispersion.py
