Optimal bounds for an alternating sum on a downset - MathOverflow

Optimal bounds for an alternating sum on a downset

2012-07-09T16:27:27Z

Let $n$ be a natural number, and consider the discrete cube $2^{[n]} := \{ A: A \subset \{1,\ldots,n\}\}$ consisting of all subsets of the $n$-element set $[n] := \{1,\ldots,n\}$. Define a downset in $2^{[n]}$ to be a collection ${\mathcal D}$ of elements $A$ in $2^{[n]}$ with the property that if $A \in {\mathcal D}$ and $B \subset A$, then $B \in {\mathcal D}$.

My question is: what are the largest and smallest possible values for the alternating sum $\sum_{A \in {\mathcal D}} (-1)^{|A|}$, as ${\mathcal D}$ ranges over downsets in $2^{[n]}$, as a function of $n$? (Here $|A|$ denotes the cardinality of $A$.)

The trivial bounds here are $\pm 2^{n-1}$, by taking only the positive or negative values of ${\mathcal D}$, but of course these values are attained on a "checkerboard" set which is very far from being a downset, and this suggests that significant improvement is possible.

By taking ${\mathcal D}$ to be the set of all subsets $A$ of $2^{[n]}$ of cardinality at most $r$ for some $1 \leq r \leq n-1$, this gives a value of $(-1)^r \binom{n-1}{r}$; setting $r$ close to $(n-1)/2$ then seems to give reasonably good extremals (of size about $2^n/\sqrt{n}$ asymptotically). In the spirit of Sperner's lemma, one might tentatively conjecture that these are the extremal examples, but I was unable to prove or disprove this. (I feel like I'm missing some obvious application of downset isoperimetric inequalities or something.)

One motivation for this question is from analytic number theory: partial divisor sums $\sum_{d|a: d \leq x} \mu(d)$ of the Mobius function (which show up from time to time in this subject) can be viewed as an alternating sum over a downset, where $n$ is the number of prime factors $p_1,\ldots,p_n$ of $a$, and ${\mathcal D}$ is the collection of subsets $A$ of $[n]$ for which $\prod_{i \in A} p_i \leq x$. So any bounds on the general alternating-sum-of-downset problem would imply bounds on partial divisor sums of the Mobius function that depend only on the number of prime factors.

One small observation (using the shifting technology of Frankl) which may or may not be of use: given two natural numbers $1 \leq i < j \leq n$ and a downset ${\mathcal D}$, define the $ij$-shift of ${\mathcal D}$ to be the set formed by replacing any element of ${\mathcal D}$ of the form $A \cup \{j\}$ with $A \cup \{i\}$, if $A$ is disjoint from $\{i,j\}$ and $A \cup \{i\}$ is not already in A. Note that this is again a downset. Call a downset ${\mathcal D}$ shift-minimal if it is equal to all of its $ij$-shifts. Then one can reduce without loss of generality to the shift-minimal case, because shifting does not affect the sum $\sum_{A \in {\mathcal D}} (-1)^{|A|}$. In other contexts, the reduction to the shift-minimal case can be very powerful, but for some strange reason I was unable to exploit it here.

Answer by Robert Israel for Optimal bounds for an alternating sum on a downset

2012-07-09T16:56:35Z

I tried it using linear integer programming for the first few values of $n$, with the following results.

$$ \matrix{ n & min & max\cr 1 & 0 & 1\cr 2 &-1 & 1\cr 3 & -2 & 1\cr 4 & -3 & 3\cr 5 & -4 & 6\cr 6 & -10 & 10\cr 7 & -20 & 15\cr 8 & -35 & 35\cr 9 & -56 & 70\cr} $$

These sequences do not appear to be in the OEIS.

Answer by Christian Stump for Optimal bounds for an alternating sum on a downset

2012-07-09T17:23:31Z

This is more a comment, but here I have more space:

Did you try to use the characterization of f-vectors of simplicial complexes given by Kruskal in "Joseph B. Kruskal. The number of simplices in a complex. In Mathematical optimization techniques, pages 251–278. Univ. of California Press, Berkeley, Calif., 1963." ?

It states that a vector $(f_{-1},\ldots,f_{d-1})$ is the f-vector of a $d$-dimensional downset if and only if

$$f_{-1} = 1, \quad f_j \leq f_{j-1}^{(j)}, j = 1,\ldots,d-1,$$

