Sum of k-powers and divisibility

[Bibubo]

Let $a_{1},\dots,a_{n},\, n>2$ positive and distinct integer. Prove that the set of primes divisors of the numbers $$a_{1}^{k}+\dots+a_{n}^{k}$$with $k\in\mathbb{N}$ is infinite.

 

[mathbalarka]

Any integer has only a finite number of prime divisors. Do you mean to say that the set $S$ consisting of prime factors of numbers _of the form_ $\sum a_i^k$ is infinite? That is pretty easy to prove : there are infinitely many primes of the form $x^2 + y^2$ by Fermat so a subset of $S$ is (countably, of course) infinite, thus all of $S$ is infinite.

 

[Nono713]

Any integer has only a finite number of prime divisors. Do you mean to say that the set $S$ consisting of prime factors of numbers _of the form_ $\sum a_i^k$ is infinite? That is pretty easy to prove : there are infinitely many primes of the form $x^2 + y^2$ by Fermat so a subset of $S$ is (countably, of course) infinite, thus all of $S$ is infinite.

It looks like he wants to show that for every finite set of integers $\{ a_1, a_2, \cdots, a_n \}$, for $n > 2$, the set of prime factors of the elements of the set:
$$\left \{ \sum_{i = 1}^n a_i^k \mid k \in \mathbb{N} \right \}$$
is infinite.

 

[mathbalarka]

Ah, that makes the problem seemingly nontrivial. Interesting.

Bibubo, where did you get this problem?

 

[Bibubo]

Ah, that makes the problem seemingly nontrivial. Interesting.

Bibubo, where did you get this problem?

A friend of mine proposed to me this problem some days ago.

 

[Nono713]

Well, it looks like a clever choice of values of $k$ to ensure divisibility by a particular sequence of primes might perhaps work, but I have nothing in mind at the moment. In the meantime, here is at least a heuristic argument for even $n$. Take any sequence of primes all larger than all $a_i$, and choose $k_p = (p - 1) / 2$. Then we have:
$$\sum_{i = 1}^n a_i^{k_p} \equiv \sum_{i = 1}^n r_p(a_i) \pmod{p}$$
Where $r_p(a_i)$ is the quadratic character of $a_i$ mod $p$ and is equal to $1$ if $a_i$ is a quadratic residue, $-1$ if $a_i$ a quadratic nonresidue, and $0$ if $p$ divides $a_i$ (not applicable here as $0 < a_i < p$). There is evidence that $r_p(a)$ for $a \in \left ( \mathbb{Z}_p \right )^*$ behaves essentially like a random variable and all we need is that in our set $\{ a_1, a_2, \cdots a_n \}$, half of the $a_i$ be quadratic residues and the other half be quadratic nonresidues. Hence via the binomial distribution this should occur with probability:
$$P = \binom{n}{n/2} \left ( \frac{1}{2} \right )^n$$
For instance $P = 0.375$ for $n = 4$, and $P \approx 0.23$ for $n = 12$. And we will then have:
$$\sum_{i = 1}^n a_i^{k_p} \equiv \sum_{i = 1}^n r_p(a_i) \equiv 0 \pmod{p} ~ ~ \implies ~ ~ p ~ \text{divides} ~ \sum_{i = 1}^n a_i^{k_p}$$
So we can just keep selecting larger and larger primes until that holds, and hence it follows that at least a subset of your $k$-powers should be multiples of arbitrarily large primes, and so there should be infinitely many primes in your set. But I am not happy with this because besides being heuristic, it doesn't work at all for odd $n$, so this is probably not the right way to go about the problem.​

 

[Bibubo]

Well, it looks like a clever choice of values of $k$ to ensure divisibility by a particular sequence of primes might perhaps work, but I have nothing in mind at the moment. In the meantime, here is at least a heuristic argument for even $n$. Take any sequence of primes all larger than all $a_i$, and choose $k_p = (p - 1) / 2$. Then we have:
$$\sum_{i = 1}^n a_i^{k_p} \equiv \sum_{i = 1}^n r_p(a_i) \pmod{p}$$
Where $r_p(a_i)$ is the quadratic character of $a_i$ mod $p$ and is equal to $1$ if $a_i$ is a quadratic residue, $-1$ if $a_i$ a quadratic nonresidue, and $0$ if $p$ divides $a_i$ (not applicable here as $0 < a_i < p$). There is evidence that $r_p(a)$ for $a \in \left ( \mathbb{Z}_p \right )^*$ behaves essentially like a random variable and all we need is that in our set $\{ a_1, a_2, \cdots a_n \}$, half of the $a_i$ be quadratic residues and the other half be quadratic nonresidues. Hence via the binomial distribution this should occur with probability:
$$P = \binom{n}{n/2} \left ( \frac{1}{2} \right )^n$$
For instance $P = 0.375$ for $n = 4$, and $P \approx 0.23$ for $n = 12$. And we will then have:
$$\sum_{i = 1}^n a_i^{k_p} \equiv \sum_{i = 1}^n r_p(a_i) \equiv 0 \pmod{p} ~ ~ \implies ~ ~ p ~ \text{divides} ~ \sum_{i = 1}^n a_i^{k_p}$$
So we can just keep selecting larger and larger primes until that holds, and hence it follows that at least a subset of your $k$-powers should be multiples of arbitrarily large primes, and so there should be infinitely many primes in your set. But I am not happy with this because besides being heuristic, it doesn't work at all for odd $n$, so this is probably not the right way to go about the problem.​

I think I get a solution, but I'm not sure. Suppose for absurd that $$\left\{ p\, primes:\, p\mid\underset{i=1}{\overset{n}{\sum}}a_{i}^{k},\, k\in\mathbb{N}\right\} =\left\{ p_{1},\dots,p_{r}\right\}.$$Let $a_{1}+\dots+a_{n}=c$ and let $b_{i}$ the order of $c$ as a element of $\mathbb{Z}/p_{i}\mathbb{Z}.$ Now take $$k=p_{1}\cdots p_{r}b_{1}\cdots b_{r}$$then we have $$\overset{n}{\underset{i=1}{\sum}}a_{i}^{k}\equiv\left(\overset{n}{\underset{i=1}{\sum}}a_{i}\right)^{k}=\left(\left(\overset{n}{\underset{i=1}{\sum}}a_{i}\right)^{b_{1}}\right)^{p_{1}\cdots p_{r}b_{2}\cdots b_{r}}\equiv1\,\textrm{mod}\, p_{1}$$where the first congruence is for the "freshman's dream" (in this case we have char=$p_{1}$).We can repeat the same argument for every $p_{i}$ and so nobody of the $p_{i}$ divides that sum, which is a contradiction. Is it wrong? Note that I haven't information about $p_{i}$ (they can be greater than $c$ or smaller, they can divide $c$ or not). So I can't show explicit the value of $b_{i}$. Am I wrong? Thank you.

 

[Nono713]

I think I get a solution, but I'm not sure. Suppose for absurd that $$\left\{ p\, primes:\, p\mid\underset{i=1}{\overset{n}{\sum}}a_{i}^{k},\, k\in\mathbb{N}\right\} =\left\{ p_{1},\dots,p_{r}\right\}.$$Let $a_{1}+\dots+a_{n}=c$ and let $b_{i}$ the order of $c$ as a element of $\mathbb{Z}/p_{i}\mathbb{Z}.$ Now take $$k=p_{1}\cdots p_{r}b_{1}\cdots b_{r}$$then we have $$\overset{n}{\underset{i=1}{\sum}}a_{i}^{k}\equiv\left(\overset{n}{\underset{i=1}{\sum}}a_{i}\right)^{k}=\left(\left(\overset{n}{\underset{i=1}{\sum}}a_{i}\right)^{b_{1}}\right)^{p_{1}\cdots p_{r}b_{2}\cdots b_{r}}\equiv1\,\textrm{mod}\, p_{1}$$where the first congruence is for the "freshman's dream" (in this case we have char=$p_{1}$).We can repeat the same argument for every $p_{i}$ and so nobody of the $p_{i}$ divides that sum, which is a contradiction. Is it wrong? Note that I haven't information about $p_{i}$ (they can be greater than $c$ or smaller, they can divide $c$ or not). So I can't show explicit the value of $b_{i}$. Am I wrong? Thank you.

I believe that doesn't quite work. Note that if we set $k = 1$ then there is at least one $p_i \mid \sum a_i$, such that $p_i$ divides $c$. So $c \equiv 0 \pmod{p_i}$ so $\sum a_i^k \equiv 0 \pmod{p_i}$ for any $k$ multiple of $p_1$ in that case. So the congruence for $p_i$ doesn't really hold for that $k$.

As an example, take $a = (2, 3, 6)$ and consider $k = 1, 2, 3$. We get:
$$2 + 3 + 6 = 11$$
$$2^2 + 3^2 + 6^2 = 49 = 7^2$$
$$2^3 + 3^3 + 6^3 = 216 = 2 \times 11 \times 13$$
So our set of primes here is $\{ 2, 7, 11, 13 \}$. Your proof claims that we can always find a larger $k$ which is not divisible by any of the primes in this set (and hence the set was not in fact complete, showing it must be infinite). Your proof proceeds by taking $c = 2 + 3 + 6 = 11$, and then computing multiplicative orders of $c$ modulo $2, 7, 11, 13$. But $c$ has no order modulo 11! Even if we redefine $b_i$ as something sensible like $p_i - 1$ (since $b_i$ must divide $p_1 - 1$ by Lagrange's theorem) your congruence fails for 11, and in fact $11$ will divide $\sum a_i^k$ for any $k$ divisible by 11.

So the congruence does not hold for all primes in the set, and so it does not follow that $\sum a_i^k$ for such $k$ must be divisible by a prime not in the set.

I like your approach though. It might be possible to modify it so that it does work!

 

[Bibubo]

I believe that doesn't quite work. Note that if we set $k = 1$ then there is at least one $p_i \mid \sum a_i$, such that $p_i$ divides $c$. So $c \equiv 0 \pmod{p_i}$ so $\sum a_i^k \equiv 0 \pmod{p_i}$ for any $k$ multiple of $p_1$ in that case. So the congruence for $p_i$ doesn't really hold for that $k$.

As an example, take $a = (2, 3, 6)$ and consider $k = 1, 2, 3$. We get:
$$2 + 3 + 6 = 11$$
$$2^2 + 3^2 + 6^2 = 49 = 7^2$$
$$2^3 + 3^3 + 6^3 = 216 = 2 \times 11 \times 13$$
So our set of primes here is $\{ 2, 7, 11, 13 \}$. Your proof claims that we can always find a larger $k$ which is not divisible by any of the primes in this set (and hence the set was not in fact complete, showing it must be infinite). Your proof proceeds by taking $c = 2 + 3 + 6 = 11$, and then computing multiplicative orders of $c$ modulo $2, 7, 11, 13$. But $c$ has no order modulo 11! Even if we redefine $b_i$ as something sensible like $p_i - 1$ (since $b_i$ must divide $p_1 - 1$ by Lagrange's theorem) your congruence fails for 11, and in fact $11$ will divide $\sum a_i^k$ for any $k$ divisible by 11.

So the congruence does not hold for all primes in the set, and so it does not follow that $\sum a_i^k$ for such $k$ must be divisible by a prime not in the set.

I like your approach though. It might be possible to modify it so that it does work!

Thank you so much for your observations! I will try to fix these errors.