Elliptic Curves

Finally, Witt Vectors

June 1, 2009

Now, let us try to do arithmetic operations on $p$ -adic numbers written in terms of Teichmüller representatives. Suppose

$a = t(a_0) + t(a_1)p + t(a_2)p^2 + \ldots$

and

$b = t(b_0) + t(b_1)p + t(b_2)p^2 + \ldots.$

In other words,

$a \equiv a_0 \pmod{p},$

$a \equiv a_0^p + a_1 p \pmod{p^2},$

$a \equiv a_0^{p^2} + a_1^p p + a_2 p^2 \pmod{p^2},$

and ditto for $b.$ Then

$a + b \equiv a_0 + b_0\pmod{p}\\ \text{\ \ \ \ \ \ } \equiv t(a_0 + b_0) \pmod{p}.$

$a + b \equiv a_0^p + a_1 p + b_0^p + b_1 p \pmod{p^2}\\ \text{\ \ \ \ \ \ }\equiv (a_0+b_0)^p + \big(a_1 + b_1 - \sum_{i=1}^{p-1} \frac{1}{p}\binom{p}{i} a_0^i b_0^{p-i} \big)p \pmod{p^2}.$

$a b \equiv a_0 b_0 \pmod{p}\\ \text{\ \ \ \ \ \ } \equiv t(a_0 b_0) \pmod{p}.$

$a b \equiv (a_0^p + a_1 p )( b_0^p + b_1 p) \pmod{p^2}\\\text{\ \ \ \ \ \ } \equiv (a_0 b_0)^p + (a_0^p b_1 + a_1 b_0^p)p \pmod{p^2}.$

So, if we define polynomials in $x = (x_0, x_1, \ldots)$ and $y = (y_0, y_1, \ldots)$

$S_0(x, y) = x_0 + y_0,$

$S_1(x, y) = x_1 + y_1 - \sum_{i=1}^{p-1} \frac{1}{p}\binom{p}{i} x_0^i y_0^{p-i},$

$P_0(x, y) = x_0 y_0,$

$P_1(x, y) = x_0^p y_1 + x_1 y_0^p,$

then

$a+b \equiv t(S_0(a,b)) \pmod{p},$

$a+b \equiv t(S_0(a,b)) + t(S_1(a,b))p \pmod{p^2},$

$ab \equiv t(P_0(a,b)) \pmod{p},$

$ab \equiv t(P_0(a,b)) + t(P_1(a, b))p \pmod{p^2}.$

One can also show that there exist polynomials $S_j(x, y)$ and $P_j(x, y)$ for all integer $j\geq 0$ such that

$a+b \equiv \sum_{j=0}^{i-1} t(S_j(a,b))p^j \pmod{p^i}$ and

$ab \equiv \sum_{j=0}^{i-1} t(P_j(a,b))p^j \pmod{p^i},$

for all $i\geq 1$ , or, more curtly,

$a+b = \sum_{j=0}^{\infty} t(S_j(a,b))p^j$ and

$ab = \sum_{j=0}^{\infty} t(P_j(a,b))p^j.$

In other words, the addition and multiplication of $p$ -adic integers can be written in polynomial form when those numbers are written in terms of Teichmüller representatives.

Tags: p-adic, Teichmüller representatives, Witt vectors
Posted in p-adic numbers, Witt vectors | Leave a Comment »

More on Teichmüller Representatives

June 1, 2009

As I mentioned before, Teichmüller’s great insight was that one might have better luck if using representatives

$t(m) = (m, m^p, m^{p^2}, \ldots)$

for $m = 0, \ldots, p-1$ , instead of integers $0, \ldots, p-1$ themselves. One of the advantages, for example is that this set of representatives is closed under multiplication. In other words, it is an monomorphism of multiplicative monoids from ${\mathbb F}_p$ to ${\mathbb Z}_p.$

But is this really a set of representative? In other words, can every $p$ -adic integer be written as a $p$ -series in $t(0), \ldots, t(p-1)?$ Since $t(m) \equiv m \pmod{p}$ for each $m,$ and integers $0,\ldots, p-1$ form a set of representatives, the answer to this question is yes.

Let’s offer a demonstration. Say we would like to write $5$ -adic integer 7 in terms of Teichmüller representatives. Say,

$7 = t(a_0) + t(a_1)5 + t(a_2)5^2 + \ldots.$

Then

