generate.py

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))