Free groups, Lengths and Computer Proofs
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).
Conjugacy-invariance and Homogeneity
- A pseudo-length function $l$ is said to be conjugacy invariant if
$l(ghg^{-1})=l(h)$ for all $g,
h \in G$.
- Conjugacy often corresponds to change of coordinates.
- $l$ is said to be homogeneous if $l(g^n) = nl(g)$ for all $g \in G$.
- Homogeneity was motivated by norms on vector spaces.
Length functions on $\mathbb{Z}^2$
- The group $(\mathbb{Z}^2, +) = \{(n, m) : n, m \in \mathbb{Z}\}$ with
$(n_1, m_1) + (n_2, m_2) = (n_1 + n_2, m_1 + m_2)$.
-
Two length functions on $\mathbb{Z}^2$ are:
- $l_1((a,b)) = |a| + |b|$,
- $l_2((a, b)) = \sqrt{a^2 + b^2}$
- These are homogeneous (and conjugacy invariant).
- The function $l'((a, b)) = \sqrt{|a|} + \sqrt{|b|}$ is a length function, but
not homogeneous.
- The function $l''((a, b)) = |a - b|$ is a homogeneous pseudo-length function
which is not positive.
Groups without homogeneous length functions
- If $l$ is a homogeneous length function on $G$ and $g\in G$ is such that
$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 =e$ for some $n > 0$ and $g\neq e$, then there is no homogeneous length function on $G$.
- In particular finite groups have no homogeneous length functions.
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;
- the identity is the empty word
- every word has an inverse, e.g.,
$(\alpha\bar{\beta}\alpha\beta\beta)^{-1} =
\bar{\beta}\bar{\beta}\bar{\alpha}\beta\bar{\alpha}$.
Word length on $\mathbb{F}_2$
- Any word is equivalent to a unique reduced word, i.e., where we have no cancellation e.g. $\alpha\beta\bar{\beta}\alpha\beta\bar{\beta}\beta\bar{\alpha}$ reduces to $\alpha\alpha\beta\bar{\alpha}$.
- The word length $l_0$ on $\mathbb{F_2}$ is the length of the reduced
word
representing an element.
- The word length is not conjugacy-invariant as $l_0(\alpha\beta\bar{\alpha}) = 3
\neq 1 = l_0(\beta)$.
- The word length is also not homogeneous, e.g.,
$l_0((\alpha\beta\bar{\alpha})^2) = l_0(\alpha\beta\beta\bar{\alpha}) = 4 \neq
2l_0(\alpha\beta\bar{\alpha})$.
Pullback pseudo-length on $\mathbb{F}_2$
- We define a homomorphism $ab: \mathbb{F}_2 \to \mathbb{Z}^2$.
- For a word $g$, let $n_\alpha(g)$ and $n_\beta(g)$ be the number of $\alpha$'s and
$\beta$'s counted with sign.
- Define $ab(g) = (n_\alpha(g), n_\beta(g))$, 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_1(ab(g)) = |n_\alpha(g)| + |n_\beta(g)| $.
- As $l_1$ is homogeneous, so is $l_{ab}$.
- However, this is not a length function as $l_{ab}([\alpha,
\beta]) = l(\alpha\beta\bar{\alpha}\bar{\beta}) =0$, violating positivity (recall $[g, h] = ghg^{-1}h^{-1}$).
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.
Lengths from 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 energy is the number of unmatched letters.
Watson-Crick length on $\mathbb{F}_2$
- 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.
- In fact it is the maximal
normalized conjugacy-invariant length
function on $\mathbb{F}$. Candidate?
- However, if $g=\alpha[\alpha, \beta]$, then
$l^{}_{WC}(g^2)= 4$, but
$l^{}_{WC}(g) = 3$, violating homogeneity.
The great bound chase
- By Tuesday morning, most people were convinced that there are no homogeneous
length functions on the free group, and probably $l([\alpha, \beta]) = 0$ for homogeneous pseudo-lengths.
- 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 Watson-Crick 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. [Algebra Number Theory , 12 (2018), 1773-1786.]
- 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$.
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$.
Conclusions
- If we view applications of the axioms as moves, the computer proof helped in
identifying composite moves that could be applied recursively.
-
The principal difficulty in finding computer proofs often lies in choosing the useful complexity
increasing moves (here homogeneity).
- In this case, these were chosen mainly on mathematical considerations.
- However, a general heuristic we see is to seek useful families of
complexity-increasing moves.
Conclusions
-
The unusual feature of the use of computers here was that a computer generated but human
readable proof was read, understood, generalized
and abstracted by mathematicians to obtain the key lemma in an interesting
mathematical result.
-
The use of computers was based on the idea of proofs as mathematical objects which can be
computed, following foundations based on Homotopy Type Theory.