generate.py

back to table · edit · history · where entries came from · files · download

12621 bytes, as of the version from 2026-11-20 12:03 (current). Recorded here, not run.

"""Weil polynomials over prime fields: numberdb.org/T214.

Run with SageMath and the numberdb package:

    sage -pip install numberdb
    sage -python generate.py
    sage -python generate.py --publish

The default command verifies every stored polynomial without writing.
Publication requires explicit authorization and configured session credentials.
The independent check_T214.py additionally compares every stored comment.

The exact coefficient bounds enumerate dimension 1 over primes q <= 13
and dimension 2 over primes q <= 11: 60 + 835 = 895 classes. These small
prime-field ranges provide complete low-dimensional reference slices;
the cutoffs are practical, noncanonical choices, not mathematical boundaries.

Simplicity means simplicity over the base field, not geometric simplicity.
A nonsimple surface is isogenous to a product of two elliptic curves.
Over a prime field each integral Hasse-admissible elliptic trace occurs,
so testing for two elliptic Weil factors is sufficient. Polynomial
irreducibility alone is NOT the criterion: (t^2-q)^2 is simple, with
Honda-Tate exponent 2 for the real Weil number sqrt(q).

Theory: Dupuy, Kedlaya, Roe and Vincent, arXiv:2003.05380, Section 2.3;
Waterhouse, Abelian varieties over finite fields (1969), Theorem 4.1.
Counts: OEIS A362198; the independent evidence checks the entire q=11
LMFDB enumeration and all five real-Weil-number exceptional classes.
Integer arithmetic and exact polynomial operations introduce no rounding.
"""

import os
import sys

import numberdb.sage as numberdb
from sage.arith.misc import is_prime
from sage.rings.integer_ring import ZZ
from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing

G1_PRIMES = (2, 3, 5, 7, 11, 13)
G2_PRIMES = (2, 3, 5, 7, 11)
OEIS_A362198 = {2: 35, 3: 63, 5: 129, 7: 207, 11: 401}

ZT = PolynomialRing(ZZ, "t")
t = ZT.gen()

_RECORDS = None
_RECORDS_BY_KEY = None


def _key_from_stdin():
    if os.environ.get("NUMBERDB_KEY_FROM_STDIN") != "1":
        return
    token = sys.stdin.read().strip()
    if "=" in token and token.split("=", 1)[0].isupper():
        token = token.split("=", 1)[1].strip().strip("'\"")
    if token:
        os.environ["NUMBERDB_API_KEY"] = token


def _floor_sqrt_times(coefficient, q):
    return ZZ(coefficient * coefficient * q).isqrt()


def _ceil_sqrt_times(coefficient, q):
    square = ZZ(coefficient * coefficient * q)
    root = square.isqrt()
    return root if root * root == square else root + 1


def _encode_nonnegative(n):
    n = ZZ(n)
    if n < 0:
        raise ValueError("expected a nonnegative integer")
    if n == 0:
        return "a"

    letters = []
    while n:
        n, digit = n.quo_rem(26)
        letters.append(chr(ord("a") + int(digit)))
    return "".join(reversed(letters))


def _encode_lmfdb_integer(n):
    n = ZZ(n)
    if n < 0:
        return "a" + _encode_nonnegative(-n)
    return _encode_nonnegative(n)


def lmfdb_label(g, q, coefficients):
    return "%s.%s.%s" % (
        g, q, "_".join(_encode_lmfdb_integer(c) for c in coefficients))


def _lmfdb_url(label):
    g, q, iso = label.split(".", 2)
    return "https://www.lmfdb.org/Variety/Abelian/Fq/%s/%s/%s" % (g, q, iso)


def _p_rank(q, coefficients):
    rank = 0
    for index, coefficient in enumerate(coefficients, start=1):
        if ZZ(coefficient) % q != 0:
            rank = index
    return ZZ(rank)


def _is_simple_class(dimension, prime, polynomial):
    """Classify valid prime-field Weil polynomials in dimensions 1 and 2.

    A surface is nonsimple exactly when its polynomial is
    (t^2 + first*t + prime)(t^2 + second*t + prime), with both
    integral coefficients satisfying the elliptic Hasse bound.
    This includes repeated elliptic factors, but excludes t^2-prime.
    """
    if not is_prime(prime):
        raise ValueError("simplicity test requires a prime field")
    if dimension == 1:
        return True
    if dimension != 2:
        raise ValueError("simplicity test supports dimensions 1 and 2")

    bound = _floor_sqrt_times(2, prime)
    for first in range(-int(bound), int(bound) + 1):
        second = polynomial[3] - first
        if second * second > 4 * prime:
            continue
        product = ((t**2 + first * t + prime)
                   * (t**2 + second * t + prime))
        if polynomial == product:
            return False
    return True


def _genus1_records(q):
    bound = _floor_sqrt_times(2, q)
    for a1 in range(-int(bound), int(bound) + 1):
        a1 = ZZ(a1)
        polynomial = t**2 + a1 * t + q
        yield _record(1, q, (a1,), polynomial)


def _genus2_records(q):
    bound = _floor_sqrt_times(4, q)
    for a1 in range(-int(bound), int(bound) + 1):
        a1 = ZZ(a1)
        lower = _ceil_sqrt_times(2 * abs(a1), q) - 2 * q
        upper = a1 * a1 // 4 + 2 * q
        for a2 in range(int(lower), int(upper) + 1):
            a2 = ZZ(a2)
            polynomial = t**4 + a1 * t**3 + a2 * t**2 + q * a1 * t + q**2
            yield _record(2, q, (a1, a2), polynomial)


def _record(g, q, coefficients, polynomial):
    label = lmfdb_label(g, q, coefficients)
    rank = _p_rank(q, coefficients)
    simple = _is_simple_class(g, q, polynomial)
    return {
        "g": ZZ(g),
        "q": ZZ(q),
        "label": label,
        "url": _lmfdb_url(label),
        "coefficients": tuple(ZZ(c) for c in coefficients),
        "polynomial": ZT(polynomial),
        "p_rank": rank,
        "ordinary": bool(rank == g),
        "simple": simple,
    }


def _published_order(record):
    """Preserve the original slices' order and the later q=11 label order."""
    if record["g"] == 2 and record["q"] == 11:
        return record["label"]
    return tuple((abs(coefficient), coefficient < 0)
                 for coefficient in record["coefficients"])


def _build_records():
    built = []
    for q in G1_PRIMES:
        if not is_prime(q):
            raise ArithmeticError("%s is not prime" % (q,))
        built.extend(sorted(_genus1_records(ZZ(q)),
                            key=_published_order))
    for q in G2_PRIMES:
        if not is_prime(q):
            raise ArithmeticError("%s is not prime" % (q,))
        built.extend(sorted(_genus2_records(ZZ(q)),
                            key=_published_order))
    return built


def _check_q_reciprocal(record):
    polynomial = record["polynomial"]
    g = int(record["g"])
    q = record["q"]
    if not polynomial.is_monic() or polynomial.degree() != 2 * g:
        raise ArithmeticError("%s is not monic of degree %s"
                              % (record["label"], 2 * g))
    for i in range(g + 1):
        if polynomial[i] != q**(g - i) * polynomial[2 * g - i]:
            raise ArithmeticError("%s does not satisfy q-reciprocity"
                                  % (record["label"],))


def _check_weil_bounds(record):
    g = int(record["g"])
    q = record["q"]
    coefficients = record["coefficients"]
    if g == 1:
        a1, = coefficients
        if a1 * a1 > 4 * q:
            raise ArithmeticError("%s fails the Hasse bound"
                                  % (record["label"],))
        return

    a1, a2 = coefficients
    if a1 * a1 > 16 * q:
        raise ArithmeticError("%s fails the genus 2 trace bound"
                              % (record["label"],))
    lower = _ceil_sqrt_times(2 * abs(a1), q) - 2 * q
    upper = a1 * a1 // 4 + 2 * q
    if not (lower <= a2 <= upper):
        raise ArithmeticError("%s fails the genus 2 Weil bounds"
                              % (record["label"],))


def _check_record(record):
    if lmfdb_label(record["g"], record["q"],
                   record["coefficients"]) != record["label"]:
        raise ArithmeticError("label mismatch for %s" % (record["label"],))
    _check_q_reciprocal(record)
    _check_weil_bounds(record)
    if _p_rank(record["q"], record["coefficients"]) != record["p_rank"]:
        raise ArithmeticError("p-rank mismatch for %s" % (record["label"],))
    if bool(record["p_rank"] == record["g"]) != record["ordinary"]:
        raise ArithmeticError("ordinary mismatch for %s" % (record["label"],))
    if _is_simple_class(record["g"], record["q"], record["polynomial"]) != record["simple"]:
        raise ArithmeticError("simplicity mismatch for %s" % (record["label"],))


def _check_global(records):
    by_pair = {}
    labels = set()
    polynomials = set()
    for record in records:
        _check_record(record)
        key = (record["g"], record["q"])
        by_pair[key] = by_pair.get(key, 0) + 1
        if record["label"] in labels:
            raise ArithmeticError("duplicate label %s" % (record["label"],))
        labels.add(record["label"])
        poly_key = (record["g"], record["q"], str(record["polynomial"]))
        if poly_key in polynomials:
            raise ArithmeticError("duplicate polynomial %s"
                                  % (record["polynomial"],))
        polynomials.add(poly_key)

    for q in G1_PRIMES:
        q = ZZ(q)
        expected = 2 * _floor_sqrt_times(2, q) + 1
        if by_pair.get((ZZ(1), q)) != expected:
            raise ArithmeticError("g=1, q=%s: got %s, expected %s"
                                  % (q, by_pair.get((ZZ(1), q)), expected))
    for q, expected in OEIS_A362198.items():
        key = (ZZ(2), ZZ(q))
        if by_pair.get(key) != expected:
            raise ArithmeticError("g=2, q=%s: got %s, expected %s"
                                  % (q, by_pair.get(key), expected))

    required = {
        "2.2.ab_a": t**4 - t**3 - 2 * t + 4,
        "2.2.ad_f": t**4 - 3 * t**3 + 5 * t**2 - 6 * t + 4,
    }
    by_label = {record["label"]: record for record in records}
    for label, polynomial in required.items():
        if by_label[label]["polynomial"] != polynomial:
            raise ArithmeticError("%s is %s, expected %s"
                                  % (label, by_label[label]["polynomial"],
                                     polynomial))


    exceptional_labels = {
        2: "2.2.a_ae", 3: "2.3.a_ag", 5: "2.5.a_ak",
        7: "2.7.a_ao", 11: "2.11.a_aw",
    }
    for prime, label in exceptional_labels.items():
        exceptional = by_label[label]
        if (exceptional["polynomial"] != (t**2 - prime)**2
                or not exceptional["simple"] or exceptional["p_rank"] != 0
                or exceptional["ordinary"]):
            raise ArithmeticError("real-Weil-number exception failed: %s" % label)
        for product in ((t**2 + prime)**2,
                        (t**2 + t + prime) * (t**2 - t + prime)):
            if _is_simple_class(2, prime, product):
                raise ArithmeticError("elliptic product misclassified over %s" % prime)
    if len(records) != 895:
        raise ArithmeticError("expected all 895 default entries")


def records():
    global _RECORDS
    if _RECORDS is None:
        _RECORDS = _build_records()
        _check_global(_RECORDS)
    return _RECORDS


def records_by_key():
    global _RECORDS_BY_KEY
    if _RECORDS_BY_KEY is None:
        _RECORDS_BY_KEY = {
            (record["g"], record["q"], record["label"]): record
            for record in records()
        }
    return _RECORDS_BY_KEY


def _coerce_params(params):
    return ZZ(params["g"]), ZZ(params["q"]), str(params["label"])


def _comment(record):
    simple = "simple" if record["simple"] else "not simple"
    ordinary = "ordinary" if record["ordinary"] else "not ordinary"
    return (
        "HREF{%s}[LMFDB %s]. The class is %s, has p-rank %s, and is %s."
        % (record["url"], record["label"], simple, record["p_rank"], ordinary)
    )


class WeilPolynomialsOfAbelianVarieties(numberdb.Generator):

    table = os.environ.get("NUMBERDB_TABLE", "T214")
    parameters = ("g", "q", "label")
    type = "Z[]"
    rigour = "exact"

    def enumerate(self):
        for record in records():
            yield {
                "g": record["g"],
                "q": record["q"],
                "label": record["label"],
            }

    def value(self, params, digits):
        record = records_by_key()[_coerce_params(params)]
        _check_record(record)
        return {
            "number": record["polynomial"],
            "comment": _comment(record),
        }


if __name__ == "__main__":
    _key_from_stdin()
    generator = WeilPolynomialsOfAbelianVarieties()

    if os.environ.get("NUMBERDB_PUBLISH") == "1" or "--publish" in sys.argv:
        print(generator.publish(
            message="Weil polynomials over prime fields, g <= 2"))
    else:
        report = generator.verify(sample=None)
        print(report)
        sys.exit(0 if report.ok else 1)