Theory of Computing, Volume 1 (2005), pp. 149–176 http://theoryofcomputing.org

A Non-linear Time Lower Bound for Boolean Branching Programs

Miklós Ajtai

Received: October 6, 2004; revised: May 5, 2005; published: October 5, 2005.

Abstract: We give an exponential lower bound for the size of any linear-time Boolean branching program computing an explicitly given function. More precisely, we prove that for all positive integers k and for all sufficiently small ϵ > 0, if n is sufficiently large then there is no Boolean (or 2-way) branching program of size less than 2^{ϵn}which, for all inputs X ⊆ {0,1,...,n − 1}, computes in time kn the parity of the number of elements of the set of all pairs ⟨x,y⟩ with the property x ∈ X, y ∈ X, x < y, x + y ∈ X.

For the proof of this fact we show that if A = (a_{i,j})_{i=0,j=0}^{n} is a random n by n matrix over the field with 2 elements with the condition that “A is constant on each minor diagonal,” then with high probability the rank of each δn by δn submatrix of A is at least cδ|logδ|^{−2} n, where c > 0 is an absolute constant and n is sufficiently large with respect to δ.

(A preliminary version of this paper has appeared in the Proceedings of the 40th IEEE Symposium on Foundations of Computer Science.)

ACM Classification: F.2.2, F.2.3

AMS Classification: 68Q17, 68Q15

Key words and phrases: complexity theory, lower bounds, space complexity, branching programs, Hankel matrices, matrix rigidity

Authors retain copyright to their papers and grant “Theory of Computing” unlimited rights to publish the paper electronically and in hard copy. Use of the article is permitted as long as the author(s) and the journal are properly acknowledged. For the detailed

copyright statement, see http://theoryofcomputing.org/copyright.html.

\begin{matrix}c \\ ◯ \end{matrix} 2005 Miklós Ajtai

Miklós Ajtai

1 Introduction

1.1 The statement of the main result

A Boolean (or 2-way) branching program is a finite directed acyclic graph (which may contain parallel edges) with a unique source node, so that each non-sink node is labeled by one of the input variables x_{0},...,x_{n−1} , each non-sink node has outdegree two, each edge is labeled by an element of {0,1} so that the two outgoing edges of a non-sink node always get different labels, and each sink-node is labeled by an element of {0,1}. If an input is given we start from the unique source node and go along a path according to the following rule. If we are at node v and the label of v is the variable x_{i} then we leave v on the unique outgoing edge whose label is the value of x_{i}. This path will end in a sink node; the label of the sink-node is the output of the program at the given input, the length of the path is the computational time at the given output, the maximal length of a path in the graph that we may get from an input this way is the length (or depth) of the branching program. The number of nodes in the graph is the size of the branching program.

This model describes a very general way of computing where the computational time measures the number of accesses to the individual bits of the input and the size measures the number of different states of the machine performing the computations. We do not measure the computational time needed to determine the next state of our machine (that is, the next node in the graph along the path). We may also think about this model as a random access machine whose input registers contain a single input bit, with a working memory containing log_{2}M bits where M is the size of the branching program.

Our goal is to give an explicit function which cannot be computed with a Boolean branching program in linear time if the size of the branching program is 2^{ϵn}. The function has to assign to each {0,1}- sequence of length n a single {0,1}-value. We identify the set of all {0,1}-sequences of length n with the set of all subsets of {0,1,...,n − 1}, that is, our function f will assign to each subset X of {0,1,...,n − 1} a {0,1}-value. For such a set X let f(X) be the parity of the number of elements of the set of all pairs ⟨x,y⟩ with the property x ∈ X, y ∈ Y, x < y, and x + y ∈ X. We will say that f(X) is the parity of interior sums for the set X, where the expression “interior” refers to the fact that both the terms in the sum and the sum itself must be in X.

Our main result is that the parity of interior sums for a set of n elements cannot be computed with a Boolean branching program in linear time if the size of the branching program is 2^{ϵn}(see Theorem 3.4).

1.2 The history of the problem and related results

1.2.1 Boolean and R-way branching programs

One of the main goals of complexity theory is to describe explicitly given functions which cannot be computed in certain computational models with specified amount of resources. Branching programs form one of the most general models of computation, e.g. random access machines with memory M and running time t can be described by branching programs of size 2^{M} and time (depth) t. Because of the generality and simplicity of the model and its mentioned close connection to the practical random access models of computation, finding lower bounds for explicitly given functions in the branching program model in general, and with the given values of parameters in particular (linear time and sublinear memory) was always considered a question of great importance.

A Non-linear Time Lower Bound for Boolean Branching Programs

A generalization of the Boolean branching programs is the computational model of R-way branching programs. Since most of the results that we use in our proofs were established for R-way branching programs, we describe briefly its definition. The computation is done in the same way, along a path of a directed graph as in the Boolean case, with the following differences. A set Γ with R elements is given, the elements of Γ are the possible values of the input variables. Each non-sink node has outdegree R, and the outgoing edges are labeled by the elements Γ so that the R outgoing edges have R different labels. Each sink node is labeled by an element of Γ. If an input is given, that is, we assign an element of Γ to each of the input variables x_{1},...,x_{n}, then we follow a path of the graph in the following way. We start at the unique source node. If we are at node v and the label of node v is the variable x_{i} then we leave v on the unique outgoing edge whose label is the element of Γ assigned to the variable x_{i}. This path will end in a sink node. The element of Γ which is the label of this sink node is the output of the R-way branching program. The value of R, in the results most interesting for us, is n^{c} where c is a constant. (This corresponds to the random access machines where each register can contain clog_{2}n bits.)

1.2.2 Branching programs with many output bits, and the time segmentation method

The computational model of R-way branching programs was introduced by Borodin and Cook [8], who proved a time-space trade-off for sorting n integers. This work also introduced a method for proving lower bounds about R-way branching programs in the special case where the number of output bits is relatively large compared to the time allowed for the computation. Several other lower bounds and timespace trade-offs of similar nature were given, see e. g. Abrahamson [1, 2], Beame [5], Karchmer [11], Reisch and Schnitger [12], and Yesha [14]. These lower bound proofs have a common high-level structure, namely the time is cut into short intervals and we use the fact that during such an interval any information that we can use about the past must be contained in the limited memory at the beginning of the interval. In particular if many output bits are provided in a single time interval, then these may depend only on those input values which are accessed during this time interval and the the content of the memory at the the beginning of the interval.

1.2.3 Lower bounds for explicit functions and decision problems

Using the same high level proof structure, and other new ideas, Beame, Saks and Jayram^{1} [6] gave a lower bound on the computational time for an explicitly given function with a Boolean branching program of size 2^{o(n)}. Namely they proved that there is an ϵ > 0 so that the question whether the quadratic form σ^{T}Qσ is zero, (where σ is the input, a {0,1}-vector of length n, and Q is the n × n Sylvester matrix over the field with three elements) cannot be decided with a branching program of length (1 + ϵ)n and of size 2^{o(n)}. (The proof shows that the theorem holds for ϵ = .0178.) This is the best previously known lower bound in the direction of our main result. In the same paper they gave a nonlinear lower bound on the length of an R-way branching program computing an explicitly defined function, (similar to the function they used in the Boolean case.) More precisely they prove that for all k there is an r_{k} so that for all sufficiently large n there is an (explicitly given) 0-1 valued function g(x_{1},...,x_{n}) of n variables such that: (a) each variable is takes its values from a set of size r_{k} and (b) there is no r_{k}-way and size n^{c} branching program which computes g(x_{1},...,x_{n}) in depth kn.

1T.S. Jayram, formerly Jayram S. Thathachar

Theory of Computing, Volume 1 (2005), pp. 149–176 151

The author of the present paper proved [4] that the element distinctness problem (where each “element” is the value of a variable) cannot be decided with an R-way branching program, for R = clog_{2}n, in length linear in n if the size of the program is at most 2^{ϵn}, provided that c ≥ 2. (If the problem is to find two elements whose Hamming distance is smaller than \frac{1}{4}clog_{2}n then for a similar lower bound on the length the necessary restriction on the size is only 2^{ϵnlog_{2}n}.) These proofs are based on the analysis of certain combinatorial properties of the input, which are very similar to the combinatorial properties used in [6]. The high level structure of the proof still follows the time segmentation idea described earlier. Since the present proof uses some of the technical lemmata of [4], we will give later a more detailed description of its techniques. At this point we sketch only some of the basic ideas of the proof in [4]. Since these are also related to the proof methods of [6], this will show the additional ideas that are needed to make the time segmentation method work when the number of output bits is small.

1.2.4 Lower bounds for binary functions and relations

It is shown in [4] that if a function f can be computed in linear time with the given restrictions on the size then there are two large disjoint subsets, W_{1},W_{2}, of the set of the input variables and an input χ with the following properties. For each i = 1,2 we may change the input χ in many different ways by changing the values of the variables in W_{i} only, so that the output does not change. Moreover, for i = 1,2 we can select a large set of changes Y_{i} so that even if we perform a change from Y_{1} (on the values of the variables in W_{1}) and another one from Y_{2} (on the values of the variables in W_{2}) simultaneously, the output remains unchanged.

In the case of the element distinctness problem we are able to chose an input χ which meets these requirements with the additional property that χ (which is a list of n integers) consists of pairwise distinct integers. Therefore, if our branching program solves the element distinctness program, its output is, say,

1. However we can prove the for a fixed i = 1,2 the inputs that we get from χ through the changes in Y_{i}, take more than \frac{n}{2} different values on the set of variables W_{i}. Therefore there will be an integer x so that for both i = 1,2, x will be a value of a variable from W_{i} if we perform suitable change on χ from Y_{i}. Consequently performing both suitable changes simultaneously we get an input which contains x twice and still the unchanged output is 1. This contradicts the assumption that the program solves the element distinctness problem.

Similar ideas are used for the other relations, or functions in the mentioned lower bounds. In each case we need a function F (x,y) or a relation R(x,y) with two variables so that if we can separately change x and y in many different ways then among these changes there will be two so that performing them simultaneously we are able to change the value of F (x,y) or R(x,y). If R is the equality predicate then, as we have seen, this can be guaranteed if both sets of changes produces at least \frac{n}{2} different input values. In the case of the Hamming distance problem described above the situation is even better since \frac{n}{2} can be replaced by n^{1−ϵ′} for some small constant ϵ′> 0 (see [4]). (This is the reason that the proof of the lower bound for the Hamming distance problem is much simpler and gives a stronger result than the proof for the element distinctness problem.)

1.2.5 Quadratic forms and rigidity

The binary function F (x,y) can be also defined by a quadratic form x^{T}By. Assume that, as before, x and y independently run over large sets and now we want to guarantee that the x^{T}By is not constant. Motivated by similar considerations, quadratic forms were studied by Borodin, Razborov, and Smolensky [9], Jayram [13], and Beame, Saks, and Thatachar [6]. The result in this direction that we will use in our paper is the following. (This was proved in more general forms in [9], [13], and [6], and also follows from the results of [10].) Suppose that the rank of the matrix B is r and x resp. y are taking values independently from m_{1} resp. m_{2} dimensional subspaces of an m dimensional vectorspace. If m_{1}+ m_{2}+ r > 2m then the quadratic form x^{T}By is not constant.

As we described earlier, in the lower bound proofs we can usually guarantee only that x and y can take values independently only in some limited sense, namely we can apply independent changes to two disjoint sets of variables. In [6] the mentioned property of the quadratic forms is applied in the following way. The lower bound is proved for a function of the form x^{T}Ay where A is a suitably chosen, explicitly given, matrix over a finite field. This matrix has the property that each δn × δn submatrix which does not contain elements from the main diagonal is of rank at least δ^{2}n where δ > 0 is a small constant. (This may be considered as a rigidity property of the matrix A.) The input variables of the branching program take values from the field F. We pick two large sets of independent changes on two disjoint sets of variables of at least δn elements. The submatrix of A formed from the corresponding rows and columns will be the matrix B in the mentioned property of quadratic forms. This way it is possible to guarantee that, roughly speaking, under independent changes on these sets of variables, the quadratic form cannot remain constant, which makes the lower bound proof possible.

