# Building a Swedish Open-Domain Conversational Language Model

Tobias Norlund
Chalmers University of Technology
Recorded Future
<EMAIL_ADDRESS>
Agnes Stenbom
Royal Institute of Technology
Schibsted Media Group
<EMAIL_ADDRESS>

###### Abstract

We present on-going work of evaluating the, to our knowledge, first large
generative language model trained to converse in Swedish, using data from the
online discussion forum Flashback. We conduct a human evaluation pilot study
that indicates the model is often able to respond to conversations in both a
human-like and informative manner, on a diverse set of topics. While data from
online forums can be useful to build conversational systems, we reflect on the
negative consequences that incautious application might have, and the need for
taking active measures to safeguard against them.

##  1 Introduction

Dialog is an important means through which machines can exhibit intelligence
toward humans, which is interesting from a general AI perspective. But dialog
also constitutes a natural interface for humans to interact with technology,
which opens up for a breadth of applications involving complex information
acquisition, automation of tasks and smart support systems. A promising
direction towards this goal is the development of open domain conversational
systems using large neural networks.

Early approaches to neural conversational systems rely on various forms of
Recurrent Neural Networks (RNN) trained autoregressively to model the textual
sequences Shang et al. (2015); Vinyals and Le (2015); Sordoni et al. (2015);
Serban et al. (2016). More recently, as large pre-trained Transformer networks
have come to dominate progress in NLP in general Devlin et al. (2019); Radford
(2018); Radford et al. (2019); Brown et al. (2020); Raffel et al. (2020),
approaches such as DialoGPT Zhang et al. (2020), Meena Adiwardana et al.
(2020) and Blender Roller et al. (2020) have proven the architecture’s
applicability in open domain dialog systems as well.

However, as the research effort is predominantly put into making progress on
English, the importance of making progress in other languages as well has been
noted Ruder (2020); Wali et al. (2020). Each language is its own unique
challenge for many reasons, but the difference in availability of resources is
a major one, in particular for data-driven methods. We argue this is also
important to keep the public debate on the risks and ethical aspects of large
scale language models open to non-English speaking communities. Toward those
ends, we present the first (to our knowledge) attempt to build a large scale
open domain dialog system in Swedish based on data from Flashback, one of the
largest social discussion forums in Sweden. We also present early indicative
results on a human evaluation to assess its response generation capabilities
across a wide range of topics.

##  2 Data and preprocessing

Flashback111http://www.flashback.org is a Swedish online forum that launched
in 1996 and has since grown to become one of the country’s most popular social
medias Internetstiftelsen (2019). In the various sub forums, a breadth of
topics are openly discussed including computers and programming, economics,
politics, sports and science. To the general public however, the forum is also
widely known for housing an anonymous safe haven for controversial subjects
such as prostitution, drugs and conspiracy theories Östman and Aschberg
(2015). Due to its consistent popularity over the last two decades, it
arguably today makes up Sweden’s biggest single source of general
conversational text.

On Flashback, posts are chronologically organized into threads. In a single
thread, the discussion is centered around a specific topic typically described
by a thread title. Acknowledging the potential for embedding undesired biases,
we have initially chosen to use a complete and unfiltered dump of the forum
for this study.

The data was tokenized into strings of BPE tokens Sennrich et al. (2016) using
a customly trained vocabulary. Due to Flashback’s organization of posts into a
single linear feed (unlike the tree structure on e.g. Reddit), it is common
that users quote the previous post they respond to, to avoid confusion. As a
quote holds important contextual information to a post, we chose to explicitly
include this in the way we formatted the threads. More details of how the data
was formatted into strings can be found in Appendix A.

##  3 Model

Following previous works on open-domain dialogue systems Zhang et al. (2020);
Adiwardana et al. (2020), we trained an auto-regressive language model using a
slightly modified Transformer Vaswani et al. (2017) decoder as proposed by
Radford et. al. Radford et al. (2019). That is, for an input sequence of
tokens $x_{1},...,x_{n}$, the language model is trained to maximize the
likelihood of the joint probability:

$p(x_{1},...,x_{n})=p(x_{1})\prod_{i=2}^{n}p(x_{i}|x_{i-1},...,x_{1})$ (1)

We denote our model _Flashback-GPT_ , where GPT is an acronym for Generative
Pre-trained Transformer as first coined by Radford et. al. Radford et al.
(2019). The hyper-parameters chosen are similar to those of the largest
variant of GPT-2 Radford et al. (2019), and are detailed in Table 1.

Number of layers | 48
---|---
Dimensionality | 1600
Feed-forward dim | 5400
Number of heads | 16
Number of parameters | 1.4B
Max context length | 400
Batch size | 512
Optimizer | Adam
Vocabulary size | 52,000
Table 1: Model hyperparameters

The model was trained on 16 Nvidia Tesla V100 SXM2 GPUs for 7 days, equivalent
to 86,250 gradient updates. The learning rate was increased linearly for the
first 5,000 steps up until $5\mathrm{e}{-5}$, after which it was kept
constant. We used the deepspeed Rasley et al. (2020) library to optimize
memory efficiency across the devices during training.

##  4 Evaluation

Evaluating natural language generation systems is known to be hard. Even
though it is common to conduct automatic evaluations due to their low cost, a
human evaluation often serves as an additional validation of the results.
However, designing a human evaluation to measure a specific quantity is also
not trivial since there is always room for interpretation among the human
annotators.

Therefore, we present a pilot study where the main aim is merely to get early
indications rather than definite results, and to guide the design of bigger
future studies. We design our pilot to measure our quantity of interest: To
which extent is the model capable of participating in social discussion forums
across a diverse set of topics?

To that end, we seek to measure two quantities: _humanlikeness_ and
_informativeness_. As language models can often be inconsistent and show lack
of commonsense knowledge, humanlikeness is supposed to answer if there is
anything in a response that seems off, suggesting it has not been written by a
human. However, a response can be humanlike but still uninformative. The
notion of ”informativeness” is particularly interesting in our setting as
forums can be relatively knowledge centric, and uninformative responses such
as _I don’t know_ add little to the discussion.

###  4.1 Study design

The study was designed as follows. We select a set of $N$ Flashback threads,
held out from training, to be used in the study. For each thread, we only take
the first two or three posts to limit the discussion context. We then, for
each thread, swap the last post for an alternative generated by the model.
Along with the originals, we now have $2N$ threads that we present (in
shuffled order) to human annotators. For each thread, we ask two binary
questions to measure humanlikeness and informativeness respectively:

  1. 1.

Is there any indication that the last message was not written by a human?

  2. 2.

Do you think that the last message adds information to the discussion?

This draws close resemblance to previous evaluations performed on English
systems Zhang et al. (2020); Adiwardana et al. (2020). In Zhang et. al. Zhang
et al. (2020), humans are asked to rank two alternative responses according to
_informativeness_ , _humanlikeness_ and _relevance_. In Adiwardana et. al.
Adiwardana et al. (2020), humans are instead asked the binary questions
whether a response ”makes sense” and also whether it is ”specific”, and the
average of the two (Sensibleness and Specificity Average - SSA) is found to
correlate with humanlikeness. For simplicity, we chose to directly ask for
humanlikeness instead of the SSA proxy questions. The complete annotator
guideline (Swedish) is included in Appendix B for reference.

For the pilot study, we collected a sample of $N=120$ Flashback threads,
stratified across 12 of the top level forums. We then formed two groups of
human annotators with three persons in each group. Each group was presented 60
threads with generated responses, and 60 original, with no overlap. The
threads included were randomly chosen, except for a few criteria that we
employed to prevent the annotators from exploiting obvious surface patterns
when answering question 1.

  * •

As has been noted previously Roller et al. (2020), beam search decoding
strategies have a tendency to generate shorter responses over longer. We
decided to only include threads where the last (human written) response is at
most 200 characters.

  * •

Since the model supports a maximum sequence length of 400 tokens, we exclude
threads where the context is longer than 350 tokens, to leave some room for
the generated response.

  * •

Since the model often fails to generate correct quotes of previous responses,
we remove any quotes from the last (human written) response, and force the
model not to generate quotes as well.

We include a subset of the threads (both with generated and ground truth
responses) in Appendix C.

###  4.2 Decoding

The decoding strategy used to generate responses from neural language models
is an important part of the system as a whole Roller et al. (2020). While the
commonly employed beam search algorithm is optimizing the joint likelihood for
the whole generated sequence, its outputs are known to be generic, unspecific
and repetitive Holtzman et al. (2020); See et al. (2019). We chose to use a
beam sampling strategy, where we at each step, for each beam, sample from the
(re-normalized) top 50 predicted vocabulary items. This struck a good balance
between generating short uninformative responses vs longer incoherent
ramblings. We used a beam size of 6. The model has a tendency to generate
responses such as ”duplicate thread, locking //mod”, which are commonly found
on Flashback but are not very interesting for this study. We try to circumvent
this by banning the generation of certain distinguishing words, such as ”mod”.
Finally, to avoid repetitions we also prevent the model from generating
repetitions of any 3-grams occurring in the context, or in the generated
sequence thus far.

##  5 Results and Discussion

| Flashback-GPT | Human
---|---|---
Humanlike | 68% (48%) | 95% (79%)
Informative | 48% (52%) | 83% (74%)
Humanlike + informative | 46% | 83%
Table 2: Pilot study results. _Humanlike_ is the percentage where the majority
response to the first question is _no_. _Informative_ is the percentage where
the majority response to the second question is _yes_. Numbers in parentheses
are percentages of the $120$ threads where all three annotators agreed Figure
1: Ratio of responses that were deemed both humanlike and informative for each
of the evaluated forums

Results from the study are shown in Table 2. We judge a thread’s humanlikeness
and informativeness based on the majority response from the three annotators.
We also report the percentage of threads where all annotators agreed in their
responses.

Unsurprisingly, ground truth human responses display a high ratio of
humanlikeness, consolidated by a relatively high degree of annotator
agreement. Our model’s responses also show signs of humanlikeness, as
suggested by the fact that 68% of its generated responses were deemed
plausible to be human-written. We note however that the annotator agreement is
significantly lower compared to ground truth responses, suggesting we could
further clarify the humanlikeness question we ask the human annotators.

The model shows less strength on our measure of informativeness, with only 48%
of the model’s generated responses were deemed informative to the discussion.
If we compare the amount of threads where the responses were both deemed
humanlike and informative, the model’s ratio drops to 46% compared to 83% for
the ground truth responses. While our sample size is too small to draw any
statistically significant conclusions, Figure 1 shows the distribution of
humanlike + informative responses over their top-level forums. Interestingly,
the top-3 most popular forums (Society, Politics and Culture & media), which
together comprise 41% of the training data, all perform below average.

Qualitative feedback from the annotators highlight how the model tends to
respond with short and straight answers, less prone to vent thoughts and
opinions compared to human responses. Common failure modes include completely
misunderstanding the question being asked, or change of topic to a related but
irrelevant one.

Reflecting on the design of the study, we found very few responses were deemed
informative but not humanlike (2 of the generated, 0 ground truth). If the
main purpose of a future study is to measure both humanlikeness and
informativeness, the question of informativeness might be sufficient.

##  6 Broader implications

Conversational models such as that presented in this paper can be understood
as part of a broader transformation of communication. As argued by Guzman and
Lewis (2020), we are now moving away from the traditional view of
communication as anchored in human such. How we apply and evaluate
conversational models going forward may come to alter the way we relate to
each other as communicators, and ultimately, humans. There is need for
informed discussion around what constitutes desirable use. While highlighting
the risks of these emerging technologies could be considered detrimental, we
believe it to be an important means towards enabling the inclusion of diverse
perspectives in this discussion.

