back to table · edit · history · where entries came from · files · download
6423 bytes, as of the version from 2026-10-31 10:42 (current). Recorded here, not run.
"""Zeros of Hecke-type Faber polynomials -- numberdb.org/T636.
Run with SageMath (install numberdb once with sage -pip install numberdb):
sage -python generate.py # verify every stored entry
sage -python generate.py --publish # fill an authorized draft; key in env
The latter sends entries, never publishes the website draft publicly.
The monic Faber recurrence uses exact integer eta products. Sage QQbar
isolates every root and compares algebraic real/imaginary parts exactly.
Conversion of the exact algebraic roots to Arb balls gives certified bounds.
For 100 digits the working precision is numberdb.bits(100, losing=96).
The minimum measured nonzero component accuracy is 427 bits.
See numerical-evidence.md for the evidence and checks.py
for independent root certificates, companion comparisons and controls.
See argument-selection.md for the finite extent. No source data is needed
by the generator. Companion snapshots are used only by the checker.
"""
import os
import sys
from functools import lru_cache, cmp_to_key
import numberdb.sage as numberdb
from sage.rings.integer_ring import ZZ
from sage.rings.rational_field import QQ
from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing
import sage.rings.qqbar as qqbar_module
from sage.rings.qqbar import QQbar
# Named imports do not run Sage's final algebraic-field initialization.
if not hasattr(qqbar_module, "QQbar_I"):
qqbar_module._init_qqbar()
from sage.rings.complex_arb import ComplexBallField
CLASSES = ('1A', '2A', '2B', '3A', '3B', '5A', '5B', '7A', '7B', '13A', '13B')
MAX_DEGREE = 10
WORKING_GUARD = 96
ZX = PolynomialRing(ZZ, 'X')
X = ZX.gen()
def multiply(a, b, limit):
return [sum((a[j] * b[k-j] for j in range(max(0, k-len(b)+1),
min(k+1, len(a)))), ZZ(0)) for k in range(limit+1)]
def invert(a, limit):
assert a[0] == 1
b = [ZZ(1)]
for k in range(1, limit+1):
b.append(-sum((a[j]*b[k-j] for j in range(1, min(k+1, len(a)))), ZZ(0)))
return b
def product(exponent, limit, excluded_prime=None):
a = [ZZ(1)] + [ZZ(0)]*limit
for m in range(1, limit+1):
if excluded_prime is not None and m % excluded_prime == 0:
continue
for _ in range(exponent):
for k in range(limit, m-1, -1):
a[k] -= a[k-m]
return a
@lru_cache(maxsize=None)
def coefficients(g, limit):
"""Return c_g(0),...,c_g(limit), with c_g(0)=0 exactly."""
if g not in CLASSES:
raise ValueError('unsupported Monster class')
length = limit+1 # coefficient of q^(limit+1) in q*T_g
if g == '1A':
e4 = [ZZ(1)] + [ZZ(240)*sum((ZZ(d)**3 for d in range(1,k+1)
if k % d == 0), ZZ(0)) for k in range(1,length+1)]
h = multiply(multiply(multiply(e4,e4,length),e4,length),
invert(product(24,length),length),length)
h[1] -= 744
else:
p = int(g[:-1]); e = 24//(p-1)
h = product(e,length,excluded_prime=p)
inverse = invert(h,length)
h[1] += e
if g.endswith('A'):
C = ZZ(p)**(12//(p-1))
for k in range(2,length+1):
h[k] += C*inverse[k-2]
assert h[0] == 1 and h[1] == 0
return tuple(h[1:])
@lru_cache(maxsize=None)
def faber(g, n):
n = int(n)
if n < 1:
raise ValueError('degree must be positive')
c = coefficients(g,n-1)
polynomials = [ZX(1), X]
for d in range(2,n+1):
polynomials.append(X*polynomials[d-1]
-sum((c[k]*polynomials[d-1-k] for k in range(1,d-1)),ZX(0))
-d*c[d-1])
return polynomials[n]
@lru_cache(maxsize=None)
def algebraic_roots(g, n):
p = faber(g,int(n))
roots = p.roots(ring=QQbar)
def compare(left, right):
a, b = left[0], right[0]
if a == b:
return 0
# Conjugates have exactly equal real parts. Recognize this before
# constructing a potentially much larger compositum for a.real()-b.real().
if a.conjugate() == b:
return -1 if a.imag() < b.imag() else 1
for precision in (128, 256, 512, 1024):
F = ComplexBallField(precision)
ar, br = F(a).real(), F(b).real()
if ar < br:
return -1
if ar > br:
return 1
# An unresolved tie is decided algebraically, never by rounded digits.
if a.real() != b.real():
return -1 if a.real() < b.real() else 1
return -1 if a.imag() < b.imag() else 1
roots.sort(key=cmp_to_key(compare))
assert sum(m for z,m in roots) == n
return tuple(roots)
def enclosed_root(g, n, k, digits=100):
z,multiplicity = algebraic_roots(g,int(n))[int(k)-1]
if z.imag() == 0 and z.real() in QQ:
value = QQ(z.real())
else:
field = ComplexBallField(numberdb.bits(digits,losing=WORKING_GUARD))
value = field(z)
assert value.real().is_finite() and value.imag().is_finite()
if z.imag() == 0:
value = value.real()
return {'number':value,'comment':'Multiplicity %d.' % multiplicity}
class FaberZeros(numberdb.Generator):
table = 'T636'
files = ('generate.py', 'checks.py', 'argument-selection.md', 'T635.json',
'T79.json', 'numerical-evidence.md', 'validation-result.json',
'skill-manifest.json')
parameters = ('g','n','k')
type = 'C'
digits = 100
rigour = 'proven'
def enumerate(self, max_degree=MAX_DEGREE):
for g in CLASSES:
for n in range(2,int(max_degree)+1):
for k in range(1,len(algebraic_roots(g,n))+1):
yield {'g':g,'n':n,'k':k}
def value(self,params,digits):
return enclosed_root(str(params['g']),int(params['n']),int(params['k']),digits)
if __name__ == '__main__':
if os.environ.get('NUMBERDB_KEY_FROM_STDIN') == '1':
key = sys.stdin.read().strip()
if '=' in key and key.split('=',1)[0].isidentifier():
key = key.split('=',1)[1].strip().strip('\"\'')
numberdb.configure(api_key=key)
generator = FaberZeros()
if '--publish' in sys.argv or os.environ.get('NUMBERDB_PUBLISH') == '1':
print(generator.publish(message='Fill draft with certified algebraic Faber roots'))
else:
result = generator.verify(sample=None)
print(result)
sys.exit(0 if result.ok else 1)