Where in mathematics do these polynomials appear?

Question

Does anyone recognize the following sequence of polynomials?

$f_0(x) = x-1$
$f_1(x) = x^2-x$
$f_2(x) = x^4-2x^2+x$
$f_3(x) = x^8-3x^4+3x^2-x$
$f_4(x) = x^{16}-4x^8+6x^4-4x^2+x$
$\vdots$

The polynomials satisfy the recurrence $f_{k+1}(x) = f_k(x^2) - f_{k}(x)$, for $k \ge 0$.

I came across these polynomials in my research (for details, see http://arxiv.org/abs/1402.5367, in particular Table 1), and I want to know where else they appear in mathematics. For $k \ge 1$, the polynomial $f_k$ seems similar to $(x-1)^k$, but all of its terms have exponents that are powers of $2$. I have asked several mathematicians, but so far no one has recognized this sequence of polynomials.

Answer 1

Not a truly satisfying answer, but maybe it puts things under a slightly more natural view. Consider the linear map $L$ on the space $k[x]$ such that $Lp(x):=p(x^2)$ . So $(L-I)^k$ expands by the binomial theorem, and $f_k=(L-I)^kf_0$ .

edit I. And, of course $(L-I)[1]=0$ , whence the form of your polynomials. That said, I'm sorry that I have no idea either, of where these polynomials may appear in mathematics.

A possible source. Let $S$ be the shift operator on sequences, and let $M$ be the sequence $M(k):=x^{2^k}$, for a given $x$. Then $f_n(x)$ is also equal to $[(S-I)^n M](0)$, the $n$-th finite difference at $k=0$ of the sequence $M$. Let in particular $x\ge 1$. I would like to believe that there is a measure $\mu_x$ that solves the Stieltjes moment problem on $[0,\infty)$ wrto the sequence of weights $M$, that is $$x^{2^n}=\int_0^\infty t^n d\mu_x(t)\, ,$$

so that the $p_k$ would have a representation by the kernel $\{\mu_x\}_{x\ge1}$ $$p_k(x)=\int_0^\infty (t-1)^n d\mu_x(t).$$

edit II. I've made some experiment by Maple to see if the compatibility condition (see the link) is fulfilled, that is, the non-negativity of $\Delta_n(x):=\operatorname{det}\Big(x^{2^{i+j}}\Big)_{0\le i < n \atop 0\le j< n} $ and of $\Delta_n(x^2)$. In fact for $n\le 5$ it is true that $\Delta_n(x)>0$ for all $x> 1$, as it follows from the factorizations:

$$\Delta_1(x)=x;$$ $$\Delta_2(x)=x^4(x-1);$$ $$\Delta_3(x)=x^{12}(x^2-1)(x^3-1)(x^4-1) (x^3+x+1) ;$$ $$\Delta_4(x)=x^{32}(x-1)(x^2-1)(x^3-1)(x^4-1)(x^6-1)(x^7-1)\,$$ $$ (1+x+2\,{x}^{2}+3\,{x}^{3}+2\,{x}^{4}+3\,{x}^{5}+4\,{x}^{6}+4\,{x}^{7} +4\,{x}^{8}+6\,{x}^{9}+5\,{x}^{10}+4\,{x}^{11}+5\,{x}^{12}+4\,{x}^{13} +4\,{x}^{14}+4\,{x}^{15}+5\,{x}^{16}+3\,{x}^{17}+3\,{x}^{18}+2\,{x}^{ 19}+3\,{x}^{20}+2\,{x}^{21}+2\,{x}^{22}+2{x}^{23}+2\,{x}^{24}+{x}^{ 26}+{x}^{27}+{x}^{28}+{x}^{30});$$ $$\Delta_5(x)=x^{80}(x^2-1) (x^3-1) (x^4-1) (x^5-1)(x^6-1) (x^7-1)(x^8-1)(x^9-1)(x^{12}-1)$$ $$(x^{14}-1) (x^8-x^7 + x^5 -x^4 +x^3 -x +1) P(x)$$ and $P(x)$ is a $183$-degree polynomial with non-negative integer coefficients.

Answer 2

The polynomials $f_k(x), k\geq1$, have 0 and 1 as roots and so we can divide out by $x^2-x$; after factoring them out we seem to be getting an irreducuble polynomial; that was what Sage gave me for $k\leq11$. And that irreducible factor's coefficients have a nice pattern--they are the same in blocks.

Answer 3

I have just found this closed form for f and hope it might help a bit and verified it for $ k=1, 2, 3, 4 $here the formula $ f_k (x)= \binom{k}{k}(x^2)^{2^{k-1}}-\binom{k}{k-1} (x^2)^{2^{k-2}}+\binom{k}{k-2}(x^2)^{2^{k-3}}+\cdots+\binom{k}{0} (-1)^k+(x-1)(-1)^k$