# Growth of Integers

## 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.