Puyuan Peng1, Brian Yan2, Shinji Watanabe2, David Harwath1

# Prompting the Hidden Talent of Web-Scale Speech Models
for Zero-Shot Task Generalization

###### Abstract

We investigate the emergent abilities of the recently proposed web-scale
speech model Whisper, by adapting it to unseen tasks with prompt engineering.
We selected three tasks: audio-visual speech recognition (AVSR), code-switched
speech recognition (CS-ASR), and speech translation (ST) on unseen language
pairs. We design task-specific prompts, by either leveraging another large-
scale model, or simply manipulating the special tokens in the default prompts.
Experiments show that compared to the default prompts, our proposed prompts
improve performance by $9\%$ to $45\%$ on the three zero-shot tasks, and even
outperform SotA supervised models on some datasets. In addition, our
experiments reveal many interesting properties of Whisper, including its
robustness to prompts, bias on accents, and the multilingual understanding in
its latent space. Code is available here

Index Terms: speech recognition, audio-visual speech recognition, speech
translation, zero-shot learning, task adaptation, web-scale speech models

##  1 Introduction

The study of large scale foundation models [1] has become ubiquitous in many
areas of AI, such as large language models for natural language processing [2,
3, 4], vision-and-language models for computer vision [5, 6]. One of the most
intriguing aspects of these large scale pretrained models is their emergent
ability [7], usually invoked by prompting [8], to generalize to unseen data or
tasks [2, 5]. In addition to its scientific value, the zero-shot
generalization capability of large scale models alleviates the burden of
collecting specialized datasets or training special-purpose models for new
tasks and domains, resulting in tremendous impact on the application of AI.

In the field of audio and speech processing, prompt engineering has only
recently started to attract attention. Gao et al. [9] finetuned a wav2vec2
model [10] to produce tokens as prompt for the frozen GPT-2 [11] to do speech
and audio classification tasks. Concurrently, Chang et al. [12] studied
gradient-based prompt tuning on a pre-trained speech unit language model [13]
for speech classification and generation tasks. Kim et al. [14] combined
learnable prompts and adapters for efficient finetuning of audio models. Xue
et al. [15] is the most similar work to ours. In that paper, the authors
trained a Transformer-Transducer model using in-house data on a comparable
scale to Whisper, and they ran test time gradient-based adaptation to fine-
tune the model for speech translation on unseen language pairs. Our work is
different from theirs because our adaptation methods are prompt-based and
gradient-free, and we study three different zero-shot tasks instead of just
one.

_Our work reveals and analyzes the hidden talent and weaknesses of Whisper
[16]._ It is the first of its kind that studies gradient-free zero-shot task
generalization abilities of web-scale speech models. We show that Whisper can
be easily adapted to unseen tasks by simply modifying its prompt. The
effectiveness of our proposed prompts are validated on three tasks - audio-
visual speech recognition (AVSR), code-switched speech recognition (CS-ASR),
and speech translation (ST) on unseen language pairs.

##  2 The Whisper model

Here we briefly describe the Whisper model family [16] with an emphasis on the
structure of its default prompt. Whisper is a family of Transformer-based
encoder-decoder models [17] with parameters ranging from 39M (Tiny and
Tiny.en) to 1.55B (Large and LargeV2). Whisper models can be categorized into
two classes based on languages and tasks: English-only models and multilingual
models. The multilingual models are trained on 630k hours of web-scraped
speech data for multilingual automatic speech recognition (ASR),
En$\rightarrow$X speech translation (ST), language identification (LID), and
timestamp prediction. The English models are trained on the English subset of
the data (438k hours) for ASR and timestamp prediction. The encoder of Whisper
models takes in log Mel spectrogram, and produces features for the decoder.
The decoder consumes encoder features, positional embeddings, and a prompt
token sequence. It then produces the transcription of the input speech, or
alternatively its translation depending on the prompt. The prompt used in the
original Whisper paper is the following: <|sop|>previous
text<|sot|><|language|><|task|><|notimesta mps|>111We use <|sop|> to
abbreviate <|startofprev|>, and <|sot|> for <|startoftranscript|>. Also
<|asr|> for <|transcribe|>, and <|st|> for <|translate|> later.. Those
encapsulated in <||> are special tokens. previous text represents the
transcript of the previous utterance, and is optional. For multilingual
models, <|language|> should be replaced by one of the 99 language tokens that
Whisper encountered during training. When the input language is unknown at
inference, Whisper will first run LID which results in a probability
distribution over the 99 languages, and the language with the highest
probability is chosen to fill the <|language|> token. <|task|> will be
replaced by either <|asr|> or <|st|> depending on whether the model should
perform ASR or ST. We keep <|notimestamps|> in all prompts as our tasks do not
need Whisper to produce timestamps222and therefore we omit this token in the
rest of the paper.

In all three zero-shot tasks that we consider in this paper, we only modify
the prompt to the Whisper decoder without modifying the model weights or
architecture. See table 1 for a summary of our proposed prompts.

Table 1: Summary of our proposed prompts and relative improvement over the
default prompts. The differences between our prompt and the default are in
bold. In the AVSR task, CLIP retrie. stands for ``CLIP retrieved objects'',
and <default> stands for <|sot|><|en|><|asr|>, please find detailed
description of our prompt for AVSR in section 3. For each task only one case
is shown in the table, and similar improvements are shown across different
datasets and languages in the main text.

Task | Language(s) | Default prompt | Our proposed prompt | Improvement
---|---|---|---|---
AVSR | En | <|sot|><|en|><|asr|> | <|sop|>CLIP retrie.<default> | $9\%$
CS-ASR | Zh+En | <|sot|><|zh|>or<|en|><|asr|> | <|sot|><|zh|><|en|><|asr|> | $19\%$
ST | En$\rightarrow$Ru | <|sot|><|ru|><|st|> | <|sot|><|ru|><|asr|> | $45\%$

##  3 Audio-visual speech recognition

The first task is using an ASR system to produce transcription for a video,
where the on-screen visual content is semantically related to the speech audio
and can therefore aid in recognition [18, 19]. This task is related to, but
more general than, performing audio-visual speech recognition (AVSR) on speech
audio accompanied by a video of the speaker's facial or lip movements [20].

Approach. Our approach is shown in figure 1. To provide Whisper with a
visually-conditioned prompt, we utilize the popular vision-and-language CLIP
[5] model along with an external vocabulary of common object words to first
`convert' the visual stream into a sequence of word tokens. To do so, we take
every word/phrase in the external vocabulary, construct a sentence with
template ``This is a photo of a { }''. Then we use the CLIP text encoder to
pre-compute an embedding vector for each sentence in an offline fashion. At
inference time, for each video we sample $3$ equally-spaced RGB image frames,
use the CLIP image encoder to embed them, and calculate the similarity between
the image embeddings and the pre-computed text embeddings. We select the top
$K$ objects whose embeddings have the highest similarity scores with the image
embeddings for the prompt. Next, we concatenate the $K$ selected object names
into a comma-separated list of words, and insert this token sequence into the
previous text slot of the prompt. This method draws inspiration from the idea
of Socratic Models [21], where an engineered interface enables large
pretrained models to `talk' to one other to solve a complex task.

Datasets and implementation details. Our main dataset for the AVSR task is the
recently proposed VisSpeech [19], which is a subset of the instructional video
dataset HowTo100M [22]. VisSpeech consists of those videos where an audio-only
baseline ASR system performs badly, and whose visual stream and speech audio
are semantically related. Since VisSpeech is proposed as a test set and it
only contains 508 examples, we use another instructional video dataset, How2
[18], for hyperparameter tuning. We use a randomly selected 2000 example
subset of How2, and add pub noise to the audio to increase the ASR difficulty
similar to [19], since the dataset has been shown to be biased towards clean
audio [19] preventing the visual modality from offering significant benefit to
its ASR task. For the external object vocabulary, we follow [21] and used the
label set of Tencent ML-Images [23], which contains around 10,000 common
objects. The number of object $K$ used in the prompt is tuned for each Whisper
model separately on our version of the How2 dataset with three different noise
levels (SNR=$5$,$0$,$-5$dB).

Results. We found that on our How2 tuning set, using very large number of
objects (as many as $90$ objects) does not hurt performance. Our manual
inspection shows that even when using $30$ objects, there are already many
irrelevant ones that got mis-retrieved by CLIP. For example, in the example
shown in figure 1, we found `yogurt', `heavy cream', and `mayonnaise' in the
visual prompt. In addition, more than $90\%$ of the utterances in our How2
dataset have a ground truth transcription less than $30$ words. _This shows
that Whisper is very robust to the noise and length of the prompt._

For each model, the top $3$ best performing number of object choices selected
from How2 are used for the experiments on VisSpeech333We use $3$ number of
objects choices to reduce the tuning noise introduced by the mismatch between
How2 and VisSpeech., and the average WER is shown in figure 2. We see that the
_visually-informed prompt improves the performance for all four English models
and three smaller multilingual models, but hurts the performance of the
multilingual models Medium, Large, and LargeV2._ In table 2, we compare the
previous SotA AVSR results on VisSpeech with the audio-only Whisper
performance, and Whisper Medium.en with $50$ objects as the visual prompt. We
highlight that _visual prompt improve Medium.en by $9\%$, and even outperforms
Large._

Remarks. We propose a prompting approach that that adapts the audio-only
Whisper for audio-visual speech recognition. Based on figure 2, visual
prompting helps most of the models with the exception of three larger
multilingual models. However, because Large.en and LargeV2.en are not
available, it is difficult to draw conclusions on whether it is the model size
or multilinguality that hinders the model from benefiting from visual
prompting. The fact that visual prompting improves the performance of
Medium.en while degrading the performance of Medium suggests that the cause
could be multilinguality. If this is the case, multilingual models may benefit
from being fine-tuned on monolingual data.

Figure 1: Framework for visually prompting Whisper. The external object vocab
is dataset agnostic.

Figure 2: The effectiveness of visual prompt on VisSpeech across different
models.

Table 2: Comparison of model performance on VisSpeech. With visual prompt,
Medium.en outperforms Large.

Model | Modality | WER
---|---|---
SotA [19] | A+V | 11.28
Whisper Medium.en | A | 8.35
Whisper Medium.en | A+V | 7.60
Whisper Large | A | 8.02
Whisper LargeV2 | A | 7.16

##  4 Code-switched speech recognition

Code-switched speech refers to the scenario where more than one language is
used in the same utterance. With the raise of globalization and
democratization of speech recognition technologies, Code-switched ASR (CS-ASR)
has become a popular research area [24]. While we cannot know for certain
whether Whisper was trained on code-switched data, it is clear that the
model's language and task tokens can not explicitly direct the model to do CS-
ASR - each language token only represents one of the 99 training languages,
and the task tokens do not convey any information on whether the model should
output text in more than one language.

Approach. To test Whisper's CS-ASR capabilities, we use two Mandarin-English
code-switched corpora. See table 1 for a quick summary of default and our
proposed approach. The default approach (denoted as default) is to let Whisper
to first run LID to detect the language between the two444We set the
probabilities of the languages other than the two to be 0., and then use the
detected language in the prompt. While this default approach work to some
degree, it relies heavily on Whisper's LID capabilities, but our results show
this can sometimes be inaccurate, especially on accented speech. In addition,
this approach doesn't explicitly instruct the model to output text in more
than one language for intra-sentential code-switched utterances. We propose a
simple approach called concat that handles the aforementioned issues. The
concat approach replaces the single language token in the prompt with two
language tokens i.e. <|zh|> and <|en|>, as shown in table 1. As will be shown
later, despite the simplicity of this approach and the fact that Whisper has
never be trained to take two language tokens in the prompt, our approach
significantly improves performance.

Datasets and implementational details. We use ASCEND [25] and SEAME [26],
which are both Mandarin-English code-switched datasets. Both datasets are
spontaneous conversational speech, but ASCEND was recorded from bilingual
speakers with different Chinese dialects, while SEAME is recorded from
Singaporean and Malaysian speakers. We'll show that despite the fact that both
datasets contains the same languages, Whisper performs very differently on
them. Tuning is done on the validation sets of ASCEND and SEAME. For our
proposed concat approach, the hyperparameters we tune are: 1. the order of two
language tokens in prompt, and 2. the threshold on Whisper's LID confidence
score, above which we use the single detected language's token instead of
concatenating two language tokens. Whisper Large with concat (<|zh|> first)
outperforms all other models and prompts combinations on both datasets, and a
threshold of $0.9$ works the best for ASCEND, and $1.0$ i.e. always
concatenating two language tokens, works the best for SEAME.

Results. Table 3 shows the performance of Whisper Large on the validation set
of ASCEND and SEAME. In addition to default and our proposed concat prompts,
we also show results when we fixed the language token to be <|zh|> or <|en|>
for analysis purposes. _We see that the concat method performs the best on
both datasets_, and in particular it provides $19\%$ relative improvement on
Total MER (mixed error rate) on SEAME compared to default. Secondly, with
prompt <|zh|>, Whisper performs much better on pure Mandarin utterances on
ASCEND ($16.3$) than SEAME ($26.3$). Similar results are observed for pure
English utterances. This indicates that _Whisper's monolingual ASR performance
is much worse on SEAME than on ASCEND._ Next we note that on SEAME, when we
use default instead of <|en|>, En WER increased from $33.8$ to $85.5$, while
on ASCEND, WER was $31.8$ in both cases. This indicates that i.e. _Whisper's
LID performance for detecting English is much worse on SEAME than on ASCEND._

To understand how do different language prompts steer Whisper's output. We
manually examined the error modes, and found a common scenario where _the
model outputs monolingual translation for code-switched utterances_. This is
especially interesting when Whisper does English to Mandarin translation, as
the model was only trained to perform X$\rightarrow$En translation. This
phenomenon inspired us to quantitatively study En$\rightarrow$X translation
capabilities of Whisper in section 5.

The test set results for CS-ASR are shown in table 4. We see that _with
concat, Whisper achieves a new SotA for ASCEND_, while on SEAME there is still
an considerable gap between zero-shot Whisper and SotA.

Table 3: Performances of Whisper Large on ASCEND and SEAME validation sets. Zh
CER shows results on Mandarin utterances, En WER represents results on English
utterances. CS MER shows mixed error rate on code-switched utterance. Total
MER is the summarizing metric on the entire dataset.

Dataset | Lang. prompt. | Zh CER | En WER | CS MER | Total MER
---|---|---|---|---|---
ASCEND | <|zh|> | 16.3 | 93.1 | 33.1 | 32.6
<|en|> | 90.4 | 31.5 | 80.1 | 78.9
default | 17.0 | 31.8 | 26.6 | 22.1
concat | 16.6 | 31.8 | 25.0 | 21.3
SEAME | <|zh|> | 26.3 | 97.4 | 43.3 | 46.7
<|en|> | 99.3 | 33.8 | 86.9 | 82.2
default | 27.1 | 85.5 | 43.2 | 45.3
concat | 25.9 | 44.7 | 38.4 | 36.9

Table 4: Comparison between zero-shot Whisper Large and supervised SotA models
on ASCEND and SEAME test sets

Dataset | Approach | Zh CER | En WER | CS MER | Total MER
---|---|---|---|---|---
ASCEND | Sup. SotA [27] | - | - | - | 25.0
Whisper+default | 19.6 | 30.3 | 23.6 | 22.8
Whisper+concat | 16.8 | 30.8 | 22.0 | 20.9
SEAMEdevman | Sup. SotA [28] | - | - | - | 16.6
| Whisper+default | 24.7 | 76.3 | 38.2 | 38.2
| Whisper+concat | 23.6 | 45.8 | 33.4 | 32.7
SEAMEdevsge | Sup. SotA [28] | - | - | - | 23.3
| Whisper+default | 32.4 | 82.8 | 56.4 | 65.0
| Whisper+concat | 31.0 | 46.7 | 49.6 | 47.6

Figure 3: Whisper Zero-shot En$\rightarrow$X ST results. In the labels of
x-axis, Arabic (3kh,13.9) is interpreted as in the training of Whisper, Arabic
ASR data + Arabic$\rightarrow$English ST data amounts to 3k hours, and the
supervised ST baseline for English$\rightarrow$Arabic is 13.9. The same
interpretation applies to other languages. For the default prompt, we only
show numbers for larger models for better visualization.

Remarks. Recall that ASCEND is Chinese accented, and SEAME is Singaporean and
Malaysian accented, and based on our discussion on table 3, we hypothesize
that the performance gap on ASCEND and SEAME is because _Whisper's LID and ASR
performance vary drastically on different accents_ , even though the
underlying languages are the same. We leave a more comprehensive investigation
of this hypothesis for future work.

##  5 En to X speech translation

In this section, we investigate Whisper's ability to perform En$\rightarrow$X
speech translation (ST). Note that Whisper is trained on both multilingual ASR
and X$\rightarrow$En speech translation (ST), but never on En$\rightarrow$X
ST. Studying Whisper's zero-shot performance on En$\rightarrow$X ST could be a
way to measure the speech understanding capabilities that emerge from large
scale, multilingual, multitask training. we emphasize that the goal of this
section is not to achieve SotA performance, but to study the model's emergent,
zero-shot translation ability across different language families, amounts of
training data, and model sizes.

Approach. The default prompt for ST is to use <|st|> as the task token.
However, we found that <|st|> would lead Whisper to only output English no
matter what language token is used, unless we constrained the output
vocabulary. To instruct Whisper to do En$\rightarrow$X ST, we propose to use
task token <|asr|> instead, and use language token correspond to the language
X. See table 1 for a example of the default and our proposed approach.
Counter-intuitive as it might be (using <|asr|> for ST), as we'll show later,
our prompt outperforms the default prompt significantly, and even comes close
to supervised approaches for some languages.

Datasets and implementation details. We pick Arabic, Mandarin, Catalan and
German in CoVoST2 [29], to achieve a resource- and topology-wise diverse
evaluation. To be able to compare with supervised, unsupervised, and other
zero-shot ST approaches [30], we also evaluate Whisper on En$\rightarrow$Ru
and En$\rightarrow$De from MuST-C V1 [31], and En$\rightarrow$Fr from Libri-
Trans [32]. As for vocabulary constrain, for Arabic, Mandarin, and Russian, we
use the unicode range to constrain the vocab to only contain tokens that
belong to their scripts; for German, Catalan, and French we constrain the
vocab to only contain tokens that are the top $K\%$ most frequent in their
training set text. $K$ is tuned for CoVoST2 on the development set. For MuST-C
and Libri-Trans, we set K to be $40\%$ for German and $50\%$ for French based
on CoVoST2 tuning results.

Results. In Figure 3, we show different Whisper models' performance on the
four CoVoST2 languages. In general, for our proposed prompt, bigger models
perform better across languages, and vocabulary constrained generation
outperforms unconstrained generation. As for the default prompt (green bars),
we didn't show its performance for unconstrained generation as it only output
English text, and for constrained generation, it also performs vert poorly
except for Mandarin. We compare Whisper's performance with other models in
table 5555Whisper Large for En$\rightarrow$De; LargeV2 for En$\rightarrow$Ru
and En$\rightarrow$Fr.. Whisper performs reasonably on all three directions,
and especially well on En$\rightarrow$Ru. We note that the comparison in this
table should only be treated as a reference. This is because even for the
unsupervised and zero-shot approaches, they are particularly designed for ST,
and they either leverage machine translation systems [30, 33] or multilingual
sentence embedding models [34]. For Whisper, however, we simply adjust its
prompt, and the goal is to probe the multilingual understanding of the model.

Remarks. Although Whisper is trained with massive multilingual data,
performing En$\rightarrow$X might be harder than one expects. Because for the
<|st|> task token, the model is never trained to generate non-English text;
for the <|asr|> task token the model is never trained to generate text
belonging to a different language than the input speech. The fact that Whisper
is able to do En$\rightarrow$X ST with a simple modification on its prompt
reveals that semantically related words and phrases from different languages
might be close in the model's latent space. We also expect that we could fine-
tune Whisper to boost the performance of ST on new language pairs.

