Lời giải: Chứng minh của Tao cho bài toán bất tương xứng Erdős qua tương quan trung bình logarit (2015)

Biểu thức trong bước này định nghĩa bất tương xứng của $f:\mathbb{N}\to\{-1,+1\}$: supremum $\sup_{n,d\in\mathbb{N}}\left|\sum_{j=1}^n f(jd)\right|$ đo độ mất cân bằng lớn nhất của $f$ dọc theo các cấp số cộng thuần nhất $d,2d,\ldots,nd$. Erdős đặt giả thuyết vào những năm 1930 rằng supremum này vô hạn với mọi $f$ — tức với mọi chặn $C$ tồn tại $n,d$ sao cho $\left|\sum_{j=1}^n f(jd)\right| > C$. Để định hướng, so sánh với định lý Roth năm 1964, buộc bất tương xứng $\gg\sqrt{N}$ nhưng chỉ khi cho phép mọi cấp số cộng (với điểm đầu tùy ý); giới hạn về các cấp số đi qua $0$ chính là chỗ cấu trúc nhân tính có thể can thiệp, vì $f$ nhân tính hoàn toàn thỏa $\sum_{j=1}^n f(jd) = f(d)\sum_{j=1}^n f(j)$ và bài toán thu về chính các tổng riêng của nó.

Giả thuyết tồn tại tám mươi năm và trải qua một thử nghiệm polymath chuyên biệt. Polymath5 (2010, do Gowers khởi xướng) kiểm tra các trường hợp nhỏ bằng tay và máy tính, trưng ra một dãy dài $1160$ với bất tương xứng $2$, và phát triển phép quy giản Fourier dùng ở bước ba; tính toán bằng bộ giải SAT của Konev và Lisitsa năm 2014 sau đó chỉ ra mọi dãy dài $1161$ đã có bất tương xứng ít nhất $3$, đồng thời tìm được một dãy dài khoảng $13{,}000$ với bất tương xứng $3$ — nên sự tăng không bị chặn là có thật nhưng có thể chậm tùy ý.

Chứng minh năm 2015 của Tao (arXiv:1509.05363, Discrete Analysis 2016) thực ra giải quyết phát biểu mạnh hơn với giá trị vectơ cho $f:\mathbb{N}\to H$ thỏa $\|f(n)\|_H=1$ trong một không gian Hilbert. Các bước còn lại đi theo kiến trúc của bài báo: quy giản về một hàm nhân tính hoàn toàn ngẫu nhiên $\mathbf{g}$ (Mục 2), một dạng trung bình logarit của giả thuyết Elliott (Định lý 1.10, chuyển từ bài báo đồng hành), và một lập luận Borwein–Choi–Coons tổng quát (Mục 4) loại trừ trường hợp cuối cùng.