$7 \equiv 2 \pmod{5},$ so let $a_0 = 2.$
$7 \equiv a_0^5 + 5 a_1 \pmod{5^2},$ i.e., $5 a_1 \equiv 7 - 2^5 \equiv 0 \pmod{25}$ , so we take $a_1=0$ .
$7 \equiv a_0^{25} + 5 a_1^5 + 5^2 a_2 \pmod{5^3},$ i.e., $25 a_2 \equiv 7 - 2^{25} - 0^5 \equiv 75 \pmod{125}$ , so we take $a_2=3$ .
$7 \equiv a_0^{125} + 5 a_1^{25} + 5^2 a_2^5 + 5^3 a_3 \pmod{5^4},$ i.e., $125 a_3 \equiv 0 \pmod{125}$ , so we take $a_3=0$ .
etc.

So,

$7 = t(2) + t(0) 5 + t(3) 5^2 + t(0) 5^3 + \ldots.$

Therein lies a seed of the inductive proof of the fact that

$\{t(m) | m\in 0,\ldots, p-1\}$

is a set of representatives. If for a fixed $p$ -adic integer $a$ one can choose $a_0, \ldots, a_{n-1} \in 0,\ldots, p-1$ so that

$a \equiv t(a_0) + t(a_1) p + \cdots + t(a_{n-1}) p^{n-1} \pmod{p^n},$

or, equivalently,

$a \equiv a_0^{p^{n-1}} + a_1^{p^{n-2}} p + \cdots + a_{n-1} p^{n-1} \pmod{p^n},$

then

$a - (a_0^{p^n} + a_1^{p^{n-1}} p + \cdots + a_{n-1}^p p^{n-1}) \equiv 0 \pmod{p^n},$

and there exists $a_n \in 0, \ldots, p-1$ such that

$a - (a_0^{p^n} + a_1^{p^{n-1}} p + \cdots + a_{n-1}^p p^{n-1}) \equiv a_n p^{n} \pmod{p^{n+1}}.$

Then

$a \equiv a_0^{p^n} + a_1^{p^{n-1}} p + \cdots + a_{n-1}^p p^{n-1} + a_n p^{n} \pmod{p^{n+1}},$

or, equivalently,

$a \equiv t(a_0) + t(a_1) p + \cdots + t(a_{n}) p^{n} \pmod{p^{n+1}}.$

The short version is that any overshot modulo $p^{n}$ can be corrected modulo $p^{n+1}$ using only multiples of $p^n.$

Tags: p-adic, Teichmüller representatives
Posted in p-adic numbers, Witt vectors | Leave a Comment »

Motivation for Witt Vectors

June 1, 2009

If we write two $p$ -adic integers $a$ and $b$ as $p$ -series in integers $0, \ldots, p-1,$ and then multiply them together to get $c,$ it goes something like this:

$(a_0 + a_1 p + \cdots)(b_0 + b_1 p + \cdots) = a_0 b_0 + (a_1 b_0 + a_0 b_1) p + \cdots$

Therefore, $c_0 \equiv a_0 b_0 \pmod{p}.$ So far so good. But as we move to the next congruence class, we get

$c_1 \equiv a_1 b_0 + a_0 b_1 + \text{ carry from }a_0 b_0 \pmod{p}.$

Good luck figuring out the formula for the carry part.

Tags: Witt vectors
Posted in p-adic numbers, Witt vectors | Leave a Comment »

Teichmüller Representatives

January 21, 2009

Let us solve a particular equation in $p$ -adic numbers:

$x^p - x = 0.$

Notice that since this equation has precisely $p$ distinct solutions in ${\mathbb F}_p={\mathbb Z}/p {\mathbb Z}$ (actually, all of its elements), by $p$ -adic mojo, it has $p$ solutions in ${\mathbb Z}_p$ .

It is easy to figure out the sequence representations of these solutions:

$(m, m^p, m^{p^2}, \ldots)$

for $m=0,\ldots, p-1$ . By Euler’s Theorem,

$m^{p^r} \equiv m^{p^{r-1}} \pmod{p^{r-1}},$

which takes care of both the condition on sequences defining a $p$ -adic number and the fact that every element of the sequence is a solution of our equation in its respective modular ring.

Teichmüller’s insight was that it might be easier to write down the arithmetic laws on $p$ -adic numbers expressed as $p$ -series in these numbers (zero and $(p-1)$ st roots of unity) rather than just the integers $0, \ldots, p-1$ themselves. But more on that later.

