UDC 517.51

MATHEMATICS

B. L. FRIDMAN

IMPROVING THE SMOOTHNESS OF FUNCTIONS IN A. N. KOLMOGOROV’S THEOREM ON SUPERPOSITIONS

(Presented by Academician A. N. Kolmogorov on 20 II 1967)

By A. N. Kolmogorov’s theorem \((^1)\), every continuous function of \(n\) variables can be represented in the form

\[ f(x_1,x_2,\ldots,x_n)=\sum_{i=1}^{2n+1}\chi_i\left(\sum_{j=1}^{n}\varphi_{i,j}(x_j)\right), \tag{A} \]

where all the functions are continuous, and the \(\varphi_{i,j}(x_j)\) are fixed and do not depend on the function being decomposed \(f(x_1,x_2,\ldots,x_n)\). G. M. Henkin showed that the \(\varphi_{i,j}(x_j)\) can be chosen to satisfy a Hölder condition with any exponent \(0<\alpha<1\). A. G. Vitushkin and G. M. Henkin proved that if continuously differentiable functions are fixed as the \(\varphi_{i,j}(x_j)\), then the set of superpositions of the form (A) is nowhere dense in the space of all continuous functions \((^2,^3)\). Here we shall show that the inner functions in A. N. Kolmogorov’s construction can be chosen to satisfy a Lipschitz condition. The precise formulation of the result is as follows.

Theorem. Every function continuous on the cube \(0\le x_j\le 1\) \((j=1,2,\ldots,n)\) can be represented in the form

\[ f(x_1,x_2,\ldots,x_n)=\sum_{i=1}^{2n+1}\chi_i\left(\sum_{j=1}^{n}\varphi_{i,j}(x_j)\right), \]

where \(\chi_i(x)\) are continuous functions, and \(\varphi_{i,j}(x_j)\) are preassigned fixed functions, independent of the function \(f(x_1,x_2,\ldots,x_n)\), and satisfying a Lipschitz condition.

For simplicity of exposition we shall give the proof for \(n=2\). The proof will use the following lemma, whose proof may be found in \((^1)\).

Lemma 1. (A. N. Kolmogorov). Let \(P^k_{\alpha,j}\) \((k=1,2,\ldots,5;\ \alpha=1,2,\ldots,\alpha_{j,k};\ j=1,2,\ldots)\) be closed rectangles in the square \(I_2(0\le x\le 1,\ 0\le y\le 1)\), satisfying the following conditions:

1. For all \(k\) and \(j\), if \(\alpha_1\ne\alpha_2\), then
   \[ P^k_{\alpha_1,j}\cap P^k_{\alpha_2,j}=\varnothing. \]

2. The diameter of the rectangle \(P^k_{\alpha,j}\) tends to zero as the index \(j\) increases.

3. For every fixed \(j\), every point of the square \(I_2\) belongs to at least three rectangles from the system \(\{P^k_{\alpha,j}\}\) with one and the same fixed index \(j\).

Suppose, further, that continuous functions \(\Phi_k(x,y)\) are given such that, for all \(k\) and \(j\), the sets \(\{\Phi_k(P^k_{\alpha,j})\}\) \((\alpha=1,2,\ldots,\alpha_{j,k})\) are pairwise disjoint.

Then, for every continuous function \(f(x,y)\) on \(I_2\), one can specify continuous functions \(\chi_k(x)\) such that

\[ f(x,y)=\sum_{k=1}^{5}\chi_k(\Phi_k(x,y)). \]

For the proof of the theorem it suffices to construct a system of rectangles \(P_{\alpha,j}^{k}\) and functions \(\Phi_k(x,y)=\varphi_k(x)+\psi_k(y)\) satisfying the Lipschitz conditions and Lemma 1.

Construction of the systems of rectangles. On the segment \(I_1\) \((0\leq x\leq 1)\) we construct a system \(\{S_{i,j}^{k}\}\) of intervals \(S_{i,j}^{k}\) \((k=1,2,\ldots,5;\ i=1,2,\ldots,i_{j,k};\ j=1,2,\ldots)\) of length \(\Delta_{i,j}^{k}\), possessing the following properties:

a) for any \(k\) and \(j\), if \(i_1\neq i_2\), then \(S_{i_1,j}^{k}\cap S_{i_2,j}^{k}=\varnothing\);

b) \(\Delta_{i,j}^{k}\to 0\) as \(j\to\infty\);

c) for every \(j\), each point of \(I_1\) belongs to at least 4 intervals of the system \(\{S_{i,j}^{k}\}\) with one and the same fixed \(j\).

The construction of \(S_{i,j}^{k}\) will be carried out by induction on \(j\). For \(j=1\) we take \(i_{1,k}=1\) and put \(S_{1,1}^{k}=I_1\). We shall assume that the intervals \(S_{i,n-1}^{k}\) have been constructed. From the set \(\{S_{i,n-1}^{k}\}\) choose an interval \(S_{i_1,n-1}^{k_1}\) such that
\[ \Delta_{i_1,n-1}^{k_1}\geq \Delta_{i,n-1}^{k} \]
for all \(i\) and \(k\). Near its center, for example at a distance not exceeding \(\frac14\Delta_{i_1,n-1}^{k_1}\), fix a point \(x_{i_1,n-1}^{k_1}\) which is not an endpoint of the intervals \(\{S_{i,n-1}^{k}\}\). By property c) this point belongs to either 4 or 5 intervals of the system \(\{S_{i,n-1}^{k}\}\). Having fixed \(x_{i_1,n-1}^{k_1}\), we arrive at one of the following two cases.

1. \(x_{i_1,n-1}^{k_1}\) belongs to 5 intervals \(\{S_{i,n-1}^{k}\}\). Then a sufficiently small interval \(\lambda\subset S_{i_1,n-1}^{k_1}\) with \(\lambda\ni x_{i_1,n-1}^{k_1}\) will be covered by these same intervals. Remove from \(S_{i_1,n-1}^{k_1}\) a sufficiently small interval belonging to \(\lambda\), containing the point \(x_{i_1,n-1}^{k_1}\), and lying at a positive distance from the endpoints of the intervals of the system \(\{S_{i,n-1}^{k}\}\). We obtain two intervals \(L\) and \(R\) (left and right). In this case, for \(k\neq k_1\) put \(S_{i,n}^{k}=S_{i,n-1}^{k}\). As \(\{S_{i,n}^{k_1}\}\) take the system consisting of the intervals \(L\) and \(R\) and of the intervals \(\{S_{i,n-1}^{k_1}\}\), with the exception of the interval \(S_{i_1,n-1}^{k_1}\).

2. \(x_{i_1,n-1}^{k_1}\) belongs to 4 intervals \(\{S_{i,n-1}^{k}\}\). This means that for some \(p\),
   \[ x_{i_1,n-1}^{k_1}\notin \bigcup_i S_{i,n-1}^{p}. \]
   In this case remove from the segment \(S_{i_1,n-1}^{k_1}\) an interval \(\lambda\ni x_{i_1,n-1}^{k_1}\) of such small length that it is possible to indicate an interval \(B_{i_1,n-1}^{p}\) such that
   \[ B_{i_1,n-1}^{p}\cap \bigcup_i S_{i,n-1}^{p}=\varnothing \]
   and \(B_{i_1,n-1}^{p}\supset \lambda\). Let us note here that the length \(\Delta_n\) of the interval \(B_{i_1,n-1}^{p}\) can be chosen arbitrarily small. \(\Delta_n\) will be chosen below in the construction of the functions.

In this case, as before, the intervals \(L\) and \(R\) (obtained by removing \(\lambda\) from \(S_{i_1,n-1}^{k_1}\)) and \(\{S_{i,n-1}^{k_1}\}\) without the interval \(S_{i_1,n-1}^{k_1}\) will constitute \(\{S_{i,n}^{k_1}\}\). The system \(\{S_{i,n}^{p}\}\) will consist of the intervals \(\{S_{i,n-1}^{p}\}\) and the interval \(B_{i_1,n-1}^{p}\). For \(k\neq k_1\) and \(k\neq p\) put \(S_{i,n}^{k}=S_{i,n-1}^{k}\).

Thus the systems \(\{S_{i,j}^{k}\}\) \((k=1,2,\ldots,5)\) on \(I_1\) have been constructed. (In the assumption that \(\Delta_n\) is given each time when this is necessary. It will be seen below that \(\Delta_n\) is chosen immediately after the \((n-1)\)-st step of constructing the systems of intervals.) They possess properties a), b), and c).

On the segment \(\bar I_1\) \((0\leq y\leq 1)\), in an analogous way, we construct systems of intervals \(\{T_{i,j}^{k}\}\). (In constructing the systems \(\{T_{i,n}^{k}\}\), in analogy with \(L,R,B_{i_1,n-1}^{p}\), and \(x_{i_1,n-1}^{k_1}\), there arise the intervals \(\bar L,\bar R,\bar B_{i_1,n-1}^{p}\) and the point \(y_{i_1,n-1}^{k_1}\).)

