We use simulations of frictionless soft sphere packings to identify novel constitutive relations for linear elasticity near the jamming transition. By forcing packings at varying wavelengths, we directly access their transverse and longitudinal compliances. These are found to be wavelength dependent, in violation of conventional (local) linear elasticity. Crossovers in the compliances select characteristic length scales, which signify the appearance of nonlocal effects. Two of these length scales diverge as the pressure vanishes, indicating that critical effects near jamming control the breakdown of local elasticity. We expect these nonlocal constitutive relations to be applicable to a wide range of weakly jammed solids, including emulsions, foams, and granulates.