Simple and general relation between continuant polynomials - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T00:28:44Z http://mathoverflow.net/feeds/question/91648 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/91648/simple-and-general-relation-between-continuant-polynomials Simple and general relation between continuant polynomials kakaz 2012-03-19T18:26:11Z 2012-03-20T11:45:21Z <p>Continued fraction $[a_0,a_1,...,a_n]$ may be expressed as quotient of two polynomials of $(a_0,a_1,...,a_n)$, named continuants (see <a href="http://en.wikipedia.org/wiki/Continuant_%28mathematics%29" rel="nofollow">http://en.wikipedia.org/wiki/Continuant_%28mathematics%29</a> )</p> <p>$[a_0,a_1,...,a_n] = K(a_0,a_1,...,a_n)/K(a_1,...,a_n)$</p> <p>For example $K(a_0,a_1,a_2,a_3) = a_{0} a_{1} a_{2} a_{3} + a_{0} a_{1} + a_{0} a_{3} + a_{2} a_{3} + 1$</p> <p>Continuants has many interesting recurrence relations some of which You may find in Graham, Knuth, Patashnik book "Concrete mathematics". Continuants appears for example in Hopcroft's minimization algorithm. </p> <p>I found interesting relation:</p> <p>$K( a_0,a_1,...,a_k,a_{(k+1)},...,a_n ) =$</p> <p>$K(a_0,a_1,...,a_k,1,1,a_{(k+1)},...a_n) - K(a_0,a_1,...,a_k,1,a_{(k+1)},...a_n)$</p> <p>that is - between variables $a_k$ and $a_{(k+1)}$ You put two of "1" in the firs and one "1" in the second term... You may consider this as generalisation of Fibonacci recurrence - because if You put all $a_i =1$ You obtain Fibonacci numbers. </p> <p>For example: $K(a_0,a_1,a_2) = (a_0 a_ 1+1)a_2+a_0$ $K(a_0,a_1,1,1,a_2) = (2 a_0 a_1+ a_0+2)a_2+a_0 a_1+a_0+1$ $K(a_0,a_1,1,a_2) = (a_2+1)(a_0 a_1+1)+a_0 a_2$</p> <p>And it is true that:</p> <p>$K(a_0,a_1,a_2) = K(a_0,a_1,1,1,a_2) - K(a_0,a_1,1,a_2)$</p> <p><strong>I am curious - is this known fact? Or something new?</strong></p> <hr> <p>How to proove it - I found finite closed expression for continuant polynomial $K(a_0,a_1...a_n)$ in the form:</p> <p>(1) $x = [a_{0},a_{1},a_{2},...a_{n}] =\frac{K(a_0,a_1,...,a_n)}{K(a_1,...,a_n)}= - \frac{1}{2} \frac{Tr \left( M(S- L) \right) }{Tr \left( M(S-T) \right) }$</p> <p>where M is continuant matrix 2x2 and $S,T,L$ and $I$ (unity matrix) are constant matrices which form base in $SL(2,Z)$ space - they are defined in Sage workbook accesible for download here: <a href="http://fiksacie.wordpress.com/2012/03/17/ulamki-lancuchowe-nonstandard-matrix-representation-of-continued-fractions-cz-5/" rel="nofollow">http://fiksacie.wordpress.com/2012/03/17/ulamki-lancuchowe-nonstandard-matrix-representation-of-continued-fractions-cz-5/</a> There is also several essays about that on my blog - in polish. Proof is simple linear algebra exercise: </p> <p>start from monoid formed by $S,T$ generators ( which represent in nonstandard way moves on Stern-Brocot tree - standard way consists of R-ight, and L-eft, RL matrices) and then construct ring over <strong>rationals</strong> with $I,S,T,L$ generators, and then formula above appears. M is defined as follows ( it is continuant matrix representation for given continued fraction $x = [a_{0},a_{1},a_{2},...a_{n}]$ )</p> <p>(2) $M = S \prod_{i=0}^{n} S(ST)^{a_{i}}$. </p> <p>$S$ is that $S^2 =I$ and $T$ is that $T^2 = I+T$ so </p> <p>$I = T^2 -T = S(ST)S(ST) - S(ST)$ </p> <p>Then You may insert it in any place between $S(ST)^{a_{i}}S(ST)^{a_{i+1}}$ which gives expression above and many more if You consider $T^p$ for $p \in Z$ etc. </p> <hr> <p>It is worth to note that in the general ring $Q[{I,S,T,L}]$ matrix $M$ has decomposition in the form $M=aI+bS+cT+dL$ with rational $a,b,c,d$ and that continued fractions form algebraic curve which equations is given by bilinear form $\left| w^TBw \right| = 1$ where $w=[a,b,c,d]$ - column vector where $a,b,c,d$ are integers (there are additional inequalities for this coefficients - because $M$ has to have positive elements)</p> <p>Please note that (1) and (2) allows similarity transformations, and then You may choose any base in SL(2,Z) space and that whole construction may be easily generalized to bigger than 2x2 dimensional matrices. I have many questions here to ask, some of which are:</p> <p>(A) are there irreducible representations of this construction in SL(D,Z) spaces where D>2?</p> <p>(B) are there representations in complex number set ${z_1,...z_4}$ which obeys the same multiplication table as for $I,S,T,L$ matrices? How to express (1) in that case? </p> <p>(C) probably there is possibility to construct pure algebraical representation in which continued fractions are generalised to values of operator which should be generalisation of rhs of (1). How to do it?</p> <p>I am not professional mathematician - I have problems if it is worth to publish it, where to do it etc. </p> http://mathoverflow.net/questions/91648/simple-and-general-relation-between-continuant-polynomials/91695#91695 Answer by Johann Cigler for Simple and general relation between continuant polynomials Johann Cigler 2012-03-20T08:51:45Z 2012-03-20T08:51:45Z <p>As Gerry remarked it follows from the recursion of the continuants. By the recurrence of the continuants you have ${K_{k + 3}}({a_0}, \cdots ,{a_k},1,1) = {K_{k + 2}}({a_0}, \cdots ,{a_k},1) + {K_{k + 1}}({a_0}, \cdots ,{a_k}).$ Therefore ${K_{k + 4}}({a_0}, \cdots ,{a_k},1,1,{a_{k + 1}}) = {a_{k + 1}}{K_{k + 3}}({a_0}, \cdots ,{a_k},1,1) + {K_{k + 2}}({a_0}, \cdots ,{a_k},1)$, ${K_{k + 3}}({a_0}, \cdots ,{a_k},1,{a_{k + 1}}) = {a_{k + 1}}{K_{k + 2}}({a_0}, \cdots ,{a_k},1) + {K_{k + 1}}({a_0}, \cdots ,{a_k}),$ ${K_{k + 2}}({a_0}, \cdots ,{a_k},{a_{k + 1}}) = {a_{k + 1}}{K_{k + 1}}({a_0}, \cdots ,{a_k}) + {K_k}({a_0}, \cdots ,{a_{k - 1}}).$ This implies ${K_{k + 4}}({a_0}, \cdots ,{a_k},1,1,{a_{k + 1}}) = {K_{k + 3}}({a_0}, \cdots ,{a_k},1,{a_{k + 1}}) + {K_{k + 2}}({a_0}, \cdots ,{a_k},{a_{k + 1}}).$ By induction your result follows.</p>