news

EXTERNAL NEWS - Professor Makes Breakthrough in Cap Set Problem

Primary tabs

Ernie Croot of the Georgia Institute of Technology, Vsevolod Lev of the University of Haifa, Oranim, in Israel, and Péter Pál Pach of the Budapest University of Technology and Economics in Hungary, have made a major breakthrough in the cap set problem.

Read the full research paper here:

https://arxiv.org/abs/1605.01506

Read the full Quanta article here:

https://www.quantamagazine.org/set-proof-stuns-mathematicians-20160531/

Highlights from the Quanta article:

The result is related to the card game SET, in which cards with four attributes - color (red, purple, or green), shape (oval, diamond, or squiggle), shading (solid, striped, or empty), and count (one, two, or three) - need to be matched with 3 cards being a match, or "set", if all three cards either all share or all differ in all three attributes.

In a series of papers posted online in recent weeks, mathematicians have solved a problem about the pattern-matching card game Set that predates the game itself. The solution, whose simplicity has stunned mathematicians, is already leading to advances in other combinatorics problems.

The result extends previous results in an unexpected leap, while the proof is quite profound in its simplicity, and is likely to have far reaching implications.

The proof uses the “polynomial method,” an innovation that, despite its simplicity, only rose to prominence on the mathematical scene about a decade ago. The approach produces “beautiful short proofs,” Tao said. It’s “sort of magical.”

The previous results were “already considered to be quite a big breakthrough, but this completely smashes the bounds that they achieved,” said Timothy Gowers, a mathematician and Fields medalist at the University of Cambridge.

There’s still room to improve the bound on cap sets, but in the near term, at least, any further progress is likely to be incremental, Gowers said. “In a certain sense this completely finishes the problem.”

The paper soon set off a cascade of what Ellenberg called “math at Internet speed.”  Within 10 days, Ellenberg and Dion Gijswijt, a mathematician at Delft University of Technology in the Netherlands, had each independently posted papers showing how to modify the argument to polish off the original cap set problem in just three pages.

Mathematicians are now scrambling to figure out the implications of the new proof. Already, a paper has been posted online showing that the proof rules out one of the approaches mathematicians were using to try to create more efficient matrix multiplication algorithms. And on May 17, Gil Kalai, of the Hebrew University of Jerusalem, wrote an “emergency” blog post pointing out that the cap set result can be used to prove the “Erdős-Szemerédi sunflower conjecture,” which concerns sets that overlap in a sunflower pattern.

“I think a lot of people will be thinking, ‘What can I do with this?’” Gowers said. Croot, Lev and Pach’s approach, he wrote in a blog post, is “a major new technique to add to the toolbox.”

The fact that the cap set problem finally yielded to such a simple technique is humbling, Ellenberg said. “It makes you wonder what else is actually easy.”

 

Status

  • Workflow Status:Published
  • Created By:sbarone7
  • Created:12/02/2019
  • Modified By:sbarone7
  • Modified:05/25/2022

Categories

  • No categories were selected.

Keywords