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

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.

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

It's perhaps worth observingadding 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$.

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\}$ 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 observing 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$.

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

re-written everything
Source Link
Salvo Tringali
  • 10.5k
  • 2
  • 29
  • 64

Let $\mathcal P_{{\rm fin},0}(\mathbf N)$$H$ be thea multiplicatively written monoid of non-empty, finite subsets of $\mathbf N$ containing $0$ equipped with the 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, as usual, with the symbol "$+$".

We refer to a set $A \in \mathcal P_{{\rm fin},0}(\mathbf N)$ as an atom if (i) $A \ne \{0\}$ and (ii) $A \ne X+Y$ for all $X, Y \in \mathcal P_{{\rm fin},0}(\mathbf N) \setminus \bigl\{\{0\}\bigr\}$: Note that $\{0\}$ is the identity (and, in fact, the only unit) of $\mathcal P_{{\rm fin},0}(\mathbf N)$, so this is nothing but a special instance of the abstract notion of atom (or irreducible element) for an arbitrary monoid$1_H$.

With this in mind, fix Given $X \in \mathcal P_{{\rm fin},0}(\mathbf N)$. We$x \in H$, we take ${\sf L}(X) := \{0\}$${\sf L}_H(x) := \{0\}$ if $X = \{0\}$$x = 1_H$; otherwise, ${\sf L}(X)$${\sf L}_H(x)$ is the set of all $k \in \mathbf N^+$ for which there exist atoms $A_1, \ldots, A_k \in \mathcal P_{{\rm fin},0}(\mathbf N)$$a_1, \ldots, a_k \in H$ such that $X = A_1 + \cdots + A_k$$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}(X)$ would be${\sf L}_H(x)$ is called the set of lengths of $X$$x$ (relative to the atoms of $\mathcal P_{{\rm fin},0}(\mathbf N)$$H$), which explainsand we drop the titlesubscript '$H$' from these notations if $H$ is implied from the context. The following holds:

