The Shift Indicators

In this sub-area, we prepare a key technical building block that we'll use throughout Binius64. How do we algebraically represent logical and arithmetic bitshifts?

We break our treatment of this problem into a number of steps.

• Shifted Witness Polynomials. How does the multilinear extension of bitshifted data relate to the multilinear extension of the original raw data? This problem is key for us, and also interesting; in this section, we set things up.
• Logical Shifts. We begin by constructing our logical shift indicator. Actually, most of the work will come from constructing $\mathsf{srl}$.
• Arithmetic Shifts. Now, the problem is to construct a shift indicator for arithmetic shift right, which "drags" or "fills" the sign bit rightwards as it goes. We show how this can be done, bootstrapping minimally off of logical shift right.