Number theory

Number theory studies integers, their divisibility, and the patterns created by prime numbers. Its questions often have short statements but rigid answers: which integers divide a given one, when does an equation have integer solutions, and when can arithmetic with congruence classes be reversed? The Euclidean algorithm and modular multiplicative inverses connect these questions through explicit calculations.

For example,

252 = 2^{2} \cdot 3^{2} \cdot 7

and

198 = 2 \cdot 3^{2} \cdot 11

. Their shared prime factors give greatest common divisor

18

. The Euclidean algorithm reaches that answer without finding either complete prime factorization. It also produces

18 = 4 \cdot 252 - 5 \cdot 198

, an instance of Bézout's identity. This relation certifies every common divisor at once and solves an associated linear Diophantine equation.

Modular arithmetic retains only remainders, but the lost information can be surprisingly controlled. Multiplication by

5

modulo

17

is a permutation of all residue classes, because

5

has modular inverse

7

. Multiplication by

5

modulo

15

collapses fifteen residue classes to three. Thus an apparently small change in the modulus changes whether a calculation can be reversed. The Chinese remainder theorem explains another kind of compression: remainders modulo coprime integers can be combined into one remainder modulo their product.

Simple restrictions help reveal the structure without telling the whole story. Every prime number greater than three is congruent to

1

5

modulo

6

: the other four residue classes force divisibility by

2

3

. The converse fails because

25

and

35

lie in those classes but are composite numbers. Necessary conditions are useful filters, not substitutes for primality testing.

The subject's appeal lies partly in this tension: prime factorization gives a clean description of every positive integer, while identifying factors and predicting their distribution lead to substantial further questions. Analytic number theory uses tools from analysis to study global patterns, and algebraic number theory extends arithmetic into number fields. Applications include cryptography and error-correcting codes; MIT's discrete applied mathematics course develops modular structures for both purposes. ^[ref]

Table of contents

Sum of two squares

 0  0

A representation

n = a^{2} + b^{2}

with integers

a, b

. Signs, ordering, and whether zero is allowed must be specified when counting representations. The sum of two squares theorem characterizes which nonnegative integers have such a representation.

Pronic number ( $n (n + 1)$ )

 1  0

A pronic number is the product

n (n + 1)

of consecutive nonnegative integers. It is twice a triangular number.

Cube-full number

 0  0

A cube-full number is a positive integer in which every occurring prime factor has exponent at least three. The number

1

is included by the empty-product convention.

Arithmetic derivative ( $n^{'}$ )

 1  0

The arithmetic derivative on positive integers is defined by

p' = 1

for every prime

p

and the product rule

(ab)' = a' b + ab'

. For

n = \prod_{i} p_{i}^{e_{i}}

, these rules give

n' = n \sum_{i} e_{i} / p_{i}

. In particular,

(p^{e})' = e p^{e - 1}

Harshad number

 0  0

A Harshad number in base

b \geq 2

is a positive integer divisible by its base-p digit sum in that base. In base ten,

18

is a Harshad number because

1 + 8 = 9

divides

18

. It is strong when the quotient by its base-p digit sum is prime, and right-truncatable when every nonempty prefix is a Harshad number.

Frobenius number ( $g (a_{1}, \dots, a_{k})$ )

 0  0

For positive integers

a_{1}, \dots, a_{k}

with greatest common divisor

1

, and with every

a_{i} > 1

, the largest integer not expressible as a nonnegative integer linear combination of the

a_{i}

. For two coprime generators

a, b

, it equals

ab - a - b

Two-generator Frobenius theorem

 0  0

For coprime integers

a, b > 1

, the Frobenius number is

ab - a - b

. Every larger integer is a nonnegative integer linear combination of

a, b

Practical number

 1  0

A positive integer

n

such that every positive integer at most

n

is a sum of distinct divisors of

n

. For example,

6

is practical because its divisors

1, 2, 3, 6

represent every value from

1

through

6

Product-sum number

 0  0

A positive integer

N

that is both the sum and the product of one multiset of

k

positive integers. For factors at least

2

with product

P

, sum

S

, and count

t

, appending

P - S

ones gives

k = t + P - S

without changing the product. For

k \geq 2

, the example

2, k

with

k - 2

ones proves that the smallest product-sum value is at most

2 k

Integer factorization ( $N = \prod_{p} p^{v_{p} (N)}$ )

 2  0

Integer factorization seeks the prime factorization of a positive integer

N

. For

N > 1

, this means identifying its prime factors and their multiplicities; one has the empty prime factorization. Finding one proper divisor

1 < d < N

is useful progress, but need not finish the job: factor

d

and

N / d

further until all factors are prime numbers.

For example,

77 = 7 \cdot 11

is a semiprime, whereas

231 = 3 \cdot 7 \cdot 11

has three prime factors. Primality testing asks whether a proposed integer is prime; it need not return a factor when the answer is no. Trial division is a direct factoring method: try division by small prime numbers until a divisor is found. More elaborate methods obtain a proper divisor through a greatest common divisor of

N

with a specially constructed integer.

The beautiful trick in congruence of squares is that two integers with equal squares modulo

N

can reveal different factors through their sum and difference. In the worked

N = 77

example,

2 0^{2} \equiv 1 3^{2} (mod 77)

gives

g cd (20 - 13, 77) = 7

and

g cd (20 + 13, 77) = 11

. Computing those greatest common divisors uses the Euclidean algorithm; it does not require trying every potential factor. A factor base supplies a systematic way to construct useful equal-square relations. ^[ref].

This connection is useful in cryptography because recovering the factors of an RSA cryptosystem modulus defeats the factoring assumption behind its construction. That application concerns large, carefully chosen inputs; the small examples here explain the arithmetic mechanism and are not benchmarks or estimates of present cryptographic security.

Pollard's p-1 algorithm

 0  0

For an integer

n

to be factored, John Pollard's method chooses an integer

a

coprime to

n

and an exponent

M

divisible by many small prime powers. Compute

d = g cd (a^{M} - 1, n)

by modular exponentiation and the Euclidean algorithm. If

1 < d < n

, it is a proper factor. If a prime divisor

p

n

has

p - 1 ∣ M

, Fermat's little theorem ensures

p ∣ d

; success requires some other prime divisor not to divide

a^{M} - 1

. Common choices are

M = B!

and

M = lcm (1, \dots, B)

. The method exploits a smooth

p - 1

, rather than a small factor

p

itself.

General number field sieve

 0  0

A general-purpose classical integer factorization algorithm combining polynomial relations, arithmetic in number fields and sparse linear algebra to construct congruent squares modulo the input. Its familiar general-input complexity estimate is heuristic and subexponential in the input's value, roughly

exp (O (n^{1/3} (lo g n)^{2/3}))

for

n

input bits. This is not polynomial in the bit length. Special input structure, small factors and preprocessing can make other algorithms preferable.

Ordered factorization

 0  0

An ordered factorization of a positive integer

n > 1

is an ordered list of factors greater than one whose product is

n

. For example,

6

2 \cdot 3

, and

3 \cdot 2

are the three ordered factorizations of

6

. Taking successive partial products gives a bijection with strictly increasing divisor chains from

1

n

Pollard's rho algorithm

 0  0

An integer factorization algorithm that iterates a simple map such as

x \mapsto x^{2} + c mod n

and searches for a nontrivial greatest common divisor of

n

and the difference of two iterates. A collision modulo an unknown prime factor can reveal that factor before a collision modulo

n

. A cycle detection schedule such as Floyd's cycle-finding algorithm limits the number of stored iterates. Unsuccessful choices of seed or map can be retried.

Brent variant of Pollard rho

 0  0

Factor base

 0  0

A factor base is a finite set of small prime numbers over which selected auxiliary integers are completely factored. Some methods also record a sign coordinate for

- 1

, which is not a prime number. A positive integer supported entirely on the chosen factor base gives an exponent vector; reducing that vector modulo two records which prime exponents are odd integers. The product is a square of a number precisely when every prime exponent is an even integer.

For the original toy

N = 77

, use factor base

{2, 3, 5}

and the two relations

1 3^{2} \equiv 15 = 3 \cdot 5 (mod 77), 4 0^{2} \equiv 60 = 2^{2} \cdot 3 \cdot 5 (mod 77) .

(1)

The residues have exponent vectors

(0, 1, 1)

and

(2, 1, 1)

in the order

(2, 3, 5)

. Adding the two vectors modulo two gives

(0, 0, 0)

, so multiplying the residues gives

15 \cdot 60 = 900 = 3 0^{2}

. Consequently

(13 \cdot 40)^{2} \equiv 3 0^{2} (mod 77), X = 13 \cdot 40 mod 77 = 58, Y = 30,

(2)

and $g cd (X - Y, 77) = 7$ and $g cd (X + Y, 77) = 11$ . Neither individual residue was a square; combining the relations made all exponents even.

Figure 1.
A factor base turns two smooth relations into a congruence of squares through exponent parity
. The original $N = 77$ example uses the ordered factor base $(2, 3, 5)$ . The rows $(0, 1, 1)$ and $(2, 1, 1)$ add to zero modulo two, giving residue product $900 = 3 0^{2}$ . The product of the original inputs is $520 \equiv 58 (mod 77)$ ; greatest common divisor calculations then extract seven and eleven. **Details**.

In a larger collection, choose relations

x_{i}^{2} \equiv r_{i} (mod N)

with positive residues

r_{i} = \prod_{j = 1}^{B} p_{j}^{e_{ji}}

. If a nonempty selection

I

has an even sum in every exponent coordinate, set

X = \prod_{i \in I} x_{i} mod N, Y = \prod_{j = 1}^{B} p_{j}^{\frac{1}{2} \sum_{i \in I} e_{ji}} mod N .

(3)

Then

X^{2} \equiv Y^{2} (mod N)

. Finding such a selection is a linear dependence problem over the finite field

F_{2}

: the indicator vector of the chosen relations belongs to the kernel of a linear map given by the parity matrix. This is why a problem about prime factors recruits linear algebra. The final congruence of squares may still be trivial, so another selection can be needed. ^[ref].

There is a tradeoff: a small factor base gives a smaller parity matrix, but fewer auxiliary integers factor completely over it. A larger factor base accepts more relations but makes the linear algebra larger. Negative auxiliary values need an additional sign coordinate, and a selected product needs even sign parity as well as even prime exponents. Pomerance's account explains this balance and the historical development of combining smooth relations; the toy example omits algorithm-specific sieving and running-time claims. ^[ref].

Exponent vector ( $e (r) = (e_{1}, \dots, e_{B})$ )

 0  0

Relative to an ordered factor base

(p_{1}, \dots, p_{B})

, a positive integer

r = \prod_{j} p_{j}^{e_{j}}

has exponent vector

(e_{1}, \dots, e_{B})

. Multiplication of such integers adds their exponent vectors. Reducing every coordinate modulo two gives the parity vector used to find congruences of squares. The ordering and any sign coordinate must be used consistently across all rows.

Prime-exponent difference

 0  0

Odd part of a positive integer ( $n = 2^{v_{2} (n)} d$ )

 0  0

The odd part of a positive integer

n

is the unique odd positive integer

d

obtained by repeatedly dividing

n

by two. The process terminates because the positive integers decrease. If

2^{r} d = 2^{s} e

with

d, e

odd, then

r > s

would make

e

even and

s > r

would make

d

even; hence

r = s

and

d = e

. Two positive integers have the same odd part exactly when their ratio is an integral power of two. The odd positive integers therefore give representatives for the resulting equivalence classes.

Congruence of squares ( $a^{2} \equiv b^{2} (mod N)$ )

 1  0

A congruence of squares says that two integers

a, b

have the same square modulo a positive integer

N

. Factoring their difference of squares gives

a^{2} \equiv b^{2} (mod N) ⟹ N ∣ (a - b) (a + b) .

(1)

A useful integer factorization results when

g cd (a - b, N)

g cd (a + b, N)

is a proper divisor of

N

. Divisibility of a product does not generally force divisibility of either factor by all of

N

: different prime factors of

N

can divide different parts of that product.

For

N = 77

2 0^{2} - 1 3^{2} = 231 = 3 \cdot 77

. Therefore

g cd (20 - 13, 77) = g cd (7, 77) = 7, g cd (20 + 13, 77) = g cd (33, 77) = 11.

(2)

Thus $77 = 7 \cdot 11$ . The prime seven divides the difference, while eleven divides the sum. These computations already give a complete prime factorization because seven and eleven are prime numbers.

The Chinese remainder theorem explains the hidden sign choices. The four congruence classes solving

z^{2} \equiv 15 (mod 77)

have representatives

13, 20, 57, 64

. Modulo seven each is

1

- 1

; modulo eleven each is

2

- 2

. Two independent sign choices produce four roots. The inputs thirteen and twenty agree modulo seven and disagree by sign modulo eleven, allowing their sum and difference to separate the two prime factors.

Figure 1.
The Chinese remainder theorem exposes four sign choices behind one square residue modulo $77$
. Each cell gives the unique residue modulo $77$ with its indicated residues modulo seven and eleven. Relative to input thirteen, input twenty agrees modulo seven and has the opposite sign modulo eleven. The resulting greatest common divisors are seven and eleven. Diagonal all-same or all-opposite choices give only the trivial factors one and $77$ . **Details**.

For distinct odd prime numbers

p, q

N = pq

and

g cd (b, N) = 1

, a solution

a^{2} \equiv b^{2} (mod N)

with

a \neq \equiv b

and

a \neq \equiv - b

modulo

N

yields both proper factors by the two greatest common divisors. For a general composite integer, a proper divisor need not itself be prime; further factoring can remain. If

a \equiv b

a \equiv - b (mod N)

in the coprime case, the two calculations return

N

and one instead. A factor base helps generate relations, but does not ensure every resulting relation is useful.

For historical context, Pomerance describes Kraitchik's 1920s enhancement of the difference-of-squares approach associated with Fermat: seek a difference that is a multiple of

N

, rather than exactly

N

. His account also notes antecedents in Gauss and Seelhoff, so this is not an attribution of the whole idea to a single inventor. ^[ref].

Nontrivial square root of unity modulo an integer ( $z^{2} \equiv 1 (mod N), z \neq \equiv \pm 1 (mod N)$ )

 0  0

For an odd integer

N > 1

, a nontrivial square root of unity modulo

N

is a residue

z

with

z^{2} \equiv 1 (mod N)

and

z \neq \equiv \pm 1 (mod N)

. Then both

g cd (z - 1, N)

and

g cd (z + 1, N)

are proper divisors. For

N = 77

z = 34

works:

3 4^{2} \equiv 1 (mod 77)

g cd (33, 77) = 11

, and

g cd (35, 77) = 7

A congruence of squares with

g cd (b, N) = 1

converts to this form by

z \equiv a b^{- 1} (mod N)

, using a modular multiplicative inverse. In the

a = 20, b = 13

example,

1 3^{- 1} \equiv 6 (mod 77)

, so

z \equiv 20 \cdot 6 \equiv 43 (mod 77)

. It yields

g cd (42, 77) = 7

and

g cd (44, 77) = 11

. Nontriviality requires mixed sign choices across prime factors, which an odd prime number modulus cannot provide.

Erdős-Turán inequality

 1  0

The Erdős-Turán inequality bounds discrepancy of a finite sequence on the circle by a smoothing error and exponential sums of its low Fourier modes.

Fermat number ( $F_{n} = 2^{2^{n}} + 1$ )

 1  0

A Fermat number is the positive integer

F_{n} = 2^{2^{n}} + 1

, indexed by a nonnegative integer

n

. The first five are

3, 5, 17, 257, 65537

, all prime numbers; the next is the composite number $F_{5} = 4294967297 = 641 \cdot 6700417$ . This family offers a compact lesson in number theory: a very persuasive finite pattern can fail, while an exact divisibility relation settles a gigantic case with little computation.

Figure 1.
Exact Fermat numbers: five initial primes, a composite sixth term, and rapidly increasing decimal lengths
. **Details**.

Why does the exponent itself have the form

2^{n}

? Suppose

m = ab

is a positive integer with an odd integer factor

b > 1

. The polynomial factorization

x^{b} + 1 = (x + 1) (x^{b - 1} - x^{b - 2} + \dots - x + 1)

shows that

2^{a} + 1

is a proper divisor of

2^{m} + 1

. Consequently, if

2^{m} + 1

is a prime number,

m

must be a power of two. That is a necessary condition, rather than a promise that the surviving candidates are prime.

The Fermat number product identity makes distinct Fermat numbers coprime integers. Thus every term has a prime factor absent from all earlier terms, whether or not that term is itself a prime number. This gives an explicit route to infinitely many different prime numbers, without establishing that infinitely many terms of this particular sequence are prime. Meanwhile the prime divisor of a Fermat number criterion filters possible factors through a small multiplicative order calculation.

The family also links arithmetic to Euclidean geometry: a constructible regular polygon can have a number of sides equal to a power of two times a product of distinct Fermat primes. The Gauss-Wantzel theorem gives the precise criterion. For instance,

15 = 3 \cdot 5

and

17

qualify, but

9 = 3^{2}

does not. The word "distinct" matters. Carl Pomerance describes this connection in Primality testing: then and now by Carl Pomerance (slide 18).

Historically, Leonhard Euler records Pierre de Fermat's proposed primality pattern, then refutes it by finding the factor

641

F_{5}

. His paper was presented in 1732 and published in 1738; those are different events, not competing dates for one publication.^[ref]

A short modern check needs only two representations of

641

641 = 5 \cdot 2^{7} + 1 = 5^{4} + 2^{4} .

(1)

In modular arithmetic these give

5^{4} 2^{28} \equiv 1

and

5^{4} \equiv - 2^{4} (mod 641)

. Substitution yields

2^{32} \equiv - 1 (mod 641)

, so

641 ∣ F_{5}

. This verifies the factor directly; it does not claim to reconstruct Euler's search process.

Fermat number product identity ( $\prod_{j = 0}^{n - 1} F_{j} = F_{n} - 2$ )

 0  0

For each positive integer

n

, the product of the preceding Fermat numbers is two less than the next:

\prod_{j = 0}^{n - 1} F_{j} = 2^{2^{n}} - 1 = F_{n} - 2.

(1)

For example,

3 \cdot 5 \cdot 17 = 255 = 257 - 2

. The identity telescopes by repeated difference of squares:

(2^{2^{j}} - 1) (2^{2^{j}} + 1) = 2^{2^{j + 1}} - 1

. Its usefulness is that a huge integer product exposes a tiny difference, two, from the next term.

Distinct Fermat numbers are coprime ( $g cd (F_{m}, F_{n}) = 1 (m \neq = n)$ )

 0  0

m < n

, a common divisor of

F_{m}

and

F_{n}

divides both

F_{n} - 2

, by the Fermat number product identity, and

F_{n}

. It therefore divides two. Both Fermat numbers are odd integers, so their greatest common divisor is one. Each term's prime factors are consequently different from the prime factors of every other term.

Prime divisor of a Fermat number ( $ord_{p} (2) = 2^{n + 1}$ )

 0  0

For a prime number

p

, the exact criterion is

p ∣ F_{n} ⟺ ord_{p} (2) = 2^{n + 1}, n \geq 0,

(1)

where

p

must be different from two and

ord_{p} (2)

is the multiplicative order of two modulo

p

. If

p ∣ F_{n}

, then

2^{2^{n}} \equiv - 1 (mod p)

: the order divides

2^{n + 1}

but not

2^{n}

, so it is exactly

2^{n + 1}

. Conversely, that order makes

2^{2^{n}}

a square root of unity different from one in the prime field

F_{p}

; it must be

- 1

, because

(x - 1) (x + 1) = 0

has no other roots in a field.

Figure 1.
Exact modular powers distinguish Fermat divisors from the prime thirteen, whose multiplicative order is twelve
. **Details**.

For example, modulo seventeen the powers of two are

2, 4, 8, 16, 15, 13, 9, 1

. Their first return to one occurs after eight steps. The half-way value is

16 = - 1 (mod 17)

, proving that

17 ∣ F_{2}

. Likewise,

ord_{641} (2) = 64

identifies

641

as a prime factor of

F_{5}

. These are statements about divisibility, not evidence that the entire Fermat number is prime.

The multiplicative order always divides

p - 1

, by Fermat's little theorem, so

p \equiv 1 (mod 2^{n + 1})

. In particular, for

n \geq 1

every prime divisor of a Fermat number is one modulo four. That weaker modular congruence is insufficient: thirteen is one modulo four, but

ord_{13} (2) = 12

, which is not a power of two. It divides no Fermat number at any index. The exact order criterion explains the whole family, instead of testing finitely many terms.

Stronger prime-divisor congruence for Fermat numbers ( $p ∣ F_{n}, n \geq 2 ⟹ p \equiv 1 (mod 2^{n + 2})$ )

 0  0

For

n \geq 2

, the first order bound already gives

p \equiv 1 (mod 8)

. The second supplementary law for quadratic reciprocity says that two is then a quadratic residue modulo

p

. Euler's criterion gives

2^{(p - 1) /2} \equiv 1

, so its multiplicative order

2^{n + 1}

divides

(p - 1) /2

. Thus

2^{n + 2} ∣ p - 1

, further reducing the candidate factors. At

n = 5

641 = 5 \cdot 128 + 1

meets this bound. The restriction matters:

F_{1} = 5

has factor five, which is not one modulo eight.

Bernoulli number ( $B_{n}$ )

 1  0

The Bernoulli numbers are a sequence of rational numbers that turns integer power sums into exact polynomials. The same numbers describe corrections when a discrete summation is compared with an integral. For example, the sum of squares

1^{2} + \dots + N^{2}

N^{3} /3 + N^{2} /2 + N /6

: the leading term is an integral, while the last two terms repair the difference between area and sampled values.

We use $B_{1} = - \frac{1}{2}$ throughout. The defining exponential generating function is

\frac{t}{e ^{t} - 1} = \sum_{n = 0}^{\infty} B_{n} \frac{t ^{n}}{n !} = 1 - \frac{t}{2} + \frac{t ^{2}}{12} - \frac{t ^{4}}{720} + \frac{t ^{6}}{30240} - \dots .

(1)

Here

e^{t}

is the exponential function and

n!

is a factorial; in particular, the coefficient of

t^{2}

B_{2} /2!

, rather than

B_{2}

. At

t = 0

the quotient has limiting value one. The identity can be read algebraically as a formal power series, or as a convergent series for

∣ t ∣ < 2 π

.^[ref]

To compute the numbers, multiply by

e^{t} - 1

and compare coefficients. The resulting recurrence relation, with binomial coefficients, is

B_{0} = 1, \sum_{k = 0}^{m} (k m + 1) B_{k} = 0 (m \geq 1), B_{m} = - \frac{1}{m + 1} \sum_{k = 0}^{m - 1} (k m + 1) B_{k} .

(2)

Thus

1 + 2 B_{1} = 0

1 + 3 B_{1} + 3 B_{2} = 0

, and

1 + 4 B_{1} + 6 B_{2} + 4 B_{3} = 0

give

B_{1} = - 1/2

B_{2} = 1/6

, and

B_{3} = 0

. Continuing gives

n B_{n} 01 1 - \frac{1}{2} 2 \frac{1}{6} 30 4 - \frac{1}{30} 50 6 \frac{1}{42} 70 8 - \frac{1}{30} 90 10 \frac{5}{66}

(3)

The recurrence relation agrees with equation 24.5.3 after replacing its index

n

m + 1

.^[ref]

Why do so many values vanish? Put

F (t) = t / (e^{t} - 1)

. Direct substitution gives

F (- t) = F (t) + t

, so

F (t) + t /2

is an even function. Its odd power series coefficients vanish:

B_{2 r + 1} = 0

for every positive integer

r

. The exception

B_{1}

matters. The alternative convention obtained from

t / (1 - e^{- t}) = F (t) + t

has

B_{1}^{+} = + 1/2

and exactly the same other values. A formula copied between conventions must also retain its summation endpoints.

Historically, integer power sums were studied before the modern Bernoulli number notation. A historical study examines formulas published in 1631 and distinguishes those separate formulas from encoding all exponents using one sequence of constants. This is a useful motivation for the generating function, without assigning all discovery to a single moment. ^[ref]

von Staudt-Clausen theorem

 1  0

Bernoulli polynomial ( $B_{n} (x)$ )

 0  0

The Bernoulli polynomials extend the Bernoulli numbers by inserting the exponential function

e^{x t}

into their exponential generating function:

\frac{t e ^{x t}}{e ^{t} - 1} = \sum_{n = 0}^{\infty} B_{n} (x) \frac{t ^{n}}{n !}, B_{n} (x) = \sum_{j = 0}^{n} (j n) B_{j} x^{n - j}, B_{n} (0) = B_{n} .

(1)

For example,

B_{0} (x) = 1

B_{1} (x) = x - 1/2

B_{2} (x) = x^{2} - x + 1/6

, and

B_{3} (x) = x^{3} - 3 x^{2} /2 + x /2

.^[ref]

Their crucial property is a finite difference identity:

B_{n} (x + 1) - B_{n} (x) = n x^{n - 1} (n \geq 1) .

(2)

Indeed, subtracting the two exponential generating functions cancels

e^{t} - 1

and leaves

t e^{x t}

. Thus

B_{p + 1} (x) / (p + 1)

plays for discrete summation the role that

x^{p + 1} / (p + 1)

plays for integration: taking a unit finite difference recovers

x^{p}

.^[ref]

Integer power sum ( $S_{p} (N) = \sum_{k = 0}^{N - 1} k^{p}$ )

 0  0

An integer power sum adds a fixed nonnegative integer power of consecutive integers. Let

N

be a nonnegative integer and

p

a nonnegative integer. For

p = 0

, use the constant polynomial

x^{0} = 1

, including at zero, so

S_{0} (N) = N

. Summing the Bernoulli polynomial finite difference identity makes the intermediate terms cancel and gives

S_{p} (N) = \sum_{k = 0}^{N - 1} k^{p} = \frac{B _{p + 1} ( N ) - B _{p + 1} ( 0 )}{p + 1} = \frac{1}{p + 1} \sum_{j = 0}^{p} (j p + 1) B_{j} N^{p + 1 - j} .

(1)

The sum is empty when

N = 0

. For the endpoints

1, \dots, N

, the formula valid also at

p = 0

is instead

\sum_{k = 1}^{N} k^{p} = \frac{B _{p + 1} ( N + 1 ) - B _{p + 1} ( 1 )}{p + 1} .

(2)

For

p \geq 1

B_{p + 1} (1) = B_{p + 1} (0)

, and this becomes the standard positive-endpoint formula. The exception at

p = 0

is essential:

B_{1} (1) - B_{1} (0) = 1

.^[ref]

For

p \geq 1

, adding

N^{p}

S_{p} (N)

changes the

B_{1}

contribution from

- N^{p} /2

+ N^{p} /2

. Equivalently,

\sum_{k = 1}^{N} k^{p} = \frac{1}{p + 1} \sum_{j = 0}^{p} (j p + 1) B_{j}^{+} N^{p + 1 - j} (p \geq 1),

(3)

where only

B_{1}^{+}

differs from our Bernoulli numbers. A quick endpoint check is

p = 1

: the sums over

0, \dots, N - 1

and

1, \dots, N

are

N (N - 1) /2

and

N (N + 1) /2

, respectively. The latter is a triangular number.

Bernoulli corrections for polynomial sums ( $\sum_{k = 1}^{N} k^{4} = \frac{N ^{5}}{5} + \frac{N ^{4}}{2} + \frac{N ^{3}}{3} - \frac{N}{30}$ )

 0  0

For a concrete comparison, take

f (x) = x^{2}

[0, 6]

. The integral is

I = \int_{0}^{6} x^{2} d x = 72

, whereas the unit-width left and right Riemann sums are

L = 55

and

R = 91

. The exact integer power sum formula gives

L = I - \frac{6 ^{2}}{2} + \frac{6}{6} = 55, R = I + \frac{6 ^{2}}{2} + \frac{6}{6} = 91.

(1)

The endpoint choice explains the opposite signs of the

18

correction. The remaining correction is one in both cases.

Figure 1.
Left and right Riemann sums for $x^{2}$ differ from its integral by exact Bernoulli number corrections
. Six rectangles of width one sample $x^{2}$ at $0, \dots, 5$ on the left and $1, \dots, 6$ on the right. Their areas are $55$ and $91$ ; the smooth area is $72$ . The endpoint terms are $- 18$ and $+ 18$ , while the $B_{2}$ correction adds one in each case. **Details**.

The same method is useful far beyond squares of numbers. Substituting

B_{0}

B_{1}

B_{2}

and

B_{4}

into the integer power sum formula gives the exact fourth-power result

\sum_{k = 1}^{N} k^{4} = \frac{N ^{5}}{5} + \frac{N ^{4}}{2} + \frac{N ^{3}}{3} - \frac{N}{30} .

(2)

N = 10

, this is

integral 20000 + endpoint 5000 + B_{2} term \frac{1000}{3} - B_{4} term \frac{1}{3} = 25333.

(3)

Thus a finite polynomial calculation replaces ten additions, or a million additions if

N

is a million. Although the individual corrections can be rational numbers, the result is the exact integer sum.

Figure 2.
Exact Bernoulli number corrections turn an integral into the fourth-power sum $1^{4} + \dots + 1 0^{4}$
. The first panel builds the sum from integral $20000$ , endpoint term $5000$ , and $B_{2}$ term $1000/3$ . The enlarged second panel resolves the final $B_{4}$ correction $- 1/3$ , reaching $25333$ , checked independently by direct addition. **Details**.

There is also a useful numerical integration interpretation. The average of the left and right Riemann sums is the composite trapezoidal rule. For

x^{2}

, the endpoint corrections cancel but its value is

73

, one above the true integral. Subtracting the

B_{2}

correction makes this particular polynomial example exact. For

f (x) = x^{4}

, the two interior corrections above can be written

B_{2} (f^{'} (N) - f^{'} (0)) /2!

and

B_{4} (f^{'''} (N) - f^{'''} (0)) /4!

. These are exact identities for these polynomials; extending such corrections to general functions requires a separate error analysis.

Hyperbolic cotangent generating function for Bernoulli numbers ( $coth z = z^{- 1} + \sum_{j \geq 1} \frac{2 ^{2 j} B _{2 j}}{( 2 j )!} z^{2 j - 1}$ )

 0  0

The defining generating function of the Bernoulli numbers, with

B_{1} = - 1/2

, gives this identity of formal Laurent series by

coth z = 1 + 2/ (e^{2 z} - 1)

. Therefore

a coth (a z) - coth z

is regular and odd. Integrating it gives the even formal logarithm of

sinh (a z) / (a sinh z)

. Its even derivatives of order

k

at zero are

2^{k} (a^{k} - 1) B_{k} / k

, while the odd derivatives vanish. This computes the cyclotomic higher logarithmic derivatives of symmetric cyclotomic units without introducing a spurious linear term.

Euler evaluation of even zeta values ( $ζ (2 r) = (- 1)^{r + 1} B_{2 r} (2 π)^{2 r} / (2 (2 r)!)$ )

 0  0

The Euler evaluation of even zeta values turns a family of series into exact expressions using Bernoulli numbers, factorials and powers of

π

. For every positive integer

r

n = 1 \sum \infty \frac{1}{n ^{2 r}} = ζ (2 r) = \frac{( - 1 ) ^{r + 1} B _{2 r} ( 2 π ) ^{2 r}}{2 ( 2 r )!} .

(1)

Here

ζ

is the Riemann zeta function, defined by its convergent series at these arguments, and the Bernoulli number convention is

B_{1} = - 1/2

. The alternating sign combines with the sign of

B_{2 r}

to give a positive sum.^[ref]

Substituting

B_{2} = 1/6

B_{4} = - 1/30

and

B_{6} = 1/42

gives

ζ (2) = \frac{π ^{2}}{6}, ζ (4) = \frac{π ^{4}}{90}, ζ (6) = \frac{π ^{6}}{945} .

(2)

The first identity answers the Basel problem. It is surprising because the original series only mentions reciprocal squares of integers, while its exact sum involves the circle constant

π

. The cotangent partial-fraction expansion supplies a connection between the two: trigonometric functions encode equally spaced integer poles, whose expansion brings the reciprocal powers into view.

For an original numerical comparison, the first ten terms give

\sum_{n = 1}^{10} n^{- 2} \approx 1.549767731

, while

π^{2} /6 \approx 1.644934067

. The omitted positive terms still contribute approximately

0.095166336

. For fourth powers, the ten-term partial sum is approximately

1.082036583

, only

0.000286650

below

π^{4} /90 \approx 1.082323234

. Both are convergent series, but the second approaches its limit much faster.

Figure 1.
Reciprocal-square and reciprocal-fourth-power partial sums approach exact zeta values
. Original computed partial sums for the first thirty terms. Each panel has its own vertical scale. Dashed horizontal lines mark $π^{2} /6$ and $π^{4} /90$ ; neither finite partial sum equals its limiting value. **Details**.

Exact evaluation is useful beyond obtaining more digits. It supplies an independent check on a numerical summation, exposes how Bernoulli numbers organize infinitely many identities, and makes the remaining series truncation error measurable without knowing any omitted terms individually. The even integer condition is essential to this formula: putting

r = 3/2

into it is not a way to evaluate

ζ (3)

, since the required Bernoulli number index and factorial expression here are indexed by positive integers.

Historically, Leonhard Euler announced reciprocal-square and reciprocal-fourth-power evaluations in §2 of On the sums of series of reciprocals by Leonhard Euler. That paper was presented on 5 December 1735 and published in 1740, as the English translation's first-page note records. His §§3–8 develop a route through the sine power series and relationships between roots and coefficients. The cotangent calculation below is a concise modern presentation of the connection.^[ref]

Zeta series truncation error ( $R_{N} (s) = ζ (s) - \sum_{n = 1}^{N} n^{- s}$ )

 0  0

For a real exponent

s > 1

and a positive integer

N

, the series truncation error in the defining Riemann zeta function series is

R_{N} (s) = \sum_{n = N + 1}^{\infty} n^{- s} > 0.

(1)

The integral comparison for the positive decreasing function

x^{- s}

gives the explicit bounds

\frac{( N + 1 ) ^{1 - s}}{s - 1} \leq R_{N} (s) \leq \frac{N ^{1 - s}}{s - 1} .

(2)

On each unit interval, the area under

x^{- s}

lies between its endpoint heights. Summing from the first omitted term gives the lower integral from

N + 1

to infinity and the upper integral from

N

to infinity. This uses positivity and monotonicity, not an assumption that the last computed term equals the remaining error.

N = 10

, the bounds are

1/11 \leq R_{10} (2) \leq 1/10

, whereas

1/ (3 \cdot 1 1^{3}) \leq R_{10} (4) \leq 1/ (3 \cdot 1 0^{3})

. The errors above fit both intervals. Merely looking at the eleventh term would give

1/121 \approx 0.008264

for squares, far smaller than the actual remaining

0.095166

Figure 1.
Integral bounds enclose the full remaining error of two zeta series
. Original computed errors, obtained by subtracting finite partial sums from the exact even zeta values. Shaded bands show the upper and lower integral comparison bounds. The logarithmic axes reveal decay proportional to $1/ N$ for squares and $1/ N^{3}$ for fourth powers. These are mathematical computations, not measured data. **Details**.

For a chosen absolute error target

ε > 0

, the sufficient condition is

N \geq ((s - 1) ε)^{- 1/ (s - 1)}

, rounded upward to an integer. Thus

ε = 1 0^{- 4}

requires

N = 10000

by this bound for squares but only

N = 15

for fourth powers. This is a guarantee from an upper bound, not a claim that those are the smallest successful term counts.

Cotangent coefficient proof of the even zeta values

 0  0

The cotangent partial-fraction expansion gives, on

0 < ∣ z ∣ < 1

π cot (π z) = z^{- 1} - 2 \sum_{r \geq 1} ζ (2 r) z^{2 r - 1} .

(1)

The Bernoulli number generating function gives the same Laurent series in another form:

π cot (π z) = πi + \frac{2 πi}{e ^{2 πi z} - 1} = z^{- 1} + \sum_{r \geq 1} \frac{B _{2 r} ( 2 πi ) ^{2 r}}{( 2 r )!} z^{2 r - 1} .

(2)

The

B_{1}

term cancels the separate

πi

; the higher odd Bernoulli numbers vanish. Comparing Laurent coefficients therefore gives

- 2 ζ (2 r) = B_{2 r} (2 πi)^{2 r} / (2 r)!

, which is the stated real formula because

i^{2 r} = (- 1)^{r}

. The cotangent partial-fraction expansion justifies the convergent expansion before the coefficient comparison; a finite plot of partial sums alone would not prove the infinite identity.

Generalized Bernoulli number ( $B_{k, χ}$ )

 0  0

For a Dirichlet character

χ

of conductor

f

, define the generalized Bernoulli numbers by

\sum_{a = 1}^{f} χ (a) \frac{z e ^{a z}}{e ^{f z} - 1} = \sum_{k \geq 0} B_{k, χ} \frac{z ^{k}}{k !} .

(1)

They express special values of Dirichlet L-functions at nonpositive integers and occur in the interpolation formula for Kubota-Leopoldt p-adic L-functions.

Normal number ( $lim_{N \to \infty} F_{N} (w) = K^{- r}$ )

 1  0

A real number is normal in an integer base

K \geq 2

when every finite word of digits occurs in its positional notation with the same limiting digit block frequency as every other word of the same length. Write its fractional part as

x = 0. d_{1} d_{2} \dots

in base

K

, using the expansion that is not eventually all

K - 1

digits when two expansions are possible. For every length

r \geq 1

and every word

w \in {0, \dots, K - 1}^{r}

, the requirement is

lim_{N \to \infty} \frac{∣ { 1 \leq j \leq N - r + 1 : ( d _{j} , \dots , d _{j + r - 1} ) = w } ∣}{N - r + 1} = K^{- r} .

(1)

Occurrences overlap: the word

11

occurs twice in

111

. There are

K^{r}

possible words of length

r

, so

K^{- r}

is the equal share for each. In a decimal representation, this means frequency

1/10

for each digit,

1/100

for each pair, and

1/1000

for each triple, continuing through every finite length. The definition agrees with that used by Copeland and Erdős in their work on explicit normal numbers. ^[ref]

The appeal is that a precise, deterministic real number can have the same limiting digit block frequencies as repeated draws from a uniform distribution on a finite set, with independence between draws. Champernowne constant is an explicit example. Normality is useful for studying digit distribution, but balanced digits alone establish only a simply normal number, and a finite sample cannot establish any of these infinite limits.

Émile Borel introduced normal numbers and established their prevalence in his 1909 paper applying probability to number theory; the stronger all-base statement is discussed under absolutely normal number. ^[ref]

Digit block frequency ( $F_{N} (w)$ )

 0  0

For a finite prefix of

N \geq r

digits in positional notation, the digit block frequency

F_{N} (w)

of a length-

r

word

w

is its number of overlapping occurrences divided by

N - r + 1

, the number of available starting positions. All such digit block frequencies sum to one. The infinite limit used for a normal number can instead divide counts by

N

: the factor

(N - r + 1) / N

tends to one for fixed

r

For the six binary digits

010101

, the single-digit counts are three zeros and three ones. Its five adjacent pairs are

01, 10, 01, 10, 01

, giving

F_{6} (00) = F_{6} (11) = 0, F_{6} (01) = \frac{3}{5}, F_{6} (10) = \frac{2}{5} .

(1)

This example explains both the overlapping convention and the end correction in a finite sample. The corresponding infinite binary expansion has pair frequencies

0, 1/2, 1/2, 0

, rather than the four values

1/4

required of a normal number in base two.

Simply normal number ( $lim_{N \to \infty} F_{N} (a) = 1/ K$ )

 0  0

A real number is simply normal in base

K

if each individual digit in its positional notation has limiting digit block frequency

1/ K

. This is the length-one part of the definition of a normal number. It places no equal-frequency requirement on longer words.

For example,

x = 0.010101 \dots_{2} = 1/3

is a simply normal number in base two: each binary digit has frequency

1/2

. But

00

and

11

never occur, and

01

and

10

each have frequency

1/2

. Thus

x

is not a normal number in base two. Even a sequence that looks more complicated, such as the deterministic Thue–Morse sequence, must be tested against the actual digit block frequency definition; visual complexity is no substitute for it.

The decimal representation

y = 0.01234567890123456789 \dots

makes the same point in base ten. Every digit has frequency

1/10

, yet the only adjacent pairs are

01, 12, 23, 34, 45, 56, 67, 78, 89, 90.

(1)

Each has limiting digit block frequency

1/10

; the other ninety pairs have frequency zero. A normal number in base ten requires

1/100

for every one of the hundred pairs. This rational number is a simply normal number in base ten, but it is not a normal number in that base.

Champernowne constant ( $C_{10} = 0.123456789101112 \dots$ )

 1  0

Form Champernowne constant by using concatenation to join the decimal representations of the positive integers

1, 2, 3, \dots

after the decimal point. Champernowne proved in 1933 that this particular real number is a normal number in base ten. The construction is striking because its rule is completely explicit, while all finite words have the prescribed limiting digit block frequencies. ^[ref] Copeland and Erdős explicitly recall this result at the start of their own paper. ^[ref]

The first

100000

digits of Champernowne constant have the following exact counts, in digit order

0, 1, \dots, 9

(8642, 19753, 11111, 8642, 8642, 8642, 8642, 8642, 8642, 8642) .

(1)

For the

99999

adjacent pairs fully inside that prefix, the words

00, 01, 12, 99

occur

642, 1753, 2088, 753

times respectively. Thus, for example,

F_{100000} (12) = 2088/99999

, which is about

0.02088

, rather than

0.01

. The prefix ends partway through the decimal representation of

22222

; the many leading ones in earlier positive integers help explain the visible imbalance.

Figure 1.
Exact digit and adjacent-pair frequencies in two prefixes of 100000 decimal digits
. The upper panels compare single-digit frequencies and list exact counts. The lower panels show all hundred overlapping pair frequencies, each with denominator $99999$ , on the same vertical scale. The dashed $1/100$ line is the limiting reference for a normal number in base ten. In the periodic prefix, pairs $01$ through $89$ occur $10000$ times each and $90$ occurs $9999$ times; all other pairs are absent. **Details**.

These are finite counts, not a proof of the normal number theorem: a finite prefix can be followed by an all-zero tail. The theorem for Champernowne constant concerns the infinite limit, and establishes base-ten normality, rather than absolute normality. Nor do computations prove normality for familiar constants: the normality of Pi and Euler's number remains unproved, as discussed by Bailey and Borwein. ^[ref]

Normality and equidistribution under integer multiplication ( $x normal in base K ⟺ ({K^{n} x})_{n \geq 0} equidistributed$ )

 0  0

A real number

x

is a normal number in base

K

exactly when its iterates under the integer multiplication map on the circle,

T_{K} (x) = {K x}

, form an equidistributed sequence. Braces denote the fractional part. Multiplication by

K

shifts the positional notation one digit to the left:

T_{K}^{n} (x) = {K^{n} x} = 0. d_{n + 1} d_{n + 2} \dots in base K .

(1)

A length-

r

word with base-

K

integer value

a

specifies the half-open interval

[a / K^{r}, (a + 1) / K^{r})

, whose length is

K^{- r}

. Visiting that interval is exactly encountering that word at the next digit position. These digit intervals form arbitrarily fine grids, so their correct limiting visiting frequencies imply equidistribution on every interval. This converts a question about digits into one about a dynamical system. Bailey and Crandall develop this connection using equidistribution of the fractional parts of

K^{n} x

. ^[ref]

In base ten the word

12

corresponds to

[0.12, 0.13)

. For Champernowne constant, counting the visits

T_{10}^{n} (x)

for

0 \leq n \leq 99998

gives precisely the

2088

occurrences of

12

in its first

100000

digits. For

x = 1/3

, the base-two integer multiplication map on the circle instead alternates between

1/3

and

2/3

; it never visits

[0, 1/4)

, the interval for

00

. This two-point orbit is not an equidistributed sequence.

Absolutely normal number

 0  0

An absolutely normal number is a normal number in every integer base

K \geq 2

. This requires every finite word in every such positional notation to have its appropriate limiting digit block frequency. Knowing base-ten normality alone does not establish absolute normality; the base is part of the statement.

A modern route uses the Birkhoff ergodic theorem and ergodicity of integer multiplication on the circle. For each fixed base and digit interval, the time proportion equals its Lebesgue measure almost everywhere. The bases and finite words form countable sets, so a countable intersection of these measure-one sets still has Lebesgue measure one. For an absolutely normal number, the word

11

therefore has frequency

1/4

in base two,

1/9

in base three, and

1/100

in base ten. The same symbols represent different intervals in different bases.

Natural density ( $d (S)$ )

 1  0

For a set

S

of nonnegative integers, its natural density is the limiting proportion of the first

N

nonnegative integers that belong to

S

d (S) = lim_{N \to \infty} \frac{∣ S \cap { 0 , \dots , N - 1 } ∣}{N},

(1)

provided this limit exists. Write

C_{S} (N) = ∣ S \cap {0, \dots, N - 1} ∣

for the counting function. The numerator is a finite cardinality; the denominator is exactly

N

, including zero. Every existing natural density lies between zero and one.

For the even nonnegative integers

E = {0, 2, 4, \dots}

, there are

m

elements below

N = 2 m

and

m + 1

below

N = 2 m + 1

. Thus

C_{E} (N) = ⌈ N /2 ⌉

using the ceiling function, and

d (E) = 1/2

. For the square numbers

Q = {0, 1, 4, 9, \dots}

, the exact count for

N \geq 1

C_{Q} (N) = ⌊ N - 1 ⌋ + 1, d (Q) = 0.

(2)

The floor function counts the allowed indices

1, \dots, ⌊ N - 1 ⌋

, and the extra one counts zero. At

N = 10

, the square numbers below ten are

0, 1, 4, 9

, so the proportion is

4/10

; at

N = 100

, it is

10/100

. The count grows like the square root of

N

, while the denominator grows like

N

The prime numbers also have natural density zero. If

P

is their set, the Prime number theorem gives

C_{P} (N) \sim N / lo g N

, hence

C_{P} (N) / N \to 0

. The Prime number theorem is a substantial result about the count, rather than a consequence of the fact that there are infinitely many prime numbers. ^[ref]

Why use natural density when cardinality already measures size? The even nonnegative integers, the square numbers, and the prime numbers all have the same countably infinite cardinality, yet their proportions among large initial integer intervals differ. Natural density distinguishes frequent membership from sparse membership. Equivalently, under a uniform distribution on a finite set of

N

possible nonnegative integers,

C_{S} (N) / N

is the probability of landing in

S

. A set without natural density shows why this limiting proportion need not exist.

Figure 1.
Exact proportions below N: even integers, squares, and an alternating-block set
. Every point uses the count in ${0, \dots, N - 1}$ divided by $N$ , with zero included among the even integers and square numbers. The right panel marks exact block-boundary counts for a set without natural density. Its low and high proportions approach $1/3$ and $2/3$ along different subsequences. **Details**.

Set without natural density ( $A = ⋃_{k \geq 0} ([4^{k}, 2 \cdot 4^{k}) \cap Z)$ )

 0  0

Include the positive integers in

[1, 2), [4, 8), [16, 32), [64, 128), \dots

, and exclude the intervening integer intervals and zero. Equivalently, include

[2^{2 k}, 2^{2 k + 1}) \cap Z

for

k \geq 0

. Each included block is large enough to raise the running proportion; the following excluded block lowers it again.

With

C_{A} (N) = ∣ A \cap {0, \dots, N - 1} ∣

, the exact boundary counts follow from a geometric series:

C_{A} (4^{k}) = \sum_{j = 0}^{k - 1} 4^{j} = \frac{4 ^{k} - 1}{3}, C_{A} (2 \cdot 4^{k}) = \sum_{j = 0}^{k} 4^{j} = \frac{4 ^{k + 1} - 1}{3} .

(1)

The first sum is empty at

k = 0

. Dividing by the corresponding boundary, rather than using one denominator for both, gives

\frac{C _{A} ( 4 ^{k} )}{4 ^{k}} = \frac{1}{3} - \frac{1}{3 \cdot 4 ^{k}}, \frac{C _{A} ( 2 \cdot 4 ^{k} )}{2 \cdot 4 ^{k}} = \frac{2}{3} - \frac{1}{6 \cdot 4 ^{k}} .

(2)

For example,

C_{A} (16) = 1 + 4 = 5

, whereas

C_{A} (32) = 1 + 4 + 16 = 21

, yielding proportions

5/16

and

21/32

. For

4^{k} \leq N \leq 2 \cdot 4^{k}

, the exact count is

(4^{k} - 1) /3 + N - 4^{k}

; for

2 \cdot 4^{k} \leq N \leq 4^{k + 1}

it stays

(4^{k + 1} - 1) /3

. Hence the proportion increases through each included block and decreases through each excluded block. These boundary subsequences give the actual limit inferior and limit superior:

lim inf_{N \to \infty} \frac{C _{A} ( N )}{N} = \frac{1}{3}, lim sup_{N \to \infty} \frac{C _{A} ( N )}{N} = \frac{2}{3} .

(3)

Since these differ,

A

has no natural density. Its upper asymptotic density still records its largest limiting proportion.

Upper asymptotic density ( $\overline{d} (A)$ )

 0  0

For a subset

A

of the positive integers, its upper asymptotic density is

\overline{d} (A) = lim sup_{N \to \infty} \frac{∣ A \cap { 1 , \dots , N } ∣}{N} .

(1)

The limit superior keeps the largest limiting proportion even when the running proportions oscillate. Because they lie in

[0, 1]

, this limit superior always exists in

[0, 1]

. If natural density exists, upper asymptotic density equals it.

The convention here uses

1, \dots, N

, while natural density above uses

0, \dots, N - 1

. Replacing one interval by the other changes a count by at most one, so the proportions differ by at most

1/ N

and have the same limit superior. For the set without natural density above, the count in

{1, \dots, 16}

is six rather than five, because

16

is included and zero is absent. Nevertheless its upper asymptotic density is exactly

2/3

. The even positive integers have upper asymptotic density

1/2

and the prime numbers have upper asymptotic density zero.

The useful feature is that a large proportion along arbitrarily large initial integer intervals already supplies structure. The Szemerédi theorem says that positive upper asymptotic density forces arithmetic progressions of every finite length, with positive common difference, even without an existing natural density. Szemerédi's 1975 paper resolved this general finite-length problem; it makes density a bridge from counting to additive structure. ^[ref]

Full-density sequence

 0  0

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.

Lagrange's four-square theorem ( $n = a^{2} + b^{2} + c^{2} + d^{2}$ )

 2  0

Every nonnegative integer is a sum of squares with four terms, with zero terms allowed. Precisely, for every integer

n \geq 0

, there exist nonnegative integers

a, b, c, d

such that

n = a^{2} + b^{2} + c^{2} + d^{2} .

(1)

Allowing arbitrary integer roots gives the same statement: changing a root to its absolute value leaves the resulting square number unchanged. Four is a uniform upper bound on the number of nonzero terms, rather than a demand for four positive terms. Repeated square numbers are allowed. Conrad states the positive case and explicitly explains the role of zero terms;

n = 0

follows by taking all four roots zero. ^[ref]

The small cases make the convention visible:

01237 = 0^{2} + 0^{2} + 0^{2} + 0^{2}, = 1^{2} + 0^{2} + 0^{2} + 0^{2}, = 1^{2} + 1^{2} + 0^{2} + 0^{2}, = 1^{2} + 1^{2} + 1^{2} + 0^{2}, = 2^{2} + 1^{2} + 1^{2} + 1^{2} .

(2)

In particular,

1

could not be a sum of squares with four strictly positive roots, since each term would be at least one. Geometrically, a square of integer side length

a

has area

a^{2}

: the theorem says that any nonnegative whole-number total area can be split into at most four such square areas. It does not assert that those squares tile one larger square or a prescribed rectangle.

Figure 1.
Four-square representations as areas counted in unit cells
. The roots for $7, 23, 28, 31$ were found by enumerating nonnegative four-tuples. Each panel has the same unit length, and each little cell has area one. The four separate squares illustrate addition of areas, with no claim about tiling a prescribed shape. These are exact arithmetic examples, not measured data. **Details**.

Why does the fourth term matter? Two square numbers do not suffice for

3

: in modular arithmetic, a square number has remainder zero or one modulo four, so their sum cannot be three modulo four. The sum of two squares theorem gives a complete criterion for the positive integers representable with two terms. Even three terms leave gaps. A square number has remainder

0, 1,

4

modulo eight; adding three of these, with repetition allowed, never gives seven modulo eight. Thus

7, 15, 23, 31, \dots

cannot be sums of three square numbers, although Lagrange's four-square theorem represents all of them with four. This also proves that the bound four cannot be reduced to three.

The modulo-eight obstruction is not the only way that three terms can fail. For example,

28

needs four: if three square numbers added to

28

, their remainders modulo four would force all three roots even. Dividing by four would then express

7

as a sum of three square numbers, contradicting the preceding calculation. These short checks explain the examples without requiring a full classification of sums of three square numbers.

Figure 2.
Minimum number of nonzero square terms for integers from one to one hundred
. Each cell is labelled by the positive integer being represented; its colour records the least number of nonzero square numbers whose sum equals it. Direct enumeration gives $10$ requiring one term, $33$ two, $42$ three, and $15$ four. Zero is omitted from the grid and requires no nonzero terms. Zero padding converts every representation into four slots. This finite computation illustrates Lagrange's four-square theorem; it does not prove its assertion for all nonnegative integers. **Details**.

The practical benefit of Lagrange's four-square theorem is an existence guarantee for a family of Diophantine equations: for every nonnegative integer

n

, the displayed equation has an integer solution. It does not specify a unique solution. For instance,

65 = 8^{2} + 1^{2} + 0^{2} + 0^{2} = 7^{2} + 4^{2} + 0^{2} + 0^{2} = 6^{2} + 4^{2} + 3^{2} + 2^{2}

. To find a representation by a finite search, enumerate

0 \leq d \leq c \leq b \leq a \leq ⌊ n ⌋

and test the sum. The floor function supplies a finite bound because no single term can exceed

n

, and sorting roots removes duplicate orderings without discarding any possible sum. The theorem guarantees that the search succeeds.

A greedy algorithm that repeatedly subtracts the largest available square number need not find four terms: for

23

it chooses

16 + 4 + 1 + 1 + 1

, while

23 = 9 + 9 + 4 + 1

uses four. The appeal of the theorem is this gap between local choices and a global promise: individual square numbers become farther apart, and two or three terms leave arithmetic obstructions, yet four terms cover every nonnegative integer.

For historical orientation, Conrad dates Lagrange's four-square theorem to

1770

and identifies the memoir as Démonstration d'un théorème d'arithmétique: it appeared in the Berlin Academy's volume for the year

1770

, published in

1772

, pages

123

–

133

. Keeping the volume year and publication year distinct avoids an apparent conflict between dates. ^[ref]

Analytic number theory

 1  0

Analytic number theory studies integers, prime numbers, and arithmetic functions using tools from real analysis and complex analysis, especially Dirichlet series and their singularities.

Hardy-Littlewood circle method

 0  0

The circle method represents a weighted additive count as an integral of products of exponential sums against a character. Near rationals with small denominator, major arcs produce a structured main term involving a singular series and an archimedean singular integral. Away from those rationals, minor arcs require cancellation bounds. The partition and approximation estimates depend on the problem; a formal integral alone is not a positivity proof.

Vinogradov's three-primes theorem ( $n = p_{1} + p_{2} + p_{3} (n sufficiently large and odd)$ )

 0  0

Every sufficiently large odd integer is a sum of three primes, with repetitions allowed. The weighted count is asymptotic to

S (n) n^{2} /2

. Siegel–Walfisz theorem controls the major arcs, and Type I/II estimates for the prime exponential sum make the minor arcs negligible. Removing prime-power contributions gives genuine prime representations. This is the sufficiently-large theorem, not by itself a proof for every small odd integer.

Singular series ( $S (n)$ )

 0  0

A singular series assembles the local congruence densities in an additive counting asymptotic. For three prime summands it is

\sum_{q \geq 1} μ (q) c_{q} (n) / φ (q)^{3}

, with Ramanujan sum

c_{q} (n)

. Its Euler product vanishes for even

n

and has a uniform positive lower bound for odd

n

. Different additive problems have different local factors, so this is a specific instance rather than a universal formula.

Minor arc

 0  0

Minor arcs are the complement of the specified major arcs. They contribute an error only when a suitable pointwise or mean-value cancellation estimate is proved; their name does not imply that their measure is small.

Major arc

 0  0

In a circle-method problem of scale

n

, major arcs are neighborhoods of reduced rational points

a / q

with small denominator, where the relevant exponential sum is approximated using distribution in residue classes. For the three-prime problem one may take

q \leq (lo g n)^{B}

and

∣ θ - a / q ∣ \leq (lo g n)^{B} / n

, with suitably fixed

B

L-function ( $L (s)$ )

 1  0

An L-function is an arithmetic function given initially by a Dirichlet series and often an Euler product, with analytic continuation and a functional equation in important cases. Dirichlet L-functions and L-functions of cusp forms are basic examples; p-adic L-functions interpolate suitably modified special values.

Hasse–Weil zeta function ( $Z (V, s)$ )

 1  0

The Hasse–Weil zeta function of an algebraic variety over a number field is assembled from local point-counting factors at finite places. At a good place with residue field of size

q

, the factor is

Z (V_{q}, q^{- s})

, where

Z (V_{q}, T) = exp (\sum_{n \geq 1} # V_{q} (F_{q^{n}}) T^{n} / n)

. Defining all bad-place factors requires a specified integral model or convention. The zeta function of an elliptic curve over a finite field is a local factor, rather than this global product.

Hasse-Weil L-function ( $L (E / F, s) = \prod_{v} det (1 - Frob_{v} N v^{- s} ∣ V_{ℓ} (E)^{I_{v}})^{- 1}$ )

 0  0

For an elliptic curve over a number field, its Hasse-Weil L-function is the product of the local factors determined by its Tate module. At a good finite place, the factor is

(1 - a_{v} N v^{- s} + N v^{1 - 2 s})^{- 1}

, with

a_{v} = N v + 1 - # E (κ (v))

. At a bad place use the inertia-invariant subspace and an auxiliary prime different from the residue characteristic. For a CM elliptic curve with all endomorphisms defined over the base, this factors as the product of the two conjugate Hecke L-functions.

Hecke L-function ( $L (ψ, s) = \prod_{q ∤ f} (1 - ψ (q) N q^{- s})^{- 1}$ )

 0  0

The L-function of a Hecke character is initially the displayed Euler product over prime ideals away from its conductor. The equivalent Dirichlet series sums

ψ (a) N a^{- s}

over integral ideals prime to the conductor. For a CM elliptic curve with its endomorphisms defined over the base, its Hasse-Weil L-function factors into the two conjugate Hecke L-functions.

p-adic L-function ( $L_{p} (s)$ )

 1  0

A p-adic L-function is a

p

-adic analytic function or measure interpolating suitably adjusted special values of an L-function. The Kubota-Leopoldt p-adic L-function is the basic example attached to a Dirichlet character.

Kubota-Leopoldt p-adic L-function ( $L_{p} (χ, s)$ )

 0  0

For an even Dirichlet character

χ

, the Kubota-Leopoldt function interpolates generalized Bernoulli values with the relevant Euler factor and Teichmüller character adjustment. If

χ \neq = 1

, it can be encoded by an integral power series. For

u = 1 + p

, the

p

-ramified convention is

g_{χ} (u^{1 - s} - 1) = L_{p} (χ, s)

. The trivial character requires separate treatment of the pole.

p-adic zeta pseudomeasure ( $\int x^{k} d ζ_{p} = (1 - p^{k - 1}) ζ (1 - k) (k \geq 2 even)$ )

 0  0

G = Z_{p}^{\times} / {\pm 1}

, this element of the total quotient ring of the Iwasawa algebra becomes an integral measure after multiplication by every difference

[a] - [1]

. Its even moments interpolate the displayed Euler-corrected zeta values. Its trivial-character component has a pole, so the pseudomeasure itself must not be treated as an element of the integral group algebra. Multiplication by the augmentation ideal removes the pole.

Linnik's theorem ( $p (a, q) ≪ q^{L} ((a, q) = 1)$ )

 1  0

There is an absolute finite exponent

L

bounding the least prime in any reduced arithmetic progression by a constant times

q^{L}

. The multiplicative large sieve inequality is one of the tools in proofs of this theorem.

Character sum ( $\sum_{n \in S} χ (n)$ )

 0  0

A sum of character values over a set. Arithmetic cancellation, rather than the termwise absolute-value bound, is the useful feature. A Gauss sum of a Dirichlet character is a weighted example, and the Pólya–Vinogradov inequality bounds interval sums.

Pólya–Vinogradov inequality ( $∣ \sum_{M < n \leq M + N} χ (n) ∣ ≪ q lo g q$ )

 0  0

For a primitive nonprincipal Dirichlet character modulo

q

, finite Fourier inversion theorem and the primitive Gauss magnitude give this bound uniformly in the interval. Bound the exponential sums by

C ∥ a / q ∥^{- 1}

and sum the resulting harmonic series. The general Gauss identity follows from the prime-power identity by the Chinese remainder theorem.

Prime sum

 0  0

A prime sum is a summation indexed by prime numbers, for example

\sum_{p \leq x} 1/ p

. The indexing restriction distinguishes it from a sum over all positive integers.

Bombieri–Vinogradov theorem

 1  0

For every

A > 0

there is

B > 0

such that, for

Q \leq x^{1/2} / lo g^{B} x

\sum_{q \leq Q} max_{(a, q) = 1} max_{2 \leq y \leq x} ψ (y; q, a) - \frac{y}{ϕ ( q )} ≪_{A} \frac{x}{l o g ^{A} x} .

(1)

Here

ψ (y; q, a)

is the Chebyshev function in an arithmetic progression and

ϕ

is the Euler totient function. Partial summation gives the corresponding result for the prime-counting function and the offset logarithmic integral function. The theorem controls the total error over many moduli; it need not give the same bound for each individual modulus.

Weighted arithmetic-progression error bound

 0  0

Let

E_{q} = max_{(a, q) = 1} ∣ π (x; q, a) - Li (x) / ϕ (q) ∣

. For

Q \leq x^{1 - η}

, the Brun–Titchmarsh theorem and Cauchy-Schwarz inequality give

\sum_{q \leq Q} 3^{ω (q)} E_{q} ≪_{η} (\sum_{q \leq Q} E_{q})^{1/2} (\frac{x}{l o g x} \sum_{q \leq Q} \frac{9 ^{ω (q)}}{ϕ ( q )})^{1/2} .

(1)

Write each summand as

E_{q} 3^{ω (q)} E_{q}

, then use

E_{q} ≪_{η} x / (ϕ (q) lo g x)

Exponential sum

 0  0

A finite sum of complex exponentials, such as

S (θ) = \sum_{n} a_{n} e (n θ)

with

e (t) = exp (2 πi t)

, is an exponential sum. Cancellation in an exponential sum between its terms can make it much smaller than the sum of their absolute values.

Weyl differencing

 0  0

Taking a finite difference lowers the degree of a polynomial phase. For

S (θ) = \sum_{x = 1}^{n} e (θP (x))

, expand

∣ S ∣^{2}

by shifts

h

and apply the Cauchy-Schwarz inequality to those shift sums. This gives

∣ S ∣^{4} \leq 2 n \sum_{h, l} \sum_{x \in I_{h, l}} e (θ Δ_{h} Δ_{l} P (x))

, where

I_{h, l}

enforces that

x, x + h, x + l, x + h + l

lie in

[1, n]

. Although individual terms can be complex, the entire sum is real and nonnegative because it equals a sum of squares. For

P (x) = x^{3}

, the phase is

3 h l (2 x + h + l)

Weyl inequality ( $∣ S ∣ ≪_{k, η} N^{1 + η} (q^{- 1} + N^{- 1} + q N^{- k})^{2^{1 - k}}$ )

 0  0

For a real degree-

k

polynomial with leading coefficient

θ

k \geq 2

, and coprime integers

a, q

satisfying

∣ θ - a / q ∣ \leq q^{- 2}

, the displayed bound applies to its exponential sum over

1 \leq n \leq N

. Repeated Weyl differencing reduces the phase to slope

k! θ h_{1} \dots h_{k - 1}

. A geometric-sum estimate, the subpower bound for the divisor function and the reciprocal fractional-part sum near a rational complete the estimate. The arbitrary positive exponent

η

absorbs divisor bounds and logarithms.

Cubic Weyl inequality ( $∣ S (θ) ∣ ≪_{η} n^{1 + η} (q^{- 1} + n^{- 1} + q / n^{3})^{1/4}$ )

 0  0

S (θ) = \sum_{x \leq n} e (θ x^{3})

and

∣ θ - a / q ∣ \leq q^{- 2}

with

(a, q) = 1

, the displayed estimate holds. Twice applying Weyl differencing bounds

∣ S ∣^{4}

O (n^{3} + n \sum_{0 < ∣ h ∣, ∣ l ∣ < n} min (n, ∥6 θ h l ∥^{- 1}))

. Group by

6 h l

and use the subpower bound for the divisor function. The reciprocal fractional-part sum near a rational bounds the resulting sum by

O (lo g (2 q) (n^{3} / q + n^{2} + n + q))

. Take fourth roots, absorbing logarithms into

n^{η}

when

q \leq n^{3}

; for larger

q

the trivial bound suffices. Leiden lecture notes, Section 7.2 develop this cubic differencing estimate.

Hua's lemma ( $\int_{0}^{1} ∣ \sum_{x \leq n} e (θ x^{k}) ∣^{2^{j}} d θ ≪_{k, j, η} n^{2^{j} - j + η}$ )

 1  0

For

1 \leq j \leq k

and every

η > 0

, the displayed estimate bounds a mean value of a polynomial exponential sum. For cubes its eighth-moment bound is

O_{η} (n^{5 + η})

. It complements pointwise Weyl differencing estimates: a ninth moment over a region is bounded by its supremum there times this eighth moment. Leiden lecture notes, Section 8.1 give the cubic formulation.

Cubic eighth-moment proof by differencing ( $\int_{0}^{1} ∣ \sum_{x \leq n} e (θ x^{3}) ∣^{8} d θ ≪_{η} n^{5 + η}$ )

 0  0

Write

S (θ) = \sum_{x \leq n} e (θ x^{3})

and

I_{j} = \int_{0}^{1} ∣ S ∣^{j}

. Character orthogonality gives

I_{2} = n

. For

I_{4}

, fix the difference

D = x^{3} - y^{3}

. If

D = 0

, there are

n^{2}

choices for the two equal pairs. If

D \neq = 0

, any solution

z^{3} - w^{3} = D

has

z - w ∣ D

; fixing this divisor gives a quadratic equation for

w

, hence at most two choices. The subpower bound for the divisor function yields

I_{4} ≪_{η} n^{2 + η}

The twice-differenced inequality in Weyl differencing reads

∣ S ∣^{4} \leq 2 n \sum_{v} c_{v} e (θ v)

, with

c_{v}

counting triples

(h, l, x)

for which

v = 3 h l (2 x + h + l)

and all four shifted arguments are in

[1, n]

. Thus

c_{0} ≪ n^{2}

, and

c_{v} ≪_{η} n^{η}

for

v \neq = 0

: the product

h l

divides

v

, and the remaining equation determines

x

. The Fourier coefficients

r (v)

∣ S ∣^{4}

are nonnegative counts, with

r (0) = I_{4}

and

\sum_{v} r (v) = n^{4}

. Multiply the inequality by

∣ S ∣^{4}

and integrate. It follows that

I_{8} ≪ n (n^{2} I_{4} + n^{η} n^{4}) ≪_{η} n^{5 + η}

, after choosing the divisor-bound exponents small enough.

Power Gauss sum over a prime field ( $G_{a, p} = p^{- 1} \sum_{x \in F_{p}} e^{2 πia x^{k} / p}$ )

 0  0

For

a \neq = 0

in the finite field

F_{p}

, put

d = g cd (k, p - 1)

. The multiplicative group of a finite field is cyclic, and character orthogonality expresses the number of

k

th roots of

y \neq = 0

\sum_{χ^{d} = 1} χ (y)

. The trivial character contributes

- 1

, cancelling the

x = 0

term. Each of the remaining

d - 1

Gauss sums of Dirichlet characters has modulus

p

, by the prime-field character Gauss sum identity. Consequently

∣ G_{a, p} ∣ \leq (d - 1) / p \leq k / p

Three power summands over a large prime field ( $p > k^{6} ⟹ F_{p} = {u^{k} + v^{k} + w^{k} : u, v, w \in F_{p}}$ )

 0  0

For

S (a) = \sum_{u} e (a u^{k} / p)

, character orthogonality counts representations of

x

p^{- 1} \sum_{a} S (a)^{3} e (- a x / p)

. Its zero-frequency term is

p^{2}

. The power Gauss sum over a prime field bounds the other terms in total by

k^{3} p^{3/2}

, strictly less than

p^{2}

when

p > k^{6}

. Every residue class therefore has a representation.

Quadratic exponential sum ( $\sum_{n = 1}^{N} e (α n^{2} + β n)$ )

 0  0

A quadratic exponential sum has a polynomial phase of degree two. Its multiplicative derivative at lag

h

has the linear phase

2 α hn

up to a constant factor. This degree reduction lets the Van der Corput inequality for finite scalar sequences reduce its size to estimates for finite geometric series.

Quadratic Weyl inequality ( $∣ \sum_{n = 0}^{N} e (α n^{2}) ∣ ≪ ((N^{2} / q + N + q) lo g (2 N))^{1/2}$ )

 0  0

For coprime integers

a, q

with

1 \leq q \leq Q

and

∣ α - a / q ∣ \leq 1/ (qQ)

, expand the squared quadratic exponential sum by its difference

h

. The exponential geometric sum bound gives

∣ S ∣^{2} ≪ N + \sum_{h \leq N} min (N + 1, ∥2 α h ∥^{- 1})

. In each block of length at most

q /4

, the rotations

2 α h

are separated by at least

1/ (2 q)

: the reduced denominator of

2 a / q

is at least

q /2

, and the approximation error between two block points is at most

1/ (2 q)

. The separated reciprocal-distance sum bounds each block by

O (N + q lo g (2 N))

. There are

O (N / q + 1)

blocks, giving the displayed inequality. For bounded

q

the trivial estimate supplies the same conclusion.

Vinogradov mean value ( $J_{k, r} (Z) = \int_{[0, 1]^{r}} ∣ \sum_{z \leq Z} e (\sum_{j = 1}^{r} θ_{j} z^{j}) ∣^{2 k} d θ$ )

 0  0

By orthogonality of integer Fourier modes, this integral counts pairs of

k

-tuples with the same first

r

power sums. Diagonal pairs give

J_{k, r} (Z) ≫ Z^{k}

. There are

O_{k, r} (Z^{r (r + 1) /2})

possible moment vectors; the Cauchy-Schwarz inequality gives

J_{k, r} (Z) ≫ Z^{2 k - r (r + 1) /2}

. Upper bounds measure how much arithmetic coincidence remains beyond these necessary contributions, and enter the Vinogradov mean-value method for a bilinear exponential sum.

Vinogradov mean-value method for a bilinear exponential sum ( $U = \sum_{x, y \leq Z} e (\sum_{j} α_{j} x^{j} y^{j})$ )

 0  0

Expand moments of the inner sum and group equal power-sum differences. Their multiplicities are bounded by

J_{k, r} (Z)

through the Cauchy-Schwarz inequality. Two applications of the Holder inequality yield a bound for

∣ U ∣^{4 k^{2}}

containing

Z^{8 k^{2} - 4 k} J_{k, r} (Z)^{2}

and a product of short geometric-sum bounds over the moment differences. Thus a sharp mean-value estimate combines with rational approximation or spacing of the coefficients to prove cancellation. When all coefficients are integers,

U = ⌊ Z ⌋^{2}

, so mean-value estimates alone cannot force cancellation.

Bilinear shift averaging for a logarithmic phase ( $S = Z^{- 2} \sum_{n \in I} \sum_{x, y \leq Z} (n + x y)^{- i t} + O (Z^{2})$ )

 0  0

Translating an integer interval by

x y

changes a sum of unit-modulus terms by at most

2 x y

. Averaging gives the displayed formula. For

n ≍ N

Z = N^{2/5}

, expand

- t lo g (1 + x y / n)

to degree

r = ⌊ 5.01 lo g t / lo g N ⌋

. Its remainder is at most

t N^{- (r + 1) /5} < t^{- 1/500}

. This reduces the logarithmic exponential sum to bilinear polynomial sums while keeping explicit boundary and approximation errors.

Van der Corput sum-integral lemma ( $\sum_{a < n \leq b} e (f (n)) = \int_{a}^{b} e (f (x)) d x + O ((1 - δ)^{- 1})$ )

 0  0

For a real

C^{1}

phase with continuous monotone derivative and

∣ f^{'} ∣ \leq δ < 1

, the sum-integral discrepancy has the displayed uniform bound. Periodization and the Dirichlet-Jordan convergence theorem express it as symmetric nonzero Fourier modes. Integration by parts gives endpoint terms and reciprocal-derivative variations. Monotonicity bounds their total variation by

\sum_{h \neq = 0} 2 δ / (h^{2} - δ^{2}) = O ((1 - δ)^{- 1})

. Pairing the leading

1/ h

endpoint terms reduces them to the uniformly bounded sine series. The exclusion of integer nonzero frequencies is essential.

Cancellation in an exponential sum

 0  0

Cancellation occurs when different complex numbers in an exponential sum have directions that reduce the absolute value of their sum. For example, the orthogonality of roots of unity makes

\sum_{a = 0}^{p - 1} e (a / p) = 0

for every integer

p > 1

, despite all terms having absolute value one.

Probabilistic number theory

 1  0

Probabilistic number theory studies arithmetic functions and integer sets through probability distributions, concentration, and limit theorems.

Erdős-Kac theorem

 0  0

For a real strongly additive arithmetic function with uniformly bounded values on primes, put

A (x) = \sum_{p \leq x} f (p) / p

and

B (x)^{2} = \sum_{p \leq x} f (p)^{2} / p

. If

B (x) \to \infty

, then

(f (n) - A (N)) / B (N)

under uniform sampling from

[N]

converges to the standard normal distribution. For the prime omega function, the mean and variance scales are

lo g lo g N

Centered moment comparison for additive arithmetic functions

 0  0

If a strongly additive arithmetic function

g

is supported on primes up to

y

, its

j

th uniform central moment differs from the independent Bernoulli random variables model with probabilities

1/ p

O (j y^{j} (\sum_{p \leq y} ∣ g (p) ∣)^{j} / N)

. Expansion of divisibility indicator functions reduces the comparison to

⌊ N / d ⌋ / N = 1/ d + O (1/ N)

Cramér model

 0  0

The Cramér model selects integers

n \geq 3

independently with probability

1/ lo g n

, and conventionally sets

U_{1} = 0

U_{2} = 1

. It is a random model for the distribution of primes, not an assertion of independence for actual prime numbers.

Cramér model prime-gap upper bound

 0  0

P_{n}

are the increasing selected integers in the Cramér model, then almost surely

lim sup_{n} (P_{n + 1} - P_{n}) / (lo g P_{n})^{2} \leq 1

. A zero block of length

(1 + ϵ) (lo g k)^{2}

after

k

has summable probability, so the Borel-Cantelli first lemma excludes these blocks eventually.

Multiplication table problem ( $M (N) = # {ab : 1 \leq a, b \leq N}$ )

 0  0

The multiplication table problem asks how many distinct integers occur as

ab

with

1 \leq a, b \leq N

. Counting the

N^{2}

pairs greatly overcounts the distinct products.

Multiplication table bound from distinct prime factors

 0  0

Concentration of the prime omega function near

lo g lo g N

, together with

ω (ab) = ω (a) + ω (b) - ω (g cd (a, b))

and the bounded mean of

ω (g cd (a, b))

, gives

M (N) ≪ N^{2} / lo g lo g N

. This elementary argument uses only distinct prime factors.

Turán-Kubilius inequality ( $E_{N} ∣ f - A_{f} (N) ∣^{2} ≪ B_{f} (N)^{2}$ )

 1  0

For an additive arithmetic function

f

N^{- 1} \sum_{n \leq N} ∣ f (n) - A_{f} (N) ∣^{2} ≪ B_{f} (N)^{2}

, where

A_{f}

is the mean of an additive arithmetic function and

B_{f} (N)^{2} = \sum_{p^{k} \leq N} ∣ f (p^{k}) ∣^{2} / p^{k}

. The implied constant is absolute.

Landau theorem for a Dirichlet series with nonnegative coefficients

 0  0

If a Dirichlet series with nonnegative coefficients has finite abscissa of convergence

σ_{c}

, then the function it defines has a singularity at the real point

s = σ_{c}

. Consequently, if that function extends holomorphically across every real point, the original series converges for every real

s

Nonvanishing of a nonprincipal Dirichlet L-function at one

 0  0

For every nonprincipal Dirichlet character,

L (1, χ) \neq = 0

. A nonreal character is covered by Euler product positivity for L-function nonvanishing at height zero, since its squared character is nonprincipal.

For a real character, suppose

L (1, χ) = 0

. The simple zeta pole would cancel, making

F (s) = ζ (s) L (s, χ)

an entire function. Its nonnegative zeta-times-real-L coefficients satisfy

a_{n} \geq 0

and

a_{m^{2}} \geq 1

. Termwise derivatives at two give

(- 1)^{k} F^{(k)} (2) = \sum_{n} a_{n} (lo g n)^{k} n^{- 2}

. The Taylor series of this entire function at two converges at zero. Every term there is nonnegative, and Tonelli theorem identifies its sum as

F (0) = \sum_{k \geq 0} \frac{2 ^{k}}{k !} \sum_{n} \frac{a _{n} ( l o g n ) ^{k}}{n ^{2}} = \sum_{n} a_{n} .

(1)

The last series diverges because all square coefficients are at least one. This contradiction proves the claim. It is the positive-coefficient mechanism behind the more general Landau theorem for a Dirichlet series with nonnegative coefficients.

Chebyshev function in an arithmetic progression ( $ψ (x; q, a)$ )

 0  0

For

(a, q) = 1

ψ (x; q, a) = \sum_{n \leq x n \equiv a (mod q)} Λ (n) .

(1)

The Orthogonality of Dirichlet characters expresses it in terms of character-twisted Von Mangoldt functions.

Classical zero-free region for Dirichlet L-functions

 0  0

There is an absolute

c > 0

such that the Dirichlet L-functions modulo

q

have no zero in

ℜ s \geq 1 - \frac{c}{l o g ( q ( ∣ℑ s ∣ + 2 ))}

(1)

apart from at most one real simple zero belonging to a real nonprincipal character.

Uniqueness of a possible exceptional real Dirichlet zero ( $# {β \in [1 - c / lo g q, 1] : L (β, χ) = 0} \leq 1$ )

 0  0

For primitive real nonprincipal Dirichlet characters, there is an absolute

c > 0

with at most one zero in this interval, counted with multiplicity. Positivity of

- ζ^{'} / ζ - L^{'} / L

and the local partial fractions give

0 \leq 1/ (σ - 1) + C lo g q - \sum (σ - β)^{- 1}

. Testing

σ = 1 + a / lo g q

with small fixed

a

rules out two nearby real zeros. Any possible zero is consequently simple; existence is not asserted.

Siegel zero

 1  0

An exceptional zero is the possible real simple zero

β

omitted from the otherwise uniform classical zero-free region for Dirichlet L-functions. It belongs to a real nonprincipal primitive Dirichlet character and satisfies

β < 1

 Articles were limited to the first 100 out of 969 total.

 View more

Number theory is a branch of mathematics that deals with the properties and relationships of numbers, particularly integers. It is one of the oldest areas of mathematics and has a rich historical background, dating back to ancient civilizations. Number theory explores various topics, including: 1. **Prime Numbers**: The study of prime numbers (integers greater than 1 that have no positive divisors other than 1 and themselves) and their distribution.

 Read the full article

Number theory by

Ciro Santilli  40 Updated 2025-07-16

 Read the full article

  See all articles in the same topic Create my own version

 Discussion (0)  Subscribe (1) New discussion

 Discussion (0) New discussion