On Erd\H os chains in the plane
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
Let $P$ be a finite point set in $\mathbb{R}^2$ with the set of distance $n$-chains defined as $$ \Delta_n(P)=\{(|p_1-p_2|,|p_2-p_3|,\ldots,|p_n-p_{n+1}|):p_i \in P\}.$$ We show that for $2\leq n=O_{|P|}(1)$ we have $$|\Delta_n(P)|\gtrsim \frac{|P|^{n}}{\log^{\frac{13}{2}(n-1)}|P|}.$$ Our argument uses the energy construction of Elekes and a general version of Rudnev's rich-line bound implicit in \cite{R19}, which allows one to iterate efficiently on intersecting nested subsets of Guth-Katz lines. Let $G$ is a simple connected graph on $m=O(1)$ vertices with $m\geq 2$. Define the graph-distance set $\Delta_G(P)$ as $$ \Delta_G(P) = \{ (|p_{i}-p_{j}|)_{\{i,j\}\in E(G)} : p_i,p_j \in P\}.$$ Combining with results of Guth and Katz \cite{GK15} and Rudnev \cite{R19} with the above, if $G$ has a Hamiltonian path we have $$ |\Delta_G(P)| \gtrsim \frac{|P|^{m-1}}{\text{polylog}|P|}. $$
Abstract
Let $P$ be a finite point set in $\mathbb{R}^2$ with the set of distance $n$-chains defined as $$ \Delta_n(P)=\{(|p_1-p_2|,|p_2-p_3|,\ldots,|p_n-p_{n+1}|):p_i \in P\}.$$ We show that for $2\leq n=O_{|P|}(1)$ we have $$|\Delta_n(P)|\gtrsim \frac{|P|^{n}}{\log^{\frac{13}{2}(n-1)}|P|}.$$ Our argument uses the energy construction of Elekes and a general version of Rudnev's rich-line bound implicit in \cite{R19}, which allows one to iterate efficiently on intersecting nested subsets of Guth-Katz lines. Let $G$ is a simple connected graph on $m=O(1)$ vertices with $m\geq 2$. Define the graph-distance set $\Delta_G(P)$ as $$ \Delta_G(P) = \{ (|p_{i}-p_{j}|)_{\{i,j\}\in E(G)} : p_i,p_j \in P\}.$$ Combining with results of Guth and Katz \cite{GK15} and Rudnev \cite{R19} with the above, if $G$ has a Hamiltonian path we have $$ |\Delta_G(P)| \gtrsim \frac{|P|^{m-1}}{\text{polylog}|P|}. $$
참고문헌 (33)
- M. Bennett, "Finite chains inside thin subsets of Rd", Anal. & PDE, 9(3), pp.597~614 (2016)
- J. Bourgain, "A szemerédi type theorem for sets of positive density in Rk", Israel Journal of Mathematics, 54(3), pp.307~316 (1986), Springer Science and Business Media LLC[DOI]
- BORIS BUKH, "Space Crossing Numbers", Combinatorics, Probability and Computing, 21(3), pp.358~373 (2012), Cambridge University Press (CUP)[DOI]
- Vincent Chan, "Finite configurations in sparse sets", Journal d'Analyse Mathématique, 128(1), pp.289~335 (2016), Springer Science and Business Media LLC[DOI]
- F.R.K Chung, "The number of different distances determined by n points in the plane", Journal of Combinatorial Theory, Series A, 36(3), pp.342~354 (1984), Elsevier BV[DOI]
- F. R. K. Chung, "The number of different distances determined by a set of points in the euclidean plane", Discrete & Computational Geometry, 7(1), pp.1~11 (1992)
- F. de Zeeuw, "A short proof of rudnev’s point-plane incidence bound", arXiv preprint arXiv : 1612. 02719, ~ (2016)
- GYÖRGY ELEKES, "Incidences in Three Dimensions and Distinct Distances in the Plane", Combinatorics, Probability and Computing, 20(4), pp.571~608 (2011), Cambridge University Press (CUP)[DOI]
- P. Erdos, "On Sets of Distances of n Points", The American Mathematical Monthly, 53(5), pp.248~250 (1946), Informa UK Limited[DOI]
- K. J. Falconer, "On the Hausdorff dimensions of distance sets", Mathematika, 32(2), pp.206~212 (1985), Wiley[DOI]
- K. J. Falconer, "Plane Sets with Positive Density at Infinity Contain all Large Distances", Bulletin of the London Mathematical Society, 18(5), pp.471~474 (1986), Wiley[DOI]
- N. Frankl, "Almost sharp bounds on the number of discrete chains in the plane", 36th International Symposium on Computational Geometry (SoCG 2020). Schloss Dagstuhl-Leibniz-Zentrum f¨ur Informatik (2020)
- H. Furstenberg, "Mathematics of Ramsey theory", pp.184~198 (1990), Springer
- J. Garibaldi, "The Erd˝os distance problem" (2011), American Mathematical Society
- L. Guth, "Polynomial methods in combinatorics" (2016), American Mathematical Society
- Larry Guth, "On Falconer’s distance set problem in the plane", Inventiones mathematicae, 219(3), pp.779~830 (2020), Springer Science and Business Media LLC[DOI]
- L. Guth, "On the Erd˝os distinct distances problem in the plane", Ann. of Math, 181(1), pp.155~190 (2015)[DOI]
- A. Iosevich, "Cycles of arbitrary length in distance graphs on Fq", arXiv preprint arXiv : 2101. 00748, ~ (2021)
- Alex Iosevich, "Embedding distance graphs in finite field vector spaces", 대한수학회지, 56(6), pp.1515~1528 (2019), 대한수학회[DOI]
- A. Iosevich, "Finite point configurations in the plane, rigidity and Erd˝os problems", Proc. Steklov Inst. Math, 303(1), pp.129~139 (2018)
- E. Landau, "Uber die Einteilung der positiven ganzen Zahlen in vier Klassen nach der ¨Mindestzahl der zu ihrer additiven Zusammensetzung erforderlichen Quadrate", ~ (1909)
- N. Lyall, "Distance graphs and sets of positive upper density in Rd", Anal. & PDE, 13(3), pp.685~700 (2020)
- P. Moree, "On a claim of Ramanujan in his first letter to Hardy", Exposition. Math, 17(4), pp.289~311 (1999)
- L. Moser, "On the different distances determined by n points", Amer. Math. Monthly, 59, pp.85~91 (1952)[DOI]
- Y. Ou, "Finite point configurations and the regular value theorem in a fractal setting", arXiv preprint arXiv : 2005. 12233, ~ (2020)
- E. A. Palsson, "On the number of discrete chains", arXiv preprint arXiv : 1902. 08259, ~ (2019)
- M. Rudnev, "On the number of classes of triangles determined by n points in R2", arXiv preprint arXiv : 1205. 4865, ~ (2012)
- Misha Rudnev, "Note on the Number of Hinges Defined by a Point Set in ℝ2", Combinatorica, 40(5), pp.749~757 (2020), Springer Science and Business Media LLC[DOI]
- M. Sharir, "Incidences between points and lines on two-and threedimensional varieties", Discrete & Computational Geometry, 59(1), pp.88~130 (2018)
- J. Solymosi, "On the number of k-rich transformations", Computational geometry (SCG’07), pp.227~231, ACM
- J. Solymosi, "Distinct distances in the plane", Discrete & Computational Geometry, 25(4), pp.629~634 (2001)
- Gábor Tardos, "On distinct sums and distinct distances", Advances in Mathematics, 180(1), pp.275~289 (2003), Elsevier BV[DOI]
- Tamar Ziegler, "Nilfactors of ℝ m and configurations in sets of positive upper density in ℝ m", Journal d'Analyse Mathématique, 99(1), pp.249~266 (2006), Springer Science and Business Media LLC[DOI]