Let $F$ be an $n$-point set in $\mathbb{ K}^d$ with $\mathbb{ K}\in\{ \mathbb{ R},\mathbb{ Z}\}$ and $d\geq 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)\leq 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+\varepsilon})$ for $\varepsilon>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\'enyi's theorem for points in $\mathbb{ Z}^2$.
Categories: math.MG math.CO