A recurrence is given by $f[0]=2x$, $f[1]=3x^3-x^2+x+1$, $$ f[n]=(x^{2^n}+1)f[n-1]+(x^{2^n}+1)(x^{2^n-1}+1) $$
How does the PRODUCT of the nonzero coefficients of $f[n]$ scale with $n$?
$\begingroup$
$\endgroup$
4
1 Answer
$\begingroup$
$\endgroup$
4
It follows by induction from the recursion that for all $n\ge2$ the polynomial $f_n$ writes as $f_n=(x^{2^{n}}+1)(x^{2^{n-1}}+1)g_n $ where $g_n$ satisfies $$\begin{cases} g_2:=3x+2 \\ g_n:=(x^{2^{n-2}}+1)g_{n-1}+1,\quad & \mathrm{if }\; n>2\end{cases}$$ and has degree $2^{n-1}-1$. Since $f_n=(x^{2^{n}}+1)(x^{2^{n-1}}+1)g_n $, the list of coefficients of $f_n$ is that of $g_n$ repeated $4$ times, and their product is the fourth power of the product $P_n$ of the coefficients of $g_n$. Also, the list of coefficients of $g_n$ is the one of $g_{n-1}$ repeated twice, with the constant term incremented by one. Thus the constant term is $g_n(0)=n$ and $$\begin{cases} P_2:=3\cdot 2, \\ P_n:= {n\over n-1}\ P_{n-1}^2\quad & \mathrm{if }\; n>2\end{cases}$$ whence it follows by induction, for $n\ge2$ $$P_n=3^{2^{n-2}}n\prod_{k=1}^{n-1}k^{2^{n-1-k}}.$$
So the product of coefficients of $f_n$ is $P_n^4=3^{2^{n}}n^4\prod_{k=1}^{n-1}k^{2^{n+3-k}}$, and as to how it scales with $n$ I'd say it is quite a lot larger. For a more precise asymptotics, $$\log P^4_n=2^{n}\bigg({\log3} +8\sum_{k=1}^{n-1}{\log k\over 2^k}+{4\log n\over 2^{n}}\bigg)=2^{n}\bigg({\log3} +8\sum_{k=1}^{\infty}{\log k\over 2^k} +o(1)\bigg).$$
[edit] sorry for mis-reading the correct definition of the iteration. The correct result is kindly given by მამუკა ჯიბლაძე in a comment below!
answered Jan 21, 2017 at 20:56
-
2$\begingroup$ I believe you have read in the question $x^{2^{n-1}}+1$ while it should be $x^{2^n-1}+1$ $\endgroup$ Commented Jan 21, 2017 at 21:14
-
3$\begingroup$ If it is the way my eyes see, it is still not difficult to compute, I've got$$ \left(2^7\times3\right)^{2^{n-3}}(n+1)^2(n+2)^2n^6\left(\prod_{k=5}^{n−1}k^{2^{n−k}}\right)^5$$ $\endgroup$ Commented Jan 21, 2017 at 21:42
-
$\begingroup$ yes, I (mis)read it in the first non-TeX version :) $\endgroup$ Commented Jan 21, 2017 at 21:56
-
1$\begingroup$ More "civilized" form:$$2^{2^{n-2}}3^{2^{n-3}}\left(\prod_{k=4}^{n-1}k^{2^{n-k}}\right)^5n^6(n+1)^2(n+2)^2,$$starting from $n=5$. $\endgroup$ Commented Jan 27, 2017 at 7:25
f(n,x)=if(n==0,return(2),if(n==1,return(3*x^3-x^2+x+1),return((x^(2^n)+1)*f(n-1,x)+(x^(2^n)+1)*(x^(2^n-1)+1))));g(n,x)=return(Vec(f(n,x)));product(v)={P=1;for(k=1,length(v),P=P*v[k]);return(P);};result(n)=product(g(n,x));$\endgroup$