  Higher order MDS codes are an interesting generalization of MDS codes
recently introduced by Brakensiek, Gopi and Makam (IEEE Trans. Inf. Theory
2022). In later works, they were shown to be intimately connected to optimally
list-decodable codes and maximally recoverable tensor codes. Therefore
(explicit) constructions of higher order MDS codes over small fields is an
important open problem. Higher order MDS codes are denoted by
$\operatorname{MDS}(\ell)$ where $\ell$ denotes the order of generality,
$\operatorname{MDS}(2)$ codes are equivalent to the usual MDS codes. The best
prior lower bound on the field size of an $(n,k)$-$\operatorname{MDS}(\ell)$
codes is $\Omega_\ell(n^{\ell-1})$, whereas the best known (non-explicit) upper
bound is $O_\ell(n^{k(\ell-1)})$ which is exponential in the dimension.
  In this work, we nearly close this exponential gap between upper and lower
bounds. We show that an $(n,k)$-$\operatorname{MDS}(3)$ codes requires a field
of size $\Omega_k(n^{k-1})$, which is close to the known upper bound. Using the
connection between higher order MDS codes and optimally list-decodable codes,
we show that even for a list size of 2, a code which meets the optimal
list-decoding Singleton bound requires exponential field size; this resolves an
open question from Shangguan and Tamo (STOC 2020).
  We also give explicit constructions of $(n,k)$-$\operatorname{MDS}(\ell)$
code over fields of size $n^{(\ell k)^{O(\ell k)}}$. The smallest non-trivial
case where we still do not have optimal constructions is
$(n,3)$-$\operatorname{MDS}(3)$. In this case, the known lower bound on the
field size is $\Omega(n^2)$ and the best known upper bounds are $O(n^5)$ for a
non-explicit construction and $O(n^{32})$ for an explicit construction. In this
paper, we give an explicit construction over fields of size $O(n^3)$ which
comes very close to being optimal.
