1% quasimorphisms and group cohomology

7 July, 2018 in expository, math.CO, math.GR | Tags: additive combinatorics, Balog-Szemeredi-Gowers lemma, cocycle, group cohomology, quasimorphism, structure

Let ${G = (G,+)}$ , ${H = (H,+)}$ be additive groups (i.e., groups with an abelian addition group law). A map ${f: G \rightarrow H}$ is a homomorphism if one has

$\displaystyle f(x+y) - f(x) - f(y) = 0$

for all ${x,y \in G}$ . A map ${f: G \rightarrow H}$ is an affine homomorphism if one has

$\displaystyle f(x_1) - f(x_2) + f(x_3) - f(x_4) = 0 \ \ \ \ \ (1)$

for all additive quadruples ${(x_1,x_2,x_3,x_4)}$ in ${G}$ , by which we mean that ${x_1,x_2,x_3,x_4 \in G}$ and ${x_1-x_2+x_3-x_4=0}$ . The two notions are closely related; it is easy to verify that ${f}$ is an affine homomorphism if and only if ${f}$ is the sum of a homomorphism and a constant.

Now suppose that ${H}$ also has a translation-invariant metric ${d}$ . A map ${f: G \rightarrow H}$ is said to be a quasimorphism if one has

$\displaystyle f(x+y) - f(x) - f(y) = O(1) \ \ \ \ \ (2)$

for all ${x,y \in G}$ , where ${O(1)}$ denotes a quantity at a bounded distance from the origin. Similarly, ${f: G \rightarrow H}$ is an affine quasimorphism if

$\displaystyle f(x_1) - f(x_2) + f(x_3) - f(x_4) = O(1) \ \ \ \ \ (3)$

for all additive quadruples ${(x_1,x_2,x_3,x_4)}$ in ${G}$ . Again, one can check that ${f}$ 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 ${f: {\bf Z} \rightarrow {\bf R}}$ . Iterating (2), we see that ${f(kx) = kf(x) + O(k)}$ for any integer ${x}$ and natural number ${k}$ , which we can rewrite as ${f(kx)/kx = f(x)/x + O(1/|x|)}$ for non-zero ${x}$ . Also, ${f}$ is Lipschitz. Sending ${k \rightarrow \infty}$ , we can verify that ${f(x)/x}$ is a Cauchy sequence as ${x \rightarrow \infty}$ and thus tends to some limit ${\alpha}$ ; we have ${\alpha = f(x)/x + O(1/x)}$ for ${x \geq 1}$ , hence ${f(x) = \alpha x + O(1)}$ for positive ${x}$ , and then one can use (2) one last time to obtain ${f(x) = \alpha x + O(1)}$ for all ${x}$ . Thus ${f}$ is the sum of the homomorphism ${x \mapsto \alpha x}$ 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 ${f: G \rightarrow H}$ a ${0}$ -cocycle. A ${1}$ -cocycle is a map ${\rho: G \times G \rightarrow H}$ obeying the identity

$\displaystyle \rho(x,y+z) + \rho(y,z) = \rho(x,y) + \rho(x+y,z)$

for all ${x,y,z \in G}$ . Given a ${0}$ -cocycle ${f: G \rightarrow H}$ , one can form its derivative ${\partial f: G \times G \rightarrow H}$ by the formula

$\displaystyle \partial f(x,y) := f(x+y)-f(x)-f(y).$

Such functions are called ${1}$ -coboundaries. It is easy to see that the abelian group of ${1}$ -coboundaries is a subgroup of the abelian group of ${1}$ -cocycles. The quotient of these two groups is the first group cohomology of ${G}$ with coefficients in ${H}$ , and is denoted ${H^1(G; H)}$ .

If a ${0}$ -cocycle is bounded then its derivative is a bounded ${1}$ -coboundary. The quotient of the group of bounded ${1}$ -cocycles by the derivatives of bounded ${0}$ -cocycles is called the bounded first group cohomology of ${G}$ with coefficients in ${H}$ , and is denoted ${H^1_b(G; H)}$ . There is an obvious homomorphism ${\phi}$ from ${H^1_b(G; H)}$ to ${H^1(G; H)}$ , formed by taking a coset of the space of derivatives of bounded ${0}$ -cocycles, and enlarging it to a coset of the space of ${1}$ -coboundaries. By chasing all the definitions, we see that all quasimorphism from ${G}$ to ${H}$ are the sum of a homomorphism and a bounded function if and only if this homomorphism ${\phi}$ 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 ${\phi}$ .

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 “ ${1\%}$ 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 ${1\%}$ -structure to ${100\%}$ -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 ${G = (G,+)}$ , ${H = (H,+)}$ be additive groups with ${|G|=N}$ , let ${S}$ be a subset of ${H}$ , let ${E \subset G}$ , and let ${f: E \rightarrow H}$ be a function such that

