Extremal diagonal-coherent binary codes: shortened Hamming cores, deep holes, and the 64 I-Ching hexagrams

Source abstract

Each of the 64 hexagrams of the I-Ching, or Book of Changes, is a stack of six Yin-Yang lines and is therefore a binary vector of length 6; the eight hexagrams formed by repeating a single trigram span a doubled-trigram subspace $Δ$. We ask which binary $[6,3,3]$ codes are compatible with this trigram structure. We show that a $[6,3,3]$ code meets $Δ$ in at most four codewords, that the four are then forced to be the doubled trigrams Earth, Fire, Wind and Lake, and that exactly two codes attain this bound: the shortened Hamming code $\mathcal C_A$ and its dual. Since $\mathcal C_A$ has covering radius 2, its eight codewords, their radius-one balls, and its eight deep holes together reconstruct all 64 hexagrams. In general, we call a binary code of length $2m$ with $d \ge 3$ diagonal-coherent if it contains the half of the diagonal subspace $\{(u,u)\}$ coming from even-weight vectors $u$ -- the largest part of that subspace a single-error-correcting code can contain -- and extremal if its dimension is as large as possible. For $m\ge2$ and $r=\lceil\log_2(2m+1)\rceil$, we determine the number $N(m)$ of extremal diagonal-coherent codes with parameters $[\,2m,\ 2m-r,\ \ge3\,]$, show that diagonal coherence entails no loss of redundancy, and determine their minimum distances. We also put these codes in a normal form, determine their hulls, and show that each has covering radius $2$ with exactly $2^r-1-2m$ deep-hole cosets. Finally we propose three open problems.