Cyclic Groups and the Three Distance Theorem

Chevallier, Nicolas

Canadian journal of mathematics, Tome 59 (2007) no. 3, pp. 503-552

Résumé

We give a two dimensional extension of the three distance theorem. Let $\theta $ be in ${{\mathbf{R}}^{2}}$ and let $q$ be in $\mathbf{N}$ . There exists a triangulation of ${{\mathbf{R}}^{2}}$ invariant by ${{\mathbf{Z}}^{2}}$ -translations, whose set of vertices is ${{\mathbf{Z}}^{2}}\,+\,\{0,\,\theta ,\,\ldots ,\,q\theta \}$ , and whose number of different triangles, up to translations, is bounded above by a constant which does not depend on $\theta $ and $q$ .

Détail

DOI : 10.4153/CJM-2007-022-3

Mots-clés : 11J70, 11J71, 11J13

Bibliographie

[1] [1] Allessandri, P. and Berthé, V., Three distance theorems and combinatorics on words. Enseign. Math 44(1998), no. 1-2, 103–132. Google Scholar

[2] [2] Babai, L., On Lovász’ lattice reduction and the nearest lattice point problem. Combinatorica 6(1986), no. 1, 1–13. Google Scholar

[3] [3] Berthé, V. and Tijdeman, R., Balance properties of multi-dimensional words. Theoret. Comput. Sci. 273(2002), no. 1-2, 197–224. Google Scholar

[4] [4] Boot, B., Okabe, A., and Sugihara, K., Spatial Tessellations, Concepts and Applications of Voronoï Diagrams. John Wiley, 1991. Google Scholar

[5] [5] Chevallier, N., Meilleures approximations d’un élément du tore T2 et géométrie de la suite des multiples de cet élément. Acta Arith. 78(1996), no. 1, 19–35. Google Scholar

[6] [6] Chevallier, N., Géométrie des suites de Kronecker. Manuscripta Math. 94(1997), no. 2, 231–241. Google Scholar

[7] [7] Chevallier, N., Three distance theorem and grid graph. Discrete Math. 223(2000), no. 1-3, 355–362. Google Scholar

[8] [8] Chevallier, N., Meilleures approximations diophantiennes d’un élément du tore T d. Acta Arith. 97(2001), no. 3, 219–240. Google Scholar

[9] [9] Chung, F. R. K. and Graham, R. L., On the set of distances determined by union of arithmetic progression. Ars. Combinatoria 1(1976), no. 1, 57–76. Google Scholar

[10] [10] Dieudonné, J., Éléments d’analyse. I. fondements de l’analyse moderne. Gauthier-Villars, Paris, 1972. Google Scholar

[11] [11] Drmota, M. and Tichy, R., Sequences, Discrepancies and Applications. Lectures Notes in Mathematics 1651, Springer-Verlag, Berlin, 1997. Google Scholar

[12] [12] Fried, E. and Sós, V. T., A generalization of the three-distance theorem for groups. Algebra Universalis, 29(1992), no. 1, 136–149. Google Scholar

[13] [13] Grötschel, M., Lovász, L., and Schrijver, A., Geometric Algorithms and Combinatorial Optimization. Second edition. Algorithms and Combinatorics 2, Springer-Verlag, Berlin, 1993. Google Scholar

[14] [14] Geelen, A. S. and Simpson, R. J., A two dimensional Steinhaus theorem. Australas. J. Combin. 8 (1993), 136–197. Google Scholar

[15] [15] Lagarias, J. C., Some new results in simultaneous Diophantine approximation. Proc. of the Queen's Number Theory Conference 1979 (Ribenboim, P., Ed.), Queen's Paper in Pure and Applied Math. No. 54 (1980), 453–474. Google Scholar

[16] [16] Lagarias, J. C., Best simultaneous Diophantine approximations I. Growth Rates of Best Approximations denominators, Trans. Amer. Math. Soc. 272(1982), no. 2, 545–554. Google Scholar

[17] [17] Lagarias, J. C., Best simultaneous Diophantine approximations II. Behavior of consecutive best approximations. Pacific J. Math. 102(1982), no. 1, 61–88. Google Scholar

[18] [18] Lagarias, J. C., Best Diophantine approximations to a set of linear forms. J. Austral. Math. Soc. Ser. A 34(1983), no. 1, 114–122. Google Scholar

[19] [19] Lagarias, J. C., The computational complexity of simultaneous Diophantine approximations problems. SIAM J. Comput. 14(1985), no. 1, 196–209. Google Scholar

[20] [20] Lagarias, J. C., Geodesic multidimensional continued fractions. Proc. London Math. Soc. 69(1994), no. 3, 464–488. Google Scholar

[21] [21] Langevin, M., Stimulateur cardiaque et suite de Farey. Period. Math. Hungar. 23(1991), no. 1, 75–86. Google Scholar

[22] [22] Liang, F. M., A short proof of the 3d distance theorem. Discrete Math. 28 (1979), no. 3, 325–326. Google Scholar

[23] [23] Mignosi, F., On the number of factors of Sturmian words. Theoret. Comput. Sci. 82(1991), no. 1, 71–84. Google Scholar

[24] [24] Preparata, F. P. and Shamos, M. I., Computational geometry. An Introduction. Texts and Monographs in Computer Science, Springer-Verlag, New York, 1985. Google Scholar

[25] [25] Pytheas Fogg, N., Substitutions in Dynamics, Arithmetic and Combinatorics. Lectures Notes in Mathematics 1794, Springer-Verlag, Berlin, 2002. Google Scholar

[26] [26] van Ravenstein, T., Three gap theorem (Steinhaus conjecture). J. Austral. Math. Soc. Ser. a 45(1988), no. 3, 360–370. Google Scholar

[27] [27] Rogers, C. A., The signatures of the errors of some simultaneous Diophantine approximations. Proc. London Math. Soc. 52(1951), 186–190. Google Scholar

[28] [28] Siegel, A., Théorème des trois longueurs et suites sturmiennes: mots d’agencement des longueurs. Acta Arith. 97(2001), no. 3, 195–210. Google Scholar

[29] [29] Slater, N. B., The distribution of the integers N for whic. ﹛θN﹜ < ϕ. Proc. Cambridge Philos. Soc. 46(1950), 525–534. Google Scholar

[30] [30] Slater, N. B., Distribution problems and physical applications. Compositio Math. 16(1964), 176–183. Google Scholar

[31] [31] Slater, N. B., Gaps and steps for the sequence nθ. mod 1. Proc. Cambridge Philos. Soc. 63(1967), 1115–1123. Google Scholar

[32] [32] Sós, V. T., On the theory of diophantine approximation. I. Acta Math. Acad. Sci. Hung. 8(1957), 461–472. Google Scholar

[33] [33] Sós, V. T., On the theory of Diophantine approximation. II. Acta Math. Acad. Sci. Hung. 9(1958), 229–241. Google Scholar

[34] [34] Sós, V. T., On the distribution mod 1 of the sequence nα, Ann. Univ. Sci. Budapest, Eötvös Sect. Math. 1 (1958), 127–134. Google Scholar

[35] [35] Świerczkowski, S., On the successive settings of an arc on the circumference of a circle. Fund. Math. 46(1959), 187–189. Google Scholar