B Mohammed-Azizi
email: aziziyoucef@gmail.com

Derivation of the Strutinsky method from the least squares principle

Keywords: numbers: 02.60.-x, 21.60.-n, 05.45.Mt, 21.10.Ma Mathematical methods in physics, Strutinsky averaging method I

The main purpose of this paper is to rigorously establish the Strutinsky method from the least squares principle. Thus, it is the mathematical basis of this method (aspect often neglected) which is revisited in an extensive way. Some formulas previously given without demonstration or in a simplified way are set out here with all the details. In this respect, the most important mathematical properties of the averaging functions are also established in this paper.

In quantum physics, the density of states g( ) is defined as the number of states per energy unit. These states are deduced from the solution of the time-independent Schrodinger equation. One can distinguish the discrete states in the well and a continuum of scattering states above. For a finite well, there is a finite number of bound states within the well and a continuum above. The level density is then defined as:

g( ) = ν i=0 δ( -i ) + g cont ( ) (1)
For an infinite potential there are only discrete (bound) states.

g( ) = ∞ i=0 δ( -i ) (2)
In this respect, it is useful to make the following remarks. From a practical point of view, the continuum is rather difficult to solve. In most of cases, the resolution of the Schrodinger equation is done through a discrete harmonic oscillator basis and all the spectrum is obtained under a discrete form. In, principle in this way, only bound states are to be considered and the continuum, obtained thus under a discrete form, is not valid and must be solved in other ways. This makes things difficult . Fortunately, there is a method [1] which avoid that, solving the level density by using also unbound states in their discrete form. In this way Eq. ( 1) can reduces to the more simple form given by Eq. (2). Regardless on how this function is solved, in the following, we only will assume that the function g( ) is known, and that, it is not necessary to specify its explicit form.

It is also assumed that this density of states results from the superposition of a smooth monotonous function g 0 ( ) and a fluctuating or oscillating part δg( ). This can be written as:

g( ) = g 0 ( ) + δg( ) (3)
It is known that g 0 ( ) is monotonously increasing function for infinite wells whereas for finite wells it is monotonously increasing and then monotonously decreasing [1]. It will be assumed that, g( ) and g 0 ( ) have the same asymptotic behavior for the increasing part. This is conditioned by the so called asymptotic limit [2,3] :

g( ) ∼ g 0 ( ) as ω (4)
where ω represents one quantum of the energy of the system The aim of the proposed method is only to determine the smooth part g 0 ( ) which does not contain oscillations. This quantity has already been identified to the semi classical level density g sc (λ) [2]. As we will see, the mathematical process we are going to use, leads to the Strutinsky method. In this context, it is only the mathematical framework of the Strutinsky method that is developed here, especially the derivation from the least squares principle. The physical part of this method has been described at length in the references [2,3] and the references quoted therein. One therefore limits ourselves to determining the smooth part g 0 ( ) without calculating the shell correction itself, insisting only on the mathematical aspect.

II. DERIVATION OF THE STRUTINSKY PROCEDURE AS A POLYNOMIAL APPROXIMATION FROM A LOCAL LEAST SQUARES PRINCIPLE

The proof will be established in two successive steps.

A. Step 1: Local least squares polynomial fit

In a first step, we want to average or to smooth g( ) by a polynomial P M ( ) of degree M , in the vicinity of some point = λ over a finite range, by means of a Gaussian weight of effective width γ. The least squares principle will be applied by minimizing the following integral:

I(M, γ, λ) = +∞ -∞ {g( ) -P M ( )} 2 e -( -λ γ ) 2 d (5)
Thus polynomial P M ( ) averages the function g( ) locally over a range defined by the parameter γ around λ. By construction, the coefficients of that polynomial depends on the order M (arbitrarily fixed) and because of the Gaussian, it depends also on γ and λ. For this reason, it will be more correct to write this polynomial as follows:

P M,γ,λ ( ) = M m=0 a m (M, γ, λ) m (6)
Knowing coefficients a m , it is always possible to write this polynomial under the following form:

P M,γ,λ ( ) = M m=0 c m (M, γ, λ) ( -λ) m (7)
Expanding the sum of Eq. ( 7) and indentifying coefficients of power of with those of Eq. ( 6) it is then possible to solve coefficients c m as a linear combination of coefficients a m . Now, it is convenient to introduce the parameter γ seen before as follows:

P M,γ,λ ( ) = M m=0 c m (M, γ, λ)γ m -λ γ m (8)
Finally, du to the Gaussian weight, the most interesting form is to write this polynomial as a combination of Hermite's polynomials of degree m:

P M,γ,λ ( ) = M m=0 d m (M, γ, λ)H m -λ γ (9)
Consequently, the integral to be minimized can be rewritten in the form:

I = +∞ -∞    g( ) - M m=0 d m (M, γ, λ)H m -λ γ    2 e -( -λ γ ) 2 d ( 10
)
The coefficients ensuring the least squares principle will be resolved by minimization:

∂I ∂d k = 0 (11)
This gives:

+∞ -∞ 2    g( ) - M m=0 d m (M, γ, λ)H m -λ γ    -H k -λ γ e -( -λ γ ) 2 d = 0 (12)
Using the orthogonality property of Hermite polynomials, one finds:

d k (M, γ, λ) = 1 2 k k! √ πγ +∞ -∞ g( )H k -λ γ e -( -λ γ ) 2 d (13)
As it can be easily seen coefficient d k (γ, λ, M ) does not depend on M , but Polynomial P M,λ,γ ( ) does. Consequently, omitting M in coefficient d m , this polynomial will be written under the form:

P M,γ,λ ( ) = M m=0 d m (γ, λ)H m -λ γ (14)
Note: In the relationship (5), a Gaussian weight function was used. In fact any weight function tending towards the Dirac delta function can be used. For example, it is perfectly possible to replace the Gaussian weight function with a Lorentzian function in order to apply the least squares principle in the same way. In this case, Eq. ( 5) must be replaced by:

I = +∞ -∞ {g( ) -P M,γ,λ ( )} 2 1 1 + ( -λ γ ) 2 d (15)
In that respect, references [4,5] can be consulted. In the present work, for convenience and simplicity, a Gaussian weight function has been chosen. This is mainly due to the ease of use of Hermite polynomials (which are associated to the Gaussian weight).

B.

Step 2: Definition of the Strutinsky level density as a least squares moving average

Due to the Gaussian factor in Eq. ( 5), the averaging defined in the above subsection is by definition local and thereby depends essentially on the region near λ centered on an interval of a length about γ. Thus, the values that influence the polynomial approximation are the ones which are the closest to λ on either side around λ. The latter being fixed in the least squares principle. This means that if is far from λ, this averaging becomes erroneous since the neighboring points of play a negligible role whereas the points that are close to λ have the main role. To remedy to this problem, one proposes to move the average in a such way that the points in the neighborhood of take the major role. This amounts to "move" the effective interval of averaging with λ. Mathematically, this is simply obtained by making = λ, namely by replacing P M,γ,λ ( ) by P M,γ,λ (λ) or in equivalent way by P M,γ, ( ). In the following, we will choose λ as the new variable. Thus, in simpler terms, Strutinsky's density g(λ) is approached by a local polynomial for any value of λ. In each point λ, polynomial P M,γ,λ (λ) is the result of the smoothing of g(λ) in the neighborhood of λ. However, the coefficients of this polynomial (see Eq. ( 14)) depend also on λ so that in general P M,γ,λ (λ) is not really a polynomial. Finally, the approximation of g(λ) is defined by making = λ in Eq. (14):

g(λ) ≈ P M,γ,λ ( )| =λ = M k=0 d k (γ, λ)H k (0) (16)
In order to emphasize that P M,γ,λ (λ) is in general not a polynomial, it is convenient to change the notation as follows:

P M,γ,λ (λ) = Π M,γ (λ) ( 17
)
Although λ is constant in the least squares procedure, in this definition it must be considered as a variable. Thus, due to the Gaussian weight, Π M,γ (λ) can be considered as an average in an interval about

[λ -γ, λ + γ] whereas Π M,γ (λ + λ) is obtained from the "moved interval" [(λ + λ) -γ, (λ + λ) + γ].
Thus, in the latter, "one moves" the whole averaging region with λ by a quantity equal to λ. For this reason, Π M,γ (λ) is in fact, obtained from a moving average. From Eq. ( 16) one can see that Π M,γ (λ) is a linear combination of functions d k (γ, λ). In this respect, as noted just above, one can show that in general, this procedure does not necessarily lead to a polynomial. Indeed, making x = -λ γ , Eq. ( 13) can be re-written as:

d k (γ, λ) = 1 2 k k! √ π +∞ -∞ g(λ + γx)H k (x)e -x 2 dx ( 18
)
By Taylor expansion, we obtain:

