"""Independent exact Gauss products and character-free point counts for T729.

sage -python independent_check.py > check.log
Place computed.json (offline) or stored-values.json (API readback) alongside.
Does not import the generator. Output RESULT_JSON is the machine evidence.
Shared dependencies: Sage finite fields and cyclotomic arithmetic; numpy for
exact int64 additive convolutions (total tuple count proven below 2^63).
Character evaluation uses a power-residue subgroup and a different generator,
not the production discrete-log histogram or binary-Jacobi recurrence.
"""
import numberdb.sage as numberdb
from sage.rings.integer_ring import ZZ
from sage.rings.number_field.number_field import CyclotomicField
from sage.rings.finite_rings.finite_field_constructor import GF
from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing
import sage.version
from itertools import product
from functools import lru_cache
from math import gcd,lcm,comb
from pathlib import Path
import json,sys,time,hashlib
import numpy as np
HERE=Path(__file__).resolve().parent
R=PolynomialRing(ZZ,'T');T=R.gen()

@lru_cache(maxsize=12)
def gauss(p,r,m):
    q=p**r;F=GF(q,'b');base=F.multiplicative_generator()
    exponent=2
    while gcd(exponent,q-1)!=1:exponent+=1
    g=base**exponent;step=(q-1)//m
    labels={g**(step*j):j for j in range(m)}
    assert len(labels)==m
    hist=[[0]*p for _ in range(m)]
    # Enumerate field elements in additive-coordinate order, not powers of g.
    for x in F:
        if x:hist[labels[x**step]][int(x.trace())]+=1
    K=CyclotomicField(lcm(m,p));z=K.gen();roots=[z**i for i in range(m*p)]
    G={}
    for s in range(1,m):
        G[s]=sum((ZZ(hist[e][t])*roots[(s*e*p+t*m)%(m*p)]
                  for e in range(m) for t in range(p)),K.zero())
        assert G[s]*G[s].conjugate()==q
    return G

def gauss_polynomial(n,d,p):
    # Derive admissible tuples by choosing the last n+1 coordinates.
    admiss=[]
    for tail in product(range(1,d),repeat=n+1):
        a0=(-sum(tail))%d
        if a0:admiss.append((a0,)+tail)
    done=set();factors=[];K=CyclotomicField(d*p);S=PolynomialRing(K,'U');U=S.gen()
    out=S.one(); orbit_degrees=0
    for a in admiss:
        if a in done:continue
        orbit=[];b=a
        while b not in orbit:
            orbit.append(b);done.add(b);b=tuple((p*x)%d for x in b)
        assert b==a
        r=len(orbit);h=d
        for x in a:h=gcd(h,x)
        m=d//h;tail=[x//h for x in a[1:]]
        G=gauss(p,r,m);beta=G[sum(tail)%m]**(-1)
        for x in tail:beta*=G[x]
        assert beta*beta.conjugate()==ZZ(p)**(r*n)
        out*=1-K(beta)*U**r;orbit_degrees+=r
    result=R([ZZ(c) for c in out.list()])
    b=((d-1)**(n+2)+d-1)//d
    assert len(done)==b==orbit_degrees==result.degree()
    return result

@lru_cache(maxsize=40)
def histogram(p,m,d):
    q=p**m;F=GF(q,'c');shape=(p,)*m
    hist=np.zeros(shape,dtype=np.int64)
    for x in F:
        y=x**d
        cs=list(y.polynomial()) if m>1 else [int(y)]
        coords=tuple(int(cs[j]) if j<len(cs) else 0 for j in range(m))
        hist[coords]+=1
    assert int(hist.sum())==q
    return hist

def points(n,d,p,m,all_plus=False):
    q=p**m
    assert q**(n+2)<2**63
    h=histogram(p,m,d)
    ans=np.zeros_like(h);ans[(0,)*m]=1
    support=[(ix,int(h[ix])) for ix in np.ndindex(h.shape) if h[ix]]
    for j in range(n+2):
        dest=np.zeros_like(ans)
        sign=1 if j or all_plus else -1
        for ix,c in support:
            dest+=c*np.roll(ans,tuple(sign*x for x in ix),axis=tuple(range(m)))
        ans=dest
    affine=int(ans[(0,)*m]); assert (affine-1)%(q-1)==0
    return (affine-1)//(q-1)

def traces(P):return (-P[1],P[1]**2-2*P[2])
def valid(P,n,d,p):
    b=((d-1)**(n+2)+d-1)//d;w=n//2
    if P.degree()!=b or P[0]!=1:return False
    eps=ZZ(P[b])/ZZ(p)**(w*b)
    if eps not in (-1,1):return False
    if any(P[b-k]!=eps*ZZ(p)**(w*(b-2*k))*P[k] for k in range(b//2+1)):return False
    return all(abs(c)<=comb(b,k)*ZZ(p)**(w*k) for k,c in enumerate(P.list()))

def run():
    start=time.monotonic()
    path=HERE/'stored-values.json'
    if not path.exists():path=HERE/'computed.json'
    packet=json.loads(path.read_text());rows=packet['rows']
    expected=[(n,d,p) for n,d in [(2,d) for d in range(3,7)]+[(4,3)]
              for p in [2,3,5,7,11,13,17,19,23,29,31] if d%p and (n==2 or p>3)]
    assert [tuple(int(row['params'][k]) for k in ('n','d','p')) for row in rows]==expected
    known=(points(2,4,5,1)==12 and points(2,4,5,1,True)==0
           and points(2,3,2,1)==7 and points(2,3,2,2)==45)
    control=(1-49*T)**20*(1+91*T+2401*T**2)
    assert gauss_polynomial(4,3,7)==control
    assert gauss_polynomial(2,3,2)==(1-4*T**2)**3
    assert known and control[1]!=0
    negative=[];comparisons=[];failures=[]
    for row,(n,d,p) in zip(rows,expected):
        t=time.monotonic();P=R([ZZ(c) for c in row['coefficients']]);Q=gauss_polynomial(n,d,p)
        if P!=Q:failures.append({'params':[n,d,p],'gauss':'mismatch'})
        assert valid(P,n,d,p)
        tr=traces(P); counts=[]
        for m in (1,2):
            count=points(n,d,p,m);pred=sum(ZZ(p)**(j*m) for j in range(n+1))+tr[m-1]
            if count!=pred:failures.append({'params':[n,d,p],'m':m,'actual':str(count),'predicted':str(pred)})
            counts.append(str(count))
        # Full equality checker rejects sign, multiplicity and reversal corruptions.
        neg=(-P!=Q and P*(1-p**(n//2)*T)!=Q and R(list(reversed(P.list())))!=Q)
        assert neg;negative.append(neg)
        comparisons.append({'params':[n,d,p],'degree':int(P.degree()),'coefficient_match':P==Q,
                            'point_counts':counts,'seconds':time.monotonic()-t})
        print('CHECK '+json.dumps(comparisons[-1]),flush=True)
    wrong_model=traces(R([31]+[0])) if False else points(2,4,5,1,True)!=points(2,4,5,1)
    result={'checked_entries':len(rows),'total_entries':48,'failures':failures,
            'known_answer_control':bool(known),'negative_control_rejected':bool(all(negative) and wrong_model),
            'known_controls':{'quartic_p5':12,'all_plus_quartic_p5':0,'cubic_p2':7,'cubic_p2_squared':45,
                              'cubic_fourfold_p7':'(1-49*T)^20*(1+91*T+2401*T^2)'},
            'comparisons':comparisons,'input':path.name,'input_sha256':hashlib.sha256(path.read_bytes()).hexdigest(),
            'program_sha256':hashlib.sha256(Path(__file__).read_bytes()).hexdigest(),
            'sage':sage.version.version,'numpy':np.__version__,'seconds':time.monotonic()-start,
            'method':'exact additive Gauss products, separate power-residue characters and p-orbit construction; exact character-free additive histogram convolution over F_p and F_p^2',
            'limitations':'Shared Sage finite-field/cyclotomic library and theoretical character decomposition. Point counts alone test only two traces. This build evidence is not an independent actor verdict.'}
    print('RESULT_JSON '+json.dumps(result),flush=True)
    assert not failures
if __name__=='__main__':run()
