Zero Capacity Region of Multidimensional Run Length Constraints

Hisashi Ito

Department of Information Science Toho University, Chiba 274-8510, Japan

        his@kuro.is.sci.toho-u.ac.jp

Akiko Kato

Dept. of Mathematical Engineering and Information Physics

University of Tokyo, Tokyo 113-8656, Japan

       akiko@misojiro.t.u-tokyo.ac.jp

Zsigmond Nagy

Department of Electrical and Computer Engineering University of California, San Diego, CA 92093-0407

             nagy@code.ucsd.edu

Kenneth Zeger

Department of Electrical and Computer Engineering University of California, San Diego, CA 92093-0407

               zeger@ucsd.edu

Submitted: April 24, 1999; Accepted: September 1, 1999. 1991 Mathematics Subject Classification: 94A99, 58F03. the electronic journal of combinatorics 6 (1999), #R33 2

0This work was supported in part by the National Science Foundation and by a JSPS Fellowship for Young Scientists. A portion of this work was presented in Japanese at the Research Institute for Mathematical Sciences Workshop (RIMS Kokyuroku), Kyoto University, Japan, January 1999.

Abstract

For integers d and k satisfying 0 ≤ d ≤ k, a binary sequence is said to satisfy a one-dimensional (d, k) run length constraint if there are never more than k zeros in a row, and if between any two ones there are at least d zeros. For n ≥ 1, the n-dimensional (d, k)-constrained capacity is defined as

C_{d,k}^{(n)} = lim_{m_{1},m_{2},...,m_{n}→∞} \frac{log_{2} N_{m_{1},m_{2},...,m_{n}}^{(n;d,k)}}{m_{1}m_{2} ⋯ m_{n}}

where N_{m_{1},m_{2},...,m_{n}}^{(n;d,k)} denotes the number of m_{1} × m_{2} × ⋯ × m_{n} n-dimensional binary rectangular patterns that satisfy the one-dimensional (d, k) run length constraint in the direction of every coordinate axis. It is proven for all n ≥ 2, d ≥ 1, and k > d that C_{d,k}^{(n)} = 0 if and only if k = d + 1. Also, it is proven for

every d ≥ 0 and k ≥ d that lim_{n→∞} C_{d,k}^{(n)} = 0 if and only if k ≤ 2d.

1 Introduction

A binary sequence is (d, k)-constrained (or “runlength constrained”) if there are at most k consecutive zeros and between every two ones there are at least d consecutive zeros. An n-dimensional pattern of zeros and ones arranged in an m_{1} × m_{2} × ⋯ × m_{n} hyper-rectangle is (d, k)-constrained if it is (1-dimensional) (d, k)-constrained in each of the n coordinate axis directions. The n-dimensional (d, k)-capacity is defined as

C_{d,k}^{(n)} = lim_{m_{1},m_{2},...,m_{n}→∞} \frac{log_{2} N_{m_{1},m_{2},...,m_{n}}^{(n;d,k)}}{m_{1}m_{2} ⋯ m_{n}} ,

where N_{m_{1},m_{2},...,m_{n}}^{(n;d,k)} denotes the number of (d, k)-constrained patterns on an m_{1} ×m_{2} × ⋯ × m_{n} hyper-rectangle. A simple proof was given in [5] that shows the existence of two-dimensional (d, k)-capacities, and a slight modification of the proof can show that the n-dimensional (d, k)-capacities exist. The capacity C_{d,k}^{(n)} represents the maximum number of bits of information that can be stored asymptotically per unit volume in n-dimensional space without violating the (d, k) constraint.

The study of 1-dimensional (d, k)-capacities was originally motivated by applications in magnetic storage. Interest in 2-dimensional (d, k)-capacities has recently increased due to emerging 2-dimensional optical recording devices, and the 3-dimensional (d, k)-capacities may play a role in future applications as well. A tutorial on these topics is given in [4]. Capacities in four and higher dimensions yield natural generalizations of interesting mathematical questions in lower dimensions.

In general, the exact values of the various n-dimensional (d, k)-capacities are not known except in a few cases [6]. For example, in all dimensions, if k = d the capacity is zero, and if d = 0 the capacity is positive for all k ≥ 1. In one dimension the capacity is positive whenever k > d ≥ 0. The capacity is known to be a monotonically nonincreasing function of n and d and a monotonically nondecreasing function of k. It was recently shown [5] that whenever k > d ≥ 1, the 2-dimensional capacity is zero if and only if k = d + 1. These facts are summarized in our Lemma 1.

Some interesting facts are known about the capacities for d = 0 and k = 1 in three and lower dimensions. In one dimension, N_{m}^{(1;0,1)} is known [6] to be a Fibonacci sequence with initial conditions N_{1}^{(1;0,1)} = 2 and N_{2}^{(1;0,1)} = 3, and thus the 1-dimensional (0, 1)-capacity is the logarithm of the golden mean, namely C_{0,1}^{(1)} = log_{2} \frac{1+\sqrt{5}}{2} ≈ 0.694. Very tight upper and lower bounds on the (0, 1)-capacity were given for two dimensions in [2] and for three dimensions in [7]. These two and three dimensional (0, 1)-capacities are C_{0,1}^{(2)} ≈ 0.58789116 and C_{0,1}^{(3)} ≈ 0.52, given here to their known accuracies.

In this paper we present two main results that characterize the zero capacity region for finite dimensions and in the limit of large dimensions. The first result generalizes the zero capacity characterization in [5] to all dimensions greater than one. Namely it gives a necessary and sufficient condition on d and k for the capacity to equal zero. This condition turns out to be exactly the same as in dimension 2. The second result gives a necessary and sufficient condition on d and k, such that the capacity approaches zero in the limit as the dimension n grows to infinity. These results are summarized in the following two theorems.

Theorem 1 For every n ≥ 2, d ≥ 1, and k > d,

C_{d,k}^{(n)} = 0 ⇔ k = d + 1.

Theorem 2 For every d ≥ 0 and k ≥ d,

lim_{n→∞} C_{d,k}^{(n)} = 0 ⇔ k ≤ 2d.

The following lemma contains useful facts about capacities for various constraints and is used to establish Theorems 1 and 2.

Lemma 1

(a) C_{d,k+1}^{(n)} ≥ C_{d,k}^{(n)}; whenever n ≥ 1, 0 ≤ d ≤ k

(b) C_{d,k}^{(n)} ≥ C_{d+1,k}^{(n)}; whenever n ≥ 1, 0 ≤ d < k

(c) C_{d,k}^{(n+1)} ≤ C_{d,k}^{(n)}; whenever n ≥ 1, 0 ≤ d < k

(d) C_{d,d}^{(n)} = 0; whenever n ≥ 1, d ≥ 0

(e) C_{d,2d+1}^{(n)} ≥ \frac{1}{2(d+1)}; whenever n ≥ 1, d ≥ 0

(f) C_{0,k}^{(n)} > 0; whenever n ≥ 1, k ≥ 1

(g) C_{d,k}^{(1)} > 0; whenever 0 ≤ d < k

(h) C_{d,k}^{(2)} = 0 if and only if k = d + 1; whenever 1 ≤ d < k .

Proof.

(a) Follows from the fact that N_{m_{1},m_{2},...,m_{n}}^{(n;d,k+1)} ≥ N_{m_{1},m_{2},...,m_{n}}^{(n;d,k)} since any pattern that satisfies the (d, k) constraint also satisfies the (d, k + 1) constraint.

(b) Follows from N_{m_{1},m_{2},...,m_{n}}^{(n;d,k)} ≥ N_{m_{1},m_{2},...,m_{n}}^{(n;d+1,k)}.

(c)

C_{d,k}^{(n+1)} = lim_{m_{1},m_{2},...,m_{n+1}→∞} \frac{log_{2} N_{m_{1},m_{2},...,m_{n+1}}^{(n+1;d,k)}}{m_{1}m_{2} … m_{n+1}}
≤ lim_{m_{1},m_{2},...,m_{n+1}→∞} \frac{log_{2}(N_{m_{1},m_{2},...,m_{n}}^{(n;d,k)})^{m_{n+1}}}{m_{1}m_{2} … m_{n+1}} = lim_{m_{1},m_{2},...,m_{n}→∞} \frac{log_{2} N_{m_{1},m_{2},...,m_{n}}^{(n;d,k)}}{m_{1}m_{2} … m_{n}}
= C_{d,k}^{(n)}.

