Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Write A(x)=∑n≥1φ(n)xnA(x)=\sum_{n\ge1}\varphi(n)x^n, S=A(1/2)S=A(1/2), and B(x)=x/(1−x)2B(x)=x/(1-x)^2. These are the conventions of the parent sketch. All new arguments here are author-recorded and unreviewed. The obstruction concerns the literal rational sieve sums defined below, with their reduced denominators.

The exact family and its entire remainder

For a squarefree positive integer QQ define

MQ(x)=∑d∣Qμ(d)B(xd).M_Q(x)=\sum_{d\mid Q}\mu(d)B(x^d).

Then, for ∣x∣<1|x|<1,

MQ(x)=∑n≥1(n,Q)=1A(xn).(1)M_Q(x)=\sum_{\substack{n\ge1\\(n,Q)=1}}A(x^n). \tag{1}

Indeed, the coefficient of xmx^m on the left is m∑d∣(m,Q)μ(d)/dm\sum_{d\mid(m,Q)}\mu(d)/d. Write m=m0m1m=m_0m_1, where every prime factor of m0m_0 divides QQ and (m1,Q)=1(m_1,Q)=1. The coefficient on the right is $\sum_{n\mid m_1}\varphi(m/n) =\varphi(m_0)\sum_{n\mid m_1}\varphi(m_1/n) =\varphi(m_0)m_1$, the same quantity. Absolute convergence follows from φ(n)≤n\varphi(n)\le n and justifies the analytic identity.

From now on let QQ be squarefree with largest prime factor P≥5P\ge5, and let qq be the least prime not dividing QQ. The prime divisors of QQ need not be consecutive. Put

MQ=MQ(1/2)=∑d∣Qμ(d)2d(2d−1)2,RQ=MQ−S.M_Q=M_Q(1/2) =\sum_{d\mid Q}\frac{\mu(d)2^d}{(2^d-1)^2}, \qquad R_Q=M_Q-S.

The entire omitted series is positive and obeys

2−q≤RQ=∑n>1(n,Q)=1A(2−n)≤21−q(1−2−q)2.(2)2^{-q}\le R_Q =\sum_{\substack{n>1\\(n,Q)=1}} A(2^{-n}) \le\frac{2^{1-q}}{(1-2^{-q})^2}. \tag{2}

The least admissible index is qq, and A(t)≥tA(t)\ge t for 0<t<10<t<1. For the upper bound use A(t)≤t/(1−t)2A(t)\le t/(1-t)^2 and include all n≥qn\ge q. Both bounds concern the full infinite remainder in the same parameter QQ as the rational approximant.

Which denominator factors cannot cancel

Let ΨQ(X)\Psi_Q(X) denote the QQth cyclotomic polynomial and put CQ=ΨQ(2)C_Q=\Psi_Q(2). Define

GQ=CQgcd⁡(CQ,P).G_Q=\frac{C_Q}{\gcd(C_Q,P)}.

Lemma 1. Every prime factor ℓ\ell of GQG_Q satisfies ord⁡ℓ(2)=Q\operatorname{ord}_{\ell}(2)=Q. Moreover

GQ≥CQP>2φ(Q)−2P.(3)G_Q\ge\frac{C_Q}{P}>\frac{2^{\varphi(Q)-2}}P. \tag{3}

Proof. The Möbius formula for the cyclotomic value is

CQ=∏d∣Q(2d−1)μ(Q/d).(4)C_Q=\prod_{d\mid Q}(2^d-1)^{\mu(Q/d)}. \tag{4}

It is an odd positive integer. Fix an odd prime ℓ\ell and put m=ord⁡ℓ(2)m=\operatorname{ord}_{\ell}(2). If m∤Qm\nmid Q, no factor in (4) has nonzero ℓ\ell-adic valuation. If m∣Qm\mid Q, write Q=mhQ=mh. The squarefreeness of QQ makes (m,h)=1(m,h)=1, and ℓ∤m\ell\nmid m since m∣ℓ−1m\mid\ell-1. The elementary valuation formula

vℓ(2me−1)=vℓ(2m−1)+vℓ(e)(e≥1)(5)v_\ell(2^{me}-1)=v_\ell(2^m-1)+v_\ell(e) \qquad(e\ge1) \tag{5}

gives

