Erdős Problem #301

Erdős Problem #301

1) ROUND-2 OBJECTIVE

I pursue path (A): prove a genuinely stronger upper bound for $f(N)$.

Round 1 reconstructed the known bound \[ f(N)\le \left(\frac{25}{28}+o(1)\right)N \] from the disjoint blocks $\{2a,3a,4a,6a,12a\}$. The most promising Round-2 direction is to enlarge the local forbidden block while keeping the blocks pairwise disjoint. This is exactly what the new argument does.

2) Round-1 FOUNDATION USED

I use the following Round-1 facts.

• The definition of $f(N)$ as the largest size of a set $A\subseteq\{1,\ldots,N\}$ containing no distinct solution to \[ \frac1a=\frac1{b_1}+\cdots+\frac1{b_k}. \]
• The trivial lower bound $f(N)\ge \lfloor N/2\rfloor$, from $A$ equal to the integers in $(N/2,N]$.
• The Round-1 block argument giving \[ f(N)\le \left(\frac{25}{28}+o(1)\right)N. \]
• The exact values of $f(N)$ for $N\le 15$.

I do not re-prove the Round-1 $25/28$ bound; I only use it as the baseline to improve upon.

3) NEW INSIGHT / TOOL (ROUND-2)

The new block is \[ T_a:=\{2a,3a,4a,6a,8a,12a,24a\}\cap[1,N]. \]

I choose $a$ from the set \[ \mathcal{I}:=\{16^b 9^c d:\ b,c\ge 0,\ (d,6)=1\}. \] Equivalently, \[ v_2(a)\equiv 0\ (\mathrm{mod}\ 4), \qquad v_3(a)\equiv 0\ (\mathrm{mod}\ 2). \]

The residue pairs modulo $(4,2)$ of the multipliers \[ 2,3,4,6,8,12,24 \] are all distinct, so these larger blocks are still pairwise disjoint. The local hypergraph on this block is stronger than in Round 1 and forces more omissions.

4) ATTACK PLAN (ROUND-2)

The exact Round-1 gap was quantitative: the local block $\{2a,3a,4a,6a,12a\}$ forced only a density loss of $3/28$.

To improve this I will:

• prove pairwise disjointness of the larger blocks $T_a$ for $a\in\mathcal I$;
• prove local omission bounds: \[ \begin{array}{ll} a\le N/24 & \Longrightarrow \mbox{at least $3$ omissions from }T_a,\\ N/24<a\le N/12 & \Longrightarrow \mbox{at least $2$ omissions from }T_a,\\ N/12<a\le N/6 & \Longrightarrow \mbox{at least $1$ omission from }T_a; \end{array} \]
• count how many such $a$ exist.

This directly overcomes the Round-1 obstacle by extracting more omissions from each disjoint block.

5) WORK (ROUND-2)

Step 1: the new block and its identities.

Write \[ U_a:=\{2a,3a,4a,6a,8a,12a\}. \] Inside $T_a$ we have the exact identities \[ \frac1{2a}=\frac1{3a}+\frac1{6a}, \qquad \frac1{3a}=\frac1{4a}+\frac1{12a}, \qquad \frac1{4a}=\frac1{6a}+\frac1{12a}, \] and also \[ \frac1{6a}=\frac1{8a}+\frac1{24a}, \qquad \frac1{8a}=\frac1{12a}+\frac1{24a}, \qquad \frac1{2a}=\frac1{3a}+\frac1{8a}+\frac1{24a}. \]

Step 2: disjointness.

Lemma 1. As $a$ ranges over $\mathcal I$, the sets $T_a$ are pairwise disjoint.

Proof. For $a\in\mathcal I$ we have \[ v_2(a)\equiv 0\ (\mathrm{mod}\ 4),\qquad v_3(a)\equiv 0\ (\mathrm{mod}\ 2). \] If $x\in T_a$, then $x=ca$ for some \[ c\in\{2,3,4,6,8,12,24\}. \] Therefore \[ \left(v_2(x)\bmod 4,\ v_3(x)\bmod 2\right) = \left(v_2(c)\bmod 4,\ v_3(c)\bmod 2\right). \] The seven multipliers give the seven distinct residue pairs \[ (1,0),\ (0,1),\ (2,0),\ (1,1),\ (3,0),\ (2,1),\ (3,1). \] Hence the residue pair determines the multiplier $c$, and then $a=x/c$ is uniquely determined. So no integer can belong to two different blocks $T_a$.

Step 3: counting the admissible $a$.

Let \[ I(X):=\#\{a\le X:\ a\in\mathcal I\}. \]

Lemma 2. As $X\to\infty$, \[ I(X)=\frac25 X+o(X). \]

Proof. Write every $a\in\mathcal I$ uniquely as $a=16^b9^cd$ with $(d,6)=1$. If \[ C(Y):=\#\{d\le Y:\ (d,6)=1\}, \] then \[ C(Y)=\frac13 Y+O(1). \] Therefore \[ I(X)=\sum_{b,c\ge 0} C\!\left(\frac{X}{16^b9^c}\right) =\sum_{b,c\ge 0}\left(\frac13\cdot \frac{X}{16^b9^c}+O(1)\right). \] Only $O((\log X)^2)$ pairs $(b,c)$ satisfy $16^b9^c\le X$, so the total error is $o(X)$. The main term is \[ \frac{X}{3}\left(\sum_{b\ge 0}16^{-b}\right)\left(\sum_{c\ge 0}9^{-c}\right) = \frac{X}{3}\cdot \frac{16}{15}\cdot \frac98 = \frac25 X. \] Hence \[ I(X)=\frac25 X+o(X). \]

Step 4: local omission lemmas.

Lemma 3. If $a\le N/12$, then any admissible set $A\subseteq \{1,\ldots,N\}$ omits at least $2$ elements of $U_a$.

Proof. Assume for contradiction that $A$ omits at most one element of $U_a$. Then exactly one of the following happens.

• If the missing element is $2a$, $6a$, or $8a$, then $3a,4a,12a\in A$, and \[ \frac1{3a}=\frac1{4a}+\frac1{12a} \] is a forbidden relation.
• If the missing element is $3a$, then $4a,6a,12a\in A$, and \[ \frac1{4a}=\frac1{6a}+\frac1{12a} \] is forbidden.
• If the missing element is $4a$ or $12a$, then $2a,3a,6a\in A$, and \[ \frac1{2a}=\frac1{3a}+\frac1{6a} \] is forbidden.

All cases contradict admissibility, so at least two elements of $U_a$ are omitted.

Lemma 4. If $a\le N/24$, then any admissible set $A\subseteq \{1,\ldots,N\}$ omits at least $3$ elements of $T_a$.

Proof. Suppose instead that at most two elements of $T_a$ are omitted.

If $24a\notin A$, then among the six elements of $U_a$ at most one is missing, contradicting Lemma 3.

So $24a\in A$. Then exactly two elements of $U_a$ are missing.

Now consider whether $8a$ lies in $A$.

• If $8a\notin A$, then four of the five elements \[ 2a,3a,4a,6a,12a \] belong to $A$. Any such $4$-subset contains one of the forbidden triples \[ \{2a,3a,6a\},\qquad \{3a,4a,12a\},\qquad \{4a,6a,12a\}, \] giving a contradiction.
• If $8a\in A$, then to avoid \[ \frac1{6a}=\frac1{8a}+\frac1{24a} \] we must have $6a\notin A$, and to avoid \[ \frac1{8a}=\frac1{12a}+\frac1{24a} \] we must also have $12a\notin A$. Since only two elements of $U_a$ are missing, this forces \[ 2a,3a,4a,8a,24a\in A. \] But then \[ \frac1{2a}=\frac1{3a}+\frac1{8a}+\frac1{24a} \] is a forbidden relation, again a contradiction.

Therefore at least three elements of $T_a$ are omitted.

Lemma 5. If $N/12<a\le N/6$, then any admissible set $A\subseteq \{1,\ldots,N\}$ omits at least one element of $T_a$.

Proof. In this range we still have $2a,3a,6a\le N$. If all three belonged to $A$, then \[ \frac1{2a}=\frac1{3a}+\frac1{6a} \] would be a forbidden relation. Hence at least one of $2a,3a,6a$ is missing, so at least one element of $T_a$ is missing.

Step 5: global counting.

Let $A\subseteq\{1,\ldots,N\}$ be admissible. Because the blocks $T_a$ are pairwise disjoint, omissions forced by different $a\in\mathcal I$ are distinct.

Therefore the number of omitted elements is at least \[ 3I(N/24)+2\left(I(N/12)-I(N/24)\right)+\left(I(N/6)-I(N/12)\right). \] This simplifies to \[ I(N/24)+I(N/12)+I(N/6). \] Using Lemma 2 three times, \[ I(N/24)+I(N/12)+I(N/6) = \frac25\left(\frac{N}{24}+\frac{N}{12}+\frac{N}{6}\right)+o(N) = \frac{7}{60}N+o(N). \] Hence \[ |A|\le N-\frac{7}{60}N+o(N) = \left(\frac{53}{60}+o(1)\right)N. \]

So we obtain the improved upper bound

Theorem 6 (Round-2 improvement). \[ f(N)\le \left(\frac{53}{60}+o(1)\right)N. \]

Step 6: extending the exact computation.

Round 1 computed $f(N)$ exactly for $N\le 15$. I extended this to $N\le 26$ by exhaustive search over all subsets of $\{1,\ldots,N\}$, with forbidden hyperedges given by all exact identities \[ \frac1a=\frac1{b_1}+\cdots+\frac1{b_k} \] among distinct integers in $\{1,\ldots,N\}$.

The resulting exact values are \[ \begin{array}{c|cccccccccccccccccccccccccc} N &1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19&20&21&22&23&24&25&26\\ \hline f(N) &1&2&3&4&5&5&6&7&8&9&10&10&11&12&12&13&14&15&16&16&17&18&19&19&20&21 \end{array} \]

6) ADVERSARIAL VERIFICATION

• Disjointness check. The residue-pair argument determines the multiplier uniquely, so different blocks really are disjoint.
• Local omission check. Lemma 4 is the delicate point. The proof splits into the only two possible cases: $8a\in A$ or $8a\notin A$. Both are fully closed.
• Counting check. Because blocks are disjoint, local omissions from different blocks cannot overlap. This is exactly what makes the global sum legitimate.
• Arithmetic check. The omitted-density constant is \[ \frac25\left(\frac1{24}+\frac1{12}+\frac1{6}\right)=\frac25\cdot\frac7{24}=\frac7{60}, \] so the surviving-density constant is indeed \[ 1-\frac7{60}=\frac{53}{60}. \]
• Compatibility with Round 1. Since \[ \frac{53}{60}=0.88333\ldots < 0.892857\ldots=\frac{25}{28}, \] the new bound is a genuine improvement over the Round-1 result.

7) FINAL (EXACTLY ONE)

