we-solve (beta)

Math-6120-A1 · revision r1 · on Math-6120

Reused writeup on Math-6120 (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 1066 --- 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 1066 --- collection record

PROVENANCE AND STATUS

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

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/1066.tex.

REUSED SOURCE 1

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

FORMAL RESTATEMENT

Let $P\subset\mathbb{R}^2$ be a set of $n$ points with pairwise distances at least $1$: \[ |x-y|\ge 1\quad\text{for all distinct }x,y\in P. \] Define a graph $G(P)$ with vertex set $P$ by joining $x,y\in P$ by an edge iff $|x-y|=1$. Let \[ g(n) := \min_{|P|=n,\ \min_{x\ne y}|x-y|\ge 1}\ \alpha(G(P)), \] where $\alpha(G)$ is the independence number. The problem asks for estimates on $g(n)$ and in particular the behavior of $g(n)/n$ as $n\to\infty$.

QUICK LITERATURE/CONTEXT CHECK

The problem file states (i) Pollack noted that the four color theorem implies $g(n)\ge n/4$; (ii) constructions give $g(n)\le 6n/19$; (iii) Csizmadia gives $n/4\le g(n)\le (3n+7)/11$. I will not use any external improvements beyond these statements; instead I prove the basic geometric planarity fact and the $n/4$ consequence.

ATTACK PLAN

Show $G(P)$ is planar by drawing edges as straight segments and ruling out crossings using the distance-$\ge 1$ constraint. Then apply 4-colorability to force an independent set of size at least $n/4$. For an upper bound construction, exhibit configurations whose graphs are disjoint unions of triangles.

WORK

Lemma 1066.1 (crossing unit edges force a short distance). Let $A,B,C,D\in\mathbb{R}^2$ and suppose the closed line segments $\overline{AB}$ and $\overline{CD}$ intersect at a point $X$ that is interior to both segments. If $|AB|=|CD|=1$, then at least one of the four distances $|AC|,|AD|,|BC|,|BD|$ is strictly less than $1$.

Proof. Because $X$ is interior to $\overline{AB}$, we have $|AX|>0$, $|BX|>0$, and $|AX|+|BX|=|AB|=1$. Hence $\min(|AX|,|BX|)\le 1/2$. Similarly, $\min(|CX|,|DX|)\le 1/2$. Choose $P\in\{A,B\}$ so that $|PX|\le 1/2$ and choose $Q\in\{C,D\}$ so that $|QX|\le 1/2$. Then by the triangle inequality, \[ |PQ| \le |PX|+|XQ| \le \tfrac12+\tfrac12 = 1. \] If equality held, then we would have $P,X,Q$ collinear with $X$ between $P$ and $Q$ and also $|PX|=|XQ|=1/2$. But $P,X$ lies on the line through $A,B$ and $Q,X$ lies on the line through $C,D$. Since $X$ is an interior intersection point of the two segments, these two lines are not the same line. Hence $P,X,Q$ cannot be collinear, so the inequality is strict and $|PQ|<1$. Thus one of $|AC|,|AD|,|BC|,|BD|$ is $<1$. $\square$

Lemma 1066.2 (planarity of $G(P)$). For any $P$ as in the problem, the straight-line drawing of $G(P)$ with vertices at the points of $P$ and edges drawn as straight segments has no crossings; in particular $G(P)$ is planar.

Proof. Assume for contradiction that two edges $xy$ and $uv$ of $G(P)$ cross in their interiors when drawn as straight segments. Then $|x-y|=|u-v|=1$ by definition of the edges, and the two segments intersect in their interiors. By Lemma 1066.1, one of the distances between an endpoint of the first edge and an endpoint of the second edge is strictly less than $1$. This contradicts the hypothesis that all pairwise distances among points of $P$ are at least $1$. Therefore no two edges cross, and the drawing is planar. $\square$

Lemma 1066.3 ($n/4$ independent set lower bound). For all $n\ge 1$, $g(n)\ge \lceil n/4\rceil$.

Proof. Fix any admissible $P$ with $|P|=n$. By Lemma 1066.2, $G(P)$ is planar. By the four color theorem, $G(P)$ admits a proper vertex-coloring with at most $4$ colors. In any $4$-coloring, the largest color class has size at least $\lceil n/4\rceil$ and is an independent set. Hence $\alpha(G(P))\ge \lceil n/4\rceil$. Taking the minimum over all admissible $P$ gives $g(n)\ge \lceil n/4\rceil$. $\square$

Lemma 1066.4 (triangle construction gives $\lceil n/3\rceil$ upper bound). For each $n\ge 1$, there exists an admissible point set $P$ of size $n$ for which $\alpha(G(P))=\lceil n/3\rceil$. In particular $g(n)\le \lceil n/3\rceil$.

Proof. Write $n=3m+r$ with $r\in\{0,1,2\}$. Place $m$ disjoint equilateral triangles of side length $1$ very far apart from each other (e.g. translate the $i$th triangle by a vector of length $>10$ from the origin and from all previous triangles). This ensures:

  • within each triangle, all three pairwise distances are $1$;
  • between points from different triangles, all distances are $>1$;
  • hence the minimum pairwise distance is $1$.
If $r>0$, add $r$ more points far from everything else and also far from each other (distance $>1$), so they are isolated vertices. In the resulting graph, each triangle forms a $K_3$ component and each extra point is isolated. Any independent set can contain at most one vertex from each triangle, and it can contain all isolated vertices. Therefore \[ \alpha(G(P)) = m + r = \lceil n/3\rceil. \] This proves existence of a configuration with independence number $\lceil n/3\rceil$, hence $g(n)\le \lceil n/3\rceil$. $\square$

FAST REALITY CHECK (small $n$). From the definitions:

  • $g(1)=1$.
  • $g(2)=1$ since two points at distance $1$ give a single edge.
  • $g(3)=1$ using an equilateral triangle of side $1$.
  • $g(4)=2$: the lower bound gives $g(4)\ge 1$, but $g(4)\ge 2$ because $\alpha(G)=1$ would force $G\cong K_4$, impossible here; and the unit square configuration gives $\alpha=2$ so $g(4)\le 2$.
  • $g(5)=2$: lower bound $\lceil 5/4\rceil=2$ and the construction "triangle + edge far away" gives $\alpha=2$.
  • $g(6)=2$: lower bound $\lceil 6/4\rceil=2$ and two disjoint triangles give $\alpha=2$.

VERIFICATION

Lemma 1066.1 was proved purely from triangle inequality and the geometry of an interior crossing. Lemma 1066.2 uses Lemma 1066.1 and the minimum distance hypothesis. Lemma 1066.3 uses only the four color theorem (explicitly mentioned in the problem file) and an averaging argument over color classes. Lemma 1066.4 checks all distance constraints by placing components far apart. The stated small-$n$ values are justified by explicit configurations and simple impossibility arguments.

FINAL

UNRESOLVED.

(i) Strongest proved partial result: Every such graph $G(P)$ is planar (Lemma 1066.2), hence $\alpha(G(P))\ge \lceil n/4\rceil$ and therefore $g(n)\ge \lceil n/4\rceil$ (Lemma 1066.3). A simple explicit construction shows $g(n)\le \lceil n/3\rceil$ (Lemma 1066.4).

(ii) First gap (crisp statement): Determine the true asymptotic constant $\lim_{n\to\infty} g(n)/n$ (if it exists), or improve the current interval between the general lower bound $1/4$ and known constructions.

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

  1. Attempt to exploit additional geometric structure beyond planarity (e.g. constraints on local configurations in a unit-circle packing/contact graph) to improve the $n/4$ bound.
  2. For upper bounds, search for explicit periodic point configurations with minimum distance $\ge 1$ and small independence ratio; a concrete step is to optimize such configurations numerically in bounded windows and then periodize.
  3. Compute exact $g(n)$ for small $n$ by enumerating feasible contact graphs of unit disk packings (penny graphs) and taking the minimum independence number among realizable graphs.

(iv) Minimal counterexample structure: A counterexample to any proposed bound $g(n)\ge c n$ would be an explicit admissible configuration $P$ whose unit-distance graph has independence number $<c n$. Such a configuration must in particular realize a planar graph with unusually small independence ratio and respect the geometric "no crossings" constraint of Lemma 1066.2.

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.