Number theory

A Fermat number is $F_n=2^{2^n}+1$ for $n\ge 0$. Distinct Fermat numbers are coprime integers. Their prime divisors are constrained by the multiplicative order of $2$ modulo that prime; this remains useful whether or not the Fermat number itself is prime. The initial value $F_0=3$ must be distinguished when a statement restricts to positive indices.

If a prime number $p$ divides the Fermat number $F_n$, it is odd and $2^{2^n}\equiv -1(\mathrm{mod}p)$. The multiplicative order of $2$ divides $2^{n+1}$ but not $2^n$, so it is exactly $2^{n+1}$. Fermat's little theorem then gives $2^{n+1}\mid p-1$. For $n\ge 1$, every prime divisor is $1$ modulo $4$. A prime need not divide any Fermat number merely because it is $1$ modulo $4$: order $12$ excludes the prime $13$ from the whole family.

The Bernoulli numbers in the convention $B_1=-1/2$ are defined by $t/(e^t-1)={\sum }_{n\ge 0}{B}_n{t}^n/n!$. The first values are $1,-1/2,1/6,0,-1/30$. The function $t/(e^t-1)+t/2$ is even, so all odd-index values beyond $B_1$ vanish.

For a Dirichlet character $\chi$ of conductor $f$, define the generalized Bernoulli numbers byThey express special values of Dirichlet L-functions at nonpositive integers and occur in the interpolation formula for Kubota-Leopoldt p-adic L-functions.

A real number is normal in base $K\ge 2$ if every word of $r$ digits occurs in its base-$K$ expansion with limiting overlapping frequency $K^{-r}$, for every $r\ge 1$.

A number $x$ is a normal number in base $K$ exactly when $(T_K^{n}x)$ is an equidistributed sequence. A word of length $r$ corresponds to a half-open interval of length $K^{-r}$; these intervals form arbitrarily fine grids, which approximate any interval from inside and outside.

An absolutely normal number is a normal number in every integer base $K\ge 2$. The Birkhoff ergodic theorem and ergodicity of integer multiplication on the circle, followed by a countable intersection of full-measure sets, show that almost every real number is absolutely normal.

For $S\subseteq {\mathbb{Z}}_{\ge 0}$, its natural density, when it exists, is $d(S)={\lim }_{N\to \infty }|S\cap \{0,\dots ,N-1\}|/N$.

For a subset $A$ of the positive integers, its upper asymptotic density is $\overline{d}(A)={\mathrm{limsup}}_{N\to \infty }|A\cap \{1,\dots ,N\}|/N$. Unlike natural density, it always exists. If natural density exists, the two agree. Positive upper asymptotic density suffices for the Szemerédi theorem.

An increasing sequence of integers has full density when its range has natural density one. Convergence in density of a sequence means that, for each fixed tolerance, the exceptional indices have natural density zero.

The Lagrange four-square theorem says that every nonnegative integer is a sum of four integer squares.

An arithmetic function is a function whose domain is the positive integers, usually taking values in the complex numbers.

The radical of a positive integer is the product of its distinct prime factors, with $\mathrm{rad}(1)=1$. It is the squarefree integer recording which primes occur, independently of their exponents. Equality of radicals is equivalent to mutual divisibility by sufficiently high positive powers.

The completely additive arithmetic function $\Omega (n)={\sum }_p{v}_p(n)$ counts prime factors with multiplicity, whereas the prime omega function $\omega (n)$ counts distinct prime factors.

The nonnegative arithmetic function $\Omega (n)-\omega (n)$ counts the repeated occurrences beyond the first of each prime factor. Its expectation under uniform sampling from $[N]$ is bounded by ${\sum }_{p}1/(p(p-1))\le 1$, independently of $N$.

An arithmetic function $f$ is additive when $f(mn)=f(m)+f(n)$ for coprime integers $m,n$. Equivalently, $f(n)={\sum }_{p^k\parallel n}f(p^k)$. This concerns multiplication of integers, and differs from an additive function on a vector space.

For an additive arithmetic function, the model mean is $A_f(x)={\sum }_{p^k\le x}f(p^k)(1-1/p)/p^k$. The exact uniform expectation differs by $O(x^{-1}{\sum }_{p^k\le x}|f(p^k)|)$.

A strongly additive arithmetic function satisfies $f(p^k)=f(p)$ for every prime $p$ and $k\ge 1$, so $f(n)={\sum }_{p\mid n}f(p)$. The prime omega function is an example.

A completely additive arithmetic function satisfies $f(mn)=f(m)+f(n)$ for all positive $m,n$, equivalently $f(p^k)=kf(p)$. The total number of prime factors is an example.

An arithmetic function $f$ is multiplicative when $f(mn)=f(m)f(n)$ whenever $m$ and $n$ are coprime.

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.

An arithmetic function $f$ is completely multiplicative when $f(mn)=f(m)f(n)$ for every pair of positive integers $m,n$, without a coprimality condition.

The divisor sum of an arithmetic function $f$ isIf $f$ is multiplicative, then $F$ is multiplicative as well.

The sum-of-divisors function isIt is the divisor sum of the identity arithmetic function $n\mapsto n$.

For multiplicative functions bounded by one, the pretentious distance up to $x$ is defined byIt measures how similarly $f$ and $g$ behave on primes.

Let $X\ge 3$, and let $f$ be a normalized multiplicative arithmetic function supported on squarefree integers, with $|f(p)|\le 1$. Form the finite measure $\nu ={\sum }_{n}f(n)n^{-1-1/\log X}{\delta }_{\log n}$ using Dirac measures. Under the transform convention $\hat{\nu }(t)=\int e^{-itu}d\nu (u)$, its Euler product is ${\prod }_p(1+f(p)p^{-1-1/\log X-it})$. Expanding its logarithmic modulus, and replacing the damped prime weights by $1/p$ up to $X$ with Mertens first theorem, gives the displayed absolute bound, uniformly in real $t$. Hence $|\hat{\nu }(t)|\ge \delta \log X$ forces $D(f,n^{it};X{)}^2\le \log (C/\delta )$. The distance expression still defines a nonnegative pretentious score for prime values bounded by one; its actual metric interpretation uses unit-modulus values.

Because $\mu (p)=-1$, the squared pretentious distance from one to the Möbius function is twice the reciprocal-prime sum. The Mertens second theorem therefore gives $D(1,\mu ;X{)}^2=2\log \log X+2B_1+o(1)$. In particular the distance diverges, illustrating that a multiplicative function can be far from the constant function even though both have unit-modulus prime values.

For unit-modulus prime values, pretentious distance is the Euclidean metric on the finite vectors $(f(p)/\sqrt{2p}{)}_{p\le X}$. On whole arithmetic functions it is only a pseudometric: it sees neither values on prime powers nor primes above the cutoff. Even for every cutoff, the functions one and ${\mu }^2$ have distance zero but differ on nonsquarefree integers. The norm representation proves the triangle inequality and identifies exactly the quotient on which separation holds.

The pretentious distance obeys

An Archimedean character on the positive integers is the completely multiplicative function $n\mapsto n^{it}$ for a real parameter $t$.

Halász's theorem bounds the mean of a bounded multiplicative arithmetic function in terms of its least pretentious distance from an Archimedean character. A large mean can occur only when this distance is small.

The Möbius function stays far in pretentious distance from every Archimedean character. One useful uniform form isThis follows by estimating the prime sum ${\sum }_{p\le x}(1+\cos (t\log p))/p$.

The Dirichlet convolution of arithmetic functions $f$ and $g$ isIt is associative and commutative, its identity is the function supported at $1$, and the Möbius function is the convolution inverse of the constant-one function.

The constant-one arithmetic function has $1(n)=1$ for every positive integer $n$. Its Dirichlet convolution with $f$ is the divisor sum $(1\ast f)(n)={\sum }_{d\mid n}f(d)$.

The identity arithmetic function is $\mathrm{id}(n)=n$. The identity $\mathrm{id}=1\ast \phi$ is equivalent to ${\sum }_{d\mid n}\phi (d)=n$.

The identity for Dirichlet convolution is $\epsilon (1)=1$ and $\epsilon (n)=0$ for $n>1$. It satisfies $f\ast \epsilon =f$ for every arithmetic function $f$.

The Dirichlet hyperbola method evaluates a summatory Dirichlet convolution by splitting the lattice points $ab\le x$ at $a,b\le \sqrt{x}$. For the divisor 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 divisor function $\tau (n)={\sum }_{d\mid n}1$ counts the positive integer divisors of $n$.

The divisor function satisfies ${\sum }_{n\le X}d(n{)}^2\ll X{\log }^3(2X)$. Partial summation consequently gives ${\sum }_{n\le X}d(n{)}^2/n\ll {\log }^4(2X)$.

The Von Mangoldt function is $\Lambda (n)=\log p$ when $n$ is a positive power of a prime number $p$, and is zero otherwise.

The elementary Selberg symmetry formula can be writtenUse the weights ${\lambda }_d=\mu (d)\log (x/d)/\log x$. Their divisor sum is $1_{n=1}+\Lambda (n)/\log x$. Apply them to the integrated Chebyshev sum, then use the Möbius harmonic logarithmic moments. The Chebyshev estimate shows this is equivalent, with an $O(x)$ error, to ${\sum }_{n\le x}\Lambda (n)\log n+{\sum }_{mn\le x}\Lambda (m)\Lambda (n)=2x\log x+O(x)$.

For every positive integer $n$,Equivalently, the constant-one function convolved with the Von Mangoldt function is the natural logarithm.

The two Chebyshev functions are

The second Chebyshev function is the summatory Von Mangoldt function, $\psi (x)={\sum }_{n\le x}\Lambda (n)$.

For $\psi (t)={\sum }_{m\le t}\Lambda (m)$, finite rearrangement and the Von Mangoldt divisor identity giveThe Stirling formula, or integral comparison for the logarithm, gives $T(x)=x\log x-x+O(\log (x+1))$ for real $x\ge 1$.

The Chebyshev estimate isIt gives upper and lower bounds of the correct linear order without asserting the Prime number theorem asymptotic $\psi (x)\sim x$.

The central binomial coefficient satisfies $4^m/(2m+1)\le \left(\genfrac{}{}{0ex}{}{2m}{m}\right)\le 4^m$. Prime factors between $m$ and $2m$ give a dyadic upper bound for the Chebyshev theta function. The prime-power exponents in the factorial quotient are sums of zeros and ones, so the central coefficient gives a linear lower bound for the Second Chebyshev function. Higher prime powers contribute only $O(\sqrt{x}\log x)$; hence the prime-counting function has upper and lower bounds of order $x/\log x$.

For $x>1$ away from a jump of $\psi$,where the sum over Nontrivial zeros of the Riemann zeta function is taken symmetrically. A finite-height version has an explicit truncation error controlled by $x/T$ and the distance from $x$ to the nearest prime power.