BSM, Fall 2018, Conjecture and Proof C&P


My email address is freud@cs.elte.hu.

Course syllabus

General info


Final is on December 17, 12-2 in the usual classroom. We discuss the review problems in class on December 10 and 13.

Midterm is on October 29 (as scheduled). We discuss the sample midterm in class on October 25.


Problem sheets: 1. ; 2. ; 3. ; 4. ; 5. ; 6. ; 7. ; 8. ; 9. ; 10.


Short summaries: 1. Algebraic numbers ; 2. Diophantine approximation ; 3. Cardinalities ; 4. Waring's problem ; 5. All subset sums are distinct ; 6. Rational angles with rational cosines ; 7. Linear algebra ; 8. Field extensions ; 9. Sidon sets ; 10. Coloring arithmetic progressions ; 11. Mersenne and Fermat primes


Assignments

Homeworks are assigned on Thursday and are due on next Thursday. Each problem is one point worth (partial credit is possible), the weekly assignment contains 3 problems from the problem sheets.

HW1. Due on September 20: (i) Any three of the altogether five parts 1/b,c,f,g,h; (ii) Any three of the altogether six parts of Problems 2 and 7; (iii) Problem 8. Problem 10 can replace one of (i), (ii), and (iii).

HW2. Due on September 27: (i) Any three parts of 5; (ii) Any three parts of 6a,b,d,e,f; (iii) One of 11, 13, and 17.

HW3. Due on October 4: Any three of the following seven problems: two parts of 15; 20; two parts of 21; 23; two of 24b,c,d,e; 25; 26.

HW4. Due on October 11: Any three of the following seven problems: two parts of 16; lower bounds in 27; 28; 29; 31; 32a,b; 32c.

HW5. Due on October 15(!): Any three of the following six problems: 33a, 35, 36, 37, 38, 39.

HW6. Due on November 8(!): Any three of the following seven problems: 40, 41, 42b, 43, 44, 46a, 47.

HW7. Due on November 8(!): Any three of the following seven problems: 49, 50, 51a, 52ab, 53a, 54, 55. --- As we discussed Problem 51 in class later, 51a is canceled as a HW option.

HW8. Due on November 15: (i) Any two of the altogether four parts 63b,c,64a,b; (ii) Any two of 66a,b,d,e,f; (iii) 67 or 69 or 71.

HW9. Due on November 29(!): (i) 68 or 70; (ii)-(iii) Any two of 72, 73, 74, 75, 76, and 77a.

HW10. Due on November 29(!): Any three of the following seven problems: 79, 80, 81, 82, 84, 85, 86.

HW11. Last homework, due on December 6: (i) 88 or 89 or 90; (ii)-(iii) Any two of 91 - 96.


Extra problems

(optional)

You can hand in the solutions of these problems without time limit.


What happened in class?

September 10: We "tasted" Problem 9: we gave some upper (see also the first page of Section 8 in the textbook) and lower bounds for the maximal size of a Sidon set in the interval [1,n]. We shall return to better estimates later. Then we gave 5 proofs for 1a (see also Section 1 in the Textbook).

September 13: We solved 1e first (see also Section 1 in the textbook), then after summarizing the basic facts about complex numbers, we solved 1d. We introduced algebraic numbers, minimal polynomial, and degree, and discussed some of their properties (see Handout 1, you are encouraged to prove (a), (b), and (c) on the sheet, but do not try to prove (d), we shall return to it later).

September 17: We proved properties (a), (b), and (c) in Handout 1, solved Problems 4, 3, and 6c, stated the Gelfond-Schneider theorem about powers of algebraic numbers with a non-rational algebraic exponent, and applied it to prove that log base 10 of 3 is transcendental. During the office hour we tried to handle rationally some problems of irrationality.

September 20: Diophantine approximation (see Handout 2, and also eXtra problems X1--X3): The different order of approximation of rational and irrational numbers, the fractional parts of the multiples of an irrational number are dense in interval [0,1], Problem 14 as an application, square root 2 cannot be approximated "too well" (Problem 12). You are encouraged to show that cube root of 2 cannot be approximated too well and to make a conjecture about the poor approximation of algebraic numbers in general depending on their degress - to be discussed next week. This will be the key to construct a transcendental number.

September 24: We proved that if u is algebraic with degree n, then |u-r/s|>c/s^n for some constant c>0, and used it to construct transcendental numbers (see also Section 9 in the textbook). During the office hour we designed mostly umbrellas (see Problem 17).

September 27: We proved some basic facts about cardinalities (see Handout 3 and Section 10 in the textbook), and deduced that "most" numbers are transcendental. We solved problems 22 and 24a.

October 1: After solving 17, we continued to study cardinalities, saw a few interesting phenomenons of set theory, and got acquainted with the Cantor set (see Handout 3 and Sections 10 and 14 in the textbook). You are encouraged to think on Problem 30 to be discussed on Thursday. During the office hour we dealt mostly with zooligal questions (monkeys and fleas), but also tried to count some uncountable sets.

October 4: We solved 13, and then starting from 30 we discussed some aspects of Waring's problem (see Handout 4, to be continued). In the meantime we proved Fermat's Little Theorem and stated its generalization, the Euler-Fermat Theorem after introducing Euler's phi-function.

October 8: We proved G(k)>k in Waring's problem (see Handout 4, and also eXtra problem X4). During the office hour, we recolored the chessboard and crowded pigeons into holes.

October 11: We solved and generalized Problems 15 and 20. The former led us to Pell's equation, where we sketched its connection to Diophantine approximation (see eXtra problem X8); the latter gave rise to several unsolved questions for the small values instead of 2000 (see eXtra problems X5 and X6) and about the related Frobenius problem of non-negative integer solvability of linear Diophantine equations in 3 or more variables (see eXtra problem X7). Then we gave two solutions for 34, one of the proofs was "from the Book" (see Handout 5 and also eXtra problem 9).

October 13: We discussed the answers, generalizations, and some historic notes concerning Problems 27a, 31, and 32 (see also eXtra problems X10 and X11). During the office hour, we mostly dealt with geographic, horticultural, and zoological questions (Problems 35--39; note that Fibonacci numbers arose originally in connection with the reproduction of rabbits).

October 15: We solved Problems 42a, 45 (see Handout 6), and 46b.

October 18: We saw nice solutions of 37 and 38. We summarized some basic facts in linear algebra (see Handout 7), and gave three proofs for Problem 48.

October 25: Review session, we discuss the sample midterm. We solved also Problem 51 (hence 51a is canceled from HW7).

October 29: Midterm.

November 5: We solved 52c and started field extensions, to be continued (see Handout 8). During the office hour we had COMPLEX tasks to handle two sets of HW, not necessarily in LINEAR order.

November 8: We continued to study field extensions (see Handout 8), and solved Problems 63a, 65, and 66c.

November 12: We discussed some generalization of 41, introducing quaternions, and stating the theorems of Hurwitz and Frobenius. We compared the pigeon hole principle and linear algebra solkutions of 50, and showed an application in factorization of integers. During the office hour we extended our knowledge concerning extensions.

November 15: We discussed some basic facts about finite fields (mostly with proofs), and applied finite fields to Problems 78 (see Handout 9) and 77b (see Handout 10). Think on other solutions to Problem 77b relying on hints given in class - to be discussed on Monday (if you present solutions).

November 19: After presenting a counting argument solution to 77b, we stated Van der Waerden's and Szemerédi's theorems (see Handout 10). Then we turned to the algebraic theory of Euclidean geometric construction, and discussed the celebrated problems of squaring the circle, doubling the cube, trisecting an angle and constructing regular polygons, discussing also the related Fermat primes (see Handout 11 and Sections 2 and 3 in the textbook). You are encouraged to think on Problem 83 where two out of the five cases are constructible via elementary geometry.

November 26: We finished the proof of the theorem about the algebraic condition of constructibility, and then solved Problem 83. During the office hour we did some hard work in the fields and at constructions.

November 29: We proved that any two polygons of the same area are equidissectible (Bolyai-Gerwien Theorem), but the analog in the space is false: a cube and a regular tetrahedron are not equidissectible (Hilbert's Third Problem, Dehn's Theorem) (see Section 7 in the textbook). Then we showed some weird phenomena: a bounded set in the plane can be congruent to its proper subset, moreover a set can be the disjoint union of its two "copies", i.e. each subset is congruent to the original set. This is a prelude to the Hausdorff and Banach-Tarski paradoxes to be discussed next week.

December 3: We discussed solutions of Problems 84b, 72, and the application of 73 to construct finite fields. Then we introduced paradoxical decompositions, and verified some surprising equidecomposabilities. During the office hour, we tried to find seemingly remote methods to cope with some geometry problems.

December 6: We discussed the Hausdorff and Banach-Tarski paradoxes (see also Sections 12 and 13 in the textbook), and solved Problem 33b.

December 10 and 13: Review sessions. On December 10 we discussed Problems 97, 98a,b,d, and also 91, 92, 94, 96.