INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A20

A NOTE ON BOOLEAN LATTICES AND FAREY SEQUENCES

Andrey O. Matveev

Data-Center Co., RU-620034, Ekaterinburg, P.O. Box 5, Russian Federation

                   aomatveev@dc.ru, aomatveev@hotmail.com

Received: 2/7/07, Accepted: 4/10/07, Published: 4/18/07

Abstract

We establish monotone bijections between the Farey sequences of order m and the halfsequences of Farey subsequences associated with the rank m elements of the Boolean lattice of subsets of a 2m-set. We also present a few related combinatorial identities.

Subject class: 05A19, 11B65. Keywords: Boolean lattice, Farey sequence.

1. Introduction

The Farey sequence of order n, denoted by F_{n}, is the ascending sequence of irreducible fractions \frac{h}{k} ∈ ℚ with 0 ≤ h ≤ k ≤ n, see, e.g., [2, Chapter 27], [3, §3], [4, Chapter 4], [5, Chapter III], [8, Chapter 6], [9, Chapter 5]; their numerators and denominators are presented in sequences A006842 and A006843 in Sloane’s On-Line Encyclopedia of Integer Sequences. For example, F_{6} = (\frac{0}{1} < \frac{1}{6} < \frac{1}{5} < \frac{1}{4} < \frac{1}{3} < \frac{2}{5} < \frac{1}{2} < \frac{3}{5} < \frac{2}{3} < \frac{3}{4} < \frac{4}{5} < \frac{5}{6} < \frac{1}{1}) .

For any integer m, 0 < m < n, the ascending sets

(\frac{h}{k} ∈ F_{n} : h ≤ m)  (1)

are interesting Farey subsequences [1].

Let C be a finite set of cardinality n := |C| greater than or equal to two, and A its proper subset; m := |A|. Denote the Boolean lattice of subsets of C by 𝔹(n); the empty set is denoted by ˆ0, and the family of l-element subsets of C is denoted by 𝔹(n)^{(l)}. Let gcd(·, ·) denote the greatest common divisor of two integers. The ascending sequence of fractions

\begin{aligned}F(𝔹(n), m) : & = (\frac{|B∩A|}{gcd(|B∩A|,|B|)}/\frac{|B|}{gcd(|B∩A|,|B|)} : B ⊆ C, |B| > 0) \\ & = (\frac{h}{k} ∈ F_{n} : h ≤ m, k − h ≤ n − m) , \end{aligned}

considered in [7], has the properties very similar to those of the standard Farey sequence F_{n} and of Farey subsequence (1).

The Farey subsequences F(𝔹(2m), m) := (\frac{h}{k} ∈ F_{2m} : h ≤ m, k − h ≤ m) arise in analysis of decision-making problems [6]. One such subsequence is

F(𝔹(12), 6) = (\frac{0}{1} < \frac{1}{7} < \frac{1}{6} < \frac{1}{5} < \frac{1}{4} < \frac{2}{7} < \frac{1}{3} < \frac{3}{8} < \frac{2}{5} < \frac{3}{7} < \frac{4}{9} < \frac{5}{11} < \frac{1}{2} < \frac{6}{11} < \frac{5}{9} < \frac{4}{7} < \frac{3}{5} < \frac{5}{8} < \frac{2}{3} < \frac{5}{7} < \frac{3}{4} < \frac{4}{5} < \frac{5}{6} < \frac{6}{7} < \frac{1}{1}) .

The fractions in the above-mentioned Farey (sub)sequence are indexed starting with zero.

In Theorem 5 of this note we establish the connection between the standard Farey sequence F_{m} and the halfsequences of F(𝔹(2m), m).

2. The Farey Subsequence F(𝔹(n), m)

Recall that the map F_{n} → F_{n}, which sends a fraction \frac{h}{k} to \frac{k−h}{k}, is order-reversing and bijective. The sequences F(𝔹(n), m) and F(𝔹(n), n − m) have an analogous property:

Lemma 1 [7] The map

F(𝔹(n), m) → F(𝔹(n), n − m) , \frac{h}{k} ↦ \frac{k−h}{k} ,  (2)

is order-reversing and bijective.

If we write the fractions \frac{h}{k} ∈ ℚ as the column vectors [\begin{matrix}h \\ k \end{matrix}] ∈ ℤ^{2}, then map (2) can be thought of as the map

[\begin{matrix}h \\ k \end{matrix}] ↦ [ \begin{matrix}−1 & 1 \\ 0 & 1 \end{matrix} ] · [\begin{matrix}h \\ k \end{matrix}] .

Let a′ ∈ 𝔹(n) and 0 < m := ρ(a′) < n, where ρ(a′) denotes the poset rank of a′ in 𝔹(n). For a subset A ⊂ 𝔹(n), let ℑ(A) and 𝔉(A) denote the order ideal and filter in 𝔹(n), generated by A, respectively. The subposet 𝔉(ℑ(a′) ∩ 𝔹(n)^{(1)}), of cardinality 2^{n} − 2^{n−m}, can be partitioned in the following way:

𝔉(ℑ(a′) ∩ 𝔹(n)^{(1)}) = (ℑ(a′) − {ˆ0}) ˙∪

˙⋃_{\begin{matrix}\frac{h}{k} ∈F(𝔹(n),m): \\ \frac{0}{1} < \frac{h}{k} < \frac{1}{1} \end{matrix}} ˙ ⋃_{1≤s≤⌊min\{\frac{m}{h} , \frac{n−m}{k−h}\}⌋}(𝔹(n)^{(s·k)} ∩ (𝔉(ℑ(a′) ∩ 𝔹(n)^{(s·h)}) − 𝔉(ℑ(a′) ∩ 𝔹(n)^{(s·h+1)}))) ,

where |𝔹(n)^{(s·k)} ∩ (𝔉(ℑ(a′) ∩ 𝔹(n)^{(s·h)}) − 𝔉(ℑ(a′) ∩ 𝔹(n)^{(s·h+1)}))| = \binom{m}{s·h}\binom{n−m}{s·(k−h)} .

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A20 3

Since |ℑ(a′) − {ˆ0}| = 2^{m} − 1, we obtain

2^{n} − 2^{n−m} = 2^{m} − 1 + ∑_{\begin{matrix}\frac{h}{k} ∈F(𝔹(n),m): \\ \frac{0}{1} < \frac{h}{k} < \frac{1}{1} \end{matrix}} ∑_{1≤s≤⌊min\{\frac{m}{h} , \frac{n−m}{k−h}\}⌋} \binom{m}{s·h}\binom{n−m}{s·(k−h)} .

If a′′ ∈ 𝔹(n) and ρ(a′′) = n − m, then Lemma 1 implies

2^{n} − 2^{m} = 2^{n−m} − 1 + ∑_{\begin{matrix}\frac{h}{k} ∈F(𝔹(n),n−m): \\ \frac{0}{1} < \frac{h}{k} < \frac{1}{1} \end{matrix}} ∑_{1≤s≤⌊min\{\frac{n−m}{h} , \frac{m}{k−h}\}⌋} \binom{n−m}{s·h}\binom{m}{s·(k−h)} ,

and we come to the following conclusion: Proposition 2 Fractions from the Farey subsequences F(𝔹(n), m) and F(𝔹(n), n − m) satisfy the equality:

∑_{\begin{matrix}\frac{h}{k} ∈F(𝔹(n),m): \\ \frac{0}{1} < \frac{h}{k} < \frac{1}{1} \end{matrix}} ∑_{1≤s≤⌊min\{\frac{m}{h} , \frac{n−m}{k−h}\}⌋} \binom{m}{s·h}\binom{n−m}{s·(k−h)}
= ∑_{\begin{matrix}\frac{h}{k} ∈F(𝔹(n),n−m): \\ \frac{0}{1} < \frac{h}{k} < \frac{1}{1} \end{matrix}} ∑_{1≤s≤⌊min\{\frac{n−m}{h} , \frac{m}{k−h}\}⌋} \binom{n−m}{s·h}\binom{m}{s·(k−h)}
= 2^{n} − 2^{m} − 2^{n−m} + 1 .

3. The Farey Subsequence F(𝔹(2m), m) Denote the left and right halfsequences of F(𝔹(2m), m) by

