Proposition 4.1 — on the bit family the best deterministic competitive ratio is $|\mathcal F| = k = \log_2 n$

Let $k \ge 1$, $n = 2^k$, $X = \{0, \dots, n-1\}$, and let $\mathcal F = \{F_1, \dots, F_k\}$ where $F_i$ is the set of elements of $X$ whose $i$th bit is on. Then the competitive ratio of the best deterministic online algorithm for the online set cover problem $(X, \mathcal F)$ is $|\mathcal F| = k = \log_2 n$. Precisely:

1. $|\mathcal F| = k$;
2. for every valid deterministic online algorithm $A$ there is a nonempty arrival sequence $\sigma$ such that some single set of $\mathcal F$ contains every element of $\sigma$ (so $\mathrm{OPT}(\sigma) = 1$) and

3. there is a valid deterministic online algorithm $A$ such that for every arrival sequence $\sigma$ and every offline cover $C \subseteq \mathcal F$ of $\sigma$, $|\mathcal C_A(\sigma)| \le k\,|C|$.

Parts 2 and 3 together say the optimal deterministic competitive ratio on this instance is exactly $k$. The adversary of part 2 is also the one-block step of the lower bound for the block family of Section 4.

Formalization Note The parameter is $k$ and $n := 2^k$, so $\log_2 n = k$ needs no logarithm. The hypothesis $k \ge 1$ is the paper's implicit one (it indexes $1 \le i \le k$); for $k = 0$ the family is empty and part 2 fails. Element $0$ lies in no $F_i$; validity asks nothing for it, and part 2's sequence avoids it because one set covers it. Algorithms may add several sets per arrival. Part 2 states $\mathrm{OPT}(\sigma) = 1$ and cost $\ge k = k \cdot \mathrm{OPT}(\sigma)$, which is how the paper's proof establishes the ratio.