Finite Cores and Eventual Optimality of Ulam Anticodes

Abstract

The Ulam distance measures how many symbols must be deleted from each of two permutations to obtain a common ordered subsequence. An anticode is a family of permutations whose pairwise distances are bounded by a prescribed diameter. The Devlin-Douhovnikoff conjecture predicts that the largest such families are full symbol cylinders: all permutations formed by freely inserting a fixed set of symbols into one common ordered backbone. For an alphabet of size n and diameter k, the predicted maximum is the product of k consecutive descending integers starting at n. When n is at least k plus three, the conjecture also predicts that cylinders are the only families attaining this maximum. This paper establishes the conjectured maximum and equality classification for every fixed diameter at all sufficiently large alphabet sizes. It gives explicit thresholds, including the sufficient condition that n is at least the result of raising (k + 1) to the power (20 times k squared). The eventual theorem has an analytic proof. Bounded witnesses for the absence of a common center, vertex covers of inversion graphs, and counting arguments based on symbol labels and insertion positions reduce sufficiently large families to free-symbol lifts of Ulam balls. Families outside this structured class have a counting bound of one lower polynomial degree. Exact comparisons among the structured families then identify full cylinders as the unique eventual extremizers. The paper also determines the largest families not contained in any full k-symbol cylinder, at sufficiently large alphabet sizes. These extremal noncylindrical families are full lifts of radius-one balls obtained by freely inserting two fewer symbols than the prescribed diameter. Their exact sizes and equality cases are determined. Comparisons between the canonical ball lifts and cylinders hold at every admissible order. Quantitative exclusion bounds show how many cylinder members become incompatible with an outside permutation, and the largest cylinder-outsider intersection is determined to its sharp leading order. For diameter three, the sufficient eventual threshold improves to two raised to the power 132. Independent exact computations establish the sharp maximum and cylinder uniqueness for every alphabet size from six through twelve. The centered case is resolved at every alphabet size of at least six: a diameter-three family lying within distance two of a common center is strictly smaller than a full three-symbol cylinder. From eight symbols onward, its size is at least four below the cylinder bound. This uniform result follows from Robinson-Schensted recording-tableau estimates for two-row and hook shapes, together with stronger bounds for four exceptional two-row classes. The argument combines induction, explicit inverse-insertion formulas, exact local incompatibility conditions, and a finite induction base. For alphabets of at least thirteen symbols, every diameter-three family containing two distinct full two-symbol cylinders satisfies the conjectured bound, with equality only for a full three-symbol cylinder. The proof covers parallel free directions, intersecting free directions, and every possible relative position of their prescribed symbols in the common backbone. Its ingredients include exact descriptions of common deletion-card hosts, intersection bounds for radius-one balls, factorial-moment identities, Holder's inequality, and explicit partitions into sets of mutually distant orders. Consequently, any remaining diameter-three numerical counterexample or noncylindrical equality example must have radius exactly three and contain at most one full two-symbol cylinder. Several uniform insertion and deletion results are established independently of the eventual extremal argument. An explicit antipodal insertion bijection pairs complete lift fibers and increases every paired distance by exactly the number of inserted symbols. A sharp two-fiber inequality holds at all alphabet sizes through diameter four: two nonempty, mutually compatible insertion fibers over backbones at distance k have combined size at most k plus two. Symbols compulsory in every longest common subsequence, together with Hajnal's independent-set inequality, reduce the verification to cores containing at most twice the diameter in symbols. Strict versions of Hall's matching condition then give the equality classification for parallel-cylinder families through diameter four at every admissible order. A comparison-vector rank argument gives a linear tolerance for outsiders in the first-deletion loss inequality. If a family has s members outside a full k-symbol cylinder, at least n minus k minus twice s backbone coordinates satisfy the sharp deletion-loss bound. Thus a family violating that bound in every coordinate must have at least half the backbone size, rounded upward, outside every full cylinder. Uniform Helly bounds for equal-radius Ulam balls, finite all-card radius-lifting bounds, cylinder-saturation rules, and estimates for intersections of Ulam balls impose additional structural restrictions. The deletion-packet theory supplies a simplicial host in every dimension and an explicit bound on its top reduced Betti number. These topological bounds do not imply the corresponding signed-defect inequalities. Explicit counterexamples refute every cylinder-threshold signed-defect bound at deletion levels of three or higher throughout its nonvacuous range. The examples preserve the complete deletion shadow, and amplified constructions retain an asymptotic proportion of cylinder members tending to one. Further examples distinguish pairwise antipodal matchings from simultaneous couplings and show that several proposed radius-lifting and fiber-capacity assertions fail. The computational supplement includes exact integer verifiers, explicit certificates, result files, and independent implementations of the principal finite checks. The two-fiber certificate examines 20,459 normalized backbone permutations and 9,634,413 nonempty subsets of gap-graph vertices. The coincident-cylinder certificates partition 114 complete hosts containing 106,842 orders; independent verifiers reconstruct the hosts from their deletion conditions and check the required distances. The centered proof uses six fixed satisfiability-modulo-theories formulas with unbounded integer parameters and an exhaustive induction base on eight symbols. All six formulas were independently replayed with Z3 5.1.0 and found unsatisfiable. Complete native solver proof records and integrity hashes are included. These records have not been checked by a separate proof kernel; independent formula replay and mathematical-model auditing are distinguished from that stronger form of verification. The general all-order Devlin-Douhovnikoff conjecture remains open. The paper proves eventual optimality and uniqueness for every fixed diameter, complete diameter-three classifications through twelve symbols, the uniform centered theorem, and the two-cylinder theorem described above. Within the remaining diameter-three interval, any numerical counterexample or noncylindrical equality example must have radius three and contain zero or one full two-symbol cylinder. The global first-loss inequality and the remaining smaller-order ranges for general diameter are not resolved. The deposit contains the manuscript PDF, matching source, and a computational supplement with reproduction instructions, exact data, verification programs, and SHA-256 manifests. The preceding diameter-two study is Comparison Packets and Deletion-Radius Lifting for Diameter-Two Ulam Anticodes, DOI: 10.5281/zenodo.22152825. The eventual theorems and finite whole-family classifications are independent of its all-order result. The strict Hall arguments and full-fiber center bounds explicitly use its sharp diameter-two classification.