7

Let $f_n$ denote the "averaging" function $[0,1]^n \rightarrow [0,1]$ defined as follows. $$f_n(x_0,\cdots,x_{n-1}) = \frac{x_0 + \cdots + x_{n-1}}{n}$$

Then clearly, it is possible to express $f_4$ in terms of $f_2$.

$$f_4(a,b,c,d) = \frac{a+b+c+d}{4} = \frac{\frac{a+b}{2}+\frac{c+d}{2}}{2} = f_2(f_2(a,b),f_2(c,d)).$$

Question. Can we express $f_3$ in terms of $f_2$ in this way, using $0$ and $1$ as well if necessary? Perhaps this is trivial, but I cannot see the answer.

A more precise statement of the problem.

Let $A$ denote the following set of "primitive symbols." $$\{a,b,c,0,1\}.$$ We define a class of "valid expressions" $B$ as the least superset of $A$ such that if $\alpha,\beta \in B$, then $f_2(\alpha,\beta) \in B$.

The problem can be solved in one of two ways, listed here below.

  1. Option 1. Find an expression in $B$ that correctly defines $f_3(a,b,c).$
  2. Option 2. Show that no such expression exists.
goblin GONE
  • 67,744

2 Answers2

4

You cannot build $f_3$ in such a way.

A first solution, not the most rigorous but it gets the idea across without using too much algebra:

Let $R$ be any ring where $2$ is invertible. Then $\frac{x+y}{2}$ is defined on elements of $R$.

This allows us to define a mapping $\varphi: B \times R^3 \to R$, where $\varphi(\beta,a,b,c)$ is the result of evaluating the symbolic expression $\beta$, with the values $a,b,c \in R$ substituted in.

(For example, if $\beta = f_2(f_2(a,b),c)$, then $\varphi(\beta,a,b,c) = \frac{a+b}{4} + \frac{c}2$.)

Suppose there is an expression $\beta \in B$ such that $\varphi(\beta,a,b,c) = \frac{a+b+c}{3}$. Then $\varphi(\beta,1,0,0) = \frac{1}3$, and so $3$ is invertible in $R$.

