The Refinement Polynomial

In this page, we discuss refinement and packing, two dual notions that sit at the center of ring-switching. Indeed, as we've said, we've thus far only committed large-field polynomials. On the other hand, given any large-field polynomial, we can freely decide to view it as a small-field polynomial, merely by refining the boundary points which divide adjacent field elements. The point is to make this formal data-casting operation algebraic, so that we can get an evaluation protocol on the refined thing. An important resource here will be our primer on binary towers.

The Refinement Polynomial

As we've seen, each $\mathcal{T}_\tau$-element concretely looks like a length-$2^\tau$ strings of bits. We're going to pick a refinement factor $\kappa \in \{0, \ldots , \tau\}$. The basic operation is this: if I start with a length-$2^\ell$ list containing $2^\tau$-bit strings, then, by "chopping them up" into $2^\kappa$ substrings a piece, I can cook up a length-$2^{\ell + \kappa}$ list of $2^{\tau - \kappa}$-bit strings.

This is a procedure we just introduced on lists. On the other hand, using the dictionary between lists and multilinears, we can always equally express the procedure in terms of multilinears, too. Thus our input is a multilinear $t(X_0, \ldots , X_{\ell - 1})$ over the huge field $\mathcal{T}_\tau$. By performing the above procedure on $t$'s vector of Lagrange coefficients, we get a further vector. Upon interpreting that vector as the vector of Lagrange coefficients of some further polynomial, we obtain a polynomial $t'(X_0, \ldots, X_{\ell + \kappa - 1})$ over $\mathcal{T}_{\tau - \kappa}$. We call $t'(X_0, \ldots, X_{\ell + \kappa - 1})$ the refinement virtual polynomial.

The Packed Polynomial

We can always reverse this process, in a fairly straightforward way. Indeed, if we start with a polynomial $t(X_0, \ldots, X_{\ell - 1})$ over $\mathcal{T}_\iota$, let's say, we can choose to pack its coefficients. In this side of things, we arrange $t(X_0, \ldots, X_{\ell - 1})$'s vector of Lagrange coefficients into chunks, and concatenate each chunk. In this way, we obtain a polynomial with fewer coefficients, but over a larger field. More precisely, if our chunk size is $2^\kappa$, then the end result will be $t'(X_0, \ldots , X_{\ell - \kappa - 1})$, a polynomial over $\mathcal{T}_{\iota + \kappa}$. The number of variables has gotten smaller, by $\kappa$, while the tower height has increased by $\kappa$.

The Algebraic Meaning

The key fact that underlies everything that comes next is that these packing and refinement operations are algebraic. If we were working in the prime-field setting, it simply would not be algebraically meaningful to slice and dice the bit-representations of field elements in the way that we're doing now. Nor, for that matter, would these operations be meaningful if we used classical binary fields (defined as quotients of univariate polynomial rings).

Binius uses towers of binary fields, binary fields of a special sort. We again fix a pair of tower heights $\mathcal{T}_\iota \subset \mathcal{T}_\tau$. We write $\kappa \coloneqq \tau - \iota$. As is true for any field extension, we can always view $\mathcal{T}_\tau$ as a vector space over its own subfield $\mathcal{T}_\iota$. As we've seen, our tower construction yields a particular natural basis $(\beta_0, \ldots , \beta_{2^\kappa - 1})$ of $\mathcal{T}_\tau$ over $\mathcal{T}_\iota$, called the the multilinear monomial basis. Because of how the recursive bit-representation of $\mathcal{T}_\tau$-elements works, the splitting or refinement operation we just did above in fact effects a basis decomposition with respect to this basis. Similarly, our packing operation is a basis-combination.

Indeed, if we start with a big-field element $\alpha \in \mathcal{T}_\tau$, then, by definition of the basis $\beta_0, \ldots , \beta_{2^\kappa - 1}$, we get a unique sequence of $\mathcal{T}_\iota$-valued coordinates $\alpha_0, \ldots , \alpha_{2^\kappa - 1}$ for which $\alpha = \sum_{i = 0}^{2^\kappa - 1} \alpha_i \cdot \beta_i$ holds. These $\mathcal{T}_\iota$-elements $\alpha_0, \ldots , \alpha_{2^\kappa - 1}$ turn out to be exactly the substrings we just split $\alpha$'s bit representation into. This makes sense when you think about how towers work: the elements $\alpha_0, \ldots , \alpha_{2^\kappa - 1}$ are the coefficients corresponding respectively to the monomials $1, \ldots , X_\iota \cdot \cdots \cdot X_{\tau - 1}$, in $\alpha$'s multilinear polynomial representation. When we write $\alpha$ in bits, we end up concatenating these coefficients.

In our next topic—the tensor algebra—we will constantly use these splitting and joining operations. In fact, we will view $\mathcal{T}_\tau$-elements $\alpha$ and $2^\kappa$-tuples of $\mathcal{T}_\iota$-elements like $(\alpha_0, \ldots , \alpha_{2^\kappa - 1})$ as "the same thing".