It has been recently observed that small violations of Lorentz invariance,
of a type which may arise in quantum gravity, could explain both the observ
ations of cosmic rays above the GZK cutoff and the observations of 20-TeV g
amma rays from Markarian 501. We show here that different pictures of the s
hort-distance structure of space-time would lead to different forms of viol
ation of ordinary Lorentz invariance. In particular, even space-time models
leading to the same deformed dispersion relation, the only aspect of Loren
tz-invariance violation considered in most recent studies, can lead to very
different predictions for the physics of cosmic rays and high-energy gamma
rays. This could provide an unexpected window on the (possibly quantum) na
ture of space-time at very short distances. (C) 2001 Elsevier Science B.V.
All rights reserved.