Merging

As an extremely basic example, let's say we have 2 $\ell$-variate things $t_0(X_0, \ldots , X_{\ell - 1})$ and $t_1(X_0, \ldots , X_{\ell - 1})$. Equivalently, we have two lists $\left( t_{0, 0}, \ldots , t_{0, 2^\ell - 1} \right)$ and $\left( t_{1, 0}, \ldots , t_{1, 2^\ell - 1} \right)$. What if we want the $\ell + 1$-variate polynomial—say, $t^*(X_0, \ldots , X_\ell)$—associated with the concatenation $\left( t_{0, 0}, \ldots , t_{0, 2^\ell - 1}, t_{1, 0}, \ldots , t_{1, 2^\ell - 1} \right)$? To cut to the chase, we can write down the algebraic expression:

It is a basic exercise that the list representation of this polynomial $t^*(X_0, \ldots , X_\ell)$ indeed gives us the concatenation of the two original lists that we started with.

The final thing to note is that the verifier may evaluate $t^*(r)$ efficiently, for any point $(r_0, \ldots , r_\ell) \in \mathcal{T}_\tau^{\ell + 1}$. How? To do this, the verifier should first query $s_0 \coloneqq t_0(r_0, \ldots , r_{\ell - 1})$ and $s_1 \coloneqq t_1(r_0, \ldots , r_{\ell - 1})$. Finally, the verifier should locally compute the combination $(1 - r_\ell) \cdot s_0 + r_\ell \cdot s_1$ and output it. Indeed, this evidently gives us an evaluation procedure for $t^*$ (entailing two sub-queries to $t_0$ and $t_1$ and a tiny bit of local math).

Finally, there is a geometrical story corresponding to this concatenation operation. As the equation above makes clear, $t^*$, as a polynomial, is defined "piecewise" on the $\ell + 1$-dimensional cube. That is, we let the "bottom" $\ell$-subcube of that cube (i.e., where $X_\ell = 0$) take exactly the values that $t_0$ does, and the "top" $\ell$-subcube (i.e., where $X_\ell = 1$) take exactly the values that $t_1$ does. The resulting piecewise polynomial takes, as its values, the concatenation of the values that $t_0$ and $t_1$ respectively take.

Concatenating

It is not hard to generalize this basic procedure to some power-of-two number $2^\alpha$ of constituent polynomials, instead of just 2. We'll fix $\ell$ again, and consider now $\ell$-variate constituent polynomials $t_0, \ldots , t_{2^\alpha - 1}$. To concatenate all of these things into a single, $2^{\ell + \alpha}$-sized list, we want the composite polynomial:

$t^*(X_0, \ldots , X_{\ell + \alpha - 1}) \coloneqq \sum_{v \in \mathcal{B}_\alpha} t_{\{v\}}(X_0, \ldots , X_{\ell - 1}) \cdot \widetilde{\texttt{eq}}(X_\ell, \ldots , X_{\ell + \alpha - 1}, v_0, \ldots , v_{\alpha - 1})$.

For straightforward reasons, the table of values of $t^*$ over the $\ell + \alpha$-dimensional cube yields exactly the concatenation of the polynomials $t_0, \ldots , t_{2^\alpha - 1}$'s respective individual tables of values. Geometrically, here were are partitioning $\mathcal{B}_{\ell + \alpha}$ into $2^\alpha$ $\ell$-dimensional subcubes, and defining $t^*$ piecewise on $\mathcal{B}_{\ell + \alpha}$ out of the $t_0, \ldots , t_{2^\alpha - 1}$.

The important thing here is that if $2^\alpha$ is small, then this thing is succinct for the verifier. Indeed, to evaluate $t^*$ at some arbitrary point $(r_0, \ldots , r_{\ell + \alpha - 1}) \in \mathcal{T}_\tau^{\ell + \alpha}$, the verifier may first query $s_v \coloneqq t_{\{v\}}(r_0, \ldots , r_{\ell - 1})$, for each $v \in \mathcal{B}_\alpha$. Next, the verifier must simply output the combination $\sum_{v \in \mathcal{B}_\alpha} s_v \cdot \widetilde{\texttt{eq}}(v_0, \ldots , v_{\alpha - 1}, r_\ell, \ldots , r_{\ell + \alpha - 1})$. By a standard algorithm, the verifier may compute the vector $\left( \widetilde{\texttt{eq}}(v_0, \ldots , v_{\alpha - 1}, r_\ell, \ldots , r_{\ell + \alpha - 1}) \right)_{v \in \mathcal{B}_\alpha}$—and hence the entire sum above—in $\Theta(2^\alpha)$ time.

Interleaving

By changing this story very slightly, we can also achieve a dual outcome, whereby we interleave $2^\alpha$ $\ell$-variate polynomials. That is, we construct an $\ell + \alpha$-variate polynomial whose (lexicographically flattened) list of evaluations is exactly the interleaving of the respective lists of $2^\alpha$ constituent polynomials $t_0, \ldots , t_{2^\alpha - 1}$.

To do this, we just need to switch the endianness of our combination operation—that is, we need to combine these polynomials using the low variables as "selectors", instead of the high variables. In other words, we need to use the alternate expression:

This thing is also succinct for the verifier to evaluate (provided $2^\alpha$ is small), for the same reason that the concatenated polynomial was.