Technical Reports

UBC CS TR-93-33 Summary

Analysis of a Recurrence Arising from a construction for Non-Blocking Networks, October 1993 Nicholas Pippenger, 32 pages

Define f on the integers n > 1 by the recurrence

f(n) = min{n, min 2f(m) + 3f(n/m)}. m|n

The function f has f(n) = n as its upper envelope, attained for all prime n. Our goal in this paper is to determine the corresponding lower envelope. We shall show that this has the form f(n) ~ C(log n)^(1+1/g) for certain constants g and C, in the sense that for any epsilon > 0, the inequality f(n) <= (C + epsilon)(log n)^(1 + 1/g) holds for infinitely many n, while f(n) <= (C - epsilon)(log n)^(1 + 1/g) holds for only finitely many. In fact, g = 0.7878.... is the unique real solution of the equation 2^(-g) + 3^(-g) = 1, and C = 1.5595... is given by the expression

_ _ 1/g | -g g -g g | g | 2 log 2 + 3 log 3 | |_ _| C = -------------------------------------------------------------------------- _ __ __ _ 1/g | -g g+1 -g \ g+1 \ g+1 | (g+1) | 15 log (5/2) + 3 /_ log ((k+1)/k) + /_ log ((k+1)/k) | |_ 5 <= k <= 7 8 <= k <= 15 _|

We also consider the function f0 defined by replacing the integers n > 1 with the reals x > 1 in the above recurrence:

f0(x) = min{x, inf 2f0(y) + 3f0(x / y)} 1 < y < x

We shall show that f0(x) ~ C0(log x)^(1+1/g), where C0 = 1.5586... is given by

_ _ 1/g | -g -g -g -g | 1 + 1/g C0 = 6e | 2 log 2 + 3 log 3 | (g / (g + 1)) |_ _|

and is smaller than C by a factor of 0.9994...