Premium
Distinct partial sums in cyclic groups: polynomial method and constructive approaches
Author(s) -
Hicks Jacob,
Ollis M. A.,
Schmitt John R.
Publication year - 2019
Publication title -
journal of combinatorial designs
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.618
H-Index - 34
eISSN - 1520-6610
pISSN - 1063-8539
DOI - 10.1002/jcd.21652
Subject(s) - mathematics , conjecture , combinatorics , prime (order theory) , abelian group , constructive , sequence (biology) , bounded function , polynomial , cyclic group , group (periodic table) , discrete mathematics , mathematical analysis , chemistry , organic chemistry , process (computing) , biology , computer science , genetics , operating system
Let ( G , + ) be an abelian group and consider a subset A ⊆ G with ∣ A ∣ = k . Given an ordering ( a 1 , … , a k ) of the elements of A , define its partial sums by s 0 = 0 and s j = ∑ i = 1 j a i for 1 ≤ j ≤ k . We consider the following conjecture of Alspach: for any cyclic group Z n and any subset A ⊆ Z n ⧹ { 0 } with s k ≠ 0 , it is possible to find an ordering of the elements of A such that no two of its partial sums s i and s j are equal for 0 ≤ i < j ≤ k . We show that Alspach’s Conjecture holds for prime n when k ≥ n − 3 and when k ≤ 10 . The former result is by direct construction, the latter is nonconstructive and uses the polynomial method. We also use the polynomial method to show that for prime n a sequence of length k having distinct partial sums exists in any subset of Z n ⧹ { 0 } of size at least 2 k − 8 kin all but at most a bounded number of cases.