# Sand Piles Models of Signed Partitions withd Piles

Authors: C. Bisi; G. Chiaselotti; P. A. Oliverio
Journal: ISRN Combinatorics
 (2013)

---

## Abstract

Letr,d≤n   be nonnegative integers. In this paper we study the basic properties of a discrete dynamical model of signed integer partitions that we denote by S(n,d,r). A generic element of this model is a signed integer partition with exactly  d all distinct nonzero parts, whose maximum positive summand is not exceeding r and whose minimum negative summand is not less than -(n-r). In particular, we determine the covering relations, the rank function, and the parallel convergence time from the bottom to the top of S(n,d,r) by using an abstract Sand Piles Model with three evolution rules. The lattice S(n,d,r) was introduced by the first two authors in order to study some combinatorial extremal sum problems.


---

## Body

## 1. Introduction

Discrete dynamical models whose configurations are integer partitions are also called Sand Piles Models and they have been deeply investigated. In these models an integer partition is treated as a sequence of piles of grains of sand and each singular grain as a single integer unit. An evolution rule in these models is a rule which describes how to move some particular grains of a configuration in order to obtain another configuration. The famous Brylawski paper [1] can be considered the first implicit study of an integer partitions lattice by means of two evolution dynamical rules which determine the covering relations of this lattice. In [1] Brylawski proposed a dynamical approach to study the lattice LB(n) of all the partitions of a fixed positive integer n with the dominance order.However, the explicit identification of a specific set of integer partitions with a Sand Piles Model begins in [2, 3].In the Sand Piles Model introduced by Goles and Kiwi in [3], denoted by SPM(n), a sand pile is represented by an ordered partition of an integer n, that is, a decreasing sequence a=(a1,…,an) having sum n, and the movement of a sand grain respects the following rule.Rule (vertical rule).
One grain can move from a column to the next one if the difference of height of these two columns is greater than or equal to 2.In the modelLB(n) (introduced by Brylawski, 1973 [1]), the movement of a sand grain respects Rule 1 and Rule 2, which is described as follows.Rule (horizontal rule).
If a column containingp+1 grains, is followed by a sequence of columns containing p grains and then one column containing p-1 grains, one grain of the first column can slip to the last one.The Sand Piles ModelSPM(n) is a special case of the more general Chip Firing Game (CFG), which was introduced by Spencer in [4] to study some “balancing game”. There are a lot of specializations and extensions of this model which have been introduced and studied under different names, different aspects and different approaches. The SPM(n) can be also related to the Self-Organized Criticality (SOC) system introduced by Bak et al. in [5]. The study of such systems have been developed in an algebraic context ([6]), in a combinatorial games theory setting ([3, 7, 8]) and in the theory of cellular automata [9, 10].In the papers [8, 11–20], several dynamical models related to SPM(n) have been studied. Almost all systems studied in the previous works have a linear topology and they have extended the classical models SPM(n) and LB(n) to obtain more general models. An excellent survey on these topics is [21].Let nowr and d be non-negative integers less or equal than n and [n] the n-set {1,…,n}. In [22] the authors have introduced and studied a poset (S(n,r),⊑) related to some extremal combinatorial sums problems (see also [23–26] for studies on these problems). Such a poset can be seen as a lattice of particular integer partitions with all distinct summands which can be positive or negative, whose maximum positive summand is not exceeding r and whose minimum negative summand is not less than -(n-r). Such a poset is an involution poset; that is, it has an involution map that gives it some special symmetric properties, and it is also a lattice isomorphic (as noted in [27]) to the direct product M(r)×M(n-r)*, where M(n) is the lattice introduced by Stanley, [28], in order to solve an Erdös and Moser conjecture (here we denote by M(n,r)* the dual lattice of M(n-r)). The structure of M(n) is well known. For example, since M(n) is Peck, it follows that S(n,r) is Peck by [29]. This lattice contains an interesting sublattice (S(n,d,r),⊑) that is the set of all the integer partitions of S(n,r) having exactly d non-zero summands. Also this sublattice has been introduced in [22] and its structure at present is incompletely understood. For example, we know that it is a graded poset because it is a finite distributive lattice, but its rank function is unknown. In [30] Andrews introduced the concept of signed partition: a signed partition is a finite sequence of integers λk,…,λ1,λ-1,…,λ-l such that λk≥⋯≥λ1>0>λ-1≥⋯≥λ-l. In [30, 31] the signed partitions are studied from an arithmetical point of view.In this paper we study the latticeS(n,d,r) as a Sand Piles Model of signed integer partitions with three evolution rules. The first of these rules is an outside adjunction rule on the “positive” piles. The second rule is a switching rule between “negative” piles and “positive” piles which allows to maintain constant the number of the piles. The third rule is an outside elimination rule on the negative “piles”. We prove that the covering relation in the lattice S(n,d,r) is uniquely determined from the three previous rules. The paper is articulated as follows. In Section 1 we recall some basic definitions and preliminary results, for example, the definition of S(n,d,r) and some of its properties. In Section 2 we explain how to see the signed partitions of S(n,d,r) as configurations of our Sand Piles Model and also we describe its evolution rules. In Section 3 we prove (Theorem 3) that the covering relation in the lattice S(n,d,r) is uniquely determined by three evolution rules of our Sand Piles Model. We determine the rank function of S(n,d,r) and we compute the rank of S(n,d,r), that is, the sequential convergence time from the minimum to the maximum in S(n,d,r). Finally, in Section 4 we give some estimates for the parallel convergence time in our model.


## 2. Definitions and Preliminary Results

If(X,≤) is a poset and x,y∈X, we write y⋗x (or x⋖y) if y covers x. Now we briefly recall the definition of the lattice S(n,r) that we have introduced in [22] in a more formal context. In this paper we always denote with n and r two fixed non-negative integers such that r≤n. We call (n,r)-string an n-pla of integers
(1)ar…a1∣b1…bn-r,
such that(i)
a1,…,ar∈{1,…,r,0};(ii)
b1,…,bn-r∈{-1,…,-(n-r),0};(iii)
ar≥⋯≥a1≥0≥b1≥⋯≥bn-r;(iv)
the unique element in (1) which can be repeated is 0.Ifw is a (n,r)-string, we call parts of w the integers ar,…,a1,b1…bn-r, non-negative parts of w the integers ar,…,a1 and non-positive parts of w the integers b1…bn-r. We set ∑‍(w):=∑i=1r‍ai+∑j=1n-r‍bj, and if m∈ℤ is such that ∑‍(w)=m, we say that w is a signed partitions of m; in this case we write w⊢m. We set w+=ar…a1∣ and w-=∣b1…bn-r. Also, we denote by |w|> the number of parts of w that are strictly positive, with |w|< the number of parts of w that are strictly negative and we set ||w||=|w|>+|w|<. S(n,r) is the set of all the (n,r)-strings. If w=ar…a1∣b1…bn-r and w′=ar′…a1′∣b1′…bn-r′ are two (n,r)-strings, we set w+=w+′ if ai′=ai for all i=r,…,1, w-=w-′ if bj′=bj for all j=1,…,n-r and w=w′ if w+=w+′ and w-=w-′. On S(n,r) we consider the partial order on the components, that we denote by ⊑. To simplify the notations, in all the numerical examples the integers on the right of the vertical bar | will be written without minus sign. Since (S(n,r),⊑) is a finite distributive lattice it is also graded, with minimum element 0⋯0∣12⋯(n-r) and maximum element r(r-1)⋯21∣0⋯0.We recall now the concept of involution poset (see [32, 33] for some recent studies on such class of posets). An involution poset (IP) is a poset (X,≤,c) with a unary operation c:x∈X↦xc∈X, such that  (I1)
(xc)c=x, for all x∈X;(I2)
ifx,y∈X and if x≤y, then yc≤xc.The mapc is called complementation of X and xc the complement of x. Let us observe that if X is an involution poset, by (I1) follows that c is bijective and by (I1) and (I2) it holds that if x,y∈X are such that x<y, then yc<xc. If (X,≤,c) is an involution poset and if Z⊆X, we will set Zc={zc:z∈Z}. We note that if X is an involution poset then X is a self-dual poset because from (I1) and (I2) it follows that if x,y∈X we have that x≤y, if and only if yc≤xc, and this is equivalent to say that the complementation is an isomorphism between X and its dual poset X*. In [22] has been shown that (S(n,r),⊑) is an involution poset and its complementation map c is the following:
(2)(ak…a10…0∣0…0b1…bl)c=ar-k′…a1′0…0∣0…0b1′…bn-r-l′,
where {a1′,…,ar-k′} is the usual complement of {a1,…,ak} in {1,…,r}, and {b1′,…,bn-r-l′} is the usual complement of {b1,…,bl} in {-1,…,-(n-r)} (e.g., in S(7,4), we have that (4310∣001)c=2000∣023). If d is an integer such that 0≤d≤n, we set now S(n,d,r)={w∈S(n,r):∥w∥=d}. It's easy to see that (S(n,d,r),⊑) is a sub-lattice of (S(n,r),⊑) and obviously |S(n,d,r)|=(nd). In the sequel we always denote, respectively, by 0^ and 1^ the minimum and the maximum element of the lattice S(n,d,r).


