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

In reading the paper of Green and Tao on arithmetic progressions within the primes, I became very interested in the notion of a k-pseudorandom measure discussed in that paper.

A measure here is a function $\nu:\mathbf{Z}_N\to\mathbf{R}$ such that $\mathbf{E}\nu=1+o(1)$, and it is k-pseudorandom if it obeys the ($k2^{k-1}$,$3k-1$,$k$) (I think) linear forms condition, which basically asserts that it behaves independently with respect to at most $k2^{k-1}$ independent linear forms in $3k-1$ variables, and if it also obeys the correlation condition, which is a weaker form controlling the linear forms $x+h_i$.

They show that a relative Szemeredi's theorem applies to functions bounded by a k-pseudorandom measure, and then construct one that (effectively) bounds the primes.

My question is where else these type of functions have been studied, whether their theory has been expanded, and whether other explicit examples have been found and applied in other situations.

share|cite|improve this question
Maybe this post from "in theory"… is relevant – Gil Kalai Nov 28 '09 at 19:46
up vote 5 down vote accepted

Linear forms condition says that these functions are morally the functions that are close to $1$ in appropriate $U^k$ norm. What I mean is that $U^k$ norms are a special kind of linear forms, and so linear forms condition implies proximity to $1$ in $U^k$, on one hand. On the other hand,if one controls $\nu-1$ in $U^t$ norm for sufficiently large $t=t(k)$, then by Cauchy-Schwarz argument one can control arbitrary linear forms.

[EDIT: The rest of the answer is result of my misunderstanding. See the comments.] There is an unpublished work of David Conlon and Timothy Gowers on Szemerédi-type results in random sets, in which, if I understood correctly what David explained to me, they show as a special case that the control in an appropriate $U^t$ norm is enough. (In particular the correlation condition is no longer necessary, and was an artifact of the original proof.)

So, the answer to your question is that the theory of these functions is essentially the theory of functions with small $U^k$ norm.

share|cite|improve this answer
Perfect - the removal of the correlation condition was one of the things I was wondering about. Any idea if this paper is located online somewhere? – Thomas Bloom Nov 28 '09 at 21:59
Last I asked, it was not fully written yet. You should ask the authors. – Boris Bukh Nov 28 '09 at 22:12
It's not true that we removed the correlation condition -- that question is still open. What we did was look at functions bounded by random as opposed to pseudorandom measures, and we obtained best possible results by considering a specially constructued norm rather than the $U^k$ norm. The paper will be posted on the arXiv soon. – gowers Nov 29 '09 at 21:07
Thanks for clarifying. The way I understood David's explanation in Oberwolfach was that the norms you introduce are all bounded by an appropriate U^k norm. I must have misunderstood. – Boris Bukh Nov 29 '09 at 21:56
The way I understood David's explanation was that if there is control of all these norm, then the set is sufficiently pseudorandom to run transference. As all the norms are dominated by U^k norm, one can run transference having control on U^k alone (though due to use of Cauchy-Schwarz, the results obtained in this way are not sharp quantitatively). – Boris Bukh Nov 29 '09 at 22:02

For a relative Szemer\'edi theorem, the correlation condition was removed and just a weak linear forms condition was shown to be sufficient in:

D. Conlon, J. Fox, and Y. Zhao, A relative Szemerédi theorem, preprint.

share|cite|improve this answer

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.