The two-trace partition number of the Boolean cube: the exact value χ₄ = 6

Abstract

For d ≥ 1, let Q be the Boolean cube of binary words of length 2d, with coordinates indexed by {0,…,2d−1}. A two-trace mask is a set H ⊆ Q for which each word h can be assigned a d-element coordinate set S(h) such that, whenever h and k are distinct words in H, the coordinates on which they differ meet both S(h) ∖ S(k) and S(k) ∖ S(h). Let χ(d) be the least number of nonempty two-trace masks in a partition of Q. We prove that every mask has at most C(2d,d) words, where C(2d,d) is the central binomial coefficient, with equality exactly for the sets of words at Hamming distance d from a fixed centre. The minimum total weight of a fractional cover of Q by masks is 4ᵈ/C(2d,d). For d ≥ 2, we also prove that every mask with at least C(2d,d)−d+1 words is contained in one of these Hamming spheres, and that this threshold is sharp. We determine the first four partition numbers: χ₁ = 2, χ₂ = 4, χ₃ = 5 and χ₄ = 6. For d = 4, we give an explicit partition into six masks. To prove that five masks do not suffice, we first use exchange graphs, shadow bounds in the middle layers and local four-cube arguments to prove that every part would have at most 57 words. We then reduce the remaining possibilities to 488 finite formulas. The final step is computer-assisted: 453 formulas are refuted directly, and binary case trees reduce the remaining 35 to checked leaves, giving 559 independently checked DRAT refutations in total. DRAT denotes the deletion resolution asymmetric tautology format for clausal proofs. The certificates and instructions for reproducing the verification are publicly archived. Preprint, version 1.1, 30 August 2026. This version has not been peer reviewed. The accompanying computer-verification certificates are archived separately at https://doi.org/10.5281/zenodo.21425638. Version 1.1. Venue-neutral revision. This version removes journal-specific typesetting and corrects contextual attribution and references. The mathematical claims, proofs, finite counts, and declared computer-assisted proof boundary are unchanged from version 1.0. This work is not under journal review.