  An $(m,n,a,b)$-tensor code consists of $m\times n$ matrices whose columns
satisfy `$a$' parity checks and rows satisfy `$b$' parity checks (i.e., a
tensor code is the tensor product of a column code and row code). Tensor codes
are useful in distributed storage because a single erasure can be corrected
quickly either by reading its row or column. Maximally Recoverable (MR) Tensor
Codes, introduced by Gopalan et al., are tensor codes which can correct every
erasure pattern that is information theoretically possible to correct. The main
questions about MR Tensor Codes are characterizing which erasure patterns are
correctable and obtaining explicit constructions over small fields.
  In this paper, we study the important special case when $a=1$, i.e., the
columns satisfy a single parity check equation. We introduce the notion of
higher order MDS codes (MDS$(\ell)$ codes) which is an interesting
generalization of the well-known MDS codes, where $\ell$ captures the order of
genericity of points in a low-dimensional space. We then prove that a tensor
code with $a=1$ is MR iff the row code is an MDS$(m)$ code. We then show that
MDS$(m)$ codes satisfy some weak duality. Using this characterization and
duality, we prove that $(m,n,a=1,b)$-MR tensor codes require fields of size
$q=\Omega_{m,b}(n^{\min\{b,m\}-1})$. Our lower bound also extends to the
setting of $a>1$. We also give a deterministic polynomial time algorithm to
check if a given erasure pattern is correctable by the MR tensor code (when
$a=1$).