UNRESOLVED (BUT STRICTLY ADVANCED).

Round 2 proves the stronger upper bound \[ f(N)\le \left(\frac{53}{60}+o(1)\right)N, \] improving the Round-1 constant $\frac{25}{28}$, and extends the exact computation of $f(N)$ from $N\le 15$ to $N\le 26$.

The original Erdős problem remains open, because there is still a large gap between the lower bound $f(N)\ge N/2$ and the new upper bound $f(N)\le (53/60+o(1))N$.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 58%

9) REFERENCES

1. T. F. Bloom, Erdős Problem #301, erdosproblems.com/301, accessed 2026-03-07.
2. The Round-1 writeup for the previously reconstructed $25/28$ argument of van Doorn.
3. The exact values for $f(N)$ up to $26$ are from the exhaustive computation carried out in this round.

Erdős Problem #301: independent continuation

1) TARGET AND SOURCE AUDIT

All supplied versions considered: 301.tex. The supplied disjoint-block proof yields $f(N)\le(53/60+o(1))N$. I enlarge the block and obtain the rigorously reproducible local improvement $349/403$. This is an improvement over the supplied argument, not a claim of a new literature record.

2) WORK

Choose block origins $d$ with $v_2(d)\equiv0\pmod5$ and $v_3(d)\equiv0\pmod3$. Their density is \[ \delta={1/3\over(1-2^{-5})(1-3^{-3})}={144\over403}. \] This follows by writing $d=32^u27^v w$ with $(w,6)=1$ and summing the convergent geometric densities; truncation leaves $o(X)$ error in the counting function. The sets $dT$ are disjoint: the valuations modulo $(5,3)$ determine the multiplier in $T$, and then determine $d$.

