Non-trivial solution to $\sum^{n}_{i=1}\sum^{n}_{j=1,j\ne i}(x_{i})^{(x_j)}=(\sum^{n}_{i=1}x_i)^{(\sum^{n}_{i=1}x_i)}$

Question

This problem was first asked at Mathematics Stack Exchange, where it wasn't drawn much attention.

For ease of reading, $$S=\sum_{i=1}^nx_i, S_p=\sum_{i=1,i\ne p}^nx_i, S^{[q]}=\sum_{i=1}^nx_i^q, S_p^{[q]}=\sum_{i=1,i\ne p}^nx_i^q. \sum\text{ refers to }\sum_{i=1}^n.$$ Note that $S^q$ is not $S^{[q]}$ and $S_p^q$ is not $S_p^{[q]}$.

Define an equation $A_n$: $$\sum S_i^{[x_i]}=S^S.$$ For example, $A_3$ is: $${x_1}^{x_2}+{x_1}^{x_3}+{x_2}^{x_1}+{x_2}^{x_3}+{x_3}^{x_1}+{x_3}^{x_2}=({x_1}+{x_2}+{x_3})^{({x_1}+{x_2}+{x_3})}.$$

Without loss of generality, for every non-negative integer solutions (hereinafter called "solutions") for $A_n$, $x_i\le x_{i+1}$ for every $1\leq i<n$, then there are two distinct non-negetive solutions for $A_3$, one is ${x_1}=0,{x_2}=0,{x_3}=2$, and the other is ${x_1}=0,{x_2}=1,{x_3}=1$.

We call a solution for $A_n$ 'non-trivial' if $x_{n-1}\ne0$. The only known non-trivial solution is ${x_1}=0,{x_2}=1,{x_3}=1$ for $A_3$. The problem is: are there any more non-trivial solutions for $A_n$?
If so, please give an example.

Since this question is difficult enough, I will also recieve answers which give some features about every non-trivial solutions.

Update on 2021-06-26: Claim. For every solution to $A_n$, $$S^{S_n}\le n(n-1).$$

Proof.

1. Lemma 1. Claim. $$S_i^{[x_i]}\le(n-1)S_i^{x_i}.$$
   Proof. If $x_1=0$, then $$S_i^{[x_i]}=(n-1)S_i^{x_i}.$$ If $x_1\ne0$, then $$S_i^{[x_i]}\le S_i^{x_i}\le(n-1)S_i^{x_i}.$$
2. For every $1\le i<n$, $x_i\le x_{i+1}$, therefore, for every $1\le i\le n$, $x_i\le x_n$. And for every $1\le i\le n$, $x_i$ is non-negetive integer, therefore, for every $1\le i\le n$, $$S_i^{x_i}\le S_i^{x_n}\le S^{x_n}.$$
3. Therefore, $$S^S=\sum S_i^{[x_i]}\le(n-1)\sum S_i^{x_i}\le(n-1)\sum S^{x_n}=n(n-1)S^{x_n}, $$ that is, $$\frac{S^S}{S^{x_n}}\le n(n-1).$$ Since $$\frac{S^S}{S^{x_n}}=S^{S-x_n}=S^{S_n},$$ $$S^{S_n}\le n(n-1).$$ And that's what we want. $\tiny{\text{I've typed for an hour and I finished it finally :)}}$

Update on 2021-07-02: Claim. For every non-trivial solution to $A_n$, $$S^{S_n}\le\frac{n^2-3n+6}2.$$ Proof.

1. Split $x_i$ to $m$ zeros and $(n-m)$ non-zeros, $0\le m\le n-2$, $$S^S=\sum S_i^{[x_i]}=\sum_{i=1}^mS_i^{[x_i]}+\sum_{i=m+1}^nS_i^{[x_i]}\le m(n-1)+\sum_{i=m+1}^nS_i^{x_i}\le m(n-1)+(n-m)S^{x_n}.$$
2. $$S^{x_n}\ge n-m,$$ $$m(n-1)+(n-m)S^{x_n}\le\frac{m(n-1)}{n-m}\cdot S^{x_n}+(n-m)S^{x_n}=(n-m+\frac{m(n-1)}{n-m})S^{x_n}.$$
3. $$d(n-m+\frac{m(n-1)}{n-m})/dx=\frac{n(n-1)}{(n-m)^2}-1,$$ which is always positive for $n-\sqrt{n(n-1)}\le m\le n-2$.
   We can see that $n-m+\frac{m(n-1)}{n-m}$ is the greatest when $m=n-2$, $$(n-m+\frac{m(n-1)}{n-m})S^{x_n}\le2+\frac{(n-2)(n-1)}2\cdot S^{x_n}=\frac{n^2-3n-6}2\cdot S^{x_n}.$$
4. $$S^S\le\frac{n^2-3n-6}2\cdot S^{x_n},$$ $$S^{S_n}=\frac{S^S}{S^{x_n}}\le\frac{n^2-3n+6}2.$$ And that's what we want.

Answer 1

Split $x_i$ into $z$ zeroes and a partition of $n$ into $k$ (non-zero) parts, $\lambda_j$. Then your equality can be rewritten as $$z(z-1) + kz + \mathop{\sum\sum}_{i \neq j} \lambda_i^{\lambda_j} = n^n$$ The solution with positive $z$ is $$z = \frac{-(k-1) + \sqrt{(k-1)^2 + 4n^n - 4\mathop{\sum\sum}_{i \neq j} \lambda_i^{\lambda_j}}}{2}$$ which by a simple parity argument is an integer iff the square root is an integer. Therefore the question reduces to which partitions into more than one part satisfy $$4n^n + (k-1)^2 - 4\mathop{\sum\sum}_{i \neq j} \lambda_i^{\lambda_j} = \square$$

Noting that there are $k(k-1)$ terms in the sum, each of which is a positive integer, and that the non-triviality requirement is that $k > 1$, we see that $\square < 4n^n$, so we rearrange as $$4\mathop{\sum\sum}_{i \neq j} \lambda_i^{\lambda_j} - (k-1)^2 = 4n^n -\square$$ where both sides are positive.

Case $n = 2m$

$4n^n = (2n^m)^2$ is a square, so we require $$4\mathop{\sum\sum}_{i \neq j} \lambda_i^{\lambda_j} - (k-1)^2 \ge 4n^m - 1$$ to at least reach the next square down.

For $m=1$ we have the known solution; for $m > 1$ the map $x \to x^m$ is superlinear, so a priori it feels hard to satisfy even the relaxed condition $$\mathop{\sum\sum}_{i \neq j} \lambda_i^{\lambda_j} \ge n^m$$ In fact, empirically even if we replace $\mathop{\sum\sum}_{i \neq j}$ by $\sum_i \prod_{j \neq i}$ we fall short for $n > 2$.

Case $n = m^2$

$4n^n = (2m^n)^2$, so we get a very similar condition

$$4\mathop{\sum\sum}_{i \neq j} \lambda_i^{\lambda_j} - (k-1)^2 \ge 4m^n - 1$$

and again, empirically we fall short even replacing the inner $\sum$ by $\prod$.

Case $n = 2m+1$ is not a square

This is the tricky case. The nearest square is $\lfloor 2n^m \sqrt{n} \rfloor^2$.

If we let $s = \lfloor 2n^m \sqrt{n} \rfloor$, $f = \textrm{fpart}(2n^m \sqrt{n})$, then $4n^n = (s+f)^2$ and we require

$$4\mathop{\sum\sum}_{i \neq j} \lambda_i^{\lambda_j} - (k-1)^2 \ge 2sf + f^2$$

but this isn't much use unless we can bound $f$ below. Empirically again the RHS grows exponentially for small $n$, but here we can't easily justify that the gap between the maximum LHS and the RHS won't jump down.

So the strongest claim that I can justify with this approach is that, other than the known example, non-trivial examples will have $n$ odd and not a square.

Answer 2

On OP's request, I am converting my comment into an answer.

This answer proves the following claims :

Claim 1 : For every non-trivial solution to $A_n$, $S^{S_n}\le \dfrac{n(n-1)}{2}$.

Claim 2 : $A_2$ has no non-trivial solution. $A_3$ has only one non-trivial solution. Each of $A_4,A_5,A_6,A_7$ has no non-trivial solution.

Claim 3 : For every non-trivial solution to $A_n$, $x_1=x_2=\cdots =x_{\lfloor (2n-1)/3\rfloor}=0$.

---

Claim 1 : For every non-trivial solution to $A_n$, $S^{S_n}\le \dfrac{n(n-1)}{2}$.

Proof : We have $$S^{S}=\sum^{n}_{i=1}\sum^{n}_{j=1,j\neq i}{x_{i}}^{x_j}\le n(n-1){x_n}^{x_n}$$ from which we get $$S^{S_n}=\frac{S^S}{S^{x^n}}\le n(n-1)\bigg(\frac{x_n}{S}\bigg)^{x_n}\le n(n-1)\bigg(\frac{x_n}{1+x_n}\bigg)^{x_n}\le \frac{n(n-1)}{2}$$ since $2\le\bigg(1+\dfrac{1}{x_n}\bigg)^{x_n}$.

---

Claim 2 : $A_2$ has no non-trivial solution. $A_3$ has only one non-trivial solution. Each of $A_4,A_5,A_6,A_7$ has no non-trivial solution.

Proof :

For $n=2$, it follows from $x_1=0$ (supposing that $x_1\ge 1$ gives $n^{n-1}\le n(n-1)/2$ which is impossible) that $A_2$ has no non-trivial solution.

