BIT predicate

In mathematics and computer science, the BIT predicate, sometimes written ${\text{BIT}}(i,j)$, is a predicate that tests whether the $j$th bit of the number $i$ (starting from the least significant digit) is 1, when $i$ is written as a binary number.

History

The BIT predicate was first introduced in 1937 by Wilhelm Ackermann to define the Ackermann coding, which encodes hereditarily finite sets as natural numbers. The BIT predicate can be used to perform membership tests for the encoded sets: ${\text{BIT}}(i,j)$ is true if and only if the set encoded by $j$ is a member of the set encoded by $i$.

The notation ${\text{BIT}}(i,j)$, and the name "the BIT predicate", come from the work of Ronald Fagin and Neil Immerman, who applied this predicate in computational complexity theory as a way to encode and decode information in the late 1980s and early 1990s.

Description and implementation

In mathematical notation, the BIT predicate can be described as $${\text{BIT}}(i,j)=\lfloor i\mathbin {/} 2^{j}\rfloor {\bmod {2}}$$ where $\lfloor \cdot \rfloor$ is the floor function and mod is the modulo function. It is a primitive recursive function.

In programming languages such as C, C++, Java, or Python that provide a right shift operator >> and a bitwise Boolean and operator &, the BIT predicate ${\text{BIT}}(i,j)$ can be implemented by the expression (i>>j)&1. Here the bits of $i$ are numbered from the low-order bits to high-order bits in the binary representation of $i$, with the ones bit being numbered as bit 0. The subexpression i>>j shifts these bits so that bit $j$ is shifted to position 0, and the subexpression &1 masks off the remaining bits, leaving only the bit in position 0. The value of the expression is 1 or 0, respectively as the value of ${\text{BIT}}(i,j)$ is true or false.

Applications

Set data structures

For a set represented as a bit array, the BIT predicate can be used to test set membership. For instance, subsets of the non-negative integers $\{0,1,\ldots \}$ may be represented by a bit array with a one in position $i$ when $i$ is a member of the subset, and a zero in that position when it is not a member. When such a bit array is interpreted as a binary number, the set $\{i,j,k,\dots \}$ for $i,j,k,\dots$ all distinct is represented as the binary number $2^{i}+2^{j}+2^{k}+\cdots$. If $S$ is a set, represented in this way, and $i$ is a number that may or may not be an element of $S$, then ${\text{BIT}}(S,i)$ returns a nonzero value when $i$ is a member and zero when it is not.

The same technique may be used to test membership in subsets of any sequence $x_{0},x_{1},\dots$ of distinct values, encoded using powers of two whose exponents are the positions of the elements in this sequence, rather than their values. For instance, in the Java collections framework, java.util.EnumSet uses this technique to implement a set data structure for enumerated types. Ackermann's encoding of the hereditarily finite sets is an example of this technique, for the recursively-generated sequence of hereditarily finite sets.

Private information retrieval

In the mathematical study of computer security, the private information retrieval problem can be modeled as one in which a client, communicating with a collection of servers that store a binary number $i$, wishes to determine the result of a BIT predicate ${\text{BIT}}(i,j)$ without divulging the value of $j$ to the servers. Chor et al. (1998) describe a method for replicating $i$ across two servers in such a way that the client can solve the private information retrieval problem using a substantially smaller amount of communication than would be necessary to recover the complete value of $i$.

Complexity and logic

The BIT predicate is often examined in the context of first-order logic, where systems of logic result from adding the BIT predicate to first-order logic. In descriptive complexity, the complexity class FO + BIT resulting from adding the BIT predicate to FO results in a more robust complexity class. The class FO + BIT, of first-order logic with the BIT predicate, is the same as the class FO + PLUS + TIMES, of first-order logic with addition and multiplication predicates.

Construction of the Rado graph

The Rado graph: for instance there is an edge from 0 to 3 because the 0th bit of 3 is non zero.

Ackermann in 1937 and Richard Rado in 1964 used this predicate to construct the infinite Rado graph. In their construction, the vertices of this graph correspond to the non-negative integers, written in binary, and there is an undirected edge from vertex $i$ to vertex $j$, for $i<j$, when ${\text{BIT}}(i,j)$ is nonzero.

The resulting graph has many important properties: it contains every finite undirected graph as an induced subgraph, and any isomorphism of its induced subgraphs can be extended to a symmetry of the whole graph.