## Sums of Function over Subsets of Natural Numbers

In this post we analysed sums of the form

$S_{k}(n) = 1^{k} + \cdots + n^{k}.$

We will generalise this to sums of the form

$S_{f}(n) := f(1) + \cdots + f(n)$

for suitable functions $f: \mathbb{N} \to \mathbb{N}$.

Theorem. For $n \in \mathbb{N}$, define $[n] := \{1, \dots, n\}$. Suppose that $f: \mathbb{N} \to \mathbb{N}$ satisfies

$\displaystyle \sum_{j \in [n]} f(j) < 2^{n} - 1$

for some $n \in \mathbb{N}$. Then there exist disjoint non-empty subsets $A, B \subseteq [n]$ such that

$\displaystyle \sum_{j \in A} f(j) = \sum_{j \in B} f(j)$.

First Proof. Each non-empty subset $T \subseteq [n]$ corresponds to a sum

$\displaystyle S_{f}(T) := \sum_{j \in T} f(j) \in [S_{f}(n)]$.

Since $S_{f}(n) < 2^{n} - 1$—the total number of non-empty subsets $T \subseteq [n]$—there must be two non-empty subsets $A, B \subseteq [n]$ with $S_{f}(A) = S_{f}(B)$. Excluding the common elements from both sides gives the desired claim. $\square$

Second Proof. We consider expressions of the form

$S(c_{1}, \dots, c_{n}) := c_{1} f(1) + \cdots + c_{n} f(n)$,

where $c_{i} \in \{\pm 1\}$ for each $i$. Then $S$ takes $2^{n}$ possible values in $[-S_{f}(n), S_{f}(n)]$, which are all congruent modulo $2$. Hence, the number of distinct values that $S$ takes is at most

$\displaystyle \left \lceil \frac{2 S_{f}(n) + 1}{2} \right \rceil = S_{f}(n) + 1$.

Since this is less than $2^{n}$, we can find $c_{j}, c_{j}' \in \{\pm 1\}$ for $j \in [n]$ such that

$\displaystyle \sum_{j=1}^{n} c_{j} f(j) = \sum_{j=1}^{n} c_{j}' f(j) \Leftrightarrow \sum_{j=1}^{n} (c_{j} - c_{j}') f(j) = 0$

with $c_{j} \neq c_{j}'$ for some $j$.

Note that $c_{j} - c_{j}' \in \{0, \pm 2\}$ for all $j$. Let $A = \{j: c_{j} - c_{j}' = 2\}$ and $B=\{j: c_{j} - c_{j}' = -2\}$. Then $A$ and $B$ are non-empty and disjoint, $A \cup B \subseteq \{1, \dots, n\}$, and

$\displaystyle\sum_{j \in A} f(j) = \sum_{j \in B} f(j)$,

as desired. $\square$

Remark. This is tight: taking $f(j) = 2^{j - 1}$ shows that

$\displaystyle \sum_{j \in [n]} f(j) = 2^{n} - 1$

and

$\displaystyle \sum_{j \in A} f(j) \neq \sum_{j \in B} f(j)$

for any two disjoint non-empty subsets $A, B \subseteq [n]$.

Filed under Combinatorics

## A Bound on the Prime Counting Function

The idea for this post arose from this quora answer.

Let $\pi(n)$ denote the number of primes up to $n$. It is well-known that

$\displaystyle\pi(n)\sim\frac{n}{\log n}$,

which is the celebrated prime number theorem. Although “elementary” proofs exist, most proofs of the prime number theorem are technical. Nevertheless, we can obtain some simple bounds as follows.

Let $p_1,\ldots,p_k$ denote fixed prime numbers $\leq n$. By the inclusion-exclusion principle, the number of positive integers $\leq n$ not divisible by any of the $p_i$ is

\displaystyle\begin{aligned}&n-\sum_{i}\left\lfloor\frac{n}{p_i}\right\rfloor+\sum_{i

Therefore, we have the following (rather weak) bound for the prime-counting function $\pi(n)$:

$\boxed{\displaystyle \pi(n)< n\left(1-\frac{1}{p_1}\right)\cdots\left(1-\frac{1}{p_k}\right) + k + 2^{k-1}}$.

Nonetheless, this implies the following result.

Theorem. $\displaystyle\lim_{n\to\infty}\frac{\pi(n)}{n}=0$.

For example, let’s say we want to find all $n$ such that at least 20% of the natural numbers below $n$ are prime. Then

$\displaystyle\pi(n)\geq\frac n5$.

If $p_1,\ldots,p_k$ are the prime numbers $\leq n$, then this means that

$\displaystyle n\left(1-\frac{1}{p_1}\right)\cdots\left(1-\frac{1}{p_k}\right) + k + 2^{k-1}>\frac n5$
$\displaystyle\iff n\left(\frac 15-\frac{\phi(p_k!)}{p_k!}\right).

The left-hand side is positive for $k=6$, for which the inequality has the solution $n<6041035/1657\approx 4638.78$. Trying the values in this range we obtain the following set of solutions

$n\in[2,330]\cup[331,335]\cup[337,340]\cup[349,350]\cup[353,355]\cup[359,360]$.

In general, if we want to find all $n$ such that $\pi(n)\geq\varepsilon n$, then we start by finding the least $k$ such that the $k$-th prime $p_k$ satisfies

$\displaystyle\left(1-\frac{1}{p_1}\right)\cdots\left(1-\frac{1}{p_k}\right)=\frac{\phi(p_k!)}{p_k!}<\varepsilon$.

(Note that such a $k$ is guaranteed to exist since the left-hand side approaches $0$ as $k\to\infty$, since the harmonic series diverges.) Then we can bound $n$ using

$\displaystyle n<\frac{k+2^{k-1}}{\varepsilon-\frac{\phi(p_k!)}{p_k!}}$.

(Observe also that $\displaystyle\frac{\phi(n!)}{n!}<\frac{\phi((n-1)!)}{(n-1)!}\Leftrightarrow n$ is prime.)

Filed under Number Theory

## SL(2,IR) is the Commutator Subgroup of GL(2,IR)

Here is a proof of the above fact.

Let $N$ be the commutator subgroup of the general linear group $GL(2,\mathbb R)$; i.e.,

$N=\langle ABA^{-1}B^{-1}:A,B\in GL(2,\mathbb R)\rangle$.

First, it is clear that $N$ is contained in the special linear group $SL(2,\mathbb R)$, since $\det(ABA^{-1}B^{-1})=1$ for any $A,B\in GL(2,\mathbb R)$. Next, we claim that $N$ contains all matrices

$\begin{pmatrix} 1 & b\\ 0 & 1\end{pmatrix}$.

This follows from noting that

$\begin{pmatrix} 1 & b\\ 0 & 1\end{pmatrix}=\begin{pmatrix} 1 & b\\ 0 & b\end{pmatrix}\begin{pmatrix} 1 & 1\\ 0 & 1\end{pmatrix}\begin{pmatrix} 1 & b\\ 0 & b\end{pmatrix}^{-1}\begin{pmatrix} 1 & 1\\ 0 & 1\end{pmatrix}^{-1}$.

By taking transposes, it also follows that $N$ contains all matrices

$\begin{pmatrix} 1 & 0\\ c & 1\end{pmatrix}$.

Further, $N$ contains all matrices

$\begin{pmatrix} a & 0\\ 0 & 1/a\end{pmatrix}$

since

$\begin{pmatrix} a & 0\\ 0 & 1/a\end{pmatrix}=\begin{pmatrix} a & 0\\ 0 & 1\end{pmatrix}\begin{pmatrix} 0 & 1\\ 1 & 0\end{pmatrix}\begin{pmatrix} a & 0\\ 0 & 1\end{pmatrix}^{-1}\begin{pmatrix} 0 & 1\\ 1 & 0\end{pmatrix}^{-1}$

for any $a\neq 0$.

Now let

$\begin{pmatrix} a & b\\ c & d\end{pmatrix}\in SL(2,\mathbb R)$.

Then $ad-bc=1$. Using the above results,

$\begin{pmatrix} a & b\\ c & d\end{pmatrix}=\begin{pmatrix} 1 & 0\\ c/a & 1\end{pmatrix}\begin{pmatrix} 1 & ab\\ 0 & 1\end{pmatrix}\begin{pmatrix} a & 0\\ 0 & 1/a\end{pmatrix}\in N$

if $a\neq 0$, and

$\begin{pmatrix} a & b\\ c & d\end{pmatrix}=\begin{pmatrix}0&1\\-1&0\end{pmatrix}\begin{pmatrix}1&-d/b\\ 0&1\end{pmatrix}\begin{pmatrix}1&0\\ ab&1\end{pmatrix}\begin{pmatrix}1/b&0\\ 0&b\end{pmatrix}\in N$

if $b\neq 0$, and the latter since

\begin{aligned}&\begin{pmatrix} 0 & -1\\ 1 & 0\end{pmatrix}\\=&\begin{pmatrix}x&y\\0&-x-y\end{pmatrix}\begin{pmatrix}-x-y&0\\ x&y\end{pmatrix}\begin{pmatrix}x&y\\0&-x-y\end{pmatrix}^{-1}\begin{pmatrix}-x-y&0\\ x&y\end{pmatrix}^{-1}\\ \in &\ N\end{aligned}

for any $x,y,x+y\neq 0$. Thus $SL(2,\mathbb R)\subseteq N$, i.e., $N=SL(2,\mathbb R)$.

Filed under Linear Algebra

## Simple Cases of Jacobson’s Theorem

A celebrated theorem of Jacobson states that

Theorem. Let $R$ be a ring, not necessarily containing $1$. If, for each $a\in R$ there exists a positive integer $n$ such that $a^n=a$, then $R$ is commutative.

This is a very strong and difficult result (albeit not very useful in practice). However, we can obtain some special cases via elementary means.

Proposition 1. Let $R$ be a ring such that for each $a\in R$ we have $a^2=a$. Then $R$ is commutative.

Proof. Let $a,b\in R$. Then $a+b=(a+b)^2=a^2+ab+ba+b^2=a+ab+ba+b$, i.e., $ab=-ba$. Again, $a-b=(a-b)^2=a^2-ab-ba+b^2=a-ab-ba+b$, i.e., $ab=-ba+2b$. Thus $2b=0$, i.e., $b=-b$ for each $b\in R$. Thus $ab=-ba=ba$, as desired. $\square$

The next case is already considerably harder.

Proposition 2. Let $R$ be a ring such that for each $a\in R$ we have $a^3=a$. Then $R$ is commutative.

Proof. Let $a,b\in R$. Then $a+b=(a+b)^3$ shows that

$(*) \qquad a^2b+aba+ba^2+ab^2+bab+b^2a=0$,

and $a-b=(a-b)^3$ shows that

$a^2b+aba+ba^2=ab^2+bab+b^2a$.

Hence

$(**) \qquad 2(a^2b+aba+ba^2)=0$

for all $a,b\in R$.

Plugging $a=b$ into $(**)$ gives $6a=0$, i.e., $3a=-3a$ for each $a\in R$.

Plugging $b=a^2$ into $(*)$ gives $3(a^2+a)=0$, i.e., $3a^2=3a$ for each $a\in R$. Replacing $a$ by $a+b$ gives $3(ab+ba)=0$, i.e., $3(ab-ba)=0$.

Also, multiplying $(**)$ by $a$ first on the left and then on the right and then subtracting the two gives $2(ab-ba)=0$.

From the last two paragraphs we conclude that $ab-ba=0$ for all $a,b \in R$. $\square$

Corollary. Let $R$ be a ring such that for each $a \in R$ we have $a^n=a$ for some integer $n \in [0, 3]$. Then $R$ is commutative.

Proof. Note that if $a^n=a$ for some integer $n \in [0, 3]$ then $a^3=a$. Hence the result follows by Proposition 2. $\square$

Filed under Algebra

## A Nice Group Theory Result

While working on some group theory problems today a friend and I came up with the following result.

Lemma. Let $H$ be a normal subgroup of a finite group $G$ such that $\gcd(|H|,|G/H|)=1$. If the order of $g\in G$ divides $|H|$, then $g\in H$.

Proof. Let $d$ be the order of $g$. Then the order $d'$ of $gH$ in $G/H$ divides both $d$ and $|G/H|$. But $\gcd(d,|G/H|)=1$. Hence $d'=1$, i.e., $gH=H$, i.e., $g\in H$. $\square$

Corollary 1. Let $H$ be a normal subgroup of a finite group $G$ such that $\gcd(|H|,|G/H|)=1$. If $K\le G$ such that $|K|$ divides $|H|$, then $K\le H$.

Proof. Apply the lemma to the elements of $K$. $\square$

Corollary 2. Let $H$ be a normal subgroup of a finite group $G$ such that $\gcd(|H|,|G/H|)=1$. Then $H$ is the unique subgroup of $G$ of order $|H|$.

Proof. Use Corollary 1. $\square$

Here is an example of the lemma in action.

Problem. Show that $S_4$ has no normal subgroup of order $8$ or $3$.

Solution. If $H$ is a normal subgroup of $S_4$ of order $8$, then $\gcd(|H|,|S_4/H|)=1$. Hence every element of order $2$ or $4$ in $S_4$ must lie in $H$. In particular, $(1\ 2),(1\ 2\ 3\ 4)\in H$. By a result in the previous post, $H=S_4$, a contradiction.

Likewise, if $H$ is a normal subgroup of $S_4$ of order $3$, then $H$ must contain every 3-cycle; in particular, $(1\ 2\ 3),(2\ 3\ 4)\in H$. Hence $(1\ 2\ 3)(2\ 3\ 4)=(1\ 2)(3\ 4)\in H$. But this has order 2, and $2\nmid 3$, a contradiction. $\square$

More generally, we can prove the following.

Corollary 3. $S_n$ for $n\ge 4$ has no non-trivial proper normal subgroup $H$ with $\gcd(|H|,|S_n/H|)=1$.

Proof. Suppose otherwise and let $d$ divide $|H|$. Then $H$ must contain all $d$-cycles. So if $|H|$ is even then taking $d=2$ gives $H=S_n$. If $|H|$ is odd, it contains the cycles $\sigma=(1\ \cdots\ d)$ and $\rho=(d\ \cdots\ 2\ n)$ for some $3\le d. Then $\sigma\rho=(1\ 2\ n)\in H$ has order 3. So $|H|$ contains all 3-cycles, i.e., $A_n\le H$. Since $A_n\le S_n$ is maximal, either $H=A_n$ or $H=S_n$, a contradiction. $\square$

1 Comment

Filed under Algebra