Approximations of the Lagrange and Markov spectra

Delecroix, Vincent; Matheus, Carlos; Moreira, Carlos Gustavo

doi:10.1090/mcom/3513

Approximations of the Lagrange and Markov spectra
HTML articles powered by AMS MathViewer

by Vincent Delecroix, Carlos Matheus and Carlos Gustavo Moreira;

Math. Comp. 89 (2020), 2521-2536

DOI: https://doi.org/10.1090/mcom/3513

Published electronically: January 29, 2020

HTML | PDF | Request permission

Abstract:

We describe a polynomial time algorithm providing finite sets arbitrarily close (in Hausdorff topology) to the Lagrange and Markov spectra.

References

Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Robert E. Tarjan, A new approach to incremental cycle detection and related problems, ACM Trans. Algorithms 12 (2016), no. 2, Art. 14, 22. MR 3465937, DOI 10.1145/2756553
A. A. Beršteĭn, The connections between the Markov and Lagrange spectra, Number-theoretic studies in the Markov spectrum and in the structural theory of set addition (Russian), Kalinin. Gosudarstv. Univ., Moscow, 1973, pp. 16–49, 121–125 (Russian, with English summary). MR 429768
Thomas W. Cusick and Mary E. Flahive, The Markoff and Lagrange spectra, Mathematical Surveys and Monographs, vol. 30, American Mathematical Society, Providence, RI, 1989. MR 1010419, DOI 10.1090/surv/030
R. Bradshaw, S. Behnel, D. S. Seljebotn, G. Ewing et al., The Cython compiler, http://cython.org.
N. G. de Bruijn, A combinatorial problem, Nederl. Akad. Wetensch., Proc. 49 (1946), 758–764 = Indagationes Math. 8, 461–467 (1946). MR 18142
G. A. Freĭman, Non-coincidence of the spectra of Markov and of Lagrange, Mat. Zametki 3 (1968), 195–200 (Russian). MR 227110
G. A. Freĭman, The initial point of Hall’s ray, Number-theoretic studies in the Markov spectrum and in the structural theory of set addition (Russian), Kalinin. Gosudarstv. Univ., Moscow, 1973, pp. 87–120, 121–125 (Russian, with English summary). MR 429771
Bernhard Haeupler, Telikepalli Kavitha, Rogers Mathew, Siddhartha Sen, and Robert E. Tarjan, Faster algorithms for incremental topological ordering, Automata, languages and programming. Part I, Lecture Notes in Comput. Sci., vol. 5125, Springer, Berlin, 2008, pp. 421–433. MR 2500290, DOI 10.1007/978-3-540-70575-8_{3}5
Bernhard Haeupler, Telikepalli Kavitha, Rogers Mathew, Siddhartha Sen, and Robert E. Tarjan, Incremental cycle detection, topological ordering, and strong component maintenance, ACM Trans. Algorithms 8 (2012), no. 1, Art. 3, 33. MR 2893005, DOI 10.1145/2071379.2071382
Doug Hensley, Continued fraction Cantor sets, Hausdorff dimension, and functional analysis, J. Number Theory 40 (1992), no. 3, 336–358. MR 1154044, DOI 10.1016/0022-314X(92)90006-B
Douglas Hensley, A polynomial time algorithm for the Hausdorff dimension of continued fraction Cantor sets, J. Number Theory 58 (1996), no. 1, 9–45. MR 1387719, DOI 10.1006/jnth.1996.0058
J. D. Hunter, Matplotlib: A 2D graphics environment, Computing in Science & Engineering 9 (2007), no. 3, pp. 90–95, doi:10.1109/MCSE.2007.55.
Oliver Jenkinson, On the density of Hausdorff dimensions of bounded type continued fraction sets: the Texan conjecture, Stoch. Dyn. 4 (2004), no. 1, 63–76. MR 2069367, DOI 10.1142/S0219493704000900
Oliver Jenkinson and Mark Pollicott, Computing the dimension of dynamically defined sets: $E_2$ and bounded continued fractions, Ergodic Theory Dynam. Systems 21 (2001), no. 5, 1429–1445. MR 1855840, DOI 10.1017/S0143385701001687
O. Jenkinson and M. Pollicott, Rigorous effective bounds on the Hausdorff dimension of continued fraction Cantor sets: a hundred decimal digits for the dimension of $E_2$, Adv. Math. 325 (2018), 87–115. MR 3742587, DOI 10.1016/j.aim.2017.11.028
Markoff, Sur les formes quadratiques binaires indéfinies, Math. Ann. 15 (1879), no. 3, 381-406 (French)., DOI 10.1007/BF02086269
A. Markoff, Sur les formes quadratiques binaires indéfinies, Math. Ann. 17 (1880), no. 3, 379–399 (French). (Sécond mémoire). MR 1510073, DOI 10.1007/BF01446234
C. Matheus and C. G. Moreira, Fractal geometry of the complement of Lagrange spectrum in Markov spectrum, preprint, 2018, arXiv:1803.01230, Comment. Math. Helv. (to appear).
Carlos Gustavo Moreira, Geometric properties of the Markov and Lagrange spectra, Ann. of Math. (2) 188 (2018), no. 1, 145–170. MR 3815461, DOI 10.4007/annals.2018.188.1.3
T. Morrison, A glimpse of the Markoff spectrum, preprint, 2012, available at https://dca.ue.ucsc.edu/system/files/dca/2012/193/193.pdf.
O. Perron, Über die approximation irrationaler Zahlen durch rationale II, S.-B. Heidelberg Akad. Wiss. 8 (1921).
Jacob Palis and Floris Takens, Hyperbolicity and sensitive chaotic dynamics at homoclinic bifurcations, Cambridge Studies in Advanced Mathematics, vol. 35, Cambridge University Press, Cambridge, 1993. Fractal dimensions and infinitely many attractors. MR 1237641
SageMath, the Sage Mathematics Software System (Version 8.8), The Sage Developers, 2019, https://www.sagemath.org.
Hanno Schecker, Über die Menge der Zahlen, die als Minima quadratischer Formen auftreten, J. Number Theory 9 (1977), no. 1, 121–141 (German, with English summary). MR 466031, DOI 10.1016/0022-314X(77)90056-7