2025/08/25 by Bedert, Benjamin, Bucić, Matija, Kravitz, Noah +2
#05C35 #05D40 #20K01 #Combinatorics (math.CO) #FOS: Mathematics #Group Theory (math.GR) #Number Theory (math.NT)
paper · doi:10.48550/arxiv.2508.18254
A sequence s1,s2,…, sk of elements of a group G is called a valid ordering if the partial products s1, s1 s2, …, s1⋯ sk are all distinct. A long-standing problem in combinatorial group theory asks whether, for a given group G, every subset S ⊆ G∖ \id\ admits a valid ordering; the instance of the additive group \mathbbFp is the content of a well-known 1971 conjecture of Graham. Most partial progress to date has concerned the edge cases where either S or G ∖ S is quite small. Our main result is an essentially complete resolution of the problem for G=\mathbbF2n: we show that there is an absolute constant C>0 such that every subset S⊆ \mathbbF2n ∖ \0\ of size at least C admits a valid ordering. Our proof combines techniques from additive and probabilistic combinatorics, including the Freiman--Ruzsa theorem and the absorption method. Along the way, we also solve the general problem for moderately large subsets: there is a constant c>0 such that for every group G (not necessarily abelian), every subset S ⊆ G∖ \id\ of size at least |G|1-c admits a valid ordering. Previous work in this direction concerned only sets of size at least (1-o(1))|G|. A main ingredient in our proof is a structural result, similar in spirit to the Arithmetic Regularity Lemma, showing that every Cayley graph can be efficiently decomposed into mildly quasirandom components.