Borel Polychromatic Number of Grids

Edward Hou; Katalin Berlow

REVIEW 3 major objections 5 minor 13 references

Borel Polychromatic Number of Grids

T0 review · 3 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The Borel polychromatic number of a free Z^d grid is exactly 2^d − 1: every such grid admits a Borel coloring using all colors on every unit cube, and one more is impossible for ergodic actions.

desk verdict New upper bound and a nice local lemma, but the advertised sharpness is false: ergodic generators do not block Borel 2^d-colorings, and a concrete product action gives a counterexample. read the letter →

arxiv 2508.18559 v1 pith:JAI25NL4 submitted 2025-08-25 math.LO math.CO

Katalin Berlow , Edward Hou This is my paper · ORCID

classification math.LOmath.CO MSC 03E1505C1537A20

keywords BorelpolychromaticcoloringgridgraphscombinatoricsZ^dactionstoastdecompositionergodicnumberdescriptivesettheory

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper asks how many colors a Borel labeling of a grid graph can use while still guaranteeing that every unit $d$-dimensional cube sees every color at least once, and it answers the question for grids coming from free Borel actions of $\mathbb{Z}^d$. In the classical setting every $\mathbb{Z}^d$ grid admits a polychromatic coloring with all $2^d$ colors available on its $2^d$ vertices; the paper shows that imposing Borelness costs exactly one color. The main theorem constructs a Borel $(2^d-1)$-polychromatic coloring for every free Borel $\mathbb{Z}^d$ action, and the sharpness theorem shows that when the generators act ergodically no Borel $2^d$-polychromatic coloring exists. The upshot is that the Borel polychromatic number of a free ergodic $\mathbb{Z}^d$ grid is exactly $2^d-1$.

What carries the argument

The construction runs on a Borel $r$-toast: a Borel collection of finite nested pieces of the grid such that any two pieces are either $r$-apart or one is contained in the $r$-thickening of the other. Each toast piece's exterior is colored by a repetitive template, a coloring that factors through the quotient $(\mathbb{Z}/2\mathbb{Z})^d$ and therefore carries all $2^d-1$ colors on every cube, and the paper interpolates between the inner template of a piece and the outer template through shells around each internal piece. The interpolation step rests on Lemma 3.1, which states that any two surjective labelings of the $d$-cube with $2^d-1$ colors can be connected by a sequence of surjective labelings in which consecutive labelings differ on at most one vertex; the shells are spaced so that every unit cube meets at most two consecutive steps of such a sequence. The toast radius $r=(2^{d+3}+1)d$ is chosen large enough that the shells of distinct pieces never interfere, so the local interpolations assemble into a single Borel coloring of the whole grid.

What would settle it

Exhibit a free Borel action of $\mathbb{Z}^d$ whose grid graph has no Borel $(2^d-1)$-polychromatic coloring, or exhibit a Borel $2^d$-polychromatic coloring of an ergodic action such as the Bernoulli shift; either outcome would contradict the claimed sharp value $2^d-1$.

Watch

Extended reading notes

Core claim

The central claim, Theorem 3.3, is that for every free Borel action of $\mathbb{Z}^d$ on a standard Borel space, the induced Schreier grid graph carries a Borel polychromatic coloring with $2^d-1$ colors: a Borel labeling with that many colors in which every unit hypercube $\{0,1\}^d\cdot x$ contains all colors. The bound is sharp: if the generators act ergodically, in particular for the Bernoulli shift, no Borel $2^d$-polychromatic coloring exists, so the Borel polychromatic number of a free ergodic $\mathbb{Z}^d$-grid is exactly $2^d-1$. The paper also shows that any Borel $2^d$-polychromatic coloring forces a Borel proper 2-coloring of each coordinate $\mathbb{Z}$-subaction, and it characterizes the $d=2$ case completely: a Borel 4-polychromatic coloring exists exactly when the action admits a '1-fold invariant' pair of Borel 2-colorings, and every 4-coloring is invariant under $e_0^2$ or $e_1^2$ on each orbit.

Load-bearing premise

The construction of the $(2^d-1)$-coloring rests on the imported lemma that every Borel graph induced by a Borel action of $\mathbb{Z}^d$ admits a Borel $r$-toast with nesting radius as large as $(2^{d+3}+1)d$; if such large-radius toasts failed to exist for some action, the claimed coloring would not follow from the given proof.

Editorial extensions

If this is right

