# Language Model Sentence Completion with a Parser-Driven Rhetorical Control
Method

Joshua Zingale
San Diego State University
5500 Campanile Drive
San Diego CA 92182
<EMAIL_ADDRESS>
&Jugal Kalita
University of Colorado Colorado Springs
1420 Austin Bluffs Pkwy
Colorado Springs CO 80918
<EMAIL_ADDRESS>

###### Abstract

Controlled text generation (CTG) seeks to guide large language model (LLM)
output to produce text that conforms to desired criteria. The current study
presents a novel CTG algorithm that enforces adherence toward specific
rhetorical relations in an LLM sentence-completion context by a parser-driven
decoding scheme that requires no model fine-tuning. The method is validated
both with automatic and human evaluation. The code is accessible on GitHub.111
https://github.com/joshua-zingale/plug-and-play-rst-ctg

##  1 Introduction

Despite outstanding success, Large Language Models (LLMs) are black-box in
nature and perform unpredictably. They are known to generate non-facts and to
deviate from desired criteria for generation (Ji et al., 2023). Controlled
text generation (CTG) seeks to enforce constraints upon LLM-generated text,
such as favoring the generation of pre-specified words or phrases or sentence
structures, or requiring adherence to pre-specified communicative goals
(Prabhumoye et al., 2020).

For a piece of text to be articulate, it must present a cohesive story using
grammatically correct components that are also logically related to one
another. This paper presents a novel algorithm that attempts to influence the
text generation behavior of an LLM by mandating that certain rhetorical
relationships exist between spans of text. The introduced algorithm
incorporates a pre-existing parser that identifies discourse relationships
among spans of text, within an LLM’s probabilistic process of generation of
text tokens, to produce text components that satisfy desired logical
relationships. In particular, given an input span of text, the approach
generates the next span that holds a desired relation with the given input.

The direct use of the proposed system is the downstream task of generation of
an entire Rhetorical Structure Theory (RST) tree. Such guided generation could
aid specialized domains such as machine translation, where different languages
have different expected orderings of rhetorical relations (Marcu et al.,
2000).

The results show that the proposed method retains generation quality of an
LLM, while enhancing it with a pronounced ability to control the rhetorical
relations between adjacent sentence components. Automatic and human evaluation
verify the effectiveness of the control method in generating high-quality
English text.

Figure 1: Relation-influenced completions for the sentence, “He came to my
house,”. The proposed method generates such completions.

##  2 Related Work

Large language models (LLMs), such as the GPT series OpenAI (2023), PaLM
Narang and Chowdhery (2022), LLaMa Touvron et al. (2023a, b), and BLOOM
Hugging Face (2022) generate text autoregressively, generating the next token
conditioned on previously generated text. LLMs, pre-trained on vast corpora of
text data, have demonstrated versatility in fluent text generation across
domains (Wu et al., 2023). However, these probabilistic models generate text
in a black-box manner without the user’s full understanding or control of the
underlying generative process. Controlled text generation attempts to modify
the generation of text by LLMs by exerting influence on the next token being
produced.

An attempt at controlling text generation includes Baumler and Ray’s use of
phrase-structure parses of sentences generated by a language model and a
database of world knowledge to modify generated phrases by inserting fact-
driven words as applicable (2022). Zhou et al. (2022) utilize a common-sense
database to append knowledge to a language model prompt, enabling the language
model to incorporate relevant information. Zhou et al. (2023) use prompt
engineering to instruct a language model to generate sentences with specific
lexical, syntactic, semantic, style, or length constraints.

Mann and Thompson (1988) introduced a theory of discourse called Rhetorical
Structure Theory formally to articulate how clausal units in a sentence and
between sentences relate to one another to deliver meaning coherently. RST
represents a collection of Elementary Discourse Units (EDUs) as a tree
structure. Although a descriptive theory, RST has been used to drive
objectives in natural language processing, including summarization, machine
translation, and generation (Afantenos et al., 2005; Marcu et al., 2000;
Vander Linden and Martin, 1995). These early efforts in using RST to generate
text were able to impose structure but were unable to generate fluent text. On
the flip side LLMs are good at generating fluent text, although are not
amenable to being explicitly controlled.

The so-called plug-and-play approaches to CTG allow for controlled generation
of text without expensive fine-tuning of the language models (Dathathri et
al., 2020; Zhang et al., 2023). For example, Liu et al. (2022) train a parser
relevant to recipe generation and use it to re-rank the token distribution
from a language model, resulting in controlled generation of recipes.

Building off the success of recent methods in integrating traditional
computational linguistics tools, the present study integrates RST with large
language modeling through a plug-and-play combination of an RST parser and a
language model.

To the best of our knowledge, there is no equivalent method against which to
test our system. We attempted to utilize prompting to guide BLOOM 1.7B toward
generation of relation completions as a baseline; but this smaller model
showed no ability to complete these relations with prompt engineering. This
further bolsters the proposed method because, through it, the model can
generate according to instructions that the model otherwise could not follow.

Figure 2: The generation pipeline. Given the top-$p$ nucleus vocabulary of the
distribution from the LLM, the parser re-ranks the tokens according to which
tokens better fit the desired relation.

##  3 Models

The proposed method uses two models for text generation. The first is a
general language model without any RST pretraining. The second is an RST
parser.

#### BLOOM 1.7B:

BLOOM is a multilingual decoder-only transformer language model trained on the
$1.61$ terabyte ROOTS corpus, which contains $46$ natural languages alongside
$13$ programming languages (Scao et al., 2023; Laurençon et al., 2022). The
current study uses the 1.7-billion-parameter version of the model because of
computational limitations for this study. A BLOOM model is decoder-only,
allowing autoregressive generation of text.

#### DMRST:

RST parsing consists of two tasks—segmentation and relation attribution.
Segmentation is the task of converting a document into a collection of EDUs,
the basic units in RST. Relation attribution, on the other hand, arranges
these EDUs into a binary tree, assigning each edge to be a specific relation
between two EDUs. DMRST segments and parses raw text into an RST tree (Liu et
al., 2021, 2020). Importantly for the present study, DMRST also can be
configured to perform relation attribution for a preset segmentation upon a
document.

DMRST classifies between $42$ relations, where varying nuclearity
configurations count as different relations. Each relation’s name is of the
form

$\displaystyle\text{\\{Relation\\}\\_\\{Nuclearities\\}},$

where Relation is any of 18 categories, such as Contrast or Attribution, and
Nuclearities is NN to mean the relation is between two nuclei, NS to mean the
left component is a nucleus and the right component is a satellite, and SN for
the other ordering of the nucleus and satellite.

The code for DMRST is publicly available.222https://github.com/seq-to-
mind/DMRST_Parser

##  4 Method

Given a prompt and a relation, the pipeline generates a single EDU that
continues the prompt while maintaining the given relation between the prompt
and the generated EDU. For each generation step, the language model first
yields a distribution across all tokens conditioned on the prompt and the
already generated tokens. Then, the RST parser re-ranks the top of the
distribution to favor tokens that fit the desired relation. Finally, the next
token is selected from this re-ranked top of the distribution and the process
continues until the parser detects the end of the EDU.

#### Generation:

The pipeline receives relation $r$ and prompt $X$, comprising of a string of
tokens, $x_{1},x_{2}\ldots,x_{U}$, from the language model’s vocabulary $V$.
The pipeline then returns continuation $Y$, which comprises of tokens,
$y_{1},\ldots,y_{T}\in V$, such that $Y$ continues $X$ while maintaining
relation $r$ with $X$. Generation of token $y_{t}$ begins by finding the
top-$p$, $0<p\leq 1$, nucleus vocabulary $V^{(p)}\subset V$ (Holtzman et al.,
2019). $V^{(p)}$ is the smallest subset that satisfies

$\sum_{y\in V^{(p)}}P(y|X,Y_{<t})\geq p,$

where each token in $V^{({p})}$ is more likely than or equally likely to each
token not in $V^{(p)}$, where $Y_{<t}$ is all tokens generated before timestep
$t$, and where each $y$’s likelihood is calculated by the language model. The
size of $V^{(p)}$ is here capped at $k$.

The RST parser has token vocabulary $V^{\prime}$, which is different from $V$.
Therefore, the prompt and all tokens already generated are re-tokenized to
$V^{\prime}$ and are given by $X^{\prime}$ and $Y_{<t}^{\prime}$. Each $y\in
V^{(p)}$ is also re-tokenized to $V^{\prime}$ and is given by $y^{\prime}$,
where $y^{\prime}$ may be more than one token.

The RST parser then scores each $y\in V^{(p)}$ first by finding the logit
value associated with the likelihood that the already generated sequence,
$Y_{<t}^{\prime}$, appended by $y^{\prime}$, satisfies the desired relation
$r$ with $X^{\prime}$, calculated as

$\text{logit}_{r}(y)=D_{r}(X^{\prime},Y_{<t}^{\prime}\oplus y^{\prime}),$

