Graffiti Conjecture 806

Let $S$ be the set of square-free integers in $[2, n]$ and $G = PR[S]$ the graph on $S$ in which two integers are adjacent when they are not coprime. From the cases $n \le 100$ and about twenty further values $n \le 200$ , Graffiti conjectured that the largest adjacency eigenvalue $\lambda_1(G)$ is at most the number of distinct vertex degrees.

False. At $n = 51$ the graph has $31$ vertices, $11$ distinct degrees and $\lambda_1 > 11.846$ ; the conjecture fails again for every $n$ from $786$ to $5000$ , and the deficit $\lambda_1 - D$ grows roughly linearly in $n$ , so no additive correction $\lambda_1 \le D + C$ survives either.

Result: Disproved(see note)
Status: Resolved
AI contribution: AI-discovered
Method: Computation
Field: Spectral graph theory
Posed by: Graffiti (Siemion Fajtlowicz's program)
Year posed: 1995
Years open: 31y
Solved: 2026-08-26
Model: Claude Opus 5 (AI Village)
Vendor: Anthropic
Collaborators: —
Verification: Site-confirmed
Publication: Announced
Significance: 5 / 100
Disclosed cost: —
Wikipedia: No dedicated article

What was actually shown

The repository supplies an executable verifier in exact integer arithmetic; for $n = 51$ an integer vector $x$ satisfies $x^{T}Ax > 11\,x^{T}x$ , so $\lambda_1 > 11 = D$ . The deficit $\lambda_1(n) - D(n)$ grows through $n = 5000$ in the repository's computations, but no asymptotic theorem proving divergence is claimed, so "false for every constant $C$ " is a computed pattern, not a proved one.

One anomaly, which the repository records itself: $n = 51$ lies inside the range Graffiti is said to have tested when it made the conjecture.

What the AI did

Claude Opus 5 identified and verified counterexamples to WOW conjecture 806 in the square-free non-coprimality graph family. It reconstructed the intended graph and degree-count invariant from the original Written on the Wall source, searched the family, found the smallest counterexample at $n=51$ , and produced exact integer Rayleigh-quotient certificates showing that the largest adjacency eigenvalue exceeds the number of distinct degree values.

Verification

Site-confirmed: the repository's verifier, verify_wow1_806.py, was re-run here on 2 September 2026. Fast mode passed 160 assertions and full mode 175, in 21 seconds, with every counterexample certified without floating point - an explicit integer vector $x$ with $x^{T}Ax > D\,x^{T}x$ , which forces $\lambda_1 > D$ by the Rayleigh principle. For $n = 51$ the certificate is $x^{T}Ax = 1117310362790 > 11 \cdot 94319113125$ .

The verifier also confirms the graph construction against direct gcd tests, scans every $n \le 300$ for the least counterexample (it is $51$ ), and checks the neighbouring conjectures 802, 805, 807 and 808 of the same block as controls, which hold on Graffiti's stated range. Its check against the original Written on the Wall text was skipped here, since the text file is not in the repository; statement fidelity rests on the transcription in the script header and on those controls.

No independent specialist review.

Sources

CodeAI Village graffiti-verification (GitLab)Repository: 197 refutations, each with a verifier script

Submitted by VibeGene on 01 Sep 2026

Graffiti Conjecture 806

What was actually shown

What the AI did

Verification

Sources

Discussion