You are currently browsing the tag archive for the ‘Cauchy-Davenport inequality’ tag.

In 1964, Kemperman established the following result:

Theorem 1Let be a compact connected group, with a Haar probability measure . Let be compact subsets of . Then

Remark 1The estimate is sharp, as can be seen by considering the case when is a unit circle, and are arcs; similarly if is any compact connected group that projects onto the circle. The connectedness hypothesis is essential, as can be seen by considering what happens if and are a non-trivial open subgroup of . For locally compact connected groups which are unimodular but not compact, there is an analogous statement, but with now a Haar measure instead of a Haar probability measure, and the right-hand side replaced simply by . The case when is a torus is due to Macbeath, and the case when 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 are compact can be replaced with Borel measurability, so long as one then adds the additional hypothesis that 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 , but gives many elements of some multiplicity:

Theorem 2Let be a compact connected group, with a Haar probability measure . Let be compact subsets of . Then for any , one has

Indeed, Theorem 1 can be deduced from Theorem 2 by dividing (1) by and then taking limits as . The bound in (1) is sharp, as can again be seen by considering the case when 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 and with , and define the quantity

for any compact set . Our task is to establish that whenever .

We first verify the extreme cases. If , then , and so in this case (since ). At the other extreme, if , then from the inclusion-exclusion principle we see that , and so again in this case.

To handle the intermediate regime when lies between and , we rely on the *submodularity inequality*

for arbitrary compact . This inequality comes from the obvious pointwise identity

whence

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

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

Now introduce the function

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

for any , and hence by (2)

Note that depends continuously on , equals when is the identity, and has an average value of . As is connected, we thus see from the intermediate value theorem that for any , we can find such that , and thus by inclusion-exclusion . By definition of , we thus have

Taking infima in (and noting that the hypotheses on are independent of ) we conclude that

for all . As is a local minimum and is arbitrarily small, this implies that is locally constant, a contradiction. This establishes Theorem 2.

We observe the following corollary:

Corollary 3Let be a compact connected group, with a Haar probability measure . Let be compact subsets of , and let . Then one has the pointwise estimateif , and

if .

Once again, the bounds are completely sharp, as can be seen by computing when are arcs of a circle. For quasirandom , 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 . For any

we can bound

where we used Theorem 2 to obtain the third line. Optimising in , we obtain the claim.

## Recent Comments