A short proof for Open Problem 4 on unique multiset sums

This note concerns Open Problem 4 in Minimum modulus for the unique multiset-sum problem.

Let n >= 2, let G be a finite abelian group, and let g_0,...,g_(n-1) be elements of G. Say that these elements have unique multiset sums if every nonnegative integer vector k=(k_0,...,k_(n-1)) satisfying

sum_(i=0)^(n-1) k_i = n,
sum_(i=0)^(n-1) k_i g_i = sum_(i=0)^(n-1) g_i

must satisfy k_0=...=k_(n-1)=1. Let mu(n) be the least possible order of such a group.

Theorem

mu(n) = 2^(n-1)   for every n >= 2.

Lower bound

Suppose g_0,...,g_(n-1) in G have unique multiset sums, and put h_i=g_i-g_0 for 1 <= i <= n-1. Consider the subset-sum map

Phi(S) = sum_(i in S) h_i,   S subset {1,...,n-1}.

Assume that Phi(S)=Phi(T) for distinct subsets S,T. For 1 <= i <= n-1 put x_i=1_S(i)-1_T(i). After exchanging S and T if necessary, assume that

r := sum_(i=1)^(n-1) x_i >= 0.

The subset-sum collision gives

sum_(i=1)^(n-1) x_i(g_i-g_0)=0,
so  sum_(i=1)^(n-1) x_i g_i = r g_0.

Define a new multiplicity vector by

k_0=1+r,   k_i=1-x_i  (1 <= i <= n-1).

Since x_i is in {-1,0,1} and r >= 0, all k_i are nonnegative integers. Moreover,

sum_(i=0)^(n-1) k_i
= 1+r + sum_(i=1)^(n-1)(1-x_i)
= n,

and

sum_(i=0)^(n-1) (k_i-1)g_i
= r g_0 - sum_(i=1)^(n-1) x_i g_i
= 0.

Thus k is a size-n multiset with the same sum as the all-ones multiset. Since S and T are distinct, some x_i is nonzero, so k is not the all-ones vector. This contradicts uniqueness.

Therefore Phi is injective; equivalently, {h_1,...,h_(n-1)} is dissociated. Its domain has 2^(n-1) elements, so

|G| >= 2^(n-1).

Upper bound

Take

G = (Z/2Z)^(n-1),   g_0=0,   g_i=e_i  (1 <= i <= n-1),

where e_1,...,e_(n-1) are the standard basis vectors. If a nonnegative multiplicity vector k has total size n and the target group sum, then comparison in coordinate i gives

k_i = 1 (mod 2)   for 1 <= i <= n-1.

Hence every k_i with i >= 1 is a positive odd integer. If any of them exceeded 1, it would be at least 3, giving

sum_(i=1)^(n-1) k_i >= (n-2)+3 = n+1,

contrary to sum_i k_i=n. Therefore k_1=...=k_(n-1)=1, and then k_0=1. This family has unique multiset sums and |G|=2^(n-1). Together with the lower bound, this proves the theorem.

Status note. The cited preprint states the general finite-abelian-group question as open in version 2. The argument above is self-contained but unreviewed. This page is not a substitute for independent expert review, and no claim of priority is made. Corrections or counterexamples are welcome.