Archive for August, 2014

Introduction

Today we will play a small game which is really really simple. We will add up numbers to make numbers. And to keep the matters simple we will only deal with counting numbers \(1, 2, 3, \ldots\) As an example \(2 + 3 = 5\), but to make the game challenging we would reverse the problem. Let’s ask how we can split \(5\) into sum of other numbers. For completeness we take \(5\) also as one of the ways to express \(5\) as sum of numbers. Clearly we have the following other ways $$ 5 = 4 + 1 = 3 + 1 + 1 = 3 + 2 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1$$ so that there are \(7\) different ways of adding numbers to make \(5\). We don’t take into account the order of summands. Also one number can be repeated if needed.

Partitions of a Number

It turns out that a whole generation of distinguished mathematicians (Euler, Jacobi, Ramanujan, Hardy, Rademacher etc) were also interested in playing the above game. And needless to say, they made the whole thing very systematic by adding some definitions (its their silly habit so to speak). Following their footprints we say that a tuple \((n_{1}, n_{2}, \ldots, n_{k})\) of positive integers is a partition of a positive integer \(n\) if $$n_{1} \geq n_{2} \geq \cdots \geq n_{k}\text{ and }n_{1} + n_{2} + \cdots + n_{k} = n$$ Thus \((3, 2), (3, 1, 1)\) etc are partitions of \(5\). If \((n_{1}, n_{2}, \ldots, n_{k})\) is a partition of \(n\) then we say that each of the \(n_{i}\) is a part of this partition, \(k\) is the number of parts, \(n_{1}\) is the greatest part and \(n_{k}\) the least part of this partition.

The mathematicians were really not so interested in finding individual partitions of a number \(n\), but were rather interested in finding out the total number of partitions of \(n\). The example above deals with \(n = 5\) and clearly there are \(7\) partitions of \(5\). You should convince yourself by taking a slightly larger number, say \(n = 8\) or \(n = 10\), that finding the number of partitions of any given number \(n\) is not that easy. Especially writing out each partition of \(n\) and then counting them all is very difficult. You may always feel that probably you have missed one of the partitions. Mathematicians however found out a smart way to count partitions. We explore this technique further.

more »

I wrote an article with Irving Kaplansky on indefinite binary quadratic forms, integral coefficients. At the time, I believe I used high-precision continued fractions or similar. It took me years to realize that the right way to solve Pell’s equation, or find out the “minimum” of an indefinite form (and other small primitively represented values), or the period of its continued fraction, was the method of “reduced” forms in cycles/chains, due to Lagrange, Legendre, Gauss. It is also the cheapest way to find the class number and group multiplication for ideals in real quadratic fields, this probably due to Dirichlet. For imaginary quadratic fields, we have easier “reduced” positive forms.

A binary quadratic form, with integer coefficients, is some $$ f(x,y) = A x^2 + B xy + C y^2. $$ The discriminant is $$ \Delta = B^2 – 4 A C. $$ We will abbreviate this by $$ \langle A,B,C \rangle. $$ It is primitive if \({\gcd(A,B,C)=1. }\) Standard fact, hard to discover but easy to check: $$ (A x^2 + B x y + C D y^2 ) (C z^2 + B z w + A D w^2 ) = A C X^2 + B X Y + D Y^2,$$ where \({ X = x z – D yw, \; Y = A xw + C yz + B yw. }\) This gives us Dirichlet’s definition of “composition” of quadratic forms of the same discriminant, $$ \langle A,B,CD \rangle \circ \langle C,B,AD \rangle = \langle AC,B,D \rangle. $$ In particular, if this \({D=1,}\) the result represents \({1}\) and is (\({SL_2 \mathbb Z}\)) equivalent to the “principal” form for this discriminant. Oh, duplication or squaring in the group; if \({\gcd(A,B)=1,}\) $$ \langle A,B,AD \rangle^2 = \langle A^2,B,D \rangle. $$ This comes up with positive forms: \({ \langle A,B,C \rangle \circ \langle A,-B,C \rangle = \langle 1,B,AC \rangle }\) is principal, the group identity. Probably should display some \({SL_2 \mathbb Z}\) equivalence rules, these are how we calculate when things are not quite right for Dirichlet’s rule: $$ \langle A,B,C \rangle \cong \langle C,-B,A \rangle, $$ $$ \langle A,B,C \rangle \cong \langle A, B + 2 A, A + B +C \rangle, $$ $$ \langle A,B,C \rangle \cong \langle A, B – 2 A, A – B +C \rangle. $$

more »