Table 5: Comparing zero-shot Whisper with supervised and unsupervised
approaches for MuST-C (En$\rightarrow$De and En$\rightarrow$Ru) and Libri-
Trans (En$\rightarrow$Fr). Zero-shot Whisper performs reasonably on all three
directions. *T-Modules [34] relies on strong multilingual sentence embedding
models that are trained on bitext.

Category | Approach | En$\rightarrow$De | En$\rightarrow$Ru | En$\rightarrow$Fr
---|---|---|---|---
Supervised | w2v2+mBART [30] | 32.4 | 20.0 | 23.1
E2E Transformer [35] | 27.2 | 15.3 | 11.4
Unsupervised | Chung et al. [36] | - | - | 12.2
Cascaded [30] | 22.0 | 10.0 | 15.4
E2E (w2v2+mBART) [30] | 23.8 | 9.8 | 15.3
Zero-shot | Escolano et al. [33] | 6.8 | - | 10.9
T-Modules* [34] | 23.8 | - | 32.7
Whisper w/ default prompt | 0.4 | 8.8 | 0.8
Whisper w/ our prompt | 18.1 | 12.8 | 13.1

##  6 Conclusion

We investigate the emergent abilities of Whisper through the lens of prompt-
based zero-shot task generalization. Our proposed prompts significantly
outperform the default prompts in all three tasks that we studied. In
addition, we found interesting properties of Whisper - in AVSR, we found that
the model is very robust to the length and noisiness of the visual prompt, and
the effectiveness of the visual prompt between English models and multilingual
models are quite different; in CS-ASR, we identified potential performance
gaps between different accents; in ST, we found the surprising results that
the <|asr|> task token can be used to instruct the model to do translation and
outperforms <|st|>. Many of the above properties are worth further
investigating, and can potentially lead to models that are more robust, more
generalizable, and have less unwanted bias.

## References

  * [1] R. Bommasani, D. A. Hudson, E. Adeli, R. Altman, S. Arora, S. von Arx, M. S. Bernstein, J. Bohg, A. Bosselut, E. Brunskill _et al._ , ``On the opportunities and risks of foundation models,'' _ArXiv preprint_ , 2021.
  * [2] T. B. Brown, B. Mann, N. Ryder, M. Subbiah, J. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, S. Agarwal, A. Herbert-Voss, G. Krueger, T. Henighan, R. Child, A. Ramesh, D. M. Ziegler, J. Wu, C. Winter, C. Hesse, M. Chen, E. Sigler, M. Litwin, S. Gray, B. Chess, J. Clark, C. Berner, S. McCandlish, A. Radford, I. Sutskever, and D. Amodei, ``Language models are few-shot learners,'' in _NeurIPS_ , 2020\.
  * [3] J. Wei, M. Bosma, V. Zhao, K. Guu, A. W. Yu, B. Lester, N. Du, A. M. Dai, and Q. V. Le, ``Finetuned language models are zero-shot learners,'' in _ICLR_ , 2022.
  * [4] J. Wei, X. Wang, D. Schuurmans, M. Bosma, E. Chi, Q. Le, and D. Zhou, ``Chain of thought prompting elicits reasoning in large language models,'' in _NeurIPS_ , 2022.
  * [5] A. Radford, J. W. Kim, C. Hallacy, A. Ramesh, G. Goh, S. Agarwal, G. Sastry, A. Askell, P. Mishkin, J. Clark, G. Krueger, and I. Sutskever, ``Learning transferable visual models from natural language supervision,'' in _ICML_ , 2021.
  * [6] K. Zhou, J. Yang, C. C. Loy, and Z. Liu, ``Learning to prompt for vision-language models,'' _IJCV_ , no. 9, 2022.
  * [7] J. Wei, Y. Tay, R. Bommasani, C. Raffel, B. Zoph, S. Borgeaud, D. Yogatama, M. Bosma, D. Zhou, D. Metzler, E. H. hsin Chi, T. Hashimoto, O. Vinyals, P. Liang, J. Dean, and W. Fedus, ``Emergent abilities of large language models,'' _TMLR_ , 2022.
  * [8] P. Liu, W. Yuan, J. Fu, Z. Jiang, H. Hayashi, and G. Neubig, ``Pre-train, prompt, and predict: A systematic survey of prompting methods in natural language processing,'' _ACM Computing Surveys_ , no. 9, 2023.
  * [9] H. Gao, J. Ni, K. Qian, Y. Zhang, S. Chang, and M. Hasegawa-Johnson, ``Wavprompt: Towards few-shot spoken language understanding with frozen language models,'' in _Interspeech_ , 2022.
  * [10] A. Baevski, H. Zhou, A. rahman Mohamed, and M. Auli, ``wav2vec 2.0: A framework for self-supervised learning of speech representations,'' in _NeurIPS_ , 2020\.
  * [11] A. Radford, J. Wu, R. Child, D. Luan, D. Amodei, and I. Sutskever, ``Language models are unsupervised multitask learners,'' 2019.
  * [12] K.-W. Chang, W.-C. Tseng, S.-W. Li, and H.-y. Lee, ``An exploration of prompt tuning on generative spoken language model for speech processing tasks,'' in _Interspeech_ , 2022.
  * [13] K. Lakhotia, E. Kharitonov, W.-N. Hsu, Y. Adi, A. Polyak, B. Bolte, T.-A. Nguyen, J. Copet, A. Baevski, A. Mohamed, and E. Dupoux, ``On generative spoken language modeling from raw audio,'' _Transactions of the Association for Computational Linguistics_ , 2021.
  * [14] J. ho Kim, J.-S. Heo, H. seo Shin, C. Lim, and H. jin Yu, ``Integrated parameter-efficient tuning for general-purpose audio models,'' _ArXiv_ , 2022\.
  * [15] J. Xue, P. Wang, J. Li, and E. Sun, ``A weakly-supervised streaming multilingual speech model with truly zero-shot capability,'' _ArXiv_ , 2022\.
  * [16] A. Radford, J. W. Kim, T. Xu, G. Brockman, C. McLeavey, and I. Sutskever, ``Robust speech recognition via large-scale weak supervision,'' _ArXiv preprint_ , 2022.
  * [17] A. Vaswani, N. M. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin, ``Attention is all you need,'' 2017.
  * [18] R. Sanabria, O. Caglayan, S. Palaskar, D. Elliott, L. Barrault, L. Specia, and F. Metze, ``How2: a large-scale dataset for multimodal language understanding,'' 2018.
  * [19] V. Gabeur, P. H. Seo, A. Nagrani, C. Sun, K. Alahari, and C. Schmid, ``Avatar: Unconstrained audiovisual speech recognition,'' in _Interspeech_ , 2022.
  * [20] J. S. Chung and A. Zisserman, ``Lip reading in the wild,'' in _ACCV_ , 2016\.
  * [21] A. Zeng, M. Attarian, brian ichter, K. M. Choromanski, A. Wong, S. Welker, F. Tombari, A. Purohit, M. S. Ryoo, V. Sindhwani, J. Lee, V. Vanhoucke, and P. Florence, ``Socratic models: Composing zero-shot multimodal reasoning with language,'' in _ICLR_ , 2023.
  * [22] A. Miech, D. Zhukov, J. Alayrac, M. Tapaswi, I. Laptev, and J. Sivic, ``Howto100m: Learning a text-video embedding by watching hundred million narrated video clips,'' in _ICCV_ , 2019.
  * [23] B. Wu, W. Chen, Y. Fan, Y. Zhang, J. Hou, J. Liu, and T. Zhang, ``Tencent ml-images: A large-scale multi-label image database for visual representation learning,'' _IEEE Access_ , 2019.
  * [24] G. I. Winata, A. F. Aji, Z.-X. Yong, and T. Solorio, ``The decades progress on code-switching research in nlp: A systematic survey on trends and challenges,'' _ArXiv preprint_ , 2022.
  * [25] H. Lovenia, S. Cahyawijaya, G. Winata, P. Xu, Y. Xu, Z. Liu, R. Frieske, T. Yu, W. Dai, E. J. Barezi, Q. Chen, X. Ma, B. Shi, and P. Fung, ``ASCEND: A spontaneous Chinese-English dataset for code-switching in multi-turn conversation,'' in _LREC_ , 2022.
  * [26] D.-C. Lyu, T. P. Tan, C. E. Siong, and H. Li, ``Seame: a mandarin-english code-switching speech corpus in south-east asia,'' in _Interspeech_ , 2010\.
  * [27] T. Nguyen, N. Tran, L. Deng, T. G. da Silva, M. Radzihovsky, R. Hsiao, H. Mason, S. Braun, E. McDermott, D. Can, P. Swietojanski, L. Verwimp, S. Oyman, T. Arvizo, H. Silovsky, A. Ghoshal, M. J. Martel, B. R. Ambati, and M. Ali, ``Optimizing bilingual neural transducer with synthetic code-switching text generation,'' _ArXiv_ , 2022.
  * [28] S. Watanabe, T. Hori, S. Karita, T. Hayashi, J. Nishitoba, Y. Unno, N. E. Y. Soplin, J. Heymann, M. Wiesner, N. Chen, A. Renduchintala, and T. Ochiai, ``Espnet: End-to-end speech processing toolkit,'' in _Interspeech_ , 2018\.
  * [29] C. Wang, A. Wu, and J. Pino, ``Covost 2: A massively multilingual speech-to-text translation corpus,'' 2020.
  * [30] C. Wang, H. Inaguma, P.-J. Chen, I. Kulikov, Y. Tang, W.-N. Hsu, M. Auli, and J. M. Pino, ``Simple and effective unsupervised speech translation,'' _ArXiv_ , 2022.
  * [31] M. A. Di Gangi, R. Cattoni, L. Bentivogli, M. Negri, and M. Turchi, ``MuST-C: a Multilingual Speech Translation Corpus,'' in _NAACL-HLT_ , 2019.
  * [32] A. C. Kocabiyikoglu, L. Besacier, and O. Kraif, ``Augmenting librispeech with French translations: A multimodal corpus for direct speech translation evaluation,'' in _LREC_ , 2018.
  * [33] C. Escolano, M. R. Costa-jussà, J. A. R. Fonollosa, and C. Segura, ``Enabling zero-shot multilingual spoken language translation with language-specific encoders and decoders,'' _ASRU_ , 2020.
  * [34] P.-A. Duquenne, H. Gong, B. Sagot, and H. Schwenk, ``T-modules: Translation modules for zero-shot cross-modal machine translation,'' in _EMNLP_ , 2022\.
  * [35] C. Wang, Y. Tang, X. Ma, A. Wu, D. Okhonko, and J. Pino, ``Fairseq S2T: Fast speech-to-text modeling with fairseq,'' in _AACL: System Demonstrations_ , 2020.
  * [36] Y. Chung, W. Weng, S. Tong, and J. R. Glass, ``Towards unsupervised speech-to-text translation,'' in _ICASSP_ , 2019.