Denote
\[ P_{(i,l),j}^{k}=\{(x,y): x\in S_{i,j}^{k},\ y\in T_{l,j}^{k}\}. \]
Renumber the pairs \((i,l)\) by the index \(\alpha\) and put
\[ P_{\alpha,j}^{k}=P_{(i(\alpha),\,l(\alpha)),j}^{k}. \]
The system of rectangles \(\{P_{\alpha,j}^{k}\}\) satisfies the conditions of Lemma 1.

Construction of the functions. \(\varphi_k(x)\) and \(\psi_k(y)\) will be obtained as the limits of certain sequences \(\varphi_{k,j}(x)\) and \(\psi_{k,j}(y)\) as \(j\to\infty\).

We shall construct \(\varphi_{k,j}(x)\) and \(\psi_{k,j}(y)\) so that they satisfy the following conditions:

г) for fixed \(j\) and \(k\), the functions \(\varphi_{k,j}(x)\) and \(\psi_{k,j}(y)\) are constant on the intervals \(S_{i,j}^{k}\) and \(T_{i,j}^{k}\), respectively, and linear in the intervals complementary to \(\bigcup_i S_{i,j}^{k}\) and \(\bigcup_i T_{i,j}^{k}\), respectively;

д) \(\varphi_{k,j}(x)\) and \(\psi_{k,j}(y)\) are nondecreasing functions;

е) the function
\[ \Phi_{k,j}(x,y)=\varphi_{k,j}(x)+\psi_{k,j}(y) \]
is such that, for any fixed \(k\) and \(\tau\le j\), and for \(a_1\ne a_2\),
\[ \rho\bigl(\Phi_{k,j}(P_{a_1,\tau}^{k}),\Phi_{k,j}(P_{a_2,\tau}^{k})\bigr)>\varepsilon_\tau>0, \]
where \(\Phi_{k,j}(P_{a,\tau}^{k})\) is the set of values of the function \(\Phi_{k,j}(x,y)\) on the rectangle \(P_{a,\tau}^{k}\), and \(\rho(B,C)\) is the distance between the sets \(B\) and \(C\);

ж) the functions \(\varphi_{k,j}(x)\) and \(\psi_{k,j}(y)\) satisfy a Lipschitz condition with constant \(<1\);

з)
\[ \max_x|\varphi_{k,j-1}(x)-\varphi_{k,j}(x)|\le 1/2^j,\qquad \max_y|\psi_{k,j-1}(y)-\varphi_{k,j}(y)|\le 1/2^j \]
(condition (з) is needed only to ensure the uniform convergence of the functions \(\varphi_{k,j}(x)\) and \(\psi_{k,j}(y)\) as \(j\to\infty\)).

The functions \(\varphi_{k,j}(x)\) and \(\psi_{k,j}(y)\) are constructed by induction.

For \(j=1\), \(k=1,2,\ldots,5\), put \(\varphi_{k,1}(x)=\psi_{k,1}(y)\equiv 0\). The passage from the functions \(\varphi_{k,n-1}(x)\) and \(\psi_{k,n-1}(y)\) to the functions \(\varphi_{k,n}(x)\) and \(\psi_{k,n}(y)\) is connected with the construction of the intervals \(\{S_{i,n}^{k}\}\) and \(\{T_{i,n}^{k}\}\), and is therefore carried out by one of the following two methods.

I. In case 1 (see the construction of the systems of intervals), for \(k\ne k_1\) we take
\[ \varphi_{k,n}(x)=\varphi_{k,n-1}(x) \]
and
\[ \psi_{k,n}(y)=\psi_{k,n-1}(y). \]
For \(k=k_1\), on all intervals \(S_{i,n}^{k_1}\), except \(Л\) and \(П\), put \(\varphi_{k_1,n}(x)=\varphi_{k_1,n-1}(x)\), and on \(T_{i,n}^{k_1}\), except \(\overline{Л}\) and \(\overline{П}\), put \(\psi_{k_1,n}(y)=\psi_{k_1,n-1}(y)\).

Put
\[ \varphi_{k_1,n}(Л)=\varphi_{k_1,n-1}(Л)+\varepsilon_{n,1},\qquad \psi_{k_1,n}(\overline{Л})=\psi_{k_1,n-1}(\overline{Л})-\varepsilon_{n,2}, \]
\[ \varphi_{k_1,n}(П)=\varphi_{k_1,n-1}(П)+\varepsilon_{n,3},\qquad \psi_{k_1,n}(\overline{П})=\psi_{k_1,n-1}(\overline{П})+\varepsilon_{n,4}, \]
and in the intervals complementary to \(\bigcup_i S_{i,n}^{k_1}\) and \(\bigcup_i T_{i,n}^{k_1}\), respectively, define \(\varphi_{k_1,n}(x)\) and \(\psi_{k_1,n}(y)\) to be linear and to agree at the endpoints of the intervals with the already assigned values.

