Reading Eight Erdős Problems Together

The computation and its limits

The computation [36] runs the greedy rule in exact arithmetic on every reduced fraction in $(0,E]$ with $2\le q\le Q$.

First reading. At $Q=36$, $382$ of $633$ fractions are not rejected through step $160$ and $14$ are finite subsums, a share $(382+14)/633=0.6256$ close to $1/E=0.6224$. This was read as evidence that about $62\mathrm{\%}$ of rationals are subsums, hence that #257 is false. The reading is wrong. By Theorem 6.4 above the share at any fixed depth tends to $2^N{R}_N/E$ whatever the truth of #257, because fractions equidistribute over the $2^N$ intervals that survive $N$ steps.

An incorrect stopping rule. A subsequent interpretation went too far in the opposite direction, asserting that survival after about $2{\log }_{2}Q-3.3$ steps was forced. The measure-based main term for the number rejected at step $n$ is $2^{n-1}{g}_n\sum _{2\le q\le Q}\phi (q)$, asymptotically $(3Q^2/{\pi }^2)2^{n-1}{g}_n$, which is below $1$ for $n>2{\log }_{2}Q-2{\log }_2\pi$, about step $12$ at $Q=200$. A main term below $1$ does not make the actual count zero. Theorem 6.4 is a fixed-depth asymptotic, and its error $O(2^N\log Q/Q)$ does not justify an extrapolation to $N\sim 2{\log }_{2}Q$. Late rejections remain exact nonmembership certificates; the $\mathrm{12,218}$ fractions not rejected through step $60$ have only that finite-depth status. At $N=12$ the observed share is $0.62372$ against $2^{12}{R}_{12}/E=0.62245$.

An exact rejection at step $17$. The witness $189/388$, recorded in the earlier investigation’s Desk B report, contradicts the proposed stopping rule: $2{\log }_{2}388-2{\log }_2\pi$ is about $13.9$. The selected indices through step $16$ are $F=\{2,3,7,9,10,14,15,16\}$. At each skipped earlier index $n$, exact rational arithmetic gives a remainder at most $2^{-n}<R_n$, so no rejection has yet occurred. The remaining value is

Since $1/(2^k-1)=2^{-k}+4^{-k}/(1-2^{-k})$ and $1/(1-2^{-k})\le 2$ for $k\ge 1$, summing gives

At $n=17$, the exact comparison is

The same rejection occurs for $577/388=1+189/388$ by Lemma 6.9. The independent reproduction, including every earlier skipped step, is in research/experiments/sparse_interpolation/late_rejection.py. This certificate shows that deeper computation can add exclusions. It does not convert survival to any finite depth into a membership certificate.

What survives is the agreement itself. At $Q=200$ the counts at steps $1$ to $9$ are $4809$, $1470$, $600$, $268$, $132$, $66$, $32$, $8$, $6$, against $4811$, $1467$, $604$, $277$, $133$, $65$, $32$, $16$, $8$ from the measures of Lemma 6.8; steps $10$ and $11$ have none against $4$ and $2$, and step $12$ has $4$ against $1$. The late counts fluctuate more than independent events would, because rejections arrive in the families of Lemma 6.9.