For $n=3$, we have $x_1=0$ and $(x_2+x_3)^{x_2}\le 3$ which implies $x_2=1$. So, it follows from $x_3+3=({x_3}+1)^{{x_3}+1}$ that $x_3=1$.

For $n=4$, it follows from $x_1=x_2=0$ (if $x_2\ge 1$, then $(n-1)^{n-2}\le n(n-1)/2$ implies $n\le 3$) that $(x_3+x_4)^{x_{3}}\le 6$ which implies $x_3=1$, and $x_4+7=(x_4+1)^{x_4+1}$ has no non-negative integer solution.

For $n=5$, we have $x_1=x_2=0$, so $(x_3+x_4 +x_5)^{x_3+x_4}\le 10$ implies $x_3\le 1$. If $x_3=0$, then $(x_4 +x_5)^{x_4}\le 10$ implies $x_4=1$, and $(x_5+1)^{x_5+1}=x_5+13$ has no integer solution. If $x_3=1$, then $(1+x_4 +x_5)^{1+x_4}\le 10$ implies $x_4=1$, and $(x_5+2)^{x_5+2}=2x_5+12$ has no non-negative integer solution.

For $n=6$, we have $x_1=x_2=x_3=0$ (if $x_3\ge 1$, then $(n-2)^{n-3}\le n(n-1)/2$ implies $n\le 5$) that $(x_4 +x_5+x_6)^{x_4+x_5}\le 15$ which implies $x_4\le 1$. If $x_4=0$, then $(x_5+x_6)^{x_5}\le 15$ implies $x_5=1$, and $(1+x_6)^{1+x_6}=x_6+21$ has no non-negative integer solution. If $x_4=1$, then $(1+x_5+x_6)^{1+x_5}\le 15$ implies $x_5=1$, and $(2+x_6)^{2+x_6}=2x_6+19$ has no non-negative integer solution.

For $n=7$, we have $x_1=x_2=x_3=0$, so $(x_4+x_5+x_6+x_7)^{x_4+x_5+x_6}\le 21$ implies $x_4=0$ and $x_5\le 1$. If $x_5=0$, then $(x_6+x_7)^{x_6}\le 21$ implies $x_6\le 2$. If $x_6=1$, then $(1+x_7)^{1+x_7}=x_7+31$ has no non-negative integer solution. If $x_6=2$, then $(2+x_7)^{2+x_7}=19+2^{x_7}+{x_7}^2$ has no non-negative integer solution. If $x_5=1$, then $(1+x_6+x_7)^{1+x_6}\le 21$ implies $x_6=1$, and $(x_7+2)^{x_7+2}=28+2x_7$ has no non-negative integer solution.

---

Claim 3 : For every non-trivial solution to $A_n$, $x_1=x_2=\cdots =x_{\lfloor (2n-1)/3\rfloor}=0$.

Proof :

If $x_{m}\ge 1$ where $4\le m\le n-1$, then we have, from Claim 1, $$(n-m+1)^{n-m}\le\frac{n(n-1)}{2}$$ i.e. $$n^2-n-2(n-m+1)^{n-m}\ge 0$$

Let $f(n):=n^2-n-2(n-m+1)^{n-m}$. Then, $$f'(n)=2n-1-2 (n-m + 1)^{n - m} \bigg(\frac{n - m}{n-m + 1} + \ln(n-m + 1)\bigg) $$ and $$f''(n)= 2-2(n-m + 1)^{n - m}\bigg(\frac{n-m+2}{n-m + 1}+\bigg(\frac{n - m}{n-m + 1} + \ln(n-m + 1)\bigg)^2\bigg) $$

Since $f''(n)$ is negative, we see that $f'(n)$ is decreasing. We also have $f(m+1)\gt 0$ and $f\bigg(\dfrac{3m+1}{2}\bigg)\lt 0$, so we can say that

$$x_m\ge 1\implies f(n)\ge 0\implies n\lt \dfrac{3m+1}{2}\implies m\gt \frac{2n-1}{3}$$ So, we can say that $$m\le \frac{2n-1}{3}\implies x_{m}=0$$ which means that $$x_1=x_2=\cdots =x_{\lfloor (2n-1)/3\rfloor}=0.$$

Answer 3

The results are shown in this answer.

1. The upper bound of $S^{S_n}$.
   I proved that $S^{S_n}\le n(n-1)$.
   @mathlove commented that $S^{S_n}\le n(n-1)/2$.
   I proved that $S^{S_n}\le\frac{n^2-3n-6}2$.
2. The parity of $S^S$. @PeterTaylor proved that $S^S$ is odd and not a square.
3. Zeros. @mathlove commented that $x_1=x_2=\cdots=x_{\lfloor(2n-1)/3\rfloor}=0$.