A fast algorithm to find reduced hyperplane unit cells and solve N-dimensional Bézout's identities

Cayron, C.

doi:10.1107/S2053273321006835

research papers

FOUNDATIONS
ADVANCES

ISSN: 2053-2733

Volume 77| Part 5| September 2021| Pages 453-459

https://doi.org/10.1107/S2053273321006835

Open

access

A fast algorithm to find reduced hyperplane unit cells and solve N-dimensional Bézout's identities

Cyril Cayron ^a ^*

^aLaboratory of Thermo Mechanical Metallurgy (LMTM), PX Group Chair, EPFL, Rue de la Maladière 71b, Neuchâtel, 2000, Switzerland
^*Correspondence e-mail: cyril.cayron@epfl.ch

Edited by L. Palatinus, Czech Academy of Sciences, Czech Republic (Received 1 February 2021; accepted 1 July 2021; online 13 August 2021)

Deformation twinning on a plane is a simple shear that transforms a unit cell attached to the plane into another unit cell equivalent by mirror symmetry or 180° rotation. Thus, crystallographic models of twinning require the determination of the short unit cells attached to the planes, or hyperplanes for dimensions higher than 3. Here, a method is presented to find them. Equivalently, it gives the solutions of the N-dimensional Bézout's identity associated with the Miller indices of the hyperplane.

Keywords: N-dimensional Bézout's identity; hyperplane unit cell; integer relation; twinning.

1. Introduction

How to determine a unit cell attached to a plane $[{\bf{p}} = (h,k,l)]$ ? This problem occurs for example in the crystallographic models of twinning, when the obliquity or the shear values must be calculated for many planes. It is intuitively solved for low-index planes, but the solutions are more difficult to obtain for high-index planes. In addition, if a unit cell can be found, can it be reduced to a smaller one? In dimension N, the difficulty of finding a small unit cell attached to a hyperplane of dimension [N - 1] becomes even more pronounced. Let us express mathematically this `hyperplane unit-cell problem' by the notations detailed in Appendix A. We assume that a hyperplane is known only by its Miller indices h,k,l which are coprime integers, or equivalently by its normal which is expressed as an integer vector of coordinates h,k,l in the reciprocal space. We want to determine a small unit cell such that one short integer vector of the cell points to a node of the first layer parallel to the hyperplane, and the other [N - 1] short integer vectors lie in the hyperplane. The `out-of-plane' vector and the `in-plane' vectors are noted $[{\bf b}_{1}]$ and $[ {{\bf b}}_{2},\ldots, {{\bf b}}_{j},\ldots, {{\bf b}}_{N}]$ , respectively. The vector $[{{\bf{b}}_1}]$ is such that $[{{\bf p}}^{\rm t}{\bf b}_{1} = 1]$ , and the [N - 1] vectors $[{{\bf{b}}_2}, \ldots, {{\bf{b}}_j}, \ldots, {{\bf{b}}_N}]$ are such that $[{{\bf p}}^{\rm t}{\bf b}_{j} = 0]$ . The coordinates of the vector $[{{\bf{b}}_1}]$ constitute a solution of the N-dimensional Bézout's identity formed on the coordinates of $[{\bf{p}}]$ . The coordinates of any of the vectors $[{{\bf{b}}_j}]$ , $[j \in \{ {2,\ldots,N} \}]$ , are solutions of what is called an `integer relation' with the coordinates of $[{\bf{p}}]$ (Appendix A). For example, with N = 3, the integer coordinates u,v,w of $[{\bf b}_{1}]$ verify the equation u h+v k+w l = 1; the integer coordinates u,v,w of the vector $[{{\bf{b}}_2}]$ (or $[{{\bf{b}}_3})]$ verify the equation u h+v k+w l = 0, as illustrated in Fig. 1.

Figure 1
Unit cell associated with the plane $[{\bf{p}} = (h,k,l)]$ . The out-of-plane vector $[{\bf{b}}_1]$ points to a node of the layer q = 1, and the in-plane vectors $[{\bf{b}}_2]$ and $[{\bf{b}}_3]$ lie in the layer q = 0. The vector $[{\bf{b}}_1]$ is a solution of the Bézout's identity $[{\bf p}^{\rm t}{\bf b}_{1} = 1]$ , and the vectors $[{\bf{b}}_2]$ and $[{\bf{b}}_3]$ are solutions of the integer relations $[{\bf p}^{\rm t}{\bf b}_{2} = 0]$ and $[{\bf p}^{\rm t} {\bf b}_{3} = 0]$ .

Finding solutions to integer relations is not complicated. For N = 3, if we know a plane $[{\bf{p}} = (h,k,l)]$ with let us say $[k \ne 0]$ , it is not difficult to find two integer vectors $[{{\bf{b}}_2}]$ and $[{{\bf{b}}_3}]$ in this plane, for example, $[{\bf b}_{2} = [-k,h,0]]$ and $[{\bf b}_{3} = [0,-l,k]]$ . The difficult part of the problem is to find vectors with small coordinates by considering all the possible linear combinations of the Miller indices h,k,l. Finding the shortest solutions in dimension N is an NP-hard (non-deterministic polynomial-time) problem well known in computer science and cryptography. An algorithm called PSLQ gives short solutions to integer relations with any vector $[{\bf p}\in {{\bb R}}^{N}]$ (Ferguson et al., 1999 ; see also Wikipedia, 2021a ). It has permitted the discovery of numerous previously unknown identities among real numbers; one of them is the formula that allows the calculation of the nth hexadecimal digit of π without computing the preceding digits (Bailey et al., 1997 ; Raayoni et al., 2021 ). The algorithm presented in the present paper gives only solutions for the vectors $[{\bf p}\in {{\bb Z}}^{N}]$ but, as we will show, the vectors we obtain are shorter than those obtained by PSLQ. Our algorithm actually provides simultaneously a short solution to the N-dimensional Bézout's identity and short solutions to the `integer relations'. It gives the affine space of all the solutions of the N-dimensional Bézout's identity. From a crystallographic point of view, it provides a small unit cell attached to a hyperplane.

Recently, Gorfman (2020 ) proposed a method to find some solutions to an intermediate problem that we will call the `column-constrained unimodular matrix' (CCUM) problem in order to differentiate it from the initial `hyperplane unit-cell problem'. The CCUM problem consists of finding a unimodular matrix M such that the first column is equal to a fixed integer vector t. We recall that a unimodular matrix has integer entries and its determinant is $[ \pm 1]$ . Note that, in Gorfman's paper, it was the last vector (and not the first one) that was imposed, but that does not change the problem. Gorfman's approach involves a series of multiplication with matrices called S containing 0, 1 and −1 in order to reduce the imposed vector t to a unit vector (a vector for which one of its coordinates is 1 and the others are 0). Gorfman showed that the same algorithm applied in the reciprocal space to a vector p gives a solution to the hyperplane unit-cell problem. Let us explain how it works with our notations. For an imposed reciprocal vector p, Gorfman's method permits one to obtain a unimodular matrix $[{{\bf{M}}^*}]$ that has p for the first column vector. Then, the inverse of its transpose $[{\bf{M}} = ({{\bf{M}}^*})^{ - {\rm{t}}}]$ is calculated. Since $[{{\bf{M}}^*}]$ is a unimodular matrix, the matrix $[{\bf{M}}]$ is also unimodular, which implies that its columns are integer vectors. Let us call them $[{\bf b}_{j}]$ . Since $[({{\bf M}}^{*})^{\rm t}{\bf M}]$ is the identity matrix, its first column is a vector that has 1 as the first coordinate and 0 for all the other coordinates. This means that $[{{\bf p}}^{\rm t}{\bf b}_{1} = 1]$ and $[{{\bf p}}^{\rm t}{\bf b}_{j} = 0]$ for $[j \in \{ 2, \ldots, N\}]$ , which proves that the matrix $[{\bf{M}}]$ is a solution of the hyperplane unit-cell problem. Gorfman's idea of using unimodular matrices is very interesting and his approach is innovative and inspiring, but it does not give short solutions. For example, for the plane $[{{\bf{p}}^{\rm{t}}} = (12,20,225)]$ , the solution determined by his algorithm in which the first imposed column vector is $[{\bf{p}}]$ is

$[{{\bf{M}}^*} = \left [{\matrix{ {12} & 2 & 3 \cr {20} & 3 & 5 \cr {225} & 4 & {56} \cr } } \right].]$

The inverse of its transpose is

$[{\bf{M}} = \left [{\matrix{ {148} & 5 & { - 595} \cr { - 100} & { - 3} & {402} \cr 1 & 0 & { - 4} \cr } } \right].]$

The reader can check that the scalar product of (12,20,225) with the first column vector [[148, - 100,1]] is 1, and that the scalar product with the last column vectors [[-595, 402,-4]] and [ [{5, - 3,0} ]] is 0. However, the vector solution of the 3D Bézout identity and the vector solution of the integer relation are large. The vector is even larger than the obvious solution [[0,-4, 45]] . More generally, Gorfman suggests that the algorithm could be `an alternative approach to calculate the Bezout coefficients', but we would like to show that the opposite approach is possible. The aim of the paper is to show that determination of the Bézout's coefficients is an efficient way to find short solutions of both the CCUM problem and hyperplane unit-cell problem. The algorithm proposed in the present paper is based on Euclidean division. An algorithm to determine some short solutions to the N-dimensional Bézout's identity is proposed in Section 2. The algorithm to solve the CCUM problem is detailed in Section 3. Sections 2 and 3 are independent. In Section 4, we explain how to combine the two algorithms to find short solutions to the hyperplane unit-cell problem. Some examples will be given and compared with the PSLQ algorithm. The method has been encoded in a Python 3.8 computer program called GeneralizedBezout. The examples given were obtained on a laptop computer equipped with an Intel Core i7-4600 CPU 2.1 GHz, 64-bit Windows system with a RAM of 8 GB. Note: the Python program GeneralizedBezout is freely available from the author upon request.

2. N-dimensional Bézout's identity

Given a set of integers $[\{{p}_{i},i = 1,\ldots, N\}]$ we look for another set of integers $[\{{u}_{i},i = 1,\ldots, N\}]$ such that $[\sum_{i = 1}^N {p_i}{u_i} = 1]$ . In other words, given an integer vector p of coordinates p_i, we want to get the coordinates u_i of an integer vector $[{\bf{u}}]$ that is such that $[{{\bf p}}^{\rm t}{\bf u} = 1]$ . If N = 2, the fast and well known algorithm based on Euclidean division gives a solution that is also the shortest one (Capparelli, 2020 ; Wikipedia, 2021b ). Surprisingly, we could not find in the literature algorithms in high dimensions N. We propose here two recursive algorithms. They give different solutions that are all valuable, but we will see that the second one gives shorter solutions.

Method-0. We consider p₁ and p₂ the two first coordinates of $[{\bf{p}}]$ , and we call (u, v) their Bézout numbers, i.e. $[{up}_{1}+{vp}_{2} = {\rm gcd}\ ({p}_{1}, {p}_{2})]$ . If we note $[\{{k}_{i},i = 2,\ldots, N\}]$ the Bézout numbers in dimension [N - 1] associated with the set $[\{{{\rm gcd}\ ({p}_{1}, {p}_{2}),p}_{3},\ldots, {p}_{N}\}]$ , a solution of the N-dimensional Bézout's identity is thus $[\{{{uk}_{2},{vk}_{2}, k}_{3},\ldots, {k}_{N}\}]$ . This method is easy to compute by recursion until the dimension decreases to N = 2 for which the solution is given by the classical Bézout's algorithm. The problem related to this method is that the absolute values of the Bézout numbers u_i can be quite high. One could screen all the pairs (p_i, p_j) in place of (p₁, p₂) to determine the lowest Bézout numbers but this method would be unrealistic for high dimensions N. We could find another method for which the values are lower than those determined by method-0.

Method-1. We consider the set of integers $[\{{p}_{i},i = 1,2,\ldots, N\}]$ . If $[\exists i, |{p}_{i}| = 1]$ , the solution of the Bézout identity is immediately $[\{ {0, \ldots 0,{p_i},0\ldots,0} \}]$ . If none of the p_i's has 1 as absolute value, the set { p_i } is sorted in decreasing order of the absolute values of p_i. The sorting permutation σ is kept in memory. The smaller non-null value is called p_i₀. We calculate the quotient set and the residue set { q_i,i = $[1, 2,\ldots, {i}_{0}-1]$ } and $[\{{r}_{i},i = 1, 2,\ldots, {i}_{0}-1\}]$ with $[{q_i} =\lfloor {p_i} / p_{i_0}\rfloor]$ and $[{r_i} = {p_i} - {q_i}{p_{{i_0}}}]$ , quotient and remainder of the Euclidean division by p_i₀. If we note $[\{ {u_1},{u_2}, \ldots, u_{{i_0} - 1},0,\ldots,0 \}]$ the Bézout numbers associated with the set { $[{r}_{1},{r}_{2},\ldots,]$ $[r_{{i}_{0}-1}, 0,\ldots,0]$ }, a solution of the N-dimensional Bézout's identity is $[\{{u}_{1},{u}_{2},\ldots {,u}_{{i}_{0}-1}, -\sum _{i = 1}^{{i}_{0}-1}{q}_{i}{u}_{i},0,\ldots,0\}]$ . This method is easy to compute by recursion until one of the absolute values of the input vector is 1. The correct order of the Bézout numbers associated with the initial set $[\{{p}_{i},i = 1,2,\ldots, N\}]$ is restored by applying $[{\sigma ^{ - 1}}]$ . The pseudocode is given in Fig. 2.

Figure 2
Pseudocode to find Bézout numbers associated with the coordinates of a vector p.

The Bézout numbers calculated with method-1 are smaller than those obtained by method-0. Only method-1 will be considered in the rest of the paper. With the vector $[{\bf{p}}^{\rm{t}} = ({12,20,225} )]$ , it gives $[{\bf{u}} = [- 17, - 1,1]]$ . With the vector $[{\bf p}^{\rm t} = (51, 450, -102, 240, -277, 54, 450, 532)]$ , it gives $[{\bf{u}}]$ = [−3, 0, 0, 0, 0, −3, 0, 1]. The calculation lasts only a few ms. Even if method-1 gives small Bézout vectors u, it may not give systematically the smallest ones. We will see in Section 4 how `hyperplane shearing' can give shorter Bézout vectors u with the help of the CCUM algorithm detailed in Section 3.

3. Algorithm to solve the column-constrained unimodular matrix problem

3.1. Case where one of the coordinates of t is ±1

Now we consider the CCUM problem. There is a simple and immediate solution if the first coordinate of $[{\bf{t}}]$ is 1. In that case, any diagonal or even triangular matrix M with 1 in the diagonal and with t as the first column checks the condition det(M) = 1. If the first coordinate of $[{\bf{t}}]$ is −1, changing one 1 into −1 in the diagonal is sufficient to maintain det(M) = 1. The example used by Gorfman (2020) with the vector $[{\bf{t}}]$ of coordinates [ [- 1,4,2]] enters in this category. A direct solution is

$[{\bf M} = \left[\matrix{-1& 0& 0\cr 4& 1& 0\cr 2& 0& -1}\right].]$

Note that the result is obtained without any calculation. If one of the coordinates of $[{\bf{t}}]$ is 1 in a position i > 1, then a simple matrix of permutation P is sufficient to recalculate the matrix M. We will not give more details here because the solutions are actually included in the more general method based on Bézout's identity explained as follows.

3.2. Case where t has at least one pair of coprime coordinates

In the case N = 2, the general solution to the CCUM problem is given by the classical 2D Bézout's identity. We note

$[{\bf t} = \left[\matrix{{t}_{1}\cr {t}_{2}}\right]]$

the imposed vector. There is a solution if and only if the integers t₁ and t₂ are coprime, and the solution is simply

$[\left[\matrix{{t}_{1}& -v\cr {t}_{2}& u}\right],]$

where u, v are the Bézout numbers associated with t₁ and t₂, i.e. solutions of the equation ut₁ + vt₂ = 1. If t₁ and t₂ are not coprime, the determinant of any matrix M with t in the first column would be a multiple of gcd( t₁, t₂), the greatest common divisor of t₁ and t₂, and thus cannot be equal to $[ \pm 1]$ . The resulting vector

$[\left [{\matrix{ { - v} \cr u \cr } } \right]]$

is the shortest vector. The other vectors are

$[\left [{\matrix{ {-v + k{t_1}} \cr { u + k{t_2}} \cr } } \right]]$

with $[k\in {\bb Z}]$ .

Now, we consider the case where N > 2 and the vector t has its two first coordinates t₁ and t₂ that are coprime numbers. We consider the matrix M made of two blocks, the top left one is

$[\left [{\matrix{ {{t_1}} & { - v} \cr {{t_2}} & u \cr } } \right],]$

where u, v are the Bézout numbers associated with t₁ and t₂, and the bottom right one is the $[({N - 2} ) \times ({N - 2} )]$ identity matrix. Then, the first column of M is replaced by t ( t₁ and t₂ are not changed, and the zeros in M_i,1 are replaced by $[{t}_{i}, i\,\gt\, 2)]$ . The matrix M is the solution of the CCUM problem.

When the two coprime coordinates of vector t, t₁ and t₂, are not the first ones, the permutation matrices $[{\bf{P}}(i,1)]$ and $[{\bf{P}}(j,2)]$ are used to return to the previous case. We recall that a permutation matrix $[{\bf{P}}(i,j)]$ is a N ×N identity matrix, except for the line i for which 1 is written in the column j, and for the column j where 1 is written in the line i. Permutation matrices are unimodular matrices and are equal to their inverse. The unimodular matrix $[{\bf P}]$ = $[{\bf P}(i,1){\bf P}(j,2)]$ is such that the vector $[{\bf{P}}\cdot{\bf{t}}]$ has for first coordinates the coprime numbers t₁ and t₂. We thus return to the previous case. If we call M the two-block solution of that case, the solution of the problem is given by the matrix $[{{\bf P}}^{-1}{\bf M}]$ . Note that $[{{\bf P}}^{-1} = {\bf P}(j,2){\bf P}(i,1)\ne {\bf P}]$ .

With $[{\bf{t}}]$ of coordinates [12,20,225], the algorithm gives

$[{\bf{M}} = \left [{\matrix{ {12} & 1 & 0 \cr {20} & 2 & 1 \cr {225} & 0 & { - 56} \cr } } \right].]$

The algorithm works very efficiently, even in high dimensions and with large coordinates. For example, with $[{\bf{t}}]$ of coordinates [1551, −540, 67, −102, 2140, −277, 32, 366, 450, 1532], the algorithm gives immediately (less than 1 ms) a solution:

$[{\bf M} = \left[\matrix{1551& 0& 0& 0& 0& 0& 0& 0& 0& -463\cr -540& 0& 1& 0& 0& 0& 0& 0& 0& 0\cr 67& 0& 0& 0& 0& 0& 0& 0& 0& -20\cr -102& 0& 0& 0& 1& 0& 0& 0& 0& 0\cr 2140& 0& 0& 0& 0& 1& 0& 0& 0& 0\cr -277& 0& 0& 0& 0& 0& 1& 0& 0& 0\cr 32& 0& 0& 0& 0& 0& 0& 1& 0& 0\cr 366& 0& 0& 0& 0& 0& 0& 0& 1& 0\cr 450& -1& 0& 0& 0& 0& 0& 0& 0& 0\cr 1532& 0& 0& 1& 0& 0& 0& 0& 0& 0}\right].]$

3.3. Case where none of the pairs of coordinates of t are coprime

Now, let us consider the rarer cases in which none of the pairs (t_i,t_j) of coordinates of $[{\bf{t}}]$ are coprime despite the fact that the set of coordinates of t are coprime (as mentioned previously, if they are not, there is no solution to the problem). The set of integers $[\{{t}_{i},i = 1,\ldots, N\}]$ is said to be `coprime but not pairwise coprime'. A classical example is {6, 10, 15}. Let us recall that in large dimensions N, the probability that a set of integers { t_i } is coprime but not pairwise coprime is very small because the probability that two randomly chosen integers are coprime is quite high: it is equal to $[1 / [\zeta (2)] = 6 / {\pi ^2} \simeq 61\%]$ , where $[\zeta]$ refers to the Riemann zeta function (Wikipedia, 2021c ). The exact calculation of the probability for a set of N integers { t_i } to be coprime but not pairwise coprime as a function of N is not straightforward and is beyond the scope of the present study. Even if rare, these cases can be solved as follows. We consider the two first coordinates t₁ and t₂ of the vector $[{\bf{t}}]$ (any pair of coordinates would also work). As t₁ and t₂ are not coprime, they can be written t₁ = xy and t₂ = yz, where x, y, z are three integers and $[y = {\rm gcd}\ ({{t_1},{t_2}} ) \,\gt\, 1]$ . It is important to note here that there is at least another coordinate t_i with $[i \,\gt\, 2]$ that cannot be divided by y because if it were not so the set { t_i } would not be coprime. We call (u, v) the Bézout numbers associated with (t₁,t₂ ), ut₁+ vt₂ = y. The pair (u, v) are also the Bézout numbers associated with (x,z ), ux+ vz = 1, i.e. (u, v) are also coprime. We call $[(\alpha, \beta )]$ the Bézout numbers associated with (u, v). We consider the matrix

$[\left [{\matrix{ u & v \cr { - \beta } & \alpha \cr } } \right],]$

its determinant is 1, and

$[{\bf{B}}\cdot\left [{\matrix{ {xy} \cr {yz} \cr } } \right] = \left [{\matrix{ y \cr {ky} \cr } } \right],]$

with $[k\in {\bb Z}]$ . We build the N ×N matrix $[{\bf{K}}]$ from the 2 ×2 block $[{\bf{B}}]$ and from the $[({N - 2} ) \times ({N - 2} )]$ identity matrix. The first coordinate $[({\bf{K}}\cdot{\bf{t}} )_{(1 )}]$ of the new vector $[{\bf{K}}\cdot{\bf{t}}]$ is coprime with at least one of the coordinates $[({\bf{K}}\cdot{\bf{t}} )_{(i)}]$ with $[ i\,\gt\, 2]$ . It means that the method described in Section 3.2 can be applied to calculate a matrix L such that $[\det ({\bf{L}} ) = 1]$ , and its last column is the vector $[{\bf{K}}\cdot{\bf{t}}]$ . The matrix $[{\bf{M}} = {\bf{K}}^{ - 1}{\bf{L}}]$ is then such that its determinant is also 1 and its last column is $[{\bf{t}}]$ . As the determinant of $[{\bf{K}}]$ is 1, $[{\bf{K}}^{ - 1}]$ is the adjugate (transpose of the cofactor matrix) of K, and is thus an integer matrix. Consequently, $[{\bf{M}}]$ is also an integer matrix, solution of the problem.

The algorithm is effective and fast, whatever the dimension N of the vector $[{\bf{t}}]$ . The pseudocode is shown in Fig. 3.

Figure 3
Pseudocode to find a column-constrained unimodular matrix associated with an integer vector t.

We give an example with the classical set of coprime but not coprime coordinates [6, 10, 15]. The algorithm gives immediately a solution (the vectors are written in columns):

$[{\bf M} = \left[\matrix{6& 1& 0\cr 10& 2& 1\cr 15& 0& -7}\right].]$

Let us build another example with a vector $[{\bf{t}}]$ of coordinates [[-42, 10,15,-30,6] ]. A solution is

$[{\bf M} = \left[\matrix{-42& 0& 4& 0& 1\cr 10& 0& -1& 0& 0\cr 15& 0& 0& 0& -7\cr -30& -1& 0& 0& 0\cr 6& 0& 0& 1& 0}\right].]$

4. Hyperplane unit cell by oblique projection

Let us recall the hyperplane unit-cell problem. We are looking for a set of N vectors $[\{ {\bf{b}}_1, \ldots, {\bf{b}}_j, \ldots, {\bf{b}}_N \}]$ such that the first out-of-plane vector $[{\bf{b}}_1]$ is such that $[{\bf p}^{\rm t}{\bf b}_{1} = 1]$ (pointing to a node of the layer q = 1), and the [N - 1] in-plane vectors $[{\bf{b}}_2, \ldots, {\bf{b}}_j, \ldots, {\bf{b}}_N]$ are such that $[{\bf p}^{\rm t}{\bf b}_{j} = 0]$ (lying in the layer q = 0). The solution $[{\bf{b}}_1]$ of Bezout's identity is placed in the first position to be coherent with the notations we used in a separate paper dedicated to the lattice reduction (Cayron, 2021 ). The method we propose uses a short solution to the N-dimensional Bézout identity (Section 2) and a solution of the CCUM problem (Section 3).

We start from the input vector $[{\bf{p}}]$ . The coordinates of the vector $[{\bf b}_{1}]$ pointing to a node of the layer q = 1 are the solution of the Bézout's identity associated with $[{\bf{p}}]$ . They are obtained by the algorithm detailed in Section 2 (method-1). Now, how to determine the [N - 1] vectors in the layer q = 0? We consider the unimodular matrix M that is such that the first column is the vector $[{\bf b}_{1}]$ . The [N - 1] next column vectors of the matrix M are called $[{\bf{v}}_j]$ for $[j \in \{ 2,\ldots N\}]$ . Each of these vectors belongs to the lattice; thus, they verify $[{\bf p}^{\rm t}{\bf v}_{j} = q_{j}\in {\bb Z}]$ . The vectors $[{\bf b}_{j} = {\bf v}_{j}- q_{j}{\bf b}_{1}]$ verify $[{\bf p}^{\rm t}{\bf b}_{j} = 0]$ for $[j \in \{ 2,\ldots N\}]$ ; i.e. they are in-plane vectors lying in the layer q = 0. Geometrically, the vectors $[{\bf b}_{j}]$ are obtained by oblique projection of the vectors $[{\bf v}_{j}]$ along $[{\bf b}_{1}]$ onto the plane $[{\bf{p}}]$ , as illustrated for N = 3 in Fig. 4.

Figure 4
Projections of the vectors $[{\bf{v}}_2,{\bf{v}}_3]$ along $[{\bf{b}}_1]$ onto the plane $[{\bf{p}} = (h,k,l)]$ . The vector $[{\bf{b}}_1]$ is a short solution of the Bézout's identity $[{\bf p}_{1}^{\rm t}{\bf b}_{1} = 1]$ . The vectors $[{\bf{v}}_2,{\bf{v}}_3]$ are the solutions of the $[{\bf{b}}_1]$ –CCUM problem. The vector $[{\bf b}_{1}]$ is a short vector that can be further shortened into a vector $[{\bf{b}}_1^\prime]$ by `hyperplane shearing' (Cayron, 2021

