Discrete Math, Ninth Problem Set (July 9th)
REU 2003

Instructor: Laszlo Babai
Scribe: David Balduzzi

READING: Please read the handout on irreducibility of polynomials (last chapter of ``Algebra review'' handout.)

Recall that $\alpha$ is an algebraic number if $\alpha$ is a root of some nonzero polynomial $f$ with rational coefficients. If $f$ has the lowest possible degree then we call $f$ minimal polynomial of $\alpha$. The degree of $\alpha$ is the degree of its minimal polynomial.

Exercise 0.1   Show that the minimal polynomial is irreducible over ${\mathbb{Q}}$.

Exercise 0.2   Lat $f\in\mathbb{\mathbb C}[x]$ with $f(\alpha)=0$. Then $\alpha$ is a multiple root of $f$ if and only if $f'(\alpha)=0$.

The following straightforward observation is used to great effect in many arguments about diophantine approximation and algorithm analysis.

Lemma 0.3   If $z\in\mathbb{Z}$ and $z\neq 0$ then $\vert z\vert\ge 1$.

Theorem 0.4   Liouville
Let $\alpha$ be an algebraic number of degree $n\geq2$. Then

$$\left\vert\alpha-\frac{p}{q}\right\vert\leq\frac{1}{q^{n+1}}$$$$\mbox{ has only a finite number of solutions $(p,q)$\ ($p,q\in{\mathbb{Z}}$). }$$$$$$

Sketch of proof:
By assumption we have $f\in{\mathbb{Z}}[x]$, $\deg(f)=n$, $f(\alpha)=0$ and $\alpha$ is a simple roort of $f$. Therefore $f$ can be written as $f(x)=(x-\alpha)g(x)$, where $g\in {\mathbb{C}}[x]$ and $g(\alpha)\neq 0$. Now

$$\left\vert\alpha- \frac{p}{q}\right\vert=\frac{\left\vert f\left(... ...frac{p}{q}\right)\right\vert} \sim\frac{1}{q^n\left\vert g(\alpha)\right\vert}.$$ (1)

(Why does $f\left(\frac{p}{q}\right)\neq0$ ?) So

$$\frac{1}{q^{n+1}}\ge\left\vert\alpha-\frac{p}{q}\right\vert\gtrsim \frac{c}{q^n}.$$

This implies that $q$ is bounded and therefore there are only a finite number of solutions.

Problem 0.5   (Computational geometry.) Suppose we are to find the shortest path between two points $A$ and $B$ in the plane, avoiding certain straight line segments (``obstacles''). The obstacles are perpendicular to $\overline{AB}$ drawn such that they have ``convex boundary.''

Can the number of candidate optimum paths be bounded by $n^c$, where $n$ is the number of obstacles? In other words can an algorithm be found limiting the number of candidate paths to a polynomial number.

OPEN PROBLEM 0.6   Given positive integers $a_1,\ldots,a_k, b_1,\ldots,b_l$ can we decide in polynomial time (in terms of total bit length) if

$$\sum \sqrt{a_i}>\sum\sqrt{b_i}?$$

Exercise 0.7   Show

$$\prod_{\pm}\sum\pm\sqrt{c_n}\in\mathbb{Z}$$

where we are taking products over all assignments of signs, with the restriction that $\sqrt{c_1}$ always positive.

Suppose we assume that for no choice of signs does $\sum\pm\sqrt{c_i}=0$. Then

$$\left\vert\prod_\pm\sum\pm\sqrt{c_i}\right\vert\geq1$$ implies $$\left\vert\sum\pm\sqrt{c_i}\right\vert\geq\frac{1}{\left(\sum\sqrt{c_i}\right)^{ 2^n-1}}.$$

Problem 0.8   Find a sequence $\{c^n\}$ of sequences such that $c^n$ is a collection of $n$ $n$-digit numbers; with the additional property that for some choice of signs,

$$-$$log$$\left\vert\sum\pm\sqrt{c^n_i}\right\vert\geq\Vert{c^n}\Vert^{N(c)}.$$

Can $-$log $\left\vert\sum\pm\sqrt{c^n_i}\right\vert$ grow faster than $n^{const}$?

Review seventh problem set.

Exercise 0.9   Show coefficient reduction does not affect the sequence ${\mathbf{b}}_1^*,\ldots,{\mathbf{b}}_n^*$.

Exercise 0.10   We denote the Lovász potential function by $\cal P$. Show

$$\frac{{\cal P}_{new}}{{\cal P}_{old}}=\frac{\Vert{{\mathbf{b}}_i^{new*}}\Vert}{\Vert{{\mathbf{b}}_i^{old*}}\Vert}$$

is a (what?) constant factor. (Hint: work only in the space spanned by ${\mathbf{b}}_i$ and ${\mathbf{b}}_{i+1}$.)