## 3. Evolution Rules

In this section we describe a discrete dynamical model with three evolution rules. In this model a configuration will be a generic element ofS(n,d,r). In the sequel, to comply with the terminology concerning the Sand Piles Models, if w∈S(n,d,r), we represent the sequence of the positive parts of w as a not-increasing sequence of columns of stacked squares and the sequence of the negative parts of w as a not-decreasing sequence of columns of stacked squares. We call a column of stacked squares a pile and each square of a pile is called a grain. For example, if n=10,r=6,d=5, the configuration
(3)
is identified with the partition (4,3,1,0,0,0∣0,0,-1,-3)=433100∣0113∈S(10,5,6). We denote by D(w):=D+(w):D-(w) the configuration associated to w, where D+(w) is the Young diagram (represented with not-increasing columns) of the partition (ar,…,a1) and D-(w) is the Young diagram (represented with not-decreasing columns) of the partition with negative summands (-b1,…,-bn-r). Our goal is to define some rules of evolution that starting from the minimum of S(n,d,r) allow us to reconstruct the Hasse diagram of S(n,d,r) (and therefore to determine the covering relations in S(n,d,r)).Letw=ar…a1∣b1…bn-r∈S(n,d,r). We formally set a0:=0, ar+1:=r+1 and b0:=0. If 0≤i≤r+1 we call ai the ith-plus pile of w, and if 0≤j≤n-r we call bj the jth-minus pile of w. We call ai plus singleton pile if ai=1 and bj minus singleton pile if bj=-1. If 1≤i≤r+1 we set Δi+(w)=ai-ai-1 and we call Δi+(w) the plus height difference of w in i. If 1≤j≤n-r we set Δj-(w)=|bj|-|bj-1| and we call Δj-(w) the minus height difference of w in j. If 1<i≤r, we say that w has a plus cliff at i if Δi+(w)≥2. If 1<j≤n-r, we say that w has a minus cliff at j if Δj-(w)≥2.Remark 1.
The choice to seta0=0, ar+1=r and b0=0 is a formal trick for decrease the number of rules necessary for our model. This means that when we apply the next rules to one element w∈S(n,d,r) we think that there is an “invisible” extra pile in the imaginary place r+1 having exactly r+1 grains, an “invisible” extra pile with 0 grains in the imaginary place to the right of a1 and to the left of | and another “invisible” extra pile with 0 grains in the imaginary place to the left of b1 and to the right of |. However the piles corresponding respectively to a0=0, ar+1=r+1 and b0=0 must be not considered as parts of w.


### 3.1.   Evolution Rules

R
1:
If theith-plus pile has at least one grain and if w has a plus cliff at i+1 then one grain must be added on the ith-plus pile:
(4)
R
2:
If there is not a plus singleton pile and there is a minus singleton pile, then the latter must be shifted to the side of the lowest not empty plus pile:(5)
R
3:
One grain must be deleted from thejth-minus pile if w has a minus cliff at j:
(6)Remark 2.
(i) Under the hypothesis inR3, the jth minus pile must have at least 2 grains.
(ii) InR2 the lowest not empty plus pile can also be the invisible column in the place r+1. In this case all the plus piles are empty and an eventual minus singleton pile must be shifted in the place r.


