Maths Olympiad Prep

Library / /28 of 31

Algebra Difficulty 8.8 Shortlist Prove it Baltic Way

A polynomial f(x)f(x) with real coefficients is called generating, if for each polynomial φ(x)\varphi(x) with real coefficients there exists positive integer kk and polynomials g1(x),,gk(x)g_1(x), \dots, g_k(x) such that
φ(x)=f(g1(x))++f(gk(x)). \varphi(x) = f(g_1(x)) + \dots + f(g_k(x)).

Find all generating polynomials.

Solution

Answer: the generating polynomials are exactly the polynomials of odd degree.
Take an arbitrary polynomial ff. We call a polynomial good if it can be represented as f(gi(x))\sum f(g_i(x)) for some polynomials gig_i. It is clear that the sum of good polynomials is good, and if φ\varphi is a good polynomial then each polynomial of the form φ(g(x))\varphi(g(x)) is good also. Therefore for the proof that ff is generating it is sufficient to show that xx is good polynomial. Consider two cases.

1) Let the degree nn of ff is odd. Check that xx is good polynomial. Observe that by substitutions of the form f(ux)f(ux) we can obtain a good polynomial ϕn\phi_n of degree nn with leading coefficient 11, and a good polynomial ψn\psi_n of degree nn with leading coefficient 1-1 (because nn is odd). Then for each aa a polynomial ϕn(x+a)+ψn(x)\phi_n(x+a) + \psi_n(x) is good. It is clear that its coefficient of xnx^n equals 00; moreover, by choosing appropriate aa we can obtain a good polynomial ϕn1\phi_{n-1} of degree n1n-1 with leading coefficient 11, and a good polynomial ψn1\psi_{n-1} with leading coefficient 1-1. Continuing in this way we will obtain a good polynomial ϕ1(x)=x+c\phi_1(x) = x + c. Then ϕ1(xc)=x\phi_1(x - c) = x is also good.

2) Let the degree nn of ff is even. Prove that f(x)f(x) is not generating. It follows from the observation that the degree of every good polynomial is even in this case. Indeed, the degree of each polynomial f(gi)f(g_i) is even and the leading coefficient has the same sign as the leading coefficient of ff. Therefore the degree of polynomial f(gi(x))\sum f(g_i(x)) is even.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.