MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $X$ be a finite subset of $\mathbb R$ and let $f : X \to {\mathbb R}$. Suppose we want to approximate $f$ by a polynomial $g$ of fixed degree $d\geq 1$ with the additional condition $g\geq f$. Let

$$ S=\lbrace h : X \to {\mathbb R} | h \geq f, \ h {\rm\ is \ the \ restriction \ of \ a \ polynomial \ } g {\rm \ of \ degree \ } d\rbrace $$

We equip $S$ with the usual partial ordering ( $h_1 \leq h_2$ iff $h_1(x) \leq h_2(x)$ for all $x\in X$). Let $M(S)$ denote the set of minimal elements of $S$. Is it true that $M(S)$is always finite ? Also, is there an effective bound for $|M(S)|$ in terms of $d$ ?

When $d=1$, it seems that $|M(S)| \leq 3$ (this bound is attained when the graph of the function is a trapezium for example).

UPDATE : as noted in the comment below, $M(S)$ is not finite. But $S$ is convex, so the convex hull $C(M(S))$ of $M(S)$ is contained in $S$, and it seems that the set of extremal points in $C(M(S))$ (denote it by $E(S)$) is finite.

share|cite|improve this question
If $d=1$ and $X=\{-1,0,1\}$ and $f(x) = -x^2$ on these points, then aren't all $h_c$ minimal where $h_c(x) = cx, -1 \le c \le 1$? – Douglas Zare Oct 31 '11 at 9:59
@Douglas : you're absolutely right. Note that your family of examples is actually the convex hull between $h_{-1}$ and $h_1$, so perhaps looking at extremal elements inside those maximal elements yields a really finite set this time. – Ewan Delanoy Oct 31 '11 at 11:08
For every fixed $x\in X$, the requirement that $h(x)\ge f(x)$ is a linear inequality on the coefficients of $f$. So $S$ is a convex polyhedral set and therefore has finitely many extremal points. And $M(S)$ is the boundary of $S$. – Sergei Ivanov Oct 31 '11 at 11:20

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.