Commuting Probability in Finite Semigroups

ISEF Category: Mathematics

Subcategory: Algebra  ·  Difficulty: Advanced  ·  Setup: University Lab  ·  Time: Full Year

The Hook

Two objects can obey the same rule and still act very differently when you swap their order. In algebra, that simple swap test is called commutativity. For finite semigroups, the chance that two random elements commute can reveal deep structure. Your job is to turn that chance into a number you can compute, test, and prove things about.

What Is It?

Commuting probability means the fraction of ordered pairs (x, y) for which (xy = yx). In a group, this idea has a long history. In a semigroup, which is a set with an associative operation but no need for inverses or an identity, the picture gets messier fast. That makes the project rich. You are studying how often multiplication works the same way in both orders, then asking what that frequency says about the whole algebraic object.

A good analogy is a classroom seating chart. If two students commute, switching their seats does not change the final arrangement. If many pairs commute, the structure feels orderly. If few do, the structure is more tangled. A threshold theorem asks where that line sits. In this project, you would explore a 5/8-style cutoff for inverse semigroups, then check the claim against small examples from a catalog of finite semigroups.

Why This Is a Good Topic

This is a strong science fair topic because it asks a clean yes-or-no question, but the answer depends on real computation and proof. You can generate data from small finite structures, look for patterns, and test a conjectured threshold. The topic connects to algebraic structure, symmetry, and algorithmic search. You can realistically learn how to use a computer algebra system, compare many small cases, and write a proof around a sharp bound.

Research Questions

• How does commuting probability change as the order of an inverse semigroup increases?
• What is the effect of idempotent density on commuting probability in finite semigroups?
• Does every inverse semigroup with commuting probability above 5/8 have a specific structural form?
• To what extent do non-group inverse semigroups differ from groups with the same order in commuting probability?
• Which small inverse semigroups of order up to 8 attain the highest commuting probability?
• How does the distribution of commuting pairs change when you compare inverse semigroups and arbitrary semigroups of the same size?

Basic Materials

• Laptop or desktop computer with enough memory to run algebra software.
• Python installed with SageMath or a similar open-source math environment.
• Access to SmallSemigroups data through a computer algebra system or exported tables.
• Spreadsheet software for organizing commuting pair counts.
• Notebook for tracking conjectures, counterexamples, and proof ideas.

Advanced Materials

• University computer access for larger semigroup enumeration runs.
• SageMath with semigroup and permutation-group tools.
• GAP with semigroup-related packages, if available.
• Access to the SmallSemigroups library or a local mirror of the database.
• LaTeX for writing proofs, tables, and theorem statements.
• Version control software such as Git for tracking code changes and result logs.

Software & Tools

• SageMath: Computes multiplication tables, counts commuting pairs, and checks algebraic properties of finite semigroups.
• GAP: Helps explore finite algebraic structures and test candidate theorems on small examples.
• Python: Automates data extraction, counting, and table creation for large batches of semigroups.
• Jupyter Notebook: Keeps code, outputs, and notes together while you test conjectures.
• Excel or Google Sheets: Organizes results and helps you spot patterns in commuting probability.

Experiment Steps

1. Define the exact family of semigroups you will study and the commuting probability formula you will measure.
2. Choose one structural feature to compare first, such as inverse, regular, or nilpotent behavior.
3. Build a computation plan that counts commuting pairs from multiplication tables without manual enumeration.
4. Set up a search strategy for small semigroups and record the cases that meet or miss the 5/8 threshold.
5. Test whether the smallest examples support a sharp theorem or reveal a counterexample pattern.
6. Turn the strongest pattern into a proof outline with lemmas that match the computed data.

Common Pitfalls

• Confusing semigroups with groups, which leads to using inverse rules that do not exist in the objects you are testing.
• Counting unordered pairs instead of ordered pairs, which gives the wrong commuting probability.
• Mixing up the identity of a semigroup with the identity relation, which breaks the structure check.
• Trusting software output without verifying the multiplication table source, which can hide bad data from the library.
• Assuming a pattern from one order size must hold in general, which can make a false conjecture look proved.

What Makes This Competitive

A strong version of this project does more than list examples. You would need a clean theorem statement, a careful proof strategy, and a computation that checks all small cases in a transparent way. Strong students also compare the inverse semigroup result with nearby classes of semigroups, so the threshold feels earned, not guessed. Better still, you can test whether the bound is sharp and explain why the exceptions fail.

Project Variations

• Compare commuting probability for inverse semigroups, regular semigroups, and arbitrary semigroups of the same order.
• Study how commuting probability changes when you restrict attention to idempotents, nilpotent elements, or maximal subgroups.
• Search for the smallest semigroups that violate a proposed threshold and classify their multiplication-table features.

Learn More

• MIT OpenCourseWare Algebra materials: Search MIT OpenCourseWare for abstract algebra notes and lectures that refresh quotient ideas, group actions, and proof style.
• GAP Manual: Search the official GAP documentation for finite algebra commands, object definitions, and examples.
• SageMath Reference Manual: Use the official SageMath docs to learn how to encode finite algebraic structures and compute pair counts.
• Journal of Algebra: Search the journal for papers on commuting probability, finite semigroups, and inverse semigroups through your school library or abstract databases.
• PubMed Central and arXiv are not the right fit here, so use arXiv math papers and search for semigroup theory, commuting probability, and inverse semigroups in the math category.