Skip to main content
6 of 6
fixed further details and added an obvious upper bound on bim(S)
Salvo Tringali
  • 10.5k
  • 2
  • 29
  • 64

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

Let a discrete interval be a set of the form $\{x \in \mathbb Z \colon a \le x \le b\}$ with $a, b \in \mathbb Z \cup \{\pm \infty\}$. Then 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 whose union is $S$, 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). Note also that $\text{bim}(S) \le |S|$.

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$. On the other hand, the set of even integers and that 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?

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 (algebraic) objects naturally arising from additive combinatorics 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