New AI Counterexample Pushes Borsuk Failures to 63D

New AI Counterexample Pushes Borsuk Failures to 63D
Introduction

Borsuk’s problem asks a deceptively simple geometric question: if you have a set of points in (\mathbb{R}^d) with positive diameter, can you always split it into (d+1) smaller-diameter chunks? For low dimensions, yes. But in high dimensions, it fails—and the new research behind Yibo Ji’s arXiv paper shows just how brutally it can fail.

The headline result is wild: the paper constructs a 321-point set in (\mathbb{R}^{63}) that cannot be partitioned into 64 subsets of strictly smaller diameter. In Borsuk-problem language, this proves bounds like
[
b(63) \ge 65 \quad \text{and in fact} \quad b^\text{?}(63)\ge 65 b(63)\ge 65,
]
i.e., the “needed number of pieces” is at least 65 in dimension 63 (with the paper’s precise inequality chain). The construction takes a known “almost” counterexample core in dimension 63 and—using a clever geometric projection trick—adds exactly one extra point without ruining the obstruction.

What’s especially interesting is how the proof is stitched together from two kinds of information: graph structure (cliques in a strongly regular graph) and geometry (a two-distance Euclidean embedding). The new point is not just “picked from the existing configuration”—it’s created by projecting a vertex that originally lived in a 65-dimensional ambient space down into the 63-dimensional subspace, then rescaling so it lands on the diameter sphere in the right combinatorial way. That’s the core mechanism of the AI-generated counterexample.

Why This Matters

This is the kind of mathematics that looks abstract until you realize what it’s really about: worst-case packing and partitioning. Many real systems boil down to “can I split something complex into a bounded number of simpler clusters?” or “how many ‘bins’ do I need if I must keep internal spread below a threshold?” The Borsuk problem is a clean, sharp version of those questions.

So why is this significant right now? Because machine learning and optimization are increasingly concerned with guarantees under adversarial structure: robust clustering, separation in embeddings, and bounding the number of “small-diameter” groups needed when the geometry is hostile. When a problem like Borsuk’s fails at dimension 63, it’s a reminder that high-dimensional geometry can be wildly non-intuitive—and that you shouldn’t assume “a small number of clusters always suffices” unless you’ve proven it.

A concrete scenario you can connect to today: imagine designing a system that takes pairwise similarities (distances) between a large set of items and tries to enforce a rule like “each group must have diameter < D.” If your embedding space has effective dimension around 60–70 (common in latent representations), this kind of result tells you there are configurations where no matter how cleverly you group, you’ll need more than (d+1) groups. The paper doesn’t give an ML product, but it gives a certificate of impossibility: there exist finite point sets for which the “(d+1) clustering” hope provably breaks.

And compared to previous work: earlier constructions (notably by Bondarenko, and then improved by Jenrich–Brouwer) already produced Borsuk counterexamples in dimension 64 and 65 using graph-to-Euclidean embeddings. This new work builds on that by noticing that the known 320-point “core” in dimension 63 is one point short of what you’d want. Instead of trying to rebuild from scratch, it performs a targeted extension: add one projected-and-rescaled point. That’s a pattern you see often in AI-era research: take an existing structured dataset/model, then perform a controlled perturbation that preserves the hidden obstruction.

Main Content Sections

From Borsuk to Graph Cliques: How the Problem Becomes Combinatorics

At a high level, Borsuk’s problem sounds like geometry: you have a set (X \subset \mathbb{R}^d), and you want to split (X) into (d+1) pieces each with strictly smaller diameter than (\operatorname{diam}(X)).

But the Bondarenko method (used repeatedly in this lineage) turns that into something graph-based. The trick is to encode “which pairs are at the full diameter” using a graph.

The diameter-graph dictionary (the intuition)

Think of your point set (X) of diameter (D). Define a graph where:
- vertices are points in (X),
- and an edge means the distance between the two points is exactly the maximum (D) (or, equivalently, they are “incompatible” with being in a smaller-diameter subset).

Then the key observation is:
- If you take a subset whose diameter is strictly smaller than (D), you’re not allowed to include two points that are at full diameter—so the subset can only contain points that form a structure with no forbidden pairs.

