Proof that the following function is a polynomial

Question

I've been trying to get my head around this problem for a long time, yet I have not been able to make much progress.

Let $\ell_0(j) = \left\lfloor \frac{1}{2}\left( \sqrt{8j^2 - 8j + 1} + 2j - 1 \right) \right\rfloor$.

Then, prove that the following function $P(j,s)$ is a polynomial in $s$ for all positive integers $j$:

$$P(j,s) = \frac{1}{1 - s^{\ell_0(j)}}\sum_{\ell =1}^{\ell_0(j)}\left((-1)^\ell \left( \frac{s^{\ell(\ell+3)/2 - (j+1)\ell - j(j-1)/2}}{1-s^\ell} \right) \prod_{k=\ell}^{\ell_0(j)}(1-s^k)^2\right) $$

If anybody could suggest anything, I would greatly appreciate it. Thanks!

Answer 1

Here is some information pertaining to P(j,s):

I get the impression that if this function is used at all for anything the values that matter $s\in(0,1)$. Now for the actual functions:

$P(1,s)=-1$

$P(2,s)=-s^6+s^5+2 s^4-2 s^2-2 s+1$

$P(3,s)=-s^{30}+s^{29}+2 s^{28}-3 s^{25}-3 s^{24}-4 s^{23}+s^{22}+6 s^{21}+7 s^{20}+7 s^{19}+2 s^{18}-4 s^{17}-13 s^{16}-7 s^{15}-7 s^{14}+7 s^{12}+9 s^{11}+8 s^{10}-s^8-5 s^7-3 s^6-2 s^5+2 s^4+s^3+s^2+s-1$

$P(4,s)= -s^{54}+s^{53}+2 s^{52}-s^{50}-2 s^{49}-s^{48}-2 s^{47}-2 s^{46}+4 s^{44}+6 s^{43}+9 s^{42}+4 s^{41}-s^{40}-3 s^{39}-11 s^{38}-15 s^{37}-15 s^{36}-8 s^{35}+s^{34}+13 s^{33}+16 s^{32}+23 s^{31}+21 s^{30}+13 s^{29}-3 s^{28}-16 s^{27}-19 s^{26}-22 s^{25}-21 s^{24}-14 s^{23}+2 s^{22}+9 s^{21}+19 s^{20}+17 s^{19}+11 s^{18}+6 s^{17}+3 s^{16}-7 s^{15}-9 s^{14}-8 s^{13}-6 s^{12}+2 s^9+3 s^8+3 s^7+s^6-s^4+s^3-s^2-s+1$

$P(5,s)=-s^{85}+s^{84}+2 s^{83}-s^{81}-3 s^{80}-s^{78}+s^{76}-s^{75}+s^{74}+5 s^{73}+7 s^{72}+4 s^{71}+2 s^{70}-4 s^{69}-6 s^{68}-11 s^{67}-10 s^{66}-11 s^{65}-10 s^{64}-7 s^{63}+6 s^{62}+17 s^{61}+25 s^{60}+27 s^{59}+23 s^{58}+23 s^{57}+6 s^{56}-5 s^{55}-24 s^{54}-36 s^{53}-52 s^{52}-44 s^{51}-33 s^{50}-18 s^{49}-s^{48}+22 s^{47}+44 s^{46}+59 s^{45}+61 s^{44}+50 s^{43}+33 s^{42}+2 s^{41}-8 s^{40}-34 s^{39}-45 s^{38}-61 s^{37}-54 s^{36}-38 s^{35}-16 s^{34}+s^{33}+22 s^{32}+33 s^{31}+31 s^{30}+36 s^{29}+32 s^{28}+22 s^{27}+2 s^{26}-9 s^{25}-18 s^{24}-17 s^{23}-20 s^{22}-12 s^{21}-11 s^{20}-5 s^{19}+s^{18}+7 s^{17}+10 s^{16}+7 s^{15}+5 s^{14}+2 s^{13}+3 s^{12}-s^{11}-2 s^{10}-2 s^9-3 s^8-2 s^7+s^6+s^2+2 s-1$

$P(6,s)$ has $148$ terms so I will stop here. But, do you see the trend? Neither do I. I am posting this in case anyone who is interested in working on this has a good few data points about this function.

Answer 2

Some (possibly) useful simplications:

I thought it might be helpful to write $P(j,s)$ as \begin{equation*} P(j,s) = \frac{(1-s^{l_{0}(j)})}{s^{j(j-1)}}\sum_{l=1}^{l_{0}(j)}(-1)^{l}(1 - s^{l})s^{l(l+3)/2 - (j+1)l + j(j-1)/2} \prod_{k=l+1}^{l_{0}(j)-1}(1-s^{k})^{2}. \end{equation*} The benefit of this is that \begin{equation*} g(l) := l(l+3)/2 - (j+1)l + j(j-1)/2 = \frac{l^{2}}{2} - (j-\frac{1}{2})l + j(j-1)/2 \end{equation*} is a quadratic in $l$ whose minimum over $l \in \mathbb{Z}$ is $0$, which occurs at $l = j, j-1$. Simply observe that \begin{align*} g(j) & = \frac{j^{2}}{2} - j^{2} + j/2 + j(j-1)/2 = 0\\ g(j-1) & = \frac{(j-1)^{2}}{2} - (j-\frac{1}{2})(j-1) + j(j-1)/2\\ & = \frac{j^{2} - 2j + 1}{2} - j^{2} + j + \frac{j}{2} - \frac{1}{2} + \frac{j^{2}}{2} - \frac{j}{2}\\ & = 0. \end{align*}

So at this point one just has to show that \begin{equation} Q(j,s) = \sum_{l=1}^{l_{0}(j)}(-1)^{l}(1 - s^{l})s^{l(l+3)/2 - (j+1)l + j(j-1)/2} \prod_{k=l+1}^{l_{0}(j)-1}(1-s^{k})^{2} \end{equation} is divisible by $s^{j(j-1)}$, which is always a positive power of $s$ for integer $j$. One possible way to do this might be to show that $Q$ and its derivatives with respect to $s$ up to order $j(j-1) - 1$ are zero at $s = 0$. However, I'm not sure how to proceed with that yet.

Finally, I haven't verified it yet, but it seems that $l_{0}(j) = \lfloor ( 1+ \sqrt{2})j - \frac{1 + \sqrt{2}}{2} \rfloor$. I experimentally verified it for $1 \leq j \leq 1000000$ at least, but will have to do some floor manipulation to prove it if it is indeed true.