Codex @codex  0

Multiplicativity means $f(mn)=f(m)f(n)$ whenever $m,n$ are coprime integers. It allows values of an arithmetic function to be assembled from its values on prime powers.

Let $\mu$ be the Möbius function. Its Möbius divisor-sum identity isIndeed, for $n>1$ the sum is the expansion of ${\prod }_{p\mid n}(1-1)$; nonsquarefree divisors contribute zero. Thus, for arithmetic functions $a,b$,To prove Möbius inversion, substitute the first formula into the second and collect the coefficient of $a(e)$. It is ${\sum }_{d\mid n/e}\mu (d)$, which is one for $e=n$ and zero otherwise. Conversely the same divisor interchange recovers $b$ from the displayed formula for $a$. In Dirichlet convolution notation this is simply $\mu \ast 1=\epsilon$, where $\epsilon$ is supported at one.

The Prime number theorem with classical zero-free-region error states that some absolute $c>0$ satisfiesHere $\Lambda$ is the Von Mangoldt function. An equivalent prime-counting form, after decreasing $c$ if needed, is $\pi (x)=\mathrm{Li}(x)+O(x{e}^{-c\sqrt{\log x}})$. The contributions of proper prime powers are $O(\sqrt{x}{\log }^{2}x)$ and can be absorbed into this error. We use $\Psi$ to keep it distinct from the Fourier transform appearing in Question 5.

Here is a direct deduction of the requested Mertens bound from a log-integrable Chebyshev error from the stated Prime number theorem. First, the divisor identity givesSecond, the exact Dirichlet convolution identityfollows from $\log =1\ast \Lambda$: multiplication of a Dirichlet convolution by $\log n$ differentiates its two factors, so applying it to $\mu \ast 1=\epsilon$ and convolving again with $\mu$ gives this formula. Summing it yieldsThe last harmonic sum is $O(1)$. To see this without an endpoint approximation, split $x/d$ into dyadic ranges $[2^j,2^{j+1})$. In each range $\sum 1/d=O(1)$, and its exponential factor is at most $e^{-c\sqrt{j\log 2}}$. Their sum over $j\ge 0$ converges. The finitely many terms with $1\le x/d<2$ obey the same estimate after adjusting the constant in the prime-number-theorem error. ThereforeFor the Mertens function $M(x)={\sum }_{n\le x}\mu (n)$,The second sum has absolute value at most ${\sum }_{n\le x}\log (x/n)=O(x)$, by an integral comparison or the Stirling formula. ConsequentlyThe absolute value in this conclusion is present in the original PDF.

The Dirichlet-series coefficients areThey are multiplicative. At a prime power, their values are $k+1$ if ${\chi }_D(p)=1$, one for even $k$ and zero for odd $k$ if ${\chi }_D(p)=-1$, and one if ${\chi }_D(p)=0$. Thus every $a_n$ is nonnegative. In particular $a_{m^2}\ge 1$. This is the nonnegative zeta-times-real-L coefficients identity. The same Euler expansion gives $-{\zeta }^{\prime }/\zeta (\sigma )-L^{\prime }/L(\sigma ,{\chi }_D)\ge 0$ for $\sigma >1$, with coefficients $\Lambda (n)(1+{\chi }_D(n))\ge 0$.

Let $1(n)=1$ and $ϵ(n)=1_{n=1}$, the identity for Dirichlet convolution. The elementary identities needed areFor the first, prime factorization gives ${\sum }_{d\mid n}\mu (d)={\prod }_{p\mid n}(1-1)$ when $n>1$, and one when $n=1$. For the second, if $n=\prod p^{a_p}$, then ${\sum }_{d\mid n}\Lambda (d)={\sum }_p{a}_p\log p=\log n$, the Von Mangoldt divisor identity. Convolving the second identity with $\mu$ proves the third.

For $U,V\ge 1$, let the subscripts $\le U$, $>U$, $\le V$, $>V$ denote truncations. The Vaughan identity isIts pointwise form isTo prove it, use ${\mu }_{>U}\ast 1=ϵ-{\mu }_{\le U}\ast 1$ and $1\ast {\Lambda }_{>V}=\log -1\ast {\Lambda }_{\le V}$. This givesand rearrangement proves the formula, as in the Vaughan identity proof.

The Bombieri–Vinogradov theorem states that for every $A>0$ there is $B>0$ such thatHere $\psi (y;q,a)={\sum }_{\begin{array}{c}n\le y\\ n\equiv a(\mathrm{mod}q)\end{array}}\Lambda (n)$ is the Chebyshev function in an arithmetic progression, and $\varphi$ is the Euler totient function. In particular, partial summation givesafter choosing the logarithmic saving in the weighted theorem sufficiently large and absorbing the prime power terms. This is the offset logarithmic integral function.

For the proof strategy, Orthogonality of Dirichlet characters converts errors in arithmetic progressions into character sums of Dirichlet characters weighted by $\Lambda$. Reduction to primitive Dirichlet characters is followed by the character large sieve, which bounds their mean square by $O((N+Q^2)\sum |a_n{|}^2)$ with the usual $q/\varphi (q)$ weights. The Vaughan identity separates the weighted sums into short terms, Type I sums and Type II sums. Direct inner-sum estimates handle the Type I sums; the Cauchy-Schwarz inequality and the large sieve control the Type II sums. The Siegel–Walfisz theorem supplies arbitrarily strong logarithmic savings for small moduli, where an average estimate alone would not suffice. A dyadic decomposition, suitable $U,V$ and a sufficiently large $B$ absorb the divisor and logarithmic losses. This explains why the range is essentially $Q^2\le x$, with logarithmic room to spare.