##  Appendix A Appendix

###  A.1 Examples of CS-ASR transcription

Table 6: Examples of how concat improve transcription over default on SEAME with Whisper Large. We use … when transcriptions are the same for all three cases. Ground Truth | transcription w/ default | transcription w/ concat
---|---|---
也 不 需 要 做 research | 也 不 需 要 做 研 究 | 也 不 需 要 做 research
这 真 的 是 一 个 very tough question … | 这 真 的 是 一 个 很 困 难 的 问 题… | 这 真 的 是 一 个 very tough question…
每 次 … 还 是 choir practice | 每 次 … 还 是 quiet practice | 每 次 … 还 是 choir practice
then did you realise the performances… | 那 你 有 没 有 意 识 到 表 演 | then do you realise the performances…
…你 真 的 是 要 睡 觉 了 是 吗 | …你 真 的 是 要 sweet 小 的 是 吗 | …你 真 的 是 要 睡 觉 了 是 吗


V. Treumova, D. A. Lyakhov, and D. L. Michels V. Treumova et al.

<EMAIL_ADDRESS>and {dmitry.lyakhov, dominik.michels<EMAIL_ADDRESS>
# On the Algorithmic Verification of Nonlinear Superposition for Systems of
First Order Ordinary Differential Equations

Veronika Treumova  1  Dmitry A. Lyakhov  2  and Dominik L. Michels  2
11affiliationmark:  National Institute for Pure and Applied Mathematics, Rio
de Janeiro, Brazil
22affiliationmark:  Computational Sciences Group, KAUST, KSA  1  2

## Abstract

This paper belongs to a group of work in the intersection of symbolic
computation and group analysis aiming for the symbolic analysis of
differential equations. The goal is to extract important properties without
finding the explicit general solution. In this contribution, we introduce the
algorithmic verification of nonlinear superposition properties and its
implementation. More exactly, for a system of nonlinear ordinary differential
equations of first order with a polynomial right-hand side, we check if the
differential system admits a general solution by means of a superposition rule
and a certain number of particular solutions. It is based on the theory of
Newton polytopes and associated symbolic computation. The developed method
provides the basis for the identification of nonlinear superpositions within a
given system and for the construction of numerical methods which preserve
important algebraic properties at the numerical level.

Keywords: Algorithmic Verification, Difference Thomas Decomposition, Newton
Polytope, Nonlinear Superposition, Strong Consistency, Vessiot-Guldberg-Lie
Algebra.

##  1 Introduction

Nonlinear ordinary differential equations (ODEs) play a crucial role in
modeling a wide range of complex phenomena across various scientific
disciplines. Unlike linear ODEs, which are well-understood and often
analytically solvable in terms of elementary functions, nonlinear ODEs capture
intricate interactions and dependencies that characterize many real-world
systems ranging from physics and engineering to biology and economics.
Generally, addressing these equations involves employing difference
approximations for differential systems since analytical methods face
significant constraints. Rather than seeking exact solutions, engineering
tasks require obtaining an approximate solution with a specified level of
precision. Furthermore, practical considerations often necessitate the use of
an appropriate method that not only maintains the properties of the underlying
system in the limit but also does so for finite time steps, achieving an
approximation.

In this contribution, we focus on the symbolic analysis of nonlinear
superposition properties of systems of ODEs. Nonlinear superposition is a
generalization of the superposition principle to nonlinear systems. It states
that, for certain nonlinear systems, the response to a combination of inputs
can be expressed as a combination of the responses to the individual inputs.
This means that the system’s behavior is not always linear but still exhibits
some degree of predictability. The nonlinear superposition property is
important in many areas of physics, including quantum mechanics, fluid
dynamics, and optics [1, 2, 3, 4]. It is used to study the behavior of complex
systems that cannot be easily described by linear equations. For instance, in
quantum mechanics, the nonlinear superposition property is used to explain the
behavior of particles that can exist in multiple states at the same time. This
key element of modern quantum mechanics has many important consequences, such
as the existence of quantum entanglement and wave-particle duality. In fluid
dynamics, the nonlinear superposition property is used to study the behavior
of waves in fluids. For example, it can be used to explain the formation of
solitons, the interesting phenomenon of a single nonlinear wave that can
travel long distances without changing shape. In optics, the nonlinear
superposition property is used to explain the behavior of light in nonlinear
media – the phenomenon of self-focusing, i.e., a beam of light can focus
itself as it travels through a nonlinear medium.

This paper is organized as follows. In Section 2, we provide all required
definitions and the basic theorem. After discussing related work in Section 3,
we briefly present an elementary example illustrating the relevance of the
nonlinear superposition property in Section 4. The main mathematical objects
we deal with and the algorithms are then presented in Section 5. The
implementation of these algorithms in Maple is described in Section 6, and a
nontrivial example is illustrated in Section 7. Finally, we provide our view
on applications in Sections 8 and 9, and generalizations in Section 10 before
our concluding remarks in Section 11.

##  2 Mathematical Formulation

Sophus Lie had an extraordinary geometric vision of problems. It helped him to
simplify analytical calculations and often led him to new theoretical
concepts. One of them is the generalization of properties of linear equations,
which led to the concept of nonlinear superposition.

######  Definition 2.1.

We say that a differential system admits a nonlinear superposition rule if its
general solution can be represented in the form

$\textbf{x}=\Phi(\textbf{x}^{1},\textbf{x}^{2},\dots,\textbf{x}^{m};C_{1},\dots,C_{n})\,,$

including a finite number $m$ of partial solutions and $n$ arbitrary
constants.

The nonlinear superposition problem is strongly connected to the field of Lie
algebras [5]. Together with Vessiot and Guldberg, Sophus Lie characterized all
possible first-order ODE systems with superposition property:

######  Theorem 2.2.

The system of first-order ODEs with a vector of dependent variables
$\textbf{x}=(x_{1},\dots,x_{n})$ admits a nonlinear superposition if and only
if it has the form of generalized separation of variables with $r<\infty$
members:

$\frac{d\textbf{x}}{dt}=T_{1}(t)\xi^{i}_{1}(\textbf{x})+T_{2}(t)\xi^{i}_{2}(\textbf{x})+\dots+T_{r}(t)\xi^{i}_{r}(\textbf{x})\,,$
(1)

where the operators111We use the common summation rule in repeated indices.

$X_{\alpha}=\xi_{\alpha}^{i}(\textbf{x})\frac{\partial}{\partial
x_{i}},\,\alpha=1,\dots r\,,$

satisfy the commutator relations

$[X_{\alpha},X_{\beta}]=C_{\alpha\beta}^{\gamma}X_{\gamma}\,,$ (2)

in $C_{\alpha\beta}^{\gamma}$, which are called the structure constants. The
equations mean that the operators span a Lie algebra $L_{r}$ of the finite
dimension $r$. The number $m$ of necessary particular solutions is estimated
by $nm\geq r$.

The linear space (2) is called Vessiot-Guldberg-Lie algebra to honor the
memory of pioneers. Significant efforts were invested in classifying all
systems with nonlinear superposition property, but up to now, only
realizations of small dimensions like $3$ and $4$ have been obtained [6, 7].

However, the actual point of how to check the conditions of the theorem was
missing. In this paper, we will derive an algorithm for verifying the
condition of closeness for the important case of polynomially nonlinear
$\xi^{i}_{k}(\textbf{x})$ functions. It is based on the theory of Newton
polytopes and represents a constructive procedure to verify – by a finite
amount of steps – if the Lie algebra is finite or not. Such a verification
requires a huge amount of symbolic algebraic computations and is only possible
to do using a computer algebra system. The general logic here is similar to a
previous ISSAC paper [8] where linearizability criteria were derived. However,
we use a completely different algebraic technique.

Figure 1: Illustration of the exact (blue curve) and the numerical (red
rhombi) solution of the Ricatti equation with coefficients (6).

##  3 Related Work

There is a burgeoning interest in symbolic computation in disciplines such as
bioinformatics [9] and biochemistry [10]. Preprocessing of the differential
systems is beneficial from a numerical perspective as recent work has shown
the transformation of polynomial dynamical systems into quadratic ones [11],
and exact hierarchical reductions to smaller and more tractable blocks by
linear transformations [12]. Classical computer algebra achievements such as
the Rosenfeld-Gröbner algorithm [13] and the Differential Thomas Decomposition
[14, 15] are ubiquitously used now for the symbolic analysis of differential
equations. It started from basic tasks in classical mathematical physics for
partial differential systems like constructing all compatibility conditions,
detecting the inconsistency of the system, deriving degrees of freedom in the
general solution, and determining the coefficients of a power series solution.
The general work in this direction is within the scope of Hilbert’s Program
for the algebraization of mathematics.

The work of Sophus Lie on group analysis of differential equations was
continued in the 20th and 21st centuries by Lev Ovsyannikov and his multiple
followers, who applied Lie’s method for the large-scale integration of
differential equations that arose in practice. There has been recent interest
in theoretical studies of the nonlinear superposition principle. E.g.,
Gainetdinova et al. generalized the superposition theorem for systems of two
second-order ODEs admitting four-dimensional Lie algebras [16]. Carinena et
al. investigated an important class of constrained systems on Dirac manifolds,
more precisely called Dirac-Lie systems, which also preserve the Hamiltonian
structure and superposition rule [17]. Moreover, Ballesteros et al. [18]
studied Lie-Hamiltonian systems endowed with the Poisson–Hopf deformation
formalism, which extends nonlinear superposition theory to quantum
mathematical physics.

##  4 Riccati Equation

The Riccati equation can be considered as the simplest example which admits a
nonlinear superposition property

$\frac{dx}{dt}=a_{0}(t)+a_{1}(t)x+a_{2}(t)x^{2}\,,$ (3)

so that any solution of it could be represented as a rational function of
three known solutions $x_{i}(t),i=1,\dots,4$ and a single constant $C$:

$x(t)=\frac{C(\mathit{x_{1}}\mathit{x_{3}}-\mathit{x_{2}}\mathit{x_{3}})+\mathit{x_{1}}\mathit{x_{3}}-\mathit{x_{1}}\mathit{x_{2}}}{C(\mathit{x_{1}}-\mathit{x_{2}})+\mathit{x_{3}}-\mathit{x_{2}}}\,.$

The superposition rule is equivalent to the symmetric property that the
subharmonic ratio of four solutions remains the same for all $t$:

$\frac{x_{4}-x_{1}}{x_{1}-x_{2}}:\frac{x_{4}-x_{3}}{x_{2}-x_{3}}=C\,.$ (4)

The simple forward Euler scheme

$\frac{x_{n+1}-x_{n}}{h}=a_{0}(t_{n})+a_{1}(t_{n})x_{n}+a_{2}(t_{n})x_{n}^{2}\,,$

where $t_{n+1}=t_{n}+h$, according to a general logic of numerical methods,
converges on intervals without singularities. However, it does not satisfy
property (4), and when approaching the infinity point $x(t)\rightarrow\infty$,
the solution crashes.

In contrast, the slightly modified version – the partially implicit Euler
scheme

$\frac{x_{n+1}-x_{n}}{h}=a_{0}(t_{n})+a_{1}(t_{n})x_{n}+a_{2}(t_{n})x_{n}x_{n+1}$
(5)

satisfies property (4), and the solution can cross singularity points without
an excessive error accumulation.

For example, let us consider in (3),

$a_{2}(t)=\frac{1}{t},\,\,\,\,a_{1}(t)=1,\,\,\,\,a_{0}(t)=0\,.$ (6)

The general solution is given by means of exponential integrals222The function
is not elementary as shown by applying the Risch algorithm [19].

$x(t)=(Ei(1,-t)+C)^{-1}{e^{t}}\,,$

where

$Ei(a,z)=\int_{1}^{\infty}e^{-\tau z}\tau^{-a}d\tau\,.$

The solution of the Cauchy problem (3) with initial condition $x(1)=~{}1$ is
illustrated in Figure 1 in which the blue curve corresponds to the exact
solution and the red rhombi represent the numerical solution obtained from the
finite-difference scheme (5).

In the next section, we consider the important class of nonlinear dynamical
systems of the form (1) where

$\xi^{i}_{k}(x)=\sum_{m=0}^{N}a_{m}(i,k)x^{m}$

are multivariate polynomials of dependent variables. In this case, we can say
if the corresponding set of differential operators forms a Lie algebra or if
it does not admit finite closure by means of a Lie bracket.

##  5 Algorithmics

This section introduces the primary mathematical entities we work with, along
with the corresponding algorithms. The main object of consideration here are
polynomial vector fields and their associated first-order differential
operators:

$X=f_{1}\frac{\partial}{\partial x_{1}}+\dots+f_{n}\frac{\partial}{\partial
x_{n}}\,,$

where $f_{i}=f_{i}(x_{1},x_{2},\dots,x_{n})$ – polynomial function of all
variables. The goal here is to understand if a finite set of operators

$\\{X_{1},X_{2},\dots,X_{m}\\}$

is closed under the Lie bracket or not. We will start from the scalar case
when the dependent variable is only a single one.

###  5.1 One-dimensional Case

The one-dimensional case is not difficult to investigate, but at the same
time, it provides an idea for the general case.

Let $X_{1},\dots,X_{r},$ be operators, where $r>1.$ For each $i$, we denote
$X_{i}=~{}f_{i}\frac{\partial}{\partial x}.$ We define the degree of operators
as $deg(X_{i}):=deg(f_{i})$.

The algorithm for checking nonlinear superposition is given by the following
steps.

  1. 1.

Check degrees of the polynomials $\\{f_{i}\\}.$ If there are two polynomials
$g$ and $h$ of different degrees which are greater or equal to 2, then algebra
is infinite-dimensional. Otherwise, go to (2).

  2. 2.

Compute all pairwise commutators. Check the dimensions in the vector space
spanned by $\\{x^{k}\\}_{k=0}^{\infty}$:

     * •

If $dim(\langle f_{i},[f_{j},f_{k}]\rangle)=dim(\langle f_{i}\rangle),$ then
the algebra is finite-dimensional.

     * •

Otherwise go to (1) with the set $\\{f_{i},[f_{j},f_{k}]\\}$.

The algorithm always stops working due to the criterion.

######  Theorem 5.1.

The algebra $\mathcal{A}$ spanned by $\\{X_{i}\\}$ where
$X_{i}=f_{i}\frac{\partial}{\partial x}$ is infinite-dimensional if and only
if, after adding all pairwise commutators a finite number of times, there will
be two polynomials $g$ and $h$ of different degrees which are greater or equal
to 2.

######  Proof 5.2.

Firstly, observe that $\mathcal{A}$ is infinite-dimensional if and only if
$\forall\;C>0\;\exists\;X=f\frac{\partial}{\partial x}\in\mathcal{A}$ such
that $deg(f)>C.$ Therefore, sufficiency of the condition follows from the fact
that the commutator of operators of degrees $d_{1},d_{2}$ where $d_{1}\neq
d_{2},$ has degree $d_{1}+d_{2}-1.$ The condition is necessary as well since
in the infinite-dimensional algebra, there always exist two operators of
different degrees which are greater or equal to 2.

###  5.2 General Case

The general case is treated in the same manner. The analog of polynomials from
the previous section is Newton polytope.

We start with convenient notations. To a vector $(y_{1},\dots,y_{d})$
corresponds a linear vector field $Y=y_{1}D_{1}+\dots+y_{d}D_{d},$ where
$D_{k}=x_{k}\frac{\partial}{\partial x_{k}}.$

Any operator $X$ can be written as a Laurent polynomial, whose coefficients
are linear vector fields

$X=\sum_{n\in\mathbb{Z}^{d}}x^{n}X(n)\,,$

where $x^{n}=x_{1}^{n_{1}}\dots
x_{d}^{n_{d}},\,X(n)=\sum\limits_{i=1}^{d}X_{n,i}D_{i}.$ We call
$(X_{n,1},\dots,X_{n,d})$ the vector corresponding to $n.$ Observe that
$X(n)\neq 0$ only for a finite number of $n\in\mathbb{Z}^{d}.$ Thus, for a
given operator $X$, we can construct a convex polytope

$N_{X}=Conv\\{n\>|\>X(n)\neq 0\\}\,,$

which is called a Newton polytope.

Let again $X_{1},\dots,X_{r}$ be operators, where $r>1,$ and
$N_{X_{1}},\dots,N_{X_{r}}$ are the corresponding polytopes. The algorithm for
checking nonlinear superposition is given by the following steps.

  1. 1.

Check the vertices of polytopes $\\{N_{X_{k}}\\}$. If there are two vertices
$v\in vert(N_{X_{i}})$ and $u\in vert(N_{X_{j}})$, $i\neq j$, with
corresponding vectors $V$ and $U$ such that all five conditions

     * •

$|v+u|>max(|v|,|u|)$ ,

     * •

$v+u$ is the vertex of $N_{X_{i}}+N_{X_{j}}$ (Minkowski sum) ,

     * •

$(u\cdot V)U-(v\cdot U)V\neq 0$, with dot product $(\cdot)$ ,

     * •

if $(u\cdot V)=0$ then $\forall m\in\mathbb{N}_{\geq 1}\;(v+mu,U)\neq 0$ ,

     * •

if $(v\cdot U)=0$ then $\forall m\in\mathbb{N}_{\geq 1}\;(mv+u,V)\neq 0$ ,

are satisfied, then the algebra is infinite-dimensional.

  2. 2.

Compute all pairwise commutators and check dimensions:

     * •

If
$dim(\langle\Xi_{X_{\alpha}}\rangle)=dim(\langle\Xi_{X_{\alpha}},\Xi_{[X_{\beta},X_{\gamma}]}\rangle),$
then the algebra is finite-dimensional.

     * •

Otherwise go to (1) with operator set
$\\{X_{\alpha},[X_{\beta},X_{\gamma}]\\}$.

The algorithm always terminates due to the following criterion.

######  Theorem 5.3.

Algebra $\mathcal{A}$ spanned by $\\{X_{\alpha}\\}$ where
$X_{\alpha}=\sum\limits_{i=1}^{d}f_{\alpha,i}\frac{\partial}{\partial x_{i}}$
is infinite-dimensional if and only if, after adding all pairwise commutators
a finite number of times, there will be two vertices $v\in
vert(N_{X_{i}}),u\in vert(N_{X_{j}})$, $i\neq j$, with corresponding vectors
$V$ and $U$ such that all following five conditions are satisfied:

  1. (i)

$|v+u|>max(|v|,|u|)$ ,

  2. (ii)

$v+u$ is the vertex of $N_{X_{i}}+N_{X_{j}}$ (Minkowski sum) ,

  3. (iii)

$(u\cdot V)U-(v\cdot U)V\neq 0$, with dot product $(\cdot)$ ,

  4. (iv)

if $(u\cdot V)=0$ then $\forall m\in\mathbb{N}_{\geq 1}\;(v+mu,U)\neq 0$ ,

  5. (v)

if $(v\cdot U)=0$ then $\forall m\in\mathbb{N}_{\geq 1}\;(mv+u,V)\neq 0$ .

######  Proof 5.4.

Firstly, observe that $\mathcal{A}$ is infinite-dimensional if and only if
$\forall\;C>0\;\exists\;X=\sum\limits_{i=1}^{d}f_{i}\frac{\partial}{\partial
x_{i}}\in\mathcal{A}$ such that

$max(\\{|v|:v\in vert(N_{X})\\})>C\,.$

Sufficiency. Suppose $a$ and $b$ are vertices satisfying the conditions
(i)-(v). Please note, that

$[x^{v}V,x^{u}U]=x^{v+u}(u\cdot V)U-(v\cdot U)V)\,.$