F^{≤ \frac{1}{2}}(𝔹(2m), m) : = (f ∈ F(𝔹(2m), m) : f ≤ \frac{1}{2})

and

F^{≥ \frac{1}{2}}(𝔹(2m), m) : = (f ∈ F(𝔹(2m), m) : f ≥ \frac{1}{2}) ,

respectively. Lemma 3 [6] The maps

F(𝔹(2m), m) → F(𝔹(2m), m) ,  \frac{h}{k} ↦ \frac{k−h}{k} ,  [\begin{matrix}h \\ k \end{matrix}] ↦ [ \begin{matrix}−1 & 1 \\ 0 & 1 \end{matrix} ] · [\begin{matrix}h \\ k \end{matrix}] ,
F^{≤ \frac{1}{2}}(𝔹(2m), m) → F^{≤ \frac{1}{2}}(𝔹(2m), m) ,  \frac{h}{k} ↦ \frac{k−2h}{2k−3h} ,  [\begin{matrix}h \\ k \end{matrix}] ↦ [ \begin{matrix}−2 & 1 \\ −3 & 2 \end{matrix} ] · [\begin{matrix}h \\ k \end{matrix}] ,

and

F^{≥ \frac{1}{2}}(𝔹(2m), m) → F^{≥ \frac{1}{2}}(𝔹(2m), m) ,  \frac{h}{k} ↦ \frac{h}{3h−k} ,  [\begin{matrix}h \\ k \end{matrix}] ↦ [ \begin{matrix}1 & 0 \\ 3 & −1 \end{matrix} ] · [\begin{matrix}h \\ k \end{matrix}] ,

are order-reversing and bijective.

Corollary 4 The maps

F^{≤ \frac{1}{2}}(𝔹(2m), m) → F^{≥ \frac{1}{2}}(𝔹(2m), m) ,  \frac{h}{k} ↦ \frac{k−h}{2k−3h} ,  [\begin{matrix}h \\ k \end{matrix}] ↦ [ \begin{matrix}−1 & 1 \\ −3 & 2 \end{matrix} ] · [\begin{matrix}h \\ k \end{matrix}] ,

and

F^{≥ \frac{1}{2}}(𝔹(2m), m) → F^{≤ \frac{1}{2}}(𝔹(2m), m) ,  \frac{h}{k} ↦ \frac{2h−k}{3h−k} ,  [\begin{matrix}h \\ k \end{matrix}] ↦ [ \begin{matrix}2 & −1 \\ 3 & −1 \end{matrix} ] · [\begin{matrix}h \\ k \end{matrix}] ,

are order-preserving and bijective.

Let f_{t_{3}^{1}}, f_{t_{2}^{1}}, f_{t_{3}^{2}}, f_{t_{1}^{1}} ∈ F(𝔹(2m), m), m > 1, where

f_{t_{3}^{1}} := \frac{1}{3} , f_{t_{2}^{1}} := \frac{1}{2} , f_{t_{3}^{2}} := \frac{2}{3} , f_{t_{1}^{1}} := \frac{1}{1} ;

then Lemma 3 and Corollary 4 imply that t_{2}^{1} = 2t_{3}^{1} , t_{3}^{2} = 3t_{3}^{1} , and t_{1}^{1} = 4t_{3}^{1} . This in particular means that the number |F(𝔹(2m), m)| − 1 =: t_{1}^{1} is divisible by four.

4. The Farey Sequence F_{m} and the Farey Subsequence F(𝔹(2m), m)

Let h be a positive integer, and [i, l] := {j : i ≤ j ≤ l} an interval of positive integers. Let

ϕ(h; [i, l]) := |{j ∈ [i, l] : gcd(h, j) = 1}| ;

thus, ϕ(h; [1, h]) is the Euler ϕ-function. Recall that for a nonempty interval of positive integers [i′ +1, i′′] it holds ϕ(h; [i′ +1, i′′]) = ∑_{d∈[1,min\{i′′,h\}]: d|h} \overline{μ}(d) · (⌊\frac{i′′}{d} ⌋ − ⌊\frac{i′}{d} ⌋), where d|h means that d divides h, and \overline{μ}(·) stands for the Möbius function: \overline{μ}(1) := 1; if p^{2}|d, for some prime p, then \overline{μ}(d) := 0; if d = p_{1}p_{2} ⋯ p_{s} is the product of distinct primes p_{1}, p_{2}, …, p_{s}, then \overline{μ}(d) := (−1)^{s}.

Let m be an integer, m > 1. For every integer h, 1 ≤ h ≤ m, we have

|\{\frac{h}{k} ∈ F(𝔹(2m), m) : \frac{h}{k} < \frac{1}{2}\}| = ϕ(h; [2h + 1, h + m])

= ∑_{d∈[1,h]: d|h} \overline{μ}(d) · (⌊\frac{h+m}{d}⌋ − \frac{2h}{d}) = ∑_{d∈[1,h]: d|h} \overline{μ}(d) · (⌊\frac{m}{d}⌋ − \frac{h}{d})

= ϕ(h; [h + 1, m]) = |\{\frac{h}{k} ∈ F_{m} : \frac{h}{k} < \frac{1}{1}\}| ;

hence, the sequences F^{≤ \frac{1}{2}}(𝔹(2m), m) and F_{m} are of the same cardinality. Noticing that fractions \frac{h_{j}}{k_{j}} and \frac{h_{j+1}}{k_{j+1}} are consecutive in F_{m} if and only if the fractions \frac{h_{j}}{k_{j}+h_{j}} and \frac{h_{j+1}}{k_{j+1}+h_{j+1}} are consecutive in F^{≤ \frac{1}{2}}(𝔹(2m), m), we arrive, with the help of Lemma 3 and Corollary 4, at the following conclusion:

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A20 5

Theorem 5 Let m be an integer, m > 1. The maps

F^{≤ \frac{1}{2}}(𝔹(2m), m) → F_{m} , \frac{h}{k} ↦ \frac{h}{k−h} , [\begin{matrix}h \\ k \end{matrix}] ↦ [ \begin{matrix}1 & 0 \\ −1 & 1 \end{matrix} ] · [\begin{matrix}h \\ k \end{matrix}] ,

and

F_{m} → F^{≤ \frac{1}{2}}(𝔹(2m), m) , \frac{h}{k} ↦ \frac{h}{k+h} , [\begin{matrix}h \\ k \end{matrix}] ↦ [ \begin{matrix}1 & 0 \\ 1 & 1 \end{matrix} ] · [\begin{matrix}h \\ k \end{matrix}] ,

are order-preserving and bijective; the maps

F^{≥ \frac{1}{2}}(𝔹(2m), m) → F_{m} , \frac{h}{k} ↦ \frac{k−h}{h} , [\begin{matrix}h \\ k \end{matrix}] ↦ [ \begin{matrix}−1 & 1 \\ 1 & 0 \end{matrix} ] · [\begin{matrix}h \\ k \end{matrix}] ,

and

F_{m} → F^{≥ \frac{1}{2}}(𝔹(2m), m) , \frac{h}{k} ↦ \frac{k}{k+h} , [\begin{matrix}h \\ k \end{matrix}] ↦ [ \begin{matrix}0 & 1 \\ 1 & 1 \end{matrix} ] · [\begin{matrix}h \\ k \end{matrix}] ,

are order-reversing and bijective.

Direct counting gives |F(𝔹(2), 1)| = 3 and |F(𝔹(4), 2)| = 5.

Since |F_{m}| − 1 = \frac{1}{2} ∑_{d≥1} \overline{μ}(d) · ⌊\frac{m}{d}⌋ · ⌊\frac{m}{d} + 1⌋ (see, e.g., [4, §4.9]), Theorem 5 implies that for m > 1 we have

|F(𝔹(2m), m)| − 1 = ∑_{d≥1} \overline{μ}(d) · ⌊\frac{m}{d}⌋ · ⌊\frac{m}{d} + 1⌋ .

By means of Theorem 5, the descriptions of sequences F_{m} and F(𝔹(2m), m) supplement each other. For example, consider a fraction \frac{h}{k} ∈ F_{m} − \{\frac{0}{1}, \frac{1}{1}\}. If x_{0} is the integer such that hx_{0} ≡ −1 (mod k) and m − k + 1 ≤ x_{0} ≤ m, then it is known (see, e.g., [2, §27.1]) that the fraction \frac{hx_{0}+1}{k}/x_{0} succeeds the fraction \frac{h}{k} in F_{m}. Similarly, if x_{0} is the integer such that hx_{0} ≡ 1 (mod k) and m − k + 1 ≤ x_{0} ≤ m, then the fraction \frac{hx_{0}−1}{k}/x_{0} precedes \frac{h}{k} in F_{m}. Theorem 5 leads to an analogous statement: Remark 6 Let m be an integer, m > 1.

(i) Let \frac{h}{k} ∈ F(𝔹(2m), m). Suppose that \frac{0}{1} < \frac{h}{k} ≤ \frac{1}{2}. Let x_{0} be the integer such that hx_{0} ≡ 1 (mod (k − h)) and m − k + h + 1 ≤ x_{0} ≤ m. The fraction \frac{hx_{0}−1}{k−h} / \frac{kx_{0}−1}{k−h} precedes \frac{h}{k} in F(𝔹(2m), m).

(ii) Let \frac{h}{k} ∈ F(𝔹(2m), m). Suppose that \frac{0}{1} ≤ \frac{h}{k} < \frac{1}{2}. Let x_{0} be the integer such that hx_{0} ≡ −1 (mod (k − h)) and m − k + h + 1 ≤ x_{0} ≤ m. The fraction \frac{hx_{0}+1}{k−h} / \frac{kx_{0}+1}{k−h} succeeds \frac{h}{k} in F(𝔹(2m), m).

Proposition 2 can be reformulated in the case where n := 2m, with the help of the bijections mentioned in Lemma 3 and Corollary 4, in several ways which we now summarize:

Proposition 7 Let m be an integer, m > 1. The following combinatorial identities hold for fractions from the Farey subsequence F(𝔹(2m), m):

(i)

∑_{\begin{matrix}\frac{h}{k} ∈F(𝔹(2m),m): \\ \frac{0}{1} < \frac{h}{k} < \frac{1}{1} \end{matrix}} ∑_{1≤s≤⌊min\{\frac{m}{h} , \frac{m}{k−h}\}⌋} \binom{m}{s·h}\binom{m}{s·(k−h)} = 2^{2m} − 2^{m+1} + 1 .

(ii)

\begin{aligned}∑_{\begin{matrix}\frac{h}{k} ∈F(𝔹(2m),m): \\ \frac{0}{1} < \frac{h}{k} < \frac{1}{2} \end{matrix}} ∑_{1≤s≤⌊\frac{m}{k−h}⌋} \binom{m}{s·h}\binom{m}{s·(k−h)} & = ∑_{\begin{matrix}\frac{h}{k} ∈F(𝔹(2m),m): \\ \frac{1}{2} < \frac{h}{k} < \frac{1}{1} \end{matrix}} ∑_{1≤s≤⌊\frac{m}{h}⌋} \binom{m}{s·h}\binom{m}{s·(k−h)} \\ & = 2^{2m−1} − 2^{m} − \frac{1}{2} \binom{2m}{m} + 1 . \end{aligned}

(iii)

\begin{matrix}∑_{\begin{matrix}\frac{h}{k} ∈F(𝔹(2m),m): \\ \frac{0}{1} < \frac{h}{k} < \frac{1}{3} \end{matrix}} & ∑_{1≤s≤⌊\frac{m}{k−h}⌋} & \binom{m}{s·(k−h)} & (\binom{m}{s·h} + \binom{m}{s·(k−2h)}) \\ = ∑_{\begin{matrix}\frac{h}{k} ∈F(𝔹(2m),m): \\ \frac{1}{3} < \frac{h}{k} < \frac{1}{2} \end{matrix}} ∑_{1≤s≤⌊\frac{m}{k−h}⌋} \binom{m}{s·(k−h)} (\binom{m}{s·h} + \binom{m}{s·(k−2h)}) \end{matrix}

= ∑_{\begin{matrix}\frac{h}{k} ∈F(𝔹(2m),m): \\ \frac{1}{2} < \frac{h}{k} < \frac{2}{3} \end{matrix}} ∑_{1≤s≤⌊\frac{m}{h}⌋} \binom{m}{s·h} (\binom{m}{s·(k−h)} + \binom{m}{s·(2h−k)})

= ∑_{\begin{matrix}\frac{h}{k} ∈F(𝔹(2m),m): \\ \frac{2}{3} < \frac{h}{k} < \frac{1}{1} \end{matrix}} ∑_{1≤s≤⌊\frac{m}{h}⌋} \binom{m}{s·h} (\binom{m}{s·(k−h)} + \binom{m}{s·(2h−k)})

= 2^{2m−1} − 2^{m} − \frac{1}{2} \binom{2m}{m} − ∑_{1≤t≤⌊\frac{m}{2}⌋} \binom{m}{2t}\binom{m}{t} + 1 .

The bijections between the Farey sequence F_{m} and the halfsequences of F(𝔹(2m), m), presented in Theorem 5, allow us to describe the properties of fractions from F_{m}, analogous to those of fractions from F(𝔹(2m), m), presented in Proposition 7(ii,iii):

Corollary 8 Let m be an integer, m > 1. The following combinatorial identities hold for fractions from the standard Farey sequence F_{m}:

(i)

∑_{\begin{matrix}\frac{h}{k} ∈F_{m}: \\ \frac{0}{1} < \frac{h}{k} < \frac{1}{1} \end{matrix}} ∑_{1≤s≤⌊\frac{m}{k}⌋} \binom{m}{s·h}\binom{m}{s·k} = 2^{2m−1} − 2^{m} − \frac{1}{2} \binom{2m}{m} + 1 .

(ii)

∑_{\begin{matrix}\frac{h}{k} ∈F_{m}: \\ \frac{0}{1} < \frac{h}{k} < \frac{1}{2} \end{matrix}} ∑_{1≤s≤⌊\frac{m}{k}⌋} \binom{m}{s·k} (\binom{m}{s·h} + \binom{m}{s·(k−h)})

= ∑_{\begin{matrix}\frac{h}{k} ∈F_{m}: \\ \frac{1}{2} < \frac{h}{k} < \frac{1}{1} \end{matrix}} ∑_{1≤s≤⌊\frac{m}{k}⌋} \binom{m}{s·k} (\binom{m}{s·h} + \binom{m}{s·(k−h)})

= 2^{2m−1} − 2^{m} − \frac{1}{2} \binom{2m}{m} − ∑_{1≤t≤⌊\frac{m}{2}⌋} \binom{m}{2t}\binom{m}{t} + 1 .

References

[1] D. Acketa and J. Žunić, On the number of linear partitions of the (m, n)-grid, Inform. Process. Lett. 38 (1991), no. 3, 163–168.

[2] A.A. Buchstab, Teoriya Chisel (in Russian) [Number Theory], Uchpedgiz, Moscow, 1960.

[3] S.B. Gashkov and V.N. Chubarikov, Arifmetika. Algoritmy. Slozhnost’ Vychisleniy, Third edition (in Russian) [Arithmetic. Algorithms. Complexity of Computation], Drofa, Moscow, 2005.

[4] R.L. Graham, D.E. Knuth and O. Patashnik, Concrete Mathematics. A Foundation for Computer Science, Second edition, Addison-Wesley, Reading Massachusetts, 1994.

[5] G.H. Hardy and E.M. Wright, An Introduction to the Theory of Numbers, Fifth edition, Clarendon Press, Oxford, 1979.

[6] A.O. Matveev, Pattern recognition on oriented matroids: Layers of tope committees, arXiv:math.CO/0612369.

[7] A.O. Matveev, Relative blocking in posets, J. Comb. Optim. 13 (2007), no. 4, 379–403.

[8] I. Niven, H.S. Zuckerman and H.L. Montgomery, An Introduction to the Theory of Numbers, Fifth edition, John Wiley & Sons, Inc., New York, 1991.

[9] J.J. Tattersall, Elementary Number Theory in Nine Chapters, Second edition, Cambridge University Press, Cambridge, 2005.