User steve - MathOverflow

palindromic subsequences

2011-01-23T20:09:53Z

I'd like any insight or references to the following two conjectures (see the glossary below for definitions):

Conjecture 1: For any string $x$, there exists a longest common subsequence of $x$ and its reversal $x^R$ that is a palindrome.

Conjecture 2: For any string $x$ over a two-letter alphabet, all longest common subsequences of $x$ and $x^R$ are palindromes.

Conjecture 2 is not true for strings over a three-letter alphabet, a counterexample being $abacbab$, which has $abcab$ and $bacba$ as longest common subsequences.

Glossary:

A string (or word) is any finite sequence of objects ("letters") drawn from some finite set (the "alphabet").

For any string $x = x_1x_2\cdots x_{n-1}x_n$ of length $n$, the reversal of $x$ is $x^R := x_nx_{n-1}\cdots x_2x_1$.

A string $x$ is a palindrome if $x = x^R$.

A string $x$ is a subsequence of a string $y$ if $x$ results from $y$ by removing zero or more letters (in arbitrary locations, closing up any gaps that result).

A longest common subsequence (LCS) of two strings $x$ and $y$ is a string $z$ that is a subsequence of both $x$ and $y$ such that no string longer than $z$ has this property. Generally, $x$ and $y$ may have several different LCSs. There is a well-known algorithm to find an LCS of two given strings that runs in quadratic time (see e.g., Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms).

Answer by Steve for How fast are a ruler and compass?

2010-07-30T19:29:10Z

Here is a construction showing that $D(n) \ge 2^{2^{n-O(1)}}$. This shows that any constant $c<1$ in the original question can be achieved for sufficiently large $n$. The construction assumes some fixed (but arbitrary) positive integer $m$.

Using a constant number of moves, draw both the real and imaginary axes, and mark the points $A = -i$ and $B = -1$. Let $z_0 = 1$.
For $k = 1,2,3,\ldots,m$, do

a) If $k$ is odd, then draw a circle centered at $A$ and passing through $z_{k-1}$. Let $z_k$ be the intersection of this circle with the positive imaginary axis.

b) If $k$ is even, then draw a circle centered at $B$ and passing through $z_{k-1}$. Let $z_k$ be the intersection of this circle with the positive real axis.

Using a constant number of moves, construct the reciprocal of $|z_m|$.

Some things to observe:

Step 2 uses exactly $m$ moves, so the total number of moves is $n = m + O(1)$.
$z_k > 0$ for all even $k$, and $-iz_k > 0$ for all odd $k$.
For all $k\in{1,\ldots,m}$, we have $|z_k| = \sqrt{1+|z_{k-1}|^2}-1 \le |z_{k-1}|^2/2$.
The previous fact combined with induction on $k$ gives $|z_k| \le 2^{-(2^k-1)}$.
Thus the point constructed in Step 3 has norm at least $2^{2^m-1} \ge 2^{2^{n-O(1)}}$.

Comment by Steve

2011-01-25T20:36:05Z

That's a nice, clean proof. Thanks!

Comment by Steve

2011-01-25T20:23:34Z

That is a better wording; thanks. I unconsciously took "longest common subsequence" as an unbreakable term of art.

Comment by Steve

2011-01-25T20:17:36Z

Thanks for the reference. The problem is discussed there, but not solved.