This post is a continuation of the previous post, which has attracted a large number of comments. I’m recording here some calculations that arose from those comments (particularly those of Pace Nielsen, Lior Silberman, Tobias Fritz, and Apoorva Khare). Please feel free to either continue these calculations or to discuss other approaches to the problem, such as those mentioned in the remaining comments to the previous post.

Let be the free group on two generators , and let be a quantity obeying the triangle inequality

and the linear growth property

for all and integers ; this implies the conjugation invariance

or equivalently

We consider inequalities of the form

or

for various real numbers . For instance, since

we have (1) for . We also have the following further relations:

**Proposition 1**

- (i) If (1) holds for , then it holds for .
- (ii) If (1) holds for , then (2) holds for .
- (iii) If (2) holds for , then (1) holds for .
- (iv) If (1) holds for and (2) holds for , then (1) holds for .

*Proof:* For (i) we simply observe that

For (ii), we calculate

giving the claim.

For (iii), we calculate

giving the claim.

For (iv), we calculate

giving the claim.

Here is a typical application of the above estimates. If (1) holds for , then by part (i) it holds for , then by (ii) (2) holds for , then by (iv) (1) holds for . The map has fixed point , thus

For instance, if , then .

### Like this:

Like Loading...

## 96 comments

Comments feed for this article

19 December, 2017 at 10:49 pm

Lior SilbermanTrying again, the fixed point of (iv) is .

20 December, 2017 at 12:18 am

Siddhartha GadgilThis has become redundant since a nice bound below 1 has been found, but (for completeness) I have a computer generated proof that has norm less than 5, hence the commutator has norm less than one. This is a proof in the sense of the structure at

https://github.com/siddhartha-gadgil/Superficial/blob/master/src/main/scala/freegroups/LinNormBound.scala with the proof itself at

https://github.com/siddhartha-gadgil/Superficial/blob/master/pf6raw.txt

I will format stuff better when I have a better bound.

20 December, 2017 at 12:40 am

Tobias FritzWouldn’t it also be possible to consider the system from Proposition 1 as one big iteration, ? The unique fixed point of this is . Thus we obtain .

Can this be right? I feel like I’ve made a mistake somewhere.

If it is correct, then we would also have , which may lead to further improvements when plugged into Terry’s argument for (ii).

20 December, 2017 at 2:16 am

Pace NielsenAre you using (iv) to get those new values? Those should be values if so.

20 December, 2017 at 2:27 am

Tobias FritzAh of course, thanks!

20 December, 2017 at 1:23 am

Tobias FritzHere are some (more or less straightforward) thoughts on the current status.

1) If we can prove that , then it follows that every norm on any group arises by pullback from the abelianization . This is because it’s enough to show that the norm of any commutator vanishes, but by pulling back to , it’s enough to show . And on , the norms are in bijection with norms on the vector space . In this sense, we’d have a complete classification.

2) So optimally, we’d like to derive estimates like in Proposition 1, but without any constant terms; currently there still is a constant in (ii). But this would require bounding the norm of an element of the commutator subgroup only in terms of other elements of the commutator subgroup. (Since outside of the commutator subgroup, we obviously cannot expect the norm to vanish.) So effectively, we’d be looking at norms on the commutator subgroup. But then we cannot hope to prove that every such norm must vanish, since this is not the case: the commutator subgroup again has nontrivial abelianization.

In conclusion, I think that if there is an argument for in the style of Proposition 1, then it will necessarily involve an infinite sequence of terms giving better and better bounds.

3) Linear programming duality suggests that if is necessarily true, then there indeed must be an argument of this type which proves it. (It should be possible to make this reasoning rigorous via the Hahn-Banach theorem for order unit spaces; the collection of all length functions on is the positive cone of an order unit space, with generator word length as order unit.)

20 December, 2017 at 3:28 am

Tobias FritzConcerning (iii), here’s an argument that reduces the factor of in both components to : the power is a product of four terms of type . But this is conjugate to .

20 December, 2017 at 6:25 am

Lior SilbermanThat’s very useful: suppose the constant in (iii) is . Combining with (i),(ii) gives the iteration , which has the fixed point .

This is monotone in , and the sum crosses when . With we get the admissible value which add up to .

20 December, 2017 at 8:29 am

AnonymousIt is interesting to observe that now (iii) is active (replacing the role of (iv) which was used for the previous bound.)

20 December, 2017 at 11:28 am

Tobias FritzActually I seem to have messed up there…! What I actually get is . In other words, if (2) holds for , then (1) holds for . This is less useful than what I had claimed.

