From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math,sci.math.num-analysis Subject: Re: help: solve this functional relation Date: 25 Nov 1996 21:08:24 GMT In article <56maqc$dlo@hecate.umd.edu>, Jason Stratos Papadopoulos wrote: >Hello. I've run across a problem that has me stumped. How would >you go about finding a function "f" such that > > 1 1 >f ( ----------- ) = j f( --- ) ? > 2(1+j)(1-j) 1-j > ... >Anyway, j is supposed to be close to 1, and an asymptotic series for f is > > 2 3 4 5 > (j-1) (j-1) (j-1) 23 (j-1) 263 (j-1) >f(j) = 1 + ----- - ------ + ------ - --------- + ---------- - .... > 3 45 189 14175 4677775 > >Can such a problem even be solved in closed form? I'm a little confused here; if you take j close to 1 in the top equation, you'll find yourself evaluating f at very large arguments; in the final line, you are evaluating f near 1. Is that really your intent? I also feel something must be amiss here: I don't think there are any nice nonzero functions satisfying the proposed functional equation. Functional equations such as this arise frequently in this newsgroup so if you don't mind I'll generalize your question a little (you can keep generalizing much more). The typical question here reads "What function f satisfies f(h(x))= G(x, f(x)) for all x?" (where the functions h and G are given explicitly). The first thing to keep in mind is that _the solution is not unique_ (usually). For example, in the original poster's situation, if f is any function satisfying the functional equation, then any scalar multiple c.f also satisfies that relation. The second thing to worry about is that _you need to be clear about the domain of f_ (or more precisely, the range of x's for which the purported functional equation is to hold). For example, there may be many more functions with a complex domain which match the given requirements, but fewer on the real line. And a restriction on the domain of f will mean the functional equation holds for fewer x (giving fewer restrictions on f). Finally, you need to decide _what you want to assume about continuity_ (and/or differentiability). Assume nothing and you'll get nowhere. Assume too much and you may find no nontrivial solutions f. (That is, you must be careful not to "throw out the baby with the dishwater" as my grandmother used to say.) Let me clarify this last point. Given any value of x such that both x and h(x) are (defined and) in the domain of f, the assumed functional equation will give some information relating f(x) and f(h(x)). So let us declare x and h(x) to be _equivalent_, and let " ~ " denote the equivalence relation this generates on the real number line (or whatever the domain of f is assumed to be). One can check that this means x1 ~ x2 iff there exist m,n >= 0 s.t. h^n(x1) = h^m(x2). Now the crucial observation is this: the given functional equation will _only_ give some information about the relationships between the values of f(x) among points x in a single equivalence class. This is a telling statement in situations like the proposer's problem: since h is at worst a two-to-one map, it is easily verified that the equivalence class of x is at most countable, and thus there are uncountably many equivalence classes. In most cases we have more than one solutions for the behaviour of f on each equivalence class, so we obtain uncountably many possible solutions f in toto! Therefore in order to make some progress we try to assume f is, say, continuous at x=1. I believe in that case, however, the number of such functions drops to 1: f must be identically zero. Let us see what information we do glean about the behaviour of f on each equivalence class C. Note that C is actually a directed graph, with an edge from x to y iff h(x) = y. If the (corresponding undirected) graph is a _tree_, then we can pretty easily determine the values of f on all of C. Pick a point x0 to be the root of this tree; define f(x0) to be any value you wish. Then the functional equation forces f(h(x0)) = G(x, f(x0)) to be a certain value; similarly, the value of f(h^n(x0)) is forced for any n. For any other point x in C there exist unique minimal n and m such that h^m(x) = h^n(x0); if for example m=1 we may then deduce the value of f(x) from the equation f(h(x)) = G(x, f(x)), which we solve as a single equation in the single unknown "f(x)". Proceeding by induction we may compute f(x) for those values of x corresponding to higher values of m. (Here we're using the fact that G(x, y) is linear in y for the proposer's problem, so that a unique solution for f(x) exists. In more general settings of course the equations to be solved do not have a unique solution for f(x), so we will find more than one possibility for the function f: C -> R. Or there may be occasions in which f(h(x)) = G(x, f(x)) admits no solution for f(x); in these cases we would need to backtrack and see if a different choice for f(h(x)) would enable a solution.) More interesting is the case in which C contains some cycles. One can check that this can only happen if C contains a point x for which h^n(x) = x for some n. When this occurs we usually have an equation which limits the possible values of f(x). For example, if x is a fixed point of h then we must have f(x) = G(x, f(x)). Of course, once the values of f on the points within cycles have been determined, the values of f on the rest of C are determined as in the previous paragraphs. So we see that the cycles under h play a special role. I will look for some of them in the poster's specific problem. I suppose I should reiterate that the domain of f is assumed to include all these points, otherwise the functional equation does not give any further information (that is, the graph C loses this cycle). As I remarked at the beginning I'm not sure a mistake in notation hasn't been made, but I'll take it as is. Rather than write > 1 1 >f ( ----------- ) = j f( --- ) > 2(1+j)(1-j) 1-j I would prefer to let x=1/(1-j) so that this equation reads (*).....f(x^2/(4x-2)) = (x-1)/x f(x) that is, h(x) = x^2/(4x-2) and G(x,y) = ((x-1)/x) * y . Now, the fixed points of h are 0 and 2/3. What do we learn here? From (*) with x=0 we have f(0) = 0*f(0), and so f(0)=0. Note that h(0)=0 and h(x)=0 implies x=0: the equivalence class of 0 is just { 0 }. Taking the other fixed point x=2/3 gives f(2/3) = -1/2 * f(2/3), which requires f(2/3)=0, too. This time the graph C is more complicated; here is a portion of it: ...-> 29.347... -> 4+sqrt(12) -> 2 -> 2/3 (loops back) ...-> 0.508... -----^ ^ | ...-> 1.349... -> 4-sqrt(12) ---| ...-> 0.794... -----^ Well, since f(2/3)=0, we have 0= f(h(x))=(x-1)/x f(x) for both x=4 +- sqrt(12); so f vanishes there as well. Similarly, working back over the graph, we see f(x) = 0 for all x in C. And now we see more possibilities. The only cycle of length of 2 is the one containing 1 +- sqrt(1/5) = {x1, x2} , say. Then we have f(x1) = (x2-1)/x2 f(x2) and f(x2) = (x1-1)/x1 f(x1), so that f(x1) = (x2-1)/x2 * (x1-1)/x1 * f(x1)= (-1/4) f(x1); again f(x1)=f(x2)=0. There are two cycles of length 3; on these as well we have f(2.66)=f(.818)=f(.526)= f(4.27)=f(1.21)=f(.515)=0. I think one can show that f(x)=0 for all elements in _any_ finite orbit under h, although I have not carried this out. In this way, one obtains a large number of points at which f must vanish. Since for any x > 0.5 there are two points y with h(y)=x, both with y>0.5, we find that the number of points in the tree doubles with each lengthening to the left. So a picture of the behaviour of f begins to emerge. There seems to be a countable collection of families of graphs such that f(x)=0 for all x in the graphs; these graphs end in cycles ("on the right") but go arbitrarily far to the left, splitting in two at each stage. All the other values of x lie in equivalence classes which are trees -- roughly as above but with no terminal points. On each tree f(x) may be chosen arbitrarily at one point x0, and is then determined everywhere else. (Well, in the equivalence class of 1 we must take x0 to be "to the left of" 1.) Ah, but you object, what does f "look like"? The answer: it's a mess. As far as I can tell, the equivalence class containing 2/3, for example, is dense in the interval (1/2 , oo). Certainly the 1024 points obtained as (h^n)^(-1) (2/3) ( for 0 <= n <= 10) show no sign of leaving any gap, although there is no upper bound on the magnitude of the points in the equivalence class. If this hunch is correct, then we have some bad news: wherever f is continuous, it must be zero. (This follows since at each of the points in this equivalence class, f(x)=0.) In particular, it seems difficult to believe there can be a function f expressible as a power series near 1, as the poster suggested; this function must vanish at the points ..., .98987715, .99188524, .99592606, .99795886, 1.0020494, 1.0041074, 1.0082486, 1.0103320, ... as well, surely, as many points in between. Summary: Chase through the trees, use continuity if you think it's appropriate -- and make sure you've expressed the problem correctly. dave