Journal of Undergraduate Research
Volume 2, Issue 1 - October 2000

Equiseparations

Matthew Belcher

INTRODUCTION

This paper defines and studies new geometric structures called equiseparations, which arise from the problem of finding a lower bound on the size of the threshold circuit needed to compute a certain function in the complexity class NP. This class also contains the notorious Travelling Salesperson problems. Results in [1] and [2] show that our equiseparation question, if answered, will establish that an explicit NP problem has superpolynomial time complexity when the model of computation is restricted to a certain kind of neural network. Restricting the model of computation is one direction taken by researchers in the process of settling the famous P vs. NP problem, i.e., in distinguishing the complexity class of polynomially computable problems from the class NP. See [4] for a comprehensive background and treatment of these complexity classes and their relationships.

PROBLEM DEFINITION

Definition

Let E = (P,H), where P is a set of points and H is a set of hyperplanes in Rd, with |P| = n 0, |H| = m 0. Then, E is an (n, m) - equiseparation0 if for any pair of points x, y P, x, and y have exactly half the hyperplanes between them. Figure 1 shows two (4,4)-equiseparations in 2D. (Note: The problem could instead require x and y to have greater than or equal to half the hyperplanes between them, since we can always add hyperplanes that do not separate any points.)

Problem

Given d dimensions what is the maximum number of points, n, which form an equiseparation in Rd? Alternatively, given n, one can ask, what is the lowest dimension, d, in which one can find an equiseparation of n points? In this paper, we use both formulations.

INITIAL RESULTS AND TOOLS

The following are preliminary observations about equiseparations. First, since we are trying to show that equiseparations do not exist in low dimensions, it is useful for us to consider a special case of the equiseparation question in which all the hyperplanes in the equiseparation pass through the origin. The following proposition, which follows from projective geometry, allows us to do so.

Proposition 1

An (n, m)-equiseparation exists in d dimensions if and only if there is an (n, m)-equiseparation in d + 1 dimensions with all hyperplanes passing through the origin. Thus, we can force hyperplanes to pass through the origin when it is convenient for us to do so.

In an equiseparation, we do not need to concern ourselves with the actual coordinates of points and hyperplanes. All that matters is the relationship between them. Therefore, we use a notation from the study of oriented matroids that reflects this fact[5]. For each hyperplane, we can define a positive side and a negative side. Also, we can order the hyperplanes arbitrarily. Then, we can define each point as a sign vector, with the i^th term of the sign vector is 1 if the point is on the positive side of the i^thhyperplane and -1 if the point is on the negative side. Similarly, by ordering the points, each hyperplane can be represented as a sign vector where the i^th term in the vector is 1 if the i^th point is on the positive side of the hyperplane, and -1 if it is on the negative side. Then an equiseparation exists if and only if the set of sign vectors of the points is pairwise orthogonal, since, from the definition of inner product, this means that the points are on opposite sides of exactly half the hyperplanes.

This naturally leads to the following matrix:

Definition:The equiseparation matrix X as X_ij = 1 if the i^th point is on the positive of the j^th hyperplane, and -1 otherwise. If the points and hyperplanes in X are all in d-dimension, then we say the equiseparation matrix X is realized in d.

To demonstrate the utility of these observations, we will show how this definition facilitates the proof of the following.

Proposition 2

Without loss, we can assume |H| > |P|.

LOW-DIMENSIONAL RESULTS

We will now attempt to answer the two equiseparation questions for low dimensions. First, we will see that the maximum nhumber of points for an equiseparation in 2D is 4, then we will see that the smallest dimension in which one can place 6 points in 3. First, however, we prove a short lemma that is useful in the proofs, and also serves to demonstrate the proof method we use.

Lemma 3

There is no equiseparation possible with 3 co-linear points in 2D.

FIVE POINT EQUISEPARATION IS IMPOSSIBLE IN 2D

We have already seen an equiseparation of 4 points in 2D, so all that remains to show that this is the maximum number of points is to show that 5 points is impossible. We do that now. Our proof method that finds all possible unique point configurations in 2D in which an equiseparation may be possible, i.e. those not barred by the above lemma, them proceeds to show why an equiseparation is not.

Proposition 4

There is no equiseparation possible with 5 points in 2D.

SIX POINTS IN 3D

We now wish to find the smallest dimension in which we can place six points in an equiseparation. We saw in the previous section that it is impossible in 2D, so we move on to 3D. It turns out it is possible in 3D, as we now show.

