Hacker News new | past | comments | ask | show | jobs | submit login

I was confused by this article. It says that for every k, then all sufficiently large sets have an arithmetic progression of length k.

But suppose we set k = 3, and take the set {1, 2, 4, 8, ..., 2^n}. Then no matter how big n is, we have no arithmetic progression of length 3.

Looking into this, it appears that the article misstated the result, called Szemerédi's theorem: “if the positive integers are partitioned into finitely many classes, then at least one of these classes contains arbitrarily long arithmetic progressions”. https://www.semanticscholar.org/paper/A-new-proof-of-Szemeré...






The theorem you quoted is Van der Waerden's theorem [0], not Szemerédi's. It is significantly easier to prove than Szemerédi's result.

The article correctly states Szemerédi's theorem, if you interpret "sufficiently large" to mean "positive density": For every density delta > 0 and length k, there exists an n0 such that every subset of {1, ..., n} (n > n0) of density at least delta (that is, at least delta * n elements) contains an arithmetic progression of length k.

For n large, your set has density roughly (log N)/N (where N = 2^n), which is not bounded from below by any constant delta > 0; this is why Szemerédi's theorem does not apply. Speaking of your example, you might be interested in Behrend's construction [1], a way of constructing "large" sets (for another definition of large) with no 3-term arithmetic progression.

Szemerédi's theorem easily implies Van der Waerden's theorem because if you colour the integers with finitely many colours, you can apply Szemerédi's theorem to the largest colour class.

[0] https://en.wikipedia.org/wiki/Van_der_Waerden%27s_theorem [1] https://www.ncbi.nlm.nih.gov/pmc/articles/PMC1078964/pdf/pna...


There's a lot of interesting trivia related to this. For instance, the sequence of perfect squares {1,4,9,...} contains 3-term subsequences that are in arithmetic progression (e.g., {1,25,49}). However, it does not contain any 4-term such subsequences. And if you consider the sequence of nth powers, for n > 2, it does not contain any arithmetic progressions at all. This claim turns out to be very similar to Fermat's Last Theorem and can be established with similar techniques. (See https://math.berkeley.edu/~ribet/Articles/acta.pdf, with alpha = 1. Note that this is the same Ribet of Ribet's theorem, which established the link between modularity of elliptic curves and FLT, setting the stage for Wiles.)

The example given in the article elaborates that the sets have bounded range, e.g. for a given size N, the set’s values must range from 0 to mN for some m > 1.

The results therefore depend on both m and N.

Equivalently, you can pick the length of your range first and then pick a ‘density’ d, where d * length is the size of the set (this matches the formulation given in the article).




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: