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$.