Erdős Problem #953

Erdős Problem 953 --- collection record

PROVENANCE AND STATUS

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

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

REUSED SOURCE 1

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

Erdős Problem #953

FORMAL RESTATEMENT

Fix $r>0$ and let $D_r:=\{x\in\mathbb R^2:|x|<r\}$. Let $A\subset D_r$ be Lebesgue measurable and assume that for all distinct $a,b\in A$, \[ |a-b|\notin \mathbb Z. \] Let $m(\cdot)$ denote planar Lebesgue measure. Question: how large can $m(A)$ be as a function of $r$?

QUICK LITERATURE/CONTEXT CHECK

The extracted text states that the trivial upper bound is $O(r)$ and mentions an unpublished remark attributed to Sárközi and a lower bound adaptation giving $\gg r^{0.26}$. I will only prove the trivial $O(r)$ bound (with an explicit constant) and record the trivial small-$r$ lower bound.

ATTACK PLAN

• Reduce to a 1D statement: for each horizontal line, the intersection of $A$ with that line has no integer distances, hence its 1D measure is $\le 1$.
• Integrate the 1D bound over $y\in[-r,r]$ by Fubini to get $m(A)\le 2r$.
• Sanity-check small $r$ (e.g. $r<1/2$) where the whole disk works.

WORK

Fast reality check. If $0<r<\tfrac12$, then taking $A=D_r$ gives $|a-b|<1$ for all $a,b\in A$, hence no integer distances. So $m(A)$ can be as large as $\pi r^2$ for small $r$.

Lemma 953.1 (1D measure bound for avoiding integer distances). Let $B\subset\mathbb R$ be Lebesgue measurable and suppose that for all distinct $x,y\in B$, \[|x-y|\notin\mathbb Z.\] Then the 1D Lebesgue measure $m_1(B)\le 1$.

Proof. For each integer $k\in\mathbb Z$, define \[ B_k := (B\cap [k,k+1)) - k \ \subseteq [0,1). \] Then $m_1(B_k)=m_1(B\cap [k,k+1))$ by translation invariance. We claim the sets $\{B_k\}_{k\in\mathbb Z}$ are pairwise disjoint. Indeed, if $t\in B_k\cap B_\ell$, then there exist $x\in B\cap[k,k+1)$ and $y\in B\cap[\ell,\ell+1)$ with $t=x-k=y-\ell$. Thus $x-y=k-\ell\in\mathbb Z$. If $k\ne \ell$ then $x\ne y$ and this contradicts the hypothesis. Hence $B_k\cap B_\ell=\emptyset$ for $k\ne\ell$.

Since all $B_k\subseteq[0,1)$ are disjoint and $\mathbb Z$ is countable, \[ \sum_{k\in\mathbb Z} m_1(B_k)= m_1\left(\bigsqcup_{k\in\mathbb Z} B_k\right)\le m_1([0,1))=1. \] But \[ \sum_{k\in\mathbb Z} m_1(B_k)=\sum_{k\in\mathbb Z} m_1(B\cap[k,k+1))=m_1(B). \] Therefore $m_1(B)\le1$. $\square$

Lemma 953.2 (trivial planar upper bound $m(A)\le 2r$). Let $A\subset D_r$ be measurable with no integer distances. Then \[ m(A)\le 2r. \]

Proof. For each $y\in\mathbb R$, define the horizontal section \[ A_y:=\{x\in\mathbb R:(x,y)\in A\}. \] By Fubini's theorem, \[ m(A)=\int_{\mathbb R} m_1(A_y)\,dy. \] If $(x_1,y)$ and $(x_2,y)$ are distinct points of $A$ on the same horizontal line, their Euclidean distance is $|x_1-x_2|$. Since $A$ has no integer distances, it follows that for each fixed $y$, the measurable set $A_y\subset\mathbb R$ satisfies the 1D hypothesis of Lemma 953.1. Hence $m_1(A_y)\le1$ for all $y$.

