Skip to main content
11 of 11
re-written everything
Salvo Tringali
  • 10.5k
  • 2
  • 29
  • 64

The set of lengths of $nX$ gets larger and larger for every non-zero, non-empty, finite $X \subseteq \mathbf N$ with $0 \in X$

Let $H$ be a multiplicatively written monoid with identity $1_H$. Given $x \in H$, we take ${\sf L}_H(x) := \{0\}$ if $x = 1_H$; otherwise, ${\sf L}_H(x)$ is the set of all $k \in \mathbf N^+$ for which there exist atoms $a_1, \ldots, a_k \in H$ such that $x = a_1 \cdots a_k$ (let me recall that an atom of $H$ is an element $a \in H \setminus H^\times$ with $a \ne xy$ for all $x, y \in H \setminus H^\times$, where $H^\times$ is the group of units of $H$): In factorization theory, ${\sf L}_H(x)$ is called the set of lengths of $x$ (relative to the atoms of $H$), and we drop the subscript '$H$' from these notations if $H$ is implied from the context. The following holds:

Proposition 1. ${\sf L}(x) + {\sf L}(y) \subseteq {\sf L}(xy),$ and hence $|{\sf L}(xy)| \ge| {\sf L}(x)| + |{\sf L}(y)| - 1$, for all $x, y \in H$.

Sketch of a proof. The second part is a consequence of the fact that $|X+Y| \ge |X| + |Y| - 1$ for all non-empty $X, Y \subseteq \mathbf Z$ (this is a basic inequality in additive combinatorics), while the first part is subtler, insofar as it's first necessary to prove that $1_H \ne xy$ for all non-units $x, y \in H$, unless the set of atoms of $H$ is empty. []

With the above in mind, let $\mathcal P_{{\rm fin},0}(\mathbf N)$ be the monoid of non-empty, finite subsets of $\mathbf N$ containing $0$, equipped with the binary (associative) operation $$\mathcal P_{{\rm fin},0}(\mathbf N) \times \mathcal P_{{\rm fin},0}(\mathbf N) \to \mathcal P_{{\rm fin},0}(\mathbf N): (X, Y) \mapsto \{x+y: x \in X,\, y \in Y\},$$ which we'll denote additively with the symbol "$+$". Note that $\{0\}$ is the identity (and, in fact, the only unit) of $\mathcal P_{{\rm fin},0}(\mathbf N)$. Moreover, $\mathcal P_{{\rm fin},0}(\mathbf N)$ is a (reduced) BF-monoid, that is, $1 \le |\mathsf L(X)| < \infty$ for every non-zero $X \in \mathcal P_{{\rm fin},0}(\mathbf N)$. Then my question is:

Q. Is it true that $|{\sf L}(nX)| \to \infty$ as $n \to \infty$, unless $X = \{0\}$?

And here is something that makes the question a bit more intriguing (at least to my eyes):

Proposition 2. Let $H$ be a multiplicatively written BF-monoid. Then the following are equivalent:

  1. $|{\sf L}(x^n)| \to \infty$, as $n \to \infty$, for every $x \in H \setminus H^\times$.
  1. $\frac{1}{n}|{\sf L}(x^n)| \to \lambda_x \in \mathbf R^+ \cup \{\infty\}$, as $n \to \infty$, for every $x \in H \setminus H^\times$.
  1. For every atom $a \in H$, there exists $n \in \mathbf N^+$ such that $|{\sf L}(a^n)| \ge 2$.

Sketch of a proof. Use Proposition 1 and Fekete's lemma.

It's perhaps worth adding that, in the special case when $H = \mathcal P_{{\rm fin},0}(\mathbf N)$, the limit in Proposition 2.2 is (positive and) finite: Indeed, let $n \in \mathbf N^+$ and suppose that $nX = X_1 + \cdots + X_k$ for some non-zero sets $X_1, \ldots, X_k \subseteq \mathbf N$ (either atoms or not). Then $X_i$ is finite and non-empty for each $i$, and $n \max X = \max X_1 + \cdots + \max X_k \ge k$, which yields $ \frac{1}{n}|{\sf L}(nX)| \le \max X$.

Salvo Tringali
  • 10.5k
  • 2
  • 29
  • 64