(d) C_{d,d}^{(1)} = 0 since N_{m}^{(1;d,d)} ≤ d + 1. The result then follows by induction and from the monotonicity in part (c).

(e) Let T = {1, 2, …, m}, where m is a multiple of 2(d + 1). Any mapping f : T^{n} → {0, 1} satisfying f(x_{1}, x_{2}, …, x_{n}) = 1 when 2(d + 1) divides ∑_{i=1}^{n} x_{i}, and f(x_{1}, x_{2}, …, x_{n}) = 0 when d + 1 does not divide ∑_{i=1}^{n} x_{i}, induces a (d, 2d + 1)-constrained pattern on T^{n}. Since the value of f(x_{1}, x_{2}, …, x_{n}) can be chosen arbitrarily when ∑_{i=1}^{n} x_{i} ≡ (d+1) mod 2(d+1), the number of (d, 2d+1)-constrained patterns on T^{n} is at least 2^{m^{n}/(2(d+1))} and hence N_{m,m,...,m}^{(n;d,2d+1)} ≥ 2^{m^{n}/(2(d+1))}. Thus

C_{d,2d+1}^{(n)} ≥ lim_{m→∞} \frac{m^{n}/(2(d + 1))}{m^{n}} = \frac{1}{2(d + 1)}.

(f) Follows from (a) and (e).

(g) It is known [1] that C_{d,∞}^{(1)} = C_{d−1,2d−1}^{(1)} for d ≥ 1, and also that for 0 ≤ d < k < ∞, the 1-dimensional capacity is the logarithm (base 2) of the largest real root of the equation X^{k+1} − X^{k−d} − X^{k−d−1} − ⋯ − X − 1 = 0. The equation clearly has a root greater than 1, and thus the result follows.

(h) This was proven in [5].

□

2 Proof of Theorem 1

Proof. Lemma 1(c),(h) shows that C_{d,d+1}^{(n)} = 0 for all d ≥ 1 and all n ≥ 2. To prove C_{d,k}^{(n)} > 0 for k ≥ d + 2, it suffices by Lemma 1(a),(h) to prove C_{d,d+2}^{(n)} > 0 for all d ≥ 1 and n ≥ 3. This is shown below in Proposition 1 for even d ≥ 0, and in Proposition 2 for odd d ≥ 3. A special case of Lemma 1(e) shows the result for d = 1 and for all n ≥ 3. This completes the proof of Theorem 1.

□

The following definitions are useful for proving Propositions 1 and 2. Let S={0,1,…, d + 1}. The set S^{n} is an n-cube, and any mapping g : S^{n} → {0, 1} is a binary n-cube. A row of an n-cube is any set of the form {(c_{1}, …, c_{l−1}, x, c_{l+1}, …, c_{n}) : x ∈ S} for some fixed l, and some fixed c_{j} ∈ S for j = 1, …, l − 1, l + 1, …, n. A binary n-cube g is a permutation n-cube if g equals 1 once per row of S^{n}.

A binary n-cube g is (d, d + 2)-constrained unless g takes the value one twice on some consecutive d points in some row of S^{n}. It is clear that permutation n-cubes are (d, d + 2)-constrained. A set of permutation n-cubes is (d, d + 2)-compatible if the concatenation of any two of the cubes along a face (i.e. with translation but without rotation) is also (d, d + 2)-constrained. If S_{1}, …, S_{n} are subsets of S, each consisting of two consecutive integers, the smaller of which is even, then S_{1} × ⋯ × S_{n} is a bi-subcube of S^{n}. If a permutation n-cube g equals 1 exactly once per row in a bi-subcube, then the restriction of g to the bi-subcube is said to be a permutation bi-subcube.

