NetNews Usenet Archive 1992 #27/NN_1992_27.iso/spool/sci/math/15393

Internet Message Format | 1992-11-22 | 3.6 KB

Path: sparky!uunet!decwrl!waikato.ac.nz!canterbury.ac.nz!math!wft
Newsgroups: sci.math
Subject: Re: Functions
Message-ID: <[e-mail]>
From: [e-mail] (Bill Taylor)
Date: Mon, 23 Nov 1992 04:26:31 GMT
References: <[e-mail]>
Organization: Department of Mathematics, University of Canterbury
Keywords: Subexponential
Nntp-Posting-Host: sss330.canterbury.ac.nz
Lines: 69

In article <[e-mail]>, [e-mail] (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              [e-mail]
-------------------------------------------------------------------------------
 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.
-------------------------------------------------------------------------------