28a.md

Smallest dimension in which Borsuk’s conjecture fails

Description of constant

For a bounded set $X\subset \mathbb{R}^n$, its diameter is

$$ \mathrm{diam}(X)\ :=\ \sup{|x-y|_2:\ x,y\in X}. $$

Let $b(X)$ be the smallest integer $m$ such that $X$ can be written as a union

$$ X = X_1 \cup \cdots \cup X_m $$

with

$$ \mathrm{diam}(X_i) < \mathrm{diam}(X)\qquad \text{for all } i=1,\dots,m. $$

[WX2022-diam-bX]

Define the Borsuk number in dimension $n$ by

$$ b(n)\ :=\ \sup{b(X):\ X\subset\mathbb{R}^n \text{ bounded with } |X|\ge 2}. $$

[Bon2014-bn]

Borsuk’s partition conjecture (1933) asserts that

$$ b(n)\ \le\ n+1 \qquad \text{for all } n\ge 1. $$

Equivalently, every bounded set in $\mathbb{R}^n$ can be partitioned into $n+1$ subsets of strictly smaller diameter. [KK1993-borsuk-conj]

We define $C_{28}$ to be the smallest integer $n\ge 1$ such that Borsuk’s conjecture fails in $\mathbb{R}^n$, i.e.

$$ C_{28}\ :=\ \min{n\ge 1:\ b(n) > n+1}. $$

If Borsuk’s conjecture were true in all dimensions, we would set $C_{28}=\infty$. Since counterexamples are known, $C_{28}$ is finite but its exact value is unknown. [WX2022-open-4-63] [JB2014-ub-64]

Known upper bounds

Bound	Reference	Comments
$1325$	[KK1993], [Jen2018]	First counterexamples in high dimension (Kahn–Kalai); see Jen2018 for detailed discussion of the construction. [KK1993-ub-1325] [Jen2018-jen2018-detail]
$946$	[N1994]	Improves the explicit counterexample dimension. [Bon2014-ub-improvements]
$561$	[R1997]	[Bon2014-ub-improvements]
$560$	[Wei2000]	[Bon2014-ub-improvements]
$323$	[Hin2002]	Spherical-code based construction. [Bon2014-ub-improvements] [Pik2002-hin2002-spherical]
$321$	[Pik2002]	Gives counterexamples in dimensions $321$ and $322$. [Bon2014-ub-improvements] [Pik2002-ub-321-322]
$298$	[HR2003]	[Bon2014-ub-298]
$65$	[Bon2014]	Two-distance counterexample (416 points on $S^{64}\subset \mathbb{R}^{65}$); cannot be partitioned into $83$ smaller-diameter sets (so needs $\ge 84$). [Bon2014-ub-65]
$64$	[JB2014]	Current best: a 352-point two-distance subset giving a counterexample in $\mathbb{R}^{64}$; cannot be partitioned into $70$ smaller-diameter sets (so needs $\ge 71$). [JB2014-ub-64]

Known lower bounds

Bound	Reference	Comments
$4$	[Per1947], [Egg1955], [Gru1957]	Borsuk’s conjecture is true for $n\le 3$. It remains open for $4\le n \le 63$. [WX2022-lb-nle3] [WX2022-open-4-63]

Additional comments and links

• Status of the “first failing dimension.” At present, $$ 4\ \le\ C_{28}\ \le\ 64, $$ and it is open whether the conjecture already fails in dimensions $4,5,\dots,63$; see the surveys [Rai2004], [Zon2021]. [WX2022-lb-nle3] [WX2022-open-4-63] [JB2014-ub-64]

• Two-distance counterexamples. The currently best bounds $65$ and $64$ come from highly structured finite point sets with only two pairwise distances (equivalently, from certain strongly regular graphs); see [Bon2014], [JB2014]. [Bon2014-ub-65] [JB2014-ub-64] [Bon2014-strongly-regular]

• Asymptotic behavior of $b(n)$. Kahn–Kalai [KK1993] showed that $b(n)$ can grow faster than $n+1$ (indeed at least $\exp(c\sqrt{n})$ for some $c&gt;0$), implying failure of Borsuk’s conjecture in all sufficiently large dimensions. [KK1993-asymptotic]

