-- g o g = f

2 views
Skip to first unread message

quasi

unread,
Jan 27, 2009, 9:03:16 PM1/27/09
to
In another thread, I asked a number of questions concerning the
functional equation

g o g = f

but I think perhaps they need a separate thread.

For now, I'll allow arbitrary functions from R to R.

Given f : R -> R, let S(f) = {g : R -> R | g o g = f}.

I'll start with just one question:

What are the possible cardinalities for S(f)?

quasi

Chip Eastham

unread,
Jan 27, 2009, 9:50:45 PM1/27/09
to

You're not going to require continuity?

Then the cardinality S(f) would be 2^R
for f(x) = x, the identity. That is,
take any subset of R equinumerous with
its complement, and consider all the
possible g which map the subset 1-to-1
with its complement. Then suitably
extended to R in the obvious way,

g o g = f.

regards, chip

quasi

unread,
Jan 27, 2009, 10:16:47 PM1/27/09
to
On Tue, 27 Jan 2009 18:50:45 -0800 (PST), Chip Eastham
<hard...@gmail.com> wrote:
>
>On Jan 27, 9:03 pm, quasi <qu...@null.set> wrote:
>>
>> In another thread, I asked a number of questions concerning the
>> functional equation
>>
>>    g o g = f
>>
>> but I think perhaps they need a separate thread.
>>
>> For now, I'll allow arbitrary functions from R to R.
>>
>> Given f : R -> R, let S(f) = {g : R -> R | g o g = f}.
>>
>> I'll start with just one question:
>>
>> What are the possible cardinalities for S(f)?
>
>You're not going to require continuity?

Not yet. I first want to understand the possibilities for the case of
arbitrary functions. Of course, with no restrictions, the analysis
will tend to have more of a set theory feel, as illustrated by your
solution below for the function f(x) = x.

>Then the cardinality S(f) would be 2^R
>for f(x) = x, the identity. That is,
>take any subset of R equinumerous with
>its complement, and consider all the
>possible g which map the subset 1-to-1
>with its complement. Then suitably
>extended to R in the obvious way,

Cool.

Can a similar argument be applied to other functions f? If so, which
ones?

As a simple sub-question of the original question, does there exist a
function f such that S(f) is empty?

quasi

Robert Israel

unread,
Jan 27, 2009, 11:58:43 PM1/27/09
to
quasi <qu...@null.set> writes:

Suppose there is exactly one 2-cycle for f, i.e. exactly one pair of distinct
points p,q such that f(p) = q and f(q) = p. Then it's easy to prove there
is no such g. An example is f(x) = -x^3.
--
Robert Israel isr...@math.MyUniversitysInitials.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada

galathaea

unread,
Jan 28, 2009, 2:25:43 AM1/28/09
to
On Jan 27, 8:58 pm, Robert Israel

i'm sorry i am probably being dense
but what does this proof use?

all i can see is

p
g(x) = a x

then
2
1+p p
f(x) = a x

so if f(x) = -x^3

2
p = 3

1+p
a = -1

so

ln(a) = (2n + 1) pi i / (1 + sqrt(3))

a = exp((2n + 1) pi i / (1 + sqrt(3)))

this seems like it may work here

have i chosen a bad branch?

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
galathaea: prankster, fablist, magician, liar

galathaea

unread,
Jan 28, 2009, 2:28:31 AM1/28/09
to

i probably fail for being outside R -> R right?

is that the real constraint here?

quasi

unread,
Jan 28, 2009, 2:50:16 AM1/28/09
to

Beats me.

I'm sure it's something simple, but I don't see it.

>all i can see is
>
> p
>g(x) = a x

Where do you get that?

Why does g have to be a polynomial?

>then
> 2
> 1+p p
>f(x) = a x
>
>so if f(x) = -x^3
>
> 2
> p = 3
>
> 1+p
> a = -1
>
>so
>
>ln(a) = (2n + 1) pi i / (1 + sqrt(3))
>
>a = exp((2n + 1) pi i / (1 + sqrt(3)))
>
>this seems like it may work here
>
>have i chosen a bad branch?

Well, the functions f,g were specified as being from R to R.

quasi

quasi

unread,
Jan 28, 2009, 2:51:06 AM1/28/09
to

Yes.

quasi

quasi

unread,
Jan 28, 2009, 3:02:13 AM1/28/09
to
On Tue, 27 Jan 2009 22:58:43 -0600, Robert Israel
<isr...@math.MyUniversitysInitials.ca> wrote:

>quasi <qu...@null.set> writes:
>
>> On Tue, 27 Jan 2009 18:50:45 -0800 (PST), Chip Eastham
>> <hard...@gmail.com> wrote:
>> >
>> >On Jan 27, 9:03 pm, quasi <qu...@null.set> wrote:
>> >>
>> >> In another thread, I asked a number of questions concerning the
>> >> functional equation
>> >>

