# A Computational Analysis of Vagueness in Revisions of Instructional Texts

Alok Debnath
Kohli Center for Intelligent Systems
International Institute of Information
Technology, Hyderabad
<EMAIL_ADDRESS>
&Michael Roth
Institute for Natural Language Processing
University of Stuttgart
<EMAIL_ADDRESS>

###### Abstract

_WikiHow_ is an open-domain repository of instructional articles for a variety
of tasks, which can be revised by users. In this paper, we extract pairwise
versions of an instruction before and after a revision was made. Starting from
a noisy dataset of revision histories, we specifically extract and analyze
edits that involve cases of vagueness in instructions. We further investigate
the ability of a neural model to distinguish between two versions of an
instruction in our data by adopting a pairwise ranking task from previous work
and showing improvements over existing baselines.

##  1 Introduction

Instructional texts aim to describe the actions necessary to accomplish a task
or goal, in as clear and concise a manner as possible.
WikiHow111https://www.wikihow.com/ is an extensive compendium of instructional
guides for various topics and domains. Any user may edit the articles, and
WikiHow collates these revision histories. The edit history of such informal
instructional articles is a source of user-generated data that can help
identify possible reasons and necessities for editing. _wikiHowToImprove_
(Anthonio et al., 2020) is a dataset that compiles revision histories for the
analysis of linguistic phenomena that occur in edits of instructional texts,
ranging from the correction of typos and grammatical errors to the
clarification of ambiguity and vagueness.

Original Sentence |  Revised Sentence
---|---
3.60cmThen, make the floor and walls of your house. |  3.60cmThen, design the floor and walls of your house.
3.58cmWhen you go to the Hogwarts park… |  3.58cmWhen you visit the Hogwarts park…
3.58cmGet a flexible single cord. |  3.58cmPurchase a flexible single cord.
Table 1: Examples of vague instructions and their more clarified versions from
the _wikiHowToImprove_ Dataset

In this paper, we focus on cases of lexical vagueness, defined as “lexeme[s]
with a single but nonspecific meaning” Tuggy (1993), which can potentially
cause misunderstandings in instructional texts. Specifically, we study
vagueness based on the change in the main verb in the original and revised
version of an instruction. We say that an instruction was vague if, upon
revision, the revised main verb is contextually more specific than the
original version. Some examples of vague and clarified instructions are
provided in Table 1. As indicated by the examples, the revised verb is usually
more specific in that it provides additional information on how or why an
action needs to be taken.

The classification of vague and clarified instructions is a first step towards
automatic text editing for clarification based on linguistic criteria such as
ambiguity and vagueness at a sentence level. Existing tools for text editing
focus on text simplification and fact editing (Malmi et al., 2019), while
others are designed for grammatical error correction (Xie et al., 2018). Our
work acts as the first step towards automated editing based on linguistic
criteria by identifying vague instructions and differentiating them from
“clarified” ones. Our use of the _wikiHowToImprove_ corpus also utilizes a
resource of edit pairs, therefore introducing a new dataset for the linguistic
study of vagueness as well as exploring the general versatility of such
corpora.

Our contributions are to create a dataset of vague and clarified instructions,
provide an analysis based on semantic frames, and demonstrate the first
results of a neural model’s ability to distinguish the two versions. We create
and analyze the dataset by extracting relevant instances from
_wikiHowToImprove_ , using POS tags, dependency features, and edit distance as
constraints, as well as FrameNet frames as features (Section 3). We then
devise a pairwise ranking task, where we train and evaluate different neural
models and analyze their performance based on frame relations and differences
in distributional word representations (Section 4).

##  2 Related Work

Our paper focuses on revisions in wikiHow for a specific linguistic
phenomenon, namely vagueness. The motivation to use revision histories as
corpora for NLP tasks was introduced by Ferschke et al. (2013). The task of
defining and categorizing edit intentions has been explored well for the
Wikipedia edits corpus (Yang et al., 2016, 2017). More recently, Anthonio et
al. (2020) performed a similar categorization on the revisions in WikiHow.

Traditional computational analyses of vague statements have been based on
logical representations (DeVault and Stone, 2004; Tang, 2008). In contrast,
our focus is on vagueness in terms of lexical changes in revisions, which is
more similar to previous analyses that considered the context-dependent
resolution of vague expressions such as colour references (Meo et al., 2014).
Other computational approaches to vagueness include, the detection of vague
sense definitions in ontological resources (Alexopoulos and Pavlopoulos, 2014)
and website privacy policies (Lebanoff and Liu, 2018) as well as the
verification of historical documents (Vertan, 2019).

Our approach to identifying and classifying vagueness is analyzed using
FrameNet frames which provide specialized relations among conceptual
categories, in a manner similar to recent advances in neural models that use
sentence-level information to perform hyponymy–hypernymy classification.
Roller et al. (2018) analyzes lexico-syntactic pattern-based instances of
word-specific hypernymy-hyponymy constructions. Snow et al. (2004) explores
the extraction of predefined patterns for hypernyms and hyponyms in the same
sentence, while Shwartz et al. (2016) incorporates distributional methods for
their classification using sentence-level features.

##  3 Data Creation, Preprocessing, and Analysis

_WikiHow_ articles mostly contain instructions, but also include descriptions,
explanations, and other non-instructional sentences that provide additional
context. The _wikiHowToImprove_ corpus Anthonio et al. (2020) is an unfiltered
corpus of revision histories. Therefore, we first need to extract those
revisions where the original and revised versions are both instructional
sentences, which can be done based on syntactic properties (§3.1). We then use
a FrameNet parser to determine the frames (and their relationships) evoked by
the root verb in the original and revised version of an instruction (§3.2).

The final extracted data consists of only those revisions where the root verb
has been modified to be more specific to the sentence. This extracted corpus
consists of 41,615 sentences.

###  3.1 Data Extraction and Cleaning

_wikiHowToImprove_ is a noisy source of data with misspellings, non-standard
abbreviations, grammatical errors, emoticons, etc. In order to use the data
for our task, we first perform some cleaning and preprocessing.

We filter the typos and misspellings in the dataset by comparing all the
vocabulary words to words in the English dictionary using the Enchant python
API222https://pyenchant.github.io/. After filtering the typos, we POS tag and
dependency parse the data using the Stanza
library333https://stanfordnlp.github.io/stanza/ (Qi et al., 2020). We discard
all sentence pairs where the sentences are shorter than four or longer than 50
words.

We then create a sub-corpus of instructional sentneces by extracting those
edit pairs in which both the original and revised version of a sentence
fulfill at least one of the following criteria:

  * •

imperative form—the root verb has no nominal subject (e.g. “Please finish the
task”);

  * •

instructional indicative form—the nominal subject of the root verb is ‘you,’
‘it’ or ‘one’ (e.g. “You should finish the task”);

  * •

passive form with ‘let’—the sentence is in passive voice, and the root verb is
‘let’ (e.g. “Let the paper be put on the table.”).

Finally, we retain only those sentence pairs whose character edit distance is
smaller than 10. This filter was added after empirical tests to accommodate
changes in the verb form and syntactic frame while ensuring that there are
little to no additional edits (often just vandalism or spam).

###  3.2 Verb Frame Analysis

We perform an analysis of verb frame relations from this extracted corpus
using the FrameNet hierarchy (Baker et al., 1998). In order to identify evoked
frames from the data, we use the INCEpTION Project’s neural _FrameNet Tools_
parser444https://github.com/inception-project/framenet-tools (Klie et al.,
2018; Markard and Klie, 2020). FrameNet Tools identifies the frame-evoking
elements, the evoked frames, and the context elements’ roles in these frame
for a given sentence. In this work, we ignore role assignments and only
consider predictions of evoked frames, which we found to be generally reliable
in our data.555Although automatic frame identification is noisy, the tools
used here are implementations of the unimodal model presented in Botschen et
al. (2018), which achieves a high accuracy of over 88%.

We extract the frame of the root verb in the original and revised sentences.
For each pair, we identify the frame relation, if any, using the NLTK FrameNet
API666http://www.nltk.org/howto/framenet.html(Schneider and Wooters, 2017). We
found that most edits could be categorized into one of the following frame
relations between the frames evoked by the original and revised verb frames:

  1. 1.

