AXIOMATICS OF FINITE POINT SYSTEMS

G. G. PESTOV

(Presented by the Department of Engineering and Computational Mathematics)

In a number of works published in recent years [1], [2], [3], [4], [5], [6], finite sets of points situated in the Euclidean plane are studied. In these works it is assumed that no three points of the given set lie on one straight line. Each straight line passing through two points of such a set effects a division of the set of points into two subsets. At the same time, all results of the cited works that pertain to finite sets in the Euclidean plane can be formulated in terms of divisions of this kind.

It therefore seems reasonable to free ourselves from the assumption that finite sets, or a finite point system, as we shall say following Kárteszi [1], lie in the Euclidean plane. The aim of the present article is to formulate an axiomatics of finite systems, to obtain some consequences of these axioms, and to introduce the simplest concepts.

Wherever possible, we try to retain the terminology and notation used in the already cited works [1], [2], [3], [4], [5], [6], as well as in works adjacent to this direction [7], [8].

Let there be given a certain finite set of points \(a, b, c,\ldots\), which we shall denote by \(S\). Let a function \(N(a,b)\) be given, taking integer values, positive or negative, and satisfying the following conditions:

\[ \text{a)}\quad -n \leq N(a,b) \leq n,\qquad N(a,b)\neq 0; \]

\[ \text{b)}\quad |N(a,b)|\neq |N(a,d)|,\qquad \text{if } b\neq d; \]

\[ \text{c)}\quad \frac{N(a,b)N(a,c)\,[N^2(a,c)-N^2(a,b)]} {N(b,a)N(b,c)\,[N^2(b,c)-N^2(b,a)]}<0; \]

d) in every subset \(S'\subset S\) there can be found points \(a\) and \(b\) such that for all \(c\in S'\)

\[ N(a,c)N(a,b)\,[N^2(a,c)-N^2(a,b)]>0. \]

Definition. A finite set of points for which a binary cyclic function \(N(a,b)\) is specified is called a finite point system.

Let us define an order function, taking two values \(+1\) and \(-1\), and specified for each triple of points from \(S\):

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

If \(\zeta(a,b,c)=+1\), we shall say that the point \(c\) lies to the left of the straight line \((a,b)\).

The set of points lying to the left of \((a,b)\) will be denoted by \(L(a,b)\). The set of points lying to the right of \((a,b)\) will be denoted by \(R(a,b)\).

Triangle lemma

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

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

These equalities follow from axiom (c).

Thus, the value of the order function for each triple of points is preserved under a cyclic permutation of the points.

Sometimes it is convenient to replace the function \(N(x,y)\) by another \(N_1(x,y)\) in such a way that the order function is not changed and, for the given pair \((a,b)\), \(N(a,b)=1\).

Definition. We shall say that the functions \(N(x,y)\) and \(N_1(x,y)\) are equivalent if the order functions generated by them coincide.

Theorem. Let \(N(x,y)\) be a double cyclic function. Define the function \(N_1(x,y)\) by

\[ N_1(x,y)=N(x,y),\qquad x\ne a, \]

\[ N_1(a,y)=\{Res[|N(a,y)|-|N(a,b)|+n+1]\;(\operatorname{mod} n)\}\,\zeta(a,b,y). \]

Then \(N_1(x,y)\) is a double cyclic function equivalent to \(N(x,y)\), and \(N_1(a,b)=1\); by \(Res\,m\,(\operatorname{mod} n)\) we denote the least strictly positive residue of the number \(m\) modulo \(n\).

Proof. It is required to prove that

\[ \zeta(x,y,z)=\zeta_1(x,y,z). \tag{1} \]

If \(x\ne a\), then (1) follows from the definition of \(N_1(x,y)\). If \(x=a\), then

\[ \zeta_1(a,y,z)=Sgn\{N_1(a,y)N_1(a,z)[N_1^2(a,z)-N_1^2(a,y)]\}= \]

\[ =\zeta(a,b,y)\zeta(a,b,z)\cdot Sgn\{N_1^2(a,z)-N_1^2(a,y)\}. \]

Next we consider three cases:

\[ 1)\ |N(a,z)|>|N(a,b)| \quad \text{and} \quad |N(a,y)|>|N(a,b)|. \]

\[ \zeta_1(a,y,z)=Sgn\{N_1(a,y)N_1(a,z)[N_1^2(a,z)-N_1^2(a,y)]\}= \]

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

\[ -N_1^2(a,b)\}\zeta(a,b,z)\cdot Sgn\{N_1^2(a,z)-N_1^2(a,y)\}= \]

\[ =\zeta(a,b,y)\zeta(a,b,z)\cdot Sgn\{N_1^2(a,z)-N_1^2(a,y)\}= \]

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

\[ =Sgn\{N(a,b)N(a,y)\cdot [N^2(a,y)-N^2(a,b)]\,N(a,b)N(a,z)\times \]

\[ \times [N^2(a,z)-N^2(a,b)] [N^2(a,z)-N^2(a,y)]\}= \]

\[ =Sgn\{N(a,y)N(a,z)[N^2(a,z)-(N^2(a,y)]\}= \]

\[ =\zeta(a,y,z); \]

\[ 2)\quad |N(a,z)|<|N(a,b)|,\qquad |N(a,y)|<|N(a,b)|. \]

\[ \zeta_1(a,y,z)=Sgn\{N(a,y)N(a,b)[N^2(a,y)-N^2(a,b)]\}\cdot \]

\[ \cdot N(a,z)N(a,b)[N^2(a,z)-N^2(a,b)]\cdot [n+|N(a,z)|- \]

\[ -|N(a,b)|-n-|N(a,y)|+|N(a,b)|]\}= \]

\[ =Sgn\{N(a,y)N(a,z)[N^2(a,z)- \]

\[ -N^2(a,y)]\}=\zeta(a,y,z); \]

3)
\[ |N(a,z)|>|N(a,b)|,\qquad |N(a,y)|<|N(a,b)|. \]
\[ \begin{aligned} \zeta(a,y,z)&=\operatorname{Sgn}\{N(a,y)N(a,b)[N^2(a,y)-N^2(a,b)]\\ &\quad \cdot N(a,z)N(a,b)\cdot [N^2(a,z)-N^2(a,b)]\cdot [|N(a,z)|\\ &\quad -|N(a,b)|-n-|N(a,y)|+|N(a,b)|]\}\\ &=\operatorname{Sgn}\{-N(a,y)N(a,z)[|N(a,z)|-|N(a,y)|-n]\}\\ &=\operatorname{Sgn}\{N(a,y)N(a,z)[N^2(a,z)-N^2(a,y)]\}=\zeta(a,y,z). \end{aligned} \]

Remark. Analogously one can construct a dual cyclic function \(N_1(x,y)\) satisfying the condition \(N_1(a,b)=k\).

Lemma 1. Every subsystem is a system; in other words, if a system \(S\) is given and \(S'\) is a subset of \(S\), then \(N'(a,b)\) can be defined so that \(\zeta(a,b,c)=\zeta'(a,b,c)\) for every triple of points \(a,b,c\in S'\).

Proof. Indeed, on \(S'\) one can prescribe a dual cyclic function satisfying conditions a), b), c):
\[ N'(a,b)=\left\{1+\sum_{\substack{c\ne b\\ c\ne a}}\frac{1}{2}\{ \operatorname{Sgn}[N^2(a,b)-N^2(a,c)]+1\}\right\}\cdot \operatorname{Sgn}N(a,b). \]
We shall show that
\[ \zeta(a,b,c)=\zeta'(a,b,c). \]
\[ \zeta'(a,b,c)=\operatorname{Sgn}\{N'(a,b)N'(a,c)[N'^2(a,c)-N'^2(a,b)]\}= \]
\[ =\operatorname{Sgn}\left\{N(a,b)N(a,c)\left[1+\sum_x \frac{1}{2}\,[1+\operatorname{Sgn}[N^2(a,c)\right.\right. \]
\[ \left.\left.-N^2(a,x)]]-1-\sum \frac{1}{2}\,[\operatorname{Sgn}[N^2(a,b)-N^2(a,y)]+1]\right]\right\}= \]
\[ =\operatorname{Sgn}\{N(a,b)N(a,c)[|N(a,c)|-|N(a,b)|]\}=\zeta(a,b,c). \]

Definition. A point \(a\) is called an exterior point with respect to \(S\) if \(a\in S'\), where \(S\) is a subsystem of \(S'\), and there exists a point \(b\in S\) such that \(R(a,b)=\overline{0}\).

If \(a\in S\) and \(a\) is exterior with respect to \(S\), then we shall say that \(a\) is an exterior point of \(S\). We shall call \(a,b\) adjacent exterior points if \(L(a,b)=\overline{0}\) or \(R(a,b)=\overline{0}\).

Lemma 2. There exist at least three exterior points in \(S\).

Proof. By property (c) there exists at least one point \(a\) such that \(R(a,b)=\overline{0}\). We shall show that \(b\) is also exterior. For this purpose introduce a dual cyclic function by the condition \(N'(b,a)=n\). Then \(N(b,c)>0,\ c\in S\).

Indeed,
\[ \zeta(a,b,c)=+1, \]
therefore
\[ \zeta(b,a,c)=-1, \]
\[ \zeta(b,a,c)=\operatorname{Sgn}\{N(b,a)N(b,c)[N^2(b,c)-N^2(b,a)]\}<0. \]
Hence \(N(b,c)>0\).

Consequently, \(N(b,c)\) takes the values \(1,2,\ldots,n\).

Let \(d\) be such that \(N(b,d)=1\) (therefore, \(d\ne a\)).

Then
\[ \zeta(b,d,c)=\operatorname{Sgn}\{N(b,d)N(b,c)[N^2(b,c)-N^2(b,d)]\}=+1. \]

Consequently, \(R(b,d)=\overline{0}\), hence \(b\) is exterior; it likewise follows that \(d\) is exterior, as was required to prove.

Carathéodory’s Lemma. If \(d\in S\) is not an exterior point of the system \(S\), then there exists a \(\Delta abc\) containing \(d;\ a,b,c\in S\).

Here we say that \(\Delta a_1a_2a_3\) contains \(d\) if there exists a cyclic order \(a_{i_1}a_{i_2}a_{i_3}\) such that

\[ d\in \{L(a_1,a_2)\cap L(a_2,a_3)\cap L(a_3,a_1)\}. \]

Proof.
\(d\) is not an exterior point. If \(A\) is a point set, then by \(A\) we shall denote the number of elements of \(A\).

Let

\[ \alpha=\min_{b\in S}\{L(d,b),\ R(d,b)\}. \]

Let \(L(a,b)=\alpha\); consequently,

\[ \overline{L(d,b)}\ll \overline{L(d,c)} \quad\text{and}\quad \overline{L(d,b)}\ll \overline{R(d,c)}. \]

Let \(a\) be such that \(a\in L(a,b)\).

Make a cyclic numbering, taking \(N(d,b)=1\). Then the least positive value not equal to one is

\[ N(d,c)\geq 3. \]

Indeed, if there were a point \(f\) such that \(N(d,f)=2\), then

\[ L(d,f)=\{e:N(d,e)N(d,f)[N^2(d,e)-N^2(d,f)]>0\}= \]

\[ =\{e:N(d,e)[N^2(d,e)-2^2]>0\}=L(d,b)/b, \]

therefore,

\[ \overline{L(d,f)}=\overline{L(d,b)}-1=\alpha-1, \]

which is impossible.

Thus the least of the positive values greater than one is

\[ N(d,e)\geq 3. \]

Consequently, there exists a point \(g\) such that \(N(d,g)=-2\). The triangle \(\Delta agb\) is the desired one.

Indeed,

\[ \zeta(g,b,d)=\zeta(d,g,b)= \]

\[ =Sgn\{N(d,b)N(d,g)[N^2(d,b)-N^2(d,g)]\}=+1, \]

\[ \zeta(g,b,d)=+1. \]

Further,

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

\[ -N^2(d,a)]\}=Sgn\{(1-2)N(d,a)[4-N^2(d,a)]\}=+1. \]

Thus,

\[ \zeta(a,g,d)=+1. \]

Finally,

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

Thus,

\[ \zeta(a,d,b)=+1. \]

The equalities (2), (3), (4) mean that \(d\in \Delta abg\).

Lemma on an exterior point. If \(a,b,c\in S\) and \(L(a,b)=c\), then \(c\) is an exterior point of the system \(S\).

Proof.
1. One of the equalities holds:

\[ L(a,c)=\overline{0}\quad \text{or}\quad L(c,b)=\overline{0}. \]

Then, by definition, \(c\) is an exterior point.

\[ \text{2. } L(a,c)\ne 0,\quad L(c,b)\ne \overline{0}. \]

Take \(d\in L(a,c)\) and \(e\in L(c,b)\).

We shall denote by \(S_n\) a system consisting of \(n\) points. Consider \(S_5\), consisting of the points \(a,b,c,d,e\). Then \(a\) cannot be an exterior point in \(S_5\).

Indeed, every exterior point has two adjacent exterior points; meanwhile \(\zeta(a,c,d)=+1\), \(\zeta(a,c,b)=-1\), hence \(a\) and \(c\) are not adjacent; \(\zeta(d,a,b)=-1\), \(\zeta(d,a,c)=+1\), hence \(a\) and \(d\) are not adjacent; \(\zeta(a,b,c)=+1\), \(\zeta(a,b,d)=-1\), hence \(a\) and \(b\) are not adjacent.

Thus the point \(a\) cannot have two adjacent points, and therefore is not an exterior point. The same applies to the point \(b\). Consequently, the exterior points will be \(c,d,e\). In this case \(d\in R(d,c)\); hence \(d,b,e\in R(d,c)\).
\[ \tag{5} \]

Further, \(d\in R(c,b)\); hence \(a,d\in R(c,b)\).

Let us now return to the system \(S\).

Introduce a double cyclic function by the condition: \(N(c,b)=1\). Then for \(d\in R(c,b)\), \(N(c,d)<0\); for any \(l\) from \(L(c,b)\), \(N(c,l)>0\).

Note that for \(d\in L(a,c)\), \(|N(c,d)|<|N(c,a)|\).

Indeed,
\[ \zeta(c,a,d)=-1, \]
\[ \zeta(c,a,d)=Sgn[\,|N(c,d)|-|N(c,a)|\,]. \]

Thus, \(|N(c,d)|<|N(c,a)|\).

Similarly, if \(f\in R(c,b)\cap L(c,a)\), then
\[ |N(c,f)|>|N(c,a)|>|N(c,d)|. \]

Let \(d_1\) be such that
\[ |N(c,d_1)|=\min_{x\in R(c,b)} |N(c,x)|. \]

Then \(d_1\in R(c,a)\).

Further, \(R(c,d_1)=\overline{0}\). Indeed, if \(x\in R(c,b)\), then
\[ \zeta(c,x,d)=Sgn\{(|N(c,d)|-|N(c,x)|\}=-1,\quad x\in R(c,d). \]

If \(x\in L(c,b)\), then \(x\in L(c,d)\) by virtue of (5). Consequently, \(R(c,d)=\overline{0}\), as was required to prove.

REFERENCES

1. Kartesci Franz. Extremalaufgaben über endliche Punktsysteme, Publs. mat., 4, No. 1—2, 16—27, 1955.

2. B. J. Birch. On 3N points in a plane, Proc. Cambridge Philos. Soc., 55, No. 4, 289—293, 1959.

3. I. M. Yaglom, V. G. Boltyanskii. Convex Figures, 1951.

4. Sedlacek. A note on a convex polygon. Časop. pěstov. mat. 82, No. 3, 1957.

5. Sedlacek. On systems of diagonals in a convex polygon. Časop pěstov. mat. 81, No. 2, 1956.

6. Václav Polák. On the existence of certain systems of diagonals of a convex polygon. Časop. pěstov. mat., 85, No. 1, 70—74, 1960.

7. Joussen Jakob. Ordnungsfunktionen in freien Ebenen, Abhandl. Math. seminar Univ. Hamburg., 24, 239—263, 1960.

8. Glock Erich. Ordnungsfunktionen, die af Seiteneinteilungen besonderer Art führen, Arch. Math., 12, No. 1, 71—77, 1961.