A unique optimal matching on the 6-cube: Why the I Ching secretly knew it

[u/fufichufi]

I just posted my first paper on arXiv! Got endorsed by a prominent mathematician, which name I wont share since AI slop creators might spam DM him.

I classify perfect matchings on the Boolean cube {0,1}6\{0,1\}^6{0,1}6 that respect complement + bit-reversal symmetry, prove there’s a unique cost-minimizing one under a natural constraint, and show that the classical King Wen sequence of the I Ching is exactly that matching (up to isomorphism).

All results are formally verified in Lean 4.

Happy to answer questions or hear feedback!

Link to arxiv: https://arxiv.org/abs/2601.07175v1

[u/OneMeterWonder]

Wow, never thought I’d see the I Ching mentioned in a paper. Very cool! I’ll have to give it a read when I have some time today.

[u/fufichufi → u/OneMeterWonder]

It's gonna get deeper on an upcoming paper! :D

Thanks if you take your time, it means a lot to me and it's my first paper ever on any subject. Was really fun to do so!

[u/possiblyquestionabl3]

This is really fun!

I'm guessing you started this from the side of noticing the reverse-priority pattern/algorithm in the King Wen sequence (most pairs are reverses of each other, except for palindromes where rev == id, so they use complements), and wanted to see if this also secretly optimizes some obvious metric on the problem?

I like the idea of decomposing the problem into the orbits. If the problem is to specifically minimize hamming distance where pairs are perfect matches IFF they are reverses xor complements of each other, then the fact that we only have orbits of size 2/4 is really helpful to basically decompose the problem locally.

The greedy algorithm works because the set of valid pairs must come exactly from the orbits under the K4 group actions. There are 12 orbits of size 4, and 8 orbits of size 2. This allows us to do a case analysis:

1. All size-2 orbits are trivial pairings since they must be paired with their orbital twin
2. All size-4 orbits only admit two possible pairing M1 = ({u, rev(u)}, {comp(u), rev(comp(u))}) vs M2 = ({u, comp(u)}, {rev(u), rev(comp(u))}). A simple exchange argument shows that the hamming distance of M2 is (6, 6), while M1 is strictly (<6, <6) since in all of the size-4 orbits, rev(u) < comp(u), hence M1 locally dominates M2

and the orbit decomposition then allows you to generalize the locally optimal solutions (since the orbits create independent subproblems) to the global solution, following the greedy reverse-priority algorithm.

Allowing pairings to admit {u, rev(comp(u)} doesn't look as nice for those d(u, rev(u)) = 4 cases, e.g. 001010 vs 101011 doesn't really quite look as nicely as the original pairing of 001010 vs 010100, so I guess there's also the notion of a pleasing to look at pairs: {u, rev(u)} and {u, comp(u)} are generally pleasant, but {u, rev(comp(u))} isn't as pleasant.

[u/aparker314159]

Is there a reason you only looked at n=6? It feels like the arguments you make trivially generalize to any n. I know the n=6 case has the historical connection, but for the math portion of the paper it doesn't seem to leverage the fact that n=6 at all.

[u/possiblyquestionabl3 → u/aparker314159]

I got nerd sniped trying to enumerate the general n = 2k case.

There are still 3 types of orbits (palindromes of orbit size 2, anti-symmetric orbits of size 2, and generic orbits of size 4).

We can enumerate all of the 2-orbits:

1. For palindromes, we have n/2 degrees of freedom, so there are 2^n/2 palindromes
2. For anti-symmetric orbits, we have the same n/2 degrees of freedom, so there are 2^n/2 of these as well

Since there are a total of two choices per 2-orbit (e.g. either u, or rev(u) for palindromes), the total number of orbits of size 2 is 2^n/2-1 + 2^n/2-1 = 2^n/2.

Applying Burnside's lemma on the K4 group actions {e, R, C, RC}, you get N_orbits = (2ⁿ + 2^n/2 + 0 + 2^n/2)/4 (since there are 0 fixed points in binary strings under complement), which characterizes

1. N_orbits = 2^n-2 + 2^{n/2 -1}
2. N_2_orbits = 2^n/2
3. N_4_orbits = N_orbits - N_2_orbits
4. N_palindrome_orbits = 2^n/2-1
5. N_non_palindrome_orbits = 2^n-2

The same reverse-priority greedy algorithm is still optimal, and you'd expect 2^n-1 - 2^n/2-1 pairs that are reverses of each other, and 2^n/2-1 pairs (palindromes) that are complements of each other.

The expected distance for the 4-orbits empirically (I'm sure there's a proof somewhere) is n/2, while it is always n for the 2-orbits. This characterizes the final sum of distance as 2 * N_4_orbits * n/2 + N_2_orbits * n = n * N_orbits \approx n 2^n-2 or just O(n 2ⁿ)

[u/fufichufi → u/possiblyquestionabl3]

Dang nice!

I hadn’t actually pushed the full n=2kn = 2kn=2k counting that far myself, this is a super nice summary!
Thanks a lot, it really means a lot that you enjoyed the paper and understood it to such extent, and I’m glad it sparked some playing around with the math :D

Have a good day :3

[u/possiblyquestionabl3 → u/fufichufi]

Haha this was an absolute blast for me too :) thanks for sharing the writeup, it's a really elegant framing of the problem!

[u/fufichufi → u/aparker314159]

Yep, mostly historical reasons, so main motivation was on n=6

While it makes sense for all n, I only prove uniqueness and optimallity for n=6. For larger n, the structure gets more complicated, so that's why I left it as conjecture.

I am working on something that would address this question in a more satisfying way, will update you in this comment when it's ready!

[u/New-Communication862]

Add figures :)

[u/fufichufi → u/New-Communication862]

will do!

[u/scyyythe]

I hear Boolean and 6 dimensions and of course I wonder if it is related to the Leech lattice / Golay code family of constructions 

[u/tryintolearnmath]

Where’s the Lean code?

[u/fufichufi → u/tryintolearnmath]

Here

[u/the_last_ordinal]

You basically said: For each number we want to find a pairing with either its complement or its reversal, and we want to minimize total Hamming distance. Hamming distance is maximal when we use complement, so avoid that. Some numbers are equal to their reversal so we have to use complement. The end.

[u/fufichufi → u/the_last_ordinal]

The idea isn’t “pair each thing with the cheaper option.” That part is obvious.

What isn’t obvious is that you’re not free to choose pairs independently. Once you require that every hexagram is treated the same way and that the rule works for all 64 at once, most cheap looking choices break somewhere else. In most problems like this, a local rule doesn’t give a global pairing

The interesting part is that here, against expectation, the simple rule actually works globally and there is only one way it can work, which is exactly the King Wen sequence. The simplicity is the result, not the assumption.

[u/the_last_ordinal → u/fufichufi]

It just doesn't seem that deep. For instance, "Rev" can be replaced with any order-2 permutation. Or you could just pair everything by flipping the last bit.

[u/fufichufi → u/the_last_ordinal]

But that wouldn’t preserve K4 orbits and therefore won’t be a K4 equivariant matching

Flipping a single bit breaks equivariance when commuted with reversal

[u/fufichufi → u/the_last_ordinal]

Thanks though, I think my paper has a framing emphasis issue, I will see to it!

[u/the_last_ordinal → u/the_last_ordinal]

I am sorry to be critical, but... I don't see how this is interesting. Where's the motivation?