Fact-checked by Grok 2 weeks ago

Arithmetic progression

An arithmetic progression, also known as an , is a of numbers in which the between consecutive s is constant, referred to as the common d. This constant distinguishes arithmetic progressions from other types of s, such as geometric progressions, where s are multiplied by a fixed . The general form of an arithmetic progression begins with a first a_1 (or simply a), followed by s generated by adding d successively: a, a + d, a + 2d, \dots. The nth of the is given by the formula a_n = a + (n-1)d, which allows for the identification of any based on its position. For the sum of the first n s, denoted S_n, two equivalent formulas are commonly used: S_n = \frac{n}{2} [2a + (n-1)d] or S_n = \frac{n}{2} (a + a_n), facilitating calculations for finite s. Arithmetic progressions have been recognized since ancient times, with early examples appearing in the Egyptian around 1650 BCE, where they were used in practical computations such as dividing grain among workers. In modern mathematics, they form a foundational concept in and are extensively applied in fields such as —for instance, in studying primes within arithmetic progressions—and in real-world scenarios like for annuities and loan repayments. Their simplicity and linear structure make them essential for understanding more complex sequences and series in .

Fundamentals

Definition

An arithmetic progression is a sequence of numbers such that the difference between any two successive members of the sequence is a constant. Formally, a sequence \{a_k\} where k = 1, 2, \dots, n is an arithmetic progression if there exists a constant d (called the common difference) such that a_{k+1} - a_k = d for all k. This distinguishes it from a geometric progression, in which the ratio between successive terms remains constant rather than the difference. Arithmetic progressions may be finite, consisting of a limited number of terms, or , extending indefinitely. However, an arithmetic progression does not converge to a finite unless d = 0, in which case it is a constant . As a fundamental type of , arithmetic progressions provide essential groundwork for studying broader concepts in sequences and series.

Notation and Examples

In standard mathematical notation, an arithmetic progression (AP) is typically denoted by its first term a (or sometimes a_1) and common difference d, with the general term given by a_n = a + (n-1)d for the nth term, where n is a positive integer. This notation allows for concise description of the sequence's terms, emphasizing the linear increase or decrease by the fixed difference d. Consider a simple finite AP: 2, 5, 8, 11, where a = 2 and d = 3. Here, each term is obtained by adding 3 to the previous one, illustrating a positive common difference that generates increasing values. For a decreasing sequence, take 10, 7, 4, with a = 10 and d = -3, showing how a negative d produces successively smaller terms. A constant sequence, such as 5, 5, 5, ..., arises when d = 0, where all terms remain identical regardless of position. To visualize an AP, the terms can be arranged in a table showing the index, term value, and cumulative effect of the common difference:
Index nTerm a_nCalculation
12a + (1-1)d = 2
25$2 + 3 = 5
38$5 + 3 = 8
411$8 + 3 = 11
This tabular form highlights the consistent addition of d across terms, aiding intuition for the progression's structure. In real-world contexts, arithmetic progressions model evenly spaced events, such as dates occurring every fixed interval (e.g., biweekly paydays on the 1st and 15th of each month, with a = 1, d = 14) or appointments scheduled at regular time gaps.

Core Formulas

nth Term

The nth term of an arithmetic progression, denoted a_n, is given by the explicit a_n = a_1 + (n-1)d, where a_1 is the first term, n is the term number, and d is the common difference. This formula arises from the recursive definition of the sequence, where each subsequent term is obtained by adding the common difference to the previous term: a_{k+1} = a_k + d for k = 1, 2, \dots. Unfolding the recursion step by step yields a_2 = a_1 + d, a_3 = a_2 + d = a_1 + 2d, a_4 = a_3 + d = a_1 + 3d, and in general, a_n = a_1 + (n-1)d. The formula can be rigorously established using mathematical induction on n. For the base case n=1, a_1 = a_1 + (1-1)d = a_1, which holds. Assume the statement is true for n = k, so a_k = a_1 + (k-1)d. For the inductive step, consider n = k+1: a_{k+1} = a_k + d = [a_1 + (k-1)d] + d = a_1 + kd = a_1 + ((k+1)-1)d. Thus, the formula holds for n = k+1. By the principle of mathematical induction, it is true for all positive integers n \geq 1. Rearranging the formula allows solving for other parameters. For instance, the common difference is d = \frac{a_n - a_1}{n-1} for [n > 1](/page/N+1), and the term number n can be found as n = 1 + \frac{a_n - a_1}{d} assuming d \neq 0.

