Skip to content

4. Number Theory, Graphs ​

4.1 Sets, Relations, Functions, and Operations ​

A set is determined by its elements. The empty set is ∅. A set A is a subset of B, written A⊆B, if every element of A is also in B. The power set 2A is the set of all subsets of A, and for finite A it has 2|A| elements.

Basic set operations:

OperationDefinition
UnionA∪B contains elements in A or in B.
IntersectionA∩B={x∈A:x∈B}.
DifferenceA∖B={x∈A:x∉B}.
ComplementIf A⊆X, then A―=X∖A.
Symmetric differenceA△B=(A∖B)∪(B∖A).

Useful identities include associativity and commutativity of ∪ and ∩, distributivity of each over the other, A∖B=A∩B―, and De Morgan's laws:

A∩B―=A―∪B―,A∪B―=A―∩B―.

An ordered pair (x,y) records order, and the Cartesian product is X×Y={(x,y):x∈X, y∈Y}. A binary relation between X and Y is a subset of X×Y; a relation on X is a subset of X×X.

Important relation properties:

PropertyMeaning
ReflexivexRx for every x.
IrreflexiveNo xRx.
SymmetricxRy implies yRx.
AntisymmetricxRy and yRx imply x=y.
TransitivexRy and yRz imply xRz.
Dichotomous / total comparabilityFor any x,y, at least one of xRy or yRx holds.

An equivalence relation is reflexive, symmetric, and transitive. It partitions a set into disjoint equivalence classes, and every partition defines an equivalence relation by putting elements in relation exactly when they belong to the same block.

A partial order is reflexive, antisymmetric, and transitive. If every two elements are comparable, it is a total order. In a partial order, the smallest element is below every element; a minimal element only has no strictly smaller element. Similarly, the largest element is above every element, while a maximal element has no strictly larger element. Bounds, infimum, and supremum describe lower and upper constraints on subsets.

A function is a relation that assigns at most one value to each input. For f:X→Y, the domain is X and the range is a subset of Y. A function is injective if different inputs cannot have the same output, surjective if every element of Y is hit, and bijective if it is both.

Operations are functions with algebraic meaning:

Operation typeForm
Nullary operationChooses an element of X.
Unary operationf:X→X.
Binary operationf:X×X→X.

A binary operation may be associative, commutative, have identity elements, have inverses, and distribute over another operation. A structure-preserving map between two sets with operations is a homomorphism: if ⋆ is an operation on X and ∘ is an operation on Y, then f(x1⋆x2)=f(x1)∘f(x2).

These ideas lead to algebraic structures. A set with a binary operation is a groupoid; associativity gives a semigroup; an identity gives a monoid; inverses give a group; a commutative group is Abelian. A ring combines additional Abelian-group structure with multiplication and distributivity. A field is a ring where every nonzero element has a multiplicative inverse.

What to Emphasize in an Oral Answer ​

  • Start with sets: membership, subset, power set, and the basic operations union, intersection, difference, complement, and symmetric difference.
  • Mention the main set identities, especially distributivity and De Morgan's laws.
  • Define relations as subsets of Cartesian products and list the key relation properties: reflexive, symmetric, antisymmetric, transitive, and total comparability.
  • Contrast equivalence relations with partial orders: equivalences partition into classes, while partial orders support comparisons, bounds, minimal/maximal, and smallest/largest elements.
  • Define functions as single-valued relations and distinguish injective, surjective, and bijective maps.
  • Explain operations as functions on a set, then connect associativity, identity, inverses, and distributivity to structures such as semigroups, monoids, groups, rings, and fields.
  • Mention homomorphisms as maps preserving operations.
Suggested answer

The basic language of this topic starts with sets. A set is determined by its elements, so the central questions are membership, inclusion, and how sets are combined. The empty set has no elements, a subset contains only elements of another set, and the power set contains all subsets. The basic operations are union, intersection, difference, complement, and symmetric difference. Their algebraic laws, such as associativity, commutativity, distributivity, and De Morgan's laws, let us transform set expressions in the same way arithmetic laws let us transform numeric expressions.

Relations add structure between elements. A binary relation is a subset of a Cartesian product, so it consists of ordered pairs. On one set, the important properties are reflexivity, symmetry, antisymmetry, transitivity, and comparability. Equivalence relations are reflexive, symmetric, and transitive; they express "same type as" and divide the set into disjoint equivalence classes. Partial orders are reflexive, antisymmetric, and transitive; they express ordering where not every two elements must be comparable. If every pair is comparable, the partial order becomes a total order.

