Maximum insertion rate and capacity of multidimensional constraints

The maximum insertion rate of a one-dimensional constrained system over a finite alphabet is defined to be the maximum density of positions that can be freely, and independently, filled in with arbitrary symbols of the alphabet and still satisfy the constraint. In this paper, this concept is extended to higher dimensional constraints, that is, to constraints on D-dimensional arrays defined by imposing a 1-dimensional constraint in each dimension. We give a simple upper bound on the D-dimensional maximum insertion rate in terms of the individual 1-dimensional maximum insertion rate. For D-dimensional constraints defined by imposing the same 1-dimensional constraint in each dimension, we show that the D-dimensional maximum insertion rate is the same as the 1-dimensional maximum insertion rate. In this case (called the isotropic or, sometimes, symmetric case), we show that the maximum insertion rate is a lower bound on the limiting D-dimensional capacity as D tends to infinity. Finally, we show that in the case of a finite memory constraint, when the maximum insertion rate is zero, the D-dimensional capacity decays exponentially fast to zero.