A prominent issue related to NLP is found in the notion of bias. Explicit and
implicit biases concerning gender, race or disability can be embedded in e.g.
text corpora (Caliskan et al., 2017), word embeddings (Bolukbasi et al., 2016)
and generative models (Sheng et al., 2019). Employing biased conversational
models risks scaling systematic discrimination of various groups in society.

When developing conversational technologies, we must acknowledge that they can
be used for malicious purposes. As generative language technology improves and
grows in Swedish, so will its ability to manipulate and deceive at scale. As
noted by the Swedish Defence Research Agency (FOI), recent developments within
generative language technology present risks of increased computer-generated
false news and comments – predominately on social media – possibly posing a
national security threat (Lundén et al., 2021).

Potential harm must also be considered on the individual level. In 2020, a
GPT-3-powered Brown et al. (2020) bot engaged in Reddit-forums with 30 million
users about sensitive topics such as suicide and conspiracy theories (Heaven,
2020). With the indicative model performance demonstrated in this article,
such human-machine communication could soon transpire in Swedish.

##  7 Conclusions and Future work

We demonstrate that Flashback can provide a base on which to build general
conversational systems in Swedish. While our early results suggest the model
is often capable to converse across a diverse set of topics, more work remains
to examine its utility on various conversational tasks. We also believe
developing methods for grounding the responses in additional data is an
interesting direction to further the performance on informativeness in
particular. However, we also believe particular care should be taken as the
underlying data is known to contain toxic content. This points to the
importance of putting our model through further scrutiny in following work, to
better understand its biases, how they are manifested in downstream tasks, and
how they can be mitigated. Towards those ends, we intend to make the model
available for such purposes, and more information is available at
https://github.com/TobiasNorlund/
flashback-gpt

## Acknowledgments

This work was partially supported by the Wallenberg AI, Autonomous Systems and
Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation.
The computations were enabled by resources provided by the Swedish National
Infrastructure for Computing (SNIC) at Chalmers Centre for Computational
Science and Engineering (C3SE) partially funded by the Swedish Research
Council through grant agreement no. 2018-05973.

## References

  * Adiwardana et al. (2020) Daniel Adiwardana, Minh-Thang Luong, David R. So, Jamie Hall, Noah Fiedel, Romal Thoppilan, Zi Yang, Apoorv Kulshreshtha, Gaurav Nemade, Yifeng Lu, and Quoc V. Le. 2020.  Towards a human-like open-domain chatbot.
  * Bolukbasi et al. (2016) Tolga Bolukbasi, Kai-Wei Chang, James Zou, Venkatesh Saligrama, and Adam Kalai. 2016\.  Man is to computer programmer as woman is to homemaker? debiasing word embeddings.  In _Proceedings of the 30th International Conference on Neural Information Processing Systems_ , NIPS’16, page 4356–4364, Red Hook, NY, USA. Curran Associates Inc.
  * Brown et al. (2020) Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020.  Language models are few-shot learners.
  * Caliskan et al. (2017) Aylin Caliskan, Joanna J. Bryson, and Arvind Narayanan. 2017.  Semantics derived automatically from language corpora contain human-like biases.  _Science_ , 356(6334):183–186.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Guzman and Lewis (2020) Andrea L Guzman and Seth C Lewis. 2020.  Artificial intelligence and communication: A human–machine communication research agenda.  _New Media & Society_, 22(1):70–86.
  * Heaven (2020) Will Douglas Heaven. 2020.  A gpt-3 bot posted comments on reddit for a week and no one noticed.
  * Holtzman et al. (2020) Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. 2020.  The curious case of neural text degeneration.
  * Internetstiftelsen (2019) Internetstiftelsen. 2019.  Svenskarna och internet 2019.
  * Lundén et al. (2021) Jenny Lundén, Anders Melander, Elin Hellquist, Björn Ottosson, Liselotte Steen, and Anders Strindberg. 2021.  Strategisk utblick 9 framtida hot.
  * Radford (2018) Alec Radford. 2018.  Improving language understanding by generative pre-training.
  * Radford et al. (2019) Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. 2019.  Language models are unsupervised multitask learners.
  * Raffel et al. (2020) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. 2020.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _Journal of Machine Learning Research_ , 21(140):1–67.
  * Rasley et al. (2020) Jeff Rasley, Samyam Rajbhandari, Olatunji Ruwase, and Yuxiong He. 2020.  Deepspeed: System optimizations enable training deep learning models with over 100 billion parameters.  In _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, page 3505–3506, New York, NY, USA. Association for Computing Machinery.
  * Roller et al. (2020) Stephen Roller, Emily Dinan, Naman Goyal, Da Ju, Mary Williamson, Yinhan Liu, Jing Xu, Myle Ott, Kurt Shuster, Eric M. Smith, Y-Lan Boureau, and Jason Weston. 2020.  Recipes for building an open-domain chatbot.
  * Ruder (2020) Sebastian Ruder. 2020.  Why You Should Do NLP Beyond English.  http://ruder.io/nlp-beyond-english.
  * See et al. (2019) Abigail See, Stephen Roller, Douwe Kiela, and Jason Weston. 2019.  What makes a good conversation? how controllable attributes affect human judgments.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 1702–1723, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Sennrich et al. (2016) Rico Sennrich, Barry Haddow, and Alexandra Birch. 2016.  Neural machine translation of rare words with subword units.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1715–1725, Berlin, Germany. Association for Computational Linguistics.
  * Serban et al. (2016) Iulian V. Serban, Alessandro Sordoni, Yoshua Bengio, Aaron Courville, and Joelle Pineau. 2016.  Building end-to-end dialogue systems using generative hierarchical neural network models.  In _Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence_ , AAAI’16, page 3776–3783. AAAI Press.
  * Shang et al. (2015) Lifeng Shang, Zhengdong Lu, and Hang Li. 2015.  Neural responding machine for short-text conversation.  In _Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 1577–1586, Beijing, China. Association for Computational Linguistics.
  * Sheng et al. (2019) Emily Sheng, Kai-Wei Chang, Premkumar Natarajan, and Nanyun Peng. 2019.  The woman worked as a babysitter: On biases in language generation.  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 3407–3412, Hong Kong, China. Association for Computational Linguistics.
  * Sordoni et al. (2015) Alessandro Sordoni, Michel Galley, Michael Auli, Chris Brockett, Yangfeng Ji, Margaret Mitchell, Jian-Yun Nie, Jianfeng Gao, and Bill Dolan. 2015.  A neural network approach to context-sensitive generation of conversational responses.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Ł ukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  In _Advances in Neural Information Processing Systems_ , volume 30, pages 5998–6008. Curran Associates, Inc.
  * Vinyals and Le (2015) Oriol Vinyals and Quoc Le. 2015.  A neural conversational model.
  * Wali et al. (2020) Esma Wali, Yan Chen, Christopher Mahoney, Thomas Middleton, Marzieh Babaeianjelodar, Mariama Njie, and Jeanna Neefe Matthews. 2020.  Is machine learning speaking my language? a critical look at the nlp-pipeline across 8 human languages.
  * Zhang et al. (2020) Yizhe Zhang, Siqi Sun, Michel Galley, Yen-Chun Chen, Chris Brockett, Xiang Gao, Jianfeng Gao, Jingjing Liu, and Bill Dolan. 2020.  Dialogpt: Large-scale generative pre-training for conversational response generation.  In _ACL, system demonstration_.
  * Östman and Aschberg (2015) Karin Östman and Richard Aschberg. 2015.  Flashback – ett laglöst land.

