0
$\begingroup$

I have a doubt with the usage of the Big Oh notation. I made a toy example to explain it. Consider the following easy lemmas:

Lemma 1. If $(a_n)$ is a sequence of positive real numbers such that $a_n = n + O(1)$ for all $n \geq 1$, then $\tfrac1{x} \sum_{n \leq x} a_n = \tfrac1{2} x + O(1)$ for all $x \geq 1$.

Lemma 2. If $(a_n)$ is a sequence of positive real numbers such that $a_n = \mu n + O(1)$ for all $n \geq 1$, for some constant $\mu >0$, then $\tfrac1{x} \sum_{n \leq x} a_n = \tfrac{\mu}{2} x + O(1)$ for all $x \geq 1$.

Lemma 3. If $(a_n)$ is a sequence of positive real numbers such that $a_n = \mu n + O(1)$ for all $n \geq 1$, for some constant $\mu >0$, then $\tfrac1{x} \sum_{n \leq x} a_n = \tfrac{\mu}{2} x + O_\mu(1)$ for all $x \geq 1$.

I guess we all agree that Lemma 2 is sloppy, since the implied constant in the second Big Oh depends on $\mu$ and making that not explicit could lead to a mistake (for example if using Lemma 2 with several values of $\mu$). In this regard, Lemma 3 explicitly states that the error term is not uniform in $\mu$, writing $O_\mu$ instead of just $O$, so it leaves no space for ambiguity and it is strongly preferred to Lemma 2. My doubt is with Lemma 1: the implied constant in the second Big Oh depends on the implied constant in the first Big Oh, however this is stated in no way. Clearly, this is a trivial example, but in more complicated situations this dependence may go unnoticed and lead to the same kind of errors of the formulation of Lemma 2.

My question is: What is the standard way to make the statements of lemmas like Lemma 1 precise?

$\endgroup$
  • $\begingroup$ The whole point of using $O(\cdots)$ notation is to ignore the constants in those terms. It's perfectly reasonable to want information about those constants, but trying to tweak $O(\cdots)$ notation to fulfill that need isn't an optimal approach. $\endgroup$ – Antonio Vargas Apr 8 '17 at 20:46
  • $\begingroup$ @AntonioVargas The problem is that I do not see an approach avoiding Big Oh notation except for writing down all the constants explicitly, which is much more annoying in my opinion... $\endgroup$ – sercej Apr 8 '17 at 21:00
  • $\begingroup$ Did you forget an $x$ in Lemma 2? As for your doubt, in Lemma 2 there is no constant that works for all values of $\mu$. Therefore it is appropriate to use the parameterized big oh. But in Lemma 1 there is no $\mu$. (In fact, there is no parameter.) Hence, the parametrized big oh is out of place. $\endgroup$ – Fabio Somenzi Apr 8 '17 at 21:01
  • $\begingroup$ @FabioSomenzi Right, I forgot an $x$, thanks. I understand that in Lemma 1 there are no parameters. However, the implied constant in the second Big Oh depends on the implied constant in the first Big Oh. $\endgroup$ – sercej Apr 8 '17 at 21:19
  • $\begingroup$ And why is that a problem? By assumption there's a single constant that, for every $n$, bounds the error term of $a_n$. Therefore there's a constant that bounds the error term of the summation. The second constant obviously depends on the first, but in terms of big oh notation it doesn't make a difference. In the case of Lemma 2 the situation is different, because you want to make a claim that holds for all $\mu$ and you want to stress that, "for every $\mu$ there is a constant such that..." instead of, "there is a constant such that for every $\mu$." $\endgroup$ – Fabio Somenzi Apr 8 '17 at 21:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.