Functions are special relations: each input has at most one output. A function can be injective, meaning no two different inputs share one output; surjective, meaning every target element is reached; or bijective, meaning both. Bijections are especially important because they show two sets have the same size or the same structure.

Operations are functions that take elements of a set and produce elements of the same set. Unary operations take one argument, binary operations take two, and nullary operations can be viewed as choosing a distinguished element. Properties such as associativity, commutativity, identity, inverse, and distributivity determine the algebraic behavior of the operation. This is how we arrive at structures such as semigroups, monoids, groups, rings, integral domains, and fields. The point is that sets provide the universe of objects, relations describe comparisons or classifications among them, functions describe deterministic mappings, and operations provide the internal algebraic rules.

4.2 Complex Numbers ​

The complex numbers are defined as C=R×R with

(x,y)+(x′,y′)=(x+x′,y+y′)

and

(x,y)(x′,y′)=(xx′−yy′,xy′+yx′).

The element (0,1) is denoted by i, and i2=−1. Real numbers embed as (x,0), so (x,y) can be written as x+yi.

Core forms and operations:

ConceptFormula
Real and imaginary partsIf z=x+yi, then Re(z)=x and Im(z)=y.
Conjugatez―=x−yi.
Modulus|z|=x2+y2.
InverseIf z≠0, then z−1=z―/|z|2.
Product with conjugatezz―=|z|2.

Conjugation preserves addition and multiplication:

z+w―=z―+w―,zw―=z―w―.

The modulus is multiplicative and satisfies the triangle inequality:

|zw|=|z||w|,|z+w|≤|z|+|w|.

If z≠0, an argument t is an angle such that

z=|z|(cos⁡t+isin⁡t).

Arguments are not unique: adding 2kπ gives the same complex number.

Multiplication and powers are simple in trigonometric form. If

z=r(cos⁡t+isin⁡t),w=s(cos⁡u+isin⁡u),

then

zw=rs(cos⁡(t+u)+isin⁡(t+u)),

and de Moivre's formula gives

zn=rn(cos⁡(nt)+isin⁡(nt)).

The nth roots of w=R(cos⁡t+isin⁡t) are

zk=Rn(cos⁡t+2kπn+isin⁡t+2kπn),k=0,…,n−1.

Complex numbers form a field but not an ordered field compatible with multiplication, because i2=−1 contradicts the ordered-field rule that every nonzero square is positive.

What to Emphasize in an Oral Answer ​

  • Define C as R2 with special multiplication, introduce i=(0,1), and note i2=−1.
  • Explain algebraic form x+yi, real/imaginary parts, conjugate, modulus, and inverse z−1=z―/|z|2 for z≠0.
  • State useful identities: zz―=|z|2, conjugation respects addition/multiplication, and |zw|=|z||w|.
  • Give the geometric/trigonometric form z=r(cos⁡t+isin⁡t) and note that arguments are defined modulo 2π.
  • Explain multiplication, powers, and roots through moduli and arguments, including de Moivre's formula.
  • Finish with the structural point: C is a field but not an ordered field compatible with multiplication.
Suggested answer

Complex numbers extend the real numbers so that equations such as x2+1=0 have solutions. Formally, a complex number is a pair of real numbers with special addition and multiplication rules. The pair (x,y) is written as x+yi, where i=(0,1) and i2=−1. Real numbers sit inside the complex numbers as x+0i, so the real number system is preserved.

The algebraic form x+yi separates a complex number into real and imaginary parts. The conjugate of z=x+yi is z―=x−yi, and the modulus is |z|=x2+y2. These are not just notation: they make division possible, because zz―=|z|2, so for nonzero z the inverse is z―/|z|2. Conjugation also respects addition and multiplication, which makes it a useful algebraic tool.

Complex numbers also have a geometric interpretation as points or vectors in the plane. The modulus is the distance from the origin, and the argument is the angle with the positive real axis. In trigonometric form, z=r(cos⁡t+isin⁡t). This form explains why multiplication adds angles and multiplies lengths. If another number is s(cos⁡u+isin⁡u), then the product has modulus rs and angle t+u.

