Babai dan Seress membuktikan bahwa dengan diberi subkelompok dan himpunan S dari G , permutasi apa pun dalam G dapat ditulis sebagai produk generator dan inversinya dengan panjang e ( 1 + o ( 1 ) ) √ . Batas ini optimal karenaSnmemiliki elemen ordee(1+o(1)) √ .
Fakta klasik bahwa setiap elemen dalam memiliki urutan paling banyak e ( 1 + o ( 1 ) ) √ , digabungkan dengan hasil Babai dan Seress, menunjukkan bahwa diberikan subkelompokG≤SndangensetSofG, permutasi dalamGdapat ditulis sebagai produk generator dengan panjang maksimale2(1+o(1)) √ .
Bisakah kita meningkatkan batas atas kee(1+o(1)) √ ?
Pertanyaan ini telah terinspirasi oleh pertanyaan Automata terbaru dan sejenis pemompaan lemma pada fungsi transisi negara .
gr.group-theory
Yuval Filmus
sumber
sumber