Composite function

A function that is the composite of several functions. If the range $Y_i$ of a function $f_i$ is contained in the domain $X_{i+1}$ of a function $f_{i+1}$, that is, if

$$f_i\colon X_i\to Y_i\subset X_{i+1},\quad i=1,\dots,n-1,$$

then the function

$$f_n\circ\dots\circ f_1,\quad n\geq2,$$

defined by

$$(f_n\circ\dots\circ f_1)(x)=f_n(\dots(f_1(x))\dots),\quad x\in X_1,$$

is called the composite function or $(n-1)$-fold composite (or superposition) of $f_1,\dots,f_n$. For example, every rational function in any number of variables is a composite of the four arithmetic operations, that is, of the functions $x+y$, $x-y$, $xy$, and $x/y$.

A composite function inherits many of the properties of the functions of which it is composed. For example, the composite of continuous functions is continuous. This means that if a function $f_1\colon X\to Y$ is continuous at a point $x_0\in X$, and a function $f_2\colon Y\to Z$ is continuous at the point $f_1(x_0)\in Y$, then the composite $f_2\circ f_1$ is also continuous at $x_0$ (here $X$, $Y$ and $Z$ are, for example, topological spaces). Similarly, the composite of $n$-fold (continuously) differentiable functions is again $n$-fold (continuously) differentiable, $n=1,2,\dots$. The composite of increasing (decreasing) functions is again increasing (decreasing). In composing functions quantitative properties often change: The composition of two functions $f_1$ and $f_2$ satisfying a Hölder condition of certain degrees is a function satisfying the Hölder condition of degree equal to the product of the degrees of the Hölder conditions satisfied by $f_1$ and $f_2$. Some properties of functions are not preserved under composition. For example, the composite of Riemann- or Lebesgue-integrable functions is not, in general, Riemann or Lebesgue integrable, respectively. The composite of absolutely-continuous functions can turn out not to be absolutely continuous. However, according to the results of N.K. Bari and D.E. Men'shov [1], composition of three absolutely-continuous functions on an interval does not lead to a wider class of functions than that obtained by composing two. Bari [2] proved that any continuous function on a closed interval can be written as the sum of three composites of absolutely-continuous functions, and that there are continuous functions which cannot be written as the sum of two. Moreover, every continuous function on a closed interval is the sum of two composites of functions of bounded variation. Finally, $n$-fold composites of functions of bounded variation lead to essentially new classes of functions for every $n=1,2,\dots,$ and there are continuous functions that are not one-fold compositions of functions of bounded variation [3].

The concept of composition of functions constitutes the widest possible way of giving meaning to the term "representation of a function by a formula" . The problem of representing a function in terms of composites arose in connection with the discovery of formulas for the solutions of algebraic equations. Every root of an equation of degree at most four can be expressed as a composition of the four arithmetical operations and of radicals applied to the coefficients of the equation. By means of a certain substitution (called a Tschirnhausen transformation) every equation of degree $n\geq5$ can be reduced to the form

$$x^n+a_1x^{n-4}+\dots+a_{n-4}x+1=0.$$

Thus, every root of an equation of degree $n\geq5$ is a function of $n-4$ parameters. The problem consists of deciding whether these functions can be represented as a composition of algebraic functions in a smaller number of variables. One of the 23 problems posed by D. Hilbert at the International Congress of Mathematicians in Paris in 1900 is related to this. Namely, the thirteenth problem consists of the following (see [4]): Can a root $f$ of the equation

\begin{equation}f^7+xf^3+yf^2+zf+1=0\label{*}\end{equation}

be represented as a composite of certain continuous functions in two variables applied to the coefficients $x,y$ and $z$? (Note that every function in a finite number of variables is a composite of discontinuous functions in two variables.) Hilbert established the impossibility of obtaining all analytic functions in three variables by composing analytic functions in two variables. He also showed [5] that a solution of an equation of the nine-th degree can be written as a composite of algebraic functions in four variables (instead of in five, as immediately follows from the application of a Tschirnhausen transformation). These investigations were taken up by many mathematicians (see [6]–[19]).

In 1954 A.G. Vitushkin proved [10] that if natural numbers $m,n,m_1$, and $n_1$ satisfy the inequality $(m/n)>(m_1/n_1)$, then it is possible to find an $n$-fold differentiable function in $m$ variables that cannot be written as a composite of $n_1$-fold differentiable functions in $m_1$ variables. In particular, for every $n$ it is possible to find a function in $n$ variables of preassigned smoothness that is not a composite of functions of a smaller number of variables and of the same smoothness. In this sense, among smooth functions of any number of variables there are functions that depend essentially on all their arguments.

In 1956, A.N. Kolmogorov showed [11] that every continuous function defined on an $n$-dimensional cube $(n\geq4)$ is a composite of continuous functions in three variables. Later V.I. Arnol'd reduced the number of variables from three to two. In fact, he proved [12] that any continuous function in three variables on a cube can be written as a composite of continuous functions in two variables (and even, more precisely, as the sum of nine functions each of which is a composite of two continuous functions in two variables). Thus, every continuous function on an $n$-dimensional cube $(n\geq3)$ can be written as a composite of continuous functions in two variables. This was the last word in refuting Hilbert's conjecture on the impossibility of representing the roots of the equation \eqref{*} in the form of composites of continuous functions in two variables. The papers of Kolmogorov and Arnol'd gave, in particular, a positive solution to the problem of representing the roots of algebraic equations of arbitrary degree as composites of continuous functions in at most two variables. For composites of analytic and algebraic functions the corresponding problem remains unsolved. It is not yet known (1987) whether or not the roots of the equation \eqref{*} are composites of analytic functions.

This series of papers is completed by the following theorem of Kolmogorov [13]: Any continuous function in $n$ variables can be obtained by composing continuous functions in one variable and the single function $g(x,y)=x+y$ in two variables. In fact, he proved that any continuous function $f$ on an $n$-dimensional cube can be written in the form

$$f(x_1,\dots,x_n)=\sum_{i=1}^{2n+1}h_i\left(\sum_{j=1}^n\phi_{ij}(x_j)\right),$$

where the functions $h_i$ and $\phi_{ij}$ are continuous, and $\phi_{ij}$ are standard functions, that is, they do not depend on the choice of $f$.

Vitushkin showed [14] that for any finite sets of continuous functions $p_k$ and continuously-differentiable functions $q_k$ in $n$ variables ($k=1,\dots,m$; $n=1,2,\dots$), there even are analytic functions in $n$ variables that cannot be written as a composite of the form

$$\sum_{k=1}^mp_k\circ(f_k\circ q_k),$$

where the $f_k$ are arbitrary continuous functions in one variable.

References

[1]	N.K. Bari, D.E. Men'shov, "Sur l'intégrale de Lebesgue–Stieltjes et les fonctions absolument continues de fonctions absolument continues" Ann. di Math. , 5 (1928) pp. 19–54
[2a]	N. [N.K. Bari] Bary, "Mémoire sur la répresentation des fonctions continues I" Math. Ann. , 103 (1930) pp. 185–248
[2b]	N. [N.K. Bari] Bary, "Mémoire sur la répresentation des fonctions continues II" Math. Ann. , 103 (1930) pp. 598–653
[3]	N.K. Bari, Mat. Sb. , 40 (1933) pp. 326–372
[4]	"Hilbert problems" Bull. Amer. Math. Soc. , 8 (1902) pp. 437–479 (Translated from German)
[5]	D. Hilbert, "Ueber die Gleichung neunten Grades" Math. Ann. , 97 (1927) pp. 243–251
[6]	L. Bieberbach, "Bemerkungen zum dreizehnten Hilbertschen Problem" J. Reine Angew. Math. , 165 (1931) pp. 89–92
[7]	N.G. Chebotarev, , Collected Works , 1 , Moscow-Leningrad (1949) pp. 255–340
[8]	N.G. Chebotarev, "On the problem of resolvents" Uchen. Zap. Kazan. Univ. , 114 : 2 (1954) pp. 189–193 (In Russian)
[9]	V.V. Morozov, "On certain questions in the problem of resolvents" Uchen. Zap. Kazan. Univ. , 114 : 2 (1954) pp. 173–187 (In Russian)
[10]	A.G. Vitushkin, "On higher-dimensional variations" , Moscow (1955) (In Russian)
[11]	A.N. Kolmogorov, "On the representation of continuous functions of several variables by superpositions of continuous functions of a smaller number of variables" Dokl. Akad. Nauk SSSR , 108 : 2 (1956) pp. 179–182 (In Russian)
[12]	V.I. Arnol'd, Dokl. Akad. Nauk SSSR , 114 : 4 (1957) pp. 679–681
[13]	A.N. Kolmogorov, Dokl. Akad. Nauk SSSR , 114 : 5 (1957) pp. 953–956
[14]	A.G. Vitushkin, "Some properties of linear superpositions of smooth functions" Soviet Math. Doklady , 5 (1964) pp. 741–744 Dokl. Akad. Nauk SSSR , 156 (1964) pp. 1258–1261
[15]	G.G. Lorentz, "Approximation of functions" , Holt, Rinehart & Winston (1966)
[16]	D.A. Sprecher, "A survey of solved and unsolved problems on superpositions of functions" J. Approx. Theory , 6 : 2 (1972) pp. 123–134
[17]	J.P. Kahane, "Sur le théorème de superposition de Kolmogorov" J. Approx. Theory , 13 (1975) pp. 229–234
[18]	V.Ya. Lin, "Superpositions of algebraic functions" Functional. Anal. Appl. , 10 : 1 (1976) pp. 32–38 Funktsional. Analiz. i Prilozhen. , 10 : 1 (1976) pp. 37–45
[19]	A.G. Vitushkin, "On representation of functions by means of superpositions and related topics" l'Enseign. Math. , 23 (1977) pp. 255–320