Compositional square root

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Desiato
Posts: 43
Joined: Fri Nov 25, 2011 11:15 pm UTC

Compositional square root

Postby Desiato » Tue Jan 10, 2012 5:34 am UTC

So, in this post, the construction of a function e1/2 with e1/2(e1/2(x))=exp(x) is discussed.

I don't think the post refered to there is a solid valid proof of existance, so I tried to formalize the argument, but failed. That irks me especially because it reminded me of the more general problem that I spent a long time thinking about long ago:

M arbitrary set with infinite cardinality (1), f: M->M given. Is there g: M->M with g(g(x))=f(x) for all x in M?

(1) appears necessary, since for F_2, this is not true. There are only 4 functions F_2->F_2, and f with f(0)=1, f(1)=0 does not have a "compositional square root". The other three functions (0, 1, id) all are their own square roots, but f(f)=id!=f.

A few (more or less trivial) examples of functions where that "square root" exists, all considered R->R:

f = const: g=const
f=x: g=x
f = x^2: g=abs(x)^sqr(2)
f = -x: This is not as trivial as previous examples, but consider: [0,1) -> [1, 2) -> [0, -1) -> [-1, -2) -> [0, 1) and [2, 3) -> [3, 4) -> [-2, -3) -> [-3,-4) -> [2,3) etc

Well, and for the general case, choice seems sufficient - but how?

I have more thoughts on this, but I'm curious what others think from this minimal idea. Got counterexamples? Got an idea for or even a full proof?

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Compositional square root

Postby tomtom2357 » Tue Jan 10, 2012 8:50 am UTC

Okay, try this: Find the compositional square root of g:x->x+1 over the integers. I have a proof that there isn't one: f(f(x))=g(x), so f(f(1))=2. Let f(1)=x, therefore f(2)=x+1, since f(f(x))=x+1, and let fy(z)=f(fy-1(z)). f2x-2(1)=x=f1(1), f2x-3(x)=x, so f2x-2(x)=2, but f2x-2(y)=gx-1(y). So x+(x-1)=2, 2x-1=2, which is impossible for the integers. Try a larger set, the rational numbers maybe? If anyone finds an error in this proof, please tell me.

Edit: Actually, there is a simpler way to prove this, and it also proves the wider result that no matter what set you use, compositional square roots are undefined for some functions (unless of course the set has only one member). Consider the function f:N->N, f(1)=2 and f(n)=1 for n not equal to 1. g(g(x))=f(x). If g(2)=1, then g(1)=1 so that g(g(2))=g(1)=1, but then g(g(1))=1, which is contradictory. If g(2) is not equal to 1, then let g(2)=x. g(x)=1, g(g(x))=1 (remember that x is not equal to 1), g(g(x))=g(1)=1 so g(1)=1, which again implies that f(1)=1, which is false. Therefore g(x) is not defined. Sorry to burst your bubble :(
If you're talking about continuous functions, you need to say that in your post.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

mfb
Posts: 950
Joined: Thu Jan 08, 2009 7:48 pm UTC

Re: Compositional square root

Postby mfb » Tue Jan 10, 2012 3:06 pm UTC

I think I can give some cases where f has such a composition:
- f is a projection, so by definition f(f(x))=f(x) - trivial case
- f is an even permutation (of a finite set)
- f:R->R is bijective and [imath]a>b => f(a)>f(b)[/imath] (90% sure)

And f has no composition if:
- f is an uneven permutation (of a finite set) - that follows from the rules of permutation parity
- f(x)=x for all x except a finite subset M, [imath]f(M) \subset M[/imath], and there is no composition for f restricted to the subset.

Proof of the last one: Let [imath]m \in M[/imath]. [imath]g(m) \notin M[/imath] leads to [imath]g(g(m))=g(m) \notin M[/imath] (contradiction). Therefore, a composition of f would satisfy [imath]g(M) \subset M[/imath], which is a composition of M => contradiction.


I had a good idea for general finite sets, but I am not sure whether that works. I think there is a simple general rule, involving Im(f) and the intersection of all Im(f^n). f restricted to the latter one is a permutation...

Deedlit
Posts: 91
Joined: Sun Mar 08, 2009 2:55 am UTC

Re: Compositional square root

Postby Deedlit » Tue Jan 10, 2012 4:22 pm UTC

mfb, can you find a compositional square root of the permutation g = (1 2) (3 4 5 6)?

It seems to me that even cycles must come in pairs: if f(f(x)) transposes a and b, it must transpose f(a) and f(b) as well, and similarly for any even cycle. Also, for any x such that {x, f(f(x)), f(f(f(f(x))),...} are all distinct, and x is not in the image of f, there is a distinct set {y, f(f(y), f(f(f(f(y)))), ...} of all distinct elements such that y is not in the image of f (take either y = f(x) or x = f(y) ). Finally, for every double-sided series {..., x_{-2}, x_{-1}, x_0, x_1, x_2, ...} where x_{i+1} = f(f(x_i)), there is a double sided series {..., y_{-2}, y_{-1}, y_0, y_1, y_2, ...} where y_{i+1} = f(f(y_i)). (take y = f(x) ) I think that takes care of all cases when g(x) is an injective map. So when g(x) is an injection, the numbers of 2n-cycles, as well as the numbers of one-sided and double-sided paths, must all be even or infinite. Further, if every such number is even or infinite, then it is straightforward to construct an f(x) such that g(x) = f(f(x)); for each n, pair off the 2n-cycles, and for each pair construct a 4n-cycle such that f(f(x)) yields the desired pair of 2n-cycles. Similarly for one-sided and double-sided paths. Of course for odd cycles there is an i such that g2i(x) = g(x), so setting f(x) = gi(x) for that odd cycle will work. So we have a criterion for injective maps.

mfb
Posts: 950
Joined: Thu Jan 08, 2009 7:48 pm UTC

Re: Compositional square root

Postby mfb » Tue Jan 10, 2012 4:39 pm UTC

Oh crap, you are right. I noticed a similar problem while playing around with general functions, but I did not see that it applies to permutations as well.

For non-injective functions: If the function f:M->M can be split in an bijective composite part fN:N->N and a part which maps all other elements to elements in the injective part, let g(a)=gN-1(f(a)) where gN is defined on N.
The tricky functions contain stuff like "x is in the image of f, but not part of f(Im(x))". There, I am not sure how to handle it.

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Compositional square root

Postby tomtom2357 » Thu Jan 12, 2012 5:28 am UTC

Does anyone have a continuous function that does not have a compositional square root (over any set you want).
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

mfb
Posts: 950
Joined: Thu Jan 08, 2009 7:48 pm UTC

Re: Compositional square root

Postby mfb » Thu Jan 12, 2012 1:26 pm UTC

tomtom2357 wrote:(over any set you want)

See the integer example. Or the discrete space for any set.

For R->R with the standard topology, I don't know whether this exists or not. A related question: Can g be continuous, too?

Desiato
Posts: 43
Joined: Fri Nov 25, 2011 11:15 pm UTC

Re: Compositional square root

Postby Desiato » Sun Jan 15, 2012 12:27 am UTC

I think Deedlit's classification works for general (i.e. not necessarily injective) functions as well. There's just a few more cases to consider.

The basic idea is to consider the equivalence relation x~y :<=> There is n, m in N (including 0) such that f^n(x) = f^m(y)

Let S(x) be the equivalence class of x.

Then S(x) can be of several (in this listing, not mutually exclusive, since I kept in Deedlit's classification) types:

1. An even cycle
2. An odd cycle
3. {x, f(x), f^2(x), ...} infinite with f^-1(x) empty
4. {...y-n,...y-1, y, y1,...} with yi=f(yi-1)
5. There is x with S(x) = Union over all successive preimages of x, and f(x) is in the nth (but not (n-1)st) successive preimage of x (where we define the 0th preimage as the case f(x) = x)
6. For any x in S(x), no n in N exists so that f^n(x) is preimage of x.

Now what we need to consider is the same "pairing off", and in what ways the various types of 5 and 6 can be paired. The "breadth"of the structure of those trees seems irrelevant, as by definition, we can set the value of g identical for each preimage of a value, and if g exists, then we know that for any x on a given preimage level except 0 and 1, g(x) can't be on the same preimage level. Then what matters are the depths (including infinite).

Now, there actually seem to be a lot more combinations we can consider. For instance, any set of type 5 with depth = n (i.e. f(x) is in the lowest preimage level) finite >0, we could pair off with a cycle of equivalent length of type 1 or 2 (which strictly speaking are subtypes of 5). For the nontrivial (i.e. f^-1(x)!={x}) n=0 case, we need another set of same type and depth to pair off against - except depth 1.
For type 6 (of which 3 is a subtype), we can in turn pair off with sets of type 3 if preimage depth is finite. For infinite preimage depth, we need pairs of type 6 or 4.

Not sure if those combinations are exhausting already, but it's already safe to say that if there's an even or infinite number of each type (this is considering the various preimage depths for type 5, also the preimage level of x, as separate types), g exists: well-order the equivalence classes, for given S chose next match, build g by weaving the positive/negative preimage levels, starting at the critical point (i.e. peak of 5) where necessary.


Edit: I have a vague feeling that continuous functions R->R (with standard topology) will always have a compositional square root due to the intermediate value theorem. Specificially, it seems as if the following is true: If f is continuous and there exists an nonempty equivalence class of a specific type, then there exist infinitely many equivalence classes of that type. But I'm not remotely close to a real proof for that, that's just intuition for now (and maybe a starting point?).

Edit the third: Removed edit the second because I should not post that late at night.

mfb
Posts: 950
Joined: Thu Jan 08, 2009 7:48 pm UTC

Re: Compositional square root

Postby mfb » Sun Jan 15, 2012 2:28 pm UTC

Desiato wrote:Edit: I have a vague feeling that continuous functions R->R (with standard topology) will always have a compositional square root due to the intermediate value theorem. Specificially, it seems as if the following is true: If f is continuous and there exists an nonempty equivalence class of a specific type, then there exist infinitely many equivalence classes of that type. But I'm not remotely close to a real proof for that, that's just intuition for now (and maybe a starting point?).

I also think that this is true.

But I am bit unsure about your handling of type 5 and 6. How do you combine these two trees of type 5?

1->2->3->3
4->3

a->b->b
c->b

The first part is easy:
3->b->3
So 2->b, 4->b and c->3, a->3
And now? We need an element which is mapped to 2.

How do you combine arbitrary branch structures?

Desiato
Posts: 43
Joined: Fri Nov 25, 2011 11:15 pm UTC

Re: Compositional square root

Postby Desiato » Sun Jan 15, 2012 3:19 pm UTC

mfb wrote:How do you combine arbitrary branch structures?

That's what I tried to address here: "(this is considering the various preimage depths for type 5, also the preimage level of x, as separate types)". With that I mean how many successive preimages we can take before they're all empty. So, your examples would not be of the same type. The only thing that does not matter is the breadth of that tree - i.e. card(preimage^n(x)).

So for type 5, there's actually two additional parameters that create different types: The length of the final cycle - how many steps do we go back? And the depth before preimages become empty (if ever).

Nitrodon
Posts: 497
Joined: Wed Dec 19, 2007 5:11 pm UTC

Re: Compositional square root

Postby Nitrodon » Sun Jan 15, 2012 4:33 pm UTC

The function defined by f(x) = (x-1)2 is continuous from R to itself, but it has exactly one 2-cycle. Thus, it has no compositional square root.

Desiato
Posts: 43
Joined: Fri Nov 25, 2011 11:15 pm UTC

Re: Compositional square root

Postby Desiato » Sun Jan 15, 2012 6:42 pm UTC

Nitrodon wrote:The function defined by f(x) = (x-1)2 is continuous from R to itself, but it has exactly one 2-cycle. Thus, it has no compositional square root.

Interesting! Seems possibly related to f having two fixed points

This certainly shows my "vague feeling" wrong, and moreso, it shows that continuity (and differentiability and other stronger typical analytical concepts) is not really a relevant term for this, when even such simple things as polynomials fail.

Deedlit
Posts: 91
Joined: Sun Mar 08, 2009 2:55 am UTC

Re: Compositional square root

Postby Deedlit » Sun Jan 15, 2012 7:01 pm UTC

Desiato wrote:That's what I tried to address here: "(this is considering the various preimage depths for type 5, also the preimage level of x, as separate types)". With that I mean how many successive preimages we can take before they're all empty. So, your examples would not be of the same type. The only thing that does not matter is the breadth of that tree - i.e. card(preimage^n(x)).

So for type 5, there's actually two additional parameters that create different types: The length of the final cycle - how many steps do we go back? And the depth before preimages become empty (if ever).


I think the situation is more complicated than what you're describing. For example, take a path of length n, leading up to an x such that f(x) = x. This does not have to be paired up with an equivalent structure; it can be mapped up with a path of length n-1, n, or n+1. Take for example:

1 -> 2 -> 3 -> 3
4 -> 5 -> 5

we can take the compositional square root by taking 1 -> 4 -> 2 -> 5 -> 3 -> 5.

Note that while we can pair a path of length n with a path of length n+1, and a path of length n+1 with a path of length n+2, we cannot pair a a path of length n+2 with a path of length n. So we cannot just count up structures to see if the number is even or infinite.

I also disagree that we can ignore the width of branchings. For example, a path of length n leading up to an m-cycle cannot be paired off with a double path of length n leading up to an m-cycle. So the tree structure of the preimages is important, and it is not clear when two tree structures can be paired off or not.

Also, some structures need not be paired off, for example a two paths of length n leading to an x with f(x) = x. But such structures cannot be ignored, because for instance the previous structure can be paired off with two paths of length n-1 and n+1 leading up to a y with f(y) = y.

We don't have to worry about uncountable length chains, since they always decompose into countable length chains. We do have to worry about uncountable branchings of preimages - I'm not sure if an uncountable branching is always equivalent to a countably infinite branching, since there are uncountably many possibly tree structures.

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Compositional square root

Postby tomtom2357 » Mon Jan 16, 2012 9:54 am UTC

Can we have a necessary and sufficient condition for something to have a compositional square root? Lets start with the simplest of functions, the linear functions. They always have a compositional square root, if you try hard enough you'll find it. Now on to quadratics: a sufficient condition for not having a compositional square root is having exactly one 2-cycle. I can prove that having an odd number of 1 or 2-cycles ensures the impossibility of having a compositional square root, so that is a good generalization. An easy compositional square root of x2 is xsqrt(2), and other quadratics can have a compositional square root. Another interesting idea is that if square roots come in pairs, then maybe compositional square roots come in pairs too. Let f(x) be our original function, and let g(x) and h(x) be a pair of compositional square roots of f(x), and let i(x)=g(h(x)), what would i(x) look like? Knowing one of the square roots of a function, how do you calculate its pair?
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

mfb
Posts: 950
Joined: Thu Jan 08, 2009 7:48 pm UTC

Re: Compositional square root

Postby mfb » Mon Jan 16, 2012 10:59 am UTC

tomtom2357 wrote:An easy compositional square root of x2 is xsqrt(2)

Be careful with this expression for negative numbers. |x|sqrt(2) is better here.

But at least we have more for the case of "f:R->R is bijective and [imath]a>b => f(a)>f(b)[/imath]" now.
For this function, every x is in a two-sided chain and the function is injective, therefore we can pair the chains (using AoC - or maybe even without?) to get a composition. I think that it is even possible to get another function of the same type as composition of f.


@Deedlit: Thanks for the examples of problems in the tree structures.
The general case is still a problem, and we don't have a good classification yet. We only have some sufficient (pairs of same tree structures) and some necessary (everything related to injective functions) conditions.

Desiato
Posts: 43
Joined: Fri Nov 25, 2011 11:15 pm UTC

Re: Compositional square root

Postby Desiato » Mon Jan 16, 2012 12:37 pm UTC

Deedlit: Dang, of course you're right. I was just considering preimage of a single element, but not noticing that as soon as we have more than one "branch", collapsing isn't trivial. Now I'm thinking that there won't be a simpler condition for the general case than some sort of "tree equivalence" criteria and then pairing those off. As your examples show, defining exactly which types of trees are "pairable" doesn't look like it will have a very elegant solution - but I want to think about that some more.

Tomtom: When you say linear functions, you mean R->R only, right? Otherwise, it really depends on what kind of linear function you mean, and it doesn't appear straightforward to me to show this for a general linear function between vector spaces.

Also: "1-cycles" are fixpoints, and thus an odd number of those is not an issue.

mfb wrote:But at least we have more for the case of "f:R->R is bijective and [imath]a>b => f(a)>f(b)[/imath]" now.
For this function, every x is in a two-sided chain and the function is injective, therefore we can pair the chains (using AoC - or maybe even without?) to get a composition. I think that it is even possible to get another function of the same type as composition of f.

Given my error above, I'm a bit more careful here as well; at very least the argument is not correct: every x is in a two-sided chain or a fixpoint. So the conclusion is not quite as trivial. I still think the result is correct, though: bijective monotonic functions R->R are necessarily continuous as well, and so it seems if we have the case that the R\{fixpoints} countable and considering that then {fixpoints} must be dense, it follows that f(x)=x. But: can we generalize this result to more general totally ordered spaces? It appears that the argument works the same for uncountable totally ordered sets?

mfb
Posts: 950
Joined: Thu Jan 08, 2009 7:48 pm UTC

Re: Compositional square root

Postby mfb » Mon Jan 16, 2012 1:59 pm UTC

"or a fixed point", right.

>> It appears that the argument works the same for uncountable totally ordered sets?
As long as there is a bijection from this set M to R which preserves the ordering: Of course. Map your function f': M->M to a function f:R->R, find g, map it back to g':M->M.

Oh, and I can add another category: f:R->R bijective with f(x)>x for all x or f(x)<x for all x. Injective should be sufficient, and I think it is required for the general statement.

Desiato
Posts: 43
Joined: Fri Nov 25, 2011 11:15 pm UTC

Re: Compositional square root

Postby Desiato » Mon Jan 16, 2012 9:36 pm UTC

tomtom2357 wrote: Another interesting idea is that if square roots come in pairs, then maybe compositional square roots come in pairs too. Let f(x) be our original function, and let g(x) and h(x) be a pair of compositional square roots of f(x), and let i(x)=g(h(x)), what would i(x) look like? Knowing one of the square roots of a function, how do you calculate its pair?


There's generally many more than "a pair". Consider f(x) = 0. Define ga(x):=a for x !=a and ga(a):= 0 - then ga(ga)=0 for any a!=0.
The same example shows us we know little about the composition of two different compositional square roots. In the above example, b!=a, then ga(gb)(x) is a for all x.

mfb wrote:>> It appears that the argument works the same for uncountable totally ordered sets?
As long as there is a bijection from this set M to R which preserves the ordering: Of course. Map your function f': M->M to a function f:R->R, find g, map it back to g':M->M.

Right, for sets order-isomorphic to R, that obviously works. I was thinking about the general case. For instance, the density argument works for any uncountable Hausdorff-space, and since totally ordered sets are Hausdorff with order topology, that argument works for any totally ordered set. However, the step "countable complement" => dense is at least worth a proof... and the question not immediately clear to me is whether "monotoneuous bijective => continuous" works for any totally ordered set. I think this is not necessarily true. However, if we add the requirement for f to be continuous, then the same argument should hold.

mfb wrote:Oh, and I can add another category: f:R->R bijective with f(x)>x for all x or f(x)<x for all x. Injective should be sufficient, and I think it is required for the general statement.

I don't think injective is sufficient; without surjectivity, you potentially get chains of the type {x, f(x), ...} as well, and it's at least not clear how it follows that there's infinitely many of each type in this setup.


Deedlit wrote:We do have to worry about uncountable branchings of preimages - I'm not sure if an uncountable branching is always equivalent to a countably infinite branching, since there are uncountably many possibly tree structures.

I think we do need to at least think about cardinalities here in general.

Consider f:R->R defined as following: x in unique decimal representation. If x is integer !=0, map it to 1. If x is not integer, cut off anything before the decimal point, then replace all occurances of the highest occuring digit with the next lower digit. If this would map an irrational x to a rational one, map it to an arbitrary irrational with the "available digits" instead (we can chose a fixed one for each type of "max digit" - we do this just so the rationals and irrationals don't "connect"). Lastly, map any rational only containing digits 1 and 0 behind the decimal point to 1.

This function, unless I missed some case, should have two equivalence classes, one ending at 0, one ending at 1, and the one ending at 0 will have uncountable preimages on each level. We cannot pair these two (even if we leave other "fixable" issues aside) in the "typical" way of jumping from same preimage depth to the same for the other set and then back - if we could, we'd need g to map a countable set surjectively into an uncountable set, and that's obviously not possible.

But that says nothing about what "skipping" we can do within the tree with uncountable width, of course, and much less about what's possible there in the general case. I think we could find a decomposition for the uncountable set: since every point has infinite preimages (or none), we can start pairing those from top down such that preimage(x) -> preimage(y) -> x -> y -> 0 etc. We don't get into issues at the top level since we can let g map to zero, and we always have infinite selection of further preimages for every point. So on the level below, with a in preimage(x) and b in preimage(y), we can map preimage(a)->preimage(b)->a->b->x->y->0, and so on. In fact, this should also work for any tree where all preimages have equal even or infinite cardinality, but that's something I need to think through more as well.

But: If we modify f so that instead of ending at a fixed point 0, we end in a loop (e.g. by mapping 0->1->0 and moving the end point for the rational part to 2), then that method doesn't work, and I think by standard argument, we already know we can't map that tree to itself. So that should then be an example where the cardinalities matter. I think.

Desiato
Posts: 43
Joined: Fri Nov 25, 2011 11:15 pm UTC

Re: Compositional square root

Postby Desiato » Thu Mar 15, 2012 7:11 am UTC

For anyone still interested in this topic I've posted a followup discussion of this on stackexchange, here.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 16 guests