# A Minimum Problem for Finite Sets of Real Numbers with Nonnegative Sum

Authors: G. Chiaselotti; G. Marino; C. Nardi
Journal: Journal of Applied Mathematics
 (2012)

---

## Abstract

Letn and r be two integers such that 0<r≤n; we denote by γ(n,r)[η(n,r)] the minimum [maximum] number of the nonnegative partial sums of a sum ∑1=1nai≥0, where a1,…,an are n real numbers arbitrarily chosen in such a way that r of them are nonnegative and the remaining n-r are negative. We study the following two problems: (P1)which are the values ofγ(n,r)andη(n,r)for eachnandr, 0<r≤n?(P2)ifqis an integer such thatγ(n,r)≤q≤η(n,r), can we findnreal numbersa1,…,an, such thatrof them are nonnegative and the remainingn-rare negative with∑1=1nai≥0, such that the number of the nonnegative sums formed from these numbers is exactlyq?


---

## Body

## 1. Introduction

In [1] Manickam and Miklós raised several interesting extremal combinatorial sum problems, two of which will be described below. Let n and r be two integers such that 0<r≤n; we denote by γ(n,r)[η(n,r)] the minimum [maximum] number of the nonnegative partial sums of a sum ∑1=1nai≥0, when a1,…,an are n real numbers arbitrarily chosen in such a way that r of them are nonnegative and the remaining n-r are negative. Put A(n)=min{γ(n,r):0<r≤n}. In [1] the authors answered the following question.(Q1)Which is the value ofA(n)?In [1, Theorem 1] they found that A(n)=2n-1. On the other side, from the proof of Theorem 1 of [1] also it follows that γ(n,r)≥2n-1 for each r and that γ(n,1)≤2n-1; therefore γ(n,1)=2n-1 (since 2n-1=A(n)≤γ(n,1)≤2n-1). It is natural to set then the following problem which is a refinement of (Q1).(P1)Which are the values ofγ(n,r)andη(n,r)for eachnandrwith0<r≤n?In the first part of this paper we solve the problem(P1), and we prove (see Theorem 4.1) that γ(n,r)=2n-1 and η(n,r)=2n-2n-r for each positive integer r≤n.A further question that the authors raised in [1] is the following.(Q2)  “We do not know what is the range of the possible numbers of the nonnegative partial sums of a nonnegativen-element sum. The minimum is2n-1as it was proven and the maximum is obviously2n-1but we do not know which are the numbers between them for which we can find realsa1,…,anwith∑1=1nai≥0such that the number of the nonnegative sums formed from these numbers is equal to that number.’’The following problem is a natural refinement of (Q2).(P2)  Ifqis an integer such thatγ(n,r)≤q≤η(n,r), can we findnreal numbersa1,…,an, such thatrof them are nonnegative and the remainingn-rare negative with∑1=1nai≥0, such that the number of the nonnegative sums formed from these numbers is exactlyq?In the latter part of this paper (see Theorem4.5) we give a partial solution to the problem (P2).To be more precise in the formulation of the problems that we study and to better underline the links with some interesting problems raised in [1], it will be convenient-identify a finite set of real-numbers with an appropriate real-valued function. Let then n and r be two fixed integers such that 0<r≤n and let In={1,2,…,n} (we call In the index set). We denote by W(n,r), the set of all the functions f:In→ℝ such that ∑x∈Inf(x)≥0 and |{x∈In:f(x)≥0}|=r. If f∈W(n,r), we set α(f)=|{Y⊆In:∑y∈Yf(y)≥0}|. It is easy to observe that γ(n,r)=min{α(f):f∈W(n,r)} and η(n,r)=max{α(f):f∈W(n,r)}. We can reformulate the problem (P2) in an equivalent way using the functions terminology instead of the sets terminology.(P2)  Ifqis an integer such thatγ(n,r)≤q≤η(n,r), does there exist a functionf∈W(n,r)with the property thatα(f)=q?To solve the problem(P1) and (partially) (P2), we use some abstract results on a particular class of lattices introduced in [2, 3]. In this paper we substantially continue the research project started in [4], which is the attempt to solve some extremal sum problems as started in [1] and further studied in [3, 5–11].


## 2. A Partial Order on the Subsets ofIn

