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$?
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this communityA 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$?
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!
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$ – Emanuele Tron Jan 21 '17 at 18:37