Return to Question

I'm looking for a reference to the following elementary result (or to a generalization of it).

Lemma. Let $(H, +, \preceq)$ be an (additive) partially ordered commutative monoid such that $$x+z \prec y+z\quad \text{for all }\ x, y, z \in H \ \text{ with }\ x \prec y, $$ and let $x_1, \ldots, x_n \in H^+$ and $\kappa_1, \ldots, \kappa_n \in \mathbf N$ such that $\kappa_1 x_1 + \cdots + \kappa_i x_i \prec x_{i+1}$ for every $i \in [\![1, n-1]\!]$, under the assumption that $H^+ := \{x \in H: 0_H \prec x\} \ne \emptyset$. If $y$ is an element in the sumset $\kappa_1 \{0_H, x_1\} + \cdots + \kappa_n\{0_H, x_n\}$, then there is uniquely determined an $n$-tuple $(a_1, \ldots, a_n) \in [\![0, \kappa_1]\!] \times \cdots \times [\![0, \kappa_n]\!]$ for which $y = \sum_{i = 1}^n a_i x_i$.

Any pointer? The result popped up in the study of some arithmetic invariants (namely, set of distances and set of catenary degrees) of a certain class of non-cancellative BF-monoids.

For the special case when the monoid under consideration is $(\mathbf N, +)$, I thought I would have found something along the same lines in the literature on the knapsack problem or the subset sum problem, but I couldn't get to anything and resolved to ask here (after having first tried at MSE).

Incidentally, the lemma provides, by a simple counting argument, another proof of the existence and uniqueness of the base-$b$ representation of a non-negative integer (for any given base $b \ge 2$).

I'm looking for a reference to the following elementary result (or to a generalization of it).

Lemma. Let $(H, +, \preceq)$ be an (additive) partially ordered commutative monoid such that $$x+z \prec y+z\quad \text{for all }\ x, y, z \in H \ \text{ with }\ x \prec y, $$ and let $x_1, \ldots, x_n \in H^+$ and $\kappa_1, \ldots, \kappa_n \in \mathbf N$ such that $\kappa_1 x_1 + \cdots + \kappa_i x_i \prec x_{i+1}$ for every $i \in [\![1, n-1]\!]$, under the assumption that $H^+ := \{x \in H: 0_H \prec x\} \ne \emptyset$. If $y$ is an element in the sumset $\kappa_1 \{0_H, x_1\} + \cdots + \kappa_n\{0_H, x_n\}$, then there is uniquely determined an $n$-tuple $(a_1, \ldots, a_n) \in [\![0, \kappa_1]\!] \times \cdots \times [\![0, \kappa_n]\!]$ for which $y = \sum_{i = 1}^n a_i x_i$.

Any pointer? The result popped up in the study of some arithmetic invariants (namely, set of distances and set of catenary degrees) of a certain class of non-cancellative BF-monoids.

For the special case when the monoid under consideration is $(\mathbf N, +)$, I thought I would have found something along the same lines in the literature on the knapsack problem or the subset sum problem, but I couldn't get to anything and resolved to ask here (after having first tried at MSE).

Incidentally, the lemma provides, by a simple counting argument, another proof of the existence and uniqueness of the base-$b$ representation of a non-negative integer (for any given base $b \ge 2$).

I'm looking for a reference to the following elementary result (or to a generalization of it).

Lemma. Let $(H, +, \preceq)$ be an (additive) partially ordered commutative monoid, and let $x_1, \ldots, x_n \in H^+$ and $\kappa_1, \ldots, \kappa_n \in \mathbf N$ such that $\kappa_1 x_1 + \cdots + \kappa_i x_i \prec x_{i+1}$ for every $i \in [\![1, n-1]\!]$, under the assumption that $H^+ := \{x \in H: 0_H \prec x\} \ne \emptyset$. If $y$ is an element in the sumset $\kappa_1 \{0_H, x_1\} + \cdots + \kappa_n\{0_H, x_n\}$, then there is uniquely determined an $n$-tuple $(a_1, \ldots, a_n) \in [\![0, \kappa_1]\!] \times \cdots \times [\![0, \kappa_n]\!]$ for which $y = \sum_{i = 1}^n a_i x_i$.

Any pointer? The result popped up in the study of some arithmetic invariants (namely, set of distances and set of catenary degrees) of a certain class of non-cancellative BF-monoids.

For the special case when the monoid under consideration is $(\mathbf N, +)$, I thought I would have found something along the same lines in the literature on the knapsack problem or the subset sum problem, but I couldn't get to anything and resolved to ask here (after having first tried at MSE).

Incidentally, the lemma provides, by a simple counting argument, another proof of the existence and uniqueness of the base-$b$ representation of a non-negative integer (for any given base $b \ge 2$).

I'm looking for a reference to the following elementary result (or to a generalization of it).

Lemma. Let $(H, +, \preceq)$ be an (additive) partially ordered commutative monoid such that $$x+z \prec y+z\quad \text{for all }\ x, y, z \in H \ \text{ with }\ x \prec y, $$ and let $x_1, \ldots, x_n \in H^+$ and $\kappa_1, \ldots, \kappa_n \in \mathbf N$ such that $\kappa_1 x_1 + \cdots + \kappa_i x_i \prec x_{i+1}$ for every $i \in [\![1, n-1]\!]$, under the assumption that $H^+ := \{x \in H: 0_H \prec x\} \ne \emptyset$. If $y$ is an element in the sumset $\kappa_1 \{0_H, x_1\} + \cdots + \kappa_n\{0_H, x_n\}$, then there is uniquely determined an $n$-tuple $(a_1, \ldots, a_n) \in [\![0, \kappa_1]\!] \times \cdots \times [\![0, \kappa_n]\!]$ for which $y = \sum_{i = 1}^n a_i x_i$.

Any pointer? The result popped up in the study of some arithmetic invariants (namely, set of distances and set of catenary degrees) of a certain class of non-cancellative BF-monoids.

For the special case when the monoid under consideration is $(\mathbf N, +)$, I thought I would have found something along the same lines in the literature on the knapsack problem or the subset sum problem, but I couldn't get to anything and resolved to ask here (after having first tried at MSE).

Incidentally, the lemma provides, by a simple counting argument, another proof of the existence and uniqueness of the base-$b$ representation of a non-negative integer (for any given base $b \ge 2$).

I'm looking for a reference to the following elementary result (or to a generalization of it), where for $X \subseteq \mathbf R$ and $\kappa \in \mathbf N^+$ we let $\kappa X := \{x_1 + \cdots + x_\kappa: x_1, \ldots, x_\kappa \in X\}$.

Lemma. Let $x_1, \ldots, x_n \in \mathbf R^+$ and $\kappa_1, \ldots, \kappa_n \in \mathbf N^+$ such that $\kappa_1 x_1 + \cdots + \kappa_i x_i < x_{i+1}$ for every $i \in [\![1, n-1]\!]$, and let $y$ be an element in the sumset $\kappa_1 \{0, x_1\} + \cdots + \kappa_n\{0, x_n\}$. Then there is uniquely determined an $n$-tuple $(a_1, \ldots, a_n) \in [\![0, \kappa_1]\!] \times \cdots \times [\![0, \kappa_n]\!]$ for which $y = \sum_{i = 1}^n a_i x_i$.

Any pointer? The result popped up in the study of some arithmetic invariants (namely, set of distances and set of catenary degrees) of a certain class of non-cancellative BF-monoids. For some reason, I thought I would have found something along the same lines in the literature on the knapsack problem or the subset sum problem, but I couldn't get to anything and resolved to ask here (after having first tried at MSE).

Incidentally, the lemma provides, by a simple counting argument, another proof of the existence and uniqueness of the base-$b$ representation of a non-negative integer (for any given base $b \ge 2$), and for what it's worth, it carries over in a natural way to partially ordered commutative monoids.

I'm looking for a reference to the following elementary result (or to a generalization of it).

Lemma. Let $(H, +, \preceq)$ be an (additive) partially ordered commutative monoid, and let $x_1, \ldots, x_n \in H^+$ and $\kappa_1, \ldots, \kappa_n \in \mathbf N$ such that $\kappa_1 x_1 + \cdots + \kappa_i x_i \prec x_{i+1}$ for every $i \in [\![1, n-1]\!]$, under the assumption that $H^+ := \{x \in H: 0_H \prec x\} \ne \emptyset$. If $y$ is an element in the sumset $\kappa_1 \{0_H, x_1\} + \cdots + \kappa_n\{0_H, x_n\}$, then there is uniquely determined an $n$-tuple $(a_1, \ldots, a_n) \in [\![0, \kappa_1]\!] \times \cdots \times [\![0, \kappa_n]\!]$ for which $y = \sum_{i = 1}^n a_i x_i$.

Any pointer? The result popped up in the study of some arithmetic invariants (namely, set of distances and set of catenary degrees) of a certain class of non-cancellative BF-monoids. 

For the special case when the monoid under consideration is $(\mathbf N, +)$, I thought I would have found something along the same lines in the literature on the knapsack problem or the subset sum problem, but I couldn't get to anything and resolved to ask here (after having first tried at MSE).

Incidentally, the lemma provides, by a simple counting argument, another proof of the existence and uniqueness of the base-$b$ representation of a non-negative integer (for any given base $b \ge 2$).