Of course if we take two functionsf,g∈W(n,r) such that f(In)=g(In), then α(f)=α(g). This implies that if we define on W(n,r) the equivalence relation f~g iff f(In)=g(In) and we denote by [f] the equivalence class of a function f∈W(n,r), then the definition β([f])=α(f) is well placed. It is also clear that it holds γ(n,r)=min{β([f]):[f]∈W(n,r)/~} and η(n,r)=max{β([f]):[f]∈W(n,r)/~}. Now, when we take an equivalence class [f]∈W(n,r)/~, there is a unique f*∈[f] such that(2.1)f*(r)≥⋯≥f*(1)≥0>f*(r+1)≥⋯≥f*(n).
We can then identify the quotient set W(n,r)/~  with the subset of all the functions f*∈W(n,r) that satisfy the condition (2.1). This simple remark conducts us to rename the indexes of In as follows: r̃ instead of r,…,1̃ instead of 1, 1¯ instead of r+1,…,n-r¯ instead of n. Therefore, if we set I(n,r)={1̃,…,r̃,1¯,…,n-r¯}, we can identify the quotient set W(n,r)/~  with the set of all the functions f:I(n,r)→ℝ that satisfy the following two conditions:(2.2)f(r̃)+⋯+f(1̃)+f(1¯)+⋯+f(n-r¯)≥0,f(r̃)≥⋯≥f(1̃)≥0>f(1¯)≥⋯≥f(n-r¯).
Now, if a generic function f:I(n,r)→ℝ that satisfies (2.2) is given, we are interested to find all the subsets Y⊆I(n,r) such that ∑y∈Yf(y)≥0. This goal becomes then easier if we can have an appropriate partial order⊑ on the power set 𝒫(I(n,r)) “compatible” with the total order of the partial sums inducted by f, that is, a partial order ⊑ that satisfies the following monotonicity property: if Y,Z∈𝒫(I(n,r)), then ∑z∈Zf(x)≤∑y∈Yf(y) whenever Z⊑Y. To have such a partial order ⊑on 𝒫(I(n,r)) that has the monotonicity property we must introduce a new formal symbol that we denote by0§. We add this new symbol to the index set I(n,r), so we set A(n,r)=I(n,r)∪{0§}. We introduce on A(n,r) the following total order:(2.3)n-r¯≺⋯≺2¯≺1¯≺0§≺1̃≺2̃≺⋯≺r̃.If i,j∈A(n,r), then we write: i⪯j for i=j or i≺j. We denote by S(n,r) the set of all the formal expressions i1⋯ir∣j1⋯jn-r (hereafter called strings) that satisfy the following properties:(i)
i1,…,ir∈{1̃,…,r̃,0§},(ii)
j1,…,jn-r∈{1¯,…,n-r¯,0§},(iii)
i1≽⋯≽ir≽0§≽j1≽⋯≽jn-r,(iv)
the unique element which can be repeated is0§.In the sequel we often use the lowercase lettersu,w,z,… to denote a generic string in S(n,r). Moreover to make smoother reading, in the numerical examples the formal symbols which appear in a string will be written without ~  − and §; in such way the vertical bar ∣ will indicate that the symbols on the left of | are in {1̃,…,r̃,0§} and the symbols on the right of ∣ are elements in {0§,1¯,…,n-r¯}. For example, if n=3 and r=2, then A(3,2)={2̃≻1̃≻0§≻1¯} and S(3,2)={21|0,21|1,10|0,20|0,10|1,20|1,00|1,00|0}.Note that there is a natural bijective setcorrespondence*:w∈S(n,r)↦w*∈𝒫(I(n,r))between S(n,r) and 𝒫(I(n,r)) defined as follows: if w=i1⋯ir∣j1⋯jn-r∈S(n,r), then w* is the subset of I(n,r) made with the elements ik and jl such that ik≠0§ and jl≠0§. For example, if w=4310∣013∈S(7,4), then w*={1̃,3̃,4̃,1¯,3¯}. In particular, if w=0⋯0∣0⋯0, then w*=∅.Now, ifv=i1⋯ir∣j1⋯jn-r and w=i1′⋯ir′∣j1′⋯jn-r′ are two strings in S(n,r), we define: v⊑w iff i1⪯i1′,…,ir⪯ir′,j1⪯jr′,…,jn-r⪯jn-r′.It is easily seen that(1)
(S(n,r),⊑) is a finite distributive (hence also graded) lattice with minimum element 0⋯0∣12⋯(n-r) and maximum element r(r-1)⋯21∣0⋯0;(2)
(S(n,r),⊑)has the following unary complementary operation c:
(2.4)(p1⋯pk0⋯0∣0⋯0q1⋯ql)c=p1′⋯pr-k′0⋯0∣0⋯0q1′⋯qn-r-l′,where {p1′,…,pr-k′} is the usual complement of {p1,…,pk} in {1̃,…,r̃} and {q1′,…,qn-r-l′} is the usual complement of {q1,…,ql} in {1¯,…,n-r¯} (e.g., in S(7,4), we have that (4310∣001)c=2000∣023).Since we have the formal necessity to consider functionsf defined on the extended set A(n,r) instead of on the indexes set I(n,r), then we will put f(0§)=0. Precisely we can identify the quotient set W(n,r)/~ with the set WF(n,r), defined by
(2.5)WF(n,r)={(1̃)f:A(n,r)→R:f(r̃)≥⋯≥f(1̃)≥f(0§)=0>f(1¯)≥⋯≥f(n-r¯),f(r̃)+⋯+f(1̃)+f(1¯)+⋯+f(n-r¯)≥0}.We call an element ofWF(n,r) a (n,r)-weight function, and if f∈WF(n,r), we will continue to set α(f):=|{Y⊆I(n,r):∑y∈Yf(y)≥0}|. Therefore, with these last notations we have that γ(n,r)=min{α(f):f∈WF(n,r)}, η(n,r)=max{α(f):f∈WF(n,r)} and the question (P2) becomes equivalent to the following.(P2)  Ifqis an integer such thatγ(n,r)≤q≤η(n,r), does there exist a functionf∈WF(n,r)with the property thatα(f)=q?


## 3. Boolean Maps Induct by Weight Functions

