OpenAlex ·

Anti-concentration and Graham's rearrangement problem in finite abelian groups

Hoi H. Nguyen, Tuan Tran and Van H. Vu

Published
Source
OpenAlex
Published in
arXiv (Cornell University)
DOI
10.48550/arxiv.2610.40712
Original
Read it at the publisher
Topics
Combinatorics

Abstract

Let $S$ be a subset of $n$ elements of a group $G$. An ordering $x_1,\ldots,x_n$ of its elements is valid if the partial sums $x_1,x_1+x_2,\ldots,x_1+\cdots+x_n$ are pairwise distinct. This notion has a long history in combinatorial group theory, dated back to Gordon's works in early 1960. Alspach-Liversidge conjecture asserts that any subset of the nonzero elements of a finite abelian group $G$ has a valid ordering. This generalizes Graham's conjecture, which considers the case when the group $G$ is $\mathbb{F}_p$, the cyclic group of prime order. Graham's conjecture has been solved recently, as a combination of results by Kravitz, Bedert and Kravitz, Müyesser and Pokrovskiy, Bedert, Bucić, Kravitz, Montgomery, and Müyesser, and Pham and Sauermann. Beside this, the only other case where Alspach-Liversidge conjecture has been confirmed is $G=\mathbb{F}_2^k$, thanks to a recent result by Bedert, Bucić, Kravitz, Montgomery, and Müyesser. We prove the Alspach-Liversidge conjecture in its full generality. Our proof combines ideas from many previous papers. In particular, we will use the probabilistic approach and the absorption method. Our new main technical ingredient is a Fourier-moment estimate, which is of independent interest. In particular, we can use it to show that the distribution of certain kinds of random sums in an abelian group has an almost uniform distribution.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

Read it on ReadSearch

Each opens after you create an account, and brings you back to this paper.

Already a reader? Sign in

All new papers in Combinatorics

Get the few papers worth your time in Combinatorics every morning.

ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.

Papers belong to their authors and publishers; every page here links to the original. All research topics