Reverse Littlewood-Offord problem: lower bound for the number of choices of signs such that $|\pm a_1\dots\pm a_n| \leq \max|a_i|.$

Question

Let $n$ be a positive integer. For $\mathbf{a}\in\mathbb R^n$ let $N(\mathbf{a})$ be the number of choices of $\epsilon\in\{-1,1\}^n$ such that $$\Biggl|\sum_{i=1}^n\epsilon_ia_i\Biggr|\leq \max_{1\leq i\leq n}|a_i|.$$

Example. for $n$ even and $a=(1,\dots,1),$ we are counting $\epsilon$ with $|\sum_{i=1}^n\epsilon_i|\leq 1,$ which forces $\epsilon$ to have exactly $n/2$ entries of $-1,$ so $N(1,\dots,1)$ is the central binomial coefficient $\binom{n}{n/2}.$

Is it true that $N(\mathbf a)\geq \binom{n}{n/2}$ for even $n$?

I also have a conjectured lower bound for odd $n$ if you're interested. Define $$B_n=N(1,\dots,1,\tfrac12)=2\binom{n-1}{\lfloor (n-1)/2\rfloor}= \begin{cases} \binom{n}{n/2}&\text{ for $n$ even}\\ 2\binom{n-1}{(n-1)/2}&\text{ for $n$ odd.} \end{cases} $$

I've confirmed $N(\mathbf a)\geq B_n$ by picking random vectors $\mathbf{a}$ uniformly at random, but these tests aren't very convincing since it doesn't even find $B_n$ for $n\geq 9.$

For $n=3$ we always have $N(\mathbf{a})\geq B_3=4$: assume $1=a_1\geq a_2\geq a_3\geq 0,$ then $a_1-a_2-a_3$ and $a_1-a_2+a_3$ and their negations all lie in $[-1,1].$

This would be a reversed form of the Littlewood-Offord problem, where Erdős showed there are at most $\binom{n}{\lfloor n/2\rfloor}$ vectors $\epsilon\in\{-1,1\}^n$ such that $\Bigl|\sum_{i=1}^n\epsilon_ia_i\Bigr|\leq \color{red}{\min}_{1\leq i\leq n}|a_i|.$

It's a version of Tomaszewski's Problem with the $\ell^2$ norm replaced by $\ell^\infty.$

I believe a positive answer would also provide a lower bound for the Minimum number of balanced partitions.

Answer 1

Here is a proof of a strong version of the conjecture in @mathworker21's post, which in the context of the original question proves $N(\mathbf{a})\geq B_n.$ This also proves the slightly stronger "balanced partitions" conjecture by Karo that I linked to. (That post only asked about even $n,$ so I posted a cut-down version of this argument there.)

$\textbf{Theorem}$: Let $\Sigma$ be a collection of subsets of $[n]$ satisfying

1. $A \in \Sigma \implies A^c \in \Sigma$;
2. $\Sigma$ is "convex" i.e. $A \subseteq B \subseteq C$, $A,C \in \Sigma \implies B\in \Sigma$;
3. $\Sigma$ is a "cutset" i.e. $\emptyset = A_0 \subseteq A_1 \subseteq \dots \subseteq A_{n-1} \subseteq A_n = [n]$ with $|A_j| = j$ for each $j$ implies $A_j \in \Sigma$ for some $j$.

Then $|\Sigma| \ge B_n$.

Proof.

Define $L$ to be the set of sets $A\subseteq[n]$ such that $A\not\in\Sigma$ and there exists $B\in\Sigma$ with $A\subset B.$ Define $U$ to be the set of sets $A\subseteq [n]$ such that $A\not\in\Sigma$ and there exists $B\in\Sigma$ with $B\subset A.$ By the cutset property, every set is in $L\cup\Sigma\cup U.$ And by convexity, $L\cap U=\emptyset.$ So every subset of $[n]$ is in exactly one of $L,\Sigma,$ or $U.$ The L stands for lower, and the U stands for upper, in the sense of lower and upper sets. By property 1, a set is in $U$ iff its complement is in $L.$ In particular, $|L|=|U|.$

By the cutset property, for any $A\in L$ we have $A\cup\{j\}\not\in U$ for any $j\not\in A.$ And since $L$ is a lower set, $A\setminus\{j\}\not\in U$ for any $j\in A.$ This means that $L$ and $U$ are at Hamming distance at least $2$:

$$d(L,U):=\min_{A\in L}\min_{B\in U}|A\Delta B|\geq 2.$$

By the result in https://cseweb.ucsd.edu/~ccalabro/essays/harper.pdf, or B. Bollobás, Combinatorics: Set Systems, Hypergraphs, Families of Vectors, and Combinatorial Probability Chapter 16 Theorem 3, there is an integer $r$ and collections $L_0,U_0$ of subsets of $[n]$ such that:

• $|L_0|=|U_0|=|L|=|U|$
• $d(L_0,U_0)\geq 2$
• all sets in $L_0$ have cardinality at most $r$
• $L_0$ contains all sets of cardinality less than $r$
• all sets in $U_0$ have cardinality at least $n-r$
• $U_0$ contains all sets of cardinality more than $n-r$

Even $n.$

Suppose for contradiction that $L_0$ contains any set $A$ of cardinality $n/2.$ Then $r\geq n/2,$ so $U_0$ contains all sets of cardinality $(n/2)+1.$ In particular, $A\cup\{j\}\in U_0$ for any $j\in[n]\setminus A.$ This contradicts $d(L_0,U_0)\geq 2.$

So $L_0$ does not contain any set of cardinality $n/2.$ By a symmetric argument, neither does $U_0.$ This implies $$|\Sigma|=2^n-|L|-|U|=2^n-|L_0|-|U_0|\geq \binom{n}{n/2}=B_n.$$

Odd $n.$

By a similar argument to the even case, $L_0$ consists of sets of cardinality at most $(n-1)/2,$ and $U_0$ consists of sets of cardinality at least $(n+1)/2.$

