This chapter is a collection of basic material on probability theory, information theory, complexity theory, number theory, abstract algebra, and finite fields that will be used throughout this book. Further background and proofs of the facts presented here can be found in the references given in §2.7. The following standard notation will be used throughout:

ℤ denotes the set of integers; that is, the set {…, −2, −1, 0, 1, 2, …}.

ℚ denotes the set of rational numbers; that is, the set { a b | a , b ∈ ℤ , b ≠ 0 } https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429466335/81e205fb-b60a-4276-b51a-603b35ce55a6/content/eq186.tif"/> .

ℝ denotes the set of real numbers.

π is the mathematical constant; π ≈ 3.14159.

e is the base of the natural logarithm; e ≈ 2.71828.

[a, b] denotes the integers x satisfying a ≤ x ≤ b.

⌊x⌋ is the largest integer less than or equal to x. For example, ⌊5.2⌋ = 5 and ⌊−5.2⌋ = −6.

⌈x⌉ is the smallest integer greater than or equal to x. For example, ⌈5.2⌉ = 6 and ⌈−5.2⌈ = −5.

If A is a finite set, then |A| denotes the number of elements in A, called the cardinality of A.

a ∈ A means that element a is a member of the set A.

A ⊆ B means that A is a subset of B.

A ⊂ B means that A is a proper subset of B; that is A ⊆ B and A ≠ B.

The intersection of sets A and B is the set A ⋂ B = {x | x ∈ A and x ∈ B}.

The union of sets A and B is the set A ⋃ B = {x | x ∈ A or x ∈ B}.

The difference of sets A and B is the set A − B = {x | x ∈ A and x ∉ B}.

The Cartesian product of sets A and B is the set A × B = {(a, b) | a ∈ A and b ∈ B}. For example, {a ₁, a ₂} × {b ₁, b ₂, b ₃} = {(a ₁, b ₁), (a ₁, b ₂), (a ₁, b ₃), (a ₂, b ₁), (a ₂, b ₂), (a ₂, b ₃)}.50

A function or mapping f : A → B is a rule which assigns to each element a in A precisely one element b in B. If a ∈ A is mapped to b ∈ B then b is called the image of a, a is called a preimage of b, and this is written f(a) = b. The set A is called the domain of f, and the set B is called the codomain of f.

A function f : A → B is 1 − 1 (one-to-one) or injective if each element in B is the image of at most one element in A. Hence f(a ₁) = f(a ₂) implies a ₁ = a ₂.

A function f : A → B is onto or surjective if each b ∈ B is the image of at least one a ∈ A.

A function f : A → B is a bijection if it is both one-to-one and onto. If f is a bijection between finite sets A and B, then |A| = |B|. If f is a bijection between a set A and itself, then f is called a permutation on A.

ln x is the natural logarithm of x; that is, the logarithm of x to the base e.

lg x is the logarithm of x to the base 2.

exp(x) is the exponential function e^x .

∑ i = 1 n a i https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429466335/81e205fb-b60a-4276-b51a-603b35ce55a6/content/eq187.tif"/> denotes the sum a ₁ + a ₂ + · · · + a_n .

∏ i = 1 n a i https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429466335/81e205fb-b60a-4276-b51a-603b35ce55a6/content/eq188.tif"/> denotes the product a ₁ · a ₂ ….. a_n .

For a positive integer n, the factorial function is n! = n(n − 1) (n − 2) · · · 1. By convention, 0! = 1.