from Hacker News

Graduate Student Solves Classic Problem About the Limits of Addition

by sonabinu on 5/23/25, 11:15 AM with 11 comments

• by svat on 5/25/25, 3:53 PM

  So cool. On the one hand, going from n/3 to (n/3 + log log n) seems like such a small improvement, but as the article shows, the history is formidable:

  - n/3 (Erdős, 1965)

  - (n+1)/3 (Alon and Kleitman, 1990)

  - (n+2)/3 (Bourgain, 1997)

  - n/3 + Ω(log log n) (this paper, Benjamin Bedert, https://arxiv.org/abs/2502.08624)

  And the upper bound:

  - n/3 + o(n) (Eberhard, Green, Manners, 2014).

  Ben Green's list of 100 open problems is which this is (was?) Problem 1, is here: https://people.maths.ox.ac.uk/greenbj/papers/open-problems.p...

• by VladVladikoff on 5/25/25, 12:46 PM

  Why is the lower bound N/3 and not N/2? Doesn’t the set of all odd numbers make the lower bound N/2?

• by dooglius on 5/25/25, 5:58 PM

  It's weird to spend paragraphs talking about the incremental improvements to (N+1)/3 and (N+2)/3 and then miss that the new bound is N/3 + c*log(log(n)) for some c>0, not N/3+log(log(n))

• by nyc111 on 5/25/25, 5:21 PM

  Is the main subject here addition or sets?