Abstract
We study configurations of n points and n lines that form \(\Theta (n^{4/3})\) incidences, when the point set is a Cartesian product. We prove structural properties of such configurations, such that there exist many families of parallel lines or many families of concurrent lines. We show that the line slopes have multiplicative structure or that many sets of y-intercepts have additive structure. We introduce the first infinite family of configurations with \(\Theta (n^{4/3})\) incidences. We also derive a new variant of a different structural point–line result of Elekes. Our techniques are based on the concept of line energy. Recently, Rudnev and Shkredov introduced this energy and showed how it is connected to point–line incidences. We also prove that their bound is tight up to sub-polynomial factors.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ackerman, E.: On topological graphs with at most four crossings per edge. Comput. Geom. 85, # 101574 (2019)
Bombieri, E., Bourgain, J.: A problem on sums of two squares. Int. Math. Res. Not. 2015(11), 3343–3407 (2015)
Bourgain, J., Demeter, C.: New bounds for the discrete Fourier restriction to the sphere in 4D and 5D. Int. Math. Res. Not. 2015(11), 3150–3184 (2015)
Chernikov, A., Galvin, D., Starchenko, S.: Cutting lemma and Zarankiewicz’s problem in distal structures. Selecta Math. (N.S.) 26(2), # 25 (2020)
Elekes, Gy.: On linear combinatorics I. Concurrency—an algebraic approach. Combinatorica 17(4), 447–458 (1997)
Elekes, Gy.: On linear combinatorics II. Structure theorems via additive number theory. Combinatorica 18(1), 13–25 (1998)
Elekes, Gy.: On linear combinatorics III. Few directions and distorted lattices. Combinatorica 19(1), 43–53 (1999)
Elekes, Gy.: SUMS versus PRODUCTS in number theory, algebra and Erdős geometry. In: Paul Erdős and His Mathematics, vol. 2. Bolyai Society Mathematical Studies, vol. 11, pp. 241–290. Springer, Berlin (2002)
Erdős, P.: Problems and results in combinatorial geometry. In: Discrete Geometry and Convexity. Annals of the New York Academy of Sciences, vol. 440, pp. 1–11. New York Academy of Sciences, New York (1985)
Green, B., Tao, T.: On sets defining few ordinary lines. Discrete Comput. Geom. 50(2), 409–468 (2013)
Guth, L., Silier, O.: Structural Szemerédi–Trotter for non-lattices. (in preparation)
Hanson, B., Roche-Newton, O., Zhelezov, D.: On iterated product sets with shifts, II. Algebra Number Theory 14(8), 2239–2260 (2020)
Hardy, G.H., Wright, E.M.: An Introduction to the Theory of Numbers. Oxford University Press, New York (1979)
Katz, N.H., Zahl, J.: An improved bound on the Hausdorff dimension of Besicovitch sets in \(\mathbb{R} ^3\). J. Am. Math. Soc. 32(1), 195–259 (2019)
Mirzaei, M., Suk, A.: On grids in point-line arrangements in the plane. Discrete Comput. Geom. 65(4), 1232–1243 (2021)
Petridis, G., Roche-Newton, O., Rudnev, M., Warren, A.: An energy bound in the affine group. Int. Math. Res. Not. 2022(2), 1154–1172 (2022)
Rudnev, M., Shkredov, I.D.: On growth rate in \({\rm SL}_2(F_p)\), the affine group and sum-product type implications (2018). arXiv:1812.01671
Sheffer, A.: Distinct distances: open problems and current bounds (2014). arXiv:1406.1949
Sheffer, A.: Incidences: Lower bounds (Part 1) (2016). https://adamsheffer.wordpress.com/2014/06/04/incidences-lower-bounds-part-1/
Shen, J.: Structural Szemerédi–Trotter for lattices and semi-lattices. (in preparation)
Shteinikov, Yu.N.: On the product sets of rational numbers. Proc. Steklov Inst. Math. 296(1), 243–250 (2017)
Singer, N., Sudan, M.: Point-hyperplane incidence geometry and the log-rank conjecture. ACM Trans. Comput. Theory 14(2), # 7 (2022)
Solymosi, J.: Dense arrangements are locally very dense. I. SIAM J. Discrete Math. 20(3), 623–627 (2006)
Szemerédi, E., Trotter, W.T., Jr.: Extremal problems in discrete geometry. Combinatorica 3(3–4), 381–392 (1983)
Acknowledgements
The authors thank Misha Rudnev, Junxuan Shen, Ilya Shkredov, and Audie Warren for helpful conversations. We also thank Chi Hoi Yip and the anonymous referees for spotting issues and helping to improve this work.
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.
This research project was done as part of the 2020 NYC Discrete Math REU, supported by NSF awards DMS-1802059, DMS-1851420, DMS-1953141, and DMS-2028892. A.S. supported by NSF award DMS-1802059 and by PSCCUNY award 63580. O.S. supported by the Lynn A. Booth and Kent Kresa SURF Fellowship.
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
Sheffer, A., Silier, O. A Structural Szemerédi–Trotter Theorem for Cartesian Products. Discrete Comput Geom 71, 646–666 (2024). https://doi.org/10.1007/s00454-023-00555-4
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-023-00555-4