HOMOGENEOUS LENGTH FUNCTIONS ON GROUPS

arXiv:1801.03908v1 [] 11 Jan 2018

D.H.J. POLYMATH
Abstract. A pseudo-length function defined on an arbitrary group
G “ pG, ¨, e, p q´1 q is a map ` : G Ñ r0, `8q obeying `peq “ 0, the
symmetry property `px´1 q “ `pxq, and the triangle inequality `pxyq ď
`pxq ` `pyq for all x, y P G. We consider pseudo-length functions which
saturate the triangle inequality whenever x “ y, or equivalently those
that are homogeneous in the sense that `pxn q “ n `pxq for all n P N. We
show that this implies that `prx, ysq “ 0 for all x, y P G. This leads to
a classification of such pseudo-length functions as pullbacks from embeddings into a Banach space. We also obtain a quantitative version of
our main result which allows for defects in the triangle inequality or the
homogeneity property.

1. Introduction
Let G “ pG, ¨, e, p q´1 q be a group (written multiplicatively, with identity
element e). A pseudo-length function on G is a map ` : G Ñ r0, `8q that
obeys the properties
‚ `peq “ 0,
‚ `px´1 q “ `pxq,
‚ `pxyq ď `pxq ` `pyq
for all x, y P G. If in addition we have `pxq ą 0 for all x P Gzteu, we say
that ` is a length function. By setting dpx, yq :“ `px´1 yq, it is easy to see
that pseudo-length functions (resp. length functions) are in bijection with
left-invariant pseudometrics (resp. left-invariant metrics) on G.
From the axioms of a pseudo-length function it is clear that one has the
upper bound
`pxn q ď |n| `pxq
for all x P G and n P Z. Let us say that a pseudo-length function ` : G Ñ
r0, `8q is homogeneous if equality is always attained here, thus one has
`pxn q “ |n| `pxq

(1.1)

