3
$\begingroup$

The EGZ theorem states that any multiset of $2n-1$ integers has a subset of size $n$ the sum of whose elements is a multiple of $n$.

Kemnitz-Reiher theorem is a 2-dimensional analogue of EGZ. Here is the formulation: Let $n$ be a natural number and $S$ a set of $4n − 3$ lattice points in plane. Then there exists a subset $S_1$ $\subseteq S$ with $n$ points such that the centroid of all points from $S_1$ is also a lattice point.

So how about higher dimensions?

$\endgroup$

1 Answer 1

7
$\begingroup$

In higher dimension things become more complicated. For a finite abelian group $G$ define $\mathfrak{s}(G)$ to be the least integer $N$, such that every sequence $x_1, \ldots, x_N$ of elements of $G$ contains a subsequence $x_{i_1}, \ldots, x_{i_n}$ with sum 0, where $n=\exp(G)=\min \{ n\mid g^n=e \text{ for all }g\in G \}$. The natural generalization of EGZ and Kemnitz-Reiher would be $\mathfrak{s}(\mathbb{Z}_n^d)=2^d(n-1)+1$, however, this conjecture is wrong for $d>2$.

Edel-Elsholtz-Geroldinger-Kubertin-Rackham (Zero sum problems in finite abelian groups and affine caps, Quarterly J. Math. 58) showed that for $n$ odd we have $\mathfrak{s}(\mathbb{Z}_n^3)\geq 9n-8$, and $\mathfrak{s}(\mathbb{Z}_n^4)\geq 20n-19$, and Elsholtz (Lower Bounds for Multidimensional Zero Sums, Combinatorica 24) showed that for $n$ odd we have $\mathfrak{s}(\mathbb{Z}_n^d)\geq 2^d(1.125)^{\lfloor d/3\rfloor}(n-1)+1$.

In the other direction Alon and Dubiner (Zero-sum sets of prescribed size, Combinatorics, Paul Erdos is Eighty, 1993) showed that for every $d$ there exists some $C(d)$, such that $\mathfrak{s}(\mathbb{Z}_n^d)\leq C(d) n$, and Meshulam (On subsets of finite abelian groups with no 3-term arithmetic progressions, J. Combin. Theory Ser. A 71) used the method of Roth's theorem to show that $\mathfrak{s}(\mathbb{Z}_n^d)\leq\frac{2n^d}{d}$.

$\endgroup$
0

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.