Symmetric measures of pseudorandomness for binary sequences
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911541641609216 |
|---|---|
| author | Ren, Yixin Winterhof, Arne |
| author_facet | Ren, Yixin Winterhof, Arne |
| contents | We compare ordinary and symmetric variants of two classical measures of pseudorandomness for binary sequences, the $2$-adic complexity and the linear complexity.
In the periodic setting, we show that for binary periodic sequences constructed from the binary expansions of non-palindromic primes, the symmetric $2$-adic complexity can be strictly smaller than the ordinary $2$-adic complexity. We also give a direct proof (of the known result) that the linear complexity of a periodic binary sequence is invariant under reversal, and hence coincides with its symmetric version.
In the aperiodic setting, we provide explicit families of finite binary sequences for which both the $N$th symmetric 2-adic complexity and the $N$th symmetric linear complexity are substantially smaller than their ordinary counterparts. Furthermore, we show that the expected values of the $N$th rational complexity and of the $N$th exponential linear complexity exceed those of their symmetric analogues by at least a term of order of magnitude $N$. Thus, the effect of symmetrization is clearly visible on an exponential scale.
We also establish lower bounds for the expected values of the symmetric rational complexity, symmetric $2$-adic complexity, symmetric linear complexity, and symmetric exponential linear complexity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_23166 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Symmetric measures of pseudorandomness for binary sequences Ren, Yixin Winterhof, Arne Number Theory Combinatorics We compare ordinary and symmetric variants of two classical measures of pseudorandomness for binary sequences, the $2$-adic complexity and the linear complexity. In the periodic setting, we show that for binary periodic sequences constructed from the binary expansions of non-palindromic primes, the symmetric $2$-adic complexity can be strictly smaller than the ordinary $2$-adic complexity. We also give a direct proof (of the known result) that the linear complexity of a periodic binary sequence is invariant under reversal, and hence coincides with its symmetric version. In the aperiodic setting, we provide explicit families of finite binary sequences for which both the $N$th symmetric 2-adic complexity and the $N$th symmetric linear complexity are substantially smaller than their ordinary counterparts. Furthermore, we show that the expected values of the $N$th rational complexity and of the $N$th exponential linear complexity exceed those of their symmetric analogues by at least a term of order of magnitude $N$. Thus, the effect of symmetrization is clearly visible on an exponential scale. We also establish lower bounds for the expected values of the symmetric rational complexity, symmetric $2$-adic complexity, symmetric linear complexity, and symmetric exponential linear complexity. |
| title | Symmetric measures of pseudorandomness for binary sequences |
| topic | Number Theory Combinatorics |
| url | https://arxiv.org/abs/2603.23166 |