## Posts Tagged ‘**number theory**’

## Expansions in irrational bases

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

where . (We leave it to the reader to speculate as to why one would do such a perverse thing.) -expansions are not generally unique. For example, let be the golden ratio. Then and , so and are both -expansions of 1. However, there are certain curious irrational numbers for which 1 has a unique -expansion. Moreover, there is a even a **least** between 1 and 2 with this property. This is the unique solution (approx 1.78723…) to

where is the number of 1’s mod 2 in the binary expansion of . (It seems rather bizarre that the parity of 1’s in the binary expansion of should have anything to do with this problem!) This 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.

## 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 , the denominators of the convergents of the continued fraction expansion of satisfy

.

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 ?
- Why should its value involve the three constants , , and ?

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.

## Determining if a linear recurrence sequence contains a zero

Let be an integer sequence satisfying a linear recurrence for some . 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 be a unary non-deterministic finite automaton. Let us suppose that the states of are labeled and let us suppose further that state is the initial state. We construct the adjacency matrix of by defining if has a transition from state to state , and otherwise. Let be the -vector with a in the first position and ‘s elsewhere. Let be the -vector with a in position if state is an accepting state of , and a in position otherwise. It is not hard to see that is the number of paths in of length from the initial state to an accepting state. Thus, rejects a length input if and only if . That is, rejects some input if and only if the sequence contains a zero.

We now construct a linear recurrence satisfied by this sequence. Let be the characteristic polynomial of . We claim that satisfies the linear recurrence . We have

,

where we have applyed the Cayley-Hamilton Theorem in the last step. Thus, the automaton rejects some input if and only if the linear recurrence sequence contains a zero. This completes the reduction and the NP-hardness proof.

## 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 ; squares, of the form ; pentagonal numbers, of the form ; and -gonal numbers in general, of the form .

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.

## A curious proof of Wilson’s Theorem

Recall that Wilson’s Theorem states that is a prime number if and only if . 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 is prime. Recall that

We also showed that for some constant , so that . Let . It follows then that . On the other hand, for we have

However, by Fermat’s Little Theorem, we have , so

where we have applied the Binomial Theorem. Now

but by our previous observation, all of the terms on the right hand side are congruent to , except the last, . We thus have

.

Thus, , as required.

## Some more curious continued fractions

We have previously observed that has the remarkably regular continued fraction expansion .

Another curious continued fraction is the following:

,

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:

.

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.”

## 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 and respectively.

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