<p>Here's an elaboration on my comment, assuming I didn't get lost in all the notation above:</p>
<p>For <span class="math-container">$\mathfrak{S}=\mathcal{P}([n])$</span>, the power set of <span class="math-container">$[n]$</span>, it holds that
<span class="math-container">\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*}</span>
which implies that <span class="math-container">$f_{\mathfrak{S}}(z)$</span> is <span class="math-container">$2^n$</span> if <span class="math-container">$z_i=1$</span> for all <span class="math-container">$i\in [n]$</span> and otherwise is zero. As best I can tell, this example trivially satisfies all the criteria above.</p>
<p>The case of <span class="math-container">$\mathfrak{S}=K_{n,d}$</span> is slightly trickier, but it can be computed using <span class="math-container">$O(d)$</span> arithmetic operations (which seemed to be the measure in the other link as well); in particular, this is <em>without considering the time it takes to read and store large numbers</em> (which seems to be the case in the linked answer as well, so hopefully this is okay). If <span class="math-container">$z$</span> has <span class="math-container">$k$</span> entries with <span class="math-container">$-1$</span>, we may assume the first <span class="math-container">$k$</span> entries are <span class="math-container">$-1$</span> and the rest are <span class="math-container">$+1$</span> by invariance. Then looking at each monomial separately, we find
<span class="math-container">\begin{equation*}
f_{K_{n,d}}(z) = A_{n,d,k,\mathsf{even}}-A_{n,d,k,\mathsf{odd}}
\end{equation*}</span>
where <span class="math-container">$A_{n,d,k,\mathsf{even}}$</span> is the number of subsets of <span class="math-container">$[n]$</span> of size at most <span class="math-container">$d$</span> with even intersection with <span class="math-container">$\{1,\ldots,k\}$</span> and analogously for <span class="math-container">$A_{n,d,k,\mathsf{odd}}$</span>.</p>
<p>To calculate <span class="math-container">$A_{n,d,k,\mathsf{even}}$</span>, standard combinatorics implies this is just
<span class="math-container">\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}</span>
where
<span class="math-container">\begin{equation*}
S_{n,k,r}\triangleq \sum_{\ell=0}^{r} {n-k \choose \ell}.
\end{equation*}</span>
The key now is to calculate the <span class="math-container">$S_{n,k,r}$</span> using few arithmetic operations by being careful. The key is using the recurrences
<span class="math-container">\begin{equation*}
{m \choose i} = {m \choose i-1}\cdot \frac{m-i+1}{i},
\end{equation*}</span>
one can compute all <span class="math-container">${n-k \choose 0},\ldots, {n-k \choose d}$</span> using <span class="math-container">$O(d)$</span> arithmetic operations total. Then, using the recurrence
<span class="math-container">\begin{equation*}
S_{n,k,r+1} = S_{n,k,r} + {n-k \choose r+1},
\end{equation*}</span>
one can compute each of the <span class="math-container">$S_{n,k,0},\ldots,S_{n,k,d}$</span> using <span class="math-container">$O(d)$</span> more arithmetic operations. After similarly computing all of <span class="math-container">${k \choose 0}, \ldots, {k \choose d}$</span> using <span class="math-container">$O(d)$</span> arithmetic operations, the identity for <span class="math-container">$A_{n,d,k,\mathsf{even}}$</span> requires <span class="math-container">$O(d)$</span> more arithmetic operations given what has already been calculated. The same thing can be done for <span class="math-container">$A_{n,d,k,\mathsf{odd}}$</span>. Of course, if one cares about time, it takes <span class="math-container">$O(n)$</span> to count the number of <span class="math-container">$-1$</span> entries, and if you're concerned about bit complexities, which should all be like <span class="math-container">$O(d\log n)$</span>, you'll probably get something like <span class="math-container">$n+\tilde{O}(d^2\log n)$</span> for total time complexity using fancy multiplication algorithms.</p>