By $1$, an additional omission is forced at each cutoff multiplier $6,12,18,36,48,72,144$. Summing distinct omissions gives \[ N-f(N)\ge\left({144\over403}\left({1\over6}+{1\over12}+{1\over18}+{1\over36}+{1\over48}+{1\over72}+{1\over144}\right)+o(1)\right)N =\left({54\over403}+o(1)\right)N. \] Hence $f(N)\le(349/403+o(1))N$, strictly below $53/60$.

3) ADVERSARIAL VERIFICATION

4) FINAL

5) SOURCES CHECKED

6) COMPLETION ESTIMATE

Erdős Problem #301

1. FORMAL RESTATEMENT

The prompt contains a typographical issue: it states "there are no solutions to $\frac1a\neq \frac1{b_1}+\cdots+\frac1{b_k}$"; this would be trivial because inequalities almost always hold. The intended statement (consistent with the rest of the prompt) is that there are no solutions to the equality \[ \frac1a=\frac1{b_1}+\cdots+\frac1{b_k} \] with distinct $a,b_1,\dots,b_k\in A$.

Definition. Let $f(N)$ be the maximum size of a subset $A\subseteq\{1,2,\dots,N\}$ such that there do not exist distinct $a,b_1,\dots,b_k\in A$ with \[ \frac1a=\sum_{i=1}^k \frac1{b_i} \qquad (k\ge 1). \]

Goal. Estimate $f(N)$ as $N\to\infty$, and in particular decide whether $f(N)=(\tfrac12+o(1))N$.

2. QUICK LITERATURE/CONTEXT CHECK (only if browsing is available)

The problem page records:

• The easy lower bound $f(N)\ge \lfloor N/2\rfloor$, achieved by $A=(N/2,N]\cap\mathbb{N}$.
• van Doorn's elementary upper bound \[ f(N)\le \left(25/28+o(1)\right)N. \]
• Cambie--van Doorn note that if one allows the $b_i$ to repeat (i.e. non-distinct $b_i$), then the maximum size drops to at most $N/2$ (a divisibility/pigeonhole threshold).

3. ATTACK PLAN

1. Reconstruct van Doorn's argument in full detail: define disjoint "forbidden configuration" blocks $S_a$ and show each block forces omissions from $A$.
2. Count how many such blocks exist up to $N/6$ to obtain a density loss of $3/28$.
3. Compute small $f(N)$ for tiny $N$ by brute force to sanity-check the scale.

4. WORK

4.1 The block sets $S_a$ and why they force omissions

For $a\in\mathbb{N}$ define \[ S_a:=\{2a,3a,4a,6a,12a\}\cap[1,N]. \] We will only use $a\le N/6$, so that $2a,3a,4a,6a\le N$.

The key observation is that there are short identities among the reciprocals of these multiples: \begin{equation} \label{wsref-0-65-71-3a-73-68-6f-72-74-69-64-65-6e-74-69-74-69-65-73} \frac{1}{2a}=\frac{1}{3a}+\frac{1}{6a},\qquad \frac{1}{3a}=\frac{1}{4a}+\frac{1}{12a},\qquad \frac{1}{4a}=\frac{1}{6a}+\frac{1}{12a}. \end{equation}

4.2 A disjoint family of blocks

Let \[ \mathcal{I}:=\{a=8^b 9^c d:\ b,c\ge0,\ \gcd(d,6)=1\}. \] Equivalently, $a\in\mathcal{I}$ iff $v_2(a)\equiv0\pmod3$ and $v_3(a)\equiv0\pmod2$.

