Discrete Math Notation

In this class, we must express mathematical operations in a rigorous fashion, in order to (a) understand their structure and function, (b) predict consequences of changing function or procedure parameters, and (c) have a unified basis for comparing algorithms. Thus, we provide the following brief theoretical introduction.
NOTE: Bold-italic-face titles or names denote special terms that we will use in class.

1. Sets and Set Operations

Sets are the basic entities and are the building blocks of mappings that we will subsequently use to define images. A few concepts and conventions are noteworthy:

Sets are customarily denoted by upper-case letters in roman (regular) or italic face (e.g., A, G), or by the empty set &Oslash.
Value Sets or Alphabets are denoted by bold upper-case letters from the head of the alphabet (e.g., A, B, ...). Additionally, we call F the generalized value set. Commonly-used value sets include the

• Natural numbers: N

• Integers: Z

• Real numbers: R

• Complex numbers: C

Furthermore, we have the integers modulo n, which are denoted by Z_n. In the special case of the binary numbers, we write B Z₂ for purposes of brevity.
Intervals. Occasionally, we use a concise specification of a contiguous subset of a given set, called an interval. For example, [1,4]Z denotes the set {1,2,3,4}, while the half-open interval (1,4]Z denotes the set {2,3,4}. Similarly, (2,4]R = {xR: 2 < x 4}.
Point Sets, Domain Sets, or Domains are denoted by bold upper-case letters from the tail of the alphabet (e.g., U, V, W, X, and Y). Additionally, we call X the generalized point set. Customary point sets include

• Euclidean n-space: Rⁿ

• Discrete n-space: Zⁿ

Set Operations. The customary set operations of union (), intersection (), subtraction (\), complement (´), cardinality (|A|), and choice (choice) are used in this course.
Unary arithmetic functions such as -x or sin(x) are used in this course. Such functions can be applied to subsets of the real numbers (e.g., max or , min or , and abs). Note that abs denotes absolute value of a set instead of |A|, which is reserved for cardinality.

2. Arrays

One usually thinks of an array as a two-dimensional matrix of reals or integers, which is sufficient for this class.

Definition. A vector a Fⁿ has n elements, each of which is a member of a set F. We can also write a as [a_n], which is defined by its element a_i F, i = 1..n.
Assumption. For the purposes of this course, an array a F_{m × n} is assumed to have m rows and n columns, where each element of the array, denoted by a_i,j, is a member of a set F. We can also write a as [a_m,n], which is defined by its element a_i,j F, i = 1..m, j = 1..n.
Remark. Alternatively, a vector or array can be thought of as a mapping from a point set (domain of the mapping) to a value set (range space of the mapping).

Example. Given X R_{m × n}, a mapping a : X -> R denotes a real-valued array a with m columns and n rows. This is also a concise way of denoting the set of all mappings from X to F, which is a little different from the notation we used in Discrete Math class.

Definition. If a F^X, then X = domain(a) and F = range(a).
Definition. The graph of a F^X is denoted by
G(a) = {(x, a(x)) : a(x) F, x X} .
We also write a G(a), where denotes equivalence.
Observation. Given an n-tuple a Fⁿ, observe that p_k denotes projection onto the k^th coordinate, such that p_k(a) denotes the k-th value of a, that is a_k.
Note that p₁(G(a)) = X = domain(a) and p₂(G(a)) = F = range(a).
Remark. Although a point set or value set can be any set, one must take care to specify arrays using only those value or point sets for which operations are defined.
Definition. A special class of arrays are called constant-valued arrays. Given a constant value
k F, we denote a constant array k {k}^X as
k {(x, a(x)) : a(x) = k, x X} = {(x,k): x X} .

Example. The unitary array on X is denoted as 1_X, or simply 1, with X understood.

3. Array Operations.

In order to manipulate arrays, we must specify a few simple operations. We thus concentrate on the pointwise unary and binary operations, as well as matrix multiplication, which are frequently used in computer science.

Definition. Let a denote an array in F^X. A unary pointwise operation g:F^X -> F^X is induced over X by the corresponding scalar operation g:F -> F.

Example. We have the following cases of real and Boolean negation:
-a {(x, -[a(x)]) : a(x) R, x X}
¬a {(x, ¬[a(x)]) : a(x) B, x X}
where B = {0,1}, as before.

Definition. A special type of unary operation is called the global reduce operation O: F^X -> F, which maps an array a F^X to an element of its value set.

Example. If a B^X, then the operation
a = a(x)
determines the number of unitarily-valued elements in a. Alternatively, replacing with would tell us if there are any unitary values in a. Definition. A binary pointwise array operation g:F^X × F^X -> F^X is induced over X by the corresponding scalar operation g:F × F -> F. Note that the operands (input arrays) must have the same domain, which the result (output array) also has.

Example. Given the arrays a,b F^X, we have the pointwise arithmetic operations
c = a + b {(x, c(x)) : c(x) = a(x) + b(x), where a(x),b(x) R, x X}
c = a · b {(x, c(x)) : c(x) = a(x) · b(x), where a(x),b(x) R, x X} .

Example. If a and b are Boolean arrays on X, then we have the following definition of the exclusive-or function:
c = (a xor b) {(x, c(x)) : c(x) = |a(x) - b(x)|, x X} .

Observation. A wide variety of binary operations can be described (e.g., a^b and log_ab), provided that value sets are properly defined. However, in the case of the logarithm, we must set range(a), range(b) R⁺, the positive reals. Otherwise, the logarithm is not defined.
Definition. A matrix is an m × n-element array (i.e., m rows and n columns). Matrix addition and subtraction were defined previously in terms of pointwise arithmetic operations on arrays.
Definition. A special type of operation, called matrix multiplication, is used to multiply matrices. Given an m × n-element matrix a and an n × p-element matrix b, matrix multiplication of a and b, denoted by c = a · b, is defined in terms of an element of c, as follows:
c_i,j = a_i,k · b_k,j
Thus, matrix multiplication requires n multiplications per element of c. Since c has m rows and p columns, there is a total requirement of mnp multiplications and mp(n-1) additions for multiplying a by b.

discrete math notation

discrete math notation

The first proof was given by Lagrange

In 1770 Lagrange has shown that any natural number can be written as a sum of at most four squares, a conjecture dating back to the days of Diophantus. In this section we show how this decomposition can effectively be computed even for large numbers.

Backtracking: simple but not efficient

The simplest solution one can think of works by subtracting a trial square from the number to be decomposed and then trying to decompose the resulting number into a sum of three squares. Using the same idea, this problem is then reduced to the representation of two squares. The final step of this algorithm asks to decompose an integer into just one square which boils down to checking whether a number D is a square. This can easily be accomplished by adopting the Newton iteration
x_n+1 = (x_n + D / x_n) / 2
for finding the square root of D to the integers. Unfortunately, the backtracking algorithm does not perform very well in practice. Nevertheless we will use one piece of this algorithm, namely the procedure to find the integer square root x of a number D which is defined as the largest x such that x² ≤ D
.

Reducing the problem to the sum of three squares

In a first step we will reduce the problem to the representation as a sum of three squares and later to the representation of a prime as a sum of two squares. An important result is that any integer n which is not of the form 4^a(8m + 7) can be written as a sum of three squares. We will therefore first check whether n, the number to be decomposed, is representable as a sum of three squares. If this is not the case then n - (2^a)² is not of the forbidden form and we will obtain a representation as a sum of four squares. Note that one could also try to subtract the largest possible square from n that makes sure that n is not of the forbidden in order to have a smaller number to be represented as a sum of three squares.

Representing a prime as the sum of two squares

Before we can tackle the problem of representation as a sum of three squares we need to solve the simpler problem of representing a prime p, p congruent 1 modulo 4, as a sum of two squares (note that numbers congruent 3 modulo 4 cannot be represented as a sum of two squares since any square is either congruent 0 modulo 4 or 1 modulo 4). One can show that any prime p congruent 1 modulo 4 is the sum of two squares. The calculation of this representation works in two steps: computing an imaginary unit and reduction to the final result. The following pseudo-code gives an efficient algorithm for decomposing a prime congruent 1 modulo 4 into a sum of two squares. It is a simplified variant of Cornacchia's algorithm but avoids computing the (integer) square root.

integer[] decomposePrime(integer p) { // (p is prime) and (p = 1 mod 4)
   if (p = 5 mod 8) b := 2;
   else { b := 3; while (b(p - 1) / 2 = 1 mod p) b := nextPrime(b); }
   // nextPrime(b) returns the smallest prime larger than b
   b := b(p - 1) / 4 mod p;
   // b is now an imaginary unit, i.e. b2 = -1 mod p
   a := p;
   while (b2 > p) {
 a, b := b, a mod b;
   }
   return [b, a mod b]