Also, since $A\subset D_r$, we have $A_y=\emptyset$ unless $|y|<r$. Therefore \[ m(A)=\int_{-r}^{r} m_1(A_y)\,dy\le \int_{-r}^{r} 1\,dy=2r. \] $\square$

VERIFICATION

• Lemma 953.1: checked disjointness of $B_k$ uses only the fact that equal fractional parts in different integer blocks would give an integer difference.
• Lemma 953.2: checked that distance along horizontal line equals $|x_1-x_2|$ exactly, so integer distances in 2D would be forced by integer differences in the 1D sections.
• Edge case: if $r<1/2$, the lower bound $m(A)\ge \pi r^2$ from $A=D_r$ is consistent with the upper bound $2r$.

FINAL

UNRESOLVED

(i) Strongest proved partial result. We proved an explicit "trivial" upper bound $m(A)\le 2r$ for any measurable $A\subset D_r$ avoiding integer distances (Lemma 953.2). For $r<1/2$, one can achieve $m(A)=\pi r^2$ by taking $A=D_r$.

(ii) First gap. Improve the growth-rate bounds: either produce constructions with $m(A)\gg r^{\alpha}$ for larger $\alpha$ (or even $\gg r$), or prove a better upper bound $o(r)$ or $r^{1-\varepsilon}$.

(iii) Top 3 next moves.

1. Explore lower-bound constructions by placing many small discs with radii shrinking to control distances between different components, and optimize the total area under the "avoid all integers" constraint.
2. Attempt Fourier-analytic bounds: interpret the forbidden distances as constraints on the autocorrelation of $1_A$ and exploit positivity/oscillation of Bessel functions for integer radii.
3. Investigate whether one can strengthen Lemma 953.1 by considering multiple directions (not just horizontal) to improve the constant or power of $r$.

(iv) What a minimal counterexample would likely look like. If one hopes for an upper bound $o(r)$, a near-extremal set would likely be "essentially 1-dimensional": concentrated near a curve or union of thin strips so that typical pairwise distances avoid integers. If one hopes for a linear lower bound $\gg r$, a construction would need to arrange many components while controlling the dense set of inter-component distances so that none hit an integer.

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.

Erdős Problem #953

FORMAL RESTATEMENT

Fix $r>0$ and let $D_r:=\{x\in\mathbb R^2:|x|<r\}$. Let $A\subset D_r$ be Lebesgue measurable and assume that for all distinct $a,b\in A$, \[ |a-b|\notin \mathbb Z. \] Let $m(\cdot)$ denote planar Lebesgue measure. Question: how large can $m(A)$ be as a function of $r$?

QUICK LITERATURE/CONTEXT CHECK

The extracted text states that the trivial upper bound is $O(r)$ and mentions an unpublished remark attributed to Sárközi and a lower bound adaptation giving $\gg r^{0.26}$. I will only prove the trivial $O(r)$ bound (with an explicit constant) and record the trivial small-$r$ lower bound.

ATTACK PLAN

• Reduce to a 1D statement: for each horizontal line, the intersection of $A$ with that line has no integer distances, hence its 1D measure is $\le 1$.
• Integrate the 1D bound over $y\in[-r,r]$ by Fubini to get $m(A)\le 2r$.
• Sanity-check small $r$ (e.g. $r<1/2$) where the whole disk works.

WORK

Fast reality check. If $0<r<\tfrac12$, then taking $A=D_r$ gives $|a-b|<1$ for all $a,b\in A$, hence no integer distances. So $m(A)$ can be as large as $\pi r^2$ for small $r$.

Lemma 953.1 (1D measure bound for avoiding integer distances). Let $B\subset\mathbb R$ be Lebesgue measurable and suppose that for all distinct $x,y\in B$, \[|x-y|\notin\mathbb Z.\] Then the 1D Lebesgue measure $m_1(B)\le 1$.

