What are the necessary and sufficient conditions on a utility function for gross substitutes? What are the necessary and sufficient conditions on a utility function for gross substitutes? Gross substitutes is:

$$
  \frac{dx^*_i}{dp_j} \ge 0\ \ \forall_{i,j}\ i \ne j
$$
The paper @Henry referred to in comments pretty much answers this question. For closure, and to summarize the jist, the paper opens:


  As is very well known, the case in which all excess demands have the gross substitute property is one in which very strong results can be obtained concerning the uniqueness and stability of general equilibrium. Considering how long this has been known it is perhaps remarkable that we apparently do not possess a convenient characterization of the class of utility functions which yield individual demand functions with the gross substitute property. ... [This] note provides a characterization of the entire class of utility functions having the gross substitute property. Since the primary interest in that property is in the analysis of general equilibrium, we shall mainly concern ourselves with the demand functions which arise in a condition of exchange rather than with those that arise when income is fixed, independent of prices. The extension of the results to the latter case being given at the end of the paper.




The main result is, in an exchange market, for any initial endowments (quoting directly):

A necessary and sufficient condition for $U(x)$ to have GS is that for every $i, j = 1,...,n, j \ne i$, positive income $Y$, and strictly positive price vector $p$:

$$
  \eta_{ij} &gt; max(e_i, e_j, e_i(1 - \frac{1}{\alpha_j}), e_j(1 - \frac{1}{\alpha_i}))
$$

Where:


$e_i$ is the income elasticity of the i-th commodity, $\frac{\partial x_i}{\partial Y}/\frac{Y}{x_i}$.
$\alpha_i$ is the proportion of expenditure devoted to the i-th commodity, $\alpha_i = \frac{p_ix_i}{Y}$.
$\eta_{ij}$ is the elasticity of substitution i-th to j-th of the so called "Allen-Uzara" kind (what ever that is - see paper).


There are some corollaries.

The main complication with all this is you have to take income or rather income elasticity, into consideration. Some broad classes of utility functions that are sufficient for GS regardless, are only very briefly mentioned in the intro of paper.