3
$\begingroup$

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$.

$\endgroup$
2
  • 1
    $\begingroup$ In other words, $\operatorname{bim}(S)$ is the number of connected components in the graph $G$ with vertex set $V(G)=S$ and edge set $E(G)=\{\{x,y\}\subseteq S:|x-y|=1\}$. Right? $\endgroup$
    – bof
    Commented Feb 18, 2023 at 22:03
  • $\begingroup$ @bof Right. It's also the shortest length of a factorization of the set $S$ as a union of (non-empty, discrete) intervals in the commutative monoid obtained by endowing the power set of $\mathbb Z$ with the binary operation $(X,Y) \mapsto X \cup Y$. The "shortest factorization length" is an arithmetic invariant studied in a variety of settings for a wide range of "building blocks" (or "elementary factors") that one may want to use all along the factorization process. So, I find this point of view more natural. $\endgroup$ Commented Apr 2, 2023 at 21:14

1 Answer 1

3
$\begingroup$

We have a similar concept on numerical semigroups, borrowed from the idea of run.

For a numerical semigroup, a desert is an run of gaps (non-negative integers not belonging to the semigroup), and it has some connections with the second Feng-Rao number of the semigroup, related to algebro-geometric codes.

In this setting, for a numerical semigroup $S$, then you can count deserts as the cardinality of the Apéry set of -1, that is, the cardinality of $\{s\in S : s+1\not\in S\}$.

In any case, I my feeling is that you should allow infinite intervals in your definition. Then, the Apéry set of 1 would also recover the interval $[-\infty,-1]$.

$\endgroup$
3
  • $\begingroup$ Hi Pedro. :-) I edited the OP to clarify that yes, also infinite intervals are allowed in the definition of the boxing dimension. $\endgroup$ Commented Feb 18, 2023 at 11:01
  • 1
    $\begingroup$ Good! Probably, someone has used this concept to measure how many runs of integers has a numerical semigroup, which should be less than or equal to the number of what people call sporadic elements (or small elements, or left elements - say elements below the conductor). $\endgroup$ Commented Feb 18, 2023 at 11:04
  • $\begingroup$ To me, (what I'm calling) the boxing dimension looks like a natural notion for all sets of integers. In particular, Weihao and I are using it as a measure of the "complexity" of a finite subset of $\mathbb N$. Let's see if someone else comes up with other pointers, it's quite hard to believe that the notion hasn't shown up before in the literature. $\endgroup$ Commented Feb 18, 2023 at 18:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .