Notation and properties of nested functions?
Moderators: gmalivuk, Moderators General, Prelates
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 n1 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)
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 n1 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: f^{3}(x) = f(f(f(x))). f^{n}(x) = f(f(...f(x)...)), with n nested "f" applications.
See Wikipedia.
See Wikipedia.
Code: Select all
enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵╰(ಠ_ಠ ⚠) {exit((int)⚠);}
Re: Notation and properties of nested functions?
The usual way to denote it is f^{n}(x) (with the notable exception of trig functions, where e.g. sin^{n}(x) represents (sin(x))^{n})
she/they
gmalivuk wrote:Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.King Author wrote:If space (rather, distance) is an illusion, it'd be possible for one metame to experience both body's sensory inputs.
 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 f^{2}(x) = f(x), so by extension f^{n}(x) = f(x) for all positive n. A simple example is the absolute value function.
Functions that are idempotent have the property f^{2}(x) = f(x), so by extension f^{n}(x) = f(x) for all positive n. A simple example is the absolute value function.
For your convenience: a LaTeX to BBCode converter
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))?
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(n^{2}) takes on new meaning when trying to find pairs of socks in the morning.
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 f^{n}(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 nth 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)⚠);}
 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!
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.
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.
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!
Re: Notation and properties of nested functions?
Another function that outputs the same:
f(x)=(x  ((1)^x1)(2.5x +1))/2
Though instead of quadratics, you get exponentiation.
f(x)=(x  ((1)^x1)(2.5x +1))/2
Though instead of quadratics, you get exponentiation.
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.
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.
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.

 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)
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 2adic 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 2adics. 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.
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 2adics. 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.
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.
Re: Notation and properties of nested functions?
Iterated quadratics get messy. The classic example is the logistic map x_{n+1} = rx_{n}(1  x_{n}). 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.
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 2adics are a number system just like the integers, reals, complex numbers, etc. The 2adic 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).
2adic 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 f_{ab}(x), a and b odd, on the 2adics as as ax+b if x is odd and x/2 if x is even; then for any a,b,c,d there is g_{abcd} so g_{abcd} is bijective and f_{ab}g_{abcd} = g_{abcd}f_{cd}. Then, if you can understand the behaviour of any such f, the real question is how g_{abcd}'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 2adics 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 2adics (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 2adic 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 2adics 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.
Who is online
Users browsing this forum: No registered users and 13 guests