# Computing Absolutely Normal Numbers in Nearly Linear Time

@article{Lutz2016ComputingAN, title={Computing Absolutely Normal Numbers in Nearly Linear Time}, author={Jack H. Lutz and Elvira Mayordomo}, journal={ArXiv}, year={2016}, volume={abs/1611.05911} }

A real number $x$ is absolutely normal if, for every base $b\ge 2$, every two equally long strings of digits appear with equal asymptotic frequency in the base-$b$ expansion of $x$. This paper presents an explicit algorithm that generates the binary expansion of an absolutely normal number $x$, with the $n$th bit of $x$ appearing after $n$polylog$(n)$ computation steps. This speed is achieved by simultaneously computing and diagonalizing against a martingale that incorporates Lempel-Ziv parsing… Expand

#### Figures and Topics from this paper

#### 9 Citations

Normal Numbers and Computer Science

- Computer Science
- 2018

This chapter is an introduction to the theory of normal numbers and proves Agafonov’s theorem, which establishes that a number is normal to a given base exactly when its expansion in that base is such that every subsequence selected by a finite automaton is also normal. Expand

On the continued fraction expansion of absolutely normal numbers

- Mathematics
- 2017

We construct an absolutely normal number whose continued fraction expansion is normal in the sense that it contains all finite patterns of partial quotients with the expected asymptotic frequency as… Expand

Lempel-Ziv: a "one-bit catastrophe" but not a tragedy

- Computer Science, Mathematics
- SODA
- 2018

The so-called "one-bit catastrophe" for the compression algorithm LZ'78 asks whether the compression ratio of an infinite word can change when a single bit is added in front of it. We answer… Expand

Asymptotic Divergences and Strong Dichotomy

- Mathematics, Computer Science
- STACS
- 2020

The main theorem is a $\textit{strong dichotomy theorem}$ that uses the Kullback-Leibler divergence to quantify the exponential rates of winning and losing on the two sides of the Schnorr-Stimm dichotomy criterion. Expand

I T ] 3 0 O ct 2 01 9 Asymptotic Divergences and Strong Dichotomy ∗ †

- 2019

The Schnorr-Stimm dichotomy theorem [31] concerns finite-state gamblers that bet on infinite sequences of symbols taken from a finite alphabet Σ. The theorem asserts that, for any such sequence S,… Expand

Finite-state Independence and Normal Sequences

- Computer Science
- J. Comput. Syst. Sci.
- 2019

This work characterize finite-state independence of normal words in three different ways, using three different kinds of asynchronous deterministic finite automata with two input tapes containing infinite words. Expand

2017 EUROPEAN SUMMER MEETING OF THE ASSOCIATION FOR SYMBOLIC LOGIC LOGIC COLLOQUIUM ’17 Stockholm, Sweden August 14–20, 2017

- The Bulletin of Symbolic Logic
- 2018

s of invited and contributed talks given in person or by title by members of the Association follow. For the Program Committee Mirna Džamonja Abstracts of Invited Talkss of Invited Talks DAVID… Expand

Contributions to arithmetic complexity and compression

- Mathematics
- 2018

Cette these explore deux territoires distincts de l’informatique fondamentale : la complexite et la compression. Plus precisement, dans une premiere partie, nous etudions la puissance des circuits… Expand

Algorithmic Fractal Dimensions in Geometric Measure Theory

- Computer Science, Mathematics
- ArXiv
- 2020

This work survey's developments, with emphasis on connections with computable functions on the reals, recent uses of algorithmic dimensions in proving new theorems in classical (non-algorithmic) fractal geometry, and directions for future research. Expand

#### References

SHOWING 1-10 OF 52 REFERENCES

On the construction of absolutely normal numbers

- Mathematics
- 2017

We give a construction of an absolutely normal real number $x$ such that for every integer $b $ greater than or equal to $2$, the discrepancy of the first $N$ terms of the sequence $(b^n x \mod… Expand

A polynomial-time algorithm for computing absolutely normal numbers

- Computer Science, Mathematics
- Inf. Comput.
- 2013

We give an algorithm to compute an absolutely normal number so that the first n digits in its binary expansion are obtained in time polynomial in n; in fact, just above quadratic. The algorithm uses… Expand

Note on normal numbers

- Mathematics
- 1946

was normal (in the sense of Borel) with respect to the base 10, a normal number being one whose digits exhibit a complete randomness. More precisely a number is normal provided each of the digits 0,… Expand

Turing's unpublished algorithm for normal numbers

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 2007

In an unpublished manuscript, Alan Turing gave a computable construction to show that absolutely normal real numbers between 0 and 1 have Lebesgue measure 1; furthermore, he gave an algorithm for… Expand

Nearly Linear Time

- Computer Science
- Logic at Botik
- 1989

This work introduces a class NLT of functions computable in nearly linear time n(log n)O(1) on random access computers and gives also a machine-independent definition of NLT and a natural problem complete for NLT. Expand

Distribution Modulo One and Diophantine Approximation

- Mathematics
- 2012

1. Distribution modulo one 2. On the fractional parts of powers of real numbers 3. On the fractional parts of powers of algebraic numbers 4. Normal numbers 5. Further explicit constructions of normal… Expand

Why Computational Complexity Requires Stricter Martingales

- Mathematics, Computer Science
- ICALP
- 2002

This paper elucidates the relationship between these notions and proves that the latter notion is too weak for many purposes in computational complexity, b ecause under this definition every computable martingale can be simulated by a polynomial-time computableMartingale. Expand

Series Feasible Analysis , Randomness , and Base Invariance

- 2013

We show that polynomial time randomness of a real number does not depend on the choice of a base for representing it. Our main tool is an ‘almost Lipschitz’ condition that we show for the cumulative… Expand

Feasible Analysis, Randomness, and Base Invariance

- Mathematics, Computer Science
- Theory of Computing Systems
- 2013

It is shown that polynomial time randomness of a real number does not depend on the choice of a base for representing it, and it is proved that for any base r, n⋅log2n-randomness in base r implies normality in base r, and that n4- randomness inbase r implies absolute normality. Expand

Computable Absolutely Pisot Normal Numbers

- Mathematics
- 2016

We analyze the convergence order of an algorithm producing the digits of an absolutely normal number. Furthermore, we introduce a stronger concept of absolute normality by allowing Pisot numbers as… Expand