Skip to content

Erdős Problem #255

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (not automatically the live result).
Subject areas: discrepancy.

Read this status correctly

The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.

Documentary explanation. Editorial acceptance is determined by the protected V2 admissions ledger and the exact manuscript source hash. This article does not confer mathematical certification.

The question in plain language

Take any infinite sequence of points \(z_1,z_2,\ldots\) in the unit interval. For an interval \(I\subseteq[0,1]\), compare the number of the first \(N\) points that fall in \(I\) with the idealized number \(N|I|\), where \(|I|\) is the interval's length. The discrepancy is

\[ D_N(I)=\#\{n\leq N:z_n\in I\}-N|I|. \]

Erdős Problem 255 asks whether

\[ \forall (z_n)_{n\geq1}\in[0,1]^{\mathbb N}\;\exists\, I\subseteq[0,1]:\quad \limsup_{N\to\infty}|D_N(I)|=\infty. \]

The interval must be chosen once, after seeing the whole sequence. This is stronger than saying that for every \(N\) there is some convenient interval \(I_N\); an interval that changes with \(N\) would not answer the problem. A half-open convention, such as \(I=[0,x)\), is useful because it fixes what happens when a point lies at an endpoint.

Erdős stated the original version on the unit circle: for every sequence of points on the circle, is there a fixed arc whose discrepancy is unbounded? In “Some unsolved problems” (1961), Problem (1.21.6), printed p. 234, he defined discrepancy using arcs and asked exactly this fixed-arc question. A non-wrapping half-open arc becomes a half-open interval after identifying the circle with \([0,1)\). A wrapping arc can be replaced by its complementary arc: with compatible half-open endpoints, the two discrepancies are negatives of one another. That normalization is elementary, but its endpoint convention must be stated in a formal treatment.

A small example

Consider the first eight terms of the van der Corput sequence in base \(2\):

\[ 0,\;\frac12,\;\frac14,\;\frac34,\;\frac18,\;\frac58,\;\frac38,\;\frac78. \]

For the fixed interval \(I=[0,1/2)\), exactly every other displayed point is counted. Thus the exact finite values are

\[ D_N(I)=\frac12,0,\frac12,0,\frac12,0,\frac12,0\qquad(1\leq N\leq8). \]

The arithmetic is reproducible with only rational numbers:

from fractions import Fraction
z = [Fraction(0), Fraction(1,2), Fraction(1,4), Fraction(3,4),
     Fraction(1,8), Fraction(5,8), Fraction(3,8), Fraction(7,8)]
half = Fraction(1, 2)
print([sum(x < half for x in z[:N]) - N*half for N in range(1, 9)])

It prints [Fraction(1, 2), Fraction(0, 1), Fraction(1, 2), Fraction(0, 1), Fraction(1, 2), Fraction(0, 1), Fraction(1, 2), Fraction(0, 1)]. This is a finite check of the definition, not evidence that this interval has bounded discrepancy forever and not a proof of Problem 255. It illustrates why a long numerical prefix cannot decide a statement involving a fixed interval and infinitely many \(N\).

What is known

The original problem is classically solved in the affirmative. W. M. Schmidt, “Irregularities of distribution,” Quarterly Journal of Mathematics 19 (1968), 181–191, DOI 10.1093/qmath/19.1.181, is the proof credited by the maintained problem page. The publisher record confirms the author, year, pages, and DOI, but the article's full text was not available in this audit. Consequently, no theorem number or page inside Schmidt 1968 is claimed here.

An accessible source gives a precise usable interface. In Wolfgang M. Schmidt, “Irregularities of distribution. VI,” Compositio Mathematica 24 (1972), 63–74, the introduction on printed pp. 63–64 defines the endpoint discrepancy and, for \(\kappa\geq0\), the set \(S(\kappa)=\{x:D_N([0,x))\text{ has absolute value at most }\kappa\text{ for every }N\}\), with \(S(\infty)=\bigcup_{\kappa\geq0}S(\kappa)\). Schmidt's Theorem on printed p. 64 says that for every derivative order \(d>4\kappa\), \(S^{(d)}(\kappa)=\varnothing\); its Corollary, also p. 64, says that each \(S(\kappa)\), and in particular \(S(\infty)\), is at most countable. Since \((0,1)\) is uncountable, some endpoint \(x\) has unbounded discrepancy for \([0,x)\)—indeed, all but countably many endpoints do. This is a borrowed deep theorem of Schmidt, not an original proof supplied by GCL.

Schmidt 1972 also records the distinction between endpoint and arbitrary-interval statements. For the sequence of fractional parts of multiples of an irrational number, it notes that the bounded-discrepancy endpoint set is countable, while continuum many intervals can nevertheless have bounded discrepancy because their lengths have a special form. Thus “almost every endpoint works” and “every interval works” are very different claims. R. Tijdeman and G. Wagner, “A sequence has almost nowhere small discrepancy,” Monatshefte für Mathematik 90 (1980), 315–329, DOI 10.1007/BF01540851, give the quantitative strengthening recorded in the source audit and compatible with the maintained page's \(\gg 1\) formulation: for every sequence, for almost every \(x\in[0,1)\),

\[ \limsup_{N\to\infty}\frac{|D_N([0,x))|}{\log N}\geq\frac1{400}. \]

The constant and almost-everywhere theorem are reported from that paper and the maintained page; they are not independently reproved here. Erdős’s later discussion, “Problems and results on diophantine approximations” (1964), Compositio Mathematica 16, 52–65, pp. 53–54, revisits fixed-interval discrepancy questions and is useful historical context, not a replacement for Schmidt’s proof.

GCL's current state

The authenticated source return is RESULT/1 for issue #1525, assignment ERDOS-CATALOGUE-0255-S01, disposition PARTIAL. It preserves the exact quantifiers, the circle-to-line normalization issue, the finite check above, Schmidt 1972's countability interface, and the blocker that Schmidt 1968 was inspected only through publisher metadata. It does not claim a new proof, a formal replay, or certification.

The pinned catalogue packet is teorth/erdosproblems at commit 536408716724a2402bdfa7c1d764bf83d64a8c89, entry number: "255" in data/problems.yaml. It records informal_status: proved, formal_status: Lean, and status: proved (Lean), while also recording formalized: no. The protected GCL registry independently records catalogue status proved, triage class OUTSIDE_STRICT_OPEN_TRIAGE, and protected_fc_present: false for Problem 255. These are source and workflow states, not a GCL certificate.

The live maintained problem page says “PROVED,” attributes the affirmative answer to Schmidt, reports the later countability and Tijdeman–Wagner results, and says “Formalised statement? No.” This is live-page evidence and has drifted in presentation from the pinned packet's “proved (Lean)” label. The admitted FC-GDM-85F86371 provider record is public metadata only, and the source packet says it contains no statement file for this problem. An upstream “Lean” label therefore cannot be treated as a checked Lean theorem or GCL certification.

What remains

There is no open original yes/no problem to solve: Schmidt's classical result answers it affirmatively. The remaining work is exactness and documentary reproducibility. A formalization must choose the ambient space, interval type, endpoint convention, indexing of the sequence, and the meaning of boundedness before translating the circle statement. It must then formalize the implication

\[ \text{the bounded-discrepancy endpoint set is countable}\quad\Longrightarrow\quad\exists x\in(0,1)\text{ with }\limsup_N|D_N([0,x))|=\infty. \]

That implication is elementary once Schmidt's countability theorem is available; Schmidt's theorem itself is the deep borrowed lemma. A checked formal proof would still need an actual statement file, source-semantic comparison, and kernel replay in its pinned toolchain. The catalogue's formal_status: Lean field, an external Lean pointer, or a reported formal proof would not by itself discharge any of those requirements.

The 1968 primary article remains source-limited here: its exact theorem numbering and proof pages are not asserted. The 1972 paper supplies an accessible theorem and page for the countability route, but it does not retroactively create a GCL formalization. Endpoint and circle-to-line equivalence should be recorded as explicit lemmas rather than silently assumed.

Sources and claim boundaries

  • Original statement: Paul Erdős (1961), “Some unsolved problems,” Publications of the Mathematical Institute of the Hungarian Academy of Sciences, Series A 6, 221–254, Problem (1.21.6), p. 234. Authenticated scan.
  • Historical follow-up: P. Erdős (1964), “Problems and results on diophantine approximations,” Compositio Mathematica 16, 52–65, pp. 53–54. NUMDAM scan. It is contextual evidence, not the resolution claimed here.
  • Affirmative attribution: W. M. Schmidt (1968), “Irregularities of distribution,” Quarterly Journal of Mathematics 19, 181–191. Publisher record and DOI. Exact theorem/page was not accessible and is deliberately not fabricated.
  • Accessible deep lemma: Wolfgang M. Schmidt (1972), “Irregularities of distribution. VI,” Compositio Mathematica 24, 63–74, Theorem and Corollary, printed p. 64. Full text.
  • Quantitative strengthening: R. Tijdeman and G. Wagner (1980), “A sequence has almost nowhere small discrepancy,” Monatshefte für Mathematik 90, 315–329. DOI.
  • Status sources: maintained Problem 255 page, pinned catalogue entry, GCL registry, provider import record, and the authenticated GCL RESULT/1.

Claim boundaries: the classical solution is attributed to Schmidt; the countability argument is reported from his published 1972 theorem and not presented as an original proof. The finite computation is independently reproducible but only finite. The catalogue and live-site “Lean”/formal-status labels are reported metadata, not formal certification. No GCL acceptance, protected mathematical certification, novelty claim, or external Lean proof replay is asserted.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1525 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
  • Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
  • External mathematical status: consult current problem page and its dated bibliography.

Back to catalogue · Compendium introduction