Siblings and twins in finite p-groups and a group identification for the groups of order $2^9$

This paper introduces the concepts of "siblings" and "twins" to analyze the difficulty of distinguishing non-isomorphic p-groups, ultimately applying these insights to develop an effective algorithm for identifying all 10,494,213 groups of order $2^9$.

The Gist

Imagine you are a detective trying to identify people in a massive crowd. You have a giant database of 10 million people (groups), and your job is to look at a stranger and say, "Ah, you are Person #4,592,013."

Usually, this is easy. You check their height (group order), their job (abelian invariants), or how many friends they have (conjugacy classes). These "ID cards" work for almost everyone.

But in the world of Finite p-groups (a specific, complex type of mathematical structure), there are some people who are twins. They look exactly the same on every standard ID card. They have the same height, the same job, the same friends, and even the same family tree structure. If you only look at the basics, you can't tell them apart.

This paper by Bettina Eick and Henrik Schanze is about solving the mystery of these "mathematical twins" to finally identify every single one of the 10,494,213 groups of a specific size (order $2^9$).

Here is the breakdown of their investigation using simple analogies:

1. The Problem: The "Look-Alikes"

In the past, mathematicians had a tool (the SmallGroups Library) that could identify groups up to a certain size. But when they tried to identify the groups of order $2^9$ (about 10.5 million of them), the standard tools failed.

Why? Because there are groups that are indistinguishable using standard math tests.

• The Analogy: Imagine two identical twins, Bob and Rob. They have the same fingerprints, the same DNA, and the same voice. If you only check those, you can't tell them apart. You need a deeper test.

2. The New Tools: "Siblings" and "Twins"

The authors invented two new concepts to categorize these look-alikes:

• Siblings: These are groups that look the same when you check their internal structure (subgroups) and their external relationships (quotient groups).
  • Analogy: Siblings are like two houses that have the exact same floor plan, the same number of rooms, and the same view from the windows. If you walk inside or look outside, they seem identical.
• Twins: These are the ultimate look-alikes. They are "Siblings" plus they have the exact same character table (a complex mathematical map of their internal symmetries and power structures).
  • Analogy: Twins are like those houses, but they also have the exact same electrical wiring diagram and the same schedule of when the lights turn on. They are virtually indistinguishable without a full, expensive forensic audit.

The authors found that among the 10 million groups, there are 56 pairs of these "Twins." They are so similar that even advanced math tests struggle to tell them apart.

3. The Solution: The "Decision Tree" Detective

To identify all 10 million groups, the authors built a massive Decision Tree (like a "Choose Your Own Adventure" book, but for math).

• How it works: You start at the top with the whole crowd.
  • Step 1: "Are you tall or short?" (Checks basic invariants).
  • Step 2: "Do you have 3 friends or 4?" (Checks conjugacy classes).
  • Step 3: "What happens if you raise your friends to the 3rd power?" (Checks power maps).
• The Magic: By asking these questions in a specific order, the tree splits the crowd into smaller and smaller groups.
  • For 99.9% of the groups, the tree stops early because the answers are unique.
  • For the tricky "Twins," the tree goes deeper, using the new "Sibling" and "Twin" tests to separate them.

4. The Final Blow: The "Random Guess"

For the very last few pairs of groups that even the "Sibling" tests couldn't separate, the authors used a Random Isomorphism Test.

• The Analogy: Imagine you have two identical-looking keys. You can't tell them apart by looking. So, you try to open a thousand different random locks with them.
  • If Key A opens Lock #42 but Key B doesn't, you know they are different!
  • The computer does this millions of times in a split second. It generates random "keys" (mathematical representations) and sees if they fit the same "locks." If they behave differently even once, they are identified as different.

5. Why This Matters

Before this paper, the database of groups had a "blind spot" for groups of order $2^9$. It was like a library missing a whole section of books.

• The Result: They successfully created an algorithm that can now identify every single one of the 10,494,213 groups.
• The Discovery: They found that while most groups are unique, there are these rare, stubborn "Twins" that require very deep, complex analysis to distinguish.

Summary

Think of this paper as the ultimate ID Card Upgrade for the mathematical world.

1. They realized standard IDs weren't enough for the "Twins."
2. They invented new "Sibling" and "Twin" tests to spot the differences.
3. They built a giant flowchart (Decision Tree) to sort the crowd.
4. For the few remaining look-alikes, they used a "random lock-picking" trick to finally tell them apart.

Now, no matter which group of order $2^9$ you hand them, they can instantly tell you exactly who it is!

Technical Summary

Here is a detailed technical summary of the paper "Siblings and twins in finite p-groups and a group identification for the groups of order 29" by Bettina Eick and Henrik Schanze.

1. Problem Statement

The central problem addressed is the efficient identification of non-isomorphic finite $p$-groups. While the SmallGroups library provides a unique identifier (ID) for groups of small orders, it historically lacked an effective identification function for groups of order $2^9$(512) and$29$(a prime power$p^9$where$p=29$).

• The Challenge: Standard invariants (order, abelian invariants, conjugacy class counts) are often insufficient to distinguish between large clusters of non-isomorphic groups.
• The Specific Gap: While an identification algorithm existed for groups of order $2^8$(256) and$2^8$(256) is not the focus, the paper notes that order$2^8$(256) is handled, but the jump to order$2^9$(512) and specifically order$29$(which has over 10 million groups) presents a computational bottleneck. The authors aim to extend the group-ID function to cover the **10,494,213 groups of order$29$**.
• The Obstacle: Existing invariants fail to distinguish specific pairs of groups that share identical subgroup lattices, character tables, and power maps. These indistinguishable groups are termed "siblings" and "twins."

