Mathematicians Find Hidden Structure in a Common Type of Space

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 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.

infographic showing subspace designs

Illustration: 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.

Article Tags:
· · ·
Article Categories:
Science