You are currently browsing the tag archive for the ‘Balog-Szemeredi-Gowers lemma’ tag.
Let ,
be additive groups (i.e., groups with an abelian addition group law). A map
is a homomorphism if one has
for all . A map
is an affine homomorphism if one has
for all additive quadruples in
, by which we mean that
and
. The two notions are closely related; it is easy to verify that
is an affine homomorphism if and only if
is the sum of a homomorphism and a constant.
Now suppose that also has a translation-invariant metric
. A map
is said to be a quasimorphism if one has
for all , where
denotes a quantity at a bounded distance from the origin. Similarly,
is an affine quasimorphism if
for all additive quadruples in
. Again, one can check that
is an affine quasimorphism if and only if it is the sum of a quasimorphism and a constant (with the implied constant of the quasimorphism controlled by the implied constant of the affine quasimorphism). (Since every constant is itself a quasimorphism, it is in fact the case that affine quasimorphisms are quasimorphisms, but now the implied constant in the latter is not controlled by the implied constant of the former.)
“Trivial” examples of quasimorphisms include the sum of a homomorphism and a bounded function. Are there others? In some cases, the answer is no. For instance, suppose we have a quasimorphism . Iterating (2), we see that
for any integer
and natural number
, which we can rewrite as
for non-zero
. Also,
is Lipschitz. Sending
, we can verify that
is a Cauchy sequence as
and thus tends to some limit
; we have
for
, hence
for positive
, and then one can use (2) one last time to obtain
for all
. Thus
is the sum of the homomorphism
and a bounded sequence.
In general, one can phrase this problem in the language of group cohomology (discussed in this previous post). Call a map a
-cocycle. A
-cocycle is a map
obeying the identity
for all . Given a
-cocycle
, one can form its derivative
by the formula
Such functions are called -coboundaries. It is easy to see that the abelian group of
-coboundaries is a subgroup of the abelian group of
-cocycles. The quotient of these two groups is the first group cohomology of
with coefficients in
, and is denoted
.
If a -cocycle is bounded then its derivative is a bounded
-coboundary. The quotient of the group of bounded
-cocycles by the derivatives of bounded
-cocycles is called the bounded first group cohomology of
with coefficients in
, and is denoted
. There is an obvious homomorphism
from
to
, formed by taking a coset of the space of derivatives of bounded
-cocycles, and enlarging it to a coset of the space of
-coboundaries. By chasing all the definitions, we see that all quasimorphism from
to
are the sum of a homomorphism and a bounded function if and only if this homomorphism
is injective; in fact the quotient of the space of quasimorphisms by the sum of homomorphisms and bounded functions is isomorphic to the kernel of
.
In additive combinatorics, one is often working with functions which only have additive structure a fraction of the time, thus for instance (1) or (3) might only hold “ of the time”. This makes it somewhat difficult to directly interpret the situation in terms of group cohomology. However, thanks to tools such as the Balog-Szemerédi-Gowers lemma, one can upgrade this sort of
-structure to
-structure – at the cost of restricting the domain to a smaller set. Here I record one such instance of this phenomenon, thus giving a tentative link between additive combinatorics and group cohomology. (I thank Yuval Wigderson for suggesting the problem of locating such a link.)
Theorem 1 Let
,
be additive groups with
, let
be a subset of
, let
, and let
be a function such that
for
additive quadruples
in
. Then there exists a subset
of
containing
with
, a subset
of
with
, and a function
such that
for all
(thus, the derivative
takes values in
on
), and such that for each
, one has
for
values of
.
Presumably the constants and
can be improved further, but we have not attempted to optimise these constants. We chose
as the domain on which one has a bounded derivative, as one can use the Bogulybov lemma (see e.g, Proposition 4.39 of my book with Van Vu) to find a large Bohr set inside
. In applications, the set
need not have bounded size, or even bounded doubling; for instance, in the inverse
theory over a small finite fields
, one would be interested in the situation where
is the group of
matrices with coefficients in
(for some large
, and
being the subset consisting of those matrices of rank bounded by some bound
.
Proof: By hypothesis, there are triples
such that
and
Thus, there is a set with
such that for all
, one has (6) for
pairs
with
; in particular, there exists
such that (6) holds for
values of
. Setting
, we conclude that for each
, one has
for values of
.
Consider the bipartite graph whose vertex sets are two copies of , and
and
connected by a (directed) edge if
and (7) holds. Then this graph has
edges. Applying (a slight modification of) the Balog-Szemerédi-Gowers theorem (for instance by modifying the proof of Corollary 5.19 of my book with Van Vu), we can then find a subset
of
with
with the property that for any
, there exist
triples
such that the edges
all lie in this bipartite graph. This implies that, for all
, there exist
septuples
obeying the constraints
and for
. These constraints imply in particular that
Also observe that
Thus, if and
are such that
, we see that
for octuples
in the hyperplane
By the pigeonhole principle, this implies that for any fixed , there can be at most
sets of the form
with
,
that are pairwise disjoint. Using a greedy algorithm, we conclude that there is a set
of cardinality
, such that each set
with
,
intersects
for some
, or in other words that
whenever . In particular,
This implies that there exists a subset of
with
, and an element
for each
, such that
for all . Note we may assume without loss of generality that
and
.
By construction of , and permuting labels, we can find
16-tuples
such that
and
for . We sum this to obtain
and hence by (8)
where . Since
we see that there are only possible values of
. By the pigeonhole principle, we conclude that at most
of the sets
can be disjoint. Arguing as before, we conclude that there exists a set
of cardinality
such that
whenever (10) holds.
For any , write
arbitrarily as
for some
(with
if
, and
if
) and then set
Then from (11) we have (4). For we have
, and (5) then follows from (9).
Recent Comments