2021/06/18 by Damien Jamet, Jamet, Damien, Pierre Popoli +3
Computer Science · Engineering · #11A63 #11B50 #11B85 #11K45 #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #Number Theory (math.NT) #graph theory and CDMA systems #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2106.09959
openalex publication_date 2021/06/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Automatic sequences are not suitable sequences for cryptographic applications\nsince both their subword complexity and their expansion complexity are small,\nand their correlation measure of order 2 is large. These sequences are highly\npredictable despite having a large maximum order complexity. However, recent\nresults show that polynomial subsequences of automatic sequences, such as the\nThue--Morse sequence, are better candidates for pseudorandom sequences. A\nnatural generalization of automatic sequences are morphic sequences, given by a\nfixed point of a prolongeable morphism that is not necessarily uniform. In this\npaper we prove a lower bound for the maximum order complexity of the sum of\ndigits function in Zeckendorf base which is an example of a morphic sequence.\nWe also prove that the polynomial subsequences of this sequence keep large\nmaximum order complexity, such as the Thue--Morse sequence.\n