(2) for m ≤ n−1, that inherit many familiar properties of the Farey sequences

A NOTE ON BOOLEAN LATTICES AND FAREY SEQUENCES II

Andrey O. Matveev

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

[email protected], [email protected]

Received: 2/1/08, Revised: 4/1/08, Accepted: 5/2/08, Published: 5/21/08

Abstract

We establish monotone bijections between subsequences of the Farey sequences and the half- sequences of Farey subsequences associated with elements of the Boolean lattices.

1. Introduction

The Farey sequence of order n, denoted by Fⁿ, is the ascending sequence of irreducible fractions ^h_k ∈ Q such that ⁰₁ ≤ ^h_k ≤ ¹₁ and 1 ≤ k ≤ n; see, e.g., [3, Chapter 27], [4, §3], [5, Chapter 4], [6, Chapter III], [11, Chapter 6], [12, Chapter 6], [13, Sequences A006842 and A006843], [14, Chapter 5].

The Farey sequence of order ncontains the subsequences Fn^m :=!_h

k ∈Fⁿ : h ≤m"

, (1)

for all integersm ≥1, and the subsequences Gn^m :=!_h

k ∈Fn : k−h≤n−m"

, (2)

for m ≤ n−1, that inherit many familiar properties of the Farey sequences. In particular, if n >1 and m≥n−1, thenFn^m =Fn; if n >1 andm ≤1, thenGn^m =Fn.

The Farey subsequence Fn^m was presented in [1], and some comments were given in [10, Remark 7.10].

Let B(n) denote the Boolean lattice of rank n > 1, whose operation of meet is denoted by∧. Ifais an element of B(n), of rankρ(a) =:m such that 0< m < n, then the integers n and m determine the subsequence

F!

B(n), m"

: =#

ρ(b∧a) gcd(ρ(b∧a),ρ(b))

$ ρ(b)

gcd(ρ(b∧a),ρ(b)) : b∈B(n), ρ(b)>0%

=!_h

k ∈Fn: h≤m, k−h≤n−m" (3)

of Fn, considered in [7, 8, 9, 10].

Notice that the map F!

B(n), m"

→F!

B(n), n−m"

, ^h_k '→ ^k−_k^h , [^h_k]'→[⁻_{0 1}^{1 1}]·[^h_k] , (4) is order-reversing and bijective, by analogy with the map

Fn →Fn , ^h_k '→ ^k−_k^h , [^h_k]'→[⁻_{0 1}^{1 1}]·[^h_k] , (5) which is order-reversing and bijective as well; here [^h_k] ∈ Z² is a vector presentation of the fraction ^h_k.

We call the ascending sets F^≤12!

B(n), m"

:=!_h

k ∈F!

B(n), m"

: ^h_k ≤ ¹₂"

, and

F^≥12!

B(n), m"

:=!_h

k ∈F!

B(n), m"

: ^h_k ≥ ¹₂"

. the left and right halfsequences of the sequence F!

B(n), m"

, respectively.

This work is a sequel to note [7] which concerns the sequences F!

B(2m), m"

. See [7] for more about Boolean lattices, Farey (sub)sequences and related combinatorial identities.

The key observation is Theorem 3 which in particular asserts that there is a bijection between the sequenceFn^m−m and the left halfsequence ofF!

B(n), m"

, on the one hand; there is also a bijection between the sequenceFm^n−m and the right halfsequence ofF!

B(n), m"

, on the other hand.

Throughout the note, n and m represent integers; n is always greater than one. The fractions of Farey (sub)sequences are indexed starting with zero. Terms ‘precedes’ and

‘succeeds’ related to pairs of fractions always mean relations of immediate consecution. When we deal with a Farey subsequenceF!

B(n), m"

, we implicitly suppose 0< m < n.

2. The Farey Subsequences Fn^m and Gn^m

The connection between the sequences of the form (1) and (2) comes from their definitions:

Lemma 1 The maps

Fn^m →Gn^n−m , ^h_k '→ ^k−_k^h , [^h_k]'→[⁻_{0 1}^{1 1}]·[^h_k] , and

