back to table · edit · history · where entries came from · files · download
9668 bytes, as of the version from 2026-11-17 11:56 (current). Recorded here, not run.
"""Independent arithmetic/phase checker for T737, plus auxiliary tail data.
Different arithmetic path: exact integer pairs for the Eisenstein ring,
trial division for support, character-free rational-prime cubic exponential
sums to select local cube roots, and explicit CRT factors. No production
quotient enumeration or gauss_polynomial is called. Sources: DR (1.5)--(1.8),
DFDS (3.2)--(3.6) and (6.8). Shared assumptions: Patterson's theta theorem,
Arb's certified elementary functions, and ordinary exact arithmetic.
"""
import math,functools,json,sys,time
from pathlib import Path
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.real_arb import RealBallField
from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing
W=(0,1);ONE=(1,0);LAM=(1,2)
def mul(x,y):
a,b=x;c,d=y
return (a*c-b*d,a*d+b*c-b*d)
def powe(x,n):
v=ONE
while n:
if n&1:v=mul(v,x)
x=mul(x,x);n//=2
return v
def norm(x):return x[0]**2-x[0]*x[1]+x[1]**2
def neg(x):return (-x[0],-x[1])
def div(x,y):
a,b=x;c,d=y;n=norm(y)
A=a*(c-d)+b*d;B=b*c-a*d
if A%n or B%n:return None
return A//n,B//n
def rep(x):
a,b=x
return x if 2*a-b>0 or (2*a-b==0 and b>0) else neg(x)
def primary(x):
for u in [ONE,neg(ONE),W,neg(W),powe(W,2),neg(powe(W,2))]:
y=mul(x,u)
if y[0]%3==1 and y[1]%3==0:return y
raise ValueError(x)
def lattice(bound):
r=math.isqrt(2*bound)+2
return sorted([(a,b) for a in range(-r,r+1) for b in range(-r,r+1)
if 0<a*a-a*b+b*b<=bound and rep((a,b))==(a,b)],key=lambda x:(norm(x),x))
@functools.lru_cache(None)
def primes(bound):
"""Enumerate primary prime elements by integer primality and norm."""
r=math.isqrt(2*bound)+2;out=[]
for a in range(-r,r+1):
if a%3!=1:continue
for b in range(-r,r+1):
if b%3:continue
n=norm((a,b))
if 1<n<=bound and (ZZ(n).is_prime() or b==0 and a<0 and ZZ(-a).is_prime() and (-a)%3==2):out.append((a,b))
return tuple(sorted(out,key=lambda x:(norm(x),x)))
@functools.lru_cache(None)
def factor(x):
out=[]
for pi in primes(10000):
if norm(pi)>norm(x):break
e=0
while True:
q=div(x,pi)
if q is None:break
x=q;e+=1
if e:out.append((pi,e))
assert norm(x)==1,(x,out)
return tuple(out)
def decompose(m):
x=m;k=0
while True:
q=div(x,LAM)
if q is None:break
x=q;k+=1
if k%3==1:return None,'ramified valuation'
c=ONE;d=ONE
for pi,e in factor(primary(x)):
if e%3==2:return None,'square modulo cube'
c=mul(c,powe(pi,e%3));d=mul(d,powe(pi,e//3))
unit=div(x,mul(c,powe(d,3)));assert norm(unit)==1
if k%3==0:
if unit not in (ONE,neg(ONE)):return None,'unit support'
branch='B';n=k//3;j=0
else:
branch='A';n=(k+1)//3
j=next(j for j in range(3) if unit in (powe(W,j),neg(powe(W,j))))
return {'m':list(m),'norm_m':norm(m),'branch':branch,'n':n,'j':j,'c':list(c),'norm_c':norm(c),'d':list(d),'norm_d':norm(d)},None
# Exact powers in F_q[omega]/(omega^2+omega+1), independently of Sage residue fields.
def modpow(x,n,q):
x=(x[0]%q,x[1]%q);out=ONE
while n:
if n&1:out=tuple(t%q for t in mul(out,x))
x=tuple(t%q for t in mul(x,x));n//=2
return out
@functools.lru_cache(None)
def symbol_prime(x,pi):
n=norm(pi)
if pi[1]==0:
q=-pi[0];y=modpow(x,(n-1)//3,q)
if y==(0,0):return None
return next(j for j in range(3) if tuple(t%q for t in powe(W,j))==y)
p=n;r=(-pi[0]*pow(pi[1],-1,p))%p;y=pow((x[0]+x[1]*r)%p,(p-1)//3,p)
if y==0:return None
return next(j for j in range(3) if pow(r,j,p)==y)
def symbol(x,c):
e=0
for pi,power in factor(c):
j=symbol_prime(tuple(x),pi)
if j is None:return None
e+=j*power
return e%3
def supplementary(c):
for a2 in (-1,0,1):
for a3 in (-1,0,1):
c0=(1+a2*powe(LAM,2)[0]+a3*powe(LAM,3)[0],a2*powe(LAM,2)[1]+a3*powe(LAM,3)[1])
if (c[0]-c0[0])%9==0 and (c[1]-c0[1])%9==0:return a2,a3
raise ValueError(c)
def embed(x,B):return B(x[0])+x[1]*(-B(1)/2+B(0,1)*B(3).sqrt()/2)
@functools.lru_cache(None)
def prime_gauss(pi,bits=640):
B=ComplexBallField(bits);p=norm(pi)
if pi[1]==0:return B(-pi[0])
# Exact counts of cubes modulo the rational prime, no multiplicative symbol.
counts=[0]*p
for x in range(p):counts[pow(x,3,p)]+=1
z=(B(0,2)*B.pi()/p).exp()
# Horner rather than p transcendental evaluations.
s=B(0)
for count in reversed(counts):s=s*z+count
assert s.imag().contains_zero() and s.real().is_finite()
target=-p*embed(pi,B);base=target**(QQ(1)/3);w=embed(W,B)
roots=[base*w**j for j in range(3)]
good=[g for g in roots if (2*g.real()-s.real()).contains_zero()]
assert len(good)==1,(pi,roots,s)
g=good[0];assert (g**3-target).contains_zero()
assert all(not (2*h.real()-s.real()).contains_zero() for h in roots if h is not g)
return g
@functools.lru_cache(None)
def gauss(c,bits=640):
B=ComplexBallField(bits);v=B(1);cur=ONE;w=embed(W,B)
if c[1]==0:return B(abs(c[0]))
for pi,e in factor(c):
assert e==1
ph=symbol(cur,pi)
assert ph is not None
v*=w**((-ph)%3)*prime_gauss(pi,bits);cur=mul(cur,pi)
assert cur==c
return v
def coefficient(row,bits=640):
B=ComplexBallField(bits);c=tuple(row['c']);j=row['j'];n=row['n']
g=gauss(c,bits)
if c[1]==0:g=B(1) # exact cancellation of |c| against sqrt(N(c))
if row['branch']=='A':
a2,a3=supplementary(c);ph=(j*a2-2*a3)%3
# g(u,c)=conjugate(symbol(u,c))*g(1,c); conjugate once more in tau.
g=g.conjugate()*embed(W,B)**ph
g*=((B(0,2)*B.pi()/9)*[0,-1,1][j]).exp()
exponent=n+4
else:g=g.conjugate();exponent=n+5
return g*B(QQ(row['norm_d'])*3**exponent/(1 if c[1]==0 else row['norm_c'])).sqrt()
def finite_narrow(z,bits=350):
assert z.real().is_finite() and z.imag().is_finite()
for v in (z.real(),z.imag()):
assert v.rad()<QQ(1)/2**bits
return True
def stored_interval(text,CI):
from decimal import localcontext
from numberdb._compare import _complex_parts,_claim
from fractions import Fraction
def part(t):
if t.startswith('[') and t.endswith(']'):
lo,hi=[Fraction(x.strip()) for x in t[1:-1].split(',')]
return CI.base_ring()(QQ(lo.numerator)/lo.denominator,QQ(hi.numerator)/hi.denominator)
with localcontext() as ctx:
ctx.prec=1000
c,r=_claim(t)
lo,hi=Fraction(c-r),Fraction(c+r)
return CI.base_ring()(QQ(lo.numerator)/lo.denominator,QQ(hi.numerator)/hi.denominator)
re,im=_complex_parts(text) or (text,'0')
return CI(part(re),part(im))
def run(filename='computation.json',bound=1000,aux=False):
from sage.rings.complex_interval_field import ComplexIntervalField
from numberdb._compare import _complex_parts, _claim
from decimal import localcontext
from fractions import Fraction
t=time.time();B=ComplexBallField(640);CI=ComplexIntervalField(640)
path=Path(filename)
if path.exists():data=json.load(open(path))
else:
base=Path(__file__).resolve().parent
data={'selection':json.load(open(base/'selection.json')),'entries':json.load(open(base/'computed-entries.json'))}
production={tuple(r['m']):r for r in data['selection']};entries={tuple(int(e['params'][k]) for k in ['a','b']):e['number'] for e in data['entries']}
found={};excluded={};failures=[]
for m in lattice(bound):
row,reason=decompose(m)
if row is None:excluded[reason]=excluded.get(reason,0)+1
else:found[m]=row
assert set(found)==set(production)
assert all(found[m]==production[m] for m in found)
values={}
for i,(m,r) in enumerate(found.items()):
v=coefficient(r);finite_narrow(v);values[m]=v
stored=stored_interval(entries[m],CI)
# Decoding API storage is done by the same public package as an external user.
si=CI(stored);vi=CI(v)
assert all(s.lower()<=t.lower() and t.upper()<=s.upper() for s,t in [(si.real(),vi.real()),(si.imag(),vi.imag())]),(m,str(v),entries[m])
if i%100==0:print('independent',i,round(time.time()-t,2),file=sys.stderr,flush=True)
controls={}
def control(name,m,wanted):
v=values[m];controls[name]=bool((v-wanted).contains_zero());assert controls[name]
control('tau_lambda_minus3',(1,0),9*B(3).sqrt())
control('tau_one',rep(powe(LAM,3)),B(27))
control('tau_lambda_minus1',rep(powe(LAM,2)),9*B(3).sqrt())
for j in [1,2]:control('ninth_phase_'+str(j),rep(mul(powe(W,j),powe(LAM,2))),9*B(3).sqrt()*((B(0,2)*B.pi()/9)*[0,-1,1][j]).exp())
for m in [LAM,W]:assert decompose(m)[0] is None
controls['zero_support']=True
# All perturbations must fail; finite/narrow validation precedes overlap tests.
key=next(m for m,v in values.items() if not v.imag().contains_zero());v=values[key]
negatives={'conjugation':not (v-v.conjugate()).contains_zero(),'perturb_component':not (v-(v+B(1)/10**60)).contains_zero(),'ramified_factor':not (v-v/B(3).sqrt()).contains_zero()}
p=rep(mul(W,powe(LAM,2)));negatives['reverse_ninth_phase']=not (values[p]-values[p].conjugate()).contains_zero()
assert all(negatives.values())
common=[r for r in found.values() if r['c']==[-2,0] and r['d']==[-2,0]];assert common
controls['shared_prime_c_d_minus2']=True
# Known recurrences, evaluated independently from both parameter decompositions.
ram=0;cube=0
for m,r in found.items():
m2=rep(mul(m,powe(LAM,3)))
if m2 in values:assert (values[m2]-B(3).sqrt()*values[m]).contains_zero();ram+=1
h=(-2,0);m3=rep(mul(m,powe(h,3)))
if m3 in values:assert (values[m3]-2*values[m]).contains_zero();cube+=1
return {'checked_entries':len(found),'total_entries':len(entries),'failures':failures,'known_answer_control':all(controls.values()),'negative_control_rejected':all(negatives.values()),'controls':controls,'negative_controls':negatives,'enumeration_exclusions':excluded,'ramified_recurrences':ram,'cube_recurrences':cube,'seconds':time.time()-t},values
if __name__=='__main__':
result,_=run();print(json.dumps(result,indent=2))