Smallest dimension in which Borsuk’s conjecture fails

Description of constant

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

$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 \dots \cup X_{m}$

with

$diam (X_{i}) < diam (X) for all i = 1, \dots, m .$

Define the Borsuk number in dimension $n$ by

$b (n) := sup {b (X) : X \subset R^{n} bounded with ∣ X ∣ \geq 2} .$

Borsuk’s partition conjecture (1933) asserts that

$b (n) \leq n + 1 for all n \geq 1.$

Equivalently, every bounded set in $R^{n}$ can be partitioned into $n + 1$ subsets of strictly smaller diameter. <a href="#KK1993-borsuk-conj">[KK1993-borsuk-conj]</a>

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

$C_{28} := min {n \geq 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. <a href="#WX2022-open-4-63">[WX2022-open-4-63]</a> <a href="#JB2014-ub-64">[JB2014-ub-64]</a>

Known upper bounds

Bound	Reference	Comments
$1325$	[[KK1993](#KK1993)], [[Jen2018](#Jen2018)]	First counterexamples in high dimension (Kahn–Kalai); see [Jen2018](#Jen2018) for detailed discussion of the construction. <a href="#KK1993-ub-1325">[KK1993-ub-1325]</a> <a href="#Jen2018-jen2018-detail">[Jen2018-jen2018-detail]</a>
$946$	[[N1994](#N1994)]	Improves the explicit counterexample dimension. <a href="#Bon2014-ub-improvements">[Bon2014-ub-improvements]</a>
$561$	[[R1997](#R1997)]	<a href="#Bon2014-ub-improvements">[Bon2014-ub-improvements]</a>
$560$	[[Wei2000](#Wei2000)]	<a href="#Bon2014-ub-improvements">[Bon2014-ub-improvements]</a>
$323$	[[Hin2002](#Hin2002)]	Spherical-code based construction. <a href="#Bon2014-ub-improvements">[Bon2014-ub-improvements]</a> <a href="#Pik2002-hin2002-spherical">[Pik2002-hin2002-spherical]</a>
$321$	[[Pik2002](#Pik2002)]	Gives counterexamples in dimensions $321$ and $322$ . <a href="#Bon2014-ub-improvements">[Bon2014-ub-improvements]</a> <a href="#Pik2002-ub-321-322">[Pik2002-ub-321-322]</a>
$298$	[[HR2003](#HR2003)]	<a href="#Bon2014-ub-298">[Bon2014-ub-298]</a>
$65$	[[Bon2014](#Bon2014)]	Two-distance counterexample (416 points on $S^{64} \subset R^{65}$ ); cannot be partitioned into $83$ smaller-diameter sets (so needs $\geq 84$ ). <a href="#Bon2014-ub-65">[Bon2014-ub-65]</a>
$64$	[[JB2014](#JB2014)]	A 352-point two-distance subset giving a counterexample in $R^{64}$ ; cannot be partitioned into $70$ smaller-diameter sets (so needs $\geq 71$ ). <a href="#JB2014-ub-64">[JB2014-ub-64]</a>
$63$	[[Gri2026](#Gri2026)]	Current best: a $321$ -point subset of $R^{63}$ whose smaller-diameter subsets have size at most $5$ , so at least $65 > 64$ parts are required.

Known lower bounds

Bound	Reference	Comments
$4$	[[Per1947](#Per1947)], [[Egg1955](#Egg1955)], [[Gru1957](#Gru1957)]	Borsuk’s conjecture is true for $n \leq 3$ . After the $63$ -dimensional construction, the first possible failing dimension remains open for $4 \leq n \leq 62$ . <a href="#WX2022-lb-nle3">[WX2022-lb-nle3]</a>

Additional comments and links

Status of the “first failing dimension.” At present, $4 \leq C_{28} \leq 63,$ and it is open whether the conjecture already fails in dimensions $4, 5, \dots, 62$ ; see the surveys [[Rai2004](#Rai2004)], [[Zon2021](#Zon2021)]. <a href="#WX2022-lb-nle3">[WX2022-lb-nle3]</a> <a href="#JB2014-ub-64">[JB2014-ub-64]</a> <a href="#Gri2026">[Gri2026]</a>

Structured finite counterexamples. The bounds $65$ and $64$ come from highly structured two-distance point sets associated to strongly regular graphs. The bound $63$ modifies the $G_{2} (4)$ construction by taking a $320$ -point subset in a codimension- $2$ subspace and adding one scaled projected point. See [[Bon2014](#Bon2014)], [[JB2014](#JB2014)], and [[Gri2026](#Gri2026)]. <a href="#Bon2014-ub-65">[Bon2014-ub-65]</a> <a href="#JB2014-ub-64">[JB2014-ub-64]</a> <a href="#Bon2014-strongly-regular">[Bon2014-strongly-regular]</a>

Asymptotic behavior of $b (n)$ . Kahn–Kalai [[KK1993](#KK1993)] showed that $b (n)$ can grow faster than $n + 1$ (indeed at least $exp (c n)$ for some $c > 0$ ), implying failure of Borsuk’s conjecture in all sufficiently large dimensions. <a href="#KK1993-asymptotic">[KK1993-asymptotic]</a>

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

Wikipedia page on Borsuk’s conjecture

References

<a id="Bon2014"></a>[Bon2014] Bondarenko, Andriy. On Borsuk’s conjecture for two-distance sets. Discrete & Computational Geometry 51 (2014), no. 3, 509–515. Preprint: arXiv:1305.2584
<a id="Bon2014-bn"></a>[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.”
<a id="Bon2014-ub-improvements"></a>[Bon2014-ub-improvements] loc: PDF p.2, L30–L33 quote: “Improvements on the smallest dimension $n$ such that $b (n) > 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$ ).”
<a id="Bon2014-ub-298"></a>[Bon2014-ub-298] loc: PDF p.2, L33–L34 quote: “Currently the best known result is that Borsuk’s conjecture is false for $n \geq 298$ ; see [9].”
<a id="Bon2014-ub-65"></a>[Bon2014-ub-65] loc: PDF p.2, L45–L50 quote: “Theorem 1. There is a two-distance subset $x_{1}, \dots, x_{416}$ of the unit sphere $S^{64} \subset R^{65}$ $\dots$ which cannot be partitioned into $83$ parts of smaller diameter. Hence $b (65) \geq b_{2} (65) \geq 84$ .”
<a id="Bon2014-strongly-regular"></a>[Bon2014-strongly-regular] loc: PDF p.2, L42–L44 quote: “Two basic constructions follow from Euclidean representations of $G_{2} (4)$ and $F i_{23}$ strongly regular graphs.”

<a id="Bor1933"></a>[Bor1933] Borsuk, Karol. Drei Sätze über die n-dimensionale euklidische Sphäre. Fundamenta Mathematicae 20 (1933), 177–190. Google Scholar

<a id="Egg1955"></a>[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

<a id="Gru1957"></a>[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

<a id="Gri2026"></a>[Gri2026] Grinsztajn, Max. A $63$ -dimensional counterexample to Borsuk's conjecture (2026). Proof PDF, verification script, exported DIMACS certificates, and optional Sage verification of the exported certificates: GitHub repository.

<a id="Hin2002"></a>[Hin2002] Hinrichs, Aicke. Spherical codes and Borsuk's conjecture. Discrete Mathematics 243 (2002), 253–256. Google Scholar

<a id="HR2003"></a>[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-600833-6)

<a id="JB2014"></a>[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
<a id="JB2014-ub-64"></a>[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.”

<a id="Jen2018"></a>[Jen2018] Jenrich, Thomas. On the counterexamples to Borsuk’s conjecture by Kahn and Kalai. Preprint (2018). arXiv:1809.09612
<a id="Jen2018-jen2018-detail"></a>[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.”

<a id="KK1993"></a>[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
<a id="KK1993-borsuk-conj"></a>[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.”
<a id="KK1993-ub-1325"></a>[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 > 2, 014$ .”
<a id="KK1993-asymptotic"></a>[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$ . $\dots$ We prove that $f (d) \geq (1.2)^{d}$ for large $d$ .”
<a id="KK1993-lassak-schramm"></a>[KK1993-lassak-schramm] loc: PDF p.1, L21–L26 quote: “Lassak [14] proved that $f (d) \leq 2^{d - 1} + 1$ , and Schramm [16] showed that for every $ε$ , if $d$ is sufficiently large, $f (d) \leq (3/2 + ε)^{d}$ .”

<a id="Las1982"></a>[Las1982] Lassak, Marek. An estimate concerning Borsuk’s partition problem. Bulletin of the Polish Academy of Sciences. Mathematics 30 (1982), 449–451. Google Scholar

<a id="N1994"></a>[N1994] Nilli, A. On Borsuk’s problem. In: Jerusalem Combinatorics ’93, Contemporary Mathematics 178, Amer. Math. Soc. (1994), 209–210. Google Scholar

<a id="Per1947"></a>[Per1947] Perkal, Julian. Sur la subdivision des ensembles en parties de diamètre inférieur. Colloquium Mathematicum 1 (1947), 45. Google Scholar

<a id="Pik2002"></a>[Pik2002] Pikhurko, Oleg. Borsuk's conjecture fails in dimensions 321 and 322. Preprint (2002). arXiv:math/0202112
<a id="Pik2002-hin2002-spherical"></a>[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.”
<a id="Pik2002-ub-321-322"></a>[Pik2002-ub-321-322] loc: PDF p.1, L1–L3 quote: “Borsuk’s Conjecture Fails in Dimensions $321$ and $322$ ”

<a id="R1997"></a>[R1997] Raigorodskii, A. M. On the dimension in Borsuk’s problem. Russian Mathematical Surveys 52 (1997), no. 6, 1324–1325. MathNet

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

<a id="Sch1988"></a>[Sch1988] Schramm, Oded. Illuminating sets of constant width. Mathematika 35 (1988), no. 2, 180–199. Google Scholar

<a id="Wei2000"></a>[Wei2000] Weißbach, Bernulf. Sets with large Borsuk number. Beiträge zur Algebra und Geometrie 41 (2000), 417–423. Google Scholar

<a id="WX2022"></a>[WX2022] Wang, Jun; Xue, Fei. Borsuk’s partition problem in four-dimensional $ℓ_{p}$ space. Preprint (2022). arXiv:2206.15277
<a id="WX2022-diam-bX"></a>[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}, \dots, X_{b (X)}$ of $X$ such that $\dots$ and $d (X_{i}) < d (X)$ holds for all $i \leq b (X)$ .”
<a id="WX2022-open-4-63"></a>[WX2022-open-4-63] loc: PDF p.1, L4–L6 quote: “Up to now, the problem is still open for $4 \leq n \leq 63$ .”
<a id="WX2022-lb-nle3"></a>[WX2022-lb-nle3] loc: PDF p.1, L35–L39 quote: “K. Borsuk [1] proved that the inequality $b (X) \leq 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.”

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

What counts as progress

A better upper or lower bound, with a proof or a construction whose value is re-computed by published code (reproducible), ideally with a certificate a deterministic checker can validate.
A formal proof (Lean) of a known bound, or a precise error in a claimed one.
New references for the tables above (literature claims).

Source and licence

Imported from the crowdsourced repository of optimization constants (Terence Tao and contributors), commit 2c1968cd520b, Apache License 2.0; reformatted for this page. New records should also be reported there.