where $$a^{(i)} := \binom{a_i}{i+1} + \binom{a_{i-1}}{i} + \ldots + \binom{a_j}{j+1}$$ for the (unique) $i$-canonical expression $$a = \binom{a_i}{i} + \binom{a_{i-1}}{i-1} + \ldots + \binom{a_j}{j}$$ with $a_i > a_{i-1} > \ldots > a_j \geq j \geq 1$.

This might give some insight on min/max values of the alternating sum of f-vectors of downsets.

Answer by Robert Israel for Optimal bounds for an alternating sum on a downset

2012-07-09T18:18:32Z

I don't know if this will be useful, but the problem can be transformed into a maximum-flow / minimum-cut problem. In fact it's the "strip mining" example in Chvatal, "Linear Programming", pp 372-373. Chvatal refers to J-C Picard, "Maximal closure of a graph and applications to combinatorial problems", Management Science 22 (1976), 1268-1272.

Consider the directed graph consisting of $2^{[n]}$ plus a source $s$ and sink $t$. We have an arc $A\to B$ (of infinite capacity) whenever $B \subset A$. For each subset $A$ of $2^{[n]}$ with even cardinality, we have an arc $s \to A$ with capacity $1$, and for each subset $B$ with odd cardinality, we have an arc $B \to t$ with capacity $1$. Then a minimum cut in this network is ${s} \cup \cal D$ where $\cal D$ is a downset maximizing the sum. If instead of $s \to A$ and $B \to t$ we take $A \to t$ and $s \to B$, a minimum cut corresponds to a downset minimizing the sum.

Answer by Terry Tao for Optimal bounds for an alternating sum on a downset

2012-07-09T18:43:48Z

Thanks for all the very quick responses,they were incredibly useful! Based on these responses, I think the conjecture is now settled in the affirmative, as follows.

For each n, let $F_-(n)$ and $F_+(n)$ be the minimal and maximal values of $\sum_{A \in {\mathcal D}} (-1)^{|A|}$ respectively. The conjecture is that $F_-(n), F_+(n)$ are the extremal values of $(-1)^r \binom{n-1}{r}$ for $r=0,\ldots,n-1$. More explicitly,

$$ F_-(n) = -\binom{n-1}{n/2}, F_+(n) = \binom{n-1}{n/2}$$

when $n$ is even,

$$ F_-(n) = -\binom{n-1}{(n-1)/2}, F_+(n) = \binom{n-1}{(n+1)/2}$$

when $n=3 \mod 4$, and

$$ F_-(n) = -\binom{n-1}{(n+1)/2}, F_+(n) = \binom{n-1}{(n-1)/2}$$

when $n=1 \mod 4$. As mentioned in the post, these bounds would be best possible.

By slicing an n-dimensional downset into two n-1-dimensional downsets, one obtains the inequalities

$$ F_-(n-1)-F_+(n-1) \leq F_-(n) \leq F_+(n) \leq F_+(n-1) - F_-(n-1)$$

which already gives most of the conjecture by induction and Pascal's identity; the only remaining cases that need separate verification are

$$F_+(n) = \binom{n-1}{(n+1)/2} \qquad (1)$$

when n is 3 mod 4, and

$$F_-(n) = -\binom{n-1}{(n+1)/2} \qquad (2)$$

when n is 1 mod 4.

Let's show (1), as the proof of (2) is similar. Fix n equal to 3 mod 4, and let ${\mathcal D}$ be a downset which attains the maximal value $F_+(n)$ of $\sum_{A \in {\mathcal D}} (-1)^{|A|}$:

$$ \sum_{A \in {\mathcal D}} (-1)^{|A|} = F_+(n).$$

Now introduce the "f-vector" $(f_0,\ldots,f_n)$ of $A$, with $f_i := |\{ A \in {\mathcal D}: |A|=i\}|$ defined as the number of elements of ${\mathcal D}$ of cardinality $i$. (This is shifted by one from the polytope conventions, I guess because i points determine an i-1-dimensional simplex.) Then we have

$$ f_0 - f_1 + \ldots - f_n = F_+(n).$$

Let r be the largest index for which $f_r$ is non-zero, or equivalently the largest cardinality of an element of ${\mathcal D}$. (We can treat the degenerate case when ${\mathcal D}$ is empty by hand.) If $r$ was odd, we could simply remove all $r$-element sets from ${\mathcal D}$ and increase the alternating sum, so we may assume that $r$ is even, so the alternating sum looks like $f_0 - f_1 + \ldots - f_{r-1} + f_r$.

