> < ^ From:

> < ^ Subject:

Dear GAP-Forum,

Tim Boykett asked:

I have been digging around the code for roots of unity in the

rings Z_n, and have found a technique called the "Newton/Hensel

method of lifting". Does anyone have a reference that might explain

the algorithm, proof of its validity, etc.

Hensel lifting is basically a generalization of the classical Newton

method (to find roots numerically) to $p$-adic approximations instead

of the classical complex absolute value. Basically any book on

algebraic number theory that covers the p-adic numbers has a section

on it. (Neukirch's ``Algebraische Zahlentheorie'', Cassel's ``Local

fields'' or even van der Waerdens ``Algebra'' come to mind.) (Be

aware, however, that these descriptions sometimes are rather

nonconstructive and don't show how to improve approximations modulo

p^n but just show the existence of an appropriate element in the local

field.)

For constructive versions any book on computer algebra should describe

the method when describing the standard Hensel lifting process for

factorization of polynomials over the rationals. (Personally I prefer

Cohen's ``A Course in Computational Algebraic Number Theory'', but

there are many other as for example ``Algorithms for Computer Algebra''

by Geddes, Czapor and Labahn.) The classical reference is Zassenhaus'

seminal paper in J. Number Theory, 1 (1969), 291--311.

(Concerning that you are in Linz, I think anyone at RISC can give you

an explanation also.)

The validity of the Algorithm is probably best seen by simply

evaluating the lifted result modulo the appropriate power of the

prime; the existence of an appropriate element in the valuation ring

of Q_p (usually also denoted by Z_p, which can lead to confusion) then

follows by a simple limit argument.

As you are just searching for solutions in Z/p^nZ then just run the

lifting to the appropriate accuracy.

I also have run up against the problem that Gap guarantees

accuracy in RootsUnityMod only for k-th roots where k is a prime

number. I want to find the (p-1)th roots of 1 in Z_(p^i) for various

i. For p > 3, then p-1 is nonprime. How can the algorithm be

extended to deal with such cases?

(A necessary condition is that the extensuion given by the p-1-st

roots of unity is nonramified, but this is given for your case.)

Probably the easiest way is to implement a Hensel lifting up to the

correct accuracy yourself (the formulae are written explicitely in the

books, it's probably just 10 lines or so of code). There is a general

Hensel lifting in GAP, used for factorizing polynomials over Q, but it

is rather hidden and not well interfaced to be used alone; in the

terms of the computer algebra books you would lift the factorization

of (x^(p-1)-1).

If my description still sounds cryptic, please write to me directly

and I will provide you with more help.

Best,

Alexander Hulpke

> < [top]