research papers
A fast algorithm to find reduced hyperplane unit cells and solve Ndimensional Bézout's identities
^{a}Laboratory of Thermo Mechanical Metallurgy (LMTM), PX Group Chair, EPFL, Rue de la Maladière 71b, Neuchâtel, 2000, Switzerland
^{*}Correspondence email: cyril.cayron@epfl.ch
Deformation Ndimensional Bézout's identity associated with the of the hyperplane.
on a plane is a simple shear that transforms a attached to the plane into another equivalent by mirror symmetry or 180° rotation. Thus, crystallographic models of 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 the1. Introduction
How to determine a N, the difficulty of finding a small attached to a hyperplane of dimension becomes even more pronounced. Let us express mathematically this `hyperplane unitcell problem' by the notations detailed in Appendix A. We assume that a hyperplane is known only by its 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 We want to determine a small such that one short integer vector of the cell points to a node of the first layer parallel to the hyperplane, and the other short integer vectors lie in the hyperplane. The `outofplane' vector and the `inplane' vectors are noted and , respectively. The vector is such that , and the vectors are such that . The coordinates of the vector constitute a solution of the Ndimensional Bézout's identity formed on the coordinates of . The coordinates of any of the vectors , , are solutions of what is called an `integer relation' with the coordinates of (Appendix A). For example, with N = 3, the integer coordinates u,v,w of verify the equation u h+v k+w l = 1; the integer coordinates u,v,w of the vector (or verify the equation u h+v k+w l = 0, as illustrated in Fig. 1.
attached to a plane ? This problem occurs for example in the crystallographic models of when the obliquity or the shear values must be calculated for many planes. It is intuitively solved for lowindex planes, but the solutions are more difficult to obtain for highindex planes. In addition, if a can be found, can it be reduced to a smaller one? In dimensionFinding solutions to integer relations is not complicated. For N = 3, if we know a plane with let us say , it is not difficult to find two integer vectors and in this plane, for example, and . The difficult part of the problem is to find vectors with small coordinates by considering all the possible linear combinations of the h,k,l. Finding the shortest solutions in dimension N is an NPhard (nondeterministic polynomialtime) problem well known in computer science and cryptography. An algorithm called PSLQ gives short solutions to integer relations with any vector (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 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 Ndimensional Bézout's identity and short solutions to the `integer relations'. It gives the affine space of all the solutions of the Ndimensional Bézout's identity. From a crystallographic point of view, it provides a small attached to a hyperplane.
Recently, Gorfman (2020) proposed a method to find some solutions to an intermediate problem that we will call the `columnconstrained unimodular matrix' (CCUM) problem in order to differentiate it from the initial `hyperplane unitcell 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 . 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 to a vector p gives a solution to the hyperplane unitcell 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 that has p for the first column vector. Then, the inverse of its transpose is calculated. Since is a unimodular matrix, the matrix is also unimodular, which implies that its columns are integer vectors. Let us call them . Since 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 and for , which proves that the matrix is a solution of the hyperplane unitcell 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 , the solution determined by his algorithm in which the first imposed column vector is is
The inverse of its transpose is
The reader can check that the scalar product of (12,20,225) with the first column vector is 1, and that the scalar product with the last column vectors and 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 . 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 unitcell problem. The algorithm proposed in the present paper is based on Euclidean division. An algorithm to determine some short solutions to the Ndimensional 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 unitcell 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 i74600 CPU 2.1 GHz, 64bit Windows system with a RAM of 8 GB. Note: the Python program GeneralizedBezout is freely available from the author upon request.
2. Ndimensional Bézout's identity
Given a set of integers we look for another set of integers such that . In other words, given an integer vector p of coordinates p_{i}, we want to get the coordinates u_{i} of an integer vector that is such that . 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.
Method0. We consider p_{1} and p_{2} the two first coordinates of , and we call (u, v) their Bézout numbers, i.e. . If we note the Bézout numbers in dimension associated with the set , a solution of the Ndimensional Bézout's identity is thus . 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_{1}, p_{2}) 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 method0.
Method1. We consider the set of integers . If , the solution of the Bézout identity is immediately . 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 nonnull value is called p_{i0}. We calculate the quotient set and the residue set { q_{i},i = } and with and , quotient and remainder of the Euclidean division by p_{i0}. If we note the Bézout numbers associated with the set { }, a solution of the Ndimensional Bézout's identity is . 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 is restored by applying . The pseudocode is given in Fig. 2.
The Bézout numbers calculated with method1 are smaller than those obtained by method0. Only method1 will be considered in the rest of the paper. With the vector , it gives . With the vector , it gives = [−3, 0, 0, 0, 0, −3, 0, 1]. The calculation lasts only a few ms. Even if method1 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 columnconstrained 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 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 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 of coordinates enters in this category. A direct solution is
Note that the result is obtained without any calculation. If one of the coordinates of 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
the imposed vector. There is a solution if and only if the integers t_{1} and t_{2} are coprime, and the solution is simply
where u, v are the Bézout numbers associated with t_{1} and t_{2}, i.e. solutions of the equation ut_{1} + vt_{2} = 1. If t_{1} and t_{2} are not coprime, the determinant of any matrix M with t in the first column would be a multiple of gcd( t_{1}, t_{2}), the greatest common divisor of t_{1} and t_{2}, and thus cannot be equal to . The resulting vector
is the shortest vector. The other vectors are
with .
Now, we consider the case where N > 2 and the vector t has its two first coordinates t_{1} and t_{2} that are coprime numbers. We consider the matrix M made of two blocks, the top left one is
where u, v are the Bézout numbers associated with t_{1} and t_{2}, and the bottom right one is the identity matrix. Then, the first column of M is replaced by t ( t_{1} and t_{2} are not changed, and the zeros in M_{i,1} are replaced by . The matrix M is the solution of the CCUM problem.
When the two coprime coordinates of vector t, t_{1} and t_{2}, are not the first ones, the permutation matrices and are used to return to the previous case. We recall that a permutation matrix 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 = is such that the vector has for first coordinates the coprime numbers t_{1} and t_{2}. We thus return to the previous case. If we call M the twoblock solution of that case, the solution of the problem is given by the matrix . Note that .
With of coordinates [12,20,225], the algorithm gives
The algorithm works very efficiently, even in high dimensions and with large coordinates. For example, with of coordinates [1551, −540, 67, −102, 2140, −277, 32, 366, 450, 1532], the algorithm gives immediately (less than 1 ms) a solution:
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 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 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 , where 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_{1} and t_{2} of the vector (any pair of coordinates would also work). As t_{1} and t_{2} are not coprime, they can be written t_{1} = xy and t_{2} = yz, where x, y, z are three integers and . It is important to note here that there is at least another coordinate t_{i} with 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_{1},t_{2} ), ut_{1}+ vt_{2} = 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 the Bézout numbers associated with (u, v). We consider the matrix
its determinant is 1, and
with . We build the N ×N matrix from the 2 ×2 block and from the identity matrix. The first coordinate of the new vector is coprime with at least one of the coordinates with . It means that the method described in Section 3.2 can be applied to calculate a matrix L such that , and its last column is the vector . The matrix is then such that its determinant is also 1 and its last column is . As the determinant of is 1, is the adjugate (transpose of the cofactor matrix) of K, and is thus an integer matrix. Consequently, is also an integer matrix, solution of the problem.
The algorithm is effective and fast, whatever the dimension N of the vector . The pseudocode is shown in Fig. 3.
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):
Let us build another example with a vector of coordinates ]. A solution is
4. Hyperplane by oblique projection
Let us recall the hyperplane unitcell problem. We are looking for a set of N vectors such that the first outofplane vector is such that (pointing to a node of the layer q = 1), and the inplane vectors are such that (lying in the layer q = 0). The solution 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 Ndimensional Bézout identity (Section 2) and a solution of the CCUM problem (Section 3).
We start from the input vector . The coordinates of the vector pointing to a node of the layer q = 1 are the solution of the Bézout's identity associated with . They are obtained by the algorithm detailed in Section 2 (method1). Now, how to determine the vectors in the layer q = 0? We consider the unimodular matrix M that is such that the first column is the vector . The next column vectors of the matrix M are called for . Each of these vectors belongs to the lattice; thus, they verify . The vectors verify for ; i.e. they are inplane vectors lying in the layer q = 0. Geometrically, the vectors are obtained by oblique projection of the vectors along onto the plane , as illustrated for N = 3 in Fig. 4.
Now, we have a cell attached to the plane such that , and for . It is thus the b_{j} with the vector , 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 such that the vector becomes nearly normal to the plane 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.
we were looking for. As the vectors used for the projection are short, the is not large. It can be reduced even more. There are different methods to find a reduced , with that have the same properties asThe 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 . The Bézout vector associated with the plane given by method1 described in Section 2 is . After determining a first by projections along , and after lattice reduction, this vector becomes . The final reduced is given by the matrix
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 = (−54, 131, −48, 632, 23, 177, 333, 99, −581, 377). The coordinates were randomly chosen. The Bézout vector associated with the plane given by method1 described in Section 2 is . After determining a first by projections parallel to , and after reducing this this vector becomes . The reduced is
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 . We notice that this vector is larger than all the vectors in columns of the matrix .
The matrix is interpreted crystallographically/geometrically as the p. From an algebraic point of view, can equivalently be understood as the infinite set of solutions of the Ndimensional Bézout's identity, where is a short solution of the equation , and the other vectors are short solutions of the integer relation , . The set of solutions of Bézout's identity is thus with , where {} means all the linear combinations with integer coefficients. This dimensional affine space represents all the solutions of Bézout's identity made on the coordinates of p.
attached to the hyperplane5. Conclusion
The problem treated in the present paper called the `hyperplane unitcell problem' consists of finding, for any hyperplane p of N dimensions, one short vector that is such that and short integer vectors that are such that . The short outofplane vector is the solution of Bezout's identity with p, and the short inplane vectors , , are solutions of the integer relation with p. These vectors constitute a attached to the hyperplane p. The algorithm to find a short solution to the Ndimensional Bézout's identity is presented in Section 2. The algorithm to find a solution to a connected problem called the columnconstrained unimodular matrix (CCUM) is detailed in Section 3. Both algorithms are then combined with the help of an oblique projection to determine a small attached to any hyperplane p (Section 4). The vectors 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 . Sometimes, the notation will be equivalently used. It should not be confused with which is the ith vector in a set of vectors . The coordinates of a vector are written in columns and those of a vector 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 is written where means transpose of .
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 , calling d the greatest common divisor of the coordinates of , there exist integer vectors u such that . 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 . 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_{2},…, 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.)

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 openaccess article distributed under the terms of the Creative Commons Attribution (CCBY) Licence, which permits unrestricted use, distribution, and reproduction in any medium, provided the original authors and source are cited.