With $K_{u,v}=(u\cdot V)U-(v\cdot U)V$, it follows that

$\displaystyle N_{[X,Y]}\supset Conv\\{$ $\displaystyle
v+u\>|v\in\,vert(X),\,u\in vert(Y)\,,$ $\displaystyle v+u\in
vert(X+Y),\,K_{u,v}\neq 0\\}\,.$

Thus, it is easy to deduce that either the set $\\{|a+mb|\\}_{m\geq C_{1}}$ or
$\\{|ma+b|\\}_{m\geq C_{2}}$ is a desired increasing unbounded sequence, where
$C_{1},C_{2}\in\mathbb{N}$ are constants.

Necessity. In the infinite-dimensional algebra, there always exists a pair
satisfying the conditions (i)-(v).

##  6 Implementation

At the core of our algorithms is the symbolic manipulation with Newton
polytopes. We use the Maple-based Convex library [20] for these purposes. It
was developed by Franz based on the theory of Kushnirenko’s bound for the sum
of the Milnor numbers of the complex polynomial singularities [21]. To our
knowledge, it is the most efficient library for symbolic tasks in convex
geometry.

Check Superposition: Dimension 1 ($operators$)

0: $operators$, list of polynomial vector fields

0: True, if it is closed under Lie bracket, $\tt False$, otherwise

1: $dim:=$DimLinSpace $($LieAlgebra ($operators$));

2: $polys:=$ExtractPolynomials ($operators$);

3: while True do

4: $degrees:=convert(map(degree,polys),set)$;

5: $m_{1}:=max(degrees)$;

6: $m_{2}:=max(degrees\setminus\\{max(degrees)\\})$;

7: if $(m_{1}>1)\wedge(m_{2}>1)$ then

8: return False;

9: else

10: $operators:=$AddPairwiseCommutators ($operators$);

11: if DimLinSpace $($LieAlgebra ($operators$)) $>dim$ then

12: $dim:=dim($DimLinSpace $($LieAlgebra ($operators$));

13: else

14: return True;

15: fi

16: fi

17: od

Check Superposition: General Case ($operators$)

0: $operators$, list of polynomial vector fields

0: True, if it is closed under Lie bracket, $\tt False$, otherwise

1: $dim:=$DimLinSpace $($LieAlgebra ($operators$));

2: $polys:=$ExtractPolynomials ($operators$);

3: $polytopes:=$NewtonPolytopes ($operators$);

4: $cycle:=true$

5: while cycle do

6: for $k=1$ to $numelems(polytopes)$ do

7: for $l=1$ to $numelems(polytopes)$ do

8: if $k>l$ then

9: for $a\in vertices(polytopes[k])$ do

10: for $b\in vertices(polytopes[k])$ do

11: $c:=a+b$;

12: $v_{a}:=$GetCoeffs $(a)$;

13: $v_{b}:=$GetCoeffs $(b)$;

14: $v_{c}:=$DotProduct $(b,v_{a})v_{b}-$DotProduct $(a,v_{b})v_{a}$;

15: $s_{1}:=0$;

16: $s_{2}:=0$;

17: if DotProduct $(b,v_{a})=0$ then

18: if DotProduct $(b,v_{b})\neq 0$ then

19: $s_{1}:=$DotProduct $(a,v_{b})/$DotProduct $(b,v_{b})$;

20: fi

21: fi

22: if DotProduct $(a,v_{b})=0$ then

23: if DotProduct $(a,v_{a})\neq 0$ then

24: $s_{2}:=$DotProduct $(b,v_{a})/$DotProduct $(a,v_{a})$;

25: fi

26: fi

27: if $|c|>max(|a|,|b|)\wedge$$c\in vertices($MinSum
$(polytopes[k],polytopes[l])$$\wedge|v_{c}|\neq
0\wedge(type(s_{1},integer)=false\vee 0\leq
s_{1})\wedge$$(type(s_{2},integer)=false\vee 0\leq s_{2})$ then

28: return False;

29: fi

30: od

31: od

32: fi

33: od

34: od

35: $operators:=$AddPairwiseCommutators ($operators$);

36: if DimLinSpace $($LieAlgebra ($operators$)) $>dim$ then

37: $dim:=dim($DimLinSpace $($LieAlgebra ($operators$));

38: else

39: return True;

40: fi

41: od

The implementations of our two algorithms – for the one-dimensional and for
the general case – are available on
GitHub.333https://github.com/treverona/nonlinear-superposition

##  7 Non-trivial Example

In order to construct an example, we use a simple trick: The Symmetry algebra
of an ODE is finite-dimensional if differential order $n\geq 2$ and it is
obviously closed under the Lie bracket. We consider the following system with
variables $u(w)$ and $v(w)$:

$\frac{du}{dw}=v,\frac{d^{2}v}{dw^{2}}=0\,.$

The Lie symmetry algebra is defined by infinitesimal generators:

$X:=\eta_{u}(w,u,v))\frac{\partial}{\partial
u}+\eta_{v}(w,u,v))\frac{\partial}{\partial
v}+\xi_{w}(w,u,v))\frac{\partial}{\partial w}\,.$

As linear space it has the dimension $10$ and consists of the following
operators:

$\displaystyle\eta_{u}(w,u,v))=\frac{1}{2}\left(C_{2}v^{2}+C_{1}\right)w^{2}+\frac{1}{2}\left(C_{4}v^{2}+2C_{3}u+2C_{6}\right)w-$
$\displaystyle-2C_{2}u^{2}+\frac{1}{2}\left(2C_{8}+2C_{5}\right)u+\frac{1}{2}C_{7}v^{2}+C_{10}\,,$
$\displaystyle\eta_{v}(w,u,v))=C_{2}v^{2}w+C_{1}w-2C_{2}uv+C_{3}u+\frac{1}{2}C_{4}v^{2}+C_{5}v+C_{6}\,,$
$\displaystyle\xi_{w}(w,u,v))=\frac{1}{2}(2C_{2}v+C_{3})w^{2}+(-2C_{2}u+C_{4}v+C_{8})w-C_{4}u+C_{7}v+C_{9}\,.$

The extraction of the two-dimensional Lie subalgebra leads to

$\displaystyle\frac{d}{dt}u(t)$
$\displaystyle=\mathit{C_{1}}(t)\left(\frac{v(t)^{2}w(t)^{2}}{2}-2u(t)^{2}\right)+\mathit{C_{2}}(t)u(t)w(t)\,,$
$\displaystyle\frac{d}{dt}v(t)$
$\displaystyle=\mathit{C_{1}}(t)\left(\frac{v(t)^{2}w(t)}{2}-2u(t)v(t)\right)+\mathit{C_{2}}(t)u(t)\,,$
$\displaystyle\frac{d}{dt}w(t)$
$\displaystyle=\mathit{C_{1}}(t)\left(\frac{v(t)w(t)^{2}}{2}-2u(t)w(t)\right)+\mathit{C_{2}}(t)\frac{w(t)^{2}}{2}\,.$

##  8 Difference Thomas Decomposition

The construction of numerical schemes is a challenging topic in mathematical
modeling of natural phenomena [22]. From a naive point of view, all Cauchy
problems for first-order ODE systems are covered by a basic theorem of
Leonhard Euler, which is simple to use because of its explicit character.

######  Theorem 8.1.

([23], pp. 6.3.3) Let us suppose a first-order differential system

$\frac{dx}{dt}=f(x,t)$

with initial value $x(t_{0})=x_{0}$, and smooth right-hand side $f$. The
unique solution $x(t),\,t\in(a,b)$ defined by the Cauchy problem could be
approximated by an explicit scheme

$\tilde{x}_{n+1}-\tilde{x}_{n}=hf(x_{n},t_{n})\,,$

and it converges for $x_{n}\rightarrow x(t)$ in $||\cdot||_{\infty}$ if
$|x(t)|<\infty,\,t\in~{}(a,b)$.

In practice, it is required to apply very small time steps using explicit
methods. Including the fact that numerical computations are carried out with
floating-point arithmetic – after a lot of steps – a significant accumulation
of errors occurs. That is why the explicit Euler method becomes unpractical,
and to handle robust computation, it is important to care about the geometric
property of the solution, such as symplecticity, and physical properties, such
as conservation laws. Informally speaking, the general rule is to preserve as
many properties as possible at a numerical level.

On the other hand, linearity is the most important property of differential
equations, and for linear equations, without even thinking about it, we
usually construct a linear finite-difference scheme. Remarkably, nonlinear
superposition plays almost the same role for differential equations, which
makes it the first property that we would like to preserve when we solve the
problem numerically (as clearly seen in Section 4).

The construction of numerical schemes can benefit greatly from the analog of
differential the Thomas decomposition [15] adopted for difference equations.
Potentially, for a finite-difference scheme with undefined parameters and
known superposition rule (like the subharmonic ratio in 4), it will yield a
desirable scheme or show that it is not possible to obtain it. There is
ongoing research in the field based on the algebraic Thomas decomposition and
specific properties of differences ideals [24, 25]. It gives hope that
progress in the field will lead to an opportunity to construct numerical
schemes with advanced properties.

