Borsuk's conjecture

The Borsuk problem in geometry, for historical reasons^{[note 1]} incorrectly called Borsuk's conjecture, is a question in discrete geometry. It is named after Karol Borsuk.

Problem

In 1932, Karol Borsuk showed^[2] that an ordinary 3-dimensional ball in Euclidean space can be easily dissected into 4 solids, each of which has a smaller diameter than the ball, and generally $n$ -dimensional ball can be covered with $n + 1$ compact sets of diameters smaller than the ball. At the same time he proved that $n$ subsets are not enough in general. The proof is based on the Borsuk–Ulam theorem. That led Borsuk to a general question:^[2]

Die folgende Frage bleibt offen: Lässt sich jede beschränkte Teilmenge $E$ des Raumes $\mathbb {R} ^{n}$ in ( $n + 1$ ) Mengen zerlegen, von denen jede einen kleineren Durchmesser als $E$ hat?
The following question remains open: Can every bounded subset $E$ of the space $\mathbb {R} ^{n}$ be partitioned into ( $n + 1$ ) sets, each of which has a smaller diameter than $E$ ?

— Drei Sätze über die n-dimensionale euklidische Sphäre

The question was answered in the positive in the following cases:

$n = 2$ — which is the original result by Karol Borsuk (1932).
$n = 3$ — shown by Julian Perkal (1947),^[3] and independently, 8 years later, by H. G. Eggleston (1955).^[4] A simple proof was found later by Branko Grünbaum and Aladár Heppes.
For all $n$ for smooth convex fields — shown by Hugo Hadwiger (1946).^[5]^[6]
For all $n$ for centrally-symmetric fields — shown by A.S. Riesling (1971).^[7]
For all $n$ for fields of revolution — shown by Boris Dekster (1995).^[8]

The problem was finally solved in 1993 by Jeff Kahn and Gil Kalai, who showed that the general answer to Borsuk's question is no.^[9] They claim that their construction shows that $n + 1$ pieces do not suffice for $n = 1325$ and for each $n > 2014$ . However, as pointed out by Bernulf Weißbach,^[10] the first part of this claim is in fact false. But after improving a suboptimal conclusion within the corresponding derivation, one can indeed verify one of the constructed point sets as a counterexample for $n = 1325$ (as well as all higher dimensions up to 1560).^[11]

Their result was improved in 2003 by Hinrichs and Richter, who constructed finite sets for $n \geq 298$ , which cannot be partitioned into $n + 11$ parts of smaller diameter.^[1]

In 2013, Andriy V. Bondarenko had shown that Borsuk's conjecture is false for all $n \geq 65$ .^[12] Shortly after, Thomas Jenrich derived a 64-dimensional counterexample from Bondarenko's construction, giving the best bound up to now.^[13]^[14]

Apart from finding the minimum number $n$ of dimensions such that the number of pieces $α (n) > n + 1$ , mathematicians are interested in finding the general behavior of the function $α (n)$ . Kahn and Kalai show that in general (that is, for $n$ sufficiently large), one needs ${\textstyle \alpha (n)\geq (1.2)^{\sqrt {n}}}$ many pieces. They also quote the upper bound by Oded Schramm, who showed that for every $ε$ , if $n$ is sufficiently large, ${\textstyle \alpha (n)\leq \left({\sqrt {3/2}}+\varepsilon \right)^{n}}$ .^[15] The correct order of magnitude of $α (n)$ is still unknown.^[16] However, it is conjectured that there is a constant $c > 1$ such that $α (n) > c n$ for all $n \geq 1$ .

Oded Schramm also worked in a related question, a body $K$ of constant width is said to have effective radius $r$ if ${\text{Vol}}(K)=r^{n}{\text{Vol}}(\mathbb {B} ^{n})$ , where $\mathbb {B} ^{n}$ is the unit ball in $\mathbb {R} ^{n}$ , he proved the lower bound ${\sqrt {3+2/(n+1)}}-1\leq r_{n}$ , where $r_{n}$ is the smallest effective radius of a body of constant width 2 in $\mathbb {R} ^{n}$ and asked if there exists $\epsilon >0$ such that $r_{n}\leq 1-\epsilon$ for all $n\geq 2$ ,^[17]^[18] that is if the gap between the volumes of the smallest and largest constant-width bodies grows exponentially. In 2024 a preprint by Arman, Bondarenko, Nazarov, Prymak, Radchenko reported to have answered this question in the affirmative giving a construction that satisfies ${\text{Vol}}(K)\leq (0.9)^{n}{\text{Vol}}(\mathbb {B} ^{n})$ .^[19]^[20]^[21]

Note

^ As Hinrichs and Richter say in the introduction to their work,^[1] the "Borsuk's conjecture [was] believed by many to be true for some decades" (hence commonly called a conjecture) so "it came as a surprise when Kahn and Kalai constructed finite sets showing the contrary". However, Karol Borsuk has formulated the problem just as a question, not suggesting the expected answer would be positive.

References

^ ^a ^b Hinrichs, Aicke; Richter, Christian (28 August 2003). "New sets with large Borsuk numbers". Discrete Mathematics. 270 (1–3). Elsevier: 137–147. doi:10.1016/S0012-365X(02)00833-6.
^ ^a ^b Borsuk, Karol (1933), "Drei Sätze über die n-dimensionale euklidische Sphäre" [Three theorems about the n-dimensional Euclidean sphere] (PDF), Fundamenta Mathematicae (in German), 20: 177–190, doi:10.4064/fm-20-1-177-190
^ Perkal, Julian (1947), "Sur la subdivision des ensembles en parties de diamètre inférieur", Colloquium Mathematicum (in French), 2: 45
^ Eggleston, H. G. (1955), "Covering a three-dimensional set with sets of smaller diameter", Journal of the London Mathematical Society, 30: 11–24, doi:10.1112/jlms/s1-30.1.11, MR 0067473
^ Hadwiger, Hugo (1945), "Überdeckung einer Menge durch Mengen kleineren Durchmessers", Commentarii Mathematici Helvetici (in German), 18 (1): 73–75, doi:10.1007/BF02568103, MR 0013901, S2CID 122199549
^ Hadwiger, Hugo (1946), "Mitteilung betreffend meine Note: Überdeckung einer Menge durch Mengen kleineren Durchmessers", Commentarii Mathematici Helvetici (in German), 19 (1): 72–73, doi:10.1007/BF02565947, MR 0017515, S2CID 121053805
^ Riesling, A. S. (1971), "Проблема Борсука в трехмерных пространствах постоянной кривизны" [Borsuk's problem in three-dimensional spaces of constant curvature] (PDF), Ukr. Geom. Sbornik (in Russian), 11, Kharkov State University (now National University of Kharkiv): 78–83
^ Dekster, Boris (1995), "The Borsuk conjecture holds for fields of revolution", Journal of Geometry, 52 (1–2): 64–73, doi:10.1007/BF01406827, MR 1317256, S2CID 121586146
^ Kahn, Jeff; Kalai, Gil (1993), "A counterexample to Borsuk's conjecture", Bulletin of the American Mathematical Society, 29 (1): 60–62, arXiv:math/9307229, doi:10.1090/S0273-0979-1993-00398-7, MR 1193538, S2CID 119647518
^ Weißbach, Bernulf (2000), "Sets with Large Borsuk Number" (PDF), Beiträge zur Algebra und Geometrie (in German), 41 (2): 417–423
^ Jenrich, Thomas (2018), On the counterexamples to Borsuk's conjecture by Kahn and Kalai, arXiv:1809.09612v4
^ Bondarenko, Andriy (2014) [2013], "On Borsuk's Conjecture for Two-Distance Sets", Discrete & Computational Geometry, 51 (3): 509–515, arXiv:1305.2584, doi:10.1007/s00454-014-9579-4, MR 3201240
^ Jenrich, Thomas (2013), A 64-dimensional two-distance counterexample to Borsuk's conjecture, arXiv:1308.0206, Bibcode:2013arXiv1308.0206J
^ Jenrich, Thomas; Brouwer, Andries E. (2014), "A 64-Dimensional Counterexample to Borsuk's Conjecture", Electronic Journal of Combinatorics, 21 (4): #P4.29, doi:10.37236/4069, MR 3292266
^ Schramm, Oded (1988), "Illuminating sets of constant width", Mathematika, 35 (2): 180–189, doi:10.1112/S0025579300015175, MR 0986627
^ Alon, Noga (2002), "Discrete mathematics: methods and challenges", Proceedings of the International Congress of Mathematicians, Beijing, 1: 119–135, arXiv:math/0212390, Bibcode:2002math.....12390A
^ Schramm, Oded (June 1988). "On the volume of sets having constant width". Israel Journal of Mathematics. 63 (2): 178–182. doi:10.1007/BF02765037. ISSN 0021-2172.
^ Kalai, Gil (2015-05-19). "Some old and new problems in combinatorial geometry I: Around Borsuk's problem". arXiv:1505.04952 [math.CO].
^ Arman, Andrii; Bondarenko, Andriy; Nazarov, Fedor; Prymak, Andriy; Radchenko, Danylo (2024-05-28). "Small volume bodies of constant width". arXiv:2405.18501 [math.MG].
^ Kalai, Gil (2024-05-31). "Andrii Arman, Andriy Bondarenko, Fedor Nazarov, Andriy Prymak, and Danylo Radchenko Constructed Small Volume Bodies of Constant Width". Combinatorics and more. Retrieved 2024-09-28.
^ Barber, Gregory (2024-09-20). "Mathematicians Discover New Shapes to Solve Decades-Old Geometry Problem". Quanta Magazine. Retrieved 2024-09-28.

External links

Weisstein, Eric W. "Borsuk's Conjecture". MathWorld.

[WhyConjecture-2] As Hinrichs and Richter say in the introduction to their work,^[1] the "Borsuk's conjecture [was] believed by many to be true for some decades" (hence commonly called a conjecture) so "it came as a surprise when Kahn and Kalai constructed finite sets showing the contrary". However, Karol Borsuk has formulated the problem just as a question, not suggesting the expected answer would be positive.

[HinrRicht-1] Hinrichs, Aicke; Richter, Christian (28 August 2003). "New sets with large Borsuk numbers". Discrete Mathematics. 270 (1–3). Elsevier: 137–147. doi:10.1016/S0012-365X(02)00833-6.

[BorsukFM-3] Borsuk, Karol (1933), "Drei Sätze über die n-dimensionale euklidische Sphäre" [Three theorems about the n-dimensional Euclidean sphere] (PDF), Fundamenta Mathematicae (in German), 20: 177–190, doi:10.4064/fm-20-1-177-190

[4] Perkal, Julian (1947), "Sur la subdivision des ensembles en parties de diamètre inférieur", Colloquium Mathematicum (in French), 2: 45

[5] Eggleston, H. G. (1955), "Covering a three-dimensional set with sets of smaller diameter", Journal of the London Mathematical Society, 30: 11–24, doi:10.1112/jlms/s1-30.1.11, MR 0067473

[6] Hadwiger, Hugo (1945), "Überdeckung einer Menge durch Mengen kleineren Durchmessers", Commentarii Mathematici Helvetici (in German), 18 (1): 73–75, doi:10.1007/BF02568103, MR 0013901, S2CID 122199549

[7] Hadwiger, Hugo (1946), "Mitteilung betreffend meine Note: Überdeckung einer Menge durch Mengen kleineren Durchmessers", Commentarii Mathematici Helvetici (in German), 19 (1): 72–73, doi:10.1007/BF02565947, MR 0017515, S2CID 121053805

[8] Riesling, A. S. (1971), "Проблема Борсука в трехмерных пространствах постоянной кривизны" [Borsuk's problem in three-dimensional spaces of constant curvature] (PDF), Ukr. Geom. Sbornik (in Russian), 11, Kharkov State University (now National University of Kharkiv): 78–83

[9] Dekster, Boris (1995), "The Borsuk conjecture holds for fields of revolution", Journal of Geometry, 52 (1–2): 64–73, doi:10.1007/BF01406827, MR 1317256, S2CID 121586146

[10] Kahn, Jeff; Kalai, Gil (1993), "A counterexample to Borsuk's conjecture", Bulletin of the American Mathematical Society, 29 (1): 60–62, arXiv:math/9307229, doi:10.1090/S0273-0979-1993-00398-7, MR 1193538, S2CID 119647518

[11] Weißbach, Bernulf (2000), "Sets with Large Borsuk Number" (PDF), Beiträge zur Algebra und Geometrie (in German), 41 (2): 417–423

[12] Jenrich, Thomas (2018), On the counterexamples to Borsuk's conjecture by Kahn and Kalai, arXiv:1809.09612v4

[13] Bondarenko, Andriy (2014) [2013], "On Borsuk's Conjecture for Two-Distance Sets", Discrete & Computational Geometry, 51 (3): 509–515, arXiv:1305.2584, doi:10.1007/s00454-014-9579-4, MR 3201240

[14] Jenrich, Thomas (2013), A 64-dimensional two-distance counterexample to Borsuk's conjecture, arXiv:1308.0206, Bibcode:2013arXiv1308.0206J

[15] Jenrich, Thomas; Brouwer, Andries E. (2014), "A 64-Dimensional Counterexample to Borsuk's Conjecture", Electronic Journal of Combinatorics, 21 (4): #P4.29, doi:10.37236/4069, MR 3292266

[16] Schramm, Oded (1988), "Illuminating sets of constant width", Mathematika, 35 (2): 180–189, doi:10.1112/S0025579300015175, MR 0986627

[17] Alon, Noga (2002), "Discrete mathematics: methods and challenges", Proceedings of the International Congress of Mathematicians, Beijing, 1: 119–135, arXiv:math/0212390, Bibcode:2002math.....12390A

[18] Schramm, Oded (June 1988). "On the volume of sets having constant width". Israel Journal of Mathematics. 63 (2): 178–182. doi:10.1007/BF02765037. ISSN 0021-2172.

[19] Kalai, Gil (2015-05-19). "Some old and new problems in combinatorial geometry I: Around Borsuk's problem". arXiv:1505.04952 [math.CO].

[20] Arman, Andrii; Bondarenko, Andriy; Nazarov, Fedor; Prymak, Andriy; Radchenko, Danylo (2024-05-28). "Small volume bodies of constant width". arXiv:2405.18501 [math.MG].

[21] Kalai, Gil (2024-05-31). "Andrii Arman, Andriy Bondarenko, Fedor Nazarov, Andriy Prymak, and Danylo Radchenko Constructed Small Volume Bodies of Constant Width". Combinatorics and more. Retrieved 2024-09-28.

[22] Barber, Gregory (2024-09-20). "Mathematicians Discover New Shapes to Solve Decades-Old Geometry Problem". Quanta Magazine. Retrieved 2024-09-28.

[note 1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[1]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

Borsuk's conjecture

Problem

See also

Note

References

Further reading

External links