Frobenius automorphism and Teichmüller lifts in unramified extensions

The extension \mathbf{Q}_q/\mathbf{Q}_p of degree d, q = p^d, is Galois with cyclic Galois group of order d, and reduction modulo p identifies it with the Galois group of \mathbf{F}_q/\mathbf{F}_p [Rob2000, Ch. 3]. The generator \Sigma corresponding to the Frobenius \sigma(x) = x^p of \mathbf{F}_q is the Frobenius automorphism of \mathbf{Q}_q; it is the basic tool of p-adic point counting algorithms such as Kedlaya's [Ked2001] and of the canonical lift methods of Satoh, Skjernaa and Taguchi [SST2003]. The representation of \mathbf{Q}_q = \mathbf{Q}_p[X]/(f) is described in Arithmetic in unramified extensions.

The Frobenius automorphism#

Since \Sigma fixes \mathbf{Q}_p, it is determined by the image of the generator: for g = \sum_i c_i X^i with c_i \in \mathbf{Q}_p, \Sigma^e(g) = \sum_i c_i \, \Sigma^e(X)^i = g(\Sigma^e(X)).

_qadic_frobenius_a computes \xi modulo p^N by Newton's method. It computes X^{p^e} modulo (f, p) by binary powering, inverts f'(\xi) modulo (f, p), and then, along the precision sequence N, \lceil N/2 \rceil, \ldots of The precision sequence, applies

where s approximates f'(\xi)^{-1}; by Lemma 1 of Hensel lifting of inverses, square roots and Teichmüller lifts the precision of \xi and of s doubles in each step. The polynomials f(\xi) and f'(\xi) are compositions: polynomials of degree d and d - 1 with coefficients in \mathbf{Z}_p evaluated at an element of \mathbf{Z}_q.

This is the Paterson–Stockmeyer scheme [PS1973]: about 2\sqrt\ell multiplications in \mathbf{Z}_q and \ell scalar multiplications of elements by integers. FLINT uses it for \ell \ge 6 and Horner's rule for shorter g.

_qadic_frobenius then applies \Sigma^e to an element g by evaluating g(\Sigma^e(X)) with the same algorithm. Two special cases avoid the lifting: an element of \mathbf{Q}_p (length 1) is fixed, and for N = 1 the image is g^{p^e} computed by binary powering modulo (f, p). qadic_frobenius reduces e modulo d, so that negative e give the inverse automorphisms, and applies the map to the unit part, the valuation being unchanged.

qadic_frobenius recomputes \Sigma^e(X) on every call. A caller that applies the same power of \Sigma to many elements can call _qadic_frobenius_a once and evaluate the elements at its result.

Teichmüller lifts#

The Teichmüller lift \omega(x) of a unit x \in \mathbf{Z}_q is the unique (q - 1)-th root of unity congruent to x modulo p. The map x \mapsto \omega(x) is multiplicative, the roots of unity of order prime to p in \mathbf{Q}_q are exactly the Teichmüller lifts, and

because both sides are (q - 1)-th roots of unity congruent to x^p modulo p. _qadic_teichmuller computes \omega(x) as the root of t^q - t congruent to x, by the iteration t \gets t - (q - 1)^{-1}(t^q - t) of Teichmüller lifts, the inverse of q - 1 being lifted alongside. Each step computes t^q by binary powering with exponent q = p^d, which takes about d \log_2 p squarings in \mathbf{Z}_q, so the cost is O(d \log p) multiplications at precision N, against O(\sqrt d) for one application of \Sigma. For an element of \mathbf{Z}_p the lift is computed in \mathbf{Z}_p by _padic_teichmuller, where the exponent is p.

Use in FLINT#

• _qadic_frobenius_a computes \Sigma^e(X) modulo p^N for 0 < e < d.
• _qadic_frobenius and qadic_frobenius apply \Sigma^e to an element.
• _qadic_teichmuller and qadic_teichmuller compute Teichmüller lifts; _padic_teichmuller and padic_teichmuller do the same in \mathbf{Z}_p.
• qadic_trace and qadic_norm do not use the Frobenius map; they use Newton's identities, resultants and logarithms (Trace).