We denote by2 the boolean lattice composed of a chain with 2 elements that we denote N (the minimum element) and P (the maximum element). A Boolean map (briefly BM) onS(n,r) is a map A:dom(A)⊆S(n,r)→2; in particular if dom(A)=S(n,r),we also say that A is a Boolean total map (briefly BTM) on S(n,r). If A is BM on S(n,r), we set SA+(n,r)={w∈dom(A):A(w)=P}.Iff∈WF(n,r), the sum functionΣf:S(n,r)→ℝ induced by f on S(n,r) is the function that associates to w=ir⋯i1∣j1⋯jn-r∈S(n,r) the real number Σf(w)=f(i1)+⋯+f(ir)+f(j1)+⋯+f(jn-r), and therefore we can associate to f∈WF(n,r) the map Af:S(n,r)→2 setting:(3.1)Af(w)={PifΣf(w)≥0,w≠0⋯0∣0⋯0,Nifw=0⋯0∣0⋯0,NifΣf(w)<0.Let us note that|SAf+(n,r)|=|{w∈S(n,r):Af(w)=P}|=α(f), and so γ(n,r)=min{|SAf+(n,r)|:f∈WF(n,r)},η(n,r)=max{|SAf+(n,r)|:f∈WF(n,r)}.Our goal is now to underline that some properties of such maps simplify the study of our problems. It is easy to observe that the mapAf has the following properties.(i)
Af is orderpreserving.(ii)
Ifw∈S(n,r) is such that Af(w)=N, then Af(wc)=P,(iii)
Af(10⋯0∣0⋯0)=P, A(0⋯0∣0⋯0)=N, and Af(r⋯21∣12⋯(n-r))=P.Example 3.1.
Letf be the following (5,3)-weight function:
(3.2)f:3̃2̃1̃1¯2¯↓↓↓↓↓110.9-0.8-2.1
We represent the map Af defined on S(5,3) by using the Hasse diagram of this lattice, on which we color green the nodes where the map Af assumes value P and red the nodes where it assumes value N (See Figure 1).
Note that if we have a generic Boolean total mapA:S(n,r)→2 which has the properties (i), (ii), and (iii) of Af, that is, the following:(BM1)
A is orderpreserving,(BM2)
ifw∈S(n,r) is such that A(w)=N, then A(wc)=P,(BM3)
A(10⋯0∣0⋯0)=P, A(0⋯0∣0⋯0)=N, andA(r⋯21∣12⋯(n-r))=P,in general there does not exist a function f∈WF(n,r) such that Af=A (see [3] for a counterexample).
We denote by𝒲+(S(n,r),2) the set of all the maps A:S(n,r)→2 which satisfy (BM1) and (BM2) and by 𝒲+(n,r) the subset of all the maps in 𝒲+(S(n,r),2) which satisfy also (BM3). We also set γ*(n,r):=min{|SA+(n,r):A∈𝒲+(n,r)} and η*(n,r):=max{|SA+(n,r)|:A∈𝒲+(n,r)}. Let us observe that γ*(n,r)≤γ(n,r)≤η(n,r)≤η*(n,r). A natural question raises at this point.
(Q):ifqis an integer such thatγ*(n,r)≤q≤η*(n,r), does there exist a mapA∈𝒲+(n,r)with the property that|SA+(n,r)|=q?
The question(Q) is the analogue of (P2) expressed in terms of Boolean total maps on S(n,r) instead of (n,r)-weight functions, and if we are able to respond to (Q), we provide also a partial answer to (P2). In Section 4 we give an affirmative answer to the question (Q), and also we give a constructive method to build the map A.Figure 1


## 4. Main Results

In the sequel of this paper we adopt the classical terminology and notations usually used in the context of the partially ordered sets (see [12–14] for the general aspects on this subject). If Z⊆S(n,r), we will set ↓Z={x∈S(n,r):∃z∈Zsuchthatx⊑z},↑Z={x∈S(n,r):∃z∈Zsuchthatz⊑x}. In particular, if z∈S(n,r), we will set ↓z=↓{z}={x∈S(n,r):z⊒x}, ↑z=↑{z}={x∈S(n,r):z⊑x}. Z is called a downset of S(n,r) if for z∈Z and x∈S(n,r) with z⊒x, then x∈Z. Z is called an upset of S(n,r) if for z∈Z and x∈S(n,r) with z⊑x, then x∈Z. ↓Z is the smallest down-set of S(n,r) which contains Z, and Z is a downset of S(n,r) if and only if Z=↓Z. Similarly, ↑Z is the smallest up-set of S(n,r) which contains Z, and Z is an upset in S(n,r) if and only if Z=↑Z.Theorem 4.1.
Ifn and r are two integers such that 0<r<n, then γ(n,r)=γ*(n,r)=2n-1 and η(n,r)=η*(n,r)=2n-2n-r.Proof.
Assume that0<r<n. We denote by S1(n,r) the sublattice of S(n,r) of all the strings w of the form w=i1⋯ir∣j1⋯jn-r-1(n-r), with j1⋯jn-r-1∈{0§,1¯,…,n-r-1¯} and by S2(n,r) the sublattice of S(n,r) of all the strings w of the form w=i1⋯ir∣0j2⋯jn-r, with j2⋯jn-r∈{0§,1¯,…,n-r-1¯}. It is clear that S(n,r)=S1(n,r)⋃̇S2(n,r)and S1(n,r)≅S2(n,r)≅S(n-1,r). We consider now the following further sublattices of S(n,r):
(4.1)S1+(n,r):={w∈S1(n,r):w=r(r-1)⋯21∣j1⋯jn-r-1(n-r)},S1±(n,r):={w∈S1(n,r):w=i1⋯ir-10∣j1⋯jn-r-1(n-r),i1≻0§},S1-(n,r):={w∈S1(n,r):w=0⋯0∣j1⋯jn-r-1(n-r)},S2+(n,r):={w∈S2(n,r):w=r(r-1)⋯21∣0j2⋯jn-r},S2±(n,r):={w∈S2(n,r):w=i1⋯ir-10∣0j2⋯jn-r,i1≻0§},S2-(n,r):={w∈S2(n,r):w=0⋯0∣0j2⋯jn-r}.It occurs immediately that Si(n,r)=Si+(n,r)⋃̇Si±(n,r)⋃̇Si-(n,r), for i=1,2 and Si±(n,r) is a distributive sublattice of Si(n,r) with 2n-1-2·2n-r-1=2n-1-2n-r elements, for i=1,2.
Now we consider the following(n,r)-weight function f:A(n,r)→ℝ:(4.2)f:r~⋯1~0§1¯⋯(n-r-1)¯(n-r)¯↓↓↓↓↓↓↓↓(n-r)⋯(n-r)0-1⋯-1(n-r)(1-r)-1
Then it follows that Σf:S(n,r)→ℝ is such that
(4.3)Σf(w){≥0ifw∈S2±(n,r),<0ifw∈S1±(n,r).
It means that the boolean map Af∈𝒲+(n,r) is such that
(4.4)Af(w){Pifw∈S2±(n,r),Nifw∈S1±(n,r).
This shows that |SAf+(n,r)|=|S1+(n,r)⋃̇S2+(n,r)⋃̇S2±(n,r)|=2n-r-1+2n-r-1+2n-1-2·2n-r-1=2n-1.
In [1, Theorem 1] it has been proved that γ(n,1)=2n-1 and γ(n,r)≥2n-1. Since γ(n,r)≥γ*(n,r), using a technique similar to that used in the proof Theorem 1 of [1], it easily follows that γ*(n,r)≥2n-1. As shown above, it results that |SAf+(n,r)|=2n-1. Hence 2n-1≥γ(n,r)≥γ*(n,r)≥2n-1, that is, γ(n,r)=γ*(n,r)=2n-1. This proves; the first part of theorem; it remains to prove the latter part.
We consider now the following(n,r)-positive weight function g:A(n,r)→ℝ:
(4.5)r~⋯1~0§1¯⋯(n-r-1)¯(n-r)¯g:↓↓↓↓↓↓↓↓1⋯10-1n-r⋯-1n-r-1n-r
It results then that the sum Σg:S(n,r)→ℝ is such that Σg(w)≥0 if w∈S1±(n,r)⋃̇S2±(n,r); that is, the boolean map Ag∈𝒲+(n,r) is such that Ag(w)=Pif w∈S1±(n,r)⋃̇S2±(n,r). This shows that |SAg+(n,r)|=|S1±(n,r)⋃̇S2±(n,r)⋃̇S1+(n,r)⋃̇S2+(n,r)|=(2n-1-2n-r)+(2n-1-2n-r)+2n-r-1+2n-r-1 = 2n-2n-r.
On the other hand, it is clear that for anyA∈𝒲+(n,r) it results A(w)=P for each w∈S1+(n,r)⋃̇S2+(n,r)and A(w)=N for each w∈S1-(n,r)⋃̇S2-(n,r).The number (2n-2n-r) is the biggest number of values P that a boolean map A∈𝒲+(n,r) can assume. Hence, since η(n,r)≤η*(n,r), we have 2n-2n-r=|SAg+(n,r)|≤η(n,r)≤η*(n,r)≤2n-2n-r; that is be; η(n,r)=η*(n,r)=2n-2n-r. This concludes the proof of Theorem 4.1.To better visualize the previous result, we give a numerical example on a specific Hasse diagram. Letn=6 and r=2 and let f be as given in previous theorem; that is
(4.6)f:2~1~0§1¯2¯3¯4¯↓↓↓↓↓↓↓440-1-1-1-5
In Figure 2 we have shown the Hasse diagram of the lattice S(6,2), where S1+(n,r) is black, S1±(n,r) is violet, S1-(n,r) is red, S2+(n,r) is blue, S2±(n,r) is brown, S2-(n,r) is green. Therefore Af assume the following values.(i)
The blue, black, and brown nodes correspond to valuesP of Af,(ii)
The violet, red, and green nodes correspond to valuesN of Af.Figure 2First to give the proof of Theorem4.5 we need to introduce some useful results and the concept of basis in S(n,r). In the following first lemma we show some properties of the sublattices of S(n,r).Lemma 4.2.
Here the following properties hold, whereθ=00⋯0∣0⋯0 and  Θ=r⋯21∣12⋯(n-r). (i)
↑Θ=S1+(n,r)⋃̇S2+(n,r).(ii)
↓θ=S1-(n,r)⋃̇S2-(n,r).(iii)
↑S2±(n,r)⊆S2±(n,r)⋃̇S2+(n,r).(iv)
↓S1±(n,r)⊆S1±(n,r)⋃̇S1-(n,r).(v)
((S1±(n,r))c=S2±(n,r).Proof.
(i) Ifw∈(↑Θ), then Θ⊑w; that is, it has the form w=r⋯1∣j1⋯jn-r, where j1⋯jn-r∈{0§,1¯,…,n-r¯}; therefore w∈S1+(n,r)⋃̇S2+(n,r). If w∈S1+(n,r), it has the form w=r⋯1∣j1⋯jn-r-1(n-r), where j1⋯jn-r-1∈{0§,1¯,…,n-r-1¯}; if w∈S2+(n,r), it has the form w=r⋯1∣0j2⋯jn-r, where j2⋯jn-r∈{0§,1¯,…,n-r-1¯}. In both cases it results that Θ⊑w, that is, w∈(↑Θ).(ii)
It is analogue to (i).(iii)
The minimum of the sublatticeS2±(n,r)is α=10⋯0∣01⋯(n-r-1); since ↑S2±(n,r)⊆↑α, it is sufficient to show that ↑α=S2±(n,r)⋃S2+(n,r). The inclusion S2±(n,r)⋃S2+(n,r)⊆↑αfollows by the definition of S2±(n,r)and of S2+(n,r). On the other side, if w∈↑α, it follows that α⊑w; that is, w=i1⋯ir∣0j2⋯jn-r, with i1≻0§and j2⋯jn-r∈{0§,1¯,…,n-r-1¯}. Therefore w∈S2±(n,r)⋃S2+(n,r), and this proves the other inclusion.(iv)
Let us consider the maximum of the sublatticeS1±(n,r); that is t1=r(r-1)⋯20∣0⋯0(n-r). Since ↓S1±(n,r)⊆↓β, it is sufficient to show that ↓t1=S1±(n,r)⋃S1-(n,r); this proof is similar to (iii).(v)
Ifw∈S1±(n,r); it has the form w=i1⋯ir-10∣j1⋯jn-r-1(n-r), with i1≻0§ and j1⋯jn-r-1∈{0§,1¯,…,n-r-1¯}; therefore its complement has the form wc=i1′⋯ir-1′0∣0j2′⋯jn-r′, with i1′≻0§ and j2′⋯jn-r′∈{0§,1¯,…,n-r-1¯}; hence wc∈S2±(n,r). This shows that (S1±(n,r))c⊆S2±(n,r).
Now, ifw∈S2±(n,r), we write w in the form (wc)c; then wc∈(S2±(n,r))c⊆S1±(n,r); therefore w∈(S1±(n,r))c. This shows that S2±(n,r)⊆(S1±(n,r))c.At this point let us recall the definition of basis forS(n,r), as given in [3] in a more general context. In the same way as an antichain uniquely determines a Boolean order-preserving map, a basis uniquely determines a Boolean map that has the properties (BM1) and (BM2) (see [3] for details). Hence the concept of basis will be fundamental in the sequel of this proof.Definition 4.3.
A basis forS(n,r) is an ordered couple 〈Y+∣Y-〉, where Y+ and Y- are two disjoint antichains of S(n,r) such that(B1)
(↓Y+)⋂(Y-c)=∅,(B2)
((↑Y+)⋃↑(Y-c))⋂↓Y-=∅,(B3)
S(n,r)=((↑Y+)⋃↑(Y-c))⋃↓Y-.In the proof of Theorem 4.5 we will construct explicitly such a basis.
We will also use the following result that was proved in [3].Lemma 4.4.
Let〈W+∣W-〉 be a basis for  S(n,r). Then the map
(4.7)A(x){Pifx∈↑(W+)⋃↑(W-c),Nifx∈↓W-
is such that A∈𝒲+(S(n,r),2).Theorem 4.5.
Ifq is a fixed integer with  2n-1≤q≤2n-2n-r, then there exists a boolean map  Aq∈𝒲+(n,r) such that  |SAq+(n,r)|=q.Proof.
Letq be a fixed integer such that 2n-1≤q≤2n-2n-r. We determine a specific Boolean total map A∈𝒲+(n,r) such that |SA+(n,r)|=q. We proceed as follows.
The caser=1 is proved in the previous Theorem 4.1. Let us assume then r>1. Since S1±(n,r) is a finite distributive sublattice of graded lattice S(n,r), also S1±(n,r) is a graded lattice. We denote by R the rank of S1±(n,r) and with ρ1 its rank function. Note that the bottom of S1±(n,r) is b1=10⋯0∣1⋯(n-r-1)(n-r) and the top is t1=r(r-1)⋯20∣0⋯0(n-r).
We writeq in the form q=2n-1+p with 0≤p≤2n-2n-r-2n-1=2n-1-2n-r=|S1±(n,r)|. We will build a map A∈W+(n,r) such that |SA+(n,r)|=2n-1+p.
Ifp=0, we take A=Af, with f as in Theorem 4.1, and hence we have |SA+(n,r)|=2n-1.
Ifp=2n-1-2n-r, we take A=Ag, with g as in Theorem 4.1, and we have |SA+(n,r)|=2n-2n-r.
Therefore we can assume that0<p<2n-1-2n-r.
If0≤i≤R, we denote by ℜi the set of elements w∈S1±(n,r) such that ρ1(w)=R-i, and we also set βi:=|ℜi| to simplify the notation. We write each ℜi in the following form: ℜi={vi1,…,viβi}. If 0≤l≤R, we set 𝔘l:=⋃̇i=0,…,lℜi.
If0≤l≤R-2, we set 𝔅l:=⋃̇i=l+2,…,Rℜi and 𝔅R-1:=𝔅R:=∅. We can then write p in the form p=∑i=0k|ℜi|+s=|𝔘k|+s, for some 0≤s<|ℜk+1| and some 0≤k≤R-1. Depending on the previous number s we partition ℜk+1 into the following two disjoint subsets: ℜk+1={v(k+1)1,…,v(k+1)s}⋃̇{v(k+1)(s+1),…,v(k+1)βk+1}, where the first subset is considered empty if s=0.
In the sequel, to avoid an overload of notations, we write simplyvi instead of v(k+1)i, for i=1,…,βk+1.
Let us note thatS1±(n,r)=𝔘k⋃̇ℜk+1⋃̇𝔅k.
We define now the mapA:S(n,r)→2:
(4.8)A(w)={Pifw∈S2±(n,r)⋃̇S1+(n,r)⋃̇S2+(n,r),Pifw∈Uk⋃̇{v1,…,vs},Nifw∈Bk⋃̇{vs+1,…,vβk+1},Nifw∈S1-(n,r)⋃̇S2-(n,r).
Let us observe that |SA+(n,r)| = |S2±(n,r)⋃̇S1+(n,r)⋃̇S2+(n,r)|+|𝔘k⋃̇{v1,…,vs}| = (2n-1-2n-r)+2n-r-1+2n-r-1+|𝔘k|+s = 2n-1+p = q.
Therefore, if we show thatA∈𝒲+(n,r), the theorem is proved.
We writeℜk in the following way: ℜk={w1,…,wt}⋃̇{wt+1,…,wβk},where {w1,…,wt} = ℜk⋂↑{v1,…,vs} and {wt+1,…,wβk} = ℜk∖{w1,…,wt}. Analogously ℜk+2 = {z1,…,zq}⋃̇{zq+1,…,zβk+2}, where {zq+1,…,zβk+2} = ℜk+2⋂↓{vs+1,…,vβk+1} and {z1,…,zq} = ℜk+2∖{zq+1,…,zβk+2}.
We can see a picture of this partition of the sublatticeS1±(n,r) in Figure 3.
Depending ons and k, we build now a particular basis for S(n,r).
To such aim, let us consider the minimumα=10⋯0∣01⋯(n-r-1) of S2±(n,r) and the subsets T+:={v1,…,vs,wt+1,…,wβk} and T-:={vs+1,…,vβk+1,z1,…,zq}. Let us distinguish two cases:(a1)
α∈↑T+,(a2)
α∉↑T+. We define two different couples of subsets as follows:
In the case(a1) we set Y+:=T+andY-:=T-⋃̇{θ};in the case (a2) we set Y+:=T+⋃{α} and Y-:=T-⋃̇{θ}.
Step 1.
〈Y+∣Y-〉 is a couple of two disjoint antichains of S(n,r).
In both cases (a1) and (a2) it is obvious thatY+⋂Y-=∅.
Case  (a1)
The elements{v1,…,vs} are not comparable between them because they have all rank R-(k+1) and analogously for the elements {wt+1,…,wβk} that have all rank R-k. Let now v∈{v1,…,vs} and let w∈{wt+1,…,wβk}; then w∉↓v because ρ1(v)<ρ1(w), and w∉↑v because {wt+1,…,wβk}⋂↑{v1,…,vs}=∅ by construction. For the elements in Y- different from θ, we can proceed as for Y+. On the other side, we can observe that θ is not comparable with none of the elements vs+1,…,vβk+1,z1,…,zq since these are all in S1±(n,r) while θ∈S2-(n,r). Thus Y+ is an antichain.Case (a2)
In this case we only must show thatα is not comparable with none of the elements v1,…,vs,wt+1,…,wβk. At first from the fact that α∉↑T+ it follows vi∉↓α for each i=1,…,s, and wj∉↓α for each j=t+1,…,βk. Moreover, the elements v1,…,vs and wt+1,…,wβk are all in S1±(n,r); hence they have the form i1⋯ir-10∣j1⋯jn-r-1(n-r), with i1≻0§, while α=10⋯0∣01⋯(n-r-1), so α∉↓vi and α∉↓wj for each i=1,…,s and each j=t+1,…,βk.Step 2.
〈Y+∣Y-〉 is a basis for S(n,r).
We must see that (B1), (B2), and (B3) hold in both cases (a1) and (a2).
Case (a1)
(B1)
Let us begin to observe thatT-c={vs+1c,…,vβk+1c,z1c,…,zqc}⊆(S1±(n,r))c=S2±(n,r). Since θc=Θ, we have then Y-c=T-c⋃̇{θc}⊆S2±(n,r)⋃̇{Θ}⊆S2±(n,r)⋃̇S1+(n,r).On the other hand, since ↓Y+⊆↓S1±(n,r), by Lemma 4.2(iv) we have also that ↓Y+⊆S1±(n,r)⋃.S1-(n,r). Hence (↓Y+)⋂(Y-c)=∅. This proves (B1).(B2)
We show at first that↑Y-c⋂↓Y-=∅. Since Y-c⊆S2±(n,r)⋃̇{Θ}, we have that ↑Y-c⊆↑(S2±(n,r))⋃↑Θ. By Lemma 4.2(i) and (iii) we have then ↑Y-c⊆S2±(n,r)⋃̇S1+(n,r)⋃̇S2+(n,r). On the other side, since ↓T-⊆↓S1±(n,r), by Lemma 4.2(iv) it follows that ↓T-⊆S1±(n,r)⋃.S1-(n,r). By Lemma 4.2(ii), we have ↓θ=S1-(n,r)⋃̇S2-(n,r). Hence it holds ↓Y-⊆S1±(n,r)⋃̇S1-(n,r)⋃̇S2-(n,r). This proves that ↑Y-c⋂↓Y-=∅. We show now that also ↑Y+⋂↓Y-=∅; we proceed by contradiction. Let us suppose that there exists an element z∈↑Y+⋂↓Y-, then there are two elements w+∈Y+ and w-∈Y- such that w+⊑z⊑w-, hence w+⊑w-. We will distinguish the following five cases, and in each of them we will find a contradiction.
(a)
w+∈{v1,…,vs} and w-∈{vs+1,…,vβk+1}. In this case w+ and w- are two distinct elements having both rank R-(k+1) and such that w+⊑w-; it is not possible.(b)
w+∈{v1,…,vs} and w-∈{z1,…,zq}. In this case w+ has rank R-(k+1) while w- has rank R-(k+2)<R-(k+1), and this contradicts the condition w+⊑w-.(c)
w+∈{wt+1,…,wβk} and w-∈{vs+1,…,vβk+1}.This case is similar to the previous because w+ has rank R-k while w- has rankR-(k+1).(d)
w+∈{wt+1,…,wβk} and w-∈{z1,…,zq}.This is similar to the previous because w+ has rank R-k while w- has rank R-(k+2).(e)
w+∈{v1,…,vs,wt+1,…,wβk} and w-=θ. In this case the condition w+⊑w- implies that w+∈↓θ; since ↓θ=S1-(n,r)⋃̇S2-(n,r) this is not possible since w+∈S1±(n,r).(B3)
Sinceα is the minimum of S2±(n,r) we have that S2±(n,r)⊆↑α, moreover, α∈↑Y+; therefore S2±(n,r)⊆↑α⊆↑Y+. Since Θ=θc∈Y-c, it follows that ↑Θ⊆↑Y-c. By Lemma 4.2(i) we have then that (S1+(n,r)⋃̇S2+(n,r))=↑Θ⊆↑Y-c. By Lemma 4.2(ii) we also have that (S1-(n,r)⋃̇S2-(n,r))=↓θ⊆↓Y-.
To complete the proof of (B3) let us observe thatS1±(n,r)=(⋃i=0kℜi)⋃̇ℜk+1⋃̇(⋃j=k+2Rℜj), where (⋃i=0kℜi)⊆↑ℜk⊆↑Y+, (⋃j=k+2Rℜj)⊆↓ℜk+2⊆↓Y-.
Moreover, sinceℜk+1={v1,…,vs}⋃̇{vs+1,…,vβk+1},with {v1,…,vs}⊆Y+⊆↑Y+ and {vs+1,…,vβk+1}⊆Y-⊆↓Y-, then ℜk+1⊆(↑Y+⋃↓Y-). This shows that S1±(n,r)⊆(↑Y+⋃↓Y-). Since the six sublattices Si+(n,r), Si±(n,r) and Si-(n,r) for i=1,2 are a partition of S(n,r), the property (B3) is proved.Case (a2)
(B1)
We begin to show thatα∉Y-c. In fact, it holds that α=(r(r-1)⋯20∣0⋯0(n-r))c; suppose that α∈Y-c, and this shows that we obtain a contradiction. By α∈Y-c it follows αc=t1∈Y-. But t1 is the top of S1±(n,r), so Y-=t1, since Y- is antichain. This means that ℜk+1=ℜ0 and this is not possible, of course. Since Y+=T+⋃̇{α}, we have (↓Y+)⋂Y-c=((↓T+)⋂Y-c)⋃((↓α)⋂Y-c), and, moreover, as in the proof of (B1) in the case (a1), we also have that (↓T+)⋂Y-c=∅; therefore, to prove (B1) it is sufficient to show that (↓α)⋂Y-c=∅; As in the proof of (B1) in the case (a1), we have Y-c⊆S2±(n,r)⋃̇{Θ}. Since α is the minimum of S2±(n,r) and Θ∉↓α, it follows that the unique element of ↓α that can belong to Y-c is α, but we have shown before that this is not true.(B2)
As in the previous case we have(↑Y-c)⋂↓Y-=∅; moreover (↑Y+)⋂(↓Y-)=((↑T+)⋂(↑α))⋂(↓Y-)((↑T+)⋂(↓Y-))⋃((↑α)⋂(↓Y-)). As in the case (a1) we have ((↑T+)⋂(↓Y-))=∅; therefore, to prove (B2) also in the case (a2), it is sufficient to show that ((↑α)⋂(↓Y-))=∅. As in the proof of (B2) in the case (a1) it results that ↓Y-⊆S2±(n,r)⋃̇S1-(n,r)⋃̇S2-(n,r), and, by definition of α, it is easy to observe that (↑α)⋂(S1±(n,r)⋃̇S1-(n,r)⋃̇S2-(n,r))=∅. Hence ((↑α)⋂(↓Y-))=∅.(B3)
It is identical to that of case (a1).Step 3.
The mapA defined in (4.8) is such that A∈𝒲+(n,r).
Since we have proved that〈Y+∣Y-〉 is a basis for S(n,r), by Lemma 4.4 it follows that the map A∈𝒲+(S(n,r),2) if the two following identities hold:
(4.9)(↑Y+)⋃(↑Y-c)=S2±(n,r)⋃̇S1+(n,r)⋃̇S2+(n,r)⋃̇Uk⋃̇{v1,…,vs},(4.10)↓Y-=Bk⋃̇{vs+1,…,vβk+1}⋃̇S1-(n,r)⋃̇S2-(n,r).We prove at first (4.10). By definition of 𝔅k and T- it easy to observe that 𝔅k⋃̇{vs+1,…,vβk+1}⊆↓T-, and, moreover, by Lemma 4.2(ii) we also have that ↓θ=S1-(n,r)⋃S2-(n,r); hence, since ↓Y-=↓θ⋃↓T-, it results that  𝔅k⋃̇{vs+1,…,vβk+1}⋃S1-(n,r)⋃̇S2-(n,r)⊆↓Y-. On the other hand, by Lemma 4.2(iv) we have that ↓T-⊆S1±(n,r)⋃̇S1-(n,r) because T- is a subset of S1±(n,r). At this point let us note that the elements of ↓T- that are also in S1±(n,r) must belong necessarily to the subset 𝔅k⋃̇{vs+1,…,vβk+1}. This proves the other inclusion and hence (4.10).
To prove now (4.9) we must distinguish the cases (a1) and (a2). We set Δ:=S2±(n,r)⋃̇S1+(n,r)⋃̇S2+(n,r)⋃𝔘k⋃̇{v1,…,vs}. Let us first examine the case (a1). Since α is the minimum of S2±(n,r), we have S2±(n,r)⊆↑α⊆↑Y+. Moreover, since Y-=T-⋃{θ}, it follows that ↑Y-c⊇↑θc=↑(Θ)=S1+(n,r)⋃̇S2+(n,r) by lemma 3.2(i). Finally, since 𝔘k⋃̇{v1,…,vs}⊆↑T+=↑Y+, the inclusion ⊇ in (4.9) is proved. To prove the other inclusion ⊆ we begin to observe that ↑Y+⋂(S1-(n,r)⋃S1-(n,r))=∅; therefore the elements of ↑Y+ that are not in S2±(n,r)⋃̇S1+(n,r)⋃̇S2+(n,r) must be necessarily in S1±(n,r), and such elements, by definition of T+, must be necessarily in 𝔘k⋃̇{v1,…,vs}.This proves that ↑Y+⊆Δ, For ↑(Y-c), we have ↑(Y-c)=↑(T-c⋃{θ}c)=(↑T-c)⋃(↑Θ), where ↑(Θ)=S1+(n,r)⋃̇S2+(n,r) by Lemma 4.2(i), and, since T-⊆S1±(n,r), also T-c⊆(S1±(n,r))c=S2±(n,r), by Lemma 4.2(v). Therefore ↑T-c⊆↑S2±(n,r)⊆S2±(n,r)⋃S2+(n,r) by Lemma 4.2(iii). This shows that ↑(Y-c)⊆S2±(n,r)⋃S2+(n,r)⋃S1+(n,r)⊆Δ, hence, the inclusion ⊆. The proof of (4.9) in the case (a1) is therefore complete.
Finally, to prove (4.9) in the case (a2), it easy to observe that the only difference with respect to case (a1) is when we must show that ↑Y+⊆Δ. In fact, in the case (a2) it results that α∉↑T+ and Y+=T+⋃{α}, while Y- is the same in both cases (a1) and (a2). Therefore, in the case (a2), the elements of ↑Y+ that are not in S2±(n,r)⋃̇S1+(n,r)⋃̇S2+(n,r) must be in (↑T+)⋂S1±(n,r) or in (↑α)⋂S1±(n,r). As in the case (a1) we have (↑T+)⋂S1±(n,r)=𝔘k⋃̇{v1,…,vs}, and, since α is the minimum of S2±(n,r), it results that ↑α=↑S2±(n,r)⊆S2±(n,r)⋃S2+(n,r) by Lemma 4.2(iii); hence (↑α)⋂S1±(n,r)=∅. Therefore, also in the case (a2), the elements of ↑Y+ that are not in S2±(n,r)⋃̇S1+(n,r)⋃̇S2+(n,r) must be necessarily in 𝔘k⋃̇{v1,…,vs}. The other parts of the proof are same as in case (a1). Hence we have proved the identities (4.9) and (4.10). By Lemma 4.4 it follows then that the map A∈𝒲+(S(n,r),2). Finally, by definition of A, we have obviously A(θ)=N, A(ξ1)=P, and A(Θ)=P. This shows that A∈𝒲+(n,r). The proof is complete.Figure 3To conclude we emphasize the elegant symmetry of the induced partitions onS(n,r) from the boolean total maps Aq’s constructed in the proof of the Theorem 4.5.



---

*Source: 847958-2012-05-21.xml*