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

8
$\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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .