Erdős Problem #176

Erdős problem #176 · erdosproblems.com/176

Let $N(k, \ell)$ be the least $N$ such that every $f : [N] \to \{-1, 1\}$ has a $k$-term arithmetic progression $P$ with $|\sum_{n \in P} f(n)| \ge \ell$. In particular, is $N(k, 2) \le C^k$?

Result

Proved(see note)

Status

Partial result

AI contribution

AI-discovered

Method

Argument

Field

Discrepancy Theory

Posed by

—

Year posed

1965

Years open

61y

Solved

2026-06-21

Model

Codex 5.5, ChatGPT-5.5 Pro

Vendor

OpenAI

Collaborators

—

Verification

Lean-verified

Publication

Announced

Significance

10 / 100*

Disclosed cost

—

Wikipedia

No dedicated article