In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, a
real number
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every ...
is said to be simply normal in an
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
base b if its infinite sequence of
digits is distributed uniformly in the sense that each of the
b digit values has the same
natural density In number theory, natural density (also referred to as asymptotic density or arithmetic density) is one method to measure how "large" a subset of the set of natural numbers is. It relies chiefly on the probability of encountering members of the ...
1/
b. A number is said to be normal in base
b if, for every positive integer
n, all possible strings
n digits long have density
b−''n''.
Intuitively, a number being simply normal means that no digit occurs more frequently than any other. If a number is normal, no finite combination of digits of a given length occurs more frequently than any other combination of the same length. A normal number can be thought of as an infinite sequence of coin flips (
binary) or rolls of a die (
base 6
A senary () numeral system (also known as base-6, heximal, or seximal) has six as its base. It has been adopted independently by a small number of cultures. Like decimal, it is a semiprime, though it is unique as the product of the only two con ...
). Even though there ''will'' be sequences such as 10, 100, or more consecutive tails (binary) or fives (base 6) or even 10, 100, or more repetitions of a sequence such as tail-head (two consecutive coin flips) or 6-1 (two consecutive rolls of a die), there will also be equally many of any other sequence of equal length. No digit or sequence is "favored".
A number is said to be normal (sometimes called absolutely normal) if it is normal in all integer bases greater than or equal to 2.
While a general proof can be given that
almost all
In mathematics, the term "almost all" means "all but a negligible amount". More precisely, if X is a set, "almost all elements of X" means "all elements of X but those in a negligible subset of X". The meaning of "negligible" depends on the mathema ...
real numbers are normal (meaning that the
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
of non-normal numbers has
Lebesgue measure
In measure theory, a branch of mathematics, the Lebesgue measure, named after French mathematician Henri Lebesgue, is the standard way of assigning a measure to subsets of ''n''-dimensional Euclidean space. For ''n'' = 1, 2, or 3, it coincides wi ...
zero), this proof is not
constructive
Although the general English usage of the adjective constructive is "helping to develop or improve something; helpful to someone, instead of upsetting and negative," as in the phrase "constructive criticism," in legal writing ''constructive'' has ...
, and only a few specific numbers have been shown to be normal. For example,
Chaitin's constant
In the computer science subfield of algorithmic information theory, a Chaitin constant (Chaitin omega number) or halting probability is a real number that, informally speaking, represents the probability that a randomly constructed program will ...
is normal (and
uncomputable
Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can do ...
). It is widely believed that the (computable) numbers
,
, and ''
e'' are normal, but a proof remains elusive.
Definitions
Let be a finite
alphabet
An alphabet is a standardized set of basic written graphemes (called letters) that represent the phonemes of certain spoken languages. Not all writing systems represent language in this way; in a syllabary, each character represents a syllab ...
of -digits, the set of all infinite
sequence
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is called ...
s that may be drawn from that alphabet, and the set of finite sequences, or
strings
String or strings may refer to:
*String (structure), a long flexible structure made from threads twisted together, which is used to tie, bind, or hang other objects
Arts, entertainment, and media Films
* ''Strings'' (1991 film), a Canadian anim ...
. Let be such a sequence. For each in let denote the number of times the digit appears in the first digits of the sequence . We say that is simply normal if the
limit
Limit or Limits may refer to:
Arts and media
* ''Limit'' (manga), a manga by Keiko Suenobu
* ''Limit'' (film), a South Korean film
* Limit (music), a way to characterize harmony
* "Limit" (song), a 2016 single by Luna Sea
* "Limits", a 2019 ...
for each . Now let be any finite string in and let be the number of times the string appears as a
substring
In formal language theory and computer science, a substring is a contiguous sequence of characters within a string. For instance, "''the best of''" is a substring of "''It was the best of times''". In contrast, "''Itwastimes''" is a subsequenc ...
in the first digits of the sequence . (For instance, if , then .) is normal if, for all finite strings ,
where denotes the length of the string . In other words, is normal if all strings of equal length occur with equal
asymptotic frequency. For example, in a normal binary sequence (a sequence over the alphabet ), and each occur with frequency ; , , , and each occur with frequency ; , , , , , , , and each occur with frequency ; etc. Roughly speaking, the
probability
Probability is the branch of mathematics concerning numerical descriptions of how likely an event is to occur, or how likely it is that a proposition is true. The probability of an event is a number between 0 and 1, where, roughly speakin ...
of finding the string in any given position in is precisely that expected if the sequence had been produced at
random
In common usage, randomness is the apparent or actual lack of pattern or predictability in events. A random sequence of events, symbols or steps often has no order and does not follow an intelligible pattern or combination. Individual ra ...
.
Suppose now that is an
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
greater than 1 and is a
real number
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every ...
. Consider the infinite digit sequence expansion of in the base
positional number system
Positional notation (or place-value notation, or positional numeral system) usually denotes the extension to any base of the Hindu–Arabic numeral system (or decimal system). More generally, a positional system is a numeral system in which the ...
(we ignore the decimal point). We say that is simply normal in base if the sequence is simply normal and that is normal in base if the sequence is normal. The number is called a normal number (or sometimes an absolutely normal number) if it is normal in base for every integer greater than 1.
A given infinite sequence is either normal or not normal, whereas a real number, having a different base- expansion for each integer , may be normal in one base but not in another (in which case it is not a normal number). For bases and with
rational
Rationality is the quality of being guided by or based on reasons. In this regard, a person acts rationally if they have a good reason for what they do or a belief is rational if it is based on strong evidence. This quality can apply to an abi ...
(so that and ) every number normal in base is normal in base . For bases and with irrational, there are uncountably many numbers normal in each base but not the other.
A
disjunctive sequence A disjunctive sequence is an infinite sequence (over a finite alphabet of characters) in which every finite string appears as a substring. For instance, the binary Champernowne sequence
:0\ 1\ 00\ 01\ 10\ 11\ 000\ 001 \ldots
formed by concatenat ...
is a sequence in which every finite string appears. A normal sequence is disjunctive, but a disjunctive sequence need not be normal. A ''
rich number
Rich may refer to:
Common uses
* Rich, an entity possessing wealth
* Rich, an intense flavor, color, sound, texture, or feeling
** Rich (wine), a descriptor in wine tasting
Places United States
* Rich, Mississippi, an unincorporated comm ...
'' in base is one whose expansion in base is disjunctive: one that is disjunctive to every base is called ''absolutely disjunctive'' or is said to be a ''
lexicon''. A number normal in base is rich in base , but not necessarily conversely. The real number is rich in base if and only if the set is
dense
Density (volumetric mass density or specific mass) is the substance's mass per unit of volume. The symbol most often used for density is ''ρ'' (the lower case Greek letter rho), although the Latin letter ''D'' can also be used. Mathematically ...
in the
unit interval
In mathematics, the unit interval is the closed interval , that is, the set of all real numbers that are greater than or equal to 0 and less than or equal to 1. It is often denoted ' (capital letter ). In addition to its role in real analysis ...
.
[ denotes the fractional part of .]
We defined a number to be simply normal in base if each individual digit appears with frequency . For a given base , a number can be simply normal (but not normal or -dense,) -dense (but not simply normal or normal), normal (and thus simply normal and -dense), or none of these. A number is absolutely non-normal or absolutely abnormal if it is not simply normal in any base.
Properties and examples
The concept of a normal number was introduced by . Using the
Borel–Cantelli lemma
In probability theory, the Borel–Cantelli lemma is a theorem about sequences of events. In general, it is a result in measure theory. It is named after Émile Borel and Francesco Paolo Cantelli, who gave statement to the lemma in the first de ...
, he proved that
almost all
In mathematics, the term "almost all" means "all but a negligible amount". More precisely, if X is a set, "almost all elements of X" means "all elements of X but those in a negligible subset of X". The meaning of "negligible" depends on the mathema ...
real numbers are normal, establishing the existence of normal numbers. showed that it is possible to specify a particular such number. proved that there is a
computable
Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is close ...
absolutely normal number.
Although this construction does not directly give the digits of the numbers constructed, it shows that it is possible in principle to enumerate all the digits of a particular normal number.
The set of non-normal numbers, despite being "large" in the sense of being
uncountable
In mathematics, an uncountable set (or uncountably infinite set) is an infinite set that contains too many elements to be countable. The uncountability of a set is closely related to its cardinal number: a set is uncountable if its cardinal num ...
, is also a
null set (as its Lebesgue measure as a subset of the real numbers is zero, so it essentially takes up no space within the real numbers). Also, the non-normal numbers (as well as the normal numbers) are dense in the reals: the set of non-normal numbers between two distinct real numbers is non-empty since it contains
every rational number (in fact, it is uncountably infinite and even
comeagre
In the mathematical field of general topology, a meagre set (also called a meager set or a set of first category) is a subset of a topological space that is small or negligible in a precise sense detailed below. A set that is not meagre is calle ...
). For instance, there are uncountably many numbers whose decimal expansions (in base 3 or higher) do not contain the digit 1, and none of these numbers is normal.
Champernowne's constant
obtained by concatenating the decimal representations of the
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''Cardinal n ...
s in order, is normal in base 10. Likewise, the different variants of Champernowne's constant (done by performing the same concatenation in other bases) are normal in their respective bases (for example, the base-2 Champernowne constant is normal in base 2), but they have not been proven to be normal in other bases.
The
Copeland–Erdős constant The Copeland–Erdős constant is the concatenation of "0." with the base 10 representations of the prime numbers in order. Its value, using the modern definition of prime, is approximately
:0.235711131719232931374143… .
The constant is irration ...
obtained by concatenating the
prime number
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
s in base 10, is normal in base 10, as proved by . More generally, the latter authors proved that the real number represented in base ''b'' by the concatenation
where ''f''(''n'') is the ''n''
th prime expressed in base ''b'', is normal in base ''b''. proved that the number represented by the same expression, with ''f''(''n'') = ''n''
2,
obtained by concatenating the
square number
In mathematics, a square number or perfect square is an integer that is the square (algebra), square of an integer; in other words, it is the multiplication, product of some integer with itself. For example, 9 is a square number, since it equals ...
s in base 10, is normal in base 10. proved that the number represented by the same expression, with ''f'' being any non-constant polynomial whose values on the positive integers are positive integers, expressed in base 10, is normal in base 10.
proved that if ''f''(''x'') is any non-constant
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An example ...
with real coefficients such that ''f''(''x'') > 0 for all ''x'' > 0, then the real number represented by the concatenation
where
'f''(''n'')is the
integer part
In mathematics and computer science, the floor function is the function that takes as input a real number , and gives as output the greatest integer less than or equal to , denoted or . Similarly, the ceiling function maps to the least int ...
of ''f''(''n'') expressed in base ''b'', is normal in base ''b''. (This result includes as special cases all of the above-mentioned results of Champernowne, Besicovitch, and Davenport & Erdős.) The authors also show that the same result holds even more generally when ''f'' is any function of the form
where the αs and βs are real numbers with β > β
1 > β
2 > ... > β
''d'' ≥ 0, and ''f''(''x'') > 0 for all ''x'' > 0.
show an explicit
uncountably infinite
In mathematics, an uncountable set (or uncountably infinite set) is an infinite set that contains too many elements to be countable. The uncountability of a set is closely related to its cardinal number: a set is uncountable if its cardinal num ...
class of ''b''-normal numbers by perturbing
Stoneham numbers.
It has been an elusive goal to prove the normality of numbers that are not artificially constructed. While
,
π,
ln(2) The decimal value of the natural logarithm of 2
is approximately
:\ln 2 \approx 0.693\,147\,180\,559\,945\,309\,417\,232\,121\,458.
The logarithm of 2 in other bases is obtained with the formula
:\log_b 2 = \frac.
The common logarithm in particula ...
, and
e are strongly conjectured to be normal, it is still not known whether they are normal or not. It has not even been proven that all digits actually occur infinitely many times in the decimal expansions of those constants (for example, in the case of π, the popular claim "every string of numbers eventually occurs in π" is not known to be true). It has also been conjectured that every
irrational
Irrationality is cognition, thinking, talking, or acting without inclusion of rationality. It is more specifically described as an action or opinion given through inadequate use of reason, or through emotional distress or cognitive deficiency. T ...
algebraic number is absolutely normal (which would imply that is normal), and no counterexamples are known in any base. However, no irrational algebraic number has been proven to be normal in any base.
Non-normal numbers
No
rational number
In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all ration ...
is normal in any base, since the digit sequences of rational numbers are
eventually periodic. However, a rational number can be ''simply'' normal in a particular base. For example,
is simply normal in base 10.
gives an example of an irrational number that is absolutely abnormal. Let
Then α is a Liouville number and is absolutely abnormal.
Properties
Additional properties of normal numbers include:
* Every non-zero real number is the product of two normal numbers. This follows from the general fact that every number is the product of two numbers from a set
if the complement of ''X'' has measure 0.
* If ''x'' is normal in base ''b'' and ''a'' ≠ 0 is a rational number, then
is also normal in base ''b''.
* If
is ''dense'' (for every
and for all sufficiently large ''n'',
) and
are the base-''b'' expansions of the elements of ''A'', then the number
, formed by concatenating the elements of ''A'', is normal in base ''b'' (Copeland and Erdős 1946). From this it follows that Champernowne's number is normal in base 10 (since the set of all positive integers is obviously dense) and that the Copeland–Erdős constant is normal in base 10 (since the
prime number theorem implies that the set of primes is dense).
* A sequence is normal
if and only if
In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false.
The connective is b ...
every ''block'' of equal length appears with equal frequency. (A block of length ''k'' is a substring of length ''k'' appearing at a position in the sequence that is a multiple of ''k'': e.g. the first length-''k'' block in ''S'' is ''S''
..''k'' the second length-''k'' block is ''S''
'k''+1..2''k'' etc.) This was implicit in the work of and made explicit in the work of .
* A number is normal in base ''b'' if and only if it is simply normal in base ''b
k'' for all
. This follows from the previous block characterization of normality: Since the ''n''
th block of length ''k'' in its base ''b'' expansion corresponds to the ''n''
th digit in its base ''b
k'' expansion, a number is simply normal in base ''b
k'' if and only if blocks of length ''k'' appear in its base ''b'' expansion with equal frequency.
* A number is normal if and only if it is simply normal in every base. This follows from the previous characterization of base ''b'' normality.
* A number is ''b''-normal if and only if there exists a set of positive integers