The Borel polychromatic number of a free ergodic $\mathbb{Z}^d$ grid is exactly $2^d-1$, one less than the classical value.
Any Borel $2^d$-polychromatic coloring yields a Borel proper 2-coloring of each coordinate $\mathbb{Z}$-subaction, so actions with a non-2-colorable generator, such as irrational rotations of the circle, admit no such coloring.
For $d=2$, Borel 4-polychromatic colorings exist exactly when the action admits a 1-fold invariant pair of Borel 2-colorings, giving a complete structural picture in two dimensions.
The sharpness mechanism is rigidity: a Borel $2^d$-coloring forces a type of invariance along at least one generator, which ergodic actions cannot support.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The same toast-and-shell recipe suggests a general pattern for other translation-invariant shapes $T$: when a tile admits a surjective labeling with $|T|-1$ colors and a homotopy lemma like Lemma 3.1, the Borel polychromatic number may fall to $|T|-1$ under ergodicity, a concrete route into the paper's Open Question 5.2.
The paper's dichotomy between 0-fold and $(d-1)$-fold invariant tuples raises the testable conjecture that for $d\ge 3$ any Borel $2^d$-coloring forces orthogonally invariant 2-colorings in all but at most one direction; a finite periodic-grid search could look for a 0-fold-invariant tuple that still yields a $2^d$-coloring, which would refute the conjecture.
Because Lemma 4.1 pins the obstruction at a single generator, the sharpness threshold may extend beyond globally ergodic actions: any action whose coordinate subactions all admit Borel 2-colorings is the natural candidate class in which the existence of a Borel $2^d$-coloring should be re-examined.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Short version: the upper-bound half of this paper is a real contribution, but the sharpness theorem as stated is false. The abstract's claim that ergodic generators prevent Borel 2^d-polychromatic colorings is refuted by a concrete free action.

The Borel polychromatic number is a sensible new notion for grid actions, and the proof of the (2^d-1)-coloring uses toast technology in a genuinely new way. Lemma 3.1, the local path of surjective labelings, is neat and likely reusable. The d=2 rigidity analysis in Theorem 4.5(2) is also a nice structural result.

The construction in Theorem 3.3 is compressed in the spots you'd expect—the Borel recursion over the toast and the claim that each cube lies in one exterior or gap region—but those look like minor presentational gaps, not actual holes.

The real problem is Section 4 and the abstract. Lemma 4.1 is fine: a Borel 2^d-polychromatic coloring forces a Borel proper 2-coloring of each generator's subaction. But ergodicity of a generator does not imply absence of such a 2-coloring. Here is the counterexample. Let Y={0,1}^{Z^d} with the Bernoulli shift in each coordinate, and let X=Y x (Z/2)^d with e_i(y,eps)=(T_i y, eps+delta_i). The action is free. Each e_i is ergodic: an invariant set A decomposes as A_eps, and the invariance gives A_eps = T_i^{-1}(A_{eps+delta_i}), so each A_eps is T_i^2-invariant; since T_i^2 is ergodic, each A_eps has measure 0 or 1, and the coupling forces all of them to have the same measure. Yet c(y,eps)=eps is a Borel 2^d-polychromatic coloring: on any unit cube, the second coordinate runs through all 2^d values. So the universal 'exactly 2^d-1' claim is wrong. What the paper actually proves is a correct but weaker dichotomy: if some coordinate subaction has no Borel proper 2-coloring, then there is no Borel 2^d-polychromatic coloring. There exist free actions, like the one above, that do admit Borel 2^d-colorings.

Net: the upper bound and the new definition are worth a referee's time. The authors need to correct the sharpness statement, and the open questions in Section 5 should be revised to ask which actions admit 2^d-colorings rather than implying none with ergodic generators do. I would send it to review, with the expectation of major revision.

Who is it for? People in Borel combinatorics working on hyperfinite graphs and definable colorings. The construction technique will be cited, but as it stands I wouldn't cite the sharpness claim.

Referee Report

3 major / 5 minor

Summary. The paper studies Borel polychromatic colorings of the Schreier graph of a free Borel action of Z^d, where every unit d-cube must contain all colors. The positive result, Theorem 3.3, asserts that every such grid admits a Borel (2^d-1)-polychromatic coloring, constructed from a Borel toast decomposition and a local interpolation lemma. The paper further claims sharpness: it asserts in the abstract and in Section 5 that the Borel polychromatic number of every free Z^d-action is exactly 2^d-1, and in particular that no Borel 2^d-coloring exists when the generators act ergodically. Section 4 gives a more limited obstruction, Lemma 4.1, showing that absence of a Borel proper 2-coloring of some generator's Z-subaction implies absence of a Borel 2^d-polychromatic coloring, and it analyzes the d=2 case in Theorem 4.5.

Significance. If the positive existence statement is correct, it is a genuinely interesting contribution to Borel combinatorics: it shows that a local polychromatic constraint can be met with 2^d-1 colors in a Borel way for every free Z^d-action, using the highly nonconstructive toast machinery in a clever way. The local interpolation lemma is elegant and potentially reusable. The paper also correctly identifies a rigidity phenomenon for 2^d-colorings, namely that they force Borel 2-colorings of the coordinate subactions. However, the advertised sharpness theorem is false as stated, and this reduces the significance of the paper unless the claims are corrected. The positive theorem remains valuable even after the sharpness overclaim is removed.

major comments (3)

[Abstract and Section 5] The claimed sharpness is false. Consider the action e_i(y,epsilon) = (T_i y, epsilon + delta_i) on X = {0,1}^{Z^d} x (Z/2)^d, where T_i is the Bernoulli shift and delta_i is the i-th standard basis vector. This action is not free on all of X, but its free part F is a conull invariant Borel subset, so the restricted action is free and each generator is ergodic on F. The map c(y,epsilon)=epsilon is a Borel 2^d-polychromatic coloring on F, because every unit cube {a.x : a in {0,1}^d} has second coordinate ranging over all of (Z/2)^d. Thus ergodicity of the generators does not prevent a Borel 2^d-coloring. Section 4 only proves the obstruction under the strictly stronger hypothesis of Lemma 4.1, namely that some generator's Z-subaction has no Borel proper 2-coloring; the abstract and Section 5 must replace the universal 'exactly 2^d-1' statement with this conditional statement and should discuss the counterexample.
[Theorem 3.3, choice of r] The proof invokes Lemma 2.2 to take a Borel r-toast with r = (2^{d+3}+1)d, but Lemma 2.2 as stated merely says that 'a toast decomposition' exists and does not specify a radius. The existence of toasts with sufficiently large radius is load-bearing for the whole construction. Please cite the precise quantitative statement from [6] or include a proof that free Z^d-actions admit Borel r-toasts for this value of r.
[Theorem 3.3, induction verification] The verification step is incomplete. The text asserts that every unit cube C contained in K is contained either in E_K or in S_{i,t} union S_{i,t+1}, but this omits cubes contained entirely in an internal piece L_i and cubes crossing from L_i into P_i. Also, a cube straddling two shells does not literally have c restricted to C equal to one of the two adjacent templates; the mixed assignment can be surjective because consecutive templates differ at at most one vertex, but this needs to be stated and proved. The intended argument appears repairable, but the proof as written does not cover all cases.

minor comments (5)

[Lemma 3.1] The index arithmetic in Lemma 3.1 is unclear: the sequence appears to have 2^{d+1}+1 labelings, not '2d+1', and the bounds on i in the induction should be made explicit (i runs from 0 to 2^d-1, with final labeling c_{2^{d+1}}).
[Theorem 3.3, Step B] The notation [K]_G is used without definition; please define it as the G-connected component of K.
[Theorem 3.3, Step B] The sentence 'The choice r = 2R + d ensures...' is asserted without derivation; a short argument that the R-thickenings of distinct maximal internal pieces are separated by more than d would improve readability.
[Definition 3.2] The phrase 'factor through to a quotient Z_2^d of Z^d' should specify that the quotient is by (2Z)^d; this is implicit but could be stated explicitly.
[End of Section 3] The claim that every unit cube of G is contained in some toast piece needs a brief proof; it follows from r > d and the nesting property of toasts, but the manuscript should spell this out.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the construction relies on an external toast theorem and an in-paper combinatorial lemma, while the sharpness argument reduces a hypothetical 2^d-coloring to coordinate 2-colorings without fitting or self-citation loops.

full rationale

I walked the derivation chain of Theorems 3.3, 4.5, and Lemma 4.1. The existence proof is self-contained relative to an external, non-overlapping citation: the Borel r-toast for free Z^d-actions comes from Gao--Jackson--Krohne--Seward [6], cited as Lemma 2.2, and the local sliding lemma (Lemma 3.1) is proved in-paper. No parameter is fitted to the target quantity: the induction over the toast explicitly preserves polychromaticity on every unit cube, and Borel definability is obtained from the Borel well-founded order on toast pieces. The sharpness side is not circular either: Lemma 4.1 proves the contrapositive by converting a hypothetical Borel 2^d-polychromatic coloring into Borel proper 2-colorings of the coordinate Z-subactions, and the d=2 rigidity argument in Theorem 4.5 is an in-paper combinatorial contradiction. References to the authors' own work, e.g. [2], are background citations and are not load-bearing for the main results. I found no step where an output equals an input by definition, no renamed known result, no fitted input disguised as a prediction, and no self-citation chain forcing the conclusion. One non-circular correctness caveat is worth flagging: the abstract's sharpness assertion says ergodic generators suffice, while the proved obstruction in Lemma 4.1 requires the stronger hypothesis that some generator's Z-subaction has no Borel proper 2-coloring; ergodicity alone does not imply that failure, so the sharpness claim may be overbroad, but that is an evidential gap rather than a circularity.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

No free parameters and no invented entities. The only external inputs are a large-radius Borel toast theorem and standard ergodic obstructions to Borel 2-colorings.

assumptions (3)

domain assumption Lemma 2.2 from [6]: every Borel graph induced by a Borel action of Z^d admits a Borel r-toast.
Quoted in Section 2 and used in Theorem 3.3 as the decomposition on which the inductive coloring is built. The paper does not prove this theorem.
domain assumption A measure-preserving ergodic Z-action admits no Borel proper 2-coloring.
Used in Section 4 to convert the absence of a Borel 2-coloring of a coordinate subaction into the absence of a Borel 2^d-polychromatic coloring. This is standard in descriptive set theory, but it is an external input.
standard math Borel transfinite recursion is valid over the well-founded inclusion order on a Borel toast.
Used in Theorem 3.3 to assemble the piecewise colorings into a single Borel function. Standard, but not spelled out in the paper.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Borel Polychromatic Number of Grids." pith.science (2026). https://pith.science/paper/JAI25NL4

@misc{pith2026250818559,
  author       = {Pith},
  title        = {Pith review of: Borel Polychromatic Number of Grids},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JAI25NL4}},
  note         = {Machine review of arXiv:2508.18559}
}

abstract

We study Borel polychromatic colorings of grid graphs arising from free Borel actions of $\mathbb{Z}^d$. A polychromatic coloring is one in which every unit $d$-dimensional cube sees all available colors. In the classical setting, every grid admits a $2^d$-polychromatic coloring, while in the Borel setting this fails. Our main result shows that every free $\mathbb{Z}^d$-action admits a Borel $(2^d-1)$-polychromatic coloring. This result is sharp: any action where the generators act ergodically does not admit a Borel $2^d$-polychromatic coloring. We conclude with open directions for extending the theory beyond cube tilings and for exploring the dependence of Borel polychromatic numbers on the underlying action.

Figures

Figures reproduced from arXiv: 2508.18559 by the authors.

**Figure 2.** An orthogonally invariant proper 2-coloring for the vertical [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗

**Figure 3.** An illustration of the proof of Theorem 4.5. [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

13 extracted references · 11 canonical work pages

[6]

Borel combinatorics of abelian group actions, 2024

Su Gao, Steve Jackson, Edward Krohne, and Brandon Seward. Borel combinatorics of abelian group actions, 2024. arXiv 2401.13866

arXiv 2024
[1]

Polychromatic colorings of plane graphs

Noga Alon, Robert Berke, Kevin Buchin, Maike Buchin, P´ eter Csorba, Saswata Shannigrahi Shannigrahi, Bettina Speckmann, and Philipp Zumstein. Polychromatic colorings of plane graphs. In Proceedings of the Twenty-Fourth Annual Symposium on Computational Geometry, SCG ’08, page 338–345, New York, NY, USA, 2008. Association for Computing Machinery

work page 2008
[2]

Separating complexity classes of LCL problems on grids

Katalin Berlow, Anton Bernshteyn, Clark Lyons, and Felix Weilacher. Separating complexity classes of lcl problems on grids, 2025. arXiv 2501.17445

work page Pith review arXiv 2025
[3]

Distributed algorithms, the lov´ asz local lemma, and descriptive combina- torics

Anton Bernshteyn. Distributed algorithms, the lov´ asz local lemma, and descriptive combina- torics. Inventiones mathematicae, 233(2):495–542, 2023

work page 2023
[4]

Polychromatic Colorings of Unions of Geometric Hypergraphs

Vera Chekan and Torsten Ueckerdt. Polychromatic colorings of unions of geometric hyper- graphs, 2021. arXiv 2112.02894

work page Pith review arXiv 2021
[5]

Conley, Steve C

Clinton T. Conley, Steve C. Jackson, Andrew S. Marks, Brandon M. Seward, and Robin D. Tucker-Drob. Borel asymptotic dimension and hyperfinite equivalence relations. Duke Mathe- matical Journal, 172(16):3175 – 3226, 2023. 12

work page 2023
[7]

Group colorings and bernoulli subflows

Su Gao, Steve Jackson, and Brandon Seward. Group colorings and bernoulli subflows. Memoirs of the American Mathematical Society , 241, 01 2012

work page 2012
[8]

From descriptive to distributed, 2025

Jan Greb´ ık and Zolt´ an Vidny´ anszky. From descriptive to distributed, 2025. arXiv 2502.15347

arXiv 2025

Show all 13 references

[9]

Descriptive graph combinatorics

Alexander S Kechris and Andrew S Marks. Descriptive graph combinatorics. preprint, 2020

2020
[10]

Topics in orbit equivalence

Alexander S Kechris and Benjamin D Miller. Topics in orbit equivalence . Number 1852. Springer Science & Business Media, 2004

2004
[11]

Borel chromatic numbers

AS Kechris, S Solecki, and S Todorcevic. Borel chromatic numbers. Advances in Mathematics, 141(1):1–44, 1999

1999
[12]

Marks and Spencer T

Andrew S. Marks and Spencer T. Unger. Borel circle squaring. Annals of Mathematics, 186(2), September 2017

2017
[13]

Polychromatic Coloring for Half-Planes , page 118–126

Shakhar Smorodinsky and Yelena Yuditsky. Polychromatic Coloring for Half-Planes , page 118–126. Springer Berlin Heidelberg, 2010. 13

2010

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.

[1] [6]

Borel combinatorics of abelian group actions, 2024

Su Gao, Steve Jackson, Edward Krohne, and Brandon Seward. Borel combinatorics of abelian group actions, 2024. arXiv 2401.13866

arXiv 2024

[2] [1]

Polychromatic colorings of plane graphs

Noga Alon, Robert Berke, Kevin Buchin, Maike Buchin, P´ eter Csorba, Saswata Shannigrahi Shannigrahi, Bettina Speckmann, and Philipp Zumstein. Polychromatic colorings of plane graphs. In Proceedings of the Twenty-Fourth Annual Symposium on Computational Geometry, SCG ’08, page 338–345, New York, NY, USA, 2008. Association for Computing Machinery

work page 2008

[3] [2]

Separating complexity classes of LCL problems on grids

Katalin Berlow, Anton Bernshteyn, Clark Lyons, and Felix Weilacher. Separating complexity classes of lcl problems on grids, 2025. arXiv 2501.17445

work page Pith review arXiv 2025

[4] [3]

Distributed algorithms, the lov´ asz local lemma, and descriptive combina- torics

Anton Bernshteyn. Distributed algorithms, the lov´ asz local lemma, and descriptive combina- torics. Inventiones mathematicae, 233(2):495–542, 2023

work page 2023

[5] [4]

Polychromatic Colorings of Unions of Geometric Hypergraphs

Vera Chekan and Torsten Ueckerdt. Polychromatic colorings of unions of geometric hyper- graphs, 2021. arXiv 2112.02894

work page Pith review arXiv 2021

[6] [5]

Conley, Steve C

Clinton T. Conley, Steve C. Jackson, Andrew S. Marks, Brandon M. Seward, and Robin D. Tucker-Drob. Borel asymptotic dimension and hyperfinite equivalence relations. Duke Mathe- matical Journal, 172(16):3175 – 3226, 2023. 12

work page 2023

[7] [7]

Group colorings and bernoulli subflows

Su Gao, Steve Jackson, and Brandon Seward. Group colorings and bernoulli subflows. Memoirs of the American Mathematical Society , 241, 01 2012

work page 2012

[8] [8]

From descriptive to distributed, 2025

Jan Greb´ ık and Zolt´ an Vidny´ anszky. From descriptive to distributed, 2025. arXiv 2502.15347

arXiv 2025