>> >>    g o g = f

I don't see it.

>An example is f(x) = -x^3.

I see that -x^3 has exactly one 2-cycle. Other than that, I'm lost.

It's probably just a simple trick that I'm missing.

quasi

Mariano Suárez-Alvarez

unread,
Jan 28, 2009, 3:11:30 AM1/28/09
to

Suppose {x, f(x)} is the only is the only 2-cycle for f
(so in particular x != f(x)) and suppose f = g^2 (where
the exponent means composition) Then f^2(g(x)) = g(x),
so that {g(x), f(g(x))} is a 2-cycle. The hypothesis, then,
implies that either x = g(x) or x = f(g(x)). You should
be able to reach a contradiction in both cases.

-- m

for f.

quasi

unread,
Jan 28, 2009, 4:30:11 AM1/28/09
to
On Wed, 28 Jan 2009 00:11:30 -0800 (PST), Mariano Suárez-Alvarez
<mariano.su...@gmail.com> wrote:

>On Jan 28, 6:02 am, quasi <qu...@null.set> wrote:
>> On Tue, 27 Jan 2009 22:58:43 -0600, Robert Israel
>>
>>
>>
>> <isr...@math.MyUniversitysInitials.ca> wrote:
>> >quasi <qu...@null.set> writes:
>>
>> >> On Tue, 27 Jan 2009 18:50:45 -0800 (PST), Chip Eastham
>> >> <hardm...@gmail.com> wrote:
>>
>> >> >On Jan 27, 9:03 pm, quasi <qu...@null.set> wrote:
>>
>> >> >> In another thread, I asked a number of questions concerning the
>> >> >> functional equation
>>

>Suppose {x, f(x)} is the only 2-cycle for f


>(so in particular x != f(x)) and suppose f = g^2 (where
>the exponent means composition) Then f^2(g(x)) = g(x),
>so that {g(x), f(g(x))} is a 2-cycle. The hypothesis, then,
>implies that either x = g(x) or x = f(g(x)). You should
>be able to reach a contradiction in both cases.

Got it.

For the first case:

x = g(x)
=> g(x) = g^2(x)
=> x = f(x)
contradiction.

For the second case:

x = f(g(x))
=> f(x) = f^2(g(x))
=> f(x) = g(x)
=> g(f(x)) = g^2(x)
=> g(f(x)) = f(x)
=> g^2(f(x)) = g(f(x))
=> f(f(x)) = f(x)
=> x = f(x)
contradiction

Thanks.

quasi

quasi

unread,
Jan 28, 2009, 4:49:17 AM1/28/09
to

Current status:

S(f) has cardinality 2^|R| if f(x) = x [Chip Eastham]

S(f) is empty if f(x) = -x^3 (or any function with exactly one
2-cycle) [Robert Israel, with amplification by Mariano
Suárez-Alvarez].

Some questions ...

Are there functions f other than the identity such that S(f) has
cardinality 2^|R|?

Are there functions f other than those with exactly one 2-cycle such
that S(f) is empty?

Can S(f) have cardinality 1? If so, is every finite cardinality
achievable?

Can S(f) be countably infinite?

Can S(f) have cardinality |R|?

quasi

Gottfried Helms

unread,
Jan 28, 2009, 5:58:39 AM1/28/09
to
Am 28.01.2009 10:49 schrieb quasi:
>
> Are there functions f other than those with exactly one 2-cycle such
> that S(f) is empty?

I guess, a candidate is also the function f(x) = 1/(1+x) from
the other thread. Here, the function is not exactly oscillating
but converging. But it is oscillating in the sense, that
f°h(x) and f°(h+1)(x) are on opposite sides of the limit-case
f°inf(x) (on the real line)

If we assume, that fractional iterates between f°h(x) and f°(h+1)(x)
have real values only (and the set of continuous iterates is
again continuous) then one of that fractional iterates must equal
the limit case, and -may be- that's another case of contradiction.

Gottfried Helms

David Bernier

unread,
Jan 28, 2009, 6:17:52 AM1/28/09
to

Is it completely obvious that f^2(g(x)) = g(x) ?
For x |-> -x^3, there's the fixed point 0,
the 2-cycle (-1, 1), and for a in R, say a>0 and a=/= 1,
we have a -> (-a)^3 -> a^6 -> ... which we can continue
to the left to get a non-cyclic orbit similar
to S: Z -> Z , S(k) = k+1 with a non-cyclic orbit
... -3 |-> -2 |-> -1 |-> 0 |-> 1 .... (***)

So we have the fixed point 0, the 2-cycle (-1, 1), and
infinitely many orbits like (***) for x |-> -x^3 (f).

I was under the impression that one had to think a bit
about these other orbits or cycles, and I don't see how
3-cycles, 4-cycles or any combination for the permutation
of R given by x |-> g(x) could give the orbit structure
required for f = g o g . I ask about this because maybe
there's a completely obvious way to get f^2(g(x)) = g(x)
that I'm not seeing.