g(λ + γx) = ∞ j=0 g (j) (λ) j! (γx) j (19)
Now, if one assumes that g(λ) is a polynomial in λ of degree n, the previous sum goes only up to n. Replacing that quantity in the above formula, one obtains:

d k (γ, λ) = 1 2 k k! √ π n j=0 g (j) (λ) j! γ j +∞ -∞ x j H k (x)e -x 2 dx k = 0, 1, ....M (20)
Since we assume that g(λ) is a polynomial its derivative are also polynomials and hence, d k (γ, λ, M ) and therefore Π M,γ (λ) are also polynomials. Conversely if g(λ) is not a polynomials , Taylor series becomes infinite and Π M,γ (λ) is no more a polynomial.

III. DERIVATION OF THE INTEGRAL FORM OF THE MOVING AVERAGE. AVERAGING FUNCTIONS

Coefficient d k is given by Eq. ( 13). Replacing its expression in formula ( 16) and inverting sum and integral signs, one gets:

Π M,γ (λ) = +∞ -∞ g( )    M m=0 H m (0) 2 m m! H m -λ γ    e -( -λ γ ) 2 γ √ π d (21)
with:

H m (0) = (-1) m/2 m! (m/2)! , m = even ; H m (0) = 0, m = odd ; ( 22
)
for convenience, we define the following constant:

B m = H m (0) 2 m m! = (-1) m/2 2 m (m/2)! , m = even ; B m = 0, m = odd (23) Making x = -λ γ (24)
One obtains:

Π M,γ (λ) = +∞ -∞ g(λ + γx)    M m=0 B m H m (x)    e -x 2 √ π dx (25)
We define the averaging (or smoothing) functions by:

F M (x) =    M m=0 B m H m (x)    e -x 2 √ π (26)
Using the Darboux-Christoffel formula (see appendix B), function F M (x) can also be written in a second form:

F M (x) = B M H M +1 (x) 2x e -x 2 √ π (27)
We thus obtain an equivalent form of the smoothing average cited above (Eq. ( 16)) as follows:

Π M,γ (λ) = +∞ -∞ g(λ + γx)F M (x)dx (28)
Making in the above equation x = ( -λ)/γ, i.e. = λ + γx, an other form for this result is:

Π M,γ (λ) = +∞ -∞ g( ) 1 γ F M ( -λ γ )d (29)
In the following, we will see that if g( ) reduces to a polynomial of degree M or less, Eq. ( 29) gives the exact result, i.e., g(λ) = Π M,γ (λ) rigorously. This is logical since the polynomial approximation for another polynomial (of an equal or greater degree) must be exact. In mathematics, Eq. ( 28) is known as a convolution product of two functions, which are, g and F M . It is well known that there is a close relationship between the convolution product and the moving average.

IV. GENERAL PROPERTIES OF THE AVERAGING (OR SMOOTHING) FUNCTIONS

The main properties of the averaging (or smoothing) functions are given in the following table:

Property Condition 1 FM (x) = 0 M odd due to the def. of BM 2 FM (-x) = FM (x) M even M even in the following 3 +∞ -∞ G(x)FM (x)dx = 0 G(x) odd f unction for parity reason 4 +∞ -∞ FM (x)dx = 1 see appendix C 5 +∞ -∞ 1 γ FM ( -λ γ )d = 1 variable change in 4 6 +∞ -∞ x k FM (x)dx = 0 1 ≤ k ≤ M see appendix C 7 +∞ -∞ x k FM (x -x0)dx = x k 0 1 ≤ k ≤ M variable change in 6 8 +∞ -∞ k 1 γ FM ( -λ γ )d = λ k 1 ≤ k ≤ M variable change in 7 9 +∞ -∞ x k FM (x)dx = C k,M k ≥ M + 2, k even see appendix C C k,M = (-1) M/2 (k-1)! (M/2)!2 k-1 ((k-M -2)/2)! 10 +∞ -∞ ( -λ) k 1 γ FM ( -λ γ )d = C k,M γ k k ≥ M + 2, k even variable change in 9 TABLE I.
Main properties of the averaging functions.

V. THE WIDTH OF THE AVERAGING FUNCTION

A. Two extreme cases in which the averaging function reduces to Dirac delta distribution (i) If we make γ = 0 in Eq. ( 28) and use the property number 4 of the table, we obtain rigorously Π M,γ (λ) = g(λ). Because eq. ( 29) is equivalent to Eq. (28), we can conclude that for γ → 0 ,

1 γ F M ( -λ γ ) → δ( -λ)
where δ represents the Dirac distribution. (ii) For M → +∞, the constant B M defined in Eq. ( 23) tends to 0 + or 0 -. From the definition (27) of the averaging function F M (x), we should distinguish two cases. For x = 0, the function given by Eq. ( 26) is finite everywhere so that for a fixed x, the corresponding amplitude tends towards zero when M tends towards infinity. For x = 0, in Eq. ( 27) the quotient H M +1 (x)/2x becomes indefinite because the numerator and the denominator cancel simultaneously. Applying L'Hospital's rule, this quotient becomes 2(M + 1)H M (x)/2 . Multiplying by B M e -x 2 / √ π, for x = 0 in Eq. ( 27), we get F M (0) = B M (M + 1)H M (0). Using Eq. ( 22) and (23), we find for M → ∞ that F M (0) → ∞. Thus, when M tends towards infinity the function F M (x) tends towards zero everywhere except at the point x = 0 where it becomes infinite. Moreover its area is equal to 1 so this function tends towards the Dirac delta distribution. we can write: In the title of this subsection, the expression "finite values" means neither infinity nor zero. In theses cases the curve F M (x) does not reduce to delta function as seen in the previous subsection. So, contrarily to what one might think, the actual width of the function F M (x) is not due to the sole γ parameter but is governed by the both parameters γ and M . In fact, the parameter γ (γ = 0) is proportional to the width of the Gaussian contained in the function F M (x), M even. However, as seen in the equation ( 27), this Gaussian is modulated by the polynomial B M H M +1 (x)/(2x). The Hermite polynomial H M +1 (x) has M +1 real symmetrical roots with respect to the axis x = 0 . The value x = 0 is itself a root of the numerator. However, in x = 0, the denominator also cancels and the function F M (x) has actually no root for this value. So, this function has M symmetrical roots with respect to the x = 0 axis. (M/2) positive and (M/2) negative with M even. The function has a main maximum in x = 0 and successive oscillations with an amplitude that decreases rapidly (see Fig. 1). The area of this curve is normalized to the unit. The main contribution of this area comes from the central part because these oscillations decrease rapidly in amplitude when one walks away from the center and also because they have successive areas that are of opposite signs and thereby, approximately compensate each other. The larger M is, the smaller the width of the curve (γ being constant). This means that the larger M is, the more the entire surface of the curve is located near x = 0. To get an idea of the "convergence" of the surface of this curve, let us say that if an integration is performed over a finite interval [-2, 2] for M = 4, we could see that this integral is already quite close to the unit (in fact numerical test gave 0.99). Since the width decreases with M , this result is a fortiori valid for any value of the order M . Thus, we can say that the averaging function F M (x) practically cancels as soon as x 1 so that one can write: In Eq. ( 28), let's expand g(λ + γx) by Taylor's theorem in the vicinity of λ to the order (M + 1) with a rest. There is then a number such as ϑ with -1 < ϑ < 1, so that:

F M (x) → δ(x) when M → ∞.
+X -X F M (x)dx ≈ 1 if X 1 (
Π M,γ (λ) = +∞ -∞ g(λ) + M m=1 g (m) (λ) m! (γx) m + g (M +1) (λ) M + 1! (γx) M +1 + g (M +2) (λ + ϑγx) (M + 2)! (γx) M +2 F M (x)dx (31)
The first term gives back g(λ), the second has no contribution since m M (see property number 6 in the table given above), the third also cancels since the power of x is odd (see property number 3 of the table). Finally this gives:

Π M,γ (λ) = g(λ) + r M +2,γ (λ) (32)
where the absolute remainder contains the (M + 2)th power of γ:

r M +2,γ (λ) = γ M +2 (M + 2)! +∞ -∞ g (M +2) (λ + ϑγx)x M +2 F M (x)dx (33)
Thus, we can see that the averaging yields g(λ) itself but with some noise (remainder). In fact, since all terms corresponding to 1 ≤ m ≤ M cancel, g(λ) is simply the first term of this expansion plus a remainder. For reasons we will explain just below, we first define the relative remainder by:

R M +2,γ (λ) = r M +2,γ (λ) g(λ) = γ M +2 (M + 2)! 1 g(λ) +∞ -∞ g (M +2) (λ + ϑγx)x M +2 F M (x)dx (34)
So Eq.(32) can be written under the form:

Π M,γ (λ) = g(λ) (1 + R M +2,γ (λ)) (35)
B. The relative remainder in the asymptotic limit

In Eq. ( 34), Since |θ| is less than 1 and since the surface of curve F M (x) is practically confined between x = -1 and x = +1 (see Eq. ( 30)), the condition λ |ϑγx| turns to be simply λ γ and it is then legitimate to neglect the quantity ϑγx with respect to λ. Consequently, we will have in Eq. Eq. (34) g (M +2) (λ + ϑγx) ≈ g (M +2) (λ) and the relative remainder will be about:

R M +2,γ (λ) ≈ γ M +2 (M + 2)! g (M +2) (λ) g(λ) +∞ -∞ x M +2 F M (x)dx (36)
Taking into account property number 9 in the table given previously, we obtain:

R M +2,γ (λ) ≈ C M +2,M (M + 2)! γ M +2 g(λ)/g (M +2) (λ) ( 37
)
replacing coefficient C M +2,M by its expression, we explicitly obtain:

R M +2,γ (λ) ≈ (-1) M/2 (M/2)!2 M +1 (M + 2) γ M +2 g(λ)/g (M +2) (λ) (38)
This result is valid only if the following condition holds:

λ γ (39)
In fact γ is of the order of ω (see the next subsection) and the above condition is also called the asymptotic limit and is equivalent to Eq. ( 4). Usually, for finite wells, the bound states are characterized by negatives levels, in this case the quantity λ must be counted from the bottom of the well [2].

C. "Absolute remainder" vs "Relative remainder"

We suppose M fixed, if we make γ = 0 in Eq. ( 33), the absolute remainder cancels rigorously and from Eq. 32, we will have exactly:

Π M,γ (λ) = g(λ) (40)
This limit corresponds to an averaging (or smoothing) over a zero interval (γ = 0), the polynomial reduces simply to the oscillating function g(λ) and actually does not constitute a true averaging. In fact, the goal of the present work is to remove the oscillations contained in g(λ) in order to recover the smooth part g 0 (λ) (see section I). This is why it is not interessant to take a too small value of γ which makes the smoothing inefficient and the absolute remainder close to zero. To find the smooth function g 0 (λ), it will rather be necessary to increase gradually the parameter γ (which defines the averaging interval) until these oscillations stop, i.e., until the curve becomes strictly increasing. This amounts to average the function over a range which is at least as large as the "wavelength" of the oscillations. Let γ 0 be this "optimal value" of the smoothing'. We define the "smoothing condition" by the following relation:

γ = γ 0 ω ( 41
)
Where ω is the mean spacing between shells (which is of the same order of the one quantum of energy). Thus, in the sense of least squares fit, we have g(λ) ≈ g 0 (λ) and Eq. ( 35) becomes:

Π M,γ (λ) ≈ g 0 (λ) 1 + R 0 M +2,γ (λ) (42)
In which the relative remainder is:

R 0 M +2,γ (λ) ≈ C M +2,M (M + 2)! γ M +2 0 g (M ) 0 (λ)/g (M +2) 0 (λ) (43)
Naturally for this value (γ 0 ), the absolute remainder in Eq. 33 is not very small. But in this method it is the relative remainder which plays the main role. For reason of accuracy, it is essential that this relative remainder be very small compared to the unit (see equation 42). Once again, the relative remainder becomes small in Eq. (42) if the condition λ γ 0 is satisfied. The condition of the asymptotic limit and the smoothing condition can be summarized in one double equation:

λ γ 0 ω (44)
As noted in section I, the smoothed level density has been identified as an approximation of the semi classical level density [2]: In order to test the accuracy of the Strutinsky method, it is possible to obtain an asymptotic approximation by combining Eq. ( 28) with the Euler-Maclaurin formula. Let us apply this method to a particle in a cubic box with equal sides a for which the level density is:

g 0 (λ) ≈ g sc (λ) (45)
g( ) = ∞ nx=1 ∞ ny=1 ∞ nz=1 1 γ δ( -nxnynz γ ) ( 46
)
where the n th energy level is given by:

nxnynz = (n 2 x + n 2 y + n 2 z )E 0 (47)
E 0 = π 2 2 2ma 2 (48)
herein n x or n y or n z = 1, 2, .....∞ are quantum numbers (the value 0 is forbidden because the wave function cancels in this case), is the Planck constant and m is the mass of the particle.

To obtain the asymptotic form of g( ), i.e. g 0 ( ) (which is hidden in g( )), we replace this quantity from Eq. ( 46) into Eq. ( 28), getting:

Π M,γ (λ) = +∞ -∞ ∞ nx=1 ∞ ny=1 ∞ nz=1 1 γ δ( λ + γx -(n 2 x + n 2 y + n 2 z )E 0 γ )F M (x)dx (49)
Interverting discrete sum and integral symbol and using Dirac δ property, we find:

Π M,γ (λ) = ∞ nx=1 ∞ ny=1 ∞ nz=1 1 γ F M ( (n 2 x + n 2 y + n 2 z )E 0 γ - λ γ ) (50)
Making:

G(n x , n y , n z ) = 1 γ F M ( (n 2 x + n 2 y + n 2 z )E 0 γ - λ γ ) (51)
and using the three dimensional Euler-MacLaurin formula with the first terms (neglecting the derivatives):

Π M,γ (λ) = ∞ 1 ∞ 1 ∞ 1 G(n x , n y , n z )dn x dn y dn z - 3 2 ∞ 1 ∞ 1 G(n x , n y , 1)dn x dn y + 3 4 ∞ 1 G(n x , 1, 1)dn x - 1 8 G(1, 1 , 1)
(52) After some algebra (see details in the appendix D), one gets an asymptotic expansion.

Π M,γ (λ) ≈ πλ 1/2 4E 3/2 0 1 + a M +2 C M +2,M γ λ M +2 + a M +4 C M +4,M γ λ M +4 + ... - 3π 8E 0 + 3 8E 1/2 0 λ 1/2 1 + b M +2 C M +2,M γ λ M +2 + b M +4 C M +4,M γ λ M +4 + ... (53)
Coefficient C k,M is given in the table above. This asymptotic series has been obtained from the Euler MacLaurin formula. It is a divergent series. To obtain an approximation of the triple integral given above (Eq. 50), we have to take a finite number of terms. To this end, we can ignore for example the powers which are higher than (M + 2).

Π M,γ (λ) ≈ πλ 1/2 4E 3/2 0 1 + a M +2 C M +2,M γ λ M +2 - 3π 8E 0 + 3 8E 1/2 0 λ 1/2 1 + b M +2 C M +2,M γ λ M +2 (54)
From Ref. [2], it turns out that the expression for γ = 0 is the the semi classical level density and is the exact result and the one obtained by the Strutinsky is only an approximation to it, i.e. to:

g sc (λ) = πλ 1/2 4E 3/2 0 - 3π 8E 0 + 3 8E 1/2 0 λ 1/2
(55) This is not surprising because the Euler MacLaurin formula is an asymptotic approximation valid for every value of the parameter γ whereas in the Strutinsky method we are obliged to take a sufficiently large smoothing value for this parameter (Eq. ( 41)). Thus, the second element in both parentheses in Eq. ( 54) must be small enough compared to the unit. For example, taking M = 8 and M = 30, we have tested numerically that: Π 8,γ (λ)

≈ πλ 1/2 4E 3/2 0 1 + 10 -6 γ λ 10 -3π 8E0 + 3 8E 1/2 0 λ 1/2 1 + 10 -5 γ λ 10 Π 30,γ (λ) ≈ πλ 1/2 4E 3/2 0 1 + 10 -9 γ λ 32 -3π 8E0 + 3 8E 1/2 0 λ 1/2 1 + 10 -7 γ λ 32
Thus, in spite of the Strutinsky method is only an approximation of the semi classical method, it is obvious that these results are very accurate in terms of relative error. In this respect, it can be said that if Strutinsky's method is applied correctly, it gives good results and can thus be considered as a type of semi-classical method. It is to be noted that, in these expressions the smoothing parameter is not the same (γ = γ) because this parameter increases with the order M . x k H m (x)e -x 2 dx = 0 f or k = 0, 1, 2, ......., m -1 (A7)

In other words: H m (x) is orthogonal to any polynomial of degree less than m.

Appendix B: Christoffel-Darboux formula applied to averaging functions

M m=0 H m (x)H m (y) 2 m m! = 1 2
H M +1 (x)H M (y) -H M +1 (y)H M (x) 2 M M !(x -y) (B1)
Application to the averaging function F M (x), making y = 0 n the above formula:

M m=0 H m (x)H m (0) 2 m m! = 1 2
H M +1 (x)H M (0) -H M +1 (0)H M (x) 2 M M !(x -0) (B2)
Hermite polynomial has the property that H m (0) = 0 for odd m. Consequently the sum contains only terms corresponding to even values m up to even M . Furthermore Hermite polynomial H m (x) is therefore even and the sum in Eq. (B2) is then an even function. Consequently H M +1 (0) = 0 and we finally conclude that F M (x) is an even function and that M must be even otherwise that function cancels. Thus, it turns out that:

F M (x) =    M m=0 H m (0) 2 m m! H m (x)    e -x 2 √ π = H M (0) 2 M M ! H M +1 (x) 2x e -x 2 √ π (B3)
Or using the definition of the constant

B M F M (x) =    M m=0 H m (0) 2 m m! H m (x)    e -x 2 √ π = B M H M +1 (x) 2x e -x 2 √ π
With (see Eq. 23)):

