{'fraction_non_alphanumeric': 0.035063850839491664, 'fraction_numerical': 0.014037908537150985, 'mean_word_length': 4.155746851586163, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Increasing the attraction area of the global minimum in the binary optimization problem

The problem of binary minimization of a quadratic functional in the configuration space is discussed. In order to increase the efficiency of the random-search algorithm it is proposed to change the energy functional by raising to a power the matrix it is based on. We demonstrate that this brings about changes of the energy surface: deep minima displace slightly in the space and become still deeper and their attraction areas grow significantly. Experiments show that this approach results in a considerable displacement of the spectrum of the sought-for minima to the area of greater depth, and the probability of finding the global minimum increases abruptly (by a factor of 10^3 in the case of the 10-by-10 Edwards-Anderson spin glass).


I. INTRODUCTION
Discrete optimization plays a central role in many engineering problems as well as in fundamental science. One major open problem concerns the nature of the energy landscape of optimization problems. It is generally agreed that these energy landscapes are rugged. Finding the ground states of these disordered systems is generally an NP-hard problem so efficient algorithms are particularly called for [1].
The goal of this paper is to make a random-search procedure used in binary-minimization problems more effective. This sort of problem involves minimization of a quadratic functional E 1 (S) built around a particular N ×N matrix T in an N -dimensional configuration space of states S = (s 1 , s 2 , ..., s N ) where the discrete variables are s i = ±1 , i = 1, N .
Minimization in a configuration space is quite different from minimization in a continuous-variable space where it can be solved with the help of conventional methods. Firstly, when we deal with binary variables, the quadratic functional has many extremes even if the matrix T is positive definite, the number of extremes growing exponentially with the dimensionality of the space. Secondly, the problem of binary minimization is NP-complete in the general case, i.e., it does not have a polynomialtime solution algorithm. For this reason heuristic methods are used to solve it. Similarly to the alternatingvariable (gradient) descent method, which can be applied to functional minimization in a continuous space, the asynchronous dynamics of the Hopfield neural net [2,3] is used in a discrete space. This kind of network keeps decreasing the value of the functional until a local minimum is reached. When we use a random-search algorithm, many randomly chosen initial states are tried to start the neural-net dynamics until a deep enough minimum is reached. Because of the large number of local minima, this method does not work efficiently, though it is an acceptable solution.
Despite these difficulties, heuristic methods have found wide use in binary-optimization problems. The successful solution of the traveling salesman problem [3] with the Hopfield neural network introduced neural-net methods in graph theory [4], image processing [5] and other fields [6][7][8][9][10][11][12][13]. The reasons for such a successful application are studied in [14] where the probability of finding a minimum in random search is shown to grow exponentially with the depth of the minimum. In particular, when a neural network is initialized at random, it is very likely to converge to a state corresponding to the global minimum or to a local minimum whose depth is comparable to that of the global minimum [15,16]. The probability that the network converges to a relatively shallow local minimum is exponentially small. All this means that the neural network is most likely to find one of the suboptimal solutions (local minimum) if not the optimal solution (global minimum).
Usually, one tries to make the random-search procedure more efficient by changing the algorithm of the descent down the energy landscape described by functional E 1 (S). A good review of these methods is given in [17][18][19]. In contrast to that approach, we alter the energy landscape itself in order to increase the radius of the attraction area of the global minimum (and other minima that are almost as deep as the global one). Following the theory developed in [20], we have considered the simplest kind of alteration which involves raising the matrix T to the power k (k = 2, 3, ... ). The approach proved quite effective: the change of the surface increases the probability of finding the global minimum by 10 3 − 10 4 times and makes the spectrum of the sought-for minima move far into a deeper-depth region.
We substantiate the efficiency of this algorithm only for the case of matrices whose elements can be considered as random independent variables (matrices of the Edwards-Anderson model, matrices of uniformly or normally distributed elements (Sherrington-Kirkpatrick model), etc.). Application of the algorithm for other types of matrix will be heuristic.
In the following section, we give the general framework in which we work. Section III postulates some necessary theorems concerning the depth and the shape of the local minima. Sections IV and V introduce the double descent algorithm with a matrix to the power k (DDK algorithm) and describe the main features and grounds of the energy landscape transformation. Finally, in Section VI we explain how the algorithm behaves in practice on test problems.

II. STANDARD RANDOM-SEARCH ALGORITHM
The problem of binary minimization can be formulated as follows: there is an N × N matrix T ij , the goal is to find an N -dimensional configuration vector S m = (s where c 1 is just a normalization coefficient introduced to allow us to correctly compare the results for different matrices (see Appendix); σ T is the standard deviation of the elements of T . Without loss of generality, we assume that T ij is a symmetric zero-diagonal matrix (T ij = T ji , T ii = 0, ∀i, j = 1, N ) with zero mean value (T ij = 0). For minimization we use the Hopfield model [2] which is the basis of most of today's algorithms of binary optimization. The model is a system of N spins whose interactions are governed by the energy functional E 1 (S). Only conventional (asynchronous) behavior of the Hopfield model is considered: we compute the local field that acts on an arbitrary spin (i-th spin): If the spin is in an unstable state (h i s i < 0), the spin changes its state in accordance with the decision rule s i = sgn h i . The procedure is applied successively to all spins until the network comes to a stable state S m . We should point out that in the asynchronous behavior the state of only one spin changes at each moment of time. This is in contrast to synchronous behavior where all spins change their states at the same time. The dynamics under consideration (h i ∼ −∂E 1 (S)/∂s i ) is no other than descending the energy surface E 1 (S) which resembles the alternating-variable (gradient) descent in a continuous space. A decrease of energy accompanying each overturn of an unstable spin guarantees that the process described by asynchronous dynamics will bring the system to a stable energy-minimum state after a finite number of steps. Of course, this minimum is very likely to be a local one despite our wish to find the deepest (global) minimum of the functional. That is why we have to turn to random search which involves descents from different random initial configurations repeated until the minimum of a specific depth (probably a global minimum) is reached.
An example of a conventional random-search algorithm is presented in Fig. 1. Below we will denote it as SRS (Standard Random Search) and use it for comparison with the algorithm we offer. Though the SRS algorithm is simple, the descent from a single random configuration requires about O SRS ≈ 2N 2 operations for Sherrington-Kirkpatrick model and O SRS ≈ 8N for Edwards-Anderson model with 4N nonzero matrix elements T ij . Moreover, the number of local minima grows exponentially with N and therefore the probability to find the global minimum falls exponentially. The efficiency of the random-search procedure is usually characterized by three parameters: the probability of finding the global minimum, the search time for a given range of energies, and the average depth of sought-for minima.

III. BASIC RELATIONS
Before coming to the question of surface transformation, let us define the basic relations involving the depth of a global (local) minimum. The first relation deals with the limitation on the depth of a minimum. Let S 0 = (s N ) be a configuration corresponding to global minimum E 0 = E 1 (S 0 ). Let us single out a term T 0 from T . T 0 is responsible for the minimum's appearing. For this purpose let us rewrite T as where The weight r 0 can be found from the condition that there is no correlation between the elements of T 0 and T 1 . By calculating the covariance of these matrix elements and setting it to zero, we find that This expression establishes the relation between r 0 and the depth of the minimum E 0 . The variances of the elements of T 0 and T 1 have the form σ 2 0 = r 2 0 σ 2 T and σ 2 1 = σ 2 T − σ 2 0 , which verifies that we managed to represent a random matrix T as the sum of two independent matrices T 0 and T 1 . In addition, from (3) -(5) it follows that S 0 T 1 S + 0 = 0. This relation evidences that the contribution which T 1 makes to E 0 is strictly zero, that is, the minimum at S 0 is solely the contribution of matrix T 0 .
Let us follow [21] and continue expanding (3). Let the configuration S 1 be an extreme of a quadratic functional built around T 1 . Similarly to (3), let us present T 1 as T 1 = r 1 σ T S + 1 S 1 + T 2 and define the statistical weight r 1 using zero covariance of the elements of S + 1 S 1 and T 2 . Repeating this procedure, we can get the matrix in the form of a series of weighted exterior products of random configuration vectors: All the conclusions drawn in [22] with the aid of statistical physics hold true for this sort of matrix. In particular, we can state that any of vectors S m entering the expansion of T will be a minimum of the functional (1) only when its weight r m is greater than the threshold value where α c ≈ 0.138 is the threshold value of the load parameter [22]. First of all, the statement refers to the point S 0 which is the minimum of the functional (1) by definition and for which the following relations are true The bounding of r 0 above is evident: when r 0 → 1, we have T = T 0 , i.e., T is formed as an exterior product of S 0 and E 1 (S) has a single minimum at point S 0 . This limit is of no interest because the finding of its global minimum presents no difficulty. In most cases the minimization problem faces the situation when r 0 ∼ r c and E 0 ∼ E c and the probability to find the global minimum is very low. It is this situation (r 0 ≪ 1) that we will examine. The second necessary expression relates the depth and width of a minimum. As shown in [14], the width of a minimum E 0 increases with its depth. Correspondingly, the probability to find this minimum grows exponentially as P (E 0 ) ∼ exp −N E 2 c /E 2 0 . Such a rigid connection between the depth of the minimum and the probability of finding it can be easily understood from the following consideration. The probability of finding a global minimum in the course of a random search is no other than the ratio between the number of points located within its attraction area and the total number of points (2 N ) in the N -dimensional space. It is possible to show that the shape of the energy surface around the minimum is described [16] by the expressions whereĒ 0 (n) and σ 0 (n) are the mean value and standard deviation of energy in the n-vicinity of the minimum (at points S (n) 0 located distance n away from S 0 according to Hamming). Expressions (9) are obtained in the limit N → ∞ from the exact expressions given in Appendix. The energy surface (9) is very smooth because the dispersion of energy in the n-vicinity approaches zero with increasing dimensionality (σ ∼ 1/N ). Moreover, differing in depth and width, all minima have the same shape determined by expression (9). As seen from (9) the width of a minimum is proportional to its depth E 0 . This means that the number of points within the attraction area grows exponentially with the depth of the minimum.
All of the above conclusions have to do with the configuration S 0 corresponding to the global minimum. However, they are true for any extremum S m of E 1 (S): 1 ≥ r m ≥ r c and E c ≥ E m ≥ −1 hold for minima, and r c ≤ −r m ≤ 1 and |E c | ≤ E m ≤ 1 hold for maxima.
The result is that we have determined two formulas: a) the deeper the minimum E 0 , the greater the weight r 0 of an addition to configuration S 0 in the initial matrix T and the higher the probability of finding the minimum, b) the point S 0 can be a minimum only if r 0 ≥ r c , that is, if the depth of the minimum |E 0 | is greater than the threshold value |E c |. These formulas set the direction of our efforts to improve the efficiency of the random-search algorithm: the energy surface should be transformed in so way that the global minimum will become deeper and, therefore, the probability to find it will grow. This purpose can be reached by raising T to the power k as it is shown in the next section.