I’m afraid that this also invalidates the last sentence of Lior’s comment. Sorry, my bad…

20 December, 2017 at 11:41 am

Pace NielsenDoes this 4/7 trick account for the fact that the space isn’t symmetric? Rather than don’t we end up with ?

20 December, 2017 at 11:42 am

Pace NielsenWoops, should have refreshed before I posted. Good to know we both caught this!

20 December, 2017 at 12:29 pm

Tobias Fritz… and we seem to have independently made the same additional mistake! What my argument really gives is . Phew.

20 December, 2017 at 12:53 pm

Lior SilbermanIterating now we might as well assume so . Then the iteration scheme is with the fixed point — which is still a new point!

20 December, 2017 at 2:54 pm

Sean EberhardIf I understand correctly, the corrected valid map here is . By post-composing this with (Terry’s (ii), (iv), then (i)), you get . After iterating this you get to . So this still counts as state-of-the-art I think.

20 December, 2017 at 3:56 am

AnonymousA slight (although equivalent) “generalization” of proposition 1(i) is to take any convex combination of and , i.e. any non-negative pair satisfying

.

Hopefully, it may give more flexibility to possible iterations.

20 December, 2017 at 7:38 am

Lior SilbermanI don’t think this can help. The reason is that the sets of admissible are convex and all the inequalities we derived are preserved under convex combinations. This means we can always defer taking convex combinations till the end, or equivalently that the strongest inequalities are given by extreme points of the convex sets.

20 December, 2017 at 6:48 am

AulaIn the first display, the LHS of the triangle inequality has additive notation for the group operation, while everything else has multiplicative notation. In the next display, the RHS of the linear growth equation is missing the left vertical bar of the absolute value of n.

[Corrected, thanks – T.]20 December, 2017 at 8:58 am

Pace NielsenNotice that our only control over the points satisfying (2) comes from condition (ii) of the Proposition. In other words, these points are precisely the points of the form where satisfies (1).

Thus, we can avoid passing through the space altogether. Now condition (iii) of the Proposition (replacing 2/3 with 4/7 using Tobias’ idea) just says that the region satisfying (1) is preserved under the map . Similarly, condition (iv) just says that if are two points satisfying (1), then so is

Now setting , we may recursively set for each integer . By the symmetry in condition (i), we have that the points also belong to the region of interest. Connecting each successive point by a line segment, we get an infinite polygonal type region, with the points having limit and . (The slopes of each successive line segment are half of the previous segment.) It is easy to check that the condition in (iii) sends lines to lines, so this boundary is invariant under that transformation (with each boundary piece sent to the next).

I haven’t checked all the details, but numerical computations suggest this region is also invariant under the linear combination expressed in (iv). If that’s true, then without some further relations we should expect no further improvement.

20 December, 2017 at 10:32 am

Tobias FritzI’m hoping that it will be possible to do more with the bounds that involve only one term on the right-hand side, . These are great because we can replace by powers of , resulting in , or even other words. My hope is that we can combine this fact with tricks like .

20 December, 2017 at 11:56 am

Tobias FritzMy previous error means that all of Pace’s expressions that derive from the are a bit off. Fortunately, we still get the -independent bound upon using the original factor of in (iii).

Knowing that is upper bounded by a constant, can we show the same for ?

20 December, 2017 at 12:47 pm

Lior SilbermanThat is immediate from the hypotheses.

We know that all conjugates of the -ball are in the -ball, which seems preposterous in a torsion-free non-commutative group, but I don’t have any idea how to use this observation.

20 December, 2017 at 8:58 am

Terence TaoA small comment: now that the commutator bound has a constant less than 1, this implies that there exist non-trivial group elements of arbitrarily small norm; in particular, integer-valued norms have now been totally ruled out. This suggests that there is no simple “combinatorial” example of a norm (such as one based on edit distance), though it still doesn’t rule out more complicated constructions, perhaps coming from an iterative construction (e.g. starting with the zero seminorm and gradually making more and more elements have non-zero norm) or something like the functional analysis approach I suggested in the previous post.

20 December, 2017 at 9:24 am

Lior SilbermanMore precisely, either every term of the derived series has an element of non-zero norm, in which case the set of norms is dense in the positive reals, or (modulu elements of norm zero) the group is solvable, hence (as we saw) abelian.

In the abelian case there are both discrete and dense norms — on we can take either or .

20 December, 2017 at 9:23 am

AnonymousIn order to generalize the relations (1), (2), it seems that a general notation is needed for the norm of a general word

where is a finite sequence of integers.

For such cases, it is possible to use the generalized notation

20 December, 2017 at 11:05 am

António MachiaveloNormalize so that and . Then

and so . This shows that it is not the case that one has for all .

20 December, 2017 at 11:21 am

Apoorva KhareAh, so what you are saying is has norm at least the max of the norms of a,b. (Certainly, it would be something to get a similar lower bound for the commutator!)

20 December, 2017 at 12:16 pm

Terence Tao[I’ve deleted some comments here that were based on an inequality that was incorrect -T.]20 December, 2017 at 11:15 am

Will Sawin[This appears to be a response to Tobias’s comment https://terrytao.wordpress.com/2017/12/19/bi-invariant-metrics-of-linear-growth-on-the-free-group-ii/#comment-490317 -T.]I was thinking along similar lines to your (2), trying to make the argument formal. One issue I ran into is the argument (ii), which involves plugging a different variable into an already known inequality. This is a way to pass from estimates inside the commutator subgroup to estimates inside the commutator subgroup that isn’t necessarily foiled by the abelianization of the commutator subgroup. To demonstrate this, we can formulate the Hesienberg group argument in this way:

Suppose in the Heisenberg group. Then we have which gives an iteration whose fixed point is .

So it’s not obvious we need infinitely many identities in the free group case either. However, if you forbid this plugging-in trick, and only look at identities between group elements, not functions on group elements, then exactly the argument you state applies to a general subgroup and shows that no finite collection of identities can be used to show that the norm of any nontrivial element of the free group vanishes.

For your 3), I think there’s no problem to make it rigorous, and Hahn-Banach is unnecessary. For any element in , let be the infimum of all upper bounds on provable using this method under the assumptions . Then satisfies all the axioms to be a norm – if we had , we could combine arguments giving bounds close to the infimum for and with multiplication to get a better-than-infimum bound for , contradiction, and similarly with .

20 December, 2017 at 1:28 pm

Tobias FritzThis looks quite interesting, but I’m not sure I understand where the came from. Can you elaborate a bit?

20 December, 2017 at 11:51 pm

Will SawinI’m applying the bound , but plugging in and instead of and . This is supposed to be similar to one of the arguments used in this post.

20 December, 2017 at 11:35 am

cjerdonekWhat about an idea like the following? Consider the closed unit ball with three open discs removed from the boundary, and take the free group to be the fundamental group of that boundary. For the norm of a loop on the boundary, you can consider minimizing the area of the surface bounded by the loop inside the ball. It seems like a simple geometric construction would yield the triangle inequality, since you can connect two discs by an arbitrarily thin band.

20 December, 2017 at 12:22 pm

Tobias FritzIn order to have concatenation of loops as a well-defined operation, you need to consider based loops. But then your construction will fail to satisfy the desired linearity condition : as you loop two or more times around a puncture, you can contract your loop much further than in the case where you have to pass through the basepoint after every winding.

20 December, 2017 at 12:58 pm

cjerdonekElements of the fundamental group (the free group) are represented by based loops. But I was suggesting disregarding the base and considering the free loop when evaluating the norm and minimizing the spanned area. (Technically, I’m not sure it would matter because it seems you could replace a path to and from the base with an arbitrarily thin band, which wouldn’t contribute to the area.) I’m not sure I understand your point about looping two or more times though.

20 December, 2017 at 1:26 pm

Tobias FritzAh, I see! Then I agree with Terry, the doubling identity is probably what breaks down. In particular, the surface area for seems to be less than double than that of .

Actually, could it be that your proposal coincides with a ‘weighted’ version of word length, where each generator is counted with a weight given by the corresponding minimal surface area?

20 December, 2017 at 3:03 pm

cjerdonekIf there is a problem with doubling, I think it will be much more subtle than that (e.g. involving properties of area-minimizing immersed discs in the 3-ball). In your example, it doesn’t seem like taking a conjugate should help since it will be in the same free homotopy class and so have the same area.

I don’t see a connection to weighted word length since minimal spanning discs of products of elements might not correspond combinatorially to generators. But maybe there is some loose connection.

20 December, 2017 at 12:40 pm

Terence TaoThis seems to be somewhat incompatible with the recently obtained observation that there must exist nontrivial group elements of arbitrarily small norm. Presumably what is going on is that the doubling identity is breaking down.

20 December, 2017 at 12:44 pm

