ON SOME NUMERICAL CHARACTERISTICS OF POINT SYSTEMS

G. G. PESTOV

(Submitted by the Department of Engineering-Computational Mathematics)

In the present article a definition is introduced of the filling coefficient of a point system; the number of convex and nonconvex quadruples in a point system is studied. Apparently, the results set forth in the present article, unless otherwise stated, are new.

On the number of nonconvex quadruples

We shall consider all possible quadruples \((a, b, c, d)\) of points of a system \(S_n\). We shall call a quadruple \((a, b, c, d)\) convex if the subsystem \(S_4\) of the system \(S_n\), consisting of the points \(a, b, c, d\), has no interior points. Otherwise we shall call the quadruple \((a, b, c, d)\) nonconvex.

Denote the number of nonconvex quadruples in the point system \(S_n\) by \(I(S_n)\), and the number of convex quadruples by \(C(S_n)\).

A system consisting of \(n\) points will be denoted by \(S_n\).

In [2] it is proved:

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

The following holds:

Theorem 1. If \(n\) is odd, then \(C(S_n)\) has the same parity as \(C_n^5\).

Proof. Let \(S_5 \subset S_n\). Consider

\[ \sum_{S_5 \subset S_n} C(S_5). \]

Each convex quadruple contained in \(S_n\) is counted in expression (1) exactly \(n - 4\) times. Therefore

\[ \sum_{S_5 \subset S_n} C(S_5) = (n - 4) C(S_n). \]

By assumption, \(n - 4\) is odd. Hence

\[ \sum_{S_5 \subset S_n} C(S_5) \equiv C(S_n) \pmod 2. \tag{2} \]

Since, by Lemma 1, each of the numbers \(C(S_5)\) is odd, we have

\[ \sum_{S_5 \subset S_n} C(S_5) \equiv C_n^5 \pmod 2. \tag{3} \]

Comparing (2) and (3), we finally obtain

\[ C(S_n) \equiv C_n^5 \pmod 2. \]

We shall denote a system consisting of \(n\) points with \(\kappa\) outer points by \(S_n^\kappa\).

Theorem 2. For any system \(S_n^\kappa\), \(\kappa > 3\), there exists a system \(S_n^{\kappa-1}\) such that

\[ I(S_n^\kappa) < I(S_n^{\kappa-1}). \]

Proof. Put \(n-\kappa=\lambda\). Denote the subsystem consisting of the outer points by \(S_\kappa\), and the subsystem of the inner points by \(S_\lambda\). Let us count the number of those nonconvex quadruples of \(S_n^\kappa\) each of which contains at least one pair of adjacent outer points from \(S_\lambda\) [1]. In doing so, each nonconvex quadruple is counted as many times as the number of pairs of adjacent outer points in \(S_n^\kappa\) that are contained in this quadruple. Each quadruple of interest to us contains either two points from \(S_\kappa\) and two points from \(S_\lambda\), or three points from \(S_\kappa\) and one point from \(S_\lambda\).

1. Let us count the number of nonconvex quadruples in which one point belongs to \(S_\lambda\) and three points belong to \(S_\kappa\). Let \(a \in S_\lambda\), \(b \in S_\kappa\). Consider the system \(S_{\kappa+1}\) obtained by adding the point \(a\) to \(S_\kappa\). Introduce in the system \(S_{\kappa+1}\) a double cyclic function by the condition

\[ N(a,b)=1. \]

Let the point \(c\) be such that, for any \(x\) for which \(N(a,x)>0\), we have \(N(a,c)>N(a,x)\); let \(d\) be such that, for all \(y\) for which \(N(a,y)<0\), one has \(|N(a,d)|<|N(a,y)|\) and \(N(a,d)<0\). Then, as is easy to see, the quadruple \((a,b,c,d)\) is nonconvex, and the points \(c\) and \(d\) are adjacent outer points in the system \(S_n\).

