Rainbow AP(4) in an almost equinumerous coloring

Rainbow AP$4$ in an almost equinumerous coloring

Definitions and mathematical statement

For a prime $p\ge5$, let $\mathbb Z_p=\mathbb Z/p\mathbb Z$ with addition modulo $p$. A four-colouring is a map $\chi:\mathbb Z_p\to\{1,2,3,4\}$, with colour classes $C_i=\chi^{-1}(i)$. Call it almost equinumerous if \[ |C_i|\in\{\lfloor p/4\rfloor,\lceil p/4\rceil\} \qquad(1\le i\le4). \] Thus all classes differ in size by at most one; the sizes necessarily sum to $p$. This is a condition on all residues, not on intervals of representatives.

A four-term arithmetic progression in $\mathbb Z_p$ is an ordered list $a,a+d,a+2d,a+3d$ with $a\in\mathbb Z_p$ and $d\in\mathbb Z_p\setminus\{0\}$. Its four entries are distinct because $p\ge5$. It is rainbow when the four values of $\chi$ on these entries are pairwise different.

Does there exist an integer $p_0$ such that for every prime $p\ge p_0$ and every almost equinumerous four-colouring, a rainbow four-term arithmetic progression exists? The threshold is independent of the colouring. A negative answer requires counterexamples for arbitrarily large primes, not merely an exceptional small prime. Progressions may wrap around the chosen residue representatives, since the equations are in $\mathbb Z_p$. The source asks for the prime cyclic group: substituting a composite-order cyclic group changes the problem. No particular common difference or particular order of the four colours is prescribed.

Short English statement

Must every sufficiently large prime cyclic group, split into four almost equal colour classes, contain a four-term progression using all four colours?

Research attempt

Scope and process.

This is a GPT-6 Astra Ultra research attempt dated 1 October 2026, using primary-source browsing and elementary mathematical checks. The canonical definition above is retained. Results below are restricted results or reductions, not a claim of a new solution to the entire catalogue question. No formal proof assistant or external mathematical referee checked this text.

Literature and chosen attack.

The original page [S2, R1] explicitly separates prime cyclic groups from composite cyclic groups, where balanced rainbow-free examples are possible. We keep the prime hypothesis and examine two approaches: a constructive interval subcase, and counting monochromatic pairs inside progressions. The second approach exposes a quantitative deficit rather than providing a universal proof.

A proved subcase: four consecutive arcs.

Suppose each colour class is one interval of consecutive residues around the circle. Rotate the circle and rename colours so these intervals occur in order $C_0,C_1,C_2,C_3$, starting at zero. Write $p=4q+r$ with $0\le r\le3$. Each interval has length $q$ or $q+1$, and its left endpoint is $b_j=jq+s_j$, where $0\le s_j\le3$ counts the preceding long intervals. If $q\ge4$, choose any integer $a\in[3,q-1]$. Then for $j=0,1,2,3$, \[ b_j\le a+jq\le b_j+q-1. \] The first inequality uses $s_j\le3\le a$, and the second uses $a\le q-1\le q-1+s_j$. Thus $a+jq\in C_j$, and the progression with difference $q$ is rainbow. Its last term is at most $4q-1<p$, so no wraparound convention is being hidden. There are at least $q-3$ such ordered progressions with this difference. Translating back proves the assertion for every balanced four-arc colouring when $p\ge17$. No primality was actually needed for this restricted construction.

Exact collision count for an arbitrary colouring.

Let $n_i=|C_i|$ and, for $(a,d)\in\mathbb Z_p\times\mathbb Z_p^*$, let $Q(a,d)$ count the unordered pairs of positions in $(a,a+d,a+2d,a+3d)$ with equal colours. For each $0\le j<k\le3$, the map \[ (a,d)\longmapsto(a+jd,a+kd) \] is a bijection onto ordered pairs of distinct residues: recover $d=(y-x)/(k-j)$ and $a=x-jd$. This uses $p\ge5$, so $k-j$ is invertible. Hence \[ \sum_{a,d\ne0}Q(a,d)=6\sum_{i=1}^4n_i(n_i-1). \] Every non-rainbow progression has $Q\ge1$. If $R$ is the number of rainbow ordered progressions, the union bound therefore yields \[ R\ge p(p-1)-6\sum_i n_i(n_i-1). \] For balanced sizes the right side is $-p^2/2+5p+O(1)$, which is negative for large $p$. Thus this exact two-point information is too weak to force even one rainbow progression. Balance does not supply the higher-order correlation information missing from this inequality.

Why a random calculation also does not prove the target.

Uniformly assign the four colours with fixed positive class sizes $n_i$. For any fixed progression its four distinct positions have four different colours with probability \[ \frac{4!\,n_1n_2n_3n_4}{p(p-1)(p-2)(p-3)}. \] Multiplying by $p(p-1)$ gives the exact expected number of rainbow progressions. For balanced sizes it is $(3/32+o(1))p^2$, so some balanced colourings have many. The quantifier in the problem is every balanced colouring, however; a positive expectation neither excludes zero-count colourings nor establishes a uniform lower bound.

Verification and first remaining gap.

The interval proof permits the long classes in any order and uses no special prime residue class modulo four. The counting proof counts ordered $(a,d)$, including reversals, consistently on both sides. The missing result is a bound on structured colour correlations for arbitrary balanced classes strong enough to force $R>0$. Neither average colour-class sizes nor the two-point identity gives it.

Final status.

UNRESOLVED. The consecutive-arc subcase and exact counting identities are proved; no threshold valid for all balanced colourings is established.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3039 (OPG-478), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Rainbow AP$4$ in an almost equinumerous coloring. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/rainbow_ap_4_in_an_almost_equinumerous_coloring.

• R1 David Conlon, problem as posted by Veselin Jungić, Rainbow AP$4$ in an almost equinumerous coloring, original problem page and bibliography, checked 1 October 2026. https://www.openproblemgarden.org/op/rainbow_ap_4_in_an_almost_equinumerous_coloring.