# Verification report — OWR-15986-005 (Becher–Slaman, Question 1: discrepancy of (2^n x) for a Martin-Löf random x)

Verification date: 2026-10-15.

**Verdict.** The note answers Question 1 of Becher and Slaman (Oberwolfach Report 1/2018, p. 34) in the
**negative**, under the reading stated below; every statement it makes is proved.
- **Settled.** No Kurtz random real x (hence no Schnorr, computably or Martin-Löf random real) has
  N·D_N((2^n x)_{n≥1}) = O(log N) (Theorem 1.1). More precisely, for Kurtz random x and every computable g with
  limsup g(N)/sqrt(N log log N) < 1/√2, N·D_N > g(N) for infinitely many N; hence
  limsup N·D_N/sqrt(N log log N) ≥ 1/√2 (Theorem 1.2).
- **Not new in substance.** For Martin-Löf random x the answer follows at once from Vovk's law of the iterated
  logarithm for Martin-Löf random sequences (Theory Probab. Appl. 32, 1987, doi:10.1137/1132061) and the
  elementary digit count N·D_N ≥ |#{2 ≤ j ≤ N+1 : b_j = 0} − N/2| (Lemma 2.2, Corollary 5.3). The note presents the
  result as a short observation from known results, possibly folklore; no printed statement of it was found.
- **Not treated.** The variant with "for infinitely many N"; Korobov's question on the existence of a normal
  number with discrepancy O((log N)/N), which the source connects with the question (an answer to Question 1
  "will also answer" it; this holds for a positive answer only); upper bounds for Martin-Löf random reals and the
  sharp constant;
  item (2) of the same problem session (Jockusch, Hindman's theorem HT^{=n}_2), which forms the second half of
  record OWR-15986-005; the second half of record OWR-15986-006 (Knight, Scott sentences).

The note is unrefereed.

## Statement checked
- **Primary source.** V. Becher, T. Slaman, C. Jockusch, J. Knight, S. Lempp, A. Nies, A. Pauly, L. Yu,
  "Open problems", in *Computability Theory*, Oberwolfach Report No. 1/2018 (workshop 7–13 January 2018;
  reporter M.-C. Ho), Oberwolfach Reports 15 (2018), no. 1, pp. 34–36, doi:10.4171/OWR/2018/1 (Crossref: issue
  dated 4 January 2019, pp. 5–41).
  - Read in the publisher's open PDF (ems.press, serial-article-files/46723; 368,027 bytes, sha256
    `eb4f91fadc784f8a41e99a43871b333fa44a14377d9b8deeac0f05bcbdd604fa`), fetched on 2026-10-15.
  - Problem (1) (Becher and Slaman): the definition D_N((x_n)) = sup over 0 ≤ a < b < 1 of
    |(1/N)#{n ≤ N : {x_n} ∈ [a,b)} − (b − a)|, then Question 1: whether there is a Martin-Löf random real x such
    that, "for every N large enough", D_N((2^n x)_{n≥1}) is O((log N)/N); then the remark that an answer would
    also answer Korobov's question (1956) on a normal number with this discrepancy.
  - Becher's abstract in the same report (pp. 16–18) defines Martin-Löf tests with Lebesgue measure.
- **Corpus records.** ulamai/UnsolvedMath OWR-15986-005 = problem (1) + problem (2) (Jockusch) of that section;
  OWR-15986-006 = problem (1) + problem (3) (Knight). The note answers problem (1) only.

## Readings
| Reading | Answer | Where |
|---|---|---|
| (Q) Are there a Martin-Löf random x and C > 0, N_0 with N D_N(x) ≤ C log N for all N ≥ N_0? (the eventual bound; "for every N large enough" and the O-symbol say the same) | no; also for Kurtz random x | Theorems 1.1, 1.2 |
| The same with star discrepancy, closed intervals, b ≤ 1, indexing from n = 0, another base of the logarithm | no (constants change only) | Section 1.1 |
| The same for Schnorr or computably random x | no (both imply Kurtz randomness) | Section 3 |
| Bound required only for infinitely many N | not treated | Remark 6.2 |
| Korobov's question (normal x with D_N = O((log N)/N)) | not treated; such x, if it exists, is not Kurtz random | Remark 6.4 |
| Randomness with respect to another measure | not the source's meaning (Becher's abstract fixes Lebesgue measure); not treated | Section 1.1 |