B M = (-1) M/2 2 M (M/2)! M even B M = 0 M odd
Appendix C: Demonstrations of some Formulas:

1. Integral of the averaging functions

+∞ -∞ F M (x)dx = 1 (C1)
Using the first form F M (x) in Eq. ( 26):

+∞ -∞ M m=0 B m H m (x) e -x 2 √ π dx = B m M m=0 +∞ -∞ H m (x) e -x 2
√ π dx and since H 0 (x) = 1 this can be re-written as

M m=0 B m +∞ -∞ H 0 (x)H m (x) e -x 2 √ π dx = M m=0 B m +∞ -∞ H 0 (x)H m (x) e -x 2 √ π dx = M m=0 B m δ m0 = B 0 = 1 be
We have used the orthogonality property and the fact that B m = Hm(0)

2 m m! = (-1) m/2 2 m (m/2)!

Orthogonality between monomials and averaging functions

This comes essentially from the property given by Eq. (A7).

+∞ -∞

x k F M (x)dx = 0 k = 1, 2, 3, ...., M (M = even) (C2)

In effect, using the second form of F M (x) given in Eq. ( 27), we can write:

+∞ -∞ x k F M (x)dx = +∞ -∞ x k B M H M +1 (x) 2x e -x 2 √ π dx = (B M /2) +∞ -∞ x k-1 H M +1 (x) e -x 2 √ π dx = 0 if k -1 < M + 1.
Due to Eq. (A7), the previous inequality amounts to k < M + 2 or k = 2, 4, 6...M . The case k = 0 has been already proved. The case with odd k is obvious because F M (x) is even.

Property of Hermite polynomials

+∞ -∞ x k H m (x)e -x 2 dx = √ πk! 2 k-m k-m 2 ! if k ≥ m ≥ 0 (C3)
This property has been proved from combinations of the following equation [6]:

+∞ -∞ x 2w+m H m (x)e -x 2 dx = 2 m Γ ( 2w+m+1 2 )Γ ( 2w+m+2 2 ) Γ (w + 1) w = 0, 1, 2, ....
with the well known property of the Gamma function:

Γ (z)Γ (z + 1/2) = 2 1-2z √ πΓ (2z)
and

Γ (n + 1) = n! 4. Property of averaging functions +∞ -∞ x k F M (x)dx = C k,M = (-1) M/2 (M/2)! (k -1)! 2 k-1 1 ((k -M -2)/2)! k = M + 2, M + 4, M + 6, .........∞ (C4)
Using the second form of F M (x), i.e. Eq. ( 27), one has:

+∞ -∞ x k F M (x)dx = +∞ -∞ x k B M H M +1 (x) 2x e -x 2 √ π dx = (B M /2) +∞ -∞ x k-1 H M +1 (x) e -x 2 √ π dx = 0 if k -1 < M + 1.
Thus, making k -1 → k and M + 1 → M in Eq. C3 one obtains the result of Eq. (C4). 1 γ F M ( 3E0 γ -λ γ ) The smoothing condition is about γ 3E 0 (which means the inter shell spacing is of the order of the zero point energy) and the asymptotic limit is λ γ. Because of these conditions , we obtain with a good approximation: x n with |x| < 1

Π M,γ (λ) ≈ 1 8 ∞ -∞ 1 γ F M (s)2π λ+γs E0 1/2 γ E0 ds -3 2 1 4 ∞ -∞ 1 γ F M (t)π γ E0 dt + 3 4 ∞ -∞ 1 γ F M (u)
This gives Π M,γ (λ)

≈ πλ 1/2 4E 3/2 0 n a n ∞ -∞ F M (s) γ λ s n ds -3π 8E0 ∞ -∞ F M (t)dt+ 3 8E 1/2 0 λ 1/2 n b n ∞ -∞ F M (u) γ λ s n du
So applying property number 9 of the table, one gets: )

