Finite-State Dimension and The Davenport Erdős Theorem

Abstract

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)\dots$ 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\ge 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 of natural numbers, and a base $b\ge 2$, the base $b$ Copeland-Erdős sequence of $A$, $C{E}_b(A)$, is the infinite sequence obtained by concatenating the base $b$ expressions of the numbers in $A$ in increasing order. In this work we investigate the possible relationships between the finite-state dimensions of $C{E}_b(A)$ and $C{E}_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^{\prime }$ in the unit interval, there is a set $A$ of natural numbers and a linear polynomial $p$ so that the finite-state dimensions of $C{E}_b(A)$ and $C{E}_b(p(A))$ are $s$ and $s^{\prime }$ 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 $C{E}_b(A)$ is normal, but $C{E}_b(p(A))$ has finite-state dimension strictly less than one.