Technical Summary: On Possible Sums from Multiset of Mutually Divisible Natural Numbers

Problem Statement

The paper addresses the structural characterization of the set of possible sums, denoted as $\text{span}(A)$, generated by a finite multiset $A$ of positive integers. Specifically, the study restricts its scope to multisets where the elements form a "divisible chain." That is, for any two elements $a_i, a_j \in A$, either $a_i$ divides $a_j$ or $a_j$ divides $a_i$.

The elements of such a multiset can be represented in the form $d_0, d_0d_1, \dots, d_0d_1\cdots d_k$, where $d_0=1$ and $d_i > 1$ for $i > 0$. Let $p_i = d_0d_1\cdots d_i$. The multiset $A$ is represented as a tuple $(a_0, a_1, \dots, a_k)$, where $a_i$ denotes the multiplicity of the token with cost $p_i$. The set $\text{span}(A)$ consists of all sums $\sum c_i p_i$ where $0 \le c_i \le a_i$.

The primary objectives are:

1. To describe the structure of $\text{span}(A)$ for these specific multisets.
2. To provide a criterion for determining when two such multisets $A$ and $B$ generate the same set of sums ($\text{span}(A) = \text{span}(B)$).
3. To develop algorithms for deciding sum equivalence and membership ($n \in \text{span}(A)$).

Methodology

The paper employs a combinatorial approach centered on elementary exchanges. An elementary exchange at index $i$ (denoted $e_i$) transforms a multiset by replacing $d_i$ tokens of cost $p_i$ with one token of cost $p_{i+1}$. This operation preserves the total sum of the multiset but alters its composition.

The core methodology involves:

• Normalization: Defining a "proper" elementary exchange as one performed when the multiplicity $a_i > 2(d_i - 1)$. The paper introduces Algorithm 1, which iteratively applies proper elementary exchanges to transform any arbitrary $\{d_i\}$-collection into a normal collection where $a_i \le 2(d_i - 1)$ for all $i$. The algorithm's loop condition explicitly checks while A[i] > 2(d_i - 1), and while the Require clause in the pseudocode mentions $0 \le a_i < d_i$, the algorithm's operational logic and the resulting definition of a normal collection in the text focus on the upper bound $a_i \le 2(d_i - 1)$.
• Decomposition: Analyzing normal collections by identifying "critical indices" (where $a_j < d_j - 1$ or $j$ is the last index). This allows the decomposition of a normal collection into irreducible sub-multisets.
• Inductive Proofs: Using induction on the sum of the multiset and properties of modular arithmetic to establish bounds on the reachable sums and the uniqueness of representations.

Key Contributions and Results

1. Invariance under Proper Exchanges

The paper establishes that if a multiset $A$ satisfies $a_i > 2(d_i - 1)$, then performing an elementary exchange at index $i$ does not change the set of possible sums:
$$\text{span}(A) = \text{span}(e_i(A))$$
This leads to Corollary 2.1, stating that the normalization process (Algorithm 1) preserves the span. Consequently, $\text{span}(A) = \text{span}(\text{norm}(A))$.

2. Characterization of Normal Collections

The paper defines a normal collection as one where $a_i \le 2(d_i - 1)$ for all $i$. It proves that for normal collections, the span uniquely determines the multiset:

• Proposition 3.2: If $A$ and $B$ are normal $\{d_i\}$-collections and $\text{span}(A) = \text{span}(B)$, then $A = B$.
• Theorem 3.2: For arbitrary $\{d_i\}$-collections $A$ and $B$, $\text{span}(A) = \text{span}(B)$ if and only if $\text{norm}(A) = \text{norm}(B)$.

3. Structural Decomposition

For a normal collection $A$, the paper provides a decomposition theorem (Theorem 3.1). If $A$ is decomposed into irreducible sub-multisets $A_1, \dots, A_s$ based on critical indices, the span of $A$ is the direct sum of scaled spans of these components:
$$\text{span}(A) = \bigoplus_{i=1}^s p_{j_{i-1}+1} \cdot \{0, 1, \dots, p_{j_i-1}^{-1}\text{sum}(A_j)\}$$
This structure implies that any element in $\text{span}(A)$ has a unique representation as a sum of elements from the scaled spans of the irreducible components.

4. Algorithms

The paper presents two primary algorithms:

• Normalization Algorithm: Converts any collection to its unique normal form, enabling the decision of span equivalence by simple tuple comparison.
• Membership Algorithm: Implicitly derived from the decomposition, allowing one to decide if a specific integer $n$ belongs to $\text{span}(A)$ by checking its representation against the decomposed structure.

5. Counterexamples and Limits

The paper notes that the converse of the invariance proposition is false; an elementary exchange can preserve the span even if the condition $a_i > 2(d_i - 1)$ is not met (e.g., in specific 2-collections). However, the normalization process guarantees a unique canonical form regardless of the order of operations (Corollary 3.1).

Significance and Claims

The paper claims to provide a complete structural description of the set of sums for multisets of mutually divisible natural numbers. Its primary significance lies in:

1. Canonical Representation: Establishing that every such multiset has a unique "normal" form that preserves its span, effectively solving the equivalence problem for these sets.
2. Algorithmic Decidability: Providing concrete, finite procedures to determine if two collections generate the same set of sums and to check membership for specific values.
3. Generalization: While the problem is framed generally for $\{d_i\}$-collections, the author notes that the logic extends from the simpler case of $d$-collections (powers of a single integer $d$) to the general case.

The work is motivated by connections to integer partitions (citing [AE04]) and offers a rigorous combinatorial framework for understanding token systems with hierarchical divisibility constraints. The author explicitly thanks Professor Fedor Petrov for verifying the proofs, underscoring the paper's focus on mathematical correctness within the domain of combinatorics.