In Bondarenko’s framework for strongly regular graphs, those “smaller-diameter subsets correspond to graph cliques” in an associated graph (\Gamma). In the new paper’s setup, that clique control is especially strong because the graph they use has clique number:
[
\omega(\Gamma)=5.
]
So any subset that qualifies as “smaller-diameter” can have at most 5 points.

Why the dimensions matter

Earlier finite counterexamples lived in higher dimensions, like 64 and 65. The goal here is sharper: push the counterexample down to dimension 63.

This matters because Borsuk’s problem is about dimension (d). Every decrement in dimension is a real achievement: it tightens the “failure threshold.” The paper’s construction shows that dimension 63 is bad enough that even with 64 subsets, you can’t guarantee smaller diameter in a worst-case configuration.

What the Known (G_2(4)) Structure Gives You—and What It Doesn’t

The paper’s construction is anchored in a specific strongly regular graph called (G_2(4)) (more precisely, the Euclidean realization used comes from the graph with strongly regular parameters (\text{srg}(416,100,36,20))).

The spectral-to-geometry step

Strongly regular graphs come with parameters (\text{srg}(N,k,\lambda,\mu)), meaning:
- (N) vertices,
- each vertex has degree (k),
- adjacent vertices share exactly (\lambda) common neighbors,
- non-adjacent vertices share exactly (\mu) common neighbors.

Those parameters determine the adjacency eigenvalues in a controlled way, and from that you can build an “eigenspace projected” Euclidean embedding. Concretely, in the paper’s case:
- (N=416),
- (k=100),
- (\lambda=36),
- (\mu=20).

This leads to two nontrivial eigenvalues:
- (20),
- (-4),

and the embedding lives in a 65-dimensional space (after identifying the relevant eigenspace with (\mathbb{R}^{65})).

From this embedding, a remarkable property falls out:
- the set has a diameter that can be computed (the paper gets a diameter of (8\sqrt{8}) before rescaling),
- and “smaller-diameter subsets” correspond exactly to cliques in the graph.

The Jenrich–Brouwer dimensional squeeze

The earlier work by Jenrich and Brouwer exploited additional structure of the (G_2(4)) Euclidean realization to force many points into a 63-dimensional subspace.

They split the 416-point configuration into blocks so that:
- 320 vectors labeled by a set (C) sit inside a 63-dimensional subspace (H),
- while other parts live in directions orthogonal or partially orthogonal to (H).

The new paper emphasizes an important subtlety: that 320-point core is not itself a counterexample. It “misses by one point” in an exact counting sense.

The counting threshold you can feel

Because the clique number is 5, any subset that you’d need to be “small diameter” can contain at most 5 points. So if you had a set of size (320), then 64 such groups could cover at most:
[
64 \cdot 5 = 320.
]
That’s exactly the size of the core. So the obstruction is “tight”: counting alone can’t force failure yet.

The dream would be to have 321 points in the same 63D setting, so that:
[
64 \cdot 5 = 320 < 321,
]
and partitioning into 64 smaller-diameter subsets becomes impossible.

That’s exactly what the new paper accomplishes: it adds one extra point to the 63D core while preserving the “clique obstruction.”

The One-Point Trick: Projection + Rescaling Without Losing the Clique Pattern

Here’s the heart of the construction, explained with the least jargon possible.

The problem: the obvious extra point won’t fit in 63D

Pick a vertex (v) in one of the blocks (they choose (v \in B1)). Its Euclidean representative (xv) (within the original 65D realization) generally does not lie in the 63D subspace (H).

So you can’t just “append (x_v)” to the 320-point core and hope the diameter relations remain the same. The distances will change, and the clique correspondence could break.

The solution: project, then rescale to land on the right diameter sphere

Let (u) be the orthogonal projection of (x_v) into the 63D subspace (H). But just projecting isn’t enough—you need the new point (z) to sit with the correct distance relationships to the core points.

So the paper introduces a scalar scaling:
[
z = t\,u
]
with a carefully chosen (t).

This is where the proof becomes surprisingly elegant: the projection preserves the inner products with points already in (H), and because the graph embedding only has two relevant inner-product levels between the core points and the outside vertex, the scaled projection can be tuned so that:
- vertices that were nonadjacent to (v) land exactly on the “full diameter” distance,
- while vertices that were adjacent to (v) become strictly closer than the diameter.

