integer-valued function

Printable View

May 4th 2009, 09:30 AM
ypatia

integer-valued function

Is there any function (if any) f: Z -> Z such that
f(f(n))=-n , for every n belongs to Z(integers) ??

I think that there is not any function like the one described above but how can we prove it. Any ideas??
Thanks in Advance
May 4th 2009, 06:10 PM
Gamma

Okay, so at first I was with you and thought for sure this function was impossible, and I am still not completely convinced this works, but here is what I am thinking.

First the motivation.
f(n)=a for some a
then you know the value of f(a) to satisfy the requirement
f(a)=-n
f(-n)=-a
f(-a)=n
but then this sort of cycle of 4 works to fit the definition. I have built these ones to satisfy the requirements. So basically you just gotta find a nice way to partition the integers into dijoint cycles of 4 so this will work out and here is what I came up with.

f(0)=0

f(1)=2
f(2)=-1
f(-1)=-2
f(-2)=1

f(3)=4
f(4)=-3
f(-3)=-4
f(-4)=3
.
.
.
This is clearly bijective, so it makes sense definition wise.
so basically I think the closed form is
f(0)=0
for n positive and odd f(n)=n+1
for n positive and even f(n)=-n+1
for n negative and odd f(n)=n-1
for n negative and even f(n)=-n-1

Okay, I think it works, see what you think.
May 4th 2009, 06:26 PM
Media_Man

Freaky Problem

Wow, beautiful work, Gamma.

What happens when we extend this to f:R -> R? f continuous? f:C -> C?
May 5th 2009, 07:32 AM
Gamma

for $\mathbb{C}$ the answer is easy I think.
f(z)=iz which is entire.

For $\mathbb{R}$ I am not sure.

I think there probably is something, but I fear it would need to be really complicated. Like do the same type of thing for my integer function but apply it only to the fractions, then extend it to the other numbers by defining the value function to be the same as the the value of the limit of the Cauchy sequence of rational numbers that converge to that number. There just isnt really that same good way to get a 4 periodic partition of $\mathbb{R}$ that I wanted.
May 5th 2009, 08:49 AM
Media_Man

Extending the concept...

Yes, $f(z)=iz$ was the only thing I could think of for the original problem, which obviously doesn't satisfy the criterion $f:\mathbb{Z} \rightarrow \mathbb{Z}$ .

For $f:\mathbb{R} \rightarrow \mathbb{R}$ , your algorithm should still work, but your partition classes would no longer be countable:

$f(0)=0$
for $\lfloor x \rfloor$ positive and odd $f(x)=x+1$
for $\lfloor x \rfloor$ positive and even $f(x)=-x+1$
for $\lfloor x \rfloor$ negative and odd $f(x)=x-1$
for $\lfloor x \rfloor$ negative and even $f(x)=-x-1$

I wonder if there is a continuous function $f:\mathbb{R} \rightarrow \mathbb{R}$ satisfying $(fof)(x)=-x$ .

So there exists a "continuous" function in $\mathbb{C}$ (does this term still apply?), and a highly discontinuous function in $\mathbb{R}$ . But is there something "in between"?
May 5th 2009, 08:59 AM
NonCommAlg

here's how produce infinitely many bijections $f: \mathbb{Z} \longrightarrow \mathbb{Z}$ that satisfy $f(f(n))=-n,$ for all $n \in \mathbb{Z}$ :

choose any sequence $\{ A_j \}$ of subsets of $\mathbb{N}$ which satisfy the following conditions:

1) $|A_j|=2,$ for all $j,$ and $\bigcup_{j=1}^{\infty} A_j=\mathbb{N};$

2) $A_i \cap A_j =\emptyset,$ for any $i \neq j.$

for any $j$ let $A_j=\{a_j,b_j \}$ and define the function $f: \mathbb{Z} \longrightarrow \mathbb{Z}$ by $f(0)=0$ and for all $j: \ f(a_j)=b_j, \ f(b_j)=-a_j, \ f(-a_j)=-b_j, \ f(-b_j)=a_j.$

