# Monthly Archives: November 2014

## A combinatorial approach to multiplicative functions

As usual, let $\mathbb N$ denote the set of the positive integers. A function $f$ defined on $\mathbb N$ is said to be multiplicative if $f(mn)=f(m)f(n)$ for every pair of coprime integers $m,n\in\mathbb N$. Many well-known arithmetic functions are multiplicative, for instance:

1. The number of divisors of $n$: $\tau(n)$
2. The sum of divisors of $n$: $\sigma(n)$
3. More generally, the sum of the $k$-th powers of the divisors of $n$: $\sigma_k(n)$ (note that $\tau(n)=\sigma_0(n)$ and $\sigma(n)=\sigma_1(n)$)
4. Euler’s function, $\varphi(n)$: the number of positive integers not exceeding $n$ that are coprime to $n$

And many more. (See here for a more comprehensive list.)

Many arithmetic functions $F(n)$ can be represented as

$\displaystyle F(n)=\sum_{d\mid n}f(d)$

for some arithmetic function $f(n)$. For example, $\displaystyle \tau(n)=\sum_{d\mid n} 1$, $\displaystyle \sigma(n)=\sum_{d\mid n} d$, or $\displaystyle \sigma_k(n)=\sum_{d\mid n} d^k$, in general.

Lemma. If

$\displaystyle F(n)=\sum_{d\mid n}f(d)$

and $f$ is multiplicative, then so is $F$.

Proof. For $m,n$ coprime,

$\displaystyle F(mn)=\sum_{d\mid mn}f(d)=\sum_{\substack{d_1\mid m\\ d_2\mid n}}f(d_1d_2)$

$\displaystyle=\sum_{\substack{d_1\mid m\\ d_2\mid n}}f(d_1)f(d_2)=\sum_{d_1\mid m}f(d_1)\sum_{d_2\mid n}f(d_2)=F(m)F(n).\quad \square$

This little lemma shows that $\tau(n)$, $\sigma(n)$, or $\sigma_k(n)$ in general, is multiplicative for each $k$.

However, my original intention was to illustrate a combinatorial reasoning proving that these functions are multiplicative!

Let us first consider the divisor function $\tau(n)$. Let $m,n$ be coprime. Note that each divisor of $mn$ is of the form $d_1d_2$ where $d_1\mid m$ and $d_2\mid n$; further, each such pair $(d_1,d_2)$ corresponds to a unique divisor of $n$. Thus there is a bijection between the sets

$\{d:d\mid mn\}$ and $\{(d_1,d_2):d_1\mid m, d_2\mid n\}$

which implies $\tau(mn)=\tau(m)\tau(n)$. And the same idea works for $\sigma_k(n)$ in general.

Okay that actually wasn’t different from our previous proof. But the next one will be! Consider the Euler function $\varphi(n)$ this time. Again, let $m,n$ be coprime. Let $(\mathbb Z/n\mathbb Z)^\times$ denote the set of elements from $\{1,2,\dots,n\}$ that are coprime to $n$. If $a$ is coprime to $mn$, then $a$ is coprime to each of $m,n$. Further, each pair $(a_1,a_2)\in (\mathbb Z/m\mathbb Z)^\times\times(\mathbb Z/n\mathbb Z)^\times$ corresponds to a unique $a\in(\mathbb Z/mn\mathbb Z)^\times$ by the Chinese remainder theorem (in modern notation we write

$\displaystyle (\mathbb Z/mn\mathbb Z)^\times\cong(\mathbb Z/m\mathbb Z)^\times\times(\mathbb Z/n\mathbb Z)^\times$

as groups.) Thus we have a bijection between the sets, and so

$\varphi(mn)=|(\mathbb Z/mn\mathbb Z)^\times|=|(\mathbb Z/m\mathbb Z)^\times|\cdot |(\mathbb Z/mn\mathbb Z)^\times|=\varphi(m)\varphi(n)$

The underlying strategy in the above proofs can be outlined as follows:

1. Take a hypothetical multiplicative function $f(n)$
2. Find a set $S(n)$ such that $f(n)=|S(n)|$
3. Find a bijection between $S(mn)$ and $S(m)\times S(n)$ for coprime $m,n$.

If we want to show that a function is totally multiplicative, we can replace ‘coprime’ by ‘arbitrary’ in 3.

1 Comment

Filed under Combinatorics, Number theory

## A ‘sum of squares’ problem

Recently I came to know from a friend that the only non-trivial value of $n$ satisfying the Diophantine equation

$1^2+2^2+\dots+n^2=m^2$

is $n=24$. And apparently, although the problem looks fairly simple, especially since we have the formula for the left hand side

$\displaystyle 1^2+2^2+\dots+n^2=\frac{n(n+1)(2n+1)}{6}$

the proof is hard. In fact, I was told that all proofs of this result use advanced machinery. Nevertheless, given the simple nature of the problem I was intrigued to give it a try.

So let us assume that

$n(n+1)(2n+1)=6m^2$.

