Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.
share|improve this question

2 Answers 2

up vote 4 down vote accepted

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$.

share|improve this answer
    
By $\mathbb{Z}/3$, do you mean the set of integers modulo $3$? –  goblin Dec 21 '13 at 7: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 7: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 Dec 21 '13 at 7: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 7: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 7:59

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$.

share|improve this answer
    
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 Dec 21 '13 at 9:56

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.