In conversations with my office mate, he has been kind to introduce me to his work and show me the main objectives of the research topics he is looking into. On the other hand, I have been trying to persuade him into looking at more computational aspects of his project using programming tools.

While exploring multiprecision libraries—a project that grew on me due to the interest of providing formal verification of the arithmetic propagation errors in FEM computations—I found FLINT, a GNU LGPL v3 C library for number theory.

I will try to present some of the preceding work done by his advisor, and some of the code I wrote to play around with these objects in C++.

Prometheus’ fire

Teto’s work is based on the work of Derek,¹ that is, arithmetical dynamical systems. One of the main questions is to address the question to what extent do polynomial maps behave like random set maps?

Finding stones

A discrete dynamical system consists of a set $S$ and a function $f: S \to S$ . Our object of study are the elements $x \in S$ that are stable under the action of $f$ .

We say a point $x \in S$ is periodic if there exists $n \geq 1$ such that $f^{(n)}(x) = x$ ;
We say a point $x \in S$ is pre-periodic if there exists $n > m \geq 1$ such that $f^{(n)}(x) = f^{(m)}(x)$ .

Denote the family of periodic points of $f$ in $S$ by $\mathrm{Per}(f,S)$ . Given a family of functions $\mathcal{F} \subset \mathsf{Hom}_\mathsf{Set}(S,S)$ , we are interested in studying the growth of the average number of periodic points for the collection $\mathcal{F}$ , this is, the number

\frac{1}{\lvert \mathcal{F} \rvert} \sum_{f \in \mathcal{F}} \lvert \mathrm{Per}(f, S) \rvert.

Shelter for later

For our² purposes, we are interested in studying dynamics in finite fields. I will try to introduce these objects very briefly!

The key recipes here are some simple results from algebra: a quotient ring is a field (integral domain), if and only if the ideal we quotient by is maximal (prime).

Given a (positive) prime number $p \in \mathbb{Z}$ , one can consider the quotient $\mathbb{Z} / p\mathbb{Z}$ . Clearly, it is an integral domain. One can check that $p\mathbb{Z}$ is maximal, or that the quotient $\mathbb{Z} / p\mathbb{Z}$ is a field; we focus on the latter. Denote this field by $\mathbb{F}_p$ .

We can form more fields upon reusing a similar trick: if we consider the polynomial ring $\mathbb{F}_p [X]$ and we pick (any) irreducible polynomial $g_n(X) \in \mathbb{F}_p [X]$ of degree $\deg(g_n) = n > 1$ , then the quotient $\mathbb{F}_p [X] / (g_n(X))$ is a field again! Upon verifying that all finite fields of the same cardinality are homomorphic, we set $\mathbb{F}_{p^n} \cong \mathbb{F}_p [X] / (g_n(X))$ .

Making things tractable

It will be of interest to focus on the dynamics of these polynomials over finite fields, thus, $\mathcal{F} \subseteq \mathbb{F}_{p^n} [X]$ . Usually, $\mathcal{F} = \left\{ f \in \mathbb{F}_{p^n} [X] \colon \deg(f) = m \right\}$ for $m \in \mathbb{N}$ . Our² focus are the cases $m \in \{2, 3\}$ .

It will be important, though somewhat tacit, to lift our computations to a more amenable setting.

One point perspective

Projective geometry allows us to reinterpret the behavior of polynomials, allowing us to extend it to infinity naturally. I may not be able to make full justice to the depth of these topics.

A projective space is, simply, a space of lines to infinity. Given a field $\mathbb{K}$ , the projective space $\mathbb{P}^n(\mathbb{K})$ can be defined as $(\mathbb{K}^{n+1} \setminus \{0\} ) \diagup \sim$ , where

(x_0, \dots, x_n) \sim (y_0, \dots, y_n) \Leftrightarrow \exists k \in \mathbb{K} \setminus \{0\} \colon (k \cdot x_0, \dots, k \cdot x_n) = (y_0, \dots, y_n).

An element of $x \in \mathbb{P}^n(\mathbb{K})$ can be written as

