Distinct Partial Sums in Cyclic Groups: Polynomial Method and Constructive Approaches

2018/09/07 by Hicks, Jacob, Ollis, M. A., Schmitt, John. R. · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1809.02684

Abstract

Let (G,+) be an abelian group and consider a subset A ⊆ G with |A|=k. Given an ordering (a₁, …, a_k) of the elements of A, define its \em partial sums by s₀ = 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 non-constructive 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 2k- √(8k) in all but at most a bounded number of cases.

Cited by

• On Graham's rearrangement conjecture over \mathbbF₂ⁿ

Related

• Some new results about a conjecture by Brian Alspach
• On Sequences in Cyclic Groups with Distinct Partial Sums
• On Partial Sums in Cyclic Groups
• On unique sums in Abelian groups
• A note on the number of distinct elements and zero-sum subsequence lengths in cyclic groups