In other words: the new point (z) recreates the same smaller-diameter compatibility pattern that the original vertex (v) had—just now inside the 63D subspace.

The “projection-shadow principle” in plain English

The paper packages this logic into a lemma: if the inner products with the core come in two levels (say (\alpha) and (\beta), with (\alpha>\beta)), then after projecting and scaling, the point (z) can be positioned so that the distance threshold “cuts” in the same way as before.

That means the geometric operation (projection + rescaling) acts like a combinatorial emulator:

You don’t need the exact original point—only the adjacency/nonadjacency inner-product ordering.

This is the conceptual reason the construction is hard to find via naive search. If you only look for induced two-distance subsets inside the old 416-point set, you won’t see this new point, because it’s not a subset extraction. It’s a projection-generated extension.

Finishing the Contradiction: Why 64 Smaller-Diameter Sets Can’t Cover 321 Points

Once the point (z) is added, you get a new set:
[
X = C \cup {z}
]
with (|X|=321) points in (\mathbb{R}^{63}).

The key property: the compatibility graph is preserved

The paper defines a compatibility graph: two points are joined if their distance is strictly smaller than the full diameter.

Then it proves that this compatibility graph for the new set (C\cup{z}) matches the induced compatibility structure from the original graph:
[
\text{compatibility}(C\cup{z}) \cong \Gamma[C\cup{v}].
]

So any subset of smaller diameter corresponds to a clique in (\Gamma).

The clique number kills the partition attempt

Since (\omega(\Gamma)=5), every smaller-diameter subset has at most 5 points. Therefore, even if you use 64 subsets, the total you can cover is at most:
[
64 \cdot 5 = 320.
]
But the set has 321 points. Contradiction.

Result: Borsuk partitioning fails in (\mathbb{R}^{63})

So there exists a 321-point set in (\mathbb{R}^{63}) with diameter (8\sqrt{8}) (and after rescaling, they get a unit-diameter formulation) such that no partition into 64 strictly smaller-diameter subsets exists.

That’s the decisive “Borsuk fails here” statement, now sharpened specifically to dimension 63.

Computational Verification: Exact Enough to Be Trusted

One thing I appreciate in this paper is the emphasis on reproducibility and exactness.

The appendix (as described in the main text) uses a verification program that:
- reconstructs the relevant 416-vertex graph from the geometry over a finite field (\text{GF}(16)),
- checks the strongly regular parameters ((416,100,36,20)),
- confirms the clique property (there is a (K5), but no (K6) within the needed induced structure, equivalently no (K_6) or the stronger forbidden configuration depending on how they phrase it),
- recovers the equitable partition into blocks of sizes (32+32+32+320),
- and verifies the Gram-matrix, projection, distance, and rank computations for the augmented 321-point set.

The program uses finite-field arithmetic and exact integer bitset searches; floating-point linear algebra is only used as a redundant sanity check (not as the source of the proof). That’s a strong sign the result isn’t “numerical luck.”

Key Takeaways

Key Takeaways

• Main result: The paper constructs a 321-point set in (\mathbb{R}^{63}) that cannot be partitioned into 64 subsets of strictly smaller diameter, proving strengthened lower bounds around Borsuk’s problem in dimension 63.
• Why the number 321 matters: The underlying clique obstruction has clique number 5, so each smaller-diameter subset can contain at most 5 points. Then (64\cdot 5=320), which is one short of 321.
• How the extra point is built: It uses a projection + rescaling method. A vertex from a higher-dimensional Euclidean representation is projected orthogonally into the 63D subspace and scaled so it preserves the same adjacency/nonadjacency distance threshold pattern.
• Graph-to-geometry pipeline: Strongly regular graph eigenvalue structure gives a two-distance Euclidean embedding; additional (G_2(4))-specific equitable partition structure enables the dimension reduction.
• Not an induced-subset trick: This new construction is a projection-generated extension, not something you’d necessarily find by searching for induced two-distance subsets of the old 416-point configuration.
• Practical implication (conceptual): In high-dimensional geometric clustering/partitioning problems, there are adversarial finite configurations where “(d+1) groups always suffice” fails—sharply continuing the story of worst-case geometry breaking naive guarantees.

If you want, I can also rewrite the one-point projection step with a concrete “two distance levels (\alpha) and (\beta)” toy model, so you can visualize exactly why the scaling recovers the clique pattern.