Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Claim. Let GnG_n be the unit distance graph of Rn\mathbb R^n; the paper writes χ(Rd)\chi(\mathbb R^d) for χ(Gd)\chi(G_d). James Davies, Measurable obstructions for unmeasurable colourings, arXiv:2610.12301v1, posted 2026-10-08 (47 pages, the only version), proves

(2+o(1))n≤χ(Gn)≤(332+o(1))n,(2+o(1))^n\le\chi(G_n)\le\Bigl(\frac{3\sqrt3}{2}+o(1)\Bigr)^n,

the lower bound as Theorem 1.4 and the upper bound as Theorem 1.5 (both p. 4, combined in the display after Theorem 1.5), with 33/2=2.598…3\sqrt3/2=2.598\ldots. This answers yes the second question of Problem 704. The abstract prints the upper base as 33/43\sqrt3/4. That is a misprint: Theorem 1.5, the sentence before it, which gives the value 2.5981…2.5981\ldots, and the last line of its proof (p. 37) all have 33/23\sqrt3/2, and 33/4=1.299…3\sqrt3/4=1.299\ldots would lie below the lower base 22.

The lower bound is first proved for measurable colorings. Theorem 8.1 (p. 30) bounds the density of a measurable set avoiding distance 11 through any normalized combination HH of radial derivatives of the spherical average of e2πix⋅ωe^{2\pi i x\cdot\omega} with H≥−BH\ge-B, since the autocorrelation of such a set vanishes on an annulus around the unit sphere; this gives χ(m)(Rd)≥1+1/B\chi^{(m)}(\mathbb R^d)\ge1+1/B. Section 8 multiplies the average, a Bessel function Jd/2−1J_{d/2-1} up to normalization, by a polynomial that cancels its sign changes up to 2ν2\nu, ν=d/2−1\nu=d/2-1, and stays uniformly small beyond (Lemmas 8.2 and 8.3), which gives B=2−d+o(d)B=2^{-d+o(d)}. The paper's main theorem, Theorem 1.1 (p. 3), states that χ(Rd)\chi(\mathbb R^d) equals the measurable chromatic number χ(m)(Rd)\chi^{(m)}(\mathbb R^d) for every d≥4d\ge4, and so carries the bound to all colorings. Its proof (Sections 2–7 and Appendices A and B) transfers finite certificates of the measurable problem, in the completely positive framework of DeCorte, de Oliveira Filho and Vallentin, to lattice Cayley graphs. The upper bound (Section 10, pp. 35–37) is a random construction. Balls of radius about 1/21/2 around random periodic centers, trimmed by half-spaces so that the pieces avoid every distance in [1−ε,1+ε][1-\varepsilon,1+\varepsilon] with ε=d−1/2\varepsilon=d^{-1/2}, contain each point with probability at least pp, where 1/p≤(33/2+o(1))d1/p\le(3\sqrt3/2+o(1))^d. The base comes from the maximum 33/43\sqrt3/4 of (1+t)1−t2(1+t)\sqrt{1-t^2}, which bounds the radius of a cylinder holding the forbidden centers. O(dlog⁡d)/pO(d\log d)/p independent copies cover a fine grid, and their ε/3\varepsilon/3-neighborhoods give a proper Borel coloring. The paper's statement of AI use says that ChatGPT found the initial proof of Theorem 1.5, improved the lower-bound arguments of Sections 8 and 9, and gave initial proofs of parts of Theorem 1.1. Read depth: the statements of Theorems 1.1, 1.4 and 1.5 and the proofs of Theorems 1.4 and 1.5 (Sections 8 and 10), read through but not checked step by step; the proof of Theorem 1.1 was not read.

Covers. The exponential-growth question: χ(Gn)\chi(G_n) grows at least exponentially, with base 22; the accepted claims of Frankl and Wilson and Raigorodskii already settle it. For the estimate, both bases are new against the bounds the problem page records, Raigorodskii's lower base 1.239…1.239\ldots and the Larman–Rogers upper base 33, which the paper names as the previous bounds (p. 2). If the limit of χ(Gn)1/n\chi(G_n)^{1/n} exists, the two bounds confine it to [2,2.598…][2,2.598\ldots]. The upper bound contradicts the guess of Larman and Rogers, recorded in the erdosproblems.com remarks, that the truth may be (23/2+o(1))n(2^{3/2}+o(1))^n: (33/2)2=27/4<8=(23/2)2(3\sqrt3/2)^2=27/4<8=(2^{3/2})^2, so Theorem 1.5 gives lim sup⁡χ(Gn)1/n≤2.598…<2.828…\limsup\chi(G_n)^{1/n}\le2.598\ldots<2.828\ldots. The paper does not mention that guess; it conjectures instead that one of its two bases is tight, without saying which. Not covered: the estimate, since the two bases differ, and the existence of the limit, which the paper does not address.

Depends on. No page of this wiki. The lower bound rests on the paper's own Theorem 1.1, whose proof uses the completely positive characterization of measurable independence density of DeCorte, de Oliveira Filho and Vallentin, with a gap in its finite-point converse filled in Appendix A, and a lattice-point estimate of Magyar for its Theorem 4.1. The upper bound is self-contained.

Standing. Claimed: an arXiv preprint with no refereed version, Lean proof or outside review known to this corpus. It appeared after erdosproblems.com froze proof claims on 6 October 2026, so no proof claim on erdosproblems.com records it; Bloom's catalog labeled the problem OPEN.