Interesting Power Equality

Let $f(n) = { a }_{ 1 }^{ n }+{ a }_{ 2 }^{ n }+\ldots+{ a }_{ n }^{ n }$ where all variables are positive integers. For instance

\begin{aligned} f(2) &=& {a}_{1}^{2} + {a}_{2}^{2} \\ f(3) &=& {a}_{1}^{3} + {a}_{2}^{3} + {a}_{3}^{3} \end{aligned}

and so on.

I propose the following Conjecture:

There are infinitely many valid solutions for $f(2) = f(3) = f(4) = \ldots$.

For instance for $f(2) = f(3)$, we have $73 = {3}^{2} + {8}^{2} = {1}^{3} + {2}^{3} + {4}^{3}.$ Similarly for $f(2) = f(3) = f(4)$ we have $11378 = {67}^{2} + {83}^{2} = {1}^{3} + {9}^{3} + {22}^{3}\ = {1}^{4} + {3}^{4} + {6}^{4} + {10}^{4}.$

In my opinion there are infinitely many solutions for each case. Can anyone share insights on how to prove this conjecture?

Note by Vikram Pandya
5 years, 3 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

Extension to my comment. I claim the following:

Suppose $a_2, a_3, a_4, \ldots, a_k$ are positive integers such that:

• $a_i \in F_i$ for all $i$
• $\frac{a_m}{a_n}$ is the $\gcd(m,n)$-th power of some rational, for all $m,n$

Then $F_2 \cap F_3 \cap \ldots \cap F_k$ is non-empty.

The idea is that we represent $a_i$ as the sum of $i$ numbers that are $i$-th powers, and then multiply them with some $i$-th power so that all of them are equal. Of course, because there are things like $a_2$ multiplied by a square and $a_4$ multiplied by a fourth power (which is also a square), we cannot pick the $a_i$ randomly, otherwise we might get stuck (say, $a_2$ has a single factor of $2$ and $a_4$ has two, if you try the obvious $2 = 1^2 + 1^2$ and $4 = 1^4 + 1^4 + 1^4 + 1^4$; you can't make them equal).

The second condition is the formalization of "we can't pick them randomly". By Bezout's identity, we can find $p,q$ so that $qn-pm = \gcd(m,n)$; we make sure that the quotient $\frac{a_m}{a_n}$ is a $\gcd(m,n)$-th power, so that we can multiply $a_m$ by a $pm$-th power and $a_n$ by a $qn$-th power, which by canceling is equivalent to multiplying $a_n$ by a $\gcd(m,n)$-th power, what we desire to make $a_m$ and $a_n$ equal.

This way, we only need to find $a_2, a_3, \ldots, a_k$; this is more freedom than finding a single member of $F_2 \cap F_3 \cap \ldots \cap F_k$ directly. I believe that it should be enough to show there always exists a solution, but I don't have a proof yet. For example, we can use this to find a member of $F_2 \cap F_3 \cap F_4$:

\begin{aligned} a_2 &= 25 &=& 3^2 + 4^2 \\ a_3 &= 10 &=& 1^3 + 1^3 + 2^3 \\ a_4 &= 2500 &=& 5^4 + 5^4 + 5^4 + 5^4 \end{aligned}

The only possible problem from the second condition is $m = 2, n = 4$. (For $(m,n) = (2,3), (3,4)$, both of them give $\gcd(m,n) = 1$, and all rationals are the first power of some rational, namely themselves, so this condition is trivial.) The quotient $\frac{a_2}{a_4}$ is $\frac{1}{100}$, which is a $\gcd(2,4) = 2$-nd power of a rational $\frac{1}{10}$. So the second condition is satisfied; we should be able to find the multipliers.

We can indeed multiply $a_2$ by $2500000^2$, $a_3$ by $25000^3$, $a_4$ by $500^4$ to get:

\begin{aligned} 2500000^2 a_2 &= 156250000000000 =& 7500000^2 + 10000000^2 \\ 25000^3 a_3 &= 156250000000000 =& 25000^3 + 25000^3 + 50000^3 \\ 500^4 a_4 &= 156250000000000 =& 2500^4 + 2500^4 + 2500^4 + 2500^4 \end{aligned}

Thus $156250000000000 \in F_2 \cap F_3 \cap F_4$.

Finding the multipliers above ($2500000^2, 25000^3, 500^4$) can be done by solving simple modular equations. Suppose the multipliers are $m_2^2, m_3^3, m_4^4$ for $a_2, a_3, a_4$ respectively. Then,

• $m_2 = 2^{m_{2,2}} 5^{m_{2,5}} k_2$
• $m_3 = 2^{m_{3,2}} 5^{m_{3,5}} k_3$
• $m_4 = 2^{m_{4,2}} 5^{m_{4,5}} k_4$
• $2 m_{2,2} + 0 = 3 m_{3,2} + 1 = 4 m_{4,2} + 2$ (the exponents of the $2$: $25, 10, 2500$ has $0, 1, 2$ as the exponent of the $2$ respectively)
• $2 m_{2,5} + 2 = 3 m_{3,5} + 1 = 4 m_{4,2} + 4$ (the exponents of the $5$)
• $k_2^2 = k_3^3 = k_4^4$ (the remaining factor)

Note that for each prime factor, we have one degree of freedom. We can use modular arithmetic to figure out what values that any one particular variable can take; we simply choose any of them, which will propagate to the rest. In this case, we happen to select $m_{2,2} = 5, m_{3,2} = 3, m_{4,2} = 2$ and $m_{2,5} = 7, m_{3,5} = 5, m_{4,5} = 3$ as the smallest solution. Also, we can simply choose $k_i = 1$ that satisfies everything; we can in fact choose $k_i = a^{k!/i}$ for any $a$, as given in my previous comment to give infinitely many solutions.

(Yes, I'm still not that good in LaTeX. Someone can fix up the aligning?)

- 5 years, 3 months ago

Really nice analysis!

- 5 years, 3 months ago

Thanks for your analysis, I recently had seen this video on Numberphile and ended up thinking about this problem. Since as mentioned in that video you can not represent numbers of form 9k+4 or 9k+5 as sum of 3 cubes, I was thinking whether there is some way we can narrow down solution set for my problem for higher values of n, by eliminating such numbers which are not possible.

- 5 years, 3 months ago

Because the notation is so awful, let me rephrase it: $F_k$ is the set of positive integers that can be represented as $a_1^k + a_2^k + a_3^k + \ldots + a_k^k$ where $a_1, a_2, a_3, \ldots, a_k$ are positive integers. The conjecture is thus $F_2 \cap F_3 \cap F_4 \cap \ldots \cap F_k$ is infinite for any positive integer $k$.

The easier part is that if said intersection is non-empty, then it is infinite. If $n \in F_2 \cap \ldots \cap F_k$, then $a^{k!}n \in F_2 \cap \ldots F_k$ for all positive integer $a$, because if $n = a_1^i + a_2^i + \ldots + a_i^i$ then $a^{k!}n = (a^{k!/i}a_1)^i + (a^{k!/i}a_2)^i + \ldots + (a^{k!/i}a_i)^i$. Thus now the problem is reduced to proving that said intersection is non-empty.

- 5 years, 3 months ago

Thanks, I am not good with notations. That's why I had given examples to make it more clear. Nice rephrasing but I fail to understand how proving non-empty set would help in proving infinitely many solutions. I mean even if there is a single solution, the set would be non-empty, right? I may be missing something. May be a stupid question.

- 5 years, 3 months ago

I've shown how to generate infinitely many solutions from a single solution. Thus if we can find any one solution, we can use my method to generate infinitely many solutions from that. This is similar to, for example, we have the Pythagorean triple $(3,4,5)$ and we can generate infinitely many from that: $(6,8,10), (9,12,15), (12,16,20), \ldots$.

- 5 years, 3 months ago

Vikram, this sounds like the kind of problem which proof you've written down somewhere in the margin of a book, right? This is similar to, but unfortunately too different from, Waring's Problem.

- 5 years, 3 months ago

Nice to see you here. Sorry for such a delayed response as I was bit busy. I recently had seen this video on Numberphile and ended up thinking about this problem. I liked that subtle reference to Fermat :)

- 5 years, 3 months ago

I think it's safe to say that if we modified your conjecture to include the condition that all of the numbers had to be different (like your posted problem related to this), this becomes a much more difficult feat to prove.

- 5 years, 3 months ago

Depending on which numbers that are different, my work above might still hold. If you only require numbers that make up a single expression to be different (like $1,9,22$ making up $1^3+9^3+22^3$ and $1,3,6,10$ making up $1^4+3^4+6^4+10^4$ to be different), but numbers between expressions to be allowed to be equal ($1$ is shared between them), simply modify the definition of $F_i$ appropriately (so that it contains numbers that are the sum of $i$ distinct positive $i$-th powers). If you don't even allow numbers between expressions to be equal, that becomes more difficult.

EDIT: Actually, no, it's not much more difficult. Multiply the number with a big $a^{k!}$ number. For example, for the solution $11378$ above, multiply it by $2^{24}$. The expressions are now $(2^8)^3 + (9 \cdot 2^8)^3 + (22 \cdot 2^8)^3$ and $(2^6)^4 + (3 \cdot 2^6)^4 + (6 \cdot 2^6)^4 + (10 \cdot 2^6)^4$; the $1$s are no longer equal.

- 5 years, 3 months ago

Okay, I gotta tip my hat to your response to this one. Have you tried solving Pandya's posted problem related to this one? I think I'll try using your technique to solving this one.

- 5 years, 3 months ago

I agree, with the condition that all the numbers must be distinct positive integers, this problem becomes insane. That's the reason I filed that other question under Computer Science but this under number theory.

- 5 years, 3 months ago

Nope, I don't agree; I already stated how to fix through that condition above.

On the other hand, finding the smallest solution is almost always a CS problem. Most constructions in math aren't specifically engineered to find the smallest solution.

- 5 years, 3 months ago

Sorry, I had missed your earlier comment. So let's see how can we tackle this problem in its reduced form. Thanks again for your analysis.

- 5 years, 3 months ago