Proposition 5

An equiseparation of 6 points exists in 3D.

TECHNIQUES FOR ARBITRARY DIMENSION

Clearly, it would be very difficult to extend the proof methods used above to arbitrary dimension. We need something more powerful. This brings us then to Hadamard matrices. the definition of a Hadamrd matrix and general properties about them can be found in [6]. To aid our progress, we will make one critical assumption about equiseparations. We assume that, if an equiseparation exists with 2^p points and hyperplanes passing through the origin, then there is one with hyperplanes passing through the origin whose equiseparation matrix is the Hadamard matrix H_2p. This may not be true in dimensions which are not a power of 2, but for our application, we will consider only dimensions which are powers of 2, so the assumption is justified.

OBSERVATIONS ON HADAMARD MATRICES

We now make some observations about Hadamard matrices. A Haramard matrix can be defined recursively in what is called the Sylvester form as follows:

It is also helpful to label the rows and columns of an H_2p Hadamard matrix with lexigraphically with elements of F₂^P. WE can then show the following lemma.

Lemma 6

The (x,y)^th entry of H_2p in Sylvester form (when x and y are expressed as elements of F₂^P) is given by

(-1) (^x,y)

This lemma gives us a formula that allows us to deal with equiseparations in an abstract way, which gives us the ability to deal with higher dimensions, and possibly induct to answer the equiseparation question for arbitrary dimension.

DEMONSTRATION OF PROOF METHOD USING HADAMARD MATRICES

First, we make some observations. Suppose we hve an N- dimensional space A divided into orthants by the coordinate hyperplanes. Define the sign vector of an orthant to be the vector that gives the signs of the terms of any vector in an orthant. Then, if we can find a d-dimensional subspace B of A that intersects a set of orthants of A whose sign vectors are orthogonal, then we can place points in those orthants on B, and each of these points will be separated by exactly half the hyperplanes, all of which pass through the origin. Thus, we have an equiseparation in d-dimensions with planes passing through the origin. The equiseparation matrix is the matrix whose rows are the sign vectors of the orthants intersected by A.

Proposition 7

The Hadamard matrix H2P cannot be realized in p dimensions with hyperplanes through the origin.

Before we prove this proposition, we will need the following useful theorem, which allows us to slightly alter the proposition into a form that is easier to prove. First some definitions.

Definition: A subspace S intersects an orthant x if there exists a vector v E S whose signs exactly match the sign vector of x.

Definition: A subspace S touches an orthant x if there exists a vector v E S

whose signs match the sign vector of x wherever v is non-zero.

Duality Theorem

For all subspaces S, S intersects some orthant x if and only if S^{^} does not touch x except at the origin. Proposition 8

The Hadamard matrix H_2p can be realized in 3/4*₂^P dimensions.

CONJECTURE FOR A TIGHTER LOWER BOUND

The conjecture presented in this section, if proven true, will show a much tighter lower bound on the dimension needed to have an equiseparation of 2^p points. This lower bound is syperpolynomial, which is our desired result.

Conjecture 1

H_2p cannot be realized in 2^p-1 dimension with planes passing through the origin.

We will reformulate this problem as in the previous two proofs. It then becomes the following:

Conjecture 2

Any subspace S R^2pof dimension 2^p-1 does not intersect at least one H_2p orthant.

Conjecture 3

Any subspace S R^2p of dimension 2^p-1 touches at least one H_2p orthant.

Assumption

For simplicity, we make the assumption that every subspace S is spanned by vectors in {1, -1}_2p.

Intended proof of Conjecture 3: By induction.

Induction step A:

Induction step B:

RESULTS TOWARD INDUCTION STEP B

Results toward Induction Step B

CONCLUSION

Propositions 1 and 2 in the previous section show that H cannot be
Belcher Equation 2

REFERENCES

M. Sitharam "Approximation from Linear spaces and Complexity Applications" ECCC Report (1996)
P. Enflo and M. Sitharam "Stable bases and applications to complexity" ECCC Report (1996)
M. Sitharam and T. Straney "Derandomized Learning of Boolean Functions"
C.H. Papadimitriou Computational Complexity (1994)
A. Björner, M. Las Vergnas, B. Strumfels, N. White, G. Ziegler: Oriented Matroids Encyclopedia of Computation 5-14 (1993)
S. S. Agaian: Hadamard matrices and their Applications Lecture notes in mathematics; 1168 (1985)