Maximum order complexity of the sum of digits function in Zeckendorf base and polynomial subsequences (Q2121010)

Having cryptographic applications in mind, the \textit{\(N\)-th maximum order complexity} of a sequence \(s_n\) is the least positive integer \(M\) such that there is a polynomial \(f(x_1,\ldots,x_M)\in\mathbb{F}_2[x_1,\ldots,x_M]\) with \(s_{i+M} = f(s_i,\ldots,s_{i+M-1})\), \(0\le i\le N-M-1\). Recent results show that polynomial subsequences of automatic sequences are better candidates for pseudorandom sequences. Morphic sequences are a natural generalization of such sequences. The sum of digits function in Zeckendorf (or Fibonacci) numeration system, modulo 2, is such an example of a morphic sequence. In this paper, the authors obtain a lower bound of the form \(N/(\varphi+\varphi^3)+1\) for the maximum order complexity of this sequence, \(\varphi\) being the golden mean. They also prove that the polynomial subsequences of this sequence keep large maximum order complexity. Note that the results can be generalized to other Ostrowski numeration systems. In the final part of the paper, they discuss heuristics that supports the real growth of the maximum order complexity. In particular, they conjecture that the lower bound is indeed the actual growth of the maximal order complexity.