×

Bounding the dimension of points on a line. (English) Zbl 1496.68160

Summary: We use Kolmogorov complexity methods to give a lower bound on the effective Hausdorff dimension of the point \((x, ax + b)\), given real numbers \(a, b\), and \(x\). We apply our main theorem to a problem in fractal geometry, giving an improved lower bound on the (classical) Hausdorff dimension of generalized sets of Furstenberg type.

MSC:

68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
28A80 Fractals
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Lutz, J. H., Dimension in complexity classes, SIAM J. Comput., 32, 5, 1236-1259 (2003) · Zbl 1026.68059
[2] Lutz, J. H., The dimensions of individual strings and sequences, Inf. Comput., 187, 1, 49-79 (2003) · Zbl 1090.68053
[3] Downey, R.; Hirschfeldt, D., Algorithmic Randomness and Complexity (2010), Springer · Zbl 1221.68005
[4] Gu, X.; Lutz, J. H.; Mayordomo, E.; Moser, P., Dimension spectra of random subfractals of self-similar fractals, Ann. Pure Appl. Log., 165, 11, 1707-1726 (2014) · Zbl 1360.68523
[5] Mayordomo, E., Effective Hausdorff dimension in general metric spaces, Theory Comput. Syst. (February 2018) · Zbl 1436.03232
[6] Dougherty, R.; Lutz, J. H.; Mauldin, R. D.; Teutsch, J., Translating the Cantor set by a random real, Trans. Am. Math. Soc., 366, 3027-3041 (2014) · Zbl 1295.68139
[7] Mayordomo, E., A Kolmogorov complexity characterization of constructive Hausdorff dimension, Inf. Process. Lett., 84, 1, 1-3 (2002) · Zbl 1045.68570
[8] Miller, J. S., “Open Questions” section of personal webpage (2016)
[9] Lutz, J. H.; Weihrauch, K., Connectivity properties of dimension level sets, Math. Log. Q., 54, 483-491 (2008) · Zbl 1155.03044
[10] Turetsky, D., Connectedness properties of dimension level sets, Theor. Comput. Sci., 412, 29, 3598-3603 (2011) · Zbl 1254.28002
[11] Lutz, J. H.; Lutz, N., Algorithmic information, plane Kakeya sets, and conditional dimension, ACM Trans. Comput. Theory, 10, 2, 7:1-7:22 (2018) · Zbl 1427.68132
[12] Lutz, J. H.; Lutz, N., Lines missing every random point, Computability, 4, 2, 85-102 (2015) · Zbl 1333.03110
[13] Hitchcock, J. M., Correspondence principles for effective dimensions, Theory Comput. Syst., 38, 5, 559-571 (2005) · Zbl 1084.68054
[14] Davies, R. O., Some remarks on the Kakeya problem, Proc. Camb. Philos. Soc., 69, 417-421 (1971) · Zbl 0209.26602
[15] Wolff, T., Recent work connected with the Kakeya problem, (Prospects in Mathematics. Prospects in Mathematics, Princeton, NJ, 1996 (1999), American Mathematical Society), 129-162 · Zbl 0934.42014
[16] Rela, E., Refined size estimates for Furstenberg sets via Hausdorff measures: a survey of some recent results, (Concrete Operators, Spectral Theory, Operators in Harmonic Analysis and Approximation (2014), Springer), 421-454 · Zbl 1318.28013
[17] Molter, U.; Rela, E., Furstenberg sets for a fractal set of directions, Proc. Am. Math. Soc., 140, 2753-2765 (2012) · Zbl 1280.28006
[18] Gács, P., On the symmetry of algorithmic information, Sov. Math. Dokl., 15, 1477-1480 (1974) · Zbl 0314.94019
[19] Li, M.; Vitányi, P. M., An Introduction to Kolmogorov Complexity and Its Applications (2008), Springer · Zbl 1185.68369
[20] Nies, A., Computability and Randomness (2009), Oxford University Press · Zbl 1169.03034
[21] Lutz, J. H.; Mayordomo, E., Dimensions of points in self-similar fractals, SIAM J. Comput., 38, 3, 1080-1112 (2008) · Zbl 1187.68269
[22] Case, A.; Lutz, J. H., Mutual dimension, ACM Trans. Comput. Theory, 7, 3, 12 (2015) · Zbl 1348.03041
[23] Weihrauch, K., Computable Analysis: An Introduction (2000), Springer · Zbl 0956.68056
[24] Mayordomo, E., Effective fractal dimension in algorithmic information theory, (Cooper, S. B.; Löwe, B.; Sorbi, A., New Computational Paradigms: Changing Conceptions of What is Computable (2008), Springer), 259-285 · Zbl 1144.68030
[25] Falconer, K. J., The Geometry of Fractal Sets (1985), Cambridge University Press · Zbl 0587.28004
[26] Mattila, P., Geometry of Sets and Measures in Euclidean Spaces: Fractals and Rectifiability (1995), Cambridge University Press · Zbl 0819.28004
[27] Katz, N. H.; Tao, T., Some connections between Falconer’s distance set conjecture and sets of Furstenburg type, N.Y. J. Math., 7, 149-187 (2001) · Zbl 0991.28006
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.