Terence TaoAnother trivial comment: I have found it useful (as suggested in some other comments) to view words as paths in , with representing a unit move in (say) the north, east, south, and west directions respectively. Then for instance is a loop going around a unit square, while for instance (which is a conjugate of ) traverses a square seven quarter times, which explains why can be split into four conjugates of words looking like . Drawing these sorts of loop pictures helped me understand a number of the word identities used in the above comments (as well as to catch some incorrect ones).

20 December, 2017 at 11:47 pm

Terence TaoThe evidence seems to be slowly turning in the favour of the hypothesis that no norm exists on the free group, but it is still worth pursuing the opposing hypothesis that such a norm can be constructed. Here is one possible route to doing so. Work in a small non-abelian special unitary group, such as , and let be generic elements of this group. This gives a unitary representation of the free group in the usual fashion. The idea is to define the norm as

but the issue is to select the “correct” branch of the logarithm for . If are close to the identity, then for words of small length, is also close to the identity, and one can use the standard branch, in which the doubling condition is obvious and the triangle inequality comes from the Weyl inequalities for eigenvalues of unitary groups (arranged in the “Weyl alcove” where the arguments of the eigenvalues sum to zero and have diameter less than ). But I’m not quite sure how to proceed once one moves further away from the identity. One possibility is to try to extend the matrix logarithm by monodromy: one can consider a continuous (in fact real analytic) one-parameter family of representations by defining for some fixed choice of logarithm . One can define unambiguously for small , and I think one can extend this by analytic continuation to large (one may possibly need to use the genericity hypotheses on for this). Then one sets to obtain the required branch for .

Here is a model problem that captures the difficulty. Given two “generic” skew-Hermitian matrices , can one define a binary operation , also a skew-Hermitian matrix, with the property that depends continuously on the real number with and

for all ? (For small , one can uniquely define by the Baker-Campbell-Hausdorff formula, so the question is basically whether one can analytically continue this formula generically.) Furthermore, is it the case that this operation is (generically) associative and obeys the Weyl inequality ? If one had these properties then we could define by iterating the formula and I think we would get a norm with all the required properties this way.

The key stumbling block I am having is that it appears the exponential map ceases to be a local diffeomorphism when two eigenvalues differ by a multiple of (and this is where, not coincidentally, the Baker-Campbell-Hausdorff-Dynkin formula also breaks down), but I am hoping that one can work around this problem if the matrices involved are sufficiently generic.

Perhaps one could try to test this sort of construction numerically?

21 December, 2017 at 2:08 am

Terence TaoHmm, it actually appears that (in contrast to the complex logarithm) the matrix logarithm is genuinely discontinuous at places where two eigenvalues of the logarithm differ by a multiple of , so this monodromy idea probably doesn’t work.

21 December, 2017 at 3:40 am

Sean EberhardDoes this at least give a quick proof that there is a valid norm on any finite ball in ? (I’m still trying to convince myself of the triangle inequality.)

21 December, 2017 at 8:31 am

Terence TaoI think so, yes. Regarding the triangle inequality: consider a one-parameter family of unitary matrices of the form for some Hermitian matrix , and suppose that on some open interval of times , the eigenvalues of are distinct, with each varying smoothly in . Then one can verify the Hadamard variation formula

where is the unit eigenvector associated to the eigenvalue . In particular, the derivative of does not exceed in magnitude, and this gives the triangle inequality in this open interval for any continuous branch of the logarithm.

21 December, 2017 at 5:25 am

AnonymousFor the representation of the matrix logarithm by Cauchy formula, the integration contour should encircle all the matrix eigenvalues but not the logarithmic branch point at , so if is contained in some compact real interval , such that the spectrum of can be enclosed by such integration contour for all , then the matrix logarithm is real analytic over . Is this condition (on the existence of such integration contour) also necessary for a real analytic matrix logarithm over ?

21 December, 2017 at 8:34 am

David SpeyerI haven’t understood the full context of your suggestion, but I believe I can show that, for any , , …, in , there is a unique real analytic such that and . More generally, I claim:

Theorem: If is any real analytic map with , then there is a unique real analytic with and .

We recall the definition of the blow up of at the origin: It is a submanifold of consisting of pairs such that the vector lies on the line . Projection onto is a diffeomorphism away from the origin; projection onto is a line bundle.

We’ll denote this blow up as . The key property of analytic functions is that any real analytic map which is not identically zero, lifts uniquely to an analytic map . (Not true for smooth maps: is smooth, but the line it spans doesn’t have a well defined limit in .)

We put the standard norm on , normalized so that . I’ll write the nontrivial central element of as and the identity as .

Lemma: Let be a nonnegative integer and let be an interval such that the real analytic map does not assume the value on . Then we can find such that and for all . If , there is a unique such lift; otherwise, there are precisely two.

Proof: If , we use the fact that is a diffeomorphism from the open ball of radius to .

If , then we use stereographic projection to identify with , and then lift up to . We now use the fact (must be standard, though I don’t know a reference) that is the double cover. So this follows from the lifting lemma for covers. $\square$

Now, we prove the theorem. If is identically , the claim is obvious, so I ignore this case. Otherwise, since is analytic, and are discrete. The lemma lets us lift on each connected component of , and on each connected component of , and the finite number of lifts let us glue on the overlaps.

21 December, 2017 at 8:38 am

David SpeyerA bit more conceptually: Let be the blow up of at and let be the blow up of at . Then extends to a covering map . (The corresponding fundamental groups are and .)

21 December, 2017 at 9:34 am

David SpeyerI think I now understand the context of your idea, and I think this is not going to be useful. This notion of length is very unstable with respect to group multiplication, so I don’t see how you can expect the triangle inequality to hold. For example, if is a path through then, for generic , the path is never $-1$, which means that we can just lift the path to $|X| < \pi$.

21 December, 2017 at 4:29 am

Tobias HartnickIt seems that people are focussing on trying to show that a bi-invariant metric of linear growth on . It might be worthwhile to note that there do exist bi-invariant linear metrics of “almost linear growth”. More precisely, for every we can find a bi-invariant metric on such that the associated norm satisfies

Examples can be constructed as follows: Let be a homogeneous quasimorphism of defect and let if and . For one has

If or is the identity, then the same inequality holds of trivial reasons, and since we have if and only if , hence is a norm. The associated metric is bi-invariant, since homogeneous quasimorphisms are conjugation-invariant.

Moreover we have for all ,

hence

By rescaling we can make as small as we like.

21 December, 2017 at 4:57 am

Tobias FritzThat’s interesting to know. But we could also simply take every nontrivial group element to have norm , which achieves in a rather silly way. So I guess the point of your construction is that there moreover are elements of arbitrarily large norm.

21 December, 2017 at 6:23 am

Tobias HartnickYes, I wanted to say that there exist unbouned almost linear norms. Thanks for the correction.

21 December, 2017 at 5:46 am

Apoorva KhareThis would answer a query of Manjunath Krishnapur to me yesterday.

If I recall correctly, his other question was whether one can find a norm on the free group that is “approximately linear”, in that for all elements , one has as .

21 December, 2017 at 6:16 am

Sean EberhardThis condition implies linearity, right? Because for every the sequence would have to converge to both and to .

21 December, 2017 at 6:52 am

Apoorva KhareAha, that’s very nice!

24 December, 2017 at 5:02 am

Tobias FritzOur Proposition 2.1 of the current draft also implies that every homogeneous quasi-morphism is bounded on commutators. This is apparently a known result due to Bavard (although his constant is better). I’m in the process of clarifying the details here and adding them to the manuscript.

24 December, 2017 at 7:03 am

Tobias Fritz… but then again, quasi-morphisms are trivially bounded on commutators, since their codomain is always the abelian group .

I’ve written a few sentences about quasi-morphisms on how they relate to our results. I’ve just uploaded the new version.

24 December, 2017 at 8:12 am

Sean EberhardIt does feel like there is some underlying connection yet to be fleshed out between these results and more well known stuff about quasimorphisms and Bavard duality and so on.

Here’s a stab: Is there a Hahn–Banach theorem for quasinorms? Suppose is a quasinorm of defect . Is it true that , where the sup runs over all quasimorphisms of defect (optimistically) dominated by ?

This would imply our main result via Bavard’s result (which incidentally is not very deep). Hahn–Banach would give us a quasimorphism such that , and then Bavard would give us .

24 December, 2017 at 8:40 am

Tobias FritzI agree, I also had the impression that there could be more to say! Your stab is going in an interesting direction, but as it stands it can hardly be correct, since you haven’t imposed any actual bounds on ; in particular, your also runs over all homomorphisms , and rescaling such a yields another homomorphism. So how about e.g. optimizing only over those that satisfy for all ?

In case that you know more about this: is the bound what Bavard actually proved? Applying the triangle inequality gives the trivial bound of , which is the case of his Lemme 1.1 in “Longueur stable des commutateurs”. But I haven’t read the whole paper, and he’s quoted as having shown in that paper also elsewhere.

24 December, 2017 at 8:59 am

Sean EberhardExactly, that’s what I meant when I said “dominated by “.

I think I’ve seen the bound asserted only for homogeneous . Such are also conjugation-invariant, as we know. Then the bound just comes from . This holds because . For plain old quasimorphisms, maybe is all you can do: I don’t know.

24 December, 2017 at 9:01 am

Sean EberhardI should say I think the more interesting part of Bavard’s result is that is actually the sup of over all .

24 December, 2017 at 4:33 pm

Tobias FritzAh, sorry. I need to take more time to think for myself before commenting.

So by defect of a quasinorm, you mean the maximal violation of the triangle inequality , right? If so, then don’t we already get counterexample from actual norms (i.e. length functions) on abelian groups, e.g. on ?

I’m aware of one Hahn-Banach theorem for norms on

abeliangroups: suppose that is an additively written abelian group and is any function that satisfies the triangle inequality and . Then for all ,where ranges over all homomorphisms with . (Symmetry of the norm is not required, which manifests itself in the absence of the absolute value in the -expressions.)

One can generalize this a bit further to suitable distance functions on commutative monoids satisfying . But I’m not aware of any interesting statements in the nonabelian case and haven’t yet thought about how to ‘quasify’ this either.

25 December, 2017 at 1:41 pm

Sean EberhardYour examples show why we need to assume homogeneity. So suppose satisfies and . Then does it hold that , where ranges over defect- quasimorphisms such that for all ?

For what it’s worth, we do know this for , just because it reduces to the abelian case.

25 December, 2017 at 1:59 pm

