Erdős Problem #302

Problem #302

1) ROUND-2 OBJECTIVE

Path C (obstruction/correction). Round 1 already showed that the specific conjecture \[ f(N)=(1/2+o(1))N \] is false by proving the explicit lower bound $f(N)\ge (5/8+o(1))N$. The most promising round-2 task is therefore not to re-open the false $1/2$-claim, but to sharpen the corrected picture. In this round I prove a new family of solution-free sets, containing the parity construction as a special case, and I show that within this whole family the density $5/8$ is already optimal.

2) Round-1 FOUNDATION USED

I use the following Round 1 results without re-proving them.

1. If $1\le a,b,c\le N$ are pairwise distinct and $1/a=1/b+1/c$, then $a<N/2$.
2. The identity $bc=a(b+c)$ is equivalent to $1/a=1/b+1/c$.
3. The Round 1 construction \[ [\lceil N/2\rceil,N]\ \cup\ \{n\le N/4:\ n\text{ odd}\} \] is solution-free and has size $(5/8+o(1))N$.

3) NEW INSIGHT / TOOL (ROUND-2)

The new tool is a single-residue-class modular obstruction. Instead of taking the low block to be the odd numbers, I take it to be one fixed invertible residue class modulo an arbitrary modulus $m\ge 2$. The parity construction is exactly the case $(m,r)=(2,1)$. This gives a larger theorem and, after optimizing the interval parameter, proves that $5/8$ is the best density obtainable from any construction of this one-residue/one-interval type.

4) ATTACK PLAN (ROUND-2)

The gap left after Round 1 was that the $(5/8)$-construction looked somewhat ad hoc. To improve on that, I will:

1. prove a general theorem for sets of the form \[ \{n\le \beta N/2:\ n\equiv r\pmod m\}\cup [\beta N,N], \] with $1/2\le \beta\le 1$ and $(r,m)=1$;
2. optimize the resulting density over $\beta$ and $m$;
3. check carefully that the modular argument still works when $m$ is composite and one of $b,c$ is not coprime to $m$.

5) WORK (ROUND-2)

Theorem. Fix integers $m\ge 2$ and $r$ with $(r,m)=1$, and fix a real number $\beta$ with $1/2\le \beta\le 1$. Define \[ L_N(m,r,\beta):=\{n\in\{1,\dots,N\}: n\le \lfloor \beta N/2\rfloor,\ n\equiv r\pmod m\}, \] \[ U_N(\beta):=\{\lceil \beta N\rceil,\lceil \beta N\rceil+1,\dots,N\}, \] and \[ A_N(m,r,\beta):=L_N(m,r,\beta)\cup U_N(\beta). \] Then $A_N(m,r,\beta)$ contains no pairwise distinct $a,b,c$ with \[ \frac1a=\frac1b+\frac1c. \] Consequently, \[ f(N)\ge \left(1-\beta+\frac{\beta}{2m}\right)N+O(1). \] Within this family the density is maximized at $\beta=1/2$, where it becomes \[ \frac12+\frac{1}{4m}. \] Hence the best member of this entire family is the parity construction $(m,r,\beta)=(2,1,1/2)$, which recovers density $5/8$.

Proof. Assume for contradiction that distinct $a,b,c\in A_N(m,r,\beta)$ satisfy $1/a=1/b+1/c$. By the Round 1 lemma, the smallest denominator in any such triple satisfies $a<N/2$. Since $\beta\ge 1/2$, every element of $U_N(\beta)$ is at least $N/2$, so necessarily \[ a\in L_N(m,r,\beta). \] In particular, \[ a\le \beta N/2, \qquad a\equiv r\pmod m, \qquad (a,m)=1. \]

I now show that neither $b$ nor $c$ can lie in $L_N(m,r,\beta)$. Suppose first that $b\in L_N(m,r,\beta)$. Then also $b\equiv r\pmod m$ and $(b,m)=1$. There are two cases.

Case 1: $(c,m)=1$. Then $a,b,c$ are all invertible modulo $m$, and from \[ bc=a(b+c) \] we may divide by $abc$ modulo $m$ to get \[ a^{-1}\equiv b^{-1}+c^{-1}\pmod m. \] But $a\equiv b\equiv r\pmod m$, so $a^{-1}\equiv b^{-1}\equiv r^{-1}\pmod m$, hence \[ r^{-1}\equiv r^{-1}+c^{-1}\pmod m, \] which gives $c^{-1}\equiv 0\pmod m$, impossible.

Case 2: $(c,m)>1$. Choose a prime $q\mid (c,m)$. Since $a\equiv b\equiv r\pmod m$ and $(r,m)=1$, we have $q\nmid a$ and $q\nmid b$, whereas $q\mid c$. Reducing \[ bc=a(b+c) \] modulo $q$, the left-hand side is $0$, while the right-hand side is congruent to $ab\not\equiv 0\pmod q$. Contradiction.

Thus $b\notin L_N(m,r,\beta)$. By symmetry $c\notin L_N(m,r,\beta)$ as well. Therefore both $b$ and $c$ must lie in $U_N(\beta)$, so \[ b,c\ge \beta N. \] Assume $b\le c$. Then, because the denominators are distinct, \[ \frac1a=\frac1b+\frac1c<\frac{2}{b}\le \frac{2}{\beta N}, \] so \[ a>\beta N/2. \] But we already know $a\le \beta N/2$, contradiction. This proves that $A_N(m,r,\beta)$ is solution-free.

For the size estimate, we have \[ |U_N(\beta)|=(1-\beta)N+O(1), \qquad |L_N(m,r,\beta)|=\frac{\beta}{2m}N+O(1), \] so \[ |A_N(m,r,\beta)|=\left(1-\beta+\frac{\beta}{2m}\right)N+O(1). \] Since $m\ge 2$, the coefficient of $\beta$ here is \[ -1+\frac{1}{2m}<0, \] so the density is maximized when $\beta$ is as small as allowed, namely $\beta=1/2$. This gives the best density inside the family as \[ \frac12+\frac{1}{4m}. \] Finally, this is maximized over $m\ge 2$ at $m=2$, giving $5/8$. $\square$

6) ADVERSARIAL VERIFICATION

1. Could the modular step fail for composite $m$? No. If $(c,m)=1$, inverses modulo $m$ exist and the proof is direct. If $(c,m)>1$, one passes to a prime divisor $q\mid (c,m)$ and obtains a contradiction modulo $q$.
2. Could $b$ and $c$ both be in the upper block without contradiction when $b=\beta N$? No. Distinctness gives \[ \frac1b+\frac1c<\frac2b\le \frac{2}{\beta N}, \] so the resulting inequality for $a$ is strict.
3. Did I accidentally use a larger family than I actually proved? No. The theorem covers exactly one residue class modulo $m$ in the low interval, not an arbitrary set of residues. I am not claiming optimality beyond this family.
4. Does the density computation double-count an overlap between low and upper blocks? No. Since $\beta/2<\beta$, the intervals $[1,\beta N/2]$ and $[\beta N,N]$ are disjoint for every $\beta>0$.

7) FINAL (EXACTLY ONE)

UNRESOLVED (BUT STRICTLY ADVANCED). Round 2 proves a genuine new theorem: the Round 1 parity construction is the optimal member of the entire one-residue/one-interval family \[ \{n\le \beta N/2:\ n\equiv r\pmod m\}\cup [\beta N,N]. \] This does not determine the true asymptotic of $f(N)$, but it does explain rigorously why the Round 1 $(5/8)$-construction is the best possible within a broad modular template.

8) COMPLETION ESTIMATE

COMPLETION: 40%

9) REFERENCES

• Round 1 output in this conversation (used as fixed foundation).
• T. F. Bloom, Erdős Problem #302.

Erdős Problem #302: independent continuation

Date: 23 September 2026. Source versions read in full: 302.tex in gpt_pro_5.4.

1) OBJECTIVE AND SOURCE AUDIT

Let $f(N)$ maximize the size of a subset of $[1,N]$ containing no three distinct denominators with $1/a=1/b+1/c$. The source supplies density $5/8$ and optimizes a single-residue low block plus a high interval. I extend its obstruction to several residue classes simultaneously and show why this broader version still cannot beat $5/8$.

2) WORK: A MULTI-RESIDUE BARRIER

