Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 41 (2000), No. 2, 417-423.

Sets with Large Borsuk Number

Bernulf Weißbach

Department of Mathematics/IAG, University of Magdeburg Universitätsplatz 2, D-39106 Magdeburg, Germany e-mail: bernulf.weissbach@mathematik.uni-magdeburg.de

Abstract. We construct sets in Euclidean spaces of dimension d = \binom{4m−2}{2}, where m is a power of a prime, with the property that they can only be covered with a large number of sets having smaller diameter. Thereby we generalize a result of A.M. Raigorodskii and, in addition, we prove that there exists a counterexample to the so called “Borsuk-conjecture” already in dimension \binom{34}{2} − 1 = 560.

1. Introduction

In 1933 Karol Borsuk [3] asked the following question (literal copy):

Lässt sich jede beschränkte Teilmenge E des Raumes R^{n} in (n + 1) Mengen zerlegen, von denen jede einen kleineren Durchmesser als E hat? (Can every bounded subset E of the Euclidean space ℝ^{n} be partitioned into n + 1 sets, such that each of these sets has a smaller diameter than E?)

Of course, we have to assume that the diameter of E is positive, i.e., it consists of at least 2 points. In order to present some of the known results concerning this problem we need some notation. In the following let E be a subset of the d-dimensional Euclidean space ℝ^{d} with diameter diam E = δ > 0. The smallest positive integer k with the property that E can be partitioned into k sets with diameter less than δ is called the Borsuk number b(E) of the set E. The current best upper bound on b(E) depending only on the dimension d is due to Schramm [11]. The number

b(d) := max {b(E) : E ⊂ ℝ^{d}, 0 < diam E < ∞} .

0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix} 2000 Heldermann Verlag

will be called the d-th Borsuk number. For the d-dimensional unit ball B^{d} we have b(B^{d}) = d + 1 and this observation was the motivation for Borsuk’s question. Nowadays this question is known as Borsuk’s conjecture although Borsuk himself never posed the problem as a conjecture. The question was answered in the affirmative way in dimensions d ≤ 3 and for all smooth convex bodies. In spite of these supporting results the validity of the conjecture was doubted for quite a while. Paul Erdös [4] and C.A. Rogers [10] made some comments in this direction. Nevertheless, it was a big surprise, when 1992 Jeff Kahn and Gil Kalai [7] proved b(d) > d + 1 provided d is large enough. More precisely, they showed

Theorem 1.1. (Kahn&Kalai) Let m be a power of a prime p and let d(m) = \binom{4m}{2}−1. Then there exists a set E ⊂ ℝ^{d(m)} with

b(E) ≥ q(m) := \frac{\frac{1}{2} \binom{4m}{2m}}{2\binom{4m−1}{m−1}} = \begin{matrix}( & {4m \atop 2m} & ) \\ ( & {4m \atop m} & ) \end{matrix}.  (1.1)

Obviously, q(m) > d(m) + 1 if m is sufficiently large. Without giving further details Kahn&Kalai claimed that their proof leads to a counterexample in dimension d(13) = 1325; maybe they made a flaw at this point since q(13) < 781. The smallest admissible number m with q(m) > d(m) + 1 is 16 and we have d(16) = 2015. The book [12] of Chuanming Zong contains a detailed description of a slightly different construction of Kahn&Kalai’s counterexample. The disproof of Borsuk’s conjecture due to Kahn and Kalai is based on a result of P. Frankl and J. Wilson [5]. From today’s perspective it is quite astonishing that Frankl&Wilson themselves didn’t find a counterexample, because they were very close to it. The basic theorem of Frankl&Wilson used for the construction of a counterexample reads as follows:

Theorem 1.2. (Frankl&Wilson) Let m be a power of a prime, n = 4m, and let X = {x = [x_{1}, …, x_{n}] ∈ \{−1, 1\}^{n}, ∑_{i=1}^{n} x_{i} = 0\}. Then #X = \binom{4m}{2m} and every subset X̃ ⊂ X with #X̃ > 2\binom{4m−1}{m−1} contains an orthogonal pair of points.

Now it is easy to see that the set X^{∗} = {x^{∗} = x^{⊺}x : x ∈ X} provides a counterexample to Borsuk’s conjecture: X^{∗} lies in an affine space of dimension d(m) in ℝ^{d^{2}} and consists of exactly \frac{1}{2} \binom{4m}{2m} points. Since ⟨u^{∗}, v^{∗}⟩ = ⟨u, v⟩^{2} we know by the theorem of Frankl&Wilson that every subset of X^{∗} with more than 2\binom{4m−1}{m−1} points contains a pair of points whose distance is equal to the diameter of X^{∗}. Thus X^{∗} can not be partitioned in less than q(m) sets having a smaller diameter than diam X^{∗}. The relation to the result of Kahn&Kalai is obvious. The main difference is that the set E constructed by Kahn&Kalai consists of 0/1-vectors.

In 1993 A. Nilli [8] first used the tensorial products for the construction of counterexamples. In a remarkable, brief and clear presentation (for a more detailed version we refer to [2]) he proved the following result:

Theorem 1.3. (Nilli) Let p ≥ 3 be a prime and let d_{0}(p) = \binom{4p}{2}. There exists a set E ⊂ ℝ^{d_{0}(p)} with

b(E) ≥ q_{1}(p) := \frac{2^{4p−2}}{∑{p−1 \atop i=0} \binom{4p−1}{i}}.  (1.2)

The bound q_{1}(p) is much larger than the number q(p) and already for p = 11 we get q_{1}(P) > d_{0}(p) + 1. Thus the answer to Borsuk’s question is “No” for d = \binom{44}{2} = 946. By a slight modification of Nilli’s construction J. Grey and B. Weißbach [6] could lower the dimension to d_{1}(p) = \binom{4p−1}{2} for which (1.2) holds. Obviously, we have q_{1}(11) > d_{1}(11) + 1 and therefore, they found a counterexample already in dimension d = \binom{43}{2} = 903. However, in the same year A.M. Raigorodskii [9] proved a much better bound. He constructed a counterexample in dimension d = \binom{34}{2} = 561. His construction also is based on the work of A. Nilli. In a first step Weißbach generalized Raigorodskii’s investigations to

Theorem 1.4. (Weißbach) Let p ≥ 3 be a prime and let d_{2}(p) = \binom{4p−2}{2}. There exists a set E ⊂ ℝ^{d_{2}(p)} such that

b(E) ≥ q_{2}(p) := \frac{2^{4p−4}}{∑{p−2 \atop i=0} \binom{4p−3}{i}}.  (1.3)

A detailed presentation of his proof can be found in the book “Proofs from THE BOOK” by M. Aigner and G.M. Ziegler [1]. We remark that the lower bound on b(E) given in this book is insignificantly worse than in (1.3). Again for p = 11 we have q_{2}(p) > d_{2}(p) + 1 and thus one has a counterexample in dimension d = 861.

In order to get the bound 561 Raigorodskii also showed that Theorem 1.4 remains valid for the number 9 = 3^{2} instead of a prime p. The purpose of the present paper is to embed Raigorodskii’s result in a more general context. We show that the prime p in Theorem 1.4 may be replaced by any power p^{α} ≥ 3 of a prime p. In addition we will show that there exists a counterexample to Borsuk’s conjecture in dimension d = 560.

2. The construction

Let p be a prime, m = p^{α} ≥ 3 and let n = 4m − 2. In ℝ^{n} we consider the set

F := {x = [x_{1}, …, x_{n}] ∈ {−1, 1}^{n} : #{i : x_{i} = −1} ≡ 0 mod 2, x_{n} = 1} ,  (2.1)

and let F^{∗} := {x^{∗} = x^{⊺}x : x ∈ F }. We show

Theorem 2.1. The Borsuk number of F^{∗} is not less than

q_{2}(m) = \frac{2^{4m−4}}{∑{m−2 \atop j=0} \binom{4m−3}{j}}.

For the proof we note some basic facts first.

1. Since x_{n} = 1 the map x → x^{⊺}x is an injective map on F and thus

#F^{∗} = #F = 2^{4m−4}.  (2.2)

2. Let u = [u_{1}, …, u_{n}], v = [v_{1}, …, v_{n}] ∈ F and let u^{∗} = u^{⊺}u, v^{∗} = v^{⊺}v be the corresponding points in F^{∗}. Then we have

⟨u^{∗}, v^{∗}⟩ = ∑_{h,k=1}^{n}(u_{h}u_{k})(v_{h}v_{k}) = (∑_{h=1}^{n} u_{h}v_{h})(∑_{k=1}^{n} u_{k}v_{k}) = ⟨u, v⟩^{2}.

3. The Euclidean length of each vector of F is \sqrt{n}, and for the inner product of two vectors u, v ∈ F we find ⟨u, v⟩ ≡ 2 mod 4. More precisely we have

⟨u, v⟩ + 2 = 4z, z ∈ {−(m − 2), −(m − 3), …, (m − 1), m}.  (2.3)

One way to verify (2.3) is the following. Let u = [1, …, 1] − 2[ū_{1}, …, ū_{n}] with [ū_{1}, …, ū_{n}] ∈ {0, 1}^{n} and ∑_{i=1}^{n} ū_{i} ≡ 0 mod 2. If we write v in the same way, then we observe, that −n = −4m + 2 < ⟨u, v⟩, because u_{n} = v_{n} = 1 implies −x ∉ F for all x ∈ F.

From these facts we can deduce an upper bound on the Euclidean distance of two points of F^{∗}

∥u^{∗} − v^{∗}∥^{2} = ∥u^{∗}∥^{2} + ∥v^{∗}∥^{2} − 2⟨u^{∗}, v^{∗}⟩ = ∥u∥^{4} + ∥v∥^{4} − 2⟨u, v⟩^{2} ≤ 2n^{2} − 8,

where equality holds iff |⟨u, v⟩| = 2. In other words, each pair of points u, v in F with |⟨u, v⟩| = 2 leads to a pair of points u^{∗}, v^{∗} attaining the diameter of the set F^{∗}. The next fundamental proposition says that any sufficiently large subset of F contains such a pair of points.

Proposition 2.1. Let G ⊂ F with #G > ∑_{j=0}^{m−2} \binom{4m−3}{j}. Then there exists u, v ∈ G with |⟨u, v⟩| = 2.

This proposition immediately implies Theorem 2.1, because now we know that any subset G^{∗} ⊂ F^{∗} with #G^{∗} > ∑_{j=0}^{m−2} \binom{4m−3}{j} contains two points with ∥u^{∗}−v^{∗}∥ = diam (F^{∗}). However, by the pigeonhole principle and since #F^{∗} = 2^{4m−4} we see that any partition of F^{∗} in sets with smaller diameter consists of at least ⌈q_{2}(m)⌉ sets.

For the proof of the proposition let G ⊂ F be a set with |⟨u, v⟩| ≠ 2 for all u, v ∈ G. In the following we want to estimate the cardinality of such a set. To this end we use an idea of A. Nilli: We assign injectively to each point u ∈ F a map φ_{u} : F → ℤ, x → φ_{u}(x), where φ_{u}(x) is given by

φ_{u}(x) = φ(\frac{1}{4}(⟨u, x⟩ + 2)), φ(z) := \binom{m − 1 − z}{m − 2} = (−1)^{m}\binom{z − 2}{m − 2}.

Now the following lemma holds:

Lemma 2.1. Let m = p^{α} ≥ 3 be a power of a prime and z ∈ {−(m − 2), …, m}. Then \binom{m−1−z}{m−2} ≢ 0 mod p holds if and only if z ∈ \{0, 1, m\}.

The proof is simple. It is sufficient to show that \binom{m+s}{m−2} is divisible by p for s ∈ \{0, …, m−3\}. If g ≢ 0 (mod m) is dissected in prime factors then the prime p occurs precisely as frequently as in the residual modulo m = p^{α}. The factors of the numerator from \binom{m+s}{m−2} belong to m − 2 residue classes modulo m. Among these classes the class [0] = [m] occurs for the values of s which we have to consider. This class does not occur among the m − 2 residue classes for the factors of the denominator. Consequently, the numerator contains at least one factor p more than the denominator.

Since for all u, v ∈ G we assume |⟨u, v⟩| ≠ 2 the lemma implies

φ_{u}(v) ≢ 0 mod p ⇔ u = v for all u, v, ∈ G.  (2.4)

This shows that different points u ∈ G lead to different maps φ_{u}. Next we show that these maps are rational independent. Otherwise there exist integers λ_{u}, u ∈ G, with gcd(λ_{u} : u ∈ G) = 1 such that

0 = ∑_{u∈G} λ_{u}φ_{u}(x) = λ_{v}φ_{v}(x) + ∑_{u∈G\{v}} λ_{u}φ_{u}(x)

for all x ∈ F. With x = v we get

0 = λ_{v}φ_{v}(v) + ∑_{u∈G\{v}} λ_{u}φ_{u}(v),

where φ_{v}(v) ≢ 0 mod p and φ_{u}(v) ≡ 0 mod p for u ≠ v. Hence λ_{v} ≡ 0 mod p for all v ∈ G which contradicts the assumption gcd(λ_{u} : u ∈ G) = 1.

In order to estimate #{φ_{u} : u ∈ G} we note that φ_{u}(x) is a polynomial of degree m − 2 with rational coefficients in the n − 1 variables x_{1}, …, x_{n−1};

φ_{u}(x) = ∑_{0≤i_{1}+···+i_{n−1}≤m−2} a_{i_{1}...i_{n−1}}x_{1}^{i_{1}} ⋯ x_{n−1}^{i_{n−1}}.

Now for x ∈ F we have x_{i}^{2} = 1 and thus on the set F the polynomial φ_{u}(x) can be regarded as a multi-linear polynomial φ̄_{u}(x) with rational coefficients of degree at most (m − 2). Of course, (2.4) remains true for the polynomials φ̄_{u}(x). Therefore #G = #{φ̄_{u}(x) : u ∈ G} and the latter set of multi-linear polynomials is rational independent. Now the set of all multi-linear polynomials with (n − 1) variables with rational coefficients and of degree at most (n − 2) form a vector space V over ℚ. A basis of this space is given by the monomials

1, x_{i_{1}}, x_{i_{1}}x_{i_{2}}, …, x_{i_{1}}x_{i_{2}} ⋯ x_{i_{m−2}}, i_{j} ∈ {1, …, n − 1},

and since #G ≤ dim V the proposition is proven.

3. Counterexamples to Borsuk’s conjecture

The bound for the Borsuk number of the set F^{∗} given in Theorem 2.1 grows exponentially; it is q_{2}(m) > \frac{e}{64m^{2}} (\frac{27}{16})^{m}. (This follows from the rough estimate ∑_{j=0}^{m−2} \binom{4m−3}{j} < m\binom{4m}{m} and Stirling’s formula, cf. [1], 83–88). Since the matrix x^{⊺}x is symmetric and since all elements on the main diagonal are 1 for x ∈ F, the dimension of the affine hull of F^{∗} is equal to \binom{n}{2} = (2m − 1)(4m − 3) = d_{2}(m). Therefore F^{∗} is a counterexample to Borsuk’s conjecture, if m is large enough.

With m = 3^{2} we get d_{2}(9) = 561 and ⌈q_{2}(9)⌉ = 759. This is the result of A.M. Raigorodskii. With some extra work it should also be possible to prove q_{2}(m) > d_{2}(m) + 1 for all m ≥ 9. It seems to be worth to mention that for m = 2^{3} one gets d_{2}(8) = 435 and ⌈q_{2}(8)⌉ = 432. So the gap is rather small and one has “almost” a counterexample in dimension 435. Nevertheless, one can improve Raigorodskii’s bound by 1. To this end we note that ⌈q_{2}(9)⌉ is much larger than what is needed and this means that for m = 9 we can drop many points from the set F, F^{∗}, respectively. The correctness of the proposition is not affected by this. We just have to ensure that we still have so many points that the set can not be partitioned into 562 sets with a smaller diameter. Now we observe that

⌈\frac{3}{4}q_{2}(9)⌉ = ⌈\frac{\frac{3}{4} · 2^{32}}{∑{7 \atop j=0} \binom{33}{j}}⌉ = 569 > 562.

Thus for each subset F̄ ⊂ F with #F̄ ≥ 3·2^{30} the corresponding set F̄^{∗} can not be partitioned into less than dim(aff F̄^{∗}) + 1 sets having a smaller diameter. With the right choice of F̄ one can construct a set F̄^{∗} whose dimension is less than 561. We choose

F̄ = {x ∈ F : [x_{1}, x_{2}, x_{3}] ∉ {[−1, −1, −1], [1, 1, 1]}} .  (3.1)

It is easy to see that #F̄ = \frac{6}{8}#F = 3 · 2^{30}. With x_{1} + x_{2} + x_{3} = ±1 we get (x_{1} + x_{2} + x_{3})^{2} = 1 and thus x_{1}x_{2} + x_{2}x_{3} + x_{3}x_{1} = −1. This implies that dim(aff F̄^{∗}) = dim(aff F^{∗}) − 1 and we have shown

Theorem 3.1. There exists a counterexample to Borsuk’s conjecture in dimension d = 560.

Finally, we would like to comment this new “record” with the words

parturient montes nascetur ridiculus mus.

Quintus Horatius Flaccus (Ars poëtica 139).

The author thanks Günter M. Ziegler for helpful comments.

References

[1] Aigner, M.; Ziegler, G. M.: Proofs from THE BOOK. Springer-Verlag Berlin Heidelberg New York 1998.

[2] Boltyanski, V.; Martini, H.; Soltan, P. S.: Excursions into combinatorial geometry. Springer-Verlag Berlin Heidelberg New York 1997.

[3] Borsuk, K.: Drei Sätze über die n-dimensionale euklidische Sphäre. Fund. Math. 20 (1933), 177–190.

[4] Erdös, P.: My Scottish book “problems”. In: The Scottish Book, Mathematics from the Scottish Cafe (Hrsg. R. D. Mauldin), Birkhäuser Boston Basel Stuttgart 1981.

[5] Frankl, P.; Wilson, R.: Intersection theorems with geometric consequences. Combinatorica 1 (1981), 357–368.

[6] Grey, J.; Weißbach, B.: Ein weiteres Gegenbeispiel zur Borsukschen Vermutung. Univ. Magdeburg, Fakultät für Mathematik, Preprint 25, 1997.

[7] Kahn, J.; Kalai, G.: A counterexample to Borsuk’s conjecture. Bull. Amer. Math. Soc. 29 (1993), 60–62.

[8] Nilli, A.: On Borsuk’s problem. “Jerusalem Combinatorics ’93”, Contemporary Math. 178, Amer. Math. Soc. 1994, 209–210.

[9] Raigorodskii, A. M.: O razmernosti v probleme Borsuka [russ.], Uspekhi Mat. Nauk (6) 52 (1997), 181–182. On the dimension in Borsuk’s problem. Russian Math. Surveys 52 (1997), 1324–1325.

[10] Rogers, C. A.: Some problems in the geometry of convex bodies. In: The Geometric Vein - The Coxeter, Festschrift (Hrsg. C. Davis - B. Grünbaum - F. A. Sherk), Springer-Verlag New York 1981, 279–284.

[11] Schramm, O.: Illuminating sets of constant width. Mathematika 35 (1988), 180–189.

[12] Zong, Ch.: Strange phenomena in convex and discrete geometry. Springer-Verlag Berlin Heidelberg New York 1996.

Received July 29, 1999