Saturday, April 4, 2009

26

Yesterday, a friend of mine turned 26. I know what you're thinking, this is very exciting. Indeed, not every year your age is between a square (5^2) and a cube (3^3)!

How often does this happen? Well actually, Wikipedia states that 26 is the only number between a square and a cube (which is not exactly true, but read on). I thought this was cool, let my friend know in a creepy happy birthday e-mail and got back to work.

But the same day, I was dragged to a Polish club by friends. It was horrible: the music was awful, absolutely nobody was dancing, nobody was talking and nothing happened. I was very bored, so I started working on the demonstration that 26 was the only number between a square and a cube. Excluding the fact that the bouncer seemed worried that I was standing still (and alone, remember) on the dance floor, it was the perfect activity to have in this club.
I first thought it would be easy, but as it turned out the demonstration ended up involving quadratic integer rings and unique factorization domains.

So let's start by demonstrating that 26 is the only number preceded by a square and succeeded by a cube. We want to find all integers a and b such as b^3=a^2+2.
You can easily prove that a and b are odd: if b is even, 2 divides a^2, so 2 divides a and 4 divides a^2. Consequently, 4 divides b^3 - a^2 so 4 divides 2. Impossible. So b is odd, which implies a^2 is odd and a is odd.

Then, my first intuition was to use the known solution to this equation to prove there was no other solution. a^2-5^2=b^3-3^3, so (a-5)(a+5)=(b-3)(b^2+3b+9). But this is tedious, there isn't much you can do with this annoying (b^2+3b+9).
Well this is as far as I've got in the club. I attempted to make others in the club party one more time and then decided to head home and started working on the proof again. Sad Friday night.

When I was in college, I really liked the kind of demonstrations where we used a superset of a given set to prove properties in the first set. Here, we see b^3=a^2+2 and feel hopeless. If only a^2+2 could be factorized... Well, it can be factorized. I didn't spend my youth learning about Cauchy sequences and how to construct R and his algebraic closure C for nothing! So let s be i*sqrt(2) and we have b^3=(a-s)(a+s). But what can we do now ?
I wanted to play with prime numbers, divisors and gcds and now we're stuck with complex numbers. Hold on! It turns out that the set of numbers written in the form x+y*s (with x and y integers), written Z[s] with the usual operations is not only a ring (called a quadratic integer ring), but also an Euclidian domain and that its units are 1 and -1 (proof of this another time). We can still have some fun (for some definitions of fun, including any that would qualify the aforementioned Polish club as fun).

So we now have (a-s)(a+s)=b^3. Let's prove that a-s and a+s are mutually prime. Let g be their gcd. g must divide (a+s) - (a-s) = 2s = -s^3. s is prime in Z[s], so g=+- s^x with x being 0, 1, 2 or 3. But g also divides a+s, if x>0, then s divides a+s and so s divides a. But we already know (from the club, remember), that a is odd. And s (i*sqrt(2)) cannot divide an odd number in Z[s]. So x=0 and a-s and a+s are mutually prime.

Since Z[s] is an Euclidian domain, the fundamental theorem of arithmetic holds (Z[s] is a unique factorization domain): any number in Z[s] can be written as the product of the elements of a unique set of prime numbers (and units). So we can write a-s, a+s and b^3 as products of prime numbers (and units). Since a-s and a+s are mutually prime, a-s and a+s are cubes multiplied by some units. Since 1 and -1 are both cubes, and the only units of Z[s], a-s and a+s are cubes.

So let's write a+s=(m+ns)^3 with m and n integers. We get: a+s=m^3-6mn^2+n*(3m^2-2n^2)s. The unicity of m' and n' such as x = m'+n'*s in Z[s] (with m' and n' in Z) gives: n*(3m^2-2n^2)=1. So n=+-1. If n = 1, we have 3m^2-2=1 and m = +-1. If n =-1 there is no solution for m. So n=1 and m = +-1. We also have a=m^3-6mn^2. So a = 5 or a = -5 wich in turn gives b=3.

So the only integer solutions to b^3=a^2+2 are (a,b)=(5,3) and (a,b)=(-5,3) and 26 is the only integer preceded by a square and followed by a cube.
Happy birthday Parisa!

Now what about an integer being preceded by a cube and followed by a square? If Wikipedia is right there is no integer solution to b^3=a^2-2. Well there is actually one trivial solution (b=-1 and a=+-1), so Wikipedia is wrong, but is it the only solution? We could be tempted to follow a similar approach, let s' be sqrt(2) and use Z[s'], which is also a ring. But -1 and 1 are not the only units: s-1 and s+1 are also units since (s'-1)(s'+1)=1 and so we have an infinite number of units written +-(s'-1)^m and +-(s'+1)^m.
Moreover, is Z[s'] still a unique factorization domain ? Not sure. But you may have to find out if you want to prove 0 is the only number preceded by a cube and followed by a square (for example to celebrate your 0-aged new born baby).

9 comments:

  1. Thank you Julien, I hadn't fully appreciated how exciting an age 26 really is -- and I have never gotten a proof as a birthday gift before!

    ReplyDelete
  2. The following Python script will demonstrate that 26 is the only age within human lifespan boundaries that verifies both conditions.

    ----------------------
    from math import *

    for age in range(1,150):
    if ((modf((age-1)**(1.0/2))[0] == 0.0) and (modf((age+1)**(1.0/3))[0] == 0.0)):
    print "Age %d is ok" % age
    ----------------------

    But it does not impress girls as much as you do ;)

    ReplyDelete
  3. Doesn't prove anything as float is an approximation.

    And you should work with unix timestamps !

    ReplyDelete
  4. As an impartial anonymous internet user, I must admit that the following ruby snippet is much nicer:

    200.times { |a| 200.times { |b|
    d = a*a-b*b*b
    puts a*a-d/2 if d.abs == 2
    } }

    > 26

    ReplyDelete
  5. But your algorithm makes n squared computations jj. Despite not working because of this awesome grammatical "feature" of Python that is tabulation, newsoft's version will be faster.

    This is going to matter for unix timestamps :)

    ReplyDelete
  6. @bartavelle: I am not sure you can run into rounding issues with numbers so small. But feel free to use Python's Decimal package for best results.

    ReplyDelete
  7. Thank you for your birthday present;)

    ReplyDelete
  8. Actually, one can prove that (±1,-1) is the only solution to b^3=a^2-2, by finding integer points on an elliptic curve.

    ReplyDelete