에르되시 불일치 문제 — $\pm 1$ 수열의 부분합은 유계인가

$x_1, x_2, \ldots \in \{+1, -1\}$인 임의의 수열에 대해, 부분합

이 *모든 $n, d \ge 1$에서 어떤 상수 $C$로 유계가 되도록 수열을 선택할 수 있는가*?

Erdős 1932: 불가능하다고 추측 ($\sup |S(n, d)| = \infty$).

$d = 1$: 단순 부분합 $\sum_{k=1}^n x_k$ — Bernoulli walk. $d = 2$: 짝수 인덱스만의 부분합. *모든 $d$에 동시에 유계*가 되려면 수열이 모든 곱셈 구조에 균형을 맞춰야 한다. Polymath5는 길이 1124인 discrepancy 2 수열과 풍부한 실험 구조를 찾았고, Konev–Lisitsa는 2014년 SAT 계산으로 길이 1160은 가능하지만 1161은 불가능함을 인증했다. 이 유한 계산과 모든 $C$를 다룬 뒤의 일반 증명은 서로 다른 진척이다.

Tao 2015-09-17 (Discrete Analysis 2016) — 완전 해결. Tao는 문제를 multiplicative function의 상관 문제로 환원하고 entropy decrement 논증을 결합해 *모든 $C$*에 대한 일반 증명을 완성했다. Polymath5의 실험·부분 구조와 Konev–Lisitsa의 별도 SAT 결과는 중요한 선행 맥락이지만, Polymath5가 $C=2$를 1160까지 증명했거나 Tao의 증명을 결정적 단계까지 직접 환원했다고 합치지 않는다.