Common Difference

In an arithmetic progression (), the common difference d is the constant value by which each term differs from the preceding one, ensuring uniform spacing throughout the sequence. To identify d from a given sequence, subtract the first term from the second: d = a_2 - a_1, where a_1 and a_2 are the initial terms. For sequences with more than two terms, compute the differences between all consecutive pairs and verify their consistency; if all differences equal the same value, the sequence forms an AP with that common difference d. The sign of d determines the progression's direction: if d > 0, the sequence is strictly increasing; if d < 0, it is strictly decreasing; and if d = 0, the sequence is constant, with all terms identical. This property directly relates to the sequence's monotonicity, as the constant difference preserves the order of terms without reversals or irregularities. A key characteristic of APs is the arithmetic mean property, where the average of any two terms equals the term at the midpoint position between them, provided the terms are equally spaced by d. For instance, the mean of terms a_m and a_n (with m < n) is the term a_k where k = (m + n)/2, reflecting the linear interpolation inherent in the progression. Any finite AP of length n is uniquely determined by its first term a_1, the common difference d, and the number of terms n, as these parameters fix all subsequent terms without ambiguity. This uniqueness stems from the recursive construction of the sequence, where each term is generated solely from the prior one via addition of d.

Sums

Sum Formula

The sum S_n of the first n terms of a finite arithmetic progression, with first term a_1 and common difference d, is given by the closed-form formula S_n = \frac{n}{2} (a_1 + a_n), where a_n denotes the nth term of the progression. This expression leverages the fact that the terms are equally spaced, allowing the total to be computed directly from the endpoints. An equivalent form substitutes the expression for the nth term, a_n = a_1 + (n-1)d, yielding S_n = \frac{n}{2} [2a_1 + (n-1)d]. Both versions represent n times the average of the first and last terms, highlighting the progression's linear symmetry. Special cases arise when the progression consists of consecutive integers or multiples thereof. For the sum of the first n natural numbers (where a_1 = 1 and d = 1), the formula simplifies to S_n = \frac{n(n+1)}{2}. The sum of the first n even positive integers (sequence starting at 2 with d = 2) is S_n = n(n+1). Similarly, the sum of the first n odd positive integers (starting at 1 with d = 2) equals n^2. This formula provides computational efficiency by enabling direct evaluation in constant time, independent of n, rather than requiring iterative addition of all terms, which scales linearly with the sequence length.

Derivation

One common way to derive the sum formula is by pairing terms from the beginning and end of the sequence. Write the sum twice: once forward S_n = a_1 + (a_1 + d) + \cdots + a_n and once backward S_n = a_n + (a_n - d) + \cdots + a_1. Adding these gives $2S_n = n(a_1 + a_n), so S_n = \frac{n}{2} (a_1 + a_n). Substituting a_n = a_1 + (n-1)d yields the alternative form S_n = \frac{n}{2} [2a_1 + (n-1)d]. Alternatively, the formula can be proved by mathematical induction. For the base case n=1, S_1 = a_1, which holds. Assume true for n=k: S_k = \frac{k}{2} [2a_1 + (k-1)d]. For n=k+1, S_{k+1} = S_k + a_{k+1} = \frac{k}{2} [2a_1 + (k-1)d] + [a_1 + k d]. Simplifying gives S_{k+1} = \frac{k+1}{2} [2a_1 + k d], confirming the formula.

Applications

In physics, arithmetic progressions are commonly applied to model the motion of objects under uniform acceleration, where the distances traveled in successive equal time intervals form an arithmetic sequence. For instance, in uniformly accelerated motion starting from rest, the distance covered in the first interval is \frac{1}{2} a t^2, in the second \frac{3}{2} a t^2, and so on, with a common difference of a t^2, allowing the total distance s over n intervals to be computed as the sum of this progression. This sum yields the formula s = \frac{n}{2} (u + v), where u is the initial velocity and v is the final velocity after n intervals, providing a direct way to determine displacement without integrating velocity over time. In finance, the sum of an arithmetic progression calculates the total savings accumulated from equal periodic deposits into an account, assuming no interest or simple interest accrual. For equal instalments, the cumulative balance at the end of each period forms an arithmetic sequence, where each deposit adds a constant amount to the previous balance, and the total savings after n periods is S = \frac{n}{2} [2a + (n-1)d], with a as the initial deposit and d = 0 for fixed amounts, simplifying to S = n a. Similarly, for loan repayments structured as equal payments, the total amount repaid over time follows this summation when payments are constant, aiding in budgeting the principal and interest portions without compounding effects dominating. In computer science, sums of arithmetic progressions appear in the average-case analysis of algorithms exhibiting linear growth, such as , where the expected number of comparisons for inserting the k-th element into a sorted list averages \frac{k+1}{2}, and the total over n elements is the sum of this arithmetic sequence, yielding O(n^2) time complexity. This summation technique quantifies resource usage, like memory or operations, in scenarios where costs accumulate linearly across iterations, enabling efficient performance predictions for data processing tasks. Everyday applications of arithmetic progression sums include calculating total costs for tiered ticket pricing at events, where prices increase by a fixed amount per section, such as concert rows starting at $100 and rising by $50 each row, allowing the overall revenue from sold seats to be found via the progression sum. In sports, cumulative scores often form arithmetic sequences with a common difference of one point per play, as in volleyball sets where points add sequentially up to 25, and the total points across matches or innings can be summed to assess team performance or season totals efficiently.

Products

Product Formula

The product of the terms in a finite arithmetic progression (AP) with first term a, common difference d \neq 0, and n terms is given by P_n = \prod_{k=0}^{n-1} (a + k d) = d^n \left( \frac{a}{d} \right)^{(n)}, where \left( x \right)^{(n)} denotes the rising factorial (or Pochhammer symbol) defined as \left( x \right)^{(n)} = x (x+1) \cdots (x+n-1) for positive integer n. This rising factorial can be expressed in closed form using the gamma function as \left( x \right)^{(n)} = \frac{\Gamma(x + n)}{\Gamma(x)}, provided that x is not a non-positive integer where the gamma function has poles; thus, the general product formula becomes P_n = d^n \frac{\Gamma\left( \frac{a}{d} + n \right)}{\Gamma\left( \frac{a}{d} \right)}. This expression generalizes the product to cases where a/d may not be an integer, using the gamma function's extension of the factorial beyond positive integers. For APs consisting of positive integers, such as consecutive integers starting from 1 (i.e., a=1, d=1), the product simplifies to the factorial P_n = n!, since \Gamma(n+1) = n! for positive integer n. More generally, for an AP of consecutive integers starting from a positive integer m (i.e., m, m+1, \dots, m+n-1), the product is the ratio of factorials P_n = \frac{(m+n-1)!}{(m-1)!}. In cases where the AP terms are integers but not necessarily starting from 1, the product often involves ratios of factorials or shifted factorials, aligning with the gamma expression when a/d is integer. However, a simple closed form without special functions may not exist for arbitrary non-integer starting points or differences, as the gamma function is generally required for compactness; numerical evaluation or approximation may be needed otherwise. If the AP includes a zero term (i.e., a + k d = 0 for some integer k with $0 \leq k < n), the product is trivially zero. Additionally, for APs symmetric around their mean, such as those with an odd number of terms centered at zero (e.g., -m, -m+d, \dots, m), the product may exhibit sign alternations or specific symmetries, but the gamma-based formula still applies provided no poles are encountered. The product of an AP is closely related to when the common difference d=1 and a is a positive integer, as \binom{a+n-1}{n} = \frac{(a)^{(n)}}{n!} = \frac{P_n / 1^n}{n!}, linking it to combinatorial selections in higher dimensions or multiset coefficients.

Derivation

