Optimal bounds for an alternating sum on a downset - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T05:35:08Z http://mathoverflow.net/feeds/question/101787 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/101787/optimal-bounds-for-an-alternating-sum-on-a-downset Optimal bounds for an alternating sum on a downset Terry Tao 2012-07-09T16:27:27Z 2012-07-10T01:44:59Z <p>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 <em>downset</em> 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}$.</p> <p>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$.)</p> <p>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.</p> <p>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.)</p> <p>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.</p> <p>One small observation (using the shifting technology of Frankl) which may or may not be of use: given two natural numbers $1 \leq i &lt; j \leq n$ and a downset ${\mathcal D}$, define the <em>$ij$-shift</em> 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}$ <em>shift-minimal</em> 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.</p> http://mathoverflow.net/questions/101787/optimal-bounds-for-an-alternating-sum-on-a-downset/101790#101790 Answer by Robert Israel for Optimal bounds for an alternating sum on a downset Robert Israel 2012-07-09T16:56:35Z 2012-07-09T17:15:10Z <p>I tried it using linear integer programming for the first few values of $n$, with the following results.</p> <p>$$\matrix{ n &amp; min &amp; max\cr 1 &amp; 0 &amp; 1\cr 2 &amp;-1 &amp; 1\cr 3 &amp; -2 &amp; 1\cr 4 &amp; -3 &amp; 3\cr 5 &amp; -4 &amp; 6\cr 6 &amp; -10 &amp; 10\cr 7 &amp; -20 &amp; 15\cr 8 &amp; -35 &amp; 35\cr 9 &amp; -56 &amp; 70\cr}$$</p> <p>These sequences do not appear to be in the OEIS.</p> http://mathoverflow.net/questions/101787/optimal-bounds-for-an-alternating-sum-on-a-downset/101791#101791 Answer by Christian Stump for Optimal bounds for an alternating sum on a downset Christian Stump 2012-07-09T17:23:31Z 2012-07-09T17:23:31Z <p>This is more a comment, but here I have more space:</p> <p>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." ?</p> <p>It states that a vector $(f_{-1},\ldots,f_{d-1})$ is the f-vector of a $d$-dimensional downset if and only if</p> <p>$$f_{-1} = 1, \quad f_j \leq f_{j-1}^{(j)}, j = 1,\ldots,d-1,$$</p> <p>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$.</p> <p>This might give some insight on min/max values of the alternating sum of f-vectors of downsets.</p> http://mathoverflow.net/questions/101787/optimal-bounds-for-an-alternating-sum-on-a-downset/101794#101794 Answer by Robert Israel for Optimal bounds for an alternating sum on a downset Robert Israel 2012-07-09T18:18:32Z 2012-07-09T18:18:32Z <p>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.</p> <p>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. </p> http://mathoverflow.net/questions/101787/optimal-bounds-for-an-alternating-sum-on-a-downset/101795#101795 Answer by Terry Tao for Optimal bounds for an alternating sum on a downset Terry Tao 2012-07-09T18:43:48Z 2012-07-09T22:13:47Z <p>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.</p> <p>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,</p> <p>$$F_-(n) = -\binom{n-1}{n/2}, F_+(n) = \binom{n-1}{n/2}$$</p> <p>when $n$ is even,</p> <p>$$F_-(n) = -\binom{n-1}{(n-1)/2}, F_+(n) = \binom{n-1}{(n+1)/2}$$</p> <p>when $n=3 \mod 4$, and</p> <p>$$F_-(n) = -\binom{n-1}{(n+1)/2}, F_+(n) = \binom{n-1}{(n-1)/2}$$</p> <p>when $n=1 \mod 4$. As mentioned in the post, these bounds would be best possible.</p> <p>By slicing an n-dimensional downset into two n-1-dimensional downsets, one obtains the inequalities</p> <p>$$F_-(n-1)-F_+(n-1) \leq F_-(n) \leq F_+(n) \leq F_+(n-1) - F_-(n-1)$$</p> <p>which already gives most of the conjecture by induction and Pascal's identity; the only remaining cases that need separate verification are</p> <p>$$F_+(n) = \binom{n-1}{(n+1)/2} \qquad (1)$$</p> <p>when n is 3 mod 4, and</p> <p>$$F_-(n) = -\binom{n-1}{(n+1)/2} \qquad (2)$$</p> <p>when n is 1 mod 4.</p> <p>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|}$:</p> <p>$$\sum_{A \in {\mathcal D}} (-1)^{|A|} = F_+(n).$$</p> <p>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</p> <p>$$f_0 - f_1 + \ldots - f_n = F_+(n).$$</p> <p>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$.</p> <p>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</p> <p>$$r f_r \leq (n-r+1) f_{r-1}.$$</p> <p>(EDIT: Actually we didn't need to remove the r=0 case if we adopted the convention $f_{-1}=0$ here.)</p> <p>In particular, if $r > \frac{n+1}{2}$, then $f_r &lt; 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 &lt; \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$. </p> <p>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)$.</p> http://mathoverflow.net/questions/101787/optimal-bounds-for-an-alternating-sum-on-a-downset/101818#101818 Answer by Ryan O'Donnell for Optimal bounds for an alternating sum on a downset Ryan O'Donnell 2012-07-10T01:44:59Z 2012-07-10T01:44:59Z <p>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.</p> <p>--</p> <p>Identify the discrete cube with <code>$\{-1,1\}^n$</code> and let <code>$f : \{-1,1\}^n \to \{0,1\}$</code> 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, </p> <p>$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}]$</p> <p>where we used $\chi(x^{(j)}) = -\chi(x)$. Thus in absolute value, the quantity is at most</p> <p>$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]$,</p> <p>where the last step uses that $f$ is monotone. But </p> <p>$\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]$</p> <p>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 &lt; 0$. (If $n$ is even and the sum is $0$, it doesn't matter what $f$'s values are there.) </p> <p>--</p> <p>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.</p> <p>--</p> <p>For people familiar with "<a href="http://analysisofbooleanfunctions.org/?p=368" rel="nofollow">analysis of boolean functions</a>", I think this result could be considered "folklore". For example, it essentially appears at the end of page 8 here: <a href="http://cs.indstate.edu/~jkinne/research/mon.pdf" rel="nofollow">http://cs.indstate.edu/~jkinne/research/mon.pdf</a> </p>