31 problems

Let $E_k$ denote the limit of the expected width of the largest block-palindrome factorization of a length-$n$ word over an alphabet of size $k$, whose existence is established for…

Let ${\bf x}=(a_i)_{i\geq 0}$ be an infinite word over a finite alphabet $\Sigma$. Write $\rho_{\bf x}(n)$ for the number of distinct length-$n$ factors of ${\bf x}$, and let…

Let $L$) be a language on $k$ letters satisfying a symmetric order condition and having no connection. Its palindromic complexity is the number of palindromic factors of each lengt…

Fix a base $b\geq 2$ and let $\overleftarrow{n}$ denote the integer obtained by reversing the base-$b$ digits of $n$. A square-free palindrome is a positive integer that is square-…

Characterization conjecture. A word $w\in P_1\cap P_2$ if and only if $\operatorname{Pal}(u)=w$ for some $u\in\{a,c\}^*\cdot b^*$. The preceding proposition establishes this charac…

Let ${\mathcal B}_n$ be the set of binary integers with $n$ binary digits, let $\overleftarrow{a}$ denote the integer obtained by reversing the binary digits of $a$, and let…

Let $b\geq 2$ be an integer. A positive integer is $b$-palindromic if its sequence of base-$b$ digits is a palindrome, and let $\mathscr{P}_b(x)$ denote the set of positive $b$-pal…

Arbitrarily long gaps conjecture. Consecutive positive integers each not a $v$-palindrome in base $b$ can be arbitrarily long.

Squarefree v-palindromes conjecture. There are infinitely many $v$-palindromes $n$ in base $b$ such that both $n$ and $r_b(n)$ are squarefree.

Let $\operatorname{A}$ be a finite alphabet. For a finite nonempty rich word $w$ over $\operatorname{A}$, write its UPS-factorization as $w=w_pw_{p-1}\cdots w_1$, where the factors…

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…

Let $w$ be an infinite word. A prefix of arbitrarily high palindromic length means that for every integer $M$ there is a prefix $u$ of $w$ with $\operatorname{PL}(u)\geq M$. Frid–P…

Type-independence conjecture. The type of $m$ with respect to $n_1$ is the same as the type of $m$ with respect to $n_2$.

Fundamental-period conjecture. Either

Let $\mathcal{S}_k$ denote the set of Hertzsprung patterns of length $k$, and let $\Omega(\sigma,\sigma)$ be the autocorrelation polynomial of $\sigma\in\mathcal{S}_k$. For a palin…

Frid's conjecture. The palindromic length sequence of an infinite word is bounded if and only if the infinite word is ultimately periodic.

Let $u=u[1]u[2]\cdots$ be an infinite word. For $n\in\mathbb N$, let $PPL_u(n)$ denote the minimum number of concatenated palindromes needed to express the prefix of $u$ of length…

Three-quarter palindrome conjecture. The word $w$ has a palindromic subsequence of length at least

Orthogonal-cut conjecture. For every such $w$ and every such linear representation, the maximum of the lengths of $p_1p'_1$ and $p_2p'_2$ is at least

Strong circular-palindrome conjecture. There is such a partition with subsequences $s_1,s_2$ satisfying

Weak circular-palindrome conjecture. Every binary circular word of length $n$ has a palindromic subsequence of length at least

Brevier–Preissmann–Sebő's conjecture. The word $w$ can be partitioned into two linear words $w_1,w_2$ of equal length, $w=w_1w_2$, having subsequences $s_1,s_2$ such that $s_1s_2$…

Lyngsø and Pedersen's conjecture. Every binary circular word of length $n$ divisible by $6$ with equal numbers of zeros and ones has an antipalindromic subsequence of length at lea…

For an infinite word $\mathbf{w}$, let the palindromic length $|u|_{\rm pal}$ of a finite factor or prefix $u$ be the least number $Q$ of palindromes whose concatenation is $u$. Un…

Let $\boldsymbol{f}$ be the Fibonacci word, namely the fixed point of the morphism $0\mapsto 01$, $1\mapsto 0$. Let $\tau$ denote the golden ratio. Frid's Fibonacci-word lower-boun…