[IEEE Trans. on Information Theory, vol. 68, no. 1, pp. 130-152, January 2022 ]
Hexagonal Run-Length Zero Capacity Region, Part I — Analytical Proofs
Spencer Congero and Kenneth Zeger
Abstract
The zero capacity region for hexagonal (d,k) run-length constraints
is known for many, but not all, d and k.
The pairs (d,k) for which it has been unproven whether the capacity is zero or positive consist of:
(i) k=d+2 when d ≥ 2;
(ii) k=d+3 when d ≥ 1;
(iii) k=d+4 when either d=4 or d is odd and d ≥ 3;
(iv) k=d+5 when d=4.
Here, we prove that the capacity is zero
for all of case (i),
and for case (ii) whenever d ≥ 7.
The method used in this paper is to
reduce an infinite search space of valid labelings
to a finite set of configurations that we exhaustively examine
using backtracking.
In Part II of this two-part series,
we use automated procedures to prove that the capacity is zero
in case (i) when 2 ≤ d ≤ 9,
in case (ii) when 3 ≤ d ≤ 11,
and
in case (iii) when d ∈ {4,5,7,9},
and that the capacity is positive
in case (ii) when d ∈{1,2},
in case (iii) when d = 3,
and
in case (iv).
Thus, the only remaining unknown cases are now when k=d+4, for any odd d ≥ 11.