{"id":2036,"date":"2013-01-24T21:16:00","date_gmt":"2013-01-25T02:16:00","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/?p=2036"},"modified":"2013-01-24T21:16:00","modified_gmt":"2013-01-25T02:16:00","slug":"hensels-lemma-newtons-method-for-p-adic-numbers","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2013\/01\/24\/hensels-lemma-newtons-method-for-p-adic-numbers\/","title":{"rendered":"Hensel's Lemma: Newton's Method for p-Adic numbers"},"content":{"rendered":"

This is, sadly, the last part of my posts about P-adic arithmetic. It’s not for lack of information, but rather for lack of competence on my part. The area of math that I’m worst at is analysis, and an awful lot of the interesting things that you can do with p-adic numbers is analysis.<\/p>\n

For an explanation of what p-adic numbers are, and how arithmetic on them works, you can refer to my first post on the p-adics<\/a>, and for an explanation of p-adic metrics and distance, you can look at this post<\/a>.<\/p>\n

Today, we’re going to look at Hensel’s lemma. This is really cool. Hensel’s lemma shows you a simple way of finding polynomial roots in P-adic arithmetic. It’s sometimes called Newton’s method for p-adics, which is both a good description of how it’s used (but a complete misnomer because the lemma is a description of of a property, and Newton’s method is a description of a procedure).<\/p>\n

Hensel’s lemma says that if you’ve got a polynomial, and for a prime number p, you can find a root using modulo arithmetic using base p, then you can use the base-p root to find the corresponding root using modulo base p2<\/sup>, and given the root using base p2<\/sup>, you can find it for modulo p3<\/sup>, and so on! <\/p>\n

So far, this is just a statement about modulo arithmetic – not<\/em> about p-adic arithmetic. But what ends up happening is that the result modulo p gives you a first approximation of the root in p-adic. Using the process defined by Hensel’s lemma, you can take that root and extend it to a better approximation. It ends up being the case that each time you lift the result to a higher exponent of p, you’re performing the exactly analog of one step in Newton’s method of finding roots! But it’s actually better than that. In you look at Hensel’s lemma in the p-adic numbers, then each step extends the approximation by exactly one digit! <\/p>\n

Let’s look at the lemma in formal terms:<\/p>\n

Suppose that you have a polynomial f(x).<\/p>\n

If there is an integer, i and a prime number p such that for f(i) = 0 in mod p, j such that f(j) = 0 in mod p^2. In general, if there’s an exponent k where f(i) = 0 in mod p^k, then there’s a j where f(j) = 0 in mod p^{k+1}.<\/p>\n

In fact, we can do even better than that! If we know the root i for an exponent k, then we can easily compute j using a process called lifting<\/em>:<\/p>\n

j = i + (p^k)-frac{f(i)}{p^k times f<\/center><\/p>\n

(In this, f is the first derivative of f at i.)<\/p>\n

You can see, looking at that equation, that the derivative of f at i can’t be zero mod p^k, or else the denominator of the fraction would be zero, and everything would go kablooie in your face!<\/p>\n

In P-adic arithemetic, this becomes absolutely amazing. If i is the root mod p^k, then the root mod p^{k+1} is:<\/p>\n

j = i - frac{f(i)}{f<\/center><\/p>\n

It can’t be simpler. And you can clearly see the relation to Newton’s method.<\/p>\n

For fun, let’s try looking at an example: let’s take the square root of 2 in 7-adic. In base-10, the square root of 2 is roughly 1.4142135624. In p-adic, it’s going to bo something completely different. We’ll start by phrasing it as a polynomial: x^2 - 2 = 0. So, what’s the solution to that mod-7? 3: in mod-7, 3*3=2.<\/p>\n

So, our first approximation of a square root of 2 is 3.<\/p>\n

We can extend to the next digit using Hensel’s lemma, and we get j = 3 - 7\/6 = (9-2)\/6 = 7\/6. We’re looking at mod 7 arithmetic here, so 6 = -1. So j = 3 + 7 = 10 = 13.<\/p>\n

Repeated, we’d get 213, 6213, and so on.<\/p>\n","protected":false},"excerpt":{"rendered":"

This is, sadly, the last part of my posts about P-adic arithmetic. It’s not for lack of information, but rather for lack of competence on my part. The area of math that I’m worst at is analysis, and an awful lot of the interesting things that you can do with p-adic numbers is analysis. For […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[43],"tags":[211],"class_list":["post-2036","post","type-post","status-publish","format-standard","hentry","category-numbers","tag-padic"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-wQ","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/2036","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=2036"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/2036\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=2036"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=2036"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=2036"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}