Number of squares in a grid of dots.

[Vorde]

This is a problem that I just thought of the other day and am intrigued by, let me set it up.

You have an n x n grid of dots, so that each dot is 1 away from the four dots closest in each direction. My question is; for a grid of n² dots, what is the total number of possible combinations of four dots that form a square.
Now this is not just how many 1 by 1 squares there are, they can be any size and any orientation (meaning that the sides of the square do not have to be parallel to the sides of the grid).
Now I had attempted to figure this out myself, but I've come to a problem I couldn't solve (I apologize for not using mathematical notation, I don't really know it well enough to risk misrepresenting my idea).
Here's what I came up with:

The total amount of squares can be represented by the sum of all 4 number combinations (represented by (a,b,c,d) where a, b, c, d all stand for the coordinates of a single dot) that pass two tests:

The first test is to determine whether or not those form a square. My original idea of a test if a-b=a-c=a-d=b-a and so on failed when I realized it would not pick out the difference between squares and parallelograms. My next idea is (given a square ABCD) if AC and BD are exactly \sqrt{2} times AB,BC,CD,DA then that should imply a square, but that's where I stopped because I am not sure of that.

The second test is to test whether or not a square is not just a rotation of another square, but I have no idea how to accomplish that.

I appreciate any advice or help anyone can give.

 

[Yuqing]

It would be easiest to set up a recursion. I will use the notation that an n\times n square contains side length n, that is a 1\times 1 square actually contains 4 dots, 2\times 2 contains 9 and in general n\times n contains (n+1)² dots.

As a base case, we can easily see that a 1\times1 square will have just one square, itself. Let S(n) be the number of squares for an n\times n square.

If we construct a general n\times n square, we can see that we must add (2n + 1) 1\times1 squares to our n\times n square to obtain an n+1\times n+1 square. We need only count the squares which contain these 2n+1 1x1 to set up our recursion. If you count newly introduced 2\times 2 square you will see that there will be 2n-1 of them. Counting 3\times 3 will give you 2n-3, 4\times 4 will give you 2n-5 and this happens all the way to n+1\times n+1 which will give you just the one.

We now have a recursive formula: S(n+1) = S(n) + \sum_{i=0}^{n}2i+1 It is well know that the sum of the odd numbers from 1 to 2n+1 is given by (n+1)². Therefore S(n+1) = S(n) + (n+1)^2 We can see that then the number of squares in a n\times n grid is just the sum of the first n squares, given by the formula S(n) = \frac{n(n+1)(2n+1)}{6}

 

[Vorde]

Maybe I've not understood that entirely, but doesn't that only count squares in a rectangular alignment and not larger ones, not to mention squares that are rotated?

 

[Yuqing]

I apologize, I didn't catch the any orientation part. I suppose you can also set up a recursion for the number of squares of alternate orientation introduced upon adding a layer. But I don't see an easy way to calculate that without breaking it into several cases.

 

[Vorde]

No matter, that's the part where I was running into trouble. I think that a recursion method however would be far more complicated than the way I was thinking about it once you added in other orientations though.

 

[Yuqing]

Actually I think it should be salvageable. If we proceed again by recursion, we need only count the number of squares with off orientation "native" to the square (that is, the nxn square is the smallest possible for this orientation). It's not too difficult to see that there is exactly n-1 such squares "native" to an n by n square. Again letting S(n) be the number of squares (of any orientation this time) then we have S(1) = 1 and

S(n+1) = S(n) +\sum_{i = 0}^{n}(2i+1) + \sum_{i = 0}^{n}(2i+1)(n-i)

I don't have a real way of solving this recursion though.

edit: mistake in formula

 

[Vorde]

I think you might have lost me, how would you factor in # of off orientation permutations on a grid-segment by grid-segment basis because the dots composing a square could be arbitrarily far away.

 

[Yuqing]

I think you might have lost me, how would you factor in # of off orientation permutations on a grid-segment by grid-segment basis because the dots composing a square could be arbitrarily far away.

What do you mean arbitrarily far away? The squares must be contained within the larger nxn square no? By symmetry, you can easily determine the number of "native" squares of any orientation.

 

[Vorde]

Sorry I didn't see the rest of your post previous to your last, I think I'm following what your saying, but I'm not sure what you mean by 'native'.

 

[Yuqing]

Sorry I didn't see the rest of your post previous to your last, I think I'm following what your saying, but I'm not sure what you mean by 'native'.

By native I mean the squares within the nxn grid which is not possible within an (n-1)x(n-1) grid or smaller. For example. If we take the normally oriented squares, then the largest square (and only the largest square) is "native" to the grid. Any other smaller square can be produced in an (n-1)x(n-1) grid and hence can be covered by our recursion. Now for squares of any orientation, there will be a total of n "native" squares for each nxn grid. One is just the normally oriented square mentioned above. The other n-1 is produced by rotation one dot at a time. If we label the dots with coordinates then the normal square will have corners {(0,0), (0,n),(n,0),(n,n)} and a rotated square will have corners {(0,1), (n-1,0), (1, n),(n,n-1)} and so on.

 

[Vorde]

Ah I see that makes sense, and simpler than my method definitely.

The only question I have is would that identify rotations on the same as different squares or the same (while I guess it doesn't matter in my original view one of the goals was to identify rotations of already counted squares and not add them).

 

[Yuqing]

The only question I have is would that identify rotations on the same as different squares or the same.

I'm not too sure what you mean by this. If it's any clarification I can write a program to generate the number for squares for you if you'd like. You can see for yourself if this solution is the one you require.

 

[Vorde]

Oh no no don't bother, this is just to satisfy a curiosity. Thanks a lot for your help, if I hadn't gotten it I would still be trying after my idea.

 

[Yuqing]

As an update, the numbers I generated seem to be the four-dimensional pyramidal numbers.