# Uniformly at Random

## Expansions in irrational bases

Let $\beta$ be an irrational real number between 1 and 2. Let us write the expansion of 1 in base-$\beta$:

$1 = \sum_{n=1}^\infty a_n \beta^{-n},$

where $a_n \in \{0,1\}$.  (We leave it to the reader to speculate as to why one would do such a perverse thing.)  $\beta$-expansions are not generally unique.  For example, let $\varphi = (1 + \sqrt{5})/2$ be the golden ratio.  Then $1 = \varphi^{-1} + \varphi^{-2}$ and $1 = \sum_{n \geq 2} \varphi^{-n}$, so $.11$ and $.01111\cdots$ are both $\varphi$-expansions of 1. However, there are certain curious irrational numbers $\beta$ for which 1 has a unique $\beta$-expansion.  Moreover, there is a even a least $\beta$ between 1 and 2 with this property.  This $\beta$ is the unique solution (approx 1.78723…) to

$1 = \sum_{n = 1}^{\infty} t_n \beta^{-n},$

where $t_n$ is the number of 1’s mod 2 in the binary expansion of $n$.  (It seems rather bizarre that the parity of 1’s in the binary expansion of $n$ should have anything to do with this problem!)  This $\beta$ is called the Komornik-Loreti constant.  For the proof of this result see the paper of Komornik and Loreti in the American Mathematical Monthly 105 (1998) 636-639.

Written by uncudh

April 20, 2009 at 3:57 pm

Posted in math

Tagged with ,

## The Khinchin-Levy Theorem

To me, one of the most surprising results in number theory is the Khinchin-Levy Theorem.  This theorem states that for almost all (in the sense of Lebesgue measure) real numbers $\alpha$, the denominators $q_n$ of the convergents of the continued fraction expansion of $\alpha$ satisfy

$\lim_{n \to \infty} q_n^{1/n} = e^{\pi^2/(12 \log 2)}$.

The quantity on the right hand side is the so-called Khinchin-Levy constant.  This result is surprising for several reasons:

1. Why should the limit even exist?
2. Why should it have the same value for almost all $\alpha$?
3. Why should its value involve the three constants $e$, $\pi$, and $\log 2$?

Bizarre!

A proof of the Khinchin-Levy Theorem using probability theory can be found in the book Continued Fractions by Rockett and Szusz; it can also be proved using the Ergodic Theorem.

Written by uncudh

March 8, 2009 at 2:40 am

Posted in math

Tagged with ,

## Determining if a linear recurrence sequence contains a zero

Let $(a_i)_{i \geq 0}$ be an integer sequence satisfying a linear recurrence $a_i - c_{1}a_{i-1} - \cdots - c_d a_{i-d} = 0$ for some $d$. One wishes to determine if the sequence contains a zero. The Skolem-Mahler-Lech Theorem characterizes the indices of the zeros of such a sequence as forming a finite union of arithmetic progressions, but the proof is not effective. Blondel and Portier showed that the problem of determining if a linear recurrence sequence has a zero is NP-hard, but it is not known if the problem is even decidable. We give here the NP-hardness proof.

The reduction is from the following problem concerning finite automata, which was shown to be NP-complete by Stockmeyer and Meyer in 1973.

Given a non-deterministic finite automaton over a unary alphabet, determine if the automaton rejects some input.

Let $M$ be a unary non-deterministic finite automaton. Let us suppose that the states of $M$ are labeled $1,2,\ldots,n$ and let us suppose further that state $1$ is the initial state. We construct the $n \times n$ adjacency matrix $A$ of $M$ by defining $A_{ij} = 1$ if $M$ has a transition from state $i$ to state $j$, and $A_{ij} = 0$ otherwise. Let $u$ be the $n$-vector with a $1$ in the first position and $0$‘s elsewhere. Let $v$ be the $n$-vector with a $1$ in position $k$ if state $k$ is an accepting state of $M$, and a $0$ in position $k$ otherwise. It is not hard to see that $u^T A^\ell v$ is the number of paths in $M$ of length $\ell$ from the initial state to an accepting state. Thus, $M$ rejects a length $\ell$ input if and only if $u^T A^\ell v = 0$. That is, $M$ rejects some input if and only if the sequence $(q_\ell)_{\ell \geq 0} = (u^T A^\ell v)_{\ell \geq 0}$ contains a zero.

