{"id":"arxiv/2606.08127","url":"https://arxiv.org/abs/2606.08127","tags":["math.CO","cs.DM","cs.FL"],"score":0,"title":"Palindrome complexity versus factor complexity","domain":"math.CO","source":"arxiv","authors":["Jeffrey Shallit"],"reviews":0,"subject":"math.CO","summary":"Let ${\\bf x} = (a_i)_{i \\geq 0}$ be an infinite word over a finite alphabet $Σ$. Let $ρ(n)$ be the factor complexity function for $\\bf x$ and ${\\rm Pal}(n)$ be the palindrome complexity function for $\\bf x$. We give a new relationship between these two quantities; namely, if $\\bf x$ is not ultimately periodic, then $$ \\lim_{n \\rightarrow \\infty} {{ {\\rm Pal} (n) \\log ({\\rm Pal} (n) + 1)} \\over {ρ(n)}} = 0. $$ Furthermore, we prove that the numerator in this result is essentially optimal.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-06","reactions":{}}