This leads to de Moivre's formula: raising a complex number to the nth power raises the modulus to the nth power and multiplies the argument by n. Roots work in the reverse direction. An nth root has modulus equal to the nth root of the original modulus, and its possible arguments are obtained by adding multiples of 2π before dividing by n. Therefore a nonzero complex number has n distinct nth roots, evenly placed around a circle.

The complex numbers form a field, so addition, subtraction, multiplication, and division by nonzero elements all work. However, they cannot be ordered like the real numbers in a way compatible with field multiplication, because i is nonzero but i2=−1, whereas in an ordered field every nonzero square must be positive.

4.3 Enumeration Problems ​

Enumeration studies finite sets by counting possible choices, arrangements, and mappings. Two finite sets have the same cardinality if there is a bijection between them. The pigeonhole principle says that if |X|>|Y|, then no function f:X→Y can be injective.

Basic formulas:

ProblemMeaningCount
PermutationOrder all n distinct elements.Pn=n!
Variation without repetitionOrdered choice of k distinct elements from n.Vnk=n!(n−k)!
Combination without repetitionUnordered choice of k distinct elements from n.Cnk=(nk)=n!k!(n−k)!
Permutation with repetitionsArrange multiset counts i1,…,ir with total n.n!i1!i2!⋯ir!
Variation with repetitionOrdered length-k sequence from n options.nk
Combination with repetitionUnordered choice of k elements from n types, repetition allowed.(n+k−1k)

The binomial theorem is

(x+y)n=∑k=0n(nk)xkyn−k.

The multinomial theorem generalizes it:

(x1+⋯+xr)n=∑i1+⋯+ir=nn!i1!⋯ir!x1i1⋯xrir.

The inclusion-exclusion principle counts elements outside or inside unions by alternating intersections. For finite sets A1,…,Ak,

|⋃i=1kAi|=∑i|Ai|−∑i<j|Ai∩Aj|+∑i<j<ℓ|Ai∩Aj∩Aℓ|−⋯.

What to Emphasize in an Oral Answer ​

  • Frame enumeration as counting finite choices, arrangements, and mappings; mention cardinality through bijections.
  • State the pigeonhole principle as the basic non-injectivity obstruction.
  • Organize formulas by two questions: does order matter, and is repetition allowed?
  • Give the no-repetition counts: permutations n!, ordered variations n!/(n−k)!, and combinations (nk).
  • Give the repetition counts: ordered choices nk, combinations with repetition (n+k−1k), and multiset permutations n!/(i1!⋯ir!).
  • Include binomial and multinomial theorem coefficients as counting choices from factors.
  • Mention inclusion-exclusion for overlapping conditions, with alternating sums of intersections.
Suggested answer

Enumeration problems ask how many possibilities a finite construction has. The starting point is cardinality: finite sets have the same size when a bijection exists between them. The pigeonhole principle is the simplest counting obstruction. If more objects are assigned to fewer boxes, then at least two objects must share a box, so the assignment cannot be injective.

The main distinction in elementary enumeration is whether order matters and whether repetition is allowed. If we arrange all n distinct elements, we get n! permutations. If we choose k distinct elements and order matters, we get variations without repetition, with count n!/(n−k)!. If order does not matter, we divide by the k! possible orders of the chosen elements, giving the combination formula (nk).

When repetition is allowed, the formulas change. Ordered length-k sequences from n choices give nk, because each position has n independent possibilities. If order is ignored but repetition is allowed, the stars-and-bars formula gives (n+k−1k). For arrangements of a multiset, where element types repeat with multiplicities i1,…,ir, the number of distinguishable orders is n!/(i1!⋯ir!), because permutations that only swap identical copies do not create new outcomes.

Two important theorems organize these counts. The binomial theorem expands (x+y)n by choosing which k of the n factors contribute x and which contribute y. The multinomial theorem does the same for more than two terms, with coefficients counting repeated-type permutations. Finally, inclusion-exclusion handles overlapping conditions. To count a union, we add the single set sizes, subtract pairwise overlaps that were counted twice, add triple overlaps that were subtracted too much, and continue alternating. This is the standard way to count objects satisfying at least one of several possibly overlapping properties.

4.4 Undirected Graphs, Trees, Eulerian and Hamiltonian Graphs ​

An undirected graph consists of a vertex set V, an edge set E, and an incidence relation assigning endpoints to edges. In a simple undirected graph, there are no loops and no parallel edges, so an edge can be viewed as a two-element subset of V.