• On the upper-bound side, Lassak [Las1982] proved a general estimate $b(n)\le 2^{n-1}+1$, and Schramm [Sch1988] improved this to an exponential upper bound of the form $b(n)\le (\sqrt{3/2}+o(1))^{n}$. [KK1993-lassak-schramm]

• Wikipedia page on Borsuk’s conjecture

References

• [Bon2014] Bondarenko, Andriy. On Borsuk’s conjecture for two-distance sets. Discrete & Computational Geometry 51 (2014), no. 3, 509–515. Preprint: arXiv:1305.2584

  • [Bon2014-bn] loc: PDF p.1, L14–L18 quote: “For each $n \in N$ the Borsuk number $b(n)$ is the minimal number such that any bounded set in $R^n$ consisting of at least $2$ points can be partitioned into $b(n)$ parts of smaller diameter.”
  • [Bon2014-ub-improvements] loc: PDF p.2, L30–L33 quote: “Improvements on the smallest dimension $n$ such that $b(n) &gt; n + 1$ were obtained by Nilli [14] ($n = 946$), Raigorodskii [17] ($n = 561$), Weißbach [19] ($n = 560$), Hinrichs [8] ($n = 323$), and Pikhurko [16] ($n = 321$).”
  • [Bon2014-ub-298] loc: PDF p.2, L33–L34 quote: “Currently the best known result is that Borsuk’s conjecture is false for $n \ge 298$; see [9].”
  • [Bon2014-ub-65] loc: PDF p.2, L45–L50 quote: “Theorem 1. There is a two-distance subset $\{x_1, \ldots, x_{416}\}$ of the unit sphere $S^{64} \subset R^{65}$ $\ldots$ which cannot be partitioned into $83$ parts of smaller diameter. Hence $b(65) \ge b_2(65) \ge 84$.”
  • [Bon2014-strongly-regular] loc: PDF p.2, L42–L44 quote: “Two basic constructions follow from Euclidean representations of $G_2(4)$ and $Fi_{23}$ strongly regular graphs.”

• [Bor1933] Borsuk, Karol. Drei Sätze über die n-dimensionale euklidische Sphäre. Fundamenta Mathematicae 20 (1933), 177–190. Google Scholar

• [Egg1955] Eggleston, H. G. Covering a three-dimensional set with sets of smaller diameter. Journal of the London Mathematical Society 30 (1955), 11–24. Google Scholar

• [Gru1957] Grünbaum, Branko. A simple proof of Borsuk’s conjecture in three dimensions. Proceedings of the Cambridge Philosophical Society 53 (1957), 776–778. Google Scholar

• [Hin2002] Hinrichs, Aicke. Spherical codes and Borsuk's conjecture. Discrete Mathematics 243 (2002), 253–256. Google Scholar

• [HR2003] Hinrichs, Aicke; Richter, Christian. New sets with large Borsuk numbers. Discrete Mathematics 270 (2003), no. 1–3, 137–147. DOI: 10.1016/S0012-365X(02)00833-6

• [JB2014] Jenrich, Thomas; Brouwer, Andries E. A 64-dimensional counterexample to Borsuk’s conjecture. Electronic Journal of Combinatorics 21 (2014), no. 4, Paper 4.29. (Journal PDF: EJC 4.29) Preprint: arXiv:1308.0206

  • [JB2014-ub-64] loc: PDF p.3, L33–L36 quote: “Because $\{y_i: i \in C \cup B_1\}$ contains $352$ vectors and a subset of smaller diameter contains at most $5$ vectors, a division into less than $71$ parts of smaller diameter is impossible.”

• [Jen2018] Jenrich, Thomas. On the counterexamples to Borsuk’s conjecture by Kahn and Kalai. Preprint (2018). arXiv:1809.09612

  • [Jen2018-jen2018-detail] loc: PDF p.1, L12–L15 quote: “This updated article takes a closer look at that derivation, gives an own, much more detailed and formal version of it that delivers the improved/corrected formula, and contains some further conclusions.”

