almost all
(another Prime Pages' Glossary entries)
The Prime Glossary
Glossary: Prime Pages: Top 5000:
GIMPS has discovered a new largest known prime number: 282589933-1 (24,862,048 digits)

Often mathematicians use expressions such as "almost every positive integer is composite" or "almost all real numbers are irrational." In each case almost every or almost all means all but a "negligible" fraction, but how we define that fraction (and negligible) depends on the underlying set.

In the positive integers (the usual case in this glossary):

Let P(n) be a predicate (a statement about the integer n such as "n is prime"). Let #P(N) be the number of positive integers n less than N which satisfy P(n). For example, if P(n) = "n is even," then #P(N) is floor(N/2).

If the ratio #P(N)/N gets arbitrarily close to 1 as N gets big (that is, lim #P(N)/N = 1 as N approaches infinity), then we say "for almost every n, P(n)."

For example, if P(n) is "n is composite," then #P(N) is about (1 - 1/log N) N (by the prime number theorem), so #P(N)/N is about 1-1/log N. This clearly gets close to 1 as N gets large; so, almost every positive integer is composite.

In other sets:
In other sets the concept "almost every" is defined in different ways. For example, in the real numbers a common way to define "almost every" is to specify all but a set of measure zero (usually using the Lesbegue measure). These ideas are beyond the scope of this glossary.




Chris K. Caldwell © 1999-2019 (all rights reserved)