A binary n-cube h is a reversal of a permutation n-cube g if h equals 1 − g on the members of a (possibly empty) subset of all the bi-subcubes in S^{n}, on each of which g is a permutation bi-subcube, and h equals g elsewhere. A reversal h of any permutation cube g is also a permutation cube, and g and h together form a (d, d + 2)-compatible set. More generally, any collection of reversals of a given permutation n-cube forms a (d, d + 2)-compatible set (see Lemma 2). In Propositions 1 and 2, we construct a (d, d + 2)-compatible family of reversals of a certain permutation n-cube, and then obtain a lower bound on the (d, d + 2)-capacity from the cardinality of the family.

A mapping f̄ : S^{n} → S is a latin n-cube if on every row of S^{n}, f̄ is a permutation of S. This definition is a generalization of a latin square, although alternate definitions have been given in [3]. For any permutation n-cube g, any l < n, and any c_{j} ∈ S (for j = 1, …, l − 1, l + 1, …, n − 1), the relation x ↦ y determined by g(c_{1}, …, c_{l−1}, x, c_{l+1}, …, c_{n−1}, y) = 1 is a permutation. This leads us to define a correspondence between permutation n-cubes and latin (n − 1)-cubes as follows. Let g : S^{n} → {0, 1} be a permutation n-cube and for each (x_{1}, x_{2}, …, x_{n−1}) ∈ S^{n−1}, let y(x_{1}, …, x_{n−1}) be the unique element of S such that g(x_{1}, x_{2}, …, x_{n−1}, y(x_{1}, …, x_{n−1})) = 1. Then the mapping ḡ : S^{n−1} → S defined by ḡ(x_{1}, x_{2}, …, x_{n−1}) = y(x_{1}, …, x_{n−1}) is a latin (n − 1)-cube, and the correspondence g ↦ ḡ is bijective (see Lemma 2). The bar notation will be exclusively used for latin cubes. For any integers a ≥ 0 and b > 0, we use the notation “a mod b” to mean the unique integer a − ⌊\frac{a}{b}⌋b.

Lemma 2 Let ē_{n} : S^{n} → S be a sequence of mappings defined recursively for n ≥ 3 by

ē_{n}(x_{1}, …, x_{n}) = ē_{2}(ē_{n−1}(x_{1}, …, x_{n−1}), x_{n})  (1)

where ē_{2} is a latin square. Then ē_{n} is a latin n-cube for all n ≥ 2, and the set of all reversals of the corresponding permutation (n + 1)-cube e_{n} is (d, d + 2)-compatible.

Proof. Use induction on n. Assume ē_{2}, …, ē_{n−1} are latin cubes (for n ≥ 3) and fix all but one of the arguments x_{1}, …, x_{n} of ē_{n}. If x_{1}, …, x_{n−1} are fixed then ē_{n} is a permutation of S since fixing the first argument of ē_{2} yields a permutation of S. Likewise, if x_{n} and all but one of x_{1}, …, x_{n−1} are fixed, then by the induction hypothesis ē_{n−1}(x_{1}, …, x_{n−1}) is a permutation of S and ē_{2} is a permutation of S since its second argument x_{n} is fixed. Thus ē_{n} is a latin n-cube.

Let h be a binary (n + 1)-cube h : S^{n+1} → {0, 1} satisfying