CC BY-SA 4.0
2023-03-17T13:53:05.727Z
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 ?
dohmatob
CC BY-SA 4.0
2023-03-19T17:47:17.957Z
@dohmatob yes, that's right. But computing $\vert K_{n,d}\vert$ will also take up another $O(d)$ operations as well.
Jason Gaitonde
CC BY-SA 4.0
2023-03-16T23:48:23.403Z
2023-03-16T23:48:23.403Z
Jason Gaitonde
<p>Let <span class="math-container">$n$</span> be a large positive integer. Given a collection <span class="math-container">$\mathfrak S$</span> of subsets of <span class="math-container">$[n] := \{1,2,\ldots,n\}$</span>, and a vector <span class="math-container">$z=(z_1,\ldots,z_n)\in \{\pm 1\}^n$</span>, define
<span class="math-container">$$
f_{\mathfrak S}(z) := \sum_{\sigma \in \mathfrak S} z_\sigma,
$$</span>
where <span class="math-container">$z_\sigma := \prod_{j \in \sigma} z_j$</span>. For any <span class="math-container">$j \in [n]$</span>, let <span class="math-container">$d_{\mathfrak S}(j) = |\partial_j \mathfrak S|$</span> be &quot;degree&quot; of <span class="math-container">$j$</span> w.r.t <span class="math-container">$\mathfrak S$</span>, where
<span class="math-container">$$
\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\}.
$$</span>
Also define the minimal degree w.r.t <span class="math-container">$\mathfrak S$</span> as <span class="math-container">$d^\star_{\mathfrak S} := \min_{j \in [n]} d_{\mathfrak S}(j)$</span>.</p>
<h2>Examples</h2>
<ul>
<li><p><strong>Pairs.</strong> If <span class="math-container">$\mathfrak S$</span> is the collection of distinct unordered pairs (i.e doubletons) of elements of <span class="math-container">$[n]$</span>, then it is easy to see that <span class="math-container">$\partial_j \mathfrak S$</span> is the collection of all singletons of <span class="math-container">$[n]$</span> except <span class="math-container">$\{j\}$</span>, and so <span class="math-container">$d_{\mathfrak S}^\star = n-1$</span> for all <span class="math-container">$j \in [n]$</span>.</p>
</li>
<li><p><strong>Simplicial Complex.</strong> On the other hand, if <span class="math-container">$\mathfrak S$</span> is a simplicial complex, then <span class="math-container">$\partial_j S$</span> is the collection of elements of <span class="math-container">$\mathfrak S$</span> which don't contain <span class="math-container">$j$</span>. For example, if <span class="math-container">$\mathfrak S = K_{n,d}$</span> is the collection of all subsets of <span class="math-container">$[n]$</span> with <span class="math-container">$d$</span> or fewer elements (where <span class="math-container">$d \in [n]$</span>), then <span class="math-container">$\partial_j \mathfrak S$</span> is isomorphic to <span class="math-container">$K_{n-1,d-1}$</span>, and so
<span class="math-container">$$
d_{\mathfrak S}^\star = |K_{n-1,d-1}| = \sum_{i=0}^{d-1} {n-1 \choose i}.
$$</span></p>
</li>
<li><p><strong>Monster.</strong> Finally, if <span class="math-container">$1 \le k \le n$</span>, and <span class="math-container">$G_1,\ldots,G_k$</span> is a partition of <span class="math-container">$[n]$</span>, and <span class="math-container">$\mathfrak S$</span> is the collection of subsets of <span class="math-container">$[n]$</span> which contain exactly one element from each <span class="math-container">$G_i$</span>, then <span class="math-container">$d_{\mathfrak S}^\star = p^{k-1}$</span>, where <span class="math-container">$p := n/k$</span>.</p>
</li>
</ul>
<blockquote>
<p>Let us say that <span class="math-container">$\mathfrak S$</span> is &quot;nice&quot; if the following three conditions are satisfied:</p>
<ul>
<li>(1) <strong>Exponential Degree:</strong> <span class="math-container">$d_{\mathfrak S}^\star \ge 2^{\alpha n}$</span> for some constant <span class="math-container">$\alpha \in (0, 1]$</span>.</li>
<li>(2) <strong>Efficiency:</strong> <span class="math-container">$f_{\mathfrak S}(z)$</span> can be computed in linear time time <span class="math-container">$O(n)$</span>, for any <span class="math-container">$z \in \{\pm 1\}^n$</span>.</li>
<li>(3) <strong>Invariance:</strong> <span class="math-container">$f_{\mathfrak S}(\overline z) = f_{\mathfrak S}(z)$</span> for any <span class="math-container">$z,\overline z \in \{\pm 1\}^n$</span> such that the components of <span class="math-container">$\overline z$</span> are a permutation of the components of <span class="math-container">$z$</span>.</li>
</ul>
</blockquote>
<p>It is clear that the &quot;pairs&quot; example verifies the conditions (2) and (3), but not (1). The &quot;simplicial complex&quot; example verifies conditions (1 and 3) or (2 and 3). This is because thanks to <a href="https://cstheory.stackexchange.com/a/52570/44644">https://cstheory.stackexchange.com/a/52570/44644</a>, <span class="math-container">$f_{\mathfrak S}$</span> can be computed in time of order <span class="math-container">$O(nd)$</span>; if the time complexity is really <span class="math-container">$\Theta(nd)$</span> (see Question 2 below), then it can be linear is if <span class="math-container">$d=O(1)$</span>, which forces <span class="math-container">$d_{\mathfrak S}^\star$</span> to be of polynomial order <span class="math-container">$n^{d-1}$</span>.</p>
<p>Finally, still thanks to the previous reference, for appropriate choice of <span class="math-container">$k$</span> (for example assume WLOG that <span class="math-container">$n$</span> is even, and take <span class="math-container">$k=n/2$</span>) the &quot;monster&quot; example verifies conditions (1) and (2), but not (3). Condition (1) is clear to see. For condition (2), simply note that by construction <span class="math-container">$f_{\mathfrak S}(z) := \sum_{\sigma \in \mathfrak S} z_\sigma = \sum_{i=1}^k \prod_{j \in G_i} z_j$</span>, which definitely takes <span class="math-container">$O(n)$</span> time to compute. Condition (3) fails because every partitioning of <span class="math-container">$[n]$</span> induces a partial order on <span class="math-container">$[n]$</span>, and so <span class="math-container">$f_{\mathfrak S}(\overline z)$</span> will be different from <span class="math-container">$f_{\mathfrak S}(z)$</span> in general.</p>
<h2>Question 1</h2>
<p>What is an explicit construction of a &quot;nice&quot; <span class="math-container">$\mathfrak S$</span> ?</p>
<p><strong>N.B:</strong> I'm fine with randomized constructions, which verify the above 3 conditions in an appropriate probabilistic sense.</p>
<h2>Question 2</h2>
<p>Is <span class="math-container">$\mathfrak S = K_{n,d}$</span> efficient ?</p>

CC BY-SA 4.0
2023-03-16T01:06:20.013Z
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).
Jason Gaitonde
CC BY-SA 4.0
2023-03-16T17:20:06.520Z
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.
Neal Young
CC BY-SA 4.0
2023-03-16T19:59:33.770Z
@NealYoung There's typo in LHS. Fixed.
dohmatob
CC BY-SA 4.0
2023-03-16T21:26:25.887Z
@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.
dohmatob
<ds.algorithms><circuit-complexity><ds.data-structures><linear-algebra><randomized-algorithms>
Construction of a collection of subsets of $\{1,2,\ldots,n\}$ with certain properties
dohmatob
# Construction of a collection of subsets of $\{1,2,\ldots,n\}$ with certain properties

(Asked by: username_0 on 2023-03-15)

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 ?

**Tags:** ds.algorithms, circuit-complexity, ds.data-structures, linear-algebra, randomized-algorithms

> **Comments:**
> **username_1**: 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).  
> **username_2**: 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.  
> **username_0**: @NealYoung There's typo in LHS. Fixed.  
> **username_0**: @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.  

---

## 1 answers

### Answer by username_1 on 2023-03-16. Score: 1 | Accepted answer

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.

> **Comments:**
> **username_0**: 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 ?  
> **username_1**: @username_0 yes, that's right. But computing $\vert K_{n,d}\vert$ will also take up another $O(d)$ operations as well.  

---

