Modular congruences related to sums of Catalan numbers - MathOverflow

Modular congruences related to sums of Catalan numbers

2010-08-27T16:28:36Z

I am curious if somebody can be helpful concerning the following experimental observation:

There exist two rational sequences $\alpha_0,\alpha_1,\dots$ and $\beta_0,\beta_1,\dots$, both with values in $\mathbb Z[1/3]$ such that $$\sum_{k=0}^{p-1}{2k\choose k}\frac{k^j}{k+1}\equiv \alpha_j+p\beta_j\pmod{p^2}$$ for every prime number $p\equiv 1\pmod 6$ and $$\sum_{k=0}^{p-1}{2k\choose k}\frac{k^j}{k+1}\equiv -(-1)^j-\alpha_j+p\beta_j\pmod{p^2}$$ for every prime number $p\equiv 5\pmod 6$.

(More precisely, the sequences $3^n\alpha_n$ and $3^n\beta_n$ are seemingly integral.)

The sequence $\alpha_0,\alpha_1,\dots$ starts as $$1, 0, -2/3, 4/3, -22/9, 140/27, -14, 1316/27, -17078/81, 87860/81, -1562042/243, 31323292/729, \dots$$ and the first terms $\beta_0,\beta_1,\dots$ are $$0,0,2/3,-2,14/3,-34/3,98/3,-350/3,1526/3,-2622,46634/3,-311734/3,2316158/3, -18920018/3,\dots$$

Let me end by remarking that one has as a special case a similar result when replacing Catalan numbers by central binomial coefficients.

Update: The existence of the sequence $\alpha_n$ is explained by the Zhi-Wei Sun paper, see the answer by dke below.

Experimentally, the quotient sequence $\frac{\beta_n}{\alpha_n}$ (defined for $n\geq 2$) seems to converge very quickly towards $-\frac{4\sqrt{3}\pi}{9}=-2.4183991523\dots$ (the error is smaller than $10^{-78}$ for $n=120$).

The sequence $\frac{\alpha_{n+1}}{\alpha_n}-\frac{\alpha_n}{\alpha_{n-1}}$ converges perhaps (fairly slowly) towards something like $-.72\dots$.

Answer by dke for Modular congruences related to sums of Catalan numbers

2010-08-28T20:04:12Z

Just a quick thought about showing that $3^n\alpha_n$ is integral. It's not too hard to prove via the Catalan number generating function that \[\sum_{k=0}^{p-1} C_kx^k\equiv \frac{1-(1-4x)^{(p+1)/2}}{2x}-x^{p-1}\quad\bmod (p,x^p).\] Now apply $D=x\frac{d}{dx}$ a bunch of times and set $x=1$ to get the sums you want. Then by using $(-3)^{(p-1)/2}\equiv \left(\frac{p}{3}\right)\bmod p$ you can control the 3-adic valuation (you get an extra 3 for each differentiation) and see that the only dependence on $p$ is the Legendre symbol $\left(\frac{p}{3}\right)$ which furthermore depends only on $p$ modulo 3. There's also a 2 in the denominator but I guess by looking a bit more carefully you can show this cancels out for $p$ not equal to 3. This is a bit sketchy but hopefully the idea is there.

In particular, letting Sage do the work, I get \[\sum_{k=0}^{p-1}C_k\equiv \frac{{\left(\frac{p}{3}\right)}-1}{2}\quad\bmod p\] \[\sum_{k=0}^{p-1}kC_k\equiv \frac{{-\left(\frac{p}{3}\right)}+1}{2}\quad\bmod p\] \[\sum_{k=0}^{p-1}k^2C_k\equiv \frac{-{\left(\frac{p}{3}\right)}-3}{6}\quad\bmod p\] which seem to fit your sequence as well as the results in the Zhi-Wei Sun paper.

I can't see how to get at the $\beta_j$ though.

Edited to add: one can maybe do the same trick using \[\sum_{k=0}^{p-1} C_kx^k\equiv \frac{1-(1-4x)^{(p^2+1)/2}}{2x}-px^{p-1}\quad\bmod (p^2,x^p)\] to get the $\beta_j$ as well, though I'm not so convinced.

Answer by Wadim Zudilin for Modular congruences related to sums of Catalan numbers

2010-10-12T09:03:36Z

I wonder about the reason to consider $$ A_j=\sum_{k=0}^{p-1}\frac{k^j}{k+1}\binom{2k}{k} $$ instead of $$ \tilde A_j = \sum_{k=0}^{p-1} k^j \binom{2k}{k}, $$ as $A_j\pm A_0$ ($+$ for odd $j$ and $-$ for even $j$) are reduced to linear combinations of the latter. Let me introduce the functions $$ F_j(x)=\left(x\frac{d}{dx}\right)^j\sum_{k=0}^{p-1}\binom{2k}{k}x^k, $$ so that $\tilde A_j=F_j(1)$. Note that $$ F_0(x)=F(x)=\sum_{k=0}^{p-1}\binom{2k}{k}x^k $$ satisfies the differential equation $$ F(x)-\frac12(1-4x)F'(x)=\frac{(2p-1)!}{(p-1)!^2}x^{p-1}. $$ Here the coefficient on the right is $$ \frac{(2p-1)!}{(p-1)!^2}\equiv p\pmod{p^4} $$ by Wolstenholme's theorem and we can write the equation in the form $$ xF_0(x)-\frac12(1-4x)F_1(x)=\frac{(2p-1)!}{(p-1)!^2}x^p. $$ Applying repeatedly the operator $x\dfrac{d}{dx}$ to both sides of the identity produces, for each $j$, a relation of the form $$ P_{0,j}(x)F_0(x)+P_{1,j}(x)F_1(x)+\dots+P_{j-1,j}(x)F_{j-1}(x)-\frac12(1-4x)F_j(x)=p^{j-1}\frac{(2p-1)!}{(p-1)!^2}x^p, $$ where all coefficients of the polynomials $P_{i,j}(x)$ are integral (and, of course, independent of $p$). This gives a way to express $\frac32F_j(1)=\frac32\tilde A_j$ as a $\mathbb Z$-linear combination of $\tilde A_0,\tilde A_1,\dots,\tilde A_{j-1}$ independently of $p$ modulo $p^j$. The remaining piece is to check that $\tilde A_0$ and $\tilde A_1$ as well as the starting $A_0$ do satisfy the "$p$-independence" property modulo $p^2$.

The construction above gives a recipe to construct recursively the sequence $\tilde A_j$ (hence $A_j$), although I do not try myself to figure out a closed-form evaluation of the auxilliary polynomials $P_{i,j}(x)$ and/or their values at $x=1$.