Now, we have a cell $[{\bf U} = ({\bf b}_{1},\ldots, {\bf b}_{j},\ldots, {\bf b}_{N})]$ attached to the plane $[{\bf{p}}]$ such that $[\det({\bf{U}} ) = 1]$ , $[{\bf p}^{\rm t}{\bf b}_{1} = 1]$ and $[{\bf p}^{\rm t}{\bf b}_{j} = 0]$ for $[i \in \{ 2,\ldots N\}]$ . It is thus the unit cell we were looking for. As the vectors used for the projection are short, the unit cell is not large. It can be reduced even more. There are different methods to find a reduced unit cell $[{\bf{U}}^{\prime} = ({\bf{b}}_1^\prime, \ldots, {\bf{b}}_j^\prime, \ldots, {\bf{b}}_N^\prime )]$ , with $[{\bf{b}}_j^\prime]$ that have the same properties as b_j with the vector $[{\bf{p}}]$ , but with shorter lengths and with angles between them closer to orthogonality. One could apply for example the LLL algorithm well known in computer science (Lenstra et al., 1982 ). We realized however that the algorithm developed in Section 4 can also be used to define the operation of `hyperplane shearing' which consists of shearing the unit cell such that the vector $[{\bf{b}}_1]$ becomes $[{\bf{b}}_1^\prime]$ nearly normal to the plane $[{\bf{p}}]$ as illustrated in Fig. 4, and that this operation can be coupled with other lattice reduction methods to rival LLL implemented in Mathematica. The hyperplane reduction and its application to lattice reduction are detailed in a separate paper (Cayron, 2021). The pseudocode of the set of operations Bézout–CCUM–Projection–Hyperplane reduction is shown in Fig. 5.

Figure 5
Pseudocode of the sequence of operations to determine a short unit cell associated with a hyperplane p. The unit cell is made of N short vectors $[{\bf{U}}^{\prime} = ({\bf{b}}_1^\prime, \ldots, {\bf{b}}_j^\prime, \ldots, {\bf{b}}_N^\prime)]$ , such that $[{\bf p}^{\rm t}{\bf b}^\prime_{1} = 1]$ and $[{\bf p}^{\rm t}{\bf b}^\prime_{j} = 0]$ .

The program written in Python 3.8 called GeneralizedBezout incorporates the lattice reduction operation described by Cayron (2021). Let us give some examples we obtained:

(i) With $[{\bf{p}}^{\rm{t}} = (12,20,225)]$ . The Bézout vector associated with the plane $[{\bf{p}}]$ given by method-1 described in Section 2 is $[{\bf{b}}_1 = [{ - 17, - 1,1} ]]$ . After determining a first unit cell by projections along $[{\bf{b}}_1]$ , and after lattice reduction, this vector becomes $[{\bf{b}}_1^\prime = [{ - 7, - 7,1} ]]$ . The final reduced unit cell is given by the matrix

$[{\bf U}^{\prime} = \left[\matrix{-7& -5& 20\cr -7& 3& 33\cr 1& 0& -4}\right],]$

where the vectors are written in columns. The first vector is the short solution of the 3D Bézout's identity and the other vectors are short solutions of the integer relations with the coordinates of p.

(ii) With $[{\bf p}^{\rm t}]$ = (−54, 131, −48, 632, 23, 177, 333, 99, −581, 377). The coordinates were randomly chosen. The Bézout vector associated with the plane $[{\bf{p}}]$ given by method-1 described in Section 2 is $[{\bf b}_{1} = [1, 0, 0, 0, 11, 0, 0, -2, 0, 0]]$ . After determining a first unit cell by projections parallel to $[{\bf{b}}_1]$ , and after reducing this unit cell, this vector becomes $[{\bf b}_{1}^{\prime} = [0, 1, 1, 0, 1, 0, 0, 1, 1, 1]]$ . The reduced unit cell is

$[{\bf{U}}^\prime = \left [{\matrix{ 0 & { - 1} & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \cr 1 & 0 & 0 & { - 1} & { - 2} & 1 & { - 1} & 0 & 0 & { - 1} \cr 1 & { - 2} & { - 2} & { - 1} & { - 2} & 0 & 1 & 1 & 0 & 1 \cr 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \cr 1 & 0 & 1 & { - 1} & 1 & 2 & 0 & 0 & { - 1} & 1 \cr 0 & { - 2} & 1 & 0 & 0 & { - 1} & 0 & 1 & { - 1} & { - 1} \cr 0 & 0 & 1 & 1 & { - 1} & 0 & 0 & { - 1} & { - 1} & 1 \cr 1 & 0 & { - 2} & 0 & 1 & 0 & { - 2} & 0 & { - 1} & 0 \cr 1 & { - 1} & 0 & { - 1} & 0 & 0 & 0 & { - 1} & 0 & 0 \cr 1 & { - 1} & { - 1} & { - 2} & 1 & 0 & 1 & { - 1} & 0 & 0 \cr } } \right], ]$

where the vectors are written in columns. The first vector is a short solution of the 10D Bézout's identity and the other vectors are short solutions to the integer relations with the coordinates of p. The calculation lasted 20 ms. The PSLQ method implemented in Mathematica under the function FindIntegerNullVector gives only one solution which is [[1, 0,-2, 0, 2, 0, 2, 0, 0,-2]] . We notice that this vector is larger than all the vectors $[{\bf{b}}_j^\prime]$ in columns $[j \in \{ 2,\ldots N\}]$ of the matrix $[{\bf{U}}^\prime]$ .

The matrix $[{\bf{U}}^\prime]$ is interpreted crystallographically/geometrically as the unit cell attached to the hyperplane p. From an algebraic point of view, $[{\bf{U}}^{\prime} = ({\bf{b}}_1^\prime, \ldots, {\bf{b}}_i^\prime, \ldots, {\bf{b}}_N^\prime )]$ can equivalently be understood as the infinite set of solutions of the N-dimensional Bézout's identity, where $[{\bf{b}}_1^\prime]$ is a short solution of the equation $[{\bf p}^{\rm t} {\bf b}_{1}^{\prime} = 1]$ , and the other vectors are short solutions of the integer relation $[{\bf p}^{\rm t} {\bf b}_{j}^{\prime} = 0]$ , $[ j\in \{2,\ldots N\}]$ . The set of solutions of Bézout's identity is thus $[{\bf b}_{1}^{\prime}+\{{\bb Z}.\ {\bf b}_{j}^{\prime}\}]$ with $[j \in \{ 2,\ldots N\}]$ , where { $[{\bb Z}.]$ } means all the linear combinations with integer coefficients. This [N - 1] -dimensional affine space represents all the solutions of Bézout's identity made on the coordinates of p.

5. Conclusion

The problem treated in the present paper called the `hyperplane unit-cell problem' consists of finding, for any hyperplane p of N dimensions, one short vector $[{\bf b}_{1}]$ that is such that $[{\bf p}^{\rm t}{\bf b}_{1} = 1]$ and [N - 1] short integer vectors $[{\bf{b}}_2, \ldots, {\bf{b}}_j, \ldots, {\bf{b}}_N]$ that are such that $[{\bf p}^{\rm t}{\bf b}_{j} = 0]$ . The short out-of-plane vector $[{\bf b}_{1}]$ is the solution of Bezout's identity with p, and the short in-plane vectors $[{\bf b}_{j}]$ , $[j\ge 2]$ , are solutions of the integer relation with p. These vectors constitute a unit cell attached to the hyperplane p. The algorithm to find a short solution to the N-dimensional Bézout's identity is presented in Section 2. The algorithm to find a solution to a connected problem called the column-constrained unimodular matrix (CCUM) is detailed in Section 3. Both algorithms are then combined with the help of an oblique projection to determine a small unit cell attached to any hyperplane p (Section 4). The vectors $[{\bf{b}}_1, \ldots, {\bf{b}}_N]$ are short and can be further shortened by lattice reduction. We have shown in some examples that the solutions of the integer relation are even shorter than those determined by the PSLQ algorithm computed with Mathematica.

