Sylabus
HISTORY OF MODERN MATHEMATICS AND LOGIC, syllabus of a course
This course is devoted not only to history, but to mathematics itself. It is meant as an introduction to mathematical thinking (finding and using axioms, defining some algebraic notions) and a presentation of basic concepts in theoretical computer science, with detours to history and logic. Large and important parts of mathematics, for example mathematical analysis, will not be mentioned. Emphasis is in fact put on the development of algebra and number theory. An alternative title of the course could be From Euclid of Alexandria to cryptography. The students should get some understanding for the fact that in mathematics and probably also in science it is often impossible to distinguish what is and what is not applicable. Detecting and searching huge prime numbers might look like a useless game for many centuries, but now we implicitly use huge prime numbers or other seemingly impractical toys when making an internet payment or already when typing any password.
The intended audience of the course are students who, during their high school study, considered mathematics interesting but then did not pursue it. Students of mathematics or computer science, or students of other than the first year of logic are in fact not welcome. A similar (Czech) course was in the previous years attended by students of philosophy, languages, psychology and linguistics. The code in SIS is ALGV00120, and the course also has a tab (a subweb) on http://www1.cuni.cz/~svejdar/.
LESSON 1
Prime numbers and prime factoring. Greatest common divisor and an algorighm for it based on factoring. Number domains: natural numbers and integers. The notion of relation. Visualization of a relation as a set with arrows (a graph in the sense of graph theory). Properties of relations. The divisibility relation in particular. Its properties: reflexivity, transitivity, special position of the numbers 1 and 0. Euclidean division as a pair of function that compute the quotient and remainder of integer division and that are usually (in programming languages) denoted Div and Mod. Different ways of explaining notions: while in mathematics we prefer language-efficient definitions because they can simplify some proofs, and so we define the divisibility relation in terms of multiplication (only) and avoid speaking about division, in computer science (when constructing an algorithm) Euclidian division can hardly be avoided.
LESSON 2
This lesson is devoted to students' presentations. They can address the following questions. What biographic data we have about Euclid of Alexandria? What we know about his Elements? How did the book survive the approximately 23 centuries, what editions are known? How was the book brought to Europe? What is the contents of the book? Here the expected answer is that the book is mainly devoted to geometry, but it contains also some parts of numbers theory, which is important for this course. Both geometry and number theory are treated in a way that stimulates logic: facts are deduced from postulates and axioms.
LESSON 3
Properties of the divisibility relation can be proved from basic properties of addition and multiplication (like associativity and the distributivity of multiplication over addition) in the domain of integers. The structure of mathematical proof, logical steps in it. Logical notation Euclid's algorithm for GCD (finding a greatest common divisor) and a proof of its correctness based on the small proofs done before. Estimate on the number of divisions that Euclid's algorithm executes: if two numbers are processed and the bigger of them has n digits in its decimal expansion, then the number of divisions is bounded by 8n. This is basically the result of Gabriel Lamé from 1884. Time requirements of algorithms. The grade-school algorithm for multiplication operates in quadratic time, Euclid's algorithm operates in cubic time.
LESSON 4
A mathematical consequence of Euclid's algorithm that can easily be overlooked: any two numbers have a common divisor that is divisible by all their common divisors. Due to this fact, greatest common divisor can be defined without speaking about the order or the absolute value. Similar language-efficient definitions can be developed for coprimes and for primes. Thanks to these definitions, divisibility can be considered also in some other domains, like the structure of polynomials with rational coefficients. The notion of problem in theoretical computer science. Instances of a problem, algorithm computing or deciding a problem. Polynomial algorithms. Classifying problems as polynomially computable or polynomially decidable. MULTIPLICATION, ADDITION, GCD are polynomially computable. The conjecture that FACTORING is not polynomially computable is widely accepted, but still not proved. A polynomial algorithm for PRIMES was invented as late as in 2002 by Agrawal, Kayal and Saxena, and it can be considered one of the biggest mathematical discoveries in the last decades. This algorithm will remain beyond the scope of this course, but some facts concerning huge primes will later be explained. History of computer science: papers by Cook and Karp, and the paper by Lamé mentioned above.
LESSON 5
Bezout's equation and Bezout's theorem. There exists an extension of Euclid's algorithm that solves Bezout's equation, and thus a solution of that equation can be found in polynomial time. Theoretical consequences of Bezout's theorem: an equivalent definition of prime speaking not about divisors, but numbers for which the given number is a divisor. A similar condition for coprimes. Modular arithmetic: adding and multiplying modulo a number, i.e. computing in the structure Zm.
LESSON 6
The notion of commutative ring. Special rings: fields and integer domains. The extended Euclid's algorithm in fact decides about invertibility in Zm and computes the inverse elements. The notion of (commutative) group. Exponentiation in Zm and its computability in polynomial time. Using groups to prove Fermat's Little Theorem and Euler's theorem. Euler's function.
LESSON 7
Pseudoprimes. An algorithm computing Euler's function exists, but it is dependent on FACTORING and thus it is not a polynomial time algorithm. Another old inventory that found application as late as in the twentieth century is the Chinese Remainder Theorem. Using the equivalent condition for coprimes proved in Lesson? for proving the Chinese Remainder Therem.
LESSON 8
The RSA cryptographical method. Proof of its correctness based on the Chinese Remainder Therem. Examples of its use. Orders of elements in a commutative group (Abelian group). Euler's group of a number.
LESSON 9
Mersenne numbers and Mersenne primes. Mersenne conjecture (around 1700AD) that 267-1 is prime, and Cole's negative solution of 1903: it actually is a product of two big primes having nine and twelwe digits respectively. Using considerations about orders in a group to demonstrate that numbers like the two factors of 267-1 or the Pervushin number 261-1 are primes.
LESSON 10
Using (but probably not proving) the theorem saying that Euler's group of any prime is cyclic to explain Pratt's result of 1975: the problem PRIMES is in NP. Informal explanation of the class NP. Pratt's result is weaker than the fact that there is a polynomial time algorithm for PRIMES, but can be explained at the level of this course.
REFERENCES
[AHU74] A. V. Aho, J. E. Hopcroft, and J. Ullmann. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974.[Pap94] C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.