for all x P G and any n P Z. Using the axioms of a pseudo-length function,
it is not difficult to show that the homogeneity condition (1.1) is equivalent
to the triangle inequality holding with equality whenever x “ y (i.e., that
(1.1) holds for n “ 2); see [7, Lemma 1].
If one has a real or complex Banach space B “ pB, } }q, and φ : G Ñ B is
any homomorphism from G to B (viewing the latter as a group in additive
notation), then the function ` : G Ñ r0, `8q defined by `pxq :“ }φpxq} is
easily verified to be a homogeneous pseudo-length function. Furthermore,
2010 Mathematics Subject Classification. 20F12, 20F65.
Key words and phrases. homogeneous length function, pseudo-length function, quasimorphism, Banach space embedding.
1

2

D.H.J. POLYMATH

if φ is injective, then ` will in fact be a homogeneous length function. For
instance, the function
?
`ppn, mqq :“ |n ` 2m|
?
is a length function on Z2 , where in this case B :“ R and φpn, mq :“ n` 2m.
On the other hand, one can easily locate many length functions that are not
homogeneous, for instance by taking the square root of the length function
just constructed.
The main result of this paper is that such Banach space constructions are
in fact the only way to generate homogeneous (pseudo-)length functions.
Theorem 1.2 (Classification of homogeneous length functions). Given a
group G, let ` : G Ñ r0, `8q be a homogeneous pseudo-length function.
Then there exist a real Banach space B “ pB, } }q and a group homomorphism
φ : G Ñ B such that `pxq “ }φpxq} for all x P G. Furthermore, if ` is a
length function, one can take φ to be injective, i.e., an isometric embedding.
We will derive Theorem 1.2 from a more quantitative result bounding the
pseudo-length of a commutator
rx, ys :“ xyx´1 y ´1 ;

(1.3)

see Proposition 2.1 below. Our arguments will be elementary, relying on
directly applying the axioms of a homogeneous length function to various
carefully chosen words of x and y, and repeatedly taking an asymptotic limit
n Ñ 8 to dispose of various error terms that arise in the estimates obtained
in this fashion.
As one quick corollary of Theorem 1.2, we will obtain the following characterization of the groups that admit homogeneous length functions.
Corollary 1.4. A group admits a homogeneous length function if and only
if it is abelian and torsion-free.
1.1. Examples and approaches. We now make a few remarks to indicate the nontriviality of Theorem 1.2. Corollary 1.4 asserts in particular
that there are no non-abelian groups with homogeneous length functions.
Whether or not such a striking geometric rigidity phenomenon holds was
previously unknown to experts. Moreover, the corollary fails to hold if one
or more of the precise conditions in the theorem are weakened. For instance,
such pseudo-length functions indeed exist (i) on non-abelian monoids, and
(ii) on all balls of finite radius in free groups. We explain these two cases
further in Section 4.
Given these cases, one could a priori ask if every non-abelian group admits
a homogeneous length function. This is not hard to disprove; here are two
examples.
Example 1.5 (Nilpotent groups). If G is a nilpotent group of nilpotency
2
class 2 (such as the Heisenberg group), then one has the identity rx, ysn “
rxn , y n s for all x, y P G and natural numbers n (since the map pg, hq ÞÑ rg, hs
is now a bihomomorphism : GˆG Ñ rG, Gs Ă ZpGq). If rx, ys is non-trivial,
then any homogeneous length function on G would assign a linearly growing
quantity to the right-hand side and a quadratically growing quantity to the
left-hand side, which is absurd; thus such groups cannot admit homogeneous

HOMOGENEOUS LENGTH FUNCTIONS ON GROUPS

3

length functions. The claim then also follows for nilpotent groups of higher
nilpotency class, since they contain subgroups of nilpotency class 2.
Example 1.6 (Connected Lie groups). As we explain in Remark 2.8, a
homogeneous length function in fact induces a bi-invariant metric. Thus,
if G is a connected Lie group with a homogeneous length function, then by
[13, Lemma 7.5], G – K ˆ Rn for some compact Lie group K and integer
n ě 0. By (1.1), K cannot have torsion elements, hence must be trivial.
But then G is abelian.
Prior to Corollary 1.4, the above examples left open the question of
whether any non-abelian group admits a homogeneous length function. One
may as well consider groups generated by two non-commuting elements. As
a prototypical example, let F2 be the free group on two generators a, b. The
word length function on F2 is a length function, but it is not homogeneous,
since for instance the word length of pbab´1 qn “ ban b´1 is n ` 2, which is
not a linear function of n. (It is however the case that the word length of xn
has linear growth in n for any non-trivial x.) Similarly for the Levenshtein
distance (edit distance) on F2 .
Our initial attempts to construct homogeneous length functions on F2 all
failed in light of our main result. However, many of these methods apply
under minor weakening of the hypotheses, such as working with monoids
rather than groups, or weakening homogeneity. Results in these cases are
discussed further in Section 4.
1.2. Further motivations. We conclude this part with some motivations
from functional analysis and probability, or more precisely the study of
Banach space embeddings. If G is an additive subgroup of a Banach space
B, then clearly the norm on B restricts to a homogeneous length function
on G. In [4, 7] one can find several equivalent conditions for a given length
function on a given group to arise in this way (studied in the broader context
of additive mappings and separation theorems in functional analysis). These
conditions are summarized in the following:
Proposition 1.7 (see [10, Proposition 3.9]). Given a group G equipped with
a length function ` : G Ñ r0, `8q, the following are equivalent:
(1) There exists a Banach space B and a group homomorphism G Ñ B
that is an isometric embedding.
(2) G is abelian and dG px, yq :“ `px´1 yq is a translation-invariant metric
for which G is ‘normed’, i.e., dG pe, xn q “ |n| dG pe, xq for each x P G
and n P Z. In particular, G is torsion-free.
(3) G is t2u-normed pi.e., `px2 q “ 2`pxq for each x P Gq and is weakly
commutative, i.e., for all x, y P G there exists n “ npx, yq P N such
n
n
n
that pxyq2 “ x2 y 2 .
(4) G is t2u-normed and amenable.
In view of these equivalences, it is natural to try and characterize the
groups possessing a norm. This question is answered by Corollary 1.4, which
shows these are precisely the abelian torsion-free groups. Thus in assertion
(2), the hypothesis of admitting a ‘norm’ (i.e., homogeneous length function)

4

D.H.J. POLYMATH

is equivalent to that of being abelian and torsion-free; and hence one may
use either set of data to infer the remaining assertions in Proposition 1.7.
Groups and semigroups with translation-invariant metrics also naturally
arise in probability theory, with the most important ‘normed’ (i.e., homogeneous) examples being Banach spaces [12]. Notice however that in certain
fundamental stochastic settings, formulating – and proving – results does
not require the full Banach space structure. In this vein, a general variant
of the Hoffmann-Jørgensen inequality was shown in [9] in arbitrary metric
semigroups – including Banach spaces as well as (non-abelian) compact Lie
groups. Similarly in [10], the authors transferred the (sharp) Khinchin–
Kahane inequality from Banach spaces to abelian groups G equipped with a
homogeneous length function. To explore extensions of these results to the
non-abelian setting – e.g., of Lie groups with left-invariant metrics – we need
to first understand if such objects exist. As explained above, this question
was not answered in the literature; but it is now settled by our main result.
Finally, there may also be a relation to the Ribe program [14], which
aims to reformulate aspects of Banach space theory in purely metric terms.
Indeed, from Corollary 1.4 we see that a metric space X is isometric to
an additive subgroup of a Banach space if and only if there is a group
structure on X which makes the metric left-invariant and the length function
`pxq :“ dp1, xq homogeneous.
Acknowledgements
This project is an online collaboration that originated from a blog post
at https://terrytao.wordpress.com/2017/12/16, following the model of
the “Polymath” projects [8]. A full list of participants and their grant
acknowledgments may be found at
http://michaelnielsen.org/polymath1/index.php?title=linear_norm_
grant_acknowledgments

2. Key proposition
The key proposition used to prove Theorem 1.2 is the following estimate,
which can treat a somewhat more general class of functions than homogeneous pseudo-length functions, in which the symmetry hypothesis is dropped
and one allows for an error in the triangle inequality and the homogeneity
property (which is now only claimed for n “ 2).
Proposition 2.1. Let G “ pG, ¨q be a group, let c, c1 P R, and let ` : G Ñ R
be a function obeying the following axioms:
(i) For any x, y P G, one has
`pxyq ď `pxq ` `pyq ` c.

(2.2)

(ii) For any x P G, one has
`px2 q ě 2`pxq ´ c1 .

(2.3)

Then for any x, y P G, one has
`prx, ysq ď 4c ` 5c1 ,
where the commutator rx, ys was defined in (1.3).

(2.4)

HOMOGENEOUS LENGTH FUNCTIONS ON GROUPS

5