Sean EberhardAnother known case: is a quasinorm in this sense of defect . Another result of Bavard is that over all quasimorphisms . (See Theorem 3.11 at https://arxiv.org/pdf/math/0605354.pdf.)

25 December, 2017 at 2:00 pm

Sean EberhardSorry, .

25 December, 2017 at 2:02 pm

Sean EberhardStill sorry, . Sorry for spamming.

26 December, 2017 at 2:12 am

Tobias FritzThank you for the clarification. Suddenly Bavard duality makes a lot more sense to me!

As you may know, Theorem 1.12 in this paper is of a vaguely similar flavour as to what you’re suggesting. But the pseudo-norms there are not required to be homogeneous, and correspondingly the author uses a weaker notion of quasimorphism. And the result is not as quantitative as one would perhaps hope.

I’m not sure if this has anything to do at all, but perhaps one could also try to modify bounded cohomology by enhancing/substituting the boundedness requirement on cochains by something like ? (I assume that the case of trivial real coefficients would be of primary interest, so I’ve formulated it in these terms.)

21 December, 2017 at 9:38 am

David SpeyerApologies if this is already answered somewhere I missed. Let and be the standard generators of , let be the set of all conjugates of and , and let be the length function with respect to this generating set. It seems to me that a lot of the effort here is dedicated to proving bounds of the form

with the eventual aim of finding a bound such that .

Do we know any lower bounds for ? Do we know that it goes to ? Can we even show ?

21 December, 2017 at 4:36 pm

Sean EberhardInteresting question! But I do think it’s a different question. There is a linear lower bound. Suppose that is a product of generator-conjugates. Then by collecting generators appropriately we can write as , where is a product of commutators (using ). It follows that is at least . On the other hand I can prove that . I would guess is the truth.

21 December, 2017 at 8:23 pm

Terence TaoI’ll also mention that seems closely related to the notion of edit distance (or Levenshtein distance). The question of understanding doesn’t quite capture the full subtleties of these linear growth norms because this quantity somehow only uses the identity “once”, whereas we now know from the proof of abelianisation that one has to use this identity many, many times.

22 December, 2017 at 1:56 am

Sean EberhardI was just thinking about a rigorous version of this statement. Suppose is the “stabilization operator” which replaces a function by , and is the “Kobayashi operator” which replaces by the infimum of over all such that . Let be the word length function on the standard generators. Then we have shown that is zero on , while David’s question is about . One could ask whether there is a finite such that .

21 December, 2017 at 9:41 am

Terence TaoI’m recording here my understanding of the “inward repetition” method developed in the previous post by Siddharta, Pace, and Tobias. It can be abstracted as

Lemma.Suppose are such that is conjugate to and is conjugate to . Then.

Proof.By hypothesis, we have and for some , and hence for anywhere the patterns and are repeated times each. Repeatedly using the triangle inequality and the fact that conjugation by does not affect the norm, we conclude that

dividing by and taking the limit gives the claim.

Example 1: (Tobias) is conjugate both to and to , henceExample 2: (Pace) is conjugate both to and to , henceExample 3: (Pace) is conjugate both to and to , hence.

Example 4: (Tobias) is conjugate both to and to , hence(Example 1 is the case of Example 4.)

21 December, 2017 at 10:13 am

Sean EberhardHere is an interesting consequence of Example 1 (maybe somebody said this already and I missed it). We now know we can replace both the in (iii) with , so is a valid map. If we iterate this we reach , which means that .

21 December, 2017 at 10:29 am

Lior SilbermanWith in (iii) we also get the bound .

21 December, 2017 at 10:57 am

Tobias FritzThat’s a nice way to put it! This lemma can be applied nontrivially already with . For example for , this can be used to show that

(I’m omitting the norm symbols here, either by abuse of notation or by interpreting these inequalities in terms of the partial order on the free abelian group generated by the defining inequalities of a norm.)

So in particular for , we get

which may or may not be new. But I’m hoping to be able to do more by deriving more inequalities of the above type for .

By the way, perhaps it would be useful to have a list of inequalities and current best bounds somewhere that everyone could edit?

21 December, 2017 at 11:01 am

Apoorva KhareAh, my thoughts exactly. I had even started a TeX file but it is very primitive. Since Terry has most of the Tex already written up, perhaps he could send it to someone (or compile the rest himself)? I am glad to do this on Friday my time if nobody has done so until then; it is currently 12:30am here and I was about to sleep.

21 December, 2017 at 11:38 am

Tobias FritzActually that system of inequalities looks promising to me. Writing , it says , which can be iterated as we’ve done before. So in each iteration, the value at each grid point gets replaced by the average of the values of its left neighbour and of its

lowerright neighbour. This must be the discrete version of some PDE, some sort of ‘heat equation with drift’, which I don’t know. For large times and for initial conditions that make linear in and , I would expect to be close to the initial , which seems to be what we want: .But this is quite speculative at the moment and there’s a number of things that are wrong with it. First of all, I’ve been ignoring boundary effects completely.

21 December, 2017 at 12:33 pm

Sean EberhardThis looks plausible. The recurrence is related to the standard binomial recurrence, so is surely tractable, and numerically it gives what you guess. But is that useful? As in, suppose you knew . Now what? This doesn’t seem to me to imply anything about .

21 December, 2017 at 12:36 pm

Sean EberhardAh, I guess you’re planning on combining it with something like Example 4 from Terry’s post. OK, looks legit.

21 December, 2017 at 12:40 pm

David SpeyerPlugging in to shows . Even if we only directly prove the claimed result for , we have so and then linearity shows as desired. (But I’m coming in in the middle, so maybe I missed something.)

21 December, 2017 at 12:52 pm

Sean EberhardThere won’t be any useful bound for because that’s explicitly ruled out. I agree that any bounded would kill it, but that’s likely out too (judging from numerics). But maybe or something would be fine.

Actually yeah this is probably going to kill it. I’ve just checked that from this that , which implies .

21 December, 2017 at 2:27 pm

Terence TaoI think this does indeed work to give arbitrarily small bounds on , killing off the problem! One can work with some between and , say . A simple random walk that starts at and repeatedly moves by a step or with a 1/2 probability of each will end up hitting for some with exponentially high probability by the Chernoff bound, which implies the bound , which by the triangle inequality gives , and sending we win. I’ll write the details on the Wiki. EDIT: now available at http://michaelnielsen.org/polymath1/index.php?title=Linear_norm#Solution

21 December, 2017 at 12:54 pm

Sean EberhardIt implies that rather.

21 December, 2017 at 2:55 pm

Lior SilbermanThe proof of the theorem in the wiki is not quite right — the inequality doesn’t quite work for . Better to do it as you suggested above — start at the RW and walk steps. We are exponentially likely to have hit the lower boundary, and (stretched) exponentially very likely to have not walked horizontally more than . In the exponentially unlikely case we still have a linear bound on . This gives the bound

so, by the triangle inequality,

and we can now divide by and let .

21 December, 2017 at 3:00 pm

Terence TaoActually, it does seem to be that the proof of Corollary 7 continues to work for zero or negative, so the proof on the wiki I think works as stated (though the other way would also work).

21 December, 2017 at 3:10 pm

Sean EberhardVery nice!

21 December, 2017 at 3:13 pm

Lior SilbermanRight — the identities in Corollary 7 hold for all so your argument is simpler.

Very nice!

21 December, 2017 at 3:19 pm

Tobias FritzWow! This blows my mind. And should make for some peaceful sleep ;)

21 December, 2017 at 3:24 pm

Apoorva KhareThis is great — the problem is solved for all non-abelian groups! (For abelian groups — and other structures — I’d mentioned http://arxiv.org/abs/1610.03037.) In parallel to this, I’ll add the related question of considering (semi)norms on a more primitive algebraic/geometric structure: semigroups and monoids.

Does there exist a (bi/left/right-invariant) norm on a monoid, i.e. a distance that has linear growth?

The solution of course has to be different, since conjugations are no longer permitted. And this time there *is* a purported candidate, contrary to the case of groups — told to me by Robert Young to explore:

Consider the free monoid on a set, with the following distance between words: the number of single-character insertions or deletions it takes to go from one string to the other, so (delete , insert ). Equivalently, the edit distance between v and w is

length(v)+length(w)-2*length(longest common subsequence).

Is this a (bi/left/right-invariant) norm?

21 December, 2017 at 12:36 pm

David SpeyerCombined with the obvious bound (we could replace by another constant but it doesn’t effect the end result), it is easy to show by induction on that for . Your formula doesn’t give a bound for . Using the obvious formula , we can recursively compute a triangular array of bounds for for . Here are the first 10 bounds for

{2, 3, 15/4, 35/8, 315/64, 693/128, 3003/512, 6435/1024,

109395/16384, 230945/32768, 969969/131072, 2028117/262144,

16900975/2097152, 35102025/4194304, 145422675/16777216,

300540195/33554432, 9917826435/1073741824, 20419054425/2147483648,

83945001525/8589934592, 172308161025/17179869184} =

{2., 3., 3.75, 4.375, 4.92188, 5.41406, 5.86523, 6.28418, 6.67694,

7.04788, 7.40028, 7.73665, 8.05901, 8.36897, 8.66787, 8.9568, 9.2367,

9.50836, 9.77248, 10.0297}

It’s hard to tell whether or not this growth is sublinear. One should be able to get asymptotics using generating functions. I’ll try this tonight if someone doesn’t beat me to it.

21 December, 2017 at 12:48 pm

Tobias FritzAs Sean has noted, that system is simple enough to solve explicitly, at least as long as we are away from the boundary. So after iterations we have, at ,

where I’ve taken for simplicity, and the second equation uses initial conditions based on our current best bound , meaning .

Assuming that my computations are correct, this shows that , recovering our earlier bounds and .

Iterating the system for iterations will give further improvements, but requires working out the boundary conditions; David has suggested how to do this at the boundary; the boundary is easier, since there we can just take for all .

21 December, 2017 at 1:25 pm

David SpeyerYou may as well take your boundary condition to be , since that is the limit as . All the interest is in the range .

21 December, 2017 at 1:58 pm

Lior Silberman1. Note that the fixed points of the iteration are linear in the boundary conditions. Since our boundary conditions are linear functions in you can take the boundary conditions to depend each variable separately and sum the results.

Those recursions are easy to solve directly, and I think you get linear growth.

2. I think it’s better to define by . For example this gives the boundary conditions but .

21 December, 2017 at 2:01 pm

Lior SilbermanI also forgot to add that the best bounds used the symmetry of the commutator: that . In other words, it’s useful to add a switch of -values along the -axis to the iteration scheme.

Should also build in .

21 December, 2017 at 12:08 pm

Lior SilbermanTerry: can you or Michael Nielsen start a page on the polymath wiki as suggested by Tobias? This can be “mini-polymath 5”.

21 December, 2017 at 12:58 pm

Terence TaoTobias, I was not able to establish this inequality. I’ve put it on the wiki page http://michaelnielsen.org/polymath1/index.php?title=Linear_norm as Corollary 7, feel free to insert a proof.

21 December, 2017 at 1:31 pm

Tobias FritzDone; now the details are there for everyone to check. I hope that I haven’t made some silly mistake.

21 December, 2017 at 12:11 pm

Terence TaoOne cute application of the lemma: for any , since is conjugate to both and . Thus the function is convex in .

21 December, 2017 at 12:17 pm

Terence TaoI am starting work on a wiki page to collect and organise the various estimates at http://michaelnielsen.org/polymath1/index.php?title=Linear_norm . Right now it is only a stub but I will work on expanding it.