Can every symmetric function be written as some function of a sum?

Question

I am looking for a simple counter-example to a "theorem" about symmetric functions claimed in a published paper. The claim asserts, among many other things, that there are functions $\sigma$ and $\rho$ such that, for all $x,y\in\mathbb R$, $$ \max(x,y) = \sigma(\rho(x) + \rho(y)). $$ The paper doesn't specify the domain of $\sigma$, which is, of course, also the range of $\rho$. I'll denote this unknown by $G$. And let's assume that $G$ is some well-known type of mathematical object, in which addition is conventionally defined, for example an abelian semigroup.

Can $\sigma$ and $\rho$ be found, if $G$ is an abelian (semi-)group? What if $X$ is a set and $G = \mathbb R^X$ is the set of functions from $X$ to $\mathbb R$?

Actually, since real numbers can't be handled by a Turing machine, and the journal in which the paper appears is devoted to computer science, I would prefer a discussion in which the reals were replaced throughout the passage above by the integers. I expect the claim to be incorrect for any reasonable (non-finite) context.

If the reals are replaced by a finite closed interval of real numbers then any continuous symmetric function can be approximated by a symmetric polynomial, and then one can use Newton's identities to get an approximate result. Possibly this is what the author of the paper at issue was thinking, but not stating.

Answer 1

I'll answer your question for $\mathbb{R} \to \mathbb{R}$.

Let $r(x,y) = p(x) + p(y)$. Your question boils down to whether there exists $p$ such that $r$ is injective up to symmetry.

Since $\mathbb{R}$ has uncountable dimension over $\mathbb{Q}$, there exists for each $x \in \mathbb{R}$ some $t_x \in \mathbb{R}$ such that the set $\{t_x \}_x$ is linearly independent. Set $p(x) = t_x$, so $r$ is injective and therefore there exists a $\sigma$ as desired.

(This uses the axiom of choice.)

Edit: I guess, it also uses the continuum hypothesis. I'm guessing there should be a proof avoiding some of these?

Edit 2: As pointed out in the comments, CH is not needed.

Answer 2

For integers: Let $ρ(x) = 2^x$ for every integer $x$. Then given $ρ(x)+ρ(y)$ you can look at the binary form to determine $x,y$ and hence their maximum.

Answer 3

A more concrete version of the idea from user21820's answer, for the situation where the domain of discourse is the integers:

Define $\rho(x) = 4^x$, and define $\sigma(t) = \lfloor \log_4 t\rfloor$, where $\log_4$ is the base-4 logarithm.

Answer 4

The solution for integers generalizes to a constructive solution for real numbers, as follows.

To define $\rho$, first apply some constructive strictly-increasing map to reduce to the case where all our numbers are between $0$ and $1$. One such transformation is $x' = \frac12 + \frac1\pi \arctan x$.

Then, given a value $x' \in (0,1)$, write down sequence of zeroes and ones:

• A block of length $3$ in which the $\lceil 2x'\rceil^{\text{th}}$ bit is a $1$, and the others are $0$.
• A block of length $4$ in which the $\lceil 3x'\rceil^{\text{th}}$ bit is a $1$, and the others are $0$.
• A block of length $5$ in which the $\lceil 4x'\rceil^{\text{th}}$ bit is a $1$, and the others are $0$.
• And so on. In general, for each $n$, a block of length $n+1$ in which the $\lceil nx'\rceil^{\text{th}}$ bit is a $1$, and the others are $0$. Note that the last bit in each block is $0$.

Then, take $\rho(x) \in (0,1)$ to be the number whose binary expansion is this sequence.

Given $\rho(x) + \rho(y)$, we can find $\max\{x,y\}$ as follows. The sum of the blocks of length $n+1$ tells us $2^{\lceil nx'\rceil} + 2^{\lceil ny'\rceil}$, from which we can deduce $\lceil nx'\rceil$ and $\lceil ny'\rceil$ up to permutation. We can figure this out for arbitrarily large $n$, which gives us a sequence of arbitrarily good approximations to $x'$ and $y'$, from which $x$ and $y$ can also be found.

Answer 5

For reals: Let $d(x,k) = \lfloor x·2^k \rfloor$ for every $x∈ℝ$ and natural $k$. Let $ρ(x) = \{ ⟨k,2^{d(x,k)}⟩ : k∈ℕ \}$ for every $x∈ℝ$. Then $ρ(x)$ represents a unique sequence from $ℕ$ for each $x∈ℝ$. Define addition on sequences from $ℕ$ to be pointwise addition. Then for any $x,y∈ℝ$, we can determine $z = \max(x,y)$ from $ρ(x)+ρ(y)$ as follows.

We can easily obtain $S(k) = \{d(x,k),d(y,k)\}$ for each $k∈ℕ$. And $d(z,k) = \max(d(x,k),d(y,k))$ for every $k∈ℕ$. To see why, note that: (1) for any $m∈ℕ$ we have that if $d(x,m) > d(y,m)$ then $d(x,k) > d(y,k)$ for every $k∈ℕ_{>m}$ as well; (2) if $x > y $ then $d(x,m) > d(y,m)$ for some $m∈ℕ$. Therefore we can obtain $z$ since it is uniquely determined by $\{ ⟨k,d(z,k)⟩ : k∈ℕ \}$.

This is completely constructive (each of the desired functions are computable where each input or output $x$ is given as an oracle for $d(x,•)$).