Document Type

Article

Department

Mathematics (HMC)

Publication Date

1995

Abstract

Define f on the integers n > 1 by the recurrence f(n) = min( n, minm|n( 2f(m) + 3f(n/m) ). The function f has f(n) = n as its upper envelope, attained for all prime n.

The goal of this paper is to determine the corresponding lower envelope. It is shown that this has the form f(n) ~ C(log n)1 + 1/γ for certain constants γ and C, in the sense that for any ε > 0, the inequality f(n) ≤ (C + ε)(log n)1 + 1/γ holds for infinitely many n, while f(n) ≤ (C + ε)(log \,n )1 + 1/γ holds for only finitely many. In fact, γ = 0.7878... is the unique real solution of the equation 2 + 3 = 1, and C = 1.5595... is given by the expression C = ( γ( 2 log( 2γ) + 3 log( 3γ ) )1/γ / ( γ + 1)( 15 logγ + 1( 5/2 + 3 ) ∑5 ≤ k ≤ 7 logγ + 1((k + 1)/1) ∑8 ≤ k ≤ 15 logγ + 1 ((k + 1)/1) )1/γ ).

This paper also considers the function f0 defined by replacing the integers n > 1 with the reals n > 1 in the above recurrence: f0(x) = min{ x,inf1 < y < x (2f0(x/y) + 3f0(x/y) }. The author shows that f0(x) ~ C0( log x )1 + 1/γ, where C0 = 1.5586... is given by C0 = 6e( 2 log 2 + 3 log 3 )1/γ ( γ /( γ + 1))1 + 1/γ and is smaller than C by a factor of 0.9994... .

Rights Information

© 1995 Society for Industrial and Applied Mathematics