Tag Archive

You are currently browsing the tag archive for the ‘Haar measure’ tag.

A variant of Kemperman’s theorem

26 December, 2011 in expository, math.CO | Tags: , , , | by | 4 comments

In 1964, Kemperman established the following result:

Theorem 1 Let {G} be a compact connected group, with a Haar probability measure {\mu}. Let {A, B} be compact subsets of {G}. Then

\displaystyle \mu(AB) \geq \min( \mu(A) + \mu(B), 1 ).

Remark 1 The estimate is sharp, as can be seen by considering the case when {G} is a unit circle, and {A, B} are arcs; similarly if {G} is any compact connected group that projects onto the circle. The connectedness hypothesis is essential, as can be seen by considering what happens if {A} and {B} are a non-trivial open subgroup of {G}. For locally compact connected groups which are unimodular but not compact, there is an analogous statement, but with {\mu} now a Haar measure instead of a Haar probability measure, and the right-hand side {\min(\mu(A)+\mu(B),1)} replaced simply by {\mu(A)+\mu(B)}. The case when {G} is a torus is due to Macbeath, and the case when {G} is a circle is due to Raikov. The theorem is closely related to the Cauchy-Davenport inequality; indeed, it is not difficult to use that inequality to establish the circle case, and the circle case can be used to deduce the torus case by considering increasingly dense circle subgroups of the torus (alternatively, one can also use Kneser’s theorem).

By inner regularity, the hypothesis that {A,B} are compact can be replaced with Borel measurability, so long as one then adds the additional hypothesis that {A+B} is also Borel measurable.

A short proof of Kemperman’s theorem was given by Ruzsa. In this post I wanted to record how this argument can be used to establish the following more “robust” version of Kemperman’s theorem, which not only lower bounds {AB}, but gives many elements of {AB} some multiplicity:

Theorem 2 Let {G} be a compact connected group, with a Haar probability measure {\mu}. Let {A, B} be compact subsets of {G}. Then for any {0 \leq t \leq \min(\mu(A),\mu(B))}, one has

\displaystyle \int_G \min(1_A*1_B, t)\ d\mu \geq t \min(\mu(A)+\mu(B) - t,1). \ \ \ \ \ (1)

Indeed, Theorem 1 can be deduced from Theorem 2 by dividing (1) by {t} and then taking limits as {t \rightarrow 0}. The bound in (1) is sharp, as can again be seen by considering the case when {A,B} are arcs in a circle. The analogous claim for cyclic groups for prime order was established by Pollard, and for general abelian groups by Green and Ruzsa.

Let us now prove Theorem 2. It uses a submodularity argument related to one discussed in this previous post. We fix {B} and {t} with {0 \leq t \leq \mu(B)}, and define the quantity

\displaystyle c(A) := \int_G \min(1_A*1_B, t)\ d\mu - t (\mu(A)+\mu(B)-t).

for any compact set {A}. Our task is to establish that {c(A) \geq 0} whenever {t \leq \mu(A) \leq 1-\mu(B)+t}.

We first verify the extreme cases. If {\mu(A) = t}, then {1_A*1_B \leq t}, and so {c(A)=0} in this case. At the other extreme, if {\mu(A) = 1-\mu(B)+t}, then from the inclusion-exclusion principle we see that {1_A * 1_B \geq t}, and so again {c(A)=0} in this case (since {\int_G 1_A*1_B = \mu(A)\mu(B) = t \mu(B)}).

To handle the intermediate regime when {\mu(A)} lies between {t} and {1-\mu(B)+t}, we rely on the submodularity inequality

\displaystyle c(A_1) + c(A_2) \geq c(A_1 \cap A_2) + c(A_1 \cup A_2) \ \ \ \ \ (2)

for arbitrary compact {A_1,A_2}. This inequality comes from the obvious pointwise identity

\displaystyle 1_{A_1} + 1_{A_2} = 1_{A_1 \cap A_2} + 1_{A_1 \cup A_2}

whence

\displaystyle 1_{A_1}*1_B + 1_{A_2}*1_B = 1_{A_1 \cap A_2}*1_B + 1_{A_1 \cup A_2}*1_B

and thus (noting that the quantities on the left are closer to each other than the quantities on the right)

\displaystyle \min(1_{A_1}*1_B,t) + \min(1_{A_2}*1_B,t)

\displaystyle \geq \min(1_{A_1 \cap A_2}*1_B,t) + \min(1_{A_1 \cup A_2}*1_B,t)

at which point (2) follows by integrating over {G} and then using the inclusion-exclusion principle.

Now introduce the function

\displaystyle f(a) := \inf \{ c(A) : \mu(A) = a \}

for {t \leq a \leq 1-\mu(B)+t}. From the preceding discussion {f(a)} vanishes at the endpoints {a = t, 1-\mu(B)+t}; our task is to show that {f(a)} is non-negative in the interior region {t < a < 1-\mu(B)+t}. Suppose for contradiction that this was not the case. It is easy to see that {f} is continuous (indeed, it is even Lipschitz continuous), so there must be {t < a < 1-\mu(B)+t} at which {f} is a local minimum and not locally constant. In particular, {0 <a <1}. But for any {A} with {\mu(A) = a}, we have the translation-invariance

\displaystyle c(gA) = c(A) \ \ \ \ \ (3)

for any {g \in G}, and hence by (2)

\displaystyle c(A) \geq \frac{1}{2} c(A \cap gA) + \frac{1}{2} c(A \cup gA ).

Note that {\mu(A \cap gA)} depends continuously on {g}, equals {a} when {g} is the identity, and has an average value of {a^2}. As {G} is connected, we thus see from the intermediate value theorem that for any {0 < \epsilon < a-a^2}, we can find {g} such that {\mu(A \cap gA) = a-\epsilon}, and thus by inclusion-exclusion {\mu(A \cup gA) = a+\epsilon}. By definition of {f}, we thus have

\displaystyle c(A) \geq \frac{1}{2} f(a-\epsilon) + \frac{1}{2} f(a+\epsilon).

Taking infima in {A} (and noting that the hypotheses on {\epsilon} are independent of {A}) we conclude that

\displaystyle f(a) \geq \frac{1}{2} f(a-\epsilon) + \frac{1}{2} f(a+\epsilon)

for all {0 < \epsilon < a-a^2}. As {f} is a local minimum and {\epsilon} is arbitrarily small, this implies that {f} is locally constant, a contradiction. This establishes Theorem 2.

We observe the following corollary:

Corollary 3 Let {G} be a compact connected group, with a Haar probability measure {\mu}. Let {A, B, C} be compact subsets of {G}, and let {\delta := \min(\mu(A),\mu(B),\mu(C))}. Then one has the pointwise estimate

\displaystyle 1_A * 1_B * 1_C \geq \frac{1}{4} (\mu(A)+\mu(B)+\mu(C)-1)_+^2

if {\mu(A)+\mu(B)+\mu(C)-1 \leq 2 \delta}, and

\displaystyle 1_A * 1_B * 1_C \geq \delta (\mu(A)+\mu(B)+\mu(C)-1-\delta)

if {\mu(A)+\mu(B)+\mu(C)-1 \geq 2 \delta}.

Once again, the bounds are completely sharp, as can be seen by computing {1_A*1_B*1_C} when {A,B,C} are arcs of a circle. For quasirandom {G}, one can do much better than these bounds, as discussed in this recent blog post; thus, the abelian case is morally the worst case here, although it seems difficult to convert this intuition into a rigorous reduction.

Proof: By cyclic permutation we may take {\delta = \mu(C)}. For any

\displaystyle (\mu(A)+\mu(B)-1)_+ \leq t \leq \min(\mu(A),\mu(B)),

we can bound

\displaystyle 1_A*1_B*1_C \geq \min(1_A*1_B,t)*1_C

\displaystyle \geq \int_G \min(1_A*1_B,t)\ d\mu - t (1-\mu(C))

\displaystyle \geq t (\mu(A)+\mu(B)-t) - t (1-\mu(C))

\displaystyle = t \min( \mu(A)+\mu(B)+\mu(C)-1-t )

where we used Theorem 2 to obtain the third line. Optimising in {t}, we obtain the claim. \Box

254A, Notes 3: Haar measure and the Peter-Weyl theorem

27 September, 2011 in 254A - Hilbert's fifth problem, math.CA, math.GN, math.GR, math.RT | Tags: , , , , | by | 18 comments

In the last few notes, we have been steadily reducing the amount of regularity needed on a topological group in order to be able to show that it is in fact a Lie group, in the spirit of Hilbert’s fifth problem. Now, we will work on Hilbert’s fifth problem from the other end, starting with the minimal assumption of local compactness on a topological group {G}, and seeing what kind of structures one can build using this assumption. (For simplicity we shall mostly confine our discussion to global groups rather than local groups for now.) In view of the preceding notes, we would like to see two types of structures emerge in particular:

  • representations of {G} into some more structured group, such as a matrix group {GL_n({\bf C})}; and
  • metrics on {G} that capture the escape and commutator structure of {G} (i.e. Gleason metrics).

To build either of these structures, a fundamentally useful tool is that of (left-) Haar measure – a left-invariant Radon measure {\mu} on {G}. (One can of course also consider right-Haar measures; in many cases (such as for compact or abelian groups), the two concepts are the same, but this is not always the case.) This concept generalises the concept of Lebesgue measure on Euclidean spaces {{\bf R}^d}, which is of course fundamental in analysis on those spaces.

Haar measures will help us build useful representations and useful metrics on locally compact groups {G}. For instance, a Haar measure {\mu} gives rise to the regular representation {\tau: G \rightarrow U(L^2(G,d\mu))} that maps each element {g \in G} of {G} to the unitary translation operator {\rho(g): L^2(G,d\mu) \rightarrow L^2(G,d\mu)} on the Hilbert space {L^2(G,d\mu)} of square-integrable measurable functions on {G} with respect to this Haar measure by the formula

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

(The presence of the inverse {g^{-1}} is convenient in order to obtain the homomorphism property {\tau(gh) = \tau(g)\tau(h)} without a reversal in the group multiplication.) In general, this is an infinite-dimensional representation; but in many cases (and in particular, in the case when {G} is compact) we can decompose this representation into a useful collection of finite-dimensional representations, leading to the Peter-Weyl theorem, which is a fundamental tool for understanding the structure of compact groups. This theorem is particularly simple in the compact abelian case, where it turns out that the representations can be decomposed into one-dimensional representations {\chi: G \rightarrow U({\bf C}) \equiv S^1}, better known as characters, leading to the theory of Fourier analysis on general compact abelian groups. With this and some additional (largely combinatorial) arguments, we will also be able to obtain satisfactory structural control on locally compact abelian groups as well.

The link between Haar measure and useful metrics on {G} is a little more complicated. Firstly, once one has the regular representation {\tau: G\rightarrow U(L^2(G,d\mu))}, and given a suitable “test” function {\psi: G \rightarrow {\bf C}}, one can then embed {G} into {L^2(G,d\mu)} (or into other function spaces on {G}, such as {C_c(G)} or {L^\infty(G)}) by mapping a group element {g \in G} to the translate {\tau(g) \psi} of {\psi} in that function space. (This map might not actually be an embedding if {\psi} enjoys a non-trivial translation symmetry {\tau(g)\psi=\psi}, but let us ignore this possibility for now.) One can then pull the metric structure on the function space back to a metric on {G}, for instance defining an {L^2(G,d\mu)}-based metric

\displaystyle d(g,h) := \| \tau(g) \psi - \tau(h) \psi \|_{L^2(G,d\mu)}

if {\psi} is square-integrable, or perhaps a {C_c(G)}-based metric

\displaystyle d(g,h) := \| \tau(g) \psi - \tau(h) \psi \|_{C_c(G)} \ \ \ \ \ (1)

if {\psi} is continuous and compactly supported (with {\|f \|_{C_c(G)} := \sup_{x \in G} |f(x)|} denoting the supremum norm). These metrics tend to have several nice properties (for instance, they are automatically left-invariant), particularly if the test function is chosen to be sufficiently “smooth”. For instance, if we introduce the differentiation (or more precisely, finite difference) operators

\displaystyle \partial_g := 1-\tau(g)

(so that {\partial_g f(x) = f(x) - f(g^{-1} x)}) and use the metric (1), then a short computation (relying on the translation-invariance of the {C_c(G)} norm) shows that

\displaystyle d([g,h], \hbox{id}) = \| \partial_g \partial_h \psi - \partial_h \partial_g \psi \|_{C_c(G)}

for all {g,h \in G}. This suggests that commutator estimates, such as those appearing in the definition of a Gleason metric in Notes 2, might be available if one can control “second derivatives” of {\psi}; informally, we would like our test functions {\psi} to have a “{C^{1,1}}” type regularity.

If {G} was already a Lie group (or something similar, such as a {C^{1,1}} local group) then it would not be too difficult to concoct such a function {\psi} by using local coordinates. But of course the whole point of Hilbert’s fifth problem is to do without such regularity hypotheses, and so we need to build {C^{1,1}} test functions {\psi} by other means. And here is where the Haar measure comes in: it provides the fundamental tool of convolution

\displaystyle \phi * \psi(x) := \int_G \phi(x y^{-1}) \psi(y) d\mu(y)

between two suitable functions {\phi, \psi: G \rightarrow {\bf C}}, which can be used to build smoother functions out of rougher ones. For instance:

Exercise 1 Let {\phi, \psi: {\bf R}^d \rightarrow {\bf C}} be continuous, compactly supported functions which are Lipschitz continuous. Show that the convolution {\phi * \psi} using Lebesgue measure on {{\bf R}^d} obeys the {C^{1,1}}-type commutator estimate

\displaystyle \| \partial_g \partial_h (\phi * \psi) \|_{C_c({\bf R}^d)} \leq C \|g\| \|h\|

for all {g,h \in {\bf R}^d} and some finite quantity {C} depending only on {\phi, \psi}.

This exercise suggests a strategy to build Gleason metrics by convolving together some “Lipschitz” test functions and then using the resulting convolution as a test function to define a metric. This strategy may seem somewhat circular because one needs a notion of metric in order to define Lipschitz continuity in the first place, but it turns out that the properties required on that metric are weaker than those that the Gleason metric will satisfy, and so one will be able to break the circularity by using a “bootstrap” or “induction” argument.

We will discuss this strategy – which is due to Gleason, and is fundamental to all currently known solutions to Hilbert’s fifth problem – in later posts. In this post, we will construct Haar measure on general locally compact groups, and then establish the Peter-Weyl theorem, which in turn can be used to obtain a reasonably satisfactory structural classification of both compact groups and locally compact abelian groups.

Read the rest of this entry »

RSS Google+ feed

  • An error has occurred; the feed is probably down. Try again later.
Follow

Get every new post delivered to your Inbox.

Join 2,327 other followers