  We are interested in finding nonlinear polynomials $P$ on $\mathbb{R}^n$ that
solves the minimal surface equation.
  We first prove a structure theorem on such polynomials. We show that the
highest degree term $P_m$ must factor as $P_0^kQ_m$ where $k$ is odd, $Q_m\ge
0$ on $\mathbb{R}^n$ and $P_0$ is irreducible, and that the level sets of $P_m$
are all area minimizing. Moreover, the unique tangent cone of
$\operatorname{graph} P$ at $\infty$ is $\{P_0=0\}\times\mathbb{R}$. If $k\ge
3$, we know further that lower order terms down to some degree are divisible by
$P_0$.
  We also show that $P$ must contain terms of both high and low degree. In
particular, it cannot be homogeneous. As a corollary, we prove that there is no
quadratic or cubic polynomial solution.
  Using a general decay lower bound of Green's functions on minimal
hypersurfaces we are able to show that $\operatorname{deg}
P_0+k^{-1}\operatorname{deg} Q_m\le n-2$.
  Finally, we prove that a polynomial minimal graph cannot have $C\times
\mathbb{R}^l$ as its tangent cone at $\infty$ where $l\ge 1$ and $C$ is any
isoparametric cone. We also show that the existence of a nonlinear polynomial
solutions on $\mathbb{R}^8$ will imply the existence of an area minimizing but
not strictly minimizing cubic cone in $\mathbb{R}^8$. These results indicate
that finding an explicit polynomial solution can be hard.