Thus, for the pair of points \(a \in S_\lambda\) and \(b \in S_\kappa\), a nonconvex quadruple has been found with a pair of adjacent points \(c,d \in S_\kappa\).

Consequently, the quantity \(\kappa\lambda\) is equal to the number of nonconvex quadruples with one point from \(S_\lambda\) and, at least, with one pair of adjacent points from \(S_\kappa\); each quadruple has been counted as many times as the number of pairs of adjacent points from \(S_\kappa\) contained in that quadruple.

1. Let us find the number of nonconvex quadruples with two points \(a \in S\), \(b \in S_\lambda\) and with two adjacent points in \(S_\kappa\).

Consider the system consisting of the points \(S_\kappa\) with \(a\) and \(b\) added. As before, the number of nonconvex quadruples containing the points \(a,b\) and two more adjacent points from \(S_\kappa\) is equal to two.

Therefore the total number of nonconvex quadruples with two points from \(S_\lambda\) and two adjacent points from \(S_\kappa\) is \(2C_\lambda^2\).

1. Consequently, the total number of nonconvex quadruples, each of which is counted as many times as it contains pairs of adjacent points from \(S_\kappa\), is equal to

\[ \kappa\lambda + 2C_\lambda^2 = \kappa\lambda + \lambda^2 - \lambda. \]

Since the number of pairs of adjacent points from \(S_\kappa\) is equal to \(\kappa\), there will be a pair of adjacent points \(a,b \in S_\kappa\) such that the number of nonconvex quadruples involving \(a,b\) does not exceed

\[ \frac{\kappa\lambda+\lambda^2-\lambda}{\kappa} = \lambda+\frac{\lambda^2-\lambda}{\kappa}. \tag{4} \]

1. Denote by \(I_0(S_n^\kappa)\) the number of nonconvex quadruples of \(S_n^\kappa\) without the participation of the points \(a\) and \(b\); similarly, \(I_a(S_n^\kappa)\) is the number of all nonconvex

quadruples involving \(a\), but not \(b\); similarly, \(I_b(S_n^k)\) is the number of nonconvex quadruples involving \(b\), but not \(a\); by \(I_{ab}(S_n^k)\) we denote the number of nonconvex quadruples involving \(a\) and \(b\).

Expressing \(\lambda\) in (4) in terms of \(n\) and \(k\), we obtain

\[ I_{ab}(S_n^k) \le (n-1)\left(\frac{n}{k}-1\right). \tag{5} \]

Let, for definiteness,

\[ I_a(S_n^k)\ge I_b(S_n^k). \]

Let \(c\) and \(d\) be such that

\[ R(a,c)=\left[\frac{n-2}{2}\right]\quad \text{and}\quad L(a,d)=\left[\frac{n-1}{2}\right]. \]

Let \(S_{n-1}\) be the system \(S_n\) without \(b\); its double cyclic function \(N_0(x,y)\) is defined by the conditions

\[ N_0(a,d)=1, \]

\[ N_0(x,a)= \begin{cases} n-2, & \text{if } x\in L(a,c),\\ 1, & \text{if } x\in R(b,d). \end{cases} \]

Now consider the system \(S_n^{k-1}\), consisting of the same points as \(S_n^k\), with the double cyclic function \(N_1(x,y)\) defined as follows:

\[ N_1(x,y)= \begin{cases} N_0(a,y), & y\ne b,\quad x=a,\\ -n+1, & y=b,\quad x=a,\\ N_0(x,y), & y\ne b,\quad x\in L(a,d),\\ n-1, & y=b,\quad x\in L(a,d),\\ N_0(x,y), & y\ne b,\quad x\in R(a,c),\\ -n+1, & y=b,\quad x\in R(a,c),\\ N_0(a,y), & y\ne a,\quad x=b,\\ n-1, & y=a,\quad x=b. \end{cases} \]

The following relations hold:

\[ I_a(S_n^{k-1})=I_a(S_n^k); \]

\[ I_b(S_n^{k-1})=I_a(S_n^k), \]

that is,

\[ I_b(S_n^{k-1})\ge I_b(S_n^k) \]

\[ I_0(S_n^{k-1})=I_0(S_n^k). \]

Let us now find \(I_{ab}(S_n^{k-1})\). We shall denote sections in \(S_n^{k-1}\) by \(L'(x,y)\), \(R'(x,y)\).

It is easy to see that if \(x\in L'(a,b)\), \(y\in R'(a,b)\), then the quadruple \((a,b,x,y)\) is nonconvex. Hence

\[ I_{ab}(S_n^{k-1})\ge \left(\frac{n-2}{2}\right)^2-\frac14 \]

or

\[ I_{ab}(S_n^{k-1})\ge (n-1)\left(\frac{n+1}{4}-1\right). \tag{6} \]

If $\kappa>3$, then from (5) and (6) it follows that

\[ I_{ab}(S_n^\kappa)<I_{ab}(S_n^{\kappa-1}). \]

Finally,

\[ I(S_n^\kappa)=I_0(S_n^\kappa)+I_a(S_n^\kappa)+I_b(S_n^\kappa)+I_{ab}(S_n^\kappa)< \]

\[ <I_0(S_n^{\kappa-1})+I_a(S_n^{\kappa-1})+I_b(S_n^{\kappa-1})+I_{ab}(S_n^{\kappa-1}) =I(S_n^{\kappa-1}). \]

Thus, we have constructed such a system $S_n^{\kappa-1}$ that $I(S_n^\kappa)<I(S_n^{\kappa-1})$, as was required to prove.

Filling of a point system

Definition. The quantity

\[ P(S_n)=\frac{I(S_n)}{C_n^4} \]

will be called the filling of the point system $S_n$. $P(S_4)$ takes two values: $0$ and $1$. $P(S_5)$ takes three values: $0$, $2/5$, $4/5$.

Denote

\[ \alpha_n=\max_{S_n} P(S_n). \]

A system for which $P(S_n)=\alpha_n$ will be called a filled system.

Theorem 3. If $S_n$ is filled, then it has three outer points.

Proof follows from Theorem 2 of the present article.

Theorem 4. The numbers $\alpha_1,\alpha_2,\ldots,\alpha_n,\ldots$ form a nonincreasing sequence.

Proof. Let $n>\kappa$. Consider any system $S_n$. We shall show that

\[ P(S_n)\leq \alpha_\kappa. \]

Consider a subsystem $S_\kappa\subset S_n$. By virtue of (7), $P(S_\kappa)\leq \alpha_\kappa$. Therefore
\[ I(S_\kappa)\leq \alpha_\kappa C_\kappa^4. \tag{8} \]

Further,

\[ C_{n-4}^{\kappa-4} I(S_n)=\sum_{S_\kappa\subset S_n} I(S_\kappa). \tag{9} \]

But by virtue of (8),

\[ \sum_{S_\kappa\subset S_n} I(S_\kappa)\leq \alpha_\kappa C_\kappa^4 C_n^\kappa. \tag{10} \]

From (9) and (10) it follows that

\[ I(S_n)\leq \alpha_\kappa \frac{C_\kappa^4 C_n^\kappa}{C_{n-4}^{\kappa-4}}, \]

that is, $I(S_n)\leq \alpha_\kappa C_n^4$, whence $\alpha_n\leq \alpha_\kappa$, as was required to prove. In conclusion, note that, since the sequence $\{\alpha_n\}$ is nonincreasing and $\alpha_n\geq 0$, there exists

\[ \alpha=\lim_{n\to\infty}\alpha_n. \]

It can be shown that

\[ \alpha\geq \frac{8}{13}. \]

LITERATURE

1. G. G. Pestov. Axiomatics of finite point systems. Izvestiya TPI, vol. 131, 1965.
2. G. G. Pestov. Methods of specifying point systems. Izvestiya TPI, vol. 131, 1965.