*x*

^{n}

where both

*x*and

*n*are natural numbers. Can we say, which numbers can be expressed as perfect powers? If we don't further restrict

*n*then the answer is simple. Any number

*x*can be represented as

*x*

^{1}. So that means the set of numbers that can be represented as perfect powers is the complete set . So this question is boring.

But what if we exclude these trivial powers and say that n must be greater than 1? The list of these numbers is the sequence A001597 in OEIS. On the right is a plot of the first 100 of these numbers

*a*

_{n}. As you can see, the numbers seem to grow more than linearly. In fact for large numbers they seem to grow with

*n*

^{2}. This seems to suggest that the gaps between two consecutive numbers also needs to grow. This is intuitively right. As the numbers grow, there are less and less candidates that could produce perfect powets.

But how large are the gaps exactly? More interestingly, as the gaps grow larger, do we still encounter some small gaps? The plot on the left shows the differences

*g*

_{n}between two consecutive elements of the sequence plotted against the smaller number for the first 1000 or so numbers

*g*

_{n}=

*a*

_{n + 1}−

*a*

_{n},

i.e. we're plotting

*g*

_{n}against

*a*

_{n}. It can be seen that most of the

*g*

_{n}seem to lie close to a curve given by

which also limits the

*g*

_{n}. This simple form is amazing at first, however it becomes quite clear when one looks at just the square numbers

*x*

^{2}. If

*a*

_{n}is a square number then is also a perfect square. The difference between the two numbers is . Only few numbers seem to depart from this behaviour and have a lot smaller values. This always happens when there is at least perfect power, that is not a square, between two perfect squares.

So we have an upper bound for the

*g*

_{n}. But is there a lower bound for the

*g*

_{n}that increases with

*n*. Or does

*g*

_{n}always have excursions to small numbers? Let's look first at the smallest possible value

*g*

_{n}= 1.

Catalan's theorem makes a statement about this particular case. It says that there is only one

*n*for which

*g*

_{n}= 1, or in the full notation

*x*

^{n}−

*y*

^{m}= 1 has only one solution, which is 3

^{2}− 2

^{3}= 1

Until 2002 this was Catalan's conjecture but then it was proven by Preda Mihăilescu. Long before this proof Pillai generalised the the Catalan conjecture and speculated about the solutions of the equation

*x*

^{n}−

*y*

^{m}=

*c*for

*c*> 1

The graph above seems to suggest that for

*c*= 2 there is also just one solution

3

^{3}− 5

^{2}= 2

but to my knowledge this has not been proven. Pillai's conjecture now states that for any value of c, the above equation only has a finite number of solutions. This means that the gaps in the sequence of perfect powers not only grow, but there is some increasing lower bound for the gaps as well. Erdos went one step further and conjectured that this lower bound is given by

*g*

_{n}<

*n*

^{k}

where

*k*is a fixed constant which is greater than one.

From the plot of the first million gaps this does not immediately seem obvious. The figure shows the plot of the gaps

*g*

_{n}against

*n*for

*n*up to 10

^{6}on a double-logarithmic scale. Although the lower bound does seem to grow, the value of the parameter

*k*of the Erdos formula, of roughly 0.22 (green line), is determined by a single outlier at

*a*

_{384026}= 143384152921 and

*g*

_{384026}= 17. Almaost all other values of

*g*

_{n}lie well above the Erdos curve. Only one other point comes close to the limiting curve at

*g*

_{745174}= 24

One more interesting feature that can be seen are strange lines in the plot that slope at a slightly lower exponent of about 2 / 3. This suggests that there is some hidden structure in the seemingly random behaviour of the

*g*

_{n}. Another feature, which I noticed when plotting the

*g*

_{n}is that there seem to be islands of regularity.

If we zoom in to the region from to we get the following plot. Most points are again crowded around the upper limit but the others have the very regular shape of two parabolas intersecting each other.

As you can see, even formulas that seem simple can have surprisingly rich behaviour and open up very difficult problems.

## No comments:

## Post a Comment