2
$\begingroup$

Edit (Jan 17, 2016): Now crossposted at MO.

I'm looking for a reference to the following elementary results (or to generalizations of them):

Lemma 1. Let $x_1, \ldots, x_n$ be positive real numbers such that $x_1 + \cdots + x_i < x_{i+1}$ for every $i \in [\![1, n-1]\!]$, and let $y$ be an element in the sumset $\{0, x_1\} + \cdots + \{0, x_n\}$. Then there is a unique set $I \subseteq [\![1, n]\!]$ for which $y = \sum_{i \in I} x_i$.

Any pointer? 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.

The result has the following straightforward extension, 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 2. 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 a unique $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$.

The second lemma provides, by a simple counting argument, an alternative 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 mean alternative to the usual one, based on induction and Euclidean division.

$\endgroup$
2
  • 2
    $\begingroup$ When I reach a notation that I don't know, I can't continue reading. (Some people can.) What is " the sumset $\{0,x_1\}+...+\{0,x_n\}$" ? $\endgroup$ Commented Jan 15, 2017 at 15:39
  • $\begingroup$ Added a link to the definition of "sumset" on Wikipedia. $\endgroup$ Commented Jan 15, 2017 at 19:36

0

You must log in to answer this question.

Browse other questions tagged .