We now construct a linear recurrence satisfied by this sequence. Let $p(x) = \det(xI - A) = x^n - a_{n-1}x^{n-1} - \cdots - a_1x - a_0$ be the characteristic polynomial of $A$. We claim that $(q_\ell)_{\ell \geq 0}$ satisfies the linear recurrence $q_{n+\ell} - a_{n-1}q_{n-1+\ell} - \cdots - a_0 q_\ell = 0$. We have

$q_{n+\ell} - a_{n-1}q_{n-1+\ell} - \cdots - a_0 q_\ell$

$= u^T A^{n+\ell} v - a_{n-1} u^T A^{n-1+\ell} v - \cdots - a_0 u^T A^\ell v$

$= u^T A^\ell (A^n - a_{n-1} A^{n-1} - \cdots - a_1 A - a_0) v$

$= u^T A^\ell p(A) v$

$= 0$,

where we have applyed the Cayley-Hamilton Theorem in the last step. Thus, the automaton $M$ rejects some input if and only if the linear recurrence sequence $(q_\ell)_{\ell \geq 0}$ contains a zero. This completes the reduction and the NP-hardness proof.

Written by uncudh

March 2, 2009 at 1:46 am

Posted in math

Tagged with

## The diverse and abstruse mysteries of numbers

The epigraph to Chapter 1 of Melvyn Nathanson’s Additive Number Theory is from one of Pierre de Fermat’s notorious scribblings in the margins of his copy of Diophantus’ Arithmetica.  In English translation, it reads:

I have discovered a most beautiful theorem of the greatest generality: Every number is a triangular number or the sum of two or three triangular numbers; every number is a square or the sum of two, three, or four squares; every number is a pentagonal number or the sum of two, three, four, or five pentagonal numbers; and so on for hexagonal numbers, heptagonal numbers, and all other polygonal numbers.  The precise statement of this very beautiful and general theorem depends on the number of the angles.  The theorem is based on the most diverse and abstruse mysteries of numbers, but I am not able to include the proof here….

One wonders to what “diverse and abstruse mysteries of numbers” was Fermat referring, but of course Fermat was also notorious for not providing proofs of his claims.  Triangular numbers are numbers of the form $n(n+1)/2$; squares, of the form $n^2$; pentagonal numbers, of the form $n(3n-1)/2$; and $m$-gonal numbers in general, of the form $(m-2)k(k-1)/2 + k$.

The claim regarding squares is the famous Four Squares Theorem of Lagrange; the claim regarding triangular numbers was proved by Gauss; and the claim in general was proved by Cauchy.  The proofs of all of these results can be found in Chapter 1 of Nathanson’s book.

Written by uncudh

February 17, 2009 at 12:12 am

Posted in math

Tagged with

## A curious proof of Wilson’s Theorem

with one comment

Recall that Wilson’s Theorem states that $p$ is a prime number if and only if $(p-1)! \equiv -1 \pmod p$. Wilson did not prove this statement; the first proof is due to Lagrange in 1773. Here we give a proof due to Thue from 1893 that uses the calculus of finite differences. Fortunately we have done most of the work previously.

Suppose $p$ is prime. Recall that

$\Delta^{(r)}(f)(x) = \sum_{j=0}^r (-1)^{r-j} {r \choose j} f(x+j).$

We also showed that $\Delta^{(r-1)}(x^r) = r!x + d$ for some constant $d$, so that $\Delta^{(r)}(x^r) = r!$. Let $f(x) = x^{p-1}$. It follows then that $\Delta^{(p-1)}(f)(0) = (p-1)!$. On the other hand, for $r = 1,2,\ldots,p-2$ we have

$\Delta^{(r)}(f)(1) = \sum_{j=0}^r (-1)^{r-j} {r \choose j} (1+j)^{p-1}.$

However, by Fermat’s Little Theorem, we have $(1+j)^{p-1} \equiv 1 \pmod p$, so

$\Delta^{(r)}(f)(1) \equiv \sum_{j=0}^r (-1)^{r-j} {r \choose j} \equiv (1-1)^r \equiv 0 \pmod p,$

where we have applied the Binomial Theorem. Now

$\Delta^{(p-1)}(f)(0) = \Delta^{(p-2)}(f)(1) - \Delta^{(p-3)}(f)(1) + \cdots - \Delta^2(f)(1) + \Delta(f)(1) - \Delta(f)(0),$

