0
$\begingroup$

Let $n$ be a large positive integer. Given a collection $\mathfrak S$ of subsets of $[n] := \{1,2,\ldots,n\}$, and a vector $z=(z_1,\ldots,z_n)\in \{\pm 1\}^n$, define $$ f_{\mathfrak S}(z) := \sum_{\sigma \in \mathfrak S} z_\sigma, $$ where $z_\sigma := \prod_{j \in \sigma} z_j$. For any $j \in [n]$, let $d_{\mathfrak S}(j) = |\partial_j \mathfrak S|$ be "degree" of $j$ w.r.t $\mathfrak S$, where $$ \partial_j \mathfrak S := \{\sigma\setminus\{j\} \mid \sigma \in \mathfrak S, \,j \in \sigma\} = \{s \subseteq [n] \mid j \not \in s\text{ and }s \cup \{j\} \in \mathfrak S\}. $$ Also define the minimal degree w.r.t $\mathfrak S$ as $d^\star_{\mathfrak S} := \min_{j \in [n]} d_{\mathfrak S}(j)$.

Examples

  • Pairs. If $\mathfrak S$ is the collection of distinct unordered pairs (i.e doubletons) of elements of $[n]$, then it is easy to see that $\partial_j \mathfrak S$ is the collection of all singletons of $[n]$ except $\{j\}$, and so $d_{\mathfrak S}^\star = n-1$ for all $j \in [n]$.

  • Simplicial Complex. On the other hand, if $\mathfrak S$ is a simplicial complex, then $\partial_j S$ is the collection of elements of $\mathfrak S$ which don't contain $j$. For example, if $\mathfrak S = K_{n,d}$ is the collection of all subsets of $[n]$ with $d$ or fewer elements (where $d \in [n]$), then $\partial_j \mathfrak S$ is isomorphic to $K_{n-1,d-1}$, and so $$ d_{\mathfrak S}^\star = |K_{n-1,d-1}| = \sum_{i=0}^{d-1} {n-1 \choose i}. $$

  • Monster. Finally, if $1 \le k \le n$, and $G_1,\ldots,G_k$ is a partition of $[n]$, and $\mathfrak S$ is the collection of subsets of $[n]$ which contain exactly one element from each $G_i$, then $d_{\mathfrak S}^\star = p^{k-1}$, where $p := n/k$.

Let us say that $\mathfrak S$ is "nice" if the following three conditions are satisfied:

  • (1) Exponential Degree: $d_{\mathfrak S}^\star \ge 2^{\alpha n}$ for some constant $\alpha \in (0, 1]$.
  • (2) Efficiency: $f_{\mathfrak S}(z)$ can be computed in linear time time $O(n)$, for any $z \in \{\pm 1\}^n$.
  • (3) Invariance: $f_{\mathfrak S}(\overline z) = f_{\mathfrak S}(z)$ for any $z,\overline z \in \{\pm 1\}^n$ such that the components of $\overline z$ are a permutation of the components of $z$.

It is clear that the "pairs" example verifies the conditions (2) and (3), but not (1). The "simplicial complex" example verifies conditions (1 and 3) or (2 and 3). This is because thanks to https://cstheory.stackexchange.com/a/52570/44644, $f_{\mathfrak S}$ can be computed in time of order $O(nd)$; if the time complexity is really $\Theta(nd)$ (see Question 2 below), then it can be linear is if $d=O(1)$, which forces $d_{\mathfrak S}^\star$ to be of polynomial order $n^{d-1}$.

Finally, still thanks to the previous reference, for appropriate choice of $k$ (for example assume WLOG that $n$ is even, and take $k=n/2$) the "monster" example verifies conditions (1) and (2), but not (3). Condition (1) is clear to see. For condition (2), simply note that by construction $f_{\mathfrak S}(z) := \sum_{\sigma \in \mathfrak S} z_\sigma = \sum_{i=1}^k \prod_{j \in G_i} z_j$, which definitely takes $O(n)$ time to compute. Condition (3) fails because every partitioning of $[n]$ induces a partial order on $[n]$, and so $f_{\mathfrak S}(\overline z)$ will be different from $f_{\mathfrak S}(z)$ in general.

Question 1

What is an explicit construction of a "nice" $\mathfrak S$ ?

N.B: I'm fine with randomized constructions, which verify the above 3 conditions in an appropriate probabilistic sense.

Question 2

Is $\mathfrak S = K_{n,d}$ efficient ?

