Effective packing dimension of -classes

Author:
Chris J. Conidis

Journal:
Proc. Amer. Math. Soc. **136** (2008), 3655-3662

MSC (2000):
Primary 03Dxx, 68Qxx

Published electronically:
May 15, 2008

MathSciNet review:
2415051

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We construct a -class that has classical packing dimension 0 and effective packing dimension 1. This implies that, unlike in the case of effective Hausdorff dimension, there is no natural correspondence principle (as defined by Lutz) for effective packing dimension. We also examine the relationship between upper box dimension and packing dimension for -classes.

**1.**Krishna B. Athreya, John M. Hitchcock, Jack H. Lutz, and Elvira Mayordomo,*Effective strong dimension in algorithmic information and computational complexity*, SIAM J. Comput.**37**(2007), no. 3, 671–705 (electronic). MR**2341912**, 10.1137/S0097539703446912**2.**R. Downey and D.R. Hirschfeldt.*Algorithmic Randomness and Complexity*. Springer-Verlag, to appear.**3.**Rod Downey, Denis R. Hirschfeldt, André Nies, and Sebastiaan A. Terwijn,*Calibrating randomness*, Bull. Symbolic Logic**12**(2006), no. 3, 411–491. MR**2248591****4.**Kenneth Falconer,*Fractal geometry*, 2nd ed., John Wiley & Sons, Inc., Hoboken, NJ, 2003. Mathematical foundations and applications. MR**2118797****5.**John M. Hitchcock,*Correspondence principles for effective dimensions*, Theory Comput. Syst.**38**(2005), no. 5, 559–571. MR**2156936**, 10.1007/s00224-004-1122-1**6.**Ming Li and Paul Vitányi,*An introduction to Kolmogorov complexity and its applications*, 2nd ed., Graduate Texts in Computer Science, Springer-Verlag, New York, 1997. MR**1438307****7.**Jack H. Lutz,*The dimensions of individual strings and sequences*, Inform. and Comput.**187**(2003), no. 1, 49–79. MR**2018734**, 10.1016/S0890-5401(03)00187-1**8.**Joseph S. Miller and André Nies,*Randomness and computability: open questions*, Bull. Symbolic Logic**12**(2006), no. 3, 390–410. MR**2248590****9.**A. Nies,*Computability and Randomness*. Oxford University Press, to appear.**10.**Robert I. Soare,*Recursively enumerable sets and degrees*, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. A study of computable functions and computably generated sets. MR**882921****11.**R. I. Soare,*Computability Theory and Applications,*Springer-Verlag, Heidelberg, to appear.

Retrieve articles in *Proceedings of the American Mathematical Society*
with MSC (2000):
03Dxx,
68Qxx

Retrieve articles in all journals with MSC (2000): 03Dxx, 68Qxx

Additional Information

**Chris J. Conidis**

Affiliation:
Department of Mathematics, The University of Chicago, 5734 University Avenue, Chicago, Illinois 60637-1546

Email:
conidis@math.uchicago.edu

DOI:
https://doi.org/10.1090/S0002-9939-08-09335-0

Received by editor(s):
August 2, 2007

Received by editor(s) in revised form:
August 22, 2007

Published electronically:
May 15, 2008

Additional Notes:
The author would like to acknowledge the helpful input he received from Jan Reimann, as well as his thesis advisors, Robert I. Soare and Denis R. Hirschfeldt. The author would also like to thank the American Institute of Mathematics for hosting a valuable workshop in effective randomness which lead to the publication of this article.

Communicated by:
Julia Knight

Article copyright:
© Copyright 2008
American Mathematical Society