Π M,γ (λ) ≈ πλ 1/2 4E 3/2 0 1 + a M +2 C M +2,M γ λ M +2 + a M +4 C M +4,M γ λ M +4 + ... - 3π 8E 0 + 3 8E 1/2 0 λ 1/2 1 + b M +2 C M +2,M γ λ M +2 + b M +4 C M +4,M γ λ M +4 + ... ( D1

FIG. 1 .

 1 FIG. 1. Averaging functions Eq.((27)) for three values of the order M . It is to be noted that these functions practically cancel as soon as M 2

  VII. PARTICLE IN A CUBIC BOX WITH REFLECTING WALLS. ASYMPTOTIC EXPANSION OF THE LEVEL DENSITY:

∞ √ 3 1 γ 1 γ 4 ∞ 1 1γ•

 1141 Appendix D: Proof of formula (53)We calculate Eq. (52) by using spherical coordinates for the first integral and polar coordinates for the secondeΠ M,γ (λ) = 1 8 F M ( N 2 E0 γ -λ γ )4πN 2 dN -F M ( n 2 E0 γ -λ γ )2πndn + 3 F M ( n 2 x E0 γ -λ γ )dn x -1 8 G(1, 1, 1)• In the first integral, making n 2 x + n 2 y + n 2 z = N 2 and s = N 2 E0 γ -λ γ we will have N 2 = λ+γs E0 and 2N dN = γ E0 ds • In the second integral, making n 2 x + n 2 y = n 2 and t = n 2 E0 γ -λ γ we will have n 2 = λ+γt E0 and 2ndn = γ E0 dt In the third integral, making u = n 2 x E0 γ -λ γ we will have n 2 x = λ+γu E0 and 2n x dn x = γ E0 du We find: Π M,γ (λ)

Expanding the square roots in tems of γ λ s and γ λ u and assuming that λ γ 1 2 4E

 12 and because of the weakness of the width of F M (x) (see subsection V B) one will have: Π M,γ (λ) ≈ πλ 1/series are obtained from:(1 + x) α = ∞ n=0 a n x n = ∞ n=0 α(α-1)(α-2)...(α-n+1) n!

Appendix A: Hermite polynomials:

The degree of this polynomial is n.

Orthogonality and norm:

+∞

3. Parity and special values

H n (0) = 0 n odd (A6)


Suryajith Chillara
email: suryajith@cmi.ac.in.

On Computing Multilinear Polynomials Using Multi-r -ic Depth Four Circuits

In this paper, we are interested in understanding the complexity of computing multilinear polynomials using depth four circuits in which polynomial computed at every node has a bound on the individual degree of r (referred to as multi-r -ic circuits). The goal of this study is to make progress towards proving superpolynomial lower bounds for general depth four circuits computing multilinear polynomials, by proving better and better bounds as the value of r increases.

Recently, Kayal, Saha and Tavenas (Theory of Computing, 2018) showed that any depth four arithmetic circuit of bounded individual degree r computing a multilinear polynomial on n O(1) variables and degree d = o(n), must have size at least

when r is o(d ) and is striclty less than n 1.1 . This bound however deteriorates with increasing r . It is a natural question to ask if we can prove a bound that does not deteriorate with increasing r or a bound that holds for a larger regime of r .

We here prove a lower bound which does not deteriorate with r , however for a specific instance of d = d (n) but for a wider range of r . Formally, we show that there exists an explicit polynomial on n O(1) variables and degree Θ(log 2 n) such that any depth four circuit of bounded individual degree r < n 0.2 must have size at least exp Ω log 2 n . This improvement is obtained by suitably adapting the complexity measure of Kayal et al. (Theory of Computing, 2018). This adaptation of the measure is inspired by the complexity measure used by Kayal et al. (SIAM J. Computing, 2017).

Introduction

One of the major focal points in the area of algebraic complexity theory is to show that certain polynomials are hard to compute syntactically. Here, the hardness of computation is quantified by the number of arithmetic operations that are needed to compute the target polynomial. Instead of the standard turing machine model, we consider arithmetic circuits and formulas as models of computation.

Arithmetic circuits are directed acyclic graphs such that the leaf nodes are labeled by variables or constants from the underlying field, and every non-leaf node is labeled either by a + or ×. Every node computes a polynomial by operating on its inputs with the operand given by its label. The flow of computation flows from the leaf to the output node. We refer the readers to the standard resources [START_REF] Shpilka | Arithmetic circuits: A survey of recent results and open questions[END_REF][START_REF] Saptharishi | A survey of lower bounds in arithmetic circuit complexity version 8.0.4. Github survey[END_REF] for more information on arithmetic formulas and arithmetic circuits.

Valiant conjectured that the Permanent does not have polynomial sized arithmetic circuits [START_REF] Valiant | Completeness classes in algebra[END_REF]. Working towards that conjecture, we aim to prove superpolynomial circuit size lower bounds. However,

Motivation for this work

Raz and Yehudayoff [START_REF] Raz | Lower bounds and separations for constant depth multilinear circuits[END_REF] showed a lower bound of exp(Ω d log d ) against multilinear depth four circuits which compute a multilinear polynomial over n variables and degree d n (cf. [KST18,

Footnote 9]). Kayal, Saha and Tavenas [START_REF] Kayal | On the size of homogeneous and of depth-four formulas with low individual degree[END_REF] have shown a lower bound of

n r 1.1 Ω d r
for a multilinear polynomial over n O(1) variables and degree d that is computed by a multi-r -ic depth four circuit. This lower bound degrades with the increasing value of r and is superpolynomial only when r is o(d ) and is strictly less than n1.1 . This raises a natural question if the dependence on r could be improved upon.

In this work, we show that for a certain regime of d , we can prove a lower bound that does not deteriorate with increasing values of r .

Theorem 1. Let n and r be integers such that r < n 0.2 . There exists an explicit polynomial Q n of degree Θ(log 2 n), over n O(1) variables such that any syntactically multi-r -ic depth four circuit computing it must have size exp Ω(log 2 n) .

The explicit polynomial that we consider is a close variant of the polynomial considered by Kayal et al. [START_REF] Kayal | On the size of homogeneous and of depth-four formulas with low individual degree[END_REF]. By substituting these parameters into the bound from [START_REF] Kayal | On the size of homogeneous and of depth-four formulas with low individual degree[END_REF], their bound evaluates to n Ω log n r . Note that this bound is superpolynomial only when r = o(log 2 n). Our lower bound is quantitatively better in this regime of parameters.

If we can show superpolynomial size lower bounds against multi-r -ic depth four circuits for r = n c for any constant c, then we indeed have superpolynomial circuit size lower bounds against depth four circuits. We believe that by building on the work of [KST18, HS17], Theorem 1 is a step towards that direction.

In a subsequent work to this, we observed that by careful analysis and by building upon this work and work of Kumar and Saraf [START_REF] Kumar | On the power of homogeneous depth 4 arithmetic circuits[END_REF], we can in fact prove exponential lower bounds against depth four multi-r -ic circuits computing the Iterated Matrix Multiplication polynomial.

Proof overview:

Analogous to the work of Fournier et al. [START_REF] Fournier | Lower bounds for depth-4 formulas computing iterated matrix multiplication[END_REF], and Kumar and Saraf [START_REF] Kumar | On the power of homogeneous depth 4 arithmetic circuits[END_REF], we first consider multi-r -ic depth four circuits of low bottom support 2 and prove lower bounds against them.

Let T 1 , T 2 , . . . , T s be the terms corresponding to the product gates feeding into the output sum gate. The output polynomial is obtained by adding the terms T 1 , T 2 , . . . , T s . Note that each of these T i 's is a product of low support polynomials Q i , j , that is, every monomial in these Q i , j 's is supported on a small set of variables (say µ many). One major observation at this point is to see that there can be at most N • r many factors in any of the T i 's.

Kayal et al. [START_REF] Kayal | On the size of homogeneous and of depth-four formulas with low individual degree[END_REF] observed that the measure of shifted partial derivates [START_REF] Kayal | A super-polynomial lower bound for regular arithmetic formulas[END_REF][START_REF] Fournier | Lower bounds for depth-4 formulas computing iterated matrix multiplication[END_REF] does not yield any non-trivial lower bound if the number of factors is much larger than the number of variables itself. They worked around this obstacle by defining a hybrid complexity measure (refered to as Shifted Skew Partial Derivatives) where they first split the variables into two disjoint and unequal sets Y and Z such that |Y | |Z|, then considered the low order partial derivatives with respect to only the Y variables and subsequently set all the Y variables to zero in the partial derivatives obtained. This effectively reduces the number of factors in a partial derivative to at most |Z| • r . They then shift these polynomials by monomials in Z variables and look at the dimension of the polynomials thus obtained. This measure gave them a size lower bound of

n r 1.1 Ω d r
against multi-r -ic depth four circuits computing an explicit polynomial on n O(1) variables and degree d = o(n) when r = o(d ). To improve the dependence on r in the lower bound, we consider a variant of Shifted Skew Partial Derivatives that we call Projected Shifted Skew Partial Derivatives. Here, we project down the space of Shifted Skew Partials and only look at the multilinear terms. Since the polynomial of interest is multilinear, it makes sense to only look at the multilinear terms obtained after the shifts of the skew partial derivatives. This is analogous to the method employed by Kayal et al. [START_REF] Kayal | An exponential lower bound for homogeneous depth four arithmetic formulas[END_REF] to prove exponential lower bounds for Homogeneous depth four circuits, through the measure of Projected Shifted Partial Derivatives.

We first show that the dimension of Projected Shifted Skew Partial derivatives is not too large for small multi-r -ic depth four circuits of low bottom support. We then show that there exists an explicit polynomial whose dimension of Projected Shifted Skew Partial derivatives is large and thus cannot be computed by small multi-r -ic depth four circuits. We then lift this result to multi-r -ic depth four circuits for suitable set of parameters.

Preliminaries

Notation:

• For a polynomial f , we use ∂ =k Y ( f ) to refer to the space of partial derivatives of order k of f with respect to monomials of degree k in Y .

• We use z = and z ≤ to refer to the set of all the monomials of degree equal to and at most , respectively, in Z variables.

• We use z ≤ ML to refer to the set of all the multilinear monomials of degree at most in Z variables.

• We use z ≤ NonML to refer to the set of all the non-multilinear monomials of degree at most in Z variables.

• For a monomial m we use |MonSupp(m)| to refer to the size of the set of variables that appear in it.

• For a polynomial f , we use |MonSupp( f )| to refer to the maximum |MonSupp(m)| over all monomials in f .

Depth four circuits: A depth four circuit (denoted by ΣΠΣΠ) over a field and variables {x 1 , x 2 , . . . , x n } computes polynomials which can be expressed in the form of sums of products of polynomials. That is,

s i=1 d i j =1
Q i , j (x 1 , . . . , x n ) for some d i 's. A depth four circuit is said to have a bottom support of t (denoted by ΣΠΣΠ {t } ) if it is a depth four circuit and all the monomials in each polynomial Q i, j are supported on at most t variables.

Multi-r-ic arithmetic circuits:

Definition 2 (multi-r-ic circuits). Let r = (r 1 , r 2 , • • • , r n ). An arithmetic circuit Φ is said to be a syntac- tically multi-r-ic circuit if for all product gates u ∈ Φ and u = u 1 × u 2 × • • • × u t , each variable x i can appear in at most r i many of the u i 's (i ∈ [t ]
). Further the total degree with respect to every variable over all the polynomials computed at u

1 , u 2 , • • • , u t , is bounded by r , i.e. j ∈[t ] deg x i ( f u j ) ≤ r i for all i ∈ [n]. If r = (r, r, • • • , r
), then we simply refer to them as multi-r -ic circuits.

Complexity Measure: We shall now describe our complexity measure which we shall henceforth refer to as Dimension of Projected Shifted Skew Partial Derivatives. This is a natural extension of the Dimension of Shifted Skew Partial Derivatives as used by [START_REF] Kayal | On the size of homogeneous and of depth-four formulas with low individual degree[END_REF].

This is analogous to the work of [START_REF] Kayal | Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas[END_REF] where they study a shifted partials inspired measure called Shifted Projected Partial derivatives and then [START_REF] Kayal | An exponential lower bound for homogeneous depth four arithmetic formulas[END_REF] where they study Projected Shifted Partial derivatives.

Since the polynomial of interest is multilinear, it does make sense for us to only look at those shifts of the partial derivatives, that maintain multilinearity. At the same time, since the individual degree of the intermediate computations in the multi-r -ic depth four circuit is large and non-multilinear terms "cancel" out to generate the multilinear polynomial, we can focus on the multilinear terms generated after the shifts by projecting our linear space of polynomials down to them. We describe this process formally, below.

Let the variable set X be partitioned into two fixed, disjoint sets Y and Z such that |Y | is a magnitude larger than

