Skip to content

Erdős Problem #178

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.

The question in plain language

Let \(A_1,A_2,\ldots\) be a countable family of infinite subsets of the positive integers, each written in increasing order as \(A_i=\{a_{i1}<a_{i2}<\cdots\}\). Assign each integer a sign \(f(n)\in\{-1,1\}\).

Erdős asked whether there is one signing such that, for every fixed integer \(d\ge1\), the initial sums along the first \(d\) sets stay bounded, uniformly in how far each set is traversed:

\[ \sup_{\substack{1\le i\le d\\m\ge1}} \left|\sum_{j=1}^m f(a_{ij})\right|\le C(d). \]

The constant may depend on \(d\), but not on the prefix length \(m\), and the signs are shared among all \(A_i\).

A small example

Take \(A_1\) to be the even positive integers and \(A_2\) the odd positive integers. Giving consecutive members of each set alternating signs makes every prefix sum of both enumerations have absolute value at most one. This example has no overlap, so it does not capture the challenge: when sets overlap, the same integer must keep the same sign in every set.

On any finite truncation one can compare the maximum prefix discrepancy over the first \(d\) sets. That computation cannot itself establish one infinite signing for infinitely many constraints.

What is known

PROVED. József Beck solved Erdős's question in [Be81]. His later work, A discrepancy problem: balancing infinite dimensional vectors (2017), gives an explicit parameter dependence

\[ C(d)\ll_\varepsilon d^{4+\varepsilon} \]

for each fixed \(\varepsilon>0\). This is distinct from Erdős #177, where the polynomial exponent attributed to Beck for all fixed-difference progressions is \(8+\varepsilon\).

The maintained #178 reports that an external formalization of Beck's result was produced in 2026 and labels the problem PROVED (LEAN). The public discussion attributes the automated formalization to Aristotle. A published report of formalization does not establish that GCL has independently built the exact Lean snapshot, checked its allowed axioms or matched it to its protected provider.

GCL's current state

The pinned catalogue labels #178 PROVED. Original issue: #1447. The existence theorem and improved bound were checked against the current source description. GCL does not claim a newly discovered signing construction or protected Lean proof admission.

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 task compares prefix balancing for finite overlapping set families. Acceptance: one global sign assignment is used, all prefixes are checked for every set among the first \(d\), and the disjoint even/odd example attains bound one. Separately replay the named external Lean result at a fixed commit with a theorem-statement and axiom audit. Stop before presenting a finite balancing calculation as a proof of the infinite theorem.

Sources and claim boundaries

No independent Beck proof, certified GCL Lean replay or editorial admission is claimed.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1447 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
  • Formal-statement coverage: A provider statement was included in the pinned 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