Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I've often idly wondered one can say about the collection of "growth rates". By growth rate, let's say we mean an equivalence class of functions (0,infty) \to (0,\infty), where two functions f_1,f_2 are equivalent if f_1/f_2 and f_2/f_1 are bounded away from 0 and infinity. You can add, and multiply them, and they form a poset under the pordering where f_1 <= f_2 if f_1/f_2 is bounded above.

So, in loose terms, does the sequence xlog(1+x), xlog(log(10+x)), xlog(log(log(100+x))), ... converge to x in some natural way? With a little thought you can construct a growth rate which is strictly greater than x and strictly less than all growth rates in that sequence, so it probably no. Still is there any sort of natural "topology"? Can you find a directed set of growth rates which are linearly ordered, and eventually smaller than anything larger than x?

There's probably a better way to look at this (which is why I ask). =)

share|improve this question
add comment

6 Answers 6

You might want to look at the theory of Hardy fields.

These are fields of germs of functions at a neighborhood of infinity closed under differentiation.

The classical reference is Hardy's book "Orders of infinity". You may also want to look at the works of Maxwell Rosenlicht. While Hardy's book dates back to the 1920's, Rosenlicht works are from the 1980's and you can found them through mathscinet.

share|improve this answer
1  
Some one ought to vote this up. (I already have.) The reference to Rosenlicht's work looks very useful, and extends my answer. –  David Speyer Oct 28 '09 at 17:40
1  
Bourbaki has a nice treatment of Hardy fields in his Volume 4 (Functions of a real variable). –  Dmitri Pavlov Oct 28 '09 at 18:00
add comment

There is some fascinating work in the subject of cardinal characteristics of the continuum in set theory that directly relates to the concept of growth rates of functions. I believe that it is the ideas in this subject that are ultimately fundamental to your question. I explain a little about the general subject of cardinal characteristics in my answer here.

Much of the interest of your question is already present for functions on the natural numbers. The two main orders on such functions that one considers in cardinal characteristics are

  • almost-less-than, where $f \lt^\ast g$ means that $f(n) \lt g(n)$ for all $n$ except finitely often, and
  • domination, where $f \lt g$ means that $f(n) \lt g(n)$ for all $n$.

A family $F$ of functions is said to be unbounded if there is no function $g$ that has $f\lt^\ast g$ for all $f\in F$. That is, an unbounded family is a family that is not bounded with respect to $\lt^\ast$. A family $F$ is dominating if every function $f$ is dominated by some function $g\in F$. The corresponding cardinal characteristics of these two types of families are:

  • The bounding number $\frak{b}$ is the size of the smallest unbounded family.
  • The dominating number $\frak{d}$ is the size of the smallest dominating family.

It is easy to see that $\frak{b}\leq\frak{d}$, simply because any dominating family is also unbounded. Also, both $\frak{b}$ and $\frak{d}$ are at most the continuum $\frak{c}$, the size of the reals. It is not difficult to see that both of these numbers must be uncountable, since for any countable family of functions $f_0,f_1, f_2,\ldots$, we can build the function $g(k) = \sup_{n\leq k}f_n(k)+1$, which eventually exceeds any particular $f_n$. In other words, any countable family of functions is bounded with respect either to almost-less-than or with respect to domination. Thus, $\omega_1\leq\frak{b},\frak{d}\leq\frak{c}$.

It follows from these simple observations that if the Continuum Hypothesis holds, then both the bounding number and the dominating number are equal to $\omega_1$, which under CH is the same as the continuum $\frak{c}$.

Now, the amazing thing is that ZFC independence abounds with these concepts. First, it is relatively consistent with ZFC that the Continuum Hypothesis fails, and both the dominating number and the bounding number are as large as they could possibly be, the continuum itself, so that $\frak{b}=\frak{d}=\frak{c}$. Second, it is also consistent that both are strictly intermediate between $\omega_1$ and the continuum $\frak{c}$, but still equal. Next, it is also consistent with $\text{ZFC}+\neg\text{CH}$ that the bounding number $\frak{b}$ is as small as it could be, namely $\omega_1$, but the domintating number is much larger, with value $\frak{c}$. The tools for proving all these results and many others involve the method of forcing.

Now, let me get to the part of my answer that directly relates to the idea of rates-of-growth. A slalom is defined to be a sequence of natural number pairs $(a_0,b_0), (a_1,b_1), \ldots$ with $a_n\lt b_n$. Each slalom s corresponds to the collection of functions $f:\omega\to\omega$ such that $f(n)$ is in the interval $(a_n,b_n)$ for all but finitely many $n$. That is, imagine an olympic athlete on skiis, who must pass through (all but finitely many of) the slalom posts. An $h$-slalom is a slalom such that $|b_n-a_n|\leq h(n)$.

