12 problems

Omega linear-complexity conjecture.

Let $q$ be the alphabet size, let $n$ be the length, and let $m$ be the number of component sequences. Write $E_n^{(m)}$ for the expected linear complexity of an $m$-multisequence…

Expected exponential linear complexity symmetry gap conjecture. The difference $E_N^{lin-exp}-E_N^{lin-exp-sym}$ is of order of magnitude $2^{N/2}$.

Expected rational complexity symmetry gap conjecture. The difference $E_N^{rat}-E_N^{rat-sym}$ is at least of order of magnitude $2^{N/2}$.

Let $p\equiv \pm1\bmod 8$ be prime, let ${\cal L}_p$ denote the Legendre sequence of modulus $p$, and let $L({\cal L}_p,N)$ be its $N$th linear complexity. Expected-deviation conje…

Let $n\geq 3$, let $c$ be an integer satisfying … and suppose $c\neq 2^{n-1}+n+1$. A span $n$ de Bruijn sequence is a cyclic binary sequence in which every binary word of length…

General asymptotic conjecture. As the size of $\text{\bf A}$ increases, ${\cal L}_n(\text{\bf A})$ approaches ${\cal L}_n(\text{\bf C})$ or ${\cal L}_n(\text{\bf F})$, according as…

Let $\mathbf{s}$ be a modified binary de Bruijn sequence of order $n$, and let $\Delta_{\mathbf{s}}$ denote its linear span. Tan's conjecture. … This conjecture concerns the possib…

Let $p$ be an odd prime, let $m$ be a positive integer, and let $e$ be the relevant order parameter in the generalized cyclotomic construction. Let $\mathbf{s}^{\infty}$ be the gen…

The linear complexity conjecture. If $p$ is a non-Wieferich odd prime and $(s_i)$ is the sequence above, then its linear complexity is given by the formula stated in the source.

Linear-complexity conjecture. If $2^{p-1}\not\equiv 1\pmod {p^2}$, then the linear complexity $L$ of $s^\infty$ is

Let $s$ be a binary sequence with period $2^n$. A standard cube decomposition is a cube decomposition satisfying the conventions of the paper, and a decomposition is said to be wit…