Exact threshold conjecture for the Semple–Steel bound with r-state characters

Let $d_r(n)$ be the maximum, over all binary phylogenetic trees with $n$ leaves, of the minimum number of $r$-state characters required to define the tree. Let $n_r$ be the least integer $N$ such that the Semple–Steel lower bound is attained for every $n\geq N$, namely $d_r(n)=\left\lceil\frac{n-3}{r-1}\right\rceil$. Exact threshold conjecture. For every $r\geq4$,

$$n_r=3r+1.$$

Moreover, whenever $n\geq3r+1$, there is an explicit construction of

$$\left\lceil \frac{n-3}{r-1} \right\rceil$$

$r$-state characters defining any prescribed binary phylogenetic tree with $n$ leaves. The paper proves the lower bound $n_r\geq3r+1$ and an upper bound of order $O(r\log r)$; the conjecture asserts that the lower bound is exact and that the bound can be attained constructively from this threshold onward.