## 3.1.   Evolution Rules

R
1:
If theith-plus pile has at least one grain and if w has a plus cliff at i+1 then one grain must be added on the ith-plus pile:
(4)
R
2:
If there is not a plus singleton pile and there is a minus singleton pile, then the latter must be shifted to the side of the lowest not empty plus pile:(5)
R
3:
One grain must be deleted from thejth-minus pile if w has a minus cliff at j:
(6)Remark 2.
(i) Under the hypothesis inR3, the jth minus pile must have at least 2 grains.
(ii) InR2 the lowest not empty plus pile can also be the invisible column in the place r+1. In this case all the plus piles are empty and an eventual minus singleton pile must be shifted in the place r.


## 4. Covering Relations inS(n,d,r)

In this section we describe the covering relation in the latticeS(n,d,r). The main result of this section is the Theorem 3. In the sequel we write w→kw′ (or w′=w→k) to denote that w′ is a n-pla of integers obtained from w applying Rk, for k=1,2,3.Theorem 3.
(i) Ifw∈S(n,d,r) and w′=w→k for some k=1,2,3, then w′∈S(n,d,r) and w′⋗w.
(ii) Ifw,w′∈S(n,d,r) and w′⋗w, then w′=w→k for some k=1,2,3.Proof.
(i) Letw=ar…a1∣b1…bn-r∈S(n,d,r), ar+1=r+1 (the invisible pile in the place r+1) and D=D(w). We distinguish the three possible cases related to the previous rules.
Case1. Let us assume that r≥i≥1, ai≠0 and that w has a plus cliff at i+1. If w′=w→1, then w′=ar…ai+1(ai+1)ai-1…a1∣b1…bn-r. It is clear that ||w′||=d because ai≠0. Since there is a plus cliff at i+1 we have ai+1-ai≥2, hence ai+1≥ai+2>ai+1>ai>ai-1, and this implies that w′∈S(n,d,r). We must show now that w′ covers w in S(n,d,r). Since w and w′ differ between them only in the place i for ai and ai+1, respectively, it is clear that there does not exist an element z∈S(n,d,r) such that w⊏z⊏w′. Hence w′⋗w.
Case2. Let us assume that in D there is not a plus singleton pile and that there is a minus singleton pile bj=-1 for some 1≤j≤n-r. Since ar+1=r+1, we can assume that ai+1>0, ai=0, for some 1≤i≤r. This means that w has the following form: w=ar…ai+100…0∣0…0(-1)bj+1…bn-r, where ai+1>1 (otherwise D has a plus singleton pile). Applying R2 to w we obtain w′=w→2, where w′=ar…ai+110…0∣0…00bj+1…bn-r. It is clear then that w'∈S(n,r) and ||w′||=d since w′ is obtained from w with only a shift of the pile −1 to the left in the place i. Let us note that the only elements z1,z2∈S(n,r) such that w⊏z1⊏w′ and w⊏z2⊏w′ are z1=ar…ai+110…0∣0…0(-1)bj+1…bn-r and z2=ar…ai+100…0∣0…00bj+1…bn-r, but ||z1||=d+1 and ||z2||=d-1, hence z1,z2 are not elements of S(n,d,r). This implies that w' covers w in S(n,d,r).
Case3. If 1<j≤n-r and w has a minus cliff at j, we apply R3 to w on the pile bj and we obtain w′=w→3, where w′=ar…a1∣b1…bj-1(bj+1)bj+1…bn-r. Since w has a minus cliff at j, we have -bj+bj-1=|bj|-|bj-1|≥2, therefore w′∈S(n,r) because 0≥bj-1≥bj+2>bj+1>bj>bj+1 and ||w′||=d since bj≤-2 implies bj+1<0. As in the Case 1, we note that w′ covers w in S(n,d,r) because they differ between them only for a grain in the place j.
(ii) As in (i), we takew=ar…a1∣b1…bn-r∈S(n,d,r) and ar+1=r+1 (the invisible pile in the place r+1). Let w′′=ar′′…a1′′∣b1′′…bn-r′′ a generic element of S(n,d,r) such that w′′⊒w and w′′≠w. If we show that there exists an element w′=ar′…a1′∣b1′…bn-r′ of S(n,d,r) such that w′=w→k for some k=1,2,3 and w′′⊒w′ we complete the proof. Since w′′≠w, there is a place where the corresponding component of w′′ is an integer strictly bigger than the integer component of w corresponding to the same place. We distinguish several cases.
Case
A. ai′′>ai for some i∈{r-1,…,1}.
S
u
b
c
a
s
e
A
1. ai+1≥ai+2. In this case we apply R1 in the place i to obtain w′=w→1 such that w′′⊒w′.
S
u
b
c
a
s
e
A
2. ai+1=ai+1. Since ai′′>0 and i≤r-1, then ai+1′′>ai′′>ai, therefore ai+1′′≥ai+2>ai+1. Now, if i+1=r, then r≥ar′′>ar and we can apply R1 in the place r. We can assume therefore i+1<r. If ai+2≥ai+1+2 we proceed as in A1 with R1 in the place i+1, otherwise, if ai+2=ai+1+1 and i+2=r we proceed as before with R1 in the place r. Iterating, it follows that the cases to be examined are ai+k≥ai+k-1+2 or ai+k=ai+k-1+1 and i+k=r. In all these case we can apply R1 in the place i+k-1.
C
a
s
e  B. ar′′>ar. In this case we just apply R1 in the place r.
C
a
s
e  C. bj′′>bj for some j∈{1,…,n-r}.
S
u
b
c
a
s
e  C1. bj′′<0. Then bj≥-2 and we can apply R3 in the place j.
S
u
b
c
a
s
e  C2. bj′′=0 and bj≥-2. We apply R3 in the place j.
S
u
b
c
a
s
e  C3. bj′′=0, bj=-1 and ai=1 for some i∈{1,…,r}.
Ifa1=1 then w=r(r-1)…21∣0…0(-1)bj+1…bn-r with ||w||=d, therefore we can not have w′′∈S(n,d,r) such that w′′⊑w and w≠w′′. We can assume then i>1, and therefore ai-1=⋯=a1=0. Since ||w′′||=||w||=d, it must be ai′′>ai-1′′>0, hence ai′′≥2 and ai=1. Now, if ai+1≥ai+2, we apply R1 in the place i. We can suppose then that ai+1=ai+1=2. Since ai-1′′>0, it must be ai+2′′≥4, therefore, if ai+2=ai+2′′ then ai+2≥ai+1+2 and we can apply R1 in the place i+1. Hence we can assume ai+2<ai+2′′. If ai+2≥ai+1+2 we apply then R1 in the place i+1 because ai+1′′≥3>ai+1=2. Then we can suppose ai+2=ai+1+1=3. Iterating this reasoning, we apply R1 in some place i+k, with k≥1, or we obtain for w and w′′ the following forms:
(7)w=l(l-1)…3210…0∣0…0(-1)bj+1…bn-r,w′′=l′(l′-1)…3210…0∣0…00bj+1′′…bn-r′′
with r≥l′>l. We can apply therefore R1 in the place r.
S
u
b
c
a
s
e  C4. bj′′=0, bj=-1 and ai≠1 for each i∈{1,…,r}.
In this case there is at least one placei∈{1,…,r} such that ai=0. We take this i maximal, so that i=r or i<r and ai+1>0. Then, since bj′′=0, bj=-1, ai+1′′≥ai+1>0 and ||w||=||w′′||=d, it must be necessarily ai′′>0. We apply then R2 shifting the negative grain from the place j into a positive grain in the place i, that is, we take w'=w→2 with ai′=1 and bj′=0 and all other components unchanged.
Hence in all the previous cases we obtain an elementw′=w→k, for some k=1,2,3, such that w′⊑w′′.Below we draw the Hasse diagram of the latticeS(5,3,2) by using the evolution rules R1,R2,R3 starting to the minimum element of this lattice, which is 00∣123. We label a generic edge of the next diagram with the integer k if it leads to a production that uses Rk, for k∈{1,2,3}:
(8)
Since S(n,d,r) is a finite distributive lattice it is also graded; in the next proposition we determine its rank function.Proposition 4.
The rank functionρ of S(n,d,r) is ρ(w)=∑‍(w)-∑‍(0^)-(|w|>-|0^|>).Proof.
We denote byϱ the rank function of the graded lattice S(n,r). It is easy to verify that ρ(w)=∑‍(w)-∑‍(0^) for each w∈S(n,r) (see also [22]). Let w⋗wt⋗⋯⋗w1⋗0^ be any saturated chain from 0^ to w. Let us assume that in this chain w is obtained from 0^ with k applications of R2, for some integer k≥0. To each step l∈{1,…,t} where we apply R2, there is the following situation: wl⊐ul⊐wl-1, for exactly one only element ul∈S(n,r)∖S(n,d,r). This means that ϱ(w)=(t+1)+k, that is, ρ(w)=ϱ(w)-k. The integer k is also the difference between the number of positive parts of w and the number of positive parts of 0^. Hence the thesis follows.In the next proposition we compute the rank of the latticeS(n,d,r).Proposition 5.
rank
(
S
(
n
,
d
,
r
)
=
d
(
n
-
d
).Proof.
Ifr≥d>n-r, then 1^=r…(r-d+1)0…0∣0…0 and
(9)0^=(d-(n-r))…10…0∣(-1)(-2)…(-(n-r)).
So that |1^|>-|0^|>=n-r. If d>n-r and d>r, then 1^=r…1∣0…01…(d-r) and 0^=(d-(n-r))…10…0∣(-1)(-2)…(-(n-r)). So that |1^|>-|0^|>=n-d. If d≤n-r and d≤r, then 1^=r…(r-d+1)0…0∣0…0 and 0^=0…0∣0…0(-((n-r)-(d-1)))…(-(n-r)). Therefore |1^|>-|0^|>=d. Finally, if d≤n-r and d>r, then 1^=r…1∣0…0(-1)…(-(d-r)) and 0^=0…0∣0…0(-((n-r)-(d-1)))…(-(n-r)). Therefore |1^|>-|0^|>=r. The rank of S(n,d,r) is obviously ρ(1^)-ρ(0^), that we compute in all the previous cases applying the Proposition 4. The thesis follows then from simply arithmetic manipulations.


## 5. Dynamics ofS(n,d,r) as Sand Piles Model

In this section we study the latticeS(n,d,r) as a discrete dynamical system. For the terminology concerning the discrete dynamical system we refer to [21]. In such a context, we call configuration a generic element of S(n,d,r). The initial configuration is 0^. Each configuration converges, in sequential and in parallel, toward the unique fixed point 1^ because of the lattice structure of the model. Let us note that if w is a configuration, when we use the evolution rules in parallel, on each column of w we can apply (due to the nature of the Rules R1,R2,R3) exactly one evolution rule, hence our model is deterministic. With the same notations of [3], we denote respectively by Tsec(w) and Tpar(w) the number of time steps required to reach 1^ starting from the configuration w, using the sequential or the parallel updating scheme. Obviously Tsec(w) is independent of the order in which the sites are updated because S(n,d,r) is a graded lattice. Moreover it is also clear that
(10)Tsec(w)=ρ(1^)-ρ(w).
We study now some properties of the dynamics in parallel. If w and w′ are two different configurations, we say that w′ is a parallel successor of w, and we write w⇉w′ or w′=w⇉, if w′ is the configuration which is obtained with all the possible parallel applications of the Rules 1–3 on the parts of w. If we can apply in parallel mi times Ri on w, for i=1,2,3, we set M(w):=(m1,m2,m3) and |M(w)|:=m1+m2+m3. Let us note that m2 can be only 0 or 1. Obviously there is a unique finite sequence (w0,w1,…,ws) of configurations such that
(11)w0=0^⇉w1⇉⋯⇉ws-1⇉ws=1^.
The sequence in (11) is obviously a chain of length s in (S(n,d,r),⊑) that we call fundamental chain of S(n,d,r). It is clear that Tpar(0^)=s. We also call fundamental sequence of S(n,d,r) the finite integer sequence
(12)(|M(w0)|,|M(w1)|,…,|M(ws-1)|).Remark 6.
If(w0,w1,…,ws) is the fundamental chain of S(n,d,r) then
(13)∑i=1s-1‍|M(wi)|=rank(S(n,d,r)).
In the next result we compute the exact value of Tpar(0^) for a wide range of the integers parameters n,d,r and in another case we provide a lower estimate.Theorem 7.
(i) Ifd=(n-r)=r, Tpar(0^)=2d-1.
(ii) Ifd=(n-r)<r, Tpar(0^)=d+r-1=n-1.
(iii) Ifd<(n-r) and r≥d, Tpar(0^)≥2d-2.
(iv) Ifr>d>(n-r) and 2d=n, Tpar(0^)=2d-1.
(v) Ifr>d>(n-r) and 2d-n<0, Tpar(0^)=n-1.
Moreover, in all the previous cases the fundamental sequence ofS(n,d,r) is symmetric and unimodal.Proof.
(i) Ifd=(n-r)=r then 0^=0…0∣1…(n-r) and 1^=r⋯1∣0⋯0. In this case the first and the last rule which applies is always R2: in between all the rules R1,R2,R3 apply in a very symmetric way, in view of their definition and of the symmetry of three parameters of S(n,d,r). The number of rules which apply at each step follows this sequence: 1,…,(d-1),d,(d-1),…,1 and the unimodularity and the symmetry of the sequence of parallel configurations is therefore straightforward. Moreover there exists a unique time T=d in which the maximal number d of rules apply; the string at which the d rules apply is always of the following type:ifd is even: (d-1)…1…0∣0…2…d, where in both positive and negative part each number is the previous minus 2;ifd is odd: (d-1)…2…0∣0…1…d, where in both positive and negative part each number is the previous minus 2.
HenceTpar(0^)=2d-1.
(ii) Ifd=(n-r)<r then 0^=0…0∣1…(n-r) and 1^=r…(r-d+1)…0∣0…0. The first rule which applies is always R2 and the last one is always R1. In this case there are several strings obtained with the maximal number of rules which is d: the first one which appears from the bottom in the fundamental sequence of S(n,d,r) is: ifd is even, (d-1)(d-3)…10…0∣0…2…d, where in both positive and negative part each number is the previous minus 2;ifd is odd, (d-1)(d-3)…20…0∣0…1…(d-2)d, where in both positive and negative part each number is the previous minus 2.
The number of steps withd rules is exactly (r-d+1) and the number of rules which apply at each step follows this sequence: 1,…,(d-1),d,…d,(d-1),…,1: hence the unimodularity and the symmetry of the sequence of the parallel configurations is straightforward. Finally, Tpar(0^)=d+r-1=n-1.
(iii) With these parameters,0^=0…0∣0…(n-r-d+1)…(n-r) and 1^=r…(r-d+1)0…0∣0…0. The first rule from the bottom which applies is always R3 and the last rule from the top which applies is always R1. In this case there are several strings obtained with the maximal number of rules which is still d, and the number of rules which apply at each step follows this sequence: 1,…,(d-1),d,…d,(d-1),…,1: therefore the unimodularity and the symmetry of the sequence of the parallel configurations follow such as the lower bound for Tpar(0^).
(iv) With these parameters,0^=(d-n+r)⋯1⋯0∣1…(n-r) and 1^=r⋯(r-d+1)⋯0∣0⋯0. In this case the first and the last rule which applies is always R1: in between all the rules R1,R2,R3. The number of rules which apply at each step follows this sequence: 1,…,(d-1),d,(d-1),…,1 and the unimodularity and the symmetry of the sequence of parallel configurations is immediate. Moreover there exists a unique time T=d in which the maximal number d of rules apply. Hence Tpar(0^)=2d-1.
(v) With these parameters,0^=(d-n+r)⋯1⋯0∣1…(n-r) and 1^=r⋯(r-d+1)⋯0∣0⋯0. In this case the first and the last rule which applies is always R1. A difference with the previous case is that here there are several strings obtained with the maximal number of rules which is d; the number of string at which d rules apply is exactly (n-2d+1). The very interesting thing is that Tpar(0^)=n-1 is independent of d in this case, as in case (ii). Obviously also in this case we have the unimodularity and the symmetry of the sequence of the parallel configurations.



---

*Source: 615703-2013-01-13.xml*