The case r=0 can also be treated by hand and will be ignored. Now, we double-count. Observe that each $r$-element set in ${\mathcal D}$ has $r$ "children" as $r-1$-element subsets of ${\mathcal D}$, by removing one of the r elements from that set. On the other hand, each $r-1$-element set can have at most $n-r+1$ "parents", and so

$$ r f_r \leq (n-r+1) f_{r-1}.$$

(EDIT: Actually we didn't need to remove the r=0 case if we adopted the convention $f_{-1}=0$ here.)

In particular, if $r > \frac{n+1}{2}$, then $f_r < f_{r-1}$ we could remove both the r and r-1-element sets from the downset and again increase the sum; so we have $r \leq \frac{n+1}{2}$. In fact the same argument shows that, by changing the extremum ${\mathcal D}$ if necessary, we may assume that $r < \frac{n+1}{2}$, thus (since $n$ is 3 mod 4 and r is even) $r \leq \frac{n-3}{2}$. In other words, every element of ${\mathcal D}$ has cardinality at most $(n-3)/2$.

Now we flip the downset to look at the complementary downset ${\mathcal D}' := \{ A \in [n]: [n] \backslash A \not \in {\mathcal D} \}$. As n is odd, we have $\sum_{A \in {\mathcal D}'} (-1)^{|A|} = \sum_{A \in {\mathcal D}} (-1)^{|A|}$, and so ${\mathcal D}'$ is also an extremiser. Thus, by the above argument, every element of ${\mathcal D}'$ has cardinality at most $(n+1)/2$. Equivalently (as $n$ is odd), ${\mathcal D}$ contains every element of cardinality at most $(n-3)/2$. Combining this with the previous analysis, we see that the extremum is attained at the set consisting precisely of all subsets of [n] of cardinality at most $(n-3)/2$, which gives the required value of $F_+(n)$.

Answer by Ryan O'Donnell for Optimal bounds for an alternating sum on a downset

2012-07-10T01:44:59Z

Here is a simple proof which should give exact optimizers for "most" choices of n mod 4 and max/minimizing; and, near-sharp values for the remaining cases. I'll do it for upsets instead of downsets.

Identify the discrete cube with $\{-1,1\}^n$ and let $f : \{-1,1\}^n \to \{0,1\}$ be the indicator of $\mathcal{D}$ which is monotone since $\mathcal{D}$ is an upset. Up to a factor of $2^n$ we are trying to min/maximize $E_x[f(x) \chi(x)]$, where $x$ is uniformly random on the cube and $\chi(x) = \prod_{i=1}^n x_i$. Let $1 \leq j \leq n$ be uniformly random and let $x^{(j)}$ denote $x$ with its $j$th coordinate negated. Since $x^{(j)}$ is also uniformly distributed,

$E_x[f(x) \chi(x)] = E_{x,j}[\frac{f(x) \chi(x) + f(x^{(j)})\chi(x^{(j)})}{2}] = E[\chi(x)\frac{f(x)-f(x^{(j)})}{2}]$

where we used $\chi(x^{(j)}) = -\chi(x)$. Thus in absolute value, the quantity is at most

$E[\bigl|\frac{f(x)-f(x^{(j)})}{2}\bigr|] = \frac{1}{2n}E_x\left[\sum_{i=1}^n \bigl|f(x)-f(x^{(i)})\bigr|\right] = \frac{1}{2n}E\left[\sum_{i=1}^n f(x)x_i\right]$,

where the last step uses that $f$ is monotone. But

$\frac{1}{2n}E\left[\sum_{i=1}^n f(x)x_i\right] = \frac{1}{2n} E\left[f(x)(\sum_{i=1}^n x_i)\right]$

is clearly maximized among $0$-$1$ functions $f$ by the "Hamming ball" which is $1$ when $\sum_{i=1}^n x_i > 0$ and $0$ when $\sum_{i=1}^n x_i < 0$. (If $n$ is even and the sum is $0$, it doesn't matter what $f$'s values are there.)

For the purposes of checking sharpness, note that the maximizing $f$ (or $f$'s) there happens to be monotone. The only inequality used is in fact sharp if $n$ is odd and $n$ has the "right" (vis-a-vis min/maxing) remainder mod $4$; if $n$ is even then I think you can get a sharp inequality for any remainder mod $4$ by suitably making $f$ equal to $0$ or $1$ on the middle Hamming layer. I hope a little trick can handle the case of odd $n$ congruent to the "wrong" value mod 4 but I didn't think about it.

For people familiar with "analysis of boolean functions", I think this result could be considered "folklore". For example, it essentially appears at the end of page 8 here: http://cs.indstate.edu/~jkinne/research/mon.pdf