x = [x_0 \colon x_1 \colon \dots \colon x_n].

One with the constellations

Thus, we are interested in computing the set of stable points of

\mathcal{F} = \left\{ f \in \mathbb{F}_{p^n} [X] \colon \deg(f) = m \right\}

for the set of projective points

S = \mathbb{P}^1(\mathbb{F}_{p^n}).

In this case, the functions $f \in \mathbb{F}_{p^n} [X]$ act on the projective points quite nicely, homogenizing the polynomial naturally. Given $[x \colon y] \in \mathbb{P}^1(\mathbb{F}_{p^n})$ , we may write

f([x \colon y]) = [\operatorname{hom}(f)(x,y) \colon y^{\deg(f)}],

where $\operatorname{hom}(f)(x,y) \in \mathbb{F}_{p^n} [X, Y]$ is a homogeneous polynomial of degree $\deg(f)$ satisfying

f(x) = \operatorname{hom}(f)(x,1).

Igniting the flame with FLINT

Given the previous context, it would be of interest to study the behavior of the estimate above, in the context of projective points of a finite field. Instead of reimplementing all these objects from scratch, we rely on a well-developed number theory library, FLINT.

Using the perks of modern C++

As FLINT is a C library,³ I wrapped some of the C API with classes: RAII is employed, operator functions are provided, and the rules of zero/three/five are implemented.

One of the cool things of C++20 is the inclusion of concepts and constraints, which extend the traits system of C++11. The latter provides information on a type, while the former allows restrictions on the allowed types for generic functions.

template <typename T>
struct IsContext : std::false_type {};

template <typename T>
concept HasRingOperations = requires(T a, T b) {
    { a + b } -> std::same_as<T>;
    { a * b } -> std::same_as<T>;
    { -a } -> std::same_as<T>;
    { a - b } -> std::same_as<T>;
};

template <typename T>
concept HasFieldOperations = HasRingOperations<T> && requires(T a, T b) {
    { a / b } -> std::same_as<T>;
};

As mentioned earlier on, the key goal for me was to wrap the code in a memory-safe syntax.⁴ Using a basic container class with all the corresponding memory operations defined, one should verify the mantra “resource acquisition is initialization.”

class Integer {
    fmpz_t val_;

  public:
    Integer() { fmpz_init(val_); }
    ~Integer() { fmpz_clear(val_); }
    Integer(const Integer& other) {
        fmpz_init_set(val_, other.val_);
    }
    Integer(Integer&& other) noexcept
    {
        fmpz_init(val_);
        fmpz_swap(val_, other.val_);
    }
    Integer& operator=(const Integer& other)
    {
        fmpz_set(val_, other.val_);
        return *this;
    }
    Integer& operator=(Integer&& other) noexcept
    {
        fmpz_swap(val_, other.val_);
        return *this;
    }

I decided to include some simple header-only libraries to simplify the design of executables and testing: in this case, we are using p-ranav/argparse and doctest/doctest.

int main(int argc, char* argv[]) {
    argparse::ArgumentParser program("dynfq");

    program.add_argument("-p", "--prime")
        .help("The prime number for the finite field")
        .required()
        .scan<'i', std::size_t>();

    // ...
    auto p = program.get<std::size_t>("--prime");
    // ...
    FiniteFieldNmodContext fq(p, n, field_var.c_str());
    FiniteFieldNmodPolyContext fq_poly(fq, {"x", "y", "r", "s"});
    FiniteFieldNmod r(fq, exp_r), s(fq, exp_s);
    // ...

This allowed me to design a simple and nice driver, with varying polynomial variables and field order. It even allows using different variable names!

Garton, Derek. “Periodic points of polynomials over finite fields.” Transactions of the American Mathematical Society 375, no. 7 (2022): 4849-4871. DOI. arXiv. ↩
I might say our, but it is their goal. ↩ ↩²
There is a C++ interface FLINTXX but the last commit was done three years ago. ↩
Memory-safe, in the sense of employing the tools that modern C++ provides. ↩

FLINT and silicon