## Archive for June, 2010

June 20, 2010

Let ${O(m,r)}$ be the number of integral points in the ${m}$-dimensional octahedron of radius ${r}$:

$\displaystyle O(m,r)= \Bigl|\{(x_1,\ldots, x_m)\in {\mathbb Z}^m: |x_1|+\cdots+|x_m|\le r\}\Bigr|.$

A standard combinatorial argument shows that for positive integers ${m}$ and ${n}$

$\displaystyle O(m,n)=\sum_{k=0}^{\min\{m,n\}} 2^k \binom mk \binom nk,$

and, in particular,

$\displaystyle O(m,n)=O(n,m). \ \ \ \ \ (1)$

Is it possible to give a “geometric” interpretation (or any other “conceptual” interpretation) of identity (1)?

Update
A satisfactory answer was given by Allison and Mark Lewko, see the comments.

### Liouville vs Cantor

June 14, 2010

I do not know who is the author of this bad joke, but it is appalling that even qualified mathematicians often say that Cantor’s proof of existence of transcendental numbers is non-constructive, as opposed to Liouville’s proof.

Let me recall that Liouville proved that the infinite sum ${\sum 2^{-n!}}$ is transcendental, while Cantor proved that the set of algebraic numbers is countable, but the set of reals is uncountable.

Dear colleagues, Cantor’s proof is less “constructive” than Liuoville’s only on emotional or aesthetic level. Mathematically, both are equally constructive.

Indeed, the only way I can imagine of defining a real number “constructively” is providing an algorithm for computing rational approximations to it of any prescribed precision. More formally, call a real number ${\alpha}$ constructible if there exists an algorithm (a Turing machine) which, having a natural number ${n}$ at the input, produces at the output a rational approximation to ${\alpha}$ with precision ${1/n}$. I do not know another reasonable (non-equivalent) definition of a constructible real number; if anybody knows, I would be happy if he shares it with me.

Of course, the Liouville number ${\sum 2^{-n!}}$ is constructible, the good rational approximations being the partial sums of the infinite series.

Further, call a sequence ${(\alpha_n)}$ constructible if there exists an algorithm, which, having natural ${m}$ and ${n}$ at the input, produces a rational approximation to ${a_n}$ with precision ${1/m}$ at the output.

Now two simple exercises.

1. Show that there exists a constructible sequence containing all algebraic numbers.
2. Show that for any constructible sequence, there exists a constructible number not contained in this sequence.

A careful examination of Cantor’s proof reveals that its first part solves the first exercise, and the second part solves the second exercise.

I would never waste time for recalling these trivialities in my precious blog if this misunderstanding were not so widespread even among professional mathematicians.