I Can't Believe It's Not Random!

In 1977 Furstenberg gave a new proof of Szemerédi’s theorem using ergodic theory. The first step in that proof was to turn the combinatorial statement into a statement in ergodic theory. Thus Furstenberg created what is now known as Furstenberg’s correspondence principle. While this was not (by far) the most difficult part of the proof of Szemerédi’s theorem, it was this principle that allowed many generalizations of Szemerédi’s theorem to be proved via ergodic theoretical arguments. Most of those generalizations had to wait a long time before seeing a combinatorial proof, and for some, no combinatorial proof was ever found (yet).

In this post I will state and prove the correspondence principle and then I will use it to give another proof of Sárközy’s theorem, discussed in my previous post.

View original post 2,382 more words