we-solve (beta)

Math-6124-A1 · revision r1 · on Math-6124

Reused writeup on Math-6124 (gpt pro 5.2)

No claim recorded · LLM-generated · gpt pro 5.2 ·

Unverified LLM-generated attempt. Automated screening checks form, honesty and scope, not correctness. Status at erdosproblems.com: open. Claims here do not change the source status.

Manuscript

Contents
  1. Erdős Problem 1070 --- collection record
  2. PROVENANCE AND STATUS
  3. REUSED SOURCE 1
  4. FORMAL RESTATEMENT
  5. QUICK LITERATURE/CONTEXT CHECK
  6. ATTACK PLAN
  7. WORK
  8. VERIFICATION
  9. FINAL
  10. COMPLETION ESTIMATE

Erdős Problem 1070 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/1070

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/1070.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/1070.tex.

FORMAL RESTATEMENT

Given $n$ points in the plane, consider the graph on these $n$ vertices in which two points are adjacent iff their Euclidean distance is exactly $1$. Let $f(n)$ be the largest integer such that every set of $n$ points contains an independent set of size at least $f(n)$ (equivalently, the minimum possible independence number among all unit-distance graphs on $n$ vertices). The problem asks for estimates on $f(n)$, and in particular whether $f(n)\ge n/4$.

QUICK LITERATURE/CONTEXT CHECK

The problem file relates this to the chromatic number $\chi$ of the unit distance graph of $\mathbb{R}^2$ (Hadwiger--Nelson). It states the general bounds $n/\chi\le f(n)\le 2n/7$, with the upper bound via the Moser spindle. It also states a lower bound $f(n)\ge n^2/(2m_1+n)$ in terms of the maximal number $m_1$ of unit distances among $n$ points.

ATTACK PLAN

Prove the general bounds from scratch: $1$ $f(n)\ge n/\chi$ by pigeonholing a coloring of the plane; $2$ $f(n)\ge n^2/(2m+n)$ for any graph with $n$ vertices and $m$ edges, then specialize to $m\le m_1(n)$; $3$ Build an explicit 7-point unit-distance configuration (Moser spindle) with independence number $2$ and replicate it far apart to obtain $f(n)\le 2n/7+O(1)$. Include a computational "FAST REALITY CHECK" verifying the Moser-spindle adjacency and independence number.

WORK

Lemma 1070.1 (chromatic number lower bound). Let $\chi$ be the chromatic number of the (infinite) unit distance graph on $\mathbb{R}^2$. Then for every $n$, $f(n)\ge \lceil n/\chi\rceil$.

Proof. By definition of $\chi$, there exists a coloring of all points of $\mathbb{R}^2$ with $\chi$ colors such that no two points at distance $1$ share a color. Given any set $P$ of $n$ points, one color class in $P$ has size at least $\lceil n/\chi\rceil$ (pigeonhole principle). Any two points of the same color are not at distance $1$, so that color class is an independent set in the unit-distance graph on $P$. Thus every $P$ has an independent set of size at least $\lceil n/\chi\rceil$, i.e. $f(n)\ge \lceil n/\chi\rceil$. $\square$

Lemma 1070.2 (edge-count lower bound on independence). Let $G$ be a finite graph with $n$ vertices and $m$ edges. Then \[ \alpha(G)\ \ge\ \frac{n^2}{2m+n}. \] Consequently, if $m_1(n)$ denotes the maximum possible number of unit-distance edges among $n$ planar points, then \[ f(n)\ \ge\ \frac{n^2}{2m_1(n)+n}. \]

Proof. Let the vertex degrees be $d(v)$, $v\in V(G)$, so that $\sum_{v} d(v)=2m$. Choose a uniformly random permutation $\pi$ of $V(G)$ and define \[ I(\pi):=\{v\in V(G): v\text{ appears before all its neighbors in }\pi\}. \] Then $I(\pi)$ is an independent set: if $uv$ is an edge, it is impossible that both $u$ and $v$ appear before each other. Fix a vertex $v$ of degree $d(v)$. Among the set consisting of $v$ and its $d(v)$ neighbors (a set of size $d(v)+1$), each vertex is equally likely to be the earliest in the random permutation $\pi$, hence \[ \mathbb{P}(v\in I(\pi))=\frac{1}{d(v)+1}. \] By linearity of expectation, \[ \mathbb{E}|I(\pi)|=\sum_{v\in V(G)} \frac{1}{d(v)+1}. \] Therefore there exists at least one permutation $\pi$ with \[ \alpha(G)\ge |I(\pi)|\ge \sum_{v\in V(G)} \frac{1}{d(v)+1}. \] Apply Cauchy--Schwarz to the positive numbers $d(v)+1$: \[ \sum_{v} \frac{1}{d(v)+1} \ \ge\ \frac{n^2}{\sum_v (d(v)+1)} \ =\ \frac{n^2}{2m+n}. \] This proves $\alpha(G)\ge n^2/(2m+n)$. For unit-distance graphs on $n$ planar points, the number of edges is at most $m_1(n)$ by definition, hence $f(n)=\min \alpha\ge n^2/(2m_1(n)+n)$. $\square$

Lemma 1070.3 (a 7-vertex unit-distance graph with $\alpha=2$). There exists a set of $7$ points in the plane whose unit-distance graph has independence number $2$. Hence, for every $t\ge 1$, \[ f(7t)\le 2t, \] and in particular $f(n)\le \frac{2}{7}n + O(1)$.

Proof (explicit construction and combinatorial bound). We give coordinates for a Moser-spindle-type configuration. Let $\theta>0$ satisfy $2\sqrt{3}\,\sin(\theta/2)=1$. Define points \[ A=(0,0),\quad B=(1,0),\quad D=\left(\tfrac12,\tfrac{\sqrt{3}}{2}\right),\quad C=B+D=\left(\tfrac32,\tfrac{\sqrt{3}}{2}\right). \] Let $R_\theta$ denote rotation by $\theta$ about the origin and set \[ E=R_\theta(B),\quad F=R_\theta(D),\quad G=R_\theta(C). \] Now check unit distances:

  • In $\{A,B,C,D\}$ we have $|AB|=|AD|=|BD|=|BC|=|CD|=1$ (two equilateral triangles sharing the edge $BD$).
  • In $\{A,E,F,G\}$ we have the analogous five unit distances $|AE|=|AF|=|EF|=|EG|=|FG|=1$ by rotation invariance.
  • Finally, $|CG|=|C-R_\theta(C)|=1$ by the chord-length equation $2|C|\sin(\theta/2)=1$ and $|C|=\sqrt{3}$.
Thus the unit-distance graph on the seven vertices $\{A,B,C,D,E,F,G\}$ contains the two triangles $B\!C\!D$ and $E\!F\!G$, and $A$ is adjacent to $B,D,E,F$. From this structure we show $\alpha\le 2$:
  • If an independent set contains $A$, it cannot contain $B,D,E,F$, and among $\{C,G\}$ it can contain at most one because $C$--$G$ is an edge. So it has size $\le 2$.
  • If an independent set does not contain $A$, then it meets the triangle $\{B,C,D\}$ in at most one vertex and meets the triangle $\{E,F,G\}$ in at most one vertex, so it has size $\le 2$.
On the other hand, $\{A,C\}$ is independent (since $A$ is not adjacent to $C$), so $\alpha=2$.

To deduce $f(7t)\le 2t$, place $t$ translated copies of this 7-point configuration so far apart (distance $>2$ between distinct copies) that no unit distances occur between points from different copies. Any independent set in the union contains at most $2$ vertices from each copy, hence at most $2t$ vertices in total. $\square$

FAST REALITY CHECK (computation). Using the above coordinates and $\theta=2\arcsin(1/(2\sqrt{3}))\approx 0.5856855$ radians, a brute-force distance check (within $10^{-9}$ tolerance) finds exactly $11$ unit-distance pairs, namely \[ \{AB,AD,AE,AF,BD,BC,CD,CG,EF,EG,FG\}, \] and exhaustive search over all subsets confirms the maximum independent set size is $2$.

VERIFICATION

Lemma 1070.1 is a direct pigeonhole argument from the definition of $\chi$. Lemma 1070.2 is proved via the Caro--Wei expectation bound and Cauchy--Schwarz; all steps are explicit. Lemma 1070.3 supplies coordinates and checks unit distances by construction; the combinatorial argument for $\alpha=2$ uses only the existence of two triangles and the adjacency of $A$. The replication argument is verified by choosing inter-copy distances $>2$, ensuring cross-copy distances are $>1$. The "FAST REALITY CHECK" was done by direct computation on the stated coordinates.

FINAL

UNRESOLVED.

(i) Strongest proved partial result: We have general lower bounds $f(n)\ge \lceil n/\chi\rceil$ (Lemma 1070.1) and $f(n)\ge n^2/(2m_1(n)+n)$ (Lemma 1070.2), and an explicit construction giving $f(n)\le 2n/7+O(1)$ (Lemma 1070.3). In particular, $\limsup f(n)/n\le 2/7$ via the replicated 7-point configuration.

(ii) First gap (crisp statement): Determine the correct linear growth constant for $f(n)$ (if it exists), and specifically decide whether $f(n)\ge n/4$ holds for all $n$.

(iii) Top 3 next moves (concrete lemmas/computations):

  1. Improve upper bounds by finding smaller (or denser) finite unit-distance graphs with smaller independence ratio than $2/7$, and then replicate them.
  2. Improve lower bounds by sharpening estimates on $m_1(n)$ (maximum number of unit distances), then plugging into Lemma 1070.2.
  3. For moderate $n$ (say $n\le 50$), attempt computational search (with exact algebraic coordinates) for configurations minimizing the independence number, to guess the best constant and candidate extremizers.

(iv) Minimal counterexample structure: A counterexample to $f(n)\ge n/4$ would be a concrete $n$-point set whose unit-distance graph has an independent set of size at most $\lfloor n/4\rfloor$. Any asymptotic counterexample to a conjectured constant $c$ would require a family of finite unit-distance graphs with independence ratio $<c$.

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.