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$
$\endgroup$
4
-
$\begingroup$ en.wikipedia.org/wiki/… $\endgroup$– Joey EremondiCommented Sep 13, 2018 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$– CCOthersCommented Sep 13, 2018 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$– Joey EremondiCommented Sep 13, 2018 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 RicherbyCommented Sep 14, 2018 at 13:47
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
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
\epsilonfor $\epsilon$ and\varepsilonfor $\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$ Commented Sep 14, 2018 at 13:45
$\begingroup$
$\endgroup$
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.