• [KK1993] Kahn, Jeff; Kalai, Gil. A counterexample to Borsuk’s conjecture. Bulletin of the American Mathematical Society (N.S.) 29 (1993), no. 1, 60–62. Preprint: arXiv:math/9307229

  • [KK1993-borsuk-conj] loc: PDF p.1, L12–L14 quote: “Problem 1 (Borsuk). Is it true that every set of diameter one in $R^d$ can be partitioned into $d + 1$ closed sets of diameter smaller than one? The conjecture that this is true has come to be called Borsuk’s conjecture.”
  • [KK1993-ub-1325] loc: PDF p.3, L111–L112 quote: “Our construction shows that Borsuk’s conjecture is false for $d = 1{,}325$ and for every $d &gt; 2{,}014$.”
  • [KK1993-asymptotic] loc: PDF p.1, L6–L10 quote: “Abstract. Let $f(d)$ be the smallest number so that every set in $R^d$ of diameter $1$ can be partitioned into $f(d)$ sets of diameter smaller than $1$. $\ldots$ We prove that $f(d) \ge (1.2)^{\sqrt{d}}$ for large $d$.”
  • [KK1993-lassak-schramm] loc: PDF p.1, L21–L26 quote: “Lassak [14] proved that $f(d) \le 2^{d-1} + 1$, and Schramm [16] showed that for every $\varepsilon$, if $d$ is sufficiently large, $f(d) \le (\sqrt{3/2} + \varepsilon)^d$.”

• [Las1982] Lassak, Marek. An estimate concerning Borsuk’s partition problem. Bulletin of the Polish Academy of Sciences. Mathematics 30 (1982), 449–451. Google Scholar

• [N1994] Nilli, A. On Borsuk’s problem. In: Jerusalem Combinatorics ’93, Contemporary Mathematics 178, Amer. Math. Soc. (1994), 209–210. Google Scholar

• [Per1947] Perkal, Julian. Sur la subdivision des ensembles en parties de diamètre inférieur. Colloquium Mathematicum 1 (1947), 45. Google Scholar

• [Pik2002] Pikhurko, Oleg. Borsuk's conjecture fails in dimensions 321 and 322. Preprint (2002). arXiv:math/0202112

  • [Pik2002-hin2002-spherical] loc: PDF p.3, L158–L159 quote: “[4] A. Hinrichs, Spherical codes and Borsuk’s conjecture, Discrete Math. 243 (2002), 253–256.”
  • [Pik2002-ub-321-322] loc: PDF p.1, L1–L3 quote: “Borsuk’s Conjecture Fails in Dimensions $321$ and $322$”

• [R1997] Raigorodskii, A. M. On the dimension in Borsuk’s problem. Russian Mathematical Surveys 52 (1997), no. 6, 1324–1325. MathNet

• [Rai2004] Raigorodskii, Andreĭ M. The Borsuk partition problem: the seventieth anniversary. The Mathematical Intelligencer 26 (2004), 4–12. DOI: 10.1007/BF02986745

• [Sch1988] Schramm, Oded. Illuminating sets of constant width. Mathematika 35 (1988), no. 2, 180–199. Google Scholar

• [Wei2000] Weißbach, Bernulf. Sets with large Borsuk number. Beiträge zur Algebra und Geometrie 41 (2000), 417–423. Google Scholar

• [WX2022] Wang, Jun; Xue, Fei. Borsuk’s partition problem in four-dimensional $\ell_p$ space. Preprint (2022). arXiv:2206.15277

  • [WX2022-diam-bX] loc: PDF p.1, L19–L30 quote: “Let $d(X)$ denote the diameter of a bounded set $X$ of $E^n$ defined by $d(X) = \sup\{|x, y| : x, y \in X\}$, where $|x, y|$ denotes the Euclidean distance between $x$ and $y$. Let $b(X)$ be the smallest number of subsets $X_1, X_2, \ldots, X_{b(X)}$ of $X$ such that $\ldots$ and $d(X_i) &lt; d(X)$ holds for all $i \le b(X)$.”
  • [WX2022-open-4-63] loc: PDF p.1, L4–L6 quote: “Up to now, the problem is still open for $4 \le n \le 63$.”
  • [WX2022-lb-nle3] loc: PDF p.1, L35–L39 quote: “K. Borsuk [1] proved that the inequality $b(X) \le 3$ holds for any bounded set $X \subseteq E^2$. For $n = 3$, Borsuk’s conjecture was confirmed by H. G. Eggleston [4] in 1955.”

• [Zon2021] Zong, Chuanming. Borsuk’s partition conjecture. Japanese Journal of Mathematics 16 (2021), 185–201. DOI: 10.1007/s11537-021-2007-7

Contribution notes

Prepared with assistance from ChatGPT 5.2 Pro.