independent.py

back to table · edit · history · where entries came from · files · download

9668 bytes, as of the version from 2026-11-17 11:46. 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))