On the maximum order complexity of subsequences of the Thue–Morse and Rudin–Shapiro sequence along squares

ABSTRACT

Automatic sequences such as the Thue–Morse sequence and the Rudin–Shapiro sequence are highly predictable and thus not suitable in cryptography. In particular, they have small expansion complexity. However, they still have a large maximum order complexity. Certain subsequences of automatic sequences are not automatic anymore and may be attractive candidates for applications in cryptography. In this paper we show that subsequences along the squares of certain pattern sequences including the Thue–Morse sequence and the Rudin–Shapiro sequence have also large maximum order complexity but do not suffer a small expansion complexity anymore.

KEYWORDS:

• Thue–Morse sequence
• Rudin–Shapiro sequence
• automatic sequence
• maximum order complexity
• measures of pseudorandomness

MSC 2010:

• 11B85
• 11K45

Acknowledgements

We thank the referees for their careful reading and their valuable remarks.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

The first author is supported by China Scholarship Council and the National Natural Science Foundation of China [grant number 61472120]. The second author is supported by the Austrian Science Fund FWF Project P 30405-N32.