$\endgroup$
4
  • $\begingroup$ Why not just take $\mathfrak{S}$ to be the set of all subsets of $[n]$ -- isn't it exponential degree, efficient (actually, basically trivial) to compute, and permutation-invariant, or am I missing something? In fact, why does taking $\mathfrak{S} = K_{n,d}$ necessarily take time $\Omega(nd)$ -- it seems to me that you should be able to do it in time $O(d)$ in general (up to some polylog factors in $n$ if you're caring about bit complexity and cost of arithmetic operations). $\endgroup$ Commented Mar 16, 2023 at 1:06
  • $\begingroup$ The following claimed identity seems incorrect: $$\{\sigma\setminus\{j\} \mid \sigma \in \mathfrak S\} = \{s \subseteq [n] \mid j \not \in s\text{ and }s \cup \{j\} \in \mathfrak S\}$$ E.g. what if $\mathfrak S$ contains no sets that contain $j$? Then the left-hand side is $\mathfrak S$, but the right-hand side is empty. $\endgroup$
    – Neal Young
    Commented Mar 16, 2023 at 17:20
  • $\begingroup$ @NealYoung There's typo in LHS. Fixed. $\endgroup$
    – dohmatob
    Commented Mar 16, 2023 at 19:59
  • $\begingroup$ @JasonGaitonde I've added some clarifications about the case of $K_{n,d}$. Indeed, it is only known to be computable in time $O(nd)$, but there might be faster ways as said. Concerning $K_{n,d}$ and $\{0,1\}^n$, It'd be interested in hearing the details of what you have in mind. Thanks. $\endgroup$
    – dohmatob
    Commented Mar 16, 2023 at 21:26

1 Answer 1

1
$\begingroup$

Here's an elaboration on my comment, assuming I didn't get lost in all the notation above:

For $\mathfrak{S}=\mathcal{P}([n])$, the power set of $[n]$, it holds that \begin{equation*} f_{\mathfrak{S}}(z) = \sum_{S\subseteq [n]} z^S = 2^n\prod_{i=1}^n \left(\frac{1+z_i}{2}\right), \end{equation*} which implies that $f_{\mathfrak{S}}(z)$ is $2^n$ if $z_i=1$ for all $i\in [n]$ and otherwise is zero. As best I can tell, this example trivially satisfies all the criteria above.

The case of $\mathfrak{S}=K_{n,d}$ is slightly trickier, but it can be computed using $O(d)$ arithmetic operations (which seemed to be the measure in the other link as well); in particular, this is without considering the time it takes to read and store large numbers (which seems to be the case in the linked answer as well, so hopefully this is okay). If $z$ has $k$ entries with $-1$, we may assume the first $k$ entries are $-1$ and the rest are $+1$ by invariance. Then looking at each monomial separately, we find \begin{equation*} f_{K_{n,d}}(z) = A_{n,d,k,\mathsf{even}}-A_{n,d,k,\mathsf{odd}} \end{equation*} where $A_{n,d,k,\mathsf{even}}$ is the number of subsets of $[n]$ of size at most $d$ with even intersection with $\{1,\ldots,k\}$ and analogously for $A_{n,d,k,\mathsf{odd}}$.

To calculate $A_{n,d,k,\mathsf{even}}$, standard combinatorics implies this is just \begin{equation} \label{eq:even} A_{n,d,k,\mathsf{even}} = \sum_{j=0, \text{$j$ even}}^d {k \choose j}\left(\sum_{\ell=0}^{d-j} {n-k \choose \ell}\right) = \sum_{j=0, \text{$j$ even}}^d {k \choose j} S_{n,k,d-j}, \end{equation} where \begin{equation*} S_{n,k,r}\triangleq \sum_{\ell=0}^{r} {n-k \choose \ell}. \end{equation*} The key now is to calculate the $S_{n,k,r}$ using few arithmetic operations by being careful. The key is using the recurrences \begin{equation*} {m \choose i} = {m \choose i-1}\cdot \frac{m-i+1}{i}, \end{equation*} one can compute all ${n-k \choose 0},\ldots, {n-k \choose d}$ using $O(d)$ arithmetic operations total. Then, using the recurrence \begin{equation*} S_{n,k,r+1} = S_{n,k,r} + {n-k \choose r+1}, \end{equation*} one can compute each of the $S_{n,k,0},\ldots,S_{n,k,d}$ using $O(d)$ more arithmetic operations. After similarly computing all of ${k \choose 0}, \ldots, {k \choose d}$ using $O(d)$ arithmetic operations, the identity for $A_{n,d,k,\mathsf{even}}$ requires $O(d)$ more arithmetic operations given what has already been calculated. The same thing can be done for $A_{n,d,k,\mathsf{odd}}$. Of course, if one cares about time, it takes $O(n)$ to count the number of $-1$ entries, and if you're concerned about bit complexities, which should all be like $O(d\log n)$, you'll probably get something like $n+\tilde{O}(d^2\log n)$ for total time complexity using fancy multiplication algorithms.

$\endgroup$
2
  • $\begingroup$ Thanks for the detailed response. Indeed, the power set of $[n]$ fits the bill in my question as it stands. BTW, we agree that $A_{n,d,k,odd} = |K_{n,d}| - A_{n,d,k,even}$, and so there is not need to play a similar game for the odd case, right ? $\endgroup$
    – dohmatob
    Commented Mar 17, 2023 at 13:53
  • $\begingroup$ @dohmatob yes, that's right. But computing $\vert K_{n,d}\vert$ will also take up another $O(d)$ operations as well. $\endgroup$ Commented Mar 19, 2023 at 17:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.