Gn^m →Fn^n−m , ^h_k '→ ^k−_k^h , [^h_k]'→[⁻_{0 1}^{1 1}]·[^h_k] , are order-reversing and bijective, for any m, 0≤m ≤n.

Following [2, §4.15], we let µ(·) denote the M¨obius function on positive integers. For an interval of positive integers [i, l] := {j : i ≤ j ≤ l} and for a positive integer h, let φ(h; [i, l]) :=|{j ∈[i, l] : gcd(h, j) = 1}|.

We now describe several basic properties of the sequences Gn^m which are dual, in view of Lemma 1, to those of the sequences Fn^n−m, cf. [10, Remark 7.10].

Remark 2 Suppose 0≤m < n.

(i) In Gn^m= (g0 < g1 <· · ·< g_|Gn^m_|−2 < g_|Gn^m_|−1), we have

g0 = ⁰₁ , g1 = min{n−m+1,n}¹ , g_|G^m_n|−2 = ⁿ⁻_n¹ , g_|Gn^m_|−1 = ¹₁ . (ii) (a) The cardinality of the sequence Gn^m equals

1 + &

j∈[1,n]

φ!

j; [max{1, j+m−n}, j]"

= 1 + &

j∈[1,n−m+1]

φ!

j; [1, j]"

+ &

j∈[n−m+2,n]

φ!

j; [j+m−n, j]"

= 1 +&

d≥1

µ(d)·#'_n

d

(− ¹₂'_n−m

d

(%·'_n−m

d + 1( .

(b) If gt ∈Gn^m−{⁰₁}, then t = &

j∈[1,n]

φ!

j; [max{1, j +m−n},(j·gt)]"

= &

j∈[1,n−m+1]

φ!

j; [1,(j·gt)]"

+ &

j∈[n−m+2,n]

φ!

j; [j+m−n,(j·gt)]"

= 1 +&

d≥1

µ(d)· )'_n−m

d

(·#'_n

d

(− ¹₂'_n−m

d + 1(%

− &

j∈[1,&n/d']

min*'_n−m

d

(,(j·(1−gt))+, .

(iii) Let ^h_k ∈Gn^m, ⁰₁ < ^h_k < ¹₁.

(a) Let x0 be the integer such that kx0 ≡ −1 (mod h) and m−h+ 1 ≤ x0 ≤ m.

Define integers y0 and t^∗ by y0 := ^kx0_h⁺¹ and t^∗ := '

min-_{n−m+x0−y0}

k−h ,^n−y_k ⁰.(

. The fraction ^x_y0^0+t_+t^∗_∗k^h precedes the fraction ^h_k in Gn^m.

(b) Let x0 be the integer such that kx0 ≡ 1 (mod h) and m−h+ 1 ≤ x0 ≤ m.

Define integers y₀ and t^∗ by y₀ := ^kx0_h⁻¹ and t^∗ := '

min-_{n−m+x0−y0}

k−h ,ⁿ⁻_k^y0.(

. The fraction ^x_y0^0+t_+t^∗_∗k^h succeeds the fraction ^h_k in Gn^m.

(iv) (a) If ^h_k^j

j < ^h_k^j+1

j+1 are two successive fractions of Gn^m then kjhj+1−hjkj+1 = 1 .

(b) If ^h_k^j_j < ^h_k^j+1_j+1 < ^h_kj+2^j+2 are three successive fractions of Gn^m then

hj+1

kj+1 = _gcd(h ^hj+hj+2

j+hj+2,kj+kj+2)

$ kj+kj+2

gcd(hj+hj+2,kj+kj+2) . (c) If ^h_k^j

j < ^h_k^j+1

j+1 < ^h_k^j+2

j+2 are three successive fractions of Gn^m then the integers h_j, k_j, hj+2 and kj+2 are related in the following way:

hj =/ min*

kj+2+n

kj+1 ,^kj+2_kj+1^−hj+2_−hj+1^+n−m+0

hj+1−hj+2 , kj =/

min*_k

j+2+n

kj+1 ,^kj+2_k^{−hj+2+n−m}

j+1−hj+1

+0kj+1−kj+2 ,

hj+2 =/ min*

kj+n

kj+1,^k_k^j−hj+n−m

j+1−hj+1

+0hj+1−hj ,

k_j+2 =/ min*

kj+n

kj+1,^k_k^j−hj+n−m

j+1−hj+1

+0k_j+1−k_j .

(v) If ¹_k ∈Gn^m, where n >1, for some k >1, then the fraction

&min{ⁿ⁻_k−1^m−1,ⁿ⁻_k¹}'

k&min{^n−m−1_k−1 ,ⁿ⁻¹_k }'+1 precedes ¹_k, and the fraction ^&min{

n−m+1 k−1 ,ⁿ⁺¹_k }'

k&min{^n−m+1_k−1 ,ⁿ⁺¹_k }'−1 succeeds ¹_k in Gn^m.

3. The Farey Subsequence F!

B(n), m"

Definition (3) implies that a Farey subsequenceF!

B(n), m"

can be regarded as the intersec- tion

F!

B(n), m"

=Fn^m∩Gn^m .

Its halfsequences can be described with the help of the following statement:

Theorem 3 Consider a Farey subsequence F!

B(n), m"

. The maps F^≤12!

B(n), m"

→Fn^m−m , ^h_k '→ _k−h^h , [^h_k]'→[₋^{1 0}_{1 1}]·[^h_k] , (6) F_n−m^m →F^≤12!

B(n), m"

, ^h_k '→ _k+h^h , [^h_k]'→[^{1 0}_{1 1}]·[^h_k] , (7) F^≥12!

B(n), m"

→Gm^2m−n , ^h_k '→ ^2h_h^−k , [^h_k]'→[²_{1 0}⁻¹]·[^h_k] , (8) and

Gm^2m−n →F^≥12!

B(n), m"

, ^h_k '→ _2k^k_−h , [^h_k]'→[_{−1 2}^{0 1}]·[^h_k] , (9)

are order-preserving and bijective.

The maps F^≤12!

B(n), m"

→Gn^n−2m−m , ^h_k '→ ^k_k⁻₋^2h_h , [^h_k]'→1_{−2 1}

−1 1

2·[^h_k] , G_n−m^n−2m →F^≤12!

B(n), m"

, ^h_k '→ _2k−h^k−h , [^h_k]'→1_{−1 1}

−1 2

2·[^h_k] , F^≥12!

B(n), m"

→Fm^n−m , ^h_k '→ ^k−h_h , [^h_k]'→[^{−1 1}_{1 0}]·[^h_k] , (10) and

Fm^n−m →F^≥12!

B(n), m"

, ^h_k '→ _k+h^k , [^h_k]'→[^{0 1}_{1 1}]·[^h_k] , (11) are order-reversing and bijective.

Proof. For any integerh, 1≤h≤m, we have 33-^h_k ∈F!

B(n), m"

: ^h_k < ¹₂.33=φ(h; [2h+ 1, h+n−m])

= &

d∈[1,h]: d|h

µ(d)·!'_h+n−m

d

(− ^2h_d"

= &

d∈[1,h]: d|h

µ(d)·!'_n−m

d

(− ^h_d"

=φ(h; [h+ 1, n−m]) = 33-^h

k ∈F_n−m^m : ^h_k < ¹₁.33 and see that the sequences F^≤12!

B(n), m"

and Fn^m−m are of the same cardinality, but this conclusion also implies 33F^≥12!

B(n), m"33 = |Fm^n−m|, due to bijection (4). The proof of the assertions concerning maps (6), (7), (10) and (11) is completed by checking that, on the one hand, a fraction ^h_k^j

j precedes a fraction ^h_k^j+1

j+1 in F_n−m^m if and only if the fraction _k^hj

j+hj

precedes the fraction _kj+1^hj+1_+hj+1 inF^≤12!

B(n), m"

; on the other hand, a fraction ^h_kj^j precedes a fraction ^h_k^j+1

j+1 inFm^n−mif and only if _k ^kj+1

j+1+hj+1 precedes _k^kj

j+hj inF^≥12!

B(n), m"

. The remaining

assertions of the theorem now follow, thanks to Lemma 1. !

For example,

F⁶ =!₀

1 < ¹₆ < ¹₅ < ¹₄ < ¹₃ < ²₅ < ¹₂ < ³₅ < ²₃ < ³₄ < ⁴₅ < ⁵₆ < ¹₁"

, F6⁴ =!₀

1 < ¹₆ < ¹₅ < ¹₄ < ¹₃ < ²₅ < ¹₂ < ³₅ < ²₃ < ³₄ < ⁴₅ < ¹₁"

, G6⁴ =!₀

1 < ¹₃ < ¹₂ < ³₅ < ²₃ < ³₄ < ⁴₅ < ⁵₆ < ¹₁"

, F!

B(6),4"

=!₀

1 < ¹₃ < ¹₂ < ³₅ < ²₃ < ³₄ < ⁴₅ < ¹₁"

, F₆₋₄⁴ =F2 =!₀

1 < ¹₂ < ¹₁"

,

G4^2·4−6 =G4² = !₀

1 < ¹₃ < ¹₂ < ²₃ < ³₄ < ¹₁"

, G₆₋₄^6−2·4 =F2 =!₀

1 < ¹₂ < ¹₁"

, F4⁶⁻⁴ =F4² = !₀

1 < ¹₄ < ¹₃ < ¹₂ < ²₃ < ¹₁"

.

Theorem 3 allows us to write down the formula 33F!

B(n), m"33=|F_n−m^m |+|Fm^n−m|−1 =33Fn^min−m^{m,n−m}

33+33Fm^min{m,n−m}

33−1 ,

for the number of elements of a sequenceF!

B(n), m"

, cf. [10, Proposition 7.3(ii)]. Recall that

|Fq^p|= 1 +4

d≥1µ(d)·!'_q

d

(− ¹₂'_p

d

("

·'_p

d+ 1(

, for any Farey subsequenceFq^p with 0< p ≤q;

see [10, Remark 7.10(ii)(b)]. Notice that the well-known relation4

d≥1µ(d)·'_t

d

( = 1, for any positive integer t, leads us to one more formula: |Fq^p|= ³₂ +4

d≥1µ(d)·'_p

d

(·!'_q

d

(− ¹₂'_p

d

("

. Thus, we have

33F!

B(n), m"33= 3 2+&

d≥1

µ(d)·/

min{m,n−m}

d

0·#'_n−m

d

(− ¹₂/

min{m,n−m}

d

0%

+3 2 +&

d≥1

µ(d)·/

min{m,n−m} d

0·#'_m

d

(− ¹₂/

min{m,n−m} d

0%−1

or 33F!

B(n), m"33= 2 +&

d≥1

µ(d)·/

min{m,n−m}

d

0·#'_n−m

d

(+'_m

d

(−/

min{m,n−m}

d

0% ,

that is, 33F!

B(n), m"33−2 = &

d≥1

µ(d)·'_m

d

(·'_n−m

d

( .

In particular, for any positive integer t we have

&

d≥1

µ(d)·'_t

d

(2

=33F!

B(2t), t"33−2 = 2|Ft|−3.

Proposition 4 Consider a Farey subsequence F!

B(n), m"

. (i) Suppose m≥ ⁿ₂. The map

F^≤12!

B(n), m"

→F^≤12!

B(n), m"

, ^h_k '→ _2k−3h^k−2h , [^h_k]'→1_{−2 1}

−3 2

2·[^h_k] , (12) is order-reversing and bijective. The map

F^≤12!

B(n), m"

→F^≥12!

B(n), m"

, ^h_k '→ _2k^k−₋^h_3h , [^h_k]'→1_{−1 1}

−3 2

2·[^h_k] , is order-preserving and injective. The map

F^≤12!

B(n), m"

→F^≥12!

B(n), m"

, ^h_k '→ ^k−h_k , [^h_k]'→[⁻_{0 1}^{1 1}]·[^h_k] , is order-reversing and injective.

(ii) Suppose m≤ ⁿ₂. The map F^≥12!

B(n), m"

→F^≥12!

B(n), m"

, ^h_k '→ _3h^h_−k , [^h_k]'→[^{1 0}₃₋₁]·[^h_k] , (13)

is order-reversing and bijective. The map F^≥12!

B(n), m"

→F^≤12!

B(n), m"

, ^h_k '→ ^2h_3h−k^−k , [^h_k]'→1₂₋₁

3−1

2·[^h_k] , is order-preserving and injective. The map

F^≥12!

B(n), m"

→F^≤12!

B(n), m"

, ^h_k '→ ^k−h_k , [^h_k]'→[⁻_{0 1}^{1 1}]·[^h_k] , is order-reversing and injective.

Proof. To prove that map (12) is order-reversing and bijective, notice that F_n−m^m = Fn−m, and consider the composite map

h k

F^≤12(B(n),m)−→^{(6) Fn−m}

'→ _k−h^{h Fn−m}

−→(5) ^Fn−m

'→ ^k_k−h^{−2h Fn−m}

−→(7) ^{F≤12(B(n),m)}

'→ _2k−3h^k−2h .

Similarly, under the hypothesis of assertion (ii) we haveGm^2m−n =Fm; consider the composite map

h k

F^≥12(B(n),m)'→ −→^{(8) Fm 2h}_h^{−k Fm}

−→'→(5) ^{Fm k−}_h^{h Fm}

−→(9) ^F'→^{≥12(B(n),m)} _3h^h_−k

to see that map (13) is order-reversing and bijective.

The remaining assertions follow from the observation that map (4) is the order-reversing

bijection. !

We conclude the note by listing a few pairs of fractions adjacent inF!

B(n), m"

; see [8, 9]

on such pairs within the sequences F!

B(2m), m"

. We find the neighbors of the images of several fractions of F!

B(n), m"

under bijections from Theorem 3, and we then reflect them back toF!

B(n), m"

:

Remark 5 Consider a Farey subsequence F!

B(n), m"

, with n,= 2m.

(i) Suppose m > ⁿ₂.

The fraction _2(n^n−m−1_−m)−1 precedes ¹₂, and the fraction _2(n^n−m+1_−m)+1 succeeds ¹₂. The fraction 2 min{n−m,&^m+1₂ '}−1

3 min{n−m,&^m+1₂ '}−1 precedes ²₃; the fraction 2 min{n−m,&^m−₂¹'}+1

3 min{n−m,&^m−1₂ '}+1 succeeds ²₃. If we additionally have n−m >1, then the fraction





n−m−2 2

$3(n−m)−4

2 , if n−m is even,

n−m−1 2

$3(n−m)−1

2 , if n−m is odd, precedes ¹₃; the fraction





n−m 2

$3(n−m)−2

2 , if n−m is even,

n−m+1 2

$3(n−m)+1

2 , if n−m is odd, succeeds ¹₃.

(ii) Suppose m < ⁿ₂.

The fraction _2m+1^m precedes ¹₂, and the fraction _2m^m₋₁ succeeds ¹₂. The fraction _{3 min}^{min{m,&n−m+12 '}−1}

{m,&^n−m+1₂ '}−2 precedes ¹₃; the fraction _{3 min}^{min{m,&n−m−12 '}+1}

{m,&^n−m₂⁻¹'}+2 succeeds ¹₃. If we additionally have m >1, then the fraction





(m−1)$

3m−2

2 , if m is even, m$

3m+1

2 , if m is odd, precedes ²₃; the fraction





(m−1)$

3m−4

2 , if m is even, m$

3m−1

2 , if m is odd, succeeds ²₃.

References

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

[2] M. Aigner,Combinatorial Theory, Reprint of the 1979 original, Classics in Mathematics, Springer-Verlag, Berlin, 1997.

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

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

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

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

[7] A.O. Matveev,A note on Boolean lattices and Farey sequences, Integers7(2007), A20.

[8] A.O. Matveev,Neighboring fractions in Farey subsequences,arXiv:0801.1981.

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

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

[11] 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.

[12] V.V. Prasolov,Zadachi po Algebre, Arifmetike i Analizu (in Russian) [Problems in Algebra, Arithmetic and Analysis], Moskovski˘ı Tsentr Nepreryvnogo Matematicheskogo Obrazovaniya (MCCME), Moscow, 2005.

[13] N.J.A. Sloane, The On-Line Encyclopedia of Integer Sequences, published electronically at www.research.att.com/~njas/sequences/, 2008.

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