Lower bounds for multidimensional zero sums (Q558239): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
Property / author | |||
Property / author: Christian Elsholtz / rank | |||
Normal rank | |||
Property / review text | |||
Let \(f(n,d)\) denote the least integer such that for any choice of \(f(n,d)\) elements in \({\mathbb Z}_n^d\) contains a subset of size \(n\) whose sum is zero. \textit{H. Harborth} [J. Reine Angew. Math. 262/263, 356--360 (1973; Zbl 0268.05008)] showed that \((n-1)2^d+1\leq f(n,d)\leq (n-1)n^d+1\). \textit{N. Alon} and \textit{M. Dubiner} [Combinatorica 15, 301--309 (1995; Zbl 0838.11020)] improved the upper bound to \(c_d n\). In this nice paper, the author improves the lower bound to \(1.125^{\lfloor d/3\rfloor}(n-1)2^d+1\) for all \(d\geq 3\) and odd \(n\geq 3\). The proof is based on an example of nine vectors in \({\mathbb Z}_3^2\), first used by Harborth to show that \(f(3,3)\geq 19\), which are now treated as vectors in \({\mathbb Z}_n^3\). The author proves a lemma showing that if \(n\geq 3\) is odd, and if any \(n\) vectors from Harborth's set add to \(0\in {\mathbb Z}_n^3\), then one necessarily needs to take the same vector \(n\) times. The proof of this statement is elementary but intricate, and the author's result follows easily from the above lemma. A few immediate corollaries are also presented. | |||
Property / review text: Let \(f(n,d)\) denote the least integer such that for any choice of \(f(n,d)\) elements in \({\mathbb Z}_n^d\) contains a subset of size \(n\) whose sum is zero. \textit{H. Harborth} [J. Reine Angew. Math. 262/263, 356--360 (1973; Zbl 0268.05008)] showed that \((n-1)2^d+1\leq f(n,d)\leq (n-1)n^d+1\). \textit{N. Alon} and \textit{M. Dubiner} [Combinatorica 15, 301--309 (1995; Zbl 0838.11020)] improved the upper bound to \(c_d n\). In this nice paper, the author improves the lower bound to \(1.125^{\lfloor d/3\rfloor}(n-1)2^d+1\) for all \(d\geq 3\) and odd \(n\geq 3\). The proof is based on an example of nine vectors in \({\mathbb Z}_3^2\), first used by Harborth to show that \(f(3,3)\geq 19\), which are now treated as vectors in \({\mathbb Z}_n^3\). The author proves a lemma showing that if \(n\geq 3\) is odd, and if any \(n\) vectors from Harborth's set add to \(0\in {\mathbb Z}_n^3\), then one necessarily needs to take the same vector \(n\) times. The proof of this statement is elementary but intricate, and the author's result follows easily from the above lemma. A few immediate corollaries are also presented. / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Florian Luca / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 11B50 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05D05 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 2186322 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
zero sums modulo n | |||
Property / zbMATH Keywords: zero sums modulo n / rank | |||
Normal rank |
Revision as of 14:15, 1 July 2023
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Lower bounds for multidimensional zero sums |
scientific article |
Statements
Lower bounds for multidimensional zero sums (English)
0 references
5 July 2005
0 references
Let \(f(n,d)\) denote the least integer such that for any choice of \(f(n,d)\) elements in \({\mathbb Z}_n^d\) contains a subset of size \(n\) whose sum is zero. \textit{H. Harborth} [J. Reine Angew. Math. 262/263, 356--360 (1973; Zbl 0268.05008)] showed that \((n-1)2^d+1\leq f(n,d)\leq (n-1)n^d+1\). \textit{N. Alon} and \textit{M. Dubiner} [Combinatorica 15, 301--309 (1995; Zbl 0838.11020)] improved the upper bound to \(c_d n\). In this nice paper, the author improves the lower bound to \(1.125^{\lfloor d/3\rfloor}(n-1)2^d+1\) for all \(d\geq 3\) and odd \(n\geq 3\). The proof is based on an example of nine vectors in \({\mathbb Z}_3^2\), first used by Harborth to show that \(f(3,3)\geq 19\), which are now treated as vectors in \({\mathbb Z}_n^3\). The author proves a lemma showing that if \(n\geq 3\) is odd, and if any \(n\) vectors from Harborth's set add to \(0\in {\mathbb Z}_n^3\), then one necessarily needs to take the same vector \(n\) times. The proof of this statement is elementary but intricate, and the author's result follows easily from the above lemma. A few immediate corollaries are also presented.
0 references
zero sums modulo n
0 references