Abacus

Abacus counts points on an abelian fourfold that is described by its period lattice rather than by equations. You supply a period matrix whose entries are certified intervals, an integer polarization, and optionally an integer matrix giving multiplication by $\sqrt{-5}$. For each prime it returns the characteristic polynomial of Frobenius as an exact integer polynomial, the local L-factor and the point count, or it stops with a message saying why it could not decide. It is a Python package built on Arb's certified theta functions (through python-flint and a small Julia bridge), with PARI/GP used only as an independent cross-check in its tests.

What it does

An abelian fourfolda four-dimensional complex torus, C^4 modulo a lattice, that admits a polarization; the four-dimensional analogue of an elliptic curve can be given analytically by a 4-by-8 period matrix and an alternating integer form $E$, the polarization. Reduced modulo a prime $p$ of good reduction it has finitely many points, and that number is fixed by the characteristic polynomial of the Frobeniusthe map raising coordinates to the p-th power; its characteristic polynomial determines the number of points over F_p and every extension field map:

$$P_p(T) = T^8 + a_1 T^7 + \dots + p^4, \qquad \#A(\mathbb{F}_p) = P_p(1), \qquad |a_k| \le \binom{8}{k}\, p^{k/2}, \quad a_{8-k} = p^{4-k} a_k .$$

The Weil bound and the symmetry on the right confine the unknown coefficients to a finite box of integers. Abacus computes an enclosure of each coefficient (an interval guaranteed to contain it) and lists every integer tuple in the box that lies inside the enclosures. Exactly one survivor is the answer, returned as exact integers. No survivor stops the run with FAIL-WEIL-BOX-EMPTY; several stop it with UNDECIDED-PRECISION and an estimate of the decimal digits the input would need. A coefficient is never rounded to the nearest integer.

The analytic side uses theta constantsvalues at z = 0 of the Riemann theta function with half-integer characteristics, 256 of them in genus 4; together they determine the polarized abelian variety. The period matrix is reduced to a point $\tau$ in the genus-4 Siegel upper half-space and the theta constants are evaluated there by Arb's acb_theta, which returns each value with a claimed error radius. Abacus recomputes the same constants as a truncated lattice sum with a tail bound proved in the package manual, requires the proved bound to dominate the library's radius at the same truncation, and requires the two enclosures to overlap. Any violation stops the run.

If the input carries an action of $\mathbb{Z}[\sqrt{-5}]$ as an integer 8-by-8 matrix $\rho$, Abacus checks exactly that $\rho^2 = -5$ and that $\rho$ is compatible with the polarization ($\rho^T E \rho = 5E$, $\rho^T E + E\rho = 0$). It then confirms from the periods that $\rho$ acts as the scalar $s\, i\sqrt{5}$ with the sign $s$ the input declares; a wrong sign stops the run with FAIL-SIGN-PIN. Conversion between the two sign conventions happens in one function only, convert_sign_convention. One pitfall: replacing $\rho$ by $-\rho$ flips $s$ and every odd L-coefficient $b_P$ while leaving $a_P$ unchanged, so check $s$ before using $b_P$.

Abacus is not a general-purpose counter. Its command-line drivers run a fixed set of test inputs stored in the package's SEEDS.json file. The valid ones are a product of four elliptic curves, the square of a genus-2 Jacobian, a genus-2 Jacobian with complex multiplication, the fourth power of a CM elliptic curve over $\mathbb{Q}(\sqrt{5})$, and the Weil restriction to $\mathbb{Q}$ of a genus-2 Jacobian over $\mathbb{Q}(\sqrt{-5})$. Five more are deliberately wrong inputs that the checks must reject. A new fourfold means calling the library functions from Python. For a single curve given by an equation, use PARI's ellap or hyperellcharpoly directly.

Examples

Run the self-test suite. From the root of BootLoops' bootloops-dev repository (GitHub organization BootLoops-ai):

python3 tools/abacus/selftest.py

The script checks that cypari2 imports and that a julia executable resolves, points ABACUS_EICHLER_PROJECT at the in-repository Eichler.jl if unset, and instantiates that Julia project (the first run may precompile for a few minutes). It then copies the package into a scratch directory and runs run_s0.py and run_s3.py there; a pass shows S0-PASS with 7/7 checks, then BATTERY-PASS(11/11, B5 RUNS+PASS) with 22/22 checks in under a minute and about 0.1 GB of memory, and exits 0. A missing dependency gives a message beginning ABACUS-REFUSAL and exit code 1. Each driver also writes a JSON record of every named check into the scratch copy, so the repository tree is never modified.

