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 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 parametrize 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 s2 at fixed t. In the case of photons a four parameter subset of the polynomial S-matrices constructed above satisfies this Regge criterion. In the case of gravity, on the other hand, no polynomial addition to the Einstein S-matrix obeys this bound for D ≤ 6. When D ≥ 7 there is a single six derivative polynomial Lagrangian consistent with our conjectured Regge growth bound. Our conjecture then implies that the Einstein four graviton S-matrix does not admit any physically acceptable polynomial modifications for $D\leq 6$. A preliminary analysis suggests any finite sum of pole exchange contributions to four graviton scattering also such violates our conjectured Regge growth bound, at least when D ≤ 6$, even when the exchanged particles have low spin.