Avoiding triples in arithmetic progression

Some patterns cannot be avoided ad infinitum. A well-known example of such a pattern is an arithmetic progression in partitions of natural numbers. We observed that in order to avoid arithmetic progressions, other patterns emerge. A visualization is presented that reveals these patterns. We capitalize on the observed patterns by constructing techniques to avoid arithmetic progressions.

More formally, van der Waerden numbers $W(k, l)$ express the smallest $n$ such that partitioning $\lbrace 1, \dotsc , n \rbrace$ into $k$ sets yields at least one set containing an arithmetic progression of length at least $l$. Computing these numbers for $l \gt 2$ is a very hard combinatorial problem. We focus on avoiding triples $(l = 3)$ in arithmetic progressions. We guide the search procedure by transforming observed symmetries in best known lower bounds into additional constraints. Using our method, several lower bounds for van der Waerden numbers have been improved. As a consequence, a new pattern also emerges between the best known lower bounds. We conclude with open problems regarding van der Waerden numbers as well as some bold conjectures that challenges existing work on the subject.

Keywords

van der Waerden numbers, SAT, symmetries

2010 Mathematics Subject Classification

Primary 05D10. Secondary 68R05.

Full Text (PDF format)

This work is supported by the NSF under grant number CCF-1526760.

Received 17 May 2017

Published 21 June 2017