Iverson bracket

In mathematics, the Iverson bracket, named after Kenneth E. Iverson, is a notation that generalises the Kronecker delta. It converts any logical proposition into a number that is 1 if the proposition is satisfied, and 0 otherwise, and is generally written by putting the proposition inside square brackets:

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

In the context of summation, the notation can be used to write any sum as an infinite sum without limits: If $P(k)$ is any property of the integer $k$ ,

\sum _{k}f(k)\,[P(k)]=\sum _{P(k)}f(k).

Note that by this convention, a summand $f(k)[{\textbf {false}}]$ must evaluate to 0 regardless of whether $f(k)$ is defined. Likewise for products:

\prod _{k}f(k)^{[P(k)]}=\prod _{P(k)}f(k).

The notation was originally introduced by Kenneth E. Iverson in his programming language APL,^[1]^[2] though restricted to single relational operators enclosed in parentheses, while the generalisation to arbitrary statements, notational restriction to square brackets, and applications to summation, was advocated by Donald Knuth to avoid ambiguity in parenthesized logical expressions.^[3]

Properties

There is a direct correspondance between arithmetic on Iverson brackets, logic, and set operations. For instance, let A and B be sets and $P(k_{1},\dots )$ any property of integers; then we have

[P\land Q]=[P][Q],\qquad [\neg P]=1-[P].

[k\in A]+[k\in B]=[k\in A\cup B]+[k\in A\cap B].

[\forall m\ .\ P(k,m)]=\prod _{m}[P(k,m)].

[\exists m\ .\ P(k,m)]=\min {\Big (}1,\sum _{m}[P(k,m)]{\Big )}=1-\prod _{m}1-[P(k,m)].

\#{\{m\mid \exists m\ .\ P(k,m)\}}=\sum _{m}[P(k,m)].

Examples

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.

Double-counting rule

We mechanically derive a well-known sum manipulation rule using Iverson brackets:

{\begin{aligned}\sum _{k\in A}f(k)+\sum _{k\in B}f(k)&=\sum _{k}f(k)\,[k\in A]+\sum _{k}f(k)\,[k\in B]\\&=\sum _{k}f(k)\,([k\in A]+[k\in B])\\&=\sum _{k}f(k)\,([k\in A\cup B]+[k\in A\cap B])\\&=\sum _{k\in A\cup B}f(k)\ +\sum _{k\in A\cap B}f(k).\end{aligned}}

Summation interchange

The well-known rule $\textstyle \sum _{j=1}^{n}\,\sum _{k=1}^{j}f(j,k)=\sum _{k=1}^{n}\,\sum _{j=k}^{n}f(j,k)$ is likewise easily derived:

{\begin{aligned}\sum _{j=1}^{n}\,\sum _{k=1}^{j}f(j,k)&=\sum _{j,k}f(j,k)\,[1\leq j\leq n]\,[1\leq k\leq j]\\&=\sum _{j,k}f(j,k)\,[1\leq k\leq j\leq n]\\&=\sum _{j,k}f(j,k)\,[1\leq k\leq n]\,[k\leq j\leq n]\\&=\sum _{k=1}^{n}\,\sum _{j=k}^{n}f(j,k).\end{aligned}}

Counting

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^+.

Simplification of special cases

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])

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]

\operatorname{sgn}(x)=[x>0]-[x<0]

and

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

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\leq x<n+1]

and

\lceil x\rceil =\sum _{n}n\cdot [n-1<x\leq n],

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

The ramp function can be expressed

R(x)=x\cdot [x\geq 0].

The trichotomy of the reals is equivalent to the following identity:

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

The Möbius function has the property (and can be defined by recurrence as^[4])

\sum _{d|n}\mu (d)\ =\ [n=1].

Formulation in terms of usual functions

In the 1830s, Guglielmo Libri Carucci dalla Sommaja used $0^{0^{x}}$ as a replacement for what would now be written $[x>0]$ , as well as variants such as $(1-0^{0^{-x}})(1-0^{0^{x-a}})$ for $[0\leq x\leq a]$ .^[3] Indeed, following the usual conventions, those quantities are equal where defined: $0^{0^{x}}$ is 1 if x > 0, 0 if x = 0, and undefined otherwise.

References

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

This article is issued from Wikipedia - version of the 10/31/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.