Mathematicians Find Hidden Structure in a Common Type of Space

In 50 years of searching, mathematicians found only one example of a “subspace design” that fit their criteria. A new proof reveals that there are infinitely more out there.

In the fall of 2017, Mehtaab Sawhney, then an undergraduate at the Massachusetts Institute of Technology, joined a graduate reading group that set out to study a single paper over a semester. But by the semester’s end, Sawhney recalls, they decided to move on, flummoxed by the proof’s complexity. “It was really amazing,” he said. “It just seemed completely out there.”

The paper was by Peter Keevash of the University of Oxford. Its subject: mathematical objects called designs.

The study of designs can be traced back to 1850, when Thomas Kirkman, a vicar in a parish in the north of England who dabbled in mathematics, posed a seemingly straightforward problem in a magazine called the Lady’s and Gentleman’s Diary. Say 15 girls walk to school in rows of three every day for a week. Can you arrange them so that over the course of those seven days, no two girls ever find themselves in the same row more than once?

Soon, mathematicians were asking a more general version of Kirkman’s question: If you have n elements in a set (our 15 schoolgirls), can you always sort them into groups of size k (rows of three) so that every smaller set of size t (every pair of girls) appears in exactly one of those groups?

Such configurations, known as (n, k, t) designs, have since been used to help develop error-correcting codes, design experiments, test software, and win sports brackets and lotteries.

But they also get exceedingly difficult to construct as k and t grow larger. In fact, mathematicians have yet to find a design with a value of t greater than 5. And so it came as a great surprise when, in 2014, Keevash showed that even if you don’t know how to build such designs, they always exist, so long as n is large enough and satisfies some simple conditions.

Now Keevash, Sawhney and Ashwin Sah, a graduate student at MIT, have shown that even more elusive objects, called subspace designs, always exist as well. “They’ve proved the existence of objects whose existence is not at all obvious,” said David Conlon, a mathematician at the California Institute of Technology.

To do so, they had to revamp Keevash’s original approach — which involved an almost magical blend of randomness and careful construction — to get it to work in a much more restrictive setting. And so Sawhney, now also pursuing his doctorate at MIT, found himself face to face with the paper that had stumped him just a few years earlier. “It was really, really enjoyable to fully understand the techniques, and to really suffer and work through them and develop them,” he said.

Merrill Sherman/Quanta Magazine

‘Beyond What Is Beyond Our Imagination’

For decades, mathematicians have translated problems about sets and subsets — like the design question — into problems about so-called vector spaces and subspaces.

A vector space is a special kind of set whose elements — vectors — are related to one another in a much more rigid way than a simple collection of points can be. A point tells you where you are. A vector tells you how far you’ve moved, and in what direction. They can be added and subtracted, made bigger or smaller.

Consider the room you’re in. It contains an infinite number of points, and an infinite number of vectors — ones stretching from where you are to every point in the room. All of those vectors can be constructed out of three fundamental ones: a vector pointing horizontally in front of you, another to your right, and another pointing up. By adding these vectors, multiplying them by real numbers, or doing some combination of the two, you can generate the three-dimensional vector space in which you live. (The number of vectors needed to generate the whole space is the dimension of the vector space.)

Various subspaces lie inside each vector space. Take just the vectors pointing to your right and in front of you. These define a two-dimensional subspace — a flat plane parallel to the floor.

Mathematicians often work with finite vector spaces and subspaces, where vectors can’t point in every possible direction (and don’t have the same notion of length). In this world, each vector space has only a finite number of vectors.

The subspace design problem deals with n-dimensional vector spaces and their subspaces. In such vector spaces — again, so long as n is sufficiently large and satisfies simple conditions — can you find a collection of k-dimensional subspaces such that any t-dimensional subspace is contained in exactly one of them? Such an object is called an (n, k, t) subspace design. It’s conceptually similar to the ordinary designs problem, but it involves arrangements that are much more tightly constrained.

This finite 3D vector space consists of eight vectors. Its 2D subspaces are particular subsets of four vectors.