where $\oplus$ is concatenation. The DMRST parser is given a preset
segmentation such that the parser only finds the relation between $X^{\prime}$
and $Y^{\prime}_{<t}\oplus y^{\prime}$. After $\text{logit}_{r}(y)$ is found
for each $y\in V^{(p)}$, the parser score for each $y$ is given by calculating
a temperatured (with $\tau$) softmax function across all
$\text{logit}_{r}(y)$:

$\text{score}_{r}(y)=\frac{e^{\frac{1}{\tau}\text{logit}_{r}(y)}}{\sum_{w\in
V^{(p)}}e^{\frac{1}{\tau}\text{logit}_{r}(w)}}.$

Following Liu et al. (2022), the next token, $y_{t}$, is calculated greedily
with

$y_{t}=\operatorname*{argmax}_{y\in
V^{(p)}}[P(y|X,Y_{<t})^{(1-\alpha)}\cdot\text{score}_{r}(y)^{\alpha}],$

where $0\leq\alpha\leq 1$ determines how much power the parser has to modify
the language model’s distribution and where, again, the likelihood of $y$ is
provided by the language model.

#### Stopping:

If the parser detects that an entire EDU has been generated, generation ends.

For ending generation, the DMRST segmenter is used. Given an input string of
tokens, the DMRST parser breaks up the string into EDUs. For segmentation with
the parser, we write, for some input sequence of tokens $W$,

$S(W)=(e_{1},e_{2},\ldots,e_{L}),$

where $e_{i}$ is a sequence of tokens such that $e_{i}$ is itself an EDU and
$e_{1}\oplus e_{2}\oplus\ldots\oplus e_{L}$ is the input sequence, $W$. To
know when to stop generation, the segmenter finds that the prompt,
$X^{\prime}$, has $P$ EDUs. Then, generation continues as outlined previously
until the segmenter finds $S(X^{\prime}\oplus Y_{<t}^{\prime})$ to result in
more than $P+1$ EDUs. After stopping generation, the pipeline determines the
smallest $N$ such that $X^{\prime}\subset e_{1}\oplus e_{2}\oplus\ldots\oplus
e_{N}$333$\subset$ here indicates a proper subset.. The output, then, is
$e_{1}\oplus e_{2}\oplus\ldots\oplus e_{N}$, with the input tokens, those from
$X^{\prime}$, removed from the beginning of the sequence.

##  5 Experiments

The proposed text generation method is evaluated both by automatic measures
and by human feedback. The method is tested with seven relations that were
selected for their ease of understanding to lay annotators. Four volunteer
native English speakers each composed $20$ short English sentences according
to instructions (Appendix B). The instructions requested that the sentences be
diverse in content, including tense. The proposed method generated eight
completions for each of these $80$ sentences—seven for the seven relations
being tested and one for no relation, that is, regular generation with the
language model.

The parameter values used in the generation are
$p=0.75,k=100,\tau=0.1,\alpha=0.7$. For all completions, generation was
forced, if it had not already stopped by itself, to cease after $30$ tokens or
a period had been generated.

Relation | Correct% | Perplexity
---|---|---
Cause_NS | 96.3 | 61.7
Condition_NS | 58.8 | 44.1
Contrast_NN | 95.0 | 52.4
Elaboration_NS | 95.0 | 47.0
Evaluation_NS | 33.8 | 56.2
Joint_NN | 100 | 31.5
Manner-Means_NS | 82.5 | 45.4
All Relations | 80.2 | 48.3
None | - | 43.9
Table 1: The automatic-evaluation statistics for each relation, where None is
generation with the language model alone.

#### Automatic Evaluation:

The input text alongside its completion is automatically parsed using the
DMRST parser. As seen in Table 1, five of the seven relations are parsed in
accordance with each’s desired relation more than $82\%$ of the time, four
greater than or equal to $95\%$ of the time, and one is parsed to the desired
relation for all tested prompts. These results indicate that the proposed
control method effectively controls outputs such that they be parsed according
to their desired relations.

Perplexity is used as a crude measure for the quality of the generated text,
with lower numbers being better. One worry is that this control method may
degrade the quality of the generated completions. We therefore consider the
average perplexity of completions generated without this control method for
comparison.

Table 1 reveals that the secondary objective does not increase perplexity by
much. In the case of Joint_NN, there even is a drop in perplexity from
generation with no relation. The results indicate that the control method does
not cause the generated text to stray far from the language model’s off-the-
shelf distribution. Thus, to the degree that BLOOM 1.7B accurately models
language, the proposed method should also generate quality text. Appendix A
has similar automatic evaluation results for Spanish generations.

Relation | Rel | Flu | Rea
---|---|---|---
Cause_NS | 3.47 | 4.62 | 3.80
Condition_NS | 3.25 | 3.82 | 3.98
Contrast_NN | 3.97 | 4.02 | 3.67
Elaboration_NS | 3.70 | 4.35 | 3.75
Evaluation_NS | 2.47 | 3.97 | 3.75
Joint_NN | 4.02 | 4.05 | 4.32
Manner-Means_NS | 3.57 | 3.57 | 4.13
All Relations | 3.49 | 4.05 | 3.91
None | - | 4.16 | 3.80
Table 2: The human-evaluation statistics for each relation, where None is
generation with the language model alone. The metrics are (Rel[ation-fit]),
(Flu[ency]), and (Rea[sonableness]).

#### Human Evaluation:

A subset containing 210 generated completions is used for human evaluation.
The random subset contains $20$ completions for each of the seven relations
and $70$ completions with no enforced relation.

Three native English speakers evaluated the generations across fluency,
reasonableness, and relation-fit according to instructions in Appendix B. The
annotators first rated the fluency and reasonableness and then rated the
relation-fit of each completion because it does not reveal which relations
influenced which completions, avoiding biasing annotator ratings. For all
metrics, each prompt-completion pair was rated on a scale form one to five.

Fluency measures how grammatically correct a sentence is. Reasonableness
measures how much sense a sentence makes.

Table 2 shows the average ratings for each relation. The average fluency for
all relations is only slightly lower than for no relation, $4.05$ against
$4.16$, with the fluency for different relations ranging from $3.57$ to
$4.62$. The average reasonableness for all relations is actually higher than
that for no relation, $3.91$ against $3.80$. relation-fit is the degree to
which the generation satisfied the desired relation.

The average annotator rating of relation-fit for generation with each of the
relations is presented in Table 2. The overall average, $3.49$, is well within
the positive range. Evaluation_NS is unique in being poor, receiving an
average of $2.47$.

##  6 Perturbation Analysis

Figure 3: At each step of generation, the average difference between the
highest and the lowest DMRST parser-assigned score in the nucleus vocabulary
across $560$ generations using seven different relations.

Knowing where the proposed method most compels an alteration in token choice
to occur grants insight to the problem of CTG with RST. We measure the degree
of perturbation for each step of generation in a way semi-independent of
$\alpha$, the generation parameter that determines how much the proposed
method may perturb the language model’s distribution.

After the top-$p$ nucleus vocabulary from the language model is obtained, the
DMRST parser re-ranks each of these by creating a new token distribution,
wherein each token is likely in as much as the parser sees the token to fit
the desired relation. The difference between the score of the highest and
lowest parser-scored token is a proxy for how much the parser will re-rank, or
perturb, the regular distribution. When the difference is smaller, tokens are
not re-ranked as much as when the difference is larger. This, when only
considering a single step of generation, is a measure independent of $\alpha$.

Figure 3 displays the average, across $560$ generations, of this difference
for each generation step. The generations comprise of seven completions
influenced by the relations heretofore used for each of the $80$ human-
generated prompts. Generation here used the same parameters as were used in
Experiments. After the first token’s generation, which has an average of
$0.42$, the average difference drops to $0.18$ and then after the fourth step
below $0.1$. Hence, the most control is exerted during the generation of the
first tokens, which makes sense when considering that the words that
explicitly begin the relation completions tested in this study for English are
often headed with specific words or phrases. One example is Contrast_NN, for
which completions typically begin with “but” or another adversative such as
“instead.” After generating this first word or phrase, the decreased value of
the difference, in conjunction with human evaluation confirming that the
proposed method maintains comparable fluency, means that the language model,
now generating conditioned on this initial relation-specific start,
successfully adjusts to the desired relation without much further assistance
from the parser.

##  7 Conclusion

Validated by automatic and human evaluation, the proposed control method is
able to enforce a rhetorical relation during English sentence completion
without sacrificing fluency or reasonableness. The perplexity, fluency, and
reasonableness metrics show that the proposed method does not degrade the
quality of generated text while correct% and relation-fit indicates the
control method’s success.

##  8 Limitations

For lack of resources, the present study was not able to run reportable
ablation studies with various generation parameters $p$, $k$, $\tau$, and
$\alpha$. Also, the effect on the control method and on generation quality of
replacing greedy generation, as was herein used, with sampling from the
distribution or with beam search has not been measured.

For the human evaluation, there currently is no baseline for the relation-fit
metric, making the scores hard to interpret. Therefore the effect of the
control method has been best measured here with the automatic scores, i.e.
correct%. While this automatic metric does show that the control method
conforms the language model to the parser, it does not guarantee that the
generation’s conforming to the parser indicates true completion of the
controlled-generation task.

The proposed method requires that the a discourse parser be run between the
prompt and generation for each of the considered next tokens. Thus is the
computational overhead for generation increased.

##  9 Acknowledgements

All work herein reported is supported by the Nation Science Foundation under
Grant No. 2050919. Any opinion, finding, or conclusion in this study is that
of the authors and does not necessarily reflect the views of the National
Science Foundation. We thank the participants that made the evaluation portion
of this study possible.

## References

  * Afantenos et al. (2005) Stergos Afantenos, Vangelis Karkaletsis, and Panagiotis Stamatopoulos. 2005.  Summarization from medical documents: a survey.  _Artificial Intelligence in Medicine_ , 33(2):157–177.
  * Baumler and Ray (2022) Connor Baumler and Soumya Ray. 2022.  Hybrid Semantics for Goal-Directed Natural Language Generation.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1936–1946, Dublin, Ireland. Association for Computational Linguistics.
  * Dathathri et al. (2020) Sumanth Dathathri, Andrea Madotto, Janice Lan, Jane Hung, Eric Frank, Piero Molino, Jason Yosinski, and Rosanne Liu. 2020.  Plug and Play Language Models: A Simple Approach to Controlled Text Generation.  ArXiv:1912.02164.
  * Holtzman et al. (2019) Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. 2019.  The curious case of neural text degeneration.  _arXiv preprint arXiv:1904.09751_.
  * Hugging Face (2022) Hugging Face. 2022.  BigScience Large Open-science Open-access Multilingual Language Model.
  * Ji et al. (2023) Ziwei Ji, Nayeon Lee, Rita Frieske, Tiezheng Yu, Dan Su, Yan Xu, Etsuko Ishii, Ye Jin Bang, Andrea Madotto, and Pascale Fung. 2023.  Survey of hallucination in natural language generation.  _ACM Computing Surveys_ , 55(12):1–38.  Publisher: ACM New York, NY.
  * Laurençon et al. (2022) Hugo Laurençon, Lucile Saulnier, Thomas Wang, Christopher Akiki, Albert Villanova del Moral, Teven Le Scao, Leandro Von Werra, Chenghao Mou, Eduardo González Ponferrada, and Huu Nguyen. 2022.  The bigscience roots corpus: A 1.6 tb composite multilingual dataset.  _Advances in Neural Information Processing Systems_ , 35:31809–31826.
  * Liu et al. (2022) Yinhong Liu, Yixuan Su, Ehsan Shareghi, and Nigel Collier. 2022.  Plug-and-play recipe generation with content planning.  In _Proceedings of the 2nd Workshop on Natural Language Generation, Evaluation, and Metrics (GEM)_ , pages 223–234, Abu Dhabi, United Arab Emirates (Hybrid). Association for Computational Linguistics.
  * Liu et al. (2020) Zhengyuan Liu, Ke Shi, and Nancy Chen. 2020.  Multilingual neural RST discourse parsing.  In _Proceedings of the 28th International Conference on Computational Linguistics_ , pages 6730–6738, Barcelona, Spain (Online). International Committee on Computational Linguistics.
  * Liu et al. (2021) Zhengyuan Liu, Ke Shi, and Nancy Chen. 2021.  DMRST: A joint framework for document-level multilingual RST discourse segmentation and parsing.  In _Proceedings of the 2nd Workshop on Computational Approaches to Discourse_ , pages 154–164, Punta Cana, Dominican Republic and Online. Association for Computational Linguistics.
  * Mann and Thompson (1988) William C. Mann and Sandra A. Thompson. 1988.  Rhetorical structure theory: Toward a functional theory of text organization.  _Text-interdisciplinary Journal for the Study of Discourse_ , 8(3):243–281.  Publisher: De Gruyter Mouton.
  * Marcu et al. (2000) Daniel Marcu, Lynn Carlson, and Maki Watanabe. 2000.  The Automatic Translation of Discourse Structures.  In _1st Meeting of the North American Chapter of the Association for Computational Linguistics_.
  * Narang and Chowdhery (2022) Sharan Narang and Aakanksha Chowdhery. 2022.  Pathways Language Model (PALM): Scaling to 540 billion parameters for breakthrough performance.  _Google AI Blog_.
  * OpenAI (2023) OpenAI. 2023.  GPT-4 Technical Report.  ArXiv:2303.08774.
  * Prabhumoye et al. (2020) Shrimai Prabhumoye, Alan W Black, and Ruslan Salakhutdinov. 2020.  Exploring controllable text generation techniques.  In _Proceedings of the 28th International Conference on Computational Linguistics_ , pages 1–14, Barcelona, Spain (Online). International Committee on Computational Linguistics.
  * Scao et al. (2023) Teven Le Scao, Angela Fan, Christopher Akiki, and et al. 2023.  BLOOM: A 176B-Parameter Open-Access Multilingual Language Model.  ArXiv:2211.05100.
  * Touvron et al. (2023a) Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurelien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. 2023a.  LLaMA: Open and Efficient Foundation Language Models.  ArXiv:2302.13971.
  * Touvron et al. (2023b) Hugo Touvron, Louis Martin, Kevin Stone, and et al. 2023b.  Llama 2: Open Foundation and Fine-Tuned Chat Models.  ArXiv:2307.09288.
  * Vander Linden and Martin (1995) Keith Vander Linden and James H. Martin. 1995.  Expressing rhetorical relations in instructional text: A case study of the purpose relation.  _Computational Linguistics_ , 21(1):29–57.
  * Wu et al. (2023) Jiayang Wu, Wensheng Gan, Zefeng Chen, Shicheng Wan, and Hong Lin. 2023.  AI-Generated Content (AIGC): A Survey.  ArXiv:2304.06632 [cs].
  * Zhang et al. (2023) Hanqing Zhang, Haolin Song, Shaoyu Li, Ming Zhou, and Dawei Song. 2023.  A survey of controllable text generation using transformer-based pre-trained language models.  _ACM Comput. Surv._ , 56(3).
  * Zhou et al. (2022) Pei Zhou, Karthik Gopalakrishnan, Behnam Hedayatnia, Seokhwan Kim, Jay Pujara, Xiang Ren, Yang Liu, and Dilek Hakkani-Tur. 2022.  Think Before You Speak: Explicitly Generating Implicit Commonsense Knowledge for Response Generation.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1237–1252, Dublin, Ireland. Association for Computational Linguistics.
  * Zhou et al. (2023) Wangchunshu Zhou, Yuchen Eleanor Jiang, Ethan Wilcox, Ryan Cotterell, and Mrinmaya Sachan. 2023.  Controlled text generation with natural language instructions.  In _Proceedings of the 40th International Conference on Machine Learning_ , volume 202 of _Proceedings of Machine Learning Research_ , pages 42602–42613. PMLR.

## Appendix

###  A Spanish Automatic Evaluation

Relation | Correct% | BLOOM
---|---|---
Cause_NS | 95.0 | 39.8
Condition_NS | 43.0 | 25.2
Contrast_NN | 99.0 | 31.3
Elaboration_NS | 99.0 | 28.4
Evaluation_NS | 36.0 | 26.1
Joint_NN | 100 | 23.3
Manner-Means_NS | 86.0 | 30.8
All Relations | 79.7 | 29.3
None | - | 19.5
Table 3: The Spanish-language automatic evaluation statistics for each
relation, where None is generation with the language model alone and All
Relations is all seven presented above combined. The same $100$ prompts are
used to generate $100$ completions for each relation. Correct% is the percent
of the generations that parse, using DMRST, to the relation that controlled
their composition. BLOOM is the generations’ average perplexity as measured by
BLOOM 1.7B.

Since both BLOOM 1.7B and DMRST support Spanish, no modifications are needed
for the system to work with Spanish. Similar to the English automatic
evaluation, we ran automatic evaluation on Spanish prompts.

To collect a set of Spanish-language prompts, ChatGPT 3.5 (OpenAI, 2023) was
used to produce $100$ short diverse sentences in Spanish that employ various
verb tenses. As with the English prompts, the $100$ short sentences were
converted to $100$ prompts by removing any trailing punctuation and adding a
comma and a space where the punctuation was removed.

The same parameters as were used for the English generation are used to
generate eight completions for each of the $100$ prompts—one for each of seven
relations and one for no relation. This leads to a total of $800$ Spanish
completions.

Table 3 includes the same metrics as were used for English-language automatic
evaluation.

As with the automatic evaluation for English, the proposed method effectively
controls generation, i.e. is parsed to obtain the desired relation most of the
time. $79.7\%$ of the completions result in the desired parsing. The method
again does not increase the perplexity much, with an average relation
perplexity of $29.3$ against the no relation perplexity of $19.5$. This again
indicates that the method does not cause generation to stray far from the
language model’s regular distribution, implying that the quality of generation
is comparable to that without the control method.

###  B Human Evaluation Instructions

Starting on the next page are attached the instructions given to the
volunteers that generated the prompts for human evaluation and the
instructions for the human annotators that rated the proposed method’s
generations.

See pages - of instructions.pdf


7

# Homogeneous length functions on Groups:
Intertwined computer & human proofs

Siddhartha Gadgil  Department of Mathematics,
Indian Institute of Science,
Bangalore 560012, India<EMAIL_ADDRESS>
###### Abstract.

We describe a case of an interplay between human and computer proving which
played a role in the discovery of an interesting mathematical result [4]. 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.

###### Key words and phrases:

type theory; homotopy type theory; geometric group theory

###### 2010 Mathematics Subject Classification:

03B15 (primary), 20F12, 20F65 (secondary)

##  1\. Introduction

Computers have come to play many roles in mathematical proofs. Computer
experimentation is commonly used to make conjectures and computer algebra
systems are used for sophisticated calculations. Components of proofs of
important results have also been provided by computers. Such rigorous computer
proofs often generate independently verifiable _proof certificates_. Proof
assistants have been used to formalize proofs, including some very complex
ones.

Here we describe a case different from these – where a computer generated but
human readable proof was read, understood, generalized and abstracted by
mathematicians to obtain the key lemma in a significant mathematical result.
So far as we know this is the only such instance so far.

The result we discuss concerned a question about the existence of so called
_homogeneous length functions_ , which was asked by Terrence Tao on his blog
(Apoorva Khare had asked Tao this question). The question was answered in six
days in a collaboration that became PolyMath 14111Participants: T. Fritz, S.
Gadgil, A. Khare, P. Nielsen, L. Silberman, T. Tao., and the answer (and
stronger results) have been published in [4].

To state the main question, we need some definitions. We emphasise that in
general the groups $G$ we consider are not abelian (commutative), i.e., if
$x,y\in G$, we may have $xy\neq yx$. Thus the notation we use is
multiplicative, similar to that for matrix multiplication (except with the
identity denoted as $e$ rather than $I$). Recall that, for fixed
$n\in\mathbb{N}$, _invertible_ $n\times n$ matrices form a group.

We sometimes denote the product of $x$ and $y$ as $x\cdot y$ instead of $xy$
for readability.

######  Definition 1.1.

A _pseudo-length function_ on a group $G$ is a function $l:G\to[0,\infty)$
such that

  * •

$l(e)=0$, where $e\in G$ is the identity.

  * •

$l(g^{-1})=l(g)$ for all $g\in G$ (symmetry).

  * •

$l(gh)\leq l(g)+l(h)$ for all $g,h\in G$ (the triangle inequality).

######  Definition 1.2 (Conjugacy invariance).

A pseudo-length function $l$ on a group $G$ is said to be _conjugacy
invariant_ if $l(ghg^{-1})=l(h)$ for all $g,h\in G$.

Recall that elements $x,y\in G$ are conjugate if there exists $g\in G$ such
that $y=gxg^{-1}$. Conjugacy invariance is thus the property that conjugate
elements have equal lengths. Note that in an abelian group, conjugate elements
are equal, so this property is automatically satisfied.

######  Definition 1.3 (Homogeneity).

A pseudo-length function $l$ on a group $G$ is said to be _homogeneous_ if
$l(g^{n})=n\cdot l(g)$ for all $g\in G$, $n\in\mathbb{Z}$.

######  Definition 1.4 (Positivity).

A pseudo-length function $l$ on a group $G$ is said to be a _length function_
if $l(g)>0$ for all $g\in G\setminus\\{e\\}$.

If $G=(V,+)$ is the additive group of a vector space $V$ over $\mathbb{R}$,
then a _norm_ on $V$ gives a homogeneous, conjugacy invariant length function.
For example on $\mathbb{R}^{2}$ both $l_{1}(x,y)=|x|+|y|$ and
$l_{2}(x,y)=\sqrt{x^{2}+y^{2}}$ are homogeneous, conjugacy invariant length
functions. To see this, note that the properties of a pseudo-length follow
from the definition of norms. As mentioned above, conjugacy invariance is
automatic as additive groups of vector spaces are abelian.

It was generalizing norms on Vector Spaces that motivated the main question
(we elaborate on this after stating Question 1.5). The question was formulated
in terms of free groups as these are the prototypical non-abelian groups.

Recall that the free group $\langle\alpha,\beta\rangle$ on $2$ generators
$\alpha$ and $\beta$ is the group whose elements are _equivalence classes_ of
words in $S=\\{\alpha$, $\beta$, $\alpha^{-1}$, $\beta^{-1}\\}$, where we
think of $\alpha^{-1}$ and $\beta^{-1}$ as simply formal symbols (we will see
that in $\langle\alpha,\beta\rangle$ their equivalence classes are inverses of
the equivalence classes of $\alpha$ and $\beta$). Namely, we define an
equivalence relation $\sim$ so that two words equivalent if and only if they
are related by a sequence of moves given by cancellation of pairs of adjacent
letters that are inverses of each other and its inverse move, namely
_inserting_ a cancelling pair of letters. For example, in
$\langle\alpha,\beta\rangle$,
$\alpha\beta\beta^{-1}\alpha\beta\alpha^{-1}=\alpha\alpha\beta\alpha^{-1}$ as
cancelling the second and third letters of
$\alpha\beta\beta^{-1}\alpha\beta\alpha^{-1}$ gives
$\alpha\alpha\beta\alpha^{-1}$. Conversely, inserting $\beta\beta^{-1}$
between the first and second letters of $\alpha\alpha\beta\alpha^{-1}$ gives
$\alpha\beta\beta^{-1}\alpha\beta\alpha^{-1}$.

Formally, we consider the equivalence relation $\sim$ on words in $S$
generated by

$\xi_{1}\xi_{2}\dots\xi_{m}\lambda\lambda^{-1}\xi_{m+1}\dots\xi_{n}\sim\xi_{1}\xi_{2}\dots\xi_{m}\xi_{m+1}\dots\xi_{n}$

where $\lambda\in S$, $\xi_{i}\in S\ \forall i,1\leq i\leq n$ and $0\leq m\leq
n$. The case $m=0$ corresponds to prepending a cancelling pair, and $m=n$ to
appending a cancelling pair. The case $n=0$ (which forces $m=0$) corresponds
to the empty word. The elements of $\langle\alpha,\beta\rangle$ are
equivalence classes under this equivalence relation.

Multiplication in $\langle\alpha,\beta\rangle$ is given by concatenation, i.e.

$(\xi_{1}\xi_{2}\dots\xi_{n})\cdot(l^{\prime}_{1}l^{\prime}_{2}\dots
l^{\prime}_{m})=\xi_{1}\xi_{2}\dots\xi_{n}l^{\prime}_{1}l^{\prime}_{2}\dots
l^{\prime}_{m}$

where $\cdot$ denotes the group multiplication. More formally, concatenation
of words induces a well-defined multiplication on equivalence classes under
$\sim$ of words. The identity is the empty word $e$ (more formally the
equivalence class of $e$), and the inverse of an element is obtained by
inverting letters and reversing the order, i.e.,
$(\xi_{1}\xi_{2}\dots\xi_{n})^{-1}=\xi_{n}^{-1}\dots\xi_{2}^{-1}\xi_{1}^{-1}$.

We can now state the main question that was studied.

######  Question 1.5.

Is there a homogeneous, conjugacy-invariant length function $l$ on the free
group $\langle\alpha,\beta\rangle$ on $2$ generators?

Khare asked this question motivated by wanting to generalize results of Khare-
Rajaratnam [2][3] from vector spaces with norms to a more general context
where commutativity was no longer assumed. However, it was not clear whether
any (additional) examples would satisfy this more general hypothesis. The free
group was taken as a prototypical group which is not abelian. In fact the
results of [4] show that, in a strong sense, the only groups having
homogeneous, conjugacy invariant length functions are abelian groups, and all
such functions are restrictions of norms to subgroups of vector spaces.

The question is also natural from the point of view of Geometric group theory,
where length functions are a central concept and conjugacy invariance of
lengths (which corresponds to bi-invariance of metrics) is also commonly
studied. Lengths satisfying the additional condition of _homogeneity_ were not
much studied previously – which we now know is because there are no
interesting examples (except restrictions of norms on vector spaces, which are
well understood).

##  2\. Homogeneous length functions and the Internal repetition trick

We now describe the history and some ingredients of the solution Question 1.5.

It is natural to view Question 1.5 as asking whether a homogeneous, conjugacy-
invariant pseudo-length function $l$ on $\langle\alpha,\beta\rangle$ can also
be positive, hence a length function. Further, we can normalize to assume that
$l(s)\leq 1$ for $s=\alpha,\beta$ (hence, by symmetry, $l(s)\leq 1$ for
$s=\alpha^{-1},\beta^{-1}$). We shall say $l$ is _normalized_ if $l(s)\leq 1$
for $s=\alpha,\beta,\alpha^{-1},\beta^{-1}$.

After the failure of various constructions (by day $3$), the following
conjecture seemed likely.

######  Conjecture 2.1.

For any homogeneous, conjugacy-invariant pseudo-length function $l$ on
$\langle\alpha,\beta\rangle$, we have $l(\alpha\beta\alpha^{-1}\beta^{-1})=0$.

In particular, this conjecture implies that $l$ cannot be a length function.
Note that it is natural to focus on the element
$\alpha\beta\alpha^{-1}\beta^{-1}$ as a group $G$ is abelian if and only if
$xyx^{-1}y^{-1}=1\ \forall x,y\in G$, and we were trying to understand whether
there are non-abelian examples of groups with length functions with the
desired properties.

Several bounds on $l(\alpha\beta\alpha^{-1}\beta^{-1})$ were obtained from the
hypothesis, giving bounds that even went below $1$. However, these methods
appeared to stagnate with the best bound obtained a little above $0.9$.

Using computer-assistance, we obtained and posted a human readable proof
showing $l(\alpha\beta\alpha^{-1}\beta^{-1})\leq 0.82$. An extract of this
proof is below222https://github.com/siddhartha-
gadgil/Superficial/wiki/A-commutator-bound for the full proof as originally
posted.. Note that we have used somewhat different notation here – the
generators are $a$ and $b$ and their inverses are denoted $\bar{a}$ and
$\bar{b}$. We remark that a fully expanded proof actually had over 2000 lines,
but avoiding duplication gave the posted $126$ lines.

  * •

$|\bar{a}|\leq 1.0$

  * •

$|\bar{b}\bar{a}b|\leq 1.0$ using $|\bar{a}|\leq 1.0$

  * •

$|\bar{b}|\leq 1.0$

  * •

$|a\bar{b}\bar{a}|\leq 1.0$ using $|\bar{b}|\leq 1.0$

  * •

$|\bar{a}\bar{b}ab\bar{a}\bar{b}|\leq 2.0$ using $|\bar{a}\bar{b}a|\leq 1.0$
and $|b\bar{a}\bar{b}|\leq 1.0$

  * •

… (119 lines)

  * •

$|ab\bar{a}\bar{b}ab\bar{a}\bar{b}ab\bar{a}\bar{b}ab\bar{a}\bar{b}ab\bar{a}\bar{b}ab\bar{a}\bar{b}ab\bar{a}\bar{b}ab\bar{a}\bar{b}ab\bar{a}\bar{b}ab\bar{a}\bar{b}ab\bar{a}\bar{b}ab\bar{a}\bar{b}ab\bar{a}\bar{b}ab\bar{a}\bar{b}ab\bar{a}\bar{b}ab\bar{a}\bar{b}ab\bar{a}\bar{b}|\leq
13.859649122807017$
using $|ab\bar{a}|\leq 1.0$ and
$|\bar{b}ab\bar{a}\bar{b}ab\bar{a}\bar{b}ab\bar{a}\bar{b}ab\bar{a}\bar{b}ab\bar{a}\bar{b}ab\bar{a}\bar{b}ab\bar{a}\bar{b}ab\bar{a}\bar{b}ab\bar{a}\bar{b}ab\bar{a}\bar{b}ab\bar{a}\bar{b}ab\bar{a}\bar{b}ab\bar{a}\bar{b}ab\bar{a}\bar{b}ab\bar{a}\bar{b}ab\bar{a}\bar{b}|\leq
12.859649122807017$

  * •

$|ab\bar{a}\bar{b}|\leq 0.8152734778121775$ using
$|ab\bar{a}\bar{b}ab\bar{a}\bar{b}ab\bar{a}\bar{b}ab\bar{a}\bar{b}ab\bar{a}\bar{b}ab\bar{a}\bar{b}ab\bar{a}\bar{b}ab\bar{a}\bar{b}ab\bar{a}\bar{b}ab\bar{a}\bar{b}ab\bar{a}\bar{b}ab\bar{a}\bar{b}ab\bar{a}\bar{b}ab\bar{a}\bar{b}ab\bar{a}\bar{b}ab\bar{a}\bar{b}ab\bar{a}\bar{b}|\leq
13.859649122807017$ by
taking 17th power.

This proof was studied, understood and generalized by Pace Nielsen, who called
the method the _internal repetition trick_. After several improvements due to
Nielsen and Tobias Fritz, this was abstracted by Terrence Tao as the following
lemma. Note that this holds for all conjugacy-invariant, homogeneous pseudo-
lengths $l$ on all groups $G$.

######  Lemma 2.2.

Let $x$, $y$, $z$, $w$ in $G$ be such that $x$ is conjugate to both $wy$ and
$zw^{-1}$, i.e., there exist elements $s,t\in G$ such that
$x=swys^{-1}=tzw^{-1}t^{-1}$. Then one has

$l(x)\leq\frac{l(y)+l(z)}{2}.$

Fritz used this to obtain the key lemma.

######  Lemma 2.3.

Let $f(m,k)=l(x^{m}(xyx^{-1}y^{-1})^{k})$. Then

$f(m,k)\leq\frac{f(m-1,k)+f(m+1,k-1)}{2}.$

We apply this lemma to $x=\alpha$, $y=\beta$. An argument based on probability
theory, due to Tao, showed that $l(\alpha\beta\alpha^{-1}\beta^{-1})=0$. This
in particular answered Question 1.5 (the main result proved in [4] is actually
stronger than the Theorem 2.4).

######  Theorem 2.4 (see [4]).

For every homogeneous, conjugacy-invariant pseudo-length function
$l:\langle\alpha,\beta\rangle\to[0,\infty)$, we have
$l(\alpha\beta\alpha^{-1}\beta^{-1})=0$. In particular $l$ is not a length
function.

We mention some of the ingredients in the proof of Theorem 2.4 using Lemma 2.3
with $x=\alpha$ and $y=\beta$. Consider a random walk on points
$(m,k)\in\mathbb{Z}^{2}$ where we move to $(m-1,k)$ (i.e., one step to the
left) with probability $1/2$ and to $(m+1,k-1)$ (i.e, diagonally down and
right) with probability $1/2$. Then Lemma 2.3 says that $f(m,n)$ is at most
the _average_ value of $f$ after one step, and hence inductively after $n$
steps for $n\in\mathbb{N}$. Also observe that we move on an average $1/2$ a
step downwards (the left and right movements cancel on an average). Hence if
we start at a point $(0,n)$, (where $n\in\mathbb{N}$) the distribution after
$2n$ steps is centered around the origin, and $f(0,n)$ is bounded by the
average value of $f$ on this distribution. This average in turn can be bounded
using the Chebyshev inequality (as in the proof of the law of large numbers)
together with the observation that $f(k,l)\leq m+2k$ if $l$ is normalized (the
latter follows by a straightforward inductive use of the triangle inequality
and conjugacy invariance). The bound thus obtained is of the form $f(0,n)\leq
C\sqrt{n}$ for some constant $C\in\mathbb{R}$. Finally, as homogeneity gives
$l(\alpha\beta\alpha^{-1}\beta^{-1})\leq f(0,n)/n$, taking a limit as
$n\to\infty$ gives $l(\alpha\beta\alpha^{-1}\beta^{-1})=0$.

##  3\. The Algorithms

Our proof was generated by a mixture of algorithms and expert guidance (with
some arbitrary choices). More precisely, given certain _auxiliary choices_ , a
_deterministic_ algorithm gave upper bounds $L(g)$ such that $l(g)\leq L(g)$
for all normalized, homogeneous, conjugacy-invariant pseudo-length functions
$l:\langle\alpha,\beta\rangle\to\mathbb{R}$ and for all
$g\in\langle\alpha,\beta\rangle$.

The auxiliary choices were a finite sequence of pairs $(g_{i},n_{i})$, with
$g_{i}\in\langle\alpha,\beta\rangle$ and $n_{i}\in\mathbb{N}$. We used
homogeneity _only_ for these pairs. Thus, our algorithm actually gives an
upper bound for all functions $l:\langle\alpha,\beta\rangle\to\mathbb{R}$ such
that

  * •

$l$ is a normalized, conjugacy-invariant length function on
$\langle\alpha,\beta\rangle$.

  * •

$l(g_{i})\leq l(g_{i}^{n_{i}})/n_{i}$ for all pairs $(g_{i},n_{i})$.

We shall call such pairs $(g_{i},n_{i})$ _homogeneity pairs_ and a sequence of
homogeneity pairs a _homogeneity pair sequence_. Explicit choices for such
pairs that give a proof similar to the posted one are given in 3.7, along with
links to a script to replicate this (which runs in under 10 seconds on a
moderately powerful laptop/desktop). We discuss in 3.8 how plausible it is to
have arrived at such choices through general principles, without expert
guidance.

We used a deterministic algorithm (depending on a homogeneity pair sequence)
to obtain upper bounds $L(g)$ with $l(g)\leq L(g)$ for all lengths as above
and for all $g\in\langle\alpha,\beta\rangle$. Using this, we computed the
bound

$l(\alpha\beta\alpha^{-1}\beta^{-1})\leq\min\\{\frac{L((\alpha\beta\alpha^{-1}\beta^{-1})^{n})}{n}):1\leq
n\leq 20\\}.$

This (after keeping track of inequalities and rendering in human readable
form) was the posted proof.

