babylonpolice.com

The $2$-adic complexity has been well-analyzed in the periodic case. However,
we are not aware of any theoretical results on the $N$th $2$-adic complexity of
any promising candidate for a pseudorandom sequence of finite length $N$ or
results on a part of the period of length $N$ of a periodic sequence,
respectively. Here we introduce the first method for this aperiodic case. More
precisely, we study the relation between $N$th maximum-order complexity and
$N$th $2$-adic complexity of binary sequences and prove a lower bound on the
$N$th $2$-adic complexity in terms of the $N$th maximum-order complexity. Then
any known lower bound on the $N$th maximum-order complexity implies a lower
bound on the $N$th $2$-adic complexity of the same order of magnitude. In the
periodic case, one can prove a slightly better result. The latter bound is
sharp which is illustrated by the maximum-order complexity of $\ell$-sequences.
The idea of the proof helps us to characterize the maximum-order complexity of
periodic sequences in terms of the unique rational number defined by the
sequence. We also show that a periodic sequence of maximal maximum-order
complexity must be also of maximal $2$-adic complexity.