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?

Postby sgfw » Sun Feb 16, 2014 10:30 pm UTC

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)

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

Postby phlip » Sun Feb 16, 2014 11:36 pm UTC

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]

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

Re: Notation and properties of nested functions?

Postby Sizik » Sun Feb 16, 2014 11:41 pm UTC

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.

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

Re: Notation and properties of nested functions?

Postby Schrollini » Sun Feb 16, 2014 11:42 pm UTC

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

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

Re: Notation and properties of nested functions?

Postby somehow » Sun Feb 16, 2014 11:45 pm UTC

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?

Postby sgfw » Mon Feb 17, 2014 12:23 am UTC

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?

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

Postby phlip » Mon Feb 17, 2014 12:33 am UTC

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]

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

Re: Notation and properties of nested functions?

Postby Forest Goose » Mon Feb 17, 2014 4:14 am UTC

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?

Postby sgfw » Mon Feb 17, 2014 2:11 pm UTC

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?

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

Postby jestingrabbit » Mon Feb 17, 2014 2:44 pm UTC

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.

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

Re: Notation and properties of nested functions?

Postby cyanyoshi » Mon Feb 17, 2014 2:47 pm UTC

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?

Postby Demki » Mon Feb 17, 2014 3:06 pm UTC

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

Though instead of quadratics, you get exponentiation.

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

Re: Notation and properties of nested functions?

Postby sgfw » Mon Feb 17, 2014 3:07 pm UTC

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.

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

Postby jestingrabbit » Mon Feb 17, 2014 3:52 pm UTC

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?

Postby sgfw » Mon Feb 17, 2014 4:20 pm UTC

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?

Postby alessandro95 » Mon Feb 17, 2014 4:32 pm UTC

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.

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

Re: Notation and properties of nested functions?

Postby Forest Goose » Mon Feb 17, 2014 10:02 pm UTC

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?

Postby sgfw » Tue Feb 18, 2014 12:39 am UTC

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.

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

Re: Notation and properties of nested functions?

Postby PM 2Ring » Tue Feb 18, 2014 11:52 am UTC

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.

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

Re: Notation and properties of nested functions?

Postby Forest Goose » Wed Feb 19, 2014 7:29 am UTC

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.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 6 guests