Subframe-of: The original frame refers to a complex scenario that consists of
several individual states, one of which is the revised frame. (e.g.
Traversing$\rightarrow$Arriving: “ _Go_ to the thumbs up log.” is revised to “
_Visit_ the thumbs up log.”)

  2. 2.

Inherits-from: The frame of the revised verb elaborates on the frame evoked by
the original verb (e.g., Deciding$\rightarrow$Choosing: “ _Determine_ the card
you want to buy” is revised to “ _Choose_ which card you want to buy.”)

  3. 3.

Uses: The frame of the revised verb uses or weakly inherits properties of the
original verb frame (e.g., Perception_active$\rightarrow$Scrutiny: “ _Look_
for the best fit for your taste” is revised to “ _Search_ for the best fit for
your taste.”).

We also find cases of contextually relevant clarifications for phrasal verbs,
such as “ _Make_ your bed” vs. “ _Fix_ your bed…” which are not covered in
FrameNet. Further, there are cases in which the FrameNet Tools parser did not
identify the main verb or could not assign a frame. For instance, the verb
_compel_ as in “you may feel _compelled_ …” is not in FrameNet. We categorize
these instances, which are fewer in number than the other categories, under a
single Other category and leave further inspection to future work. A
distribution of instances over categories is shown in Table 2. Apart from
instances from the ‘Other’ category, we indeed found the main verbs in the
revised versions of a sentence to be more specific than in the original
versions.

Relation | Total | Train | Test | Val
---|---|---|---|---
Usage | 15,243 | 11,084 | 2,194 | 1,965
Inheritance | 13,166 | 9,179 | 2,008 | 1,793
Subframe | 9,481 | 6,835 | 1,720 | 926
Other | 3,925 | 2,833 | 649 | 443
Total | 41,615 | 30,044 | 6,237 | 5,334
Table 2: Number of sentences in the extracted dataset and distribution of
FrameNet relations between original and revised verbs. We also show the
distribution of train, test and validation for each frame relation.

##  4 Pairwise Ranking Experiments

In this section, we investigate if a neural model can distinguish between the
original and revised version of the same instruction. We describe a neural
architecture that uses a joint representation designed for comparing two
versions of a sentence before predicting an output. We compare our results to
a standard BiLSTM-Attention model used in previous work (Anthonio et al.,
2020).

###  4.1 System and Training Details

The initial components of our system are two BiLSTM modules, LSTM1A and
LSTM1B, that each takes one version of a sentence as input. The individual
BiLSTMs are followed by a joint layer LSTMAB and an additional layer of BiLSTM
modules, LSTM2A and LSTM2B, that re-encode the sentence based on the joint
representations. The final layer is trained to predict for each sentence,
whether it is the original or revised version, labeling them $0$ or $1$,
respectively.

In practice, we first encode versions $A$ and $B$ of an instruction using
FastText embeddings or BERT. The embedded sentences $S_{A}$ and $S_{B}$ are
then passed through LSTM1A and LSTM1B one (sub-word) token at a time. The
hidden layers $\textbf{h}_{1A}$ and $\textbf{h}_{1B}$ are then concatenated
and passed through LSTMAB, whose output $\textbf{h}_{AB}$ is then concatenated
again with the original hidden states to re-encode each sentence version in
LSTM2A and LSTM2B. Lastly a classification layer, trained using a cross-
entropy objective, transforms the final representations $\textbf{h}_{2A}$ and
$\textbf{h}_{2B}$ into a real-valued output score using self-attention, which
is normalized by softmax and rounded to $\\{0,1\\}$. The equations below give
a simplified summary of our implementation.777We will make the code available
upon publication.

$\displaystyle\textbf{h}_{1A}$ $\displaystyle=$
$\displaystyle\text{LSTM}_{1A}(S_{A})$ (1) $\displaystyle\textbf{h}_{1B}$
$\displaystyle=$ $\displaystyle\text{LSTM}_{1B}(S_{B})$ (2)
$\displaystyle\textbf{h}_{AB}$ $\displaystyle=$
$\displaystyle\text{LSTM}_{AB}(\textbf{h}_{1A}\cdot\textbf{h}_{1B})$ (3)
$\displaystyle\textbf{h}_{2A}$ $\displaystyle=$
$\displaystyle\text{LSTM}_{2A}(\textbf{h}_{AB}\cdot\textbf{h}_{1A})$ (4)
$\displaystyle\textbf{h}_{2B}$ $\displaystyle=$
$\displaystyle\text{LSTM}_{2B}(\textbf{h}_{AB}\cdot\textbf{h}_{1B})$ (5)
$\displaystyle l_{A}$ $\displaystyle=$
$\displaystyle\left[\frac{\exp(\textbf{w}^{\top}\textbf{h}_{2A})}{\exp(\textbf{w}^{\top}\textbf{h}_{2A})+\exp(\textbf{w}^{\top}\textbf{h}_{2B})}\right]$
(6) $\displaystyle l_{B}$ $\displaystyle=$
$\displaystyle\left[\frac{\exp(\textbf{w}^{\top}\textbf{h}_{2B})}{\exp(\textbf{w}^{\top}\textbf{h}_{2A})+\exp(\textbf{w}^{\top}\textbf{h}_{2B})}\right]$
(7)

#### Training Details

We experiment with both FastText (Grave et al., 2018) and BERT (Devlin et al.,
2019), using representations with a dimensionality of 300 components. The
BiLSTMs modules $\text{LSTM}_{1A},\text{LSTM}_{1B},\text{LSTM}_{2A}$ and
$\text{LSTM}_{2B}$ each comprise one hidden layer with 256 components, whereas
the joint $\text{LSTM}_{AB}$ comprises one layer with 512 components. We train
for 5 epochs with a batch size of 32 and a learning rate of $10^{-5}$. The
model is trained with a dropout of 0.2 for regularization. No dropout is
applied to any BiLSTM layers or the self-attention layer.

For training, development, and testing, we split our data according to the
existing partition given in
_wikiHowToImprove_.888https://github.com/irshadbhat/wikiHowToImprove The
resulting split consists of 30,044 sentence revision pairs in the training
set, 6,237 pairs in the test set, and 5,334 pairs in the validation set.

###  4.2 Results and Discussion

Model Description | Dataset | Accuracy
---|---|---
Anthonio et al. (2020) | Entire | 74.50%
Anthonio et al. (2020) | Filtered | 64.08%
Our Model + FastText | Filtered | 71.16%
Our Model + BERT | Filtered | 78.40%
Table 3: Results of the pairwise ranking task, on the full wikiHowToImprove
dataset (Entire) and our subset of instructional sentences (Filtered).

Table 3 shows the results of the pairwise ranking task. We find that our
proposed model with BERT embeddings is the most accurate model for this task
by a margin of about 7%. We compare our results against the baseline provided
by Anthonio et al. (2020), which also makes use of ranking and a BiLSTM
architecture. In contrast to our model, their baseline is a simple BiLSTM-
Attention classification model using FastText embeddings. It does not use an
intermediate joint representation to compare representations of two versions
of an instruction. The baseline model has the advantage of being trained on
individual sentences, but the increase in model accuracy for training sentence
pairs by sharing context highlights the efficacy of the training regime.

Their model provides an accuracy of about 64.08% when trained and evaluated on
the filtered corpus. Our model with FastText embeddings achieves an accuracy
of 71.16% ($+7.08\%$), which shows the relative importance of the joint
representation.

