# A natural refinement of the $A_n$ arrangement is to consider all $2^n-1$ hyperplanes given by the sums of the coordinate functions. Have you seen this arrangement? Is it completely intractable?

## The short version

Here is an extremely natural hyperplane arrangement in $\mathbb{R}^n$, which I will call $R_n$ for resonance arrangement.

Let $x_i$ be the standard coordinates on $\mathbb{R}^n$. For each nonempty $I\subseteq [n]=\{1,\dots,n\}$, define the hyperplane $H_I$ to be the hyperplane given by $$\sum_{i\in I} x_i=0.$$ The resonance arrangement is given by all $2^n-1$ hyperplanes $H_I$. The arrangement $R_n$ is natural enough that it arises in many contexts -- to first order, my question is simply: have you come across it yourself?

This feels rather vague to be a good question, and after giving some background on where I've seen this I'll try to be a bit more specific about what I'm looking for, but my point is this arrangement has a rather simple and natural definition, and so crops up in multiple places, and I'd be curious to hear about more of them even if you can't specifically connect it to what follows.

## What I knew until this week

I came across this arrangement in my study of double Hurwitz numbers -- they are piecewise polynomial, and the chambers of the resonance arrangement are the chambers of polynomiality. I don't want to go into this much more, as it's unimportant to most of what follows Though I will say that conjecturally double Hurwitz numbers could be related to compactified Picard varieties in a way which would connect this arrangement up with birational transformations of those. Also, the name "resonance arrangement" was essentially introduce in this context, by Shadrin, Shapiro and Vainshtein.

It apparently comes up in physics -- I only know this because the number of regions of $R_n$, starting at $n=2$, is 2, 6, 32, 370, 11292, 1066044, 347326352 ... Sloane sequence A034997, which you will see was entered as "Number of Generalized Retarded Functions in Quantum Field Theory" by a physicist.

You might expect by that rate of growth that this hyperplane arrangement is completely intractable, and more specifically, what I would love from an answer is some kind qualitative statement about how ugly the $R_n$ get. Which brings us to:

## Connection to the GGMS decomposition

I got to thinking about this again now and decided to post on MO of it because of Noah's question about the vertices of a variation of GIT problem, where this arrangement is lurking around -- see there for more detail. Allen's brief comment there prompted me to skim some of his and related papers to that general area, and I found the introduction to Positroid varieties I: juggling and geometry most enlightening, together with the discussion at Noah's question could give another suggestion why $R_n$ is perhaps intractable. Briefly:

The arrangement $R_n$ is a natural extension of the $A_n$ arrangement. One common description of the $A_n$ arrangement is as the $\binom{n+1}{2}$ hyperplanes $y_i-y_j=0, i,j\in [n]$ and $y_i=0, i\in [n]$. However, one can consider the triangular change of variables $$y_k\mapsto \sum_{j\leq k} y_j$$.

This changes the hyperplanes to $$\sum_{i\leq k \leq j} y_k=0.$$

These hyperplanes are no longer invariant under permutation of the coordinates, and if we proceed to add the entire $S_n$ orbit of them, we get the resonance arrangement $R_n$.

From the discussion on Noah's question and the introduction to the Positroid paper, we see that this manipulation is a shadow of the GGMS decomposition of the Grassmannian, and describing this decomposition in general seems to be intractable in that it requires identifying whether matroids are representable or not. So, what I'd really like to know how is much of the "GGMS abyss", as they refer to it, is reflected in the resonance arrangement? Is it hopeless to describe and count its chambers?

-
Several of my students and I have thought about the characteristic polynomial and number of regions of this arrangement over the years, but we never came up with anything interesting. –  Richard Stanley Apr 23 '11 at 19:09
-1 for not having a more specific question, but +2 for lots of details and interesting discussion and good title. Also, I think there's something funny with the TeX between "However, one can consider the triangular ..." and "These hyperplanes are no longer ...". –  Theo Johnson-Freyd Apr 23 '11 at 21:04
Think I fixed the TeX. And I was a bit torn about it not being specific enough myself, but it was never going to get asked if I kept worrying about it. Next time will be better. –  Paul Johnson Apr 23 '11 at 21:48
@Theo: Also, you are half responsible for the long title: somewhere you mentioned that a title can be about a "tweet and a half" long, and that was an odd enough description that it stuck in my head. Good work. –  Paul Johnson Apr 23 '11 at 21:56
Just commenting to thank Richard -- this is one kind of thing I wanted to hear: that people had put some real thought into it and not gotten anything interesting. I wasn't up-voting that you didn't get anywhere. –  Paul Johnson Apr 27 '11 at 19:41

## 1 Answer

Here's what I know about this arrangement.

Regarding the number of chambers in this arrangment, Zuev obtained the lower bound $2^{(1-o(1))n^2}$. The proof uses Zaslavsky's theorem and a difficult estimate due to Odlyzko.

http://www.doiserbia.nb.rs/img/doi/0350-1302/2007/0350-13020796129K.pdf describes an improvement to that lower bound (including references to Zuev's and Odlyzko's articles).

http://arxiv.org/pdf/1209.2309v1.pdf studies a closely related arrangement and gives a related (but weaker) lower bound using a very elegant method. It turns out the arrangment becomes much easier mod $2$ (even than one might expect).

Whenever one has a central hyperplane arrangement one has a zonotope dual to it. Klivans and Reiner [ http://arxiv.org/pdf/math/0610787v2.pdf ] fix $k$ and look at the zonotope (Minkowski sum of the line segments) generated by all 0/1-vectors of length $n$ with exactly $k$ ones. In particular they are interested in the zonotope considered as symmetric polynomial (the sum $\sum x^m$ over all lattice points $m$ in the zonotope). Thus the Minkowski sum of their zonotopes over $1\leq k \leq n$ is the zonotope dual to your arrangement. Degree sequences of hypergraphs correspond to integer points in this latter zonotope. Surprisingly the converse is false! This was showed by Liu [http://arxiv.org/abs/1201.5989 ].

The vertices in the zonotope, and thus the regions in the arrangement, correspond almost to linear threshold hypergraphs (better known as linear threshold (Boolean) functions). A linear threshold hypergraph is determined by $n+1$ real potentially negative numbers $q,w_1,\dots,w_n$; any set $S\subseteq [n]$ with $\sum_{i\in S} x_i \leq q$ is declared an edge. "Almost" above means that the vertices in this zonotope correspond exactly to the linear threshold hypergraphs that can be given with $q = 0$.

What if $q \neq 0$? Given a hypergraph $\mathcal{H}$ with $s$ simplices and degree sequence $v_1,\dots,v_n$, one can look at the values $s-2v_i$, $1\leq i\leq n$. If $\mathcal{H}$ happens to be down-closed, this is what game theorists call the Banzhaf value of the game represented by $\mathcal{H}$ and what computer scientists call the Boolean influence of the Boolean function represented by $\mathcal{H}$. Anyway it is more natural to look at the vector $(s,v_1,\dots,v_n)$ rather than just $(v_1,\dots,v_n)$. This corresponds to looking instead at the zonotope generated by $(1,0,0),(1,0,1),(1,1,0),(1,1,1)$ et.c. (all binary vectors of length $n$, prepended by $1$). The vertices (obviously more than when we didn't have the leading 1's in the generators) in this zonotope correspond exactly to linear threshold hypergraphs. Since each $v_i$ is an integer $0$ and $2^{n-1}$, and $s$ is between $2^n$ there are at most $2^{n + n(n-1)} = 2^{n^2}$ of them, giving an almost matching upper bound to the lower bound above.

The latter zonotope is briefly mentioned in the end of the article http://arxiv.org/pdf/0908.4425.pdf .

I remember having seen a reference to a paper of Terao computing the characteristic polynomial of the arrangemnt for some small values, but cannot locate that reference right now.

-
Thanks! Haven't digested this at all, but was hoping that there'd be more about this in the literature, and you've supplied that well. –  Paul Johnson Jun 21 '13 at 12:20