For given $n$, how to find integers $a_0, ..., a_n$ so that $\sum_{k=0}^n a_k x^k$ has $n$ distinct real roots and $\sum_{k=0}^n |a_k|$ is minimized?

Question

For a given value of $n$, how can we find integers $a_0, ..., a_n$ so that $\sum\limits_{k=0}^n a_k x^k$ has $n$ distinct real roots and $S=\sum\limits_{k=0}^n |a_k|$ is minimized?

For the first few smallest values of $n$, I have tried to find the coefficients by trial and error. These polynomials have $n$ distinct real roots, but I'm not sure if $S$ is minimized.

$n=1: x, S=1$
$n=2: x^2-1$ or $x^2-x, S=2$
$n=3: x^3-x, S=2$
$n=4: x^4-2x^2+x, S=4$
$n=5: x^5-3x^3+x, S=5$
$n=6: x^6-4x^4+3x^2-x, S=9$
$n=7: x^7-4x^5+4x^3-x, S=10$
$n=8: x^8-6x^6+10x^4-4x^2+x, S=22$
$n=9: x^9-7x^7+13x^5-7x^3+x, S=29$

EDIT

From the comments:

@Xiangxiang Xu verified my conjectured results up to $n=7$ using a Python program.

@Peter Košinár found a smaller $S$ for $n=8: x^8 - 3x^7 - x^6 + 7x^5 - 5x^3 + x, S=18$.

@Xiangxiang Xu found a smaller $S$ for $n=9: x^9-7x^7+11x^5-6x^3+x, S=26$.

Answer 1

Just an observation: For $n = 1 \mod 4$, the solutions you have listed are of the form: if $+r$ is a root then $-r$ is also a root. $0$ is a root. if $r$ is a root, then $1/r$ is also a root.

So try out: $$f(x) = x \prod_{i=1}^{n-1} (x-r_i) (x+r_i) (x+1/r_i) (x-1/r_i)$$.

Answer 2

Not an answer, but a list of partial observations and conjectures:

Properties (can be easily proved)

1. If $\displaystyle p_n(x) = \sum_{k = 0}^n a_k x^k$ is optimal, then $a_0^2 + a_1^2 > 0$.
2. If $\displaystyle p_n(x) = \sum_{k = 0}^n a_k x^k$ is optimal, then $\displaystyle p_n(-x) = \sum_{k = 0}^n (-1)^ka_k x^k$ is also optimal.
3. If $\displaystyle p_n(x) = \sum_{k = 0}^n a_k x^k$ is optimal and $a_0 = 0$, then $\displaystyle p_n(x^{-1})x^{n-1} = \sum_{k = 1}^n a_{n+1-k} x^k$ is also optimal for degree $n$.

---

Conjectures for $n > 2$

• The optimal polynomial $\displaystyle p_n(x) = \sum_{k = 0}^n a_k x^k$ satisfies $a_0 = 0$.
• If $n$ is odd, then we have $p_n(x) = x \cdot q_{\frac{n-1}{2}}(x^2)$, where $q_k(x)$ is an interger polynomial of degree $k$ that has $k$ distinct positive roots with the minimum $\ell_1$-norm.
• If $n$ is even, then we have $p_n(x) = x \cdot r_{n-1}(x)$, where $r_k(x)$ is an integer polynomial of degree $k$ that has $k$ distinct non-zero real roots with the minimum $\ell_1$-norm.

where we have defined the $\ell_1$-norm of $\displaystyle\sum_{k = 0}^n a_k x^k$ as $\displaystyle S = \sum_{k = 0}^n |a_k|$.