Merrill Sherman/Quanta Magazine

“It’s an important problem because it’s one corner of a very deep analogy between sets and subsets on the one hand, and vector spaces and subspaces on the other,” said Peter Cameron of the University of St. Andrews in Scotland.

In the 50 years since mathematicians started thinking about this problem, they’ve found only one nontrivial example (though they know that more general kinds of subspace designs exist): In a 13-dimensional vector space, it’s possible to cover two-dimensional subspaces with three-dimensional ones exactly once. The result required a massive computer-based proof, because even for such small values of n, k and t, you end up working with millions of subspaces. The complexity of such systems “isn’t just beyond our imagination; it’s beyond what is beyond our imagination,” said Tuvi Etzion of the Technion in Israel, who helped discover the example.

But do subspace designs always exist, for any k and t? Some mathematicians conjectured that, by and large, such objects are impossible. Others, heartened by work done over the years on designs, figured that “it may be hard to prove, but if there isn’t an obvious reason for them not to exist, then they should exist,” Keevash said.

Compared to the designs realm, “for this problem, there was just nothing,” Sah said. “I guess that prompts a bit of curiosity whenever that happens.”

A Sponge for Errors

Sah and Sawhney met in 2017 as undergraduates at MIT (and ended up attending the same reading group). A few months later, “they started working together and just never stopped,” Conlon said. “They’re producing high-quality research at a rate where I can’t even blink.”

The two young mathematicians were intrigued that it had been so hard to write down just one explicit example of a subspace design, and they saw the problem as a perfect way to explore the boundaries of important techniques in combinatorics.

In proving the existence of special objects called “subspace designs,” the mathematicians Mehtaab Sawhney, Ashwin Sah and Peter Keevash (left to right) tested the limits of several well-known methods in combinatorics.

From left: Courtesy of Mehtaab Sawhney; Celeste Noche; Courtesy of Peter Keevash

Keevash, meanwhile, had kept the question in the back of his mind since his 2014 result. When Sah and Sawhney approached him at a conference last year, the three decided to go for it.

They followed the same overall strategy that Keevash had laid out in his designs work — but because of the tighter constraints at hand, “in practice, all of the steps ended up being very different in their implementation,” Keevash said. First, they set aside a carefully chosen set of subspaces, called a template. The template would later act as an island of structure in an ocean of randomness.

They then applied a modified version of a fundamentally random process called the Rödl nibble to cover most of the remaining subspaces. That left a sparse hodgepodge of subspaces that they still had to deal with. On the surface, those subspaces looked completely unstructured; it seemed impossible to arrange them into clusters that could be properly covered.

That’s where the template came in. They broke the template into pieces and combined some of its subspaces with the subspaces in the hodgepodge — snugly tucking them into larger arrangements that could be properly covered. They had to carefully track how they were doing this to make sure that every move they made led toward that more global structure. But ultimately, they were able to use the template to fill all the holes that the Rödl nibble hadn’t been able to cover. Like a sponge, the template soaked up all the errors within the design. (As a result, this general technique is called “absorption.”) “It’s almost like you’re trying to put a carpet in the corner,” Sawhney said. “It pops up somewhere else, and you push it, and somehow, after 20 pushes, the carpet is just flat.”

This completed the proof. It’s important to note that, as with the designs work, this result could, at least theoretically, be used to construct these objects — but only for very large n. Finding concrete, practical examples remains a task for the future.

In the end, the work illustrated yet another counterintuitive way that mathematicians can harness the forces of randomness to search for hidden structure. “All sorts of unexpected structure is possible,” said Cheryl Praeger, a mathematician at the University of Western Australia.

“The proof demonstrates that Keevash’s techniques work in wider contexts than they were designed for,” Cameron said. It implies that other difficult problems might be tackled by combining randomness and absorption in clever ways.

Those techniques felt magical to Sawhney when he first read about them in Keevash’s paper as an undergraduate. Even now that he’s gained a much deeper understanding of them, “this impression doesn’t go away.”

Source