Monochromatic 4-term arithmetic progressions in 2-colorings of $\mathbb Z_n$

Details Monochromatic 4-term arithmetic progressions in 2-colorings of $\mathbb Z_n$ Monochromatic 4-term arithmetic progressions in 2-colorings of $\mathbb Z_n$

2011-07-14

arxiv.org/abs/1107.2888v1

Mathematics

Combinatorics

23 pages, 4 figures

Scientific paper

This paper is motivated by a recent result of Wolf \cite{wolf} on the minimum number of monochromatic 4-term arithmetic progressions(4-APs, for short) in $\Z_p$, where $p$ is a prime number. Wolf proved that there is a 2-coloring of $\Z_p$ 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 $\Z_n$ for general $n$. We obtain both lower bound and upper bound on the minimum number of monochromatic 4-APs in all 2-colorings of $\Z_n$. Wolf proved that any 2-coloring of $\Z_p$ has at least $(1/16+o(1))p^2$ monochromatic 4-APs. We improve this lower bound into $(7/96+o(1))p^2$. Our results on $\Z_n$ naturally apply to the similar problem on $[n]$ (i.e., $\{1,2,..., n\}$). In 2008, Parillo, Robertson, and Saracino \cite{prs} constructed a 2-coloring of $[n]$ with 14.6% fewer monochromatic 3-APs than random 2-colorings. In 2010, Butler, Costello, and Graham \cite{BCG} 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.

Affiliated with

Also associated with

No associations

Rating

Monochromatic 4-term arithmetic progressions in 2-colorings of $\mathbb Z_n$ does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Monochromatic 4-term arithmetic progressions in 2-colorings of $\mathbb Z_n$, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Monochromatic 4-term arithmetic progressions in 2-colorings of $\mathbb Z_n$ will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-225920