Ramanujan J (2007) 13:333–337
DOI 10.1007/s11139-006-0256-y
On Kemnitz’ conjecture concerning lattice-points
in the plane
Christian Reiher
Dedicated to Richard Askey on the occasion of his 70th birthday.
Received: 25 May 2004 / Accepted: 14 February 2005
C Springer Science + Business Media, LLC 2007
Abstract In 1961, Erd˝os, Ginzburg and Ziv proved a remarkable theorem stating that
each set of 2n − 1 integers contains a subset of size n, the sum of whose elements is
divisible by n. We will prove a similar result for pairs of integers, i.e. planar latticepoints,
usually referred to as Kemnitz’ conjecture.
Keywords Zero-sum-subsets . Kemnitz’ Conjecture
2000 Mathematics Subject Classification Primary—11B50
1 Previous work
Denoting by f (n, k) the minimal number f, such that any set of f lattice-points in the
k-dimensional Euclidean space contains a subset of cardinality n, the sum of whose
elements is divisible by n, it was first proved by Erd˝os, Ginzburg and Ziv [2], that
f (n, 1) = 2n − 1.
The problem, however, to determine f (n, 2) turned out to be unexpectedly difficult:
Kemnitz [4] conjectured it to equal 4n − 3, but all he knew were (1◦
), that 4n − 3
is a rather straighforward lower bound,1
(2◦
) that the set of all integers n satisfying
f (n, 2) = 4n − 3 is closed under multiplication and that it therefore suffices to prove
thisequationforprimevaluesofn and(3◦
)thathisassertionwascorrectforn = 2,3,5,
7 and consequently also for every n being representable as a product of these numbers.
Linear upper bounds estimating f (p, 2), where p denotes any prime, appeared for
the first time in a paper by Alon and Dubiner [1] who proved f (p, 2) ≤ 6p − 5 for
C. Reiher ( )
Oxford University, UK
e-mail: christian.reiher@keble.ox.ac.uk
1 In order to prove f (n, 2) > 4n − 4 one takes each of the four vertices of the unit square n − 1 times.
Springer
334 C. Reiher
all p and f (p, 2) ≤ 5p − 2 for large p. Later this was improved to f (p, 2) ≤ 4p − 2
by R´onyai [5].
In the third section of this paper we give a rigorous proof of Kemnitz’ conjecture.
2 Preliminary results
Notational conventions. In the sequel the letter p is always assumed to designate any
odd prime and congruence modulo p is simply referred to as ‘≡’. Uppercase Roman
letters (such as J, X, . . .) will always denote finite sets of lattice-points in the Euclidean
plane. The sum of elements of such a set, taken coordinatewise, will be indicated by a
preposed ‘ ’. Finally the symbol (n|X) expresses the number of n-subsets of X, the
sum of whose elements is divisible by p.
All propositions contained in this section are deduced without the use of combinatorial
arguments from the following
Theorem (Chevalley and Warning; see, e.g. [6]). Let P1, P2, . . . , Pm ∈ F[x1, . . . ,
xn] be some polynomials over a finite field F of characteristic p. Provided that the
sum of their degrees is less than n, the number of their common zeros (in Fn
) is
divisible by p.
Proof: It is easy to see that
≡
y1,...,yn∈F
μ=m
μ=1
{1 − Pμ(y1, . . . yn)q−1
}
where q is supposed to denote the number of elements contained in F. Expanding the
product and taking into account that
y∈F
yr
≡ 0 for 1 ≤ r ≤ q − 2
gives indeed ≡ 0.
Corollary I. If |J| = 3p − 3, then
1 − (p − 1 | J) − (p | J) + (2p − 1 | J) + (2p | J) ≡ 0.
Proof: Let (an, bn) denote the elements of J (1 ≤ n ≤ 3p − 3) and apply the above
theorem to
n=3p−3
n=1
x p−1
n + x
p−1
3p−2 ,
n=3p−3
n=1
an x p−1
n and
n=3p−3
n=1
bn x p−1
n
considered as polynomials over the field containing p elements. Their common zeros
fall into two classes, according to whether x3p−2 = 0 or not. The first class consists of
1 + (p − 1)p
(p | J) + (p − 1)2p
(2p | J) solutions, whereas the second class includes
(p − 1)p
(p − 1 | J) + (p − 1)2p
(2p − 1 | J) solutions.
Springer
On Kemnitz’ conjecture concerning lattice–points in the plane 335
Among the following two assertions the first one is proved quite analogously2
and
entails the second one immedeatedly.
Corollary IIa. If |J| = 3p − 2 or |J| = 3p − 1, then
1 − (p | J) + (2p | J) ≡ 0.
Corollary IIb. If |J| = 3p − 2 or |J| = 3p − 1, then (p | J) = 0 implies (2p | J) ≡
−1.
Corollary III (Alon and Dubiner [1]). If J contains exactly 3p elements whose sum
is ≡ (0, 0), then (p, J) > 0.
Proof: Intending to construct a contradiction thereof we assume that (p|J) = 0. This
obviously implies (p | J − A) = 0, where A denotes an arbitrary element of J. But
as | J − A | = 3p − 1 we obtain (2p, J − A) ≡ −1, which entails (2p | J − A) > 0
and in particular (2p | J) > 0. The condition J ≡ (0, 0), however, yields (2p | J) =
(p | J) and hence (p | J) > 0.
The next two statements are similar to IIa and may also be proved in the same manner.
Corollary IV. If |X| = 4p − 3, then
−1 + (p | X) − (2p | X) + (3p | X) ≡ 0. (a)
and
(p − 1 | X) − (2p − 1 | X) + (3p − 1 | X) ≡ 0. (b)
Corollary V. If | X | = 4p − 3, then
3 − 2(p − 1 | X) − 2(p | X) + (2p − 1 | X) + (2p | X) ≡ 0.
Proof: The first corollary implies
{1 − (p − 1 | I) − (p | I) + (2p − 1 | I) + (2p | I)} ≡ 0,
where the sum is extended over all I ⊂ X of cardinality 3p − 3.
2 The polynomials to be used are both times exactly the same ones as in the preceeding proof, except for
the replacement of the upper summation index by 3p − 2, 3p − 1 resp. and the omission of the term x
p−1
3p−2.
Springer
336 C. Reiher
Analysing the number of times each set is counted one obtains
4p − 3
3p − 3
−
3p − 2
2p − 2
(p − 1 | X) −
3p − 3
2p − 3
(p | X)
+
2p − 2
p − 2
(2p − 1 | X) +
2p − 3
p − 3
(2p | X) ≡ 0.
The reduction of the binomial coefficients leads directly to the claim.
3 Resolution of Kemnitz’ conjecture
Lemma . If | X | = 4p − 3 and (p | X) = 0, then (p − 1 | X) ≡ (3p − 1 | X).
Proof: Let χ denote the number of partititions X = A ∪ B ∪ C satisfying
| A | = p − 1, | B | = p − 2, | C | = 2p
and furthermore
A ≡ (0, 0), B ≡ X, C ≡ (0, 0).
To determine χ, at least modulo p, we first run through all admissible A and employing
Corollary IIb we count for each of them how many possible B are contained in its
complement:
χ ≡
A
(2p | X − A) ≡
A
−1 ≡ −(p − 1 | X)
Working the other way around we infer similarly
χ ≡
B
(2p | X − B) ≡
X−B
−1 ≡ −(3p − 1 | X).
Therefore indeed, by counting the same entities twice, (p − 1 | X) ≡ (3p − 1 | X).
Theorem . Any choice of 4p − 3 lattice-points in the plane contains a subset of
cardinality p, whose centroid is a lattice-point as well.
Proof: Adding up the congruences obtained in the Corollaries IVa, IVb, V and the
previous Lemma one deduces 2 − (p | X) + (3p | X) ≡ 0. Since p is odd this implies
that (p | X) and (3p | X) cannot vanish simultaneously which in turn yields our
assertion (p | X) = 0 via Corollary III.
It was already known to Kemnitz [4], that the above result is also true for p = 2, which
is easily seen by means of the box-principle. As according to fact (1◦
) mentioned in
Springer
On Kemnitz’ conjecture concerning lattice–points in the plane 337
our first section the general statement f (n, 2) = 4n − 3 (for every positive integer n)
immedeatedly follows from the special case where n is a prime, we have thereby
proven Kemnitz’ conjecture.
References
1. Alon, N., Dubiner, D.: A lattice point problem and additive number theory. Combinatorica 15, 301–309
(1995)
2. Erd˝os, P., Ginzburg, A., Ziv, A.: Theorem in the additive number theory. Bull Research Council Israel
10F, 41–43 (1961)
3. Gao, W.: Note on a zero-sum problem. J. Combin. Theory, Series A 95, 387–389 (2001)
4. Kemnitz, A.: On a lattice point problem. Ars Combin. 16b, 151–160 (1983)
5. R´onyai, L.: On a conjecture of Kemnitz. Combinatorica 20, 569–573 (2000)
6. Schmidt, W.M.: Equations Over Finite Fields, An Elementary Approach. Springer Verlag, Lecture Notes
in Math (1976)
Springer