If G is a finite (multiplicitively written) Abelian group, a set of elements B_G = {g₁, . . . , g_q} is called a basis of G if G is the product of the cyclic groups generated by g₁, . . . , g_q: G = бg₁с× . . . × бg_qс. Circuits for functional elements of multiplication, which for any two elements of G as input realize their product, are studied. The total number of elements of multiplication in such a circuit S is called the complexity L(S) of S. The complexity of any finite abelian group G in the basis B_G is defined as L(G, B_G) = max_g∈G min_S L(S), where the S are the circuits in the basis B_G that realize g. The paper gives proofs of the following estimates as |G| → ∞:
L(G,B_G) = (log₂|G| / log₂log₂|G|) (1+O(√ (log₂log₂log₂|G| / log₂log₂|G|))) +O(p+|B_G|) where p is the largest order of a basis element in B_G; and L(n) = log₂n + (1 + o(1))(log₂n / log₂log₂n) for the corresponding Shannon function L(n) = max_G:|G|=nmin_BGL(G,B_G). En route, some estimates on the complexity of certain auxiliary binary step matrices by gate circuits (rectifier networks) are established.

finite Abelian group, gate circuit (rectifier network), circuit complexity, complexity of group, Shannon function

Mathematical problems and theory of numerical methods