A cross term is a product of two distinct Lagrange interpolant functions, written l_i(x)l_j(x) with i ≠ j. It appears when the QAP left and right function sums are multiplied: squared interpolant terms are assigned to output functions, while products between different interpolants must be collected separately. section 19.3
For roots r_0 through r_{n-1}, define t(x) as the product of all (x-r_k), and let p_i be the denominator product for l_i(x). A cross term can then be factored into t(x), two denominator factors, and a product over every root except r_i and r_j. This form turns a large rational-looking product into polynomial coefficients suitable for computation. section 19.3
Equation 19.9
\[l_i(x)l_j(x)=\dfrac{t(x)}{p_i p_j} \prod_{\substack{k=0\\k\neq i, j}}^{n-1} x-r_k \label{zq9}\]Use the general factored form to derive coefficients for any distinct pair l_i(x)l_j(x). section 19.3
The combined cross terms supply the h(x)t(x) portion of the QAP identity. When wire values a_j satisfy the QAP, their cross-term coefficients and the separately handled squared terms make the identity hold; invalid values do not. section 19.3
To precompute cross terms for a QAP with n gates:
- Enumerate each unordered pair of distinct indices (i,j). There are n(n−1)/2 such pairs. section 19.3 section 19.5.1
- Expand each l_i(x)l_j(x) into n−1 coefficients, using the two interpolant denominators rather than one. section 19.5.1
- Store every coefficient row in a table, then multiply each row by its h(x) cross-term coefficient and sum by polynomial position. section 19.5.1
- Release the allocated table after use; the table-building routine allocates its own storage. section 19.5.1
Five-gate QAP
Five gates produce 5×4/2 = 10 cross terms: l_0l_1, l_0l_2, and so on through l_3l_4. One coefficient is attached to each pair from wire values; for example, the l_0l_1 coefficient is a_1a_2 + a_0a_3. The coefficient vector is multiplied against the precomputed cross-term table to obtain the coefficients of h(x). section 19.3 section 19.5.4
Cross terms grow quadratically in the number of gates: 20,000 gates yield about 200 million pairs. Precomputation is therefore a substantial implementation concern, although it is needed only once per QAP; proof construction later computes the pair coefficients from the wire vector and uses them to form proof data. section 19.3 section 19.5.1 section 19.5.4
