# Gao's theorem for nonabelian groups

 Importance: Medium ✭✭
 Author(s): DeVos, Matt
 Subject: Number Theory » Combinatorial Number Theory
 Keywords: subsequence sum zero sum
 Posted by: mdevos on: May 23rd, 2007

For every finite multiplicative group , let ( ) denote the smallest integer so that every sequence of elements of has a subsequence of length (length ) which has product equal to 1 in some order.

Conjecture for every finite group .

A beautiful theorem of Gao (previously conjectured by Caro) shows that the above property holds for all abelian groups. Rather surprisingly, almost all of the proof for the abelian case seems to work as well for the general case - only one rather innocent looking bit does not carry through. Next we explore this curiosity in detail, beginning with an easy observation.

Observation for every (finite) group .

To see this, choose a sequence of length of elements which has no nontrivial subsequence with product equal to 1 in any order. Now, append copies of 1 to this sequence. The new sequence has length and has no subsequence of length with product 1 in any order.

So, the hard part of Gao's theorem is to prove , and we now have multiple proofs of this fact. One of the nicest arguments uses a theorem of Kempermann-Scherck, and can be split into the following two parts.

Lemma   Let and let be a sequence in an arbitrary finite multiplicative with the added property that 1 is the most frequently occurring in . Then there is a subsequence of of length which has product equal to 1 in some order.
Observation   If is a sequence of elements in the finite abelian group and , then replacing each element of by has no effect on the products of length subsequences of .

The lemma and observation now combine easily to show in abelian groups, since we may take any sequence of length and modify it by mutiplying each element by a fixed constant so that 1 is the most common element of . The lemma shows that there is now a subsequence with product 1, and the observation shows that the corresponding subsequence has product 1 in the original. So, surprisingly, the Lemma - which includes all of the real difficutly - works just fine for general groups. The only place we required the assumption is abelian is for the observation.