The Complexity of Identifying Finite Abelian Groups.
Walid E. Gomaa · Theoretical and Mathematical Foundations of Computer Science · 2008
We investigate the descriptive complexity of nite abelian groups. Using Ehrenfeucht-Frasse games we nd upper and lower bounds on quanti er depth, quanti er alternations, and number of variables of a rst-order sentence that distinguishes two nite abelian groups. Our main results are the following. Let G1 and G2 be a pair of non-isomorphic nite abelian groups, and let m be a number that divides exactly one of the two groups' orders. Then the following hold: (1) there exists a rst-order sentence φ that distinguishes G1 and G2 such that φ is existential, has quanti er depth O(log m), and has at most 5 variables and (2) if φ is a sentence that distinguishes G1 and G2 then φ must have quanti er depth Ω(log m). These results are applied to (1) get bounds on the rst-order distinguishability of dihedral groups, (2) to show the rst-order unde nability of some group-theoretic notions.