A possible converse to the Cayley-Hamilton theorem?

Solution 1:

You write

The way we write down $p$ matters, e.g. although $x(x−1)=x^2−x$, the resulting PFE $f(f(x)−x)=0$ and $f(f(x))−f(x)=0$ are different.

This example suggests that you would consider the following to be a counter-example: Take $f(z) = z^2$ and observe that $$f \circ (2f) = 4 f \circ f.$$ Thus $f$ obeys the "polynomial" $x(2x) - 4 x^2$. Since $f$ is not bijective, it is certainly not conjugate linear.

More generally, if $f(x)$ is any polynomial of degree $d$, then the infinite list of functions $f(kf(x))$ will all be polynomials of degree $d^2$. The space of polynomials of degree $d^2$ is a vector space of dimension $d^2+1$, so there will be a linear relations between these compositions.

I was not able to find a non conjugate linear example of a function obeying $\sum c_j f^j(z)=0$ for nonzero $c_j$.