$\displaystyle f(x_1) - f(x_2) + f(x_3) - f(x_4) \in S$

for ${\geq K^{-1} N^3}$ additive quadruples ${(x_1,x_2,x_3,x_4)}$ in ${E}$ . Then there exists a subset ${A}$ of ${G}$ containing ${0}$ with ${|A| \gg K^{-O(1)} N}$ , a subset ${X}$ of ${H}$ with ${|X| \ll K^{O(1)}}$ , and a function ${g: 4A-4A \rightarrow H}$ such that

$\displaystyle g(x+y) - g(x)-g(y) \in X + 496S - 496S \ \ \ \ \ (4)$

for all ${x, y \in 2A-2A}$ (thus, the derivative ${\partial g}$ takes values in ${X + 496 S - 496 S}$ on ${2A - 2A}$ ), and such that for each ${h \in A}$ , one has

$\displaystyle f(x+h) - f(x) - g(h) \in 8S - 8S \ \ \ \ \ (5)$

for ${\gg K^{-O(1)} N}$ values of ${x \in E}$ .

Presumably the constants ${8}$ and ${496}$ can be improved further, but we have not attempted to optimise these constants. We chose ${2A-2A}$ 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 ${2A-2A}$ . In applications, the set ${S}$ need not have bounded size, or even bounded doubling; for instance, in the inverse ${U^4}$ theory over a small finite fields ${F}$ , one would be interested in the situation where ${H}$ is the group of ${n \times n}$ matrices with coefficients in ${F}$ (for some large ${n}$ , and ${S}$ being the subset consisting of those matrices of rank bounded by some bound ${C = O(1)}$ .

Proof: By hypothesis, there are ${\geq K N^3}$ triples ${(h,x,y) \in G^3}$ such that ${x,x+h,y,y+h \in E}$ and

$\displaystyle f(x+h) - f(x) \in f(y+h)-f(y) + S. \ \ \ \ \ (6)$

Thus, there is a set ${B \subset G}$ with ${|B| \gg K^{-1} N}$ such that for all ${h \in B}$ , one has (6) for ${\gg K^{-1} N^2}$ pairs ${(x,y) \in G^2}$ with ${x,x+h,y,y+h \in E}$ ; in particular, there exists ${y = y(h) \in E \cap (E-h)}$ such that (6) holds for ${\gg K^{-1} N}$ values of ${x \in E \cap (E-h)}$ . Setting ${g_0(h) := f(y(h)+h) - f(y(h))}$ , we conclude that for each ${h \in B}$ , one has

$\displaystyle f(x+h) - f(x) \in g_0(h) + S \ \ \ \ \ (7)$

for ${\gg K^{-1} N}$ values of ${x \in E \cap (E-h)}$ .

Consider the bipartite graph whose vertex sets are two copies of ${E}$ , and ${x}$ and ${x+h}$ connected by a (directed) edge if ${h \in B}$ and (7) holds. Then this graph has ${\gg K^{-2} N^2}$ 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 ${C}$ of ${E}$ with ${|C| \gg K^{-O(1)} N}$ with the property that for any ${x_1,x_3 \in C}$ , there exist ${\gg K^{-O(1)} N^3}$ triples ${(x_2,y_1,y_2) \in E^3}$ such that the edges ${(x_1,y_1), (x_2,y_1), (x_2,y_2), (x_3,y_2)}$ all lie in this bipartite graph. This implies that, for all ${x_1,x_3 \in C}$ , there exist ${\gg K^{-O(1)} N^7}$ septuples ${(x_2,y_1,y_2,z_{11},z_{21},z_{22},z_{32}) \in G^7}$ obeying the constraints

$\displaystyle f(y_j) - f(x_i), f(y_j+z_{ij}) - f(x_i+z_{ij}) \in g_0(y_j-x_i) + S$

and ${y_j, x_i, y_j+z_{ij}, x_i+z_{ij} \in E}$ for ${ij = 11, 21, 22, 32}$ . These constraints imply in particular that

$\displaystyle f(x_3) - f(x_1) \in f(x_3+z_{32}) - f(y_2+z_{32}) + f(y_2+z_{22}) - f(x_2+z_{22}) + f(x_2+z_{21}) - f(y_1+z_{21}) + f(y_1+z_{11}) - f(x_1+z_{11}) + 4S - 4S.$

Also observe that

$\displaystyle x_3 - x_1 = (x_3+z_{32}) - (y_2+z_{32}) + (y_2+z_{22}) - (x_2+z_{22}) + (x_2+z_{21}) - (y_1+z_{21}) + (y_1+z_{11}) - (x_1+z_{11}).$

Thus, if ${h \in G}$ and ${x_3,x_1 \in C}$ are such that ${x_3-x_1 = h}$ , we see that

$\displaystyle f(w_1) - f(w_2) + f(w_3) - f(w_4) + f(w_5) - f(w_6) + f(w_7) - f(w_8) \in f(x_3) - f(x_1) + 4S - 4S$

for ${\gg K^{-O(1)} N^7}$ octuples ${(w_1,w_2,w_3,w_4,w_5,w_6,w_7,w_8) \in E^8}$ in the hyperplane

$\displaystyle h = w_1 - w_2 + w_3 - w_4 + w_5 - w_6 + w_7 - w_8.$

By the pigeonhole principle, this implies that for any fixed ${h \in G}$ , there can be at most ${O(K^{O(1)})}$ sets of the form ${f(x_3)-f(x_1) + 3S-3S}$ with ${x_3-x_1=h}$ , ${x_1,x_3 \in C}$ that are pairwise disjoint. Using a greedy algorithm, we conclude that there is a set ${W_h}$ of cardinality ${O(K^{O(1)})}$ , such that each set ${f(x_3) - f(x_1) + 3S-3S}$ with ${x_3-x_1=h}$ , ${x_1,x_3 \in C}$ intersects ${w+4S -4S}$ for some ${w \in W_h}$ , or in other words that

$\displaystyle f(x_3) - f(x_1) \in W_{x_3-x_1} + 8S-8S \ \ \ \ \ (8)$

whenever ${x_1,x_3 \in C}$ . In particular,

$\displaystyle \sum_{h \in G} \sum_{w \in W_h} | \{ (x_1,x_3) \in C^2: x_3-x_1 = h; f(x_3) - f(x_1) \in w + 8S-8S \}| \geq |C|^2 \gg K^{-O(1)} N^2.$

This implies that there exists a subset ${A}$ of ${G}$ with ${|A| \gg K^{-O(1)} N}$ , and an element ${g_1(h) \in W_h}$ for each ${h \in A}$ , such that

$\displaystyle | \{ (x_1,x_3) \in C^2: x_3-x_1 = h; f(x_3) - f(x_1) \in g_1(h) + 8S-8S \}| \gg K^{-O(1)} N \ \ \ \ \ (9)$

for all ${h \in A}$ . Note we may assume without loss of generality that ${0 \in A}$ and ${g_1(0)=0}$ .

Suppose that ${h_1,\dots,h_{16} \in A}$ are such that

$\displaystyle \sum_{i=1}^{16} (-1)^{i-1} h_i = 0. \ \ \ \ \ (10)$

By construction of ${A}$ , and permuting labels, we can find ${\gg K^{-O(1)} N^{16}}$ 16-tuples ${(x_1,\dots,x_{16},y_1,\dots,y_{16}) \in C^{32}}$ such that

$\displaystyle y_i - x_i = (-1)^{i-1} h_i$

and

$\displaystyle f(y_i) - f(x_i) \in (-1)^{i-1} g_i(h) + 8S - 8S$

for ${i=1,\dots,16}$ . We sum this to obtain

$\displaystyle f(y_1) + \sum_{i=1}^{15} f(y_{i+1})-f(x_i) - f(x_8) \in \sum_{i=1}^{16} (-1)^{i-1} g_1(h_i) + 128 S - 128 S$

and hence by (8)

$\displaystyle f(y_1) - f(x_{16}) + \sum_{i=1}^{15} W_{k_i} \in \sum_{i=1}^{16} (-1)^{i-1} g_1(h_i) + 248 S - 248 S$

where ${k_i := y_{i+1}-x_i}$ . Since

$\displaystyle y_1 - x_{16} + \sum_{i=1}^{15} k_i = 0$

we see that there are only ${N^{16}}$ possible values of ${(y_1,x_{16},k_1,\dots,k_{15})}$ . By the pigeonhole principle, we conclude that at most ${O(K^{O(1)})}$ of the sets ${\sum_{i=1}^{16} (-1)^i g_1(h_i) + 248 S - 248 S}$ can be disjoint. Arguing as before, we conclude that there exists a set ${X}$ of cardinality ${O(K^{O(1)})}$ such that

$\displaystyle \sum_{i=1}^{16} (-1)^{i-1} g_1(h_i) \in X + 496 S - 496 S \ \ \ \ \ (11)$

whenever (10) holds.

For any ${h \in 4A-4A}$ , write ${h}$ arbitrarily as ${h = \sum_{i=1}^8 (-1)^{i-1} h_i}$ for some ${h_1,\dots,h_8 \in A}$ (with ${h_5=\dots=h_8=0}$ if ${h \in 2A-2A}$ , and ${h_2 = \dots = h_8 = 0}$ if ${h \in A}$ ) and then set

$\displaystyle g(h) := \sum_{i=1}^8 (-1)^i g_1(h_i).$

Then from (11) we have (4). For ${h \in A}$ we have ${g(h) = g_1(h)}$ , and (5) then follows from (9). $\Box$

9 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 $X = \{ x^2 + y^2 - 1 = 0 \} \subseteq \mathbb{R}^2$ has rotational symmetry. We could call this group $\text{SO}_2(\mathbb{R})$ . The rational points on the circle should be “sort-of” rotationally symmetric. How can we express that mathematically?

We have $(a,b) \in \mathbb{Q}^2$ with $a^2 + b^2 = 1$ and the height of $ht(a),h(b) < N$ . I'm even straining to find the definition of "height" here… if $a = \frac{p_1}{q_1}, b = \frac{p_2}{q_2}$ as reduced fractions, then we have $ht[(a,b)] = \text{max}(p_1, q_1, p_2, q_2)$ .

This is a set of measure zero, $\mu[X(\mathbb{Q})] = 0$ 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 $f$ 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 $f:G\rightarrow H$ be a quasimorphism and let $g(x) = f(x) + D$ for all $x \in G$ and for a constant $D \in H$ .
Now $g(x+y) - g(x) - g(y) = f(x+y) - f(x) - f(y) - D$ .

By triangle-inequality we have $d(f(x+y)-f(x)-f(y)-D, 0) \le d(f(x+y)-f(x)-f(y), 0) +$
$d(f(x+y)-f(x)-f(y), f(x+y)-f(x)-f(y)-D)$ .

Now because $d$ is a translation invariant metric, the right side is equal to $O(1) + d(-D, 0)= O(1)$ .

[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 $f:Z\rightarrow R$ , there is no need to use (2) a second time.
To see it, first notice that your usage of $O(1)$ in (2) is implying this definition of Big-O notation (see also here):

$f(x)=O(g(x))$ if and only if there exist constants $N$ and $C$ such that $|f(x)| \le C |g(x)|$ for all $x > N$ .

Using this notation, we have $f(kx)/kx = f(x)/x + O(1/x)$ for $x \ne 0$ , then $\alpha = f(x)/x + O(1/x)$ for $x\ne 0$ , and then $f(x)=\alpha x + O(1)$ for all $x$ .

[The final use of (2) is needed to control $f$ for negative $x$ . -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 $f(x) = x + o(1)$ for some definition of “approximate” or “close” or “looks good” or “kinda-sorta”. Well… we could show that $f(x+y) = f(x) + f(y) + o(1)$ like you said.

Rarely do they use Additive Combinatorics. Sources suggest it could be a good a resource as any. They just don’t.

	Elizabeth Batory on On the recently removed paper…
	Anonymous on On the recently removed paper…
	Elizabeth Batory on On the recently removed paper…
	Maurice de Gosson on On the recently removed paper…
	Anonymous on Polymath15, tenth thread: nume…
	Wugga on On the recently removed paper…
	Anonymous on Polymath15, tenth thread: nume…
	Igor Rivin (@igriv) on On the recently removed paper…
	Anonymous on On the recently removed paper…
	Anonymous on On the recently removed paper…
	Anonymous on On the recently removed paper…
	Elizabeth Batory on On the recently removed paper…
	Igor Rivin (@igriv) on On the recently removed paper…
	Elizabeth Batory on On the recently removed paper…
	Marshall Flax on On the recently removed paper…

1% quasimorphisms and group cohomology

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

The Polymath Blog

9 comments

Leave a Reply Cancel reply

For commenters

1% quasimorphisms and group cohomology

Share this:

Like this:

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

The Polymath Blog

9 comments

Leave a Reply Cancel reply

For commenters