Skip to main content
2 of 2
added 104 characters in body
Terry Tao
  • 114.1k
  • 33
  • 462
  • 539

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)$.

Terry Tao
  • 114.1k
  • 33
  • 462
  • 539