This paper investigates the algorithmic dimension spectra of lines in the Euclidean plane. Given any line L with slope a and vertical intercept b, the dimension spectrum is the set of all effective Hausdorff dimensions of individual points on L. We draw on Kolmogorov complexity and geometrical arguments to show that if the effective Hausdorff dimension is equal to the effective packing dimension , then contains a unit interval. We also show that, if the dimension is at least one, then is infinite. Together with previous work, this implies that the dimension spectrum of any line is infinite.
47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21–24 October 2006, Berkeley, California, USA, Proceedings, in: FOCS, IEEE Computer Society, 2006. ISBN 0-7695-2720-5.
2.
K.B.Athreya, J.M.Hitchcock, J.H.Lutz and E.Mayordomo, Effective strong dimension in algorithmic information and computational complexity, SIAM J. Comput.37(3) (2007), 671–705. doi:10.1137/S0097539703446912.
3.
A.Case and J.H.Lutz, Mutual dimension, ACM Transactions on Computation Theory7(3) (2015), 12. doi:10.1145/2786566.
4.
A.Case and J.H.Lutz, Mutual dimension and random sequences, in: Mathematical Foundations of Computer Science 2015 – 40th International Symposium, MFCS 2015, Proceedings, Part II, Milan, Italy, August 24–28, 2015, G.F.Italiano, G.Pighizzini and D.Sannella, eds, Lecture Notes in Computer Science, Vol. 9235, Springer, 2015, pp. 199–210.
5.
G.J.Chaitin, On the length of programs for computing finite binary sequences, J. ACM13(4) (1966), 547–569. doi:10.1145/321356.321363.
6.
G.J.Chaitin, On the length of programs for computing finite binary sequences: Statistical considerations, J. ACM16(1) (1969), 145–159. doi:10.1145/321495.321506.
7.
T.R.Cover and J.A.Thomas, Elements of Information Theory, 2nd edn, Wiley, 2006.
8.
R.O.Davies, Some remarks on the Kakeya problem, Proceedings of the Cambridge Philosophical Society69 (1971), 417–421. doi:10.1017/S0305004100046867.
9.
R.Dougherty, J.Lutz, R.D.Mauldin and J.Teutsch, Translating the Cantor set by a random real, Transactions of the American Mathematical Society366(6) (2014), 3027–3041. doi:10.1090/S0002-9947-2014-05912-6.
10.
R.Downey and D.Hirschfeldt, Algorithmic Randomness and Complexity, Springer-Verlag, 2010. ISBN 0387955674.
K.J.Falconer, The Geometry of Fractal Sets, Cambridge University Press, 1985.
13.
P.Gács, On the symmetry of algorithmic information, Soviet Mathematics Doklady15 (1974), 1477–1480.
14.
X.Gu, J.H.Lutz and E.Mayordomo, Points on Computable Curves, CoRR abs/cs/0512042, 2005.
15.
X.Gu, J.H.Lutz, E.Mayordomo and P.Moser, Dimension spectra of random subfractals of self-similar fractals, Ann. Pure Appl. Logic165(11) (2014), 1707–1726. doi:10.1016/j.apal.2014.07.001.
16.
J.M.Hitchcock, Correspondence principles for effective dimensions, Theory of Computing Systems38(5) (2005), 559–571. doi:10.1007/s00224-004-1122-1.
17.
G.F.Italiano, G.Pighizzini and D.Sannella (eds), Mathematical Foundations of Computer Science 2015 – 40th International Symposium, Proceedings, Part II, MFCS 2015, Milan, Italy, August 24–28, 2015, Lecture Notes in Computer Science, Vol. 9235, Springer, 2015.
18.
N.Katz and T.Tao, Recent progress on the Kakeya conjecture, in: Proceedings of the 6th International Conference on Harmonic Analysis and Partial Differential Equations, Publicacions Matematiques, 2002, pp. 161–180.
19.
N.H.Katz and T.Tao, Some connections between Falconer’s distance set conjecture and sets of Furstenburg type, New York J. Math7 (2001), 149–187.
20.
L.A.Levin, On the notion of a random sequence, Soviet Math Dokl.14(5) (1973), 1413–1416.
21.
M.Li and P.M.B.Vitányi, An Introduction to Kolmogorov Complexity and Its Applications, 3rd edn, Springer, 2008, 9780387339986. ISBN 0387339981.
22.
J.H.Lutz, The dimensions of individual strings and sequences, Inf. Comput.187(1) (2003), 49–79. doi:10.1016/S0890-5401(03)00187-1.
23.
J.H.Lutz, Dimension in complexity classes, SIAM J. Comput.32(5) (2003), 1236–1259. doi:10.1137/S0097539701417723.
24.
J.H.Lutz and N.Lutz, Lines missing every random point, Computability4(2) (2015), 85–102. doi:10.3233/COM-150038.
25.
J.H.Lutz and N.Lutz, Algorithmic information, plane Kakeya sets, and conditional dimension, ACM Trans. Comput. Theory10(2) (2018), 7:1–7:22. doi:10.1145/3201783.
26.
J.H.Lutz and E.Mayordomo, Dimensions of points in self-similar fractals, SIAM J. Comput.38(3) (2008), 1080–1112. doi:10.1137/070684689.
27.
J.H.Lutz and K.Weihrauch, Connectivity properties of dimension level sets, Mathematical Logic Quarterly54 (2008), 483–491. doi:10.1002/malq.200710060.
28.
N.Lutz and D.M.Stull, Bounding the Dimension of Points on a Line, Information and Computation275 (2020).
29.
P.Mattila, Geometry of Sets and Measures in Euclidean Spaces: Fractals and Rectifiability, Cambridge University Press, 1999.
30.
E.Mayordomo, A Kolmogorov complexity characterization of constructive Hausdorff dimension, Inf. Process. Lett.84(1) (2002), 1–3. doi:10.1016/S0020-0190(02)00343-5.
31.
E.Mayordomo, Effective fractal dimension in algorithmic information theory, in: New Computational Paradigms: Changing Conceptions of What Is Computable, S.B.Cooper, B.Löwe and A.Sorbi, eds, Springer, New York, 2008, pp. 259–285. doi:10.1007/978-0-387-68546-5_12.
32.
E.Mayordomo, Effective dimension in some general metric spaces, in: Proceedings 8th International Workshop on Developments in Computational Models, DCM 2012, Cambridge, United Kingdom, 17 June 2012, 2012, pp. 67–75.
33.
J.S.Miller, “Open Questions” section of personal webpage, Retrieved October30 (2016).
34.
U.Molter and E.Rela, Furstenberg sets for a fractal set of directions, Proc. Amer. Math. Soc.140 (2012), 2753–2765. doi:10.1090/S0002-9939-2011-11111-0.
35.
A.Nies, Computability and Randomness, Oxford University Press, Inc., New York, NY, USA, 2009, 9780199230761. ISBN 0199230765.
36.
J.Reimann, Effectively closed classes of measures and randomness, Annals of Pure and Applied Logic156(1) (2008). doi:10.1016/j.apal.2008.06.015.
37.
E.Rela, Refined size estimates for Furstenberg sets via Hausdorff measures: A survey of some recent results, in: Concrete Operators, Spectral Theory, Operators in Harmonic Analysis and Approximation, Springer, 2014, pp. 421–454. doi:10.1007/978-3-0348-0648-0_27.
38.
R.J.Solomonoff, A formal theory of inductive inference, Information and Control7(1–2) (1964), 1–22, 224–254. doi:10.1016/S0019-9958(64)90131-7.
39.
T.Tao, From rotating needles to stability of waves: Emerging connections between combinatorics, analysis, and PDE, Notices Amer. Math. Soc48 (2000), 294–303.
