0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Consider that a lower bound derives from the number of partitions of n-1 (say) into d parts. I would expect exponential growth in n even for d approaching n/e. Gerhard "Much Less For Bigger D" Paseman, 2015.04.02 $\endgroup$ Apr 2, 2015 at 20:47

3 Answers 3

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thank you Richard for this comment which is helpful. By the way, the link you gave above for real arrangement is not working. Can you fix it? or can you send me a reference for that? Thank you. $\endgroup$
    – Chebolu
    Apr 3, 2015 at 12:08
  • $\begingroup$ The link should be mathoverflow.net/questions/62764. For some reason if I put this in the text it is displayed as part of the question at this link. $\endgroup$ Apr 3, 2015 at 13:12
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.