A mapping of the domain , is called a threshold function iff there exists a line separating the sets of its ones and zeros (points at which the function takes values 1 and 0, respectively).

A teaching set of a threshold function g is a subset of its domain such that the values of g at the points from this set uniquely define the function. A teaching set of g is called minimal (or irreducible) iff no its proper subset is teaching for g. It is known (e.g., see [3, 9, 13]) that the minimal teaching set T(g) for any threshold function g is unique (this also holds for threshold functions in higher dimensions). In [9, 11] it is proved that T(g) consists of 3 or 4 points if m 2. Here we derive exact formulae for the number of threshold functions corresponding to these values. In the case when T(g) consists of 3 points, we further compute the number of threshold functions g with the specified number (one or two) of zeros in T(g), answering the question posed in [2]. We also prove that the average cardinality of the minimal teaching set is asymptotically 7we discuss some corollaries of this result concerning special arrangements of lines in the plane.

We remark that the cardinality of the minimal teaching set of threshold functions defined on many -dimensional grid is studied in a number of publications (e.g., see the bibliography in [12]). In particular, the bounds of the average cardinality of the minimal teaching set of threshold functions are given in [3, 10].

Let m . We denote by M0(g), M1(g) the set of zeros and the set of ones of g, respectively, that is

The function g is called threshold iff there exist real numbers a0, a1, a2 such that

Without loss of generality we can assume that the numbers a0, a1, a2 are integer and a1, a2 are not zero simultaneously. We call the line a1x1 separation line for the threshold function g. Note that for any line a1x1 , there are two associated threshold functions: a function g defined by (1) holds and a function h with M0(h) , which also satisfy g(x) + h(x) = 1 for any x

LetT (m, n)be the setofall threshold functionsdefined on Em

Two distinct points p, pare called adjacent if and only if the line segment [p] contains no other point from Em

9

Figure 1: Threshold functions g3 (left panel) and |T(h)| = 4 (right panel) and their separation lines. The empty dots represent zeros of the function, while the circled dots form its minimal teaching set.

Lemma 1 ([1, 6]). The number of ordered pairs (pof adjacent points in Em

Lemma 2 ([5]). If m

Denote by l(m, n) the number of lines passing through at least two points in Em

Lemma 3 ([7, 4]).

Theorem 4 ([6]).

Corollary 5.

where asymptotics holds for m

We remark that the asymptotic behavior of t(m, n) was studied by many authors (sometimes using different terminology), for example, [6, 1, 8, 2, 14, 5].

A set T for any other function h there exists x ). A teaching set of g is called minimal or irreducible iff no its proper subset is teaching for g. A point x iff there exists h ) such that g(x)

Lemma 6 ([3, 9, 13]). For any function g , the minimal teaching set of g is unique and consists of all essential points of g.

We remarkthatLemma 6 alsoholdsforthreshold functionsdefined on many-dimensional

grid.

Denote by T(g) the minimal teaching set of g. In [9, 11] it is shown that

Theorem 7.

Proof. Denote by h(m, n, i, j) the number of threshold functions defined on the domain Em such that the point (i, j) is essential. By Lemma 6,

Let us consider all lines containing the point (i, j) and at least one other point from Em . Denote by L(m, n, i, j) the set of all such lines (see Fig. 2) and let l(m, n, i, j) = |L(m, n, i, j)|. The lines from L(m, n, i, j) partition the plane into 2

It is easy to see that any line ) containing the point (i, j) is associated with two threshold functions, for which the point (i, j) is essential and a zero (Fig. 2). It is clear that these functions are uniquely determined by the two lines from L(m, n, i, j) adjacent to . Moreover, there is no other function in T (m, n), for which the point (i, j) is essential and a zero.

Thus, we have 2 ) threshold functions for which the point (i, j) is essential and a zero. We have the same number of functions for which the point (i, j) is essential and not a zero (i.e., the value at (i, j) is 1). Hence h(m). Now from (7) we get

Let L(m, n) be the set of all lines passing through at least two points from Em l(m, n) = |L(m, n)|. For a line ), we denote by z(m) the number of points in

