2011/07/14 by Lu, Linyuan, Peng, Xing · 1 citation
#05D10 #11B25 #Combinatorics (math.CO) #FOS: Mathematics #Number Theory (math.NT)
paper · doi:10.48550/arxiv.1107.2888
This paper is motivated by a recent result of Wolf \citewolf on the minimum number of monochromatic 4-term arithmetic progressions(4-APs, for short) in \Zp, where p is a prime number. Wolf proved that there is a 2-coloring of \Zp with 0.000386% fewer monochromatic 4-APs than random 2-colorings; the proof is probabilistic and non-constructive. In this paper, we present an explicit and simple construction of a 2-coloring with 9.3% fewer monochromatic 4-APs than random 2-colorings. This problem leads us to consider the minimum number of monochromatic 4-APs in \Zn for general n. We obtain both lower bound and upper bound on the minimum number of monochromatic 4-APs in all 2-colorings of \Zn. Wolf proved that any 2-coloring of \Zp has at least (1/16+o(1))p2 monochromatic 4-APs. We improve this lower bound into (7/96+o(1))p2. Our results on \Zn naturally apply to the similar problem on [n] (i.e., \1,2,..., n\). In 2008, Parillo, Robertson, and Saracino \citeprs constructed a 2-coloring of [n] with 14.6% fewer monochromatic 3-APs than random 2-colorings. In 2010, Butler, Costello, and Graham \citeBCG extended their methods and used an extensive computer search to construct a 2-coloring of [n] with 17.35% fewer monochromatic 4-APs (and 26.8% fewer monochromatic 5-APs) than random 2-colorings. Our construction gives a 2-coloring of [n] with 33.33% fewer monochromatic 4-APs (and 57.89% fewer monochromatic 5-APs) than random 2-colorings.