it's easy to see that for all $n \in \mathbb{Z}: \ f(f(n))=-n.$ so basically what i did was to decompose $f$ into an infinite product of disjoint cycles of length 4. (Surprised)

Claim: every bijective function $f: \mathbb{Z} \longrightarrow \mathbb{Z}$ which satisfies the identity $f(f(n))=-n$ is in the above form! (so we actually characterized such functions!)
May 5th 2009, 12:20 PM
Gamma

The function f(z)=iz is even better than continuous. It is analytic in the entire complex plane (this is what entire means). This means it is infinitely continuously differentiable meaning each derivative is continuous. Furthermore, it has a power series which converges absolutely to the function. This is clear because it's power series is simply $0+iz+0z^2+...$ .

Yeah, NCA has just generalized the same method I used, you just needed one example. It is pretty obvious that all of those that NCA created work as they are the same in spirit. Furthermore, I think it is pretty clear that his claim is in fact true because of what was seen by my "motivation" part on the original post. But I think you can do a little better even.
you have a function for $\mathbb{Z}$ it clearly must send 0 to 0, otherwise it would not be injective.
$0 \rightarrow b \not = 0$
but then
$b \rightarrow -0=0$
but then the rest is clear because for any integer a wherever it sends a automatically determines where it will send the rest of the cycle, including its negative and some arbitary other integer and its negative that must be different to preserve bijectivity. So this necessarily partitions all of the integers into disjoint sets of {+/-a,+/-b} for nonzero a,b, and then the one for the 0.

As for the real number situation, since one can order the positive rationals (they are countable) and index them in bijective correspondance with the natural numbers, you should be able to easily do this for the rational numbers.
f(0)=0
then take the first two positive rational numbers and make a 4 cycle with their negative counterparts
then do the same for the next 2 and their negatives
and so on.

The question is how to extend it continuously from the rationals to the irrationals. I was thinking originally you could just do this by letting it equal whatever the limit of a cauchy sequence of rational numbers is under this above bijection. But I don't think there is any reason to believe these would converge, or even if they did to believe that these cauchy sequences should be unique.

Conclusion:
definitely possible for $\mathbb{Z}, \mathbb{Q}, \mathbb{C}$ and these have been exhibited.
verdict still out on a continuous $\mathbb{R}$
May 5th 2009, 04:00 PM
NonCommAlg

this has nothing to do with number theory but since it's been proposed as probably a "challenge" by Gamma and Media_Man, i thought about it and here's my answer to the question:

claim: there's no continuous function $f: \mathbb{R} \longrightarrow \mathbb{R}$ satisfying $f(f(x))=-x.$

Proof: suppose there's such a function. then $f(x)=0$ if and only if $x=0$ and so $b=f(1) \neq 0.$ now if $b > 0,$ then since $f(b)=-1,$ there must exist an $a$ between $1$ and $b$ such that $f(a)=0,$

by IVT, which is impossible. if $b < 0,$ then $f(-1)=-b > 0,$ and thus $f(a)=0,$ for some $a$ between $-1$ and $b,$ by IVT, which is again impossible. Q.E.D.
May 5th 2009, 04:06 PM
Gamma

I like it.
May 6th 2009, 06:20 AM
Media_Man

Cool

Very good, NCA. So it requires $\mathbb{C}$ to construct a continuous function satisfying ypatia's initial requirements. Gamma's algorithm can still be used for the reals, even though they are uncountable, and even though it is discontinuous:

Define $f: \mathbb{R} \rightarrow \mathbb{R}$ by:

$f(0)=0$

For all $x \in \{ n+\alpha \in \mathbb{R}|n \in \mathbb{Z}, \alpha \in [0,1), x \neq 0 \}$ , define:

for $n$ positive and odd $f(x)=x+1$
for $n$ positive and even $f(x)=-x+1$
for $n$ negative and odd $f(x)=x-1$
for $n$ negative and even $f(x)=-x-1$