MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Elon Lindenstrauss explains in his talk at the MSRI in Fall 2008 (the relevant comment is at minute 41 of the video) that the set of large Fourier coefficients of a probability measure $\mu$ on the torus ${\mathbb T}^n$ respects the additive structure. More precisely, he defines

$$A_{\delta} := \lbrace b \in {\mathbb Z}^n \mid |\hat \mu(b)| \geq \delta \rbrace$$

and says that it is "morally" true that $A_{\delta} - A_{\delta} \subset A_{\delta^2}$. (Here, the difference of two subsets is defined to be the set of all possible differences of elements in the respective subsets.) The precise statement (according to Lindenstrauss) is a consequence of the Balog-Szemeredi-Gowers Lemma.

Can someone provide the precise statement or give some hint how the lemma can be used to obtain bounds on Fourier coefficients?

share|cite|improve this question
This set is often called the $delta$-spectrum of A, and is discussed at some length in section 4.6 of Tao and Vu, Additive Combinatorics. I can't recall anything related to your question there, however, and would be very interested myself to find out more. – Thomas Bloom Aug 25 '10 at 11:33
Chapter 2 of these notes, and in particular Chang's theorem, should answer your question. – Kevin O'Bryant Aug 25 '10 at 13:50
@Kevin: Maybe the results in Chapter 2 are related, but for the moment I do not see how they help. First of all, there is no set $A$ in my question; secondly, I am talking about Fourier coefficients of a measure on ${\mathbb T}^n$, not ${\mathbb Z}/n{\mathbb Z}$. – Andreas Thom Aug 25 '10 at 16:33
The link is currently broken since the MSRI is revamping its video section. Temporary link. – Greg Graviton Nov 9 '10 at 16:53
up vote 2 down vote accepted

I think I figured it out myself. What was meant is that for every finite subset $S$ of $A_{\delta}$ one has $$| \lbrace (n,m) \in S \times S \mid n-m \in A_{\delta^2/2} \rbrace | \geq \frac{\delta^2 |S|^2}{2}.$$ This follows from the proof of the second part of Lemma 4.37 in Tao and Vu, Additive Combinatorics. (There, the inequality is stated incorrectly as $\leq$.)

share|cite|improve this answer
Absolutely right. I believe you can use this iteratively to prove Chang's inequality, mentioned by Kevin O'Bryant above. There is a paper of Bourgain (Lambda(p) subsets of squares, perhaps) where, instead of recalling an appropriate reference to this theory, he merely says "by linearisation". – Ben Green Aug 29 '10 at 16:13

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.