Growth of Integers
The integers extend infinitely in both directions:
Size and Growth
The integers extend infinitely in both directions:
$$ \cdots,-3,-2,-1,0,1,2,3,\cdots $$
In number theory, one usually studies the size of an integer through its absolute value. The size of $n$ is measured by
$$ |n|. $$
For positive integers, this is simply $n$. For negative integers, it removes the sign:
$$ |-n|=n. $$
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,
$$ a_n=3n+2 $$
grows linearly because increasing $n$ by $1$ increases $a_n$ by $3$.
Linear functions have the form
$$ an+b, $$
where $a$ and $b$ are fixed constants.
For large $n$, the term $an$ dominates the constant $b$. Thus
$$ 3n+2 $$
and
$$ 3n $$
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
$$ n^2,\qquad n^3,\qquad n^{10}. $$
The sequence
$$ a_n=n^2+5n+1 $$
has quadratic growth. For large $n$, the highest-degree term dominates:
$$ n^2+5n+1 \approx n^2. $$
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
$$ 2^n. $$
The first few values are
$$ 2,4,8,16,32,64,\ldots $$
Each step multiplies the previous value by $2$.
More generally, if $a>1$, then
$$ a^n $$
grows exponentially.
Exponential growth dominates polynomial growth. For every fixed integer $k$,
$$ n^k<2^n $$
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
$$ \log_2 n $$
is the number of doublings needed to reach $n$.
For example,
$$ \log_2 8=3 $$
because
$$ 2^3=8. $$
Logarithms appear naturally in number theory. The number of binary digits of a positive integer $n$ is approximately
$$ \log_2 n. $$
Thus logarithms measure the length of an integer when written in positional notation.
Comparing Growth Rates
The basic hierarchy of growth is
$$ \log n \ll n \ll n^2 \ll n^3 \ll 2^n. $$
Here the symbol $\ll$ informally means "grows much more slowly than."
For example, when $n=10$,
$$ n^2=100, \qquad 2^n=1024. $$
When $n=100$,
$$ n^2=10000, $$
but
$$ 2^n $$
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
$$ f(n)=O(g(n)) $$
if there exists a constant $C>0$ and an integer $N$ such that
$$ |f(n)|\le C|g(n)| $$
for every $n\ge N$.
This means that $g(n)$ eventually bounds the size of $f(n)$, up to a constant factor.
For example,
$$ 3n+2=O(n). $$
Indeed, for $n\ge1$,
$$ 3n+2\le5n. $$
Similarly,
$$ n^2+5n+1=O(n^2). $$
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
$$ \frac{x}{\log x}. $$
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:
$$ n!=1\cdot2\cdot3\cdots n. $$
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
$$ \sqrt n $$
grows much more slowly than
$$ n. $$
Thus the study of integer growth connects elementary arithmetic with analysis, computation, and modern number theory.