 |
|
| Science Forum Index » Math - Symbolic Forum » functional equation of the form p(f(x), f(x^2),... |
|
Page 1 of 1 |
|
| Author |
Message |
| Martin Rubey... |
 Posted: Thu Oct 15, 2009 12:51 pm |
|
|
|
Guest
|
I just discovered several instances of functional equations of the form
p(f(x), f(x^2), ...f(x^n))=0
where p is a polynomial in Sloane, Borwein, etc.
Do they have a name? Pointers to more literature would be very much
appreciated!
Many thanks,
Martin |
|
|
| Back to top |
|
|
|
| Gowen, carrie... |
| Posted: Sat Oct 17, 2009 9:30 am |
|
|
|
Guest
|
For those that are interested, I came across a great opportunity for college money.
It is located at www.MathScholarship.sleekwood.com.
My friend worked with them last year and I am currently in final stages. The nice part is that you don't need to worry about what your current financial status is as my parents disqualify me for some student aide even though I still need it. |
|
|
| Back to top |
|
|
|
| Daniel Lichtblau... |
| Posted: Sat Oct 17, 2009 5:49 pm |
|
|
|
Guest
|
On Oct 17, 2:30 pm, "Gowen, carrie" <guauser+carr... at (no spam) mathforum.org>
wrote:
[quote:cf1a816425]For those that are interested, I came across a great opportunity for college money.
It is located atwww.MathScholarship.sleekwood.com.
My friend worked with them last year and I am currently in final stages. The nice part is that you don't need to worry about what your current financial status is as my parents disqualify me for some student aide even though I still need it.
[/quote:cf1a816425]
Well Martin, there you are. These fascinating polynomial functional
equations are, in some inexplicable (but surely important way),
related to a certain internet-based method of making money for
college.
Daniel Lichtblau
Wolfram Research |
|
|
| Back to top |
|
|
|
| Martin Rubey... |
| Posted: Sun Oct 18, 2009 1:38 am |
|
|
|
Guest
|
Dear Daniel,
Daniel Lichtblau <danl at (no spam) wolfram.com> writes:
[quote:3a2ef63cc5]Well Martin, there you are. These fascinating polynomial functional
equations are, in some inexplicable (but surely important way),
related to a certain internet-based method of making money for
college.
[/quote:3a2ef63cc5]
I trust that you are not making fun of me...and take it that they do
not have a name yet.
Any suggestions?
Martin |
|
|
| Back to top |
|
|
|
| Daniel Lichtblau... |
| Posted: Sun Oct 18, 2009 4:53 am |
|
|
|
Guest
|
On Oct 18, 2:38 am, Martin Rubey <axiom... at (no spam) yahoo.de> wrote:
[quote:5dff275005]Dear Daniel,
Daniel Lichtblau <d... at (no spam) wolfram.com> writes:
Well Martin, there you are. These fascinating polynomial functional
equations are, in some inexplicable (but surely important way),
related to a certain internet-based method of making money for
college.
I trust that you are not making fun of me...
[/quote:5dff275005]
Definitely not.
On the Google Groups version of this thread (maybe others, I did not
check), there was already a reply to your note. It was that reply I
was really addressing. I say this becaue it is possible you read from
elsewhere and did not see that earlier reply (in my browser it shows
up quoted).
[quote:5dff275005]and take it that they do not have a name yet.
[/quote:5dff275005]
I am not sure. I was unable to relate them to q-difference equations.
But maybe they have a name and method of attack I do not know about.
[quote:5dff275005]Any suggestions?
Martin
[/quote:5dff275005]
No good ones. I wish I knew how to solve the simplest linear cases,
because they can be translated to equations of the form
f[(k+1)*x] = a0 + a1*f[x] + a2*f[2*x] + ... + ak*f[k*x]
I've run across problems of this sort in algorithm analysis involving
e.g. divide-and-conquer methods. Best I know how to do is bound from
above and below using q-difference equations, then and show (when
possible) the asymptotics are the same. I doubt this works well for
anything but the simplest of examples.
Here is the sort of example I have in mind.
f[3x] = k0 + k1*f[x] + k2*f[2*x]
Can assume solution is at least linear growth (that is, f[n*x]>=n*f
[x]).
Bound solution above by solving
g[x] = k0 + (k1/2+k2)*f[2*x]
Bound below by solving
h[x] = k0 + (k0 + 2*k1)*f[x]
Works for some purposes, but is a bit crude and probably does not
generalize well.
Daniel Lichtblau
Wolfram Research |
|
|
| Back to top |
|
|
|
| Daniel Lichtblau... |
| Posted: Sun Oct 18, 2009 6:30 am |
|
|
|
Guest
|
On Oct 18, 10:27 am, Martin Rubey <axiom... at (no spam) yahoo.de> wrote:
[quote:d1a19f320c]Daniel Lichtblau <d... at (no spam) wolfram.com> writes:
and take it that they do not have a name yet.
I am not sure. I was unable to relate them to q-difference equations.
But maybe they have a name and method of attack I do not know about.
Well, you could take a q-dilation equation, and set q=x...
[/quote:d1a19f320c]
I was not familiar with that tern but will look into it.
[quote:d1a19f320c][...]
I wish I knew how to solve the simplest linear cases, because they can
be translated to equations of the form
f[(k+1)*x] = a0 + a1*f[x] + a2*f[2*x] + ... + ak*f[k*x]
Hm, what do you mean with "linear cases"?
[/quote:d1a19f320c]
Cases where the polynomial is linear. Often the coefficients, except
perhaps the "constant" a0, are really constant, that is, independent
of x. I'll show an example below.
[quote:d1a19f320c]I've run across problems of this sort in algorithm analysis involving
e.g. divide-and-conquer methods. Best I know how to do is bound from
above and below using q-difference equations, then and show (when
possible) the asymptotics are the same. I doubt this works well for
anything but the simplest of examples.
Here is the sort of example I have in mind.
f[3x] = k0 + k1*f[x] + k2*f[2*x]
(I assume x is a real variable here?)
[/quote:d1a19f320c]
Yes. Actually I have in mind it is a positive integer, so we round off
when needed. The idea is to get complexity of f(x) as a function of x
(probably I should have used n instead of x).
[quote:d1a19f320c]Can assume solution is at least linear growth (that is, f[n*x]>=n*f[x]).
Bound solution above by solving
g[x] = k0 + (k1/2+k2)*f[2*x]
Bound below by solving
h[x] = k0 + (k0 + 2*k1)*f[x]
Works for some purposes, but is a bit crude and probably does not
generalize well.
Is there an easy way to get the Taylor expansion of such a function?
[/quote:d1a19f320c]
I do not know. It can be tricky unless you have a good idea of what
the expansion looks like, e,g, do you have logarithmic terms to
account for?
[quote:d1a19f320c]Would you have a simple concrete example?
Martin
[/quote:d1a19f320c]
One I have in mind is the linear-time median algorithm shown, among
other places, in the algorithms book by Aho, Hopcroft, and Ullman. I
believe the algorithm itself may be due to Knuth. Anyway, the
complexity equation that results is something like
f(n) = n + f(n/5) + f(3*n/5)
In this form you see what I mean by rounding off where necessary to
get integers. But we don't worry too much about that detail, we're
just out to find the complexity. It is O(n), and that is not too hard
to show by the bounding approach I mentioned earlier.
Anyway, I guess a Taylor series ansatz might make sense here. Though
it would be trickier to handle cases where the complexity is not quite
polynomial e.g. O(n*log(n)).
Daniel Lichtblau
Wolfram Research |
|
|
| Back to top |
|
|
|
| Martin Rubey... |
| Posted: Sun Oct 18, 2009 9:27 am |
|
|
|
Guest
|
Daniel Lichtblau <danl at (no spam) wolfram.com> writes:
[quote:498b82aec9]and take it that they do not have a name yet.
I am not sure. I was unable to relate them to q-difference equations.
But maybe they have a name and method of attack I do not know about.
[/quote:498b82aec9]
Well, you could take a q-dilation equation, and set q=x...
Note that I'm going the other way round: I don't want to solve a
functional equation, but rather I have a list of Taylor coefficients,
and want to have a functional equation satisfied by the function. Eg
(warning: ascii art!)
(1) -> guessFE([1, 1, 1, 2, 5, 11, 28, 74, 199, 551, 1553, 4436, 12832, 37496])
(1)
[
n 3 3
[[x ]f(x): 2x f(x ) + x f(x) - 3f(x) + 3= 0,
2 3 4 5
f(x)= 1 + x + x + 2x + 5x + O(x )]
]
(You'll find this sequence in Sloane's Encyclopedia.)
[quote:498b82aec9]I wish I knew how to solve the simplest linear cases, because they can
be translated to equations of the form
f[(k+1)*x] = a0 + a1*f[x] + a2*f[2*x] + ... + ak*f[k*x]
[/quote:498b82aec9]
Hm, what do you mean with "linear cases"?
[quote:498b82aec9]I've run across problems of this sort in algorithm analysis involving
e.g. divide-and-conquer methods. Best I know how to do is bound from
above and below using q-difference equations, then and show (when
possible) the asymptotics are the same. I doubt this works well for
anything but the simplest of examples.
Here is the sort of example I have in mind.
f[3x] = k0 + k1*f[x] + k2*f[2*x]
[/quote:498b82aec9]
(I assume x is a real variable here?)
[quote:498b82aec9]Can assume solution is at least linear growth (that is, f[n*x]>=n*f[x]).
Bound solution above by solving
g[x] = k0 + (k1/2+k2)*f[2*x]
Bound below by solving
h[x] = k0 + (k0 + 2*k1)*f[x]
Works for some purposes, but is a bit crude and probably does not
generalize well.
[/quote:498b82aec9]
Is there an easy way to get the Taylor expansion of such a function?
Would you have a simple concrete example?
Martin |
|
|
| Back to top |
|
|
|
| Daniel Lichtblau... |
| Posted: Sun Oct 18, 2009 12:04 pm |
|
|
|
Guest
|
[quote:f15afa6832][...]
One I have in mind is the linear-time median algorithm shown, among
other places, in the algorithms book by Aho, Hopcroft, and Ullman. I
believe the algorithm itself may be due to Knuth. Anyway, the
complexity equation that results is something like
f(n) = n + f(n/5) + f(3*n/5)
[/quote:f15afa6832]
Correction: That should be
f(n) = n + f(n/5) + f(7*n/10)
I think I have it right this time. Well, strictly speaking the
constant term should be k times n, for k a little larger than 1.
[quote:f15afa6832][...]
[/quote:f15afa6832]
Daniel Lichtblau
Wolfram Research |
|
|
| Back to top |
|
|
|
| Martin Rubey... |
| Posted: Fri Oct 30, 2009 10:41 am |
|
|
|
Guest
|
Daniel Lichtblau <danl at (no spam) wolfram.com> writes:
[quote][...]
One I have in mind is the linear-time median algorithm shown, among
other places, in the algorithms book by Aho, Hopcroft, and Ullman. I
believe the algorithm itself may be due to Knuth. Anyway, the
complexity equation that results is something like
f(n) = n + f(n/5) + f(3*n/5)
Correction: That should be
f(n) = n + f(n/5) + f(7*n/10)
I think I have it right this time. Well, strictly speaking the
constant term should be k times n, for k a little larger than 1.
[/quote]
maybe
http://archive.numdam.org/ARCHIVE/JTNB/JTNB_1993__5_2/JTNB_1993__5_2_365_0/JTNB_1993__5_2_365_0.pdf
asymptotic analysis of a class of functional equations and applications,
by Grabner, Prodinger, Tichy
is of interest to you.
Martin |
|
|
| Back to top |
|
|
|
|
|
All times are GMT - 5 Hours
The time now is Sun Dec 06, 2009 10:39 am
|
|