# Is the nth-power-sum graph connected?

This post was inspired by the Square-Sum Problem presented in Numberphile by Matt Parker.
He asked about Hamiltonianness for $n=2$, and we ask about connectedness for all $n \in \mathbb{N}^*$.

Given $n \in \mathbb{N}^*$, let $\mathcal{G}_n$ be the graph $(\mathbb{N}^*,\{ \{a,b\} \ | \ a+b \in S_n\})$, with $S_n = \{r^n | r\in \mathbb{N} \}$ .

Question: Is $\mathcal{G}_n$ connected?

Checking: It is true for $n \le 5$.
Proof: For any $a \in \mathbb{N}^*$, there is $r\in \mathbb{N}$ such that $r^n \le a < (r+1)^n$. Then, $\{a,(r+1)^n-a\}$ is an edge of $\mathcal{G}_n$. Now, $(r+1)^n-a<a$ iff $(r+1)^n<2a$, which occurs if $(a^{1/n}+1)^n < 2a$. Below the table for $a_n$, the greatest $a \in \mathbb{N}^*$ such that $(a^{1/n}+1)^n \ge 2a$, for $n \le 5$:
$$\begin{array}{c|c} n&1&2&3&4&5 \newline \hline a_n&1&5&56&780&13755 \end{array}$$ It follows that as long as $a>a_n$, there is $b<a$ such that $\{a,b\}$ is an edge of $\mathcal{G}_n$. So we are reduced to prove that the set of vertices $\{ 1,2, \dots,a_n \}$ is covered by a connected component.
For so, we wrote the following SAGE program:

cpdef PowerSumGraph(int a, int s, int n):
cdef int i,j,r,t
G=Graph({})
for i in range(1,a):
r=i**(1/n)
for j in range(r,s):
t=j**n-i
if t>0 and i<>t:
return G.is_connected()


The result follows by the (minimal) computation below. $\square$

sage: PowerSumGraph(13,6,2)
True
sage: PowerSumGraph(108,7,3)
True
sage: PowerSumGraph(2008,9,4)
True
sage: PowerSumGraph(49355,11,5)
True


The case $n=6$ works also, by the following (non-minimal) computation and $a_6 = 296476$.

sage: PowerSumGraph(1500000,13,6)
True


The case $n=7$ is beyond my laptop capacity. For $n \ge 8$, the program should be modified because it would deal with integers beyond $2^{31}-1$, the maximum value for variables declared as int.

• I believe this is true by Waring's theorem. For a given a and b, pick c (and d and f and ... if needed) really big so that a+b +c^n (+ ...) is the sum of distinct nth powers. Then you rewrite to get an alternating sum of powers with c^n - d^n + a = ... - b. Indeed, there may be an upper bound to the diameter. Gerhard "Not Quite Algebraic Graph Theory" Paseman, 2018.01.11. – Gerhard Paseman Jan 12 '18 at 5:32
• @GerhardPaseman: Waring's theorem should be used, but I don't understand your argument. – Sebastien Palcoux Jan 12 '18 at 16:00
• It is a little more challenging than I first thought. If things are nice, we can find two disjoint monotone sequences of possibly differing lengths so that (c^n -(d^n - ... -a))...) = x^n -(y^ - ... -b))..), which we rewrite as two sums of nth powers and a and b. We can choose half of the powers, get the other half as a distinct sum, and then start weaving them together. Of course the weaving part is left to the reader. Gerhard "This Is Numerical CrochetOverflow, Right?" Paseman, 2018.01.12. – Gerhard Paseman Jan 12 '18 at 16:10
• @GerhardPaseman: I got the idea, but we could have issues for providing a detailed proof, due to the fact that we deal with positive integers. – Sebastien Palcoux Jan 12 '18 at 21:54
• @GHfromMO: David Eppstein's solution is clear for $\mathbb{Z}$, but unclear for $\mathbb{N}^*$ (at least for me). – Sebastien Palcoux Jan 14 '18 at 18:05

Yes, the graph $\mathcal{G}_n$ is connected, and its diameter is at most $n2^n$. To see this, write $s$ for $n2^{n-1}$, and fix any two vertices $a,b\in\mathbb{N}^*$. By Wright's solution of Waring's problem with proportionality conditions, for a large parameter $c\in\mathbb{N}$, we can find $x_1,\dots x_s\in\mathbb{N}^*$ and $y_1,\dots y_s\in\mathbb{N}^*$ such that $$x_1^n+\dots+x_s^n=c+a\qquad\text{and}\qquad y_1^n+\dots+y_s^n=c+b,$$ moreover the summands are asymptotically (as $c$ tends to infinity) $$x_1^n,y_s^n\sim\frac{c}{2s-1}\qquad\text{and}\qquad x_2^n,\dots,x_s^n,y_1^n,\dots,y_{s-1}^n\sim\frac{2c}{2s-1}.$$ As a consequence, the following walk of length $2s$ connects $a$ and $b$: $$a\ \rightarrow\ x_1^n-a\ \rightarrow\ -x_1^n+y_1^n+a\ \rightarrow\ x_1^n-y_1^n+x_2^n-a\ \rightarrow\ \cdots\ \rightarrow\ b.$$ Note that the edge sums in this walk are $x_1^n,y_1^n,\dots,x_s^n,y_s^n$, while each intermediate vertex is asymptotically $c/(2s-1)$, hence a positive integer for $c$ sufficiently large. The proof is complete.

By going from $x$ to $a^n-x$ to $b^n-(a^n-x)$ we can, in two steps, add or subtract any difference of $n$th powers. In four steps, we can add or subtract any difference of differences (a second-order difference). And, repeating this idea, in $2^{n-1}$ steps, we can add or subtract any $(n-1)$th order difference. But the $(n-1)$th order differences of a sequence of $n$th powers are an arithmetic progression, so in this many steps we can reach from any initial $x$ the value $x$ mod $m$, where $m$ is the modulus of the arithmetic progression. That is, $\mathcal{G}_n$ has at most finitely many connected components.

To show that there is only one component, we need to show how to go from any value modulo $m$ to any other value modulo $m$. But this can be done, again, by going from $x$ to $a^n-x$ to $b^n-(a^n-x)$, where $a=m$ and $b=m+1$.

This shows, more strongly, that $\mathcal{G}_n$ has bounded diameter. I don't know how close to optimal is the exponential bound given by this argument.

• A diameter $\mathcal{O}(n\log{}n)$ should follow from the argument of Gerhard Paseman above (assuming it works in details) with Hilbert–Waring theorem and the bound of what the wiki page calls $G(n)$. – Sebastien Palcoux Jan 12 '18 at 23:10
• This post is a good complementary to your answer. The modulus of the arithmetic progression is $n!$. – Sebastien Palcoux Jan 13 '18 at 20:52
• There is a gap in your argument. The set of vertices is $\mathbb{N}^*$, so how do you justify the existence of a path from $x$ to $x$ mod $m$ such that each step produces a positive integer? – Sebastien Palcoux Jan 13 '18 at 23:08
• @GHfromMO: yes of course I saw your post. My problem with David Eppstein's answer is that I don't know if the gap is in my understanding or in his argument. – Sebastien Palcoux Jan 14 '18 at 18:20
• Given that the other answer is more complete and this does need more details I don't see any reason to object to accepting the other one. – David Eppstein Jan 15 '18 at 19:04