Skip to content

Erdős Problem #176

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: additive combinatorics, arithmetic progressions, 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

Colour the integers \(1,\ldots,N\) using signs \(f(n)\in\{-1,1\}\). For a fixed length \(k\), every arithmetic progression \(P=\{a,a+d,\ldots,a+(k-1)d\}\) has discrepancy \(\bigl|\sum_{n\in P}f(n)\bigr|\).

Define \(N(k,\ell)\) as the smallest \(N\) that forces some progression of length \(k\) to have discrepancy at least \(\ell\) for every sign colouring. Erdős #176 asks for good upper bounds, particularly whether \(N(k,ck)\), \(N(k,2)\), or \(N(k,\sqrt{k})\) can be bounded by \(C^k\) with constants appropriate to the chosen threshold.

A small example

For \(k=3\), every sum of three signs is odd, so its absolute value is either one or three. Asking for discrepancy at least two is therefore equivalent to asking for discrepancy three, i.e. a monochromatic progression. In general every discrepancy has the same parity as \(k\), so noninteger thresholds such as \(ck\) must be interpreted via \(\lceil ck\rceil\) with the parity restriction applied.

When \(\ell=k\), the condition exactly forces a monochromatic progression of length \(k\). Thus \(N(k,k)\) equals the ordinary van der Waerden number \(W(k)\) for two colours.

What is known

The proposed broad exponential upper bounds are OPEN. Spencer (1973) proved, for \(k=2^tm\) with \(m\) odd,

\[ N(k,1)=2^t(k-1)+1. \]

The formula concerns the threshold one; it is not an exponential bound at a proportional threshold \(ck\).

Erdős proved exponential lower bounds for \(N(k,ck)\), with the base depending on \(c\). Zach Hunter's observation on the maintained #176 derives stronger lower bounds via the Lovász local lemma, involving the binomial tail

\[ \sum_{j>(1+c)k/2}\binom kj. \]

For \(c\to1\), the associated lower exponential base approaches two. These are obstructions to small \(N\), not upper bounds answering Erdős's question. The statement “\(N(k,2)\le C^k\)” requires a named constant independent of \(k\) and should not be inferred from finite examples.

GCL's current state

The pinned and maintained catalogue classify #176 OPEN. Original issue: #1445. No admitted statement file exists in the frozen formal provider. The current catalogue includes 2026 commentary on the local-lemma lower bound, which is recorded without claiming a separate refereed theorem. The stronger upper-bound problem remains unchanged.

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 fixture exhaustively enumerates sign colourings of \([1,N]\) for small \(N\), calculates discrepancies on every nonconstant arithmetic progression of length \(k\), and compares the formula for threshold one for \(k=2,3,4\) with brute force. Acceptance: parity restrictions and rounding are explicit, \(\ell=k\) is equivalent to the two-colour van der Waerden problem, and all results are labelled finite. Stop before extrapolating a universal exponential upper bound.

Sources and claim boundaries

No new discrepancy bound, proof of the proposed exponential upper bounds or protected editorial admission is claimed.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1445 — 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