Rational congruence of binomial coefficient matrices - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T11:36:22Z http://mathoverflow.net/feeds/question/26520 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/26520/rational-congruence-of-binomial-coefficient-matrices Rational congruence of binomial coefficient matrices Timothy Chow 2010-05-31T00:28:26Z 2010-06-01T20:58:12Z <p>Skip Garibaldi asks if there is an elementary proof of the following fact that "accidentally" fell out of some high-powered machinery he was working on.</p> <p>Say that two matrices $A$ and $B$ over the rationals are <i>rationally congruent</i> if there exists a nonsingular matrix $S$ over the rationals such that $S^t A S = B$.</p> <p><b>Theorem</b> (Garibaldi). Suppose $n \equiv 0 \pmod 4$. Then the diagonal matrices $$A = diag\left[\binom{n}{0}, \binom{n}{2}, \binom{n}{4}, \ldots, \binom{n}{n/2 - 2}\right]$$ and $$B = diag\left[\binom{n}{1}, \binom{n}{3}, \binom{n}{5}, \ldots, \binom{n}{n/2 - 1}\right]$$ are rationally congruent. Similarly, suppose $n \equiv 2 \pmod 4$. Then the matrices $$A = diag\left[\binom{n}{0}, \binom{n}{2}, \binom{n}{4}, \ldots, \binom{n}{n/2 - 1}\right]$$ and $$B = diag\left[\binom{n}{1}, \binom{n}{3}, \binom{n}{5}, \ldots, \binom{n}{n/2 - 2}, \frac{1}{2}\binom{n}{n/2}\right]$$ are rationally congruent.</p> http://mathoverflow.net/questions/26520/rational-congruence-of-binomial-coefficient-matrices/26609#26609 Answer by Will Jagy for Rational congruence of binomial coefficient matrices Will Jagy 2010-05-31T17:39:35Z 2010-05-31T18:19:38Z <p>This is far too long for a comment. From a pantload of experience finding explicit rational congruences, I can suggest that this problem could be decided by actual formulas. In any case finding some specific matrices ought to be instructive. My difficulty is that the numbers have passed what I can manage with my C++ programs ( I do not have n=12 explicit), plus I never wrote anything for 4 by 4 or larger. </p> <p>Well, if we multiply both sides of a rational congruence by the square of the LCM $k$ of the "denominators" we get an integral "congruence" $$P^t A P = k^2 B.$$ where $P$ is integral. For $n=4,$ where $A$ is diag(1) and $B$ is diag(4) we just get $k=2$ and $P$ is diag(2).</p> <p>For $n=6,$ with $A= diag(1,15)$ and $B=diag(6,10)$ we get $k=2$ and<br> $$P \; \; = \; \;<br> \left( \begin{array}{cc} 3 &amp; 5\\ -1 &amp; 1<br> \end{array} \right) .$$</p> <p>For $n=8,$ with $A= diag(1,28)$ and $B=diag(8,56)$ we get $k=2$ and<br> $$P \; \; = \; \; \left( \begin{array}{cc} 2 &amp; 14\\ -1 &amp; 1<br> \end{array} \right) .$$</p> <p>For $n=10,$ with $A= diag(1,45,210)$ and $B=diag(10,120,126)$ we get $k=7$ and<br> $$P \; \; = \; \; \left( \begin{array}{ccc} 10 &amp; 30 &amp; -63\\ 2 &amp; 6 &amp; 7 \\ 1 &amp; -4 &amp; 0<br> \end{array} \right) .$$</p> <p>The bad news for me is that $n=12$ began to run into bounds on my C++ program. So I wanted to show others how to find these matrices in computer languages with unbounded integers. The main things are that you should assume that, while there will be infinitely many possible "denominators" $k$ that work, both for computational and perceptual purposes it is worth investigating the smallest values $k= 1,2,3,\ldots$ first. Next, given a value $k,$ we do not attempt to vary all $n^2$ elements in the matrix $P.$ This is computationally infeasible. Instead, make a list of possible column 1's, then a list of possible column 2's, and so on. Once the $n$ lists of columns are complete, do what probably amounts to what they call "backtracking," meaning that you pick a column 1 ( meaning $c_1^t \; A \; c_1 = k^2 B_{11}$), then a column 2, if those are compatible so far ($c_2^t \; A \; c_1 = 0$) then pick a column 3, and so on. </p> <p>As $A$ and $B$ are diagonal we automatically get multiple copies of essentially the same matrices with the only change being $\pm$ signs. But I am really impressed that there has been essentially one matrix $P$ for each $k.$ This tells me that there may be predictable patterns in the triple $(n,k,P),$ different for $n \equiv 0,2 \pmod 4$ but perhaps related in some way all the same. </p> <p>Please contact me with any questions. Just click on <a href="http://www.ams.org/cml" rel="nofollow">http://www.ams.org/cml</a> and search for my last name.</p> http://mathoverflow.net/questions/26520/rational-congruence-of-binomial-coefficient-matrices/26645#26645 Answer by Wadim Zudilin for Rational congruence of binomial coefficient matrices Wadim Zudilin 2010-06-01T01:03:03Z 2010-06-01T01:03:03Z <p>Expecting to be criticised, I nevertheless try to explain an approach to the problem (for the first case). Assume that there exist two family of polynomials $P_i(t)$ and $\hat P_i(t)$, $i=0,1,\dots,n-1$, each spanning the space of polynomials of degree less than $n$ such that $$\sum_{i=0}^{n-1}\binom{4n}{2i}P_i(t)^2 =\sum_{i=0}^{n-1}\binom{4n}{2i+1}\hat P_i(t)^2$$ identically in $t$; this, for example, happens if the both sides are equal for $n$ distinct points. Then replacing the monomials $t^0,t^1,\dots,t^{n-1}$ by variables $t_0,t_1,\dots,t_{n-1}$ we obtain the linear forms $L_i(t_0,t_1,\dots,t_{n-1})$ and $\hat L_i(t_0,t_1,\dots,t_{n-1})$ such that $L_i(1,t,\dots,t^{n-1})=P_i(t)$ and $\hat L_i(1,t,\dots,t^{n-1})=\hat P_i(t)$, $i=0,1,\dots,n-1$, and $$\sum_{i=0}^{n-1}\binom{4n}{2i}L_i(t_0,t_1,\dots,t_{n-1})^2 =\sum_{i=0}^{n-1}\binom{4n}{2i+1}\hat L_i(t_0,t_1,\dots,t_{n-1})^2,$$ the desired equivalence. So far, I could only manage some examples of the polynomial expansions, like $$\frac{(1+t)^{4n}+(1-t)^{4n}}{2t^{2n}} =\sum_{i=0}^{2n}\binom{4n}{2i}t^{2i-2n} =\sum_{i=0}^{n-1}\binom{4n}{2i}(t^{-2(n-i)}+t^{2(n-i)})+\binom{4n}{2n}$$ $$=\sum_{i=0}^{n-1}\binom{4n}{2i}(t^{n-i}-t^{-(n-i)})^2+\sum_{i=0}^{2n}\binom{4n}{2i}$$ $$=\biggl(t-\frac1t\biggr)\sum_{i=0}^{n-1}\binom{4n}{2i}P_i\biggl(t+\frac1t\biggr)^2+2^{4n-1},$$ in other words, $$\sum_{i=0}^{n-1}\binom{4n}{2i}P_i\biggl(t+\frac1t\biggr)^2 =\frac{(1+t)^{4n}+(1-t)^{4n}-2^{4n}t^{2n}}{2t^{2n}(t-1/t)}.$$ So, the question is whether we can write the rational function on the right-hand side as $$\sum_{i=0}^{n-1}\binom{4n}{2i+1}\hat P_i\biggl(t+\frac1t\biggr)^2.$$</p> http://mathoverflow.net/questions/26520/rational-congruence-of-binomial-coefficient-matrices/26693#26693 Answer by darij grinberg for Rational congruence of binomial coefficient matrices darij grinberg 2010-06-01T10:54:26Z 2010-06-01T20:58:12Z <p>Wadim, isn't that 95% of the proof? First let me correct your first displayed equation (thanks to fherzig for pointing this out): It is not sufficient for the proof, but $$\sum_{i=0}^{n-1}\binom{4n}{2i}P_i(t)P_i(s) =\sum_{i=0}^{n-1}\binom{4n}{2i+1}\hat P_i(t)\hat P_i(s)$$ is, where $t$ and $s$ are two independent variables.</p> <p>Let me rename your $P_i$ as $Q_{2i}$ and your $\hat{P_i}$ as $Q_{2i+1}$, so that your equation $$\sum_{i=0}^{n-1}\binom{4n}{2i}P_i(t)P_i(s) =\sum_{i=0}^{n-1}\binom{4n}{2i+1}\hat P_i(t)\hat P_i(s)$$ becomes $$\sum_{i=0}^{2n-1}\left(-1\right)^i\binom{4n}{i}Q_i(t)Q_i(s)=0.$$ Now let $Q$ be the polynomial $Q\left(t\right)=t^{n-1}$ (I suspect the below proof works with any polynomial $Q$ of degree $n-1$ (not less!), but I'm not completely sure and don't have the time to check) and let $Q_i\left(t\right)=\left(2n-i\right)Q\left(t-\left(2n-i\right)^2\right)$ for every $i\in\mathbb Z$. Being a polynomial in $i$ of degree $2\left(2\left(n-1\right)+1\right)&lt;4n$ (for fixed $t$ and $s$), the term $Q_i\left(t\right)Q_i\left(s\right)$ satisfies $$\sum_{i=0}^{4n}\left(-1\right)^i\binom{4n}{i}Q_i(t)Q_i(s)=0,$$ since the $4n$-th finite difference of a polynomial of degree $&lt; 4n$ is zero. Due to the symmetry of the function $i\mapsto Q_i\left(t\right)Q_i\left(s\right)$ around $i=2n$, and due to $Q_{2n}\left(t\right)=0$, this becomes $$\sum_{i=0}^{2n-1}\left(-1\right)^i\binom{4n}{i}Q_i(t)Q_i(s)=0.$$ Now it remains to prove that each of the families $\left(Q_1,Q_3,...,Q_{2n-1}\right)$ and $\left(Q_0,Q_2,...,Q_{2n-2}\right)$ spans the space of all polynomials in $t$ of degree $&lt; n$. This is a particular case of a more general fact: If $x_1$, $x_2$, ..., $x_n$ are $n$ pairwise distinct reals, then the polynomials $\left(t-x_1\right)^{n-1}$, $\left(t-x_2\right)^{n-1}$, ..., $\left(t-x_n\right)^{n-1}$ are linearly independent. In order to prove this, assume that they are linearly dependent, take their derivatives of all possible orders, evaluate at $t=0$, and get a contradiction because Vandermonde's determinant is nonzero.</p> http://mathoverflow.net/questions/26520/rational-congruence-of-binomial-coefficient-matrices/26736#26736 Answer by fherzig for Rational congruence of binomial coefficient matrices fherzig 2010-06-01T16:38:16Z 2010-06-01T17:15:50Z <p>There is a problem with this approach (I refer to Wadim Zudilin's answer). At least I don't see how to get from the first displayed equation (involving the $P_i$) to the second (involving the $L_i$) in his post.</p> <p>Here is an example:</p> <p>$(t^2+t-2)^2 + (3t+2)^2 + 1^2 = (t^2+t+2)^2 + (t+2)^2 + 1^2$</p> <p>but </p> <p>$(t_2+t_1-2t_0)^2 + (3t_1+2t_0)^2 + t_0^2 \ne (t_2+t_1+2t_0)^2 + (t_1+2t_0)^2 + t_0^2$,</p> <p>by considering the coefficient of $t_0t_2$ or of $t_1^2$. Clearly, if the second equation were true it would imply the first. But the problem with the converse is that the first involves 5 degrees of freedom (the coefficients of $t^i$ with $0 \le i \le 4$), whereas the second has 6 (the coefficients of the $t_it_j$ with $i \le j$).</p> <p><strong>Edit:</strong> Here is a better example:</p> <p>$(t^2+1)^2 -2 (t)^2 + 1^2 = (t^2-1)^2 + 2 (t)^2 + 1^2$,</p> <p>but the two forms $diag(1,-2,1)$ and $diag(1,2,1)$ don't even have the same signature.</p>