Timeline for How to prove this polynomial always has integer values at all integers?
Current License: CC BY-SA 3.0
47 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 26, 2015 at 6:08 | vote | accept | Chitsai Liu | ||
| Sep 18, 2015 at 7:38 | answer | added | Wilberd van der Kallen | timeline score: 35 | |
| S Jun 27, 2015 at 8:16 | history | bounty ended | CommunityBot | ||
| S Jun 27, 2015 at 8:16 | history | notice removed | CommunityBot | ||
| Jun 26, 2015 at 13:50 | comment | added | Wadim Zudilin | Hypergeometric identities/transformations are often used to write different representations that are transparently integer-valued; see, e.g., arxiv.org/abs/math/0311195 or mathoverflow.net/questions/26336. In the present case the sum $\sum_{j=k}^m\frac{(-1)^jc_{m,j}}{2j+1}$ (I missed the sign $(-1)^j$ in the previous comment) assumes a completely different binomial form, and one can swap the summations over $j$ and $n$. Then the newer inner sum over $m-j$ (rather than $j$) is a partial sum of the Gauss hypergeometric function, so that one can use some further transformations... | |
| Jun 26, 2015 at 12:45 | comment | added | Chitsai Liu | @Wadim Zudilin, could you tell me why you apply hypergeometric functions transforms? I think your idea may lead us to the solution. | |
| Jun 26, 2015 at 10:15 | comment | added | Wadim Zudilin | It is nice to see that it is now reduced to showing that $$\frac32\binom{2k}{k}\sum_{j=0}^{k-1}\frac{c_{m,j}}{2j+1}\in\mathbb Z$$ for $k>[(m+1)/2]$, where $$c_{m,j}=\sum_{i=0}^m\frac{\binom{j}{i}\binom{m}{i}\binom{i}{m-j}}{(2i-1)(2m-2i-1)}.$$ The summation 4.6.1 from Bailey's book on Hypergeometric Functions transforms the coefficients to $$c_{m,j}=\frac{j!}{(1/2)_j(-m+1/2)_{j+1}(m-j)!}\sum_{n=[(m+1)/2]}^j\frac{(1/2)_n(-1/2)_n(-m+1/2)_n}{n!(2n-m)!}2^{2n-1},$$ where $(x)_n=\Gamma(x+n)/\Gamma(x)=x(x+1)\cdots(x+n-1)$ is Pochhammer's symbol. | |
| Jun 25, 2015 at 12:40 | comment | added | Wilberd van der Kallen | That must have been what I meant. | |
| Jun 25, 2015 at 12:37 | comment | added | Chitsai Liu | @Wilberd van der Kallen, I have verified via maple the identity $\sum_{i=0}^m\sum_{j=0}^m\frac{3 (-1)^{k+j}{2k \choose k }{j \choose i}{ m \choose i }{i \choose m-j }}{2(2i-1)(2j+1)(2m-2i-1)}=0$ for $m\ge 2$, which is interesting. | |
| Jun 25, 2015 at 11:54 | comment | added | Wilberd van der Kallen | $\sum_{i=0}^m\sum_{j=k}^m\frac{3 (-1)^{k+j}{2k \choose k }{j \choose i}{ m \choose i }{i \choose m-j }}{2(2i-1)(2j+1)(2m-2i-1)}$ equals $\sum_{i=0}^m\sum_{j=0}^{k-1}\frac{3 (-1)^{k+j}{2k \choose k }{j \choose i}{ m \choose i }{i \choose m-j }}{2(2i-1)(2j+1)(2m-2i-1)}$ for $k>1$. | |
| Jun 25, 2015 at 8:19 | comment | added | Wilberd van der Kallen | Experimentally ${x+j\choose j}{x-1\choose j}$ equals $\sum_{k=0}^j (-1)^{k+j} {2k\choose k} B_k(x)/2$. So $P_m(x)=\sum_{k=0}^m \sum_{i=0}^m\sum_{j=k}^m\frac{ 3(-1)^{k+j}{2k \choose k }{j \choose i}{ m \choose i }{i \choose m-j }}{2(2i-1)(2j+1)(2m-2i-1)} B_k(x)$ and one must show that $\sum_{i=0}^m\sum_{j=k}^m\frac{ 3(-1)^{k+j}{2k \choose k }{j \choose i}{ m \choose i }{i \choose m-j }}{2(2i-1)(2j+1)(2m-2i-1)}$ is an integer for $1\leq k\leq m$. Is this any easier? | |
| Jun 24, 2015 at 20:52 | comment | added | Martin Rubey | In fact, $b(n) = -(n+i-1)(120n^4 + 8(17i+38)n^3 + 8(i+1)(i+31)n^2 -4(2i^3+8i^2-36i-21)n-4(i-1)(4i^2+10i+3)$. | |
| Jun 24, 2015 at 20:32 | comment | added | Martin Rubey | In Wadim's basis it is easy to guess a second order recurrence $a(n) f_{n+2} + b(n) f_{n+1} + c(n) f_n = 0$ for any given coefficient. It appears that only $b(n)$ contains a nonlinear factor. Apparently, $a(n)=(n-i+1)(n+2)(n+i+1)(2n+2i+3)(3n+i+1)$, $b(n)=(n+i-1)p(n,i)$, $c(n)=32(n+i-2)(n+i-1)(2n+1)^2(3n+i+4)$ and $p(n,i)$ is some polynomial of degree 4 in $n$. Not sure how much this helps. | |
| Jun 24, 2015 at 10:01 | comment | added | Wilberd van der Kallen | @Wadim Zudilin. This $B_k$ basis is great. It shows for instance that it suffices to prove that $P_m(x)$ is an integer for integer $x$ between 0 and $m$. | |
| Jun 24, 2015 at 8:16 | comment | added | Wadim Zudilin | (3) Representation by means of $B_k(x)=\binom{x+k}{2k}+\binom{-x+k}{2k}$ is more economical, as $P_m(x)$ experimentally appears to be $\mathbb Z$-linear combination of $B_k(x)$ with $k>(m+1)/2$. | |
| Jun 24, 2015 at 8:15 | comment | added | Wadim Zudilin | There is something unnatural in the sum, so without any context it shows up it is hard to think of the options. (1) It is sufficient to establish the integral-valuedness of $P(x)$ by showing it for $1+\deg P$ consecutive integer values. The vanishing and symmetry of $P_m$ subsequently reduces the range. (2) The inner sum over $i$ is a well-poised $_4F_3(1)$ hypergeometric series; there are several transformations available for it but experimenting with them is time consuming. | |
| Jun 22, 2015 at 11:46 | history | edited | Chitsai Liu | CC BY-SA 3.0 |
deleted 2 characters in body
|
| Jun 22, 2015 at 4:39 | comment | added | Martin Rubey | @Kevin: sorry for being unclear. The recurrence should be true for your sum, i.e., the leading coefficient of $P_m(x)$, not for $P_m(x)$ itself. | |
| Jun 22, 2015 at 2:42 | history | edited | Chitsai Liu | CC BY-SA 3.0 |
added 443 characters in body
|
| Jun 22, 2015 at 2:37 | history | edited | Chitsai Liu | CC BY-SA 3.0 |
added 443 characters in body
|
| Jun 22, 2015 at 2:01 | comment | added | Chitsai Liu | @ Peter Mueller, Comparing the leading coefficient, we have $\sum_{i=0}^{m}{2m\choose m}{m\choose i}^2\frac{3}{(2i-1)(2m-2i-1)(2m+1)}$ is an integer. I think this sum has not a closed form. However, it is not difficulty to prove that it is an integer. | |
| Jun 22, 2015 at 1:44 | comment | added | Chitsai Liu | @Martin Rubey, The recurrence you gave was true only if $x=1$. For $x\ge 2$, $P_m(x)$ no longer satisfy the recurrence. | |
| Jun 21, 2015 at 21:31 | comment | added | Martin Rubey | @Kevin: its unlikely that this allows a closed form, but I don't have $A=B$, nor hyp.m handy. In any case, guessing the reccurrence yields $(m+2)^2(2m+5)(3m+2)f(m+2)-4m(30m^3+110m^2+128m+47)f(m+1)+32(m-1)(2m+1)^2(3m+5)f(m)=0$. | |
| Jun 21, 2015 at 18:32 | comment | added | Adam Przeździecki | @Kevin - could you tell us how you arrived at this formula? May be this would inspire some arguments... | |
| Jun 21, 2015 at 18:05 | comment | added | Peter Mueller | Comparing the leading coefficient of $P_m(x)$ with that of $\binom{x}{2m}$, one gets that $\frac{3}{(2m+1)(m-1)}\binom{2m}{m}\sum_{i=0}^m\binom{m}{i}^2\frac{1}{2i-1}$ is an integer provided that $P_m(\mathbb Z)\subseteq\mathbb Z$. Is this integrality known? I don't know if there is a closed expression for the sum. | |
| Jun 21, 2015 at 14:48 | history | edited | Chitsai Liu | CC BY-SA 3.0 |
added 426 characters in body
|
| Jun 21, 2015 at 13:15 | history | edited | Chitsai Liu | CC BY-SA 3.0 |
deleted 336 characters in body
|
| Jun 21, 2015 at 8:56 | comment | added | Wilberd van der Kallen | @Allen Knutson. My $q_{2n}$ span the space of even polynomials with integer values and with even value at zero. One sees this by showing that the determinant of the $(q_{2n}(i))$ matrix, $i=1,\dots,m$, $n=1,\dots,m$ equals one. Then your suspicion follows "easily". | |
| Jun 19, 2015 at 15:46 | comment | added | Wilberd van der Kallen | Put $q_n(x)={x\choose n}+{-x\choose n}$. Notice that $P_4(x)=-936q_2(x)+1522q_4(x)-704q_6(x)+118q_8(x)$. So it looks like the $P_n$ are integer combinations of the $q_{2n}$. | |
| Jun 19, 2015 at 6:59 | history | edited | Chitsai Liu | CC BY-SA 3.0 |
added 14 characters in body
|
| S Jun 19, 2015 at 6:42 | history | bounty started | Chitsai Liu | ||
| S Jun 19, 2015 at 6:42 | history | notice added | Chitsai Liu | Authoritative reference needed | |
| Jun 13, 2015 at 20:58 | comment | added | Timothy Chow | Given the form of the original expression, you might also try expanding in the basis $x+k\choose k$, to see if the coefficients look any nicer. By the way, does it seem that the coefficients of $P_m(x)$ in the $x\choose k$ basis are nonnegative for $m>1$? | |
| Jun 13, 2015 at 16:46 | comment | added | Lev Borisov | I have two questions/suggestions. Are the parts for fixed $i$ integer-valued? Are there some linear recursions on $P_m(x)$? | |
| Jun 13, 2015 at 11:16 | comment | added | Allen Knutson | I really don't know how to connect $\mathbb Z$-valuedness and evenness. If $x^2=y$ so we can rewrite $P(x)$ as $P(y)$, then $P$ being $\mathbb Z$-valued at all $y\in\mathbb Z$ is (much?) stronger than its being $\mathbb Z$-valued at all $x\in\mathbb Z$. Do your computed polynomials have $\mathbb Z$-coefficients expanded in $\{ {y \choose k} \}$? | |
| Jun 13, 2015 at 10:59 | comment | added | Allen Knutson | @DavidLoeffler : yes it has that effect, which means we've lost control of $a_0$ and $a_1$. I wrote "(assuming $Q(0)\in\mathbb Z$)" but meant $P(0)\in\mathbb Z$. How are you using evenness to control $a_1$, to establish this converse? | |
| Jun 13, 2015 at 8:30 | comment | added | Duchamp Gérard H. E. | @Kevin Maybe you have a "combinatorial interpretation" for your polynomials ? that means that your polynomials count something (like the hook formula) so that, for some $x\geq N(m)$ and $x\in \mathbb{N}$, you have $P_m(x)\in \mathbb{N}$. In this case, you can conclude. | |
| Jun 13, 2015 at 8:27 | history | edited | Chitsai Liu | CC BY-SA 3.0 |
deleted 14 characters in body
|
| Jun 13, 2015 at 8:13 | comment | added | David Loeffler | @AllenKnutson: Your comment (2) is a consequence of your comment (1) (and the converse is indeed true), because mapping $P$ to $Q$ in your notation has the effect of sending $\sum a_n \binom{x}{n}$ to $\sum a_{n + 2} \binom{x}{n}$, possibly up to some indexing shift. | |
| Jun 13, 2015 at 7:16 | comment | added | Chitsai Liu | @Allen Knutson, Thank you for your useful idea. I have listed the polynomials in basis $\{ {x\choose k} \}$. I think it is also hard to prove that $Q(x)$ is $\mathbb Z$-valued as you mentioned. | |
| Jun 13, 2015 at 7:01 | history | edited | Chitsai Liu | CC BY-SA 3.0 |
added 1 character in body
|
| Jun 13, 2015 at 6:53 | history | edited | Chitsai Liu | CC BY-SA 3.0 |
added 587 characters in body
|
| Jun 13, 2015 at 4:45 | comment | added | Allen Knutson | (1) The proper basis for the space of integer-valued polynomials is not monomials $\{x^k\}$ but binomial coefficients $\{ {x\choose k} \}$ (a polynomial is $\mathbb Z$-valued iff its unique expansion in this basis has $\mathbb Z$-coefficients). You should probably look into those expansions. (2) Let $Q(x) = P(x+1)+P(x-1)-2P(x)$, again even. If $P$ is $\mathbb Z$-valued, so is $Q$, and I suspect the converse is true for even functions (assuming $Q(0) \in \mathbb Z$). Perhaps you can use this for an inductive argument. | |
| Jun 13, 2015 at 4:45 | comment | added | GH from MO | Related question: mathoverflow.net/questions/190549/… | |
| Jun 13, 2015 at 3:44 | history | edited | GH from MO |
edited tags
|
|
| Jun 13, 2015 at 3:31 | history | edited | Chitsai Liu | CC BY-SA 3.0 |
added 65 characters in body
|
| Jun 13, 2015 at 3:17 | history | asked | Chitsai Liu | CC BY-SA 3.0 |