Saturday, February 11, 2012

A Functional Equation

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 zz + 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.


fudo said...

is exp( log(z)*log(z/2) / 2log(2)) reasonable enough?

VKS said...

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.

David Swart said...

Two exponentiated by itself log(n) times seems to fit.

Pavel Bakhilau said...

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).

Anonymous said...

f(x) = Sqrt(x) ^ [ log_2(x) - 1 ]

which is the same as VKS's function, slightly rewritten.

John said...


John said...

simplified a little:

z^(ln(z)/ln(4) + 1/2)

JimV said...

2 raised to the power Gamma(n).

JimV said...

Whoops, I meant 2 raised to the power Gamma(z), that is.

JimV said...

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.

JimV said...

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)

David Swart said...

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)

One Brow said...

Some of these seem very complex.

I just have 2^[n(n+1)/2)]

Jeffrey Shallit said...

You're wrong, onebrow. For example, f(2) = 1, but your formula gives 2.

Takis Konstantopoulos said...

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.

One Brow said...


Rob C said...

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);
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) /