4.3 Counting how many blocks exist

Let \[ I(X):=\#\{a\le X: a\in\mathcal{I}\}. \] We can count $I(X)$ with an elementary inclusion-by-parameters argument.

Let $C(Y):=\#\{d\le Y: \gcd(d,6)=1\}$. Since among every $6$ consecutive integers exactly $2$ are coprime to $6$, we have \[ C(Y)=\frac13 Y+O(1). \] Then \[ I(X)=\sum_{b\ge0}\sum_{c\ge0} C\left(\frac{X}{8^b 9^c}\right) =\sum_{b,c\ge0}\left(\frac13\cdot \frac{X}{8^b9^c}+O(1)\right). \] The error term sums over only $O(\log X)$ many pairs $(b,c)$ with $8^b9^c\le X$, hence contributes $O(\log X)=o(X)$. The main term factors: \[ \frac{X}{3}\left(\sum_{b\ge0}8^{-b}\right)\left(\sum_{c\ge0}9^{-c}\right) =\frac{X}{3}\cdot \frac{1}{1-1/8}\cdot\frac{1}{1-1/9} =\frac{X}{3}\cdot\frac{8}{7}\cdot\frac{9}{8} =\frac{3}{7}X. \] So \begin{equation} \label{wsref-0-65-71-3a-49-78} I(X)=\frac{3}{7}X+o(X). \end{equation}

4.4 Concluding the $25/28$ bound

By Lemma Lemma (Disjointness), omissions forced by different $a\in\mathcal{I}$ correspond to distinct missing elements of $A$.

Let $A\subseteq\{1,\dots,N\}$ have no forbidden solutions. Consider $a\in\mathcal{I}\cap[1,N/6]$.

• If $a\le N/12$, Lemma Lemma (Forced omissions in each block)$1$ forces at least $2$ omissions from $S_a$.
• If $N/12<a\le N/6$, Lemma Lemma (Forced omissions in each block)$2$ forces at least $1$ omission from $S_a$.

4.5 Small values (brute force for $N\le 15$)

A direct brute-force search over all subsets of $\{1,\dots,N\}$ (for $N\le15$) gives: \[ \begin{array}{c|ccccccccccccccc} N&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15\\\hline f(N)&1&2&3&4&5&5&6&7&8&9&10&10&11&12&12 \end{array} \] For example, one maximal set for $N=15$ is \[ A=\{1,2,3,4,5,7,8,9,10,11,13,14\} \] (of size $12$).

5. VERIFICATION

• Lemma Lemma (Forced omissions in each block) reduces to checking the explicit identities (eq:shortidentities) and a short case split; the logic is deterministic.
• Lemma Lemma (Disjointness) is verified by checking that each multiplier $c\in\{2,3,4,6,12\}$ gives a distinct pair $(v_2(c)\bmod3,v_3(c)\bmod2)$.
• The counting step uses only the exact density of integers coprime to $6$ and geometric series.
• The brute-force values for $f(N)$ were obtained by exhaustive search (exact rational arithmetic / subset-sum DP) for $N\le 15$.

6. FINAL (exactly ONE label and ONE sub-label)

LABEL: UNRESOLVED
SUBLABEL: (PARTIAL RESULTS)

• What I proved here: a complete proof of the upper bound $f(N)\le (25/28+o(1))N$ following the outlined block method.
• What remains: determine the correct asymptotic size of $f(N)$ (in particular whether it is $(1/2+o(1))N$ or strictly larger), and close the gap between the lower bound $\ge N/2$ and the proven upper bound $\le (25/28+o(1))N$.
• Potential next steps: build larger explicit constructions than $(N/2,N]$ by including carefully chosen small numbers while excluding those that complete short Egyptian identities, and/or strengthen the block method by using more identities to force a larger density of omissions.

7. COMPLETION ESTIMATE

I would rate this as 50% complete: the advertised $25/28$ upper bound is fully proved, but the main asymptotic question is not settled.