Undecidability of some elementary theories over PAC fields (Q1074575)

We consider the theory of the field \(\tilde Q\) of algebraic numbers equipped with \(n\geq 2\) automorphisms \(\sigma_ 1,...,\sigma_ n\). We show that with probability 1 (in the sense of Haar measure on Gal\((\tilde Q/Q))\) this theory has the complexity of arithmetic. We use torsion points on elliptic curves to encode finite sets. The methods work also in nonzero characteristic.