# Where in mathematics do these polynomials appear?

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.

-
I've been asking this question for about 12 years, which is when I first computed the expected Euler characteristic of some random simplicial complexes. I have no answer to your question, but I feel like I should point out that the roots of these polynomials fall into intriguing patters. – Jeff Strom Mar 28 '14 at 17:15
@Jeff, what type of random simplicial complexes were you considering? Are these the same polynomials that you found? These polynomials are related to the expected Euler characteristics of the random cubical complexes that I describe in my paper (linked above). – M Wright Mar 28 '14 at 18:00

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.

-
In contrast to the answer by KConrad, this is correct. The analogue of my computation in the comment there is that $(L+I)^2$ maps any polynomial $P$ to $$(L+I)(P[x:=x^2]+P) = (P[x:=x^2]+P)[x:=x^2] + P[x:=x^2]+P = P[x:=x^2][x:=x^2] + 2P[x:=x^2] + P = P[x:=x^4] + 2P[x:=x^2] + P$$ which is also what $L^2+2L+I$ does. Substituting $x^2$ for $x$ (which I wrote $x:=x^2$) is a linear operation on polynomials, squaring is not. – Marc van Leeuwen Mar 27 '14 at 11:16

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.

-

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$

-
well that's what Prof. Wright meant by '' For k≥1, the polynomial f_k seems similar to (x−1)^k, but all of its terms have exponents that are powers of 2'' – Harry Huang Apr 5 '14 at 7:13
Well that is also why i dont get any upvote:) Anyways it is still better then a downvote:) – UserErdos Apr 6 '14 at 15:59