APPENDIX A

Notations, Bézout's identity and integer relations

We note u_i the ith coordinate of a vector $[{\bf{u}}]$ . Sometimes, the notation $[{\bf{u}}_{(i)}]$ will be equivalently used. It should not be confused with $[{\bf{u}}_i]$ which is the ith vector in a set of vectors $[\{ {\bf{u}}_i \}]$ . The coordinates of a vector $[{\bf{u}}]$ are written in columns and those of a vector $[{\bf{u}}^{\rm{t}}]$ are in rows. From a crystallographic point of view, column and row vectors belong to direct and reciprocal spaces, respectively. The matrix multiplication notation is adopted. It means that even a `simple' scalar (inner) product $[{\bf p}\cdot {\bf u} = \sum _{ i}{p}_{i}{u}_{i}]$ is written $[{\bf p}^{\rm t}{\bf u}]$ where $[{\bf{p}}^{\rm{t}}]$ means transpose of $[{\bf p}]$ .

Bézout's identity in 2D is an arithmetic theorem that states that for a and b which are integers with d for greatest common divisor, there exist integers u and v such that au + bv = d. More generally, the linear combinations of the form au + bv are exactly the multiples of d. It can be generalized to any dimension N and written as follows. For any integer vector $[{\bf{p}}]$ , calling d the greatest common divisor of the coordinates of $[{\bf{p}}]$ , there exist integer vectors u such that $[{\bf p}^{\rm t}{\bf u} = \sum _{i}{p}_{i}{u}_{i} = d]$ . In the paper, we suppose that the coordinates of p are coprime, i.e. d = 1.

An integer relation between a real vector x exists if and only if there is an integer vector u such that $[{\bf x}^{\rm t}{\bf u} = \sum _{i}{x}_{i}{u}_{i} = 0]$ . There are different algorithms to determine integer relations, such as the PSLQ (Ferguson et al., 1999). Searching for an integer relation between a set of powers of x {1, x, x₂,…, x_n} permits one to determine whether a given real number x is likely to be algebraic. Integer relations are also searched between some mathematical constants such as e, π and ln(2) in order to establish new arithmetic conjectures. In the paper, only the cases where x is an integer vector (called p) are studied. (The equivalences between the mathematical and crystallographic terms used in the paper are given in Table 1.)

Table 1
Equivalence of mathematic/crystallographic terms

Mathematics	Crystallography
Bézout's identity: given an integer vector p, find an integer vector $[{\bf b}_{1}]$ such that that $[ {\bf p}^{\rm t}{\bf b}_{1} = 1]$	Given a plane p, find a lattice vector $[{\bf b}_{1}]$ that points to a node of the first layer of p. The vector $[{\bf b}_{1}]$ represents a translation between the layer q = 0 and q = 1

Integer relation: given an integer vector p, find integer vectors $[{\bf b}_{j}]$ such that that $[ {\bf p}^{\rm t}{\bf b}_{j} = 0]$	Given a plane p, find lattice vectors $[{\bf b}_{j}]$ that lie in the layer q = 0 of the plane p

Set of solutions of Bézout's identity $[{\bf b}_{1}+\{{\bb Z}.\ {\bf b}_{j}\}]$ with $[j \in \{ 2,\ldots N\}]$	The lattice unit cell made of vectors $[{\bf{b}}_1,{\bf{b}}_2, \ldots, {\bf{b}}_N]$

Lattice reduction of the unit cell attached to p: find the vectors $[{\bf{b}}_1^\prime]$ and $[{\bf{b}}_j^\prime]$ as short as possible and such that $[{\bf{p}}^{\rm{t}}{\bf{b}}_1^\prime = 1]$ and $[{\bf{p}}^{\rm{t}}{\bf{b}}_j^\prime = 0]$	Lattice reduction of the unit cell attached to p: find a unit cell such that the vector pointing to the first layer and the in-plane vectors are as short as possible

Acknowledgements

Professor Roland Logé is warmly acknowledged for the freedom given to our research that sometimes goes beyond metallurgy.

References

Bailey, D. H., Borwein, P. B. & Plouffe, S. (1997). Math. C. 66, 903–914. CrossRef Web of Science Google Scholar
Capparelli, S. (2020). Notes on Discrete Math. Bologna, Italy: Società Editrice Esculapio. Google Scholar
Cayron, C. (2021). arXiv:2101.04500. Google Scholar
Ferguson, H. R. P., Bailey, D. H. & Arno, S. (1999). Math. C. 68, 351–370. Web of Science CrossRef Google Scholar
Gorfman, S. (2020). Acta Cryst. A76, 713–718. Web of Science CrossRef IUCr Journals Google Scholar
Lenstra, A. K., Lenstra, H. W. Jr. & Lovász, L. (1982). Math. Ann. 261, 515–534. CrossRef Web of Science Google Scholar
Raayoni, G., Gottlieb, S., Manor, Y., Pisha, G., Harris, Y., Mendlovic, U., Haviv, D., Hadad, Y. & Kaminer, I. (2021). Nature, 590, 67–73. Web of Science CrossRef CAS PubMed Google Scholar
Wikipedia (2021a). https://en.wikipedia.org/wiki/Integer_relation_algorithm, accessed on 15th January 2021. Google Scholar
Wikipedia (2021b). https://w.wiki/znx, accessed on 15th January 2021. Google Scholar
Wikipedia (2021c). https://en.wikipedia.org/wiki/Coprime_integers, accessed on 15th January 2021. Google Scholar

This is an open-access article distributed under the terms of the Creative Commons Attribution (CC-BY) Licence, which permits unrestricted use, distribution, and reproduction in any medium, provided the original authors and source are cited.

FOUNDATIONS
ADVANCES

ISSN: 2053-2733

Volume 77| Part 5| September 2021| Pages 453-459

https://doi.org/10.1107/S2053273321006835

Open

access

Format		BIBTeX
		EndNote
		RefMan
		Refer
		Medline
		CIF
		SGML
		Plain Text
		Text

Format		BIBTeX
		EndNote
		RefMan
		Refer
		Medline
		CIF
		SGML
		Plain Text
		Text

Search IUCr Journals		doi		Advanced search
Author		volume	page

research papers\(\def\hfill{\hskip 5em}\def\hfil{\hskip 3em}\def\eqno#1{\hfil {#1}}\)

A fast algorithm to find reduced hyperplane unit cells and solve N-dimensional Bézout's identities

1. Introduction

2. N-dimensional Bézout's identity

3. Algorithm to solve the column-constrained unimodular matrix problem

3.1. Case where one of the coordinates of t is ±1

3.2. Case where t has at least one pair of coprime coordinates

3.3. Case where none of the pairs of coordinates of t are coprime

4. Hyperplane unit cell by oblique projection

5. Conclusion

APPENDIX A

Notations, Bézout's identity and integer relations

Acknowledgements

References

research papers