David Bernier

quasi

unread,
Jan 28, 2009, 6:36:24 AM1/28/09
to
On Wed, 28 Jan 2009 11:58:39 +0100, Gottfried Helms
<he...@uni-kassel.de> wrote:

>Am 28.01.2009 10:49 schrieb quasi:
>>
>> Are there functions f other than those with exactly one 2-cycle such
>> that S(f) is empty?
>
> I guess, a candidate is also the function f(x) = 1/(1+x) from
> the other thread.

However it was specified that f must be a function from R to R, so
although f is not required to be continuous, the domain of f must be
all of R.

> Here, the function is not exactly oscillating
>but converging. But it is oscillating in the sense, that
>f°h(x) and f°(h+1)(x) are on opposite sides of the limit-case
>f°inf(x) (on the real line)
>
>If we assume, that fractional iterates between f°h(x) and f°(h+1)(x)
>have real values only (and the set of continuous iterates is
>again continuous) then one of that fractional iterates must equal
>the limit case, and -may be- that's another case of contradiction.

quasi

quasi

unread,
Jan 28, 2009, 6:53:44 AM1/28/09
to

It's easy:

f = g^2 implies f,g commute under composition, hence

f^2(g(x)) = g(f^2(x)) = g(f(f(x)) = g(x), since f(f(x)) = x.

quasi

Denis Feldmann

unread,
Jan 28, 2009, 7:12:08 AM1/28/09
to
quasi a écrit :

If g(p) =a, we have g(a)=q, g(q)=g(g(a))=f(a)=b and g(f(a))=f(g(a))=p,
so f(b)=g(p)=a, so (a,b) is another 2-cycle ; now a must be p or q. If
g(p)=p, we have f(p)=p absurd ; if g(p)=q, we have q=g(q) absurd too...

David C. Ullrich

unread,
Jan 28, 2009, 7:25:21 AM1/28/09
to

I don't quite see it either, but if we add the assumption
that f is 1-1 then it's nothing but simple set theory.
Forget the calculations you do below for the specific
example f = -x^3; there is _no_ function g from C to C
with f = g o g.

In general, we're going to write f^n for the composition
of f with itself n times. (And f^0(x) = x).

If f : X -> X and x is in X then order(x, f) is the smallest
positive integer n such that f^n(x) = x (order(x, f) = infinity if
there is no such n).

Lemma. If f is 1-1 and order(x, f) = n then the n
points x, f(x), ... , f^(n-1)(x) are distinct.

Proof. If not, say f^j(x) = f^k(x), 0 <= j < k < n.
Since f is 1-1 this implies that f^(k-j)(x) = x;
since 0 < k-j < n this contradicts the fact that
the order of x is n. QED.

Suppose that f : X -> X is 1-1 and there is exactly one
pair p, q of distinct points such that f(p) = q and f(q) = p.
This means there are exactly two x with order(x,f) = 2,
namely p and q. Suppose as well that f = g o g = g^2.

Note that g must also be 1-1.

Now g^4(p) = f^2(p) = p, so order(p, g) must be
1, 2, or 4. But if g(p) = p or g^2(p) = p then
f(p) = p, which is not so. So order(p, g) = 4.

So by the lemma the four points

p, g(p), g^2(p), g^3(p)

are distinct. But it's easy to see that each of these
points has order 2 under f, contradicting the
assumption that there are only two points
of order 2 under f. QED.

(Ok, details for why order(g(p), f) = 2:
It's clear that f^2(g(p)) = g(p). So
order(g(p), f) must be 1 or 2. But
f(g(p)) <> g(p) because g^3(p) <> g(p).
So order(g(p), f) = 2.)

>all i can see is
>
> p
>g(x) = a x
>
>then
> 2
> 1+p p
>f(x) = a x
>
>so if f(x) = -x^3
>
> 2
> p = 3
>
> 1+p
> a = -1
>
>so
>
>ln(a) = (2n + 1) pi i / (1 + sqrt(3))
>
>a = exp((2n + 1) pi i / (1 + sqrt(3)))
>
>this seems like it may work here
>
>have i chosen a bad branch?
>
>-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
>galathaea: prankster, fablist, magician, liar

David C. Ullrich

"Understanding Godel isn't about following his formal proof.
That would make a mockery of everything Godel was up to."
(John Jones, "My talk about Godel to the post-grads."
in sci.logic.)

David Hartley

unread,
Jan 28, 2009, 7:52:53 AM1/28/09
to
In message <gp90o457okn9infh6...@4ax.com>, quasi
<qu...@null.set> writes

>On Tue, 27 Jan 2009 21:03:16 -0500, quasi <qu...@null.set> wrote:
>
>>In another thread, I asked a number of questions concerning the
>>functional equation
>>
>> g o g = f
>>
>>but I think perhaps they need a separate thread.
>>
>>For now, I'll allow arbitrary functions from R to R.
>>
>>Given f : R -> R, let S(f) = {g : R -> R | g o g = f}.
>>
>>I'll start with just one question:
>>
>>What are the possible cardinalities for S(f)?
>
>Current status:
>
>S(f) has cardinality 2^|R| if f(x) = x [Chip Eastham]
>
>S(f) is empty if f(x) = -x^3 (or any function with exactly one
>2-cycle) [Robert Israel, with amplification by Mariano
>Suárez-Alvarez].
>
>Some questions ...
>
>Are there functions f other than the identity such that S(f) has
>cardinality 2^|R|?

f(x) = x^2

If there is one g which is odd ( g(-x) = -g(x)) then there are 2^c
others. Change g to -g on any subset of R. Same if g is even.

>
>Are there functions f other than those with exactly one 2-cycle such
>that S(f) is empty?
>
>Can S(f) have cardinality 1? If so, is every finite cardinality
>achievable?
>
>Can S(f) be countably infinite?
>
>Can S(f) have cardinality |R|?

It can be helpful to look directly at g. If we suppose g is a bijection,
then it splits into finite cycles and infinite chains.

If it has a chain <c_n : n in Z> such that each g(c_n) = c_(n+1) then
change g on just the chain to

g(c_2n) = c_(2n+k), g(c_(2n+1)) = c_(2n+1-(k-2))

for any odd k. The new g has the same g o g.


If g has two finite cycles of the same length we can redefine g so that
it has one double length cycle whose square is the same as that of the
original - e.g. change the permutation (1 2 3)(4 5 6) to (1 4 2 5 3 6).

If g has any fixed points, they can be paired together and swapped to
give a new g with the same g o g,

At least one of the sets of fixed points, finite cycles of a given
length, and Z-chains must have cardinality c. So if there's one g,
there's 2^c.

I haven't considered when g is not a bijection.
--
David Hartley

Mariano Suárez-Alvarez

unread,
Jan 28, 2009, 12:20:26 PM1/28/09
to
On Jan 28, 10:52 am, David Hartley <m...@privacy.net> wrote:
> In message <gp90o457okn9infh6ba6posm35ii4q7...@4ax.com>, quasi

Suppose there is *one* element x in R such that
the orbit O = {g^n(x) : n in Z} is infinite. Write
x_n = g^n(x).

Let {A, B} be a partition of Z such that both parts
are infinite and let phi : A -> B be a bijection.

Define g' : R --> R such that it coincides with g
outside of O, and such that g'(x_a) = g^(x_{phi(a)})
for all a in A, and g'(x_b) = x_{phi^{-1}(b) + 1}.
Then g' is another compositional square root for f.

Since there are uncountably many triples (A, B, phi),
the existence of one infinite orbit for g (or for f)
implies the existence of uncountably many g's.

-- m

Robert Israel

unread,
Jan 28, 2009, 1:40:33 PM1/28/09
to
On Jan 27, 11:25 pm, galathaea <galath...@gmail.com> wrote:
> On Jan 27, 8:58 pm,Robert Israel

It's very simple. If g o g = f, then g o f = f o g. So
g(p) = g(f(q)) = f(g(q)) and similarly g(q) = f(g(p)).
That is, g(q) and g(p) (if distinct) form a 2-cycle for f.
Since f has only one 2-cycle, there are only the following cases to
consider:
1) g(q) = g(p). But then
p = f(q) = g(g(q)) = g(g(p)) = f(p) = q, contradicting the assumption
that p and q are distinct.
2) g(q) = q and g(p) = p. But then f(p) = g(g(p)) = g(p) = p,
contradiction.
3) g(q) = p and g(p) = q. But then again f(p) = g(g(p)) = g(q) = p,
contradiction.

hagman

unread,
Jan 28, 2009, 3:52:37 PM1/28/09
to
On 28 Jan., 10:49, quasi <qu...@null.set> wrote:
> On Tue, 27 Jan 2009 21:03:16 -0500, quasi <qu...@null.set> wrote:
> >In another thread, I asked a number of questions concerning the
> >functional equation
>
> >   g o g = f
>
> >but I think perhaps they need a separate thread.
>
> >For now, I'll allow arbitrary functions from R to R.
>
> >Given f : R -> R, let S(f) = {g : R -> R | g o g = f}.
>
> >I'll start with just one question:
>
> >What are the possible cardinalities for S(f)?
>
> Current status:
>
> S(f) has cardinality 2^|R| if f(x) = x [Chip Eastham]
>
> S(f) is empty if f(x) = -x^3 (or any function with exactly one
> 2-cycle) [Robert Israel, with amplification by Mariano
> Suárez-Alvarez].
>
> Some questions ...
>
> Are there functions f other than the identity such that S(f) has
> cardinality 2^|R|?

It is of course sufficient that f restricted to some interval is the
identity
(provided f=gog is solvable at all)

>
> Are there functions f other than those with exactly one 2-cycle such
> that S(f) is empty?

Let n be odd.
If f is the identity except ant 2n points and permutes these 2n points
as n cycles, then S(f) is empty:
If g maps a permuted point x to a permuted point y, then y is neither
x
nor the partner of x. It follows that g permutes x |-> y |-> x' |-> y'
|-> x
where (x x') and (y y') are two distinct 2-cycles.
At least one 2-cycle (u v) is not of this kind, i.e. g(u) is a fixed
point of f.
Then g(u) = f(g(u)) = g(f(u)) = g(v), hence
v = f(u) = g(g(u)) = g(g(v)) = f(v) = u -- contradiction

>
> Can S(f) have cardinality 1? If so, is every finite cardinality
> achievable?

Let g:R->R be arbitrary. We find h:R->R such that g o g = h o h:
Consider a maximal orbit under g, i.e. either a map
k:Z->R such that g(k(n)) = k(n+1)
or a map
k:N->R such that g(k(n)) = k(n+1) and k(0) is not in g(R).
Let h=g outside that orbit.
On the orbit g o g looks like the "add 2" function on Z or N.
It is easy to find a function that does not look like "add 1"
but its iteration is "add 2", for example
n |-> ((n XOR 1) +1)XOR 1

It follows that #S(f) never equals 1.

quasi

unread,
Jan 28, 2009, 4:15:58 PM1/28/09
to
On Wed, 28 Jan 2009 12:52:53 +0000, David Hartley <m...@privacy.net>
wrote:

Nice analysis.

>I haven't considered when g is not a bijection.

Of course, g is a bijection iff f is, so the case where f is bijective
is resolved. To summarize:

If f is bijective, S(f) is either empty or has cardinality 2^c.

quasi

quasi

unread,
Jan 28, 2009, 4:20:07 PM1/28/09
to

Nice.

Does your argument assume f is bijective? If so, does it how does it
break down if f is not bijective?

quasi

quasi

unread,
Jan 28, 2009, 4:24:51 PM1/28/09
to

>v = f(u) = g(g(u)) = g(g(v)) = f(v) = u -- contradiction.

Very nice.

>> Can S(f) have cardinality 1? If so, is every finite cardinality
>> achievable?
>
>Let g:R->R be arbitrary. We find h:R->R such that g o g = h o h:
>Consider a maximal orbit under g, i.e. either a map
>k:Z->R such that g(k(n)) = k(n+1)
>or a map
>k:N->R such that g(k(n)) = k(n+1) and k(0) is not in g(R).
>Let h=g outside that orbit.
>On the orbit g o g looks like the "add 2" function on Z or N.
>It is easy to find a function that does not look like "add 1"
>but its iteration is "add 2", for example
>n |-> ((n XOR 1) +1)XOR 1
>
>It follows that #S(f) never equals 1.

Very nice once again.

David Hartley

unread,
Jan 28, 2009, 7:13:40 PM1/28/09
to
In message
<e523c5a1-3d83-4a24...@y23g2000pre.googlegroups.com>,
hagman <goo...@von-eitzen.de> writes

>Let g:R->R be arbitrary. We find h:R->R such that g o g = h o h:
>Consider a maximal orbit under g, i.e. either a map
>k:Z->R such that g(k(n)) = k(n+1)
>or a map
>k:N->R such that g(k(n)) = k(n+1) and k(0) is not in g(R). Let h=g
>outside that orbit. On the orbit g o g looks like the "add 2" function
>on Z or N. It is easy to find a function that does not look like "add 1"
>but its iteration is "add 2", for example
>n |-> ((n XOR 1) +1)XOR 1

If g is not 1 - 1 then there may be a point x outside the orbit which is
mapped into it. In that case it's possible g(g(x)) =/= h(h(x)).

Even if g is a bijection. Also the "maximal orbit" may be finite and
cyclic. If its size is odd there will not be a function h defined on it,
and onto it, which differs from g but has g o g = h o h. (On a
(2n+1)-cycle, f^(n+1) = g^(2n+2) = g.)

(This shows that if we change to a countable domain we can have S(f) =
1, even with f a bijection. Take f to be a permutation made up of finite
cycles, one of each odd size.)


--
David Hartley

galathaea

unread,
Jan 29, 2009, 12:03:09 AM1/29/09
to

i was trying to understand how
the 1/2-iteration formula for these monomials
applied to robert's point on -x^3

i knew a half-iteration existed
and saw that it was complex

that seems to be a common property
of many of the half iterates discussed here lately

> >then
> >              2
> >        1+p  p
> >f(x) = a    x
>
> >so if f(x) = -x^3
>
> >   2
> >  p  = 3
>
> >   1+p
> >  a    = -1
>
> >so
>
> >ln(a) = (2n + 1) pi i / (1 + sqrt(3))
>
> >a = exp((2n + 1) pi i / (1 + sqrt(3)))
>
> >this seems like it may work here
>
> >have i chosen a bad branch?
>
> Well, the functions f,g were specified as being from R to R.

topological obstructions!

galathaea

unread,
Jan 29, 2009, 2:02:52 AM1/29/09
to

thank you for your very clear description
and that of the others who filled in the details

i think this is a really cool tool

let me see if i understand by generalising

-+- the generalised israel condition -+-

if

f(x) has only 1 n-cycle

f(p ) = p with 0 <= j < n and all p distinct
j (j+1)_n j

then there is no g(x) such that

[n]
g (x) = f(x)


-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

proof:

[n+1]
g = g o f = f o g

so

g(p ) = g(f(p ))
j (j-1)_n

= f(g(p ))
(j-1)_n

and therefore {g(p_j)}_j is an n-cycle

now

i) if {g(p_j)}_j is actually an n/d-cycle for d | n
so g(p_j) = g(p_(j)_(n/d))

p = f(p )
j (j-1)_n

[n]
= g (p )
(j-1)_n

[n]
= g (p )
(j-1)_(n/d)

= f(p )
(j-1)_(n/d)

= p
(j)_(n/d)

contradicting that the p are distinct

and

ii) otherwise g(p ) = pi (p )
j n j

is an n-cyclic permutation of the points p_j

however

[n]
f(p ) = g (p )
j j

[n-1]
= g (pi (p ))
n j

n
= pi (p )
n j

= p
j

which contradicts p_j and p_(j+1) distinct!

so no such g can exist

(also this shows there is no nth-root
of (2 3 ... n 1) in S_n
which can be proven along other elementary means)

have i understood?

David C. Ullrich

unread,
Jan 29, 2009, 5:16:27 AM1/29/09
to

Of course as we've seen we don't need to assume that.

>Forget the calculations you do below for the specific
>example f = -x^3; there is _no_ function g from C to C
>with f = g o g.

About this: I was thinking about f : R -> R here.
Of course if you're talking about f : C -> C defined
by f(z) = -z^3 then it's no longer true that there is
exactly one two-cycle (in fact there are exactly
three; six elements of order 2).

I _suspect_ that a similar argument shows there's
no such g in this case as well.

>In general, we're going to write f^n for the composition
>of f with itself n times. (And f^0(x) = x).
>
>If f : X -> X and x is in X then order(x, f) is the smallest
>positive integer n such that f^n(x) = x (order(x, f) = infinity if
>there is no such n).

I should have said "smallest non-negative integer n".
That is, if f(x) = x then order(x, f) = 0.

alainv...@gmail.com

unread,
Jan 29, 2009, 6:19:08 AM1/29/09
to
> in sci.logic.)- Masquer le texte des messages précédents -
>
> - Afficher le texte des messages précédents -- Masquer le texte des messages précédents -
>
> - Afficher le texte des messages précédents -

Good morning Sirs,

I've been interested in the equality
h o h = g o g of course
there are lots of involutive functions to
satisfy : h o h = g o g = Id.

We may also consider lines
h o h = g o g = a^2*(x -x1)+x1 ,a real , x1 fixpoint and
h o h = g o g = f ,
f verifying (f(x) -x1)/(f(x)-x2) =a^2*(x -x1)/(x-x2)
x2 the second fixpoint,

Alain

hagman

unread,
Jan 29, 2009, 2:57:34 PM1/29/09
to
On 29 Jan., 01:13, David Hartley <m...@privacy.net> wrote:
> In message
> <e523c5a1-3d83-4a24-abe2-fe0fd68f1...@y23g2000pre.googlegroups.com>,

You're right.
I think I started my idea with something specific like exp(x) or at
least
someting diff'able with positive first derivative in mind.

Robert Israel

unread,
Jan 29, 2009, 3:53:57 PM1/29/09
to
On Jan 29, 2:16 am, David C. Ullrich <dullr...@sprynet.com> wrote:
> On Wed, 28 Jan 2009 06:25:21 -0600, David C. Ullrich
>
>
>
> <dullr...@sprynet.com> wrote:
> >On Tue, 27 Jan 2009 23:25:43 -0800 (PST), galathaea
> ><galath...@gmail.com> wrote:
>
> >>On Jan 27, 8:58 pm,Robert Israel

Yes. If f has an odd number of 2-cycles, there can't be g such that f
= g o g. Note that if (a,b) is a 2-cycle of f,
then (g(a), g(b)) must be another 2-cycle, with
g(g(a)) = f(a) = b and g(g(b)) = a. So g would have to pair up the 2-
cycles, but there's one left over...

galathaea

unread,
Jan 30, 2009, 1:23:25 AM1/30/09
to

so
continuing with the generalisation then

say there are exactly m n-cycles of f

A = { a , a , ..., a } (0 <= j < m)
j j 0 j 1 j n-1

and as before

[n]
g (x) = f(x)

the application of g to each of the A gives
j

B = {g( a ), g( a ), ..., g( a )}
j j 0 j 1 j n-1

more generally
it is easier to write

B = gA
j j

so we can look at the sets

k [k] [k] [k]
g A = {g ( a ), g ( a ), ..., g ( a )}
j j 0 j 1 j n-1

which are also n-cycles of f

the earlier result has shown

A =/= B
j j

but by the very same arguments

k k+1
g A =/= g A
j j

so g must induce a derangement among

{A , A , ..., A }
0 1 m-1
[n]
which must be of order n since g ( a ) = f( a ) e A
j k j k j

the above demonstrations can be interpreted in this form
as a demonstration that there exists no order 2 derangements of 3
elements

in general
the constraint so far is that for a finite number m of n-cycle
families
for the existence of the (1/n)-th iterate g of f it is necessary that
there must exist derangements of m elements of order n

so this looks like a good beginning to mapping the space of allowable
cycle structures
particularly in the analysis of separate cycle properties over R,
C, ...

can sufficient conditions be given?

algebraic prototypes here
appear to be things like
j
w
n
f(x) = x has (1/n)-th iterates g(x) = x

which has every point an n-cycle of g and a fixpoint of f
which is an infinite (uncountable) family example
which the above structural constraints don't discount

similarly the general monomial formula

p-1 1
---- -
n n
p p -1 p
f(x) = a x has (1/n)-th iterate g(x) = a x

can take advantage of x = qth-root of unity to calculate cycle
structures

David C. Ullrich

unread,
Jan 30, 2009, 6:19:57 AM1/30/09
to

Hmm. Right - g induces a map G on 2-cycles of f. G^2 is the
identity, and then the question is why G has no fixed point.
But if g(a) = a then f(a) = a <> b. On the other hand
if g(a) = b and g(b) = a then f(a) = a as well...

Right.

>Robert Israel isr...@math.MyUniversitysInitials.ca
>Department of Mathematics http://www.math.ubc.ca/~israel
>University of British Columbia Vancouver, BC, Canada

David C. Ullrich

alainv...@gmail.com

unread,
Jan 30, 2009, 11:05:49 AM1/30/09
to
> in sci.logic.)- Masquer le texte des messages précédents -
>
> - Afficher le texte des messages précédents -

Bonjour à tous,

I would like to get back with the equation:
h o h = m o m , h <> m , (1)
And build functions h and m from any known pair(g,k)
already satisfying equation (1) ,

Let us choose g(t)= 2t +1 , k(t)=-2t-3 ,
roots of (4x +3) ,
Using parametrized functions
we define h | h(f(t)) = f(g(t))
m | m(f(t)) = f(k(t))
We obtain: h^(2](f(t)) = f(g^2(t)) = f(k^2(t)) = m^(2](f(t))
or h o h = m o m

We may work with x =f(t) = 1/t +1 ,or t = 1/(1+x)
h(x) = 1/(2t+1)-1 = -2/(3+x) ,
m(x) =-1/(2t+3)-1 =(-6-4x)/(5+3x)
with simple algebra:
h^(2](x) = m^(2](x) =-(2x+6)/(3x+7) .

Amicalement,
Alain

David Bernier

unread,
Jan 31, 2009, 5:11:39 AM1/31/09
to

I now think I _was_ missing something that is very easy:

--- 'o' is associative.

So
(g o g) o g = f o g and
g o (g o g) = g o f ,
from which f o g = g o f follows,

> > f,g commute under composition (OK ...)


> > hence f^2(g(x)) = g(f^2(x)) = g(f(f(x)) = g(x), since f(f(x)) = x.

[ {x, f(x)} is the 2-cycle for f, by hypothesis ] so OK ...

---


So, " f^2(g(x)) = g(x) " is easy, with the right idea.

David Bernier

amy666

unread,
Jan 31, 2009, 4:19:48 PM1/31/09
to
alain wrote :

..


> with simple algebra:
> h^(2](x) = m^(2](x) =-(2x+6)/(3x+7) .

in cases where

1) Q(x) = h^(2) = g^(2) ,
2) Q(x) , h , g and t map R U oo to R U oo
3) Q(x) , h , g and t are smooth
4) Q(x) =/= t^(2) where t is distinct from h or g. ( no t exists that also satisfies 2) and 3) )

then there must exist a function f such that f(h) = g and f^(2) = x.

at least , thats what my intuition says ...


>
> Amicalement,
> Alain

regards

tommy1729

Gerry Myerson

unread,
Feb 1, 2009, 6:54:11 PM2/1/09
to
In article
<bd81c898-d9c4-4ed7...@w24g2000prd.googlegroups.com>,
"alainv...@gmail.com" <alainv...@gmail.com> wrote:

