pith. sign in

arxiv: 2506.02332 · v2 · submitted 2025-06-03 · 💻 cs.IT · math.IT

Finite-State Dimension and The Davenport ErdH{o}s Theorem

Joe Clanin , Matthew Rayman This is my paper

Pith reviewed 2026-05-19 12:03 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords finite-state dimensionCopeland-Erdős sequenceDavenport-Erdős theoremBorel normalitypolynomial mappingseffective Hausdorff dimensionbase-b concatenation
0
0 comments X

The pith

For any two values s and s' between 0 and 1, a set A and linear polynomial with real coefficients exist so that the finite-state dimensions of CE_b(A) and CE_b(p(A)) equal s and s' respectively.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines the effect of applying a polynomial to a set of natural numbers on the finite-state dimension of the resulting base-b Copeland-Erdős sequence, which is the concatenation of the base-b digits of the numbers in increasing order. It establishes that when the polynomial has arbitrary real coefficients and is linear, the finite-state dimensions of the original and image sequences can be prescribed independently to any pair of values in the unit interval. This builds on the Davenport-Erdős theorem by replacing classical normality with its finite-state dimension characterization and showing that the transformation does not force the dimensions to be equal. The result also holds for strong finite-state dimension and includes contrasting statements for polynomials restricted to rational coefficients.

Core claim

If the polynomial is permitted to have arbitrary real coefficients, then for any s and 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 same holds for strong finite-state dimension. Linear polynomials with rational coefficients leave the finite-state dimension unchanged for every set A, yet polynomials with rational coefficients of every degree greater than one can change the dimension of some sequences. There also exist sets A and integer-valued monomials p such that CE_b(A) is normal while CE_b(p(A)) has finite-state dimension strictly less than one.

What carries the argument

The finite-state dimension of a base-b Copeland-Erdős sequence CE_b(A), which quantifies the effective randomness of the concatenated digit string, together with the action of polynomial evaluation on the underlying set A.

If this is right

  • Linear polynomials with real coefficients allow independent assignment of any two finite-state dimensions to a sequence and its polynomial image.
  • Linear polynomials with rational coefficients preserve finite-state dimension for every input set.
  • Rational polynomials of degree two or higher can alter finite-state dimension for some input sets.
  • Normality of a Copeland-Erdős sequence can fail after applying an integer-valued monomial.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The flexibility under real coefficients suggests that effective dimension behaves more independently under arithmetic maps than classical Hausdorff dimension does.
  • Similar independence might hold for other effective dimensions or for concatenations in non-integer bases.
  • The separation between rational and real coefficients points to a possible role for Diophantine approximation in controlling digit distributions.

Load-bearing premise

Constructions of sets with prescribed finite-state dimension can be chosen so that polynomial evaluation on the set does not introduce extra constraints that link the dimensions of the original and image sequences.

What would settle it

An explicit linear polynomial with real coefficients and a concrete set A for which the finite-state dimension of CE_b(A) equals 0.3 while the finite-state dimension of CE_b(p(A)) cannot be made equal to 0.7.

read the original abstract

A 1952 result of Davenport and Erd\H{o}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\geq 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\geq 2$, the base $b$ Copeland-Erd\H{o}s sequence of $A$, $CE_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 $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^\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 $CE_b(A)$ and $CE_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\H{o}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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript proves existence results showing that for any s, s' in [0,1] there exist a set A of naturals and a linear polynomial p with real coefficients such that fs-dim(CE_b(A)) = s and fs-dim(CE_b(p(A))) = s', with an analogous statement for strong finite-state dimension. It further shows that linear polynomials with rational coefficients preserve finite-state dimension, that rational polynomials of every degree d ≥ 2 can change the dimension for some A, and that there exist A and integer-valued monomials p such that CE_b(A) is normal while CE_b(p(A)) has finite-state dimension strictly less than 1.

Significance. The results extend the classical Davenport-Erdős and Nakai-Shiokawa normality theorems to a quantitative setting via finite-state dimension. The independent control of dimensions under real-coefficient linear maps provides a clean separation that highlights the role of irrational coefficients in breaking arithmetic correlations, while the preservation result for rational linears and the counterexamples for higher-degree and monomial cases give a nuanced picture of when polynomial evaluation affects finite-state compressibility of concatenated sequences.

major comments (2)
  1. [§3] The central existence claim for real-coefficient linear polynomials (stated in the abstract and proved via the construction in §3) requires an explicit decoupling argument: the choice of α must ensure that base-b digit blocks of p(a) realize any prescribed s' independently of the blocks realizing s for A. The manuscript should verify that carry propagation and block-length variation (≈ log_b |α| + log_b a) do not induce joint finite-state constraints when α is irrational.
  2. [§4] Theorem 4.1 (or the corresponding statement on rational polynomials of degree ≥2) asserts that such polynomials can change the dimension for some A; the proof must exhibit a concrete A where the change occurs and confirm that the finite-state dimension drop is not an artifact of the particular concatenation ordering.
minor comments (2)
  1. [§2] Notation for strong finite-state dimension is introduced without an explicit comparison to the ordinary finite-state dimension in the preliminaries; a short paragraph contrasting the two would improve readability.
  2. [§3.1] The statement that 'linear polynomials with rational coefficients do not change the finite-state dimension' should include a brief reference to the relevant prior characterization of normality via finite-state dimension used in the argument.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive major comments. We address each point below and agree to incorporate clarifications that strengthen the rigor of the constructions without altering the main results.

read point-by-point responses

  1. Referee: [§3] The central existence claim for real-coefficient linear polynomials (stated in the abstract and proved via the construction in §3) requires an explicit decoupling argument: the choice of α must ensure that base-b digit blocks of p(a) realize any prescribed s' independently of the blocks realizing s for A. The manuscript should verify that carry propagation and block-length variation (≈ log_b |α| + log_b a) do not induce joint finite-state constraints when α is irrational.

    Authors: We appreciate the referee's emphasis on making the independence explicit. In the §3 construction, α is chosen irrational so that {α a} is dense mod 1; this equidistribution lets us select successive blocks of a to control the leading digits of p(a) independently of those of a. Carry propagation affects only a bounded number of digits and is therefore a finite-state operation that cannot reduce dimension below the target. Block-length variation is O(log a) and the positions of block boundaries are governed by an irrational rotation, which is ergodic and prevents systematic alignments that would create joint finite-state compressibility. We will add a short lemma formalizing these observations in the revised §3. revision: yes

  2. Referee: [§4] Theorem 4.1 (or the corresponding statement on rational polynomials of degree ≥2) asserts that such polynomials can change the dimension for some A; the proof must exhibit a concrete A where the change occurs and confirm that the finite-state dimension drop is not an artifact of the particular concatenation ordering.

    Authors: We agree that an explicit example improves readability. The current proof of Theorem 4.1 proceeds by a recursive construction that forces compressible blocks in CE_b(p(A)) while keeping CE_b(A) normal; we will replace the implicit existence argument with an explicit recursive definition of A (for instance, for p(x)=x^2) that specifies the intervals from which elements are drawn at each stage. Because p has positive leading coefficient and is strictly increasing on the naturals, the ordering of p(A) coincides with the image of the ordering of A, so the concatenation remains the canonical increasing one. The dimension drop is produced by the polynomial map itself, which introduces arithmetic regularities (e.g., quadratic residues in digits) that finite automata can exploit. We will insert a clarifying paragraph on this point in the revision. revision: yes

Circularity Check

0 steps flagged

No significant circularity in existence constructions

full rationale

The paper establishes existence results showing that for linear polynomials with arbitrary real coefficients, any pair of finite-state dimensions s and s' can be realized independently by CE_b(A) and CE_b(p(A)) for suitable A. These are built from prior characterizations of Borel normality via finite-state dimension (explicitly noted as well-known) and explicit constructions separating the digit-block statistics under polynomial evaluation. No load-bearing step reduces a claimed dimension to a fitted parameter, self-definition, or self-citation chain; the rational-coefficient and monomial cases are handled by separate arguments that preserve independence. The derivation remains self-contained against external benchmarks for normality and dimension.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper works entirely within standard definitions of finite-state dimension, Copeland-Erdős sequences, and polynomial evaluation on natural numbers. No new free parameters, ad-hoc axioms, or invented entities are introduced in the abstract.

axioms (2)
  • standard math Finite-state dimension exactly characterizes Borel normality (sequences have FS-dimension 1 iff they are normal).
    Invoked to translate classical normality statements into dimension statements.
  • domain assumption Base-b representations and concatenation behave continuously with respect to finite-state dimension under polynomial mappings.
    Underlying the constructions that relate dim(CE_b(A)) and dim(CE_b(p(A))).

pith-pipeline@v0.9.0 · 5896 in / 1507 out tokens · 54122 ms · 2026-05-19T12:03:15.458133+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. On the normality of the concatenated Fibonacci constant

    math.NT 2026-04 unverdicted novelty 5.0

    Numerical tests on the first 500000 Fibonacci numbers suggest the concatenated constant is normal at tested scales, with any obstruction likely in the asymptotic interior digits of large terms.

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages · cited by 1 Pith paper

  1. [1]

    Normal numbers and computer sci- ence

    Ver´ onica Becher and Olivier Carton. “Normal numbers and computer sci- ence”. In: Sequences, groups, and number theory (2018), pp. 233–269

    work page 2018

  2. [2]

    The asymptotic distribution of the numerals in the decimal representation of the squares of the natural numbers

    Abram S Besicovitch. “The asymptotic distribution of the numerals in the decimal representation of the squares of the natural numbers”. In: Mathematische Zeitschrift 39 (1935), pp. 146–156

    work page 1935

  3. [3]

    Entropy rates and finite-state dimension

    Chris Bourke, John M Hitchcock, and NV Vinodchandran. “Entropy rates and finite-state dimension”. In:Theoretical Computer Science349.3 (2005), pp. 392–406

    work page 2005

  4. [4]

    Distribution modulo one and Diophantine approximation

    Yann Bugeaud. Distribution modulo one and Diophantine approximation . Vol. 193. Cambridge University Press, 2012

    work page 2012

  5. [5]

    The construction of decimals normal in the scale of ten

    David G Champernowne. “The construction of decimals normal in the scale of ten”. In: Journal of the London Mathematical Society 1.4 (1933), pp. 254–260

    work page 1933

  6. [6]

    Note on normal numbers

    Arthur H Copeland and Paul Erd¨ os. “Note on normal numbers”. In: Bull. Amer. Math. Soc. 52.12 (1946), pp. 857–860

    work page 1946

  7. [7]

    Finite-state dimension

    Jack J Dai et al. “Finite-state dimension”. In: Theoretical Computer Sci- ence 310.1-3 (2004), pp. 1–33

    work page 2004

  8. [8]

    Note on normal decimals

    Harold Davenport and Paul Erd¨ os. “Note on normal decimals”. In: Cana- dian Journal of Mathematics 4 (1952), pp. 58–63

    work page 1952

  9. [9]

    On a problem on normal num- bers raised by Igor Shparlinski

    Jean-Marie De Koninck and Imre Katai. “On a problem on normal num- bers raised by Igor Shparlinski”. In: Bulletin of the Australian Mathemat- ical Society 84.2 (2011), pp. 337–349. 12

    work page 2011

  10. [10]

    Finite-state di- mension and real arithmetic

    David Doty, Jack H Lutz, and Satyadev Nandakumar. “Finite-state di- mension and real arithmetic”. In: Information and Computation 205.11 (2007), pp. 1640–1651

    work page 2007

  11. [11]

    Zeta-Dimension: (Preliminary Version)

    David Doty et al. “Zeta-Dimension: (Preliminary Version)”. In: Mathe- matical Foundations of Computer Science 2005: 30th International Sym- posium, MFCS 2005, Gdansk, Poland, August 29–September 2, 2005. Pro- ceedings 30. Springer. 2005, pp. 283–294

    work page 2005

  12. [12]

    Les probabilit´ es d´ enombrables et leurs applications arithm´ etiques

    M ´Emile Borel. “Les probabilit´ es d´ enombrables et leurs applications arithm´ etiques”. In: Rendiconti del Circolo Matematico di Palermo (1884-1940)27.1 (1909), pp. 247–271

    work page 1940

  13. [13]

    Dimensions of Copeland- Erd¨ os sequences

    Xiaoyang Gu, Jack H Lutz, and Philippe Moser. “Dimensions of Copeland- Erd¨ os sequences”. In:FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science: 25th International Conference, Hy- derabad, India, December 15-18, 2005. Proceedings 25 . Springer. 2005, pp. 250–260

    work page 2005

  14. [14]

    Fractal dimension and logarithmic loss unpredictabil- ity

    John M Hitchcock. “Fractal dimension and logarithmic loss unpredictabil- ity”. In: Theoretical Computer Science 304.1-3 (2003), pp. 431–441

    work page 2003

  15. [15]

    Automatic Kolmogorov complexity, normality, and finite-state dimension revisited

    Alexander Kozachinskiy and Alexander Shen. “Automatic Kolmogorov complexity, normality, and finite-state dimension revisited”. In: Journal of Computer and System Sciences 118 (2021), pp. 75–107

    work page 2021

  16. [16]

    Two characterizations of finite-state dimension

    Alexander Kozachinskiy and Alexander Shen. “Two characterizations of finite-state dimension”. In: Fundamentals of Computation Theory: 22nd International Symposium, FCT 2019, Copenhagen, Denmark, August 12- 14, 2019, Proceedings 22. Springer. 2019, pp. 80–94

    work page 2019

  17. [17]

    The dimensions of individual strings and sequences

    Jack H Lutz. “The dimensions of individual strings and sequences”. In: Information and Computation 187.1 (2003), pp. 49–79

    work page 2003

  18. [18]

    Nor- mality of numbers generated by the values of entire functions

    Manfred G Madritsch, J¨ org M Thuswaldner, and Robert F Tichy. “Nor- mality of numbers generated by the values of entire functions”. In:Journal of number theory 128.5 (2008), pp. 1127–1145

    work page 2008

  19. [19]

    A Kolmogorov complexity characterization of con- structive Hausdorff dimension

    Elvira Mayordomo. “A Kolmogorov complexity characterization of con- structive Hausdorff dimension”. In: Information Processing Letters 84.1 (2002), pp. 1–3

    work page 2002

  20. [20]

    A class of normal numbers, II

    YN Nakai and Iekata Shiokawa. “A class of normal numbers, II”. In: Lon- don Math. Soc. Lecture Note Ser 154 (1990), pp. 204–210

    work page 1990

  21. [21]

    A class of normal numbers To the memory of Isamu Kobayashi

    Yoshinobu Nakai and Iekata Shiokawa. “A class of normal numbers To the memory of Isamu Kobayashi”. In: Japanese journal of mathematics. New series 16.1 (1990), pp. 17–29

    work page 1990

  22. [22]

    Besicovitch, Bisection, and the Nor- mality of 0.(1)(4)(9)(16)(25)

    Paul Pollack and Joseph Vandehey. “Besicovitch, Bisection, and the Nor- mality of 0.(1)(4)(9)(16)(25). . . ” In:The American Mathematical Monthly 122.8 (2015), pp. 757–765. 13

    work page 2015

  23. [23]

    Some normal numbers generated by arithmetic functions

    Paul Pollack and Joseph Vandehey. “Some normal numbers generated by arithmetic functions”. In: Canadian Mathematical Bulletin 58.1 (2015), pp. 160–173

    work page 2015

  24. [24]

    Endliche automaten und zu- fallsfolgen

    Claus-Peter Schnorr and Hermann Stimm. “Endliche automaten und zu- fallsfolgen”. In: Acta Informatica 1 (1972), pp. 345–359

    work page 1972

  25. [25]

    A remark on a theorem of Copeland-Erd¨ os

    Iekata Shiokawa. “A remark on a theorem of Copeland-Erd¨ os”. In: Pro- ceedings of the Japan Academy 50.4 (1974), pp. 273–276

    work page 1974

  26. [26]

    A combinatorial method for construct- ing normal numbers

    Peter Sz¨ usz and Bodo Volkmann. “A combinatorial method for construct- ing normal numbers”. In: (1994)

    work page 1994

  27. [27]

    Normal numbers

    Donald Dines Wall. Normal numbers. University of California, Berkeley, 1949. 14

    work page 1949