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