We present a search for HCN emission from four high redshift far infrared ( IR ) luminous galaxies . Current data and models suggest that these high z IR luminous galaxies represent a major starburst phase in the formation of spheroidal galaxies , although many of the sources also host luminous active galactic nuclei ( AGN ) , such that a contribution to the dust heating by the AGN can not be precluded . HCN emission is a star formation indicator , tracing dense molecular hydrogen gas within star-forming molecular clouds ( n ( H _ { 2 } ) \sim 10 ^ { 5 } cm ^ { -3 } ) . HCN luminosity is linearly correlated with IR luminosity for low redshift galaxies , unlike CO emission which can also trace gas at much lower density . We report a marginal detection of HCN ( 1-0 ) emission from the z = 2.5832 QSO J1409+5628 , with a velocity integrated line luminosity of L _ { HCN } ^ { \prime } = 6.7 \pm 2.2 \times 10 ^ { 9 } K km s ^ { -1 } pc ^ { 2 } , while we obtain 3 \sigma upper limits to the HCN luminosity of the z = 3.200 QSO J0751+2716 of L _ { HCN } ^ { \prime } = 1.0 \times 10 ^ { 9 } K km s ^ { -1 } pc ^ { 2 } , L _ { HCN } ^ { \prime } = 1.6 \times 10 ^ { 9 } K km s ^ { -1 } pc ^ { 2 } for the z = 2.565 starburst galaxy J1401+0252 , and L _ { HCN } ^ { \prime } = 1.0 \times 10 ^ { 10 } K km s ^ { -1 } pc ^ { 2 } for the z = 6.42 QSO J1148+5251 . We compare the HCN data on these sources , plus three other high- z IR luminous galaxies , to observations of lower redshift star-forming galaxies . The values of the HCN/far-IR luminosity ratios ( or limits ) for all the high z sources are within the scatter of the relationship between HCN and far-IR emission for low z star-forming galaxies . These observations are consistent with dust heating by a massive starburst in these systems , with two important caveats . First , about half the measurements are strictly upper limits to the HCN luminosities . And second , the IR spectral energy distributions for most of the high z sources are well constrained only on the Rayleigh-Jeans side of the thermal dust peak . We also present a spatially resolved 42 GHz continuum image of the gravitational lens J0751+2716 .