## Posts Tagged 'Number Theory'

### A Puzzle: Two-step Selection of a Digit

Here is a simple problem in probability.

(1) Pick a number k between 1 and 9. Assume all digits are equally likely.

(2) Pick a number m in the range from 1 to k.

What is the probability distribution for the number m?

A graph of the probability distribution is shown in the figure here.

Probability distribution for a decimal digit selected in a two-step process.

Can you derive a formula for this probability distribution?

Can you generalise it to the range from 1 to 10^n?

Can you relate this problem to Benford’s Law [described here]?

Solution, and more on Benford’s Law, next week.

### Ford Circles & Farey Series

Lester R Ford, Sr. (1886–1967).

American mathematician Lester Randolph Ford Sr. (1886–1967) was President of the Mathematical Association of America from 1947 to 1948 and editor of the American Mathematical Monthly during World War II. He is remembered today for the system of circles named in his honour.

For any rational number ${p/q}$ in reduced form (${p}$ and ${q}$ coprime), a Ford circle is a circle with center at ${(p/q,1/(2q^{2}))}$ and radius ${1/(2q^{2})}$. There is a Ford circle associated with every rational number. Every Ford circle is tangent to the horizontal axis and each two Ford circles are either tangent or disjoint from each other.

### Summing the Fibonacci Sequence

Left: Fibonacci, or Leonardo of Pisa. Right: Italian postage stamp issued on the 850th anniversary of his birth.

The Fibonacci sequence must be familiar to anyone reading this. We define it by means of a second-order recurrence relation,

$\displaystyle F_{n+1} = F_{n-1} + F_n \,. \ \ \ \ \ (1)$

and two initial values, ${F_0 = 0}$ and ${F_1 = 1}$. This immediately yields the well-known sequence

$\displaystyle \{F_n\} = \{ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, \dots \} \,.$

### Closeness in the 2-Adic Metric

When is 144 closer to 8 than to 143?

The usual definition of the norm of a real number ${x}$ is its modulus or absolute value ${|x|}$. We measure the “distance” between two real numbers by means of the absolute value of their difference. This gives the Euclidean metric ${\rho(x,y) = |x-y|}$ and, using it, we can define the usual topology on the real numbers ${\mathbb{R}}$.

The standard arrangement of the real numbers on a line automatically ensures that numbers with small Euclidean difference between them are geometrically close to each other. It may come as a surprise that there are other ways to define norms and distances, which provide other topologies, leading us to a radically different concept of closeness, and to completely new number systems, the p-adic numbers.

### Fields Medals presented at IMC 2022

Every four years, at the International Congress of Mathematicians, the Fields Medal is awarded to two, three, or four young mathematicians. To be eligible, the awardees must be under forty years of age. For the chosen few, who came from England, France, Korea and Ukraine, the award, often described as the Nobel Prize of Mathematics, is the crowning achievement of their careers [TM235 or search for “thatsmaths” at irishtimes.com].

Clockwise from top left: Maryna Viazovska, James Maynard, June Huh and Hugo Duminil-Copin. Image Credits: Mattero Fieni, Ryan Cowan, Lance Murphy.

The congress, which ran from 6th to 14th July, was originally to take place in St Petersburg. When events made that impossible, the action shifted to Helsinki and the conference presentations were moved online. The International Mathematical Union generously allowed participants to register at no cost.

### Goldbach’s Conjecture and Goldbach’s Variation

Goldbach’s Conjecture is one of the great unresolved problems of number theory. It simply states that every even natural number greater than two is the sum of two prime numbers. It is easily confirmed for even numbers of small magnitude.

The conjecture first appeared in a letter dated 1742 from German mathematician Christian Goldbach to Leonhard Euler. The truth of the conjecture for all even numbers up to four million million million (${4\times 10^{18}}$) has been demonstrated. There is essentially no doubt about its validity, but no proof has been found.

### Fairy Lights on the Farey Tree

Fairy Lights on the Farey Tree. Parity types are coloured as follows: Even: Blue; Odd: Green; None: Red.

The rational numbers ${\mathbb{Q}}$ are dense in the real numbers ${\mathbb{R}}$. The cardinality of rational numbers in the interval ${(0,1)}$ is ${\boldsymbol{\aleph}_0}$. We cannot list them in ascending order, because there is no least rational number greater than ${0}$.

### Parity and Partition of the Rational Numbers. Part II: Density of the Three Parity Classes

In last week’s post, we defined an extension of parity from the integers to the rational numbers. Three parity classes were found — even, odd and none. This week, we show that, with an appropriate ordering or enumeration of the rationals, the three classes are not only equinumerate (having the same cardinality) but of equal density in ${\mathbb{Q}}$. This article is a condensation of part of a paper [Lynch & Mackey, 2022] recently posted on arXiv.

### Parity and Partition of the Rational Numbers. Part I: The Three Parity Classes

We define an extension of parity from the integers to the rational numbers. Three parity classes are found — even, odd and none. Using the 2-adic valuation, we partition the rationals into subgroups with a rich algebraic structure.

### Gaussian Primes

We are all familiar with splitting natural numbers into prime components. This decomposition is unique, except for the order of the factors. We can apply the idea of prime components to many more general sets of numbers.

The Gaussian integers are all the complex numbers with integer real and imaginary parts, that is, all numbers in the set

$\displaystyle \mathbb{Z}[i] \equiv \{ m + i n : m, n \in \mathbb{Z} \} \,.$

The set ${\mathbb{Z}[i]}$ forms a two-dimensional lattice in the complex plane. For any element ${g \in \mathbb{Z}[i]}$ we consider the four numbers ${\{g, -g, ig, -ig \}}$ as associates. The associates of ${1}$ are known as units: ${\{1, -1, i, -i \}}$.

### Number Partitions: Euler’s Astonishing Insight

In 1740, French mathematician Philippe Naudé wrote to Leonhard Euler asking in how many ways a positive integer can be written as a sum of distinct numbers. In his investigations of this, Euler established the theory of partitions, for which he used the term partitio numerorum.

Many of Euler’s results in number theory involved divergent series. He was courageous in manipulating these but had remarkable insight and, almost invariably, his findings, although not rigorously established, were valid.

Partitions

In number theory, a partition of a positive integer ${n}$ is a way of writing ${n}$ as a sum of positive integers. The order of the summands is ignored: two sums that differ only in their order are considered the same partition.

### Set Density: are even numbers more numerous than odd ones?

In pure set-theoretic terms, the set of even positive numbers is the same size, or cardinality, as the set of all natural numbers: both are infinite countable sets that can be put in one-to-one correspondence through the mapping ${n \rightarrow 2n}$. This was known to Galileo. However, with the usual ordering,

$\displaystyle \mathbb{N} = \{ 1, 2, 3, 4, 5, 6, \dots \} \,,$

every second number is even and, intuitively, we feel that there are half as many even numbers as natural numbers. In particular, our intuition tells us that if ${B}$ is a proper subset of ${A}$, it must be smaller than ${A}$.
Continue reading ‘Set Density: are even numbers more numerous than odd ones?’

### A Grand Unification of Mathematics

Rene Descartes

There are numerous branches of mathematics, from arithmetic, geometry and algebra at an elementary level to more advanced fields like number theory, topology and complex analysis. Each branch has its own distinct set of axioms, or fundamental assumptions, from which theorems are derived by logical processes. While each branch has its own flavour, character and methods, there are also strong overlaps and interdependencies. Several attempts have been made to construct a grand unified theory that embraces the entire field of maths  [TM220 or search for “thatsmaths” at irishtimes.com].

### The Spine of Pascal’s Triangle

We are all familiar with Pascal’s Triangle, also known as the Arithmetic Triangle (AT). Each entry in the AT is the sum of the two closest entries in the row above it. The ${k}$-th entry in row ${n}$ is the binomial coefficient ${\binom{n}{k}}$ (read ${n}$-choose-${k}$), the number of ways of selecting ${k}$ elements from a set of ${n}$ distinct elements.

### All Numbers Great and Small

