I'm having troubles understanding the following proof: $$ \begin{align*} &\text{Proof: } \forall \epsilon \in \mathbb{R}^+, \forall a \in \mathbb{Z}^+, n^\epsilon \gg \log_a(n) \\ &\Longrightarrow \ln(a(n)) = \log_2(e)\ln^2(n) \ll n^{0.01} = \ln(d(n)) \\ &\Longrightarrow a(n) \ll d(n) \end{align*} $$ The topic is Big O comparisons. The proof is about $a(n)= n^{\log_2 n}$ and $d(n) = e^{n^{0.01}}$. The proof is very heavy in mathematical notation. I'm not sure what ∈ means in the example. I know that it denotes set membership in a more usual case, but have never seen it in the exponential position.

  • $\begingroup$ en.wikipedia.org/wiki/… $\endgroup$ – jmite Sep 13 '18 at 22:45
  • $\begingroup$ @jmite knowing that it is called set membership in a more usual case, but never seen it in the exponential position. $\endgroup$ – CCOthers Sep 13 '18 at 22:51
  • 1
    $\begingroup$ whoops, I only saw the $\in \mathbb{Z}$. That there is just $\epsilon$, the greek letter Epsilon. Like most symbols in math, it doesn't "mean" anything. Here it's just a placeholder for any positive real number. $\endgroup$ – jmite Sep 13 '18 at 22:57
  • $\begingroup$ @jmite Well, it would be very unusual for $\epsilon$ to be used for anything other than a positive real number in a context where "it's a positive real number" would make sense. Indeed, more strongly, it's usually a small positive real. That's a lot of meaning, really. $\endgroup$ – David Richerby Sep 14 '18 at 13:47

That's not $\in$ but $\epsilon$: that is, a lowercase Greek letter epsilon. It's normally written $\varepsilon$ instead for clarity, but this author chose to use the "lunate" form for unknown reasons.

In this case, epsilon is being used as a shorthand for "an arbitrarily small but positive real number". This should probably be explained in the proof, but it's a fairly common shorthand in mathematics (for example, delta-epsilon proofs, floating-point epsilon…).

In other words, it's saying that the log of $n$ is always asymptotically smaller than $n$ raised to any positive power. In the next line it substitutes in a definite value, 0.01, for epsilon.

  • $\begingroup$ The "unknown reason" is most likely simply that LaTeX uses \epsilon for $\epsilon$ and \varepsilon for $\varepsilon$, which is more typing. And, honestly, $\epsilon$ and $\in$ are plenty distinct enough -- you only need to be told once to know that they're not just "the same thing in different fonts." (Though, historically, $\varepsilon$ was also used for the set membership relation.) $\endgroup$ – David Richerby Sep 14 '18 at 13:45

It's a variable name, like any other. In your property you could rename it to (e.g.) $b$, turning $$\forall \epsilon \in \mathbb{R}^+, \forall a \in \mathbb{Z}^+, n^\epsilon \gg \log_a(n)$$ into $$\forall b \in \mathbb{R}^+, \forall a \in \mathbb{Z}^+, n^b \gg \log_a(n)$$

That's it.

Why calling it $\epsilon$, then, instead of a more common variable name?

In maths, it is common to call such variable $\epsilon$ when you could restrict its range to any positive interval $(0,x)$ with $x>0$ and get a completely equivalent statement, no matter how small the interval is. That is, instead of proving $\forall b \in \mathbb{R}^+$ we could only prove $\forall b \in (0,10^{-8})$ and that would be just as good. Indeed, once it is proven for the small interval, it's easy to extend the result to all positive reals.

In a nutshell it conveys the idea that "only small positive values actually matter".

This is a sort-of implicit statement which is suggested every time $\epsilon$ is used. You can safely neglect this "hint" to the reader, and take the statement as it is.


Your Answer

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

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