Let $n$ be an integer. Let there be $n$ integer weights $w_1,w_2,\ldots,w_n$. Let there be a large field $\mathbb{F}$. We can assume that $n\ll|\mathbb{F}|$ and $\sum_{i\in {1,2,\ldots,n}} w_i \ll |\mathbb{F}|$ .

Are there algorithms that on input $n$ and the weights, outputs $n$ different sets $S_1,S_2,...,S_n$, and $n^2$ field elements $k_{i,j}\ne 0$ for $i,j={1,2,\ldots,n}$ that satisfy the following constraints.

  1. $S_i\subseteq \mathbb{F}$ and $|S_i|=w_i$, i.e., $S_i$ consists of $w_i$ elements.
  2. The sets are disjoint.
  3. For all pair of sets $(S_i,S_j)$, for any given $a\in S_i$, $\prod_{b\in S_j} (a-b)=k_{i,j}$ for some non-zero $k_{i,j}$.

Any pointers to where to look for such an algorithm will be really helpful. Thank you!

  • 1
    $\begingroup$ Are you given $k_{i,j}$ or simply requiring that it be non zero? $\endgroup$
    – Carlyle
    Commented Jul 15, 2023 at 9:52
  • $\begingroup$ $k_{i,j}$ can be arbitrary non-zero values output by the algorithm. I updated the question to include this information. $\endgroup$
    – sourav
    Commented Jul 15, 2023 at 16:21


Browse other questions tagged .