Noting that $2n(n+1)-n(2n+1)=n$, we have that $n(n+1)$ and $2n+1$ are coprime. Indeed, if $g$ is a common factor, then $g$ has to divide both $n$ and $2n+1$, forcing $g=1$. So we deduce that

$\{n(n+1),2n+1\}=\{a^2,6b^2\}$ or $\{2a^2,3b^2\}$

for some integers $a,b$.

Note that $2n+1\not\in \{2a^2,6b^2\}$ so $2n+1\in\{a^2,3b^2\}$. Hence the possibilities are:

(i) $n(n+1)=2a^2$, $2n+1=3b^2$.

(ii) $n(n+1)=6b^2$, $2n+1=a^2$.

First suppose that $n(n+1)=2a^2$. Then $n(n+1)/2=a^2$ is a square triangular number, so

$n=\displaystyle\frac{H_{2k}-1}{2}$

for some $k$, where $P_0,P_1,\dots$ are the Pell numbers. and $H_0,H_1,\dots$ are the half-companion Pell numbers, and they are given by $(1+\sqrt 2)^k=H_k+P_k\sqrt 2$ for each $k$. So we have to find all $k$ such that

$2n+1=\boxed{H_{2k}=3b^2}$.

On the other hand, if $2n+1=a^2$, then $a=2c-1$ for some integer $c$. Then $n=2c(c-1)$. Hence $n(n+1)=6b^2$ implies

$c(c-1)(2c^2-2c+1)=3b^2$.

Now $\gcd(c(c-1),2c^2-2c+1)=1$, so $\{c(c-1),2c^2-2c+1\}=\{u^2,3v^2\}$ for some integers $u,v$. Clearly $c(c-1)\neq u^2$, so

$c(c-1)=3v^2$ and $2c^2-2c+1=u^2$.

So $\{c,c-1,u\}$ is a near isosceles Pythagorean triple, i.e.

$c=\displaystyle\frac{H_{2k-1}+1}{2}$.

Hence

$\boxed{H_{2k-1}^2-1=12v^2\Leftrightarrow P_{2k-1}^2-1=6v^2\Leftrightarrow P_{2k}P_{2k-2}=6v^2}$.

The two boxed cases are what only remain to check, and they show why this actually is a difficult problem! (Refer to the articles about Fibonacci numbers in the ‘Notes and Articles’ tab above to see how little information we have on divisors of sequences of this kind.) Nevertheless, I’ll leave it here and maybe come back to it another time.

1 Comment

Filed under Number theory

## A nice result on arithmetic progressions

Let $\mathbb N_0$ denote the set of the non-negative integers. For a subset $S\subseteq\mathbb N_0$, we can define the ‘counting function’

$\pi_S(x):=|\{n\in\mathbb N_0\cap S:n\le x\}|$

i.e. $\pi_S(x)$ is the number of elements in $S$ that are at most $x$. Then we can define the (asymptotic) density of $S$ as

$\displaystyle \delta(S):=\lim_{x\to\infty}\frac{\pi_S(x)}{x}$

when this limit exists.

For example, the set of the even (resp. odd) numbers has density $1/2$. More generally, any arithmetic progression $a+d\mathbb N_0:=\{a+dn:n\in\mathbb N_0\}$ has density $1/d$. Another example is the set of prime numbers, which has density $0$ by the prime number theorem. From this it also follows that the set of composite numbers has density $1$.

Theorem. If a finite union of arithmetic progressions of positive integers has density $1$, then it contains all sufficiently large positive integers.

Proof. Let

$\displaystyle A=\bigcup_{i=1}^k(a_i+d_i\mathbb N_0)$

be a finite union of arithmetic progressions such that $\delta(A)=1$. Note that (this is the main trick) we can write:

$\displaystyle A=\bigcup_{i=1}^k(a_i+d_i\mathbb N_0)=\bigcup_{j=1}^l(b_i+d\mathbb N_0)$

for some $b_1,\dots,b_l$, where $d$ is the least common multiple of $d_1,\dots,d_k$.

Why can we do this? Consider for example $(1+2\mathbb N_0)\cup(2+3\mathbb N_0)$. We can write this as

$\displaystyle \underbrace{(1+6\mathbb N_0)\cup (3+6\mathbb N_0)\cup (5+6\mathbb N_0)}_{1+2\mathbb N_0}\cup \underbrace{(2+6\mathbb N_0)\cup (5+6\mathbb N_0)}_{2+3\mathbb N_0}$

$\displaystyle =(1+6\mathbb N_0)\cup (2+6\mathbb N_0)\cup (3+6\mathbb N_0)\cup (5+6\mathbb N_0)$

And this idea works for any finite union of arithmetic progressions.

It is then clear that $\{b_1,\dots,b_l\}$ has to be a complete set of residues modulo $d$, because otherwise $A$ would have density strictly less than $1$. Therefore $A$ has to contain all positive integers $\ge\max\{b_1,\dots,b_l\}$. $\square$

We get the following nice corollary:

Corollary. The set of all composite numbers cannot be expressed as a finite union of arithmetic progressions of positive integers.

Proof. Otherwise by the above theorem all sufficiently large positive integers would be composite, contradicting the fact that there are infinitely many primes. $\square$