Growth of Integers

Size and Growth

The integers extend infinitely in both directions:

In number theory, one usually studies the size of an integer through its absolute value. The size of $n$ is measured by

For positive integers, this is simply $n$. For negative integers, it removes the sign:

Growth concerns how quantities behave as $n$ becomes large. Many arithmetic questions are not about one fixed integer, but about infinitely many integers at once. For example, instead of asking whether $101$ is prime, one may ask how many primes are less than a large number $x$.

Linear Growth

The simplest growth pattern is linear growth. A sequence grows linearly if its size is comparable to $n$.

For example,

grows linearly because increasing $n$ by $1$ increases $a_n$ by $3$.

Linear functions have the form

where $a$ and $b$ are fixed constants.

For large $n$, the term $an$ dominates the constant $b$. Thus

and

have essentially the same large-scale growth.

Polynomial Growth

A sequence has polynomial growth if it is bounded in size by a power of $n$. Examples include

The sequence

has quadratic growth. For large $n$, the highest-degree term dominates:

Polynomial growth appears frequently in counting problems, lattice point estimates, and complexity analysis.

Exponential Growth

Exponential growth is much faster than polynomial growth. A typical example is

The first few values are

Each step multiplies the previous value by $2$.

More generally, if $a>1$, then

grows exponentially.

Exponential growth dominates polynomial growth. For every fixed integer $k$,

once $n$ is sufficiently large.

This fact is often proved by induction or by estimating ratios.

Logarithmic Growth

Logarithmic growth is slower than polynomial growth. The logarithm measures how many times a number must be multiplied by a base to reach a given size.

For base $2$, the quantity

is the number of doublings needed to reach $n$.

For example,

because

Logarithms appear naturally in number theory. The number of binary digits of a positive integer $n$ is approximately

Thus logarithms measure the length of an integer when written in positional notation.

Comparing Growth Rates

The basic hierarchy of growth is

Here the symbol $\ll$ informally means “grows much more slowly than.”

For example, when $n=10$,

When $n=100$,

but

has more than thirty decimal digits.

The difference becomes enormous as $n$ increases.

Big-O Notation

To compare growth precisely, mathematicians use asymptotic notation.

We write

if there exists a constant $C>0$ and an integer $N$ such that

for every $n\ge N$.

This means that $g(n)$ eventually bounds the size of $f(n)$, up to a constant factor.

For example,

Indeed, for $n\ge1$,

Similarly,

Big-O notation ignores lower-order terms and constant factors. It records the large-scale rate of growth.

Growth and Arithmetic Problems

Growth estimates appear throughout number theory.

The prime counting function $\pi(x)$ counts the number of primes less than or equal to $x$. A central theorem of analytic number theory says that $\pi(x)$ grows approximately like

The divisor function $d(n)$, which counts the number of positive divisors of $n$, grows much more slowly than $n$, but irregularly.

Factorials grow very quickly:

They grow faster than any exponential $a^n$ with fixed $a$, once $n$ is large enough.

Growth as a Number-Theoretic Tool

Growth is not merely a way to describe size. It is often used to prove impossibility.

For example, if two integer expressions have incompatible growth rates, they cannot be equal for infinitely many values of $n$. Many Diophantine arguments depend on comparing the sizes of terms.

Growth also appears in algorithms. An algorithm that factors integers by checking all possible divisors up to $n$ behaves very differently from one that checks only up to $\sqrt n$. The second is much faster because

grows much more slowly than

Thus the study of integer growth connects elementary arithmetic with analysis, computation, and modern number theory.