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

Instructor: Laszlo Babai
Scribe: David Balduzzi

Example

$$\pi=3+(\pi-3)$$ (1)

$$\pi=3+\frac{1}{\frac{1}{\pi-3}}$$ (2)

$$\pi=3+\frac{1}{7+\frac{1}{15,99659}}$$ (3)

Continuing in this manner we can approximate $\pi$ as by a continued fraction. Terminating the continued fraction after $k$ iterations gives us an ordinary fraction, the ``$k^{th}$ convergent.'' For example the $3^{rd}$ convergent of $\pi$ is

$$3+\frac{1}{7+\frac{1}{15}}=\frac{333}{106}=\frac{g_3}{h_3}$$

Let now $\alpha\in \mathbb{R}$ and let $g_k/h_k$ be the $k^{th}$ convergent of $\alpha$.

Exercise 1   Prove that the convergents approximate $\alpha$ from alternating sides.

Exercise 2   Show $g_kh_{k+1}-g_{k+1}h_k=\pm1$.

Exercise 3   Show that for all $\alpha\in \mathbb{R}$,

$$\left\vert\alpha -\frac{g_n}{h_n}\right\vert < \frac{1}{h_nh_{n+1}},$$

where the fractions $f_n/g_n$ are the convergents of $\alpha$. Infer that the limit of the convergents of $\alpha$ is $$\lim_{k\rightarrow\infty}\frac{g_k}{h_k}=\alpha.$$

Exercise 4   (Quadratic approximability) Prove that for all $\alpha\in \mathbb{R}$ there exist infinitely many fractions $p/q$ such that $\vert\alpha - p/q\vert<1/q^2.$

Exercise 5   Show $h_k$ increases exponentially in $k$.

Definition 1   A subset $S$ of $[0,1]$ has (Lebesgue) measure zero if for all $\epsilon >0$, the set $S$ can be covered by (infinitely many) intervals of total length less than $\epsilon$.

Definition 2   Let us say that $\alpha$ is ``good'' if there exists $\epsilon >0$ such that there exist infinitely many fractions $\frac{p}{q}$ such that

$$\left\vert\alpha-\frac{p}{q}\right\vert<\frac{1}{q^{2+\epsilon}}.$$

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 $\mathbb{C}$ which is a zero of a (not identically zero) polynomial with integer coefficients. The degree of the algebraic number $\alpha$ is the smallest degree of a polynomial with integer coefficients of which $\alpha$ is a zero. A transcendental number is a number that is not algebraic.

Exercise 7 (Liouville's Theorem)   . If $\alpha$ is an irrational algebraic number of degree $n$, then $${\left\vert\alpha-\frac{p}{q}\right\vert<\frac{1}{q^{n+1}}}$$ has only a finite number of solutions $(p,q)$.

Exercise 8   (Liouville) Prove that there exists an irrational number $\alpha$ such that there exist infinitely many solutions $(p,q)$ to the inequality

$$\left\vert\alpha - \frac{p}{q}\right\vert < \frac{1}{q^{q^q}}.$$

Such an $\alpha$ 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 $f(q)$ in place of $q^{q^q}$. ($f(q)$ is said to grow super-polynomially if
$(\forall k)(\exists q_0)(\forall q>q_0)(f(q) > q^k)$.)

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 $\alpha$ is an irrational algebraic number then
$${\left\vert\alpha-\frac{p}{q}\right\vert<\frac{1}{q^{2+\epsilon}}}$$ has only a finite number of solutions $(p,q)$.

Definition 1   A monic polynomial is a polynomial where the leading coefficient is 1. For instance, $x^3-3x+4$ is

Definition 2   An algebraic integer is an algebraic number which is a zero of a monic polynomial with integer coefficients. For instance, $sqrt[3]{2}$ and the Golden Ratio are algebraic integers, corresponding to the monic polynomials $x^3-2$ and $x^2-x-1$.

Exercise 12   Show that if $\alpha$ is a rational algebraic integer then $\alpha$ 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 $\phi=\frac{1+\sqrt{5}}{2}$ (golden ratio). Show that the continued fraction expansion of $\phi$ is

$$1+\frac{1}{1+\frac{1}{1+\dots}}$$

and the convergents of this continued fraction are the quotients of consecutive Fibonacci numbers. Show that $\frac{F_{n+1}}{F_{n}}\rightarrow\phi$.

Exercise 16   Find the continued fraction expansion of $\sqrt{2}$.

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

Exercise 18   Find the continued fraction expansion for $e$.

Theorem 2   (Dirichlet)(Simultaneous diophantine approximation)
For all $\alpha_1,\dots,\alpha_n\in\mathbb{R}$ and $\epsilon >0$ there exist integers $p_1,\dots,p_n$ and $q<\frac{1}{\epsilon^n}$ such that

$$\left\vert\alpha_i-\frac{p_i}{q}\right\vert<\frac{\epsilon}{q}.$$

Exercise 19   Prove: for all $\alpha_1,\dots,\alpha_n\in\mathbb{R}$ there exist infinitely many $(n+1)$-tuples of integers $p_1,\dots,p_n$ and $q\neq 0$ such that

$$\left\vert\alpha_i-\frac{p_i}{q}\right\vert<\frac{1}{q^{1+1/n}}.$$

For most $n$-tuples $(\alpha_1,\dots,\alpha_n)$ of reals, degree-$(1+1/n)$ 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 $\mathbb{Q}[\sqrt[3]{2}]=\{a + b\sqrt[3]{2}+c\sqrt[3]{4}\,\vert\,a,b,c\in\mathbb{Q}\}$ is a field. What you need to show that this set is closed under taking reciprocals.

Exercise 22   (Fundamental Inequality of Linear Algebra).
If $w_1,\dots,w_{\ell}$ are linearly independent vectors in span $\{v_1,\dots,v_k\}$ then $\ell\leq k$.

Exercise 23   (Modularity of dimension)

$$\dim(U_1\cap U_2)+\dim(U_1+U_2)=\dim U_1+ \dim U_2$$ for two subspaces $$U_1$$    and $$U_2;$$

Exercise 24   (Submodularity of rank)

   rk$$(S_1\cap S_2)+$$rk$$(S_1\cup S_2)\leq$$rk$$(S_1)+$$rk$$(S_2)$$    for two subsets.$$$$

Exercise 25   Prove: Given a basis $b_1,\dots,b_n$ for $V_1$ and arbitrary vectors $w_1,\dots,w_n\in V_2$ there exists a unique linear map $f:V_1\rightarrow V_2$ such that $f(b_i)=w_i$ for all $i$.