  The relationship between galaxy and matter overdensities, bias, is most often
assumed to be local. This is however unstable under time evolution, we provide
proofs under several sets of assumptions. In the simplest model galaxies are
created locally and linearly biased at a single time, and subsequently move
with the matter (no velocity bias) conserving their comoving number density (no
merging). We show that, after this formation time, the bias becomes unavoidably
non-local and non-linear at large scales. We identify the non-local
gravitationally induced fields in which the galaxy overdensity can be expanded,
showing that they can be constructed out of the invariants of the deformation
tensor (Galileons). In addition, we show that this result persists if we
include an arbitrary evolution of the comoving number density of tracers. We
then include velocity bias, and show that new contributions appear, a dipole
field being the signature at second order. We test these predictions by
studying the dependence of halo overdensities in cells of fixed matter density:
measurements in simulations show that departures from the mean bias relation
are strongly correlated with the non-local gravitationally induced fields
identified by our formalism. The effects on non-local bias seen in the
simulations are most important for the most biased halos, as expected from our
predictions. The non-locality seen in the simulations is not fully captured by
assuming local bias in Lagrangian space. Accounting for these effects when
modeling galaxy bias is essential for correctly describing the dependence on
triangle shape of the galaxy bispectrum, and hence constraining cosmological
parameters and primordial non-Gaussianity. We show that using our formalism we
remove an important systematic in the determination of bias parameters from the
galaxy bispectrum, particularly for luminous galaxies. (abridged)