IV. SURFACE TRANSFORMATION
The surface defined by E 1 (S) can be transformed only by changing the corresponding matrix. Let us put M = (1 − z)T + zT k into (1). Here, T k is the matrix resulting from raising T to the power k (k = 2, 3, ...) and zeroing its diagonal elements. Let us pass from T to M = T k by varying a parameter z from 0 to 1. Correspondingly, the surface determined by E 1 (S) transforms into the surface described by E k (S): where σ M is the standard deviation of the elements of M . Transformation of the global minimum is taken as the basis for all our considerations. It is clear that the surface transformation will shift the global minimum in the space and will change its depth and attraction area size. We will show below that when the exponent k is relatively small (2 ≤ k ≤ 5) this transformation will change the minimum depth noticeably. The shift of the minimum is relatively small in case 2 ≤ k ≤ 5.
Correspondingly we offer a two-stage algorithm of minimization. The first stage consists of a descent over the surface E k (S) and finding a configuration S (k) m which brings E k (S) to a minimum. The second stage involves a correction: we descend over the surface E 1 (S) from point S (k) m to the nearest minimum S m of E 1 (S). The method of descending the surface E k (S) is exactly the same as that described above: we compute the local field at the i-th spin: and when h (k) i s i < 0, the spin's state changes in accordance with the decision rule s i = sgn h (k) i . Using this two-stage descent, we realized the randomsearch method whose formal algorithm is given in Fig. 2. Below we will refer to it as DDK (Double Descent algorithm with parameter k = 2, 3, ... ) and compare its efficiency with the conventional random-search algorithm SRS. To avoid misunderstanding, note that when k = 1, the transformed functional E k (S) is identical to the original one E 1 (S), and the DDK method does not differ from the common SRS (DD 1 ≡ SRS).
The number of operations for the DDK algorithm is about twice that of SRS, i.e., O DDK ≈ 2O SRS , but we also should remember that we have to spend some time (about N 3 operation) on matrix exponentiation.

V. THE DDK ALGORITHM VALIDATION
To justify the DDK algorithm, we turn to the case when k = 2. We will show that the surface transformation makes the global minimum significantly deeper, while its position in binary space changes only slightly. A.
The deepening of the minima Let us first make sure that the transformation of the surface results in the minima becoming deeper. Let us It follows from (12) that when N ≫ 1, E 20 can be regarded as a normally distributed quantity with meanĒ 20 and relatively small standard deviation σ E : SinceĒ 20 /E 0 = r 0 √ N ≥ r c √ N ≈ 1.35, the minimum should be expected to become deeper after the surface transformation (E 20 < E 0 ). The probability of that event is given by the expression: where From r 0 ≥ r c it follows that γ ≥ 0.3 √ N . This means that the probability of the minimum's deepening Pr {E 20 < E 0 } approaches unity with increasing N. In other words, the surface transformation is most likely to cause the minimum to deepen considerably (by a factor of 1.35 on average), which, according to [14], leads to the probability of finding the global minimum increasing exponentially with N .
It should be noted thatĒ 20 = − √ N E 2 0 . This allows the conclusion that E 2 (S) reaches its minimum when we deal with both the configuration S 0 which corresponds to the minimum (E 0 < 0) of E 1 (S), and the configuration S * 0 which corresponds to the maximum (E 0 > 0). Experiments confirm this fact.
B. The shift of the minimum Now let us evaluate how far the minimum moves after the surface transformation. The average distance of the shift can be represented as d k = N P , where is the conditional probability of the spin s i and the local field h (k) i having different directions given a configuration of minimum S 0 . For our case of k = 2 we can get from (11) the following expression: where are normally distributed quantities with zero means and standard deviations σ ξi = σ T1 N/2 and σ ξ2i = σ 2 ξi . This allows us to use the error function to express the probability (16). It can be shown that where P 0 = 1 + erf(γ) and γ = √ N r 0 . It is seen that the shift of the minimum d 2 = N P is not large: given √ N r 0 ≥ 1.35, we get that d 2 ≤ 0.026N . It can be shown that in case k = 3, the shift is even smaller.