Tags: p-adic, Teichmüller representatives
Posted in p-adic numbers, Witt vectors | Leave a Comment »

Topological construction of p-adic integers

December 26, 2008

One of the interesting things to observe is what multiplication by $p$ does to $p$ -adic integers:

$p(u_1, u_2, u_3, \ldots) = (p u_1, p u_2, p u_3, \ldots).$

But what matters is the congruence class of the components modulo $p^r,$ and $pu_1 \equiv 0 \pmod p,$ $pu_{r}\equiv pu_{r-1} \pmod{p^r},$ so

$p(u_1, u_2, u_3, \ldots) = (0, p u_1, p u_2, \ldots).$

Iterating gives us

$p^n (u_1, u_2, u_3, \ldots) = (\underbrace{0, \ldots, 0}_{n\text{ times}}, p^n u_1, p^n u_2, \ldots).$

This is, of course, a lot easier when using the series notation.

So, we can tell that $p^n$ divides $u$ precisely when the first $n$ components of $u$ are zero. As a corollary, we obtain that if $u\neq 0$ , then there exist a largest $n$ such that $p^n$ divides $u$ (i.e., $p^{n+1}$ does not divide $u$ ). This $n$ is precisely the number of the initial components of $u$ that are congruent to zero in their respective ${\mathbb Z}/p^r{\mathbb Z}.$

Definition. The number $n$ as above is called the $p$ -adic valuation of $u,$ and is denoted by $\mathrm{ord}_p(u)$ :

$\mathrm{ord}_p(u) := \mathrm{max}\{n\in {\mathbb N} | p^n\text{ divides }u\text{ in }{\mathbb Z}_p \}.$

We set $\mathrm{ord}_p(0) = \infty.$

The $p$ -adic valuation function satisfies the following properties:

$\mathrm{ord}_p(u) = \infty$ if and only if $u=0,$
$\mathrm{ord}_p(uv) = \mathrm{ord}_p(u)\mathrm{ord}_p(v),$ and
$\mathrm{ord}_p(u+v) \geq \mathrm{min}(\mathrm{ord}_p(u), \mathrm{ord}_p(v)).$

The last property is referred to as the ultrametric property for reasons to be explained right now.

Given any number $0 < \sigma < 1$ (customarily, $\sigma = 1/p$ ), we can define

$|u|_p := \sigma^{\mathrm{ord}_p(u)}$ .

Then the properties of $\mathrm{ord}_p$ become

$|u|_p \geq 0$ for all $u$ , with $|u|_p = 0$ if and only if $u=0,$

$|uv|_p = |u|_p\, |v|_p,$ and

$|u+v|_p \leq \mathrm{max}(|u|_p, |v|_p).$

In other words, $|\bullet|_p: {\mathbb Z}_p \to {\mathbb R}$ is an ultrametric norm. We can also define a metric

$d_p(u,v) := |u-v|_p,$

which makes ${\mathbb Z}_p$ into an utrametric space. The topology (convergence of sequences) induced by this norm does not change if we choose a different $\sigma$ , so from now on, $\sigma = 1/p$ . Then

$|u|_p = \frac{1}{p^{\mathrm{ord}_p(u)}}.$

In other words, the higher power of $p$ divides you, the smaller you are.

Note that this norm can be restricted to the rational integers ${\mathbb Z}$ contained in ${\mathbb Z}_p$ . The ring of integers is not complete under this norm, and therefore we can consider its completion, i.e., the smallest complete normed space containing ${\mathbb Z}$ . Then the standard construction of the completion coincides for the $p$ -adic norm with the construction of $p$ -adic integers as sequences. Specifically, the condition that $u_r \equiv u_{r+s} \pmod{p^r}$ translates into the Cauchy criterion $d_p(u_r, u_{r+s}) \to 0$ as $r\to 0$ for sequences.

In light of this norm, the series notation also starts to make sense. Indeed, the truncated series form a Cauchy sequence, since $b_r p^r + b_{r+1} p^{r+1} + \cdots + b_{r+s} p^{r+s}$ has norm no greater than $1/p^r$ , which goes to zero as $r$ goes off to infinity. Thus the infinite series we work with converge with respect to the ultrametric $p$ -adic norm.

Tags: p-adic
Posted in p-adic numbers | Leave a Comment »

The ring of p-adic integers

December 26, 2008

In what way can we impose operations of addition, subtraction, and multiplication on the set of $p$ -adic integers? One thing on our wish list is that these operation be compatible with the corresponding operations on the ring of integers embedded in ${\mathbb Z}_p$ . Another, is that they be compatible with the operation on the component considered as elements of ${\mathbb Z}/p{\mathbb Z}.$ It seems that the obvious way to define these operations is componentwise:

$(u_1, u_2, \ldots) + (v_1, v_2, \ldots) := (u_1 + v_1, u_2 + v_2, \ldots);$
$(u_1, u_2, \ldots) - (v_1, v_2, \ldots) := (u_1 - v_1, u_2 - v_2, \ldots);$
$(u_1, u_2, \ldots) \cdot (v_1, v_2, \ldots) := (u_1 v_1, u_2 v_2, \ldots).$

Another way to define these operations is using the “series” notation. We perform these operations just like base $p$ calculations, only digits extend infinitely to the left (some people write $\ldots b_2 b_1 b_0$ instead of the series notation $b_0 + b_1 p + b_2 p^2 + \cdots$ ). For example, $(2 + 1 \cdot 5 + 3 \cdot 5^2 + \cdots)(1 + 2 \cdot 5 + 4 \cdot 5^2 + \cdots) = 2\cdot 1 + (2\cdot 2 + 1\cdot 1) 5 + (2\cdot 4 + 1\cdot 2 + 3\cdot 1) 5^2 + \cdots = 2 + 0\cdot 5 + 4\cdot 5^2 + \cdots.$ We carry 1 toward $5^2$ ‘s and 2 towards $5^3$ ‘s. It’s a bit of an exercise to show that these definitions agree. It is not that difficult to check that these operations make ${\mathbb Z}_p$ into a commutative ring.

Using Abstract Nonsense, the construction of the $p$ -adic numbers as sequences can be reformulated as follows. For each $r$ we have a map

${\mathbb Z}/p^{r+1}{\mathbb Z} \to {\mathbb Z}/p^r{\mathbb Z}$

of reduction modulo $p^r$ , so rings ${\mathbb Z}/p^r{\mathbb Z}$ form an inverse system. Then

${\mathbb Z}_p = \displaystyle\mathop{\mathrm{lim}}_{\longleftarrow}\ {\mathbb Z}/p^r{\mathbb Z},$

the inverse limit of this system. Recall that the inverse limit in the category of rings is constructed by taking all elements of the direct product of all rings in the system (a.k.a. sequences) that “agree” with the reduction maps.

Posted in p-adic numbers | Leave a Comment »

Introduction to p-adic integers

December 25, 2008

I feel like taking a break from elliptic curves and talking about something completely different. For motivation, let’s take a look at solutions of the equation $x^2 + x + 3 \equiv 0 \pmod{5^r}$ for different values of $r.$ For $r = 1,$ we have two solutions: $1, 3 \pmod{5}.$ For $r=2,$ still two solutions: $8, 16 \pmod{25}.$ For $r=3$ we get $33, 91 \pmod{125}.$ And so on, and so forth.

Notice something interesting. Reduce 91 modulo 25, and you get 16. Reduce 16 modulo 5, and you get 1. Similarly, reduce 33 modulo 25 to get 8, which reduces to 3 modulo 5. It seems like a solution modulo 5 begets a solution modulo 25, which then yields a solution modulo 125, etc. No surprise there, since all we are doing is reducing the equation $x^2 + x + 3 \equiv 0 \pmod{5^r}$ modulo $5^{r-1}.$

The question is this. Can we go in the opposite direction and keep this string of solutions going ad infimum? Given a solution modulo 125, can we find one modulo 625? Read the rest of this entry »

Posted in p-adic numbers | Leave a Comment »

Definition of Elliptic Curves

September 19, 2008

I think it is about time we defined what an elliptic curve is. It is a nonsingular cubic curve $C$ with a distinguished point, usually denoted by $\mathcal O$ . We say that the elliptic curve is defined over a field $K$ if the curve $C$ is defined over $K$ and ${\mathcal O} \in C(K)$ .

It turns out that for every field $L/K$ , the set $C(L)$ can be endowed with a structure of an abelian group as follows.

Read the rest of this entry »

Posted in elliptic curves | Leave a Comment »

Bezout’s Theorem

September 3, 2008

We are coming across this theorem so often, that I think it deserves a post of its own. We keep wishing that the number of intersection of two curves defined by equation of degrees $m$ and $n,$ respectively, be $mn,$ but we constantly hit snags. In this post, we try to iron out things out all the way.

Read the rest of this entry »

