text:
# 1 Introduction

## 1 Introduction

Physicists have recently begun doing research in finance with wide application of models earlier introduce in physics  . The statistical properties of financial time series are attracting experts of statistical physics, fluctuations analysis, dynamical chaos and others. Papers on finance are appearing with some frequency in physics journals. A new movement called econophysics has been established . On the other hand, several empirical studies have determined scale-invariant behavior of both the long range correlations of price volatility and share volume traded in financial markets . Mandelbrot introduced the concept of fractals in terms of statistical self similarity  and using the context of self-affine time series extended the concept to time series . The basic definition of self-affine time series is that the power spectral density of the time series has a power-law dependence on frequency $`S(f)=f^\beta `$. Universality of $`1/f`$ noise, when $`\beta =1`$, has led to speculations that there might exist some generic mechanism underlying production of so general statistical properties. Such concepts as fractional Brownian motion provide a formal procedure how to produce self-affine time series, but can’t serve as generic mechanism. We will generalize the simple model introduced by Kaulakys and Meškauskas (KM)  to generate time series in the range $`0\beta 2`$ with particular interest in financial time series.

Long range correlations in time series $`I(t)`$ are quantified by autocovariance (autocorrelation) function $`C(s)`$:

$$C(s)=C(s)=\frac{1}{T}_0^{Ts}I(t)I(t+s)𝑑t,$$
(1)
with Wiwner-Khintchine relation to power spectral density $`S(f)`$ defined as:

$$S(f)=\underset{T\mathrm{}}{lim}\frac{2}{T}\left|_0^TI(t)e^{i2\pi ft}𝑑t\right|^2=4\underset{T\mathrm{}}{lim}_0^TC(s)\mathrm{cos}(2\pi fs)𝑑s,$$
(2)
where $`T`$ denotes the considered time interval of time series $`I(t)`$ . The KM model is based on the time series generated as:

$$I(t)=\underset{k}{}q_k\delta (tt_k)$$
(3)
where $`q_k`$ is a contribution to the signal of one pulse and noise is due to the correlations between the occurrence times $`t_k`$ of $`\delta `$ type pulses. This model corresponds to the flow of point objects: photons, electrons, cars, trades in financial markets and so on. The simplest version of the model consist of sequence of transit times $`t_k`$ described by recurrence equations:

$`t_k`$ $`=`$ $`t_{k1}+\tau _k,`$
$`\tau _k`$ $`=`$ $`\tau _{k1}\gamma (\tau _{k1}\overline{\tau })+\sigma \epsilon _k.`$ (4)
Here the recurrence time $`\tau _k=t_kt_{k1}`$ fluctuates due to the external random perturbation of the system by sequence of uncorrelated normally distributed random variables $`\left\{\epsilon _k\right\}`$ with zero expectation and unit variance, where $`\sigma `$ denotes the standard deviation of the white noise, $`\gamma 1`$ is the recurrence time $`\tau `$ relacsation rate to the some average value $`\overline{\tau }`$. Note that $`\tau `$ follows an autoregressive process AR(1).

This model containing only one relaaxation time $`\gamma ^1`$ can for sufficiently small parameters $`\gamma `$ produce an exact $`1/f`$ \- like spectrum in wide range of frequence :

$$S(f)=\frac{\alpha _H}{\overline{\overline{\tau }}^2f},f_1<f<\mathrm{min}(f_2,f_{\overline{\tau }}),$$
(5)
where $`\alpha _H`$ is a dimensionless constant — the Hooge parameter:

$$\alpha _H=\frac{2}{\sqrt{\pi }}Ke^{K^2},K=\frac{\overline{\tau }\sqrt{\gamma }}{\sigma }.$$
(6)
and $`f_1=\gamma ^{3/2}/\pi \sigma `$, $`f_2=2\gamma ^{1/2}/\pi \sigma `$, $`f_\tau =(2\pi \overline{\tau })^1.`$

Here we present generalized KM model with particular interest to reproduce the statistical properties of share volume traded in financial markets. We will generate discrete share volume time series with recurrence time of distinct trades described as AR(2) process. This particular application of the model proposed by B. Kaulakys and T. Meškauskas will exhibit univesality of the mechanism underlying production of an $`f^\beta `$ noise.

## 2 Model definition

In the numerical data analysis we usually deal with discrete sets of data. There is the first need to modify the model to the discrete one. Let us introduce a new conventional time scale defined with a time interval $`\tau _d.`$ Integrating continuous signal $`I(t)`$ in the subsequent intervals of length $`\tau _d`$ we will get discrete time series (let us call it volume $`V_r`$) :

$$V_r=_{t_r}^{t_r+\tau }I(t)𝑑t=\underset{k}{}q_k,t_r=r\tau _d.$$
(7)
Consequently, the discrete power spectral density can be expressed as:

$$S(f_s)=\frac{2}{\tau _dn}\left|\underset{r=1}{\overset{n}{}}V_re^{i2\pi (s1)(r1)/n}\right|^2,$$
(8)
where $`f_s=\frac{s1}{T}`$, $`T=\tau _dn`$.

New discrete series are equivalent to the initial sequence of $`\delta `$ functions, when $`\tau _d\overline{\tau }`$ whit the same values of $`\gamma `$ and $`\sigma `$. Numerical results of $`S(f_s)`$ calculated with various parameters are shown in Fig. 1. Multiple numerical calculations confirm full correspondence of the discrete model (DM) defined here with earlier introduced by B. Kaulakys and T. Meškauskas .

The model can produce the $`1/f`$\- like spectrum in an arbitrarily wide range of frequencies $`f_1<f<f_2,f_\tau `$ and is free from unphysical divergence of the spectrum at $`f0`$; for $`f<f_1`$:

$$S(f)=\overline{\tau }^2\frac{2\sigma ^2/\overline{\tau }\gamma ^2}{1+\sigma ^4/4\overline{\tau }^2\gamma ^4}.$$
(9)
Due to the long memory random process, defining transit time sequence $`t_k,`$ the model describes long time correlations quantified in power spectral density $`S(f)1/f`$. This model may be also generalized for non-Gaussian distribution of the periods $`\tau _k`$. Then

$$S(f)=2\overline{\tau }^1\psi (0)/f,$$
(10)
where $`\psi (\tau )`$ is the distribution density of periods $`\tau _k`$. This makes the model applicable to the wide variety of stochastic processes, which have well defined distribution function $`\psi (\tau )`$ in the vicinity of $`\tau _k=0`$. Numerical calculations confirm that, when $`\psi (0)=0`$, the dependance of the power spectral density on frequency appears as $`S(f)1/f^{3/2}`$ .

One more generalization of the model is needed for applications in financial markets and other self-affine time series with a power-law dependence on frequency $`S(f)=f^\beta `$ with $`\beta 1/2.`$ We will strengthen high frequencies and will account for positive playback of $`\tau _k`$ increment by adding the term $`\alpha \mathrm{\Delta }\tau _{k1}=\alpha (\tau _{k1}\tau _{k2})`$ to the $`\tau _k`$ recurrent expression:

$$\tau _k=\tau _{k1}+\alpha (\tau _{k1}\tau _{k2})\gamma (\tau _{k1}\overline{\tau })+\sigma \epsilon _k.$$
(11)
Note that this new term changes autoregressive process AR(1) to the higher one AR(2). Multiple numerical calculations with the generalized discrete model (GDM) exhibit dependance of $`\beta `$ on $`\alpha `$ and other parameters of the model: $`\sigma ,\overline{\tau },\gamma `$. We demonstrate an example of numerical calculation with GDM in Fig. 2, which exhibits clear fractional power law with $`\beta =1/2`$ of the power spectral density.

## 3 Application to the financial market

An important quantity that characterizes the dynamics of price movement in financial markets is the number of shares $`V_r`$ (share volume) traded in a time interval $`r\tau _d<t<(r+1)\tau _d`$. The statement “It takes volume to move stock prices” accumulates very general idea that statistical properties of financial markets are enclosed in time series of share volume. Very direct confirmation of this statement and quantitative investigation of the largest 1000 stocks in three major US stock markets was recently presented in . This work provides an evidence that long range correlations in share volume and price volatility are largely due to those of the number of trades $`N_r`$ in time interval $`\tau _d`$. Close correlation between $`N_r`$ and $`V_r`$ is imposed by the relation:

$$V_r\underset{i=1}{\overset{N_r}{}}q_i$$
(12)
and very weak correlation in time sequence of share volume per transaction $`q_i`$. These results suggest us to apply GDM as a model for the time series of share volume traded in financial markets , with a simple assumption that in the first approach the average $`q_i`$ can be included into the normalization factor. This mean that simple relation $`V_r=N_rq_i`$ enables us to make comparison of GDM to the variety of real market data. In Fig. 3. we demonstrate comparison of Lithuanian Stock Market data with numerical results from GDM. The volume of shares included in the index LITIN is normalized to average of 100 trades per $`\tau _d=1\mathrm{d}\mathrm{a}\mathrm{y}`$ . Note that despite the model simplicity it serves as market data generator and reproduces the main statistical property of the system, i.e., the power law dependence ($`\beta =1/2`$) on the frequency of the power spectral density.

## 4 Conclusion

The empirical evidence provided by Gopikrishnan *et al* , that the number of transactions $`N_r`$ in the subsequent time intervals $`\tau _d`$ define long range correlations of share volume traded, enabled us to apply simple model of a $`1/f`$ noise  and to reproduce long-range correlations of the share volume traded in financial markets. We generalized the KM model by integrating the sequence of pulses in a conventional time interval $`\tau _d`$ and replacing the recurrent time $`\tau _k`$ stochastic process from AR(1) to the AR(2) one. Numerical calculations with the generalized discrete model (GDM) reproduce power spectral density $`S(f)`$ scaled as power of frequency $`1/f^\beta `$ for various values of $`\beta `$, including $`\beta =1/2`$ for applications in financial markets. Further investigation of the model with its possible applications in financial time series is in progress.

## Acknowledgment

The author gratefully acknowledges numerous and long discussions with Bronislovas Kaulakys regarding inherent origin of $`1/f`$ noise and applicability of KM model.


format: text

text:
# Entropy and a generalisation of “Poincare’s Observation”

## 1 Notation and Definitions

Diaconis and Freedman  consider $`𝐗`$, a random variable uniformly distributed on the surface of a sphere of radius $`\sqrt{n}`$ in $`n`$ dimensions. They show that the distribution of $`\pi _{n,k}𝐗`$, the first $`k`$ coordinates of $`𝐗`$, is close in total variation distance to a Gaussian for large $`n`$. They indicate a natural connection between this problem and the equivalence of ensembles for the free Hamiltonian, where a sphere corresponds to a surface of constant kinetic energy. In this paper, we consider a more general family of manifolds defined by symmetric, additive Hamiltonians. Unlike Diaconis and Freedman we shall not assume a uniform distribution on these surfaces. We prove convergence in the stronger Kullback–Leibler sense of relative entropy distance.

First, we introduce notation. Given measurable $`f:\{\mathrm{}\}`$ we define $`F`$ to be the set on which $`f`$ is finite, and let $`R_n=R_n(f)`$ be given by $`R_n(𝐱)=_{i=1}^nf(x_i),`$ We define the surface $`𝒮_n(t)=\{𝐱:R_n(𝐱)=nt\}F^n.`$ Given $`f`$ and $`c>0`$, define $`g_{n,c}`$ for the density of a Gibbs distribution: $`g_{n,c}(𝐱)=\mathrm{exp}(cR_n(𝐱))/Z_c^n.`$ We assume that $`f`$ has the property that $`Z_c=\mathrm{exp}(cf(x))𝑑x`$ is finite for all $`c>0`$. Define the projection $`\pi _{n,k}:^n^k`$ restricting to the first $`k`$ coordinates: $`\pi _{n,k}(x_1,x_2,\mathrm{},x_n)=(x_1,x_2,\mathrm{},x_k)`$. For any probability density $`q`$ on $`^n`$ write the energy $`\epsilon (q)=q(𝐱)R_n(𝐱)𝑑𝐱`$ and the entropy $`h(q)=q(𝐱)\mathrm{log}q(𝐱)d𝐱`$.

For a given $`f`$, we know that Gibbs densities maximise the entropy for a given energy. (This characterisation of Gibbs measures via a variational principle is discussed in Chapter 15 of Georgii ). This is done by considering the Kullback–Leibler distance $`D(pg_{n,c})`$, where $`D(fg)=f(𝐱)\mathrm{log}(f(𝐱)/g(𝐱))𝑑𝐱`$, for $`f`$ and $`g`$ probability densities on $`^k`$.

###### Example 1.1

Two cases in particular are significant here:

