Skip to main content

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

8
  • 2
    Great answer, the first that says anything definitive about this problem. So the Cantor-like set has n^0.63 1s, which means that the "check all pairs of 1s" algorithm is at least n^1.26 (≫ n log n) in the worst case. The lower bound quoted in Szemeredi's paper (BTW the Moser paper he quotes is available here: books.google.com/books?id=Cvtwu5vVZF4C&pg=PA245 ) seems to actually imply n^(2-o(1)), but we must be slightly careful because there we have numbers drawn from {1,...,n} but here it's the sum of the numbers in the sequence that is n. Commented Oct 18, 2009 at 8:31
  • Er, what exactly is the "Cantor-like" binary sequence that contains n^(log_3 2) 1s in it and no three evenly spaced 1s? Commented Oct 18, 2009 at 8:46
  • Example: 101000101000000000101000101. Its length is 3^n, and has 2^n ones (so n^0.63 density). If you write down the places of 1's in binary, it will be {0,2,20,22,200,202,220,222}. Another possible way to think of it is take a sequence of ones, and continuously remove "middle" ones as in normal Cantor set construction: 111111111 -> 111000111 -> 101000101. The reason why it doesn't contain arithmetic progression is: if x, y, z formed one, then y=(x+z)/2 and x and z differ on some expansion place. Take the most significant one. Say x has 0 and z has 2. Then y must have 1 there. contradiction. Commented Oct 18, 2009 at 9:40
  • 3
    Again, great research! I followed up on the 2008 3SUM paper, and it referred to CLRS Exercise. 30.1-7, after looking at which I got the answer — the O(n log n) algorithm is actually quite simple! (Just squaring a polynomial/generatingfunction.) I've posted the answer below. (Now kicking myself for not having thought of it earlier... simple solutions always elicit that reaction :p) Commented Oct 18, 2009 at 16:36
  • So, the answer to his exam question was something like, "This problem is reducible to the 3-SUM hard problem, and 3-SUM hard has no sub-quadratic solution, so this problem cannot be solved in O(n logn)." Yes? Commented Oct 18, 2009 at 18:57