Science

Mathematicians captivated by simple card game

A new series of papers has settled a long-standing question related to the popular game Set in which players seek patterned sets of three cards. Or so Quantamagazine wrote on the 31st of May. Delft Mathematician Dr. Dion Gijswijt is author of one of the papers.

When with friends, Gijswijt always refers to the card game Set, to explain what his work is about. “Set is a simple game, popular with children,” he said. “Its goal is simple: to find special triples called ‘sets’ within a deck of 81 cards.”

The maths behind it have puzzled mathematicians for decades, however. How big is the largest collection of cards that contains no set? This is the kind of question mathematicians deal with in the field of combinatorics.

The answer to the above question is 20. Set, however, is still quite simple. Each card displays a different design with four attributes. They differ in colour (cards can be red, purple or green), shape (oval, diamond or squiggle), shading (solid, striped or outlined) and number (one, two or three copies of the shape).

In theory, one could extend the designs with more than four attributes. “How big would then be the largest collection of cards that contains no set? In extremal combinatorics, this is known as the cap set problem,” Gijswijt said.

Gijswijt, together with Jordan Ellenberg, a mathematician at the University of Wisconsin, Madison, found a technique, a so-called polynomial method, to calculate this. The simplicity of the solution has stunned mathematicians.

The polynomial method has many implications. It is useful in linear algebra, for instance. One can use the method to multiply huge matrices quickly. Or as Gijswijt put it:”Solving linear systems with huge matrices can be done asymptotically faster using `fast matrix multiplication’. Our result narrows the search for even faster algorithms.”

The paper by Gijswijt and Ellenberg was published on May 30th on ArXiv. Within only a few weeks’ time, it elicited the publication of five other papers.

Gijswijt and his American colleague on their part were elaborating on an article published on May 5, by mathematicians from Israel, the United States, and Hungary. They posted a paper online showing how to use the polynomial method to solve a closely related problem.

It seems a train is set in motion. Mathematicians around the world are publishing about this new finding with the speed of light, mostly on ArXiv, a repository of electronic preprints. Drafts that have not yet been peer reviewed. Quicker even, some mathematicians use their blogs to show their new findings.

Editor Redactie

Do you have a question or comment about this article?

delta@tudelft.nl

Comments are closed.