The Setting
A reference tour follows a computation on a tape cut into blocks: a controller of bits visits one block at a time. Fix a positive integer and group the visits into epochs of visits, and each epoch into rounds of visits. For every epoch, record the content of each block at its start and, for , the controllers met from its start to the end of round . These records are the vertices of a circuit, and each depends on earlier ones: a block’s content on its content one epoch before, a history on the history one round shorter and on the blocks.
The item is about writing each of these dependencies in one algebraic shape over a prime field : a coordinate of a vertex’s value, written as a bit vector, as a sum over guesses of products of local checks, one check for each child of the vertex.
Dependency Circuits
A dependency circuit of width with children per node has finitely many nodes, numbered from , a flag marking its base nodes, and at each node a head child , children for , a number of guess bits, a first value and a semantic value .✦ The local rules of a dependency circuit are a proposal and an allowance test , each a natural number for every node , coordinate , guess , child index , value of the head child and value of a child; the guesses at are the numbers .
The coefficient field of a dependency circuit is the prime field , where is the largest prime with and is the outer degree of ; and are read in , and vectors over are sequences indexed by the natural numbers✦. The augmented vector of a number at width is the vector over with coordinates (1)✦
A dependency circuit is good when every node has and , every base node has , and every other node obeys the identity rule: for every coordinate , (2)✦
Reference Tours
A reference tour consists of a positive integer , a controller width , a positive number of blocks, an initial controller , an initial content of every block , a selection naming for each controller the block it reads and rewrites, and a visit map sending a controller and the content of that block to the next controller and the block’s new content.✦ The controller radix of a reference tour is ; has digits per block, guess length and width , the number of bits in controllers, at which all its augmented coordinates are taken.
A reference tour has finite word bounds when its controllers are words below and its block contents words below : , every , and the visit map sends a controller below and a content below to a controller below and a content below .✦
The story of is its sequence of scenes , each a controller with the contents of all blocks; it starts from and and passes from to by one visit.✦ The controller history from visit over steps packs the controllers in base , least significant first: (3)✦
The circuit of has the vertices , and the epoch and the column of are the quotient and the remainder of divided by the stride . In epoch , column holds the array vertex , column the start vertex , and column , for , the history vertex of round ; the round index of a vertex is its column minus , or at columns up to ✦. Values are read off the story at visit : (4)✦
The header of a vertex of epoch is when is an array vertex or the start vertex, and when with .✦ The children of a vertex of epoch , for , are all when , all equal to the header when , and when with .✦ A vertex has guess bits at columns up to and beyond.✦ The first value of a vertex is at a column and at the others.✦ The base vertices of are the vertices of epoch at columns up to .✦
Offers and Validity Checks
The round proposal at a history vertex of round , for a header value and a guess , is the number whose lowest digits in base are those of and whose higher digits are those of : (5)✦
Write for the digit of at place in base .✦ The offer at a vertex of epoch , in coordinate , for a guess and a header value , is (6)✦
The replay of block under a transcript , a number read digit by digit in base , from a content is the sequence of pairs of a block content and a verdict, true or false, read as or : it starts from , and its term is obtained from its term by one replay step of block in the visit map of , taken at digit of , which updates the content and the verdict according to the visit map and that digit.✦
The validity check at a vertex of epoch , in coordinate , for a guess , a child , a header value and a child value , is (7)✦
The tour circuit is the dependency circuit whose nodes are the vertices of , of the width of with children per node, with the base vertices, headers, children, guess bits, first values and values of , the offer as proposal and the validity check as allowance test.✦ The required identity at a vertex and a coordinate is the identity (2) of at and .✦
The Claim
Theorem 1. Let be a reference tour and any coordinate; the identities below are in the coefficient field of .
For every epoch and every , the required identity holds at the history vertex : with , (8)✦
For every with and every block , the required identity holds at the array vertex : (9)✦
For every with , the required identity holds at the start vertex : (10)✦
If has finite word bounds, then (11)✦
In the paper, the result reads: for , each round update is a factored rule of the paper’s Lemma 5, with distinguished child , the array vertices of epoch as its other children and guess length .
What Is Checked
The claim is stated over a reference tour with its story, controller histories (3) and block replays, the vertices of its circuit with their values (4), headers and children, the round proposal (5), the offer (6), the validity check (7), the required identity of the tour circuit over and the notion of a good dependency circuit, with finite word bounds on as the hypothesis of its last part.