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

Erdős problem #50 — wave 7b report

Access date: 2026-07-27 UTC.

Claim labels used throughout:

(a) elementary-rigorous: proved in this report from elementary facts.
(b) rigorous-modulo-named-theorem: the dependence is named explicitly.
(c) plausible/structural-unverified: a reduction, search miss, or diagnosis that is not itself a theorem.
(d) computational-only: established by the supplied finite computation, not promoted to an infinite theorem.

0. Mandatory live-page gate

(d; direct page transcription) I fetched the live page through the Bright Data browser path, not datacenter curl. At access time the page showed:

OPEN - $250;
0 comments on this problem;
0 claimed proofs for this problem;
Interested in collaborating None;
Currently working on this problem None;
every other worker/formalisation-interest marker shown on the page was None;
the one listed known result was: “Erdős [Er95] could prove the distribution

function is purely singular.”

Thus the mandatory stop condition did not trigger.

Verbatim live statement

Schoenberg proved that for every $c\in[0,1]$ the density of \[ > \{n\in\mathbb N:\phi(n)<cn\} > \] exists. Let this density be denoted by $f(c)$. Is it true that there are no $x$ such that $f'(x)$ exists and is positive?

Live source: Erdős Problems #50, with its LaTeX source.

1. Outcome

(b) Main partial theorem proved below. There is a dense set $\mathcal S\subset(0,1)$, of cardinality continuum and consisting entirely of irrational limits generated by an explicit recursive binary construction, such that

\limsup_{h\downarrow0}\frac{f(x+h)-f(x)}h=+\infty \qquad(x\in\mathcal S).

Consequently $f$ has no finite positive derivative at any $x\in\mathcal S$. The named inputs are Schoenberg's continuity theorem, Bertrand's postulate, and the lower-bound half of Mertens's prime-product theorem. The limiting Euler-product representation is otherwise derived below from CRT plus a summable tail.

(b) Concrete point. Put $p_1=3$, $Q_k=p_1\cdots p_k$, and let $p_{k+1}$ be the least prime strictly larger than $Q_k^2$. Then

x_0:=\prod_{k\ge1}\left(1-\frac1{p_k}\right)

is irrational and has infinite upper right Dini derivative as above.

(b; numerical endpoints independently checked under (d)) The checker recomputes

\[ (p_1,p_2,p_3,p_4)=(3,11,1091,1296216011) \]

and gives the certified rational enclosure

\begin{split} 0.6055050963303562347352374259555010341886043447949594679 &<x_0\\ &<0.6055050963303562347352374263725402715451782744597739003. \end{split}

The enclosure width is $4.1703923735\ldots\times10^{-28}$.

(c) This does not settle #50. It produces an explicit structured exceptional set in this report where a finite derivative is impossible; it does not control every point in the remaining null exceptional set on which a positive finite derivative could conceivably occur. No novelty claim relative to all unpublished work is made.

2. Primary-source audit

(b; source verified) Schoenberg's 1928 paper proves existence of the

limiting distribution in the live statement: I. J. Schoenberg, Über die asymptotische Verteilung reeller Zahlen mod 1, Math. Z. 28 (1928), 171–199, DOI 10.1007/BF01181156, EuDML record/full text. His 1936 sequel is On asymptotic distributions of arithmetical functions, Trans. AMS 39 (1936), 315–330.

(b; source verified) Erdős's 1939 paper proves pure singularity for the

relevant additive function $\log(\varphi(n)/n)$: P. Erdős, On the smoothness of the asymptotic distribution of additive arithmetical functions, Amer. J. Math. 61 (1939), 722–725, primary PDF. The proof of singularity is on p. 725. This gives $f'=0$ almost everywhere but says nothing uniform about the exceptional null set.

(b; source verified) Erdős's Theorem 3 in

Some remarks about additive and multiplicative functions, Bull. AMS 52 (1946), 527–537, primary PDF, gives the endpoint order \[ 1-f(1-\varepsilon)\sim\frac{e^{-\gamma}}{\log(1/\varepsilon)}. \] The proof below needs only the weaker lower bound $1-f(1-\varepsilon)\gg1/\log(1/\varepsilon)$, which is reproved from Mertens's theorem.

(b; source verified) Erdős's 1974 paper

On the distribution of numbers of the form $\sigma(n)/n$ and on some related questions, Pacific J. Math. 52 (1974), 59–65, publisher PDF, records pure singularity and the global concentration estimate; it says the analogous estimates hold with $\sigma(n)/n$ replaced by $\varphi(n)/n$.

