<commit_before><!doctype html>
<html lang="en">

	<head>
		<meta charset="utf-8">

		<title>Homomogeneous length functions on Groups</title>

		<meta name="description" content="A framework for easily creating beautiful presentations using HTML">
		<meta name="author" content="<NAME>">

		<meta name="apple-mobile-web-app-capable" content="yes" />
		<meta name="apple-mobile-web-app-status-bar-style" content="black-translucent" />

		<meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no, minimal-ui">

		<link rel="stylesheet" href="css/reveal.css">
		<link rel="stylesheet" href="css/theme/black.css" id="theme">
		<link rel="stylesheet" href="css/custom.css">

		<!-- Code syntax highlighting -->
		<link rel="stylesheet" href="lib/css/zenburn.css">

		<link rel="icon" href="IIScLogo.jpg">

		<!-- Printing and PDF exports -->
		<script>
			var link = document.createElement( 'link' );
			link.rel = 'stylesheet';
			link.type = 'text/css';
			link.href = window.location.search.match( /print-pdf/gi ) ? 'css/print/pdf.css' : 'css/print/paper.css';
			document.getElementsByTagName( 'head' )[0].appendChild( link );
		</script>

		<!--[if lt IE 9]>
		<script src="lib/js/html5shiv.js"></script>
		<![endif]-->
	</head>

	<body>

<div class="reveal">

<!-- Any section element inside of this container is displayed as a slide -->
<div class="slides">
<section>

	<h3> Homomogeneous length functions on Groups </h3>
	<h3> A PolyMath adventure</h3>
	 <h5><NAME></h5>
	 <p>Indian Institute of Science</p>
	 <h5> joint with </h5>
	 <p class="fragment highlight-blue">The rest of (spontaneous) polymath 14</p>

</section>
<section>
		<h3>The PolyMath 14 participants</h3>
		<ul>
			<li><NAME>, MPI MIS</li>
			<li> <NAME>, IISc, Bangalore </li>
			<li> <NAME>, IISc, Bangalore</li>
			<li>	<NAME>, BYU </li>
			<li> <NAME>, UBC </li>
			<li> <NAME>, UCLA </li>
		</ul>


</section>

<section>
    <ul>
      <li>On Saturday, December 16, 2017, <NAME> posted this question, asked by <NAME>:</li>
				<blockquote class="fragment">
					Is there a homogeneous, (conjugacy invariant) length function on the free group on two generators?
				</blockquote>
			<li class="fragment">Six days later, this was answered in a collaboration involving several mathematicians (and a computer).</li>
			<li class="fragment">This the story of the answer and its discovery.</li>
    </ul>
</section>

<section>
	<h2>Length functions</h2>
	<ul>
	  <li class="fragment">Fix a group $G$, i.e. a set with an associative product with inverses.</li>
		<li class="fragment">A <em>pseudo-length function</em> $l: G \to [0, \infty)$ is a function  such that:
			<ul>
				<li>$l(e) = 0$.</li>
				<li>$l(g^{-1}) = l(g)$ , for all $g \in G$.</li>
				<li>$l(gh) \leq l(g) + l(h)$, for all $g,h\in G$.</li>
			</ul>
		</li>
		<li class="fragment">A <em>length function</em> is a pseudo-length function such that $l(g) > 0$ whenever $g\neq e$.
	</ul>
</section>

<section>
		<ul>
		  <li>A pseudo-length function $l$ is said to be conjugacy invariant if $l(ghg^{-1})=l(g)$ for all $g, h \in G$.</li>
			<li class="fragment">$l$ is  said to be <em>homogeneous</em> if $l(g^n) = nl(g)$ for all $g \in G$. </li>
			<li class="fragment">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|$.</li>
			<li class="fragment">On the other hand, if $l$ is homogeneous and $g^n=e$ then $l(g)=0$ as $nl(g) = l(g^n) = 0$.</li>
			<li class="fragment">Thus, if $G$ has <em>torsion</em>, 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$. </li>
		</ul>
</section>

<section>
	<h2>Free group on $\alpha$, $\beta$</h2>
	<ul>
	  <li class="fragment">Consider words in four letters $\alpha$, $\beta$, $\bar{\alpha}$ and $\bar{\beta}$.</li>
		<li class="fragment">We can multiply words by concatenation, e.g. $\alpha\beta\cdot\bar{\alpha}\beta = \alpha\beta\bar{\alpha}\beta$.</li>
		<li class="fragment">Two words are regarded as equal if they can be related by cancellating adjacent letters that are inverses, e.g. $\alpha\beta\bar{\beta}\alpha\beta = \alpha\alpha\beta$.</li>
		<li class="fragment">This gives a group; e.g.
			$(\alpha\bar{\beta}\alpha\beta\beta)^{-1} = \bar{\beta}\bar{\beta}\bar{\alpha}\beta\bar{\alpha}$ .</li>
	</ul>
</section>

<section>
	<h3>Non-crossing matchings</h3>
	 <img src="aabab.png" scale="20%" style="border:none; background-color: white;">
	 <ul>
	 	<li>Letters are paired with their inverses.</li>
		<li> There are no <strong  class="fragment highlight-current-blue">crossings</strong>.</li>
		<li> The <strong class="fragment highlight-current-blue">norm</strong> is the number of unmatched letters.</li>
	</ul>
</section>


<section>
	<embed src="gross-proof.html" width="1000" height="600">
</section>

<section>
<p>Proofs of $l(word)\leq bound$ for homomogeneous pseudo-lengths $l$ bounded by $1$ on generators.</p>
<pre><code class="hljs scala scrollcode">
sealed abstract class LinNormBound(
	val word: Word,
	val bound: Double)

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

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

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

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

  case object Empty extends
    LinNormBound(Word(Vector()), 0)
}
</code></pre>
</section>



<section>
	<embed src="formal-proof.html" width="1000" height="600">
</section>

<section>
	<embed type="application/pdf" src="linear_v2.pdf" width="1000" height="600">
</section>



		<script src="lib/js/head.min.js"></script>
		<script src="js/reveal.js"></script>

		<script>

			// Full list of configuration options available at:
			// https://github.com/hakimel/reveal.js#configuration
			Reveal.initialize({
				controls: true,
				progress: true,
				history: true,
				center: true,

				transition: 'slide', // none/fade/slide/convex/concave/zoom


				math: {
					mathjax: '../MathJax/MathJax.js',
					// mathjax: 'http://cdn.mathjax.org/mathjax/latest/MathJax.js',<commit_msg>intro slides<commit_after><!doctype html>
<html lang="en">

	<head>
		<meta charset="utf-8">

		<title>Homomogeneous length functions on Groups</title>

		<meta name="description" content="A framework for easily creating beautiful presentations using HTML">
		<meta name="author" content="<NAME>">

		<meta name="apple-mobile-web-app-capable" content="yes" />
		<meta name="apple-mobile-web-app-status-bar-style" content="black-translucent" />

		<meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no, minimal-ui">

		<link rel="stylesheet" href="css/reveal.css">
		<link rel="stylesheet" href="css/theme/black.css" id="theme">
		<link rel="stylesheet" href="css/custom.css">

		<!-- Code syntax highlighting -->
		<link rel="stylesheet" href="lib/css/zenburn.css">

		<link rel="icon" href="IIScLogo.jpg">

		<!-- Printing and PDF exports -->
		<script>
			var link = document.createElement( 'link' );
			link.rel = 'stylesheet';
			link.type = 'text/css';
			link.href = window.location.search.match( /print-pdf/gi ) ? 'css/print/pdf.css' : 'css/print/paper.css';
			document.getElementsByTagName( 'head' )[0].appendChild( link );
		</script>

		<!--[if lt IE 9]>
		<script src="lib/js/html5shiv.js"></script>
		<![endif]-->
	</head>

	<body>

<div class="reveal">

<!-- Any section element inside of this container is displayed as a slide -->
<div class="slides">
<section>

	<h3> Homomogeneous length functions on Groups </h3>
	<h3> A PolyMath adventure</h3>
	 <h5><NAME></h5>
	 <p>Indian Institute of Science</p>
	 <h5> joint with </h5>
	 <p class="fragment highlight-blue">The rest of (spontaneous) polymath 14</p>

</section>
<section>
		<h3>The PolyMath 14 participants</h3>
		<ul>
			<li><NAME>, MPI MIS</li>
			<li> <NAME>, IISc, Bangalore </li>
			<li> <NAME>, IISc, Bangalore</li>
			<li>	<NAME>, BYU </li>
			<li> <NAME>, UBC </li>
			<li> <NAME>, UCLA </li>
		</ul>


</section>

<section>
    <ul>
      <li>On Saturday, December 16, 2017, <NAME> posted this question, asked by <NAME>:</li>
				<blockquote class="fragment">
					Is there a homogeneous, (conjugacy invariant) length function on the free group on two generators?
				</blockquote>
			<li class="fragment">Six days later, this was answered in a collaboration involving several mathematicians (and a computer).</li>
			<li class="fragment">This the story of the answer and its discovery.</li>
    </ul>
</section>

<section>
	<h2>Length functions</h2>
	<ul>
	  <li class="fragment">Fix a group $G$, i.e. a set with an associative product with inverses.</li>
		<li class="fragment">A <em>pseudo-length function</em> $l: G \to [0, \infty)$ is a function  such that:
			<ul>
				<li>$l(e) = 0$.</li>
				<li>$l(g^{-1}) = l(g)$ , for all $g \in G$.</li>
				<li>$l(gh) \leq l(g) + l(h)$, for all $g,h\in G$.</li>
			</ul>
		</li>
		<li class="fragment">A <em>length function</em> is a pseudo-length function such that $l(g) > 0$ whenever $g\neq e$.
	</ul>
</section>

<section>
		<ul>
		  <li>A pseudo-length function $l$ is said to be conjugacy invariant if $l(ghg^{-1})=l(g)$ for all $g, h \in G$.</li>
			<li class="fragment">$l$ is  said to be <em>homogeneous</em> if $l(g^n) = nl(g)$ for all $g \in G$. </li>
			<li class="fragment">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|$.</li>
			<li class="fragment">On the other hand, if $l$ is homogeneous and $g^n=e$ then $l(g)=0$ as $nl(g) = l(g^n) = 0$.</li>
			<li class="fragment">Thus, if $G$ has <em>torsion</em>, 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$. </li>
		</ul>
</section>

<section>
	<h2>Free group $\mathbb{F}_2$ on $\alpha$, $\beta$</h2>
	<ul>
	  <li class="fragment">Consider words in four letters $\alpha$, $\beta$, $\bar{\alpha}$ and $\bar{\beta}$.</li>
		<li class="fragment">We can multiply words by concatenation, e.g. $\alpha\beta\cdot\bar{\alpha}\beta = \alpha\beta\bar{\alpha}\beta$.</li>
		<li class="fragment">Two words are regarded as equal if they can be related by cancellating adjacent letters that are inverses, e.g. $\alpha\beta\bar{\beta}\alpha\beta = \alpha\alpha\beta$.</li>
		<li class="fragment">This gives a group; e.g.
			$(\alpha\bar{\beta}\alpha\beta\beta)^{-1} = \bar{\beta}\bar{\beta}\bar{\alpha}\beta\bar{\alpha}$ .</li>
	</ul>
</section>

<section>
	<h2>Pullback pseudo-lengths</h2>
	<ul>
	  <li class="fragment">We can define $ab: \mathbb{F}_2 \to \mathbb{Z}^2$ by ignoring order, e.g. $ab(\alpha\alpha\beta\bar{\alpha}\bar{\beta}\alpha\bar{\beta}) = (2, -1)$.
		</li>
		<li class="fragment">We get a pullback pseudo-length $l$ on $\mathbb{F}_2$ by $l(g) = l_{\mathbb{Z}^2}(g)$.</li>
		<li class="fragment">As $l_{\mathbb{Z}^2}$ is homogeneous, so is $l$.</li>
		<li class="fragment"> However, this is <em>not</em> a length function as $l([\alpha, \beta])=0$, where $[g, h] = ghg^{-1}h^{-1}$. </li>
		<li class="fragment">More generally, every group $G$ has an Abelianization $ab: G \to G/[G, G]$. </li>
	</ul>
</section>

<section>
	<h2>The Main results</h2>
	<ul>
		<li class="fragment highlight-current-blue">
			<strong>Theorem:</strong> Any homogeneous pseudo-length function on a group $G$ is the pullback of a pseudo-length on its Abelianization $G / [G, G]$.</h4>
		</li>
		<li class="fragment highlight-current-blue"><strong>Corollary:</strong>  If $G$ is not abelian (e.g. $G = \mathbb{F}_2$) there is no homogeneous length function on $G$.</li>
		<li class="fragment">In fact, every homogeneous pseudo-length is the pullback of a <em>norm</em> on a vector space.</li>
	</ul>
</section>

<section>
	<h3>Non-crossing matchings</h3>
	 <img src="aabab.png" scale="20%" style="border:none; background-color: white;">
	 <ul>
	 	<li>Letters are paired with their inverses.</li>
		<li> There are no <strong  class="fragment highlight-current-blue">crossings</strong>.</li>
		<li> The <strong class="fragment highlight-current-blue">norm</strong> is the number of unmatched letters.</li>
	</ul>
</section>


<section>
	<embed src="gross-proof.html" width="1000" height="600">
</section>

<section>
<p>Proofs of $l(word)\leq bound$ for homomogeneous pseudo-lengths $l$ bounded by $1$ on generators.</p>
<pre><code class="hljs scala scrollcode">
sealed abstract class LinNormBound(
	val word: Word,
	val bound: Double)

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

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

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

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

  case object Empty extends
    LinNormBound(Word(Vector()), 0)
}
</code></pre>
</section>



<section>
	<embed src="formal-proof.html" width="1000" height="600">
</section>

<section>
	<embed type="application/pdf" src="linear_v2.pdf" width="1000" height="600">
</section>



		<script src="lib/js/head.min.js"></script>
		<script src="js/reveal.js"></script>

		<script>

			// Full list of configuration options available at:
			// https://github.com/hakimel/reveal.js#configuration
			Reveal.initialize({
				controls: true,
				progress: true,
				history: true,
				center: true,

				transition: 'slide', // none/fade/slide/convex/concave/zoom


				math: {
					// mathjax: '../MathJax/MathJax.js',
					mathjax: 'https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.0/MathJax.js',
{'fraction_non_alphanumeric': 0.18938377920519517, 'fraction_numerical': 0.012564410249170608, 'mean_word_length': 3.878787878787879, 'pattern_counts': {'":': 0, '<': 394, '<?xml version=': 0, '>': 398, 'https://': 3, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7212357', 'n_tokens_mistral': 5573, 'n_tokens_neox': 5037, 'n_words': 1404}