Notably, we neither assume symmetry `px´1 q “ `pxq, not even up to a
constant, nor `peq “ 0; we also allow ` to take on negative values. The
reader may however wish to restrict attention to length functions (and set
c “ c1 “ 0) for a first reading of the arguments below. The factors of 4, 5
are probably not optimal here, but the crucial feature of the bound (2.4) for
our application is that the right-hand side vanishes when c “ c1 “ 0.
For the remainder of this section, let G, c, c1 , and ` satisfy the hypotheses
of the proposition. Our task is to establish the bound (2.4). We shall now
use (2.2) and (2.3) repeatedly to establish a number of further inequalities
relating the pseudo-lengths `pxq of various elements x of G, culminating in
(2.4). Many of our inequalities will involve terms that depend on an auxiliary
parameter n, but we will be able to eliminate several of them by the device
of passing to the limit n Ñ 8. It is because of this device that we are able
to obtain a bound (2.4) whose right-hand side is completely uniform in x
and y.
From (2.2) and induction we have the approximate upper homogeneity
bound
`pxn q ď n`pxq ` pn ´ 1qc
(2.5)
for any natural number n ě 1. Similarly, from (2.3) and induction one has
the lower homogeneity bound
`pxn q ě n`pxq ´ pn ´ 1qc1
whenever n is a power of two. It is convenient to rearrange this latter
inequality as
`pxn q n ´ 1 1
`
c.
(2.6)
`pxq ď
n
n
This inequality (particularly in the asymptotic limit n Ñ 8) will be the
principal means by which the hypothesis (2.3) is employed.
We remark that by further use of (2.5) one can also obtain a similar
estimate to (2.6) for natural numbers n that are not powers of two1, but the
powers of two will suffice for the arguments that follow.
Lemma 2.7 (Approximate conjugation invariance). For any x, y P G, one
has
`pyxy ´1 q ď `pxq ` c ` c1 .
Remark 2.8. Setting c “ c1 “ 0, we conclude that any homogeneous
pseudo-length function is conjugation invariant, and thus determines a biinvariant metric on G. It should not be surprising that this observation is
used in the proof of Theorem 1.2, since it is a simple consequence of that
theorem.
Proof of Lemma 2.7. From (2.6) (with x replaced by yxy ´1 ) one has
`pyxn y ´1 q n ´ 1 1
`
c
n
n
whenever n is a power of two. On the other hand, from (2.5) and (2.2) one
has
`pyxn y ´1 q ď `pyq ` n`pxq ` `py ´1 q ` pn ` 1qc
`pyxy ´1 q ď

1For instance, this argument shows that if a pseudo-length function obeys the doubling
condition `px2 q “ 2`pxq for each x P G, then it is homogeneous; see also [7, Lemma 1].

6

D.H.J. POLYMATH

and thus
`pyxy ´1 q ď `pxq ` c ` c1 `

`pyq ` `py ´1 q ` c ´ c1
.
n

Sending n Ñ 8, we obtain the claim.



Lemma 2.9 (Splitting lemma). Let x, y, z, w P G be such that x is conjugate
to both wy and zw´1 . Then one has
`pyq ` `pzq 3
`pxq ď
` pc ` c1 q.
(2.10)
2
2
Proof. If we write x “ swys´1 “ tzw´1 t´1 for some s, t P G, then from
(2.6) we have
`pxn xn q 2n ´ 1 1
`
c
2n
2n
`pspwyqn s´1 tpzw´1 qn t´1 q 2n ´ 1 1
“
`
c
2n
2n
whenever n is a power of two. From Lemma 2.7 and (2.2) one has
`pxq ď

`ppwyqk`1 s´1 tpzw´1 qk`1 q “ `pwypwyqk s´1 tpzw´1 qk zw´1 q
ď `pypwyqk s´1 tpzw´1 qk zq ` c ` c1
ď `ppwyqk s´1 tpzw´1 qk q ` `pyq ` `pzq ` 3c ` c1
for any k ě 0, and hence by induction
`ppwyqn s´1 tpzw´1 qn q ď `ps´1 tq ` np`pyq ` `pzq ` 3c ` c1 q.
Inserting this into the previous bound for `pxq (via two applications of (2.2)),
we conclude that
`pyq ` `pzq ` 3c ` c1 `psq ` `ps´1 tq ` `pt´1 q ` 2c 2n ´ 1 1
`
`
c;
`pxq ď
2
2n
2n
sending n Ñ 8, we obtain the claim.

Corollary 2.11. If x, y P G, let f “ fx,y : Z2 Ñ R denote the function
f pm, kq :“ `pxm rx, ysk q.
Then for any m, k P Z, we have
f pm ´ 1, kq ` f pm ` 1, k ´ 1q
` 2pc ` c1 q.
f pm, kq ď
2

(2.12)

Proof. Observe that xm rx, ysk is conjugate to both xpxm´1 rx, ysk q and to
py ´1 xm rx, ysk´1 xyqx´1 , hence by (2.10) one has
`pxm´1 rx, ysk q ` `py ´1 xm rx, ysk´1 xyq 3
` pc ` c1 q.
2
2
´1
m
k´1
m`1
k´1
Since y x rx, ys xy is conjugate to x
rx, ys , the claim now follows
from Lemma 2.7.

`pxm rx, ysk q ď