## Results in the paper
- **Lemma 2.1, Lemma 2.2 (digit count), Lemma 2.3 (Koksma).** D*_N ≤ D_N; {2^n x} < 1/2 iff b_{n+1} = 0, hence
  N D_N ≥ N D*_N ≥ |Z_N − N/2| with Z_N = #{2 ≤ j ≤ N+1 : b_j = 0}; |E_N| ≤ 2π N D*_N for
  E_N = Σ_{n≤N} e^{2πi 2^n x}. All proved in full.
- **Lemma 3.1.** A null Π^0_1 class contains no Martin-Löf random real (explicit Martin-Löf test); a computable
  real is not Kurtz random.
- **Section 4 (first proof).** Theorem 4.1 = Erdős–Gál (1955), Theorem in the Introduction, cited (hypothesis
  n_{ν+1}/n_ν ≥ q > 1; only "≥ 1" is used, for n_ν = 2^ν). Lemma 4.2: F_g(N_0) = {x : |E_N(x)| ≤ g(N) ∀N ≥ N_0}
  is Π^0_1 for computable g (explicit enumeration with the Lipschitz bound 2π·2^{N+1}). Lemma 4.3: null if
  limsup g/sqrt(N log log N) < 1. Gives Theorem 1.1 and Theorem 1.2 with 1/(2π) in place of 1/√2.
- **Section 5 (second proof).** Lemma 5.1: the digit class P_g(N_0) (closed dyadic intervals of words with
  |z(w) − N/2| ≤ g(N)) is Π^0_1 and contains every non-dyadic x with N D_N ≤ g(N) for N ≥ N_0. Lemma 5.2:
  (a) null if (2g(N)+1)/sqrt(N+1) → 0 (P_N is empty when g(N) < 0), by the elementary bound
  binom(2m,m)4^{-m} ≤ (2m+1)^{-1/2} (proved);
  (b) null if limsup g/sqrt(N log log N) < 1/√2, by Khinchin's law of the iterated logarithm (cited, in the form
  of Pancia, arXiv:1410.1859, Theorem 3.4). Gives Theorem 1.1 without any law of the iterated logarithm and
  Theorem 1.2 with 1/√2. Corollary 5.3: for Martin-Löf random x directly from Vovk's theorem (in the form of
  Pancia, Theorem 3.5).
- **Remarks.** Other computable lacunary integer sequences (first proof); the quantifier; no upper bounds
  (Kurtz random reals may violate the law of large numbers); Levin's computable normal numbers and Schmidt's
  lower bound are consistent with the theorems; open questions.

## Computations (sanity checks; programs and outputs in reproducibility/)
No proof depends on a computation.
- **The program of the note** (`check_note.py`, standard library, about 30 s; 16 checks, TOTAL failures: 0):
  (i) the closed formulas for D_N and D*_N against the definitions, exactly, on 360 point sets (formula without
  1/N rejected on 60/60); (ii) Koksma (|E| ≤ 2π N D*, largest ratio 2.230) and its cosine form on 3000 point
  sets; for {2^n x} on 200 pairs (x, N), N ≤ 4096: exactly, the digit identity, N D*_N ≥ |Z_N − N/2| and
  D*_N ≤ D_N ≤ 2D*_N, and |E_N| ≤ 2π N D*_N with E_N in floating point; (iii) illustration only, 24 pseudo-random x, N = 2^10..2^20: mean
  N D_N/log N from 5.0 to 94.1; N D_N/sqrt(N log log N): means 0.716–0.860, min 0.383, max 1.577;
  (iv) binom(2m,m)^2(2m+1) ≤ 16^m for m ≤ 3000 and the bound of Lemma 5.2(a) in eight cases.
- **Original program** (`original/sanity_numerics.py`, numpy, about 7 s): 60 random x, N = 2^10..2^20; 0 Koksma
  violations on 660 pairs; N D_N/log N from 5.4 to 92 (means), N D_N/sqrt(N log log N) means 0.75–0.86, maxima up
  to 1.762 (minima 0.29–0.43, printed by a copy in run A).
- **Run A** (`verification_run_A/`): formulas vs exact brute force (400 sets); Koksma-type inequalities on 3000
  sets; digit count on 200 pairs with 64-bit windows; dyadic examples; exact integrals; the enumeration of
  Lemma 4.2 for N = 3..6 (69,200 soundness points, 240 completeness points, 0 failures); exact binomial
  probabilities; a dynamic-programming measure of the digit class.
- **Run B** (`verification_run_B/`): discrepancy routines vs an O(N^2) brute force (300 sets); 660 pairs with its
  own seed (Koksma, star/extreme, digit count: 0 violations); Lipschitz constant of E_N; controls (x = 1/2, 1/3,
  van der Corput, golden ratio); deliberately wrong inputs (all flagged); exact sympy identities.
- **Run 3** (`independent_run_2/`, written for the final text): an exact supremum method for D_N and D*_N by
  cells of constant count (540 point sets; the closed formulas of Section 7 agree, the formula without 1/N is
  rejected 60/60); Lemmas 2.1–2.3 on {2^n x} for 86 rational x (dyadic and non-dyadic), the identity behind
  Lemma 2.3 (deviation 2e-14), Lemma 2.2 exactly in integers up to N = 16384, the index-shift remark of
  Section 1.1; binom(2m,m)^2(2m+1) ≤ 16^m for m ≤ 20000 and the steps of its proof; Lemma 5.1(d) and Lemma 5.2(a)
  exactly; the construction of Lemma 3.1(a) carried out exactly for the middle-third Cantor set (k ≤ 9); the
  enumeration of Lemma 4.2 with the worst admissible approximations (soundness on 127,100 intervals, completeness
  on 24,662 points; a control with the Lipschitz constant L_N/64 fails as it must); the constants; an
  illustration with its own seed (sample means of N D_N/sqrt(N log log N) 0.73–0.96, min 0.35, max 1.63).
- **Re-runs (2026-10-15).** All eight programs of `original/` and of the two runs were run again from the
  package copies: outputs identical to the recorded ones apart from timing lines. `check_note.py` re-run:
  identical apart from the time line. Run 3 re-ran all of them once more from an unpacked copy of the version-1
  source archive: all 11 recorded outputs reproduced (6 byte for byte, 5 apart from timing lines).

## Independent verification runs
Two independent verification runs, both AI-assisted, examined the first written version of the result
(2026-10-15); each read the source, re-derived the proofs, wrote its own programs and re-ran the original
program (identical output).

| Item | Run A | Run B |
|---|---|---|
| Statement, reading (Q), composite record | CONFIRMED (source read) | CONFIRMED (source read) |
| Lemma 2.3 (Koksma for e^{2πit}) | CONFIRMED (re-derived; sharper constant 4 noted) | CONFIRMED (re-derived; 4√2 noted) |
| Erdős–Gál statement and normalisation | CONFIRMED (via zbMATH Zbl 0068.05403) | CONFIRMED (original, p. 65) |
| Lemma 4.2 (Π^0_1), Lemma 4.3, Lemma 3.1 | CONFIRMED (re-derived; enumeration tested) | CONFIRMED (re-derived; Lipschitz constant tested) |
| Theorem 1.1 | CONFIRMED | CONFIRMED |
| Theorem 1.2, main statement and limsup bound | CONFIRMED | CONFIRMED |
| Theorem 1.2, clause "not O(sqrt(N log log N)/7)" of the first version | FALSE as written (contradicts Philipp/Fukuyama a.e.) | — |
| Digit-count proof (constant 1/√2) and the Vovk corollary | found independently | found independently |
| Sources and bibliography | CONFIRMED with minor fixes | CONFIRMED (all references resolve; minor fixes) |
| Literature and novelty | no printed answer found; "folklore-level" | no printed answer found; Becher 2021 slides and BIRS 23w5039 (2023) list the question (or a stronger form) as open |

No run found an error in the proof of Theorem 1.1.

**Corrections required by the runs, all applied in the note:**
1. (A) The false clause of Theorem 1.2 was removed. Theorem 1.2 now states that N D_N > c sqrt(N log log N) for
   infinitely many N, for every rational c < 1/√2 (for instance c = 1/7), and the text after it says that
   N D_N/sqrt(N log log N) has the finite upper limit √84/9 for almost every x (Fukuyama), so no unboundedness
   is claimed.
2. (A, B) The digit count (Lemma 2.2), the second proof (Section 5) with the constant 1/√2, and Corollary 5.3:
   for Martin-Löf random x the answer follows at once from Vovk's theorem. Abstract, introduction and "Scope and
   priority" say so.
3. (A) The numerical statements describe means, minima and maxima correctly (Section 7).
4. (A) The garbled sentence on small N of the first version is not used.
5. (A) Becher–Scheerer–Slaman (arXiv:1702.04072) and Aistleitner–Becher–Scheerer–Slaman (Acta Arith. 180 (2017))
   are cited separately; the almost-everywhere laws are attributed as quoted in ABSS (Section 1); no statement
   "the limsup is positive a.e." is attributed to Philipp.
6. (A) Becher–Grigorieff: Information and Computation 285 (2022), 104857.
7. (A) Neutral statement: the source says an answer would also answer Korobov's question; the negative answer
   leaves it open.
8. (A, optional) Erdős–Gál cited with Zbl 0068.05403 and both DOIs; the better constant 1/√2 is used.
9. (B) Becher's CTA talk of 9 March 2021 (slide 20) and the IASM–BIRS report 23w5039 (October 2023, p. 2) are
   cited as the latest public statements that leave the question open; DOIs of Erdős–Gál I/II and Gál–Gál added.

## Third independent verification run (final text, 2026-10-15)