Basic graph notions:

ConceptMeaning
Isolated vertexA vertex incident with no edge.
LoopAn edge whose two endpoints coincide.
Parallel edgesDistinct edges with the same endpoints.
Adjacent verticesVertices joined by an edge.
Degree d(v)Number of incident edge ends at v; in a simple graph, number of neighbors.
r-regular graphEvery vertex has degree r.
Complete graph KnSimple graph where every pair of distinct vertices is adjacent.
Bipartite graphVertices split into two disjoint parts and edges run only between the parts.
Complete bipartite graph Km,nEvery vertex in one part is joined to every vertex in the other.
SubgraphUses subsets of the original vertices and edges with inherited incidence.

A walk is an alternating sequence of vertices and edges where each edge joins its neighboring vertices in the sequence. A trail has no repeated edge. A path has no repeated vertex. A graph is connected if every two vertices are joined by a path; the connected components are the equivalence classes of the reachability relation.

A tree is a connected acyclic graph. For a finite simple graph with n vertices, the following are equivalent:

  • It is a tree.
  • It is connected and has n−1 edges.
  • It is acyclic and has n−1 edges.
  • Between every two distinct vertices there is exactly one path.
  • Deleting any edge destroys connectedness.
  • Adding any new edge creates a cycle.

A spanning tree of a graph G is a subgraph that is a tree and contains all vertices of G.

An Eulerian trail uses every edge exactly once. If it starts and ends at the same vertex, it is an Eulerian circuit. A connected finite undirected graph has an Eulerian circuit exactly when every vertex has even degree. A connected finite graph has an open Eulerian trail exactly when exactly two vertices have odd degree; those vertices are the start and end.

A Hamiltonian path visits every vertex exactly once. A Hamiltonian cycle returns to the starting vertex after visiting all vertices. Unlike the Eulerian condition, Hamiltonian graphs do not have one equally simple degree-parity characterization; Hamiltonian questions are generally harder because the restriction is on vertices rather than edges.

Also note planar graphs. A connected planar graph satisfies Euler's formula |V|−|E|+|F|=2, where F is the number of faces in a planar drawing. Kuratowski's theorem characterizes finite planar graphs by excluding subdivisions of K5 and K3,3. This is useful graph background but not central to the subject wording.

Graph representations are usually adjacency lists or matrices. Lists are economical for sparse graphs; adjacency matrices are simple and efficient for dense graphs or constant-time adjacency tests.

What to Emphasize in an Oral Answer ​

  • Define an undirected graph by vertices, edges, and incidence; in a simple graph, edges are unordered pairs with no loops or parallel edges.
  • Cover local vocabulary: adjacency, degree, isolated vertices, regular, complete, bipartite, complete bipartite, and subgraph.
  • Distinguish walks, trails, and paths, then define connectedness and connected components.
  • State equivalent characterizations of finite trees: connected acyclic, n−1 edges, unique path between vertices, edge deletion disconnects, edge addition creates a cycle.
  • Explain spanning trees as minimal connected backbones of connected graphs.
  • Contrast Eulerian and Hamiltonian traversal: Eulerian uses every edge once and has a degree-parity criterion; Hamiltonian visits every vertex once and has no comparable simple test.
  • Mention graph representations briefly: adjacency lists for sparse graphs, matrices for dense graphs or fast adjacency checks.
Suggested answer

An undirected graph is a structure made of vertices and edges, where each edge connects vertices without direction. In a simple graph there are no loops and no parallel edges, so each edge just joins two distinct vertices. Basic terminology describes local structure: adjacent vertices share an edge, the degree of a vertex is the number of incident edge ends, an isolated vertex has degree zero, and an r-regular graph has the same degree r at every vertex. Complete graphs connect every pair of vertices, while bipartite graphs split vertices into two parts and only allow edges between the parts.

Movement through a graph is described by walks, trails, and paths. A walk may repeat vertices and edges. A trail may repeat vertices but not edges. A path repeats no vertex. Connectivity means every pair of vertices is joined by some path, and the connected components are the maximal connected pieces.

Trees are the most important special connected graphs. A tree is connected and acyclic. This definition has several equivalent forms for finite simple graphs: a tree with n vertices has exactly n−1 edges; between any two vertices there is exactly one path; deleting any edge disconnects it; and adding a new edge creates a cycle. A spanning tree of a connected graph keeps all vertices but selects enough edges to form a tree, so it captures a minimal connected backbone.

Eulerian and Hamiltonian graphs ask for global traversals, but they ask for different things. An Eulerian trail uses every edge exactly once, and an Eulerian circuit returns to its starting vertex. In a connected finite undirected graph, an Eulerian circuit exists exactly when all vertices have even degree, because every time the traversal enters a vertex it must also leave it. If exactly two vertices have odd degree, an open Eulerian trail can start at one and end at the other.

A Hamiltonian path visits every vertex exactly once, and a Hamiltonian cycle returns to the starting vertex. This is a vertex-covering condition rather than an edge-covering condition. The contrast is important: Eulerian existence has a clean parity test, while Hamiltonian existence is much harder and does not have a simple universal characterization. In applications, adjacency lists and adjacency matrices are common representations; lists fit sparse graphs, while matrices fit dense graphs or fast adjacency lookup.

4.5 Divisibility, Congruence, and Primes ​

For integers, b divides a, written b∣a, if there exists an integer c with a=bc. Basic properties include:

  • a∣0 for every integer a.
  • 0∣a if and only if a=0.
  • 1∣a for every integer a.
  • Divisibility is reflexive and transitive.
  • If b∣ai for several ai, then b divides every integer linear combination ∑aici.

The greatest common divisor gcd(a,b) is a common divisor divisible by every other common divisor. Integers a and b are relatively prime if their gcd is 1. The least common multiple is a common multiple that divides every other common multiple.

The Euclidean algorithm computes gcd(a,b). The extended Euclidean algorithm also produces x,y∈Z such that

gcd(a,b)=ax+by.

An integer greater than 1 is prime if its only positive divisors are 1 and itself. In integral-domain language, p is prime if p∣ab implies p∣a or p∣b. The fundamental theorem of arithmetic says every positive integer greater than 1 has a unique prime factorization up to order. The Sieve of Eratosthenes finds primes up to n by repeatedly marking multiples of the smallest remaining unmarked number.

Congruence modulo m is defined by

a≡b(modm)⟺m∣(a−b).

It is an equivalence relation on Z. The equivalence classes are residue classes; a complete residue system contains exactly one representative from each class. A reduced residue system contains representatives relatively prime to m. Euler's totient function φ(m) counts reduced residue classes modulo m.

Euler-Fermat theorem:

gcd(a,m)=1⟹aφ(m)≡1(modm).

Fermat's little theorem is the prime-modulus special case:

p prime, p∤a⟹ap−1≡1(modp).

A linear congruence ax≡b(modm) is equivalent to ax+my=b. Let d=gcd(a,m). It has a solution if and only if d∣b. After dividing by d, the reduced coefficient a/d is invertible modulo m/d, and the extended Euclidean algorithm gives the solution class.

For two congruences

x≡a(modm),x≡b(modn),

a common solution exists if and only if gcd(m,n)∣(b−a). If m and n are coprime, the Chinese remainder theorem gives a unique solution modulo mn. More generally, pairwise coprime moduli m1,…,mk give a unique solution modulo m1⋯mk.

What to Emphasize in an Oral Answer ​

  • Define divisibility b∣a and mention reflexivity, transitivity, and closure under integer linear combinations.
  • Define gcd, lcm, relative primality, and Bezout's identity from the extended Euclidean algorithm.
  • Explain primes through divisors and the product-divisibility property; state unique prime factorization and the sieve idea.
  • Define congruence modulo m by m∣(a−b), residue classes, complete residue systems, reduced residue systems, and Euler's φ.
  • State Euler-Fermat and Fermat's little theorem as the key exponent results.
  • Explain solvability of ax≡b(modm): solutions exist exactly when gcd(a,m)∣b.
  • Include the Chinese remainder theorem: compatibility for non-coprime moduli and unique solution modulo the product when moduli are pairwise coprime.
Suggested answer

Divisibility is the relation behind elementary number theory. We say that b divides a if a can be written as bc for some integer c. This relation is reflexive and transitive, and it behaves well with linear combinations: if a number divides several integers, it also divides every integer linear combination of them.

The greatest common divisor of two integers is the common divisor that is divisible by all other common divisors. If the gcd is 1, the integers are relatively prime. The Euclidean algorithm computes the gcd by repeated division with remainder, and the extended Euclidean algorithm gives Bezout coefficients, integers x and y such that gcd(a,b)=ax+by. This identity is the bridge between divisibility and congruence solving.

