Iterator for Weil polynomials.¶
For \(q\) a prime power, a \(q\)-Weil polynomial is a monic polynomial with integer coefficients whose complex roots all have absolute value \(sqrt(q)\). The class WeilPolynomials provides an iterable over a space of polynomials of this type; it is possible to relax the monic condition by specifying one (or more) leading coefficients. One may also impose certain congruence conditions; this can be used to limit the Newton polygons of the resulting polynomials, or to lift a polynomial specified by a congruence to a Weil polynomial.
For large jobs, one can set parallel=True to use OpenMP (if support was enabled at compile time). Due to increased overhead, this is not recommended for smaller problem sizes. To enable support, ensure that your compiler supports OpenMP and remove the appropriate # characters in the distutils commands below. (You may also need to move those lines to the start of the file.)
AUTHORS:
Kiran S. Kedlaya (2007-05-28): initial version
Kiran S. Kedlaya (2015-08-29): switch from NTL to FLINT
Kiran S. Kedlaya (2017-10-03): consolidate Sage layer into .pyx file; define WeilPolynomials iterator; reverse convention for polynomials; pass multiprecision integers to/from C
Kiran S. Kedlaya (2019-02-02): update for Python3; improve parallel mode
Kiran S. Kedlaya (2019-12-19): final packaging for Sage (with help from David Roe)
A standalone version of this code can be found at https://github.com/kedlaya/root-unitary.
- class sage.rings.polynomial.weil.weil_polynomials.WeilPolynomials(d, q, sign=1, lead=1, node_limit=None, parallel=False, squarefree=False, polring=None)[source]¶
Bases:
objectIterable for Weil polynomials, i.e., integer polynomials with all complex roots having a particular absolute value.
Such polynomials \(f\) satisfy a functional equation
\[T^d f(q/T) = s q^{d/2} f(T)\]where \(d\) is the degree of \(f\), \(s\) is a sign and \(q^{1/2}\) is the absolute value of the roots of \(f\).
If parallel is False, then the order of values is descending lexicographical (i.e., polynomials with the largest coefficients of largest degrees sort first).
If parallel is True, then the order of values is not specified. (Beware that due to increased overhead, parallel execution may not yield a significant speedup for small problem sizes.)
INPUT:
d– integer; the degree of the polynomialsq– integer; the square of the complex absolute value of the rootssign– integer (default: \(1\)); the sign \(s\) of the functional equationlead– integer (default: \(1\)); list of integers or pairs of integersThese are constraints on the leading coefficients of the generated polynomials. If pairs \((a, b)\) of integers are given, they are treated as a constraint of the form \(\equiv a \pmod{b}\); the moduli must be in decreasing order by divisibility, and the modulus of the leading coefficient must be 0.
node_limit– integer (default:None)If set, imposes an upper bound on the number of terminal nodes during the search (will raise a
RuntimeErrorif exceeded).parallel– boolean (default:False); whether to use multiple processesIf set, will raise an error unless this file was compiled with OpenMP support (see instructions at the top of
sage.rings.polynomial.weil.weil_polynomials).squarefree– boolean (default:False)If set, only squarefree polynomials will be returned.
polring– (optional) a polynomial ring in which to construct the results
EXAMPLES:
Some simple cases:
sage: from sage.rings.polynomial.weil.weil_polynomials import WeilPolynomials sage: list(WeilPolynomials(2,2)) [x^2 + 2*x + 2, x^2 + x + 2, x^2 + 2, x^2 - x + 2, x^2 - 2*x + 2] sage: l = list(WeilPolynomials(4,2)) sage: l[0], l[-1] (x^4 + 4*x^3 + 8*x^2 + 8*x + 4, x^4 - 4*x^3 + 8*x^2 - 8*x + 4) sage: l = list(WeilPolynomials(3, 1, sign=-1)) sage: l[0], l[-1] (x^3 + x^2 - x - 1, x^3 - 3*x^2 + 3*x - 1)
>>> from sage.all import * >>> from sage.rings.polynomial.weil.weil_polynomials import WeilPolynomials >>> list(WeilPolynomials(Integer(2),Integer(2))) [x^2 + 2*x + 2, x^2 + x + 2, x^2 + 2, x^2 - x + 2, x^2 - 2*x + 2] >>> l = list(WeilPolynomials(Integer(4),Integer(2))) >>> l[Integer(0)], l[-Integer(1)] (x^4 + 4*x^3 + 8*x^2 + 8*x + 4, x^4 - 4*x^3 + 8*x^2 - 8*x + 4) >>> l = list(WeilPolynomials(Integer(3), Integer(1), sign=-Integer(1))) >>> l[Integer(0)], l[-Integer(1)] (x^3 + x^2 - x - 1, x^3 - 3*x^2 + 3*x - 1)
from sage.rings.polynomial.weil.weil_polynomials import WeilPolynomials list(WeilPolynomials(2,2)) l = list(WeilPolynomials(4,2)) l[0], l[-1] l = list(WeilPolynomials(3, 1, sign=-1)) l[0], l[-1]
By Kronecker’s theorem, a monic integer polynomial has all roots of absolute value 1 if and only if it is a product of cyclotomic polynomials. For such a product to have positive sign of the functional equation, the factors \(x-1\) and \(x+1\) must each occur with even multiplicity. This code confirms Kronecker’s theorem for polynomials of degree 6:
sage: P.<x> = PolynomialRing(ZZ) sage: d = 6 sage: ans1 = list(WeilPolynomials(d, 1, 1)) sage: ans1.sort() sage: l = [(x-1)^2, (x+1)^2] + [cyclotomic_polynomial(n,x) ....: for n in range(3, 2*d*d) if euler_phi(n) <= d] sage: w = WeightedIntegerVectors(d, [i.degree() for i in l]) sage: ans2 = [prod(l[i]^v[i] for i in range(len(l))) for v in w] sage: ans2.sort() sage: print(ans1 == ans2) True
>>> from sage.all import * >>> P = PolynomialRing(ZZ, names=('x',)); (x,) = P._first_ngens(1) >>> d = Integer(6) >>> ans1 = list(WeilPolynomials(d, Integer(1), Integer(1))) >>> ans1.sort() >>> l = [(x-Integer(1))**Integer(2), (x+Integer(1))**Integer(2)] + [cyclotomic_polynomial(n,x) ... for n in range(Integer(3), Integer(2)*d*d) if euler_phi(n) <= d] >>> w = WeightedIntegerVectors(d, [i.degree() for i in l]) >>> ans2 = [prod(l[i]**v[i] for i in range(len(l))) for v in w] >>> ans2.sort() >>> print(ans1 == ans2) True
P.<x> = PolynomialRing(ZZ) d = 6 ans1 = list(WeilPolynomials(d, 1, 1)) ans1.sort() l = [(x-1)^2, (x+1)^2] + [cyclotomic_polynomial(n,x) for n in range(3, 2*d*d) if euler_phi(n) <= d] w = WeightedIntegerVectors(d, [i.degree() for i in l]) ans2 = [prod(l[i]^v[i] for i in range(len(l))) for v in w] ans2.sort() print(ans1 == ans2)Generating Weil polynomials with prescribed initial coefficients:
sage: w = WeilPolynomials(10,1,sign=1,lead=[3,1,1]) sage: it = iter(w) sage: next(it) 3*x^10 + x^9 + x^8 + 7*x^7 + 5*x^6 + 2*x^5 + 5*x^4 + 7*x^3 + x^2 + x + 3 sage: w = WeilPolynomials(10,1,sign=-1,lead=[3,1,1]) sage: it = iter(w) sage: next(it) 3*x^10 + x^9 + x^8 + 6*x^7 - 2*x^6 + 2*x^4 - 6*x^3 - x^2 - x - 3
>>> from sage.all import * >>> w = WeilPolynomials(Integer(10),Integer(1),sign=Integer(1),lead=[Integer(3),Integer(1),Integer(1)]) >>> it = iter(w) >>> next(it) 3*x^10 + x^9 + x^8 + 7*x^7 + 5*x^6 + 2*x^5 + 5*x^4 + 7*x^3 + x^2 + x + 3 >>> w = WeilPolynomials(Integer(10),Integer(1),sign=-Integer(1),lead=[Integer(3),Integer(1),Integer(1)]) >>> it = iter(w) >>> next(it) 3*x^10 + x^9 + x^8 + 6*x^7 - 2*x^6 + 2*x^4 - 6*x^3 - x^2 - x - 3
w = WeilPolynomials(10,1,sign=1,lead=[3,1,1]) it = iter(w) next(it) w = WeilPolynomials(10,1,sign=-1,lead=[3,1,1]) it = iter(w) next(it)
- node_count()[source]¶
Return the number of terminal nodes found in the tree, excluding actual solutions.
EXAMPLES:
sage: from sage.rings.polynomial.weil.weil_polynomials import WeilPolynomials sage: w = WeilPolynomials(10,1,sign=1,lead=[3,1,1]) sage: l = list(w) sage: w.node_count() 158
>>> from sage.all import * >>> from sage.rings.polynomial.weil.weil_polynomials import WeilPolynomials >>> w = WeilPolynomials(Integer(10),Integer(1),sign=Integer(1),lead=[Integer(3),Integer(1),Integer(1)]) >>> l = list(w) >>> w.node_count() 158
from sage.rings.polynomial.weil.weil_polynomials import WeilPolynomials w = WeilPolynomials(10,1,sign=1,lead=[3,1,1]) l = list(w) w.node_count()
- class sage.rings.polynomial.weil.weil_polynomials.WeilPolynomials_iter(d, q, sign, lead, node_limit, parallel, squarefree, polring=None)[source]¶
Bases:
objectIterator created by WeilPolynomials.
EXAMPLES:
sage: from sage.rings.polynomial.weil.weil_polynomials import WeilPolynomials sage: w = WeilPolynomials(10,1,sign=1,lead=[3,1,1]) sage: it = iter(w) sage: next(it) 3*x^10 + x^9 + x^8 + 7*x^7 + 5*x^6 + 2*x^5 + 5*x^4 + 7*x^3 + x^2 + x + 3 sage: w = WeilPolynomials(10,1,sign=-1,lead=[3,1,1]) sage: it = iter(w) sage: next(it) 3*x^10 + x^9 + x^8 + 6*x^7 - 2*x^6 + 2*x^4 - 6*x^3 - x^2 - x - 3
>>> from sage.all import * >>> from sage.rings.polynomial.weil.weil_polynomials import WeilPolynomials >>> w = WeilPolynomials(Integer(10),Integer(1),sign=Integer(1),lead=[Integer(3),Integer(1),Integer(1)]) >>> it = iter(w) >>> next(it) 3*x^10 + x^9 + x^8 + 7*x^7 + 5*x^6 + 2*x^5 + 5*x^4 + 7*x^3 + x^2 + x + 3 >>> w = WeilPolynomials(Integer(10),Integer(1),sign=-Integer(1),lead=[Integer(3),Integer(1),Integer(1)]) >>> it = iter(w) >>> next(it) 3*x^10 + x^9 + x^8 + 6*x^7 - 2*x^6 + 2*x^4 - 6*x^3 - x^2 - x - 3
from sage.rings.polynomial.weil.weil_polynomials import WeilPolynomials w = WeilPolynomials(10,1,sign=1,lead=[3,1,1]) it = iter(w) next(it) w = WeilPolynomials(10,1,sign=-1,lead=[3,1,1]) it = iter(w) next(it)
- node_count()[source]¶
Return the number of terminal nodes found in the tree, excluding actual solutions.
EXAMPLES:
sage: from sage.rings.polynomial.weil.weil_polynomials import WeilPolynomials sage: w = WeilPolynomials(10,1,sign=1,lead=[3,1,1]) sage: it = iter(w) sage: l = list(it) sage: it.node_count() 158
>>> from sage.all import * >>> from sage.rings.polynomial.weil.weil_polynomials import WeilPolynomials >>> w = WeilPolynomials(Integer(10),Integer(1),sign=Integer(1),lead=[Integer(3),Integer(1),Integer(1)]) >>> it = iter(w) >>> l = list(it) >>> it.node_count() 158
from sage.rings.polynomial.weil.weil_polynomials import WeilPolynomials w = WeilPolynomials(10,1,sign=1,lead=[3,1,1]) it = iter(w) l = list(it) it.node_count()
- class sage.rings.polynomial.weil.weil_polynomials.dfs_manager[source]¶
Bases:
objectData structure to manage depth-first search.
Such a structure is created and managed by an instance of
WeilPolynomials_iter. There is generally no need for a user to manipulate it directly.