16 ms·

Surprise computer science proof in combinatorics

267 points by theafh 4y ago

thirdmunky 4y ago
Source paper: https://arxiv.org/abs/2302.05537 https://arxiv.org/abs/2302.05537
- n4r9 4y ago
  Plus much shorter write-up from Bloom and Sisask: https://arxiv.org/abs/2302.07211 https://arxiv.org/abs/2302.07211
  - deleted 4y ago
    [deleted]
  - red_trumpet 4y ago
    I think you mean this one: https://arxiv.org/abs/2302.07211 https://arxiv.org/abs/2302.07211
    - n4r9 4y ago
      Yes, thank you!
    - rml 4y ago
      automatic conversion to web page available at https://ar5iv.labs.arxiv.org/html/2302.07211 https://ar5iv.labs.arxiv.org/html/2302.07211 (more info about the conversions at https://ar5iv.labs.arxiv.org https://ar5iv.labs.arxiv.org)
      - eternalban 4y ago
        TIL. Thank you for this. https://ar5iv.labs.arxiv.org/ https://ar5iv.labs.arxiv.org/
      - voxelghost 4y ago
        Seems to only be working for papers in TeX?
      - satvikpendem 4y ago
        See also, ArΧiv Vanity: https://www.arxiv-vanity.com/papers/2302.07211/ https://www.arxiv-vanity.com/papers/2302.07211/
- lixtra 4y ago
  The first half page finally made me understand the problem. I didn’t get it from the article.
  - n4r9 4y ago
    The statement in the article: > a limit on the size of a set of integers in which no three of them are evenly spaced This misses a key detail. You can trivially find arbitrarily large such sets e.g. take the first however many powers of 2: 1, 2, 4, 8, 16 ... The missing constraint is that the set of integers must be a subset of { 1, 2, ... , N }.
    - monktastic1 4y ago
      I thought it was pretty clear from this: > Erdős and Turán wanted to know how many numbers smaller than some ceiling N can be put into a set without creating any three-term arithmetic progressions.
- charlieyu1 4y ago
  [flagged]
  - compacct27 4y ago
    True, but we wouldn't be discussing this without the journalism in the first place
    - charlieyu1 4y ago
      Just state the result. 15 year olds can understand big O notation and arithmetic progressions. Instead we get a long article that nobody gets what is actually going on even after reading it.
  - Ar-Curunir 4y ago
    What nonsense. Would you have even heard of this paper if not for Quanta? Also, no mathematician or computer scientist I know has anything negative to say about Quanta.
    - pmezard 4y ago
      I do not really understand the unconditional love for Quanta. Sure it is better it exists than not but I find the articles vague and mostly about people/institution name dropping. "Someone someone from the prestigious MIT said <this is a tremendous result!>". Cool I guess? Take this one: - No clear explanation of the problem to solve. Could have given an example or something to hammer out what is an arithmetic progression of 3 numbers. - No detail about the actual form of the previous bound and the new one. - Not much detail about the actual technique. I get that it become very technical very quickly. But that is the actual job of a science/math journalist to distill this. "They used a well know technique of increasing density, etc.". If it is well know, why not try to describe how it works. I wonder what someone like 3blue1brown would make of this.
      - impendia 4y ago
        > I wonder what someone like 3blue1brown would make of this. Although I am not Grant Sanderson (3blue1brown creator), I would wager very good money that he would strongly approve. I am a research mathematician, I do read Quanta, and I've been interviewed for them also. Overall my impression is that they do a good job of making at least something of contemporary research mathematics accessible to the general public. Most people have very little concept of what we do. It is a notoriously hard task, it is a vitally important one, and it is one that too few people are attempting. Quanta does the best job of it of any publication I know, and for that I am very grateful.
unsupp0rted 4y ago
> Though both Bloom and Sisask had other pressing matters to attend to at the time they received the email — Bloom had just adopted a puppy, while Sisask was in the middle of moving — they quickly set to work verifying the new paper.
bennysonething 4y ago
Please stop with the click bait headlines :(
- tines 4y ago
  Did you read the article? The headline is pretty accurate, if not pretty abstract.
  - colechristensen 4y ago
    It's click bait because it contains zero information about what was actually done.
    - deleted 4y ago
      [deleted]
    - yborg 4y ago
      It's only bait if you bite on it, as you did. I did as well, because I could see it was a Quanta link, and found it quite interesting. Would I have clicked on it if the title was "The Kelley--Meka bounds for sets free of three-term arithmetic progressions?" Probably not. So in this case, I consider myself fortunately baited.
      - phendrenad2 4y ago
        So wait, you're saying that people should just accept that headlines are uselessly hyperbolic, and either (A) click every one of them to see if they're worth your time or (B) never click any, to avoid "biting" and getting "baited"? Eminently practical approach, but we can hope for a better world where this isn't necessary...
        yborg 4y ago
        It seems that there is actually (C) somewhere in there, which would be "apply some judgement" i.e. look at the source, and maybe (D) let someone else on HN bite on it and get a synopsis there.
czbond 4y ago
I'm a practical person. What's the point of spending "time" (brain cycles) on such problems? Is it just a mathematician's version of brain teaser? What useful development comes out of such?
- Vt71fcAqt7 4y ago
  >In late 2021, Kelley and Meka were analyzing the chances that a team of players in a certain cooperative game would be able to win, a standard type of computer science problem. It occurred to them that techniques from research on the size of progression-free sets might be helpful. But they found it easier to directly study those techniques than to apply them to the cooperative game. “My best idea for how to make progress on this problem [was] to actually improve the tool itself, not to use it in a more clever way,” Kelley said. I wish they went into more detail about how this problem was relevant to the other problem.
  - jmblpati 4y ago
    I don't know what specific problem Kelley and Meka were working on, but the connection between arithmetic progression free sets and computer science (especially communication complexity) is somewhat well established. See for example this paper[1] which gives new constructions of "corner-free sets" (which are closely related to 3 arithmetic progression-free sets) by thinking about a specific communication protocol. [1] https://drops.dagstuhl.de/opus/volltexte/2021/14276/pdf/LIPIcs-CCC-2021-2.pdf https://drops.dagstuhl.de/opus/volltexte/2021/14276/pdf/LIPI...
- chriswarbo 4y ago
  > What's the point of spending "time" (brain cycles) on such problems? What's the point of anything? > Is it just a mathematician's version of brain teaser? All of mathematics can be characterised as "brain teasers". Make of that what you will. > What useful development comes out of such? I'm not qualified for this particular example. However, it seems quite number-theoretic, and number-theory has given us such "practical" things as asymmetric encryption and universal computation (Turing's famous paper from 1936 was titled "On Computable Numbers", after all).
giantg2 4y ago
Ok, but what's the use of this data set? Like how does this improve something in the world? Edit: why disagree... with me asking questions?
- burnished 4y ago
  You must be confused, the title specifies computer science and mathematicians - the default assumption here should be that if it is useful no one is going to realize for some decades.
- BeetleB 4y ago
  > Ok, but what's the use of this data set? Same use as the rest of mathematics: Entertainment for those interested in the topic.
- dang 4y ago
  "Please don't post shallow dismissals, especially of other people's work. A good critical comment teaches us something." https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html
  - giantg2 4y ago
    I'm not posting a shallow dismissal. I'm legitimately asking what this applies to since I didn't see anything in the article about potential application. It's fine if there aren't any potential applications too, just like the videos/articles about Rubik's Cubes solving - the people/solutions are impressive even if it doesn't have any practical applications.
    - dang 4y ago
      I would say the main marker of shallow dismissal in your comment was the "Ok, but" (and to some extent the "Like how"). If you say you were asking out of curiosity, I believe you, but in that case your comment pattern-matched to the opposite of your intent, because a question asked out of curiosity would not normally include those markers and would not normally be phrased this way.
mabbo 4y ago
I feel like Quanta just has Terry Tao on speed dial at this point, and that he loves to answer the call. They always ask him about this stuff for their math articles and he always gives great answers. > That Kelley and Meka managed to spot the strength of once-overlooked ideas shows the often fitful nature of mathematical progress — a quality that to Tao is more of a blessing than a curse. “It’s not always the case that math just gets harder and harder and harder,” he said. “Thank God.”
- uptownfunk 4y ago
  Hey nothing wrong with that! Huge fan of Terry Tao. Something magical about how their brains work.
  - mabbo 4y ago
    It definitely wasn't a complaint, haha.
paulpauper 4y ago
This is why America's obsession with trying to boost math scores is possibly a waste of time and money. No amount of math literacy will ever approach anything like this. Those who are gifted and motivated enough will learn the material anyway and there are enough professors who can teach it. People who are professionals are so way far above and beyond anything done by non-professionals. It's not like that with reading or writing, in which knowing how to read means you can in theory appreciate almost any book. I think more emphasis should be on learning the basics, which enough kids find hard enough to do. No reason to try to make high schoolers learn algebra 1 & 2.
- permo-w 4y ago
  >there’s no point planting seeds because plants will grow anyway did you have a bad maths teacher at some point?
- tmhn2 4y ago
  The authors of the paper are academics in university CS departments with heavy math backgrounds (one with a B.S. in mathematics, another was a visiting professor at MIT dept of mathematics). I don't understand what you mean or how it relates to the article or surrounding circumstances.
mherdeg 4y ago
I had a bit of trouble grappling with this. What is the largest AP-3-free set for, say, the integers from 1 to 100? What is the largest N where we've computed it explicitly / how expensive is that to do?
- LegionMammal978 4y ago
  According to the OEIS [0], the set has size 27; you can find its terms in the Dybizbański reference [1]. Presumably, it's been computed up to N = 211, where the B-file ends. [0] https://oeis.org/A003002 https://oeis.org/A003002 [1] https://doi.org/10.37236/2061 https://doi.org/10.37236/2061
miley_cyrus 4y ago
Raghu and I had desks next to each other when we were students - we all knew he was brilliant!
graycat 4y ago
Yes, I saw the article in Quanta. Issue here: Click-bait headlines. Uh, I go to the Quanta Web site ~once a day. I respect Quanta enough not to get torqued at any of their headlines. Also there I pay attention to what fields of content (usually science) and not much to the headlines. For the fields, I tend to pass over medical, social, psychological, and biological sciences and stay with math, physics, cosmology, and engineering, and it is easy enough to guess the field of the content without getting torqued at the headlines. Soooo, net, at Quanta I don't object to their headlines. For the article under discussion, yup, it is in the field of "combinatorics". I bumped into that field while scheduling the fleet at FedEx, in grad school, and in some business problems since. Result: Combinatorics is one heck of a challenge, both in the theory of the pure math (and the field can quickly become pure math, e.g., number theory) and also in the applications in business. In practice we squeak by with a little in theory and a lot in intuitive heuristics and relatively blind enumeration (that exploits powerful computing). So, it would be nice, maybe a biggie in various respects, to have some major progress in combinatorics. So, in such an attack, sure, it would be nice for someone some afternoon to have some big insight, bigger than heap sort instead of bubble sort, the fast Fourier transform instead of the direct approach, of error correcting codes instead of just three copies, etc. So, here is an invitation: Get a sharp, soft pencil, a big, soft eraser, a pad of paper, lean back, put feet up, and have some of the needed big ideas!!! All are invited and welcome!!! After some decades, we are still looking for that big insight!! So, what now? How to modify the attack? One way is, chip away at the problem wherever can see can get something new and apparently relevant, connected, or just anywhere in combinatorics -- or just follow the standard good research criteria of "new, correct, and significant" but at least in sight of the ballpark of combinatorics. So, with that approach, the results in the current Quanta article are an example of the desired and welcome progress.

267 points by theafh 4y ago

thirdmunky 4y ago

Source paper: https://arxiv.org/abs/2302.05537 https://arxiv.org/abs/2302.05537

n4r9 4y ago
Plus much shorter write-up from Bloom and Sisask: https://arxiv.org/abs/2302.07211 https://arxiv.org/abs/2302.07211
- deleted 4y ago
  [deleted]
- red_trumpet 4y ago
  I think you mean this one: https://arxiv.org/abs/2302.07211 https://arxiv.org/abs/2302.07211
  - n4r9 4y ago
    Yes, thank you!
  - rml 4y ago
    automatic conversion to web page available at https://ar5iv.labs.arxiv.org/html/2302.07211 https://ar5iv.labs.arxiv.org/html/2302.07211 (more info about the conversions at https://ar5iv.labs.arxiv.org https://ar5iv.labs.arxiv.org)
    - eternalban 4y ago
      TIL. Thank you for this. https://ar5iv.labs.arxiv.org/ https://ar5iv.labs.arxiv.org/
    - voxelghost 4y ago
      Seems to only be working for papers in TeX?
    - satvikpendem 4y ago
      See also, ArΧiv Vanity: https://www.arxiv-vanity.com/papers/2302.07211/ https://www.arxiv-vanity.com/papers/2302.07211/
lixtra 4y ago
The first half page finally made me understand the problem. I didn’t get it from the article.
- n4r9 4y ago
  The statement in the article: > a limit on the size of a set of integers in which no three of them are evenly spaced This misses a key detail. You can trivially find arbitrarily large such sets e.g. take the first however many powers of 2: 1, 2, 4, 8, 16 ... The missing constraint is that the set of integers must be a subset of { 1, 2, ... , N }.
  - monktastic1 4y ago
    I thought it was pretty clear from this: > Erdős and Turán wanted to know how many numbers smaller than some ceiling N can be put into a set without creating any three-term arithmetic progressions.
charlieyu1 4y ago
[flagged]
- compacct27 4y ago
  True, but we wouldn't be discussing this without the journalism in the first place
  - charlieyu1 4y ago
    Just state the result. 15 year olds can understand big O notation and arithmetic progressions. Instead we get a long article that nobody gets what is actually going on even after reading it.
- Ar-Curunir 4y ago
  What nonsense. Would you have even heard of this paper if not for Quanta? Also, no mathematician or computer scientist I know has anything negative to say about Quanta.
  - pmezard 4y ago
    I do not really understand the unconditional love for Quanta. Sure it is better it exists than not but I find the articles vague and mostly about people/institution name dropping. "Someone someone from the prestigious MIT said <this is a tremendous result!>". Cool I guess? Take this one: - No clear explanation of the problem to solve. Could have given an example or something to hammer out what is an arithmetic progression of 3 numbers. - No detail about the actual form of the previous bound and the new one. - Not much detail about the actual technique. I get that it become very technical very quickly. But that is the actual job of a science/math journalist to distill this. "They used a well know technique of increasing density, etc.". If it is well know, why not try to describe how it works. I wonder what someone like 3blue1brown would make of this.
    - impendia 4y ago
      > I wonder what someone like 3blue1brown would make of this. Although I am not Grant Sanderson (3blue1brown creator), I would wager very good money that he would strongly approve. I am a research mathematician, I do read Quanta, and I've been interviewed for them also. Overall my impression is that they do a good job of making at least something of contemporary research mathematics accessible to the general public. Most people have very little concept of what we do. It is a notoriously hard task, it is a vitally important one, and it is one that too few people are attempting. Quanta does the best job of it of any publication I know, and for that I am very grateful.

unsupp0rted 4y ago

> Though both Bloom and Sisask had other pressing matters to attend to at the time they received the email — Bloom had just adopted a puppy, while Sisask was in the middle of moving — they quickly set to work verifying the new paper.

bennysonething 4y ago

Please stop with the click bait headlines :(

tines 4y ago
Did you read the article? The headline is pretty accurate, if not pretty abstract.
- colechristensen 4y ago
  It's click bait because it contains zero information about what was actually done.
  - deleted 4y ago
    [deleted]
  - yborg 4y ago
    It's only bait if you bite on it, as you did. I did as well, because I could see it was a Quanta link, and found it quite interesting. Would I have clicked on it if the title was "The Kelley--Meka bounds for sets free of three-term arithmetic progressions?" Probably not. So in this case, I consider myself fortunately baited.
    - phendrenad2 4y ago
      So wait, you're saying that people should just accept that headlines are uselessly hyperbolic, and either (A) click every one of them to see if they're worth your time or (B) never click any, to avoid "biting" and getting "baited"? Eminently practical approach, but we can hope for a better world where this isn't necessary...
      - yborg 4y ago
        It seems that there is actually (C) somewhere in there, which would be "apply some judgement" i.e. look at the source, and maybe (D) let someone else on HN bite on it and get a synopsis there.

czbond 4y ago

I'm a practical person. What's the point of spending "time" (brain cycles) on such problems? Is it just a mathematician's version of brain teaser? What useful development comes out of such?

Vt71fcAqt7 4y ago
>In late 2021, Kelley and Meka were analyzing the chances that a team of players in a certain cooperative game would be able to win, a standard type of computer science problem. It occurred to them that techniques from research on the size of progression-free sets might be helpful. But they found it easier to directly study those techniques than to apply them to the cooperative game. “My best idea for how to make progress on this problem [was] to actually improve the tool itself, not to use it in a more clever way,” Kelley said. I wish they went into more detail about how this problem was relevant to the other problem.
- jmblpati 4y ago
  I don't know what specific problem Kelley and Meka were working on, but the connection between arithmetic progression free sets and computer science (especially communication complexity) is somewhat well established. See for example this paper[1] which gives new constructions of "corner-free sets" (which are closely related to 3 arithmetic progression-free sets) by thinking about a specific communication protocol. [1] https://drops.dagstuhl.de/opus/volltexte/2021/14276/pdf/LIPIcs-CCC-2021-2.pdf https://drops.dagstuhl.de/opus/volltexte/2021/14276/pdf/LIPI...
chriswarbo 4y ago
> What's the point of spending "time" (brain cycles) on such problems? What's the point of anything? > Is it just a mathematician's version of brain teaser? All of mathematics can be characterised as "brain teasers". Make of that what you will. > What useful development comes out of such? I'm not qualified for this particular example. However, it seems quite number-theoretic, and number-theory has given us such "practical" things as asymmetric encryption and universal computation (Turing's famous paper from 1936 was titled "On Computable Numbers", after all).

giantg2 4y ago

Ok, but what's the use of this data set? Like how does this improve something in the world? Edit: why disagree... with me asking questions?

burnished 4y ago
You must be confused, the title specifies computer science and mathematicians - the default assumption here should be that if it is useful no one is going to realize for some decades.
BeetleB 4y ago
> Ok, but what's the use of this data set? Same use as the rest of mathematics: Entertainment for those interested in the topic.
dang 4y ago
"Please don't post shallow dismissals, especially of other people's work. A good critical comment teaches us something." https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html
- giantg2 4y ago
  I'm not posting a shallow dismissal. I'm legitimately asking what this applies to since I didn't see anything in the article about potential application. It's fine if there aren't any potential applications too, just like the videos/articles about Rubik's Cubes solving - the people/solutions are impressive even if it doesn't have any practical applications.
  - dang 4y ago
    I would say the main marker of shallow dismissal in your comment was the "Ok, but" (and to some extent the "Like how"). If you say you were asking out of curiosity, I believe you, but in that case your comment pattern-matched to the opposite of your intent, because a question asked out of curiosity would not normally include those markers and would not normally be phrased this way.

mabbo 4y ago

I feel like Quanta just has Terry Tao on speed dial at this point, and that he loves to answer the call. They always ask him about this stuff for their math articles and he always gives great answers. > That Kelley and Meka managed to spot the strength of once-overlooked ideas shows the often fitful nature of mathematical progress — a quality that to Tao is more of a blessing than a curse. “It’s not always the case that math just gets harder and harder and harder,” he said. “Thank God.”

uptownfunk 4y ago
Hey nothing wrong with that! Huge fan of Terry Tao. Something magical about how their brains work.
- mabbo 4y ago
  It definitely wasn't a complaint, haha.

paulpauper 4y ago

This is why America's obsession with trying to boost math scores is possibly a waste of time and money. No amount of math literacy will ever approach anything like this. Those who are gifted and motivated enough will learn the material anyway and there are enough professors who can teach it. People who are professionals are so way far above and beyond anything done by non-professionals. It's not like that with reading or writing, in which knowing how to read means you can in theory appreciate almost any book. I think more emphasis should be on learning the basics, which enough kids find hard enough to do. No reason to try to make high schoolers learn algebra 1 & 2.

permo-w 4y ago
>there’s no point planting seeds because plants will grow anyway did you have a bad maths teacher at some point?
tmhn2 4y ago
The authors of the paper are academics in university CS departments with heavy math backgrounds (one with a B.S. in mathematics, another was a visiting professor at MIT dept of mathematics). I don't understand what you mean or how it relates to the article or surrounding circumstances.

mherdeg 4y ago

I had a bit of trouble grappling with this. What is the largest AP-3-free set for, say, the integers from 1 to 100? What is the largest N where we've computed it explicitly / how expensive is that to do?

LegionMammal978 4y ago
According to the OEIS [0], the set has size 27; you can find its terms in the Dybizbański reference [1]. Presumably, it's been computed up to N = 211, where the B-file ends. [0] https://oeis.org/A003002 https://oeis.org/A003002 [1] https://doi.org/10.37236/2061 https://doi.org/10.37236/2061

miley_cyrus 4y ago

Raghu and I had desks next to each other when we were students - we all knew he was brilliant!

graycat 4y ago

Yes, I saw the article in Quanta. Issue here: Click-bait headlines. Uh, I go to the Quanta Web site ~once a day. I respect Quanta enough not to get torqued at any of their headlines. Also there I pay attention to what fields of content (usually science) and not much to the headlines. For the fields, I tend to pass over medical, social, psychological, and biological sciences and stay with math, physics, cosmology, and engineering, and it is easy enough to guess the field of the content without getting torqued at the headlines. Soooo, net, at Quanta I don't object to their headlines. For the article under discussion, yup, it is in the field of "combinatorics". I bumped into that field while scheduling the fleet at FedEx, in grad school, and in some business problems since. Result: Combinatorics is one heck of a challenge, both in the theory of the pure math (and the field can quickly become pure math, e.g., number theory) and also in the applications in business. In practice we squeak by with a little in theory and a lot in intuitive heuristics and relatively blind enumeration (that exploits powerful computing). So, it would be nice, maybe a biggie in various respects, to have some major progress in combinatorics. So, in such an attack, sure, it would be nice for someone some afternoon to have some big insight, bigger than heap sort instead of bubble sort, the fast Fourier transform instead of the direct approach, of error correcting codes instead of just three copies, etc. So, here is an invitation: Get a sharp, soft pencil, a big, soft eraser, a pad of paper, lean back, put feet up, and have some of the needed big ideas!!! All are invited and welcome!!! After some decades, we are still looking for that big insight!! So, what now? How to modify the attack? One way is, chip away at the problem wherever can see can get something new and apparently relevant, connected, or just anywhere in combinatorics -- or just follow the standard good research criteria of "new, correct, and significant" but at least in sight of the ballpark of combinatorics. So, with that approach, the results in the current Quanta article are an example of the desired and welcome progress.