The product P_n = \prod_{k=0}^{n-1} (a_1 + k d) of the first n terms of an with initial term a_1 and common difference d (assuming d \neq 0 and terms such that the is defined) can be derived using the properties of the , or . Factoring out d^n, the product becomes P_n = d^n \prod_{k=0}^{n-1} \left( \frac{a_1}{d} + k \right) = d^n \left( \frac{a_1}{d} \right)_n, where (z)_n denotes the . The Pochhammer symbol is defined as the finite product (z)_n = z (z+1) \cdots (z + n - 1) for positive integer n, and it satisfies the relation (z)_n = \frac{\Gamma(z + n)}{\Gamma(z)} for complex z not a non-positive integer, where \Gamma is the . This identity follows iteratively from the functional equation of the gamma function, \Gamma(z + 1) = z \Gamma(z), applied n times: starting from \Gamma(z + n) = (z + n - 1) \Gamma(z + n - 1) = \cdots = (z + n - 1) \cdots z \ \Gamma(z), yielding the ratio form. Substituting this expression gives the closed-form P_n = d^n \frac{\Gamma\left( \frac{a_1}{d} + n \right)}{\Gamma\left( \frac{a_1}{d} \right)}. In the special case of consecutive positive integers, where a_1 = 1 and d = 1, the product simplifies to P_n = 1 \cdot 2 \cdots n = n!. This aligns with the gamma function property \Gamma(n + 1) = n! for positive integer n, since \frac{\Gamma(1 + n)}{\Gamma(1)} = \Gamma(n + 1) = n! (noting \Gamma(1) = 1). The derivation reduces directly to the factorial via the same iterative application of the gamma recurrence. An alternative approach to analyzing the product involves taking the natural logarithm: \ln P_n = \sum_{k=0}^{n-1} \ln(a_1 + k d). This sum is exact but typically not closed-form without special functions; however, for large n, it can be approximated by the integral \int_0^n \ln(a_1 + x d) \, dx = \frac{1}{d} \left[ (a_1 + x d) \ln(a_1 + x d) - (a_1 + x d) \right]_0^n, providing asymptotic behavior. The gamma function representation offers an exact expression, with Stirling's approximation \ln \Gamma(z) \approx (z - 1/2) \ln z - z + \frac{1}{2} \ln(2\pi) applicable for large |z| in special cases like integer arguments, yielding precise large-n estimates for \ln P_n.

Examples

A simple example of the product of terms in an arithmetic progression is the sequence 1, 3, 5, which has a common difference of 2; the product is $1 \times 3 \times 5 = 15. Another basic case is the progression 2, 5, 8 with common difference 3, yielding a product of $2 \times 5 \times 8 = 80. For a larger instance, consider the first five odd numbers forming the arithmetic progression 1, 3, 5, 7, 9 with common difference 2; their product is $1 \times 3 \times 5 \times 7 \times 9 = 945, which aligns with verification using the product formula for arithmetic progressions. Non-integer terms also form valid arithmetic progressions, such as 0.5, 1.5, 2.5 with common difference 1; the product is $0.5 \times 1.5 \times 2.5 = 1.875. These products exhibit patterns with combinatorial significance; for instance, the product of the first n odd numbers equals the double factorial (2n-1)!!, which counts the number of perfect matchings in a complete graph with $2n vertices and appears in permutation enumerations and series expansions.

Statistical Properties

Standard Deviation

The standard deviation of the terms in a finite arithmetic progression quantifies the dispersion around the arithmetic mean of the sequence. For a finite arithmetic progression consisting of n terms with common difference d, the standard deviation \sigma is given by \sigma = \frac{|d|}{2} \sqrt{\frac{n^2 - 1}{3}}. This formula arises from computing the population variance \frac{1}{n} \sum (a_k - \bar{a})^2, where a_k denotes the k-th term and \bar{a} is the mean, which simplifies using the equally spaced nature of the terms. The value of \sigma measures the typical deviation of terms from the mean, scaling linearly with |d| and roughly with \sqrt{n} for large sequences, thereby capturing how the common difference and sequence length influence overall spread. This property aligns with viewing the arithmetic progression as a realization of a discrete uniform distribution over the points \{a, a+d, \dots, a+(n-1)d\}, where the variance matches that of a standard discrete uniform on \{1, 2, \dots, n\} scaled by d^2. In the special case of a constant progression (d=0), \sigma = 0 since all terms coincide at the mean; otherwise, \sigma increases with n, indicating progressively wider dispersion as more terms are included.

Related Measures

