# Discrete Math, First Problem Set (June 23) REU 2003

Instructor: Laszlo Babai
Scribe: David Balduzzi

Example

 (1) (2) (3)

Continuing in this manner we can approximate as by a continued fraction. Terminating the continued fraction after iterations gives us an ordinary fraction, the  convergent.'' For example the convergent of is

Let now and let be the convergent of .

Exercise 1   Prove that the convergents approximate from alternating sides.

Exercise 2   Show .

Exercise 3   Show that for all ,

where the fractions are the convergents of . Infer that the limit of the convergents of is

Exercise 4   (Quadratic approximability) Prove that for all there exist infinitely many fractions such that

Exercise 5   Show increases exponentially in .

Definition 1   A subset of has (Lebesgue) measure zero if for all , the set can be covered by (infinitely many) intervals of total length less than .

Definition 2   Let us say that is good'' if there exists such that there exist infinitely many fractions such that

The next exercise will show that quadratic approximation is the best we can get for most real numbers.

Exercise 6   (Most numbers cannot be super-quadratically approximated) Show that almost all numbers are bad. (I.e., show that the set of good numbers has measure zero.)

Definition 3   An algebraic number is an element of which is a zero of a (not identically zero) polynomial with integer coefficients. The degree of the algebraic number is the smallest degree of a polynomial with integer coefficients of which is a zero. A transcendental number is a number that is not algebraic.

Exercise 7 (Liouville's Theorem)   . If is an irrational algebraic number of degree , then has only a finite number of solutions .

Exercise 8   (Liouville) Prove that there exists an irrational number such that there exist infinitely many solutions to the inequality

Such an is a Liouville number.'' Prove that there are continuum many Liouville numbers.

Exercise 9   Prove: all Liouville numbers are transcendental.

This will complete the proof of Liouville's celebrated result: the existence of transcendental numbers.

Note that the same proof would work with any super-polynomially growing in place of . ( is said to grow super-polynomially if
.)

Later in the 19th century Cantor gave an alternative proof of the existence of transcendental numbers. In contrast to Liouville, Cantor did not produce any explicit transcendental numbers; yet he proved that the overwhelming majority of real numbers are transcendental, by introducing the hierarchy of infinite of cardinalities.

Exercise 10   (Cantor) Show that the set of algebraic numbers is countable, i.e., it can be put in one-to-one correspondence with the positive integers.

Exercise 11   (Cantor) Show that the set of real numbers is not countable.

The following result is a major improvement over Liouville's Theorem; it netted its author a Fields Medal.

Theorem 1   (K. F. Roth) If is an irrational algebraic number then
has only a finite number of solutions .

Definition 1   A monic polynomial is a polynomial where the leading coefficient is 1. For instance, is

Definition 2   An algebraic integer is an algebraic number which is a zero of a monic polynomial with integer coefficients. For instance, and the Golden Ratio are algebraic integers, corresponding to the monic polynomials and .

Exercise 12   Show that if is a rational algebraic integer then is an integer.

Exercise 13   Show: the set of algebraic numbers is a field (it is closed under addition, multiplication, and division).

Exercise 14   Show: the set of algebraic integers is a ring (it is closed under addition and multiplication).

Exercise 15   Let (golden ratio). Show that the continued fraction expansion of is

and the convergents of this continued fraction are the quotients of consecutive Fibonacci numbers. Show that .

Exercise 16   Find the continued fraction expansion of .

Exercise 17   Prove that if a continued fraction is periodic, then its limit is algebraic of degree 2.

Exercise 18   Find the continued fraction expansion for .

Theorem 2   (Dirichlet)(Simultaneous diophantine approximation)
For all and there exist integers and such that

Exercise 19   Prove: for all there exist infinitely many -tuples of integers and such that

For most -tuples of reals, degree- approximation is the best we can get. Formalize and prove this statement:

Exercise 20   Generalize Exercise 6 to simultaneous approximations.

Linear Algebra review - June 23, 2003

For definitions and examples related to fields and vector spaces, see Chapter 2 (handout).

Exercise 21   Show is a field. What you need to show that this set is closed under taking reciprocals.

Exercise 22   (Fundamental Inequality of Linear Algebra).
If are linearly independent vectors in span then .

Exercise 23   (Modularity of dimension)

for two subspaces     and

Exercise 24   (Submodularity of rank)

rkrkrkrk    for two subsets.

Exercise 25   Prove: Given a basis for and arbitrary vectors there exists a unique linear map such that for all .