Formal fields and the ideal of relations

The ca.h module represents a number as an element of a field K = \mathbb{Q}(a_1, \ldots, a_n) \subset \mathbb{C} generated by finitely many extension numbers a_k: algebraic numbers, constants such as \pi, and values f(z) of functions such as \exp, \log or \sqrt{\cdot} at numbers z that are themselves elements of such fields [Joh2021calcium].

Formal fields#

Evaluation at (a_1, \ldots, a_n) is a ring homomorphism \mathbb{Q}[X_1, \ldots, X_n] \to \mathbb{C}. Its kernel

is a prime ideal, the ideal of relations of the generators, and

If I were known, K could be computed with exactly, using Gröbner basis reduction modulo I [CLO2015]. In general, however, I is not known: for K = \mathbb{Q}(\pi, e) it is not even known whether I = \{0\}. FLINT therefore works with a computed ideal J \subseteq I, generated by relations that have been proved, and represents an element of K by a fraction p/q of polynomials with integer coefficients, reduced modulo J. Two consequences are fundamental.

The denominator of every element must be a polynomial that does not vanish at the generators; this is guaranteed because a division is only performed after the divisor has been proved nonzero (see Zero testing). Even with J = I the fraction p/q is not unique: 1/\sqrt{2} and \sqrt{2}/2 are different fractions in \mathbb{Q}(X)/(X^2 - 2). Fields with a single algebraic generator avoid this, since FLINT stores their elements as polynomials of degree less than the degree of the generator (nf_elem.h), which is canonical.

Extension numbers and fields#

An extension number (see ca_ext.h) is either a qqbar_t algebraic number or a function code with arguments: \pi, \gamma, e^z, \log z, \sqrt{z}, z^w, |z|, \operatorname{sgn} z, \operatorname{Re} z, \operatorname{Im} z, \overline{z}, \lfloor z \rfloor, \lceil z \rceil, \arg z, the direct trigonometric functions, \Gamma(z), \operatorname{erf}(z), \operatorname{erfc}(z) and \operatorname{erfi}(z), where the arguments are ca_t numbers of other fields. The depth of an extension number is 0 for algebraic numbers and constants and one more than the maximal depth of the generators of the arguments otherwise, so fields form towers ordered by depth.

Each context keeps a cache of extension numbers without structural duplicates and a cache of fields keyed by their (ordered) lists of generators. An operation on two numbers in different fields first merges the fields (ca_merge_fields): the generator lists are merged and the elements are mapped to the common field by substituting variables. The generators are sorted in the reverse of the structural order of ca_ext_cmp_repr, in which algebraic numbers come first and then numbers by increasing depth. Combined with a lexicographic monomial order (CA_OPT_MPOLY_ORD), the variable of a generator such as e^{\pi} is then larger than the variable of \pi, so reduction modulo J eliminates more complicated generators in favour of simpler ones.

After each operation the result is condensed (ca_condense_field): a result that does not depend on any generator is demoted to \mathbb{Q}, and one that depends on a single algebraic generator is moved to the corresponding number field. Superfluous generators are otherwise kept.

Building the ideal#

When a field with several generators is created, ca_field_build_ideal collects relations of the following kinds. Each one is proved before it is added to J.

Algebraic generators. An algebraic generator a_k with minimal polynomial P_k gives the relation P_k(X_k). If all d conjugates of an algebraic number of degree d \le CA_OPT_VIETA_LIMIT occur as generators a_{i}, \ldots, a_{i+d-1}, Vieta's formulas

are added, where e_j is the elementary symmetric polynomial and P = \sum c_j t^j. The number of terms grows like 2^d, hence the limit.

Roots and powers. A generator u = \sqrt{z} or u = z^{a/b} with a rational exponent a/b satisfies u^2 = z, respectively u^b = z^a (for the principal branch, (z^{a/b})^b = e^{a \log z} = z^a). If z = p/q can be expressed in the current field, the relation q^a X_u^b - p^a (with p and q swapped for negative a) is added.

Logarithms. For the generators \log z_1, \ldots, \log z_r, together with 2\pi i if \pi and i are both generators, integer relations \sum_j c_j \log z_j + c \cdot 2 \pi i = 0 with small coefficients are searched with LLL [LLL1982] from numerical values at CA_OPT_LLL_PREC bits. A candidate relation is proved as follows.

The bound |S| < 2 is checked in ball arithmetic and the product \prod_j z_j^{c_j} = 1 is checked exactly with ca_check_is_one, in a field where the logarithms do not occur. The relation \sum_j c_j X_{\log z_j} + 2c X_\pi X_i is then added. This finds, for example, \log 8 = 3 \log 2 and \log(1 + \sqrt{2}) + \log(\sqrt{2} - 1) = 0.

