BSM, Spring 2018, Conjecture and Proof C&P

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

Course syllabus

General info

Problem sheets: 1. ; 2. ; 3. ; 4. ; 5.

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 February 15: (i) Any three of the five questions 1b,c,f,g,h; (ii) Any three of the five questions in Problem 5; (iii) Any three of the five questions 6a,b,d,e,f.

HW2. Due on February 22: (i) Either any four (of the altogehter six) parts in 2 and 7; or 8; (ii)-(iii) Any two of the following five: 10; 11; 13; any two parts (of four) in 15; 17.

HW3. Due on March 1: Any three of the following seven problems: any three parts of 16; 20; 22; 23; 25; 26a; 26b.

HW4. Due on March 8: Any three of the following seven problems: any two parts of 21; an two parts of 24b-e; 28; 29; 31; 32a,b; 32c.

HW5. Due on March 12(!): Any three of the following seven problems: 20; 33a; 35; 36; 37; 38; 39.

HW6. Due on April 12(!): Any three of the following seven problems: 40; 41; 42b; 43; 44; 46a; lower bounds in 27.

Extra problems

(optional)

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

X1. Ad 12: Let u=(1+\sqrt5)/2 and d>0. Prove that there are only finitely many fractions r/s satisfying |u-r/s|<1/((\sqrt5+d)s^2).

X2. Ad 18: Prove it.

X3. Ad 20: Find all values of n such that one can assemble a square from n suitable squares.

What happened in class?

February 5: We gave five proofs for the irrationality of square root 5, and proved also the irrationality of e (Problems 1a,e). We introduced the algebraic and transcendental numbers, and discussed some basic facts about them (see Handout 1). You are encouraged to prove properties a, b, and c on the sheet (but do NOT try to prove d).

February 8: We proved the properties a, b, and c on Handout 1, solved Problems 3 and 6c, stated the Gelfond-Schneider theorem about non-rational algebraic powers of algebraic numbers, and applied it to prove that the logarithm of 3 to base 10 is transcendental. Finally, we established some upper and lower bounds for Sidon sets (Problem 9) - to be cont'd.

February 12: We solved Problems 1d and 4, and stated the best known bounds for the size of a finite Sidon set. During the office hour we tried to solve rationally the irrationality HW problems.

February 15: We proved the basic facts about the approximation of rational and irrational numbers (see Handout 2), and solved Problems 14 and 12. We stated that the algebraic numbers cannot be approximated "too well" and this may help to construct a transcendental number. Detailed proofs follow on Monday.

February 19: We proved Liouville's theorem about the poor approximation properties of algebraic numbers, and used this to construct a transcendental number (see Section 9 in the textbook). Finally, we summarized the best known results about approximation. During the office hour we applied several transcendental ideas to approximate the solutions of the HW problems.

February 22: We discussed HW problems 11 and 15. We proved the general result for Pell's equation via approximation. We started to investigate cardinalities, and gave a second proof for the existence of transcendental numbers (see Handout 3 and Section 10 in the textbook).

February 26: We proved the Cantor-Bernstein inequality for cardinalities, and applied it to Problem 24a. We summarized a few other aspects of set theory, including the Continuum Hypothesis. During the office hour we planted letters T onto the real line in Problem 25, painted positive integers in Problem 22, and admired the many smart monkeys in Problem 26b. You are encouraged to think on Problem 30 to be discussed on Thursday.

March 1: We summarized some interesting properties of the Cantor set. Then we solved Problem 30 and investigated its generalizations, i.e. Waring's problem: we gave lower bounds for g(k) and G(k), you are encouraged to finish the proof of the latter. Also, try to think on Problem 34.

March 5: We completed the proof of the general lower bound for G(k) (see Handout 4), and summarized the values of k for which we can improve this bound. We discussed the solutions of Problems 25 and 26b. We noted that the generalized Cantor set when we divide the interval into t parts, discard r parts of these, and continue repeating this process with the remaining parts has always measure 0 and its cardinality is continuum (if t-r>1). During the office hour we colored chessboards and tried to put pigeons into suitable holes.

March 8: We discussed Problem 34 and gave three proofs for the best upper bound there (see Handout 5). During the office hour we investigated some horticultural and zoological questions (weedy garden in Problem 36, squirrels in Problem 35).

March 12: We solved Problems 21, 24c,e, 32, 42a, and 46b. You are encouraged to think on 45.

March 19: Review session discussing the problems of the sample midterm . We solved also Problems 20 and 39.

March 22: Midterm