A Multivariate to Bivariate Reduction for Noncommutative Rank and Related Results
Vikraman Arvind Pushkar S Joglekar


[
    Zuyi Wang
    April 29, 2024
==================




  We study the noncommutative rank problem, , of
  computing the rank of matrices with linear entries in n
  noncommuting variables and the problem of noncommutative
    Rational Identity Testing, , which is to decide if a given
  rational formula in n noncommuting variables is zero on its domain
  of definition.

  Motivated by the question whether these problems have
  deterministic  algorithms, we revisit their
  interrelationship from a parallel complexity point of view.
  We show the following results:
  
  
  * Based on Cohn's embedding theorem <cit.>
    we show deterministic  reductions from multivariate
     to bivariate  and from multivariate 
    to bivariate .
  
  * We obtain a deterministic -Turing reduction from
    bivariate  to bivariate , thereby proving that
    a deterministic  algorithm for bivariate 
    would imply that both multivariate  and multivariate
     are in deterministic .
 

 

  Given a rational formula computing an element of the free skew field
   the Rational Identity Testing problem () is to
  decide if the given formula agrees on its domain of definition with
  the zero element of . The problem has a deterministic
  polynomial-time algorithm <cit.> and a randomized 
  algorithm, based on a reduction from  to the
  noncommutative rank problem of matrices with linear entries
  in the noncommuting variables X.
  
  In this note we give a deterministic NC reduction from
  multivariate to bivariate case for the noncommutative rank problem
  and hence for the  problem.  Our reduction is based on Cohn's
  embedding theorem <cit.> and Higman
  linearization.

  




§ INTRODUCTION


There are two main algorithmic problems of interest in this
paper. These are the noncommutative Rational Identity Testing
  problem () and the noncommutative rank ()
problem for matrices with linear entries.

The  problem is a generalization of multivariate polynomial
identity testing to identity testing of multivariate rational
expressions. When the variables are commuting, rational identity
testing and polynomial identity testing are equivalent problems. On
the other hand, if the variables are all noncommuting, the 
problem needs different algorithmic techniques as rational expressions
in noncommuting variables are more complicated. Mathematically,
rational expressions over noncommuting variables are quite well
studied.  They arise in the construction of the so-called free skew
fields <cit.>. Hrubes and Wigderson <cit.> initiated the
algorithmic study of  for rational
  formulas and gave a deterministic polynomial time reduction from  to . Subsequently, deterministic polynomial-time algorithms
were obtained independently by Ivanyos et al <cit.> and by
Garg et al <cit.> for the  problem, in fact they obtain deterministic polynomial time algorithms for , and using Hrubes-Wigderson reduction from  to  get a polynomial time algorithm for . The Ivanyos et al algorithm is algebraic and works for
fields of all characteristics. The Garg et al algorithm has an
analytic flavor and is for the characteristic zero case.



  
The Edmonds' Problem and  


The  problem is essentially the noncommutative version of the
well-known Edmonds' problem: determine the rank of a matrix M whose
entries are linear forms in commuting variables (see
<cit.> for more details). A special case of it
is to determine if a square matrix M with linear entries in
commuting variables is singular. This is also known as the
symbolic determinant identity testing problem, . There is an
easy randomized  algorithm for it, based on the Polynomial
Identity Lemma <cit.>, by randomly
substituting scalar values for the variables from the field (or a
suitable extension of it) and evaluating the determinant using a
standard  algorithm.  However, a deterministic polynomial-time
algorithm for  is an outstanding open problem <cit.>.

Recently, for the  problem the first deterministic quasi-
algorithm has been obtained <cit.>. Another recent development
— building on the connection between the noncommutative Edmonds'
problem and identity testing for noncommutative algebraic branching
programs <cit.> — is a generalization of the Edmond's problem
to a partially commutative setting with application to the weighted
k-tape automata equivalence problem <cit.>.



 §.§ This paper: overview of results and proofs


With this background, the natural algorithmic questions are whether
 for noncommutative rational formulas and  have
deterministic  algorithms. We revisit the problems from this
perspective and obtain the following new results.











  1.  We show that multivariate  for formulas is
  deterministic  reducible to bivariate  for formulas. More
  precisely, given a rational formula Φ(x_1,x_2,…,x_n),
  computing an element of the skew field , where
  X={x_1,x_2,…,x_n}, the deterministic NC reduction replaces
  each x_i by a formula Φ_i(x,y) computing a polynomial in
  ∠x,y. Then the resulting rational formula
  
    Ψ(x,y) = Φ(Φ_1(x,y),Φ_2(x,y),…,Φ_n(x,y))

  has the property that
  
    Φ(x_1,x_2,…,x_n) 0  iff Ψ(x,y) 0.



  2.  We next show that multivariate  is deterministic
   reducible to bivariate . More precisely, given a
  d× d linear matrix A=A_0+∑_i=1^n A_i x_i in
  noncommuting variables X={x_1,x_2,…,x_n}, where the A_i
  are matrices over the scalar field , we first give a
  deterministic NC reduction that transforms A to a d× d matrix B
  whose entries are bivariate polynomials in ∠x,y, where
  x and y are two noncommuting variables, where its entries
  B[i,j] are given by polynomial size noncommutative
    formulas, with the property that (A)=(B). Then we
  examine the Higman linearization process <cit.> that transforms
  B into a matrix B' with linear entries in x and y such that
  the noncommutative rank (B) of B can be easily recovered
  from (B'). We show that this process can be implemented in
  deterministic  (the earlier works
  <cit.> only consider its polynomial-time
  computability).

  
  
  
  
  
  Additionally, we consider the more general problem  of
  computing the noncommutative rank of a matrix whose entries are
  noncommutative formulas computing polynomials. We show using our
  parallel Higman linearization algorithm that  is also
  deterministic  reducible to bivariate .

  Both the multivariate to bivariate reductions, stated above, are
  crucially based on a theorem of Cohn <cit.> (also see 
  <cit.>) which we will refer to as Cohn's 
  embedding theorem and describe it later in the introduction.


  3.  Finally, obtaining a deterministic  reduction from
   to  turns out to be quite subtle. From the work of
  Hrubes and Wigderson <cit.>, who initiated this line of
  research on , we can only obtain a sequential deterministic
  polynomial-time reduction from  to . However, for
  our result we require an  reduction. If the given rational
  formula has logarithmic depth, then their result already implies an
   reduction.

  Now, in the same paper <cit.>, Hrubes and Wigderson have also
  shown a depth reduction result for multivariate
  noncommutative rational formulas: every rational formulas of size
  s is equivalent to a logarithmic depth rational formula of size
  (s). Their construction is based on Brent's depth reduction
  result for commutative arithmetic formulas. 
  
  
  
 
 
  However, due to noncommutativity and the presence of inversion
  gates, the formula constructed in their proof needs to be different
  based on whether certain rational subformulas, arising in the
  construction procedure, are identically zero or not. To algorithmize
  such steps in the construction we need to use  as a
  subroutine. As  has a
  polynomial-time algorithm <cit.>, the depth-reduction
  in <cit.> also has a polynomial time algorithm.[In the
    commutative case, Brent's result is parallelizable to yield an
     algorithm. For noncommutative formulas without inversion
    gates we can obtain the depth-reduced formula in , as we will
    observe later in the paper.]

  As the third result of this paper, building on the Hrubes-Wigderson
  depth-reduction construction, we are able to show that, with oracle
  access to , rational formula depth reduction can be done in
  deterministic . Using this we are able to obtain a
  deterministic -Turing reduction from  to .
  Hence, if bivariate  is in deterministic  we will
  obtain a deterministic  algorithm also for . We leave
  open the question whether depth reduction of noncommutative rational
  formulas is unconditionally in .

 
 


 
 
 



We now outline the proof ideas in more detail with some intuitive
explanations.



§ PRELIMINARIES


In this section we recall the essential basic definitions and fix the
notation.

Let  be a (commutative) field[In this paper,  will
either be the field of rationals or a finite field.] and
X={x_1,x_2,…,x_n} be n free noncommuting variables. The
free monoid X^* is the set of all monomials in the variables X. A
noncommutative polynomial f(X) is a finite -linear
combination of monomials in X^*, and the free noncommutative
ring  consists of all noncommutative polynomials.



  
Noncommutative Rational Formulas An arithmetic
  circuit computing an element of  is a directed acyclic graph
with each indegree 0 node labeled by either an input variable
x_i∈ X or some scalar c∈. Each internal node g has
indegree 2 and is either a + gate or a × gate: it computes
the sum (resp. left to right product) of its inputs. Thus, each gate
of the circuit computes a polynomial in  and the polynomial
computed by the circuit is the polynomial computed at the output
  gate. A formula is restricted to have fanout 1 or 0.

When we allow the formulas/circuits to have inversion gates we
get rational formulas and rational circuits.








  
The Free Skew Field

We now briefly explain the free skew field construction. 
The elements of the free skew field are noncommutative rational
functions which are more complicated than their commutative
counterparts. Rational formulas in the commutative setting can be
canonically expressed as ratios of two polynomials.  There is no such
canonical representation for noncommutative rational
formulas.

Following
Hrubes-Wigderson <cit.>, we use Amitsur's approach <cit.>
for formally defining skew fields.[There are other ways to defining free
skew fields <cit.>.]

 




It involves defining appropriate notion of equivalence of formulas (intuitively, two formulas are equivalent if they agree on their domain of definition). The equivalence classes under this equivalence relation are the elements of the free skew field. We give the formal definitions below.









Let _k() denote the ring of k× k matrices
with entries from field . Note that a rational formula Φ
defines a partial function

    Φ̂:_k()^n ↦_k()

that on input (a_1, a_2, …, a_n)∈_k()^n evaluates Φ
by substituting x_i ← a_i for i∈ [n].
Φ̂(a_1, …, a_n) is undefined if the input to some
inversion gate in Φ is not invertible in _k().


  Let Φ be a rational formula in variables X. For each
  k∈, let 𝒟_k,Φ be the set of all matrix tuples
  (a_1, a_2, …, a_n)∈_k()^n such that Φ̂(a_1,
  a_2, …, a_n) is defined. The domain of definition of
  Φ is the union 𝒟_Φ=⋃_k 𝒟_k,Φ.


<cit.> 


  * A rational formula Φ is called correct if for every
  gate u of Φ the subformula Φ_u has a nonempty domain of
  definition.

  * Correct rational formulas Φ_1,Φ_2 are said to be
  equivalent (denoted Φ_1 ≡Φ_2) if the
  intersection 𝒟_Φ_1∩𝒟_Φ_2 of their
  domains of definitions is nonempty and they agree on all the points
  in the intersection.



  






We note that equivalent formulas need not have the same domain of
definition. For example, Φ_1 = z_1z_2z_3 and Φ_2=(z_1z_2z_3
· (z_2z_3 - z_3z_2)^-1)· (z_2z_3 - z_3z_2) are
equivalent. However, the domain of definition of Φ_1 includes all
matrix tuples, whereas the domain of definition of Φ_2 contains
only matrix tuples (Z_1,Z_2, Z_3) such that Det(Z_2 Z_3 - Z_3 Z_2)
≠ 0.



The relation ≡ as defined above is an equivalence relation on
rational formulas and the equivalence classes, called rational
functions, are the elements of the skew field  <cit.>.



  
Noncommutative Rank

We now recall the notion of rank for matrices over the noncommutative
ring . 


  Let M be a matrix over . Its inner rank is the least
  r such that M can be written as a matrix product M=PQ where
  Q has r rows (and P has r columns).



  An n× n square matrix M over  is full if it
  cannot be decomposed as a matrix product M=PQ where P is
  n× r and Q is r× n for r<n. In other words, an
  n× n matrix is called full precisely when its inner rank is
  n.


We can also define the rank of a matrix M to be the maximum r such
that M contains an r× r full submatrix. For matrices over
 these notions of noncommutative rank coincide as
summarized below.[For a ring R in general, a full matrix
  R need not be invertible (see <cit.> for an example).]

<cit.> 
  
  Let M be an n× n matrix over the ring . Then
  
  
  * M is a full matrix (that is, M has inner rank n) iff it is invertible over the skew field
    .
  
  * More generally, M has inner rank r iff the largest full
    submatrix of M is r× r.
  




  
The Algorithmic Problems of Interest




At this point we formally define the problems of interest in
this paper.


  * The multivariate  problem takes as input a rational
  formula Φ, computing a rational function Φ̂ in ,
  and the problem is to check if Φ is equivalent to 0?
    In the bivariate  problem Φ computes 
  a rational function in .








  * The multivariate  problem takes as input a matrix
  M with affine linear form entries over X and the problem is
  to determine its noncommutative rank (M). Bivariate 
  is similarly defined.

  * A more general version of  is  in which the
  matrix entries are allowed to be polynomials in  computed by
  noncommutative formulas. A closely related problem is  where
  the problem is to test if a square matrix M over  with
  entries computed by formulas is singular or not.




  
The complexity class  and  reductions
The class  consists of decision problems that can be
solved in (n) time with (n) many processors.[
This model is widely accepted as the right theoretical notion for efficient
parallel algorithms.] For two decision problems A and B
we say A is many-one  reducible to B if there is
a reduction from A to B that is  computable. Similarly,
A is -Turing reducible to B if there is an oracle
 algorithm for A that has oracle access to B.










  
  It turns out that  and  are equivalent even under
  deterministic  reductions. [As for M ∈^m× n, (M)=r iff r is a size of a largest sized invertible minor of M, so to compute (M), it suffices to test singularity of matrix UMV, where U,V are generic r× m, n × r matrices respectively with entries as fresh noncommuting variables for r≤min(m,n). See e.g. <cit.> for details.]




  
Cohn's Embedding Theorem




We now give an outline of Cohn's embedding theorem and how
it gives us the desired reduction from multivariate to
bivariate  and also from multivariate to bivariate
. However, for multivariate to bivariate reduction for  we 
will require additional  algorithms for formula depth reduction and Higman linearization. 

Let X={x_1, x_2,…,x_n} be a set of n noncommuting variables, and let
x, y be a pair of noncommuting variables. We first recall the
following well-known fact, observed in the early papers on
noncommutative polynomial identity testing <cit.>: for
noncommutative polynomials in , the problem of  polynomial identity
testing (PIT) is easily reducible to PIT for bivariate noncommutative
polynomials in ∠x,y. Indeed, more formally, we have the
following easy to check fact.


The map

    x_i↦ x^i-1y, 1≤ i≤ n

extends to an injective homomorphism (i.e. a homomorphic
  embedding) from the ring  to the ring ∠x,y.


However, in order to obtain our multivariate to bivariate reductions,
we need a mapping β:X→∠x,y which has the following
properties:
  
  
  * For each i, there is a small noncommutative
    arithmetic formula that computes β(x_i).
  
  * β extends to an injective homomorphism[That is,
      a homomorphic embedding.], not just from the ring  to
    ∠x,y, but also to an injective homomorphism from the
    skew field  to the skew field . This will guarantee
    that for two rational formulas Φ_1,Φ_2 computing
    inequivalent rational functions in  their images
    β(Φ_1) and β(Φ_2) also compute inequivalent
    rational functions in ∠x,y. 
  
  * Furthermore, in order to get the multivariate to bivariate
    reduction for , we will additionally require of the map
    β that for any matrix M over  its image β(M),
    which is a matrix over ∠x,y obtained by applying
    β to each entry of M, has the same rank as M. Such a
    homomorphic embedding is called an honest embedding
    <cit.>. Here we note that, full matrices over  are invertible over  <cit.>. Consequently if one can lift embedding β to one between the corresponding free skew fields, it enforces β to be an honest embedding.  
  

  The mapping x_i↦ x^i-1y actually does not extend to an
  honest embedding as observed in <cit.>. Indeed, the rank 2
  matrix (
[ x_1 x_2; x_3 x_4 ])
has image

    (
    [    y   xy; x^2y x^3y ])=([   1; x^2 ])
    ([  y xy ])

which is rank 1. In general, a homomorphic embedding from a ring R
to a ring R' is an honest embedding if it maps full matrices
over R to full matrices over R'. We now state Cohn's embedding
theorem.

For polynomials f,g∈∠x,y let [f,g] denotes the
commutator polynomial fg-gf. Cohn's embedding map
β:→∠x,y is defined as follows.


  * Let β(x_1)=y. For i≥ 2, define
  β(x_i)= [β(x_i-1),x].

  * We can then naturally extend β to a homomorphism from
   to ∠y,x, and it is easy to check that it is
  injective. In fact, we can even assume |X| to be countably
  infinite.
  

<cit.>
  The embedding map β:→∠x,y defined above extends to an embedding between the corresponding skew fields
  β : Z→x,y and hence is an honest
  embedding.
  
Cohn's construction is based on skew polynomial rings, which explains
the appearance of the iterated commutators
β(x_i)=[β(x_i-1),x]. We briefly sketch the underlying ideas
in the appendix (see Section <ref>). For more details see
<cit.>.





§ THE REDUCTION FROM MULTIVARIATE  TO BIVARIATE 


The reduction follows quite easily from Theorem <ref>. However,
we present some complexity details in this section showing that it is
actually a deterministic  reduction. The following lemma is
useful to describe the reduction.


  Recall the embedding map β defined above. β(z_0)=y and
  β(z_i+1)=[β(z_i),x] are polynomials in ∠x,y
  for each i≥ 0. Then, for n≥ 1 we have
  
    β(z_n) = ∑_i=0^n (-1)^i n  i x^iyx^n-i.

  
 
  As a consequence, there is a deterministic  algorithm that
  constructs a (n)-sized formula for β(z_n). 




We will use induction on n. The base case follows from the fact that
β(z_1)= yx - xy. Inductively assume the claim is true for all
n. Now, β(z_n+1)= [β(z_n), x]

    =   ∑_i=0^n (-1)^i n  ix^i y x^n-i+1- ∑_j=0^n (-1)^j n  jx^j+1 y x^n-j by induction hypothesis
       =    yx^n+1+ ∑_i=1^n (-1)^i n  ix^i y x^n-i+1 + ∑_i=1^n+1 (-1)^i n+1-1  i-1x^i y x^n+1-i
       =    yx^n+1+ ∑_i=1^n (-1)^i   [n+1-1  i + n+1-1  i-1]   x^i y x^n-i+1 + (-1)^n+1 x^n+1y 
       =    yx^n+1 + (-1)^n+1x^n+1 y + ∑_i=1^n (-1)^i n+1  i x^i yx^n+1-i  from Pascal's identity
       =   ∑_i=0^n+1 (-1)^i n+1  i x^i yx^n+1-i

This completes the inductive proof.

As the binomial coefficients can be computed in  using Pascal's identity, the expression for β(z_n) obtained above immediately implies an  algorithm for construction of a (n) sized formula for β(z_n). 








  The multivariate  problem is deterministic  (in fact,
  logspace) reducible to bivariate . More precisely, given as
  input a rational formula Φ computing an element of ,
  X={x_1,x_2,…,x_n} there is a deterministic 
  algorithm that computes a rational formula Ψ computing an
  element of x,y such that Φ is nonzero in its
  domain of definition iff Ψ is nonzero in its domain of
  definition.



  We can identify  with z_0,z_1,…,z_n-1.
  Let Φ_i(x,y) be the (i) size noncommutative formula
  computing the nested commutator β(z_i) for each i. In the
  rational formula Φ, for each i we replace the input z_i to
  Φ by Φ_i(x,y). The new formula we obtain is
  
    Ψ(x,y) = Φ(Φ_1(x,y),Φ_2(x,y),…,Φ_n-1(x,y)).

  By Theorem <ref>, Ψ(x,y) 0 on its domain of
  definition iff Φ(z_0,z_1,…,z_n-1) is nonzero on its
  domain of definition. Furthermore, because β is an
  embedding, it is guaranteed that if Φ has a nontrivial
  domain of definition then Ψ also has a nontrivial
  domain of definition.

  As computation of Ψ from Φ involves only replacing the
  z_i by Φ_i, the reduction is clearly logspace computable.





§  AND RELATED PROBLEMS





In this section we focus on the noncommutative rank problem .



  
Noncommutative Rank Problem

In the general form, the input is a d× d matrix M over the
ring , where each M_ij is given as input by a noncommutative
formula. The problem is to compute the noncommutative rank (M)
of the matrix M. We call this problem the  problem.

The problem has two different deterministic polynomial-time algorithms
due to <cit.>. It is also in randomized : the
algorithm is to substitute random matrices A_i∈^t× t for
each variable x_i, 1≤ i≤ n. The resulting matrix M' is
td× td dimensional, and with high probability the rank of M'
divided by t is (M). The important point here is that t is
bounded by (d,s), where s is an upper bound on the formula
sizes for the different M_ij <cit.>.

The algorithms of <cit.> both first Higman linearize the
matrix M and work with the resulting linear matrix.



  
SINGULAR problem
Given a d× d matrix M over the
ring , where each M_ij is given as input by a noncommutative
formula. The problem is to if the matrix M is invertible in the skew field or not.

We can easily reduce  to SINGULAR (see e.g. Lemma A.3 in <cit.>). 


There is a deterministic  reduction from  problem to the SINGULAR problem.


I will write a short proof







  
Higman Linearization

We describe a single step of the linearization process. Given an m
× m matrix M over ring  such that M[m,m]=f+g× h,
apply the following:


  * Expand M to an  (m+1)× (m+1) matrix by adding a new last
  row and last column with diagonal entry 1 and remaining new entries
  zero:

    [
    [ M 0; 0 1 ]].


  * Then the bottom right 2× 2 submatrix is transformed as
  follows by elementary row and column operations


    (
    [ f+gh    0;    0    1 ])→(
    [ f+gh    g;    0    1 ])→(
    [  f  g; -h  1 ])




Repeated application of the above to a matrix of polynomials
M∈^m× m yields a linear matrix L.

<cit.>
Let M ∈^m × m, whose each entry M_i,j is given by a
noncommutative arithmetic formula of size at most s. Then, for
k=O(s), in time (s,m) we can compute matrices P, Q and L
in ^ℓ×ℓ of Higman's linearization such that

    (
    [   M   0;   0 I_k ])  = PLQ.
, where ℓ= m+k.
The entries of the matrices P and Q as well as P^-1 and
Q^-1 are given by polynomial-size algebraic branching programs
which can also be obtained in polynomial time.

Moreover, (M)+k=(L). Hence the (noncommutative) rank of
(M) is easily computable from (L).

ncrk -> 
Thus, it suffices to consider the noncommutative rank problem for
linear matrices over .

Our interest is in the parallel complexity of . We first
make a simple observation.


  Given M∈^m× m as input there is a deterministic
   algorithm to compute the linear matrix L.



  Suppose each entry M_ij of the input matrix M is computed by a
  noncommutative formula of size bounded by s. The first step to
  note is the following.


  Given a noncommutative formula Φ of size s computing a
  polynomial f∈, we can transform it into another
  noncommutative formula Ψ for f of size (s) and such
  that the depth of Ψ is O(log s).


The claim follows from a careful inspection of the proof of
<cit.>.


Given a noncommutative formula Φ of size s and depth O(log
s), computing a polynomial in . We can compute its Higman
Linearization in deterministic . More precisely, we can compute a
linear matrix L_Φ, upper and lower triangular invertible
matrices P and Q, respectively such that:

    (
    [   M   0;   0 I_k ])  = PLQ.



We will sketch the proof of the claim. The details are simple.  We
note that Φ is of logarithmic depth by the previous claim. Now,
we can compute the Higman linearization, layer by layer bottom up, in
parallel. Since the formula size is known and for every + or
× gate in Φ we need to add a new row and column for the
Higman process, we know exactly the dimension of the final matrix L
and the precise location for placement of the submatrices inside L,
corresponding to each subformula of Φ.

Again, essentially by the same argument, we can apply the above claim
to each entry M_ij in parallel to compute the desired linear
matrix L.





§ REDUCTION FROM N-VARIATE  TO 2-VARIATE
  


In this section we give a deterministic  reduction from
n-variate  to bivariate . The basic idea of the
reduction is as follows. Given a polynomial matrix[We can
  assume it is a square matrix without loss of generality.]
M∈^m× m such that each entry of M is computed by
formula of size at most s. We will use Cohn's embedding theorem
<ref> to get a matrix M_1 with bivariate polynomial
entries such that each entry of M_1 is computed by a (n,s)
size noncommutative formula and (M)=(M_1). Notice that
M_1 is an instance of bivariate . Next, we need to give an
 reduction transforming M_1 to an instance of bivariate
 (which will be a matrix with linear entries in x and y).

In order to do this transformation in , we will first apply the
depth-reduction algorithm of Lemma
<ref> to get matrix M_2 whose
entries are (n,s) size log-depth formulas that compute the same
polynomials as the corresponding entries of M_1. Then we apply
Higman Linearization to M_2 to obtain a bivariate linear matrix
M_3. For this we will use our parallel algorithm for Higman
Linearization described in Theorem
<ref>. From the properties of Higman
linearization we can easily recover (M_2) from
(M_3).  In what follows, first we give a deterministic 
algorithm for the depth reduction of noncommutative formulas and
Higman linearization process. We conclude the section by giving an
 reduction from multivariate to bivariate  using above
NC algorithms combined with Cohn's embedding theorem <ref>.
 

. The goal is to compute noncommutative rank of M. We will give an  algorithm for the problem assuming an  algorithm for the problem SINGULAR in a case of bivariate linear matrix. First we describe the the broad steps of the algorithm and then give the details of each of the steps. 


  * It is easy to see that the standard reduction from rank computation to singularity test can be implemented in . So instead of computing a rank of a polynomial matrix M ∈^m ×ℓ the question boils down to checking if given square polynomial matrix L ∈^n × n is singular or not. 

  * Let L_1 ∈⟨ x, y ⟩ ^ n × n be a n × n polynomial matrix defined as follows. The (i,j)^th entry of L_1 is equal to φ(L_i,j) for 1≤ i,j ≤ n where L_i,j is the (i,j)^th entry of L and φ is Cohn's honest embedding map. A formula of size (s) can easily be constructed for each entry of L_1. From Cohn's embedding theorem <ref> it follows that L is singular iff L_1 is singular. This step can also be implemented in . 


  * First we give an  algorithm to convert any formula g ∈ of size s to an equivalent formula of size (s) with depth O(log s). Using this depth reduction algorithm, we obtain an  algorithm for Higman linearization. Which then can be used to transform matrix L_1 to L_2 such that L_2 ∈⟨ x, y ⟩^k × k is a linear matrix and L_1 is singular iff L_2 is singular. 








 §.§ Depth reduction for noncommutative formulas without divisions


In the commutative setting Brent <cit.> obtained a deterministic
 algorithm to transform a given rational formula (which
may have division gates) to a log-depth rational formula. In the
noncommutative setting, Hrubes and Wigderson <cit.> proved the
existence of log-depth rational formula equivalent to
any given rational formula.  Their proof is based on <cit.>.
However, it is not directly algorithmic as explained in the
introduction. We will discuss it in more detail in Section
<ref>. However, it turns out that, if the
noncommutative formula doesn't have division gates then the depth
reduction is quite easy and we obtain a simple deterministic 
algorithm for it that computes a log-depth noncommutative formula
equivalent to the given noncommutative formula. The proof is based
Brent's commutative version. We just highlight the distinctive points
arising in the noncommutative version in the proof presented in the
appendix.
    
We introducing some notation. Let Φ be a noncommutative
arithmetic formula computing a polynomial in
⟨ x_1, x_2, …, x_n ⟩. Let Φ̂ denote the
polynomial computed by Φ. For a node v ∈Φ, let Φ_v
denote the subformula of Φ rooted at node v, so Φ̂_̂v̂
is the polynomial computed by the subformula rooted at v.

For a node v∈Φ, let Φ_v← z be a formula obtained from Φ by replacing the sub-formula Φ_v by single variable z. For a node v∈Φ, let wt(v)= |Φ_v| denote the number of nodes in the subformula rooted at v. By size of formula Φ we refer to number of gates in Φ.  


  Given a formula Φ of size s computing a noncommutative
  polynomial f ∈⟨ x_1, x_2, …, x_n⟩ there is
  an  algorithm to obtain an equivalent formula Φ' for f
  with depth O(log s).


The proof of the lemma is in the appendix.










  In Lemma , we avoid using
  the depth-reduction approach for noncommutative rational formulas in
  <cit.>. This is because it can introduce inversion gates even
  if the original formula has no inversion gates. Instead, we directly
  adapt ideas from Brent's construction for commutative formulas to
  obtain the NC algorithm. We note here that Nisan's seminal work
  <cit.> also briefly mentions noncommutative formula depth
  reduction (but not its parallel complexity or even in an algorithmic
  context).
 





Higman linearization which is sometimes called Higman's trick was
first used by Higman in <cit.>. Cohn extensively used Higman
Linearization in his factorization theory of free ideal rings. Given a
matrix with noncommutative polynomials as its entries, Higman
linearization process transforms it into a matrix with linear
entries. This transformation process has several nice properties such
as: it preserves fullness of the matrix (that is the input polynomial
matrix is full rank iff final linear matrix is full rank), it
preserves irreducibility of the matrix, etc.



We first describe a single step of the linearization process applied
to a single noncommutative polynomial, which easily generalizes to
matrices with polynomial entries. Given an m × m matrix M
over  such that M[m,m]=f+g× h, apply the following:


  * Expand M to an  (m+1)× (m+1) matrix by adding a new last
  row and last column with diagonal entry 1 and remaining new entries
  zero:

    [
    [ M 0; 0 1 ]].


  * Then the bottom right 2× 2 submatrix is transformed as
  follows by elementary row and column operations


    (
    [ f+gh    0;    0    1 ])→(
    [ f+gh    g;    0    1 ])→(
    [  f  g; -h  1 ])




Given a polynomial f∈ by repeated application of the above step
we will finally obtain a linear matrix L=A_0+∑_i=1^n A_i
x_i, where each A_i, 0≤ i≤ n is an ℓ×ℓ over ,
for some ℓ. The following theorem summarizes its properties.

<cit.>
  Given a polynomial f∈, there are matrices P, Q∈^ℓ×ℓ
  and a linear matrix L∈^ℓ×ℓ such that

    P (
    [     f     0;     0 I_ℓ-1 ])  Q= L

with P upper triangular, Q lower triangular, and the diagonal
entries of both P and Q are all 1's. (Hence, P and Q are both
invertible over , moreover entries of P^-1 and Q^-1 are in ).

Instead of a single f, we can apply Higman linearization to a matrix
of polynomials M∈^m× m to obtain a linear matrix L
such that P(M ⊕ I_k)Q = L for invertible matrices P,Q.  Garg et
al. <cit.> gave polynomial time algorithm to carry out Higman
linearization for polynomial matrix whose entries are given by
noncommutative formulas. We will give an  algorithm to implement
this transformation.



Let A ∈^n × n be a polynomial matrix such that each entry of A is given by a noncommutative formula of size at most s. Then there is a deterministic  algorithm (with parallel time complexity ( log s, log n)) to compute invertible upper and lower triangular matrices P, Q ∈^ℓ×ℓ with all diagonal entries 1 and a linear matrix L ∈^ℓ×ℓ such that P  (
[   A   0;   0 I_k ]) Q = L, where ℓ = n+k and k is O(n^2· s). 

All the entries of P,Q are computable by algebraic branching programs of size (n,s). 

Moreover ncrk(A)+k = ncrk(L), hence the rank of A is easily computable from the rank of L.  


The proof of the above theorem is in the appendix.



Using Theorem <ref>, Lemma
<ref> and Theorem
<ref> we get a deterministic  reduction
from multivariate  to bivariate .


There is a deterministic  reduction from the multivariate  problem to the bivariate  problem.
 











§  REDUCTION FROM  TO BIVARIATE 
 

In this section we give an -Turing reduction from  to
bivariate . That is, we design an  algorithm for 
assuming we have an oracle for bivariate . Hrubes and
Wigderson in <cit.> give a polynomial time reduction from 
to  problem <cit.>. Also they show that
for any given rational formula Φ there is a log-depth rational
formula that is equivalent to Φ <cit.>.




Our key contribution here is to use Cohn's embedding theorem to
transform  problem to the bivariate case. Then we
parallelize the Hrubes-Wigderson reduction from  to
. In fact, if the input rational formula is already
logarithmic depth then the Hrubes-Wigderson reduction from  to
 can be implemented in . In this section we design an
 algorithm for depth reduction of rational formulas (possibly
with division gates) assuming  oracle for bivariate .[ It is an interesting problem to devise an
   algorithm for rational formula depth reduction without oracle
  access to singularity test.] Indeed, the construction of an
equivalent log-depth rational formula, as described in <cit.>,
does not appear to be directly parallelizable, as its description
crucially requires rational formula identity testing.[The
  overall proof in <cit.> is based on the Brent's depth-reduction
  of commutative rational formulas <cit.>. In the commutative
  case addressed by Brent, it turns out that the construction
  procedure does not require oracle access to identity testing and he
  obtains an  algorithm for obtaining the depth-reduced formula.]
 




We show that, indeed, the depth-reduction proof in <cit.> can be
parallelized step by step. However, there are some key points where
our algorithmic proof is different. Firstly, to solve the 
instance arising in the depth-reduction proof, we need to recursively
depth-reduce the corresponding subformula and then apply Hrubes-Wigderson
reduction from RIT to  on the constructed log-depth subformula.
Secondly, we need to handle an important case arising in the proof (namely, the case (2) in the description of the Normal-Form procedure in the proof of the Lemma <ref> in the Appendix) which was not significant for the existential argument in
<cit.>. In fact to handle this case, we require an argument based
on Brent's commutative formula depth reduction <cit.>.

In the detailed proof of Lemma <ref> given in the Appendix, we first sketch our  algorithm for depth
reduction of rational formula assuming oracle access to bivariate . We highlight and elaborate the key
steps where our proof differs from <cit.>. We need to reproduce
some parts of their proof for completeness, for these parts we just
sketch the argument and refer to <cit.> for the details. Using
this depth reduction algorithm we give an  Turing reduction from
 to bivariate , which is a main
result of this section.



 §.§ Depth reduction for noncommutative formulas with inversion gates



Let  denote the free noncommutative ring of polynomials in
noncommuting variables X, where X={x_1, x_2, …, x_n }.
When we allow division operations (or equivalently inversion gates) in
noncommutative expressions, we can compute noncommutative rational
functions, which are far more complicated than their commutative
counterparts. Rational expressions in the commutative setting can be
canonically expressed as ratios of two polynomials. This canonical
representation allows an easy reduction from identity testing of
rational expressions to polynomial identity testing in the
commutative case. Such a canonical representation is not possible in
the noncommutative setting. Defining the equivalence of noncommutative
expressions is challenging, and a formal definition essentially leads
to the definition of the free skew field  <cit.>. There are
several different approaches to defining skew fields
<cit.>.



We specifically
would like to mention the original construction of Amitsur <cit.>
(also see <cit.>, Chapter 8 of <cit.> for a detailed
exposition) and a construction due to Cohn <cit.>, <cit.>
(see <cit.>, <cit.> for a detailed
exposition). The books which discuss history and the construction of
skew fields include <cit.>, <cit.>.



Following Hrubes-Wigderson <cit.>, we use Amitsur's approach
<cit.> for defining skew fields. We recall basic definitions from
<cit.> (a more formal description is in <cit.>).

A rational formula r(x) is a noncommutative formula whose
inputs are noncommuting variables x_1, x_2, …, x_n and field
elements from . Its internal gates are the usual addition and
multiplication gates which are binary, along with inversion gates which
are unary. A rational formula Φ computes a rational expression
Φ̂, which is an element of the free skew field  in a
natural way (defined inductively <cit.>). The output
of an inversion gate is defined only when the input formula to the gate
computes a non-zero rational function.

 A rational formula Φ is called
  correct if û is defined for every internal node u
  of Φ.

Clearly Φ is correct iff input to every inversion gate in Φ is
a formula which computes a non-zero rational function.

Let R be a ring whose center contains field  (that is elements
of R commute with every element of ). Note that, a rational
formula Φ can also be thought of as a partial function
Φ̂:R^n ↦ R, that is on input
(a_1, a_2, …, a_n)∈ R^n we simply evaluate formula Φ by
substituting x_i =a_i for i∈ [n]. Φ̂(a_1, …, a_n)
is undefined if there is an inversion gate in Φ whose input is not
invertible in R. Typically R is chosen to be some matrix ring
M_k× k() for some k.


  Let Φ be a rational formula in variables X. For each
  k∈, we can associate with Φ a domain of definition
  𝒟_k,Φ consisting of the set of all matrix tuples
  (M_1, M_2, …, M_n)∈_k()^n such that the expression
  Φ̂(M_1, M_2, …, M_n) is defined where
  M_1, M_2, …, M_n are k × k square matrices over 
  for some k. The union 𝒟_Φ=⋃_k
  𝒟_k,Φ is defined as Φ's domain of definition.




The following is a consequence of results in <cit.> and <cit.>.

 

  Let Φ be a rational formula of size s computing a
  non-zero rational function in . If the field  is
  sufficiently large and k>2s then, at a matrix tuple
  (M_1, M_2, …, M_n) chosen uniformly at random from
  M_k × k ()^n, the matrix Φ̂(M_1, …, M_n)
  is nonsingular with "high" probability.


If  is small then we can pick the random matrices over a suitable
extension field, and by “high” probability we mean, say,
1-2^-Ω(s+n).

Let Φ_1 and Φ_2 be correct rational formulas of size at most
s computing rational functions in . By Theorem <ref> and a union bound argument, for a
random matrix substitution (M_1, M_2, …, M_n) from
M_k × k ()^n, inputs to all the inversion gates in Φ_1
and Φ_2 simultaneously evaluate to non-singular matrices with
"high" probability. Hence, for k sufficiently large we have
𝒟_k,Φ_1∩𝒟_k,Φ_2≠∅. It follows that a random matrix tuple is in
𝒟_k,Φ_1∩𝒟_k,Φ_2 with high
probability.









By Theorem <ref> and the definition of correct rational
formulas (Definition <ref>), it follows that if Φ_1
and Φ_2 are size s correct formulas that are not
equivalent then for a random matrix substitution of dimension k>2s
both Φ_1 and Φ_2 are defined and they disagree with high
probability. As noted in Section <ref>, equivalent formulas
need not have the same domain of definition.

Lemma <ref> is the main technical
result of this section. It describes an  algorithm for
depth-reduction of correct formulas assuming an oracle for bivariate
. The next lemma is useful for establishing equivalences of
formulas arising in the proof of Lemma
<ref>. Suppose Φ is a
rational formula computing the rational function Φ̂.  For a
gate v in formula Φ, Φ_v denotes the subformula rooted at
v. The formula Φ_v← z∈X∪{z} is
obtained from Φ by replacing subformula Φ_v with fresh
variable z.



  Let Φ be a correct rational formula and
  v be a gate in Φ. Suppose Ψ and
  Ψ' are any correct rational formulas equivalent to
  Φ_v and Φ_v ← z, respectively. Let
  Φ' denote the rational formula obtained by replacing
  z in Ψ' by Ψ. If Φ' is correct then
  Φ' is equivalent to Φ.



I will complete the proof. I WOULD LIKE TO DISCUSS THIS...



  Let Φ be a correct rational formula and
  v be a gate in Φ. Suppose Ψ is a correct rational formula equivalent to Φ_v. Let Ψ' = (A· z + B) · (C · z +D)^-1 is a formula equivalent to Φ_v ← z such that A, B, C, D are correct formulas which do not depend upon z and Ĉ·Δ̂ + D̂≠ 0 for any formula Δ such that Φ_v ←Δ is correct. Let
  Φ' denote the rational formula obtained by replacing
  z in Ψ' by Ψ. Then Φ' is correct and it is equivalent to Φ.



From the definitions of Φ_v and Φ_v← z it follows that Φ = Φ_v ←Φ_v. As Φ is correct, from the properties of formulas C,D as stated in the lemma it follows that ĈΦ̂_̂v̂+D̂≠ 0. Which implies ĈΨ̂+D̂≠ 0 as Ψ≡Φ_v. This shows that the formula Φ' = (A ·Ψ + B) · (C ·Ψ + D)^-1 is correct. 
Now let τ= (M_1, …, M_n) is a matrix tuple in 𝒟_Φ∩𝒟_Φ', the intersection of domains of definition of Φ and Φ'. This implies τ∈𝒟_Φ_v as 𝒟_Φ⊆𝒟_Φ_v, Φ_v being subformula of Φ. Similarly, τ∈𝒟_Ψ as 𝒟_Φ'⊆𝒟_Ψ, Ψ being a subformula of Φ'. So τ∈𝒟_Φ_v∩𝒟_Ψ. As Φ_v ≡Ψ, it follows that Φ_v(τ)= Ψ(τ). 
As τ∈𝒟_Φ. It implies that (M_1, M_2,…,M_n, Φ_v(τ))= (τ, Φ_v(τ)) ∈𝒟_Φ_v← z. 
Similarly, as τ∈𝒟_Φ', it follows that (τ, Ψ(τ)) ∈𝒟_Ψ'. As Φ_v(τ)= Ψ(τ), it implies 
    (τ, Φ_v(τ))=(τ, Ψ(τ)) ∈𝒟_Φ_v← z∩𝒟_Ψ'

As Φ_v← z≡Ψ', this implies Φ_v← z(τ, Φ_v(τ)) = Ψ'(τ, Ψ(τ)). But Φ_v← z(τ, Φ_v(τ)) = Φ(τ) and Ψ'(τ, Ψ(τ))= Φ'(τ). So we get Φ(τ) = Φ'(τ) for any τ∈𝒟_Φ∩𝒟_Φ'. Thus proving Φ≡Φ'. 




Given a correct formula Φ of size s computing a rational function f ∈, for sufficiently large s and absolute constants c,b



  * we give an  algorithm, with oracle access to bivariate , that outputs a correct formula Φ' of depth at most c log _2 s which is equivalent to Φ.

  * If a variable z occurs in Φ at most once then we give an  algorithm, with bivariate  as oracle, that constructs correct rational formulas A, B, C, D which do not depend on z with depth at most c log_2 s +b and the formula Φ' = (A · z+B)· (C · z + D)^-1 is equivalent to Φ. Moreover, the rational function ĈΨ̂ +D̂≠ 0 for any formula Ψ such that Φ_z ←Ψ is correct.





The proof of the above lemma is given in the appendix.




  
Hrubes-Wigderson reduction from  to 

Now we recall the polynomial-time reduction from  to 
from <cit.>. Given a rational formula Φ their reduction
outputs an invertible linear matrix M in the variables
X.[Notice that the entries of M^-1 are elements of the
  skew field ] Their reduction ensures that the top right entry
of M^-1 is Φ̂, the rational function computed by the
formula Φ. It turns out that if Φ is already of logarithmic
depth then their reduction can be implemented in .










Let Φ be a rational formula of size s and depth O(log s) computing a rational expression in  there is an  algorithm to construct an invertible linear matrix M_Φ such that the top right entry of M_Φ^-1 is Φ̂. 
 


  We only briefly sketch the  algorithm. Their reduction
  recursively constructs the matrix M_Φ, using the formula
  structure of Φ.

  If formula Φ has height 0 that is Φ̂=x is a variable or a scalar them M_Φ can be chosen as (
[  1  x;  0 -1 ]). Clearly M_Φ^-1= M_Φ with top right entry as x. If Φ has height atleast 1  then the construction proceeds recursively as follows. Let Φ̂=f ∈. Let w be root of Φ. 


  * If w is inversion gate let u be child of w and Φ̂_̂û≠ 0 then 

    M_Φ= M_Φ_w = (
    [ v_p^T M_Φ_u;     0  -u_p ])

where p is a dimension of M_Φ_u and u_p resp. v_p be 1× p row vectors with first resp. last entry 1 and other entries zero.

  * If w is a + or × gate then let l,r be left and right children of w respectively. Let p,q be the dimensions of _Φ_ℓ and M_Φ_r respectively. For k∈{p,q}, let u_k resp. v_k be 1× k vectors with first resp. last entry is 1 and all other entries are zero. 


  * If w is ×-gate then

    M_Φ= M_Φ_w = (
    [     M_Φ_ℓ -v_p^Tu_q;         0     M_Φ_r ])


  * If w is +-gate then

    M_Φ= M_Φ_w = (
    [     M_Φ_ℓ c_1 · u_q    -v_p^T;         0     M_Φ_r     v_q^T;         0         0         1 ])

where c_1 is the first column of M_Φ_ℓ.
  

Refer Theorem 2.6 in <cit.> for the correctness proof.


Given a formula Φ we can compute the sizes of all its subformulas
in  using a standard pointer doubling algorithm. This allows us
to estimate the dimensions of matrices M_Φ_v for subformulas
Φ_v for each gate v of Φ. We can also compute in  the
precise location for placement of the sub-matrices M_Φ_v inside
the matrix M_Φ following their construction. Assuming that Φ
is already of logarithmic depth, there are only O(log s) nested
recursive calls for this recursive procedure. This ensures that the
overall process can be implemented in .


After constructing linear matrix M_Φ such that the top right
entry of M_Φ^-1 is Φ̂, define matrix M' as M'= (
[ v^T M_Φ;   0  -u ])

where u,v are 1× k vectors, such that u=(1, 0, …, 0)
and v=(0, 0, …, 0, 1) where k is the dimension of the matrix
M_Φ. It follows that Φ̂≠ 0 iff M' is invertible
in the skew field  (see e.g. <cit.>). So
we have the following theorem.





Let Φ be a rational formula of size s and depth O(log s) computing a rational expression in  then there is an  algorithm to construct a linear matrix M such that Φ̂≠ 0 iff M is invertible in the skew field . 
 
Now, from Lemma <ref>, Theorem
<ref>, and Theorem <ref>, we
obtain an  Turing reduction from multivariate  to bivariate
.


There is a deterministic  Turing reduction from  problem to  problem for bivariate linear matrices.





















  
Concluding Remarks.




Motivated by the question whether  and  have
deterministic  algorithms, we show that multivariate  is
-reducible to bivariate  and multivariate  is
-reducible to bivariate .   is known to be
polynomial-time reducible to , and indeed that is how the
polynomial-time algorithm for  works, by reducing to 
and solving . We show that  is deterministic
-Turing reducible to . We prove this by showing that
noncommutative rational formula depth reduction is -Turing
reducible to . The main open problem is to obtain deterministic  algorithms for bivariate  and bivariate
. We also leave open finding an unconditional  algorithm
for depth-reduction of noncommutative rational formulas.






plain








  Appendix






§ COHN'S EMBEDDING THEOREM


Let X={x_1, x_2,…,x_n} be a set of n noncommuting variables, and let
x, y be a pair of noncommuting variables. The goal of Cohn's
construction <cit.> is to obtain an honest embedding from
→∠x,y. Indeed, his construction gives an honest
embedding map even for a countable set of variables
X={x_1,x_2,…}.

The first point is that the free noncommutative rings  and
∠x,y have both enough structure[Technically, both these rings are semifir <cit.>.] that guarantees the
following.


  If a homomorphic embedding ϕ:→∠x,y can be
  extended to a homomorphic embedding ϕ: → then,
  in fact, ϕ is an honest embedding.
  

The reason for this is basically, that if an n× n M over
 is a full matrix then it is invertible with an inverse M^-1
over the skew field . Thus, it suffices to find a homomorphic
embeddings that extends to one between the corresponding free
skew fields.

Cohn solved this problem of finding such an embedding <cit.> by an ingenious construction using skew polynomial
rings. 



  
Skew Polynomial Rings

We recall the definition of skew polynomial rings and state some basic
properties (details can be found in Cohn's text <cit.>).  Let R be an integral
domain[That means R is a, possibly noncommutative, ring
with unity 1 and without zero divisors.] and let σ:R→ R be
a ring endomorphism.  Let

    A={x^n a_n + x^n-1a_n-1+ … + a_0| each  a_i ∈ R}

be the set of all formal univariate polynomials in the indeterminate
x which is assumed to not commute with elements of R. Addition
of elements in A can be defined component-wise as usual. The multiplication
operation is defined with a "twist" to it, using the ring endomorphism 
σ, which we briefly explain below.

A σ-derivation on R is defined as an additive
homomorphism δ: R→ R such that

    δ(ab) = σ(a)δ(b) + δ(a) b  for all  a,b∈ R.


We define

    ax=xσ(a) + δ(a),  for all  a∈ R,

which extends to ring multiplication in A. Under these operations the set A is the
skew polynomial ring denoted R[x;σ,δ]. If the R-endomorphism 
σ is the identity map 1 and δ=0 in this definition, then we 
obtain the univariate polynomial ring R[x] in which the variable x commutes 
with elements of R. 

Following Cohn's construction in his embedding theorem, we consider
skew polynomial rings of the form R[x; 1, δ], where the endomorphism
σ=1. We refer to δ as a derivation and we have:

  
    δ(ab)     =    aδ(b) + δ(a) b  for all  a,b∈
        R,  and
     ax     =     xa + δ(a),
         for all  a∈ R.




  
Cohn's Construction

We now describe the construction, adding some details to the rather terse
description in <cit.>.



We set the integral domain R to be  for
X={x_1,x_2,…,}. Consider the map δ: X ↦ X
defined as

    δ(x_i)= x_i+1.

The map δ naturally extends to a unique derivation on  as
follows. For scalars a∈, we define
δ (a x_i)=aδ(x_i), by linearity. Next, define δ on
all monomials in X^*. Let
δ(x_ix_j)=δ(x_i)x_j + x_iδ(x_j). In general, for a
degree-ℓ monomial m = x_i_1 x_i_2… x_i_ℓ we
define

    δ(m) =δ(x_i_1x_i_2… x_i_k) x_i_k+1 x_i_k+2…
    x_i_ℓ + x_i_1x_i_2… x_i_kδ ( x_i_k+1 x_i_k+2… x_i_ℓ).


It is easy to verify that the above definition of δ(m) is
independent of k∈[ℓ]. We now extend this definition to the
entire ring  by linearity.  By an easy induction on the degree of
polynomials in  we obtain the following.






The mapping δ defined above is a derivation on the ring R=.


Let H=R[x;1,δ] be the skew polynomial ring defined by the
derivation δ described above. By definition, δ satisfies
Equations <ref> and <ref>. Therefore, putting
a=x_i in Equation <ref>, for each i≥ 1 we have

    x_i+1=x_ix - xx_i=[x_i,x],

This actually gives a homomorphic embedding from the ring  to
the bivariate ring ∠x,y. To see this, we define a map 
β: X ↦∠x,y as follows:


  * Let β(x_1)=y. For i≥ 2, let β(x_i)=
  [β(x_i-1),x].

  * We can then naturally extend β to a homomorphism from  to
  ∠x,y, and it is easy to check that it is injective.
  
Hence we have

<cit.>
  β is a homomorphic embedding from  to ∠x,y.




Furthermore, by the definition of δ, the elements of the skew
polynomial ring R[x;1,δ] are also polynomials in the ring
∠x,y.  Indeed, the map β can be extended to an
isomorphism from the ring R[x;1,δ] to ∠x,y as
follows: for
f=x^n a_n + x^n-1a_n-1+ … + a_0 ∈ R[x;1,δ] define
β(f)= x^n β(a_n)+ x^n-1β(a_n-1)+ … +
xβ(a_1)+ β(a_0).


Now, define a map δ_x:G → G as follows. For a ∈ G, let
δ_x(a)= ax - xa. Clearly δ_x(x)=0 and for any scalar c
∈𝔽 δ_x(c)=0 as x commutes with c. It is easy
to check that the map δ_x is a derivation on G. That is, for
a,b ∈ G we have δ_x (a+b)= δ_x(a)+δ_x(a) and
δ_x(ab) = δ_x(a)b + a δ_x(b). Furthermore, we can
check that for any element a∈ β(δ(a))=δ_x(β(a)).
Using these properties Cohn shows the following.


<cit.>
  β is a homomorphic embedding from  to ∠x,y.
  Furthermore, β is an isomorphism from R[x;1,δ] to
  ∠x,y.
  

Using properties of the field of fractions of the skew polynomial
ring R[x;1,δ] Cohn shows that β extends to an
embedding between the skew fields.


  The embedding map β:→∠x,y extends to an
  embedding β : → which implies that β
  is an honest embedding.
  



  
Proof of Lemma <ref>





  First we describe a recursive construction to compute a formula
  Φ' equivalent to Φ and inductively prove that the depth of
  Φ' is c log_2 s for an absolute constant c. Then we
  analyze the parallel time complexity of the construction and prove that
  it can be implemented in .

  Let A_Φ be s × s matrix such that for gates
  u,v ∈Φ, (u,v)^th entry of A_Φ is 1 if gate v is
  a descendent of gate u. Using the well-known pointer doubling
  strategy (see e.g. <cit.>, <cit.>) we can compute matrix
  A_Φ in . So by adding elements in each row of A_Φ, we
  can compute wt(u) (that is the number of descendants of gate
  u ∈Φ) in . Let v be a gate in Φ such that
  s/3≤ wt(v) < 2s/3. Such a gate always exists
  by a standard argument.

  We start traversing down from the root r
  of Φ by picking a heavier child (one with more number of
  descendants) until we arrive at a gate v such that
  wt(v)< 2s/3 and wt(u) ≥2s/3 where u is
  parent of v. Clearly wt(v) can not be less than s/3,
  as if wt(v)<s/3, v being a heavier child it would imply
  wt(u)< 2s/3, a contradiction. So there exist a gate v
  such that s/3≤ wt(v) < 2s/3. 

Since we can compute the number of descendants of a gate in , we
can also find such a gate v in , by simply having a processor
associated to each gate to check the above inequalities. Now we are
ready to describe recursive construction of Φ'.


  * In  find a gate v in Φ such that s/3≤ wt(v) < 2s/3.

  * Let r=v_0 be the root of Φ and
  v_1,v_2, …, v_ℓ-1 be gates on r to v path in
  Φ. Let v=v_ℓ. For 1≤ i ≤ℓ, let u_i denote a
  sibling of v_i. Let S_1 be collection of all indices j such
  that 1≤ j ≤ℓ, v_j is a product gate and is a right
  child of its parent. Similarly let S_2 be collection of all
  indices j such that 1≤ j ≤ℓ, v_j is a product gate
  and is a left child of its parent. Define formula
  Ψ_1 = ∏ _j ∈ S_1Φ_u_j. The product is computed
  using sequence of multiplication gates, starting with Φ_u_j
  for the first u_j (one with smallest index j∈ S_1) each
  multiplication gate multiplies the product so far from right by
  Φ_u_j for the next gate u_j, j∈ S_1, along the root to
  v path. Similarly define formula
  Ψ_2 = ∏ _j ∈ S_2Φ_u_j. Let Ψ_3 be a formula
  obtained from Φ by replacing subformula Φ_v by zero.

  * Recursively in parallel compute log-depth formulas
  Ψ_1', Ψ_2', Ψ_3', Φ_v' equivalent to Ψ_1,
  Ψ_2, Ψ_3 and Φ_v respectively.

  * Define formula
  Φ' as (Ψ_1'·Φ_v')·Ψ_2'+Ψ_3.
 
From the definitions of Ψ_1, Ψ_2 and Ψ_3 it is clear that
the polynomial computed by Φ equals
(Ψ̂_̂1̂·Φ̂_̂v̂)·Ψ̂_̂2̂+Ψ̂_̂3̂,
where Ψ̂_̂1̂,Ψ̂_̂1̂,Ψ̂_̂1̂, Φ̂_̂v̂ are the
polynomials computed by Ψ_1, Ψ_2, Ψ_3 and Φ_v
respectively. Hence, Φ', defined in Step 4, is equivalent to Φ.

Let d(s) denote the upper bound on the depth of the formula output
by the above procedure if size s formula is given to it as input. We
use induction on the size s to prove that d(s)≤ c log_2 s. As
Ψ_1, Ψ_2 are disjoint subformulas of Φ_v← z,
clearly we have |Ψ_1|+|Ψ_2| ≤ |Φ_v← z|. Since
|Φ_v| ≥s/3, it implies
|Ψ_1|, |Ψ_2| ≤ |Φ_v← z|≤2s/3. From the definition of Ψ_3, it is clear that
|Ψ_3| ≤ |Φ_v← z|≤2s/3. So the size
of each formula Ψ_1, Ψ_2, Ψ_3 and Φ_v is upper
bounded by 2s/3. Hence, inductively, for each of the
formulas Ψ_1', Ψ_2', Ψ_3', Φ_v' the depth is upper
bounded by c log_2 2s/3. As Φ' is obtained from
Ψ_1', Ψ_2', Ψ_3', Φ_v' using two multiplications and an
addition as in Step 4, it follows that the depth of
Φ'=d(s)≤ clog_22s/3 + 3. Choosing
c≥3/(log_2 3-1) we get
d(s)≤ clog_22s/3 + 3 ≤ c log _2 s. This completes
the induction, proving that the depth of Φ' is at most
c log_2 s.

Let t(s) denotes parallel time complexity of the above
procedure. Since Steps 1, 2, 4 can be implemented in  they
together take (log s)^k parallel time for an absolute constant
k. As all the recursive calls in Step 3 are processed in parallel,
we have the recurrence t(s)≤ t(2s/3)+(log s)^k. Hence,
t(s)≤ (log s)^(k+1). This shows that the above procedure can
be implemented in , completing the proof of the theorem.




  
Proof of Theorem <ref>





  By Lemma <ref> we have an 
  algorithm to convert every entry of A to a log-depth formula. We
  will first describe parallel algorithm for Higman linearization of
  single polynomial f given by noncommutative log-depth formula
  Φ. Higman linearization of a polynomial matrix can be handled
  similarly.

 
Given a noncommutative formula Φ of size s and depth O(log s) computing a polynomial f in . We can compute Higman linearization of f in deterministic . More precisely, we can compute a linear matrix L_Φ∈^(s+1)× (s+1), invertible upper and lower triangular matrices P,Q ∈^(s+1)× (s+1) with all diagonal entries 1 such that P(f ⊕ I_s)Q = L_Φ. 
All the entries of P,Q are computable by algebraic branching programs of size (s). Moreover, f ≢0 iff L_Φ is a full noncommutative rank matrix.


  The basic idea is to compute the Higman linearization recursively in
  parallel. Since the formula size is known and for every + or
  × gate in Φ we need to add a new row and column for the
  Higman process, we know exactly the dimension of the final matrix
  L and the precise location for placement of the submatrices inside
  L, corresponding to each subformula of Φ. To obtain Higman
  linearization of Φ we recursively in parallel compute Higman
  linearization of the subformulas rooted at the left and the right
  child of the root. Based on whether at root of Φ we have a
  +-gate or a ×-gate, we appropriately compose Higman
  linearizations of the sub-formulas rooted at the left and the right
  child of the
  root. 
  As depth of Φ is logarithmic, there are only O(log s) nested
  recursive calls, this ensures that the overall process can be
  implemented in .

We now give the details of the inductive proof. 

Let r be the root of Φ, and g and h be the polynomials
computed at the left and right child of r, respectively. If r is a
×-gate, the matrix obtained after the first step of the Higman
Linearization is


    (
    [ 1 g; 0 1 ])
    (
    [ g· h    0;    0    1 ])
    (
    [  1  0; -h  1 ])  = (
    [  0  g; -h  1 ])


If r is a +-gate, we do not explicitly deal with it, as we are
eventually interested only in linearizing the
matrix. Nevertheless, for the +-gate case we carry out following
step.[This facilitates the presentation and calculation of
  parallel placement of linear submatrices corresponding to the
  recursive calls inside the final Higman linearized matrix for f.]


    (
    [ 1 g; 0 1 ])
    (
    [ g+h   0;   0   1 ])
    (
    [  1  0; -1  1 ])  = (
    [  h  g; -1  1 ])

It reduces computing Higman linearization of g+h to computing it for
g and for h.

We can in  compute the size of sub-tree rooted at any gate of
Φ. Let s_1 and s_2 be sizes of the left and right sub-trees
of the root r. Let w=-h if r is a ×-gate and is equal to
h when r is a +-gate. Suppose we compute Higman linearization of
g and w recursively in parallel. More precisely, we obtain
invertible upper and lower triangular matrices
P_g,Q_g ∈^(s_1+1)× (s_1+1) respectively, with all
diagonal entries 1 and linear matrix
L_g ∈^(s_1+1)× (s_1+1) such that
P_g  (g ⊕ I_s_1)  Q_g=L_g. The entries of P_g, Q_g are
given by ABPs of size (s_1). Similarly, we obtain invertible
upper and lower triangular matrices
P_w,Q_w∈^(s_2+1)× (s_2+1) respectively, with all
diagonal entries 1 and linear matrix
L_w ∈^(s_2+1)× (s_2+1) such that
P_w  (w ⊕ I_s_2)  Q_w = L_w. The entries of P_w,Q_w are
given by ABPs of size (s_2). Let R_g ∈^1× s_1 be
a row matrix obtained by dropping (1,1)^th entry from the first
row of P_g. Similarly, column matrix C_g is obtained by
dropping(1,1)^th entry from the first column of
Q_g. Analogously, define row and column matrices R_w and
C_w. Let P_g',Q_g' denote bottom right s_1 × s_1 blocks of
matrices P_g and Q_g respectively. Similarly, let P_w',Q_w'
denote bottom right s_2 × s_2 blocks of matrices P_w and
Q_w respectively. So we have,

    L_g = (
    [    1  R_g;    0 P_g' ])
    (
    [     g     0;     0 I_s_1 ])
    (
    [    1    0;  C_g Q_g' ])
    =
    (
    [ g+R_gC_g  R_gQ_g';  P_g'C_g P_g'Q_g' ])
   
Similarly, we have

    L_w = (
    [    1  R_w;    0 P_w' ])
    (
    [     w     0;     0 I_s_2 ])
    (
    [    1    0;  C_w Q_w' ])
    =
    (
    [ w+R_wC_w  R_wQ_w';  P_w'C_w P_w'Q_w' ])
   

Now we are ready to define matrices P,Q,L using matrices
P_g,Q_g,P_w,Q_w so that P(f⊕ I_s)Q = L.



  * r is ×-gate

After the first step of Higman linearization on f the matrix
obtained is
(
[ 0 g; w 1 ]).

When we obtain Higman linearization for g, w recursively, these
polynomials sit at (1,1)^th entry of g⊕ I_s_1 and
w ⊕ I_s_2 respectively. Whereas in the matrix above, the
polynomials g,w sit at (1,2)^th, (2,1)^th entries
respectively. Now we define block matrices P̃_̃g̃,P̃_̃w̃
and Q̃_̃g̃,Q̃_̃w̃ for performing row and column
operations, respectively, on the appropriate rows and columns of the
matrix, taking into account the location of g and h. Whenever we
are carrying out linearization for g it keeps the block
corresponding to linearization of h intact and vice-versa.  Define
P̃_̃g̃, P̃_̃w̃ as

    P̃_̃g̃=
    (
    [                 [ 1 0; 0 1 ]         [ R_g   0;   0   0 ];                            0 [  P_g'     0;     0 I_s_2 ] ]), P̃_̃w̃=
    (
    [                 [ 1 0; 0 1 ]         [   0   0;   0 R_w ];                            0 [ I_s_1     0;     0  P_w' ] ])


Similarly, define Q̃_̃g̃, Q̃_̃w̃ as

    Q̃_̃g̃=
    (
    [                 [ 1 0; 0 1 ]                            0;         [   0 C_g;   0   0 ] [  Q_g'     0;     0 I_s_2 ] ]), Q̃_̃w̃=
    (
    [                 [ 1 0; 0 1 ]                            0;         [   0   0; C_w   0 ] [ I_s_1     0;     0  Q_w' ] ])


P̃_̃g̃, Q̃_̃g̃ carry out linearization of g, P̃_̃w̃, Q̃_̃w̃ carry out linearization of w. Define P_1 = (
[ 1 g; 0 1 ]) ⊕ I_s_1+s_2 and Q_1 = (
[ 1 0; w 1 ]) ⊕ I_s_1+s_2, which would carry out the first step of linearization.

Finally, define P=P̃_̃w̃P̃_̃g̃P_1. We can see that P=(
[             [ 1 g; 0 1 ]     [ R_g   0;   0 R_w ];                        0 [ P_g'    0;    0 P_w' ] ]). Similarly, define Q=Q̃_̃w̃Q̃_̃g̃Q_1=(
[             [ 1 0; w 1 ]                        0;     [   0 C_g; C_w   0 ] [ Q_g'    0;    0 Q_w' ] ])

As P_g' and P_w' are bottom right blocks of the upper triangular
matrices P_g and P_w, it follows that P_g', P_w', and hence
also P is invertible, and also upper triangular with all diagonal
entries 1. Similarly, Q is invertible and lower triangular with all
diagonal entries 1. As P,Q are realized as a matrix product as
defined above and entries of P_g, Q_g and P_w, Q_w are given by
ABPs of size (s_1), (s_2) respectively, we can construct
ABPs of (s) size for entries of P and Q in .

Now, define L_Φ=P(f⊕ I_s)Q =(
[ [        0 g+R_gC_g; w+R_wC_w        1 ]     [ R_gQ_g'       0;       0 R_wQ_w' ];     [       0 P_g'C_g; P_w'C_w       0 ] [ P_g'Q_g'        0;        0 P_w'Q_w' ] ])

Clearly, L_Φ is linear as L_g and L_w are linear. Note that
we do not need to compute L_Φ as a product P(f⊕
I_s)Q. If we explicitly know linear entries of L_g, L_w (which we
do know recursively) we can explicitly compute linear entries of
L_Φ.









  * r is +-gate

  This case is handled similarly. In case of +-gate, the matrix
  obtained after first step is
  (
[  w  g; -1  1 ]).
So to ensure the Higman linearized matrices of g and w are
correctly placed inside the Higman linearized matrix for f we define
P,Q as

    P=(
    [             [ 1 g; 0 1 ]     [ R_g R_w;   0   0 ];                        0 [ P_g'    0;    0 P_w' ] ]), Q=(
    [         [  1  0; -1  1 ]                        0;     [   0 C_g; C_w   0 ] [ Q_g'    0;    0 Q_w' ] ])

and define L_Φ as 

    L_Φ=P(f⊕ I_s)Q=(
    [ [ w+R_wC_w g+R_gC_g;       -1        1 ]     [ R_gQ_g' R_wQ_w';       0       0 ];     [       0 P_g'C_g; P_w'C_w       0 ] [ P_g'Q_g'        0;        0 P_w'Q_w' ] ])
 Clearly, any entry of L_Φ is a scalar or some entry of
L_g or L_w, so L_Φ is linear. Again, entries of L_Φ can
be computed explicitly, given the matrices L_g and L_w
explicitly. This completes the Case 2.

As P,Q are invertible, it implies (f⊕ I_s) = (L),
which implies L is full iff f ≢0. This proves the
claim.



In the general case, we need to Higman linearize an n × n
polynomial matrix A. We will in parallel compute Higman
linearization matrices for each entry of A using the  algorithm
described in the above claim. Let M_i,j be
(s_i,j+1) × (s_i,j+1) linear matrix corresponding to
(i,j)^th entry for 1≤ i,j ≤ n. That is
M_i,j= P_i,j (A_i,j⊕ I_s_i,j) Q_i,j where
P_i,j, Q_i,j are invertible upper and lower triangular matrices
respectively. We have polynomial sized ABPs for entries of P_i,j
and Q_i,j.

Let M_i,j' denote s_i,j× s_i,j bottom right block of M_i,j. Let R_i,j denote 1 × s_i,j row matrix obtained by dropping first entry of first row of M_i,j. Similarly, let C_i,j be s_i,j× 1 column matrix obtained by dropping first entry of the first column of M_i,j. 
Then, the matrix L is a 2× 2 block matrix such that


  * The top left block of L is n× n and for 1≤ i,j ≤ n, (i,j)^th entry of the block is (1,1)^th entry of M_i,j.

  * The top right block of L is the matrix 

    ([ R_1,1 R_1,2 … R_1,n                                                            ;                     R_2,1 R_2,2 … R_2,n                                        ;                                                           ⋱                    ;                                                             R_n,1 R_n,2 … R_n,n ])


  * The bottom left block of L is the matrix [B_1 B_2 … B_n]^T where for 1≤ i≤ n, B_i is the matrix 
    ([ C_i,1                  ;       C_i,2            ;                 ⋱      ;                   C_i,n ])


  * The bottom right block of L is a matrix ([ D_1            ;     D_2        ;           ⋱    ;             D_n ]) where D_i is a matrix ([ M_i,1'                     ;        M_i,2'              ;                    ⋱       ;                      M_i,n' ])

   
All unspecified entries in the above matrices are zero. As done in
the proof of Claim <ref>,
we can easily define invertible upper and lower triangular matrices
P and Q such that P(A⊕ I_k)Q =L. Also we can obtain ABPs
computing entries of P,Q from ABPs for the entries of the matrices
P_i,j, Q_i,j, 1≤ i, j ≤ n. Since P,Q are invertible,
it implies that (L) is equal to (A⊕ I_k)
which is equal to (A)+k. Clearly, the dimension of the bottom
right block of L is O(n^2 · s) which implies similar bound on
k. This completes the proof of the theorem.





  
Proof of Lemma <ref>





  We give a recursive construction for both the parts and prove the
  correctness by induction on s, the size of the formula Φ.




Depth-reduce(Φ)

Input: A correct formula Φ of size s computing a rational function in .

Output: A correct formula Φ' of depth at most c log_2 s such that Φ≡Φ'.





  * Find a gate v ∈Φ such that s/3< wt(v) ≤2s/3.

  * In Parallel construct formulas Ψ, Δ such that Ψ= Depth-Reduce(Φ_v) and Δ = Normal-Form(Φ_v← z,z).

  * Obtain formula Φ' from Δ by replacing z in Δ by Ψ.

  * Output Φ'.







Normal-Form(Φ, z)

Input: A correct formula Φ of size s computing a rational function in  and a variable z ∈Φ which appears at most once in Φ

Output: A correct formula Φ' which is of the form 
    Φ' = (Az+B)(Cz+D)^-1

where A, B, C and D are correct rational formulas which do not depend on z with depth at most c log_2 s+b. Moreover, the rational function ĈΨ̂ +D̂≠ 0 for any formula Ψ such that Φ_z ←Ψ is correct.


Let v_1, v_2, …, v_ℓ=z be gates on the path from root r of
Φ to the leaf gate z, such that v_j is not an inverse
gate. So parent of each v_j has two children, and let u_i denote
the sibling of v_i. Use pointer doubling based parallel algorithm
(as mentioned in the proof of Lemma
<ref>) to compute wt(u_i) and
wt(v_i) for all i∈ [ℓ]. We call gate v_i for i∈ [ℓ]
as a balanced gate if
wt(Φ_v_i), wt(Φ_v_i ← z') ≤5s/6. Now
we consider two cases.



  * There exist a balanced gate v_i:



  * Let v= v_i. In parallel compute formulas Ψ_1, Ψ_2 such that 

    Ψ_1   =   (A_1z'+B_1)(C_1z'+D_1)^-1=Normal-Form(Φ_v ← z',z')
    Ψ_2   =   (A_2z+B_2)(C_2z+D_2)^-1=Normal-Form(Φ_v,z)


  * Define formulas A, B, C, D as A_1· A_2 + B_1 · C_2, A_1· B_2 + B_1 · D_2, C_1· A_2 + D_1 · C_2 and C_1· B_2 + D_1 · D_2 respectively.

  * Let Φ'=(A· z+B)·(C · z+D)^-1

  * Output Φ' and halt


  * There does not exist a balanced gate:

In this case, we can prove that there is a unique i∈[ℓ] such that wt(u_i)> s/6.


  * Let v be parent of the gate v_i.

  * In Parallel find formulae Ψ_1,Ψ_2,Ψ_3,Ψ_4 such that 

    Ψ_1   =   (A_1z'+B_1)(C_1z'+D_1)^-1=Normal-Form(Φ_v ← z',z')
    Ψ_2   =   (A_2z+B_2)(C_2z+D_2)^-1=Normal-Form(Φ_v_i,z)
    Ψ_3   =   Depth-Reduce(Φ_u_i)
    Ψ_4   =    (Az+B)(Cz+D)^-1=Normal-Form(Φ”,z)

where Φ” is obtained by replacing sub-tree rooted at u_i by 0 in Φ.

  * Using the algorithm of Theorem <ref>
  check if Ψ̂_̂3̂≡ 0 in  with oracle access to
  bivariate . If Ψ̂_̂3̂≡ 0 then output Ψ_4
  and halt.

  * If Ψ̂_̂3̂≢0 then let Φ'=(A· z+B)·(C · z+D)^-1, where

    A = 
    A_1A_2+B_1C_2+A_1Ψ̂_̂3̂C_2    if v_i is a +-gate
    
    A_1Ψ̂_̂3̂A_2+B_1C_2    if v_i is a ×-gate and is a right child of v
    
    A_1A_2+B_1Ψ̂_̂3̂^-1C_2   if v_i is a ×-gate and is a left child of v


    B = 
    A_1B_2+B_1D_2+A_1Ψ̂_̂3̂D_2    if v_i is a +-gate
    
    A_1Ψ̂_̂3̂B_2+B_1D_2    if v_i is a ×-gate and is a right child of v
    
    A_1B_2+B_1Ψ̂_̂3̂^-1D_2   if v_i is a ×-gate and is a left child of v


    C = 
    C_1A_2+D_1C_2+C_1Ψ̂_̂3̂C_2    if v_i is a +-gate
    
    C_1Ψ̂_̂3̂A_2+D_1C_2    if v_i is a ×-gate and is a right child of v
    
    C_1A_2+D_1Ψ̂_̂3̂^-1C_2   if v_i is a ×-gate and is a left child of v


    D = 
    C_1B_2+D_1D_2+C_1Ψ̂_̂3̂D_2    if v_i is a +-gate
    
    C_1Ψ̂_̂3̂B_2+D_1D_2   if v_i is a ×-gate and is a right child of v
    
    C_1B_2+D_1Ψ̂_̂3̂^-1D_2   if v_i is a ×-gate and is a left child of v


  * Output Φ' and halt.



Case 2 above is not explicitly dealt with in <cit.> as their
focus is on the existence of a log-depth formula equivalent to
Φ. In contrast to that, in our case we want to
algorithmically construct log-depth formula Φ' equivalent
to Φ. This makes the details of Case 2 crucial as the
construction of Φ' in Case 2 depends on whether
Φ̂_̂û_̂î≡ 0 or not. To solve this  instance we
need to recursively compute log-depth formula Ψ_3 equivalent to
Φ_u_i and then invoke algorithm of theorem
<ref> to carry out  test in NC with
oracle access to bivariate , as in Step (c).
 
We first prove the correctness of both the algorithms described above using induction on s, then we analyze the parallel complexity of both the algorithms. We will choose appropriate constants c, b during the proof.




  
Correctness of the algorithm Depth-Reduce 
We know that there exists a gate v∈Φ such that s/3< wt(v) ≤2s/3. As in proof of Lemma <ref> we can find such a gate v as required by Step 1 of the Depth-Reduce algorithm.  
Clearly, the formulas Φ_v and Φ_v← z are of size at most 2s/3. Using inductive assumption, we can construct a correct formula Ψ such that depth of Ψ is at most c log_2 2s/3 and Ψ≡Φ_v. Again using inductive assumption we can construct correct formulas A, B, C, D (which do not depend on z) of depth at most c log_2 2s/3+b such that the formula Δ = (A· z+B)·(C· z+D)^-1 is equivalent to Φ_v ← z.


Since Φ is equal to the formula obtained from Φ_v← z by replacing z by Φ_v and Φ is correct so from inductive assumption it follows that ĈΦ̂_̂v̂ + D̂≠ 0. 


As Ψ≡Φ_v, Δ≡Φ_v ← z and ĈΦ̂_̂v̂ + D̂≠ 0 from Lemma <ref> it follows that Φ' is correct and Φ'≡Φ. Since Φ' = (A·Ψ+B)·(C·Ψ+D)^-1 we get that depth of Φ' is at most c log_2 2s/3+b+4. By choosing constant c ≥b+4/(log_2 3 -1), we get that the depth of Φ' is at most c log_2 s. Completing the inductive argument for the correctness proof of the algorithm Depth-Reduce.  



  
Correctness of the algorithm Normal-Form
  In case (1) we know that there exists a balanced gate v=v_i. We have wt(Φ_v), wt(Φ_v ← z') ≤5s/6. So by inductive assumption we know that the formulas A_j,B_j, C_j, D_j for j∈{1,2} are correct, and their depths are at most c log_2 5s/6 + b. Now using compositionality of the z-normal forms as in Proposition 4.1 of <cit.> it follows that the formula Φ' = (A· z+B)·(C · z+D)^-1 is equivalent to Φ where A, B, C, D are A_1· A_2 + B_1 · C_2, A_1· B_2 + B_1 · D_2, C_1· A_2 + D_1 · C_2 and C_1· B_2 + D_1 · D_2 respectively. Also, clearly the depth of A, B, C, D is at most c log_2 5s/6 + b+2. By choosing c≥2/(log_2 6 - log_2 5) it follows that the depths of formulas A, B, C, D are at most c log_2 s+ b. 
  
Next we need to prove that Ĉπ̂+ D̂≠ 0 for any formula π such that Φ_z←π is correct where π' is any formula equivalent to π. So let π' be such that Φ_z←π' is correct and π≡π'. For simplicity lets denote formulas Φ_v and Φ_v← z' by α and β respectively. As Φ_z←π' is correct, it implies α_z←π' is correct. So by inductive assumption Ĉ_̂2̂π̂ + D̂_̂2̂≠ 0 for any π≡π'. Since Φ_z←π' is correct, it also implies β_z'←γ' is correct where γ'= (A_2·π' + B_2)· (C_2 ·π'+D_2)^-1. Now, since π≡π', we have γ'≡γ= (A_2·π + B_2)· (C_2 ·π+D_2)^-1. So by inductive assumption we get 

    Ĉ_̂1̂γ̂ + D_1    ≠    0 which implies
    Ĉ_̂1̂ [(Â_̂2̂·π̂ + B̂_̂2̂)· (Ĉ_̂2̂·π̂ +D̂_̂2̂)^-1]+D_1    ≠    0 which implies
    Ĉ_̂1̂ (Â_̂2̂·π̂ + B̂_̂2̂)+ D̂_̂1̂ (Ĉ_̂2̂·π̂ +D̂_̂2̂)    ≠    0 as Ĉ_̂2̂π̂ + D̂_̂2̂≠ 0
    So (Ĉ_̂1̂Â_̂2̂+ D̂_̂1̂Ĉ_̂2̂)π̂ + (Ĉ_̂1̂B̂_̂2̂+D̂_̂1̂D̂_̂2̂)    ≠    0 which implies
    Ĉπ̂+D̂   ≠    0
     
This completes the proof for case 1. 

To complete the inductive proof we need to prove that Ĉπ̂+ D̂≠ 0 for any formula π such that Φ_z←π is correct. Let π be such that Φ_z←π is correct. For simplicity lets denote formulas Φ_v and Φ_v← z' by α and β respectively. Since Φ_z←π is correct, it implies α_z←π is correct as α is a subformula of Φ. So by inductive assumption Ĉ_̂2̂π̂ + D̂_̂2̂≠ 0. Since Φ_z←π is correct, β being a subformula of Φ it also implies β_z'←γ is correct where γ= (A_2·π + B_2)· (C_2 ·π +D_2)^-1. 

By inductive assumption we get 

    Ĉ_̂1̂γ̂ + D_1    ≠    0 which implies
    Ĉ_̂1̂ [(Â_̂2̂·π̂ + B̂_̂2̂)· (Ĉ_̂2̂·π̂ +D̂_̂2̂)^-1]+D_1    ≠    0 which implies
    Ĉ_̂1̂ (Â_̂2̂·π̂ + B̂_̂2̂)+ D̂_̂1̂ (Ĉ_̂2̂·π̂ +D̂_̂2̂)    ≠    0 as Ĉ_̂2̂π̂ + D̂_̂2̂≠ 0
    So (Ĉ_̂1̂Â_̂2̂+ D̂_̂1̂Ĉ_̂2̂)π̂ + (Ĉ_̂1̂B̂_̂2̂+D̂_̂1̂D̂_̂2̂)    ≠    0 which implies
    Ĉπ̂+D̂   ≠    0
     
This completes the proof for case 1. 

Next we argue that case 1 and case 2 together cover all the
possibilities. To see this, we will argue that if there does not exist a unique u_i with wt(u_i)≥s/6 then there must exist a balanced gate. There are two possibilities: either for every
gate u_i, wt(u_i)≤s/6 or there are two or more gates
u_i's with wt(u_i)> s/6 If for every i∈ [ℓ],
wt(u_i) ≤s/6, we find smallest j such that
∑_i=1^j wt(u_i)>s/6. Clearly
∑_i=1^j wt(u_i)≤2s/6, which implies
wt(Φ_v), wt(Φ_v← z') ≤5s/6 for
v= v_i+1. So v is balanced. If there are two or more u_i's
such that wt(u_i)> s/6 then v be parent of gate u_i such
that i is a largest index with wt(u_i)> s/6. Clearly v
is a balanced gate. This proves that case 1, 2 together cover all
possibilities.

Assume that there is a unique i∈[ℓ] such that wt(u_i)> s/6. We first apply Depth-Reduce on formula Φ_u_i and get a log-depth formula Ψ_3 equivalent to Φ_u_i, we carry out this depth reduction to efficiently test if Φ_u_i≡ 0?. We will give details on this later when we figure out the parallel time complexity of the algorithm. Now when Φ_u_i≡Ψ_3 ≡ 0, clearly formula Φ≡Φ” where Φ” is a formula obtained from Φ by replacing sub-formula rooted at u_i by 0. As wt(u_i)> s/6, we have |Φ”|≤5s/6. So by inductive assumption, the correct sub-formulas A, B, C, D  of Ψ_4 obtained by recursive call Normal-Form(Φ”,z) have depth at most clog_2 5s/6+b ≤ clog_2 s+b and Ψ_4 ≡Φ”≡Φ. So it follows, Φ_z←π≡Φ”_z←π. Consequently Φ_z←π is correct iff Φ”_z←π is correct. So from inductive hypothesis it follows that Ĉπ̂ + D̂≠ 0 for any formula π such that Φ_z←π is correct. This proves the correctness of Normal-form procedure when Φ_u_i≡ 0.    


 
Now let Φ_u_i≢0. Let v be the parent of u_i. 

Below we discuss the case when v is ×-gate and u_i is a right child of v. 


We have Ψ_2 ≡Φ_v_i≡ (A_2· z +B_2)· (C_2· z + D_2)^-1. Let h_1=A_2· z+B_2 and h_2= C_2 · z+ D_2). So Φ_v_i≡ h_1 · h_2^-1. Now as v is ×-gate and v_i,u_i are left and right children of v respectively. So we get Φ_v ≡ h_1h_2^-1Φ_u_i≡ h_1h_2^-1Ψ_3. We have Ψ_1 ≡Φ_v← z'=(A_1z'+B_1)(C_1z'+D_1)^-1. So we get

    Φ   ≡    ( A_1 · (h_1h_2^-1Ψ_3)+B_1)· ( C_1 ·(h_1h_2^-1Ψ_3)+D_1)^-1
       ≡    (A_1 · h_1+B_1·Ψ_3^-1h_2)· h_2^-1Ψ_3 · [ (C_1· h_1+D_1 ·Ψ_3^-1h_2)· h_2^-1Ψ_3 ]^-1
       ≡    (A_1 · h_1+B_1 ·Ψ_3^-1h_2)· h_2^-1Ψ_3 ·Ψ_3^-1h_2 · (C_1· h_1+D_1·Ψ_3^-1h_2)^-1
       ≡    (A_1 · h_1+B_1 ·Ψ_3^-1h_2)·(C_1 · h_1+D_1·Ψ_3^-1h_2)^-1

By substituting values of h_1, h_2 and simplifying we get that Φ≡ (A· z+B)·(C · z+D)^-1 where A, B, C, D are A_1· A_2+B_1 ·Ψ_3^-1· C_2, A_1· B_2+B_1 ·Ψ_3^-1· D_2, C_1· A_2+D_1·Ψ_3^-1· C_2 and C_1· B_2+D_1 ·Ψ_3^-1· D_2 respectively as defined in Step 2(d). 

As wt(u_i)> s/6, clearly |Φ_v_i|, |Φ_v← z'| ≤5s/6. 
Since

    Ψ_1   =   (A_1z'+B_1)(C_1z'+D_1)^-1=Normal-Form(Φ_v ← z',z')
    Ψ_2   =   (A_2z+B_2)(C_2z+D_2)^-1=Normal-Form(Φ_v_i,z)


So by inductive assumptions the sub-formulas A_1, B_1, C_1, D_1 of Ψ_1 and the sub-formulas A_2, B_2, C_2, D_2 of Ψ_2 are correct and have depths at most c log_2 5s/6+b. As Ψ_3 = Depth-Reduce(Φ_u_i) and |Φ_u_i|< s by inductive assumption we get that the depth of Ψ_3 is at most clog_2 s. Clearly c log_2 5s/6+b ≤ c log_2 s for c≥b/log_2 6 - log_2 5). So from expressions for A, B, C, D it follows that the depth of A, B, C, D is at most depth of Ψ_3 plus 4. Which implies that the depth of A, B, C, D is at most c log_2 s + 4 ≤ c log_2 s + b if the constant b≥ 4. This gives us the desired bound on the depth of A, B, C, D.
To summarize if we choose constant b≥ 4 and choose constant c such that it satisfies all the lower bounds required in different steps of the above proof, we will get the desired bound on the depth of A, B, C, D. We can show that Ĉπ̂+D̂≠ 0 for any formula π such that Φ_z←π is correct. The proof is similar to one for Case (1), we additionally need to take into account ×-gate at v while composing z-Normal forms Ψ_1 and Ψ_2. We skip the details. 

When v is a v is a ×-gate and u_i is a left child of v, the composition of z-normal forms is easy as we do not need an oracle access for  as in the case discussed above when u_i is the right child. In the commutative case we can by default assume that u_i is the left child. Precisely for this reason Brent's construction <cit.> is independent of whether Φ_u_i≡ 0 or not.
 We skip the details of cases when v is a +-gate or v is
 ×-gate and u_i is the left child which can be handled
 similar to case (1). This proves the correctness of the procedure
 Normal-Form.
 
 
 
 

 Next we analyze the parallel time complexity of both the
 procedures. Let t_1(s), t_2(s) denote the parallel time
 complexities of the procedures Depth-Reduce and Normal-Form
 respectively. The step (1) of the Depth reduce procedure can be
 implemented in  so it has parallel time complexity
 (log_2 s)^k for some absolute constant k. As both the formulas
 Φ_v and Φ_v← z have sizes at most 2s/3, the
 parallel time complexity of step (2) is at most
 max(t_1(2s/3), t_2(2s/3)). So we get the following recurrence for
 t_1(s).

    t_1(s) ≤ (log_2 s)^a + max( t_1 ( 2s/3) ,  t_2(2s/3 ))

where a is an absolute constant.
Now we obtain recurrence for t_2(s). In Case (1) of Normal-Form when there exist a balanced gate v_i, we can find such a gate in . Both the formulas Φ_v and Φ_v← z' have the sizes at most 5s/6 so step 1(a) takes parallel time max(t_1(5s/6), t_2(5s/6)). In case (2) the formulas Φ_v← z', Φ_v_i and Φ” all have sizes at most 5s/6 and formula Φ_u_i has size at most s-1. So collectively we get the following recurrence for t_2(s)

    t_2(s)    ≤    (log_2 s)^b + max(  t_1 ( 5s/6) ,  t_2(5s/6 ) ,   t_1(s-1) )
       ≤    (log_2 s)^b + max(   t_2(5s/6 ) ,   t_1(s) )

for an absolute constant b. The upper bound t_1(s), t_2(s) ≤ (log_2 s)^c for sufficiently large constant c follows from an easy induction. Hence both the procedures can be implemented in deterministic . 
 

 





