TITLE: Convert implication to linear constraint
QUESTION [1 upvotes]: I have the next constraint in logic (simplified):
$$\forall r \in R, t \in T: x_{rt} = 1 \implies t_a < r_p < t_b$$
I need to linearize this. What I've come up with is:
\begin{align}
x_{rt}t_a &< r_p \\
x_{rt}r_p &< t_b
\end{align}
But this looks kind of hacky. Although I think it should work, is there a better way to convert my constraint?
I need to assign reservations to tables. $R$ is the list of reservations. $T$ is the list of tables.
Obviously the amount of people in the reservation needs to be less than the maximum amount of seats on a table and more than the minimum amount of seats.
$x_{rt}$ is the boolean that says that reservation $r$ is assigned to table $t$. $t_a$ is the minimum seats at the table, $t_b$ is the maximum and $r_p$ is the amount of people in the reservation. $t_a$, $t_b$ and $r_p$ can be assumed constant. $x_{rt}$ is a variable (and needs to be optimized).

REPLY [1 votes]: I will reformulate the problem to what I think you want, which is not what you stated in the formulation. For simplicity, I will dispense with all subscripts other than on the t's.
First of all, $r$ needs to be a decision (i.e., optimization) variable in your optimization formulation; it can not be considered constant, or your whole formulation is meaningless. Second of all, all of your inequalities should be non-strict, i.e., $\le$ rather than $\lt$.
Even when these changes are made, your proposed formulation is incorrect. If $x = 0$, your constraints become $0 \le r$ and $0 \le t_b$. There is nothing which forces $r$ to equal $0$ in this case, which is one of your requirements.
Here is a correct formulation: Add the constraints
$xt_a \le r$ and $r \le xt_b $, and x is binary.
If $x = 1$, this becomes $t_a \le r \le t_b$.
If $x = 0$, this becomes $0 \le r \le 0$. In other words, $r = 0$, as required.


TITLE: Expectation of a combination of random variables.
QUESTION [0 upvotes]: Assume that $\xi_i, i=1, \dots, n$ are independent identically distributed  discrete random variables. What is an expectation of
$$\frac{\sum_{i=1}^{n} a_i \xi_i^2}{\left( \sum_{i=1}^n \xi_i \right)^2}$$
Note:
It is possible to show that $E\frac{\sum_i a_i \xi_i}{\sum_i \xi_i} = \frac{\sum_i a_i}{n}$.

REPLY [1 votes]: The expectation of $\eta_n^{-1}\sum\limits_{i=1}^na_i\xi_i$ is $\theta_1\sum\limits_{i=1}^na_i$, where $\theta_1=E[\eta_n^{-1}\xi_1]$ and $\eta_n=\sum\limits_{i=1}^n\xi_i$. Note that, by symmetry, $n\theta_1=E[\eta_n^{-1}\xi_1]+E[\eta_n^{-1}\xi_2]+\cdots+E[\eta_n^{-1}\xi_n]=1$ hence $\theta_1=n^{-1}$, irrespectively of the distribution of $\xi_1$. This yields the result recalled in the question.
Likewise, the answer here is $\theta_2\sum\limits_{i=1}^na_i$, where $\theta_2=E[\eta_n^{-2}\xi_1^2]$.
Note that $n^2\theta_2\geqslant1$ by Cauchy-Schwarz inequality and $n\theta_2\lt1$ for every $n\geqslant2$ since $n\theta_2+n(n-1)\varphi=1$, where $\varphi=E[\eta_n^{-2}\xi_1\xi_2]$. However, there is no reason to expect that $\theta_2$ is independent of the distribution of $\xi_1$, nor that it has a simple form in general.


TITLE: the integral a complex variable
QUESTION [1 upvotes]: $\int\limits_{0}^{2\pi}e^{\cos\varphi}(\cos\varphi-\sin\varphi)d\varphi$
I think
$e^{i\varphi}=z$ $\to d\varphi=\frac{dz}{iz}$
$\cos\varphi=\frac{z^2+1}{2z}$
$\sin\varphi=\frac{z^2-1}{2iz}$
$\oint\limits_{|z|=1}^{}e^{\frac{z^2+1}{2z}}\left(\frac{z^2+1}{2z}-\frac{z^2-1}{2iz}\right)dz$
$z=0$    -  essential singularity
We need to be expanded in a Laurent but I do not know how there are so many polchaetsya values at $\frac{1}{z}$

REPLY [0 votes]: $$\int_0^{2\pi}e^{\cos\varphi}(\cos\varphi-\sin\varphi)~d\varphi~=~2\int_0^\pi e^{\cos\varphi}\cos\varphi~d\varphi~=~2\pi~I_1(1).$$

See Bessel function for more information.


text:
\section{Factorization algebras}
Hochschild homology, $K$-theory and the Todd genus are all intimately concerned with the concept of associative algebra.  In order to understand the Witten genus, one needs to consider a richer algebraic structure called a factorization algebra (or more precisely, a translation-invariant factorization algebra on the complex plane $\C$).

Factorization algebras can be defined on any smooth manifold: they can be viewed as a ``multiplicative'' analog of a cosheaf.   In the algebro-geometric context,  factorization algebras were first considered by Beilinson and Drinfeld \cite{BeiDri04}.

In this section,  I will give the formal definition of a factorization algebra, and state a theorem (from \cite{CosGwi10}) which allows one to construct factorization algebras using the machinery of perturbative renormalization developed in \cite{Cos10}.

The approach to constructing factorization algebras developed in \cite{CosGwi10} is a quantum field theoretic analog of the deformation quantization approach to quantum mechanics. Thus, a classical field theory yields a \emph{commutative} factorization algebra (I will define what this means shortly).   Quantizing a classical field theory  amounts to replacing this commutative factorization algebra by a plain factorization algebra.   Just like the Todd genus of a complex manifold $X$ appears when one considers the deformation quantization of the cotangent bundle $T^\ast X$, we will see that the Witten genus arises when we consider the quantization of a commutative factorization algebra associated to a classical field theory whose fields are maps from a Riemann surface to $T^\ast X$.

\numberedparagraph
The definition of a factorization algebra is rather straightforward to give.   First I will define the notion of prefactorization algebra.
\begin{definition}
Let $M$ be a manifold.  A prefactorization algebra $\F$ on $M$ is consists of the following data.
\begin{enumerate}
\item For every open set $U \subset M$, a cochain complex of topological vector spaces, $\F(U)$.
\item If $U_1, \ldots, U_k$ are disjoint open sets in $M$, all contained in a larger open set  $V$,  a continuous linear map
$$
\F(U_1) \otimes \cdots \otimes \F(U_k) \to \F(V)
$$
(where we use the completed projective tensor product).  These maps are required to be $S_k$-covariant.
\item These maps must satisfy an evident compability condition, which says that different ways of composing these maps yield  the same answer.

