Twisted Galois stratification

We prove a direct image theorem stating that the direct image of a Galois formula by a morphism of difference schemes is equivalent to a Galois formula over fields with powers of Frobenius. As a consequence, we obtain an effective quantifier elimination procedure and a precise algebraic-geometric description of definable sets over fields with Frobenii in terms of twisted Galois formulae associated with finite Galois covers of difference schemes.