back to table · edit · history · where entries came from · files · download
6126 bytes, as of the version from 2026-11-17 10:38 (current). Recorded here, not run.
"""Sextic Gauss sums (T736).
Requires SageMath 10.9 and numberdb. Run:
sage -pip install numberdb
sage -python generate.py # verify, no write
sage -python generate.py --publish # fill the assigned draft only
The pair (a,b) means the E-primary c=a+b*omega, omega=exp(2*pi*i/3).
Enumerate all nonunit squarefree ideals prime to 6 with norm <= 500.
This cutoff bounds the quotient size and is not part of the natural domain.
The character is the embedded sextic residue symbol, extended by zero at
nonunits. The additive character is exp(2*pi*i*(z-conj(z))/(i*sqrt(3))).
There is no norm normalization. Source: Gao--Zhao, arXiv:2201.01885v2,
sections 2.1--2.2, (2.3)--(2.6).
Exact integer-pair quotient arithmetic and HNF provide N(c) representatives.
Each term is a power of exp(2*pi*i/(6*N(c))); exact cyclotomic reduction
certifies rational values and zero components. Direct Horner evaluation of
that integer polynomial with Arb at >=512 bits encloses the exact sum.
Nonzero components must support more than the requested precision; no
rounded input or truncation tail occurs. Exact rational values stay exact.
All upload credentials and model provenance are supplied by the caller.
"""
import os,sys
from functools import lru_cache
from math import isqrt,gcd
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
def eprimary(c):
a,b=c
if gcd(norm(c),6)!=1 or a%3==0 or b%3:return False
if b%2==0:return (a+b)%4==1
if a%2==0:return b%4==1
return a%4==3
@lru_cache(None)
def primary_lattice(limit):
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 eprimary((a,b)) 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 abs(c[0])%3==2 and ZZ(abs(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)))
ROOTS6=((1,0),(1,1),(0,1),(-1,0),(-1,-1),(0,-1))
def symbol_exponent(x,prime):
if quotient(x,prime) is not None:return None
y=powmod(x,(norm(prime)-1)//6,prime)
for k,r in enumerate(ROOTS6):
if quotient((y[0]-r[0],y[1]-r[1]),prime) is not None:return k
raise ArithmeticError(('no embedded sextic root',x,prime,y))
@lru_cache(None)
def term_counts(c,shift=(1,0),trace=False):
a,b=c;n=norm(c);m=6*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)
t=(2*a-b)*U+(2*b-a)*V if trace else a*V-b*U
counts[(6*t+k*n)%m]+=1
return tuple(counts)
@lru_cache(None)
def exact_sum(c,shift=(1,0),trace=False):
counts=term_counts(c,shift,trace);L=CyclotomicField(6*norm(c))
return L,L(list(counts)),counts
def conjugate_exact(L,x):
order=int(L.gen().multiplicative_order());cs=[0]*order
for j,k in enumerate(x):cs[(-j)%order]+=k
return L(cs)
def ball_value(c,digits=100):
L,x,counts=exact_sum(c)
if x in QQ:return QQ(x)
xc=conjugate_exact(L,x)
real_zero=(x+xc==0);imag_zero=(x-xc==0)
C=ComplexBallField(max(512,numberdb.bits(digits,losing=160)))
root=(C(0,2)*C.pi()/(6*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()
r=C(0).real() if real_zero else v.real()
i=C(0).real() if imag_zero else v.imag()
for part,zero in [(r,real_zero),(i,imag_zero)]:
if not zero:
assert not part.contains_zero(),(c,'unresolved nonzero component')
assert part.accuracy()>=numberdb.bits(digits,losing=20)
v=C(r,i)
assert norm(c) in (v.real()**2+v.imag()**2)
return v
class SexticGaussSums(numberdb.Generator):
table='T736'
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 eprimary(c) 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=SexticGaussSums()
if '--publish' in sys.argv or os.environ.get('NUMBERDB_PUBLISH')=='1':print(g.publish())
else:print(g.verify(sample=None))