Let $R$ be a set of units modulo $m\ge2$ such that \[ \gcd(r-s,m)>1\quad\hbox{for all }r,s\in R. \tag{1} \] Take \[ A=\{n\le N/4:n\bmod m\in R\}\ \cup\ [\lceil N/2\rceil,N]. \] This is solution-free. In any proposed solution the smallest denominator is $a=bc/(b+c)<N/2$, so it lies in the low block. If $b$ also lies there, the equation becomes $(b-a)c=ab$. Since $a,b$ are units modulo $m$, this congruence has a solution in $c$ only if $\gcd(b-a,m)=1$, contrary to $1$. The same argument excludes $c$ from the low block. If both $b,c$ are high, then $1/a=1/b+1/c<4/N$, hence $a>N/4$, another contradiction. Consequently \[ |A|=\left(\frac12+\frac{|R|}{4m}\right)N+O_m(1). \]

But $R$ and $R+1$ are disjoint in $\mathbb Z/m\mathbb Z$: an intersection would give two members differing by one, whose difference is coprime to $m$. Thus $2|R|\le m$, and this entire compatible multi-residue template has density at most $5/8$. The parity choice $m=2,R=\{1\}$ attains it.

3) ADVERSARIAL VERIFICATION

Condition $1$ is sufficient to forbid a low--low pair for every third residue. It is not necessary for every possible interval construction. Accordingly the upper bound just proved is a bound on this template, not on $f(N)$. It does not rule out interdependent choices of several scale intervals or more selective choices of the third denominator. No assertion that the optimal asymptotic constant equals $5/8$ is made.

7) FINAL AND SOURCE

UNRESOLVED. A larger class than the source's one-residue family has been analyzed rigorously, but the global extremal question remains. The target and the existing $5/8$ construction are taken from the supplied 302.tex; the external search returned official indexing but did not supply an additional theorem used in this proof.

8) COMPLETION ESTIMATE

COMPLETION: 10% This is a subjective estimate of progress toward the entire stated problem, not a probability that the conjecture or an unverified proof is correct.

Problem #302

1) FORMAL RESTATEMENT

Let $N\in\mathbb{N}$ and write $[N]=\{1,2,\dots,N\}$. Define \[ f(N) := \max\Big\{ |A| : A\subseteq [N]\ \text{and there do not exist pairwise distinct }a,b,c\in A\ \text{with }\frac1a=\frac1b+\frac1c\Big\}. \] The problem asks for asymptotics of $f(N)$ as $N\to\infty$ ("estimate $f(N)$"), and in particular asks whether \[ f(N)=(1/2+o(1))N \] holds. (As written, this last sentence is a concrete conjectural asymptotic.)

2) QUICK LITERATURE/CONTEXT CHECK

I checked the ErdosProblems entry for #302 and its linked comments/notes. The prompt itself already records the main currently-advertised bounds:

• Lower bounds: $f(N)\ge (1/2+o(1))N$ from $A=\{\text{odd}\}$ or $A=[\lceil N/2\rceil, N]$; and an improved construction $f(N)\ge (5/8+o(1))N$ attributed to Stijn Cambie.
• Upper bound: Wouter van Doorn gives $f(N)\le (9/10+o(1))N$.

My quick web search did not reveal a newer asymptotic constant determination beyond these notes.

3) ATTACK PLAN

1. Structural rewrite. Rewrite the Diophantine condition in a form that makes combinatorial obstructions transparent.
2. Disprove the specific $1/2$-asymptotic. Exhibit an explicit family of sets $A\subseteq[N]$ with density strictly bigger than $1/2$ and prove they contain no solutions.
3. Reality check. Compute $f(N)$ for small $N$ via exact search (maximum independent set in a 3-uniform hypergraph) to see what densities appear.
4. What would remain. Any true asymptotic will require either a much better construction (raising the lower bound) or a density/supersaturation theorem (lowering the upper bound).

4) WORK

4.1. Algebraic normal form.

If $a,b,c\in\mathbb{N}$ satisfy $ \frac1a=\frac1b+\frac1c $ then \[ \frac1a = \frac{b+c}{bc}\quad\Longleftrightarrow\quad bc=a(b+c)\quad\Longleftrightarrow\quad (b-a)(c-a)=a^2. \] In particular $bc=a(b+c)$ implies $bc>ab$ and $bc>ac$, so $b>a$ and $c>a$. Conversely, any factorisation $a^2=de$ with $d,e\in\mathbb{N}$ and $d\ne e$ gives a solution \[ b=a+d,\qquad c=a+e \] with $b\ne c$ and $\frac1a=\frac1b+\frac1c$.

4.2. A universal inequality: $a<\tfrac{N}{2}$ in any solution inside $[N]$ (with $b\ne c$).