vℓ(CQ)={vℓ(2Q−1),m=Q,1,h=ℓ,0,otherwise.(6)v_\ell(C_Q)= \begin{cases} v_\ell(2^Q-1),&m=Q,\\ 1,&h=\ell,\\ 0,&\text{otherwise}. \end{cases} \tag{6}

For completeness, substitute d=med=me in (4). The constant term in (5) sums to zero over e∣he\mid h when h>1h>1. Because hh is squarefree, the remaining sum is ∑e∣h, ℓ∣eμ(h/e)\sum_{e\mid h,\,\ell\mid e}\mu(h/e), which equals one exactly for h=ℓh=\ell. Formula (5) follows by the binomial expansion of (1+ℓau)ℓ(1+\ell^a u)^\ell for odd ℓ\ell and ℓ∤u\ell\nmid u, followed by induction and the case of an exponent coprime to ℓ\ell.

In the nonprimitive case Q=mℓQ=m\ell with m∣ℓ−1m\mid\ell-1, every other prime divisor of QQ is smaller than ℓ\ell. Thus ℓ=P\ell=P, and its exponent in CQC_Q is exactly one. Removing gcd⁡(CQ,P)\gcd(C_Q,P) therefore removes every possible nonprimitive factor.

Finally (4) and ∑d∣Qμ(Q/d)d=φ(Q)\sum_{d\mid Q}\mu(Q/d)d=\varphi(Q) imply

CQ=2φ(Q)∏d∣Q(1−2−d)μ(Q/d)>14 2φ(Q).C_Q=2^{\varphi(Q)} \prod_{d\mid Q}(1-2^{-d})^{\mu(Q/d)} >\frac14\,2^{\varphi(Q)}.

To see the strict lower bound, omit the reciprocal factors and bound the remaining product below by the product over all positive integers. Its first two factors are 1/21/2 and 3/43/4; its tail is at least 1−∑d≥32−d=3/41-\sum_{d\ge3}2^{-d}=3/4. Their product is 9/32>1/49/32>1/4. This proves (3). □\square

This proof does not invoke a primitive-divisor existence theorem. It identifies and removes the possible exceptional cyclotomic prime directly.

Lemma 2. If DQD_Q is the positive reduced denominator of MQM_Q, then

GQ2∣DQ,DQ>22φ(Q)−4P2.(7)G_Q^2\mid D_Q, \qquad D_Q>\frac{2^{2\varphi(Q)-4}}{P^2}. \tag{7}

Proof. Let ℓ∣GQ\ell\mid G_Q. Its order is QQ, so it divides 2Q−12^Q-1 and divides no 2d−12^d-1 for a proper divisor d∣Qd\mid Q. Consequently only the d=Qd=Q summand of MQM_Q has a denominator divisible by ℓ\ell. Its numerator μ(Q)2Q\mu(Q)2^Q is an ℓ\ell-adic unit. Therefore

vℓ(MQ)=−2vℓ(2Q−1)=−2vℓ(GQ).v_\ell(M_Q)=-2v_\ell(2^Q-1)=-2v_\ell(G_Q).

Adding the other ℓ\ell-integral summands cannot change that negative valuation. Multiplying the surviving prime powers proves the divisibility; (3) gives the inequality. □\square

The readily available common denominator (2Q−1)2(2^Q-1)^2 is an upper bound. It plays no role in this reduced-denominator lower bound.

The obstruction after exact denominator clearing

Theorem 3. For every squarefree QQ with largest prime factor P≥5P\ge5,

DQRQ>22φ(Q)−q−4P2≥22P−9P2.(8)D_Q R_Q> \frac{2^{2\varphi(Q)-q-4}}{P^2} \ge\frac{2^{2P-9}}{P^2}. \tag{8}

Consequently DQRQ→∞D_QR_Q\to\infty along every sequence of squarefree Q→∞Q\to\infty. For primorials the sharper lower bound DQRQ>22P−8/P2D_QR_Q>2^{2P-8}/P^2 holds.

Proof. Combine (2) and (7). If 3∤Q3\nmid Q, then q≤3q\le3 and φ(Q)≥P−1\varphi(Q)\ge P-1, whence 2φ(Q)−q−4≥2P−92\varphi(Q)-q-4\ge2P-9. If 3∣Q3\mid Q, then φ(Q)≥2(P−1)\varphi(Q)\ge2(P-1), since 33 and PP are distinct prime divisors. Bertrand's postulate gives a prime between PP and 2P2P, which cannot divide QQ, so q<2Pq<2P. Therefore 2φ(Q)−q−4>2P−82\varphi(Q)-q-4>2P-8. This case includes every primorial with P≥5P\ge5. Finally, only finitely many squarefree integers have all prime factors bounded by a fixed number, so Q→∞Q\to\infty forces P→∞P\to\infty.

For that external prime bound, the source states that for every integer n≥1n\ge1 there is a prime with n<p≤2nn<p\le2n; at n=P≥5n=P\ge5 the upper endpoint is composite, so q<2Pq<2P. See Erdős, Beweis eines Satzes von Tschebyschef (1932), pp. 197-198, section 5. Its source statement was inspected; the classical theorem is an external input, not a new proof claimed here. □\square

If S=a/bS=a/b were rational, then

bDQ(MQ−S)=bDQMQ−aDQ∈Z>0.bD_Q(M_Q-S)=bD_QM_Q-aD_Q\in\mathbb Z_{>0}.

For each fixed bb, (8) shows that these particular integers grow without bound. They cannot eventually lie strictly between zero and one. The same holds for any larger integer denominator clearing MQM_Q.

This closes only the use of MQM_Q itself as an approximation with a small denominator-cleared error, for every choice of the finite prime set. It does not compare different QQ at a prescribed reduced denominator or claim that primorials are extremal in such a comparison. It does not exclude signed combinations of different MQM_Q, subtraction of further rational terms, other sieve weights, or multiplier approximants with independent cancellation. Those operations change both the reduced denominator and the full remainder, and require new estimates.