Elliptic Curves

Finally, Witt Vectors

June 1, 2009 by ellipticcurves

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 Witt vectors, p-adic numbers | Leave a Comment »

More on Teichmüller Representatives

June 1, 2009 by ellipticcurves

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 Witt vectors, p-adic numbers | Leave a Comment »

Motivation for Witt Vectors

June 1, 2009 by ellipticcurves

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 Witt vectors, p-adic numbers | Leave a Comment »

Teichmüller Representatives

January 21, 2009 by ellipticcurves

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 Witt vectors, p-adic numbers | Leave a Comment »

Topological construction of p-adic integers

December 26, 2008 by ellipticcurves

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 by ellipticcurves

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 by ellipticcurves

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 by ellipticcurves

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 by ellipticcurves

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 by ellipticcurves

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

Read the rest of this entry »

Tags: algebraic geometry, maps
Posted in algebraic geometry | Leave a Comment »

Elliptic Curves

Finally, Witt Vectors

More on Teichmüller Representatives

Motivation for Witt Vectors

Teichmüller Representatives

Topological construction of p-adic integers

The ring of p-adic integers

Introduction to p-adic integers

Definition of Elliptic Curves

Bezout’s Theorem

Affine Maps

Pages

Archives

Categories

Blogroll

Meta