Monthly Archive

You are currently browsing the monthly archive for January 2011.

Universality

29 January, 2011 in expository, math.MP, math.PR, non-technical, talk | Tags: , , | by | 9 comments

Last week I gave a talk at the Trinity Mathematical Society at Trinity College, Cambridge UK.  As the audience was primarily undergraduate, I gave a fairly non-technical talk on the universality phenomenon, based on this blog article of mine on the same topic.  It was a quite light and informal affair, and this is reflected in the talk slides (which, in particular, play up quite strongly the role of former students and Fellows of Trinity College in this story).   There was some interest in making these slides available publicly, so I have placed them on this site here.  (Note: copyright for the images in these slides has not been secured.)

An introduction to measure theory

24 January, 2011 in book, math.CA | Tags: | by | 26 comments

As I have done in the last three years, I am spending some time at the beginning of this year converting some of my posts on this blog into book format.  This time round, the situation is a bit different because the majority of mathematical posts last year came from three courses I have taught: random matrices, higher-order Fourier analysis, and measure theory.  These topics are sufficiently unrelated to each other, and to the other mathematical posts from 2010, that I am thinking of having as many as four distinct books this time around, though my plans are not yet definite in this regard.

In any event, I have started the process by converting the measure theory notes to book form, a draft copy of which is now available here.  I have also started up a stub of a book page for this text, though it has little content at present beyond that link.    I will be continuing to work on it in parallel with the rest of the conversion process.  As always, any comments and corrections are very welcome.

The Peter-Weyl theorem, and non-abelian Fourier analysis on compact groups

23 January, 2011 in expository, math.CA, math.RT | Tags: , , , | by | 28 comments

Let {G} be a compact group. (Throughout this post, all topological groups are assumed to be Hausdorff.) Then {G} has a number of unitary representations, i.e. continuous homomorphisms {\rho: G \rightarrow U(H)} to the group {U(H)} of unitary operators on a Hilbert space {H}, equipped with the strong operator topology. In particular, one has the left-regular representation {\tau: G \rightarrow U(L^2(G))}, where we equip {G} with its normalised Haar measure {\mu} (and the Borel {\sigma}-algebra) to form the Hilbert space {L^2(G)}, and {\tau} is the translation operation

\displaystyle \tau(g) f(x) := f(g^{-1} x).

We call two unitary representations {\rho: G \rightarrow U(H)} and {\rho': G \rightarrow U(H')} isomorphic if one has {\rho'(g) = U \rho(g) U^{-1}} for some unitary transformation {U: H \rightarrow H'}, in which case we write {\rho \equiv \rho'}.

Given two unitary representations {\rho: G \rightarrow U(H)} and {\rho': G \rightarrow U(H')}, one can form their direct sum {\rho \oplus \rho': G \rightarrow U(H \oplus H')} in the obvious manner: {\rho \oplus \rho'(g)(v) := (\rho(g) v, \rho'(g) v)}. Conversely, if a unitary representation {\rho: G \rightarrow U(H)} has a closed invariant subspace {V \subset H} of {H} (thus {\rho(g) V \subset V} for all {g \in G}), then the orthogonal complement {V^\perp} is also invariant, leading to a decomposition {\rho \equiv \rho\downharpoonright_V \oplus \rho\downharpoonright_{V^\perp}} of {\rho} into the subrepresentations {\rho\downharpoonright_V: G \rightarrow U(V)}, {\rho\downharpoonright_{V^\perp}: G \rightarrow U(V^\perp)}. Accordingly, we will call a unitary representation {\rho: G \rightarrow U(H)} irreducible if {H} is nontrivial (i.e. {H \neq \{0\}}) and there are no nontrivial invariant subspaces (i.e. no invariant subspaces other than {\{0\}} and {H}); the irreducible representations play a role in the subject analogous to those of prime numbers in multiplicative number theory. By the principle of infinite descent, every finite-dimensional unitary representation is then expressible (perhaps non-uniquely) as the direct sum of irreducible representations.

The Peter-Weyl theorem asserts, among other things, that the same claim is true for the regular representation:

Theorem 1 (Peter-Weyl theorem) Let {G} be a compact group. Then the regular representation {\tau: G \rightarrow U(L^2(G))} is isomorphic to the direct sum of irreducible representations. In fact, one has {\tau \equiv \bigoplus_{\xi \in \hat G} \rho_\xi^{\oplus \hbox{dim}(V_\xi)}}, where {(\rho_\xi)_{\xi \in \hat G}} is an enumeration of the irreducible finite-dimensional unitary representations {\rho_\xi: G \rightarrow U(V_\xi)} of {G} (up to isomorphism). (It is not difficult to see that such an enumeration exists.)

In the case when {G} is abelian, the Peter-Weyl theorem is a consequence of the Plancherel theorem; in that case, the irreducible representations are all one dimensional, and are thus indexed by the space {\hat G} of characters {\xi: G \rightarrow {\bf R}/{\bf Z}} (i.e. continuous homomorphisms into the unit circle {{\bf R}/{\bf Z}}), known as the Pontryagin dual of {G}. (See for instance my lecture notes on the Fourier transform.) Conversely, the Peter-Weyl theorem can be used to deduce the Plancherel theorem for compact groups, as well as other basic results in Fourier analysis on these groups, such as the Fourier inversion formula.

Because the regular representation is faithful (i.e. injective), a corollary of the Peter-Weyl theorem (and a classical theorem of Cartan) is that every compact group can be expressed as the inverse limit of Lie groups, leading to a solution to Hilbert’s fifth problem in the compact case. Furthermore, the compact case is then an important building block in the more general theory surrounding Hilbert’s fifth problem, and in particular a result of Yamabe that any locally compact group contains an open subgroup that is the inverse limit of Lie groups.

I’ve recently become interested in the theory around Hilbert’s fifth problem, due to the existence of a correspondence principle between locally compact groups and approximate groups, which play a fundamental role in arithmetic combinatorics. I hope to elaborate upon this correspondence in a subsequent post, but I will mention that versions of this principle play a crucial role in Gromov’s proof of his theorem on groups of polynomial growth (discussed previously on this blog), and in a more recent paper of Hrushovski on approximate groups (also discussed previously). It is also analogous in many ways to the more well-known Furstenberg correspondence principle between ergodic theory and combinatorics (also discussed previously).

Because of the above motivation, I have decided to write some notes on how the Peter-Weyl theorem is proven. This is utterly standard stuff in abstract harmonic analysis; these notes are primarily for my own benefit, but perhaps they may be of interest to some readers also.

Read the rest of this entry »

A note on approximate subgroups of GL_n(C) and uniformly nonamenable groups

15 January, 2011 in math.CO, math.GR, paper | Tags: , , , | by | 3 comments

Emmanuel Breuillard, Ben Green, and I have just uploaded to the arXiv our paper “A note on approximate subgroups of {GL_n({\bf C})} and uniformly nonamenable groups“. In this short note, we obtain a new proof of a “noncommutative Freiman” type theorem in linear groups {GL_n({\bf C})}. As discussed in earlier blog posts, a general question in additive (or multiplicative) combinatorics is to understand the structure of approximate groups – subsets {A} of genuine groups {G} which are a symmetric neighbourhood the identity (thus {id \in A} and {a^{-1} \in A} whenever {a \in A}), and such that the product set {A \cdot A := \{ ab: a,b \in A \}} is covered by {K} left (or right) translates of {A} for some bounded {K}. (The case {K=1} corresponds to the case of a genuine group.) Most of the focus in multiplicative combinatorics has been on the “discrete” case when {A} is a finite set, though continuous cases are also of interest (for instance, small balls around the identity in a Lie group are approximate groups).

In the discrete case, examples of approximate groups include:

  • Finite groups;
  • Balls in a discrete abelian group, or more generally a discrete nilpotent group, with boundedly many generators;
  • Extensions of the latter type of balls by finite groups;
  • Approximate groups {A} that are controlled by one of the previous examples {B}, in the sense that {A} has comparable cardinality to {B}, and can be covered by boundedly many translates of {B}.

It was conjectured independently by Helfgott and Lindenstrauss (private communication) that these are in fact the only examples of finite approximate groups. This conjecture is not yet settled in general (although we, with Tom Sanders, are making progress on this problem that we hope to be able to report on soon). However, many partial results are known. In particular, as part of the recent paper of Hrushovski in which model-theoretic techniques were introduced to study approximate groups, the following result was established:

Theorem 1 If {n=O(1)}, then every approximate subgroup of {GL_n({\bf C})} is controlled by a nilpotent approximate subgroup.

This result can be compared with Jordan’s theorem (discussed earlier on this blog) that every finite subgroup of {GL_n({\bf C})} is virtually abelian (with a uniform bound on the index of the abelian subgroup), or the special case of Gromov’s theorem for linear groups (which follows easily from the Tits alternative and the work of Milnor and of Wolf) that every finitely generated subgroup in {GL_n({\bf C})} of polynomial growth is virtually nilpotent.

