Lower bounds for multidimensional zero sums (Q558239): Difference between revisions

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
Importer (talk | contribs)
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
    0 references
    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
    0 references
    zero sums modulo n
    0 references

    Identifiers