Some new results about a conjecture by Brian Alspach
- PDF / 354,431 Bytes
- 10 Pages / 439.37 x 666.142 pts Page_size
- 44 Downloads / 168 Views
Archiv der Mathematik
Some new results about a conjecture by Brian Alspach S. Costa and M.A. Pellegrini
Abstract. In this paper, we consider the following conjecture, proposed by Brian Alspach, concerning partial sums in finite cyclic groups: given a subset A of Zn \{0} of size k such that z∈A z = 0, it is possible to find an ordering (a1 , . . . , ak ) of the elements of A such that the partial sums si = ij=1 aj , i = 1, . . . , k, are nonzero and pairwise distinct. This conjecture is known to be true for subsets of size k ≤ 11 in cyclic groups of prime order. Here, we extend this result to any torsion-free abelian group and, as a consequence, we provide an asymptotic result in Zn . We also consider a related conjecture, originally proposed by Ronald Graham: given a subset A of Zp \{0}, where p is a prime, there exists an ordering of the elements of A such that the partial sums are all distinct. Working with the methods developed by Hicks, Ollis, and Schmitt, based on Alon’s combinatorial Nullstellensatz, we prove the validity of this conjecture for subsets A of size 12. Mathematics Subject Classification. Primary 05C25; Secondary 20K15. Keywords. Alspach’s conjecture, Partial sum, Torsion-free abelian group, Polynomial method.
1. Introduction. In this paper, we give some new results about a conjecture, due to Brian Alspach, concerning finite cyclic groups. First of all, we introduce some notations. Given an abelian group (G, +), a finite subset A = {x1 , x2 , . . . , xk } of G\{0G } and an ordering ω = (xj1 , xj2 , . . . , xjk ) of its elements, we denote by si = si (ω) the partial sum xj1 +xj2 +· · ·+xji . Clearly, the ordering ω induces the permutation σω = (j1 , j2 , . . . , jk ) ∈ Sym(k). Alspach’s conjecture was originally proposed only for finite cyclic groups, see [6,7]. However, it can be extended to any abelian group, [11,19]. Conjecture 1.1 (Alspach). Given an abelian group (G, +) and a subset A of G\{0G } of size k such that z∈A z = 0G , it is possible to find an ordering ω of the elements of A such that si (ω) = 0G and si (ω) = sj (ω) for all 1 ≤ i < j ≤ k.
S. Costa and M.A. Pellegrini
Arch. Math.
The validity of this conjecture has been proved in each of the following cases: (1) (2) (3) (4) (5)
k ≤ 9 or k = |G| − 1, [3,6,7,15]; k = 10 or |G| − 3 with G cyclic of prime order, [17]; k = 11 with G cyclic of prime order, [20]; |G| ≤ 21, [7,11]; G is cyclic and either k = |G| − 2 or |G| ≤ 25, [6,7].
Clearly, when k = |G| − 3, |G| − 2, |G| − 1, G is assumed to be finite. Alspach’s conjecture is worth to be studied also in connection with sequenceability and strong sequenceability of groups, see [2,3,18], and simplicity of Heffter arrays, see [4,5,12,14]. In Section 2, we explain how the validity of Conjecture 1.1 for sets of size k in cyclic groups Zp , for infinitely many primes p, implies the validity for sets of size k in any torsion-free abelian group. As a consequence, in Section 3, we provide an asymptotic result for sets of size k ≤ 11 in finite cyclic groups: this has been achieved without
Data Loading...
