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 »

In this post I describe how simple facts about polynomials are applied in correcting errors, for example scratches on compact disks.  The same technique is used in many other places, e.g. in the 2-dimensional QuickResponse  bar codes.

Elements

The two facts from algebra that we need are:

Theorem 1. A polynomial of degree \(n\) has at most \(n\) zeros.

Theorem 2. If \((x_1,y_1),(x_2,y_2),\ldots,(x_n,y_n)\) are \(n\) points on the \(xy\)-plane such that \(x_i\neq x_j\) whenever \(i\neq j\), then there is a unique polynomial \(f(x)\) of degree \(<n\) such that \(f(x_i)=y_i\) for all \(i\).

So, if \(n=2\), we want the polynomial \(f(x)\) to be linear. In that case, the graph \(y=f(x)\) will be the line passing through the points \((x_1,y_1)\) and \((x_2,y_2)\). Similarly, when \(n=3\) we want the polynomial to be (at most) quadratic, and we want its graph to pass through the given three points. Finding the coefficients of such a quadratic is not too arduous an exercise in linear systems of equations. For general \(n\) there is a known formula for the polynomial \(f(x)\) called Lagrange’s interpolation polynomial . The uniqueness of such a polynomial follows from Theorem 1. If \(f_1(x)\) and \(f_2(x)\) were two different polynomials of degree \(<n\) passing through all these \(n\) points, then their difference \(f_1(x)-f_2(x)\) is also of degree \(<n\) and vanishes at all the points \(x_i, i=1,2,\ldots,n\), which is impossible by Theorem 1.

Extending a message using a polynomial

The applications I discuss are about communication. We have two parties, a transmitter and a receiver. The transmitter wants to send a message to the receiver. We assume that they have in advance agreed upon a method of coding the messages to sequences of numbers \(y_1,y_2,\ldots,y_k\) for some natural number \(k\). The simplest way of communicating would be for the transmitter to simply write this list of numbers to a channel that the receiver can later read. The channel could be something like a note that you pass to a classmate or it could be compact disk, where the transmitter just writes the numbers. It could be something fancier like a radio frequency band, or an optical fiber, but we ignore the physical nature of the channel here.

more »

There are no doubts that open mapping theorem, closed graph theorem, bounded inverse theorem, uniform boundedness principle are the fundamental theorems of functional analysis. All of them are similar in the sense that they explicitly or implicitly use the Baire category theorem, but in the details they are different. However, all these theorems can be formulated as continuity of certain seminorms defined on a normed spaces.

The proof of the lemma is very similar to the usual proof by Banach-Schauder of the open mapping theorem and is actually stronger than the usual consequences of the Baire category theorem in basic functional analysis. The lemma can be used to easily prove the aforementioned theorems.

I would like to thank the user t.b. for drawing our attention to this lemma and adaptation of the original proof from the general case of linear metric spaces, which he gave as an answer to the question Direct Approach to the Closed Graph Theorem on the main site.

Lemma. (Zabreiko, [1], [2]) Let \(X\) be a Banach space and let \(p: X \to [0,\infty)\) be a seminorm. If for all absolutely convergent series \(\sum_{n=1}^\infty x_n\) in \(X\) we have \[ p\left(\sum_{n=1}^\infty x_n\right) \leq \sum_{n=1}^\infty p(x_n) \in [0,\infty] \] then \(p\) is continuous. That is to say, there exists a constant \(C \geq 0\) such that \(p(x) \leq C\lvert x\rvert _{X}\) for all \(x \in X\).

Proof. Let \(A_n = p^{-1}([0,n])\) and \(F_n = \overline{A_n}\). Note that \(A_n\) and \(F_n\) are symmetric and convex because \(p\) is a seminorm. We have \(X = \bigcup_{n=1}^\infty F_n\) and Baire’s theorem implies that there is \(N\) such that the interior of \(F_N\) is nonempty.

