Is the nth-power-sum graph connected?

Question

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

Answer 1

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.

Answer 2

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.