0
$\begingroup$

Let $P(k)$ and $Q(k)$ be two polynomials ($k>0$). Let $\mathrm{neg}(k)$ be a negligible function for sufficiently large $k$ (see Appendix on question for definition).

Does someone know how to show that $$ \left(1 - \frac{1}{Q(k)}\right)^{P(k)} \leq \mathrm{neg}(k) $$

It seems to me that it should be obvious/intuitive that its less than or equal to something similar to:

$$ \frac{1}{Q(k)^{P(k)}} \text{or} \frac{1}{e^{P(k)}} $$

(which if true, I believe it satisfies my requirement that is negligible).

Appendix:

Definition of negligible function according cryptography notes by Goldwasser and Bellare 2008:

$$ \mathrm{neg}(k) < k^{-c} \ , \forall{c} \geq 0, \exists{k_{0}} \ \mathrm{s.t.} \ k>k_{0} $$

In words, $\mathrm{neg}(k)$ is negligible if its less than $k^{-c}$ for every constant $c \geq 0$ for sufficiently large k (i.e. there exists a $k_{0}$ such that $k \geq k_0$).

A good example of a "negligible" function is the reciprocal of an exponential function:

$$ \frac{1}{e^{-k}} $$

$\endgroup$
3
  • 1
    $\begingroup$ Is a "negligible function" a function which tends to zero? $\endgroup$ Jan 4, 2014 at 7:00
  • $\begingroup$ To answer in an intuitive way; a function is negligible if it tends to zero faster than $k^{-c}$ does (as k goes to positive infinity). Or see edits to question. $\endgroup$ Jan 4, 2014 at 7:31
  • $\begingroup$ If $P(k)=Q(k)=k$, the expression converges to $e^{-1}$, so it clearly is not negligible. Do you have any additional conditions on the polynomials? $\endgroup$ Jan 4, 2014 at 9:51

1 Answer 1

2
$\begingroup$

The condition for negligiblity implies that the expression multiplied by $k^c$ (for any positive $c$) must converge to zero when $k$ goes to infinity:

$$\lim_{k\rightarrow\infty} k^c\left(1 - \frac{1}{Q(k)}\right)^{P(k)}=0$$

Assuming that neither of the polynomials is identically equal to zero, they both have only finitely many roots, so they'll eventually become strictly positive or strictly negative. Thus, we can write $$\lim_{k\rightarrow\infty} k^c\left(1 - \frac{1}{Q(k)}\right)^{P(k)} = \lim_{k\rightarrow\infty} k^c\left(1 - \frac{1}{Q(k)}\right)^{(-Q(k))\cdot (-P(k)/Q(k))}$$

Assuming that $Q(k)$ is not a constant, we have $|\lim\limits_{k\rightarrow\infty} Q(k)|=\infty$ (depending on the sign of its leading term, it can go to positive or negative infinity) and thus $$\lim_{k\rightarrow\infty} \left(1-\frac{1}{Q(k)}\right)^{-Q(k)}=e$$ so the full limit reduces to $$\lim_{k\rightarrow\infty} k^ce^{-P(k)/Q(k)}$$

Ratio of two polynomials can converge to a non-zero number (if their degrees are equal), to zero (if the "numerator" is of lower degree than denominator) or diverge to positive or negative infinity (if the "numerator" is of higher degree than denominator). In this case, only the positive infinity yields the desired result, so the degree of $P(k)$ must be greater than degree of $Q(k)$ and the leading coefficients of $P(k)$ and $Q(k)$ must have the same sign.

As it turns out, the same conclusion can be reached if $Q(k)$ is a non-zero constant, but the reasoning is simpler: $\left(1-\frac{1}{Q(k)}\right)$ is a constant already, so we only need for $P(k)$ to go to suitably-signed infinity.

Note that most of this reasoning actually applies to any reasonable functions $P(k)$ and $Q(k)$, not just polynomials.

In order to finish the proof, it's sufficient to note that the exponential term goes to zero at least as fast as $e^{-k}$, which is faster than any polynomial $k^c$, so the whole limit goes to zero regardless of value of $c$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .