This post was inspired by the [Square-Sum Problem](https://youtu.be/G1m7goLCJDY) 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:
                G.add_edge(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`.



Is the nth-power-sum graph connected?
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](http://www.digizeitschriften.de/dms/img/?PID=GDZPPN002375354) 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.


