6
$\begingroup$

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.
$\endgroup$
12
  • 2
    $\begingroup$ You want integers or real numbers? $\endgroup$ Jun 19, 2021 at 13:28
  • $\begingroup$ 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. $\endgroup$ Jun 19, 2021 at 13:49
  • 1
    $\begingroup$ $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$. $\endgroup$ Jun 19, 2021 at 14:19
  • $\begingroup$ @BrendanMcKay And for odd square $t$ it is also close to the square $(2t^{t/2})^2$. $\endgroup$ Jun 19, 2021 at 23:39
  • 1
    $\begingroup$ 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. $\endgroup$
    – mathlove
    Jun 26, 2021 at 10:12

3 Answers 3

4
+25
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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$. $\endgroup$ Jun 26, 2021 at 23:31
  • $\begingroup$ 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. $\endgroup$ Jun 27, 2021 at 9:39
  • 1
    $\begingroup$ @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. $\endgroup$ Jun 27, 2021 at 18:07
  • $\begingroup$ 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. $\endgroup$ Jun 28, 2021 at 8:26
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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$.
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Jul 2, 2021 at 7:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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