6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Jan 12 '18 at 5:32
  • $\begingroup$ @GerhardPaseman: Waring's theorem should be used, but I don't understand your argument. $\endgroup$ – Sebastien Palcoux Jan 12 '18 at 16:00
  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Jan 12 '18 at 16:10
  • $\begingroup$ @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. $\endgroup$ – Sebastien Palcoux Jan 12 '18 at 21:54
  • $\begingroup$ @GHfromMO: David Eppstein's solution is clear for $\mathbb{Z}$, but unclear for $\mathbb{N}^*$ (at least for me). $\endgroup$ – Sebastien Palcoux Jan 14 '18 at 18:05
6
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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)$. $\endgroup$ – Sebastien Palcoux Jan 12 '18 at 23:10
  • $\begingroup$ This post is a good complementary to your answer. The modulus of the arithmetic progression is $n!$. $\endgroup$ – Sebastien Palcoux Jan 13 '18 at 20:52
  • $\begingroup$ 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? $\endgroup$ – Sebastien Palcoux Jan 13 '18 at 23:08
  • 1
    $\begingroup$ @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. $\endgroup$ – Sebastien Palcoux Jan 14 '18 at 18:20
  • 3
    $\begingroup$ 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. $\endgroup$ – David Eppstein Jan 15 '18 at 19:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.