QProposition 1. Is it true ${\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 $|{\sf L}(nX)| \to \infty$$|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 $n \to \infty$$1_H \ne xy$ for all non-units $x, y \in H$, unless the set of atoms of $X = \{0\}$?$H$ is empty. []

Of course, it's enough to show thatWith the answer is yesabove in mind, let $\mathcal P_{{\rm fin},0}(\mathbf N)$ be the special case whenmonoid of non-empty, finite subsets of $X$ is an atom$\mathbf N$ containing $0$, though I'm not so sure that this makes things any easierequipped 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 "$+$". What is perhaps more interesting is that a positive answer is equivalent to showingNote that there exists $n \in \mathbf N^+$ such that$\{0\}$ is the identity $|\mathsf L(nX)| \ge 2$: This comes as a consequence of a general(and, simplein fact about sets, the only unit) of lengths in factorization theory$\mathcal P_{{\rm fin},0}(\mathbf N)$.

Edit 1. It's probably worth mentioning that 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\}$?

Edit 2. To be completely open, I believe that something much stronger is true: That the limit of $\frac{1}{n} |{\sf L}(nX)|$ as $n \to \infty$ And here is positive (if not even equal to $\infty$) for every non-zero $X \in \mathcal P_{{\rm fin},0}(\mathbf N)$, where the existence ofsomething that makes the limit follows fromquestion a bit more intriguing Fekete's lemma, the general property of sets of lengths alluded(at least to in the above, and the basic fact that $|A+B| \ge |A| + |B|-1$ for all non-empty $A, B \subseteq \mathbf Z$.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\}$ 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.

Edit 3. With reference to Edit 2, let me note that the limit $\frac{1}{n} |{\sf L}(nX)|$ as $n \to \infty$ need not be infinite (and, on a second thought, it sounds much more plausible It's perhaps worth observing that it's always finite). Indeed, considerin the special case when $X = [\![0, m]\!]$ for some $m \in \mathbf N^+$. Then $nX = [\![0, mn]\!]$ for all $n \in \mathbf N^+$, and hence $\frac{1}{n} |{\sf L}(nX)| \to m$ as $n \to \infty$, since it can be proved (this is not for free) that ${\sf L}([\![0, k]\!]) = [\![2,k]\!]$ for every integer $k \ge 2$.

Edit 4. Yes$H = \mathcal P_{{\rm fin},0}(\mathbf N)$, of course: Thethe limit in EditProposition 2.2 is always(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$.

Let $\mathcal P_{{\rm fin},0}(\mathbf N)$ be the monoid of non-empty, finite subsets of $\mathbf N$ containing $0$ equipped with the 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, as usual, with the symbol "$+$".

We refer to a set $A \in \mathcal P_{{\rm fin},0}(\mathbf N)$ as an atom if (i) $A \ne \{0\}$ and (ii) $A \ne X+Y$ for all $X, Y \in \mathcal P_{{\rm fin},0}(\mathbf N) \setminus \bigl\{\{0\}\bigr\}$: Note that $\{0\}$ is the identity (and, in fact, the only unit) of $\mathcal P_{{\rm fin},0}(\mathbf N)$, so this is nothing but a special instance of the abstract notion of atom (or irreducible element) for an arbitrary monoid.

With this in mind, fix $X \in \mathcal P_{{\rm fin},0}(\mathbf N)$. We take ${\sf L}(X) := \{0\}$ if $X = \{0\}$; otherwise, ${\sf L}(X)$ is the set of all $k \in \mathbf N^+$ for which there exist atoms $A_1, \ldots, A_k \in \mathcal P_{{\rm fin},0}(\mathbf N)$ such that $X = A_1 + \cdots + A_k$: In factorization theory, ${\sf L}(X)$ would be called the set of lengths of $X$ (relative to the atoms of $\mathcal P_{{\rm fin},0}(\mathbf N)$), which explains the title.

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

Of course, it's enough to show that the answer is yes in the special case when $X$ is an atom, though I'm not so sure that this makes things any easier. What is perhaps more interesting is that a positive answer is equivalent to showing that there exists $n \in \mathbf N^+$ such that $|\mathsf L(nX)| \ge 2$: This comes as a consequence of a general, simple fact about sets of lengths in factorization theory.

Edit 1. It's probably worth mentioning that $\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)$.

Edit 2. To be completely open, I believe that something much stronger is true: That the limit of $\frac{1}{n} |{\sf L}(nX)|$ as $n \to \infty$ is positive (if not even equal to $\infty$) for every non-zero $X \in \mathcal P_{{\rm fin},0}(\mathbf N)$, where the existence of the limit follows from Fekete's lemma, the general property of sets of lengths alluded to in the above, and the basic fact that $|A+B| \ge |A| + |B|-1$ for all non-empty $A, B \subseteq \mathbf Z$.

Edit 3. With reference to Edit 2, let me note that the limit $\frac{1}{n} |{\sf L}(nX)|$ as $n \to \infty$ need not be infinite (and, on a second thought, it sounds much more plausible that it's always finite). Indeed, consider the case when $X = [\![0, m]\!]$ for some $m \in \mathbf N^+$. Then $nX = [\![0, mn]\!]$ for all $n \in \mathbf N^+$, and hence $\frac{1}{n} |{\sf L}(nX)| \to m$ as $n \to \infty$, since it can be proved (this is not for free) that ${\sf L}([\![0, k]\!]) = [\![2,k]\!]$ for every integer $k \ge 2$.

Edit 4. Yes, of course: The limit in Edit 2 is always 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$.

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\}$ 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 observing 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$.

fixed a typo in the title and in the text
Source Link
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 \mathbf N$X$

Let $\mathcal P_{{\rm fin},0}(\mathbf N)$ be the monoid of non-empty, finite subsets of $\mathbf N$ withcontaining $0 \in \mathbf N$$0$ equipped with the 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, as usual, with the symbol "$+$".

We refer to a set $A \in \mathcal P_{{\rm fin},0}(\mathbf N)$ as an atom if (i) $A \ne \{0\}$ and (ii) $A \ne X+Y$ for all $X, Y \in \mathcal P_{{\rm fin},0}(\mathbf N) \setminus \bigl\{\{0\}\bigr\}$: Note that $\{0\}$ is the identity (and, in fact, the only unit) of $\mathcal P_{{\rm fin},0}(\mathbf N)$, so this is nothing but a special instance of the abstract notion of atom (or irreducible element) for an arbitrary monoid.

With this in mind, fix $X \in \mathcal P_{{\rm fin},0}(\mathbf N)$. We take ${\sf L}(X) := \{0\}$ if $X = \{0\}$; otherwise, ${\sf L}(X)$ is the set of all $k \in \mathbf N^+$ for which there exist atoms $A_1, \ldots, A_k \in \mathcal P_{{\rm fin},0}(\mathbf N)$ such that $X = A_1 + \cdots + A_k$: In factorization theory, ${\sf L}(X)$ would be called the set of lengths of $X$ (relative to the atoms of $\mathcal P_{{\rm fin},0}(\mathbf N)$), which explains the title.

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

Of course, it's enough to show that the answer is yes in the special case when $X$ is an atom, though I'm not so sure that this makes things any easier. What is perhaps more interesting is that a positive answer is equivalent to showing that there exists $n \in \mathbf N^+$ such that $|\mathsf L(nX)| \ge 2$: This comes as a consequence of a general, simple fact about sets of lengths in factorization theory.

Edit 1. It's probably worth mentioning that $\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)$.

Edit 2. To be completely open, I believe that something much stronger is true: That the limit of $\frac{1}{n} |{\sf L}(nX)|$ as $n \to \infty$ is positive (if not even equal to $\infty$) for every non-zero $X \in \mathcal P_{{\rm fin},0}(\mathbf N)$, where the existence of the limit follows from Fekete's lemma, the general property of sets of lengths alluded to in the above, and the basic fact that $|A+B| \ge |A| + |B|-1$ for all non-empty $A, B \subseteq \mathbf Z$.

Edit 3. With reference to Edit 2, let me note that the limit $\frac{1}{n} |{\sf L}(nX)|$ as $n \to \infty$ need not be infinite (and, on a second thought, it sounds much more plausible that it's always finite). Indeed, consider the case when $X = [\![0, m]\!]$ for some $m \in \mathbf N^+$. Then $nX = [\![0, mn]\!]$ for all $n \in \mathbf N^+$, and hence $\frac{1}{n} |{\sf L}(nX)| \to m$ as $n \to \infty$, since it can be proved (this is not for free) that ${\sf L}([\![0, k]\!]) = [\![2,k]\!]$ for every integer $k \ge 2$.

Edit 4. Yes, of course: The limit in Edit 2 is always 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$.

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

Let $\mathcal P_{{\rm fin},0}(\mathbf N)$ be the monoid of non-empty, finite subsets of $\mathbf N$ with $0 \in \mathbf N$ equipped with the 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, as usual, with the symbol "$+$".

We refer to a set $A \in \mathcal P_{{\rm fin},0}(\mathbf N)$ as an atom if (i) $A \ne \{0\}$ and (ii) $A \ne X+Y$ for all $X, Y \in \mathcal P_{{\rm fin},0}(\mathbf N) \setminus \bigl\{\{0\}\bigr\}$: Note that $\{0\}$ is the identity (and, in fact, the only unit) of $\mathcal P_{{\rm fin},0}(\mathbf N)$, so this is nothing but a special instance of the abstract notion of atom (or irreducible element) for an arbitrary monoid.

With this in mind, fix $X \in \mathcal P_{{\rm fin},0}(\mathbf N)$. We take ${\sf L}(X) := \{0\}$ if $X = \{0\}$; otherwise, ${\sf L}(X)$ is the set of all $k \in \mathbf N^+$ for which there exist atoms $A_1, \ldots, A_k \in \mathcal P_{{\rm fin},0}(\mathbf N)$ such that $X = A_1 + \cdots + A_k$: In factorization theory, ${\sf L}(X)$ would be called the set of lengths of $X$ (relative to the atoms of $\mathcal P_{{\rm fin},0}(\mathbf N)$), which explains the title.

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

Of course, it's enough to show that the answer is yes in the special case when $X$ is an atom, though I'm not so sure that this makes things any easier. What is perhaps more interesting is that a positive answer is equivalent to showing that there exists $n \in \mathbf N^+$ such that $|\mathsf L(nX)| \ge 2$: This comes as a consequence of a general, simple fact about sets of lengths in factorization theory.

Edit 1. It's probably worth mentioning that $\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)$.

Edit 2. To be completely open, I believe that something much stronger is true: That the limit of $\frac{1}{n} |{\sf L}(nX)|$ as $n \to \infty$ is positive (if not even equal to $\infty$) for every non-zero $X \in \mathcal P_{{\rm fin},0}(\mathbf N)$, where the existence of the limit follows from Fekete's lemma, the general property of sets of lengths alluded to in the above, and the basic fact that $|A+B| \ge |A| + |B|-1$ for all non-empty $A, B \subseteq \mathbf Z$.

Edit 3. With reference to Edit 2, let me note that the limit $\frac{1}{n} |{\sf L}(nX)|$ as $n \to \infty$ need not be infinite (and, on a second thought, it sounds much more plausible that it's always finite). Indeed, consider the case when $X = [\![0, m]\!]$ for some $m \in \mathbf N^+$. Then $nX = [\![0, mn]\!]$ for all $n \in \mathbf N^+$, and hence $\frac{1}{n} |{\sf L}(nX)| \to m$ as $n \to \infty$, since it can be proved (this is not for free) that ${\sf L}([\![0, k]\!]) = [\![2,k]\!]$ for every integer $k \ge 2$.

Edit 4. Yes, of course: The limit in Edit 2 is always 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$.

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 $\mathcal P_{{\rm fin},0}(\mathbf N)$ be the monoid of non-empty, finite subsets of $\mathbf N$ containing $0$ equipped with the 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, as usual, with the symbol "$+$".

We refer to a set $A \in \mathcal P_{{\rm fin},0}(\mathbf N)$ as an atom if (i) $A \ne \{0\}$ and (ii) $A \ne X+Y$ for all $X, Y \in \mathcal P_{{\rm fin},0}(\mathbf N) \setminus \bigl\{\{0\}\bigr\}$: Note that $\{0\}$ is the identity (and, in fact, the only unit) of $\mathcal P_{{\rm fin},0}(\mathbf N)$, so this is nothing but a special instance of the abstract notion of atom (or irreducible element) for an arbitrary monoid.

With this in mind, fix $X \in \mathcal P_{{\rm fin},0}(\mathbf N)$. We take ${\sf L}(X) := \{0\}$ if $X = \{0\}$; otherwise, ${\sf L}(X)$ is the set of all $k \in \mathbf N^+$ for which there exist atoms $A_1, \ldots, A_k \in \mathcal P_{{\rm fin},0}(\mathbf N)$ such that $X = A_1 + \cdots + A_k$: In factorization theory, ${\sf L}(X)$ would be called the set of lengths of $X$ (relative to the atoms of $\mathcal P_{{\rm fin},0}(\mathbf N)$), which explains the title.

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

Of course, it's enough to show that the answer is yes in the special case when $X$ is an atom, though I'm not so sure that this makes things any easier. What is perhaps more interesting is that a positive answer is equivalent to showing that there exists $n \in \mathbf N^+$ such that $|\mathsf L(nX)| \ge 2$: This comes as a consequence of a general, simple fact about sets of lengths in factorization theory.

Edit 1. It's probably worth mentioning that $\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)$.

Edit 2. To be completely open, I believe that something much stronger is true: That the limit of $\frac{1}{n} |{\sf L}(nX)|$ as $n \to \infty$ is positive (if not even equal to $\infty$) for every non-zero $X \in \mathcal P_{{\rm fin},0}(\mathbf N)$, where the existence of the limit follows from Fekete's lemma, the general property of sets of lengths alluded to in the above, and the basic fact that $|A+B| \ge |A| + |B|-1$ for all non-empty $A, B \subseteq \mathbf Z$.

Edit 3. With reference to Edit 2, let me note that the limit $\frac{1}{n} |{\sf L}(nX)|$ as $n \to \infty$ need not be infinite (and, on a second thought, it sounds much more plausible that it's always finite). Indeed, consider the case when $X = [\![0, m]\!]$ for some $m \in \mathbf N^+$. Then $nX = [\![0, mn]\!]$ for all $n \in \mathbf N^+$, and hence $\frac{1}{n} |{\sf L}(nX)| \to m$ as $n \to \infty$, since it can be proved (this is not for free) that ${\sf L}([\![0, k]\!]) = [\![2,k]\!]$ for every integer $k \ge 2$.

Edit 4. Yes, of course: The limit in Edit 2 is always 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$.

fixed some details
Source Link
Salvo Tringali
  • 10.5k
  • 2
  • 29
  • 64
Loading
fixed a typo
Source Link
Salvo Tringali
  • 10.5k
  • 2
  • 29
  • 64
Loading
added a further remark concerning the limit in Edit 2
Source Link
Salvo Tringali
  • 10.5k
  • 2
  • 29
  • 64
Loading
added a remark concerning Edit 2
Source Link
Salvo Tringali
  • 10.5k
  • 2
  • 29
  • 64
Loading
added a link
Source Link
Salvo Tringali
  • 10.5k
  • 2
  • 29
  • 64
Loading
added 22 characters in body
Source Link
Salvo Tringali
  • 10.5k
  • 2
  • 29
  • 64
Loading
added 22 characters in body
Source Link
Salvo Tringali
  • 10.5k
  • 2
  • 29
  • 64
Loading
Source Link
Salvo Tringali
  • 10.5k
  • 2
  • 29
  • 64
Loading