- #1
- 2,845
- 0
Meta-note: This post includes both computer science and computational number theory. I could have posted it in the Programming forum, the CS forum, the NT forum, or here; I felt that this was the best place, especially since the CS forum does not actually deal with computer science these days.
I was looking to verify some of the bounds on van der Waerden numbers, in particular the new ones posted at the http://www.st.ewi.tudelft.nl/sat/waerden.php. I thought this would be a good exercise for me, and that's what the certificates are for, right?
Apart from checking that numbers appear exactly once, the problem comes down to checking that there are no long arithmetic progressions in each of the sequences. I started by coding a direct implementation of Jeff Erickson's quadratic algorithm: Finding longest arithmetic progressions. The trouble is that the method requires an n x n array to find the longest progression in a list of length n, so verifying a lower bound of L for W(r, k) requires at least ceil(L/r)^2 memory. As I was using Pari (where a number takes at least 128 bits, I believe), this limited me to about 16,000 (in theory, with r = 2 and 1 GB of free memory) and only about 9,000 in practice (for r = 2 -- more for larger r).
Is there a good way to go further? Quadratic time and space won't let me verify large bounds. Is there a more memory-efficient algorithm, or perhaps a time-space tradeoff I can use?
I was looking to verify some of the bounds on van der Waerden numbers, in particular the new ones posted at the http://www.st.ewi.tudelft.nl/sat/waerden.php. I thought this would be a good exercise for me, and that's what the certificates are for, right?
Apart from checking that numbers appear exactly once, the problem comes down to checking that there are no long arithmetic progressions in each of the sequences. I started by coding a direct implementation of Jeff Erickson's quadratic algorithm: Finding longest arithmetic progressions. The trouble is that the method requires an n x n array to find the longest progression in a list of length n, so verifying a lower bound of L for W(r, k) requires at least ceil(L/r)^2 memory. As I was using Pari (where a number takes at least 128 bits, I believe), this limited me to about 16,000 (in theory, with r = 2 and 1 GB of free memory) and only about 9,000 in practice (for r = 2 -- more for larger r).
Is there a good way to go further? Quadratic time and space won't let me verify large bounds. Is there a more memory-efficient algorithm, or perhaps a time-space tradeoff I can use?