PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 82(96) (2007), 129–134 DOI 102298/PIM0796129K

AN ENUMERATIVE PROBLEM IN THRESHOLD LOGIC

Žana Kovijanić Vukićević

Abstract. The number of Boolean threshold functions is investigated. A new lower bound on the number of n-dimensional threshold functions on a set {0, 1, …, K − 1} is given.

1. Introduction

Let K ∈ N be positive integer and E_{K} = {0, 1, …, K − 1}. An n-dimensional threshold function on E_{K} is a function f : E_{K}^{n} → {−1, 1} such that there exists a hyperplane π separating the pre-images f^{−1}(−1) and f^{−1}(1). The question is: what is the number P (K, n) of n-dimensional threshold functions on E_{K}?

The bounds for these numbers have been well-studied only for the case K = 2. Nevertheless, the asymptotic even for P (2, n) is still open. The case K = 2 has an application in switching theory.

A Boolean (switching) function f : {−1, +1}^{n} → {−1, +1} is a threshold function when there exist real numbers a_{0}, a_{1}, …, a_{n} so that

(1)  f(x) = sgn(a_{0} + ∑_{i=1}^{n} a_{i}x_{i})

i.e., hyperplane that separates vertices of n-dim cube in which f takes value −1 from the vertices in which it takes value 1. The number of all switching functions is obvious, but the basic problem in the study of threshold functions, their enumeration for each n, is still open.

Clearly, two sets of weights a = (a_{0}, a_{1}, …, a_{n}) and b = (b_{0}, b_{1}, …, b_{n}) generate different functions f and g by rule (1) iff two points a, b ∈ R^{n+1} are separated by one of 2^{n} hyperplanes 1±x_{1} ±⋯±x_{n} = 0 in R^{n+1}. Thus, each distinct hyperplane partition of a cube, or each threshold function defined on that cube, corresponds to one of regions in R^{n+1} defined by the arrangement of the upper 2^{n} hyperplanes. This connection with the number of cells in central hyperplane arrangement yields that the best upper bound of the number P (2, n) of threshold functions given by Schläfli [3] in 1850 is:

2000 Mathematics Subject Classification: Primary 05A16; Secondary 94C10.

P (2, n) < 2 ∑_{i=0}^{n} \binom{2^{n} − 1}{i} ∼ exp_{2} (n^{2} − n log n − O(n)), n → ∞

By direct application of Odlyzko’s [2] and Winder’s [6] results, Zuev [4] in 1989 obtained the asymptotics log_{2} P (2, n) ∼ n^{2}, n → ∞. More precisely, he obtained a lower bound

(2)  P (2, n) > exp_{2} (n^{2} − \frac{10n^{2}}{ln n} − O(n ln n))

The interpretation in the terms of hyperplane arrangements permits us to obtain an upper bound P (K, n) ⩽ 2 ∑_{i=0}^{n} \binom{K^{n}−1}{i}. For the lower bound it is necessary to develop much more sophisticated methods. Here we sketch the proof for the next lower bound:

P (K, n + 1) ⩾ \frac{1}{2}\binom{K^{n}}{⌊n − 2\frac{n}{log_{K} n} − 4⌋}

× [P (K, ⌊2\frac{n}{log_{K} n} + 3⌋) − 1 + ⌊2\frac{n}{log_{K} n} + 4⌋ (P (K, ⌊2\frac{n}{log_{K} n} + 2⌋) − 1)]

As far as we now, this is the best lower bound for P (K, n).

2. Previous work

Without loss of generality we may suppose that

E_{K} = \begin{cases}\{±1, ±3, …, ±(2Q − 1)\} , & K = 2Q \\ \{0, ±1, ±2, …, ±Q\} , & K = 2Q + 1 \end{cases}

Hyperplane H : a_{1}x_{1} + a_{2}x_{2} + ⋯ + a_{n}x_{n} = 0 divides the cubical net E_{K}^{n} on the three parts:

A_{H} = E_{K}^{n} ∩ H^{+}, B_{H} = E_{K}^{n} ∩ H, C_{H} = E_{K}^{n} ∩ H^{−}.

For arbitrary ε > 0 let

H_{−ε} : a_{1}x_{1} + … + a_{n}x_{n} − ε = 0
H_{ε} : a_{1}x_{1} + … + a_{n}x_{n} + ε = 0.

To be definite, assume that H_{−ε}^{+} ∩H_{ε}^{−} ≠ ∅ and ε is chosen such that (H_{−ε}^{+} ∩ H_{ε}^{−})∩ E_{K}^{n} = B_{H}. Then, A_{H} = E_{K}^{n} ∩ H_{ε}^{+} and C_{H} = E_{K}^{n} ∩ H_{−ε}^{−}. On the other hand, each triplet (A_{H}, B_{H}, C_{H}) defines a hyperplane partition of the (n + 1)-dim cubic net E_{K}^{n+1} on the following way:

• If K is even, i.e., K = 2Q, the partition is defined by hyperplane

\overline{H} : a_{1}x_{1} + … + a_{n}x_{n} + \frac{ε}{2Q − 1}x_{n+1} = 0

• If K is odd, i.e., K = 2Q + 1, the partition is defined by hyperplane

\overline{H} : a_{1}x_{1} + … + a_{n}x_{n} + \frac{ε}{Q}x_{n+1} = δ,

where δ is sufficiently small such that \overline{H} ∩ (E_{K})^{n+1} = ∅.

Proof of our main result is based on the following simple observation (see [1]):

Lemma 1. Let H and G be two hyperplanes in R^{n} so that B_{H} ≠ B_{G}. Then, associated hyperplanes \overline{H} and \overline{G} generate different partitions of the (n + 1)-dim cubical net.

It follows from the above that the lower bound of the number P (K, n) can be obtained by estimation of the number of sets B_{H} appearing in triplets (A_{H}, B_{H}, C_{H}). Let us take the vectors v_{1}, v_{2}, …, v_{p} ∈ E_{K}^{n} in whose linear cover there is no “new” vector from E_{K}^{n}. Sets {v_{1}, v_{2}, …, v_{p}} will play the role of the B_{H}!

The most important argument in the construction of the sets B_{H} is the next theorem, proved in [1]. It is a generalization of Odlyzko’s result [2] on subspaces spanned by random selections of ±1 vectors.

Theorem 1. For any K ∈ N and any nonnegative integer p ⩽ n − 2\frac{n}{log_{K} n} − 4 probability P that in the linear cover of p vectors v_{1}, v_{2}, …, v_{p} chosen at random from the set E_{K}^{n} there is at least one vector from E_{K}^{n} ∖ ⋃_{i=1}^{p}⟨v_{i}⟩ tends to zero, as n tends to infinity.

Let p = ⌊n − 2\frac{n}{log_{K} n} − 4⌋ be the value from Theorem 1 and let M_{n} denotes the family of p × n matrices with elements from set E_{K}. Let M′_{n} be subset of M_{n} such that any two rows of the matrix M ∈ M′_{n} are linearly independent. In that case, ∥M_{n}^{′C} ∥ ⩽ K^{n}K\binom{p}{2}K^{n(p−2)} i.e., ∥M′_{n}∥ ∼ ∥M_{n}∥, n → ∞.

Over the family M′_{n} we define the relation ∼ on the next way: A ∼ B iff A is obtainable from B by permutation of the rows or by replacement of one row with the row that is collinear to that one. ∼ is equivalence relation and each equivalence class has p!K^{p} elements. Two matrices from the same class of equivalence generate the same linear subspace. By Theorem1, linear covers of the row-vectors of almost all K-valued matrices M ∈ M_{n} do not contain K-valued vectors v ∈ E_{K}^{n} different from that row-vectors and vectors collinear with any of them. It follows that the number of sets B_{H} from Lemma 1 is greater than or equal with

\frac{1}{2} \frac{K^{np}}{p!K^{p}}

Hence log_{K} P (K, n) ∼ n^{2}, n → ∞.

The biggest r ∈ N with the property that any r vectors of the system S = {s_{1}, …, s_{n}} are linearly independent is called the strong rank of S. It is denoted by r_{st}(s_{1}, …, s_{n}).

In [5] we have proved that the probability that a random n by n K-valued matrix is singular tends to zero. The next theorem can be proved by a little modification of that one.

Theorem 2. Let p = ⌊n − 2\frac{n}{log_{K} n} − 4⌋ and let \overline{a}_{1}, …, \overline{a}_{n} be at random independently chosen from E_{K}^{p}. The probability that r_{st}(\overline{a}_{1}, …, \overline{a}_{n}) = p tends to 1, as n tends to infinity.

3. The main result

Let p = ⌊n−2\frac{n}{log_{K} n} −4⌋ and let A_{n} denotes the event: the rows v_{1}, v_{2}, …, v_{p} ∈ E_{K}^{n} and the columns c_{1}, c_{2}, …, c_{n} ∈ E_{K}^{p} of the random matrix M_{p×n} ∈ E_{K}^{pn} have the next properties:

(1) in the linear cover of the vectors v_{1}, v_{2}, …, v_{p} there is no “new” vector of the same type, i.e., vector from E_{K}^{n} ∖ ⋃_{i=1}^{p}⟨v_{i}⟩,

(2) r_{st}(c_{1}, …, c_{n}) = p.

On the basis of theorems 1 and 2, we have that P (A_{n}^{c}) → 0 as n → ∞. Therefore, starting from some enough large n_{0} ∈ N, the number of p-sets {v_{1}, v_{2}, …, v_{p}} ⊂ E_{K}^{n}, n ⩾ n_{0}, that satisfy the upper two conditions is bigger than \frac{1}{2} \binom{K^{n}}{p}. Let B = {v_{1}, v_{2}, …, v_{p}} be one of them. Because of the first property, B is one of the sets B_{H} introduced in previous section. Denote by B p-dimensional linear subspace spanned by B. In what follows, with different chose of hyperplanes that expand subspace B, we are going to get a different hyperplane partitions of the net E_{K}^{n}, with the same set B. Because of the simplicity of presentation, instead of the net E_{K}^{n}, only the cube C = {−1, +1}^{n} will be considered on. Generalization on arbitrary K will be obvious.

Let D be the orthogonal complement of the space B. By g_{1}, …, g_{n} denote the images of the basis vectors e_{1}, …, e_{n} of the space R^{n} under the orthogonal projection pr_{D} : [−1, 1]^{n} → D and by G_{i}, i = 1, …, n linear segments conv{−g_{i}, g_{i}}. First, let us prove that any d = n − p vectors of the set g_{1}, …, g_{n} are linearly independent. If it would not be true, there would be d vectors, for instance g_{1}, …, g_{d}, and their linear combination α_{1}g_{1} + ⋯ + α_{d}g_{d} = 0, with some nonzero coefficient. This is equivalent with α_{1}e_{1} + ⋯ + α_{d}e_{d} ∈ B − {0}, i.e.,

det(v_{1}, …, v_{p}, e_{1}, …, v_{d}) = | \begin{matrix}v_{1}^{1} & v_{1}^{2} & … & v_{1}^{d} & v_{1}^{d+1} & … & v_{1}^{n} \\ v_{2}^{1} & v_{2}^{2} & … & v_{2}^{d} & v_{2}^{d+1} & … & v_{2}^{n} \\ ⋮ & ⋮ & ... & ⋮ & ⋮ & ... & ⋮ \\ v_{p}^{1} & v_{p}^{2} & … & v_{p}^{d} & v_{p}^{d+1} & … & v_{p}^{n} \\ 1 & 0 & … & 0 & 0 & … & 0 \\ 0 & 1 & … & 0 & 0 & … & 0 \\ ⋮ & ⋮ & ... & ⋮ & ⋮ & ... & ⋮ \\ 0 & 0 & … & 1 & 0 & … & 0 \end{matrix}| = 0

It follows that

| \begin{matrix}v_{1}^{d+1} & v_{1}^{d+2} & … & v_{1}^{n} \\ v_{2}^{d+1} & v_{2}^{d+2} & … & v_{2}^{n} \\ ⋮ & ⋮ & ... & ⋮ \\ v_{p}^{d+1} & v_{p}^{d+2} & … & v_{p}^{n} \end{matrix}| = 0.

This is contrary to the assumption r_{st}(c_{1}, …, c_{n}) = p, where c_{i} = (v_{1}^{i}, v_{2}^{i}, …, v_{p}^{i}) are the column vectors of the matrix defined by row vectors v_{1}, …, v_{p} ∈ {−1, 1}^{n}.

We conclude that the image of cube C under orthogonal projection on to ddimensional plane D, is a cubical zonotop Z = G_{1} + … + G_{n} and any r ⩽ d − 1 vectors g_{i_{1}}, …, g_{i_{r}} ∈ {g_{1}, …, g_{n}} define r-dimensional facies

F = G_{i_{1}} + ⋯ + G_{i_{r}} + ∑_{j≠i_{1},...,i_{r}} δ_{j}g_{j}, δ_{j} ∈ {±1}.

Line segments G_{i_{1}}, …, G_{i_{r}} will be called the components and vector ∑_{j≠i_{1},...,i_{r}} δ_{j}g_{j} the moving vector of F.

We shall now prove that different central partitions of the set of vertices

p(Z) = \{δ_{1}g_{1} + δ_{2}g_{2} + ⋯ + δ_{n}g_{n} | δ_{1} = ±1, i = \overline{1, n}\}

of zonotope Z yield to the different central partitions of cube C (the partition is central if it is defined by hyperplane that contains the origin; the points of P (Z) are not necessary all distinct).

Let us take hyperplane H_{d−1} = ⟨h_{1}, …, h_{d−1}⟩ that define a partition of the set P (Z). Let h ∈ D be its normal vector. Than, H_{n−1} = ⟨h_{1}, …, h_{d−1}, v_{i_{1}}, …, v_{i_{p}}⟩ = V + H_{d−1} is hyperplane in R^{n} and h is its normal vector. Thus, for any v ∈ R^{n}:

⟨v, h⟩ < 0 iff ⟨pr_{D}v, h⟩ < 0