Therefore, there are \(x_0 \in X\) and \(R \gt 0\) such that \(B_R(x_0) \subset F_N\). By symmetry of \(F_N\) we have \(B_{R}(-x_0) = -B_{R}(x_0) \subset F_n\), too. If \(\lvert x\rvert \lt R\) then \(x+x_0 \in B_{R}(x_0)\) and \(x-x_0 \in B_{R}(-x_0)\), so \(x \pm x_0 \in F_{N}\). By convexity of \(F_N\) it follows that \[ x = \frac{1}{2}(x-x_0) + \frac{1}{2}(x+x_0) \in F_N, \] so \(B_R(0) \subset F_N\). But, in fact, we can prove much more: \[ B_{R}(0) \subset A_N \] Suppose \(\lvert x\rvert \lt R\) and choose \(r\) such that \(\lvert x\rvert \lt r \lt R\). Fix \(0 \lt q \lt 1-\frac{r}{R}\), so \(\frac{1}{1-q} \frac{r}{R} \lt 1\). Then \(y = \frac{R}{r}x \in B_{R}(0) \subset F_N = \overline{A_N}\), so there is \(y_{0} \in A_N\) such that \(\lvert y-y_0\rvert \lt qR\), so \(q^{-1}(y-y_0) \in B_R\). Now choose \(y_1 \in A_N\) with \(\lvert q^{-1}(y-y_0) – y_1\rvert \lt q R\), so \(\lvert (y-y_0 – qy_1)\rvert \lt q^2 R\). By induction we obtain a sequence \( (y_k)\subset A_N\) such that \[ \left\lvert y – \sum_{k=0}^n q^k y_k\right\rvert \lt q^n R \quad \text{for all }n \geq 0, \] hence \(y = \sum_{k=0}^\infty q^k y_k\). Observe that by construction \(|y_k| \leq R + qR\) for all \(k\), so the series \(\sum_{k=0}^\infty q^k y_k\) is absolutely convergent. But then the countable subadditivity hypothesis in \(p\) implies that \[ p(y) = p\left(\sum_{k=0}^\infty q^k y_k\right) \leq \sum_{k=0}^\infty q^k p(y_k) \leq \frac{1}{1-q} N \] and thus \(p(x) \leq \frac{r}{R} \frac{1}{1-q} N \lt N\) which means \(x \in A_N\), as we wanted.

Finally, for any \(x \neq 0\), we have with \(\lambda = \frac{R}{\lvert x\rvert (1+\varepsilon)}\) that \(\lambda x \in B_{R}(0) \subset A_N\), so \(p(\lambda x) \leq N\) and thus \(p(x) \leq \frac{N(1+\varepsilon)}{R} \lvert x\rvert \), as desired. \(\blacksquare\)

Now the proof of the fundamental theorems becomes an easy exercise.

1. The open mapping theorem. Hint: set \(p(y) = \inf_{x\in T^{-1}(y)}\lvert x\rvert \).
2. The bounded inverse theorem. Hint: set \(p(x) = \lvert T^{-1}(x)\rvert \).
3. The uniform boundedness principle. Hint: set \(p(x) = \sup_{i\in I}\lvert T_i (x)\rvert \).
4. The closed graph theorem. Hint: set \(p(x) = \lvert T(x)\rvert \).

Detailed solutions can be found in theorems \(1.6.5\), \(1.6.6\), \(1.6.9\) and \(1.6.11\) in An Introduction to Banach Space Theory Graduate Texts in Mathematics. Robert E. Megginson.

[1] П. П. Забрейко, Об одной теореме для полуаддитивных функционалов, Функциональный анализ и его приложения, 3:1 (1969), 86–88

[2] P. P. Zabreiko, A theorem for semiadditive functionals, Functional analysis and its applications 3 (1), 1969, 70-72)

A recent question on math.stackexchange asks for the smallest positive number \( A \) for which the number \( 2A \) has the same decimal digits in some other order.

Math geeks may immediately realize that \( 142857 \) has this property, because it is the first 6 digits of the decimal expansion of \( \frac 17 \), and the cyclic behavior of the decimal expansion of \( \frac n7 \) is well-known. But is this the minimal solution? It is not. Brute-force enumeration of the solutions quickly reveals that there are 12 solutions of 6 digits each, all permutations of \( 142857 \), and that larger solutions, such as \( 1025874 \) and \( 1257489 \), seem to follow a similar pattern. What is happening here?

Stuck in Dallas-Fort Worth airport last month, I did some work on the problem, and although I wasn’t able to solve it completely, I made significant progress. I found a method that allows one to hand-calculate that there is no solution with fewer than six digits, and to enumerate all the solutions with 6 digits, including the minimal one. I found an explanation for the surprising behavior that solutions tend to be permutations of one another. The short form of the explanation is that there are fairly strict conditions on which sets of digits can appear in a solution of the problem. But once the set of digits is chosen, the conditions on that order of the digits in the solution are fairly lax.

