Tập hợp các phần tử nhóm đã cho có tập hợp các đại diện coset không?

Question

Tôi sợ câu hỏi là một chút kỹ thuật, nhưng tôi hy vọng ai đó có thể đã vấp vào một chủ đề tương tự, hoặc cho tôi một con trỏ của một số loại.

Nếu G là một nhóm (theo nghĩa của cấu trúc đại số), và nếu g , ..., g _n là những yếu tố của G, là có một thuật toán (hay một hàm trong một số chương trình chuyên dụng , giống như GAP) để xác định liệu có một nhóm con của G sao cho những yếu tố đó tạo thành một tập hợp các đại diện cho các tổ hợp của nhóm con? (Chúng ta có thể giả định rằng G là một nhóm hoán vị, và có lẽ là cả nhóm đối xứng đầy đủ.)

(Có một số thuật toán để tìm các coset của một phân nhóm nhất định, như thuật toán Todd-Coxeter; của câu hỏi ngược.)

Cảm ơn, Daniele

Answer 1

giải pháp duy nhất tôi có thể đưa ra là ngây thơ. Về cơ bản nếu bạn có các phần tử x1,...,xn, bạn sẽ sử dụng số LowIndexSubgroupsFpGroup của GAP để liệt kê tất cả các nhóm con có chỉ số n (loại bỏ những nhóm có chỉ mục < n). Sau đó, bạn sẽ đi qua từng nhóm như vậy, tạo ra các coset và kiểm tra xem mỗi coset có chứa một trong các phần tử hay không.

Đây là tất cả những gì tôi có thể nghĩ đến. Tôi sẽ rất quan tâm nếu bạn nghĩ ra cách tiếp cận tốt hơn.

Answer 2

Một cách tiếp cận hơi ít vũ phu sẽ được liệt kê tất cả các phân nhóm của chỉ số n, như Il-Bhima đề nghị, và sau đó cho từng nhóm, kiểm tra từng x _i * x _j ^-1 để xem nếu nó được chứa trong nhóm con.

Các yếu tố x1, ..., xn sẽ đại diện cho một nhóm khi và chỉ khi mỗi sản phẩm

x _i * x _j ^-1 nơi (i! = J)

KHÔNG ở trong nhóm con.

Loại kiểm tra này có vẻ đơn giản hơn tạo ra tất cả các coset và tính toán nhanh hơn.

Answer 3

gì bạn đang cố gắng để xác định được nếu có một nhóm con H của G sao cho {g , ..., g _n} là một transversal của cosets của H. tức Một tập hợp các đại diện của việc phân vùng G của các vũ trụ của H.

Đầu tiên, theo định lý Lagrange's, | G | = | G: H | * | G |, ở đâu | G: H | = | G |/| H | là chỉ số của nhóm con H của G. Nếu {g , ..., g _n} thực sự là một chuyển đổi, sau đó | G: H | = | {g , ..., g _n} |, vì vậy, thử nghiệm đầu tiên trong thuật toán của bạn phải là n chia tách | G |.

Hơn nữa, vì g _i và g _j đang trong coset cùng đúng chỉ nếu g _i g _j^-1 là H, sau đó bạn có thể kiểm tra các phân nhóm với chỉ số n để xem nếu họ tránh g _i g _j^-1. Ngoài ra, lưu ý rằng (g _i g _j^-1) (g _j g _k^-1) = g _i g _k^-1, vì vậy bạn có thể chọn bất kỳ sự ghép nối nào của g _i s.

Điều này là đủ nếu n nhỏ so với | G |.

Một cách khác là để bắt đầu với H là nhóm tầm thường và thêm các yếu tố của bộ H ^* = {h trong G: h ^k = g _i g _j^-1, cho tất cả i, j, k; i! = j} với các máy phát của H cho đến khi bạn không thể thêm nữa (tức là cho đến khi nó không còn là nhóm con). H sau đó là một nhóm con tối đa của G sao cho H là một tập con của H ^*. Nếu bạn có thể nhận được tất cả các H như vậy (và có chúng đủ lớn) thì nhóm con bạn đang tìm kiếm phải là một trong số chúng.

Cách tiếp cận này sẽ hoạt động tốt hơn cho n lớn hơn.

Dù bằng cách nào thì cách tiếp cận không theo thời gian không phải là hiển nhiên.

EDIT: Tôi vừa tìm thấy một cuộc thảo luận về chủ đề này rất ở đây: http://en.wikipedia.org/wiki/Wikipedia:Reference_desk/Archives/Mathematics/2009_April_18#Is_a_given_set_of_group_elements_a_set_of_coset_representatives.3F