Counting zero-sum free sequences of a given length in $\mathbb{Z}_n$

Question

Let $n$ and $d$ be positive integers. Define $\alpha_n^d$ to be the number of vectors $(x_1, x_2, \cdots, x_d)$ in $\mathbb{Z}_n^d$ such that given any subset $S$ of $\{ 1, 2, 3, \cdots d\}$, $\sum_{i \in S} x_i \ne 0$ in $\mathbb{Z}_n$. What is known about $\alpha_n^d$?

It is easy to compute $\alpha_n^d$ explicitly for $d=1, 2$ and $3$. Computing this value for $d\ge 4$ seems very hard. I wrote a Sage program which can compute $\alpha_n^d$ for any given $n$ and $d$. But I don't see any pattern in the data to make any conjecture. Any suggestions or references would be greatly appreciated.

Answer 1

This is not really an answer, but it's too long for a comment. If $n$ is a prime $p$, then you are asking for the number of points in $\mathbb{Z}_p^d$ not lying on any of the $2^d-1$ hyperplanes $x_{i_1}+\cdots + x_{i_k}=0$. By the general theory of hyperplane arrangements, for sufficiently large $p$ this number will be a polynomial in $p$ which is the characteristic polynomial of the corresponding real arrangement. The real arrangement is discussed in https://mathoverflow.net/62764. The problem of finding the characteristic polynomial (or even its value at $-1$, which is up to sign the number of regions) is considered to be intractable. Thus an exact formula for $\alpha_n^d$ (even when $n$ is prime) is highly unlikely. It still should be possible to obtain some reasonable estimates.

Answer 2

Expanding on the comment, consider the smaller figure where the sum of $x_i$ is restricted to be less than $n$. One gets $\sum_{d \leq s \lt n} {s+1 \choose d-1}$ as a lower bound (or something like that) by considering each vector as an ordered partition of the number $s$ into exactly $d$ parts. This sum is close to (if not equal) $n \choose d$. However given a multiset of $d$ numbers, there are $2^d - 1$ possible sums you are asking, and if $d$ is much larger than $\log n$, then two such sums will be equal modulo $d$. This is OK if neither submultiset contains the other, but otherwise one has a subset whose sum is $0 \bmod n$. I thus suspect the set will become rather sparse (compared to the space of $n^d$ vectors) when $d$ gets to a size of $O(\log n)$.

Gerhard "Not In A Calculating Mood" Paseman, 2015.04.02

Answer 3

I think I am able to prove the following result which gives a partial answer to my question.

Theorem: Let $n \ge 3$ and $d > n/2$. Then $\alpha_n^d$ (the number of zero-sum free $d$-tuples in $\mathbb{Z}_{n}$) is given by $$\alpha_n^d = \phi(n) {n-1 \choose d},$$ where $\phi$ is the Euler's $\phi$-function.

Proof. To count these zero-sum free $d$-tuples, it is enough to count the number of minimal zero-sum $d+1$-tuples in $\mathbb{Z}_n^{d+1}$, where a minimal zero-sum $d+1$-tuple is a vector in $\mathbb{Z}_n^{d+1}$ whose sum of components is zero but no proper nonempty subset of components adds up to zero. It is an easy exercise to show that these two collections have the same cardinality. We now use the following characterization of minimal zero sum sequences (unordered) in the range $d > n/2$ given in [1].

Theorem[1] Every minimal zero sum sequence $\alpha$ of length $d > n/2$ in $\mathbb{Z}_{n}$ for $n \ge 3$ is of the form $x_{1}g, x_{2}g, \dots, x_{d}g$, where $g$ is a term of $\alpha$ which generates $\mathbb{Z}_{n}$ and $x_{1}, x_{2}, \cdots, x_{d}$ are positive integers whose sum is $n$.

Consider the natural action of $Aut(\mathbb{Z}_n)$ on the minimal zero-sum $d+1$-tuples. When $d > n/2$ it can be shown using the above theorem that this action is free and hence each orbit will have size $|Aut(\mathbb{Z}_n)| = \phi(n)$. Moreover, each orbit $O$ is of the form $$O = \{ g (x_{1}, x_{2}, \cdots, x_{d+1} )\, | \, g \text{ is a generator of } \mathbb{Z}_n \}$$ where $(x_1, x_2, \cdots ,x_{d+1})$ is an ordered partition of $n$ into $d+1$ positive integers. This tells us that the number of orbits is equal to the number of partitions of $n$ into $d+1$ positive integers. The latter can be shown to be equal to ${n-1 \choose d}$. Thus the total number of minimal zero sum $d+1$ tuples is $\phi(n) {n-1 \choose d}$. By the remark at the beginning of the proof, this number is also equal to $\alpha_n^d$.

References

[1] Savchev, Svetoslav; Chen, Fang Long zero-free sequences in finite cyclic groups. Discrete Math. 307 (2007), no. 22, 2671–2679.