한
Problem workshop

One great problem, three kinds of immersion

From a story to your own conjecture

Problem stories open curiosity. The problem workshop is the next place, where curiosity becomes a testable idea.

  1. 1 · DiscoverMeet the questionLearn when it appeared and why it still holds people’s attention.
  2. 2 · ChallengeTest one caseMake your first observation in five minutes with a drawing, calculation, or colors.
  3. 3 · DevelopYou are hereBuild on ideasPublish an observation and grow it through comparisons, conjectures, and counterexamples.
Week 24 · ErdősResolved
Primary source

Erdős Discrepancy Problem — Can ±1\pm 1 Subsequence Sums Stay Bounded?

Intermediate· Posed 1932

Problem

For any sequence x1,x2,…∈{+1,−1}x_1, x_2, \ldots \in \{+1, -1\}, do the partial sums S(n,d)=∑k=1nxkdS(n, d) = \sum_{k=1}^n x_{kd} always become arbitrarily large? Erdős (1932) conjectured yes — no ±1\pm 1 sequence can keep all "arithmetic-progression sums" bounded.

Why it matters

For d=1d=1, partial sums describe a Bernoulli walk. For all dd simultaneously bounded, the sequence would have to balance against every multiplicative structure — Erdős conjectured impossible. Even the C=2C = 2 case was open for 80 years.

Progress so far

Tao (2015-09-17, Discrete Analysis 2016) completely resolved the problem after Polymath 5 reduced the C=2C=2 case computationally. Tao's entropy-decrement argument combined with multiplicative-function structure (Liouville/Möbius) closed the case for all CC.

Further reading

💡 Explore together, one line at a time(0 contributions)

Contributions are not ranked by popularity. Curator feedback names what is clear or reproducible, and peer signals mean someone understood or actually reproduced it.

What did you notice?

You do not need a complete proof. A small observation can open the next path.

Markdown + KaTeX supported (`$x^2$` inline, `$$\sum_{k=1}^n k$$` display)
0 / 3000 characters

moderation policy. Sign in after submitting if you want to edit or delete this attempt from another device.

Loading…

Related concepts

Related mathematicians