We now prove Proposition 2.1. Let x, y P G. We can write the inequality
(2.12) in probabilistic form as
ˆˆ
˙
ˆ
˙˙
1
1
f pm, kq ď Ef
m, k ´
` Y 1, ´
` 2pc ` c1 q
2
2

HOMOGENEOUS LENGTH FUNCTIONS ON GROUPS

7

where Y “ ˘1 is a Bernoulli random variable `that equals
1 or ´1 with equal
˘
probability. The key point here is the drift of 0, ´ 21 in the right-hand side.
Iterating this inequality, we see that if we let n be a large power of 2, then
we have
˙˙
ˆ
ˆ
1
` 4pc ` c1 qn,
f p0, nq ď Ef pY1 ` ¨ ¨ ¨ ` Y2n q 1, ´
2
where Y1 , . . . , Y2n are independent copies of Y (so in particular Y1 `¨ ¨ ¨`Y2n
is an even integer).
From (2.2) and (2.5) one has the inequality
`
˘
f pm, kq ď |m| maxp`pxq, `px´1 qq ` c
`
˘
`|k| maxp`prx, ysq, `prx, ys´1 qq ` c ` `peq
(the final term being needed to deal with the m “ k “ 0 case). We conclude
that
ˆ
ˆ
˙˙
1
f pY1 ` ¨ ¨ ¨ ` Y2n q 1, ´
ď A|Y1 ` ¨ ¨ ¨ ` Y2n | ` `peq
2
where A is a quantity independent of n; more explicitly, one can take
`
˘ 1
`
˘ 3
A :“ max `pxq, `px´1 q ` max `prx, ysq, `prx, ys´1 q ` c.
2
2
Taking expectations, since the random variable Y1 ` ¨ ¨ ¨ ` Y2n has mean zero
and variance 2n, we see from the Cauchy–Schwarz inequality (or Jensen’s
inequality) that
`
˘1{2 ?
E|Y1 ` ¨ ¨ ¨ ` Y2n | ď E|Y1 ` ¨ ¨ ¨ ` Y2n |2
“ 2n
and hence

?
f p0, nq ď A 2n ` `peq ` 4pc ` c1 qn.

But from (2.6) we have
`prx, ysq ď

f p0, nq n ´ 1 1
`
c.
n
n

Combining these two bounds and sending n Ñ 8, we obtain Proposition 2.1.
Remark 2.13. As discussed in the footnote preceding Lemma 2.7, if c “ 0
then the condition c1 “ 0, or equivalently `px2 q “ 2`pxq for all x P G, is in
turn equivalent to `pxk q “ k`pxq for all x P G, for any k ě 2. One can thus
ask if (2.3) can be replaced by a similar condition of the form
`pxk q ě k`pxq ´ c1
for some k ě 2. We claim that such a condition essentially implies (2.3).
Indeed, using the triangle inequality for xk “ px2 qtk{2u xδ where δ “ 0, 1, we
obtain:
k`pxq ´ c1 ď `pxk q ď Opkq`px2 q ` c Opkq,
which in turn implies `px2 q ě Op1q`pxq ´ Op1qc ´ c1 {k.

8

D.H.J. POLYMATH

Remark 2.14. One can deduce a ‘local’ version of Proposition 2.1 as follows:
notice that the constants c, c1 can be described in terms of ` from (2.2) and
(2.3), to yield
˜
¸
ˆ
˙
2
`prx, ysq ď 4 sup `pzwq ´ `pzq ´ `pwq ` 5 sup 2`pzq ´ `pz q , (2.15)
z,wPG

zPG

for any group G and function ` : G Ñ R, and any x, y P G. (Both sides are
zero when G is a Banach space and ` is the norm, so equality is obtained
in that case.) Now it is enough to consider G “ xx, yy without loss of
generality, which may lead to a better bound on `prx, ysq than taking the
suprema over all of G. Notice also that at least one of the constants c, c1
must be non-negative, from (2.2) with x “ y and (2.3):
(
maxtc, c1 u ě max `pe2 q ´ 2`peq, 2`peq ´ `pe2 q “ maxt´`peq, `pequ ě 0.
(2.16)
In fact, this reasoning and our results imply that the only way to get c “ c1 “
0 on the right-hand side of (2.15) is when ` arises from pulling back the norm
of a Banach space B along a group homomorphism G Ñ B, or equivalently
along a group homomorphism from the torsion-free abelianization of G to
B.
3. Proof of main theorem
With Proposition 2.1 in hand, it is not difficult to conclude the proof of
Theorem 1.2. Suppose that G is a group with a homogeneous pseudo-length
function ` : G Ñ r0, `8q. Applying Proposition 2.1 with c “ c1 “ 0, we
conclude that `prx, ysq “ 0 for all x, y P G, thus by the triangle inequality `
vanishes on the commutator subgroup rG, Gs, and therefore factors through
the abelianization Gab :“ G{rG, Gs of G. (This already establishes part of
one implication of Corollary 1.4.) Factoring out by rG, Gs like this, we may
now assume without loss of generality that G is abelian. To reflect this, we
now use additive notation for G, thus for instance `pnxq “ |n|`pxq for each
x P G and n P Z, and one can also view G as a module over the integers Z.
At this point we repeat the arguments in [10, Theorem B], which treated
the case when G was separable, though it turns out that this separability
hypothesis is unnecessary.
If x is a torsion element of G (thus nx “ 0 for some n), then the homogeneity condition forces `pxq “ 0. Thus ` vanishes on the torsion subgroup
of G; factoring out by this subgroup, we may thus assume without loss of
generality that G is not only abelian, but is also torsion-free.
We can view G as a subgroup of the Q-vector space G bZ Q, the elements
of which can be formally expressed as n1 x for natural numbers n and elements
1
x P G (with two such expressions n1 x, m
y identified if and only if mx “ ny,
and the Q-vector space operations defined in the obvious fashion); the fact
that this is well defined as a Q-vector space follows from the hypotheses
that G is abelian and torsion-free. We can then define a seminorm } }Q :
G bZ Q Ñ r0, `8q by setting
› ›
›1 ›
› x› :“ 1 `pxq
›n ›
n
Q

HOMOGENEOUS LENGTH FUNCTIONS ON GROUPS

9

for any x P G and natural number n; the linear growth condition ensures that
} }Q is well-defined. It is not difficult to verify the homogeneity condition
}qx}Q “ |q|}x}Q
and the triangle inequality
}x ` y}Q ď }x}Q ` }y}Q
for all x, y P G bZ Q and q P Q, so that } }Q is indeed a seminorm over the
Q-vector space G bZ Q.
The Q-vector space G bZ Q may be embedded in turn into the R-vector
space G bZ R “ pG bZ Qq bQ R, elements of which take the form α1 x1 ` ¨ ¨ ¨ `
αk xk for some x1 , . . . , xk P G bZ Q and α1 , . . . , αk P R. We identify two such
elements α1 x1 `¨ ¨ ¨`αk xk , β1 y1 `¨ ¨ ¨`βl yl if and only if there are Q-linearly
independent elements z1 , . . . , zm P G bZ Q and coefficients ařin , bjn P Q for
i “ 1, . . . , k, j “ 1, . . . , l, n “ 1, . . . , m such that xi “ m
n“1 ain zn for
řm
ř
each i “ 1, . . . , k, yj “ n“1 bjn zn for each j “ 1, . . . , l, and ki“1 αi ain “
řl
j“1 βj bjn for each n “ 1, . . . , m; one can check that this criterion does not
depend on the precise choice of linearly independent elements z1 , . . . , zm ,
so long as their span contains all of the x1 , . . . , xk , y1 , . . . , yl .2 It is easy to
verify3 that G bZ R has the structure of an R-vector space that contains
G bZ Q (and hence G). We can extend the seminorm } }Q to G bZ R by
setting
}α1 x1 ` ¨ ¨ ¨ ` αk xk }R :“

lim
pq1 ,...,qk qÑpα1 ,...,αk q

}q1 x1 ` ¨ ¨ ¨ ` qk xk }Q

where pq1 , . . . , qk q is restricted to Qk . For any given α1 , . . . , αk , x1 , . . . , xk it
is easy to see using the triangle inequality and homogeneity that the limit
exists. We still need to verify that the seminorm is well-defined, in the sense
that
}α1 x1 ` ¨ ¨ ¨ ` αk xk }R “ }β1 y1 ` ¨ ¨ ¨ ` βl yl }R
whenever α1 x1 ` ¨ ¨ ¨ ` αk xk “ β1 y1 ` ¨ ¨ ¨ ` βl yl . By the triangle inequality
it suffices to verify this at the origin, or more precisely that
lim
pq1 ,...,qk qÑpα1 ,...,αk q

}q1 x1 ` ¨ ¨ ¨ ` qk xk }Q “ 0

whenever x1 , . . . , xk P G bZ Q and α1 , . . . , αk P R are such that α1 x1 ` ¨ ¨ ¨ `
αk xk “ 0. To prove this one can induct on k, the case k “ 0 being trivial.
2Stated slightly differently, let z , . . . , z denote a Q-basis of the Q-span of the x , y ,
1
m
i
j

and define the vector z :“ pz1 , . . . , zm qT by abuse of notation; similarly define x, y, α, β.
Then x “ Az, y “ Bz for matrices A P Qkˆm , B P Qlˆm , and we identify αT x “ β T y if
and only if αT A “ β T B.
3
One subtle point is that if G is already embedded inside an existing R-vector space V ,
then the vector space G bZ R constructed here is not necessarily a subspace of that vector
space (although
there will be a canonical linear map from G bZ R to V ). For instance, if
?
G “ x1, 2y Ă R, then while G is contained in a one-dimensional
R-vector space, G bZ R
?
is in fact two-dimensional (with the generators 1 and 2 of G forming a R-basis of this
space); the point is that the vector space operations on G bZ R do not agree in this case
with
those of the ambient vector space R, for instance in G bZ ?
R the second generator
?
2 is not equal to the scalar multiple of the first generator 1 by 2. To avoid confusion,
we recommend to the reader that they view G as an abstract group that is not already
embedded into an existing R-vector space.

10

D.H.J. POLYMATH

If one of the x1 , . . . , xk is a Q-linear combination of the others, then we can
eliminate it and invoke the induction hypothesis for k ´1, so we may assume
without loss of generality that the x1 , . . . , xk are linearly independent over
Q. But then, by construction of G bZ R, the condition α1 x1 ` ¨ ¨ ¨ ` αk xk “ 0
forces α1 “ ¨ ¨ ¨ “ αk “ 0, and the claim now follows from the triangle
inequality and homogeneity.
By construction, } }R : GbZ R Ñ r0, `8q obeys the homogeneity condition
}αx}R “ |α|}x}R
and the triangle inequality
}x ` y}R ď }x}R ` }y}R
for all x, y P G bZ R and α P R; thus } }R is a seminorm on G bZ R.
By the usual metric completion device of taking formal Cauchy sequences
and factoring out the elements that converge to zero, we can find a real
Banach space B “ pB, } }B q and an R-linear map φ : G bZ R Ñ B such that
}x}R “ }φpxq}B for each x P G bZ R. (In fact, as observed in [10], one can
directly take the metric space completion of G bZ Q without first passing to
G bZ R.) It is now clear that φ restricts to a homomorphism from G to B
such that `pxq “ }φpxq}B for each x P G. Finally, if ` is a length function,
then }φpxq}B must be non-zero for each x ‰ e, which implies that the kernel
of φ is trivial and hence φ is injective.
This concludes the proof of Theorem 1.2. Since the homomorphism φ :
G Ñ B can only be injective for abelian torsion-free G, we obtain the “only
if” portion of Corollary 1.4. Conversely, if a group G is abelian and torsionfree, by the above constructions it embeds into a real vector space B :“
G bZ R; now by Zorn’s lemma B has a norm (e.g., consider the `1 norm with
respect to a Hamel basis of B), which restricts to the desired homogeneous
length function on G. We remark, as also mentioned in [10], that G bZ R is
the construction of the smallest, ‘enveloping’ vector space containing a copy
of the abelian, torsion-free group G.
Remark 3.1. The above arguments also show that homogeneous pseudolength functions on G are in bijection with seminorms on the real vector
space Gab,0 bZ R, where Gab,0 denotes the torsion-free abelianization of G.
4. Further remarks and results
One could ask if the homogeneity condition can be relaxed to an asymptotic homogeneity condition
`pxn q
“ `pxq, for each x P G.
nÑ8
n
lim

In fact this condition is equivalent to homogeneity, since for all positive
integers m P N, the sequence t`pxmn q{pmnq : n ě 1u would converge as
n Ñ 8 to both `pxq and `pxm q{m.
However, if we weaken any of several conditions in the above formulations,
then examples of such structures do, in fact, exist. Here we mention several
such cases and discuss other related problems.

HOMOGENEOUS LENGTH FUNCTIONS ON GROUPS

11

4.1. Monoids and embeddings. Our first weakening is to replace ‘groups’
by the more primitive structures ‘monoids’ or ‘semigroups’. In this case,
Robert Young (private communication) described to us non-abelian monoids
with homogeneous, bi-invariant length functions: consider the free monoid
FMonpXq on any alphabet X of size at least 2, with the ‘edit’ distance
dpv, wq between strings v, w P FMonpXq being the least number of single
generator insertions and deletions to get from v to w. The triangle inequality
and positivity are easily verified, while homogeneity of the corresponding
length function `pxq :“ dpe, xq is trivial. Moreover, the metric dp¨, ¨q turns
out to be bi-invariant:
dpgxh, gyhq “ dpx, yq for all g, h, x, y P FMonpXq.
This specializes to left- and right-invariance upon taking g P X and h “ e,
or h P X and g “ e, respectively.
Note moreover that FMonpXq embeds into FGppXq (the free group generated by X and X ´1 , the collection of symbols defined to be inverses of
elements of X), and in particular, is cancellative. While this trivially addresses the embeddability issue, notice that a more refined version of embeddability fails. Namely, by our main theorem, FMonpXq does not embed
into any group in the category Cbi´inv, hom with cancellative semigroups with
homogeneous bi-invariant metrics as objects and isometric semigroup maps
as morphisms. Thus, one may reasonably ask what is a sufficiently small
category in which the embeddability works.
Proposition 4.1. Let Cbi´inv denote the category whose objects are cancellative semigroups with bi-invariant metrics, and morphisms are isometric semigroup maps. Then FMonpXq embeds isometrically into FGppXq in
Cbi´inv .
Proof. From above, FMonpXq is an object of Cbi´inv ; denote the metric by
dF M . One can check that dF M pw, w1 q equals the difference lpwq ` lpw1 q (the
sum of the lengths in X) minus twice the length of the longest common
(possibly non-contiguous) substring in w, w1 .
We next claim FGppXq is also an object of Cbi´inv . Namely, for a word
w “ x1 x2 ¨ ¨ ¨ xm in the free group, we consider non-crossing matchings in w,
i.e., sets M of pairs of letters in t1, 2, . . . mu such that the following hold.
‚ If pi, jq P M , then i ă j and xj “ x´1
i .
‚ If pi, jq P M and pk, lq P M , then either pi, jq “ pk, lq or i, j, k and l
are distinct.
‚ If i ă k ă j ă l and pi, jq P M , then pk, lq R M .
Given a matching M as above, consider the set U “ U pM q of indices k,
1 ď k ď m which are not part of a pair in M . Define the deficiency of the
matching M as the cardinality of the set U pM q, and define the length `pwq of
the word w as the infimum of the deficiency over all non-crossing matchings
in w. This length was previously studied in [6], including checking that it is
well-defined on all of FGppXq; moreover, `pwq equals the smallest number
of conjugates of elements in X \ X ´1 whose product is w. Now define
dF G pw, w1 q :“ `pw´1 w1 q. It is easy to see that ` is a conjugacy invariant
length function.

12

D.H.J. POLYMATH

We claim that dF G ” dF M on FMonpXq, which proves the result. It is
easy to show that if two words in FMonpXq differ by a single insertion or
deletion, then their distance in FGppXq is at most one, hence exactly one.
In the other direction, we claim that a non-crossing matching on w´1 w1 ,
with w and w1 containing only positive generators (in X), is just a ‘rainbow’, i.e. nested arches with one end in w´1 and the other in w1 . But
then dF G pw, w1 q equals lpwq ` lpw1 q minus twice the length of a common
substring, which is maximal by the minimality of the deficiency. Hence
dF G pw, w1 q “ dF M pw, w1 q, completing the proof.

