Frobenius, Teichmüller lifts, norm and trace

The extension \mathbf{Q}_q/\mathbf{Q}_p is Galois with cyclic Galois group of order d, generated by the Frobenius automorphism \Sigma, the unique automorphism that reduces to x \mapsto x^p on the residue field \mathbf{F}_q. These functions compute \Sigma^e, the Teichmüller lifts, which are the roots of unity of order prime to p, and the trace and norm, which are the sum and the product of the d conjugates \Sigma^i(x). All four reduce their output to its precision; for the norm and trace the output is a padic_t.

Algorithms#

• qadic_frobenius computes the image \Sigma^e(X) of the generator as the root of f congruent to X^{p^e} modulo p, by Newton iteration, and evaluates the input polynomial at it by rectangular splitting. The cost is O(e \log p) multiplications modulo p and O(\sqrt d) multiplications in \mathbf{Z}_q at each precision. Elements of \mathbf{Q}_p are returned unchanged, and for precision 1 the image is computed as a power x^{p^e}.
• qadic_teichmuller lifts a unit x to the root of t^q - t congruent to x modulo p by the Newton iteration t \gets t - (t^q - t)/(q - 1), which costs O(d \log p) multiplications at each precision (Teichmüller lifts).
• qadic_trace computes the power sums S_i of the roots of f by Newton's identities and returns \sum_i c_i S_i for the element \sum_i c_i X^i; the cost is linear in d times the number of terms of f.
• qadic_norm uses N(x) = \exp(\operatorname{Tr}(\log x)) when the unit part is \equiv 1 \pmod p (\bmod 4 for p = 2) and d is large compared with \log N, and otherwise the resultant \operatorname{Res}(f, x), computed as the determinant of the Sylvester matrix modulo p^N (Norm).

The valuation passes through unchanged for \Sigma, is zero for the Teichmüller lift, and is multiplied by d for the norm (N(p^v u) = p^{dv} N(u)); the trace of p^v u is p^v \operatorname{Tr}(u), which can have larger valuation.

Example#

The program works in the extension of degree 3 of \mathbf{Q}_3 defined by the Conway polynomial X^3 + 2X + 1, to precision 3^8. It computes the Teichmüller lift t of the generator, checks that t is a 26th root of unity and that \Sigma(t) = t^3, checks that \Sigma^3 is the identity, and computes the norm and trace of X, which are -f(0) = -1 and minus the coefficient of X^2 in f.

#include <flint/flint.h>
#include <flint/fmpz.h>
#include <flint/padic.h>
#include <flint/qadic.h>

int main(void)
{
    fmpz_t p, e;
    qadic_ctx_t ctx;
    qadic_t x, t, s, u;
    padic_t n;

    fmpz_init_set_ui(p, 3);
    fmpz_init(e);
    qadic_ctx_init_conway(ctx, p, 3, 0, 20, "X", PADIC_SERIES);
    qadic_ctx_print(ctx);

    qadic_init2(x, 8); qadic_init2(t, 8); qadic_init2(s, 8); qadic_init2(u, 8);
    padic_init2(n, 8);

    qadic_gen(x, ctx);

    qadic_teichmuller(t, x, ctx);            /* the (q-1)-th root of unity = X mod 3 */
    flint_printf("t = "); qadic_print_pretty(t, ctx); flint_printf("\n");

    fmpz_set_ui(e, 26);                      /* q - 1 = 26 */
    qadic_pow(u, t, e, ctx);
    flint_printf("t^26 == 1: %d\n", qadic_is_one(u));

    qadic_frobenius(s, t, 1, ctx);           /* Sigma(t) */
    fmpz_set_ui(e, 3);
    qadic_pow(u, t, e, ctx);                 /* t^p */
    flint_printf("Sigma(t) == t^3: %d\n", qadic_equal(s, u));

    qadic_frobenius(s, x, 3, ctx);           /* Sigma^3 = identity */
    flint_printf("Sigma^3(X) == X: %d\n", qadic_equal(s, x));

    qadic_norm(n, x, ctx);
    flint_printf("Norm(X) = "); padic_print(n, &ctx->pctx);
    qadic_trace(n, x, ctx);
    flint_printf(", Trace(X) = "); padic_print(n, &ctx->pctx);
    flint_printf("\n");

    qadic_clear(x); qadic_clear(t); qadic_clear(s); qadic_clear(u);
    padic_clear(n);
    qadic_ctx_clear(ctx);
    fmpz_clear(p); fmpz_clear(e);
    return 0;
}

p    = 3
d    = 3
f(X) = 1 + 2*X + X^3
t = (X) + (X^2)*3 + (1)*3^2 + (2*X^2+1)*3^3 + (X+1)*3^4 + (X)*3^5 + (X+2)*3^6 + (2*X^2+X+2)*3^7
t^26 == 1: 1
Sigma(t) == t^3: 1
Sigma^3(X) == X: 1
Norm(X) = 2 + 2*3^1 + 2*3^2 + 2*3^3 + 2*3^4 + 2*3^5 + 2*3^6 + 2*3^7, Trace(X) = 0

The series form of the norm shows the 3-adic expansion of -1, whose digits are all p - 1 = 2. The relation \Sigma(t) = t^p holds for every Teichmüller lift, because both sides are (q-1)-th roots of unity with the same reduction modulo p.