Primes are the building blocks of the integers. A prime integer has no positive divisors except 1 and itself, and equivalently it has the property that if it divides a product, it divides at least one factor. The fundamental theorem of arithmetic says every positive integer greater than 1 factors uniquely into primes, up to order. The Sieve of Eratosthenes is a constructive way to list primes up to a bound: starting from 2, repeatedly keep the smallest unmarked number and mark its multiples.

Congruence modulo m means that two integers have the same remainder behavior modulo m, or equivalently that m divides their difference. It is an equivalence relation, and its equivalence classes are residue classes. Arithmetic can be performed on these classes because addition and multiplication respect congruence. A complete residue system chooses one representative from each class, and a reduced residue system chooses representatives from the classes relatively prime to the modulus. Euler's totient function counts these reduced classes.

Euler-Fermat's theorem states that if a is relatively prime to m, then aφ(m)≡1(modm). For a prime modulus p, this becomes Fermat's little theorem: ap−1≡1(modp) when p does not divide a. Linear congruences are solved by translating ax≡b(modm) into ax+my=b. If d=gcd(a,m) does not divide b, there is no solution; if it does, division by d and the extended Euclidean algorithm produce a solution modulo m/d. Systems of congruences are handled similarly, and when the moduli are pairwise coprime the Chinese remainder theorem guarantees a unique solution modulo their product.

4.6 Polynomials and Division With Remainder ​

Let R be a ring. A polynomial over R is a finite expression

f(x)=∑i=0nfixi,fi∈R.

If fn≠0, then fn is the leading coefficient and n is the degree. The polynomial ring R[x] can also be viewed as sequences of coefficients with only finitely many nonzero terms.

Polynomial operations:

OperationRule
AdditionAdd coefficients componentwise: (f+g)i=fi+gi.
Negation/subtractionUse additional inverses coefficientwise.
MultiplicationConvolution of coefficients: (fg)k=∑i+j=kfigj.

If R is commutative, then R[x] is commutative. If R has multiplicative identity 1, then R[x] has identity polynomial 1+0x+0x2+⋯.

Division with remainder: if R is a ring where the leading coefficient of g is invertible, and in particular if g is monic, then for f,g∈R[x] with g≠0, there exist unique polynomials q,r∈R[x] such that

f=gq+r,deg⁡r<deg⁡g.

Over a field this works for every nonzero divisor polynomial g.

Horner's scheme evaluates

f(x)=fnxn+fn−1xn−1+⋯+f0

by rewriting it as

f(x)=(((fnx+fn−1)x+fn−2)x+⋯)x+f0.

This reduces the number of multiplications and also supports testing whether c is a root: c is a root exactly when f(c)=0. The same nested computation is closely related to division by x−c, where the remainder is f(c).

What to Emphasize in an Oral Answer ​

  • Define a polynomial over a ring R as a finite formal sum and identify leading coefficient and degree.
  • State how R[x] operations work: coefficientwise addition and convolution-style multiplication.
  • Mention inherited structure: commutativity or a multiplicative identity in R carries to R[x] when applicable.
  • Explain division with remainder f=gq+r, deg⁡r<deg⁡g, and the condition needed: the leading coefficient of g is invertible; over fields every nonzero divisor works.
  • State uniqueness of quotient and remainder under the division hypotheses.
  • Present Horner's scheme as efficient nested evaluation and connect it to the remainder theorem/root test for division by x−c.
Suggested answer

A polynomial over a ring R is a finite formal sum f0+f1x+⋯+fnxn with coefficients in R. It is important that only finitely many coefficients are nonzero. The highest index with nonzero coefficient is the degree, and the corresponding coefficient is the leading coefficient.

Polynomials form a ring R[x]. Addition is componentwise: coefficients of the same power of x are added. Multiplication is based on collecting equal powers. The coefficient of xk in a product is the sum of all products figj with i+j=k. This is the same convolution pattern that appears when multiplying ordinary algebraic expressions. If the coefficient ring is commutative or has a unit, the polynomial ring inherits those corresponding properties.

Division with remainder generalizes integer division. Given polynomials f and nonzero g, we want to write f=gq+r, where the remainder has smaller degree than g. Over a field this is always possible and unique. More generally, it is enough for the leading coefficient of g to be invertible; in particular, monic divisors work over any coefficient ring where the other operations are defined. The quotient records how many times the divisor fits into the polynomial by leading terms, and the remainder is what cannot be further reduced below the divisor's degree.

