Methods for Creating Point Systems

G. G. Pestov

(Presented by the Department of Engineering and Computational Mathematics)

This article studies the specification of a point system by means of the so-called matrix of sections; some properties of the order function are studied, and on the basis of these properties certain finite systems are investigated.

Theorem on the Matrix of Sections

Let us number the points of the system \(S_n\). To the point system \(S_n\) we assign the matrix of sections
\[ A=(a_{ik}), \qquad a_{ik}=\overline{L(x_i,x_k)} \]
(the double bar denotes the number of elements of the set).

We shall consider two point systems equivalent if it is possible to establish a one-to-one correspondence between the elements of \(S_n\) and \(S'_n\) such that
\[ L(x,y)\sim L'(x',y'), \quad \text{if } x\sim x',\; y\sim y'. \]

Theorem 1. If \(S_n\) and \(S'_n\) have identical matrices of sections, then \(S_n\) is equivalent to \(S'_n\).

Proof—we proceed by induction on the number of points.

A. Suppose that the theorem has been proved for \((n-1)\). Under this assumption we shall prove the theorem for \(n\).

Thus, let \(S_n\) and \(S'_n\) be two systems with equivalent matrices of sections. We establish between the points of \(S_n\) and \(S'_n\) the one-to-one correspondence \(x_i\sim x'_i\). Here the numbers of the points in \(S_n\) and \(S'_n\) are specified by the matrices of sections.

Let \(x_k\) be an exterior point [1] of \(S_n\). Then in the \(k\)-th row of the matrix \(A\) there is an element equal to zero. Since, by assumption, the matrices of sections \(A\) and \(A'\) are identical, in the \(k\)-th row of the matrix \(A'\) there is a zero element; i.e., \(x'_k\) is also exterior in \(S'_n\).

Let \(x_i, x_j\) be arbitrary points of \(S_n\); we shall show that the order function
\[ \zeta(x_k,x_i,x_j)=\zeta'(x'_k,x'_i,x'_j). \]

For this, note that the row with number \(k\) contains all integers from \(0\) to \((n-1)\), inclusive, each number occurring once. Indeed, let \(y\) be a point adjacent to \(x_k\), i.e. \(R(x_k,y)=0\).

We normalize the cyclic function [1] by the condition \(N(x_k,y)=1\). Then for all \(x_i\ne x_k\), \(N(x_k,x_i)>0\).

In this case, for any \(x_i, x_j\) we have \(R(x_k,x_i)\subset R(x_k,x_j)\) or \(R(x_k,x_i)\supset R(x_k,x_j)\).

Let \(R(x_k,x_i)\supset R(x_k,x_j)\), \(x_i\ne x_j\). This means that

\[ N(x_k,x_i)<N(x_k,x_j), \]

and also

\[ N'(x'_k,x'_i)<N'(x'_k,x'_j). \]

Then

\[ \xi(x_k,x_i,x_j)=\operatorname{Sgn}\{N(x_k,x_i)N(x_k,x_j)[N^2(x_k,x_j)- \]

\[ -N^2(x_k,x_i)]\}=\operatorname{Sgn}\{N'(x'_k,x'_i)N'(x'_k,x'_j)[N'^2(x'_k,x'_j)- \]

\[ -N'^2(x'_k,x'_i)]\}=\xi'(x'_k,x'_i,x'_j). \]

Thus,

\[ \xi(x_k,x_i,x_j)=\xi'(x'_k,x'_i,x'_j). \tag{1} \]

Consequently, if \(x_k\in L(x_i,x_j)\), then \(x'_k\in L'(x'_i,x'_j)\), and conversely.

Therefore the system \(S_{n-1}\), obtained from \(S_n\) by deleting \(x_k\), and \(S'_{n-1}\), obtained from \(S'_n\) by deleting \(x'_k\), have identical section matrices. Hence \(S_{n-1}\sim S'_{n-1}\). In other words, if \(x\sim x'\), \(y\sim y'\), \(z\sim z'\), and among \(x,y,z\) there is no \(x_k\), then

\[ \xi(x,y,z)=\xi'(x',y',z'). \tag{2} \]

Comparing (2) and (1), we see that

\[ \xi(x,y,z)=\xi'(x',y',z'), \]

if \(x,y,z\in S_n\), \(x',y',z'\in S'_n\), and \(x\sim x'\), \(y\sim y'\), \(z\sim z'\); and this means that \(S_n\sim S'_n\).

B. For three points the theorem is trivial. Consequently, the theorem is proved.

Systems with weights

Let \(S_n\) be a point system. Assign to each point \(x_i\) of the system \(S_n\) a positive number \(p(x_i)\)—the weight of the point.

We form the section matrix for the system with weights

\[ B=(B_{ik}), \]

where

\[ B_{ik}=\sum_{x\in L(x_i,x_k)}p(x). \]

Lemma 1. Let \((B_{ik})\) be the matrix of a system with weights. Let \(x_k\) be an exterior point; if \(B_{ki}=0\), then \(p(x_i)=\min_{j\ne i} B_{ji}\).

Proof—obvious.

Lemma 2. If \(x_k\) is an exterior point, then \(\xi(x_k,x_i,x_j)=+1\) if and only if \(d_{ki}>d_{kj}\).

On the basis of Lemma 1 and Lemma 2, analogously to Theorem 1, the following is proved.

Theorem 2. The section matrix of the system \(S_n\) with unknown weights of the points uniquely determines the system \(S_n\) and the weights of the points.

Some properties of the order function

In [1] we established the following property of the order function:

A) \(\zeta(x, y, z)\) does not change under a cyclic permutation of the arguments and changes sign to the opposite one when the cyclic order of the arguments is violated.

Let us establish one more property of the order function:

B) for any points \(a, b \in S_n\) there exist two and only two points \(c, d \in S_n\) such that, for all \(x\) not coinciding with \(a, b, c\),

\[ \zeta(a,b,x)=\zeta(a,c,x), \tag{3} \]

or, for all \(x\) not coinciding with \(a, b, c\),

\[ \zeta(a,b,x)=-\zeta(a,c,x) \tag{4} \]

and, for all \(y\) not coinciding with \(a, b, d\),

\[ \zeta(a,b,y)=\zeta(a,d,y), \tag{5} \]

or, for all \(y\) not coinciding with \(a, b, d\),

\[ \zeta(a,b,y)=-\zeta(a,d,y). \tag{6} \]

Definition. If one of the relations (3) or (4) is satisfied, then the pairs of points \((a,b)\) and \((a,c)\) will be called adjacent. Consequently, whatever the pair of points \((a,b)\) may be, there exist two and only two pairs \((a,c)\) and \((a,d)\) adjacent to it.

Proof of property (B).

To prove property (B), normalize the cyclic function by the condition \(N(a,b)=1\).

If \(c\) and \(d\) are such that

\[ |N(a,c)|=2,\quad |N(a,d)|=n-1, \]

then \((a,c)\) and \((a,d)\) are adjacent to \((a,b)\).

Indeed, if \(x\) is distinct from \(a, b, c\), then

\[ |N(a,x)|>|N(a,c)|>|N(a,b)|. \]

Then

\[ \zeta(a,b,x)=Sgn\{N(a,b)N(a,x)[N^2(a,x)-N^2(a,b)]\}= \]

\[ =Sgn\,N(a,x)\,Sgn\,N(a,b). \]

\[ \zeta(a,b,x)=Sgn\,N(a,x)\,Sgn\,N(a,b). \tag{7} \]

Also

\[ \zeta(a,c,x)=Sgn\{N(a,c)N(a,x)[N^2(a,x)-N^2(a,c)]\}= \]

\[ =Sgn\,N(a,x)\,Sgn\,N(a,c). \tag{8} \]

It follows from (7) and (8) that if \(Sgn\,N(a,b)=Sgn\,N(a,c)\), then

\[ \zeta(a,b,x)=\zeta(a,c,x) \]

for all \(x\ne a,b,c\).

In the opposite case,

\[ \zeta(a,b,x)=-\zeta(a,c,x). \]

Consequently, \((a,b)\) and \((a,c)\) are adjacent.

Now let \(y\) be distinct from \(a, b, d\). Then

\[ \zeta(a,d,x)=Sgn\{N(a,d)N(a,x)[N^2(a,x)-N^2(a,d)]\}= \]

\[ =-Sgn\{N(a,x)\cdot N(a,d)\}. \tag{9} \]

Comparing (9) and (7), we see that relation (5) or (6) is satisfied; consequently, \((a,b)\) and \((a,d)\) are adjacent.

We now show that if \(e\ne c,\ e\ne d\), then \((a,e)\) and \((a,b)\) are not adjacent pairs.

Indeed,

\[ 2<|N(a,c)|<n-1. \]

Consider the expression:

\[ \Phi(a,b,c,d,e)=\zeta(a,b,c)\zeta(a,e,c)\zeta(a,b,d)\zeta(a,e,d), \]

\[ \zeta(a,b,c)=\operatorname{Sgn}\{N(a,b)N(a,c)[N^2(a,c)-N^2(a,b)]\}=\operatorname{Sgn}N(a,c), \]

\[ \zeta(a,b,d)=\operatorname{Sgn}\{N(a,b)N(a,d)[N^2(a,d)-N^2(a,b)]\}=\operatorname{Sgn}N(a,d), \]

\[ \zeta(a,e,c)=\operatorname{Sgn}\{N(a,e)N(a,c)[N^2(a,c)-N^2(a,e)]\} =-\operatorname{Sgn}[N(a,c)N(a,e)], \]

\[ \zeta(a,e,d)=\operatorname{Sgn}\{N(a,e)N(a,d)[N^2(a,d)-N^2(a,e)]\} =\operatorname{Sgn}[N(a,e)N(a,d)]. \]

And, consequently, for \(\Phi(a,b,c,d,e)\) we obtain

\[ \Phi(a,b,c,d,e) =-\operatorname{Sgn}\{N(a,c)N(a,d)N(a,c)N(a,e)N(a,e)N(a,d)\}=-1. \]

i.e.

\[ \zeta(a,b,c)\zeta(a,e,c)\zeta(a,b,d)\zeta(a,e,d)=-1, \]

and this, as is easy to see, means that \((a,b)\) and \((a,e)\) are not adjacent.

Thus, property (B) has been proved completely.

Let us note that from the properties of exterior points there also follows:

B. There will be at least three pairs of points \((a_i,b_i)\), \(i=1,2,3\), such that \(\zeta(a_i,b_i,x)=\delta_i\), \(|\delta_i|=+1\), \(x\in S_n\), \(x\ne a_i,b_i\). In an analogous way one may introduce adjacency of the pairs \((a,b)\), \((c,b)\).

Analysis of \(S_5\)

For a system with a small number of points, it is convenient to specify the order function \(\zeta(x,y,z)\) in the form of a table.

For example, when \(n=3\) the table may look as follows:

Table 1

Here, in the \(k\)-th position in the cell standing at the intersection of the \(i\)-th row and the \(j\)-th column, the value \(\zeta(x_i,x_j,x_k)\) is written. The diagonal cells are empty. In the \(i\)-th and \(j\)-th positions in the cell \(ij\) the symbols \(*\) are written, since the value \(\zeta(x_i,x_j,x_i)\) is not defined.

With the help of a table of this kind we investigate systems of five points. We are interested in the number of convex quadruples [2] contained in \(S_5\).

The system \(S_5\) may have 3, 4, or 5 exterior points.

a. Obviously, only convex quadruples enter into \(S_5^5\). Denoting the number of convex quadruples in \(S_n^k\) by \(C(S_n^k)\), we may write \(C(S_5^5)=5\).

b. The case \(S_5^4\). Number the exterior points \(x_1,x_2,x_3,x_4\) in the order of adjacency so that \(R(x_1,x_2)=0\), etc. Then, without violating generality, we can partially fill in the table of the order function as follows:

Table 2

We see that the pairs \((x_2, x_1)\) and \((x_4, x_1)\) are adjacent. By virtue of (B), one of the pairs \((x_3, x_1)\), \((x_5, x_1)\) is adjacent to \((x_2, x_1)\), and the other is not adjacent.

Suppose that \((x_2, x_1)\) and \((x_3, x_1)\) are adjacent. Let us note that this does not diminish generality. Then, since \(\zeta(x_2, x_1, x_4)=\zeta(x_3, x_1, x_4)\) and \(\zeta(x_2, x_1, x_5)=0\), it follows that \(\zeta(x_3, x_1, x_5)=0\).

Entering these data in the table, we obtain:

Table 3

We see that \((x_1, x_2)\) and \((x_3, x_2)\) are adjacent. Consequently, one of the pairs \((x_4, x_2)\) or \((x_5, x_2)\) is adjacent to \((x_1, x_2)\). Let \((x_1, x_2)\) and \((x_5, x_2)\) be adjacent. Then \(\zeta(x_5, x_2, x_4)=1\).

The table of the order function has the form:

Table 4

We see that the quadruples \((x_1, x_2, x_3, x_4)\), \((x_2, x_3, x_4, x_5)\), and \((x_1, x_2, x_3, x_5)\) are convex.

Thus,

\[ C(S_5^4)=3. \]

b. Similarly, we find

\[ C(S_5^3)=1. \]

Thus, the following holds:

Lemma. \(C(S_5)\) is an odd number.

REFERENCES

1. G. G. Pestov. Axiomatization of finite point systems. Izvestiya TPI, vol. 131, 1965.
2. G. G. Pestov. On certain numerical characteristics of point systems. Izvestiya TPI, vol. 131, 1965.