  The hypothesis of a discrete fabric of the universe--the "Planck scale"--is
always on stage, since it solves mathematical and conceptual problems in the
infinitely small. However, it clashes with special relativity, which is
designed for the continuum. Here we show how the clash can be overcome within a
discrete quantum theory where the evolution of fields is described by a quantum
cellular automaton. The reconciliation is achieved by defining the change of
observer as a change of representation of the dynamics, without any reference
to space-time. We use the relativity principle, i.e. the invariance of dynamics
under change of inertial observer, to identify a change of inertial frame with
a symmetry of the dynamics. We consider the full group of such symmetries, and
recover the usual Lorentz group in the relativistic regime of low energies,
while at the Planck scale the covariance is nonlinearly distorted.
