33
$\begingroup$

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 \le f_2$ if $f_1/f_2$ is bounded above.

So, in loose terms, does the sequence $x\log(1+x)$, $x\log(\log(10+x))$, $x\log(\log(\log(100+x)))$, ... converges 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).

$\endgroup$
1
  • 2
    $\begingroup$ The given sequence shouldn't converge to $x$, because there's some growth rate strictly in between. $\endgroup$
    – YCor
    Jul 30, 2023 at 7:34

6 Answers 6

22
$\begingroup$

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}\leq\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 in "Almost Disjoint Families and Diagonalizations of Length Continuum" 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.

$\endgroup$
8
  • $\begingroup$ I finally texified this entry. $\endgroup$ Jan 3, 2012 at 22:49
  • 1
    $\begingroup$ Joel, you will sleep better at night after this. $\endgroup$
    – Will Jagy
    Jan 3, 2012 at 23:14
  • 1
    $\begingroup$ Yes, I agree with that. My idea at the time was that the question seemed to call for mainly a brief general introduction to the area of cardinal characteristics and specifically the bounding number and the dominating number, since clearly that was the direction of his motivation. So I had just tried to do that. In 2010, there was very little cardinal characteristics on MO; I wouldn't necessarily answer this way today, now that we have many experts in this area. Why don't you post an answer explaining the equivalence with $\frak{b}=\frak{d}$? A sketch is better than a citation in my opinion. $\endgroup$ Apr 25, 2016 at 13:02
  • 1
    $\begingroup$ There may be an error in this definition of slalom that could be patched by changing each $(a_n,b_n)$ to $[a_n,b_n)$. Using the current definition, $f(x)=0$ does not correspond to any slalom, and Bartoszynski's fat slaloms ($s$ in which $\vert s(n)\vert=2^n$) here only have $\vert s(n)\vert\leq 2^n-1$. The meager set result may be stronger as well, in Bartoszynski it's stated as $g$ missing each slalom in $F$ in all but cofinitely many places, as opposed to eventually missing each slalom in $F$ (i.e. missing in infinitely many places, without the cofiniteness requirement) $\endgroup$
    – C7X
    Jul 30, 2023 at 2:44
  • 1
    $\begingroup$ @C7X Good catch. I have edited. And thanks for your recent edits on this question and several other of my questions. Much appreciated! $\endgroup$ Jul 30, 2023 at 2:48
21
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Some one ought to vote this up. (I already have.) The reference to Rosenlicht's work looks very useful, and extends my answer. $\endgroup$ Oct 28, 2009 at 17:40
  • 1
    $\begingroup$ Bourbaki has a nice treatment of Hardy fields in his Volume 4 (Functions of a real variable). $\endgroup$ Oct 28, 2009 at 18:00
12
$\begingroup$

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.

$\endgroup$
1
7
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Yes, I think this is right, and I explain a bit more about some of it in my answer. $\endgroup$ Feb 2, 2010 at 4:35
4
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ By the way, this order doesn't have the least upper bound property, so my guess is that no bounded nonconstant monotonic sequence converges. $\endgroup$ Oct 28, 2009 at 14:27
  • $\begingroup$ isn't the original question allowing partial order and not just total (linear) order? $\endgroup$
    – Yemon Choi
    Oct 28, 2009 at 18:11
  • $\begingroup$ 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. $\endgroup$ Oct 28, 2009 at 18:21
3
$\begingroup$

Then there are transseries.

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

$\endgroup$
1
  • 2
    $\begingroup$ Pages 19-22 look particularly relevant. $\endgroup$ Oct 28, 2009 at 18:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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