The Erdős Discrepancy Problem

Imagine standing on the center of a towering platform just steps in either direction from a deadly fall. You must now choreograph a sequence of steps forward and backward that will keep you on the platform. But here’s the twist: You may have to follow every step in your sequence, or just those divisible by two, or three, or some other number. What’s the longest sequence of steps you can create while guaranteeing your safety? If you’re two steps from death, the answer is 11. For three steps, the answer is 1,161. But what about for other numbers?

This conundrum, the Erdős discrepancy problem, was conjectured by mathematician Paul Erdős in around 1932 and had gone unsolved for more than seven decades. In this lecture, Terence Tao will discuss his general solution to the problem, published last year, and its connections to the Chowla and Elliot conjectures in number theory. The solution incorporates mathematical tools from probability, number theory and information theory.