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].

Leave a comment

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<j}\left\lfloor\frac{n}{p_ip_j}\right\rfloor-\sum_{i<j<k}\left\lfloor\frac{n}{p_ip_jp_k}\right\rfloor+\cdots\\&< n\left(1-\frac{1}{p_1}\right)\cdots\left(1-\frac{1}{p_k}\right)+2^{k-1}.\end{aligned}

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)<k+2^{k-1}.

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.)

Leave a comment

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).

2 Comments

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

Leave a comment

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<n. 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