##  Appendix Appendix A Flashback data details

The data needs to be converted into a textual string format for it to be
compatible with a standard language model. To this end, each thread was
formatted into textual _records_. Listing 1 provides an example of a formatted
data record used to train the model. A record can be at most 400 tokens, and
as such, threads are often broken up into multiple records. This means the
model will in general not have the full thread context when predicting the
next message.

⬇

1Dator och IT > Hårdvara: PC

2Luft eller vattenkylning till cpu

3

4[user1]:

5Jag har lite beslutsångest till vilken kylning jag ska satsa på till min AMD
Phenom II X4 965 AM3.

6Denna fläkten http://www.komplett.se/k/ki.aspx?sku=456730 eller är det
smartare att satsa på vattenkylning?

7

8[user2]:

9Citat: [user1]

10 Jag har lite beslutsångest till vilken kylning jag ska satsa på till min
AMD Phenom II X4 965 AM3.

11 Denna fläkten http://www.komplett.se/k/ki.aspx?sku=456730 eller är det
smartare att satsa på vattenkylning?

12Det där var väl ett jävla åbäk iaf, är du säker på att det inte finns bättre
för typ halva priset? Typ Noctua eller liknande?

13

14[user3]:

15En vettig fråga är: Vad skall du göra med datorn? Extrem överklockning? Få
en tyst dator?

Listing 1: Example of a formatted training record. The usernames are
anonymized.

Table 3 details the amount of data from each of the top level forums that was
used for training. The dump was collected in September 2020 and in total the
data comprised 23.5 GB of raw formatted text.

Top-level forum (swedish) | Top-level forum (english) | Num threads | Num posts
---|---|---|---
Samhälle | Society | 230,931 | 8,681,841
Politik | Politics | 123,031 | 7,578,865
Kultur & Media | Culture & Media | 165,929 | 6,495,860
Vetenskap & humaniora | Science & Humanities | 225,139 | 5,130,519
Dator och IT | Computer & IT | 334,931 | 4,833,468
Sport & träning | Sports & training | 81,922 | 4,475,793
Hem, bostad & familj | Home & family | 158,819 | 4,055,688
Droger | Drugs | 137,870 | 3,551,768
Övrigt | Others | 75,735 | 2,164,237
Livsstil | Lifestyle | 81,750 | 2,060,600
Sex | Sex | 49,512 | 1,335,657
Ekonomi | Economy | 68,078 | 1,327,001
Mat, dryck & tobak | Food, drink & tobacco | 51,133 | 1,286,707
Fordon & trafik | Automotive & traffic | 68,078 | 1,070,619
Om Flashback | About Flashback | 73,910 | 486,536
Resor | Travels | 29,514 | 478,150
- | Forum unknown | 181 | 71,933
Total |  | 1,956,463 | 55,085,242
Table 3: Flashback training data statistics

##  Appendix Appendix B Annotation guideline for human evaluation

##  Appendix Appendix C Examples from study

In the following examples, the last response is generated by the model.
Usernames are anonymized.

⬇

1Fordon & trafik > Motorcyklar och mopeder

2Off road MC

3

4[user1]:

5När jag blir äldre vill jag köra Off road MC, typ Yamaha WR250X verkar nice.

6Annars finns det yamaha XT125X. men med mindre klenare motor.

7Det är ju bäst att skaffa mc kort med obegränsad motoreffekt, så jag för köra
alla typer.

8Jag är 175 cm just nu.

91. Hade jag kunnat ha en Yamaha WR250X, så jag inte är för kort?

10någon som vet?

11

12[user2]:

13när du blir äldre?

14e du över 18..?

15men nej, tror inte du e för kort att köra off road mc

16

17[user3]:

18Vad ska du ha den till?

⬇

1Vetenskap & humaniora > Fysik, matematik och teknologi > Matematiska och
naturvetenskapliga uppgifter

2ekvationer som omformas med formler-ma d

3

4[user1]:

55sin4x=3sin2x

6lös ekvationen och svara med en decimal?

7Jag vet att jag ska flytta över HL i VL. Men sedan vet jag ej vad jag ska
göra.

8

9[user2]:

10sin(2a) = 2sin(a)cos(a) giver ju i princip svaret.

11

12[user3]:

13Du skall multiplicera båda leden med cos(a).

⬇

1Resor > Övriga resediskussioner

2Beställa saker som ligger i planet när jag sätter mig!

3

4[user1]:

5Heellu, har en fråga här.. När man beställer saker ifrån tax-free saken så
det ligger i sätet när man kommer in i planet, måste man vara 20 och över för
vodka o sånt då?

6Är inte mer än 19 när jag ska åka, vore gûtt att få med sig en flaska ner dit
man nu ska =)

7

8[user2]:

9Eftersom du är 19 så misstänker jag att du ska ner till nåt varmt partyställe
runt medelhavet, har jag rätt? I så fall är det billigare att köpa den där
flaskan på plats och de bryr sig inte om din ålder.

10

11[user3]:

12Du behöver inte vara 20 för att köpa sprit i tax-freen.

Below are the same examples, but translated to English

⬇

1Automotive & traffic > Motorcycles and mopeds

2Off road MC

3

4[user1]:

5When I get older I want to drive Off road MC, like Yamaha WR250X seems nice.

6Otherwise there is yahama XT125X. but with a weaker engine.

7It is best to get the mc license with unlimited power, so I can drive all
types.

8I’m 175cm right now.

91. Can I have a Yamaha WR250X, or am I too short?

10anyone who knows?

11

12[user2]:

13when you get older?

14are you above 18..?

15but no, don’t think you’re too short to drive off road mc

16

17[user3]:

18What are you gonna use it for?

⬇

1Science & Humanities > physics, mathematics and technology > Mathematical and
natural science exercises

2reshaping equations with forumlas-ma d

3

4[user1]:

55sin4x=3sin2x

6solve the equation and answer with one decimal?

7I know I should move right-side over to left-side. But then I don’t know what
to do.

8

9[user2]:

10sin(2a) = 2sin(a)cos(a) basically gives you the answer

11

12[user3]:

13You should multiply both sides with cos(a).

⬇

1Travels > Other travel discussions

2Order things to my plane seat

3

4[user1]:

5Heellu, got a question here.. When you order stuff from the tax-free thing
they lie on your seat when you board the plane, do you have to be 20 or above
for vodka and such then?

6Won’t be more than 19 when I’m going, would be sweet to bring a bottle down
to the destination =)

7

8[user2]:

9Since you are 19 I’m suspecting you’re going down to some warm party place
around the Mediterranean, am I right? In such case it is cheaper to buy that
bottle in-place and they won’t care about your age.

10

11[user3]:

12You don’t need to be 20 to buy spirits in the tax-free.


#  $p$-ary sequences with six-valued cross-correlation function: a new
decimation of Niho type

Yuhua Sun1, Hui Li1, Zilong Wang2, and Tongjiang Yan3,4
1 Key Laboratory of Computer Networks and Information Security,
Xidian University, Xi’an 710071, Shaanxi, China
2 State Key Laboratory of Integrated Service Networks,
Xidian University, Xi’an, 710071, Shaanxi, China
3 College of Mathematics and Computational Science,
China University of Petroleum Dongying 257061, Shandong, China
4 State Key Laboratory of Information Security (Institute of Software,
Chinese Academy of Sciences), Beijing 100049,China

###### Abstract

For an odd prime $p$ and $n=2m$, a new decimation
$d=\frac{(p^{m}-1)^{2}}{2}+1$ of Niho type of $m$-sequences is presented.
Using generalized Niho’s Theorem, we show that the cross-correlation function
between a $p$-ary $m$-sequence of period $p^{n}-1$ and its decimated sequence
by the above $d$ is at most six-valued and we can easily know that the
magnitude of the cross correlation is upper bounded by $4\sqrt{p^{n}}-1$.

Index Terms. $p$-ary $m$-sequence, Niho type, cross-correlation.

00footnotetext: The work is supported by the National Natural Science
Foundation of China (No.60772136), Shandong Provincial Natural Science
Foundation of China (No. ZR2010FM017), the Fundamental Research Funds for the
Central Universities(No.K50510010012) and the open fund of State Key
Laboratory of Information Security(Graduate University of Chinese Academy of
Sciences)(No.F1008001).

##  1 Introduction

It is of great interest to find a decimation value $d$ such that the cross-
correlation between a $p$-ary $m$-sequence $\\{s_{t}\\}$ of period $p^{n}-1$
and its decimation $\\{s_{dt}\\}$ is low. For the case
$\mathrm{gcd}(d,p^{n}-1)=1$, the decimated sequence $\\{s_{dt}\\}$ is also an
$m$-sequence of period $p^{n}-1$. Basic results on the cross-correlation
between two $m$-sequences can be found in [3], [5], [8] and [10]. For the case
$\mathrm{gcd}(d,p^{n}-1)\neq 1$, the reader is referred to [7], [6], and [1].

Let $p$ be a prime and $n=2m$. The cross correlation functions for the type of
decimations $d\equiv 1\ (\mathrm{mod}\ p^{m}-1)$ were first studied by Niho
[8] named as Niho type of decimations. In [8], for $p=2$ and $d=s(p^{m}-1)+1$,
Niho converted the problem of finding the values of cross-correlation
functions into the problem of determining the number of solutions of a system
of equations . This result is called Niho’s Theorem. In 2006, Rosendahl [9]
generalized Niho’s Theorem to nonbinary sequences. In 2007, Helleseth et al.
[4] proved that the cross correlation function between two $m$-sequences that
differ by a decimation $d$ of Niho type is at least four-valued.