C. Conclusions and their verification
The following conclusions can be drawn from expressions (12)- (21). The surface transformation is most likely to make minima deeper and, therefore, the probability of finding them higher. Moreover, the greater the original depth |E 0 |, the greater the average increase of the depthĒ 20 /E 0 = √ N |E 0 |. In other words, deep minima become still deeper and the probability to find them becomes yet higher, while shallow minima become more shallow (if not even disappearing) and the probability to discover them become still lower. The above allows us to expect the spectrum of minima found with the given algorithm to move noticeably towards the global minimum, and the probability of finding it to increase considerably. These conclusions have been tested in a few numerical experiments. Fig. 3 shows the observed deepening of the global minima. As we see, global minima become deeper for k = 2, 3, 4 and even for k = 5, but with increasing dispersion. The most average deepening is observed for k = 3.
Since the deepening of minima should lead to an increase in the probability of finding them, the spectrum of the minima of the transformed functional should shift towards greater depths. To confirm this, Fig. 4 shows the spectral densities of the minima of two functional E 1 (S) and E 2 (S) built for N = 100. The density N (E) is defined in the following way: N (E)dE is the number of local minima found in the energy interval [E, E + dE] and normalized to the total number of minima. We see that the spectrum of E 2 (S) is some distance to the left from that of the original functional E 1 (S), and the minimum at point S 0 has become noticeably deeper. The number of found minima of E 2 (S) is roughly half that of E 1 (S). This shows that we have reached our ends: the transformation of the surface arranged that deep minima become yet deeper and are detected more frequently, while shallow ones are found less frequently or not at all.
The shift of the minimum caused by the surface transformation is relatively small. From (21) it follows that the smallest shifts are expected for the deepest minima. For example, in case N = 100, k = 2 the experiment shows that for different matrices the shift of global minima varies from 0 to 6 bits and its average value is d 2 ∼ 3.5 bits, which corresponds well to (21). Figure 5 shows the relation between the shift and transformation parameter k. It is seen that the smallest shift occurs when k = 3. We see that all the theoretical conclusions agree with the experimental results, providing good grounds for the use of the DDK algorithm. In the following sections we will give information on how to apply the algorithm for different types of matrices.

