% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} % Please remove all other commands that change parameters such as % margins or pagesizes. % only use standard LaTeX packages % only include packages that you actually need % we recommend these ams packages \usepackage{amsthm,amsmath,amssymb} % we recommend the graphicx package for importing figures \usepackage{graphicx} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins % declare theorem-like environments \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} \newcommand{\A}{{\mathcal A}} \newcommand{\D}{{\mathcal D}} \newcommand{\E}{{\mathcal E}} \newcommand{\F}{{\mathcal F}} \newcommand{\G}{{\mathcal G}} \newcommand{\mH}{{\mathcal H}} \newcommand{\B}{{\mathcal B}} \newcommand{\R}{{\mathcal R}} \newcommand{\T}{{\mathcal T}} \newcommand{\Shi}{{\mathcal S}} \newcommand{\ST}{{\mathcal{ST}}} \newcommand{\real}{{\mathbb R}} %\newcommand{\perm}{{\mathcal S}} \newcommand{\mS}{{\mathcal S}} \newcommand{\ga}{\alpha} \newcommand{\gb}{\beta} \newcommand{\gc}{\gamma} \newcommand{\gd}{\delta} \newcommand{\ve}{\varepsilon} \newcommand{\rk}{{\rm rk}} \newcommand{\0}{\hat{0}} \newcommand{\fld}{{\mathbb F}} \newcommand{\cpst}{\chi_{\ST_n}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{\bf Shi threshold arrangement} % input author, affilliation, address and support information as follows; % the address should include the country, and does not have to include % the street address \author{Seunghyun Seo\\ %\thanks{Research supported by Basic Science Research Program through %the National Research Foundation of Korea funded by the Ministry of Education, Science and Technology(2011-0008683).}\\ \small Department of of Mathematics Education\\[-0.8ex] \small Kangwon National University\\[-0.8ex] \small Chuncheon 200-701, Republic of Korea\\ \small\tt shyunseo@kangwon.ac.kr\\ %\and %Forgotten Second Author \qquad Forgotten Third Author\\ %\small School of Hard Knocks\\[-0.8ex] %\small University of Western Nowhere\\[-0.8ex] %\small Nowhere, Australasiaopia\\ %\small\tt \{fsa,fta\}@uwn.edu.ao } % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \date{\dateline{Feb 8, 2012}{Aug 29, 2012}\\ \small Mathematics Subject Classifications: 52C35, 05A15} \begin{document} \maketitle % E-JC papers must include an abstract. The abstract should consist of a % succinct statement of background followed by a listing of the % principal new results that are to be found in the paper. The abstract % should be informative, clear, and as complete as possible. Phrases % like "we investigate..." or "we study..." should be kept to a minimum % in favor of "we prove that..." or "we show that...". Do not % include equation numbers, unexpanded citations (such as "[23]"), or % any other references to things in the paper that are not defined in % the abstract. The abstract will be distributed without the rest of the % paper so it must be entirely self-contained. \begin{abstract} Richard Stanley suggested the problem of finding the characteristic polynomial of a certain hyperplane arrangement defined by $x_i + x_j=0,1$, which is called the Shi threshold arrangement. We present the answer of the problem, using the finite field method. % keywords are optional %\bigskip\noindent \textbf{Keywords:} hyperplane arrangement; Shi threshold arrangement; finite field method \end{abstract} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Introduction} Much work has been devoted in recent years to studying hyperplane arrangements, especially finding their characteristic polynomials and number of regions. Several authors have worked on computing the number of regions of specific hyperplane arrangements. See for examples \cite{Ath-am,PoSt,Ard}. Stanley's paper \cite{Sta3} on hyperplane arrangements contain classic and more recent results in this field, together with numerous problems. We consider the following problems \cite[p.~473]{Sta3} of finding the characteristic polynomial of the following hyperplane arrangement: $$ x_i + x_j =0,1,\quad 1 \leq i < j \leq n. $$ Stanley called the arrangement by ``Shi threshold arrangements" The present paper solves this problem by the finite field method (see \cite{Ath-am, CR, Sta3}). In Section 2, we introduce the basic notations of hyperplane arrangements. In Section 3, we find the characteristic polynomial of the Shi threshold arrangement. We also calculate the exponential generating function for the characteristic polynomial of the Shi threshold arrangement. In Section 4, we comment on some related works and further studies. \section{Preliminaries} We recall some of the basic concepts of hyperplane arrangements. For a more thorough introduction, see \cite{OT, Sta2}. \subsection{Intersection posets and characteristic polynomials} Given a field $K$ and a positive integer $n$, a \emph{hyperplane arrangement} of dimension $n$ over $K$ is a finite set of affine hyperplanes in $V=K^n$. We will refer to hyperplane arrangements simply as arrangements. Now, let $V=\real^n$. A \emph{region} of an arrangement $\A$ is a connected component of the complement $X$ of the hyperplanes: $$X=\real^n - \bigcup_{H \in \A} H.$$ Let $R(\A)$ denote the set of regions of $\A$, and let $r(\A)$ be the number of regions. Given an arrangement $\A$ in $V$, let $L(\A)$ be the set of all nonempty intersections of hyperplanes in $\A$, including $V$. Define $x \leq y$ in $L(\A)$ if $x \supseteq y$ as a subsets of $V$. We call $L(\A)$ the \emph{intersection poset} of $\A$. It is easy to show that $L(\A)$ is a graded poset with the rank function $\rk:L(\A)\to \mathbb{N}$ defined by $$\rk(x)=\dim(V)-\dim(x)=n-\dim(x),$$ where $\dim(x)$ is the dimension of $x$ as an affine subspace of $V$. Given a finite poset $P$ with $\0$, the \emph{M\"{o}bious function} $\mu:P\to \mathbb{Z}$ is defined by $$ \mu(\0)=1\quad\mbox{and}\quad \mu(x)=-\sum_{y0$. For nonnegative integers $m$ and $n$, let $a_m(n)$ be \begin{equation} \label{eq:amn} a_m(n):=\sum_{0 \le j \le n} \binom{m-j+1}{j} \,S(n,j)\,j!\,, \end{equation} where $S(n,k)$ is the Stirling number of the second kind. Now we go back to Shi threshold arrangements, i.e., $$ {\bf u} = (u_1,\ldots,u_q)= (0,1,-1,2,-2,\ldots,r,-r). $$ To enumerate the set $Y$, we should regard the additional condition: Each $0$ and $-r$ can be chosen at most once. So we have three cases to consider. \begin{enumerate} \item Neither $0$ nor $-r$ are selected. \item Either $0$ or $-r$ is selected. \item Both $0$ and $-r$ are selected. \end{enumerate} By Lemma~\ref{lem:select}, the number of elements $(b_1,\ldots,b_n)$ of the first case is $$\sum_{0 \le j \le \min(n, r)} \binom{2r-j}{j} \,S(n,j)\,j!,$$ which becomes $a_{2r-1}(n)$ for $r \ge n$, i.e., for infinitely many sufficiently large primes $q=2r+1$. Similarly, the second case is $2n\, a_{2r-2}(n-1)$ and the third case is $n(n-1)\, a_{2r-3}(n-2)$ for infinitely many sufficiently large primes $q=2r+1$. Thus we have the following result: \begin{theorem}\label{thm:ch-poly} The characteristic polynomial of the Shi-threshold arrangement $\ST_n$ is given by \begin{align*} \chi_{\ST_n}(t) =& \sum_{j\geq 0}\,(t-j-1)_j\,S(n,j) \,+\, 2n \sum_{j\geq 0}\,(t-j-2)_j\,S(n-1,j)\\ &+\, n(n-1) \sum_{j\geq 0}\,(t-j-3)_j\,S(n-2,j), \end{align*} where $(x)_k$ is defined by $(x)_0=1$ and $(x)_k=x(x-1)\cdots(x-k+1)$ for $k \ge 1$. \end{theorem} For instance $\chi_{\ST_0}(t)=1$,~~$\chi_{\ST_1}(t)=t$,~~$\chi_{\ST_2}(t)=t^2 -2t$,~~and \begin{eqnarray*} \chi_{\ST_3}(t) &=& t^3-6t^2+12t-8 \\ \chi_{\ST_4}(t) &=& t^4 -12t^3 +60t^2 - 142t +130\\ \chi_{\ST_5}(t) &=& t^5-20t^4+180t^3-870t^2+2190t-2252. \end{eqnarray*} Applying the Zaslovsky's Theorem, we have the followings. \begin{corollary} The number of regions in the Shi-threshold arrangement $\ST_n$ is given by \begin{align*} r(\ST_n) =& \sum_{j\geq 0}\binom{2j+1}{j}\,j!\,(-1)^{n-j} S(n,j) + 2n \sum_{j\geq 0}\binom{2j+2}{j}\,j!\,(-1)^{n-j}S(n-1,j)\\ &+ n(n-1) \sum_{j\geq 0}\binom{2j+3}{j}\,j!\,(-1)^{n-j}S(n-2,j)\,. \end{align*} \end{corollary} The sequence $\{r(\ST_n)\}_{n \geq 0}$ starts with $$1,~1,~3,~27,~345,~5513,~106619,~2426819,~\ldots$$ which is not listed in the ``Online Encyclopedia of Integer Sequences". \subsection{Generating function for $\chi_{\ST_n}(t)$} Recall the definition of $a_m(n)$ in equation~\eqref{eq:amn}. By exponential formula we have $$ a_m(n)= \sum_{j \ge 0} \binom{m-j+1}{j} \left[\frac{x^n}{n!} \right] (e^x-1)^j, $$ where $\left[\frac{x^n}{n!} \right] F(x)$ is the coefficient of $\frac{x^n}{n!}$ in the power series $F(x)$. Thus \begin{equation} \label{eq:gen-amn-m} \sum_{n \ge 0} a_m(n)\frac{x^n}{n!} = \sum_{j \ge 0} \binom{m-j+1}{j}(e^x-1)^j. \end{equation} It is well known (for example~\cite[p.~54]{Wi}) that %According to Wilf's bo \begin{equation} \label{eq:gen-amn-l} \sum_{j \ge 0} \binom{2j+\alpha }{j}{z^j} = \frac{{C(z)}^{\alpha}}{\sqrt{1-4z}}\,, \end{equation} where $C(z)$ is the generating function for the Catalan number, i.e., $$C(z)=\frac{1-\sqrt{1-4z}}{2z}=\sum_{n\geq 0}\frac{1}{n+1}\binom{2n}{n} z^n.$$ Substitute $\alpha=-m-2$ and $z=-(e^x-1)$ then \begin{equation} \label{eq:gen-amn-r} \sum_{j \ge 0} \binom{2j+\alpha }{j}{z^j} = \sum_{j \ge 0} \binom{m-j+1}{j}(e^x -1)^{j}\,. \end{equation} Combining \eqref{eq:gen-amn-m}, \eqref{eq:gen-amn-l}, and \eqref{eq:gen-amn-r} yields that \begin{equation*} \label{eq:gen-amn} \sum_{n \ge 0} a_m(n)\frac{x^n}{n!} = \frac{{C(1-e^x)}^{-m-2}}{\sqrt{4e^x -3}}\,. \end{equation*} In Theorem~\ref{thm:ch-poly}, $\chi_{\ST_n}(t)$ is expressed by a linear combination of $a_m(n)$'s. So, with simple calculations, we can deduce the exponential generating function for $\chi_{\ST_n}(t)$, which is \begin{equation}\label{eq:gen-cha-st} \sum_{n \geq 0} \chi_{\ST_n}(t)\frac{x^n}{n!} ~=~\frac{C(1-e^x)^{-t}}{\sqrt{4e^x-3}}\left(x\,C(1-e^x)+1\right)^2. \end{equation} %where $C(z)$ is the generating function for the Catalan number, i.e., %$$C(z)=\frac{1-\sqrt{1-4z}}{2z}=\sum_{n\geq 0}\frac{1}{n+1}\binom{2n}{n} z^n.$$ %%\vspace{15pt} Put $t=-1$ and $x=-x$ in~\eqref{eq:gen-cha-st} to get \begin{equation}\label{eq:gen-reg-st} \sum_{n \geq 0} r(\ST_n)\frac{x^n}{n!} ~=~\frac{C(1-e^{-x})}{\sqrt{4e^{-x}-3}}\left(x\,C(1-e^{-x})-1\right)^2\,. \end{equation} Unfortunately, it looks like that right hand sides of equations~\eqref{eq:gen-cha-st} and \eqref{eq:gen-reg-st} cannot be simplified. \section{Remarks} A similar problem was solved by Athanasiadis in his PhD~thesis~\cite[Cor~7.3.3]{Ath-phd}, about the arrangement defined by \begin{equation} \label{arr:ath} x_i + x_j =0,1 \qquad 1\leq i \le j \leq n. \end{equation} The difference between this arrangement and the Shi-threshold arrangement is whether $i\leq j$ or $i