At low densities, the standard ionization history of the intergalactic medium (IGM) predicts a decreasing temperature of the IGM with decreasing density once hydrogen (and helium) reionization is complete. Heating the high-redshift, low-density IGM above the temperature expected from photoheating is difficult, and previous claims of high/rising temperatures in lowdensity regions of the Universe based on the probability density function (PDF) of the opacity in Ly $\alpha$ forest data at 2 < $z$ < 4 have been met with considerable scepticism, particularly since they appear to be in tension with other constraints on the temperature–density relation (TDR). We utilize here an ultrahigh signal-to-noise spectrum of the Quasi-stellar object HE0940-1050 and a novel technique to study the low opacity part of the PDF. We show that there is indeed evidence (at 90 per cent confidence level) that a significant volume fraction of the underdense regions at $z$ ~ 3 has temperatures as high or higher than those at densities comparable to the mean and above. We further demonstrate that this conclusion is nevertheless consistent with measurements of a slope of the TDR in overdense regions that imply a decreasing temperature with decreasing density, as expected if photoheating of ionized hydrogen is the dominant heating process. We briefly discuss implications of our findings for the need to invoke either spatial temperature fluctuations, as expected during helium reionization, or additional processes that heat a significant volume fraction of the low-density IGM.