2. Methodology

The authors develop a hierarchical approach combining theoretical definitions of indistinguishable groups with a decision-tree-based identification algorithm.

A. Definitions: Siblings and Twins

To handle groups that resist standard invariant-based separation, the authors introduce two precise definitions:

1. Siblings: Two groups $G$ and $H$ are siblings if they are:
   • Subgroup Equivalent: There is a bijection between their proper subgroups preserving isomorphism types and conjugacy.
   • Factor Equivalent: There is a bijection between their proper quotients preserving isomorphism types.
   • Structure Preserving: The bijection preserves the Frattini subgroup and the terms of the lower and upper central series.
   • Tool: The Sibling Fingerprint (SS) combines the Subgroup Fingerprint (SF) and Factor Fingerprint (FF) with central series data.
2. Twins: Two groups are twins if they are siblings and form a Brauer pair.
   • Brauer Pair: Groups with equivalent character tables including power maps (the map $g \mapsto g^n$).
   • Significance: Twins are the most difficult to distinguish, as they share subgroup structure, quotient structure, and representation theory data.

B. The Identification Algorithm (Decision Tree)

The authors construct a decision tree for groups of order $29$similar to the one used for order$28$. The algorithm proceeds through 10 steps, refining the set of candidate groups at each node:

1. Basic Invariants: Rank, derived series abelian invariants, element orders, and conjugacy class sizes/orders.
2. Power Maps: Analysis of conjugacy class clusters under power maps (e.g., $g \mapsto g^3$).
3. Sibling/Factor Reduction:
   • Identifying IDs of maximal subgroups.
   • Identifying IDs of quotients by cyclic central subgroups.
4. Final Resolution: For the remaining indistinguishable pairs (the "twins"), the algorithm resorts to Random Isomorphism Testing. This involves generating random polycyclic (pc) presentations for the groups and comparing their integer codes. If standard invariants fail, this probabilistic method (or standard presentation algorithms from the ANUPQ package) is used to confirm isomorphism or non-isomorphism.

3. Key Contributions

1. Theoretical Classification of Indistinguishable Groups:

   • Defined and analyzed siblings and twins within the context of finite $p$-groups.
   • Proved that the smallest $p$-group siblings have order $p^4$ (for $p>3$) and the smallest twins have order $p^5$ (for $p>3$).
   • Provided explicit presentations for these minimal sibling and twin pairs.

2. Comprehensive Analysis of Order $29$:

   • Analyzed the entire database of 10,494,213 groups of order $29$.
   • Identified 428 sibling-pairs, 6 sibling-triples, and 3 sibling-quadruples.
   • Crucially, identified 56 twin-pairs (groups indistinguishable by character tables and power maps).

3. Algorithmic Implementation:

   • Developed a highly effective group-ID function for order $29$ that integrates these new "sibling/twin" concepts.
   • The algorithm successfully distinguishes all groups, reducing the "hard" cases to a manageable set of 56 pairs that require only a final isomorphism check.
   • The implementation is available in the IdPGroup package.

4. Investigation of Other Invariants:

   • Tested the 56 twin-pairs against Isoclinism, Modular Group Ring Isomorphism (MIP), and (Outer) Automorphism Groups.
   • Found that while most twins are isoclinic, not all are.
   • Confirmed that none of the twin-pairs of order $29$are counterexamples to the Modular Isomorphism Problem (MIP), though the authors note that MIP examples of order$29$ exist elsewhere in the library.

4. Key Results

• Order $29$ Statistics:
  • Total groups: 10,494,213.
  • Twin pairs found: 56.
  • These 56 pairs represent the "hardest" cases where character tables and subgroup lattices are identical.
• Order $28$ Comparison:
  • For order $28$ (56,092 groups), there are 8 twin-pairs.
  • The authors used the order $28$tree as a baseline, showing that the methods for order$28$were insufficient for order$29$ without the specific "sibling" refinements.
• Performance:
  • 99.9% of groups of order $29$ are identified by Step 7 (conjugacy class clustering and power maps).
  • 99.99% are identified by Step 9 (using sibling/factor invariants).
  • Only 281 groups (the 56 pairs + 1 triple + 1 quadruple) require the final random isomorphism test.
  • Average runtime for the full identification is roughly 10.5 ms for the bulk of groups, rising to ~57 ms for the difficult twin cases (averaged over 100 trials).

5. Significance

• Completeness of SmallGroups Library: This work fills a critical gap in the SmallGroups library, providing a complete and efficient identification function for groups of order $29$, a previously inaccessible order due to the sheer volume of groups and the existence of "twins."
• Advancement in Group Theory: The paper moves beyond simple invariants to a structural understanding of why certain $p$-groups are indistinguishable. By formalizing "siblings" and "twins," the authors provide a framework for understanding the limits of invariant-based classification.
• Algorithmic Efficiency: The proposed decision tree demonstrates that even for groups with over 10 million entries, a hybrid approach (deterministic invariants + probabilistic isomorphism testing for the final few cases) is computationally feasible.
• MIP Context: By verifying that the specific twin-pairs of order $29$do not violate the Modular Isomorphism Problem, the paper contributes to the ongoing research into the structure of group rings, even though the MIP counterexamples of order$29$ were found elsewhere in the library.

6. Open Problems

The authors conclude with several open questions:

• Do "twin-tuples" of arbitrary length exist among finite $p$-groups?
• Can the number of siblings/twins for groups of order $p^n$ be estimated or bounded?
• What specific invariants (beyond those tested) could distinguish twins without resorting to full isomorphism testing?