Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2501.16785 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929689562447872 |
|---|---|
| author | Chen, Z. Winterhof, A. |
| author_facet | Chen, Z. Winterhof, A. |
| contents | 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^{\mathrm{2-adic}}_N$ 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^{\mathrm{2-adic}}_N= \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$}. $$ |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_16785 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Probabilistic results on the $2$-adic complexity Chen, Z. Winterhof, A. Combinatorics Number Theory 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^{\mathrm{2-adic}}_N$ 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^{\mathrm{2-adic}}_N= \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$}. $$ |
| title | Probabilistic results on the $2$-adic complexity |
| topic | Combinatorics Number Theory |
| url | https://arxiv.org/abs/2501.16785 |