##  9 Matrix Ricatti Equation

Scalar Ricatti equations admit wonderful generalizations to matrix
ones444Certain authors employ the phrase “multidimensional Riccati equation”
to encompass all quadratic equations, whereas we prefer to reserve the term
“Riccati” specifically for those equations that retain the nonlinear
superposition property., which is worth to mention in our manuscript [26]:

$\frac{dW}{dt}=A(t)+B(t)W+WC(t)+WD(t)W\,,$ (7)

where $W$ is an $(n\times k)$-matrix with arbitrary $n,k\in\mathbb{N}$ and
$A,B,C,D$ are matrices of appropriate dimensions.

The beautiful result that a two-parameter class of operators $U_{q,h}$ with

$U_{q,h}f(t)=\begin{cases}f^{\prime}(t)\,,&\text{if }q=1\,,h=0\,,\\\
\frac{f(qt+h)-f(t)}{(q-1)t+h}\,,&\text{else}\,.\end{cases}$

defines the difference analog of the Ricatti equation, which admits the
superposition formula

$U_{q,h}w(t)=a(t)+b(t)w(t)+w(qt+h)c(t)+w(qt+h)d(t)w(t)\,,$

and in particular for the case $q=1$ and the limit case $h\rightarrow 0$, it
converges to the differential matrix Ricatti equation. We will show that in
addition to nonlinear superposition, it is possible to construct a scheme that
is also strongly consistent [27, 28].

Let us briefly remind the definition of strong consistency. We consider
polynomially nonlinear ordinary (partial) differential equation systems of the
form

$f_{1}=\dots=f_{p}=0,\quad F:=\\{f_{1},\ldots,f_{p}\\}\subset{\mathcal{R}}\,,$
(8)

where $f_{1},\ldots,f_{p}$ are elements of the differential polynomial ring

${\mathcal{R}}:={\mathbb{K}}[t^{1},\ldots,t^{m}]$

over a differential coefficient field ${\mathbb{K}}$. The differential
polynomial ring ${\mathcal{R}}$ contains polynomials in the dependent
variables

$\mathbf{w}:=\\{w^{1},\ldots,w^{n}\\}$

and their partial derivatives $\partial_{x_{1}},\ldots,\partial_{x_{n}}$.

The coefficients on the grid are elements of the difference field with
mutually commuting difference operators $\\{\sigma_{1},\ldots,\sigma_{n}\\}$
acting on a function $\phi(\mathbf{x})$ as follows:

$\sigma_{i}\circ\phi(x_{1},\ldots,x_{n})=\phi(x_{1},\ldots,x_{i}+h_{i},\ldots,x_{n})\,,\quad\,h_{i}>0\,.$

We refer to $\sigma_{i}$ also as shift operators. Analogously, we define
$\tilde{\mathcal{R}}$ as a difference polynomial ring.

######  Definition 9.1.

We shall say that a difference equation $\tilde{f}(\mathbf{u})=0$ defined on
the orthogonal and uniform grid with the grid spacing set
$\mathbf{h}:=(h_{1},\ldots,h_{n})$ implies the differential equation
$f(\mathbf{u})=0$ and write $\tilde{f}\rhd f$ if the Taylor expansion about a
grid point yields

$\tilde{f}(\mathbf{u})\xrightarrow[h_{i}\rightarrow
0]{}f(\mathbf{u})+O(\mathbf{h})\,,$

where $O(\mathbf{h})$ denotes terms that reduce to zero when $h_{i}\rightarrow
0$ for $i=1,\ldots,n$.

In the theory of strongly consistence finite-difference approximations, it is
important to consider perfect difference ideals.

######  Definition 9.2.

[29] A perfect difference ideal generated by a set
$\tilde{F}\in\tilde{\mathcal{R}}$ and denoted by
$\llbracket\tilde{F}\rrbracket$ is the smallest difference ideal containing
$\tilde{F}$ and such that for any $\tilde{f}\in{\mathcal{R}}$,
$\theta_{1},\ldots,\theta_{r}\in\Theta$ and
$k_{1},\ldots,k_{r}\in\mathbb{N}_{\geq 0}$:

$(\theta_{1}\circ\tilde{f})^{k_{1}}\dots(\theta_{r}\circ\tilde{f})^{k_{r}}\in\llbracket\tilde{F}\rrbracket\Longrightarrow\tilde{f}\in\llbracket\tilde{F}\rrbracket\,.$

In the context of difference algebra, perfect ideals play the same role as
radical ideals in differential algebra. The clarity of this fact becomes
evident when examining the difference analogue of the Nullstellensatz [30].
For this reason, we will contemplate the perfect ideal
$\llbracket\tilde{F}\rrbracket$ generated by the difference polynomials in the
finite-difference approximation as the set of its difference-algebraic
consequences. Respectively, the set of differential-algebraic consequences of
a differential system is the radical differential ideal generated by the set
$F$ in (8).

######  Definition 9.3.

[24] A finite-difference approximation to a differential system (8) is
strongly consistent if

$(\,\forall\tilde{f}\in\llbracket\tilde{F}\rrbracket\,)\ (\,\exists
f\in\llbracket F\rrbracket\,)\ [\,\tilde{f}\rhd f\,]\,.$

Now, let us consider the square matrix case ($k=n$). Based on the operator
$U_{q,h}$, we can construct a finite-difference scheme with desired
properties.

######  Theorem 9.4.

The finite difference numerical scheme

$\frac{W(t_{n+1})-W(t_{n})}{h}=A(t_{n})+B(t_{n})W(t_{n})+W(t_{n+1})(C(t_{n})+D(t_{n})W(t_{n}))\,,$
(9)

where $t_{n+1}=t_{n}+h$ with time step $h$, satisfies the three properties:

  * •

$W(t_{n})\rightarrow W(t_{n+1})$ is an invertible linear mapping ;

  * •

difference solution admits nonlinear superposition formula ;

  * •

as a numerical difference scheme, it is strongly consistent .

######  Proof 9.5.

The explicit solution is given by formula

$W(t_{n+1})=(I-hC(t_{n})-hD(t_{n})W(t_{n}))^{-1}(W(t_{n})(I+hB(t_{n}))+hA(t_{n}))\,,$

where the invertible matrix always exists for moderately small $h>0$. For more
details, we refer to the original paper [26]. Let us suppose it is not
strongly consistent. Then, there exists an algebraic consequence of the
difference matrix system (9) which in the limit of $h\rightarrow 0$ leads to
the differential polynomial $S$ that is not lying in the radical of the
differential ideal generated by the differential system of the matrix Ricatti
equation (7). As it is not in the radical, we can find the solution
$\tilde{W}$ of the differential system which does not satisfy $S$. System (7)
is a well-posed Cauchy problem, so that every solution could be encoded by its
initial value at some point (e.g., $\tilde{W}(t_{0})=W_{1}$). In the
difference setting, we can also find a solution with initial value $W_{1}$ at
point $t_{0}$ which will converge to $\tilde{W}$ when $h\rightarrow 0$ by an
analog of Theorem 8.1 (generalization to implicit and semi-explicit schemes)
which immediately implies a contradiction as it should satisfies $S$.

##  10 Generalization and Open Questions

Our approach raises questions for several natural generalizations. Firstly, it
is interesting to consider monomials on the right-hand side, which allow to
have negative integer exponents. If functions $\xi^{i}_{k}(x)$ are represented
as power series in the form of computable coefficients, is it still possible
to decide algorithmically when the set is closed under the Lie bracket?

As we observe, the numerical scheme (5) even outperforms the one obtained from
Theorem 8.1 because it can cross the singularity points without an excessive
accumulation of errors. It shows the importance of studying numerical schemes
which preserve the property of nonlinear superposition.

Open problem: There are several ways how to transform a polynomial ODE system
into a quadratic one by introducing new variables [11, 31]. Is it possible to
transform a polynomial system into a Ricatti matrix system defined by (7)?

##  11 Conclusion

This contribution is devoted to the application of the theory of Newton
polytopes for the verification of nonlinear superposition of first-order
differential systems. Our viewpoint is that the presented methods assisted by
computer algebra will be helpful for the construction and evaluation of
appropriate discretizations of differential equations that appear in the
applied sciences.

Also, we would like to emphasize that a lot of effort was invested into the
field of Lie Algebras to classify all of them for some fixed dimension [32].
Typically, such kind of work involves the compilation of tables that describe
all possible cases up to isomorphisms [6, 7]. We truly believe that the
development of symbolic algorithms provides the opportunity to extend powerful
Lie formalism to a bigger audience.

Significant recent advancements in geometry [33] demonstrate the effectiveness
of machine learning as a tool for autonomously solving olympiad geometry
problems. This underscores the significance of advancing symbolic analysis
tools, which can serve as foundational components for future machine learning-
driven automatic reasoning in algebra.

We conclude by anticipating that our approach will facilitate meaningful
discussions and inspire productive future research endeavors.

## Acknowledgments

We wish to honor the memory of Vladimir P. Gerdt, a real enthusiast for
employing computer algebra in solving differential equations, with a
particular emphasis on preserving their algebraic properties at a numerical
level. This work has been partially supported by the baseline funding of the
KAUST Computational Sciences Group. Veronika Treumova acknowledges KAUST
support and hospitality during her research stay at KAUST.

