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

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






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

Search: