# Are all smooth functions composites of 0-, 1-, and 2-ary functions?

I will formalize my question in terms of algebraic theories.

Background:

Recall that an algebraic theory (in the sense of Lawvere) is a category $\mathcal{C}$ which is closed under taking finite products, and whose set of objects can be identified with the set $\mathrm{Ob}(\mathcal{C})\cong\{T^0,T^1,\ldots\}$, where $T^i=T^1\times T^1\times\cdots\times T^1$ is the $i$-fold product of $T^1$. We denote $T^1$ by $T$. The interesting aspect of an algebraic theory $\mathcal{C}$ are the morphisms $\mathcal{C}(T^i,T^1)$ and their compositions.

For any algebraic theory $\mathcal{C}$, a $\mathcal{C}$-model is defined to be a functor $\mathcal{C}\to\mathbf {Set}$ that preserves all finite products. Denote the category of $\mathcal{C}$-models (and natural transformations between them) by $\mathbf{Mod}(\mathcal{C})$.

Let $n\in\mathbb{N}$ be a natural number, and let $\mathcal{C}$ be an algebraic theory. Its $n$-truncation, denoted $\mathcal{C}_{\leq n}\subseteq\mathcal{C}$, is the smallest algebraic sub-theory that has the same $k$-ary functions $$\mathcal{C}_n(T^k,T^1):=\mathcal{C}(T^k,T^1),$$ for all $k\leq n$. full subcategory spanned by the objects $\{T^0,\ldots,T^n\}$. We say that $\mathcal{C}$ is $n$-truncated if it is equivalent (as a category) to its $n$-truncation.

Setup:

Let $R$ denote the algebraic theory whose morphisms $T^n\to T$ are the smooth functions ${\mathbb R}^n\to{\mathbb R}$. This of course defines the set of morphisms $T^n\to T^m$ for any $m$. Endow $R$ with the usual formula for composing smooth functions.

To me it would be quite surprising if $R$ were 2-truncated. But I've never heard of a 3-ary function $\mathbb{R}^3\to\mathbb{R}$ that wasn't constructed from a combination of 0-, 1-, and 2-ary functions.

Question: Can you prove that $R$ is not 2-truncated? More interestingly, can you name, i.e., construct a 3-ary function that isn't also constructible by a combination of 0-, 1-, and 2-ary functions?

(Note: thanks to Todd Trimble for suggestions on how to clean up this question.)

• Vladimir Arnold answered this question for continuous functions, it seems: en.wikipedia.org/wiki/Hilbert%27s_thirteenth_problem Jan 31 '15 at 23:31
• Might you mean by $\mathcal{C}_{\leq n}$ the smallest Lawvere subtheory contained in $\mathcal{C}$ and with the same $k$-ary operations for $k = 0, \ldots, n$? Jan 31 '15 at 23:38
• My strong recollection is that you get all functions $\mathbb R^n \to \mathbb R$ by composing functions $\mathbb R \to \mathbb R$ and addition $+ : \mathbb R^2 \to \mathbb R$. My recollection is that this is true in both the continuous and smooth cases. But Qiaochu's comment makes me worried that perhaps I'm remembering Arnold's solution to Hilbert's problem for continuous functions, and perhaps my recollections are wrong for the smooth category. Feb 1 '15 at 1:05
• Wikipedia is not very informative on (Kolmogorov and) Arnold's work on this topic. Do you have references to (the original papers and) some "popular" account of the ideas that are involved? (The question should perhaps be tagged as real analysis.) Feb 1 '15 at 10:24

For any $n$, there is an $n$-ary smooth function that is not a composition of smooth functions of lower arity; according to this answer to a very similar question, this is due to Vitushkin (at least for $n=3$). Here is a simple but rather inexplicit proof (adapted from this paper of Akashi and Kodama). Suppose that a smooth n-ary function $f$ can be expressed as a composition of smooth functions $g_i$ of lower arity (WLOG, all of arity $n-1$). Then for each $k$, the $k$-jet of $f$ at any point is determined by the $k$-jets of the $g_i$ at corresponding points. But dimension of the space of $n$-ary $k$-jets grows like $k^n$, while the dimension of the space of $(n-1)$-ary $k$-jets grows like $k^{n-1}$. It follows that for any particular way to compose lower arity functions to get an $n$-ary function, most $k$-jets of $n$-ary functions cannot be so obtained for $k$ sufficiently large. Since there are only countably many such ways to compose, we can use bump functions to construct a single $f$ that has jets at different points that fail for all of them. Actually, by a diagonal argument we can find a single $n$-ary $\infty$-jet (i.e., power series) that is not a composition of jets of lower arity, and every $\infty$-jet can be realized by a smooth function.