All pseudo-lengths we consider henceforth will be assumed to be normalized and
conjugacy-invariant (but not necessarily homogeneous).

###  3.1. Maximal homogeneous pseudo-lengths

It is convenient to reformulate our main problem using a standard
construction. Namely, we define a function
$l_{h}:\langle\alpha,\beta\rangle\to\mathbb{R}$ by defining, for
$g\in\langle\alpha,\beta\rangle$, $l_{h}(g)$ to be

$\max\\{l(g):\textrm{ $l$ normalized, homogeneous, conjugacy-invariant pseudo-
length}\\}.$

It is well known that this is well-defined and gives the maximal normalized,
homogeneous, conjugacy-invariant pseudo-length on
$\langle\alpha,\beta\rangle$. Thus, our main problem is equivalent to finding
upper bounds for $l_{h}(g)$, in particular for
$l_{h}(\alpha\beta\alpha^{-1}\beta^{-1})$.

###  3.2. Bounding conjugacy-invariant pseudo-lengths

We now make analogous constructions dropping the homogeneity condition. Let
$\mathcal{L}_{c}$ be the set of all normalized, conjugacy-invariant pseudo-
length functions on $\langle\alpha,\beta\rangle$. We define, for
$g\in\langle\alpha,\beta\rangle$,

$l_{c}(g)=\max\\{l(g):l\in\mathcal{L}_{c}\\}.$

This is well-defined and gives the maximal normalized, conjugacy-invariant
pseudo-length on $\langle\alpha,\beta\rangle$ (i.e., the maximal element of
$\mathcal{L}_{c}$). Further, clearly $l_{h}(g)\leq l_{c}(g)$, so upper bounds
on $l_{c}(g)$ give ones on $l_{h}(g)$.

We describe in Section 3.5 an algorithm to obtain an upper bound $L_{c}(g)$
for $l_{c}(g)$. Indeed this bound is sharp, i.e., we have $l_{c}(g)=L_{c}(g)$
for all $g\in\langle\alpha,\beta\rangle$ (we do not prove or use this, but
this fact motivated our approach). Here and henceforth we follow the
convention that we use $l$ with subscripts to denote pseudo-lengths we wish to
bound (whose definition may be non-constructive) and $L$ with the same
subscript to denote algorithmic upper bounds for these lengths.

###  3.3. Conjugacy-invariant lengths with elementary bounds

Next, suppose we are given a finite set $B$ of pairs $(g_{i},x_{i})$, $1\leq
i\leq m$, with $g\in\langle\alpha,\beta\rangle$ and $x_{i}\geq 0$,
$x_{i}\in\mathbb{R}$ (we call this a set of _elementary bounds_). We consider
a refinement of $l_{c}$ and a corresponding modified algorithm (our
definitions and algorithms do not depend on the order of the pairs
$(g_{i},x_{i})$).

Namely, for $g\in\langle\alpha,\beta\rangle$, we define

$l_{b}(g;B)=\max\\{l(g):l\in\mathcal{L}_{c},\ l(g_{i})\leq x_{i}\
\forall(g_{i},x_{i})\in B\\}.$

The function $l_{b}(g;B)$ is a normalized, conjugacy-invariant pseudo-length
on $\langle\alpha,\beta\rangle$ which is maximal among such lengths that
satisfy the additional bounds $l(g_{i})\leq x_{i}$ for all $(g_{i},x_{i})\in
B$.

Note that $l_{c}(g)=l_{b}(g;\emptyset)$ for $g\in\langle\alpha,\beta\rangle$.
A straightforward modification of the algorithm describing $L_{c}(g)=l_{c}(g)$
gives an algorithm giving bounds $L_{b}(g;B)$ such that $l_{b}(g;B)\leq
L_{b}(g;B)$ for all $g\in\langle\alpha,\beta\rangle$. We remark that the bound
given by this algorithm is not optimal.333Indeed, an optimal algorithm for
$l_{b}(g;B)$ for general finite $B$ gives a solution to the word problem for
groups, which is known to be algorithmically undecidable. Namely, given
_relations_ $r_{1}\in\langle\alpha,\beta\rangle$,
$r_{2}\in\langle\alpha,\beta\rangle$, …$r_{m}\in\langle\alpha,\beta\rangle$,
let $B$ be the set $\\{(r_{1},0),(r_{2},0),\dots,r_{n},0)\\}$. Then
$l_{b}(g;B)=0$ if and only if $g$ is trivial in the group
$\langle\alpha,\beta;r_{1}=e$, $r_{2}=e,\dots r_{m}=e\rangle$.

We shall say that the set of elementary bounds is _admissible_ if
$l_{h}(g_{i})\leq x_{i}$ for all $i$, $1\leq i\leq m$. Observe that we can
algorithmically obtain an admissible set of elementary bounds from a
homogeneity pair sequence $(g_{i},n_{i})$, $1\leq i\leq m$, by setting
$x_{i}=\frac{l_{c}(g_{i}^{n_{i}})}{n_{i}}=\frac{L_{c}(g_{i}^{n_{i}})}{n_{i}}$
as
$l_{h}(x_{i})=\frac{l_{h}(g_{i}^{n_{i}})}{n_{i}}\leq\frac{l_{c}(g_{i}^{n_{i}})}{n_{i}}=x_{i}$.

Note that if a set of elementary bounds $B$ is admissible, then $l_{h}(g)\leq
l(g;B)$ for all $g\in\langle\alpha,\beta\rangle$. Hence $L_{b}(g;B)$ gives an
upper bound for $l_{h}$. We use such a bound, but with the process of
obtaining elementary bounds from a homogeneity pair sequences a refinement of
setting $x_{i}=\frac{l_{c}(g_{i}^{n_{i}})}{n_{i}}$ (and depending on the order
of the pairs).

###  3.4. Bounds with homogeneity pair sequences

In this section we describe algorithms depending on a _homogeneity pair
sequence_ in terms of algorithms depending on _elementary bounds_ ,
essentially by deducing elementary bounds using homogeneity. The algorithms
depending on elementary bounds are described in 3.5, which the reader may
prefer to read first. In 3.6 we describe how to modify the algorithms of 3.5
along the lines described below.

Assume that we are given a homogeneity pair sequence, i.e., a finite sequence
of pairs $(g_{i},n_{i})$, $1\leq i\leq m$. We define inductively in $j$
(simultaneously)

  * •

an elementary bound $(g_{j},x_{j})$ (with the element $g_{j}$ from the given
homogeneity pair sequences),

  * •

a length function $l_{j}:\langle\alpha,\beta\rangle\to\mathbb{R}$, such that
$l_{h}(g)\leq l_{j}(g)$ for all $g\in\langle\alpha,\beta\rangle$, and

  * •

An _algorithmically defined_ length function
$L_{j}:\langle\alpha,\beta\rangle\to\mathbb{R}$, $0\leq i\leq m$, such that
$l_{j}(g)\leq L_{j}(g)$ for all $g\in\langle\alpha,\beta\rangle$.

First, let $l_{0}(g)=l_{c}(g)$. Let $L_{0}(g)=L_{c}(g)$, which we recall can
be computed algorithmically (as described in 3.5).

Next, let
$x_{1}=\frac{l_{0}(g_{1}^{n_{1}})}{n_{1}}=\frac{L_{c}(g_{1}^{n_{1}})}{n_{1}}$
and define $l_{1}(g)=l_{b}(g;\\{(g_{1},x_{1})\\})$. By homogeneity,
$l_{h}(g_{1})\leq x_{1}$, so by maximality of $l_{b}(g;\\{(g_{1},x_{1})\\})$,
$l_{h}(g)\leq l_{1}(g)$ for all $g\in\langle\alpha,\beta\rangle$.

Recall that we have an algorithm (described in 3.5) giving (for
$g\in\langle\alpha,\beta\rangle$) an upper bound
$L_{b}(g;\\{(g_{1},x_{1})\\})$ for $l_{b}(g;\\{(g_{1},x_{1})\\})$. Define
$L_{1}(g)=L_{b}(g;\\{(g_{1},x_{1})\\})$ for $g\in\langle\alpha,\beta\rangle$.

Continuing in this fashion define

  * •

$x_{2}=\frac{L_{1}(g_{2}^{n})}{n_{2}}$ (which can be algorithmically
computed),

  * •

$l_{2}(g)=l_{b}(g;\\{(g_{1},x_{1}),(g_{2},x_{2})\\})$, and

  * •

$L_{2}=L_{b}(g;\\{(g_{1},x_{1}),(g_{2},x_{2})\\})$ (which is algorithmic).

As before, we have the bounds $l_{h}(g)\leq l_{2}(g)$ for all
$g\in\langle\alpha,\beta\rangle$.

Inductively, given $k<m$, $x_{i}\in\langle\alpha,\beta\rangle$ for $1\leq
i\leq k$, a function $l_{k}:\langle\alpha,\beta\rangle\to\mathbb{R}$, and an
algorithmically defined function
$L_{k}:\langle\alpha,\beta\rangle\to\mathbb{R}$, define

  * •

$x_{k+1}=\frac{L_{k}(g_{k+1}^{n_{k+1}})}{n_{k+1}}$ (which can be
algorithmically computed),

  * •

$l_{k+1}(g):=l_{b}(g;\\{(g_{1},x_{1}),(g_{2},x_{2}),\dots,(g_{k+1},n_{k+1})\\})$,
and

  * •

$L_{k+1}(g):=L_{b}(g;\\{(g_{1},x_{1}),(g_{2},x_{2}),\dots,(g_{k+1},n_{k+1})\\})$

The function
$L(g):=L_{m}(g)=L_{b}(g;\\{(g_{1},x_{1}),(g_{2},x_{2}),\dots,(g_{n},n_{m})\\})$
is the desired upper bound for $l_{h}$.

###  3.5. Algorithm for conjugacy-invariant pseudo-lengths

We now describe the algorithms giving $L_{c}(g)$ and $L_{b}(g;B)$, i.e. giving
upper bounds for $l_{c}(g)$ and $l_{b}(g;B)$. Recall that
$l_{c}(g)=l_{b}(g;\emptyset)$.

Let $l$ be a normalized, conjugacy-invariant pseudo-length $l(g)$, which may
also be assumed to satisfy a finite number of elementary bounds. We describe
an upper bound for $l(g)$ for a word $g=\xi_{1}\xi_{2}\dots\xi_{n}$
recursively in the length $n$ of the word. The key ingredient is the following
lemma bounding $l(g)$ in terms of bounds on shorter words.

######  Lemma 3.1.

Let $g=\xi_{1}\xi_{2}\dots\xi_{n}$ with $n>1$.

  1. (a)

$l(g)\leq 1+l(\xi_{2}\xi_{3}\dots\xi_{n})$

  2. (b)

If $\xi_{k}=\xi_{1}^{-1}$, then $l(g)\leq
l(\xi_{2}\xi_{3}\dots\xi_{k-1})+l(\xi_{k+1}\xi_{k+2}\dots\xi_{n})$

###### Proof.

To see (a), observe that

$\displaystyle l(g)$ $\displaystyle=l(\xi_{1}\xi_{2}\dots\xi_{n})$
$\displaystyle\leq l(\xi_{1})+l(\xi_{2}\xi_{3}\dots\xi_{n}),$
$\displaystyle(\textrm{by the triangle inequality})$ $\displaystyle\leq
1+l(\xi_{2}\xi_{3}\dots\xi_{n}),$ $\displaystyle(\textrm{as $l$ is
normalized})$

as claimed.

Next, suppose $\xi_{k}=\xi_{1}^{-1}$. By the triangle inequality,

(1) $\displaystyle l(g)$ $\displaystyle\leq
l(\xi_{1}\xi_{2}\xi_{3}\dots\xi_{k-1}\xi_{k})+l(\xi_{k+1}\xi_{k+2}\dots\xi_{n})$
(2)
$\displaystyle=l(\xi_{1}(\xi_{2}\xi_{3}\dots\xi_{k-1})\xi_{1}^{-1})+l(\xi_{k+1}\xi_{k+2}\dots\xi_{n}).$

Further, by conjugacy invariance of $l$,

(3)
$l(\xi_{1}(\xi_{2}\xi_{3}\dots\xi_{k-1})\xi_{1}^{-1})=l(\xi_{2}\xi_{3}\dots\xi_{k-1}).$

Substituting (3) in (2), we get

$l(g)\leq l(\xi_{2}\xi_{3}\dots\xi_{k-1})+l(\xi_{k+1}\xi_{k+2}\dots\xi_{n}),$

showing (b). ∎

The algorithms are based on Lemma 3.1. Elementary bounds $l(g_{i})\leq x_{i}$,
$1\leq i\leq m$ are specified by a map $L_{0}:D\to\mathbb{R}$ with
$D\subset\langle\alpha,\beta\rangle=\\{g_{1},\dots,g_{m}\\}$ and
$L_{0}(g_{i})=x_{i}$. If we have no such bounds, i.e. we are computing
$l_{c}$, we initially take $D=\emptyset$ and $L_{0}$ as the empty map (however
the map is updated to avoid repeating computations).

For $g\in\langle\alpha,\beta\rangle$, the recursive algorithm shown in Figure
1 gives a bound $L(g)$ so that $l(g)\leq L(g)$ for any normalized, conjugacy-
invariant pseudo-length $l$ on $\langle\alpha,\beta\rangle$. We describe this
using sets in mathematical language, but this can be readily translated to
code using, for instance, list comprehensions.

Figure 1. Algorithm for bounding lengths • For
$g\in\langle\alpha,\beta\rangle$, compute $L(g)$ by – If $g=e$ is the empty
word, define $L(g):=0$. – If $g=\xi_{1}$ has exactly one letter, define
$L(g):=1$. – If $d\in D$, define $L(g)=L_{0}(g)$. – If
$g=\xi_{1}\xi_{2}\dots\xi_{n}$ has at least two letters (and $g\notin D$):
@itemiii let $\lambda_{0}=1+L(\xi_{2}\xi_{3}\dots\xi_{n})$ (computed
recursively). @itemiii for $2\leq k\leq n$, define
$\lambda_{k}=L(\xi_{2}\xi_{3}\dots\xi_{k-1})+L(\xi_{k+1}\xi_{k+2}\dots\xi_{n}).$
@itemiii let $\Lambda$ be the set $\Lambda=\\{\lambda_{k}:2\leq k\leq
n,\xi_{k}=\xi_{1}^{-1}\\}.$ @itemiii let
$x=\min(\\{\lambda_{0}\\}\cup\Lambda)$. @itemiii let $D:=D\cup\\{g\\}$ and
extend $L_{0}$ by defining $L_{0}(g)=x$. @itemiii define $L(g)=x$.

Furthermore, we can keep track of a labelled rooted tree of inequalities used
to compute $L(g)$, and hence bound $l(g)$. We give a schematic condensed
example of such a tree in Figure 2. Essentially such a tree (actually a
corresponding Algebraic Data Type) was used to generate the human readable
proof.

Figure 2. Proof tree of $l(\alpha\beta\alpha^{-1}\beta^{-1})\leq 1$ in a YAML-
like format • bound: $l(\alpha\beta\alpha^{-1}\beta^{-1})\leq 1$ • proof:
triangle-inequality – first-inequality: @itemiii bound: $l(\alpha)\leq 1$
@itemiii proof: length-is-normalized – second-inequality @itemiii bound:
$l(\beta\alpha^{-1}\beta^{-1})\leq 1$ @itemiii proof: conjugacy-invariance -
conjugated-by: $\beta$ - base-inequality: $\circ$ bound: $l(\alpha^{-1})\leq
1$. $\circ$ proof: length-is-normalized.

Observe that the function $L$ is integer valued, and can hence be computed
exactly. On using homogeneity we obtain rational bounds. These were stored as
double precision real numbers – we switched to arbitrary precision rational
numbers at one stage, but switched back for performance reasons during the
recursive computations (as these were involved in a large search). Note
however that it is easy (and efficient) to map a proof tree using doubles to
one using arbitrary precision rational numbers to ensure that there is no
error in rounding off. Indeed, as we discuss in 3.7, we have subsequently
implemented the mapping of proofs to exact rational bounds.

###  3.6. Bounding with a homogeneity pair sequence

We now describe how to modify the above algorithm given a homogeneity pair
sequence. This is following the approach of 3.4, but with one minor difference
as mentioned in Remark 3.6.1.

Suppose now that we are given a homogeneity pair sequence, i.e., a finite
sequence of pairs $(g_{i},n_{i}$), $1\leq i\leq m$. We initialize $L_{0}$ to
be the empty map, and compute $L(g_{1}^{n_{1}})$ using the main algorithm. We
let $x_{1}=L(g_{1}^{n_{1}})/n_{1}$ and update the map $L_{0}$ by setting
$L_{0}(g_{1})=x_{1}$.

Next we use the main algorithm to compute $L(g_{2}^{n_{2}})$, but with $L_{0}$
the map obtained at the end of the previous computation and after setting
$L_{0}(g_{1})=x_{1}$. Again let $x_{2}=L(g_{2}^{n_{2}})/n_{2}$ and update the
map $L_{0}$ by setting $L_{0}(g_{2})=x_{2}$. We proceed in this fashion to
obtain the numbers $x_{1}$, $x_{2}$, …, $x_{n}$, and an _updated_ map $L_{0}$.

Finally, for an elements $g\in\langle\alpha,\beta\rangle$, we define the
function $L(g)$ as the result of using the algorithm with the map $L_{0}$
obtained at the end of the above sequence of computations and updates.

######  Remark 3.6.1.

While the above algorithm is very similar to that described in 3.4, it gives
in general slightly worse bounds. This is because, for a fixed
$g_{0}\in\langle\alpha,\beta\rangle$, if $L(g_{0})$ is computed for a word
while computing, for example $x_{1}$ (which happens if $g_{0}$ is a subword of
$g_{1}^{n_{1}}$), we do not recompute $L(g_{0})$ when computing, for example
$x_{2}$. However we may get a smaller value (i.e., better bound) if we
recomputed $L(g_{0}$) as we have the additional elementary bound $L(x_{1})\leq
g_{1}$ (we get an improved bound if $g_{1}$ is a subword of $g_{0}$ and
$L(g_{1}^{n_{1}})<n_{1}L(g_{1})$). It is easy to avoid this by setting the map
$L_{0}$ when computing $x_{i}$ to be just the earlier elementary bounds, i.e.
set $D=\\{g_{j}:j<i\\}$ and $L_{0}(g_{j})=x_{j}$. However, this comes at a
cost in efficiency due to computations being repeated.

###  3.7. Choices and results

In generating the proofs, we used the family of words of the form
$\gamma_{k}=\alpha(\alpha\beta\alpha^{-1}\beta^{-1})^{k}$, with this family
chosen based on expert knowledge. From these, we constructed a homogeneity
sequence, depending on certain choices.

Namely, our homogeneity pair sequence was of the following form (with explicit
choices stated, which we have used in a script as mentioned below):

  * •

We choose and fix $N\geq 1$ (we take $N=20$).

  * •

Choose and fix a few values of $k$ (chosen with some experimentation), say
$k_{1}$, $k_{2}$, …, $k_{m}$ (we take $m=3$ with $k_{1}=1$, $k_{2}=2$ and
$k_{3}=6$).

  * •

We get a homogeneity pair sequence taking each element $\gamma_{k_{i}}$ with
each exponent between $1$ and $N$, namely

$(\gamma_{k_{1}},1),\dots,(\gamma_{k_{1}},N),(\gamma_{k_{2}},1),\dots,(\gamma_{k_{2}},N),\dots,(\gamma_{k_{m}},1),\dots,(\gamma_{k_{m}},N).$

  * •

The homogeneity pair sequence we use is the above sequence _followed by_ the
sequence

$(\alpha\beta\alpha^{-1}\beta^{-1},1),(\alpha\beta\alpha^{-1}\beta^{-1},2)\dots,(\alpha\beta\alpha^{-1}\beta^{-1},N)$

With the explicit choices $N=20$, $m=3$, $k_{1}=1$, $k_{2}=2$ and $k_{3}=6$,
we get the bound

$l_{h}(\alpha\beta\alpha^{-1}\beta^{-1})\leq 0.8098765432098762$

and a corresponding human readable proof.

Furthermore, we can map proofs to arbitrary precision rational bounds to avoid
rounding errors. Mapping the above proof gives the bound (with no rounding-off
error)

$l_{h}(\alpha\beta\alpha^{-1}\beta^{-1})\leq 328/405.$

We have created an _executable jar_ file to replicate generating this proof
(as well as mapping to a proof with arbitrary precision rational bounds). This
is available online at http://math.iisc.ac.in/~gadgil/PolyProof.html (with
instructions on running it), along with sample output (slightly reformatted).
On the systems we used (a desktop and a laptop with Core i7 processors) this
runs in under 10 seconds.444The full code is in the repository
https://github.com/siddhartha-gadgil/Superficial. The script is generated from
this source. The script uses the same algorithms we originally used, but with
modifications to be more robust in memory usage and to avoid concurrency (as
the concurrency we implemented leads to non-determinacy, and occasionally to
race conditions). The proof generated by this script is a little longer than
the one originally posted ($173$ lines instead of $126$) but gives a slightly
better bound.

Values for $N$ and the indices $k_{i}$ were obtained by experimentation, and
the bounds are fairly robust when we vary choices.

######  Remark 3.7.1.

In generating the script we only used our knowledge that $k=6$ was useful
(though not crucial) while generating the original proof, and the only other
choices we tried were taking $N=10$, which also gives a bound below $1$, and
also taking $k$’s to be $1$, $2$ ,$3$ and $6$, which only marginally improved
the bound.

The choice of the family $\gamma_{k}$ was based on mathematical considerations
related to [1], and this was the only expert guidance. We next discuss whether
finding the proof was plausible using general principles in place of expert
knowledge.

###  3.8. Auxiliary choices without expert knowledge?

As we have seen, the only expert guidance was the “natural family of group
elements $\gamma_{k}$”. We sketch a series of general considerations (some
using basic group theory) that could plausibly have led to the same family.

  * •

A natural measure of _usefulness_ of a homogeneity pair $(g,n)$ is the ratio
$\rho(g,n)=\frac{l_{c}(g)}{l_{c}(g^{n})/n}$, as this is an upper bound on the
ratio $l_{c}(h)/l_{b}(h;\\{(g,n)\\})$ for $h\in\langle\alpha,\beta\rangle$,
i.e., the maximum possible improvement in bounds (a value of $1$ means no gain
from using homogeneity).

  * •

Rather than looking for individual useful elements, we look for _families_
$\gamma_{k}$ of useful elements, choosing between families by small scale
sampling.

  * •

We look for _natural_ families in the sense of having a simple description in
terms of the group operations. The simplest families in a group are those of
the form $a^{k}$ for fixed $a\in\langle\alpha,\beta\rangle$ and the next
simplest are those of the form $ab^{k}$ for fixed
$a,b\in\langle\alpha,\beta\rangle$. The family we considered is of the second
form. (As $b^{k}a$ is conjugate to $a^{-1}b^{k}$, families of the form
$b^{k}a$ are equivalent to those we considered.)

  * •

We first consider simple families, i.e., with simple words for $a$ and $b$,
while using symmetries of the problem to reduce choices.

Here the symmetries are: transposing the generators $\alpha$ and $\beta$,
transposing one or both generators with their inverses, and cyclic
permutations of words. Further, one needs to only consider _reduced_ words,
i.e., those without a cancelling pair. Up to all these symmetries, there are
only $6$ words with length $4$, $2$ each with lengths $3$ and $2$ and a single
word with length $1$. Even allowing for not all symmetries being exploited (as
they do depend on some expert knowledge) and allowing for different choices
for the word $a$, the number of families of complexity comparable to the one
we considered is modest.

Furthermore, if $b$ is a word of length at most $4$ which is not equivalent to
$\alpha\beta\alpha^{-1}\beta^{-1}$, then $l_{h}(b)=l_{c}(b)$, which in
particular implies that $\rho(ab^{k},n)\approx 1$ for large $k$ and $n$. Thus
the families with other values of $b$ can be ruled out as not useful with
limited experimentation.

Thus, if one searches through natural families, with simpler ones considered
first and symmetries exploited to avoid duplication, and assesses each family
rapidly by measuring improvements in relevant bounds after small scale
sampling, one is likely to arrive at the family we considered (or an
equivalent one) in a reasonable amount of time.

##  4\. Concluding remarks

If we view applications of the axioms as _moves_ , the computer proof helped
in identifying _composite moves_ that could be applied _recursively_ for words
in appropriate families. These were abstracted and generalized to give the
core lemma. One can hope that in other situations as well computer generated
proofs targeting key examples give hints about useful composite moves, and
especially those that can be used iteratively.

The principal difficulty in finding computer proofs often lies in choosing the
useful moves among those that increase complexity, which in our case are
applications of homogeneity. In this work, we primarily based ourselves on
mathematical considerations, partly because the auxiliary choices were
identified even before we started programming, and partly because of the fast
pace555the proof was posted less than two days after we began writing code,
and the main question answered less than a day after that.. However, we have
attempted to justify in Section 3.8 that it is plausible that experimentation
and general considerations could have led to similar results, with the use of
one heuristic – one should search for _natural families_ of useful moves.

We used modest computing resources (including time) and did not use search
heuristics. It is thus all the more likely that domain specific expertise
could have been replaced by (or combined with) the vast arsenal of well-known
heuristics for tree searches, such as Alpha-beta pruning, Markov Chain Monte
Carlo and various Machine learning techniques.

Fully automating the search in this and similar problems involves identifying
useful candidate families (beyond simply enumerating those with simple
descriptions). This is an interesting challenge, and it would be interesting
to explore various techniques for this. Computer scientists have developed
various techniques to find inputs trigger a bug (such as fuzzing) and
techniques to minimize such inputs (such as delta-debugging). Perhaps these
techniques are also useful for finding a human-understandable proof like the
one presented in the paper.

######  Acknowledgements.

I thank the referees and the editors for many valuable comments, which have
led to the paper being completely rewritten twice and much improved in the
process. It is also a pleasure to thank the rest of the PolyMath 14 team for
the collaboration of which the work described here is a part.

## References

  * [1] S. Gadgil, Watson–Crick pairing, the Heisenberg group and Milnor invariants, Journal of Mathematical Biology 59 (2009), 123–142.
  * [2] A. Khare and B. Rajaratnam, The Hoffmann-Jørgensen inequality in metric semigroups, Annals of Probability, 45 (2017), 4101–4111.
  * [3] A. Khare and B. Rajaratnam, The Khinchin–Kahane inequality and Banach space embeddings for metric groups, preprint, 2016.
  * [4] D.H.J. PolyMath, _Homogeneous length functions on Groups_ , Algebra and Number Theory 12 (2018), 1773-1786.