Newsgroups: sci.math
Subject: Re: Functions
From: wft@math.canterbury.ac.nz (Bill Taylor)
Date: Mon, 23 Nov 1992 04:26:31 GMT
Organization: Department of Mathematics, University of Canterbury
Keywords: Subexponential

In article <Nov.19.12.14.36.1992.3136@pepper.rutgers.edu>, gore@pepper.rutgers.edu (Bittu) writes:
|> 
|> I am trying to figure out if a certain class of functions is well
|> defined and also trying to find good nontrivial examples of functions
|> that belong to this class. 

|> Let me define a class "subexp" first:
|> 
|> f is in subexp if for every e > 0, f(n) = o(2^(n^e))
|>                         this is little oh ^ 
|> 
|> Now define the class subsubexp with the follwing restriction:
|> 
|> For any two functions f and g in subsubexp, their composition must be
|> in subexp.
|> 
|> Is subsubexp well defined?

Looks like it is to me. I would say for sure if they have to be monotonic also.

|> I know that functions like 2^((log n)^k)    .................(*)
|> for any k are in subsubexp, but I want better examples. 

Pity, I thought these were quite good examples. It's always possible to
distinguish the dividing line between a slower-growing and a faster-growing
class more and more finely, seemingly.  For instance, a bit of logging and
fiddling about seems to indicate that 

f(n) = 2^[(log n)^((log log n)^k)]   is subsubexp, but that

g(n) = 2^[ 2^(sqrt(log n))]   is bigger than subsubexp, (though still subexp).

f(n) here is bigger than the example (*) given above.

|> Maybe there
|> are functions that come out of combinatorial analysis (like the Ramsey
|> function R(n,n) for instance) that belong to subsubexp.

Maybe, but I would think it most unlikely to be significant. 
                                           Most of the "naturally occurring"
functions like this seem to fit in to the log-&-exp hierarchy fairly simply,
(when they're known at all). I think it doubtful they would lie close to your
dividing line, sadly. There is an out-of-print pamphlet concerning this
hierarchy of functions, in which the author makes this same point concerning
prime number densities and so forth. (Unfortunately I can't lay my hands on it
right now, so can't give a reference. Perhaps someone else can recognize it
and tell us?)

On the face of it, the distiction between subsubexp and subexp looks significant,
in that subsubexp seems to be a natural accumulation point for closure under
composition, a highly desirable property. But alas, these composition-closure
accumulations occur all up and down the log-exp hierarchy of functions.

For example, the functions  h(n) = 2^(2^(...2^(2^n)))) , where the number
of nests is fixed for each function, but varies to give the whole class, 
(together with functions that are O of these), are another "natural" accumulation
class for composition-closure; with the functions just "a little bit bigger"
being *not* closed under composition.


Nice problem though.

-------------------------------------------------------------------------------
              Bill Taylor              wft@math.canterbury.ac.nz
-------------------------------------------------------------------------------
 Galaxies - results of chaotic amplification of quantum events in the big bang.
 Free will- the result of chaotic amplification of quantum events in the brain.
-------------------------------------------------------------------------------

Xref: sparky sci.math:15409 misc.education:4459 sci.edu:1189 misc.kids:28996