EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 16, No. 4, 2023, 2662-2692 ISSN 1307-5543 – ejpam.com Published by New York Business Global Crystal reduced motif via the vectors exchange theorem I: Impact of swapping on two orthogonalization processes and the AE algorithm Seddik Abdelalim1, Ilias Elmouki1,∗ 1 Team of Algebra and Discrete Mathematics, Laboratory of Fundamental and Applied Mathematics (LMFA), Faculty of Sciences Ain Chock (FSAC), University Hassan II of Casablanca (UNIVH2C), Morocco. Abstract. Crystallographic literature is relying more on observational rules for the determination of the motif that could generate the whole representing Bravais lattice of a crystal. Here, we devise an algebraic method that can serve in this regard at least in cases when the associated unit cell is made of quasi-orthogonal vectors. To let our approach be applicable to other reduction problems, we introduce a concept which is about starting first from any ’bad’ crystal cell, not necessarily the primitive elementary cell, in order to find a ’good’ crystal cell and that means seeking a motif made of a basis whose vectors are close-to-orthogonal. The orthogonalization loss could happen any time of vectors swapping which represents a very important process in dealing with lattice reduction, but it has insufficiently been discussed in this subject. Thus, through our present version of vectors exchange theorem, and by using examples of two processes, namely the Gram-Schmidt (GS) procedure and its modified version (MGS), we provide formulations for the new reduced unit cell vectors and analyze the impact of the repeated exchange of vectors on the orthogonalization precision. Finally, we give a detailed explanation to our procedure named as Abdelalim-Elmouki (AE) algorithm. More interestingly, we show that MGS is not only better than GS because of the classical reason related to numerics, but also because its formulation for the new motif vectors in four conditions, has been preserved in three times rather than two for GS, and this may recommend more the introduction of MGS in a harder problem, namely when the crystal dimension is very big. 2020 Mathematics Subject Classifications: 74E15, 06B05, 65Y20, 68R01 Key Words and Phrases: Crystallography, Bravais lattice, Orthogonalization, Lattice reduction 1. Introduction 1.1. Concrete Context of the Problem A point in a crystal lattice could represent an atom, ion, or molecule. If we take the example of halite crystal (NaCl) [9] made of sodium Na and chlorine Cl, we find that ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v16i4.4941 Email addresses: seddikabd@hotmail.com (S. Abdelalim), i.elmouki@gmail.com (I. Elmouki) https://www.ejpam.com 2662 © 2023 EJPAM All rights reserved. S. Abdelalim, I. Elmouki / Eur. J. Pure Appl. Math, 16 (4) (2023), 2662-2692 2663 Na+ and Cl− are repeated together (see this kind of crystal structure with more details in [42] or its representation in short via Figure 1 (a)). In fact, we are working on long range order crystal as we suppose that from anywhere we look at the crystal, the pattern of the points is the same everywhere, forming of what we will call a motif and which is contained in a periodically repeating cell called unit cell. In the technical part of this work thereafter, a basis will refer to this unit cell and whose vectors easily help in gen- erating it. Another example would be about Fluorite crystal CaF2 [39] made of calcium Ca and fluorine F , we find that Ca+2 is repeated every time with two of F− (see this kind of crystal structure in [51] or its representation in short via Figure 1 (b)). We deduce from both examples, the existence of a periodic repetition of a group of atoms with long range order. Another property of these crystals is about the translational symmetry [30], and which means wherever we move the crystal from one repeating unit to another, the crystal remains exactly the same. Let us suppose now, three hypothetical crystals whose repeating cells are formed with just two atoms as in the case of Figure 1 (a) but whose representations are different because of the positioning of their atoms. Figure 1: (a) Representation of NaCl: Na+ shown as bigger discs and Cl− as smaller discs. (b) Representation of CaF2: Ca+2 shown as bigger discs and F− as smaller discs. For instance, if we take the three arrangements (a), (b) and (c) shown in Figure 2, and where we consider the bigger discs as points of what we will call a lattice, we obtain three different forms of lattices. In fact, the lattice is like a crystal, just for instance instead of talking with atoms, we talk about a periodic arrangement of points, then we have crystal = lattice+ basis but with respect to the definition that we have provided before in referring to the motif’s associated unit cell and not exactly any repeating unit cell as in [20, 29] as some researchers do not totally agree with that popular definition. In fact, in order to avoid any conflict, we have seen too that it is better to introduce the basis as defined mathematically rather than considering it as the unit cell itself because one would wonder if the unit cell is a part of the lattice, then crystal = lattice + basis can simply be reduced to crystal = lattice. Using examples of atoms and ions, Maurice Loyal Huggins provided in [25], principles in order to find the arrangement of points in crystals and he concluded that this arrange- ment is repeating itself in short intervals while the motif should contain relatively few points. Here, we deduce that even if we consider the smaller discs, or their points of S. Abdelalim, I. Elmouki / Eur. J. Pure Appl. Math, 16 (4) (2023), 2662-2692 2664 h!] Figure 2: Representation of different crystals where the centers of the bigger discs are considered as the main and only points of the different lattices obtained in the three cases. (a) Result of a lattice with points forming shapes as squares. (b) Result of a lattice with points forming shapes as parallelograms. (c) Result of a lattice with points forming shapes as centered squares. intersection with the bigger ones, we will obtain the same patterns of the lattices (a), (b) and (c) of Figure 2. After this introductory description of the transformation being followed to move from the crystal general structure to the lattice framework as an easiest way to study the prop- erties of the complex crystals, we introduce in the next subsection, some technical issues that are still open in this regard and that has motivated us to suggest a mathematical- based method for Bravais cell reduction instead of the observational rules as we will discuss hereafter. 1.2. Theoretical Context and Motivation 1.2.1. Observational Rules To the best of our knowledge, there is no algebraic procedure that organizes the operations followed for the determination of the unit cell that could generate the whole representing Bravais lattice of a crystal. In fact, this is not feasible simply because of the complex struc- tures of crystals. Victor Goldschmidt considered to be the founder of modern geochemistry and crystal chemistry, reported in his lecture [16] delivered to the Faraday Society in 1929, that there must be a relation between the chemical composition of crystalline substance and the crystal geometrical structure. W.A. Wooster also reported in 1953 in [53] that there is closer relation between magnetic measurements and the arrangement of atoms in a crystal. In 1986, Per Bak asked about the arrangements of atoms in crystals that are characterized by an icosahedral symmetry, but he concluded in [6] that no mathematical model could possibly help in describing the structures of such crystals. In the absence of convincing mathematical methods to deal with this problem, and since S. Abdelalim, I. Elmouki / Eur. J. Pure Appl. Math, 16 (4) (2023), 2662-2692 2665 the determination of a motif is very helpful to researchers who are interested to know more about crystals through their geometrical shapes, crystallographers suggest some ob- servational rules. For instance, Frank Hoffman in [22], saw that in order to find the motif from which we could generate the whole crystal lattice, one could observe, relatively to the special case that we will treat in this paper, that the sought unit cell basis vectors, should satisfy the following conditions, • Be short as much as possible, • Be perpendicular to the symmetry plane, • Be orthogonal. We retake two examples from the above-mentioned reference but with application now to the crystals considered in Figure 1. In the simplest case (a) of Figure 3, namely the one representing the Halite crystal NaCl, we can deduce that the red and black unit cells are equivalent and preferred since they both satisfy the above conditions. As an additional remark, one could consider a cell that is not necessarily made by the Bravais crystal points as described in case (a) of Figure 2, and which concerns the example of the red cell that has only one lattice point in its center. Figure 3: (a) Choice of red and black cells as the generating Halite crystal unit cells. (b) Choice of green cell as the generating Fluorite crystal unit cells. In a more interesting example, if we consider now the other case (b) of Figure 3, namely representing the Fluorite crystal CaF2 and where we start from the red primitive elemen- tary cell [28] and which is a name given to the smallest given cell while its vectors are called primitive translation vectors, then, we will choose the centered green unit cell. As an additional remark, the blue cell are the intermediary cell obtained by the transforma- tion of the red cell and then by another transformation, we obtain the green cell. We will go back to this point in the next section with technical explanation that is more relevant to our work. S. Abdelalim, I. Elmouki / Eur. J. Pure Appl. Math, 16 (4) (2023), 2662-2692 2666 In front of such recommendations, one would also wonder whether there is a mathematical method or not and that could serve in determining that crystal reduced basis. Before going further in our study, let us give more technical information about the story of such open question. 1.2.2. Literature on the Problem and Goal In 1970, Mighell and Karen, were among the first authors who wondered about a method in order to find the crystal reduced cell [45], and they explained in their report in [27], that the first step is to start with the smallest possible cell and that is called a primitive cell, while the problem was remaining to show which one of these many possible cells should be selected. In their opinion, they saw that Niggli [41] described earlier in 1929, what was defined as a unique reduced cell, but unfortunately, no algebraic procedure was devised for calculating it if one starts from any cell of the crystal. Let us retake the example (b) of Figure 3, and let us consider in Figure 4 the primi- tive translation vectors e1 and e2 referring to the primitive elementary red cell, e3 and e4 referring to the blue cell, and finally the obtained e5 and e6 referring to the green unit cell. Figure 4: The sums e1 + e2, e3 + e4 and e5 + e6 serving to make the red, blue and green cells in example (b) of Figure 3. The transformation steps are: e3 = e1, e4 = e1 + e2, e5 = e3 + e4, e6 = e4 − e3. If we look at the primitive translation vectors e1 and e2 in Figure 4, we can see that it helps to make the primitive elementary red cell in example (b) of Figure 3 and which can generate many points of the Bravais lattice, but unfortunately, not all of them. In S. Abdelalim, I. Elmouki / Eur. J. Pure Appl. Math, 16 (4) (2023), 2662-2692 2667 spite of this little detail, it has also helped us to reach the vectors e5 and e6 by simple transformation as we described above. Let us now call the basis (e1, e2) whose vectors are not far-to-orthogonal, a ’good’ basis, however, we not not assume that it is ’good’ enough compared to basis (e5, e6) which is the real ’good’ one and even the ’best’ to make the sought unit cell or motif. Figure 5: Vectors e1 and e2 making a ’bad’ basis from which we start to find a ’good’ one and that can help us to generate the sought motif. Here, in this work, we consider a more difficult problem, subject to a Bravais lattice reduction and that is about starting from any couple of vectors like e1 and e2 of Figure 5 as they are supposed not necessarily making a primitive elementary cell, and let us call (e1, e2) in this case, as a ’bad’ basis, then we wonder how could we start from this basis in order to each a basis like (e5, e6) of Figure 4. The most considered practical algorithm in lattice reduction is the Lenstra-Lenstra-Lovász (LLL) algorithm and that has been introduced in 1982 by A. K. Lenstra, H. Lenstra, Jr., J., and L. Lovász [31]. There have always been problems that interested researchers in the subjects of Diophantine equations as in [2, 13]. The lattice reduction through LLL has shown to be also beneficial in solving such problems as explained in [47] with ex- amples of linear problems, quadratic equations, number fields and testing conjectures, while most authors in this topic have been interested in the complexity analysis of this method in the hope to find a high performance computer program [1, 3, 5, 8, 14, 17– 19, 32, 33, 35, 38, 40, 43, 46, 49, 50]. This algorithm has been applied to many fields such as communication systems [4, 36] as in the study of the multiple-input and multiple- output (MIMO) method [11, 12, 15, 24], while also being used to resolve cryptographic problems as in [21, 23, 26, 34]. Many problems remain open in this subject as for example in the study of the floating-point [48]. Here, we choose to focus on the proof of the vectors swapping and which is a problem that has insufficiently been analyzed in the literature. In fact, as the combination of orthogonalization with the vectors swapping processes, is S. Abdelalim, I. Elmouki / Eur. J. Pure Appl. Math, 16 (4) (2023), 2662-2692 2668 an indispensable part of this algorithm, we will exhibit through our proof of this first suggested version of vectors exchange theorem that by the use of any procedure, there would be a loss of orthogonalization especially due to the repetitive exchange of vectors in the lattice reduction process. As a final result, the second orthogonalization method will show to preserve the orthogonality more than the most used one. Going back to the concrete context of this research and which is about seeking a crystal reduced motif while studying the impact of the vectors exchange, we should note that the literature has not answered about the problem that we have presented in Figure 5. In fact, until nowadays, the interest has been limited to Niggli-like reduction as in [7, 37], in a tentative to find better results than the old work [41]. With respect to the practical side of this work, we aim to recommend a lattice reduction computing procedure which respects the result of the theorem that we will state thereafter and which gives the proof of which or- thogonalization process should be really followed, differently to what is usually considered. After the description of the lattice reduction problem, we need to define the orthogonal- ization processes that will be used in our algorithm. Thus, we start in the next section, by stating some important properties of the Gram-Schmidt method and its modified version through theorem 1 with original statements and proof. 2. Orthogonalization Procedures 2.1. GS and MGS from mathematics In this part of the paper, we consider two ways of orthogonalization [44], namely the Gram-Schmidt process (GS) and its modified version (MGS), then, we prove through a numerical example why one option would be better to consider instead of the other. In fact, the reason behind choosing the MGS is due to the fact that this tries to correct the orthogonalization at every step of its scheme, which means that sometimes, we would lose orthogonality more if we follow just the classical approach during the lattice basis reduction. This study would motivate other researchers working on this particular topic, to look for other forms of orthogonalizing their vectors while searching good bases for their lattices. Let E be a vector space of finite dimension n over the real field, with an inner product ⟨., .⟩ : E × E → R, and we consider in the rest of the paper, that this function induces a norm defined by √ ⟨., .⟩ and denoted by |.|. First, we recall how we generally construct an orthogonal GS basis without necessarily orthonormalizing its new vectors. This is to say that in case of an orthonormalization process, one would simply consider later, the division of those vectors on their norms at each iteration. Let us then start with the definition of B = (e1, ..., en) as a basis of Rn, therefore, the associated GS orthogonal basis B∗ = (e∗1, ..., e ∗ n), is defined as follows e∗1 = e1 e∗2 = e2 − ⟨e2, e∗1⟩ ⟨e∗1, e∗1⟩ e∗1, S. Abdelalim, I. Elmouki / Eur. J. Pure Appl. Math, 16 (4) (2023), 2662-2692 2669 e∗3 = e3 − ⟨e3, e∗1⟩ ⟨e∗1, e∗1⟩ e∗1 − ⟨e3, e∗2⟩ ⟨e∗2, e∗2⟩ e∗2 ... ... e∗n = en − n−1∑ k=1 ⟨en, e∗k⟩ ⟨e∗k, e∗k⟩ e∗k If we are considering orthonormalization of these vectors and which is the most popular step to achieve the straightforwardness of coordinate representation, we simply proceed at each iteration of the orthogonalization process as follows e∗i → e∗i |e∗i | , 1 ≤ i ≤ n Alternatively, following the MGS process, we consider the associated GS orthogonal mod- ified basis B∗∗ = (e∗∗1 , ..., e∗∗n ), defined as follows e∗∗1 = e1 e∗∗2 → e ∗∗(1) 2 = e2 − ⟨e2, e∗∗1 ⟩ ⟨e∗∗1 , e∗∗1 ⟩ e∗∗1 , e ∗∗(1) 3 = e3 − ⟨e3, e∗∗1 ⟩ ⟨e∗∗1 , e∗∗1 ⟩ e∗∗1 e∗∗3 → e ∗∗(2) 3 = e ∗∗(1) 3 − ⟨e∗∗(1)3 , e∗∗2 ⟩ ⟨e∗∗2 , e∗∗2 ⟩ e∗∗2 ... ... e∗∗(k−1) n = en − ⟨en, e∗∗k−1⟩ ⟨e∗∗k−1, e ∗∗ k−1⟩ e∗∗k−1, k = 2, ..., n− 1 e∗∗n → e∗∗(k)n = e∗∗(k−1) n − ⟨e∗∗(k−1) n , e∗∗k ⟩ ⟨e∗∗k , e∗∗k ⟩ e∗∗k , k = 2, ..., n− 1 and if we are considering orthonormalization of these vectors at every iteration, we proceed as follows e∗∗1 → e∗∗1 |e∗∗1 | , e∗∗i → e ∗∗(i−1) i |e∗∗i−1| , 2 ≤ i ≤ n Since we need to use some direct but important properties of such considerations in the proof of theorem 2 hereafter either in the case of GS or MGS, we prove them now in the following theorem and they concern the orthogonality between vectors when they are different and the equality between the linear spans between first input vectors and the orthogonal vectors obtained. S. Abdelalim, I. Elmouki / Eur. J. Pure Appl. Math, 16 (4) (2023), 2662-2692 2670 Theorem 1. Let B = (e1, ..., en) be a basis of Rn, B∗∗ = (e∗∗1 , ..., e∗∗n ) and B∗ = (e∗1, ..., e ∗ n) its associated MGS and GS basis respectively, then, the following properties are verified • ⟨e∗∗(k−1) i , e ∗∗(k) j ⟩ = 0 for 1 ≤ i ≤ k < j ≤ n, 2 ≤ k ≤ n− 1, and ⟨e∗i , e∗j ⟩ = 0 for 1 ≤ i < j ≤ n. • span(e1, ..., en) = span(e∗∗1 , e ∗∗(1) 2 , e ∗∗(2) 3 , ..., e ∗∗(k) n ), 2 ≤ k ≤ n− 1 and span(e1, ..., en) = span(e∗1, ..., e ∗ n) Proof. • – To the best of our knowledge, there is a lack of rigorous proof of the vec- tors orthogonality in MGS case. In fact, as we will see hereafter, a reasoning by induction will help us in the proof of GS case, however, such reasoning can not work for MGS as there is no kind of relation between the products ⟨e∗∗(k)j , e ∗∗(k−1) i ⟩ and ⟨e∗∗(k−1) j , e ∗∗(k−2) i ⟩, 2 ≤ k ≤ n− 1. Then, we will proceed as in the following three sub-cases and general case. Let us show first why the orthogonality property is verified for j = 2, 3, 4. We start with j = 2, i = 1 and k = 1, then we have e ∗∗(1) 2 = e2 − ⟨e2, e∗∗1 ⟩ ⟨e∗∗1 , e∗∗1 ⟩ e∗∗1 , ⟨e∗∗(1)2 , e∗∗1 ⟩ = ⟨e2, e∗∗1 ⟩ − ⟨e2, e∗∗1 ⟩ ⟨e∗∗1 , e∗∗1 ⟩ ⟨e∗∗1 , e∗∗1 ⟩ = 0. Now, we take j = 3, i = 1, 2 and k = 2, we have e ∗∗(2) 3 = e ∗∗(1) 3 − ⟨e∗∗(1)3 , e∗∗2 ⟩ ⟨e∗∗2 , e∗∗2 ⟩ e∗∗2 , then, ⟨e∗∗(2)3 , e ∗∗(1) 2 ⟩ = ⟨e∗∗(1)3 , e ∗∗(1) 2 ⟩ − ⟨e∗∗(1)3 , e ∗∗(1) 2 ⟩ ⟨e∗∗(1)2 , e ∗∗(1) 2 ⟩ ⟨e∗∗(1)2 , e ∗∗(1) 2 ⟩ = 0. We also have, ⟨e∗∗(2)3 , e∗∗1 ⟩ = ⟨e∗∗(1)3 , e∗∗1 ⟩ − ⟨e∗∗(1)3 , e ∗∗(1 2 ⟩ ⟨e∗∗(1)2 , e ∗∗(1) 2 ⟩ ⟨e∗∗(1)2 , e∗∗1 ⟩. Since, we have already showed that ⟨e∗∗(1)2 , e∗∗1 ⟩ = 0, it remains to show that ⟨e∗∗(1)3 , e∗∗1 ⟩ = 0. In fact, we have, ⟨e∗∗(1)3 , e∗∗1 ⟩ = ⟨e∗∗(1)3 , e∗∗1 ⟩ − ⟨e3, e∗∗1 ⟩ ⟨e∗∗1 , e∗∗1 ⟩ ⟨e∗∗1 , e∗∗1 ⟩ = 0. S. Abdelalim, I. Elmouki / Eur. J. Pure Appl. Math, 16 (4) (2023), 2662-2692 2671 An additional last example will be the most interesting as it shows that the few examples above are not enough to deduce a general logic that imply orthogo- nality for these three sub-cases. Thus, we take now j = 4, i = 1, 2, 3 and k = 2, 3, we have e ∗∗(3) 4 = e ∗∗(2) 4 − ⟨e∗∗(2)4 , e∗∗3 ⟩ ⟨e∗∗3 , e∗∗3 ⟩ e∗∗3 , then, ⟨e∗∗(3)4 , e ∗∗(2) 3 ⟩ = ⟨e∗∗(2)4 , e ∗∗(2) 3 ⟩ − ⟨e∗∗(2)4 , e ∗∗(2) 3 ⟩ ⟨e∗∗(2)3 , e ∗∗(2) 3 ⟩ ⟨e∗∗(2)3 , e ∗∗(2) 3 ⟩ = 0. We also have, ⟨e∗∗(3)4 , e ∗∗(1) 2 ⟩ = ⟨e∗∗(2)4 , e ∗∗(1) 2 ⟩ − ⟨e∗∗(2)4 , e ∗∗(1) 2 ⟩ ⟨e∗∗(1)2 , e ∗∗(1) 2 ⟩ ⟨e∗∗(1)2 , e ∗∗(1) 2 ⟩ = 0. In addition, we have, ⟨e∗∗(3)4 , e∗∗1 ⟩ = ⟨e∗∗(2)4 , e∗∗1 ⟩ − ⟨e∗∗(2)4 , e ∗∗(2 3 ⟩ ⟨e∗∗(2)3 , e ∗∗(2) 3 ⟩ ⟨e∗∗(2)3 , e∗∗1 ⟩. Since, we have already shown that ⟨e∗∗(1)3 , e∗∗1 ⟩ = 0, it remains to show that ⟨e∗∗(2)4 , e∗∗1 ⟩ = 0. In fact, we have, ⟨e∗∗(2)4 , e∗∗1 ⟩ = ⟨e∗∗(1)4 , e∗∗1 ⟩ − ⟨e∗∗(1)4 , e∗∗1 ⟩ ⟨e∗∗1 , e∗∗1 ⟩ ⟨e∗∗1 , e∗∗1 ⟩ = 0. To generalize all this, let us consider 1 < i ≤ k < j ≤ n and 1 < k ≤ n − 1, then we have, ⟨e∗∗(k)j , e ∗∗(k−1) i ⟩ = ⟨e∗∗(k−1) j , e ∗∗(k−1) i ⟩ − ⟨e∗∗(k−1) j , e∗∗k ⟩ ⟨e∗∗k , e∗∗k ⟩ ⟨e∗∗k , e ∗∗(k−1) i ⟩ −− If i = k = j − 1, then, ⟨e∗∗k , e ∗∗(k−1) i ⟩ = ⟨e∗∗k , e ∗∗(k−1) k ⟩ = ⟨e∗∗k , e∗∗k ⟩ and also, ⟨e∗∗(k−1) j , e∗∗k ⟩ = ⟨e∗∗(k−1) j , e∗∗i ⟩ = ⟨e∗∗(k−1) j , e ∗∗(k−1) i ⟩. Thus, ⟨e∗∗(k)j , e ∗∗(k−1) i ⟩ = 0. −− If i < k, then, on one hand, ⟨e∗∗k , e ∗∗(k−1) i ⟩ = 0 because we have, ⟨e∗∗(k), e∗∗(k−1) i ⟩ = ⟨e∗∗k , ei⟩ − ⟨ei, e∗∗k−1⟩ ⟨e∗∗k−1, e ∗∗ k−1⟩ ⟨e∗∗k−1, e ∗∗ k ⟩ S. Abdelalim, I. Elmouki / Eur. J. Pure Appl. Math, 16 (4) (2023), 2662-2692 2672 and we can just take i = k − 1 which gives ⟨e∗∗(k), e∗∗(k−1) i ⟩ = 0. On the other hand, ⟨e∗∗(k−1) j , e ∗∗(k−1) i ⟩ = ⟨e∗∗(k−1) j , ei⟩ − ⟨ei, e∗∗k−1⟩ ⟨e∗∗k−1, e ∗∗ k−1⟩ ⟨e∗∗k−1, e ∗∗(k−1) j ⟩ and we can just take i = k − 1 which gives ⟨e∗∗(k−1) j , e ∗∗(k−1) i ⟩ = 0. – If we consider a GS process, this can not be deduced directly from the GS formulations as done for MGS. Thus, we proceed by induction. First for j = 2, i = 1, we have e∗2 = e2 − ⟨e2, e∗1⟩ ⟨e∗1, e∗1⟩ e∗1, ⟨e∗2, e∗1⟩ = ⟨e2, e∗1⟩ − ⟨e2, e∗1⟩ ⟨e∗1, e∗1⟩ ⟨e∗1, e∗1⟩ = 0. Suppose now that ⟨e∗i , e∗j ⟩ = 0 for 1 < i < j ≤ n and we try to prove that ⟨e∗i , e∗j+1⟩ = 0 for 1 < i < j + 1 ≤ n. In fact, we have, ⟨e∗i , e∗j+1⟩ = ⟨e∗i , ej+1⟩ − j∑ k=1 ⟨ej+1, e ∗ k⟩ ⟨e∗k, e∗k⟩ ⟨e∗k, e∗i ⟩ Based on the induction assumption, we have ⟨e∗i , e∗j ⟩ ≠ 0 if i = j and ⟨e∗k, e∗i ⟩ = 0 for 1 < k < i (The case when k = 1, i = 2, already verified above). Thus, ⟨e∗i , e∗j+1⟩ = ⟨e∗i , ej+1⟩ − ⟨ej+1, e ∗ i ⟩ ⟨e∗i , e∗i ⟩ ⟨e∗i , e∗i ⟩ = 0 • – On one hand, we have, e∗∗(k)r = e∗∗(k−1) r − ⟨e∗∗(k−1) r , e∗∗r ⟩ ⟨e∗∗k , e∗∗k ⟩ e∗∗k , k = 2, ..., r − 1 = er − ⟨er, e∗∗k−1⟩ ⟨e∗∗k−1, e ∗∗ k−1⟩ e∗∗k−1 − ⟨e∗∗(k−1) r , e∗∗r ⟩ ⟨e∗∗k , e∗∗k ⟩ e∗∗k , k = 2, ..., r − 1 Thus, er = e∗∗(k)r + ⟨er, e∗∗k−1⟩ ⟨e∗∗k−1, e ∗∗ k−1⟩ e∗∗k−1 + ⟨e∗∗(k−1) r , e∗∗r ⟩ ⟨e∗∗k , e∗∗k ⟩ e∗∗k , k = 2, ..., r − 1 Hence, ei ∈ span(e∗∗1 , e ∗∗(1) 2 , e ∗∗(2) 3 , ..., e ∗∗(k) r ) for all 1 ≤ i ≤ r and with k = 2, ..., r − 1 (because as a remark, we have (e∗∗1 , ..., e∗∗k−1) ⊆ (e∗∗1 , ..., e∗∗k ) implies S. Abdelalim, I. Elmouki / Eur. J. Pure Appl. Math, 16 (4) (2023), 2662-2692 2673 that span(e∗∗1 , ..., e∗∗k−1) ⊆ span(e∗∗1 , ..., e∗∗k )). Then, span(e1, , ..., er) ≤ span(e∗∗1 , e ∗∗(1) 2 , e ∗∗(2) 3 , ..., e ∗∗(k) r ), 1 ≤ i ≤ r, k = 2, ..., r − 1. On the other hand, the result is obviously satisfied when r = 1 since we have e∗∗1 = e1. Suppose now that r ≥ 1, and span(e∗∗1 , e ∗∗(1) 2 , e ∗∗(2) 3 , ..., e ∗∗(k−1) r ) ⊆ span(e1, , ..., er) and let us prove that span(e∗∗1 , e ∗∗(1) 2 , e ∗∗(2) 3 , ..., e ∗∗(k) r ) ⊆ span(e1, , ..., er). (The assumption span(e∗∗1 , e ∗∗(1) 2 , e ∗∗(2) 3 , ..., e ∗∗(k−1) r ) ⊆ span(e1, , ..., er) should be even true as from the formulation, er = e∗∗(k−1) r + ⟨er, e∗∗k−1⟩ ⟨e∗∗k−1, e ∗∗ k−1⟩ e∗∗k−1, k = 2, ..., r − 1 that sum is known to be unique with e ∗∗(k−1) r ∈ span(e1, , ..., er) ⊥ and e∗∗k−1 ⊆ span(e1, , ..., er), 2 ≤ k ≤ r − 1). For 2 ≤ k ≤ r − 1, we have now, e∗∗(k)r = e∗∗(k−1) r − ⟨e∗∗(k−1) r , e∗∗r ⟩ ⟨e∗∗r , e∗∗r ⟩ e∗∗r , k = 2, ..., r − 1 = er − ⟨er, e∗∗k−1⟩ ⟨e∗∗k−1, e ∗∗ k−1⟩ e∗∗k−1 − ⟨e∗∗(k−1) r , e∗∗r ⟩ ⟨e∗∗r , e∗∗r ⟩ e∗∗r , k = 2, ..., r − 1 Thus, e ∗∗(k) r = er + f with f ∈ span(e∗∗1 , e ∗∗(1) 2 , e ∗∗(2) 3 , ..., e ∗∗(k−1) r ). Then, since we have supposed that span(e∗∗1 , e ∗∗(1) 2 , e ∗∗(2) 3 , ..., e ∗∗(k−1) r ) ⊆ span(e1, , ..., er), therefore, e ∗∗(k) r ∈ span(e1, , ..., er), hence, span(e∗∗1 , e ∗∗(1) 2 , e ∗∗(2) 3 , ..., e ∗∗(k) r ) ∈ span(e1, , ..., er). – On one hand, if we suppose that ⟨er, e∗r⟩ ⟨e∗r , e∗r⟩ = 1. Then, e∗r = er − r−1∑ k=1 ⟨er, e∗k⟩ ⟨e∗k, e∗k⟩ e∗k is giving, er = r∑ k=1 ⟨er, e∗k⟩ ⟨e∗k, e∗k⟩ e∗k ∈ span(e∗1, ..., e ∗ r). Thus, span(e1, ..., er) ⊆ span(e∗1, ..., e ∗ r). On the other hand, by induction, we have for k = 1, e1 = e∗1, then span(e1) = span(e∗1). Now, if we suppose that span(e∗1, ..., e ∗ r) ⊆ span(e1, ..., er), then, we have, e∗r+1 = er+1 − r∑ k=1 ⟨er+1, e ∗ k⟩ ⟨e∗k, e∗k⟩ e∗k ∈ span(e1, ..., er+1) S. Abdelalim, I. Elmouki / Eur. J. Pure Appl. Math, 16 (4) (2023), 2662-2692 2674 This is because we have first r∑ k=1 ⟨er+1, e ∗ k⟩ ⟨e∗k, e∗k⟩ e∗k ∈ span(e∗1, ..., e ∗ r), and which is in turn by the induction hypothesis, an element of span(e1, ..., er). Thus, by the formula of e∗r+1, we deduce that span(e ∗ 1, ..., e ∗ r+1) ⊆ span(e1, ..., er+1). We note that the properties just stated above, are very important in the proof of the following theorem. 2.2. The Vectors Exchange theorem The main goal from this part, is to provide a theoretical framework that helps to define the new motif and whose basis vectors could generate the whole representing Bravais lattice of a crystal, all around the case when its associated unit cell is made of quasi-orthogonal vectors. The study also aims to exhibit the change that occurs to the sought Bravais lattice since during the resolution of this problem, we have to exchange our consecutive first and newly input vectors many times. In fact, we will consider hereafter, a new basis denoted as (f1, ..., fn) of the Bravais lattice, and we define it in a way which respects the fact that during the most important part of lattice reduction algorithmic process, we need to exchange some vectors ej and ej+1 and which belong to any given bad basis (e1, ..., en) of the same lattice. The Bravais lattice L is defined as a discrete subgroup of Rn, and we call it as a Bra- vais lattice of order k if there exists a family of linearly independent vectors e1, ..., en in Rn and we have L defined by the set { k∑ i=1 aiei | ai ∈ Z } . The importance of this theoretical part, can not be denied as the vectors swapping play a major role in the algorithmic process of many problems, including the problem of re- duction of lattice bases, however, this has been underestimated in the understanding of the process of lattice basis reduction as it has rarely been analyzed in literature. In fact, as far as we know, there were only two researchers who detected this issue and tried to solve it. For the theoretical side of this problem, Murray Bremner in [10], one of the mathematical descendants of Isaac Newton, was the first author who wondered about the impact of vectors swapping on the precision of orthogonalization as a repeated exchange could lead to a loss of orthogonality and which is developed in time of the iteration that comes just before the vectors being swapped, and he even developed a result which meets the case of GS here. As for the numerical side of this problem, Liguo et al. in [52] tried to use the greedy algorithm along with the partial column reduction in order to minimize the number of times of swapping. In this part of work, we provide a clear definition of another basis of L for every con- dition on its range j and that is associated to the index of swapping, namely between a vector ej+1 and ej . As for the result that really exhibits the originality here, it concerns S. Abdelalim, I. Elmouki / Eur. J. Pure Appl. Math, 16 (4) (2023), 2662-2692 2675 first proving that the orthogonality loss would be less considerable in case of MGS, and even showing that this procedure will preserve the formulations of its sought vectors in three times rather than two compared to GS method. In front of the results that we will show hereafter, one would recommend the application of MGS in a harder problem, namely when the dimension of the Bravais crystal, is very big. Now, let us go deeper into the technical part. In fact, since we are aiming to start from any bad basis of the crystal as shown in the more simple particular case of Figure 5, we generalize our problem here for any dimension n and we consider first the given vectors e1, ..., en from L, then, we define the exchange process of the basis generated by these vectors with the help of other vectors f1, ..., fn from L in order to provide in the end, all formulations of the orthogonal vectors of the last generated orthogonal basis in function of the first considered one. In the following, we state the theorem where we define the properties of the new or- thogonal basis after exchanges steps, and as above, we use one star to denoting vectors of the GS orthogonal basis and two stars to denoting vectors of the MGS orthogonal basis. Theorem 2. Let (e1, ..., en) be a basis of a lattice L of order n, and (f1, ..., fn) another basis of L, with fi =  ei if i ̸= j, j + 1 ej+1 if i = j ej if i = j + 1 then, the following properties are verified through GS and MGS orthogonalization processes in the context of repeated exchange of two consecutive input vectors • If 1 ≤ i < j, then f ∗∗(k) i = e ∗∗(k) i , k = 2, ..., n− 1, and, f∗ i = e∗i . • If i = j, then, f ∗∗(k) j = ej+1 − ⟨ej+1, e ∗∗ k−1⟩ ⟨e∗∗k−1, e ∗∗ k−1⟩ e∗∗k−1 − ⟨e∗∗(k−1) j+1 , e∗∗k ⟩ ⟨e∗∗k , e∗∗k ⟩ e∗∗k , k = 2, ..., j − 1, and, f∗ j = e∗j+1 + ⟨ej+1, e ∗ j ⟩ ⟨e∗j , e∗j ⟩ e∗j . • If i = j + 1, then f ∗∗(k) j+1 = e ∗∗(k) j , k = 2, ..., n− 1. and, f∗ j+1 = |e∗j+1|2 |f∗∗ j |2 e∗j − ⟨ej+1, e ∗ j ⟩ ⟨e∗j , e∗j ⟩ |e∗j |2 |f∗∗ j |2 e∗j+1. • If i > j + 1, then f ∗∗(k) i = e ∗∗(k) i , k = 2, ..., i− 1 and, f∗ i = e∗i . At first sight at the formulations obtained, we can see that the theorem proves that MGS can not only considered better than GS as we are used to understand by checking S. Abdelalim, I. Elmouki / Eur. J. Pure Appl. Math, 16 (4) (2023), 2662-2692 2676 numerics, but also because the formulation of f ∗∗(k) i , k = 2, ..., n− 1. has been preserved in three times rather than two in case of GS, and this may recommend the introduction of MGS in a harder problem, namely when the dimension of the crystal is very big. Proof. • By induction, if i < j, already for the first initial case i = 1, we obviously have f1 = e1 = e∗∗1 = f∗∗ 1 . The same if we consider a GS process, we have f1 = e1 = e∗1 = f∗ 1 . If now, we suppose f∗∗ k = e∗∗r with k < r < j, then, we obviously have f∗∗(k−1) r = fr − ⟨fr, f∗∗ k−1⟩ ⟨f∗∗ k−1, f ∗∗ k−1⟩ f∗∗ k−1, k = 2, ..., r − 1 = er − ⟨er, e∗∗k−1⟩ ⟨e∗∗k−1, e ∗∗ k−1⟩ e∗∗k−1, k = 2, ..., r − 1 = e∗∗(k−1) r , k = 2, ..., r − 1 which implies that f∗∗(k) r = f∗∗(k−1) r − ⟨f (k−1) r , f∗∗ k ⟩ ⟨f∗∗ k , f∗∗ k ⟩ f∗∗ k , k = 2, ..., r − 1 = e∗∗(k−1) r − ⟨e(k−1) r , e∗∗k ⟩ ⟨e∗∗k , e∗∗k ⟩ e∗∗k , k = 2, ..., r − 1 = e∗∗(k)r , k = 2, ..., r − 1 In fact, if we consider a GS process and suppose f∗ k = e∗r with k < r < j,, we also have f∗ r = fr − r−1∑ k=1 ⟨fr, f∗ k ⟩ ⟨f∗ k , f ∗ k ⟩ e∗k = er − r−1∑ k=1 ⟨fr, f∗ k ⟩ ⟨f∗ k , f ∗ k ⟩ e∗k = er − r−1∑ k=1 ⟨er, e∗k⟩ ⟨e∗k, e∗k⟩ e∗k = e∗r • Now, if i = j, we have f ∗∗(k−1) j = fj − ⟨fj , f∗∗ k−1⟩ ⟨f∗∗ k−1, f ∗∗ k−1⟩ f∗∗ k−1, k = 2, ..., j − 1 S. Abdelalim, I. Elmouki / Eur. J. Pure Appl. Math, 16 (4) (2023), 2662-2692 2677 = ej+1 − ⟨ej+1, e ∗∗ k−1⟩ ⟨e∗∗k−1, e ∗∗ k−1⟩ e∗∗k−1, k = 2, ..., j − 1 which implies that f ∗∗(k) j = f ∗∗(k−1) j − ⟨f (k−1) j , f∗∗ k ⟩ ⟨f∗∗ k , f∗∗ k ⟩ f∗∗ k , k = 2, ..., j − 1 = ej+1 − ⟨ej+1, e ∗∗ k−1⟩ ⟨e∗∗k−1, e ∗∗ k−1⟩ e∗∗k−1 − ⟨e∗∗(k−1) j+1 , e∗∗k ⟩ ⟨e∗∗k , e∗∗k ⟩ e∗∗k , k = 2, ..., j − 1 As for the GS process, we have f∗ j = fj − j−1∑ k=1 ⟨fj , f∗ k ⟩ ⟨f∗ k , f ∗ k ⟩ f∗ k = ej+1 − j−1∑ k=1 ⟨fj , f∗ k ⟩ ⟨f∗ k , f ∗ k ⟩ f∗ k = ej+1 − j−1∑ k=1 ⟨ej+1, e ∗ k⟩ ⟨e∗k, e∗k⟩ e∗k = ej+1 − j∑ k=1 ⟨ej+1, e ∗ k⟩ ⟨e∗k, e∗k⟩ e∗k + ⟨ej+1, e ∗ j ⟩ ⟨e∗j , e∗j ⟩ e∗j = e∗j+1 + ⟨ej+1, e ∗ j ⟩ ⟨e∗j , e∗j ⟩ e∗j • Now, if i = j + 1, we have f ∗∗(k−1) j+1 = fj+1 − ⟨fj+1, f ∗∗ k−1⟩ ⟨f∗∗ k−1, f ∗∗ k−1⟩ f∗∗ k−1, k = 2, ..., j − 1 = ej − ⟨ej , e∗∗k−1⟩ ⟨e∗∗k−1, e ∗∗ k−1⟩ e∗∗k−1, k = 2, ..., j − 1 = e ∗∗(k−1) j , k = 2, ..., j − 1 which implies that f ∗∗(k) j+1 = f ∗∗(k−1) j+1 − ⟨f (k−1) j+1 , f∗∗ k ⟩ ⟨f∗∗ k , f∗∗ k ⟩ f∗∗ k , k = 2, ..., j − 1 S. Abdelalim, I. Elmouki / Eur. J. Pure Appl. Math, 16 (4) (2023), 2662-2692 2678 = e ∗∗(k−1) j − ⟨e(k−1) j , e∗∗k ⟩ ⟨e∗∗k , e∗∗k ⟩ e∗∗k , k = 2, ..., j − 1 = e ∗∗(k) j , k = 2, ..., j − 1 As for the GS process, we have f∗ j+1 = fj+1 − j∑ k=1 ⟨fj+1, f ∗ k ⟩ ⟨f∗ k , f ∗ k ⟩ f∗ k = ej − j−1∑ k=1 ⟨ej , f∗ k ⟩ ⟨f∗ k , f ∗ k ⟩ f∗ k + ⟨ej , f∗ j ⟩ ⟨f∗ j , f ∗ j ⟩ f∗ j = ej − j−1∑ k=1 ⟨ej , e∗k⟩ ⟨e∗k, e∗k⟩ e∗k + 〈 ej , e ∗ j+1 + ⟨ej+1, e ∗ j ⟩ ⟨e∗j , e∗j ⟩ e∗j 〉 |f∗ j |2 〈 ej , e ∗ j+1 + ⟨ej+1, e ∗ j ⟩ ⟨e∗j , e∗j ⟩ e∗j 〉 N.B. |f∗ j |2 = |e∗j+1|2 + ⟨ej+1, e ∗ j ⟩ ⟨e∗j , e∗j ⟩ 2 |e∗j |2 and then, we have, f∗ j+1 = e∗j − ⟨ej+1, e ∗ j ⟩ ⟨e∗j , e∗j ⟩ ⟨ej , e∗j ⟩ |f∗ j |2 (ej + ⟨ej+1, e ∗ j ⟩ ⟨e∗j , e∗j ⟩ e∗j+1) Since ej = e∗j − j−1∑ k=1 ⟨ek, e∗j ⟩ ⟨e∗j , e∗j ⟩ e∗k. Then, ⟨ej , e∗j ⟩ = ⟨e∗j , e∗j ⟩. Hence, f∗ j+1 = e∗j − ⟨ej+1, e ∗ j ⟩ ⟨e∗j , e∗j ⟩ 2 |e∗j |2 |f∗ j |2 − ⟨ej+1, e ∗ j ⟩ ⟨e∗j , e∗j ⟩ |e∗j |2 |f∗ j |2 e∗j+1 = |f∗ j |2 − ⟨ej+1, e ∗ j ⟩ ⟨e∗j , e∗j ⟩ 2 |e∗j |2 |f∗ j |2 e∗j − ⟨ej+1, e ∗ j ⟩ ⟨e∗j , e∗j ⟩ 2 |e∗j |2 |f∗ j |2 = |e∗j+1|2 |f∗ j |2 e∗j − ⟨ej+1, e ∗ j ⟩ ⟨e∗j , e∗j ⟩ 2 |e∗j |2 |f∗ j |2 • – For i > j + 1, we already know by definition of the basis in this case, that fi = ei. But let us start with this result. Since ei can be decomposed into a unique sum of an element of span(e1, ..., ei−1) ⊥ and an element of span(e1, ..., ei−1), i.e. ei ∈ span(e1, ..., ei−1) ⊥⊕span(e1, ..., ei−1) while knowing that, ei = e ∗∗(k) i + ⟨ei, e∗∗k−1⟩ ⟨e∗∗k−1, e ∗∗ k−1⟩ e∗∗k−1 + ⟨e∗∗(k−1) i , e∗∗i ⟩ ⟨e∗∗k , e∗∗k ⟩ e∗∗k , k = 2, ..., r − 1 S. Abdelalim, I. Elmouki / Eur. J. Pure Appl. Math, 16 (4) (2023), 2662-2692 2679 and at the same time, we also know from theorem 1 that span(e1, ..., ei−1) = span(e∗∗1 , e ∗∗(1) 2 , e ∗∗(2) 3 , ..., e ∗∗(k) i−1 ), 2 ≤ k ≤ n−1, then, the element of span(e∗∗1 , ..., e∗∗i−1) ⊥ is exactly e ∗∗(k) i , therefore, we can say that, ei ∈ span(e∗∗1 , ..., e ∗∗(k−1) i−1 )⊥ ⊕ span(e∗∗1 , ..., e ∗∗(k−1) i−1 ). Similarly, by having, fi = f ∗∗(k) i + ⟨fi, f∗∗ k−1⟩ ⟨f∗∗ k−1, f ∗∗ k−1⟩ f∗∗ k−1 + ⟨f∗∗(k−1) i , f∗∗ i ⟩ ⟨f∗∗ k , f∗∗ k ⟩ e∗∗k , k = 2, ..., r − 1 and which also gives in the end that, fi ∈ span(f∗∗ 1 , ..., f ∗∗(k−1) i−1 )⊥ ⊕ span(f∗∗ 1 , ..., f∗∗ i−1(k − 1)). From another side, we can say that ⟨fi, f∗∗ k−1⟩ ⟨f∗∗ k−1, f ∗∗ k−1⟩ f∗∗ k−1 + ⟨f∗∗(k−1) i , f∗∗ i ⟩ ⟨f∗∗ k , f∗∗ k ⟩ e∗∗k and ⟨ei, e∗∗k−1⟩ ⟨e∗∗k−1, e ∗∗ k−1⟩ e∗∗k−1 + ⟨e∗∗(k−1) i , e∗∗i ⟩ ⟨e∗∗k , e∗∗k ⟩ e∗∗k are in span(f∗∗ 1 , ..., f ∗∗(k−1) i−1 ) and span(e∗∗1 , ..., e ∗∗(k−1) i−1 ) respectively, then again, by theorem 1, it becomes the same as saying they are in span(f1, ..., fi−1) and span(e1, ..., ei−1) respectively and which born in turn can be reduced to span(e1, ..., ei−1) because we have fi = ei. From the formulation of fi and ei, we can now deduce directly that f∗ i and e∗i are both in span(e1, ..., ei−1) ⊥ and that they are even equal. – As for the GS process, and considering the same introductory result in the previous case, we choose now to proceed otherwise by saying that since we have, fi = f∗ i + i−1∑ k=1 ⟨fi, f∗ k ⟩ ⟨f∗ k , f ∗ k ⟩ f∗ i and ei = e∗i + i−1∑ k=1 ⟨ei, e∗k⟩ ⟨e∗k, e∗k⟩ e∗k. Then, the fact that we have fi − ei = 0, it gives us, f∗ i − e∗i = − i−1∑ k=1 ⟨fi, f∗ k ⟩ ⟨f∗ k , f ∗ k ⟩ f∗ i + i−1∑ k=1 ⟨ei, e∗k⟩ ⟨e∗i , e∗k⟩ e∗k. with − i−1∑ k=1 ⟨fi, f∗ k ⟩ ⟨f∗ k , f ∗ k ⟩ f∗ i + i−1∑ k=1 ⟨ei, e∗k⟩ ⟨e∗k, e∗k⟩ e∗k ∈ vect(e1, ..., ei−1), Then, we have, f∗ i − e∗i ∈ vect(e1, ..., ei−1) ⊥, and which finally gives f∗ i = e∗i . As an application of the results stated in theorems 1 and 2, we show in the next section, how the properties just proven above, are incorporated in the following algorithm and that we devise to serving the crystal lattice reduction. S. Abdelalim, I. Elmouki / Eur. J. Pure Appl. Math, 16 (4) (2023), 2662-2692 2680 3. Application for Bravais Cell Reduction 3.1. AE algorithm from Theory In this section, we will explain how we can implement our algorithm using the results of theorem 2. The steps of the algorithm that we will explain in details hereafter are defined by the following points • Initial step and objective, with the three subpoints, – Basis vectors input, – Basis reduction input, with introduction of the modified size reduction as long as the modified Lovász for the MGS case, – Basis vectors output. • Intermediary step, • Vectors exchange theorem step. In fact, the new conditions on the lattice reduction have given us the idea to call our procedure by the name of AE algorithm where AE referring to our names since to the best of our knowledge, it is the first time a theorem-based mathematical algorithm is designed for the crystal reduction with incorporation of the more convincing MGS process, while suggesting the two new conditions on size reduction and quasi-orthogonality. One of the application of vectors swapping, is its introduction in algorithms that are designed for the reduction of lattice bases. We try in this part to convert the logical implementation of vectors swapping treated in the vector exchange theorem as an algo- rithmic process. In general, we define the main goal from reducing a Bravais lattice basis as the process which starts from this input in order to obtain this output Initial Step and Objective • Basis Vectors Input: Choose a random first input basis (e1, ...en) of a Bravais lattice L. • Basis Reduction Input: Choose any real constant by which L basis is determined whether it is reduced or not in the sense of ’quasi-orthogonality’ as in Definition 2 and which could serve as an additional condition to combine with the results of theorem 2. It is also important to note that reduction through orthogonalization alone, is mostly used as an introductory step for reduction in such problems in the sense of ’size’ as in Definition 1 in below, thus, it is very recommended that the computist chooses two constants and condition for i = 2, ..., n, k = 2, ..., i− 1 on the two quantities ∣∣∣∣∣⟨f ∗∗(k−1) i , f∗∗ k ⟩ ⟨f∗∗ k , f∗∗ k ⟩ ∣∣∣∣∣ for the MGS case or the quantity ∣∣∣∣∣ ⟨fi, f∗ j ⟩ ⟨f∗ j , f ∗ j ⟩ ∣∣∣∣∣ when it is about the GS case and by which it is decided whether to go to the First Intermediary Step in below or not. To get a clearer idea about this part, we provide the following definition. S. Abdelalim, I. Elmouki / Eur. J. Pure Appl. Math, 16 (4) (2023), 2662-2692 2681 Definition 1. (The modified condition for size reduction devised for MGS) The Bravais crystal basis (e1, ...en) is reduced in the sense of size if it verifies – MGS case.∣∣∣∣∣⟨f ∗∗(k−1) i , f∗∗ k ⟩ ⟨f∗∗ k , f∗∗ k ⟩ ∣∣∣∣∣ ≤ εMGS, i = 2, ..., n, k = 2, ..., i− 1. – GS case.∣∣∣∣∣ ⟨fi, f∗ j ⟩ ⟨f∗ j , f ∗ j ⟩ ∣∣∣∣∣ ≤ εGS, i = 2, ..., n, j = 1, ..., i− 1, with εMGS , εGS ∈ [1/2, 1[. Definition 2. (The modified condition for quasi-orthogonality devised for MGS) The Bravais crystal basis (e1, ...en) is reduced in the sense of quasi-orthogonality if it verifies – MGS case. (Proposition) ε|e∗∗k |2 ≤ ∣∣∣e∗∗(k−1) j+1 + ⟨e∗∗(k−1) j+1 , e∗∗k ⟩ ⟨e∗∗k , e∗∗k ⟩ e∗∗k ∣∣∣2, k = 2, ..., j, with ε ∈]ε2MGS , 1[. – GS case. ε|e∗j |2 ≤ ∣∣∣e∗j+1 + ⟨ej+1, e ∗ j ⟩ ⟨e∗j , e∗j ⟩ e∗j ∣∣∣2, j = 1, ..., n with ε ∈]ε2GS , 1[ (known as the Lovász condition [31]). Proof. Now, we prove the proposition stated in definition 2 and that is about the modified version of the Lovász condition, namely the quasi-orthogonality condition that we are suggesting in this paper for the MGS case. From the theorem 2, we can see that for i = j, namely at the time of the vectors swapping, we have, f ∗∗(k) j = ej+1 − ⟨ej+1, e ∗∗ k−1⟩ ⟨e∗∗k−1, e ∗∗ k−1⟩ e∗∗k−1 − ⟨e∗∗(k−1) j+1 , e∗∗k ⟩ ⟨e∗∗k , e∗∗k ⟩ e∗∗k , k = 2, ..., j, Thus, by using the definition of MGS formulation at n = j + 1, we get, f ∗∗(k) j = e ∗∗(k−1) j+1 − ⟨e(k−1) j+1 , e∗∗k ⟩ ⟨e∗∗k , e∗∗k ⟩ e∗∗k , k = 2, ..., j. Then, |f∗∗(k) j |2 = |e∗∗(k−1) j+1 |2 + ( ⟨e∗∗(k−1) j+1 , e∗∗k ⟩ ⟨e∗∗k , e∗∗k ⟩ )2 |e∗∗k |2, k = 2, ..., j, and which gives, |e∗∗(k−1) j+1 |2 = |f∗∗(k) j |2 − ( ⟨e∗∗(k−1) j+1 , e∗∗k ⟩ ⟨e∗∗k , e∗∗k ⟩ )2 |e∗∗k |2, k = 2, ..., j. But before this, in order to obtain shorter vector with respect to f ∗∗(k) j , we need S. Abdelalim, I. Elmouki / Eur. J. Pure Appl. Math, 16 (4) (2023), 2662-2692 2682 through its formulation shorter vector e∗∗k , which is the same as saying that by the formulation of |f∗∗(k) j |2, we need the existence of some ε that is close to 1 and such that ε|e∗∗k |2 ≤ |e∗∗(k−1) j+1 |2 + ( ⟨e∗∗(k−1) j+1 , e∗∗k ⟩ ⟨e∗∗k , e∗∗k ⟩ )2 |e∗∗k |2, k = 2, ..., j. Then, going back to the equality on |e∗∗(k−1) j+1 |2, it can be changed now to the in- equality, |e∗∗(k−1) j+1 |2 ≥ ε− ( ⟨e∗∗(k−1) j+1 , e∗∗k ⟩ ⟨e∗∗k , e∗∗k ⟩ )2  |e∗∗k |2, k = 2, ..., j, which is equivalent to the condition stated in Definition 2. Just as remark, if we take ε in ]ε2MGS , 1[, it is better to say that the this condition is verified if ε is close to 1 as in this case, the crystal basis will be more reduced. • Basis Vectors Output: Obtaining an MGS reduced basis (f∗∗ 1 , ...f∗∗ n ) or GS reduced basis (f∗ 1 , ...f ∗ n) associated to some basis (f1, ...fn) and which was defined in the first step or before reduction as fi =  ei if i ̸= j, j + 1 ej+1 if i = j ej if i = j + 1 Once fi is defined, it comes the step where we are in front of the first result of the vectors exchange theorem and which states that in conditions 1 ≤ i < j or i > j + 1, we have the equality between the orthogonal basis of the input random vector and the orthogonal basis of the vector that copied it. Thus, without forgetting the remark given above in the part of Input, we simply go to the computation of its associated orthogonal bases (f∗∗ 1 , ...f∗∗ n ) or (f∗ 1 , ...f ∗ n) using either MGS or GS defined respectively as follows Intermediary Step • MGS case: – If 1 ≤ i < j, then we proceed by the following formulations f∗∗ 1 = f1 f∗∗ 2 → f ∗∗(1) 2 = f2 − ⟨f2, f∗∗ 1 ⟩ ⟨f∗∗ 1 , f∗∗ 1 ⟩ f∗∗ 1 , f ∗∗(1) 3 = f3 − ⟨f3, f∗∗ 1 ⟩ ⟨f∗∗ 1 , f∗∗ 1 ⟩ f∗∗ 1 f∗∗ 3 → f ∗∗(2) 3 = f ∗∗(1) 3 − ⟨f∗∗(1) 3 , f∗∗ 2 ⟩ ⟨f∗∗ 2 , f∗∗ 2 ⟩ f∗∗ 2 ... ... f∗∗(k−1) n = fn − ⟨fn, f∗∗ k−1⟩ ⟨f∗∗ k−1, f ∗∗ k−1⟩ f∗∗ k−1, k = 2, ..., n− 1 S. Abdelalim, I. Elmouki / Eur. J. Pure Appl. Math, 16 (4) (2023), 2662-2692 2683 f∗∗ n → f∗∗(k) n = e∗∗(k−1) n − ⟨f∗∗(k−1) n , f∗∗ k ⟩ ⟨f∗∗ k , f∗∗ k ⟩ f∗∗ k , k = 2, ..., n− 1 – If i > j + 1, then we use from theorem 2, the equality f ∗∗(k) i = e ∗∗(k) i , k = 2, ..., i− 1. • GS case: – If 1 ≤ i < j, we proceed by the following formulations f∗ 1 = f1 f∗ 2 = f2 − ⟨f2, f∗ 1 ⟩ ⟨f∗ 1 , f ∗ 1 ⟩ f∗ 1 , f∗ 3 = f3 − ⟨f3, f∗ 1 ⟩ ⟨f∗ 1 , f ∗ 1 ⟩ f∗ 1 − ⟨e3, e∗2⟩ ⟨f∗ 2 , f ∗ 2 ⟩ f∗ 2 ... ... f∗ n = fn − n−1∑ k=1 ⟨fn, f∗ k ⟩ ⟨f∗ k , f ∗ k ⟩ f∗ k – If i > j + 1, then we use from theorem 2, the equality f∗ i = e∗i . As for the next step and which concerns the vectors swapping and that is presented by using the second, third and fourth results of the vectors exchange theorem, namely when we are either in condition i = j or i = j + 1, then we have the following algorithmic form Vectors Exchange Theorem Step - MGS case: • If i = j, set f ∗∗(k) j = ej+1 − ⟨ej+1, e ∗∗ k−1⟩ ⟨e∗∗k−1, e ∗∗ k−1⟩ e∗∗k−1 − ⟨e(k−1) j+1 , e∗∗k ⟩ ⟨e∗∗k , e∗∗k ⟩ e∗∗k , k = 2, ..., j − 1. • If i = j + 1, set f ∗∗(k) j+1 = e ∗∗(k) j , k = 2, ..., n− 1. - GS case: • If i = j, set f∗ j = e∗j+1 + ⟨ej+1, e ∗ j ⟩ ⟨e∗j , e∗j ⟩ e∗j . • If i = j + 1, set f∗ j+1 = |e∗j+1|2 |f∗∗ j |2 e∗j − ⟨ej+1, e ∗ j ⟩ ⟨e∗j , e∗j ⟩ |e∗j |2 |f∗∗ j |2 e∗j+1. In order to present a concrete application of the algorithm above, we provide a numerical example in the following section. S. Abdelalim, I. Elmouki / Eur. J. Pure Appl. Math, 16 (4) (2023), 2662-2692 2684 3.2. AE algorithm from Numerics In this section, we will we explain how the AE algorithm can be used through a nu- merical example. Mathematically speaking, we have showed in theorem 1 above that GS and MGS pro- cesses are proven to produce orthogonal vectors, however, the main reason behind thinking about these two different ways in order to orthogonalize vectors, is that when it comes to numerical computing, we come in front of a slight difference in the orthogonality results but that may become important for some problems. Thus, to get convinced by the choice of MGS as example, we decide to produce numerical results using our own Python code as we could only find very few examples in literature, explained just through pen or text rather than programs. As an important remark, most numerical experiments and problems in lattice reduction problems, have focused only in providing examples with the assumption that the dimen- sion of the lattice is equal to the dimension of the space, and this does not meet the general definition since it is also allowed to consider its order smaller than the one of the space. The illustrations in Figure 2 where we are moving from third dimensional crystals to second dimensional lattice, is a good example to get this point. Example. Let us suppose that we have a hypothetical fourth dimensional Bravais crystal while the representing lattice is considered to be defined in the third dimension. Thus, we take for example our input vectors defined as follows, e1 = (1, δ, 0, 0), e2 = (1, 0, δ, 0), e3 = (1, 0, 0, δ) with δ = 0.001. Let us take now the new basis fi = ei with 1 ≤ i < j or i > j + 1 and which corre- spond to conditions when there is not yet any vectors swapping. Thus, we are allowed to rewrite our input vectors in this case as f1 = e1, f2 = e2, f3 = e3 Then, if we just consider the non-normalized case for both processes and fix the same number of digits of precision for all calculations of the products to 32, we find the following numerical values of the inner products as follow • MGS process S. Abdelalim, I. Elmouki / Eur. J. Pure Appl. Math, 16 (4) (2023), 2662-2692 2685 f∗∗ 1 = (1, δ, 0, 0) f∗∗ 2 = (9.99999× 10−07,−9.99999× 10−04, δ, 0) = f∗ 2 f∗∗ 3 = (4.9999975× 10−07,−4.9999975× 10−04,−4.9999975× 10−04, δ) ̸= f∗ 3 (even it does not look so at first sight, see proof below) and which gives, ⟨f∗∗ 1 , f∗∗ 2 ⟩ = 0.00000000000000016089962580334832 = ⟨f∗ 1 .f ∗ 2 ⟩ ⟨f∗∗ 1 .f∗∗ 3 ⟩ = 0.00000000000000008044991878079256 = ⟨f∗ 1 .f ∗ 3 ⟩ ⟨f∗∗ 2 .f∗∗ 3 ⟩ = 0.00000000000000000000000000000000 or just 0 with ⟨f∗ 1 .f ∗ 2 ⟩ and ⟨f∗∗ 1 .f∗∗ 3 ⟩ computed as in the following, • GS process f∗ 1 = (1, δ, 0, 0) f∗ 2 = (9.99999× 10−07,−9.99999× 10−04, δ, 0) f∗ 3 = (4.9999975× 10−07,−4.9999975× 10−04,−4.9999975× 10−04, δ) and which gives, ⟨f∗ 1 , f ∗ 2 ⟩ = 0.00000000000000016089962580334832 ⟨f∗ 1 .f ∗ 3 ⟩ = 0.00000000000000008044991878079256 ⟨f∗ 2 .f ∗ 3 ⟩ = 0.00000000000000016089930816599310 Proof. As we noted above, if we look at the values of the components of orthogonal vectors for both processes, one would observe at first sight that f∗∗ 3 = f∗ 3 which is not true because if we are having this, then there would be no need to compute those products. In fact, this is a very important note for readers who want to try both MGS and GS methods, to do for f∗∗ 3 and f∗ 3 the same as we did for getting a precision on the above products, and as we can observe now, that if we fix the number of digits of precision again to 32, we obtain the following real values of f∗∗ 3 and f∗ 3 , f∗∗ 3 = (0.00000049999975008057487955320276, −0.00049999975000012493366735588651, −0.00049999975000012504208757313506, δ) f∗ 3 = (0.00000049999975000012517253064701, S. Abdelalim, I. Elmouki / Eur. J. Pure Appl. Math, 16 (4) (2023), 2662-2692 2686 −0.00049999974991967528932523823215, −0.00049999975008057479484990803797, δ) Thus, f∗∗ 3 ̸= f∗ 3 . Even if we try now the normalized case for both processes, we find that MGS is again better than GS as we have for this case, ⟨f∗∗ 1 , f∗∗ 2 ⟩ = ⟨f∗ 1 .f ∗ 2 ⟩ ⟨f∗∗ 1 .f∗∗ 3 ⟩ = 0.00000000000000000000000000000000 or just 0 ̸= ⟨f∗ 1 .f ∗ 3 ⟩ = 0.00000099999999999999995474811183 ⟨f∗∗ 2 .f∗∗ 3 ⟩ = ⟨f∗ 2 .f ∗ 3 ⟩ We can now deduce from our example and via MGS, in both non-normalized and nor- malized cases, that we can obtain better results about the orthogonalization of our input vectors either for f2 and f3 in the first case, or for f1 and f3 in the second case. Now, we consider the conditions on i when we need to swap the vectors, namely when we take the new basis defined by fi = ej+1 if i = j or fi = ej if i = j + 1. This can simply translated to a different way, by stating that fj = ej+1 and fj+1 = ej and which both correspond to the original case when we generally swap vectors ej+1 and ej . Until now, we have shown how to use MGS and GS in order to implement them in the First Intermediary Step, and why it is preferable to use MGS instead of GS. In order to understand how the vectors exchange process and make the operations clear, let us first suppose again that we just start working and we did not decide to swap any vectors. Then, as explained before, we retake, f1 = (1, δ, 0, 0), f2 = (1, 0, δ, 0), f3 = (1, 0, 0, δ) We have f∗∗ 1 = f1, then we use it to reduce the vector f2. Thus, we get in this step, f1 = f∗∗ 1 , f2 = f ∗∗new1 2 , f3 = f3 For the size reduction, we can see that we have, ⟨f∗∗(1)new1 2 , f∗∗ 1 ⟩ ⟨f∗∗ 1 , f∗∗ 1 ⟩ = 0.00000000000000016089946490388340 which satisfies the condition in Definition 1. As for the quasi-orthogonality condition of Definition 2, we find that for S. Abdelalim, I. Elmouki / Eur. J. Pure Appl. Math, 16 (4) (2023), 2662-2692 2687 ε = 0.75, the condition is not satisfied, then, we have to swap vectors f∗∗ 1 and f ∗∗new1 2 , which means, we have now, f1 = f ∗∗new1 2 , f2 = f∗∗ 1 , f3 = f3 Again, for the size reduction, we can see that we have, ⟨f∗∗(1)new1 2 , f∗∗ 1 ⟩ ⟨f∗∗ 1 , f∗∗ 1 ⟩ = 0.00000000000000029761705115610202 which satisfies the condition in Definition 1. As for the quasi-orthogonality condition of Definition 2, we find that the condition is satisfied. Then, no need to swap any vectors in this step. This means we repeat the process again, and then retake f∗∗ 1 = f ∗∗new1 2 but use these last two first vectors in order to get the new reduced vector f ∗∗new2 2 which we will use now for the reduction of f3. Then, we have, f1 = f ∗∗new1 2 , f2 = f ∗∗new2 2 , f3 = f ∗∗new1 3 Now, for the size reduction, we can see that we have, ⟨f∗∗(1)new2 2 , f ∗∗(1)new1 2 ⟩ ⟨f∗∗(1)new1 2 , f ∗∗(1)new1 2 ⟩ = 0.00000000000000002049319288085836 and ⟨f∗∗(2)new1 3 , f ∗∗(1)new2 2 ⟩ ⟨f∗∗(1)new2 2 , f ∗∗(1)new2 2 ⟩ = 0.00000000000000000000014925455088 which both satisfy the condition in Definition 1. As for the quasi-orthogonality condition of Definition 2, we find that the condition is not satisfied between f ∗∗(2)new1 3 and f ∗∗(1)new2 2 . Then, we should swap these vectors. This means, we will have now, f1 = f ∗∗new1 2 , f2 = f ∗∗new1 3 , f3 = f ∗∗new2 2 In this step, we find that the conditions on both size reduction and quasi-orthogonality are satisfied, then we keep those last vectors. 4. Conclusion In this paper, we have introduced a theoretical concept which is about seeking a ’good’ crystal cell starting from any ’bad’ crystal cell, in order to determine the reduced unit cell whose vectors are close-to-orthogonal, through a major part of Bravais basis reduction, namely the steps of the first version that we have suggested for the vectors exchange REFERENCES 2688 theorem 2. In fact, we studied the special case when we have known beforehand that the motif should be made of quasi-orthogonal vectors. In addition, this work has more interestingly answered about a more general problem often not taking enough place in the literature, and which is about investigating theoretically, the impact of the repeated exchange of vectors, on the precision of two different orthogonalization methods, in times of the reduction process of Bravais basis. Another major point that we have succeeded to prove in this paper, is that MGS was better than GS, not only in numerics as traditionally known, but because of its preservation of the orthogonality formulations in spite of the vectors swapping in three conditions rather than two for GS, and which can lead to MGS to be more recommended in future in more complicated cases, for instance when the dimension is very big. Acknowledgements A special thanks to the editor Professor Dr. Eyup Cetin. We would also like to thank all the three anonymous referees for their time, effort and help for improving the content of our paper. References [1] K. Aardal and F. Eisenbrand. The lll algorithm and integer programming. In The LLL Algorithm: Survey and Applications. p.293-314, Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. [2] S. Abdelalim H. El Adlouni and H. Diany. The diophantine equation x3 + y3 = 2z2. Gulf Journal of Mathematics, 4(4). p.67-73, 2016. [3] A. Akhavi. The optimal lll algorithm is still polynomial in fixed dimension. Theoretical computer science, 297(1-3), p.3-23, 2003. [4] S. Roger A. Gonzalez V. Almenar and A. M. Vidal. Extended lll algorithm for efficient signal precoding in multiuser communication systems. IEEE communications letters, 14(3), p.220-222, 2010. [5] K. Arimoto. On lll lattice basis reduction over imaginary quadratic fields by intro- ducing reduction parameters. Int. J. Math. Comput. Sci., 15(2), p.611-619, 2020. [6] P. Bak. Icosahedral crystals: Where are the atoms? Physical review letters, 56(8), p.861, 1986. [7] L. C. Andrews H. J. Bernstein and N. K. Sauter. Selling reduction versus niggli reduction for crystallographic lattices. Acta Crystallographica Section A: Foundations and Advances, 75(1), p.115-120, 2019. [8] Y. Bilu and G. Hanrot. Solving thue equations of high degree. Journal of number theory, 60(2), p.373-392, 1996. REFERENCES 2689 [9] R. L. Bonewitz. Rocks and Minerals. DK Publishing. ISBN: 978-0-7566-9042-7. p.110, 2012. [10] M. R. Bremner. Lattice basis reduction: an introduction to the LLL algorithm and its applications. CRC Press. ISBN: 1439807027, 9781439807026, p.332, 2011. [11] C. F. Liao L. W. Chai and Y. H. Huang. Loop-reduction lll algorithm and architec- ture for lattice-reduction-aided mimo detection. Journal of Electrical and Computer Engineering, 2012, p.1-7, 2012. [12] D. Chunxiao and Y. Fei. Performance simulation on low-complexity lll-based algo- rithm for mimo system. Telecommunications and Radio Engineering, 77(14), p.1249- 1264, 2018. [13] H. Diany and S. Abdelalim. Characterization of the solution of the diophantine equation x2 + y2 = 2z2. Gulf Journal of Mathematics, 3(2). p.1-4, 2015. [14] M. Haslbeck A. Yamada S. Joosten R. Thiemann J. Divasón and R. Bottesch. A verified lll algorithm. Archive of Formal Proofs, p.1-251, 2018. [15] T. Fujino. Gram-schmidt combined lll lattice-reduction aided detection in mimo systems. REV Journal on Electronics and Communications, 1(2), p.106-114, 2011. [16] V. M. Goldschmidt. Crystal structure and chemical constitution. Transactions of the Faraday Society, 25, p.253-283, 1929. [17] T. Bogart J. Goodrick and K. Woods. A parametric version of lll and some conse- quences: parametric shortest and closest vector problems. SIAM Journal on Discrete Mathematics, 34(4), p.2363-2387, 2020. [18] D. G. Papachristoudis S. T. Halkidis and G. Stephanides. An experimental com- parison of some lll-type lattice basis reduction algorithms. International Journal of Applied and Computational Mathematics, 1(3), p.327-342, 2015. [19] G. Hanrot. Lll: a tool for effective diophantine approximation. In The LLL Algorithm: Survey and Applications. p.215-263, Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. [20] W. A. Harrison. Solid state theory. Courier Corporation. ISBN: 0486639487, 9780486639482. p.554, 1980. [21] M. Van Hoeij. Factoring polynomials and the knapsack problem. Journal of Number theory, 95(2), p.167-189, 2002. [22] F. Hoffmann. Introduction to crystallography. Springer Nature. ISBN: 978-3-030- 35110-6. p.309, 2020. REFERENCES 2690 [23] N. A. Howgrave-Graham and N. P. Smart. Lattice attacks on digital signature schemes. Designs, Codes and Cryptography, 23, p.283-290, 2001. [24] L. Huazhang and L. Jianping. A novel independent processing lll algorithm for mimo detection. Telecommunications and Radio Engineering, 75(7), p.607-620, 2016. [25] M. L. Huggins. Principles determining the arrangement of atoms and ions in crystals. The Journal of Physical Chemistry, 35(5), p.1270-1280, 2002. [26] A. Joux and J. Stern. Lattice reduction: A toolbox for the cryptanalyst. Journal of Cryptology, 11, p.161-185., 1998. [27] A. D. Mighell V. L. Karen and R. Munro. Determination of reduced cells in crystal- lography. A Century of Excellence in Measurements, Standards, and Technology. A Chronicle of Selected NBS/NIST Publications 1901-2000 NIST Special Publication 958. p. 188-190, 2001. [28] S. F. Kettle and L. J. Norrby. Really, your lattices are all primitive, mr. bravais! Journal of chemical education, 70(12), p.959, 1993. [29] C. Kittel. Introduction to solid state physics. American Journal of Physics, 21(8). p.650, 1953. [30] J. W. Lauher. Symmetry and crystal design. Proceedings from the Symposium; Crystals in Supramolecular Chemistry. ACA TRANSACTIONS. VOLUME 39. 4031. p.35, 2004. [31] A. K. Lenstra H. W. Lenstra and L. Lovász. Factoring polynomials with rational coefficients. Math Ann 261, p.515–534, 1982. [32] G. H. Cho H. S. Lee S. Lim and Y. Kim. Storage efficient algorithm for hermite normal form using lll. Linear Algebra and its Applications, 613, p.183-200, 2021. [33] J. Bai N. Liu and Z. Li. New lattice reduction algorithm based on gauss and lll reduction. J. Comput. Eng, 39(11), p.147-149, 2013. [34] A. May. Using lll-reduction for solving rsa and factorization problems. In The LLL Algorithm: Survey and Applications. p.315-348, Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. [35] S. Mehrotra and Z. Li. Segment lll reduction of lattice bases using modular arithmetic. Algorithms, 3(3), p.224-243, 2010. [36] C. Ling W. H. Mow and N. Howgrave-Graham. Reduced and fixed-complexity vari- ants of the lll algorithm for communications. IEEE Transactions on Communications, 61(3), p.1040-1050, 2013. REFERENCES 2691 [37] A. Mujica. Lattice reduction using a euclidean algorithm. Acta Crystallographica Section A: Foundations and Advances, 73(1), p.61-68., 2017. [38] H. Napias. A generalization of the lll-algorithm over euclidean rings or orders. Journal de théorie des nombres de Bordeaux, 8(2), p.387-396, 1996. [39] W. D. Nesse. Introduction to mineralogy. New York: Oxford University Press. ISBN: 9780195106916. p.376-377, 2000. [40] P. Q. Nguyen and D. Stehlé. An lll algorithm with quadratic complexity. SIAM Journal on Computing, 39(3), p.874-903, 2009. [41] P. Niggli. Krystallographische und strukturtheoretische grundbegriffe. Handbuch der Experimentalphysik, Bd VII, 1. Geologiska Föreningen i Stockholm Förhandlingar, 51(1), p.121-122, 1929. [42] K. Panchuk. Physical Geology. First University of Saskatchewan Edition. Chapter 5. p.1-26, 2019. [43] Y. Park and J. PARK. Analysis of the upper bound on the complexity of lll algorithm. Journal of the Korean Society for Industrial and Applied Mathematics, 20(2), p.107- 121, 2016. [44] J. R. Rice. Experiments on gram-schmidt orthogonalization. Mathematics of Com- putation, 20(94), p.325-328, 1966. [45] A. T. Santoro and A. D. Mighell. Determination of reduced cells. Acta Crystallograph- ica Section A: Crystal Physics, Diffraction, Theoretical and General Crystallography, 26(1), p.124-127, 1970. [46] C. P. Schnorr. Fast lll-type lattice reduction. Information and Computation, 204(1), p.1-25, 2006. [47] D. Simon. Selected applications of lll in number theory. In The LLL Algorithm: Survey and Applications. p.265-282, Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. [48] D. Stehlé. Floating-point lll: theoretical and practical aspects. In The LLL Algorithm: Survey and Applications. p.179-213, Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. [49] T. Plantard W. Susilo and Z. Zhang. Lll for ideal lattices: re-evaluation of the security of gentry–halevi’s fhe scheme. Designs, Codes and Cryptography, 76, p.325-344, 2015. [50] B. Vallée and A. Vera. Probabilistic analyses of lattice reduction algorithms. In The LLL Algorithm: Survey and Applications. p.71-143, Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. REFERENCES 2692 [51] M. Vehkamäki. Atomic layer deposition of multicomponent oxide materials. Univer- sity of Helsinki and for the Academic Dissertation at the Faculty of Science. ISBN: 978-952-10-4452-6. p.1-69, 2007. [52] L. U. Liguo L. I. U. Wanke and L. I. Jiangwei. An efficient lll reduction algo- rithm. Geomatics and Information Science At Wuhan University. Vol 41. No. 8. DOI. 10.13203/j.whugis20140484, 2016. [53] W. A. Wooster. Physical properties and atomic arrangements in crystals. Reports on Progress in Physics, 16(1), p.62, 1953.