# 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)}$

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, 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, $$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.
• You want integers or real numbers? Jun 19, 2021 at 13:28
• I agree with @BrendanMcKay ... as given I would inerpret this in real numbers. Well, positive real numbers so that the powers are also real. In integers, you could allow negative values. Jun 19, 2021 at 13:49
• $4t^t+(t-1)(3t+1)$ is a square for $t=2$. If it is ever a square for larger integer $t$, that will give another 0-1 solution. It doesn't happen up to $t=10000$. For even $t$, it is too close to the square $(2t^{t/2})^2$; I'm not sure about odd $t$. Jun 19, 2021 at 14:19
• @BrendanMcKay And for odd square $t$ it is also close to the square $(2t^{t/2})^2$. Jun 19, 2021 at 23:39
• A slightly better claim can be obtained. One can prove that for every non-trivial solution to $A_n$, $S^{S_n}\le n(n-1)/2$. I've already got the following small results, but don't know how to do for larger $n$. (1) $x_1=0$. (2) If $n\ge 4$, then $x_2=0$. (3) If $n\ge 6$, then $x_3=0$. (4) $A_2$ has no non-trivial solution. (5) $A_3$ has only one non-trivial solution. (6) Each of $A_4,A_5,A_6,A_7$ has no non-trivial solution. Jun 26, 2021 at 10:12

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.

• In fact, choosing partitions into two parts to maximise the LHS, I find that the LHS readily exceeds the RHS for odd non-square $n > 61$, so that this approach in itself isn't going to rule out the case of odd non-square $n$. Jun 26, 2021 at 23:31
• Because of the shape of the sum involving the $\lambda_{i}^{\lambda_{j}}$, it is possible to reformulate the problem as a linear form in logarithms and then using a quantitative version of Baker's theorem to obtain a lower bound for $n$? Perhaps, it could lead to a contradiction, showing no non-trivial solutions for large $n$, or give a finite list of possible $n$ to verify. Jun 27, 2021 at 9:39
• @rgvalenciaalbornoz, I think we want an upper bound on that sum rather than a lower bound, and since all of the quantities involved are integers I'm not sure how to apply Baker's theorem. Of course, maybe someone else can see something I can't. Jun 27, 2021 at 18:07
• Sorry, it was upper, my typo. Thank you for the answer, I agree completely. It was just because I remembered Ellison's numdam.org/article/STNB_1970-1971____A9_0.pdf and maybe something similar could be applied in this case, but I don't know really. As you said, I hope someone else finds the next clue too. Jun 28, 2021 at 8:26

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

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$$.
• To be precise, I haven't proved that $S$ is odd and not a square. I've made an empirical argument which I find completely convincing, but that's not the same thing. Jul 2, 2021 at 7:20