We study the space of all kinematically allowed four photon and four graviton S-matrices, polynomial in scattering momenta. We demonstrate that this space is the permutation invariant sector of a module over the ring of polynomials of the Mandelstam invariants $s$, $t$ and $u$. We construct these modules for every value of the spacetime dimension $D$, and so explicitly count and parameterize the most general four photon and four graviton S-matrix at any given derivative order. We also explicitly list the local Lagrangians that give rise to these S-matrices. We then conjecture that the Regge growth of S-matrices in all physically acceptable classical theories is bounded by $s^2$ at fixed $t$. A four parameter subset of the polynomial photon S-matrices constructed above satisfies this Regge criterion. For gravitons, on the other hand, no polynomial addition to the Einstein S-matrix obeys this bound for $D leq 6$. For $D geq 7$ there is a single six derivative polynomial Lagrangian consistent with our conjectured Regge growth bound. Our conjecture thus implies that the Einstein four graviton S-matrix does not admit any physically acceptable polynomial modifications for $Dleq 6$. A preliminary analysis also suggests that every finite sum of pole exchange contributions to four graviton scattering also such violates our conjectured Regge growth bound, at least when $Dleq 6$, even when the exchanged particles have low spin.