1. If $`f(x)=x^2`$, then $`Z_c=\sqrt{\pi /c}`$, and $`g_{n,c}(𝐱)=_{i=1}^ng_{1,c}(x_i)`$, where $`g_{1,c}`$ is a $`N(0,(2c)^1)`$ density, the density which maximises entropy subject to a variance constraint.
2. If $`f(x)=x`$ for $`x0`$ and $`f(x)=\mathrm{}`$ for $`x<0`$, then $`Z_c=1/c`$, and $`g_{n,c}(𝐱)=_{i=1}^ng_{1,c}(x_i)`$, where $`g_{1,c}`$ is an Exp($`c`$) density, the density which maximises entropy on the positive half-line subject to a mean constraint.

Now we can state Diaconis and Freedman’s results on the normal and exponential case in the form:

###### Theorem 1.2

For $`f`$ as in Example 1.1.1 or 1.1.2 and for a given $`t(0,\mathrm{})`$, take $`c`$ such that $`\epsilon (g_{1,c})=t`$ and let $`𝐗`$ be distributed uniformly on the surface $`𝒮_n(t)F^n`$. Writing $`p_{n,k,t}(𝐲)`$ for the density of $`\pi _{n,k}𝐗`$:

For $`f(x)=x^2`$, as in Example 1.1.1, $`d_{TV}(p_{n,k,t},g_{k,c})2(k+3)/(nk3)`$.

For $`f(x)=x`$, as in Example 1.1.2, $`d_{TV}(p_{n,k,t}𝐗,g_{k,c})2(k+1)/(nk1)`$.

The following theorem is the main result of this paper. It involves a class $``$ of functions (we postpone the precise definition to Definition 2.2, but roughly speaking we want $`f`$ to be strictly increasing and well-behaved at zero). Let $`h_{n,t}`$ be the density corresponding to uniform distribution on $`𝒮_n(t)`$.

###### Theorem 1.3

Assuming $`f`$, for any $`t(0,\mathrm{})`$ take $`c`$ such that $`\epsilon (g_{1,c})=t`$ and consider $`𝐗`$, a random variable with density $`p`$ on $`𝒮_n(t)`$. Writing $`p_{n,k,t}(𝐲)`$ for the density of $`\pi _{n,k}𝐗`$, for some constant $`C=C(f)`$:

$$D(p_{n,k,t}g_{k,c})D(ph_{n,t})+\mathrm{log}\left(\frac{n}{nk}\right)+\frac{2}{\sqrt{n}/C1}.$$

A major motivation for this work, beyond the intrinsic interest of generalising Diaconis and Freedman’s work , comes from the question of so-called ‘equivalence of ensembles’. Given a Hamiltonian $`H(𝐱)`$, for $`𝐱^n`$ we can consider the microcanonical ensemble (uniform measure with density $`h_{n,t}`$ on the surface $`\{𝐱:H(𝐱)=nt\}`$) and grand canonical ensemble (Gibbs measure with density $`g_{n,c}`$ proportional to $`\mathrm{exp}(cH(𝐱))`$ for $`𝐱^n`$). The principle of equivalence of ensembles suggests that in some sense $`h_{n,t}`$ and $`g_{n,c}`$ are close together, that is

$$p(𝐱)h_{n,t}(d𝐱)p(𝐱)g_{n,c}(𝐱)$$
(1)
for some class of test functions $`p`$. Convergence in total variation distance (as established by Diaconis and Freedman) implies that Equation (1) holds for $`p`$ bounded and continuous and depending only on $`k=o(n)`$ coordinates. Theorem 1.3 implies this for a wider class of test functions, including the Hamiltonian itself.

###### Corollary 1.4

Assuming $`f`$, for any $`t(0,\mathrm{})`$

$$\underset{n\mathrm{}}{lim}\left(p(𝐱)h_{n,t}(d𝐱)p(𝐱)g_{n,c}(𝐱)\right)=0,$$

for $`p`$ depending only on $`k`$ coordinates, if $`p(x_1,\mathrm{},x_k)`$ is bounded above by a multiple of $`1+_{i=1}^kf(x_i)`$. Here, $`k`$ need not be fixed, and can grow as $`o(n)`$.

Proof  This is a consequence of Theorem 1.3 in conjunction with Lemma 3.1 of Csiszár . The latter states that $`D(u_nv)0`$ implies $`p(x)u_n(x)𝑑xp(x)v(x)𝑑x`$, for any $`p`$ such that $`\mathrm{exp}(tp(x))v(x)𝑑x<\mathrm{}`$ for small $`|t|`$. This integral is seen to be finite by definition of the partition function.

A second application is to results of de Finetti type, as described in . For example, define an infinite sequence $`X_1,X_2,\mathrm{}`$ of random variables to be orthogonally invariant if for any $`n`$, the law of $`(X_1,\mathrm{},X_n)`$ is invariant under orthogonal transformations of $`^n`$. Schoenberg  states that all orthogonally invariant distributions are mixtures of normals. Diaconis and Freedman  prove this by showing that the first $`k`$ of $`n`$ orthogonally invariant variables are within $`2k/n`$ of a mixture of normals, so a passage to the limit provides the infinite result.

In a similar way we can consider $`f`$-invariant measures; that is, sequences of random variables such that for any $`n`$, the law of $`(X_1,\mathrm{},X_n)`$ is invariant under continuous transformations of $`^n`$ which preserve $`R_n(x_1,\mathrm{},x_n)`$. We show:

###### Corollary 1.5

For $`f`$, the only $`f`$-invariant measures $`P`$ are mixtures of Gibbs measures. That is, if we write $`G_{\mathrm{},c}`$ for the distribution of $`Y_1,Y_2,\mathrm{}`$, where $`Y_i`$ are independent with density $`g_{1,c}`$, there exists a measure $`\lambda `$, valued on $`c>0`$, such that

$$P=G_{\mathrm{},c}\lambda (c)𝑑c.$$

Proof  First we consider finite subsequences of $`X_1,\mathrm{}`$. If measure $`P_n`$ is invariant under $`R_n`$-preserving transformations then (as in ), $`P_n`$ is constant on each manifold $`𝒮_n(t)`$, so:

$$P_n=h_{n,t}\mu _n(t)𝑑t,$$

for some measure probability measure $`\mu _n`$. Now projecting down to the first $`k`$ coordinates:

$$Q_k=\pi _{n,k}P_n=(\pi _{n,k}h_{n,t})\mu _n(t)𝑑t.$$

Writing $`c(t)`$ for the unique $`c`$ such that $`\epsilon (g_{1,c})=t`$, and defining $`R_k=g_{k,c(t)}\mu _n(t)𝑑t`$, then:

$$R_kQ_k_{TV}\mu _n(t)(\pi _{n,k}h_{n,t})g_{k,c(t)}𝑑t\sqrt{\frac{2k}{nk}},$$

by Theorem 1.3.

Duplicating Diaconis and Freedman’s tightness argument we can show that as $`n\mathrm{}`$, $`\mu _n`$ must have a convergent subsequence, with limit $`\mu `$. Mapping from $`t`$ to $`c(t)`$, we find a $`\lambda `$ with the required properties.

The fact that projecting a uniform distribution on a sphere approximately gives a Gaussian is often referred to as Poincaré’s Observation (see for example ). However, in Section 6 of their paper, Diaconis and Freedman suggest that this attribution is wrong, and that the earliest reference to it in the probability literature comes in the work of Borel. Nonetheless, it appears that the observation is even older than this, and can be traced back to Mehler .

Csiszár  uses entropy-theoretic methods to consider the distribution of a random variable $`X_1`$, conditional on the vector $`𝐗=(X_1,\mathrm{},X_n)A`$ for some set $`A`$. However, these results rely on $`A`$ being a ‘thick set’ of positive measure, whereas in the present paper we consider the so-called ‘thin shell’ case. Dembo and Zeitouni  extended Csiszár’s results to the distribution of the first $`k`$ coordinates, where $`k=k(n)`$ can vary with $`n`$, and (as in this paper) discovered that a sufficient condition for convergence is that $`k(n)=o(n)`$. Schroeder  generalised this result to Markov processes, and Comets and Zeitouni  even to mean–field perturbations of Markov processes. However, all these papers use the assumption that $`A`$ has non-empty interior. This corresponds to a weak limit theorem, bounding the probability of a particular set, whereas our methods require a local limit theorem, bounding densities.

## 2 Class of Functions Considered

It is natural to ask for the widest possible class of functions $`f`$ such that results such as Theorem 1.2 hold. For technical reasons, we will need to control $`w_n`$, the density of $`R_n(𝐗)`$, when $`𝐗`$ has Gibbs density $`g_{n,c}`$. Specifically we need an upper bound on $`\mathrm{log}(w_{nk}(s)/w_n(t))`$ for certain $`s,t`$. Theorem 1.2 holds because $`w_n`$ is known exactly (in Example 1.1.1 $`R_n(𝐗)`$ is the sum of squares of normals, with the $`\chi _n^2`$ distribution, and in Example 1.1.2 $`R_n(𝐗)`$ is the sum of exponentials, with the $`\mathrm{\Gamma }(n,c)`$ distribution). A later paper by Borovkov  extends Diaconis and Freedman’s work to the case $`f(x)=|x|^p`$, again using exact calculations of the density. Whilst his bounds are tighter, the method will not extend to the general case – it gives no information about Hamiltonians of the form $`f(x)=x^2+ϵx^4`$.

However, we can make progress in other cases too. The key observation is that $`X_i`$ are IID (with marginal density $`g_{1,c}`$), so $`R_n(𝐗)=_{i=1}^nf(X_i)`$ is a sum of $`n`$ IID random variables. Using a local version of the Central Limit Theorem, we will be able to show that the densities are sufficiently close in supremum norm to a Gaussian density for our result to go through. We obtain a proposition reminiscent of Equation (2.9) of .

###### Proposition 2.1

Consider $`𝐗`$ with density $`g_{n,c}`$ and let $`Y_j=f(X_j)`$, with $`𝔼Y_j=\mu `$, $`\text{Var}(Y_j)=\sigma ^2`$, and characteristic function $`\varphi (u)=𝔼\mathrm{exp}(iuY_j)`$. Assume that $`I=|\varphi (u)|^r𝑑u`$ is finite for some $`r1`$ and $`m=𝔼|Y\mu |^3`$ is finite. If $`w_k`$ is the density of $`R_k(𝐗)=_{i=1}^kY_i`$ then there exists a constant $`C=C(Y)`$ such that for $`nkr`$:

$$\mathrm{log}\left(\frac{w_{nk}(z)}{w_n(n\mu )}\right)\mathrm{log}\left(\frac{n}{nk}\right)+\frac{2}{\sqrt{n}/C1}\text{ for all }z\text{.}$$

Proof  The local limit theorem tells us that there exists a constant $`C(Y)`$ such that if $`f_n`$ is the density of $`(Y_i\mu )/\sqrt{n\sigma ^2}`$ then for $`nr`$:

$$\underset{x}{sup}\left|f_n(x)\frac{1}{\sqrt{2\pi }}\mathrm{exp}(x^2/2)\right|\frac{C(Y)}{\sqrt{2\pi n}}.$$

A careful reading of (for example) Section 46 of Gnedenko and Kolmogorov  shows that the dependence of $`C(Y)`$ on $`Y`$ comes through $`m,\sigma ^2,I`$ and $`\nu =sup_{t>\sigma ^2/m}|\varphi (t)|<1`$.

Rescaling this, we know that for any $`z`$:

$$w_{nk}(z)\frac{\sqrt{nk}+C}{(nk)\sqrt{2\pi \sigma ^2}}\text{ and }w_n(n\mu )\frac{\sqrt{n}C}{n\sqrt{2\pi \sigma ^2}}.$$

Taking the ratio of these terms we deduce the result, since:

$$\mathrm{log}\left(\frac{\sqrt{nk}+C}{\sqrt{n}C}\right)\mathrm{log}\left(1+\frac{2C}{\sqrt{n}C}\right).$$

We can now describe the class of surfaces that our Theorem will cover. These conditions on function $`f`$ are chosen so that they imply that the local limit theorem will hold in Proposition 2.1. We confirm this in Lemmas 2.3 and 2.4 below. Roughly speaking, we require the function $`f`$ to grow faster than a linear function on most of the domain, and to be well-behaved at $`0`$.

###### Definition 2.2

Define $``$ to be the class of functions $`f:\{\mathrm{}\}`$ with:

1. $`f(0)=0`$, $`f(x)`$ right continuous at $`0`$.
2. $`f(x)`$ is differentiable for $`x>0`$ with $`f^{}(x)>0`$ and:

1. There exist $`a_1`$,$`a_2`$ such that $`f^{}(x)a_1>0`$ for $`x(a_2,\mathrm{})`$.
    2. There exist $`1<q<2`$ and $`a_3>0`$ such that:

    $$lim\underset{x0}{inf}\frac{f^{}(x)^q}{f(x)}a_3.$$
3. Either (a) $`f(x)\mathrm{}`$ for $`x<0`$ or (b) $`f(x)=f(x)`$ for all $`x`$. As before, we write $`F`$ for the interval on which $`f`$ is finite.

Notice that for any $`p1`$, picking $`f(x)=x^p`$ on $`x0`$ and infinity elsewhere, or $`f(x)=|x|^p`$ everywhere ensure that $`f`$. Thus the cases considered by Diaconis and Freedman  and Borovkov  are included in our theorems.

Conditions 1 and 2 ensure that $`Z_c`$ is finite and non-zero for $`c(0,\mathrm{})`$, since then $`\mathrm{exp}(cf(x))𝑑xa_2+_{a_2}^{\mathrm{}}f^{}(x)\mathrm{exp}(cf(x))/a_1a_2+\mathrm{exp}(cf(a_2))/ca_1`$, and continuity provides boundedness away from zero.

###### Lemma 2.3

Assume $`f`$. If $`X`$ has density $`g_{1,c}(x)=\mathrm{exp}(cf(x))/Z_c`$ and $`Y=f(X)`$, then $`m=𝔼|Y𝔼Y|^3`$ is finite.

Proof  In case 3(a) and 3(b) of Definition 2.2 $`f(X)`$ will have the same density, hence we need only consider case 3(a). Further, note that in this case, since $`Y0`$, $`m=𝔼(Y\mu )^3`$, the 3rd cumulant. Since the moment generating function of $`Y`$ is $`M(t)=Z_{ct}/Z_c`$, the cumulant generating function $`\mathrm{log}M(t)=\mathrm{log}Z_{ct}\mathrm{log}Z_c`$, and the result follows.

###### Lemma 2.4

If $`f`$, then if $`X`$ has density $`g_{1,c}(x)=\mathrm{exp}(cf(x))/Z_c`$ and $`Y=f(X)`$, with characteristic function $`\varphi `$, then there exists $`r`$ such that $`I=|\varphi (u)|^r𝑑u`$ is finite.

Proof  The density $`g(y)`$ of $`Y`$ is $`Z_c^1\mathrm{exp}(cy)/f^{}(f^1(y))`$. As described in for example Theorem 74 of , if $`gL^p`$, for some $`1<p2`$ then $`I`$ is finite for $`rp/(p1)`$. By Condition 2b of Definition 2.2, for $`y`$ close to zero $`g(y)\text{const.}\mathrm{exp}(cy)y^{1/q}`$, so picking $`p>q`$ ensures the finiteness of the integral at 0. Condition 2a gives us control as $`y\mathrm{}`$.

## 3 Nesting and Projection of Surfaces

Recall that we want to project a density $`p`$ from a manifold $`𝒮_n(t)`$ onto its first $`k`$ coordinates. Given $`p`$, we will first create $`(\theta p)`$, a density on $`F^n`$, by placing weighted copies of $`p`$ on each manifold $`𝒮_n(u)`$. One has a free choice of how to weight the individual manifolds. The picture is that of fitting together an infinite set of ‘Russian dolls’, each of different sizes, but each with the same pattern of densities on their surface. We then consider the projection of $`p`$ by considering the projection of $`(\theta p)`$ conditional on being on $`𝒮_n(t)`$.

By a suitable choice of weighting, we can make the projection well-behaved. For example, in the case of the uniform density on the sphere, we weight concentric spheres by the $`\chi ^2`$ distribution to produce the normal density on $`^n`$.

We need to develop a coordinate system that allows us to describe a point $`𝐱`$ in space by giving its distance from the origin $`\mathrm{𝟎}`$ and the point where the line from $`\mathrm{𝟎}`$ to $`𝐱`$ crosses $`𝒮_n(t)`$. In the case of the sphere $`f(x)=x^2`$, this corresponds to transforming between rectangular and polar coordinates. We shall require one further technical lemma, not proved here:

###### Lemma 3.1

For any $`t(0,\mathrm{})`$, the equation $`\epsilon (g_{1,c})=t`$ has a unique solution as an equation in $`c`$, if $`f(0)=0`$, $`f`$ is right continuous at zero, increasing on $`x>0`$, $`f(x)\mathrm{}`$ as $`x\mathrm{}`$, and $`f(x)=\mathrm{}`$ for $`x<0`$.

More formally, we give a $`C^1`$-foliation of $`F^n\backslash \{\mathrm{𝟎}\}`$ by compact $`(n1)`$-dimensional manifolds $`𝒮_n(u)`$, $`u>0`$. Each manifold is endowed with a standard Riemannian metric and diffeomorphic, by a central projection, to either a unit sphere centered at the origin or to its intersection with a non-negative orthant.

###### Proposition 3.2

For given $`t`$, under Conditions 1 and 2 of Definition 2.2 there exists a bijection $`\mathrm{\Phi }_t`$ between $`\{x:x>0\}\times 𝒮_n(t)`$ and $`F^n\{\mathrm{𝟎}\}`$. The bijection $`\mathrm{\Phi }_t`$ has a Jacobian $`A_{n,t}`$ which is positive everywhere.

Proof  For given $`u`$ and for any $`𝐱F^n\{\mathrm{𝟎}\}`$, under Conditions 1 and 2 of Definition 2.2, the equation $`R_n(k𝐱)=u`$ has a unique solution in $`k>0`$, by the Intermediate Value Theorem. Hence given $`(r,𝐬)`$, where $`r>0`$ and $`𝐬𝒮_n(t)`$, we can find a unique $`𝐱=k𝐬`$, where $`k`$ is chosen such that $`R_n(k𝐬)=nr`$. Conversely, given $`𝐱`$, we can define the central projection $`S_{n,t}(𝐱)=k𝐱`$, where $`k`$ is chosen such that $`R_n(k𝐱)=nt`$, which is equivalent to saying that $`k𝐱𝒮_n(t)`$. We take the pair $`(r,𝐬)=(R_n(𝐱),S_{n,t}(𝐱))`$.

This foliation induces a coordinate system on $`F^n\backslash \{\mathrm{𝟎}\}`$ via the bijection $`\mathrm{\Phi }_t`$. Let $`\sigma _{n,t}`$ denote the induced Riemannian volume on $`𝒮_n(t)`$. The Jacobian $`A_{n,t}(𝐱)=A_{n,t}(t,𝐬)`$ is determined since for any measurable function $`f`$:

$`{\displaystyle _{_+\times 𝒮_n(t)}}f(t,𝐬)\mathrm{\Phi }_t(dt,d𝐬)`$ $`=`$ $`{\displaystyle _^n}f(R_n(𝐱),S_{n,t}(𝐱))𝑑𝐱`$
$`=`$ $`{\displaystyle _{_+\times 𝒮_n(t)}}f(t,𝐬)A_{n,t}(t,𝐬)𝑑t\sigma _{n,t}(d𝐬).`$
The positivity of $`f^{}`$ ensures the positivity of $`A_{n,t}`$, since the local structure of the above foliation (and the induced map $`\mathrm{\Phi }_t`$) may be also described as follows. Given a point $`𝐱`$, such that $`\mathrm{\Phi }_t(𝐱)=(R_n(𝐱),S_n(𝐱))`$, for small $`\delta 𝐱`$, we calculate $`\mathrm{\Phi }_t(𝐱+\delta 𝐱)`$. Now $`R_n(𝐱+\delta 𝐱)=R_n(𝐱)+_i\delta x_if^{}(x_i)+O(\delta x^2)`$, which is not identically equal to $`R_n(𝐱)`$. Similarly, if $`S_n(𝐱)=k𝐱𝒮_n(t)`$, then $`S_n(𝐱+\delta 𝐱)`$ is $`k(1ϵ)(𝐱+\delta 𝐱)`$, where $`ϵ`$ is chosen such that this lies on $`𝒮_n(t)`$. The choice of $`ϵ`$ that achieves this is $`ϵ=(f^{}(x_i)\delta x_i)/(f^{}(x_i)x_i)`$, which again ensures that $`S_n(𝐱+\delta 𝐱)`$ is not identically equal to $`S_n(𝐱)`$.

Now having developed our coordinate system, we can describe the map $`\theta `$ which takes a density on $`𝒮_n(t)`$ and gives a density on $`F^n`$. The motivation for this definition is that it gives an isometry between densities (see Lemma 3.4).

###### Definition 3.3

Given a probability density $`p`$ on $`𝒮_n(t)`$, we can define the product density $`(w_n\times p)`$ on $`_+\times 𝒮_n(t)`$, where $`w_n`$ is the density of $`R_n(𝐗)`$ when $`𝐗`$ has density $`g_{n,c}`$. We can thus define the density $`(\theta p)`$ induced by $`\mathrm{\Phi }_t`$ on $`F^n\{\mathrm{𝟎}\}`$, since transforming to Cartesian coordinates, we know that:

$$(\theta p)(𝐱)=\frac{w_n(R_n(𝐱))p(S_{n,t}(𝐱))}{A_{n,t}(R_n(𝐱),S_{n,t}(𝐱))},\text{ for }𝐱\mathrm{𝟎}\text{,}$$

which is by construction a probability density on $`F^n\{\mathrm{𝟎}\}`$.

The one significant difference, as mentioned by Borovkov, is that we will no longer consider the uniform distribution on the surface but rather consider $`h_{n,t}(𝐯)=A_{n,t}(nt,𝐯)/\left(A_{n,t}(nt,𝐬)\sigma _{n,t}(d𝐬)\right)`$ for $`𝐯𝒮_n(t)`$.

###### Lemma 3.4

With the definitions above: $`D(\theta pg_{n,c})=D(ph_{n,t})`$.

Proof  Note that $`w_n`$ is characterized by:

$`{\displaystyle _0^r}w_n(t)𝑑t`$ $`=`$ $`{\displaystyle g_{n,c}(𝐱)𝕀(R_n(𝐱)r)𝑑𝐱}`$
$`=`$ $`{\displaystyle \mathrm{exp}(ct)Z_c^n𝕀(tr)\left(A_{n,t}(nt,𝐬)\sigma _{n,t}(d𝐬)\right)𝑑t}.`$
We deduce that for any $`𝐮F^n`$, $`g_{n,c}(𝐮)=w_n(R_n(𝐮))/\left(A_{n,t}(nt,𝐬)\sigma _{n,t}(d𝐬)\right)`$.

Hence by definition, $`(\theta h_{n,t})(𝐮)=w_n(R_n(𝐮))/\left(A_{n,t}(nt,𝐬)\sigma _{n,t}(d𝐬)\right)=g_{n,c}(𝐮)`$. This means that

$`D(\theta pg_{n,c})`$ $`=`$ $`D(\theta p\theta h_{n,t})={\displaystyle \theta p(𝐱)\mathrm{log}\left(\frac{p(S_{n,t}(𝐱))}{h_{n,t}(S_{n,t}(𝐱))}\right)𝑑𝐱}`$
$`=`$ $`{\displaystyle p(𝐬)\mathrm{log}\left(\frac{p(𝐬)}{h_{n,t}(𝐬)}\right)𝑑𝐬}`$
as required.

###### Definition 3.5

Given $`t>0`$ and a density $`p`$ on $`𝒮_n(t)`$, write $`p_{n,k,t}(𝐲)`$ for the density of $`p`$ projected by $`\pi _{n,k}`$ onto $`^k`$.

The key observation is that $`p_{n,k,t}(𝐲)=q_{n,k}(𝐲,nt)/w_n(nt),`$ which is the projection of $`(\theta p)`$ on $`^k`$ conditioned on $`R_n=nt`$. Here $`q_{n,k}(𝐲,nt)`$ may be treated as the joint density of $`\pi _{n,k}𝐗=𝐲`$ and $`R_n(𝐗)=nt`$, where $`𝐗`$ is a random point of $`F^n`$ with density $`\theta p`$. We thus establish the principal result of this paper:

Proof of Theorem 1.3 We can write:

$`D(p_{n,k,t}g_{k,c})`$ $`=`$ $`{\displaystyle \frac{q_{n,k}(𝐲,nt)}{w_n(nt)}\mathrm{log}\left(\frac{q_{n,k}(𝐲,nt)}{g_{k,c}(𝐲)w_{nk}(ntR_k(𝐲))}\right)𝑑𝐲}`$
$`+{\displaystyle p_{n,k,t}(𝐲)\mathrm{log}\left(\frac{w_{nk}(ntR_k(𝐲))}{w_n(nt)}\right)𝑑𝐲}.`$
Proposition 3.6 below deals with the first term. Lemmas 2.3 and 2.4 imply Proposition 2.1, providing a bound uniformly in $`z`$ on $`\mathrm{log}(w_{nk}(z)/w_n(nt))`$, so we can deal with the second term.

An analogue of the discrete log-sum inequality holds for integrals, and hence we deduce a projection inequality:

###### Proposition 3.6

Under the previous definitions:

$$\frac{q_{n,k}(𝐲,nt)}{w_n(nt)}\mathrm{log}\left(\frac{q_{n,k}(𝐲,nt)}{g_{k,c}(𝐲)w_{nk}(ntR_k(𝐲))}\right)𝑑𝐲D(ph_n).$$

Proof  Given integrable functions $`g(x),h(x)`$, normalising to get probability densities $`p(x)=g(x)/g(x)𝑑x`$, $`q(x)=h(x)/h(x)𝑑x`$, the Gibbs inequality gives:

$$0D(pq)g(x)𝑑x=g(x)\mathrm{log}\left(\frac{g(x)}{h(x)}\right)𝑑x\left(g(x)𝑑x\right)\mathrm{log}\left(\frac{g(x)𝑑x}{h(x)𝑑x}\right).$$

Now, writing $`𝐱=(𝐲,𝐮)`$, where $`𝐲^k`$, $`𝐮^{nk}`$, notice that:

$`q_{n,k}(𝐲,nt)`$ $`=`$ $`{\displaystyle (\theta p)(𝐲,𝐮)𝕀(R_k(𝐲)+R_{nk}(𝐮)=nt)𝑑𝐮}`$
$`g_{k,c}(𝐲)w_{nk}(ntR_k(𝐲))`$ $`=`$ $`{\displaystyle (\theta h_{n,t})(𝐲,𝐮)𝕀(R_k(𝐲)+R_{nk}(𝐮)=nt)𝑑𝐮}`$
Hence we deduce that for each $`𝐲`$:

$`{\displaystyle \frac{q_{n,k}(𝐲,nt)}{w_n(nt)}}\mathrm{log}\left({\displaystyle \frac{q_{n,k}(𝐲,nt)}{g_{k,c}(𝐲)w_{nk}(ntR_k(𝐲))}}\right)`$
$``$ $`{\displaystyle \frac{(\theta p)(𝐲,𝐮)}{w_n(nt)}\mathrm{log}\left(\frac{(\theta p)(𝐲,𝐮)}{(\theta h_{n,t})(𝐲,𝐮)}\right)𝕀(R_k(𝐲)+R_{nk}(𝐮)=nt)𝑑𝐮}`$
$`=`$ $`{\displaystyle p(S_n(𝐲,𝐮))\mathrm{log}\left(\frac{p(S_n(𝐲,𝐮))}{h_{n,t}(S_n(𝐲,𝐮))}\right)𝕀(R_k(𝐲)+R_{nk}(𝐮)=nt)𝑑𝐮}`$
Integrating with respect to $`𝐲`$, we obtain:

$`{\displaystyle \frac{q_{n,k}(𝐲,nt)}{w_n(nt)}\mathrm{log}\left(\frac{q_{n,k}(𝐲,nt)}{g_{k,c}(𝐲)w_{nk}(ntR_k(𝐲))}\right)𝑑𝐲}`$
$`=`$ $`{\displaystyle p(S_n(𝐲,𝐮))\mathrm{log}\left(\frac{p(S_n(𝐲,𝐮))}{h_{n,t}(S_n(𝐲,𝐮))}\right)𝕀(R_k(𝐲)+R_{nk}(𝐮)=nt)𝑑𝐮𝑑𝐲}`$
$`=`$ $`{\displaystyle p(S_n(𝐱))\mathrm{log}\left(\frac{p(S_n(𝐱))}{h_{n,t}(S_n(𝐱))}\right)𝕀(R_n(𝐱)=nt)𝑑𝐱}`$
$`=`$ $`D(ph_n),`$
as required.

###### Corollary 3.7

Assume $`f`$ and taking $`t=\epsilon (g_{1,c})`$, given the density $`p=h_{n,t}`$ on $`𝒮_n(t)`$, then the projection $`p_{n,k,t}`$ satisfies:

$$D(p_{n,k,t}g_{k,c})\mathrm{log}\left(\frac{n}{nk}\right)+\frac{2}{\sqrt{n}/C1}.$$

Observe that $`d_{TV}(f,g)=|f(x)g(x)|𝑑x\sqrt{2D(fg)}`$ (see ), and hence in this case then the rate of convergence in total variation distance is $`O(1/\sqrt{n})`$, as opposed to the $`O(1/n)`$ which Diaconis and Freedman establish. This difference can be attributed to the fact that we approximate the densities $`w_n`$, rather than being able to obtain exact bounds on them.

## 4 A converse

Given the density $`p=h_{n,t}`$ on $`𝒮_n(t)`$ we can see from Corollary 3.7 that as $`n\mathrm{}`$, and $`k/n0`$ then $`D(p_{n,k,t}g_{k,c})0`$. This is also Diaconis and Freedman’s  necessary and sufficient condition for convergence in total variation distance in the spherical case. We show that this condition holds for more surfaces than that:

###### Proposition 4.1

Given $`f`$, consider the uniform probability density $`h_{n,t}`$ on $`𝒮_n(t)`$, and consider $`p_{n,k,t}`$, the distribution of its first $`k`$ coordinates. If $`p_{n,k,t}g_{k,c}`$ in total variation distance then $`k/n0`$. Hence the stronger result of $`D(p_{n,k,t}g_{k,c})0`$ implies that $`k/n0`$.

Proof  Now considering $`𝐘`$ with density $`g_{n,c}`$, by conditioning and independence, the density $`r_k(y)`$ of $`(R_k(\pi _{n,k}𝐘)|R_n(𝐘)=nt)`$ satisfies:

$$r_k(y)=\frac{w_k(y)w_{nk}(nty)}{w_n(nt)}.$$

Hence since total variation distance is reduced by projection, we deduce that for any set $`L`$:

$$d_{TV}(p_{n,k,t},g_{k,c})d_{TV}(r_k,w_k)2_Lw_k(y)\left(\frac{w_{nk}(nty)}{w_n(nt)}1\right)𝑑y.$$

Now, using the estimates of the previous section, we know that choosing the interval $`L=(ktϵ\sqrt{nk},kt+ϵ\sqrt{nk})`$ will ensure that the term in brackets is close to $`\sqrt{n/nk}1`$. Furthermore for $`nk`$, $`w_k(L)`$ will be close to 1, so we deduce the result.

## Acknowledgements

I wish to thank Yuri Suhov and Geoffrey Grimmett for advice, assistance and support. This work was supported by an EPSRC grant, Award Reference Number 96000883, and EC Grant ‘Training Mobility and Research’ (Contract ERBMRXT-CT 960075A). I would also like to thank Professor Hans-Otto Georgii of LMU, München for useful discussions. Professors Joel Lebowitz and Eric Carlen also provided extremely helpful advice.


text:
# Lower Bounds for Matrix Product

## 1 Introduction

The problem of computing the product of two matrices is one of the most studied computational problems: We are given two $`n\times n`$ matrices $`x=(x_{i,j})`$, $`y=(y_{i,j})`$, and we wish to compute their product, i.e. there are $`n^2`$ outputs where the $`(i,j)`$’th output is

$$(xy)_{i,j}=\underset{k=1}{\overset{n}{}}x_{i,k}y_{k,j}.$$

In 69’ Strassen surprised the world by showing an upper bound of $`O(n^{\mathrm{log}_27})`$ . This bound was later improved and the best upper bound today is $`O(n^{2.376})`$  (see also  for a survey). The best lower bound is a lower bounds of $`2.5n^2o(n^2)`$, on the number of products needed to compute the function . Thus the following problem is still open: Can matrix product be computed by a circuit of size $`O(n^2)`$ ?

The standard computational model for computing polynomials is the model of arithmetic circuits, i.e. circuits over the base $`\{+,\}`$ over some field $`F`$. This is indeed the most general model, but for matrix product two other models are usually considered, quadratic circuits and bilinear circuits. In the quadratic model we require that product gates are applied only on two linear functions. In the bilinear model we also require that product gates are applied only on two linear functions, but in addition we require that the first linear function is linear in the variables of $`x`$ and that the second linear function is linear in the variables of $`y`$. These models are more restricted than the general model of arithmetic circuits. However it is interesting to note that over infinite fields we can always assume w.l.o.g. that any circuit for matrix product is a quadratic circuit . In addition we note that the best circuits that we have today for matrix product are bilinear circuits.

In this paper we prove that any quadratic circuit that computes matrix product over the field $`GF(2)`$ has at least $`3n^2o(n^2)`$ product gates, and that any bilinear circuit for matrix product over the field $`GF(p)`$ must have at least $`(2.5+\frac{1.5}{p^31})n^2o(n^2)`$ product gates.

From now on we will use the notation $`MP_n`$ to denote the problem of computing the product of two $`n\times n`$ matrices.

### 1.1 Known Lower Bounds

In contrast to the major advances in proving upper bound, the attempts to prove lower bounds on the size of bilinear circuits that compute $`MP_n`$ were less successful. Denote by $`q_{}(MP_n)`$ and $`bl_{}(MP_n)`$ the number of product gates in a smallest quadratic circuit for $`MP_n`$, and in a smallest bilinear circuit for $`MP_n`$ respectively. We also denote by $`bl_{tot}(MP_n)`$ the total number of gates in a smallest bilinear circuit for $`MP_n`$. In 78’ Brocket and Dobkin proved that $`bl_{}(MP_n)2n^21`$ over any field . This lower bound was later generalized by Lafon and Winograd to a lower bound on $`q_{}(MP_n)`$ over any field . In 89’ Bshouty showed that over $`GF(2)`$, $`q_{}(MP_n)2.5n^2O(n\mathrm{log}n)`$ . Recently Bläser proved a lower bound of $`2n^2+n3`$ on $`q_{}(MP_n)`$ over any field . In  Bläser proved that $`bl_{}(MP_n)2.5n^23n`$ over any field.

In  it is shown that any bounded depth circuit for $`MP_n`$, over any field, has a super linear (in $`n^2`$) size. Notice however, that the best known circuits for $`MP_n`$ have depth $`\mathrm{\Omega }(\mathrm{log}n)`$.

### 1.2 Bilinear Rank

An important notion that is highly related to the problem of computing matrix product in bilinear circuits is the notion of bilinear rank.

A bilinear form in two sets of variables $`x,y`$ is a polynomial in the variables of $`x`$ and the variables of $`y`$, which is linear in the variables of $`x`$ and linear in the variables of $`y`$. Clearly each output of $`MP_n`$ is a bilinear form in $`x=\{x_{i,j}\},y=\{y_{i,j}\}`$. The bilinear rank of a set of bilinear forms $`\{b_1(x,y),\mathrm{},b_m(x,y)\}`$ is the smallest number of rank 1 bilinear forms that span $`b_1,\mathrm{},b_m`$, where a rank 1 bilinear form is a product of a linear form in the $`x`$ variables and a linear form in the $`y`$ variables. We denote by $`R_F(b_1,\mathrm{},b_m)`$ the bilinear rank of $`\{b_1,\mathrm{},b_m\}`$ over the field $`F`$. For further background see .

We denote by $`R_F(MP_n)`$ the bilinear rank over $`F`$ of the $`n^2`$ outputs of matrix product, i.e. it is the bilinear rank of the set $`\{_{k=1}^nx_{i,k}y_{k,j}\}_{i,j}`$ over $`F`$.

The following inequalities are obvious (over any field).

* $`q_{}(MP_n)bl_{}(MP_n)2q_{}(MP_n)`$.
* $`R_F(MP_n)=bl_{}(MP_n)`$.
* The following inequality is less obvious, but also not so hard to see.

$$bl_{}(MP_n)bl_{tot}(MP_n)\mathrm{poly}(\mathrm{log}n)bl_{}(MP_n).$$

I.e. up to polylogarithmic factors, the number of product gates in a smallest bilinear circuit for $`MP_n`$, over any field $`F`$, is equal to the total number of gates in the circuit.

### 1.3 Results and Methods

We prove that any quadratic circuit that computes $`MP_n`$ over the field $`GF(2)`$ has at least $`3n^2o(n^2)`$ product gates (i.e. $`q_{}(MP_n)3n^2o(n^2)`$ over $`GF(2)`$). We also prove that over the field $`GF(p)`$ every bilinear circuit for $`MP_n`$ must have at least $`(2.5+\frac{1.5}{p^31})n^2o(n^2)`$ product gates (i.e. $`bl_{}(MP_n)(2.5+\frac{1.5}{p^31})n^2o(n^2)`$ over $`GF(p)`$). Both of these results actually hold for the bilinear rank as well.

The proof of the lower bound over $`GF(2)`$ is based on techniques from the theory of linear codes. However, we cannot use known results from coding theory in a straightforward way, since we are not dealing with codes in which every two words are distant, but rather with codes on matrices in which the distance between two code words, of two matrices, is proportional to the rank of the difference of the matrices. The reduction from circuits to codes and the proof of the bound are given in section 4.

The proof of the second bound is based on a lemma proved by Bläser in . We prove that in the case of finite fields we can use the lemma with better parameters than those used by Bläser. This result is proved in section 5.

### 1.4 Organization of the paper

In section 2 we present the models of bilinear circuits and quadratic circuits. In section 3 we present some algebraic and combinatorial tools that we need for the proofs of our lower bounds.

In section 4 we introduce the notion of linear codes of matrices, and prove our lower bound on bilinear and quadratic circuits that compute $`MP_n`$ over $`GF(2)`$. In section 5 we prove our lower bound on bilinear circuits that compute $`MP_n`$ over $`GF(p)`$.

## 2 Arithmetic Models

In this section we present the models of quadratic circuits and bilinear circuits. These are the models for which we prove our lower bounds. We first give the definition of a general arithmetic circuit. An arithmetic circuit over a field $`F`$ is a directed acyclic graph as follows. Nodes of in-degree 0 are called inputs and are labeled with input variables. Nodes of out-degree 0 are called outputs. Each edge is labeled with a constant from the field and each node other than an input is labeled with one of the following operations $`\{+,\}`$, in the first case the node is a plus gate and in the second case a product gate. The computation is done in the following way. An input just computes the value of the variable that labels it. Then, if $`v_1,\mathrm{},v_k`$ are the vertices that fan into $`v`$ then we multiply the result of each $`v_i`$ with the value of the edge that connects it to $`v`$. If $`v`$ is a plus gate we sum all the results, otherwise $`v`$ is a product gate and we multiply all the results. Obviously the value computed by each node in the circuit is a polynomial over $`F`$ in the input variables.

We are interested in the problem of computing the product of two $`n\times n`$ matrices, $`MP_n`$. The input consists of two $`n\times n`$ matrices $`x,y`$. The output is the matrix $`xy`$, i.e., there are $`n^2`$ outputs, and the $`(i,j)`$’th output is:

$$(xy)_{i,j}=\underset{k=1}{\overset{n}{}}x_{i,k}y_{k,j}.$$

Each output $`(xy)_{i,j}`$ is hence a bilinear form in $`x`$ and $`y`$.

Since each output of $`MP_n`$ is a bilinear form, it is natural to consider bilinear arithmetic circuits for it. A bilinear arithmetic circuit is an arithmetic circuit with the additional restriction that product gates are applied only on two linear functions, one function is linear in the variables of $`x`$ and the other function is linear in the variables of $`y`$. Thus, bilinear circuits have the following structure. First, there are many plus gates computing linear forms in $`x`$ and linear forms in $`y`$. Then there is one level of product gates that compute bilinear forms, and finally there are many plus gates that eventually compute the outputs. We will be interested in bounding from below the number of products in any bilinear circuit for $`MP_n`$. This model is more restricted than the general model of arithmetic circuits but we note that all the known upper bounds (over any field) for $`MP_n`$ are by bilinear circuits.

Another model that we will consider is the model of quadratic circuits. A quadratic circuit is an arithmetic circuit with the additional restriction that product gates are applied only on two linear functions. Notice that the only difference between quadratic circuits and bilinear circuits is that in the quadratic model the product gates compute quadratic forms in $`x,y`$, whereas in the bilinear model the product gates compute bilinear forms in $`x,y`$. This model is more general than the model of bilinear circuits, but it is still more restricted than the general model. However it is interesting to note that over infinite fields we can assume w.l.o.g. that any arithmetic circuit for $`MP_n`$ is a quadratic circuit .

## 3 Algebraic and Combinatorial tools

In this section we present some algebraic and combinatorial tools that we will use.

The following lemma is an extremely weak variant of the famous Schwartz-Zippel lemma which shows that every non zero polynomial (non zero as a formal expression) over a large enough field has a non zero assignment in the field (see ).

###### Lemma 1

Let $`P`$ be a polynomial of degree $`d`$ in $`x_1,\mathrm{},x_n`$ over some field $`F`$, such that $`d<|F|`$, and such that at least one of the coefficients of $`P`$ is not zero. Then we can find an assignment, $`\rho F^n`$, to the $`x_i`$’s, such that $`P(\rho _1,\mathrm{},\rho _n)0`$.

We say that two polynomials $`p,q`$ in $`n`$ variables are equivalent over a field $`F`$, if $`p(x_1,\mathrm{},x_n)=q(x_1,\mathrm{},x_n)`$ for any $`x_1,\mathrm{},x_nF`$. We denote $`pq`$ if $`p`$ and $`q`$ are equivalent over $`F`$ (we omit $`F`$ from the notation as the field that we deal with will be clear from the context).

###### Lemma 2

Let $`P`$ be a polynomial of degree $`d`$ in the variables $`x_1,\mathrm{},x_n`$ over a field $`F`$. If $`P0`$ then we can find an assignment, $`\rho F^n`$, to the $`x_i`$’s such that at most $`d`$ of the $`\rho _i`$’s get a nonzero value, and such that $`P(\rho _1,\mathrm{},\rho _n)0`$.

Proof: $`P`$ is equal (as a function) to a polynomial $`\overline{P}`$ in which the degree of each variable is at most $`|F|1`$. We call $`\overline{P}`$ the reduction of $`P`$. Consider some monomial $`M`$ in $`\overline{P}`$ whose coefficient is not zero. We assign all the variables that do not appear in $`M`$ to zero. The resulting polynomial (after the assignment), is a polynomial in the variables of $`M`$, which is not the zero polynomial as it is a reduced polynomial which has a monomial with a non zero coefficient ($`M`$ of course). Therefore according to lemma 1 there is some assignment to the variables of $`M`$, that gives this polynomial a nonzero value. Therefor we have found an assignment which gives nonzero values only to the variables of $`M`$ (and there are at most $`d`$ such variables) under which $`P0`$. $`\mathrm{}`$

The following useful lemma, which is a straightforward implication of the previous lemma, is the key lemma in most of our proofs. The lemma deals with linear forms in $`n^2`$ variables. From now on we shall think about such linear forms as linear forms in the entries of $`n\times n`$ matrices.

###### Lemma 3

Let $`\mu _1,\mathrm{},\mu _{n^2}`$ be $`n^2`$ linearly independent linear forms in $`n^2`$ variables over some field $`F`$. Let $`P`$ be a polynomial of degree $`d`$ in $`kn^2`$ variables over $`F`$, i.e. we can view $`P`$ as a polynomial $`P(x_1,\mathrm{},x_k)`$ in the entries of $`k`$ matrices, $`x_1,\mathrm{},x_k`$, of size $`n\times n`$ each. Assume that $`P0`$. Then we can find $`k`$ matrices $`a_1,\mathrm{},a_kM_n(F)`$ such that $`P(a_1,\mathrm{},a_k)0`$ and such that there exist $`n^2d`$ linear forms among $`\mu _1,\mathrm{},\mu _{n^2}`$’s that vanish on all the $`a_i`$’s.

Proof: The idea of the proof is the following. Let $`b_1,\mathrm{},b_{n^2}`$ be the dual basis of $`\mu _1,\mathrm{},\mu _{n^2}`$, i.e. it is a basis of $`M_n(F)`$ satisfying $`i,j\mu _i(b_j)=\delta _{i,j}`$. We wish to find $`k`$ matrices, $`a_1,\mathrm{},a_k`$, such that $`P(a_1,\mathrm{},a_k)0`$, and such that there exist $`b_{i_1},\mathrm{},b_{i_d}`$ that span all of them. If we manage to find such matrices, then since the $`b_i`$’s are the dual basis to the $`\mu _i`$’s we will get that $`n^2d`$ of the $`\mu _i`$’s vanish on $`a_1,\mathrm{},a_k`$. The way to find such matrices that are contained in the span of a small subset of the $`b_i`$’s, is based on lemma 2.

So let $`b_1,\mathrm{},b_{n^2}`$ be the dual basis to $`\mu _1,\mathrm{},\mu _{n^2}`$, i.e. $`i,j\mu _i(b_j)=\delta _{i,j}`$. We now change the variables of $`P`$. Let $`\alpha _{i,j}j=1\mathrm{}k,i=1\mathrm{}n^2`$, be a set of $`kn^2`$ variables. Denote $`x_j=_{i=1}^{n^2}\alpha _{i,j}b_i`$. Thus $`P(x_1,\mathrm{},x_k)`$ can be viewed as a polynomial of degree $`d`$ in the $`kn^2`$ variables $`\alpha _{i,j}`$. Therefore $`P0`$ as a polynomial in the $`\alpha _{i,j}`$’s. Hence, according to lemma 2 there exists an assignment, $`\rho `$, to the $`\alpha _{i,j}`$’s such that at most $`d`$ of them get a nonzero value. Define $`a_j=_{i=1}^{n^2}\rho _{i,j}b_i`$. Clearly $`P(a_1,\mathrm{},a_k)0`$. Since at most $`d`$ of the $`\rho _{i,j}`$’s got non zero values, we see that there are at most $`d`$ $`b_i`$’s such that all the $`a_j`$’s are linear combinations of them. Since the $`b_i`$’s are the dual basis to $`\mu _1,\mathrm{},\mu _{n^2}`$ we get that there are at least $`n^2d`$ of the $`\mu _i`$’s that vanish on all the $`a_j`$’s. Therefore $`a_1,\mathrm{},a_k`$ satisfy the requirements of the lemma. $`\mathrm{}`$

The next lemma will enable us to translate properties of matrices over large fields of characteristic $`p`$ to properties of matrices (of higher dimension) over $`GF(p)`$.

###### Lemma 4

There exist an embedding, $`\varphi :GF(p^n)M_n(GF(p))`$. That is there exist a mapping $`\varphi :GF(p^n)M_n(GF(p))`$ such that

* $`\varphi `$ is a one to one linear transformation.
* $`\varphi (1)=I`$, where $`I`$ is the $`n\times n`$ identity matrix.
* $`\varphi `$ is multiplicative, i.e. $`x,yGF(p^n)`$ we have that $`\varphi (xy)=\varphi (x)\varphi (y)`$.

This embedding also induces an embedding $`M_k(GF(p^n))M_{nk}(GF(p))`$.

This lemma is a standard tool in algebra, but for completeness we give the proof.

Proof: $`GF(p^n)`$ is an $`n`$ dimensional vector space over $`GF(p)`$. Each element $`xGF(p^n)`$ can be viewed as a linear transformation $`x:GF(p^n)GF(p^n)`$ in the following way:

$$yGF(p^n)x(y)=xy.$$

Clearly this is a linear transformation of $`GF(p^n)`$ into itself, as a vector space over $`GF(p)`$. Therefore, by picking a basis to $`GF(p^n)`$ we can represent the linear transformation corresponding to each $`xGF(p^n)`$ by a matrix $`a_xM_n(GF(p))`$. Thus, we have defined a mapping $`\varphi :GF(p^n)M_n(GF(p))`$ such that $`\varphi (x)=a_x`$, and it is easy to verify that this mapping is an embedding of $`GF(p^n)`$ into $`M_n(GF(p))`$. The way to generalize it to an embedding of $`M_k(GF(p^n))`$ into $`M_{nk}(GF(p))`$ is the following. Let $`a=(a_{i,j})M_k(GF(p^n))`$ be some matrix. Every entree of $`a_{i,j}`$ of $`a`$, is some element of $`GF(p^n)`$. We can now replace $`a_{i,j}`$ with the matrix $`\varphi (a_{i,j})`$. Thus the resulting matrix will be a $`kn\times kn`$ matrix whose entries are in $`GF(p)`$. Again it is easy to verify that this is indeed an embedding of $`M_k(GF(p^n))`$ into $`M_{nk}(GF(p))`$. $`\mathrm{}`$

In addition to the algebraic lemmas we also need the following combinatorial tools.

###### Definition 1

Let $`F`$ be a field, and let $`v,u`$ be two vectors in $`F^m`$. We denote by $`\mathrm{𝐰𝐞𝐢𝐠𝐡𝐭}(v)`$ the number of nonzero coordinates of $`v`$. Let $`𝐝_𝐇(v,u)=\mathrm{𝐰𝐞𝐢𝐠𝐡𝐭}(vu)`$, i.e. $`𝐝_𝐇(v,u)`$ is the number of coordinates on which $`u`$ and $`v`$ differ. $`𝐝_𝐇(v,u)`$ is also known as the Hamming distance of $`u`$ and $`v`$. We also denote by $`\mathrm{𝐚𝐠𝐫𝐞𝐞}(u,v)`$ the number of coordinates on which $`u`$ and $`v`$ are equal, i.e. $`\mathrm{𝐚𝐠𝐫𝐞𝐞}(u,v)=m𝐝_𝐇(v,u)`$.

The next lemma shows that if a vector space contains a set of vectors such that every pair/triplet of them don’t agree on many coordinates (i.e. their Hamming distance is large) then it is of large dimension. There are numerous similar lemmas in coding theory, and in particular the first part of our lemma is the famous Plotkin bound (see ).

###### Lemma 5

1. In every set of $`k`$ vectors in $`GF(p)^t`$, such that $`p<k`$, there are two vectors that agree on at least $`(\frac{t}{p}\frac{t}{k})`$ coordinates.
2. In every set of $`k`$ vectors in $`GF(p)^t`$, such that $`2p<k`$, there are three vectors that agree on at least $`(\frac{t}{p^2}\frac{3t}{pk})`$ coordinates.

Proof: We begin by proving the first claim. Let $`v_1,\mathrm{},v_k`$ be $`k`$ vectors in $`GF(p)^t`$. We are going to estimate $`_{i<j}\mathrm{𝐚𝐠𝐫𝐞𝐞}(v_i,v_j)`$ in two different ways. On the one hand this sum is at most $`\left(\genfrac{}{}{0pt}{}{k}{2}\right)`$ times the maximum of $`\mathrm{𝐚𝐠𝐫𝐞𝐞}(v_i,v_j)`$. On the other hand consider a certain coordinate. For every $`\alpha GF(P)`$ denote by $`n_\alpha `$ the number of vectors among the $`v_i`$’s that are equal to $`\alpha `$ on this coordinate. Clearly $`_{\alpha =0}^{p1}n_\alpha =k`$. The contribution of this coordinate to $`_{i<j}\mathrm{𝐚𝐠𝐫𝐞𝐞}(v_i,v_j)`$ is exactly $`_{\alpha =0}^{p1}\left(\genfrac{}{}{0pt}{}{n_\alpha }{2}\right)`$. By convexity

$$\underset{\alpha =0}{\overset{p1}{}}\left(\genfrac{}{}{0pt}{}{n_\alpha }{2}\right)p\frac{1}{2}\frac{k}{p}\left(\frac{k}{p}1\right)=\frac{k(kp)}{2p}.$$

We get that

$$\left(\genfrac{}{}{0pt}{}{k}{2}\right)\underset{i<j}{\mathrm{max}}(\mathrm{𝐚𝐠𝐫𝐞𝐞}(v_i,v_j))$$

$$\underset{i<j}{}\mathrm{𝐚𝐠𝐫𝐞𝐞}(v_i,v_j)t\frac{k(kp)}{2p}.$$

Therefore

$$\underset{i<j}{\mathrm{max}}(\mathrm{𝐚𝐠𝐫𝐞𝐞}(v_i,v_j))\frac{t}{p}\frac{kp}{k1}\frac{t}{p}\frac{kp}{k}=\frac{t}{p}\frac{t}{k}.$$

The proof of the second claim is similar. We give two different estimates to $`_{i<j<l}\mathrm{𝐚𝐠𝐫𝐞𝐞}(v_i,v_j,v_l)`$ (the number of coordinates on which $`v_i,v_j`$, and $`v_l`$ are the same). In the same manner as before we get that

$$\underset{i<j<l}{\mathrm{max}}(\mathrm{𝐚𝐠𝐫𝐞𝐞}(v_i,v_j,v_l))\frac{t}{p^2}\frac{kp}{k1}\frac{k2p}{k2}\frac{t}{p^2}\frac{3t}{pk}.$$

$`\mathrm{}`$

###### Corollary 1

If $`\{0,1\}^t`$ contains $`k`$ vectors $`v_1,\mathrm{},v_k`$, such that $`2<k`$ and $`ij𝐝_𝐇(v_i,v_j)N`$, then $`t2N4\frac{N}{k+2}`$.

Proof: According to lemma 5 there are two vectors, w.l.o.g. $`v_1`$ and $`v_2`$, such that $`\mathrm{𝐚𝐠𝐫𝐞𝐞}(v_1,v_2)\frac{t}{2}\frac{t}{k}`$. Since $`𝐝_𝐇(v_1,v_2)=t\mathrm{𝐚𝐠𝐫𝐞𝐞}(v_1,v_2)`$ we get that

$$t(\frac{t}{2}\frac{t}{k})𝐝_𝐇(v_1,v_2)N$$

and the result follows. $`\mathrm{}`$

## 4 Lower bound over GF(2)

In this section we prove our main theorems.

###### Theorem 1

$`bl_{}(MP_n)3n^2O(n^{\frac{5}{3}})`$ (in other words $`R_{GF(2)}(MP_n)3n^2O(n^{\frac{5}{3}})`$).

The second theorem that we shall prove is a lower bound for quadratic circuits.

###### Theorem 2

$`q_{}(MP_n)3n^2O(n^{\frac{5}{3}})`$. I.e. the number of product gates in any quadratic circuit that computes the product of two $`n\times n`$ matrices over $`GF(2)`$ is at least $`3n^2O(n^{\frac{5}{3}})`$.

Clearly theorem 2 imply theorem 1, but we first prove of theorem 1 as it is more intuitive and simple. We begin by introducing the notion of linear codes of matrices.

### 4.1 Linear Codes of Matrices

###### Definition 2

A linear code of matrices is a mapping,

$$\mathrm{\Gamma }:M_n(GF(2))\{0,1\}^m,$$

(for some $`m`$) with the following properties:

* $`\mathrm{\Gamma }`$ is linear.
* For any matrix $`a`$, $`\mathrm{𝐰𝐞𝐢𝐠𝐡𝐭}(\mathrm{\Gamma }(a))n\mathrm{rank}(a)`$.

From the linearity of $`\mathrm{\Gamma }`$ and the requirement on $`\mathrm{𝐰𝐞𝐢𝐠𝐡𝐭}(\mathrm{\Gamma }(a))`$ we get the following corollary.

###### Corollary 2

$`\mathrm{\Gamma }`$ is a one to one mapping, and for any two matrices $`a`$ and $`b`$, $`𝐝_𝐇(\mathrm{\Gamma }(a),\mathrm{\Gamma }(b))n\mathrm{rank}(ab)`$.

The following theorem shows that the dimension of the range of any linear code of matrices is large (i.e. $`m`$ must be large).

###### Theorem 3

Let $`\mathrm{\Gamma }:M_n(GF(2))\{0,1\}^m`$ be a linear code of matrices, then $`m3n^2O(n^{\frac{5}{3}}).`$

Proof: Denote

$$\mathrm{\Gamma }(a)=(\mu _1(a),\mathrm{},\mu _m(a)).$$

The proof is based on the following lemma that shows that we can find $`k=n^{\frac{1}{3}}`$ matrices, $`a_1,\mathrm{},a_kM_n(GF(2))`$, with the following properties.

* $`ij,a_ia_j`$ is an invertible matrix.
* There are $`n^2\left(\genfrac{}{}{0pt}{}{k}{2}\right)n`$ linear forms among the $`\mu _i`$’s that vanish on all the $`a_i`$’s.

We state the lemma for every $`k<2^n`$ but we apply it only to $`k=n^{\frac{1}{3}}`$.

###### Lemma 6

For every $`n,k`$ such that $`k<2^n`$, and any $`\mu _1,\mathrm{},\mu _{n^2}`$ linearly independent linear forms in $`n^2`$ variables, over $`GF(2)`$, there are $`k`$ matrices, $`a_1,\mathrm{},a_kM_n(GF(2))`$, such that for every $`ij`$, $`a_ia_j`$ is an invertible matrix, and such that $`n^2\left(\genfrac{}{}{0pt}{}{k}{2}\right)n`$ of the $`\mu _i`$’s vanish on them.

Proof: Consider the following polynomial $`P`$ in $`k`$ matrices:

$$P(a_1,\mathrm{},a_k)=\mathrm{determinant}\left(\underset{i<j}{}(a_ia_j)\right).$$

Clearly a set of $`k`$ matrices $`a_1,\mathrm{},a_k`$ satisfy $`P(a_1,\mathrm{},a_k)0`$ iff all the matrices $`a_ia_j`$ are invertible. In addition, it is easy to see that $`deg(P)=\left(\genfrac{}{}{0pt}{}{k}{2}\right)n`$. Therefore if we show that $`P0`$ over $`GF(2)`$, then according to lemma 3 we will get what we wanted to prove.

In order to show that $`P0`$ we just have to prove the existence of $`k`$ matrices, such that the difference of every two of them is invertible. Lemma 4 assures us that we can embed the field $`GF(2^n)`$ into $`M_n(GF(2))`$. Denote this embedding by $`\mathrm{\Phi }:GF(2^n)M_n(GF(2))`$. We take $`k`$ distinct elements in $`GF(2^n)`$, $`x_1,\mathrm{},x_k`$. Their images, $`\mathrm{\Phi }(x_1),\mathrm{},\mathrm{\Phi }(x_k)`$, are matrices in $`M_n(GF(2))`$ such that the difference of every two of them, $`\mathrm{\Phi }(x_i)\mathrm{\Phi }(x_j)=\mathrm{\Phi }(x_ix_j)`$, is an invertible matrix. This is because the $`x_i`$’s are distinct (i.e. $`x_ix_j0`$), and every nonzero element in $`GF(2^n)`$ is invertible. Thus, $`\mathrm{\Phi }(x_1),\mathrm{},\mathrm{\Phi }(x_k)`$ are exactly the $`k`$ matrices that we were looking for. This concludes the proof of the lemma. $`\mathrm{}`$

We proceed with the proof of the theorem. Let $`k=n^{\frac{1}{3}}`$. Since $`\mathrm{\Gamma }`$ is a one to one mapping, there are $`n^2`$ independent linear forms among $`\mu _1,\mathrm{},\mu _m`$. Therefore we can use lemma 6 and get that there are $`k`$ matrices $`a_1,\mathrm{},a_k`$ such that for every $`ij`$ $`a_ia_j`$ is invertible, and such that, w.l.o.g., $`\mu _{mr+1},\mathrm{},\mu _m`$ vanish on $`a_1,\mathrm{},a_k`$ for some $`rn^2\left(\genfrac{}{}{0pt}{}{k}{2}\right)nn^2n^{\frac{5}{3}}`$.

Since the last $`r`$ linear forms vanish on all the $`a_i`$’s, we are going to restrict our attention only to the first $`mr`$ linear forms. So from now on we only consider $`\mathrm{\Gamma }(a_i)`$ restricted to its first $`mr`$ coordinates.

Since each of the differences, $`a_ia_j`$ ($`ij`$), is an invertible matrix, we get that $`𝐝_𝐇(\mathrm{\Gamma }(a_i),\mathrm{\Gamma }(a_j))n^2`$. Thus, $`\mathrm{\Gamma }(a_1),\mathrm{},\mathrm{\Gamma }(a_k)`$ are $`k`$ vectors contained in $`\{0,1\}^{mr}`$ (we consider only their first $`mr`$ coordinates !) such that the hamming distance of every pair of them is at least $`n^2`$. Therefore according to corollary 1 we get that

$$mr2n^24\frac{n^2}{k+2}.$$

Since $`rn^2n^{\frac{5}{3}}`$ and $`k=n^{\frac{1}{3}}`$, we get that

$$m3n^2O(n^{\frac{5}{3}})$$

which is what we wanted to prove. This concludes the proof of the theorem. $`\mathrm{}`$

### 4.2 Proof of Theorem 1

Assume that $`bl_{}(MP_n)=m`$. Let $`C`$ be a smallest bilinear circuit for $`MP_n`$. Let

$$\mu _1(x)\eta _1(y),\mathrm{},\mu _m(x)\eta _m(y)$$

be the $`m`$ bilinear forms computed in the product gates of $`C`$. We will show that these bilinear forms define in a very natural way a code on $`M_n(GF(2))`$. The code thus defined, will have the property that the dimension of the space into which the code maps $`M_n(GF(2))`$ is exactly $`m`$. Thus, according to theorem 3 we will get that $`m3n^2O(n^{\frac{5}{3}})`$, which is what we wanted to prove.

So we begin by defining a mapping from $`M_n(GF(2))`$ to $`\{0,1\}^m`$. Let $`\mathrm{\Gamma }:M_n(GF(2))\{0,1\}^m`$ be the following mapping.

$$\mathrm{\Gamma }(x)=(\mu _1(x),\mathrm{},\mu _m(x)).$$

Notice that we ignore the $`\eta _i`$’s in the definition of $`\mathrm{\Gamma }`$. The next lemma shows that $`\mathrm{\Gamma }`$ is a linear code of matrices.

###### Lemma 7

$`\mathrm{\Gamma }`$ is a linear transformation with the property that for every matrix $`xM_n(GF(2))`$, $`\mathrm{𝐰𝐞𝐢𝐠𝐡𝐭}(\mathrm{\Gamma }(x))n\mathrm{rank}(x)`$.

Proof: Clearly $`\mathrm{\Gamma }`$ is a linear transformation from $`M_n(GF(2))`$ to $`\{0,1\}^m`$. So we only have to prove the claim about the weights. Let $`x`$ be a matrix of rank $`r`$. Assume w.l.o.g. that $`\mu _1(x)=\mathrm{}=\mu _k(x)=1`$ and that $`\mu _{k+1}(x)=\mathrm{}=\mu _m(x)=0`$, i.e. $`\mathrm{𝐰𝐞𝐢𝐠𝐡𝐭}(\mathrm{\Gamma }(x))=k`$. We shall show that $`knr`$. For every $`yM_n(GF(2))`$, the $`n^2`$ entries of $`xy`$ are functions of $`\mu _1(x)\eta _1(y),\mathrm{},\mu _m(x)\eta _m(y)`$. Since $`\mu _{k+1}(x)=\mathrm{}=\mu _m(x)=0`$, we get that $`xy`$ is a function of $`\eta _1(y),\mathrm{},\eta _k(y)`$. Therefore there are at most $`2^k`$ different matrices of the form $`xy`$. Since $`\mathrm{rank}(x)=r`$ we get that there are exactly $`2^{nr}`$ different matrices of the form $`xy`$. Therefore $`knr`$. This concludes the proof of the lemma. $`\mathrm{}`$

Therefore $`\mathrm{\Gamma }`$ is a linear code of matrices, so according to theorem 3 we get that $`m3n^2O(n^{\frac{5}{3}})`$ which is what we wanted to prove. This concludes the proof of theorem 1. $`\mathrm{}`$

### 4.3 Proof of Theorem 2

As in the proof of theorem 1 we will show that every quadratic circuit for $`MP_n`$, defines a code on $`M_n(GF(2))`$. The code thus defined, will have the property that $`m`$ (i.e the dimension of the space into which the code maps $`M_n(GF(2))`$) is exactly the number of product gates in the circuit. Thus, according to theorem 3 we will get that $`m3n^2O(n^{\frac{5}{3}})`$, which is what we wanted to prove.

Let $`C`$ be a quadratic circuit for $`MP_n`$. Assume that the product gates of $`C`$ compute the quadratic forms $`\mu _1(x,y)\eta _1(x,y),\mathrm{},\mu _m(x,y)\eta _m(x,y)`$. Thus, each of the outputs $`(xy)_{i,j}`$ can be written as a sum of these quadratic forms:

$$(xy)_{i,j}=\underset{k=1}{\overset{m}{}}\alpha _{i,j}^{(k)}\mu _k(x,y)\eta _k(x,y),$$

where $`\alpha _{i,j}^{(k)}\{0,1\}`$.

We would like to have a proof similar to the proof of theorem 1. In that proof we defined a code of matrices using the linear transformation $`\mu _1,\mathrm{},\mu _m`$. Unfortunately this method will fail here as $`\mu _i`$ is a linear function in both the variables of $`x`$ and the variables of $`y`$ and not just in the variables of $`x`$ as in the proof of theorem 1. In order to overcome this obstacle we introduce a new set of variables $`z=\{z_{i,j}\}_{i,j=1\mathrm{}n}`$. We think about $`z`$ as an $`n\times n`$ matrix. Define the following $`m`$ linear forms in $`z`$:

$$\gamma _k(z)=\underset{i,j}{}\alpha _{i,j}^{(k)}z_{i,j},k=1,\mathrm{},m.$$

We get that

$$\underset{k=1}{\overset{m}{}}\mu _k(x,y)\eta _k(x,y)\gamma _k(z)=$$

$$\underset{k=1}{\overset{m}{}}(\underset{i,j}{}z_{i,j}\alpha _{i,j}^{(k)})\mu _k(x,y)\eta _k(x,y)=$$

$$\underset{i,j}{}z_{i,j}\underset{k=1}{\overset{m}{}}\alpha _{i,j}^{(k)}\mu _k(x,y)\eta _k(x,y)=$$
(1)
$$\underset{i,j}{}z_{i,j}(xy)_{i,j}=\mathrm{𝐭𝐫𝐚𝐜𝐞}(xyz^t),$$

where $`(z^t)_{i,j}=z_{j,i}`$. The computation that we just performed shows that the $`\gamma _k`$’s that we introduced are quite natural. We also notice that $`z`$ plays the same role in $`\mathrm{𝐭𝐫𝐚𝐜𝐞}(xyz^t)`$ as $`x`$ and $`y`$. These observations motivate us to try to repeat the proof of theorem 1 using the $`\gamma _k`$’s instead of the $`\mu _i`$’s.

So define a linear mapping $`\mathrm{\Gamma }:M_n(GF(2))\{0,1\}^m`$ by

$$\mathrm{\Gamma }(z)=(\gamma _1(z),\mathrm{},\gamma _m(z)).$$

The following lemma shows that $`\mathrm{\Gamma }`$ is indeed a linear code of matrices.

###### Lemma 8

$`\mathrm{\Gamma }`$ is a linear mapping and it has the property that for every matrix $`z`$, $`\mathrm{𝐰𝐞𝐢𝐠𝐡𝐭}(\mathrm{\Gamma }(z))n\mathrm{rank}(z)`$.

Proof: Clearly $`\mathrm{\Gamma }`$ is a linear mapping. So we only have to prove the claim about the weights. Let $`z_0`$ be a matrix of rank r, and assume w.l.o.g. that $`\gamma _1(z_0)=\mathrm{}=\gamma _k(z_0)=1`$ and $`\gamma _{k+1}(z_0)=\mathrm{}=\gamma _m(z_0)=0`$. We wish to prove that $`knr`$. From equation 1 we get that

$$\mathrm{𝐭𝐫𝐚𝐜𝐞}(xyz_{0}^{}{}_{}{}^{t})=\underset{i=1}{\overset{k}{}}\mu _i(x,y)\eta _i(x,y).$$

We now consider the discrete derivatives of this equation. Let $`e_{i,j}`$ be the matrix of all zeros but 1 in the $`(i,j)`$’th place. Define

$$\frac{}{x_{i,j}}\mathrm{𝐭𝐫𝐚𝐜𝐞}(xyz_{0}^{}{}_{}{}^{t})\stackrel{\mathrm{def}}{=}$$

$$\mathrm{𝐭𝐫𝐚𝐜𝐞}((x+e_{i,j})yz_{0}^{}{}_{}{}^{t})\mathrm{𝐭𝐫𝐚𝐜𝐞}(xyz_{0}^{}{}_{}{}^{t}).$$

On the one hand

$$\mathrm{𝐭𝐫𝐚𝐜𝐞}((x+e_{i,j})yz_{0}^{}{}_{}{}^{t})\mathrm{𝐭𝐫𝐚𝐜𝐞}(xyz_{0}^{}{}_{}{}^{t})=$$

$$\mathrm{𝐭𝐫𝐚𝐜𝐞}(e_{i,j}yz_{0}^{}{}_{}{}^{t})=(z_0y^t)_{i,j}.$$

On the other hand we have that

$$\mathrm{𝐭𝐫𝐚𝐜𝐞}((x+e_{i,j})yz_{0}^{}{}_{}{}^{t})\mathrm{𝐭𝐫𝐚𝐜𝐞}(xyz_{0}^{}{}_{}{}^{t})=$$

$$\underset{i=1}{\overset{k}{}}(\mu _i(x+e_{i,j},y)\eta _i(x+e_{i,j},y)\mu _i(x,y)\eta _i(x,y))=$$

$$\underset{i=1}{\overset{k}{}}(\mu _i(e_{i,j},0)\eta _i(x,y)+\mu _i(x,y)\eta _i(e_{i,j},0))+$$
(2)
$$+\underset{i=1}{\overset{k}{}}\mu _i(e_{i,j},0)\eta _i(e_{i,j},0),$$

where the last equality follows from the linearity of the $`\mu _i`$’s and the $`\eta _i`$’s. Since $`(z_0y^t)_{i,j}`$ is a linear form in $`y`$, we actually get that

$$(z_0y^t)_{i,j}=\frac{}{x_{i,j}}\mathrm{𝐭𝐫𝐚𝐜𝐞}(xyz_{0}^{}{}_{}{}^{t})=$$

$$\underset{i=1}{\overset{k}{}}(\mu _i(e_{i,j},0)\eta _i(x,y)+\mu _i(x,y)\eta _i(e_{i,j},0))$$

$$\mathrm{span}(\mu _i(x,y),\eta _i(x,y))$$

(since $`(z_0y^t)_{i,j}`$ is a linear form the third summand of equation 2 sums to $`0`$). In the same manner we define

$$\frac{}{y_{i,j}}\mathrm{𝐭𝐫𝐚𝐜𝐞}(xyz_{0}^{}{}_{}{}^{t})\stackrel{\mathrm{def}}{=}$$

$$\mathrm{𝐭𝐫𝐚𝐜𝐞}(x(y+e_{i,j})z_{0}^{}{}_{}{}^{t})\mathrm{𝐭𝐫𝐚𝐜𝐞}(xyz_{0}^{}{}_{}{}^{t}).$$

We get that

$$(x^tz_0)_{i,j}=\frac{}{y_{i,j}}\mathrm{𝐭𝐫𝐚𝐜𝐞}(xyz_{0}^{}{}_{}{}^{t})=$$

$$\underset{i=1}{\overset{k}{}}(\mu _i(0,e_{i,j})\eta _i(x,y)+\mu _i(x,y)\eta _i(0,e_{i,j}))$$

$$\mathrm{span}(\mu _i(x,y),\eta _i(x,y)).$$

Denote by $`\mathrm{PD}`$ the set of all the discrete partial derivatives

$$\{\frac{}{x_{i,j}}\mathrm{𝐭𝐫𝐚𝐜𝐞}(xyz_{0}^{}{}_{}{}^{t}),\frac{}{y_{i,j}}\mathrm{𝐭𝐫𝐚𝐜𝐞}(xyz_{0}^{}{}_{}{}^{t})\}_{i,j}.$$

We just proved that $`\mathrm{PD}`$ is contained in the linear span of

$$\{\mu _i(x,y),\eta _i(x,y)\}_{i=1}^k,$$

in the vector space of all linear forms in $`x,y`$. Therefore

$$\mathrm{dim}(\mathrm{span}(\mathrm{PD}))$$

$$\mathrm{dim}(\mathrm{span}\{\mu _i(x,y),\eta _i(x,y)\}_{i=1}^k)2k.$$
(3)
We also showed that

$$\{\frac{}{x_{i,j}}\mathrm{𝐭𝐫𝐚𝐜𝐞}(xyz_{0}^{}{}_{}{}^{t}),\frac{}{y_{i,j}}\mathrm{𝐭𝐫𝐚𝐜𝐞}(xyz_{0}^{}{}_{}{}^{t})\}_{i,j}=$$

$$=\{(x^tz_0)_{i,j},(z_0y^t)_{i,j}\}_{i,j}.$$

Therefor, using our assumption that $`\mathrm{rank}(z_0)=r`$, we get that

$$\mathrm{dim}(\mathrm{span}(\mathrm{PD}))=$$

$$=\mathrm{dim}(\mathrm{span}\{(x^tz_0)_{i,j},(z_0y^t)_{i,j}\}_{i,j})=2nr.$$
(4)
Combining equations 3 and 4 we get that $`2k2nr`$. $`\mathrm{}`$

Theorem 2 now follows from applying theorem 3 on the linear code of matrices $`\mathrm{\Gamma }`$. $`\mathrm{}`$

## 5 Other Finite Fields

In this section we prove the following theorem.

###### Theorem 4

The number of product gates in any bilinear circuit that computes the product of two $`n\times n`$ matrices over $`GF(p)`$ is at least $`(2.5+\frac{1.5}{p^31})n^2O(n^{\frac{7}{4}})`$ (i.e. $`bl_{}(MP_n)(2.5+\frac{1.5}{p^31})n^2O(n^{\frac{7}{4}})`$ over $`GF(p)`$).

Let $`C`$ be a bilinear circuit for $`MP_n`$ over $`GF(p)`$. Assume that $`\mu _1(x)\eta _1(y),\mathrm{},\mu _m(x)\eta _m(y)`$ are the bilinear forms computed in the product gates of $`C`$. The following lemma of Bläser is the main tool in the proof of the theorem.

###### Lemma 9

 Let $`[a,b]=abba`$. If there are two matrices $`a,b`$ such that $`[a,b]`$ is an invertible matrix, and such that there are $`t`$ linear forms among $`\mu _1,\mathrm{},\mu _m`$ such that each of them vanish on $`I,a,b`$ then

$$mt+1.5n^2.$$

We are going to prove that we can find $`a,b`$ such that $`(1\frac{1}{p^3})n^2+\frac{m}{p^3}O(n^{\frac{7}{4}})`$ linear forms among $`\mu _1,\mathrm{},\mu _m`$ vanish on $`I,a,b`$ , and such that $`[a,b]`$ is invertible.