When $d=2p^{m}-1\equiv 1\ (\mathrm{mod}\ p^{m}-1)$, the cross correlation
function between a $p$-ary $m$-sequence $\\{s_{t}\\}$ of period $p^{2m}-1$ and
its decimated sequence $\\{s_{dt}\\}$ is four-valued, which was originally
given by Niho [8] for the case $p=2$ and by Helleseth [3] for the case $p>2$.
And when $d=3p^{m}-2$, the cross correlation function between two
$m$-sequences that differ by $d$ is at most six-valued, especially, for $p=3$,
the cross correlation function is at most five-valued [9].

In this note, we study a new decimation $d=\frac{(p^{m}-1)^{2}}{2}+1$ of Niho
type. Employing generalized Niho’s Theorem, we show that the cross-correlation
function between a $p$-ary $m$-sequence and its decimated sequence by $d$ is
at most six-valued.

The rest of this note is organized as follows. Section 2 presents some
preliminaries and definitions. Using generalized Niho’s Theorem, we give an
alternative proof of a result by Helleseth [3] where
$d=\frac{(p^{m}-1)(p^{m}+1)}{2}+1$ in section 3. A new decimation
$d=\frac{(p^{m}-1)^{2}}{2}+1$ of Niho type is given in section 4. We prove
that the cross correlation function between a $p$-ary $m$-sequence and its
decimated sequence by $d$ takes at most six values.

##  2 Preliminaries

We will use the following notation in the rest of this note. Let $p$ be an odd
prime, $\mathrm{GF}(p^{n})$ the finite field with $p^{n}$ elements and
$\mathrm{GF}(p^{n})^{*}=\mathrm{GF}(p^{n})\backslash\\{0\\}$. The trace
function $\mathrm{Tr}_{m}^{n}$ from the field $\mathrm{GF}(p^{n})$ onto the
subfield $\mathrm{GF}(p^{m})$ is defined as

$\mathrm{Tr}_{m}^{n}(x)=x+x^{p^{m}}+x^{p^{2m}}+\cdots+x^{p^{(l-1)m}},$

where $l=\frac{n}{m}$ is an integer.

We may assume that a $p$-ary $m$-sequence $\\{s_{t}\\}$ of period $p^{n}-1$ is
given by

$s_{t}=\mathrm{Tr}_{1}^{n}(\alpha^{t}),$

where $\alpha$ is a primitive element of the finite field $\mathrm{GF}(p^{n})$
and $\mathrm{Tr}_{1}^{n}$ is the trace function from $\mathrm{GF}(p^{n})$ onto
$\mathrm{GF}(p)$. The periodic cross correlation function $C_{d}(\tau)$
between$\\{s_{t}\\}$ and its decimated sequence $\\{s_{dt}\\}$ is defined as

$C_{d}(\tau)=\Sigma_{t=0}^{p^{n}-2}\omega^{s_{t+\tau}-s_{dt}},$

where $\omega=e^{\frac{2\pi\sqrt{-1}}{p}}$ and $0\leq\tau\leq p^{n}-2$.

We will always assume that $n=2m$ is even in this note unless otherwise
specified.

##  3 An alternative proof of a known result

For $p=2$, Niho [8] presented Niho’s Theorem about decimations of Niho type of
$m$-sequences. Rosendahl [9] generalized this result as follows.

###### Lemma 1

(generalized Niho’s Theorem) [9] Let $p$, $n$, and $m$ be defined as in
section 2. Assume that $d\equiv 1\ (\mathrm{mod}\ p^{m}-1)$, and denote
$s=\frac{d-1}{p^{m}-1}$. Then when $y={\alpha}^{\tau}$ runs through the
nonzero elements of the field $\mathrm{GF}(p^{n})$, $C_{d}(\tau)$ assumes
exactly the values

$-1+\left(N(y)-1\right)\cdot p^{m},$

where $N(y)$ is the number of common solutions of

$\displaystyle x^{2s-1}+y^{p^{m}}x^{s}+yx^{s-1}+1$ $\displaystyle=0,$
$\displaystyle x^{p^{m}+1}$ $\displaystyle=1.$

In 1976, Helleseth [3] proved the following result. Here, using the
generalized Niho’s Theorem, we give a simple proof.

###### Theorem 1

[3] Let the symbols be defined as in section 2, $p$ be an odd prime and
$d=\frac{p^{n}-1}{2}+1$. Then $C_{d}(\tau)\in\\{-1-p^{m}$, $-1$, $-1+p^{m}$,
$-1+\frac{p^{m}-1}{2}p^{m},-1+\frac{p^{m}+1}{2}p^{m}\\}$.

Proof of Theorem 1. Since
$d=\frac{p^{n}-1}{2}+1=\frac{p^{m}+1}{2}(p^{m}-1)+1$, we get
$s=\frac{d-1}{p^{m}-1}=\frac{p^{m}+1}{2}$. By Lemma 1, we have

$C_{d}(\tau)=-1+\left(N(y)-1\right)\cdot p^{m},$

where $y=\alpha^{\tau}$, $0\leq\tau\leq p^{n}-2$, and $N(y)$ is the number of
common solutions of

$\displaystyle
x^{(p^{m}+1)-1}+y^{p^{m}}x^{\frac{p^{m}+1}{2}}+yx^{\frac{p^{m}+1}{2}-1}+1$
$\displaystyle=0,$ (1) $\displaystyle x^{p^{m}+1}$ $\displaystyle=1.$ (2)

Note that Eq. (2) implies

$\displaystyle x^{\frac{p^{m}+1}{2}}=1$ (3)

or

$\displaystyle x^{\frac{p^{m}+1}{2}}=-1.$ (4)

Substituting (3) and (4) into (1) respectively, we get

$C_{d}(\tau)=-1+\left(N_{1}(y)+N_{-1}(y)-1\right)\cdot p^{m},$

where $N_{1}(y)$ is the number of the common solutions of

