A little computation is often a useful way to get insight into such questions. Fortunately, available open-source solvers can approximately solve a given instance of this problem with a few lines of code and in a second or less.

# Code

Here is a Python program that makes use of CVXOPT to find the polynomial of least deviation for a given $n$ and $d$. There is one important approximation here: it minimizes $p(x)$ only over a discrete set of points $x$. However, by taking a moderately fine grid of the desired interval, reasonably accurate values are obtained.

```
import numpy as np
def find_min_poly(x, d, n):
from cvxopt import matrix
from cvxopt.modeling import variable, op, max
X = matrix(x)
y = np.empty( (len(x), d+2) )
y[:,0] = x**n
for i in range(d, -1, -1):
y[:, d+1-i] = x**i
Y = matrix(y)
c = variable(d+1)
op(max(abs(Y[:,0] + Y[:,1:]*c))).solve()
return c.value, max(abs((Y[:,0] + Y[:,1:]*c.value)))
```

Here is a nested loop that calls this for a range of $n,d$ values with
the interval $[-1,1]$:

```
x = np.linspace(-1,1,10000)
N = range(1,11)
maxabs = np.zeros( (len(N),len(N)) )
for n in N:
for d in range(n-1,-1,-1):
print n, d
coeffs, M = find_min_poly(x, d, n)
maxabs[d, n-1] = M
print M
print maxabs
```

You can download the code here.

One warning: for large enough values of $n,d$, this approach will give inaccurate results due to effects of roundoff errors.

# Results

Here is the resulting table of values (computed in a few seconds), truncated to 4 decimal places:

$$\begin{bmatrix}
1. & 0.5 & 1. & 0.5 & 1. & 0.5 & 1. & 0.5 & 1. & 0.5 \\
- & 0.5 & 0.25 & 0.5 & 0.32645& 0.5 & 0.36491& 0.5 & 0.38843& 0.5 \\
- & - & 0.25 & 0.125 & 0.32645& 0.19245& 0.36491& 0.23624& 0.38843& 0.2675 \\
- & - & - & 0.125 & 0.0625 & 0.19245& 0.11157& 0.23624& 0.14921& 0.2675 \\
- & - & - & - & 0.0625 & 0.03125& 0.11157& 0.06346& 0.14921& 0.09216 \\
- & - & - & - & - & 0.03125& 0.01562& 0.06346& 0.03559& 0.09216 \\
- & - & - & - & - & - & 0.01562& 0.00781& 0.03559& 0.01972 \\
- & - & - & - & - & - & - & 0.00781& 0.00391& 0.01972 \\
- & - & - & - & - & - & - & - & 0.00391& 0.00195 \\
- & - & - & - & - & - & - & - & - & 0.00195
\end{bmatrix}$$

The value of $n$ is 1 for the leftmost column and increases to the right (up to 10); the value of $d$ is 0 in the first row and increases downward. You can see the $1/2^{n-1}$ values, corresponding to the Chebyshev polynomials, along the main diagonal.

The code above also provides the coefficients of the optimal polynomial, of course.

# Conjectures

By experimenting and investigating these values, you may be able to conjecture the general behavior. For instance, it is obvious that the first superdiagonal is identical to the main diagonal; the 2nd and 3rd superdiagonals are identical, etc., apparently because the optimal polynomial has $a_d=0$ whenever $n-d$ is odd.

One might hope that the other diagonals exhibit geometric progressions like that of the Chebyshev polynomials, but examining the other diagonals shows this to be false. However, by computing a larger table of values with higher precision, one is led to conjecture that *asymptotically*, the ratio of consecutive values along any diagonal approaches two.