Today I Learned

March 29th

Today I learned some stuff around the pigeonhole principle. What interested me most today was the following.

The main idea here is that, even though the statement feels sufficiently intuitive, we actually want to show the contrapositive. In particular, we show that if $A_k\cap A_\ell\ne\emp$ implies $k=\ell,$ then\[\sum_{n\in\NN}\mu(A_n)\le\mu(B).\]Now the measure $\mu$ can actually help us. The condition tells us that the collection $\{A_n\}_{n\in\NN}$ is a disjoint collection of measurable sets, so it follows\[\sum_{n\in\NN}\mu(A_n)\le\mu\left(\bigcup_{n\in\NN}A_n\right)\le\mu(B),\]and we're done immediately. The first inequality holds because of the disjoint countable union, and the second inequality holds by subset. $\blacksquare$

What I find interesting about this proof is its generality. For example, even though there are potential circular reasoning issues, we can endow $X$ with the counting measure so that we get the following statement.

That is, we have recovered the usual pigeonhole principle immediately. We do remark that the measure-theoretic version is not necessarily strictly stronger, however. For example, the provided proof makes it difficult to expand to uncountable collections, and the set-theoretic version permits infinite cardinalities more readily.

Anyways, I guess I should say that I started this journey as an attempt to justify the step in the proof of Minkowski's theorem where we consider the size of translated sets as bigger than the fundamental domain they occupy. In this case, all of the set-theoretic cardinalities are merely $|\RR|,$ but we can still use the measure-theoretic version of the pigeonhole principle to conclude.

While we're here, let's use the pigeonhole principle on some combinatorial number theory.

The idea is to focus on the equality case, which is all evens. What breaks all evens is that, as soon as we add on another element, we can choose that odd number with "lots'' of its even friends. While $2$ looks like a tempting choice, the neighbors of the odd number are more apparent.

In particular, we note that\[S\subseteq\{1,2\}\cup\{3,4\}\cup\cdots\cup\{2n-1,2n\}.\]There are $n$ sets on the right-hand sets while more than $n$ elements in $S,$ so there are distinct $k,\ell\in S$ which belong to the same set $\{2m-1,2m\}.$ In other words, there exists an $m$ with $2m-1,2m\in S,$ and these $2m-1$ and $2m$ make our relatively prime pair. $\blacksquare$

Let's do another one, for fun. I saw this one in Mrs. Harrelson's number theory class.

Again, we focus on the equality case, which is $S=\{n+1,\ldots,2n\},$ in which no element divides another for size reasons. However, as soon as we add another element $k,$ it must be no greater than $n.$ If $k\in(n/2,n],$ then $2k$ double lives in $S.$ If $k\in(n/4,n/2],$ then $4k$ lives in $S,$ and so on. This gives us a methodical way of finding $k$'s multiple.

As an aside, we note that we could do something like $k\floor{n/k}$ as our multiple of $k,$ but it isn't clear how to generalize this when $S$ doesn't contain literally everything bigger than $n.$ What's going on under the surface here is that we are able to double our way out of trouble, and this algorithm provides a unique multiple for each $k.$

So we organize ourselves around doubling. We would like to say something like "there exists two elements such that one is double another,'' but this is false, for we could choose\[\{2,5,6,7,8\}\subseteq\{1,2,3,4,5,6,7,8\}.\]We see that $2$'s double doesn't actually live in $\{2,5,6,7,8\},$ so we have to be more careful—we want to consider doubles of doubles, and so on.

Thus, we note\[\{1,2,\ldots,2n\}=\bigcup_{\substack{1\le k\le 2n\\k\text{ odd}}}\left\{k2^\nu:\nu\in\NN\text{ and }k2^\nu\le2n\right\}\]is a disjoint union of $n$ sets. Because $S$ has more than $n$ elements, two of $S$'s elements live in the same set generated by an odd $k,$ implying they must take the form $k2^\alpha$ and $k2^\beta$ for distinct $\alpha$ and $\beta.$ Asserting $\alpha\le\beta$ without loss of generality, we see $k2^\alpha\mid k2^\beta,$ and we are done. $\blacksquare$

This last proof I have little idea how to motivate; I have done my best, but it is truly clever.