(d; source verified by direct inspection) The exact original formulation of this problem is

on journal p. 171 of P. Erdős, Some of my favourite problems in number theory, combinatorics, and geometry, Resenhas 2 (1995), 165–186, journal record and DOI, primary PDF. Erdős explicitly asks whether the function can have a “finite positive derivative” and offers 250 dollars.

(b; source verified) V. Toulmonde,

Module de continuité de la fonction de répartition de $\varphi(n)/n$, Acta Arith. 121 (2006), 367–402, DOI/journal page, primary PDF, already proves the following strong result. If \[ E=\left\{\frac{\varphi(n)}n:n\ge1\right\},\qquad K(t)=\sum_{\varphi(n)/n=t}\frac1n, \] then for fixed $t\in E$, \[ f(t)-f((1-\varepsilon)t) \sim K(t)\frac{e^{-\gamma}}{\log(1/\varepsilon)}. \] Hence the left derivative is $+\infty$ at every $t\in E$. The paper's Lemmas 1–4 also contain the unique finite-prime representation and the cylinder lower bound used below.

(b; source verified) G. Tenenbaum and V. Toulmonde,

Sur le comportement local de la répartition de l'indicatrice d'Euler, Funct. Approx. Comment. Math. 35 (2006), 321–338, DOI 10.7169/facm/1229442631, author PDF, explicitly says the local study remains incomplete and refines the expansion at 1.

(b; source verified) Toulmonde's separate paper

Sur les variations de la fonction de répartition de $\varphi(n)/n$, J. Number Theory 120 (2006), 1–12, DOI 10.1016/j.jnt.2005.10.015, studies Erdős's derivative question and proves a uniform polynomial lower bound for right increments. Its abstract does not claim a resolution.

(d; source verified and excluded as a false match) J.-M. Deshouillers

and M. Hassani, A note on the distribution function of $\varphi(p-1)/(p-1)$, J. Aust. Math. Soc. 93 (2012), 77–83, proves non-differentiability at a structured set for a distribution over shifted primes. It is not the distribution in #50.

(c; honest search miss) Exact-statement searches, title searches, and

forward checks from the Toulmonde papers found no primary paper claiming a complete resolution. This is not proof that none exists; the live page's current OPEN, zero-claims, zero-worker state remains the authoritative status for this run.

3. Euler-product model

For a prime $p$, put

q_p=1-\frac1p,\qquad a_p=-\log q_p,

and let $B_p$ be independent Bernoulli variables with $\Pr(B_p=1)=1/p$.

(b) Lemma 1 (probabilistic representation, modulo Schoenberg continuity). The product

X=\prod_pq_p^{B_p}

converges to a positive random variable almost surely, and the live-page distribution is

f(c)=\Pr(X<c)=\Pr(X\le c).

Proof. Since

a_p=-\log(1-1/p)\le\frac1{p-1},

\mathbb E\sum_pa_pB_p \le\sum_p\frac1{p(p-1)}<\infty.

Thus $\sum_pa_pB_p<\infty$ almost surely and $X>0$.

For any finite set of primes, CRT says that the divisibility indicators of a uniform integer have limiting joint probabilities

\prod_p(1/p)^{b_p}(1-1/p)^{1-b_p}.

The expected logarithmic contribution from primes $>y$ is at most $\sum_{p>y}1/(p(p-1))\to0$, so Markov's inequality makes the truncation uniform in the limiting-density calculation. Hence the limiting law is the law of $X$. Schoenberg's continuity removes the distinction between $<$ and $\le$. $\square$

4. Two lower-bound lemmas

Let

H(\eta):=1-f(1-\eta)=\Pr(X>1-\eta).

(b) Lemma 2 (elementary endpoint lower bound, modulo Mertens). There are constants $c>0$ and $\eta_0>0$ such that

H(\eta)\ge\frac{c}{\log(1/\eta)} \qquad(0<\eta<\eta_0).

Proof. Let $y=\lceil2/\eta\rceil$. Require $B_p=0$ for every $p\le y$. This event has probability

M(y)=\prod_{p\le y}\left(1-\frac1p\right).

For the independent tail

Z_y=\sum_{p>y}a_pB_p

we have

\mathbb EZ_y\le \sum_{p>y}\frac1{p(p-1)} \le\sum_{n>y}\frac1{n(n-1)}=\frac1y.

Markov gives $\Pr(Z_y\ge\eta)\le1/(y\eta)\le1/2$. On the remaining event, $X=e^{-Z_y}>e^{-\eta}>1-\eta$. Independence therefore gives

