Code used in the paper “Twins in words and long common subsequences in permutations”
Upper bound on $\LT(k,n)$ (page 9)
In the paper it is proved that if $$(1-2\alpha)\log\frac{1}{1-2\alpha}-\alpha\log(\alpha^2k)-2\alpha\log\left(\frac{2}{1+\sqrt{1-1/k}}\right)+(1-2\alpha)\log(1-1/k)$$ is negative, then $\LT(k,n)\leq \alpha n$ for all sufficiently large $n$. It is then claimed that this implies that $$\LT(k,n)\leq \left(\frac{e}{\sqrt{k}}-\frac{e^2+1/2}{k}+O(k^{-3/2})\right)n+o(n)\qquad\text{for all large }k.$$ A more accurate claim is that $$\LT(k,n)\leq \left(\frac{e}{\sqrt{k}}-\frac{e^2+1/2}{k}+\frac{20e^4+30e^2-3}{24e\cdot k^{3/2}}\right)n+o(n)\qquad\text{for all large }k.$$ The latter claim is based on the following Mathematica code:
Expr = (1-2a)*Log[1/(1-2*a)] - a*Log[a^2*k] - 2*a*Log[2/(1+Sqrt[1-1/k])]+(1-2*a)*Log[1-1/k];
Asympt = E/Sqrt[k] - (E^2+1/2)/k + k^(-3/2)*(20*E^4+30*E^2-3)/(24*E);
Series[ Expr/.{a->Asympt}, {k,Infinity,2}]
which outputs the expression $(-1-3e^2-22e^4-8e^6)/6e^2 k^2+O(k^{-5/2})$, which is clearly negative.
The upper bounds on $\LT(4,n)$ and $\LT(5,n)$ are obtained by evaluating
Expr /. {a -> 0.4932, k -> 4}
and
Expr /. {a -> 0.48, k -> 5}
respectively.
Derivative of the lower bound on $M$ (page 14)
“A bit of calculus” on page 14 can be done by a machine via:FullSimplify[D[Binomial[x, 3] + Binomial[t - x, 3] + t*Binomial[x*(t - x)/t, 2], x]]
