# Attack on Unfair ToS Clause Detection: A Case Study using Universal
Adversarial Triggers

Shanshan Xu  Irina Broda  Rashid Haddad
Marco Negrini Matthias Grabmair
School of Computation, Information, and Technology; Technical University of
Munich, Germany
<EMAIL_ADDRESS>

###### Abstract

Recent work has demonstrated that natural language processing techniques can
support consumer protection by automatically detecting unfair clauses in the
Terms of Service (ToS) Agreement. This work demonstrates that transformer-
based ToS analysis systems are vulnerable to adversarial attacks. We conduct
experiments attacking an unfair-clause detector with universal adversarial
triggers. Experiments show that a minor perturbation of the text can
considerably reduce the detection performance. Moreover, to measure the
detectability of the triggers, we conduct a detailed human evaluation study by
collecting both answer accuracy and response time from the participants. The
results show that the naturalness of the triggers remains key to tricking
readers.

##  1 Introduction

When using online platforms, users are asked to agree to the Terms of Service
(ToS), which are often long and difficult to understand. According to Obar and
Oeldorf-Hirsch (2020), it would take a user around 45 minutes on average to
read a ToS properly. Most users accept the terms without reading them,
including clauses which would be deemed unfair under consumer protection
standards. Software applications that warn consumers about unfair clauses can
support consumers’ rights, and have been the subject of prior work (e.g.,
Lippi et al., 2019; Ruggeri et al., 2022). At the same time, their existence
forms an incentive for drafters of ToS to formulate clauses with potentially
unfair effects that bypass automated screening. In turn, developers of control
systems seek to make their detectors robust against such ‘adversarial
attacks’. In this paper, we report on an experiment in discovering weaknesses
of ToS analysis models.
Natural language processing (NLP) models for ToS analysis conduct binary
classification of a given clause as fair/unfair. Previous studies have shown
that state-of-the-art transformer-based classifiers are vulnerable to
adversarial attacks Belinkov and Bisk (2017); even slight modifications to the
input text (e.g., changing a few characters) can cause incorrect
classifications Ebrahimi et al. (2018). Numerous adversarial attack methods
have been developed and demonstrate effective attack performance in various
downstream NLP tasks such as sentiment analysis Iyyer et al. (2018), question
answering Wang et al. (2020), machine-translation Cheng et al. (2019) etc. One
such method is the attack via a universal adversarial trigger, which is a
sequence of tokens (words, sub-words, or characters) that can be injected into
any text input from a dataset to mislead the victim model to a target
prediction (see Table 1 for examples). These input-agnostic triggers, once
generated, can be distributed to anyone, and do not need access to the victim
model at the time of attack.
Adversarial attacks have, to the best of our knowledge, remained largely
unaddressed in legal NLP. Our work extends the state of the art through the
following contributions: (1) We conduct experiments attacking ToS unfair
clause detectors trained on the public CLAUDETTE dataset with universal
adversarial triggers. Our results show that a minor perturbation of the text
can reduce the detection performance of transformer based models
significantly. (2) We also use artifacts from the training data for universal
trigger attacks. Our experiments demonstrate that such words can considerably
reduce the victim model’s accuracy, highlighting the potential threat of
training data leakage. (3) We conduct a human evaluation study to measure the
detectability of the generated triggers. The results show that suppressing sub
tokens can make generated triggers more difficult to detect. 111Our code is
available at https://github.com/TUMLegalTech/ToS_attack_nllp22

ToS Clause (red = trigger) | Model Detection
---|---
| Pinterest isn’t liable for damages that result from a may vote against non-
material
---
breach of any other applicable duty of care.
Unfair $\rightarrow$ Fair
| The English courts will have jurisdiction over any claim arising from may
vote
---
against, or related to , any use of our services.
Unfair $\rightarrow$ Fair
Table 1: The universal adversarial trigger can be injected into any input from
a dataset to mislead the victim model. By inserting the displayed trigger can
cause the trained unfair ToS detector to flip its correct unfair predictions
to fair.

##  2 Related Work

Adversarial Attacks in NLP: Most adversarial attack methods in NLP are white-
box, where the attacker has full access to the victim model (including
architectures, parameters, and training data). Prevalent white-box attacks
include HotFlip Ebrahimi et al. (2018), a gradient-based method that generates
adversarial examples on discrete text structure; PWWS Ren et al. (2019), an
importance-based method that substitutes words of high saliency. By contrast,
black-box attacks assume no knowledge of the victim model’s architectures and
parameters. Example techniques include the use of generative adversarial
networks (GANs) Zhao et al. (2018) and human-in-the-loop heuristics Wallace et
al. (2019b)

Universal Triggers: Wallace et al. (2019a) generate universal attack triggers
by using gradient signals to guide a search over the word embedding space.
They are input-agnostic, which makes them more threatening in real-world
scenarios. Despite being successful in confusing classification systems,
universal triggers are often unnatural and can easily be detected by human
readers. Song et al. (2021) generate attack triggers that appear closer to
natural text by using a pre-trained GAN. Training a GAN in the ToS domain from
scratch requires large datasets and GPU resources. In this work we try to
generate natural triggers by simply skipping all the subword and special
tokens during the search process; and leave the development and evaluation of
a ToS-GAN to future work.

##  3 Universal Trigger Generation

We assume a text input $x$ and its target label $y$ from the dataset
$D=\\{X,Y\\}$, a trained victim classifier model $f$ that predicts
$f(x)=\hat{y}$. While in a non-universal targeted attack the focus is on
flipping the prediction of a single text input $x$, our goal is to find an
input-agnostic trigger $t$ consisting of a sequence of tokens
$\\{w_{1},w_{2},…,w_{i}\\}$ such that when concatenating $t$ with any input
$x$ from $X$, the victim model incorrectly predicts $f(x;t)=\tilde{y}$, where
$\tilde{y}\neq\hat{y}$. Specifically, we use the following objective function:

$\operatorname*{arg\,min}_{t}\operatorname{\mathbb{E}}_{x\sim
X}[\mathcal{L}(\tilde{y},f(x;t))]$ (1)

To solve the above objective function, we follow the approach of Wallace et
al. (2019a) by utilizing the HotFlip method Ebrahimi et al. (2018) at the
token level: First, we initiate the trigger $t$ with a sequence of $i$
placeholder tokens (i.e., ‘the’); then we compute the gradient of (1) w.r.t
the trigger. Since tokens are discrete, we approximate the loss function
around the current token embedding using the first-order Taylor expansion

$\operatorname*{arg\,min}_{e_{i}^{\prime}\in\mathcal{V}}\left[e_{i}^{\prime}-e_{adv_{i}}\right]^{T}\nabla_{e_{adv_{i}}}\mathcal{L}$
(2)

where $\mathcal{V}$ is the set of all token embeddings over the entire
vocabulary and $e_{adv_{i}}$ represent the embedding of the current trigger
token.

We update the embedding for every trigger token $e_{adv_{i}}$ to minimize (2).
This can be efficiently computed through $d$-dimensional dot products, with
$d$ corresponding to the dimension of the token embeddings. For constructing
the entire updated trigger, we then use beam search to evaluate the top $i$
token candidates from (2) for each token position in the trigger $t$. As
variable parameters, we run experiments with triggers of different lengths [3,
5, 8] and insert positions [begin, middle, end] in the input text.

##  4 Experiments

###  4.1 Dataset and the Victim Model

The CLAUDETTE dataset Lippi et al. (2019); Ruggeri et al. (2022) consists of
100 ToS contracts (20,417 clauses) of online platforms. A clause is deemed as
unfair if it creates an unacceptable imbalance in the parties’ rights and
obligations, i.e., harms the user’s rights or minimizes the online service’s
obligations. Each clause was labelled by legal experts. 222To measure the
inter-annotation agreement, Lippi et al. (2019) have an additional test set
containing 10 contracts labelled by two distinct experts, which achieve a high
inner-annotator agreement with standard Cohen $\kappa$= 0.871. For details on
the annotation process and the legal rational of unfair contractual clauses,
please refer the original CLAUDETTE paper.

Following Lippi et al. 2019, we discard sentences shorter than 5 words. In
order to avoid an information leak between training and testing sentences by
virtue of them stemming from the same document of contracts, we split the 100
contracts randomly into 40:40:20 for training, development and testing. Table
2 in Appendix A shows the detailed statistics of each split. Notably, the
CLAUDETTE has a very imbalanced class ratio of 9:1 (fair:unfair).

For the victim model, we finetune an instance of LEGAL-BERT (nlpaueb/legal-
bert-base-uncased) Chalkidis et al. (2020) on the CLAUDETTE training set.
Please refer to Appendix B for details on model finetuning. It achieves
overall macro F1 of 88.9%, 97.7% F1 for class fair, and 80.1% for class
unfair.

###  4.2 Attack Results

In the following we focus on the attack scenario fairwashing: targeted attacks
that flip unfair predictions to fair. We apply the universal attack trigger
algorithm on the development set and report the attack performance on the test
set. The generated triggers can considerably degrade the victim model’s
performance. For instance, inserting the trigger of token length 8
“##purchased another opponent shall testify unless actuarial opponent” in the
middle of the sentence can decrease the model’s accuracy from 80.1% to 16.9%.
However, we observe that triggers often contain special tokens or subwords,
such as ‘[SEP]’ or ‘##purchased’, which makes them easily detectable for human
readers. Inspired by Wang, 2022, we facilitate the generation of natural
triggers by simply skipping all subwords and special tokens during the search
(hereafter we denote this approach as mode ’no_subword’ for simplicity).
Although slightly less effective than the original triggers (Table 4 in
Appendix C), the no_subword triggers are less likely to be detected by human
readers (See our human evaluation study in Section 6).

Figure 1: Accuracy loss of the victim model’s detection performance when
attacked by universal triggers of different insert positions and lengths. For
completeness, we report the full attack results in Appendix C

