Fabian Arevalo

Bishnoi–Cames van Batenburg–Ravi, Problem 1 · finite geometry · session 2026-09-01

A five-colouring of PG(7,2), if it exists, has almost no symmetry

On the newest open case of the chromatic number of projective spaces: a Mersenne-prime obstruction proved for all dimensions, certified exclusions at orders 17, 5 and the Frobenius map, and hence that every witness has a 2-group stabiliser. The value χ₂(8) itself is left open.
1 September 2026 · AI-assisted (Claude), see disclosure · code, data and certificates

Start here, no maths required

Take all 255 non-zero strings of eight bits. Call three of them a line when the third is the bitwise XOR of the other two, which is the same as saying the three of them XOR to zero. There are 10,795 such lines. Now try to paint the 255 strings with five colours so that no line ever comes out all one colour.

Nobody knows whether it can be done. Five is the interesting number: with six colours it is easy, and with four it is impossible. The question of whether five suffices was posed in December 2025 by Anurag Bishnoi, Wouter Cames van Batenburg and Jozefien Ravi, who worked out the answer for every smaller number of bits. Seven bits: five colours are enough. Eight bits: open.

This session did not settle it. What it did was take away the tools you would naturally reach for. A common way to build such a colouring is to make it symmetric: find a shuffle of the strings that preserves the XOR structure, and paint whole orbits of that shuffle a single colour, so you only have to decide a few dozen colours instead of 255. This note shows that trick cannot work here. Every symmetry of odd order is dead. Some die to a one-paragraph argument, which the figure below is; the rest died to certified computer search. Anything that paints PG(7,2) in five colours has to be, in a precise sense, lopsided.

seven points, one orbit
Why an order-7 symmetry can never help, in one picture. The seven dots are the non-zero strings of three bits, drawn as the Fano plane: the seven lines are the three sides, the three medians and the circle, and each is a triple XOR-ing to zero. The shuffle being applied is multiplication by a generator of the field with eight elements, which preserves every line. Watch where it sends the starting point: it walks through all seven, so the orbit is everything. A colouring that is constant on orbits is therefore constant, and every one of those seven lines is monochromatic. The same argument runs for any Mersenne prime order, 3, 7, 31, 127, inside any dimension, which is Lemma B. The orbit is computed here from the field arithmetic, not stored.

What this note adds

  1. A one-paragraph proof that kills four symmetry orders at once. No proper colouring of any of these spaces, with any number of colours, can be symmetric under a shuffle whose order is 3, 7, 31 or 127. Those are the Mersenne primes available, and the reason is the picture above.
  2. The two survivors were killed by certified computation. Order 17 and the squaring map fall in seconds with small proof files. Order 5, the hard one, needed a 40-minute search and a proof of 812 megabytes for one of its two cases.
  3. So every five-colouring of PG(7,2) has a symmetry group of size a power of two. That is the theorem. It rests on one two-line hand-proved lemma about relabelling colours, which is stated rather than hidden.
  4. One dimension down, the symmetric colouring does exist. An explicit order-5-symmetric five-colouring of the 127 strings of seven bits, with colour classes of sizes 21, 21, 25, 27 and 33, verified from the definition. So whatever kills the symmetry at eight bits is not inherited from seven.
  5. χ₂(8) is still open. Nothing here decides it. The circumstantial evidence points at 6, and it is labelled as evidence.

Everything below is the technical version. The ledger in Section 2 is the whole result in one table.

AbstractSummary of results

Bishnoi, Cames van Batenburg and Ravi (arXiv:2512.01760) determine the chromatic number χ₂(n) of PG(n−1,2), the least number of colours on the non-zero vectors of F₂n with no monochromatic line {x, y, x⊕y}, for all n ≤ 7, and ask in their Problem 1 whether χ₂(8) is 5 or 6. A positive answer would give the multicolour Ramsey bound R(3;5) ≥ 257. We do not decide χ₂(8). We constrain any witness severely.

Lemma B (PROVED). For every prime p = 2d − 1 with d ≥ 2, no proper colouring of any PG(n−1,2), with any number of colours, is invariant under a collineation of order p. Such an element has an irreducible invariant d-space whose 2d − 1 = p non-zero points form a single orbit, and that orbit spans lines. In GL(8,2) this kills orders 3, 7, 31 and 127 at one stroke, leaving only 5 and 17 among odd prime orders.

CERTIFIED. No proper 5-colouring of PG(7,2) is invariant under any order-17 collineation (single Sylow class, orbit-contracted 75-variable instance, UNSAT, 131-lemma DRUP proof), nor under the Frobenius map x ↦ x² of F256 (35 cells, UNSAT, 2,060-lemma proof). Both proofs were re-verified for this page by an independently written checker. Order 5, both conjugacy classes, is UNSAT after colour-symmetry breaking: the [C,I] leg by Glucose42 in 5.5 s with a DRUP proof of 166,270 lemmas, verified by the repository's checker, by drat-trim, and again independently for this page; the [C,C] leg by kissat in about 40 minutes with an 812 MB DRAT proof verified by drat-trim in 2,174 s.

Theorem 1. The automorphism group of any proper 5-colouring of PG(7,2) is a 2-group. Sole proviso: a two-line colour-WLOG lemma, proved in the note, which the symmetry breaking uses. The unbroken [C,I] instance was subsequently also decided UNSAT by kissat in about 90 minutes, removing that proviso for one leg as a solver verdict, though its 6.7 GB proof was too large to check.

Section 1The setting

Points of PG(n−1,2) are the non-zero vectors of F₂n; the line through distinct x, y is {x, y, x⊕y}. PG(7,2) has 255 points and (2⁸−1)(2⁸−2)/6 = 10,795 lines. A colour class avoids monochromatic lines exactly when it is sum-free, so a proper k-colouring is a partition of F₂n ∖ {0} into k sum-free sets.

From the source paper: χ₂(n) = 2, 3, 3, 4, 5, 5 for n = 2…7; χ₂(n) ≤ ⌊2n/3⌋ + 1 always; and χ₂(8) ∈ {5,6} with Problem 1 asking which. Their §6.1 records that χ₂(n) ≤ k implies R(3;k) > 2n, and the known range 162 ≤ R(3;5) ≤ 307 secondary: those Ramsey bounds are quoted from that paper and were not re-derived here. The paper contains no computational work on n = 8.

The full collineation group is GL(8,2), of order 228·3⁵·5²·7²·17·31·127. A colouring is φ-invariant when every colour class is a union of ⟨φ⟩-orbits. The strategy of the session is to walk the odd part of that order and kill it.

Section 2The ledger

orderverdict at n = 8, k = 5howcertificate
3no invariant colouringLemma B (Mersenne)proof, all n and k
7no invariant colouringLemma B (Mersenne)proof, all n and k
31no invariant colouringLemma B (Mersenne)proof, all n and k
127no invariant colouringLemma B (Mersenne)proof, all n and k
17UNSATorbit-contracted SAT, 75 vars131-lemma DRUP, re-verified
Frobenius x ↦ x²UNSAT35 orbit cells2,060-lemma DRUP, re-verified
5, class [C,I]UNSAT63 cells, colour-broken166,270-lemma DRUP, re-verified
5, class [C,C]UNSAT51 cells, colour-broken812 MB DRAT, drat-trim only
2-power ordersnot excluded—the theorem stops here

By Cauchy's theorem an odd-order element has an odd prime order, so the first eight rows leave only 2-power orders, which is Theorem 1. The one soft spot is the colour-WLOG lemma used by the two order-5 rows: the SAT instances break the S₅ action on colour names by a value-precedence constraint, and soundness of that break is a two-line argument proved in the note rather than a certificate. Any claim resting on it is Certified modulo a hand lemma and is marked so throughout.

Two exclusions are worth separating from the rest because their trust base differs. The [C,I] proof is pure RUP and was checked three ways: by the repository's own from-the-definition checker, by drat-trim, and by a checker written from scratch during this publish pass, which re-derived the empty clause after 166,270 lemmas. The [C,C] proof contains RAT lemmas and exists only as an 812 MB binary DRAT file, too large to commit; it ships as a SHA-256 hash and a regeneration command, and its checker of record is drat-trim alone.

Beyond the prime orders, the session also swept the natural structured families and found them all dead by inspection rather than by search: every cyclic multiplicative subgroup of orders 3, 5, 15, 17, 51, 85 and 255, and about twenty block-diagonal Singer, twisted and swap families. In each the group acts transitively on a punctured subspace, which puts a whole line inside one orbit.

Section 3One dimension down, the symmetry survives

The contrast is the point. At n = 7 an order-5-invariant proper 5-colouring does exist, and the session built one.

31 cells, 24 of size five and 7 fixed
The witness at n = 7, and the empty slot at n = 8. The upper strip is the 127 points of PG(6,2), grouped into the 31 orbits of an order-5 collineation and shaded by the committed witness; the five colours are drawn as five fill densities, since this page has no palette. Each block is visibly constant, which is what invariance means. The lower strip is the 255 points of PG(7,2), left empty, because Theorem 1 says no order-5 grouping of it can be filled in this way. Both buttons run real checks in your browser: the first tests all 2,667 lines of PG(6,2) for monochromacy from the definition, the second rebuilds the field with 16 elements from x⁴ + x + 1, reconstructs the order-5 map, and confirms the witness is constant on every one of its orbits.

Its colour classes have sizes 21, 21, 25, 27 and 33, and its symmetric family is large: at least 10⁵ invariant cell-colourings at the quotient level. Whatever kills 5-colourings at n = 8 is not visible one level down.

Lemma A · PROVED

In any proper 5-colouring of PG(7,2), every colour class meets every one of the 255 hyperplanes, and the restriction to each hyperplane is a proper 5-colouring of PG(6,2) using all five colours. Otherwise four colours would properly colour PG(6,2), contradicting χ₂(7) = 5. Consequence: no colour class is contained in an affine hyperplane, so the natural ansatz "take a maximum sum-free set as one class" cannot even start.

Section 4The evidence about the answer, labelled as evidence

Everything in this section is Numerical. It is consistent with χ₂(8) = 6 and proves nothing.

Room to spare, and it does not help. For each of the five colour classes of the n = 7 witness above, the bar is the Hoffman ratio bound on how many of the 128 affine points that class could take, computed in your browser by an exact integer Walsh–Hadamard transform of the class indicator. The five bounds sum to about 260, against the 128 that must be covered, so capacity is roughly double the requirement. This is a bound on each class separately; the classes still cannot be made to partition the 128 points simultaneously. That is what "the obstruction is global, not local" means.

Controls. The published table χ₂(n) = 2, 3, 3, 4, 5, 5 for n = 2…7 was reproduced end to end by the same pipeline, with every witness re-verified from the definition and the line counts matching (2n−1)(2n−2)/6.

Section 5Caveats

Section 6Open threads

  1. Decide the unbroken [C,C] instance, which would remove the hand lemma from Theorem 1 entirely. Cube and conquer is the obvious tool; a plain run past three hours produced a 3.4 GB proof and no verdict.
  2. Decide the combined instance asking whether any witness has an order-5-symmetric hyperplane shadow. UNSAT there would be a certified structural exclusion strictly stronger than the sampled non-extensions. It also terminated undecided, at about 2.5 hours and 5.9 GB.
  3. Attack the involutions. The theorem's boundary is exactly where the group becomes a 2-group, and an order-2 exclusion would leave only the trivial stabiliser, which is a strong statement about any witness.
  4. χ₂(8) itself. The honest reading of Section 4 is that a witness, if it exists, is unstructured, which is precisely the regime where SAT is weakest and where a lower-bound argument would have to come from counting rather than search.