$(3.1.1)\ \ \left\\{\begin{array}[]{ll}(y^{p^{m}}+1)x+(y+1)=0,\\\
x^{\frac{p^{m}+1}{2}}=1,\end{array}\right.$

and $N_{-1}(y)$ is the number of solutions of

$(3.1.2)\ \ \left\\{\begin{array}[]{ll}(y^{p^{m}}-1)x+(y-1)=0,\\\
x^{\frac{p^{m}+1}{2}}=-1.\end{array}\right.$

Obviously, for $y\neq\pm 1$, $0\leq N_{1}(y)+N_{-1}(y)\leq 2.$

Let $y=1$. First, it is straightforward to get $N_{-1}(1)=\frac{p^{m}+1}{2}$.
Second, we see that $x=-1$ is the only solution of (3.1.1) for $p^{m}+1\equiv
0\ \mathrm{mod}\ 4$ and $N_{1}(1)=0$ for $p^{m}+1\equiv 2\ \mathrm{mod}\ 4$.
Hence, we have

$N_{1}(1)+N_{-1}(1)=\left\\{\begin{array}[]{ll}1+\frac{p^{m}+1}{2},\ \ \
\mathrm{if}\ p^{m}+1\equiv 0\ \mathrm{mod}\ 4,\\\ \frac{p^{m}+1}{2},\ \ \ \ \
\ \ \ \mathrm{if}\ p^{m}+1\equiv 2\ \mathrm{mod}\ 4.\end{array}\right.$

Similarly, for $y=-1$, we have

$N_{1}(-1)+N_{-1}(-1)=\left\\{\begin{array}[]{ll}\frac{p^{m}+1}{2},\ \ \ \ \ \
\ \ \mathrm{if}\ p^{m}+1\equiv 0\ \mathrm{mod}\ 4,\\\ 1+\frac{p^{m}+1}{2},\ \
\ \mathrm{if}\ p^{m}+1\equiv 2\ \mathrm{mod}\ 4.\end{array}\right.$

The result follows. $\Box$

In Theorem 1, the value $s$ of Niho type decimation $d$ is equal to
$\frac{p^{m}+1}{2}$ corresponding to Lemma 1. Motivated by the above proof, we
take $s$ as the value $\frac{p^{m}-1}{2}$, a new decimation of Niho type will
be presented, and cross correlation values will be determined in the following
section.

##  4 A new decimation of Niho type

In this section, we give a new decimation $d$ of Niho’s type and we show that
the cross correlation function between a $p$-ary $m$-sequence and its
decimated sequence by $d$ is at most six-valued.

###### Theorem 2

Let the symbols be defined as in section 2. Let $d=\frac{(p^{m}-1)^{2}}{2}+1$.
Then $C_{d}(\tau)\in\\{-1+(j-1)\cdot p^{m}|\ 0\leq j\leq 5\\}$ is at most six-
valued.

Proof of Theorem 2. since
$d=\frac{(p^{m}-1)^{2}}{2}+1=\frac{p^{m}-1}{2}\cdot(p^{m}-1)+1\equiv 1\
\mathrm{mod}\ (p^{m}-1),$ we know that the value $s$ corresponding to that in
Lemma 1 is $\frac{p^{m}-1}{2}$. By the same argument as in Theorem 1, we get

$C_{d}(\tau)=-1+\left(N_{1}(y)+N_{-1}(y)-1\right)\cdot p^{m},$

where $N_{1}(y)$ is the number of solutions of

$(4.1.1)\ \ \left\\{\begin{array}[]{ll}x^{3}+y^{p^{m}}x^{2}+yx+1=0,\\\
x^{\frac{p^{m}+1}{2}}=1,\end{array}\right.$

and $N_{-1}(y)$ is the number of solutions of

$(4.1.2)\ \ \left\\{\begin{array}[]{ll}x^{3}-y^{p^{m}}x^{2}-yx+1=0,\\\
x^{\frac{p^{m}+1}{2}}=-1.\end{array}\right.$

By the basic algebraic theorem, we know that $0\leq N_{1}(y)\leq 3$ and $0\leq
N_{-1}(y)\leq 3$, i.e., $0\leq N_{1}(y)+N_{-1}(y)\leq 6$. Further, we will
prove $0\leq N_{1}(y)+N_{-1}(y)\leq 5$, i.e., we will prove
$N_{1}(y)+N_{-1}(y)\neq 6$.

Suppose that $N_{1}(y)+N_{-1}(y)=6$. Then $N_{1}(y)=3$ and $N_{-1}(y)=3$,
i.e., both (4.1.1) and (4.1.2) have three solutions. Now, for $i=1,2,3$, let
$x_{i}$ and $x_{i}^{\ast}$ be the solutions of (4.1.1) and (4.1.2),
respectively. Since $x_{i}$ satisfies $x^{\frac{p^{m}+1}{2}}=1$ and
$x_{i}^{\ast}$ satisfies $x^{\frac{p^{m}+1}{2}}=-1$, we know that there exists
some even integer $j_{i}$ satisfying $x_{i}=\alpha^{j_{i}(p^{m}-1)}$ and that
there exists some odd integer $j_{i}^{\ast}$ satisfying
$x_{i}^{\ast}=\alpha^{j_{i}^{\ast}(p^{m}-1)}$, where $i=1,2,3$.
Simultaneously, since $x_{i}$ and $x_{i}^{\ast}$ satisfy the first equations
of (4.1.1)and (4.1.2) respectively, we have

$\displaystyle\prod\limits_{i=1}^{3}x_{i}$
$\displaystyle=\alpha^{(p^{m}-1)\sum\limits_{i=1}^{3}j_{i}}=-1,$
$\displaystyle\prod\limits_{i=1}^{3}x_{i}^{\ast}$
$\displaystyle=\alpha^{(p^{m}-1)\sum\limits_{i=1}^{3}j_{i}^{\ast}}=-1.$

By multiplying the above two equations, we get

$\prod\limits_{i=1}^{3}x_{i}\prod\limits_{i=1}^{3}x_{i}^{\ast}=\alpha^{(p^{m}-1)(\sum\limits_{i=1}^{3}j_{i}+\sum\limits_{i=1}^{3}j_{i}^{\ast})}=1,$

and induce
$p^{m}+1|\sum\limits_{i=1}^{3}j_{i}+\sum\limits_{i=1}^{3}j_{i}^{\ast}$. This
contradicts to the fact that $p^{m}+1$ is even but
$\sum\limits_{i=1}^{3}j_{i}+\sum\limits_{i=1}^{3}j_{i}^{\ast}$ is odd.
Therefore, we get $N_{1}(y)+N_{-1}(y)\neq 6$, i.e., $0\leq
N_{1}(y)+N_{-1}(y)\leq 5$. The result follows. $\Box$

###### Remark 1

The decimated sequence $\\{s_{dt}\\}$ in Theorem 2 is not necessarily an
$m$-sequence. In fact,
$d=\frac{p^{m}-1}{2}(p^{m}-1)+1\equiv\frac{p^{m}-1}{2}(-2)+1\equiv 3\
\mathrm{mod}\ (p^{m}+1)$. For $p\equiv-1\ \mathrm{mod}\ 3$, $m$ odd, we know
that $\mathrm{gcd}(d,p^{n}-1)=3$, $\\{s_{dt}\\}$ is not an $m$-sequence. For
the other case, $\mathrm{gcd}(d,p^{n}-1)=1$, and $\\{s_{dt}\\}$ is an
$m$-sequence.

###### Remark 2

Theoretically, the number of the values of $C_{d}(\tau)$ can not be reduced to
less than 6. Following is an example whose cross correlation function between
an $m$-sequence and its decimated sequence by $d$ has exactly six values.

###### Example 1

Let $p=3$, $n=6$, $m=3$ and $d=\frac{(p^{m}-1)^{2}}{2}+1=339$. The polynomial
$f(x)=x^{6}+x^{5}+2$ is primitive over $\mathrm{GF}(3)$. Let $\alpha$ be a
root of $f(x)$, then $s_{t}=\mathrm{Tr}_{1}^{6}(\alpha^{t})$,
$s_{dt}=\mathrm{Tr}_{1}^{6}(\alpha^{339t})$. Computer experiment gives the
following cross correlation values:

$\begin{array}[]{lclc}-1-3^{3}&\mathrm{occurs}&246&\mathrm{times},\\\
-1&\mathrm{occurs}&284&\mathrm{times},\\\
-1+3^{3}&\mathrm{occurs}&144&\mathrm{times},\\\ -1+2\cdot
3^{3}&\mathrm{occurs}&42&\mathrm{times},\\\ -1+3\cdot
3^{3}&\mathrm{occurs}&3&\mathrm{times},\\\ -1+4\cdot
3^{3}&\mathrm{occurs}&9&\mathrm{times}.\end{array}$

## Conclusion

In this note, using generalized Niho’s Theorem, we give an alternative proof
of a known result. By changing the form of the known decimation factor, we
give a new decimation $d=\frac{(p^{m}-1)^{2}}{2}+1$ of Niho type. We prove
that the cross correlation function between a $p$-ary $m$-sequence of period
$p^{n}-1$ and its decimated sequence by the value $d$ is at most six-valued,
and we can easily see that the magnitude of the cross correlation values is
upper bounded by $4\sqrt{p^{n}}-1$.

## References

  * [1] S.-T. Choi, J.-S. No, H. Chung, On the cross-correlation of a ternary $m$-sequence of period $3^{4k+2}-1$ and its decimated sequence by $\frac{(3^{2k+1}+1)^{2}}{8}$, _ISIT 2010_ , Austin, Texas, U.S.A., June 13-18, 2010.
  * [2] H. Dobbertin, T. Helleseth, P.V. Kumar, and H. Martinsen, Ternary $m$-sequences with three-valued cross-correlation function:new decimations of Welch and Niho type, _IEEE Trans. Inf. Theory,_ vol. 47 (2001), pp. 1473-1481.
  * [3] T. Helleseth, Some results about the cross-correlation function between two maximal linear sequences. _Discrete Math_. , vol. 16 (1976) pp. 209-232.
  * [4] T. Helleseth, J. Lahtonen, and P. Rosendahl, On Niho type cross-correlation functions of $m$-sequences, _Finite Field and Their Applications_ , vol. 13 (2007) pp. 305-317.
  * [5] T. Helleseth and P. V. Kumar, Sequences with low correlation, In V. S. Pless and W.C. Huffman (eds.), Handbook of Coding Theory, Elsevier Science (1998), pp. 1765-1853.
  * [6] Z. Hu, Z. Li, D. Mills, E. N. Müller, W. Sun, W. Willems, Y. Yang, and Z. Zhang, On the cross-correlation of sequences with the decimation factor $d=\frac{p^{n}+1}{p+1}-\frac{p^{n}-1}{2},$ _Applicable Algebra in Engineering, Communication and Computing,_ vol. 12 (2001) pp. 255-263.
  * [7] E.N. Müller, On the cross-correlation of sequences over $\mathrm{GF}(p)$ with short periods, _IEEE Trans. Inf. Theory,_ vol.45 (1999) pp. 289-295.
  * [8] Y. Niho, Multivalued cross-correlation functions between two maximal linear recursive sequences. PhD Thesis, University of Southern California (1972).
  * [9] P. Rosendahl, A generalization of Niho’s Theorem,_Des. Codes Cryptogr._ , vol. 38 (2006), pp. 331-336.
  * [10] H.M. Trachtenberg, On the cross-correlation functions of maximal linear sequences, PhD Thesis , University of Southern California (1970).