parity | Eventually Almost Everywhere

This post is aimed at secondary-school students pitched roughly at the level of the British Mathematical Olympiad. It is ostensibly about a certain class of number theory problems, but the main underlying mathematical principle is broader than this. The post is based on an in-person session I have given to students and at teachers’ conferences a few times over the past five years, but I’ve chosen to write it up at this moment because of the connection to Problem 4 on the most recent BMO1 paper, which we discuss later in the post.

Prologue

Alice and Bob make the following statements:

Alice: all prime numbers are odd.
Bob: we can’t say anything about whether prime numbers are odd or even.

These are different types of statement, one objective, one more subjective; but both are wrong. Alice is wrong because 2 is a prime, and 2 is of course even. Bob is wrong because while Alice is wrong, and the alternative statement “all prime numbers are even” is even more wrong¹, there are plenty of possible statements that are true and useful, including

Cleo: all prime numbers are odd except 2.

and weaker versions (that may be more relevant in other contexts) like “all primes greater than $10^{2024}$ are odd”.

The characters now turn their attention to another family of integers, the square numbers $\{1,4,9,16,25\ldots\}$ , and the sixth powers $\{1,64, 729, 4096, 15625,\ldots\}$

Alice: no square numbers are prime.
Bob: I agree.
Alice: most square numbers are not sixth powers.
Bob: hang on, but infinitely many square numbers are sixth powers?

The difficulty in the second statement is what does most mean in this context? The square of an integer n is a sixth power if and only if n is a cube, and so Alice’s statement is equivalent to the statement “most positive integers are not cubes”, which is intuitively reasonable, but would require more clarification than the analogous statement “most primes are odd”. Is it not relevant, for example, that 1/4 of the first eight positive integers are in fact cubes?

It is not impossible to formalise this notion of most in a reasonable way to permit the two statements above².

But the bulk of this post will discuss situations that extend the first of these conversations, ie when it’s not true to say “all element of X have property Y”, but where it’s nonetheless possible to make a useful intermediate statement.

Warmup problems

I hope most readers know how to solve an equation such as

$3x+4 = 2(x+7),$

and indeed learning how to solve such equations forms a important milestone in mathematical education as the first example of various principles of algebra. When such equations are still novel, teachers would be advised to avoid examples such as

$2x+4 = 2(x+7)\quad\text{or}\quad 2x+14 = 2(x+7),$

for which the answers are, respectively, ‘no solutions’ and ‘every x satisfies this’. While they are perfectly valid equations, it means something slightly different to solve them, since the answer set has different structure and, more importantly, the method is different since it doesn’t consist of a sequence of a manipulations leading directly to the required conclusion $x= \texttt{answer}$ .

However, I mention this in passing to clarify that even in the simplest possible family of equations (probably encountered somewhere between ages 9 and 13) we are mindful that not all equations have unique solutions.

I’ve adapted a problem from the American competition AIME:

Find all integers $n\ge 1$ such that $\frac{(n+2)!-(n+1)!}{n!}$ is a prime.

One could start by writing $\frac{(n+2)!-(n+1)!}{n!}=p$ if you wish, but in fact we only need to work with the left hand side, so it’s better to avoid this if possible. The key to this problem is to avoid the prime condition initially, and just manipulate the LHS until it simplifies as

$\frac{(n+2)!-(n+1)!}{n!} = (n+1)(n+2)-(n+1)=(n+1)^2,$ (*)

which is never a prime, since $(n+1)^2$ is a square number and so, as already discussed, never a prime.

So at a meta-level, comparing with the other problem in this section, this one also begins with reversible algebraic manipulations, but does not end with a direct reduction to $n = [...]$ , and indeed the final step is not reversible at all.

Finally, we remark that the original version of the AIME problem was

Prove that for all integers $n\ge 9$ , $\frac{(n+2)!-(n+1)!}{n!}$ is a perfect square.

The same algebraic reduction as (*) resolves the original version without an extra step concerning primes.

To be, or not to be, a perfect square

The rest of this article will focus entirely on problems of the form: find all positive integers n such that […] is a perfect square.

As setup, we’ll always consider a function f(n), and the sequence f(1),f(2),f(3),… and the question, comment on the set of n is f(n) a square? In particular, this is a more open-ended question than for which n is f(n) a square, which requires a more exact answer. We’ll aim for one of the following possible answers:

f(n) is always a square;
f(n) is a square for infinitely many n;
f(n) is a square for only finitely many n;
f(n) is never a square.

Clearly this is not an exhaustive list of possible descriptions³ of the set under discussion, but it will do for now. The difference between the second and the third bullet point can be thought of as: “are there arbitrarily large values of n for which f(n) is a square?”

As some examples:

$\frac{(n+2)!-(n+1)!}{n!}$ is always a square, because $(n+1)^2$ is always a square.
$(n+2)^2-1$ is never a square, because the only squares that differ by 1 are {0,1} which aren’t attainable when $n\ge 1$ .
$n^2+3$ is a square for only finitely many n, because the only squares that differ by 3 are {1,4}.

Exercises to try yourself

$n^8, 3n+1, 3n-1, \lfloor \sqrt{n}\rfloor, 2^n, 2^n+1, 2^n-1, 3n^3, n^2+5n+10$ ,
or, now with p ranging over the set of prime numbers: $3p^3$ .

Some discussion of some of these follows later to avoid spoilers.

BMO1 2023, Problem 4

This problem does not have exactly the same structure as the previous exercise. A solution will follow shortly, but before starting, [spoilers] I want to emphasise that the main part of the solution involves framing this problem exactly as in the exercise above.

We will establish that there are only finitely many n such that $n\times 2^n+1$ is a square, using a classical number theory argument.
In doing so, we will eliminate all integers n that are at least some threshold value K from consideration (which we think of as “n large”, even though in this case it isn’t so large).
The actual set of solutions comes from check the remaining “small” values of n.
The point to emphasise is that while this third bullet is definitely an important component of a successful solution (and does feel closest to actually addressing the “find all” aspect of the problem statement), it is not really the key step, since checking a small number of possibilities is fundamentally much more straightforward than an argument to eliminate the other infinitely-many integers.

This overall structure is very common when solving Diophantine equations involving integers, even if the exact statement isn’t “find all n such that […] is a perfect square”.

Anyway, to the solution of this problem. As in many problems of this difficulty in this number theory, it’s really useful to aim to factorise and analyse the factors, remembering that they are integers! In this case, writing $n\times 2^n+1=k^2$ doesn’t suggest an easy factorisation of the LHS, but rewriting as $n2^n = k^2-1$ does now have a nice factorisation, using difference of two squares on the RHS:

$n2^n = (k-1)(k+1).$

Here the two factors are (k-1) and (k+1). We know nothing about k, so we know nothing intrinsic about these factors, except that they differ by 2. But now when we consider that their product is $n2^n$ , we can start to make some serious deductions⁴.

(k-1) and (k+1) differ by two, and so have the same parity⁵. Then $n2^n$ is even, and so in fact both factors are even.
But more than this, one factor will be a multiple of 4, while the other will not be. So all the powers of 2 within $n2^n$ (which may include additional factors of 2 coming from n) apart from one, must be included in one of the factors.
The idea is that $2^n$ is generally much larger than n, and so this will force one of the factors to be much larger than the other factor, which is not permitted. (Recall that the factors differ by 2.)

So formally, we might write that $k+1\ge 2^{n-1}$ and $k-1\le 2n$ . These are inequalities not equalities because some of the factors of n could be in (k+1) not (k-1) and/or a priori, we could have $k-1=2^{n-1}$ and $k+1=2n$ etc. This leads to

$2n+2\ge 2^{n-1}$ (*)

