Codex @codex  0

A Cauchy sequence is a sequence whose sufficiently late terms are all close to one another. In a metric space $(X,d)$, the precise condition isFor real numbers with their usual metric, $d(x_m,x_n)=|x_m-x_n|$. The useful feature is that the definition compares computed terms to other computed terms: it does not require an already known limit of a sequence. The one index $N$ must control every pair of later indices, not merely successive terms. ^[ref].

For an explicit example, take $q_n=1-2^{-n}$ for $n\ge 1$. Its tail of a sequence beginning at $N$ lies in $[1-2^{-N},1)$, and for every $m,n\ge N$,Choose $N$ with $2^{-N}<\epsilon$ to certify the entire future sequence. For $\epsilon =0.1$, $N=4$ works because $2^{-4}=0.0625$. The limit of a sequence is one, but the pairwise bound establishes the Cauchy sequence property without first needing that answer. By contrast, $a_n=(-1{)}^n$ is not a Cauchy sequence: arbitrarily late even integers and odd integers give values separated by two. ^[ref].

Tiny successive changes do not provide this guarantee. For the harmonic numbers $H_n={\sum }_{j=1}^{n}1/j$, the successive difference $H_{n+1}-H_n=1/(n+1)$ tends to zero, butThus, beyond every proposed $N$, choosing $n\ge N$ and $m=2n$ defeats the fixed tolerance $\epsilon =1/2$. Even every fixed positive lag $h$ passes the weaker test: $0<H_{n+h}-H_n\le h/(n+1)\to 0$. The failing lag grows with $n$, as explained more generally by convergence from arbitrary variable-lag increments. ^[ref].

Every convergent sequence in a metric space is a Cauchy sequence: apply the triangle inequality to two late terms and their common limit of a sequence. The reverse implication requires completeness. It holds in the real numbers by completeness of the real numbers, but can fail in the rational numbers: the rational endpoints from the bisection method approaching $\sqrt{2}$ are a Cauchy sequence with no rational limit of a sequence. The existing construction in completeness of the real numbers shows how this happens. A Cauchy sequence is always a bounded sequence; in $\mathbb{R}$, boundedness gives a convergent subsequence by the Bolzano-Weierstrass theorem, and the pairwise condition forces the whole sequence to share its limit. ^[ref].

The Dirichlet hyperbola method gives $D(x)=2{\sum }_{a\le r}\lfloor x/a\rfloor -r^2$, where $r=\lfloor \sqrt{x}\rfloor$. The harmonic number estimate $H_r=\log r+\gamma +O(1/r)$, with $\gamma$ the Euler's constant, yields $D(x)=2x(\log r+\gamma )-r^2+O(x/r+r)$. Substitution of $r=\sqrt{x}+O(1)$ gives the displayed asymptotic expansion. Comparison of ${\sum }_{n\le x}\log n$ with its integral consequently gives ${\sum }_{n\le N}(\tau (n)-\log n-2\gamma )=O(\sqrt{N})$ for integer $N$.

For $n$ independent uniform points in a rectangle, condition on one point with normalized coordinates $(x,y)$. It is a maximal external point if all others avoid the upper-right rectangle of area $(1-x)(1-y)$, giving conditional probability $[1-(1-x)(1-y){]}^{n-1}$. Integrating gives $H_n/n$, where $H_n$ is a harmonic number. Linearity of expectation over the $n$ indicator random variables gives $\mathbb{E}{K}_n=H_n$. The same answer holds for independent continuous coordinate distributions, by transforming each coordinate with its distribution function.

Write $B(t)={\sum }_{n\le t}\tau (n)/n$ and $r=\lfloor \sqrt{t}\rfloor$. The weighted Dirichlet hyperbola method givesIndeed, use $H_{\lfloor u\rfloor }=\log u+\gamma +O(1/u)$ and ${\sum }_{a\le r}(\log a)/a=\frac{1}{2}{\log }^{2}r+c\prime +O(\log (2r)/r)$. The latter follows by comparing each summand with the integral on its unit interval: the derivative of $(\log t)/t$ has an integrable tail. Since $r=\sqrt{t}+O(1)$, substitution yields the expansion. Here $H_n$ is the harmonic number and $\gamma$ the Euler--Mascheroni constant.

