wp-plugin-hostgator domain was triggered too early. This is usually an indicator for some code in the plugin or theme running too early. Translations should be loaded at the init action or later. Please see Debugging in WordPress for more information. (This message was added in version 6.7.0.) in /home4/scienrds/scienceandnerds/wp-includes/functions.php on line 6114ol-scrapes domain was triggered too early. This is usually an indicator for some code in the plugin or theme running too early. Translations should be loaded at the init action or later. Please see Debugging in WordPress for more information. (This message was added in version 6.7.0.) in /home4/scienrds/scienceandnerds/wp-includes/functions.php on line 6114Source:https:\/\/www.quantamagazine.org\/a-team-of-math-proves-a-critical-link-between-addition-and-sets-20231206\/#comments<\/a><\/br> The lists have fixed lengths, and each bit can be either 0 or 1. You add them together by adding each entry to its counterpart in another list, with the rule that 1 + 1 = 0. So (0, 1, 1, 1, 0) + (1, 1, 1, 1, 1) = (1, 0, 0, 0, 1). PFR is an attempt to figure out what a set can look like if it isn\u2019t quite a subgroup but has some grouplike features.<\/p>\n To make PFR precise, imagine you have a set of binary lists called A<\/em>. Now take every pair of elements from A<\/em> and add them up. The resulting sums make up the sumset of A<\/em>, called A <\/em>+ A<\/em>. If the elements of A<\/em> are chosen randomly, then most of the sums are different from each other. If there are k <\/em>elements in A<\/em>, that means there will be around k<\/em>2<\/sup>\/2 elements in the sumset. When k <\/em>is large \u2014 say, 1,000 \u2014 k<\/em>2<\/sup>\/2 is a lot bigger than k<\/em>. But if A <\/em>is a subgroup, every element of A <\/em>+ A <\/em>is in A<\/em>, meaning that A <\/em>+ A<\/em> is the same size as A<\/em> itself.<\/p>\n PFR considers sets that are not random, but are not subgroups either. In these sets, the number of elements in A <\/em>+ A <\/em>is somewhat small \u2014 say, 10k<\/em>, or 100k<\/em>. \u201cIt\u2019s really useful when your notion of structure is much more rich than just being an exact algebraic structure,\u201d said Shachar Lovett<\/a>, a computer scientist at the University of California, San Diego.<\/p>\n All the sets mathematicians knew of that obeyed this property \u201care pretty close to actual subgroups,\u201d Tao said. \u201cThat was the intuition, that there weren\u2019t any other sort of fake groups lying around.\u201d Freiman had proved a version of this statement in his original work. In 1999, Ruzsa extended Freiman\u2019s theorem from the integers to the setting of binary lists. He proved<\/a> that when the number of elements in A<\/em> + A<\/em> is a constant multiple of the size of A<\/em>, A <\/em>is contained within a subgroup.<\/p>\n But Ruzsa\u2019s theorem required the subgroup to be enormous. Marton\u2019s insight was to posit that rather than being contained in one giant subgroup, A<\/em> could be contained in a polynomial number of cosets of a subgroup that is no bigger than the original set A<\/em>.<\/p>\n Around the turn of the millennium, Gowers came across Ruzsa\u2019s proofs of Freiman\u2019s theorem while studying a different problem about sets containing strings of evenly spaced numbers. \u201cI needed something like this, kind of getting structural information from much looser information about a certain set,\u201d Gowers said. \u201cI was very fortunate that not that long before, Ruzsa produced this absolutely gorgeous proof.\u201d<\/p>\n Gowers began to work out a potential proof of the polynomial version of the conjecture. His idea was to start with a set A <\/em>whose sumset was relatively small, then gradually manipulate A <\/em>into a subgroup. If he could prove that the resulting subgroup was similar to the original set A<\/em>, he could easily conclude the conjecture was true. Gowers shared his ideas with colleagues, but no one could mold them into a full proof. Though Gowers\u2019 strategy was successful in some cases, in others the manipulations took A <\/em>further away from the desired conclusion of the polynomial Freiman-Ruzsa conjecture.<\/p>\n Eventually, the field moved on. In 2012, Sanders almost proved PFR<\/a>. But the number of shifted subgroups he needed was above the polynomial level, though only by a little bit. \u201cOnce he did that, it meant that it became a less urgent thing, but still a really nice problem for which I have a great fondness,\u201d Gowers said.<\/p>\n But Gowers\u2019 ideas lived on in his colleagues\u2019 memories and hard drives. \u201cThere\u2019s a real idea there,\u201d said Green, who had also been a student of Gowers. \u201cI know a real idea when I see a real idea.\u201d This summer, Green, Manners and Tao finally liberated Gowers\u2019 ideas from their purgatory.<\/p>\n Green, Tao and Manners were 37 pages deep in collaboration before they thought to return to Gowers\u2019 20-year-old ideas. In a June 23 paper<\/a>, they had successfully used a concept from probability theory called random variables to probe the structure of sets with small sumsets. By making this switch, the group could manipulate their sets with more finesse. \u201cDealing with random variables is somehow much less rigid than dealing with sets,\u201d Manners said. With a random variable, \u201cI can tweak one of the probabilities by a small amount, and that might give me a better random variable.\u201d<\/p>\n Using this probabilistic perspective, Green, Manners and Tao could move from working with the number of elements in a set to a measurement of the information contained in a random variable, a quantity called entropy. Entropy was not new to additive combinatorics. In fact, Tao had attempted<\/a> to popularize the concept in the late 2000s. But nobody had yet tried to use it on the polynomial Freiman-Ruzsa conjecture. Green, Manners and Tao discovered it was powerful. But they still couldn\u2019t prove the conjecture.<\/p>\n As the group chewed over their new results, they realized that they\u2019d finally built an environment in which Gowers\u2019 dormant ideas could flourish. If they measured the size of a set using its entropy, rather than its number of elements, the technical details might work out much better. \u201cAt some point we realized that these old ideas from Tim from 20 years ago were actually more likely to work than the ones we were trying,\u201d Tao said. \u201cAnd so we brought Tim back into the project. And then all the pieces fit together surprisingly nicely.\u201d<\/p>\n Still, there were many details to figure out before a proof came together. \u201cIt was sort of foolish that all four of us were incredibly busy with other things,\u201d Manners said. \u201cYou want to publish this great result and tell the world, but you\u00a0do actually still have to write your midterms.\u201d Eventually, the group pushed through, and on November 9, they posted their paper. They proved that if A <\/em>+ A <\/em>is no bigger than k<\/em> times the size of A<\/em>, then A<\/em> can be covered by no more than about k<\/em>12<\/sup> shifts of a subgroup that is no bigger than A<\/em>. This is a potentially enormous number of shifts. But it is a polynomial, so it doesn\u2019t grow exponentially faster as k<\/em> gets bigger, as it would if k<\/em> were in the exponent.<\/p>\n A few days later, Tao began to<\/a> formalize the proof. He ran the formalization project collaboratively, using the version-control package GitHub to coordinate contributions from 25 volunteers around the world<\/a>. They used a tool called Blueprint<\/a> developed by Patrick Massot<\/a>, a mathematician at Paris-Saclay University, to organize the efforts to translate from what Tao called<\/a> \u201cMathematical English\u201d into computer code. Blueprint can, among other things, create a chart<\/a> depicting the various logical steps involved in the proof. Once all the bubbles were covered in what Tao called a \u201clovely shade of green,\u201d the team was done. They discovered a few very minor typos in the paper \u2014 in an online message<\/a>, Tao noted that \u201cthe most mathematically interesting portions of the project were relatively straightforward to formalize, but it was the technical \u2018obvious\u2019 steps that took the longest.\u201d<\/p>\n Marton died just a few years before her famous conjecture was proved, but the proof echoes her life\u2019s work<\/a> on entropy and information theory. \u201cEverything works much better when you do it in this entropy framework than in the framework I was trying to\u00a0do it,\u201d Gowers said. \u201cTo me, it still seems somewhat magical.\u201d<\/p>\n Quanta\u00a0is conducting a series of surveys to better serve our audience. Take our\u00a0<\/i>mathematics reader survey<\/i><\/a>\u00a0and you will be entered to win free\u00a0<\/i>Quanta\u00a0merch.<\/i><\/p>\n<\/div>\n <\/br><\/br><\/br><\/p>\n
\n\u2018A-Team\u2019 of Math Proves a Critical Link Between Addition and Sets<\/br>
\n2023-12-07 21:58:08<\/br><\/p>\n\u2018I Know a Real Idea When I See a Real Idea\u2019<\/strong><\/h2>\n