I have spent some time using gp-pari. There is, of course, a **formal power series** solution to
$ f(f(x)) = \sin x.$ It is displayed below, identified by the symbol $g$ because I am not entirely sure whether it is a function of anything.

On the other hand, should the coefficients continue to (by and large) decrease, this suggests a nonzero radius of convergence. If the radius of convergence is nonzero, then inside that, not only is a function defined and, you know, analytic, but the functional equation is satisfied. Indeed, all that is necessary is radius of convergence strictly larger than $\frac{\pi}{2}$ owing to certain symmetries. For instance, given my polynomial $g,$ it seems we have $g=1$ at about $x \approx 1.14.$ Then we seem to have a local maximum at $x =\frac{\pi}{2},$ and apparently there $g \approx 1.14,$ strictly larger than 1 which is an important point. So everything would fall into place with large enough nonzero radius of convergence.

$$ \begin{array}{lll} g & = & x - \frac{x^3 }{ 12} - \frac{x^5 }{ 160} - \frac{53 x^7 }{ 40320} - \frac{23 x^9 }{71680} - \frac{92713 x^{11}}{1277337600} - \\\ & & \\\ & & \frac{742031 x^{13} }{79705866240} + \frac{594673187 x^{15} }{167382319104000} + \frac{329366540401 x^{17} }{91055981592576000} + \\\ & & \\\ & & \frac{104491760828591 x^{19} }{62282291409321984000} + \frac{1508486324285153 x^{21} }{4024394214140805120000} + \cdots \end{array} $$

Note that the polynomial $g$ is smaller than $x$ but larger that $\sin x,$ for, say, $0 < x \leq \frac{\pi}{2}.$

So, that is the question, does the formal power series beginning with $g$ converge anywhere other than $x = 0$?

EDIT: note that the terms after the initial $x$ itself have all turned out to be $$ \frac{a_{2 k + 3} x^{2 k + 3} }{2^k ( 2 k + 4)!} $$ where each $a_{2 k + 3}$ is an integer. This much seems provable, although I have not tried yet.

EDIT, Friday 12 November 2010. It now seems really unlikely that this particular problem gives an analytic answer. I suspect that the answer is $C^\infty$ and piecewise analytic, with failure of analyticity at only the points "parabolic" where the **derivative** has absolute value as large as 1, those points being $0,\pi, 2 \pi, \ldots.$ However, we need the anchor point at the fixpoint 0, otherwise how to begin? And I do think the power series will serve as an asymptotic expansion around 0.

Given the problem with the size of the derivative, now I am hoping for great things, and an obviously periodic and analytic solution, to the easier variant $f(f(x)) = g(x) = (1/2) \sin x.$ I would like both a nice power series and a nice answer by methods summing iterates $ g^{[k]}(x),$ which for the moment is an entirely mysterious method to me, but attractive for periodic target functions as periodicity would be automatic.

Enumerative Combinatorics, vol. 2. Part (c) of this exercise is concerned with the formal power series $h(x)$ satisfying $h(h(x))=e^x-1$ and seems to behave similarly to $f(x)$. – Richard Stanley Nov 11 '10 at 4:01