4.2. Quasi-pseudo-length functions via quasimorphisms. We see that
Proposition 2.1 is also of interest for c ą 0, as follows. A quasi-morphism
on a group G is a map f : G Ñ R whose defect is bounded,
Dpf q :“ sup |f pxyq ´ f pxq ´ f pyq| ă `8.
x,yPG

Let us use the term quasi-pseudo-length function for a function ` : G Ñ
r0, `8q which satisfies the relaxed triangle inequality (2.2) for some c. Then
every quasi-morphism as above induces a quasi-pseudo-length function by
setting
`pxq :“ |f pxq|,
(4.2)
where we can take c “ Dpf q.
A quasi-morphism is homogeneous if f pxn q “ nf pxq for n P N. Replacing
any quasi-morphism f by limnÑ8 f pxn q{n results in a homogeneous quasimorphism. (Note that this limit exists by the de Bruijn–Erdös generalization
[3, Theorem 23] of Fekete’s subadditive lemma.) A homogeneous quasimorphism defines a quasi-pseudo-length function that is homogeneous.4 In
this case, Proposition 2.1 makes a rather trivial statement: a homogeneous
quasi-morphism is bounded on commutators,
|f prx, ysq| ď 4Dpf q.
In fact, as observed in [1, Lemme 1.1], one can improve the constant 4 to 3
in this case.
Nevertheless, quasi-morphisms can be utilized to construct interesting
quasi-pseudo-length functions, for example satisfying homogeneity on specific commutators. The following quasi-morphism is due to Brooks [5, Section 2]. For a given word w in the free group F2 , written in reduced form, let
fw : F2 Ñ R be the function which assigns to every other g P F2 , also written
in reduced form, the maximum number of times such that w occurs in g without overlaps, minus the analogous number of times that w´1 can maximally
occur in g. Since fw pwn q “ nfw pwq, homogenizing this quasi-morphism and
taking the absolute value results in a quasi-pseudo-length function that is
4Of course, homogeneous quasi-morphisms must satisfy

sup |f peq ´ f pg n q ´ f pg ´n q| “ sup |f peq ´ npf pgq ` f pg ´1 qq| ă 8,
ně1
´1

ně1

whence f pg q “ ´f pgq for all g P G. On the other hand, if f ı 0 then the corresponding
homogeneous quasi-pseudo-length function ` :“ |f | never has bounded defect, since if
f pgq ‰ 0 then inf ně0 `peq ´ `pg n q ´ `pg ´n q “ inf ně0 ´2n`pgq “ ´8. So in a sense, the
two concepts are ‘morally different’.

HOMOGENEOUS LENGTH FUNCTIONS ON GROUPS

13

homogeneous on the powers of w. For example with w being the commutator of the generators of F2 , we see that although the quasi-pseudo-length
function must be bounded on commutators by Proposition 2.1, it can nevertheless grow linearly on the powers of a fixed commutator.
4.3. Finite balls in free groups. From Proposition 2.1 and a standard
compactness argument, we can establish the following local version of the
theorem.
Theorem 4.3. For any ε ą 0 there exists R ě 4 with the following property:
if a, b are two elements of a group G, Ba,b pRq Ă G is the collection of all
words in a, b, a´1 , b´1 of length at most R pso in particular Ba,b pRq contains
ra, bsq, and the map ` : Ba,b pRq Ñ r0, `8q is a “local pseudo-length function”
which obeys the triangle inequality
`pxyq ď `pxq ` `pyq

(4.4)

whenever x, y, xy P Ba,b pRq, with equality when x “ y, then one has
`pra, bsq ď εp`paq ` `pbqq.
Proof. By pulling back to the formal group generated by a and b, we may
assume without loss of generality that G is the free group generated by a and
b. Without loss of generality we may also normalize `paq ` `pbq “ 1. If the
claim failed, then one could find a sequence Rn Ñ 8 and local pseudo-length
functions `n : Ba,b pRn q Ñ r0, `8q such that `n paq ` `n pbq “ 1, but that
`n pra, bsq ě ε. By the Arzela–Ascoli theorem, we can pass to a subsequence
that converges pointwise to a homogeneous pseudo-length function ` : G Ñ
r0, `8q such that `pra, bsq ě ε, which contradicts Proposition 2.1.

Remark 4.5. By carefully going through the arguments in the previous
section, choosing n to be various small powers of R instead of sending n
to infinity, one can extract an explicit value of R of the form R “ Cε´A
for some absolute constants C, A ą 0; we leave the details to the interested
reader.
On the other hand, for any finite R one can construct local pseudo-length
functions ` : Bp0, Rq Ñ r0, `8q such that `pxq ą 0 for all x P Bp0, Rqzteu.
One construction is as follows. Any two matrices Ua , Ub P SOp3q define a
representation x ÞÑ Ux of the free group F2 in the obvious fashion. Every
Ux is then a rotation around some axis in R3 by some angle 0 ď θ ď π
in one of the two directions around that axis; if Ua and Ub are sufficiently
close to the identity, then the angle of rotation of Ux will be at most π{2 for
all x P Bp0, Rq. We set `pxq to be equal to this angle of rotation. Also, if
Ua , Ub are chosen generically, the representation will be faithful (this follows
from the dominance of word maps on simple Lie groups such as SOp3q, see
[2]), so `pxq ą 0 for any non-identity x. From the triangle inequality for
angles we thus have (4.4) whenever x, y, xy P Bp0, Rq, with equality when
x “ y. Note that as one sends R Ñ 8, the local pseudo-length functions
constructed here converge to zero pointwise, so in the limit we do not get
any counterexample to the main theorem.

14

D.H.J. POLYMATH

4.4. Quasi-norms and commutator lengths. Our main result is a classification theorem for homogeneous pseudo-length functions. We will see next
that even in the case of homogeneous quasi-length functions, i.e., where we
replace `pxyq ď `pxq ` `pyq by `pxyq ď `pxq ` `pyq ` c for a fixed constant
c ě 0, we get non-trivial restrictions on these functions which give the main
result in the case when c “ 0. Further, we see that the restrictions we obtain
are essentially the strongest possible.
Recall that the commutator length clpgq of a word in rG, Gs is the length k
of the shortest expression g “ ra1 , b1 s ¨ ra2 , b2 s ¨ ¨ ¨ rak , bk s of g as a product of
commutators. The stable commutator length is defined as limnÑ8 clpg n q{n,
where the limit exists by sub-additivity of the function n ÞÑ clpg n q.
Then Proposition 2.1, together with (2.2), (2.6), easily imply the following
estimates:
Proposition 4.6. Let `, c, c1 be as in Proposition 2.1. Then for g P
rG, Gszteu, `pgq ď 5pc ` c1 q clpgq ´ c and `pgq ď 5pc ` c1 q sclpgq ` c1 .
Observe that in various cases where we do not have a (quasi-)homogeneous
quasi-norm, we get much weaker bounds. For example, consider the word
rak , bm s in the free group F2 , generated by a and b, for some integers k and
m.
‚ The norm of such an element with respect to the word metric is
2p|k| ` |m|q.
‚ If we have a length function ` which is symmetric and conjugationinvariant (but not assumed to be homogeneous), then we have the
bound `prak , bm sq ď 2 minp|k| `paq, |m| `pbqq. Furthermore, there are
conjugation-invariant length functions for which these inequalities
hold with equality.
Namely, fix positive real numbers `paq and `pbq; now given a word
w “ x1 ¨ ¨ ¨ xm , consider the set U “ U pM q of indices k, 1 ď k ď m
which are not part of a pair in a matching M ; here M is defined
as in the proofřof Proposition 4.1. Now define the deficiency of
M as the sum iPU `pxi q, and as in loc. cit., define `pwq to be the
infimum of the deficiency over all non-crossing matchings in w. Then
` is a conjugation-invariant length function. Further, `prak , bm sq ě
2 minp|k| `paq, |m| `pbqq as, for any matching M for w “ rak , bm s,
if some pair pi, jq corresponds to letters a and a´1 , then no pair
corresponds to letters b and b´1 and conversely. Further, it is easy to
find a matching for which the deficiency is minp|k| `paq, |m| `pbqq. On
the other hand, ` is not homogeneous; for instance, `pra, bsq “ 2 and
`pra, bs3 q “ 4. Similarly, we have `prak , bk sq “ 2|k| and `prak , bk s3 q ď
4|k|, which demonstrates that 2`pxq ´ `px2 q is unbounded (as must
be the case, according to (2.15)).
‚ On the other hand, the function ` associating to each word the length
of its cyclically reduced form is homogeneous but not a quasi-length
function. For this we have `prak , bm sq “ 2p|k| ` |m|q.
Observe that all of the bounds on `prak , bm sq here become unbounded as
k, m Ñ 8. This should be compared with Proposition 2.1, which establishes

HOMOGENEOUS LENGTH FUNCTIONS ON GROUPS

15

a bound `prak , bm sq ď 4c ` 5c1 that is uniform in k and m for any function
` satisfying the hypotheses of that proposition.
Now we show that the bound in Proposition 2.1 is essentially sharp for
every finitely generated group G. By assumption, also the abelianization
Gab :“ G{rG, Gs is finitely generated. For simplicity of notation, assume
Gab is torsion-free. Let x1 , x2 , . . . , xk be the generators of Gab – Zk and
let ϕ : G Ñ Gab be the abelianization map. Let αi : G Ñ Z for i “ 1, . . . , k
be the homomorphisms such that for all g P G,
ϕpgq “

k
ÿ

αi pgqxi .

i“1

Choose and fix elements yi P G such that ϕpyi q “ xi . We define a function
ψ : G Ñ R by
´α pgq ´α pgq
´α pgq
ψpgq “ clpgy1 1 y2 2 ¨ ¨ ¨ yk k q.
Repeatedly using relations of the form clpbaq “ clpbara´1 , b´1 sq ď clpabq`
1, we see that
ψpg1 g2 q ď ψpg1 q ` ψpg2 q ` p2k ` 1q,
i.e., ψ is a quasi-pseudo-length function. Further, by similar arguments we
see that
|ψppxyqn q ´ ψpxn y n q| ď n,
from which we deduce that on replacing ψ by its homogenization (via [3,
Theorem 23]), we still get a quasi-pseudo-length function.
Therefore, we can define functions satisfying Proposition 2.1 which are
homogeneous by considering a length function `Gab on Gab and taking the
linear combination
c
ψpgq.
`pgq :“ `Gab pϕpgqq `
2k ` 1
This gives a homogeneous function satisfying the hypotheses of Proposition 2.1 while being strictly positive on all nontrivial elements.
References
[1] C. Bavard, Longueur stable des commutateurs, L’Enseignement Mathématique, 37(1–
2):109–150, 1991.
[2] A. Borel, On free subgroups of semisimple groups, L’Enseignement Mathématique,
29(1–2):151–164, 1983.
[3] N.G. de Bruijn and P. Erdös, Some linear and some quadratic recursion formulas. II,
Indagationes Mathematicae, 55:152–163, 1952.
[4] F. Cabello Sánchez and J.M.F. Castillo, Banach space techniques underpinning a theory for nearly additive mappings, Dissertationes Mathematicae (Rozprawy Matematyczne), 404:1–73, 2002.
[5] K. Fujiwara, Quasi-homomorphisms on mapping class groups, Handbook of Teichmüller theory. Vol. II, 241–269, IRMA Lect. Math. Theor. Phys., 13, Eur. Math.
Soc., Zürich, 2009.
[6] S. Gadgil, Watson–Crick pairing, the Heisenberg group and Milnor invariants, Journal
of Mathematical Biology 59(1), Article:123, 2009.
[7] Z. Gajda and Z. Kominek, On separation theorems for subadditive and superadditive
functionals, Studia Mathematica, 100(1):25–38, 1991.
[8] T. Gowers and M. Nielsen, Massively collaborative mathematics, Nature,
461(7266):879–881, 2009.

16

D.H.J. POLYMATH

[9] A. Khare and B. Rajaratnam, The Hoffmann-Jørgensen inequality in metric semigroups, Annals of Probability, 45(6A):4101–4111, 2017.
[10] A. Khare and B. Rajaratnam, The Khinchin–Kahane inequality and Banach space
embeddings for metric groups, preprint (arXiv:1610.03037), 2016.
[11] S. Kobayashi, Hyperbolic Manifolds and Holomorphic Mappings, World Scientific,
1970.
[12] M. Ledoux and M. Talagrand, Probability in Banach Spaces (Isoperimetry and Processes), Ergebnisse der Mathematik und ihrer Grenzgebiete, Springer-Verlag, BerlinNew York, 1991.
[13] J. Milnor, Curvatures of left invariant metrics on lie groups, Advances in Mathematics, 21(3):293–329, 1976.
[14] A. Naor, An introduction to the Ribe program, Japan Journal of Mathematics, 7:167–
233, 2012.
http://michaelnielsen.org/polymath1/index.php

