2 views

Skip to first unread message

Jan 27, 2009, 9:03:16 PM1/27/09

to

In another thread, I asked a number of questions concerning the

functional equation

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

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

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)?

>

<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

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

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

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?

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

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

to

Yes.

quasi

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:

<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

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.

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:

<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

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

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?

>

> 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

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

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:

<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

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

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...

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.)

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|?

<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

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

> 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

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 IsraelIt'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.

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|?

> 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.

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:

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

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

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.

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

<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

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!

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?

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.

Jan 29, 2009, 6:19:08 AM1/29/09

to

>

> - 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

Jan 29, 2009, 2:57:34 PM1/29/09

to

> <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.

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 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

>

> >>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...

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

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

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 -

>

> - 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

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

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

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:

<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)

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:

<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

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>,> On Mon, 02 Feb 2009 10:54:11 +1100, Gerry Myerson

>

> <ge...@maths.mq.edi.ai.i2u4email> wrote:

> >In article

> > "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

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:

>

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

<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

>

>

> > >> In another thread, I asked a number of questions concerning the

> > >> functional equation

>

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).

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)

--

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