Next: About this document ...
Discrete Math, First Problem Set (June 23)
REU 2003
Instructor: Laszlo Babai
Scribe: David Balduzzi
Example
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)
Exercise 24
(Submodularity of rank)
rk
rk
rk
rk
for two subsets.
Exercise 25
Prove:
Given a basis
for
and arbitrary vectors
there exists a unique linear map
such that
for all
.
Next: About this document ...
Varsha Dani
2003-07-25