The Smallest Sets of Points not Determined by Their X-rays

Let F be an n-point set in Kd with K∈{R,Z} and d≥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 ψKd(m) as the minimum number n for which there exist m directions s1,...,sm (pairwise linearly independent and spanning Rd) such that two n-point sets in Kd exist that have the same X-rays in these directions. The bound ψZd(m)≤2m−1 has been observed many times in the literature. In this note we show ψKd(m)=O(md+1+ε) for ε>0. For the cases Kd=Zd and Kd=Rd, d>2, this represents the first upper bound on ψKd(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 ψKd that enable us to prove a strengthened version of R\'enyi's theorem for points in Z2.     «

Let F be an n-point set in Kd with K∈{R,Z} and d≥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 ψKd(m) as the minimum number n for which there exist m directions s1,...,sm (pairwise linearly independent and spanning Rd) such that two n-point sets in Kd exist that have the same X-rays in these directions. The bound ψZd(m)≤2m−1 has been observed many times in the literature. In this note we show ψKd(m)=O(md+1+ε) for ε>0. For the case...     »