Comparison Packets and Deletion-Radius Lifting for Diameter-Two Ulam Anticodes: A computer-assisted proof of the full k = 2 conjecture for n ≥ 5

Abstract

This record contains the manuscript, LaTeX source, and reproducibility materials for a computer-assisted solution of the diameter-two case of the Devlin–Douhovnikoff Ulam anticode conjecture. For permutations pi and sigma in S_n, the Ulam distance is d_U(pi,sigma) = n - LCS(pi,sigma). The principal theorem proves that, for every n >= 5, a family of permutations having Ulam diameter at most two contains at most n(n-1) members. Equality holds if and only if the family is a full two-symbol cylinder. The proof develops a deletion-shadow framework based on deletion losses, signed comparison packets, radius-one centers, finite-core rigidity, and deletion induction. Its main ingredients include an all-card center theorem, the Defect–Center implication, a uniform uncentered double-shadow defect bound, and an equality-lifting argument recovering a common cylinder backbone. The computer-assisted components are applied only after explicit reductions to finite cores. Independent implementations reproduce the principal bounded certificates. The archive also contains exact maximal-family censuses through n = 12, anchor computations through n = 15, a seven-card envelope computation through order 20, source code, computational ledgers, validation records, and reproducibility instructions. The stronger uniform four-deletion loss inequality and maximal comparison stability statement remain open; neither is required for the diameter-two theorem proved here.