Distinct Partial Sums in Cyclic Groups: Polynomial Method and Constructive Approaches
| Autor: | Jacob Hicks, John R. Schmitt, M. A. Ollis |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
Sequence
Conjecture 020206 networking & telecommunications Cyclic group 0102 computer and information sciences 02 engineering and technology 01 natural sciences Constructive Prime (order theory) Combinatorics 010201 computation theory & mathematics Bounded function Polynomial method 0202 electrical engineering electronic engineering information engineering FOS: Mathematics Discrete Mathematics and Combinatorics Mathematics - Combinatorics Combinatorics (math.CO) Abelian group Mathematics |
| Popis: | Let $(G,+)$ be an abelian group and consider a subset $A \subseteq G$ with $|A|=k$. Given an ordering $(a_1, \ldots, a_k)$ of the elements of $A$, define its {\em partial sums} by $s_0 = 0$ and $s_j = \sum_{i=1}^j a_i$ for $1 \leq j \leq k$. We consider the following conjecture of Alspach: For any cyclic group $\Z_n$ and any subset $A \subseteq \Z_n \setminus \{0\}$ with $s_k \neq 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 \leq i < j \leq k$. We show that Alspach's Conjecture holds for prime $n$ when $k \geq n-3$ and when $k \leq 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 \setminus \{0\}$ of size at least $2k- \sqrt{8k}$ in all but at most a bounded number of cases. 18 pages |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|