### A PolyMath adventure

##### Siddhartha Gadgil

Indian Institute of Science

##### joint with

the rest of (spontaneous) polymath 14

### The PolyMath 14 participants

• Tobias Fritz, MPI MIS
• Siddhartha Gadgil, IISc, Bangalore
• Apoorva Khare, IISc, Bangalore
• Pace Nielsen, BYU
• Lior Silberman, UBC
• Terence Tao, UCLA
• On Saturday, December 16, 2017, Terrence Tao posted on his blog a question, which Apoorva Khare had asked him.
• Is there a homogeneous, (conjugacy invariant) length function on the free group on two generators?
• Six days later, this was answered in a collaboration involving several mathematicians (and a computer).
• This the story of the answer and its discovery.

### Length functions

• Fix a group $G$, i.e. a set with an associative product with inverses.
• A pseudo-length function $l: G \to [0, \infty)$ is a function such that:
• $l(e) = 0$.
• $l(g^{-1}) = l(g)$ , for all $g \in G$.
• (Triangle inequality) $l(gh) \leq l(g) + l(h)$, for all $g,h\in G$.
• A length function is a pseudo-length function such that $l(g) > 0$ whenever $g\neq e$ (positivity condition).
• A pseudo-length function $l$ is said to be conjugacy invariant if $l(ghg^{-1})=l(h)$ for all $g, h \in G$.
• $l$ is said to be homogeneous if $l(g^n) = nl(g)$ for all $g \in G$.
• On the group $\mathbb{Z}^2$ of pairs of integers, a (conjugacy invariant) homogeneous length function is given by $l_{\mathbb{Z}^2}((a,b)) = |a| + |b|$.
• On the other hand, if $l$ is homogeneous and $g^n=e$ then $l(g)=0$ as $nl(g) = l(g^n) = 0$.
• Thus, if $G$ has torsion, i.e., there exists $g\neq e\in G$, such that $g^n =0$ for some $n > 0$, then there is no homogeneous length function on $G$.

### Free group $\mathbb{F}_2$ on $\alpha$, $\beta$

• Consider words in four letters $\alpha$, $\beta$, $\bar{\alpha}$ and $\bar{\beta}$.
• We multiply words by concatenation, e.g. $\alpha\beta\cdot\bar{\alpha}\beta = \alpha\beta\bar{\alpha}\beta$.
• Two words are regarded as equal if they can be related by cancelling adjacent letters that are inverses, e.g. $\alpha\beta\bar{\beta}\alpha\beta = \alpha\alpha\beta$.
• This gives a group; e.g. $(\alpha\bar{\beta}\alpha\beta\beta)^{-1} = \bar{\beta}\bar{\beta}\bar{\alpha}\beta\bar{\alpha}$.
• The word length on $\mathbb{F_2}$ is the length of the shortest word representing an element.

### Pullback pseudo-lengths

• We define $ab: \mathbb{F}_2 \to \mathbb{Z}^2$ by total exponents (ignoring order), e.g. $ab(\alpha\alpha\beta\bar{\alpha}\bar{\beta}\alpha\bar{\beta}) = (2, -1)$.
• We get a pullback pseudo-length $l$ on $\mathbb{F}_2$ by $l_{ab}(g) = l_{\mathbb{Z}^2}(ab(g))$.
• As $l_{\mathbb{Z}^2}$ is homogeneous, so is $l_{ab}$.
• However, this is not a length function as $l_{ab}([\alpha, \beta])=0$, where $[g, h] = ghg^{-1}h^{-1}$ (violating positivity).
• More generally, every group $G$ has an Abelianization $ab: G \to G/[G, G]$.

### The Main results

• Question: Is there a homogeneous length function on the free group on two generators?
• Answer: No; we in fact describe all homogeneous pseudo-lengths.
• Theorem: Any homogeneous pseudo-length function on a group $G$ is the pullback of a pseudo-length on its Abelianization $G / [G, G]$.
• Corollary: If $G$ is not abelian (e.g. $G = \mathbb{F}_2$) there is no homogeneous length function on $G$.
• In fact, every homogeneous pseudo-length is the pullback of a norm on a vector space.

### First reductions

• (Fritz): Homomogeneous implies Conjugacy invariant.
• (Tao, Khare): $l(g^2) = 2l(g) \forall g\in G$ implies Homogeneity.

#### Finding bounds: contradict positivity?

• Fix $l$ homomogeneous pseudo-length function.
• The triangle inequality gives bounds on $l(gh)$ in terms of $l(g)$ and $l(h)$.
• Homogeneity gives a bound on $l(g)$ in terms of a bound on $l(g^n)$; also use conjugacy invariance.
• Find bounds for elements in terms of bounds for others, especially
• $l([x, y])$ in terms of $l(x)$ and $l(y)$
• $l(g)$ for fixed $g$ in terms of bounds on generators.
• Combine bounds, including by interpreting in terms of convexity.

#### Seeking a homogeneous length function

• We can attempt to construct pseudo-lengths that are positive, or at least such that $l([\alpha, \beta])> 0$.
• Can consider quotients larger than $\mathbb{Z}^2$: negative results by Sawin, Silberman, Tao.
• Given a candidate $l: G \to [0, \infty)$, try to fix this to ensure homogeneity and the triangle inequality.
• There were also attempted constructions based on functional analysis.

### Repairing lengths

• We start with a candidate function $l: G \to \mathbb{R}$, say the word length.
• Homogenize: $\bar{l}(g) = lim_{n\to \infty} \frac{l(g^n)}{n}$.
• The limit exists by sub-addivity of $l(g^n)$ (for fixed $g$) by Fekete's lemma.
• Kobayashi construction: Fix triangle inequality by $\bar{l}(g) = \inf\{\sum_{i=1}^nl(g_i) : g=\prod_{i=1}^n g_i \}$.
• I hoped to combine these with an approach based on non-crossing matchings.

### Non-crossing matchings

• Given a word in $\mathbb{F}_2$, we consider matchings such that
• letters are paired with their inverses,
• there are no crossings
• The norm is the number of unmatched letters.
• For $g\in \mathbb{F}_2$, define the Watson-Crick length $l^{}_{WC}(g)$ to be the minimum number of unmatched letters over all non-crossing matchings.
• $l^{}_{WC}$ is unchanged under cancellation (hence well-defined on $\mathbb{F}_2$) and conjugacy invariant.
• However, if $g=\alpha[\alpha, \beta]$, then $l^{}_{WC}(g^2)= 4$, but $l^{}_{WC}(g) = 3$, violating homogeneity.
• Non-crossing matchings correspond to decompositions into conjugates, e.g., $(\alpha[\alpha, \beta])^2 = ((\beta)^\alpha (\alpha^2)^{\bar{\beta}})^\alpha\bar{\beta}$, where ($g^h$ denotes $hgh^{-1}$; giving proofs of bounds and showing $l^{}_{WC}$ is the maximal conjugacy-invariant length.

### The great bound chase

• By Tuesday morning, most people were convinced that there are no homogeneous length functions on the free group.
• There was a steady improvements in the combinatorial/analytic bounds on $l([\alpha, \beta])$.
• These seemed to be stuck above 1 (as observed by Khare) - but eventually broke this barrier (work of Fritz, Khare, Nielsen, Silberman, Tao).
• At this stage, my approach diverged.

#### Computer Assisted proofs: beyond (symbolic) computation, enumeration?

• We can recursively compute the matching length $l^{}_{WC}(g)$ for a word $g$.
• This gives an upper bound on all conjugacy-invariant normalized lengths.
• This can be combined with using homogenity.
• Using this, I obtained an upper bound of about $0.85$ on $l(\alpha, \beta)$.
• This was upgraded to a (computer) checkable proof.
• On Thursday morning, I posted an in principle human readable proof of a bound.
• The computer-generated proof was studied by Pace Nielsen, who extracted the internal repetition trick.
• This was extended by Nielsen and Fritz and generalized by Tao; from this Fritz obtained the key lemma:
• Let $f(m, k) = l(x^m[x, y]^k)$. Then $f(m, k) \leq\frac{f(m-1, k) + f(m+1, k-1)}{2}$.
• A probabilistic argument of Tao finished the proof.

#### Computer bounds and proofs

• For $g=ah$, $a \in \{\alpha, \beta, \bar{\alpha}, \bar{\beta}\}$, the length $l^{}_{WC}(g)$ is the minimum of:
• $1 + l^{}_{WC}(h)$ : corresponding to $a$ unmatched.
• $\min\{l^{}_{WC}(x) + l^{}_{WC}(y): h = x\bar{a}y \}$.
• We can describe a minimal non-crossing matching by a similar recursive definition.
• A similar recursion gives a proof of a bound on $l(g)$ for $g$ a homogeneous, conjugacy-invariant length with $l(\alpha)=l(\beta)=1$.
• We can also use homogeneity for selected elements and powers to bound the length function $l$.

Proofs of $l(word)\leq bound$:


sealed abstract class LinNormBound(
val word: Word,
val bound: Double)

final case class Gen(n: Int) extends
LinNormBound(Word(Vector(n)), 1)

final case class ConjGen(n: Int,pf: LinNormBound) extends
LinNormBound(n +: pf.word :+ (-n), pf.bound)

final case class Triang(
pf1: LinNormBound, pf2: LinNormBound) extends
LinNormBound( pf1.word ++ pf2.word, pf1.bound + pf2.bound)

final case class PowerBound(
baseword: Word, n: Int, pf: LinNormBound) extends
LinNormBound(baseword, pf.bound/n){
require(pf.word == baseword.pow(n))
}

final case object Empty extends
LinNormBound(Word(Vector()), 0)



### On the computer proof

• Our proofs, and their correctness are self-contained, and separate from the act of finding the proof.
• Hence the correctness of the proof depended only on the correctness of the code defining proofs, which was tiny.
• Further, while the proof was large, the search space for the proof was enormous.
• Hence the proof had information content beyond establishing the truth of a statement.
• In particular, one can learn from such a proof.

### Limitations of the computer proof

• The elements for which we applied homogeneity were selected by hand.
• More importantly, in our representations of proofs, the bounds were only for concrete group elements.
• In particular, we cannot
• represent inequalities for expressions.
• use induction.
• Would want proof in complete foundations - which I completed a few days after the PolyMath proof.
• Lemma: If $x = s(wy)s^{-1} = t(zw^{-1})t^{-1}$, we have $l(x)\leq \frac{l(y)+ l(z)}{2}$.
• Proof: $l(x^nx^n) = l(s(wy)^ns^{-1}t(zw^{-1})^nt^{-1})$ $\leq n(l(y) +l(z)) + 2(l(s) + l(t))$
• Use $l(x) = \frac{l(x^nx^n)}{2n}$ and take limits.
• Lemma: $f(m, k) \leq\frac{f(m-1, k) + f(m+1, k-1)}{2}$, where $f(m, k) = l(x^m[x, y]^k)$.
• In other words, for $Y$ a Rademacher random variable, i.e., $Y$ is $1$ or $-1$ each with probability $1/2$, $f(m, k)\leq E(f( (m, k - 1/2) + Y(1, -1/2) ))$.
• Hence for $Y_i$ i.i.d. Rademacher random variables, $f(0, n) \leq E(f((Y_1 + Y_2 + \dots + Y_{2n}) (1, -1/2) ))$,
• By triangle inequality, $f(a, b) \leq A\Vert (a, b) \Vert$.
• $Y_1 + Y_2 + \dots Y_{2n}$ has mean $(0, 0)$ and variance $2n$, so $E(\Vert Y_1 + Y_2 + \dots Y_{2n} \Vert) \leq B\sqrt{n}$.
• We deduce that $l([x, y]^n) = f(0, n) \leq C\sqrt{n}$, hence $l([x, y]) = 0$.

### Epilogue: Quasification

• The function $l: G \to [0, \infty)$ is a quasi-pseudo-length function if there exists $c \in \mathbb{R}$ such that $l(gh) \leq l(g) + l(h) + c$, for all $g,h\in G$.
• We see that for a homogeneous quasi-pseudo-length function, $l([x, y]) \leq 4c$ for all $x, y\in G$.
• Free groups have homogeneous quasi-pseudo-length functions that are not pullbacks of norms.
• But, for a group with vanishing stable commutator length, e.g. if $G$ is solvable or $G=Sl(n , \mathbb{Z})$, $n\geq 3$, any homogeneous quasi-pseudo-length function is equivalent to the pullback of a norm.