Figure 2: The lines forming L(4, 4, 1, 1) with l(4, 4, 1, 1) = 8 and a line 1) defining two threshold functions.

Em belonging to . Now from (8) we get

We remark that if contains exactly k points from Em , then they form k 1 adjacent pairs of points. Then by Lemma 1,

Substituting here the expressions (2) and (3), we obtain (6).

Theorem 7 and Lemma 2 imply the following asymptotics for

Corollary 8. For m

Denote by t) the number of functions g ) such that Corollary 8 implies that each of the quantities t3(m) is asymptotically 12t(m, n). Below we give exact formulae for t3(m

Theorem 9.

Proof. From the conditions

we obtain

Substitution of the expressions (3) and (6) here completes the proof.

It is known that a minimum teaching set of a non-constant threshold function g with |T(g)| = 4 always contains two zeros [11]. The threshold functions g with |T(g)| = 3 can be classified depending on whether their minimal teaching sets contain one or two zeros. The question of counting threshold functions in these classes was posed and partially answered in [2]. Below we give a complete answer to this question.

Let u) be the number of threshold functions g on Em that g(0) and a minimum teaching set of g consists of zeros and 3 ones (). The number u0) enumerates so-called unstable threhold functions [2]:

which can be also expressed as

Theorem 11.

Furthermore, for any n, we have

