On a Question of Becher and Slaman: For Kurtz Random x the Discrepancy of (2^n x) Is Not O((log N)/N)

In Oberwolfach Report 1/2018, Becher and Slaman ask whether some Martin-Löf random real x has discrepancy D_N((2^n x)_{n≥1}) = O((log N)/N) for all large N. Read as asking for constants C, N_0 with N D_N ≤ C log N for all N ≥ N_0, the question has a negative answer, also for Schnorr, computably and Kurtz random x. More precisely, if x is Kurtz random and g is computable with limsup_N g(N)/√(N log log N) < 1/√2, for instance any computable g(N) = o(√(N log log N)), then N D_N > g(N) for infinitely many N; in particular limsup_N N D_N/√(N log log N) ≥ 1/√2. We give two short proofs of the negative answer. The first combines Koksma's inequality for e^{2πit}, the law of the iterated logarithm of Erdős and Gál for lacunary exponential sums, and the fact that a null effectively closed set contains no Kurtz random real; it gives the constant 1/(2π) in place of 1/√2. The second replaces these analytic tools by the observation that {2^n x} < 1/2 exactly when the (n+1)st binary digit of x is 0, so that N D_N is at least the deviation from N/2 of a count of zeros; a binomial estimate then gives the negative answer, and Khinchin's law of the iterated logarithm gives the constant 1/√2. For Martin-Löf random x the negative answer follows at once from this digit count and Vovk's law of the iterated logarithm for Martin-Löf random sequences; the note records a short observation from known results, which may be folklore. The question is due to Becher and Slaman, and the tools are classical. We do not treat the variant with "for infinitely many N", nor Korobov's question on the existence of a normal number with discrepancy O((log N)/N), which the source connects with the question, nor the other questions of the problem session. This is an unrefereed note. Unrefereed preprint released for independent mathematical scrutiny. Publication on Zenodo does not constitute peer review. AI-assisted tools supported research, computation, proof development, and manuscript preparation. The author remains responsible for all claims and the final text. Corpus identifiers: OWR-15986-005, OWR-15986-006 (Question 1 of each; Becher and Slaman, Open problems, Oberwolfach Report 1/2018, p. 34).

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-10-15
DOI
https://doi.org/10.5281/zenodo.23400058
Primary Topic
Computability, Logic, AI Algorithms
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
preprint

On a Question of Becher and Slaman: For Kurtz Random x the Discrepancy of (2^n x) Is Not O((log N)/N)

Alper Ferudun
Zenodo (CERN European Organization for Nuclear Research)
Computability, Logic, AI Algorithms
preprint

On a Question of Becher and Slaman: For Kurtz Random x the Discrepancy of (2^n x) Is Not O((log N)/N)

Alper Ferudun
preprint en

Abstract

In Oberwolfach Report 1/2018, Becher and Slaman ask whether some Martin-Löf random real x has discrepancy D_N((2^n x)_{n≥1}) = O((log N)/N) for all large N. Read as asking for constants C, N_0 with N D_N ≤ C log N for all N ≥ N_0, the question has a negative answer, also for Schnorr, computably and Kurtz random x. More precisely, if x is Kurtz random and g is computable with limsup_N g(N)/√(N log log N) < 1/√2, for instance any computable g(N) = o(√(N log log N)), then N D_N > g(N) for infinitely many N; in particular limsup_N N D_N/√(N log log N) ≥ 1/√2. We give two short proofs of the negative answer. The first combines Koksma's inequality for e^{2πit}, the law of the iterated logarithm of Erdős and Gál for lacunary exponential sums, and the fact that a null effectively closed set contains no Kurtz random real; it gives the constant 1/(2π) in place of 1/√2. The second replaces these analytic tools by the observation that {2^n x} < 1/2 exactly when the (n+1)st binary digit of x is 0, so that N D_N is at least the deviation from N/2 of a count of zeros; a binomial estimate then gives the negative answer, and Khinchin's law of the iterated logarithm gives the constant 1/√2. For Martin-Löf random x the negative answer follows at once from this digit count and Vovk's law of the iterated logarithm for Martin-Löf random sequences; the note records a short observation from known results, which may be folklore. The question is due to Becher and Slaman, and the tools are classical. We do not treat the variant with "for infinitely many N", nor Korobov's question on the existence of a normal number with discrepancy O((log N)/N), which the source connects with the question, nor the other questions of the problem session. This is an unrefereed note. Unrefereed preprint released for independent mathematical scrutiny. Publication on Zenodo does not constitute peer review. AI-assisted tools supported research, computation, proof development, and manuscript preparation. The author remains responsible for all claims and the final text. Corpus identifiers: OWR-15986-005, OWR-15986-006 (Question 1 of each; Becher and Slaman, Open problems, Oberwolfach Report 1/2018, p. 34).

Zenodo (CERN European Organization for Nuclear Research)
Computability, Logic, AI Algorithms
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.