chebЧебышевский сборникChebyshevskii Sbornik2226-8383Tula State Lev Tolstoy Pedagogical University10.22405/2226-8383-2021-22-4-344-351cheb-1149Research ArticleКраткие сообщенияОб оценках на диаметр плоских множеств с целочисленными расстояниями полуобщего положенияOn diameter bounds for planar integral point sets in semi-general positionАвдеевНиколай НиколаевичAvdeevNikolai Nikolaevichnickkolok@mail.ruВоронежский государственный университетРоссияVoronezh State UniversityRussian Federation202111012022224344351Copyright © Авдеев Н.Н., 20212021Авдеев Н.Н.Avdeev N.N.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.chebsbornik.ru/jour/article/view/1149

Множество точек 𝑀 на плоскости называется плоским множеством с целочисленными расстояниями, если все расстояния между точками 𝑀 суть целые числа, и при этом𝑀 не содержится ни в какой прямой. Говорят, что плоское множество с целочисленными расстояниями есть множество полуобщего положения, если никакие три его точки не лежат на одной прямой. Известная оценка снизу для плоского множества с целочисленными расстояниями линейна относительно его мощности. Ранее не были известны отдельные оценки снизу на диаметр плоских множеств с целочисленными расстояниями полуобщего положения заданной мощности (известная конструктивная оценка сверху на диаметр плоских множеств с целочисленными расстояниями использует как раз множества полуобщего положения). В статье доказывается надлинейная оценка снизу на диаметр плоского множества с целочисленными расстояниями полуобщего положения (полиномиальная споказателем 5/4). Доказательство основано на относительно большом количестве лемм и наблюдений, включая результаты Солимоси из статьи, в которой была впервые доказана линейная оценка снизу на диаметр плоских множеств с целочисленными расстояниями.

A point set 𝑀 in the Euclidean plane is said to be a planar integral point set if all the distances between the elements of 𝑀 are integers, and 𝑀 is not situated on a straight line.A planar integral point set is said to be a set in semi-general position, if it does not contain collinear triples. The existing lower bound for mininal diameter of a planar integral point set islinear with respect to its cardinality. There were no known special diameter bounds for planar integral point sets in semi-general position of given cardinality (the known upper bound forplanar integral point sets is constructive and employs planar integral point sets in semi-general position). We prove a new lower bound for minimal diameter of planar integral point sets insemi-general position that is better than linear (polynomial of power 5/4). The proof is based on several lemmas and observations, including the ones established by Solymosi to prove the first linear lower bound for diameter of a planar integral point set.

