Probabilistic results on the $2$-adic complexity

Abstract

This work is devoted to solving some closely related open problems on the average and asymptotic behavior of the $2$-adic complexity of binary sequences. First, for fixed $N$, we prove that the expected value $E_N^{2-\mathrm{adic}}$ of the $2$-adic complexity over all binary sequences of length $N$ is close to $\frac{N}{2}$ and the deviation from $\frac{N}{2}$ is at most of order of magnitude $\log (N)$. More precisely, we show that $$\frac{N}{2}-1\le E_N^{2-\mathrm{adic}}=\frac{N}{2}+O(\log (N)).$$ We also prove bounds on the expected value of the $N$th rational complexity. Our second contribution is to prove for a random binary sequence $\mathcal{S}$ that the $N$th $2$-adic complexity satisfies with probability $1$ $$ λ_{\mathcal{S}}(N)=\frac{N}{2}+O(\log(N)) \quad \mbox{for all $N$}. $$