Search code for root-unitary (Weil) polynomials
This package implements a search strategy for Weil polynomials (integer polynomials with all roots on a fixed circle) described in:
K.S. Kedlaya, Search techniques for root-unitary polynomials, in Computational Arithmetic Geometry, Contemporary Mathematics 463, American Mathematical Society, 2008, 71-82;
plus some additional improvements described in:
K.S. Kedlaya and A.V. Sutherland, A census of zeta functions of quartic K3 surfaces over F_2, LMS Journal of Computing 19 special issue A (2016), 1-11
and:
K.S. Kedlaya, Improved search techniques for root-unitary polynomials, preprint (2026).
For the version circa 2015, see the branch archive-2015. For the version circa 2025, see the branch archive-2025.
As of December 2019, the code is available in Sage: try
sage: R.<x> = ZZ[]
sage: R.weil_polynomials?
to learn more. I plan to maintain this repository with bugfixes and improvements to the underlying C code, as well as auxiliary code that is not intended for inclusion in Sage. That includes scripts from the aforementioned papers as well as code for abelian varieties in the L-Functions and Modular Forms Database (https://www.lmfdb.org).
The source files for the main package are:
- weil_polynomials.pyx: Cython source file for Sage, providing the class WeilPolynomials to iterate over Weil polynomials
- power_sums.c: C code (using FLINT) to enumerate the tree based on Rolle's theorem, Sturm's theorem, power sum bounds, etc.
- power_sums.h: associated header file
To use the Cython file, from a Sage prompt type
sage: load("weil_polynomials.pyx")
and everything should compile automatically.
If the OpenMP library is available systemwide, you can also do some computations in parallel. To enable this, you will need to uncomment a couple of lines in weil_polynomials.pyx, and possibly change the value of the environment variable OMP_NUM_THREADS (thanks to Edgar Costa for this tip).
There are also some test scripts. See the README files in the following directories:
- test-scripts: Miscellaneous tests
- av-scripts: Build tables associated to abelian varieties
- k3-scripts: Build tables associated to K3 surfaces
- k3-quartic-f2: Scripts and data associated to smooth quartic surfaces over F2
As of 2026, we also provide wrapper code in C and Rust.
This code is made available under the Lesser GNU Public License (LGPL), version 3.0 or any later version.
POSSIBLE TODO LIST:
- Improve scheduling of parallel computation in the current Cython model.
- Add a Julia wrapper for use in Nemo.
- Use real root isolation instead of (or in addition to) Sturm's theorem.
- Use the mts library for budgeted reverse search: http://cgm.cs.mcgill.ca/~avis/doc/tutorial.html
- Compute subresultant sequences using a half-GCD algorithm.
- Compute Hankel determinants using a multimodular algorithm, using continued fractions to handle the mod-p case.
- Compute Hankel determinants even when they are valued in QQ(sqrt(q)) rather than QQ.