Proof of a conjecture of Green and Liebeck on codes in symmetric groups

Let A and B be subsets of a finite group G and r a positive integer. If for every g ∈ G , there are precisely r pairs ( a , b ) ∈ A × B such that g = a b , then B is called a code in G with respect to A and we write r G = A ⋅ B . If in addition B is a subgroup of G , then we say that B is a subgroup code in G . In this paper we resolve a conjecture by Green and Liebeck [8, Conjecture 2.3] on certain subgroup codes in the symmetric group S n . Let n > 2 k and let j be such that 2 j ⩽ k < 2 j + 1 . Suppose that X is a conjugacy class in S n containing x , and Y k is the subgroup S k × S n − k of S n , where the factor S k permutes the subset { 1 , … , k } and the factor S n − k permutes the subset { k + 1 , … , n } . We prove that r S n = X ⋅ Y k for some positive integer r if and only if the cycle type of x has exactly one cycle of length 2 i for 0 ⩽ i ⩽ j and all other cycles have length at least k + 1 . We also propose several problems concerning the existence of certain subgroup codes in a finite group G with respect to a conjugation-closed subset in G .