19. Roth's theorem II: Fourier analytic proof in the integers

Key Takeaways

Last time we started talking about Roth's theorem and we showed a Fourier analytic proof of Roth's theorem in the finite field model. So, Roth's theorem in F3 to the n. And I want to today show you how to modify that proof to work in integers. And this will be basically Roth's original proof of his theorem. Okay. So, what we'll prove today is the statement that the size of the largest 3-AP-free subset of 1 to n is at most n divided by log log n. Okay, so we'll prove a bound of this form. The strategy of this proof will be very similar to the one that we had from last time. So, let me review for you what is the strategy. Um so, So, from last time, uh the proof had three main steps. In the first step, we observed that if you are in a 3-AP-free set, then there exists a large Fourier coefficient. From this Fourier coefficient, we were able to extract um a large sub- a subspace where there's a density increment. I want to modify that strategy so that we can work in the integers. Unlike in F3 to the N, where things were fairly nice and clean and because you have subspaces, you can, you know, take a Fourier coefficient, pass down to a subspace. There's no subspaces, right? There are no subspaces in the integers. So, we'll have to do something slightly different, but in the same spirit. So, you'll find a large Fourier coefficient. And we will find that THERE'S DENSITY INCREMENT. WHEN YOU restrict not to subspaces, but what could play the role of subspaces when it comes to the integers? Well, so I want something which looks like a smaller version of the original space. So, instead of it being integers, if we restrict to a sub-progression, so to a smaller arithmetic progression, I will show that you can just restrict to a sub-progression where you can obtain density increment. So, we'll restrict the integers to something smaller. And then same as last time, we can iterate this in the increment to obtain the conclusion that you have an upper bound on the size of this 3-AP free set. Okay, so that's the strategy. So, you see the same strategy as the one we did last time, and many of the ingredients will have parallels, but the execution will be slightly different, especially in the second step, where because we no longer have subspaces, which are nice and clean. So, that's why we started with a finite field model just to show how things work in a slightly easier setting. And today we'll see uh how to do the same kind of strategy here, where there's going to be a a bit more work. Right? So, not too much more, but a bit more work. So, before we start, any questions? All right. So, last time I used the proof of Roth's theorem as an excuse to introduce Fourier analysis, and we're going to see basically the same kind of Fourier analysis, but it's going to take on a slightly different form, because we're not working in F 3 to the n. We're working inside the integers. And there's a general theory of Fourier analysis on the group um Abelian groups. I don't want to go into that theory, cuz it's I want to focus on the specific case, but the point is that given an Abelian group, you always have a dual group. Dual group of characters. And they play the role of Fourier transform. Specifically, in the case of Z, we have the following Fourier transform. Um so, THE DUAL GROUP OF Z TURNS OUT TO BE THE TORUS. SO, real numbers mod 1. And the Fourier transform is defined as follows. Starting with a function on the integers. Okay? Um if you like, let's say it's finitely supported just to make our lives a bit easier, don't have to deal with technicalities. But, in general, the following formula holds. We have um this Fourier transform defined by setting f hat of theta to be the following sum. OKAY? WHERE THIS E IS ACTUALLY somewhat standard notation in additive combinatorics. It's E to the 2 pi i t. So, it goes a fraction t around the complex unit circle. Okay, so that's the Fourier transform on the integers. Okay, so you might have seen this before under a different name. This is usually CALLED FOURIER SERIES. OKAY? BUT, YOU KNOW, THE NOTATION MAY BE SLIGHTLY DIFFERENT. OKAY, so that's that's what we see today. And this Fourier transform plays the same role as the Fourier transform from last time, which was on the group F3 to the n. And just as in um So, last time we had a number of important identities. And we'll have the same kinds of identities here. So, let me remind you what they are, and the proofs are all basically the same, so I won't show you the proofs. F hat of zero is simply the sum of F over the domain. We have this Plancherel Parseval identity which tells us that if you look at the inner product bilinear form in the physical space it equals to the inner product in the Fourier space. Okay, so in the physical space now you sum, in the frequency space you take integral over the torus. Or the circle in this case, it's a one-dimensional torus. There's also the Fourier inversion formula. Which now says that f of x is equal to f hat of theta e of x theta, you integrate theta from zero to one. Okay, on the torus, on the circle. And third and finally there was this identity last time that related three-term arithmetic progressions to the Fourier transform. Okay, so this last one was uh slightly not as I mean it's not as standard as the the first several which are standard Fourier identities, um but this one will be useful to us. Um so the identity relating the Fourier transform to three-AP's now has the following form. Okay, so if we define lambda of f, g, and h to be um the following sum which sums over all three-AP's in the integers then one can write this expression in terms of the Fourier transform um as follows. Okay. Okay, so compare this formula to the one that we saw from last time, it's the same formula. We have different domains of of where you're summing or integrating, but it's the same formula. And the proof is the same. Okay, so go look at the proof, it's the same proof. Um Okay, so these are the key Fourier things that we'll use. And then we'll try to follow our notes with same as the proof as last time and see where we can get. So, let me introduce one more notation. So, I'll write lambda sub three of f to be lambda of f f f three times. Okay, so at this point, if you understood the lecture from last time, none of anything I've said so far should be surprising. We're working in the integers, so we should look at the corresponding Fourier transform in integers. And if you follow your notes, this is all the things that we're going to use. Okay, so what was one of the first things we mentioned regarding the Fourier transform from last time after this point. Okay, so let's do a counting lemma. So, what should the counting lemma say? Well, the spirit of the counting lemma is that if you have two functions that are close to each other, and now close means close in Fourier, then their corresponding number of 3-APs should be similar. So, so that's what we want to say, and indeed Right. So, the counting lemma for us will say that if f and g are functions on Z, um and such that their L2 norms are both bounded by this M, okay, so the sum of the squared absolute value entries are both bounded, then the difference of their 3-AP counts should not be so different from each other if f and g are close in Fourier. Okay? And that means that if all the Fourier coefficients of f minus g are small, then lambda 3 FF, which considers 3 AP counting F, is close to that of G. Okay. Same kind of 3 AP counting lemma from last time. Okay, so let's prove it. As with the counting lemma proofs you've seen several times already in this course, we will prove it by first writing this difference as a telescoping sum. The first term being F minus G of FF and then G of F minus G F and lambda G G F minus G. And we would like to show that each of these terms is small if F minus G has small Fourier coefficients. Okay, so let's bound the first term. So, let me bound this first term using the 3 AP identity relating 3 AP to Fourier coefficients, we can write um this lambda as the following integral over Fourier coefficients. And now, let me Okay, so what was the trick last time? So, we said let's pull out one of these guys and then use triangle inequality on the remaining factors. So, we'll do that. Okay, so far so good. And now you see this integral apply Cauchy-Schwarz. Okay, so apply Cauchy-Schwarz to the first first factor, you get this L2 sum uh this L2 integral. And then you apply Cauchy-Schwarz to the SECOND FACTOR. YOU GET THAT INTEGRAL. NOW, WHAT DO WE DO? YEP. OKAY, so yeah, so you see an L2 of Fourier the first automatic reaction should be to use Plancherel or Parseval. So, apply apply the Plancherel identity to each of these factors. We find that each of those factors is equal to um this L2 sum in the physical space. This square root the same thing square root again. Okay, and then we find that because there was some hypothesis in the hypothesis there was a bound M on this the sum of squares. You have that down there. And similarly with the other two terms. Okay, so that proves the counting number. Question. Last time the the term on the right hand side was like the maximum over non-zero. Okay. Okay, so the question is last time we had a counting number that looked slightly different. But I claim they're all really the same counting number, they're all the same proofs. If you run this proof, it will work. If you take what we did last time it's the same kind of proofs. So last time we had a counting number where we had the same um f f f essentially. Well, now I have I have you to essentially take three different things and okay, so both in both cases you're running through this calculation, but they look slightly different. Right, so yeah, so I agree it doesn't look exactly the same, but if you think about what's involved in the proof, they're the same proofs. Any more questions? All right. So, now we have this counting lemma, so let's start our proof of Roth's theorem in the integers. As with last time, there will be three steps as mentioned up there. Okay? In the first step, let us show that if you are 3-AP free, then we can obtain a density of a a large Fourier coefficient. Yes, so in this course, you know, it's a this counting lemma, we actually saw this basically this kind of proof for the first time when we discussed graph counting lemma back in the chapter on Szemeredi's regularity lemma. And sure, they all look literally not exactly the same, but they're all really the same kind of proofs. So, I won't I'm showing you the same thing in many different guises, but they're all the same proofs. So, if you are a set that IS 3-AP FREE, AND AS WITH LAST TIME, I'M GOING TO call alpha the density of A now inside this progression, this length N progression. And suppose N is large enough. Okay, so the conclusion now is that there exists some theta such that if you look at this sum over here as a sum over over integers Actually, let me do the sum only from 1 to uppercase N. I claim that Okay, so so It's saying what this title says. If you are 3-AP free and this N is large enough relative to the density, you think of this density alpha as a constant then I can find a large Fourier coefficient. Now there's a small difference and this is related to what you were asking earlier between the how we set things up now versus what happened last time. So last time we just looked for a Fourier coefficient corresponding to a non-zero R. Now I'm not restricting non-zero, but I don't start with indicator function. I start with a demeaned indicator function. I take out the mean so that the zeroth coefficient so to speak which corresponds to the mean is already zero. So you don't get to use that Fourier coefficient. Okay, so if you didn't do this, if you just tried to do this last time, I mean you can also do the exactly the same setup, but if you don't demean it, then if you don't have this term, then this statement is trivially true because I can take theta equal to zero. Cuz but I don't want that. I want a I want an actual sort of significant uh Fourier improvement, so I take I do this demean and then I consider its Fourier coefficient. Okay, any questions about the statement? Yeah, so this the meaning is really important. And so that's something that's a very common technique whenever you do these kind of analysis. And so make sure you're uh get so so that you're Yeah, so you're looking at functions with mean zero. Let's see the proof. We have the following uh information about 3-AP counts in A because A is 3-AP free. Okay, so what is the value of lambda sub three of the indicator of A? Lambda of three, if you look at the expression, it basically sums over all 3-APs, but A has no 3-APs except for the trivial ones. So only consider the trivial 3-APs, which has size exactly the size of A, which is alpha n from trivial 3-APs. On the other hand, what do we know about lambda of three of this interval from one to n? Okay, so how many 3-APs are there? Okay, so roughly it's going to be about n squared over two. And in fact, it will be at least n squared over two because to generate a 3-AP, I just have to pick a first term and a third term, and I'm okay as long as they're the same parity. Okay, then you a 3-AP. So, same parity cuts you down by half. So, you have at least n squared over two 3-APs from 1 through n. So, now let's look at how to apply the counting lemma to the setting. So, we have the counting lemma up there, where I now want to apply it. SO, APPLY COUNTING to on one hand the indicator function of A. So, so we get a count 3-APs in A. But, also compare to the normalized indicator on the interval. Okay, so maybe this is a good point for me to pause and remind you that the spirit of this whole proof is understanding structure versus pseudorandomness. Okay, so as was was with the case last time. So, we want to understand in what ways is A pseudorandom? And here pseudorandom, just as with last time, means having small Fourier coefficients, being Fourier uniform. If A is pseudorandom, which in here means F and G are close to each other. That's what being pseudorandom means. Then the counting lemma will tell us that F and G should have similar AP counts. But, A has basically no AP count. So, they should not be close to each other. So, so that's So, that's the strategy to show that A is not pseudorandom in this sense, and thereby extracting a large Fourier coefficient. So, we apply counting to these two functions, and we obtain that So this quantity which corresponds to lambda three of G minus alpha n. lambda three of G lambda three of F So it is upper bounded the difference is upper bounded by the Using the counting lemma, we find that their difference is upper bounded by the following quantity. Namely, you look at the difference between F and G and evaluate its maximum Fourier coefficient. So if A is pseudorandom meaning that Fourier uniform this L infinity norm is small then I should expect lots and lots of 3A pieces in A, but because that is not the case we will should be able to conclude that there is some large Fourier coefficient. So thus So rearranging the equation above we have that So this is should be a square. Okay, so we have this expression here. And now we are Okay, so let me simplify this expression slightly. And now we're using that N is sufficiently large. So we're using the N is sufficiently large. So this quantity is at least a 10th of alpha squared N. Okay, and that's the conclusion. Okay, so that's the conclusion of this this step here. What does this mean? This means there exists some theta so that the Fourier coefficient at theta is at least the claimed quantity. Any questions? All right. So that finishes step one. So now let me go on to step two. In step two, we wish to show that if you have a large Fourier coefficient then one can obtain a density increment. So last time we were working in a finite field vector space. A Fourier coefficient Okay, so which is a dual vector corresponds to some hyperplane. And having a large Fourier coefficient then implies that the density of A on the cosets of those hyperplanes must be not all close to each other. So, one of the hyperplanes must have significantly higher density than the rest. Okay, so we want to do something similar here, except we run into this technical difficulty where there are no subspaces anymore. And so, the Fourier character, namely corresponding to this data, is just a real number. It doesn't divide up your space. It doesn't divide up your 1 through n very nicely into sub chunks. But, we still want to use this data to chop up 1 through n into smaller spaces so that we can iterate and do density increment. All right. So, let's see what we can do. So, GIVEN THIS DATA, WHAT WE WOULD LIKE TO DO IS TO PARTITION THIS 1 THROUGH N INTO SUBPROGRESSIONS OKAY, SO CHOP UP 1 through n into sub APs um such that if you evaluate you know, for so, this data is fixed. So, on each sub AP, this function here is roughly constant on each of your parts. Last time, we had this Fourier character, and then we chopped it up using these three hyperplanes. And on each hyperplane, the Fourier character is literally constant. So, you have And so, that's what we work with. And now, you cannot get them to be exactly constant, but the next best thing we can hope for is to get this Fourier character to be roughly constant. So, we're going to do some partitioning that allows us to achieve this characteristic. And let me give you some intuition about why this is true. And this is not exactly a surprising fact. The intuition is just that if you look at what this FUNCTION BEHAVES LIKE, SO, WHAT'S GOING ON HERE? YOU are on the unit circle, and you are jumping by theta. So, you just keep jumping by theta. And so on. And I want to show that I can chop up my progression into a bunch of almost periodic pieces, where in each part, I'm staying inside a small arc. So, in the extreme case of this, where it is very easy to see, is if X is some rational number, A over B, with B fairly small, then we can So, so then, um this character is actually constant on a piece with common difference B. Also theta theta thank you theta 2 pi. Yeah, theta if theta is some rational with some small denominator. So then you are literally jumping in periodic steps on the unit circle. So if you partition and according to the exact same periods you have you you have that this character is exactly constant on each of your progressions. Now in general the theta you get out of that proof might not have this very nice form. But we can at least approximately achieve the desired effect. Okay. Any questions? Okay. So to achieve approximately the desired effect, what we'll do is define something so that B times theta is not quite an integer but very close to an integer. So this is probably many of you have seen before. It's a classic pigeonhole type result. So usually attributed to Dirichlet. So if you have theta a real number and a delta kind of a tolerance, then there exists a positive integer D at most one over delta such that D times theta is very close to an integer. Okay, so this norm here is distance to the closest integer. All right. All right, so the proof here is by pigeonhole principle. So if we let M be one over delta round down and consider the numbers zero theta, two theta, three theta and so on to M theta. SO BY PIGEONHOLE UM THERE EXISTS I theta and J theta, some two different um terms of the sequence such that they differ by less than or at most um delta in their fractional parts. Okay, so now I'll take d to be difference between i and j. Um okay, and that works. Okay, so even though you do not have exactly rational, you have approximately rational. So, this is a it's a simple rational approximation statement. And using this approximation, we can now um kind of try to do the intuition here pretending that we're working with rational numbers. Indeed. Okay, so if we take theta between 0 and 1 and um theta irrational and suppose n is large enough. Okay, so here c means there exists some sufficiently large some constant c such that the statement is true. Okay, so suppose, think uh you know, a million here. That should be fine. So, then there exists um so, then one can partition 1 through n into sub APs which we'll call PI and each having length between cube root of n and twice the cube root of n. Such that this character that we want to stay roughly constant indeed does not change very much. If you look at two terms in the same AP, in the same sub AP, then the value of this character on each piece of I is roughly the same. So, they don't vary by more than eta on each PI. So, here we're partitioning this 1 through n into a sub AP's so that this guy here stays roughly constant. Okay, any questions? All right, so think about how you might prove this. Let's take a quick break. So, you see we are basically following the same strategy as the proof from last time, but the second step, which we're on right now, needs to be somewhat modified because you cannot cut the space up into pieces where your character is constant. But, if they're roughly constant, then we're good to go. So, that's what we're doing now. So, let's prove the statement up there. All right, so All right, so let's prove this statement over here. So, using Dirichlet's lemma, we find that um there exists some D. Okay, so I'll write down some number for now. Don't worry about it. It will come up shortly why I write this specific quantity. So, there exists some D which is not too big um such that um D theta is very close to an integer. So, now um I'm literally applying Dirichlet's lemma. Okay. So, given such D, and so how big is this D? You see that because I assumed that N is sufficiently large, if we choose that C large enough, D is at most root N. So, given such D which is at most root N, you can partition 1 through N into subprogressions with common difference D. Essentially look at residue classes mod D. So, they're all going to have length by basically N over D, and I chop them up a little bit further um to get so a piece of length between cube root of N and twice cube root of N. Okay, so I'm going to make sure that all of my APs are roughly the same length. And now inside each sub progression Let me call the sub progression P prime. Uh sub progression P. Let's look at how much this character value can vary inside this progression. Like So, we I guess so how much can this can this vary? Well, because theta is such that D times theta is very close to an integer. And the length of each progression is not too large. Here's I want some control on the length. So, we find that the maximum variation is at most the size of P, the length of P times um so this uh that difference over there. Since all of these are exponentials, I can shift them. Well, the length of P is at most twice cube root of N. And so what is this quantity? So the point is that if this fractional part here is very close to an integer, then E to that num E to the 2 pi times that item to number should be very close to one because what's happening here, this is the distance between those two points on the circle, which is at most bounded by the length of the arc. Okay, so chord length at most that of the arc. Um so now you put everything here together and applying the bound that we got on D theta, so this is the reason for choosing that weird number up there. We find that the variation within each progression is at most eta. So variation of this character within each progression is not very large. And that's the claim. Any questions? So this is the analogous claim to the one that we had the one that we used last time where we said that the character is constant on each coset of the hyperplane. Not exactly constant, but almost good enough. All right. So, the goal of step two is to show an energy show a density increment that if you have a large Fourier coefficient, then we want to claim that the density goes up significantly on some sub progression. And the next part the next lemma will get us to that goal. And this part is very similar to the one that we saw from last time. But with this new partition in mind. If you have A that is 3-AP-3 with density alpha and N is large enough, then there exists some sub progression P Um So, by sub progression, I just mean that I'm starting with original progression 1 through N and I'm zooming into some sub progression um with the length of P fairly long. So, the length of P is at least cube root of N. And such that A when restricted to this sub progression has A DENSITY INCREMENT. OKAY, SO ORIGINALLY THE DENSITY of A is alpha. So, we're zooming into some sub progression P, which is a pretty long sub progression, where the density goes up significantly from A to essentially A from alpha to roughly alpha plus alpha squared. Okay. All right, so we start with a a 3 AP free set. So, FROM STEP ONE THERE EXISTS SOME THETA with large core So, that corresponds to a large Fourier coefficient. Um So, this sum here is large. Okay. And now we use Okay, so so step one obtains us, you know, this uh consequence. And from this data, now we apply the lemma up there to um So, we apply lemma with, let's say, eta being alpha squared over 30. So, exact constants are not so important, but we apply the lemma to partition N into a bunch of subprogressions which we'll call P1 through PK. And each of these progressions have length between cube root of n and twice cube root of n. And I want to understand what happens to the density of A when restricted to these progressions. So, starting with this inequality over here, which suggests to us that there must be some deviation. SO, STARTING STARTING WITH WHAT we saw. And now, inside each progression, this E X theta is roughly constant. Okay, so if you pretend that it's actually constant, I can break up the sum depending on where the X's lie. So, I from 1 to K. And let me sum inside each progression. Um okay, so by triangle inequality, I can upper bound first sum by where I now cut the sum into progression by progression. And on each progression, this character is roughly constant. So, let me take out the maximum possible deviations from them being constant. So, upper bound again, We find that we CAN ESSENTIALLY PRETEND ALL RIGHT, SO IF each exponential is constant on each sub-progression, then I might as well just have this sum here. But I lose a little bit because it's not exactly constant, it's almost constant. So, I lose a little bit, and that little bit is this this eta. So, then you lose that little bit of eta, and so on each progression PI, you lose at most something that's essentially alpha squared times the length of PI. Okay. Now, you see I have chosen the error parameter so that uh everything I've lost is no not so much more than the initial bound I began with. So, in particular, we see that even if we had pretended that the characters were constant on each progression, we would have still obtained a some lower bound on the total deviation. UH OKAY. AND WHAT IS THIS QUANTITY OVER HERE? WELL, you see I'm restricting each sum to each sub-progression. Um but the sum here, even though it's the sum, but it's it's really counting how many elements of A are in that progression. Right? So, this sum over here is the same thing. Okay, so let me write it in a new board. We don't need step one anymore. So, So, what we have So, left-hand side over there is this quantity here. We see that the right-hand side, even though you have that sum, it is really just counting how many elements of A are in each progression versus how many you should expect based on the overall density of A. So, that should look similar to what we got last time. And now the intuition should be that well, if the average deviation is large, then one of them one of these terms should have a the density increment. If you try to do the next step somewhat naively, you run into an issue, because it could be Now, here you have K terms. It could be that you have all the densities except for one going up only slightly and one density dropping dramatically. In which case, you might not have a significant density increment. Right, so we want to show that on some progression, the density increases significantly. So far from this inequality, we just know that there is some sub progression where the density changes significantly. But of course, the overall density, the average density should remain constant. So, if some goes up, others must go down. But, if you just try to do an averaging argument, you have to be careful. Okay. So, so there was a trick last time, which we didn't really need last time, but now now it's much more more useful, where I want to show that if this holds, then some PI sees a large energy sees a large density increment. And to do that, let me rewrite THE SUM AS THE FOLLOWING. SO, I KEEP THE SAME EXPRESSION. AND I ADD A TERM WHICH is the same thing, but without THE ABSOLUTE VALUE. OKAY. SO, YOU SEE these guys, they total to zero. So, adding that term doesn't change my expression. But, now the sum end is always non-negative. So, it's either zero or twice this number, depending on the sign of that number. Okay. So, comparing left-hand side and right-hand side, we see that there must be some I So, hence there exists some I such that the LEFT-HAND SIDE THE ITH TERM ON THE LEFT-HAND SIDE is less than or equal to the Ith term on THE RIGHT-HAND SIDE. AND IN PARTICULAR, THAT TERM SHOULD be positive. So, it implies Okay, so so how how can how can you get this inequality? Okay. It implies simply that the restriction of A to this PI is at least alpha plus alpha squared over 4D times PI. And so so this claim here just says that on the Ith progression, there's a significant energy increment. If it's more decrement, that term would have been zero. So, REMEMBER THAT. OKAY. SO, THIS ACHIEVES WHAT WE WERE looking for in step two, namely to find that there's a density increment on some long sub progression. So, now we can go to step three, which is basically the same as what we saw last time. Where now we want to iterate this density increment. Okay, so it's basically the same argument as last time. You start with density alpha, and each step in the iteration, the density goes up QUITE A BIT. AND WE WANT TO CONTROL THE total number of steps, knowing that the final density is at most one always. Okay. So, how many steps can you take? Right. So, this was the same argument that we saw last time. We see that starting with alpha alpha not being alpha um it doubles after a certain number of steps. Right. So, we double after Okay. So, how many steps do you need? Um Well, I want to get from alpha to two alpha. So, I need at most alpha over 40 steps. Um cuz the last time I was slightly sloppy and so there's a basically a floor up or floor down situation, uh rounding up or down situation, but I should add a plus one. Yeah. 40 Thank you. 40 over alpha. Yeah. So, you double after at most that many steps. And then now you're at density at least two alpha. So, we double after at most 20 over alpha steps. And so on. And we double at most Well, basically log sub two of one over alpha times Okay. So, anyway, putting everything together, we see that the total NUMBER OF STEPS IS AT MOST ON THE ORDER OF one over alpha. When you stop, you can only stop for one reason. Because in the um Yeah, so Yeah, so in in step one remember the iteration said that the process terminates. The process can always go on and it terminates um if the length So, now at step I, so let n sub I be the length of the progression at step I is at most C times alpha I to the minus 12. So um Do we have a Right, so provided that n is large enough, you can always pass to a sub progression. And here in you know, when you pass to a sub progression, of course, you can relabel that sub progression and it's now, you know, one through n I. Right, so I can it's all the progressions are basically the same as the first uh set of positive integers. Right, so a prefix of the positive integers. So, when we stop at step I, you must have n sub I being at most this quantity over here, which is at most C times the initial density raised to this minus 12. So, therefore the initial length n of the space is bounded by Well each time we went down by a cube root at most. Right, so we find if you stop at step I, then the initial length is at most n sub I to the three times uh three to the power of I. Each time you're doing a cube root. Okay, so you put everything together. At most iterations, when you stop, the length is at most this. So, you put them together, and then you find that um the n must be at most double exponential in 1 over the density. In other words, the density is at most 1 over log log n, which is what we claimed in Roth's theorem. So, what we claimed up there. Okay, so that finishes the proof. Any questions? So, the message here is that it's the same proof as last time, but we need to do a bit more work. And none of this work is difficult, but they're more technical. And that's often the theme that you see in additive combinatorics. This is part of the reason why the finite field model is a really nice playground, because there are things tend to be often cleaner, uh but the ideas are often similar or the same ideas. Not always. Next lecture, we'll see one technique where there's a dramatic difference between the finite field vector space and over the integers. But for many things in additive combinatorics, the finite field vector space is just a nicer place to be in to try all your ideas and techniques. All right. Let me comment on some analogies between these two approaches and compare the bounds. So, on one hand, okay, so we saw last time this proof in F3 to the end and now in uh the integers inside this interval of length n. Okay, so let me write uppercase n in both cases to be the size of the overall ambient space. Okay, so what kind of bounds do we get in both situations? So, last time for um in F3 to the end, we got a bound which is of the order n over log n. Whereas today the bound is somewhat worse. So, it's a little bit worse. Now, we lose an extra log. So, where do we lose an extra log in this argument? So, where does these two argument Where do these two arguments differ quantitatively? Okay, so you're you're dividing by So, here in each iteration Okay. Over here you are size of the iteration uh I mean, each iteration the size of the space goes down by a factor three, whereas over here it could go down by a cube root. And that's that's precisely right. So, that explains for this extra log in in the balance. So, while this is a great analogy, um it's not a perfect analogy. So, you see there's this divergence here between the two situations. And so, then you might ask, is there some way to avoid the loss, this extra log factor loss over here? Is there some way to carry out the strategy that we did last time in a way that is much more faithful to that strategy of passing down to subspaces? So, here we passed to progressions. And because we had to do this extra, you know, pigeonhole type argument, it was somewhat lost. We lost a power, which translated into this extra log. Um So, it turns out there there is some way to do this. So, let me just briefly mention what's the idea that is involved. So, last time we went down from um So, the main objects that we were passing were start with a vector space and pass down to a subspace, which is also a vector space. Right? So, you can define subspaces in F3 to the n by um the following. So, I can start with some set of characters U, and I define a some set of characters S, and I define U sub S to be basically the orthogonal complement of S. So, this is a subspace. And these were the kind of subspaces that we saw last time because the S's or the R's that came out of the proof last time, every time we saw one, we threw it in, we cut down to a smaller subspace, and we repeat. But the progressions, they don't really look like this. So the question is, is there some way to do this argument so that you end up with progressions that look like that? And it turns out there is a way. And there are these objects, which we'll see more later in this course, called Bohr sets. Um so they were used by Bourgain to mimic this uh Maschler argument that we saw last time more faithfully into the integers. Where we're going to come up with some set of integers that resemble the much close more closely resemble this notion of subspaces in the finite field setting. And for this, it's much easier to work inside a group. So instead of working in the integers, let's work inside Z mod NZ. So we can do Fourier transform in Z mod NZ, so the discrete Fourier analysis here. So in Z mod NZ, we define So given an S, let's define the Bohr set to be the set of elements of Z mod NZ such that if you look at what really is supposed to resemble this this thing over here. Okay? If this quantity is small for all S. Okay, so we put that element into the Bohr set. Okay, so these sets, they they function much more like subspaces. So they are the analog analog of subspaces inside Z mod NZ, which, you know, if Z N is prime, has no subgroups. It has no natural subspace structure. But by looking at these Bohr sets, they provide a natural way to set up this argument so that you can but with much more technicalities, repeat this kind of arguments more similar to last time, but passing not to subspaces, but to Bohr sets. And um and then with quite a bit of extra work, um one can obtain bounds of the quantity n over uh polylog n. Okay. So, the current best bound I mentioned last time is of this type, which is through further refinements of this technique. Questions? The last thing I want to mention today is so far we've been talking about 3-APs. So, what about 4-term arithmetic progressions? Do any of the things that we talked about here work for 4-APs? And there's an analogy to be made here compared to what we discussed with graphs. So, in graphs, we had a triangle counting lemma and a triangle removal lemma. And then we said that to prove 4-APs, we would need the hypergraph version, the simplex removal lemma, hypergraph regularity lemma. And that was much more difficult. And that analogy carries through, and the same kind of difficulties that come up. So, it can be done, but you need something more. And the main message I want you you to take away is that for 4-APs, while we had A COUNTING LEMMA THAT SAYS THAT FOURIER coefficients of the Fourier transform controls 3-AP counts. It turns out the same is not true for 4-APs. So, but Fourier does not control 4-AP counts. Um Let me give you some Uh okay, so in fact, in the homework for this week, there's a specific example of a set where it has uniformly small Fourier coefficients, but has a wrong number of 4-APs. So, the following it is true. Okay, so it is true that you have Szemeredi's theorem um in let's just talk about the finite field setting where things are a bit easier to discuss. So, it is true that the size of the biggest subset of F5 to the N is a tiny fraction. It's a little more than a fraction of the entire space. Okay, I use F5 here because if I said F3, it doesn't make sense to talk about 4-APs. Okay, so F5, but doesn't really matter which specific field. Um So, you can prove this using hypergraph removal, same proof verbatim that we saw earlier if you have hypergraph removal. But, if you want to try to prove it using Fourier analysis, well, it doesn't work quite using the same strategy. But, in fact, there is a modification that would allow you to to make it work, but you need an extension of Fourier analysis, and it is known as higher order Fourier analysis. Which was an important development in modern additive combinatorics that initially arose in Gowers's work where he gave a new proof of Szemeredi's theorem. So, Gowers didn't work in this setting, he worked in the integers, but many of the ideas originated from from his paper and then subsequently developed you know by a lot of people in various settings. Um I just want to give you one specific statement what this higher order Fourier analysis looks like. So, it's a fancy term and you know the statements often get very technical um but I just want to give you one concrete thing to take away. Right, so for 4-APs higher order Fourier analysis roughly okay, so it also goes by the name quadratic Fourier analysis. Okay, so let me give you a very specific um instance of the theorem. Um and this can be sometimes called an inverse theorem for quadratic Fourier analysis. Suppose Okay, so for every delta there exists some C such that following is true. If A is a subset of F5 to the N with density alpha and such that it's Okay, so now lambda sub four, so this is the 4-AP density, so similar to 3-AP but now you write four terms. The 4-AP density of A differs from alpha to the fourth by a significant amount. Okay, so for 3-APs then we said that now A has a large Fourier coefficient. Right. Um So, for Okay. For 4-APs that may not be true, but following is true. All right. So, then there exists a non-zero QUADRATIC POLYNOMIAL F IN N VARIABLES over f 5 such that the indicator function of A correlates with this quadratic exponential phase. So, Fourier analysis, the conclusion that we got from counting lemma is that you have some linear function f such that this quantity is large, this large Fourier coefficient. Okay, so that is not true for 4-APs. But, what is true is that now you can look at quadratic exponential phases. And and then this true. So, that's the content of um higher order Fourier, I mean, that's the example of higher order Fourier analysis. And you can imagine with this type of result and with quite a bit of more work, you can try to follow a similar density increment strategy to prove Szemerédi's theorem for 4-APs.