Erdős Problem #130

Erdős Problem 130: a checked attempt

GPT_6_Astra_Ultra

25 September 2026

Statement and scope

Countable degree and finite cliques

Here is the classical finite-clique obstruction in algebraic form. Take three noncollinear clique points, translate the first to $0$, and denote the others by $u_1,u_2$. Set $d_i=|u_i|$, positive integers. For any further clique point $x$, put $r=|x|$ and $k_i=|x-u_i|-r$. Each $k_i$ is an integer in $[-d_i,d_i]$. Squaring the distance equalities gives \[ -2x\cdot u_i=2k_i r+k_i^2-|u_i|^2\qquad(i=1,2). \] Because $u_1,u_2$ are linearly independent, a fixed pair $(k_1,k_2)$ forces $x=v+wr$ for fixed vectors $v,w$. The equation $|x|^2=r^2$ is a polynomial of degree at most two in $r$. It cannot vanish identically: that would imply $v=0$, $|w|=1$, and $k_i^2=|u_i|^2$, while the linear equations give $w\cdot u_i=-k_i$. Equality in Cauchy--Schwarz would then force both $u_i$ parallel to $w$, a contradiction. Thus there are at most two possible points for each $(k_1,k_2)$, and the entire clique has size at most \[ 2(2d_1+1)(2d_2+1). \] The bound depends on the chosen distances and is not a uniform bound on clique size. Cliques with fewer than three points are already finite. This reconstructs the Anning--Erdős obstruction recorded on the source page without importing its proof.

An infinite disjoint union of four-cliques

Inductively place rigid copies of this configuration, avoiding all cross-copy integer distances and all mixed collinear triples and concyclic quadruples. The details of simultaneous avoidance matter. At a finite stage choose an orientation such that no difference between two new vertices is parallel to any difference between two old vertices; only finitely many orientations are excluded. Vary the translation $t\in\mathbb R^2$. Each mixed collinearity condition excludes a line in the translation plane. A concyclicity condition involving three old and one new vertex, or three new and one old vertex, excludes a circle. For two of each, write the old pair as $0,u$ and the new pair as $t,t+v$, absorbing fixed translations. The four-point circle determinant, up to sign, is \[ \det\begin{pmatrix} u_1&u_2&|u|^2\\ t_1&t_2&|t|^2\\ v_1&v_2&2t\cdot v+|v|^2 \end{pmatrix}. \] It is a nonzero polynomial: at $t=sv$ its quadratic coefficient is $\det(u,v)|v|^2\ne0$. Thus its zero set has empty interior. Coincident old and new vertices exclude finitely many translations. Finally, each forbidden integer distance from an old to a new vertex excludes one circle, giving only countably many further closed sets with empty interior. The Baire category theorem says these sets cannot fill the translation plane, or any prescribed nonempty open region in it. Choose an allowed translation and continue. At each stage all configurations of mixed triples and quadruples, including two-new/two-old ones, have been covered. The countable union has the required general position and its integer-distance graph is exactly a disjoint union of $K_4$'s, so $\chi=\omega=4$.

Remaining gap and provenance

Completion rate estimate: 25%.

1) FORMAL RESTATEMENT

Let $A\subset\mathbb{R}^2$ be an infinite set of points such that (i) no three points of $A$ are collinear, and (ii) no four points of $A$ are concyclic. Define a graph $G(A)$ with vertex set $A$ where two vertices are adjacent iff the Euclidean distance between them is an integer.

Questions: - How large can the chromatic number $\chi(G(A))$ be? - How large can the clique number $\omega(G(A))$ be? - In particular, can $\chi(G(A))$ be infinite?

The text also asks about an infinite complete graph in this metric setting, and notes (by Anning--Erdos 1945) that it is impossible.

2) QUICK LITERATURE/CONTEXT CHECK

(Restricted to statements explicitly present in 123-137.tex.) - Anning and Erdos $1945$ imply the graph cannot contain an infinite complete graph.

3) ATTACK PLAN

- Prove basic combinatorial/geometry constraints implied by "no four cocircular". - Deduce that an infinite clique cannot occur (using the Anning--Erdos statement from the problem file). - Give at least one explicit (existence) construction of an infinite $A$ with controlled $\chi$ and $\omega$ to show nontrivial lower bounds.

4) WORK

Lemma 4.1 (At most three neighbors at any fixed integer radius). Fix $p\in A$ and a positive integer $r$. Then there are at most 3 points $q\in A$ with $\|p-q\|=r$.

Proof. All points $q$ with $\|p-q\|=r$ lie on the circle of radius $r$ centered at $p$. If there were 4 such points, those 4 points of $A$ would be concyclic, contradicting the hypothesis that no four points of $A$ lie on a circle. $\square$

Lemma 4.2 (No infinite clique). The graph $G(A)$ contains no infinite clique.

Proof. An infinite clique in $G(A)$ is an infinite subset $K\subset A$ such that every pair of points in $K$ has integer distance. The problem text states (Anning--Erdos 1945) that an infinite set of points with all pairwise distances integers is impossible in this setting (in fact such a set must be collinear). Since $A$ has no three collinear points, it cannot contain such an infinite clique. Therefore $G(A)$ has no infinite clique. $\square$

Proposition 4.3 (Existence of an infinite example with $\chi=3$ and $\omega=3$). There exists an infinite set $A\subset\mathbb{R}^2$ satisfying the hypotheses (no three collinear, no four concyclic) such that $G(A)$ is a disjoint union of triangles (hence $\omega(G(A))=3$ and $\chi(G(A))=3$).

Proof (constructive existence by induction). We build $A$ as a disjoint union of equilateral triangles of side length 1, placed so that: - within each triangle, all three pairwise distances are 1 (integer), giving a $K_3$ component; - between distinct triangles, all inter-triangle distances are non-integers (so no extra edges); - no three points are collinear and no four concyclic.

Inductive step: Assume we have built a finite set $A_m$ which is a disjoint union of $m$ such triangles and satisfies all geometric conditions and the no-extra-integer-distance condition. We will place the next triangle far away.

Let $F$ be the union of the following forbidden sets for the location of the next triangle (we choose one vertex first and then the other two relative to it): - For each pair of points in $A_m$, the line through them (to avoid creating a collinear triple). - For each triple of points in $A_m$, the unique circle through them (to avoid creating a concyclic quadruple). - For each point $p\in A_m$ and each integer $r\ge 1$, the circle of radius $r$ centered at $p$ (to avoid creating a new integer distance from any new point to $p$).

For the first two bullets there are finitely many lines/circles; for the third bullet there are countably many circles. In all cases, each forbidden set is a 1-dimensional subset of the plane. Hence their union $F$ is a countable union of sets with empty interior, and therefore cannot cover all of $\mathbb{R}^2$. Choose a point $p_{m+1}\in \mathbb{R}^2\setminus F$. Now place an equilateral triangle of side 1 with one vertex at $p_{m+1}$ and with the other two vertices obtained by rotating the vector $(1,0)$ by an angle $\theta$ and translating, where $\theta$ is also chosen to avoid the finitely many bad orientations that would place a new vertex on a forbidden line/circle or on a forbidden integer-radius circle around existing points. Such a choice is possible because only finitely many orientations are excluded at this step. Let these two new vertices be $q_{m+1},r_{m+1}$. Set $A_{m+1}:=A_m\cup\{p_{m+1},q_{m+1},r_{m+1}\}$.

By construction: - the new triangle has integer edges (all 1); - no new point lies on a forbidden line/circle determined by previous points, so no new collinear triple or concyclic quadruple is formed; - no new point lies on any integer-radius circle around any old point, so there are no new integer distances between different triangles.

Thus the induction continues, producing an infinite set $A=\bigcup_m A_m$. The resulting graph $G(A)$ is a disjoint union of triangles, so $\omega(G(A))=3$ and $\chi(G(A))=3$. $\square$

5) VERIFICATION

- Lemma 4.1 is immediate from the "no four concyclic" hypothesis. - Lemma 4.2 uses the Anning--Erdos statement explicitly given in the problem file. - In Proposition 4.3, at each finite stage we avoid a countable union of circles/lines; such a union cannot cover the plane, so a choice exists. The construction guarantees the graph is exactly a disjoint union of triangles.

6) FINAL

UNRESOLVED

(i) Strongest fully proved partial result: - For any such $A$, each vertex has at most 3 neighbors at any fixed integer distance (Lemma 4.1). - No infinite clique can occur (Lemma 4.2). - There exist infinite examples with $\chi=3$ and $\omega=3$ (Proposition 4.3).

(ii) Exact first gap: - Determine whether $\chi(G(A))$ can be infinite (and more generally, characterize possible growth of $\chi$ and $\omega$ over all such $A$).

(iii) Top 3 next moves: 1. Try to embed known high-chromatic graphs as integer-distance graphs while maintaining the no-three-collinear/no-four-concyclic constraints. 2. Prove upper bounds on $\chi(G(A))$ from geometric constraints (e.g. degree growth restrictions implied by Lemma 4.1 plus incidence bounds). 3. Investigate whether forbidding 4 concyclic points forces bounded chromatic number for integer-distance graphs, perhaps via circle-packing type arguments.

(iv) What a minimal counterexample would likely look like: - An infinite configuration $A$ producing arbitrarily large finite subgraphs of $G(A)$ with large chromatic number but without large cliques (since infinite cliques are impossible), requiring very controlled integer-distance incidence across many different radii.