Deep thought required

The integer 10 can be written as the sum of three cubes: 10=2^3+1^3+1^3. So can 6, although that isn’t obvious until you think of using negative integers: 6 = 2^3+(-1)^3+(-1)^3. For that matter, there are easy solutions to the problem of finding such sums of three cubes for every integer up to 10 except for 4 and 5:

  • 0 = 0^3+0^3+0^3
  • 1 = 1^3+0^3+0^3
  • 2 = 1^3+1^3+0^3
  • 3 = 1^3+1^3+1^3
  • 4 = ???
  • 5 = ???
  • 6 = 2^3+(-1)^3+(-1)^3
  • 7 = 2^3+(-1)^3+0^3
  • 8 = 2^3+0^3+0^3
  • 9 = 2^3+1^3+0^3
  • 10 = 2^3+1^3+1^3

That prompts a few questions: Are there solutions for 4 and 5? Are there solutions for all integers? Or for an infinite number of integers?

The answers to the first two questions are, no and no. Start by observing that the cube of any multiple of 3, (3n)^3, is divisible by 9 (in fact 27). For numbers equal to 1 mod 3, (3n+1)^3 = 27n^3+27n^2+9n+1 so is equal to 1 mod 9, and for numbers equal to -1 mod 3, (3n-1)^3 = 27n^3-27n^2+9n-1 so is equal to -1 mod 9. So all cubes are equal to 0 or ±1 mod 9. From this you can figure out all sums of three cubes are equal to 0, 1, 2, or 3 mod 9. But 4 and 5 equal -4 and +4 mod 9. So they cannot be written as sums of three cubes; nor can 13, 14, 22, 23, 31, 32, ….

As for the third question, it’s conjectured all other integers can be expressed as sums of three cubes. But it’s not proved.

The integers up through 11 are easy. In fact you might realize 10 can be done another way: 10 = 4^3+(-3)^3+(-3)^3. For that matter, 8 = 2^3+1^3+(-1)^3 =  2^3+2^3+(-2)^3 and so on for an infinite number of solutions.

But 12 might take you a little longer: 12 = 10^3+7^3+(-11)^3. Worse, 21 = 16^3+(-11)^3+(-14)^3. Things are pretty easy up through 29, and then 30 is hard. Very hard.

Good luck coming up with the simplest known answer:

30 = 2220422932^3+(-283059965)^3+(-2218888517)^3.

Yikes!

So it goes. Lots of easy ones

53 = 3^3+3^3+(-1)^3

interspersed with slightly tougher ones

52 = 60702901317^3 + 23961292454^3 + (-61922712865)^3

But as of a few days ago, there were solutions known for all but two numbers less than 100 (other than the ±4 mod 9 impossibilities).

That was then. Andrew R. Booker has just published this result for the smallest hitherto-unsolved case:

8866128975287528^3 + (-8778405442862239)^3 + (-2736111468807040)^3

= 696950821015779435648178972565490929714876221952
-676467453392982277424361019810585360331722557919
-20483367622797158223817952754905569383153664000

= 696950821015779435648178972565490929714876221952
-696950821015779435648178972565490929714876221919

= 33

I hardly need add that this was not found with a Python script during Booker’s lunch hour. The paper goes into the number theoretic gymnastics involved in his computer search, which, he reports, “used approximately 15 core-years over three weeks of real time.”

So that’s 33 solved. We’re down to one remaining unsolved number under 100. And I’m ready to give it to you. Now.

Though I don’t think that you’re going to like it.

All right.

You’re really not going to like it.

All right. The smallest n \ne \pm4\mod 9 for which no expression as the sum of three cubes is known is…

is…

Forty-two.

Advertisements

2^n-gons

There’s nothing at all new about this, in fact it’s ancient, but maybe it’s new to you? So here goes.

Here’s a square inscribed in a unit circle:

Or to keep down the clutter, here’s just one quadrant of that:

One side of the square along with the radii at each endpoint forms a triangle. The length of one side of the square we’ll call s_4 and it is of course \sqrt 2. That means the perimeter of the square is p_4 = 4\sqrt 2\approx 5.656854249.

Now consider an inscribed octagon. Again, here’s just one quadrant.

One side of the square is labeled s_8; what’s its length? Well, drop a perpendicular from the vertex in the middle:

And now notice the right triangle with hypotenuse 1 and sides x_8 and h_8 is just half of a quadrant of an inscribed square, which means h_8=s_4/2. Then x_8^2 = 1-h_8^2 = 1-s_4^2/4. From that you can get y_8=1-x_8 and from that, s_8^2=h_8^2+y_8^2. The perimeter of the octagon is then p_8 = 8s_8\approx 6.122934918.

