Republic of Mathematics blog

A curious number exploration

Posted by: Gary Ernest Davis on: May 6, 2011

In: Uncategorized
Leave a Comment

Benjamin Vitale (@BenVitale) tweeted that he followed 203 people on Twitter and $203^2 + 203^0 + 203^3 = 8406637$ is a prime number.

Alex Bogomolny (@CutTheKnotMath) observed that if $n=abc$ (digits base 10) then $abc^a+abc^b+abc^c$ has a factor of $abc$ unless one of $a, b, c =0$ .

A quick computational search (using Mathematicaâ„¢) yields the following numbers $n=d_k\ldots d_0 \leq 10000$ (base 10 digits) for which $n^{d_k}+\ldots +n^{d_0}$ is prime:

10, 20, 203, 230, 308, 309, 330, 350, 503, 603, 650, 960, 1068, 1110, 1206, 1350, 1404, 1480, 1730, 1802, 1860, 1910, 2032, 2038, 2044, 2054, 2250, 2320, 2502, 3044, 3082, 3402, 3970, 4032, 4046, 4072, 4120, 4340, 4450, 4540, 4650, 4908, 5204, 5310, 5402, 5530, 5770, 5820, 6038, 6076, 6120, 6206, 6490, 6520, 6830, 7110, 8074, 8106, 8120, 8380, 8450, 8610, 8690, 8902, 8960, 9064, 9330, 9402, 9408, 9950

How do these numbers increase?

Are they becoming relatively rarer?

Let’s denote by $V(p)$ the number of $n=d_k \ldots d_0 \textrm{ (base 10 digits) } \leq p$ such that $n^{d_k}+\ldots + n^{d_0}$ Â is prime.

How does the fraction $\frac{V (p)}{p}$ vary with increasing $p$ ?

Here is a plot of that fraction up to $p=200000$ :

It appears that $\frac{V(p)}{p} \to 0$ as $p$ increases, although the decrease is highly exaggerated by the foreshortened plot.

Does $\frac{V(p)}{p} \to 0$ as $p$ increases?

Postscript

Matt Henderson (@mattthen2) made the following useful observation:

Let $Z(p)$ denote the number of $n\leq p$ whose digits contain a $0$ .

Then $Z(10^n)< 10^n + 9/8 - \frac{9^{n+1}}{8}$ so $\frac{Z(10^n)}{10^{nk}}\to 0\textrm{ as } n\to \infty$ for all $k>1$ .

Because $V(p)\leq Z(p)$ for all $p$ we see that:

$\frac{V(10^n)}{10^{nk}}\to 0\textrm{ as } n\to \infty$ for all $k>1$ .

Tags: prime numbers

The axiom of choice: can’t live without it, can’t live with it

Posted by: Gary Ernest Davis on: May 4, 2011

In: Uncategorized
2 Comments

Imagine you get to choose one of each type of cake from the cake shop pictured above!

What a treat!

With trembling hands you go from one type of cake to another, carefully choosing one of each until you’ve run out of different types of cakes.

Yum!

When you’re done you have a collection of cakes, with one cake from each type of cake.

Infinitely many choices

This is such a natural procedure that mathematicians imagined, without really thinking about it, that the same type of choice could be carried out even if there were infinitely many different types of cakes to choose from.

Ernst Zermelo (1871 - 1953)

Until Ernst Zermelo made it clear that it was a foundational axiom, or assumption, of set theory that one could always make such a choice.

Where in mathematics might one need to make a choice from one of infinitely many different types of collections?

Here is one simple example:

The Cartesian plane consists of ordered pairs $(x,y)$ of real numbers $x\textrm{ and } y$ .

We can shift points in the Cartesian plane by moving them left or right one unit, or up and down one unit.

The orbit of a point $(x,y)$ in the Cartesian plane for this group of motions is the collection of all points that $(x,y)$ can be moved to by moving it up, down, left or right one unit, repeatedly.

In other words the orbit of $(x,y)$ consists exactly of the points $(x\pm m,y\pm n)$ where $m,n$ range over all possible integers.

The orbits of points split the Cartesian plane into disjoint sets.

Is there some way of forming a set that consists of just one point from each possible orbit?

We can answer this positively by first observing that the orbit of each point on the Cartesian plane passes through the square with corners $(0,0), (1,0), (0,1), (1,1)$ exactly once, except for points on the lines joining $(0,0)$ to $(1,0)$ and to $(0,1)$ , and the lines joining $(1,1)$ to $(1,0)$ and to $(0,1)$ : for any point on these lines, its orbit passes through the square exactly twice (once on each edge).

So, if we identify (= glue together) the edges of the square as indicated, we willÂ have a set of points that (is in one-to-one correspondence with a set that) contains a single point from each and every orbit.

This identification gives us a torus:

So the answer to our question is: “Yes. we can find a set (the torus) consisting of one and only one point from each orbit.”

If we fancifully imagine the orbits as types of cakes, and points in each orbit as cakes, then we have found a set that consists of one and only one of each of the infinite types of cake.

Axioms of choice

Zermelo’s phrasing of the axiom of choice was as follows:

“If T is a set whose elements all are sets that are different from âˆ… and mutually disjoint, its union âˆªT includes at least one subset S₁ having one and only one element in common with each element of T“.

Ideas about infinity, and infinite processes, are essential to mathematics, so Zermelo’s axiom of choice came to play a central role in the foundations of mathematical thought.

Independence of the axiom of choice

Kurt GÃ¶del

Paul Cohen

Kurt Godel and Paul Cohen showed that the axiom of choice is independent of the other axioms of Zermelo-Fraenkel (ZF) set theory. Assuming ZF set theory is consistent, Godel constructed a model of set theory in which the the axiom of choice cannot be disproved from the other axioms. Cohen constructedÂ a model of ZFÂ set theory in which the axiom of choice cannot be proved from the other axioms.

Godel and Cohen’s theorems together tell us that we can take the axiom of choice as an axiom, or take its negation as an axiom – it’s up to us to decide in which set-theoretic world we want to live.

Now that IS choice!

Nice things with the axiom of choice

1. We say that a set $A$ is larger than a set $B$ if there is a one-to-one function $f:B\to A$ . (“One-to-one” means if $f(b_1)=f(b_2) \textrm{ then } b_1=b_2$ )

The axiom of choice allows us to conclude (indeed, is equivalent with): for any two sets $A, B$ either $A$ is larger than $B$ or $B$ is larger than $A$ .

2. A set is countably infinite if it can be put into one-to-one correspondence with the set of natural numbers.

The axiom of choice allows us to conclude that a countably infinite union of countably infinite sets is again countably infinite.

Weird things with the axiom of choice

1. The axiom of choice allows us to prove the Banach-Tarski theorem:

A ball of radius 1 in 3-dimensional real space can be dissected into a finite number of pieces which can be re-arranged by rotations and translations to yield two balls of radius 1.

As you might suspect, these pieces do not have a rotation and translation invariant volume.

I was prompted to write this post by someone saying they were puzzled about the reference to the axiom of choice in the following XKCD cartoon:

Courtsey XKCD

2. A total order on a set $A$ is a relation between pairs of elements of $A$ (a binary relation), denoted $\preceq$ , with the following properties:

$a \preceq a \textrm{ for all } a \in A$
$\textrm{if } a \preceq b \textrm { and } b \preceq a \textrm{ then } a=b$
$\textrm{if } a \preceq b \textrm{ and } b\preceq c \textrm{ then } a \preceq c$

A first element for a subset $B \subseteq A$ for a total order $\preceq$ is a $b_0\in B$ such that $b_0 \preceq b \textrm{ for all } b \in B$ .

The axiom of choice allows us to conclude that there is a total order (not the usual order !) on the set of real numbers such that every non-empty set of real numbers has a first element.

Indeed there is nothing special about the set of real numbers in this respect: we can replace it by any set whatsoever.

Nice things without the axiom of choice

No Banach-Tarski paradox.

Weird things without the axiom of choice

There is a model for ZF set theory with the negation of the axiom of choice in which the set of real numbers is a countable union of countable subsets (but, of course, is not itself countable).

Last words

To paraphrase Horst Herrlich:

Mathematics with â€œchoiceâ€ may be as unreal as a soap-bubble dream, but mathematics without â€œchoiceâ€ is as horrible as nightmare.

We might also say that you have to know if you can choose your cake before you can eat it.

And we couldn’t pass up the old, but golden, riddle: “What’s yellow and equivalent to the axiom of choice?”

Tags: axiom of choice, Banach-Tarski paradox, countable set, infinity, Kurt Godel, Paul Cohen