Group items tagged

In the second lecture (based on Gowers’s joint work with Julia Wolf) we were introduced to decomposition theorems. A decomposition theorem for the norm can be stated as follows: if is a function (on either or ) with , there is a decomposition , where are “generalized quadratic phase functions” and are error terms with and small. This can be deduced from the inverse theorem of Green-Tao; in fact a similar statement was already implicit in their work, based on the energy increment argument. Tim presented a different approach to deducing decomposition theorems from inverse theorems, based on functional-analytic arguments involving the geometry of normed spaces (specifically, a variant of the Hahn-Banach theorem).

This can be applied to the question of counting solutions to systems of linear equations in sets. Let’s say that we are interested in finding sensible conditions under which a set will have the “statistically correct” number of solutions to a system of linear equations. For instance, if it is 4-term arithmetic progressions that we are concerned with, then uniformity is sufficient (and, in general, necessary). Green and Tao prove a more general result of this type: they define the complexity of a system of linear forms, and prove that systems of complexity are controlled by norms.

Gowers and Wolf, however, do not stop there. Suppose that, instead of 4-term progressions, we are interested in configurations of the form, say, . The complexity of this system in the sense of Green-Tao is 2, hence a set uniform in the norm will contain the “right” number of such configurations. Gowers and Wolf, however, can prove that uniformity already guarantees the same conclusion! The difference between the two examples? The squares are linearly dependent, whereas are not. Gowers and Wolf prove that such “square independence” is in fact both sufficient and necessary for a system of complexity 2 to be controlled by the $U^2$ norm. The proof is based on the decomposition theorem described earlier.

Topics in Harmonic Analysis and Ergodic Theory Joseph M. Rosenblatt, Alexander M. Stokolos, Ahmed I. Zayed ISBN: 0821842358 Paperback American Mathematical Society Usually despatched within 3 to 9 days

There are strong connections between harmonic analysis and ergodic theory. A recent example of this interaction is the proof of the spectacular result by Terence Tao and Ben Green that the set of prime numbers contains arbitrarily long arithmetic progressions. The breakthrough achieved by Tao and Green is attributed to applications of techniques from ergodic theory and harmonic analysis to problems in number theory.Articles in the present volume are based on talks delivered by plenary speakers at a conference on Harmonic Analysis and Ergodic Theory (DePaul University, Chicago, December 2-4, 2005). Of ten articles, four are devoted to ergodic theory and six to harmonic analysis, although some may fall in either category. The articles are grouped in two parts arranged by topics. Among the topics are ergodic averages, central limit theorems for random walks, Borel foliations, ergodic theory and low pass filters, data fitting using smooth surfaces, Nehari's theorem for a polydisk, uniqueness theorems for multi-dimensional trigonometric series, and Bellman and s-functions.In addition to articles on current research topics in harmonic analysis and ergodic theory, this book contains survey articles on convergence problems in ergodic theory and uniqueness problems on multi-dimensional trigonometric series.

We extend two well-known results in additive number theory, S\'ark\"ozy's theorem on square differences in dense sets and a theorem of Green on long arithmetic progressions in sumsets, to subsets of random sets of asymptotic density 0. Our proofs rely on a restriction-type Fourier analytic argument of Green and Green-Tao.

However, it turns out that if one of the sets, say A, is sufficiently “uniform” or “pseudorandom”, then one can always solve this Goldbach-type problem, regardless of what the other two sets are. This type of fact is often established by Fourier-analytic means (or by closely related techniques, such as spectral theory), but let me give a heuristic combinatorial argument to indicate why one would expect this type of phenomenon to occur.

quares Primes Lagrange’s four square theorem: For every positive integer N, there exists a pattern in of the form . Vinogradov’s theorem: For every sufficiently large integer N, there exists a pattern in of the form . Fermat’s two square theorem: For every prime number , there exists a pattern in of the form . Even Goldbach conjecture: For every even number , there exists a pattern in of the form . Fermat’s four square theorem: There does not exist any pattern in of the form with . Green-Tao theorem: For any , there exist infinitely many patterns in of the form with . Pell’s equation: There are infinitely many patterns in of the form . Sophie Germain conjecture: There are infinitely many patterns in of the form .

A new norm related to the Gowers U^3 norm Add to your list(s) Download to your calendar using vCal Pablo Candela Pokorna Monday 16 February 2009, 16:00-17:00 MR12, CMS, Wilberforce Road, Cambridge, CB3 0WB. If you have a question about this talk, please contact Anton Evseev. The uniformity norms (or U^d norms, for d>1 a positive integer) were introduced about ten years ago by Gowers in his effective proof of Szemerédi’s theorem, and have played an important role in arithmetic combinatorics ever since. The U^2 norm is naturally related to Fourier analysis, and a very active trend in current research aims to develop an analogue of Fourier analysis for each U^d norm with d>2. The body of results of this research for d=3 is known as quadratic Fourier analysis. After an introduction to this area we will consider a new norm related to the U^3 norm, and discuss some of its applications in quadratic Fourier analysis, including a strengthening of a central theorem of Green and Tao (the inverse theorem for the U^3 norm), and how this stronger version of the theorem can be used to give a new proof of a recent decomposition-theorem of Gowers and Wolf. This talk is part of the Junior Algebra/Combinatorics/Number Theory seminar series.

We show that the Mobius function mu(n) is strongly asymptotically orthogonal to any polynomial nilsequence n -> F(g(n)L). Here, G is a simply-connected nilpotent Lie group with a discrete and cocompact subgroup L (so G/L is a nilmanifold), g : Z -> G is a polynomial sequence and F: G/L -> R is a Lipschitz function. More precisely, we show that the inner product of mu(n) with F(g(n)L) over {1,...,N} is bounded by 1/log^A N, for all A > 0. In particular, this implies the Mobius and Nilsequence conjecture MN(s) from our earlier paper ``Linear equations in primes'' for every positive integer s. This is one of two major ingredients in our programme, outlined in that paper, to establish a large number of cases of the generalised Hardy-Littlewood conjecture, which predicts how often a collection \psi_1,...,\psi_t : Z^d -> Z of linear forms all take prime values. The proof is a relatively quick application of the results in our recent companion paper on the distribution of polynomial orbits on nilmanifolds. We give some applications of our main theorem. We show, for example, that the Mobius function is uncorrelated with any bracket polynomial. We also obtain a result about the distribution of nilsequences n -> a^nxL as n ranges only over the primes.

There is an amusing way to interpret the conjecture (using the close relationship between nilsequences and bracket polynomials) as an assertion of the pseudorandomness of the Liouville function from a computational complexity perspective.   

Let $p$ be a fixed prime number, and $N$ be a large integer. The 'Inverse Conjecture for the Gowers norm' states that if the "$d$-th Gowers norm" of a function $f:\F_p^N \to \F_p$ is non-negligible, that is larger than a constant independent of $N$, then $f$ can be non-trivially approximated by a degree $d-1$ polynomial. The conjecture is known to hold for $d=2,3$ and for any prime $p$. In this paper we show the conjecture to be false for $p=2$ and for $d = 4$, by presenting an explicit function whose 4-th Gowers norm is non-negligible, but whose correlation any polynomial of degree 3 is exponentially small.Essentially the same result (with different correlation bounds) was independently obtained by Green and Tao \cite{gt07}. Their analysis uses a modification of a Ramsey-type argument of Alon and Beigel \cite{ab} to show inapproximability of certain functions by low-degree polynomials. We observe that a combination of our results with the argument of Alon and Beigel implies the inverse conjecture to be false for any prime $p$, for $d = p^2$.

Quadratic Uniformity of the Mobius Function Authors: Ben Green, Terence Tao (Submitted on 4 Jun 2006 (v1), last revised 22 Sep 2007 (this version, v2)) Abstract: This paper is a part of our programme to generalise the Hardy-Littlewood method to handle systems of linear questions in primes. This programme is laid out in our paper Linear Equations in Primes [LEP], which accompanies this submission. In particular, the results of this paper may be used, together with the machinery of [LEP], to establish an asymptotic for the number of four-term progressions p_1 < p_2 < p_3 < p_4 <= N of primes, and more generally any problem counting prime points inside a ``non-degenerate'' affine lattice of codimension at most 2. The main result of this paper is a proof of the Mobius and Nilsequences Conjecture for 1 and 2-step nilsequences. This conjecture is introduced in [LEP] and amounts to showing that if G/\Gamma is an s-step nilmanifold, s <= 2, if F : G/\Gamma -> [-1,1] is a Lipschitz function, and if T_g : G/\Gamma -> G/\Gamma is the action of g \in G on G/\Gamma, then the Mobius function \mu(n) is orthogonal to the sequence F(T_g^n x) in a fairly strong sense, uniformly in g and x in G/\Gamma. This can be viewed as a ``quadratic'' generalisation of an exponential sum estimate of Davenport, and is proven by the following the methods of Vinogradov and Vaughan.

Inverse Conjecture for the Gowers norm is false Authors: Shachar Lovett, Roy Meshulam, Alex Samorodnitsky (Submitted on 21 Nov 2007) Abstract: Let $p$ be a fixed prime number, and $N$ be a large integer. The 'Inverse Conjecture for the Gowers norm' states that if the "$d$-th Gowers norm" of a function $f:\F_p^N \to \F_p$ is non-negligible, that is larger than a constant independent of $N$, then $f$ can be non-trivially approximated by a degree $d-1$ polynomial. The conjecture is known to hold for $d=2,3$ and for any prime $p$. In this paper we show the conjecture to be false for $p=2$ and for $d = 4$, by presenting an explicit function whose 4-th Gowers norm is non-negligible, but whose correlation any polynomial of degree 3 is exponentially small. Essentially the same result (with different correlation bounds) was independently obtained by Green and Tao \cite{gt07}. Their analysis uses a modification of a Ramsey-type argument of Alon and Beigel \cite{ab} to show inapproximability of certain functions by low-degree polynomials. We observe that a combination of our results with the argument of Alon and Beigel implies the inverse conjecture to be false for any prime $p$, for $d = p^2$. Comments: 20 pages