Can every symmetric function be written as some function of a sum? 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.
 A: 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.
A: 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.
A: 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.
A: 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.
A: 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,•)$).
