So in the last post, we defined the discrete Fourier transform and gave some of its basic properties. At the end, we claimed that it gives us a simple notion of pseudorandomness that allows us to make rigorous the intuition that “pseudorandom subsets of should have many arithmetic progressions.” Today we’re going to justify this notion of pseudorandomness, and work through this — the easy case — of the proof of Roth’s theorem for . At the end, we’ll sketch how to modify the method for the regular, finitary version of the theorem.

If you’ve forgotten the definition and basic properties of the discrete Fourier transform, it’s probably worth looking back at the last post now. The important things to keep in mind here are the definition of the DFT and the Plancherel identity, as well as the following identity that we derived toward the end, letting be the number of 3-term APs in our set:

So an obvious strategy is to try and bound the size of the “error term” in the above identity. To do this, we’ll look at the behavior of the Fourier coefficients of a random set.

Let be a random set of size . How big are the Fourier coefficients ? Well, , of course. But the rest are all quite small, in fact of order (depending on ). The quickest way to see this is probably to note that the Fourier coefficients away from 0 should all have the same order, and then apply the Plancherel identity.

And, as it happens, we can bound the error term given that the coefficients away from 0 are small. Here’s how we do it: Let be the maximum value of . Then we pull c out of the sum, and bound it by

again by the Plancherel identity, but the RHS of the above identity is .

The above should make it clear how to deal with the “pseudorandom” case. Call the set “-pseudorandom” if the Fourier coefficients , are bounded by . Then it follows from the above discussion that if is -pseudorandom for some $\epsilon < \delta^2/2$, for instance, then is large and contains nontrivial 3-APs.

This is, in fact, the best we can do by this argument, up to a constant. We have to ask: Is this (seemingly somewhat strong) notion of pseudorandomness enough to allow us to use density increment for non-pseudorandom sets? Well, the answer is yes, but that’ll wait for the next post.

Of course, the above argument works only for the version of Roth’s theorem. However, there’s a (somewhat non-obvious) trick we can use to ensure the existence of a real 3-AP. Instead of listing it here, though, I’ll refer the interested reader (once again) to Neil Lyall’s notes, where the trick is found on page 3.

Tags: DFT, GILA, math.CO, math.NT, probabilistic method, pseudorandom, randomness, roth's theorem

## Leave a Reply