# A Discrete Dynamical Model of Signed Partitions

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

---

## Abstract

We use a discrete dynamical model with three evolution rules in order to analyze the structure of a partially ordered set of signed integer partitions whose main properties are actually not known. This model is related to the study of some extremal combinatorial sum problems.


---

## Body

## 1. Introduction

A dynamical system is by definition a system whose state changes with timet. We have a discrete dynamical system when t is an integer or a natural number, and the elements of the system can be obtained in the form ut+1=F(ut), where F is some global function which describes the evolution rule of the system (see [1]). In a series of very recent works, the theory of discrete dynamical systems has been applied in several contexts. In [2], the theory of discrete dynamical systems is applied in order to analyze some models of concurrent computing systems. In [3], a dynamical model of parallel computation on bi-infinite time scale with an approach similar to two-sided symbolic dynamics is constructed. In [4], the authors analyze the orbit structure of parallel discrete dynamical systems over directed dependency graphs, with Boolean functions as global functions. In [5], the authors extend the manner of defining the evolution update of discrete dynamical systems on Boolean functions, without limiting the local functions to being dependent restrictions of a global one. Finally, in [6] is given a complete characterization of the orbit structure of parallel discrete dynamical systems with maxterm and minterm Boolean functions as global functions. In [7], the authors have introduced the poset (S(n,d,r),⊑) of all the signed integer partitions r≥ar≥⋯≥a1≥0≥b1≥⋯≥bn-r≥-(n-r), where the positive parts and the negative parts are all distinct between them and the number of nonzero parts is exactly d. In this case, the partial order ⊑ is that on the components. The concept of signed integer partition has been introduced in [8] and studied in [9] from an arithmetical point of view. In [7, 10], it is shown that the structure of the lattice S(n,d,r) is strictly related to the study of some combinatorial extremal sum problems. In this paper, we study some particular type of signed partitions (specifically, of the signed partitions of S(n,d,r)) by adopting the interesting point of view of the discrete dynamical models. In particular, we analyze the lattice S(n,d,r) as a discrete dynamical model with three local evolution rules whose dynamics is studied in a sequential mode. The way to study a lattice of classical partitions as a discrete dynamic model having some particular evolution rules is implicit in [11], where Brylawski proposed a dynamical approach to study the lattice LB(n) of all the partitions of the fixed positive integer n with the dominance ordering. In such a context, a configuration of the system is represented by an ordered partition of an integer n, that is, a decreasing sequence a=(a1,…,an) having sum n, whose blocks of the corresponding Young diagram are considered as mobile sand grain, and the movement of a sand grain, respects the following rules.Rule 1 (vertical rule).
One grain can move from a column to the next column if the difference of height of these two columns is greater than or equal to 2.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, then one grain of the first column can slip to the last column.In this paper, we prove that the covering relation in the latticeS(n,d,r) is uniquely determined by three evolution rules of our discrete dynamical model. We articulate the proof of this result by contradiction by using only the first-order logic. This method of proof is very laborious; however, its advantage is that it can be easily implemented on a proof assistant checker based on the first-order logic (e.g., Mizar). The paper is articulated as follows. In Section 2, we recall some basic definitions and preliminary results, for example, the definition of S(n,d,r) and some of its properties. In Section 3, we explain how to see the signed partitions of S(n,d,r) as configurations of our discrete dynamical model and we also describe its evolution rules. In Section 4, we assume by contradiction that there is a generic element w′ of S(n,d,r) that covers another generic element w∈S(n,d,r) but w′ is not generated by w with none of our evolution rules. From this assumption we deduce several propositions and conditions that we use in order to prove our principal result, that is, Theorem 4.


## 2. Definitions and Preliminary Results

If(X,≤) is a poset and x,y∈X, we write y⋗x (orx⋖y) if y covers x. Now we briefly recall the definition of the lattice S(n,r) that we have introduced in [7] in a more formal context. Let n and r be two nonnegative integers such that r≤n.We call(n,r)-string a n-tuplet 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.If w is a (n,r)-string, we call parts of w the integers ar,…,a1,b1⋯bn-r, nonnegative parts of w the integers ar,…,a1, and nonpositive parts of w the integers b1⋯bn-r. We set w+=ar⋯a1| and w-=|b1⋯bn-r. In some cases, we do not distinguish between nonnegative and nonpositive parts of w, and we write more simply w=l1⋯ln instead of w=ar⋯a1|b1⋯bn-r. We also 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 minimal element 0⋯0|12⋯(n-r) and maximal element r(r-1)⋯21|0⋯0.We recall now the concept of involution poset (see [12, 13] 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 map c 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*. In [7], it 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}. Its easy to see that (S(n,d,r),⊑) is a sublattice of (S(n,r),⊑) and obviously |S(n,d,r)|=(nd).We callsigned Young diagrams (briefly SYD) an ordered couple D=D1:D2, where D1 is a Young diagram of an integer partition built with decreasing columns instead with decreasing rows, and D2 is a Young diagram of an integer partition built with increasing columns. In the sequel, we will call pile a column of a Young diagram and grain a square of a pile. For example,
(3)
is determined by the partitions 4331 and 113. If w=ar⋯a1|b1⋯bn-r∈S(n,r), we denote by D(w) the signed Young diagram D(w)=D+(w):D-(w), where D+(w) is the Young diagram of the partition (ar,…,a1) and D-(w) is the Young diagram of the partition (-b1,…,-bn-r). Now, if D=D1:D2 is a SYD, where (at,…,a1) is the decreasing partition having D1 as Young diagram and ((-b1),…,(-bs)) is the increasing partition having D2 as Young diagram, we set p(D)=at⋯a1|(-b1)⋯(-bs) and we call p(D) the signed partition ofD. We say that a signed Young diagram D is a (n,r)-SYD if  it results that p(D)∈S(n,r) and we denote with YS(n,r) the set of all the (n,r)-SYD. It is clear that the map ϕ:w↦D(w) is a bijection between S(n,r) and YS(n,r), whose inverse function is the map ψ:D↦p(D); therefore, in the sequel, we will identify the elements of S(n,r) with the (n,r)-SYDs of YS(n,r). If A and B are two usual Young diagrams, we set A⊆B if A is a subdiagram of B. If D=D1:D2 and D′=D1′:D2′ are two SYDs, we set
(4)D⊑D′⟺D1⊆D1′,D2⊇D2′.
Therefore, it is clear that we can identify (S(n,r),⊑) with (YS(n,r),⊑). Now we set YS(n,d,r)={D(w):w∈S(n,d,r)}. Obviously we can identify (YS(n,d,r),⊑) with (S(n,d,r),⊑). If (H) is a statement, in the sequel we denote by ¬(H) the negation of (H).


## 3. Description of the Evolution Rules

In our dynamic model, the set of all configurations is exactlyYS(n,d,r). Our goal is to define some rules of evolution that starting from the minimum of YS(n,d,r) allow us to reconstruct the Hasse diagram of YS(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) and D=D(w)=D+(w):D-(w). If 1≤i≤r, we call ith-plus pile of D, and we denote it by C+(i,D), the ith pile of D+(w) that corresponds to part ai of w and, if 1≤j≤n-r, we call jth-minus pile of D, and we denote it by C-(j,D), the jth pile of D-(w) that corresponds to part bj of w. We call the pile C+(i,D)  plus  singleton  pile if ai=1 and C-(j,D)minus  singleton  pile if bj=1. Let us note that if there exists a plus singleton pile, then it is necessarily unique, analogously for a minus singleton pile. If 1<i≤r, 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.
When we apply the following rules to one elementw∈S(n,r), we impose that there is an “invisible” extra pile in the imaginary place (r+1) of D+(w) having exactly r+1 grains. This is only a formal trick for decreas the number of rules necessary for our model; therefore, the (r+1)th pile must be not considered as a part of w.


### 3.1. Evolution Rules

Rule 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:
(5)Rule 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 non empty plus pile:(6)Rule 3.
One grain must be deleted from thejth-minus pile if w has a minus cliff at j:
(7)Remark 2.
(i) Under the hypothesis in Rule3, the jth plus must have at least 2 grains.
(ii) In Rule2, the lowest non empty plus pile can also be the invisible column in the place r+1. In this case, all the plus piles are empty and a possible minus singleton pile must be shifted in the place r.


## 3.1. Evolution Rules

Rule 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:
(5)Rule 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 non empty plus pile:(6)Rule 3.
One grain must be deleted from thejth-minus pile if w has a minus cliff at j:
(7)Remark 2.
(i) Under the hypothesis in Rule3, the jth plus must have at least 2 grains.
(ii) In Rule2, the lowest non empty plus pile can also be the invisible column in the place r+1. In this case, all the plus piles are empty and a possible minus singleton pile must be shifted in the place r.


## 4. Main Result

In the sequel, we writew→kw′ (or w′=w→k) to denote that w′ is an n-tuplet of integers obtained from w applying the Rule k, for k=1,2,3, and that ¬(w→kw′) if the condition w→kw′ is false. We also set
(8)∇(w)={w′:w⟶kw′,k=1,2,3}.Proposition 3.
Ifw∈S(n,d,r), then ∇(w)⊆{w′∈S(n,d,r):w′⋗w}.Proof.
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.
Case  1. 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.
Case  2. Let us assume that in D(w) there is not a plus singleton pile and that there is a minus singleton pile (we say C-(j,D), 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(w) has a plus singleton pile). Applying Rule 2 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).
Case  3. If 1<j≤n-r and w has a minus cliff at j, we apply Rule 3 to w on the pile C-(j,D) 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 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.The main result of this paper is to prove that ifw,w′∈S(n,d,r), then w′ covers w in S(n,d,r) if and only if w→kw′ for some k∈{1,2,3}. Obviously this result can be reformulated as follows.Theorem 4.
Ifw∈S(n,d,r), then ∇(w)={w′∈S(n,d,r):w′⋗w}.By Proposition3, to prove Theorem 4, it suffices to show that {w′∈S(n,d,r):w′⋗w}⊆∇(w). To show this inclusion, we proceed by contradiction as follows. We start with the following hypotheses:
(9)w,w′∈S(n,d,r),w=ar⋯a1∣b1⋯bn-r,w′=ar′⋯a1′∣b1′⋯bn-r′,w′⋗w
and we also assume that
(10)¬(w⟶kw′)foreachk=1,2,3.
Then the proof of Theorem 4 will consist into show that the hypotheses (9) and the conditions (10) always lead to contradictory cases, so that it must be necessarily verified the inclusion {w′∈S(n,d,r):w′⋗w}⊆∇(w).We will articulate the proof of Theorem4 in several cases. Each possible case will be placed in the form of a proposition and we will obtain a contradiction in all cases, showing, hence, the thesis of the theorem. Before proceeding, let us note that in some cases we also use the alternative notations w=l1⋯ln and w′=l1′⋯ln′.We set now(11)Ω1(w)={i∈{1,…,r}:ai>0,ai+1-ai≥2},Ω3(w)={j∈{2,…,n-r}:bj-1-bj≥2},Λ+(w,w′)={h∈{1,…,r}:ah′>ah},Λ-(w,w′)={l∈{1,…,n-r}:bl′>bl}.Formalization of Rules1, 2, and 3.The description of Rules1, 2, and 3 in terms of parts of w and w′ is the following:(1)
w→1w′ is equivalent toΩ1(w)≠∅ AND (∃i∈Ω1(w):(ai′=ai+1) AND (Λ+(w,w′)∖{i}=Λ-(w,w′)=∅));(2)
w→2w′ is equivalent to(forallk∈{1,…,r}ak≠1) AND(∃j∈{1,…,n-r} such that bj=-1) AND(∃i∈{1,…,r} such that ai+1>0, ai=0) AND(Λ+(w,w′)∖{i}=Λ-(w,w′)∖{j}=∅, ai′=1, bj′=0);(3)
w→3w′ is equivalent toΩ3(w)≠∅ AND (∃j∈Ω3(w):(bj′=bj+1) AND (Λ+(w,w′)=Λ-(w,w′)∖{j}=∅)).Negation of Rules1, 2, and 3.
(1)
¬
(
w
→
1
w
′
)
⇔ [(1A′) OR (1B)],
where
(1B)
is (Ω1(w)=∅),
(1A′)
is [Ω1(w)≠∅ AND (foralli∈Ω1(w) (ai′≠ai+1) OR (Λ+(w,w′)∖{i}≠∅ OR Λ-(w,w′)≠∅))].
(2)
¬
(
w
→
2
w
′
)
⇔ [(2A′) OR (2B) OR (2C) OR (2D)],
where
(2A′)
is (forallk∈{1,…,r}ak≠1) AND
(∃j∈{1,…,n-r} such that bj=-1) AND
(∃i∈{1,…,r} such that ai+1>0,ai=0) AND ((Λ+(w,w′)∖{i}≠∅ OR Λ-(w,w′)∖{j}≠∅) OR ai′≠1 OR bj′≠0);
(2B)
is (∃k∈{1,…,r} such that ak=1);
(2C)
is (forallj∈{1,…,n-r}bj≠-1);
(2D)
is (foralli∈{1,…,r}ai+1=0 OR ai>0).
(3)
¬
(
w
→
3
w
′
)
⇔ [(3A′) OR (3B)],
where
(3B)
is (Ω3(w)=∅);
(3A′)
is [Ω3(w)≠∅ AND (forallj∈Ω3(w) (bj′≠bj+1) OR (Λ+(w,w′)≠∅ OR Λ-(w,w′)∖{j}≠∅))].
we set
(12)(1.1b):w=00⋯0∣b1⋯bn-r,(13)(1.2b):w=r(r-1)⋯(k+1)k⋯0∣b1⋯bn-rforsomek∈{1,…,r}.Proposition 5.
Consider (1B)⇒ ((1.1b) OR (1.2b)).Proof.
The conditionΩ1(w)=∅ means that for all i∈{1,…,r},ai=0 or 0≤ai+1-ai≤1 (i.e., ai+1-ai=0 or ai+1-ai=1). We have then the following possibilities:(j)
ai=0;(jj)
ai+1-ai=0 (and therefore ai+1=ai=0 since w∈S(n,r));(jjj)
ai+1=ai+1. If ai=0 for all i∈{1,…,r} then (12) holds. Let us assume therefore that k∈{1,…,r} is the smallest index such that ak>0; hence, ar>ar-1>⋯>ak+1>ak>0 and ak-1=⋯=a1=0. This means that for all indexes i∈{r,r-1,…,k+1,k} holds necessarily (jjj). In particular, for i=r we have r+1=ar+1=ar+1; hence, ar=r. Now, if i=r-1, r=ar=ar-1+1, that is, ar-1=r-1. Iterating (13) follows.We set(14)(2.1d):w=r(r-1)⋯21∣b1⋯bn-r.Proposition 6.
Consider (2D)⇔ (2.1d).Proof.
By (2D), if we takei=r, we have ar+1=0 or ar>0; therefore, it is necessarily ar>0 because by hypothesis, ar+1=r+1>0. Thus, still by (2D), for i=r-1, we have a(r-1)+1=ar=0 or ar-1>0; therefore, it must be ar-1>0. By iterating, we can deduce that ar>0,ar-1>0,…, a1>0; hence, a1=1, a2=2,…, ar=r because w is an element of S(n,r), that is, exactly (14). On the other side, if w=r(r-1)⋯21|b1⋯bn-r, then it is immediate to note that (2D) is verified.We set(15)(3.1b):w=ar⋯a1∣00⋯0,(16)(3.2b):w=ar⋯a1∣00⋯0(-1)(-2)⋯(-l)forsomel∈{1,…,n-r}.Proposition 7.
Consider (3B)⇒ ((3.1b) OR (3.2b)).Proof.
The conditionΩ3(w)=∅ means that for all j∈{2,…,n-r},0≤bj-1-bj≤1 (i.e., bj-1-bj=0 or bj-1-bi=1). We have then the following possibilities:(i)
bj-1-bj=0 (and therefore bj-1=bi=0 since w∈S(n,r));(ii)
bj-1=bj+1.
If (i) holds for allj∈{2,…,n-r}, then (15) holds. We can assume therefore that k∈{2,…,n-r} is the smallest index such that (ii) holds. Let us observe then that if in a place j∈{2,…,n-r}, (ii) holds; then also in the places j+1,…,n-r, (ii) holds. In fact, if bj=bj-1-1 and by absurd bj=bj+1=0, then bj-1=1 which is a contradiction because 0≥bj-1. Therefore, if (ii) holds in j, then it also holds in j+1, and therefore, by iteration, it holds for j+1,j+2,…,n-r. Now we assume at first that k=2. In this case, (ii) holds for all indexes in {2,…,n-r}; therefore, b1=0 or b1=-1 and b2=b1-1, b3=b2-1⋯. If b1=0, then w=ar⋯a1|0(-1)(-2)⋯(-(n-r)+1) and if b1=-1, then w=ar⋯a1|(-1)(-2)⋯(-(n-r)); thus in both cases (ii) holds. Let now k≥3. Then bk-1=bk-2=0 (because in the place k-1 (i) holds) and hence 0=bk-1=bk-2=⋯=b2=b1. Moreover, since (i) holds in the places k,k+1,…,n-r, we have bk=bk-1-1=0-1=-1; therefore, bk+1=bk-1=-2,…, bn-r=bn-r-1-1=-(n-r-k)-1=-l, where l=n-r-k+1. This completes the proof.Proposition 8.
Consider (3.1b)⇒ (w-=w-′=∣00⋯0).Proof.
Sincew⊏w′, it must be 0≥bj′≥bj, where bj=0 for all j∈{1,…,n-r} because (15) implies w=ar⋯a1|00⋯0. Therefore, bj=bj′=0 for all j∈{1,…,n-r}; that is, w′=ar′⋯a1′∣00⋯0.Proposition 9.
Consider(i)
(1.1b) AND (2B)⇒absurd,(ii)
(1.1b) AND (2.1d)⇒absurd,(iii)
(2C) AND (3.2b)⇒absurd,(iv)
(1.1b) AND (3.1b)⇒absurd,(v)
(1.2b) AND (3.1b)⇒absurd.Proof.
(i), (ii), and (iii) are obvious.(iv)
By (12) and (15), it follows that w=0⋯0|0⋯0, absurd.(v)
By Proposition8, we have w-′=w-. Then, since w⊏w′, ∥w′∥=∥w∥ and w-′=w-, by (13) we deduce that w+′=w+. Hence, the absurd w′=w.Proposition 10.
Consider (1.2b) AND (2B)⇒ (2.1d).Proof.
By (2B), it follows that in (13) it must be k=1; therefore, w=r(r-1)⋯21|b1⋯bn-r.Proposition 11.
Consider (2.1d) AND (3.2b)⇒ absurd.Proof.
By (14), it is immediate to observe that w+′=w+ because w⊏w′. Then by (16), since w+′=w+, ∥w-′∥=∥w-∥ and w⊏w′, it must also be w-′=|00⋯0(-1)(-2)⋯(-l). Hence, we obtain w=w′, absurd.Proposition 12.
Consider (2A′) ⇒ absurd.Proof.
We set(F)
[(forallk∈{1,…,r}ak≠1) AND (∃j∈{1,…,n-r} such that bj=-1) AND (∃i∈{1,…,r} such that ai+1>0,ai=0)];(G)
(Λ+(w,w′)∖{i}≠∅ OR Λ-(w,w′)∖{j}≠∅);(H)
(ai′≠1 OR bj′≠0).
Then (2A′) is equivalent to ((F) AND (G)) OR ((F) AND (H)). We show at first that ((F) AND (H)) leads to a contradiction. Next we show that ((F) AND (G) AND ¬(H)) also leads to an absurd. This will prove the thesis;
((F) AND (H))⇒ absurd.
By (F), it follows thatw satisfies the hypothesis of Rule 2; therefore, by Proposition 3 we can take an element z∈S(n,d,r) such that z=w→2. As in the proof of the Case 2 in Proposition 3, it results that w and z must have the following form:
(17)w=ar⋯ai+100⋯0∣0⋯0(-1)bj+1⋯bn-r,(18)z=ar⋯ai+110⋯0∣0⋯00bj+1⋯bn-r,
where ai+1>1 and bj+1<-1. We distinguish now several cases.
(I) bj′≠0. Then bj′≤-1, and also bj′≥bj=-1 because w⊏w′; hence bj′=-1.
We note now that(19)ar′>0,…,ai+1′>0
because ar′≥ar>0,…,ai+1′≥ai+1>0. Moreover, since bj′=-1, it follows that
(20)-1=bj′>bj+1′>⋯>bn-r′
because w′∈S(n,r). Now, since w∈S(n,d,r), from the form of w it results that d=(r-i)+(n-r-j+1). Moreover, since also w′∈S(n,d,r), we have ∥w′∥=d=(r-i)+(n-r-j+1). Therefore, since in (19), there are exactly r-i inequalities and in (20) there are exactly n-r-j+1 inequalities; it follows that
(21)w′=ar′⋯ai+1′00⋯0∣0⋯0(-1)bj+1′⋯bn-r′.
(II) ai′=0. Since w⊏w′, by (17) we have two possible cases: w′ has the form (21) or
(22)w′=ar′⋯ai+1′00⋯0∣0⋯00bj+1′⋯bn-r′
with ai+1′≥ai+1>1 and 0≥bj+1′. If (22) holds, then ∥w′∥≤(r-i)+(n-r-j)=d-1, which is absurd because w′∈S(n,d,r); hence it must hold necessarily (21).
(III) ai′>1. Since w⊏w′ and d=∥w∥=∥w′∥, by (17) it follows that
(23)w′=ar′⋯ai+1′ai′0⋯0∣0⋯00bj+1′⋯bn-r′.
Then from the hypothesis ai′≥2 and by (18), we have w⊏z⊏w′, which is a contradiction.
Hence the unique possibility is thatw′ has the form (21). Since w′⋗w, we have ak′≥ak for k=r,…,i+2,i+1 and bl′≥bl for l=j+1,j+2,…,n-r. Moreover, at least one inequality of the type ak′>ak or the type bl′>bl must hold. We distinguish now the several cases.
(Δ1) We assume that a unique inequality of the type ap′>ap holds for some p=r,…,i+2,i+1. Therefore, we have ak′=ak for all k≠p and bl′=bl for all l=j+1,j+2,…,n-r. Then, since ap+1=ap+1′>ap′>ap>0 (let us note that the previous inequalities also hold if p=r because ar+1=r+1=ar+1′), we have that ap+1-ap≥2 and ap>0. Hence w satisfies the hypotheses of Rule 1 in the place p and so w→1u, where
(24)u=ar⋯ap+1(ap+1)ap-1⋯ai+10⋯0∣0⋯0(-1)bj+1⋯bn-r(=ar′⋯ap+1′(ap+1)ap-1′⋯ai+1′0⋯0∣0⋯0(-1)bj+1′⋯bn-r′),
with u∈S(n,d,r). Now, if ap′=ap+1, it results that w′=u; therefore, w→1w′, which is a contradiction with the hypothesis ¬(w→1w′). Otherwise, if ap+1<ap′, then we have w⊏u⊏w′, which is absurd because w′⋗w.
(Δ2) If a unique inequality of the type bq′>bq holds for some q=j+1,j+2,…,n-r, we deduce a contradiction as in the proof of the previous case by using Rule 3 instead of Rule 1.
(Δ3) We assume now that at least two strict inequalities among the ak′≥ak and bl′≥bl hold, and let us also assume that the first (by left) of such strict inequalities is ap′>ap for some p∈{r,…,i+1}. We consider then the following (n,r)-string:
(25)v=ar⋯ap+1(ap+1)ap-1⋯ai+10⋯0∣0⋯0(-1)bj+1⋯bn-r.
Since ap′>ap is the first strict inequality by left, we have ap+1′=ap+1 (also if p=r); hence ap+1=ap+1′>ap′≥ap+1>ap>ap-1 because ap>0; this implies that v∈S(n,r); therefore v∈S(n,d,r) because ∥v∥=∥w∥=d. Moreover, it is clear that w⊏v. Let us observe now that v⊏w′; in fact, by hypothesis, w′ must have at least another place q≠p where aq′>aq or bq′>bq and v differs by w only in the place p. This shows that w⊏v⊏w′, with v∈S(n,d,r), which is absurd because w′⋗w.
(Δ4) If at least two strict inequalities among the ak′≥ak and bl′≥bl hold and the first (by left) of such strict inequalities is bp′>bp for some p∈{j+1,j+2,…,n-r}, then we deduce a contradiction in the same way as in the previous case.
This concludes the proof that ((F) AND (H))⇒ absurd. To complete the proof we show now that ((F) AND (G) AND ¬(H)) ⇒ absurd.
Since (H) is false, we haveai′=1 and bj′=0; therefore, w has the form (17) and w′=ar′⋯ai+1′10⋯0|0⋯00bj+1′⋯bn-r′. We take z∈S(n,d,r) as in (18), so that w and z differ between them only in the places i,j and w⊏z. Moreover, since w′=ar′⋯ai+1′10⋯0|0⋯00bj+1′⋯bn-r′, by (G), (18), and (17) it follows that z⊏w′. Therefore, we obtain w⊏z⊏w′ that is in contrast with the hypothesis w′⋗w.We set now(26)(1A):Ω1(w)≠∅,∀i∈Ω1(w)ai′≠ai+1,(27)(3A):Ω3(w)≠∅,∀j∈Ω1(w)bj′≠bj+1.Proposition 13.
Consider(i)
(1A′)⇔(1A),(ii)
(3A′)⇔(3A).Proof.
(i) The implication⇐ is obvious. We assume now that (1A′) holds and there exists i∈Ω1(w) such that ai′=ai+1 and also that Λ+(w,w′)∖{i}≠∅ (i.e., there exists h≠i such that ah′>ah) or Λ-(w,w′)≠∅ (i.e., there exists l such that bl′>bl). Since i∈Ω1(w), we can apply Rule 1 to w and we can take z=w→1. By Proposition 3, we know that z∈S(n,d,r) and z⋗w. Moreover, since ah′>ah (h≠i) or bl′>bl, we also have z⊏w′; therefore, w⊏z⊏w′, which is in contrast with the hypothesis w′⋗w. Hence this proves that the condition ai′≠ai+1 must be verified for all i∈Ω1(w), which is exactly (26).
(ii) The proof is similar to (i) applying Rule3 to w instead of Rule 1.We set(28)(1a):Ω1(w)≠∅,∀i∈Ω1(w)ai′=ai,(29)(3a):Ω3(w)≠∅,∀j∈Ω3(w)bj′=bj.Proposition 14.
Consider(i)
(1A)⇒(1a),(ii)
(3A)⇒(3a).Proof.
(i) By (1A), we haveΩ1(w)≠∅, and by the definition of Ω1(w) this is equivalent to say that w satisfies the hypotheses of Rule 1 for some i∈{1,…,r}. Therefore, by Proposition 3, there exists an element zi∈S(n,d,r) such that w→1zi, where zi=ar⋯ai+1(ai+1)ai-1⋯a1|b1⋯bn-r and obviously w⊏zi. Since ai′≠ai+1, we distinguish two cases.(a)
ai′>ai+1. In this case w⊏zi⊏w′, that is in contrast with the hypothesis w′⋗w.(b)
ai′<ai+1. In this case ai′≤ai; hence ai′=ai because ai′≥ai from the hypothesis w′⋗w.
(ii) The proof of this case is similar to (i).Lemma 15.
Assume that (1a) holds. Ifq∈{2,3,…,r,r+1}, aq′=aq, and aq-1>0, then aq-1′=aq-1.Proof.
Ifq-1∈Ω1(w), then the thesis holds by the definition of (1a) in (28). We assume now that q-1∉Ω1(w). Then aq-1=0 or 0≤a(q-1)+1-aq-1=aq-aq-1≤1, and since aq-1>0, we necessarily have 0≤aq-aq-1≤1. Now, if aq-aq-1=0, we have aq=aq-1=0 since w∈S(n,r), which is in contradiction with aq-1>0. Hence, it must be aq-aq-1=1; that is, aq=aq-1+1. Moreover, aq′>aq-1′ because aq-1′≥aq-1>0 and w′∈S(n,r). Therefore, since aq′=aq, we have aq-1+1=aq=aq′>aq-1′, which implies aq-1+1>aq-1′≥aq-1 because w⊏w′. By subtracting aq-1 from each term of the previous inequalities, we obtain 1>aq-1′-aq-1≥0; therefore, it must be aq-1′=aq-1.We set(30)(1.1a):∃l∈{r,…,2}suchthatal>0,w=arar-1⋯al+1al0⋯0∣b1⋯bn-r,w′=arar-1⋯al+1alal-1′⋯a1′∣b1′⋯bn-r′.Proposition 16.
Consider (1a)⇒ (1.1a).Proof.
By (28), there exists at least one element i∈Ω1(w). In this place we have ai>0 and moreover ai+1-ai≥2. Since w∈S(n,r), it must be a1=0 or a1=1. If a1=1, then a2=2,…,ar=r, which is in contrast with ai+1-ai≥2. Hence a1=0 and therefore there exists l∈2,…,r such that al>0 and al-1=⋯=a1=0. We take q=r+1; that is, q-1=r. Since aq′=aq=r+1 and aq-1=ar≥al>0, by Lemma 15 it follows that aq-1′=aq-1; that is, ar′=ar. Let now q=r. If r=l, then we have the thesis otherwise q=r>l; that is, q-1≥l; therefore aq-1≥al>0 because w∈S(n,r). Then since aq′=ar′=ar=aq, we can apply Lemma 15 and we deduce aq-1′=aq-1; that is, ar-1′=ar-1. By iteration the thesis follows.Lemma 17.
Assume that (3a) holds. Ifq∈{2,3,…,n-r-1}, bq′=bq<0, then bq+1′=bq+1.Proof.
Ifq+1∈Ω3(w), then the thesis holds by definition of (3a) in (29). We assume now that q+1∉Ω3(w). Now, if bq-bq+1=0, we have bq=bq+1=0 since w∈S(n,r), which is in contradiction with the hypothesis bq<0. Hence it must be bq-bq+1=1; that is, 0>bq=bq+1+1; therefore 0>bq+1+1=bq=bq′>bq+1′≥bq+1 since w′∈S(n,r) and w⊏w′. The last inequalities provide bq+1+1>bq+1′≥bq+1. By subtracting bq+1 from each term of the previous inequalities, we obtain 1>bq+1′-bq+1≥0; therefore it must be bq+1′=bq+1.Proposition 18.
If (3a) holds, thenw has the following form: w=ar⋯a1|0⋯0blbl+1⋯bn-r, with bl<0 and l≥2. Moreover, ifbl≤-2, we also have w-′=w-.Proof.
By (3a) in (29), we know that Ω3(w)≠∅. Moreover, if j∈Ω3(w), then j≥2 and bj<0 because bj-1-bj≥2. Therefore, we can take the minimum l∈2,…,n-r such that bl<0; hence bl-1=⋯=b1=0 and this means that w=ar⋯a1|0⋯0blbl+1⋯bn-r. Assume now that bl≤-2. Since bl-1=0, we have bl-1-bl≤2; therefore l∈Ω3(w). By (3a), follows then that bl′=bl<0. Now, if l=n-r, the thesis is true, otherwise, if l∈{2,…,n-r-1}, by Lemma 17 we have bl+1′=bl+1<0. Again, if l+1=n-r, the thesis is true; otherwise, if l+1∈{2,…,n-r-1}, by Lemma 17 we have bl+2′=bl+2<0. Proceeding repeatedly in this way we obtain bl′=bl, bl+1′=bl+1,…,bn-r′=bn-r. Finally, since b1=⋯=bl-1=0 and w⊏w′, we also have b1′=⋯=bl-1′=0. This proves that w-′=w-.Proposition 19.
Consider ((2C) AND (3a))⇒w-′=w-.Proof.
(2C) implies thatw has the form w=ar⋯a1|0⋯0blbl+1⋯bn-r, with bl≤-2. Since (3a) holds, by Proposition 18, the thesis follows.Proposition 20.
Consider ((1.1a) AND (2C) AND (3a))⇒ absurd.Proof.
By Proposition19, we have that w-′=w-. Moreover, by (1.1a) in (30), we also have w+′=w+ because ∥w′∥=∥w∥=d and w-′=w-; therefore, w=w′. This is absurd because w′⋗w by hypothesis.Proposition 21.
Consider ((1.1b) AND (2C) AND (3a))⇒ absurd.Proof.
By (1.1b) in (12), we know that w=0⋯0|b1⋯bn-r, and this implies ∥w+∥=0 and ∥w-∥=d. Moreover, by Proposition 19, w-′=w-; therefore it follows that ∥w-′∥=d; hence ∥w+′∥=0 since w′∈S(n,d,r). This shows that w=w′ and this is absurd because w⋗w′.Proposition 22.
Consider ((1.1a) AND (2B))⇒w+′=w+.Proof.
By (1.1a) in (30) and (2B), it follows that w=ar⋯al+110⋯0|b1⋯bn-r and w′=ar⋯al+11al-1′⋯a1′|b1⋯bn-r. Now, since w′∈S(n,r) and al=al′=1, we have that 1=al′>al-1′≥⋯≥a1′≥0; that is, al-1′=⋯=a1′=0. Therefore w+′=w+.Proposition 23.
Consider ((1.1a) AND (2B) AND (3.1b))⇒ absurd.Proof.
By Proposition22w+′=w+ and by Proposition 8  w=w-′; hence w=w′ and this is a contradiction.Proposition 24.
Consider ((1.1a) AND (3.1b))⇒ absurd.Proof.
By Proposition8,  w=w-′=|00⋯0; hence ∥w+′∥=∥w+∥=d because w,w′∈S(n,d,r). Moreover, by (1.1a) in (30), it follows that
(31)w+′=w+=ar⋯al+1al0⋯0.
Therefore, w=w′, which is absurd.Proposition 25.
Consider ((1.1a) AND (2B) AND (3a))⇒ absurd.Proof.
By Proposition18, we have w=ar⋯a1|0⋯0blbl+1⋯bn-r with bl<0 and l≥2. By Proposition 22,w+′=w+. Now, if bl≤-2, by Proposition 18 we have w-′=w- and therefore w′=w, which is absurd. So we can assume that bl=-1. Since w+′=w+, ∥w′∥=∥w∥=d and w⊏w′, it follows that bl′ cannot be 0; otherwise, it is ∥w′∥<d. This implies that it must be bl′=-1. We distinguish now two cases.
Case  1. If l∈{2,…,n-r-1}, since bl=bl′=-1, by Lemma 17 (with q=l) we obtain bl+1=bl+1′<0. Now, if l+1=n-r, then w-=w-′, and as before this provides a contradiction. If l+1<n-r, we can still apply Lemma 17 (with q=l+1) and therefore have bl+2=bl+2′<0. Proceeding in this way in all cases we always obtain w-=w-′ and hence is absurd.
Case  2. If l=n-r, then w=ar⋯a1∣0⋯0(-1), and since ∥w′∥=∥w∥=d, w⊏w′, and w+′=w+, it must also be w′=ar⋯a1|0⋯0(-1); that is, w=w′, absurd.Proposition 26.
Consider ((1.1a) AND (2B) AND (3.2b))⇒ absurd.Proof.
By Proposition22,  w+′=w+. Then by (3.2b) in (16), since w+′=w+, ∥w-′∥=∥w-∥, and w⊏w′, it must also be
(32)w-′=∣00⋯0(-1)(-2)⋯(-l).
Hence we obtain w=w′, absurd.Proposition 27.
Consider ((1.2b) AND (2C) AND (3a))⇒ absurd.Proof.
By Proposition19,  w-′=w-. Then, since w⊏w′, ∥w′∥=∥w∥, and w-′=w-, by (1.2b) in (13) we deduce that w+′=w+. Hence the absurd w′=w.Proposition 28.
Consider ((2.1d) AND (3a))⇒ absurd.Proof.
Sincew⊏w′ by (2.1d) in (14), it follows that w+′=w+. Then, since (3a) in (29) holds, the same proof of Proposition 25 leads to the absurd w=w′.We complete now the proof of our main result; that is, we provide three syntactic trees where each possible path from the roots to the leaves leads to a contradiction. In the following we draw each tree and next we also write all the implication chains for each path from the roots to the leafs.We recall at first some useful implications and equivalences already proved in the previous section:(Θ1A)
(1A′) ⇔ [by Proposition 13 (i)] (1A) ⇒ [by Proposition 14] (1a) ⇒ [by Proposition 16] (1.1a)(Θ2A)
(2A′) ⇒ [by Proposition 12] absurd(Θ2D)
(2D)⇔ [by Proposition 6] (2.1d)(Θ3A)
(3A′) ⇔ [by Proposition 13 (ii)] (3A) ⇒ [by Proposition 14] (3a) ⇒ [see statement of Proposition 18] Proposition 18.The first tree that we consider is that having the condition (1A′) as root (we denote such tree with TREE(1A′)).TREE (1A′):
(33)We observe now that by virtue of Proposition5 when we start from the condition (1B), we must consider two subtrees, the first with root (1.1b) (which we denote by TREE(1.1b)) that isTREE (1.1b):(34)and the second (which we denote by TREE(1.2b)) that isTREE (1.2b):(35)Let us note that the ramification(36)in each of the previous trees follows by Proposition7.We have then exactly27 possible paths from the roots to the leafs in all the previous trees (we exclude the paths that lead to (2A′) because we already know that they lead to a contradiction by Θ2A). In the following we write all these 27 paths and, for each, the related proposition that leads to a contradiction together with some implication among the Θ1A, Θ2D, and Θ3A. In the sequel, the node (3B) is omitted for brevity because it is only an intermediate node and in the paths that involve (3B) we use only the leafs (3.1b) and (3.2b) to deduce the related contradictions:(1A′) AND (2B) AND (3A′) ⇒ absurd by Θ1A, Θ3A, and Proposition 25(1A′) AND (2B) AND (3.1b) ⇒ absurd by Θ1A and Proposition 23(1A′) AND (2B) AND (3.2b) ⇒ absurd by Θ1A and Proposition 26(1A′) AND (2C) AND (3A′) ⇒ absurd by Θ1A, Θ3A, and Proposition 20(1A′) AND (2C) AND (3.1b) ⇒ absurd by Θ1A and Proposition 24(1A′) AND (2C) AND (3.2b) ⇒ absurd by Θ1A and Proposition 9 (iii)(1A′) AND (2D) AND (3A′) ⇒ absurd by Θ2D, Θ3A, and Proposition 28(1A′) AND (2D) AND (3.1b) ⇒ absurd by Θ1A and Proposition 24(1A′) AND (2D) AND (3.2b) ⇒ absurd by Θ2D and Proposition 11(1.1b) AND (2B) AND (3A′) ⇒ absurd by Proposition 9 (i)
(1.1b) AND (2B) AND (3.1b)⇒ absurd by Proposition 9 (i)
(1.1b) AND (2B) AND (3.2b)⇒ absurd by Proposition 9 (i)
(1.1b) AND (2C) AND (3A′) ⇒ absurd by Θ3A and by Proposition 21
(1.1b) AND (2C) AND (3.1b)⇒ absurd by Proposition 9 (iv)
(1.1b) AND (2C) AND (3.2b)⇒ absurd by Proposition 9 (iii)
(1.1b) AND (2D) AND (3A′) ⇒ absurd by Θ2D and by Proposition 9 (ii)
(1.1b) AND (2D) AND (3.1b)⇒ absurd by Θ2D and by Proposition 9 (ii)
(1.1b) AND (2D) AND (3.2b)⇒ absurd by Θ2D and by Proposition 9 (ii)(1.2b) AND (2B) AND (3A′) ⇒ (1.2b) AND (2D) AND (3A′) (that we examine below) by Θ2D and by Proposition 10
(1.2b) AND (2B) AND (3.1b)⇒ (1.2b) AND (2D) AND (3.1b) (that we examine below) by Θ2D and by Proposition 10
(1.2b) AND (2B) AND (3.2b)⇒ (1.2b) AND (2D) AND (3.2b) (that we examine below) by Θ2D and by Proposition 10
(1.2b) AND (2C) AND (3A′) ⇒ absurd by Θ3A and by Proposition 27
(1.2b) AND (2C) AND (3.1b)⇒ absurd by Proposition 9 (v)
(1.2b) AND (2C) AND (3.2b)⇒ absurd by Proposition 9 (iii)
(1.2b) AND (2D) AND (3A′) ⇒ absurd by Θ2D, Θ3A, and Proposition 28
(1.2b) AND (2D) AND (3.1b)⇒ absurd by Proposition 9 (v)
(1.2b) AND (2D) AND (3.2b)⇒ absurd by Θ2D and by Proposition 11This concludes the proof of Theorem4. Below we draw the Hasse diagram of the lattice S(5,3,2) by using the evolution Rules 1, 2, and 3 starting with the minimum element of this lattice, which is 00|123. We label a generic edge of the next diagram with the symbol Rk if it leads to a production that uses the Rule k, for k∈{1,2,3}:
(37)



---

*Source: 973501-2013-04-03.xml*