2026-08-21T18:34:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27419 2026-08-21T14:42:39Z ddc:004 open_access

Finite-State Dimension and the Davenport-Erdős Theorem Clanin, Joe Rayman, Matthew Normal numbers finite-state dimension polynomials A 1952 result of Davenport and Erdős states that if p is an integer-valued polynomial, then the real number 0.p(1)p(2)p(3)… is Borel normal in base ten. A later result of Nakai and Shiokawa extends this result to polynomials with arbitrary real coefficients and all bases b ≥ 2. It is well-known that finite-state dimension, a finite-state effectivization of the classical Hausdorff dimension, characterizes the Borel normal sequences as precisely those sequences of finite-state dimension 1. For an infinite set A of natural numbers, and a base b ≥ 2, the base-b Copeland-Erdős sequence of A, CE_b(A), is the infinite sequence obtained by concatenating the base-b expansions of the numbers in A in increasing order. In this work we investigate the possible relationships between the finite-state dimensions of CE_b(A) and CE_b(p(A)) where p is a polynomial. We show that, if the polynomial is permitted to have arbitrary real coefficients, then for any s,s^′ in the unit interval, there is a set A of natural numbers and a linear polynomial p so that the finite-state dimensions of CE_b(A) and CE_b(p(A)) are s and s^′ respectively. The corresponding result for strong finite-state dimension is also shown. We demonstrate that linear polynomials with rational coefficients do not change the finite-state dimension of any Copeland-Erdős sequence, but there exist polynomials with rational coefficients of every larger integer degree that change the finite-state dimension of some sequence. We also prove the surprising fact that there exist sets A and integer-valued monomials p such that CE_b(A) is normal, but CE_b(p(A)) has finite-state dimension strictly less than one. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Joe Clanin and Matthew Rayman 2026 Is Part Of LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2026.38 urn:nbn:de:0030-drops-274195 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.38 eng https://creativecommons.org/licenses/by/4.0/legalcode