More precisely, suppose that $V_1,\ldots, V_l$ are disjoint open subsets of $V$ such that each $U_i$ is in some $V_j$.  Then the diagram
$$
\xymatrix{  \otimes_{j = 1}^l \left( \otimes_{U_i \subset V_j} \F(U_i) \right) \ar[r] \ar[d]  &  \F(V) \\
\otimes_{j = 1}^l \F(V_j) \ar[ur] & }
$$
is required to commute.
\item $\F(\emptyset) = \C$.
\end{enumerate}
\end{definition}

\subsection{}
A factorization algebra is a prefactorization algebra that satisfies the //locality// axiom. This axiom is the analog of the gluing axiom for sheaves; it expresses how the values on big open sets are determined by the values on small open sets. For sheaves, the gluing axiom says that for any open set $U$ and any cover of that open set, we can determine the value of the sheaf on $U$ from the values on the open cover. For factorization algebras, we require our covers to be fine enough that they capture all the ``multiplicative structure.''

\begin{definition}
Let $U$ be an open set and $\mathfrak{U} := \{ U_i \mid i \in I\}$ a cover of $U$ by open sets.  The cover $\mathfrak{U}$ is \emph{factorizing} if  for any finite collection of points $\{x_1,\ldots,x_k\}$ in $U$, there is a finite collection of pairwise disjoint opens $\{U_{i_1}, \ldots, U_{i_n}\}$ from the cover such that $\{x_1,\ldots,x_k\} \subset U_{i_1} \cup \cdots \cup U_{i_n}$.
\end{definition}

\begin{remark} There is a simple way to find a factorizing cover of a Riemannian manifold $M$.  Namely, fix a Riemannian metric on $M$, and  consider
\[
\{ B_r(x) \,:\, \forall x \in M, \text{ with } 0 < r < InjRad(x)\},
\]
the collection of open balls, running over each point $x \in M$, whose radii are less than the injectivity radius at $x$. Another construction is simply to take the collection of open sets in $M$ diffeomorphic to the open $n$-ball.
\end{remark}

\subsection{}
In order to motivate our definition of factorization algebra, let us write briefly recall the cosheaf axiom. Since, in this paper, we are exclusively interested in factorization algebras and cosheaves with values in cochain complexes, we will discuss the homotopical version of the cosheaf axiom.

This homotopy cosheaf axiom is defined using the \v{C}ech complex associated to an open cover.   Let $\Phi$ be a pre-cosheaf on $M$, and let $\mf{U} = \{U_i \mid i \in I\}$ be a cover of some open subset $U$ of $M$.  The \v{C}ech complex of $\mf{U}$ with coefficients in $\Phi$ is is defined in the usual way, as
$$
\oplus_k \oplus_{j_1,\ldots, j_k \in I} \Phi (U_{j_1} \cap \cdots \cap U_{j_k}  )   [ k - 1]
$$
where the differential is defined in the usual way.  We say that $\Phi$ is a homotopy cosheaf if the natural map from the \v{C}ech complex to  $\Phi(U)$ is a quasi-isomorphism, for every open $U \subset M$ and every open cover of $U$.

We will define the notion of factorization algebra in a similar way, except that instead of considering elements $U_i$ of the cover, one considers finite collections of disjoint elements of the cover.

In order to make this precise, we need to introduce some notation.  Let $P I$ denote the set of finite subsets $\alpha \subset I$, with the property that if $j,j' \in \alpha$, $U_j \cap U_{j'} = \emptyset$.

If $\alpha \in PI$, let us define $\F(\alpha)$ by
$$
\F(\alpha) = \otimes_{j \in \alpha} \F( U_j ).
$$
Similarly, if $\alpha_1, \ldots, \alpha_k \in P I$, we will let
$$
\F(\alpha_1, \ldots, \alpha_k ) = \otimes_{j_1 \in \alpha_1,\ldots, j_k \in \alpha_k} \F (U_{j_1} \cap \cdots \cap U_{j_k}).
$$
Note that there are natural maps
$$
p_i : \F( \alpha_1,\ldots, \alpha_k ) \to \F( \alpha_1, \ldots, \what{\alpha_i}, \ldots, \alpha_k )
$$
for each $1 \le i \le k$.

This allows us to define the \v{C}ech complex of the cover $\mf{U}$ with coefficients in $\F$ by
$$
\check{C} ( \mf{U}, \F) = \oplus_{k \ge 0} \oplus_{\alpha_1,\ldots, \alpha_k \in P I } \F ( \alpha_1, \ldots, \alpha_k) [k-1].
$$
The differential defined in the usual way.
\begin{definition}
A prefactorization algebra is a factorization algebra if, for every open subset $U \subset M$ and every factorizing cover $\mf{U}$ of $U$, the natural map
$$
\check{C}(\mf{U}, \F) \to \F(U)
$$
is a quasi-isomorphism.
\end{definition}
We call this axiom the \emph{locality} axiom\footnote{In the version of this paper which appears in the ICM proceedings, a slightly weaker locality axiom was posited.   Owen Gwilliam and I have since found that the stronger axiom presented here satisfies better formal properties.}.     This axiom is, of course, only the correct one for factorization algebras taking values in the category of cochain complexes.

For factorization algebras taking values in vector spaces, one should require that the map from the \v{C}ech complex to $\F(U)$ is an isomorphism on $H_0$.  This amounts to saying that the sequence
$$
\oplus_{\alpha,\beta} \F(\alpha,\beta) \to \oplus_{\gamma}\F(\gamma) \to \F(U) \to 0
$$
is exact on the right.

  A special case of this locality axiom asserts that,  $U_1, U_2$ are disjoint subsets, then
$$
\F(U_1 \amalg U_2) = \F(U_1) \otimes \F(U_2).
$$
Similarly, if $\{U_i \in i \in I\}$ is any collection of disjoint open subsets of $M$, then
$$
\F(\amalg U_i) = \otimes_{i \in I} \F(U_i) .
$$
The cochain complexes $\F(U_i)$ are pointed; the map $\emptyset \to U$ induces a map $\F(\emptyset) = \C \to \F(U)$.  The infinite tensor product of pointed vector spaces is defined as the colimit over all finite tensor products, in the usual way.

\numberedparagraph
The definition of a factorization algebra is reminiscent of that of an $E_n$ algebra.  In fact, Jacob Lurie has shown the following \cite{Lur09a}.
\begin{proposition}
There is an equivalence of $(\infty,1)$-categories between the category of $E_n$ algebras, and the category of factorization algebras $\mc F$  on $\R^n$ with the additional property that if $B \subset B'$ are balls, the map
$$
\mc F(B) \to \mc F(B')
$$
is a quasi-isomorphism.
\end{proposition}

In another direction, what we call a factorization algebra is the $\cinfty$ analog of a definition introduced by Beilinson and Drinfeld \cite{BeiDri04}.  Beilinson and Drinfeld introduced an algebro-geometric version of the notion of factorization algebra, in order to give a geometric formulation of the axioms of a vertex algebra.  In particular, every vertex algebra yields a factorization algebra.

\numberedparagraph
As our first example of a factorization algebra, let us see how a differential graded associative algebra $A$ gives rise to a translation-invariant factorization algebra $\mc F_A$ on $\R$.

We will define the value of $\mc F_A$ on the open intervals of $\R$; the value of $\mc F_A$ on more complicated open subsets is formally determined by this data.

Let $-\infty \le a < b \le \infty$, and let $(a,b)$ be the corresponding (possibly infinite) open interval in $\R$. We set
$$
\mc F_A((a,b)) = A.
$$
If $(a,b) \subset (c,d)$, then the map
$$\mc F_A( (a,b) )  \to \mc F_A ((c,d))$$
is the identity map on $A$.

If $-\infty \le a_1 < b_1 < a_2 < b_2 < \dots < a_n < b_n \le \infty$, then the intervals $(a_i,b_i)$ are disjoint.  Part of the data of a factorization algebra is thus a map
$$
\mc F_A ((a_1, b_1 ) )  \otimes \cdots \otimes \mc F_A ((a_n, b_n ) )  \to \mc F_A ( (a_1, b_n ) ).
$$
Once we identify each $\mc F_A ((a_i, b_i ) )$ with $A$, this map is the $n$-fold product map
\begin{align*}
A ^{\otimes n} & \to A\\
\alpha_1 \otimes  \cdots \otimes \alpha_n & \mapsto \alpha_1 \cdot \alpha_2 \cdot \cdots \cdot \alpha_n.
\end{align*}
The value of $\F_A$ on any other open subset of $\R$ is determined from this data by the axioms of a factorization algebra.

\section{Descent and factorization homology}
In this paper, we are only interested in translation-invariant factorization algebras on $\C$.    In this section, we will see that associated to such a factorization algebra $\F$, and to an elliptic curve $\E$, equipped with a never-vanishing volume element $\omega$, one can define the \emph{factorization homology}
$$
FH( E, \F ).
$$
Factorization homology is the analog, in the world of factorization algebras, of Hochschild homology.

As motiviation, I will first explain how the Hochschild homology groups of an associative algebra $A$ can be viewed as the factorization homology of the translation-invariant factorization algebra $\F_A$ on $\R$ associated to $A$.

\numberedparagraph
Factorization algebras satisfy a gluing axiom. Suppose that our manifold $M$ is written as a union $M = U \cup V$ of two open subsets. If $\F$ is a factorization algebra on an open subset $U \subset M$, and if $\G$ is a factorization algebra on $V$, and if
$$
\phi : \F \mid_{U \cap V} \to \G \mid_{U \cap V}
$$
is an isomorphism of factorization algebras on $U \cap V$, then we can construct a factorization algebra $\mc{H}$ on $M$, whose restriction to $U$ is $\F$ and whose restriction to $V$ is $\G$.

Similarly, factorization algebras satisfy descent.  Suppose that a discrete group $G$ acts properly discontinuously on a manifold $M$, and suppose that $\til{\F}$ is a $G$-equivariant factorization algebra on $M$.  Then, $\til{\F}$ descends to a factorization algebra $\F$ on the quotient $M / G$.

\numberedparagraph
Since we will be using the descent property extensively, it is worth explaining how one constructs the descended factorization algebra $\F$.

Let us start by mentioning a general construction of factorization algebras from partial data. Let $\mf{U}$ be a basis of open sets of $X$ which is also a factorizing cover (that is, $\mf{U}$ is a \emph{factorizing basis}).
\begin{definition}
A $\mf{U}$-factorization algebra $\F$ is like a factorization algebra, except that $\F((U)$ is only defined for $U \in \mf{U}$.
\end{definition}
Let $\F$ be a $\mf{U}$-factorization algebra.  Let us define a prefactorization algebra $\op{Fact} (\F)$ on $X$ by
$$
\op{Fact}(\F)(V) = \check{C}(\mf{U}_V, \mc{F}).
$$
Here $\mf{U}_V$ is the cover of $V$ consisting of those open subsets in the cover $\mf{U}$ which are contained in $V$.
\begin{lemma}
With this definition, $\op{Fact}(\F)$ is a factorization algebra whose restriction to open sets in the cover $\mf{U}$ is quasi-isomorphic to $\F$.
\end{lemma}
\begin{comment}

\begin{proof}
We need to check that, if $\mf{U}'$ is a factorizing cover of $V \subset X$, that
$$
\op{Fact}(\F)(V) \simeq \check{C}(\mf{U}', \op{Fact}(\F)).
$$

We can replace $\mf{U}$ by the subcover $\til{\mf{U}}$ of open sets subordinate to $\mf{U}'$.  Then,
$$
\check{C}(\mf{U}', \op{Fact}(\F)) \simeq \check{C}(\til{\mf{U}}, \F).
$$
Indeed, there's clearly a natural map from the left hand side to the right hand side.

The complex on the left break up as a direct sum of pieces corresponding to tuples $\alpha_1,ldots,\alpha_n \in P \til{\mf{U}}$.  If $$\beta \in P \mf{U}'$ and $\alpha \in P \til{\mf{U}}$, say $\alpha \subset \beta$ if  $U_{\alpha} \subset U'_\beta$.  Then, let us define a complex
$$
\check{C}(\mf{U}', \op{Fact}(\F)) = \oplus_{\alpha_1,\ldots,\alpha_n} \F(\alpha_1,\ldots,\alpha_n)[k] \otimes \left( \oplus_{\substack{\beta_1,\ldots,\beta_m \\ \alpha_i \subset \beta_j \text{ all } i,j}} \C \cdots (\beta_1,\ldots,\beta_k) \right)
$$
Here $(\beta_1,\ldots,\beta_k)$ denotes a vector in degree $-k$.

We need to show that the complex inside the tensor product is contractible.   We have as usual
$$
\d  (\beta_1,\ldots,\beta_k) = \sum (-1)^i (\beta_1,\ldots,\what{\beta_i}, \ldots,\beta_k).
$$
But this is just the simplicial chains on the complete simplicial set based on vertices $\beta_i$, i.e. on the infinite simplex.

Next, the fact that $\F$ is a $\mf U$-factorization algebra implies that the map
$$
\check{C}(\til{U}, \F) \to \check{C}(\til{U}_V, \F)
$$
is a quasi-isomorphism.
\end{proof}
\end{comment}

\subsection{}
Now, let us see how this lemma allows us to construct a descended factorization algebra on $M / G$ from a $G$-equivariant factorization algebra $\til{\F}$  on $M$.   Let $\mf{U}$ be the open cover of $M / G$ consisting of connected open sets which admit a section of the map $M \to M / G$.

We will define a $\mf{U}$-factorization algebra $\F_0$ by saying that, if $U \in \mf{U}$,
$$
\F_0(V) = \til{\F} ( \til{U} )
$$
where $\til{U} \subset M$ is a lift of $U$ .  Since $\til{\F}$ is $G$-invariant, this is independent of the choice of lift $\til{U}$.

Now we can apply the extension procedure provided by the lemma. We will let
$$
\F = \op{Fact}(\F_0).
$$
$\F$ is the desired descended factorization algebra.

\numberedparagraph
This descent property implies that any translation-invariant factorization algebra $\F$ on $\R$ descends to a factorization algebra $\F^{S^1}$ on $S^1 = \R / \Z$.  We will let
$$
FH ( S^1, \F ) = \F^{S^1} (S^1)
$$
denote the complex of global sections of the factorization algebra $\F^{S^1}$ on $S^1$.  We will refer to the complex $FH ( S^1, \F)$ as the factorization homology complex of $S^1$ with coefficients in $\F$.

\begin{lemma}
Let $\F_A$ denote the factorization algebra on $\R$ associated to a differential graded associated algebra $A$.  Then, there is a natural quasi-isomorphism
$$
FH ( S^1, \F_A  )  \simeq HH(A)
$$
between the factorization homology complex of $S^1$ with coefficients in $\F_A$, and the Hochschild complex of $A$.
\end{lemma}
\begin{proof}
If one analyzes the descent prescription described above, one sees that
$$
FH ( S^1, \F_A ) = \hocolim_{I_1, \ldots ,I_n} A^{\otimes n}
$$
where the homotopy colimit is over disjoint unordered intervals in $S^1$.  The maps in this homotopy colimit just arise form multiplication in $A$.    One sees that a complex which looks like the ordinary cyclic bar complex emerges from this procedure.  In  \cite{Lur09a} it is proven that the result of this homotopy colimit is indeed homotopy equivalent to the cyclic bar complex.
\end{proof}

\numberedparagraph
If $\lambda \in \R_{> 0}$, let $S^1_\lambda$ be the quotient of $\R$ by the lattice $\lambda \Z$.  If $\F$ is a translation-invariant factorization algebra on $\R$, then we can descend $\F$ to a factorization algebra on $S^1_\lambda$, and thus define factorization homology $FH (S^1_\lambda, \F)$. When $\lambda = 1$, this coincides with the definition given above. In principle, there is no reason that $FH(S^1_\lambda, \F)$ should be independent of $\lambda$.

If we use the factorization algebra $\F_A$ arising from an associative algebra $A$, then all the factorization homology complexes $FH (S^1_\lambda ,\F_A)$ are canonically isomorphic.  This is because the factorization algebra $\F_A$ on $\R$ is not only translation invariant but also dilation invariant.

\numberedparagraph

As I mentioned earlier, the factorization algebras relevant to the Witten genus are translation-invariant factorization algebras on $\C$.  Let $\F$ be such a factorization algebra.  Let $E$ be an elliptic curve equipped with a volume element $\omega$.  We will write $E$ as a quotient $\C / \Lambda$ of $\C$ by a lattice $\Lambda$, in such a way that form $\omega$ on $E$ pulls back to the volume form $\d z$ on $\C$.

Since $\F$ is translation-invariant, it is in particular invariant under $\Lambda$.  Thus, $\F$ descends to a factorization algebra $\F^E$ on $E$.  We define the factorization homology complex of $E$ with coefficients in $\F$ by
$$
FH ( E , \F) = \F^E ( E).
$$
Thus, $FH ( E, \F)$ is the global sections of $\F^E$ on $E$.

Thus, there is an analog of the Hochschild homology groups for every elliptic curve $E$ with volume element $\omega$.

config: arxiv


TITLE: weak solution of viscous Burgers equation with non-homogeneous Dirichlet boundary conditions
QUESTION [0 upvotes]: I was wondering if anybody knows (and can give me a reference, please) if the PDE below has a unique weak solution. I can only find the result if we consider homogeneous Dirichlet boundary conditions, but not for non-homogeneous as I need.
Many thanks!
$$ \partial_t \rho(t,u)  = \partial_u^2\rho(t,u)-E\partial_u f(\rho(t,u))\\
\rho(t,0) = \alpha\; \rho(t,1) = \beta, \quad 0\leq t\leq T,\\
\rho(0,u) = \rho_0(u)\; \quad 0\leq u \leq 1 $$
with $f(x)=x(1-x)$ and $\alpha$, $\beta$ and $E$ constants;

REPLY [1 votes]: Try to substract $g(x)=\alpha-x(\alpha-\beta)$. Now the dirichlet conditions of the new unknown $h=\rho-g$ are homogeneous. The new problem is
$$
\partial_t h=\partial_u^2h-E\partial_u f(h)+F(g).
$$
with initial data $h_0=\rho_0-g$.
Now I think that the usual theory applies straightforwardly.


TITLE: Restrictions of Inserting Numbers Method
QUESTION [1 upvotes]: These are two similar questions from two different contests.

(AIME 2015) Call a permutation $a_1, a_2, ..., a_n$ quasi-increasing if $a_k \leq a_{k+1} + 2$ for each $1\leq k\leq n-1$.
For example, $54321$ and $14253$ are quasi-increasing permutations of the integers $1, 2, 3, 4, 5$, but
$45123$ is not. Find the number of quasi-increasing permutations of the integers $1, 2, . . . , 7$.

By inserting numbers one by one, the answer is $486$, which is the intended answer.
Let me explain the method used here:
Assume that the number of quasi-increasing permutations of the integers $1, 2, 3, ..., n$ be $A_n$, then obviously $A_1=1$, $A_2=2$, $A_3=6$, thus 4 can be inserted into the string of integers $1, 2, 3$ in only $3$ ways, so $A_4=3\times A_3=18$, and so do $5, 6, 7$, so $A_7=3\times 3\times 3\times A_4=486$

(SMO 2010 Open R1) Find the number of permutations $a_1a_2a_3a_4a_5a_6$ of the six integers from $1$ to $6$ such that for all $i$ from $1$ to $5$, $a_{i+1}$ does not exceed $a_i$ by $1$.

By inserting numbers one by one, the answer is $120$, which is not the intended answer.
By Inclusion-Exclusion, the answer is $309$, which is the intended answer.
I would like to ask what are the restrictions of this method for solving these similar problems?

REPLY [0 votes]: In general, for $n$-step process where the first step can be done in $m_1$ ways, the second in $m_2$ ways, and so on up the the $n^\text{th}$ being doable in $m_n$ ways, the number of ways to complete the whole process is $$m_1\times m_2\times \dots \times m_n$$
Importantly, the number of ways to complete each step must not depend on which particular choices you made previously. If $m_3=7$ (say), there should always be three choices for the third step, regardless of what you chose in steps $1$ and $2$.
Let's see why this works for the AIME 2015 problem. A permutation can be built by inserting the numbers $1,2,\dots, n$ one at a time. $1$ can be inserted in one way, $2$ in two ways, $3$ in three ways. For each $k\in \{4,\dots,n\}$, when you try to insert $k$ into the previous permutation made up $\{1,\dots,k-1\}$, there are always three options: either at the end of the permutation, or just before $k-1$, or just before $k-2$. These are indeed always legal, regardless of the specific ordering of $\{1,\dots,k-1\}$, and no other options are allowed. We conclude that the number of ways is $1\times 2\times 3\times 3\times \dots \times 3=2\cdot 3^{n-2}$.
Why does this same idea not work for the SMO 2010 problem? Let's see. Just look at a small example, permutations of length $3$. There is only one valid permutation of length $2$ where $a_{k+1}\neq a_k+1$, namely $[2,1]$. There are two ways to insert $3$ into this while maintaining the property $a_{k+1}\neq a_k+1$, which would suggest that there are only two valid permutations of length $3$, namely $[3,2,1]$ and $[2,1,3]$. However, there is actually a third permutation that works, namely, $[1,3,2]$. How did we miss this? The problem is that our process would require first inserting $2$ after $1$, which seems illegal, then later inserting $3$ after $1$. Inserting the $3$ blocks the $2$ from the $1$, so the it turned out not be an illegal move. To summarize,

the number of available moves depends on what choices were made later.

This shows that the number of moves at each step is not constant, so you cannot just multiply the number of ways to complete each step.


text:
\begin{document}

\begin{abstract}
We construct counterexamples to Yoshinaga's conjecture that every free arrangement is either inductively free or rigid in characteristic zero. The smallest example has $13$ hyperplanes, its intersection lattice has a one dimensional moduli space, and it is free but not recursively free.
\end{abstract}

\maketitle

\section{Introduction}

Let $\Ac$ be an arrangement of hyperplanes. To $\Ac$ we may associate its module of derivations $D(\Ac)$ and its intersection lattice $L(\Ac)$, see Section \ref{prel} for definitions. If $D(\Ac)$ is a free module, then $L(\Ac)$ satisfies certain strong combinatorial properties, for example that the characteristic polynomial of $L(\Ac)$ factorizes into degree one polynomials over the integers:
\begin{theor}[{\cite[Thm.\ 4.137]{OT}}] \label{Thm4137}
Let $\Ac$ be a free arrangement and $e_1,\ldots,e_r$ be the degrees of a homogeneous basis of $D(\Ac)$. Then
\[ \chi(\Ac,t) = \prod_{i=1}^r (t-e_i). \]
\end{theor}
On the other hand, there are certain strong combinatorial properties of $L(\Ac)$ which imply that $D(\Ac)$ is a free module, for example if $L(\Ac)$ is \emph{inductively free}.
The holy grail in the field of arrangements is Terao's conjecture (see \cite{p-hT-80}, \cite{p-hT-81}, \cite{p-hT-83}, \cite{p-gZ-86}, \cite{p-gZ-89}, \cite{p-gZ-90}, \cite{OT}, \cite{p-Y-12}):
\begin{oprob}[Terao]\label{probter}
Is the freeness of the module of derivations of any arrangement over a fixed field $K$ a purely combinatorial property of its intersection lattice?
\end{oprob}
To be more precise: are there arrangements $\Ac_1,\Ac_2$ in the same vector space $V$ such that $L(\Ac_1)\cong L(\Ac_2)$, $D(\Ac_1)$ is free, and $D(\Ac_2)$ is not free?
We formulate Terao's Conjecture as an open problem here because there is a lot of evidence that it is wrong;
we quote Ziegler \cite{p-gZ-90}: ``We believe that Terao's conjecture over large fields is in fact false.'' In fact I suppose that Terao himself has doubts that the answer is `yes'.

Another formulation of Problem \ref{probter} is using the moduli space of all arrangements whose intersection lattice is a given lattice, see Section \ref{modulispace} for details:
\begin{oprob}
Does a lattice $L$ exist such that the moduli space $\Vc(L)$ contains a free and a non-free arrangement?
\end{oprob}

\begin{figure}
\begin{center}
\setlength{\unitlength}{0.75pt}
\begin{picture}(400,400)(100,200)
\moveto(275.403252247502313339499089644,598.481737195138434731455900375)
\lineto(275.403252247502313339499089644,201.518262804861565268544099625)
\moveto(498.481737195138434731455900375,375.403252247502313339499089644)
\lineto(101.518262804861565268544099625,375.403252247502313339499089644)
\moveto(439.167609485287577515505169793,256.360254559712843091676482869)
\lineto(156.360254559712843091676482869,539.167609485287577515505169793)
\moveto(470.504748702514523981268673470,295.462300245832978482848070577)
\lineto(100.873581185488167904693903570,418.672689418175097175039660544)
\moveto(230.681892697506519411315616269,587.603304874940835888685984162)
\lineto(230.681892697506519411315616269,212.396695125059164111314015838)
\moveto(364.845971347493901195866036393,589.195665912303604228199767981)
\lineto(364.845971347493901195866036393,210.804334087696395771800232018)
\moveto(487.603304874940835888685984162,330.681892697506519411315616270)
\lineto(112.396695125059164111314015838,330.681892697506519411315616270)
\moveto(386.440473505466700388082664215,219.644671439542132362732041699)
\lineto(119.644671439542132362732041699,486.440473505466700388082664215)
\moveto(489.195665912303604228199767982,464.845971347493901195866036393)
\lineto(110.804334087696395771800232018,464.845971347493901195866036393)
\moveto(460.106753515647283469601637540,280.142470079348931065763488497)
\lineto(180.142470079348931065763488497,560.106753515647283469601637540)
\moveto(340.870050249808744105836497484,595.779567352106762728540852073)
\lineto(167.898376268199836280669216832,249.836219388888947078206290770)
\moveto(423.506575597486519570920613016,242.690986322517591848733751335)
\lineto(202.294208758280284618416006238,574.509536581326944277490661501)
\thinlines
\strokepath
\put(470,560){\Large $\infty$}
\end{picture}
\end{center}
\caption{An arrangement with $13$ hyperplanes which is free but not recursively free and whose intersection lattice defines a one dimensional moduli space (the symbol $\infty$ stands for the line at infinity).\label{a13m1}}
\end{figure}

Not much is known about this moduli space regarding freeness; Yuzvinsky \cite{p-sY-93} proved that the free arrangements form an open subset in $\Vc(L)$ (see also \cite[Thm.\ 1.50]{p-Y-12} for the case of dimension three).
The first intuition one gets when working with these notions is, that either the moduli space is very big and the free arrangements are inductively free, or the moduli space is zero dimensional and all its elements are Galois conjugates (let us call such an arrangement \emph{rigid}).
Yoshinaga proposed to check the following conjecture which is stronger than Terao's conjecture since the property of being free is invariant under Galois automorphisms:
\begin{conje}[Yoshinaga, {\cite[p.\ 20, (11)]{p-Y-12}}]
\[ \{\text{Free arrangements}\} \subset \{\text{Inductively free}\} \cup \{\text{Rigid}\}.\]
\end{conje}

Since Terao's conjecture is trivial for arrangements in dimension two but still open in dimension three, we will concentrate on dimension three in this note.
A recent result by Abe illustrates that the case of dimension three is somewhat special:
\begin{theor}[{\cite[Corollary 1.5]{p-tA-13}}]
Let $\Ac,\Ac'$ be a deletion pair of arrangements in $K^3$, i.e.\ $\Ac'=\Ac\backslash\{H\}$ for some $H\in\Ac$. Then if the characteristic polynomials $\chi(\Ac)$ and $\chi(\Ac')$ have a common root, then both $\Ac$ and $\Ac'$ are free.
\end{theor}
Thus if there is a counterexample $L$ to Terao's Conjecture in dimension three, then $L$ cannot be inductively free, and a recursively free arrangement $\Ac$ with $L=L(\Ac)$ is very unlikely to exist.
Another recent progress is our counterexample with Hoge \cite{p-CH-13} to the conjecture (see \cite[3.6]{gZ-87}, \cite[4.3]{OT}, \cite[5]{p-S-99}) that free arrangements are recursively free in characteristic zero.
Although recursive freeness is not a combinatorial property of the intersection lattice, it thus appears to be a good idea to investigate the (probably small) class of arrangements which are free but not recursively free. The smallest example provided in \cite{p-CH-13} has $27$ hyperplanes. A natural question is thus how many hyperplanes such an example will have at least.

\begin{resul}\label{mainres}
In this note we present
\begin{enumerate}
\item a lattice $L$ such that the moduli space $\Vc_\CC(L)$ has dimension one and consists mostly of arrangements with 13 hyperplanes which are free but not recursively free,
\item and a lattice $L'$ such that the moduli space $\Vc_\CC(L')$ has dimension one and consists mostly of arrangements with 15 hyperplanes which are free but not recursively free.
\end{enumerate}
\end{resul}
We thus obtain:
\begin{corol}
Yoshinaga's conjecture about free, inductively free, and rigid arrangements is wrong.
\end{corol}
I would like to emphasize that to my knowledge the two lattices presented here are the only two known such examples. Lattices satisfying these strong properties appear to be extremely rare.

After posting the first version of this paper, I was informed by Professor Takuro Abe that Abe, Kawanoue, and Nozawa also found the arrangement with 13 hyperplanes independently, see \cite{p-AKN-14}.

\section{Preliminaries}\label{prel}

We shortly review the required notions, compare with \cite{OT}.

\begin{defin}
Let $\Ac$ be a central arrangement of hyperplanes, i.e.\ a finite set of linear hyperplanes in a fixed vector space $V$ over a field $K$.
Let $S=S(V^*)$ denote the symmetric algebra of the dual space $V^*$ of $V$.
We choose a basis $x_1,\ldots,x_r$ for $V^*$ and identify $S$ with
$K[x_1,\ldots,x_r]$ via the natural isomorphism $S\cong K[x_1,\ldots,x_r]$.
We write $\Der(S)$ for the set of derivations of $S$ over $K$.
It is a free $S$-module with basis $D_1,\ldots,D_r$ where $D_i$ is the usual derivation
$\partial/\partial x_i$.

A nonzero element $\theta\in\Der(S)$ is \emph{homogeneous of polynomial degree} $p$
if $\theta=\sum_{k=1}^r f_k D_k$ and $f_k\in S_p$ for $a\le k\le r$.
In this case we write $\pdeg \theta = p$.
Let $\Ac$ be an arrangement in $V$ with defining polynomial
\[ Q(\Ac) = \prod_{H\in\Ac} \alpha_H \]
where $H=\ker \alpha_H$, $\alpha_H\in V^*$. Define the \emph{module of $\Ac$-derivations} by
\[ D(\Ac) = \{\theta\in\Der(S)\mid \theta(Q(\Ac))\in Q(\Ac)S\}. \]
An arrangement $\Ac$ is called a \emph{free arrangement} if $D(\Ac)$ is a free
module over $S$.
If $\Ac$ is free and $\{\theta_1,\ldots,\theta_r\}$ is a homogeneous basis for
$D(\Ac)$, then $\pdeg\theta_1,\ldots,\pdeg\theta_r$ are called the \emph{exponents}
of $\Ac$ and we write
\[ \exp \Ac = \lmultiset \pdeg\theta_1,\ldots,\pdeg\theta_r\rmultiset, \]
where we use the notation $\lmultiset *\rmultiset$ to emphasize the fact that it is a multi\-set.
Remark that the exponents depend only on $\Ac$, thus by Theorem \ref{Thm4137} they depend only on $L(\Ac)$.
\end{defin}
\begin{defin}[{\cite[1.12-1.14]{OT}}]
Let $(\Ac,V)$ be an arrangement. We denote $L(\Ac)$ the set of all nonempty
intersections of elements of $\Ac$ including the empty intersection $V$.
For $X\in L(\Ac)$ define an arrangement $(\Ac^X,X)$ in $X$ by
\[ \Ac^X=\{X\cap H\mid X \not\subseteq H \mbox{ and } X\cap H\ne \emptyset\}.\]
We call $\Ac^X$ the {\it restriction} of $\Ac$ to $X$.
Let $H_0\in\Ac$. Let $\Ac'=\Ac\backslash\{H_0\}$ and let $\Ac''=\Ac^{H_0}$.
We call $(\Ac,\Ac',\Ac'')$ a {\it triple} of arrangements and $H_0$ the
{\it distinguished} hyperplane.
\end{defin}

\begin{theor}[Addition-Deletion, {\cite[Thm.~4.51]{OT}}]\label{adddel}
Suppose $\Ac\ne\emptyset$. Let $(\Ac,\Ac',\Ac'')$ be a triple.
Any two of the following statements imply the third:
\begin{eqnarray*}
\Ac \mbox{ is free with } \exp \Ac &=& \lmultiset b_1,\ldots,b_{r-1},b_r\rmultiset, \\
\Ac' \mbox{ is free with } \exp \Ac' &=& \lmultiset b_1,\ldots,b_{r-1},b_r-1\rmultiset, \\
\Ac'' \mbox{ is free with } \exp \Ac'' &=& \lmultiset b_1,\ldots,b_{r-1}\rmultiset.
\end{eqnarray*}
\end{theor}

Inspired by this theorem, one defines:

\begin{defin}[{\cite[Def.~4.53]{OT}}]\label{def:indfree}
The class $\IF$ of \emph{inductively free} arrangements is the smallest
class of arrangements which satisfies
\begin{enumerate}
\item the empty arrangement $\Phi_\ell$ of rank $\ell$ is in $\IF$ for $\ell\ge 0$,
\item\label{part2} if there exists $H\in \Ac$ such that $\Ac''\in\IF$, $\Ac'\in\IF$, and
$\exp \Ac''\subset\exp \Ac'$, then $\Ac\in\IF$.
\end{enumerate}
\end{defin}

Thus the property of an arrangement $\Ac$ of being inductively free is a
combinatorial property of its intersection lattice $L(\Ac)$.
A class of arrangements which is bigger than the class of inductively free ones is:

\begin{defin}[{\cite[Def.~4.60]{OT}}]\label{def:recfree}
The class $\RF$ of \emph{recursively free} arrangements is the smallest
class of arrangements which satisfies
\begin{enumerate}
\item The empty arrangement $\Phi_\ell$ of rank $\ell$ is in $\RF$ for $\ell\ge 0$,
\item if there exists $H\in \Ac$ such that $\Ac''\in\RF$, $\Ac'\in\RF$, and
$\exp \Ac''\subset\exp \Ac'$, then $\Ac\in\RF$,
\item if there exists $H\in \Ac$ such that $\Ac''\in\RF$, $\Ac\in\RF$, and
$\exp \Ac''\subset\exp \Ac$, then $\Ac'\in\RF$.
\end{enumerate}
\end{defin}

We need the following simple lemma (see also \cite[Lemma 3.1]{p-CH-13} or \cite[Cor.\ 2.18]{p-HR12}):

\begin{lemma}\label{strnotindfree}
Let $\Ac$ be a free arrangement in $K^3$ with exponents $\lmultiset 1$, $e$, $f\rmultiset$.
If $|\Ac^H| \notin\{e+1,f+1\}$ for all $H\in\Ac$, then $\Ac$ is not inductively free.
\end{lemma}

For $\alpha=(a_1,\ldots,a_r)\in K^r$ we will write
\[ \ker \alpha := \left\{ (x_1,\ldots,x_r)\in K^r \mid \sum_{i=1}^r a_i x_i =0\right\}. \]

\section{Intersection lattices and moduli spaces}\label{modulispace}

Given a matrix $A\in K^{r\times n}$, let $\Ac(A)$ be the arrangement
\[ \Ac(A) := \{ \ker \alpha \mid \alpha \text{ is a column vector of } A, \:\: \alpha\ne 0 \}. \]
Thus the map $A \mapsto \Ac(A)$ is a surjection onto the set of arrangements in $K^r$ with at most $n$ hyperplanes.

Assume that $(L,\le)$ is a graded lattice, i.e.\ all maximal chains in $L$ have the same length. This implies the existence of a map $\rk : L \rightarrow \ZZ$ such that for fixed $n\in\ZZ$ the set $\{U\in L\mid \rk(U)=n\}$ is an antichain.

For a fixed field, the set $\Ac(L)$ consisting of those arrangements $\Ac$ with $L(\Ac)\cong L$ is not an algebraic variety.
However, in dimension three it is a constructible set:
\begin{propo}
Let $L$ be a graded lattice with $\rk(L)=\{0,\ldots,3\}$, $K$ be a field, and
\[ \Vc(L) := \{ A \in K^{3\times n} \mid |\Ac(A)|=n, \:\: L(\Ac(A))\cong L\} \]
where $n = \{U\in L\mid \rk(U)=1\}$.

Then $\Vc(L)$ is a constructible set, i.e., there exist varieties $V_1,V_2$ in $K^{3\times n}$ such that $\Vc(L) = V_1\backslash V_2$.
Moreover, $\{\Ac(A)\mid A\in \Vc(L)\}$ is the set of all arrangements $\Ac\in K^r$ with $L(\Ac)\cong L$.
\end{propo}
\begin{proof}
The isomorphism $L(\Ac(A))\cong L$ implies that we know exactly which subsets of the columns of $A$ are linearly independent or linearly dependent. These dependencies and independencies translate into equations of the form $\det(v_1,v_2,v_3)=0$ or $\det(v_1,v_2,v_3)\ne 0$ respectively, thus contribute to a variety $V_1$ or $V_2$ respectively.
\end{proof}

If $L$ is a poset, we write $\Aut(L)$ for the set of automorphisms of posets, i.e.\ the set of bijections preserving the relation in the poset.

\section{Examples}

\subsection{Arrangements with $13$ hyperplanes}

Let $R\subseteq \ZZ[t]^3$ be the set
\begin{eqnarray*}
R &=& \{ (1,0,0),(0,1,0),(0,0,1),(1,0,-1),(0,1,-1),(1,1,-1), \\
&& (1,0,-t),(0,1,-t),(1,1,-t),(1,1,-t-1), \\
&& (t,1,-t),(1,-t+1,-1),(t-1,t,-t^2) \}.
\end{eqnarray*}
We first consider the arrangement $\Ac_t = \{\ker_{\QQ(t)} \alpha\mid \alpha \in R\}$ as an arrangement in the space $\QQ(t)^3$.
Labeling the hyperplanes of $\Ac_t$ by $1,\ldots,13$ (in the ordering given by the definition of $R$) and the one dimensional elements by $1,\ldots,30$, the intersection lattice $L(\Ac_t)$ can be described by the following sequence of lists:
\begin{align*}
&\left[1, 2, 3, 4, 5, 6\right],\left[1, 7, 8, 9, 10, 11\right],\left[2, 7, 12, 13, 14, 15\right],\\
&\left[2, 8, 16, 17, 18, 19\right],\left[3, 7, 16, 20, 21, 22\right],\left[3, 8, 12, 23, 24, 25\right],\\
&\left[2, 9, 20, 23, 26, 27\right],\left[4, 7, 17, 24, 26, 28\right],\left[4, 9, 12, 18, 21, 29\right],\\
&\left[5, 10, 12, 17, 20, 30\right],\left[4, 8, 13, 22, 27, 30\right],\left[6, 8, 14, 20, 28, 29\right],\\
&\left[4, 11, 15, 19, 20, 25\right],
\end{align*}
for example the third list
encodes that (the projective points) $2$, $7$, $12$, $13$, $14$, $15$ lie on hyperplane number three.
From the intersection lattice we can compute
\[ \chi_{\Ac_t}(x) = (x-1)(x-6)^2, \]
and we see that $\Ac_t$ is not inductively free by Lemma \ref{strnotindfree}.

For any field extension $K/\QQ$ and each $\omega \in K$, we also have a corresponding arrangement
\[ \Ac_\omega:=\{ \ker_K \alpha(\omega) \mid \alpha\in R\} \]
in $K^3$.
It is easy to check that $L(\Ac_\omega)\ne L(\Ac_t)$ if and only if
\[ \omega \in Z := \left\{ -1,0,\frac{1}{2},1,2,\frac{1\pm \sqrt{-3}}{2} \right\}. \]
If $\omega\in \{0,1,\frac{1\pm \sqrt{-3}}{2}\}$ then $|\Ac_t|\ne|\Ac_\omega|$.
For $\omega\in \{-1,\frac{1}{2},2\}$ we have $|\Ac_t|=|\Ac_\omega|$, but the intersection lattices are different.
See Figure \ref{a13m1} for a picture in the real projective plane of one of the $\Ac_\omega$ with $\omega\notin Z$.

Moreover, using the algorithm of \cite{p-C10b} we get
\[ \Vc_\CC(L(\Ac_t)) = \{ \Ac_\omega \mid \omega \in \CC\backslash Z\}. \]
Thus the moduli space of $L(\Ac_t)$ is one dimensional. A short computation with Singular shows that every arrangement in $\Vc_\CC(L(\Ac_t))$ is free. Further, $\Ac_t$ is free but not recursively free.
It is remarkable that the arrangements $\Ac_\omega$, $\omega\in \{-1,\frac{1}{2},2\}$ are free as well, but their exponents are $\lmultiset 1,5,7 \rmultiset$.

The symmetry group of $L(\Ac_t)$ is
\[ \Aut(L(\Ac_t)) \cong \ZZ/3\ZZ \rtimes S_3. \]

\begin{figure}
\begin{center}
\setlength{\unitlength}{0.75pt}
\begin{picture}(400,400)(100,200)
\moveto(496.773982019981493284007282848,364.222912360003364857453221300)
\lineto(103.226017980018506715992717152,364.222912360003364857453221300)
\moveto(499.799899899874824737086828568,408.944271909999158785636694675)
\lineto(100.200100100125175262913171431,408.944271909999158785636694675)
\moveto(495.715111622386654550161466794,441.177604139103725326976197484)
\lineto(104.284888377613345449838533206,441.177604139103725326976197484)
\moveto(462.003080212687308662930982098,517.281720662691514734747508724)
\lineto(182.718279337308485265252491277,237.996919787312691337069017902)
\moveto(441.421356237309504880168872421,541.421356237309504880168872421)
\lineto(158.578643762690495119831127579,258.578643762690495119831127579)
\moveto(406.952750824954505690978417484,569.000322754056281424622386528)
\lineto(130.999677245943718575377613472,293.047249175045494309021582516)
\moveto(308.944271909999158785636694675,599.799899899874824737086828568)
\lineto(308.944271909999158785636694675,200.200100100125175262913171431)
\moveto(367.958188185589464486680994098,211.899801545739966944654699262)
\lineto(223.491767387609719016567995648,584.787689910687449561575785165)
\moveto(444.811903076327848709446111418,262.052500104524442500854566083)
\lineto(173.745865467501343672573169961,555.112518880487948495621622922)
\moveto(499.968602029388036590795160647,396.456244589107931398792724109)
\lineto(100.031397970611963409204839353,396.456244589107931398792724109)
\moveto(432.492660930138327285243171407,549.818873309244309090703667076)
\lineto(150.181126690755690909296332923,267.507339069861672714756828593)
\moveto(422.256045515541062845432718669,241.717154009343286710386751204)
\lineto(151.716113756179965018531360123,534.208379322715313821763695360)
\moveto(482.566108371663406313081719590,481.667717453263334783894740716)
\lineto(113.729449702885217465211784879,327.176363095420508928667332648)
\moveto(279.130032210001949593332228440,598.908130664496578018818014653)
\lineto(279.130032210001949593332228440,201.091869335503421981181985346)
\thinlines
\strokepath
\put(470,560){\Large $\infty$}
\end{picture}
\end{center}
\caption{An arrangement $A_\omega$ with $15$ hyperplanes.}
\end{figure}

\subsection{Arrangements with $15$ hyperplanes}

Now let $R\subseteq \ZZ[t]^3$ be the set
\begin{eqnarray*}
R &=& \{ (1,0,0),(1,1,0),(1,0,1),(1,1,1),(1,t,1),(0,1,0),(2,1,1),\\
&& (t+1,t,1),(t+1,1,1),(2t,t,1),(1,-t+1,1),\\
&& (-3t+1,t^2-3t+1,-t),(3t-1,t,t),\\ && (-3t+1,-t^2,-t),(3t-1,2t-1,t) \}.
\end{eqnarray*}
With the analogous notations $\Ac_t$, $\Ac_\omega$ and similar computations as in the example with $13$ hyperplanes, we get:
\begin{enumerate}
\item If $\omega\in \{0, 1, -1, \frac{1}{2}\}$ then $|\Ac_t|\ne|\Ac_\omega|$.
\item If $\omega\in \{\frac{3}{2}\pm \sqrt{2},(-1\pm \sqrt{5})/2\}$ then $|\Ac_t|=|\Ac_\omega|$, but the intersection lattices are different.
\item $\Vc_\CC(L(\Ac_t)) = \{ \Ac_\omega \mid \omega \in \CC\backslash Z\}$ for $$Z=\left\{0, 1, -1, \frac{1}{2},\frac{3}{2}\pm \sqrt{2},\frac{-1\pm \sqrt{5}}{2}\right\}.$$
\item The arrangement in $\Ac_t$ is free, but not recursively free with exponents $\lmultiset 1,7,7\rmultiset$.
\item If $\omega\in \{\frac{3}{2}\pm \sqrt{2},(-1\pm \sqrt{5})/2\}$ then $\Ac_\omega$ is free with exponents $\lmultiset 1,5,9\rmultiset$.
\item The moduli space of $L(\Ac_t)$ is one dimensional.
\item The symmetry group of $L(\Ac_t)$ is $\Aut(L(\Ac_t)) \cong \ZZ/2\ZZ \wr S_3$, thus isomorphic to the reflection group of type $B_3$.

\end{enumerate}

\def\cprime{$'$}
\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\providecommand{\MR}{\relax\ifhmode\unskip\space\fi MR }

\providecommand{\MRhref}[2]{
  \href{http://www.ams.org/mathscinet-getitem?mr=#1}{#2}
}
\providecommand{\href}[2]{#2}


TITLE: Strong law of large numbers implications
QUESTION [0 upvotes]: Let $S_n$ be the sum of i.i.d. components $X_i$ with $P(X_i= 0) = P(X_i = 1) = 1/2$. Then, according to the strong law of large numbers we have that $$ \frac{S_n}{n} \to 1/2 \quad a.s.$$
Can I follow that: Let $\epsilon > 0$. There exists a $n_0$ such that for all $n \geq n_0$: $$ \frac{n}{2} - \epsilon < S_n < \frac{n}{2} + \epsilon \quad a.s. \ $$ Or am I interpreting the SLLN incorrectly? Or, can I only infer a statement like $$
 \frac{n}{4} < S_n < \frac{3n}{4} \quad a.s. \quad ?$$

REPLY [1 votes]: The convergence delivered by the SLLN is point-wise, not uniform.    The central limit theorem tells us that deviations of $S_n$ from $n/2$ are typically of size $\pm\sqrt n$, so your first formula asks for the impossible. The law of the iterated logarithm tells us that   with probability $1$ we have
$$\limsup_{n\to\infty}\frac{S_n-n/2}{\sqrt{n\log\log n}}=1$$
and
$$\liminf_{n\to\infty}\frac{S_n-n/2}{\sqrt{n\log\log n}}=-1.$$
This shows your first formula cannot hold, and gives a way to prove your second.