{"id":614460,"date":"2026-09-28T16:30:17","date_gmt":"2026-09-28T16:30:17","guid":{"rendered":"https:\/\/www.newsbeep.com\/nz\/614460\/"},"modified":"2026-09-28T16:30:17","modified_gmt":"2026-09-28T16:30:17","slug":"mathematicians-harness-randomness-to-crack-a-55-year-old-conjecture","status":"publish","type":"post","link":"https:\/\/www.newsbeep.com\/nz\/614460\/","title":{"rendered":"Mathematicians Harness Randomness To Crack a 55-Year-Old Conjecture"},"content":{"rendered":"

The conjecture is set in the world of clock arithmetic. You start by placing the whole numbers on a number line, then you wrap the line around the face of a clock so that the numbers repeat after some prime number, p. Say p is 7, for instance. In this setting, 0, 7, 14, and all other multiples of 7 are equivalent \u2014 meaning that you can add two positive numbers (like 3 and 4) and get zero.<\/p>\n

Graham asked the following: If you pick any set of nonzero numbers off this number line (for any p), can you always rearrange them so that the partial sums you get are all different?<\/p>\n

The challenge depends on how big your set is compared to p. The more numbers you pick, the more sums there are to manage. But if you choose fewer numbers, there will be fewer ways to rearrange them. These different cases inspire different approaches.<\/p>\n

M\u00fcyesser, along with his former adviser, Alexey Pokrovskiy<\/a> of University College London, tackled the case where your set includes almost every possible number up to p. With sets this large, it can be extremely hard to construct a valid ordering. But it turned out that starting with a random ordering can bring you most of the way there.<\/p>\n

It\u2019s embarrassing for humanity that we don\u2019t know this. This situation just had to be rectified.<\/p>\n

Noah Kravitz, University of Oxford<\/p>\n

\u201cComputer scientists often call this a \u2018finding the hay in the haystack<\/a>\u2019 problem,\u201d M\u00fcyesser said. You might know that lots of good orderings are out there, but actually finding one is hard. \u201cIf you do it randomly, it\u2019s likely going to work, but it\u2019s hard to explicitly describe what the solution is supposed to look like.\u201d<\/p>\n

M\u00fcyesser and Pokrovskiy needed to ensure that no sequence of numbers anywhere in the ordering added up to zero. Otherwise, adding those numbers to the previous partial sum would repeat that sum.<\/p>\n

A completely random ordering might have a few of these troublesome sequences. So M\u00fcyesser and Pokrovskiy first set aside a few specially chosen numbers from the set, then randomly scrambled the rest. They scanned their random ordering for any problems; if they came across an interval that added up to zero, they could insert one of the spare numbers to change it. In 2022, they posted their solution<\/a>, though it was hidden in a paper that focused on applying the same technique to a more general problem.<\/p>\n

A couple of years later, Noah Kravitz<\/a> of Oxford, unaware of M\u00fcyesser and Pokrovskiy\u2019s solution, stumbled on Graham\u2019s conjecture in an online archive of unsolved problems. \u201cI saw there was an open problem, and I was like, it\u2019s embarrassing for humanity that we don\u2019t know this,\u201d Kravitz said. \u201cThis situation just had to be rectified.\u201d<\/p>\n

\"Man <\/p>\n

Noah Kravitz is one of several young mathematicians who recently revived the decades-old Graham conjecture.<\/p>\n

He decided to approach the conjecture from the opposite end. Together with Benjamin Bedert<\/a> of Oxford, he considered the case where the set of numbers is tiny compared to p \u2014 for instance, Alon said, if you have a set of 100 numbers where p is 1 billion.<\/p>\n

Kravitz and Bedert solved Graham\u2019s conjecture for those cases and posted their proof<\/a> in September 2024. M\u00fcyesser saw it and reached out, sharing his own work; the three of them (plus two other colleagues) then teamed up to extend M\u00fcyesser\u2019s original approach.<\/p>\n

\u201cIt was a pretty unlikely combination of people,\u201d Kravitz said. He and M\u00fcyesser come from two areas of combinatorics that don\u2019t typically collaborate. \u201cDifferent sections have completely different techniques,\u201d he said.<\/p>\n

Their paper, which they posted in August 2025<\/a>, handled more cases where the set of numbers is relatively large compared to p. But between those cases and the small-set cases that Kravitz and Bedert had covered, a gap remained. No one could figure out what to do about medium-size sets, such as those that include roughly half as many numbers as p. \u201cOur methods didn\u2019t work there, and there were clear reasons that they would not have worked,\u201d M\u00fcyesser said.<\/p>\n

It seemed as though research on the problem might enter another long hiatus.<\/p>\n

Then, in February 2026, a surprise appeared online.<\/p>\n

The Fountain<\/p>\n

Lisa Sauermann and Huy Tuan Pham were old friends. The two mathematicians had met in 2015 at Stanford University, where Sauermann was a graduate student and Pham an undergraduate. Today they live on different continents \u2014 Sauermann in Bonn, Germany, and Pham in Chicago. But a conference in Germany in September 2025 provided a rare chance for them to share a chalkboard again, and afterward Pham followed Sauermann to Bonn for a short visit. All they needed was a problem to work on.<\/p>\n

At the conference, they heard two talks on Graham\u2019s conjecture by mathematicians who had attempted but failed to bridge the gap. They were intrigued. And as it later turned out, Sauermann had encountered a closely related problem in the International Mathematical Olympiad as a high school student. She solved it correctly, and by the time she finished high school, she\u2019d won a gold medal in the prestigious competition four times. (Most likely, it was Chung who placed the problem on that year\u2019s exam, as she was on the committee that wrote the questions, and she frequently took inspiration from Graham\u2019s many puzzles.)<\/p>\n

\"Side-by-side <\/p>\n

Lisa Sauermann (top) and Huy Tuan Pham have been friends for the past decade. Their recent collaboration on the Graham conjecture finally settled the problem.<\/p>\n

Barbara Frommann\/University of Bonn; Courtesy of Huy Tuan Pham<\/p>\n

By the end of their three-day visit, Sauermann and Pham had a plan for how to crack the case.<\/p>\n

It hinged on a technically demanding method called anti-concentration. Here, an anti-concentration statement asserts that some event has a particularly low chance of happening. But the mechanics of proving these kinds of statements are so intricate that, though Kravitz and others were aware that such an anti-concentration approach might succeed, \u201cwe just hadn\u2019t had the guts to actually try it,\u201d he said.<\/p>\n

First, though, Sauermann and Pham began the way their predecessors had. They randomly reordered their set of numbers and came up with a procedure to fix any problems \u2014 that is, any sequences that add up to zero. Any time they found a zero-sum sequence, they swapped out the last number in the sequence with another one.<\/p>\n

This procedure often went without a hitch. But three types of \u201cbad events\u201d would cause it to fail. One: A zero-sum sequence might occur toward the end of the entire arrangement; then there would be no other numbers to swap in. Two: Many zero-sum sequences might appear too close together, making it impossible to fix them all. And three: Fixing one bad sequence might create another zero-sum sequence down the line.<\/p>\n

Sauermann and Pham hoped to prove, using anti-concentration, that each of these bad events was sufficiently unlikely. Then there would have to be a way to rearrange the set of numbers to satisfy the conjecture.<\/p>\n

To do this, the duo used Fourier analysis<\/a> \u2014 an area of math that lets you rewrite functions as sums of simple waves \u2014 to show that in general, when you add up random sets of numbers, no one sum is especially likely to appear. They then used this insight to carefully estimate the probability that each bad event would occur, ultimately showing that the total chance of getting a bad event was less than 100%. That was enough to settle the conjecture.<\/p>\n

A few months after their stint in Germany, Sauermann and Pham posted their 27-page proof<\/a> online. They had shown not only that a satisfactory rearrangement was always possible, but that a random ordering could be rearranged to eliminate bad events at least 90% of the time \u2014 a massive success rate.<\/p>\n

The mathematicians who had previously worked on the problem were surprised to see the remaining case closed so quickly. \u201cTheir approach is just completely different,\u201d M\u00fcyesser said.<\/p>\n

Together, the four papers prove Graham\u2019s conjecture for sets of all sizes. But they all assume that p is very large; though no one has calculated its exact value, think along the lines of 10 raised to the 100th power. To mathematicians, that\u2019s fine \u2014 the salient point is that you\u2019re working in the setting of clock arithmetic. But another aspect of the problem technically remains unsolved \u2014 you might still try to resolve the conjecture for all p. And if you want to use the result to choreograph a real juggling routine, you\u2019re out of luck: To correspond to such a large p, the routine would have to be much too long.<\/p>\n

The proof confirms that even within these strange, limited number settings, \u201cthere are some nice structures that always exist,\u201d Alon said. You can always achieve some degree of flexibility, shuffling the numbers in your set around to avoid revisiting the same partial sums.<\/p>\n

\u201cTo pose a good problem is really an art,\u201d Chung said. \u201cI think Ron would be extremely happy to see the problem solved.\u201d<\/p>\n

\"\" <\/p>\n","protected":false},"excerpt":{"rendered":"The conjecture is set in the world of clock arithmetic. You start by placing the whole numbers on…\n","protected":false},"author":2,"featured_media":614461,"comment_status":"","ping_status":"","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6],"tags":[111,139,69,145],"class_list":["post-614460","post","type-post","status-publish","format-standard","has-post-thumbnail","category-technology","tag-new-zealand","tag-newzealand","tag-nz","tag-technology"],"_links":{"self":[{"href":"https:\/\/www.newsbeep.com\/nz\/wp-json\/wp\/v2\/posts\/614460","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.newsbeep.com\/nz\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.newsbeep.com\/nz\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.newsbeep.com\/nz\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.newsbeep.com\/nz\/wp-json\/wp\/v2\/comments?post=614460"}],"version-history":[{"count":0,"href":"https:\/\/www.newsbeep.com\/nz\/wp-json\/wp\/v2\/posts\/614460\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.newsbeep.com\/nz\/wp-json\/wp\/v2\/media\/614461"}],"wp:attachment":[{"href":"https:\/\/www.newsbeep.com\/nz\/wp-json\/wp\/v2\/media?parent=614460"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.newsbeep.com\/nz\/wp-json\/wp\/v2\/categories?post=614460"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.newsbeep.com\/nz\/wp-json\/wp\/v2\/tags?post=614460"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}