Improved Upper Bound for Lindström's Unique-Sum Problem

Abstract

Let $\{0,1{\}}^n$ denote the set of all $n$-dimensional vectors whose components are either $0$ or $1$. For any two nonempty subsets $\mathcal{X},\mathcal{Y}\subseteq \{0,1{\}}^n$, the pair $(\mathcal{X},\mathcal{Y})$ is called an $n$-dimensional unique-sum pair if each pair $(\mathbf{x},\mathbf{y})\in \mathcal{X}\times \mathcal{Y}$ can be uniquely determined from the arithmetic sum $\mathbf{x}+\mathbf{y}$. Let $M(n)$ denote the maximum value of $|\mathcal{X}||\mathcal{Y}|$ over all $n$-dimensional unique-sum pairs $(\mathcal{X},\mathcal{Y})$. In 1969, Lindström proved that $$\frac{1}{2}(1+{\log }_{2}3)\le \underset{n\to \infty }{\lim }\frac{1}{n}{\log }_{2}M(n)\le 3/2.$$ Since then, the lower bound $(1+{\log }_{2}3)/2$ has been successively improved, whereas the upper bound $3/2$ has remained unchanged. In this paper, we establish an explicit upper bound whose numerical value is approximately $1.4884$. To the best of our knowledge, this is the first strict improvement over Lindström's upper bound $3/2$. Towards this end, we develop a coordinate projection approach that constructs a lower-dimensional unique-sum system from a unique-sum pair. By combining the results obtained from this approach with a relaxed form of a necessary condition established by Ordentlich and Shayevitz on unique-sum systems, we establish the above improved upper bound.