可忽略函式的極限定義
我正在閱讀 Dan Boneh 的書，我被困在定理 2.11 上，其證明留作練習。
問題是：證明如果 $ \lim_{n \rightarrow \infty} f(n)n^c = 0 $ 對所有人 $ c > 0 $ ， 然後 $ f $ 可以忽略不計。
在這裡，可忽略的函式被定義為一個函式 $ f : \mathbb{Z}_{\geq 1} \rightarrow \mathbb{R} $ 這樣對於任何真實的 $ c > 0 $ , 存在一個整數 $ n_0 \geq 1 $ 這樣 $ f(n) < \frac{1}{n^c} $ 為人 $ n \geq n_0 $ .
到目前為止，我所做的如下：假設，對於任何真實的 $ c > 0 $ ， 我們有 $ \lim_{n \rightarrow \infty} f(n)n^c = 0 $ . 看到這意味著 $ \lim_{n \rightarrow \infty} f(n)n^{c+1} = 0 $ 也是。注意 $ \frac{1}{n} = \frac{1}{n^{c+1}}n^c $ ， 所以 $ \lim_{n \rightarrow \infty} \frac{1}{n^{c+1}}n^c = \lim_{n \rightarrow \infty} f(n)n^c = 0 $ ， 所以 $ f(n)n^c < \frac{1}{n^{c+1}}n^c $ 最後 $ f(n) < \frac{1}{n^{c+1}} $ ，如我們所願。
這個對嗎？如果是這樣，如何證明說的部分 $ f(n)n^c < \frac{1}{n^{c+1}}n^c $ ?
假設對於任何 $ c>0, $ 我們有 $$ \lim_{n \rightarrow \infty} f(n)n^{c} = 0. $$這意味著對於任何 $ \epsilon>0 $ 無論多麼小，都存在一些有限的 $ N $ 這樣對所有人 $ n>N, $ 我們有 $ f(n) n^c \leq \epsilon. $ 這是標準 $ \epsilon $ 分析極限的定義（如果你走得足夠遠，你就會任意接近，即 $ \epsilon $ -接近極限點，這裡等於零）。
請注意，這直接意味著除法 $$ f(n) \leq \frac{\epsilon}{n^c}, \quad \forall n>N $$ 也是。自從 $ \epsilon>0 $ 是任意的，我們可以認為它在 $ (0,1) $ 我們完成了。
筆記：
你的假設太強了，不需要 $ f(n)<1/n, $ 為了收斂，可以有 $ f(n)<1/g(n) $ 對於任何增長的功能 $ g(n) $ 不管它增長得多麼緩慢。此外，在這裡我們通常可以假設 $ f(n) $ 是一個正函式，否則可能需要使用絕對值，但在密碼學中，函式通常是正的。