TITLE: Set of polynomials with rational roots
QUESTION [1 upvotes]: Is the set of polynomials with rational roots a vector space?
The polynomial $p_i(x)=(x-{{a_i}/{b_i}})(q_i(x))$ is from that given set.
If $p_1(x) + p_2(x) = (x-{{a_1}/{b_1}})(q_1(x)) + (x-{{a_2}/{b_2}})(q_2(x))$ is the polynomial from that set, it is ok. Where $b_i$ can't be 0.
If $rp_1(x) = r(x-{{a_1}/{b_1}})(q_1(x))$ is the polynomial from that set, it is ok. Where $r$ is a scalar.
We are restricted that if those polynomials form a subspace, all of them must have rational roots.
Any suggestions how to find a contradiction? Thank you and sorry for my English.

REPLY [3 votes]: No. Both $x^2$ and $(x-1)^2$ have rational roots, but their sum $x^2+(x-1)^2$ does not (it doesn't have any real roots).


text:
\begin{document}

\maketitle

\section{Introduction}

Cumulative processes were initially introduced by Smith in 1955 \cite{Smith1955}. Idea of Smith’s construction of regenerative and cumulative processes was to create an opportunity to apply methods of analysis of sums of independent random variables to a wider class of sequences and processes. Smith proved the stability theorem for regenerative processes and LLN and CLT for cumulative processes. The concept of regeneration turned to be very popular in the queueing theory and was renovated after Smith’s work in a lot of ways. Markov-modulated processes, batch Markov-arrival processes   \cite{Asmussen,Neuts}, regenerative flows in \cite{LG}, cumulative processes as defined in \cite{GW} represent sub-classes of cumulative processes, introduced by Smith. Special definitions arose in order to find explicit formulae for characteristics of models. But as was shown already by Smith himself and later in studies \cite{LG,Thorisson} some classes of important theorems, like  stability conditions or diffusion approximations, may be proved under general assumptions.
Our conditions {\bf{(A)}} and {\bf{(B)}} below, taken together, are somewhat more restrictive than Smith's definition as we are tackling an almost sure approximation, but rather general and include the most part of examples in literature, e.g. those mentioned above.

Strong Gaussian approximation of random processes presents an important class of limit theorems (almost sure invariance principles), stemming from seminal results by Skorokhod and Strassen \cite{Strass}. While classical functional limit theorems establish the proximity of properly rescaled  random processes formed by partial sums to  standard ones (e.g. to the Wiener process) in distribution, strong functional limit theorems provide the ways to estimate the almost sure difference of those two types of random processes. For example, given a stationary sequence $ \{X_1,X_2,\ldots\}$ of centered random variables and denoting $S_n=X_1+\ldots+X_n$ for $n\geq 1,$ a strong invariance principle (almost sure invariance principle) would typically state that the sequence can be initially defined on a rich enough probability space so that for some Wiener process $\{W_t,t
\geq 0\}$ and some specified $\sigma^2>0$ (meaning the asymptotic variance of $S_n$) one has
\begin{equation}\label{intr1}
S_n - \sigma W_n = O(f(n)) \mbox{ a.s.,}
\end{equation}
$f=\{f(n),n\geq 1\}$ being some non-random increasing sequence in $n\geq 1$. For \eqref{intr1} to be non-trivial (e.g. allowing to deduce the law of the iterated logarithm for $S_n$) $r$ should satisfy $f(n)=o(\sqrt{n\log\log n})$ which was Strassen's statement. Strong Gaussian approximation allows to deduce almost sure limit theorems, such as laws of the iterated logarithm, by using corresponding statements for approximating Gaussian processes. It has been shown that strong invariance principles  have important applications   to establishment of Darling-Erd\H{o}s type theorems and integral tests for upper and lower functions \cite{StrassBerk,DieEin}.

One can go further and analyze the rate of convergence in \eqref{intr1}, e.g. obtain an estimate of order $f(n)=n^{1/2-\eps}$ with some nonrandom $\eps>0$.
  Fundamental results by Koml\'{o}s, Major and Tusn\'{a}dy \cite{KMT,KMT2,Maj} state that the rates $f(n)=\log n$ for i.i.d. sequences with finite exponential moments and $f(n)=n^{1/p}$ if they possess only a moment of order $p>2$ are true and non-improvable. These results were achieved by developing the quantile transformation method. These authors give also a more delicate estimate of the rate of Gaussian approximation in terms of probabilistic maximal inequalities. Namely, in the case of finite exponential moments one has
  \begin{equation}\label{intr2}
\p\left(\sup_{k\leq n}|S_k - \sigma W_k| \geq C\log n+x\right)\leq Ae^{-Bx}
\end{equation}
for some non-random $A,B,C>0$ and all $n\geq 1,x\geq 0,$ and similar bounds exist in case of lower moment restrictions. Such bounds imply the convergence results of type \eqref{intr1}.

The power and beauty of almost sure (strong) invariance principles prompted extensive research for such results for many classes of random systems. Vector-valued random processes were studied by many authors (\cite{GZ} and references therein), in particular, Zaitsev \cite{Zait} extended \eqref{intr2}  to sums of independent random vectors.  Berkes and Morrow  \cite{BerMor} initiated the exploration of strong approximation for random fields, establishing the rate $f(n)=(n_1\ldots n_d)^{1/2-\eps}$ (here partial sums are indexed by multiindices $n=(n_1,\ldots,n_d)\in\mathbb{N}^d$). For renewal processes, exact rates of convergence in the sense of Koml\'{o}s-Major-Tusn\'{a}dy were established by Cs\"{o}rg\H{o},
Horv\'{a}th and Steinebach \cite{CHS} and are in agreement with what one has in the i.i.d. setup (in this case, moment conditions are imposed on the innovations). However for systems of dependent random variables, while there have been many results proved (for martingales \cite{StrassBerk,Eberl,Mermart}, associated random systems  \cite{BSh},  mixing families \cite{PhiStout,Shao,Rio,BerLiuWu} and others), one can rarely attain the optimal convergence rate.  In particular, in most cases methods based on the Skorokhod embedding and the approximation of partial sums by those of independent families do not provide the convergence faster that $O(n^{1/4}),$ which is not optimal in case moments greater than fourth exist. However this border was broken in the works by Berkes, Liu and Wu \cite{BerLiuWu} for processes driven by regular enough Bernoulli shifts, by Merlev${\rm\grave{e}}$de and Rio \cite{MerRio} for functionals of Markov chains and by Cuny, Dedecker, Korepanov, Merlev${\rm\grave{e}}$de \cite{CDKM} for mixing dynamical systems.

  This paper is devoted to optimal logarithmic rates of convergence in almost sure invariance principle for multivariate cumulative processes.
  Our goal is to obtain exponential probabilistic inequalities  of Koml\'{o}s-Major-Tusn\'{a}dy type \eqref{intr2}. To establish the strong Gaussian approximation exact rate under exponential moment restrictions  we follow the approach of Merlev${\rm\grave{e}}$de and Rio \cite{MerRio} to geometrically ergodic Markov chains. Their approach is based on the approximation by an auxiliary process formed by a composition of a Wiener and Poisson ones (Lemma 2.4 \cite{MerRio}). Besides,  the Zaitsev  strong approximation technique \cite{Zait} is applied. Merlev${\rm\grave{e}}$de and Rio study the sequence of partial sums $S_n=\sum_{i=1}^n f(\xi_j),$ $n\geq 1,$ with a bounded Borel functional $f$ and $\{\xi_n,n\geq 1\}$ being a geometrically ergodic Markov chain. However their Lemma 2.4 is a powerful tool of its independent interest.   In particular, we were able to apply it together with Zaitsev construction to analysis of cumulative processes. Note that random sums $S_n$ studied in \cite{MerRio} present a partial case of processes under consideration, as can be seen by taking the Markov chain returns to zero as points of regeneration.
  Besides, we allow vector-valued processes and dispense with the boundedness condition on the random summands. In the concluding part of the paper we give two corollaries about two important subclasses of cumulative processes. The first one deals with stopped sums. Cs\"{o}rg\H{o}, Deheuvels and Horv\'{a}th \cite{Deheu} obtained the optimal rate in strong invariance principle for such sums  in case when the indexing process is independent from summands, while Horv\'{a}th \cite{Hor} studied general case and got the convergence rate of order $O(n^{1/4}(\log n)^{1/2}(\log\log n)^{1/4})$. We consider stopped sums as in \cite{Hor} and get the logarithmic rate of convergence as a consequence of our main theorem. The second corollary concerns birth and death processes arising in queueing theory \cite{KarlinMc}.

 In this paper
 we study a $\mathbb{R}^d-$valued random process $S=\{S(t),t\geq 0\} = \{(S_1(t),\ldots,S_d(t)),t\geq 0\}$ which is assumed to be separable. For a vector $z\in\mathbb{R}^d$, by $|z|$ we denote the maximal norm. The principal condition we will require is:

 \begin{cond1}[{\textbf{A}}]
 There exists an a.s. increasing random sequence $\{T_k, k\geq 0\}$ such that $T_0=0$ and random elements
 $$ \Bigl\{\bigl(T_j-T_{j-1}, S(T_{j-1}+t) - S(T_{j-1}), t\in(0,T_j-T_{j-1}]  \bigr) ,j\geq 1\Bigr\}$$
 are i.i.d.
 \end{cond1}

 We need the following notation.
\begin{itemize}
\item $\tau_k = T_k - T_{k-1},\;k\geq 1;$
\item $\xi_k =(\xi_{k1},\ldots,\xi_{kd})= S(T_k) - S(T_{k-1}),\; k\geq 1;$
\item  $m(t) = \max\limits\{k\in\mathbb{Z}_+: T_k \leq t\},\; t\geq 0$, i.e. $m=\{m(t),t\geq 0\}$ is the renewal process built by sequence $\{\tau_k,k\geq 1\}$;
\item $\eta_k = \max\limits_{0< t \leq T_k-T_{k-1}}|S(T_{k-1}+t) - S(T_{k-1})|,\;k\geq 1;$
\item $\mu=\e \tau_1$, $\varkappa = \mu^{-1}\e \xi_1  ;$
\item $\sigma^2 =   \mu^{-1}(\di(\xi_1) - 2 cov(\xi_1,\tau_1)\varkappa^T + \varkappa \varkappa^T \di(\tau_1)),$
 \end{itemize}
 where $cov(\xi_1,\tau_1) := (cov(\xi_{11},\tau_1),\ldots, cov(\xi_{1d},\tau_1) ).$ We will write $\sigma$ for the usual square root of the matrix $\sigma^2.$

 Next condition restricts the tails of $\eta$ and $\tau$ and is a typical requirement to ensure the logarithmic rate of convergence in the strong invariance principle.
  \begin{cond1}[{\textbf{B}}]
There is $s>0$ such that $\e \exp\{s \tau_1\}<\infty$ and $\e\exp\{s \eta_1\}<\infty$.
 \end{cond1}
 Condition $\mathbf{(B)}$ implies that the exponential moments  of $\xi_1$ are finite in some neighbourhood of the origin.

\section{Main result}

\begin{thm1}\label{TheoremMain}
Suppose that $\{S(t),t\geq 0\}$ satisfies conditions {\bf(A)} and {\bf (B)}.  Then one can redefine it on a probability space $(\Omega,\mathcal{F},\mathsf{P})$ supporting also a standard $d$-dimensional Wiener process $\{W_t,t\geq 0\}$ such that for some positive constants $a,b,c,$ any $x>0$ and  $t\geq 1$ one has
\begin{equation}\label{1}
\p\left(\sup_{u\leq t}\bigl|S(u) - \varkappa u - \sigma W_u\bigr| \geq c\log t + x \right) \leq a e^{-b x} .
\end{equation}
\end{thm1}
Standard estimate shows that \eqref{1} implies the strong invariance principle, i.e. the relation
$$S(t) - \varkappa t - \sigma W_t = O(\log t)\mbox{ when }t\to\infty,\mbox{ a.s}. $$

\begin{proof} Without loss of generality we assume  $\di (\tau_1)>0$ as otherwise the statement would be easily derived from the Koml\'{o}s-Major-Tusn\'{a}dy theorem for i.i.d. summands \cite[Theorem 1]{KMT2}.
We will use triplets of positive constants $(a_i,b_i,c_i),\,i\geq 1,$ when we want to write an auxiliary estimate of the type \eqref{1}.

Note that we always can confine ourselves to the case $t\geq M,$ with a fixed number $M>1$. For if theorem is proved for that case, then given $t\in[1,M),$ we will be able to write
$$\p\left(\sup_{u\leq t}\bigl|S(u) - \varkappa u - \sigma W_u\bigr| \geq c\log t + x \right) \leq \p\left(\sup_{u\leq M}\bigl|S(u) - \varkappa u - \sigma W_u\bigr| \geq c  + x +c(\log t -\log M) \right)\leq  $$
$$\leq \begin{cases}ae^{-b(x-c\log M)},& x\geq c\log M, \\e^{c\log M-x},& 0< x \leq c\log M.\end{cases} $$
Using this remark we will consider only $t\geq e$ in what follows.

Write
\begin{equation}\label{greeks}
\beta = \bigl(\di (\tau_1)\bigr)^{-1} {cov(\xi_1, \tau_1)},\; v^2 = \di(\xi_1 - \beta \tau_1),\;
\gamma = \frac{\di(\tau_1)}{\mu}, \;\lambda = \frac{\mu^2 }{\di(\tau_1)},\;\alpha = \beta - \varkappa.
\end{equation}

Using the remark above, we will consider only $t\geq e.$
Note that the choice of $\beta$ implies that $$cov(\xi_{ki} - \beta_i \tau_k,\tau_k)=0, \;i=1,\ldots,d. $$

Applying Zaitsev  \cite[Theorem 1.3]{Zait} to a $(d+1)$-dimensional sequence $\{(\xi_k - \beta \tau_k +\alpha\mu,\tau_k-\mu), k\geq 1\}$ we can infer (redefining the initial process on a larger probability space if necessary) that there exist two independent Wiener processes $\{B_t,t\geq 0\},\{\widetilde{B}_t,t\geq 0\} $, the former being $d-$dimensional, such that for any pair $(t,x)\in [e,\infty)\times [0,\infty)$

\begin{equation}\label{2}
\p\left(\sup_{k\leq t}\bigl|S(T_k) - k\varkappa \mu - \beta(T_k - k\mu) - vB_k \bigr| \geq c_1\log t + x \right) \leq a_1 e^{-b_1 x} ,
\end{equation}
\begin{equation}\label{3}
\p\left(\sup_{k\leq t}\bigl|T_k - k\mu  - \sqrt{\di(\tau_1)}\widetilde{B}_k \bigr| \geq c_1\log t + x \right) \leq a_1 e^{-b_1 x} ,
\end{equation}
with some $a_1,b_1,c_1>0.$

Arguing as before  (2.50) in Merlev${\rm\grave{e}}$de and Rio \cite{MerRio}, we can construct also a Poisson process $\{N(t),t\geq 0\}$ with parameter $\lambda$, measurable with respect to the $\sigma-$algebra generated by $\widetilde{B}$ and such that the following relations hold:

\begin{equation}\label{4a}
\p\left(\sup_{u\leq t}\bigl|\gamma N_u - u\mu- \sqrt{\di(\tau_1)}\widetilde{B}_u \bigr| \geq c_2\log t + x \right) \leq a_2 e^{-b_2 x} .
\end{equation}

\begin{equation}\label{5}
\p\left(\sup_{u\leq t}\bigl|\gamma N_u - T_{[u]} \bigr| \geq c_2\log t + x \right) \leq a_2 e^{-b_2 x}
\end{equation}
with some $a_2,b_2,c_2>0.$

Further, we denote now $y(u) = N^{-1}(u/\gamma)$. Then, process $m$ is the inverse of process $T$ and $y$ is the inverse of   $\gamma N$. Therefore in view of the paper of  Cs\"{o}rg\H{o}, Horv\'{a}th and Steinebach \cite{CHS} and particular Corollary 4.2 there, and of \eqref{3}--\eqref{4a}, one can construct (enlarging the probability space if necessary) a standard Wiener process $\widetilde{W}=\{\widetilde{W}_t,t\geq 0\}$ such that the following statements are simultaneously true:

\begin{equation}
\label{deheuvels}
\p\left(\sup_{u\leq t}\left|m(u) - \frac{u}{\mu} - \frac{1}{\lambda\sqrt{\gamma}}\widetilde{W}_u\right|\geq c_3\log t + x\right)  \leq a_3 e^{-b_3 x},
\end{equation}

\begin{equation}\label{6}
\p\left(\sup_{u\leq t}\left| y(u)-  \frac{u}{\mu} - \frac{1}{\lambda\sqrt{\gamma}}\widetilde{W}_u \right| \geq c_3\log t + x \right) \leq a_3 e^{-b_3 x}
\end{equation}
and
\begin{equation}\label{m-y}
\p\left(\sup_{u\leq t}  |m(u) - {y(u)}| \geq c_3\log t +
  x \right) \leq a_3e^{  - b_3 x},
 \end{equation}
 with some $a_3,b_3,c_3>0.$ Moreover, process $\widetilde{W}$ is measurable with respect to a $\sigma$-algebra generated by $\widetilde{B}$ plus some random element $V$ independent from all ones considered above.

 \begin{lm1}\label{estimate_for_m}
 For any $z\geq 0$ and $t\geq e$ one has
 $$\p\left(\left|m(t) - \frac{t}{\mu} - \frac{1}{\lambda\sqrt{\gamma}}\widetilde{W}_t\right|> z\right)  \leq \max\{a_3,1\} \exp\Bigl\{\max\{b_3,1\}c_3\log t   -\min\{b_3,1\}z \Bigr\}. $$
 \end{lm1}

 \begin{proof}
 Consider separately the cases $z\geq c_3\log t$ and $z<c_3\log t,$ and use \eqref{deheuvels} for the first one.
 \end{proof}

\begin{lm1}\label{Lemma24} One can construct a standard $d$-dimensional Wiener process $W^*=\{W^*_t,t\geq 0\}$ such that
\begin{equation}\label{7}\p\left(\sup_{k\leq t}\left|  B_k - \frac{W^*_{N(k)}}{\sqrt{\lambda}}   \right| \geq c_4\log t + x \right) \leq a_4 e^{-b_4 x}  \end{equation}
with some $a_4,b_4,c_4>0$ and all $t\geq e,\,x> 0;$ this process is determined by the process $B$ plus some random element $V^*$ which is independent from all other random elements considered above. In particular, $W^*$  is independent from $\widetilde{B}$ and $N$.
\end{lm1}

\begin{proof} This is a multi-dimensional version of Lemma 2.4 in \cite{MerRio} and is proved along the lines of that lemma, with the following change. One introduces mutually independent Gaussian random vectors
$$Y_{j,k} =2B_{(k+1/2)2^j} -B_{(k+1)2^j}-B_{k2^j},\,j\in\mathbb{Z},k\geq 0 $$
and random functions
$$a_{j,k}=N((k+1/2)2^j) -N(k2^j),\;b_{j,k}=N((k+1)2^j) -N((k+1/2)2^j),$$
$$f_{j,k}=\frac{b_{j,k}I\{(N(k2^j) ,N((k+1/2)2^j)]\}   -a_{j,k} I\{(N((k+1/2)2^j) ,N((k+1)2^j)]\} }{a_{j,k}b_{j,k}(a_{j,k}+b_{j,k})} ,\,j\in\mathbb{Z},k\geq 0$$
where the fraction with $0$ at the denominator is treated as zero. Then, using that $\{f_{j,k}\}_{j,k}$ conditionally on $N$ is an orthonormal family plus some set of identically zero functions, one shows that random vectors
$$W_l=\sum_{j\in\mathbb{Z}}\sum_{k=0}^{\infty}Y_{j,k}\int_0^l f_{j,k}(t)dt ,\,l\geq 0, $$
are jointly Gaussian and $\e W_lW_m^T = \min\{l,m\}I_d $ for $l,m\geq 0,$ where $I_d$ is the identity matrix. The rest of the proof goes like in \cite{MerRio}.
\end{proof}

 By construction,  standard Wiener processes $\{\widetilde{W}_t,t\geq 0\}, \{W^*_t,t\geq 0\}$, the latter being $d$-dimensional,  are independent.

\begin{lm1}\label{nonint} In  $\eqref{7}$ one can change the supremum to be over all real $u\in[0,t]$ $($changing $a_4,b_4,c_4$ if necessary$).$
\end{lm1}

\begin{proof}
For a standard scalar Wiener process $Z=\{Z_t,t\geq 0\}$ one has
$$\p\left(\sup_{u\leq t}|Z_u-Z_{[u]}| \geq  \log t +x \right)\leq (t+1)\p\left(\sup_{u\leq 1}|Z_u| \geq \log t + x\right)\leq $$
\begin{equation}\label{Levy}\leq 4(t+1)\exp\left\{-\log^2t/2 - x\log t \right\} \leq    10e^{-x} \end{equation}
as $t\geq e.$
Finally, if $Z$ is independent from the Poisson process $N,$ for $x\geq 1$ we may write
$$\p\left(\sup_{u\leq t}|Z_{N(u)}-Z_{N([u])}| \geq  \log t +x \right)
\leq \sum_{k=0}^{[t]}\p\left( \sup_{u\leq 1}|Z_{N(k+u)}-Z_{N(k)}| \geq  \log t +x \right) \leq $$ $$ \leq (t+1)\p\left(N(1) >\frac{1}{2}(\log t + x)\right)+  (t+1)\p\left( \sup_{u\leq (\log t+x)/2}|Z_{u}| \geq  \log t +x \right) \leq  $$
$$\leq \frac{t+1}{t}e^{-x}\e e^{2N(1)} + (t+1)\p\left( \sup_{u\leq 1}|Z_{u}| \geq  \sqrt{2(\log t +x)} \right)\leq 2e^{\lambda (e^2-1)-x} + 8e^{-x}.  $$
\end{proof}

Let $W^{\circ}=\{W^{\circ}_t,t\geq 0\}$ be a standard $d$-dimensional Wiener process independent from $(W^*,\widetilde{W}).$ Define a Gaussian   process
\begin{equation}\label{4}
W_t = \sigma^{+}\left( \lambda^{-1/2}{v} W^*_{t/\gamma}  - \lambda^{-1}\gamma^{-1/2} \mu \alpha  \widetilde{W}_{t} \right) + (I_d - \sigma^{+} \sigma)W^{\circ}_t, \end{equation}
where $v$ is the square root of the covariance matrix $v^2,$ and $\sigma^+$ stands for the Moore-Penrose pseudo-inverse matrix to $\sigma.$

\begin{lm1}\label{Wiener}
$W$ is a standard $d$-dimensional Wiener process.
\end{lm1}

\begin{proof} It suffices to compute the covariance matrix of $W_1,$ which is equal to
$$\frac{1}{\mu}\sigma^{+}\Bigl(\di(\xi_1-\beta\tau_1) + \di(\tau_1(\beta-\varkappa))\Bigr)\sigma^{+} + I_d - \sigma^{+} \sigma ,$$
and since the components of the random vectors whose covariance matrices are inside the brackets are mutually uncorrelated, using the definition of $\sigma^2$ we infer that $\di W_1=I_d.$
\end{proof}

Denoting $y = y(u) = N^{-1}(u/\gamma) $  we write, for $u\geq 0,$
$$S(u) - \varkappa u -\sigma W_u = S(u)   - \varkappa u - \sigma\sigma^+\frac{v}{\sqrt{\lambda}}W^*_{u/\gamma} + \sigma\sigma^+\alpha \frac{\mu}{\lambda\sqrt{\gamma}}\widetilde{W}_{u} =$$
$$=S(u)   - \varkappa u - \frac{v}{\sqrt{\lambda}}W^*_{u/\gamma}  -\alpha \mu \left(N^{-1}(u/\gamma) - \frac{u}{\lambda \gamma} - \frac{\widetilde{W}_{u }}{\lambda\sqrt{\gamma}}\right) + \alpha\mu\left(N^{-1}(u/\gamma) - \frac{u}{\lambda \gamma} \right) =$$
$$= (S(u) - S(T_{m(u)}) )+   (S(T_{m(u)}) - S(T_{[y]})) +\left(S(T_{[y]}) -\beta T_{[y]}   + \alpha \mu y - v B_y\right)+ $$ $$+\beta  (T_{[y]} - \gamma N(y)) - \alpha \mu \left(y - \frac{u}{\lambda \gamma} - \frac{\widetilde{W}_{u }}{\lambda\sqrt{\gamma}}\right)  + $$ $$+v\left(B_y - \lambda^{-1/2}W^*_{N(y)}\right)+\lambda^{-1/2}v\left(  W^*_{N(y)}-  W^*_{u/\gamma}\right)+\beta(\gamma[u/\gamma]+\gamma-u)  =:\sum_{q=1}^8 \Phi_q(u).  $$
We took into account that $\sigma\sigma^+ v = v $ and  $\sigma\sigma^+ \alpha=\alpha. $
Pick $s_1\in(0,s)$ and  $r>0$ such that \begin{equation}\label{select_r} \e \exp\{s_1|\xi_1 - \varkappa \tau_1|\}<\infty,\; r\log \e \exp\{s_1|\xi_1 - \varkappa \tau_1|\} < \frac{s_1}{6}.\end{equation}

From now till Lemma \ref{LD}, we always consider pairs $(t,x)$ such that
\begin{equation}\label{pair}x \leq \frac{3 t}{\mu r}.\end{equation}
\begin{lm1}\label{Poisson}
We have $$\p\left(N^{-1}(t/\gamma)\geq 2t/\mu\right) \leq 2e^{  - \lambda (1-2/e)  r x/3},$$
for $(t,x)$ satisfying $\eqref{pair}.$
\end{lm1}

\begin{proof} $N^{-1}(t/\gamma)$ is the sum of $[t/\gamma]+1$ i.i.d. exponential random variables with parameter $\lambda,$ hence
$$\p(N^{-1}(  t/\gamma)\geq 2t/\mu)\leq  e^{-t/\gamma} 2^{[t/\gamma]+1},$$
 and it remains to use the inequality \eqref{pair} and the equality $\mu=\lambda\gamma$.
\end{proof}

 \begin{lm1}\label{MerlevedeRio}
There are  $a_5,b_5,c_5>0$ such that for $q=3,\ldots,8$ we have $$\p\left(\sup_{u\leq t}   |\Phi_q(u)|I\{N^{-1}(t/\gamma)\leq 2t/\mu \} \geq c_5\log t + x \right) \leq a_5e^{  - b_5 x},$$
 for all $(t,x)$ satisfying $\eqref{pair}$.
\end{lm1}

\begin{proof}
For $q=3$ one should apply \eqref{2} and \eqref{Levy}.
For $q=4,5,6$ the corresponding statements directly follow from \eqref{5}, \eqref{6}, \eqref{7} respectively with the help of Lemma \ref{nonint}.
For $ q=7$, using that $|u/\gamma - N(y)|\leq 1,$ one has
$$\p\left(\sup_{u\leq t}|W^*_{N(y)}-  W^*_{u/\gamma}|>3d\log t+x\right)\leq
(t/\gamma +1)\p\Bigl(\sup_{u\leq 1}|B_u|>\log t + x/3d\Bigr)\leq $$ $$\leq  4(t/\gamma +1)\exp\{-\log^2 t -(x\log t)/3d\}   \leq 4(\gamma^{-1}+e^{-1})e^{1/2-x/3d}. $$
Finally, for $q=8$ the statement is trivial as $\Phi_8$ is uniformly bounded.
\end{proof}

 \begin{lm1}\label{Phi1}
There are  $a_6,b_6,c_6>0$ such that   $$\p\left(\sup_{u\leq t}   |\Phi_1(u)| \geq c_6\log t + x \right) \leq a_6e^{  - b_6 x},$$
 for all $(t,x)$ satisfying $\eqref{pair}$.
\end{lm1}

\begin{proof}
Note that $\sup_{u\leq t}|\Phi_1(u)|\leq \max_{k\leq m(t)+1}\eta_k,$ since $m(u)$ is the last renewal point of $T$ happening before $u,\,u\leq t.$ Consequently, for a fixed $c_6>0$ we have
$$\p\left(\sup_{u\leq t}|\Phi_1(u)|\geq c_6\log t + x\right)\leq \p\left(m(t) >\frac{2t}{\mu}\right) +\p\left(\max_{k\leq 2t/\mu+1}\eta_k > c_6\log t + x\right)=:\Phi_{1,1}+\Phi_{1,2}. $$
Using Lemma \ref{estimate_for_m} and assuming $a_3\geq 1,\,b_3\leq 1$  we get
$$\Phi_{1,1} \leq \p\left(m(t) - \frac{t}{\mu} - \frac{1}{\lambda\sqrt{\gamma}} \widetilde{W}_t >\frac{t}{2\mu}\right) + \p\left(\frac{\widetilde{W}_t}{\lambda\sqrt{\gamma}}>\frac{t}{2\mu}\right)  \leq a_3\exp\left\{c_3\log t - b_3\frac{t}{2\mu}\right\} + e^{-t/(8\gamma)} \leq $$ $$\leq
a_3\left(\frac{4\mu c_3}{b_3e}\right)^{c_3}e^{-b_3 t/(4\mu) } + e^{-x \lambda r/24}\leq a_3\left(\frac{4\mu c_3}{b_3e}\right)^{c_3}e^{-b_3 x  r/12 } + e^{-x \lambda r/24}. $$
Also,
$$\Phi_{1,2} \leq \frac{2t+\mu}{\mu}\exp\{-c_6 s_1 \log t  -s_1 x \}\e\exp\{s_1 \eta_1\}\leq \frac{2+\mu}{\mu}\e\exp\{s_1 \eta_1\}e^{-s_1 x} $$
 provided that $c_6$ is so large that $c_6 s_1 > 1.$
\end{proof}

To handle $\Phi_2$   we need a series of  auxiliary lemmas. The first of them is a modification of the Lemma 1 in Cs\"{o}rg\H{o} and Steinebach \cite{CS}.

\begin{lm1}\label{CsorgoSteinebach}
Suppose that $X_1,X_2,\ldots$ are i.i.d. centered random variables such that $\e \exp\{s X_1\}<\infty$ for some $s>0,$ and let $Q_n=\sum_{j=1}^n X_j$ $(Q_0=0).$ Then for any $L>0$ there exist $\delta = \delta(L),a_7,b_7,c_7>0$ $($which depend on $L,\delta$ and the distribution of $X_1)$ such that for any $n\in\mathbb{N}$ and all $x\geq 0$ one has
$$ \p\left(\max_{j\leq n}\max_{k\leq L\log n +\delta x} (Q_{j+k} - Q_j)\geq c_7 \log n + x\right) \leq  a_7e^{-b_7 x}.$$
\end{lm1}

\begin{proof} Clearly we can consider only non-constant distribution of $X_1.$ The probability under consideration is not greater than
$$(n+1)\sum_{j=1}^{[L\log n+\delta x]}\p(Q_j \geq c_7 \log n + x)\leq (n+1)\exp\{-sx - c_7s\log n\}\sum_{j=1}^{[L\log n+\delta x]}\e\exp\left\{ sQ_j \right\}\leq  $$  $$\leq (n+1)\exp\{-sx - c_7s\log n\}\frac{\varphi(s)}{\varphi(s)-1}\varphi(s)^{L\log n+\delta x}  \leq $$ $$\leq (n+1)\frac{\varphi(s)}{\varphi(s)-1} \exp\Bigl\{-sx - c_7s\log n + L(\log \varphi(s))\log n + (\log \varphi(s))\delta x  \Bigr\} , $$
where $\varphi(s)=\e \exp\{s X_1\}> 1.$ It   remains to take $c_7$ and $\delta$ so that inequalities  $c_7 s > L\log \varphi(s) + 1$ and $\delta(\log \varphi(s))<s$ are ensured.
\end{proof}

 \begin{lm1}\label{Phi2}
There are  $a_8,b_8,c_8>0$ such that   $$\p\left(\sup_{u\leq t}  |\Phi_2(u)| \geq c_8\log t +
  x \right) \leq a_8e^{  - b_8 x},$$
 for all $(t,x)$ satisfying $\eqref{pair}$.
\end{lm1}

\begin{proof} Clearly we can consider only one coordinate of $S,$ say the first one. Also, using the remark before \eqref{greeks}, we can consider only $t\geq e\max\{1,\mu/2\}.$
Write, for $L>0$ and $\delta>0,$
$$\widetilde{L} := \frac{L}{2(1+\max\{0,\log \mu/2\})}, $$
$$\p\left( \sup_{u\leq t}|S_1(T_{m(u)}) - S_1(T_{[y]})|\geq  c_8\log t + x \right)\leq \p\left(N^{-1}(t/\gamma)>2t/\mu\right) + $$ $$+\p\left(\sup_{u\leq t}|m(u) - y(u)|> \widetilde{L}\log t + \delta x-1\right)+
\p\left(\sup_{\substack{n\leq 2t/\mu\\ k\leq \widetilde{L}\log t +\delta x}}  |S_1(T_{n+k}) - S_1(T_n)|\geq  c_8\log t + x\right)\leq $$ $$\leq\p\left(N^{-1}(t/\gamma)>2t/\mu\right)+
\p\left(\sup_{u\leq t}|m(u) - y(u)|> (\widetilde{L}-1)\log t + \delta x\right)+$$
$$+\p\left(\sup_{n\leq 2t/\mu}\sup_{k\leq  {L}\log [2t/\mu] +\delta x}  |S_1(T_{n+k}) - S_1(T_n)|\geq  c_8\log t + x\right) =:\sum_{q=1}^3  J_q,$$
where we have used that $2\log [z]\geq \log z$ if $z\geq e.$

Suppose that $L$ has been chosen to ensure  $\widetilde{L}\geq c_3+1 $ where $c_3$ is like in \eqref{m-y}, and that the numbers $\delta=\delta(L),a_7,b_7,c_7$ are provided by Lemma \ref{CsorgoSteinebach},
applied when $X_1$ has the  distribution of $\xi_{11}$. Then by Lemma \ref{CsorgoSteinebach} we see that
$J_3 \leq a_7 e^{-b_7x}  $
provided that $c_{8}$ is so large that $c_{8}\log t \geq c_7\log  (2t/\mu)$   for all $t$ considered.
To prove the statement of the lemma it remains to notice that by Lemma \ref{Poisson} and the relation \eqref{m-y} one has
$$J_1+J_2 \leq 2 e^{  - \lambda (1-2/e)   r x/3}+a_3e^{  - b_3 \delta x}. $$
\end{proof}

Consider now the case when $x $ lies in a domain of large deviations.

\begin{lm1}\label{LD} The relation $\eqref{1}$ holds for all $x > 3t /(\mu r).$
\end{lm1}

\begin{proof} First, by standard properties of Brownian motion one has
$$\p\left(\sup_{u\leq t}|W_u| > \frac{x}{2}\right)\leq 4de^{-3x/(8\mu r)} $$
for any $x$ provided that the pair $(x,t)$ satisfies Lemma's condition.
 Next, write
$$\p\left(\sup_{u\leq t}|S(u) - \varkappa u| > \frac{x}{2}\right)\leq \p\left(\sup_{k\leq m(t)}|S(T_k) - \varkappa T_k| > \frac{x}{6}\right) + $$ $$+\p\left(\sup_{u\leq t}|S(T_{m(u)}) - S(u)| > \frac{x}{6}\right) + \p\left(\sup_{u\leq t}|\varkappa||T_{m(u)} - u| > \frac{x}{6}\right) \leq $$ $$ \leq
\p\left(\sup_{k\leq m(t)}|S(T_k) - \varkappa T_k| > \frac{x}{6}\right) + \p\left(\sup_{k\leq m(t)+1}\eta_{k} > \frac{x}{6}\right) + \p\left(\sup_{k\leq m(t)+1}\tau_{k} > \frac{x}{6|\varkappa|}\right)\leq
$$
$$\leq 3\p(m(t) > rx) + \p\left(\sup_{k\leq rx}|S(T_k) - \varkappa T_k| > \frac{x}{6}\right) + \p\left(\sup_{k\leq rx+1}\eta_k > \frac{x}{6}\right) + \p\left(\sup_{k\leq rx+1}\tau_k > \frac{x}{6|\varkappa|}\right) =\sum_{q=1}^4 R_q,
$$
By \eqref{deheuvels} and Lemma \ref{estimate_for_m}, assuming without loss of generality that $a_3\geq 1,b_3\leq 1,$ one has
$$\frac{R_1}{3} \leq \p\left(m(t) - \frac{t}{\mu} - \frac{1}{\lambda\sqrt{\gamma}}\widetilde{W}_t>\frac{rx}{2}\right)
+  \p\left( \frac{t}{\mu}  +\frac{\widetilde{W}_t}{\lambda \sqrt{\gamma}}>\frac{rx}{2}\right) \leq  a_3\exp\left\{c_3\log \frac{x\mu r}{3} - b_3\frac{rx}{2}\right\} + $$ $$+ \p\left( \frac{\widetilde{W}_t}{\lambda \sqrt{\gamma}}>r\frac{x}{6}\right)\leq  a_3\left(\frac{4\mu c_3}{3be}\right)^{c_3}e^{-b_3 rx/4} +  e^{-r^2x^2\lambda^2\gamma/(72  t)}\leq a_3\left(\frac{4\mu c_3}{3be}\right)^{c_3}e^{-b_3 rx/4} +  e^{-\lambda rx/24 } $$
for any $t\geq 1,x\geq 0$ if $x>3t/(\mu r).$

To estimate $R_2,$ by Doob's inequality for non-negative submartingales we get
$$R_2 \leq  \sum_{j=1}^d \p\left(\sup_{k\leq rx}\exp\{s_1(S_j(T_k) - \varkappa_j T_k)\} > e^{s_1 {x}/{6}}\right)
+ \sum_{j=1}^d\p\left(\sup_{k\leq rx}\exp\{s_1(\varkappa_j T_k - S_j(T_k) )\} > e^{s_1{x}/{6}}\right)
 \leq $$
 \begin{equation}\label{R2}\leq  e^{-s_1   {x}/{6}}\sum_{j=1}^d\left(\e  \exp\{s_1(S_j(T_{[rx] }) - \varkappa_j T_{[rx] })\}  +   \e  \exp\{s_1( \varkappa_j T_{[rx] } - S_j(T_{[rx] }) )\} \right) \leq \end{equation} $$\leq 2d \exp\left\{-s_1  \frac{x}{6}      +   [rx] \log \e\exp\{s_1|\xi_1-\varkappa\tau_1|\} \right\}  \leq 2d e^{-qx}   $$
where $q:=s_1/6-r \log \e\exp\{s_1|\xi_1-\varkappa\tau_1|\}>0$ by \eqref{select_r}.
Now we estimate $R_{3}$ (and then $R_{4}$ is estimated analogously). From \eqref{select_r} it is seen that we can assume $r<s/12,$ in which case we have
$$R_{3}=\p\left(\sup_{k\leq rx+1}\eta_k > \frac{x}{6}\right)   \leq (rx+1) \p\left(\eta_1 > \frac{x}{6}\right) \leq (rx+1)e^{-s {x}/{6}}\e e^{s\eta_1}  \leq    \e e^{s\eta_1}e^{-sx/12}  . $$
\end{proof}

Theorem now follows from Lemmas \ref{Poisson}, \ref{MerlevedeRio}, \ref{Phi1}, \ref{Phi2}, \ref{LD}.

\end{proof}

We now turn to some corollaries of Theorem \ref{TheoremMain}. The first one concerns sums of a random amount of random summands.

\begin{cor1}
Consider a sequence of i.i.d. random vectors $\{(\xi_n = (\xi_{1n},\dots ,\xi_{dn}),\tau_n),n\geq 1\}$ with values in $\mathbb{R}^{d}\times\mathbb{R}_+$.  Let there exist $s>0$ such that $\e \exp\{s \tau_1\}<\infty$ and $\e\exp\{s |\xi_{k1}|\}<\infty$, $k=\overline{1,\, d}$. Denote $m(t) = \max\left(k\geq 0 : \sum\limits_{i=1}^k \tau_i\leq t\right)$ and
$S(t) = \sum\limits_{i=1}^{m(t)} \xi_i$ $($assuming a sum over an empty set is zero$)$. Then one can redefine the sequence $\{(\xi_n,\tau_n)\}$ on a probability space $(\Omega,\mathcal{F},\mathsf{P})$ supporting a standard Wiener process $\{W_t,t\geq 0\}$ such that for some positive constants $a,b,c,$ any $x>0$ and  $t\geq 1$ one has
\begin{equation}\label{RandomSumAsa}
\p\left(\sup_{u\leq t}\left|S(u) - \varkappa u - \sigma W_u\right| \geq c\log t + x \right) \leq a e^{-b x},
\end{equation}
where $\varkappa = {\e\xi_1}/{\e\tau_1}$ and $\sigma^2 = \di (\xi_1 - \varkappa\tau_1 )/\e\tau_1.$
\end{cor1}
\begin{proof}
It is sufficient to note that $S(u)$ is a cumulative process satisfying the conditions {\bf(A)} and {\bf(B)} with $T_0=0$ and $T_k = m^{-1}(k-1),\,k\geq 1$. Then, $\eta_k \equiv |\xi_k|$ and all the conditions of Theorem \ref{TheoremMain} are fulfilled.
\end{proof}

The second corollary  deals with birth and death processes. Recall that a continuous time homogeneous Markov chain $X=\{X_t,t\geq 0\}$ taking values in $\mathbb{Z}_+$
is an irreducible birth-death process if its transition matrices $\{P(t),t\geq 0\}$ satisfy
$$\frac{dP(t)}{d t} = P(t)A = AP(t), $$
where the entries of infinitesimal matrix $A$ are
$$a_{i,i+1}=\lambda_i ,i\geq 0;\;a_{i,i-1}=\mu_i,i\geq 1;\; a_{0,0} = -\lambda_0,\, a_{i,i} = -\lambda_i-\mu_i,i\geq 1\mbox{ and }a_{i,j}=0\mbox{ if }  |i-j|>1. $$
Denote
$$\pi_0=1,\;\pi_n = \frac{\lambda_0\ldots \lambda_{n-1}}{\mu_1\ldots \mu_n},\;n\geq 1. $$
Karlin and McGregor  \cite{KarlinMc} proved that conditions $\sum_n\pi_n<\infty,$ $\sum_n(\lambda_n\pi_n)^{-1}=\infty$ ensure that $X$ is ergodic, in which case $X$ satisfies the condition {\bf{(A)}}, with $T_0=0$ and $\{T_k,k\geq 1\}$ taken to be the moments of returning to zero.
For the condition {\bf{(B)}} to be true, we will require two following assumptions:
\begin{equation}\label{vanDoorn}
\liminf_{n\to\infty} (\lambda_n+\mu_n - \sqrt{\lambda_{n-1}\mu_n} - \sqrt{\lambda_{n}\mu_{n+1}} )>0
\end{equation}
and
\begin{equation}\label{exponential}
\limsup_{n\to\infty}\left(\lambda_n\pi_n\right)^{1/n} <1.
\end{equation}
Note that \eqref{vanDoorn} and \eqref{exponential} together imply the Karlin-McGregor ergodicity conditions \cite{KarlinMc}, in which case there exists a stationary distribution $\tilde{\pi}$ on $\mathbb{Z}_+,$ defined as
$$\tilde{\pi}_n = \frac{\pi_n}{\sum_{k=0}^{\infty}\pi_k},\,n\geq 0.$$ Furthermore,
by Van Doorn \cite{VanDoorn} and Karlin-McGregor \cite{KarlinMc} the relation \eqref{vanDoorn}  ensures that  the Laplace transform of the return time to zero is an analytic function at the origin. Finally,
by \cite[\S I.12]{Chung} \eqref{exponential} means that the maximum of the birth and death process between two returns to zero has a finite exponential moment.
Thus we arrive at the following corollary.

\begin{cor1}
Consider a birth and death process $X$ satisfying \eqref{vanDoorn} and \eqref{exponential}, with initial distribution $\tilde{\pi},$ and let $f:\mathbb{R}\to \mathbb{R}$ be a   function growing not faster than a linear one. Then one can redefine $X$ on a probability space $(\Omega,\mathcal{F},\mathsf{P})$ supporting a standard Wiener process $\{W_t,t\geq 0\}$ such that for some positive constants $a,b,c,$ any $x>0$ and  $t\geq 1$ one has
\begin{equation}\label{BirthDeathProcess}
\p\left(\sup_{u\leq t}\left|\int_0^u f(X_s) ds - \varkappa_f u - \sigma_f W_u\right| \geq c\log t + x \right) \leq a e^{-b x},
\end{equation}
where $\varkappa_f = \sum_{n=0}^{\infty}f(n)\tilde{\pi}_n$ and $$\sigma_f^2 =
2\int_0^{\infty}\sum_{n,m=0}^{\infty}f(n)f(m)\tilde{\pi}_n(P_{nm}(s)-\tilde{\pi}_m)  ds.$$
\end{cor1}
\begin{proof}
Given the discussion above, it suffices to compute $\varkappa_f$ and $\sigma_f.$ However by central limit theorem for Markov chains,
$\varkappa_f=\e f(X_0)$  and
$$\sigma_f^2 = \lim_{u\to\infty} \frac{1}{u}\int_{0}^u\int_0^u cov(f(X_t),f(X_s))ds \,dt =
2\int_{0}^{\infty} cov(f(X_0),f(X_s))ds. $$
\end{proof}

config: arxiv


TITLE: GAP-Character table
QUESTION [2 upvotes]: I the following link I have found the character table of $S_8$ which is computed with the program GAP.
http://groupprops.subwiki.org/wiki/Linear_representation_theory_of_symmetric_groups
But I don't quite understand it.  For instance this row:
Character( CharacterTable( "Sym(8)" ), [ 28, -10, 4, -2, -4, 1, -1, 1, 1, -1, 2, 0, 2, -1, 0, -2, 0, 1, 1, -1, 0, 0 ] ),
First for which partition we get this row in the character table and second each column of this row associated to which conjugacy class?
I would be very thankful, if you please help me understanding these.

REPLY [7 votes]: Here is a character table from GAP.

Here is how I made it:

gap> displaySym := function(n,file)
> local c,f;
> if IsString(file) then f := OutputTextFile(file,false);
>   SetPrintFormattingStatus(f,false);
> else f:= file; fi;
> c := CharacterTable("Symmetric",n);
> PrintTo(f, "\\documentclass[border=10]{standalone}\n");
> PrintTo(f, "\\begin{document}\n");
> PrintTo(f, "\\(\\begin{array}{l|",
>   ListWithIdenticalEntries(NrConjugacyClasses(c),'r'),"}\n");
> PrintTo(f, "Sym(",n,") & ", JoinStringsWithSeparator( List(CharacterParameters(c),
>   x -> Concatenation( List(Collected(x[2]),
>   y -> Concatenation( String(y[1]), "^{", String(y[2]), "}" ) ) ) )," & " ),
>   "\\\\ \\hline\n" );
> Perform( [1..NrConjugacyClasses(c)], function(k)
>   PrintTo( f, Concatenation( List( Collected( CharacterParameters(c)[k][2] ),
>   y -> Concatenation( String(y[1]), "^{", String(y[2]), "}" ) ) ), " & ",
>   JoinStringsWithSeparator( Irr(c)[k], " & " ), "\\\\\n" );
> end );
> PrintTo(f,"\\end{array}\\)\n");
> PrintTo(f,"\\end{document}\n");
> if IsString(file) then CloseStream(f); fi;
> end;;
gap> displaySym(8,"sym8.tex");;

Then convert to an image with:

$ xelatex sym8 >/dev/null 2>&1
$ convert -density 300 sym8.pdf sym8.png
$ pngcrush -e _c.png sym8.png


TITLE: If function is measurable on an interval, is it measurable on its subinterval?
QUESTION [4 upvotes]: This is exercise 2.3 from "A User-Friendly Introduction to Lebesgue Measure and Integration" by Gail S. Nelson:
Let $[c,d]\subseteq[a,b]$. Show that if $f$ is measurable on $[a,b]$, then $f$ is measurable on $[c,d]$.
By definition, function $f$ is Lebesgue measurable on an interval $I$ if for every $s\in\mathbb{R}$ the set $\{x\in I\mid f(x)>s\}$ is a Lebesgue measurable set. Here, obviously $\{x\in[c,d]\mid f(x)>s\}\subseteq\{x\in[a,b]\mid f(x)>s\}$, but at the moment I don't see how to proceed.

REPLY [1 votes]: Since $[c,d]\subseteq[a,b]$, we have:
$$
\Big( x\in[a,b]\ \&\ f(x)>s \Big)\ \&\ x\in[c,d]\quad\text{if and only if}\quad \Big( x\in[c,d]\ \&\ f(x)>s \Big).
$$
Therefore
$$
\{x : x\in[a,b]\ \&\ f(x)>s\} \cap [c,d] = \{x: x\in[c,d]\ \&\ f(x)>s\}.
$$


TITLE: If $A$ is subset of $B$, $B$ is subset of $C$, and $C$ is subset of $A$, then $A = B = C$
QUESTION [0 upvotes]: For all sets $A$, $B$, $C$, if $A$ is subset of $B$, $B$ is subset of $C$, and $C$ is subset of $A$, then $A = B = C$.
This is a true statement and I need to provide a proof? Thus, when a statement is false I need to provide it with counterexample whereas if it is true then it has to be provided by a proof?

REPLY [1 votes]: Yes what you say is correct. The statement is an application of the Extensionality Axiom of set theory. Extensionality says that if two sets have the same elements then they are equal. It is easy to see from $A \subseteq B$ and $B \subseteq A$ that an element belongs to $A$ if and only if it belongs to $B$, so by extensionality $A=B$.


TITLE: Why there is no even order in high-order harmonics generation of noble gas?
QUESTION [1 upvotes]: As we all know, there is no even-order peaks in HHG of noble gas. I understand this phenomenon by the knowledge here: there will be odd and even peaks in the frequency domain when we do fourier transform on a series of equally seperated pulses in time domain. Then the even order peaks dispear because that the even-order nonlinear susceptbility of noble gas is zero. However, the present explanation is really ugly. Is there more direct and resonable understanding of this phenomenon?

REPLY [0 votes]: Selection rules in the spectrum correspond directly with symmetries in the time domain.
For the case of even harmonics in HHG (or indeed any harmonic-generation configuration), the driving laser has a symmetry of the form
$$ E(t+\pi/\omega) = - E(t)$$
(i.e. advancing time by half a period results in a spatially-inverted electric field) and for a noble gas the generating medium is symmetric under that inversion, which entails that the dipole moment of the harmonic emission shares that symmetry,
$$ D(t+\pi/\omega) = - D(t).$$
The lack of even harmonic orders is simply the Fourier transform of this property.


TITLE: Is there a sensible notion of an approximation algorithm for an undecidable problem?
QUESTION [50 upvotes]: Certain problems are known to be undecidable, but it is nevertheless possible to make some progress on solving them.  For example, the halting problem is undecidable, but practical progress can be made on creating tools for detecting potential infinite loops in your code.  Tiling problems are often undecidable (e.g., does this polyomino tile some rectangle?) but again it is possible to advance the state of the art in this area.
What I am wondering is if there is any decent theoretical method of measuring progress on solving undecidable problems, that resembles the theoretical apparatus that has been developed for measuring progress on NP-hard problems.  Or does it seem that we are stuck with ad hoc, I-know-progress-when-I-see-it assessments of how much particular breakthroughs advance our understanding of undecidable problems?
Edit: As I think about this question, it occurs to me that perhaps parameterized complexity may be relevant here.  An undecidable problem may become decidable if we introduce a parameter and fix the value of the parameter.  I'm not sure if this observation is of any use, though.

REPLY [6 votes]: This is answering the title of the question more than its content, but you can also consider "approximations" of the halting problem as algorithms which will give you a correct answer on "almost all" programs.
The notion of "almost all" programs only makes sense if your model of computation is optimal (in the same sense that for Kolmogorov's complexity), to avoid situations where the majority of your programs are trivial.
Given an optimal machine $M$ and an integer $n$, can you give a correct answer to the halting problem for all programs of size $\lt n$, except a fraction $\epsilon$, for arbitrarily small $\epsilon$? Lynch proved in the 70s that no, you can't. A few years ago, colleagues and I proved a stronger version of this result, allowing the algorithm to make mistakes or to not halt on a small proportion of inputs, or only requiring a probabilistic approximation with probability $p\gt 0$ (allowing the algorithm to flip coins).
Along the way, we proved a bunch of interesting things about the properties of the sequence $\rho_n$, where $\rho_n$ is the ratio of programs of size $<n$ which halt (turns out, this sequence is very weird). If the paper above is too dense, you can check out my slides from when we presented the results at ICALP.


TITLE: Number of channels required to provide access to subscribers 80% of the time
QUESTION [2 upvotes]: A multichannel microwave link is to provide telephone communicationto a remote community having 12 subscribers, each of whom uses the link 20% of the time during peak hours. How many channels are needed to make the link available during peak hours to:
a. Eighty percent of the subscribers all of the time?
b. All of the subscribers 80% of the time?
For the a) part I came up with answer 10 channels which is correct according to my TA but I am not sure about the procedure I followed (I just found out what is eighty percent of 12)
I have no clue what b part means

REPLY [0 votes]: Let $c$ be the number of necessary channels and let $X \sim \text{Binomial}(12, 0.2)$ be the total number of subscribers that want to use the link at the same time during peak hours. Then we want to find the minimum $c$ such that:
$$
\text{Pr}(X \leq c) \geq 0.8
$$
Using this formula:
$$
\text{Pr}(X = c) = \binom{12}{c}(0.2)^c(0.8)^{12 - c}
$$
we guess and check by making a table:
\begin{array}{c|l}
c & \text{Pr}(X \leq c) \\ \hline
0 & 0.0687195 \\
1 & 0.274878 \\
2 & 0.558346 \\
3 & 0.794569 \\
4 & 0.927445
\end{array}
So we conclude that $c = 4$ channels are more than enough.


TITLE: Is the completion of $(k[x,y]/f)_\mathfrak{m}$ isomorphic to $k[[x]][y]/f$?
QUESTION [1 upvotes]: Let $k$ be an algebraically closed field and let $f\in k[x,y]$ be an irreducible polynomial with no constant term that is not a polynomial in $x$ alone.
Is it the case that the completion of the localization of $k[x,y]/(f)$ at the maximal ideal $(x,y)$ is isomorphic to $k[[x]][y]/(f)$?
If so, is there an easy proof? If not, an easy counterexample?
If it is true in less than full generality, what additional hypotheses are needed?

REPLY [0 votes]: This isn't true, and there are easy counterexamples.
As user115654 points out in the comments, $k[[x]][y]/(f)$ may not be local. This happens if $f$ has zeros on the $y$-axis other than $(0,0)$. For example, take $f = x^2 + y^2-y$. Then $(x,y)$ and $(x,y-1)$ are both maximal ideals of $k[[x]][y]/(f)$.


TITLE: What is the smallest prime of the form $n^n+5$?
QUESTION [10 upvotes]: This question asks about the smallest prime of the form $n^n+8$. However, I haven't be able to find a prime of the form $n^n+5$ where $n$ is natural, assuming we take $0^0=1$.
If $n$ is odd, then $n^n+5$ is even. If $n \equiv 2 \mod 6$ or $n \equiv 4 \mod 6$ then $n$ is even and $\gcd(n,3)=1$ and hence by the Euler-Fermat theorem $n^n \equiv 1 \mod 3$, and hence $n^n+5 \equiv 0 \mod 3$.
So only numbers in the form $n=6m$ can qualify. Of course, one also needs that $n$ is not divisible by 5. I also checked $n \leq 71$, they are not prime.
So I wonder whether there exists a prime in the form $n^n+5$, and if so, what is the smallest?

REPLY [4 votes]: $444^{444}+5$ is prime, and is the smallest of that form.  The next is $3948^{3948}+5$.
perl -Mntheory=:all -Mbigint -E 'for (1..1e5) { say if is_prime((0+$_)**$_+5); }'
It's a little faster using -Mbigint=lib,GMP or -MMath::GMP=:constant.  A bit under 0.3 seconds to find the first, albeit this is uses a robust PRP test rather than doing a proof.
See:  factordb entry for a primality certificate.


TITLE: Euler characteristic and generating series
QUESTION [11 upvotes]: This question was inspired by the question posed by John Baez here: https://mathoverflow.net/questions/67209?sort=votes#sort-top and Neil Strickland's answer to that question.
Let $X$ be a CW complex. If $X$ is finite, there are no problems defining its Euler characteristic whatsoever. However, when $X$ is infinite, there are at least two different ways which give similar but not identical results:
If the number $c(d)$ of cells of $X$ of dimension $d$ is finite for each $d$, one can form a generating function $f(t)=\sum_d c(d)t^d$ and define $\chi(X)=\lim_{t\to -1^+}f(t)$ (assuming the limit makes sense and exists).
If $X$ has a finite $d$-fold cover $\tilde X$ which is homotopy equivalent to a finite CW complex, then we can set $\chi(X)=\frac{1}{d}\sum_{i=1}^\infty (-1)^i\dim H^i(\tilde X,k)$ where $k$ is a field. This is the Wall characteristic (a.k.a. the rational Euler characteristic) of $X$ and it is a homotopy invariant and does not depend on $k$.
Now, if we try to calculate the characteristic of $\mathbb{R} P^\infty$ with its standard cell decomposition (one cell in each dimension from $0$ to $\infty$), then both definitions agree: the first one gives the generating function $\frac{1}{1-t}$, which gives $\frac{1}{2}$, when evaluated at $t=-1$; the second one also gives $\frac{1}{2}$ using the double cover $pt\cong S^\infty\to \mathbb{R} P^\infty$.
However, if we take a finite group $G$ and try to compute the characteristic of the Milnor construction of $BG$, then the first definition will give $\frac{1}{1+\# G}$, since the number of simplices of dimension $d$ is $(\# G)^d$, while the second one gives $\frac{1}{\# G}$.
I would like to ask: is there a conceptual reason the two definitions agree in the first case and almost (but not quite) agree in the second? This is, of course, a rather vague question, so here is a slightly more specific version: if the number of cells of $X$ of each dimension is finite, then is there a way to deduce the Wall characteristic of $X$ from the generating series for those numbers, assuming the Wall characteristic exists?

REPLY [7 votes]: I hope a topologist provides an answer.  I'll make some general comments about sums of series.
Something to keep in mind when working with divergent series is that they do diverge.  In particular, divergent sums are not associative.  (This is similar to the fact that conditionally convergent sums are not commutative, as is standardly explained in freshman calculus.)  Perhaps the most famous manifestation of the non-associativity is the "proof" that $0=1$ by writing $0 = \sum 0 = \sum (1-1) = \dots$.  But a better example, because it's more illustrative, is the proof that $\frac12 = \frac13$: as you point out in the case of $\mathbb R P^\infty$, one should predict that $1 - 1 + 1 - 1 + \dots = \frac12$, because if you translate the sum by one step and then add the translated series to the original series in columns, all terms cancel except the first one.  But if you instead consider $1 - 1 + 0 + 1 - 1 + 0 + \dots$, you see that you need three shifts the sum to $1$.  Put another way, the Abel sum of $1 - 1 + 0 + 1 - 1 + 0 + \dots$ is $\sum t^{3n} - \sum t^{3n+1} = \frac1{1-t^3} - \frac t{1-t^3} = \frac1{1+t+t^2} \to \frac13$.
I think you're finding some similar behavior in the case of the Milnor $\mathrm BG$.  Of course, the "correct" Euler characteristic is $1/\chi(G)$.  What I think needs to happen is that the "new" simplices when you construct $\mathrm B G$ should have the even spacing in the sum, the same as they have in the reduced bar construction.  But the degenerate simplices in Milnor's cell complex should be associated in such a way as to cancel out like in $(1-1) + (1-1) + \dots$.
Of course, this is a bit ad hoc.  A possibility is that the dimensions of the homology groups do have the correct Abel sum?  That would be the answer if you believe me that only the nondegenerate simplices should contribute.  But I haven't thought whether this is correct on the nose.


text:
\section{Introduction}
Algebraic objects depending on combinatorial data have attracted a lot of interest among both algebraists and combinatorialists: some valuable sources to learn about this research area are the books by Stanley \cite{Stanley}, Villarreal \cite{Villarreal}, Miller and Sturmfels \cite{MillerSturmfels}, and Herzog and Hibi \cite{HerzogHibi}.
It is often a challenge to establish relationships between algebraic and combinatorial properties of these objects.

Let $G$ be a simple graph and consider its vertices as variables of a polynomial ring over a field $K$. We can associate with each edge $e$ of $G$ the squarefree monomial $M_e$ of degree 2 obtained by multiplying the variables corresponding to the vertices of the edge. With this correspondence in mind, we can now introduce some algebraic objects associated with the graph $G$:
\begin{itemize}
\item the \emph{edge ideal} $I(G)$ is the monomial ideal generated by $\{M_e \mid e\textrm{ is an edge of }G\}$;
\item the \emph{toric ideal} $I_G$ is the kernel of the presentation of the $K$-algebra $K[G]$ generated by $\{M_e \mid e\textrm{ is an edge of }G\}$.
\end{itemize}
An important result by Fr\"oberg \cite{Fr} gives a combinatorial characterization of those graphs $G$ whose edge ideal $I(G)$ admits a linear resolution: they are exactly the ones whose complementary graph $G^c$ is chordal.
Another strong connection between the realms of commutative algebra and combinatorics is the one which links initial ideals of the toric ideal $I_G$ to triangulations of the edge polytope of $G$, see Sturmfels's book \cite{Sturmfels} and the recent article by Haase, Paffenholz, Piechnik and Santos \cite{HPPS}. Furthermore, Gr\"obner bases of $I_G$ have been studied among others by Ohsugi and Hibi \cite{OHToric} and Tatakis and Thoma \cite{TTUniversal}. A necessary condition for $I_G$ to have a squarefree initial ideal is the normality of $K[G]$, which was characterized combinatorially by Ohsugi and Hibi \cite{OHPolytopes} and Simis, Vasconcelos and Villarreal \cite{SVV}. Normality, though, is not sufficient: Ohsugi and Hibi \cite{OHStar} gave an example of a graph $G$ such that $K[G]$ is normal but all possible initial ideals of $I_G$ are not squarefree.

An interesting class of graphs is the one consisting of the so-called \emph{gap-free graphs} (following Dao, Huneke and Schweig's notation in \cite{DHS}), i.e. graphs such that any two edges with no vertices in common are linked by at least one edge. Unfortunately, these graphs do not have a standard name in the literature. Just to name a few possibilities:
\begin{itemize}
\item graph theorists refer to gap-free graphs as ``2$K_2$-free graphs'' and so do Hibi, Nishiyama, Ohsugi and Shikama in \cite{HNOS};
\item Nevo and Peeva call them ``$C_4$-free graphs'' in \cite{Nevo} and \cite{NevoPeeva};
\item Ohsugi and Hibi use the phrase ``graphs whose complement is weakly chordal'' in \cite{OHIndispensable};
\item Corso and Nagel call bipartite gap-free graphs ``Ferrers graphs'' in \cite{CorsoNagel}.
\end{itemize}

The main goal of this paper is to prove that the toric ideal $I_G$ has a squarefree lexicographic initial ideal, provided the graph $G$ is gap-free (Theorem \ref{onesteplin}): moreover, the corresponding reduced Gr\"obner basis consists of circuits. In the particular case when $I(G)$ has a linear resolution (Theorem \ref{linres}) we are actually able to prove that the reduced Gr\"obner basis $\mathcal{G}$ we describe consists of circuits such that all monomials (both leading and trailing) in the support of $\mathcal{G}$ are squarefree, thus extending a result of Ohsugi and Hibi \cite{OHCompressed} on multipartite complete graphs.

\renewcommand{\labelenumi}{(\alph{enumi})}

In \cite{HHZ} Herzog, Hibi and Zheng proved that the following conditions are equivalent:
\begin{enumerate}
\item $I(G)$ has a linear resolution;
\item $I(G)$ has linear quotients;
\item $I(G)^k$ has a linear resolution for all $k \geq 1$.
\end{enumerate}
It is quite natural to ask (see for instance the article by Hoefel and Whieldon \cite{HW}) whether these conditions are in turn equivalent to the fact that \begin{enumerate}\item[(d)] $I(G)^k$ has linear quotients for all $k \geq 1$.\end{enumerate} In Theorem \ref{linchar} we prove that this is indeed the case, as can be deduced from results in \cite{HerzogHibi}. Note that all the equivalences between conditions (a), (b), (c), (d) above hold more generally for monomial ideals generated in degree 2 which are not necessarily squarefree.

The computer algebra system $\cocoa$ \cite{CoCoA} gave us the chance of performing computations which helped us to produce conjectures about the behaviour of the objects studied.

\renewcommand{\labelenumi}{(\roman{enumi})}

\section{Notation and known facts}
First of all, let us fix some notation.
$K$ will always be a field and $G$ a simple graph with vertices $V(G) = \{1, \ldots, n\}$ and edges $E(G) = \{e_1, \ldots, e_m\}$. We can associate to each edge $e = \{i, j\}$ the degree 2 monomial (called \emph{edge monomial}) $M_e := x_ix_j \in K[x_1, \ldots, x_n]$ and hence we can consider the \emph{edge ideal} $I(G) := (M_{e_1}, \ldots, M_{e_m})$ and the subalgebra $K[G] := K[M_{e_1}, \ldots, M_{e_m}]$. In the following we will denote by $I_G$ the \emph{toric ideal associated with} $G$, i.e. the kernel of the surjection
\[\begin{array}{ccc}  K[y_1, \ldots, y_m] & \twoheadrightarrow & K[G] \\ y_i & \mapsto & M_{e_i} \end{array}\]
Since the algebraic objects we defined are not influenced by isolated vertices of $G$, we will always assume without loss of generality that $G$ does not have any isolated vertex.
We will now introduce some terminology and state some well-known results about toric ideals of graphs: for reference, see for instance \cite[Section 10.1]{HerzogHibi}.

A collection of (maybe repeated) consecutive edges \[\Gamma = \{\{v_0, v_1\},\{v_1, v_2\}, \ldots, \{v_{q-1}, v_q\}\}\] (also denoted by $\{v_0 \rightarrow v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_{q-1} \rightarrow v_q\}$) is called a \emph{walk} of $G$. If $v_0 = v_q$, the walk is \emph{closed}. If $q$ is even (respectively odd), the walk is an even (respectively odd) walk. A \emph{path} is a walk having all distinct vertices; a \emph{cycle} is the closed walk most similar to a path, i.e. such that vertices $v_0, \ldots, v_{q-1}$ are all distinct. A \emph{bow-tie} is a graph consisting of two vertex-disjoint odd cycles joined by a single path. Given a walk $\Gamma$, we will denote by $|\Gamma|$ the subgraph of $G$ whose vertices and edges are exactly the ones appearing in $\Gamma$.
If no confusion occurs, we will often write walks in more compact ways, such as by decomposing them into smaller walks. If $\Gamma$ is a walk, $-\Gamma$ denotes the walk obtained from $\Gamma$ by reversing the order of the edges.

If $\Gamma = \{\{v_0, v_1\},\{v_1, v_2\}, \ldots, \{v_{2q-1}, v_{2q}\}\}$ is an even closed walk, one can associate with $\Gamma$ a binomial $b_{\Gamma} \in K[y_1, \ldots, y_m]$ in the following way: \[b_{\Gamma} := \prod_{i=1}^q y_{\{v_{2i-2}, v_{2i-1}\}} - \prod_{i=1}^q  y_{\{v_{2i-1}, v_{2i}\}},\] where, if $e \in E(G)$, by $y_e$ we mean the variable which is mapped to $M_e$ by the standard surjection.
A \emph{subwalk} $\Gamma'$ of $\Gamma$ is an even closed walk such that all even edges of $\Gamma'$ are also even edges of $\Gamma$ and all odd edges of $\Gamma'$ are also odd edges of $\Gamma$.
An even closed walk $\Gamma$ is called \emph{primitive} if it does not have any proper subwalk. The set of binomials corresponding to primitive walks of a graph $G$ coincides with the so-called \emph{Graver basis} of $I_G$ (see for instance \cite{Sturmfels}) and is denoted by $\Gr_G$.

\begin{rem} \label{primitivepaint}
Note that, given a primitive walk $\Gamma$, one can paint -- using two colours -- the edges of $|\Gamma|$ so that those appearing in an even position in $\Gamma$ are assigned the same colour and those appearing in an odd position are assigned the other one. If an edge were assigned both colours, then the walk $\Gamma$ would not be primitive: deleting inside both monomials one instance of the variable corresponding to that edge, one could construct a proper subwalk of $\Gamma$.
\end{rem}

The \emph{support} of a binomial $b = u-v \in I_G$ is the union of the supports of the monomials $u$ and $v$, that is to say the variables that appear in $u$ and $v$. A binomial $b \in I_G$ is called a \emph{circuit} if it is irreducible and has minimal support, i.e. there does not exist $b' \in I_G$ such that $\supp(b') \subsetneq \supp(b)$. The set of circuits of $I_G$ is denoted by $\textrm{C}_G$.

Let $I$ be an ideal of $S := K[x_1, \ldots, x_n]$. A Gr\"obner basis $\mathcal{G}$ of $I$ with respect to a term order $\tau$ is called \emph{reduced} if every element of $\mathcal{G}$ is monic, the leading terms of $\mathcal{G}$ minimally generate $in_{\tau}(I)$ and no trailing term of $\mathcal{G}$ lies in $in_{\tau}(I)$. Such a basis is unique and is denoted by $\RGB_{\tau}(I)$. Generally speaking, changing the term order $\tau$ yields a different reduced Gr\"obner basis: we will denote by $\UGB(I)$ the \emph{universal Gr\"obner basis} of $I$, i.e. the union of all reduced Gr\"obner bases of $I$.

\begin{prop}[{\cite[Proposition 4.11]{Sturmfels}}] \label{inclusions}
One has that $\emph{C}_G \subseteq \UGB(I_G) \subseteq \Gr_G$.
\end{prop}

The second inclusion of Proposition \ref{inclusions} means that every reduced Gr\"obner basis $\mathcal{G}$ of $I_G$ consists of binomials coming from primitive walks of $G$. Consider the set of monomials (both leading and trailing) in such a basis: if they are all squarefree, we will say that $\mathcal{G}$ is \emph{doubly squarefree}.

Complete characterizations of both $\textrm{C}_G$ (Villarreal \cite{VillarrealCircuits}) and $\UGB(I_G)$ (Tatakis and Thoma \cite{TTUniversal}) are known. We recall the characterization of $\textrm{C}_G$ (using the phrasing in Ohsugi and Hibi's article \cite{OHCircuits}) as a reference.

\renewcommand{\labelenumi}{\arabic{enumi}.}

\begin{prop} \label{circuits}
A binomial $b \in I_G$ is a circuit of $G$ if and only if $b = b_{\Gamma}$, where $\Gamma$ is one of the following even closed walks:
\begin{enumerate}
\item an even cycle;
\item $\{C_1, C_2\}$ where $C_1$ and $C_2$ are odd cycles with exactly one common vertex;
\item $\{C_1, p, C_2, -p\}$ where $C_1$ and $C_2$ are vertex-disjoint odd cycles and $p$ is a path running from a vertex of $C_1$ to a vertex of $C_2$.
\end{enumerate}
\end{prop}

\begin{defin}
Let $I \subseteq S := K[x_1, \ldots, x_n]$ be a graded ideal generated in degree $d$.
\begin{itemize}
\item If the minimal free resolution of $I$ as an $S$-module is linear until the $k$-th step, i.e. $\Tor^S_i(I, K)_j = 0$ for all $i \in \{0, \ldots, k\}$, $j \neq i+d$, we say that $I$ is \emph{k-step linear}.
\item If $I$ is $k$-step linear for every $k \geq 1$, we say $I$ has a \emph{linear resolution}.
\item If $I$ is minimally generated by $f_1, \ldots, f_s$ and for every $1 < i \leq s$ one has that $(f_1, f_2, \ldots, f_{i-1}) :_S (f_i)$ is generated by elements of degree 1, then $[f_1, \ldots, f_s]$ is called a \emph{linear quotient ordering} and $I$ is said to have \emph{linear quotients}.
\item If $I = I(G)$ for some graph $G$ and $I$ has one of the properties above, we say that $G$ has that property.
\end{itemize}
\end{defin}

\begin{prop}[{\cite[Proposition 8.2.1]{HerzogHibi}}] \label{linquotres}
Let $I \subseteq K[x_1, \ldots, x_n]$ be a graded ideal generated in degree $d$. Then
\[I\textrm{ has linear quotients }\Rightarrow I\textrm{ has a linear resolution.}\]
\end{prop}

\renewcommand{\labelenumi}{(\alph{enumi})}

We now recall an important result by Herzog, Hibi and Zheng (\cite{HHZ}) about the connection between linear quotients and linear resolution in the case when $I$ is a monomial ideal generated in degree 2. Condition (d) below did not appear in the original paper: its equivalence to other conditions, though, can be obtained quickly using results in \cite{HerzogHibi}.

\begin{thm} \label{linchar}
Let $I \subseteq K[x_1, \ldots, x_n] $ be a monomial ideal generated in degree 2. Then the following conditions are equivalent:
\begin{enumerate}
\item $I$ has a linear resolution;
\item $I$ has linear quotients;
\item $I^k$ has a linear resolution for all $k \geq 1$;
\item $I^k$ has linear quotients for all $k \geq 1$.
\end{enumerate}
\begin{proof}
The implications $(c) \Rightarrow (a)$ and $(d) \Rightarrow (b)$ are obvious, while $(b) \Rightarrow (a)$ and $(d) \Rightarrow (c)$ follow from Proposition \ref{linquotres}. It is then enough to prove that $(a) \Rightarrow (d)$, but this follows at once from \cite[Theorems 10.1.9 and 10.2.5]{HerzogHibi} (since the lexicographic order $<_{\textrm{lex}}$ introduced in Theorem 10.2.5 is of the kind appearing in Theorem 10.1.9).
\end{proof}
\end{thm}

\begin{rem} \label{linquotedges}
Theorem 10.2.5 and the proof of Theorem 10.1.9 in \cite{HerzogHibi} (or, as an alternative, just the proof of the implication $(a) \Rightarrow (b)$ in Theorem 10.2.6) tell us also that, if $I$ is a monomial ideal of degree 2 having a linear resolution and $\{m_1, m_2, \ldots, m_s\}$ is a minimal set of monomial generators for $I$, then there exists a permutation $\sigma$ of $\{1, \ldots, s\}$ such that $[m_{\sigma(1)}, m_{\sigma(2)}, \ldots, m_{\sigma(s)}]$ is a linear quotient ordering for $I$. As a consequence, if $I$ is the edge ideal of some graph $G$ having a linear resolution, there exists a way of ordering the edge monomials so that they form a linear quotient ordering.
\end{rem}

We thank Aldo Conca for pointing out the following result:

\begin{prop} \label{linquot}
Let $f_1, \ldots, f_s$ be distinct homogeneous elements of degree $d$ in $S := K[x_1, \ldots, x_n]$ which are minimal generators for the ideal $(f_1, \ldots, f_s)$. The following conditions are equivalent:
\begin{enumerate}
\item $[f_1, \ldots, f_s]$ is a linear quotient ordering;
\item the ideal $(f_1, \ldots, f_i)$ is 1-step linear for all $i \leq s$.
\end{enumerate}

\begin{proof}
Let us prove that $(a) \Rightarrow (b)$. Let $i \leq s$. If $[f_1, \ldots, f_s]$ is a linear quotient ordering, than $[f_1, \ldots, f_i]$ is too and hence, by Proposition \ref{linquotres}, the ideal $(f_1, \ldots, f_i)$ has a linear resolution; in particular, it is 1-step linear.

To prove that $(b) \Rightarrow (a)$, let $i \in \{2, \ldots, s\}$. Consider the exact sequence \[0 \to \Ker\varepsilon \to S(-d)^i \xrightarrow{\varepsilon} (f_1, \ldots, f_i) \to 0,\] where $\varepsilon$ is the map which sends $e_j$ to $f_j$ for all $j \in \{1, \ldots, i\}$. Then, by hypothesis, $\Ker\varepsilon$ is generated in degree 1. Since $(f_1, \ldots, f_{i-1}) :_S (f_i)$ is isomorphic to the $i$-th projection of $\Ker\varepsilon$, we are done.
\end{proof}
\end{prop}

In what follows, we will denote by $G^c$ the \emph{complementary graph} of $G$, i.e. the graph which has the same vertex set of $G$ and whose edges are exactly the non-edges of $G$.

The next result by Eisenbud, Green, Hulek and Popescu proves that, in our context, the algebraic concept of $k$-step linearity can be characterized in a purely combinatorial manner.

\begin{prop}[{\cite[Theorem 2.1]{EGHP}}] \label{EGHPprop}
Let $G$ be a graph and let $k \geq 1$. The following conditions are equivalent:
\begin{itemize}
\item $G$ is $k$-step linear;
\item $G^c$ does not contain any induced cycle of length $i$ for any $4 \leq i \leq k+3$.
\end{itemize}
\end{prop}

As a corollary, we recover the important result by Fr\"oberg characterizing combinatorially graphs with a linear resolution.

\begin{cor} [\cite{Fr}]
Let $G$ be a graph. Then $G$ has a linear resolution if and only if $G^c$ is chordal, i.e. $G^c$ does not contain any induced cycle of length greater than or equal to $4$.
\end{cor}

Following the notation in \cite{DHS}, we will call a graph $G$ \emph{gap-free} if for any $\{v_1, v_2\}$, $\{w_1, w_2\}$ in $E(G)$ (where $v_1, v_2, w_1, w_2$ are all distinct) there exist $i, j \in \{1, 2\}$ such that $\{v_i, w_j\} \in E(G)$. In other words, in a gap-free graph any two edges with no vertices in common are linked by at least a bridge.

\begin{rem} \label{gapfreeonesteplin}
It is easy to see that $G$ is gap-free if and only if $G^c$ does not contain any induced cycle of length 4. It then follows from Proposition \ref{EGHPprop} that $G$ is gap-free if and only if $G$ is 1-step linear.
\end{rem}

The following theorem holds more generally for affine semigroup algebras.

\renewcommand{\labelenumi}{\arabic{enumi}.}

\begin{thm} \label{hocstu}
Let $G$ be a graph.
\begin{enumerate}
\item \emph{(Hochster \cite{Hochster})} If $K[G]$ is normal, then it is Cohen-Macaulay.
\item \emph{(Sturmfels \cite[Proposition 13.15]{Sturmfels})} If $I_G$ admits a squarefree initial ideal with respect to some term order $\tau$, then $K[G]$ is normal (and hence Cohen-Macaulay).
\end{enumerate}
\end{thm}

\renewcommand{\labelenumi}{(\roman{enumi})}

The problem of normality of graph algebras (and, as a consequence, of edge ideals, see \cite[Corollary 2.8]{SVV}) was addressed and completely solved by Ohsugi and Hibi \cite{OHPolytopes} and Simis, Vasconcelos and Villarreal \cite{SVV}.
One of the main results they found is the following:

\begin{thm}
A connected graph $G$ is such that $K[G]$ is normal if and only if $G$ satisfies the \emph{odd cycle condition}, i.e. for every couple of disjoint minimal odd cycles $\{C_1, C_2\}$ in $G$ there exists an edge linking $C_1$ and $C_2$.
\end{thm}

Ohsugi and Hibi \cite{OHStar} also found an example of a graph $G$ such that $K[G]$ is normal but $in_{\tau}(I_G)$ is not squarefree for every choice of $\tau$, hence the condition in Theorem \ref{hocstu}.2 is sufficient but not necessary.

\begin{rem}
There is a strong connection between squarefree initial ideals of $I_G$ and unimodular regular triangulations of the edge polytope of $G$. To get more information about this topic, see \cite{Sturmfels} and the recent work \cite{HPPS}, in particular Section 2.4.
\end{rem}

\section{Results}
We start by stating a result about the shape of primitive walks. This is a modification of \cite[Lemma 2.1]{OHToric}: note that primitive walks were completely characterized by Reyes, Tatakis and Thoma in \cite[Theorem 3.1]{RTT} and by Ogawa, Hara and Takemura in \cite[Theorem 1]{OHT}. In the rest of the paper we will often talk of primitive walks of type (i), (ii), (iii) referring to the classification below.

\begin{lemma}\label{primitivewalks}
Let $\Gamma$ be a primitive walk. Then $\Gamma$ is one of these:
\begin{enumerate}
\item an even cycle;
\item $\{C_1, C_2\}$ where $C_1$ and $C_2$ are odd cycles with exactly one common vertex;
\item $\{C_1, p_1, C_2, p_2, \ldots, C_h, p_h\}$ where the $p_i$'s are paths of length greater than or equal to one and the $C_i$'s are odd cycles such that $C_{i \pmod h}$ and $C_{i+1 \pmod h}$ are vertex-disjoint for every $i$.
\end{enumerate}
\begin{proof}
Let $\Gamma$ be a primitive walk neither of type (i) nor (ii). Since $\Gamma$ is primitive, there exists a cycle $C_1$ inside $\Gamma$ (otherwise $\Gamma = \{p, -p\}$ where $p$ is a path and hence all edges of $p$ would appear both in odd and even position in $\Gamma$, thus violating the primitivity); moreover, since $\Gamma$ is not of type (i), $C_1$ has to be odd. Let $C_1 = \{v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_{2k+1} \rightarrow v_1\}$; then \[\Gamma = \{v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_{2k+1} \rightarrow v_1=u_0 \rightarrow u_1 \rightarrow u_2 \rightarrow u_3 \rightarrow \ldots\}.\]
Let $s \geq 1$ be the least integer such that $u_s$ coincides with one of the vertices in $\{u_0 = v_1, v_2, \ldots, v_{2k+1}, u_1, \ldots, u_{s-1}\}$.
\begin{itemize}
\item Suppose $u_s = v_i$ where $i \neq 1$. If $s = 1$ and $i \in \{2, 2k+1\}$, we get that the edge $\{v_1, v_i\}$ is both an even and an odd edge of $\Gamma$ (contradiction). In all other cases, paint the edges appearing in $\Gamma$ red and black alternately and note that, since $i \neq 1$, there are both a red and a black edge of $C_1$ starting from $v_i$. Then exactly one of $\{v_1 = u_0 \rightarrow u_1 \rightarrow \ldots \rightarrow u_{s-1} \rightarrow u_s = v_i \rightarrow v_{i+1} \rightarrow \ldots \rightarrow v_{2k+1} \rightarrow v_1 = u_0\}$ and $\{v_1 = u_0 \rightarrow u_1 \rightarrow \ldots \rightarrow u_{s-1} \rightarrow u_s = v_i \rightarrow v_{i-1} \rightarrow \ldots \rightarrow v_2 \rightarrow v_1 = u_0\}$ is an even closed subwalk, thus violating the primitivity of $\Gamma$. This gives us a contradiction.
\item Suppose $u_s = u_i$ where $i \in \{0, \ldots, s-2\}$ (since $G$ has no loops, $i \neq s-1$). Note that one actually has that $i < s-2$, since $i = s-2$ would imply that the edge $\{u_{s-1}, u_s\}$ is both an even and an odd edge of $\Gamma$ (contradiction). Therefore there exists a cycle $C_2 = \{u_s = u_i \rightarrow u_{i+1} \rightarrow \ldots \rightarrow u_{s-1} \rightarrow u_s = u_i\}$ disjoint from $C_1$ by construction. Since $\Gamma$ is primitive, $C_2$ must be odd; moreover, since $\Gamma$ is not of type (ii), one has that $i \neq 0$. This means that we have found a path $p_1 = \{u_0 \rightarrow u_1 \rightarrow \ldots \rightarrow u_i\}$ linking the odd cycles $C_1$ and $C_2$. We can now repeat the whole procedure starting from the cycle $C_2$ to find a path $p_2$ and an odd cycle $C_3$ disjoint from $C_2$ and so on, hence proving the claim in a finite number of steps. \qedhere
\end{itemize}
\end{proof}
\end{lemma}

\begin{rem}
The referee noted that an alternative proof of Lemma \ref{primitivewalks} may be given using \cite[Theorem 1]{OHT}.
\end{rem}

\begin{rem}
Note that, by Proposition \ref{circuits}, all binomials corresponding to primitive walks of type (i) and (ii) are circuits.
\end{rem}

\renewcommand{\labelenumi}{(\alph{enumi})}

\begin{notat}
Let $G$ be a graph with $m$ edges and let $\tau$ be a term ordering on $K[y_1, \ldots, y_m]$. With a slight abuse of notation, we will often say that $e \preceq_{\tau} e'$ instead of $y_e \preceq_{\tau} y_{e'}$ (where $e, e' \in E(G)$). Moreover, if $H$ is a subgraph of $G$ and $\tau$ is lexicographic, we will say that $e \in E(H)$ is the \emph{leading edge} of $H$ with respect to $\tau$ if $y_{e'} \preceq_{\tau} y_e$ for every $e' \in E(H)$.
\end{notat}

Next we introduce the main technical lemma of the paper. Note that, when dealing with the vertices $v_1, \ldots, v_s$ of a cycle, for the sake of simplicity we will often write $v_i$ instead of $v_{i \pmod s}$.

\begin{lemma}\label{mainlemma}
Let $\Gamma$ be a primitive closed walk of $G$ of type (iii) and let $\tau$ be a lexicographic term order on $K[y_1, \ldots, y_m]$. Let $e$ be the leading edge of $|\Gamma|$ with respect to $\tau$: by Lemma \ref{primitivewalks}, $e$ lies into a bow-tie $\{C_1, p, C_2\}$.
Let $C_1 = \{v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_{2k+1} \rightarrow v_1\}$, $C_2 = \{v'_1 \rightarrow v'_2 \rightarrow \ldots \rightarrow v'_{2{\ell}+1} \rightarrow v'_1\}$ and let $v_1$ and $v'_1$ be the starting and ending vertices of the path $p$.
Suppose one of the following two conditions holds:
\begin{enumerate}
\item $e \in p$ and there exist $i, j$ such that $\tilde{e} := \{v_i, v'_j\} \in E(G)$, $\tilde{e} \prec_{\tau} e$, $\tilde{e} \neq \{v_1, v'_1\}$;
\item $e = \{v_i, v_{i+1}\}$ and there exists $j$ such that at least one between $\{v_i, v'_j\}$ and $\{v_{i+1}, v'_j\}$ is an edge of $G$ (call it $\tilde{e}$) such that $\tilde{e} \prec_{\tau} e$ and $\tilde{e} \neq \{v_1, v'_1\}$.
\end{enumerate}
Then $b_{\Gamma} \notin \RGB_{\tau}(I_G)$.
\begin{proof}
First of all, by Remark \ref{primitivepaint} the primitivity of the walk $\Gamma$ allows us to paint the edges of $|\Gamma|$ red and black so that no two edges consecutive in $\Gamma$ are painted the same colour. We can assume without loss of generality that the edge $e$ is black.
\begin{enumerate}
\item Paint $\tilde{e}$ red. We can suppose without loss of generality that $i \neq 1$: hence, exactly one of $\{v_{i-1}, v_i\}$ and $\{v_i, v_{i+1}\}$ is black. This means that exactly one of the two paths going from $v_i$ to $v_1$ along $C_1$ has its first edge painted black: let $w$ be this path. We now need to define a path $w'$ going from $v'_1$ to $v'_j$.
\begin{itemize}
\item If $j \neq 1$, exactly one of $\{v'_{j-1}, v'_j\}$ and $\{v'_j, v'_{j+1}\}$ is black. Applying the same reasoning as before, let $w'$ be the path going from $v'_1$ to $v'_j$ along $C_2$ having its last edge painted black.
\item If $j = 1$ and the last edge of $p$ is red, let $w' = \{v'_1 \rightarrow v'_2 \rightarrow \ldots \rightarrow v'_{2k+1} \rightarrow v'_1\}$ (in other words, the whole cycle $C_2$); if the last edge of $p$ is black, let $w'$ be the empty path in $v'_1$.
\end{itemize}
Let $\Gamma' = \{v'_j \xrightarrow{\tilde{e}} v_i \xrightarrow{w} v_1 \xrightarrow{p} v'_1 \xrightarrow{w'} v'_j\}$. By construction, $\Gamma'$ is an even closed walk, since its edges are alternately red and black and the first and the last one have different colours. Moreover, it is easy to check that $\Gamma'$ is primitive either of type (ii) (when $j=1$ and the last edge of $p$ is red) or of type (i) (in all other cases); hence, $\Gamma' \in \Gr_G$. Finally, since $\tau$ is a lexicographic term order, to get who the leading monomial of $b_{\Gamma'}$ is we just have to identify the leading edge of $\Gamma'$: since $\tilde{e} \prec_{\tau} e$ by hypothesis and the rest of the edges of $\Gamma'$ are edges of $\Gamma$, we get that the leading monomial of $b_{\Gamma'}$ is the one formed by black edges. Since the black edges of $\Gamma'$ all lie in $\Gamma$, we have that $in_{\tau}(b_{\Gamma'})$ divides $in_{\tau}(b_{\Gamma})$. Since $b_{\Gamma} \neq b_{\Gamma'}$, we have that $b_{\Gamma} \notin \RGB_{\tau}(I_G)$.
\item Paint $\tilde{e}$ red and define $w'$ in the same way as in part (a). Let $w$ be defined the following way:
\begin{itemize}
\item if $\tilde{e} = \{v_i, v'_j\}$, let $w := \{v_{i+1} \rightarrow v_{i+2} \rightarrow \ldots \rightarrow v_{2k+1} \rightarrow v_1\}$ (if $i = 2k+1$, $w$ is the empty path);
\item if $\tilde{e} = \{v_{i+1}, v'_j\}$, let $w := \{v_{i} \rightarrow v_{i-1} \rightarrow \ldots \rightarrow v_2 \rightarrow v_1\}$ (if $i = 1$, $w$ is the empty path).
\end{itemize}
Let \[\Gamma' :=  \left\{ \begin{array}{lll} \{v_{i+1} \xrightarrow{w} v_1 \xrightarrow{p} v'_1 \xrightarrow{w'} v'_j \xrightarrow{\tilde{e}} v_i \xrightarrow{e} v_{i+1}\} & \textrm{if} & \tilde{e} = \{v_i, v'_j\} \\ \{v_i \xrightarrow{w} v_1 \xrightarrow{p} v'_1 \xrightarrow{w'} v'_j \xrightarrow{\tilde{e}} v_{i+1} \xrightarrow{e} v_i\} & \textrm{if} & \tilde{e} = \{v_{i+1}, v'_j\}\end{array} \right.\]
Reasoning the same way as in part (a), we get that $\Gamma'$ is an even closed walk; moreover, it can be easily checked that $\Gamma'$ is primitive either of type (ii) (when $v'_1$ belongs to $\tilde{e}$ and the last edge of $p$ is red or when $v_1$ belongs to $\tilde{e}$, with no restrictions on the colour of the last edge of $p$) or type (i) (in all other cases), hence $b_{\Gamma'} \in \Gr_G$. For the same reasons as in part (a), we get that $b_{\Gamma} \notin \RGB_{\tau}(I_G)$. \qedhere
\end{enumerate}
\end{proof}
\end{lemma}

\renewcommand{\labelenumi}{(\roman{enumi})}

\begin{thm} \label{linres}
Let $G$ be a graph with linear resolution and let $[e_1, \ldots, e_m]$ be an ordering of the edges of $G$ such that $[M_{e_1}, \ldots, M_{e_m}]$ is a linear quotient ordering for $I(G)$ (such an ordering exists by Remark \ref{linquotedges}). Let $\tau$ be the lexicographic order on $K[y_1, \ldots, y_m]$ such that $y_1 \prec_{\tau} y_2 \prec_{\tau} \ldots \prec_{\tau} y_m$. Then the reduced Gr\"obner basis of $I_G$ with respect to $\tau$ is doubly squarefree.
\begin{proof}
By Proposition \ref{linquot}, the linear quotient property is equivalent to asking that each subgraph $\{e_1, \ldots, e_i\}$ is 1-step linear, that is to say gap-free by Remark \ref{gapfreeonesteplin}. Let $\Gamma$ be a primitive walk such that at least one of the two monomials of $b_{\Gamma}$ is not squarefree. This implies that $\Gamma$ is primitive of type (iii). Hence, by Lemma \ref{primitivewalks}, we know that the leading edge $e$ of $\Gamma$ lies into a bow-tie $\{C_1, p, C_2\}$. Let $G_{\preceq e}$ be the subgraph of $G$ obtained by considering all the edges $e'$ such that $e' \preceq_{\tau} e$. This means that $G_{\preceq e} = \{e_1, e_2, \ldots, e_s = e\}$; hence, $G_{\preceq e}$ is gap-free. Using the notation of Lemma \ref{mainlemma}, we have to consider two different cases.
\begin{itemize}
\item If $e \in p$, consider the edges $\{v_2, v_3\}$ and $\{v'_2, v'_3\}$. Since $G_{\preceq e}$ is gap-free, there exists an edge $\tilde{e} \in E(G)$ which links the edges we are considering and is such that $\tilde{e} \prec_{\tau} e$. By applying Lemma \ref{mainlemma}.(a), we get that $b_{\Gamma} \notin \RGB_{\tau}(I_G)$.
\item If $e = \{v_i, v_{i+1}\}$, consider the edge $\{v'_2, v'_3\}$. Reasoning as before, we discover the existence of an edge $\tilde{e} \in E(G)$ linking these two edges and having the property that $\tilde{e} \prec_{\tau} e$: hence, by applying Lemma \ref{mainlemma}.(b), we get that $b_{\Gamma} \notin \RGB_{\tau}(I_G)$.
\end{itemize}
This ends the proof.
\end{proof}
\end{thm}

As a corollary we recover a result by Ohsugi and Hibi \cite{OHCompressed} about complete multipartite graphs:
\begin{cor}[\cite{OHCompressed}]
If $G$ is a complete multipartite graph, then there exists a doubly squarefree Gr\"obner basis of $I_G$.
\end{cor}
\begin{proof}
The complementary graph of a complete multipartite graph is a disjoint union of cliques and hence is chordal. Applying Theorem \ref{linres} yields the thesis. \endproof
\end{proof}

\begin{rem}
In Theorem \ref{linres} we actually proved that $\RGB_{\tau}(I_G)$
does not contain any binomials corresponding to primitive walks of type (iii). This means in particular that $\RGB_{\tau}(I_G)$ consists entirely of circuits (and hence $I_G$ is generated by circuits, as one could have already noticed applying Theorem 2.6 in Ohsugi and Hibi's article \cite{OHToric}).
\end{rem}

\begin{thm} \label{onesteplin}
Let $G$ be a gap-free graph and order its edges the following way: $\{v_{i_1}, v_{i_2}\} \preceq \{v_{j_1}, v_{j_2}\}$ if and only if $v_{i_1}v_{i_2} \preceq_{\sigma} v_{j_1}v_{j_2}$, where $\sigma$ is an arbitrary graded reverse lexicographic order on $K[v_1, \ldots, v_n]$. Rename the edges so that $e_1 \succ e_2 \succ \ldots \succ e_m$. Let $\tau$ be the lexicographic order on $K[y_1, \ldots, y_m]$ such that $y_1 \succ_{\tau} y_2 \succ_{\tau} \ldots \succ_{\tau} y_m$. Then $in_{\tau}(I_G)$ is generated by squarefree elements.
\begin{proof}
Let $\Gamma$ be a primitive walk of $G$ such that $in_{\tau}(b_{\Gamma})$ is not squarefree and let $e = \{u_1, u_2\}$ be the leading edge of $\Gamma$ with respect to $\tau$. Then, since $\Gamma$ has to be of type (iii), by Lemma \ref{primitivewalks} there exists a bow-tie $\{C_1, p, C_2\}$ containing $e$. We will use the notation of Lemma \ref{mainlemma} to denote the edges of this bow-tie.
\begin{itemize}
\item If $e \in C_1$, then no edges of $C_2$ have vertices in common with $e$. In the following we will say that a vertex $v \in V(|\Gamma|)$ satisfies condition $(<)$ if \[v \prec_{\sigma} u_1, v \prec_{\sigma} u_2.\]
Note that, by definition of $\sigma$ and $\tau$, if an edge $\{w_1, w_2\} \in E(|\Gamma|)$ shares no vertices with $e$, then at least one of $w_1$ and $w_2$ must satisfy condition $(<)$. Since no edges of $C_2$ share vertices with $e$, any pair of consecutive vertices in $C_2$ must include a vertex satisfying condition $(<)$: since $C_2$ is odd, by pigeonhole principle we get that there exists an edge $e'$ of $C_2$ whose vertices both satisfy condition $(<)$.

Since $G$ is gap-free, there exists $\tilde{e} \in E(G)$ linking $e$ and $e'$: moreover, since both vertices of $e'$ satisfy condition $(<)$, one has that $\tilde{e} \prec_{\tau} e$. If $\tilde{e} \neq \{v_1, v'_1\}$ then, by Lemma \ref{mainlemma}.(b), we get that $b_{\Gamma} \notin \RGB_{\tau}(I_G)$. If $\tilde{e} = \{v_1, v'_1\}$, then $v_1 \in e$ and we have to consider two different cases.

\begin{itemize}

\item[$\circ$] If $p$ is made of an even number of edges, then $\Gamma' := \{C_1, p, -\tilde{e}\}$ is a primitive walk of type (ii) such that $in_{\tau}(b_{\Gamma'})$ divides $in_{\tau}(b_{\Gamma})$. Hence $b_{\Gamma} \notin \RGB_{\tau}(I_G)$.

\item[$\circ$] If $p$ is made of an odd number of edges, then consider $\Gamma' := \{C_1, \tilde{e}, C_2, -\tilde{e}\}$. By Proposition \ref{circuits}, $b_{\Gamma'}$ is a circuit and hence $\Gamma'$ is a primitive walk. Since $in_{\tau}(b_{\Gamma'})$ is squarefree and divides $in_{\tau}(b_{\Gamma})$, we get that $b_{\Gamma} \notin \RGB_{\tau}(I_G)$.

\end{itemize}

\item If $e \in p$, we have to discuss two different situations.

If $p$ is made of more than one edge, then at least one of the cycles $C_1$ and $C_2$ has no vertices in common with $e$ (let it be $C_1$ without loss of generality). Then, applying the same pigeonhole reasoning used in the previous case, we discover the existence of an edge $e'$ of $C_1$ whose vertices both satisfy condition $(<)$. Since $G$ is gap-free, there exists $\tilde{e}$ linking $e'$ and $\{v'_2, v'_3\}$. Since $\tilde{e} \prec_{\tau} e$ by construction, applying Lemma \ref{mainlemma}.(a) we get that $b_{\Gamma} \notin \RGB_{\tau}(I_G)$.

The last case standing is the one where $p = \{\{v_1, v'_1\}\} = \{e\}$. Let $\hat{C}_1 := \{v_2, v_3, \ldots, v_{2k+1}\}$, $\hat{C}_2 := \{v'_2, v'_3, \ldots, v'_{2{\ell}+1}\}$. If there exist two consecutive vertices belonging to either $\hat{C}_1$ or $\hat{C}_2$ and satisfying condition $(<)$, then we can apply Lemma \ref{mainlemma}.(a) to infer that $b_{\Gamma} \notin \RGB_{\tau}(I_G)$.
Suppose otherwise. Then condition $(<)$ is satisfied alternately: to be more precise, we have that the vertices of $\hat{C}_1$ (or $\hat{C}_2$) satisfying condition $(<)$ are either the ones with odd index or the ones with even index. We can suppose without loss of generality that $v_3, v_5, \ldots, v_{2k+1}, v'_3, v'_5, \ldots, v'_{2{\ell}+1}$ are the vertices in $\hat{C}_1 \cup \hat{C}_2$ satisfying condition $(<)$. Consider the edges $\{v_2, v_3\}$ and $\{v'_2, v'_3\}$. Since $G$ is gap-free, these edges are surely linked by some edge $\tilde{e}$: if one of $v_3$ and $v'_3$ belongs to $\tilde{e}$ we have that $\tilde{e} \prec_{\tau} e$ and hence, by Lemma \ref{mainlemma}.(a), we can conclude that $b_{\Gamma} \notin \RGB_{\tau}(I_G)$.
What happens if $\tilde{e} = \{v_2, v'_2\}$? If $\tilde{e} \prec_{\tau} e$ we are done for the same reason as before. Suppose $\tilde{e} \succ_{\tau} e$. Then, by definition of $\tau$, at least one of $v_1$ and $v'_1$ (call it $w$) must be such that $w \prec_{\sigma} v_2$ and $w \prec_{\sigma} v'_2$. Since $e$ is the leading edge of $|\Gamma|$, though, one has that $e \succ_{\tau} \{v_1, v_2\}$ and $e \succ_{\tau} \{v'_1, v'_2\}$, hence $v'_1 \succ_{\sigma} v_2$ and $v_1 \succ_{\sigma} v'_2$. This gives us a contradiction. \qedhere
\end{itemize}
\end{proof}
\end{thm}

\begin{rem}
The proof of Theorem \ref{onesteplin} shows also that $\RGB_{\tau}(I_G)$ consists of circuits and hence (as we already knew by \cite[Theorem 2.6]{OHToric}) $I_G$ is generated by circuits. To see this, replace the hypothesis ``$\Gamma$ primitive walk such that $in_{\tau}(b_{\Gamma})$ is not squarefree'' with ``$\Gamma$ primitive walk of type (iii)'' and note that the only primitive walks of type (iii) that may appear in $\RGB_{\tau}(I_G)$ are bow-ties (more precisely, just those with a connecting path of length one). Since binomials associated with bow-ties are circuits by Proposition \ref{circuits}, we are done.
\end{rem}
\begin{rem}
In general, the construction appearing in Theorem \ref{onesteplin} does not necessarily yield a doubly squarefree reduced Gr\"obner basis of $I_G$. For instance, consider the gap-free graph $G$ with $6$ vertices and the following edges: \[\begin{split}&e_1 = \{1, 2\},~e_2 = \{1, 3\},~e_3 = \{2, 3\},~e_4 = \{1, 4\},~e_5 = \{3, 4\}, \\&e_6 = \{1, 5\},~e_7 = \{4, 5\},~e_8 = \{2, 6\},~e_9 = \{3, 6\},~e_{10} = \{5, 6\}.\end{split}\]
Note that the edges are ordered from the biggest to the smallest in a reverse lexicographic way according to the vertex order 1 > 2 > 3 > 4 > 5 > 6 (in the sense explained in the claim of Theorem \ref{onesteplin}).
Let $\tau$ be the lexicographic order on $K[y_1, \ldots, y_{10}]$ such that $y_1 \succ_{\tau} y_2 \succ_{\tau} \ldots \succ_{\tau} y_{10}$. Then \cocoa~computations yield \[\begin{split}\RGB_{\tau}(I_G) = \{&y_1y_{10} - y_6y_8,~y_1y_5 - y_3y_4,~y_1y_9 - y_2y_8,~y_5y_{10} - y_7y_9,~y_2y_7 - y_5y_6,\\&y_2y_{10} - y_6y_9,~y_3y_4y_{10} - y_5y_6y_8,~y_2y_5y_8 - y_3y_4y_9,~\boxed{y_3y_4y_7y_9 - y_5^2y_6y_8}\}.\end{split}\]
\end{rem}

\section*{Acknowledgements}
The author would like to thank his advisor Aldo Conca, Matteo Varbaro and the referee for their valuable comments and suggestions.


TITLE: How to solve a matrix for the span of columns.
QUESTION [0 upvotes]: Having trouble with the problem shown above ^. I put that matrix and solved it in it's reduced echloen form and got this:
$$
\begin{bmatrix}
1 & 0 & -13 \\
0 & 1 & 6\\
0 & 0 & 0 \\
\end{bmatrix}
\quad
$$
But I don't know how this helps me because the answer is:

How did they get that answer? Thanks.

REPLY [2 votes]: Apply the reduced Echelon form to the $augmented$ matrix:  $$
\begin{bmatrix}
2 & 5 & 4 & b_{1}\\
1 & 2 & -1 & b_{2}\\
-1 & -1 & 7  & b_{3}\\
\end{bmatrix}
\quad
$$
This will give $$
\begin{bmatrix}
1 & 0 & -13 & -2b_{1}+5b_{2}\\
0 & 1 & 6 & b_{1}-2b_{2}\\
0 & 0 & 0  & b_{1}-3b_{2}-b_{3}\\
\end{bmatrix}
\quad
$$
Thus the solution to the system will be $x_{1}-13x_{3}=-2b_{1}+5b_{2},$ $x_{2}+6x_{3}=b_{1}-2b_{2}$ and $b_{1}-3b_{2}-b_{3}=0.$ In other words, provided that $b_{1}-3b_{2}-b_{3}=0$ then there will be infinitely many solutions. See here for examples of augmented matrices.


TITLE: Why are the real numbers usually ordered the way they are?
QUESTION [0 upvotes]: How do we get the usually used form of $<$ (i.e. $\dots-3<-2<-1<0<1<2<3\dots$) on the real number field, defined as the Dedekind complete totally ordered field?
Why isn't it e.g. $\dots-3<-2<1<2<0<-1<4<5\dots$? $0$ is defined as the additive identity of $\mathbb{R}$ and $1$ as this set's multiplicative identity. I'm especially curious about why the additive and multiplicative identities are placed the way they are.

REPLY [3 votes]: They aren't placed there. They were already there. Natural numbers were for counting. If you want to count backwards, you would need to extend to integers. If you want to count in halves or thirds and so on, you would need to extend to rationals. Finally, if you have a sequence of rationals that 'converge' (such as Cauchy sequence), you need real numbers otherwise the 'limits' would not exist. So where $0$ and $1$ end up in the real line is simply where they started off in the natural number sequence. They didn't choose to have particular locations in the real line, nor did we. All those intervening rationals and reals just 'happen' to fill the 'gap' in between $0$ and $1$.

REPLY [1 votes]: What kind of properties do you want real numbers to have? For example, if you require $x^2 > 0$ for all $x \neq 0$, then you get $1 = 1^2 > 0$.
Looking a bit more deeply, in Dedekind's cut, you want to "fill the gap" between rationals, so to speak. Therefore, it will be preferable if the addition, subtraction, order relations etc of real numbers behave the same way they do for rationals. How will you decide the properties for rationals? Well, they come from natural numbers, which has a (tentative) basis in "counting", and we all "know" 2 is greater than 1!
If you want a bottoms up view of the whole construction, consult Terence Tao's Analysis I. It is an excellent read once you have some exposure to limits (it might tear down some preconceived notions, at least it did in my case. Boy, was that a learning experience!!!)
This is how I eventually made my peace with real numbers: we have certain expectations of their behavior, so what will you need to concretely define them and retain those expectations?
Bottom line (personal opinion), we don't construct reals, rather we construct axioms that describe real number system logically.


TITLE: Closed form solution of a definite integral?
QUESTION [2 upvotes]: I've never heard of a closed form solution, and I had this assigned to me and it is supposed to be 'review'. Could somebody at least get me pointed in the right direction here?
'Provide a closed form solution for the following definite integrals'
$$\int_0^\infty xe^{-x^2}\ dx$$
$$\int_0^\infty x^2e^{-x}\ dx$$

REPLY [4 votes]: Hint: It is a fancy way of asking you to compute the two integrals.
For the first question, make the substitution $u=x^2$.  After a while you should get $1/2$.
For the second, integrate by parts twice.  For the first integration by parts, let $u=x^2$ and $dv=e^{-x}\,dx$.


TITLE: How should I define random variable when doing an experiment?
QUESTION [0 upvotes]: I have difficulty understanding the relationship between probability function and random variable. Suppose the case where 2 people are selected out of 100 people. Then the sample space is $\{a_1,\ a_2,\ \cdots\,\ a_{100}\}^2$, the probability of choosing each ordered pair will be equal to 1/10000.
I want to find the sum of the ages of the two selected people. So where should each person's age be set? Perhaps I can set the random variable to be the sum of the ages of the two selected people. But where does the valuation for the chosen outcome come from? I was thinking of putting the sample space to a set like $\{13,\ 42,\ 31,\ 66,\ ...\}^2$, but the set doesn't allow duplicate values, which seems inappropriate. How can I construct the probability space in this case?

REPLY [0 votes]: If you have a 100 people and their ages then you have $\binom{100}{2}$ pairs of people. So your probability space should be the $\binom{100}{2}$ pairs of ages (of course there might be duplicates so that makes it more likely to have a particular pair and corresponding sum). Then the random variable $X$ would take the sum of the values in the pair.