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.
For the version circa 2015, see the branch archive-2015. For an upcoming version with further improvements, see the branch 2026.
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
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.