Calculate the missing components

Given two group elements, can one be obtained from the other by multiplying on the left and right by elements of specified subgroups? Testing every pair can revisit the same endpoints. A graph search avoids that repetition, but then it must remember how an endpoint was reached. Choosing the right record makes membership witnesses and the ambiguity between witnesses part of the same calculation.

Specify a finite input and two kinds of edge

Let G be a finite group with explicitly available elements, exact multiplication, inverses, and equality. Let A and B be subgroups given by finite generating lists X and Y; include the inverses in each list.

Fix a starting element g. We want a record with two words, one from each generating list, whose value explains the current vertex. We also want to append a new generator to the end of its word whenever we make a move. Writing the record as v = agb would make a new left multiplication prepend to a. Instead store the inverse of the left multiplier:

v = a⁻¹ g b,       a ∈ A, b ∈ B.

Now appending x to a gives (ax)⁻¹gb = x⁻¹v, while appending y to b gives vy. This convention is chosen to make the two records update in the same order as the search; using ordinary left multipliers with the opposite word order would also work.

Use the elements of G as graph vertices. At a vertex v allow two kinds of directed move:

left move x ∈ X:       v ↦ x⁻¹v,
right move y ∈ Y:      v ↦ vy.

Both moves have reverses. Left and right moves commute with each other: x⁻¹(vy) = (x⁻¹v)y. Moves on the same side must retain their order.

The starting record is (1, 1). Store one such record when each vertex is first visited, retaining both the generator words and their evaluated group elements. Encountering an already visited vertex then gives two records with the same value. The closed comparison between those records will supply information that a list of visited vertices alone would lose.

Prove which vertices a search reaches

Every path from g has endpoint a⁻¹gb by the invariant. Conversely, write any a and b as generator words and perform their left moves and right moves. This constructs a path to that endpoint.

The connected component is therefore exactly

A g B = {a⁻¹ g b : a ∈ A, b ∈ B}.

This set is called a double coset, but the graph has already supplied its meaning. A breadth-first search lists the component and gives a pair of words certifying membership for each vertex. If a queried vertex is not reached when the queue is exhausted, it is not in the component.

Repeat from unvisited vertices to obtain every component. With G explicitly listed, this inspects at most |G|(|X| + |Y|) directed moves. This is a bound in this input model, not a polynomial-time claim for an arbitrary succinct presentation of a group.

Read the group carried by a closed comparison

A path with pair (a, b) closes at g precisely when

a⁻¹ g b = g,       equivalently       a = g b g⁻¹.

Its first coordinate lies in A ∩ gBg⁻¹, and every element of that intersection supplies one and only one closed pair: for a chosen a, take b = g⁻¹ag.

Following a pair (a, b) by (a′, b′) gives (aa′, bb′). Thus the closed pairs form a group under componentwise multiplication, and taking the first coordinate identifies it with the displayed intersection.

These are closed comparisons, not freely generated graph loops. Different paths are identified when their evaluated pairs in A × B agree. Keeping every graph path distinct would instead create a free path group and give the wrong object.

Extract all closed comparisons from one search tree

A search from g records one pair p_v = (a_v, b_v) for each reached vertex, with p_g = (1, 1). Regard a left step as the pair k = (x, 1) and a right step as k = (1, y). On an edge v → w, the old record p_w and the newly obtained record p_vk reach the same vertex. To compare them at the starting point, follow the new record and then undo the old one:

p_v k p_w⁻¹.

This pair fixes g. All closed pairs are generated by these finitely many pairs. To see why, take any closed path with successive steps k₁, …, k_ℓ and vertices v₀ = g, …, v_ℓ = g. Insert the recorded paths and their inverses:

k₁ ⋯ k_ℓ
 = (p_{v₀} k₁ p_{v₁}⁻¹)(p_{v₁} k₂ p_{v₂}⁻¹) ⋯ (p_{v_{ℓ−1}} k_ℓ p_{v_ℓ}⁻¹).

The middle factors cancel, and the endpoint factors are identities. Every closed pair has a generator-word path, so this proves the claim. Take the first coordinates of these closed pairs to obtain generators of A ∩ gBg⁻¹. Finite closure under multiplication then lists that intersection if a full list is wanted.

Compute the two components of a six-element group

Use the permutations of three letters, with products acting rightmost first. Set A = B = {1, (12)}. The component of 1 is {1, (12)}. Its closed-comparison group is all of A, of order 2.

Now start at g = (13). Applying or omitting the left and right move gives

g = (13),       (12)g = (132),
g(12) = (123),  (12)g(12) = (23).

These are the other four vertices. Conjugating B by g gives {1, (23)}, whose intersection with A is {1}. The two components therefore have different closed-comparison groups. Inspecting only A ∩ B would miss the second component and its different group.

Count the representing pairs

Each vertex in the component has exactly |A ∩ gBg⁻¹| representing pairs. Indeed, if (a₀, b₀) represents that vertex, all other representing pairs are uniquely

a = h a_0,       b = g⁻¹ h g b_0,
where h ∈ A ∩ gBg⁻¹.

Substitution checks the endpoint, and rearranging equality of two endpoints recovers that unique h. Counting pairs now gives

|AgB| = |A| |B| / |A ∩ gBg⁻¹|.

In the example this gives 4/2 = 2 and 4/1 = 4. The graph search, recorded word pairs, and closed-edge comparisons give three checkable outputs from one construction: the components, a membership certificate for each reached vertex, and generators of each component's intersection group. Finiteness and effective group operations are essential to the termination and bounds asserted here.