Hrushovski’s proof of the above argument was quite sophisticated; one first transplants the problem using model-theoretic techniques to an infinitary setting, in which the approximate group induces a locally compact topological group structure, which can be played off against the Lie group structure of {GL_n({\bf C})} using the machinery of a paper of Larsen and Pink, as discussed in this previous blog article.

Two further proofs of this theorem were obtained by ourselves, as well as in the most recent version of a similar preprint by Pyber and Szabo. The arguments used here are variants of those used in earlier papers of Helfgott, and are based on establishing expansion of sets that generated Zariski-dense subgroups of various Lie groups (such as {SL_n({\bf C})}). Again, the machinery of Larsen and Pink (which controls how such approximate subgroups intersect with algebraic subgroups) plays a central role.

In this note we give a new proof of this theorem, based primarily on a different tool, namely the uniform Tits alternative of Breuillard. Recall that the Tits alternative asserts that a finitely generated subgroup of {GL_n({\bf C})} is either virtually solvable, or contains a copy of a free group on two generators. In other words, if {A} is a finite symmetric neighbourhood of the identity of {GL_n({\bf C})}, then either {A} generates a virtually solvable subgroup, or else some power {A^m} of {A} contains two elements {x,y} that generate a free group. As stated, {m} may depend on {A}. However, the uniform Tits alternative makes the stronger assertion that one can take {m=m(n)} to be uniform in {A}, and depend only on the dimension parameter {n}.

To use this alternative, we have the following simple observation, that asserts that multiplication by two elements that generate a free group forces a small amount of expansion:

Lemma 2 Let {A, B} be finite sets, such that {B} is symmetric and contains two elements {x,y} that generate a free group {F_2}. Then {|A \cdot B| \geq 3 |A|}.

We remark that this lemma immediately establishes the classical fact that any group that contains a copy of {F_2} is not amenable, an observation initially made by von Neumann.

Proof: By foliating {A} into cosets of {F_2} and translating, we may assume without loss of generality that {A \subset F_2}. Observe that for every element {a} in {A}, at least three of the four elements {ax, ay, ax^{-1}, ay^{-1}} has a longer word length than {a}, while lying in {A \cdot X}. Furthermore, all such elements generated in this fashion are distinct (as one can recover the initial word {a} from the longer word by truncation). The claim follows. \Box

This can be combined with a lemma of Sanders (also independently established by Croot and Sisask), that asserts that for any approximate group {A}, and any {r=O(1)}, one can find a smaller version {S} of {A} – also a symmetric neighbourhood of the identity – with the property that {S^r \subset A^4}, while {S} remains of comparable size to {A}. (One should think of {A} as being like a ball of some radius {R}, in which case {S} is analogous to a ball of radius {R/r}). In particular, {A \cdot S^r \subset A^5} still has size comparable to {A}. Inspecting the size of the sets {A, A \cdot S, A \cdot S^2, \ldots, A \cdot S^r}, we conclude (if {r} is large enough) from the above lemma that {S} cannot contain two elements that generate a free group. Indeed, a slight modification of this argument shows that for any {m = O(1)}, if we take {r} sufficiently large depending on {m}, that {S^m} does not contain two elements that generate a free group. Applying the uniform Tits alternative, this shows that {S} generates a virtually solvable subgroup of {GL_n({\bf C})}. From the known product theory for such groups (due to Breuillard and Green), {S} (and hence {A}) is therefore controlled by a virtually nilpotent group, as desired.

The inverse conjecture for the Gowers norm over finite fields in low characteristic

11 January, 2011 in math.CO, paper | Tags: , , , | by | 3 comments

Tamar Ziegler and I have just uploaded to the arXiv our paper “The inverse conjecture for the Gowers norm over finite fields in low characteristic“, submitted to Annals of Combinatorics. This paper completes another case of the inverse conjecture for the Gowers norm, this time for vector spaces {{\bf F}^n} over a fixed finite field {{\bf F} = {\bf F}_p} of prime order; with Vitaly Bergelson, we had previously established this claim when the characteristic of the field was large, so the main new result here is the extension to the low characteristic case. (The case of a cyclic group {{\bf Z}/N{\bf Z}} or interval {[N]} was established by Ben Green and ourselves in another recent paper. For an arbitrary abelian (or nilpotent) group, a general but less explicit description of the obstructions to Gowers uniformity was recently obtained by Szegedy; the latter result recovers the high-characteristic case of our result (as was done in a subsequent paper of Szegedy), as well as our results with Green, but it is not immediately evident whether Szegedy’s description of the obstructions matches up with the one predicted by the inverse conjecture in low characteristic.)

The statement of the main theorem is as follows. Given a finite-dimensional vector space {V = {\bf F}^n} and a function {f: V \rightarrow {\bf C}}, and an integer {s \geq 0}, one can define the Gowers uniformity norm {\|f\|_{U^{s+1}(V)}} by the formula

\displaystyle \|f\|_{U^{s+1}(V)} := \left( \mathop{\bf E}_{x,h_1,\ldots,h_{s+1} \in V} \Delta_{h_1} \ldots \Delta_{h_{s+1}} f(x) \right)^{1/2^{s+1}}

where {\Delta_h f(x) := f(x+h) \overline{f(x)}}. If {f} is bounded in magnitude by {1}, it is easy to see that {\|f\|_{U^{s+1}(V)}} is bounded by {1} also, with equality if and only if {f(x) = e(P)} for some non-classical polynomial {P: V \rightarrow {\bf R}/{\bf Z}} of degree at most {s}, where {e(x) := e^{2\pi ix}}, and a non-classical polynomial of degree at most {s} is a function whose {s+1^{th}} “derivatives” vanish in the sense that

\displaystyle \partial_{h_1} \ldots \partial_{h_{s+1}} P(x) = 0

for all {x,h_1,\ldots,h_{s+1} \in V}, where {\partial_h P(x) := P(x+h) - P(x)}. Our result generalises this to the case when the uniformity norm is not equal to {1}, but is still bounded away from zero:

Theorem 1 (Inverse conjecture) Let {f: V \rightarrow {\bf C}} be bounded by {1} with {\|f\|_{U^{s+1}(V)} \geq \delta > 0} for some {s \geq 0}. Then there exists a non-classical polynomial {P: V \rightarrow {\bf R}/{\bf Z}} of degree at most {s} such that {|\langle f, e(P) \rangle_{L^2(V)}| := |{\bf E}_{x \in V} f(x) e(-P(x))| \geq c(s,p, \delta) > 0}, where {c(s,p, \delta)} is a positive quantity depending only on the indicated parameters.

This theorem is trivial for {s=0}, and follows easily from Fourier analysis for {s=1}. The case {s=2} was done in odd characteristic by Ben Green and myself, and in even characteristic by Samorodnitsky. In two papers, one with Vitaly Bergelson, we established this theorem in the “high characteristic” case when the characteristic {p} of {{\bf F}} was greater than {s} (in which case there is essentially no distinction between non-classical polynomials and their classical counterparts, as discussed previously on this blog). The need to deal with genuinely non-classical polynomials is the main new difficulty in this paper that was not dealt with in previous literature.

In our previous paper with Bergelson, a “weak” version of the above theorem was proven, in which the polynomial {P} in the conclusion had bounded degree {O_{s,p}(1)}, rather than being of degree at most {s}. In the current paper, we use this weak inverse theorem to reduce the inverse conjecture to a statement purely about polynomials:

Theorem 2 (Inverse conjecture for polynomials) Let {s \geq 0}, and let {P: V \rightarrow {\bf C}} be a non-classical polynomial of degree at most {s+1} such that {\|e(P)\|_{U^{s+1}(V)} \geq \delta > 0}. Then {P} has bounded rank in the sense that {P} is a function of {O_{s,p,\delta}(1)} polynomials of degree at most {s}.

This type of inverse theorem was first introduced by Bogdanov and Viola. The deduction of Theorem 1 from Theorem 2 and the weak inverse Gowers conjecture is fairly standard, so the main difficulty is to show Theorem 2.

The quantity {-\log_{|{\bf F}|} \|e(P)\|_{U^{s+1}(V)}^{1/2^{s+1}}} of a polynomial {P} of degree at most {s+1} was denoted the analytic rank of {P} by Gowers and Wolf. They observed that the analytic rank of {P} was closely related to the rank of {P}, defined as the least number of degree {s} polynomials needed to express {P}. For instance, in the quadratic case {s=1} the two ranks are identical (in odd characteristic, at least). For general {s}, it was easy to see that bounded rank implied bounded analytic rank; Theorem 2 is the converse statement.

