  Tropical geometry and its applications indicate a "theory of syzygies" over
polytope semirings. Taking cue from this indication, we study a notion of
syzygies over the polytope semiring. We begin our exploration with the concept
of Newton basis, an analogue of Gr\"obner basis that captures the image of an
ideal under the Newton polytope map. The image ${\rm New}(I)$ of a graded ideal
$I$ under the Newton polytope is a graded sub-semimodule of the polytope
semiring. Analogous to the Hilbert series, we define the notion of
Newton-Hilbert series that encodes the rank of each graded piece of ${\rm
New}(I)$. We prove the rationality of the Newton-Hilbert series for
sub-semimodules that satisfy a property analogous to Cohen-Macaulayness. We
define notions of regular sequence of polytopes and syzygies of polytopes. We
show an analogue of the Koszul property characterizing the syzygies of a
regular sequence of polytopes.