Well, that was so much fun, let’s do it again. Here’s a quadrant of a 16-gon:

The right triangle with hypotenuse 1 and sides x_{16} and h_{16} is just half of an eighth of an inscribed octagon, which means h_{16}=s_8/2. Then x_{16}^2 = 1-h_{16}^2 = 1-s_8^2/4, y_{16}=1-x_{16}, and s_{16}^2=h_{16}^2+y_{16}^2. The perimeter of the 16-gon is then p_{16} = 16s_{16}\approx 6.242890305.

You know the rest, right? From here you can do the 32-gon, 64-gon, 128-gon, and so on, getting x_{2n}^2 = 1-h_{2n}^2 = 1-s_n^2/4, y_{2n}=1-x_{2n}, s_{2n}^2=h_{2n}^2+y_{2n}^2, and perimeter = p_{2n} = 2ns_{2n}. For n = 1024, the perimeter is p_{1024}\approx 6.283175451 = 2\times 3.1415877255. As n increases, the perimeter gets closer and closer to the circumference of the circle, so this gives a way to calculate \pi.

What about circumscribed polygons? If you look at the figures above, you can see the ratio of the size of a circumscribed square to an inscribed square is 1/x_8. Likewise the ratio of the size of a circumscribed octagon to an inscribed octagon is 1/x_{16}, and so on. So the perimeter of a circumscribed n-gon is P_n = p_n/x_{2n}. As n increases, P_n approaches 2\pi from above. And the average of p_n and P_n is a better approximation to 2\pi than either, though not by a lot.

nh_nx_ny_ns_np_nP_naverage
41.414213565.656854258.000000006.82842712
80.707106780.707106780.292893220.765366866.122934926.627417006.37517596
160.382683430.923879530.076120470.390180646.242890306.365195766.30404303
320.195090320.980785280.019214720.196034286.273096986.303449816.28827340
640.098017140.995184730.004815270.098135356.280662316.288236776.28444954
1280.049067670.998795460.001204540.049082466.282554506.284447266.28350088
2560.024541230.999698820.000301180.024543086.283027606.283500746.28326417
5120.012271540.999924700.000075300.012271776.283145886.283264166.28320502
10240.006135880.999981180.000018820.006135916.283175456.283205026.28319024

This is something like the way Archimedes calculated \pi around 250 BC (I told you this was ancient), although he started with a hexagon rather than a square and only went up to a 96-gon. He didn’t have Google Sheets, though.

Power trip (part 2)

That proof that e^a>a^e for any positive a\ne e relies on \ln(e)=1, so doesn’t generalize to anything nearly as simple relating a^b to b^a. But let’s see what we can do.

Here’s an inequality which, if you’re like me, looks pretty mysterious:

\displaystyle b>\frac{b-a}{\ln(b/a)}>a for a and b>a positive real numbers.

I mean, the difference between a and b doesn’t “know” anything about a or b, right? And neither does their ratio. But the difference over the log of the ratio is always between a and b? Weird!

(Okay, maybe you’re not so easily impressed, since if you know b-a and b/a you can get a and b. Fine. I think it’s mysterious anyway.)

Well, let’s consider a function f(x) with derivative df(x)/dx = f'(x) monotonically decreasing (we could do increasing too, similarly). Let a and b>a be in the range where f(x) and f'(x) exist and f'(x)>0. Then

\displaystyle \int_a^b f'(x)dx = f(b)-f(a)

But that integral is the area under the curve from a to b and so

\displaystyle f'(a)(b-a)>f(b)-f(a)>f'(b)(b-a).

Then (b-a)>[f(b)-f(a)]/f'(a) and [f(b)-f(a)]/f'(b)> (b-a) or

\displaystyle \frac{f(b)-f(a)}{f'(b)}> (b-a)>\frac{f(b)-f(a)}{f'(a)}.

But that makes sense given the definition of the derivative and the monotonic property of f'(x); with a little thought you could’ve written this down directly. As obvious as it is, it takes a decidedly less obvious form if you specify f(x) = \ln(x), f'(x) = 1/x, which gives

\displaystyle b\ln(b/a)>(b-a)>a\ln(b/a)

or the formerly mysterious

\displaystyle b>\frac{b-a}{\ln(b/a)}>a QED.

I called the original post “Power trip” and this one “Power trip (part 2)”, and there haven’t been any powers here. Sorry. Here:

\displaystyle a\ln(b/a) < b-a < b\ln(b/a)

so

\displaystyle (b/a)^a < e^{b-a} < (b/a)^b.

That form is… neither obvious nor interesting, though. Unless a=e in which case the left part is

\displaystyle (b^e)/(e^e) < (e^b)/(e^e)

or

\displaystyle b^e<e^b

which is where we came in.

Power trip

Here’s a mathematical paper of which I can smugly say I understood every word.

Ha ha. No, seriously, I like it. A visual proof that e^\pi>\pi^e.

But as Math with Bad Drawings pointed out someone else pointed out, the proof doesn’t depend on \pi but can be generalized to any number > e, and as Math with Bad Drawings pointed out, a similar proof works for any positive number < e. That is, for all a > 0 and a\ne e, e^a>a^e.

Proof here if you don’t want to click through to MwBD:

 

If a > e,

\displaystyle \frac{1}{e}(a-e) = \frac{a}{e}-1 > \int_e^a \frac{1}{x}dx = \ln(a)-\ln(e) = \ln(a)-1

so

\displaystyle \frac{a}{e} > \ln(a)

or

\displaystyle a > \ln(a^e)

or

\displaystyle e^a > a^e

and similarly, if b < e,

\displaystyle \frac{1}{e}(e-b) = 1-\frac{b}{e} < \int_b^e \frac{1}{x}dx = \ln(e)-\ln(b) = 1-\ln(b)

so

\displaystyle \frac{b}{e} > \ln(b)

or

\displaystyle b > \ln(b^e)

or

\displaystyle e^b > b^e

QED

 

Three gaps, part 4

Okay, we’ve shown that when you generate a scale using an interval X, that scale has no more than three different gap sizes. Now let’s learn about the relationship between those sizes.

Let’s suppose we have three different gap sizes. For instance, the 8 note scale:Here the first note, the note we started with, is F, and the last note added is F♯. That means the Type I rigid gaps are FF♯ and F♯G (the yellow gap on the left, and the purple one immediately to its right, surrounding the last note). AB (the blue gap closest to the center) is a Type II rigid gap, because shifting it by X makes it coincide with EF♯, which isn’t a gap, it’s the two gaps surrounding the first note (EF and FF♯). Clearly that means the size of gap AB is the size of EF (which is the same as the size of rigid gap F♯G) plus the size of FF♯. So in this case the size of the largest gap is the sum of the sizes of the two smaller gaps.

But is that always true? Can you get a Type II gap that isn’t the same size as the sum of the gaps surrounding the first point? Or can you get a scale in which the two gaps surrounding the first point are both the size of one or the other of the Type I gaps?

Let’s try to look at all the possibilities. For the Type I (rigid) gaps:

  1. There are no Type I gaps
  2. There is only one Type I gap
  3. There are two Type I gaps, and they’re the same size
  4. There are two Type I gaps, and they’re different sizes

And for the Type II (rigid) gap:

  1. There is no Type II gap
  2. There is a Type II gap, and it is also a Type I gap
  3. There is a Type II gap, and it is not a Type I gap

Type I gaps surround the last note. If the gaps adjacent to the last note aren’t rigid, that means there’s a note X above the last note, which would have to be the first note, and the only way that can happen is if nX = 0 \mod 1200. That is, X has to be rational, of the form 1200m/n (in lowest terms). Then the n note scale divides the octave into n equal intervals, and we have a 1-gap scale. In that case there aren’t any Type II rigid gaps, either. Every gap coincides with a gap when shifted.

If there is no note X above the last note, then the gap to the left of the last note is rigid and so is the gap to the right, and there are two Type I gaps unless those two gaps are one and the same. In other words, it’s a one-note scale with one (one octave) gap. Which is a degenerate sort of equal division of the octave, so in fact there aren’t any rigid gaps. In other words, if it’s not an equal division of the octave (or a one-note scale), then there must be two distinct Type I gaps. They can be the same size, or not.

Now suppose there is no Type II gap. No gap contains the first note in its shifted interior. The only way that can happen is if there is a note X to the left of the first note, and that would have to be the last note. Again, this means it’s an equal division of the octave, and there are no Type I gaps either.

So suppose there is a Type II gap, but it is also a Type I gap. That is, one of its end notes is the last note. Then when shifted, that end will not coincide with a note. If the two Type I gaps are different sizes, then all we can say is we have a 2-gap scale, and there is no particular relationship between the two sizes.

Example: the 7 note scale:

Here gap AB (the blue gap closest to the center) is a Type II rigid gap: if you shift it, it goes from E to where F♯ would be if there were an F♯, and it contains F. It’s also one of the Type I rigid gaps, since B is the last note; the other is BC. So it’s a 2-gap scale.

