Graham’s rearrangement for dihedral groups
Simone Costa, Stefano Della Fiore, Eva Engel · 2025
Read Graham’s rearrangement for dihedral groups by Simone Costa, Stefano Della Fiore, Eva Engel (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-18101.txt.
Introduction
Simone Costa, Stefano Della Fiore, and Eva Engel extend a famous ordering puzzle from number theory into group theory. Graham conjectured that any set of nonzero residues modulo a prime can be ordered so that all running sums differ. A recent proof settled the claim for sets up to a certain size.
The team adapts that approach to semidirect products, a way of combining two groups where one twists the other. They handle the case where the twisting only ever acts as identity or negation. The second group is abelian, and each of its subsets can itself be ordered with all running products distinct. For these groups they obtain an upper bound of the same type as the recent proof for Graham's original setting.
Catalog record
| CREATOR | Simone Costa, Stefano Della Fiore, Eva Engel |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 49 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-18101
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Graham’s rearrangement for dihedral groups Simone Costa, Stefano Della Fiore, Eva Engel Abstract A famous conjecture of Graham asserts that every set A ⊆ 𝔽 p ∖ { 0 } A\subseteq\mathbb{F}_{p}\setminus\{0\} can be ordered so that all partial sums are distinct. Bedert and Kravitz proved in [ 4 ] that this statement holds whenever | A | ⩽ e c ( log p ) 1 / 4 |A|\leqslant e^{c(\log p)^{1/4}} . In this paper, we will use a similar procedure to obtain an upper bound of the same type in the case of dihedral groups D i h p Dih_{p} . 1 Introduction Let A be a finite subset of group (G,\cdot) . We say that an ordering a_{1},\ldots,a_{|A|} of A is valid if the partial products (or partial sums in additive notation) p_{1}=a_{1},p_{2}=a_{1}\cdot a_{2},\ldots,p_{|A|}=a_{1}\cdot a_{2}\cdot\cdots\cdot a_{|A|} are all distinct. Moreover, this ordering is a sequencing if it is valid and p_{i}\not=id for any i\in[1,|A|-1] . In this case, we will say that A is sequenceable. In the literature, there are several conjectures about valid orderings and sequenceability. We refer to [ 8 , 12 , 14 ] for an overview of the topic, [ 1 , 2 , 3 , 7 ] for lists of related conjectures and [ 5 ] . Here, we explicitly recall just that of Graham, who conjectured that every set of non-zero elements of \mathbb{F}_{p} has a valid ordering. Conjecture 1.1 ( [ 10 ] and [ 9 ] ) . Let p be a prime. Then every subset A\subseteq\mathbb{F}_{p}\setminus\{0\} has a valid ordering. Until recently, the main results on this conjecture were for small values of |A| ; in particular, in [ 7 ] , the conjecture was proved for sets A of size at most 12 . The first result involving arbitrarily large sets A was presented last year by Kravitz [ 11 ] . He used a simple rectification argument to show that Graham’s conjecture holds for all sets A of size |A|\leqslant\log p/\log\log p . A similar argument was also proposed (but not published) by Will Sawin [ 15 ] in a 2015 MathOverflow post. Then, in [ 4 ] , Bedert and Kravitz improved this upper bound to the following: Theorem 1.2 ( [ 4 ] ) . Let p be a large enough prime and let c>0 . Then every subset A\subseteq\mathbb{F}_{p}\setminus\{0\} is sequenceable provided that |A|\leqslant e^{c(\log p)^{1/4}}. Graham’s conjecture over non-abelian groups was first studied by Ollis in [ 13 ] over dihedral groups. More recently, the authors in [ 5 ] presented a nice connection with rainbow paths and produced the asymptotic result that a subset A of a finite group G admits an ordering in which at least (1-o(1))|A| many partial products are distinct. Returning to dihedral groups, inspired by the result of Kravitz ( [ 11 ] ) on cyclic groups, Costa and Della Fiore proved in [ 6 ] that any subset A of the dihedral group Dih_{p}\setminus\{id\} (and in general, of a class of semidirect products) is sequenceable, provided that p>\frac{|A|!}{2} . Note that this is slightly better than |A|\leq\log p/\log\log p . This paper is dedicated to proving, with a similar procedure as that of Bedert and Kravitz, that subsets of the dihedral group Dih_{p}\setminus\{id\} are sequenceable if they are not too large with respect to p . In this setting, we improve the results of [ 6 ] on dihedral groups, obtaining essentially the same bound as in the case of \mathbb{F}_{p} . That is, Theorem 1.3 . Let p be a large enough prime and let c>0 . Then every subset A\subseteq Dih_{p}\setminus\{id\} is sequenceable provided that |A|\leqslant e^{c(\log p)^{1/4}}. 2 Proof Strategy We offer a brief summary of the main steps of our proof of Theorem 1.3 . Note that we represent elements in Dih_{p} as (x_{i},a_{i}) where x_{i}\in\mathbb{F}_{p} and a_{i}\in\mathbb{F}_{2} . We begin Section 3 by describing how a small set B\subseteq Dih_{p} can be “rectified” such that all of its \mathbb{F}_{p} components are contained within a small interval. Then, for a nonempty subset A\subseteq Dih_{p}\setminus\{id\} , we prove the existence of an automorphism \phi\in Aut(Dih_{p}) such that \phi(A)=E\cup\left(\cup_{j=1}^{s}D_{j}\right) , where each D_{j} is a dissociated set with size a multiple of eight and where the \mathbb{F}_{p} components of E are in a small interval by our rectification argument. Moreover, we can impose that each dissociated set D_{j} has \mathbb{F}_{2} components either constantly-one, (in this case we say that j\in L_{1} ) or constantly 0 ( j\in L_{0} ). Here we split each D_{j} with j\in L_{1} into an odd-position subset D^{o}_{j} and an even-position subset D^{e}_{j} of about equal size. Then the product \tau_{j} of its elements, with elements of D^{o}_{j} in odd position and elements of D^{e}_{j} in even position, does not depend on the ordering of those elements. This means that, even if Dih_{p} is non-abelian, we have a constant product \delta of the elements of the dissociated sets without fixing the ordering of all the elements. We then relabel \phi(A) by A for ease of notation. In Section 4 , we order the elements of E . Here we split E into sets P (with \mathbb{F}_{p} components positive and \mathbb{F}_{2} components constantly 0), N (with \mathbb{F}_{p} components negative and \mathbb{F}_{2} components constantly-zero), and S (with \mathbb{F}_{2} components constantly-one). We further split S into subsets S_{e} and S_{o} of almost equal size, where the \mathbb{F}_{p} component of each element of S_{e} is larger than the \mathbb{F}_{p} components of all of the elements in S_{o} . We then prove the existence of an ordering \mathbf{x} of the elements of P,N,S_{e}, and S_{o} such that \delta,\mathbf{x} is a sequencing, where \delta is the prespecified product of the elements of the D_{j} s. At the same time, we derive an important bound on the size of overlap between subsets of Dih_{p} and { \delta times the partial products of \mathbf{x} }. Finally, in Section 5 of our paper, we describe a two-step method of ordering the D_{j} s. First, we randomly split each D^{o}_{j} , each D^{e}_{j} (when j\in L_{1} ), and each remaining D_{j} (when j\in L_{0} ) into a four-set partition. Here, we use a probabilistic argument to prove that, given a sequencing \mathbf{x} of E , we can obtain a sequencing \tau_{1},\dots\tau_{u}\mathbf{x} of E and the products \tau_{i} of the partitions of the D_{j} s. To conclude, we use again a probabilistic argument to prove that if \mathbf{x} satisfies a technical condition (on the intersection between suitable subsets and { \delta times the partial products of \mathbf{x} }), there exists a sequencing of E and each partition T_{i} of the D_{j} s. This gives us Theorem 1.3 . 3 Structure Theorem In this paper we will consider groups that are semidirect products G=\mathbb{F}_{p}\rtimes_{\varphi}H for some group homomorphism \varphi:H\rightarrow Aut(\mathbb{F}_{p}) . We recall that the group operation is defined as (x_{1},a_{1})\cdot_{G}(x_{2},a_{2})=(x_{1}+\varphi(a_{1})(x_{2}),a_{1}\cdot_{H}a_{2}). Here the map x\rightarrow\varphi(a_{1})(x) is an automorphism of (\mathbb{F}_{p},+) . It is well known that the automorphisms of (\mathbb{F}_{p},+) are the multiplications and hence that there exists \varphi_{a_{1}}\in\mathbb{F}_{p} such that \varphi(a_{1})(x)=\varphi_{a_{1}}x. Thus for this kind of semidirect product, we can rewrite the group operation as (x_{1},a_{1})\cdot_{G}(x_{2},a_{2})=(x_{1}+\varphi(a_{1})(x_{2}))\cdot_{G}(a_{1},a_{2})=(x_{1}+(\varphi_{a_{1}}x_{2}),a_{1}\cdot_{H}a_{2}). Here we let