Proof. Trivially, we have u0). Furthermore, the bijection g implies that u) and thus we can focus only on the case 0, for which u0). The exact formulae now easily follow from Theorem 9 and Lemma 10. To obtain the asymptotics, we use Lemma 2 and notice that s(m

Figure 3: The partition of the plane by the lines a1x1 1, where (x1There are c(320 generalized 3-polygons, c4(3, 3) = 9 generalized 4-polygons, e(3, 3) = 43 edges, and v(3, 3) = 15 vertices in this partition.

5.1 Partition of the plane

For a threshold function g ), all vectors (a0ficients of its separating line, form a polyhedral cone defined by the following system of linear inequalities:

Furthermore, a minimal teachingsetT(g)consistsofthe pointsfrom Emthatcorrespond to irredundant inequalities in (9). Thus, there is a bijection of the set T (m, n) into the set of cones in the partition of the space of parameters by all the planes a1x1 . Moreover, the planes that form the boundary of each of these cones correspond to the points in T(g). This construction is well known in the threshold logic [9, 13].

For . The mapping g represents a bijection between the sets ), for which the teaching sets are invariant.

Without loss of generality, for g ), we can assume that a0 = 1. In this case the points (a1such that the line a1x1 1 is separating for g represent the solutions to the following system of linear inequalities:

So we have the bijection of the set ) into the set of all polygonal cells in the partition of the plane by the lines a1x1 1, where (x1(see Fig. 3).

Let c(m, n), e(m, n), v(m, n) be respectively the number of cells, edges, and vertices (i.e., intersection points) in this partition. We call a convex polygon (possibly unbounded) by a generalized k-polygon if it can be obtained as the intersection of an k-faced polyhedral cone with a plane that does not contain the cone vertex. Every unbounded generalized k-polygon representing a cell in the partition has two parallel or two non-parallel infinite edges (i.e., rays). In the former case, the polygon has k 1 vertices; in the latter case, it has k 2 vertices.

Theorem 12. The cells in the partition of the plane by the lines a1x1 where (x1, are only generalized 3- and 4-polygons. The number of such cells is, respectively,

which imply that

Moreover,

where s(m, n) is defined in Lemma 10. Everywhere above the asymptotics holds for m

Proof. The number of cells is c(mAmong them there are c3(m)generalized 3-polygonsand c4(m)generalized 4-polygons, since the mapping g is a bijection between ), for which the teaching sets are invariant. To obtain (10) and (11) it remains to apply Theorem 9 and Lemma 2.

Let v) be the number of infinite vertices (i.e., families of parallel lines) in the partition, which also equals the total number of infinitely-distant edges in the unbounded generalized polygons. Each family of parallel lines is defined by the slope, which may be zero (for the horizonal lines), infinite (for the vertical lines), or represent an irreducible fractionpq with 1 1. Since the number of such fractions is given by s(m

Since 3c3(m) gives twice the number of edges including infinitely-distant ones, we have 3c3(mwhich together with (10) implies (12).

To find the number of vertices, we apply Euler characteristic for the plane: v(me(m, n) + c(m, n) = 1 and use (11) and (12) to obtain (13).

Figure 4: The partition of the triangle by the lines a1x1 1, where (x1are c33 triangles, c14 quadrilaterals, e82 edges, and vvertices in this partition.

5.2 Partition of the triangle

Now we consider the triangle with vertices (0, 0), (1, 0), (0, 1) in the plane its partition by the lines a1x1 1, where (x1Let c) be respectively the number of cells, edges, and vertices in this partition.

Theorem 13. Every cell in the partition of the triangle with vertices (0, 0), (1, 0), (0, 1) by the lines a1x1 , there is either a triangle or a quadrilateral. Moreover, the number of triangles and quadrilaterals is given by the following formulae:

which imply that

Moreover,

Everywhere above the asymptotics holds for m

Proof. We notice that all cells incident to the axes are triangular and use Theorem 12 to obtain

The number e) of edges satisfies the equality: 2en + 1, which implies (14). Now we use Euler characteristic for the triangle: ve1 to obtain (15).

The first author was supported by the National Science Foundation under the grant No. IIS-1253614.

[1] D. M. AOn the number of linear partitions of the (m, n)-grid, Inform. Process. Lett., 38 (1991), pp. 163–168.

[2] M. A. Alekseyev, On the number of two-dimensional threshold functions, SIAM J. Discrete Math., 24 (2010), pp. 1617–1631.

[3] M. Anthony, G. Brightwell, and J. Shawe-Taylor, On specifying Boolean functions by labelled examples, Discrete Appl. Math., 61 (1995), pp. 1–25.

[4] P. Haukkanen and J. K. Merikoski, Some formulas for numbers of line segments and lines in a rectangular grid, Ars Combin., 104 (2012), pp. 353–361.

, Asymptotics of the number of threshold functions on a two-dimensional rectangular grid, Discrete Appl. Math., 161 (2013), pp. 13–18.

[6] J. Koplowitz, M. Lindenbaum, and A. Bruckstein, The number of digital straight lines on an N , IEEE Trans. Inform. Theory, 36 (1990), pp. 192–197.

[7] S. Mustonen, On lines and their intersection points in a rectangular grid of points, preprint, (2009). http://www.survo.fi/papers/PointsInGrid.pdf.

[8] V. N. Shevchenko, Qualitative Topics in Integer Linear Programming, vol. 156 of Translations of Mathematical Monographs, AMS, 1997.

[9] V. N. Shevchenko and N. Y. Zolotykh, On the complexity of deciphering the threshold functions of k-valued logic, Dokl. Math., 58 (1998), pp. 268–270.

[10] M. A. Virovlyanskaya and N. Y. Zolotykh, An upper bound for the average cardinality of minimal teaching set of a threshold function of many-valued logic, Vestn. Nizhegorod. Univ. N. I. Lobachevskogo, Mat. Model. Optim. Upr., (2003), pp. 238–246. (in Russian).

[11] N. Y. Zolotykh, On the complexity of deciphering threshold functions in two variables, in Proceedings of XI International school-seminar “Synthesis and complexity of control systems”. Part I, Center of applied research of MSU Faculty of Mechanics and Mathematics, 2001, pp. 74–79. (in Russian).

[12]

, Bounds for the cardinality of the minimal teaching set of a threshold function of many-valued logic, Mathematical Topics in Cybernetics, 17 (2008), pp. 159–168. (in Russian).

[13] N. Y. Zolotykh and V. N. Shevchenko, Estimating the complexity of deciphering a threshold functions in a k-valued logic, Comput. Math. Math. Phys., 39 (1999), pp. 328– 334.

[14] J. Zunic, Note on the number of two-dimensional threshold functions, SIAM J. Discrete Math., 25 (2011), pp. 1266–1268.