A. Results for Edwards-Anderson matrices
The algorithm was tested using mostly matrices of the 2-dimensional Edwards-Anderson model with N = 10 × 10. This type of matrix was chosen for two reasons.
Firstly, the standard random search procedure for this sort of matrix is not efficient: when N = 100, the probability of finding the global minimum is less than 2 · 10 −6 . Secondly, in the case of Edwards-Anderson matrices it is possible to use the branch and bound method [11] to find the global minimum S 0 , which allows us to control the efficiency of the process.
We will determine the efficiency of the DDK algorithm with the help of three parameters: the probability of finding the global minimum, the difference between the average energy of the local minimaĒ m and the energy E 0 of the global minimum expressed by a dimensionless quantity of discrepancy δE = Ē m − E 0 /E 0 , and the probability of entering the energy interval [E 0 , 0.99E 0 ].
The DDK algorithm efficiency was evaluated for k from 2 to 7. First of all we watched how the spectrum of local minima of E 1 (S) determined by the DDK algorithm changes when the transformation parameter k grows. The processing of the data allowed us to obtain the probability density P (E) where P (E)dE is the probability of finding minima in the energy interval [E, E + dE]. Figure 6 shows the probability density curves determined for a 2D Edwards-Anderson model with N = 100, the energy of the global minimum being taken equal to -1. It is seen that the spectrum of minima moves towards the location of the global minimum. Besides, even the probability of finding the global minimum goes noticeably further from zero.
In addition, we have investigated how the type of the search algorithm affects the distribution of local minima around the global minimum. The distribution is governed by the probability W k = W k (d) which is computed by the DDK algorithm and determines the probability of finding a local minimum at a point distance d away from the global minimum. The magnitudes of W k = W k (d) do not carry useful information. For this reason Fig. 7 gives W k normalized to probability W SRS = W SRS (d) determined by using the SRS algorithm. It is seen that the use of the DDK algorithm increases the probability of finding a local minimum near the global one considerably. In particular, the probability of finding the global minimum (d = 0) grows more than three orders of magnitude when k grows.
The experimental results are given in Table I. The first column holds data for the SRS algorithm. The other columns hold data for the DDK algorithm (for k = 2−5). To evaluate the efficiency of the algorithm, we picked three characteristics: the first row contains the deviation δE = Ē m − E 0 /E 0 ; the second the probability of entering the energy interval [E 0 , 0.99E 0 ] in close vicinity to the global minimum; the third the probability of hitting the global minimum. It is seen that the results for k = 5 little differ from the results for k = 3. When k > 5, the results become worse. That is why a further increase of k does not make much sense: as k grows, the efficiency of the algorithm falls and computations begin to consume too much time.  Unlike sparse Edwards-Anderson matrices, full matrices with evenly (or gaussian) distributed elements allow relatively high chances (about 1% for matrix dimensionality N = 100) to find the global minimum with a conventional neural-net dynamics. However, it was interesting to check how efficiently the method under consideration works with this kind of matrices. Table II shows the results of the surface transformation obtained for Sherrington-Kirkpatrick matrices. We dealt with matrices of dimensionality N = 100. It is seen that the raising-to-a-power trick also increases the minimization efficiency for this sort of matrix. Indeed, if we use the SRS algorithm, the probability of finding the global minimum is just below one percent, while the raising of the matrix to the third power (DD3 algorithm) allows a tenfold increase of this probability.
C. Improvement of the dynamics.

