Function kimchi_msm::logup::combine_lookups

pub fn combine_lookups<F: PrimeField, ID: LookupTableID>(
    column: Column,
    lookups: Vec<Logup<E<F>, ID>>
) -> E<F>

Compute the following constraint:

                    lhs
   |------------------------------------------|
   |                           denominators   |
   |                         /--------------\ |
column * (\prod_{i = 0}^{N} (β + f_{i}(X))) =
\sum_{i = 0}^{N} m_{i} * \prod_{j = 1, j \neq i}^{N} (β + f_{j}(X))
   |             |--------------------------------------------------|
   |                             Inner part of rhs                  |
   |                                                                |
   |                                                               /
    \                                                             /
     \                                                           /
      \---------------------------------------------------------/
                          rhs

It is because h(X) (column) is defined as:

        n      m_i(X)        n         1            m_0(ω^j)
h(X) =  ∑    ----------  =   ∑   ------------  -  -----------
       i=0   β + f_i(X)     i=1  β + f_i(ω^j)      β + t(ω^j)

The first form is generic, the second is concrete with f_0 = t; m_0 = m; m_i = 1 for ≠ 1. We will be thinking in the generic form.

For instance, if N = 2, we have

h(X) = m_1(X) / (β + f_1(X)) + m_2(X) / (β + f_{2}(X))

       m_1(X) * (β + f_2(X)) + m_2(X) * (β + f_{1}(X))
     = ----------------------------------------------
                 (β + f_2(X)) * (β + f_1(X))

which is equivalent to

h(X) * (β + f_2(X)) * (β + f_1(X)) = m_1(X) * (β + f_2(X)) + m_2(X) * (β + f_{1}(X))

When we have f_1(X) a looked-up value, t(X) a fixed table and m_2(X) being the multiplicities, we have

h(X) * (β + t(X)) * (β + f(X)) = (β + t(X)) + m(X) * (β + f(X))