0
$\begingroup$

I frequently encountered theorems here and there, which claim to establish essentially sharp upper bounds for certain quantities. However, I am confused about what “essentially sharp” exactly means, because it is never spelled out explicitly.

My intuitive interpretation is the following. Suppose that a theorem gives an upper bound for a quantity in terms of some variables and constants. My interpretation of this estimate being essentially sharp is that one may find a different constant by which the upper bound can be tightened, but the functional form according to which variables and constants in the formula for this upper bound are interrelated cannot be improved.

For example, suppose that the upper bound is $C x^2$ for some constant $C>0$ and you may be able to find a better estimate $C' x^2$ for some $0<C'<C$, but the estimate $ C x^{2-a}$ will no longer be an upper bound for any $a>0$. Then, the estimate $C x^2$ can be said to be essentially sharp, because you cannot find another function of the class $x^a$ with $a>0$ (modulo a multiplicative constant) that provides a better estimate.

Is this interpretation correct?

$\endgroup$

1 Answer 1

3
$\begingroup$

In my experience, and I work on nonlinear PDEs, some colleagues speak of "essentially sharp" when they mean that an estimate is not sharp, but they feel that it is up to some small error. Of course it is almost impossible to formalize this, and quite often your interpretation is correct.

Sometimes, a theorem is "almost sharp" when it "almost" complements another negative theorem. For example, suppose that a problem is known to be solvable for the values of a parameter $\kappa \leq 1$. Then you prove that the problem is not solvable whenever $\kappa > 1+\varepsilon$, for any $\varepsilon>0$ fixed. You may not be able to deduce that the problem is solvable if and only if $k \leq 1$, but your non-existence result is "essentially (or almost) sharp".

$\endgroup$
3
  • $\begingroup$ You're saying that it's a semi-formal expression? That was my gut feeling, too. Referring back to my example, suppose you can give an upper bound on the quantity $f(x)$ depending on $x$ as $f(x)\leq C x^2$. If the situation described in my original question holds, you might say that this bound is essentially sharp. But observe that you can actually give a trivially better estimate: $f(x)$ itself, as $f(x)\leq f(x)$. What makes $C x^2$ an essentially sharp estimate is the implicit assumption that you are looking for functions in the class $D x^a$, where $D$ and $a$ are positive constants. $\endgroup$
    – triple_sec
    Sep 12, 2013 at 20:40
  • $\begingroup$ Therefore, what “essentially sharp” means always depends on the context of the class of functions you confine yourself to in looking for estimates. What has confused me is that this implicit assumption is often left unsaid. $\endgroup$
    – triple_sec
    Sep 12, 2013 at 20:42
  • $\begingroup$ I'd be curious to know if anybody working in algorithms could use the phrase to mean something like "computing any sharper bound is computationally hard" - i.e. "this bound is the tightest bound that's easy to compute". $\endgroup$ Dec 10, 2020 at 16:34

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.