H(\eta)\ge\frac12M(y).

Mertens's product theorem, $M(y)\sim e^{-\gamma}/\log y$, proves the claim. $\square$

For a finite prime set $A$, write

t_A=\prod_{p\in A}q_p,\quad Q_A=\prod_{p\in A}p,\quad P_A=\prod_{p\in A}(p-1),\quad K_A=\frac1{P_A}.

(a) Lemma 3 (cylinder spike). If $0<\eta\le\min_{p\in A}1/p$, then

f(t_A)-f((1-\eta)t_A)\ge K_AH(\eta). \tag{1}

Proof. Let $Y_A=\prod_{p\notin A}q_p^{B_p}$. If $X>1-\eta$, then every $B_p$, $p\in A$, must be zero, since otherwise $X\le q_p\le1-\eta$. Hence

H(\eta)=t_A\,\Pr(Y_A>1-\eta),

because the probability that all $B_p=0$ on $A$ is $t_A$. On the other hand, the event that all $B_p=1$ on $A$ and $Y_A>1-\eta$ lies inside $(t_A(1-\eta),t_A]$, and its probability is

\frac1{Q_A}\Pr(Y_A>1-\eta) =\frac{H(\eta)}{Q_At_A} =\frac{H(\eta)}{P_A}.

This is (1). $\square$

(b) Known comparison. Combining (1) with Erdős's sharp endpoint asymptotic already shows the infinite left derivative at every $t_A\in E$. Toulmonde's 2006 theorem gives the matching asymptotic, not merely this lower bound.

5. An explicit irrational obstruction

Define

p_1=3,\qquad Q_k=\prod_{i\le k}p_i,\qquad p_{k+1}=\min\{p\text{ prime}:p>Q_k^2\},

t_k=\prod_{i\le k}\left(1-\frac1{p_i}\right),\qquad x_0=\lim_{k\to\infty}t_k.

(b) Proposition 4. The number $x_0$ is positive and irrational, and

\limsup_{h\downarrow0}\frac{f(x_0+h)-f(x_0)}h=+\infty.

Proof.

Bertrand's postulate gives

\[ Q_k^2<p_{k+1}<2Q_k^2. \tag{2} \] Also $p_{j+1}>p_j^2$, so $\sum1/p_j<\infty$ and $x_0>0$.

\[ \eta_k=1-\frac{x_0}{t_k} =1-\prod_{j>k}\left(1-\frac1{p_j}\right). \] The first omitted factor and the union bound give \[ \frac1{p_{k+1}}\le\eta_k \le\sum_{j>k}\frac1{p_j}<\frac2{p_{k+1}}. \] With (2), \[ \frac1{2Q_k^2}<\eta_k<\frac2{Q_k^2}. \tag{3} \]

The rational $t_k$ has denominator dividing $Q_k$, while

$0<t_k-x_0=t_k\eta_k<2/Q_k^2$. If $x_0=a/b$ were rational, then $t_k\ne x_0$ would imply \[ |t_k-x_0|\ge\frac1{bQ_k}, \] contradicting the preceding upper bound for large $k$. Thus $x_0$ is irrational.

Let $P_k=\prod_{i\le k}(p_i-1)$. Then $P_k<Q_k$, so

$K_k=1/P_k>1/Q_k$. The upper bound in (3) is at most $\min_{i\le k}1/p_i$, so Lemmas 2 and 3 apply: \[ \frac{f(t_k)-f(x_0)}{t_k-x_0} \ge \frac{cK_k}{t_k\eta_k\log(1/\eta_k)}. \] From (3), $t_k\le1$, and $K_k>1/Q_k$, \[ \frac{f(t_k)-f(x_0)}{t_k-x_0} \ge \frac{cQ_k}{2\log(2Q_k^2)} \longrightarrow+\infty. \] Since $t_k-x_0\downarrow0$, this is the asserted upper right Dini derivative. $\square$

6. Dense continuum version

