Skip to main content
5 of 6
fixed another (and more critical) detail
Salvo Tringali
  • 10.5k
  • 2
  • 29
  • 64

Decomposing a set of integers as a union of well-separated (discrete) intervals

Let us define the boxing dimension $\text{bim}(S)$ of a set $S \subseteq \mathbb Z$ as the smallest integer $k \ge 0$ for which there is a family of $k$ discrete intervals (that is, finite or infinite intervals of the poset of integers with their usual ordering) that cover $S$ (in the sense that $S$ is contained in equal to their union), with the understanding that if no such integer $k$ exists then $\text{bim}(S) := \infty$.

The boxing dimension of the set $S$ is zero if and only if $S$ is empty, and it is one if and only if $S$ is a discrete interval. More generally, the boxing dimension of $S$ is equal to a certain integer $k \ge 0$ if and only if there is a unique way to decompose $S$ as a union of $k$ well-separated non-empty discrete intervals, where we say that two sets $X, Y \subseteq \mathbb Z$ are well separated if $|x-y| \ge 2$ for all $x \in X$ and $y \in Y$ (so, well-separated sets are disjoint).

For instance, the sets $A := \{0, 5\} \cup \mathbb N_{\ge 7}$ and $B := \{-2, 2, 3\}$ are well separated, with $\text{bim}(A) = 3$ and $\text{bim}(B) = 2$. To the contrary, the set of even integers and the set of odd integers are not well separated, with the boxing dimension of each of them being infinite.

MY QUESTIONS. (1) Does (what I'm calling) the boxing dimension have a more standard name? Or is it a special case of a more general standard notion? (2) Likewise, do well-separated subsets of $\mathbb Z$ have a more standard name? Or are they a special case of a more general standard notion?

For what it's worth, my interest in this notion comes from a joint project with Weihao Yan (an undergraduate student at Hebei Normal University), where the classification of the automorphism group of certain objects boils down to a (somewhat unusual) induction on the boxing dimension of certain finite subsets of $\mathbb N$.

Salvo Tringali
  • 10.5k
  • 2
  • 29
  • 64