IPB University Mathematics Webinar Series

19th March 2021

19th March 2021

- Introduction to Integer Relations
- Computation of Classical Integer Relations
- A Brief Introduction to Algebraic Number Theory
- Algebraic Integer Relations
- Computing Quadratic Integer Relations

For convenience, we will usually think of \( x \in \RR^n \) and \( a \in \ZZ^n \) and say that \( a \) is an integer realtion of \( x \).

Aside: picture proof that \( \arctan{1} + \arctan{2} + \arctan{3} = \pi \)

and so \( (4,-3,4) \) really is an integer relation for \( (\arctan{2}, \pi, \arctan{3}) \).

Euclid's extended algorithm.

- \( a\,m + b\,n = \gcd(a,b) \) relates \( a \), \( b \), and \( \gcd(a,b) \) by integers.
- Each iteration produces incrementally better approximation.
- Also works for real numbers (see Book X, Prop 3).

General case (for more than 2 numbers).

- Sought after by: Euler, Jacobi, PincarĂ©, Minkowski, Perron, Brun, Mahler, and others.
- None proved to work for \( n > 3 \)
- None adequately captured the increasing approximation property.

Generalisations satisfying both properties.

- First one published by Ferguson & Forcade in 1979 with extensive, unpublished notes, by Bergman.
- Several intermediate results (Ferguson & Forcade 1982, Ferguson 1986, Ferguson 1987).
- PSOS algorithm (Ferguson 1988)
- PSLQ algorithm (Ferguson & Bailey 1992)

Can see if a number \( \alpha \) satisfies an integer polynomial by searching for integer relations of \( (\alpha^0, \alpha^1, \dotsc, \alpha^n) \)

Bailey & Ferguson used such a technique to show \( \gamma, \log\gamma, \log\pi, \zeta(3) \) and some others do not satisfy a low-degree polynomial.

Borwein Bailey Plouffe formula \[ \pi =\sum_{k=0}^\infty \left( \frac{1}{16^k} \left( \frac{4}{8k+1} - \frac{2}{8k+4} - \frac{1}{8k+5} - \frac{1}{8k+6} \right)\right)\] found by â€śinspired guessing and extensive searching using the PSLQ integer relation algorithmâ€ť

Bailey & Plouffe use PSLQ to search for (â€śrecogniseâ€ť) symbolic representations of floating point numbers.

E.g., they were able to recognise that \[ 1.6083594219855456\dotso \approx \int_{0}^\infty t^{7/4}\,e^{-t}\,\mathrm{d}t = \frac{21\pi\sqrt{2}}{16\,\Gamma(1/4)} \] (note that the RHS can be reduced to \(\frac{21}{16} \, \Gamma(3/4) \))

Chamberland uses PSLQ to find relationships between functions.

There are many others. See Borwein & LisonÄ›k 2000 â€śApplications of Integer Relation Algorithmsâ€ť (DOI: 10.1016/S0012-365X(99) 00256-3).

We can extend the idea to allow complex numbers.

Note that \( \ZZ[i] = \left\{ a + bi: a,b \in \ZZ \right\} \)

This definition encapsulates the previous one.

- âś… Introduction to Integer Relations
- Computation of Classical Integer Relations
- A Brief Introduction to Algebraic Number Theory
- Algebraic Integer Relations
- Computing Quadratic Integer Relations

When talking about integer relations in general, we use the following notation so as to encapsulate all cases.

We will use \( \FF \) to denote the field of numbers which we are relating and we will use \( \mathcal{O} \) to denote the ring of integers from which the relation elements are from.

The classical cases, then, are when \( \mathcal{O} = \ZZ \) and \( \FF = \RR\), and when \( \mathcal{O} = \ZZ[i] \) and \( \FF = \CC \).