|Z|. Let σ Y : [Y Z] → [Z] be a map such that for any polynomial f (Y, Z), σ Y ( f ) ∈ [Z]
is obtained by setting every variable in Y to zero by it and leaving Z variables untouched. Let mult : [Z] → [Z] be a map such that for any polynomial f (Y, Z), mult( f ) ∈ [Z] is obtained by setting the coeficients of all the non-multilinear monomials in f to 0 and leaving the rest untouched. We use

z ≤ • σ Y (∂ =k Y f
) to refer to the linear span of polynomials obtained by multiplying each polynomial in σ Y (∂ =k Y f ) with monomials of degree at most in Z variables. We will now define our complexity measure, Dimension of Projected Shifted Skew Partial Derivatives (denoted by Γ k, ) as follows.

Γ k, ( f ) = dim -span mult z ≤ • σ Y ∂ =k Y f
This is a natural generalization of Shifted Skew Partial Derivatives of [START_REF] Kayal | On the size of homogeneous and of depth-four formulas with low individual degree[END_REF]. The following proposition is easy to verify. Proposition 3 (Sub-additivity). Let k and be integers. Let the polynomials f ,

f 1 , f 2 be such that f = f 1 + f 2 . Then, Γ k, ( f ) ≤ Γ k, ( f 1 ) + Γ k, ( f 2 ) .
Monomial Distance: We recall the following definition of distance between monomials from [START_REF] Chillara | Depth-4 lower bounds, determinantal complexity: A unified approach. computational complexity[END_REF].

Definition 4 (Definition 2.7, [START_REF] Chillara | Depth-4 lower bounds, determinantal complexity: A unified approach. computational complexity[END_REF]). Let m 1 , m 2 be two monomials over a set of variables. Let S 1 and S 2 be the multisets of variables corresponding to the monomials m 1 and m 2 respectively. The distance dist(m 1 , m 2 ) between the monomials m 1 and m 2 is the min{|S

1 | -|S 1 ∩ S 2 |, |S 2 | -|S 1 ∩ S 2 |}
where the cardinalities are the order of the multisets.

For example, let

m 1 = x 2 1 x 2 x 2 3 x 4 and m 2 = x 1 x 2 2 x 3 x 5 x 6 . Then S 1 = {x 1 , x 1 , x 2 , x 3 , x 3 , x 4 }, S 2 = {x 1 , x 2 , x 2 , x 3 , x 5 , x 6 }, |S 1 | = 6, |S 2 | = 6 and dist(m 1 , m 2 ) = 3.
It is important to note that two distinct monomials could have distance 0 between them if one of them is a multiple of the other and hence the triangle inequality does not hold.

The following beautiful lemma (from [START_REF] Gupta | Approaching the chasm at depth four[END_REF]) is key to the asymptotic estimates required for the lower bound analyses.

Lemma 5 (Lemma 6, [GKKS14]). Let a(n), f (n), g (n) : ≥0 → ≥0 be integer valued functions such that ( f + g ) = o(a). Then, ln (a + f )! (a -g )! = ( f + g ) ln a ± O ( f + g ) 2 a
We use the following strengthening of the Principle of Inclusion and Exclusion in our proof.

Lemma 6 (Strong Inclusion-Exclusion

[KS14]). Let W 1 ,W 2 , • • • ,W t be subsets of a finite set W . For a parameter λ ≥ 1, let i, j ∈[t ] i = j W i ∩ W j ≤ λ i∈[t ] |W i | . Then, ∪ i∈[t ] W i ≥ 1 4λ i ∈[t ] |W i | .
Polynomial Families: Let n, α, k be positive integers. We define the polynomial family P n,α,k n,α,k≥0 as follows. Let the variable set X = {x 1 , . . . , x N 0 } be partitioned into two fixed, and disjoint sets Y and Z. We first define the polynomial family f n,α,k (Y, Z) as follows (as it was defined in [START_REF] Kayal | On the size of homogeneous and of depth-four formulas with low individual degree[END_REF]).

f n,α,k = k i=1 g i (Y i , Z i ) where g i (Y i , Z i ) = a,b ∈[n] y (i) a,b c∈[α] z (i,1) a,c z (i,2) c+α,b .
It is easy to see that |Y | is n 2 k and |Z| is 2αnk. We shall henceforth use m to refer to |Z|. Thus,

N 0 = |X | = |Y | + |Z| = k(n 2 + 2αn).
Let c be a fixed constant in (0, 1). We shall now define another polynomial family P n,α,k based on the definition of f n,α,k . Let p = N -c 0 . Let X = {x 1,1 , x1,2 , . . . , x1,t , . . . , xN 0 ,1 , xN 0 ,2 , . . . , xN 0 ,t } be a variable set distinct from X such that t = N 0 log N 0 p

. Let Lin p : X → X be a linear map such that x i → t j =1 xi,j for all i ∈ [N 0 ]. Then the polynomial P n,α,k ( X ) be defined to be f n,α,k • Lin p ( X ). That is,

P n,α,k = f n,α,k t j =1 x1,j , t j =1 x2,j , • • • , t j =1
xN 0 , j where t = N 0 log N 0 p .

Note that P n,α,k is a polynomial on N = N 2+c 0 log N 0 many variables.

We will now recall the following lemma which in the mentioned form is due to Kumar and Saptharishi [START_REF] Saptharishi | A survey of lower bounds in arithmetic circuit complexity version 8.0.4. Github survey[END_REF].

Lemma 7 (Analogous to Lemma 20.5, [START_REF] Saptharishi | A survey of lower bounds in arithmetic circuit complexity version 8.0.4. Github survey[END_REF]). Let ρ be a random restriction on the variable set X that sets each variable to zero with a probability of at least (1 -p) where p = N -c 0 for some constant c ∈ (0, 1) . Then f n,α,k (X ) is a projection of ρ(P n,α,k ( X )) with a probability of at least (1 -2 -N 0 ).

Multi-r -ic Depth Four Circuits of Low Bottom Support

For some carefully chosen parameters k and , we shall first show that if a multi-r -ic depth four circuit C of bottom support µ is small then Γ k, (C ) is not too large. We shall then show that Γ k, ( f n,α,k ) is large and thus it cannot be computed by C .

Upper Bound on Γ k, (C )

Recall that C is a sum of at most s many products of polynomials T (1) + • • • + T (s) where each T i is a syntactically multi-r -ic product of polynomials of low monomial support.

We shall first prove a bound on Γ k, (T i ) for an arbitrary T i and derive a bound on Γ k, (C ) by using sub-additivity of the measure (cf. Theorem 3).

Let T be a syntactic multi-r -ic product of polynomials Q1 (Y, Z)

• Q2 (Y, Z) • . . . • QD (Y, Z) • R(Y )
such that MonSupp( Qi ) ≤ µ. We will first argue that D is not too large since T is a syntactically multi-r -ic product. We shall first pre-process the product T by doing the following procedure.

Repeat this process until all but at most one of the factors in T (except R) have a Z-support of at least µ 2 .

1. Pick two factors Qi 1 and Qi,2 such that they have the smallest

Z-support amongst Q 1 , • • • , Q D .
2. If both of them have support strictly less than µ 2 , merge these factors to obtain a new factor. Else, stop.

In the afore mentioned procedure, it is important to note that the monomial support post merging will still be at most be µ since the factors being merged are of support strictly less than µ 2 . Henceforth, W.L.O.G we shall consider that every product gate at the top, in any multi-r -ic depth four circuit to be in a processed form.

Let T = Q 1 (Y, Z) • Q 2 (Y, Z) • . . . • Q t (Y, Z) • R(Y )
be the product obtained after the preprocessing. Each of the Q i has a Z-support of at least µ 2 . The total Z-support is at most |Z| r = m r since T is a syntactically multi-r -ic product. Thus t could at most be 2m r µ .

Lemma 8. Let n, k, r, and µ be positive integers such that

+ kµ < m 2 . Let T be a processed syntactic multi-r -ic product of polynomials Q 1 (Y, Z) • Q 2 (Y, Z) • . . . • Q t (Y, Z) • R(Y ) such that |MonSupp(Q i )| ≤ µ. Then, Γ k, (T ) is at most t k • m +kµ • ( + kµ).
Before proving Theorem 8, we shall first use it to show an upper bound on the dimension of the space of Projected Shifted Skew Partial derivatives of a depth four multi-r -ic circuit of low bottom support.

Lemma 9. Let n, k, r, and µ be positive integers such that + kµ < m 2 . Let C be a processed syntactic multi-r -ic depth four circuit of bottom support µ and size s. Then,

Γ k, (C ) is at most s • 2m r µ k • m +kµ •( +kµ).
Proof. W.L.O.G we can assume that C be expressed as s i T (i) such that T (i) is a processed syntactically multi-r -ic product of bottom support polynomials at most µ. From Theorem 3, we get that Γ k, (C ) ≤ s i =1 Γ k, (T (i) ). From the afore mentioned discussion we know that the number of factors in T (i) with a non-zero Z-support is at most 2m r µ . From Theorem 8, we get that Γ k, (T (i) ) is at most

2m r µ k • m +kµ • ( + kµ)
. By putting all of this together, we get that

Γ k, (C ) ≤ s • 2m r µ k • m + kµ • ( + kµ) .
Proof of Theorem 8. We will first show by induction on k, the following.

∂ =k Y T ⊆ -span    S∈( t t -k ) i∈S Q i (Y, Z) • z ≤kµ ML • [Y ]    -span    S∈( t t -k ) i∈S Q i (Y, Z) • z ≤k r µ NonML • [Y ]   
The base case of induction for k = 0 is trivial T is already in the required form. Let us assume the induction hypothesis for all derivatives of order < k. That is, ∂ =k-1 Y T can be expressed as a linear combination of terms of the form

h(X , Y ) = i∈S Q i (Y, Z) • h 1 (Z) • h 2 (Y )
where S is a set of size t -(k -1), h 1 (Z) is a polynomial in Z variables of degree at most (k -1)r µ, and h 2 (Y ) is some polynomial in Y variables. In fact, h 1 (Z) can be expressed as a linear combination of multilinear monomials of degree at most (k -1)µ, and non-multilinear monomials of degree at most (k -1)r µ.

For some u ∈ [|Y |] and some fixed i 0 in S,

∂ h(Y, Z) ∂ y u =     j ∈S i∈S i = j Q i (Y, Z) • ∂ Q j (Y, Z) ∂ y u • h 1 (Z) • h 2 (Y )     + i∈S Q i Q i 0 • Q i 0 (Y, Z) • h 1 (Z) • ∂ h 2 (Y ) ∂ y k ∈ -span      i∈S i = j Q i (Y, Z) • ∂ Q j (Y, Z) ∂ y u • h 1 (Z) • [Y ] | j ∈ [S]      -span i∈S Q i Q i 0 • Q i 0 (Y, Z) • h 1 (Z) • [Y ] ⊆ -span      T ∈( S |S|-1 ) i∈T Q i (Y, Z) • z µ ML • h 1 (Z) • [Y ]           T ∈( S |S|-1 ) i∈T Q i (Y, Z) • z ≤r µ NonML • h 1 (Z) • [Y ]      ⊆ -span    T ∈( t t -k ) i∈T Q i (Y, Z) • z ≤kµ ML • [Y ]    -span    T ∈( t t -k ) i∈T Q i (Y, Z) • z ≤k r µ NonML • [Y ]   
The last inclusion follows from the fact that h 1 (Z) is a linear combination of multilinear monomials of degree at most (k -1)µ, and non-multilinear monomials of degree at most (k -1)r µ. From the discussion above we know that any polynomial in ∂ k Y (T ) can be expressed as a linear combination of polynomials of the form

∂ h ∂ y u
. Further every polynomial of the form

∂ h ∂ y u belongs to the set W = -span    T ∈( t t -k ) i∈T Q i (Y, Z) • z ≤kµ ML • [Y ]    -span    T ∈( t t -k ) i∈T Q i (Y, Z) • z ≤k r µ NonML • [Y ]    .
Thus, we get that ∂ =k T is a subset of W . This completes the proof by induction.

From the afore mentioned discussion, we can now derive the following expressions. (1)

σ Y ∂ =k Y T ⊆ -span      S∈( [t ] t -k ) i∈S σ Y (Q i ) • z ≤kµ ML      -span      S∈( [t ] t -k ) i∈S σ Y (Q i ) • z ≤k r µ NonML      z ≤ σ Y ∂ =k Y T ⊆ -span      S∈( [t ] t -k ) i∈S σ Y (Q i ) • z ≤ +kµ ML      -span      S∈( [t ] t -k ) i∈S σ Y (Q i ) • z ≤ +k r µ NonML      =⇒ -span mult z ≤ • σ Y ∂ =k Y T ⊆ -span      S∈( [t ] t -k ) i ∈S mult(σ Y (Q i )) • z ≤kµ+ ML      . Thus we get that dim -span mult z ≤ • σ Y (∂ =k Y T ) is at most dim    -span      S∈( [t ] t -k ) i∈S mult(σ Y (Q i )) • z ≤kµ+ ML         ≤ dim   -span    S∈( t t -k ) i∈S mult(σ Y (Q i ))      • dim -span z ≤kµ+ ML ≤ t t -k • kµ+ i=0 m i ≤ t k • m + kµ • ( + kµ) (Since + kµ < m/2).

Lower

a 1 ,b 1 y (2) a 2 ,b 2 • • • y (k) a k ,b k
that is used to derive f n,α,k with. For every ∆ 0 < k, there is a subset

∆ 0 ⊂ [n] 2k of size n 2k-∆ 0 ∆ 0 ( 2k ∆
≥ ∆ 0 . Then dist ∂ k (a,b) f n,α,k , ∂ k (a ,b ) f n,α,k ≥ α∆ 0 .
Let m 1 , m 2 , . . . , m t be the monomials in the set 0 (= ∂ =k ∆ 0 f n,α,k ), over Z variables such that dist(m i , m j ) ≥ ∆ ≥ α∆ 0 for all i = j . Further, σ Y ( 0 ) = 0 . Let be the set of mutlilinear monomials of the form m i m over Z-variables for some 1 ≤ i ≤ t where m is a monomial of length .

It is important to note that the set now corresponds to the set

z = • σ Y ∂ =k ∆ 0 f n,α,k . We shall now
show that the cardinality of the set is large enough for a suitable setting of parameters α, ∆ 0 and k. Proof. For all i ∈ [t ], Let B i be the set of multilinear monomials of the form m i m where m is a multilinear monomial of degree . From the previous discussion, it follows that | | = ∪ t i=1 B i . Using the principle of Inclusion and Exclusion, we get that

∪ t i=1 B i ≥ t i=1 |B i | - t i = j ∈[t ] B i ∩ B j . Claim 14. For all i ∈ [t ], |B i | = m-(d -k) . Proof. Since deg(m i ) is equal to d -k, the cardinality of B i is equal to m-(d -k) .
Claim 15. For all i, j ∈

[t ] such that i = j , B i ∩ B j ≤ m-(d -k)-∆ -∆ .
Proof. Consider any two monomials mi and mj from B i and B j respectively. For mi and mj to be identical, mi should contain at least ∆ variables from mj \ mi and similarly mj should contain at least ∆ variables from mi \ mj . The rest of the at most ( -∆) many variables should be the same both in mi and mj . The number of such multilinear monomials over Z variables is at most

m-(d -k)-∆ -∆
.

Putting Theorem 14 and Theorem 15 together, we get the following.

| | = ∪ t i=1 B i ≥ t m -(d -k) - t 2 2 m -(d -k) -∆ -∆ . Let T 1 = t m-(d -k) and T 2 = t 2 2 m-(d -k)-∆ -∆
. Let us consider the case where T 2 = λT 1 where λ ≥ 1 for some setting of the parameters ∆, α, and k.

λ = T 2 T 1 = t 2 2 m-(d -k)-∆ -∆ t m-(d -k) = t 2 • (m -(d -k) -∆)! ( -∆)!(m --(d -k))! • (m --(d -k))! ! (m -(d -k))! = t 2 • (m -(d -k) -∆)! (m -(d -k))! • ! ( -∆)! = t 2 • (m -(d -k) -∆)! m! • m! (m -(d -k))! • ! ( -∆)! = t 2 • m (d -k) • ∆ m (d -k)+∆ (Using Theorem 5) = t 2 • m ∆ .
The math block above crucially uses the fact that

∆ 2 = o( ) and (d -k) 2 = o(m) while invoking Theorem 5. Since λ ≥ 1, we get that t 2 • m ∆ ≥ 1.
For some suitably fixed constants δ and , let ∆ 0 be set to δk and be set to

m 2 (1 -). Recall that for a fixed ∆ 0 , t = n 2k-∆ 0 ∆ 0 ( 2k ∆ 0 ) and ∆ = α∆ 0 = δαk. Thus, n 2k-∆ 0 2 2k ∆ 0 • m ∆ ≥ 1 n 2k-∆ 0 ≥ 2∆ 0 m ∆ 2k ∆ 0 n 2k-∆ 0 ≥ 2 1 - ∆ 2k ∆ 0 ∆ 0 n (2-δ)k ≥ 2 1 - αδk 2k ∆ 0 δk and hence, α ≤ (2 -δ) log n -δ log 2 δ δ log 2 1- .
Invoking Theorem 6 with the previous discussion, we get that

| | ≥ T 1 4λ = t m-(d -k) 4λ = 1 2 m ∆ • m -(d -k) = 1 2 2 1 - δαk • m -(d -k) .
Lemma 16. Let m, k, d , r, and µ be positive integers such that + kµ < m 2 , ∆ 0 = δk and = m 2 (1 -) for some fixed constants δ and . Then,

Γ k, ( f n,α,k ) ≥ | | ≥ 1 2 2 1- δαk • m-(d -k) .
Proof. Recall that corresponds to the set

z = • σ Y ∂ =k ∆ 0 f n,α,k .
Since is a bag of multilinear monomials over just the Z variables

| | = dim -span mult z = • σ Y ∂ =k ∆ 0 f n,α,k Since ∂ =k ∆ 0 f n,α,k ⊆ ∂ =k f n,α,k and z = ⊆ z ≤ , we get that dim -span mult z = • σ Y ∂ =k ∆ 0 f n,α,k ≤ dim -span mult z ≤ • σ Y ∂ =k Y f n,α,k = Γ k, ( f n,α,k ) . Thus, Γ k, ( f n,α,k ) ≥ | | ≥ 1 2 2 1- δαk • m-(d -k) .
We shall now a size lower bound on the depth four multi-r -ic circuits of low bottom support that compute f n,α,k . • (m -

) (d -k)-kµ = 1 2( + kµ) • 2 1 - δαk • kµ 2e m r k • m - kµ • m - m d -k = 1 2( + kµ) • 2 1 - δαk • µ 4eαn r k • 1 - 1 + kµ • 1 + 2 d -k = 1 2( + kµ) • 2 1 - δαk • µ 4eαn r k • 1 - 1 + kµ • 1 + 2 2αk = 1 2( + kµ) • 2 1 - δ • 1 + 2 2 αk • µ 4eαn r k • 1 - 1 + kµ = exp αk log 2 1- δ • 1+ 2 2 -k log n -k log r -k log 4eα µ + kµ log 1- 1+
2( + kµ) .

In the above math block, we use Theorem 5 to simplify the terms along with the fact that k 2 µ 2 = o(m -), (dk) 2 = o(m) and k 2 µ 2 = o( ). To get a meaningful lower bound, we need On the other hand, from Theorem 17 we know that any multi-r -ic ΣΠΣΠ {µ} circuit that computes f n,α,k must be of size exp(Ω(k log n)). Thus, it must be that exp(Ω(k log n)) ≤ s ≤ N γ µ . We can choose c to be a small enough constant such that the aforementioned expression is satisfied. Thus, s must at least be exp Ω(log 2 n) . The explicit polynomial Q n is P n,α,k where α =

  Bound on Γ k, ( f n,α,k ) First we recall the generalized Hamming bound [GRS19, Section 1.7]. Claim 10. Let the vectors a = (a 1 , a 2 , . . . , a k ) and b = (b 1 , b 2 , . . . , b k ) correspond to the indices of the Y -monomial y

  0 ) such that for all (a, b), (a , b ) ∈ , dist((a, b), (a , b )) ≥ ∆ 0 . Observation 11. It is important to note that ∂ k f n,α,k y of (a, b) ∈ [n] 2k is a multilinear monomial over just the Z variables. Claim 12. Let (a, b) and (a , b ) be such that dist((a, b), (a , b ))