In the present paper we will follow the same strategy for our proof with the following improvements. We use two-way branching programs with a single output bit which creates three new problems. (1) It is more difficult to prove the existence of the two disjoint sets of variables which admit many independent changes that leave the output of the branching program unchanged. For this we use the machinery worked out in [4]. (2) The explicitly given matrix of [6] is a Sylvester matrix over the field F and so the size of the field must be at least n. We need something similar for F_{2}, the field with two elements. We do not give an explicit construction for such a matrix, but a random construction which depends only on a linear number of random bits which can be included in the input. (3) it is not enough for us if the rank of the submatrices of sizes δn × δn are δ^{2}n, we need much larger ranks; what we prove will be δ|logδ|^{−2} n.

1.2.6 Summary of the history of the problem

Summarizing the historical developments about the lower bound techniques for branching programs, we can say that there were two parallel developments. The first is the time segmentation method which later was supplemented by the technique of considering changes of the values of variables on two disjoint sets: [8],[6],[4]. The second is the development of the algebraic techniques about quadratic forms based on matrices with rigidity properties, providing explicitly defined functions which were suitable for the lower bound proof techniques mentioned in the first direction of developments: [9],[13],[6]. The present paper uses the techniques of both of these directions.

1.3 Subsequent developments

A preliminary version of this paper was published in [3] containing all of the essential elements of the proofs presented here. Since then, the main result of this paper was further improved by Beame, Saks, Sun, and Vee in [7] by making the time/space lower bounds sharper and generalizing the theorem for the case of probabilistic branching programs. Their proofs use the results and techniques of the present paper (together with methods of different nature).

2 Overview of the proof

2.1 A lower bound for a nonexplicit function

Our proof in the present paper uses a technical lemma of the element distinctness result. As we have mentioned already in the introduction, it is shown in [4] that if a function f can be computed in linear time with the given restrictions on the size then there are two large disjoint subsets, W_{1},W_{2}, of the set of the input variables and an input χ so that for each i = 1,2 we may change the input χ in many different ways by changing only the values of the variables in W_{i} so that the output does not change; moreover these changes can be performed simultaneously on W_{1} and W_{2} so that the output still does not change. The ratio between the sizes of the sets W_{i} and the logarithm of the number of changes has a crucial importance in the proofs of the present paper. (A precise statement of this result is given in Lemma 3.5 below.)

We use this result to show that a quadratic form (which is not given explicitly) cannot be computed in linear time. The algebraic part of this proof (Lemma 3.11) is a theorem proved by Borodin, Razborov, and Smolensky [9] (and in more general forms by Jayram [13] and Beame, Saks, and Jayram [6]). We reduce the problem of giving a quadratic form with the required properties to a question about the ranks of the submatrices (or minors) of the matrix generating the quadratic form in a similar way as is done in [6]. In both cases the goal is to get a matrix A so that each ⌊δn⌋ by ⌊δn⌋ submatrix of the matrix A has rank at least ψ(δ)n, for each δ > 0, provided that n is sufficiently large with respect to δ, where the function ψ should be as large as possible. The Sylvester matrices used in [6] are explicitly given examples of such matrices with ψ(δ) = δ^{2}, provided that we consider only submatrices that do not contain any elements of the main diagonal. (This restriction does not affect the applicability of the matrix to the lower bound proof.)

2.2 Decreasing the randomness needed

Definition 2.1. We will call an n×n matrix A = (a_{i,j}) a Hankel matrix if ∀i,j,k,l ∈ {0,1,...,n−1},i+ j = k +l implies a_{i,j} = a_{k,l}. In other words A is a Hankel matrix iff it is constant across minor diagonals.

Remark 2.2. A Hankel matrix is determined by only 2n − 1 suitably chosen entries, e.g. by entries of the first row and last column. If a matrix is constant along all diagonals it is called a Toeplitz matrix. Reversing the ordering of the rows creates a one-to-one correspondence between Toeplitz matrices and Hankel matrices. Therefore all of our results concerning the ranks of Hankel matrices remain valid for Toeplitz matrices as well.

We show that if A is a random n by n Hankel matrix over the field with 2 elements, with uniform distribution on the set of all such matrices, then with high probability the described property about the ranks of the submatrices holds with ψ(δ) = cδ|logδ|^{−2} for an absolute constant c > 0. As a consequence, using also the mentioned lemma from [4], we are able to show that if Ãis the matrix that we get from A by replacing each entry in the main diagonal and above by 0, then the quadratic form ⟨Ãx,x⟩, where x is the input vector, cannot be computed with a branching program of linear length and size at most 2^{ϵn}.

2.3 From a non-explicit function to an explicit function

Of course this is not an explicitly given function; we only know that the lower bound holds for almost all matrices. However, we got the matrix by randomizing only 2n−1 bits. Therefore if we include these bits in the input, then we get an explicitly given problem (with 3n − 1 input variables, where the described tradeoff holds between the length and size of any branching program computing the quadratic form). In other words, if A(y), y = ⟨y_{0},...,y_{2n−2} ⟩ denotes the Hankel matrix with a_{i,j} = y_{i+j} , then ⟨Ã(y)x,x⟩ cannot be computed in the given length and size from the input ⟨x,y⟩.

2.4 Obtaining a lower bound for the parity of interior sums problem

Assume now that A = (a_{i,j}) is a fixed Hankel matrix so that ⟨Ãx,x⟩ cannot be computed with a branching program with the given restrictions. Suppose that x = ⟨x_{0},...,x_{n−1} ⟩ and X = {i | x_{i} = 1}, and

D = {i + j | a_{i,j} = 1,i,j ∈ {0,...,n − 1}} .

It is easy to see that ⟨Ãx,x⟩ is the parity of the number of all pairs ⟨i,j⟩, i ∈ X,j ∈ X with the property i < j and i + j ∈ D.

This will already imply that if two subsets, X,Y, of the set {1,2,...,2n} are given, then the problem of computing the parity of the number of elements of the set of all pairs ⟨i,j⟩ with the property i ∈ X, j ∈ X, i < j, i + j ∈ Y cannot be solved by a branching program of linear length and of size at most 2^{ϵn}. (The set D defined above will play the role of Y.) It will not be difficult to make a single set from the two sets X,Y, by taking into account the sizes of their elements, and so we will get that the task of computing, given as input an X ⊆ {1,2...,n}, the parity of the number of elements of the set of all pairs ⟨i,j⟩ with the property i ∈ X, j ∈ X, i < j, i + j ∈ X cannot be accomplished by a branching program of linear length and of size at most 2^{ϵn}.

Finally we note that our results about random Hankel matrices remain true over any field with appropriate modifications. (See the remarks after Lemma 4.5, Lemma 4.7 and Lemma 4.9. See also the comment about the applicability of these modified versions to generalizations of Theorem 3.4 in the proof of Lemma 3.11.)

3 The reduction of the lower bound to a problem about Hankel matrices

3.1 The statement of Theorem 3.4

In this section we reduce the problem of giving a lower bound for the time needed to solve the problem described in the introduction to the existence of a matrix A which can be constructed from n bits with the property that each large submatrix of A has also relatively large rank.

Definition 3.1. If X,Y are sets then Func(X,Y) will denote the set of all functions, defined on X, taking values in Y.

A branching program as we will define below will be what is usually called a (deterministic) Boolean or 2-way branching program indicating that the input variables take their values from a set of size 2.

Definition 3.2. A branching program ℬ with n input variables x_{0},...,x_{n−1} is a five tuple

                            ⟨𝒢,start,sink,var,val⟩ ,

with the following properties

(a). 𝒢 is a finite directed acyclic graph, which may contain parallel edges

(b). start is the unique source node of 𝒢,

(c). var is a function defined on the non-sink nodes of 𝒢 with values in the set {x_{0},...,x_{n−1} } of variables,

(d). out is a function defined on the set of sink nodes of 𝒢 with values in {0,1},

(e). val is a function defined on the set of edges with values in {0,1},

(f). each non-sink node has out-degree 2, and the function val takes different values on the two outgoing edges.

An input for the branching program ℬ is a {0,1}-assignment of the variables x_{i}. (Instead of such an assignment we usually will think about an input as a {0,1}-valued function η defined on {0,1,...,n−1} where η(i) is the value of x_{i}.) If an input is given, then starting from start we go along a path in the graph in the following way. When we are at a non-sink node v then we look at the value of the variable var(v) and leave the node along the edge e where the value of val(e) is the same as the value of this variable. Since the graph is acyclic and finite, this way we will reach a sink-node w. out(w) will be the output of the branching program at the given input. The number of edges along the path determined this way by the input is the computational time of the branching program at the given input. The maximal computational time for the set of all inputs (that is, the maximal length of all paths arising from an input in the given way) is the length of the branching program. The size of the branching program is the number of nodes of 𝒢.

Definition 3.3. Assume that X is a subset of {0,...,n − 1}. N_{+} (X) will denote the number of all pairs x,y ∈ X, x < y so that x + y ∈ X.

The following theorem is the main result of the present paper. It states that the parity of the interior sums of a subset of 0,1,...,n − 1 cannot be determined by a branching program of size 2^{ϵn} in linear time.

Theorem 3.4. For all positive integers k, if ϵ > 0 is sufficiently small and n is sufficiently large then there is no branching program ℬ with n inputs, of length at most kn and of size at most 2^{ϵn}, which for all inputs η computes the parity of N_{+} (X_{η}) where X_{η} = {i ∈ {0,1,...,n − 1} | η(i) = 1}}

3.2 Results from earlier works

In the proof we will use the following lemma, Lemma 3.5, which is a consequence of Lemma A1 proved in [4] (called Lemma 9 in that paper). The proof of Lemma 3.5 from Lemma A1 is almost identical to the proof of Theorem 4 from Lemma 9 in [4] and does not require any new ideas. We describe this proof (of Lemma 3.5 from Lemma A1) in the last section.

The remaining part of the paper, starting with Lemma 3.7, is self-contained. We begin with the definitions needed to understand the statement of Lemma 3.5.

Definitions.

1. An input (of a branching problem with n input variables) is a function χ defined on {0,1,...,n−1} with values in {0,1}. A partial input is a function η defined on a subset of {0,1,...,n − 1} with values in {0,1}.

2. Assume that χ is an input and η is a partial input. Then χ ≀ η will denote the input which is identical to η on domain(η) and identical to χ on domain(χ)\domain(η).

3. If δ ∈ {0,1} and ℬ is a branching program, then ℬ^{−1} (δ) will denote the set of all inputs η so that the output of ℬ at input η is δ.

Lemma 3.5. For all positive integers k, if σ_{1} > 0 is sufficiently small with respect to k, σ_{2} > 0 is sufficiently small with respect to σ_{1}, ϵ > 0 is sufficiently small with respect to σ_{2}, n is sufficiently large with respect to ϵ, ℬ is a branching program with n inputs of length at most kn and of size at most 2^{ϵn}, and δ ∈ {0,1} so that |ℬ^{−1} (δ)| ≥ 2^{n−1} , then there exist a χ ∈ ℬ^{−1} (δ), λ ∈ (σ_{2},σ_{1}), μ ∈ (σ_{2},σ_{1}), W_{i} ⊆ {0,1,...,n−1}, i = 1,2, and sets of partial inputs Y_{i}, i = 1,2 defined on W_{i} satisfying the following conditions:

(1). for all i ∈ W_{1} and j ∈ W_{2} we have i < j,

(2). |W_{1}| = |W_{2}| = μn,

(3). |Y_{1}|,|Y_{2}| ≥ 2^{μn−λn} ,

(4). μ^{1+ \frac{1}{100k}} ≥ 2λ, and

(5). for all η_{1} ∈ Y_{1}, η_{2} ∈ Y_{2}, we have (χ ≀ η_{1}) ≀ η_{2} ∈ ℬ^{−1} (δ).

3.3 Branching programs and matrix rigidity

Definition 3.6. Assume that A is an n by n matrix over the field F and f is a real-valued function defined on (0,1]. We say that the matrix A is f-rigid if for each q = 1,...,n and for each q by q submatrix B of A we have that the rank of B is at least f(\frac{q}{n})n.

The proof of Theorem 3.4 is based on Lemma 3.7 and Lemma 3.9 described below.

Lemma 3.7. There is a δ > 0 so that, for all γ > 0, if the function g(x) is defined by g(x) = δx|logx|^{−2} if x ∈ (γ, \frac{1}{2}) and g(x) = 0 otherwise, then for each sufficiently large positive integer n there is an n by n Hankel matrix A over F_{2}, so that A is g-rigid.

Remark 3.8. It would be much easier to prove the lemma with g(x) = δ^{2}x, though this is not enough for the present application.

We will prove Lemma 3.7 in the next section; more precisely, we will prove (Theorem 4.2) that a random matrix A taken with uniform distribution on the set of all Hankel matrices meets the requirements of the Lemma with high probability.

Definitions.

1. Assume that η is a function with values in {0,1} defined on {0,1,...,n − 1}. u_{η} will denote the n-dimensional vector ⟨η(0),...,η(n − 1)⟩

2. The inner product of the n-dimensional vectors u,v will be denoted by u · v.

3. Assume that A = {a_{i,j}}_{i=0,j=0}^{n−1} is an n by n matrix. Ãwill denote the n by n matrix that we get from A by keeping every entry of A below the main diagonal and replacing all other entries by 0. In other words Ã= {b_{i,j}}_{i=0,j=0}^{n−1} , where b_{i,j} = a_{i,j} for all i > j and b_{i,j} = 0 for all i ≤ j, i = 1,...,n, j = 1,...,n.

Lemma 3.9. For all positive integers k, if σ_{1} > 0 is sufficiently small with respect to k, σ_{2} > 0 is sufficiently small with respect to σ_{1}, ϵ > 0 is sufficiently small with respect to σ_{2}, and n is sufficiently large with respect to ϵ, then the following holds. Assume that the function f is defined on (0,1] by f(x) = x^{1+ \frac{1}{100k}} if x ∈ (σ_{1},σ_{2}) and f(x) = 0 otherwise. If A is an f-rigid n by n matrix A over F_{2} then there is no branching program ℬ with n inputs of length at most kn and of size at most 2^{ϵn}which, for all inputs η, computes Ãu_{η} · u_{η}.

Remark 3.10. We use the matrix Ã instead of A in the expression Ãu_{η} · u_{η} at the conclusion of the lemma, since over a field of characteristic 2 and for a symmetric matrix A, almost all of the terms of Au_{η} · u_{η} will have 0 coefficients.

Proof of Lemma 3.9. Assume that, contrary to our statement, there is a branching program ℬ with the given properties which computes Ãu_{η} · u_{η}. We apply Lemma 3.5 with the given values of k,σ_{1}.σ_{2},ϵ,n and with the given ℬ. According to Lemma 3.5 there exist δ ∈ {0,1}, χ ∈ ℬ^{−1} (δ), λ,μ ∈ (σ_{2},σ_{1}), and W_{i},Y_{i}, i = 1,2 with the properties listed in Lemma 3.5. Let v = ⟨v_{0},...,v_{n−1} ⟩ be an n dimensional vector over F_{2} defined in the following way. For all i ∉ W_{1} ∪ W_{2} let v_{i} = χ(i) and for all i ∈ W_{1} ∪ W_{2} let v_{i} = 0. Recall that for i = 1,2, Y_{i} is a set of functions from W_{i} to {0,1}. We define a vector w^{(ξ)} = ⟨w_{0}^{(ξ)},...,w_{n−1}^{(ξ)} ⟩ for all ξ in Y_{1}∪ Y_{2}. If i ∈ domain(ξ) then w_{i}^{(ξ)} = ξ(i), if i ∉ domain(ξ) then w_{i}^{(ξ)} = 0. Let g_{i} be the following function defined on Y_{i}: for all ξ ∈ Y_{i}, g_{i}(ξ) = Ã(v + w^{(ξ)}) · (v + w^{(ξ)}). Since the functions g_{i} take at most two different values there are Y′_{i}⊆ Y_{i} so that |Y′_{i}| ≥ \frac{1}{2}|Y_{i}| and g_{i} is constant on Y′_{i}for i = 1,2. Assume now that ξ_{1} ∈ Y′_{1}, ξ_{2} ∈ Y′_{2}and let η = (χ ≀ ξ_{1}) ≀ ξ_{2}. By Lemma 3.5, η ∈ H and therefore

Ãu_{χ} · u_{χ}= Ãu_{η} · u_{η} = Ã(v + w^{(ξ_{1})}+ w^{(ξ_{2})}) · (v + w^{(ξ_{1})}+ w^{(ξ_{2})})
= −Ãv · v + g_{1}(ξ_{1}) + g_{2}(ξ_{2}) + Ãw^{(ξ_{1})}· w^{(ξ_{2})}+ Ãw^{(ξ_{2})}· w^{(ξ_{1})} .

Ãu_{χ} ·u_{χ} and Ãv·v do not depend on the choices of ξ_{1},ξ_{2}. By the definition of Y′_{1}and Y′_{2}, g_{1}(ξ_{1})+g_{2}(ξ_{2}) is constant on Y′_{1}×Y′_{2}. These facts imply that Ãw^{(ξ_{1})}·w^{(ξ_{2})}+Ãw^{(ξ_{2})}·w^{(ξ_{1})}, as a function of ξ_{1},ξ_{2}, is also constant on Y′_{1}× Y′_{2}. Condition (1) and the definition of Ãimplies that Ãw^{(ξ_{2})}· w^{(ξ_{1})} is identically 0 on Y′_{1}× Y′_{2}; therefore Ãw^{(ξ_{1})}· w^{(ξ_{2})} is constant on Y′_{1}× Y′_{2}. Let V_{0} be the vectorspace all F_{2}-valued functions defined on {0,...,n − 1}, and let V_{i}, i = 1,2, be the subspace of functions that vanish outside W_{i}. The dimension of V_{i} is μn. We may assume that Y_{i},Y′_{i}⊆ V_{i}. Let ι_{1} be the natural embedding of V_{1} into V_{0} and let π_{2} be the orthogonal projection of V_{0} onto V_{2}. B will be the linear map of V_{1} into V_{2} defined by Bx = π_{2}Ãι_{1}x. For all ξ_{1} ∈ V_{1}, ξ_{2} ∈ V_{2} we have Ãw^{(ξ_{1})}·w^{(ξ_{2})} = Bξ_{1}·ξ_{2}. If we fix the bases in both V_{1} and V_{2} which consist of those functions which take the value 1 at exactly one point and 0 everywhere else, then the matrix of B is a submatrix of Ãconsisting of those entries whose column numbers are in W_{1} and row numbers are in W_{2}. By Condition (1) this submatrix of Ãis identical to the corresponding submatrix of A. Therefore by the f-rigidity of A, the rank of B is at least μ^{1+ \frac{1}{100k}} n. We apply Lemma 3.11 (below) with V_{1}, V_{2}, m → μn, X → Y′_{1}, Y → Y′_{2}and B. Condition (3) implies that

|Y′_{i}| ≥ \frac{1}{2}|Y_{i}| ≥ 2^{μn−λn−1} .

Therefore, according to Lemma 3.11, the fact that Bx · y is constant on γ_{1}(Y_{1}) × γ_{2}(Y_{2}) implies that 2(μn − λn) + μ^{1+ \frac{1}{100k}} n ≤ 2μn. This is however impossible since, by Condition (4), μ^{1+ \frac{1}{100k}} > 2λ.

The following lemma, in more general forms, is proved in [9], [13], [6], and also follows from the results of [10]. To make the paper more self contained we provide a proof.

Lemma 3.11. Assume that V_{1}, V_{2} are m-dimensional vectorspaces over the field F_{2}, X ⊆ V_{1},Y ⊆ V_{2}, |X| ≥ 2^{m_{1}}, |Y | ≥ 2^{m_{2}} and B is a linear map of V_{1} into V_{2} so that the rank of B is at least r. If m_{1}+m_{2}+r > 2m then the function Bx · y, x ∈ X, y ∈ Y is not constant on X × Y.

Proof of Lemma 3.11. Let x_{0} be an arbitrary but fixed element of X and let X′= {x−x_{0} | x ∈ X}. Clearly |X| = |X′| and if Bx · y is constant on X × Y then Bx · y is identically 0 on X′× Y. Therefore it is enough to prove that the assumptions of the lemma imply that Bx · y is not identically 0 on X × Y. Assume that, contrary to our assertion, it is identically 0. Let H be the subspace in V_{1} generated by X and G be the subspace in V_{2} generated by Y. We have BH · G = 0, that is, the subspaces BH and G are orthogonal. Therefore dim(BH) + dim(G) ≤ m, where dim(W) denotes the dimension of the subspace W. Since the rank of B is at least r we have that dim(BH) ≥ dim(H) − (m − r). We have dim(H)−(m−r)+dim(G) ≤ m. The lower bound on the sizes of the sets X,Y imply the following lower bound on the dimensions of the subspaces generated by them: dim(H) ≥ m_{1}, dim(G) ≥ m_{2}. This simply follows from the fact that a d-dimensional subspace has 2^{d} elements. We have m_{1}− (m − r) + m_{2} ≤ m, that is, m_{1}+ m_{2}− r ≤ 2m in contradiction to our assumption.

Remark 3.12. The lower bounds on dim(H) and dim(G) remain true even if the field has characteristic different from 2, but we assume that the elements of X and Y have only {0,1} coefficients in a suitably chosen basis of V_{1} and V_{2}. See Lemma 7 of [13]. This is important for the generalization of Theorem 3.4 for fields with other characteristics.

3.4 The proof of the main result

Proof of Theorem 3.4. Assume that, contrary to our assertion, there is a branching program ℬ with the given parameters which computes the parity of N_{+} (X). Let m = ⌊\frac{n}{10}⌋. We apply Lemma 3.9 with n → m, k → ck, where c is a sufficiently large absolute constant and ϵ → \frac{ϵ}{2}. Assume that σ_{1}, σ_{2} are picked with the properties described in the lemma.

Let g be the function defined in Lemma 3.7. Applying Lemma 3.7 with n → m, γ → σ_{2} we get that there is an m by m g-rigid matrix A = (a_{i,j}) over F_{2}. If σ_{1} is sufficiently small with respect to δ, then A will be f-rigid as well. Therefore by Lemma 3.9 there is no branching program of size at most 2^{\frac{ϵ}{2}n} which computes u_{ζ} Ã· u_{ζ} in time ckn for all ζ, where ζ is an F_{2}-valued function defined on {0,1,...,m − 1}. Let D = {i + j | a_{i,j} = 1} and

X_{ζ} = {i ∈ {0,1,...,m − 1} | ζ(i) = 1} .

For any pair of sets of integers X,Z let N_{+} (X,Z) be the number of pairs x,y, x < y so that x ∈ X, y ∈ X and x+y ∈ Z. The statement of Lemma 3.9 in our case is that the parity of N_{+} (X_{ζ},D) cannot be decided by a branching program with the given restrictions on its parameters. We show that this problem can be reduced to the problem of determining the parity of N_{+} (X_{η}) for a suitably chosen η ∈ Func(n,2) in a way which can be implemented by a linear-time branching program. Therefore our indirect hypothesis will contradict to Lemma 3.9. η is defined in the following way.

We define first two sets U_{1},U_{2}. U_{1} = 2m + X_{ζ}, U_{2} = 4m + D. Let η be the unique element of Func({0,1,...,n − 1},{0,1}) so that X_{η} = U_{1} ∪ U_{2}. Clearly, if x,y ∈ X_{ζ}, x < y, and x + y ∈ D then 2m + x ∈ X_{η},2m + y ∈ X_{η}, 2m + x < 2m + y, and (2m + x) + (2m + y) ∈ X_{η}. Conversely, assume that z,w ∈ X_{η}, z < w and z + w ∈ X_{η}. It is easy to see that this implies z,w ∈ {2m,...,3m − 1} and therefore z − 2m,w − 2m ∈ X_{ζ}, z − 2m < w − 2m, and (z − 2m) + w(−2m) ∈ X_{ζ}. Therefore N_{+} (X_{ζ},D) = N_{+} (X_{η}). We claim that each value of η can be computed in constant time by a branching program, and to do this the size of our program must be increased only by a factor of two since the extra memory needed for this step is only one bit. Indeed, assume that we want to determine the value of η(i) for some i ∈ {0,1,...,n − 1}. First the program decides whether i ∈ U_{1} by checking whether ζ(i − 2m) = 1. If not, then η(i) = 0. If ζ(i − 2m) = 1, then it has to decide whether i ∈ U_{2}. Since D is part of the input this can be decided by checking whether i − 4m ∈ D. If the anser is no then η(i) = 0, if the answer is yes then η(i) = 1. Therefore we have reduced the problem of determining the parity of N_{+} (X_{ζ},D) to the problem of determining the parity of N_{+} (X_{η}).

4 Random Hankel matrices

4.1 The statement of the result

In this section we show that with a positive probability all large submatrices of a random Hankel matrix have relatively large ranks.

Definition 4.1. The field with q elements will be denoted by F_{q}.

Theorem 4.2. There exists a c_{1} > 0 so that, for all c_{2} > 0, if n is sufficiently large then the following holds: Assume that A = {a_{i,j}}, i = 0,...,n − 1, j = 0,...,n − 1 is a random n by n Hankel matrix over F_{2}, taken with uniform distribution on the set of all such matrices. Then with a probability greater than \frac{1}{2}, A has the following property:

(6). Suppose S = {s_{0},...,s_{q−1} }, T = {t_{0},...,t_{q−1} } are subsets of {0,...,n − 1} with q elements, where c_{2}n < q < \frac{n}{2}, and B_{S,T}= (a_{s_{i},t_{j}}), i = 0,...,q−1, j = 0,...,q−1 is the submatrix of A consisting of those entries whose row numbers are in S and column numbers are in T. Then the rank of B_{S,T} is at least c_{1}|log(\frac{q}{n})|^{−2} q.

4.2 Sketch of the proof

4.2.1 A natural but unsuccessful attempt

The most natural way to prove the statement of the theorem would be the following. Assume that the sets S,T are fixed. We give an upper bound M on the probability p_{S,T} of the event that, for the randomization of A, the matrix B_{S,T}defined for the fixed sets S and T has rank smaller than c_{1}|log(\frac{q}{n})|^{−2} . If M multiplied by the number of choices for the pair ⟨S,T ⟩ is smaller than \frac{1}{2} then the assertion of the theorem clearly holds.

Unfortunately a proof of this type cannot work. Indeed if q = cn then the number of pairs ⟨S,T ⟩ is about 2^{2c(log \frac{1}{c})n}. On the other hand for a fixed pair S,T, in the worst case, the number of minor diagonals of A intersected by S × T can be as small as 2cn − 1. Each of the choices of 0s and 1s in A on these diagonals are equally probable so the probability that we get rank smaller than c_{1}|log(\frac{q}{n})|^{−2} is at least 2^{−2cn+1} . (It is not 0 since, e.g. the 0 matrix has such a small rank.) Since the absolute value of the exponent in the number of pairs is greater by a factor of |log \frac{1}{c}| than in the upper bound M, the product cannot be smaller than \frac{1}{2} if c is a small constant.

4.2.2 Reducing the number of relevant submatrices

The main problem with the argument described above was that the number of pairs ⟨S,T ⟩ is too large compared to the number of relevant minor diagonals. Let 𝒮 be the set of these pairs, that is, the set of all pairs ⟨S,T ⟩ so that S,T ⊆ {0,1,...,n − 1} and |S| = |T | = q. We will be able to avoid the mentioned difficulty in the following way. Instead of working with the elements of 𝒮, we will consider a smaller set 𝒮′consisting of pairs ⟨S′,T′⟩ so that |S′| ≤ q, |T′| ≤ q and with the property that for all ⟨S,T ⟩ ∈ 𝒮 there is a ⟨S′,T′⟩ ∈ 𝒮′so that S′⊆ S and T′⊆ T. (We will refer to this property by saying that 𝒮′is dense in 𝒮.)

It is enough to show that for all ⟨S′,T′⟩ ∈ 𝒮′ the rank of B_{S′,T′}is at least c_{1}|log(\frac{q}{n})|^{−2} q. Indeed, since 𝒮′is dense in 𝒮, each matrix B_{S,T} with ⟨S,T ⟩ ∈ 𝒮 has a submatrix B_{S′,T′}with ⟨S′,T′⟩ ∈ 𝒮 and so rank(B_{S,T}) ≥ rank(B_{S′,T′}) ≥ c_{1}|log(\frac{q}{n})|^{−2} q.

We will define the set 𝒮′ by constructing a function ℱ defined on 𝒮 so that for each ⟨S,T ⟩ ∈ 𝒮, ℱ(⟨S,T ⟩) = ⟨S′,T′⟩ with S′⊆ S, T′⊆ T. Clearly if such an ℱ is given and 𝒮′= {ℱ(⟨S,T ⟩) | ⟨S,T ⟩ ∈ 𝒮}, then 𝒮′is dense in 𝒮. We also have to make sure that |𝒮′| is small and that we are able to give a good upper bound, for each fixed ⟨S′,T′⟩ ∈ 𝒮′, on the probability that the rank of the matrix B_{S′,T′}is smaller than c_{1}|log(\frac{q}{n})|^{−2} .

4.2.3 The rank of an enlarged submatrix

First we describe our method of estimating the probability that the rank of a submatrix B_{S,T} of A is small for a fixed pair ⟨S,T ⟩. This will be based on the following observation. Assume that a pair ⟨S,T ⟩, S,T ⊆ {0,1,...,n − 1}, is fixed and s > max S = max_{x∈S}x, t > max T, S_{1} = S ∪ {s}, and T_{1} = T ∪ {t}. Then with probability at least \frac{1}{2} for the randomization of A we have that the rank of B_{S_{1},T_{1}} is strictly greater than the rank of B_{S,T}. We will prove this statement in the following way. For all k = 0,1,...,n−1, let D_{k} be the minor diagonal of A containing the entries a_{i,j} with i + j = k. We show that if the values of the entries of A are fixed on all minor diagonals D_{k} with k < s + t, then out of the two possible definitions of A on the minor diagonal D_{s+t}, at least one will yield a matrix B_{S_{1},T_{1}}with the property that rank(B_{S_{1},T_{1}}) > rank(B_{S,T}). The proof of this fact is a simple argument in linear algebra as described in the proof of Lemma 4.5.

Lemma 4.5 itself is a slight generalization of this assertion, stating that if we add not a single new element to S and another single element to T, but a set of new elements S̃to S so that max S < min S̃, and a set of new elements T̃ to T so that max T < min T̃ then the resulting enlarged sets S_{1} = S ∪ S̃, T_{1} = T ∪ T̃ have the following property. If the values of the entries of A are fixed on all minor diagonals D_{k} with k ≤ maxS+maxT, then for the randomization of A on the remaining minor diagonals we have that, with probability at least 1 − 2^{−|S̃+T̃|} , rank(B_{S_{1},T_{1}}) > rank(B_{S,T}). Indeed, there are |S̃+ T̃| minor diagonals which contain an entry a_{s,t} of A with s ∈ S̃ and t ∈ T̃. According to the already described special case the randomization of the values of the entries on each of these diagonals will lead to the required increase of the rank with a probability of at least \frac{1}{2}. Since these randomizations are independent we get that the rank increases with probability at least 1 − 2^{−|S̃+T̃|} .

4.2.4 Partitioning the rows and columns

What we have done so far is only good for estimating the probability of rank(B_{S_{1},T_{1}}) > rank(B_{S,T}) for some pairs ⟨S,T ⟩, ⟨S_{1},T_{1}⟩ where S ⊆ S_{1}, T ⊆ T_{1}. To get a lower bound on the probability of rank(B_{S,T}) > R for some integer R, we will partition S into subsets S_{1},...,S_{l} and T into subsets T_{1},...,T_{l} so that max S_{i} < min S_{i+1} and max T_{i} < min T_{i+1} for all i = 1,...,l − 1. If rank(B_{S,T}) ≤ R = l − r then there must be at least r distinct elements i of {1,...,l} with the property rank(B_{Γ_{i},Λ_{i}} ) = rank(B_{Γ_{i+1} ,Λ_{i+1}} ), where Γ_{j} = S_{1} ∪ ...∪ S_{j} and Λ_{j} = T_{1} ∪ ...∪ T_{j} for j = 1,...,l. We will denote by E the set of all integers i ∈ {1,...,l} with this property. Then (7). the probability of the event that we get equalities for every element of this set is at most

2^{−∑_{i∈E}(|S_{i}+T_{i}|)} .

If we add these upper bounds for all of the possible choices for E, that is for all subsets of {1,...,l} with r elements, then we get an upper bound on the probability of rank(B_{S,T}) ≤ l −r. (This upper bound is formulated in a slightly more general form in Lemma 4.7.) We will use this estimate for each fixed choice for ⟨S,T ⟩ ∈ 𝒮′with suitable choices of the partitions S_{1},...,S_{l}, T_{1},...,T_{l}.

4.2.5 The choice of the partitions and the submatrices

Our remaining task is to define the function ℱ so that

𝒮′= {ℱ(⟨X_{1},X_{2}⟩) | ⟨X_{1},X_{2}⟩ ∈ 𝒮}

is dense in 𝒮, select a pair of partitions for each ⟨S,T ⟩ ∈ 𝒮′, and then add the corresponding upper bounds (with R = c_{1}q|log(\frac{q}{n})|^{−2} ) for each ⟨S,T ⟩ ∈ 𝒮′. The upper bounds will not depend on the choice of ⟨S,T ⟩ ∈ 𝒮′, so we will have to prove that the common upper bound multiplied by |𝒮′| is at most \frac{1}{2}.

When we define ℱ(⟨X_{1},X_{2}⟩) for some ⟨X_{1},X_{2}⟩ ∈ 𝒮, we will have already in mind the task of choosing suitable partitions of S and T, where ⟨S,T ⟩ = ℱ(X_{1},X_{2}). We give here a somewhat simplified definition of ℱ, the final definition will be provided in the proof of Lemma 4.9. Let t be a positive integer which is a large constant. We assume now, for the sake of simplicity, that t^{2}|q. For j = 1,2 we partition X_{j} into \frac{q}{t^{2}} subsets K_{1}^{(j)},...,K_{q/t^{2}}^{(j)} each containing exactly t^{2} elements so that max K_{i}^{(j)} < min K_{i+1}^{(j)} for i = 1,..., \frac{q}{t^{2}}− 1. Clearly these properties uniquely determine both partitions.

For each fixed i = 1,...,q/t^{2} we pick sets J_{i}^{(j)} ⊆ K_{i}^{(j)}, j = 1,2, with exactly t elements so that |J_{i}^{(1)}+ J_{i}^{(2)}| is maximal. Since the sets J_{i}^{(j)} have t elements this maximum is at most t^{2}. We will show (Lemma 4.3) that, since we pick the sets J_{i}^{(j)} from sets of size t^{2}, this upper bound can be can be attained, and so |J_{i}^{(1)}+ J_{i}^{(2)}| = t^{2} for all i = 1,2,..., \frac{q}{t^{2}}. Let

Z_{j} = ⋃_{i=1}^{q/t^{2}}J_{i}^{(j)}

for j = 1,2. Now we define ℱ by ℱ({X_{1},X_{2}}) = ⟨Z_{1},Z_{2}⟩. For j = 1,2 we will use the partition J_{1}^{(j)},...,J_{q/t^{2}}^{(j)} of the set Z_{j} when estimating prob(rank(B_{Z_{1},Z_{2}}) ≤ c_{1}|log(\frac{q}{n})|^{−2} q). The inequality of Condition (7) gives a good upper bound which can be easily evaluated (as a function of q,t and n) since in the exponents the value of the expression −(|J_{i}^{(1)}+ J_{i}^{(2)}|) is t^{2}, and the number of exceptional sets E can be also estimated without any problems. Finally the number of possible pairs ⟨Z_{1},Z_{2}⟩ is at most \binom{n}{q/t^{2}}^{2}. These estimates lead to the conclusion of the theorem.

4.2.6 Why did it work?

From the description of the necessary estimates at the end of the last paragraph it is not clear what made it possible to get a good enough upper bound on the probabilities prob(rank(B_{Z_{1},Z_{2}}) ≤ R), where R = c_{1}|log(\frac{q}{n})|^{−2} q, compared to the number of pairs ⟨Z_{1},Z_{2}⟩. It is true that the number of pairs became smaller, since the sizes of the sets Z_{j} are smaller by a factor of t then the sizes of the sets X_{j}, but for smaller sets the upper bounds on the probabilities can be larger. Why is it that we gained more on the number of sets then lost on the upper bounds on the probabilities?

