## Notation and properties of nested functions?

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

sgfw
Posts: 46
Joined: Wed Jun 19, 2013 11:47 pm UTC

### Notation and properties of nested functions?

Say you have a function, f(x). Is there any easy way to denote f(f(f(...f(x)...))), nested n times? Also, are there any handy properties to help simplify things like this? Some are obvious, such as:

if f(x) is in the form x + c, then nested n times it would be x + c*n
if f(x) is in the form c*x, then nested n times it would be x*c^n
if f(x) is in the form c*x + d, then nested n times it would be x*(c^n)*d*(sum from i=0 to n-1 of c^i)

These are all I have found, but if there is something I am missing here please tell me. Pretty much, I am trying to find a generalized form of this nested n times:

2.5*x^2 + 3*x/2 - (5*x+2)*floor(x/2)

phlip
Restorer of Worlds
Posts: 7569
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

### Re: Notation and properties of nested functions?

The usual notation I've seen for this is function powers: f3(x) = f(f(f(x))). fn(x) = f(f(...f(x)...)), with n nested "f" applications.

See Wikipedia.

Code: Select all

`enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}`
[he/him/his]

Sizik
Posts: 1243
Joined: Wed Aug 27, 2008 3:48 am UTC

### Re: Notation and properties of nested functions?

The usual way to denote it is fn(x) (with the notable exception of trig functions, where e.g. sinn(x) represents (sin(x))n)
gmalivuk wrote:
King Author wrote:If space (rather, distance) is an illusion, it'd be possible for one meta-me to experience both body's sensory inputs.
Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.

Schrollini
Posts: 515
Joined: Sat Sep 29, 2012 5:20 pm UTC

### Re: Notation and properties of nested functions?

Iterated functions can have incredibly rich dynamics. Smale's horseshoe and the baker's map are two classic examples. Given this, I don't think there's any general simplification that always applies.

Functions that are idempotent have the property f2(x) = f(x), so by extension fn(x) = f(x) for all positive n. A simple example is the absolute value function.
For your convenience: a LaTeX to BBCode converter

somehow
Posts: 99
Joined: Wed Aug 14, 2013 8:31 pm UTC

### Re: Notation and properties of nested functions?

This may sound a little obvious, but I'll say it anyway, because I'm not exactly sure what it is the original poster wants and I think this might help clarify:

The use of powers to denote repeated function application is just a notational convenience. It doesn't get you any closer to knowing what actually happens when you repeatedly apply a function. Are you asking for this sort of notational shorthand, or are you interested in the particular question of what f(x), f(f(x)), etc. actually are when f(x) is (5/2)x^2 + (3/2)x - (5x+2)(floor(x/2))?
Xenomortis wrote:O(n2) takes on new meaning when trying to find pairs of socks in the morning.

sgfw
Posts: 46
Joined: Wed Jun 19, 2013 11:47 pm UTC

### Re: Notation and properties of nested functions?

Are you asking for this sort of notational shorthand, or are you interested in the particular question

I'm trying to learn what I can about this sort of thing so that I can come closer to solving the problem. Of course is someone can solve it for me, then that would be great. Really, what I'm looking for is something I can just google that will give me information on the topic (apparently "iterated functions"). I didn't even have a term for what I'm describing.

Also, I thought fn(x) was the nth derivative of f(x). Is this one of those things that just depends on context?

phlip
Restorer of Worlds
Posts: 7569
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

### Re: Notation and properties of nested functions?

The n-th derivative is usually written f(n)(x), just to tell it apart from function iteration. Between that and context, it's usually enough to tell them apart.

Code: Select all

`enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}`
[he/him/his]

Forest Goose
Posts: 377
Joined: Sat May 18, 2013 9:27 am UTC

### Re: Notation and properties of nested functions?

In general, there will be no useful and pretty closed form; given the quadratic terms and the floor, it will get ugly quick. You may be able to get some sort of calculation rules based on how those functions interact, but using a computer to carry out the iteration will be probably be quicker (unless you're using really really big exponents on f, but then you can just approximate it by something simpler anyways).

More to the point, though:

1.) What is the context of this function? (as in why not some other function or set of coeffs.)
2.) Do you want a closed form for its own sake? Or are you trying to determine what happens to points under repeated application? Or something else entirely?

I can't guarantee anything, but if you can give me some details of what you are doing and what you want to know, I may be able to help in some form.

If not, good luck:-) Such problems are not at all simple!
Forest Goose: A rare, but wily, form of goose; best known for dropping on unsuspecting hikers, from trees, to steal sweets.

sgfw
Posts: 46
Joined: Wed Jun 19, 2013 11:47 pm UTC

### Re: Notation and properties of nested functions?

I'm actually making an attempt to prove the collatz conjecture. The function f(x) = (5/2)x^2 + (3/2)x - (5x+2)(floor(x/2)) will output x/2 is x is even and 3x + 1 if x is odd. If I can find a generalized form of that function nested n times, I may be able to find the limit as n approaches infinity, and so if I can prove that that limit is equal to one for every positive integer x, then I will know the collatz conjecture is true. Of course, I need to find a general form of (5/2)x^2 + (3/2)x - (5x+2)(floor(x/2)) nested n times, first. Is it possible a general form doesn't exist?

jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

### Re: Notation and properties of nested functions?

sgfw wrote:I'm actually making an attempt to prove the collatz conjecture. The function f(x) = (5/2)x^2 + (3/2)x - (5x+2)(floor(x/2)) will output x/2 is x is even and 3x + 1 if x is odd. If I can find a generalized form of that function nested n times, I may be able to find the limit as n approaches infinity, and so if I can prove that that limit is equal to one for every positive integer x, then I will know the collatz conjecture is true. Of course, I need to find a general form of (5/2)x^2 + (3/2)x - (5x+2)(floor(x/2)) nested n times, first. Is it possible a general form doesn't exist?

Well, even if there weren't a floor in there, you'd have serious problems. A quadratic f will have f^n be a degree 2^n polynomial. That's a huge problem in terms of what you're trying to do imo.
Last edited by jestingrabbit on Mon Feb 17, 2014 3:48 pm UTC, edited 1 time in total.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

cyanyoshi
Posts: 407
Joined: Thu Sep 23, 2010 3:30 am UTC

### Re: Notation and properties of nested functions?

sgfw wrote:Is it possible a general form doesn't exist?

Some very interesting fractals come out of these kinds of problems, like Julia sets and Newton fractals. If anyone wants to look for the regions where the repeated application of this function converges, I would love to see it!

Demki
Posts: 199
Joined: Fri Nov 30, 2012 9:29 pm UTC

### Re: Notation and properties of nested functions?

Another function that outputs the same:
f(x)=(x - ((-1)^x-1)(2.5x +1))/2

sgfw
Posts: 46
Joined: Wed Jun 19, 2013 11:47 pm UTC

### Re: Notation and properties of nested functions?

Speaking of interesting things, I noticed something. The collatz conjecture only works for positive integers, and the generalized form I made [which I now simplified to x/2 + (5*x+2)*mod(x/2, 1)] when iterated seems to work for all real numbers except zero. All positive numbers approach the cycle 1, 4, 2, 1, while all negative numbers seem to approach the cycle -17, -50, -25, -74, -37, -110, -55, -164, -82, -41, -122, -61, -182, -91, -272, -68, -34. Keep in mind decimals seem to work as well.

Edit: Demki's function does not behave the same way with decimals or negative numbers, while it does with positive integers.

jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

### Re: Notation and properties of nested functions?

sgfw wrote:Speaking of interesting things, I noticed something. The collatz conjecture only works for positive integers, and the generalized form I made [which I now simplified to x/2 + (5*x+2)*mod(x/2, 1)] when iterated seems to work for all real numbers except zero. All positive numbers approach the cycle 1, 4, 2, 1, while all negative numbers seem to approach the cycle -17, -50, -25, -74, -37, -110, -55, -164, -82, -41, -122, -61, -182, -91, -272, -68, -34. Keep in mind decimals seem to work as well.

Edit: Demki's function does not behave the same way with decimals or negative numbers, while it does with positive integers.

There's at least one cycle you've missed: -2 -> -1 -> -2... but it might be a repulsive attractor.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

sgfw
Posts: 46
Joined: Wed Jun 19, 2013 11:47 pm UTC

### Re: Notation and properties of nested functions?

There's at least one cycle you've missed: -2 -> -1 -> -2... but it might be a repulsive attractor.

Yeah, so I guess it doesn't work completely with all negative numbers. Oh well, it's still interesting.

alessandro95
Posts: 109
Joined: Wed Apr 24, 2013 1:33 am UTC

### Re: Notation and properties of nested functions?

There's also -5 -> -14 -> -7 -> -20 -> -10 -> -5
But there's no other known cycle (except 0 -> 0 if we consider it)
The primary reason Bourbaki stopped writing books was the realization that Lang was one single person.

Forest Goose
Posts: 377
Joined: Sat May 18, 2013 9:27 am UTC

### Re: Notation and properties of nested functions?

Every bit string is the parity vector of a cycle made up of rational numbers for the 2-adic continuation of the collatz function.

If you generalize to functions of the form ax + b with a and b odd, you should find that all such are conjugal on the 2-adics. The whole conjecture can be reduced down to determining how these conjugacies shuffle trajectories around. Personally, I'm of the opinion that this is the "right way" to look at the problem.

I don't belive that a good answer to the problem exists in real valued extensions, all such extensions seem to "drown out" the number theoretical part since they replace parity with fractional parts; the conjecture hinges on what happens to trajectories mod 2, throwing that out doesn't seem a strong start.

Anyways, just my personal opinion posted poorly from a phone - ill probably extend this out later since it's hard typing this way (interesting conversation, just wanted to throw my 2 cents in since ill be out all day.)

*if you are considering continuous real valued extensions, then there will be a cycle of every length for any such by Sharkovskii's Theorem sine 1->4->2 is of period 3.
Forest Goose: A rare, but wily, form of goose; best known for dropping on unsuspecting hikers, from trees, to steal sweets.

sgfw
Posts: 46
Joined: Wed Jun 19, 2013 11:47 pm UTC

### Re: Notation and properties of nested functions?

the conjecture hinges on what happens to trajectories mod 2, throwing that out doesn't seem a strong start

I'm not really sure what your post is saying- I don't know what "adic" means (something to do with prime numbers?). But anyway, I think I understand what you are saying here, and the function I made actually uses modulo, I just turned mod(a, b) into a - b*floor(a/b) to make the function easier to simplify. I later changed it back to mod when I simplified the function to x/2 + (5*x+2)*mod(x/2, 1). I'm not really sure that that was what you were asking. If I misunderstood, please tell me.

PM 2Ring
Posts: 3701
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Sydney, Australia

### Re: Notation and properties of nested functions?

Iterated quadratics get messy. The classic example is the logistic map xn+1 = rxn(1 - xn). See the bifurcation diagram & the cobweb diagram about a third of the way down that Wikipedia page. If we use complex numbers instead of reals then we're into Julia / Mandelbrot set territory.

Of course, adding floor / mod into the mix (a la the bakers map & Smale's horseshoe mentioned earlier by Schrollini) is bound to make things even messier.

FWIW, a few years ago, inspired by the connection between the logistic map & the Mandelbrot set, I played around with variants of Collatz in the Gaussian integers, hoping to get some interesting insights. I didn't discover anything particularly useful, but I reckon that it's worth checking out.

Forest Goose
Posts: 377
Joined: Sat May 18, 2013 9:27 am UTC

### Re: Notation and properties of nested functions?

sgfw wrote:
the conjecture hinges on what happens to trajectories mod 2, throwing that out doesn't seem a strong start

I'm not really sure what your post is saying- I don't know what "adic" means (something to do with prime numbers?). But anyway, I think I understand what you are saying here, and the function I made actually uses modulo, I just turned mod(a, b) into a - b*floor(a/b) to make the function easier to simplify. I later changed it back to mod when I simplified the function to x/2 + (5*x+2)*mod(x/2, 1). I'm not really sure that that was what you were asking. If I misunderstood, please tell me.

The 2-adics are a number system just like the integers, reals, complex numbers, etc. The 2-adic integers extend the rationals of the form a / b, b odd. A simple way to look at them is as infinitely long binary numbers with no decimal; of course, without an understanding of how they work, this has some unexpected consequences, like ...111111 = -1 (to see this, try carrying out adding 1 to the number and carrying out the addition).

2-adic integers have properties like being even or odd - which real numbers bury under having a rather ugly fractional part. The other benefit is this: define fab(x), a and b odd, on the 2-adics as as ax+b if x is odd and x/2 if x is even; then for any a,b,c,d there is gabcd so gabcd is bijective and fabgabcd = gabcdfcd. Then, if you can understand the behaviour of any such f, the real question is how gabcd's shuffle around the naturals; and if the f's are too hard to work with, they can be extended to a bigger class (yet, again).

I'm not saying that some other approach won't solve the problem, indeed, some other approach probably will. However, I do, personally, believe that it is a useful perspective to become familiar with - the 2-adics are a very simple and elegant extension of the integers that still functions like the integers, but has versions of analysis and topology - it's like working in the integers without being hampered by them being discrete, this is quite powerful if used correctly.

As for the comment about "trajectories mod 2":
What makes the conjecture both maddening and fascinating is that even if some number fails to reach 1 after a billion billion billion steps, it can still hit a power of 2 on the very next step. It's not "growing", as in strictly enlarging, that is indicative of things, it is how many times the next iterate is divisible by 2 (size is a side effect of this, of course). That the 2-adics (mod 2) are the same as the integers (mod 2), rather than some smeared out continuum of irrationals, is valuable since they retain this aspect of the problem. In short, there is a direct and visceral connection between how the 2-adic form and the integer forms work; for the reals, this is lost, you end up with one out of a trillion equal choices of functions, the big link being that they all restrict to the Collatz function on the integers. This isn't to say that there isn't value in considering the reals, just that it may be worth looking at from a different angle.

Finally, I'm sleepy and had a long day; this is probably quite poorly put together; also, I'm not the best at clarity on good days! I would suggest reading up on the 2-adics and messing around with them a bit, they may be of use in your endeavours. Most of all, good luck:-)
Forest Goose: A rare, but wily, form of goose; best known for dropping on unsuspecting hikers, from trees, to steal sweets.