Let $k=(n+1)/2,$ so $n=2k-1.$ Let $L'_0$ denote $\{A\in L_0\mid |A|=k-1\}.$ Let $U'_0$ denote $\{A\in U_0\mid |A|=k\}.$ Let $\Delta(U'_0)$ denote the lower shadow of $U'_0,$ i.e. the sets $B$ with $|B|=k-1$ and $B\cup\{j\}\in U'_0$ for some $j.$ Suppose for contradiction that $|L'_0|> \binom{2k-2}{k}.$ The Kruskal-Katona theorem says $$|L'_0|=|U'_0|\geq\binom{2k-2}{k}\qquad\implies\qquad|\Delta(U'_0)|\geq \binom{2k-2}{k-1}.$$

But $\binom{2k-2}{k}+\binom{2k-2}{k-1}=\binom{2k-1}{k}=\binom{2k-1}{k-1}=\binom{n}{k-1}.$ By the pigeonhole principle applied to the sets of cardinality $k-1,$ the sets $L'_0$ and $\Delta(U'_0)$ would have to intersect, which contradicts $d(L_0,U_0)\geq 2.$

So $|L'_0|\leq\binom{2k-2}{k}.$ The cardinality of $\Sigma$ is the number of sets not in $L_0$ or $U_0,$ which is twice the number of $k-1$ element sets not in $L_0'.$ This gives $|\Sigma|=2(\binom{n}{k-1}-|L'_0|)\geq 2\binom{2k-2}{k-1}=B_n.$

Answer 2

Nice problem, Dap. Just some (hopefully nontrivial) thoughts, not an answer. I think the way to go about your problem is to prove the following.

$\textbf{Conjecture}$: Let $\Sigma$ be a collection of subsets of $[n]$ satisfying

(1). $A \in \Sigma \implies A^c \in \Sigma$;

(2). $A \subseteq B \subseteq C$, $A,C \in \Sigma \implies B=A$ or $B=C$;

(3). $\emptyset = A_0 \subseteq A_1 \subseteq \dots \subseteq A_{n-1} \subseteq A_n = [n]$ with $|A_j| = j$ for each $j$ implies $A_j \in \Sigma$ for some $j$.

Then $|\Sigma| \ge B_n$.

.

To see that this conjecture gives that $N(a) \ge B_n$, let $a_1 \ge a_2 \ge \dots \ge a_n \ge 0$ and let $\Sigma = \{I \subseteq [n] : |\sum_{i \in I} a_i - \sum_{i \not \in I} a_i| \le a_1\}$. Clearly $\Sigma$ satisfies property (1) above. It satisfies property (3), since changing some $-a_j$ to $a_j$ cannot yield an addition of more than $2a_1$. And we get property (2), under the assumption that $a_{n-1}+a_n > a_1$, which is an assumption we can apriori make, for otherwise, we may use induction (on the original problem).

So it suffices to prove the conjecture. I want to now talk about the conjecture in two specific cases.

First, we'll prove the conjecture under the assumption that $\Sigma$ is an antichain. Take some $A \in \Sigma$. Let $k = |A|$. Suppose that there is some $B \subseteq [n]$, $|B| = k, |B \Delta A| = 1$ with $B \not \in \Sigma$. We can form an $n+1$-chain $\emptyset \subseteq A_1 \subseteq \dots \subseteq A_{k-2} \subseteq A \cap B \subseteq B \subseteq A \cup B \subseteq A_{k+2} \subseteq \dots \subseteq A_{n-1} \subseteq [n]$. But this chain doesn't intersect $\Sigma$, since everything above $A \cup B$ contains $A$ and everything below $A \cap B$ is contained by $A$ (meaning they can't be in $\Sigma$, since $\Sigma$ is an antichain), and since $B \not \in \Sigma$. This contradicts property (3) and so every such $B$ must be in $\Sigma$. But iterating this gives that all sets of size $k$ are in $\Sigma$. Now by property (1), we get that all sets of size $n-k$ are in $\Sigma$, which contradicts $\Sigma$ being an antichain unless $k = n/2$. [This argument thus shows $\Sigma$ cannot be an antichain for $n$ odd].

Second, let's consider the conjecture when $\Sigma = \{A \cup B : A \subseteq[n_1], B \subseteq (n\setminus[n_1]) : (|A|,|B|) \in J\}$ for a fixed $J \subseteq [n_1]\times (n\setminus[n_1])$ and fixed $n_1 \in [0,n]$ (this corresponds to $|\{a_1,\dots,a_n\}| = 2$). Let's have $n$ even and $n_1 = n/2$ for now. The dots below correspond to $[n_1]\times(n\setminus[n_1])$. The circled green dots below represent pairs of a certain $J$. Condition (1) corresponds to symmetry about the center green dot. Condition (3) corresponds to that any up-right path from the bottom left to the top right hits a circled dot. Condition (2) corresponds to that if one circled dot is (weakly) above and (weakly) to the right of another circled dot, then the two circled dots are adjacent. In particular, this condition combined with condition (1) implies that neither the bottom left quadrant nor the upper right quadrant can contain a circled dot. The conjecture is thus that circling green dots with restrictions mentioned above will yield the total weight of circles being at least ${n \choose n/2}$, where the weight of a dot in position $(i,j)$ is ${n/2 \choose i}{n/2 \choose j}$. It's easy to convince yourself the conjecture is true in this case, but might be a bit annoying to write down.

I'm not sure how to do the conjecture (in the general case). Condition (2) can be replaced by the weaker condition: $A \subseteq B, A,B \in \Sigma$ and $A \subseteq C \subseteq B$ imply $C \in \Sigma$ (thus making the conjecture harder). The reason I chose the condition (2) I chose is that it makes the second case of the conjecture considered above much easier (I don't know how to do that second case with this weaker condition (2)). I hope this helped!