> Let us choose g(t)= 2t +1 , k(t)=-2t-3 ,
> roots of (4x +3) ,
> Using parametrized functions
> we define h | h(f(t)) = f(g(t))
> m | m(f(t)) = f(k(t))
> We obtain: h^(2](f(t)) = f(g^2(t)) = f(k^2(t)) = m^(2](f(t))
> or h o h = m o m

Maybe so, but I wouldn't recommend telling someone
that his m o m is a h o h.

--
Gerry Myerson (ge...@maths.mq.edi.ai) (i -> u for email)

quasi

unread,
Feb 1, 2009, 7:19:40 PM2/1/09
to
On Mon, 02 Feb 2009 10:54:11 +1100, Gerry Myerson
<ge...@maths.mq.edi.ai.i2u4email> wrote:

>In article
><bd81c898-d9c4-4ed7...@w24g2000prd.googlegroups.com>,
> "alainv...@gmail.com" <alainv...@gmail.com> wrote:
>
>> Let us choose g(t)= 2t +1 , k(t)=-2t-3 ,
>> roots of (4x +3) ,
>> Using parametrized functions
>> we define h | h(f(t)) = f(g(t))
>> m | m(f(t)) = f(k(t))
>> We obtain: h^(2](f(t)) = f(g^2(t)) = f(k^2(t)) = m^(2](f(t))
>> or h o h = m o m
>
>Maybe so, but I wouldn't recommend telling someone
>that his m o m is a h o h.

Hahaha.

quasi

alainv...@gmail.com

unread,
Feb 2, 2009, 3:16:06 AM2/2/09
to
On 2 fév, 01:19, quasi <qu...@null.set> wrote:
> On Mon, 02 Feb 2009 10:54:11 +1100, Gerry Myerson
>
> <ge...@maths.mq.edi.ai.i2u4email> wrote:
> >In article
> ><bd81c898-d9c4-4ed7-a71a-376fe62f4...@w24g2000prd.googlegroups.com>,

> > "alainvergh...@gmail.com" <alainvergh...@gmail.com> wrote:
>
> >> Let us choose g(t)= 2t +1 , k(t)=-2t-3 ,
> >> roots of (4x +3) ,
> >> Using parametrized functions
> >> we define h  | h(f(t)) = f(g(t))
> >>           m  | m(f(t)) = f(k(t))
> >> We obtain: h^(2](f(t)) = f(g^2(t)) = f(k^2(t)) = m^(2](f(t))
> >> or h o h = m o m
>
> >Maybe so, but I wouldn't recommend telling someone
> >that his m o m is a h o h.
>
> Hahaha.
>
> quasi

Bonjour,

yes, strictly speaking Gerry is right.
I am sure we can define conditions (associativity,
intervals...) and make it mathematically correct,

Alain

mike3

unread,
Feb 18, 2009, 10:21:39 PM2/18/09
to
On 27 Jan., 21:58, Robert Israel

<isr...@math.MyUniversitysInitials.ca> wrote:
> quasi <qu...@null.set> writes:
> > On Tue, 27 Jan 2009 18:50:45 -0800 (PST), Chip Eastham
> > <hardm...@gmail.com> wrote:
>
> > >On Jan 27, 9:03 pm, quasi <qu...@null.set> wrote:
>
> > >> In another thread, I asked a number of questions concerning the
> > >> functional equation
>
> is no such g. An example is f(x) = -x^3.

Does this have any implication for tetration, where we iterate
f(z) = b^z, for complex z and b? Because analytical tetration
functions (actually, multivalued "functions") can be constructed
that seem to work, at least for certain bases such as b = e^(1/e).


Robert Israel

unread,
Feb 19, 2009, 12:48:48 AM2/19/09
to

I would guess that such an f has infinitely many 2-cycles in the complex
plane. Some (for your example, using the principal branch) are
(approximately)
5.88582054270295 + 18.1749088192740 i, 8.01868089084282 + 3.41854132891569 i
7.54116079645200 + 14.1413128226242 i, 7.54116079645202 - 14.1413128226246 i
9.45964020268395 + 13.4529902080628 i, 7.61139682940279 - 31.5549562773120 i
9.72135220788657 + 3.78249017517063 i, 6.37385562851085 + 35.1676010154758 i

(and their complex conjugates)
--

mike3

unread,
Feb 19, 2009, 2:17:53 AM2/19/09
to
On Feb 18, 10:48 pm, Robert Israel

What about for, say, base b = e? Also, would this "half function" be a
multivalued function instead of a regular function? Looking at one
possible
idea for what it might look like, there is a branch point and cut:

http://en.citizendium.org/images/f/f4/Sqrt%28exp%29%28z%29.jpg

so if that is really it, it would have to be a multifunction instead
of a function.

For what bases, if any, would the iterated exponential have exactly
one 2-cycle, and
so the tetration of such bases (which requires evaluating the iterated
exponential at 1)
not be extensible to real towers?

Reply all
Reply to author
Forward
0 new messages