The smallest sets of points not determined by their X-rays

Abstract

Let $F$ be an $n$-point set in ${\mathbb{K}}^d$ with $\mathbb{K}\in \{\mathbb{R},\mathbb{Z}\}$ and $d\ge 2$. A (discrete) X-ray of $F$ in direction $s$ gives the number of points of $F$ on each line parallel to $s$. We define ${\psi }_{{\mathbb{K}}^d}(m)$ as the minimum number $n$ for which there exist $m$ directions $s_1,...,s_m$ (pairwise linearly independent and spanning ${\mathbb{R}}^d$) such that two $n$-point sets in ${\mathbb{K}}^d$ exist that have the same X-rays in these directions. The bound ${\psi }_{{\mathbb{Z}}^d}(m)\le 2^{m-1}$ has been observed many times in the literature. In this note we show ${\psi }_{{\mathbb{K}}^d}(m)=O(m^{d+1+\epsilon })$ for $\epsilon >0$. For the cases ${\mathbb{K}}^d={\mathbb{Z}}^d$ and ${\mathbb{K}}^d={\mathbb{R}}^d$, $d>2$, this represents the first upper bound on ${\psi }_{{\mathbb{K}}^d}(m)$ that is polynomial in $m$. As a corollary we derive bounds on the sizes of solutions to both the classical and two-dimensional Prouhet-Tarry-Escott problem. Additionally, we establish lower bounds on ${\psi }_{{\mathbb{K}}^d}$ that enable us to prove a strengthened version of Rényi's theorem for points in ${\mathbb{Z}}^2$.