Erdős problem 706 — live audit, explicit lattice certificates, and an exact four-distance subcase

Date: 2026-07-27 UTC

Claim labels used below:

• (a) elementary-rigorous: proved here from the definitions.
• (b) rigorous-modulo-named-theorem: the deduction uses the named published theorem.
• (c) plausible/structural-unverified: a diagnosis or research direction, not a theorem.
• (d) computational-only: exhaustive finite computation, with the verifier stated.

0. Mandatory live-page gate

(d; direct browser observation.) I fetched the live problem page, its LaTeX view, and its discussion thread through the Bright Data browser path on 2026-07-27. I did not rely on the stale tracker metadata or on datacenter curl.

The live page displayed OPEN. Its statement, verbatim from the live LaTeX view, is:

> Let $L(r)$ be such that if $G$ is a graph formed by taking a finite set of points $P$ in $\mathbb{R}^2$ and some set $A\subset (0,\infty)$ of size $r$, where the vertex set is $P$ and there is an edge between two points if and only if their distance is a member of $A$, then $\chi(G)\leq L(r)$.

>

> Estimate $L(r)$. In particular, is it true that $L(r)\leq r^{O(1)}$?

The page's listed known result is, verbatim:

> The case $r=1$ is the Hadwiger-Nelson problem, for which it is known that $5\leq L(1)\leq 7$.

It also links problems 508, 704, and 705.

(d; direct browser observation.) The stop-condition fields were:

• 0 claimed proofs for this problem;
• Currently working on this problem: None;
• Interested in collaborating: None;
• I am working on formalising the results on this problem: None.

Thus neither mandatory stop condition was triggered.

(d; direct browser observation.) There is one comment, by Quanyu Tang at 17:12 on 3 May 2026. The site explicitly warns that comments are not verified. The comment:

1. defines the infinite-plane quantity

\(\overline\chi(\mathbb R^2;m)=\max_{|A|=m}\chi(\mathbb R^2,A)\);

2. invokes the de Bruijn--Erdős compactness theorem to identify it with the finite-subgraph formulation;

3. records

\[ \overline\chi(\mathbb R^2;m)\gg m\sqrt{\log m} \quad\text{and}\quad \overline\chi(\mathbb R^2;m)\leq 7^m; \]

4. records \(L(2)\geq6\), first for \(A=\{1,2\}\) via Exoo--Ismailescu, and mentions Parts's 16-vertex two-distance construction; and

5. cites de Bruijn--Erdős (1951), Naslund (2023), Exoo--Ismailescu (2019), Parts (2020/2023), and a MathOverflow answer by Naslund.

I checked the primary sources below rather than treating the comment as proof.

1. Exact formulation and elementary bounds

For finite \(A\subset(0,\infty)\), let \(G_A(\mathbb R^2)\) have vertex set \(\mathbb R^2\), with \(x\) and \(y\) adjacent exactly when \(\|x-y\|_2\in A\).

(b; de Bruijn--Erdős compactness.) The live finite quantity is exactly

Indeed, every finite subgraph of \(G_A(\mathbb R^2)\) is one of the graphs allowed on the live page. Conversely, if every finite subgraph is \(k\)-colourable, the de Bruijn--Erdős theorem makes the full graph \(k\)-colourable. Since the elementary upper bound below is finite, the relevant chromatic numbers are integers in a bounded set, so the suprema in (1) are attained as integer maxima.

(a; product colouring.) For \(A=\{a_1,\ldots,a_r\}\), rescale a seven-colouring of the unit-distance plane separately for each \(a_i\), obtaining colourings \(c_i:\mathbb R^2\to[7]\). Then

is a proper colouring for every distance in \(A\). Hence

(a; regular polygons.) A regular \((2r+1)\)-gon has exactly \(r\) pairwise chord lengths. Taking all of them as \(A\) makes its vertices a \(K_{2r+1}\), so

(b; Landau--Ramanujan/distinct-distance estimate.) An \(n\times n\) square grid has \(n^2\) points and \(O(n^2/\sqrt{\log n})\) distinct distances. Taking every realised distance makes the grid a clique and inverting the relation gives

This is the planar lower bound stated in Naslund's paper and in the live comment. It is much larger than (3) asymptotically, but still polynomial; the open side is the upper bound.

2. Primary-source literature audit

I searched the exact phrases “multiple forbidden distances,” “\(m\)-distance chromatic number,” and “colouring the plane with multiple forbidden distances,” including arXiv-oriented 2024--2026 searches. I then opened the primary papers for every retained claim.

