You might know the gamma function, which is one way to extend the factorial function to the complex plane. It obeys the functional equation
Γ(1) = 1
Γ(z + 1) = z Γ(z).
In fact, if we demand that it be logarithmically convex and obey the rules above, then the ordinary gamma function is in fact the only way to extend the factorial function to the positive reals. (Here Γ(n) = (n-1)!.)
Now the successor function z → z + 1 is on the lowest level of the Grzegorczyk hierarchy. The next higher level includes the function z → 2z. So, in analogy with gamma function, suppose we demand that
f(1) = 1
f(2z) = z f(z).
Then what's a "reasonable" function that satisfies this functional equation? My answer in the comments tomorrow, unless someone comes up with the same answer I did.
Saturday, February 11, 2012
Subscribe to:
Post Comments (Atom)
16 comments:
is exp( log(z)*log(z/2) / 2log(2)) reasonable enough?
Let g(x) = x(x-1)/2 , so that g(x+1) = x + g(x).
Then if we define f(x) = 2^g(log_2(x)), then f(2x) = x*f(x) and f(1) = 1 as required.
Two exponentiated by itself log(n) times seems to fit.
Let g(z) = f(2^z), so that g(z) = 2^(z-1) * g(z-1) and g(0) = 1. Then g(z) = 2^(z*(z-1)/2), and f(z) = g(log_2 z).
f(x) = Sqrt(x) ^ [ log_2(x) - 1 ]
which is the same as VKS's function, slightly rewritten.
z^((1+ln(z)/ln(2))/2)
simplified a little:
z^(ln(z)/ln(4) + 1/2)
2 raised to the power Gamma(n).
Whoops, I meant 2 raised to the power Gamma(z), that is.
Dang, what I actually meant to say is f(2^n) = 2^Gamma(n), where Gamma(n) = (n-1)!, but you want f(z), where z=2^x,
or x=ln(z)/ln(2), so:
f(z) = 2^Gamma(ln(z)/ln(2)) - that's my final answer.
No it isn't. I shouldn't do this late at night without checking my work before posting - exponents add, not multiply;
f(2^n) = 2^(n-1)*2^(n-2)* ,,, 1
= 2^[(n-1)*(n-2)/2]
= 2^{Gamma(n)/[2*Gamma(n-2)]}
so I think what you want is
f(z) = 2^{Gamma(x)/[2*Gamma(x-2)]}
where x = ln(z)/ln(2)
After double checking I take back my earlier comment too.
In the end I got what VKS got.
(giving credit to a search for 1,1,2,8,64,1024 in OEIS)
Some of these seem very complex.
I just have 2^[n(n+1)/2)]
You're wrong, onebrow. For example, f(2) = 1, but your formula gives 2.
JimV
Your latest function satisfies
f(2z) = 2 zf(z)
(there is an extra 2)
so it's not correct.
By the way, the question really means that f should be an analytic extension of the function which assigns the number 2^{n(n-1)/2} to the integer 2^n for all nonnegative integers n.
I had occasion to solve a somewhat similar equation in January. The following technique failed for mine, but seems to have worked for yours!
But maybe the Maple won't render well...
> g(t) = f(2^t);
/ t\
g(t) = f\2 /
> g(t+1) = 2^t*g(t);
t
g(t + 1) = 2 g(t)
> rsolve(%, g(t));
(1/2 t (t - 1))
2 g(0)
> eval(%, t = log[2](z));
/ /ln(z) \\
|ln(z) |----- - 1||
| \ln(2) /|
|-----------------|
\ 2 ln(2) /
2 g(0)
> simplify(%);
/ -ln(z) + ln(2)\
|- --------------|
\ 2 ln(2) /
z g(0)
> f(1)*z^(ln(z)/(2*ln(2))-1/2);
/ ln(z) \
|------- - 1/2|
\2 ln(2) /
f(1) z
> (eval(%, z = 2*z))/%;
/ln(2 z) \
|------- - 1/2|
\2 ln(2) /
(2 z)
--------------------
/ ln(z) \
|------- - 1/2|
\2 ln(2) /
z
simplify((2*z)^((1/2)*ln(2*z)/ln(2)-1/2)/z^((1/2)*ln(z)/ln(2)-1/2));
z
>
Post a Comment