User steve - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T08:05:35Z http://mathoverflow.net/feeds/user/8056 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/52988/palindromic-subsequences palindromic subsequences Steve 2011-01-23T20:09:53Z 2011-01-24T00:56:39Z <p>I'd like any insight or references to the following two conjectures (see the glossary below for definitions):</p> <p>Conjecture 1: For any string $x$, there exists a longest common subsequence of $x$ and its reversal $x^R$ that is a palindrome.</p> <p>Conjecture 2: For any string $x$ over a two-letter alphabet, all longest common subsequences of $x$ and $x^R$ are palindromes.</p> <p>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.</p> <p>Glossary:</p> <p>A <strong>string</strong> (or <strong>word</strong>) is any finite sequence of objects ("letters") drawn from some finite set (the "alphabet").</p> <p>For any string $x = x_1x_2\cdots x_{n-1}x_n$ of length $n$, the <strong>reversal</strong> of $x$ is $x^R := x_nx_{n-1}\cdots x_2x_1$.</p> <p>A string $x$ is a <strong>palindrome</strong> if $x = x^R$.</p> <p>A string $x$ is a <strong>subsequence</strong> of a string $y$ if $x$ results from $y$ by removing zero or more letters (in arbitrary locations, closing up any gaps that result).</p> <p>A <strong>longest common subsequence</strong> (<strong>LCS</strong>) 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, <em>Introduction to Algorithms</em>).</p> http://mathoverflow.net/questions/32986/how-fast-are-a-ruler-and-compass/33935#33935 Answer by Steve for How fast are a ruler and compass? Steve 2010-07-30T19:29:10Z 2010-07-30T19:29:10Z <p>Here is a construction showing that $D(n) \ge 2^{2^{n-O(1)}}$. This shows that any constant $c&lt;1$ in the original question can be achieved for sufficiently large $n$. The construction assumes some fixed (but arbitrary) positive integer $m$.</p> <ol> <li><p>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$.</p></li> <li><p>For $k = 1,2,3,\ldots,m$, do</p></li> </ol> <p>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.</p> <p>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.</p> <ol> <li>Using a constant number of moves, construct the reciprocal of $|z_m|$.</li> </ol> <p>Some things to observe:</p> <ol> <li>Step 2 uses exactly $m$ moves, so the total number of moves is $n = m + O(1)$.</li> <li>$z_k > 0$ for all even $k$, and $-iz_k > 0$ for all odd $k$.</li> <li>For all $k\in{1,\ldots,m}$, we have $|z_k| = \sqrt{1+|z_{k-1}|^2}-1 \le |z_{k-1}|^2/2$.</li> <li>The previous fact combined with induction on $k$ gives $|z_k| \le 2^{-(2^k-1)}$.</li> <li>Thus the point constructed in Step 3 has norm at least $2^{2^m-1} \ge 2^{2^{n-O(1)}}$.</li> </ol> http://mathoverflow.net/questions/52988/palindromic-subsequences/52999#52999 Comment by Steve Steve 2011-01-25T20:36:05Z 2011-01-25T20:36:05Z That's a nice, clean proof. Thanks! http://mathoverflow.net/questions/52988/palindromic-subsequences Comment by Steve Steve 2011-01-25T20:23:34Z 2011-01-25T20:23:34Z That is a better wording; thanks. I unconsciously took &quot;longest common subsequence&quot; as an unbreakable term of art. http://mathoverflow.net/questions/52988/palindromic-subsequences/53015#53015 Comment by Steve Steve 2011-01-25T20:17:36Z 2011-01-25T20:17:36Z Thanks for the reference. The problem is discussed there, but not solved.