Exponentials, powers and roots. For the generators g_j of the forms e^{z_j}, \sqrt{z_j}, z_j^{w_j} and algebraic numbers, logarithms L_j with e^{L_j} = g_j are formed (z_j, \frac{1}{2} \log z_j, w_j \log z_j and \log g_j), and integer relations \sum_j c_j L_j + c \pi i = 0 are searched with LLL. Such a relation implies the multiplicative relation \prod_j g_j^{c_j} = (-1)^c, which is added as the binomial \prod_{c_j > 0} X_j^{c_j} \mp \prod_{c_j < 0} X_j^{-c_j}. It is proved exactly: by qqbar.h arithmetic if all the g_j involved are algebraic, and otherwise by proving \sum_j c_j L_j + c \pi i = 0 with ca_check_is_zero (which in turn may use relations between the logarithms). This finds, for example, e^{z} e^{-z} = 1 and \sqrt{6} = \sqrt{2} \sqrt{3}, so that \sqrt{2} \sqrt{3} - \sqrt{6} evaluates to zero as soon as the three square roots meet in one field.

Special functions. For error functions, the relations implied by \operatorname{erf}(-z) = -\operatorname{erf}(z), \operatorname{erfc}(z) = 1 - \operatorname{erf}(z) and \operatorname{erfi}(z) = -i \operatorname{erf}(iz) between generators with equal, opposite or i-related arguments are added (ca_field_build_ideal_erf). For the gamma function, \Gamma(z + n) = z (z+1) \cdots (z+n-1) \Gamma(z) is added for generators whose arguments differ by an integer |n| \le 10 (ca_field_build_ideal_gamma).

Gröbner basis. Finally, if CA_OPT_USE_GROEBNER is set and the relations have moderate degree, the generators of J are replaced by a reduced Gröbner basis computed with Buchberger's algorithm [Buc1965] (fmpz_mpoly_buchberger_naive_with_limits), subject to limits on the number, length and coefficient size of the polynomials. Reduction modulo a Gröbner basis gives normal forms, so that elements of J reduce to zero; if the limits are exceeded, the unreduced relations are kept, which is still sound.

Arithmetic and reduction#

In a field with several generators, arithmetic operates on fractions of multivariate polynomials (fmpz_mpoly_q.h). After each operation, the numerator and the denominator are reduced modulo J by multivariate pseudo-division (_ca_mpoly_q_reduce_ideal), the fraction is canonicalised by removing the polynomial GCD, and monomial factors of the denominator that can be moved to the numerator with the help of a relation are moved (_ca_mpoly_q_simplify_fraction_ideal); for example, if e^{x} and e^{-x} are both generators, so that e^{x} e^{-x} = 1 is known, 1/e^{x} becomes e^{-x}. Elements of number fields use nf_elem.h arithmetic, and elements of \mathbb{Q} use fmpq.

Completeness#

For a field with one algebraic generator, J = I and the representation is canonical. With several algebraic generators, the minimal polynomials together with the relations found as above generate I in the common cases (such as square roots of integers), but not always; this does not affect zero tests, which evaluate algebraic numbers exactly with qqbar.h when needed.

For transcendental generators, completeness is out of reach in general. Schanuel's conjecture [Lan1966] asserts that for \mathbb{Q}-linearly independent complex numbers z_1, \ldots, z_n, the field \mathbb{Q}(z_1, \ldots, z_n, e^{z_1}, \ldots, e^{z_n}) has transcendence degree at least n; it would imply, for example, that e and \pi are algebraically independent, and that the relations between exponentials and logarithms of algebraic numbers are those that follow from \mathbb{Q}-linear relations between the logarithms [CP1978]. The relation searches above are designed to find exactly those relations, so under Schanuel's conjecture they are complete for such fields, up to the size limits of the LLL searches. For other functions (gamma, error functions) only the listed functional equations are known to the implementation, so that, for instance, the reflection formula \Gamma(z) \Gamma(1-z) = \pi/\sin(\pi z) is not used.

Use in FLINT#

• ca_field_build_ideal, ca_field_build_ideal_erf and ca_field_build_ideal_gamma build the ideal; they are called by ca_field_cache_insert_ext when a new field is created.
• ca_merge_fields, ca_condense_field, _ca_mpoly_q_reduce_ideal and _ca_mpoly_q_simplify_fraction_ideal implement field merging, condensation and reduction; every arithmetic function of ca.h uses them.
• The options CA_OPT_VIETA_LIMIT, CA_OPT_LLL_PREC, CA_OPT_USE_GROEBNER and the Gröbner limits control the work done (see Context options); ca_ctx_print shows the fields of a context with their ideals.