back to table · edit · history · where entries came from · files · download
6613 bytes, as of the version from 2026-11-17 11:01 (current). Recorded here, not run.
"""Cubic Gauss sums over the Eisenstein integers (T735).
Requires SageMath (tested with 10.9) and numberdb. Run:
sage -pip install numberdb
sage -python generate.py # verify the stored table, no write
sage -python generate.py --publish # fill the assigned draft only
The parameter pair (a,b) means c=a+b*omega, omega=exp(2*pi*i/3).
The default enumerates every nonunit squarefree ideal prime to 3 with norm
at most 500, using its unique generator c=1 mod 3. Bounds limit the quotient
cardinality; they do not define the natural family. Both conjugate prime
ideals, inert prime ideals and all composites are retained.
The cubic residue symbol is computed in exact integer-pair quotient arithmetic.
Hermite normal form supplies exactly N(c) lattice representatives. Each term
is an exact power of zeta_(3*N(c)), with positive imaginary embedding. The integer polynomial
is evaluated directly at Arb's exp(2*pi*i/(3*N(c))). The helper exact_sum()
also reduces it in its cyclotomic field for exact checking evidence. All
inputs are exact. At least 512 working bits
and a measured component-accuracy guard support 100 significant decimal digits.
For a rational primary squarefree generator c, conjugation and the cube
identity prove G3(c)=abs(c); this value is returned as an exact integer.
Every component of other returned values is certified nonzero by its ball,
never from decimal patterns. There is no truncation error.
Sources: Dunn--Radziwill arXiv:2109.07463v3, (1.6)--(1.8);
David--de Faveri--Dunn--Stucky arXiv:2410.03048v2, (3.5)--(3.8), Lemma 3.1.
The separate build_check.py uses unweighted prime exponential sums and CRT;
it is additional numerical evidence, not this generator's own verification.
Credentials and upload provenance are supplied by the caller's environment.
"""
import os
import sys
from functools import lru_cache
from math import isqrt
import numberdb.sage as numberdb
from sage.rings.integer_ring import ZZ
from sage.rings.rational_field import QQ
from sage.rings.complex_arb import ComplexBallField
from sage.rings.number_field.number_field import CyclotomicField
from sage.matrix.constructor import matrix
def norm(c):
a,b=map(int,c)
return a*a-a*b+b*b
def mul(c,d):
a,b=c; u,v=d
return (a*u-b*v, a*v+b*u-b*v)
def quotient(x,c):
u,v=x; a,b=c; n=norm(c)
A=(a-b)*u+b*v; B=a*v-b*u
if A%n or B%n:
return None
return (A//n,B//n)
def reduce_pair(x,c):
u,v=x; a,b=c; n=norm(c)
q=(((a-b)*u+b*v)//n,(a*v-b*u)//n)
t=mul(c,q)
return (u-t[0],v-t[1])
def powmod(x,e,c):
r=(1,0);x=reduce_pair(x,c)
while e:
if e&1:r=reduce_pair(mul(r,x),c)
x=reduce_pair(mul(x,x),c);e//=2
return r
@lru_cache(None)
def primary_lattice(limit):
# N(a+b*w)>=3*a^2/4 and >=3*b^2/4, so this box is exhaustive.
B=isqrt((4*int(limit))//3)+1
return tuple(sorted(((a,b) for a in range(-B,B+1) for b in range(-B,B+1)
if a%3==1 and b%3==0 and 1<norm((a,b))<=limit),
key=lambda c:(norm(c),*c)))
@lru_cache(None)
def prime_generators(limit):
return tuple(c for c in primary_lattice(limit)
if ZZ(norm(c)).is_prime() or
(c[1]==0 and c[0]<0 and (-c[0])%3==2 and ZZ(-c[0]).is_prime()))
@lru_cache(None)
def factors(c):
rest=c; out=[]
for p in prime_generators(norm(c)):
if norm(p)>norm(rest):break
while True:
q=quotient(rest,p)
if q is None:break
out.append(p);rest=q
assert rest==(1,0),(c,rest)
return tuple(out)
@lru_cache(None)
def selection(limit=500):
return tuple(c for c in primary_lattice(int(limit))
if len(set(factors(c)))==len(factors(c)))
def symbol_exponent(x,prime):
if quotient(x,prime) is not None:return None
y=powmod(x,(norm(prime)-1)//3,prime)
for k,r in enumerate(((1,0),(0,1),(-1,-1))):
if quotient((y[0]-r[0],y[1]-r[1]),prime) is not None:return k
raise ArithmeticError(('no embedded cubic root',x,prime,y))
@lru_cache(None)
def term_counts(c,shift=(1,0),different=False):
a,b=c;n=norm(c);m=3*n
H=matrix(ZZ,[[a,b],[-b,a-b]]).hermite_form()
assert H.det()==n and H[1,0]==0
h0,h1=int(H[0,0]),int(H[1,1]);assert h0*h1==n
fs=factors(c);counts=[0]*m
for u in range(h0):
for v in range(h1):
k=0
for prime in fs:
t=symbol_exponent((u,v),prime)
if t is None:break
k+=t
else:
U,V=mul((u,v),shift)
# Tr(x/c)=[(2a-b)U+(2b-a)V]/N(c).
# (x/c-conj(x/c))/lambda=(aV-bU)/N(c).
t=a*V-b*U if different else (2*a-b)*U+(2*b-a)*V
counts[(3*t+k*n)%m]+=1
return tuple(counts)
@lru_cache(None)
def exact_sum(c,shift=(1,0),different=False):
counts=term_counts(c,shift,different)
L=CyclotomicField(3*norm(c))
return L,L(list(counts)),counts
def ball_value(c,digits=100):
counts=term_counts(c)
if c[1]==0:
# Conjugation makes G real. The cube relation and primary choice give
# G^3=abs(c)^3 for a squarefree rational generator. No digit inspection.
return ZZ(abs(c[0]))
bits=max(512,numberdb.bits(digits,losing=160))
C=ComplexBallField(bits)
root=(C(0,2)*C.pi()/(3*norm(c))).exp()
v=C(0)
for coef in reversed(counts):
v=v*root+coef
assert v.real().is_finite() and v.imag().is_finite()
assert norm(c) in (v.real()**2+v.imag()**2)
for part in (v.real(),v.imag()):
assert not part.contains_zero(),(c,'unresolved component')
assert part.accuracy()>=numberdb.bits(digits,losing=20),(c,part.accuracy())
return v
class CubicGaussSums(numberdb.Generator):
table='T735'
parameters=('a','b')
type='C'
digits=100
rigour='proven'
def enumerate(self,limit=500):
for a,b in selection(int(limit)):
yield {'a':a,'b':b}
def value(self,params,digits):
c=(int(params['a']),int(params['b']))
assert c[0]%3==1 and c[1]%3==0 and norm(c)>1
assert len(set(factors(c)))==len(factors(c))
return ball_value(c,digits)
if __name__=='__main__':
if os.environ.get('NUMBERDB_KEY_FROM_STDIN')=='1':
key=sys.stdin.read().strip()
if '=' in key:key=key.split('=',1)[1].strip().strip('"\'')
numberdb.configure(api_key=key)
g=CubicGaussSums()
if '--publish' in sys.argv or os.environ.get('NUMBERDB_PUBLISH')=='1':
print(g.publish())
else:
print(g.verify(sample=None))