Erdős Problem 848: A Kernel-Checked Proof of the Exact Extremal Bound

Source abstract

For N >= 1, let A be a subset of {1, ..., N} satisfying the condition that ab + 1 is nonsquarefree for every a, b in A. We determine the exact maximum cardinality of such a set, proving that |A| is at most the number of integers n in {1, ..., N} congruent to 7 modulo 25, with equality attained by the progression 7 modulo 25. Thus the extremal value is established for every N, closing the finite range left by the preceding asymptotic results. The proof begins with an exact Hall reformulation. A prefix-colouring certificate handles N <= 5,000,000; for larger N, uniform square-divisor estimates, opposite-base matchings, and valuation-cell-fibre decompositions reduce the remaining Hall defects to finitely many exact rational certificate states, together with a uniform argument on the unbounded tail. Certificate generators lie outside the trusted base: they emit ordinary Lean data, semantic checkers prove the required statements about that data, and the Lean 4 kernel replays the terminal all-N theorem with --trust=0. The complete proof archive, semantic checkers, theorem map, and reproduction metadata are available under code concept DOI 10.5281/zenodo.21750213.