In an (AP) consisting of n terms with common difference d, the population variance of the terms, treating them as a discrete uniform sample, is given by \text{Var} = \frac{d^2 (n^2 - 1)}{12}. This formula arises because the AP terms are affinely equivalent to the scaled integers from 0 to n-1, whose variance is \frac{n^2 - 1}{12}, and affine transformations preserve the variance up to scaling by d^2. Due to the inherent symmetry of an AP around its mean, the skewness is zero, indicating no asymmetry in the distribution of terms. The kurtosis of an AP reflects its uniform-like spread, with excess kurtosis \gamma_2 = -\frac{6(n^2 + 1)}{5(n^2 - 1)}, which is negative for n > 1, characterizing a platykurtic with lighter tails and a flatter compared to the normal distribution. In a symmetric AP, the equals the ; for odd n, it is the middle term, and for even n, it is the of the two central terms. The s of an AP leverage its linear structure: odd-order central moments vanish due to symmetry, while even-order moments \mu_k (for even k) are d^k times the k-th of the centered integers \{-(n-1)/2, \dots, (n-1)/2\}, computable via for power sums.

Combinatorial Aspects

Intersections

The intersection of two arithmetic progressions of integers, say A = \{ a + n d_1 \mid n \in \mathbb{Z} \} and B = \{ b + m d_2 \mid m \in \mathbb{Z} \}, is either empty or itself an arithmetic progression. This holds because the common terms satisfy the simultaneous congruences x \equiv a \pmod{d_1} and x \equiv b \pmod{d_2}, which form a linear Diophantine system. The intersection is nonempty if and only if \gcd(d_1, d_2) divides a - b. When nonempty, the common terms form an arithmetic progression with common difference d' = \operatorname{lcm}(d_1, d_2) = \frac{d_1 d_2}{\gcd(d_1, d_2)}, starting from some initial term r that satisfies both congruences (solvable via the Chinese Remainder Theorem if \gcd(d_1, d_2) = 1, or more generally by the above condition). For progressions restricted to nonnegative indices (rays), the intersection is infinite if nonempty, as the common difference ensures infinitely many terms beyond the first common one. Consider the arithmetic progression of odd positive integers \{ 2n + [1](/page/1) \mid n = 0, [1](/page/1), 2, \dots \} (common difference 2, starting at ) and the progression of positive multiples of \{ 3m \mid m = [1](/page/1), 2, [3](/page/3), \dots \} (common difference , starting at ). Here, \gcd(2, [3](/page/3)) = [1](/page/1) divides [1](/page/1) - 0 = [1](/page/1) (adjusting the second start to 0 modulo ), so the intersection is nonempty. The common terms are the multiples of : , 9, 15, 21, ..., forming an arithmetic progression with common difference \operatorname{lcm}(2, [3](/page/3)) = 6 and starting at . For another example, take the progressions \{ 5n + 3 \mid n = 0, [1](/page/1), 2, \dots \} and \{ 7m - 2 \mid m = [1](/page/1), 2, [3](/page/3), \dots \} (adjusting indices for positivity). Since \gcd(5, 7) = [1](/page/1) divides $3 - (-2) = 5, the intersection exists and has common difference \operatorname{lcm}(5, 7) = 35, with terms starting at 33: 33, 68, 103, ....

Arithmetic Subsets

In the set \{[1](/page/1), 2, \dots, n\}, an arithmetic subset of length k is a k-term arithmetic progression embedded within it. The total number of such k-term arithmetic progressions is given by the formula \sum_{d=1}^{\left\lfloor \frac{n-1}{k-1} \right\rfloor } \bigl( n - (k-1)d \bigr), where the sum is over possible common differences d \geq 1. This counts, for each fixed d, the number of valid starting terms a \geq 1 such that a + (k-1)d \leq n, which yields n - (k-1)d possibilities when positive. For fixed k, the asymptotic number of k-term arithmetic progressions in \{1, 2, \dots, n\} as n \to \infty is approximately \frac{n^2}{2(k-1)}. This follows from approximating the sum by an or using the involving the function, highlighting the quadratic growth in n. Van der Waerden's theorem states that for any positive integers k and r, there exists a number W(k, r) such that if the integers from 1 to W(k, r) are colored with r colors, at least one color class contains a k-term progression. This guarantees the existence of monochromatic arithmetic subsets in sufficiently large colorings of \{1, 2, \dots, n\}, connecting to the enumeration above by ensuring that no finite coloring avoids them entirely. As a computational example, consider n=10 and k=3. Here, \left\lfloor \frac{9}{2} \right\rfloor = 4, so the sum is (10 - 2 \cdot [1](/page/1)) + (10 - 2 \cdot 2) + (10 - 2 \cdot [3](/page/3)) + (10 - 2 \cdot 4) = 8 + 6 + 4 + 2 = 20. These include progressions like $1,2,[3](/page/3) (for d=1) and $1,6,11 (but truncated to fit, wait no, for d=5: 10-10=0, so up to d=4: e.g., $2,6,10 for d=4). This count illustrates how smaller [n](/page/N+) yields fewer progressions, scaling with the formula.