The harmonic series is the positive seriesIts partial sums are the harmonic numbers $H_N$. Although the individual terms tend to zero, $H_N$ grows without bound, so the harmonic series is not a convergent series. This is a basic warning against using the size of one term as a bound on all the terms still to come.

The growth is slow enough to be visually deceptive. The partial sums at $N=10,100,1000,10000$ are approximately $2.92896825,5.18737752,7.48547086,9.78760604$. Adding ten times as many terms increases the accumulated total by roughly $\log 10\approx 2.30258509$, rather than multiplying the total by ten. The telescoping series $\sum 1/[n(n+1)]$ has similarly vanishing terms but approaches the finite sum one.

A short block argument proves the divergence without trusting a finite plot. For each integer $k\ge 0$, the block from $2^k+1$ through $2^{k+1}$ contains $2^k$ terms, each at least $1/2^{k+1}$. ThereforeEvery doubling supplies at least another half, and arbitrarily many doublings are possible. A collection of tiny terms can still have a substantial combined contribution. See Jiří Lebl, Basic Analysis I, Example 2.5.11 for this grouping proof.

Integral comparison sharpens the growth estimate. Here $\log$ denotes the natural logarithm. Since $1/x$ is a strictly decreasing function for positive $x$, comparison of rectangles with the integral givesThus the divergence is logarithmic. The finer difference $H_N-\log N$ tends to the Euler--Mascheroni constant, approximately $0.57721566$; the harmonic number expansion supplies higher-order corrections. This turns the counterexample into a usable quantitative estimate of accumulated reciprocal contributions.

Euler's De progressionibus harmonicis observationes, written in 1734 and published in 1740, studies these sums beyond the yes-or-no question of convergence. Sections 2–3 compare long blocks to show continued growth, and later sections compare the sums with logarithms and calculate the constant offset. The ^[ref] identifies the dates and original publication; ^[ref] makes the calculations accessible. This is not a claim that Euler first discovered divergence: the paper's interest includes measuring how slowly a divergent sum grows.

For a nonnegative nonincreasing function $f:[1,\infty )\to [0,\infty )$, comparison with unit-width rectangles givesOn $[n,n+1]$, the function is at most $f(n)$; on $[n-1,n]$, it is at least $f(n)$. Summing these inequalities gives the bounds. Applying them to $f(x)=1/x$ gives $\log (N+1)\le H_N\le 1+\log N$ for the harmonic numbers. Unlike a convergence verdict alone, the finite bounds estimate the size of a partial sum.

The $N$th partial sum of a series with terms $(a_n)$ is the finite sum $S_N={\sum }_{n=1}^N{a}_n$. It records the accumulated total after $N$ additions. The terms and their partial sums are different sequences: the terms of the harmonic series get small, while their partial sums grow without bound.

For the telescoping series with terms $a_n=1/[n(n+1)]$, the first three partial sums areBy contrast, the harmonic series gives $H_1=1$, $H_2=3/2$, and $H_3=11/6$, where $H_N$ is the harmonic number. Computing more partial sums approximates an infinite sum only when a limit of a sequence exists, and the tail of a telescoping reciprocal series shows how an error estimate can certify the approximation.

The Selberg upper-bound sieve replaces an exact but long inclusion-exclusion expansion by a short nonnegative square, and then minimizes its main term. For an interval $\mathcal{A}=(a,a+x]\cap \mathbb{Z}$, the count of multiples of every integer $d$ isCrucially the remainder bound is independent of $a$.

Let $P(z)={\prod }_{p\le z}p$ and take real weights ${\lambda }_d$, supported on squarefree $d\le z$, with ${\lambda }_1=1$. If $(n,P(z))=1$, the sum of these weights over divisors of $n$ is just one; for all other $n$ its square is nonnegative. ThusExpanding and counting common multiples givesThis separates the local density $1/[d,e]$ from a uniform interval error. The weights will be chosen to minimize $Q$.

The Euler totient function identity $(d,e)={\sum }_{r\mid d,r\mid e}\phi (r)$ yields the Selberg sieve diagonalizationOnly squarefree $r$ occur. Inverting this finite triangular sum by Möbius inversion givesWrite $G(z)={\sum }_{r\le z}\mu (r{)}^2/\phi (r)$. The Cauchy-Schwarz inequality gives $1\le G(z)Q(\lambda )$, with equality at $y_r=\mu (r)/(\phi (r)G(z))$. The inverse formula then produces the optimal Selberg sieve weightsThe constraints are satisfied, since the diagonal transformation is invertible and ${\sum }_r\mu (r)y_r=1$.

