My email address is freud@cs.elte.hu.
Course syllabus
General information
Extra office will be held on May 21, Monday, 4 p.m., in Room 104 (adjacent to our usual classroom), as I received an email note, that some of you will come to this extra office.
For those willing to receive their graded final and consult about it before the farewell party on May 24, 3 p.m., I will be available also on May 23, Wednesday, 4 p.m., in our usual classroom.
Review problems (solutions will be discussed in class on May 16).
Extra office: March 19 (Monday) 4 p.m. in Room 104. Sample midterm (solutions will be discussed in class on March 20).
Problem sheets: 1 ; 2 ; 3 ; 4 ; 5 ; 6 ; 7 ; 8 ; Extra problems ; 9 ;
Short summaries: Algebraic numbers ; Diophantine approximation ; Cardinalities ; Algebraic integers and cyclotomic polynomials ; Waring's problem ; Linear algebra ; Field extensions ; Sidon sets ; Mersenne and Fermat primes ; Oddtown and Eventown .
Homeworks are assigned on Wednesday and are due on next Wednesday. Each problem is 10 points worth, the weekly assignment contains 3 or 4 problems from the problem sheets.
Due on February 15: 1b or c; 1f or g; any two parts of 5; any two parts of 6, except 6c (done in class). Any of these problems can be freely traded for the "fun" problem 10.
Due on February 22: altogether two parts of 2 and 7, except 7b (done in class); two problems from 11, 13 and 16. Again, the "fun" problem 18 is a jolly joker to substitute one of these.
Due on February 29: altogether two parts of 19b,c and 20a,b (each is 10 points worth); two parts of 22. The solution of fun problem 25 ("turtle") is welcome to replace one of the above problems.
Due on March 7: altogether 3 problems from the following assortment: 26a, 26b, 27a, 27b, 31, 32a, 32b (the parts "a" seem to be easier).
Due on March 14: altogether 3 problems from 35, 36, 38, 40, 41, 42 (here 36 seems to be harder).
Due on March 28(!!): altogether 3 problems from 50a, 51, 52a, 53a, 56a, 56b, 56c.
Due on April 11: any three parts of 57, plus altogether 2 problems from 50b, 53b, 54a, 54b.
Due on April 18: 61 or 62; 58a or b; two of 60b,c,d,e. Any of these can be substituted by 65.
Due on April 25: Any three problems from 66-72.
Due on May 2: Any three problems from 73-75 and 77-80.
Due on May 9 (last homework): One of 81 and 82; one of 84 and 85; and one of 87, 88 and 89. Any problem can be substituted by 90.
February 7: We solved Problems 1a (four and a half proofs), 1d, 1e and 1h. (See also Section I/1 in the textbook.) As a generalization of 1h we established a method for finding all rational zeros of a polynomial with integer coefficients. As a preparation for tomorrow's class you may read the short summary about algebraic numbers (with title "Some are more irrational than others"), and try to prove properties (a), (b) and (c) listed there.
February 8: We discussed the basic definitions and facts about algebraic numbers (see also Section I/5 in the textbook), saw lots of examples, and solved Problems 3, 4, 6c and 8. As a preparation to construct a transcendental number, we started to investigate, how strongly the real numbers can be approximated by rationals, and found that the rationals behave "badly" in this relation. Next week we shall show that the irrationals perform much better.
February 14: We stated and proved the promised approximation theorem for irrational numbers (see the last theorem of Section II/8 in the textbook), and as a consequence we found that the fractional parts of the multiples of an irrational number are everywhere dense in the interval [0,1]. We shall apply this to the second part of Problem 14 tomorrow (you might try to solve it). We solved the first part of Problem 14, and - during the office hour, after discussing some hints concerning the first homework set - we answered also the first two questions of Problem 15. As a generalization we mentioned that the equation x^2-dy^2=1 has infinitely many integer solutions, if d>0 and d is not a square (Pell's equation). We saw that the hard point is to find one solution (with non-zero y), since if we have such a solution, then we can easily generate infinitely many others. We sketched the connection of this question to the approximation theorem of irrational numbers. You may hand in the solution to the third question of Problem 15, as an extra problem, you can use the above result for Pell's equation (it is still not very easy).
February 15: We first solved the second part of Problem 14, and then turned to Problem 12, which showed that some irrational numbers cannot be approximated very well. We generalized our observation to arbitrary algebraic numbers, and this made us possible to construct a transcendental number (see also Section II/9 in the textbook). We solved also Problem 7b. Finally, generalizing 6d we observed that grouping the complex n-th roots of unity according to their order we obtain a factorization of x^n-1 into polynomials with integer coefficients which are irreducible over Q, and described their degrees, as well.
February 21: We discussed the basic definitions and facts about cardinalities (see also Sections II/10 and II/17 in the textbook). We solved Problems 19a, 21, 17 and 15c (partly during the office hour).
February 22: We discussed some interesting properties of the Cantor set (see also Section II/14 in the textbook), and then solved Problem 24 in three different ways: a "secondary school" solution, one using special algebraic numbers, the so called algebraic integers, and one using the degree of roots of unity (see "Algebraic integers and cyclotomic polymonial among the short summaries ). It is worth thinking a little on Problems 27 and 30, we shall investigate them in detail soon. As an eXtra problem you may think on the following questions: Are there other algebraic numbers on the unit circle, than the roots of unity? And are there other algebraic integers there?
February 28: I commented on the returned homework set 2, and gave hints to homework set 3 (and we had also an office hour).
February 29: We discussed Problem 28 in full detail (see "Waring's problem" among the short summaries).
March 6: I commented on the returned homework set 3 (and we had also an office hour).
March 7: We discussed (the "elementary" handling of) Sidon-sets (Problem 30), and (as an application of complex numbers) also Problems 37 and 39 in detail, plus I gave some hints to Homework set 5.
March 13: We solved 34, 27c, and I commented on the returned homework set 4 (partly during the office hour), and we discussed also some generalizations: in 26b we determined which squares can be deleted, so that the rest can be covered by 3x1 dominoes; in 27 the general question is: how many positive integers can be selected in [1,n], so that no r should be pairwise relatively prime; all multiples of the first r-1 primes satisfy this condition, but to show that (for large n) this is the maximum, turned out to be a hard Erdős-problem for general r, and was finally solved in 1995 by Ahlswede and Khachatrian.
March 14: We discussed several solutions of 31, examined the problem for a 5x5 board, and determined the number of attainable colorings for a 4x4 board, using elementary linear algebra. We solved 29, and formulated the two-dimensional version of 29b, also guessing the answer (which was a long-standing unsolved problem, finally proven just a few years ago).
March 20: We discussed the problems of the sample midterm (43-48), and also 36 and 40, mentioning some generalizations and unsolved problems, as well.
March 27: After some comments on the midterm, we got acquainted with a classical result of the fresh Abel-prize winner Endre Szemere'di: If a sequence of positive integers is "dense enough", then it must contain arbitrarily long AP-s; more precisely: Let r_k(n) denote the maximal possible size of a subset of {1,2,...,n} which does not contain a k-term AP. Then, for any fixed k, r_k(n)/n tends to 0, as n tends to infinity. This is a significant generalization of Van der Waerden's theorem, stating, that if we color the positive integers with 2 (or any fixed number of) colors, then we must obtain arbitrarily long arithmetic progressions of the same color. This generalization was conjectured by Erdo"s and Tura'n, and was unsolved for about 30 years. By proving this conjecture, Szemere'di received 1000 dollars, the biggest sum Erdo"s ever had to pay for the solution of his conjectures. Then we discussed three solutions to Problem 49, applying three different arguments of elementary linear algebra. Finally I gave some hints to the homework due tomorrow, and we had some "office minutes", as well.
March 28: We discussed Problems 51, 52, and 53c. We gave two solutions for Problem 51, one with the pigeon hole principle, and one using some linear algebra. The latter provides a quick algorithm to select the suitable numbers, and this has an application in prime factorization. For Problem 53c see also Section I/6 in the textbook, and for the basic facts about vector spaces and fields see also the two handouts and/or Section I/4 in the textbook.
April 10: We proved some basic properties of field extensions (see the handout and/or Section I/4 in the textbook), and solved 60a (plus I gave some further hints to the HW, and left some time for office hour consultation).
April 11: We solved 60f, 59, proved some basic properties of finite fields (see also the handout), illustrated by the construction of a field with 4 elements. As a surprising application, we solved 63 (see also the handout).
April 17: Related to HW 57 we showed that a finite ring is a field iff it has no zero divisors, and (e2) can be interpreted as the extension Z_3(i) since x^2+1 is irreducible over Z_3, hence as a generalization we obtain a field if we take the "complex numbers" over Z_p where x^2=-1 (mod p) is not solvable (these are the primes of form 4k-1). We gave two and half solutions for HW 50b. Then we started to discuss the theory of geometric constructions, to be continued tomorrow. Finally I gave some detailed hints to HW set 8.
April 18: We showed how geometric constructions lead via classical algebra (coordinates) to the theory of field extensions, and proved the impossibility of constructing the classical Greek problems. We also discussed the constructibility of regular polygons and some related number theoretical questions concerning Fermat and Mersenne primes. (See also Sections I/2 and I/3 in the textbook.) We shall see next week that the algebraic theory of constructibility can be useful also in some normal high-school problems: Problem 76 asks for construction in five different situations, where in two of them the construction is easy, but in the other three variants the best way is to transform them into algebra, and use the theory just developed; in two cases we find that construction is possible, but we see no nice geometric method, we just have to follow the construction given by the algebraic operations, and one case turns out to be non-constructible.
April 24: I commented on Homework problems 58, 60 and 61, then we solved three cases from Problem 76.
April 25: We solved the two last cases of Problem 76, one turned out to be constructible, though no "nice" geometric construction seems to be available, whereas the other one is non-constructible. Then we gave three different solutions to Problem 62: one by a counting argument, one by giving an explicit MC-AP-free coloring using divisibility properties by 7 and 17, and one by defining a(n essentially constructive) MC-AP-free coloring using finite fields.
May 2: We discussed homework problems 68 and 80, then proved that any two polygons in the plane of the same area are equidissectible (Bolyai-Gerwien theorem), but this is not true for polyhedra in the space: a cube and a regular tetrahedron are not equidissectible (Hilbert's third problem solved by Dehn, see also Section I/7 in the textbook). Finally we made a short review of the inner product of vectors in the plane and in F^n, where F is the real or the modulo 2 field.
May 8: We discussed homework problems 77 and 78, then proved the Oddtown and Eventown theorems as application of inner product for combinatorial problems (see also the handout). Finally we had some office hour with hints for the last homework set.
May 9: The Hausdorff and Banach-Tarski paradoxes (see also II/12 and 13 in the textbook).
May 15: We discussed homework problems 88 and 89, plus I commented on problems 85 and 87, and then we solved review problems 91-93.
May 16: We solved review problems 94-99.