комбинаторная геометриядиаметр множествамножество с целочис- ленными расстояниями.combinatorial geometrydiameter of a setintegral point set.Исследование выполнено за счет гранта Российского научного фонда (проект 19-11-00197).ReferencesAnning N. H., Erd¨os P. Integral distances // Bulletin of the American Mathematical Society. — 1945. — т. 51, No 8. — с. 598—600.Anning, N.H. & Erd¨os, P. 1945. “Integral distances”. Bulletin of the American Mathematical Society, vol. 51.8, pp. 598—600. doi: 10.1090/S0002-9904-1945-08407-9Erd¨os P. Integral distances // Bulletin of the American Mathematical Society. — 1945. — т. 51, No 12. — с. 996.Erd¨os, P. 1945. “Integral distances”. Bulletin of the American Mathematical Society, vol. 51.12, p. 996. doi: 10.1090/S0002-9904-1945-08490-0Авдеев Н. Н., Семёнов Е. М. Множества точек с целочисленными расстояниями на плоскости и в евклидовом пространстве // Математический форум (Итоги науки. Юг России). — 2018. — с. 217—236.Avdeev, N.N. & Semenov, E.M. 2018. “Mnozhestva tochek c tselochislennymi rasstoyaniyami na ploskosti i v evklidovom prostranstve” (“Integral point sets on the plane and in EuclideanKurz S., Laue R. Bounds for the minimum diameter of integral point sets // Australasian Journal of Combinatorics. — 2007. — т. 39. — с. 233—240. — arXiv: 0804.1296.space”) Matematicheskiy forum (Itogi nauki. Yug Rossii), pp. 217—236.Kurz S., Wassermann A. On the minimum diameter of plane integral point sets // Ars Combinatoria. — 2011. — т. 101. — с. 265—287. — arXiv: 0804.1307.Kurz, S. & Laue, R. 2007. “Bounds for the minimum diameter of integral point sets”. Australasian Journal of Combinatorics, vol. 39, pp. 233—240. arXiv: 0804.1296.Antonov A. R., Kurz S. Maximal integral point sets over Z2 // International Journal of Computer Mathematics. — 2008. — т. 87, No 12. — с. 2653—2676. — arXiv: 0804.1280.Kurz, S. & Wassermann, A. 2011. “On the minimum diameter of plane integral point sets”. Ars Combinatoria, vol. 101, pp. 265—287. arXiv: 0804.1307.Huff G. B. Diophantine problems in geometry and elliptic ternary forms // Duke Mathematical Journal. — 1948. — т. 15, No 2. — с. 443—453.Antonov, A.R. & Kurz, S. 2008. “Maximal integral point sets over 𝑍2”. International Journal of Computer Mathematics, vol. 87.12, pp. 2653—2676. arXiv: 0804.1280. doi: 10.1080/Harborth H., Kemnitz A., M¨oller M. An upper bound for the minimum diameter of integral point sets // Discrete & Computational Geometry. — 1993. — т. 9, No 4. — с. 427—432.Harborth H., Kemnitz A., M¨oller M. An upper bound for the minimum diameter of integral point sets // Discrete & Computational Geometry. — 1993. — т. 9, No 4. — с. 427—432.Piepmeyer L. The maximum number of odd integral distances between points in the plane // Discrete & Computational Geometry. — 1996. — т. 16, No 1. — с. 113—115.Huff, G.B. 1948. “Diophantine problems in geometry and elliptic ternary forms”. Duke Mathematical Journal, vol. 15.2, pp. 443—453. doi:10.1215/S0012-7094-48-01543-9Kreisel T., Kurz S. There are integral heptagons, no three points on a line, no four on a circle // Discrete & Computational Geometry. — 2008. — т. 39, No 4. — с. 786—790.Harborth, H., Kemnitz, A. & M¨oller, M. 1993. “An upper bound for the minimum diameter of integral point sets”. Discrete & Computational Geometry vol. 9.4, pp. 427—432. doi:Constructing 7-clusters / S. Kurz [и др.] // Serdica Journal of Computing. — 2014. — т. 8, No 1. — с. 47—70. — arXiv: 1312.2318.1007/bf02189331Solymosi J. Note on integral distances // Discrete & Computational Geometry. — 2003. — т. 30, No 2. — с. 337—342.Piepmeyer, L. 1996. “The maximum number of odd integral distances between points in the plane”. Discrete & Computational Geometry, vol. 16.1, pp. 113—115. doi: 10.1007/bf02711135Avdeev N. On existence of integral point sets and their diameter bounds. // Australasian Journal of Combinatorics. — 2020. — т. 77.1. — с. 100—116. — arXiv: 1906.11926.Kreisel, T. & Kurz, S. 2008. “There are integral heptagons, no three points on a line, no four on a circle”. Discrete & Computational Geometry, vol. 39.4, pp. 786—790. doi: 10.1007/s00454-007-9038-6Bat-Ochir G. On the number of points with pairwise integral distances on a circle // Discrete Applied Mathematics. — 2018. — т. 254. — с. 17—32.Kurz, S., Noll, L.C., Rathbun, R, & Simmons, C. 2014. “Constructing 7-clusters”. Serdica Journal of Computing, vol. 8.1, pp. 47—70. arXiv: 1312.2318.Brass P., Moser W. O., Pach J. Research problems in discrete geometry. — Springer Science & Business Media, 2006.Solymosi, J. 2003. “Note on integral distances”. Discrete & Computational Geometry, vol. 30.2, pp. 337—342. doi: 10.1007/s00454-003-0014-7Guy R. Unsolved problems in number theory. т. 1. — Springer Science & Business Media, 2013.Avdeev, N. N. 2019. “On existence of integral point sets and their diameter bounds”. Australasian Journal of Combinatorics, vol. 77.1, pp. 100—116. arXiv: 1906.11926Авдеев Н. Н. Об отыскании целоудалённых множеств специального вида // Актуальные проблемы прикладной математики, информатики и механики - сборник трудов Международной научной конференции. — Научно-исследовательские публикации, 2018. — с. 492—498.Bat-Ochir, G. 2018. “On the number of points with pairwise integral distances on a circle”. Discrete Applied Mathematics, vol. 254, pp. 17—32. doi: 10.1016/j.dam.2018.07.004Авдеев Н. Н. On integral point sets in special position // Некоторые вопросы анализа, алгебры, геометрии и математического образования: материалы международной молодежной научной школы «Актуальные направления математического анализа и смежные вопросы». — 2018. — т. 8. — с. 5—6.Brass, P., Moser, W.O.J. & Pach, J. 2006. Research problems in discrete geometry. Springer Science & Business Media. doi: 10.1007/0-387-29929-7Kurz S. On the characteristic of integral point sets in 𝐸𝑚 // Australasian Journal of Combinatorics. — 2006. — т. 36. — с. 241. — arXiv: math/0511704.Guy, R. 2013. Unsolved problems in number theory. Vol. 1. Springer Science & Business Media. doi: 10.1007/978-1-4757-1738-9Nozaki H. Lower bounds for the minimum diameter of integral point sets // Australasian Journal of Combinatorics. — 2013. — т. 56. — с. 139—143.Avdeev, N.N. 2018. “Ob otyskanii tseloudalennykh mnozhestv spetsial’nogo vida” (“On the search of integral point sets of a special type”). Aktual’nye problemy prikladnoj matematiki, informatiki i mekhaniki - sbornik trudov Mezhdunarodnoj nauchnoj konferencii. (Actual problems of applied mathematics, informatics and mechanics - proc. of the int. conf.). Voronezh, pp. 492—498.Смуров М., Спивак А. Покрытия полосками // Квант. — 1998. — No 5. — с. 6.Avdeev, N.N. 2018. “On integral point sets in special position”. Nekotorye voprosy analiza, algebry, geometrii i matematicheskogo obrazovaniya (Some problems of analysis, algebra, geometry and mathematical education), vol. 8, pp. 5—6.Kurz, S. 2006. “On the characteristic of integral point sets in 𝐸𝑚”. Australasian Journal of Combinatorics, vol. 36, pp. 241–248. arXiv: math/0511704.Kurz, S. 2006. “On the characteristic of integral point sets in 𝐸𝑚”. Australasian Journal of Combinatorics, vol. 36, pp. 241–248. arXiv: math/0511704.Nozaki, H. 2013. “Lower bounds for the minimum diameter of integral point sets”. Australasian Journal of Combinatorics, vol. 56, pp. 139—143.Nozaki, H. 2013. “Lower bounds for the minimum diameter of integral point sets”. Australasian Journal of Combinatorics, vol. 56, pp. 139—143.Smurov, M. & Spivak, A. 1998. “Pokrytiya poloskami” (“Covering by strips”). Kvant, vol. 5, pp. 6–12.Smurov, M. & Spivak, A. 1998. “Pokrytiya poloskami” (“Covering by strips”). Kvant, vol. 5, pp. 6–12.

The authors declare that there are no conflicts of interest present.