17
$\begingroup$

The question is motivated by yet another possible approach to a combinatorial problem formulated previously in "Special" meanders. I'm not giving details of the connection as I believe the question is sufficiently motivated by itself.

I've got a vector space with basis $\left\{e_n\mid n\geqslant0\right\}$ and scalar product $$ \left\langle e_m,e_n\right\rangle=q^{\gcd(m,n)} $$ (with the convention $\gcd(0,n)=n$ for all $n\geqslant0$).

What I need is a maximally explicit expression for an orthogonal basis $\left\{o_n\mid n\geqslant0\right\}$ with respect to this scalar product. I do not mind if the $o_n$ are not of unit norm (and this is clearly a minor point anyway).

Here are the first few values (calculated with MAPLE). Up to arbitrary rescalings, \begin{align*} o_{{0}}&=e_{{0}}\\ o_{{1}}&=e_{{1}}-qe_{{0}}\\ o_{{2}}&=e_{{2}}- \left( q+1 \right) e_{{1}}+qe_{{0}}\\ o_{{3}}&=e_{{3}}-qe_{{2}}-e_{{1}}+qe_{{0}}\\ o_{{4}}&=\left( q+1 \right) e_{{4}}-{q}^{2}e_{{3}}- \left( {q}^{2}+q+1 \right) e_{{2}}+{q}^{2}e_{{1}}+{q}^{2}e_{{0}}\\ o_{{5}}&=\left( {q}^{2}+q+1 \right) e_{{5}}- \left( {q}^{2}+1 \right) qe_{{4}}- \left( {q}^{2}+1 \right) qe_{{3}}+ \left( {q}^{3}-{q}^{2}-1 \right) e_{{1}}+ \left( {q}^{2}+1 \right) qe_{{0}}\\ o_{{6}}&=\left( {q}^{3}+{q}^{2}+2\,q+1 \right) e_{{6}}- \left( {q}^{3} +q-1 \right) qe_{{5}}- \left( {q}^{3}+q-1 \right) qe_{{4}}\\&- \left( {q} ^{2}+1 \right) \left( {q}^{2}+q+1 \right) e_{{3}}- \left( {q}^{3}+{q} ^{2}+2\,q+1 \right) e_{{2}}+ \left( 2\,{q}^{4}+{q}^{3}+3\,{q}^{2}+1 \right) e_{{1}}+ \left( {q}^{3}+q-1 \right) qe_{{0}}\\ o_{{7}}&=\left( {q}^{2}+1 \right) e_{{7}}- \left( {q}^{2}-q+1 \right) qe_{{6}}- \left( {q}^{2}-q+1 \right) qe_{{5}}- \left( {q}^{2}-q+1 \right) qe_{{4}}\\&+ \left( {q}^{2}-q+1 \right) qe_{{2}}+ \left( {q}^{3} -2\,{q}^{2}+q-1 \right) e_{{1}}+ \left( {q}^{2}-q+1 \right) qe_{{0}} \end{align*}

The inverse transformation (again up to rescalings) does not look any more enlightening (except that everything is positive):

\begin{align*} e_{{0}}&=o_{{0}}\\ e_{{1}}&=o_{{1}}+qo_{{0}}\\ e_{{2}}&=o_{{2}}+ \left( q+1 \right) o_{{1}}+{q}^{2}o_{{0}}\\ e_{{3}}&=o_{{3}}+qo_{{2}}+ \left( {q}^{2}+q+1 \right) o_{{1}}+{q}^{3}o_ {{0}}\\ e_{{4}}&=o_{{4}}+{\frac {{q}^{2}}{q+1}}o_{{3}}+ \left( {q}^{2}+1 \right) o_{{2}}+ \left( q+1 \right) \left( {q}^{2}+1 \right) o_{{1}} +{q}^{4}o_{{0}}\\ e_{{5}}&=o_{{5}}+{\frac { \left( {q}^{2}+1 \right) q}{{q}^{2}+q+ 1}}o_{{4}}+{\frac {q \left( {q}^{2}+1 \right)}{q+1}} o_{{3}}+q \left( {q}^{2} +1 \right) o_{{2}}+ \left( {q}^{4}+{q}^{3}+{q}^{2}+q+1 \right) o_{{1}} +{q}^{5}o_{{0}}\\ e_{{6}}&=o_{{6}}+{\frac { \left( {q}^{3}+q-1 \right) q}{{q}^{3}+ {q}^{2}+2\,q+1}}o_{{5}}+{\frac { \left( {q}^{3}+q-1 \right) q}{{q}^{2} +q+1}}o_{{4}}+{\frac { \left( {q}^{2}+q+1 \right) \left( {q}^{2}-q+1 \right)}{q+1}} o_{{3}}\\ &+ \left( {q}^{2}+q+1 \right) \left( {q}^{2}-q+ 1 \right) o_{{2}}+ \left( q+1 \right) \left( {q}^{2}+q+1 \right) \left( {q}^{2}-q+1 \right) o_{{1}}+{q}^{6}o_{{0}}\\ e_{{7}}&=o_{{7}}+{\frac { \left( {q}^{2}-q+1 \right) q}{{q}^{2}+ 1}}o_{{6}}+{\frac { \left( {q}^{2}+q+1 \right) \left( {q}^{2}-q+1 \right) q}{{q}^{3}+{q}^{2}+2\,q+1}}o_{{5}}+ \left( {q}^{2}-q+1 \right) qo_{{4}}\\ &+{\frac {q \left( {q}^{2}+q+1 \right) \left( {q}^{2}-q+1 \right)}{q+1}}o_{{3}} +q \left( {q}^{2}+q+1 \right) \left( {q}^{2}-q+1 \right) o_{{2}} + \left( {q}^{6}+{q}^{5}+{q}^{4}+{q}^{3}+{q}^{2}+q+1 \right) o_{{1}}+{q}^{7}o_{{0}}\\ e_{{8}}&=o_{{8}}+{\frac { \left( {q}^{2}+1 \right) {q}^{4}}{ \left( {q}^{2}+q+1 \right) \left( {q}^{3}+q+1 \right) }}o_{{7}}+{\frac {{q} ^{4}}{{q}^{2}+q+1}}o_{{6}}+{\frac { \left( {q}^{2}+1 \right) {q}^{4}}{{q}^{3}+{q}^{2}+2\,q+1}}o_{{5}}\\ &+{\frac { {q}^{6}+{q}^{4}+{q}^{2}+q+1 }{{q}^{2}+q+1}}o_{{4}} +{\frac {{q}^{2} \left( {q}^{2}+q+1 \right) \left( {q}^{2}-q+1 \right)}{q+1}}o_{{3}}+ \left( {q}^{2}+1\right) \left( {q}^{4}+1 \right) o_{{2}}+ \left( q+1 \right) \left( {q}^{2}+1 \right) \left( {q}^{4}+1 \right) o_{{1}}+{q}^{8}o_{ {0}} \end{align*}

There are some patterns, but I cannot even guess any statement that I could try to prove about these coefficients. Also the above was computed under the assumption that the transformation matrix is triangular, i. e. that $o_n$ only depends on $e_k$ with $k\leqslant n$. It is quite possible that there is a nicer basis which violates this assumption, but again I cannot think of any natural alternative form of the transformation matrix.

What I know is an explicit orthogonal basis for a similar scalar product "without $q$": if I would have just $\left\langle e_m,e_n\right\rangle=\gcd(m,n)$, then an orthogonal basis would be given by $e_n=\sum_{d|n}o_d$, so $o_n=\sum_{d|n}\mu\left(\frac nd\right)e_d$. Strangely enough, I obtain this from the above by substituting $q=0$, and again I have no idea why.

As @alpoge points out in a comment, if one removes $e_0$, then this actually works "with $q$" too.

PS As suggested by @Wolfgang in a comment, I've looked at polynomials resulting from the substitutions $q=\pm1$, $e_n=x^n$. Here:

$q=1$: \begin{align*} &1\\ &x-1\\ & \left( x-1 \right) ^{2}\\ & \left( x+1 \right) \left( x-1 \right) ^{2}\\ & \left( x+1 \right) \left( 2\,x+1 \right) \left( x-1 \right) ^{2}\\ & \left( x+1 \right) \left( 3\,{x}^{2}+x+2 \right) \left( x-1 \right) ^{2}\\ & \left( x+1 \right) \left( 5\,{x}^{3}+4\,{x}^{2}+8\,x+1 \right) \left( x-1 \right) ^{2}\\ & \left( x+1 \right) \left( {x}^{2}+x+1 \right) \left( 2\,{x}^{2}-x+1 \right) \left( x-1 \right) ^{2}\\ & \left( x+1 \right) \left( 9\,{x}^{5}+7\,{x}^{4}+14\,{x}^{3}+10\,{x}^ {2}+6\,x+2 \right) \left( x-1 \right) ^{2}\\ & \left( x+1 \right) \left( 11\,{x}^{6}+8\,{x}^{5}+16\,{x}^{4}+10\,{x} ^{3}+15\,{x}^{2}+9\,x+3 \right) \left( x-1 \right) ^{2}\\ & \left( x+1 \right) \left( 7\,{x}^{5}+6\,{x}^{4}+5\,{x}^{3}+4\,{x}^{2 }+10\,x+1 \right) \left( {x}^{2}+1 \right) \left( x-1 \right) ^{2}\\ & \left( x+1 \right) \left( 16\,{x}^{8}+11\,{x}^{7}+22\,{x}^{6}+12\,{x }^{5}+18\,{x}^{4}+3\,{x}^{3}+9\,{x}^{2}-6\,x+5 \right) \left( x-1 \right) ^{2}\\ & \left( x+1 \right) \left( 21\,{x}^{9}+19\,{x}^{8}+38\,{x}^{7}+34\,{x }^{6}+51\,{x}^{5}+45\,{x}^{4}+39\,{x}^{3}+33\,{x}^{2}+6\,x+2 \right) \left( x-1 \right) ^{2} \end{align*} $q=-1$: \begin{align*} 0&:1\\ 1&:1+x\\ 2&:\left( x-1 \right) \left( 1+x \right)\\ 3&:\left( x-1 \right) \left( 1+x \right) ^{2}\\ 4&:- \left( x-1 \right) \left( 1+x \right) ^{2}\\ 5&:\left( x-1 \right) \left( {x}^{2}+x+2 \right) \left( 1+x\right) ^{2}\\ 6&:-\left( x-1 \right) \left( {x}^{3}+2\,{x}^{2}+2\,x+3 \right) \left( 1+x \right) ^{2}\\ 7&:\left( x-1 \right) \left( {x}^{2}+x+1 \right) \left( 2\,{x}^{2}- x+3 \right) \left( 1+x \right) ^{2}\\ 8&:-\left( x-1 \right) \left( {x}^{4}+2\,{x}^{2}+2 \right) \left( 1 +x \right) ^{3}\\ 9&:\left( x-1 \right) \left( {x}^{5}+{x}^{4}+{x}^{3}+3\,{x}^{2}+3 \right) \left( 1+x \right) ^{3}\\ 10&:- \left( x-1 \right) \left( {x}^{2}+1 \right) \left( {x}^{5}+2\, {x}^{4}+{x}^{3}+2\,{x}^{2}+2\,x+3 \right) \left( 1+x \right) ^{2}\\ 11&:\left( x-1 \right) \left( 4\,{x}^{8}+{x}^{7}+8\,{x}^{6}+2\,{x}^{ 5}+12\,{x}^{4}+3\,{x}^{3}+11\,{x}^{2}+4\,x+5 \right) \left( 1+x \right) ^{2} \end{align*}

Improve this question
$\endgroup$
13
  • 1
    $\begingroup$ Have you tried putting $q=1$ and replacing $e_i$ by $x^i$ in the $o_j$ expressions? The resulting polynomials seem to split into linear and quadratic factors, and maybe you'll find some patterns in those factors, which might give some ideas to start with. $\endgroup$
    – Wolfgang
    Commented Jun 30, 2015 at 13:00
  • 5
    $\begingroup$ Formally doesn't $o_n := \sum_{d\vert n} \mu(d) e_{n/d}$ for $n > 0$ and $o_0 := e_0 - \sum_{n\geq 1} o_n$ work? (Not that that helps much, since the expression for $o_0$ is nonsense.) $\endgroup$
    – alpoge
    Commented Jul 1, 2015 at 21:06
  • 2
    $\begingroup$ Just a remark\restatement, nothing fancy: Let $A_{i,j} = q^{(i,j)}$ be a $(n+1) \times(n+1)$ matrix. Decompose $A$ as $B^T B$ (Cholesky-Decomposition; $B$ can be upper-triangular). The condition that $o_i = \sum_{j} o_{i,j} e_j$ are orthonormal w.r.t to the given inner product is the same as requiring that $B o_i$ are orthonormal w.r.t to the ordinary inner product, so we can take $o_i = B^{-1} e_i$. Hence the problem reduces to Cholesky-decomposing $A$, and inverting. Bruce Sagan's talk here about GCD-matrices might provide useful input: users.math.msu.edu/users/sagan/Slides/mfp5.pdf $\endgroup$
    – Ofir Gorodetsky
    Commented Jul 1, 2015 at 21:55
  • 1
    $\begingroup$ @alpoge But this is great! I was sticking to $e_0$ so much it never occurred to me that dropping it gives such a nice orthogonal basis! It is true that I still need $e_0$ essentially (it is the unit of certain algebra), but your version does almost all of it. Could you please post this as an answer? It's worth it in any case, and if nobody will find a way to incorporate $e_0$ I will go for it $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Jul 2, 2015 at 2:45
  • 1
    $\begingroup$ @OfirGorodetsky Thanks for the link! Reading that - seems an interesting idea to give it a combinatorial interpretation in terms of the Möbius function of some poset. In fact this might be important for the original problem which is of combinatorial nature. $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Jul 2, 2015 at 2:49

0

Reset to default

You must log in to answer this question.