Houdayer-Martin algorithm
It follows from the above that the increased efficiency of the algorithm is caused by a static change -the alteration of the surface being descended. However, it is possible to modify the dynamics of descent. We found in experiments that the descent often stops in shallow pits just a few bits off the global minimum. In order to avoid this unfavorable effect, we changed the algorithm of descent.
We borrowed a local optimization algorithm from [1]. This algorithm was inspired from the Kernighan-Lin [23] algorithm and in [1] it was adapted to our problem of quadratic functional minimization in binary space. This local search algorithm is similar to Hopfield dynamics. However it is more efficient due to its capability of going out of small cavities in the energy landscape.
Here we use this algorithm in the form proposed in [1]. The number of operations that occur during the execution of one start of the Houdayer-Martin dynamics is about O HM ≈ 10O SRS .
The use of this new Houdayer-Martin dynamics of descent instead of Hopfield neural net dynamics improved the efficiency of the DDK algorithm by an order of magnitude. The improved characteristics are shown in Table III (the SRS and DDK algorithms using a modified Houdayer-Martin dynamics are designated as SRS-HM and DDK-HM here). Figure 8 gives the probability density curves P (E) when we use the modified search algorithms DDK-HM and SRS-HM. Comparing them with the curves in Fig. 6, we can see that this modification of the descent dynamics brings about a significant shift of the spectral curves towards the global minimum. It is seen that due to this modification the probability of arriving at a global minimum increased by another order of magnitude. The DD3-HM algorithm gives the best result: the probability to find the global minimum is 2.5 · 10 4 times higher than for the SRS method. For Sherrington-Kirkpatrick matrices the gain of using the DDK-HM algorithm instead of the SRS-HM algorithm becomes evident with increasing dimensionality N .

VII. DISCUSSION
Let us again formulate the DDK algorithm. The preparatory stage involves three steps: 1) the original matrix T is made symmetric (if it is not so initially) and the diagonal elements are set to zero; 2) the matrix is raised to the kth power and the diagonal elements of the resulting matrix M = T k are set to zero; 3) E k (S) is built using M and formula (10). The preparatory stage is followed by the random search procedure which employs m . In both stages we can use any dynamics of descent (i.e., any local optimization procedure), e.g., Hopfield's or Houdayer-Martin's, discussed earlier.
Comparison shows that the surface transformation increases the optimization algorithm efficiency significantly. In particular, for Edwards-Anderson matrices of size N = 196, the use of the DD3-HM method allows the following improvements: the probability of hitting the global minimum increases by order of magnitude in comparison with the SRS-HM algorithm; the difference between the average energyĒ m and the energy of the global minimum decreases by half; and the probability of getting the energy interval around the global minimum E m ∈ [E 0 , 0.99E 0 ] grows by order of magnitude.
The analysis shows that the power k have an optimal value k = 3, because the shift of global minimum is minimal (see Fig. 5) and the deepening is maximal (Fig. 3) at k = 3. Wnen k > 3 the dispersion of deepening increases and algorithm becomes unstable: when experimenting with DD5, we could not detect the global minimum for 60% of matrices. That is why one should keep in mind that though Table I tells us about the higher efficiency of the DD5 algorithm than DD3, these are averaged data and the actual situation may be quite different for a particular kind of matrix.
Adding the Houdayer-Martin algorithm instead of the neural-net dynamics also improves the algorithm considerably. In particular, the DD3-HM algorithm allows hitting the global minimum with an average probability of about 6%, which is 30 times higher than the probability (∼ 0.2%) provided by the DD3 algorithm and 25,000 times greater than the probability (∼ 2.4 · 10 −6 ) permitted by the SRS algorithm. Introduction of a Houdayer-Martin approach increases the time of a single descent tenfold (see Table IV). However, this dynamics adds stability to the algorithm: there were not such matrices for which the DD3-HM algorithm failed to find the global minimum.
The above allows the following conclusion: in all experiments the double-descent algorithm (DDK or DDK-HM) brings the system to a configuration that is very close to the global minimum in energy and distance with a very high probability, all characteristics of the algorithm being much better than those of the SRS algorithm. Besides, the superiority of the DDK (DDK-HM) algorithm over the SRS algorithm only grows with increasing dimensionality N . The examination of the experimental data shows that the DD3-HM algorithm is the best for practical use: it exhibits the highest probability of finding the global minimum, the greatest stability, and the smallest search time.  is located n bits away from S 0 is called the n-vicinity of S 0 . Let us show that as N → ∞ the dispersion of energy in the n-vicinity is negligible and the energy surface around S 0 is determined by the mean value of the energy in the n-vicinity.
The components of a vector S (n) 0 that belongs to the n-vicinity and the components of S 0 are connected by the relation: where a n is a vector such that some N − n of its components equal +1 and the other n components equal −1. Using this notation, the energy at the point S (n) 0 is: where χ ij is the unit antisymmetric tensor. Further, the sum of the energies and the sum of squared energies over the set of all points of the n-vicinity is described by the expressions: i s According to (A.5) the mean value of the energy in the n-vicinity behaves parabolically. At n = 0 the mean energy equals E 0 ; with increasing n the mean energyĒ 0 (n) rises as if the configuration S 0 were surrounded by a funnel with parabolic walls. At n = 1 2 (N − √ N ) the quantitȳ E 0 (n) vanishes and at n = N/2 the parabola reaches its peak. The further trend of the curve is completely symmetric: with increasing n the mean energy goes down parabolically up to energy E 0 at n = N when the configuration turns into mirroring S * 0 = −S 0 . Expressions (A.5)-(A.6) are true for any point of the configuration space. However,Ē 0 (n) describes more precisely the shape of the energy surface around the minimum: it follows from (A.6) that the energy dispersion is minimal when S 0 is the global minimum because σ hs is minimal and E 2 0 is maximal. The energy surface described byĒ 0 (n) is very smooth because its roughness vanishes with increasing N (σ 0 (n) ∼ N −1 ).
It is not hard to calculate σ hs for any point of the space. But when calculating σ hs for a minimum S 0 we should take into account that h i s 3) over all n-vicinities (n = 0, N ), i.e., over the whole space, we have a trivial result: the average value of energy is zero (E 0 (n) = 0) and the average square of energy is determined only by the average square of the matrix elements (E 2 0 (n) = 2c 2 N (N − 1)T 2 ij ), which coincides with the dispersion of matrix elements under the condition of zero mean value T ij . This explains the meaning of the normalization constant c in the energy functional: due to this normalization the energy value is independent of the sort of the matrix; so we can compare results for different matrices of the same type and also different sorts of matrices.