2024/03/13 by Satyadev Nandakumar, Nandakumar, Satyadev, Subin Pulari +3 · 1 citation
Computer Science · Mathematics · #03D32 #28A78 #68P30 #FOS: Computer and information sciences #Information Theory (cs.IT) #cs.IT #math.IT #msc:03D32 #msc:28A78 #msc:68P30
paper · pdf · doi:10.48550/arxiv.2403.08278
arxiv created 2026/07/30 · arxiv updated 2026/07/31
Hausdorff Φ-dimension is a notion of Hausdorff dimension developed using a restricted class of coverings of a set. We introduce an effective version of Hausdorff Φ-dimension, which we call constructive Φ-dimension. We prove a point-to-set principle for Φ-dimension. We also provide a characterization of constructive Φ-dimension using Kolmogorov complexity and s-gales. Finally, we apply these tools to study faithfulness of coverings Φ. A family of coverings Φ is said to be faithful to Hausdorff dimension if the Φ-dimension and Hausdorff dimension coincide for every set. Similarly, Φ is said to be faithful to constructive dimension if the constructive Φ-dimension and constructive dimension coincide for every set. We derive the necessary and sufficient conditions for the constructive dimension faithfulness of the coverings generated by the Cantor series expansion, based on the terms of the expansion. Using the point-to-set principle for Cantor coverings, we show that the same condition characterises Hausdorff dimension faithfulness of Cantor coverings, thereby giving an information theoretic proof of the result by Albeverio, Ivanenko, Lebid, and Torbin. We investigate the question of weather the notions of faithfulness at Hausdorff and constructive levels are equivalent. Using a new technique for the construction of sequences satisfying a certain Kolmogorov complexity condition, we show that the notions of ``faithfulness'' of Cantor coverings at the Hausdorff and constructive levels are equivalent, independent of the log-limit condition.