title: Boolean convolution using integer multiplication
body: <p>In algorithms presented in <a href="https://arxiv.org/abs/1610.04712" rel="nofollow noreferrer">Bringmann16</a> article a <em>Boolean convolution</em> is suggested to use to get sumset for two sets of positive integers.</p>
  
  <p>In above work both sets are represented as bitmasks - <a href="https://en.wikipedia.org/wiki/Indicator_vector" rel="nofollow noreferrer">indicator vectors</a>. If represent them as polynomials in form <code>1 + bit(0) * x + bit(1) * x^2 + ... + bit(i) * x^(i + 1) + ... + bit(n - 1) * x^n</code>, then indeed their product contains only those monomials, whose power is number either in first set, or in second set or in sumset. The coefficients of product does not matter for subset sum problem. Their values just indicate how many ways to get the number (degree of corresponding monomial) as a sum of elements from first and second set or maybe 0. Value of any coefficient limited by greater size of both sets (<code>s</code>).</p>
  
  <p>To convert the problem of polynomials multiplication to problem of big integers (indicator vectors) multiplication there is need to append <code>log(s)</code> zero bits after each bit of indicator vector. If bits <code>(log(s) + 1) * i ... (log(s) + 1) * (i + 1) - 1</code> are not all clear in product bitset, then corresponding sum=<code>i</code> is realizable.</p>
  
  <p>For big int multiplication algorithms (Karatsuba-like or FFT-based) it gives extra logarithmic factor to problem size. I want to eliminate logarithmic padding.</p>
  
  <p>I think it feasible if I use simple textbook <code>ijk</code> algorithm to multiply two integers. I just need to use logical <em>OR</em> instead of <em>ADD</em> for summation. But this algorithm has quadratic runtime complexity.</p>
  
  <p>Is it possible to replace summation with ORing in case of FFT-based algorithms, like <a href="https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm" rel="nofollow noreferrer">Schönhage–Strassen algorithm</a>?</p>