derivation of Hartley function

We want to show that the Hartley function $\log_{2}(n)$ is the only function mapping natural numbers to real numbers that

1.

$H(mn)=H(m)+H(n)$ (),
2.

$H(m)\leq H(m+1)$ (monotonicity), and
3.

$H(2)=1$ (normalization).

Let $f$ be a function on positive integers that satisfies the above three properties. Using the additive property, it is easy to see that the value of $f(1)$ must be zero. So we want to show that $f(n)=\log_{2}(n)$ for all integers $n\geq 2$ .

From the additive property, we can show that for any integer $n$ and $k$ ,

$f(n^{k})=kf(n).$

(1)

Let $a>2$ be an integer. Let $t$ be any positive integer. There is a unique integer $s$ determined by

$a^{s}\leq 2^{t}<a^{s+1}.$

Therefore,

$s\log_{2}a\leq t<(s+1)\log_{2}a$

and

$\frac{s}{t}\leq\frac{1}{\log_{2}a}<\frac{s+1}{t}.$

On the other hand, by monotonicity,

$f(a^{s})\leq f(2^{t})\leq f(a^{s+1}).$

Using Equation (1) and $f(2)=1$ , we get

$sf(a)\leq t\leq(s+1)f(a),$

and

$\frac{s}{t}\leq\frac{1}{f(a)}\leq\frac{s+1}{t}.$

Hence,

$\Big{|}\frac{1}{f(a)}-\frac{1}{\log_{2}(a)}\Big{|}\leq\frac{1}{t}.$

Since $t$ can be arbitrarily large, the difference on the left hand of the above inequality must be zero,

$f(a)=\log_{2}(a).$

Title	derivation of Hartley function
Canonical name	DerivationOfHartleyFunction
Date of creation	2013-03-22 14:32:15
Last modified on	2013-03-22 14:32:15
Owner	Mathprof (13753)
Last modified by	Mathprof (13753)
Numerical id	11
Author	Mathprof (13753)
Entry type	Derivation
Classification	msc 94A17