**Table of contents:**

**Introduction: the general strategy of finding homomorphic spaces****Integral points on hyperplanes: prerequisites****Integral points on hyperplanes****: Bezout, Euclid's algorithm, Gaussian elimination and Smith normal form**

**Introduction**

Number theory is just algebra done over the integers. This seems kind of weird at first -- the integer lattice seems like a rather arbitrary lattice to care about; I mean, if you're looking for solutions for an equation over the reals, you can always show existence and approximate the solution by analytic means, but whether or not an arbitrary real number is an integer is just so *arbitrary*, why would you even CARE about that--

But the integers do have some special structure. The most obvious interesting thing about the integers is *divisibility*. One can show something isn't a solution by taking both sides $\mod b$ for some $b$ -- i.e. one can get restrictions on the space of possible solutions by considering the problem in $\mathbb{Z} \mod b$.

This is an example of a much more general strategy in mathematics to restrict the space of possible solutions -- apply a homomorphism to both sides and eliminate non-solutions in the homomorphic space. If you apply an *isomorphism*, you can also do the converse -- i.e. accept solutions in the isomorphic space.

So we're interested in the structure of $\mathbb{Z}$, so as to know what it can homomorph to. Addition and multiplication are rather important to the structure of $\mathbb{Z}$ -- we like to call this a *ring*. In fact, $\mathbb{Z}$ is the "free ring". If you know any category theory, this means $\mathbb{Z}$ is the ring that has homomorphisms to every other ring.

In basic number theory, there are two sorts of such rings to which we will be interested in homomorphisms to: $\mathbb{Z}/b\mathbb{Z}$ (which we've discussed) and $\mathbb{Z}[\alpha]$ for some non-integer $\alpha$.

This is why the algebraic properties of these rings are of so much importance in number theory -- that's why *algebra* is so important in number theory. The Chinese remainder theorem -- the statement that the obvious projection map $\mathbb{Z}/(n_1\dots n_k)\mathbb{Z}\to\mathbb{Z}/n_1\mathbb{Z}\times\dots\times\mathbb{Z}/n_k\mathbb{Z}$ is a ring isomorphism -- is such an algebraic property. Stuff about quadratic and higher residues (squares mod $b$) are such algebraic properties. Stuff about when $\mathbb{Z}[\alpha]$ is a UFD, PID blabla are such algebraic properties. We will make reference to them throughout this course without getting into the details of things.

So the topic is *solving equations over the integers. *In particular, solving polynomial equations over the integers.

**Integral points on hyperplanes: prerequisites**

The following animation is a picture illustration of Euclid's algorithm:

**Integral points on hyperplanes****: Bezout, Euclid's algorithm, Gaussian elimination and Smith normal form**

$$381x+66y=b$$

So Bezout's identity tells us that the equation $a_1x+a_2y=b$ (by convention $a_1, a_2, b$ are known/"constants" while $x, y, z$ are to be solved for/"variables") is solvable iff $\mathrm{gcd}(a_1,a_2)$ divides $b$. In fact it says the equation $\sum a_ix_i=b$ is solvable iff $\mathrm{gcd}((a_i))$ divides $b$.

In fact it tells us there is an algorithm to compute this solution $x_i$ -- namely, Euclid's algorithm.

To help us generalize this: the nicest way to think of Euclid's algorithm algorithmically is as a sequence of matrix multiplications. E.g.

$$\begin{align}381&=5\times 66+51\\ 66&=1\times 51+15\\ 51&=3\times 15+6\\15&=2\times 6+3\\6&=2\times 3+0\end{align}$$

$$\begin{align}\left[\begin{array}{c}381\\66\end{array}\right]&=\left[\begin{array}{cc}5&1\\1&0\end{array}\right]\left[\begin{array}{cc}1&1\\1&0\end{array}\right]\left[\begin{array}{cc}3&1\\1&0\end{array}\right]\left[\begin{array}{cc}2&1\\1&0\end{array}\right]\left[\begin{array}{cc}2&1\\1&0\end{array}\right]\left[\begin{array}{c}3\\0\end{array}\right]\\&=\left[\begin{array}{cc}127&52\\22&9\end{array}\right]\left[\begin{array}{c}3\\0\end{array}\right]\\ \left[\begin{array}{cc}3&0\end{array}\right] &= \left[\begin{array}{cc}381&66\end{array}\right]\left[\begin{array}{cc}-9&22\\52&-127\end{array}\right] \end{align}$$

So in effect, we're solving the linear equation (where $\mathbf{a},\mathbf{d}$ are row vectors) $\mathbf{a}\mathbf{x}=b$ by instead solving $\mathbf{d}\mathbf{y}=b$ where $\mathbf{d}=\mathbf{a}\mathbf{T}$ is of the form $(d,0)$ and $\mathbf{T}\in\mathrm{GL}(\mathbb{Z}^2)$.

Note also that left- (resp. right-) multiplication by $\left[\begin{array}{cc}\lambda&1\\1&0\end{array}\right]$ can also be understood as "add $\lambda$ copies of Row 1 to Row (resp. Col) 2, then switch Row (resp. Col) 1 and Row (resp. Col) 2" -- i.e.

$$\left[\begin{array}{cc}\lambda&1\\1&0\end{array}\right]=\left[\begin{array}{cc}0&1\\1&0\end{array}\right]\left[\begin{array}{cc}1&0\\\lambda&1\end{array}\right]$$

*GCD-preserving transformations*. (The algorithm to simplify $\mathrm{gcd}(ax+by,cx+dy)$ -- using the identity $\mathrm{gcd}(x+\lambda y, y)=\mathrm{gcd}(x,y)$ -- is precisely Euclid's algorithm.)

But the nice thing about this matrix approach is that it can be used to solve *systems* of linear equations. It is not sufficient to solve these equations independently and state the conditions as $d_1\mid c_1,\dots d_m\mid c_m$, because the solution sets for each equation needn't intersect (think: $3x+6y=3, 3x+9y=3$).

Instead, we solve $\mathbf{A}\mathbf{x}=\mathbf{b}$ by solving $\mathbf{D}\mathbf{y}=\mathbf{c}$ where $\mathbf{D}=\mathbf{S}\mathbf{A}\mathbf{T}$, $\mathbf{c}=\mathbf{S}\mathbf{b}$ and $\mathbf{D}$ is diagonal, $\mathbf{S},\mathbf{T}\in\mathrm{GL}(\mathbb{Z}^n)$. This $\mathbf{D}$ is called the *Smith normal form* of $\mathbf{A}$, and can be seen as a generalization of the Greatest Common Divisor to a set of integer vectors.

## No comments:

## Post a Comment