# Parallel Rank of Two Sandpile Models of Signed Integer Partitions

Authors: G. Chiaselotti; T. Gentile; G. Marino; P. A. Oliverio
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

We introduce the concept of fundamental sequence for a finite graded posetX which is also a discrete dynamical model. The concept of fundamental sequence is a refinement of the concept of parallel convergence time for these models. We compute the parallel convergence time and the fundamental sequence when X is the finite lattice P(n,r) of all the signed integer partitions ar,…,a1,b1,…,bn−r such that r≥ar≥⋯≥a1≥0≥b1≥⋯≥bn−r≥−(n−r), where n≥r≥0, and when X is the sublattice P(n,d,r) of all the signed integer partitions of P(n,r) having exactly d nonzero parts.


---

## Body

## 1. Introduction

The study of the order relation in particular subsets of integer partitions has been recently addressed from the point of view of the discrete dynamical models. The excellent survey [1] describes several subsets of integer partitions which have a lattice structure in terms of discrete dynamical models. Before going further, we borrow from [1] the following description of discrete dynamical model (briefly DDM): “At each (discrete) time step, such a model is in some state, which we call a configuration. Configurations are described by combinatorial objects, like graphs, integer partitions, and others, and we will not distinguish a configuration and its combinatorial description. A discrete dynamical model is then defined by an initial configuration and (some) evolution (rules) which (say) under which conditions the (configurations) may be changed, and which (describe) the new configurations one may obtain. These (rules) can generally be applied under a local condition, and (they imply) a local modification of the current configuration. Note that in the general case the evolution (rules) can be applied in several places in a configuration, leading to several configurations. If a configuration c′ can be obtained from a configuration c after one application of (some) evolution (rule), we say that c′ is a successor of c, or c is a predecessor of c′, which is denoted by c→c′." In this paper, we consider integer partitions; therefore, we use the term configuration as an equivalent to integer partition. There are two ways in which we can apply the evolution rules on a given configuration: a sequential way (in this case, we refer also to sequential dynamic of the DDM) and a parallel way (in this case, we refer also to parallel dynamic of the DDM). In the sequential way, we apply the evolution rules separately on each summand of the configuration. In the parallel way, we apply the evolution rules concurrently on all the summands of the configuration. When we start from the initial configuration and apply the evolution rules in a sequential way, generally we obtain an oriented graph which represents the Hasse diagram of a poset of integer partitions with an order relation ⊑. In this case, one usually proves that the relation c→c′ is equivalent to saying that c is covered by c′ with respect to the partial order ⊑. Therefore, several concepts of the classical order theory find their interesting formulation in dynamic terms. The first implicit formulation of the covering rules of an integer partitions lattice as evolution rules of a DDM was given in the famous Brylawski paper [2]. In this paper, Brylawski proposed a dynamical approach in order 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 DDM begins in [3, 4]. In the DDM introduced by Goles and Kiwi in [4], denoted by SPM(n), a configuration is an integer partition a=(a1,…,an) of the positive integer n, and each summand of a is identified with a pile of sand grains; hence, the name is sandpile model (briefly SPM). In this model, there is only one evolution rule.Rule 1 (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 [2]), the movement of a sand grain respects Rule 1 and also the following.Rule 2 (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.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. TheSPM(n) can be also related to the self-organized criticality (SOC) property, introduced by Bak et al. in [5]. The study of such systems has been developed in an algebraic context [6], in a combinatorial game theory setting [4, 7, 8], in the theory of cellular automata [9–11], and in the setting of discrete dynamical systems [12–14].There exists a wide literature concerning dynamical models related in several ways to the original modelSPM(n), [8, 15–29].When we study the parallel dynamic of an SPM which also has a lattice structure, starting from its initial configuration (denoted by0^), we always arrive after s unit time steps to a unique final configuration (denoted by 1^), that is, the maximum of the correspondent lattice. This nonnegative integer s, denoted by Tpar(0^), was introduced explicitly in [3, 4]. The number Tpar(0^) is relevant to the study of a DDM of integer partitions which is also a graded lattice because it represents a type of “parallel rank" of the graded lattice. The classical concept of rank can be identified with the number of sequential unit steps needed to reach 1^ starting from 0^, and in [4] this number is denoted by Tseq(0^). Our question is then as follows: is it possible to refine the concept of “parallel rank" Tpar(0^) in such a way that this refinement conducts us to have further information concerning the graded lattice? For example, can the parallel dynamic of the model, in some sense, characterize the symmetry of the corresponding lattice? It is very difficult, in general, to establish, for example, when a graded lattice has the Sperner property, or it is rank unimodal or rank symmetric. Can a refinement of the study of the parallel dynamic of an SPM that is also a graded lattice be helpful in addressing these problems? In this paper, we introduce and study some concepts related to the parallel dynamic of SPMs, and we study these concepts in the wider environment of the signed integer partitions, that is, integer partitions whose summands can be also negative. The signed integer partitions have been recently introduced by Andrews in [30] and further studied in [31] from an arithmetical point of view. The reason why we work in the signed integer partitions environment is not only formal. In the context of the signed integer partitions, it is easier to see the symmetry of the examined models. Almost all these models of the signed integer partitions are equipped with an involution order-reversing map that makes their self-duality immediately clear. Moreover, a signed integer partition is a generalization of a usual integer partition; therefore, all the classical results can be considered as particular cases of their analogues obtained with signed integer partitions. In the sequel, we assume that (X,⊑) is a finite graded lattice of signed integer partitions with minimum 0^ and maximum 1^. We denote by rank(X) the rank of X. Moreover, we also assume that X is a generic deterministic DDM having k distinct evolution rules R1,…,Rk. In our case, this means that at each position at most one rule is applied (however the same rule may be applied at several different positions). In our model X, given two configurations w,w′∈X, it results that w is covered by w′ (with respect to the partial order ⊑) if and only if w′ is obtained from w with the application of some rule Ri. Therefore, in the sequel, we can always identify Tseq(0^) with rank(X).Ifw and w′ are two different configurations of X, 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 R1,…,Rk on the parts of w. If we apply in parallel mi times the rule Ri on w, for i=1,…,k, in order to obtain w′, we write w⇉〈(m1,…,mk)〉w′, and we also set M(w):=(m1,…,mk) and |M(w)|:=m1+⋯+mk. We write w⇉〈M(w),M(u),…,M(z)〉w′ if there exists u,v,…,z such that w⇉〈M(w)〉u⇉〈M(u)〉v⇉⋯z⇉〈M(z)〉w′. Let us note that there is a unique finite sequence (w0,w1,…,ws) of configurations in X such that
(1)w0=0^⇉w1⇉⋯⇉ws-1⇉ws=1^.
The sequence in (1) is a chain of length s in X that we call fundamental chain of X. It is clear that
(2)∑i=1s-1‍|M(wi)|=Tseq(0^)
and Tpar(0^)=s. We call parallel rank of X the integer Tpar(0^) and sequential rank of X the integer Tseq(0^). We also call fundamental sequence of X the integer sequence
(3)(|M(w0)|,|M(w1)|,…,|M(ws-1)|).
We say that X is  parallel unimodal if the fundamental sequence of X is a unimodal sequence; we also say that X is  parallel symmetric if the fundamental sequence of X is a symmetric sequence. In this paper, we compute the parallel rank and the fundamental sequence in two cases. In the first case, when X is the lattice P(n,r) of all the signed integer partitions of the form ar,…,a1,b1,…,bn-r, where n≥r≥0 are two fixed integers and r≥ar≥⋯≥a1≥0≥b1≥⋯≥bn-r≥-(n-r). In the second (more difficult) case, when X is the sublattice P(n,d,r) of all the signed integer partitions of P(n,r) having exactly d nonzero parts. The paper is structured as follows. In Section 2, we define the lattice P(n,r) and establish the evolution rules which determine its covering relations, and we compute the usual rank, the parallel rank, and the fundamental sequence of P(n,r). In Section 3, we introduce a new integer parameter 1≤d≤n and define the sublattice P(n,d,r). We establish three evolution rules which determine the covering relations in P(n,d,r) and determine the usual rank of this lattice. In Section 4, we compute the parallel rank and the fundamental sequence of P(n,d,r) for all the values of the integers parameters n, d, and r. The complete results of our computations are listed in Tables 1 and 2.Table 1
Parallel rank inP(n, d, r).
Case
Relation betweenn, d, and r
Parallel rankTpar(0^)
I
d
≤
min
{
r
,
n
-
r
}
n
+
d
-
2
II
r
≥
d
≥
2
(
n
-
r
)
d
+
r
-
2
III
r
≥
d
≥
n
-
r and 2(n-r)≥d≥n-r
2
n
-
r
-
2
IV
n
-
r
≥
d
≥
2
r
d
+
n
-
r
-
2
V
n
-
r
≥
d
≥
r and 2r≥d≥r
n
+
r
-
2
VI
min
{
2
r
,
2
(
n
-
r
)
}
≥
d
≥
max
{
r
,
n
-
r
}
2
n
-
d
-
2
VII
2
r
>
d
≥
2
(
n
-
r
) and d≥max{r,n-r}
2
r
-
2
VIII
2
(
n
-
r
)
>
d
≥
2
r and d≥max{r,n-r}
2
(
n
-
r
)
-
2Table 2
Fundamental sequence inP(n, d, r).
Case
Fundamental sequence
Case I
(
1
,
2
,
…
,
d
-
1
,
d
,
d
,
…
,
d
,
d
-
1
,
…
1
)
Case II
(
2
,
4
,
…
,
2
(
n
-
r
-
1
)
,
2
(
n
-
r
)
,
…
,
2
(
n
-
r
)
,
2
(
n
-
r
)
+
1
,
…
,
d
-
1
,
d
,
…
,
d
,
d
-
1
,
…
1
)
Case III
(
2
,
4
,
…
,
2
(
d
-
n
+
r
-
1
)
,
2
(
d
-
n
+
r
)
,
2
(
d
-
n
+
r
)
+
1
,
…
,
d
-
1
,
d
,
…
,
d
,
d
-
1
,
…
,
1
)
Case IV
(
1
,
2
,
…
,
d
-
1
,
d
,
…
,
d
,
d
-
2
,
…
,
d
-
2
r
,
d
-
2
r
-
1
,
…
,
1
)
Case V
(
1
,
2
,
…
,
d
-
1
,
d
,
…
,
d
,
d
-
2
,
…
,
2
r
-
d
,
2
r
-
d
-
1
,
…
,
1
)
Case VI.1
(
2
,
4
,
…
,
2
(
d
-
n
+
r
)
,
2
(
d
-
n
+
r
)
+
1
,
…
,
d
,
…
,
d
,
d
-
1
,
…
,
n
-
r
,
…
,
n
-
r
,  n-r-1,…,n-d,…,n-d,n-d-1,…,1)
Case VI.2
(
2
,
4
,
…
,
2
(
d
-
n
+
r
)
,
2
(
d
-
n
+
r
)
+
1
,
…
,
d
,
…
,
d
,
d
-
1
,
…
,
2
(
d
-
n
+
r
)
,
2
(
d
-
n
+
r
-
1
)
,
…   …,4n-4r-2d,4n-4r-2d-1,…,n-d,…,n-d,n-d-1,…,1)
Case VI.3
(
2
,
4
,
…
,
2
(
d
-
n
+
r
)
,
2
(
d
-
n
+
r
)
+
1
,
…
,
d
,
…
,
d
,
d
-
1
,
…
,
2
(
d
-
n
+
r
)
,
2
(
d
-
n
+
r
)
-
1,   2(d-n+r)-3,…,4r-2n-1,4r-2n-2,…,n-d,…,n-d,n-d-1,…,1)
Case VI.4
(
2
,
4
,
…
,
2
(
d
-
n
+
r
)
,
2
(
d
-
n
+
r
)
+
1
,
…
,
d
-
n
+
2
r
-
1
,
…
,
d
-
n
+
2
r
-
1
,
d
-
n
+
2
r
,
…
,
n
-
r
,
…  …,n-r,n-r-1,…,2n-d-2r,2n-d-2r-2,…,2r-d,2r-d-1,…,1)
Case VI.5
(
2
,
4
,
…
,
2
(
d
-
n
+
r
)
,
2
(
d
-
n
+
r
)
+
1
,
…
,
d
-
n
+
2
r
-
1
,
…
,
d
-
n
+
2
r
-
1
,
d
-
n
+
2
r
-
2
,
…   …,n-r,…,n-r,n-r-1,…,2n-d-2r,2n-d-2r-2,…,2r-d,2r-d-1,…,1)
Case VI.6
(
2
,
4
,
…
,
2
(
d
-
n
+
r
)
,
2
(
d
-
n
+
r
)
+
1
,
…
,
d
-
n
+
2
r
-
1
,
…
,
d
-
n
+
2
r
-
1
,
d
-
n
+
2
r
-
2
,
…   …,n-r,…,n-r,n-r-1,…,2n-d-2r,2n-d-2r-2,…,2r-d,2r-d-1,…,1)
Case VII.1
(
2
,
4
,
…
,
2
(
n
-
r
)
,
…
,
2
(
n
-
r
)
,
2
(
n
-
r
)
-
1
,
…
,
2
(
n
-
r
)
-
1
,
2
(
n
-
r
)
-
2,   2(n-r)-4,…,4r-2n,4r-2n-1,…,1)
Case VII.2
(
2
,
4
,
…
,
2
(
n
-
r
)
,
…
,
2
(
n
-
r
)
,
2
(
n
-
r
)
-
1
,
…
,
2
(
n
-
r
)
-
1
,
2
(
n
-
r
),   2(n-r)+1,…,r-1,r-1,…,1)
Case VIII.1
(
2
,
4
,
…
,
2
(
d
-
n
+
r
)
,
2
(
d
-
n
+
r
)
+
1
,
…
,
d
-
n
+
2
r
-
1
,
…
,
d
-
n
+
2
r
-
1
,
d
-
n
+
2
r
,
…
,
n
-
r
,  …,n-r,n-r-1,…,2n-2r-d,2n-2r-d-2…,d-2r,d-2r-1,…,1)
Case VIII.2
(
2
,
4
,
…
,
2
(
d
-
n
+
r
)
,
2
(
d
-
n
+
r
)
+
1
,
…
,
d
-
n
+
2
r
-
1
,
…
,
d
-
n
+
2
r
-
1
,
d
-
n
+
2
r
-
2,   …,2(d-n+r),2(d-n+r-1),…,2(2n-2r-d),2(2n-2r-d)-1,   …,2n-2r-d,2n-2r-d-2…,d-2r,d-2r-1,…,1)
Case VIII.3
(
2
,
4
,
…
,
2
(
d
-
n
+
r
)
,
2
(
d
-
n
+
r
)
+
1
,
…
,
d
-
n
+
2
r
-
1
,
…
,
d
-
n
+
2
r
-
1
,
d
-
n
+
2
r
-
2,   …,n-r+1,n-r,…,n-r,n-r-1,…,2n-2r-d,   2n-2r-d-2…,d-2r,d-2r-1,…,1)


## 2. The Sandpile ModelP(n,r)

In this section, we introduce the lattice of signed integer partitionsP(n,r), and we examine some of its basic properties. Let n,r be two fixed nonnegative integers such that n≥r. We call (n,r)-signed partition an n-tuple of integers
(4)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.In some cases, whenn and r are clear from the context, we say simply signed partition instead of (n,r)-signed partition. We denote by P(n,r) the set of all the (n,r)-signed partitions. If w is an (n,r)-signed partition, we call parts of w the integers ar,…,a1,b1⋯bn-r, nonnegative 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 an (n,r)-signed partition of m; in this case, we write w⊢m. We set w+=ar⋯a1| and w-=|b1⋯bn-r. In order to simplify the notations, in the numerical examples we write the integers b1,…,bn-r of a generic (n,r)-signed partition without the minus sign. For example, we write 4410∣01125 instead of 4410∣0(-1)(-1)(-2)(-5). Sometimes, when we do not distinguish between nonnegative and nonpositive parts, we write an (n,r)-signed partition without vertical bar ∣. 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|<. If w=ar⋯a1∣b1⋯bn-r and w′=ar′⋯a1′∣b1′⋯bn-r′ are two (n,r)-signed partitions, 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 P(n,r), we consider the partial order on the components that we denote by ⊑. As usual, we write w⊏w′ if w⊑w′ and w≠w′. Moreover, we write w⋖w′ (or w′⋗w) if w′ covers w. Since (P(n,r),⊑) is a finite distributive lattice (because its partial order is on the components), it is also graded with minimum element 0⋯0∣(n-r)⋯(n-r) and maximum element r⋯r∣0⋯0.Now let us describe the evolution rules which describeP(n,r) as a discrete dynamical model. In the sequel, if w∈P(n,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 pile a column of stacked squares and grain each square of a pile. For example, if n=10,r=6, the configuration
(5)
is identified with the signed partition 433100∣0113∈P(10,6).Letw=ar⋯a1∣b1⋯bn-r∈P(n,r). We formally set a0=0, ar+1=r, 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 bjminus singleton pile if bj=-1. If 1≤i≤r+1, we say that w has a plus step at i if ai-ai-1≥1. If 1≤j≤n-r, we say that w has a minus step at j if |bj|-|bj-1|≥1.Remark 1.
The choice to seta0=0, ar+1=r, and b0=0 is a formal trick to decrease the number of rules necessary for our model. This means that when we apply the next rules to one element w∈P(n,r), we think that there is an “invisible" extra pile in the imaginary place r+1 having exactly r 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, and b0=0 must not be considered as parts of w.


### 2.1. Evolution Rules

Rule 1.
Ifw has a plus step at i+1, then one grain must be added on the ith-plus pile
(6)Rule 2.
One grain must be deleted from thejth-minus pile if w has a minus step at j(7)
We write w↦kw′ (or w′=w↦k) to denote that w′ is an n-tuple of integers obtained from w applying the Rule k, for k=1,2. We also set
(8)∇(w)={w′:w↦kw′,k=1,2}.Theorem 2.
Ifw∈P(n,r), then ∇(w)={w′∈P(n,r):w′⋗w}.Proof.
We start to show that∇(w)⊆{w′∈P(n,r):w′⋗w}. Let w=ar⋯a1∣b1⋯bn-r∈P(n,r) and ar+1=r be the invisible pile in the place r+1. We distinguish the two possible cases related to the previous rules.
Case
1. Let us assume that r≥i≥1,  ai≠0, and that w has a plus step at i+1. If w′=w↦1, then w′=ar⋯ai+1(ai+1)ai-1⋯a1∣b1⋯bn-r. Since there is a plus step at i+1, we have ai+1-ai≥1; hence, ai+1≥ai+1>ai≥ai-1, and this implies that w′∈P(n,r). We must show now that w′ covers w in P(n,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∈P(n,r) such that w⊏z⊏w′. Hence, w′⋗w.
Case
2. If 1≤j≤n-r and w has a minus step at j, we apply Rule 2 to w on the minus pile bj, and we obtain w′=w↦2, where w′=ar⋯a1∣b1⋯bj-1(bj+1)bj+1⋯bn-r. Since w has a minus step at j, we have -bj+bj-1=|bj|-|bj-1|≥1, and therefore, w′∈P(n,r) because 0≥bj-1≥bj+1>bj≥bj+1. As in the Case 1, we note that w′ covers w in P(n,r) because they differ between them only for a grain in the place j.
We must show now that{w′∈P(n,r):w′⋗w}⊆∇(w). Let w=an⋯a1 and w′=an′⋯a1′ be two (n,r)-signed partitions in P(n,r). We prove at first that w′ covers w if and only if there exists exactly a place k where w and w′ are different and that ak′-ak=1. In fact, if ak′-ak=1 and ai′=ai if i≠k, it is immediate to see that w′ covers w. In order to prove the other implication, we assume that w′ covers w, and we proceed by contradiction. We must distinguish three cases.
Case
A.  w and w′ are equal in all their parts. In this case, w=w′, against the hypothesis.
Case
B. There exist at least two places k and h, with h>k, where w and w′ differ, with lk′>lk and lh′>lh. We consider the signed partition
(9)u=an′⋯ah+1′ah′ah-1⋯ak+1akak-1⋯a1.
Then, r≥an′≥⋯≥ah+1′≥ah′>ah≥ah-1≥⋯≥ak+1≥ak≥ak-1≥⋯≥a1≥-(n-r); therefore, u∈P(n,r), and since w⊏u⊏w′, this is against the hypothesis that w′ covers w.
Case
C. There exists exactly one place k where w and w′ are different, but ak′-ak>1. This implies that ak<ak+1<lk′. We consider now the signed partition
(10)u=an⋯ak+1(ak+1)ak-1⋯a1.
Let us observe then that w⊏u⊏w′ and u∈P(n,r), and this is absurd because w′ covers w.
Therefore, ifw=ar⋯a1∣b1⋯bn-r and w′=ar′⋯a1′∣b1′⋯bn-r′ are two (n,r)-signed partitions such that w⋖w′, the condition thatw′ covers w can occur just by one of the following possibilities:(i)
there exists exactly an indexi∈{1,…,r}, with ai′=ai+1, and so w′=w↦1,(ii)
there exits exactly an indexj∈{1,…,n-r}, with bj′=bj+1, and so w′=w↦2.
According to the definition of∇(w), the thesis follows.Now let us study the sequential and the parallel dynamic of the modelP(n,r). In such a context, we call configuration an element of P(n,r). The initial configuration is 0^=0⋯0∣(r-n)⋯(r-n). Each configuration converges, in sequential and in parallel, toward the unique fixed point 1^=r⋯r∣0⋯0 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 Rules 1 and 2) at most one evolution rule; hence, our model is deterministic. Obviously, Tseq(w) is independent of the order in which the sites are updated because P(n,r) is a finite distributive and hence also a graded lattice. From the previous theorem, we can easily obtain the rank function of P(n,r).Proposition 3.
Let one denote byϱ the rank function of the graded lattice P(n,r). Then, ϱ(w)=∑‍(w)-∑‍(0^) for each w∈P(n,r) and Tseq(0^)=r2+(n-r)2.Proof.
Letw,w′∈P(n,r) such that w′⋗w. From the previous theorem, w′ is obtained from w with an application of Rules 1 or 2. If we take then the function ϱ(w):=∑‍(w)-∑‍(0^), we obtain ϱ(w′)=ϱ(w)+1 and ϱ(0^)=0. Hence, ϱ is exactly the rank function of P(n,r). The second part of the thesis is followed by Tseq(0^)=ϱ(1^)=∑‍(1^)-∑‍(0^)=r2+(n-r)2.For the sake of completeness, we recall that in [36] we have computed the rank of the sublattice S(n,r) of all the signed partitions of P(n,r) having positive and negative parts all distinct between them.We recall now the concept of involution poset. Aninvolution 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) it 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*.Now, ifw=ar⋯a1∣b1⋯bn-r∈P(n,r), we set wc=(r-a1)⋯(r-ar)∣(|bn-r|-(n-r))⋯(|b1|-(n-r)), and let us note that wc is still a signed partition in P(n,r); therefore, we can define a unary operation c:P(n,r)→P(n,r) such that w↦wc. Then, it is immediate to verify that (P(n,r),⊑,c) is an involution poset. If w=ar⋯a1∣b1⋯bn-r∈P(n,r), we also set wt=(-bn-r)⋯(-b1)∣(-a1)⋯(-ar), and we call wt the transposed of w. Let us note that wt∈P(n,n-r).Proposition 4.
We have:
(i)|P(n,r)|=(2rr)(2(n-r)n-r)
(ii)P(n,r)≅P(n,n-r).Proof.
(i) It is sufficient to observe thatP(n,r) can be identified with the set of all the ordered pairs (z1,z2), where z1 is a decreasing string of length r on the ordered alphabet r>⋯>1>0 and z2 is a decreasing string of length n-r on the ordered alphabet 0>-1>⋯>-(n-r); therefore, |P(n,r)|=((r+1)+r-1r)((n-r+1)+(n-r)-1n-r)=(2rr)(2(n-r)n-r).
(ii) We define the mapϕ:P(n,r)→P(n,n-r) such that ϕ(w)=(wt)c, for all w∈P(n,r). We prove then that ϕ is an isomorphism of posets. By part (i), it follows that |P(n,r)|=|P(n,n-r)|; therefore, ϕ is bijective since it is easily seen that it is injective. If w,w′∈P(n,r), the condition w⊑w′⇔ϕ(w)⊑ϕ(w′) follows at once from the conditions (I1), (I2) and because the transposed map w↦wt is order-reversing and such that (wt)t=w.Theorem 5.
The parallel rankTpar(0^) in P(n,r) is given by
(11)Tpar(0^)={2r-1ifr≥n-r2(n-r)-1ifr<n-r.
The fundamental sequence ofP(n,r) is equal to(12)(2,4,…,2(n-r),2(n-r),…,2(n-r),2(n-r)+1,…,r,r-1,…,1)yyyyyyyyyyyyyyifr>2(n-r)(2,4,…,2(n-r),2(n-r),…,2(n-r),2(n-r)-2,…,4r-2n,4r-2n-1,…,1)yyyyyifn-r≤r≤2(n-r)(2,4,…,2r,2r,…,2r,2r+1,…,n-r,n-r-1,…,1)yyyyyyyyyyyyyyyyyyyyyyyyyyifn-r>2r(2,4,…,2r,2r,…,2r,2r-2,…,2n-4r,2n-4r-1,…,1)yyyyyyyyyyyyyyyyyyyyyyyifr≤n-r≤2r.Proof.
By Proposition4 (ii), we can consider r≥n-r. The initial configuration is 0^=0⋯0∣(n-r)⋯(n-r). Since our model is deterministic, we can consider separately the action of the Rules 1 and 2. On the nonnegative part, Rule 1 is applied as in the sequence
(13)(1,2,…,r,(r-1),…,1)
of length 2r-1 and similarly Rule 2 on the nonpositive part as in the sequence
(14)(1,2,…,(n-r),(n-r-1),…,1),
of length 2(n-r)-1. It follows that the parallel rank of P(n,r) is equal to the maximum of the length of the two sequences (13) and (14) and that the fundamental sequence is the sum of the two sequences. The other parts follow easily by replacing r with n-r and conversely.


## 2.1. Evolution Rules

Rule 1.
Ifw has a plus step at i+1, then one grain must be added on the ith-plus pile
(6)Rule 2.
One grain must be deleted from thejth-minus pile if w has a minus step at j(7)
We write w↦kw′ (or w′=w↦k) to denote that w′ is an n-tuple of integers obtained from w applying the Rule k, for k=1,2. We also set
(8)∇(w)={w′:w↦kw′,k=1,2}.Theorem 2.
Ifw∈P(n,r), then ∇(w)={w′∈P(n,r):w′⋗w}.Proof.
We start to show that∇(w)⊆{w′∈P(n,r):w′⋗w}. Let w=ar⋯a1∣b1⋯bn-r∈P(n,r) and ar+1=r be the invisible pile in the place r+1. We distinguish the two possible cases related to the previous rules.
Case
1. Let us assume that r≥i≥1,  ai≠0, and that w has a plus step at i+1. If w′=w↦1, then w′=ar⋯ai+1(ai+1)ai-1⋯a1∣b1⋯bn-r. Since there is a plus step at i+1, we have ai+1-ai≥1; hence, ai+1≥ai+1>ai≥ai-1, and this implies that w′∈P(n,r). We must show now that w′ covers w in P(n,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∈P(n,r) such that w⊏z⊏w′. Hence, w′⋗w.
Case
2. If 1≤j≤n-r and w has a minus step at j, we apply Rule 2 to w on the minus pile bj, and we obtain w′=w↦2, where w′=ar⋯a1∣b1⋯bj-1(bj+1)bj+1⋯bn-r. Since w has a minus step at j, we have -bj+bj-1=|bj|-|bj-1|≥1, and therefore, w′∈P(n,r) because 0≥bj-1≥bj+1>bj≥bj+1. As in the Case 1, we note that w′ covers w in P(n,r) because they differ between them only for a grain in the place j.
We must show now that{w′∈P(n,r):w′⋗w}⊆∇(w). Let w=an⋯a1 and w′=an′⋯a1′ be two (n,r)-signed partitions in P(n,r). We prove at first that w′ covers w if and only if there exists exactly a place k where w and w′ are different and that ak′-ak=1. In fact, if ak′-ak=1 and ai′=ai if i≠k, it is immediate to see that w′ covers w. In order to prove the other implication, we assume that w′ covers w, and we proceed by contradiction. We must distinguish three cases.
Case
A.  w and w′ are equal in all their parts. In this case, w=w′, against the hypothesis.
Case
B. There exist at least two places k and h, with h>k, where w and w′ differ, with lk′>lk and lh′>lh. We consider the signed partition
(9)u=an′⋯ah+1′ah′ah-1⋯ak+1akak-1⋯a1.
Then, r≥an′≥⋯≥ah+1′≥ah′>ah≥ah-1≥⋯≥ak+1≥ak≥ak-1≥⋯≥a1≥-(n-r); therefore, u∈P(n,r), and since w⊏u⊏w′, this is against the hypothesis that w′ covers w.
Case
C. There exists exactly one place k where w and w′ are different, but ak′-ak>1. This implies that ak<ak+1<lk′. We consider now the signed partition
(10)u=an⋯ak+1(ak+1)ak-1⋯a1.
Let us observe then that w⊏u⊏w′ and u∈P(n,r), and this is absurd because w′ covers w.
Therefore, ifw=ar⋯a1∣b1⋯bn-r and w′=ar′⋯a1′∣b1′⋯bn-r′ are two (n,r)-signed partitions such that w⋖w′, the condition thatw′ covers w can occur just by one of the following possibilities:(i)
there exists exactly an indexi∈{1,…,r}, with ai′=ai+1, and so w′=w↦1,(ii)
there exits exactly an indexj∈{1,…,n-r}, with bj′=bj+1, and so w′=w↦2.
According to the definition of∇(w), the thesis follows.Now let us study the sequential and the parallel dynamic of the modelP(n,r). In such a context, we call configuration an element of P(n,r). The initial configuration is 0^=0⋯0∣(r-n)⋯(r-n). Each configuration converges, in sequential and in parallel, toward the unique fixed point 1^=r⋯r∣0⋯0 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 Rules 1 and 2) at most one evolution rule; hence, our model is deterministic. Obviously, Tseq(w) is independent of the order in which the sites are updated because P(n,r) is a finite distributive and hence also a graded lattice. From the previous theorem, we can easily obtain the rank function of P(n,r).Proposition 3.
Let one denote byϱ the rank function of the graded lattice P(n,r). Then, ϱ(w)=∑‍(w)-∑‍(0^) for each w∈P(n,r) and Tseq(0^)=r2+(n-r)2.Proof.
Letw,w′∈P(n,r) such that w′⋗w. From the previous theorem, w′ is obtained from w with an application of Rules 1 or 2. If we take then the function ϱ(w):=∑‍(w)-∑‍(0^), we obtain ϱ(w′)=ϱ(w)+1 and ϱ(0^)=0. Hence, ϱ is exactly the rank function of P(n,r). The second part of the thesis is followed by Tseq(0^)=ϱ(1^)=∑‍(1^)-∑‍(0^)=r2+(n-r)2.For the sake of completeness, we recall that in [36] we have computed the rank of the sublattice S(n,r) of all the signed partitions of P(n,r) having positive and negative parts all distinct between them.We recall now the concept of involution poset. Aninvolution 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) it 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*.Now, ifw=ar⋯a1∣b1⋯bn-r∈P(n,r), we set wc=(r-a1)⋯(r-ar)∣(|bn-r|-(n-r))⋯(|b1|-(n-r)), and let us note that wc is still a signed partition in P(n,r); therefore, we can define a unary operation c:P(n,r)→P(n,r) such that w↦wc. Then, it is immediate to verify that (P(n,r),⊑,c) is an involution poset. If w=ar⋯a1∣b1⋯bn-r∈P(n,r), we also set wt=(-bn-r)⋯(-b1)∣(-a1)⋯(-ar), and we call wt the transposed of w. Let us note that wt∈P(n,n-r).Proposition 4.
We have:
(i)|P(n,r)|=(2rr)(2(n-r)n-r)
(ii)P(n,r)≅P(n,n-r).Proof.
(i) It is sufficient to observe thatP(n,r) can be identified with the set of all the ordered pairs (z1,z2), where z1 is a decreasing string of length r on the ordered alphabet r>⋯>1>0 and z2 is a decreasing string of length n-r on the ordered alphabet 0>-1>⋯>-(n-r); therefore, |P(n,r)|=((r+1)+r-1r)((n-r+1)+(n-r)-1n-r)=(2rr)(2(n-r)n-r).
(ii) We define the mapϕ:P(n,r)→P(n,n-r) such that ϕ(w)=(wt)c, for all w∈P(n,r). We prove then that ϕ is an isomorphism of posets. By part (i), it follows that |P(n,r)|=|P(n,n-r)|; therefore, ϕ is bijective since it is easily seen that it is injective. If w,w′∈P(n,r), the condition w⊑w′⇔ϕ(w)⊑ϕ(w′) follows at once from the conditions (I1), (I2) and because the transposed map w↦wt is order-reversing and such that (wt)t=w.Theorem 5.
The parallel rankTpar(0^) in P(n,r) is given by
(11)Tpar(0^)={2r-1ifr≥n-r2(n-r)-1ifr<n-r.
The fundamental sequence ofP(n,r) is equal to(12)(2,4,…,2(n-r),2(n-r),…,2(n-r),2(n-r)+1,…,r,r-1,…,1)yyyyyyyyyyyyyyifr>2(n-r)(2,4,…,2(n-r),2(n-r),…,2(n-r),2(n-r)-2,…,4r-2n,4r-2n-1,…,1)yyyyyifn-r≤r≤2(n-r)(2,4,…,2r,2r,…,2r,2r+1,…,n-r,n-r-1,…,1)yyyyyyyyyyyyyyyyyyyyyyyyyyifn-r>2r(2,4,…,2r,2r,…,2r,2r-2,…,2n-4r,2n-4r-1,…,1)yyyyyyyyyyyyyyyyyyyyyyyifr≤n-r≤2r.Proof.
By Proposition4 (ii), we can consider r≥n-r. The initial configuration is 0^=0⋯0∣(n-r)⋯(n-r). Since our model is deterministic, we can consider separately the action of the Rules 1 and 2. On the nonnegative part, Rule 1 is applied as in the sequence
(13)(1,2,…,r,(r-1),…,1)
of length 2r-1 and similarly Rule 2 on the nonpositive part as in the sequence
(14)(1,2,…,(n-r),(n-r-1),…,1),
of length 2(n-r)-1. It follows that the parallel rank of P(n,r) is equal to the maximum of the length of the two sequences (13) and (14) and that the fundamental sequence is the sum of the two sequences. The other parts follow easily by replacing r with n-r and conversely.


## 3. The SubmodelP(n,d,r) with Three Evolution Rules

In this section, we consider a submodel ofP(n,r) which presents an evolution rule which permits us to move one single grain from the right part of a configuration into its left part. Let d be a positive integer such that d≤n. We define P(n,d,r) as the set of all the (n,r)-signed partitions w∈P(n,r) such that ||w||=d. It is immediate to see that P(n,d,r) is a sublattice of P(n,r). The lattice P(n,d,r) is related to some extremal combinatorial sum problems studied in [32–35]. The interesting problem is to determine some evolution rules which describe such a lattice as a discrete dynamical model. We consider then the following rules.


### 3.1.  Evolution Rules

Rule
R
1
. If the ith-plus pile has at least one grain, and if w has a plus step at i+1, then one grain must be added on the ith-plus pile(15)Rule
R
2. If there are some minus singleton piles, then the first from the left of them must be shifted to the side of the lowest not empty plus pile(16)Rule
R
3
. One grain must be deleted from the jth-minus pile if w has a minus step at j and |bj|>1(17)Remark 6.
(i) In the previous rule, the lowest not empty plus pile can also be the invisible column in the placer+1. In this case, all the plus piles are empty, and an eventual minus singleton pile must be shifted in the place r.
(ii) We take implicitly for intended that the shift of one minus singleton pile into a plus singleton pile can be made if the number of plus piles (excludingar+1=r) with at least a grain is less than r (otherwise we obtain a configuration that does not belong to P(n,d,r)).We writew→kw′ (or w′=w→k) to denote that w′ is an n-tuple of integers obtained from w applying Rule Rk, for k=1,2,3. We also set
(18)∇(w)={w′:w⟶kw′,k=1,2,3}.Theorem 7.
Ifw∈P(n,d,r), then ∇(w)={w′∈P(n,d,r):w′⋗w}.Proof.
We start to show that∇(w)⊆{w′∈P(n,d,r):w′⋗w}. Let w=ar⋯a1∣b1⋯bn-r∈P(n,d,r) and ar+1=r be the invisible pile in the place r+1. We distinguish the three possible cases related to the previous rules.
Case
1. Let us assume that r≥i≥1, ai≠0 and that w has a plus step 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 step at i+1, we have ai+1-ai≥1; hence, ai+1≥ai+1>ai≥ai-1, and this implies that w′∈P(n,d,r). We must show now that w′ covers w in P(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∈P(n,d,r) such that w⊏z⊏w′. Hence, w′⋗w.
Case
2. Let us assume that in w there is a minus singleton pile bj, for some 1≤j≤n-r. Since ar+1=r>0, 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. Applying Rule 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′∈P(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∈P(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 P(n,d,r). This implies that w′ covers w in P(n,d,r).
Case
3. If 1≤j≤n-r and w has a minus step at j, we apply Rule R3 to w on the minus 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 step at j, we have -bj+bj-1=|bj|-|bj-1|≥1, therefore w′∈P(n,r) because 0≥bj-1≥bj+1>bj≥bj+1 and ||w′||=d since bj≤-2 implies bj+1<0. As in Case 1, we note that w′ covers w in P(n,d,r) because they differ between them only for a grain in the place j. We now must show that {w′∈P(n,d,r):w′⋗w}⊆∇(w). Let w′′=ar′′⋯a1′′∣b1′′⋯bn-r′′ be a generic element of P(n,d,r) such that w′′⊐w. If we show that there exists an element w′=ar′⋯a1′∣b1′⋯bn-r′ of P(n,d,r) such that w′∈∇(w) and w′′⊒w′, we complete the proof of the theorem. 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. We assume that ai′′>ai and ai+1≥ai+1 for some i∈{r-1,…,1}. In this case, we can apply Rule R1 in the place i to obtain w′=w→1 such that w′′⊒w′.
Case B. We assume that ai′′>ai and ai+1=ai for some i∈{r-1,…,1}. In this case, we have ai+1′′≥ai′′>ai=ai+1, that is, ai+1′′≥ai+1+1; therefore if ai+2≥ai+1+1, we can apply Rule R1 in the place i+1 to obtain w′, otherwise we have ai+2=ai+1=ai. Iterating this procedure, to each step k≥1 we can apply Rule R1  in the place i+k to obtain w′ or it necessarily results that ai+k=⋯=ai+1=ai. Hence, if for no one k we can apply Rule R1 in the place i+k, we necessarily arrive to the condition ar=⋯=ai+1=ai. Since r≥ai′′>ai, it must be ar<r; therefore, we can apply Rule R1 in the place r to obtain ar′=ar+1, with ar′′≥ar′ because ar′′≥⋯≥ai′′>ai=⋯=ar.
Case C. We assume that ar′′>ar. In this case, we can apply Rule R1 in the place r.
Case D. We assume that 0>bj′′>bj, for some j∈{1,…,n-r}. In this case, we can apply Rule R3 in the place j.
Case E. We assume that 0=bj′′>bj and bj≤-2, for some j∈{1,…,n-r}. Also in this case, we can apply Rule R3 in the place j.
Case F. We assume that 0=bj′′>bj=-1, for some j∈{1,…,n-r}. In this case, the number of negative parts of w′′ is strictly lower than the number of negative parts of w, and since ||w||=||w′′||=d, it follows that there exists at least one index i∈{1,…,r} such that ai′′>0 and ai=0. We choose then such index i maximal, so that we have i=r or i≤r-1 and ai+1>0.
We suppose at first thati=r. In this case, we have ar′′≥1 and 0=ar=⋯=a1; therefore, we can apply Rule R2 to move the “negative" grain from the place j into the place r, so that the (n,r)-partition w′=100⋯0∣0⋯0bj+1⋯n-r is such that ||w′||=d and w′′⊒w′.
Ifi≤r-1 and ai+1>0, we apply again Rule R2 to move the “negative" grain from the place j into the place i, so that the (n,r)-partition w′=ar⋯ai+11⋯0∣0⋯0bj+1⋯n-r is such that ||w′||=d and w′′⊒w′.An analogous statement of the previous theorem was proven in [36] for the sublattice of all the signed integer partitions of P(n,d,r) having positive and negative parts all distinct between them. Below, we draw the Hasse diagram of the lattice P(4,3,2) by using the evolution Rules R1,R2, and R3 starting from the minimum element of this lattice, which is 10∣22. We label a generic edge of the next diagram with the symbol k if it leads to a production that uses the Rule Rk, for k∈{1,2,3}(19)


## 3.1.  Evolution Rules

Rule
R
1
. If the ith-plus pile has at least one grain, and if w has a plus step at i+1, then one grain must be added on the ith-plus pile(15)Rule
R
2. If there are some minus singleton piles, then the first from the left of them must be shifted to the side of the lowest not empty plus pile(16)Rule
R
3
. One grain must be deleted from the jth-minus pile if w has a minus step at j and |bj|>1(17)Remark 6.
(i) In the previous rule, the lowest not empty plus pile can also be the invisible column in the placer+1. In this case, all the plus piles are empty, and an eventual minus singleton pile must be shifted in the place r.
(ii) We take implicitly for intended that the shift of one minus singleton pile into a plus singleton pile can be made if the number of plus piles (excludingar+1=r) with at least a grain is less than r (otherwise we obtain a configuration that does not belong to P(n,d,r)).We writew→kw′ (or w′=w→k) to denote that w′ is an n-tuple of integers obtained from w applying Rule Rk, for k=1,2,3. We also set
(18)∇(w)={w′:w⟶kw′,k=1,2,3}.Theorem 7.
Ifw∈P(n,d,r), then ∇(w)={w′∈P(n,d,r):w′⋗w}.Proof.
We start to show that∇(w)⊆{w′∈P(n,d,r):w′⋗w}. Let w=ar⋯a1∣b1⋯bn-r∈P(n,d,r) and ar+1=r be the invisible pile in the place r+1. We distinguish the three possible cases related to the previous rules.
Case
1. Let us assume that r≥i≥1, ai≠0 and that w has a plus step 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 step at i+1, we have ai+1-ai≥1; hence, ai+1≥ai+1>ai≥ai-1, and this implies that w′∈P(n,d,r). We must show now that w′ covers w in P(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∈P(n,d,r) such that w⊏z⊏w′. Hence, w′⋗w.
Case
2. Let us assume that in w there is a minus singleton pile bj, for some 1≤j≤n-r. Since ar+1=r>0, 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. Applying Rule 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′∈P(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∈P(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 P(n,d,r). This implies that w′ covers w in P(n,d,r).
Case
3. If 1≤j≤n-r and w has a minus step at j, we apply Rule R3 to w on the minus 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 step at j, we have -bj+bj-1=|bj|-|bj-1|≥1, therefore w′∈P(n,r) because 0≥bj-1≥bj+1>bj≥bj+1 and ||w′||=d since bj≤-2 implies bj+1<0. As in Case 1, we note that w′ covers w in P(n,d,r) because they differ between them only for a grain in the place j. We now must show that {w′∈P(n,d,r):w′⋗w}⊆∇(w). Let w′′=ar′′⋯a1′′∣b1′′⋯bn-r′′ be a generic element of P(n,d,r) such that w′′⊐w. If we show that there exists an element w′=ar′⋯a1′∣b1′⋯bn-r′ of P(n,d,r) such that w′∈∇(w) and w′′⊒w′, we complete the proof of the theorem. 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. We assume that ai′′>ai and ai+1≥ai+1 for some i∈{r-1,…,1}. In this case, we can apply Rule R1 in the place i to obtain w′=w→1 such that w′′⊒w′.
Case B. We assume that ai′′>ai and ai+1=ai for some i∈{r-1,…,1}. In this case, we have ai+1′′≥ai′′>ai=ai+1, that is, ai+1′′≥ai+1+1; therefore if ai+2≥ai+1+1, we can apply Rule R1 in the place i+1 to obtain w′, otherwise we have ai+2=ai+1=ai. Iterating this procedure, to each step k≥1 we can apply Rule R1  in the place i+k to obtain w′ or it necessarily results that ai+k=⋯=ai+1=ai. Hence, if for no one k we can apply Rule R1 in the place i+k, we necessarily arrive to the condition ar=⋯=ai+1=ai. Since r≥ai′′>ai, it must be ar<r; therefore, we can apply Rule R1 in the place r to obtain ar′=ar+1, with ar′′≥ar′ because ar′′≥⋯≥ai′′>ai=⋯=ar.
Case C. We assume that ar′′>ar. In this case, we can apply Rule R1 in the place r.
Case D. We assume that 0>bj′′>bj, for some j∈{1,…,n-r}. In this case, we can apply Rule R3 in the place j.
Case E. We assume that 0=bj′′>bj and bj≤-2, for some j∈{1,…,n-r}. Also in this case, we can apply Rule R3 in the place j.
Case F. We assume that 0=bj′′>bj=-1, for some j∈{1,…,n-r}. In this case, the number of negative parts of w′′ is strictly lower than the number of negative parts of w, and since ||w||=||w′′||=d, it follows that there exists at least one index i∈{1,…,r} such that ai′′>0 and ai=0. We choose then such index i maximal, so that we have i=r or i≤r-1 and ai+1>0.
We suppose at first thati=r. In this case, we have ar′′≥1 and 0=ar=⋯=a1; therefore, we can apply Rule R2 to move the “negative" grain from the place j into the place r, so that the (n,r)-partition w′=100⋯0∣0⋯0bj+1⋯n-r is such that ||w′||=d and w′′⊒w′.
Ifi≤r-1 and ai+1>0, we apply again Rule R2 to move the “negative" grain from the place j into the place i, so that the (n,r)-partition w′=ar⋯ai+11⋯0∣0⋯0bj+1⋯n-r is such that ||w′||=d and w′′⊒w′.An analogous statement of the previous theorem was proven in [36] for the sublattice of all the signed integer partitions of P(n,d,r) having positive and negative parts all distinct between them. Below, we draw the Hasse diagram of the lattice P(4,3,2) by using the evolution Rules R1,R2, and R3 starting from the minimum element of this lattice, which is 10∣22. We label a generic edge of the next diagram with the symbol k if it leads to a production that uses the Rule Rk, for k∈{1,2,3}(19)


## 4. Sequential and Parallel Dynamics inP(n,d,r)

In this section, we study the parallel dynamic of the modelP(n,d,r). In such a context, we call configuration a generic element of P(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, and R3) at most one evolution rule, hence our model is deterministic. We denote by Tseq(w) and Tpar(w) the number of time steps required to reach 1^ starting from the configuration w, using, respectively, the sequential or the parallel updating scheme. Obviously Tseq(w) is independent of the order in which the sites are updated because P(n,d,r) is a finite distributive, and hence also a graded lattice (let us note that P(n,d,r) is distributive because it is a sublattice of the distributive lattice P(n,r). In the next proposition, we determine the rank function of P(n,d,r).Proposition 8.
The mapρ:P(n,d,r)→ℕ such that ρ(w)=∑‍(w)-∑‍(0^)-(|w|>-|0^|>) is the rank function of P(n,d,r).Proof.
We denote byϱ the rank function of the graded lattice P(n,r). If w and w′ are two (n,r)-signed partitions and w⋗w′, then ∑‍(w)=∑‍(w′)+1. It follows that ϱ(w)=∑‍(w)-∑‍(0^), for each w∈P(n,r). Let now w⋗wt⋗⋯⋗w1⋗0^ be any saturated chain from 0^ to w in the lattice P(n,d,r). 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 one only element ul∈P(n,r)∖P(n,d,r). This means that ϱ(w)=(t+1)+k, that is, ρ(w)=t+1=ϱ(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.By using the rank function, we can compute the sequential convergence time of any elementw∈P(n,d,r) as in the following:
(20)Tseq(w)=ρ(1^)-ρ(w).In particular, if we denote byrank(P(n,d,r)) the rank of the lattice P(n,d,r), then Tseq(0^)=ρ(1^)-ρ(0^)=ρ(1^)=rank(P(n,d,r)). In the next proposition, we compute this number.Proposition 9.
the following result holds:(21)Tseq(0^)={d(n-1)ifd≤randd≤n-r,dr-d+(n-r)2ifr≥d≥n-r,d(n-r)-d+r2ifn-r≥d≥r,r2+(n-r)2-difd≥randd≥n-r.Proof.
The minimal and maximal elements inP(n,d,r) are, respectively,
(22)0^:={0⋯0∣0⋯0(n-r)⋯(n-r)ifn-r≥d,1⋯10⋯0∣(n-r)⋯(n-r)ifd≥n-r,1^:={r⋯r0⋯0∣0⋯0ifr≥d,r⋯r∣0⋯01⋯1ifd≥r.
Then,
(23)∑‍(0^):={d(r-n)ifn-r≤d,d-n+r+(n-r)(r-n)ifd≤n-r,∑‍(1^):={drifr≤d,r2+r-difd≤r,
while the number of positive parts in 0^ and 1^ is, respectively,
(24)|0^|>:={0ifn-r≤d,d-n+rifd≤n-r,|1^|>:={difr≤d,rifd≤r.
The thesis follows then from simple arithmetic calculations and from Proposition 8, because rank(P(n,d,r))=ρ(1^).The next theorem is the main result of this section. Here we determine the parallel rank of the latticeP(n,d,r), for all the values of n, d, and r. In the proof of the next theorem, we also determine the fundamental sequence of P(n,d,r) in almost all the values of n, d, and r. We do not provide the construction of the fundamental sequence for all the parameters n, d, and r because several cases have similar constructions. However, for completeness, in Tables 1 and 2 we provide a complete description of the parallel rank value and of the fundamental sequence for all the values n, d, and r.Theorem 10.
(I)
Ifd≤min{r,n-r}, Tpar(0^)=n+d-2.
(II)
Ifr≥d≥2(n-r), Tpar(0^)=d+r-2.
(III)
Ifr≥d≥n-r and 2(n-r)≥d≥n-r, Tpar(0^)=2n-r-2.
(IV)
Ifn-r≥d≥2r, Tpar(0^)=d+n-r-2.
(V)
Ifn-r≥d≥r and 2r≥d≥r, Tpar(0^)=n+r-2.
(VI)
Ifmin{2r,2(n-r)}≥d≥max{r,n-r}, Tpar(0^)=2n-d-2.
(VII)
If2r>d≥2(n-r) and d≥max{r,n-r}, Tpar(0^)=2r-2.
(VIII)
If2(n-r)>d≥2r and d≥max{r,n-r}, Tpar(0^)=2(n-r)-2.Proof.
In all cases, let us denote the sequence of configurations as in (1).
Case I
(
d
≤
min
{
r
,
n
-
r
}
)
. If d≤min{r,n-r}, then 0^=0⋯0∣0⋯0(n-r)⋯(n-r) and 1^=r⋯r0⋯0∣0⋯0. Therefore,
(25)0^⇉〈(0,0,1),(0,0,2),…,(0,0,d-1)〉0⋯0∣0⋯0(n-r-d+1)⋯(n-r):=w1.
Starting from w1, we obtain
(26)w1⇉〈(0,0,d),(0,0,d),…,(0,0,d)〉0⋯0∣0⋯01⋯d:=w2,
where (0,0,d) is repeated n-r-d times. The next steps are
(27)w2⇉〈(0,1,d-1),(1,1,d-2),…,(d-2,1,1),(d-1,1,0)〉d(d-1),⋯10⋯0∣0⋯0:=w3,w3⇉〈(d,0,0),…,(d,0,0)〉r(r-1)⋯(r-d+1)0⋯0∣0⋯0:=w4,
where (d,0,0) is repeated r-d times. Finally, we have
(28)w4⇉〈(d-1,0,0),(d-2,0,0)⋯,(2,0,0),(1,0,0)〉r⋯r0⋯0∣0⋯0=1^.
From the previous computations, it follows that the fundamental sequence of P(n,d,r) is
(29)(1,2,…,d-1,d,…,d,d-1,…,1),
where the integer d is repeated exactly n-d times; hence, Tpar(0^)=n+d-2. Let us note that the sequence (29) is unimodal and symmetric.
Case II
(
r
≥
d
≥
2
(
n
-
r
)
)
. In this case, 0^=1⋯10⋯0∣(n-r)⋯(n-r) and 1^=r⋯r0⋯0∣0⋯0. Since d≥2(n-r), we have d-n+r≥n-r therefore,
(30)0^⇉〈(1,0,1),(2,0,2),…,(n-r-1,0,n-r-1)〉w1,
with w1:=(n-r)(n-r-1)⋯11⋯10⋯0∣12⋯(n-r), where 1 is repeated exactly d-2n+2r+1 times.
Sincer≥2(n-r), by starting from w1 we obtain
(31)w1⇉〈(n-r,1,n-r-1),(n-r+1,1,n-r-2),…,(2n-2r-1,1,0)〉w2,
with w2:=(2n-2r)(2n-2r-1)⋯11⋯10⋯0∣0⋯0, where 1 is repeated exactly d-2n+2r+1 times.
Now, fromw2 we have
(32)w2⇉〈(2n-2r,0,0),(2n-2r-1,0,0),…,(d-1,0,0)〉d(d-1)⋯10⋯0∣0⋯0:=w3.
At this point we obtain
(33)w2⇉〈(d,0,0),…,(d,0,0)〉r(r-1)⋯(r-d+1)0⋯0∣0⋯0:=w4,
where (d,0,0) is repeated r-d times. Finally, we have
(34)w4⇉〈(d-1,0,0),(d-2,0,0)⋯,(2,0,0),(1,0,0)〉r⋯r0⋯0∣0⋯0=1^.
Thus, the parallel rank Tpar(0^) is equal to d+r-2, and the fundamental sequence of P(n,d,r) is
(35)(2,4,…,2(n-r-1),2(n-r),…,2(n-r),2(n-r)+1,…,d-1,d,…,d,d-1,…1),
and so P(n,d,r) in this case is parallel unimodal but not  parallel symmetric.
In a similar way, we can compute in all other cases the parallel rank and the fundamental sequence. The details are left to the interested reader. Here are the results.
Case III
(
r
≥
d
≥
n
-
r
and
2
(
n
-
r
)
≥
d
≥
n
-
r
)
. In this case, Tpar(0^)=2n-r-2, and the fundamental sequence is
(36)(2,4,…,2(d-n+r-1),2(d-n+r),2(d-n+r)+1,…,d-1,d,…,d,d-1,…,1).It isunimodal and not symmetric.
Case IV
(
n
-
r
≥
d
≥
2
r
)
. In this case, Tpar(0^)=d+n-r-2 and the fundamental sequence is
(37)(1,2,…,d-1,d,…,d,d-2,…,d-2r,d-2r-1,…,1).
It is unimodal, and if r≠0, it isnot symmetric.
Case V
(
n
-
r
≥
d
≥
r
and
2
r
≥
d
≥
r
). In this case, Tpar(0^)=n+r-2. The fundamental sequence is
(38)(1,2,…,d-1,d,…,d,d-2,…,2r-d,2r-d-1,…,1).
It is unimodal, and if d≠r, it is not symmetric.
Case VI
(
min
{
2
r
,
2
(
n
-
r
)
}
≥
d
≥
max
{
r
,
n
-
r
}
). In this case, Tpar(0^)=2n-d-2. The fundamental sequence depends on the relations between r, n-r, and d in the following way.(VI.1)
Ifr≥n-r and 2d-1≤3(n-r), the fundamental sequence is
(39)(2,4,…,2(d-n+r),2(d-n+r)+1,…,d,…,d,d-1,…,n-r,…,n-r,n-r-1,…,n-d,…,n-d,n-d-1,…,1).(VI.2)
Ifr≥n-r, 2d-1>3(n-r), and d≤3(n-r)-r+1, the fundamental sequence is
(40)(2,…,2(d-n+r),2(d-n+r)+1,…,d,…,d,d-1,…,2(d-n+r),2(d-n+r-1),…,4n-4r-2d,4n-4r-2d-1,…,n-d,…,n-d,n-d-1,…,1).(VI.3)
Ifr≥n-r, 2d-1>3(n-r) and d>3(n-r)-r+1, the fundamental sequence is
(41)(2,…,2(d-n+r),2(d-n+r)+1,…,d,…,d,d-1,…,2(d-n+r),2(d-n+r)-1,2(d-n+r)-3,…,4r-2n-1,4r-2n-2,…,n-d,…,n-d,n-d-1,…,1).(VI.4)
Ifr≤n-r and d≤2n-3r+1, the fundamental sequence is
(42)(2,4,…,2(d-n+r),2(d-n+r)+1,…,d-n+2r-1,…,d-n+2r-1,d-n+2r,…,n-r,…,n-r,n-r-1,…,2n-d-2r,2n-d-2r-2,…,2r-d,2r-d-1,…,1).(VI.5)
Ifr≤n-r, d>2n-3r+1, and 2d-1≤3(n-r), the fundamental sequence is
(43)(2,4,…,2(d-n+r),2(d-n+r)+1,…,d-n+2r-1,…,d-n+2r-1,d-n+2r-2,…,n-r,…,n-r,n-r-1,…,2n-d-2r,2n-d-2r-2,…,2r-d,2r-d-1,…,1).(VI.6)
Ifr≤n-r, d>2n-3r+1, and 2d-1>3(n-r), the fundamental sequence is
(44)(2,4,…,2(d-n+r),2(d-n+r)+1,…,d-n+2r-1,…,d-n+2r-1,d-n+2r-2,…,n-r,…,n-r,n-r-1,…,2n-d-2r,2n-d-2r-2,…,2r-d,2r-d-1,…,1).
In those casesP(n,d,r) is  parallel unimodal but not parallel symmetric.
Case VII
(
2
r
>
d
≥
2
(
n
-
r
)
and
d
≥
max
{
r
,
n
-
r
}
). In this case, the parallel rank is Tpar(0^)=2n-d-2. The fundamental sequence depends on the relations between r, n-r, and d in the following way.(VII.1)
If3r≤2(n-r), the fundamental sequence is
(45)(2,4,…,2(n-r),…,2(n-r),2(n-r)-1,…,2(n-r)-1,2(n-r)-2,2(n-r)-4,…,4r-2n,4r-2n-1,…,1).
In this case P(n,d,r) is  parallel unimodal but not  parallel symmetric.(VII.2)
If3r>2(n-r), the fundamental sequence is
(46)(2,4,…,2(n-r),…,2(n-r),2(n-r)-1,…,2(n-r)-1,2(n-r),2(n-r)+1,…,r-1,r-1,…,1).Therefore, in this case,  P(n,d,r), it is not  parallel unimodal and it is not parallel symmetric. This is the only case in which the fundamental sequence is not unimodal (see Example 11).
Case VIII
(
2
(
n
-
r
)
>
d
≥
2
r
and
d
≥
max
{
r
,
n
-
r
}
). In this case, the parallel rank is Tpar(0^)=2n-d-2. The fundamental sequence depends on the relations between r, n-r, and d in the following way.(VIII.1)
Ifd≤2n-3r+1, the fundamental sequence is
(47)(2,4,…,2(d-n+r),2(d-n+r)+1,…,d-n+2r-1,…,d-n+2r-1,d-n+2r,…,n-r,…,n-r,n-r-1,…,2n-2r-d,2n-2r-d-2,…,d-2r,d-2r-1,…,1).(VIII.2)
Ifd>2n-3r+1 and 2d-1≥3(n-r), the fundamental sequence is
(48)(2,4,…,2(d-n+r),2(d-n+r)+1,…,d-n+2r-1,…,d-n+2r-1,d-n+2r-2,…,2(d-n+r),2(d-n+r-1),…,2(2n-2r-d),2(2n-2r-d)-1,…,2n-2r-d,2n-2r-d-2,…,d-2r,d-2r-1,…,1).(VIII.3)
Ifd>2n-3r+1 and 2d-1>3(n-r), the fundamental sequence is
(49)(2,4,…,2(d-n+r),2(d-n+r)+1,…,d-n+2r-1,…,d-n+2r-1,d-n+2r-2,…,n-r+1,n-r,…,n-r,n-r-1,…,2n-2r-d,2n-2r-d-2,…,d-2r,d-2r-1,…,1).
In these casesP(n,d,r) is  parallel unimodal but not  parallel symmetric.We summarize all the previous results in Tables1 and 2.Example 11.
Let us consider the latticeP(n,d,r) with n=7, d=6, and r=5. In this case, 2r>d≥2(n-r),d≥max{r,n-r}, and 3r>2(n-r). The fundamental chain is the following:(50)


## 5. Conclusions and Future Research Directions

In this work, we have introduced a refinement of the concept of parallel time convergence for a finite deterministic discrete dynamical modelX which also has a lattice structure. This new concept is the fundamental sequence of X. In particular, the length of the fundamental sequence is exactly the parallel time of convergence from the minimum to the maximum of X. In this paper, we have computed the fundamental sequence for two models whose configurations are signed integer partitions. The perspectives, for future research directions, are the following: to compute the fundamental sequence for more general models, to compare the properties of the fundamental sequence with the properties of other relevant combinatorial objects related to the order structure of X (e.g., the Whitney number sequence and the rank of X when X is graded), and to characterize the models whose fundamental sequence has some specific property (e.g., unimodality or symmetry).



---

*Source: 292143-2013-04-21.xml*