A third independent verification run, AI-assisted, examined the written note (version 1) and this package as if
nothing had been checked before. It read the source again (OWR 1/2018 pp. 16–18 and 34–36, the publisher's PDF),
p. 65 of Erdős–Gál in the original (rendered page), Pancia (arXiv:1410.1859v2: Theorems 2.2, 3.4, 3.5, Lemma 3.1),
ABSS Section 1, BSS pp. 1–2, Avigad Section 2, Becher's slides 17–21 and the BIRS report pp. 1–3; re-derived every
proof line by line; wrote its own programs (`independent_run_2/`); re-ran the whole package from the source
archive; checked all 15 DOIs with Crossref and two reviews with zbMATH; and repeated the literature search.

| Item | Verdict |
|---|---|
| Statement and reading (Q), Korobov remark, Lebesgue measure (p. 17) | CONFIRMED |
| Lemma 2.1, Lemma 2.2, Lemma 2.3, index-shift remark | CONFIRMED (re-derived; tested exactly) |
| Lemma 3.1(a), (b) | CONFIRMED (re-derived; construction carried out for the Cantor set) |
| Theorem 4.1 (Erdős–Gál) as stated; Lemmas 4.2, 4.3; first proof | CONFIRMED (hypothesis ≥ q > 1 seen on p. 65; enumeration tested, with a failing control) |
| Lemma 5.1; Lemma 5.2(b); second proof; Corollary 5.3; the constant 1/√2 | CONFIRMED |
| Lemma 5.2(a) and the bound binom(2m,m)4^{-m} ≤ (2m+1)^{-1/2} | CONFIRMED; the proof did not treat g(N) < 0 (P_N then empty) — corrected |
| Cited statements (Pancia, ABSS, BSS, Avigad, Becher 2021, BIRS 2023) | CONFIRMED, except that Avigad's Section 2 states ML ⇒ Schnorr ⇒ Kurtz only — citation restricted |
| Package (re-run from the archive) | all 11 recorded outputs reproduced |
| Literature and novelty | no printed answer found; claim "short observation from known results, may be folklore" appropriate |

It found no mathematical error. **Corrections required by run 3, all applied in the note:**
1. Abstract: it states that the first proof gives the constant 1/(2π) and the second 1/√2, and describes
   Korobov's question as the source does (an answer to Question 1 "will also answer" it), instead of saying that
   Korobov's question motivated Question 1.
2. Section 1.2: log is the natural logarithm; the constants 1/√2, 1/(2π) and √84/9 refer to it.
3. Lemma 5.2(a): "for instance if 0 ≤ g(N) ≤ K log N + 1"; the proof first disposes of g(N) < 0 (P_N = ∅); the
   second proof of Theorem 1.1 notes 0 ≤ g′(N) ≤ C′ log N + 1.
4. Section 3: the reference to Avigad (Section 2) is restricted to the implications ML ⇒ Schnorr ⇒ Kurtz.
5. Section 7: Lemma 2.3 is tested on {2^n x} with E_N in floating point; the sample means are 0.72–0.86; the
   package holds the programs of three runs.
6. This run is recorded in the Verification paragraph and in "Scope and priority", here, and in
   `reproducibility/independent_run_2/`.
Also applied (optional): Lemma 3.1(a) says that V_k is intersected with [0,1].

## Relation to the literature, novelty and scope
- **Searches (2026-10-15).** By the two runs: arXiv API (discrepancy with Martin-Löf/Kurtz/Schnorr randomness,
  algorithmic randomness, random reals; normal numbers and Korobov; the law of the iterated logarithm for
  lacunary sequences and for algorithmically random sequences; the proposers), Crossref, OpenAlex (no work cites
  the report), zbMATH, Semantic Scholar (rate-limited), Becher's publication list, her talk slides of 2018 and
  2021, the Oberwolfach report 21/2021 and the IASM–BIRS report 23w5039, and four web searches. When the note
  was written: five further arXiv API queries (one failed with a connection reset). By run 3: six arXiv API
  queries (one, for the author Becher, returned nothing), OpenAlex (the report still has no citing work), Crossref and zbMATH keyword searches, the zbMATH list of
  Becher's works 2022–2026, the full text of the survey of lacunary sequences by Aistleitner, Berkes and Tichy
  (arXiv:2301.05561), and one web search. No printed statement of the negative answer was found. A search that
  finds nothing is not a proof of novelty; no priority is claimed.
- **What was read.** The source (pp. 16–18, 34–36); Erdős–Gál (1955) p. 65 and the zbMATH review; ABSS (2017)
  Section 1 and BSS (2017) pp. 1–2 (arXiv), for the statements of Gál–Gál, Philipp, Fukuyama, Levin, Schmidt and
  Korobov's question; Pancia (arXiv:1410.1859), Theorems 2.2, 3.4, 3.5 and Lemma 3.1; Avigad (arXiv:1203.4126)
  Section 2; Becher's 2021 slides 17–21; the BIRS report pp. 1–3. Not read: Gál–Gál, Philipp, Fukuyama, Levin,
  Schmidt, Korobov, Khinchin, Vovk, Kuipers–Niederreiter, Downey–Hirschfeldt, Nies (statements taken from the
  sources named; for Vovk also the zbMATH review Zbl 0645.60006); Becher–Grigorieff only the abstract. The proofs
  of the cited theorems were not checked.
- **Caveats.** The source remarks that an answer to Question 1 would answer Korobov's question; this holds only
  for a positive answer, and the note says so neutrally. The record's second question (Jockusch) and the second
  half of OWR-15986-006 (Knight) are untouched.
- **Scope.** The note answers Question 1 as printed (reading (Q)). The question is Becher's and Slaman's; the
  tools are classical (Koksma; Erdős–Gál; Khinchin; Vovk; null Π^0_1 classes and Kurtz randomness from the
  standard texts).

## Public release and license
This paper, its source files, and this verification report are licensed under the Creative Commons Attribution
4.0 International License (CC BY 4.0): https://creativecommons.org/licenses/by/4.0/