Abstract
This paper considers an extremal version of the Erdős distinct distances problem. For a point set \(P \subset {\mathbb {R}}^d\), let \(\Delta (P)\) denote the set of all Euclidean distances determined by P. Our main result is the following: if \(\Delta (A^d) \ll |A|^2\) and \(d \ge 5\), then there exists \(A' \subset A\) with \(|A'| \ge |A|/2\) such that \(|A'-A'| \ll |A| \log |A|\). This is one part of a more general result, which says that, if the growth of \(|\Delta (A^d)|\) is restricted, it must be the case that A has some additive structure. More specifically, for any two integers k, n, we have the following information: if
then there exists \(A' \subset A\) with \(|A'| \ge |A|/2\) and
These results are higher dimensional analogues of a result of Hanson [4], who considered the two-dimensional case.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
Henceforth, all sets introduced are assumed to be finite.
The theorem of Sanders implies the existences of a convex coset progression which can be extended to a GAP with negligible losses using a John-type theorem of Tao and Vu [12].
References
Bradshaw, P.J.: Growth in sumsets of higher convex functions. Combinatorica 43(4), 769–789 (2023)
Erdős, P.: On some metric and combinatorial geometric problems. Discrete Math. 60, 147–153 (1986)
Guth, L., Katz, N.H.: On the Erdős distinct distance problem in the plane. Ann. Math. 181(1), 155–190 (2015)
Hanson, B.: The additive structure of Cartesian products spanning few distinct distances. Combinatorica 38(5), 1095–1100 (2018)
Hanson, B., Roche-Newton, O., Rudnev, M.: Higher convexity and iterated sum sets. Combinatorica 42(1), 71–85 (2022)
Hanson, B., Roche-Newton, O., Senger, S.: Convexity, superquadratic growth, and dot products. J. Lond. Math. Soc. 107(5), 1900–1923 (2023)
Mudgal, A.: Energy estimates in sum-product and convexity problems. arXiv:2109.04932
Pohoata, C.: On Cartesian products which determine few distinct distances. Electron. J. Combin. 26(1), 1.7, 7 (2019)
Ruzsa, I.Z., Shakan, G., Solymosi, J., Szemerédi, E.: ‘On distinct consecutive differences’, Combinatorial and additive number theory IV 425-434, Springer Proceedings in Mathematics Statistics, 347, Springer, Cham (2021)
Sanders, T.: The structure theory of set addition revisited. Bull. Am. Math. Soc (N. S.) 50(1), 93–127 (2013)
Solymosi, J., Vu, V.: Near optimal bounds for the Erdős distinct distances problem in high dimensions. Combinatorica 28(1), 113–125 (2008)
Tao, T., Vu, V.: John-type theorems for generalized arithmetic progressions and iterated sumsets. Adv. Math. 219, 428–449 (2018)
Acknowledgements
Oliver Roche-Newton, Dmitrii Zhelezov were supported by the Austrian Science Fund FWF Project P 34180. We are grateful to Brandon Hanson and Audie Warren for several helpful conversations concerning the content of this paper. We also thank the anonymous referee for some helpful suggestions.
Author information
Authors and Affiliations
Corresponding author
Additional information
Editor in Charge: János Pach
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Roche-Newton, O., Zhelezov, D. Convexity, Elementary Methods, and Distances. Discrete Comput Geom (2024). https://doi.org/10.1007/s00454-023-00625-7
Received:
Revised:
Accepted:
Published:
DOI: https://doi.org/10.1007/s00454-023-00625-7