Return to Answer

The trivial inequality $$n(k, d) \leq k \times n(k, d - 1) - (k - 1)$$ gives a trivial upper bound: $$n(k, d) \leq (k- 1) k^d + 1.$$

An easy lower bound is: $$n(k, d) \geq (k - 1) 2^d + 1.$$ This is proved by choosing the following lattice points: for every vector in $\{0, 1\}^d \subseteq (\mathbb{Z}/k\mathbb{Z})^d$, repeat the vector $k - 1$ times. One then proves easily by induction on $d$ that there are no $k$ vectors among them which have a lattice point centroid.

The above two inequalities determine the value of $n(2, d)$ for every $d$, namely $n(2, d) = 2^d + 1$.

Interestingly, in the case $d = 1$, one has $n(k, 1) = 2k - 1$ (Erdos-Ginzburg-Ziv theorem, c.f. GTM 165, section 2.4), which suggests that the lower bound $(k - 1) 2^d + 1$ might be a good guess for the exact value.

Also, the case where $k = p$ is prime and $d = 2$ is already a conjecture (according to encyclopedia of mathematics): it is conjectured that $n(p, 2) = 4 p - 3$ in this case, coinciding with the lower bound.

The trivial inequality $$n(k, d) \leq k \times n(k, d - 1) - (k - 1)$$ gives a trivial upper bound: $$n(k, d) \leq (k- 1) k^d + 1.$$

An easy lower bound is: $$n(k, d) \geq (k - 1) 2^d + 1.$$ This is proved by choosing the following lattice points: for every vector in $\{0, 1\}^d \subseteq (\mathbb{Z}/k\mathbb{Z})^d$, repeat the vector $k - 1$ times. One then proves easily by induction on $d$ that there are no $k$ vectors among them which have a lattice point centroid.

The above two inequalities determine the value of $n(2, d)$ for every $d$, namely $n(2, d) = 2^d + 1$.

Interestingly, in the case $d = 1$, one has $n(k, 1) = 2k - 1$ (Erdos-Ginzburg-Ziv theorem, c.f. GTM 165, section 2.4), which suggests that the lower bound $(k - 1) 2^d + 1$ might be a good guess for the exact value.

Also, the case where $k = p$ is prime and $d = 2$ is already a conjecture (according to encyclopedia of mathematics): it is conjectured that $n(p, 2) = 4 p - 3$ in this case, coinciding with the lower bound.

The trivial inequality $$n(k, d) \leq k \times n(k, d - 1) - (k - 1)$$ gives a trivial upper bound: $$n(k, d) \leq (k- 1) k^d + 1.$$

An easy lower bound is: $$n(k, d) \geq (k - 1) 2^d + 1.$$ This is proved by choosing the following lattice points: for every vector in $\{0, 1\}^d \subseteq (\mathbb{Z}/k\mathbb{Z})^d$, repeat the vector $k - 1$ times. One then proves easily by induction on $d$ that there are no $k$ vectors among them which have a lattice point centroid.

The above two inequalities determine the value of $n(2, d)$ for every $d$, namely $n(2, d) = 2^d + 1$.

Interestingly, in the case $d = 1$, one has $n(k, 1) = 2k - 1$ (Erdos-Ginzburg-Ziv theorem, c.f. GTM 165, section 2.4), which suggests that the lower bound $(k - 1) 2^d + 1$ might be a good guess for the exact value.

The trivial inequality $$n(k, d) \leq k \times n(k, d - 1) - (k - 1)$$ gives a trivial upper bound: $$n(k, d) \leq (k- 1) k^d + 1.$$

An easy lower bound is: $$n(k, d) \geq (k - 1) 2^d + 1.$$ This is proved by choosing the following lattice points: for every vector in $\{0, 1\}^d \subseteq (\mathbb{Z}/k\mathbb{Z})^d$, repeat the vector $k - 1$ times. One then proves easily by induction on $d$ that there are no $k$ vectors among them which have a lattice point centroid.

The above two inequalities determine the value of $n(2, d)$ for every $d$, namely $n(2, d) = 2^d + 1$.

Interestingly, in the case $d = 1$, one has $n(k, 1) = 2k - 1$ (Erdos-Ginzburg-Ziv theorem, c.f. GTM 165, section 2.4), which suggests that the lower bound $(k - 1) 2^d + 1$ might be a good guess for the exact value.

Also, the case where $k = p$ is prime and $d = 2$ is already a conjecture (according to encyclopedia of mathematics): it is conjectured that $n(p, 2) = 4 p - 3$ in this case, coinciding with the lower bound.

The trivial inequality $$n(k, d) \leq k \times n(k, d - 1) - (k - 1)$$ gives a trivial upper bound: $$n(k, d) \leq (k- 1) k^d + 1.$$

An easy lower bound is: $$n(k, d) \geq (k - 1) 2^d + 1.$$ This is proved by choosing the following lattice points: for every vector in $\{0, 1\}^d \subseteq (\mathbb{Z}/k\mathbb{Z})^d$, repeat the vector $k - 1$ times. One then proves easily by induction on $d$ that there are no $k$ vectors among them which have a lattice point centroid.

The above two inequalities determine the value of $n(2, d)$ for every $d$, namely $n(2, d) = 2^d + 1$.

Interestingly, in the case $d = 1$, one observes $n(k, 1) = 2k - 1$ (experimental result, verified for $k \leq 6$), which suggests that the lower bound $(k - 1) 2^d + 1$ might be a good guess for the exact value.

The trivial inequality $$n(k, d) \leq k \times n(k, d - 1) - (k - 1)$$ gives a trivial upper bound: $$n(k, d) \leq (k- 1) k^d + 1.$$

An easy lower bound is: $$n(k, d) \geq (k - 1) 2^d + 1.$$ This is proved by choosing the following lattice points: for every vector in $\{0, 1\}^d \subseteq (\mathbb{Z}/k\mathbb{Z})^d$, repeat the vector $k - 1$ times. One then proves easily by induction on $d$ that there are no $k$ vectors among them which have a lattice point centroid.

The above two inequalities determine the value of $n(2, d)$ for every $d$, namely $n(2, d) = 2^d + 1$.

Interestingly, in the case $d = 1$, one has $n(k, 1) = 2k - 1$ (Erdos-Ginzburg-Ziv theorem, c.f. GTM 165, section 2.4), which suggests that the lower bound $(k - 1) 2^d + 1$ might be a good guess for the exact value.