  Several air shower observatories have established that the number of muons
produced in UHE air showers is significantly larger than that predicted by
models. We argue that the only solution to this muon deficit, compatible with
the observed Xmax distributions, is to reduce the transfer of energy from the
hadronic shower into the EM shower, by reducing the production or decay of
pi0s. We present four different models of new physics, each with a theoretical
rationale, which can accomplish this. One has a pure proton composition and
three have mixed composition. Two entail new particle physics and suppress pi0
production or decay above LHC energies. The other two are less radical but
nonetheless require significant modifications to existing hadron production
models -- in one the changes are only above LHC energies and in the other the
changes extend to much lower energies. We show that the models have
distinctively different predictions for the correlation between the number of
muons at ground and Xmax in hybrid events, so that with future hybrid data it
should be possible to discriminate between models of new physics and
disentangle the particle physics from composition.