Proof of Theorem 4: We begin by proving that (w.l.o.g.) many of the $`\mu _i`$’s vanish on $`I`$. The following lemma shows that we can always find an invertible matrix such that many of the $`\mu _i`$’s vanish on it. As before we assume that $`\mu _1,\mathrm{},\mu _{n^2}`$ are independent linear forms.

###### Lemma 10

There exists an invertible matrix $`c`$, such that at least $`(1\frac{1}{p})n^2+\frac{m}{p}O(n^{\frac{5}{3}})`$ of the $`\mu _i`$’s vanish on it, where $`n^2O(n^{\frac{5}{3}})`$ of the $`\mu _i`$’s that vanish on it are among $`\mu _1,\mathrm{},\mu _{n^2}`$.

Proof: An analog of lemma 6 over $`GF(p)`$ guarantees that we can find $`k=n^{\frac{1}{3}}`$ matrices, $`a_1,\mathrm{},a_kM_n(GF(p))`$, such that for $`ij`$ $`a_ia_j`$ is invertible, and such that $`n^2\left(\genfrac{}{}{0pt}{}{k}{2}\right)n`$ linear forms among $`\mu _1,\mathrm{},\mu _{n^2}`$ vanish on all of them. Denote $`r=n^2\left(\genfrac{}{}{0pt}{}{k}{2}\right)n`$. And assume w.l.o.g. that $`\mu _1,\mathrm{},\mu _r`$ vanish on all the $`a_i`$’s.

Let us consider the following k vectors in $`GF(p)^{mr}`$:

$$\mathrm{\Gamma }(a_i)\stackrel{\mathrm{def}}{=}(\mu _{r+1}(a_i),\mathrm{},\mu _m(a_i)),i=1\mathrm{}k.$$

As in the proof of theorem 1, we get that since $`ija_ia_j`$ is an invertible matrix, then $`𝐝_𝐇(\mathrm{\Gamma }(a_i),\mathrm{\Gamma }(a_j))n^2`$. According to lemma 5, two of these vectors agree on at least $`\frac{mr}{p}\frac{mr}{k}`$ coordinates. Assume that $`\mathrm{\Gamma }(a_1)`$ and $`\mathrm{\Gamma }(a_2)`$ are these vectors. Denote $`c=a_1a_2`$. We have that $`c`$ is an invertible matrix, such that the first $`r=n^2\left(\genfrac{}{}{0pt}{}{k}{2}\right)n`$ linear forms (which are independent) vanish on it, and such that all the linear forms that $`\mathrm{\Gamma }(a_1)`$ and $`\mathrm{\Gamma }(a_2)`$ agree on, vanish on it as well. Therefore there are at least

$$r+\frac{mr}{p}\frac{mr}{k}$$

linear forms that vanish on $`c`$. Since $`r=n^2\left(\genfrac{}{}{0pt}{}{k}{2}\right)n`$, and $`k=n^{\frac{1}{3}}`$, we get that at least

$$(1\frac{1}{p})n^2+\frac{m}{p}O(n^{\frac{5}{3}})$$

linear forms vanish on $`c`$, $`n^2O(n^{\frac{5}{3}})`$ of them are among $`\mu _1,\mathrm{},\mu _{n^2}`$ (we assume for simplicity that $`n^2<m<10n^2`$, as it will not change the results). This completes the proof of the lemma. $`\mathrm{}`$

The lemma doesn’t tell us who $`c`$ is, but using the sandwiching method we can assume that $`c=I`$: We know that $`xy`$ is computed using the bilinear forms

$$\mu _1(x)\eta _1(y),\mathrm{},\mu _m(x)\eta _m(y).$$

We now do the following trick: $`xy=(xc)(c^1y)`$, therefore $`xy`$ can be computed using the bilinear forms

$$\stackrel{~}{\mu _1}(x)\stackrel{~}{\eta _1}(y),\mathrm{},\stackrel{~}{\mu _m}(x)\stackrel{~}{\eta _m}(y),$$

where

$$\stackrel{~}{\mu _i}(x)\stackrel{\mathrm{def}}{=}\mu _i(xc)\mathrm{and}\stackrel{~}{\eta _i}(y)\stackrel{\mathrm{def}}{=}\eta _i(c^1y).$$

Thus, if $`\mu _i(c)=0`$ then we get that $`\stackrel{~}{\mu _i}(I)=\mu _i(Ic)=0`$. This trick is called sandwiching, for further background see .

So by combining the sandwiching method and lemma 10 we get that we can assume w.l.o.g. that $`(1\frac{1}{p})n^2+\frac{m}{p}O(n^{\frac{5}{3}})`$ of the $`\mu _i`$’s, where $`n^2O(n^{\frac{5}{3}})`$ of them are among $`\mu _1,\mathrm{},\mu _{n^2}`$, vanish on $`I`$. The next lemma now assures us that we can find two matrices $`a,b`$ that satisfy the requirements of lemma 9.

###### Lemma 11

There are two matrices $`a,b`$ such that $`[a,b]`$ is an invertible matrix and such that at least $`(1\frac{1}{p^3})n^2+\frac{m}{p^3}O(n^{\frac{7}{4}})`$ of the $`\mu _i`$’s vanish on $`I,a,b`$.

Proof: The proof of this lemma is similar to the proof of lemma 10. Let $`k=n^{\frac{1}{4}}`$. The following lemma shows that we can find $`k`$ matrices such that many of the $`\mu _i`$’s vanish on all of them and such that among their differences there are matrices satisfying the requirements of lemma 9.

###### Lemma 12

For every $`n,k`$, such that $`p^{\frac{n}{2}}>4\left(\genfrac{}{}{0pt}{}{k}{3}\right)`$, and any $`\mu _1,\mathrm{},\mu _{n^2}`$ linearly independent linear forms, in $`n^2`$ variables, over $`GF(p)`$, there are $`k`$ matrices, $`a_1,\mathrm{},a_k`$, such that $`i<j<l`$, $`[a_ia_l,a_ja_l]`$ is invertible, and such that $`n^22\left(\genfrac{}{}{0pt}{}{k}{3}\right)n`$ of the $`\mu _i`$’s vanish on all the $`a_i`$’s.

Proof: Again we use lemma 3. Let $`P`$ be the following polynomial.

$$P(a_1,\mathrm{},a_k)=\mathrm{determinant}\left(\underset{i<j<l}{}[a_ia_l,a_ja_l]\right).$$

Clearly $`deg(P)=2\left(\genfrac{}{}{0pt}{}{k}{3}\right)n`$ (as a polynomial in the entries of the $`a_i`$’s). Therefore if we will prove that $`P0`$, i.e. that there exist $`k`$ matrices on which $`P`$ is not zero, then according to lemma 3 we are done. This is guaranteed by the following lemma.

###### Lemma 13

If $`p^{\frac{n}{2}}>4\left(\genfrac{}{}{0pt}{}{k}{3}\right)`$ then there exist $`k`$ matrices in $`M_n(GF(p))`$, $`a_1,\mathrm{},a_k`$ such that $`i<j<l`$, $`[a_ia_l,a_ja_l]`$ is invertible.

We prove the lemma only for $`n`$ even. Clearly this will not affect theorem 4, as the lower bound for odd $`n`$ follows from the lower bound for even $`n`$.

Proof: Consider the following polynomial in $`\mathrm{𝟒}𝐤`$ variables (i.e. it is a polynomial in $`k`$ matrices over $`𝐌_\mathrm{𝟐}(\mathrm{𝐆𝐅}(𝐩))`$! ).

$$Q(x_1,\mathrm{},x_k)=\mathrm{determinant}\left(\underset{i<j<l}{}[a_ia_l,a_ja_l]\right).$$

$`Q`$ is a polynomial of degree $`d=4\left(\genfrac{}{}{0pt}{}{k}{3}\right)`$ over $`GF(p)`$, in the entries of the $`a_i`$’s. Clearly $`Q`$ is not the zero polynomial (as it is a product of non zero polynomials). Consider the field $`F=GF(p^{\frac{n}{2}})`$. Since $`d<|F|`$ we get by lemma 1 that there are $`k`$ matrices $`\rho _1,\mathrm{},\rho _kM_2(F)`$ such that $`Q(\rho _1,\mathrm{},\rho _k)0`$. That is, $`i<j<l[\rho _i\rho _l,\rho _j\rho _l]`$ is an invertible matrix. According to lemma 4 we can embed $`M_2(F)`$ in $`M_n(GF(p))`$. Therefore there are $`k`$ matrices in $`M_n(GF(p))`$ satisfying $`i<j<l[a_ia_l,a_ja_l]`$ is an invertible matrix, which is what we wanted to prove. $`\mathrm{}`$

This concludes the proof of lemma 12. $`\mathrm{}`$

We proceed with the proof of lemma 11. We now restrict our attention to the linear forms among $`\mu _{n^2+1},\mathrm{},\mu _m`$ that vanish on $`I`$. We shall prove that three of the matrices guaranteed by lemma 12 agree on many of these linear forms (more formally on $`\frac{mn^2}{p^3}O(n^{\frac{7}{4}})`$ of them). Thus, if $`a_1,a_2,a_3`$ are these three matrices, then we get that $`(1\frac{1}{p^3})n^2+\frac{m}{p^3}O(n^{\frac{7}{4}})`$ linear forms vanish on $`I,(a_1a_3),(a_2a_3)`$, and that $`[(a_1a_3),(a_2a_3)]`$ is an invertible matrix, which is what we wanted to prove.

So assume w.l.o.g. that the linear forms $`\mu _{n^2+1},\mathrm{},\mu _{n^2+r},`$ vanish on $`I`$ (beside those among $`\mu _1,\mathrm{},\mu _{n^2}`$ that vanish on it) where $`r\frac{mn^2}{p}O(n^{\frac{5}{3}})`$. Let $`a_1,\mathrm{},a_k`$ be the matrices guaranteed by lemma 12. Consider the following vectors: $`1ik,`$

$$v_i=(\mu _{n^2+1}(a_i),\mathrm{},\mu _{n^2+r}(a_i))GF(p)^r.$$

According to lemma 5 three of these vectors, namely $`v_1,v_2,v_3`$, agree on at least $`\frac{r}{p^2}\frac{3r}{pk}`$ coordinates. Therefore there are $`\frac{r}{p^2}\frac{3r}{pk}`$ linear forms among $`\mu _{n^2+1},\mathrm{},\mu _{n^2+r}`$ that vanish on $`a_1a_3`$ and $`a_2a_3`$. In addition there are $`n^22\left(\genfrac{}{}{0pt}{}{k}{3}\right)n`$ linear forms among $`\mu _1,\mathrm{},\mu _{n^2}`$ that vanish on $`a_1,a_2,a_3`$, hence there are $`n^22\left(\genfrac{}{}{0pt}{}{k}{3}\right)n`$ linear forms among $`\mu _1,\mathrm{},\mu _{n^2}`$ that vanish on $`a_1a_3`$ and on $`a_2a_3`$. Let $`a=a_1a_3,b=a_2a_3`$.

We get that there are $`\frac{r}{p^2}\frac{3r}{pk}`$ linear forms among $`\mu _{n^2+1},\mathrm{},\mu _{n^2+r}`$ that vanish on $`I,a,b`$. Since $`n^2O(n^{\frac{5}{3}})`$ of the first $`n^2`$ $`\mu _i`$’s vanish on $`I`$, we get that at least $`n^22\left(\genfrac{}{}{0pt}{}{k}{3}\right)nO(n^{\frac{5}{3}})`$ of the first $`n^2`$ $`\mu _i`$’s vanish on $`I,a,b`$. Putting it all together we get that at least

$$n^22\left(\genfrac{}{}{0pt}{}{k}{3}\right)nO(n^{\frac{5}{3}})+\frac{r}{p^2}\frac{3r}{pk}$$

linear forms among $`\mu _1,\mathrm{},\mu _m`$ vanish on $`I,a,b`$. Since $`r=\frac{mn^2}{p}O(n^{\frac{5}{3}})`$, and $`k=n^{\frac{1}{4}}`$, we get that at least

$$(1\frac{1}{p^3})n^2+\frac{m}{p^3}O(n^{\frac{7}{4}})$$

of the $`\mu _i`$’s vanish on them. This concludes the proof of lemma 11. $`\mathrm{}`$

Putting everything together we get by lemma 9 and lemma 11 that:

$$m1.5n^2+(1\frac{1}{p^3})n^2+\frac{m}{p^3}O(n^{\frac{7}{4}}).$$

Therefore

$$m(2.5+\frac{1.5}{p^31})n^2O(n^{\frac{7}{4}}).$$

This concludes the proof of theorem 4. $`\mathrm{}`$

## 6 Acknowledgment

I would like to thank Michael Ben-Or and Avi Wigderson for helpful conversations. I would also like to thank Ran Raz for commenting on an earlier draft of the paper (in his words: Would you like to hear my comments or do you just want to rewrite everything).