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).
10 comments
Comments feed for this article
7 July, 2018 at 1:50 pm
Harry Crimmins
The link to the previous post re cohomology appears to be broken.
[Corrected, thanks – T.]
8 July, 2018 at 4:02 am
John Mangual
The circle
has rotational symmetry. We could call this group
. The rational points on the circle should be “sort-of” rotationally symmetric. How can we express that mathematically?
We have
with
and the height of
. I'm even straining to find the definition of "height" here… if
as reduced fractions, then we have
.
This is a set of measure zero,
but maybe I can cover each rational point with a small interval? If I rotate this circle by 45 degrees, none of this set overlaps with itself, so this circle is definitely not rotationally symmetric.
8 July, 2018 at 1:43 pm
Allan van Hulst
Three lines below Z -> R in bold: “we can then one can verify that”
[Corrected, thanks – T.]
9 July, 2018 at 1:23 am
Anonymous
two lines above theorem 1, it seems that “think” should be “thank”.
[Corrected, thanks – T.]
9 July, 2018 at 5:59 am
majdoddin
“one can check that
is an affine quasimorphism if and only if it is the sum of a quasimorphism and a constant.”
But isn’t the sum of quasimorphism and a constant simply a quasimorphism?
Let
be a quasimorphism and let
for all
and for a constant
.
.
Now
By triangle-inequality we have
.
Now because
is a translation invariant metric, the right side is equal to
.
[This is technically true, but only if one is willing to lose control of the quasimorphism constants; I have reworded this paragraph to address this point. -T]
9 July, 2018 at 11:46 pm
OneGuy
OT: Are you gonna write on the Kakeya conjecture anytime soon? My
paper was on the editors table for almost 10 months, but the experts on the field wouldn`t referee it.
10 July, 2018 at 5:35 am
majdoddin
In calculations of the quasimorphism
, there is no need to use (2) a second time.
in (2) is implying this definition of Big-O notation (see also here):
To see it, first notice that your usage of
Using this notation, we have
for
, then
for
, and then
for all
.
[The final use of (2) is needed to control
for negative
. -T.]
16 July, 2018 at 6:53 pm
Anonymous
Dear Terry,
Today is 17th july 1975
Happy birthday to you,I am expecting your new breakthrough works.
28 August, 2018 at 5:51 am
John Mangual
The goal in many papers (or a Theorem in a book) pages and pages to show that
for some definition of “approximate” or “close” or “looks good” or “kinda-sorta”. Well… we could show that
like you said.
Rarely do they use Additive Combinatorics. Sources suggest it could be a good a resource as any. They just don’t.
28 October, 2018 at 1:42 am
1% Quasimorphisms and group cohomology – BeingProWorld
[…] Link to the original work […]