Let \( B = \left\{ b_1, \dotsc, b_n\right\} \subset \FF^n \) be a linearly independent set of vectors. The set \[ L = \left\{ \lambda_1 b_1, \dotsc, \lambda_n b_n : \lambda_1 \in \mathcal{O} \right\} \] is the *lattice spanned by \(B\)*. We call \( B \) the *basis* of the lattice \( L \)

We will sometimes refer to an \( \mathcal{O} \)-lattice if we need to specify the integer ring explicitly.

We can represent a lattice \( L \) as a matrix by using the basis vectors as row vectors.

The lattice spanned by the vectors \( (1, 2, 0) \) and \( (3, 0, 4) \), and \( (0, 5, 6) \) is given by the matrix \[ \begin{bmatrix} 1 & 2 & 0 \\ 3 & 0 & 4 \\ 0 & 5 & 6 \end{bmatrix} \]

Note that the literature often uses column vectors instead of row vectors.

An information theoretic argument shows that in order to numerically compute an integer relation on \( n \) numbers, where the relation consists of integers with no more than \( d \) digits, then at least \( nd \) decimal digits of precision need to be used.

In the case of complex numbers and Gaussian integers, the number of digits is the number of digits in the real part, or the imaginary part, whichever is larger.

The LLL algorithm was introduced by Lenstra, Lenstra Jr, and Lovasz in 1982.

It is not an algorithm for computing integer relations directly. Instead it finds short lattice vectors

It can, however, be used to compute integer relations

Given a basis \( B \) for a lattice \( L \), the LLL algorithm computes a basis \( B^\prime = (b^\prime_1,\dotsc,b^\prime_n) \) such that \[ \begin{gather} \lvert \mu_{i,j} \rvert \le \frac{1}{2} \text{ for } 1 \le j < i \le n \\ \lvert\lvert b^*_i + \mu_{i,j} b^*_{i-1} \rvert\rvert^2 \ge \frac{3}{4} \lvert\lvert b^*_{i-1} \rvert\rvert^2 \text{ for } 1 < i \le n \\ \end{gather} \] where \( b^*_i = b^\prime_i - \sum_{j=1}^{i-1}\mu_{i,j}b^*_j \text{ and } \mu_{i,j} = \frac{ b^\prime_i \cdot b^*_j}{\lvert\lvert b^*_j \rvert\rvert^2} \)

To find an integer relation on \( x = (x_1, \dotsc, x_n) \in \RR^n \) we can use LLL on the lattice \[ L := \begin{bmatrix} 1 & 0 & 0 & \dotsm & 0 & Nx_1 \\ 0 & 1 & 0 & \dotsm & 0 & Nx_2 \\ \vdots & \vdots & \ddots & \dotsm & \vdots & \vdots \\ 0 & 0 & 0 & \dotsm & 1 & Nx_n \end{bmatrix}\] for some \( N \in \RR \).

Think of this as the augmented matrix \( \left[ I_n\, Nx \right] \).

Elements of the lattice look like \[ \left(\lambda_1, \dotsc, \lambda_n, N(\lambda_1x_1 + \dotsm + \lambda_nx_n) \right) \] So if the \( \lambda_i \) are an integer relation for \( x \) then the last term will be 0.

We can prove that if \( N \) is large enough, then the first element of the reduced lattice must contain the integer relation.

For the complex case where n \( z = (z_1, \dotsc, z_n) \in \CC^n \) we still use the augmented lattice \( L := \left[ I_n \, Nz \right] \) like we did for the real case.

However we then construct a 2nd augmented lattice \[ \begin{bmatrix} \Re{L} & \Im{L} \\ -\Im{L} & \Re{L}\end{bmatrix} \] and use LLL on that lattice.

As with the real case, so long as \( N \) is large enough then the procedure must find an integer relation.

In all cases, we don't know how large to make \( N \) before we start. So we must use trial and error.

We have found, experimentally, that with numeric (floating point) calculations it is possible for \( N \) to be too large, even though the theory requires \( N \) to be â€śsufficiently largeâ€ť.

The PSLQ algorithm was introduced by Ferguson & Bailey in 1988. It was later analysed by Ferguson, Bailey, and Arno in 1999

It can handle both the real and complex cases directly.

We will not discuss the details of the algorithm itself. However we will establish some facts.

Observe that in both the real and complex cases \( \mathcal{O} \) forms a lattice, and that \( \mathcal{O} \subset \FF \).

Let \( x \in \FF \). An integer \( a \in \mathcal{O} \) is a *nearest integer* if \( \lvert x-a \rvert \) is maximal.
A function \( \lceil \cdot \rfloor : \FF \to \mathcal{O} \) is a nearest integer functino if it maps each \( x \in \FF \) to one of its nearest integers.

We denote by \( \lceil \cdot \rfloor_{\mathcal{O}} \) if we need to be specific.

There are parameters: \( \gamma, \rho \), and \( \tau \) that must satisfy \[ \begin{gather} \frac{1}{\rho} \ge \lvert x - \lceil x \rfloor \rvert \text{ for all } x \in \FF \\ 1 \le \tau \le \rho \\ \frac{1}{\tau^2} = \frac{1}{\gamma^2} + \frac{1}{\rho^2} \end{gather} \]

\( \rho \) is bounded by the integer lattice; choose to maximise \(1/\rho\).

\( \gamma \) is minimised when \( \tau = 1 \); choose any larger value.

\( \tau \) is fixed by the choice of \( \gamma \) and the value of \( \rho \).

Each iteration of the PSLQ algorithm finds an increased lower bound on the norm of *any* integer relation on the input.

The algorithm can terminate when that bound exceeds some threshold.

If the algorithm finds a relation, \( a \) then \( \lvert\lvert a \rvert\rvert \le \gamma^{n-2}M \) where \( M \) is the norm of the smallest possible relation.

LLL requires more precision than PSLQ

Real Integer Relation Problems

LLL requires more precision than PSLQ

Complex Integer Relation Problems (real constants)

LLL requires more precision than PSLQ

Complex Integer Relation Problems (complex constants)

PSLQ Required Precision (as % of theoretical min).

Real Integer Relation Problems

PSLQ Required Precision (as % of theoretical min).

Complex Integer Relation Problems (real constants)

PSLQ Required Precision (as % of theoretical min).

Complex Integer Relation Problems (complex constants)

LLL takes much more time than PSLQ

Real Integer Relation Problems

LLL takes much more time than PSLQ

Complex Integer Relation Problems (real constants)

LLL takes much more time than PSLQ

Complex Integer Relation Problems (complex constants)

- âś… Introduction to Integer Relations
- âś… Computation of Classical Integer Relations
- A Brief Introduction to Algebraic Number Theory
- Algebraic Integer Relations
- Computing Quadratic Integer Relations