Horner's scheme is a practical consequence of polynomial structure. Instead of evaluating fnxn+fn−1xn−1+⋯+f0 by computing every power separately, the polynomial is nested as (((fnx+fn−1)x+fn−2)x+⋯)+f0. This uses repeated multiply-and-add steps, so evaluation is efficient. It also tests roots: c is a root if and only if the computed value f(c) is zero. In the background, this is related to division by x−c, because the remainder of that division is exactly f(c).

4.7 Additional Material: Coding Theory ​

Coding theory is included here as related material for number theory, graphs, and discrete mathematics.

Letter-by-Letter Encoding ​

Encoding maps messages into another set of messages, usually over a different alphabet. If messages are words over an alphabet A and code words use an alphabet B, then a letter-by-letter code is determined by a mapping

φ:A→B∗.

This mapping extends to whole words by concatenation:

ψ(a1a2⋯an)=φ(a1)φ(a2)⋯φ(an).

For decoding to be unambiguous, the extended mapping ψ:A∗→B∗ must be injective. If two source letters get the same code word, or if an empty code word is allowed for a source letter, unique decoding fails. Therefore practical letter-by-letter codes use φ:A→B+ and require enough structure to decode concatenated words.

Word terminology:

TermMeaning
A+Nonempty words over alphabet A.
A∗All words over A, including the empty word.
PrefixA beginning part of a word.
InfixA contiguous middle part of a word.
SuffixAn ending part of a word.
Prefix codeNo code word is a prefix of another code word.
Uniform codeAll code words have the same length.
Comma codeA special comma word terminates code words and appears neither as prefix nor infix of code words.

A code tree represents code words as root-to-vertex paths labelled by alphabet symbols. Prefix-free codes correspond to choosing code words at vertices none of which is an ancestor of another chosen code-word vertex.

Frequency, Information, Entropy, and Average Length ​

If a source emits n messages and symbol ai occurs ki times, then

pi=kin

is the relative frequency. The distribution is (p1,…,pm) with ∑ipi=1.

The information content of symbol ai is

Ii=−logr⁡pi,

where r is the size/base of the unit. With r=2, information is measured in bits.

Entropy is the average information content:

Hr(p1,…,pm)=−∑i=1mpilogr⁡pi.

If code word i has length li, then the average word length is

l¯=∑i=1mpili.

An optimal uniquely decodable code minimizes average word length for the given alphabet size and source distribution.

Shannon Code ​

A Shannon-code construction for an r-letter code alphabet.

  1. Sort source letters by decreasing relative frequency.
  2. Choose code lengths li such that
r−li≤pi<r−li+1.
  1. Assign code words in lexicographic tree order with those lengths.

For the example with code alphabet {0,1,2}:

LetterFrequencyShannon lengthShannon code
f0.31200
a0.17201
h0.17202
c0.13210
j0.093110
i0.063111
b0.0241120
d0.0241121
g0.0241122
e0.01512000

The original tree image is represented by the table: each code is the path label from the root to the leaf for that symbol.

Huffman Code ​

Huffman coding builds an optimal prefix code by repeatedly merging least frequent symbols.

For an r-ary code alphabet, the construction first adjusts the number of leaves so that the final tree has the right arity. If the number of source symbols is n, the first merge uses

m=2+((n−2)mod(r−1))

symbols. After that, each reduction merges the r least frequent current symbols into a new combined symbol whose frequency is their sum. When only r symbols remain, labels from the code alphabet are assigned, and the reductions are expanded backwards to obtain the final code words.

The ternary Huffman example has final code table:

LetterFrequencyHuffman code
f0.311
a0.1700
h0.1701
c0.1302
j0.0920
i0.0622
b0.02211
d0.02212
g0.022100
e0.012101

The original Huffman tree image is replaced by the reduction description plus this code table. The important mechanism is that frequent symbols get short paths and rare symbols get longer paths.

Error-Control Codes and Hamming Distance ​

Error-control codes add redundancy so that transmission errors can be detected or corrected. Error-detecting codes report that something went wrong; error-correcting codes choose a likely original code word. For error-control codes, code words usually have a fixed length.

