Big Oh notation ambiguity

146 Views Asked by At

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?