Lemma 13 .

 13 Let m, k, d , r, ∆ 0 , ∆, and µ be positive integers such that +kµ < m 2 , (d -k) 2 = o(m), ∆ 2 = o(m), ∆ 0 = δk and = m 2 (1 -) for some fixed constants δ and . Then, | | ≥

Theorem 17 ..

 17 Let δ = 0.25 and = 0.8. Let n, r, α, k and µ be positive integers such that r ≤ n 0.2 , Let C be a depth four multi-r -ic circuit of low bottom support µ and size s.If C computes the polynomial f n,α,k then s must be exp(Ω(k log n)).Proof. Recall that the polynomial f n,α,k is defined on the variable sets Y and Z such that |Z| = m = 2αnk. Let be an integer such that = m 2 (1 -) and + kµ < m 2 . Let ∆ 0 = δk. Let us assume that the polynomial f n,α,k is computed by a depth four multi-r -ic circuit C of low bottom support µ and size s. Then it must be the case that Γ k, ( f n,α,k ) = Γ k, (C ).

Agrawal and Vinay [AV08], Koiran, and Tavenas[START_REF] Tavenas | Improved bounds for reduction to depth 4 and depth 3[END_REF] showed that any general circuit can be depth reduced to a depth four circuit of non-trivial size.

That is, all the product gates at the bottom are supported on small set of variables.

This reduces to showing that there exist constants δ, and ν such that

(1)

Let us fix the constants as follows: = 0.8, δ = 0.25 and ν = 0.23. Through some calculations, it can be verified that Equation 1 gets satisfied. Thus,

50 and r ≤ n 0.2 , we get that s ≥ exp (Ω (k log n)).

Multi-r -ic Depth Four Circuits

To prove the main theorem, we also need the following lemma.

Lemma 18 (Analogous to Lemma 20.4, [START_REF] Saptharishi | A survey of lower bounds in arithmetic circuit complexity version 8.0.4. Github survey[END_REF]). Let P be a multi-r -ic polynomial that is computed by a syntactically multi-r -ic depth 4 circuit C of size s ≤ N γ µ for some γ > 0 . Let ρ be a random restriction that sets each variable to zero independently with probability (1 -N -2γ ) . Then with probability at least (1 -N -γ µ ) the polynomial ρ(P ) is computed by a multi-r -ic depth four circuit C of bottom support at most µ and size s .

Proof of Theorem 1. Let n be a large positive integer. Let us set some relevant parameters in terms of n or otherwise as follows.

Let X = {x 1,1 , x1,2 , . . . , x1,t , . . . , xN 0 ,1 , xN 0 ,2 , . . . , xN 0 ,t } be a set of variables over which the polynomial P n,α,k is defined. Let ρ : X → {0, * } be a random restriction such that a variable is set to zero with a probability of (1 -N -2γ ), and is left untouched otherwise. Let C be a syntactically multi-r -ic depth four circuit of size s ≤ N γ µ that computes P n,α,k . Theorem 18 tells us that C = ρ(C ) is a multi-r -ic depth four circuit of size s and bottom support at most µ with a probability of at least (1 -N -γ µ ).

Conditioned on this probability, ρ(P n,α,k ) has a multi-r -ic ΣΠΣΠ {µ} size at most s.

Theorem 7 tells us that f n,α,k is a p-projection of ρ(P n,α,k ) with a probability of (1-2 -N 0 ) and hence f n,α,k also has a multi-r -ic ΣΠΣΠ {µ} of size at most s with a probability of at least (1-N -γ µ -2 -N 0 ). In other words, there is a random restriction σ such that f n,α,k is a p-projection of ρ(P n,α,k ) and C = ρ(C ) is a multi-r -ic ΣΠΣΠ {µ} circuit.

Missing Proofs:

Proof of Theorem 10. There are n 2k elements in . It is easy to see that the volume of a Hamming Ball of radius ∆ 0 for vectors of length 2k is at most

n ∆ 0 and thus there are at most 2k ∆ 0 n ∆ 0 many vectors (a, b) in that Hamming ball. Thus, there exists a packing of these Hamming balls in with at least

many balls.

Proof of Theorem 12. For a vector (a, b)

is at least α. Similar is the case when b i = b i . Thus, if dist((a, b), (a , b )) ≥ ∆ 0 ), there are at least ∆ 0 many locations where either

The following proofs are a step by step adaptation, rather a replication of proofs Lemma 20.4 and Lemma 20.5 respectively in [START_REF] Saptharishi | A survey of lower bounds in arithmetic circuit complexity version 8.0.4. Github survey[END_REF].

Proof of Theorem 18. Let C be a multi-r -ic depth four circuit of size s. Let m 1 , m 2 , • • • , m t be the set of monomials computed at the lower product gate of C , that have at least µ distinct variables in their support. Note that t is at most s. For all i ∈ [t ], Pr[ρ(m i ) = 0] ≤ N -2γ µ . By taking an union bound, the probability that there exists in a monomial amongst m 1 , m 2 , • • • , m t which is not set to 0 by ρ is at most t • N -2γ µ ≤ s • N -2γ µ ≤ N -γ µ . Thus with a probability of at least (1 -N -γ µ ), all the monomials at the bottom product gate have at most µ distinct variables in their support.

Proof of Theorem 7. For all i ∈ [N 0 ],

By union bound, probability that there exists an i ∈ [N 0 ] such that all the variables of the form xi,j for j ∈ [t ] are set to zero is at most 1 2 N 0 . Thus, with a probability of at least (1 -2 -N 0 ), for each i, there exists at least one j such that ρ(x i, j ) = 0.It is easy to see that the polynomial f n,α,k can be written as a p-projection of ρ(P n,α,k ) in such a case.