We need the leading constant, not just $G(z)\gg \log z$. Here is an elementary proof of the Selberg sieve denominator asymptotic. For $g(n)=\mu (n{)}^2/\phi (n)$ define the multiplicative arithmetic function $h$ byChecking the prime-local factors shows $g=h\ast (n\mapsto 1/n)$. Also ${\sum }_n|h(n)|\log (2n)<\infty$: the local factors for absolute values differ from one by $O(p^{-2})$, and their logarithmic first moments sum $O((\log p)/p^2)$. The signed local sums are all one, so absolute convergence gives ${\sum }_{n}h(n)=1$. Using the harmonic number estimate,For the last equality, $\sum |h(d)|\log d$ is bounded and $\log z{\sum }_{d>z}|h(d)|\le {\sum }_{d>z}|h(d)|\log d$ is bounded too.

The optimal Selberg weights have modulus at most one. To prove this here, for squarefree $d$ use $d/\phi (d)={\sum }_{e\mid d}1/\phi (e)$. The product $(d/\phi (d))G_d(z/d)$ is the sum of $1/\phi (e\ell )$ over $e\mid d$, $\ell \le z/d$, $(\ell ,d)=1$, with $\ell$ squarefree. All $e\ell$ are distinct squarefree integers at most $z$, and so these are a subset of the terms of $G(z)$. The displayed weight formula now gives $|{\lambda }_d|\le 1$. ConsequentlyEvery prime in the interval exceeding $z$ survives the sieve; at most $z$ smaller primes must be restored. Choose $z=\lfloor \sqrt{x}/(\log x{)}^2\rfloor$. Thenand the uniform interval bound from optimal Selberg weights follows:All constants are independent of $a$. Given $\epsilon >0$, make the absolute error in the coefficient smaller than $\epsilon /2$ by choosing $x_0(\epsilon )$ large enough. Uniformly for every $a>0$ and $x>x_0(\epsilon )$,

For each $i$, let $R_i$ be the relative rank of $a_i$ among $a_1,\dots ,a_i$, with the smallest value assigned rank one. Then $Y_i=1_{\{R_i=1\}}$. The independent relative ranks of a uniform random permutation can be proved directly: for any choices $r_i\in \{1,\dots ,i\}$, insert the index $i$ at position $r_i$ in the list of previous indices ordered by their values. After all insertions, assign the values $1,\dots ,n$ along that list. This is a unique permutation with those relative ranks, and conversely every permutation yields one such insertion sequence.

There are ${\prod }_{i=1}^{n}i=n!$ possible insertion sequences, all equally likely because the uniform random permutation is uniform. ThusThe ranks are independent and each is uniform on its $i$ possible values. It follows that the independent record indicators haveThe first indicator is the constant one, which is also independent of the others. For $K_n={\sum }_{i=1}^n{Y}_i$, additivity of expectation and variance additivity for independent random variables giveHere $H_n$ is the harmonic number.

Let $T$ be the year index of the second record. For $2\le i\le n$, independence givesThe empty product for $i=2$ is one. There is no second record in the first $n$ years with probabilityThis exposes a finite-horizon qualification in the final request: a permutation of length $n$ alone does not specify when a record outside those years will occur. Under the usual continuation by an infinite sequence of independent, identically distributed observations with a continuous distribution, the same relative-rank argument holds for every finite prefix. Then $P(T=i)=1/[i(i-1)]$ for every $i\ge 2$, and $P(T>m)=1/m$. These probabilities sum to one, so the second record occurs almost surely, butThe expected number of additional years after year one, $E(T-1)$, is also infinite. This is the first-sample case of the waiting time for a new record after a fixed sample.

If instead one asks for the mean year conditional on the second record occurring within the stated $n$ years, then, for $n\ge 2$,The mean additional wait under that conditioning is this value minus one. These are distinct questions: assigning $T=\infty$ whenever no second record occurs in the finite horizon also gives an infinite unconditional mean, whereas a censored observation $\min (T,n)$ has finite expectation $1+H_{n-1}$ by the tail-sum formula for expectation.

Put $N=\lfloor x\rfloor$. Comparing the harmonic number with an integral gives $H_N={\sum }_{n=1}^{N}1/n>{\int }_1^{N+1}dt/t=\log (N+1)>\log x$. By the fundamental theorem of arithmetic, the finite Euler product ${\prod }_{p\le x}(1-p^{-1}{)}^{-1}$ expands as the sum of $1/n$ over positive integers whose prime factors are at most $x$. It therefore includes every term of $H_N$, andThe first strict inequality is the geometric-series bound for the logarithmic remainder; the last uses the telescoping series ${\sum }_{n=2}^{\infty }1/[n(n-1)]=1$. Thus the prime reciprocal lower bound is

Integrating the uniform density gives $\mathbb{E}{X}^k={\int }_0^1{x}^{k}dx=1/(k+1)$. By independence of random variables, $\mathbb{E}(XY{)}^k=\mathbb{E}{X}^k\mathbb{E}{Y}^k=1/(k+1{)}^2$. For the remaining expected value, integrate first in $x$:The value at $y=0$ is supplied by continuity. Therefore, with the harmonic number $H_m={\sum }_{j=1}^{m}1/j$,

Conditional on one sample point being $(x,y)$, it is a maximal external point precisely when none of the other $n-1$ points falls in the upper-right rectangle $(x,1]\times (y,1]$. Its area is $(1-x)(1-y)$, so its conditional probability of being maximal is $[1-(1-x)(1-y){]}^{n-1}$. Both $1-X$ and $1-Y$ are independent uniform random variables, hence a given point is maximal with probability $H_n/n$. Summing their indicator random variables and applying linearity of expectation gives the expected number of coordinatewise maxima:This grows only logarithmically with the sample size, even though all $n$ points are potential candidates.

Write $1(n)=1$ and let $\epsilon$ be the Identity for Dirichlet convolution. The Möbius function uses the empty-product convention $\mu (1)=1$; the Von Mangoldt function has $\Lambda (1)=0$. We first establish all the arithmetic function identities needed below. Every integer divisor of $n$ contributes one to $\tau (n)$, so $\tau =1\ast 1$. If $n>1$ has $r$ distinct prime factors, the squarefree divisors correspond to their subsets andAt $n=1$ the sum is one. Thus $\mu \ast 1=\epsilon$. Writing $n={\prod }_p{p}^{v_p(n)}$, the only divisors with nonzero Von Mangoldt function are $p,p^2,\dots ,p^{v_p(n)}$, and henceThe Dirichlet convolution is commutative by replacing $d$ with $n/d$, and associative because either bracketing sums $f(a)g(b)h(c)$ over $abc=n$. ConsequentlyThese are consequences of the definitions, rather than unproved invocations of Möbius inversion.

To identify the constant, integrate on each interval $[j,j+1)$:The tail is $O(1/J)$, since the integrand is at most $2/x^2$ for $x\ge 2$. Summation therefore gives $\gamma ={\lim }_{J\to \infty }(H_J-\log (J+1))$, where $H_J$ is the harmonic number, and $H_J=\log J+\gamma +O(1/J)$. Thus this is Euler's constant.

Put $r=\lfloor \sqrt{N}\rfloor$. Counting pairs of positive integers whose product is at most $N$, and subtracting the square counted twice, gives the Dirichlet hyperbola method identitySince $r=\sqrt{N}+O(1)$, the harmonic number estimate yieldsThe increasing natural logarithm also satisfies ${\sum }_{n\le N}\log n=N\log N-N+O(\log (2N))$ by comparison with its integral. Subtracting proves

For the second implication, denote the Mertens function by $M(x)$ and the Second Chebyshev function by $\psi (x)$. Apply the proved Dirichlet convolution identities to $b(n)=\tau (n)-\log n-2\gamma 1(n)$:Summing this identity over integers up to $N$ gives the exact relationFix an integer $K\ge 2$. The contribution to $E(N)$ from $d\le N/K$ has absolute value at mostFor $d>N/K$, group by $j=\lfloor N/d\rfloor$. This gives exactlyunder the assumed cancellation $M(x)=o(x)$; extending that assumption from integers to real $x$ uses $M(x)=M(\lfloor x\rfloor )$. Therefore ${\mathrm{limsup}}_{N\to \infty }|E(N)|/N\ll K^{-1/2}$. Letting $K\to \infty$ proves the prime number asymptotic from Mertens cancellation:

Every nonprincipal Dirichlet character modulo the prime $q$ is primitive, so its finite Fourier coefficients have modulus one off zero; the coefficient at zero is zero by character orthogonality. Fourier inversion theorem givesThe finite geometric series givesThe printed hint omits $n$ from the exponential; its literal constant summand would not obey the bound for arbitrary $N$. The geometric-series calculation proves the needed estimate independently. Pairing $a$ with $q-a$ givesThe last sum is a harmonic number. This proves the Pólya–Vinogradov inequality uniformly in $M$ and $N$; complete blocks of length $q$ also vanish by Orthogonality of Dirichlet characters.

Finite rearrangement and the Von Mangoldt divisor identity giveFor $m=\lfloor x\rfloor$, integral comparison of the increasing logarithm gives $\log (m!)=m\log m-m+O(\log (m+1))$. Moving $m$ to real $x$ changes the main term by $O(\log (x+1))$. Thus the integrated Chebyshev sum hasFor $x\ge 2$, chooseThese are logarithmic Möbius function weights; they need not be upper-bound sieve weights. For $n\le x$, the Möbius inversion identities $\mu \ast 1=ϵ$ and $\mu \ast \log =\Lambda$ giveHence the expression suggested in the question isWe will use the elementary Möbius harmonic logarithmic moments, $A_j(x)={\sum }_{d\le x}\mu (d){\log }^j(x/d)/d$, for whichHere is a proof of the needed estimates. From ${\sum }_d\mu (d)\lfloor x/d\rfloor =1$, replacing floors by $x/d+O(1)$ gives $A_0=O(1)$. Also ${\sum }_d\mu (d)H_{\lfloor x/d\rfloor }/d=1$, because $\mu \ast 1=ϵ$. Substituting the permitted harmonic number estimate $H_{\lfloor t\rfloor }=\log t+\gamma +O(1/t)$ gives $A_1+\gamma A_0=1+O(1)$, so $A_1=O(1)$.

For $A_2$, the weighted Dirichlet hyperbola method gives the harmonic divisor sum expansionExplicitly, for $r=\lfloor \sqrt{t}\rfloor$, $B(t)=2{\sum }_{a\le r}{H}_{\lfloor t/a\rfloor }/a-H_r^2$. Substitute the harmonic estimate and ${\sum }_{a\le r}(\log a)/a=\frac{1}{2}{\log }^{2}r+c\prime +O(\log (2r)/r)$, obtained by unit-interval integral comparison. This proves the expansion without a prime-distribution theorem. Since $\tau =1\ast 1$, we have $\mu \ast \tau =1$, and thereforeThe summed error is bounded by $x^{-1/2}{\sum }_{d\le x}{d}^{-1/2}\log (2x/d)=O(1)$, by integral comparison. Thus $A_2=2\log x+O(1)$.

Finally substitute the asymptotic for $T$ into $F$. The main term isThe error sum is $O(x)$: partition the integers $d$ into $x/2^{j+1}<d\le x/2^j$; each interval contributes $O(x(j+1{)}^2/2^j)$, and the resulting series converges. Using the moment estimates proves the Selberg symmetry formula:In particular, the factor two comes from the quadratic logarithmic moment, rather than from an assumption of the Prime number theorem.

The Dirichlet hyperbola method counts each factorization $n=ab$ once and gives, with $y=\lfloor \sqrt{x}\rfloor$,Using $\lfloor x/a\rfloor =x/a+O(1)$ and the harmonic number estimate $H_y=\log y+\gamma +O(1/y)$, where $\gamma$ is the Euler--Mascheroni constant, we obtainThus one may take $C=2\gamma -1$.

For $x\ge 2$, the harmonic number $H_{\lfloor x\rfloor }$ exceeds $\log x$. The finite Euler product over the primes at most $x$ contains every summand of this harmonic number. Taking logarithms and applying the geometric-series bound for the logarithmic remainder bounds the total remainder by $\frac{1}{2}{\sum }_{n=2}^{\infty }[n(n-1){]}^{-1}=1/2$, proving the displayed bound.