The two theta enclosures from Python. The first calls run_s0.py makes, on the curve 11a1, with tools/abacus/ on sys.path:

from flint import ctx
import abcount_s0 as ab
ctx.dps = 60
w1, w2, _ = ab.pari_periods((0, -1, 1, -10, -20), 60)   # period lattice of 11a1 as balls
tau, _ = ab.tau_from_periods(w1, w2)                     # reduced tau, Im tau > 0 certified
t2a, t3a, t4a = ab.theta_nulls_arb(tau)                  # Arb's theta constants
t2d, t3d, t4d, _ = ab.theta_nulls_desk(tau, N=12)        # truncated series + proved tail bound
ab.balls_overlap(t3a, t3d)

The last line is True: the enclosure built from twelve terms of the $q$-series plus the proved tail bound overlaps Arb's, the consistency Abacus demands before it trusts any theta value. run_s0.py goes on to recover $j$ with ab.j_from_theta(t2a, t3a) and to confirm with ab.j_recognition that the curve's exact $j = c_4^3/\Delta$ lies inside that ball while $j\pm1$ and $-j$ do not. It also checks that ab.weil_box_isolate_g1 returns "OK" on a zero-radius enclosure of $a_{13}$ and "UNDECIDED-PRECISION" on one of radius 5, and finishes with a round trip through ab.convert_sign_convention.

Degree-8 assembly and the Weil box. The integer route of test case B1 in run_s3.py, a product of four elliptic curves at $p = 13$:

from flint import acb
import abcount_s0 as ab, abcount_s1 as s1
curves = [(0,-1,1,-10,-20), (1,0,1,4,-6), (1,1,1,-10,-10), (1,-1,1,-1,-14)]   # 11a1, 14a1, 15a1, 17a1
p = 13
a = [ab.ap_naive(*c, p)[0] for c in curves]
c2 = s1.assemble_lp_deg8(a, p)
fe_ok, _ = s1.functional_equation_receipt(c2, p)
verdict, tuples, box = s1.weil_box_isolate_deg8([acb(v) for v in c2[1:5]], p)
cnt = s1.count_from_charpoly(c2)

The run log in the repository records a = [4, -4, -2, -2], c2 = [1, 4, 40, 92, 638, 1196, 6760, 8788, 28561], fe_ok = True and cnt = 46080, the product $10\cdot18\cdot16\cdot16$ of the four curves' point counts. verdict is "OK", meaning exactly one tuple survived; the driver also requires that tuple to equal c2[1:5], here (4, 40, 92, 638). The test repeats the computation with PARI's ellap and the two lists must agree exactly.

Routines

Command-line drivers (tools/abacus/; the top-level files forward to the canonical copies in build/abcount/)

• selftest.py — readies the Julia project, then runs run_s0.py and run_s3.py on a scratch copy of the package; exit 0 only if both pass.
• run_s0.py — genus-1 core checks on one curve at one prime; verdict S0-PASS.
• run_s3.py — the full suite, test cases B1 to B5 and B4s plus the must-fail inputs N1 to N5; verdict BATTERY-PASS.
• run_s1.py, run_s2.py — earlier-stage drivers; by design they stop with an error against the current SEEDS.json, and run_s3.py replays their checks.

Genus-1 core (abcount_s0)

• convert_sign_convention(artifact) — the single conversion site between the two complex-structure conventions ($\tau \to -\bar\tau$, periods conjugated).
• weierstrass_invariants, pari_periods(model, dps), tau_from_periods(w1, w2) — exact $c_4, c_6, \Delta, j$; periods as balls; reduced $\tau$ with certified $\mathrm{Im}\,\tau \gt 0$.
• theta_nulls_arb(tau), theta_nulls_desk(tau, N) — theta constants from Arb and from the truncated series with the proved tail, two independent enclosures.
• j_from_theta(t2, t3), j_recognition(j_ball, j_num, j_den) — $j$ from theta, and the check that the exact $j$ is inside the ball while nearby wrong values are not.
• ap_naive(a1, a2, a3, a4, a6, p), ap_pari(model, p) — $a_p$ by direct count (odd $p$) and by PARI's ellap.
• weil_box_isolate_g1(enclosure, p) — enumerate $|a| \le 2\sqrt{p}$ inside the enclosure: OK, FAIL-WEIL-BOX-EMPTY or UNDECIDED-PRECISION.

Genus 4 and products (abcount_s1)

• tail_bound_c7(g, N, lam_lb), desk_theta_g4_all(taus, N) — the proved tail bound as a certified upper bound, and truncated sums for all 256 characteristics of a block-diagonal $\tau$.
• julia_theta_all_g4(tau_entries, prec, workdir, tag) — one genus-4 acb_theta call through theta_g4_bridge.jl, exact dyadic values both ways; raises an error when ABACUS_EICHLER_PROJECT is unset or no julia executable resolves.
• assemble_lp_deg8(a_list, p), functional_equation_receipt(c, p), weil_box_isolate_deg8(coeff_enclosures, p), count_from_charpoly(c) — exact degree-8 assembly, the symmetry check, the Weil box, and $P_p(1)$.

Genus 2 (abcount_s2)

• periods_from_bridge, recover_tau(Pi) — certified periods of $y^2 = f(x)$, $\deg f = 5$, through period_g2_bridge.jl, and $\tau$ recovered from them with certified symmetry and positivity.
• theta_from_bridge, desk_theta_g2_all(tau, N) — all theta constants of a full (non-diagonal) $\tau$ from Arb, and the independent truncated sums they are checked against.
• count_curve_Fp, count_curve_Fp2, quartic_from_counts(n1, n2, p), hyperellcharpoly_pari(fcoeffs, p), weil_box_isolate_deg4(coeff_enclosures, p) — direct counts, the genus-2 Frobenius quartic, the PARI cross-check, and the degree-4 Weil box.

$\mathbb{Z}[\sqrt{-5}]$ action and number-field cases (abcount_s3, hecke_desk.py)

• ok_action_receipts(rho, E), polarization_type_check(E, declared) — the exact integer predicates on $\rho$, and the polarization type from the Smith normal form; the first failing predicate is named.
• analytic_rep_receipts(Pi, M), sign_pin_receipt(s, declared_s1) — how $\rho$ acts on the tangent space, its sign $s$, and the comparison with the declared convention (verifies or returns FAIL-SIGN-PIN, never converts).
• cornacchia_a2_5b2(p), hecke_ok_eval(p, u), induced_lp_b4(a_P_by_prime, p) — the PARI-free route for the CM curve: $a^2 + 5b^2 = p$ at split primes, $a_P = 0$ at inert ones, degree-16 assembly.
• b5_counts_inert(p), b5_counts_split(p, sval), gp_run(script) — point counts of the genus-2 curve behind the Weil-restriction case at inert and split primes, and the PARI driver for their cross-check (stops with a message if gp is missing).
• jacobi_sum_vectors(p), b3_charpoly(p) — exact $\mathbb{Z}[\zeta_5]$ Jacobi sums giving the Frobenius polynomial of the Jacobian of $y^2 = x^5 + 1$ without PARI; raises FAIL-HECKE-DESK on a non-rational coefficient.

Requirements and source

Python 3 with python-flint and cypari2 (both on pip), the PARI/GP binary gp on PATH, and a julia executable on PATH (set ABACUS_JULIA to use a different one) with the Eichler.jl project named by ABACUS_EICHLER_PROJECT. Eichler.jl is included in the repository under upgrades/Eichler.jl/ and selftest.py defaults to that copy; first use needs julia --project=<project> -e 'import Pkg; Pkg.instantiate()'. The $j$-recognition check uses Lockpick, which the drivers locate in the repository themselves. Tests: python3 tools/abacus/selftest.py.

The code is tools/abacus/ in the bootloops-dev repository, released under the MIT license. The canonical body is in build/abcount/, with small forwarding files at the package root and the manual with the proofs at build/abcount/manuals/abcount.md. Do not rename the abcount_* files; the drivers verify checksums of the modules before running. Credit: acb_theta in Arb/FLINT (F. Johansson, J. Kieffer and contributors), reached through the Eichler Siegel-space wrapper; PARI/GP for ellap and hyperellcharpoly.

← back to the tools index