Wiki
Wiki

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

Updated


This proves L230 at author-recorded standing. All logarithms are natural.

Write D={n:an≠pn}D=\{n:a_n\ne p_n\}. Since DD has density zero, for every fixed η>0\eta>0 and all sufficiently large nn there is an unchanged index in each of [(1−η)n,n][(1-\eta)n,n] and [n,(1+η)n][n,(1+\eta)n]. Monotonicity and pn∼nlog⁡np_n\sim n\log n then imply an∼pna_n\sim p_n. The series converges, and for some integer B≥1B\ge1,

an≤Bnlog⁡(n+1),pn≤Bnlog⁡(n+1)(n≥1).(1)a_n\le Bn\log(n+1),\qquad p_n\le Bn\log(n+1) \quad(n\ge1). \tag{1}

We first fix BB and take its countable union at the end.

Define integer gap changes, without halving them, by

vn=(an+1−an)−(pn+1−pn),n≥1.v_n=(a_{n+1}-a_n)-(p_{n+1}-p_n),\qquad n\ge1.

Their support EE is contained in D∪{n:n+1∈D}D\cup\{n:n+1\in D\}, so ∣E∩[1,N]∣=o(N/log⁡log⁡N)|E\cap[1,N]|=o(N/\log\log N). Positivity of both sets of gaps and telescoping give, for N≥3N\ge3,

∑n=1N∣vn∣≤aN+1−a1+pN+1−p1≤6BNlog⁡N.(2)\sum_{n=1}^N|v_n| \le a_{N+1}-a_1+p_{N+1}-p_1 \le6BN\log N. \tag{2}

Fix ϵ>0\epsilon>0 and an integer N0≥16N_0\ge16, and restrict to the class with (1) and

∣E∩[1,N]∣≤ϵNlog⁡log⁡N(N≥N0).(3)|E\cap[1,N]|\le\frac{\epsilon N}{\log\log N} \quad(N\ge N_0). \tag{3}

For each fixed ϵ\epsilon, every sequence in the class with fixed BB satisfies (3) for some N0N_0.

Put M=⌈6BNlog⁡N⌉M=\lceil6BN\log N\rceil and ρN=ϵ/log⁡log⁡N\rho_N=\epsilon/\log\log N. For all sufficiently large NN, 0<ρN<1/40<\rho_N<1/4. An integer vector (v1,…,vN)(v_1,\ldots,v_N) with support of size tt has at most (Nt)\binom Nt choices of support, 2t2^t choices of signs and (Mt)\binom Mt choices of positive absolute values with sum at most MM. Thus (2)--(3) give the upper bound

∑0≤t≤⌊ρNN⌋(Nt) 2t(Mt).(4)\sum_{0\le t\le\lfloor\rho_NN\rfloor} \binom Nt\,2^t\binom Mt. \tag{4}

The summand for t=0t=0 is 11. For 1≤t≤ρNN1\le t\le\rho_NN, using M≤(6B+1)Nlog⁡NM\le(6B+1)N\log N and (ut)≤(eu/t)t\binom ut\le(eu/t)^t gives

(Nt) 2t(Mt)≤(2e2(6B+1)log⁡N (N/t)2)t.(5)\binom Nt\,2^t\binom Mt \le \left(2e^2(6B+1)\log N\,(N/t)^2\right)^t. \tag{5}

The logarithm of the right side is increasing as a function of t/Nt/N on (0,1/4](0,1/4]. It is therefore at most

NρNlog⁡2e2(6B+1)log⁡NρN2=Nϵlog⁡log⁡N(log⁡log⁡N+2log⁡log⁡log⁡N+OB,ϵ(1))=(ϵ+oB,ϵ(1))N.(6)\begin{aligned} N\rho_N\log\frac{2e^2(6B+1)\log N}{\rho_N^2} &=N\frac{\epsilon}{\log\log N} \left(\log\log N+2\log\log\log N+O_{B,\epsilon}(1)\right)\\ &=(\epsilon+o_{B,\epsilon}(1))N. \end{aligned} \tag{6}

There are at most N+1N+1 summands in (4) and finitely many possibilities for a1a_1 under (1). The initial value and vector (vn)(v_n) determine the position prefix. Thus the number of prefixes through index NN in this class is at most

exp⁡((ϵ+oB,ϵ(1))N).(7)\exp\bigl((\epsilon+o_{B,\epsilon}(1))N\bigr). \tag{7}

Each prefix determines an interval of possible series values of length at most CBNlog⁡N 2−NC_BN\log N\,2^{-N}, by (1). For any s>ϵ/log⁡2s>\epsilon/\log2, the sum of the ssth powers of these covering lengths is bounded above by

exp⁡((ϵ−slog⁡2+oB,ϵ,s(1))N)⟶0.\exp\bigl((\epsilon-s\log2+o_{B,\epsilon,s}(1))N\bigr) \longrightarrow0.

The definition of Hausdorff dimension gives a bound of ϵ/log⁡2\epsilon/\log2 for the values in the class (1), (3). Its countable union over N0N_0 includes the full class with fixed BB and the required little-oh support bound, so it has the same dimension bound. Letting ϵ↓0\epsilon\downarrow0 proves dimension zero for that class. Taking the countable union over BB proves the assertion about VV. A fixed exceptional set with the stated size bound gives a subset of VV; such a subset cannot contain an interval of positive length. □\square