So one typically sees, not only in base 10 but in other bases, that the solutions to this problem fall into a few classes that are all permutations of one another; this is exactly what happens in base 10 where all the 6-digit solutions are permutations of \( 124578 \). As the number of digits is allowed to increase, the strict first set of conditions relaxes a little, and other digit groups can (and do) appear as solutions.

Notation

The property of interest, \( P_R(A) \), is that the numbers \( A \) and \( B=2A \) have exactly the same base-\( R \) digits. We would like to find numbers \( A \) having property \( P_R \) for various \( R \), and we are most interested in \( R=10 \). Suppose \( A \) is an \( n \)-digit numeral having property \( P_R \); let the (base-\( R \)) digits of \( A \) be \( a_{n-1}\ldots a_1a_0 \) and similarly the digits of \( B = 2A \) are \( b_{n-1}\ldots b_1b_0 \). The reader is encouraged to keep in mind the simple example of \( R=8, n=4, A=\mathtt{1042}, B=\mathtt{2104} \) which we will bring up from time to time.

Since the digits of \( B \) and \( A \) are the same, in a different order, we may say that \( b_i = a_{P(i)} \) for some permutation \( P \). In general \( P \) might have more than one cycle, but we will suppose that \( P \) is a single cycle. All the following discussion of \( P \) will apply to the individual cycles of \( P \) in the case that \( P \) is a product of two or more cycles. For our example of \( A=\mathtt{1042}, B=\mathtt{2104} \), we have \( P = (0\,1\,2\,3) \) in cycle notation. We won’t need to worry about the details of \( P \), except to note that \( i, P(i), P(P(i)), \ldots, P^{n-1}(i) \) completely exhaust the indices \( 0. \ldots n-1 \), and that \( P^n(i) = i \) because \( P \) is an \( n \)-cycle.

more »

A common method used to find the area of a polygon is to break the polygon into smaller shapes of known area. For example, one can separate the polygon below into two triangles and a rectangle:

By breaking this composite shape into smaller ones, the area is at hand: $$\begin{align}A_1 &= bh = 5\cdot 2 = 10 \\ A_2 = A_3 &= \frac{bh}{2} = \frac{2\cdot 1}{2} = 1 \\ A_{total} &= A_1+A_2+A_3 = 12\end{align}$$

Unfortunately, this approach can be difficult for a person to use when they cannot physically (or mentally) see the polygon, such as when a polygon is given as a list of many vertices.

Formula

Happily, there is a formula for the area of any simple polygon that only requires knowledge of the coordinates of each vertex. It is as follows: $$A = \sum_{k=0}^{n} \frac{(x_{k+1} + x_k)(y_{k+1}-y_{k})}{2} \tag{1}$$ (Where \({n}\) is the number of vertices, \({(x_k, y_k)}\) is the \({k}\)-th point when labelled in a counter-clockwise manner, and \({(x_{n+1}, y_{n+1}) = (x_0, y_0)}\); that is, the starting vertex is found both at the start and end of the list of vertices.)

It should be noted that the formula is not “symmetric” with respect to the signs of the \({x}\) and \({y}\) coordinates. This can be explained by considering the “negative areas” incurred when adding the signed areas of the triangles with vertices \({(0,0)-(x_k, y_k)-(x_{k+1}, y_{k+1})}\).

In the next sections, I derive this formula using Green’s Theorem, show an example of its use, and provide some applications.

more »

Welcome to the Math StackExchange community blog!

Four years ago today, Dan Dumitru proposed the creation of Math.StackExchange. The site has evolved into a community with hundreds of thousands of questions and answers, and over 30 thousand questions and answers appearing each month.

Now, we have a blog.

This blog provides a way of going beyond the Q&A format to allow exposition and discussion. There might be posts about mathematics, or Math.SE, or a book review, or whatever seems appropriate. Anyone can contribute to the blog. This blog is written and edited by community members, and we are actively soliticing both one-time and regular contributors! So if you have an idea of something you’d like to hear about or read about, or if you would like to contribute, check out the blog chat room and the Blog FAQ thread on meta.

I’m looking forward to see what we make here.