Property of negligible functions Suppose that $\mu(n)$ is a negligible function, which means that for every $c&gt;0$ there is some $N$ such that for all $n&gt;N$ it holds that $\mu(n)\leq n^{-c}$. 

Now, imagine that some encryption scheme, signature scheme, or some cryptographic primitive in general has an "error" (distinguishing error, forging error, etc.) of $\mu(n)$. 
Imagine that now I want to set up my primitive so that this error is no larger than $2^{-80}$.
If I had the explicit expression for $\mu(n)$ (which is likely to be the case if I read the security proof of the given primitive) then I would solve the inequality $\mu(n)\leq 2^{-80}$ for $n$.
In practice (even though this is not necessarily the case), negligible functions look pretty much like exponentials $2^{-n}$, so we know that this $n$ will be polynomial in $80$ and therefore it won't be too large.

Now think of the general case.
Suppose I want to find some $n$ such that $\mu(n)\leq 2^{-\kappa}$ for some $\kappa$, let's denote the minimum of such $n$'s by $n(\kappa)$.
We know that such value must exist simply because $\mu$ tends to zero as $n$ approaches infinity. 
Moreover, since $\mu$ is negligible, intuition on the definition says that $n(\kappa)$ shouldn't be too large in terms of $\kappa$ (e.g. if $\mu(n) = 2^{-n}$ then $n(\kappa) = \kappa$).
My question is: how do we actually prove this?

Here's my question, extracted from the motivation above:


  Let $\mu$ be a negligible function, and let $n(\kappa)$ be the smallest $n$ such that $\mu(n)\leq 2^{-\kappa}$.
  Prove that $n(\kappa)$ does not grow too fast as $\kappa\to\infty$.


Part of the question requires to specify precisely what is meant by "too fast". 
I would love some statement like "$n(\kappa)$ is polynomial in $\kappa$", but I'm not sure how to prove this.

I believe this property is important as this is one of the reasons why we choose negligible functions (besides being closed on additions and multiplication by polynomials): it allows us to get small error probabilities without increasing the security parameter too much.

Any insights on this are welcome.
The function $n^{-\log(n)}=2^{-\log(n)^2}$ is negligible, but $n(\kappa)$ for it is $2^{\sqrt{\kappa}}$ which is not polynomial in $\kappa$.

If we look at the functions $\mu_c(n)=n^c$, their $n_c(\kappa)$ is $2^\frac{\kappa}{c}$, so if $\mu$ is negligible, its $n(\kappa)$ must be smaller than those (at least for big enough $\kappa$, this is ok since you asked for the asymptotics). This means that $n(\kappa)$ is subexponential, i.e., $n(\kappa)=2^{o(\kappa)}$.