but by our previous observation, all of the terms on the right hand side are congruent to $0 \pmod p$, except the last, $-\Delta(f)(0)$. We thus have

$\Delta^{(p-1)}(f)(0) \equiv -\Delta(f)(0) \equiv f(0) - f(1) \equiv 0^{p-1} - 1^{p-1} \equiv -1 \pmod p$.

Thus, $(p-1)! \equiv -1 \pmod p$, as required.

Written by uncudh

December 20, 2008 at 3:22 am

Posted in math

Tagged with

## Some more curious continued fractions

We have previously observed that $e$ has the remarkably regular continued fraction expansion $e = [2; 1, 2, 1, 1, 4, 1, 1, 6,\ldots]$.

Another curious continued fraction is the following:

$\sum_{n \geq 1} 2^{-\lfloor 2n/(\sqrt{5}-1) \rfloor} = [0; 2^0, 2^1, 2^1, 2^2, 2^3, 2^5, 2^8, 2^{13}, \ldots]$,

where the exponents of the 2’s in the continued fraction are the Fibonacci numbers. This unusual continued fraction has been independently rediscovered by several authors. See, for example, Anderson, Brown, and Shiue, Proc. Amer. Math. Soc. 123 (1995), 2005-2009.

Among the most famous continued fractions are the Rogers-Ramanujan continued fractions:

$\cfrac{1}{1+\cfrac{e^{-2\pi}}{1+\cfrac{e^{-4\pi}}{1+\cfrac{e^{-6\pi}}{\vdots}}}} = \left( \sqrt{\frac{5+\sqrt{5}}{2}} - \frac{\sqrt{5}+1}{2} \right)e^{2\pi/5}$

$1-\cfrac{e^{-\pi}}{1+\cfrac{e^{-2\pi}}{1-\cfrac{e^{-3\pi}}{\vdots}}} = \left( \sqrt{\frac{5-\sqrt{5}}{2}} - \frac{\sqrt{5}-1}{2} \right)e^{\pi/5}$.

Ramanujan included these formulas in his famous 1913 letter to Hardy. Later, Hardy wrote, “[These formulas] defeated me completely. I had never seen anything in the least like them before. A single look at them is enough to show that they could only be written down by a mathematician of the highest class. They must be true because, if they were not true, no one would have had the imagination to invent them.”

Written by uncudh

November 27, 2008 at 1:50 am

Posted in math

Tagged with ,

## On the number of 1’s in the binary expansions of multiples of 3

Consider the sequence of multiples of 3: i.e., 3, 6, 9, 12, 15, 18, 21, 24 etc.  Now write these numbers in base 2 to obtain the sequence 11, 110, 1001, 1100, 1111, 10010, 10101, 11000, etc.  Look at these binary expansions and note which ones have an even number of 1’s and which ones have an odd number of 1’s.  For instance, construct the sequence whose n-th term is 0 if there is an even number of 1’s in the binary expansion of 3n and is 1 if there is an odd number of 1’s in the binary expansion of 3n.  This sequence begins 0, 0, 0, 0, 0, 0, 1, 0, etc.  If one generates (by computer) a long initial segment of this sequence, one may note that there seems to be a clear preponderance of 0’s in any initial segment of this sequence.  In fact, there appears to always be more 0’s than 1’s in any initial segment of the sequence.

Intuitively, this looks to be utterly bizarre.  One would expect the parity of 1’s in the binary expansions of 3n to be more or less random.  That is, there should sometimes be a slight preponderance of those with even parity and sometimes a slight deficit of those with even parity.  Nevertheless, one can prove definitively that in any intial segment of the sequence 0, 0, 0, 0, 0, 0, 1, 0, . . . , whose n-th term counts the parity of 1’s in the binary expansion of 3n, there are always more 0’s than 1’s.  Furthermore, the excess of 0’s over 1’s in any initial segment of length n can be bounded from below and above by $1/20 n^{\log 3 / \log 4}$ and $5n^{\log 3 / \log 4}$ respectively.

This curious result was obtained by Donald J. Newman in 1969 and appears in Proc. Amer. Math. Soc..

Written by uncudh

November 26, 2008 at 7:29 pm

Posted in math

Tagged with