(This part bothers me a bit, because it's a bit presumptuous to even write down the expression $\frac{a+b+c}{3}$. Perhaps it would be better stated that $3 \varphi(\beta,a,b,c) = a+b+c.$ Either way, $3$ ends up being invertible so long as 2 is, if we suppose that we can build $f_3$ by iterating $f_2$, and allowing ourselves to substitute in 1 and 0.)

And, so, it suffices to note there are rings $R$ where 3 is not invertible, but 2 is. One such ring is $\mathbb{Z}/3$.

I intended the above solution to avoid possibly confusing abstraction, but in response to comments below I will be super rigorous:

Let $S = \mathbb{Z}[\frac{1}2]$ denote the ring of rational numbers with denominator a power of two. We can define a mapping of sets $\tau : B \to S[a,b,c]$ by sending $a,b,c,0,1$ to themselves, and $f_2(x,y)$ to $\frac{1}2 (\tau(x) + \tau(y))$. A simple induction proves that the image of $\tau$ consists solely of linear polynomials.

The map $\tau$ extends linearly to a map of $S-$modules $\varphi: SB \to S[a,b,c]$. We have also the change of rings morphism $\theta : S[a,b,c] \to \mathbb{R}[a,b,c]$, and evaluation maps $ev_{(x,y,z)} : \mathbb{R}[a,b,c] \to \mathbb{R}$.

This gives chains of $S$-module morphisms

$$SB \xrightarrow{\varphi} S[a,b,c] \xrightarrow{\theta} \mathbb{R}[a,b,c] \xrightarrow{ev} \mathbb{R}.$$

where $ev$ is any one of the many evaluation maps we might choose from.

The map $\varphi$ also has image solely among the linear polynomials, while $\theta$ is injective and degree-preserving.

If $ev_{(x,y,z)}P = ev_{(x,y,z)} Q$ for every $x,y,z \in [0,1]$, and $P,Q,$ are linear polynomials, then $P = Q$.

Therefore, it suffices to show that there is no $\beta \in SB$ such that $\theta (\varphi(\beta)) = \frac{a+b+c}{3}.$

Proof of claim: Suppose otherwise. Then $\theta (3 \varphi(\beta)) = 3\theta (\varphi (\beta)) = a+b+c$. The map $\theta$ is injective, so $3\varphi(\beta) = a+b+c$. Evaluating at $(a,b,c) = (1,0,0)$ gives that $3\varphi(\beta)(1,0,0) = 1 \in S$; yet, $3$ is not invertible in $S$ (*). This gives a contradiction.

(*) For various reasons: to stick to my guns a bit, one being that, since $2$ is a unit in $\mathbb{Z}/3$, there is a unique ring morphism $S \to \mathbb{Z}/3$ extending the canonical quotient map $\mathbb{Z} \to \mathbb{Z}/3$. As $3$ is not a unit in $\mathbb{Z}/3$, it cannot be a unit of $S$.

Thomas Belulovich
  • 3,891
  • By $\mathbb{Z}/3$, do you mean the set of integers modulo $3$? – goblin GONE Dec 21 '13 at 07:48
  • Yes. It seems like a bit of cheating, but any "formula" for building $f_3$ symbolically using $f_2$, 0, and 1, should work in any field where division by 2 is defined (i.e. a field not of characteristic 2). – Thomas Belulovich Dec 21 '13 at 07:49
  • Okay, but why should the fact that $f_3$ does not exist in $\mathbb{Z}/3$ impact its definability in terms of $f_2$ over $[0,1]$? Note that the latter is not even a field. – goblin GONE Dec 21 '13 at 07:54
  • The definition of $f_n$ extends to $\mathbb{R}$ perfectly well. Another way to think about it is that $f_2$ doesn't introduce any "powers of three" into the denominator. – Thomas Belulovich Dec 21 '13 at 07:57
  • Yet another thing that could be said is that there is a mapping from the set $B$ you've defined to the set of functions $F^3 \to F$ (where $F$ is any field of characteristic different from 2), where given $\beta \in B$, you can define $\beta(a,b,c) = $ (what you get when you plug in $a,b,c$ into $\beta$). This mapping sends $f_n$ to the "averaging" function in $F$, so if $f_3$ were in $B$, there would be an "averaging" function of three variables in $F$. There isn't always such a thing. – Thomas Belulovich Dec 21 '13 at 07:59
  • I think I see what you're getting at, but I'll have to ponder it for awhile before I can make a decision. – goblin GONE Dec 21 '13 at 08:02
  • I have updated my answer to be a bit more thorough. – Thomas Belulovich Dec 21 '13 at 08:06
  • Even if some element $\beta \in B$ is such that $3\beta(x,y,z) = x+y+z$ for every $x,y,z \in [0,1]$, why is it necessary that $3\varphi(\beta,a,b,c) = a+b+c$ for $a,b,c \in R$? – ronno Dec 21 '13 at 09:26
  • @ronno If a linear polynomial $P(x,y,z)$ agrees with $f_3(x,y,z)$ for all $x,y,z \in [0,1]$, then $P \equiv f_3$. Thanks for pointing that out, I didn't make that explicit. – Thomas Belulovich Dec 21 '13 at 09:39
  • Then you should also include in the implicit induction when defining $\varphi$ that every element of $B$ will be a linear polynomial. – ronno Dec 21 '13 at 09:55
  • @ronno Not wanting to turn the first solution into spaghetti, I added a second solution that is more rigorous as an alternative. – Thomas Belulovich Dec 21 '13 at 10:46
1

We will prove something a bit more general. We prove that no composition can ever take the value $1/3$ when supplied $0$'s and $1$'s as argument. We define $B'$ to be all functions $[0,1]^n \to \mathbb{R}$ which can be written as a composition of $f_2$, $0$ and $1$.

More precisely, $B'$ is the smallest superset of $A' = \{f_2,0,1\}$, where $0,1$ are the constant functions, such that $B'$ is closed under composition.

It's clear that the $B$ defined in the problem, interpreted appropriately, is a subset of this.

  1. $B'$ is given by finite compositions of elements of $A'$, since this is a superset of $A'$ that is closed under composition of $f_2$, and any such superset must contain finite compositions. This is a standard argument in recursive definitions. More precisely, let $A_0' =A'$ and $A_{k+1}' = A_k' \cup \{f_2 \circ (\beta_1,\beta_2) \mid \beta_1,\beta_2 \in A_k'\}$. Then $B' = \cup_k A_k'$. To be even more precise, we should include arity $ar(\beta)$ of elements $\beta \in A_k'$ and the tuple $(\beta_1,\beta_2)$ will have different choices of arity between $\min(ar(\beta_1),ar(\beta_2))$ and $ar(\beta_1)+ar(\beta_2)$ depending on how we mix the arguments.

  2. For any $\beta \in B'$ of arity $n$, and any $n$-vector $v$ of $0$'s and $1$'s, $\beta(v)$ is rational, and in the reduced form, the denominator is a power of $2$. This is easily proved via induction on $k$ above, since $\beta \in A_k'$ for some $k$.

ronno
  • 11,390
  • Ronno thanks for your answer. I'm doing other things at the moment, but I'll definitely have a close read of this either later today, or tomorrow. Once again, thank you. – goblin GONE Dec 21 '13 at 09:56