SOME EXTREMAL PROBLEMS IN THE THEORY OF POINT SYSTEMS

G. G. PESTOV

(Presented by the Department of Engineering and Computational Mathematics)

The aim of the present article is to estimate the order of covering of a point in a point system as a function of the depth of the point. From these estimates, as one of the consequences, follow results obtained by Kárteszi [1].

Let \(S_{n+1}\) be a point system, \(q \in S_{n+1}\). Denote by \(S_n\) the system \(S_{n+1}\) without \(q\).

Definition. If \(q\) lies inside exactly \(T\) triangles with vertices belonging to \(S_n\), then one says that \(q\) is covered \(T\) times.

\(T\) is the order of covering of \(q\) in the system \(S_n\).

We shall denote the order of covering of the point \(q\) by \(T(q)\).

Statement of the problem: given the depth \(d(q)\) [3] of the point \(q\) in the system \(S_n\).

Find estimates for \(T(q)\).

Denote \(d(q)=d\). Let \(\overline{R(q,\pi_1)}=d\).

Introduce the double cyclic function [4] by the condition \(N(q,\pi_1)=1\).

Number the points belonging to \(R(q,\pi_1)\).

To the point \(\mu \in R(q,\pi_1)\) assign the number

\[ i(\mu)=\overline{R(q,\pi_1)\cap R(q,\mu)}+1. \]

The point with number \(i\) will be denoted by \(\mu_i,\ i=1,2,\ldots,d\).

Number the points belonging to \(L(q,\pi_1)\), including also \(\pi_1\). To the point \(\pi \in L(q,\pi_1)\) assign the number

\[ K(\pi)=\overline{R(q,\pi)\cap L(q,\pi_1)}+2,\quad K(\pi_1)=1. \]

The point \(\pi\) with number \(K\) is denoted by \(\pi_K,\ K=1,2,\ldots,p=n-d\).

Denote

\[ \alpha_i=\overline{L(q,\mu_i)\cap L(q,\pi_1)}+1. \]

Then from the definition of depth [3] it follows that

\[ \begin{cases} i \leq \alpha_i \leq p-d+i-1,\\ \alpha_i \leq \alpha_j,\quad i,j=1,2,\ldots,d,\quad i\leq j, \end{cases} \tag{1} \]

where \(p=n-d\). Then the number of covering triangles with one vertex in \(L(q,\pi_1)\cup \pi_1\) and two vertices in \(R(q,\pi_1)\) is

\[ T_1=\sum_{i<j}(\alpha_j-\alpha_i). \]

The number of triangles with one vertex in \(R(q,\pi_1)\) and two vertices in \(L(q,\pi_1)\cup \pi_1\) is

\[ \sum_{i=1}^{d}\alpha_i(p-\alpha_i)=T_2, \]

Since a covering triangle cannot have all three vertices in \(R(q,\pi_1)\) or in \(L(q,\pi_1)\cup \pi_1\), the total number of covering triangles is

\[ T=T_1+T_2=\sum_{i<j}(\alpha_j-\alpha_i)+\sum_{i=1}^{d}\alpha_i(p-\alpha_i). \tag{2} \]

Thus, it is required to find the maximum and minimum of expression (2), if \(\alpha_i\) satisfies the conditions (1).

Differentiate with respect to \(\alpha_i\).

\[ T'_{\alpha_i}=p-2\alpha_i-1-d+2i,\quad i=1,2,\ldots,d. \]

Equating to zero,

\[ T'_{\alpha_i}=0;\quad \alpha_i=\frac{p-d-1}{2}+i. \tag{3} \]

Consider the difference

\[ \begin{aligned} \Delta T&=T(\alpha_1+\Delta\alpha_1,\ldots,\alpha_d+\Delta\alpha_d)-T(\alpha_1,\ldots,\alpha_d)=\\ &=\sum_{i=1}^{d}\Delta\alpha_i(p+2i-d-1-2\alpha_i-\Delta\alpha_i). \end{aligned} \]

Thus, under deviation from the extremal values determined by formula (3),

\[ \Delta T=-\sum_{i=1}^{d}(\Delta\alpha_i)^2. \]

Thus, under deviation from the extremal values of the arguments \(\alpha_1,\ldots,\alpha_d\), determined by (3), the value of \(T\) decreases monotonically in each argument. Therefore the integer values nearest to the values determined by (3) will give the maximum of the function \(T(\alpha_1,\ldots,\alpha_d)\), while the values farthest from (3) and satisfying the inequalities (1) will give the minimum.

The greatest deviations from (3) are given by the set of values \(\alpha_i=i\). Therefore

\[ \begin{aligned} \tau(d)=\min T &=\sum_{i=1}^{d} i(p-i)+\sum_{i<j}(j-i)=\\ &=\sum_{i=1}^{d}\left[i^2+(p-d-1)i\right] =\frac{d(d+1)(2d+1)}{6}+(p-d-1)\frac{d+1}{2}d=\\ &=\frac{d(d+1)(3n-4d-2)}{6}. \end{aligned} \]

Thus,

\[ \tau(d)=\min T(q)=\frac{d(d+1)(3n-4d-2)}{6}, \tag{4} \]

where \(d=d(q)\).

Let us now find \(\max T(q)\).

a. \(n\) is even. Then the \(\alpha_i\) from formula (3) are not integers. Put \(\alpha'_i=\alpha_i+\dfrac{1}{2}\). Then \(\Delta\alpha_i=\dfrac{1}{2}\). Use the already found value \(\min T(q)\).

\[ \begin{aligned} \max T(q) &=\min T(q)+\left(\frac{p-d-1}{2}\right)^2\cdot d-\frac{1}{4}\cdot d=\\ &=d\cdot \frac{4d^2-6nd+3n^2-4}{12}. \end{aligned} \]

Thus, for even \(n\),

\[ \Theta(d)=\max T(q)=\frac{4d^{2}-6nd+3n^{2}-4}{12}\cdot d. \]

1. Similarly, for odd \(n\) we obtain

\[ \Theta(d)=d\,\frac{4d^{2}-6nd+3n^{2}-1}{12}. \tag{6} \]

Formulas (4), (5), and (6) completely solve the problem posed.

We shall now obtain, as a consequence of (5), (6), the result of Kertész.

Introduce the quantities

\[ K(S_n)=\max_{S_{n+1}}\max_{q\in S_{n+1}}T(q), \]

\[ S_{n+1}\supset S_n, \]

\[ W(n)=\max_{S_n}K(S_n), \]

\[ V(n)=\min_{S_n}K(S_n). \]

To find \(W(n)\), note that

\[ W(n)=\max_d \Theta(d). \]

a) \(n\) is odd

\[ \Theta'(d)=0,\quad d=\frac{6n\pm\sqrt{12}}{12}=\frac n2\pm\frac{1}{\sqrt{12}}, \]

\[ d=\frac n2-\frac{1}{\sqrt{12}}. \]

Since the value of \(d\) is an integer and \(d\le \left[\frac n2\right]\), we have

\[ W(n)=\Theta\left(\left[\frac n2\right]\right)=\frac{n(n^2-1)}{24}. \]

b) \(n\) is even.

\[ \Theta'(d)=0,\quad d=\frac n2\pm\sqrt{\frac13}. \]

Since \(d\le \frac n2-1\), we have

\[ W(n)=\frac{n(n^2-4)}{24}. \]

Thus,

\[ W(n)= \begin{cases} \dfrac{n(n^2-1)}{24}, & n\text{ is odd},\\[6pt] \dfrac{n(n^2-4)}{24}, & n\text{ is even}. \end{cases} \tag{7} \]

Formulas (7) were obtained by Kertész [1].

Since \(d(S_n)\ge \left[\frac n3\right]\), [2], it follows that

\[ \tau\left(\left[\frac n3\right]\right)\le V(n)\le \Theta\left(\left[\frac n3\right]\right), \]

where \(\tau\) and \(\Theta\) are found from formulas (4), (5), (6). Hence it follows that

\[ W(n)>V(n)\quad \text{for } n\ge 7. \]

References

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

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

3. G. G. Pestov. On the depth of a point in a point system. Izvestiya TPI, vol. 131, 1965.

4. G. G. Pestov. Axiomatization of finite point systems. Izvestiya TPI, vol. 131, 1965.