(b) Lemma 5 (modulo Mertens, or equivalently Euler's divergence of prime reciprocals). The finite products

E=\left\{\prod_{p\in A}(1-1/p):A\text{ a finite prime set}\right\}

are dense in $(0,1)$.

Proof. The numbers $a_p=-\log(1-1/p)$ tend to zero and have divergent sum because Mertens's product theorem implies $\prod_{p\le y}(1-1/p)\to0$. Given $L>0$ and an error $\delta>0$, start beyond a prime for which $a_p<\delta$, and add consecutive $a_p$'s until their sum first exceeds $L$. The overshoot is $<\delta$. Exponentiate with a minus sign. $\square$

(b) Proposition 6. The points in Proposition 4 may be chosen to form a dense continuum $\mathcal S$ of irrationals.

Proof. Start with any finite seed set $A$, its product $t_0$, and a large integer $M$ exceeding all seed primes. For each infinite bit string $\omega=(\omega_1,\omega_2,\ldots)$, choose:

$p_1$ as the least prime $>M$ if $\omega_1=0$, or the least prime

$>4M$ if $\omega_1=1$;

after $p_1,\ldots,p_k$, put

$Q_k=(\prod_{q\in A}q)(\prod_{i\le k}p_i)$, and choose $p_{k+1}$ as the least prime $>Q_k^2$ for bit 0, or the least prime $>4Q_k^2$ for bit 1.

Bertrand places the two choices respectively in

(Q_k^2,2Q_k^2)\quad\text{and}\quad(4Q_k^2,8Q_k^2).

The proof of Proposition 4, with

\frac1{8Q_k^2}<\eta_k<\frac2{Q_k^2},

works unchanged and makes every limit irrational with infinite upper right Dini derivative.

The bit-string map is injective. At its first split after a common $Q$, the bit-0 tail deficit is $>1/(2Q^2)$, whereas the bit-1 tail deficit is $<2/(4Q^2)=1/(2Q^2)$. At the initial split, the identical argument uses $M$ in place of $Q^2$: the two deficits lie respectively above and below $1/(2M)$. Hence there are continuum many limits.

Finally, given an open interval $I\subset(0,1)$, use Lemma 5 to choose $t_0\in E\cap I$, and then choose $M$ so large that the total future decrement $<2/M$ keeps every resulting limit inside $I$. Thus the union of these continuum families is dense. $\square$

7. Independent checker and exact output

Standalone verifier: runs/erdos50_wave7b_verify.py.

Run command:

python runs/erdos50_wave7b_verify.py

Key lines from the observed terminal output (the executable also prints the two exact rational enclosure endpoints):

explicit all-zero path
 k | p_k        | Q_k            | t_k=prod(1-1/p)       | K(t_k)
 1 | 3          | 3              | 2/3                    | 1/2
 2 | 11         | 33             | 20/33                  | 1/20
 3 | 1091       | 36003          | 21800/36003            | 1/21800
 4 | 1296216011 | 46667665044033 | 28257509018000/46667665044033 | 1/28257509018000

exact four-stage enclosure for x_0
lower decimal = 0.6055050963303562347352374259555010341886043447949594679254273662051248
upper decimal = 0.6055050963303562347352374263725402715451782744597739002740422247180453
width = 4.170392373565739296648144323486148585129204514754755901586056880084122E-28

finite Euler product: 1024 distinct subset products; exact probabilities sum to 1

first two binary branch levels
bits | previous Q | chosen prime
   0 |          3 | 11
   1 |          3 | 37
  00 |         33 | 1091
  01 |         33 | 4357
  10 |        111 | 12323
  11 |        111 | 49297

cost estimate: pi(10000) = 1229 ; balanced tables have 2^614 and 2^615 states; smaller table > 10^174 core-hours at 10^7 states/core-second

VERIFIED: all exact arithmetic and finite structural checks passed.

(d) What the script certifies. It uses standard-library trial division, not SymPy or a prime table; exactly checks the four displayed least primes, the rational identity

\frac{\Pr(B_p=1\ \forall p\in A)} {\Pr(B_p=0\ \forall p\in A)} =\frac1{\prod_{p\in A}(p-1)}=K_A,

all $2^{10}=1024$ distinct products and probabilities for the first ten primes, the exact enclosure, and the first binary splits. It does not pretend to computationally prove Mertens or the infinite limiting step.

The compact mathematical core is below; the standalone file additionally formats and asserts every displayed rational value and cost estimate.

#!/usr/bin/env python3
from decimal import Decimal, getcontext
from fractions import Fraction
from itertools import product
from math import isqrt

def is_prime(n):
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2
    d = 3
    while d <= isqrt(n):
        if n % d == 0:
            return False
        d += 2
    return True

def next_prime(n):
    q = n + 1
    if q <= 2:
        return 2
    if q % 2 == 0:
        q += 1
    while not is_prime(q):
        q += 2
    return q

def dec(x, digits=70):
    getcontext().prec = digits
    return str(Decimal(x.numerator) / Decimal(x.denominator))

def explicit_path():
    ps = [3]
    while len(ps) < 4:
        Q = 1
        for p in ps:
            Q *= p
        ps.append(next_prime(Q * Q))
    assert ps == [3, 11, 1091, 1296216011]

    Q = P = 1
    t = Fraction(1)
    for p in ps:
        Q *= p
        P *= p - 1
        t *= Fraction(p - 1, p)
        assert t == Fraction(P, Q)
        assert Fraction(1, Q) / t == Fraction(1, P)

    lo = t * (1 - Fraction(2, Q * Q))
    hi = t * (1 - Fraction(1, 2 * Q * Q))
    assert Q == 46667665044033
    assert P == 28257509018000
    assert hi - lo < Fraction(1, 10**27)
    print(ps)
    print(dec(lo))
    print(dec(hi))
    return lo, hi

def finite_model():
    ps = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
    law = {}
    for bits in product((0, 1), repeat=len(ps)):
        x = w = Fraction(1)
        for p, bit in zip(ps, bits):
            if bit:
                x *= Fraction(p - 1, p)
                w *= Fraction(1, p)
            else:
                w *= Fraction(p - 1, p)
        assert x not in law
        law[x] = w
    assert len(law) == 1024
    assert sum(law.values(), Fraction(0)) == 1

def branch(Q, bit):
    base = Q * Q * (1 if bit == 0 else 4)
    p = next_prime(base)
    assert base < p < 2 * base
    return p

def binary_prefixes():
    level = [("", 3)]
    for _ in range(2):
        nxt = []
        for word, Q in level:
            A = Q * Q
            p0, p1 = branch(Q, 0), branch(Q, 1)
            assert Fraction(1, p0) > Fraction(1, 2 * A)
            assert Fraction(2, p1) < Fraction(1, 2 * A)
            nxt += [(word + "0", Q * p0), (word + "1", Q * p1)]
        level = nxt

if __name__ == "__main__":
    explicit_path()
    finite_model()
    binary_prefixes()
    print("VERIFIED")

8. Exact remaining wall

(c) Logical wall. The cylinder inequality (1) turns an approximation $t_A\downarrow x$ into an infinite right Dini derivative when

\frac{K_A} {((t_A-x)/t_A)\log\!\bigl(t_A/(t_A-x)\bigr)} \longrightarrow\infty. \tag{4}

The construction forces (4) by making each next prime much larger than the product of all previous primes. For an arbitrary candidate $x$, no theorem found in the audited literature supplies appropriately sided approximants $t_A$ with the needed simultaneous control of distance and $K_A=\prod_{p\in A}(p-1)^{-1}$. This weighted subset-product approximation is the exact missing arithmetic lemma for extending this particular method. It cannot hold for every $x$, because pure singularity gives derivative zero almost everywhere; a full solution would have to derive a contradiction only under the hypothesis $0<f'(x)<\infty$.

(c) Analytic wall. Conditioning on any finite prime set $A$ decomposes the law into positive scaled copies of the tail law. A finite positive derivative would require these copies to have mutually compatible local linear increments at all relevant scaled points. The known global bound $\sup_t(f(t)-f((1-\varepsilon)t))\ll1/\log(1/\varepsilon)$ is far too large after division by $\varepsilon$, and the available right-increment estimates do not provide the cancellation or uniform pointwise upper bound needed to rule out that compatibility.

(d/c) Computation wall and cost. A straightforward certified truncation at primes $p\le y$ has $2^{\pi(y)}$ subset-product cylinders (meet-in-the-middle still needs about $2^{\pi(y)/2}$). The elementary tail certificate used above is

\Pr(-\log R_y\ge h)\le\frac1{yh}.

To make this error at most $h$, it requires $y\ge h^{-2}$. Already at $h=10^{-2}$, $y=10^4$ and $\pi(y)=1229$, so a balanced meet-in-the-middle split has tables of $2^{614}$ and $2^{615}$ states; the smaller alone has $2^{614}\approx6.8\times10^{184}$ states. Even a generous throughput of $10^7$ certified states per core-second would require about $1.9\times10^{174}$ core-hours for that smaller table, before accounting for memory or sorting. I did not run such a computation; progress must use an analytic or structural lemma rather than finer brute force.

PARTIAL: Proved, modulo Schoenberg/Mertens/Bertrand, a dense continuum-sized family of irrational points generated by an explicit recursion with infinite upper-right Dini derivative; the possibility of a finite positive derivative at all remaining exceptional points stays open.

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