We also run experiments to study the impact of trigger length, insert
position, and mode (with/without subwords) on the attack’s effectiveness.
Figure 1 shows that increasing the token length improves attack effectiveness
by a noticeable margin. The victim model’s accuracy degrades by 25% to 60%
using three words and by 80% to 13% with eight words. The result also
indicates the victim model’s sensitivity to the insert position of the
triggers. These results are consistent with previous studies Wallace et al.
(2019b); Wang (2022): Triggers are more effective when inserted at the
beginning of the clause, which may be due to the transformer-based model
paying more attention to the terms at the beginning of the text. These results
hold across both modes. Between the modes, a higher effectiveness is
consistently observed for ’all’ compared with ’no_subword’. This is in line
with ’no_subword’ generating triggers from a subset of potential trigger
tokens of ’all’ mode.

Figure 2: Human response time (box plots) and detection accuracy (line plots)
for triggers of different insert positions and lengths. Control stands for the
question where no trigger is inserted. LMI represents an LMI trigger of length
eight inserted in the middle of the sentence. The insert positions are the
following. 0.0 : beginning, 0.5 : middle, 1.0 : end.

##  5 Data Artifacts as Universal Triggers

A growing number of works have raised awareness that deep neural models may
exploit spurious artifacts in the dataset and take erroneous shortcuts McCoy
et al. (2019); Xu and Markert (2022). In this section, we experiment with
using dataset artifacts as universal triggers to explore the feasibility of
generating universal triggers without access to the victim model’s gradient
signals. Following Gururangan et al. (2018), Wallace et al. (2019a) identified
the dataset artifacts as words with high pointwise mutual information (PMI)
Church and Hanks (1990) with each label. Since the Claudette dataset has a
heavily imbalanced label distribution, in order to prevent picking up very
sparse tokens, in this work, we use local mutual information (LMI) Schuster et
al. (2019), a re-weighted version of PMI. We observe that high LMI ranked
words are successful triggers. We use the 8 highest LMI words and PMI words
with label fairness as triggers (hereafter LMI trigger and PMI trigger
respectively, please refer to Appendix E for the list of words used); and
insert them to the unfair clauses at different token positions. The LMI
trigger is able to reduce the victim model’s classification accuracy from 80%
to around 60%; while the PMI trigger can only reduce the performance to around
76% (see Figure 3 in Appendix E). Although less successful than the universal
adversarial triggers, the LMI triggers are natural and less detectable than
’all’ mode triggers according to our human evaluation studies. Critically, LMI
triggers are extracted by simply analyzing the training data and do not
require access to the victim model. The attack effectiveness of LMI trigger
highlights the potential threat of training data leakage in the NLP
application.

##  6 Human Evaluation Study

We perform a human evaluation to study the impact of token length, insert
position and mode on the triggers’ detectability 333We report the details of
the web application used and full instructions for the human subjects in
Appendix D. The task is to identify which sentence out of four candidate
sentences from ToS contracts was modified. We include one question with no
modified sentence as the control. In a previous study, Song et al. 2021
directly asked the human participants to rate whether the generated triggers
were natural or not. However, the rating of naturalness is very abstract and
varies between individuals. Inspired by studies on the detection process in
psychological studies Pandya and Macy (1995); Yap and Balota (2007), we assume
response time (i.e., the length of time taken for a human to detect a trigger)
can act as a proxy for the naturalness. To measure the human detectability of
triggers, we hence collect the answer accuracy as well as the response time
from the participants.
19 participants of different ages, English abilities, and legal experience
were recruited from the personal network of the authors. Figure (2)
demonstrates that it is consistently easier for participants to detect ’all’
mode triggers than ’no_subword’ mode triggers. Participants were on average
19% faster in detecting that a sentence inserted by ‘all’ than ‘no_subword’
triggers; and they find ’all’ triggers with 21% higher accuracy on average. We
include the LMI trigger of token length eight in the study and find its
detectability is in between the ‘no_subword’ and ’all’ triggers of the same
length. The intuitive notion that participants are better at finding longer
triggers generally holds with regard to detection accuracy. Nevertheless, we
cannot observe a trend in the response time change, which may be due to our
small sample size. Regarding the insert position, participants are the fastest
in detecting triggers inserted in the middle. Further, we notice that special
tokens and subwords make triggers more obvious. Qualitative, informal reports
from participants indicate that ’spelling error’ stuck out in a legal context.
All triggers containing these tokens can be detected with more than 90%
accuracy, which include two ’all’ triggers of length three (containing special
token [SEP] or combination of subtokens ’##assignabilityconsult’); and one
‘no_subword’ triggers inserted at position 5 (includes a bound stem ‘concul’).
This likely explains why these two data points do not conform to the general
trend of detection accuracy.

##  7 Conclusion

We attacked ToS unfair clause detectors with universal adversarial triggers
generated by a gradient-based algorithm as well as by simply analyzing the
training data. The effectiveness of the triggers exposes the vulnerability of
the transformer-based classification model, and highlights the potential
threat of training data leakage. We also conducted a human evaluation to study
the detectability of the triggers. The results show that the triggers are less
likely to be detected if they do not include subtokens. Future work can
explore ways to generate more natural triggers in the legal domain, which may
even deceive readers with a formal education in law.

## Limitations

Wallace et al. (2019a) reduce the detection accuracy to 1% while we can only
manage to degrade it to 10%. This might be due to the imbalanced label
distribution and comparatively small size of the CLAUDETTE dataset. Our human
evaluation is an initial exploration with only 19 participants. Future work
will focus on using crowdsourcing techniques for large survey data collection.
Furthermore, we generate the ’no_subword’ triggers by skipping all the tokens
preceded by the double hashtag ’##’. This enables us to avoid derivational
morphemes and inflection suffixes but fails to exclude bound stems such as
‘consul’, which makes some triggers obvious to human readers. Future work can
explore better ways to generate natural triggers.

## Ethics Statement

The study presented here works exclusively with the publicly available
CLAUDETTE dataset, which consists of the Terms of Service (ToS) Agreements of
various online platforms. The techniques described in this paper are prone to
misuse. However, we design this study to draw public attention to the
vulnerability of the transformer-based classification model. We hope our work
will help accelerate progress in detecting and defending adversarial attacks.
We finetuned the victim model and generated all the triggers on Google Colab.
Our models adapted pretrained language models and we did not engage in any
training of such large models from scratch. We did not track computation
hours.

## References

  * Belinkov and Bisk (2017) Yonatan Belinkov and Yonatan Bisk. 2017.  Synthetic and natural noise both break neural machine translation.  _arXiv preprint arXiv:1711.02173_.
  * Chalkidis et al. (2020) Ilias Chalkidis, Manos Fergadiotis, Prodromos Malakasiotis, Nikolaos Aletras, and Ion Androutsopoulos. 2020.  LEGAL-BERT: The muppets straight out of law school.  In _Findings of the Association for Computational Linguistics: EMNLP 2020_ , pages 2898–2904, Online. Association for Computational Linguistics.
  * Cheng et al. (2019) Yong Cheng, Lu Jiang, and Wolfgang Macherey. 2019.  Robust neural machine translation with doubly adversarial inputs.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 4324–4333, Florence, Italy. Association for Computational Linguistics.
  * Church and Hanks (1990) Kenneth Church and Patrick Hanks. 1990.  Word association norms, mutual information, and lexicography.  _Computational linguistics_ , 16(1):22–29.
  * Ebrahimi et al. (2018) Javid Ebrahimi, Anyi Rao, Daniel Lowd, and Dejing Dou. 2018.  HotFlip: White-box adversarial examples for text classification.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 31–36, Melbourne, Australia. Association for Computational Linguistics.
  * Grinberg (2018) Miguel Grinberg. 2018.  _Flask web development: developing web applications with python_.  " O’Reilly Media, Inc.".
  * Gururangan et al. (2018) Suchin Gururangan, Swabha Swayamdipta, Omer Levy, Roy Schwartz, Samuel Bowman, and Noah A. Smith. 2018.  Annotation artifacts in natural language inference data.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers)_ , pages 107–112, New Orleans, Louisiana. Association for Computational Linguistics.
  * Iyyer et al. (2018) Mohit Iyyer, John Wieting, Kevin Gimpel, and Luke Zettlemoyer. 2018.  Adversarial example generation with syntactically controlled paraphrase networks.  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 1875–1885, New Orleans, Louisiana. Association for Computational Linguistics.
  * Lippi et al. (2019) Marco Lippi, Przemysław Pałka, Giuseppe Contissa, Francesca Lagioia, Hans-Wolfgang Micklitz, Giovanni Sartor, and Paolo Torroni. 2019.  Claudette: an automated detector of potentially unfair clauses in online terms of service.  _Artificial Intelligence and Law_ , 27(2):117–139.
  * McCoy et al. (2019) Tom McCoy, Ellie Pavlick, and Tal Linzen. 2019.  Right for the wrong reasons: Diagnosing syntactic heuristics in natural language inference.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 3428–3448, Florence, Italy. Association for Computational Linguistics.
  * Obar and Oeldorf-Hirsch (2020) Jonathan A Obar and Anne Oeldorf-Hirsch. 2020.  The biggest lie on the internet: Ignoring the privacy policies and terms of service policies of social networking services.  _Information, Communication & Society_, 23(1):128–147.
  * Pandya and Macy (1995) Abhijit S Pandya and Robert B Macy. 1995.  _Pattern recognition with neural networks in C++_.  CRC press.
  * Ren et al. (2019) Shuhuai Ren, Yihe Deng, Kun He, and Wanxiang Che. 2019.  Generating natural language adversarial examples through probability weighted word saliency.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 1085–1097, Florence, Italy. Association for Computational Linguistics.
  * Ruggeri et al. (2022) Federico Ruggeri, Francesca Lagioia, Marco Lippi, and Paolo Torroni. 2022.  Detecting and explaining unfairness in consumer contracts through memory networks.  _Artificial Intelligence and Law_ , 30(1):59–92.
  * Schuster et al. (2019) Tal Schuster, Darsh Shah, Yun Jie Serene Yeo, Daniel Roberto Filizzola Ortiz, Enrico Santus, and Regina Barzilay. 2019.  Towards debiasing fact verification models.  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 3419–3425.
  * Song et al. (2021) Liwei Song, Xinwei Yu, Hsuan-Tung Peng, and Karthik Narasimhan. 2021.  Universal adversarial attacks with natural triggers for text classification.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 3724–3733, Online. Association for Computational Linguistics.
  * Wallace et al. (2019a) Eric Wallace, Shi Feng, Nikhil Kandpal, Matt Gardner, and Sameer Singh. 2019a.  Universal adversarial triggers for attacking and analyzing NLP.  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 2153–2162, Hong Kong, China. Association for Computational Linguistics.
  * Wallace et al. (2019b) Eric Wallace, Pedro Rodriguez, Shi Feng, Ikuya Yamada, and Jordan Boyd-Graber. 2019b.  Trick me if you can: Human-in-the-loop generation of adversarial examples for question answering.  _Transactions of the Association for Computational Linguistics_ , 7:387–401.
  * Wang et al. (2020) Boxin Wang, Hengzhi Pei, Boyuan Pan, Qian Chen, Shuohang Wang, and Bo Li. 2020.  T3: Tree-autoencoder constrained adversarial text generation for targeted attack.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 6134–6150, Online. Association for Computational Linguistics.
  * Wang (2022) Yumeng Wang. 2022.  Global triggers for attacking and analyzing ranking models.  Master’s thesis, Hannover: Gottfried Wilhelm Leibniz Universität.
  * Wolf et al. (2019) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, et al. 2019.  Huggingface’s transformers: State-of-the-art natural language processing.  _arXiv preprint arXiv:1910.03771_.
  * Xu and Markert (2022) Shanshan Xu and Katja Markert. 2022.  The chinese causative-passive homonymy disambiguation: an adversarial dataset for nli and a probing task.  In _Proceedings of the 13th Language Resources and Evaluation Conference_ , Marseille, France. European Language Resources Association.
  * Yap and Balota (2007) Melvin J Yap and David A Balota. 2007.  Additive and interactive effects on response time distributions in visual word recognition.  _Journal of Experimental Psychology: Learning, Memory, and Cognition_ , 33(2):274.
  * Zhao et al. (2018) Zhengli Zhao, Dheeru Dua, and Sameer Singh. 2018.  Generating natural adversarial examples.  In _International Conference on Learning Representations_.

##  Appendix A Dataset Statistics

Table 2 displays the statics of the CLAUDETTE dataset.

Figure 3: Attack performance of LMI trigger and PMI trigger of the different
insert position.

##  Appendix B Finetuning the Victim Model

We used LEGAL-BERT (nlpaueb/legal-bert-base-uncased) with a sequence
classification head on top from the transformers library Wolf et al. (2019);
and finetuned it on the CLAUDETTE training set. The model is fine-tuned with 5
epochs, a learning rate of 1e-5. We determine the best learning rate using
grid search on the development set and use early stopping based on the
development set F1 score.

split | # sentences | % fair label | % unfair label
---|---|---|---
train | 8354 | 89.5% | 10.5%
dev | 8279 | 89.1% | 10.9%
test | 3784 | 89.3% | 10.7%
Table 2: Statistics of the train, dev and test split of the CLAUDETTE dataset.

##  Appendix C Additional Experimental Results

Table 3 demonstrates the attack results on fair clauses. Restricted to limited
GPU resources, we generated only triggers of eight tokens which are inserted
at the beginning of the sentence.

Table 4 displays the attack on unfair clauses with triggers of different
lengths [3,5,8], insert position [begin, middle, end] and mode [original,
no_subword].

Trigger | Length | Position | Mode | Accuracy | $\Delta$
---|---|---|---|---|---
Baseline | - | - | - | 97.7 |
not liable whenever | 3 | beginning | no_sub | 69.8 | -28.5%
terminate our convening practices if | 5 | beginning | no_sub | 47.6 | -51.2%
agree tankage bound through cloud terms 2016 laws | 8 | beginning | no_sub | 9.0 | -90.0%
Table 3: Performance of Universal Triggers on Fair Clauses Trigger | Length | Position | Mode | Accu. | $\Delta$
---|---|---|---|---|---
Baseline | - | - | - | 80.1 |
witness should testify | 3 | beginning | no_sub | 58.4 | -27.0%
may vote against | 3 | middle | no_sub | 60.8 | -24.1%
witness testified without | 3 | end | no_sub | 62.9 | -21.5%
interrelat order refusing priority where | 5 | beginning | no_sub | 37.1 | -53.7%
consul must produce his attorney | 5 | middle | no_sub | 46.6 | -41.9%
privilege to authenticate testimony groot | 5 | end | no_sub | 48.1 | -39.9%
testimony allows contracts opposing person tuber testify where | 8 | beginning | no_sub | 13.9 | -82.7%
compute another opponent shall testify unless lockbox opponent | 8 | middle | no_sub | 19.7 | -75.4%
another witness seems thus admissible scope testify usc | 8 | end | no_sub | 22.6 | -71.8%
admissible in evidence | 3 | beginning | all | 56.7 | -29.3%
##assignabilityconsult assigned | 3 | middle | all | 59.9 | -25.2%
[SEP] expert testimony | 3 | end | all | 60.2 | -24.8%
evid allowed equit testify where | 5 | beginning | all | 31.4 | -67%
[SEP] give precedence before priority | 5 | middle | all | 43.6 | -45.6%
368 hearsay witnesses may exclude | 5 | end | all | 43.1 | -46.2%
inference forbid 2028 opposing person may testify where | 8 | beginning | all | 12.8 | -84.0%
##purchased another opponent shall testify unless actuarial opponent | 8 | middle | all | 16.9 | -78.9%
assist [SEP] witness normally justifies cross admissibilitywillingness | 8 | end | all | 19.2 | -76.0%
Table 4: Performance of Universal Triggers on Unfair Label

##  Appendix D Instruction for the human evaluation study

The application is written in Python using Flask Grinberg (2018) and was
hosted on an AWS EC2 instance. It included a landing page with a short
instructions. Figure 4 is a screenshot of the web application. Following is
the instruction on the landing page for the human evaluation study:

“Background information
When using online platforms, users are asked to agree to the Terms of Service
(ToS). ToS documents tend to be long and difficult to understand. As a result,
most users accept the terms without reading them, including clauses which
would be deemed unfair under consumer protection standards. Therefore,
applications that can support consumers in detecting unfair clauses would be
useful. Nevertheless, studies have shown that such applications are vulnerable
to adversarial attacks; even slight modifications to the input text, like
inserting a few words into the text, can cause incorrect classifications. In
this study, we ask you to help us detect the malicious modifications in the
text.
Task instruction
You will be shown an excerpt of four sentences from a ToS contract. The task
is to identify which sentence is modified. Please feel free to contact us if
you have any questions. Many thanks for taking part in the study.”

##  Appendix E LMI and PMI triggers

Figure 3 demonstrates the attack performance of LMI and PMI triggers. The 8
highest LMI ranked words that used as LMI trigger are [’information’,
’payment’, ’must’, ’provide’, ’person’, ’license’, ’rights’, ’please’]. The
PMI trigger words are: [’berlin’, ’attribution’, ’addressing’, ’android’,
’sources’, ’organiser’, ’pc’, ’unreasonable’]

Figure 4: Screenshot of the web application for human evaluation


# On Tribonacci Sequences

Luke Pebody

(Saturday 28, January 2023)

###### Abstract

Let a tribonacci sequence be a sequence of integers satisfying
$a_{k}=a_{k-1}+a_{k-2}+a_{k-3}$ for all $k\geq 4$. For any positive integers
$k$ and $n$, denote by $f_{k}(n)$ the number of tribonacci sequences with
$a_{1},a_{2},a_{3}>0$ and with $a_{k}=n$.

For all $n$, there is a maximum $k$ such that $f_{k}(n)$ is non-zero.
Answering a question of Spiro [1], we show that there is a finite upper bound
(we specifically prove 561001) on $f_{k}(n)$ for any positive integer $n\geq
3$ and this maximum $k$.

We do this by showing that $f_{k}(n)$ has transitions in $n$ around constant
multiples of $\phi^{3k/2}$ (where $\phi$ is the real root of
$\phi^{3}=\phi^{2}+\phi+1$): there exists a constant $C$ such that
$f_{k}(n)>0$ whenever $n>C\phi^{3k/2}$ and for any constant $T$, the values of
$f_{k}(n)$ with $n<T\phi^{3k/2}$ have an upper bound independent of $k$.

##  1 Introduction

A tribonacci sequence of length $k$ is a sequence of integers $\langle
a_{i}\rangle_{i=1}^{k}$ such that $a_{i}=a_{i-1}+a_{i-2}+a_{i-3}$ for all
$4\leq i\leq k$. We say that such a sequence terminates at $a_{k}$ and that it
is positive if $a_{1},a_{2},a_{3}>0$ \- note that this easily implies that
$a_{i}>0$ for all $i$. Denote by $f_{k}(n)$ the number of tribonacci sequences
of length $k$ terminating at $n$.

Clearly $f_{1}(n)=1$ for all $n>0$, the only tribonacci sequence of length 1
terminating at $n$ being $\langle n\rangle$. Further,
$f_{2}(n)=f_{3}(n)=\infty$ as we can choose any values for the proceeding
terms.

For $n\geq 3$, there exists a tribonacci sequence of length longer than 3
terminating at $n$, for example $\langle n-2,1,1,n\rangle$. However for any
tribonacci sequence $\langle a_{i}\rangle_{i=1}^{k}$ of length $k$, and for
any $4\leq i\leq k$, $a_{i}=a_{i-1}+a_{i-2}+a_{i-3}\geq a_{i-1}+2$, so by
induction $a_{i}\geq 2i-5$ for all $3\leq i\leq k$, and hence if $n<2k-5$,
$f_{k}(n)=0$. Let $t(n)$ be the largest number such that $f_{t(n)}(n)>0$.

Let $p(n)$ denote the number of positive tribonacci sequences of length $t(n)$
terminating at $n$, so $p(n)=f_{t(n)}(n)$.

Clearly, since $t(1)=t(2)=3$ it follows that $p(1)=p(2)=\infty$. Spiro [1]
asks

######  Question 1.

Does there exist some absolute constant $c$ such that for all $n\geq 3$,
$p(n)\leq c$ for all $n$?

The purpose of this paper is to give a positive answer to this question.
Indeed we will show

######  Theorem 2.

For any integer $n\geq 3$, there are at most 561001 positive tribonacci
sequences of length $t(n)$ terminating at $n$.

It turns out the key question for our proof is the minimum size of the vector
$\begin{pmatrix}a_{1}\\\ a_{2}\\\ a_{3}\end{pmatrix}$ where $\langle
a_{i}\rangle_{i=1}^{n}$ is a non-zero tribonacci sequence terminating at
$a_{n}=0$. In Section 2 we will show a lower bound on such a sequence of the
order of $\phi^{n/2}$, which will allow us to prove

######  Theorem 3.

For any positive integers $n,k$ with $k\geq 4$, the number of positive
sequences of length $k$ terminating at $n$ is at most

$\lceil 1500\frac{n}{\phi^{3k/2}}\rceil^{2}.$

In Section 3 we turn to trying to put an upper bound on numbers that don’t
have any positive tribonacci sequences of length $k$ terminating at them. This
is an instance of the Coin Problem, also known as calculating the Frobenius
Number. We construct two specific tribonacci sequences terminating at
$a_{n}=0$ with $\begin{pmatrix}a_{1}\\\ a_{2}\\\ a_{3}\end{pmatrix}$ being of
the order of $\phi^{n/2}$ and with the integers $a_{1},a_{2},a_{3}$ having
specified signs, allowing us to prove

######  Theorem 4.

For any integer $n$ above $0.2\phi^{3k/2}$, there exists a positive tribonacci
sequence of length $k$ terminating at $n$.

This will be all that is required.

###### Proof of Theorem 2.

There is no sequence of length $t(n)+1$ terminating at $n$. Hence by Theorem
4, it follows that $n<0.2\phi^{3(t(n)+1)/2}=0.2\phi^{3/2}\phi^{3t(n)/2}$.

Thus from Theorem 3, it follows that there are at most

$\displaystyle\lceil 1500\frac{n}{\phi^{3t(n)/2}}\rceil^{2}$
$\displaystyle\leq\lceil
1500\frac{0.2\phi^{3/2}\phi^{3t(n)/2}}{\phi^{3t(n)/2}}\rceil^{2}$
$\displaystyle\leq\lceil 300\phi^{3/2}\rceil^{2}=749^{2}=561001$

positive tribonacci sequences of length $t(n)$ terminating at $n$. ∎

In Section 4, we will investigate which recurrence relations of the form
$x_{n}=ax_{n-1}+bx_{n-2}+cx_{n-3}$ for non-negative $a$ and $b$ and for
positive $c$ the arguments in this paper can be carried across to. We will
extend the result in the earlier sections to the following case.

######  Theorem 5.

Suppose $a,b,c$ are non-negative integers with $a+b>0$, $c=1$ and such that
$x^{3}-ax^{2}-bx-c=0$ has exactly one real root. Then there is an absolute
bound $T$ such that if positive integers $k\geq 4$ and $n$ are such that there
are no positive sequences $\langle a_{i}\rangle_{i=1}^{k+1}$ satisfying the
recurrence relation $a_{i}=aa_{i-1}+ba_{i-2}+ca_{i-3}$ of length $k+1$
terminating at $n$, then there are at most $T$ such sequences of length $k$
terminating at $n$.

We will leave open the question of which linear recurrences satisfy this
property, but will at least demonstrate an example of a recurrence that does
not. In particular we will show the existence of positive integers $k$ and $n$
such that there is no positive sequence $\langle a_{i}\rangle_{i=1}^{k+1}$
satisfying the recurrence relation $a_{i}=a_{i-1}+a_{i-2}+2a_{i-3}$ of length
$k+1$ terminating at $n$, but for which the number of such sequences of length
$k$ terminating at $n$ is unbounded.

##  2 Lower Bound

Let us say a sequence $\langle a_{i}\rangle_{i=1}^{\infty}$ is a reverse-
tribonacci sequence if for all $i\geq 0$, $a_{i}=a_{i+1}+a_{i+2}+a_{i+3}$. Let
us write out the expression for the reverse-tribonacci sequence starting
$\langle 0,k,l\rangle$. Recall that $\phi$ is the real solution to
$\phi^{3}=\phi^{2}+\phi+1$. We write the complex roots as $\phi_{1}$ and
$\phi_{2}=\overline{\phi_{1}}$.

######  Lemma 6.

For all integers $k,l$, if $\langle a_{i}\rangle_{i=1}^{\infty}$ is a reverse-
tribonacci sequence with $a_{1}=0$, $a_{2}=k$ and $a_{3}=l$, then for all $i$,
$a_{i}$ can be expressed as

$\displaystyle a_{i}$
$\displaystyle=\alpha\phi^{-i}+(k\psi_{1}+l\zeta_{1})\phi_{1}^{-i}+(k\psi_{2}+l\zeta_{2})\phi_{2}^{-i}$
$\displaystyle=(\alpha\phi^{-3i/2}+\beta\cos(\gamma-\delta i))\phi^{i/2},$

where

$\displaystyle\psi_{1}$
$\displaystyle=\frac{\phi_{1}^{3}+\phi_{1}^{2}}{\phi_{1}^{2}+2\phi_{1}+3}$
$\displaystyle\psi_{2}$ $\displaystyle=\overline{\psi_{1}}$
$\displaystyle\zeta_{1}$
$\displaystyle=\frac{\phi_{1}^{3}}{\phi_{1}^{2}+2\phi_{1}+3}$
$\displaystyle\zeta_{2}$ $\displaystyle=\overline{\zeta_{1}}$
$\displaystyle\alpha$
$\displaystyle=\frac{k\phi^{2}+(k+l)\phi^{3}}{\phi^{2}+2\phi+3}$
$\displaystyle\beta e^{\gamma i}$
$\displaystyle=2(k\psi_{1}+l\zeta_{1})\textrm{ and}$ $\displaystyle e^{\delta
i}$ $\displaystyle=\phi_{1}\sqrt{\phi}.$

###### Proof.

Any two-way infinite tribonacci sequence $\langle
a_{i}\rangle_{-\infty}^{\infty}$ can be written as
$a_{i}=p\phi^{i}+q\phi_{1}^{i}+r\phi_{2}^{i}$ for some $p,q$ and $r$.

Thus any reverse-tribonacci sequence $\langle a_{i}\rangle_{-\infty}^{\infty}$
can be written as $a_{i}=p\phi^{-i}+q\phi_{1}^{-i}+r\phi_{2}^{-i}$ for some
$p$, $q$, $r$. Solving for the $p,q,r$ that give $a_{1}=0$, $a_{2}=k$ and
$a_{3}=l$ leads to the above expression. ∎

Note that in the above expressions, $\psi_{1}$, $\psi_{2}$, $\zeta_{1}$,
$\zeta_{2}$ and $\delta$ are constants that do not depend on $k$ and $l$.

######  Lemma 7.

For any integers $k$ and $l$, if $\alpha$ and $\beta$ are defined as in Lemma
6, then $|\alpha|\leq|k|+|l|$ and $\beta\geq\frac{|k|+|l|}{31}$.

###### Proof.

$\alpha$ is roughly $0.9546k+0.6184l$, which is clearly bounded above by
$|k|+|l|$. $\psi_{1}$ is roughly $0.02267-0.217i$ and $\zeta_{1}$ is roughly
$0.1908-0.0187i$. As such, if $k$ and $l$ are non-negative then the real part
of $2(k\psi_{1}+l\zeta_{1})$ (and hence $\beta$) is at least
$0.04(k+l)>\frac{|k|+|l|}{31}$.

For $k$ positive and $l$ negative, the minimum value of $\frac{\beta}{k-l}$ is
approximately $0.03221>\frac{1}{31}$, and is achieved around $k=-0.3653l$. ∎

Finally we need a simple trigonometric property

######  Lemma 8.

For any real numbers $p$ and $q$ with $\frac{\pi}{2}<q<\pi$, the larger of
$|\cos(p)|$ and $|\cos(p+q)|$ is at least $\cos(q/2)$.

###### Proof.

Note that $\cos(q)<0$. Thus

$\displaystyle 2(\cos(p)^{2}+\cos(p+q)^{2})$
$\displaystyle=2\cos(p)^{2}+2\cos(p+q)^{2}$
$\displaystyle=\cos(2p)+\cos(2p+2q)+2$ $\displaystyle=2\cos(2p+q)\cos(q)+2$
$\displaystyle\geq 2+2\cos(q)$ $\displaystyle=4\cos(q/2)^{2}.$

Thus either $\cos(p)^{2}\geq\cos(q/2)^{2}$ or
$\cos(p+q)^{2}\geq\cos(q/2)^{2}$. ∎

This allows us to put a lower bound on the size of at least one of each
consecutive pair of a reverse-tribonacci sequence.

######  Corollary 9.

Given a non-zero integer reverse-tribonacci sequence $\langle
a_{i}\rangle_{i=1}^{\infty}$ with $a_{1}=0$, for every integer $n\geq 2$,
either $|a_{n}|>0.01\phi^{n/2}$ or $|a_{n+1}|>0.01\phi^{(n+1)/2}$ (or both).

###### Proof.

For $n\geq 2$ if $a_{n}$ and $a_{n+1}$ are both 0, then $a_{1}$ is the same
sign as $a_{n-1}$. Since $a_{1}=0$, it follows that the entire series must be
0. Since the sequence is non-zero, it follows that either $|a_{n}|\geq 1$ or
$|a_{n+1}\geq 1$. Since $1>0.01\phi^{n/2}$ for $n\leq 15$, we have proved the
statement for $n\leq 14$. Thus we may assume $n\geq 15$.

By Lemma 6, $\frac{a_{i}}{\phi^{i/2}}$ can be written as
$\alpha\phi^{-3i/2}+\beta\cos(\gamma-\delta i)$.

Now by Lemma 8, at least one of $|\cos(\gamma-\delta n)|$ and
$|\cos(\gamma-\delta(n-1))|$ is at least $\cos(\delta/2)$ ($\delta=2.176$ is
between $\frac{\pi}{2}$ and $\pi$). Let $t$ be the choice from $\\{n-1,n\\}$
that maximises $|\cos(\gamma-\delta t)|$.

By Lemma 7, if we write $\alpha^{\prime}=\frac{\alpha}{|k|+|l|}$ and
$\beta^{\prime}=\frac{\beta}{|k|+|l|}$ then $|\alpha^{\prime}|\leq 1$ and
$\beta^{\prime}>\frac{1}{31}$.

Therefore

$\displaystyle|\frac{a_{t}}{\phi^{t/2}}|$
$\displaystyle=|\alpha\phi^{-3t/2}+\beta\cos(\gamma-\delta t)|$
$\displaystyle\geq|\alpha^{\prime}\phi^{-3t/2}+\beta^{\prime}\cos(\gamma-\delta
t)|$ $\displaystyle\geq|\beta^{\prime}\cos(\gamma-\delta
t)|-|\alpha^{\prime}\phi^{-3t/2}|$
$\displaystyle\geq\frac{1}{31}\cos(\delta/2)-\phi^{-3t/2}\geq\frac{\cos(\delta/2)}{31}-\phi^{-22.5}>0.01.$

∎

Then we have a bound on the size of tribonacci sequences terminating at 0.

######  Corollary 10.

For $n\geq 3$, if $\langle a_{i}\rangle_{i=1}^{n}$ is a non-zero integer
tribonacci sequence terminating at 0 then either $|a_{1}|>0.01\phi^{n/2}$ or
$|a_{2}|>0.01\phi^{(n-1)/2}$ (or both).

###### Proof.

Let $k=a_{n-1}$ and $l=a_{n-2}$. Then if $\langle b_{i}\rangle_{i=1}^{\infty}$
is the reverse-tribonacci sequence with $b_{1}=0$, $b_{2}=k$ and $b_{3}=l$,
then $a_{i}=b_{n+1-i}$ for all $1\leq i\leq n$. Then this is just a
restatement of Corollary 9. ∎

This is all we need to prove Theorem 3.

###### Proof of Theorem 3.

Partition the tribonacci sequences of length $k\geq 4$ terminating at $n$
$\langle a_{i}\rangle_{i=1}^{k}$ by the pair
$(\lfloor\frac{a_{1}}{0.01\phi^{k/2}}\rfloor,\lfloor\frac{a_{2}}{0.01\phi^{k-1/2}}\rfloor)$.

If two sequences $\langle a_{i}\rangle_{i=1}^{k}$ and $\langle
b_{i}\rangle_{i=1}^{k}$ have the same pair, then
$|a_{1}-b_{1}|<0.01\phi^{k/2}$ and $|a_{2}-b_{2}|<0.01\phi^{(k-1)/2}$ and
hence, by Corollary 10, either $\langle a_{i}-b_{i}\rangle_{i=1}^{k}$ is zero
everywhere or does not terminate at 0.

Thus each distinct tribonacci sequence of length $k$ terminating at $n$ has a
distinct pair.

Define tribonacci sequence by $x_{1}=1,x_{2}=0,x_{3}=0$. Then if
$a_{1},a_{2},\ldots,a_{k}$ is a positive tribonacci sequence, $a_{i}\geq
x_{i}a_{4}$ for $i=2,3$ and $4$ and therefore $a_{k}\geq x_{k}a_{4}$. Now
$x_{k}<\phi^{k}/11$ for all $k\geq 4$ and hence
$a_{1}+a_{2}+a_{3}\leq\frac{11n}{\phi^{k}}$ for all tribonacci sequences of
length $k$ terminating at $n$.

Thus $\lfloor\frac{a_{1}}{0.01\phi^{k/2}}\rfloor$ is at most
$\frac{1100n}{\phi^{3k/2}}$ and
$\lfloor\frac{a_{2}}{0.01\phi^{(k-1)/2}}\rfloor$ is at most
$\frac{1100n}{\phi^{3k-1/2}}<\frac{1500n}{\phi^{3k/2}}$.

It follows that the number of Tribonacci sequences of length $k\geq 4$
terminating at $n$ is at most $\lceil\frac{1500n}{\phi^{3k/2}}\rceil^{2}$. ∎

Note we have not worked hard here to get the best bound. In a previous draft
we had a much more complicated proof of an upper bound which showed, in place
of Corollary 10, that if $\langle a_{i}\rangle_{i=1}^{n}$ terminated at 0 then
$\sqrt{a_{1}^{2}+a_{2}^{2}+a_{3}^{2}}>0.28\phi^{n/2}$, which led to an upper
bound for the main theorem of 42875.

##  3 Upper Bound

In this section, we turn to numbers which are not the terminus for any
tribonacci sequence of length $k$, working towards a proof of Theorem 4.

To that end, define three infinite tribonacci sequences $\langle
p_{i}\rangle_{i=1}^{\infty},\langle q_{i}\rangle_{i=1}^{\infty}$ and $\langle
r_{i}\rangle_{i=1}^{\infty}$ by
$(p_{1},p_{2},p_{3})=(1,0,0),(q_{1},q_{2},q_{3})=(0,1,0)$ and
$(r_{1},r_{2},r_{3})=(0,0,1)$. It is clear that for any tribonacci sequence
$\langle a_{i}\rangle_{i=1}^{n}$, $a_{n}=a_{1}p_{n}+b_{1}q_{n}+c_{1}r_{n}$.
Thus we are simply looking to get an upper bound on the largest number which
cannot be written as a positive integral linear combination of $p_{n},q_{n}$
and $r_{n}$. This is called the Frobenius Number of $p_{n},q_{n}$ and $r_{n}$.

First let us see that a finite bound does exist.

######  Lemma 11.

For all $k\geq 1$, $p_{k}$, $q_{k}$ and $r_{k}$ have no non-trivial common
divisor.

###### Proof.

If $p_{k},q_{k}$ and $r_{k}$ had a non-trivial common divisor $t>1$ then $t$
would be a common divisor of the terminus of every tribonacci sequence of
length $k$, from which it would follow that $t$ would in fact be a common
divisor of $p_{k+l}$ for all $l\geq 0$ (since $\langle p_{i+l}\rangle_{1}^{k}$
is a tribonacci sequence of length $k$).

Then, since $p_{i}=p_{i+3}-(p_{i+1}+p_{i+2})$, it would follow that $t$ would
be a common divisor of $p_{k-1},p_{k-2}$ and all the way back to $p_{0}=1$ by
induction, causing a contradiction. ∎

We will use the following bound, which might be originally due to
Killingbergtro.

######  Theorem 12.

Suppose $p,q$ and $r$ are integers with no non-trivial common divisor and let
us suppose $ap=bq+cr$ and $dq=ep+fr$ where $a,c,d,f>0$ and $b,e\geq 0$. Then
for every integer $N\geq ap+dq+r$, $N$ can be written in the form $xp+yq+zr$
for some positive integers $p,q,r$.

###### Proof.

Let $x,y,z$ be positive integers such that $px+qy+rz$ is equivalent to
$N\pmod{r}$, but for which $px+qy+rz$ is minimal (such a triple $x,y,z$ exist
because, as is well known, if $p,q$ and $r$ have no non-trivial common divisor
then all sufficiently large integers can be written in the form $px+qy+rz$,
and many of these sufficiently large integers are equivalent to $N\pmod{r}$.)

Since $px+qy+rz$ is minimal, $px+qy+rz-r$ cannot be written as a positive
linear combination of $x,y$ and $z$.

Thus in each of the equations

$\displaystyle px+qy+rz-r$ $\displaystyle=px$ $\displaystyle+qy$
$\displaystyle+r(z-1)$ $\displaystyle px+qy+rz-r$ $\displaystyle=p(x-a)$
$\displaystyle+q(y+b)$ $\displaystyle+r(z+c-1)$ $\displaystyle px+qy+rz-r$
$\displaystyle=p(x+e)$ $\displaystyle+q(y-d)$ $\displaystyle+r(z+f-1),$

it must follow that one of the coefficients must not be positive. Two of the
coefficients in each equation are clearly positive, so it follows that $x\leq
a,y\leq d$ and $z\leq 1$, so $px+qy+rz\leq pa+qd+r\leq N$. Since $N$ and
$px+qy+rz$ are equivalent modulo $r$, there exists a non-negative integer $t$
such that $N=px+qy+rz+rt$. Then $N=px+qy+r(z+t)$. ∎

Therefore, to show that all sufficiently large integers can be written as the
terminus of a tribonacci sequence of length $k$, we just need to find linear
combinations of $p_{n},q_{n}$ and $r_{n}$ combining to 0, with particular
signs of the combinations. This is equivalent to finding tribonacci sequences
ending at 0, which is equivalent to finding reverse-tribonacci sequences
starting at 0, and hence we can again use the expression from Lemma 6, which
states that if $\langle a_{i}\rangle_{i=1}^{\infty}$ is a reverse-tribonacci
sequence with $a_{1}=0$, $a_{2}=k$ and $a_{3}=l$ then for all $n$

$a_{n}=(\alpha\phi^{-3n/2}+\beta\cos(\gamma-\delta n))\phi^{n/2}.$

Note that for all but an extremely small collection of $n$, the term
$\beta\cos(\gamma+\delta n)$ dwarves $\alpha\phi^{-3n/2}$. As such, for a
fixed $k$ and $l$, the sign of $a_{n}$ depends only (except for a few very
rare counterexamples) on the fractional part of $\frac{\delta}{2\pi}n$.

######  Lemma 13.

For each integer $n\geq 4$, there exists a tribonacci sequence $\langle
a_{i}\rangle_{i=1}^{n}$ terminating at $a_{n}=0$, with $a_{1}>0$, $0\geq
a_{2}$, $0>a_{3}$ and with $a_{1}<0.81\phi^{n/2}.$

Similarly for all such $n$, there exists a tribonacci sequence $\langle
b_{i}\rangle_{i=1}^{n}$ terminating at $b_{n}=0$, with $b_{2}>0$, $0\geq
b_{1}$, $0>b_{3}$ and with $b_{2}<0.64\phi^{n/2}.$

###### Proof.

Table 1: Table for Lemma 13 $t_{0}$ | $t_{1}$ | $k$ | $l$ | $\alpha$ | $\beta$ | $\gamma$ | $x_{0}$ | $x_{1}$ | $x_{2}$
---|---|---|---|---|---|---|---|---|---
0 | 0.06 | 0 | 1 | 0.6184 | 0.3834 | -0.0977 | 0.3410 | -0.0500 | -0.1694
0.06 | 0.16 | -1 | 2 | 0.2822 | 0.8027 | 0.4640 | 0.6879 | -0.0515 | -0.2163
0.16 | 0.22 | -1 | 1 | -0.3362 | 0.5200 | 0.8677 | 0.4526 | -0.0471 | -0.2482
0.22 | 0.35 | -1 | 0 | -0.9546 | 0.4364 | 1.6749 | 0.3778 | -0.0354 | -0.0294
0.35 | 0.45 | -1 | -1 | -1.5731 | 0.6360 | 2.3067 | 0.5517 | -0.0538 | -0.1588
0.45 | 0.56 | 0 | -1 | -0.6184 | 0.3834 | 3.0439 | 0.3410 | -0.0500 | -0.0548
0.56 | 0.66 | 1 | -2 | -0.2822 | 0.8027 | -2.6776 | 0.6879 | -0.0515 | -0.2163
0.66 | 0.72 | 1 | -1 | 0.3362 | 0.5200 | -2.2739 | 0.4526 | -0.0471 | -0.2482
0.72 | 0.85 | 1 | 0 | 0.9546 | 0.4364 | -1.4667 | 0.3778 | -0.0354 | -0.0294
0.85 | 0.95 | 1 | 1 | 1.5731 | 0.6360 | -0.8349 | 0.5517 | -0.0538 | -0.1588
0.95 | 1 | 0 | 1 | 0.6184 | 0.3834 | -0.0977 | 0.3745 | -0.1864 | -0.0548

We will split into cases based on the fractional part of $\frac{\delta
n}{2\pi}=0.3464n$. See Table 1. For each row, if $t_{0}\leq\frac{\delta
n}{2\pi}-\lfloor\frac{\delta n}{2\pi}\rfloor\leq t_{1}$, then for the given
values of $k$ and $l$, if $\beta$ and $\gamma$ are as defined in Lemma 6, one
can confirm that $\beta\cos(\gamma-\delta n)\geq x_{0}>0.34$, while
$\beta\cos(\gamma-\delta(n-1))\leq x_{1}<-0.035$ and
$\beta\cos(\gamma-\delta(n-2))\leq x_{2}<-0.029$.

Furthermore, for all such $k,l$, $|\alpha|<1.58$, so if $n\geq 7$,
$|\alpha\phi^{-3(n-2)/2}|\leq 0.017$, from which it follows that
$a_{n}>0>a_{n-1},a_{n-2}$. Further,
$\frac{a_{n}}{\phi^{n/2}}<\beta+0.017<0.81.$

For $4\leq n<7$, we can verify the sequences $(1,0,-1,0),(2,0,-1,1,0)$ and
$(2,0,-1,1,0,0)$ satisfy the conditions for $(a_{1},a_{2},\ldots,a_{n})$.

Table 2: Other table for Lemma 13 $t_{0}$ | $t_{1}$ | $k$ | $l$ | $\alpha$ | $\beta$ | $\gamma$ | $x_{0}$ | $x_{1}$ | $x_{2}$
---|---|---|---|---|---|---|---|---|---
0 | 0.06 | 1 | -1 | 0.3362 | 0.5200 | 2.2739 | -0.3362 | 0.4625 | -0.0678
0.06 | 0.19 | 1 | 0 | 0.9546 | 0.4364 | 1.4667 | -0.1176 | 0.3862 | -0.0528
0.19 | 0.29 | 1 | 1 | 1.5731 | 0.6360 | 0.8349 | -0.2812 | 0.5639 | -0.0791
0.29 | 0.41 | 0 | 1 | 0.6184 | 0.3834 | 0.0977 | -0.1311 | 0.3369 | -0.0413
0.41 | 0.56 | -1 | 1 | -0.3362 | 0.5200 | -0.8677 | -0.0714 | 0.4625 | -0.0678
0.56 | 0.69 | -1 | 0 | -0.9546 | 0.4364 | -1.6749 | -0.1176 | 0.3862 | -0.0528
0.69 | 0.79 | -1 | -1 | -1.5731 | 0.6360 | -2.3067 | -0.2812 | 0.5639 | -0.0791
0.79 | 0.91 | 0 | -1 | -0.6184 | 0.3834 | -3.0439 | -0.1311 | 0.3369 | -0.0413
0.91 | 1 | 1 | -1 | 0.3362 | 0.5200 | 2.2739 | -0.0714 | 0.4641 | -0.2528

For the sequence $(b_{1},b_{2},\ldots,b_{n})$, see Table 2. Here, for each
row, if $t_{0}\leq\frac{\delta n}{2\pi}-\lfloor\frac{\delta
n}{2\pi}\rfloor\leq t_{1}$, then for the given values of $k$ and $l$, if
$\beta$ and $\gamma$ are as defined in Lemma 6, one can confirm that
$\beta\cos(\gamma-\delta n)\leq x_{0}<-0.071$, while
$\beta\cos(\gamma-\delta(n-1))\geq x_{1}>0.33$ and
$\beta\cos(\gamma-\delta(n-2))\leq x_{2}<-0.041$.

Furthermore, for all such $k,l$, $|\alpha|<1.58$, so if $n\geq 7$,
$|\alpha\phi^{-3(n-2)/2}|\leq 0.017$, from which it follows that
$a_{n-1}>0>a_{n},a_{n-2}$.

For $4\leq n<7$, we can verify the sequences $(0,1,-1,0),(0,1,-1,0,0)$ and
$(-1,2,-1,0,1,0)$ satisfy the conditions for $(b_{1},b_{2},\ldots,b_{n})$. ∎

This then completes our proof.

###### Proof of Theorem 4.

Lemma 13 gives us tribonacci sequences $\langle a_{i}\rangle_{i=1}^{n}$ and
$\langle b_{i}\rangle_{i=1}^{n}$ terminating at $a_{n}=b_{n}=0$. It follows
that $a_{1}p_{n}+a_{2}q_{n}+a_{3}r_{n}=0=b_{1}q_{n}+b_{2}q_{n}+b_{3}r_{n}.$

Since $a_{1},b_{2}>0>a_{3},b_{3}$ and $0\geq a_{2},b_{1}$, it follows that we
can write

$\displaystyle a_{1}p_{n}$ $\displaystyle=(-a_{2})q_{n}+(-a_{3})r_{n}\text{
and}$ $\displaystyle b_{2}q_{n}$ $\displaystyle=(-b_{1})p_{1}+(-b_{3})r_{n}$

satisfying the sign requirements of Theorem 12, so it follows that every
integer $N\geq a_{1}p_{n}+b_{2}q_{n}+r_{n}$ can be written in the form
$xp_{n}+yq_{n}+zr_{n}$ for some positive integers $x,y$ and $z$, and hence
there exists a positive tribonacci sequence of length $k$ ending at $N$.

By the bounds on $a_{1}$ and $b_{2}$ given in Lemma 13, we have such a
tribonacci sequence for all $N\geq
0.81\phi^{k/2}u_{k}+0.64\phi^{k/2}v_{k}+w_{k}$. Since $u_{k}\leq v_{k}\leq
w_{k}<0.11\phi^{k}$ and $0.81\phi^{k/2}+0.64\phi^{k/2}+1<1.74\phi^{k/2}$, it
follows that such a tribonacci sequence exists for all $N\geq 0.2\phi^{3k/2}$
as was required. ∎

##  4 Other cubic recurrences

For non-negative $a,b,c$ we can ask a similar question for recurrences of the
form $x_{n}=ax_{n-1}+bx_{n-2}+cx_{n-3}$. Formally, let us define
$k_{a,b,c}(n)$ to be the largest $k$ such there is a positive $k$-element
solution $\langle x_{i}\rangle_{i=1}^{k}$ to the recurrence relation
$x_{i}=ax_{i-1}+bx_{i-2}+cx_{i-3}$, and define $t_{a,b,c}(n)$ to be the number
of positive $k_{a,b,c}(n)$-element solutions that exist.

If $c=0$, this is a quadratic recurrence, and the problem is already solved.
If $a=0,b=0$ and $c=1$, the recurrence is $x_{n}=x_{n-3}$, and $k_{a,b,c}(n)$
is not defined for any $n$.

For all $a,b,c\geq 0$ with $c\geq 1$ and $a+b+c\geq 2$, say that the
recurrence $x_{n}=ax_{n-1}+bx_{n-2}+cx_{n-3}$ is congenial if there exists a
finite bound $B$ such that for all $n$, $t_{a,b,c}(n)=\infty$ or
$t_{a,b,c}(n)\leq B$.

Firstly let us note that not all recurrences are congenial.

######  Lemma 14.

The recurrence $x_{n}=x_{n-1}+x_{n-2}+2x_{n-3}$ is not congenial.

###### Proof.

Let $\langle p_{n}\rangle_{n=1}^{\infty}$, $\langle
q_{n}\rangle_{n=1}^{\infty}$ and $\langle r_{n}\rangle_{n=1}^{\infty}$ be the
solutions to the recurrence starting with $\langle 1,0,0\rangle$, $\langle
0,1,0\rangle$ and $\langle 0,0,1\rangle$ respectively. Then
$x_{n}=x_{1}p_{n}+x_{2}q_{n}+x_{3}r_{n}$.

Solutions to the recurrence can be split as the sum of two parts - a sequence
of the form $\langle x^{(1)}_{n}=2^{n-1}k\rangle$ and a sequence of the form
$\langle x^{(2)}_{n}\rangle$ which is periodic with period 3 with
$x^{(2)}_{1}+x^{(2)}_{2}+x^{(2)}_{3}=0$. It is then easy to solve for $k$:
$x_{1}+x_{2}+x_{3}=x^{(1)}_{1}+x^{(1)}_{2}+x^{(1)}_{3}=7k$, so
$k=\frac{x_{1}+x_{2}+x_{3}}{7}$.

In particular, if you let $t_{n}=\frac{2^{n-1}}{7}$, $p_{n}-t_{n}$ is periodic
with period $\langle\frac{6}{7},-\frac{2}{7},-\frac{4}{7}\rangle$,
$q_{n}-t_{n}$ with period
$\langle-\frac{1}{7},\frac{5}{7},-\frac{4}{7}\rangle$ and $r_{n}-t_{n}$ with
period $\langle-\frac{1}{7},-\frac{2}{7},\frac{3}{7}\rangle$.

For $n=3t$, $x_{n}=c(x_{1}+x_{2})+(c+1)x_{n-3}$ and
$x_{n+1}=2(c+1)x_{1}+(2c+1)(x_{2}+x_{3})$ where $c=\frac{2^{3t-1}-1}{7}$. Then
$x_{n+1}$ cannot be equal to $(2c+1)(2c+3)$ for positive $x_{1},x_{2},x_{3}$
($x_{1}$ would have to be a multiple of $2c+1$ that is positive but less than
$2c+1$), but for all $1\leq i\leq 4c+4$, if $x_{1}=i$, $x_{2}=4c+5-i$ and
$x_{3}=3$, then $x_{n}=c(4c+5)+(c+1)3=4c^{2}+8c+3=(2c+1)(2c+3)$. ∎

The proofs in this paper can be adapted to show that many other recurrences
are congenial. Let us say a polynomial $x^{3}-ax^{2}-bx-c$ is affable if $c=1$
and it has exactly one real root, which is more than 1. We will show that
affability leads to congeniality.

For the rest of this section, fix an affable polynomial $x^{3}-ax^{2}-bx-c$
with real root $\eta_{1}$ and complex roots $\eta_{2}$ and
$\eta_{3}=\overline{\eta_{2}}$. Note that $|\eta_{2}|=\eta_{1}^{-1/2}$.

We will make use of the following equivalent to Lemma 6.

######  Lemma 15.

Given a sequence $\langle x_{i}\rangle_{i=1}^{n}$ satisfying
$x_{i+3}=ax_{i+2}+bx_{i+1}+cx_{i}$ with $x_{n}=0$, $x_{n-1}=k$ and
$x_{n-2}=l$, $x_{i}$ can be expressed as

$x_{i}=\sum_{j=1}^{3}(k\psi_{j}+l\zeta_{j})\eta_{j}^{n-i}$

for constants $\psi_{j},\zeta_{j}$ depending only on $x^{3}-ax^{2}-bx-c$,
which can be rewritten as

$\frac{x_{i}}{\eta_{1}^{(n-i)/2}}=\alpha\eta_{1}^{-3(n-i)/2}+\beta\cos(\gamma-\delta(n-i))$

where

$\displaystyle\alpha$ $\displaystyle=k\psi_{1}+l\zeta_{1},$
$\displaystyle\beta e^{\gamma i}$
$\displaystyle=2(k\psi_{2}+l\zeta_{2})\textrm{ and}$ $\displaystyle e^{\delta
i}$ $\displaystyle=\eta_{2}\sqrt{\eta_{1}}.$

We will follow the steps of the proof of Theorem 2 for all recurrence
relations corresponding to affable polynomials. We will not attempt to give an
actual bound.

We note the following, which will be used in the equivalents of both Theorems
3 and 4

######  Lemma 16.

If real numbers $k$ and $l$ satisfy $k\psi_{2}+l\zeta_{2}=0$, then $k=l=0$.

###### Proof.

As $\psi_{3}=\overline{\psi_{2}}$ and $\zeta_{3}=\overline{\zeta_{2}}$,
$k\psi_{3}+l\zeta_{3}=0$ and therefore the sequence with $x_{n}=0$,
$x_{n-1}=k$ and $x_{n-2}=l$ can simply be expressed as
$x_{i}=(k\psi_{1}+l\zeta_{1})\eta_{1}^{n-i}$.

As $0=x_{n}=k\psi_{1}+l\zeta_{1}$, it follows that $x_{i}=0$ for all $i$ and
therefore $k=l=0$. ∎

We start by following the proof of Theorem 3.

######  Lemma 17.

There exists an absolute bound $M$ such that for $n\geq 4$ and all non-zero
integer sequences $\langle x_{i}\rangle_{i=1}^{n}$ satisfying
$x_{i+3}=ax_{i+2}+bx_{i+1}+cx_{i}$ and $x_{n}=0$ either $|x_{1}|\geq
M\eta_{1}^{n/2}$ or $|x_{2}|\geq M\eta_{1}^{n/2}$ (or both).

###### Proof.

The set of complex numbers $k\psi_{2}+l\zeta_{2}$ for $k,l$ real with
$|k|+|l|=1$ is a closed subset of the complex plane (in fact a hollow
parallelogram) which, by Lemma 16 does not contain 0. As such, there exists a
constant $V>0$ such that for all such $k,l$, $|k\psi_{2}+l\zeta_{2}|>V$. Then
for all real $k,l$ it follows that $\beta=|k\psi_{2}+l\zeta_{2}|>V(|k|+|l|)$.

Clearly if $U=\max(|\psi_{1}|,|\zeta_{1}|)$, $\alpha\leq U(|k|+|l|)$.

Pick integer $N$ such that $V\cos(\delta/2)-U\eta_{1}^{-3(N-1)/2}$ is
positive. Note we can do this because $\frac{\pi}{2}<\delta<\pi$. Then let
$M>0$ be such that $V\cos(\delta/2)-U\eta_{1}^{-3(N-2)/2}>M\eta_{1}$ and
$\eta_{1}^{-N/2}>M$.

Now if $n\leq N$, then $M\eta_{1}^{n/2}<1$ (note that $\eta_{1}>1$ since
$1^{3}<a\times 1^{2}+b\times 1+c$) and $x_{1},x_{2}$ cannot both be 0 (as then
$x_{n}$ would have to be the same sign as $x_{3}$ and non-zero).

For $n>N$, we know from Lemma 8 that there exists $t\in\\{1,2\\}$ such that
$|\cos(\gamma-\delta(n-t))|>\cos(\delta/2)>0$.

For such $t$, $n-t\geq N-1$ and so it follows that

$\displaystyle\frac{|x_{t}|}{\eta_{1}^{(n-t)/2}}$
$\displaystyle=|\alpha\eta_{1}^{-3n/2}+\beta\cos(\gamma-\delta n)|$
$\displaystyle\geq|\beta\cos(\gamma-\delta n)|-|\alpha|\eta_{1}^{-3n/2}$
$\displaystyle\geq V\cos(\delta/2)-U\eta_{1}^{-3n/2}$ $\displaystyle\geq
M\eta_{1}$

and hence $|x_{t}|\geq M\eta_{1}^{(n+2-t)/2}\geq M\eta_{1}^{n/2}$. ∎

This is enough for the equivalent of Theorem 3

######  Theorem 18.

There exists a fixed bound $T$ such that for any positive integers $n,k$ with
$k\geq 4$, the number of positive sequences $\langle x_{i}\rangle_{i=1}^{k}$
satisfying $x_{i+3}=ax_{i+2}+bx_{i+1}+cx_{i}$ and terminating at $x_{k}=n$ is
at most

$\lceil T\frac{n}{\eta_{1}^{3k/2}}\rceil^{2}.$

###### Proof.

There is a fixed $P$ such that for any positive sequence $\langle
a_{i}\rangle_{i=1}^{k}$ satisfying the recurrence relation with $k\geq 4$,
$P\eta_{1}^{k}(a_{1}+a_{2}+a_{3})\leq a_{k}$.

Thus for any such sequence terminating at $n$, $a_{1}$ and $a_{2}$ are bounded
above by $\frac{n}{P\eta_{1}^{k}}$ and for any two such sequences, by Lemma
17, either the first terms or the second terms differ by at least
$M\eta_{1}^{k/2}$.

Thus the number of such sequences is at most
$\lceil\frac{n}{PM\eta_{1}^{3k}/2}\rceil^{2}$. ∎

Now we proceed to follow the proof of Theorem 4. We will need the following
Corollary to Lemma 16

######  Corollary 19.

Given any interval $0\leq x<y\leq 2\pi$ within $(0,2\pi)$, we can pick non-
zero integers $k,l$ for which $x<\gamma<y$.

###### Proof.

Lemma 16 says that the set $\\{k\psi_{2}+l\zeta_{2}:k,l\in\mathbb{R}\\}$, when
viewed geometrically as a subset of the complex plane, is not of dimension 1.
Thus it must be the entire complex plane. Pick $x<z<y$, then there exist real
$k,l$ with $k\psi_{2}+l\zeta_{2}=e^{iz}$.

Now let $k_{n}=\lfloor nk\rfloor$ and $l_{n}=\lfloor nl\rfloor$. The limit as
$n$ tends to infinity of $\frac{k_{n}\psi_{2}+l_{n}\zeta_{2}}{n}$ is $e^{iz}$
and therefore for all sufficiently large $n$, $\gamma$ (which is the argument
of $\frac{k_{n}\psi_{2}+l_{n}\zeta_{2}}{n}$) must be contained in the open
interval $(x,y)$. ∎

We shelve this for the moment and focus on a simple piece of trigonometry.

######  Lemma 20.

For all numbers $\frac{\pi}{2}<\delta<\pi$, there exists $t$ such that
$\cos(t)>0>\cos(t+\delta),\cos(t+2\delta)$

###### Proof.

Pick $t$ such that $\frac{\pi}{2}-\delta<t<\frac{3\pi}{2}-2\delta$. There
exists such a $t$ because $\delta<\pi$.

Since $\delta<\pi$, $-\frac{pi}{2}<\frac{\pi}{2}-\delta<t$. Similarly since
$\frac{\pi}{2}<\delta$, $t<\frac{3\pi}{2}-2\delta<\frac{pi}{2}$. So
$-\frac{pi}{2}<t<\frac{pi}{2}$ and hence $\cos(t)>0$.

Further $\frac{\pi}{2}<t+\delta<t+2\delta<\frac{3\pi}{2}$, so $\cos(t+\delta)$
and $\cos(t+2\delta)$ are negative. ∎

This leads to the following somewhat technical-seeming lemma.

######  Lemma 21.

For all numbers $\frac{\pi}{2}<\delta<\pi$, there exists an $\epsilon>0$ and
finitely many intervals $\langle(x_{i},y_{i})\rangle_{i=1}^{n}$ such that for
all $t$ there exists an interval $(x_{i},y_{i})$ such that for all
$x\in(x_{i},y_{i})$, $\cos(t+x)>\epsilon$ and
$-\epsilon>\cos(t+x+\delta),\cos(t+x+2\delta)$.

###### Proof.

Pick a $t$ according to Lemma 20, and let $\epsilon>0$ be a real number such
that $\cos(t)>\epsilon$ and $-\epsilon>\cos(t+\delta),\cos(t+2\delta)$.

Then since $\cos$ is a continuous function, there is an open region $(l,u)$
around $t$ such that for all $x\in(l,u)$, $\cos(x)>\epsilon$ and
$-\epsilon>\cos(x+\delta),\cos(x+2\delta)$.

Let $n$ be an integer such that $\frac{4\pi}{n}<u-l$ and then define
$(x_{i},y_{i})$ to be $(i\frac{2\pi}{n},(i+1)\frac{2\pi}{n})$ for $1\leq i\leq
n$.

For all $t$ there is a maximum integer $K$ such that $t+K\frac{2\pi}{n}\leq
l$. Then $l<t+(K+1)\frac{2\pi}{n}$ by maximality, but
$t+(K+2)\frac{2\pi}{n}\leq l+\frac{4\pi}{n}<u$.

Thus if $(K+1)\frac{2\pi}{n}<x<(K+2)\frac{2\pi}{n}$, $l<t+x<u$ and hence
$\cos(t+x)>\epsilon$ and $-\epsilon>\cos(t+x+\delta),\cos(t+x+2\delta)$.

Since $\cos$ is periodic with period $2\pi$, if $1\leq i\leq n$ and $i$ is
equivalent to $K+1$ modulo $n$, then for all $x_{i}<x<y_{i}$,
$\cos(t+x)>\epsilon$ and $-\epsilon>\cos(t+x+\delta),\cos(t+x+2\delta)$. ∎

This leads to the equivalent of Lemma 13.

######  Lemma 22.

There exists a constant $C$ such that for all $n\geq 4$, there exist sequence
$\langle a_{i}\rangle_{i=1}^{n}$ satisfying the recurrence relation and
terminating at 0 for which $C\eta_{1}^{n/2}>a_{1}>0>a_{2},a_{3}$

###### Proof.

Since $\frac{\pi}{2}<\delta<\pi$, we can apply Lemma 21 and get $\epsilon>0$
and finitely many intervals $(x_{i},y_{i})$ such that for all $t$ there exists
an interval $(x_{i},y_{i})$ such that for all $x\in(x_{i},y_{i})$,
$\cos(t+x)>\epsilon$ and $-\epsilon>\cos(t+x+\delta),\cos(t+x+2\delta)$.

By Corollary 19, for each such interval $(x_{i},y_{i})$, we can choose non-
zero integers $k_{i},l_{i}$ for which $x_{i}<\gamma(k_{i},l_{i})<y_{i}$. Let
$A$ be some real number such that $|\alpha(k_{i},l_{i})|<A$ for all such
pairs, $B>0$ be some real number such that $|\beta(k_{i},l_{i})|>B$ and let
$N$ be such that $A\eta_{1}^{-3N/2}<B\epsilon$.

Then for any $j\geq N+3$, by the statement of Lemma 21, there exists an
interval $(x_{i},y_{i})$ such that for all $x\in(x_{i},y_{i})$,
$\cos(x-(j-1)\delta)>\epsilon$ and
$-\epsilon>\cos(x-(j-2)\delta),\cos(x-(j-3)\delta)$. Since
$\gamma(k_{i},l_{i})\in(x_{i},y_{i})$, it follows that

$\frac{a_{1}}{\eta_{1}^{(j-1)/2}}=\alpha(k_{i},l_{i})\eta_{1}^{-3(j-1)/2}+\beta(k_{i},l_{i})\cos(\gamma(k_{i},l_{i})-(j-1)\delta)$

is the sum of a number of absolute value at most $A\eta_{1}^{-3N/2}$ and a
number that is at least $B\epsilon$ and so is positive. Similarly $a_{2}$ and
$a_{3}$ are negative. $\frac{|a_{1}|}{\eta_{1}^{j/2}}$ is bounded above by
$2B\epsilon$.

For each value $4\leq j\leq N+2$, we can just choose any sequence satisfying
the bounds. For instance, if $a_{j}=pa_{1}+qa_{2}+ra_{3}$, we set $a_{1}=q+r$,
$a_{2}=a_{3}=-p$. Choose $C$ such that $C>2B\epsilon$ and such that for all
$4\leq j\leq N+2$, the sequences we have chosen satisfy
$a_{1}<C\eta_{1}^{j/2}$. ∎

Similarly we can get the following.

######  Lemma 23.

There exists a constant $C$ such that for all $n\geq 4$, there exist sequence
$\langle b_{i}\rangle_{i=1}^{n}$ satisfying the recurrence relation and
terminating at 0 for which $C\eta_{1}^{n/2}>b_{2}>0>b_{1},b_{3}$

###### Proof.

Proof entirely analagous to Lemma 22.

For Lemma 20, we need a $u$ such that
$\cos(u+\delta)>0>\cos(u),\cos(u-2\delta)$.

Pick $u$ such that $\frac{\pi}{2}-2\delta<u<\frac{-\pi}{2}$. There exists such
a $u$ because $\delta>\frac{\pi}{2}$.

Since $\delta<\pi$, $\frac{-3\pi}{2}<u<\frac{-\pi}{2}$ and hence $\cos(u)<0$.
Similarly $\frac{\pi}{2}<u+2\delta<\frac{3\pi}{2}$ and hence
$\cos(u+2\delta)<0$. Finally
$\frac{\pi}{2}-\delta<u+\delta<\delta-\frac{\pi}{2}$, so
$-\frac{\pi}{2}<u+\delta<\frac{\pi}{2}$, so $\cos(u+\delta)>0$.

Then by a method equivalent to Lemma 21 there exists an $\epsilon^{\prime}>0$
and finitely many intervals
$\langle(x^{\prime}_{i},y^{\prime}_{i})\rangle_{i=1}^{m}$ such that for all
$t$ there exists an interval $(x^{\prime}_{i},y^{\prime}_{i})$ such that for
all $x\in(x^{\prime}_{i},y^{\prime}_{i})$,
$\cos(t+x+\delta)>\epsilon^{\prime}$ and
$\epsilon^{\prime}>\cos(t+x),\cos(t+x+2\delta)$.

We then apply the same method as the proof of Lemma 22 ∎

This allows us to prove the equivalent of Theorem 4.

######  Theorem 24.

There exists a real number $U$ such that for any positive integers $n,k$ with
$k\geq 4$ and $n\geq U\eta_{1}^{3k/2}$, there is a positive sequence $\langle
x_{i}\rangle_{i=1}^{k}$ satisfying $x_{i+3}=ax_{i+2}+bx_{i+1}+cx_{i}$ and
terminating at $x_{k}=n$.

###### Proof.

Denote by $p_{k},q_{k}$ and $r_{k}$ the integers such that
$x_{k}=p_{k}x_{1}+q_{k}x_{2}+r_{k}x_{3}$ for all such sequences $\langle
x_{i}\rangle_{i=1}^{k}$.

Then since there can be an integer sequence ending at $x_{k}=1$, there is no
non-trivial common divisor of $p_{k},q_{k}$ and $r_{k}$.

Further, by Lemma 22 and Lemma 23 there exist integers
$C\eta_{1}^{k/2}>a_{1}>0>a_{2},a_{3}$ and
$C\eta_{1}^{k/2}>b_{2}>0>b_{1},b_{3}$ for which
$a_{1}p_{k}+a_{2}q_{k}+a_{3}r_{k}=b_{1}p_{k}+b_{2}q_{k}+b_{3}r_{k}=0$. Hence
by Theorem 12, for all $n\geq a_{1}p_{k}+b_{2}q_{k}+r_{k}$, there is such a
sequence terminating at $n$.

Since $(2C+1)\zeta_{1}^{k/2}>a_{1}+b_{2}+1$ and
$p_{k},q_{k},r_{k}>T\zeta_{1}^{n}$ for some fixed constant $T$, it follows
that for all $n\geq(2C+1)T\zeta_{1}^{3k/2}$, there is such a sequence
terminating at $n$. ∎

Finally we are able to show that all affable polynomials are congenial.

###### Proof of Theorem 5.

For our polynomial $x^{3}-ax^{2}-bx-c$ with $c=1$ and $a+b>1$ and at most one
real root, Theorem 24 has stated the existence of a real number $U$ uch that
for any positive integers $n,k$ with $k\geq 4$ and $n\geq U\eta_{1}^{3k/2}$
there is a positive sequence of length $k$ terminating at $n$.

Thus if there is no positive sequence of length $k+1$ terminating at $n$, it
follows that $n<U\eta_{1}^{3(k+1)/2}$.

Then by Theorem 18 it follows that the number of sequences of length $k$
terminating at $n$ is at most $\lceil
T\frac{n}{\eta_{1}^{3k/2}}\rceil^{2}<\lceil TU\eta_{1}^{3/2}\rceil^{2}.$ ∎

For now we leave open the following question.

######  Question 25.

For which positive integers $a,b,c$ with $c>0$ and $a+b>0$ is the recurrence
relation $x_{n}=ax_{n-1}+bx_{n-2}+cx_{n-3}$ congenial?

## References

  * [1] S. Spiro, “Problems that i would like somebody to solve,” 2020.