Aiming for Perfection

Here is a post after a long time.

The other day I came across list of unsolved problems one of the 'problems' was to study the sequence of square complements. So I thought, let us see how far we can get.

A square complement of a number is any number when multiplied to the original number results in a perfect square. e.g. 3, 12, 27, 48 are all square complements of 12.

The least of such numbers is called the least square complement (LSC) of the number. (Some authors call this just the square complement. For our analysis below, we distinguish between these two.)

Now the sequence of least square complements go like this:

1, 2, 3, 1, 5, 6, 7, 2, 1, 10, 11, 3, 13, 14, 15, 1 etc.

So what? How do we analyze them?

Here are some observations:

1. The least square complement of a perfect square is 1.
2. The least square complement of a number cannot be greater than the number itself. This is because any number is its own square complement.
3. The least square complement of a number has to be square free; i.e. it should not have any divisor that is a perfect square. If this were not the case, we could easily factor out the square part and still get a square complement.
4. The least square complement of a number must be one of its divisors. (Prove it!)
   
5. Therefore, a prime is its own least square complement.
6. Therefore, the sequence of least square complements diverges. As we all know the primes are infinite and since we can find a prime however large, we can find a least square complement however large (itself).

So far so good.

Let us approach this from another direction.

Define SC(n) = {m | m is a square complement of n}

Now an interesting thing to note is that the product of any two members of SC(n) is a perfect square. It is easy to see that "is a square complement of" is an equivalence relation.

Now every integer m belongs to at least one SC(n), in particular to SC(m). So the SCs cover the set of integers. Now are they mutually exclusive?

Let m belong to both SC(s) and SC(t). Let r be another member of SC(s).

Now, m.s = square. m.t = square. r.s = square, by our assumptions. Based on above, r.m is also a square.

Consider m.m r.t = r.m m.t = square. square = square.
So square . r.t = square. Therefore, r.t should also be a square.

So SC(s) = SC(t).

Thus the SCs partition the set of integers.

Can we have a look at them? Most certainly! Here they go:

SC(1) = {1, 4, 9, 16, 25, ... }, set of perfect squares
SC(2) = {2, 8, 18, 32, 50, .....}, twice the perfect squares
SC(3) = {3, 12, 27, 48, 75, ....}, three times the perfect squares
SC(5) = {5, 20, 45, 80, 125, ...}, five times the perfect squares
SC(6) = {6, 24, 54, 96, 150, ...}, six times the perfect squares

Hey, is there a catch? Is SC(n) always n times the perfect squares?

Yes, that is true as long as n is square free.

Here is why.

The fundamental theorem of arithmetic says that each number has a unique factorization. So each number can be represented by an infinite vector of non-negative integers, which correspond to the prime powers in the factorization.

n = (a1, a2, .....)

For example, 24 = (3, 1, 0, 0, ....) = 2^3 * 3

Now a perfect square will have all ai's even.

The least square complement of a number is just the number that makes the ai's even.

LSC(n) = (a1 mod 2, a2 mod 2, ....)

For example, LSC(24) = LSC(3, 1, 0, 0, ...) = (1, 1, 0, 0, ..) = 6.

Let m = (b1, b2, ....) be a square complement of n = (a1, a2, ....). This means that b1+a1 is even, b2 + a2 is even, etc.

Now bi = ai mod 2 + (bi - ai mod 2). You can verify that (bi - ai mod 2) is even since ai + bi is even. So every square complement can be written as a product of the least square complement and a perfect square.

Now all this didn't really address the original question of studying the sequence of least square complements. All we know so far is that the sequence diverges but it grows no faster than n.

Since the primes do not seem to follow a particular pattern, it can be expected that the least square complements also don't since they match at the primes.

How about the average of the least square complements?

I tried to run some simulation in excel and found that the average of the averages seems to be constant. I do not have a proof though.

Any ideas?