Erdoes #311 - working report - Erdős Problem a Day

Erdős problem #311 — wave5t report

Accessed 2026-07-26 UTC. Mathematical-claim labels used below are:

[a] elementary-rigorous;
[b] rigorous modulo the named theorem(s);
[c] plausible/structural-unverified;
[d] computational-only.

Step 0: live-page gate

I fetched the live page through the Bright Data browser, not a cached search

result. The live state was:

OPEN;
0 claimed proofs;
Currently working on this problem: None;
Interested in collaborating: None;
8 comments (the ordinary search-engine cache showed fewer and was stale);
main page last edited 16 January 2026.

Thus neither mandatory skip condition applied.

Verbatim live statement

The following is copied verbatim from the live page's LaTeX view:

> Let $\delta(N)$ be the minimal non-zero value of $\lvert 1-\sum_{n\in A}\frac{1}{n}\rvert$ as $A$ ranges over all subsets of $\{1,\ldots,N\}$. Is it true that\[\delta(N)=e^{-(c+o(1))N}\]for some constant $c\in (0,1)$?

Verbatim listed results

> It is trivial that\[\delta(N)\geq \frac{1}{[1,\ldots,N]}=e^{-(1+o(1))N},\]where $[1,\ldots,N]$ is the least common multiple of $\{1,\ldots,N\}$.

> The formulation in \cite{ErGr80} has the additional condition that $A$ contain no $S$ such that $\sum_{n\in S}\frac{1}{n}=1$, but Kovac in the comments has shown that the simpler formulation above is equivalent.

> Tang has shown that\[\delta(N) \leq \exp\left(-c\frac{N}{(\log N\log\log N)^3}\right)\]for some constant $c>0$.

The exact rational lower bound is [a]. Its asymptotic form uses

$\log\operatorname{lcm}(1,\ldots,N)=N+o(N)$, hence is [b] modulo the

prime number theorem. Tang's displayed upper bound is [b], with the

named theorem and source checked below.

All eight live comments

The comments page says explicitly that comments are not verified. Here is a

complete chronological inventory; I do not silently promote a comment to a

theorem.

1. Vjekoslav Kovac, 17 Aug 2025. He explains why the original

admissibility condition should not affect the minimum, reports an exact

brute-force table for $1\leq N\leq25$, and observes

$e^{-0.71N}\leq\delta(N)\leq e^{-0.52N}$ on $3\leq N\leq25$.

The table is [d]; it is independently reproduced by the checker here.

2. Quanyu Tang, 12 Jan 2026. Using Liu--Sawhney

arXiv:2404.07113v1, he reports [b]

\[ \delta(N)\leq \exp\!\left(-c_0\frac{N}{(\log N)^3(\log\log N)^4}\right). \]

3. Vjekoslav Kovac, 13 Jan 2026. He notes that Tang's estimate is not

far from upper bounds in problem #317 despite #317 allowing two sums.

4. Quanyu Tang, 14 Jan 2026. He reports the strengthened [b] bound

\[ \delta(N)\leq \exp\!\left(-c_0\frac{N}{(\log N)^3(\log\log N)^3}\right). \]

This is the result incorporated into the main page.

5. Will Sawin, 1 Jul 2026. He gives:

(i) a necessary congruence for equality in the trivial

$1/\operatorname{lcm}$ bound, namely that

$L_N/p$ have a common sign $\pm1\bmod p$ for all

\(N/2

(ii) a random-local-distribution heuristic [c]

\[ c=\int_0^1 h(e^{-\alpha/t})\,dt,\qquad \int_0^1e^{-\alpha/t}\frac{dt}{t}=1. \]

6. Will Sawin, 2 Jul 2026, 13:30. He records Mehtaab Sawhney's

observation that the number of distinct reciprocal subset sums is

\[ \exp\!\left(O\!\left(\frac{N\log\log N}{\log N}\right)\right)=e^{o(N)} \tag{1} \]

([b] modulo standard prime estimates), suggests from this the

anti-clustering heuristic

$\delta(N)\geq \exp(-O(N\log\log N/\log N))$ ([c]), and gives an argument that

$\delta(N)>e^{-cN}$ infinitely often for every $c>5/6$.

I audit and correct a displayed-product typo in that argument below.

7. Will Sawin, 2 Jul 2026, 15:41. Conditional on the requested

asymptotic existing, he argues [c] that

\[ c\leq C_{\rm S}:= 1-\sum_{\ell\geq1} \frac{1}{\ell(\ell+1)D_\ell},\qquad D_\ell=\left|\left\{\sum_{n\in A}\frac1n:A\subseteq[\ell]\right\}\right|, \]

and writes $C_{\rm S}\approx0.69$. The checker recomputes

$D_1,\ldots,D_{20}$ and rigorously encloses the numerical series by

\[ 0.691755087404

This verifies the decimal only; it does not certify the posted

probabilistic proof.

8. Steve Fan, 3 Jul 2026. He proposes the analogous candidate

\[ c=\int_0^1h\!\left(\frac1{1+e^{\alpha t}}\right)dt,\qquad \int_0^1\frac1{1+e^{\alpha t}}\frac{dt}{t}=1. \]

[a] As written, this cannot be correct: the integrand in the second

integral tends to $1/2$ as $t\downarrow0$, so the integral diverges

for every finite $\alpha$. Replacing $\alpha t$ by $\alpha/t$

would match the saddle point in Liu--Sawhney Theorem 1.2, where the

corresponding constants are approximately

$\alpha=0.127191$ and $c=0.631573$; that replacement is an inference,

not text present in the comment.

Primary-source literature check

1. Original source. I downloaded and visually checked page 40 of

P. Erdős and R. Graham, *Old and new problems and results in

combinatorial number theory*, Monographies de L'Enseignement

Mathématique 28 (1980):

<https://mathweb.ucsd.edu/~ronspubs/80_11_number_theory.pdf>.

The scan asks for the same exponential form and contains the additional

no-unit-subsum condition described on the live page.

2. Liu--Sawhney. arXiv:2404.07113v1 exists and is

Y. P. Liu and M. Sawhney, *On further questions regarding unit

fractions*: <https://arxiv.org/abs/2404.07113v1>.

Its Lemma 4.1 states that an $S$-smooth denominator with

$S=cN(\log N)^{-3}(\log\log N)^{-4}$ can be represented by a reciprocal

subset of $[N/16,N]$ in the required numerator range. This is exactly

the input Tang says he strengthens.

3. Tang. The primary v2 note is present in Tang's public repository:

<https://github.com/QuanyuTang/erdos-problem-311-note/blob/main/On_Erd%C5%91s_Problem_311_v2.pdf>.

Its Lemma 3.3 changes the fourth power of $\log\log N$ to a third

power, and Theorem 4.1 explicitly concludes the bound displayed on the

live page. Thus the arXiv ID and both Tang claims were checked, not

inferred from snippets.

4. An exact-title and exact-formula search found no other primary paper

addressing this $\delta(N)$. The recent Samuel Korsky paper

arXiv:2607.04157,

<https://arxiv.org/abs/2607.04157>, is a genuine new

stretched-exponential result for the adjacent multiset problem #312,

not for #311. Croot's and other Egyptian-fraction papers found by the

search concern representation/density questions and do not state a

stronger bound for this $\delta(N)$. This is an honest search miss,

not a claim that no unindexed literature exists.

Result 1: a uniform proof of equivalence of the two formulations

This removes the “small brute force verification” left in Kovac's comment.

Lemma [a]. For every $N\geq1$, the live-page minimum over all subsets

equals the original Erdős--Graham minimum over subsets containing no

reciprocal subsum equal to $1$.

Proof. For $N=1$ this is immediate. For $N\geq2$, let

\[ s_1=2,\qquad s_{j+1}=s_j(s_j-1)+1 \quad(2,3,7,43,1807,\ldots). \]

If \(s_k\leq N \[ \sum_{j=1}^k\frac1{s_j}=1-\frac1{s_{k+1}-1}. \tag{3} \]

The sum is below $1$, so its denominator set is admissible, and since

$N\leq s_{k+1}-1$, its error is at most $1/N$.

On the other hand, if a set $B\subseteq[N]$ is nonadmissible and has

nonzero error, it contains $S\subseteq B$ with reciprocal sum $1$.

The subset must be strict (otherwise the error is zero), whence

\[ \sum_{n\in B}\frac1n-1 =\sum_{n\in B\setminus S}\frac1n\geq\frac1N. \]

Thus a nonadmissible set cannot beat the admissible candidate (3).

Minimizing over the larger and smaller families gives equality. $\square$

The same proof supplies the useful uniform elementary bound

$\delta(N)\leq1/N$, hence $\delta(N)\to0$.

Result 2: audit of Sawin's $5/6$ argument

The live comment's MathJax source writes products where division is needed.

As literally displayed, its denominator estimate would have exponent

$7/6$, not the claimed $5/6$. The following corrected argument is

rigorous.

Let $L_N=\operatorname{lcm}(1,\ldots,N)$, and choose

\[ x_N=\epsilon_N\delta(N) =\sum_{n\in A_N}\frac1n-1,\qquad \epsilon_N\in\{-1,1\}. \]

At a strict drop $\delta(N)<\delta(N-1)$, the three rationals

\[ x_N,\quad x_{N-1},\quad y=x_N-x_{N-1} \]

are nonzero. Fix a prime \(N/2

$x_N$ is divisible by $p$ exactly when $p\in A_N$; similarly for

$x_{N-1}$. If these two membership bits are $a,b$, divisibility of

the denominator of $y$ is their XOR. Among $a,b,a\mathbin{\rm XOR}b$,

there are zero or two ones, never three. Therefore, with $q(z)$ denoting

the reduced denominator and

\(P_N=\prod_{N/2 \[ q(x_N)q(x_{N-1})q(y)\mid \frac{L_N^3}{P_N}. \tag{4} \]

One of the denominators is at most $L_N/P_N^{1/3}$, so the corresponding

nonzero rational has magnitude at least $P_N^{1/3}/L_N$. If that

rational is $y$, use

$|y|\leq\delta(N)+\delta(N-1)<2\delta(N-1)$. Hence

\[ \max(\delta(N),\delta(N-1)) \geq \frac{P_N^{1/3}}{2L_N}. \tag{5} \]

There are infinitely many strict drops because $\delta(N)$ is

nonincreasing and tends to zero by (3). Finally,

$\log L_N=N+o(N)$ and

$\log P_N=N/2+o(N)$ by the prime number theorem. Thus [b]

\[ \delta(M)>e^{-cM}\quad\text{for infinitely many }M \quad\text{for every fixed }c>5/6. \]

This verifies the intended conclusion modulo the prime number theorem and

identifies the exact correction $L_N^3/P_N$ needed in the comment.

Result 3: exact computation through $N=50$

Exact reduction

Fix $N$ and put $L=L_N$. For $A\subseteq[N]$,

\[ \left|1-\sum_{n\in A}\frac1n\right| =\frac1L\left|L-\sum_{n\in A}\frac Ln\right|. \tag{6} \]

Thus the problem is an exact integer subset-sum nearest-target problem.

Term $1$ may be omitted: $\{1\}$ gives the excluded zero, and any

other subset containing $1$ has error at least $1/N$, already matched

by (3).

Split $2,\ldots,N$ into two halves, enumerate their subset sums, sort one

half, and binary-search the closest complement for every sum in the other

half. An initial $1/N$ witness allows exact pruning at

$L+L/N$: all weights are positive, so a pruned half-sum cannot occur in

any improving full sum. Exact-target duplicates are skipped because

$\delta$ is the least nonzero error. These observations prove [a]

that the algorithm exhausts every potentially optimal subset; the

resulting values are [d].

The posted $N\leq25$ table was reproduced exactly. The new extension is:

| $N$ | exact $\delta(N)$ |

|---:|---:|

| 26 | $319/608435100$ |

| 27--31 | $1/12209400$ |

| 32 | $7/125215200$ |

| 33--36 | $1/33599412$ |

| 37 | $353/79242587424$ |

| 38--40 | $1891/1188638811360$ |

| 41--43 | $17/29007778800$ |

| 44--45 | $167/348985892640$ |

| 46 | $2537/18050444111700$ |

| 47--50 | $68194627/4024733122397398320$ |

For completeness, the reproduced first 25 values are:

\[ \begin{array}{c|ccccc} N&1&2&3&4&5\\ \hline \delta(N)&1&1/2&1/6&1/12&1/30\\ N&6&7&8&9&10\\ \hline \delta(N)&1/30&1/105&1/120&1/252&1/360\\ N&11&12&13&14&15\\ \hline \delta(N)&1/2310&1/2310&1/2310&1/2772&1/2772\\ N&16&17&18&19&20\\ \hline \delta(N)&1/6160&1/30940&1/30940&5/298452&5/298452\\ N&21&22&23&24&25\\ \hline \delta(N)&11/1244880&23/17907120&1/1105104&1/1105104&1/1593900 \end{array} \]

Plateau certificate

It is unnecessary to rerun an exhaustive search at every $N$.

Monotonicity gives $\delta(a)\geq\delta(n)\geq\delta(b)$ for

$a\leq n\leq b$. For each row $[a,b]$ above, the checker:

1. verifies an exact witness of value $d$ already at $N=a$, so

$\delta(a)\leq d$;

2. exhaustively proves $\delta(b)=d$;

3. concludes [a], from monotonicity, that every value on $[a,b]$

equals $d$.

The new left-end witnesses are:

| $a$ | sign in $\sum_{n\in A}1/n=1\pm\delta(a)$ | $A$ |

|---:|:---:|:---|

| 26 | $+$ | $6,7,9,12,13,14,15,17,19,21,23,25,26$ |

| 27 | $+$ | $6,7,8,10,12,14,15,17,18,19,25,27$ |

| 32 | $-$ | $5,6,8,10,11,16,17,18,25,27,31,32$ |

| 33 | $-$ | $5,7,9,10,14,15,17,20,21,22,23,31,33$ |

| 37 | $-$ | $8,9,10,12,13,15,16,17,18,19,21,23,32,33,36,37$ |

| 38 | $-$ | $5,9,12,13,14,16,19,22,23,26,27,30,32,33,34,37,38$ |

| 41 | $+$ | $6,9,13,14,15,16,18,19,20,21,22,25,26,30,31,40,41$ |

| 44 | $-$ | $8,9,10,12,15,18,19,20,21,22,23,31,32,33,34,40,41,42,44$ |

| 46 | $-$ | $7,8,10,12,19,22,24,25,26,27,28,29,30,31,33,34,36,38,45,46$ |

| 47 | $+$ | $7,9,16,17,19,23,24,26,27,28,29,30,31,34,36,37,38,39,40,41,42,43,46,47$ |

Every displayed identity is recomputed with Python Fraction, not

floating point.

Independent checks and resource record

[d] A separate Gray-code full enumeration agrees for every

$1\leq N\leq18$.

[d] The MITM computation reproduces all 25 values in the live comment

before extending them.

[a] The script checks the Sylvester identity and $1/N$ bound for

$N\leq10000$, in addition to the symbolic proof above.

[d] The full run completed successfully in 98.25 wall seconds

(94.69 user CPU seconds), with maximum RSS 2,162,648 KiB.

[d] The heaviest endpoint $N=50$ sorted 2,872,689 retained left

half-sums and scanned 33,554,432 right half-sums.

[a+d] The finite corollary

$\delta(N)>1/L_N$ holds for every $5\leq N\leq50$.

For (2), the code exactly computes $D_\ell$ through $\ell=20$.

The elementary bound $D_\ell\geq\ell+1$ gives

\[ 0<\sum_{\ell>20}\frac1{\ell(\ell+1)D_\ell} <\sum_{\ell>20}\frac1{\ell^3}<\frac1{800}, \]

which produces the rigorous displayed enclosure.

Core checker code

The complete standalone verifier, including every plateau and witness, is

runs/erdos311_wave5t_verify.py. Its exact search core is:

def capped_subset_sums(weights, cap):
    sums = [0]
    for weight in weights:
        limit = cap - weight
        sums += [value + weight for value in sums if value <= limit]
    return sums

def mitm_delta(n):
    if n == 1:
        return Fraction(1), 1, 1
    L = math.lcm(*range(1, n + 1))
    initial_best = L // n
    cap = L + initial_best
    denominators = list(range(2, n + 1))
    split = len(denominators) // 2
    left = capped_subset_sums(
        [L // d for d in denominators[:split]], cap
    )
    right = capped_subset_sums(
        [L // d for d in denominators[split:]], cap
    )
    left.sort()
    best = initial_best
    for right_sum in right:
        wanted = L - right_sum
        lo = bisect_left(left, wanted)
        if lo < len(left):
            difference = left[lo] + right_sum - L
            if difference:
                best = min(best, difference)
            else:
                hi = bisect_right(left, wanted)
                if hi < len(left):
                    best = min(best, left[hi] + right_sum - L)
        if lo:
            difference = L - left[lo - 1] - right_sum
            if difference:
                best = min(best, difference)
    return Fraction(best, L), len(left), len(right)

Reproduce with:

python3 runs/erdos311_wave5t_verify.py

The final output from the completed run was:

[47,50] delta=68194627/4024733122397398320
halves=(2872689,33554432)
0.691755087404 < C < 0.693005087404
VERIFIED: exact delta(N) for every 1<=N<=50 (98.215s)

What remains, precisely

The finite table cannot decide the limit. The current asymptotic gap is:

[b] Tang constructs

$\delta(N)\leq\exp(-cN/(\log N\log\log N)^3)$, which does not give

a positive lower bound for $-\log\delta(N)/N$.

[b] The corrected Sawin argument controls an infinite subsequence by

exponent $5/6$, but supplies no uniform lower bound on $\delta(N)$

and no convergence.

[c] The $e^{o(N)}$ count (1) does not imply a lower bound near the

particular target $1$: subexponentially many values may still cluster

exponentially close to $1$.

A positive answer needs, at minimum, a **uniform exponential

approximation lemma**

\[ \delta(N)\leq e^{-c_1N}\quad(N\geq N_0) \]

for some $c_1>0$, plus a matching enough uniform anti-approximation and a

mechanism forcing the normalized logarithm to converge. No cited method

provides the first lemma. A negative answer along Sawhney's heuristic route

needs an anti-clustering lemma at the target $1$, for example

$\delta(N)>e^{-\varepsilon N}$ infinitely often for every

$\varepsilon>0$; merely bounding the number of distinct sums does not do

this. This is the exact mathematical wall.

The direct MITM verifier costs

$\Theta(2^{(N-1)/2})$ subset sums. Extrapolating from the measured

$N=50$ run, $N=60$ would cost about $0.9$ single-core hours and,

with Python integers, more than 60 GiB at peak; at a realistic

\$0.05--\$0.15 per core-hour the CPU alone is cheap, but a 64+ GiB instance

dominates the cost. More finite data would still not supply the missing

uniformity step, so I did not run it.

PARTIAL: Uniform elementary equivalence proof, corrected rigorous 5/6 subsequence argument, and an exact independently checked table extended from N=25 to N=50; the asymptotic question remains open at the explicit uniform exponential-approximation/anti-clustering gap.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger