Suppose f is a polynomial with complex coefficients. Is there a way to test if there are polynomials g and h with degree(h)>1 such that
f(z)=g(h(z)) identically? Is there a way to characterize such f and find the "factors" h and g?
Clearly the degree of f can't be prime. Also, for any complex c, h must map the solutions of "f(z)=c" to the solutions of "g(z)=c" so, for
example, h would need to map the roots of f to the roots of g, respecting multiplicities.
Any other thoughts?
Other urls found in this thread:
en.wikipedia.org
en.wikipedia.org
en.wikipedia.org
researchgate.net
twitter.com
My thoughts are that you can pass to an algebraic equation via
en.wikipedia.org
and going from small to high exponents (the higher use the smaller ones too),
maybe the solutions can be parameterized by h's coeffieints.
Yes, I you could (once you pick degrees for g and h) multiply out g(h(z)) and equate coefficients. This looks like it would be a mess though. I was wondering if there were a necessary condition based on examining the roots of f. For example, must every root of f have the same multiplicity which is >1 ? If b is a root of f with multiplicity m, then c=h(b) must be a root of g of multiplicity k that divides m, and b must be a root of h(z)-c of multiplicty m/k.. or some such. Seems like there should be a way to make this sharp.
it feels weird.
I feel like f and g can't contain as much information as f.
In fact I'm pretty sure that's key to the problem.
say f, g and h are of degree n, p and q with n=pq
f has n+1 independent coefficients.
g has only p+1, h has only q+1
so I would say a strong condition for f=g(h) would be that (p+1)+(q+1)>=n+1 (basically you need to have more degrees of freedom to be able to fit the resulting polynomial).
this results in p+q+1>=n, or p+q>n.
given pq=n, it's pretty hard to accomplish.
p+q>=pq implies 1/p+1/q >= 1, which is impossible unless p=q=2 and n=4
Is it possible to formalize this? I think the main tool would be that h has to map a certain number of complex numbers on the set of roots of g. But h only has so many roots, meaning a restriction on the degree of f.
also from n=4, p=q=2, the other constraints should be expressed pretty easily.
I shit the bed on this one, disregard this post.
Suppose f has degree n=pq with p,q>1. Suppose f has q distinct roots each with multiplicity p. Let h be the polynomial of degree q sharing the distinct roots of f. Let g(z)=z^p. Then it seems we have f(z) = g(h(z)).
Surely this is not the only possibility though?
A polynomial can be considered as a morphism of affine varieties [math]\displaystyle f: \mathbb A^1 \to \mathbb A^1[/math]. We get from this a map of polynomial rings [math]\displaystyle f^*: g \mapsto g \circ f[/math]. This map [math]\displaystyle f^*[/math] is an isomorphism if and only if f is, and f is an isomorphism if and only if [math]\displaystyle \frac {\mathrm d f} {\mathrm d x}[/math] is a nonzero constant, i.e. f is a linear polynomial.
So in your statement, any f can be factored uniquely through any linear polynomial h. I think this settles a simple first case that we can build off of.
Yes, I suggested the degrees should be bigger than 1 because it seemed likely that it is "doable" otherwise.
If f(z) = g( a z + b) for all z, then
f( (z-b)/a ) = g(z) for all z and you can just multiply the left hand side out to get g()
I was merely suggesting another way of viewing the problem that I think would be fruitful. The point was that you can say things about the image of [math]f^*[/math] (which is what you care about) simply in terms of properties of f, and I was hoping somebody would be aware of a result that would cover everything.
n=pq, p,q>1.
f degree n, n roots counting multiplicities
g degree p, p roots counting multiplicities
h degree q, q roots counting multiplicities
h maps roots of f to roots of g.
Suppose g(b)=0. Then h(z)-b = 0 has exactly q solutions, each of which must be a root of f. So h must divide the n roots of f into p disjoint
subsets of q elements each, and map each set to a root of g. But specifying one such subset mapping would typically be enough to determine h. The other subset mappings would have to agree.
Yes, I understood your intent and agree. Thank you.
1/3
So I decided not to be lazy and pulled though with the coefficient approach.
Here's how it went down for two an order 4 polynomial f(X).
So we want to factor it into two order 2 polynmomials, f(X)=g(h(X)).
I call the k's coefficient c(f,k), c(g,k), c(h,k), respectively.
I want to parameterize h in terms of g and f.
The equation f(X)=g(h(X)) is the 5 equations in pic related.
I have to solve 3 of those for c(h,k), which I do.
I take the first 3 equation. (Remark: one minus sign for a root, I have to choose)
I use the c(h,k) to compute g(h(X)).
This must equal f(X).
I chose the first 3 equations from top, so c(f,2), c(f,3) and c(f,4) are right by construction.
I find that c(f,1) is now fixed by those upper three.
On the other hand c(f,0) fixes one coefficient of g.
I relabel the free numbers for convenience.
I find the expression for c(f,0) and c(f,1) involve some determinant like term.
3/3
finally, I find h in terms of g and 3 coefficients of f.
To exemplify, I use the formula to construct a f (reminder: it's not free because I found one of it's 5 components to depend on the other) which can be factored in a nice way. (By nice way I mean I choose numbers to that the square roots and rational numbers all end up integers)
Use Bruno's formula to get [math]\frac{d^n}{dx^n}f[/math] in terms of g and h. Then evaluate each of these at [math]x = 0[/math]. This will give n + 1 equations for the derivatives of g and h in terms of f, so then with that, you'll have some degrees of freedom to fuck around with. Either way, once you've chosen values you like for the derivatives of g and h, you just sum them together like for a Taylor series, and you've got your functions. You could even make g and h infinite, and this could easily enough give you results there two for when the degree of f is prime.
en.wikipedia.org
Either way, it all seems kind of pointless, unless you're interested in some special forms of g and h, for example, solutions where all your coefficients are integers, or something like that. Then, in that case, maybe it could be an interesting problem.
So this maybe leads to the following crude algorithm, but does it work and is there something better?
Let's say the degree of f is n=15, and we want to try p=5,q=3 for the degrees of g and h. Go through all 455 ways of choosing 3 of the 15
roots of f. For each such way, say the roots are a,b and c, consider h(z)=(z-a)(z-b)(z-c). Using the relation x~y iff h(x)=h(y), see if the roots of f form 5 equivalence classes of 3 elements each. If so, then let g be the monic polynomial that has the 5 values of h as roots. Then f and g(h()) have the same roots. Scaling g by a constant gives f.
The tl;dr is that I found that I can factor a polynomial
f(X) := f0 + f1·X + x·X^2 + y·X^3 + z·X^4
via
f(X) = g(h(X))
in C^2 many ways (i.e. two complex coefficients of g to be chossen freely) and where h is fixed by g,
but where however f1 is determined by x,y,z, namely
f1 = (4xyz-y^3) / (8z^3)
and f0 fixes one component of g.
Would this be any different from just assuming, for example, h=h0+h1 z + h2 z^2 +... and g=g0+g1 z + g2 g^2 + ... up to some order, substituting, multiplying it out, and equating coefficients? it seems the resulting equations would be horrible to try to solve.
Indeed, I was thinking about this for polynomials having integer coefficients. The problem came to mind while finding polynomial solutions to Diophantine equations.
Interesting! Took me a while to work through your Mathematica, which I stink at. The 2 degrees of freedom perhaps follows from
Do you think in general coefficients can be solved for one at a time, or would it require simultaneous solution? It seems the latter would be very difficult.
It seems to work. Matlab/Octave code below. The problem of course is that "N choose K" gets big fast. So if there is some other way I would like to know.
clear all
p=5; % degree of g
q=3; % degree of h
n=p*q; % degree of f
g=rand(1,p+1)+rand(1,p+1); % random poly g
h=rand(1,q+1)+rand(1,q+1); % random poly h
% compute f, where f(z)=g(h(z))
f=g(1);
for k=2:p+1
f=conv(f,h);
f(end)=f(end)+g(k);
end
% try to "factor" f
rf=roots(f); % get the roots of f
R=rf(nchoosek([1:n],q)); % roots of f taken q at a time
N=size(R,1); % should have N = nchoosek(n,q)
minerr=inf;
for k=1:N
H=ones(size(rf)); % will hold h(roots)
for j=1:q
H=H.*(rf-R(k,j)); % evaluate H at the roots
end
H=reshape(sort(H),q,p).';
err=max(abs(var(H,[],2))); % err=0 if grouped properly
if minerr>err
minerr=err;
mink=k;
end
end
minerr
Playing around with this code, I find that normalizing h by requiring h to be monic (leading coefficient 1) and to satisfy h(0)=0 typically gives a unique h. I suppose though it would depend on symmetries in the roots of f.
The octave/matlab code works well for cases like n=36, p=9, q=4, as long as the coefficients aren't so large as to cause overflow with double types.
Still looking for a better answer.
This thread kind of shows what's shitty about Veeky Forums.
If a problem comes along where people come around and actually put some time in for once, nobody (not even OP) even comments on it or makes them feel their effort is appreciated.
Of course people then stick to the easy arguing threads.
I (OP) am trying to answer and encourage comments. I seem to be pretty much alone here though, except for a couple others who were gracious enough to contribute a few posts. I came up with the code.
Your point is well-taken though. I posted because I thought it was an interesting problem some might like to think about. Sometimes posting gets results, some times it doesn't.
If you want h to have real coefficients, and correct me if you don't, then anytime you choose a complex root you must choose its conjugate as well. That will at least somewhat scale down the number of combinations to check.
Yes, I agree. I am interested in anything to cut down the time of the algorithm. Taking advantage of having real coefficients when appropriate makes sense.
Don't know if anyone's mentioned this, but if g shares any of the same roots as f, then h must map 0 to 0, i.e. its constant term is 0.
This isn't obvious to me. Can you explain?
I would also be interested in extending this to rational functions, thought of as n-fold mappings of the Riemann sphere to itself. In this case you would have some collection of zeros and poles. I am wondering how hard it would be to adapt the code above to handle this case.
en.wikipedia.org
So I (OP) decided to google and found this from 2011:
researchgate.net
"Abstract
In this note we explore when a polynomial f(x) can be expressed as a composition of other polynomials. First, we give a necessary and sufficient condition on the roots of f(x). Through a clever use of symmetric functions we then show how to determine if f(x) is expressible as a composition of polynomials without needing to know any of the roots of f(x)."
Sounds good! I'm betting the root condition is similar to what we've discussed... they must be partitionable into equivalence classes by some h.
But the paper abstract also says it's possible to test without finding the roots! Very interesting.
Bump. Anyone have access to this? How to do without finding the roots?
I switched g and h by accident in my post, which might have confused you, but I'll go through it anyways.
Let f(x) = g(h(x)), and assume that f(x) = h(x) = x for some x. Equivalently, f and h share a root. Then g(h(x)) = g(0) = f(x) = 0. So g(0) = 0, which implies that the constant term in g must be 0.
>f(x) = h(x) = x
That should be f(x) = h(x) = 0.
I suck today.
...
...
...
...
...
...
Thanks a million for uploading this! This page answers exactly the question I had from the start of this post. I look forward to seeing how it works.
I'm surprised this wasn't done prior to 2011. Note also the guy who wrote this was in high school at the time. Thanks again.
I understand this now with g and h switched. Thank you.