4
$\begingroup$

How to derive an upper bound on the minimum number $n(k,d)$ of lattice points in $d$-dimensions such that there are some $k$ of these points which have a lattice point centroid.

$\endgroup$
2
  • 4
    $\begingroup$ Finding $n(2,3) = 9$ was a Putnam problem in the early 1970's. $\endgroup$ – Mark Fischler Aug 24 '17 at 18:14
  • $\begingroup$ $n(k,d)=k$ as written. Clarification of the question needed. $\endgroup$ – js21 Aug 25 '17 at 14:04
2
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ Case $d = 1$ is exactly Erdös-Ginzburg-Ziv theorem. $\endgroup$ – Aleksei Kulikov Aug 26 '17 at 15:28
  • $\begingroup$ @AlekseiKulikov Thanks! I updated the answer. $\endgroup$ – WhatsUp Aug 27 '17 at 2:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.