• (b; source-verified.) Erdős's original paper, On the combinatorial problems which I would most like to see solved, Combinatorica 1 (1981), 25--42, defines the multiple-distance plane quantity on pp. 2--3 of the scan, asks whether it increases polynomially or exponentially, and states his expectation of a bound \(r^c\) for an absolute \(c\).
• (b; source-verified.) Eric Naslund, The chromatic number of \(\mathbb R^n\) with multiple forbidden distances, Mathematika 69 (2023), 692--718, DOI 10.1112/mtk.12197, records (4) for \(n=2\). Its main partition-rank theorem concerns growth in the dimension \(n\), not a polynomial upper bound in \(r\) for the fixed plane. Section 5 explicitly asks whether the exponential dependence on the number of distances can be reduced to polynomial, and separately asks whether the planar distinct-distance lower bound can be improved by any constant factor \(>1\).
• (b; source-verified.) Geoffrey Exoo and Dan Ismailescu, arXiv:1909.13177, prove that every five-colouring of the plane has a monochromatic pair at distance \(1\) or \(2\). Therefore \(L(2)\geq6\).
• (b; source-verified.) Jaan Parts, arXiv:2010.12656v2, gives a 16-vertex six-chromatic two-distance graph; the arXiv record gives the journal reference Geombinatorics 29/3 (2020), 111--115.
• (b; source-verified.) The cited de Bruijn--Erdős paper exists with the stated title and publication data: N. G. de Bruijn and P. Erdős, A colour problem for infinite graphs and a problem in the theory of relations, Proceedings of the Section of Sciences of the Koninklijke Nederlandse Akademie van Wetenschappen, Series A 54 (1951), 371--373.

(c; honest negative search.) I found no later primary source claiming a polynomial upper bound, a superpolynomial lower bound, or a resolution of the general planar question. Searches also found work on intervals of forbidden distances and on infinite sets such as the odd integers, but those do not settle the finite-\(r\) extremal function in (1). A negative literature search is not a theorem of absence; it is consistent with both the live status and Naslund's explicit open problem.

3. Explicit small-\(r\) clique certificates

Use the triangular lattice

For axial coordinates \(u=(i,j)\), put

Then the squared Euclidean distance between the points represented by \(u\) and \(v\) is exactly \(Q(u-v)\).

Let

It has 19 points, and its complete set of nonzero squared pairwise distances is

For \(D_r\) equal to the first \(r\) entries in (5), the standalone verifier exhaustively computes the following clique numbers inside \(H_2\):

| \(r\) | \(D_r\) | maximum clique in the \(H_2\) distance graph |

|---:|---|---:|

| 1 | \(1\) | 3 |

| 2 | \(1,3\) | 4 |

| 3 | \(1,3,4\) | 7 |

| 4 | \(1,3,4,7\) | 9 |

| 5 | \(1,3,4,7,9\) | 12 |

| 6 | \(1,3,4,7,9,12\) | 13 |

| 7 | \(1,3,4,7,9,12,13\) | 16 |

| 8 | \(1,3,4,7,9,12,13,16\) | 19 |

The maximality assertions in this finite host are (d). The displayed cliques themselves are finite certificates, so the resulting lower bounds are (a) once their coordinates are checked.

For example, for \(r=5\), the following 12 axial coordinates have every squared pairwise distance in \(\{1,3,4,7,9\}\):

For \(r=7\), the analogous 16-point certificate is

For \(r=8\), all of \(H_2\) is a 19-clique. Consequently,

The first two live-page small cases remain stronger than the first two rows: \(L(1)\geq5\) and \(L(2)\geq6\). The constructions in (6) are instances of the standard few-distances lattice mechanism behind (4), so I make no claim that the numerical inequalities are new to the literature.

4. New exact computation retained from this run

Consider the four actual distances

is their set of squares. Let \(T_*\) be the graph on all of \(\Lambda\) joining two lattice points exactly when their squared distance lies in \(D_*\).

4.1 A rigorous nine-colouring

(a) Colour \((i,j)\in\mathbb Z^2\) by

using nine colours. If two vertices receive the same colour, their coordinate difference is \((3a,3b)\), and

None of \(1,7,12,13\) is divisible by \(9\), so a same-colour pair cannot be adjacent. Therefore

4.2 Exact finite lower obstruction

For \(R\geq1\), put

The verifier reconstructs the \(D_*\)-distance graph on each patch using integer arithmetic and obtains:

| \(R\) | vertices | edges | clique number | chromatic number | graph SHA-256 |

|---:|---:|---:|---:|---:|---|

| 1 | 7 | 12 | 3 | 3 | cb20094a8d6d579a33de020ed9de83dc108aefb2943b0e25ed28e8e025b97720 |

| 2 | 19 | 99 | 6 | 6 | 4d20e32cff0feb5aac60b34e8a2063cb9ef3607b69339660867a698bb0227099 |

| 3 | 37 | 309 | 6 | 8 | 0e44e98d611c920b6a8a6a97b07ece75856de83ce4cb43ceef41403d153f82ad |

| 4 | 61 | 627 | 6 | 9 | 34e7890f95e585e3f1f01b8411b126f064c900a109a5a42a1d5c9dd20f47af65 |

(d; exhaustive.) The chromatic-number and clique-number columns are exact. In particular, the 61-point graph is not 8-colourable even though its largest clique has only six vertices.

There is a smaller symmetric witness. Delete from \(H_4\) its six points with \(Q(i,j)=16\), and call the remaining set \(P_*\). Then:

Its coordinate-and-edge digest is

f2ca16cdb8ce0f11220b8945c313ef1cb8ddb2db1cfe5c89ee1b05293b6afd5f.

The nine-colour upper certificate is the residue colouring from (7). The eight-colour lower test exhaustively visited 45,809 search nodes in the fresh verifier run.

Combining (7) and (8) gives the exact concrete regime

This also proves \(\chi(G_{A_*}(\mathbb R^2))\geq9\), hence \(L(4)\geq9\). It does not prove that the full plane graph \(G_{A_*}(\mathbb R^2)\) is nine-colourable: (7) colours only the lattice. Numerically, \(L(4)\geq9\) was already supplied by a regular nonagon. The added information in (8) is that the same lower bound occurs in an exact lattice subproblem with clique number only six.

5. Standalone re-verification

Run:

python runs/erdos706_wave6k_verify.py

The script uses only the Python standard library and no saved graph, colouring, SAT output, or third-party solver. It:

1. regenerates every coordinate set;

2. reconstructs every edge from \(Q(u-v)\) using exact integers;

3. verifies all 36 displacement vectors realising \(D_*\);

4. computes maximum cliques with a from-scratch bit-set Bron--Kerbosch search;

5. verifies the explicit residue colourings;

6. proves non-\(k\)-colourability with an exact DSATUR-style backtracker; and

7. recomputes the prefix-distance clique table and every quoted digest.

The colouring backtracker is exhaustive for the following reason. It first fixes distinct colour names on a verified clique, which is harmless up to a permutation of colours. At every later node it chooses an uncoloured vertex and branches over every colour not already used by a coloured neighbour. Unused colour names are introduced in order, removing only colour-permutation symmetry. A branch is rejected only when some uncoloured vertex sees all \(k\) colours. Thus a completed search returning false is a finite proof that no \(k\)-colouring exists.

The retained checker was written after exploratory OR-Tools/PySAT searches and does not call either system. This gives an independent implementation of the final arithmetic and colouring claims.

(d) A fresh normal-mode run completed with PASS in about 2.7 seconds. The two substantive unsatisfiable searches used 43,376 nodes for the full \(H_4\) graph and 45,809 nodes for the reduced 55-vertex witness.

6. Exact wall for the general question

The computations above concern lower bounds and structured lattice subgraphs. They do not address the uniform upper bound for arbitrary real distance sets.

(a; black-box barrier.) The product proof (2) cannot be compressed merely by post-processing its \(r\) independent seven-colour coordinates. If a map

is required to distinguish every two coordinate vectors whenever they differ in any coordinate, then \(F\) must be injective: every two distinct vectors differ somewhere. Hence \(q\geq7^r\). Geometry might make many tuple pairs unattainable, but the separate one-distance colourings supply no theorem controlling that attainability.

(c; precise missing input.) A polynomial solution needs a genuinely simultaneous geometric colouring/correlation lemma: for every arbitrary collection of \(r\) radii, construct one partition of the plane into \(r^{O(1)}\) sets, each avoiding all \(r\) radii. Neither the one-distance seven-colour theorem, the product construction, nor the few-distances lattice lower-bound machinery provides such a correlation across unrelated scales. Assuming such a lemma is simply assuming the open part of the problem.

(c) Finite lattice searches can improve individual lower bounds, but cannot certify a polynomial upper bound: \(P\) is unbounded and the radii are arbitrary reals. For scale, a complete four-shell search on a radius-six triangular patch already has 46 candidate norm shells and

distance sets. At an observed exact-colouring cost ranging from roughly \(0.05\) seconds for easy instances to \(10\) seconds for hard tails, a certificate-producing sweep would cost about \(2\) to \(450\) core-hours. Even a successful sweep would prove only another finite-patch lower statement, not the uniformity required by the live question, so I did not run it.

PARTIAL: The polynomial upper bound remains open; this run gives explicit checked clique certificates including \(L(5)\ge12,L(7)\ge16,L(8)\ge19\), and proves by a standalone exhaustive checker that the triangular-lattice graph with squared forbidden distances \(\{1,7,12,13\}\) has chromatic number exactly \(9\), witnessed by a 55-vertex clique-number-six obstruction.