Let \( \FF \) be a field. If \( \FF \) is a subfield of some other field \( \KK \) (i.e., \( \FF \subseteq \KK \) then we call \( \KK \) a *field extension* (or, equivalently an *extension field*) of \( \FF \).

We denote this by \( \KK:\FF \) when we need to be explicit about the base field and the extension.

Note that the literature often uses the notation \( \KK/\FF \) instead.

Let \( \FF \) be a field, and consider an extension field \( \KK:\FF \). An element \( k \in \KK \) is said to be *algebraic over \( \FF \)* if it satisfies
\[ f_nk^n + \dotsm + f_1 k + f_0 = 0 \]
for some \( n \in \NN \) and \( f_i \in \FF \). Note that \( f_n \ne 0 \).

For example \( \sqrt{2} \) satisfies \( k^2 - 2 = 0 \) and so is algebraic over the rationals.

Let \( D \) be an integral domain and consider an extension field \( \KK:\FF \) such that \( D \subseteq \KK \). An element \( k \in \KK \) is said to be *integeral over \( \FF \)* if it satisfies a monic polynomial
\[ k^n + d_{n-1}k^{n-1} + \dotsm + d_1 k + d_0 = 0 \]
for some \( n \in \NN \) and \( d_i \in D \)

An integral domain is a commutative ring with multiplicative identity and no non-zero elements \( d_1, d_2 \) with the property that \( d_1d_2 = 0 \).

Let \( z \in \CC \).

We denote by \( \QQ(z) \) the smallest subfield of \( \CC \) that contains both \( \QQ \) and \( z \).

We denote by \( \ZZ[z] \) the smallest subring of \( \CC \) that contains both \( \ZZ \) and \( z \).

Note that the ring \( \ZZ \) is often called the â€śrational integersâ€ť to avoid ambiguity.

We are primarily interested in extension fields of \( \QQ \).

A number \( z \in \CC \) is an *algebraic number* (or simply *algebraic*) if it is algebraic over \( \QQ \).

A number \( z \in \CC \) is an *algebraic integer* if it is integral over \( \ZZ \).

The ring of all algebraic integers is denoted by \( \mathcal{A} \).

An algebraic extension is *real* if \( \KK \subseteq \RR \) and *complex* otherwise.

We are primarily interested in extension fields of \( \QQ \).

An extension field \( \KK:\QQ \) is an *algebraic extension field* (or simply an *algebraic extension* if every \( k \in \KK \) is an algebraic number.

Its *ring of integers of \( \KK \)*, denoted \( \mathcal{O}_{\KK} \), is \( \KK \cap \mathcal{A} \). We call such rings *algebraic integers*

We are primarily interested in extension fields of \( \QQ \).

The set \( \QQ(\sqrt{5}) \) is an algebraic extension field. Its elements look like \( \{ q_1 + q_2 \sqrt{5} : q_i \in \QQ \} \), such as \( \frac{1}{2} + \frac{32}{101}\sqrt{5} \)

The golden ratio \( \frac{1 + \sqrt{5}}{2} \) is an algebraic integer of \( \QQ( \sqrt{5} ) \) because it satisfies the polynomial \( x^2 - x - 1 = 0 \). Similarly for \( \frac{1 - \sqrt{5}}{2} \).

We will restrict our attention to quadratic extension fields. These are fields of the form:
\[ \QQ( \sqrt{D} ) = \left\{ q_1 + q_2 \sqrt{D} : q_i \in \QQ \right\} \]
wher \( D \in \ZZ \) is *square free*.

Elements of these fields satisfy *quadratic* (or lower degree) polynomials with rational coefficients.

The algebraic integers of a quadratic field (which we call *quadratic integers*) are of the form
\[ \mathcal{O}_{\QQ(\sqrt{D})} = \ZZ[\omega] = \left\{ m_1 + m_2 \omega : m_i \in \mathbb{Z} \right\} \]
where
\[
\omega = \begin{cases} \sqrt{D} & \text{ if } D \equiv 2,3 \;(\operatorname{mod} 4) \\ \frac{1+\sqrt{D}}{2} & \text{ if } D \equiv 1 \;(\operatorname{mod} 4) \end{cases}
\]

\( D \equiv 2,3 \;(\operatorname{mod} 4) \)

\( D \equiv 1 \;(\operatorname{mod} 4) \)

Finally we mention a special class of quadratic fields.

- âś… Introduction to Integer Relations
- âś… Computation of Classical Integer Relations
- âś… A Brief Introduction to Algebraic Number Theory
- Algebraic Integer Relations
- Computing Quadratic Integer Relations

Recall the definiton of an integer relation:

We could try and replace \( \CC \) with an algebraic extension field, and replace \( \ZZ[i] \) with the ring of integers of that field.

However, this won't capture the existing cases.

We could try and replace \( \CC \) with an algebraic extension field, and replace \( \ZZ[i] \) with the ring of integers of that field.

However, this won't capture the existing cases.

The fields \( \RR \) and \( \CC \) are not algebraic fields (although they are extension fields of \( \QQ \) ). Thus they do not have algebraic integers.

If we try to take the intersections anyway (\( \RR \cap \mathcal{A} \) or \( \CC \cap \mathcal{A} \)) we do not get correct integers.

Instead, specify an intermediate extension field.

Let \( \FF \in \{ \RR, \CC \} \) and let \( \KK \) be an algebraic extension field. Let \( \mathcal{O} = \mathcal{O_{\KK}} \).

Let \( x_1, \dotsc, x_n \in \FF \). Integers, \( a_1, \dotsc, a_n \in \mathcal{O} \) are an *algebraic integer relation* (or a \( \KK \)-integer relation) of the original numbers \( x_i \) if
\[ a_1x_1 + \dotsm + a_nx_n = 0 \]

- âś… Introduction to Integer Relations
- âś… Computation of Classical Integer Relations
- âś… A Brief Introduction to Algebraic Number Theory
- âś… Algebraic Integer Relations
- Computing Quadratic Integer Relations

Observe that for an quadratic integer relation: \[ \begin{align*} & \left(m_{1,1} + m_{1,2} \omega\right)\,x_1 + \dotsm + \left(m_{n,1} + m_{n,2}\omega\right)\,x_n \\ =& \left(m_{1,1}x_1 + \dotsm + m_{n,1}x_n \right) + \left(m_{1,2}\, \omega x_1 + \dotsm m_{n,2}\,\omega x_n\right) \end{align*} \]

This suggests a way to reduce a quadratic integer relation to a classical one.

Given \( (x_1, \dotsc, x_n) \in \FF^n \) we compute \( (x_1, \dotsc, x_n, x_1\omega, \dotsc, x_n\omega) \in \FF^{2n} \) and search for a classical integer relation on that.

We recover the integer relation by taking \( a_k + a_{n+k}\omega \) for \( 1 \le k \le n \).

This works well for real quadratic fields (i.e., when \( D > 1 \)). It works less well for complex quadratic fields.

In the complex case, the integers are of the form \( a_k = m_{k,1} + m_{k,2} i \). So when we attempt to recover the relation we get \[ \left(m_{k,1} + m_{k,2} i\right) + \left(m_{k+n,1} + m_{k+n,2} i \right)\omega \] after expansion and some simplification we get \[ \alpha_1 + \beta_2 i \sqrt{\lvert D \rvert} + \alpha_2 i - \beta_2 \sqrt{\lvert D \rvert} \text{ for } \alpha_1, \beta_1 \in \ZZ \] which is not an algebraic integer in \( \QQ(\sqrt{D}) \) if \( \alpha_2 \ne 0 \) or \( \beta_2 \ne 0 \).

Much of the time the reduction technique works fine, and gives good answers even in the complex cases.

When it does not work, we try two techniques to nonetheless extract a relation.

Decomposition method

We observe that \[ \alpha_1 + \beta_2 i \sqrt{\lvert D \rvert} + \alpha_2 i - \beta_2 \sqrt{\lvert D \rvert}\] can be written as \[ \left( \alpha_1 + \beta_2 i\sqrt{\lvert D \rvert} \right) + i \left( \alpha_2 + \beta_2 \sqrt{\lvert D \rvert} \right) \] and we have two possible algebraic integers embedded. We try extracting only these.

Conjugate Method

Given \[ \alpha_1 + \beta_2 i \sqrt{\lvert D \rvert} + \alpha_2 i - \beta_2 \sqrt{\lvert D \rvert} \] a conjugate is \[ \alpha_1 - \beta_2 i \sqrt{\lvert D \rvert} - \alpha_2 i - \beta_2 \sqrt{\lvert D \rvert} \]

Multiplying the number by its conjugate gives an element of \( \mathcal{O}_{\QQ(\sqrt{D})} \). We multiply all elements of the relation by the conjugate of only one of the elements.

Both the methods for correcting the complex case work well in practice.

We do not have proofs that they will always be correct. It is nonetheless easy to just try them, and check the extracted relation.

To compute an algebraic integer n \( z = (z_1, \dotsc, z_n) \in \FF^n \) we still use the augmented lattice \( L := \left[ I_n \, Nz \right] \) like we did for the real case.

However we then construct a 2nd augmented lattice. \[ \begin{bmatrix} \Re{L} & \Im{L} \\ \mathfrak{W_1}{L} & \mathfrak{W_2}{L}\end{bmatrix} \] and use LLL on that lattice.

However we then construct a 2nd augmented lattice. \[ \begin{bmatrix} \Re{L} & \Im{L} \\ \mathfrak{W_1}{L} & \mathfrak{W_2}{L}\end{bmatrix} \] and use LLL on that lattice.

\[ \mathfrak{W_1}{x_k} = \begin{cases} -\sqrt{\lvert D \rvert} \Im{x_k} & \text{ if } \text{ if } D \equiv 2,3 \;(\operatorname{mod} 4) \\ \left(\Re{x_k} - \sqrt{\lvert D \rvert}\Im{x_k} \right)/2 & \text{ if } D \equiv 1 \;(\operatorname{mod} 4) \end{cases} \] \[ \mathfrak{W_1}{x_k} = \begin{cases} -\sqrt{\lvert D \rvert} \Im{x_k} & \text{ if } \text{ if } D \equiv 2,3 \;(\operatorname{mod} 4) \\ \left(\Re{x_k} - \sqrt{\lvert D \rvert}\Im{x_k} \right)/2 & \text{ if } D \equiv 1 \;(\operatorname{mod} 4) \end{cases} \]

As with the other cases, so long as \( N \) is large enough then the procedure must find an algebraic integer relation.

We attempt to modify PSLQ while keeping the existing theory.

We simply use a quadratic integer nearest integer function, and modify the algorithm to allow us to specify the quadratic extension field we wish to use.

We simply use a quadratic integer nearest integer function, and modify the algorithm to allow us to specify the quadratic extension field we wish to use.

This introduces a problem: for real quadratic extension fields, the integers do not form a lattice (there is no unique nearest integer to a field element), so we cannot use the existing theory.

We restrict our attention to the complex cases, then.

We restrict our attention to the complex cases, then.

In these cases we have a more subtle problem.

As \( D \) increases, the parameter \( \rho \) decreases, until eventually \( \rho < 1 \) making it impossible to satisfy the \( 1 < \tau \le \rho \) condition.

In these cases we have a more subtle problem.

As \( D \) increases, the parameter \( \rho \) decreases, until eventually \( \rho < 1 \) making it impossible to satisfy the \( 1 < \tau \le \rho \) condition.

The complex quadratic fields that do not exhibit these problems are exactly: \[ \QQ(\sqrt{-2}), \QQ(\sqrt{-3}), \QQ(\sqrt{-7}), \QQ(\sqrt{-11})\]

As \( D \) increases, the parameter \( \rho \) decreases, until eventually \( \rho < 1 \) making it impossible to satisfy the \( 1 < \tau \le \rho \) condition.

The complex quadratic fields that do not exhibit these problems are exactly: \[ \QQ(\sqrt{-2}), \QQ(\sqrt{-3}), \QQ(\sqrt{-7}), \QQ(\sqrt{-11})\]

These are precisely the complex quadratic norm Euclidean fields.

The complex quadratic fields that do not exhibit these problems are exactly: \[ \QQ(\sqrt{-2}), \QQ(\sqrt{-3}), \QQ(\sqrt{-7}), \QQ(\sqrt{-11}) \]

We note that we've had surprising success with the modified PSLQ on \[ \QQ(\sqrt{-5}), \QQ(\sqrt{-6}), \QQ(\sqrt{-10}) \] even though they do not fit the existing theory.

- âś… Introduction to Integer Relations
- âś… Computation of Classical Integer Relations
- âś… A Brief Introduction to Algebraic Number Theory
- âś… Algebraic Integer Relations
- âś… Computing Quadratic Integer Relations