Posted in Uncategorized | Leave a Comment »

Affine Maps

August 26, 2008

What are acceptable maps between irreducible curves in ${\mathbb A}^2$ ? We start by defining rational maps, which are precisely what they sound like.

Definition. A rational map $\phi: C \to D$ between two irreducible curves is a map given on points of $C$ by $\phi(x, y) = (r(x,y), s(x,y))$ for some rational functions $r, s$ , such that

the denominators of $r, s$ do not identically vanish on $C,$
$\phi(P) \in D$ for all points $P \in C$ where $\phi$ is defined.

For now, we say that $\phi$ is defined over a field $K$ if we can choose $r, s \in K(x,y).$

The first requirement says that $\phi$ should be defined in at least one point of $C$ . We can say more.

Theorem. A rational map is defined on all but finitely many points of the curve $C$ .

Proof. Consider the (not necessarily) irreducible curves $X_1$ and $X_2$ defined by the denominators of $r$ and $s.$ The points of intersection of these curves with $C$ are precisely the points where $\phi$ is undefined. The first condition of the definition means that the defining polynomial $f(x, y)$ of $C$ does not divide the denominators of $r$ and $s,$ which implies that $C$ is not a component of $X_1$ and $X_2.$ By Bezout’s Theorem, each intersection $C \cap X_i$ is finite. So is their union, which is precisely the set at which $\phi$ is undefined. $\square$

Remark. The second condition can be restated as follows. If $D$ is given by $g(x,y)=0$ , then

$g(r(P), s(P))=0,$

for all points $P\in C$ where $\phi$ is defined.

Definition. Similarly, a rational map ${\mathbb A}^1 \to C$ is given by a pair of rational functions in one variable whose image lies in $C$ . A rational map $C \to {\mathbb A}^1$ is called a rational function on $C$ , because that is what it is. The only restriction is that the denominator of this function not identically vanish on $C$ .

We say that two rational maps $\phi_1, \phi_2: C \to D$ of irreducible curves are equivalent (write $\phi_1 = \phi_2$ ) if they agree on all but finitely many points of $C.$ From now on, we consider rational maps modulo this equivalence relation. In this way, domains of rational maps can sometimes be extended by switching to another pair of rational functions that define an equivalent function and are defined in the chosen point $P \in C.$ If this is possible, we say that $\phi$ is regular at $P.$

Example. For every curve $C,$ the identity map ${\mathrm id}_C: C \to C$ is a rational map.

Definition. Let $\phi: C \to D$ be a rational map. If there exists a rational map $\psi: D \to C$ such that $\phi\circ \psi = {\mathrm id}_D$ and $\psi\circ \phi = {\mathrm id}_C,$ we call $\phi$ a birational map, and say that curves $C$ and $D$ are birationally isomorphic, or just birational.

Definition. A rational map on a curve $C$ is said to be regular if it is regular at every point of $C.$ If a map $\phi: C\to D$ of curves is regular, with a regular inverse, we call it an isomorphism and say that curves $C$ and $D$ are isomorphic.

Example. Go back to the parameterization of points on the unit circle. Let $C: x^2 + y^2 = 1$ be the unit circle defined over ${\mathbb Q}$ , and consider maps

$\phi: {\mathbb A}^1 \to C$

given by

$\alpha \mapsto ((1-\alpha^2)/(1+\alpha^2), 2\alpha/(1-\alpha^2)),$

and

$\psi: C \to {\mathbb A}^1$

given by

$(x, y) \mapsto y / (x+1).$

Both maps are rational. The map $\phi$ is defined on the whole of ${\mathbb A}^1$ and therefore is regular. The map $\psi$ is undefined at $(-1, 0)$ and so it is not rational. These maps are inverses of each other. Therefore, in the affine plane, the circle is birationally isomorphic to an affine line, but is not isomorphic.

One of the important points about the previous example is that a map being a birational isomorphism and regular does not guarantee that the inverse is regular. In other words, a regular birational isomorphism is not necessarily an isomorphism.

Example. Generalizing the previous example, we showed using projections that any irreducible conic is birationally isomorphic to ${\mathbb A}^1.$

Example. Any line in ${\mathbb A}^2$ is isomorphic to ${\mathbb A}^1.$ Indeed, if $L:ax+by=c$ is the line in question with $b\neq 0$ , then rational maps $(x, y) \mapsto x$ and $t \mapsto (t, (c-at)/b)$ are regular and inverse to each other.