The answer is that the upper bound did not depend on the sizes of the sets Z_{i} but depended only on the common size of the sets J_{i}^{(1)}+ J_{i}^{(2)} which was t^{2}. The corresponding quantity for the pair ⟨X_{1},X_{2}⟩ is |K_{i}^{(1)}+K_{i}^{(2)}|. Since we do not have any assumption about the sets K_{i}^{(1)},K_{i}^{(2)} other than that their sizes are t^{2}, in the worst case |K_{i}^{(1)}+ K_{i}^{(2)}| can be as small as 2t^{2}. Therefore, although the sizes of the sets went down by a factor of t, the critical quantity in the upper bounds remained essentially unchanged. This guaranteed that we won more on decreasing the number of pairs then we lost on increasing the upper bound of the probabilities. To formulate the same phenomenon in the language of minor diagonals we may say that: although the ratio of the sizes of the sets X_{j} and Z_{j} is t, if we consider the number of minor diagonals intersecting the subsets K_{i}^{(1)}×K_{i}^{(2)} resp. J_{i}^{(1)}×J_{i}^{(2)} the ratio, at least in certain cases, is at most 2.

This completes the sketch of the proof of the theorem. In the remaining part of the section we gave a detailed proof of the mentioned lemmata and the theorem.

4.3 The proof of Theorem 4.2

Lemma 4.3. Assume that t is a positive integer and U,V are sets of integers with |U| = |V | = t^{2}. Then there are U′⊆ U, V′⊆ V, so that |U′| = |V′| = t and |U′+ V′| = t^{2}.

Remark 4.4. As the proof will show, the lemma remains true if we replace |U| = |V | = t^{2} by the weaker assumption |U| = |V | = t^{2}− t + 1.

Proof of Lemma 4.3. We have to select the subsets U′,V′of U and V so that each has exactly t elements and all of the t^{2} sums u + v, u ∈ U′, v ∈ V′ are different. Suppose that this does not hold for some selection of U′,V′, that is u + v = ū+ v̄for some suitably chosen u,ū∈ U′, v,v̄∈ V′. This would imply that u−ū= v̄−v and so the sets (U′−U′)_{+} and (V′−V′)_{+} are not disjoint, where for a set of integers X, (X)_{+} = {x ∈ X | x > 0}. Therefore it is sufficient (and also necessary) to prove that there exist U′⊆ U, V′⊆ V so that |U′| = |V′| = t and (U′− U′)_{+} ∩ (V′− V′)_{+} = ∅.

Let U = {u_{0},...,u_{t^{2}−1}}, V = {v_{0},...,v_{t^{2}−1}} so that u_{0} < ... < u_{t^{2}−1} and v_{0} < ... < v_{t^{2}−1}. We define the integers m_{u},m_{v} by

m_{u} = min{u_{i+t−1} − u_{i} | i = 0,1,..,t^{2}− t} and m_{v} = min{v_{i+t−1} − v_{i} | i = 0,1,..,t^{2}− t} .

Suppose that, e.g. m_{u} ≤ m_{v}, and let s be an integer with m_{u} = u_{s+t−1} − u_{s}. We claim that the choice U′= {u_{s},u_{s+1} ,...,u_{s+t−1} }, V′= {v_{jt} | j = 0,1,...,t −1} meets our requirements. Indeed, if v_{jt},v_{kt}∈ V′ and j < k then v_{kt}−v_{jt} ≥ v_{(j+1)t} −v_{jt} > v_{jt+t−1} −v_{jt} ≥ m_{v}≥ m_{u}, and therefore each element of (V′−V′)_{+} is strictly greater than m_{u}. On the other hand U′⊆ [u_{s},u_{s+t−1} ] = [u_{s},u_{s} + m_{u}]; therefore (U′− U′)_{+} contains only integers not greater than m_{u}. Consequently (U′− U′)_{+} ∩ (V′− V′)_{+} = ∅.

Definitions.

1. func(n,2) will denote the set of all functions defined on {0,...,n−1} with values in F_{2}. Similarly, func([l,n),2) will denote the set of all functions defined on the interval [l,n) = {l,...,n − 1} with values in F_{2}.

2. Assume that n_{1},n_{2} are positive integers and f ∈ func(n_{1}+ n_{2}− 1,2). Then diag(f,n_{1},n_{2}) will be the n_{1} by n_{2} matrix (d_{i,j}), i = 0,...,n_{1}− 1, j = 0,1,...,n_{2}− 1, where d_{i,j} = f(i + j).

3. Assume that n_{1},n_{2},k_{1},k_{2}, are positive integers, n_{1} > k_{1}, n_{2} > k_{2}, f ∈ func(k_{1}+ k_{2}− 1,2), and g is taken with uniform distribution from the set func([k_{1}+ k_{2},n_{1}+ n_{2}− 1),2). Φ(n_{1},n_{2},f) will be a random variable whose value is diag(f ∪g,n_{1},n_{2}) (where f ∪g is the unique common extension of f and g to [0,n_{1}+n_{2}−1)). Φ(n_{1},n_{2}) will denote the random variable whose value is diag(h,n_{1},n_{2}) where h is taken with uniform distribution from the set func(n_{1}+ n_{2}− 1,2).

4. Suppose A = (a_{i,j}), i = 0,...,n_{1}−1, j = 0,1,...,n_{2}−1, is an n_{1} by n_{2} matrix and S ⊆ {0,1,...,n_{1}− 1}, T ⊆ {0,1,...,n_{2}− 1}. Then sub(A,S,T) will denote the |S| by |T | matrix consisting of those entries of A which have row numbers in S and in column numbers in T.

Lemma 4.5. Assume that n_{1}, n_{2}, k_{1}, and k_{2} are positive integers, k_{1} < n_{1}, k_{2} < n_{2}, f is a function on {0,1,...,k_{1}+ k_{2}− 1} with values in F_{2}, S ⊆ {0,1,...,n_{1}− 1}, T ⊆ {0,1,...,n_{2}− 1}, and

|(S ∩ {k_{1},...,n_{1}− 1}) + (T ∩ {k_{2},...,n_{2}− 1})| ≥ m .

Then with probability at least 1−2^{−m} the following holds: the rank of the matrix sub(Φ(n_{1},n_{2},f),S,T) is greater than the rank of the matrix

sub(Φ(n_{1},n_{2},f),S ∩ {0,1,...,k_{1}− 1},T ∩ {0,1,...,k_{2}− 1}) .

Remark 4.6. If we define random Hankel matrices over an arbitrary field F so that the random entries of the Hankel matrices are picked from a finite subset D of F with uniform distribution, then our Lemma remains true if we substitute 1 − |D|^{−m} for the probability 1 − 2^{−m}. (Naturally we also have to modify the definition on Φ(n_{1},n_{2},f), since in this case f is a function whose values are in the set D.)

Proof of Lemma 4.5. Let Φ(n_{1},n_{2},f) = (φ_{i,j}), i = 0,...,n_{1}−1, j = 0,...,n_{2}−1. For each ℓ = 0,1,2,... let S_{ℓ} = S ∩ {0,1,...,ℓ}, T_{j} = T ∩ {0,1,...,ℓ}. For each i ∈ S, j ∈ T, w_{i,j} will be a function defined on T_{j} by w_{i,j}(x) = φ_{i,x} for all x ∈ T_{j}. Let r be rank of the matrix sub(Φ(n_{1},n_{2},f),S_{k_{1}−1},T_{k_{2}−1}). r is the dimension of the vectorspace generated by the functions w_{i,k_{2}−1}, i ∈ S_{k_{1}−1}. Suppose that S̄⊆ S_{k_{1}−1}, |S̄| = r so that the set of functions W = {w_{i,k_{2}−1} | i ∈ S̄} are linearly independent.

According to the definition of Φ(n_{1},n_{2},f), we have to randomize a function g with values in F_{2} which is defined on the interval [k_{1}+k_{2},n_{1}+n_{2}−1). We randomize the values of g sequentially for each x ∈ [k_{1}+k_{2},n_{1}+n_{2}−1)∩(S+T). Assume that x ∈ [k_{1}+k_{2},n_{1}+n_{2}−1)] and g(y) has been randomized already for all y < x. Suppose that for a suitably chosen i ∈ S∩{k_{1},...,n_{1}−1} and j ∈ T ∩{k_{2},...,n_{2}−1} we have i + j = x. By the assumption of the lemma this will happen for at least m different values of x. Therefore, it is enough to show that for such an x the following holds with a probability at least \frac{1}{2}: the function w_{i,j} is linearly independent from the set of functions H = {w_{l,j}|l ∈ S̄}. (Such an independence obviously implies that the rank of the matrix sub(Φ(n_{1},n_{2},f),S,T) is greater than |S̄| = r.) Before the randomization of g(x) the function w_{i,j} is known in every point of T_{j} with the exception of j. Since there are two possibilities for the value of w_{i,j} at j, we have two functions u,v; hence for the randomization of g(x) we have P(w_{i,j} = u) = P(w_{i,j} = v) = \frac{1}{2}. Consequently, it is enough to show that at least one of the two vectors u,v is linearly independent from the set H. Indeed, if both are linearly dependent, then their difference is also linearly dependent on them, that is, u − v = ∑_{s∈S̄}γ_{s}w_{s,j} where γ_{s} ≠ 0 for at least one s ∈ S̄. We show that this is impossible. Indeed, u − v is a function on T_{j} which is zero everywhere but at j and (u−v)(j) = 1. Consequently j ≥ k_{2} implies that the restriction of u−v to T_{k_{2}−1} is 0. Therefore we get that ∑_{s∈S̄γ_{s}} γ_{s}w_{s,k_{2}} = 0. The functions w_{s,k_{2}} are linearly independent so we have γ_{s} = 0 for all s ∈ S̄, in contradiction to our assumption.

Lemma 4.7. Assume that for each j = 1,2, I_{1}^{(j)},...,I_{l}^{(j)}, is a partition of the interval [0,...,n) into pairwise disjoint subintervals, S^{(1)},S^{(2)} ⊆ {0,1,...,n − 1}, and |(S^{(1)}∩ I_{i}^{(1)}) + (S^{(2)}∩ I_{i}^{(2)})| ≥ m_{i} for all i = 1,...,l. Then, for any positive integer r, the probability that the rank of sub(Φ(n,n),S^{(1)},S^{(2)}) is not greater than l − r is at most

∑_{1≤i_{1}<··· <i_{r}≤l} 2^{−m_{i_{1}}−...−m_{ir}} .

Remark 4.8. If we define the random Hankel matrix Φ(n,n) over an arbitrary field F in the way described in Remark 4.6 (just after Lemma 4.5), then our lemma remains true if we substitute |D|^{−m_{i_{1}}−...−m_{ir}} for 2^{−m_{i_{1}}−...−m_{ir}} in the last expression of the lemma.

Proof of Lemma 4.7. Assume that for all j = 1,2, x ∈ I_{i}^{(j)}, y ∈ I_{i+1}^{(j)} implies x < y, and assume further that for all j = 1,2, i = 1,...,l, I_{i}^{(j)} = [b_{j,i},b_{j,i+1} ). Let

S_{i}^{(j)} = S^{(j)} ∩ ⋃_{k=1}^{i} I_{k}^{(1)} = S^{(j)} ∩ [0,b_{j,i+1} ) ,

and let Φ_{i} = sub(Φ(n,n),S_{i}^{(1)},S_{i}^{(2)}). If the rank of X = sub(Φ(n,n),S^{(1)},S^{(2)}) is not greater than l − r then there are r integers 1 ≤ i_{1} < ... < i_{r} ≤ l so that the rank of Φ_{i_{t}} and Φ_{i_{t}+1} is the same for t = 1,...,r. We show that for each fixed i_{1},...,i_{r} the probability of this event is at most 2^{−m_{i_{1}}−...−m_{ir}} which clearly implies the statement of the lemma. Suppose that i_{1},...,i_{r} are fixed. According to the definition of Φ(n,n) we randomize an h ∈ func(2n−1,2). We pick the values of h on [2n−1,2) sequentially. Assume that for some t ∈ {1,...,r} the values of h(0),...,h(b_{i_{t},1}+b_{i_{t},2})−1 have been already fixed. We define a function f on the set {0,...,h(b_{i_{t},1}+ b_{i_{t},2}) − 1} by f(y) = h(y) for all y = 0,...,h(b_{i_{t},1}+ b_{i_{t},2}) − 1. Now we randomize the values of h(x) for all x = b_{i_{t,1}}+ b_{i_{t,2}},...,b_{i_{t+1,1}} + b_{i_{t+1,2}} − 1. We apply Lemma 4.5 for this part of the randomization with n_{j} → b_{t+1,j} , k_{j} → b_{i_{t},j} for j = 1,2, S → S_{t}^{(1)}, T → S_{t}^{(2)}, m → m_{i_{t}}, and for the function f defined above. We get that the probability of the event rank(Φ_{i_{t−1}}) = rank(Φ_{i_{t}}) is less than 2^{−m_{t}}. This implies that the probability that rank(Φ_{i_{t−1}}) = rank(Φ_{i_{t}}) for all t = 1,...,r is at most 2^{−m_{1}−...−m_{r}} .

The following lemma will be used to give an estimate on the probability that the rank of a matrix sub(A,S,T) is at least R where the sets S,T ⊆ {0,1,...,n − 1} are fixed and A is a random Hankel matrix over F_{2}. Since the statement of the lemma depends on many parameters we restate their roles as described in the “sketch of the proof” of Theorem 4.2. The sizes of the sets S,T are the same:

|S| = |T | = q. We may think of t as a large constant, although the lemma requires only t^{2} < q. In the “sketch of the proof” (using the notation S → X_{1},T → X_{2}) we made the simplifying assumption that t^{2}|q, and partitioned both S and T into \frac{q}{t^{2}} subsets each of size t^{2}. Without the assumption q^{2}|t, we will take first subsets of both S and T with t^{2}⌊\frac{q}{t^{2}}⌋ elements and partition these subsets into classes each of size t^{2}. Therefore Q = ⌊\frac{q}{t^{2}}⌋ of the lemma refers to the number of classes in these partitions. In the estimate given in the lemma the factor 2^{−(Q−R+1)t^{2}} is an upper bound on the probability that if we select R − 1 pairs of corresponding classes from the two partitions, then the remaining ones do not increase the rank of sub(A,S,T) in the sense explained in the “sketch”. The factor \binom{Q}{Q−R+1} is the number of ways that we

can select these R − 1 pairs from the Q pairs of classes. The factor \binom{n}{Qt}^{2} has the following meaning. In the proof we consider all of the pairs of subsets S′⊆ S, T′⊆ S and estimate the probability that for at least one of them the rank of sub(A,S′,T′) will be R or greater. Then we multiply this estimate by the number of possible pairs of sets S′,T′. Since we select S′,T′with |S′| = |T′| = Qt (they contain exactly t elements from each class) the number of possible selections is at most \binom{n}{Qt}^{2}.

Lemma 4.9. Assume that n,q,R,t are positive integers, t^{2} < q < n and R < ⌊\frac{q}{t^{2}}⌋. Suppose further that A = {a_{i,j}}, i = 0,...,n−1, j = 0,...,n−1 is a random n by n Hankel matrix over F_{2}, taken with uniform distribution on the set of all such matrices. Let p be the probability of the following event:

(8). for all S ⊆ [0,n),T ⊆ [0,n), |S| = |T | = q the rank of the matrix sub(A,S,T) is at least R. Then

p ≥ 1 − \binom{n}{Qt} ^{2}\binom{Q}{Q − R + 1} 2^{−(Q−R+1)t^{2}}

where Q = ⌊\frac{q}{t^{2}}⌋.

Remark 4.10. This lemma also remains true with some modifications over an arbitrary field if we randomize the Hankel matrix A according to the distribution described in the remark after Lemma 4.5. Namely we have to substitute |D|^{−(Q−R+1)t^{2}} for 2^{−(Q−R+1)t^{2}} in the last expression of the lemma.

Proof of Lemma 4.9. We will define a function ℱ on the set of all ordered pairs ⟨X_{1},X_{2}⟩ with X_{j} ⊆ {0,...,n − 1}, for j = 1,2, |X_{1}| = |X_{2}| = q. Before getting into the details of this definition, recall from the “sketch of proof”of Theorem 4.2 that, roughly speaking, we get ℱ(⟨X_{1},X_{2}⟩) in the following way. First we partition both X_{1} and X_{2} into classes of sizes t^{2}. Then we select subsets J_{i}^{(1)}, J_{i}^{(2)} from each pairs of corresponding classes with the property that |J_{i}^{(1)}| = |J_{i}^{(2)}| = t, |J_{i}^{(1)}+ J_{i}^{(2)}| = t^{2}. The pair ⟨⋃_{i}J_{i}^{(1)},⋃_{i}J_{i}^{(2)}⟩ is the value of ℱ.

Each value of the function will be a pair ⟨Z_{1},Z_{2}⟩ so that Z_{1},Z_{2} ⊆ {0,...,n − 1} and |Z_{1}| = |Z_{2}| = ⌊\frac{q}{t^{2}}⌋t. The definition is the following. Assume that the pair ⟨X_{1},X_{2}⟩ is given with the described properties. For each j = 1,2 we pick pairwise disjoint subsets K_{1}^{(j)},...,K_{Q}^{(j)} of X_{j}, where Q = ⌊\frac{q}{t^{2}}⌋, so that

|K_{i}^{(j)}| = t^{2} for all j = 1,2 i = 1,...,Q and x ∈ K_{i}^{(j)}, y ∈ K_{i′}^{(j)} implies x < y for all j = 1,2, 1 ≤ i < i′≤ Q. (By the definition of Q this is possible.)

Assume now that an i = 1,...,Q is fixed. We apply Lemma 4.3 with U → K_{i}^{(1)}, V → K_{i}^{(2)}. Let U′, V′ be the sets whose existence is stated in Lemma 4.3 and let J_{i}^{(1)} = U′, J_{i}^{(2)} = V′. Finally let Z_{j} = ⋃ _{i=1}^{Q} J_{i}^{(j)} for j = 1,2 and let ℱ(⟨X_{1},X_{2}⟩) = ⟨Z_{1},Z_{2}⟩. Clearly the pair ⟨Z_{1},Z_{2}⟩ satisfies the conditions described above as well as the following additional properties:

(a). for all j = 1,2 J_{1}^{(j)},...,J_{Q}^{(j)} is a partition of Z_{j}, |J_{i}| = t for all i = 1,...,Q,

(b). for all j = 1,2, 1 ≤ i < i′≤ Q x ∈ J_{i}^{(j)}, y ∈ J_{i′}^{(j)} implies x < y,

(c). for all j = 1,2 and i = 1,...,q we have Z_{j} ⊆ X_{j} and |J_{i}^{(1)}| + |J_{i}^{(2)}| = t^{2}.

Assume now that ⟨Z_{1},Z_{2}⟩ ∈ range(ℱ). We estimate the probability ρ_{Z_{1},Z_{2}} of the event that the rank of the matrix sub(A,Z_{1},Z_{2}) is smaller than R.

We apply Lemma 4.7 with l → Q, I_{i}^{(j)} → J_{i}^{(j)}, S^{(1)} → Z_{1}, S^{(2)} → Z_{2}, m_{i} → t^{2}, r → Q−R+1. We get that ρ_{Z_{1},Z_{2}} is at most QQ − R + 1 2^{−(Q−R+1)t^{2}} . Therefore, using that |Z_{j}| = Qt, we get that the probability that the rank of the matrix sub(A,Z_{1},Z_{2}) is smaller than R for at least one ⟨Z_{1},Z_{2}⟩ ∈ range(ℱ) is at most

|range(ℱ)|\binom{Q}{Q − R + 1} 2^{−(Q−R+1)t^{2}} ≤ \binom{n}{Qt} ^{2}\binom{Q}{Q − R + 1} 2^{−(Q−R+1)t^{2}} .

For each pair S,T, with the properties given in the lemma, if ℱ(⟨S,T ⟩) = ⟨Z_{1},Z_{2}⟩, then Z_{1} ⊆ S, Z_{2} ⊆ T and this implies that rank(sub(A,S,T)) ≥ rank(sub(A,Z_{1},Z_{2})) so we have the same upper bound on the probability that the rank of sub(A,S,T) is smaller than R.

Proof of Theorem 4.2. Assume that θ > 0 is sufficiently small, c_{1} > 0 is sufficiently small with respect to θ, and c_{2} > 0. Suppose further that n is sufficiently large and c_{2}n < q ≤ n. We apply Lemma 4.9 with n, q, R = c_{1}|log(\frac{q}{n})|^{−1} q, and t = ⌊θ^{−1} |log(\frac{q}{n})|⌋. We get that the probability that rank of sub(A,S,T) is at least R is at least

p ≥ 1 − \binom{n}{Qt} ^{2}\binom{Q}{Q − R + 1} 2^{−(Q−R+1)t^{2}}

where Q = ⌊\frac{q}{t^{2}}⌋. We show that

\binom{n}{Qt} ^{2}\binom{Q}{Q − R + 1} 2^{−(Q−R+1)t^{2}}

is at most \frac{1}{2} by giving upper bounds in its factors. As we have remarked already at the end the of sketch of the proof, the crucial fact that leads to the desired result is that in the exponent of 2 we have the factor t^{2} and not only t. We will see that in the actual estimates this t^{2} makes it possible to get the strong upper bound we need.

We will use that if 0 < α < \frac{1}{2}, n is sufficiently large, and x < αn then

\binom{x}{αn} ≤ e^{2αnlog \frac{1}{α}} .

Let γ = \frac{q}{n}, and λ = \frac{Qt^{2}}{q}. Clearly c_{2} < γ < 1 and \frac{1}{2} < λ ≤ 1. Hence

\binom{n}{Qt} = \binom{n}{γλt^{−1} n} ≤ e^{2γλt^{−1} nlog(γ^{−1} λ^{−1} t)}= e^{2γλt^{−1} n(logγ^{−1} +logλ^{−1} +logt)} .

Using that t^{−1} logγ^{−1} = θ, t^{−1} logλ^{−1} ≤ t^{−1} log2 ≤ t^{−1} ≤ θ, and t^{−1} logt ≤ t^{− \frac{1}{2}} ≤ θ^{\frac{1}{2}} we get that

\binom{n}{Qt} ^{2} ≤ e^{4γλ(θ+θ+θ ^{\frac{1}{2}} )n} ≤ 2^{\frac{1}{20}}γλn

and

\binom{Q}{Q − R + 1} ≤ 2^{Q} = 2^{γλt^{−2} n}≤ 2^{\frac{1}{20}γλn}

if θ is sufficiently small. Moreover,

2^{−(Q−R+1)t^{2}} ≤ 2^{− \frac{1}{8}Qt^{2}} = 2^{− \frac{1}{8}γλt^{−2} t^{2}n} = 2^{− \frac{1}{8}γλn} .

These inequalities imply that

\binom{n}{Qt} ^{2}\binom{Q}{Q − R + 1} 2^{−(Q−R+1)t^{2}} ≤ 2^{\frac{1}{20}γλn+ \frac{1}{20}γλn− \frac{1}{8}γλn} ≤ 2^{−( \frac{1}{8}− \frac{1}{10})γλn} < \frac{1}{2}

if n is sufficiently large. (Here we use that c_{2} < γ and \frac{1}{2} < λ.)

5 The proof of Lemma 3.5

5.1 A lemma about disjoint sets of variables

In this section we prove Lemma 3.5 using Lemma 9 of [4]. (This is the most important technical lemma of that paper with a long proof.) We reformulate below this result from [4] as Lemma A1 to make it consistent with the terminology of the present paper. In the proof we will also use other lemmata from [4]; we will formulate them as Lemma A2, Lemma A3, and Lemma A4 in the present paper. These latter three lemmata have short proofs (given in [4]) using only the definitions of the concepts contained in their statements. The following definitions are needed for the statement of Lemma A1.

Definitions.

1. Assume that ℬ is a branching program with n input variables and η is an input for ℬ. (Recall that an input is a {0,1}-valued function defined on {0,1,...,n − 1} with the meaning that the value η(i) is assigned to the variable x_{i}.) At input η the branching program follows a path in the directed graph 𝒢 as described in the definition of a branching program. We associate a time (a nonnegative integer) with each node of this path. If the path is v_{0},v_{1},...,v_{i}, where v_{0} is the source node and v_{i} is a sink node, then for all integers t ∈ [0,1], we will say that the program is at node v_{t} at time t with respect to input η. We will use the notation state(t,η) = v_{t}.

2. Assume that state(t,η) = v_{t}, and var(v_{t}) = x_{i}. In this case we will say that the program accesses the variable x_{i} at time t.

3. An input η is visible if each variable x_{i}, i = 0,1,...,n − 1 is accessed at some time during the computation performed at input η.

4. Assume that ℬ is a branching program so that the path associated with each input is of length l. In this case we will say that for each input the length of the program is l.

Additional assumptions about ℬ. Without loss of generality we will make the following two additional assumptions about the branching program ℬ in the proof of Lemma 3.5.

(a) We assume that every input is visible. Indeed, we can modify the branching program ℬ so that the new branching program ℬ′first reads the value of each variable and then continues with the original computation of ℬ. The length and the size of the program are thus increased only by n. Moreover, if Lemma 3.5 holds for ℬ′then clearly it also holds for ℬ since, apart from the size and the depth of the program, Lemma 3.5 treats the program as a black box, it speaks only about the function defined by the branching program.

(b) We assume that, independently of the input, the length of the branching program is exactly kn, that is, for each input η the program reaches a sink node at time kn. This is not an essential restriction because there is another program ℬ′, whose size is larger than the size of ℬ by only a factor of at most n^{2}, so that program ℬ′works exactly the same way as program ℬ but also counts the time and when ℬ reaches a sink node v then it works further till time kn when it gives the same output as the output of ℬ at node v. (We may assume that at each time t in this new additional time interval, the branching program ℬ′accesses, e.g., the variable x_{0}.)

As a consequence of this second assumption, for each fixed input η, the function state(t,η) is defined for all t = 0,1,...,nk and the branching program accesses a variable at each time t for t = 0,1,...,kn − 1.

Definitions.

1. Suppose that σ is a real number with σ ∈ (0, \frac{1}{2}). We assume that a partition of the set \{0,1,...,kn− 1} into intervals is fixed so that the length of each interval is between σn and 2σn. ℐ^{(σ)} will denote the set of these intervals. If the choice of σ is clear from the context, we will omit the superscript σ.

2. Assume that T ⊆ {0,1,...,kn − 1} is a set of integers. The set of all integers i ∈ {0,1,...,n − 1}, so that the input variable x_{i} is accessed by the branching program at some t ∈ T, at input η, will be denoted by register(T,η). The set of all integers j in register(T,η) so that the value of variable x_{j} is not accessed at any time outside T at input η will be denoted core(T,η). Clearly

     core(T,η) ⊆ register(T,η).

Remark 5.1. The notation register(η) was motivated by the fact that, in [4], instead of branching programs we work with random access machines, and so instead of reading the values of variables the machine reads the content of registers. To make the two papers more compatible we did not change this notation.

Definitions.

1. If a σ > 0 is given, F ⊆ ℐ^{(σ)}, and χ is an input, then stem(F,χ) will denote the restriction of χ onto {0,1,...,n − 1}\core(F,χ).

2. Suppose that T ⊆ {0,...,kn − 1}. We say that x is at the right border of T if x ∉ T and x − 1 ∈ T. The set of those integers which are at the right border of T will be denoted by right(T).

3. Suppose that T ⊆ {0,...,kn − 1} and χ is an input. Let f be a function defined on the set right(T), so that for all t ∈ right(T) we have f(t) = state(t,χ). We will call f the rightstate function of the set T at input χ and will denote it by rstate_{T,χ}.

Remark 5.2. The significance of the set core(T,χ), the right border of T, and the function right_{T,χ} is the following. Assume that starting from the input χ we change the value of some of the variables in core(T,χ) in a way that for the new input χ′we have right_{T,χ} = right_{T,χ′}. Then the output of the program remains unchanged.

Lemma A1. For all positive integer k, if σ > 0 is sufficiently small with respect to k, ϵ > 0 is sufficiently small with respect to σ, n is sufficiently large with respect to ϵ, ℬ is a branching program with n input variables, ℬ is of size at most 2^{ϵn}, for each input the length of the program is kn, and G is a set of visible inputs, then the following holds. There exist κ > σ, F_{1},F_{2}, f_{1}, f_{2}, H satisfying the following conditions:

(9). H ⊆ G and |H| ≥ 2^{−κn} |G|

(10). F_{1},F_{2} are disjoint subsets of ℐ^{(σ)}

(11). for all i = 1,2 and j = 3 − i if χ,ξ ∈ H, and stem(F_{i},χ) = stem(F_{i},ξ), then core(F_{j},χ) = core(F_{j},ξ)

(12). |core(F_{i},χ)| ≥ κ^{τ}n for all χ ∈ H and i = 1,2, where τ = 1 − \frac{1}{50k},

(13). rstate_{χ,⋃ F_{i}} = f_{i} for all χ ∈ H, i = 1,2.

(14). κ < 2^{−|logσ|^{\frac{1}{4}}}

Motivation. The intuitive meaning of Lemma A1 is the following. Suppose that a branching program works in linear time. Then, if we segment the time into intervals of length about σn, it is possible to select two disjoint sets of intervals F_{1} and F_{2} so that in each of them, for a large number of inputs χ, we access many variables (the ones in core(F_{3−i} ,χ)) that are not accessed anywhere else. Moreover the sets F_{1} and F_{2} can be selected with the additional property described below. If the state of the branching program is fixed at the right borders of F_{1} and F_{2} (Condition (13)), then core(F_{1},χ) and core(F_{2},χ) are independent from each other in the following sense. In order to know what is core(F_{i},χ), we do not have to know the values of the variables in core(F_{3−i} ,χ) (Condition (11)). This last condition is the crucial part of the lemma, everything else in it can be proved by a simple counting argument.

Remarks.

1. Condition (14) was not included in the original statement of the lemma in [4] but its proof clearly implies it. The exact form of the upper bound on κ is not important for us, any upper bound of the type κ < g(σ) where lim_{x→∞} g(x) = 0 would be sufficient for the proof of Lemma 3.5.

2. We have changed the notation of the original lemma (by substituting κ for λ) to make it more compatible to the notation of Lemma 3.5.

3. The lemma in [4] was originally formulated for random access machines, however in the case when the possible contents of the input registers form a set with two elements, the notion of the random access machines used there is identical to the notion of (2-way) branching programs. Therefore Lemma A1 is a special case of Lemma 9 of [4].

4. There is a slight difference between the notation of the two papers: in [4] an input is a function defined on the set {1,...,n} while in the present paper it is defined on {0,1,...,n − 1}.

5. The proof of Lemma 3.5 from Lemma A1 is almost identical to the proof of Theorem 4 of [4] from Lemma 9 of the same paper.

5.2 Reducing Lemma 3.5 to Lemma A1

As we pick the values of the various parameters in Lemma 3.5 we will describe the values of the parameters of Lemma A1 when we use it in our proof.

Assume that k is given (we will apply Lemma A1 with the same value of k). Now we pick σ_{1} and σ_{2} so that σ_{1} is sufficiently small with respect to k and σ_{2} is sufficiently small with respect to σ_{1}. Let σ = 3σ_{2}. Let ϵ > 0 be sufficiently small with respect to σ_{2}, let n be sufficiently large with respect to ϵ, and let ℬ be a branching program of length kn (for each input)and size at most 2^{ϵn}. (ϵ, ℬ and n are the same in the two lemmata.) We pick δ ∈ {0,1} so that |ℬ^{−1} (δ)| ≥ 2^{n−1} . Let G = ℬ^{−1} (δ) in Lemma A1. (As we noted earlier we may assume that every input of ℬ is visible, so G meets this requirement of Lemma A1.) Now we pick κ, F_{1},F_{2},f_{1},f_{2},H with the properties listed in Lemma A1.

As a first step in the proof of Lemma 3.5 we prove that there is a χ̄ ∈ H so that for each i = 1,2 the following condition is satisfied:

(15). assume that s_{i} = |core(F_{i},χ̄)| and Ȳ_{i}is the set of all partial inputs η defined on core(F_{i},χ̄) so that χ̄≀ η ∈ H; then |Ȳ_{i}| ≥ \frac{1}{6}2^{−κn} 2^{s_{i}}.

For the proof we use the following two lemmata from [4]. The first one, Lemma A2 is Lemma 10 in [4], the second one Lemma A2, is Proposition 3 in that paper.

Lemma A2. Suppose that F ⊆ ℐ, χ, ξ are inputs with stem(F,χ) ≠ stem(F,ξ) and rstate_{χ,⋃ F} = rstate_{ξ,⋃ F}. Then there is an x ∈ domain(stem(F,χ)) ∩ domain(stem(F,ξ)) so that χ(x) ≠ ξ(x).

Lemma A3. Assume that A ⊆ A′are finite sets, P is a partition of A, P′is a partition of A′, each class of P is contained in a single class of P′, and d = |A||A′|^{−1} . Then for all λ > 0, there are at most λ|A| elements x of A so that if C,C′are the unique P,P′classes containing x then |C||C′|^{−1} ≤ λd.

As a first step in proving the existence of a χ̄ ∈ H so that for all i = 1,2 Condition (15) is satisfied, we fix an i ∈ {1,2} and give a lower bound on the number of inputs χ̄ ∈ H with Condition (15) (with this fixed i). We define a partition 𝒯_{i} of H in the following way. ∀χ,ξ ∈ H, ξ,χ belong to the same class iff stem(F_{i},χ) = stem(F_{i},ξ). It is a consequence of this definition that if χ and ξ do not belong to the same class of 𝒯_{i}, then the functions stem(F_{i},χ) and stem(F_{i},ξ) must be different (for the fixed value of i). Since the domains of these two functions, that is, {0,1,...,n − 1}\core(F_{i},χ) and {0,1,...,n − 1}\core(F_{i},ξ) are not necessarily identical, in principle it would be possible for the functions stem(F_{i},χ) and = stem(F_{i},ξ) to be compatible, that is, to be identical on the intersection of their domains. However Condition (13) of Lemma A1 and Lemma A2 imply that this can never happen, that is,

(16). functions that belong to different classes of 𝒯_{i} are not compatible.

We will denote by H′the set of all inputs ζ so that there is a χ ∈ H with the property that ζ is an extension of stem(χ,H). For each fixed χ ∈ H let W_{χ} be the set of all ζ ∈ H′so that ζ is an extension stem(F_{i},χ). Condition (16) implies that the sets W_{χ}, χ ∈ H (we take each of them only once) form a partition 𝒯′_{i}of H′. Clearly each class of 𝒯_{i} is contained in exactly one class of 𝒯′_{i}.

We want to apply Lemma A3 with A → H, A′→ H′, P → 𝒯_{i}, P′→ 𝒯′_{i}, and λ → \frac{1}{3}. Since, by the definition of G, we have |G| ≥ 2^{n−1} , Condition (9) of Lemma A1 implies that |H| ≥ 2^{−κn} 2^{n−1} . Obviously |H′| ≤ 2^{n} and so d = |H||H′|^{−1} ≥ \frac{1}{2}2^{−κn}. Therefore, according to Lemma A3, for at least \frac{1}{3}|H| inputs χ from the set H, the following condition is satisfied: χ belongs to a class in 𝒯_{i} whose density in the unique class of 𝒯′_{i}containing it is at most \frac{1}{3}d ≥ \frac{1}{6}2^{−κn}. Let X_{i} be the set of all inputs χ ∈ H with this property. Since |X_{i}| ≤ \frac{1}{3}|H| for both i = 1 and i = 2 we have that |H\(X_{1}∪X_{2})| ≥ \frac{1}{3}|H|. Let χ̄ ∈ H\(X_{1}∪X_{2}). The definition of X_{i} implies that for all i = 1,2, χ̄ belongs to a class of 𝒯_{i} whose density in the corresponding class of 𝒯′_{i}is greater than \frac{1}{6}2^{−κn}. Since each class of 𝒯′_{i}contains exactly 2^{s_{i}} elements this implies that χ̄ meets the requirements of Condition (15).

Assume that χ̄ is fixed with Condition (15) and Ȳ_{i}, i = 1,2 are the sets defined in the description of that property. We will prove the following:

(17). for all η_{i} ∈ Ȳ_{i}, i = 1,2 we have (χ̄≀ η_{1}) ≀ η_{2} ∈ ℬ^{−1} (δ).

For the proof of this fact we use the following lemma which is Lemma 2 in [4]:

Lemma A4. Assume that χ is an input, η_{1}, η_{2} are partial inputs, T_{1},T_{2} ⊆ {0,1,...,nk −1}. If χ, η_{1}, η_{2}, T_{1}, and T_{2} satisfy the following conditions, then ℬ(χ) =ℬ((χ ≀ η_{1}) ≀ η_{2}).

(18). domain(η_{1}) and domain(η_{2}) are disjoint.

(19). T_{1} and T_{2} are disjoint.

(20). for all i = 1,2 we have domain(η_{i}) ⊆ core(T_{i},χ)

(21). for all i = 1,2 we have rstate_{T_{i},χ} = rstate_{T_{i},χ≀η_{i}}

(22). for all i,j ∈ {1,2}, i ≠ j we have domain(η_{i}) ∩ register(T_{j},χ ≀ η_{j}) = ∅.

To prove that Condition (17) is satisfied by χ̄, we show that the assumptions of Lemma A4 hold with χ → χ̄, η_{1}, η_{2}, T_{1} → ⋃ F_{1}, and T_{2} → ⋃ F_{2}.

Condition (18). By the definitions of η_{i} and the function core we have domain(η_{i}) = core(F_{i},χ) ⊆ F_{i} for i = 1,2. Condition (10) of Lemma A1 implies that F_{1}∩ F_{2} = ∅, so domain(η_{1}) and domain(η_{2}) are disjoint.

Condition (19). This is a consequence of Proposition (10) of Lemma A1.

Condition (20). By the definition of η_{i} this holds with equality.

Condition (21). This follows from χ,χ̄≀ η_{i} ∈ H and Condition (13) of Lemma A1.

Condition (22). Assume that i,j ∈ {1,2}, i ≠ j are fixed. We have domain(η_{i}) = core(F_{i},χ̄). Condition (11) of Lemma A1 and the fact χ̄≀ η_{j} ∈ H together imply that core(F_{i},χ̄) = core(F_{i},χ̄≀ η_{j}). Therefore domain(η_{i}) = core(F_{i},χ̄≀ η_{j}). F_{1}∩ F_{2} = ∅ so at input χ̄≀ η_{j} and at times belonging to the set ⋃ F_{j} we can never access a variable in core(F_{i},χ̄≀ η_{j}), and consequently

domain(η_{i}) ∩ register(T_{j},χ̄≀ η_{j})) = ∅ .

Since all of the assumptions of Lemma A4 hold, its conclusion must hold as well and so χ̄ satisfies Proposition (17).

We will need the following observation to conclude the proof. Let core(F_{i},χ̄) = S_{i}. For any i = 1,2 and for any X ⊆ S_{i}, there is an Ȳ_{i}(X) ⊆ Ȳ_{i}so that η(x) = ζ(x) for all η,ζ ∈ Ȳ_{i}(X), x ∈ S_{i}\X, and |Ȳ_{i}(X)| ≥ \frac{1}{6}2^{−κn} 2^{|X|}. Indeed, we may partition the elements of Ȳ_{i}into disjoint classes according to the values of its elements on the set S_{i}\X. Since there are at most 2^{s_{i}−|X|} classes, at least one class must contain at least 2^{−s_{i}+|X|} |Ȳ_{i}| elements. Ȳ_{i}(X) will be such a class. The stated lower bound on |Ȳ_{i}(X)| and the lower bound on |Ȳ_{i}| formulated in Condition (15) imply |Ȳ_{i}(X)| ≥ \frac{1}{6}2^{−κn} 2^{|X|}.

By Condition (12) of Lemma A1 we have |S_{i}| ≥ κ^{τ}n for i = 1,2. Let [\frac{1}{2}κ^{τ}n] = r. Let z_{i} be the rth smallest element of S_{i} and assume that e.g. z_{1} ≤ z_{2}. Let W_{1} be the set of the r smallest elements of S_{1} and let W_{2} be the set of the r largest elements of S_{2}. Let Y_{i} = Ȳ_{i}(W_{i}) for i = 1,2. According to our previous observation we have

(23). for all i = 1,2, |Y_{i}| ≥ \frac{1}{6}2^{|W_{i}|−κn}.

By the definitions of r, z_{i}, and W_{i}, Condition (1) is satisfied by W_{1} and W_{2}. We claim that the other requirements of the lemma are also met by the following choice of the various parameters. We pick two partial inputs ζ_{1} ∈ Y_{1}, ζ_{2} ∈ Y_{2} in an arbitrary way. Let χ = (χ̄≀ ζ_{1}) ≀ ζ_{2}, λ = 2κ, and μ = |W_{1}|n^{−1} = |W_{2}|n^{−1} . (W_{i}, Y_{i} have already been defined.)

The definitions of σ_{1},σ_{2},ϵ, and δ at the beginning of the proof of Lemma 3.5 show that the requirements of the lemma, stated before the conditions λ ∈ (σ_{2},σ_{1}), μ ∈ (σ_{2},σ_{1}), are met. λ ∈ (σ_{2},σ_{1}) is an

immediate consequence of λ = 2κ, the inequalities σ < κ, κ ≤ 2^{−|logσ|^{\frac{1}{4}}} , and the fact that we choose σ_{2} = \frac{1}{3}σ so that it is sufficiently small with respect to σ_{1}.

The fact that μ ∈ (σ_{2},σ_{1}) is a consequence of the following facts: τ = 1− \frac{1}{50k} (cf. Condition (12) of

Lemma A1), μ = |W_{i}|n^{−1} , |W_{i}| = [\frac{1}{2}κ^{τ}n], σ < κ ≤ 2^{−|logσ|^{\frac{1}{4}}} , σ = 3σ_{2}, and σ_{2} is sufficiently small with respect to σ_{1}. Indeed σ = 3σ_{2} is sufficiently small with respect to σ_{1} (for a fixed k), and so

μ = [ \frac{1}{2}κ^{τ}n] n^{−1} ≤ \frac{1}{2}κ^{τ} ≤ 2^{−|logσ|^{\frac{1}{4}} (1− \frac{1}{50k})} < σ_{1} .

On the other hand

μ = [ \frac{1}{2}κ^{τ}n] n^{−1} > \frac{1}{3}κ^{τ} ≥ \frac{1}{3}σ^{1− \frac{1}{50k}} ≥ \frac{1}{3}σ = σ_{2}

and so μ ∈ (σ_{2},σ_{1}).

We have already seen that Condition (1) of Lemma 3.5 is satisfied.

Condition (2) of Lemma 3.5 is a consequence of the definition of μ. Condition (3). Using the inequality of Condition (23) we get |Y_{i}| ≥ \frac{1}{6}2^{|W_{i}|−κn} ≥ 2^{|W_{i}|−λn} = 2^{μn−λn} . Condition (4). By the definition of r = |W_{i}| = μn we have μn = [\frac{1}{2}κ^{τ}n] and so

μ ≥ \frac{1}{3}κ^{τ} = \frac{1}{3}(\frac{λ}{2})^{τ} = \frac{1}{3}(\frac{λ}{2})^{1− \frac{1}{50k}} .

Therefore

μ^{1+ \frac{1}{100k}} ≥ (\frac{1}{3})^{1+ \frac{1}{100k}} (\frac{λ}{2})^{(1− \frac{1}{50k})(1+ \frac{1}{100k})} ≥ 2λ .

(Here we used that by Condition (17), both κ and λ > 0 are sufficiently small with respect to k.)

Condition (5) of Lemma 3.5 is a consequence of Condition (17) and the definitions of χ and Y_{i}. These definitions imply that (χ ≀ η_{1}) ≀ η_{2} = (χ̄≀ η′_{1}) ≀ η′_{2} where η′_{i}= η_{i}∪ ζ_{i}|_{S_{i}−W_{i}} ∈ Ȳ_{i}.

References

[1] * K. Abrahamson: Time-Space Tradeoffs for Branching Programs Contrasted With Those for Straight-Line Programs. In 27th IEEE FOCS. IEEE Computer Society, 1986. 1.2.2

[2] * K. Abrahamson: Time-Space Tradeoffs for Algebraic Problems on General Sequential Machines. Journal of Computer and System Sciences, 43:269–289, 1991. [JCSS:10.1016/0022-0000(91)90014-V]. 1.2.2

[3] * M. Ajtai: A non-linear time lower bound for boolean branching programs. In 40th IEEE FOCS, pp. 60–70. IEEE Computer Society, 1999. [FOCS:10.1109/SFFCS.1999.814578]. 1.3

[4] * M. Ajtai: Determinism versus Non-Determinism for Linear Time RAMs with Memory Restrictions. Journal of Computer and System Sciences, 65:2–37, 2002. [JCSS:10.1006/jcss.2002.1821]. 1.2.3, 1.2.4, 1.2.5, 1.2.6, 2.1, 2.2, 3.2, 5.1, 5.1, 1, 3, 4, 5, 5.2, 5.2

[5] * P. Beame: General Sequential Time-Space Tradeoff for Finding Unique Elements. SIAM J. Computing, 20(2):270–277, 1991. [SICOMP:20/0220017]. 1.2.2

[6] * P. Beame, M. Saks, and T. S. Jayram: Time-space tradeoffs for branching programs. Journal of Computer and System Sciences, 63(4):542–572, 2001. [JCSS:10.1006/jcss.2001.1778]. 1.2.3, 1.2.5, 1.2.6, 2.1, 3.3

[7] * P. Beame, M. Saks, X. Sun, and E. Vee: Time-space tradeoff lower bounds for randomized computation of decision problems. Journal of the ACM, 50(2):154–195, 2003. [JACM:10.1145/636865.636867]. 1.3

[8] * A. Borodin and S. A. Cook: A time-space tradeoff for sorting on a general sequential model of computation. SIAM J. Computing, 11:287–297, 1982. [SICOMP:11/0211022]. 1.2.2, 1.2.6 [9] * A. Borodin, A. A. Razborov, and R. Smolensky: On lower bounds for read-k-times

branching programs. Computational Complexity, 3:1–18, 1993. 1.2.5, 1.2.6, 2.1, 3.3

[10] * B. Chor and O. Goldreich: Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity. In 26th IEEE FOCS, pp. 429–442. IEEE Computer Society, 1985. 1.2.5, 3.3

[11] * M. Karchmer: Two Time-Space Tradeoffs for Element Distinctness. Theoretical Computer Science, 47:237–246, 1986. [TCS:10.1016/0304-3975(86)90150-7]. 1.2.2

[12] * S. Reisch and G. Schnitger: Three applications of Kolmogorov-complexity. In 23rd IEEE FOCS, pp. 45–52. IEEE Computer Society, 1982. 1.2.2

[13] * J. S. Thathachar: On separating the read-k-times branching program hierarchy. In 30th ACM STOC, pp. 653–662. ACM, 1998. [STOC:10.1145/276698.276881]. 1.2.5, 1.2.6, 2.1, 3.3, 3.12

[14] * Y. Yesha: Time-Space Tradeoffs for Matrix Multiplication and the Discrete Fourier Transform of Any General Sequential Random-Access Computer. Journal of Computer and System Sciences, 29:183–197, 1984. [JCSS:10.1016/0022-0000(84)90029-1]. 1.2.2

AUTHOR

Miklós Ajtai IBM Almaden Research Center ajtai almaden ibm com

ABOUT THE AUTHOR

Miklós Ajtai received his Ph. D. from the Hungarian Academy of Sciences in 1975. His advisor was András Hajnal. He worked in the following areas: axiomatic set theory (independence proofs), lattice theory (posets with meet and join), combinatorics, the theory of random graphs, complexity theory, sorting networks, the theory of lattices (ndimensional grids) and their applications to complexity theory and cryptography. He is a member of the Hungarian Academy of Sciences and was an invited speaker at ICM in 1998. He received the Knuth prize in 2003, and the IBM Corporate Award in 2000.