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)\le 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\ge 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

Therefore,

and

On the other hand, by monotonicity,

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

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

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

and

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

Hence,

$$\left|\frac{1}{f(a)}-\frac{1}{{\log }_2(a)}\right|\le \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