Dirichlet’s Approximation Theorem in Mathematica

The Dirichilet’s approximation Theorem is about using rational numbers to approximate any numbers. To state it formally:

If \alpha \in \mathbb{R}, n \in \mathbb{Z}^+, then there exist integer a and b with 1 \leq a \leq n such that |a \alpha - b | < 1/n.

I managed to write up a simple Mathematica code (when I say simple, it still took me about 1 hr to write up and satisfy with, I suck at programming)

 

 


Clear["Global`*"]

Declaring all the necessary variables first.

\[Alpha] = E;
n = 1000;
seq = (Range[n + 1] - 1)*\[Alpha];
fracseq = FractionalPart[seq];
intervals = Partition[(Range[n + 1] - 1)/n, 2, 1];
found = 0;
k = 1;

Just like in the proof of the Dirichlet Therorem, we created a sequence, which are the fractional part of first n integer multiples of alpha. The intervals are created in a similar way.

A loop to find the very first instance that we have “two piegeons in the same piegeonhole”.

While[k < Length[intervals] && found == 0, If[ Total[Boole[IntervalMemberQ[Interval[intervals[[k]]], fracseq]]] > 1,
found = 1, found = 0
];
k++]

This is just checking that we have the piegeons in the right place.

k - 1
Total[Boole[IntervalMemberQ[Interval[intervals[[k - 1]]], fracseq]]]
intervals[[k - 1]]

13

2

{3/250, 13/1000}

We have a selection criterion here, to select the first two piegeons in the hole.

selectseqcriterion =
Boole[IntervalMemberQ[Interval[intervals[[k - 1]]], fracseq]];
Pick[seq, selectseqcriterion, 1];

i = Pick[Range[n + 1] – 1, selectseqcriterion, 1][[1]];
j = Pick[Range[n + 1] – 1, selectseqcriterion, 1][[2]];

‘a’ and ‘b’ are the denominator and numerator of the rational approximation to the real number alpha.

a = j - i
b = Floor[j*\[Alpha]] - Floor[i*\[Alpha]]

536

1457

This is just a check that the function works.

Abs[a*\[Alpha] - b] < 1/n
Abs[\[Alpha] - b/a] <= 1/(a^2)
N[Abs[\[Alpha] - b/a]]

True

True

1.75363*10^-6

 

So this simple program works. The exercise and theorem came from Kenneth Rosen’s “Elementary Number Theory”, and it certainly a good exercise to do.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s