Assume $1\le a<b<c\le N$ and $\frac1a=\frac1b+\frac1c$. Then \[ a=\frac{bc}{b+c} \le \frac{bc}{2\sqrt{bc}} = \frac{\sqrt{bc}}{2}\le \frac{N}{2} \] by AM--GM and $\sqrt{bc}\le N$. Moreover equality $a=N/2$ forces $\sqrt{bc}=N$ and $b+c=2\sqrt{bc}$, hence $b=c=N$, which is excluded by distinctness. Therefore: \begin{equation} \label{wsref-0-65-71-3a-61-2d-73-74-72-69-63-74-2d-68-61-6c-66} \boxed{\text{If }1\le a,b,c\le N\text{ are distinct and }\tfrac1a=\tfrac1b+\tfrac1c,\text{ then }a<\tfrac{N}{2}.} \end{equation} This immediately proves that $A=[\lceil N/2\rceil,N]$ is solution-free.

4.3. Parity obstruction.

If $b$ and $c$ are both odd, then $bc$ is odd and $b+c$ is even, so $(b+c)/bc$ is a rational with even numerator and odd denominator in lowest terms; it cannot equal $1/a$. Equivalently: there is no integer solution to $\frac1a=\frac1b+\frac1c$ with $b,c$ odd.

4.4. A rigorous $(5/8)$-density construction (disproving the $1/2$ asymptotic conjecture).

Define \[ A_N := \{n\in [N] : n\ge \lceil N/2\rceil\}\ \cup\ \{n\in[N] : n\le \lfloor N/4\rfloor\ \text{and $n$ is odd}\}. \] Then \[ |A_N| = \big(N-\lceil N/2\rceil+1\big) + \#\{\text{odd }n\le \lfloor N/4\rfloor\} = \frac{N}{2} + \frac{N}{8} + O(1) = \Big(\frac{5}{8}+o(1)\Big)N. \]

4.5. Small-$N$ computation (exact).

As a quick reality check, I exhaustively computed $f(N)$ for $N\le 100$ by modeling the valid triples as a 3-uniform hypergraph and running a branch-and-bound maximum independent set search. The resulting densities are much larger than $5/8$ for these $N$ (e.g. $f(100)=86$), illustrating that the extremal behavior for small $N$ is not yet close to any conjectural asymptotic. A witness for $N=100$ is $A=[100]\setminus\{6,8,12,14,18,20,22,24,28,30,48,78,84,90\}$.

5) VERIFICATION

• The equivalence $(b-a)(c-a)=a^2$ was checked by direct algebra.
• Inequality (eq:a-strict-half) was derived from AM--GM and is strict because $b\ne c$.
• In the $(5/8)$ construction proof, the key steps are: (i) $a<N/2$ forces $a$ to be odd $\le N/4$; (ii) that forces $b,c$ even; (iii) then $b,c\ge N/2$ forces $a>N/4$; contradiction.
• Computations (not reproduced here) verified that the displayed witness for $N=100$ contains no forbidden triple.

6) FINAL

UNRESOLVED.

1. Progress achieved. I gave a complete proof of the explicit construction $A_N$ of size $(5/8+o(1))N$ with no solutions, which in particular disproves the conjectural asymptotic $f(N)=(1/2+o(1))N$. I also recorded the structural identity $(b-a)(c-a)=a^2$ and the universal constraint $a<N/2$ for any solution in $[N]$.
2. Where it got stuck. Determining the true asymptotic constant (or even improving the $(9/10)$ upper bound or the $(5/8)$ lower bound) appears to require substantially new extremal/combinatorial input; the present work does not bridge that gap.
3. What next steps would look like. (a) Use the factorisation form $(b-a)(c-a)=a^2$ to set up a hypergraph container/supersaturation argument for dense $A$. (b) Search for higher-density constructions guided by exact solutions for moderate $N$ and attempt to prove a general pattern.
4. Falsifiable conjecture. Based on the existing upper bound $f(N)\le (0.9+o(1))N$ and my small-$N$ computations hovering around $\approx 0.86N$, a plausible guess is that $f(N)=(c+o(1))N$ for some constant $c\in[0.85,0.9]$.

7) COMPLETION ESTIMATE

To "complete" the original problem (i.e. pin down the correct asymptotics of $f(N)$), one would need either: (i) a new construction improving the best-known lower density, or (ii) a new extremal argument improving the best-known upper density. Either route would likely require nontrivial new ideas beyond the parity/interval obstructions used above.