Frame Relation | Sentence Pair
---|---
(#errors / total) |
Usage |  Make a comic in Flash
(503 / 1,965) |  Create a comic in Flash
Inheritance |  Check the “made in” label
(352 / 1,793) |  Inspect the “made in” label
Subframe |  Let your hair dry
(137 / 926) |  Allow your hair to dry
Other | Next, try to sneak out…
(160 / 443) | Next, attempt to sneak out…
Table 4: Some examples of sentences which our BERT-based classifier could not
distinguish between the original (top) and revised (bottom) versions. We find
that confusable verbs (marked in bold) are mostly synonymous. The error and
total counts from the validation set are provided in parenthesis for each
relation type.

#### Discussion

We find that version pairs that involve a subframe relation are the easiest to
distinguish across our model using both FastText and BERT, while pairs
involving the usage relation are most often confused. The model using BERT
embeddings performs better than the FastText-based model on revisions that do
not involve any frame-to-frame relations according to FrameNet (referred to as
‘other’ in Table 2).

In Table 4, we provide examples where the model failed using both FastText and
BERT. We observe that the models fail to correctly distinguish between
sentences when the main verbs are synonymous. The embeddings of the most
commonly confused verb pairs, which include $\langle$allow, permit$\rangle$,
$\langle$choose, decide$\rangle$ and $\langle$create, make$\rangle$, have a
cosine similarity of $0.8$ or higher, while the average cosine similarity
between the representation of verb pairs is $0.47$. This insight shows that
embeddings by themselves might be insufficient for this classification task.
In future work, we will explore additional features such as indicator features
derived from the discourse context (e.g., the position of a sentence) and from
the FrameNet resource (e.g., properties of the frames evoked in a sentence).

##  5 Conclusion

In this paper, we extracted a corpus of clarifications of instructions from
the _wikiHowToImprove_ corpus. We described a methodology for extracting
version pairs of a sentence that are both instructional. We then identified
cases in which a revision has clarified a vague instruction by analyzing the
relationship between the frames evoked by the ‘original’ verb and the
‘revised’ verb.

In our experiments, we adopted a simple pairwise ranking task, in the same
vein as performed by Anthonio et al. (2020) on the entire _wikiHowToImprove_
dataset. We extended a simple BiLSTM architecture with a joint component and
explored different embeddings methods, observing that both modifications lead
to improvements over baselines presented in previous work.

We hope that our methodology of extracting linguistically interesting cases of
revisions from a noisy dataset can be extended to more phenomena and other
corpora in future work. This direction has the potential of paving the way for
developing automated revision and editing methods beyond typo, style, and
grammar correction.

## Acknowledgements

The research presented in this paper was funded by the DFG Emmy Noether
program (RO 4848/2-1).

## References

  * Alexopoulos and Pavlopoulos (2014) Panos Alexopoulos and John Pavlopoulos. 2014.  A vague sense classifier for detecting vague definitions in ontologies.  In _Proceedings of the 14th Conference of the European Chapter of the Association for Computational Linguistics, volume 2: Short Papers_ , pages 33–37.
  * Anthonio et al. (2020) Talita Anthonio, Irshad Bhat, and Michael Roth. 2020.  wikiHowToImprove: A resource and analyses on edits in instructional texts.  In _Proceedings of The 12th Language Resources and Evaluation Conference_ , pages 5721–5729.
  * Baker et al. (1998) Collin F Baker, Charles J Fillmore, and John B Lowe. 1998.  The Berkeley FrameNet project.  In _36th Annual Meeting of the Association for Computational Linguistics and 17th International Conference on Computational Linguistics, Volume 1_ , pages 86–90.
  * Botschen et al. (2018) Teresa Botschen, Iryna Gurevych, Jan-Christoph Klie, Hatem Mousselly-Sergieh, and Stefan Roth. 2018.  Multimodal frame identification with multilingual evaluation.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)_ , pages 1481–1491, New Orleans, Louisiana. Association for Computational Linguistics.
  * DeVault and Stone (2004) David DeVault and Matthew Stone. 2004.  Interpreting vague utterances in context.  In _COLING 2004: Proceedings of the 20th International Conference on Computational Linguistics_ , pages 1247–1253.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  Bert: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4171–4186.
  * Ferschke et al. (2013) Oliver Ferschke, Johannes Daxenberger, and Iryna Gurevych. 2013.  A survey of NLP methods and resources for analyzing the collaborative writing process in Wikipedia.  In _The People’s Web Meets NLP_ , pages 121–160. Springer.
  * Grave et al. (2018) Edouard Grave, Piotr Bojanowski, Prakhar Gupta, Armand Joulin, and Tomas Mikolov. 2018.  Learning word vectors for 157 languages.  In _Proceedings of the International Conference on Language Resources and Evaluation (LREC 2018)_.
  * Klie et al. (2018) Jan-Christoph Klie, Michael Bugert, Beto Boullosa, Richard Eckart de Castilho, and Iryna Gurevych. 2018.  The INCEpTION platform: Machine-assisted and knowledge-oriented interactive annotation.  In _Proceedings of the 27th International Conference on Computational Linguistics: System Demonstrations_ , pages 5–9. Association for Computational Linguistics.
  * Lebanoff and Liu (2018) Logan Lebanoff and Fei Liu. 2018.  Automatic detection of vague words and sentences in privacy policies.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 3508–3517.
  * Malmi et al. (2019) Eric Malmi, Sebastian Krause, Sascha Rothe, Daniil Mirylenka, and Aliaksei Severyn. 2019.  Encode, tag, realize: High-precision text editing.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 5057–5068.
  * Markard and Klie (2020) André Markard and Jan-Christoph Klie. 2020.  FrameNet Tools: A python library to work with FrameNet.
  * Meo et al. (2014) Timothy Meo, Brian McMahan, and Matthew Stone. 2014.  Generating and resolving vague color references.  In _Proceedings of the 18th Workshop on the Semantics and Pragmatics of Dialogue (SemDial)_ , pages 107–115.
  * Qi et al. (2020) Peng Qi, Yuhao Zhang, Yuhui Zhang, Jason Bolton, and Christopher D. Manning. 2020\.  Stanza: A Python natural language processing toolkit for many human languages.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics: System Demonstrations_.
  * Roller et al. (2018) Stephen Roller, Douwe Kiela, and Maximilian Nickel. 2018.  Hearst patterns revisited: Automatic hypernym detection from large text corpora.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 358–363.
  * Schneider and Wooters (2017) Nathan Schneider and Chuck Wooters. 2017.  The NLTK FrameNet API: Designing for discoverability with a rich linguistic resource.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , pages 1–6.
  * Shwartz et al. (2016) Vered Shwartz, Yoav Goldberg, and Ido Dagan. 2016.  Improving hypernymy detection with an integrated path-based and distributional method.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 2389–2398.
  * Snow et al. (2004) Rion Snow, Daniel Jurafsky, and Andrew Ng. 2004.  Learning syntactic patterns for automatic hypernym discovery.  _Advances in neural information processing systems_ , 17:1297–1304.
  * Tang (2008) Yongchuan Tang. 2008.  A collective decision model involving vague concepts and linguistic expressions.  _IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics)_ , 38(2):421–428.
  * Tuggy (1993) David Tuggy. 1993.  Ambiguity, polysemy, and vagueness.  _Cognitive linguistics_ , 4(3):273–290.
  * Vertan (2019) Cristina Vertan. 2019.  Modelling linguistic vagueness and uncertainty in historical texts.  In _Proceedings of the Workshop on Language Technology for Digital Historical Archives_ , pages 34–38.
  * Xie et al. (2018) Ziang Xie, Guillaume Genthial, Stanley Xie, Andrew Y Ng, and Dan Jurafsky. 2018\.  Noising and denoising natural language: Diverse backtranslation for grammar correction.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)_ , pages 619–628.
  * Yang et al. (2016) Diyi Yang, Aaron Halfaker, Robert Kraut, and Eduard Hovy. 2016.  Edit categories and editor role identification in Wikipedia.  In _Proceedings of the Tenth International Conference on Language Resources and Evaluation (LREC’16)_ , pages 1295–1299.
  * Yang et al. (2017) Diyi Yang, Aaron Halfaker, Robert Kraut, and Eduard Hovy. 2017.  Identifying semantic edit intentions from revisions in Wikipedia.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_ , pages 2000–2010.


# Offsets of a regular trifolium

Thierry Dana-Picard  Jerusalem College of Technology
Havaad Haleumi Street 21, 9116011 Jerusalem, Israel<EMAIL_ADDRESS>Zoltán
Kovács  Private Pädagogische Hochschule der Diözese Linz
Salesianumweg 3, 4020 Linz, Austria<EMAIL_ADDRESS>
###### Abstract