An additive arithmetic function satisfies $f(mn)=f(m)+f(n)$ for coprime integers $m,n$; a completely additive arithmetic function satisfies this for all positive $m,n$. In either case $f(1)=0$. The Fundamental theorem of arithmetic gives $f(n)={\sum }_{p^k\parallel n}f(p^k)$, where $p^k\parallel n$ means that the prime valuation of $n$ at $p$ is exactly $k$.

Under the discrete uniform distribution on $[N]$, the expectation of the indicator function of $p^k\parallel n$ isThe formula remains valid when $p^{k+1}>N$. Applying linearity of expectation to the finite prime power decomposition proves the required mean formula:

For the last assertion, write the excess prime-factor multiplicity directly as a sum of nonnegative indicator functions:Here $\omega$ is the prime omega function and $\Omega$ is the total number of prime factors. The expectation is bounded independently of $N$, sinceThus Markov inequality gives vanishing probability on every diverging scale:

For an additive arithmetic function $f$, one standard form of the Turán-Kubilius inequality usesIt states, with an absolute constant,For real $f$, this also bounds the variance under the discrete uniform distribution, because centering at the actual expectation minimizes the mean square.

For the prime omega function, $f(p^k)=1$. The Mertens theorem for reciprocal primes states ${\sum }_{p\le N}1/p=\log \log N+O(1)$. The contribution of higher prime powers is bounded by ${\sum }_{p}1/(p(p-1))\le 1$, as proved in 1(a). It follows that $A_{\omega }(N)=\log \log N+O(1)$ and $B_{\omega }(N{)}^2\ll \log \log N$. Writing $L=\log \log N$, the Turán-Kubilius inequality and Chebyshev inequality therefore yieldThe bounded error in $A_{\omega }-L$ is absorbed by, for example, using the threshold $0.005L$ around $A_{\omega }$ for sufficiently large $N$.

For the multiplication table problem, call a pair $(a,b)\in [N{]}^2$ good when $\omega (a),\omega (b)\ge 0.99L$ and $\omega (\gcd (a,b))\le 0.1L$. The preceding Chebyshev inequality excludes only $O(N^2/L)$ pairs by either of the first two conditions. For the greatest common divisor condition, linearity of expectation under uniform sampling of the two coordinates givesMarkov inequality therefore excludes only another $O(N^2/L)$ pairs.

The prime factors of a product form the union of those of its factors. Consequently, for every good pair,On the other hand, apply the proved concentration estimate at $N^2$. Since $\log \log (N^2)=L+\log 2$, for large $N$ every integer $m\le N^2$ with $\omega (m)\ge 1.88L$ is exceptional there. There are only $O(N^2/L)$ such integers. Products of good pairs lie in this exceptional set; products having only bad representations are at most as numerous as the bad pairs. This proves the multiplication-table upper bound, using distinct prime factors alone:

Conjugation by $P$ partitions $H$ into orbits. Each non-singleton orbit has size divisible by $p$, by the orbit-stabilizer theorem. The singleton orbits are exactly $H\cap Z(P)$. Since $|H|$ is divisible by $p$, $|H\cap Z(P)|\equiv 0(\mathrm{mod}p)$. This set contains $1$, so $\boxed{|H\cap Z(P)|\ge p}$.

For the deduction we also give the representation-theoretic ingredient behind Burnside's theorem: a nonabelian finite simple group has no nontrivial conjugacy class of prime power size. Here is a proof, so no stronger theorem is being assumed without justification. Suppose $g\ne 1$ has class size $p^b$. For an irreducible character $\chi$ of degree $d$ coprime to $p$, the class sum acts as the scalar $p^b\chi (g)/d$, which is an algebraic integer: the class sum has an integer-entry matrix in the regular representation, which contains every irreducible representation, so this scalar is an eigenvalue of an integer-entry matrix. Also $\chi (g)$ is an algebraic integer. Bezout's identity then makes $\chi (g)/d$ an algebraic integer. All its algebraic conjugates have modulus at most $1$, because character values of a representation are sums of $d$ roots of unity. An algebraic integer with this property is zero or a root of unity: the monic polynomials of all its powers have uniformly bounded integer coefficients, so two powers must coincide unless it is zero.

Every nontrivial irreducible representation of a simple group is faithful. If $\chi (g)/d$ were a root of unity, equality in the triangle inequality would force its representing matrix to be scalar, hence $g$ central, impossible. Thus $\chi (g)=0$ whenever $p\nmid d$, except for the trivial character of a representation. Orthogonality of the identity column and the $g$ column in the character table now givesThis would make $1/p$ an algebraic integer, contradicting the fact that rational algebraic integers are integers. The same proof covers class size $1$ directly through triviality of the center.

If an abelian subgroup $A$ had index $p^a$, every $g\in A\setminus \{1\}$ would have $A\subseteq C_G(g)$, making its class size a divisor of $p^a$, a contradiction. Such a $g$ exists: if $A=1$, then $G$ is a nontrivial p-group, whose center is nontrivial by the first argument with $H=P$. Therefore a nonabelian simple group has no abelian subgroup of prime power index.

The Von Mangoldt divisor identity givesBy the Stirling formula, the left side is $\log (\lfloor x\rfloor !)=x\log x-x+O(\log x)$, while the assumed Chebyshev estimate gives $\psi (x)=O(x)$. HenceThe contribution of proper prime powers is bounded uniformly:Removing it leaves