4
$\begingroup$

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$?

$\endgroup$
  • $\begingroup$ Is there some background to this question? The product of the coefficients of a poynomial is not a quantity that comes up very often, nor a particularly natural one (let alone the product of nonzero coefficients). $\endgroup$ – Emanuele Tron Jan 21 '17 at 15:59
  • $\begingroup$ This recurrence encodes (as a kind of generating function) the possible elements of the random Fibonacci sequence as the coefficients of the polynomials. The growth rate of the random Fibonacci sequence is related to the geometric mean of its elements. This is why I need the product of the (nonzero) coefficients. Could you give me some pointers to papers/topics where the product of polynomial coefficients come up? $\endgroup$ – Tamas Kalmar-Nagy Jan 21 '17 at 18:10
  • $\begingroup$ I don't know of any, that is why I asked. Anyway, if you wanna see for yourself how this grows, here's a naive PARI GP script: 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
  • 1
    $\begingroup$ Emanuele, I have numerical results, I would like an analytical approach. $\endgroup$ – Tamas Kalmar-Nagy Jan 21 '17 at 20:22
4
$\begingroup$

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!

| cite | improve this answer | |
$\endgroup$
  • 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$ – მამუკა ჯიბლაძე Jan 21 '17 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$ – მამუკა ჯიბლაძე Jan 21 '17 at 21:42
  • $\begingroup$ yes, I (mis)read it in the first non-TeX version :) $\endgroup$ – Pietro Majer Jan 21 '17 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$ – მამუკა ჯიბლაძე Jan 27 '17 at 7:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.