Counting like Gauss, Part II

24 May

If you missed Part I, which introduces our problem, click here to read last week’s post.

Here are some pictures from last week:

level setsoctahedron

The picture on the left describes technique 1, which we did last time to count how many points are in an octahedron with vertices at (0,0,n), (0,0,-n), (0,n,0),(0,-n,0), (n,0,0), and (-n,0,0).  The edges of the octahedron are lines between vertices that live in the same octant, and the faces live in each octant (so there are eight faces).  Now we’ll do Technique 2: counting the points in each octahedral shell, which is also called the spherical number.

Let’s look at just the yz plane, that is, where x=0.  So we want the integer points in the yz plane that lie on the n-shell of the octahedron.  Let’s stop and think about what we said in the last paragraph: there are eight faces because there are eight identical octants.  What if we count up all the points in one octant, then multiply by 8, and subtract any points we double counted?  Sounds great to me!  Let’s now just focus on when x, y, and are all greater than or equal to 0.

tech2

Octahedron, x=0 plane, one quadrant, view of that quadrant

So now we have these points on a line such that x=0, and the line runs between (0,n,0) and (0,0,n).  Well thanks to point-slope formula, or slope-intercept form, or however you want to write your equation, we know that these points satisfy the equation of the line: y+z=n.  How many ways can I cut up n into two numbers and such that both are at least 1?  (I’m going to say they both have to be at least one because the vertices (0,n,0) and (0,0,n) will be special in the next paragraph).  Well if I choose y, that automatically chooses z.  I have n-1 choices for y (they are {1,…,n-1}), so that means I have exactly n-1 ways to choose and z.  Then there are n-1 points on the line.  I can either count and see I have 12 edges in my octahedron, so insides of edges contribute 12n-12 to the total count, or I can see I have three edges in my positive octant, multiply by 8 (because we have eight octants), and then divide by two since each edge lies in two octants.  Either way, we contribute 12n-12 to the final count.

By the same logic, I have exactly three vertices in my positive octant, each of which appears in 4 neighboring quadrants.  These contribute 6 to the final count (3*8/4=6 if we do the double counting method, or again we can just look at how many vertices are in an octahedron).

Now I’ve counted the edges and vertices in my octahedral shell, so I only need to figure out how many points lie inside the triangular face.  Again I can write an equation for the face: x+y+z=n.  Then I need to figure out how many ways I can partition n balls into three boxes, each with at least ball inside.  This is a partition problem.

trime

We’ve counted the outside, now we need to find the number of integer points inside the triangle.

Let’s try to tackle this the way we did the last one.  But maybe let’s use an example, like the number 6.  How many ways can I cut up 6?  Well, I can choose 3 for x, which leaves 3 leftover to split into two numbers y and z.  From above I know there are 3-1 ways to choose, which I know since I can pick 2,1 or 1,2 for and z.  I can also choose 4 for x, which leaves 2 leftover, or 2 for x, which leaves 4 leftover, or 1 for x.  Let’s organize this into a table.

table

I’ve considered investing in a mouse, but haven’t quite bitten the bullet yet

Notice then that the number of ways I have to partition 6 into three bins, each of which has value at least 1, is 1+2+3+4.  This logic generalizes: I can pick any number from 1 to n-2 for x, and each of those options gives me n-x leftover to split into and z, and from above that’s n-x-1 such options.  So I have \sum_{x=1}^{n-2} n-x-1=\sum_{x=1}^{n-2} x.  Thanks to nine-year-old Gauss via fable, I know how to sum up the numbers from 1 to k: it’s a formula, 1+\ldots+k=\frac{(k+1)(k)}{2}.  There’s a bunch of ways to explain this formula, here’s an easy to read collection.  So if I apply this formula to my sum, I have \frac{(n-1)(n-2)}{2}.  This is all the points inside the face that lie completely in the octant, so if I multiply this by 8 I have contributed 4(n-1)(n-2) points.

Then in the octahedral shell, I can add up all the contributions and get 6+12n-12+4(n-1)(n-2), which simplifies to 4n^2+2.

We actually want to count all the lattice points inside an octahedron.  The octahedron is a bit special, since any lattice point inside it will lie on one of these octahedral shells, like a bunch of nesting Russian dolls.  So now I need to do 1+ \sum_{k=1}^n (4k^2+2), where I added the 1 at the beginning to represent the single point (0,0,0).  Luckily I also have a formula for the sum of squares, though without fun folklore to go with it.  The formula is \sum_1^n k^2 = \frac{n(n+1)(2n+1)}{6}.  Plugging that into my formula, I have the number of points in the octahedron is 1+4(\frac{n(n+1)(2n+1)}{6})+2n = \frac{4}{3}n^3+2n^2+\frac{8}{3}n+1, which is EXACTLY WHAT WE GOT LAST WEEK!!!!

I hope this was as exciting for you as it was for me.  My friend Jeremy Kun and an anonymous number theorist commented last week about the Gauss Circle Problem and the error terms in it.  I just wanted to add that Gauss offered up the problem and the error guess, and it took 100 years until Sierpinski came up with a proof for something not that close to the error guess, and now it’s been like 200 years and we don’t quite have a proof for what we think the answer is yet.  Rumor has it that several years ago someone posted a proof to the arXiv, then quietly withdrew it.

Partner has pointed out that there’s a wikipedia entry for this problem but it doesn’t go into as much depth or have as cute pictures as my two blog posts.

Advertisements

One Response to “Counting like Gauss, Part II”

Trackbacks/Pingbacks

  1. Counting Things | nebusresearch - May 25, 2016

    […] Yesterday, Yenergy continued the discussion and got into partitions. Partitions sound boring; they’re about identifying ways to split something up into components. Yet they turn up everywhere. I’m most used to them in statistical mechanics, the study of physics problems where there’s too many things moving to keep track of them all. But it isn’t surprising they turn up in this sort of point-counting problem. […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: