Skip to content

Erdős Problem #177

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

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.

The question in plain language

Assign every positive integer a sign \(f(n)\in\{-1,1\}\). For a fixed positive common difference \(d\), consider every finite arithmetic progression with that difference, of any length and any starting point. Its discrepancy is the absolute sum of the signs on its members.

Erdős asked for the smallest function \(h(d)\) such that one single infinite signing can keep the discrepancy of every progression of difference \(d\) at most \(h(d)\), simultaneously for all \(d\ge1\). The quantifiers matter: choosing a different signing for each \(d\) would be much easier. The finite progressions need not start at one or have a prescribed length.

A small example

For \(d=1\), the alternating signing \(f(n)=(-1)^n\) keeps the sum on every interval between \(-1\) and \(1\). For \(d=2\), however, that same signing is constant along each even or odd progression, so its discrepancy grows with the progression length. Thus an argument for one difference cannot be reused indiscriminately for all differences.

For any progression \(a,a+d,\ldots,a+(m-1)d\), the sum is a difference of two prefix sums along the residue class \(a\bmod d\). Uniform boundedness of those residue-class prefix sums implies bounded discrepancy for the corresponding difference \(d\).

What is known

The optimal growth of \(h(d)\) remains OPEN. Cantor, Erdős, Schreiber and Straus established a signing for which \(h(d)\ll d!\). Van der Waerden's theorem forces \(h(d)\) to be unbounded as \(d\) grows. K. F. Roth's 1964 discrepancy theorem supplies the quantitative lower estimate \(h(d)\gg d^{1/2}\).

József Beck, in A discrepancy problem: balancing infinite dimensional vectors (2017), improved the existence upper bound to \(h(d)\le C_\varepsilon d^{8+\varepsilon}\) for every fixed \(\varepsilon>0\). This polynomial upper bound does not prove that exponent \(8\) is optimal or that a square-root estimate can be attained. The catalogue references to [Be17] and [Ro64] are primary-source trails; the full proofs have not been independently replayed.

GCL's current state

The pinned and maintained Erdős #177 classify it OPEN. The authenticated issue is #1446. No admitted formal statement is available at the pinned provider SHA. This review preserves the existence of one global signing and the all-starts, all-lengths progression quantifier.

The original issue contains an authenticated RESULT/1 source report. This is unadjudicated source evidence only, not independent mathematical certification or editorial admission.

What remains

A bounded successor exhaustively searches sign assignments on \([1,12]\) and computes maximum discrepancies for each difference \(d\le4\) and all possible starts and lengths, then compares an independent residue-prefix implementation. Acceptance: the alternating signing has discrepancy at most one for \(d=1\) and unbounded two-step discrepancies as its domain grows. Finite witnesses are not a construction of the required infinite signing.

Sources and claim boundaries

No new discrepancy exponent, independent original-proof verification or editorial admission is claimed.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1446 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: STATEMENT_CAPTURE_REQUIRED.
  • 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