From: "denis-feldmann" Subject: Re: asymptotic functions Date: Sat, 30 Sep 2000 09:47:46 +0200 Newsgroups: sci.math Summary: Asymptotic rates of growth: no trichotomy Don Reble a écrit dans le message : 39D56332.16A64A87@nl2k.ab.ca... > Oh, oh: Jan Schaumann's posting got me thinking. In effect, he asked > whether there are any functions which are asymptotically > sub-exponential, but hyper-polynomial. It turns out, there are some. > > In fact, it seems to me that between any two asymptotic functions there > is a third... Wait, I have to make that more precise. [cut essentially correct analysis, except for two points:] > I rather expect that trichotomy holds: for any monotonic univariate > functions F and G, exactly one of "F == G", "F << G", "F >> G" is > true. If this were not the case, there would be two such functions > such that "not F in O(G) and not G in O(F)", which sounds absurd. Sounds so. Alas, here is a counter example: f(x)=(x*cos^x+ sin^2x)*exp(x^2); g(x)=sqrt(x)*exp(x^2) (check that f and g are monotonous, tend towards +oo, yet neither f/g nor g/f are bounded). >How many asymptotic functions are there? Obviously, there can be no more >a.f.'s than functions. And there are at least as many a.f.'s as real >numbers, since if "q < r" then "x^q << x^r". Under Cantor's C.H., you mean GCH in this case there >are either Aleph-1 or Aleph-2 asymptotic functions. No, only aleph1, because you supposed those functions monotonous (so their values on the rationnal, say, are (more than) enough to caracterize them to equivalence > > Hmm... am I the first person to ponder all this? Of course not. Will > someone please recommend a textbook? Well, you could try Chapter 3 of Dieudonne 's analysis book (it's Calcul Infinitesimal in French, something like Calculus in English?) The historical research on all this was done (almost independently) by Hardy and Landau. > -- > Don Reble djr@nl2k.ab.ca >