If the Type II gap is also Type I, and the two Type I gaps are the same size, well… then obviously we have a 1-gap scale, which means an equal division of the octave, but that has no rigid gaps at all, so by contradiction that case is impossible.

Finally, suppose there is a Type II gap, and it is not a Type I gap. That means there’s a note X to the right of each of its end notes, so when you shift the gap it’ll coincide with two gaps, the two surrounding the first note. The Type II gap is the sum of the gaps surrounding the first note. One of the two gaps surrounding the first note has its “older” end note (namely the first note) on the right end, the other has the older note on the left end. If you shift the first of these as many times as you can, the “newer” note on the left end reaches the last note first, so this gap matches up with the Type I rigid gap in which the last note is on the left end. But if you shift the second one, the “newer” note on the right end reaches the last note first, so that gap matches up with the Type I rigid gap in which the last note is on the right end. So if the two Type I gaps are different sizes, then so are the two gaps surrounding the first note, and we have a 3-gap scale in which the Type II rigid gap is the same size as the sum of the sizes of the two Type I gaps.

The only way the two gaps surrounding the first note can be the same size is if both Type I gaps are the same size, in which case the Type II gap is exactly twice that size and it’s a 2-gap scale. That would happen, for instance, if instead of ~702 cents, X were 700 cents, and you generated an 8-note scale. It would look like the 8-note scale above, except the gaps surrounding the first note both would be 100 cents in size, and so would the gaps surrounding the last note.

Summing up:

  1. If there are no Type I gaps, there are no Type II gaps, and vice versa; we have a 1-gap scale
  2. If there is a Type II gap, and it is also a Type I gap, then the two Type I gaps are different sizes, and we have a 2-gap scale, with no particular relationship between the two sizes
  3. If there is a Type II gap, and it is not a Type I gap, and the Type I gaps are the same size, we have a 2-gap scale with the large gap twice the small gap
  4. If there is a Type II gap, and it is not a Type I gap, and the Type I gaps are not the same size, we have a 3-gap scale with the large gap the sum of the small gaps

So there you go. I’ve framed this discussion in terms of musical scales, putting notes within an octave, at positions ranging from 0 to 1200 cents, but of course this all could be restated in terms of putting points on a unit line segment, at positions from 0 to 1, or on a circle, at angular positions from 0 to 2π. The Wikipedia article says in the latter form it has applications to phyllotaxis, although I’m not sure it has anything significant to say in that field. The theorem also has applications in the theory of Sturmian words, it says, and if I ever come to grips with what Sturmian words are and why one would care, maybe I’ll write about them here… don’t hold your breath, though…

Three gaps, part 3

Let’s look at a proof of the three-gap theorem given by F. M. Liang and restated more clearly by Schiu [paywall].

Here’s the 6-note scale again:

We’re going to look for gaps that are “rigid”, by which we mean this: A rigid gap is one that, if shifted (right) by X, does not coincide with another gap.

Think about the gap from F to G (the leftmost blue gap). If you shift it (right) by X, you get the gap from C to D. Shift gap CD by X and you get the gap GA; shift that by X and you get the gap DE. But if you shift DE by X you don’t get a gap: you get a segment from A to where B would be if there were a B. The gap DE is rigid. EF (the purple gap) is rigid too, because shifting it by X doesn’t give you a gap (it goes from where B would be to C). And AC (orange) is rigid, because shifting it by X gives you the segment EG, which is two adjacent gaps (EF and FG), not one.

Generally, there are only two ways a gap can be rigid. One is if when you do the shift one or the other of its end notes doesn’t map to a note. That happens only when one or the other of the end notes is the last note added (A in this case), in which case there isn’t a note X to the right of it. We’ll call this a Type I rigid gap.

The other way is if when you do the shift there is a note, or more than one note, in the middle of the shifted segment. But that happens only if the note(s) in the middle have no notes X to the left of them. Otherwise there’d be one or more notes in the middle of the unshifted gap, and by the definition of a gap, there isn’t. And the only note with no note X to its left is the first note (F in this case), so there can be only one note in the middle of the shifted gap and there can be only one rigid gap of this sort. This is a Type II rigid gap.

And that means there are no more than three rigid gaps: two Type I gaps that start or end on the last point, and one Type II whose shifted version contains the first point. All the other gaps are nonrigid. By shifting any one of them one or more times, you can make it coincide with one of the rigid gaps, and so it must be the same size as one of the rigid gaps. Therefore there can be at most three gap sizes.

That’s the first part of the theorem. Second part, coming up soon.