What is the smallest $\mathbb{Z}[x]$ multiple of $(x-1)^n$ in the coefficient vector $\ell_1$ sense?

Question

Define a norm $\lVert p \rVert_1$ for $p\in \mathbb{Z}[x]$ as the sum of absolute values of the coefficients of $p$, as expressed in the ordinary monomial basis. What is the smallest norm of a polynomial divisible by $(x-1)^n$?

Equivalently, what is the smallest (in $\ell_1$ sense) integer relation among the values at integer arguments of all polynomials of degree at most $n-1$? That is, suppose $c_k \in \mathbb{Z}$ satisfy $\sum_{k=0}^\infty c_k f(k) = 0$ for all $f\in \mathbb{R}[x]$ of degree at most $n-1$. What is the smallest choice of such $c_k$ in the $\ell_1$ sense?

The equivalence of the two questions can be seen as such choices of $c_k$ are exactly those for which $\sum_k c_k x^k$ are divisible by $(x-1)^n$.

If this question is easier with some other norm, perhaps $\ell_2$, this would also be of interest. Lower bounds and asymptotics in $n$ are also of interest to me.

Using LLL basis reduction to look for short vectors in the appropriate lattice, one can make some guesses for this minimum, and at least provide upper bounds for small $n$. Doing this, one finds all solutions are products of factors of the form $x^k-1$, summarized below. The columns below are $n$, $\lVert p\rVert_1$, and set of $k$ for which $p=\prod_k x^k-1$

2 4 [1, 1]

3 6 [3, 2, 1]

4 8 [5, 3, 2, 1]

5 10 [7, 5, 3, 2, 1]

6 12 [7, 5, 4, 3, 2, 1]

7 16 [11, 7, 5, 4, 3, 2, 1]

8 20 [11, 9, 7, 5, 4, 3, 2, 1]

9 28 [11, 9, 7, 5, 4, 3, 2, 1, 1]

10 36 [9, 8, 7, 6, 5, 4, 3, 2, 1, 1]

11 44 [13, 11, 9, 8, 7, 6, 5, 4, 3, 2, 1]

12 44 [11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 1]

13 60 [13, 11, 9, 8, 7, 6, 5, 5, 4, 3, 2, 1, 1]

14 88 [11, 9, 8, 7, 6, 5, 5, 4, 4, 3, 3, 2, 1, 1]

15 88 [13, 11, 9, 8, 7, 7, 6, 5, 5, 4, 3, 3, 2, 2, 1, 1]

16 88 [13, 11, 9, 8, 7, 7, 6, 5, 5, 4, 3, 3, 2, 2, 1, 1]

17 106 [19, 13, 11, 9, 8, 7, 7, 6, 5, 5, 4, 3, 3, 2, 2, 1, 1]

18 140 [13, 11, 9, 8, 7, 7, 6, 5, 5, 4, 4, 3, 3, 2, 2, 1, 1, 1]

19 188 [13, 11, 10, 9, 8, 7, 7, 6, 5, 5, 4, 4, 3, 3, 2, 2, 1, 1, 1]

20 168 [17, 13, 11, 10, 9, 8, 7, 7, 6, 5, 5, 4, 4, 3, 3, 2, 2, 1, 1, 1]

Answer 1

This is the problem of "multigrade equations". Let $p(x)=\sum x^{a_i}-\sum x^{b_i}$ be a multiple of $(x-1)^n$, where the $a_i$ and $b_i$ are positive integers. Then $\sum a_i^k=\sum b_i^k$ for $k=0,1,\dots,n-1$. Conversely, if $\sum a_i^k=\sum b_i^k$ for $k=0,1,\dots,n-1$, then $\sum x^{a_i}-\sum x^{b_i}$ is a multiple of $(x-1)^n$. E.g., for the case $n=4$ in the table above, we have $$ (x^5-1)(x^3-1)(x^2-1)(x-1)=(x^{11}+x^7+x^4+x^0)-(x^{10}+x^9+x^2+x^1) $$ and $$ 11^k+7^k+4^k+0^k=10^k+9^k+2^k+1^k,\qquad k=0,1,2,3 $$ (for our purposes, $0^0=1$).

It's known that $p$ must have $\ell_1$-norm at least $2n$. The case of norm exactly $2n$ is called an "ideal multigrade." I think the current state of play is that ideal multigrades are known for $n\le10$ and for $n=12$ only. See https://mathworld.wolfram.com/Prouhet-Tarry-EscottProblem.html Estimates are known for larger values of $n$.

EDIT. Hardy and Wright, An Introduction to the Theory of Numbers, Sixth Edition, page 436, define $P(k,2)$ to be the least value of $s$ for which there exist integers $a_1,\dotsc,a_s$ and $b_1,\dotsc,b_s$ such that $\sum a_i^h=\sum b_i^h$ for $1\le h\le k$, omitting as trivial solutions where the $b_i$ are a permutation of the $a_i$. Their Theorem 409 implies $P(k,2)\le(1/2)k(k+1)+1$. The proof goes by the Pigeonhole Principle. The theorem is due to Wright, Bull Amer Math Soc 54 (1948) 755-7.