372 problems

Collatz conjecture. For every $x \in \mathbb{N}$ there exists $N \ge 0$ such that $\phi^{N}(x) = 1$. This is the classical Collatz problem, asserting that every positive integer ev…

Dejean's conjecture.

Let a square in a word be a subword of the form $v\doubleplus v$ for some word $v$, where $\doubleplus$ denotes concatenation. For a word of length $n$, Fraenkel and Simpson showed…

Frid–Puzynina–Zamboni conjecture. If $k$ is an integer such that

Hof–Knill–Simon conjecture. The language of $\mathbf{u}$ contains infinitely many palindromes if and only if $\mathcal{L}(\mathbf{u})$ coincides with the language of a fixed point…

Sharp upper-bound conjecture. For all $d \geq 2^{2|v|+1}$,

Brlek–Reutenauer conjecture. If $\mathbf u$ is closed under reversal, then

Let an infinite word be aperiodic if it is not ultimately periodic, and let the palindromic length of a factor be the minimum number of palindromes whose product is that factor. Un…

Baranwal–Shallit's conjecture. No other binary rich sequence has a smaller critical exponent than $2+\frac{\sqrt{2}}{2}$. This conjecture concerns the minimum possible critical exp…

Samsonov–Shur's conjecture. The exact values are

Let $w$ be an infinite word, and let $\operatorname{PPL}_w(n)$ denote the palindromic length of the prefix of $w$ of length $n$. Frid's conjecture. If $w$ is $k$-power-free for som…

Erdős's conjecture. The number $\pi(K)$ is finite for every lacunary set $K$.

Fici–Saarela conjecture. Any binary word of length $n$ contains at least

Let $\kappa_{2,1}$ denote the Oldenburger–Kolakoski word over $\{1,2\}$, and interpret the frequency of a letter as its limiting proportion among prefixes, when that limit exists.…

Thue list-number conjecture. The Thue list number of the infinite path is $3$.

Let $\mathbf B=a_0a_1a_2\cdots$ be the infinite binary word obtained from the inflation sequence, and let $I_1(n)$ be the index, using Kimberling's indexing starting at $1$, of the…

Let $w$ be a string of length $n$, and let $w'$ be obtained from $w$ by an edit operation. Write $\chi(w)$ for the size of a smallest suffixient set of $w$. The additive sensitivit…

For each integer $k\geq 1$, let ${\bf x}_k$ be the infinite word defined as the limit of the locally catenative sequence described above, and let $\rho_{{\bf x}_k}(n)$ denote its s…

Let $cmathcal{L}$ be a language over an alphabet $cmathcal{A}$, and let … be the set of words infinitely extendable in both directions. A language has the Restivo--Salemi property…

Let $x_{3/2}$ be the binary Thue–Morse sequence in base $3/2$, and let $\mu[w]$ denote the frequency of a finite word $w$ occurring in it, when that frequency exists. Word-frequenc…

Grytczuk–Kordulewski–Niewiadomski conjecture. There are no extremal words over an alphabet of size $4$.

Mäkelä's conjecture. There exists an infinite ternary word whose only abelian square factors are $00$, $11$, and $22$.

Rampersad–Shallit–Vandomme conjecture. For every alphabet size $d\geq 5$, the minimal critical exponent among balanced sequences over a $d$-letter alphabet equals

A coloring of a graph is nonrepetitive if no path has a color sequence of the form $uu$ for a nonempty finite sequence $u$. The nonrepetitive list chromatic number of a graph is th…

Generalized nonchalant-word infinitude conjecture. If $\ae(N_1)>2$ for the starting word $N_1$ of the nonchalant algorithm, then the respective sequence of nonchalant words is infi…