  The class of gross substitutes (GS) set functions plays a central role in
Economics and Computer Science. GS belongs to the hierarchy of {\em complement
free} valuations introduced by Lehmann, Lehmann and Nisan, along with other
prominent classes: $GS \subsetneq Submodular \subsetneq XOS \subsetneq
Subadditive$. The GS class has always been more enigmatic than its counterpart
classes, both in its definition and in its relation to the other classes. For
example, while it is well understood how closely the Submodular, XOS and
Subadditive classes (point-wise) approximate one another, approximability of
these classes by GS remained wide open. In particular, the largest gap known
between Submodular and GS valuations was some constant ratio smaller than 2.
  Our main result is the existence of a submodular valuation (one that is also
budget additive) that cannot be approximated by GS within a ratio better than
$\Omega(\frac{\log m}{\log\log m})$, where $m$ is the number of items. En
route, we uncover a new symmetrization operation that preserves GS, which may
be of independent interest.
  We show that our main result is tight with respect to budget additive
valuations. However, whether GS approximates general submodular valuations
within a poly-logarithmic factor remains open, even in the special case of {\em
concave of GS} valuations (a subclass of Submodular containing budget
additive). For {\em concave of Rado} valuations (Rado is a significant subclass
of GS, containing, e.g., weighted matroid rank functions and OXS), we show
approximability by GS within an $O(\log^2m)$ factor.