Proof. For each integer $k\in\mathbb Z$, define \[ B_k := (B\cap [k,k+1)) - k \ \subseteq [0,1). \] Then $m_1(B_k)=m_1(B\cap [k,k+1))$ by translation invariance. We claim the sets $\{B_k\}_{k\in\mathbb Z}$ are pairwise disjoint. Indeed, if $t\in B_k\cap B_\ell$, then there exist $x\in B\cap[k,k+1)$ and $y\in B\cap[\ell,\ell+1)$ with $t=x-k=y-\ell$. Thus $x-y=k-\ell\in\mathbb Z$. If $k\ne \ell$ then $x\ne y$ and this contradicts the hypothesis. Hence $B_k\cap B_\ell=\emptyset$ for $k\ne\ell$.

Since all $B_k\subseteq[0,1)$ are disjoint and $\mathbb Z$ is countable, \[ \sum_{k\in\mathbb Z} m_1(B_k)= m_1\left(\bigsqcup_{k\in\mathbb Z} B_k\right)\le m_1([0,1))=1. \] But \[ \sum_{k\in\mathbb Z} m_1(B_k)=\sum_{k\in\mathbb Z} m_1(B\cap[k,k+1))=m_1(B). \] Therefore $m_1(B)\le1$. $\square$

Lemma 953.2 (trivial planar upper bound $m(A)\le 2r$). Let $A\subset D_r$ be measurable with no integer distances. Then \[ m(A)\le 2r. \]

Proof. For each $y\in\mathbb R$, define the horizontal section \[ A_y:=\{x\in\mathbb R:(x,y)\in A\}. \] By Fubini's theorem, \[ m(A)=\int_{\mathbb R} m_1(A_y)\,dy. \] If $(x_1,y)$ and $(x_2,y)$ are distinct points of $A$ on the same horizontal line, their Euclidean distance is $|x_1-x_2|$. Since $A$ has no integer distances, it follows that for each fixed $y$, the measurable set $A_y\subset\mathbb R$ satisfies the 1D hypothesis of Lemma 953.1. Hence $m_1(A_y)\le1$ for all $y$.

Also, since $A\subset D_r$, we have $A_y=\emptyset$ unless $|y|<r$. Therefore \[ m(A)=\int_{-r}^{r} m_1(A_y)\,dy\le \int_{-r}^{r} 1\,dy=2r. \] $\square$

VERIFICATION

• Lemma 953.1: checked disjointness of $B_k$ uses only the fact that equal fractional parts in different integer blocks would give an integer difference.
• Lemma 953.2: checked that distance along horizontal line equals $|x_1-x_2|$ exactly, so integer distances in 2D would be forced by integer differences in the 1D sections.
• Edge case: if $r<1/2$, the lower bound $m(A)\ge \pi r^2$ from $A=D_r$ is consistent with the upper bound $2r$.

FINAL

UNRESOLVED

(i) Strongest proved partial result. We proved an explicit "trivial" upper bound $m(A)\le 2r$ for any measurable $A\subset D_r$ avoiding integer distances (Lemma 953.2). For $r<1/2$, one can achieve $m(A)=\pi r^2$ by taking $A=D_r$.

(ii) First gap. Improve the growth-rate bounds: either produce constructions with $m(A)\gg r^{\alpha}$ for larger $\alpha$ (or even $\gg r$), or prove a better upper bound $o(r)$ or $r^{1-\varepsilon}$.

(iii) Top 3 next moves.

1. Explore lower-bound constructions by placing many small discs with radii shrinking to control distances between different components, and optimize the total area under the "avoid all integers" constraint.
2. Attempt Fourier-analytic bounds: interpret the forbidden distances as constraints on the autocorrelation of $1_A$ and exploit positivity/oscillation of Bessel functions for integer radii.
3. Investigate whether one can strengthen Lemma 953.1 by considering multiple directions (not just horizontal) to improve the constant or power of $r$.

(iv) What a minimal counterexample would likely look like. If one hopes for an upper bound $o(r)$, a near-extremal set would likely be "essentially 1-dimensional": concentrated near a curve or union of thin strips so that typical pairwise distances avoid integers. If one hopes for a linear lower bound $\gg r$, a construction would need to arrange many components while controlling the dense set of inter-component distances so that none hit an integer.