Automatic sequences are not suitable sequences for cryptographic applications since both their subword complexity and their expansion complexity are small, and their correlation measure of order 2 is large. These sequences are highly predictable despite having a large maximum order complexity. However, recent results show that polynomial subsequences of automatic sequences, such as the Thue–Morse sequence, are better candidates for pseudorandom sequences. A natural generalization of automatic sequences are morphic sequences, given by a fixed point of a prolongeable morphism that is not necessarily uniform. In this paper we prove a lower bound for the maximum order complexity of the sum of digits function in Zeckendorf base which is an example of a morphic sequence. We also prove that the polynomial subsequences of this sequence keep large maximum order complexity, such as the Thue–Morse sequence.
Notes
Publisher’s note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
1 Introduction
Feedback shift register (FSR) sequences are used for many cryptographic applications such as pseudorandom number generators for stream cipher cryptosystems, see [10]. A binary n-stage feedback shift register (FSR) is a mapping \(\mathfrak {F}\) from \(\mathbb {F}_{2}^{n}\) to \(\mathbb {F}_{2}^{n}\) of the form
where f is a function from \(\mathbb {F}_{2}^{n}\) to \(\mathbb {F}_{2}\). Consider the binary sequence \(\mathcal {S}=(s_{i})_{i\geq 0}\) whose first n terms are given and the remaining terms are uniquely determined by the recurrence relation
The sequence \(\mathcal {S}\) is called the output sequence of the FSR. An output sequence of a short FSR is considered weak in cryptographic applications. In order to determine this shortness for an infinite sequence \(\mathcal {S}\), Jansen [12, 13] introduced the notion of N th maximum order complexity of\(\mathcal {S}\), denoted as \(M(\mathcal {S},N)\), which is the length of the shortest FSR that generates the first N elements of \(\mathcal {S}\). If the mapping \(\mathfrak {F}\) is a linear transformation, then the FSR is called a linear feedback shift register (LFSR). This leads to the notion of the linear complexity profile of \(\mathcal {S}\) denoted as \(L(\mathcal {S},N)\). We have obviously \(M(\mathcal {S},N)\leq L(\mathcal {S},N)\). The sequence \((M(\mathcal {S},N))_{N}\) is called the maximum order complexity profile of \(\mathcal {S}\) and \(M(\mathcal {S})=\sup _{N\geq 1} M(\mathcal {S},N)\) is called the maximum order complexity of \(\mathcal {S}\).
A sequence \(\mathcal {S}\) is said to have a perfect linear complexity profile if
An explicit construction of sequences with perfect linear complexity profile is given in [1]. These are known under the name of apwenian sequences (see [17]). Diem [7] observed that these sequences and sequences based on function expansion into expansion series can be efficiently computed from relatively short sequences. This leads to the notion of expansion complexity, denoted as \(E(\mathcal {S},N)\), see Definition 2 below for more details. It was proved by Mérai, Niederreiter and Winterhof [16] that the expansion complexity and the linear complexity of an infinite sequence satisfy \(E(\mathcal {S},N)\leq L(\mathcal {S},N)+1\).
A natural question is to ask about the mutual relationship between the maximum order complexity and the expansion complexity. It is known that these two complexities have expected behavior \(\log N\) for the maximum order complexity, see [12, 20], and \(\sqrt {N}\) for the expansion complexity, see [17, Theorem 6.2] and [16]. This suggests that maximum order complexity is smaller than the expansion complexity. However, the Thue–Morse sequence has a large maximum order complexity and a bounded expansion complexity. Thus in order to determine the unpredictability of a sequence, both the expansion complexity and the maximum order complexity are useful and needed.
In recent years, research focused in particular on automatic sequences, i.e. sequences that are generated by a deterministic finite automaton. These sequences are not suitable for cryptographic applications as we will state later. Nevertheless, their pseudorandom behavior changes radically when the sequence is rarefied along special subsequences such as polynomial subsequences. One can extend the definition of automatic to morphic sequences which is an again larger class.
The aim of the present article is to study pseudorandomness of some morphic sequences and its polynomially rarefied subsequences. We first introduce several measures of complexity (Section 1.1) and illustrate their behavior with a simple example. We then introduce automatic and morphic sequences (Section 1.2) and give an overview about the results known for their measures of complexity. We then indicate our main results of this paper (Section 1.3).
Advertisement
1.1 Measures of complexity
Let us first introduce some measures of complexity that we will focus on in the present paper.
Definition 1 (Maximum order complexity)
Let N be a positive integer with N ≥ 2, and \(\mathcal {S}=\left (s_{n} \right )_{n\geq 0}\) be a sequence over {0,1} with (s0,…,sN− 2)≠(a,…,a) for a = 0 or 1. The Nth maximum order complexity \(M(\mathcal {S},N)\) is the smallest 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
If si = a for i = 0,…,N − 2, we define \(M(\mathcal {S},N)=0\) if sN− 1 = a and \(M(\mathcal {S},N)=N-1\) else.
A sequence with small maximum order complexity is not suitable for cryptographic applications. Indeed, such a sequence can be built with relatively short blocks of consecutive terms. However, a sequence with large maximum order complexity can still be predictable, as it is known for the Thue–Morse sequence, see [15, 28]. Note also that the largest possible order of magnitude of \(M(\mathcal {S},N)\) is N and the expected value of \(M(\mathcal {S},N)\) is \(\log N\), see [12, 20].
The maximum order complexity has been studied by several authors, for general results see [11‐13, 20, 31] or [21, 27‐29] for applications to some particular sequences such as the Thue–Morse sequence or the Rudin–Shapiro sequence. From a computational perspective, Jansen [12, Proposition 3.17] showed how Blumer’s DAWG (Direct Acyclic Weighted Graph) algorithm [3] can be used to compute the maximum order complexity in linear time and memory. In the last section of this paper, we use DAWG algorithm to formulate some conjectures (Section 3.2).
Diem [7] introduced the expansion complexity of a sequence as follows.
Definition 2 (Expansion complexity)
Let N be a positive integer, \(\mathcal {S}=\left (s_{n} \right )_{n\geq 0}\) be a sequence over {0,1} and \(G_{\mathcal {S}}(x)\) its generating function defined by
The Nth expansion complexity\(E(\mathcal {S},N)\) is defined as the least total degree of a nonzero polynomial \(h(x,y) \in \mathbb {F}_{2}[x,y]\) with
if s0,…,sN− 1 are not all equal to 0, and \(E(\mathcal {S},N)=0\) otherwise.
A truly random sequence has expected value \(E(\mathcal {S},N)\) of order N1/2, see [17].
Binary, and more generally, p-ary automatic sequences are not good pseudorandom sequences since their expansion complexity satisfies \(E(\mathcal {S},N)<+\infty \) by Christol’s theorem, see [6]. In fact, automatic sequences generated by a finite automaton do not have sufficiently many different factors of a fixed length.
The subword complexity, denoted by \(p_{\mathcal {S}}(k)\), counts how many different subwords of fixed length k the sequence contains. It can again serve as a measure of pseudorandomness. A sequence \(\mathcal {S}\) over {0,1} is normal if for every k ≥ 1 and for any block of length (b0,…,bk− 1) ∈{0,1}k, we have
One can associate to a binary sequence a symbolic dynamical system based on the shift on \(\{0,1\}^{\mathbb {N}}\). The topological entropy of such a dynamical system is \(\lim _{k\rightarrow +\infty } \frac {\log _{2} p_{\mathcal {S}}(k)}{k}\), where \(\log _{2}\) denotes the base 2-logarithm. A sequence with 0 topological entropy is said to be deterministic and it should not provide a pseudo-random sequence since such a sequence has a small subword complexity, see [23].
1.2 Automatic and morphic sequences
Let k ≥ 2 and Σ be a finite alphabet. We denote by Σ∗ the set of all finite or infinite words over Σ. A morphism f is a mapping \(f:{{{\varSigma }}}^{*} \rightarrow {{{\varSigma }}}^{*}\) satisfying f(uv) = f(u)f(v) for all words u and v. A morphism is said to be k-uniform if |f(x)| = k for all x ∈Σ, where |x| is the length of the word x. If there is b ∈Σ such that f(b) starts with b, i.e. f(b) = bu for some u ∈Σ∗, we say that f is b-prolongable. In this case, let us denote fω(b) the fixed point of f given by fω(b) = bf(u)f2(u)…
Definition 3 (Automatic and morphic sequences)
Let \(\mathcal {S}\) be a sequence over an alphabet Σ. \(\mathcal {S}\) is morphic if \(\mathcal {S}=\pi (f^{\omega }(b))\) where \(f:{{{\varSigma }}}^{*} \rightarrow {{{\varSigma }}}^{*}\) is a b-prolongeable morphism and \(\pi :{{{\varSigma }}}\rightarrow {{{\varDelta }}}\) is a morphism, named coding. \(\mathcal {S}\) is said k-automatic if f is k-uniform.
For equivalent definitions of automatic sequences, we refer to [2]. An emblematic example of automatic sequence is the Thue–Morse sequence, or Prouhet–Thue–Morse sequence, independently introduced by Thue [30], Morse [18] and Prouhet sixty years before [22]. This sequence appears in many different fields of mathematics, see [14], and is still an important object of recent work.
Definition 4 (Thue–Morse sequence)
For an integer n ≥ 0, we write \(n={\sum }_{i \geq 0}\varepsilon _{i}2^{i}\) with εi ∈{0,1} for all i and (n)2 = ⋯ε1ε0. The binary sum-of-digits of n equals \(s_{2}(n)={\sum }_{i \geq 0} \varepsilon _{i}\). The Thue–Morse sequence\(\mathcal {T}=(t(n))_{n\geq 0}\) is defined by t(n) = s2(n) mod 2.
The Thue–Morse sequence is 2-automatic and the corresponding morphism is
The Thue–Morse sequence has a large maximum order complexity, see [28], but this sequence is far from being pseudorandom. Indeed, it is well-known that \(E(\mathcal {T},N)\leq 5\) for all N since h(x,y) = (x + 1)3y2 + (x + 1)2y + x satisfies \(h(x,G_{\mathcal {T}}(x))=0\) where \(G_{\mathcal {T}}(x)\) is the generating function of \(\mathcal {T}\), see [2, Example 12.1.12]. Also, its subword complexity is small, \(p_{\mathcal {T}}(k)\ll k\) (see [2, Corollary 10.3.2] for a general result for all automatic sequences).
The behavior of this sequence regarding the defined pseudorandomness measures changes when this sequence is rarefied along specific subsequences. Drmota, Mauduit et Rivat [8] showed that the Thue–Morse sequence along squares is normal and Moshe [19] showed that the polynomial subsequences of degree d ≥ 2 of the Thue–Morse sequence have an exponential subword complexity. Sun and Winterhof [27] and Popoli [21] showed that the maximum order complexity of the Thue–Morse sequence along polynomial subsequences remains comparatively large. A large maximum order complexity is desired, however, it should be noted that it should be not too large since the correlation measure of order 2 gets large in that case (see [12, Proposition 3.1]).
Furthermore, these polynomial subsequences are no longer automatic sequences, see [2, Theorem 6.10.1], and their expansion complexity is no longer bounded by Christol’s theorem. These statements mean that the polynomial subsequences of the Thue–Morse sequence are better candidates for cryptographic applications than the original sequence.
In order to generalize the investigation to other morphic sequences and sum of digits function, let us introduce the Zeckendorf base sum of digits function, which is related to the Fibonacci sequence (see [2, Theorem 3.8.1], [32]).
Definition 5 (Zeckendorf base)
Let \(\mathcal {F}=(F_{n})_{n\geq 0}\) be the Fibonacci sequence with initial values F0 = 0, F1 = 1 and Fn+ 2 = Fn+ 1 + Fn for all n ≥ 0. Let us denote \(\varphi =(1+ \sqrt {5})/2\) the golden ratio. Each integer n can be represented uniquely by
with εi(n) ∈{0,1} and εi(n)εi+ 1(n) = 0 for all i ≥ 0.
Since \(F_{n}=\lfloor \frac {\varphi ^{n}}{\sqrt {5}}+\frac {1}{2} \rfloor \) for n ≥ 0, the index n(a) of the largest Fibonacci number that is not greater than an integer a > 1 is \(\lfloor \frac {\log (a \sqrt {5}+1/2)}{\log (\varphi )} \rfloor \). We call n(a) − 1 the length of a.
Thus we can define the sum of digits function in Zeckendorf base by \(s_{Z}(n)={\sum }_{i \geq 0} \varepsilon _{i}(n)\), see [9, 24, 26] or sequence A007895 in On-Line Encyclopedia of Integer Sequences (OEIS) for discussions on this sequence. We denote by \(\mathcal {S}_{Z}\) the sequence defined by \(\mathcal {S}_{Z}=\left (s_{Z}(n)\mod 2\right )_{n\geq 0}\), an analog of the Thue–Morse sequence. It is known that \(\mathcal {S}_{Z}\) is a morphic sequence, see for example [4, p.14] or [2, Examples 7.8.2, 7.8.4]. An example of the corresponding morphism and coding is
$$f:\left\{ \begin{array}{lll} a \mapsto ab \\ b \mapsto c \\ c \mapsto cd \\ d \mapsto a \end{array} \right. \quad \text{and} \quad g:\left\{ \begin{array}{lll} a \mapsto 0 \\ b \mapsto 1 \\ c \mapsto 1 \\ d \mapsto 0. \end{array} \right. $$
Thus, the sequence modulo 2 is obtained by iterating f on the letter a and recoding with g : \(\mathcal {S}_{Z}=\texttt {0}\texttt {1}\texttt {1}\texttt {1}\texttt {0}\texttt {1}\texttt {0}\texttt {0}\texttt {1}\texttt {0}\texttt {0}\texttt {0}\texttt {1}\texttt {1}\texttt {0}\texttt {0}\texttt {0}\texttt {1}\texttt {0}\texttt {1}\texttt {1}\ldots \) This sequence is not automatic, see [9, Remark 1]. Indeed the authors show that the k-kernel is infinite for every k, see [2] for more details on equivalent definitions of automatic sequences. This implies that the expansion complexity of \(\mathcal {S}_{Z}\) is not bounded, since this sequence is not automatic, and motivates our study of this sequence. In fact, morphic non-automatic sequences are better candidates for cryptographic applications regarding this complexity. However morphic sequences have subword complexity at most bounded by a quadratic function, see [2, Corollary 10.4.9], and their associated dynamical system has 0 topological entropy, see [23, Corollary V.20] for an alternative proof.
Example 1.1 (Carry propagations in Zeckendorf base)
In Zeckendorf base, the carry propagations work in a different way than in the usual q-base with \(q\in \mathbb {N}\) and q ≥ 2. Indeed, since we cannot have two consecutive 1-bits, the carry is “transversal” by the Fibonacci recurrence relation and if we have two 1-bits on the same column we use the formulas 2Fj = Fj+ 1 + Fj− 2 for all j ≥ 2 in order to get an admissible expansion. For example, 5 = F5, 6 = F5 + F2 and 5 + 6 = 11 = F6 + F4 as shown by the following calculation:
In this kind of calculation, we first do not take into consideration the restriction of non-adjacent terms then we normalize to obtain the Zeckendorf representation with non-adjacent terms. This simple example shows that the carry propagation is on both sides of the expansion since 2Fj = Fj+ 1 + Fj− 2 for all j ≥ 2. We will see later that this specific carry propagation, compared to the usual q-base carry propagation, will play an important role in our investigation.
As the sum of digits function for the usual q-base, sZ is a subadditive function, i.e. for any integers n1,n2 ≥ 0 we have sZ(n1 + n2) ≤ sZ(n1) + sZ(n2), see [26, Proposition 1]. Consider the Zeckendorf expansion of n1 and n2,
with \(\varepsilon _{k_{i}}^{(i)}=\varepsilon _{K_{i}}^{(i)}=1\). Without loss of generality suppose that k1 ≤ k2. We say that n1 and n2 are non-interfering if k2 − K1 ≥ 2. This means that non-interfering integers have digital blocks that do not overlap and no normalization after the addition has to be executed. We therefore have
where sq denotes the sum of digits function in q-base. For Zeckendorf base there are two major differences with respect to the usual q-base. First, we have a transversal carry propagation and this translates into the condition k2 − K1 ≥ 2 instead of k2 − K1 ≥ 1 that we would have for the usual q-base. Secondly, the identity (2) is not true in general when we replace qℓ by Fℓ and sq by sZ. We will use Lucas numbers to replace the usual shift qℓ.
1.3 Main results
In the following we will determine a lower bound for the maximum order complexity of \(\mathcal {S}_{Z}=(s_{Z}(n) \mod 2)_{n}\) and for \(\mathcal {S}_{Z,P}=(s_{Z}(P(n)) \mod 2)_{n}\) with \(P \in \mathbb {Z}[X]\) a monic polynomial such that \(P(\mathbb {N}_{0}) \subset \mathbb {N}_{0}\). In what follows, we use Vinogradov’s notation f ≪ g is defined as |f|≤ c|g| for some c > 0.
Theorem 1.1
There exists N0 > 0 such that for all N > N0 we have
Since the correlation measure is bounded below by the maximum order complexity (see [17]), Theorem 1.1 shows that \(\mathcal {S}_{Z}\) is non-random in this specific respect. We mention also the recent result of Shutov [25] that shows that the autocorrelation of order 2 with lag equal to 1 of \((-1)^{s_{Z}(n)}\) is large. This serves as motivation to look at subsequences, that we address in following result.
Theorem 1.2
Let \(P(X) \in \mathbb {Z}[X]\) be a monic polynomial of degree d ≥ 2 with \(P(\mathbb {N}_{0}) \subset \mathbb {N}_{0}\). Then \(\mathcal {S}_{Z,P}\) satisfies
$$ M(\mathcal{S}_{Z,P},N)\gg N^{1/(2d)}, \qquad N \to \infty, $$
where the implied constant only depends on P.
We will discuss the heuristics that supports the real growth of the maximum order complexity in the final part of the paper (Section 3.2). In particular, we conjecture that the lower bound is indeed the actual growth of the maximal order complexity.
The rest of the paper is structured as follows. In Section 2, we prove Theorems 1.1 and 1.2 where we first prove the linear case and the particular case P(X) = Xd for d ≥ 2 before tackling the general case. We conclude the paper with some final remarks (Section 3) about possible generalizations of this result to other numerations systems and some heuristically supported conjectures.
2 Sum of digits function in Zeckendorf base
In order to prove a lower bound for the Nth maximum order complexity of a sequence, we use a tool from [12, Proposition 3.1].
Let \(\mathcal {S}\) be a sequence over \(\mathbb {F}_{2}\) of length n. Let k be the length of the longest subsequence of \(\mathcal {S}\) that occurs at least twice with different successors. Then \(\mathcal {S}\) has maximum order complexity k + 1.
The proofs of Theorem 1.1 and Theorem 1.2 are split into two parts. Let N be a sufficiently large integer. First we built two subsequences of the sequence \(\mathcal {S}\) of same length L(N), depending on N, which coincide by using non-interfering terms. Then, for these subsequences, we look for different successors, by studying precisely the involved carry propagations. Thus, by Lemma 1, we then will have \(M(\mathcal {S},N)\geq L(N)+1\).
2.1 Linear case
We first study the maximum order complexity of \(\mathcal {S}_{Z}\).
If n < Fℓ, the terms n and Fℓ+ 1, respectively, n and Fℓ+ 2 are non-interfering, see (1). The second line follows from sZ(Fℓ + Fℓ+ 1) = 1 and sZ(Fℓ + Fℓ+ 2) = 2. □
We are now able to prove Theorem 1.1.
Proof of Theorem 1.1
We choose ℓ ≥ 2 such as Fℓ + Fℓ+ 2 ≤ N < Fℓ+ 1 + Fℓ+ 3. This implies N ≥ F2 + F4 = 4. Then by Lemma 2, \((s_{Z}(n+F_{\ell +1}))_{0\leq n <F_{\ell }}\) and \((s_{Z}(n+F_{\ell +2}))_{0\leq n <F_{\ell }}\) are two subsequences of same length with different successors. Thus by Lemma 1, we have \(M(\mathcal {S}_{Z},N)\geq F_{\ell }+1\). Furthermore, since \(\lim _{n\to \infty } \frac {F_{n+k}}{F_{n}}= \varphi ^{k}\), for k ≥ 1, we have N < (φ + φ3)Fℓ for ℓ large enough. Thus, the theorem is proved. □
2.2 Monomial subsequences
We now study the sequence \(\mathcal {S}_{Z}\) along polynomial values. In a classical q-base, xqj is a shift of length j for the expansion of x. In Zeckendorf base, the Fibonacci numbers do not have this property since a power of a Fibonacci number is in general not a Fibonacci number (note that the only exceptions of pure powers that are Fibonacci numbers are 1,8 and 144, see [5]). The Lucas numbers are an interesting analogue of powers of q in q-base.
Definition 6 (Lucas numbers)
Let \({\mathscr{L}}=(L_{n})_{n}\) be the sequence defined by L0 = 2, L1 = 1 and Lj+ 2 = Lj+ 1 + Lj for all j ≥ 0.
We have for all j ≥ 1, the basic relation Lj = Fj+ 1 + Fj− 1, which means that the expansion of Lucas numbers in Zeckendorf base is simple. Moreover we have the following formulas.
Furthermore, let m > 0, there are non-adjacent terms ε−(2u+ 1)(m),…, ε2u+v(m) ∈{0,1}, ε− 2u− 1(m) = ε2u+v(m) = 1 for some u,v integers depending only on m such that for all k ≥ 2u + 3,
and \([-(2u+1),2u+v] \subseteq \left [k-\ell -1,k+\ell +1\right ]\) where ℓ is such that Fℓ ≤ m < Fℓ+ 1.
The last statement of Lemma 3 has an important role for the construction of sums with non-interfering terms. Indeed, for an integer m and k large enough (of order of length of m), the expansion of mLk is the expansion of m centered around Fk. Notice that this result is different from the q-base since the digits here appear on both sides of the expansion of m. We will see the impact in our main result Theorem 1.2 with the occurence of N1/(2d) in the place of N1/d that we got in the case of q-base expansion, see [21].
Let us start with the case P(X) = Xd for d ≥ 2. In the following we write \(\overline {\lambda }=\lambda \mod 2\) with \(\overline {\lambda }\in \{0,1\}\). This case is the building brick for the general case of \(P(X) \in \mathbb {Z}[X]\) with \(P(\mathbb {N}_{0}) \subset \mathbb {N}_{0}\).
To begin with, we study the expression of (n + Lℓ)d in terms of a sum of distinct Lucas numbers.
Lemma 4
Let n ≥ 0 be an integer and ℓ ≥ 0 be an even integer. We have
Then we have c3d > 0, c3d− 1 < 0 and ci > 0 for i = 0,1,…,3ℓ − 2.
This lemma will be useful to construct two elements with different sums of digits in Zeckendorf base when we take their d th powers. Indeed, only the subdominant coefficient is negative so we are able to create a block of digits 1010⋯10 of length k for any k large enough. Indeed, as we will state later, the transition from k to k + 1 adds exactly one block of 10. We have already used a similar method in the usual 2-base, see [21, proof of Lemma 6].
In the following, let α ≥ 1 be an integer such that
Under these conditions, Td(k) and Td(k + 1) have all positive integral coefficients with the only exception of the coefficient of L2k(3d− 1) and L2(k+ 1)(3d− 1) respectively, see [26]. Notice that these coefficients are the same for these two polynomials for k large enough.
Lemma 7
Let d ≥ 3 be odd and k ≥ 0 be a sufficiently large integer. Let n be an integer such that n ≥ d and
Condition (4) and Lemma 5 imply that all coefficients in front of each Lλℓ, for 1 ≤ λ ≤ d, are < F3k. Since the aim is to build a sum with non-interfering terms, we study for the range of digits of each term in the sum with the help of Lemma 3. Hence for sufficiently large ℓ, the range of digits of
is included in the interval \(\left [\lambda \ell - 3k,\lambda \ell + 3k\right ]\) for λ > 0 and \(\left [0,3k-1\right ]\) for λ = 0. If we suppose that these intervals are disjoints plus one small gap, see Remark 1.1, we have a non-interfering sum, i.e when we suppose
For this to happen, it is sufficient to suppose ℓ > 6k and we have imposed ℓ even. So we can choose ℓ = 6k + 2 in order to have a non-interfering sum. An identical proof works for ℓ = 6k + 4 and (5) is proved.
The second part follows directly from [26, Lemma 3]. For m1,m2 ≥ 1 and k1 > k2 large enough, we have
Thus condition (4) gives nd ≪ F3k and \(n \ll F_{k}^{3/d}\). As we have already stated in Lemma 1, we have
$$ M(\mathcal{S}_{Z,P},N) \gg F_{k}^{3/d} $$
since we have two blocks of length \(\ll F_{k}^{3/d}\) with two different successors. It remains to ensure that
$$ t(k) \gg F_{k}^{3/d}+L_{6k+2}, $$
(8)
since we need t(k)d a successor of the non-interfering block. We have \(t(k)\sim m_{3}L_{6k}\sim m_{3}\varphi ^{6k}\) and \(F_{k}^{3/d}+L_{6k+2}\sim L_{6k+2} \sim \varphi ^{6k+2}\) as \(k\to +\infty \). Since by (3), m3 ≥ d3(32φ)d, we have t(k) ≫ 32dd3φ6k+d for \(k\to +\infty \). Therefore for sufficiently large k, (8) is satisfied. For the same reasons, we need
$$ t(k+1) \gg F_{k}^{3/d}+L_{6k+4}. $$
(9)
A very similar proof of (8) gives (9) for k sufficiently large. Furthermore, (7) gives
For d even, we prove a similar result as Lemma 7 and a similar proof works for the same reasons (we omit the details). Thus Theorem 1.2 is proved in the case P(X) = Xd. □
2.3 Polynomial subsequences
We consider now the general case with P(X) = αdXd + ⋯ + α0 a polynomial such that \(P(\mathbb {N}_{0}) \subset \mathbb {N}_{0}\) and αd = 1. Such as before, we shall determine exactly P(n + Lk) for the integers n ≥ 0 et k ≥ 0.
We introduce μ since it is sufficient to adjust the non-interfering block to have the same result. Later, we shall take μ depending only on d.
To prove a lower bound on the Nth maximum order complexity of \(\mathcal {S}_{Z,P}\), we look for an analogue of Lemma 7. The analogue of the first part of this lemma is described as follows.
Lemma 10
Let k ≥ 0 be a sufficiently large integer and r > 1. For any integer Cd < n < Fμk we have
For n < Fμk we have β0(n) ≪ Ldμk. Then the terms in (10) are non-interfering for k large enough such as in the proof of Lemma 7 where Lemma 5 is replaced by Lemma 9. Thus we have
According to Lemma 10, we need λ ≥ μk. Note that we want to prove that \(M(\mathcal {S}_{Z,P},N)\gg N^{1/(2d)}\) in order to have the same bound as the one for the monomial case. The following result gives sufficient conditions for the size of λ and r for this bound.
Lemma 11
If λ ≤ 2dμk and r is constant, then we have \(M(\mathcal {S}_{Z,P},N)\gg N^{1/(2d)}\).
Proof
If we have λ such that (12) is verified, we show in the same way as before that
If λ ≤ 2dμk and r is constant, we have \(N\ll F_{\mu k}^{2d}\) and \(M(\mathcal {S}_{Z,P},N)\gg N^{1/(2d)}\). Notice that μ independent from k is also required to have this result. □
We are now looking for (λ,r) such that μk ≤ λ ≤ 2dμk, r constant and (12) is verified.
As we will state later, only two Lucas numbers will interfere. The following lemma describes all the possibilities for this interference.
Lemma 12
Let k,ℓ be two integers such that k ≥ ℓ ≥ 5. We have
We have Lk = Fk+ 1 + Fk− 1 and Lℓ = Fℓ+ 1 + Fℓ− 1. So we shift two blocks of 101 one against the other and look for transversals in the carry propagations. Note that if k ≥ ℓ + 4, there is no carry propagation at all and sZ(Lk + Lℓ) = 4 ≡ 0 (mod 2). By symmetry, there remain only four cases to consider. We suppose ℓ ≥ 5:
Case k = ℓ:
Then we have sZ(Lk + Lℓ) ≡ 0 (mod 2).
Case k = ℓ + 1:
Then we have sZ(Lk + Lℓ) ≡ 0 (mod 2).
Case k = ℓ + 2:
Then we have sZ(Lk + Lℓ) ≡ 1 (mod 2).
Case k = ℓ + 3:
Then we have sZ(Lk + Lℓ) ≡ 0 (mod 2).
Thus the lemma is proved. □
Proof
(Proof of Theorem 1.2) We now investigate the interferences in
We will now choose λ even. Thus we have for the first interference Lλd + L2dμk−(d− 1)λ+ 2. By Lemma 12 we have for sufficiently large k
$$ \begin{array}{@{}rcl@{}} s_{Z}(L_{\lambda d}+L_{2d\mu k -(d-1)\lambda+2})&=&1 \Leftrightarrow 2d\mu k-(d-1)\lambda+2=\lambda d +2 \\\Leftrightarrow \lambda&=&\frac{2d\mu k}{2d-1}. \end{array} $$
(13)
Hence it is sufficient to take μ = 2d − 1 and λ = 2dk. Furthermore, all other possible interferences are non-existing by this choice of λ and μ. We finally need to check if λ satisfies all the conditions: λ is even and (2d − 1)k ≤ λ ≤ 2d(2d − 1)k. Furthermore we can take r = 2 for example and all the appearing blocks do not interfere. Summing up, we have proved that \(s_{Z}\left (P\left (L_{\lambda }+L_{2d(2d-1) k +2}\right )\right )\neq s_{Z}\left (P\left (L_{\lambda }+L_{2d(2d-1) k +4}\right )\right )\). Thus, we have proved the general case of Theorem 1.2. □
Remark 2.3
The choice of L2dμk+ 2 in the proof is motivated to have an integer solution for λ in (13). Indeed, if we had chosen L2dμk instead, (13) would not have provided an integer for all k.
3 Final remarks
3.1 Generalizations
Our result can be generalized to other numeration systems without new methods. Let us first comment on Ostrowski’s α-numeration system, see [2, Theorem 3.9.1], related to the continued fraction of an irrational number.
Definition 7 (Continued fraction)
Let α be a real number, we define the sequence (ai)i such that
and we define p− 2 = 0, p− 1 = 1, q− 2 = 1, q− 1 = 0, and pn = anpn− 1 + pn− 2, qn = anqn− 1 + qn− 2. Then we have \(\frac {p_{n}}{q_{n}}=\left [a_{0},a_{1},\ldots ,a_{n}\right ]\). The sequence (qn)n is called denominators of the convergents of the continued fraction of α.
Definition 8 (Ostrowski’s α-numeration system)
Let α be a non rational real number, and let (qn) be the sequence of the denominators of the convergents of the continued fraction of α. Then every non-negative integer n can be represented uniquely in the form
$$ \begin{array}{@{}rcl@{}} n=\underset{0\leq i \leq j}{\sum}\varepsilon_{i} q_{i} \end{array} $$
where the εi are integers satisfying the following conditions:
1.
0 ≤ b0 < a1
2.
0 ≤ bi ≤ ai+ 1, for i ≥ 1.
3.
For i ≥ 1, if bi = ai+ 1 then bi− 1 = 0.
For the specific case α = φ, we have the Zeckendorf expansion since φ = [1,1,1,…].
Our result might be generalized to a quadratic irrational α such that the continued fraction of α is of the form α = [1,a,a,…]. In this particular case, we have \(q_{n+2}=\frac {1}{a}q_{n+1}+q_{n}\). We denote by γ the zero of the polynomial \(x^{2}-\frac {1}{a}x-1\) such that its Galois conjugate \(\overline {\gamma }\) verifies \(|\overline {\gamma }|<|\gamma |\). Thus we have \(q_{n}=\frac {1}{\sqrt {a^{-2}+4}}(\gamma ^{n}-\overline {\gamma }^{n})\), an analogous formula that for Fibonacci numbers. We define an analogue of Lucas numbers by \(L^{\prime }_{n}=\gamma ^{n}+\overline {\gamma }^{n}\) for all n ≥ 0. Then, in this particular case, our new notion of “Lucas numbers” verifies \(L^{\prime }_{n}=q_{n+1}+q_{n-1}\) and an analogous formula of Lemma 3 holds true. So it might be possible to generalize our result in this case since no more input in the proof is needed.
3.2 Conjectures
We can compute the maximum order complexity thanks to Blumer’s DAWG (Direct Acyclic Weighted Graph) algorithm (see [3] and [12]). The C++ program that computes the maximum order complexity of a sequence is available on the web page of the second author.1 By using this program, we are able to formulate some heuristically supported conjectures.
Conjecture 3.1
We conjecture that \(M(\mathcal {S}_{Z},N) \sim \frac {1}{1+\varphi ^{2}}N\). Figure 1 indicates that the maximum order complexity for \(\mathcal {S}_{Z}\) is linear with coefficient \(\frac {1}{1+\varphi ^{2}}=0.27639\ldots \)
Fig. 1
Maximum order complexity for the sum of digits function in Zeckendorf base
×
Let us compare the maximum order complexity along polynomial subsequences of the Thue–Morse sequence to the Zeckendorf expansion sequence.
The plots for squares and cubes (and the large values of R2), see Figs. 2 and 3, indicate that the growth is close to x1/2 and x1/3, respectively. We therefore formulate the following conjecture :
Fig. 2
Maximum order complexity for the Thue–Morse sequence along squares
Fig. 3
Maximum order complexity for the Thue–Morse sequence along cubes
×
×
Conjecture 3.2
The Thue–Morse sequence along polynomial subsequences, denoted by \(\mathcal {T}_{P}\) for a polynomial P of degree d, verifies \(M(\mathcal {T}_{P},N)\asymp N^{1/d}\), i.e. there are c,C > 0 such as for all N large enough we have
A proof of this conjecture would imply that the lower bound proved by Popoli [21] is optimal.
The maximum order complexity of \(\mathcal {S}_{\varphi }\) is algorithmically more difficult to handle. Motivated by the results on Thue–Morse we conjecture the following:
Conjecture 3.3
The sequence \(\mathcal {S}_{Z}\) along polynomial subsequences, denoted by \(\mathcal {S}_{Z,P}\) for a polynomial P of degree d ≥ 2, verifies \(M(\mathcal {S}_{Z,P},N)\asymp N^{1/(2d)}\), i.e. there are c,C > 0 such as for all N large enough we have
This is, to some extent, supported by the plot for squares, see Fig. 4. Again, a proof of this conjecture would imply that the lower bound in Theorem 1.2 is sharp. Notice that there is a larger gap for the maximum order complexity between the linear case and the quadratic case for \(\mathcal {S}_{Z}\) compared to the classical Thue–Morse sequence.
Fig. 4
Maximum order complexity of \(\mathcal {S}_{Z}\) along squares
×
We conclude the discussion by a surprising phenomenon on steps. Since the maximum order complexity is integer-valued and an increasing function, it is a step function. Each time \(M(\mathcal {S},N)\) has a different value from \(M(\mathcal {S},N-1)\), we say that N is a step. The ratio of successive steps is the ratio N1/N2 for two steps N1,N2 such that there is no N ≥ 1 with \(M(\mathcal {S},N_{1})<M(\mathcal {S},N)<M(\mathcal {S},N_{2})\).
We observed that the ratio of successive steps seems to converge.
Conjecture 3.4
The ratio of successive steps for the maximum order complexity of a sequence related to the Thue–Morse sequence, respectively, the sequence related to the Zeckendorf sum of digits, tends to 2, respectively, the golden ration φ.
This phenomenon seems to be related to numeration systems, and not directly to the fact that a sequence is automatic or morphic.
The plot for cubes, see Fig. 5, does not enlighten Conjecture 3.3 and Conjecture 3.4. With our program and our machine, it is not possible to compute the maximum order complexity of a sequence any further than 109 terms. Nevertheless, we believe that if it were possible to compute for a few more terms, both of theses conjectures should appear more clearly.
Fig. 5
Maximum order complexity of \(\mathcal {S}_{Z}\) along cubes
We would like to thank Arne Winterhof for very helpful discussions and comments on a preliminary version of the paper, and for sending us the bachelor thesis of his student Jan-Michael Holzinger. This work was supported partly by the French PIA project “Lorraine Université d’Excellence”, reference ANR-15-IDEX-04-LUE, and by the projects ANR-18-CE40-0018 (EST) and ANR-20-CE91-0006 (ArithRand).
Declarations
Conflict of Interests
The authors declare that they have no conflict of interest.
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher’s note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Then we have sZ(Lk + Lℓ) ≡ 0 (mod 2).
Then we have sZ(Lk + Lℓ) ≡ 0 (mod 2).
Then we have sZ(Lk + Lℓ) ≡ 1 (mod 2).
Then we have sZ(Lk + Lℓ) ≡ 0 (mod 2).