## References

  * [1] Yan Li, Xiazhi Hao, Ruoxia Yao, Yarong Xia, and Yali Shen.  Nonlinear superposition among lump soliton, stripe solitons and other nonlinear localized waves of the (2+1)-dimensional cpkp-bkp equation.  Mathematics and Computers in Simulation, 208:57–70, 2023.
  * [2] Angelo Bassi, Kinjalk Lochan, Seema Satin, Tejinder P Singh, and Hendrik Ulbricht.  Models of wave-function collapse, underlying theories, and experimental tests.  Reviews of Modern Physics, 85(2):471, 2013.
  * [3] Nils Ackermann.  A nonlinear superposition principle and multibump solutions of periodic schrödinger equations.  Journal of Functional Analysis, 234(2):277–320, 2006.
  * [4] Colin Rogers and Boris Malomed.  On madelung systems in nonlinear optics: A reciprocal invariance.  Journal of Mathematical Physics, 59(5), 2018.
  * [5] Sophus Lie.  Allgemeine untersuchungen über differentialgleichungen, die eine continuirliche, endliche gruppe gestatten.  Mathematische Annalen, 25(1):71–151, 1885.
  * [6] Nail H Ibragimov and AA Gainetdinova.  Three-dimensional dynamical systems admitting nonlinear superposition with three-dimensional vessiot-guldberg-lie algebras.  Applied Mathematics Letters, 52:126–131, 2016.
  * [7] NH Ibragimov and AA Gainetdinova.  Classification and integration of four-dimensional dynamical systems admitting non-linear superposition.  International Journal of Non-Linear Mechanics, 90:50–71, 2017.
  * [8] Dmitry A Lyakhov, Vladimir P Gerdt, and Dominik L Michels.  Algorithmic verification of linearizability for ordinary differential equations.  In Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation, pages 285–292, 2017.
  * [9] Erickson Fajiculay and Chao-Ping Hsu.  Biosans: A software package for symbolic and numeric biological simulation.  Plos one, 17(4):e0256409, 2022.
  * [10] François Boulier, François Fages, Ovidiu Radulescu, Satya Swarup Samal, Andreas Schuppert, Werner Seiler, Thomas Sturm, Sebastian Walcher, and Andreas Weber.  The symbiont project: symbolic methods for biological networks.  ACM Communications in Computer Algebra, 52(3):67–70, 2019.
  * [11] Andrey Bychkov and Gleb Pogudin.  Optimal monomial quadratization for ode systems.  ACM Communications in Computer Algebra, 54(3):119–123, 2021.
  * [12] Alexander Demin, Elizaveta Demitraki, and Gleb Pogudin.  Exact hierarchical reductions of dynamical models via linear transformations.  Communications in Nonlinear Science and Numerical Simulation, page 107816, 2024.
  * [13] François Boulier, Daniel Lazard, François Ollivier, and Michel Petitot.  Representation for the radical of a finitely generated differential ideal.  In Proceedings of the 1995 international symposium on Symbolic and algebraic computation, pages 158–166, 1995.
  * [14] Joseph Miller Thomas.  Differential systems, volume 21.  American Mathematical Soc., 1937.
  * [15] Thomas Bächler, Vladimir Gerdt, Markus Lange-Hegermann, and Daniel Robertz.  Algorithmic thomas decomposition of algebraic and differential systems.  Journal of Symbolic Computation, 47(10):1233–1266, 2012.
  * [16] AA Gainetdinova and RK Gazizov.  Integrability of systems of two second-order ordinary differential equations admitting four-dimensional lie algebras.  Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 473(2197):20160461, 2017.
  * [17] JF Carinena, Janusz Grabowski, J de Lucas, and Cristina Sardón.  Dirac–lie systems and schwarzian equations.  Journal of Differential Equations, 257(7):2303–2340, 2014.
  * [18] Angel Ballesteros, Rutwig Campoamor-Stursberg, Eduardo Fernández-Saiz, Francisco J Herranz, and Javier de Lucas.  Poisson–hopf deformations of lie–hamilton systems revisited: deformed superposition rules and applications to the oscillator algebra.  Journal of Physics A: Mathematical and Theoretical, 54(20):205202, 2021.
  * [19] Robert H Risch.  The problem of integration in finite terms.  Transactions of the American Mathematical Society, 139:167–189, 1969.
  * [20] Matthias Franz.  Convex—a maple package for convex geometry.  Available electronicly at https://www.math.uwo.ca/faculty/franz/convex/, 2016.
  * [21] Anatoli G Kouchnirenko.  Polyedres de newton et nombres de milnor.  Inventiones mathematicae, 32(1):1–31, 1976.
  * [22] James William Thomas.  Numerical partial differential equations: finite difference methods, volume 22.  Springer Science & Business Media, 2013.
  * [23] Randall J LeVeque.  Finite difference methods for ordinary and partial differential equations: steady-state and time-dependent problems.  SIAM, 2007.
  * [24] Vladimir P Gerdt and Daniel Robertz.  Algorithmic approach to strong consistency analysis of finite difference approximations to pde systems.  In Proceedings of the 2019 on International Symposium on Symbolic and Algebraic Computation, pages 163–170, 2019.
  * [25] Vladimir P Gerdt, Daniel Robertz, and Yuri A Blinkov.  Strong consistency and thomas decomposition of finite difference approximations to systems of partial differential equations.  arXiv preprint arXiv:2009.01731, 2020.
  * [26] Alexei V Penskoi and Pavel Winternitz.  Discrete matrix riccati equations with superposition formulas.  Journal of mathematical analysis and applications, 294(2):533–547, 2004.
  * [27] Yury A Blinkov, Vladimir P Gerdt, Dmitry A Lyakhov, and Dominik L Michels.  A strongly consistent finite difference scheme for steady stokes flow and its modified equations.  In Computer Algebra in Scientific Computing: 20th International Workshop, CASC 2018, Lille, France, September 17–21, 2018, Proceedings 20, pages 67–81. Springer, 2018.
  * [28] Dominik L Michels, VP Gerdt, Yu A Blinkov, and DA Lyakhov.  On the consistency analysis of finite difference approximations.  Journal of Mathematical Sciences, 240:665–677, 2019.
  * [29] Alexander Levin.  Difference algebra, volume 8.  Springer Science & Business Media, 2008.
  * [30] Dima Trushin.  Difference nullstellensatz in the case of finite group.  arXiv preprint arXiv:0908.3863, 2009.
  * [31] Edward H Kerner.  Universal formats for nonlinear ordinary differential systems.  Journal of Mathematical Physics, 22(7):1366–1371, 1981.
  * [32] Roman O Popovych, Vyacheslav M Boyko, Maryna O Nesterenko, and Maxim W Lutfullin.  Realizations of real low-dimensional lie algebras.  Journal of Physics A: Mathematical and General, 36(26):7337, 2003\.
  * [33] Trieu H Trinh, Yuhuai Wu, Quoc V Le, He He, and Thang Luong.  Solving olympiad geometry without human demonstrations.  Nature, 625(7995):476–482, 2024.

##  Appendix A Nonlinear superposition function

The problem that was not discussed in the main text of the manuscript is how
to find the superposition rule. This task could not be solved algorithmically
as it requires solving a system of partial differential equations. However, it
is still an interesting task from a symbolic point of view and requires proper
heuristics. We illustrate it with an example of the scalar Ricatti equation.
We need to prolong symmetry operators by adding their copies

$\displaystyle eq1:=\frac{\partial F}{\partial x}+\frac{\partial F}{\partial
x_{1}}+\frac{\partial F}{\partial x_{2}}+\frac{\partial F}{\partial
x_{3}}=0\,,$ $\displaystyle eq2:=x\frac{\partial F}{\partial
x}+x_{1}\frac{\partial F}{\partial x_{1}}+x_{2}\frac{\partial F}{\partial
x_{2}}+x_{3}\frac{\partial F}{\partial x_{3}}=0\,,$ $\displaystyle
eq3:=x^{2}\frac{\partial F}{\partial x}+x_{1}^{2}\frac{\partial F}{\partial
x_{1}}+x_{2}^{2}\frac{\partial F}{\partial x_{2}}+x_{3}^{2}\frac{\partial
F}{\partial x_{3}}=0\,.$

The built-in Maple command pdsolve cannot find any solution. However, if we
integrate only the first two equations, then it yields the solution

$F(x,x_{1},x_{2},x_{3})=F_{1}\left(\frac{-x+x_{2}}{x-x_{1}},\frac{-x+x_{3}}{x-x_{1}}\right)\,.$

The change of independent variables

$(x,x_{1},x_{2},x_{3})\mapsto(w,v,x_{2},x_{3})\,,$

where

$w=\frac{-x+x_{2}}{x-x_{1}},\,v=\frac{-x+x_{3}}{x-x_{1}}$

defines a local diffeomorphism almost everywhere because the Jacobi matrix

$\left[\begin{array}[]{cccc}\frac{\mathit{x_{1}}-\mathit{x_{2}}}{\left(x-\mathit{x_{1}}\right)^{2}}&\frac{-x+\mathit{x_{2}}}{\left(x-\mathit{x_{1}}\right)^{2}}&\frac{1}{x-\mathit{x_{1}}}&0\\\
\frac{\mathit{x_{1}}-\mathit{x_{3}}}{\left(x-\mathit{x_{1}}\right)^{2}}&\frac{-x+\mathit{x_{3}}}{\left(x-\mathit{x_{1}}\right)^{2}}&0&\frac{1}{x-\mathit{x_{1}}}\\\
0&0&1&0\\\ 0&0&0&1\end{array}\right]$

has a non-zero determinant (except for the set of zero measure),

$\frac{\mathit{x_{2}}-\mathit{x_{3}}}{\left(x-\mathit{x_{1}}\right)^{3}}\neq
0\,.$

In new variables, the remaining equation $eq3$ could be rewritten as

$\left(w+1\right)w\left(\frac{\partial}{\partial
w}\mathit{F_{1}}\\!\left(w,v\right)\right)+\left(v+1\right)v\left(\frac{\partial}{\partial
v}\mathit{F_{1}}\\!\left(w,v\right)\right)=0\,,$

which could be easily be integrated as

$\mathit{F_{1}}\\!\left(w,v\right)=\mathit{F_{2}}\\!\left(-\frac{v-w}{v\left(w+1\right)}\right)\,.$

Substituting $w$ and $v$ via $x_{1},x_{2},x_{3},x$ and assuming $x=x_{4}$, we
immediately obtain (4). The general problem of constructing a superposition
rule is out of scope for this paper, but we find it interesting as an applied
problem in symbolic computation. Generally speaking, the nonlinear
superposition should not distinguish which is the first and which is the
second solution. Hence, it is required to construct a solution that is also a
symmetric function of its variables.