and we now have exactly the language to describe the truth of this inequality! It is only true for finitely many positive integers n. There are a number of ways to prove this, but it is important that we do provide a lower bound. One possibility is to check that (*) holds for n=5, and then prove (*) for all $n\ge 5$ by an inductive argument.

At this point, we have shown that $n\times 2^n+1$ is not a perfect square for $n\ge 5$ , and so at this point it really is easiest just to check $n=1,2,3,4$ by hand, which reveals that $n=2,3$ work.

To link this to the background, note that this final procedure of “finding all the solutions” really had nothing in common structure-wise with “solving $3x+4 = 2(x+7)$ “, for which substituting in various values of x would never constitute part of a good solution.

Comments on exercises

$3n+1$ is a square for infinitely many n, while $3n-1$ is never a square, for reasons that are often framed in the language of quadratic residues.
$2^n$ is a square for infinitely many n (specifically, when n is even), while $2^n+1$ is a square only when n=3, which can be seen via a similar argument to the argument above for the BMO problem. Meanwhile $2^n-1$ is never a square, which can also be checked using quadratic residues.
$3n^3$ is a square for infinitely many n (specifically, when $n=3k^2$ ), while $3p^3$ is a square for only one prime p, since only one prime is divisible by 3.
$n^2+5n+10$ is only a square for finitely many n, because when n is large, we have $(n+2)^2< n^2+5n+10<(n+3)^2$ . This style of argument is sometimes called square-sandwiching, although it can of course be deployed in contexts other than squares. Problems that turn on this method have appeared in BMO surprisingly often in the past 15 years. For this particular example, note that one does have to check a handful of values to confirm it is for finitely many but at least one n (rather than for no n).

Footnotes

of course, writing even more wrong is in itself making a nuanced comment about the parity of the prime numbers. ↩︎
given a set $A\subseteq \mathbb{N}$ , a natural formalisation of the notion that ‘most integers are not in A’ would be that $\lim_{n\to\infty} \frac{|A\cap\{1,\ldots,n\}|}{n}=0.$ In other words, the proportion of elements of A amongst the first n integers vanishes as $n\to\infty$ . This is certainly true when A is the set of cubes.
There are many sets for which this limit does not exist, including quite natural sets like the integers whose decimal representation starts with a 1, and so a full treatment of this notion of asymptotic density would require more than a footnote. ↩︎
in particular, we might wish to draw a distinction between f(n) is a square for infinitely many n and the stronger statement f(n) is a square for all-but-finitely many n, and in some applications that difference is crucial. ↩︎
A common error is to make some reasonable-sounding assumption about how the factors of $n\times 2^n$ are split between (k-1) and (k+1), for example by assuming that $k-1=n$ and $k+1=2^n$ because this is visually a natural way to pair them up. ↩︎
parity refers to whether a number is odd or even. ↩︎

This post concludes my non-exhaustive list of things I think are interesting about the top-to-random shuffle. In previous posts I have talked about the construction and correct sense of convergence to randomness, and that this algorithm does genuinely achieve uniform randomness at some hitting time which is easy to specify. Promising that posts will be short hasn’t worked in the past so I won’t do that again now, but the idea of this post is brief:

When we specified the dynamics of the top-to-random shuffle, we insisted that the top card card could be placed anywhere in the deck with equal probability including back on top. This appears to be doing nothing except slowing down the shuffling process. Why is this important for convergence to randomness?

Fortunately the answer is short: if we do not let the top card be inserted back onto the top, allowing the configuration to stay the same, then we can divide up the set of orderings into two classes, and the pack will alternate between them.

Why is this a problem? Suppose the classes are called X and Y, and X is the class that contains the original ordering 1,2,…,n. Then after k shuffles, the ordering of the deck will be in X if k is even and in Y if k is odd. Remember our definition of ‘close to randomness’ will be the greatest difference in probability of an event between the actual distribution and the uniform distribution. As before, you can think of this by a betting analogy – what proportion profit can you make again someone who thinks it’s uniform by knowing the true distribution?

Well, it will turn out that the sets X and Y have the same size, so in the uniform distribution, the probability that an ordering is in X is 1/2. Whereas if the pack alternates, then so long as we know how many shuffles have occurred, this probability is either 0 or 1. In particular this is far from 1/2. We should remark that if we introduce the notion of sampling at a random time, or taking an average over all large times in some sense, such problems may disappear, but the result obtained may be less useful. See this post on Cesaro Mixing for details presented in a more rigorous style.

So it remains to see why this is true. First a definition. A transposition is when two elements in a permutation are exchanged. Eg 31452 -> 35412 by transposing 1 and 5. It makes sense intuitively that we can get from any permutation to any other permutation by making successive transpositions. Indeed, this is precisely what is happening in the top-to-random shuffle. To avoid continually having to write it out, we call the original permutation 1,2,…,n the identity permutation.

Then the idea is that X is the set of permutations we can obtain by starting with the identity and applying an even number of transpositions, while Y is the set obtained by applying an odd number of transpositions. For this to work, we will need to show that these sets are disjoint. That is, no permutation can be generated by both an odd number and an even number of transpositions. This is important, as a permutation can certainly be generated from transpositions in multiple ways. For example, if the elements are 1,2,3, we can obtain the permutation 2,1,3 by transposing 1 and 2, obviously. However, we could alternatively start by transposing 2 and 3 to get 1,3,2, then 1 and 3 to get 3,1,2, then 2 and 3 again to get 2,1,3. Note that both of these require an odd number of transpositions.

We will call a permutation even if it is generated by an even number of transpositions, and odd otherwise. We also say that its sign (alternatively signature, parity) is +1 or -1 respectively. To prove this is well-defined, we really want to find a different property that is easier to track.

A useful trick is to count how many pairs of elements are not in the correct order. Let’s do this for our previous example: 31452. There are 5 elements so 5 x 4 / 2 = 10 pairs of elements. We list them:

1 and 2 are in the correct order.
1 and 3 are not, as 3 comes before 1 in this permutation.
1 and 4 are correct.
1 and 5 are correct.
2 and 3 are not.
2 and 4 are not.
2 and 5 are not.
3 and 4 are correct.
3 and 5 are correct.
4 and 5 are not.

So 5 pairs are not in the correct order. Since 5 is odd, the claim is that this means 31452 is an odd permutation. To check this, and to confirm that the sign is well-defined, it suffices to check that the number of so-called inversions, or pairs in the wrong order, changes parity every time we apply a transposition.

This is clearly true if we transpose adjacent elements. Then the orderings of all pairs remain the same, apart from the pair we transposed, which changes. Then, if the elements are not adjacent, instead of transposing them directly, we can perform a succession of transpositions of adjacent elements. The easiest way to describe this is again by example. Suppose we want to transpose 3 and 5 in 31452.

31452 -> 13452 -> 14352 -> 14532 -> 15432 -> 51432.

Note that the middle transposition is actually transposing 3 and 5, and the others are symmetric about this middle operation. In particular, there is an odd number of transpositions in total. So we have proved the result for general transpositions, and thus we now know that the sign of a permutation is well-defined. Note also that there are an equal number of odd and even permutations of every n=>2. For every odd permutation, transposing 1 and 2 gives an even permutation, and vice versa, uniquely, giving a bijection.

What’s really going on is that we are able to multiply permutations, by doing one after the other. Unlike multiplying real numbers, the order in which we do this now matters. In this context, the set of permutations is an example of a general structure called a group. The idea of partitioning a group into subsets which are in some sense symmetric and where some other operation jumps between the subsets is a useful motivation point for a whole avenue of interesting theory. Not to be explored now unfortunately…

Solving Rubik’s cube from scratch, in python (fulmicoton.com)

Eventually Almost Everywhere

A blog about probability and olympiads by Dominic Yeo

Tag Archives: parity

Finitely many solutions

Related articles