Choose the numbers \(\varepsilon_{n,\beta}>0\) so that \(\varphi_{k_1,n}(x)\) and \(\psi_{k_1,n}(y)\) still satisfy conditions (д), (е), (ж), and (з). (We note that under condition (е), for sufficiently small \(\varepsilon_{n,\beta}\), it is necessary to monitor only the case \(\tau=n\), since for small changes of \(\varphi_{k_1,n-1}(x)\) and \(\psi_{k_1,n-1}(y)\) the obtained functions \(\varphi_{k_1,n}(x)\) and \(\psi_{k_1,n}(y)\) satisfy condition (е) for \(\tau<n\).)

II. In case 2 (see the construction of the systems of intervals), for \(k\ne k_1\) and \(k\ne p\) put
\[ \varphi_{k,n}(x)=\varphi_{k,n-1}(x) \]
and
\[ \psi_{k,n}(y)=\psi_{k,n-1}(y). \]
On the intervals
\[ S_{i,n}^{p}\ne B_{i_1,n-1}^{p} \]
and
\[ T_{i,n}^{p}\ne \overline{B}_{i_1,n-1}^{p} \]
respectively, take
\[ \varphi_{p,n}(x)=\varphi_{p,n-1}(x) \]
and
\[ \psi_{p,n}(y)=\psi_{p,n-1}(y). \]

Put
\[ \varphi_{p,n}(B_{i_1,n-1}^{p})=\varphi_{p,n-1}(x_{i_1,n-1}^{k_1})+\varepsilon_n', \qquad \psi_{p,n}(\overline{B}_{i_1,n-1}^{p})=\psi_{p,n-1}(y_{i_1,n-1}^{k_1})+\varepsilon_n'', \]
where \(\varepsilon_n'\) and \(\varepsilon_n''\) will be chosen below.

In the intervals complementary to \(\bigcup_i S_{i,n}^{p}\) and \(\bigcup_i T_{i,n}^{p}\), respectively, define \(\varphi_{p,n}(x)\) and \(\psi_{p,n}(y)\) to be linear and to agree at the endpoints of the intervals with the already assigned values. Recall that we could choose the length \(\Delta_n\) of the intervals \(B_{i_1,n-1}^{p}\) and \(\overline{B}_{i_1,n-1}^{p}\) arbitrarily. We now choose it so that, for sufficiently small \(\varepsilon_n'\) and \(\varepsilon_n''\), \(\varphi_{p,n}(x)\) and \(\psi_{p,n}(y)\) satisfy condition (ж). Now choose \(\varepsilon_n'\) and \(\varepsilon_n''\) so that the functions \(\varphi_{p,n}(x)\) and \(\psi_{p,n}(y)\) satisfy conditions (д), (е), (ж), and (з).

The functions \(\varphi_{k_1,n}(x)\) and \(\psi_{k_1,n}(y)\) are obtained from the functions \(\varphi_{k_1,n-1}(x)\) and \(\psi_{k_1,n-1}(y)\) in the same way as in case 1.

Now set

\[ \varphi_k(x)=\lim_{j\to\infty}\varphi_{k,j}(x), \qquad \psi_k(y)=\lim_{j\to\infty}\psi_{k,j}(y), \]

\[ \Phi_k(x,y)=\varphi_k(x)+\psi_k(y). \]

Since for \(\Phi_{k,j}(x,y)\) condition (e) is fulfilled for every \(j\), the \(\Phi_k(x,y)\) satisfy the conditions of Lemma 1. From condition (ж) it follows that \(\varphi_k(x)\) and \(\psi_k(y)\), for every \(k\), satisfy a Lipschitz condition with constant 1. The theorem is proved.

I express my gratitude to A. G. Vitushkin and G. M. Khenkin for their guidance in carrying out this work.

Moscow State University
named after M. V. Lomonosov

Received
20 II 1967

REFERENCES

\(^{1}\) A. N. Kolmogorov, DAN, 114, No. 5 (1957).
\(^{2}\) A. G. Vitushkin, DAN, 156, No. 6 (1964).
\(^{3}\) G. M. Khenkin, DAN, 157, No. 2 (1964).