Let cube F_{0} = G_{1}+⋯+G_{d−1}+∑_{j=d}^{n} δ_{j}g_{j} be a facet (maximal or (d−1)-dimensional face) of zonotope Z and B_{0} = G_{1} + ⋯ + G_{d−2} + ∑_{j=d−1}^{n} δ_{j}g_{j} a facet of cube F_{0}. Denote by F_{1} the facet of Z such that F_{0} ∩ F_{1} = B_{0}. The components of the face F_{1} are G_{1}, …, G_{d−2} and G_{i} for some i ∈ {1, …, n} ∖ {1, …, d − 1}. Without loose of generality it can be assumed that i = d. Let B_{1} be a facet of F_{1} that is the reflection of B_{0} in the center of cube F_{1}. Its components are G_{1}, …, G_{d−2}, too. If we continue this procedure, we obtain the sequence of (d − 1)-dimensional faces F_{0}, F_{1}, …, F_{p+2} and the sequence of (d−2)-dimensional faces B_{0}, B_{1}, …, B_{p+2} such that F_{i} ∩ F_{i+1} = B_{i}; B_{i} and B_{i+1} are mutually symmetric faces of the cube F_{i+1}, i = \overline{0, p}, F_{p+2} is the reflection of F_{0} in the origin, G_{1}, …, G_{d−2} are the components of each (d − 2)-dimensional face B_{i}, i = \overline{0, p + 1} and the components of the face F_{i} are G_{1}, …, G_{d−2}, G_{d−1+i}, for each i = \overline{0, p + 2}.

Let A be (d − 1)-dimensional affine cover of the cube F_{0}. Each of P (2, d − 1) hyperplane partitions of F_{0} can be uniquely expanded to central hyperplane partitions of the zonotope Z. Let us consider the number of hyperplane partitions of Z whose restriction on A is negative-empty partition of the face F_{0}.

The number of all hyperplane partitions of (d − 2)-dimensional cube B_{1} is P (2, d − 2). P (2, d − 2) − 1 of them are proper or positive-empty. Let H_{d−3}^{1} be hyperplane in Aff(B_{1}) that generates one of them. Denote by H_{d−2}^{1} (d − 2)- dimensional subspace that linearly spans H_{d−3}^{1}. In D there is a hyperplane H_{d−1}^{1} such that

(1) H_{d−2}^{1} ⊂ H_{d−1}^{1}

(2) F_{0} is contained in the positive halfspace H_{d−1}^{1+},

(3) B_{1} is not contained in the positive halfspace H_{d−1}^{1+}.

If we continue the same procedure for the faces B_{i}, i = 2, …, p, in each of p steps we construct P (2, d − 2) new partitions of Z with the next properties:

(1) the partitions obtained in i-th step are defined by the the proper or positive-empty partitions of (d − 2)-dimensional cube B_{i} in the affine plane Aff(B_{i}),

(2) the faces F_{0}, B_{1}, B_{2}, …, B_{i−1} are contained in the positive halfspace H_{d−1}^{i+},

(3) the face B_{i} is not contained in the positive halfspace H_{d−1}^{i+}.

Hence, the number of hyperplane partitions of Z whose restriction on A is negative-empty partition of the face F_{0} (i.e., F_{0} is contained in the positive halfspace) is p (P (2, d − 2) − 1) .

The lower bound

P (2, n + 1) ⩾ \frac{1}{2}\binom{2^{n}}{⌊n − 2\frac{n}{log_{2} n} − 4⌋}

× [P (2, ⌊2\frac{n}{log_{2} n} + 3⌋) − 1 + ⌊2\frac{n}{log_{2} n} + 4⌋ (P (2, ⌊2\frac{n}{log_{2} n} + 2⌋) − 1)]

follows from d = n − p = 2\frac{n}{log_{K} n} − 4 and the above estimates.

References

[1] A. A. Irmatov and Ž. Kovijanić, On the asymptotic of the logarithm of the number of threshold functions in K-valued logic, Discrete Math. Appl. 8:4 (1998), 331355; Russian original in Diskretn. Mat. 10:3 (1998), 35–56.

[2] A. M. Odlyzko, On subspspaces spanned by random selections of ±1 vectors, J. Combin. Theory Ser. A 47 (1988), 124–133.

[3] L. Schläfli, Gesammelte mathematische Abhandlugen, Band 1, Birkhäuzer, Basel, 1850.

[4] Yu. A. Zuev, Methods of Geometry and Probabilistic Combinatorics in Threshold Logics, Discrete Math. Appl. 2 (1992), 427–438

[5] Žana Kovijanić, On the singularity of random {0, 1, …, K} matrices, Math. Montisnigri 17 (2004), 11–16

[6] R. O. Winder, Partitions Or N-space by hyperplanes, SIAM J. Appl. Math. 14:4 (1966), 811– 818

Prirodno-matematički fakultet 81000 Podgorica, p.p. 211 Montenegro

    zanak@cg.yu