Thus, a slalom is a growth rate of functions, in a very precise sense. With suitably chosen (countable collections of) slaloms, it is possible to express the concept of growth rate that you mentioned in your question.

The set theory gets quite interesting. For example, a major question is: how many slaloms suffice to cover all the functions? This is particularly interesting when one restricts the size of the slaloms by considering $h$-slaloms. A fat slalom is a $2^n$-slalom, where the $n^{\rm th}$ interval has size at most $2^n$.

It turns out that this is connected with ideas involving meagerness, otherwise known as category. For example, Bartoszynski proved that every set of reals of size less than $\kappa$ is meager if and only if for every function $h$ and every family of $h$-slaloms $F$ of size less than $\kappa$, there is a function $g$ eventually missing every slalom in $F$. In other words, the possibility of a family of fewer than $\kappa$ many $h$-slaloms covering all the functions is equivalent to every set of size less than $\kappa$ being meager.

And so on. There is a large amount of work on these and similar ideas. An article particularly focused on slaloms would be this. And there is a survey article by Brendle on cardinal characteristics.

share|improve this answer
    
I finally texified this entry. –  Joel David Hamkins Jan 3 '12 at 22:49
    
Joel, you will sleep better at night after this. –  Will Jagy Jan 3 '12 at 23:14
    
You are right! It has taken me two years to do this! Finally, I will get some rest.... (But the fuller truth is that in the early days of MO, when I posted this answer, my computer refused to show any tex output except with lots of dollar signs and \fully\verbose\tex\macros, and so at that time I composed all my entries in html. But I noticed that some of the asterisks didn't come out properly in this answer, which caused mathematical errors in how my answer appeared, and so I finally texified today.) –  Joel David Hamkins Jan 3 '12 at 23:35
add comment

You are going to run into issues because of oscilatory functions. For example, is x*(1+sin(x)) greater than or less than x in your order?

GH Hardy proposed solving this problem by defining the logarithmico-exponential functions. These are all the functions on the real line which can be defined starting with the identity and scalars and applying addition, subtraction, multiplication, division, exponentiation and logarithm; with the proviso that we are only allowed to take the logarithm of a function if it is eventually positive.

One of Hardy's main theorems is that every LE-function is either eventually positive, eventually negative or identically 0. So we can define a total order by f>g if f(x) - g(x) is eventually positive. Hardy then proposed studying a general function by studying the interval of LE-functions which are infinitely often greater than and infinitely often less than it.

Unfortunately, I don't know a good modern reference on this subject. Hardy's book is online, but with pages missing. I am told that the buzzword for modern work on this subject is "Hardy fields", but that is the limit of my knowledge.

share|improve this answer
    
The complete text of Orders of Infinity is available for dowload from archive.org/details/ordersofinfinity00harduoft –  Charles Stewart Jan 28 '10 at 10:56
add comment

I might be misremembering, but I believe the question of whether there is a cofinal totally ordered sequence of growth rates is independent of ZFC. It follows from CH (or more generally, Martin's Axiom) by a simple diagonalization argument, using the fact that for any countable set of growth rates, you can diagonalize them to get a growth rate which is faster than all of them. In any case, questions about the order structure of growth rates are highly set-theoretic in nature.

share|improve this answer
    
Yes, I think this is right, and I explain a bit more about some of it in my answer. –  Joel David Hamkins Feb 2 '10 at 4:35
add comment

Every totally ordered set naturally gives rise to a topology; the basis of the topology is the set of open intervals and open rays, just as in the order definition of the topology on R. See the Wikipedia article.

On the other hand, what you can say about this particular order probably depends on how strong you allow your axioms to be.

share|improve this answer
    
By the way, this order doesn't have the least upper bound property, so my guess is that no bounded nonconstant monotonic sequence converges. –  Qiaochu Yuan Oct 28 '09 at 14:27
    
isn't the original question allowing partial order and not just total (linear) order? –  Yemon Choi Oct 28 '09 at 18:11
    
Partial orders have a topology with exactly the same construction. But my understanding of the intent of the question is that he wanted to define "growth rate" in such a way that a total order was obtained. –  Qiaochu Yuan Oct 28 '09 at 18:21
add comment

Then there are transseries.

How about a plug ... "Transseries for Beginners"

share|improve this answer
2  
Pages 19-22 look particularly relevant. –  David Speyer Oct 28 '09 at 18:45
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.