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
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.
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.
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.
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.
χ₂(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
order
verdict at n = 8, k = 5
how
certificate
3
no invariant colouring
Lemma B (Mersenne)
proof, all n and k
7
no invariant colouring
Lemma B (Mersenne)
proof, all n and k
31
no invariant colouring
Lemma B (Mersenne)
proof, all n and k
127
no invariant colouring
Lemma B (Mersenne)
proof, all n and k
17
UNSAT
orbit-contracted SAT, 75 vars
131-lemma DRUP, re-verified
Frobenius x ↦ x²
UNSAT
35 orbit cells
2,060-lemma DRUP, re-verified
5, class [C,I]
UNSAT
63 cells, colour-broken
166,270-lemma DRUP, re-verified
5, class [C,C]
UNSAT
51 cells, colour-broken
812 MB DRAT, drat-trim only
2-power orders
not 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.
Sampled witnesses do not extend. 1,000 proper 5-colourings of
PG(6,2) were sampled by randomized CDCL, giving 999 distinct fingerprints under
a class-size-and-line-type invariant, one fingerprint occurring twice. Not one
of them extends over a hyperplane split to a colouring of PG(7,2): each
non-extension is a solver-decided UNSAT on a 640-variable instance, with a
50-witness subsample DRUP-certified end to end, 50 of 50 verified. The
order-5-symmetric witness does not extend either. The sampling is solver-biased
and not uniform.
The obstruction is packing, not capacity. Each colour class must sit
independently in a Cayley graph on the 128 affine points. The eigenvalues of
those graphs are exact integers via the Walsh–Hadamard transform, and the
Hoffman ratio bound gives capacity sums of roughly 265 to 274 across the sampled
witnesses against the 128 points that need covering, with randomized greedy
already packing about 151 to 170. There is room by a factor of two, and the
simultaneous partition still fails.
Local search says nothing useful, loudly. With breakout clause
weighting, PG(6,2) witnesses arrive in about 5 × 10³ flips.
PG(7,2) produced none in roughly 5 × 10⁹ weighted flips across
two independently seeded engines. That count is an order-of-magnitude estimate
from the measured flip rate: the engines were retired early to free cores and
their exact counters were not flushed.
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
χ₂(8) remains open. Nothing here decides it.
The theorem stops at odd order. Frobenius powers σ², σ⁴ and every
involution class of GL(8,2) are not excluded. "2-group stabiliser" is the
exact statement, and it does not say the stabiliser is trivial.
The colour-WLOG lemma is a hand proof, not a certificate. Both
order-5 rows depend on it. The unbroken [C,I] instance was separately decided
UNSAT by kissat, which removes the proviso for that leg as a solver verdict, but
its 6.7 GB proof was too large to check or commit. The unbroken [C,C]
instance was terminated undecided after about 3 hours with its proof past
3.4 GB; it stays an open thread.
Two trust bases, named. The [C,I] DRUP proof is pure RUP and checks
under three independent checkers. The [C,C] proof carries RAT lemmas in binary
DRAT and is attested by drat-trim only, shipped as a hash plus a regeneration
command rather than as a file.
R(3;4) ≤ 62 and 162 ≤ R(3;5) ≤ 307
are secondary, quoted from the source paper's
§6.1 and not re-derived from Radziszowski's survey.
The prior-work check was one day deep. arXiv full text plus a
citation search on 2512.01760 found nothing on χ₂(8) as of 2026-09-01, but the
sum-free-partition literature over F₂n is old and broad. A referee
should specifically ask whether the order-17 and order-5 exclusions duplicate
something in the Schur-like or cap-set symmetric-search literature. We found
none, and we mark the search shallow.
One number on this page differs from the session note as first
written. The sampled-witness fingerprint count is 999 distinct out of 1,000,
not 1,000; the committed summary file says so, and the note, README, writeup and
daily log were corrected before this page went up.
Section 6Open threads
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.
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.
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.
χ₂(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.