Monochromatic 4-term arithmetic progressions in 2-colorings of Z_n

DOI10.1016/J.JCTA.2011.12.004zbMATH Open1293.05385arXiv1107.2888OpenAlexW2147906032MaRDI QIDQ412187FDOQ412187

Authors: Linyuan Lu, Xing Peng 

Publication date: 4 May 2012

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Abstract: 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 $$, where $p$ is a prime number. Wolf proved that there is a 2-coloring of $$ 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 $$ for general $n$. We obtain both lower bound and upper bound on the minimum number of monochromatic 4-APs in all 2-colorings of $$. Wolf proved that any 2-coloring of $$ 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 $$ naturally apply to the similar problem on $[n]$ (i.e., $1,2,\mathrm{...},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.

Full work available at URL: https://arxiv.org/abs/1107.2888

Recommendations

• The minimum number of monochromatic 4-term progressions in \(\mathbb Z_p\)
• Progressions in every two-coloration of \(Z_ n\)
• Monochromatic solutions to \(x+y=z^2\) in the interval \([N,cN^4]\)
• On four color monochromatic sets with nondecreasing diameter
• scientific article; zbMATH DE number 2061965
• Some arithmetical restatements of the four color conjecture
• On the existence of rainbow 4-term arithmetic progressions
• Arithmetic progressions, quasi progressions, and Gallai-Ramsey colorings
• Monochromatic arithmetic progressions with large differences
• On modular monochromatic \((2,0)\)-colorings

zbMATH Keywords

2-colorings of \([n\)]2-colorings of \(\mathbb Z_n\)2-colorings of \(\mathbb Z_p\)monochromatic arithmetic progressions

Mathematics Subject Classification ID

Other combinatorial number theory (11B75) Ramsey theory (05D10) Arithmetic progressions (11B25)

Cites Work

• A 2-coloring of \([1, N]\) can have \((1/22) N^2+O(N)\) monochromatic Schur triples, but not less
• The minimum number of monochromatic 4-term progressions in \(\mathbb Z_p\)
• On monochromatic solutions of equations in groups
• Quantitative theorems for regular systems of equations
• On the number of monochromatic Schur triples.
• The number of monochromatic Schur triples
• On the monochromatic Schur triples type problem
• On the asymptotic minimum number of monochromatic 3-term arithmetic progressions
• Finding Patterns Avoiding Many Monochromatic Constellations

Cited In (8)

• Counting patterns in colored orthogonal arrays
• Unrolling residues to avoid progressions
• Monochromatic progressions in random colorings
• On the existence of rainbow 4-term arithmetic progressions
• From discrete to continuous: monochromatic 3-term arithmetic progressions
• The minimum number of monochromatic 4-term progressions in \(\mathbb Z_p\)
• Using Ramsey theory to measure unavoidable spurious correlations in big data
• Linear configurations containing 4-term arithmetic progressions are uncommon

Uses Software

• RON

This page was built for publication: Monochromatic 4-term arithmetic progressions in 2-colorings of \(\mathbb Z_n\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q412187)