Hurwitz matrix

2014-01-03T21:13:40Z

46.107.165.6: 1 -> a_{0}

In [[mathematics]], '''Hensel's lemma''', also known as '''Hensel's lifting lemma''', named after [[Kurt Hensel]], is a result in [[modular arithmetic]], stating that if a [[polynomial equation]] has a [[Multiplicity (mathematics)#Multiplicity of a root of a polynomial|simple root]] modulo a [[prime number]] {{math|''p''}}, then this root corresponds to a unique root of the same equation modulo any higher power of {{math|''p''}}, which can be found by iteratively "[[lift (mathematics)|lift]]ing" the solution modulo successive powers of {{math|''p''}}. More generally it is used as a generic name for analogues for [[completion (ring theory)|complete]] [[commutative ring]]s (including [[p-adic field|''p''-adic field]]s in particular) of the [[Newton method]] for solving equations. Since [[p-adic analysis|''p''-adic analysis]] is in some ways simpler than [[real analysis]], there are relatively neat criteria guaranteeing a root of a polynomial.

== Statement ==
Let <math>f(x)</math> be a [[polynomial]] with [[integer]] (or ''p''-adic integer) coefficients, and let ''m'',''k'' be positive integers such that ''m'' ≤ ''k''. If ''r'' is an integer such that

:<math>f(r) \equiv 0 \pmod{p^k}</math> and <math>f'(r) \not\equiv 0 \pmod{p}</math>

then there exists an integer ''s'' such that

:<math>f(s) \equiv 0 \pmod{p^{k+m}}</math> and <math>r \equiv s \pmod{p^{k}}.</math>

Furthermore, this ''s'' is unique modulo ''p''''k''+m, and can be computed explicitly as

:<math>s = r + tp^k</math> where <math>t = - \frac{f(r)}{p^k} \cdot (f'(r)^{-1}).</math>

In this formula for ''t'', the division by ''p''''k'' denotes ordinary integer division (where the remainder will be 0), while negation, multiplication, and multiplicative inversion <math>f'(r)^{-1}</math> are performed in <math>\mathbb{Z}/p^m\mathbb{Z}</math>.

As an aside, if <math>f'(r) \equiv 0 \pmod{p}</math>, then 0, 1, or several ''s'' may exist (see Hensel Lifting below).

=== Derivation ===
The lemma derives from considering the Taylor expansion of ''f'' around ''r''. From <math>r \equiv s \pmod{p^k}</math>, we see that ''s'' has to be of the form ''s = r + tpk'' for some integer ''t''. Expanding <math>f(r + tp^k)</math> gives

:<math>f(r + tp^k) = f(r) + tp^k\cdot f'(r) + O(p^{2k}).</math>

Reducing both sides modulo pk+m, we see that for <math>f(s) \equiv 0 \pmod{p^{k+m}}</math> to hold, we need

:<math>0 \equiv f(r + tp^k) \equiv f(r) + tp^k \cdot f'(r)\pmod{p^{k+m}}</math>

where the ''O''(''p''2''k'') terms vanish because ''k''+''m'' ≤ 2''k''. Then we note that <math>f(r) = zp^k</math> for some integer ''z'' since ''r'' is a root of ''f'' mod ''p''''k'', so
:<math>0 \equiv (z + tf'(r))p^k \pmod{p^{k+m}}</math>,
which is to say
:<math>0 \equiv z + tf'(r) \pmod{p^m}.</math>

Then substituting back ''f''(''r'')/''p''''k'' for ''z'' and solving for ''t'' in <math>\mathbb{Z}/p^m\mathbb{Z}</math> gives the explicit formula for ''t'' mentioned above. The assumption that <math>f'(r)</math> is not divisible by ''p'' ensures that <math>f'(r)</math> has an inverse mod <math>p^m</math> which is necessarily unique. Hence a solution for ''t'' exists uniquely modulo <math>p^m</math>, and ''s'' exists uniquely modulo <math>p^{k+m}</math>.

== Hensel Lifting ==

Using the lemma, one can "lift" a root ''r'' of the polynomial ''f'' mod ''p''''k'' to a new root ''s'' mod ''p''''k''+1 such that ''r'' ≡ ''s'' mod ''p''''k'' (by taking ''m''=1; taking larger ''m'' also works). In fact, a root mod ''p''''k''+1 is also a root mod ''p''''k'', so the roots mod ''p''''k''+1 are precisely the liftings of roots mod ''p''''k''. The new root ''s'' is congruent to ''r'' mod ''p'', so the new root also satisfies <math>f'(s) \equiv f'(r) \not\equiv 0 \pmod{p}</math>. So the lifting can be repeated, and starting from a solution ''r''''k'' of <math>f(x) \equiv 0 \pmod{p^k}</math> we can derive a sequence of solutions ''r''''k''+1, ''r''''k''+2, ... of the same congruence for successively higher powers of ''p'', provided <math>f'(r_k) \not\equiv 0 \pmod{p}</math> for the initial root ''r''''k''. This also shows that ''f'' has the same number of roots mod ''p''''k'' as mod ''p''''k''+1, mod ''p'' ''k''+2, or any other higher power of ''p'', provided the roots of ''f'' mod ''p''''k'' are all simple.

What happens to this process if ''r'' is not a simple root mod ''p''? If we have a root mod ''p''''k'' at which the derivative mod ''p'' is 0, then there is ''not'' a unique lifting of a root mod ''p''''k'' to a root mod ''p''''k''+1: either there is no lifting to a root mod ''p''''k''+1 or there are multiple choices:

::if <math> f(r) \equiv 0 \,\bmod{p^k}</math> and <math> f'(r) \equiv 0 \,\bmod{p},</math> then <math> s \equiv r \,\bmod p^k \Rightarrow f(s) \equiv f(r) \,\bmod p^{k+1}</math>.

That is, <math>f(r + tp^{k}) \equiv 0\,\bmod{p^{k+1}}\, </math> for all integers ''t''.
Therefore if <math> f(r) \not\equiv 0 \,\bmod{p^{k+1}},</math> then there is no lifting of ''r'' to a root of ''f''(''x'') mod ''p''''k''+1, while if <math> f(r) \equiv 0 \,\bmod{p^{k+1}},</math> then every lifting of ''r'' to modulus ''p''''k''+1 is a root of ''f''(''x'') mod ''p''''k''+1.

To see the difficulty that can arise in a concrete example, take ''p'' = 2, ''f''(''x'') = ''x''2 + 1, and ''r'' = 1. Then ''f''(1) ≡ 0 mod 2 and f'(1) ≡ 0 mod 2. We have ''f''(1) = 2 ≠ 0 mod 4 and no lifting of 1 to modulus 4 is a root of ''f''(''x'') mod 4.
On the other hand, if we take ''f''(''x'') = ''x''2 - 17 and then 1 is a root of ''f''(''x'') mod 2 and for every positive integer ''k'' there is more than one lifting of 1 mod 2 to a root of ''f''(''x'') mod 2''k''.

== Hensel's Lemma for ''p''-adic Numbers ==
In the ''p''-adic numbers, where we can make sense of rational numbers modulo powers of ''p'' as long as the denominator is not a multiple of ''p'', the recursion from ''r''''k'' (roots mod ''p''''k'') to ''r''''k''+1 (roots mod ''p''''k''+1) can be expressed in a much more intuitive way. Instead of choosing ''t'' to be an(y) integer which solves the congruence
<math>tf'(r_k) \equiv -(f(r_k)/p^{k})\,\bmod{p^m}\,</math>, let ''t'' be the rational number <math>\ -(f(r_k)/p^{k})/f'(r_k) </math> (the ''p''''k'' here is not really a denominator since ''f''(''r''''k'') is divisible by ''p''''k''). Then set

::<math>r_{k+1} = r_k + tp^k = r_k - \frac{f(r_k)}{f'(r_k)}.</math>

This fraction may not be an integer, but it is a ''p''-adic integer, and the sequence of numbers ''r''''k'' converges in the ''p''-adic integers to a root of ''f''(''x'') = 0. Moreover, the displayed recursive formula for the (new) number ''r''''k''+1 in terms of ''r''''k'' is precisely [[Newton's method]] for finding roots to equations in the real numbers.

By working directly in the ''p''-adics and using the ''p''-adic absolute value, there is a version of Hensel's lemma which can be applied even if we start with a solution of ''f''(''a'') ≡ 0 mod ''p'' such that f'(''a'') ≡ 0 mod ''p''. We just need to make sure the number f'(''a'') is not exactly 0. This more general version is as follows:
if there is an integer ''a'' which satisfies |''f''(''a'')|''p'' < |f′(''a'')|''p''2, then there is a unique ''p''-adic integer ''b'' such ''f''(''b'') = 0 and |''b''-''a''|''p'' < |f'(''a'')|''p''. The construction of ''b'' amounts to showing that the recursion from Newton's method with initial value ''a'' converges in the ''p''-adics and we let ''b'' be the limit. The uniqueness of ''b'' as a root fitting the condition |''b''-''a''|''p'' < |f'(''a'')|''p'' needs additional work.

The statement of Hensel's lemma given above (taking <math>m=1</math>) is a special case of this more general version, since the conditions that ''f''(''a'') ≡ 0 mod ''p'' and f'(''a'') ≠ 0 mod ''p'' say that |''f''(''a'')|''p'' < 1 and |f'(''a'')|''p'' = 1.

== Examples ==
Suppose that ''p'' is an odd prime number and ''a'' is a [[quadratic residue]] modulo ''p'' that is nonzero mod ''p''. Then Hensel's lemma implies that ''a'' has a square root in the ring of ''p''-adic integers '''Z'''''p''. Indeed, let ''f''(''x'')=''x''2-''a''. Its derivative is 2''x'', so if ''r'' is a square root of ''a'' mod ''p'' we have

: <math>f(r) = r^2 - a \equiv 0 \,\bmod{p}</math> and <math>f'(r) = 2r \not\equiv 0 \,\bmod{p}</math>,

where the second condition depends on ''p'' not being 2. The basic version of Hensel's lemma tells us that starting from ''r''1= ''r'' we can recursively construct a sequence of integers { ''r''k } such that

: <math>r_{k+1} \equiv r_k \,\bmod{p^k}, \quad r_k^2 \equiv a \,\bmod{p^k}. </math>

This sequence converges to some ''p''-adic integer ''b'' and ''b''2=''a''. In fact, ''b'' is the unique square root of ''a'' in '''Z'''p congruent to ''r''1 modulo ''p''. Conversely, if ''a'' is a perfect square in '''Z'''p and it is not divisible by ''p'' then it is a nonzero quadratic residue mod ''p''. Note that the [[quadratic reciprocity law]] allows one to easily test whether ''a'' is a nonzero quadratic residue mod ''p'', thus we get a practical way to determine which ''p''-adic numbers (for ''p'' odd) have a ''p''-adic square root, and it can be extended to cover the case ''p''=2 using the more general version of Hensel's lemma (an example with 2-adic square roots of 17 is given later).

To make the discussion above more explicit, let us find a "square root of 2" (the solution to <math>x^2-2=0</math>) in the 7-adic integers. Modulo 7 one solution is 3 (we could also take 4), so we set <math>r_1 = 3</math>. Hensel's lemma then allows us to find <math>r_2</math> as follows:

:<math>f(r_1)=3^2-2=7</math>
:<math>f(r_1)/p^1=7/7=1</math>
:<math>f'(r_1)=2r_1=6</math>
:<math>tf'(r_1) \equiv -(f(r_1)/p^{k-1})\,\bmod{p},</math> that is, <math>t\cdot 6 \equiv -1\,\bmod{7}</math>
:<math>\Rightarrow t = 1</math>
:<math>r_2 = r_1 + tp^1 = 3+1 \cdot 7 = 10 =13_7.</math>

And sure enough, <math>10^2\equiv 2\,\bmod{7^2}</math>. (If we had used the Newton method recursion directly in the 7-adics, then ''r''2 = ''r''1 - f(''r''1)/f'(''r''1) = 3 - 7/6 = 11/6, and 11/6 ≡ 10 mod 72.)

We can continue and find <math>r_3 = 108 = 3 + 7 + 2\cdot 7^2 = 213_7</math>. Each time we carry out the calculation (that is, for each successive value of ''k''), one more base 7 digit is added for the next higher power of 7. In the 7-adic integers this sequence converges, and the limit is a square root of 2 in '''Z'''7 which has initial 7-adic expansion

::<math>3 + 7 + 2\cdot7^2 + 6\cdot 7^3 + 7^4 + 2\cdot 7^5 + 7^6 + 2\cdot 7^7 + 4\cdot 7^8 + \cdots.</math>

If we started with the initial choice <math>r_1 = 4</math> then Hensel's lemma would produce a square root of 2 in '''Z'''7 which is congruent to 4 (mod 7) instead of 3 (mod 7) and in fact this second square root would be the negative of the first square root (which is consistent with 4 = -3 mod 7).

As an example where the original version of Hensel's lemma is not valid but the more general one is, let ''f''(''x'') = ''x''2 - 17 and ''a'' = 1. Then ''f''(''a'') = -16 and f'(''a'') = 2, so |''f''(''a'')|2 < |f′(''a'')|''2''2, which implies there is a unique 2-adic integer ''b'' satisfying ''b''2 = 17 and |''b''- ''a''|2 < |f'(''a'')|2 = 1/2, i.e., ''b'' ≡ 1 mod 4. There are two square roots of 17 in the 2-adic integers, differing by a sign, and although they are congruent mod 2 they are not congruent mod 4. This is consistent with the general version of Hensel's lemma only giving us a unique 2-adic square root of 17 that is congruent to 1 mod 4 rather than mod 2. If we had started with the initial approximate root ''a'' = 3 then we could apply the more general Hensel's lemma again to find a unique 2-adic square root of 17 which is congruent to 3 mod 4. This is the other 2-adic square root of 17.

In terms of lifting roots of ''x''2 - 17 from one modulus 2''k'' to the next 2''k''+1, the lifts starting with the root 1 mod 2 are as follows:

:: 1 mod 2 --> 1, 3 mod 4
:: 1 mod 4 --> 1, 5 mod 8 and 3 mod 4 ---> 3, 7 mod 8
:: 1 mod 8 --> 1, 9 mod 16 and 7 mod 8 ---> 7, 15 mod 16, while 3 mod 8 and 5 mod 8 don't lift to roots mod 16
:: 9 mod 16 --> 9, 25 mod 32 and 7 mod 16 --> 7, 23 mod 16, while 1 mod 16 and 15 mod 16 don't lift to roots mod 32.

For every ''k'' at least 3, there are ''four'' roots of ''x''2 - 17 mod 2''k'', but if we look at their 2-adic expansions we can see that in pairs they are converging to just ''two'' 2-adic limits. For instance, the four roots mod 32 break up into two pairs of roots which each look the same mod 16:

:: 9 = 1 + 23 and 25 = 1 + 23 + 24, 7 = 1 + 2 + 22 and 23 = 1 + 2 + 22 + 24.

The 2-adic square roots of 17 have expansions

::1 + 23 + 25 + 26 + 27 + 29 + 210 + ..., 1 + 2 + 22 + 24 + 28 + 211...

Another example where we can use the more general version of Hensel's lemma but not the basic version is a proof that any 3-adic integer ''c'' ≡ 1 mod 9 is a cube in '''Z'''3. Let ''f''(''x'') = ''x''3 - c and take initial approximation ''a'' = 1. The basic Hensel's lemma can't be used to find roots of ''f''(''x'') since f'(''r'') ≡ 0 mod 3 for every ''r''. To apply the general version of Hensel's lemma we want |f(1)|3 < |f'(1)|32, which means ''c'' ≡ 1 mod 27. That is, if ''c'' ≡ 1 mod 27 then the general Hensel's lemma tells us ''f''(''x'') has a 3-adic root, so ''c'' is a 3-adic cube. However, we wanted to have this result under the weaker condition that ''c'' ≡ 1 mod 9. If ''c'' ≡ 1 mod 9 then ''c'' ≡ 1, 10, or 19 mod 27. We can apply the general Hensel's lemma three times depending on the value of ''c'' mod 27: if ''c'' ≡ 1 mod 27 then use ''a'' = 1, if ''c'' ≡ 10 mod 27 then use ''a'' = 4 (since 4 is a root of ''f''(''x'') mod 27), and if ''c'' ≡ 19 mod 27 then use ''a'' = 7. (It is not true that every ''c'' ≡ 1 mod 3 is a 3-adic cube, e.g., 4 is not a 3-adic cube since it is not a cube mod 9.)

In a similar way, after some preliminary work Hensel's lemma can be used to show that for any ''odd'' prime number ''p'', any ''p''-adic integer ''c'' which is 1 mod ''p''2 is a ''p''-th power in '''Z'''''p''.
(This is false when ''p'' is 2.)

==Generalizations==
Suppose ''A'' is a [[commutative ring]], complete with respect to an [[ideal (ring theory)|ideal]] <math>\mathfrak m_A</math>, and let <math>f(x) \in A[x]</math> be a [[polynomial]] with coefficients in ''A''. Then if ''a'' ∈ ''A'' is an "approximate root" of ''f'' in the sense that it satisfies

:<math> f(a) \equiv 0 \,\bmod{f'(a)^2\mathfrak m}</math>

then there is an exact root ''b'' ∈ ''A'' of ''f'' "close to" ''a''; that is,

:<math>f(b) = 0</math>

and

:<math>b \equiv a \,\bmod{f'(a)\mathfrak m}.</math>

Further, if ''f'' ′(''a'') is not a zero-divisor then ''b'' is unique.

As a special case, if <math>f(a) \equiv 0 \, \bmod{\mathfrak m}</math> and ''f'' ′(''a'') is a unit in ''A'' then there is a unique solution to ''f''(''b'') = 0 in ''A'' such that <math>b \equiv a \, \bmod{\mathfrak m}.</math>

This result can be generalized to several variables as follows:

'''Theorem''': Let ''A'' be a commutative ring that is complete with respect to an ideal '''m''' ⊂ ''A'' and
''f''''i''('''x''') ∈ ''A''[''x''1, …, ''x''''n''] for ''i'' = 1,...,''n'' be a system of ''n'' polynomials in ''n'' variables over ''A''. Let '''f''' = (''f''1,...,''f''''n''), viewed as a mapping from ''A''''n'' to ''A''''n'', and let ''J'''''f'''('''x''') be the [[Jacobian matrix]] of '''f'''. Suppose some '''a''' = (''a''1, …, ''a''''n'') ∈ ''A''''n'' is an approximate solution to '''f''' = '''0''' in the sense that

:''f''''i''('''a''') &equiv; 0 mod (det J'''f'''('''a'''))2'''m'''

for 1 ≤ ''i'' ≤ ''n''. Then there is some '''b''' = (''b''1, …, ''b''''n'') in ''A''''n'' satisfying '''f'''('''b''') = '''0''', i.e.,

:''f''''i''('''b''') = 0 for all ''i'',

and furthermore this solution is "close" to '''a''' in the sense that

:''b''''i'' &equiv; ''a''''i'' mod ''J'''''f'''('''a''')'''m'''

for 1 ≤ ''i'' ≤ ''n''.

As a special case, if ''f''''i''('''a''') ≡ 0 mod '''m''' for all ''i'' and det J'''f'''('''a''') is a unit in ''A'' then there is a solution to '''f'''('''b''') = '''0''' with ''b''''i'' ≡ ''a''''i'' mod '''m''' for all ''i''.

When ''n'' = 1, '''a''' = ''a'' is an element of ''A'' and ''J'''''f'''('''a''') = ''J''''f''(''a'') is ''f'' ′(''a''). The hypotheses of this multivariable Hensel's lemma reduce to the ones which were stated in the one-variable Hensel's lemma.

==Related concepts==
Completeness of a ring is not a necessary condition for the ring to have the Henselian property: [[Goro Azumaya]] in 1950 defined a commutative [[local ring]] satisfying the Henselian property for the maximal ideal '''m''' to be a '''[[Henselian ring]]'''.

[[Masayoshi Nagata]] proved in the 1950s that for any commutative local ring ''A'' with maximal ideal '''m''' there always exists a smallest ring ''A''h containing ''A'' such that ''A''h is Henselian with respect to '''m'''''A''h. This ''A''h is called the '''[[Henselization]]''' of ''A''. If ''A'' is [[noetherian ring|noetherian]], ''A''h will also be noetherian, and ''A''h is manifestly algebraic as it is constructed as a limit of [[étale topology|étale neighbourhood]]s. This means that ''A''h is usually much smaller than the completion ''Â'' while still retaining the Henselian property and remaining in the same [[category theory|category]].

== See also ==
*[[Hasse–Minkowski theorem]]
*[[Newton polygon]]

==References==
* {{Citation | last=Eisenbud | first=David | authorlink=David Eisenbud | title=Commutative algebra | publisher=[[Springer-Verlag]] | location=Berlin, New York | series=Graduate Texts in Mathematics | isbn=978-0-387-94269-8 | id={{MathSciNet | id = 1322960}} | year=1995 | volume=150}}
* {{Citation | last=Milne | first=J. G. | title=Étale cohomology | publisher=[[Princeton University Press]] | isbn=978-0-691-08238-7 | year=1980}}

[[Category:Modular arithmetic]]
[[Category:Commutative algebra]]
[[Category:Lemmas]]

formulasearchengine - User contributions [en]

Hurwitz matrix