Graduate Student Solves Classic Problem About the Limits of Addition | Hacker News Reader

Graduate Student Solves Classic Problem About the Limits of Addition

quantamagazine.org

76 pointssonabinu11 comments

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...

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?

N/3 + log log N holds for any arbitrary set, not just for 1 … N or something.

An adversary first gives you any set, and then you have to find a subset.

They could give you only even numbers.

Ohhhh ok thanks!

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))

Is the main subject here addition or sets?

It concerns the size of the largest sum-free set [0]. Take a (finite) set of integers, A. What is the largest subset of A such that no two entries sum to a third.

The previous results was not much better than |A|/3. The current, just proved, result shows that the largest subset is |A|/3 + c log(log(|A|)).

For example, the set {1,2,3} is not sum-free (1+2 = 3) but the subset {2,3} is sum-free (2+3 \notin {2,3}).

[0] https://en.wikipedia.org/wiki/Sum-free_set

"It concerns the size of the largest sum-free set [0]. Take a (finite) set of integers, A. What is the largest subset of A such that no two entries sum to a third."

Yes, it seems to me we are focusing mainly about sets, not addition. Addition is secondary. Mainly I'm debating the title. The word "set" ought to be in the title too. I guess not a big deal.

I see. Yes, I agree, the title is bad.

Although as students we learn addition before we learn about sets, from the viewpoint of mathematics, sets are everywhere / everything can be expressed in terms of sets, so there's no point talking about sets in any given problem (unless it involves matters deep in set theory, which this does not). This is evident even colloquially, where we can talk about problems without explicitly using the word “set” — for example, “given some numbers, how many can you pick such that no two of them add up to another?” — while it's hard to avoid using “add” or “addition”.

So this problem is really more about addition than about sets, as the mathematicians who worked on it will say: the amount of set theory it involves is very little/almost nonexistent, while the properties of addition it involves are fairly deep.

(But sure, no harm if sets were mentioned in the title, I guess!)

Reply on news.ycombinator.com