Historical Development

Ancient Origins

In ancient , during the Old Babylonian period (circa 2000–1600 BCE), arithmetic progressions emerged in cuneiform tablets as tools for solving practical problems, particularly in dividing inheritances where shares increased by constant differences among siblings. For instance, problems described scenarios like ten brothers sharing silver, with each subsequent share exceeding the previous by a fixed amount, solved using methods involving reciprocals and iterative calculations recorded in educational tables. These applications highlight early systematic use of sequential in administrative and economic contexts. Contemporary mathematics, as evidenced in papyri from around 2000 BCE such as the (copied circa 1650 BCE), incorporated sums and proportional calculations essential for and . Problems involved computing areas, volumes, and resource allocations for building projects like granaries and pyramids, often requiring additive sequences to estimate material needs or labor distributions. These practical exercises demonstrate an implicit understanding of arithmetic progressions in tasks. In , Euclid formalized aspects of arithmetic progressions within his Elements (circa 300 BCE), particularly through the theory of proportions in Books V and VII. Here, he defined ratios and equal differences among numbers, treating progressions as cases of continued proportion where terms maintain constant intervals, applied to problems in and . This theoretical framework elevated progressions from mere computation to axiomatic principles. Ancient scholars advanced the study of progressions significantly. Pingala's Chandaḥśāstra (circa 200 BCE) analyzed sequential patterns in poetic meters, introducing recursive methods that bordered on sequences for counting combinations. By 628 , Brahmagupta's Brahmasphutasiddhānta explicitly addressed sums of such progressions, providing formulas for the total of terms in arithmetic series used in astronomical and algebraic computations; this work marked an early recognition of the sum formula in . In the medieval (9th–15th centuries), mathematicians built on earlier traditions, advancing the study of series. For example, Al-Karaji (c. 953–1029) developed methods for summing powers and series, using proof by to establish formulas for sums, including those related to arithmetic progressions, influencing later . In , the Nine Chapters on the Mathematical Art (circa 100 BCE) featured series in chapters on proportions, notably for equitable taxation and resource apportionment. Problems in Chapter 6, "Fair Prescriptions," employed progressive distributions to divide levies among households or fields by constant differences, solving real-world fiscal challenges through tabular methods and iterative proportions.

Modern Contributions

In the late 1780s, as a young student, astounded his teacher by rapidly computing the of the integers from 1 to 100 as 5050, using the pairing method that reveals the closed-form formula S = \frac{n(n+1)}{2} for the of the first n natural numbers, which form an arithmetic progression with common difference 1. This childhood feat highlighted Gauss's intuitive grasp of arithmetic series summation, predating his formal contributions to and foreshadowing the formula's widespread use in . During the 18th and early 19th centuries, Leonhard Euler and advanced the analysis of infinite series, extending concepts from finite arithmetic progressions to divergent and generalized cases. Euler, in particular, assigned formal values to divergent arithmetic series, such as the sum $1 + 2 + 3 + \cdots = -\frac{1}{12}, through methods involving the zeta function, influencing later developments in techniques for non-convergent series. Lagrange contributed to the rigorous treatment of infinite series expansions and formulas applicable to functions evaluated at points in arithmetic progression, bridging finite differences and continuous analysis. Their work laid groundwork for handling series where terms follow arithmetic patterns, even when traditional fails. In the , and initiated a major line of research in 1936 by investigating the largest subsets of \{1, 2, \dots, n\} free of k-term arithmetic progressions, conjecturing that sets with divergent sums of reciprocals must contain arbitrarily long such progressions—a problem that spurred decades of progress in extremal . This was resolved affirmatively by Endre Szemerédi's theorem in 1975, which establishes that any subset of the positive integers with positive upper density contains arithmetic progressions of arbitrary length, providing a cornerstone for additive combinatorics with profound implications for density and structure in number sets. More recently, arithmetic progressions have driven key applications in additive combinatorics, exemplified by the 2004 Green–Tao theorem proving that the primes contain arbitrarily long arithmetic progressions, extending Szemerédi's result to a set of zero density. AP-free sets have applications in , including .