The non-uniqueness of a rational parametrization of a rational plane curve may
influence the process of computing envelopes of 1-parameter families of plane
curves. We study envelopes of family of circles centred on a regular trifolium
and its offsets, paying attention to different parametrizations. We use
implicitization both to show that two rational parametrizations of a curve are
equivalent, and to determine an implicit equation for the envelope under
study. The derivation of an implicit equation of an offset follows another
path, leading to new developments of the package GeoGebra Discovery. As an
immediate symbolic result, we obtain that in the general case the offset curve
of a regular trifolium is an algebraic curve of degree 14. We illustrate this
fact by providing a GeoGebra applet that computes such curves automatically
and visualizes them in a web browser.

###### keywords:

Rational parametrization, implicit curves, regular trifolium, offset,
GeoGebra, automated deduction

###### 1991 Mathematics Subject Classification:

Primary 53A04; Secondary 53-08

##  1\. Envelopes and offsets

Let $\mathcal{C}_{t}$ be a family of plane curves, parameterized by the real
$t$, given by the equation $F(x,y,t)=0$.

######  Definition 1 (_Impredicative_ ; [13]).

A plane curve $\mathcal{E}$ is called an _envelope_ of the family
$\\{\mathcal{C}_{k}\\}$ if the following properties hold:

  1. (i)

every curve in the family $\\{\mathcal{C}_{t}\\}$ is tangent to $\mathcal{E}$;

  2. (ii)

to every point $M$ on $\mathcal{E}$ is associated a value $t(M)$ of the
parameter $t$, such that $\mathcal{C}_{t}$ is tangent to $\mathcal{E}$ at the
point $M$;

  3. (iii)

The function $t(M)$ is non-constant on every arc of $\mathcal{E}$.

Two other definitions exist, also mentioned by [13]. One of them reads as
follows:

######  Definition 2 (_Synthetic_ ; [13]).

The envelope of the given family of curves is the set of limit points of
intersections of nearby curves $C_{t}$.

This definition is somehow problematic, as it would request the definition of
a topological set of curves, in order to have a reasonable definition of a
limit. Nevertheless, such a point of view has been used for a simple case by
[10].

The most used and usable definition is called _analytic_ by [13]; note that
[2], (sections 9.6.7 and 14.6.1) gives this one only. It has been derived form
the limit definition as theorem by [10].

######  Definition 3 (_Analytic_ ; [13]).

Let $C_{t}$ be a 1-parameter family of curves given by an equation
$F(x,y,t)=0$. The envelope of the family $\\{C_{t}\\}$ is the set of all
points $(x,y)$ such that there is a $t$ verifying the system of equations

$\begin{cases}F(x,y,t)=0,\\\ \frac{\partial F(x,y,t)}{\partial
t}=0.\end{cases}$ (1)

Following a Wikipedia
page111http://en.wikipedia.org/wiki/Envelope_(mathematics), [3] reports on a
$4^{\textrm{th}}$ definition of an envelope, namely: the envelope is the curve
that bounds the planar region described by the points belonging to the curves
in the family. In the case of our study, this is the _offset_ of the trifolium
at distance 1, as coined by [16], page 10. Actually, the first three
definitions mentioned above are equivalent, but the last one is not equivalent
to them. There exist examples where envelope and offset are identical, such as
in [10] and [16], but other examples enlighten the difference; see [7]. The
family studied in this paper is an example with new properties. They are
studied in section 4.

Note that the difference between envelope and offset is of the utmost
importance for industrial applications, such as the determination of safety
zones in industrial plants and entertainment parks. This issue is evoked in
[7].

##  2\. A regular trifolium: different presentations

We study various constructions on the basis of a regular trifolium (called
also regular _trefoil_). We recall the basic definitions, referring to [11],
where other constructions are also proposed.

######  Definition 4.

A _regular trifolium_ is a plane algebraic curve, given by the implicit
equation

$\left(x^{2}+y^{2}\right)^{2}=ax\left(x^{2}-3y^{2}\right)$ (2)

where $a$ is a positive real parameter

The parameter $a$ influences the _size_ of the trifolium, not its shape. Two
examples are shown in Figure 1, obtained using GeoGebra, a Dynamic Geometry
System (freely downloadable from http://geogebra.org). An important reason for
using this software is that it enables dynamical mouse-driven experiments.
Animation can be obtained with a CAS also, requiring some programming. The
differences between the two kinds of animation are discussed in [7].

(a) $a=1$ (b) $a=2$

Figure 1. Two examples of a regular trifolium

A plot can be obtained also using an implicitplot command of a Computer
Algebra System. WLOG, we will work in the case where $a=1$.

A more dynamical definition is as follows:

######  Definition 5.

A regular trifolium is the trajectory of the second intersection point between
a line and a circle turning around one of their common points in the same
direction, and the circle turning four times as fast as the line.

We will use this definition in order to derive a rational parametrization of
the regular trifolium, whence showing that this curve is a rational curve.

Consider the circle $C$ through the origin and whose center has coordinates
$(1/2,0)$. Its implicit equation is $(x-1/2)^{2}+y^{2}=1/4$. A general
rotation matrix about the origin is The rotated circle $C_{s}$ is thus given
by the equation

$\left(x\cos s+y\sin s-\frac{1}{2}\right)^{2}+(y\cos s-x\sin
s)^{2}=\frac{1}{4}.$ (3)

Now consider the line $L:y=x$. Rotating the line at a speed one fourth of the
rotation speed of the circle, we have a line $L_{s}$ whose equation is

$\cos\frac{s}{4}x+y\sin\frac{s}{4}=0.$ (4)

The circle $C_{s}$ and the line $L_{s}$ intersect at two points, the origin
and a second point whose coordinates are given as follows (for the sake of
simplicity, we substitute $t=s/4$):

$\begin{cases}x(t)=4\sin^{4}t-3\sin^{2}t,\\\ y(t)=-\sin t\cos
t\left(4\sin^{2}t-3\right).\end{cases}$ (5)

Using this parametrization, we obtain Figure 2; an experimental checking using
a DGS or a CAS shows that this plot is identical to Figure 1a.

Figure 2. Geometric construction of a regular trifolium

This identity may be checked by substitution of the two expressions for $x(t)$
and $y(t)$ into Equation (2). Note that the parametrization (5) is not
rational. In order to have benefit of Theorem 4.7 in [16], we need a rational
presentation.

[12] proposes another trigonometric parametric presentation (we modify it in
order to be coherent with our previous presentations):

$\begin{cases}x=a\cos t+\cos 2t,\\\ y=a\sin t-\sin 2t.\end{cases}$ (6)

This parametrization shows that a regular trifolium is a special case of a
_hypotrochoid_. It can be verified, either experimentally with software or
using trigonometric manipulations, that for $a=1/2$, we obtain the same curve
studied earlier. A regular trifolium is a special case of trifolium, in which
the three leaves are isometric, two of them being obtained from the third one
by a rotation of angle $\frac{2\pi}{3}$ or $\frac{4\pi}{3}$ (see [6]).

The following result is well-known, we emphasize it because of its importance
for the subsequent sections. We will show two proofs.

######  Proposition 6.

A regular trifolium is a rational curve.

This proposition means that a regular trifolium has a rational
parametrization. It is well-known that such a parametrization, when it exists,
is not unique. We derive now two parametrizations of a regular trifolium. The
first one will be obtained when using the following Lemma.

######  Lemma 7.

A rational parametrization of the unit circle centred at the origin is as
follows:

$\begin{cases}x=\frac{1-t^{2}}{1+t^{2}},\\\ y=\frac{2t}{1+t^{2}}.\end{cases}$
(7)

###### Proof.

The proof is straightforward; we give it as a promo, because we will use the
same method later in a more complicated setting. Consider the unit circle
$\mathcal{U}$ centred at the origin and a line $\mathcal{L}$ through the point
$B(-1,0)$ (Figure 3).

Figure 3. Geometric construction for parameterizing the unit circle
$\mathcal{U}$

The tangent to $\mathcal{U}$ through $B$ is parallel to the $y$-axis, all
other lines through $B$ have a slope $t$ and intersect $\mathcal{U}$ at a
$2^{\textrm{nd}}$ point $B_{t}$. The coordinates of $B_{t}$ are the solutions
of the system of equations

$\begin{cases}x^{2}+y^{2}=1,\\\ y=t(x+1).\end{cases}$

The result is obtained by substitution. Note that this parametrization is
valid for every point but $B$. ∎

Following [16] (p. 90), we recall that a rational parametrization can be
stated by means of rational maps. Let $\mathcal{C}$ be a rational affine curve
over the field $\mathbb{K}$ and $P(t)\in\mathbb{R}(t)^{2}$ be a rational
parametrization of $\mathcal{C}$. This parametrization induces a rational map

$P:$ | $\mathbb{A}^{1}(\mathbb{K})$ | $\longrightarrow$ | $\mathcal{C}$
---|---|---|---
| $t$ | $\mapsto$ | $P(t)$

and $P(\mathbb{A}^{1}(\mathbb{K}))$ is a dense subset of $\mathcal{C}$ (dense
in the sense of Zariski topology). A trigonometric parametrization of the unit
circle centred at the origin is given by $P(u)=(\cos u,\sin
u),\;u\in\mathbb{R}$. On the one hand, this parametrization is a bijection
between the unit circle and every interval $[2k\pi,2(k+1)\pi)$. On the other
hand, Equations (7) define a bijection from $\mathbb{R}$ onto the unit circle
but the point $B$. Therefore, for almost every real $u$, there exists a real
$t$ such that $\cos u=\frac{1-t^{2}}{1+t^{2}}$ and $\sin
u=\frac{2t}{1+t^{2}}$. By substitution into the trigonometric parametrization
of the curve given above, and after simplification, we obtain the following
result:

######  Proposition 8 (First rational parametrization).

A rational parametrization of the regular trifolium is given by

$\begin{cases}x(t)=-\frac{4t^{2}(3t^{2}-1)(t^{2}-3)}{(t^{2}+1)^{4}},\\\
y(t)=-\frac{2t(t-1)(t+1)(3t^{2}-1)(t^{2}-3)}{(t^{2}+1)^{4}}.\end{cases}$ (8)

Another rational parametric presentation for the regular trifolium can be
obtained, not applying directly Lemma 7, but using the method of its proof.

######  Proposition 9 (Second rational parametrization).

A rational parametrization of the regular trifolium is given by

$\begin{cases}x(t)=-\frac{3t^{2}-1}{(t^{2}+1)^{2}},\\\
y(t)=-\frac{t(3t^{2}-1)}{(t^{2}+1)^{2}}.\end{cases}$ (9)

###### Proof.

The regular trifolium is a quartic with a triple point at the origin. The
$y-$axis is tangent to the curve at the origin; by substitution of $x=0$ into
Equation 2, we prove that there is no other point of intersection. Any other
line through the origin (with equation $y=tx$, the parameter $t$ being the
slope of the line) through the origin intersects the trifolium at one extra
point, as we see from the solution of system of equations 10 ; see Figure 4.

Figure 4. Geometric construction for parameterizing the regular trifolium

The coordinates of this point are the solutions of the following system of
equations:

$\begin{cases}(x^{2}+y^{2})^{2}=x\;(x^{2}-3y^{2}),\\\ y=tx.\end{cases}$ (10)

The solution is obtained by substitution and simplification222Of course, these
computations may be performed using a CAS with the solve command. The output
may show both the origin and the extra (variable) point.. ∎

######  Remark 10.

Other rational parametrizations of the unit circle can be obtained, using
other families of lines, such as the families given by equations $y=t(x-1)$
(lines through $A(1,0)$, or $y-1=tx$ (lines through $B(0,1)$, etc.). Following
the same process as above, we obtain different rational presentations for the
regular trifolium. Nevertheless, it can be proven that all of them provide the
same implicit equation for the envelope that we will study.

##  3\. The 1-parameter family of unit circles centred on the regular
trifolium

We consider now the family of unit circles $\mathcal{C}_{t}$ centred on the
regular trifolium described in Section 2. The index $t$ is actually the
parameter that we use for the parametric presentation of the trifolium. Here
we will use the formulas derived in Prop. 9, namely:

$\begin{cases}x(t)=-\frac{3t^{2}-1}{(t^{2}+1)^{2}},\\\
y(t)=-\frac{t(3t^{2}-1)}{(t^{2}+1)^{2}}.\end{cases}$

A general equation for the family of unit circles centred on the trifolium is
of the form $F(x,y,t)=0$, where

$F(x,y,t)=\left(x+\frac{3t^{2}-1}{(t^{2}+1)^{2}}\right)^{2}+\left(y+\frac{t(3t^{2}-1)}{(t^{2}+1)^{2}}\right)^{2}-1.$

According to Definition 3, an envelope of this family of unit circles, if it
exists, is determined by the solutions of the following system of equations
(the second one is displayed after simplification):

$\begin{cases}\left(x+\frac{3t^{2}-1}{(t^{2}+1)^{2}}\right)^{2}+\left(y+\frac{t(3t^{2}-1)}{(t^{2}+1)^{2}}\right)^{2}-1=0,\\\
-6t^{6}y+(-12x-18)t^{5}+18t^{4}y+(8x+60)t^{3}+22t^{2}y+(20x-18)t-2y=0.\end{cases}$
(11)

Denote

$D(t)=\left(9t^{6}-45t^{4}+75t^{2}+1\right)\left(t^{2}+1\right)^{2}.$

Then solutions of the System (11) are given by the two following
parametrizations, each one defining an envelope of the family of circles, and
their union being also an envelope of this family:

$\begin{cases}x(t)=\frac{27\;\left[(-3t^{4}+12t^{2}-1)\;\sqrt{D(t)(3t^{2}-5)^{2}(t^{2}+1)}-81t^{10}+567t^{8}-1530t^{6}+1566t^{4}-357t^{2}-5\right]}{D(t)\;(3t^{2}-5)},\\\
y(t)=\frac{t\left[-27t^{8}+144t^{6}-270t^{4}+72t^{2}+2\sqrt{D(t)(3t^{2}-5)^{2}(t^{2}+1)}+1\right]}{D(t)},\end{cases}$
(12)

and

$\begin{cases}x(t)=\frac{27\;\left[(3t^{4}-12t^{2}+1)\sqrt{D(t)(3t^{2}-5)^{2}(t^{2}+1)}-81t^{10}+567t^{8}-1530t^{6}+1566t^{4}-357t^{2}-5\right]}{D(t)\;(3t^{2}-5)},\\\
y(t)=-\frac{t\;\left[(27t^{8}-144t^{6}+270t^{4}-72t^{2}+2\sqrt{D(t)(3t^{2}-5)^{2}(t^{2}+1)}-1)\right]}{D(t)}.\end{cases}$
(13)

Figures 5(a) and 5(b) show the two separate components, which will be denoted
by $\mathcal{E}_{1}$ and $\mathcal{E}_{2}$ respectively. In Figure 5(c), both
the trifolium and the “full” envelope
$\mathcal{E}=\mathcal{E}_{1}\cup\mathcal{E}_{2}$ are displayed. A first
analysis of the display reveals the following properties:

  * •

The roles of the components $\mathcal{E}_{1}$ and $\mathcal{E}_{2}$ are not
symmetric.

  * •

It seems that $\mathcal{E}_{1}$ is twice tangent to $\mathcal{C}$ and
$\mathcal{E}_{2}$ is tangent once.

  * •

The tree points of tangency are the vertices of an equilateral triangle.

Of course, these remarks have to be proven. This can be done by algebraic
manipulations and CAS aided solution of systems of equations.

(a) 1st component

(b) 2nd component

(c) Full envelope

Figure 5. The envelopes of the family of unit circles

######  Remark 11.

The first and second envelopes are themselves disjoint unions of subcurves,
with obvious discontinuities. These plots have been obtained with Maple. A
first attempt with the plot command yielded within one second a picture with
superfluous straight segments connecting the separate subcurves. Addition of
the option discont=true eliminated these superfluous, but each computation
required about one minute.

The full envelope is also the disjoint union of two components: an external
one (with three bulbs) and an internal one (looking like 3 fishes connected by
their mouth). We will now use algebraic manipulations in order to determine an
implicit polynomial equation for the envelope. The properties of the
polynomial will indicate whether each of these components is an algebraic
curve, or of they are impossible to distinguish by that way.

We transform Equations (12) into polynomial equations, using squaring and
transferring form side to side. We obtain the two following polynomials in
three variables $x,y,t$:

$P_{1}(x,y,t)=9t^{14}x^{2}-9t^{14}-9t^{12}x^{2}+54t^{12}x+45t^{12}-51t^{10}x^{2}-180t^{10}x+120t^{10}+67t^{8}x^{2}+18t^{8}x-678t^{8}+283t^{6}x^{2}+648t^{6}x+647t^{6}+261t^{4}x^{2}+250t^{4}x-567t^{4}+79t^{2}x^{2}-148t^{2}x+90t^{2}+x^{2}-2x,$
$P_{2}(x,y,t)=9t^{14}y^{2}+54t^{13}y-9t^{12}y^{2}+45t^{12}-180t^{11}y-51t^{10}y^{2}-447t^{10}+18t^{9}y+67t^{8}y^{2}+1106t^{8}+648t^{7}y+283t^{6}y^{2}-462t^{6}+250t^{5}y+261t^{4}y^{2}-111t^{4}-148t^{3}y+79t^{2}y^{2}-99t^{2}-2ty+y^{2}.$

These polynomials generate an ideal $J=\left<P_{1},P_{2}\right>$ in the
polynomial ring $\mathbb{R}[x,y,t]$. Using Maple’s command EliminationIdeal,
we eliminate the variable $t$ (i.e. we compute a projection onto
$\mathbb{R}[x,y]$). The obtained ideal is generated by a polynomial of degree
28 in two variables $x$ and $y$. This polynomial has exactly two irreducible
components, each of degree 14, namely:

$F_{1}(x,y)=256x^{14}+1792x^{12}y^{2}+5376x^{10}y^{4}+8960x^{8}y^{6}+8960x^{6}y^{8}+5376x^{4}y^{10}+1792x^{2}y^{12}+256y^{14}-512x^{13}-1024x^{11}y^{2}+2560x^{9}y^{4}+10240x^{7}y^{6}+12800x^{5}y^{8}+7168x^{3}y^{10}+1536xy^{12}+3840x^{12}-12032x^{10}y^{2}-78848x^{8}y^{4}-122368x^{6}y^{6}-71936x^{4}y^{8}-8960x^{2}y^{10}+3584y^{12}-5728x^{11}+14752x^{9}y^{2}+50752x^{7}y^{4}+6464x^{5}y^{6}-51680x^{3}y^{8}-27872xy^{10}+6080x^{10}+120064x^{8}y^{2}+336000x^{6}y^{4}+333056x^{4}y^{6}+107968x^{2}y^{8}-3072y^{10}-5952x^{9}-22688x^{7}y^{2}-435936x^{5}y^{4}-288480x^{3}y^{6}+75424xy^{8}-56823x^{8}-376540x^{6}y^{2}+232758x^{4}y^{4}-358620x^{2}y^{6}-26359y^{8}+35646x^{7}+360802x^{5}y^{2}+636938x^{3}y^{4}+201190xy^{6}+65109x^{6}-176542x^{4}y^{2}-256867x^{2}y^{4}-19328y^{6}-38090x^{5}-387676x^{3}y^{2}-68626xy^{4}-15173x^{4}+339668x^{2}y^{2}+25677y^{4}+14394x^{3}-67846xy^{2}-3289x^{2}-90y^{2}+242x,$
$F_{2}(x,y)=1024x^{14}+7168x^{12}y^{2}+21504x^{10}y^{4}+35840x^{8}y^{6}+35840x^{6}y^{8}+21504x^{4}y^{10}+7168x^{2}y^{12}+1024y^{14}-2048x^{13}-4096x^{11}y^{2}+10240x^{9}y^{4}+40960x^{7}y^{6}+51200x^{5}y^{8}+28672x^{3}y^{10}+6144xy^{12}-3072x^{12}-27648x^{10}y^{2}-67584x^{8}y^{4}-71680x^{6}y^{6}-39936x^{4}y^{8}-15360x^{2}y^{10}-4096y^{12}+13632x^{11}+13632x^{9}y^{2}-81792x^{7}y^{4}-190848x^{5}y^{6}-149952x^{3}y^{8}-40896xy^{10}-4992x^{10}-28416x^{8}y^{2}-54528x^{6}y^{4}-49152x^{4}y^{6}-23424x^{2}y^{8}-5376y^{10}-34944x^{9}+15552x^{7}y^{2}+152640x^{5}y^{4}+312384x^{3}y^{6}+99648xy^{8}+28793x^{8}+258596x^{6}y^{2}+220566x^{4}y^{4}+35492x^{2}y^{6}+44729y^{8}+35078x^{7}-35078x^{5}y^{2}-175390x^{3}y^{4}-105234xy^{6}-60633x^{6}-297828x^{4}y^{2}-104613x^{2}y^{4}-73514y^{6}-35046x^{5}+70092x^{3}y^{2}+105138xy^{4}+38880x^{4}+77760x^{2}y^{2}+38880y^{4}+23328x^{3}-69984xy^{2}.$

An implicit plot of $F_{2}$ is identical to the envelope displayed in Figure
5(c). Plotting $F_{1}$ yields a totally different figure, which is irrelevant
to our purpose. See [3] for a discussion of irrelevant components in such
situations.

The same process, starting from the parametric equations of the second
component leads to the same two polynomials $F_{1}(x,y)$ and $F_{2}(x,y)$.

The role of the two components can be explored using an animation with Maple.
Two snapshots are displayed in Figure 6.

Figure 6. Animation of the family of circles when the center moves along the
trifolium

Note that for every value of the parameter $t$, the corresponding circle
touches both components. This confirms, as if this was necessary, an
interesting detail in the definition of an envelope: its non-uniqueness. Here,
each component is a separate envelope of the given family of circles, and
their union too.

##  4\. The offset at distance 1 of the regular trifolium

An interactive study with GeoGebra of the given family of unit circles centred
on the regular trifolium shows that the offset of the family is different from
the envelope. Recall that the circles of the family have the following general
equation:

$\left(x+\frac{3t^{2}-1}{\left(t^{2}+1\right)^{2}}\right)^{2}+\left(y+\frac{t\left(3t^{2}-1\right)}{\left(t^{2}+1\right)^{2}}\right)^{2}=1.$
(14)

Using a slider bar with the Trace On feature to modify the values of the
parameter $t$, a certain number of circles can be plotted. Note that no
preview of the envelope is visible here, but some preview of the offset is
obtained. See Figure 7, which shows the regular trifolium $\mathcal{C}$ and a
certain number of circles of the family.

(a) animation of circles

(b) with the envelope

Figure 7. Offset preview of the family of unit circles

From this experiment, it appears that the offset is the union of arcs of the
external envelope (the internal part, looking like three fishes, is irrelevant
to the question here). The open question is: which arcs? The answer can come
from an analytic treatment only.

##  5\. Symbolic experiments with GeoGebra

Recent improvements in GeoGebra, in particular in its experimental version
_GeoGebra Discovery_ , allow us to directly study the offsets of the regular
trifolium at various distances. Latest versions since December 2020 (freely
available at https://github.com/kovzol/geogebra/releases) make it possible to
define the algebraic equation (2) with parameter $a=1$, and then use it as a
path for a moving circle. First the user enters this equation in the _Input
Bar_ and obtains the object $eq1$, then a distance $f$ will be defined by a
segment $AB$. As a next step, a point $C$ is attached to the trifolium curve,
and a circle $c$ with center $C$ and radius $f$ will be added. At last, the
command Envelope($c$,$C$) will be used to compute the offset of the trifolium
at distance $f$. (The same result can be obtained by using the _Envelope tool_
and clicking on $c$ and $C$. In this alternative way, the user does not even
have to type anything but the equation, and just use the mouse.) Fig. 8 shows
how the object $eq2$ can be obtained finally when $f=0.5$.

Figure 8. The distance $0.5$ offset of the regular trifolium made with
GeoGebra Discovery

The obtained figure shows some similarities with the previously obtained
figures, most visibly the external envelope has a similar geometry. On the
other hand, there is an inmost envelope that seems to be a circle. We can
verify this fact by opening the _CAS View_ and issue the command

Factors(LeftSide($eq2$)-RightSide($eq2$))

which informs us that the obtained result consists of two factors: one defines
a circle with center $(0,0)$ and radius $1/2$, reported as $4x^{2}+4y^{2}-1$;
the other factor is

$O_{1/2}(x,y)=262144x^{14}-524288x^{13}+1835008x^{12}y^{2}-1048576x^{11}y^{2}+540672x^{11}+5505024x^{10}y^{4}-2359296x^{10}y^{2}+49152x^{10}+2621440x^{9}y^{4}+540672x^{9}y^{2}-614400x^{9}+9175040x^{8}y^{6}-5505024x^{8}y^{4}-5947392x^{8}y^{2}-352000x^{8}+10485760x^{7}y^{6}-3244032x^{7}y^{4}+3981312x^{7}y^{2}+570368x^{7}+9175040x^{6}y^{8}-2621440x^{6}y^{6}-7766016x^{6}y^{4}+9098240x^{6}y^{2}+213504x^{6}+13107200x^{5}y^{8}-7569408x^{5}y^{6}-10911744x^{5}y^{4}-570368x^{5}y^{2}-359424x^{5}+5505024x^{4}y^{10}+1572864x^{4}y^{8}+1867776x^{4}y^{6}+1390080x^{4}y^{4}-2059776x^{4}y^{2}-277344x^{4}+7340032x^{3}y^{10}-5947392x^{3}y^{8}+13320192x^{3}y^{6}-2851840x^{3}y^{4}+718848x^{3}y^{2}+62208x^{3}+1835008x^{2}y^{12}+786432x^{2}y^{10}+2998272x^{2}y^{8}-7244800x^{2}y^{6}+2440704x^{2}y^{4}-554688x^{2}y^{2}+139968x^{2}+1572864xy^{12}-1622016xy^{10}+516096xy^{8}-1711104xy^{6}+1078272xy^{4}-186624xy^{2}+262144y^{14}-262144y^{12}-638976y^{10}+815360y^{8}-86528y^{6}-277344y^{4}+139968y^{2}-19683,$

defining again a curve of degree 14.

We emphasize here that, in the background, the analytic method was used by
GeoGebra, that is, computing a Jacobi determinant and then using elimination
to obtain an equation in two variables, defining a plane curve. (See [14] and
[15] for more details.) In other words: GeoGebra performed an automated proof
on the validity of the formula that describes $O_{1/2}(x,y)$. What is more,
GeoGebra’s symbolic capability ensured that the conjectured formula was also
obtained in an automated way. (In fact, these two steps: conjecture and proof
were performed in one operation.) The computation took less than half of a
second on a modern computer.

When choosing $f=1$ or other values, similar results can be obtained. For
example, when changing $f$ to $1$ the result $(x^{2}+y^{2}-1)\cdot F_{2}(x,y)$
will be delivered, that is, again a product of a circle and the offset. In
this case is the computation, however, somewhat slower.

As a consequence, dynamic investigation of the set of offsets for various
distances is a bit inconvenient in GeoGebra. When fixing point $A$ and
dragging point $B$ we reach computation speed between and 1.34 and 1.35 frame
per second (FPS)333Testing was performed on Ubuntu Linux 18.04, Intel(R)
Core(TM) i7-4770 CPU @ 3.40GHz. See https://prover-
test.geogebra.org/job/GeoGebra_Discovery-art-
plottertest/72/artifact/fork/geogebra/test/scripts/benchmark/art-
plotter/html/all.html for a detailed output of the benchmarking suite, test
cases trifolium-offset1.ggb, …, trifolium-offset4.ggb. These results are valid
for the native version of GeoGebra, that is, GeoGebra Classic 5. The web
version, that is, GeoGebra Classic 6, underperforms this speed between 0.23
and 0.24 FPS., even if the same distance is defined but with different input
points—this difference comes from the very different computational character
of the slightly different algebraic translations. In fact, for an enjoyable
animation the user could expect at least 5 FPS, so further speedup of the
computation could be addressed in future work.

On the other hand, slow movement of point $B$ can show how the set of offsets
look like. Fig. 9 presents how the curves change while $B$ is dragged from
$(1.5,1.5)$ to $(1,0.5)$. (Coloring of point $B$ and the curve $eq2$ depends
on the length of $f$: we used the RGB-components $(f,1-f,1)$.) An online
version of this experiment can be found at [9].

Figure 9. Various offsets of the trifolium for distances $f$ between $0.5$ and
$1$

##  6\. Conclusion

We derived the offset curve of a regular trifolium by using different
approaches. Automated reasoning based on elimination played an important role
in our results. In our last experiment we highlighted that a point-and-click
approach by using a Dynamic Geometry System can merge conjecturing and proving
to a single step, and dragging some input points a large set of theorems can
be proven in a novel way.

##  7\. Acknowledgments

First author was partially supported by the CEMJ Chair at JCT 2019-2020.
Second author was partially supported by a grant MTM2017-88796-P from the
Spanish MINECO (Ministerio de Economia y Competitividad) and the ERDF
(European Regional Development Fund). Special thanks to Bernard Parisse for
his efforts on improving the Giac Computer Algebra System especially for this
research.

## References

  * [1] Adams, W., Loustaunau, P.: An Introduction to Gröbner Bases, Graduate Studies in Mathematics 3, American Mathematical Society, RI: Providence (1994).
  * [2] Berger, M.: Geometry, Berlin-Heidelberg: Springer Verlag (1987).
  * [3] Botana, F., Recio, T.: Some issues on the automatic computation of plane envelopes in interactive environments, Mathematics and Computers in Simulation 125, 115–125 (2016). https://doi.org/10.1016/j.matcom.2014.05.011
  * [4] Botana, F., Valcarce, J.L.: Automatic determination of envelopes and other derived curves within a graphic environment, Mathematics and Computers in Simulation 67, 3–13 (2004). https://doi.org/10.1016/j.matcom.2004.05.004
  * [5] Cox, D., Little, J., O’Shea, D.: Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, Undergraduate Texts in Mathematics, Springer Verlag, New York (1992).
  * [6] Dana-Picard, Th.: Automated study of a regular trifolium, Math. Comput. Sci. 13(1-2), 57–67 (2018). https://doi.org/10.1007/s11786-018-0351-7
  * [7] Dana-Picard, Th.: Envelopes and Offsets of Two Algebraic Plane Curves: Exploration of Their Similarities and Differences. Math. Comput. Sci. (2021). https://doi.org/10.1007/s11786-021-00504-5
  * [8] Dana-Picard, Th., Kovács, Z.: Networking of technologies: a dialog between CAS and DGS. Electronic Journal of Mathematics & Technology. 15(1), 43–59 (2021).
  * [9] Dana-Picard, Th., Kovács, Z.: Offsets of a trifolium, available: https://matek.hu/zoltan/offsets-of-a-trifolium.php (2020).
  * [10] Dana-Picard, Th., Zehavi, N.: Revival of a classical topic in Differential Geometry: the exploration of envelopes in a computerized environment, International Journal of Mathematical Education in Science and Technology 47(6), 938–959 (2016). https://doi.org/10.1080/0020739X.2015.1133852
  * [11] Ferréol, R., J.: Regular Trifolium, available: https://mathcurve.com/courbes2d.gb/trifoliumregulier/trifoliumregulier.shtml (2017).
  * [12] Ferréol, R.: Rational Quartic, available: https://mathcurve.com/courbes2d.gb/quarticrationnelle/quarticrationnelle.shtml (2017).
  * [13] Kock, A.: Envelopes – notion and definiteness, Beiträge zur Algebra und Geometrie (Contributions to Algebra and Geometry) 48, 345–350 (2007).
  * [14] Kovács, Z.: Real-time Animated Dynamic Geometry in the Classrooms by Using Fast Gröbner Basis Computations, Math. Comput. Sci. 11(3-4), 351–361 (2017). https://doi.org/10.1007/s11786-017-0308-2
  * [15] Kovács, Z.: Achievements and Challenges in Automatic Locus and Envelope Animations in Dynamic Geometry, Math. Comput. Sci. 13, 131–141 (2018). https://doi.org/10.1007/s11786-018-0390-0
  * [16] Sendra, J.R., Winkler, F., Pérez-Díaz, S.: Rational Algebraic Curves: A Computer Algebra Approach, Springer (2008).
  * [17] Zeitoun, D., Dana-Picard, Th.: Accurate visualization of graphs of functions of two real variables, International Journal of Computational and Mathematical Sciences 4(1), 1–11 (2010).
  * [18] Zeitoun, D., Dana-Picard, Th.: On the usage of different coordinate systems for 3D plots of functions of two real variables, Math. Comput. Sci. 13, 311–327 (2019). https://doi.org/10.1007/s11786-018-0359-z


We say that a graph is $k$-mixing if it is possible to transform any $k$-coloring into any other via a sequence of single vertex recolorings keeping a proper coloring all along. Cereceda, van den Heuvel and Johnson proved that deciding if a graph is $3$-mixing is co-NP-complete and left open the case $k \ge 4$.
We prove that for every $k \ge 4$, $k$-mixing is co-NP-hard.

Let $G$ be a graph. All the colorings considered in this paper are proper (that is adjacent vertices receive distinct colors). We say that two colorings are adjacent if they differ on exactly one vertex. The configuration graph of the $k$-colorings of a $k$-colorable graph $G$ is the graph whose vertices are $k$-colorings of $G$ with the adjacency defined above. A graph $G$ is $k$-mixing if its $k$-configuration graph of the $k$-colorings of $G$ is connected. In the $k$-Mixing problem, we are given an integer $k$ and a $k$-colorable graph $G$ and we want to decide if $G$ is $k$-mixing.
Cereceda, van den Heuvel and Johnson proved in [4] that the following holds:

$3$-Mixing is co-NP-complete.

They also proved that a $3$-chromatic graph[A graph is $k$-chromatic if it is $k$-colorable and is not $(k-1)$-colorable.] is never $3$-mixing.
Surprisingly, for any $k \ge 4$, the complexity status of $k$-mixing for every $k \ge 4$ is open. Neither the fact that it belongs to co-NP or the co-NP hardness has been proven.These problems were mentionned as open problems for instance in [2, 3, 6, 5]. We propose a very simple proof that the problem is co-NP hard for every $k \ge 4$:

For every $k \ge 4$, $k$-Mixing is co-NP-hard (even on $(k-1)$-colorable graphs where all the color classes but at most $2$ are reduced to a single vertex).

To prove Theorem <ref>, the main idea consists in observing that Theorem <ref> is equivalent to the following statement: deciding if any $3$-coloring of a bipartite graph $B$ can be transformed into a $2$-coloring is co-NP-complete. We will call this problem the $3$-To-$2$ problem. The fact that the $3$-To-$2$ problem is co-NP-complete is a direct consequence of the following lemma:

A graph $G$ is $3$-mixing if and only if it is a bipartite graph and we can reach a $2$-coloring from any $3$-coloring.

Since $3$-chromatic graphs are not $3$-mixing [4], the first condition holds (and can be checked in polynomial time).

Assume now that $G$ is bipartite. If $G$ is $3$-mixing then we can indeed transform any coloring $c$ into every $2$-coloring of $G$ by definition of being mixing.
Conversely, if any coloring $c$ of $G$ can be transformed into a $2$-coloring $c'$ then let us prove that there always exists a transformation between any pair of colorings $c_1,c_2$. By assumption, $c_1$ can be transformed into a $2$-coloring $c_1'$ with a sequence $\mathcal{S}_1$ and $c_2$ can be transformed into a $2$-coloring $c_2'$ with a sequence $\mathcal{S}_2$. Up to a recoloring of the vertices colored $2$ with $1$ or $0$, we can assume that the set of colors used in $c_1'$ is $\{1,2\}$ and in $c_2'$ is $\{ 0,1 \}$.

Let us denote by $X_0,X_1$ the vertices colored respectively $0$ and $1$ in $c_2'$. So we can successively recolor in $c_1'$ all the vertices of $X_0$ with color $0$ and then all the vertices of $X_1$ with color $1$. So we can transform $c_1$ into $c_2'$. We append to this transformation $\mathcal{S}_2$ in the  reverse order to get transformation from $c_1$ to $c_2$.

Using this lemma we can prove Theorem <ref>:

Let $k \ge 4$. Let us provide a reduction from $3$-To-$2$ to $k$-Mixing. We can assume that the instance of $3$-To-$2$ is a bipartite graph $B$, otherwise we immediately return a no instance. Consider the graph $G$ consisting of $B$ plus $k-3$ vertices $X$ inducing a clique which are complete to $B$. We claim that $G$ is $k$-mixing if and only if every $3$-coloring of $B$ can be transformed into a $2$-coloring.

If one cannot reach a $2$-coloring from a $3$-coloring $c$ of $B$, then no vertex of $X$ can be recolored in any coloring reachable from $c$ (every vertex of $X$ being adjacent to the $3$-colors of $B$ plus the $k-4$ colors of the other vertices of $X$ in any coloring reachable from $c$). So $G$ is not $k$-mixing.

Conversely, assume that any coloring $3$-coloring of $B$ can be transformed into a $2$-coloring. Let $c_1,c_2$ be two $k$-colorings of $G$. Since $3$-To-$2$ is positive if and only if $B$ is $3$-mixing, we can reach from $c_1$ and $c_2$ two colorings $c_1'$ and $c_2'$ such that $c_1[X]=c_1'[X]$, $c_2[X]=c_2'[X]$ and, vertices of $B$ are $2$-colored in both $c_1'$ and $c_2'$ with the same color classes  denoted $B_1$ and $B_2$ (but not necessarily the same colors).

We now identify all the vertices of $B_1$ and $B_2$ in $G$. The colorings $c_1'$ and $c_2'$ are still properly defined (since all the vertices of $B_1$ and $B_2$ are colored the same in both colorings). The resulting graph is a clique on $k-1$ vertices. We can now recolor the clique on $O(k)$ steps (see e.g. in [1]) and this recoloring can be transformed into a recoloring from $c_1'$ to $c_2'$ in $O(n)$ steps as observed for instance in [1].

We conclude the paper with the following conjecture:

For every $k \ge 4$, $k$-Mixing is PSPACE-complete.

Note that if $k$-Mixing is PSPACE-complete for some $k$ then it does not imply that $k'$-Mixing is PSPACE-complete for $k' \ge k$. However, the proof of Theorem <ref> ensures that if $k$-Mixing restricted to $(k-1)$-chromatic graphs is PSPACE-complete, then the same holds for $k' \ge k$. We actually conjecture that the following holds:

$4$-To-$3$ is PSPACE-complete.

The author would like to thank Laurent Feuilloley, Moritz Mühlenthaler and Théo Pierron for discussions about the problem.

[1]
M. Bonamy and N. Bousquet.
Recoloring graphs via tree decompositions.
Eur. J. Comb., 69:200–213, 2018.

[2]
R. C. Brewster and B. R. Moore.
Characterizing circular colouring mixing for $\frac p q \le 4$.
J. Graph Theory, 102(2):271–294, 2023.

[3]
L. Cereceda.
Mixing Graph Colourings.
PhD thesis, London School of Economics and Political Science, 2007.

[4]
L. Cereceda, J. van den Heuvel, and M. Johnson.
Mixing 3-colourings in bipartite graphs.
Eur. J. Comb., 30(7):1593–1606, 2009.

[5]
M. Heinrich.
Reconfiguration and Combinatorial Games.
PhD thesis, Université Claude Bernard Lyon 1, 2019.

[6]
J. van den Heuvel.
The Complexity of change, page 409.
Part of London Mathematical Society Lecture Note Series. Cambridge
University Press, S. R. Blackburn, S. Gerke, and M. Wildon edition, 2013.