Is space continuous or discrete? Is it smooth, without gaps or discontinuities, or granular with a limit on how small a distance can be? What about time? Can time be repeatedly divided into smaller periods without any limit, or is there a shortest interval of time? We don’t know the answers. There is much we do not know about physical reality: is the universe finite or infinite? Are space and time arbitrarily divisible? Does our number system represent physical space and time? [TM215 or search for “thatsmaths” at irishtimes.com]. Continue reading ‘All Numbers Great and Small’

### The Simple Arithmetic Triangle is full of Surprises

Pascal’s triangle is one of the most famous of all mathematical diagrams, simple to construct and yet rich in mathematical patterns. These can be found by a web search, but their discovery by study of the diagram is vastly more satisfying, and there is always a chance of finding something never seen before  [TM212 or search for “thatsmaths” at irishtimes.com].

Pascal’s triangle as found in Zhu Shiji’s treatise The Precious Mirror of the Four Elements (1303).

### Goldbach’s Conjecture: if it’s Unprovable, it must be True

The starting point for rigorous reasoning in maths is a system of axioms. An axiom is a statement that is assumed, without demonstration, to be true. The Greek mathematician Thales is credited with introducing the axiomatic method, in which each statement is deduced either from axioms or from previously proven statements, using the laws of logic. The axiomatic method has dominated mathematics ever since [TM206 or search for “thatsmaths” at irishtimes.com].

### Derangements and Continued Fractions for e

We show in this post that an elegant continued fraction for ${e}$ can be found using derangement numbers. Recall from last week’s post that we call any permutation of the elements of a set an arrangement. A derangement is an arrangement for which every element is moved from its original position.

### Arrangements and Derangements

Six students entering an examination hall place their cell-phones in a box. After the exam, they each grab a phone at random as they rush out. What is the likelihood that none of them gets their own phone? The surprising answer — about 37% whatever the number of students — emerges from the theory of derangements.

### Will RH be Proved by a Physicist?

The Riemann Hypothesis (RH) states that all the non-trivial (non-real) zeros of the zeta function lie on a line, the critical line, ${\Re(s) = 1/2}$. By a simple change of variable, we can have them lying on the real axis. But the eigenvalues of any hermitian matrix are real. This led to the Hilbert-Polya Conjecture:

The non-trivial zeros of ${\zeta(s)}$ are the
eigenvalues of a hermitian operator.

Is there a Riemann operator? What could this operater be? What dynamical system would it represent? Are prime numbers and quantum mechanics linked? Will RH be proved by a physicist?

This last question might make a purest-of-the-pure number theorist squirm. But it is salutary to recall that, of the nine papers that Riemann published during his lifetime, four were on physics!

### The p-Adic Numbers (Part 2)

Kurt Hensel (1861-1941)

Kurt Hensel, born in Königsberg, studied mathematics in Berlin and Bonn, under Kronecker and Weierstrass; Leopold Kronecker was his doctoral supervisor. In 1901, Hensel was appointed to a full professorship at the University of Marburg. He spent the rest of his career there, retiring in 1930.

Hensel is best known for his introduction of the p-adic numbers. They evoked little interest at first but later became increasingly important in number theory and other fields. Today, p-adics are considered by number theorists as being “just as good as the real numbers”. Hensel’s p-adics were first described in 1897, and much more completely in his books, Theorie der algebraischen Zahlen, published in 1908 and Zahlentheorie published in 1913.

### The p-Adic Numbers (Part I)

Image from Cover of Katok, 2007.

The motto of the Pythagoreans was “All is Number”. They saw numbers as the essence and foundation of the physical universe. For them, numbers meant the positive whole numbers, or natural numbers ${\mathbb{N}}$, and ratios of these, the positive rational numbers ${\mathbb{Q}^{+}}$. It came as a great shock that the diagonal of a unit square could not be expressed as a rational number.

If we arrange the rational numbers on a line, there are gaps everywhere. We can fill these gaps by introducing additional numbers, which are the limits of sequences of rational numbers. This process of completion gives us the real numbers $\mathbb{R}$, which include rationals, irrationals like ${\sqrt{2}}$ and transcendental numbers like ${\pi}$.

