number theory | Uniformly at Random

Posts Tagged ‘number theory’

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 beta expansions, number theory

The Khinchin-Levy Theorem

with 4 comments

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:

Why should the limit even exist?
Why should it have the same value for almost all $\alpha$ ?
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 continued fractions, number theory

Determining if a linear recurrence sequence contains a zero

leave a comment »

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 number theory

The diverse and abstruse mysteries of numbers

leave a comment »

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 number theory

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 number theory

Some more curious continued fractions

leave a comment »

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 continued fractions, number theory

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

leave a comment »

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 number theory

The continued fraction expansion of e

leave a comment »

It is a somewhat curious fact (due to Euler) that the continued fraction expansion of $e$ has a very regular pattern:

$e = [2; 1, 2, 1, 1, 4, 1, 1, 6, \ldots]$ .

There are many different proofs of this result. The proof given here is classical and elementary. It can be found, for instance, in the book by Rockett and Szusz.

We begin with the power series expansion of $e^x$ :

$e^x = \sum_{k=0}^\infty x^k/k!$ .

If $m$ is a positive integer, then we have

$e^{1/m} = \sum_{k=0}^\infty (1/m)^k/k!$ ,

$(e^{1/m} + e^{-1/m})/2 = \sum_{k=0}^\infty (1/m)^{2k}/(2k)!$ ,

$(e^{1/m} - e^{-1/m})/2 = \sum_{k=0}^\infty (1/m)^{2k+1}/(2k+1)!$ .

Let us also define

$x_n = \sum_{k=0}^\infty \frac{2^n(n+k)!}{k!(2n+2k)!}(1/m)^{2k+n}$

for $n \geq 0$ , so that $x_0$ and $x_1$ are the series given previously for $(e^{1/m} + e^{-1/m})/2$ and $(e^{1/m} - e^{-1/m})/2$ , respectively. Our first goal is to show that

$x_n - m(2n+1)x_{n+1} = x_{n+2}$ .

Expanding the lefthand side, we have

$\sum_{k=0}^\infty \frac{2^n(n+k)!}{k!(2n+2k)!}(1/m)^{2k+n} - m(2n+1) \sum_{k=0}^\infty \frac{2^{n+1}(n+1+k)!}{k!(2n+2+2k)!}(1/m)^{2k+n+1}$

$= \sum_{k=0}^\infty \frac{2^n(n+k)!}{k!(2n+2k)!}(1/m)^{2k+n} - \sum_{k=0}^\infty \frac{2^{n+1}(2n+1)(n+1+k)!}{k!(2n+2+2k)!}(1/m)^{2k+n}$

$= \sum_{k=0}^\infty \frac{2^n(n+k)!(2n+2+2k)(2n+1+2k)}{k!(2n+2+2k)!}(1/m)^{2k+n} - \sum_{k=0}^\infty \frac{2^{n+1}(2n+1)(n+1+k)!}{k!(2n+2+2k)!}(1/m)^{2k+n}$

$= \sum_{k=0}^\infty \frac{2^{n+1}(n+k)!(n+1+k)(2n+1+2k)}{k!(2n+2+2k)!}(1/m)^{2k+n} - \sum_{k=0}^\infty \frac{2^{n+1}(2n+1)(n+1+k)!}{k!(2n+2+2k)!}(1/m)^{2k+n}$

$= \sum_{k=0}^\infty \frac{2^{n+1}(n+1+k)!(2n+1+2k)}{k!(2n+2+2k)!}(1/m)^{2k+n} - \sum_{k=0}^\infty \frac{2^{n+1}(2n+1)(n+1+k)!}{k!(2n+2+2k)!}(1/m)^{2k+n}$

$= \sum_{k=0}^\infty \frac{2^{n+1}(n+1+k)![(2n+1+2k)-(2n+1)]}{k!(2n+2+2k)!}(1/m)^{2k+n}$

$= \sum_{k=0}^\infty \frac{2^{n+1}(n+1+k)!(2k)}{k!(2n+2+2k)!}(1/m)^{2k+n}$

$= \sum_{k=1}^\infty \frac{2^{n+2}(n+1+k)!k}{k!(2n+2+2k)!}(1/m)^{2k+n}$

$= \sum_{k=1}^\infty \frac{2^{n+2}((n+2)+(k-1))!}{(k-1)!(2(n+2)+2(k-1))!}(1/m)^{2(k-1)+(n+2)}$

$= \sum_{k=0}^\infty \frac{2^{n+2}((n+2)+k)!}{k!(2(n+2)+2k)!}(1/m)^{2k+(n+2)}$

$= x_{n+2}$

as required. Now let $y_n = x_n/x_{n+1}$ for $n \geq 0$ . We thus have $y_0 = (e^{2/m}+1)/(e^{2/m}-1)$ , and furthermore, we have

$y_n = (m(2n+1)x_{n+1} + x_{n+2})/x_{n+1} = m(2n+1) + x_{n+2}/x_{n+1} = m(2n+1) + 1/y_{n+1}$ .

It follows then that $[m; 3m, 5m, \ldots]$ is the continued fraction expansion of $(e^{2/m}+1)/(e^{2/m}-1)$ , and in particular, for $m=2$ , $[2; 6, 10, \ldots]$ is the continued fraction expansion of $(e+1)/(e-1)$ .

Recall that if $p_n/q_n$ is the $n$ -th convergent to the continued fraction $[a_0; a_1, a_2, \ldots]$ , the following hold: $p_{-1} = 1, p_0 = a_0$ , $q_{-1} = 0$ , $q_0 = 1$ , $p_{n+1} = a_{n+1}p_n + p_{n-1}$ , and $q_{n+1} = a_{n+1}q_n + q_{n-1}$ , for $n \geq 0$ . Thus, if $p_n/q_n$ is the the $n$ -th convergent of $[2; 6, 10, \ldots]$ , we have $p_{n+1} = 2(2n+1)p_n + p_{n-1}$ , and $q_{n+1} = 2(2n+1)q_n + q_{n-1}$ .

Let us now recall the claimed expansion $e = [2; 1, 2, 1, 1, 4, 1, 1, 6, \ldots]$ . That is, $e = [a_0; a_1, a_2, \ldots]$ , where $a_0 = 2$ , $a_1 = 1$ , $a_{3n-1} = 2n$ , and $a_{3n} = a_{3n+1} = 1$ , for $n \geq 1$ . Letting $r_n/s_n$ denote the convergents to $[2; 1, 2, 1, 1, 4, 1, 1, 6, \ldots]$ , we have

$r_{3n+1} = r_{3n} + r_{3n-1} = r_{3n-1} + r_{3n-2} + r_{3n-1}$

$= 2r_{3n-1} + r_{3n-2} = 2(2nr_{3n-2} + r_{3n-3}) + r_{3n-2}$

$= (2(2n)+1)r_{3n-2} + r_{3n-3} + (r_{3n-4} + r_{3n-5})$

$= (2(2n)+1)r_{3n-2} + (r_{3n-3} + r_{3n-4}) + r_{3n-5}$

$= (2(2n)+1)r_{3n-2} + r_{3n-2} + r_{3n-5}$

$= 2(2n+1)r_{3n-2} + r_{3n-5}$

$= 2(2n+1)r_{3(n-1)+1} + r_{3(n-2)+1}$ ,

for $n \geq 2$ . Similarly, we can show that $s_{3n+1} = 2(2n+1)s_{3(n-1)+1} + s_{3(n-2)+1}$ . However, observe that $r_{3n+1}$ and $s_{3n+1}$ satisfy the same recurrence as $p_n$ and $q_n$ . Furthermore, when $n=0$ we can check that $r_1 = p_0 + q_0$ and $s_1 = p_0 - q_0$ ; and similarly, when $n=1$ , we have $r_4 = p_1 + q_1$ and $s_4 = p_1 - q_1$ . It follows that $r_{3n+1} = p_n + q_n$ and $s_{3n+1} = p_n - q_n$ for $n \geq 0$ .

We can complete the proof if we can show that $r_{3n+1}/s_{3n+1}$ converges to $e$ as $n$ tends to infinity. Note that

$r_{3n+1}/s_{3n+1} = (p_n + q_n)/(p_n - q_n) = (p_n/q_n + 1)/(p_n/q_n - 1)$ .

However, we have previously noted that $p_n/q_n$ converges to $(e+1)/(e-1)$ , so $r_{3n+1}/s_{3n+1}$ converges to $\frac{(e+1)/(e-1)+1}{(e+1)/(e-1)-1} = e$ , and the proof is complete.

Written by uncudh

November 19, 2008 at 6:22 pm

Posted in math

Tagged with continued fractions, number theory

The easier Waring’s problem

leave a comment »

Waring’s problem is to show that for every $k \geq 2$ , there is a number $g(k)$ so that every positive integer can be written as the sum of $g(k)$ $k$ th powers. For instance, every positive integer is the sum of four squares and is the sum of nine cubes. Hilbert solved Waring’s problem in 1909. The proof is quite difficult. An easier variant of Waring’s problem (due to Wright) is to show that there is a number $v(k)$ so that every positive integer can be written as the sum or difference of $v(k)$ $k$ th powers. To show this, let $f$ be any function and let $\Delta$ be the operator defined by $\Delta(f)(x) = f(x+1) - f(x)$ . We first show by induction on $r$ that $\Delta^{(r)}(f)(x) = \sum_{j=0}^r (-1)^{r-j} {r \choose j} f(x+j).$

Suppose the identity holds for $r$ ; then

$\Delta^{(r+1)}(f)(x) = \Delta(\Delta^{(r)}(f))(x)$

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

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

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

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

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

$= f(x+r+1) + \sum_{j=1}^{r} (-1)^{r+1-j} \left( {r \choose j-1} + {r \choose j}\right) f(x+j) + (-1)^{r+1}f(x)$

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

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

as required. Now observe that

$\Delta(x^k) = k x^{k-1} + \cdots$

and

$= \Delta^{(2)}(x^k) = k(k-1) x^{k-2} + \cdots$

and so on, so that

$\Delta^{(k-1)}(x^k) = k!x + d$

where $d$ is an integer that does not depend on $x$ . It follows that

$\Delta^{(k-1)} (x^k) = \sum_{j=0}^{k-1} (-1)^{k-1-j} {k-1 \choose j} (x+j)^k = k!x + d.$

Since $\sum_{j=0}^{k-1} {k-1 \choose j} = 2^{k-1},$ we see that every integer of the form $k!x + d$ can be written as the sum or difference of at most $2^{k-1}$ $k$ th powers. However, for any integer $n$ we can write $n - d = k!q + p$ for some $q$ and $p$ , where $-k!/2 < p \leq k!/2$ . Since $p$ can then be written as the sum or difference of $|p|$ ones, it follows that $n$ can be written as the sum or difference of at most $2^{k-1} + k!/2$ $k$ th powers. This establishes the desired solution to the easier Waring’s problem.