For words u and v of the same length, the Hamming distance d(u,v) is the number of positions where they differ. It is a metric:

  • d(u,v)≥0;
  • d(u,v)=0 exactly when u=v;
  • d(u,v)=d(v,u);
  • d(u,z)≤d(u,v)+d(v,z).

The minimum distance of a code C is

d(C)=minu≠v, u,v∈Cd(u,v).

If the alphabet is an Abelian group with zero, the Hamming weight w(u) is the number of nonzero positions. For a linear code, the minimum distance is the minimum nonzero weight.

A code corrects all errors of size at most t when every received word within distance t of a code word is closer to that code word than to any other code word. A minimum distance d permits unique correction of up to

⌊d−12⌋

errors.

The Hamming bound for a q-ary length-n code correcting t errors is

|C|∑j=0t(nj)(q−1)j≤qn.

If equality holds, the code is perfect.

Linear Codes, Polynomial Codes, and CRC ​

Over a finite field K with q elements, a linear code is a subspace C≤Kn. If it has dimension k and minimum distance d, it is an [n,k,d]q code. A linear encoding can be represented by a generator matrix

G:Kk→Kn.

Polynomial coding represents a message vector (a0,…,ak−1) as a polynomial

p(x)=a0+a1x+⋯+ak−1xk−1.

Choosing a fixed monic polynomial g(x) of degree m with nonzero constant term, the message is encoded by multiplication:

p(x)↦p(x)g(x).

The resulting code length is n=k+m.

A cyclic code is a polynomial code where g(x) divides xn−1. Cyclic redundancy check (CRC) is the most familiar practical example over F2. To encode, multiply the message polynomial by xm, divide by g(x), and subtract the remainder:

p(x)xm=q(x)g(x)+r(x),code word=p(x)xm−r(x).

The transmitted polynomial is divisible by g(x). To check a received word, divide by g(x); a nonzero remainder indicates an error. CRC is mainly an error-detecting code, not a full error-correcting code.

What to Emphasize in an Oral Answer ​

  • Frame coding theory around three goals: representation, compression/short average length, and error detection or correction.
  • For letter-by-letter codes, explain extension by concatenation and the need for injectivity of the extended map for unique decoding.
  • Mention prefix codes and code trees as the clean practical way to decode unambiguously.
  • Define information content, entropy, and average code-word length; stress that frequent symbols should get shorter code words.
  • Contrast Shannon coding with Huffman coding: Shannon uses probability-based lengths, while Huffman constructs an optimal prefix code by merging least frequent symbols.
  • Explain Hamming distance, minimum distance, and correction capability ⌊(d−1)/2⌋; mention the Hamming bound.
  • Describe linear codes as subspaces [n,k,d]q with generator matrices, and polynomial/cyclic codes including CRC as mainly error-detecting.
Suggested answer

Coding theory studies how messages can be represented so that they are compact, uniquely decodable, or robust against errors. In letter-by-letter encoding, each source symbol from an alphabet A is assigned a word over a code alphabet B, and the code of a whole message is obtained by concatenating the code words of its symbols. For decoding to be unambiguous, the resulting map on whole words must be injective. Prefix codes are especially useful because no code word is the beginning of another, so decoding can proceed from left to right without ambiguity.

The efficiency of a code depends on the source distribution. If symbol ai has relative frequency pi, its information content is −logr⁡pi, and the entropy is the weighted average of these values. A code with lengths li has average length ∑pili, so frequent symbols should receive shorter code words. Shannon coding chooses lengths from the probabilities and assigns code words with those lengths. Huffman coding gives an optimal prefix code by repeatedly merging the least frequent symbols and then expanding the merge tree back into code words.

Coding theory also handles transmission errors. For fixed-length code words, the Hamming distance counts how many positions differ. The minimum distance of a code determines its error-control ability: a code with distance d can reliably correct up to ⌊(d−1)/2⌋ errors, because balls of that radius around different code words do not overlap. The Hamming bound counts how many received words can lie in these error balls and shows a limit on how large such a code can be.

Linear codes use algebraic structure. Over a finite field, a linear code is a subspace of Kn, described by parameters [n,k,d]q. A generator matrix maps message vectors into code words. Polynomial codes represent messages as polynomials and multiply them by a fixed generator polynomial. CRC is a cyclic polynomial code used mainly for error detection: the sender appends a remainder so that the transmitted polynomial is divisible by the generator polynomial, and the receiver checks divisibility again.