### Think of a Number: What are the Odds that it is Even?

Pick a positive integer at random. What is the chance of it being 100? What or the odds that it is even? What is the likelihood that it is prime?

Probability distribution ${P(n)=1/(\zeta(s)n^s)}$ for s=1.1 (red), s=1.01 (blue) and s=1.001 (black).

### The Ever-growing Goals of Googology

In 1920, a kindergarten class was asked to describe the biggest number that they could imagine. One child proposed to “write down digits until you get tired”. A more concrete idea was to write a one followed by 100 zeros. This number, which scientists would express as ten to the power 100, was given the name “googol” by its inventor [TM190; or search for “thatsmaths” at irishtimes.com ].

### The Online Encyclopedia of Integer Sequences

Suppose that, in the course of an investigation, you stumble upon a string of whole numbers. You are convinced that there must be a pattern, but you cannot find it. All you have to do is to type the string into a database called OEIS — or simply “Slone’s” — and, if the string is recognized, an entire infinite sequence is revealed. If the string belongs to several sequences, several choices are offered. OEIS is a great boon to both professional mathematicians and applied scientists in fields like physics, chemistry, astronomy and biology.

### John Horton Conway: a Charismatic Genius

John H Conway in 2009
[image Denise Applewhite, Princeton University].

John Horton Conway was a charismatic character, something of a performer, always entertaining his fellow-mathematicians with clever magic tricks, memory feats and brilliant mathematics. A Liverpudlian, interested from early childhood in mathematics, he studied at Gonville & Caius College in Cambridge, earning a BA in 1959. He obtained his PhD five years later, after which he was appointed Lecturer in Pure Mathematics.

In 1986, Conway moved to Princeton University, where he was Professor of Mathematics and John Von Neumann Professor in Applied and Computational Mathematics. He was awarded numerous honours during his career. Conway enjoyed emeritus status from 2013 until his death just two weeks ago on 11 April.

### Bang! Bang! Bang! Explosively Large Numbers

Typical Comic-book `bang’ mark [Image from vectorstock ].

Enormous numbers pop up in both mathematics and physics. The order of the monster group, the largest of the 26 sporadic groups, is

$\displaystyle 808,017,424,794,512,875,886,459,904,961,710,757,005,754,368,000,000,000$

which is approximately ${8\times 10^{53}}$. The number of atoms in the universe is estimated to be about ${10^{80}}$. When we consider permutations of large sets, even more breadth-taking numbers emerge.

### The “extraordinary talent and superior genius” of Sophie Germain

When a guitar string is plucked, we don’t see waves travelling along the string. This is because the ends are fixed. Instead, we see a standing-wave pattern. Standing waves are also found on drum-heads and on the sound-boxes of violins. The shape of a violin strongly affects the quality and purity of the sound, as it determines the mixture of standing wave harmonics that it can sustain [TM179 or search for “thatsmaths” at irishtimes.com].

French postage stamp, issued in 2016, to commemorate the
250th anniversary of the birth of Sophie Germain (1776-1831).

### Spiralling Primes

The Sacks Spiral.

The prime numbers have presented mathematicians with some of their most challenging problems. They continue to play a central role in number theory, and many key questions remain unsolved.

Order and Chaos

The primes have many intriguing properties. In his article “The first 50 million prime numbers”, Don Zagier noted two contradictory characteristics of the distribution of prime numbers. The first is the erratic and seemingly chaotic way in which the primes “grow like weeds among the natural numbers”. The second is that, when they are viewed in the large, they exhibit “stunning regularity”.

### Closing the Gap between Prime Numbers

Occasionally, a major mathematical discovery comes from an individual working in isolation, and this gives rise to great surprise. Such an advance was announced by Yitang Zhang six years ago. [TM161 or search for “thatsmaths” at irishtimes.com].

Yitang Zhang

### Massive Collaboration in Maths: the Polymath Project

Sometimes proofs of long-outstanding problems emerge without prior warning. In the 1990s, Andrew Wiles proved Fermat’s Last Theorem. More recently, Yitang Zhang announced a key result on bounded gaps in the prime numbers. Both Wiles and Zhang had worked for years in isolation, keeping abreast of developments but carrying out intensive research programs unaided by others. This ensured that they did not have to share the glory of discovery, but it may not be an optimal way of making progress in mathematics.

Polymath

Timothy Gowers in 2012 [image Wikimedia Commons].

Is massively collaborative mathematics possible? This was the question posed in a 2009 blog post by Timothy Gowers, a Cambridge mathematician and Fields Medal winner. Gowers suggested completely new ways in which mathematicians might work together to accelerate progress in solving some really difficult problems in maths. He envisaged a forum for the online discussion of problems. Anybody interested could contribute to the discussion. Contributions would be short, and could include false routes and failures; these are normally hidden from view so that different workers repeat the same mistakes.

### Multiple Discoveries of the Thue-Morse Sequence

It is common practice in science to name important advances after the first discoverer or inventor. However, this process often goes awry. A humorous principle called Stigler’s Law holds that no scientific result is named after its original discoverer. This law was formulated by Professor Stephen Stigler of the University of Chicago in his publication “Stigler’s law of eponymy”. He pointed out that his “law” had been proposed by others before him so it was, in a sense, self-verifying. [TM157 or search for “thatsmaths” at irishtimes.com].

Continue reading ‘Multiple Discoveries of the Thue-Morse Sequence’

### Really, 0.999999… is equal to 1. Surreally, this is not so!

The value of the recurring decimal 0.999999 … is a popular topic of conversation amongst amateur mathematicians of various levels of knowledge and expertise. Some of the discussions on the web are of little value or interest, but the topic touches on several subtle and deep aspects of number theory.

[Image Wikimedia Commons]

### Random Numbers Plucked from the Atmosphere

Randomness is a slippery concept, defying precise definition. A simple example of a random series is provided by repeatedly tossing a coin. Assigning “1” for heads and “0” for tails, we generate a random sequence of binary digits or bits. Ten tosses might produce a sequence such as 1001110100. Continuing thus, we can generate a sequence of any length having no discernible pattern [TM152 or search for “thatsmaths” at irishtimes.com].

### Listing the Rational Numbers III: The Calkin-Wilf Tree

The rational numbers are countable: they can be put into one-to-one correspondence with the natural numbers. In previous articles we showed how the rationals can be presented as a list that includes each rational precisely once. One approach leads to the Farey Sequences. A second, related, approach gives us the Stern-Brocot Tree. Here, we introduce another tree structure, The Calkin-Wilf Tree.

### Listing the Rational Numbers II: The Stern-Brocot Tree

The rational numbers are countable: they can be put into one-to-one correspondence with the natural numbers. But it is not obvious how to construct a list that is sure to contain every rational number precisely once. In a previous post we described the Farey Sequences. Here we examine another, related, approach.

### Listing the Rational Numbers: I. Farey Sequences

We know, thanks to Georg Cantor, that the rational numbers — ratios of integers — are countable: they can be put into one-to-one correspondence with the natural numbers.

### Hardy’s Apology

Godfrey Harold Hardy’s memoir, A Mathematician’s Apology, was published when he was 63 years old. It is a slight volume at just 90 pages, but is replete with interesting observations and not a few controversial opinions. After 78 years, it is still in print and is available in virtually every mathematics library. Though many of Hardy’s opinions are difficult to support and some of his predictions have turned out to be utterly wrong, the book is still well worth reading.

### Kaprekar’s Number 6174

The Indian mathematician D. R. Kaprekar spent many happy hours during his youth solving mathematical puzzles. He graduated from Fergusson College in Pune in 1929 and became a mathematical teacher at a school in Devlali, north-east of Mumbai.

Kaprekar process for three digit numbers converging to 495 [Wikimedia Commons].

### More on Moduli

We wrote last week on modular arithmetic, the arithmetic of remainders. Here we will examine a few other aspects of this huge subject. Modular arithmetic was advanced by Gauss in his Disquisitiones Arithmeticae. In this system, number wrap around when they reach a point known as the modulus. Numbers that differ by a multiple of the modulus are called congruent. Thus 4, 11 and 18 are all congruent modulo 7.

Addition table for numbers modulo 12.

### Fractions of Fractions of Fractions

Numbers can be expressed in several different ways. We are familiar with whole numbers, fractions and decimals. But there is a wide range of other forms, and we examine one of them in this article. Every rational number ${x}$ can be expanded as a continued fraction:

$\displaystyle x = a_0 + \cfrac{1}{ a_1 + \cfrac{1}{ a_2 + \cfrac{1}{ a_3 + \dotsb + \cfrac{1}{a_n} } }} = [ a_0 ; a_1 , a_2 , a_3 , \dots , a_n ]$

where all ${a_n}$ are integers, all positive except perhaps ${a_0}$. If ${a_n=1}$ we add it to ${a_{n-1}}$; then the expansion is unique.

### It’s as Easy as Pi

Every circle has the property that the distance around it is just over three times the distance across. This has been known since the earliest times  [see TM120 or search for “thatsmaths” at irishtimes.com].

The constant ratio of the circumference to the diameter, denoted by the Greek letter pi, is familiar to every school-child. You might expect to find a proof in Euclid’s Elements of Geometry, he could not prove it, and he made no mention of the ratio (see last week’s post).

### A Remarkable Pair of Sequences

The terms of the two integer sequences below are equal for all ${n}$ such that ${1,  but equality is violated for this enormous value and, intermittently, for larger values of ${n}$.

### A Geometric Sieve for the Prime Numbers

In the time before computers (BC) various ingenious devices were invented for aiding the extensive calculations required in astronomy, navigation and commerce. In addition to calculators and logarithms, several nomograms were devised for specific applications, for example in meteorology and surveying.

### Numerical Coincidences

A numerical coincidence is an equality or near-equality between different mathematical quantities which has no known theoretical explanation. Sometimes such equalities remain mysterious and intriguing, and sometimes theory advances to the point where they can be explained and are no longer regarded as surprising.

Cosine of 355 radians is almost exactly equal to -1. Is this a coincidence? Read on!

### Brun’s Constant and the Pentium Bug

Euclid showed by a deliciously simple argument that the number of primes is infinite. In a completely different manner, Euler confirmed the same result. Euler’s conclusion followed from his demonstration that the sum of the reciprocals of the primes diverges:

$\displaystyle \sum_{p\in\mathbb{P}} \frac{1}{p} = \infty$

Obviously, this could not happen if there were only finitely many primes.

### The Shaky Foundations of Mathematics

The claim is often made that mathematical results are immutable. Once proven, they remain forever valid. But things are not so simple. There are problems at the very core of mathematics that cast a shadow of uncertainty. We can never be absolutely sure that the foundations of our subject are rock-solid [TM104 or search for “thatsmaths” at irishtimes.com].

Left: Plato and Aristotle. Centre: Pythagoras. Right: Euclid [Raphael, The School of Athens]

The ancient Greeks put geometry on a firm footing. Euclid set down a list of axioms, or basic intuitive assumptions. Upon these, the entire edifice of Euclidean geometry is constructed. This axiomatic approach has been the model for mathematics ever since.

### A Ton of Wonders

Every number is interesting. Suppose there were uninteresting numbers. Then there would be a smallest one. But this is an interesting property, contradicting the supposition. By reductio ad absurdum, there are none!

This is the hundredth “That’s Maths” article to appear in The Irish Times [TM100, or search for “thatsmaths” at irishtimes.com]. To celebrate the event, we have composed an ode to the number 100.

### Negative Number Names

The counting numbers that we learn as children are so familiar that using them is second nature. They bear the appropriate name natural numbers. From then on, names of numbers become less and less apposite.

### Random Harmonic Series

We consider the convergence of the random harmonic series

$\displaystyle R = \sum_{n=1}^{\infty}\frac{\sigma_{n}}{n}$

where ${\sigma_n\in\{-1,+1\}}$ is chosen randomly with probability ${1/2}$ of being either plus one or minus one. It follows from the Kolmogorov three-series theorem that the series is “almost surely” convergent.