Minimizing the maximum of $|x^2 - x - k|$

Question

Let $k$ be a real number. Also, let $M(k)$ be the maximum value of $f(x) = |x^2 - x - k|$ in $0 \le x \le 1$. What are all real numbers $k$ which minimize $M(k)$?

Answer 1

Let $g(x)=x^2-x-k=(x-1/2)^2-k-1/4$. The graph of $g(x)$ is a parabola with the vertex at $(1/2, -k-1/4)$. Since $f(x)=|g(x)|$, the maximum of $f(x)$ at $[0,1]$ is attained when $x\in\{ 0,1/2,1\}$. We have $f(0)=f(1)=|k|$ and $f(1/2)=|k+1/4|$. So in order to minimize $M(k)$ we have to minimize $M’(k)=\max\{|k|, |k+1/4|\}$. It is easy to check that $M’(-1/8)=1/8$ and $M’(k)\ge 1/8$ for each $k$.

Answer 2

Let $\{T_n(x)\}$ be the Chebyshev polynomials of the first kind https://en.wikipedia.org/wiki/Chebyshev_polynomials.

Recall that for any given $n\ge 1$, among the polynomials of degree $n$ with leading coefficient $1$, $\frac{1}{2^{n-1}}T_n(x)$ is the one of which the maximal absolute value on $[-1, 1]$ is minimal which is equal to $\frac{1}{2^{n-1}}$. see "Minimal $\infty$-norm" https://en.wikipedia.org/wiki/Chebyshev_polynomials.

We have \begin{align} \max_{x \in [0, 1]} |x^2 - x - k| &= \max_{y \in [-1, 1]} |(\tfrac{y+1}{2})^2 - \tfrac{y+1}{2} - k|\\ &= \frac{1}{4} \max_{y \in [-1, 1]} |y^2 - 1 - 4k|\\ &\ge \frac{1}{4} \cdot \frac{1}{2^{2-1}}\\ &= \frac{1}{8}. \end{align} Also, $\frac{1}{8}$ is attainable at e.g. $k = -\frac{1}{8}$ (corresponding to $y^2 - 1 - 4k = \frac{1}{2} T_2(y) = y^2 - \frac{1}{2}$). We claim that $k = -1/8$ is the unique solution to $\max_{y \in [-1, 1]} |y^2 - 1 - 4k| = \frac{1}{2}$. Indeed, by letting $g(y) = |y^2 - 1 - 4k|$, from $g(0) \le 1/2$ and $g(1) \le 1/2$, we have $|1 + 4k|\le \frac{1}{2}$ and $|4k| \le 1/2$ which results in $k = -\frac{1}{8}$.