Iverson bracket

In mathematics, the Iverson bracket, named after Kenneth E. Iverson, is a notation that denotes a number that is 1 if the condition in square brackets is satisfied, and 0 otherwise. More exactly,

$[P] = \begin{cases} 1 & \text{if } P \text{ is true;} \\ 0 & \text{otherwise.} \end{cases}$

where P is a statement that can be true or false. This notation was introduced by Kenneth E. Iverson in his programming language APL,^[1][2] while the specific restriction to square brackets was advocated by Donald Knuth to avoid ambiguity in parenthesized logical expressions.^[3]

Uses

The Iverson bracket converts a Boolean value to an integer value through the natural map $\textbf{false}\mapsto 0; \textbf{true}\mapsto1$, which allows counting to be represented as summation. For instance, the Euler phi function that counts the number of positive integers up to n which are coprime to n can be expressed by

$\phi(n)=\sum_{i=1}^{n}[\gcd(i,n)=1],\qquad\text{for }n\in\mathbb N^+.$

More generally the notation allows moving boundary conditions of summations (or integrals) as a separate factor into the summand, freeing up space around the summation operator, but more importantly allowing it to be manipulated algebraically. For example,

$\sum_{1\le i \le 10} i^2 = \sum_{i} i^2[1 \le i \le 10].$

In the first sum, the index i is limited to be in the range 1 to 10. In the second sum, i is allowed to range over all integers, but the summand is 0 if i is strictly less than 1 or strictly greater than 10, so these terms contribute nothing to the sum. Such use of the Iverson bracket can permit easier manipulation of these expressions.

Another use of the Iverson bracket is to simplify equations with special cases. For example, the formula

$\sum_{1\le k\le n \atop \gcd(k,n)=1}\!\!k = \frac{1}{2}n\varphi(n)$

is valid for n > 1 but is off by 1/2 for n = 1. To get an identity valid for all positive integers n (i.e., all values for which $\phi(n)$ is defined), a correction term involving the Iverson bracket may be added:

$\sum_{1\le k\le n \atop \gcd(k,n)=1}\!\!k = \frac{1}{2}n(\varphi(n)+[n=1])$

Expressing common functions

Many common functions, especially those with a natural piecewise definition, may be expressed in terms of the Iverson bracket. The Kronecker delta notation is a specific case of Iverson notation when the condition is equality. That is,

$\delta_{ij} = [i=j].$

The indicator function, often denoted $\mathbf{1}_A(x)$, $\mathbf{I}_A(x)$ or $\chi_A(x)$, is an Iverson bracket with set membership as its condition:

$\mathbf{I}_A(x) = [x\in A]$.

The Heaviside step function, sign function,^[1] and absolute value function and are also easily expressed in this notation:

$H(x) = [x > 0]$,

$\sgn(x) = [x > 0] - [x < 0]$,

and

$\begin{align} |x| &= x[x>0]-x[x<0] \\ &= x([x>0]-[x<0]) \\ &= x\cdot\sgn(x).\end{align}$

The comparison functions max and min (returning the larger or smaller of two arguments) may be written as

$\max(x,y) = x[x>y]+y[x\leq y]$ and

$\min(x,y) = x[x\leq y]+y[x> y]$.

The floor and ceiling functions can be expressed as

$\lfloor x \rfloor = \sum_{n} n\cdot [n \le x < n+1]$

and

$\lceil x \rceil = \sum_{n} n\cdot [n-1 < x \le n],$

where the index $n$ of summation is understood to range over all the integers.

The ramp function can be expressed

$\{x\} = x\cdot[x\geq 0].$

Finally, the trichotomy of the reals is equivalent to the following identity:

$[a < b] + [a = b] + [a > b] = 1.$

References

1. Kenneth E. Iverson (1962). A Programming Language. Wiley. p. 11. Retrieved 7 April 2016.
2. Ronald Graham, Donald Knuth, and Oren Patashnik. Concrete Mathematics, Section 2.2: Sums and Recurrences.
3. Donald Knuth, "Two Notes on Notation", American Mathematical Monthly, Volume 99, Number 5, May 1992, pp. 403–422. (TeX, arXiv:math/9205211).