We tried a number of ways to show that bounded analytic rank implied bounded rank, in particular spending a lot of time on ergodic-theoretic approaches, but eventually we settled on a “brute force” approach that relies on classifying those polynomials of bounded analytic rank as precisely as possible. The argument splits up into establishing three separate facts:

  1. (Classical case) If a classical polynomial has bounded analytic rank, then it has bounded rank.
  2. (Multiplication by {p}) If a non-classical polynomial {P} (of degree at most {s+1}) has bounded analytic rank, then {pP} (which can be shown to have degree at most {\max(s-p,0)}) also has bounded analytic rank.
  3. (Division by {p}) If {Q} is a non-clsasical polynomial of degree {\max(s-p,0)} of bounded rank, then there is a non-classical polynomial {P} of degree at most {s+1} of bounded rank such that {pQ=P}.

The multiplication by {p} and division by {p} facts allow one to easily extend the classical case of the theorem to the non-classical case of the theorem, basically because classical polynomials are the kernel of the multiplication-by-{p} homomorphism. Indeed, if {P} is a non-classical polynomial of bounded analytic rank of the right degree, then the multiplication by {p} claim tells us that {pP} also has bounded analytic rank, which by an induction hypothesis implies that {pP} has bounded rank. Applying the division by {p} claim, we find a bounded rank polynomial {P'} such that {pP = pP'}, thus {P} differs from {P'} by a classical polynomial, which necessarily has bounded analytic rank, hence bounded rank by the classical claim, and the claim follows.

Of the three claims, the multiplication-by-{p} claim is the easiest to prove using known results; after a bit of Fourier analysis, it turns out to follow more or less immediately from the multidimensional Szemerédi theorem over finite fields of Bergelson, Leibman, and McCutcheon (one can also use the density Hales-Jewett theorem here if one desires).

The next easiest claim is the classical case. Here, the idea is to analyse a degree {s+1} classical polynomial {P: V \rightarrow {\bf F}} via its derivative {d^{s+1} P: V^{s+1} \rightarrow {\bf F}}, defined by the formula

\displaystyle d^{s+1} P( h_1,\ldots,h_{s+1}) := \partial_{h_1} \ldots \partial_{h_{s+1}} P(x)

for any {x,h_1,\ldots,h_{s+1} \in V} (the RHS is independent of {x} as {P} has degree {s+1}). This is a multilinear form, and if {P} has bounded analytic rank, this form is biased (in the sense that the mean of {e(d^{s+1} P)} is large). Applying a general equidistribution theorem of Kaufman and Lovett (based on this earlier paper of Green and myself) this implies that {d^{s+1} P} is a function of a bounded number of multilinear forms of lower degree. Using some “regularity lemma” theory to clean up these forms so that they have good equidistribution properties, it is possible to understand exactly how the original multilinear form {d^{s+1} P} depends on these lower degree forms; indeed, the description one eventually obtains is so explicit that one can write down by inspection another bounded rank polynomial {Q} such that {d^{s+1} P} is equal to {d^{s+1} Q}. Thus {P} differs from the bounded rank polynomial {Q} by a lower degree error, which is automatically of bounded rank also, and the claim follows.

The trickiest thing to establish is the division by {p} claim. The polynomial {Q} is some function {F(R_1,\ldots,R_m)} of lower degree polynomials {R_1,\ldots,R_m}. Ideally, one would like to find a function {F'(R_1,\ldots,R_m)} of the same polynomials with {pF' = F}, such that {F'(R_1,\ldots,R_m)} has the correct degree; however, we have counterexamples that show that this is not always possible. (These counterexamples are the main obstruction to making the ergodic theory approach work: in ergodic theory, one is only allowed to work with “measurable” functions, which are roughly analogous in this context to functions of the indicated polynomials {Q, R_1,\ldots,R_m} and their shifts.) To get around this we have to first apply a regularity lemma to place {R_1,\ldots,R_m} in a suitably equidistributed form (although the fact that {R_1,\ldots,R_m} may be non-classical leads to a rather messy and technical description of this equidistribution), and then we have to extend each {R_j} to a higher degree polynomial {R'_j} with {pR'_j = R_j}. There is a crucial “exact roots” property of polynomials that allows one to do this, with {R'_j} having degree exactly {p-1} higher than {R_j}. It turns out that it is possible to find a function {P = F'(R'_1,\ldots,R'_m)} of these extended polynomials that have the right degree and which solves the required equation {pP=Q}; this is established by classifying completely all functions of the equidistributed polynomials {R_1,\ldots,R_m} or {R'_1,\ldots,R'_m} that are of a given degree.

Archives