0

Recently I've been working through The Probabilistic Method by Alon and Spencer, and I've noticed that almost everywhere results (specifically bounds) are given using asymptotic notation. Here are some examples:

On page 10 (Theorem 1.3.2), we bound a function $m(n)$ as follows: $$m(n) < (1 + o(1)) \frac{e \ln 2}{4} n^2 2^n$$

On page 26 (Theorem 2.5.1), we bound a function $R(n)$: $$R(n) \ge \left( \sqrt{\frac{2}{\pi}} + o(1) \right)n^{3/2}$$

To my understanding the embedded $o(1)$'s mean that, take the second example, $R(n)$ is greater than the expression on the right when you replace the $o(1)$ with a function of $n$, call it $g(n)$, where $g(n) = o(1)$. (I.e., $\lim_{n \rightarrow \infty} g(n) = 0$.) My question is: how is a bound such as this actually useful? To me, it seems like the $o(1)$ is a hole in our bound that prevents it from being useful. For example, if I want to find a lower bound for $R(5)$ using the expression, I'm not sure how I would actually do that since I can't just plug in $n = 5$.

My intuition goes even more haywire when you have something other than 1 in there, like in $$f(n) = n^2 + n + o(\ln n)$$

Or in one example in the book (Theorem 2.2.3), it says there exists a set of size $$m = \Theta((\ln n)^{1/(k-1)}$$

I don't see how this could possibly be helpful since, say $m =a \cdot \Theta((\ln n)^{1/(k-1)}$ for some $a$, the constant $a$ could be arbitrarily large! It is just that bounds such as these are useful for deriving other important (perhaps more advanced) results? Or can I actually plug in numbers somehow? I'm used to thinking in terms of strict equalities and "plug things in," so any intuition would be much appreciated!

kanso37
  • 358
  • What is $R(n)$ and what prevents you from using other facts to compute $R(5)$? What is $m$? What are any of the other things? It makes it much more difficult to say what use it might be to have an expression relating these things to some asymptotic notation when we don't know what they are. – David K Dec 16 '19 at 02:33
  • @DavidK If we have a matrix $A$ where $a_{ij} = \pm 1$ for $1 \le i,j \le n$ then there exist $x_i, y_i = \pm 1$, $1 \le i,j \le n$ such that $$R(n) = \sum_{i=1}^n \sum_{j=1}^n a_{ij} x_i y_j \ge \left( \sqrt{\frac{2}{\pi}} + o(1) \right) n^{3/2}$$ – kanso37 Dec 17 '19 at 00:21
  • @DavidK As for $m$: It is known that, given any coloring with two colors of the $k$-subsets of a set of size $n$ (of course, $k \le n$), there exist $k$ disjoint subsets of size $m$ where $m = \Theta((\ln n)^\frac{1}{k-1})$ such that all $k$-subsets that cross the size $m$ subsets are the same color. The other examples I just made up but are similar in form to ones I've seen in the text. As you can see, most examples relate to the existence of something. – kanso37 Dec 17 '19 at 00:31
  • OK, I was hoping that someone might be familiar with one or both of the applications and be able to give specific ideas about why those particular forms are useful. I honestly don't know what the point of the $o(1)$ term in the $R(n)$ inequality is for unless it happens to be negative, but someone else might know. Putting the definitions in the question itself is more likely to get the attention of someone like that. – David K Dec 17 '19 at 01:25

1 Answers1

1

Think about the harmonic series, which can be approximated by $$H_n \approx \ln(n) + \gamma$$ Where $\gamma$ is the Euler Mascheroni constant. However, $$H_n > \ln(n) + \gamma$$ For all $n$. So if we want something that is always true we might say $$H_n = \ln(n) + \gamma + O\left(\frac{1}{2n}\right)$$ Which means we have turned our inequality into an equivalency by adding an error term that is at worst $\dfrac{1}{2n}$ which tells us more about the function we are analyzing since $$\lim_{n \rightarrow \infty} \frac{1}{2n} = 0$$ so we can say, $$\lim_{n \rightarrow \infty} H_n = \lim_{n \rightarrow \infty} \left(\ln(n) + \gamma\right).$$

an4s
  • 3,716
Ty Jensen
  • 1,516
  • I see. So you should think of it as an error term, and the error gets smaller and smaller as $n \rightarrow \infty$. But when you go to approximate the $H_n$ with an actual value you don't actually substitute the $O(\frac{1}{2n})$ in for anything since you don't know what it is. Thanks! – kanso37 Dec 17 '19 at 00:14