The Maximal Number of 3-Term Arithmetic Progressions in Finite Sets in Different Geometries
Tóm tắt
Green and Sisask showed that the maximal number of 3-term arithmetic progressions in n-element sets of integers is
$$\lceil n^2/2\rceil $$
; it is easy to see that the same holds if the set of integers is replaced by the real line or by any Euclidean space. We study this problem in general metric spaces, where a triple (a, b, c) of points in a metric space is considered a 3-term arithmetic progression if
$$d(a,b)=d(b,c)=d(a,c)/2$$
. In particular, we show that the result of Green and Sisask extends to any Cartan–Hadamard manifold (in particular, to the hyperbolic spaces), but does not hold in spherical geometry or in the r-regular tree, for any
$$r\ge 3$$
.
Tài liệu tham khảo
Aaronson, J.: Maximising the number of solutions to a linear equation in a set of integers. Bull. Lond. Math. Soc. 51(4), 577–594 (2019)
Akutsu, T., Tamaki, H., Tokuyama, T.: Distribution of distances and triangles in a point set and algorithms for computing the largest common point sets. Discret. Comput. Geom. 20(3), 307–331 (1998)
Ballmann, W., Gromov, M., Schroeder, V.: Manifolds of Nonpositive Curvature. Progress in Mathematics, vol. 61. Birkhäuser, Boston (1985)
Bhattacharya, B.B., Ganguly, S., Shao, X., Zhao, Y.: Upper tail large deviations for arithmetic progressions in a random set. Int. Math. Res. Not. IMRN 2020(1), 167–213 (2020)
Bridson, M.R., Haefliger, A.: Metric Spaces of Non-Positive Curvature. Grundlehren der Mathematischen Wissenschaften, vol. 319. Springer, Berlin (1999)
de Bruijn, N.G., Erdős, P.: On a combinatorial problem. Nederl. Akad. Wetensch. Proc. 51, 1277–1279 (1948)
Burago, D., Burago, Yu., Ivanov, S.: A Course in Metric Geometry. Graduate Studies in Mathematics, vol. 33. American Mathematical Society, Providence (2001)
Burago, Yu.D., Zalgaller, V.A.: Geometric Inequalities. Grundlehren der Mathematischen Wissenschaften, vol. 285. Springer, Berlin (1988)
Chavel, I.: Isoperimetric Inequalities. Differential Geometric and Analytic Perspectives. Cambridge Tracts in Mathematics, vol. 145. Cambridge University Press, Cambridge (2001)
Cheeger, J., Ebin, D.G.: Comparison Theorems in Riemannian Geometry. North-Holland Mathematical Library, vol. 9. North-Holland, Amsterdam (1975)
Erdős, P., Purdy, G.: Some extremal problems in geometry. III. In: 6th Southeastern Conference on Combinatorics, Graph Theory, and Computing (Boca Raton 1975). Congressus Numerantium, vol. 14, pp. 291–308. Utilitas Mathematica, Winnipeg (1975)
Goodman, A.W.: On sets of acquaintances and strangers at any party. Am. Math. Mon. 66(9), 778–783 (1959)
Green, B., Sisask, O.: On the maximal number of \(3\)-term arithmetic progressions in subsets of \(\mathbb{Z}/p\mathbb{Z}\). Bull. Lond. Math. Soc. 40(6), 945–955 (2008)
Gromov, M.: Paul Levy’s isoperimetric inequality (1980). Prépublications I.H.E.S. https://www.ihes.fr/~gromov/wp-content/uploads/2018/08/1133.pdf
Kloeckner, B.R., Kuperberg, G.: The Cartan–Hadamard conjecture and the Little Prince. Rev. Mat. Iberoam. 35(4), 1195–1258 (2019)
Leader, I.: Discrete isoperimetric inequalities. In: Probabilistic Combinatorics and Its Applications (San Francisco 1991). Proceedings of Symposia in Applied Mathematics, vol. 44, pp. 57–80. American Mathematical Society, Providence (1991)
Osserman, R.: The isoperimetric inequality. Bull. Am. Math. Soc. 84(6), 1182–1238 (1978)