Optimal Equivariant Matchings on the 6-Cube with an Application to the King Wen Sequence

Technical Summary: Optimal Equivariant Matchings on the 6-Cube

Problem Statement
The paper investigates the problem of finding optimal perfect matchings on the Boolean hypercube $\{0, 1\}^6$, which represents the 64 hexagrams of the I Ching. The study focuses on matchings that are equivariant under the action of the Klein four-group $K_4 = \langle \text{comp}, \text{rev} \rangle$, generated by bitwise complement ($\text{comp}$) and bit reversal ($\text{rev}$). The primary objective is to determine which equivariant matchings minimize the total Hamming distance (the sum of distances between paired elements) and to analyze how the inclusion of Hamming weight conservation alters the optimization landscape. Specifically, the paper seeks to explain why the historically significant King Wen sequence of the I Ching corresponds to a specific matching rule.

Methodology
The authors employ a combination of combinatorial analysis, group theory, and formal verification:

1. Group Action Analysis: The 64 vertices of the hypercube are partitioned into orbits under the $K_4$ action. The paper distinguishes between orbits of size 4 (generic hexagrams) and size 2 (palindromes and anti-symmetric hexagrams).
2. Cost Analysis: The Hamming distance $d_H$ is calculated for all possible pairings induced by the group elements: $\text{comp}$, $\text{rev}$, and $\text{comp} \circ \text{rev}$.
3. The "No-Conflict" Lemma: A central theoretical tool is Lemma 2.12, which establishes that for any hexagram $h$, the operations $\text{comp}$ and $\text{rev}$ never genuinely compete. If $\text{rev}(h) \neq h$, then $d_H(h, \text{rev}(h)) < d_H(h, \text{comp}(h)) = 6$. If they are equal in cost, the options coincide. This eliminates global optimization conflicts, allowing a greedy "reverse-priority" rule to yield a global optimum.
4. Weighted Energy Minimization: To address the discrepancy between the King Wen matching and the pure Hamming optimum (which allows $\text{comp} \circ \text{rev}$), the authors introduce a weighted energy function $E_{\alpha, \beta} = \alpha|\Delta w| + \beta d_H$, where $w$ is the Hamming weight. This allows for a phase-boundary analysis between weight preservation and distance minimization.
5. Formal Verification: All finite orbit counts, case distinctions, and computational checks regarding the 32 pairs of the King Wen sequence were verified using Lean 4 with the Mathlib library.

Key Results

• Uniqueness of the Reverse-Priority Matching (Theorem 1.1): Among matchings restricted to $\text{comp}$ or $\text{rev}$ pairings, there exists a unique perfect matching that minimizes total Hamming cost. This matching is defined by the reverse-priority rule: pair $h$ with $\text{rev}(h)$ unless $h$ is a palindrome (where $\text{rev}(h)=h$), in which case pair it with $\text{comp}(h)$.

  • Cost: This matching has a total Hamming cost of 120.
  • Comparison: This is significantly lower than the complement-only matching, which has a cost of 192.

• Isomorphism with the King Wen Sequence (Theorem 1.2): The traditional King Wen sequence of the I Ching realizes exactly this unique reverse-priority matching. The 32 pairs in the sequence correspond precisely to the pairs generated by the reverse-priority rule.

• Pure Hamming vs. Weighted Optimality:

  • If the constraint is relaxed to allow the full $K_4$ action (including $\text{comp} \circ \text{rev}$), the pure Hamming cost can be lowered to 96.
  • However, the King Wen rule is recovered as the unique optimum when Hamming weight preservation is prioritized. The reverse-priority rule minimizes failures of weight preservation first, and Hamming distance second.
  • Phase Boundary (Theorem 4.9): In the weighted energy model $E_{\alpha, \beta}$, the reverse-priority choice (King Wen) is strictly optimal whenever $\alpha > \beta$. At $\alpha = \beta$, the choices tie; for $\alpha < \beta$, the pure Hamming optimum (using $\text{comp} \circ \text{rev}$) is preferred.

• Structural Constraints: The paper identifies that the 8 palindromic hexagrams form 4 orbits of size 2. In these cases, reversal is trivial, forcing a complement pairing which inevitably fails to preserve Hamming weight. This failure is unavoidable for any non-trivial $K_4$-equivariant matching.

Significance and Claims
The paper claims that the King Wen sequence is not merely a historical artifact but is mathematically canonical. It represents the unique solution to a specific optimization problem: minimizing Hamming distance among matchings that strictly prioritize the preservation of Hamming weight (yin-yang balance).

The authors emphasize that the "greedy" nature of the King Wen rule works globally because of the specific arithmetic properties of the 6-cube under the $K_4$ action. The "No-Conflict Lemma" ensures that local choices (preferring reversal over complement) never lead to global suboptimality within the restricted class of $\text{comp}/\text{rev}$ matchings. The paper concludes that the King Wen sequence is stable under a weighted variational principle where weight preservation is valued more highly than distance reduction ($\alpha > \beta$), providing a rigorous mathematical justification for the sequence's structure.

The work is modest in its scope, focusing strictly on $n=6$ and the $K_4$ group, noting that while generalizations to $n$ exist, the specific arithmetic conditions that eliminate ambiguous ties (specifically regarding $n=6$) may not hold for all dimensions.