The aim of this paper is to describe, in as much detail as possible and constructively, the structure of the algebra of differential invariants of a Lie pseudo-group acting on the submanifolds of an analytic manifold. Under the assumption of local freeness of a suitably high order prolongation of the pseudo-group action, we develop computational algorithms for locating a finite generating set of differential invariants, a complete system of recurrence relations for the differentiated invariants, and a finite system of generating differential syzygies among the generating differential invariants. In particular, if the pseudo-group acts transitively on the base manifold, then the algebra of differential invariants is shown to form a rational differential algebra with non-commuting derivations. The essential features of the differential invariant algebra are prescribed by a pair of commutative algebraic modules: the usual symbol module associated with the infinitesimal determining system of the pseudo-group, and a new “prolonged symbol module” constructed from the symbols of the annihilators of the prolonged pseudo-group generators. Modulo low order complications, the generating differential invariants and differential syzygies are in one-to-one correspondence with the algebraic generators and syzygies of an invariantized version of the prolonged symbol module. Our algorithms and proofs are all constructive, and rely on combining the moving frame approach developed in earlier papers with Grobner basis algorithms from commutative algebra.
