The Setting
An ordered occurrence of a binary anchor matches its zeros as well as its ones, with independently increasing row and column selections. In the host considered here, those selections may range over anchor positions, tree variables and dummy positions.
Write . The anchor is the binary matrix on defined in (2); its binary digit function is given by (1) for nonnegative integers . (1)✦ (2)✦
Fix a nonnegative height . Put , and .✦ The mode set , variable set and host position set are the finite sets in (3), where is a disjoint copy of . An anchor position has mode , group and offset . (3)
For a variable , its depth , positive sign and tree node index are defined by (4). For a depth and a sign , the signed level class is the subset of specified in (5); the signs have distinct internal classes and share the leaf class. (4) (5)✦
A mode has type and level . The row roles and column roles of a mode are the subsets of given in (6). Here , and . The parity subclass is the subset of the signed level class whose variables have node index of parity . (6)
Write for and for . The variable matrix is the binary matrix on defined by (7). (7)✦
The raw host is the binary matrix on specified by (8), with . (8)✦
The Two Orders
An anchor frame on ordered mode, variable and offset sets is the disjoint union .✦ Its anchor coordinates are ordered lexicographically by mode, group and offset.✦ The row coordinate map places these triples first, followed by the variable coordinates and then dummy offsets✦; the column coordinate map places the dummy offsets before the variable coordinates.✦ The frame’s row and column orders compare the respective coordinates.
The variable row and column orders use tree traversal coordinates in with lexicographic order. For depth , remaining height , block width , node , class and offset , the entry and exit keys and , and the leaf key , are the tuples in (9). (9)
The traversal key of a variable for axis selector is the tuple defined by (10), where , , and . The variable position order compares these keys, with for rows and for columns.✦ (10)✦
The host row order is the frame row order using the variable row order✦; the host column order uses the variable column order.✦
The row enumeration and column enumeration are the increasing bijections for their respective host orders. Write for the host matrix with these row and column enumerations. An ordered copy of consists of maps such that and are strictly increasing and for every .
An anchor copy is pinned if its selected positions are on rows and on columns for one mode and offsets . For a nonnegative integer and bijections , write when every copy of whose row selections increase under and whose column selections increase under is pinned.✦
The Claim
Theorem 1. Let , and let select an ordered copy of in . There are a mode and functions satisfying (11): (11)✦ (12)✦
In the paper, the result reads: every ordered copy of in uses the row and column anchor groups of a single mode , with exactly one position from each of its groups on each axis, in their prescribed order.
What Is Checked
The assertions (11) and (12) are stated for the raw host on , with its separately ordered and enumerated rows and columns and entrywise copies of the anchor .
The host position count is (13), and the traversal keys distinguish variable positions on each axis as in (14). (13)✦ (14)✦