Let (F-n)(n is an element of N) be a sequence of non-decreasing functions from [0, +infinity) into [0, +infinity). Under some suitable hypotheses on (F-n)(n is an element of N), we prove that if g is an element of L-p(R-N), 1 < p < +infinity, satisfies [GRAPHICS] then g is an element of W-1,W- p(R-N) and moreover [GRAPHICS] where K-N, p is a positive constant depending only on N and p. This extends some results in J. Bourgain and H.-M. Nguyen [A new characterization of Sobolev spaces, C. R. Math. Acad. Sci. Paris 343, 75-80 (2006)] and H.-M. Nguyen [Some new characterizations of Sobolev spaces, J. Funct. Anal. 237, 689-720 (2006)]. We also present some partial results concerning the case p = 1 and various open problems.