Isomorphism in expanding families of indistinguishable groups. (Q2905578)

The goal of the paper under review is to ``produce a family of groups each of size \(p^n\) that have \(p^{O(n^2)}\) different isomorphism types, but for which no obvious isomorphism invariant presents itself to distinguish a pair of groups from the family.'' Here \(p>2\) is a prime, and the authors refer to the habitual practice of trying and distinguish non-isomorphic groups (of the same order) on the basis of suitable invariants, such as the number and order of the conjugacy classes.NEWLINENEWLINE The groups in questions are quotients of a Heisenberg group of order \(p^{5n/4+\Theta(1)}\), which belong to \(p^{n^2/24+\Theta(n)}\) different isomorphism types. All these groups have exponent \(p\), share the same character table, and have conjugacy classes of non-central elements of the same order. Despite this, the authors are able to produce a polynomial time algorithm that, given two of these groups as input, either exhibits an isomorphism between them, or returns that no such isomorphism exists. The authors refer to the latter occurrence as a ``zero-knowledge'' proof, in that non-isomorphism is only proved by ``exhausting all possible functions''.NEWLINENEWLINE Since the groups under study have nilpotence class \(2\), bilinear maps and tensor products naturally enter the scene, and so do rings with involutions. There is also a connection to Camina groups. For these and further details, we refer to the clearly written paper.