1

On Independence And Capacity of
Multidimensional Semiconstrained Systems
Ohad Elishco, Student Member, IEEE, Tom Meyerovitch, Moshe Schwartz, Senior Member, IEEE

arXiv:1709.05105v1 [math.DS] 15 Sep 2017

Abstract
We find a new formula for the limit of the capacity of certain sequences of multidimensional semiconstrained systems as the
dimension tends to infinity. We do so by generalizing the notion of independence entropy, originally studied in the context of
constrained systems, to the study of semiconstrained systems. Using the independence entropy, we obtain new lower bounds on
the capacity of multidimensional semiconstrained systems in general, and d-dimensional axial-product systems in particular. In
the case of the latter, we prove our bound is asymptotically tight, giving the exact limiting capacity in terms of the independence
entropy. We show the new bound improves upon the best-known bound in a case study of (0, k, p)-RLL.
Index Terms
Semiconstrained systems, capacity, independence entropy, bounds

I. I NTRODUCTION

E

RROR-correcting codes and constrained codes may be considered as two extreme ways of coping with a noisy channel.
The former are usually data independent, and assume errors are a statistical phenomenon, reducing data-transmission rate
to protect against such errors. Constrained codes, however, assume certain patterns in the data stream are responsible for the
occurrence of errors. Thus, constrained codes eliminate all undesirable patterns, at the cost of reduced data-transmission rate.
Recently in [9], [10], semiconstrained systems (SCSs) were suggested as a generalization to constrained systems (which we
emphasize by calling fully constrained systems). In SCSs we do not eliminate the undesirable patterns entirely but rather we
allow them to appear with a restriction on their frequency. To illustrate, consider a binary channel in which the appearance of
k-consecutive 1’s is forbidden. The set of allowed words is the well known inverted (0, k)-RLL. However, if k-consecutive 1’s
are not forbidden entirely, but instead are allowed to appear in at most a fraction p of places, then the set of allowed words
forms a SCS called the (0, k, p)-RLL system. Informally, a SCS is defined by a set Γ of probability measures over k-tuples.
The allowed words in the SCS are those in which the empirical distribution of k-tuples belongs to Γ. This may be viewed
as a generalization of fully constrained systems since taking Γ to be a subset with a 0-frequency restriction on some k-tuples
yields a fully constrained system.
SCSs not only generalize fully constrained systems, but also subsume a range of other settings, which were mainly dealt with
in an ad-hoc fashion. Among these we can find DC-free RLL coding [17], constant-weight ICI coding for flash memories [5],
[6], [15], [27], coding to mitigate the appearance of ghost pulses in optical communication [30], [31], and the more general,
channel with cost constraints [13], [16].
In the one-dimensional case, the capacity of a SCS is given by a relatively explicit expression as the solution to a certain
optimization problem on a finite dimensional space, e.g., [22]. A probabilistic encoder for SCSs was constructed in [10],
and constant-bit-rate to constant-bit-rate encoders are possible by approximating a SCS with a fully constrained system, as
described in [9].
A natural extension, and the goal of this work, is to study multidimensional SCSs. This is an extremely challenging problem,
considering the fact that even for fully constrained systems in complete generality it is provably impossible to find an exact
solution. The capacity of multidimensional fully constrained systems is known exactly only in a handful of cases [1], [18],
[20], [28]. In the absence of a general method for computing the capacity, various bounds and approximations were studied,
e.g., [3], [11], [12], [14], [24], [25], [29], [32]–[34]. It should be emphasized that apart from its independent intellectual merit,
studying multidimensional systems is of practical importance since most storage media are two- or three-dimensional, including
magnetic recording devices such as hard drives, optical recording devices such as CDs and DVDs, and flash memories.
The approach we take in this work is bounding the capacity by studying the independence entropy of SCSs, thus extending
the works [19], [23]. The independence entropy appeared in previous works on d-dimensional shifts of finite type. Although
this notion was first defined in [19], the idea stemmed from tradeoff functions studied in [26]. It was defined in a combinatorial
The material in this paper was presented in part at the IEEE International Symposium on Information Theory (ISIT 2017), Aachen, Germany, June 2017.
Ohad Elishco is with the Department of Electrical and Computer Engineering, Ben-Gurion University of the Negev, Beer Sheva 8410501, Israel (e-mail:
ohadeli@post.bgu.ac.il).
Tom Meyerovitch is with the Department of Mathematics, Ben-Gurion University of the Negev, Beer Sheva 8410501, Israel (e-mail: mtom@math.bgu.ac.il).
Moshe Schwartz is with the Department of Electrical and Computer Engineering, Ben-Gurion University of the Negev, Beer Sheva 8410501, Israel (e-mail:
schwartz@ee.bgu.ac.il).
This work was supported in part by the People Programme (Marie Curie Actions) of the European Union’s Seventh Framework Programme (FP7/2007-2013)
under REA grant agreement no. 333598 and by the Israel Science Foundation (grant no. 626/14).

2

fashion, where in this work we redefine it in a probabilistic fashion. We show that the two definitions are equal for the special
case of fully constrained systems.
The motivation for the use of independence entropy is the fact that it is more easily computable, since we only need to
consider independent probability measures which satisfy the constraints. We also focus on the class of d-dimensional axialproduct constraints, which form a significant proportion of multidimensional fully constrained systems studied thus far. For
this class, our approach has an additional major advantage in that instead of calculating the independence entropy for a ddimensional axial product SCS, we may calculate it directly from the one-dimensional system. This dimensionality reduction
offers further simplification of the calculations.
There are new features and difficulties that come up when adapting the results from fully constrained systems. In an abstract
sense, a very useful property of fully constrained systems is the following: If a measure µ is contained in some fully constrained
system, and µ is a convex combination of measures, then each of them is contained in the same fully constrained system. This
property does not hold for general semiconstrained systems. This is manifested for instance in the fact that any subword of
an admissible word in a fully constrained system is also admissible, leading to sub-additivity of the sequence of the amount
of admissible words. This, in turn, allows the use of Fekete’s Lemma.
The main contributions of this paper are a formulation of the independence entropy for SCSs, and its study in relation to
the capacity of SCSs. As a result, we obtain a new lower bound on the capacity of multidimensional SCSs, generalizing the
results of [19], [23], and in an example test case, improving upon the best known bounds on the capacity of multidimensional
(0, 1, p)-RLL SCSs given in [10].
In this work we also establish an equality of the limiting capacity and independence entropy for the d-axial-product SCSs.
As the independence entropy is a lower bound on the entropy of a given SCS in every dimension, the capacity approaches the
independence entropy as the dimension grows.
This paper is organized as follows. In Section II we describe the notation and give the required definitions used throughout
the paper. In Section III we define the independence entropy and provide results characterizing the independence entropy. In
Section IV we show that the capacity is lower bounded by the independence entropy. In Section V we show that the limiting
capacity of the d-axial-product SCS is equal to the independence entropy. We conclude in Section VI by describing a short
case study, and comparing it with previous results. The appendices provide proofs that the generalized notions we define in
this paper indeed contain fully constrained systems as a special case, thus providing a generalization for them.
II. P RELIMINARIES
Let N denote the set of natural numbers. We use ei to denote the unit vector of direction i, 0 to denote the all-zero vector,
and 1 to the denote the all-one vector, where in all cases, the dimension of the vectors is implied by the context. For n ∈ N
we define
[n] , {0, 1, . . . , n − 1} .
We shall often use [n]ei to denote the set {0 · ei , 1 · ei , . . . , (n − 1) · ei }. For d, n ∈ N, denote by Fnd the d-dimensional cube
of length n, i.e., the set Fnd , [n]d . Obviously | Fnd | = nd . Additionally, for (n0 , . . . , nd−1 ) ∈ Nd we conveniently denote

[(n0 , . . . , nd−1 )] , [n0 ] × [n1 ] × · · · × [nd−1 ].
Throughout the paper, Σ will be used to denote a finite alphabet. A word (or block) w of length n is a sequence of n
letters from Σ, denoted w = a0 a1 . . . an−1 , with ai ∈ Σ. We let |w| denote the length of the word w. We can also consider
d
infinite-sized words by mapping letters from Σ to positions on the integer grid Zd . Such a word will be denoted by x ∈ ΣZ ,
and the letter in the v ∈ Zd position will be denoted by xv (sometimes referred to as the restriction of x to v). More generally,
given any subset of the integer grid, S ⊆ Zd , a word x ∈ ΣS is a mapping of letters from Σ to positions indexed by elements
of S.
We require a notation for sets of probability measures and their marginals. For a set W we denote by P (W ) the set of all
probability measures over W.
Definition 1. Let ( X, B) be a measurable space. For every µ, ν ∈ P ( X ), the total variation distance is defined as

kµ − νk TV , sup |µ(W ) − ν(W )| .
W ∈B

2
Given a compact topological space X, the space P ( X ) is itself a compact topological space with respect to the weak ∗topology. In particular, when X is a finite set P
with the discrete topology, the topology on P ( X ) is given by the total variation
distance which also satisfies kµ − νk TV = 21 x∈X |µ( x ) − ν( x )|.
Given a continuous map f : X → Y between topological spaces, and µ ∈ P ( X ), let f (µ) ∈ P (Y ) be given by
f (µ)(W ) , µ( f −1 (W )), W ⊆ Y.

3

Definition 2. For d ∈ N, S ⊆ S̃ ⊆ Zd , and x ∈ ΣS̃ , let xS denote the restriction of x to the coordinates in S. Let πSS̃ : ΣS̃ → ΣS
denote the restriction map given by
πSS̃ ( x ) , xS .
2

When S̃ is clear from the context, we shall write πS instead of πSS̃ .

While having the notation πS ( x ) in addition to the equivalent notation xS , seems superfluous, we shall require the former to
simplify our presentation. As a consequence of the previous definition, for µ ∈ P (ΣS̃ ) and S ⊆ S̃, we note that πS (µ) ∈ P (ΣS )
is the S-marginal of µ.
Definition 3. For d ∈ N, v ∈ Zd , let σv : ΣZ → ΣZ be the shift by the vector v, given by
d

d

(σv ( x ))u , xu+v , u ∈ Zd , x ∈ ΣZ .
d

We denote by Psi (ΣZ ) the space of shift-invariant probability measures on ΣZ , namely,
n
o
d
d
Psi (ΣZ ) , µ ∈ P (ΣZ ) : σv (µ) = µ for all v ∈ Zd .
d

d

d

For k ∈ N we say that µ ∈ P (Σ Fk ) is shift invariant if it is the projection of some shift-invariant measure on ΣZ , i.e., if there
d
d
d
exists µ̃ ∈ Psi (ΣZ ) such that µ = π Fd µ̃. We denote by Psi (Σ Fk ) the space of shift-invariant probability measures on Σ Fk ,
k
namely,
d

d

d

Psi (Σ Fk ) , π Fd (Psi (ΣZ )) ⊆ P (Σ Fk ).
d

k

2
Fk1

In the one-dimensional case, d = 1, it is rather easy to check whether a given probability measure µ ∈ P (Σ ) is shift
1
invariant. Indeed, µ ∈ Psi (Σ Fk ) if and only if it satisfies the following finite system of linear equations,
X
X
µ( a, a1 , . . . , ak−1 ) =
µ ( a 1 , . . . , a k −1 , a ),
a∈Σ

a∈Σ

for all a1 , . . . , ak−1 ∈ Σ.
When d > 2 the space of finite marginals of shift invariant measures becomes much more complicated. It is still not difficult
d
to formulate an analogous system of linear equations that are satisfied for every µ ∈ Psi (Σ Fk ). However, these linear conditions
d
are no longer sufficient conditions for shift invariance. In fact, the problem of checking whether a given µ ∈ P (Σ Fk ) is shift
invariant, is undecidable (assuming some computable representation of µ). See for instance [4], and references within, for a
related discussion.
We are interested in defining empirical distributions of words. To that end, we give some more general definitions that
d
d
we then specialize to our specific needs. Given x ∈ ΣZ , the delta measure at x, denoted by δx ∈ P (ΣZ ), is defined by
d
δx ({ x }) = 1. Additionally, given n ∈ N, the empirical measure associated with x and n, denoted frx,n ∈ P (ΣZ ), is given
by
1 X
frx,n , d
δσv ( x) .
n
d
v∈ Fn

For S ⊆ Zd we can take the S-marginal, and define frSx,n ∈ P (ΣS ) by
frSx,n , πS (frx,n ).
Any word w ∈ Σ Fn may be extended periodically to the entire integer grid ŵ ∈ ΣZ by defining
d

d

ŵv , wv mod n
for all v ∈ Zd , and where the modulo is taken entry-wise. The empirical distribution we shall be requiring may now be
defined.
d

Definition 4. Let d, n ∈ N, w ∈ Σ Fn , and S ⊆ Zd . The empirical distribution of w with respect to S, denoted frSw , is defined by
frSw , frSŵ,n .
2

4

Combinatorially speaking, the empirical distribution frSw is obtained by cyclically scanning w with an S-shaped window and
recording the frequency of the S-tuples in w. Thus, for instance, given a word w = w0 . . . wn−1 ∈ Σn , wi ∈ Σ, and a ∈ Σk
we have
|w|−1
1 X
[k]
frw ( a) =
1 a ( wi . . . wi + k −1 )
|w|
i =0

where all coordinate indices are taken modulo |w|, and 1a : Σk → {0, 1} is the indicator function of the singleton { a}.
1

1 | = 10 and
Example 5. Let Σ = {0, 1} and let w = 0010111001 ∈ Σ F10 . We have that | F10
9

[3]

frw (110) =
[2]

frw (10) =

1 X
1
,
1110 (wi wi+1 wi+2 ) =
10
10
1
10

i =0
9
X

110 (wi wi+1 ) =

i =0

3
10
2

Example 6. Let Σ = {0, 1} and consider

0
0
w=
1
1
F2

Then frw2 ( a) =

2
16

1
0
0
0

1
1
0
1


1
1
 ∈ Σ F42 ,
1
0

a=

ï
0
1

ò
2
1
∈ Σ F2 .
0

since, of the sixteen 2 × 2 windows, exactly two contain a, shown in bold in the following:




0 1 1 1
0 1 1 1
0 0 1 1
0 0 1 1




1 0 0 1 ,
1 0 0 1 .
1 0 1 0
1 0 1 0
2

Lemma 7. Suppose d, n ∈ N, w ∈

d
Σ Fn ,

and S ⊆ S̃ ⊆

Zd .

Then

πSS̃ (frS̃w ) = frSw .
Proof: Let us denote µ , frŵ,n ∈ P (ΣZ ). By definition, for the right-hand side of the claim, for every W ⊆ ΣS ,


d
d
frSw (W ) = πSZ (µ)(W ) = µ (πSZ )−1 (W ) .
d

Similarly, for the left-hand side,
 d


Ä
ä
Ä
ä
d
d
πSS̃ (frS̃w )(W ) = πSS̃ πS̃Z (µ) (W ) = πS̃Z (µ) (πSS̃ )−1 (W ) = µ (πS̃Z )−1 (πSS̃ )−1 (W ) .
But clearly for all A ⊆ ΣS ,

Ä
ä
d
d
(πSZ )−1 (W ) = (πS̃Z )−1 (πSS̃ )−1 (W ) .

Lemma 7 implies that the empirical frequency of S-tuples in w can be calculated by first calculating the empirical frequency
of S̃-tuples, and then taking the S-marginal.
Example 8. Let Σ = {0, 1} and consider


0
0
w=
1
1

1
0
0
0


1
1
 ∈ Σ F42 .
1
0

1
1
0
1

Take S = [1]2 = {(0, 0)} and S̃ = [(2, 1)] = {(0, 0), (1, 0)}. Then
2
,
16
5
frS̃w (10) =
,
16

frS̃w (00) =

5
,
16
4
frS̃w (11) =
.
16
frS̃w (01) =

5

Moreover, we have that
7
,
16

frSw (0) =

frSw (1) =

9
.
16

We can verify now that
Ä
ä
7
πSS̃ (frS̃w )(0) = frS̃w (πSS̃ )−1 (0) = frS̃w ({00, 01}) =
= frSw (0).
16
2
We are now ready to define multidimensional semiconstrained systems.
Definition 9. For d ∈ N, a Zd -semiconstrained system (SCS) is a set Γ ⊆ P (ΣS ) for some finite set S ⊆ Zd . For n ∈ N, the
admissible n-blocks of Γ are
n
o
d
Bn (Γ) , w ∈ Σ Fn : frSw ∈ Γ .
2
Zd -SCSs,

Since all SCSs we study in this paper are
we shall abbreviate and call them just SCSs, where the dimension, d,
will be clear from the context.
Note that SCSs generalize d-dimensional fully constrained systems. Recall that fully constrained systems are defined by a
d
d
set of “forbidden patterns”, A ⊆ Σ Fk , such that a word w ∈ ΣZ is admissible if and only if none of the elements of A
appear as an Fkd -tuple of w. Thus, fully constrained systems correspond to subshifts of finite type in symbolic dynamics. In
our notation, we therefore have the following.
d

d

Definition 10. For d, k ∈ N, we say that Γ ⊆ P (Σ Fk ) is fully constrained if there exists some L ⊆ Σ Fk such that
d

Γ = {µ ∈ P (Σ Fk ) : µ( L) = 1}.
2
Example 11. Let Σ = {0, 1}, take
L=Σ

F22

ßï
0
\
1

ò ï
0
0
,
1
1

ò ï
1
1
,
1
1

ò ï
0
1
,
1
1

ò ï
1
1
,
1
1

ò ï
0
1
,
0
1

1
0

ò™
,

and consider the fully constrained system, Γ, defined by
¶
©
2
Γ = µ ∈ P (Σ F2 ) : µ( L) = 1 .
Note that Bn (Γ) is the set of all n × n two-dimensional binary arrays such that none of the six patterns above appears within
a 2 × 2 window in them. It is simple to verify that in fact, no two horizontally adjacent 1’s may appear, and no two vertically
adjacent 1’s may appear, in any admissible word. Thus, the n × n arrays in Bn (Γ) are the admissible words of the (cyclical)
(1, ∞)-RLL fully constrained system.
2
An important figure of merit we associate with any set of words, and in particular, with SCSs, is the capacity, which we
now define.
Definition 12. Let d ∈ N, and let S ⊆ Zd be a finite subset. For any SCS, Γ ⊆ P (ΣS ), and for e > 0, let
ß
™
Be (Γ) , µ ∈ P (ΣS ) : inf kµ − νk TV 6 e .
ν∈Γ

The capacity of Γ is defined as,
cap(Γ) , lim lim sup
e →0+

n→∞

1
log2 (|Bn (Γ)|) .
nd
2

First, we mention that lime→0+ in the definition of the capacity exists due to monotonicity, since |Bn (Be (Γ))| is nonincreasing in e.
To avoid certain pathological scenarios, [9], [10] defined sets of weakly-admissible words and their capacity. We contend
that the capacity definition provided here is the proper multidimensional generalization of these definitions. Intuitively, the
capacity measures the exponential growth rate of the number of words that “almost” satisfy the semiconstraints given by Γ.
Additionally, it has the nice property that the capacity of a set Γ is equal to the capacity of the closure of Γ.
At first glance this definition of capacity may seem odd. A naive definition, which we call the internal capacity, might be
as follows.

6

Definition 13. Let d ∈ N, S ⊆ Zd finite, and Γ ⊆ P (ΣS ) be a SCS. The internal capacity of Γ is defined as
” (Γ) , lim sup
cap
n→∞

1
log2 (|Bn (Γ)|) .
nd
2

By definition we have
” (Be (Γ))
cap(Γ) = lim cap
e →0+

which means that
” (Γ) 6 cap(Γ).
cap

(1)

” (Γ) = cap(Γ). For instance, we have the following result for one-dimensional
We also observe that for some “nice” SCSs Γ, cap
SCSs.
Theorem 14. [9, Section 2] Let k ∈ N, and Γ ⊆ P (Σk ) be convex and equal to the closure of its relative interior in Psi (Σk ).
Then
” (Γ) = log2 |Σ| −
cap(Γ) = cap
inf
H (η |µ)
η ∈Γ∩Psi (Σk )

where H (·|·) is the relative entropy function, and µ is defined by µ(φa) ,

1
|Σ|

P

a0 ∈Σ

η (φa0 ) for all φ ∈ Σk−1 and a ∈ Σ.

Remark 15. Consider the (compact) space M = P (ΣS ) and let C ( M ) be the set of all closed (hence, compact) subsets of M.
” (Γ) is monotone, the set of Γs for which
Thus, C ( M ) is a compact topological space (under the Hausdorff metric). Since cap
” (Γ) 6= cap(Γ) is meager. In other words, if we consider cap
” (Be (Bδ (Γ))) as a function of e, f (e) , cap
” (Be (Γ)), then
cap
” (Bδ (Γ)) whenever f is continuous in δ. Since f is a monotone function, it is discontinuous on a countable
cap(Bδ (Γ)) = cap
” (Γ) an arbitrary small change in Γ will give an
number of places. In practice, it means that if for a specific Γ, cap(Γ) 6= cap
equality.
2
d

Remark 16. For a fully constrained system, Γ ⊆ P (Σ Fk ), non-emptyness of Bn (Γ) for all n > 0 is equivalent to the fact that the
subshift of finite type
n
o
w ∈ ΣZ : ∀v ∈ Zd , (σv (w)) Fd ∈ L ,
d

k

is not empty. Berger’s Theorem [2] implies that it is undecidable whether a subshift of finite type is empty given L. Because (under
reasonable assumptions on the representation) it is undecidable if a given multidimensional SCS is non-empty, it is difficult to
understand what a SCS really looks like.
2
At this point we pause to ponder the following: Note that the definition of empirical frequency is cyclic (in the sense that
coordinates are taken modulo n) while in traditional fully constrained systems it is not. This seems at odds with our claim
of SCSs generalizing fully constrained systems. The necessity of the modulo in the definition of SCSs stems from working
with the space of shift-invariant measures and their associated admissible words. Shift-invariant measures are defined over Zd ,
d
d
hence, it is necessary to complete a word w ∈ Σ Fn to a word from ΣZ . We choose to do this completion periodically using
the modulo notion, extending w to ŵ. This choice simplifies the analysis which follows. We contend that with respect to this
issue, the capacity is more natural than the internal capacity, since it is equal to the non-cyclic capacity of fully constrained
systems. To avoid a lengthy detour, the full details are provided in Appendix A.
Finally, we raise the question: what multidimensional SCSs are of interest? If we examine the extensive literature for fully
constrained systems, a significant proportion of multidimensional fully constrained systems are defined as an axial product
of one-dimensional fully constrained systems. Intuitively speaking, if we have a set of “forbidden patterns” defining a onedimensional fully constrained system, we can define its d-dimensional axial product by forbidding these patterns along each
dimension. We now formally define this for the case of d-dimensional SCSs with slightly more generality. This definition
generalizes the d-dimensional axial product defined in [19].
S
Definition 17. Consider S0 , . . . , Sd−1 ⊆ N, with 0 ∈ Si for all i ∈ [d], and SCSs Γi ⊆ P (ΣSi ). Denote S , i∈[d] Si ei ⊆ Zd .
The d-axial-product SCS, denoted ⊗i∈[d] Γi , is defined by
©
¶
⊗i∈[d] Γi , µ ∈ P (ΣS ) : ∀i ∈ [d], πSi ei (µ) ∈ Γi .
2
It follows from the above definition, that for every n ∈ N we have
Ä
ä ¶
©
Bn ⊗i∈[d] Γi = w ∈ Fnd : ∀i ∈ [d], frSwi ei ∈ Γi ,

7

with coordinates taken modulo n. Intuitively, the arrays of a d-axial-product SCS satisfy that along the ith direction, the empirical
d
distribution of Si -tuples is in Γi . Note that ⊗i∈[d] Γi induces a set of measures over Σ Fk where k = maxi {k i : k i ∈ Si }. Hence,
d

we sometimes consider a d-axial-product SCS ⊗i∈[d] Γi as a subset of P (Σ Fk ).
Example 18. Let Σ = {0, 1}. Consider two real constants 0 6 p0 , p1 6 1, and the one-dimensional SCSs, Γ0 and Γ1 , given by
¶
©
Γ0 = µ ∈ P (Σ2 ) : µ(11) 6 p0 ,
©
¶
Γ1 = µ ∈ P (Σ2 ) : µ(11) 6 p1 .
Here we are taking S0 = S1 = {0, 1}. The admissible words in the 2-axial-product SCS, Γ0 ⊗ Γ1 , are all two-dimensional words
in which the empirical frequency of two horizontally adjacent 1s is at most p0 , and the empirical frequency of two vertically
2
adjacent 1s is at most p1 , i.e., all the words w ∈ Σ Fn such that
{(0,0),(1,0)}

frw

{(0,0),(0,1)}

frw

(11) 6 p0 ,
(11) 6 p1 .

2

We may also consider Γ0 ⊗ Γ1 as a subset of P (Σ F2 )
©
¶
2
Γ0 ⊗ Γ1 = µ ∈ P (Σ F2 ) : π{(0,0),(0,1)} (µ)(11) 6 p0 , π{(0,0),(1,0)} (µ)(11) 6 p1 .
Note that
Åï
0
π{(0,0),(1,0)} (µ)(11) = µ
1
Åï
1
π{(0,0),(0,1)} (µ)(11) = µ
1

Åï
0
+µ
1
òã
Åï
0
1
+µ
0
1
0
1

òã

Åï
1
+µ
1
òã
Åï
0
1
+µ
1
1
1
1

òã

0
1

òã

1
0

òã

Åï

+µ

1
1

+µ

Åï
1
1

òã
1
,
1
òã
1
.
1
2

In this paper we are interested in the capacity and the internal capacity of multidimensional SCSs. Although the capacity
is easier to work with, as we will see later on, the task of computing it is still daunting. Thus, there is a necessity for more
easily computable bounds on the capacity. To this end, we define the independence entropy of a d-dimensional SCS, which is
the basis of the main results of this paper.
III. I NDEPENDENCE E NTROPY
In this section we define the independence entropy of multidimensional SCSs and present some of its properties. It will be
used to bound the capacity. The independence entropy is not a new notion, and has appeared previously in [19] in relation
to the capacity of fully constrained systems. However, the formulation of the independence entropy was combinatorial and
therefore less suitable for our purposes. Thus, we modify the definition of independence entropy and formulate it as a statistical
notion.
The admissible words of SCSs (see Definition 9) have their empirical S-tuple distribution from Γ. Finding such words
inexorably involves intricate dependencies between coordinates. This affects not only the task of generating such words, but
also the very basic problem of calculating or bounding the capacity of the SCS – the problem that is the focus of this paper.
In an attempt to simplify this problem, we study the independence-entropy approach. We eliminate all dependencies by
considering only product measures, i.e., where the symbol in each coordinate of the word is chosen independently of other
coordinates. Accordingly, we only require the average of S-marginals to be in Γ. We then ask what is the entropy of such
a system. Intuitively, we are seeking the maximum rate of transmission in a system where word coordinates are transmitted
independently and in parallel, designed such that the average S-marginals are in Γ. The following model provides a rough
interpretation of the independence entropy: Suppose each bit of the output is transmitted by a different agent, and the number
of agents is very large. The agents are allowed to coordinate a protocol in advance, but are unable to communicate once they
receive the messages to be transmitted. In addition, the statistics of the output should roughly satisfy the constraints given
by Γ, with high probability (as a function of the number of agents). In this case under suitable assumptions, the maximal
transmission rate would coincide with the independence entropy. We proceed with formal definitions, starting with a product
measure.
d
Definition 19. Let d ∈ N, and
say that µ ∈ P (ΣS ) is an independent probability measure or a
Q let S ⊆ Z be a finite set. We
d
product measure if µ(w) = v∈S π{v} (µ)(w). For S ⊆ Z that is possibly infinite, µ ∈ P (ΣS ) is a product measure whenever
πS0 (µ) is a product measure for every finite S0 ⊆ S.
2
Q
In other words, we say that µ is independent if there exists { pv ∈ P (Σ) : v ∈ S} such that µ = v∈S pv . We naturally
identify the set of product measures in P (ΣS ) with (P (Σ))S .

8

Next, we define the average of a marginal.
d

Definition 20. Given d, n ∈ N, µ ∈ P (Σ Fn ), and S ⊆ Fnd , let π S (µ) ∈ P (ΣS ) be the average of the S-marginals over translates
of µ:
1 X
π S (µ) , d
π S + v ( µ ),
| Fn |
d
v∈ Fn

2

where the coordinates S + v are taken modulo n.
Let S ⊆

Fkd

and let Γ ⊆

P (ΣS )

be a SCS. For n > k we define
n
o
d
P n (Γ) , µ ∈ (P (Σ)) Fn : π S (µ) ∈ Γ .
d

Thus, P n (Γ) consists of product measures on Σ Fn such that the average of the S-marginals is in Γ. We can now define the
independence entropy of a SCS.
Definition 21. Let d, k ∈ N, S ⊆ Fkd , and let Γ ⊆ P (ΣS ) be a d-dimensional SCS. The internal independence entropy of Γ is
defined by
1
H ( µ ),
h‘
ind ( Γ ) , lim sup sup
d
n→∞ µ∈P (Γ) n
n

where H (µ) , −

P

d

w∈Σ Fn

µ(w) log2 µ(w) is the entropy of µ. The independence entropy of Γ is defined by
hind (Γ) , lim h‘
ind (Be ( Γ )).
e →0+

2
Again, it is clear by definition that
h‘
ind ( Γ ) 6 hind ( Γ ).

(2)

The notion of independence entropy which appears here is a generalization of the combinatorial notion for fully constrained
systems that appears in [19].
d

Theorem 22. Let d, k ∈ N, and let Γ ⊆ P (Σ Fk ) be a fully constrained system. Then
hind (Γ) = hcom
ind ( Γ )
where hcom
ind is the combinatorial independence entropy from [19].
To avoid a significant diversion from the main discussion, the proof of Theorem 22, together with the required definitions
from [19], are given in Appendix B.
We now show properties of h‘
ind and hind which make them easier to analyze by reducing the multidimensional case to the
one-dimensional case. We start with an inequality given in the following lemma. The proof follows the same argument that
was used in [19] to show the inequality for fully constrained systems. However, the equality for fully constrained systems
holds in an easier and stronger sense.
Lemma 23. Let k ∈ N, and let Γ ⊆ P (Σk ) be a one-dimensional SCS. Then for all d ∈ N,
‘ ⊗d
h‘
ind ( Γ ) 6 hind ( Γ ).
Proof: Take µ̂ ∈ P n (Γ). Since µ̂ is a product measure, it can be written as µ̂ =
measure µ ∈ P n (Γ⊗d ) using µ̂. For every v ∈ Fnd set

Qn −1
i =0

π{i} (µ̂). We now construct a

π{v} (µ) , π{`(v)} (µ̂),
ÄP
d −1

ä

where `(v) ,
i =0 vi mod n is the modulo n of the sum of the coordinates of v.
Observe that µ is such that in every row in every direction, i.e., a set of coordinates of the form v + [n]ei , we obtain
some cyclic rotation of µ̂ by t positions, denoted σt (µ̂). However, µ̂ ∈ P n (Γ) implies σt (µ̂) ∈ P n (Γ). Thus, we obtain that
µ ∈ P n (Γ⊗d ) and
1
1
H (µ̂) = d H (µ).
n
n
Since we are taking the supremum over all measures µ̂, we have h‘ (Γ) 6 h‘ (Γ⊗d ).
ind

ind

Theorem 24. Let k ∈ N, and let Γ ⊆ P (Σk ) be a one-dimensional SCS. Then for all d ∈ N,
hind (Γ⊗d ) = hind (Γ).

9

Proof: We first show that hind (Γ⊗d ) 6 hind (Γ). Fix δ > 0 and take µ ∈ P n (Bδ (Γ⊗d )). Recall that
d

P n (Bδ (Γ⊗d )) ⊆ P (Σ Fn ).
Let (vi )i∈[nd−1 ] be an enumeration of {0} × Fnd−1 , i.e.,

{v0 , . . . , vnd−1 −1 } = {0} × Fnd−1 .
d

For i ∈ [nd−1 ], define µi ∈ P (Σn ) by µi , π[n]e0 +vi (µ). Now let µ̂ ∈ P (Σn ) be the product measure that is the product of
nd

all the µi ’s. This means that for a word a = a0 . . . and −1 ∈ Σ ,
µ̂( a) , µ0 ( a0 . . . an−1 )µ1 ( an . . . a2n−1 ) · · · µnd −1 ( an(nd−1 −1) . . . and −1 ),
d

Since each of the µi ’s is already a product measure, µ̂ ∈ P (Σn ) is also a product measure. We have
d

n −1
1 X
π [k] (µ̂) = d
π j+[k] (µ̂)
n
j =0
Ñ d −1
é
1) n −1
nX
−1 (i +X
1
= d
π j+[k] (µ̂)
n
i =0
j=in
éé
Ñ d −1 Ñ
( i +1) n − k
( i +1) n −1
nX
−1
X
X
1
π j+[k] (µ̂)
π j+[k] (µ̂) +
= d
n
j=in
i =0
j=(i +1)n−k+1
é
Ñ d −1
−1 −1
1) n − k
( i +1) n −1
nX
−1 (i +X
ndX
X
( a) 1
π j+[k] (µ̂)
= d
π( j−in)+[k] (µi ) +
n
i =0
j=in
i =0 j=(i +1)n−k +1
Ñ d −1
é
−1 −1
−1 −1
( i +1) n −1
1) n −1
( i +1) n −1
ndX
nX
−1 (i +X
ndX
X
X
1
π j+[k] (µ̂)
= d
π( j−in)+[k] (µi ) +
π( j−in)+[k] (µi ) −
n
i =0 j=(i +1)n−k +1
i =0
j=in
i =0 j=(i +1)n−k +1
é
Ñ d −1
1) n −1 Ä
nd−1 −1 (i +X
nX
−1
ä
1
1 X
= d −1
π [k ] ( µi ) −
π( j−in)+[k] (µi ) − π j+[k] (µ̂)
n
n
i =0

i =0

n d −1 −1

= π [ k ] e0 ( µ ) −

1 X
nd
i =0

j=(i +1)n−k +1

( i +1) n −1

Ä

X

π( j−in)+[k] (µi ) − π j+[k] (µ̂)

ä

j=(i +1)n−k +1

where
( a) follows from the ädefinition of µ̂ and since the coordinates are taken modulo n when calculating π[k] (µi ). Each
Ä
π( j−in)+[k] (µi ) − π j+[k] (µ̂) is a signed measure of total variation norm at most 1. Therefore,
π [k] (µ̂) − π [k]e0 (µ)

TV

6

k
.
n

This means that π [k] (µ̂) ∈ B k +δ (Γ). We obtained that for every e > δ > 0, and every µ ∈ P n (Bδ (Γ⊗d )), we can find
n

n0 ∈ N such that for every n > n0 , µ̂ ∈ P nd (Be (Γ)). Since µ and µ̂ are both product measures we have
X
H (µ) =
H (π{v} (µ))
v∈ Fnd

=

X

H (π{i} (µ̂))

i ∈[nd ]

= H (µ̂).
This implies that for every e > δ > 0,
lim sup
n→∞

sup
µ∈P n (Bδ (Γ⊗d ))

1
H (µ) 6 lim sup
sup
nd
n→∞ µ∈P (B
nd

e ( Γ ))

1
H ( µ ).
nd

+
We therefore obtain hind (Γ⊗d ) 6 h‘
ind (Be ( Γ )) for every e > 0. Taking the limit as e → 0 , by the definition of hind ( Γ ) we
have
hind (Γ⊗d ) 6 hind (Γ).

10

We now show the other direction. By Lemma 23, For every δ > 0 we have
⊗d
‘
h‘
ind (Bδ ( Γ )) 6 hind (Bδ ( Γ ) ).

By monotonicity of h‘
ind it thus follows that for every δ > 0,
⊗d
hind (Γ) 6 h‘
ind (Bδ ( Γ ) ).

Now observe that for every e > 0 there exists δ > 0 so that
ä
Ä
Bδ ( Γ ) ⊗ d ⊆ Be Γ ⊗ d .
It follows that for every e > 0
ää
Ä Ä
⊗d
.
hind (Γ) 6 h‘
ind Be Γ
Thus, by taking the limit e → 0+ ,

ä
Ä
hind (Γ) 6 hind Γ⊗d .

We conclude this section by noting that Lemma 23 and Theorem 24 show that for Γ ⊆ P (Σk ),
⊗d
‘ ⊗d
h‘
ind ( Γ ) 6 hind ( Γ ) 6 hind ( Γ ) = hind ( Γ ).

(3)

IV. I NDEPENDENCE E NTROPY L OWER B OUNDS T HE C APACITY
This section and the next explore the relationship between the independence entropy and the capacity. In this section we
show that the capacity of any d-dimensional SCS (not necessarily an axial product) is lower bounded by the independence
entropy.
Before proceeding we require a simple lemma.
Lemma 25. Let d, n ∈ N, and S ⊆ Fnd , then πS and π S are contractions with respect to the total-variation distance, i.e., for all
d
µ, ν ∈ P (Σ Fn ),

kπS (µ) − πS (ν)k TV 6 kµ − νk TV ,
kπ S (µ) − π S (ν)k TV 6 kµ − νk TV .
Proof: For every W ⊆ ΣS we have

|πS (µ)(W ) − πS (ν)(W )| = µ(πS−1 (W )) − ν(πS−1 (W )) 6 sup µ(W 0 ) − ν(W 0 ) = kµ − νk TV .
A0 ⊂ΣS

Hence the function πS+v is a contraction for every v ∈ Fnd . Then π S , being an average of contractions, is itself a contraction.
We are now ready to state and prove the main result of this section – a lower bound on the capacity. The corresponding
result for fully constrained systems was obtained in [19].
Theorem 26. Let d ∈ N, S ⊆ Zd be a finite set, and let Γ ⊆ P (ΣS ) be a SCS. Then hind (Γ) 6 cap(Γ).
Proof: Fix δ > 0, n ∈ N such that S ⊆ Fnd , and let µ ∈ P n (Bδ (Γ)). For m ∈ N, we have a natural identification
d
d
d
d with the unique pair r ∈ F d and q ∈ F d such that v = nq + r. Consider
isomorphism Σ Fnm ∼
= (Σ Fn ) Fm that identifies v ∈ Fnm
n
m
d Fd
d
m
F
F
the product measure µ ∈ P (Σ n ) m ⊆ P (Σ nm ) satisfying
Y
µm ({ x }) =
µ(π Fd (σnv ( x ))).
n

d
v∈ Fm

Note that since µ is a product measure, µm is also a product measure.
d
d
ˆ Fn the empirical distribution of non-overlapping F d -tuples, i.e.,
For a word w ∈ Σ Fnm , denote by fr
w
n
X
d
ˆ Fn , 1
δπ d (σnu (ŵ)) .
fr
w
Fn
| Fmd |
d
u∈ Fm

Additionally, observe that
1 X ˆ Fnd
Fd
frσv (w) = frwn .
d
| Fn |
d
v∈ Fn

11

Fd

Also, because πSn is an affine map, it follows that
1 X Fnd ˆ Fnd
Fd
πS frσv (w) = πS (frwn ).
d
| Fn |
d
v∈ Fn

Fd

By Lemma 7, πS (frwn ) = frSw .
Note that by the construction of µm we have π S (µ) = π S (µm ), and we obtain,
frSw −π S (µm )

TV

= frSw −π S (µ)
=

TV

X
1
1 X
π
(
δ
)
−
πS+v (µ )
S
σ
(
w
)
u
d |
| Fnm
| Fnd |
d
d
u∈ Fnm

=

v∈ Fn

X X
1
1 X
πS+v (µ )
π
(
δ
)
−
S
σ
(
w
)
nu+v
| Fnd || Fmd |
| Fnd |
d
d
d
v∈ Fn u∈ Fm

( a)

=

v∈ Fn

X X
1 X
1
)
−
π
(
δ
πS+v (µ )
S
+
v
σ
(
w
)
nu
| Fnd || Fmd |
| Fnd |
d
d
d
v∈ Fn u∈ Fm

(b)

6

v∈ Fn

1 X
1 X
πS+v (δσnu (w) ) − πS+v (µ)
| Fnd |
| Fmd |
d
d
v∈ Fn

u∈ Fm

=

1 X
πS+v
| Fnd |
d
v∈ Fn

1 X
δσnu (w)
| Fmd |
d

v∈ Fn

6

1 X ˆ Fnd
frw − µ
| Fnd |
d
v∈ Fn

TV

TV

− πS+v (µ )

u∈ Fm

d
1 X
ˆ Fn ) − πS+v (µ)
= d
πS+v (fr
w
| Fn |
d

(d)

TV

é

Ñ
(c)

TV

TV

TV

TV

d

ˆ Fn − µ
= fr
w

TV

where:
• ( a ) follows since πS ( δσv (w) ) = πS+v ( δw ).
• ( b ) follows by the triangle inequality.
• ( c ) follows since πS is an affine map.
• ( d ) follows by Lemma 25.
Fd

ˆ n − µk TV < e − δ then k frS −π S (µm )k TV < e − δ. Therefore,
Thus, for e > δ, if kfr
w
w
n
o ß
d
d
d
ˆ Fn − µ
w ∈ Σ Fnm : frSw −π S (µ)
> e − δ ⊆ w ∈ Σ Fnm : fr
w
TV

Using the fact that π S (µ) ∈ Bδ (Γ), it follows that
n
o ß
d
d
w ∈ Σ Fnm : frSw ∈
/ int (Be (Γ)) ⊆ w ∈ Σ Fnm :

TV

™
> e−δ ,

d

ˆ Fn − µ
fr
w

™
> e−δ .

(4)

TV


where int(·) denotes the interior of a set, i.e., int(Be (Γ)) = ν ∈ P (ΣS ) : infµ∈Γ kν − µk TV < e .
d

If w ∈ Σ Fnm was randomly drawn according to µm , the non-overlapping Fnd -tuples are distributed i.i.d. according to µ. Apply
Cramer’s Theorem (as in [7, Theorem 2.2.3 remark c]) to deduce that for e > δ and for every m,
Ñ
é
Åß
™ã
d
d
F
n
ˆ −µ
µm
w ∈ Σ Fnm : fr
> e−δ
6 2 exp −m
inf
H (ν|µ) .
w
TV

d

ν∈P (Σ Fn ): kν−µk TV >e−δ

12

Note that the function ν × µ 7→ H (ν|µ) is continuous and strictly positive off the diagonal. Thus, for every e > δ we have
cµ (e) ,

d

H (ν|µ) > 0.

inf

ν∈P (Σ Fn ): kν−µk TV >e−δ

Hence
µm

Åß

d

ˆ Fn − µ
fr
w

d

w ∈ Σ Fnm :

> e−δ

™ã


6 2 exp −mcµ (e) .

(5)

TV

¶
©
d
Recall that Bnm (int(Be (Γ))) = w ∈ Σ Fnm : frSw ∈ int(Be (Γ)) . By (4), we have
 d

µm Σ Fnm \ Bnm (int(Be (Γ)))
n
o
d
= µm w ∈ Σ Fnm : frSw ∈
/ int(Be (Γ))
Åß
™ã
d
d
ˆ Fn − µ
w ∈ Σ Fnm : fr
>
e
−
δ
.
6 µm
w

(6)

TV

Combining (5) and (6) we have,
 d


ξ , µm Σ Fnm \ Bnm (int(Be (Γ))) 6 2 exp −mcµ (e) .
It now follows that,
1
1
H (µ) =
H (µm )
nd
(nm)d
X
1
µm (w) log2 µm (w)
=−
d
(nm)
d
w∈Σ Fnm

=−

1
(nm)d

X

µm (w) log2 µm (w)

w∈Bnm (int(Be (Γ)))

1
−
(nm)d

X

µm (w) log2 µm (w)

w/
∈Bnm (int(Be (Γ)))
d

log2 Σ Fnm \ Bnm (int(Be (Γ)))
log2 |Bnm (int(Be (Γ)))|
6 (1 − ξ ) ·
+ξ·
+ H2 (ξ )
(nm)d
(nm)d

( a)

d

(nm)
log2 |Bnm (int(Be (Γ)))|
−mcµ (e) log2 | Σ |
+
2e
+ H2 (ξ )
6
(nm)d
(nm)d
d
1
1
6
log2 |Bnm (int(Be (Γ)))| + 2e−mcµ (e)
log2 |Σ|(nm) + H2 (ξ ).
(nm)d
(nm)d

where ( a) follows from standard maximization of entropy arguments, and where H2 (ξ ) , −ξ log2 ξ − (1 − ξ ) log2 (1 − ξ )
is the binary entropy function. This implies
1
1
H (µ) = lim sup d H (µ)
nd
m→∞ n
1
6 lim sup
log2 |Bnm (int(Be (Γ)))|
d
m→∞ ( nm )
1
6 lim sup
log2 |Bnm (Be (Γ))|
(
nm
)d
m→∞
” (Be (Γ)) ,
6 cap
This is true for every µ ∈ P n (Bδ (Γ)) and hence
sup
µ∈P n (Bδ (Γ))

1
” (Be (Γ)) .
H (µ) 6 cap
nd

Since this holds for every n we have that for every e > δ > 0,
” (Be (Γ)).
h‘
ind (Bδ ( Γ )) 6 cap

13

Taking the limit as δ → 0, this implies that for every e > 0,
” (Be (Γ)).
hind (Γ) 6 cap
Finally, taking the limit as e → 0, it follows that
hind (Γ) 6 cap(Γ).
‘ ⊗d
We summarize our results thus far by noting that for a SCS Γ ⊆ P (Σk ), since h‘
ind ( Γ ) 6 hind ( Γ ), Theorem 26 together
with (3) show that
⊗d
⊗d
‘ ⊗d
h‘
ind ( Γ ) 6 hind ( Γ ) 6 hind ( Γ ) 6 cap( Γ ),
h‘ (Γ) 6 h‘ (Γ⊗d ) 6 h (Γ⊗d ) = h (Γ) 6 cap(Γ).
ind

ind

ind

ind

(7)
(8)

V. U PPER B OUND ON L IMITING C APACITY
In this section we prove that if Γ ⊆ P (Σk ) is a convex one-dimensional SCS and Γ⊗d its d-axial product, then
lim sup cap(Γ⊗d ) 6 hind (Γ⊗d ).
d→∞

The main idea is to show that for any e > 0 we are able to find d large enough for which the independence entropy is e-close
to cap(Γ⊗d ). This is the main result of [23] and the proof here is an adaptation of it.
Before going into details we introduce a different form of d-axial product which we call the weak d-axial product. For a
one dimensional SCS, Γ ⊆ P (Σk ), define




X
d
1
Γd , µ ∈ P (Σ Fk ) :
π [ k ] ei ( µ ) ∈ Γ ,


d
i ∈[d]

and thus
Ä

ä

B n Γ d =






1 X [ k ] ei
:
frw ∈ Γ .

d

w ∈ Fnd



i ∈[d]

For the weak d-axial product we define,

P n ( Γ d ) ,





d

µ ∈ (P (Σ)) Fn



X
1
:
π [ k ] ei ( µ ) ∈ Γ .

d
i ∈[d]

This last definition is a relaxed version of Γ⊗d , since P n (Γ⊗d ) is the set of all independent measures for which the average
of the k-marginals in each direction (separately) belongs to Γ, whereas P n (Γd ) is the set of all independent measures for
which the average of k-marginals (over all directions) belongs to Γ.
Correspondingly, we have,
1
hind (Γd ) , lim lim sup
sup
H ( µ ),
d
+
e →0
n→∞ µ∈P (B (Γ)d ) n
n
e
P
where H (µ) , −
µ(w) log2 µ(w) is the entropy of µ.
Fd
w∈Σ

n

As will become clearer later on, it will be somewhat easier to use hind (Γd ) than hind (Γ⊗d ) in this section. First, the
following lemma shows that the relaxation leading to hind (Γd ) does not affect the independence entropy.
Lemma 27. Let k ∈ N, and let Γ ⊆ P (Σk ) be a convex one-dimensional SCS, then
hind (Γ) = hind (Γ⊗d ) = hind (Γd ).
Proof: By Theorem 24 we already know that hind (Γ⊗d ) = hind (Γ). Thus, we are left with proving the last equality. Since
Γ is convex, for every δ > 0,
P n (Bδ (Γ⊗d )) ⊆ P n (Bδ (Γ)⊗d ) ⊆ P n (Bδ (Γ)d ).
Hence,
hind (Γ⊗d ) 6 hind (Γd ).

14

The other direction follows essentially by using the same method as in the proof of Theorem 24, as we now describe. Let
j
j −1
d− j
(vi )i∈[nd−1 ] be an enumeration of Fn × {0} × Fn , i.e.,
¶ j
©
j −1
j
d− j
v0 , . . . , vnd−1 −1 = Fn × {0} × Fn .
j

j

Fix δ > 0 and µ ∈ P n (Bδ (Γ)d ). For i ∈ [nd−1 ] and j ∈ [d], define µi ∈ P (Σn ) by µi , π
be the product measure satisfying
µ̂({ a}) =

Y

Y

d

j

[ n ] e j + vi

(µ). Now let µ̂ ∈ P (Σdn )

j

µi ( ain+ jnd . . . a(i+1)n+ jnd −1 )

j∈[d] i ∈[nd−1 ]
j

d

for every word a = a0 . . . adnd −1 ∈ Σdn . It is clear that µ̂ is indeed a product measure, because every µi is also a product
measure. Now,
1 X
πi+[k] (µ̂)
π [k] (µ̂) =
dnd
d
i ∈[dn ]

1 X X X
= d
π[k]+in+`+ jnd (µ̂)
dn
d
−
1
j∈[d] i ∈[n
] `∈[n]
Ñ
é
n −1
X
X
X
X
1
π[k]+in+`+ jnd (µ̂) +
π[k]+in+`+ jnd (µ̂)
= d
dn
d
−
1
`=n−k
j∈[d] i ∈[n
`∈[n−k]
]
Ñ
é
n
−
1
X
X
X
X
1
j
π[k]+` (µi ) +
π[k]+in+`+ jnd (µ̂)
= d
dn
`=n−k
j∈[d] i ∈[nd−1 ]
`∈[n−k]
Ñ
é
n −1
n −1
X
X
X
X
X
1
j
j
π[k]+` (µi ) −
π[k]+` (µi ) +
π[k]+in+`+ jnd (µ̂)
= d
dn
d −1
j∈[d] i ∈[n

( a)

=

]

`=n−k

`∈[n]

1 X
1 X X
π [k]e j (µ ) − d
d
dn
d −1
j∈[d]

j∈[d] i ∈[n

n −1
X

Ä

`=n−k

ä
j
π[k]+` (µi ) − π[k]+in+`+ jnd (µ̂) .

] `=n−k

Recall that from the definition of P n (Bδ (Γ)d ), we have
1 X
π [ k ] e j ( µ ) ∈ Bδ ( Γ ).
d
j∈[d]

Ä

j

ä

π[k]+` (µi ) − π[k]+in+`+ jnd (µ̂) is a signed measure of total variation norm at most 2, it follows that π [k] (µ̂) ∈


B 2k +δ (Γ), so µ̂ ∈ P dnd B 2k +δ (Γ) . Hence, for every e > δ > 0, and every µ ∈ P n (Bδ (Γ)d ), we can find n0 ∈ N such
Since
n

n

that for every n > n0 , µ̂ ∈ P dnd (Be (Γ)), and therefore,
lim sup
n→∞

sup
µ∈P n (Bδ (Γ)d )

1
H (µ) 6 lim sup
sup
nd
n→∞ µ∈P
(B
dnd

e ( Γ ))

1
H ( µ ).
dnd

Thus, we obtain hind (Γd ) 6 h‘
ind (Be ( Γ )) for every e > 0, and by definition it follows that
hind (Γd ) 6 hind (Γ).
Given a probability space (X , F , P), denote by L2 (X , F , P, Cn ) the Hilbert space of F -measurable functions f : X → Cn
satisfying
Z

k f k2L2 ,

h f , f idP < ∞,

where h·, ·i is the standard inner product on Cn .
The following lemma is based on Dirichlet’s “pigeon hole principle” and different versions of it are used in many de-Finetti
type proofs (see, for example, [8] [21, Lemma 4.1]).

15

Lemma 28. Let (X , F , P) be a probability space and let F0 ⊆ F1 ⊆ · · · ⊆ Fm ⊆ F be a sequence of sub-σ-algebras. Let
f ∈ L2 (X , F , P, Cn ), and denote f j , E[ f |F j ], the conditional expectation of f with respect to the sub-σ-algebra F j . Then,
there exists t ∈ [m] such that
1
k f t+1 − f t k2L2 6 k f k2L2
m
Proof: For every `, let V` , L2 (X , F` , P, Cn ) denote the corresponding sub-space of the Hilbert space V , L2 (X , F , P, Cn ).
Then f ` is an orthogonal projection of f onto V` . Thus, h f − f ` , gi L2 = 0 for every g ∈ V. Therefore,
X
k f m k2L2 =
k f `+1 − f ` k2L2 + k f 0 k2L2 .
`∈[m]

Additionally, 0 6 k f m k2L2 6 k f k2L2 . The result follows by noticing that if m non-negative real numbers sum to at most k f k2L2
then the value of at least one element is at most m1 k f k2L2 .
Before stating the lemmas, we need the following notation. Recall that for k ∈ N, we defined [k] , {0, . . . , k − 1}. We
now define [−k ] , {−1, . . . , −k}.
Lemma 29. For every e > 0, and any m ∈ N, there exists d0 ∈ N such that for every d > d0 , and every n, j ∈ N, n > j + 2,
there exists a sequence of m + 1 random subsets X0 , X1 , . . . , Xm ⊆ Fnd , and random variables It,v ∈ [d], for all t ∈ [m], v ∈ Fnd ,
all defined on an appropriate probability space (X , 2X , P), such that all the following hold:
1) P( Xi ⊆ Xi+1 ) = 1 for all i ∈ [m].
2) P(| Xm | 6 e| Fnd |) > 1 − e.
3) For all v ∈ Fnd and t ∈ [m], It,v is distributed uniformly on [d] and is independent of Xt . Furthermore, for every value of Xt ,

P Xt ∪ ([−( j + 1)]e It,v + v) ⊆ Xt+1 Xt > 1 − e.
Proof: Choose 0 < p < 1 small enough so that 1 − (1 − p)m+1 6 2e , and conveniently denote pi , 1 − (1 − p)i+1 . For
all i ∈ [m + 1], consider random subsets Ai ⊆ Fnd whose coordinates are chosen i.i.d. Bernoulli( p), i.e., P(v ∈ Ai ) = p for
all v ∈ Fnd , independently of Fnd \ {v}. Define X−1 , ∅, and for all i ∈ [m + 1], define
Xi , Xi − i ∪ A i .
Thus, P(v ∈ Xi ) = pi for all v ∈ Fnd , independently of Fnd \ {v}. We contend that for large enough d, the claims hold.
First, it is clear that P( Xi ⊆ Xi+1 ) = 1 for i ∈ [m + 1] by construction. Second, we have




2 d
P | Xm | 6 e Fnd > P | Xm | < 2pm Fnd > 1 − e−2pm n ,
where the last inequality follows from Hoeffding’s inequality. Since the right-hand side approaches 1 when n > 2 and d → ∞,
claim 2 holds for large enough d.
We now address claim 3. Fix t ∈ [m] and consider At+1 . For a coordinate v ∈ Fnd , denote by D (t, v) the set
D (t, v) , {i ∈ [d] : v + [−( j + 1)]ei ⊆ At+1 } .
If D (t, v) 6= ∅ then draw It,v uniformly from D (t, v). Otherwise, draw It,v uniformly from [d]. Note that It,v is distributed
uniformly on [d] since the distribution of At+1 is invariant under coordinate permutation. Since the coordinates in At+1 are
chosen independently of At , At−1 , . . . , A0 we obtain that It,v is independent of Xt . Finally, we have

P Xt ∪ ([−( j + 1)]e It,v + v) ⊆ Xt+1 Xt > P( D (t, v) 6= ∅) = 1 − (1 − p j+1 )d .
Since the right-hand side approaches 1 as d → ∞, claim 3 holds for large enough d.
If X is a random variable over some probability space, we use PX to denote its distribution. Let X0 , . . . , Xk−1 be random
variables over the same probability space (X , 2X , P). We denote by ( X0 , . . . , Xk−1 ) the vector distributed according to their
joint probability, PX0 ,...,Xk−1 , and denote by ( X0 × · · · × Xk−1 ) the vector distributed according to their product probability,
Q
i.e., PX0 ×···× Xk−1 , i∈[k] PXi .
Lemma 30. Let X be a finite set, and X0 , . . . , Xk−1 be k random variables defined over the same probability space (X , 2X , P).
Then
k −2
h
i
X
PX0 ,...,Xk−1 − PX0 ×···× Xk−1
6
EX0 ,...,Xi PXi+1 | X0 ,...,Xi − PXi+1
.
TV

i =0

TV

16

Proof: We prove this by induction on k. The case of k = 1 is trivially true. In the base case of k = 2 we have,
1 X
PX0 ,X1 − PX0 ×X1 TV =
PX0 ,X1 ( x0 , x1 ) − PX0 ( x0 )PX1 ( x1 )
2 x ,x
0 1
1 X
=
P X0 ( x 0 ) P X1 | X0 ( x 1 | x 0 ) − P X0 ( x 0 ) P X1 ( x 1 )
2 x ,x
0

(9)

1

where the sum of x0 and x1 is over the support of X0 and X1 , respectively. Since PX0 ( x0 ) > 0 we have
Ñ
é
X
1 X
1 X
P X0 ( x 0 )
P X0 ( x 0 ) P X1 | X0 ( x 1 | x 0 ) − P X0 ( x 0 ) P X1 ( x 1 ) =
P X1 | X0 ( x 1 | x 0 ) − P X1 ( x 1 )
.
2
2
x0 ∈X

x0 ,x1 ∈X

(10)

x1 ∈X

Combining (9) and (10) and using the total variation distance definition we obtain
h
PX0 ,X1 − PX0 × X1 TV = EX0 PX1 | X0 − PX1

i
TV

.

Now assume the statement is correct for k − 1 random variables and we show it is correct for k random variables. We write
PX0 ,...,Xk−1 − PX0 ×···× Xk−1

TV

= PX0 ,...,Xk−1 − P(X0 ,...,Xk−2 )×Xk−1 + P(X0 ,...,Xk−2 )×Xk−1 − PX0 ×···×Xk−1

TV

.

By applying the triangle inequality we obtain
PX0 ,...,Xk−1 − PX0 ×···× Xk−1

TV

6 PX0 ,...,Xk−1 − P(X0 ,...,Xk−2 )×Xk−1

TV

+ P(X0 ,...,Xk−2 )×Xk−1 − PX0 ×···×Xk−1

TV

. (11)

Considering Y = ( X0 , . . . , Xk−2 ) as a tuple-valued radom variable, and applying the case k = 2 on the pair of random variables
(Y, Xk−1 ) we have:
h
i
6 EX0 ,...,Xk−2 PXk−1|(X ,...,X ) − PXk−1
(12)
PX0 ,...,Xk−1 − P(X0 ,...,Xk−2 )× Xk−1
TV

0

k −2

TV

It is easy to check that
P(X0 ,...,Xk−2 )×Xk−1 − PX0 ×···× Xk−1

TV

= PX0 ,...,Xk−2 − PX0 ×···×Xk−2

(13)

TV

By the induction hypothesis we have
PX0 ,...,Xk−2 − PX0 ×···× Xk−2

TV

6

k −3
X

EX0 ,...,Xi

h

PXi+1 | X0 ,...,Xi − PXi+1

i =0

i
TV

.

Combining this with (11), (12) and (13) completes the proof.
For A ⊆ Fnd , let F A ⊆ 2Σ

Fnd

denote the σ-algebra generated by the coordinates in A, namely,
nn
o
o
d
FA ,
x ∈ Σ Fn : π A ( x ) ∈ W
: W ⊆ ΣA .
d

Definition 31. Let d, k, n ∈ N, A ⊆ Fnd , and let y ∈ Σ Fn . For a one-dimensional SCS, Γ ⊆ P (Σk ), and its d-axial-product SCS,
Γ⊗d , we define the following:
µn,d is the uniform measure over Bn (Γ⊗d ),
µy,A , µn,d (· | F A ) (y),
Y

ηy,A ,
π{v} µy,A .
v∈ Fnd

2
In other words, µy,A is the uniform distribution on Bn (Γ⊗d ) given whose positions in A agree with y A . Moreover, ηy,A is
the independent version of µy,A . The following statement is a particular application of Lemma 30 above.
Lemma 32. For every d, n ∈ N, i ∈ [d], and A ⊆ Fnd , we have
i
X h
X X h
E π[k]ei +v (ηy,A ) − π[k]ei +v (µy,A )
6
E π{v} (ηy,A ) − π{v} (µy,( A∪([− j]ei +v) )
v∈ Fnd

TV

v∈ Fnd

j∈[k]

i
TV

.

Proof: First note that if k = 1 the result is immediate since all the summands on the left-hand side are 0. We now
d
examine the case of k > 2. For the time being, let us fix v ∈ Fnd and y ∈ Σ Fn . We define the random variables X j , j ∈ [k ],

17

y

where X0 , . . . , Xk−1 is distributed according to PX0 ,...,X
y

, π[k]ei +v (µy,A ). In particular, each X j is distributed according
= π[k]ei +v (ηy,A ). We use the superscript y to emphasize
k −1

k −1

y

to PX , π jei +v (µy,A ) = π jei +v (ηy,A ). Additionally, PX0 ×···× X
j

d

y

that these distributions depend y. Also for z ∈ Σ Fn such that z A = y A , the conditional probability PX

j+1 | X0 ,...,X j

evaluated at

z is equal to the measure π( j+1)ei +v (µz,A∪([ j+1]ei +v) ). By Lemma 30, we have
y

PX0 ,...,X

y

− PX0 ×···×Xk−1
k −1

TV

6

k −2 ï
X
y
E PX
j =0

ò

y

j+1 | X0 ,...,X j

− P Xi + 1

.

(14)

TV

The expectations in the right-hand side are with respect to the conditioning on the random variables X0 , . . . , X j . We can rewrite
the above equation as follows:
k −2 Z
X
π[k]ei +v (µy,A ) − π[k]ei +v (ηy,A )
6
π( j+1)ei +v (µz,A∪([ j+1]ei +v) ) − π( j+1)ei +v (ηz,A )
dµy,A (z)
(15)
TV

TV

j =0

Integrating the above inequality over y with respect to µn,d we have:
Z
π[k]ei +v (µy,A ) − π[k]ei +v (ηy,A )
dµn,d (y)
TV

6

k −2 Z Z
X

π( j+1)ei +v (µz,A∪([ j+1]ei +v) ) − π( j+1)ei +v (ηz,A )

j =0

TV

dµy,A (z)dµn,d (y).

d

By definition of µy,A as the conditional measure, for every f : Σ Fn → R we have
ZZ
Z
n,d
f (z)dµy,A (z)dµ (y) =
f (y)dµn,d (y).
Writing the integeral with repect to µn,d as E [·], we thus have
E

h

π[k]ei +v (µy,A ) − π[k]ei +v (ηy,A )

i
TV

6

k −2 h
X
E π( j+1)ei +v (µy,A∪([ j+1]ei +v) ) − π( j+1)ei +v (ηy,A )
j =0

i
TV

.

Summing over all v ∈ Fnd we obtain
X

E

h

π[k]ei +v (µy,A ) − π[k]ei +v (ηy,A )

v∈ Fnd

i
TV

6

k −2 h
XX
E π( j+1)ei +v (µy,A∪([ j+1]ei +v) ) − π( j+1)ei +v (ηy,A )
v∈ Fnd

i
TV

j =0

. (16)

Recall that [− j] , {−1, . . . , − j}, hence

[ j + 1]ei = ( j + 1)ei + [−( j + 1)]ei .
Thus, (16) can be written as
X h
E π[k]ei +v (µy,A ) − π[k]ei +v (ηy,A )
v∈ Fnd

i

(17)

TV

k −2 h
XX
6
E π( j+1)ei +v (µy,A∪(( j+1)ei +v+[−( j+1)]ei ) ) − π( j+1)ei +v (ηy,A )
v∈ Fnd j=0

i
TV

.

Since we are summing over all v ∈ Fnd , and since coordinates are taken modulo n, we may write (17) as follows,
X
v∈ Fnd

E

h

π[k]ei +v (µy,A ) − π[k]ei +v (ηy,A )

i
TV

6

k −2 h
XX
E π{v} (µy,A∪(v+[−( j+1)]ei ) ) − π{v} (ηy,A )
v∈ Fnd j=0

i
TV

.

(18)

Since the total variation distance is non-negative, (18) implies the lemma.
The following proposition, which is used to prove the main result of this section, considers the following scenario. Assume
d
y ∈ Σ Fn is randomly drawn using the measure µn,d , i.e., it is drawn uniformly at random from the set of admissible words
Bn (Γ⊗d ). We then studyÄ the randomä variable ηy,A (a measure in itself), and ask what is the probability that it resides within
the set of measures P n (Be (Γ))d . For convex SCSs, we prove this probability is e-close to 1, assuming d is sufficiently
large.

18

Proposition 33. Let k ∈ N, and let Γ ⊆ P (Σk ) be a convex SCS. For any e > 0, there exists d0 ∈ N, such that for all d ∈ N,
d
d > d0 , n ∈ N, n > k + 2, there exists A ⊆ Fnd , | A| 6 end , such that for y ∈ Σ Fn drawn randomly using the measure µn,d ,
Ä
ää
Ä
µn,d ηy,A ∈ P n (Be (Γ))d > 1 − e.
Proof: Recall that by Definition 31, ηy,A is a product measure, while µy,A is not necessarily so. Additionally, we contend
that π [k]ei (µy,A ) ∈ Γ for all y ∈ Bn (Γ⊗d ), A ⊆ Fnd and i ∈ [d]. Indeed,
1 X
π [k]ei (µy,A ) = d
π[k]ei +v (µy,A )
| Fn |
d
v∈ Fn

1 X
1
= d
−
1
| Fn |
|π A (y A )|
d
v∈ Fn

1

X

π[k]ei +v (δx̂ )

1
(y A )
x ∈π −
A

1 X
π[k]ei +v (δx̂ )
1
| Fd |
|π −
A ( y A )| x ∈π −1 (y ) n v∈ F d
n
A
A
Ñ
é
X
X
1
1
π [ k ] ei
δσv ( x̂)
= −1
d
|
F
|π A (y A )|
n|
−1
d

=

X

v∈ Fn

x ∈π A (y A )

=

1

X

1
|π −
A ( y A )|

[ k ] ei

frx

,

1
x ∈π −
(y A )
A

¶
©
[ k ] ei
1
1
⊗d
where we recall that π −
∈ Γ for every x ∈ π −
A ( y A ) = x ∈ Bn ( Γ ) : x A = y A . Since frx
A ( y A ) and since Γ is
convex the contention is proved. Additionally, by the convexity of Γ, π [k]ei (µy,A ) ∈ Γ implies
1 X
π [k]ei (µy,A ) ∈ Γ.
d
i ∈[d]

Draw y ∈ Σ

Fnd

randomly using the measure µn,d . For any A ⊆ Fnd , let us denote
D A,y ,

1 X
1 X
π [k]ei (ηy,A ) −
π [k]ei (µy,A )
d
d
i ∈[d]

i ∈[d]

.
TV

We will use Ey [·] to denote expectation with respect to the random variable y which is randomly drawn using the measure
µn,d . Denote
D A , Ey [ D A,y ].
To prove the theorem, it suffices to show that for any e > 0, if d is large enough there exists A ⊆ Fnd , | A| 6 end , and with
probability at least 1 − e (with respect to µn,d ) we have D A,y 6 e. By a standard application of the Markov inequality, it is
sufficient to show that (under the above conditions) D A 6 e2 .
d
By definition, for any A ⊆ Fnd and any y ∈ Σ Fn we have
D A,y =

ä
1 X XÄ
π
(
η
)
−
π
(
µ
)
y,A
y,A
[
k
]
e
+
v
[
k
]
e
+
v
i
i
d| Fnd |
d
i ∈[d] v∈ Fn

.
TV

Applying the triangle inequality we obtain
D A,y 6

1 X X
π[k]ei +v (ηy,A ) − π[k]ei +v (µy,A )
d| Fnd |
d
i ∈[d] v∈ Fn

Taking the expectation, Ey , on both sides and using its linearity we get
h
1 X X
DA 6
E
π[k]ei +v (ηy,A ) − π[k]ei +v (µy,A )
y
d| Fnd |
d
i ∈[d] v∈ Fn

TV

.

i
TV

.

By Lemma 32 and the linearity of the expectation we obtain
h
X 1 X X
DA 6
E
π{v} (ηy,A ) − π{v} (µy,A∪([−( j+1)]ei +v) )
y
d| Fnd |
d
j∈[k ]

i ∈[d] v∈ Fn

i
TV

.

19

Consider another random variable x ∈ Σ Fn , also randomly drawn using the measure µn,d . Now define f : Σ Fn → {0, 1} Fn ×Σ
d

d

d

by
®
f ( x )(v,a) ,

xv = a,
otherwise,

1
0

for all v ∈ Fnd and a ∈ Σ. Thus, by definition we have that
î
π{v} (ηy,A )( a) = π{v} (µy,A )( a) = Ex f ( x )(v,a)

ó
F A ( y ).

Since Σ is finite we can write the total variation distance as a sum, and then apply the triangle inequality, which results in
i
î
ó
î
ó
1X 1 X XX h
DA 6
E
E
f
(
x
)
F
(
y
)
−
E
f
(
x
)
F
(
y
)
.
(19)
y
x
x
A
(
v,a
)
(
v,a
)
A
∪([−(
j
+
1
)]
e
+
v
)
i
2
d| Fnd |
d
i ∈[d] v∈ Fn a∈Σ

j∈[k ]

For any j ∈ [k], viewing the expression
î
XX h
Ey Ex f ( x )(v,a)

ó
î
F A (y) − Ex f ( x )(v,a)

v∈ Fnd a∈Σ

i
ó
F A∪([−( j+1)]ei +v) (y)

as an inner product of a vector in RFn ×Σ whose (v, a)’th coordinate is equal to
h
i
î
ó
î
ó
Ey Ex f ( x )(v,a) F A (y) − Ex f ( x )(v,a) F A∪([−( j+1)]ei +v) (y)
d

and 1, we may apply Cauchy-Schwarz (C.S) inequality and obtain
h
i
î
ó
î
ó
X
Ey Ex f ( x )(v,a) F A (y) − Ex f ( x )(v,a) F A∪([−( j+1)]ei +v) (y) · 1

(20)

(v,a)∈ Fnd ×Σ

ÕÑ
C.S

6



X

Ey

h

ó

î

î

F A (y) − Ex f ( x )(v,a)

Ex f ( x )(v,a)

ó

F A∪([−( j+1)]ei +v) (y)

i2

éÑ

(v,a)∈ Fnd ×Σ

=



12

(v,a)∈ Fnd ×Σ

ÕÑ
X

é
X

Ey

h

î

ó

î

F A (y) − Ex f ( x )(v,a)

Ex f ( x )(v,a)

ó

F A∪([−( j+1)]ei +v) (y)

i2

é

· Fnd · |Σ|.

(v,a)∈ Fnd ×Σ

Thus, combining (19) and (20) we have
Ã
p
î
|Σ| X X X X  h
DA 6 »
Ey Ex f ( x )(v,a)
2d Fnd j∈[k] i∈[d] v∈ Fd a∈Σ

ó
î
F A (y) − Ex f ( x )(v,a)

i2
ó
F A∪([−( j+1)]ei +v) (y)
.

n

Using the fact that ( E[| X |])2 6 E[ X 2 ] (again, by C.S), we have
Ã
p
Å ï î
ó
î
|Σ| X X X X
Ey Ex f ( x )(v,a) F A (y) − Ex f ( x )(v,a)
DA 6 »
2d Fnd j∈[k] i∈[d] v∈ Fd a∈Σ

F A∪([−( j+1)]ei +v)

ó

2 òã
(y)
.

(21)

n

Choose m large enough such that

√1
m

2

6 √e
k

|Σ|

and denote e0 =

e2
.
k|Σ|

Now let P, It,v , X0 , X1 , . . . , Xm be as given by Lemma

29 with n > k + 2 and with e0 and obtain d0 . From here on, assume d > d0 . Let E denote the expectation with respect to P.
First, from (21) we may bound DXt , for any t ∈ [m + 1], by
Ã
p
ï î
2 ò
ó
î
ó
|Σ| X 1 X X X
D Xt 6 »
Ey Ex f ( x )(v,a) F Xt (y) − Ex f ( x )(v,a) F Xt ∪([−( j+1)]ei +v) (y)
. (22)
2 Fnd j∈[k] d i∈[d] v∈ Fd a∈Σ
n

By the properties of Xt and Xt+1 given in Lemma 29, for every v ∈ Fnd there is a random variable It,v independent of Xt and
distributed uniformly on [d] so that P( Xt ∪ ([−( j + 1)]e It,v + v) ⊆ Xt+1 | Xt ) > 1 − e0 . Denote
Xt,v , Xt ∪ ([−( j + 1)]e It,v + v).

20

Since It,v is independent of Xt we have

Ã
ï î
 XX
E
Ey Ex f ( x )(v,a)


ó

î

F Xt (y) − Ex f ( x )(v,a)

ó

F Xt,v (y)

2 ò

v∈ Fnd a∈Σ

1 X
=
d

Ã

i ∈[d]

XX

Ey

ï

î

Ex f ( x )(v,a)

ó

î

F Xt (y) − Ex f ( x )(v,a)


Xt 

(23)

F Xt ∪([−( j+1)]ei +v)

v∈ Fnd a∈Σ

ó

2 ò
(y) .

From (22) and (23) we obtain
D Xt


Ã
p
ï î
X
|Σ|
 XX
»
Ey Ex f ( x )(v,a)
6
E
2 Fnd j∈[k]
v∈ F d a∈Σ


ó

î

F Xt (y) − Ex f ( x )(v,a)

ó

F Xt,v (y)

2 ò


Xt  .

(24)

n

ó
Since we may view Ex f ( x )(v,a) F Xt as the orthogonal projection of f ( x )(v,a) on L2 ( Fnd , F Xt , µn,d , R), if Xt,v ⊆ Xt+1
we have
ï î
2 ò
ó
ó
î
Ey Ex f ( x )(v,a) F Xt (y) − Ex f ( x )(v,a) F Xt,v (y)
ï î
2 ò
ó
î
ó
6 Ey Ex f ( x )(v,a) F Xt (y) − Ex f ( x )(v,a) F Xt+1 (y)
.
î

Otherwise, if Xt,v * Xt+1 , then
ï î
Ey Ex f ( x )(v,a)

ó
î
F Xt (y) − Ex f ( x )(v,a)

2 ò
ó
F Xt,v (y)
6 1.

By the properties of Xt given in Lemma 29, we have that
P( Xt,v ⊆ Xt+1 | Xt ) > 1 − e0 .
Thus,

Ã
ï î
 XX
Ey Ex f ( x )(v,a)
E
v∈ Fnd


ó
î
F Xt (y) − Ex f ( x )(v,a)

ó
F Xt,v (y)

2 ò

a∈Σ


Ã
ï î
 XX
6 ( 1 − e0 ) E 
Ey Ex f ( x )(v,a)
v∈ Fnd

(25)


ó

î

ó

F Xt (y) − Ex f ( x )(v,a)

F X t +1 ( y )

2 ò

a∈Σ


Ã
ï î
 XX
6 E
Ey Ex f ( x )(v,a)
v∈ Fnd


Xt 


X t  + e0

»

|Σ| Fnd


ó

î

F Xt (y) − Ex f ( x )(v,a)

a∈Σ

ó

F X t +1 ( y )

2 ò


X t  + e0

»

|Σ| Fnd .

From (24) and (25) we obtain


Ã
p
ï î
ò

ó
î
ó
X
X
X
2
|Σ|


D Xt 6 »
E
Xt 
(26)
Ey Ex f ( x )(v,a) F Xt (y) − Ex f ( x )(v,a) F Xt+1 (y)
d
2 Fn j∈[k]
v∈ Fnd a∈Σ
p
|Σ| X »
+ »
e0 |Σ| Fnd
2 Fnd j∈[k]


Ã
p
ï î
ò

ó
î
ó
X
X
2
k |Σ| 
 k | Σ | e0
= »
E
Ey Ex f ( x )(v,a) F Xt (y) − Ex f ( x )(v,a) F Xt+1 (y)
Xt  +
.
2
d
2 Fn
v∈ F d a∈Σ
n

»
Observe that viewing f as a random variable with respect to µn,d we have k f k2 =
Fnd . Note also that
Ã
2 ò
ó
î
ó
X X ï î


E [ f | F Xt ] − E f F Xt +1 2 =
Ey Ex f ( x )(v,a) F Xt (y) − Ex f ( x )(v,a) F Xt+1 (y)
.
v∈ Fnd a∈Σ

(27)

21

From (26) and (27) we obtain that for every t ∈ [m],
p
k |Σ| î
D Xt 6 »
E E [ f F Xt ] − E [ f
2 Fnd

F Xt +1 ]

ó k | Σ | e0
Xt +
.
2

2

(28)

Note that the probability that a random variable is greater or equal to its expectation is always strictly positive. Because Xt
takes only finitely many values, this means that for every t ∈ [m], for every realization of Xt , denoted as χt , there exists a
realization of Xt+1 , denoted as χt+1 = χt+1 (χt ) such that P ( Xt+1 = χt+1 | Xt ) > 0 and
ó
î




E E [ f | F Xt ] − E f F Xt +1 2 X t 6 E [ f | F χ t ] − E f F χ t +1 2 .
Together with (28) we obtain
Dχ t

p
k |Σ|
6 »
2 Fnd


E [ f | Fχt ] − E f

F χ t +1


2

+

k | Σ | e0
.
2

(29)

Since (29) holds for every t, we obtain that there exists a sequence (χt )t∈[m+1] of realizations of ( Xt )t∈[m+1] with positive
probabilities, such that for every t ∈ [m],
p


k |Σ|
k | Σ | e0
E [ f | F χ t ] − E f F χ t +1 2 +
.
(30)
Dχ t 6 »
2
2 Fnd
From Lemma 28, there exists t ∈ [m] such that

E [ f | Fχt ] − E f

F χ t +1



2
2

6

1
k f k22 .
m

(31)

Combining (31) with (30) we obtain that there exists t ∈ [m] such that
p
k |Σ| 1
k | Σ | e0
√ k f k2 +
Dχ t 6 »
2
m
2 Fnd
p
k | Σ | k | Σ | e0
= √ +
.
2
2 m
Taking A = χt , and recalling our choice of e0 =

e2
k|Σ|

and

√1
m

2

6 √e
k

|Σ|

, we obtain that

p
k | Σ | k | Σ | e0
DA 6 √ +
6 e2 ,
2
2 m
which completes the proof.
We have reached the main result of this section. We show that capacity of a convex d-axial product is arbitrarily close to
the independence entropy, as the dimension grows.
Theorem 34. Let k ∈ N, and let Γ ⊆ P (Σk ) be a convex one-dimensional SCS. Then
lim sup cap(Γ⊗d ) = hind (Γ).
d→∞

Proof: First note that lim supd→∞ cap(Γ⊗d ) > hind (Γ) by applying Theorem 26 to Γ⊗d for every d and taking d → ∞
on both sides. For the other direction, fix e0 > 0 and choose
™
ß
e
e0
0 < e < min
,1 ,
0<δ< .
2 log2 |Σ|
2
δ
δ
Replace Γ by Bδ (Γ) in Definition 31 and denote the resulting measures by µn,d
δ , µy,A , and ηy,A .
Recall that for a measure µ and a σ-algebra F ,
Z
H (µ | F ) , E [ H (µ (· | F ))] =
H (µ (· | F )) ( x )dµ( x ).

(32)

In other words, H (µ | F ) is the expected entropy of the conditional measure µ (· | F ). Also recall that for A ⊆ Fnd , π A (µδn,d )
denotes the A-marginal of µn,d
δ , and that F A denotes the σ-algebra generated by the coordinates in A. We have that
Ä
ä
n,d
n,d
H (µn,d
)
=
H
(
π
(
µ
))
+
H
µ
F
.
A
A
δ
δ
δ

22

d

By Proposition 33, for any n ∈ N, n > k + 2, there exists d0 ∈ N, such that for every d > d0 , there exists A ⊆ Σ Fn ,
| A| 6 end , such that,
Ä
ää
Ä
δ
d
µn,d
η
∈
P
(
B
(
B
(
Γ
)))
> 1 − e > 0.
n
e
δ
y,A
δ
Ä
ä
d
In particular, there exists a word y ∈ Σ Fn such that ηy,A ∈ P n (Be (Bδ (Γ)))d . Since clearly
A
H (π A (µn,d
,
δ )) 6 log2 Σ

by combining the above we have
Ä
n,d
H (µn,d
δ ) 6 H µδ

ä
F A + end log2 |Σ| .

(33)

Because the joint entropy of a finite set of random variables is bounded from above by the sum of their entropies (and the
same statement holds for conditional entropy), we have:
Ä
ä
ä
X Ä
n,d
H µn,d
F
6
H
π
(
µ
)
F
.
A
A
{
v
}
δ
δ
v∈ Fnd
δ
By definition of the random measure ηy,A
and from (32), we have
Ä
ä
Ä
ä
X
δ
H π{v} (µn,d
H π{v} (ηy,A
) µn,d
δ ) FA =
δ ( y ).
d

y∈Σ Fn

Thus,
Ä
ä
ä
X X
δ
H π{v} (ηy,A
) µn,d
FA 6
δ ( y ).

Ä
H µn,d
δ

v∈ Fnd y∈Σ Fnd

Now, since ηy,A is a product measure, we have
X

δ
H (ηy,A
)=

Ä
ä
δ
H π{v} (ηy,A
) .

v∈ Fnd

It follows that,
Ä
H µn,d
δ

ä
Ä
ä
X
δ
FA 6
H ηy,A
µn,d
δ ( y ).

(34)

d
y∈Σ Fn

Let us conveniently use p to denote the value
Ä
Ä
ää
δ
p , µn,d
ηy,A
∈ P n (Be (Bδ (Γ)))d ,
δ
and recall that p > 1 − e > 0. Then
X
δ
H (ηy,A
)µn,d
δ (y) 6 p ·
d
y∈Σ Fn

d

sup
η ∈P n ((Be (Bδ (Γ)))d )

H (η ) + (1 − p) · log2 Σ Fn .

Using the fact that p > 1 − e > 0 combined with (34) and (35), it follows that
Ä
ä
H (η ) + (1 − p)nd · log2 |Σ|
H µn,d
F
6 p·
sup
A
δ

d
η ∈P n ((Be (Bδ (Γ))) )

6

sup
η ∈P n ((Be (Bδ (Γ)))d )

(35)

(36)

H (η ) + end log2 |Σ| .

Combining (36) with (33) we obtain
1 Ä n,d ä
1
H µδ
6 d
d
n
n

sup
η ∈P n ((Be (Bδ (Γ)))d )

H (η ) + 2e log2 |Σ| .

By our choice of e, we have e + δ 6 e0 , hence (Be (Bδ (Γ)))⊗d ⊆ (Be0 (Γ))⊗d , as well as
1 Ä n,d ä
1
H µδ
6 d
sup
H ( η ) + e0 .
nd
n η ∈P (B (Γ))d
)
n(
e0
Since µδn,d is the uniform measure on Bn (Bδ (Γ)⊗d ),
⊗d
H (µn,d
δ ) = log2 Bn (Bδ ( Γ ) ) .

(37)

23

Thus,

ä
Ä
1
1
⊗d
6 d
log
B
(
B
(
Γ
))
n
δ
2
nd
n

H ( η ) + e0 .

sup
η ∈P n ((Be0 (Γ))d )

Taking lim supn→∞ we obtain
ä
Ä
1
” (Bδ (Γ))⊗d 6 lim sup d
cap
n
n→∞
Since
we have

H ( η ) + e0 .

sup
η ∈P n ((Be0 (Γ))d )

ä
Ä
Bδ Γ⊗d ⊆ (Bδ (Γ))⊗d ,
ä
ää
Ä
Ä Ä
1
” (Bδ (Γ))⊗d 6 lim sup d
” Bδ (Γ)⊗d 6 cap
cap
n
n→∞

Taking limδ→0+ , we get

ä
Ä
1
cap Γ⊗d 6 lim sup d
n
n→∞

H ( η ) + e0 .

sup
η ∈P n ((Be0 (Γ))d )

H ( η ) + e0 .

sup

(38)

η ∈P n ((Be0 (Γ))d )

At this point we take a slight detour. For ξ > 0, Be0 (Γ) ⊆ Bξ (Be0 (Γ)) and hence we have
lim sup
n→∞

1
nd

H (η ) + e0 6 lim sup lim sup

sup

ξ →0+

η ∈P n ((Be0 (Γ))d )

n→∞

1
nd

H ( η ) + e0

sup
η ∈P n ((Bξ (Be0 (Γ)))d )

( a)

Ä
ä
= hind (Be0 (Γ))d + e0

(b)

= hind ((Be0 (Γ))) + e0 ,

where ( a) follows by definition, and (b) follows by Lemma 27. Substituting this in (38) and taking d → ∞ we obtain
Ä
ä
lim sup cap Γ⊗d 6 hind ((Be0 (Γ))) + e0 .

(39)

d→∞

Note that since Γ is convex we have that for e1 > 0, Be1 (Be0 (Γ)) = Be1 +e0 (Γ). Therefore, by the definition of limit we have
lim sup lim sup lim sup
e0 → 0 +

e1 → 0 +

n→∞

1
n

sup

H (η ) = lim sup lim sup

η ∈P n ((Be1 (Be0 (Γ))))

e0 → 0 +

n→∞

1
n

sup

H ( η ).

η ∈P n ((Be0 (Γ)))

Therefore, taking the limit as e0 → 0 in (39) we obtain
Ä
ä
lim sup cap Γ⊗d 6 hind (Γ).
d→∞

VI. D ISCUSSION
Our initial motivation behind this work is to approximate the capacity of multidimensional SCSs using “meaningful”
expressions. The main challenges were defining exactly what is the capacity of multidimensional SCSs, and obtaining the
connections between the capacity and the independence entropy. Our approach, which uses the independence entropy, extends
previous combinatorial works [19], [23], [26], which apply only to fully constrained systems. At the core of our results, for
Γ ⊆ P (Σk ) and its axial product Γ⊗d , by Theorem 24 and Theorem 26 that
hind (Γ) 6 cap(Γ⊗d ).
Thus, the problem of bounding the capacity of a d-dimensional axial-product SCS is simplified by having to consider only
product measures, which are much easier to handle. Moreover, any number of dimensions d, may be reduced via this bound
to the one-dimensional case. This bound is asymptotically tight, as together with Theorem 34, for convex Γ,
lim sup cap(Γ⊗d ) = hind (Γ).
d→∞

It also appears that the capacity cap, and independence entropy hind , are robust generalizations of their one-dimensional
combinatorial counterparts.

24

cap(Γ)
(a)

(b)

” (Γ)
cap

hind (Γ)
(c)
h‘
ind ( Γ )
d

Figure 1: The Hasse diagram for a general d-dimensional SCS Γ ⊆ P (Σ Fk ), where (a) follows from (1), (b) follows from
Theorem 26, and (c) follows from (2).
cap(Γ)
” (Γ)
cap

cap(Γ⊗d )

(a)

(b)

(c)

(d)

” (Γ⊗d )
cap

hind (Γ) = hind (Γ⊗d ) = hind (Γd )
(e)
⊗d
h‘
ind ( Γ )

(f)
h‘
ind ( Γ )
Figure 2: The Hasse diagram for a convex one-dimensional Γ ⊆ P (Σk ) and its d-axial-product SCS Γ⊗d , where (a) and (d)
follow from (1), (b) and (c) follow from Theorem 26, (e) follows from (2), and (f) follows from Lemma 23.

The paper contains many connections between the various capacities and entropies. Figure 1 shows the Hasse diagram for
d
the bounds pertaining to general d-dimensional Γ ⊆ P (Σ Fk ). In the case of a convex one-dimensional Γ ⊆ P (Σk ) and its
d-axial-product SCS Γ⊗d , a more elaborate Hasse diagram emerges, which is shown in Figure 2.
We note here that following the same arguments used in the proof of Theorem 24 would show that cap(Γ⊗d ) > cap(Γ⊗d+1 )
which means that in lim supd→∞ cap(Γ⊗d ) the limit actually exists and equals to infd cap(Γ⊗d ).
We would also like to compare our results, as they apply to a specific case study described in [10]. Let Γ ⊆ P (Σk ) be a
convex one-dimensional SCS, and recall that the axial product Γ⊗d is defined as
n
o
d
Γ⊗d , µ ∈ P (Σ Fk ) : ∀i ∈ [d], π[k]ei (µ) ∈ Γ ,
and thus

o
Ä
ä n
[k]e
Bn Γ⊗d = w ∈ Fnd : ∀i ∈ [d], frw i ∈ Γ .

The SCSs studied in [10] were an averaged version of the axial product, namely,


d
1 X
π [ k ] ei ( µ ) ∈
Γd , µ ∈ P (Σ Fk ) :

d
i ∈[d]

and thus
Ä

ä

B n Γ d =





w ∈ Fnd

Γ







X
1
[k]e
:
frw i ∈ Γ .

d
i ∈[d]

,

25

By convexity, it easily follows that
ä
ä
Ä
Ä
B n Γ ⊗ d ⊆ B n Γ d ,
and thus

cap(Γ⊗d ) 6 cap(Γd ).

We now focus on the simple example known as the (0, k, p)-RLL SCS over the binary alphabet Σ = {0, 1}, which was the
case study of [10]. The one-dimensional (0, k, p)-RLL SCS, 0 6 p 6 1, is defined by
¶
©
Γk,p , µ ∈ P (Σk+1 ) : µ(1k+1 ) 6 p ,
(40)
where 1k+1 denotes the all-ones string of length k + 1. This example is a generalization of the well known inverted (0, k)-RLL
fully constrained system, since if we take p = 0 we obtain the inverted (0, k )-RLL. In [10], the authors found lower and upper
d
bounds on the internal capacity of Γ
k,p . We recall the relevant lower bound here.
Theorem 35. [10, Th. 20] Let Γk,p denote the one-dimensional (0, k, p)-RLL SCS given in (40). Then, for all 0 6 p 6

1
,
2k +1

d
” ( Γ
” ( Γ ) − 1) ,
cap
k,p ) > 1 + d (cap

whereas for all

1
2k +1

d
” ( Γ
6 p 6 1, cap
k,p ) = 1.

d
We first note that this theorem implies a lower bound on cap(Γ
k,p ),
d
d
” ( Γ
” ( Γ ) − 1) .
cap(Γ
k,p ) > cap
k,p ) > 1 + d (cap

The lower bound of [10] eventually becomes negative, as the dimension d grows, and therefore, degenerate. However, using
the results of this paper,
d
‘
cap(Γ
k,p ) > hind ( Γk,p ),
and this bound does not depend on the dimension, and therefore, does not degenerate. We provide an explicit numerical
example:
Example 36. Let us take k = 2, and p = 0.05, meaning that we restrict the frequency of the pattern 111 to be at most 0.05. Fix
d
” (Γk,p ). The latter can be calculated by solving an optimization problem
d = 3. The lower bound on cap(Γ
k,p ) from [10] uses cap
” (Γk,p ) ≈ 0.976 which means that
using a computer. We obtain that cap
d
cap(Γ
k,p ) > 1 + 3 · (0.976 − 1) ≈ 0.928.

d
Using the results of this paper, we use h‘
ind ( Γk,p ) as a lower bound to cap( Γk,p ). Finding the supremum involved in the definition
of h‘
ind ( Γk,p ) is also not easy, and we lower bound it by guessing a specific measure. We take each coordinate to be i.i.d. Bernoulli
√
3
0.05, and we get
√
3
d
‘
cap(Γ
k,p ) > hind ( Γk,p ) > H2 ( 0.05) ≈ 0.949,

” (Γ0 ) 6 0.983. We further mention that the
which is a better lower bound than that of [10]. Note that the upper bound gives cap
lower bound of [10] gets increasingly worse as the dimension grows. For example, when d = 10 we obtain by Theorem 35 that
d
d
cap(Γ
k,p ) > 0.76 whereas using the independence entropy, the bound stays the same, i.e., cap( Γ ) > 0.949. Finally, for all
d > 42, the lower bound of [10] becomes degenerate.
2
We present another example for (0, 1, p) with a more elaborate lower bound.
Example 37. Take k = 1 and consider Γk,p . From the results of this paper,
d
⊗d
‘
lim sup cap(Γ
1,p ) > lim sup cap( Γ1,p ) = hind ( Γ1,p ) > hind ( Γ1,p ).
d→∞

d→∞

2n
We lower bound h‘
ind ( Γ1,p ) by devising a product measure µ2n ∈ (P ( Σ )) , for all n ∈ N. The measures use two parameters
0 6 x, y 6 1, using a Bernoulli( x ) distribution for positions with odd indices, and a Bernoulli(y) for positions with even
indices. Thus,
ß
™
1
1
h‘
(
Γ
)
>
max
H
(
µ
)
=
max
(
H
(
x
)
+
H
(
y
))
:
0
6
x,
y
6
1,
xy
6
p
.
2n
2
2
ind 1,p
x,y 2n
2
Due to monotonicity, the maximization problem always has a solution on the curve xy = p, which in the high range is unique√x =
√
y = p, and in the lower range has two symmetric solutions. For example, for p = 0.2 the optimal solution is x = y = 0.2.
However, for p = 0.01, the first optimal solution is x ≈ 0.454, y ≈ 0.022, and the symmetric solution is x ≈ 0.022, y ≈ 0.454.
This is depicted in Figure 3.
1
d
We note that this bound agrees with the solution for the fully constrained case, lim supd→∞ cap(Γ
k,0 ) = 2 which was solved
in [23]. We conjecture that Figure 3(a) indeed shows the exact limiting capacity.
2

26

y

0.5

maxx,y

p = 0.2

0.4

1
2n H ( µ2n )

1.0

0.3

0.9
0.8
0.7

0.2

p = 0.1

0.1

p = 0.05

0.0

p = 0.01
x

0.6
p

0.00

0.05

0.10

0.15

0.20

0.0

0.25

0.1

0.2

(a)

0.3

0.4

0.5

(b)
d
lim supd→∞ cap(Γ
1,p )

is shown in (a), where (b) shows a contour plot of 21 ( H2 ( x ) + H2 (y)) as
Figure 3: A lower bound on
well as the curves xy = p for p = 0.01, 0.05, 0.1, 0.2.

A PPENDIX A
C YCLIC AND N ON - CYCLIC C APACITIES
The goal of this appendix is to show that the capacity, as we defined it cyclically, equals the (traditionally non-cyclic)
capacity in the case of fully constrained systems.
d

Definition 38. Let d, k ∈ N. A (traditional) fully constrained system is a set Φ ⊆ Σ Fk of d-dimensional words, called forbidden
d
patterns. The set of all admissible words in Σ Fn is defined as
n
o
d
Bncom (Φ) , x ∈ Σ Fn : ∀v ∈ Fnd−k , xv+ Fd ∈
/Φ .
k

The (combinatorial) capacity of Φ is defined by
capcom (Φ) , lim sup
n→∞

1
log2 |Bncom (Φ)| .
| Fnd |
2

Intuitively, a traditional fully constrained system is a set of words that do not contain any forbidden pattern non-cyclically.
d
Given a (traditional) fully constrained system Φ ⊆ Σ Fk , we can construct a set of measures ΓΦ defined as follows,
n
o
d
d
ΓΦ , µ ∈ P (Σ Fk ) : µ(Σ Fk \ Φ) = 1 .
(41)
Thus, ΓΦ is a SCS which is fully constrained in the sense of Definition 10. Since Definition 10 is more restrictive, by requiring
forbidden patterns to not appear in admissible words cyclically, we immediately have

Bn (ΓΦ ) ⊆ Bncom (Φ),
implying also
” (ΓΦ ) 6 capcom (Φ).
cap
However, we now prove that the capacity of ΓΦ does equal the (combinatorial) capacity of Φ.
d

d

Proposition 39 Let d, k ∈ N. Let Φ ⊆ Σ Fk be a fully constrained system as in Definition 38, and let ΓΦ ⊆ P (Σ Fk ) be its
corresponding fully constrained system as in Definition 10. If Bncom (Φ) 6= ∅ for all large enough n ∈ N, then
cap(ΓΦ ) = capcom (Φ).
Proof: We first show that capcom (Φ) 6 cap(ΓΦ ). Fix e > 0, and for n ∈ N, n > k, consider the k-boundary of Fnd which
is defined as Fnd \ Fnd−k . Note that | Fnd \ Fnd−k | = nd − (n − k)d . Let w ∈ Bncom (Φ). While w does not contain any forbidden
pattern when considering the coordinates non-cyclically, it may contain some when considering the coordinates cyclically. The

27

number of occurrences of forbidden patterns (cyclically) in w is at most | Fnd \ Fnd−k | = nd − (n − k )d . For all large enough n
we have

nd −(n−k )d
nd

6 e, hence
Bncom (Φ) ⊆ Bn (Be (ΓΦ )).

Thus, for every e > 0,
” (Be (ΓΦ )).
capcom (Φ) 6 cap
Taking the limit as e → 0 we obtain
capcom (Φ) 6 cap(ΓΦ ).
In the other direction, we now show that cap(ΓΦ ) 6 capcom (Φ). Let δ0 > 0 and take n0 ∈ N large enough such that
1
1
log2 Bncom
(Φ) 6 capcom (Φ) + δ0 .
0
d
3
n0
Denote the number of forbidden patterns by t , |Φ|. Take δ > 0 small enough such that both
Å
ã
t (1 + δ )
δ
1
1
6 δ0 ,
and
tδ log2 |Σ| 6 δ0 ,
H2
d
1+δ
3
3
n0
where H2 (·) is the binary entropy function. Finally, for every n > n0 , denote m , bn/n0 c, and choose any 0 < e 6 δ/n0d .
Consider a word w ∈ Bn (Be (ΓΦ )). We say w is made up a concatenation of md Fnd0 -blocks, namely, a block is a set of
d . By our choice of parameters,
positions n0 v + Fnd0 , where v ∈ Fmd , as well a boundary, namely, the set of positions Fnd \ Fmn
0
the number of occurrences (perhaps cyclically) of any forbidden pattern from Φ is at most
e| Fnd | 6 e(m + 1)d n0d 6 δ(m + 1)d .
This serves also as an upper bound on the number of blocks fully containing (non-cyclically) this forbidden pattern. Since
there are t forbidden patterns, the number of blocks that are devoid (non-cyclically) of any forbidden pattern, is at least
( Φ ).
md − tδ(m + 1)d . Such blocks are in fact words from Bncom
0
Fixing a specific type of forbidden pattern, and considering each occurrence of it as a ball, we have at most δ(m + 1)d
balls, which we throw into md + 1 bins (md blocks, and another “virtual” bin for patterns that are not fully contained within
m d +1+ δ ( m +1) d
a single block). The total number of ways to throw these ball into bins is exactly ( δ(m+1)d ). Raising this to the power
of t gives an upper bound on the number of ways the t forbidden patterns are dispersed among the blocks. In total we have,
Ç

|Bn (Be (ΓΦ ))| 6

m d + 1 + δ ( m + 1) d
δ ( m + 1) d

åt

Bncom
(Φ)
0

m d − t ( m +1) d δ

|Σ|tδ(m+1)

d nd
0

|Σ|n

d −( mn

0)

d

,

where the binomial coefficient follows from upper bounding the way forbidden patterns are dispersed among blocks, the
following term counts the number of ways to fill blocks that do not contain (non-cyclically) any forbidden word, and the last
term counts the ways to arbitrarily fill in the rest of the positions. Thus,
1
log2 |Bn (Be (ΓΦ ))|
d
n→∞ n
Å
ã
t (1 + δ )
δ
1
6
(Φ) + tδ log2 |Σ|
H2
+ d log2 Bncom
0
d
1
+
δ
n0
n0
6 δ0 + capcom (Φ).

” (Be (ΓΦ )) = lim sup
cap

Taking the limit as e → 0, we get
cap(ΓΦ ) 6 δ0 + capcom (Φ).
Finally, since this holds for any δ0 > 0, we get the desired result,
cap(ΓΦ ) 6 capcom (Φ).

28

A PPENDIX B
I NDEPENDENCE E NTROPY FOR F ULLY C ONSTRAINED S YSTEMS
Here we Prove Theorem 22. We begin by recalling relevant definitions from [19]. A Zd shift space X, is a subset X ⊆ ΣZ
that is closed under shifts, i.e., for all v ∈ Zd , and all x ∈ X, σv ( x ) ∈ X.

d

d

Definition 40. Let d, k ∈ N. Given a set of forbidden words Φ ⊆ Σ Fk , the Zd shift space over Σ defined by Φ is
n
o
d
XΦ , x ∈ Σ Z : ∀ v ∈ Zd , x v + F d ∈
/Φ .
k

2
Given a finite alphabet Σ, let Σ̃ denote the set of all non-empty subset of Σ, i.e.,
Σ̃ , { A ⊆ Σ : A 6= ∅} .
Definition 41. Let d ∈ N, S ⊆ Zd , and let x̃ be a configuration on S over Σ̃, i.e., x̃ ∈ Σ̃S . Denote by ϕ( x̃ ) the set of fillings of x̃,
¶
©
ϕ( x̃ ) , x ∈ ΣS : ∀v ∈ S, x{v} ∈ x̃{v} .
2
Definition 42. Let d ∈ N, and let X be a

Zd

shift space over Σ. We denote by X̃ the multi-choice shift space corresponding to X,
n
o
d
X̃ , x̃ ∈ Σ̃Z : ϕ( x̃ ) ⊆ X .

We also denote by Bn ( X̃ ) the set of all eligible configurations on Fnd in X̃, i.e.,
¶
©
Bn ( X̃ ) , x̃ Fd : x̃ ∈ X̃ .
n

2
Definition 43. Let d ∈ N, and let X be a
hcom
ind ( X ), by

Zd

shift space. We define the combinatorial independence entropy of X, denoted as

hcom
ind ( X ) , lim sup
n→∞


1
max log2 | ϕ(w̃)| : w̃ ∈ Bn ( X̃ ) .
d
n
2

Note that in [19] the definition of combinatorial independence entropy is slightly more general and defined over all shapes
n
and not only on the shapes Fnd . Finally, given a fully constrained system Φ ⊆ Σ Fk (see Definition 38), its representation as a
SCS is given by ΓΦ in (41). We are now ready to prove Theorem 22.
d
Proof of Theorem 22: Let d, k ∈ N, and let Φ ⊆ Σ Fk be a fully constrained system, with its SCS representation ΓΦ
from (41). The claim we want to prove is that
hcom
ind ( XΦ ) = hind ( ΓΦ ).
First, we show that hcom
ind ( XΦ ) 6 hind ( ΓΦ ). For every n ∈ N choose w̃n ∈ Bn ( X̃Φ ) which maximizes | ϕ ( w̃n )|. Now
consider the independent measures µn such that π{v} (µn ) is the uniform distribution over (w̃n ){v} . Note that in Bn ( X̃ ), the
forbidden patterns are considered without modulo while in Bn (ΓΦ ) the calculation of the marginals’ average uses modulo n.
Therefore, if a filling ϕ(w̃n ) belongs to XΦ , in µn there is perhaps a positive probability to see a forbidden pattern only in
the boundaries. In Fnd , the k-boundary is the set Fnd \ Fnd−k of size nd − (n − k)d . Since (nd − (n − k)d )/nd → 0 as n → ∞,
we obtain that for every e > 0, for every n ∈ N such that (nd − (n − k )d )/nd 6 e, we have that µn ∈ Be (ΓΦ ). Thus,
h‘
ind (Be ( ΓΦ )) = lim sup
n→∞

sup
µ∈P n (Be (ΓΦ ))

1
H (µ)
nd

1
H (µn )
d
n→∞ n
1
= lim sup d log2 | ϕ(w̃n )|
n
n→∞
= hcom
ind ( XΦ ).

> lim sup

Taking e → 0 we obtain
hind (ΓΦ ) > hcom
ind ( XΦ ).

29

1
We now show that hind (ΓΦ ) 6 hcom
ind ( XΦ ). Fix δ > 0 and take δ1 > 0 small enough such that δ1 < 3 δ. Take n0 ∈ N large
enough such that for all n > n0 ,
1
1
max {log2 | ϕ(w̃)|} 6 hcom
(42)
ind ( XΦ ) + 3 δ.
nd w̃∈Bn (X̃Φ )

We now take e > 0 small enough such that all the following hold,
q
q
1
1
1
kd
kd
n0d e 4 < δ,
− |Σ| n0d e 4 log2
3
1
d 34
2 e log2 |Σ| < δ1 ,
2
1
‘
δ .
hind (Be (ΓΦ )) − hind (ΓΦ ) 6
16 1
By the definition of h‘
ind (Be ( ΓΦ )) we may find n > n0 large enough such that all the following hold,
Å
ã

n 0 d
1
2 1− 1−
log2 |Σ| 6 δ1 ,
n
4
sup
µ∈P n (Be (ΓΦ ))

(43)
(44)

(45)

1
1
H (µ) − hind (ΓΦ ) 6 δ1 ,
8
nd

and there exists µ ∈ P n (Be (ΓΦ )) for which
1
1
H (µ) − hind (ΓΦ ) 6 δ1 .
4
nd
Since µ ∈ P n (Be (ΓΦ )), we have

1 X
π Fd +v (µ)(Φ) 6 e.
k
nd
d
v∈ Fn

¶
©
Denote m , bn/n0 c. We now partition Fnd into md blocks of shape Fnd0 in the natural way, n0 v + Fnd0 : v ∈ Fmd , as well
d . Note that
as a boundary Fnd \ Fmn
0
O
µ∼
π n v + F d ( µ ) ⊗ π F d \ F d ( µ ).
=
0

n0

d
v∈ Fm

n

mn0

Since µ is independent we obtain
1
1
1
1
H (π Fd (µ)) − hind (ΓΦ ) 6
H (π Fd (µ)) − d H (µ) + d H (µ) − hind (ΓΦ )
d
d
mn
mn
(mn0 )
(mn0 )
n
n
0
0
Å
ã
d − ( mn )d
1
1
n
1
0
6 (mn0 )d
− d log2 |Σ| +
log2 |Σ| + δ1
d
d
4
(mn0 )
n
n
nd − (mn0 )d
1
62
log2 |Σ| + δ1
d
4
Å n
ã
n 0 d
1
6 2 1− 1−
log2 |Σ| + δ1
n
4
1
6 δ1 ,
2
where the last inequality holds due to (45). Let Z : Fmd → R be a function defined by
1 X
Z (v) , d
π Fd +n v+u (µ)(Φ)
0
k
n0
d
u∈ Fn

0

(with coordinates taken modulo n). Note that since µ ∈ P n (Be (ΓΦ )), we have
1 X
π Fd +v (µ)(Φ) 6 e.
k
nd
d
v∈ Fn

If we now take v to be random uniformly distributed in Fmd , then
Å
ã
1 X 1 X
1 d
E[ Z (v)] = d
π Fd +n v+u (µ)(Φ) 6 1 +
e.
0
m
k
m
n0d
d
d
v∈ Fm

u∈ Fn

0

(46)

30

By Markov’s inequality we have
ã
Å


1
1
1 d 3
Pr Z (v) > e 4 6 e− 4 E[ Z (v)] 6 1 +
e4.
m

(47)

Recall that each v ∈ Fmd may be identified with the Fnd0 block of Fnd in coordinates n0 v + Fnd0 . Define,
o
n
1
L , v ∈ Fmd : Z (v) > e 4 .
Since v was distributed uniformly in Fmd , by (47) we have,
3

|L| 6 (m + 1)d e 4 .

(48)

It now follows that
1
(mn0 )d

X
d \L
v∈ Fm

H (πn

d
0 v + Fn0

(µ)) =

X
1
1
H (π Fd (µ)) −
H (πn v+ Fd (µ))
d
d
0
mn
n0
(mn0 )
(mn0 )
0
v∈L

( a)

X
1
1
H (πn v+ Fd (µ))
> hind (ΓΦ ) − δ1 −
d
0
n0
2
(mn0 ) v∈L
3

(m + 1)d e 4 n0d
1
> hind (ΓΦ ) − δ1 −
log2 |Σ|
2
(mn0 )d
3
1
> hind (ΓΦ ) − δ1 − 2d e 4 log2 |Σ|
2
(b)

(c)

> hind (ΓΦ ) − δ1
1
> hind (ΓΦ ) − δ,
3

where ( a) follows from (46), (b) follows from (48), and (c) follows from (44). Since there are at most md summands on the
left-hand side, there exists v0 ∈ Fmd \ L such that
1
1
H (πn v + Fd (µ)) > hind (ΓΦ ) − δ.
0 0
n0
3
n0d

(49)

We denote by ν the independent measure ν , π Fd +n v (µ).
0 0
n0
Note that if we consider ν in a non-cyclic manner, we obtain that
1
( n0 − k + 1) d

X

πu+ Fd (ν)(Φ) 6

u∈ Fnd −k+1
0

and in particular, for every coordinate u ∈ Fnd

0 − k +1

k

n0d
1
e4,
d
( n0 − k + 1)
1

, we have that πu+ Fd (ν)(Φ) 6 n0d e 4 . Let us define
k
q
1
kd
p,
n0d e 4 .

Hence, since ν is an independent measure, if a ∈ Φ then there must be a coordinate t ∈ Fkd for which πu+t (ν)( at ) 6 p.
We now construct a configuration w̃ ∈ Σ̃

Fnd

. For every coordinate u ∈ Fnd0 we take
¶
©
w̃u = a ∈ Σ : π{u} (ν)( a) > p .
0

By our previous observation, w̃ ∈ Bn0 ( X̃Φ ) since any filling of w̃ cannot contain a forbidden word from Φ as it requires at
least one position u such that π{u} (ν) 6 p. Moreover,
X
log2 |w̃u | > −
π{u} (ν)( a) log2 (π{u} (ν)( a))
a∈w̃u

= H (π{u} (ν)) +

X

π{u} (ν)( a) log2 (π{u} (ν)( a))

a∈Σ\w̃u

> H (π{u} (ν)) + |Σ| p log2 p
1
> H (π{u} (ν)) − δ
3

31

where the last inequality follows from (43). Hence, using (49),
1
1 X
2
1 X
1
log2 | ϕ(w̃)| = d
log2 |w̃u | = d
H (π{u} (ν)) − δ > hind (ΓΦ ) − δ.
d
3
3
n0
n0
n
0
d
d
u∈ Fn

u∈ Fn

0

0

Finally, using (42), this implies that,
hcom
ind ( XΦ ) >

1
n0d

1
{log2 | ϕ(w̃)|} − δ > hind (ΓΦ ) − δ.
3
w̃∈Bn0 ( X̃Φ )
max

Since this holds for every δ > 0 we have hind (ΓΦ ) 6 hcom
ind ( XΦ ), as claimed.
R EFERENCES
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[10]
[11]
[12]
[13]
[14]
[15]
[16]
[17]
[18]
[19]
[20]
[21]
[22]
[23]
[24]
[25]
[26]
[27]
[28]
[29]
[30]
[31]
[32]
[33]
[34]

R. J. Baxter, “Hard hexagons: exact solution,” J. Phys. A: Math. Gen., vol. 13, pp. L61–L70, 1980.
R. Berger, “The undecidability of the domino problem,” Mem. Amer. Math. Soc. No., vol. 66, p. 72, 1966.
N. Calkin and H. Wilf, “The number of independent sets in the grid graph,” SIAM J. Discrete Math., vol. 11, pp. 54–60, 1998.
J.-R. Chazottes, J.-M. Gambaudo, M. Hochman, and E. Ugalde, “On the finite-dimensional marginals of shift-invariant measures,” Ergodic Theory Dyn.
Syst., vol. 32, no. 5, pp. 1485–1500, 2012.
Y. M. Chee, J. Chrisnata, H. M. Kiah, S. Ling, T. T. Nguyen, and V. K. Vu, “Efficient encoding/decoding of capacity-achieving constant-composition
ICI-free codes,” in Proceedings of the 2016 IEEE International Symposium on Information Theory (ISIT2016), Barcelona, Spain, Jul. 2016, pp. 205–209.
——, “Rates of constant-composition codes that mitigate intercell interference,” in Proceedings of the 2016 IEEE International Symposium on Information
Theory (ISIT2016), Barcelona, Spain, Jul. 2016, pp. 200–204.
A. Dembo and O. Zeitouni, Large Deviations Techniques and Applications. New York: Springer, 1998.
P. Diaconis and D. Freedman, “Finite exchangeable sequences,” The Annals of Probability, pp. 745–764, 1980.
O. Elishco, T. Meyerovitch, and M. Schwartz, “Encoding semiconstrained systems,” in Proceedings of the 2016 IEEE International Symposium on
Information Theory (ISIT2016), Barcelona, Spain, Jul. 2016, pp. 395–399.
——, “Semiconstrained systems,” IEEE Trans. Inform. Theory, vol. 62, no. 4, pp. 811–824, Apr. 2016.
S. Halevy, J. Chen, R. M. Roth, P. H. Siegel, and J. K. Wolf, “Improved bit-stuffing bounds on two-dimensional constraints,” IEEE Trans. Inform. Theory,
vol. 50, no. 5, pp. 824–838, May 2004.
H. Ito, A. Kato, Z. Nagy, and K. Zeger, “Zero capacity region of multidimensional run length constraints,” Elec. J. of Comb., vol. 6, 1999.
R. Karabed, D. Neuhoff, and A. Khayrallah, “The capacity of costly noiseless channels,” IBM Research Report, Tech. Rep. RJ 6040 (59639), Jan. 1988.
A. Kato and K. Zeger, “On the capacity of two-dimensional run-length constrained channels,” IEEE Trans. Inform. Theory, vol. 45, pp. 1527–1540, Jul.
1999.
S. Kayser and P. H. Siegel, “Constructions for constant-weight ICI-free codes,” in Proceedings of the 2014 IEEE International Symposium on Information
Theory (ISIT2014), Honolulu, HI, USA, Jul. 2014, pp. 1431–1435.
A. S. Khayrallah and D. L. Neuhoff, “Coding for channels with cost constraints,” IEEE Trans. Inform. Theory, vol. 42, no. 3, pp. 854–867, 1996.
O. F. Kurmaev, “Constant-weight and constant-charge binary run-length limited codes,” IEEE Trans. Inform. Theory, vol. 57, no. 7, pp. 4497–4515, Jul.
2011.
E. H. Lieb, “Residual entropy of square ice,” Physical Review, vol. 162, no. 1, pp. 162–172, 1967.
E. Louidor, B. Marcus, and R. Pavlov, “Independence entropy of Zd -shift spaces,” Acta Applicandae Mathematicae, vol. 126, no. 1, pp. 297–317, 2013.
E. Louidor and B. H. Marcus, “Improved lower bounds on capacities of symmetric 2D constraints using Rayleigh quotients,” IEEE Trans. Inform. Theory,
vol. 56, no. 4, pp. 1624–1639, Apr. 2010.
L. Lovász and B. Szegedy, “Szemerédi’s lemma for the analyst,” GAFA Geometric And Functional Analysis, vol. 17, no. 1, pp. 252–270, Apr 2007.
[Online]. Available: https://doi.org/10.1007/s00039-007-0599-6
B. H. Marcus and R. M. Roth, “Improved Gilbert-Varshamov bound for constrained systems,” IEEE Trans. Inform. Theory, vol. 38, no. 4, pp. 1213–1221,
1992.
T. Meyerovitch and R. Pavlov, “On independence and entropy for high-dimensional isotropic subshifts,” Proceedings of the London Mathematical Society,
vol. 109, no. 4, pp. 921–945, 2014.
Z. Nagy and K. Zeger, “Capacity bounds for the three-dimensional (0, 1) run length limited channel,” IEEE Trans. Inform. Theory, vol. 46, no. 3, pp.
1030–1033, May 2000.
E. Ordentlich and R. M. Roth, “Independent sets in regular hypergraphs and multi-dimensional runlength-limited constraints,” SIAM J. Discrete Math.,
vol. 17, no. 4, pp. 615–623, 2004.
T. L. Poo, P. Chaichanavong, and B. Marcus, “Tradeoff functions for constrained systems with unconstrained positions,” IEEE Trans. Inform. Theory,
vol. 52, no. 4, pp. 1425–1449, Apr. 2006.
M. Qin, E. Yaakobi, and P. H. Siegel, “Constrained codes that mitigate inter-cell interference in read/write cycles for flash memories,” IEEE J. Select. Areas
Commun., vol. 32, no. 5, pp. 836–846, May 2014.
M. Schwartz and J. Bruck, “Constrained codes as networks of relations,” IEEE Trans. Inform. Theory, vol. 54, no. 5, pp. 2179–2195, May 2008.
M. Schwartz and A. Vardy, “New bounds on the capacity of multidimensional run-length constraints,” IEEE Trans. Inform. Theory, vol. 57, no. 7, pp.
4373–4382, Jul. 2011.
A. Shafarenko, A. Skidin, and S. K. Turitsyn, “Weakly-constrained codes for suppression of patterning effects in digital communications,” IEEE
Trans. Communications, vol. 58, no. 10, pp. 2845–2854, Oct. 2010.
A. Shafarenko, K. S. Turitsyn, and S. K. Turitsyn, “Information-theory analysis of skewed coding for suppression of pattern-dependent errors in digital
communications,” IEEE Trans. Communications, vol. 55, no. 2, pp. 237–241, Feb. 2007.
A. Sharov and R. M. Roth, “Two-dimensional constrained coding based on tiling,” IEEE Trans. Inform. Theory, vol. 56, no. 4, pp. 1800–1807, Apr.
2010.
P. H. Siegel and J. K. Wolf, “Bit-stuffing bounds on the capacity of 2-dimensional constrained arrays,” in Proceedings of the 1998 IEEE International
Symposium on Information Theory (ISIT1998), Cambridge, MA, USA, Aug. 1998, p. 323.
I. Tal and R. M. Roth, “Bounds on the rate of 2-D bit-stuffing encoders,” IEEE Trans. Inform. Theory, vol. 56, no. 6, pp. 2561–2567, Jun. 2010.