h(x_{1}, …, x_{n+1}) = \{ \begin{matrix}1 & if x_{n+1} = ē_{n}(x_{1}, …, x_{n}) \\ 0 & otherwise. \end{matrix}

Then h is a permutation (n + 1)-cube since ē_{n} is a latin n-cube, and h̄ = ē_{n} from the definition of the bar notation. This shows that there exists a unique permutation (n + 1)-cube h (i.e. e_{n}) corresponding to the latin n-cube ē_{n}.

The permutation (n + 1)-cube e_{n} has rows of length d + 2, each containing a single one. For any collection of bi-subcubes, on each of which e_{n} is a permutation bi-subcube, any row of S^{n+1} can intersect at most one of these bi-subcubes. This implies that any facewise concatenation of any two reversals of e_{n} will only have pairs of ones at distances d, d + 1, or d + 2 apart, and thus any set of reversals of e_{n} is (d, d + 2)-compatible.

□

Proposition 1 For every n ≥ 2 and every even d ≥ 0,

C_{d,d+2}^{(n)} ≥ \frac{1}{2^{n−1}(d + 2)}.

Proof. Define a mapping ē_{2} : S^{2} → S such that

ē_{2}(x_{1}, x_{2}) = \{ \begin{matrix}(x_{1} + x_{2} − 2) mod (d + 2) & if x_{1} and x_{2} are odd \\ (x_{1} + x_{2}) mod (d + 2) & otherwise \end{matrix}  (2)

as in Figure 1. The mapping ē_{2} is a latin square since ē_{2} is a permutation of the set S when either the first or second component is held fixed. For each n ≥ 3, use (1) to recursively define the latin n-cube ē_{n} : S^{n} → S.

For each n ≥ 2, let x_{1}, …, x_{n} be any set of even integers from S. We claim that for any y_{1}, …, y_{n} ∈ {0, 1},

ē_{n}(x_{1} + y_{1}, …, x_{n} + y_{n}) = \{ \begin{matrix}(x_{1} + ⋯ + x_{n}) mod (d + 2) & if ∑_{i=1}^{n} y_{i} is even \\ (1 + x_{1} + ⋯ + x_{n}) mod (d + 2) & if ∑_{i=1}^{n} y_{i} is odd. \end{matrix}

To prove this claim, use induction on n. It is easy to see from (2) that the claim is true for n = 2. By (1) and the induction hypothesis,

ē_{n}(x_{1} + y_{1}, …, x_{n} + y_{n}) =
\{ \begin{matrix}ē_{2}((x_{1} + ⋯ + x_{n−1}) mod (d + 2), x_{n} + y_{n}) & if ∑_{i=1}^{n−1} y_{i} is even \\ ē_{2}((1 + x_{1} + ⋯ + x_{n−1}) mod (d + 2), x_{n} + y_{n}) & if ∑_{i=1}^{n−1} y_{i} is odd. \end{matrix}

Equivalently, when ∑_{i=1}^{n} y_{i} is even

ē_{n}(x_{1} + y_{1}, …, x_{n} + y_{n}) = \{ \begin{matrix}ē_{2}((x_{1} + ⋯ + x_{n−1}) mod (d + 2), & x_{n}) & if y_{n} = 0 \\ ē_{2}((1 + x_{1} + ⋯ + x_{n−1}) mod (d + 2), & x_{n} + 1) & if y_{n} = 1 \end{matrix}
= (x_{1} + ⋯ + x_{n}) mod (d + 2),

and when ∑_{i=1}^{n} y_{i} is odd

ē_{n}(x_{1} + y_{1}, …, x_{n} + y_{n}) = \{ \begin{matrix}ē_{2}((x_{1} + ⋯ + x_{n−1}) mod (d + 2), & x_{n} + 1) & if y_{n} = 1 \\ ē_{2}((1 + x_{1} + ⋯ + x_{n−1}) mod (d + 2), & x_{n}) & if y_{n} = 0 \end{matrix}
= (1 + x_{1} + ⋯ + x_{n}) mod (d + 2),

thus proving the claim.

The claim just proved implies that the corresponding permutation (n + 1)-cube e_{n} satisfies

e_{n}(x_{1} + y_{1}, …, x_{n+1} + y_{n+1}) = \{ \begin{matrix}1 & if ∑_{i=1}^{n+1} y_{i} is even \\ 0 & if ∑_{i=1}^{n+1} y_{i} is odd \end{matrix}

for any even integers x_{1}, …, x_{n+1} ∈ S such that x_{n+1} = ∑_{i=1}^{n} x_{i} mod (d + 2), and for any y_{1}, …, y_{n+1} ∈ {0, 1}. Thus the restriction of e_{n} to each bi-subcube {(x_{1} + y_{1}, …, x_{n+1} + y_{n+1}) : y_{1}, …, y_{n+1} ∈ {0, 1}} is a permutation bi-subcube. Then the cardinality of the set of all reversals of e_{n} is 2^{( \frac{d+2}{2} )^{n}}, and Lemma 2 gives the lower bound

C_{d,d+2}^{(n)} ≥ \frac{log_{2} 2^{(^{\frac{d+2}{2}})}^{n−1}}{(d + 2)^{n}} = \frac{1}{2^{n−1}(d + 2)}.

□

Proposition 2 For every n ≥ 2 and every odd d ≥ 3,

C_{d,d+2}^{(n)} ≥ \frac{1}{(d + 2)^{n}} \binom{n − 1 + \frac{d−3}{2}}{n − 1}.

Proof.

Define a mapping ē_{2} : S^{2} → S such that

ē_{2}(x_{1}, x_{2}) = \{ \begin{matrix}x_{1} + x_{2} − 2 & if x_{1} and x_{2} are odd \\ x_{1} + x_{2} & otherwise \end{matrix}  (3)

for 2⌊\frac{x_{1}}{2} ⌋ + 2⌊\frac{x_{2}}{2} ⌋ ≤ d − 3. The values of ē_{2} for 2⌊\frac{x_{1}}{2} ⌋ + 2⌊\frac{x_{2}}{2} ⌋ > d − 3 (i.e. below the bold 2-step staircase line in Figures 2 and 3) are defined as follows. The points on the diagonal line above the main diagonal have value d, as does the bottom right corner of the square. Thus, d appears once in each row and in each column in the square. The portion of the next higher diagonal that lies below the 2-step staircase line has value d − 1. The area below and including the main diagonal of the square, except the bottom row and the rightmost column, is partitioned into diagonal strips of width 4. Each diagonal strip is formed by repeating the staircase pattern shape of

.

The bottom row is formed by repeating the pattern

and the rightmost column is formed by repeating the pattern

.

(For the case d ≡ 1 mod 4 the bottom-rightmost diagonal strip is truncated at width 3, and the above patterns are cut off accordingly, as illustrated in Figure 2.) Within any given diagonal strip, all labels containing a particular symbol represent the same integer. In particular, in the jth diagonal, (for j = 1, 2, …, ⌊\frac{d}{4}⌋ + 1), the square labels + , ^{}, ^{}, , and – represent 4j − 2, 4j − 3, 4j − 4, 4j − 5, and 4j − 6 respectively (for j = 1, – and represent d − 1 and d + 1, respectively). For any i ∈ {0, 1, …, d − 2} it can be seen that the value i appears once in every row and column of the top left 2⌊\frac{i}{2}⌋ + 2 rows and columns, and the value i appears once in every row and column of the bottom right d − 2⌊\frac{i}{2}⌋ rows and columns. Also, the main diagonal of S^{2} contains only the value d + 1, and the value d − 1 appears in the rightmost column at (x_{1}, x_{2}) = (1, d+2), in the bottom row at (x_{1}, x_{2}) = (d+2, 1), and in alternating positions on the diagonals that lie two above and two below the main diagonal of S^{2}. The value d−1 appears in the rightmost column at (x_{1}, x_{2}) = (1, d+2) and in the bottom row at (x_{1}, x_{2}) = (d + 2, 1), and these points do not lie on the diagonals two below nor two above the main diagonal. Consequently, every number 0, 1, …, d + 1 appears exactly once in each row and in each column in the original (d + 2) × (d + 2) square S^{2}, showing that ē_{2} is a latin square.

Using (1) and the definition of ē_{2} just given, recursively define for each integer n ≥ 3, the latin n-cube ē_{n} : S^{n} → S. For any n ≥ 2, if x_{1}, …, x_{n} are even integers from S such that ∑_{i=1}^{n} x_{i} ≤ d − 3, then for any y_{1}, …, y_{n} ∈ {0, 1},

ē_{n}(x_{1} + y_{1}, …, x_{n} + y_{n}) = \{ \begin{matrix}x_{1} + ⋯ + x_{n} & if ∑_{i=1}^{n} y_{i} is even \\ 1 + x_{1} + ⋯ + x_{n} & if ∑_{i=1}^{n} y_{i} is odd \end{matrix}

from the same proof as in Proposition 1, but with the added constraint ∑_{i=1}^{n} x_{i} ≤ d−3.

As in Proposition 1, the set of reversals of the permutation (n + 1)-cube e_{n} is (d, d + 2)-compatible. There are \binom{n+ \frac{d−3}{2}}{n} permutation bi-subcubes in this case and the volume of the (n + 1)-cube S^{n+1} (i.e. the domain of e_{n}) is (d + 2)^{n+1}. Hence

C_{d,d+2}^{(n)} ≥ \frac{1}{(d + 2)^{n}} \binom{n − 1 + \frac{d−3}{2}}{n − 1}.

□

3 Proof of Theorem 2

Proof. Lemma 1(e) gives lim_{n→∞} C_{d,2d+1}^{(n)} > 0 for every d ≥ 0, and thus lim_{n→∞} C_{d,k}^{(n)} > 0 for every k ≥ 2d + 1 by Lemma 1(a). Lemma 3 below implies that C_{d,k}^{(n)} ≤

(\frac{k−d}{k−d+1})^{n−1} C_{d,k}^{(1)} whenever d < k ≤ 2d, and hence lim_{n→∞} C_{d,k}^{(n)} = 0. This together with Lemma 1(d) completes the proof of Theorem 2.

□

Lemma 3 If n ≥ 2 and 1 ≤ d < k ≤ 2d then

C_{d,k}^{(n)} ≤ \frac{k − d}{k − d + 1}C_{d,k}^{(n−1)}.

Proof. Let l and m be positive integers and let V = {1, 2, …, m}. Define the following n-dimensional hyper-rectangles (for j = 1, 2, …, l):

T = {(x_{1}, …, x_{n−1}, x_{n}) : x_{1}, …, x_{n−1} ∈ V, −d ≤ x_{n} < (k − d + 1)l}
U_{0} = {(x_{1}, …, x_{n−1}, x_{n}) : x_{1}, …, x_{n−1} ∈ V, −d ≤ x_{n} < 0}
U_{j} = {(x_{1}, …, x_{n−1}, x_{n}) : x_{1}, …, x_{n−1} ∈ V, (k − d + 1)(j − 1) < x_{n} < (k − d + 1)j}

and let U = ⋃_{j=0}^{l} U_{j}. Note that there is a gap of width one between consecutive sets U_{j} and U_{j+1} (To help visualize the proof, the case of n = 3 is illustrated in Figure 4). A binary mapping on U is said to be (d, k)-constrained if it induces a (d, k)-constrained pattern on each U_{j}. Let N_{T} and N_{U_{j}} be the numbers of distinct (d, k)-constrained mappings on T and U_{j} (for j = 0, 1, …, l), respectively. We show that N_{T} ≤ ∏_{j=0}^{l} N_{U_{j}}.

To this end, it suffices to exhibit an injection from the set of all (d, k)-constrained mappings on T to those on U. Thus we demonstrate that every (d, k)-constrained mapping on T is completely determined by its restriction to U.

Assume the contrary. Then there exist two (d, k)-constrained mappings f_{0} : T → {0, 1} and f_{1} : T → {0, 1} that agree on U but differ on T. Let (c_{1}, …, c_{n−1}, c_{n}) ∈ T be such that f_{0}(c_{1}, …, c_{n−1}, c_{n}) ≠ f_{1}(c_{1}, …, c_{n−1}, c_{n}).

Since f_{0} and f_{1} agree on U, c_{n} must be a multiple of k−d+1. Let J be the smallest nonnegative integer j such that f_{0}(c_{1}, …, c_{n−1}, (k − d + 1)j) ≠ f_{1}(c_{1}, …, c_{n−1}, (k − d + 1)j). Without loss of generality assume f_{0}(c_{1}, …, c_{n−1}, (k − d + 1)J) = 0 and f_{1}(c_{1}, …, c_{n−1}, (k−d+1)J) = 1. Note that (k−d+1)(J +1)−1 ≤ (k−d+1)J +d since k ≤ 2d. Also, since f_{1}(c_{1}, …, c_{n−1}, (k − d + 1)J) = 1, f_{1} must equal zero for at least d consecutive positions next to this point. Thus f_{1}(c_{1}, …, c_{n−1}, x) = 0 for all x in the range (k −d+1)J −d ≤ x < (k −d+1)(J +1), excluding x = (k −d+1)J. Therefore f_{0}(c_{1}, …, c_{n−1}, x) = 0 for this same set of x’s, since either (c_{1}, …, c_{n−1}, x) is in U or else because of the choice of J. But by assumption f_{0}(c_{1}, …, c_{n−1}, (k − d + 1)J) = 0, so a string of k + 1 zeros in a row occurs for f_{0} (from x = (k − d + 1)J − d to x = (k − d + 1)(J + 1) − 1) contradicting the (d, k) constraint. This proves that every (d, k)-constrained mapping on T is uniquely determined by its restriction to U. This establishes that N_{T} ≤ ∏_{j=0}^{l} N_{U_{j}}.

Now, let M denote the number of distinct (d, k)-constrained mappings on an (n−1)-dimensional hypercube of side length m. Clearly, ∏_{j=0}^{l} N_{U_{j}} ≤ M^{(k−d)l+d}, since N_{U_{0}} ≤ M^{d} and N_{U_{j}} ≤ M^{k−d} for j = 1, 2, …, l. Thus,

C_{d,k}^{(n)} = lim_{l,m→∞} \frac{log_{2} N_{T}}{((k − d + 1)l + d)m^{n−1}} ≤ lim_{l,m→∞} \frac{log_{2} ∏_{j=0}^{l} N_{U_{j}}}{((k − d + 1)l + d)m^{n−1}}

≤ lim_{l,m→∞} \frac{log_{2} M^{(k−d)l+d}}{((k − d + 1)l + d)m^{n−1}}

= lim_{l→∞} \frac{(k − d)l + d}{(k − d + 1)l + d} · lim_{m→∞} \frac{log_{2} M}{m^{n−1}} = \frac{k − d}{k − d + 1}C_{d,k}^{(n−1)}.
□

4 Comments

For d = 1, Lemma 1(e) implies that C_{1,3}^{(n)} ≥ 1/4 for n ≥ 3. A more complicated proof can show that C_{1,3}^{(n)} ≥ C_{0,1}^{(n)}/2 for all n ≥ 2 (note that C_{0,1}^{(n)} ≥ 1/2 by Lemma 1(e)). For odd d ≥ 3 Proposition 2 gives C_{d,d+2}^{(2)} ≥ \frac{d−1}{2(d+2)^{2}} whereas a slightly better lower

bound C_{d,d+2}^{(2)} ≥ \frac{d+1}{2(d+2)^{2}} was given in [5, Theorem 2]. Propositions 1 and 2 establish

that C_{d,d+2}^{(n)} > 0. Alternatively it is possible to prove C_{d,d+2}^{(n)} > 0 in a simpler manner, but with weaker lower bounds on C_{d,d+2}^{(n)} than those given in these propositions.

References

[1] J. J. Ashley and P. H. Siegel, “A Note on the Shannon Capacity of Run-Length-Limited Codes,” IEEE Trans. Information Theory, vol. 33, no. 4, July 1987, pp. 601–605.

[2] N. J. Calkin and H. S. Wilf, “The Number of Independent Sets in a Grid Graph,” SIAM J. on Discrete Mathematics, vol. 11, February 1998, pp. 54–60.

[3] J. Dénes and A. D. Keedwell, Latin Squares: New Developments in the Theory and Applications, Elsvier, Amsterdam, 1991.

[4] K. A. Immink, P. H. Siegel, and J. K. Wolf, “Codes for Digital Recorders,” IEEE Trans. Information Theory, vol. 44, pp. 2260–2299, October 1998.

[5] A. Kato and K. Zeger, “On the Capacity of Two-Dimensional Run Length Constrained Channels,” IEEE Trans. Information Theory. vol. 45, no. 4, July 1999, pp.1527–1540.

[6] D. Lind and B. H. Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge University Press, New York, 1995.

[7] Zs. Nagy and K. Zeger, “Capacity Bounds for the 3-Dimensional (0, 1) Runlength Limited Channel,” preprint. the electronic journal of combinatorics 6 (1999), #R33 13

Figure 1: Latin square ē_{2} for d = 16 (even d). the electronic journal of combinatorics 6 (1999), #R33 14

Figure 2: Latin square ē_{2} for d = 17 (d ≡ 1 mod 4). the electronic journal of combinatorics 6 (1999), #R33 15

Figure 3: Latin square ē_{2} for d = 19 (d ≡ 3 mod 4). the electronic journal of combinatorics 6 (1999), #R33 16 Figure 4: Illustration of the sets T and U_{j} for three dimensions in the proof of Lemma