TITLE: Probability - errors in lines
QUESTION [0 upvotes]: I am really stumped on how do do this question:

A page of typescript contains $40$ lines, with $80$ characters per line. Each character has probability $p=0.001$ (independently of the others) of being erroneous.
a) What is the probability that a particular line contains no errors (i.e., no erroneous characters)?
  b) What is the probability that a particular line contains more than one error?
  c) What is the probability that the page contains exactly two errors?
  d) Given that the page contains exactly two errors, what is the probability that they occur on separate lines?

I have no idea how to start this this off. Could you give a few hints please? I've learned about random variables if that is relevant.

REPLY [0 votes]: I am posting because I believe there is a subtle flaw in the posted answer to part $(d)$
The subtle flaw is that when you count the number of ways using stars and bars, each such way is not equiprobable You could have a look at the answers to a question here
Another point is that for such a problem, I would think that you may be expected to use the poisson distribution here , which would be sufficiently accurate, e.g.
$\lambda$ for line $=80\times0.001 = 0.08\;;$
$P(x) = e^{-\lambda}\cdot\lambda^x /x!$
P($0$ error in line) $= e^-0.08 = 0.9231$
P($1$ error in line) $= e^-0.08(0.08) = 0.0739$
which can be seen to tally with the binomial computation.
Similarly, for a line, $\lambda = 40\cdot 0.08 = 3.2$,
P(page has $2$ errors) = $e^-3.2*3.2^2/2! = 0.2087$

Coming back to part $(d)$, we needn't actually use numerical values, use $\lambda$ for the parameter for a line and $40\lambda$ as parameter for page. This will simplify computations, and also yield a more accurate result.
P($2$ lines have $1$ error, $38$ have $0$ error) $= \binom{40}{2}*Le^{-L}*Le^{-L}*e^{-38L} = 780L^2e^{-40L}$
P(one line has $2$ errors, $39$ have $0$ errors) $=\binom{40}1*(L^2/2)*e^{-L}*e^{-39L} = 20L^2e^{-40L}$
As a check, P(page has $2$ errors) $= 800L^2e^{-40L}$
[ If we put $P = 40L$, P(page has $2$ errors) $= e^{-P}* P^2/2 = 800L^2e^{-40L}$ ]
Finally, P(errors on separate lines | $2$ errors on page) $= \frac{780L^2e^{-40L}}{800L^2e^{-40L}} = 0.975$


TITLE: On $ X = (0,1) \times (0,1) $ with anti lexicographic order topology find the character of topological space $X$ ( anti lexicographic order
QUESTION [2 upvotes]: On $ X = (0,1) \times (0,1) $ with anti lexicographic order topology find the character of topological space $X$  ( anti lexicographic order : $(x_1,y_1) < (x_2,y_2) \iff y_1 < y_2 \text{ or } ( \ y_1 = y_2 \text{ and } \ x_1<x_2 ) $.
I could use at least a hint.
Definition of character: https://proofwiki.org/wiki/Definition:Character_of_Point_in_Topological_Space

REPLY [1 votes]: For $(x,y)\in X$ the sub-space $Y_y=(0,1)\times \{y\}$ is open in $X$ and is homeomorphic to $(0,1),$ which  is $1$st-countable. In any space $X,$ if $p\in Y\subset X$ where $Y$ is a $1$st-countable open sub-space of $X$ then $p$ has countable character in $X.$
Note : $(x,y)$ denotes an ordered pair but $(0,1)$ denotes an  interval.


TITLE: Conceptually, why does a positive definite Hessian at a specific point able to tell you if that point is a maximum or minimum?
QUESTION [13 upvotes]: This is not about calculating anything. But can anyone tell me why this is the case?
So, from wikipedia:

If the Hessian is positive definite at x, then f attains a local minimum at x. If the Hessian is negative definite at x, then f attains a local maximum at x. If the Hessian has both positive and negative eigenvalues then x is a saddle point for f. Otherwise the test is inconclusive. This implies that, at a local minimum (resp. a local maximum), the Hessian is positive-semi-definite (resp. negative semi-definite).

Can someone explain, intuitively, why this is the case?

REPLY [1 votes]: This is because of Taylor's formula  at order $2$:
\begin{align*}f(x+h,y+k)-f(x,y)&=hf'_x(x,y)+kf'_y(x,y)\begin{aligned}[t]&+\frac12\Bigl(h^2f''_{x^2}(x,y)+2hkf''_{xy}(x,y)\\&+k^2f''_{y^2}(x,y)\Bigr)+o\bigl(\bigl\lVert(h,k)\bigr\rVert^2 \bigr)\end {aligned}\\
&=\frac12\Bigl(h^2f''_{x^2}(x,y)+2hkf''_{xy}(x,y)+k^2f''_{y^2}(x,y)\Bigr)+o\bigl(\bigl\lVert(h,k)\bigr\rVert^2 \bigr)
\end{align*}
If the quadratic form $\;q(h,k)=\frac12\Bigl(h^2f''_{x^2}(x,y)+2hkf''_{xy}(x,y)+k^2f''_{y^2}(x,y)\Bigr)$ is positive definite, the sign of the left-hand side is positive for all $\lVert(h,k)\bigr\rVert^2$ small enough, hence $f(x+h,y+k)-f(x,y)>0$, so we have a local minimum. If it is definite negative, for the same reasons, we have a local maximum.


TITLE: uniformly bounded sequence of non constant holomorphic functions
QUESTION [2 upvotes]: Let $\{f_n\}_{n=1}^{\infty}$ be a uniformly bounded sequence of nonconstant holomorphic functions in a connected open set $\Omega$. Let $f \not \equiv 0 $ be a holomorphic function in $\Omega$. Suppose that the equation
$nf(z) = f_n(z) + \ln{n}$
does not have any roots in $\Omega$ for $n =1,2,\ldots$. Prove that then $f$ does not have any zeros in $\Omega$.

REPLY [2 votes]: Suppose $f(z_0)=0$. Pick $r>0$ so that $f\ne 0$ when $|z-z_0|=r$.    Apply Rouche's theorem in the disk $D=\{z: |z-z_0|\le r\}$ to the function
$$nf(z) - (f_n(z)+\ln n)\tag{1}$$
The theorem applies when $n$ is large enough, because $|nf(z)|>|f_n(z)+\ln n|$ on the boundary of $D$.
Why?

  Let $m=\min_{\partial D} |f|$ and $M=\sup_{n,z} |f_n(z)|$; observe that $mn>M+\ln n$ when $n$ is large enough.)

This is a contradiction, since (1) is assumed not to have zeros.


TITLE: Did Zariski really define the Zariski topology on the prime spectrum of a ring?
QUESTION [23 upvotes]: The question is not: “Did Zariski really define the Zariski topology?”
It is:  “Did Zariski really define the Zariski topology on the prime spectrum of a ring?”
Here is the motivation. --- On page 80 of
Grothendieck, Alexander, Éléments de géométrie algébrique (rédigés avec la collaboration de Jean Dieudonné) : I. Le langage des schémas. Publications Mathématiques de l'IHÉS, 4 (1960), p. 5-228,
availablable here, one reads:

L'introduction de cette topologie en géométrie algébrique est due à Zariski. Aussi est-elle souvent appelée la « topologie de Zariski » de $X$.
The introduction of this topology in algebraic geometry is due to Zariski. This is why it is often called the  “Zariski topology“ of $X$.

The set $X$ is of course the prime spectrum of a ring.
EDIT. Theo Buehler has just posted a question inspired by Qiaochu's answer below. The title of Theo’s question is:
Was Grothendieck familiar with Stone's work on Boolean algebras?

REPLY [1 votes]: According to Kohls, it was Neal H. McCoy who first introduced the Zariski topology to the prime spectrum in a 1949 paper.


TITLE: Continued Fraction: Why do we get with $\gamma \in \mathbb{R}\setminus \mathbb{Q}$ the CF $\frac{1}{\gamma}=\langle0;a_0,a_1,\dotsc\rangle$
QUESTION [0 upvotes]: I have a question concerning continued fractions:
If we have $\gamma \in \mathbb{R} \setminus \mathbb{Q}$ and $\gamma=\langle a_0;a_1,a_2,\dotsc\rangle$. Why do we get
$$\frac1\gamma = \langle 0;a_0,a_1,\dotsc\rangle$$
Furthermore, how can I get the continued fraction of $\langle 0;\overline1 \rangle$?
Any help is appreciated.

REPLY [2 votes]: For the second question, let $x=\langle 0\;;\overline{1}\rangle$. Then $$x=\frac1{1+\frac1{1+\frac1{\quad\ddots}}}=\frac1{1+x}\,,$$ so $x(1+x)=1$. Solving this quadratic equation and noting that clearly $x>0$, we have $$\langle 0\;;\overline{1}\rangle=\frac{-1+\sqrt5}2\,;$$ this is $\varphi-1$, where $\varphi$ is the so-called golden ratio.
Now see if you can apply the same technique to show that if $\gamma=\langle a_0;a_1,a_2,\dots\rangle$. Then $\langle 0\;;a_0,a_1,\dots\rangle=\frac1\gamma$.


TITLE: Use the fact that $2$ is a primitive root modulo $101$ to find all solutions to $x^7\equiv-2\pmod{101}$
QUESTION [1 upvotes]: Use the fact that $2$ is a primitive root modulo $101$ to find all solutions to $$x^7\equiv-2\pmod{101}.$$

My number theory book says to compare powers of $2$ to $101$ to express $-2$ as a power of $2$ modulo $101$. I have computed powers of $2$ up to $40$ where my calculator loses accuracy so I have to assume there is some trick that I'm missing. I have read all through this chapter but I cannot find it for the life of me.

REPLY [0 votes]: Using discrete logarithm
$7$ind$_2x\equiv 1+\dfrac{\phi(101)}2\pmod{100}\equiv51\equiv-49$
$\implies$ind$_2x\equiv-7\pmod{100}\equiv93$ as $(7,100)=1$
$\implies x\equiv2^{93}\pmod{101}$


text:
\begin{document}

\title{Bessenrodt-Stanley polynomials and the octahedron recurrence}
\author{Philippe Di Francesco}
\address{
Department of Mathematics, University of Illinois at Urbana-Champaign, MC-382,
1409 W\ Green St., Urbana, IL 61801, U.S.A.
e-mail: philippe@illinois.edu
}

\begin{abstract}
We show that a family of multivariate polynomials recently introduced by Bessenrodt and Stanley can be expressed as solution
of the octahedron recurrence with suitable initial data. This leads to generalizations and explicit expressions as path or dimer partition functions.
\end{abstract}

\date{\today}
\maketitle

\tableofcontents

\section{Introduction}

In a recent publication, Bessenrodt and Stanley \cite{BS} introduced a family of multivariate polynomials attached to any
partition $\lambda$, generalizing a construction by Berlekamp \cite{BKP}. These were defined as weighted sums over sub-diagrams
of the Young diagram of $\lambda$.

In this paper, we show that these polynomials
may be viewed as the restriction of particular solutions of the octahedron recurrence relation in a three-dimensional half-space. The octahedron
recurrence is a special case of so-called $T$-system, introduced in the context of generalized Heisenberg integrable quantum
spin chains with Lie group symmetries \cite{KNS,KNS11}.
The octahedron recurrence has received much attention over the last decade for its combinatorial interpretation in terms of
domino tilings of the  Aztec diamond \cite{CEP} and generalizations thereof \cite{SPY,Henriques,DF,DFK12,DF13,DSG14}.
More generally, the $A$ type $T$-systems possess the positive Laurent property: their solutions may be expressed
as Laurent polynomials of any admissible initial data, with non-negative integer coefficients.
In Ref.\cite{DFK08}, this property of the $T$-systems was connected to an underlying cluster
algebra structure \cite{FZI}, and further confirmed by providing an explicit solution based on some representation using a flat
two-dimensional connection \cite{DF}, leading to expressions as partition function of weighted paths on oriented graphs or networks,
or equivalently of weighted dimer coverings of suitable bipartite planar graphs.

Our punchline is the following: the polynomials of Bessenrodt and Stanley were shown to obey particular determinantal identities \cite{BS},
which we interpret as initial conditions for the half-space octahedron recurrence, for which the partition $\lambda$ determines the geometry of the initial
data. Reversing the logic, and fixing the values of
these determinants, we may express the solutions of the octahedron recurrence
as Laurent polynomials thereof, as path or dimer partition functions from \cite{DF,DF13}.
This produces a general family of multivariate Laurent polynomials attached to any partition, that reduce to the polynomials of \cite{BS}, for special
choices of the initial data.

The paper is organized as follows.
In Section 2 we describe our new family of multivariate Laurent polynomials attached to a partition $\lambda$, and how they reduce
to the polynomials of \cite{BS}.
Section 3 is devoted to
a survey of the $T$-system and its general solutions in terms of network partition functions. We describe in particular the structure of admissible initial data, which take the form of initial value assignments along a ``stepped surface", and show how this data encodes an oriented weighted graph or network.
In Section 4, we show that the situation of \cite{BS} corresponds to choosing a particular ``steepest" initial data stepped surface, that forms a kind of fixed slope roof above the Young diagram of $\lambda$. The corresponding network is particularly simple, as it takes the shape of the Young diagram itself. Using the explicit solutions of the $T$-system, we write the solutions first as network partition functions (Theorem \ref{thpath},
Sect.4.3) and then as
dimer partition functions (Theorem \ref{thdim}, Sect.4.4).
Section 5 is devoted to a 3D generalization of the multivariate polynomials, by simply expressing the other solutions of the $T$-system ``under the roof". This leads us to a 3D object we call the pyramid of $\lambda$, to the boxes of which we associate other Laurent polynomials.
The latter reduce to polynomials when we apply the previous restriction of initial data. These are first expressed as  partition functions for families of non-intersecting paths on the same networks as before (Sect.5.3), and then shown to restrict to sums over nested
sub-partitions of $\lambda$ with the same weights as before (Theorem \ref{genBS}, Sect.5.4).
We gather a few concluding remarks in Section 6, where we present a different generalization for other boundary conditions of the octahedron recurrence.

\vskip1.cm

\noindent{\bf Acknowledgments}. We would like to thank R. Stanley for an illuminating seminar during the conference
``Enumerative Combinatorics" at the Mathematisches  ForschungsInstitut Oberwolfach in March 2014 and A. Sportiello for his great
help in the early stage of this work. This work is supported by the NSF grant DMS 13-01636 and the
Morris and Gertrude Fine endowment.

\section{A family of Laurent polynomials associated to Young diagrams}

We consider partitions/Young diagrams of the form $\lambda=(\lambda_1,...,\lambda_N)$ with $\lambda_i$ boxes in row $i$, and
$\lambda_1\geq \lambda_2\geq \cdots\geq \lambda_N\geq 1$. We represent the Young diagram $\lambda$ with rows
$1,2,...,N$ from top to bottom and justified on the left. The boxes of the diagram $\lambda$ are labeled by their coordinates
$(i,j)$, where $i\in [1,N]$ is the row number and $j\in [1,\lambda_i]$ the horizontal coordinate within the $i$-th row.
We write $(i,j)\in \lambda$ when the box $(i,j)$ belongs to $\lambda$. For later use, for any $(a,b)\in \lambda$, we
define the sub-diagram $\lambda_{a,b}\subset \lambda$ obtained by erasing all the boxes of $\lambda$ that are above
the row $a$ and to the left of the column $b$ (it is the intersection of the South East corner from $(a,b)$ with $\lambda$).

We also consider the extended Young diagram $\lambda^*$ associated to $\lambda$, obtained by adjoining a border strip
from the end of the first row to the end of the first column of $\lambda$, namely with
$\lambda_1^*=\lambda_1+1$,
$\lambda_i^*=\lambda_{i-1}+1 $, $i=2,...,N+1$.
For instance the extended diagram of $\lambda=(3,2)$ is $\lambda^*=(4,4,3)$. Note that $\lambda$ can be recovered from $\lambda^*$
by removing its first row and column.
We define the squares $S_{a,b}$ of $\lambda^*$ to be the square arrays of the form
$S_{a,b}=\{ (i,j), \, a\leq i\leq n_{a,b}+a-1, \, b\leq j\leq n_{a,b}+b-1\}$, and such that $S_{a,b}\subset \lambda^*$
and $n_{a,b}\geq 1$ is maximal.
The
box $(a,b)$ is called the North West (NW) corner of the square $S_{a,b}$. In other words, the square $S_{a,b}$ is the largest
square array of boxes with NW corner $(a,b)$ that fits in $\lambda^*$. The integer $n_{a,b}$ is called the size of $S_{a,b}$.
In particular, each box $(u,v)$ of the border strip
$\lambda^*\setminus \lambda$ is itself a square of size $1$, $S_{u,v}=\{(u,v)\}$.

\begin{defn}\label{lopdef}
We fix arbitrary non-zero parameters $\{\theta_{i,j}\}_{(i,j)\in \lambda^*}$ attached to the boxes of $\lambda^*$.
We now associate to each box $(i,j)\in \lambda^*$ a function $p_{i,j}\equiv p_{i,j}(\theta_\cdot)$ of all the parameters $\theta_{i,j}$
defined by  the identities:
\begin{equation}\label{condet} \det\left(\left( p_{a+i-1,b+j-1}(\theta_\cdot) \right)_{1\leq i,j \leq n_{a,b}}\right)
=\theta_{a,b}\qquad {\rm for}\, {\rm all}\, (a,b)\in \lambda^*
\end{equation}
namely we fix the value of the determinant of the array of functions $p_{i,j}(\theta_\cdot)$ on each square $S_{a,b}$ to be the parameter $\theta_{a,b}$.
\end{defn}

In particular, we have $p_{u,v}(\theta_\cdot)=\theta_{u,v}$ for all $(u,v)\in \lambda^*\setminus\lambda$.  That \eqref{condet} determines
the $p_{i,j}$'s uniquely will be a consequence of the rephrasing of the problem as that of finding the solution
of the $T$-system or octahedron recurrence, subject to some particular initial condition. As a consequence of the positive
Laurent property of the $T$-system,  we have the following main result:

\begin{thm}\label{main}
For all $(a,b)\in \lambda$, the function $p_{a,b}(\theta_\cdot)$ is a Laurent polynomial of the $\theta_{i,j}$'s with non-negative integer coefficients.
\end{thm}

\begin{example}\label{firstex}
Let us consider the Young diagram $\lambda=(2,1)$, with the following $\theta$ variables (one per box of $\lambda^*=(3,3,2)$):
$$ \begin{matrix} \theta_{1,1}=a & \theta_{1,2}=b & \theta_{1,3}=c \\
\theta_{2,1}=d & \theta_{2,2}=e & \theta_{2,3}=f \\
\theta_{3,1}=g & \theta_{3,2}=h & & \end{matrix} $$
The polynomials $p_{a,b}(\theta_\cdot)$ are:
$$\begin{matrix}
p_{1,1}=\frac{a f h+(b+c e)(d+e g)}{e f h}
& p_{1,2}=\frac{b+c e}{f} & p_{1,3}=c \\
p_{2,1}=\frac{d+e g}{h} & p_{2,2}=e & p_{2,3}=f \\
p_{3,1}=g & p_{3,2}=h & & \end{matrix} $$

\end{example}

The Laurent polynomials $p_{a,b}(\theta_\cdot)$ attached to the Young diagram $\lambda$ reduce to the polynomials introduced by
Bessenrodt and Stanley in \cite{BS} when the variables $\theta_{i,j}$ are restricted as follows. Let $x_{i,j}$, $(i,j)\in \lambda$ be new variables
attached to the boxes of $\lambda$.

\begin{thm}\label{restrictoBS}
Under the restrictions:
\begin{eqnarray}
\theta_{i,j}&=&1 \qquad {\rm for}\, {\rm all}\, (i,j)\in \lambda^*\setminus \lambda \ ,\nonumber \\
\theta_{a,b}&=& \prod_{r=0}^{n_{a,b}-1} \prod_{(i,j)\in \lambda_{a+r,b+r}} x_{i,j} \quad {\rm for}\, {\rm all}\, (a,b)\in \lambda\, , \label{bsrestrict}
\end{eqnarray}
the Laurent polynomials $p_{a,b}(\theta_\cdot)$ of Def.\ref{lopdef} reduce to the polynomials $p_{a,b}(x_\cdot)$ of \cite{BS}.
\end{thm}
In particular, the change of variables cancels all denominators and produces a {\it polynomial} of the variables $x_{i,j}$.

In Section \ref{applione}, we shall construct each polynomial $p_{a,b}(\theta_\cdot)$ explicitly, as the partition function for paths on a weighted
oriented graph (network) ${\mathcal N}_{a,b}$ associated to $\lambda_{a,b}$, and alternatively as the partition function of the dimer model on a suitable bipartite graph ${\mathcal G}_{a,b}$. We give two independent proofs of Theorem \ref{restrictoBS} in Sect.\ref{sectobs}.

\section{$A_{\infty/2}$ $T$-system and its solutions}\label{tsysect}

\subsection{$T$-system and initial data}

In the case of $A$ type
Lie algebras, the $T$-system takes the form (also known as the octahedron recurrence):
\begin{equation}\label{octa}
T_{i,j,k+1}T_{i,j,k-1}=T_{i+1,j,k}T_{i-1,j,k}+T_{i,j+1,k}T_{i,j-1,k}
\end{equation}
where the indices of the indeterminates $T_{i,j,k}$ are restricted to be vertices of the Face-Centered Cubic (FCC) lattice
$L_{FCC}=\{(i,j,k)\in \Z^3,\, i+j+k=1\, {\rm  mod}\,  2\}$. This may be viewed as a 2$+$1-dimensional evolution in the discrete
time variable $k$, while $i,j$ refer to space indices.

The $A_r$ condition consists in further restricting
$i\in [1,r]$, and to impose the additional
boundary conditions
\begin{equation}\label{affcond} T_{0,j,k}=T_{r+1,j,k}=1 \qquad (j,k\in \Z)\end{equation}
In other words, the $A_r$ $T$-system solutions are those of the octahedron equation in-between two parallel planes $i=0$ and $i=r+1$,
that take boundary value $1$ along the two planes $i=0$ and $i=r+1$.

In the following, we will concentrate on the so-called $A_{\infty/2}$ $T$-system, where we only keep the restriction $i\geq 1$
and the boundary condition
\begin{equation}\label{plus} T_{0,j,k}=1\end{equation}
In turn, the solutions of the $A_{\infty/2}$ $T$-system are those of the octahedron equation in the half-space $i\geq 0$, that take
boundary values $1$ along the plane $i=0$.

The system (\ref{octa},\ref{plus}) must be supplemented by some admissible initial data $(\bk,\bt)$, consisting of:
\begin{itemize}
\item{}
(1) a ``stepped surface"
$\bk=\{ (i,j,k_{i,j})\}_{i\in\Z_+;j\in\Z}$, such that $|k_{i+1,j}-k_{i,j}|=|k_{i,j+1}-k_{i,j}|=1$ for all $i,j$;

\item{}
(2) the following assignments of initial values $\bt=\{t_{i,j}\}_{i\in \Z_{>0};j\in \Z}$:
\begin{equation}T_{i,j,k_{i,j}}=t_{i,j} \qquad (i\in \Z_{>0};j\in Z) \end{equation}
\end{itemize}

\subsection{Solution}

In Ref. \cite{DF} the $A_r$ $T$-system was solved for arbitrary $r$ and arbitrary initial data. Note that for any finite $(i,j,k)$
above the initial data stepped surface (i.e. $k\geq k_{i,j}$), the solution $T_{i,j,k}$ only depends on finitely many
initial values $t_{i,j}$, hence for $r$ large enough  the solution is independent of $r$, so that the solution
for the case $A_{\infty/2}$ is trivially obtained from that of $A_r$. We now describe this solution.

The solution proceeds in two steps. First, one eliminates all the variables $T_{i,j,k}$ for $i\geq 2$ in terms of the
values $T_{j,k}:=T_{1,j,k}$ by noticing that the relation \eqref{octa} is nothing but the Desnanot-Jacobi (aka Dodgson condensation)
formula for the following Hankel or discrete Wronskian determinants:
\begin{equation}
W_{i,j,k}=\det\left(\left(T_{j+b-a,k+i+1-a-b}\right)_{1\leq a,b\leq i}\right)
\end{equation}
which, together with the initial condition $W_{0,j,k}=1$ allows to identify
\begin{equation}\label{wrons} T_{i,j,k}=W_{i,j,k}
\end{equation}
for all $i\geq 2$.

The second step consists of writing a compact form for $T_{j,k}$ for all $k\geq k_{1,j}$, by use of a formulation of the relation
\eqref{octa} as the flatness condition for a suitable $GL_2$ connection. The solution is best expressed in the following manner.
First we associate to the initial data stepped surface $\bk$ a bi-colored (grey/white) triangulation with the vertices of $\bk$,
defined via the following local rules, where we indicate the value of $k_{i,j}$ at each vertex
of the projection onto the $i,j$ plane:
\begin{equation}\label{eqrules}
\raisebox{-1.1cm}{\hbox{\epsfxsize=14.cm \epsfbox{rules.eps}}}
\end{equation}
The last two cases give rise to two choices  of triangulations each, due to the tetrahedron ambiguity (there are two ways of defining
a pair of adjacent triangles with the vertices of a regular tetrahedron, namely the two choices of diagonals of the white/grey square
in projection), but our construction is independent of these choices.
We may now decompose the stepped surface into lozenges made of a grey and a white triangle sharing an edge perpendicular to
the $k$ axis, and we supplement the single triangles of the bottom layer $i=1,2$ with a lower triangle of
opposite color with bottom vertex in the $i=0$ plane.

\begin{example}\label{flatex}
Let us consider the ``flat" initial data surface $\bk_0$ with $k_{i,j}=i+j +1\, {\rm mod} \, 2\in \{0,1\}$. Picking a particular choice
of diagonal in the tetrahedron ambiguities, we may decompose the surface as follows:
$$ \raisebox{1.1cm}{\hbox{\epsfxsize=7.cm \epsfbox{tdec.eps}}}    $$
where we have represented with solid (resp empty) dots the vertices with $k=1$ (resp. $k=0$).
\end{example}

To each lozenge, we associate a $2\times 2$ matrix according to the following rule:
\begin{equation}
\raisebox{-1.2cm}{\hbox{\epsfxsize=2.cm \epsfbox{ulozenge.eps}}}\to  U(a,b,c)=\begin{pmatrix} 1 & 0 \\ \frac{c}{b} & \frac{a}{b} \end{pmatrix}\qquad
\raisebox{-1.4cm}{\hbox{\epsfxsize=2.cm \epsfbox{vlozenge.eps}}}\to V(c,a,b)=\begin{pmatrix} \frac{a}{b} & \frac{c}{b}  \\0 & 1 \end{pmatrix}
\end{equation}
Note that the arguments $a,b,c$ of the matrices are the values of initial data attached to the three vertices of the grey lozenge.
These matrices have the remarkable property that they form a flat connection on the solutions of the $T$-system, namely we have
\begin{equation}\label{flat}V(u,a,b)\, U(b,c,v)=U(a,x,v)\, V(u,x,c)\qquad {\rm iff}\qquad xb=ac+uv \end{equation}
For some fixed integer $r$ (large enough), we may embed the above matrices in $r$-dimensional space, by defining the
$(r+1)\times (r+1)$ matrices
$U_i,V_i$, equal to the $(r+1)\times (r+1)$ identity matrix, with the central $2\times 2$ block with row and column labels $i,i+1$ replaced by $U,V$.
The position $i$ corresponds to the $i$ coordinate of the two middle vertices of the corresponding lozenge.
We now associate to each ``slice" $S=[0,r+1]\times [j_0,j_1]$ of the initial data surface namely with vertices $\{(i,j,k_{i,j})_{i,j\in S}\}$
the matrix $M(j_0,j_1)$ equal to the product over all lozenge matrices of the slice, taken in the order of appearance of the lozenges from left to right.
This matrix is independent of the choices pertaining to the tetrahedron ambiguity above.

Given any $j,k$ with $k\geq k_{1,j}$, let us define the left (resp. right) projections $j_0$ (resp. $j_1$) onto the stepped surface $\bk$
to be the largest (resp. smallest) integer $\ell$ such that $j-\ell=k-k_{1,\ell}$ (resp. $j-\ell=k_{1,\ell}-k$). This is illustrated below:
$$\raisebox{0.0cm}{\hbox{\epsfxsize=10.cm \epsfbox{proj.eps}}} $$
where we have represented by empty dots the vertices of the intersection of the stepped surface $\bk$ with the $i=1$ plane.
Finally the solution $T_{j,k}$ may be written
as:
\begin{equation} T_{j,k}=M(j_0,j_1)_{1,1} \, t_{1,j_1}\end{equation}
independently of $r$ for $r$ large enough. The proof in \cite{DF} relies on the flatness condition \eqref{flat}.
Note that the positive Laurent property for $T_{j,k}$ as a function of the initial data $\{t_{i,j}\}$ is manifest,
as the entries of the matrices $U,V$ are themselves Laurent monomials of the initial data with coefficient 1 or 0.

\subsection{Network interpretation}

The matrix $M(j_0,j_1)$ can be interpreted as the weighted adjacency matrix of some oriented graph $N(j_0,j_1)$
(referred to as a ``network"), constructed as follows. First interpret the matrices $U_i,V_i$ as elementary ``chips":
\begin{equation}\label{rep2UVi}
U_i(a,b,u)=
\raisebox{-.4cm}{\hbox{\epsfxsize=2.2cm \epsfbox{Ui2.eps}}}\qquad V_i(v,a,b)=
\raisebox{-.9cm}{\hbox{\epsfxsize=2.2cm \epsfbox{Vi2.eps}}}
\end{equation}
with two entrance connectors $i,i+1$ on the left and two exit connectors $i,i+1$ on the right, and such that the $(x,y)$ matrix
element is the weight of the oriented edge form entry connector $x$ to exit connector $y$ (here by convention all edges
will be oriented from left to right). Note we have represented by a dashed line the ``trivial" oriented edges with weight $1$.
The top edge in the $U_i(a,b,u)$ chip has therefore weight $a/b$, the diagonal one $u/b$, etc. The arguments $a,b$, etc. appear
as face variables in the network. Any product of such matrices can be interpreted as a larger network, obtained by concatenating
the corresponding chips. We call $N(j_0,j_1)$ the network corresponding to the matrix $M(j_0,j_1)$.
Now we may interpret the matrix element $M(j_0,j_1)_{1,1}$ as the partition function for paths on $N(j_0,j_1)$
from the leftmost entry connector $1$ to the rightmost exit connector $1$. This give a nice explicit combinatorial description of
the solution $T_{j,k}$ in terms of the initial data $\{t_{i,j}\}$, which form the face labels of the network $N(j_0,j_1)$. This is summarized in
the following:

\begin{thm}\label{netsol}
The solution $T_{1,j,k}=T_{j,k}$ of the $A_{\infty/2}$ $T$-system with initial data $(\bk,\bt)$ is $t_{1,j_1}$ times
the partition function of paths from
the entry connector $1$ to exit connector $1$ on the network $N(j_0,j_1)$, where $j_0,j_1$ are the left/right projections of $(j,k)$
onto the onto the stepped surface $\bk$.
\end{thm}

In \cite{DF}, it was further shown that $T_{i,j,k}$ for $i\geq 2$ is proportional to the partition functions of $i$ non-intersecting
paths on the network $N(j_0,j_1)$. As such, it enjoys the positive Laurent property as well.

\begin{example}
The network $N$ corresponding to a sample slice $S$ of flat initial data surface (see Example \ref{flatex}) reads:
$$ \raisebox{1.1cm}{\hbox{\epsfxsize=14.cm \epsfbox{tnet.eps}}}    $$
where we have represented the face labels in a sample row. Note also that due to the $A_{\infty/2}$
boundary condition \eqref{plus}, all the vertex/face values on the bottom row/lower face are equal to $1$.
The quantity $T_{j,k}/T_{j_1,k_{1,j_1}}$ is the partition function for paths from entry connector $1$ to exit connector $1$
on the network. We show here a sample such path, together with its local step weights:
$$ \raisebox{1.1cm}{\hbox{\epsfxsize=8.cm \epsfbox{sampa.eps}}}    $$
The total  contribution of this path to the partition function is therefore:
$\frac{1}{g}\frac{g}{c}\frac{y}{x}\frac{x}{d}\frac{d}{e}\frac{e}{j}=\frac{x}{c j}$
\end{example}

\section{Application: computation of the Laurent polynomials $p_{a,b}(\theta_\cdot)$}\label{applione}

In this section, we show that the functions $p_{a,b}(\theta_\cdot)$ defined by the system \eqref{condet} are the solutions $T_{j,k}=T_{1,j,k}$ of
the $A_{\infty/2}$ $T$-system with some particular initial conditions and some particular mapping of indices $(a,b)\to (j,k)$.

\subsection{Steepest stepped surface}\label{steepest}

In this section we consider stepped surfaces with fixed intersection with the $i=1$ plane, say equal to a path $\pi=(j,k_j)$ with
$|k_{j+1}-k_j|=1$ and $j+k_j=0$ mod 2 for all $j\in \Z$.  We define the ``steepest stepped surface" $\bk_\pi$
to be the unique stepped surface $\bk$ with $k_{1,j}=k_j$ included in the union of all the planes with normal vector $(1,-1,-1)$
or $(1,1,-1)$ and passing through pairs of distinct points of $\pi$. It is easy to see that such a surface is piecewise-linear.
Let $(a_j,b_j=k_{a_j})$, $j\in \Z$ be the vertices where $\pi$ changes direction, with say a minimum when $j$ is even, and a
maximum when $j$ is odd. The steepest stepped surface $k=k_{i,j}$ is defined by the following equations for $m\in \Z$:
\begin{eqnarray*}
i-j-k_{i,j}&=&1-a_{2m}-b_{2m}\qquad (i\geq 1;a_{2m-1}\leq j\leq a_{2m}) \\
i+j-k_{i,j}&=&1+a_{2m}-b_{2m}  \qquad (i\geq 1;a_{2m}\leq j\leq a_{2m+1})
\end{eqnarray*}

Concretely, the steepest stepped surface is a sort of roof of fixed slope above the infinite Young diagram delimited by the path $\pi$
in the $i=1$ plane (see Fig.\ref{fig:toit} for a 3D view in perspective).

\subsection{Connection with the Laurent polynomials $p_{a,b}(\theta_\cdot)$}

\begin{figure}
\centering
\includegraphics[width=16.cm]{toit.eps}
\caption{\small The FCC lattice representation of the Young diagram $\lambda=(5,4,4,4,2)$ (blue dots in the $i=1$ plane)
and its augmented tableau $\lambda^*$ (extra green vertices in the $i=1$ plane), together with the initial data steepest stepped surface
(green vertices, including $\lambda^*\setminus\lambda$). We have indicated a particular vertex of the surface
in the plane $i=3$, with assigned initial value $t$, and displayed the pyramid of which it is the apex, together with its base in the $i=1$ plane,
identified as a square of size $3$ of $\lambda^*$. The initial data assignment amounts to imposing that the $3\times 3$ determinant of the values
of $T$ in this square is equal to the value $t$ at the apex.}
\label{fig:toit}
\end{figure}

Let us represent the centers of boxes of the Young diagram $\lambda^*$ as vertices of the $i=1$ plane of the lattice $L_{FCC}$
(see Fig. \ref{fig:toit} for an illustration).
This allows to identify the strip $\lambda^*\setminus \lambda$ as a path $p$ from $(0,0)$ to $(N+\lambda_1,N-\lambda_1)$, while
the NW corner box of the diagram has coordinates $(N,N)$ (see sketch below):
$$ \raisebox{1.1cm}{\hbox{\epsfxsize=11.cm \epsfbox{sketch.eps}}}    $$
Let us extend arbitrarily the path $p$ into a path $\pi$ on the entire plane, and consider the solutions $T_{j,k}$ of the
$A_{\infty/2}$ $T$-system with initial data stepped surface equal to the steepest surface $\bk_\pi$ associated to $\pi$,
and with initial values $t_{i,j}$. To avoid confusion, note that there are distinct yet natural frames used so far for expressing
the coordinates of the centers of the boxes of $\lambda^*$.
On one hand, we have the original frame, in which the coordinate $(a,b)$ refers
to the box in row $a\in[1,N]$ and column $b\in [1,\lambda_a]$. On the other hand we have the $T$-system (or FCC lattice) frame
in the plane $i=1$, in which the coordinate $(j,k)$ of the center of a box is related to that in the original frame by:
\begin{equation}j=\lambda_1+a-b,\qquad k=\lambda_1+2-a-b
\end{equation}
In the following, we will use letters $a,b$ for the original coordinates, and $j,k$ for the FCC lattice coordinates.

We have the following:

\begin{thm}\label{pT}
The system \eqref{condet} has a unique solution $p_{a,b}(\theta_\cdot)$, $(a,b)\in \lambda$. Moreover, we have
\begin{equation}
p_{a,b}(\theta_\cdot)=T_{a-b+\lambda_1,\lambda_1+2-a-b}\qquad \big((a,b)\in \lambda^*\big)
\end{equation}
where $T_{j,k}=T_{1,j,k}$ is the solution of the $A_{\infty/2}$ $T$-system with steepest initial data stepped surface $\bk_\pi$
and initial values $\bt$ such that
\begin{equation}
\theta_{a,b}=t_{a-b+\lambda_1,\frac{\lambda_1+2-a-b+k_{a-b+\lambda_1}}{2}}\qquad \big((a,b)\in \lambda^*\big)
\end{equation}
where $(j,k_j)$ are the vertices of the path $p$, for $j=0,1,...,\lambda_1+N$.
\end{thm}
\begin{proof}
Consider the solution $T_{i,j,k}$ of the  $A_{\infty/2}$ $T$-system with steepest initial data stepped surface $\bk_\pi$
and initial values $\bt$. Let us restrict our attention to the solutions $T_{j,k}=T_{1,j,k}$ at the points $(j,k)$ with left and right projections
on the interval $[0,\lambda_1+N]$. These are exactly the centers of the boxes of $\lambda^*$ in the above representation
(see Fig.\ref{fig:toit} for the case $\lambda=(5,4,4,4,2)$).

On the other hand, the equation \eqref{wrons} may be interpreted as follows. The indices $(j+b-a,k+i+1-a-b)$
for $1\leq a,b \leq i$ are the coordinates in the plane $x=1$ of the base of the pyramid $\Pi_{i,j,k}$ with apex $(i,j,k)$, defined as
$\Pi_{i,j,k}=\{ (x,y,z)\in L_{FCC},\,  |y-j|+|z-k|\leq |x-i|\}$. As illustrated in Fig.\ref{fig:toit}, each vertex $(i,j,k_{i,j})$ of the steepest surface
$\bk_\pi$ is the apex of
such a pyramid $\Pi_{i,j,k_{i,j}}$.  By definition of the steepest stepped surface,
the base of the pyramid $\Pi_{i,j,k_{i,j}}$ in the $x=1$ plane is the square $S_{a,b}$ of $\lambda^*$, with NW corner at position
$(j,2k-k_j)=(a-b+\lambda_1,\lambda_1+2-a-b)$ (and SE corner at position $(j,k_j)$ on the path $p$), hence $a=1-k_{i,j}+\frac{j+k_j}{2}$
and $b=\lambda_1+1+k_{i,j}+\frac{k_j-j}{2}$. We conclude that $T_{i,j,k_{i,j}}=t_{i,j}$ is the determinant of the array $T_{\ell,m}$ for $(\ell,m)$
in the square $S_{a,b}$. In the example of Fig.\ref{fig:toit} (left), this amounts to the identity
$t={ \tiny{\left\vert \begin{matrix}a & b & c\\ d & e & f\\ g & h & i\end{matrix}\right\vert}}$.

Let us identify $t_{i,j}\equiv T_{i,j,k_{i,j}}$ with $\theta_{a,b}$, for all $(a,b)\in \lambda^*$,
with $a=1-k_{i,j}+\frac{j+k_j}{2}$
and $b=\lambda_1+1+k_{i,j}+\frac{k_j-j}{2}$. Then the system of equations \eqref{condet} for $p_{a,b}$ becomes the {\it same} as that for
$T_{j,k}$, with $j=a-b+\lambda_1$ and $k=\lambda_1+2-a-b$.
As all $T_{j,k}$ are uniquely determined by the initial data, then so
are the $p_{a,b}$, and the theorem follows.
\end{proof}

\subsection{Network interpretation}\label{networksec}

We may now specialize the general solution of Sect.\ref{tsysect} to the case of the steepest stepped surface. Let us describe the
extended Young tableau $\lambda^*$ via the sequence of integers $n_1,m_1,n_2,m_2,...,n_k,m_k$
corresponding to the length of straight portions of the path $p$ delimiting the diagram, namely:
$$ \raisebox{1.1cm}{\hbox{\epsfxsize=7.cm \epsfbox{sizes.eps}}}     $$
or in the notations of Sect. \ref{steepest}: $n_{i}=a_{2i}-a_{2i-1}$, $m_i=a_{2i+1}-a_{2i}$, $i=1,2,...,k$,
where $a_1,a_2,...,a_{2k}$ are the $j$ coordinates in the FCC lattice of the changes of slope of $p$.

A drastic simplification occurs in the case of the steepest stepped surface: along each steepest plane,
only one type of lozenge $U$ or $V$ occurs, namely planes orthogonal to $(1,-1,-1)$ have a lozenge decomposition
using only $V$ type lozenges, while those orthogonal to $(1,1,-1)$ have a lozenge decomposition
using only $U$ type lozenges. Moreover the slice of surface corresponding to $T_{i,j,k}$ with lower/upper projections $j_0,j_1$
always starts with a $(1,-1,-1)^\perp$ plane and ends with a $(1,1,-1)^\perp$ one. The corresponding lozenge decomposition
reads typically like:
$$ \raisebox{1.1cm}{\hbox{\epsfxsize=11.cm \epsfbox{lozendec.eps}}}      $$
where we have only included the minimal number of $V$ or $U$ type lozenges in each slice (any extra $U,V$ would have no effect
on the corresponding matrix element $M(j_0,j_1)_{1,1}$). Recall that the vertices of the surface carry initial data assignments $t_{i,j}$,
in bijection with the $\theta_{a,b}$ parameters, while the bottom layer at $i=0$ carries values all equal to $1$.

We may now construct the network associated to the lozenge decomposition above. For our running example, it reads:
$$ \raisebox{0.cm}{\hbox{\epsfxsize=17.cm \epsfbox{netdec.eps}}}      $$
where we have indicated how to deform the original network graph to bring it to the square lattice with oriented edges.
This latter graph is denoted by $L(j_0,j_1)$ in FCC lattice language. Assuming that the top inner face of $L(j_0,j_1)$
corresponds to the box $(a,b)$ of $\lambda$, we denote alternatively this network by ${\mathcal N}_{a,b}\equiv L(j_0,j_1)$.
We have indicated the face variables of this network by green dots (the top vertex carries the variable $\theta_{a,b}$),
while all variables on the (bottom-most) red dots are equal to $1$.
The medallion summarizes
the weighting rule for the edges of  $L(j_0,j_1)={\mathcal N}_{a,b}$ in terms of the face variables $t_{i,j}=\theta_{a,b}$ (at the indicated vertices).
This is just a rephrasing of the weights of $U$ and $V$ type chips after the above deformation, namely:
\begin{equation}\label{rulnet} U=\raisebox{-1.cm}{\hbox{\epsfxsize=4.cm \epsfbox{unet.eps}}},
\qquad V= \raisebox{-1.cm}{\hbox{\epsfxsize=4.cm \epsfbox{vnet.eps}}}
\end{equation}
The graph $L(j_0,j_1)={\mathcal N}_{a,b}$ is nothing but the actual initial Young diagram
$\lambda_{a,b}$ (SE corner at $(a,b)$) represented tilted by $45^\circ$,
and with all box edges oriented from left to right. The face variables,
expressed indifferently as $t_{i,j}$'s or $\theta_{a,b}$'s, are actually at the centers of boxes of $\lambda_{a,b}^*$
but displaced by a global translation of $(2,0)$ in the $(j,k)$ plane
(or by one column to the left and one row up in the original frame). For convenience we denote by $\lambda_{a,b}^\#$
this latter displaced array.
Note that extra variables equal to $1$ occupy the centers of boxes of $\lambda_{a,b}^*\setminus \lambda_{a,b}$.
In the above depiction, we have $\lambda_{a,b}=(5,4,4,4,2)$
and $\lambda_{a,b}^*=(6,6,5,5,5,3)$.

By use of Theorems \ref{netsol} and \ref{pT}, the value of $p_{a,b}=T_{j,k}$ in the top box is given by the partition function for paths
on $L(j_0,j_1)={\mathcal N}_{a,b}$ from the leftmost vertex to the rightmost one, multiplied by the bottom right initial value
$t_{1,j_1}=\theta_{a,\lambda_a^*}=\theta_{a,\lambda_a+1}$.
We summarize this result in the following:

\begin{thm}\label{thpath}
The solution $p_{a,b}$ to the system \eqref{condet} is the partition function of paths on the weighted graph ${\mathcal N}_{a,b}$
associated to $\lambda_{a,b}$, from the leftmost to the rightmost vertex, multiplied by the variable $\theta_{a,\lambda_a+1}$ of the top
right box of $\lambda_{a,b}^*$.
\end{thm}

Note that Theorem \ref{main} follows from this result, as the sum over paths produces a manifestly positive Laurent polynomial of the initial parameters $\theta_{i,j}$.

\begin{example}
Let us revisit Example \ref{firstex}. The graph $L(j_0,j_1)={\mathcal N}_{1,1}$ for the calculation of $p_{1,1}$ is associated to
$\lambda_{1,1}=\lambda=(2,1)$, and reads:
$$\raisebox{0.cm}{\hbox{\epsfxsize=12.cm \epsfbox{exnet.eps}}} $$
where we have indicated the edge weights.
The Laurent polynomial $p_{1,1}$ is $c$ times the partition function for the 5 paths $1\to 1$:
$$\begin{matrix}\begin{matrix}{\rm path:} \\ {} \end{matrix}& \hbox{\epsfxsize=2.cm \epsfbox{path1.eps}} &  \hbox{\epsfxsize=2.cm \epsfbox{path2.eps}}&
\hbox{\epsfxsize=2.cm \epsfbox{path3.eps}} &  \hbox{\epsfxsize=2.cm \epsfbox{path4.eps}}& \hbox{\epsfxsize=2.cm \epsfbox{path5.eps}} \\
{\rm weight:} & \frac{ge}{f h c}& \frac{d}{f h} &\frac{gb}{fhc} &\frac{bd}{hefc} & \frac{a}{ce}  \end{matrix}$$
wich yields
$$ p_{1,1}=\frac{a f h+(b+c e)(d+g e)}{hef} $$
in agreement with the expression of Example \ref{firstex}.
\end{example}

\subsection{Dimer interpretation}\label{dimersec}

The network formulation for the solution of the $T$-system described in Sect.\ref{tsysect} can be rephrased in terms of a statistical model of dimers on a planar bipartite graph ${\mathcal G}$ with face variables, made only of square, hexagonal and octagonal inner faces, and with open outer faces
adjacent to 1 or 2 edges (see Ref.\cite{DF13}). This graph is constructed as the dual of the lozenge decomposition, essentially by substituting:
$$\raisebox{-1.3cm}{\hbox{\epsfxsize=5.cm \epsfbox{U.eps}}}\quad {\rm and}\quad  \raisebox{-1.2cm}{\hbox{\epsfxsize=5.cm \epsfbox{V.eps}}}   $$
Note that the initial data assignments become face variables in the dimer graph.
The configurations of the dimer model on
a bipartite graph are obtained by covering single edges of the graph by ``dimers" in such a way that each vertex is covered exactly once.
The weight of a given configuration is the product of local outer/inner face weights expressed in terms of the attached face variable.
The weight of an inner face is $a^{\frac{v}{2}-1-D}$ where $a$ is the face variable, $v$ the degree of the face ($v\in\{4,6,8\}$),
and $D$ the total number of dimers occupying edges bordering the face. The weight of an outer face is $b^{1-D}$, where $b$ is the face variable
and $D$ the total number of dimers occupying edges of the graph adjacent to the face.
Then we have:

\begin{thm}\label{thdim}{\cite{DF13}}
The solution $T_{1,j,k}\equiv T_{j,k}$ of the $A_{\infty/2}$ $T$-system is the partition function of the dimer model on the dimer graph dual to the lozenge decomposition of the corresponding network.
\end{thm}

For the particular case of the steepest stepped surface, the dimer graph ${\mathcal G}_{a,b}$ for the computation of $p_{a,b}$
is particularly simple. Its inner faces occupy a domain
of the hexagonal (honeycomb) lattice with the shape of the young diagram $\lambda_{a,b}$, while its outer faces correspond
respectively to $\lambda_{a,b}^*\setminus \lambda_{a,b}$ with face variables all equal to $1$, and to $\lambda_{a,b}^\#\setminus \lambda_{a,b}$.
The other face variables are the variables $\theta_{\alpha,\beta}$ on $\lambda_{a,b}^\#$.
For the case $\lambda_{a,b}=(5,4,4,4,2)$ of previous section, the dimer graph ${\mathcal G}_{a,b}$ reads:
$$ \raisebox{-1.3cm}{\hbox{\epsfxsize=9.cm \epsfbox{hexa.eps}}}$$
where we have represented in red the centers of boxes of $\lambda_{a,b}^*\setminus\lambda_{a,b}$ (all with assigned face values $1$),
and in green the centers of boxes of $\lambda_{a,b}^\#$ (with the $\theta_{\alpha,\beta}$'s or $t_{i,j}$'s as assigned faces values).

Applying Theorem \ref{thdim}, we finally get:

\begin{thm}
The Laurent polynomial $p_{a,b}(\theta_\cdot)$ is the partition function for the dimer model on the graph ${\mathcal G}_{a,b}$ with face variables
$\theta_{\alpha,\beta}$ on the faces corresponding to the boxes of $\lambda_{a,b}^\#$ and face variables $1$ on those corresponding to the boxes
of $\lambda_{a,b}^*\setminus\lambda_{a,b}$.
\end{thm}

\begin{example}
Let us revisit the example \ref{firstex}. The graph ${\mathcal G}_{1,1}$ for computing $p_{1,1}$ reads:
$$ \raisebox{-1.3cm}{\hbox{\epsfxsize=6.cm \epsfbox{hexex.eps}}} $$
and the partition function for dimers on ${\mathcal G}_{1,1}$ is the sum over the following five configurations:
$$\begin{matrix} \begin{matrix} {\rm dimer}\\
{\rm configuration} :\\ {}\\{} \end{matrix} &\raisebox{-.3cm}{\hbox{\epsfxsize=2.5cm \epsfbox{dimer1.eps}}}
& \raisebox{-.3cm}{\hbox{\epsfxsize=2.5cm \epsfbox{dimer2.eps}}}&
\raisebox{-.3cm}{\hbox{\epsfxsize=2.5cm \epsfbox{dimer3.eps}}}
& \raisebox{-.3cm}{\hbox{\epsfxsize=2.5cm \epsfbox{dimer4.eps}}}
&\raisebox{-.3cm}{\hbox{\epsfxsize=2.5cm \epsfbox{dimer5.eps}}} \\
{\rm weight}: &\frac{g e}{f h} &\frac{d c}{fh} &\frac{g b}{f h} &\frac{b d}{efh} & \frac{a}{e}\\
\end{matrix}
$$
\end{example}

We note that Theorems \ref{thpath} and \ref{thdim} may be connected more directly by showing that the path and dimer configurations
are in bijection with each-other. To best see this, recall that the dimer configurations on a domain of  the hexagonal lattice are in
bijection with rhombus tilings of the dual (triangular) lattice, by means of three types of rhombi obtained by gluing two adjacent triangles along
their common edge.
For the above example of $\lambda_{a,b}=(5,4,4,4,2)$, the domain ${\mathcal T}_{a,b}$ of the triangular lattice dual to ${\mathcal G}_{a,b}$ reads:
$$  \raisebox{-1.3cm}{\hbox{\epsfxsize=8.cm \epsfbox{triang.eps}}} $$
Notice that generically the domain ${\mathcal T}_{a,b}$ only has two vertical boundary edges, dual to the only two horizontal external edges of
${\mathcal G}_{a,b}$.
Dimer configurations on ${\mathcal G}_{a,b}$ are in bijection with rhombus tilings of ${\mathcal T}_{a,b}$.
Moreover, such tilings are uniquely determined by either of three sets of non-intersecting paths of rhombi
(the so-called De Bruijn lines) defined as follows.
Each boundary edge of ${\mathcal T}_{a,b}$ has either of three orientations (vertical, $+30^\circ$, or $-30^\circ$). Starting from
any boundary edge, let us construct the chain of consecutive rhombi that share only edges of the same orientation. Such a chain is a path
connecting two opposite boundary edges. For a given orientation of the boundary edge, all such paths are non-intersecting, and form one of the above-mentioned three families. Any single such family determines the tiling entirely. In the present case, the ``vertical" family is particularly
simple, as it is made of a single path of rhombi:
$$  \raisebox{-1.3cm}{\hbox{\epsfxsize=8.cm \epsfbox{rhombus.eps}}} $$
This path determines the tiling entirely. We have therefore associated to each dimer configuration
on ${\mathcal G}_{a,b}$ a unique path with up and down steps (say from left to right), which can be represented on the network $L(j_0,j_1)={\mathcal N}_{a,b}$ as a path from the leftmost vertex to the rightmost one.
This gives a bijection between the dimer configurations of Theorem \ref{thdim} and the paths on networks of Theorem \ref{thpath}.
It is easy to show how the local weights of the path model can be redistributed into those of the dimer model, thus establishing directly the equivalence between the two theorems.

\subsection{Back to the polynomials of Bessenrodt and Stanley}\label{sectobs}

In this section we give two independent proofs of Theorem \ref{restrictoBS}.

As pointed out earlier, the polynomials of \cite{BS} may be recovered by specializing the variables $\theta_{i,j}$ according to \eqref{bsrestrict}.
More precisely, the (restricted) polynomials $p_{a,b}(x_\cdot)$ of \cite{BS} are defined by the formula:
\begin{equation}\label{BSp} p_{a,b}(x_\cdot)=\left\{ \begin{matrix}1 &\quad  {\rm if} (a,b)\in \lambda^*\setminus \lambda\\
{} & {}\\
\sum_{\mu \subset \lambda_{a,b}} \prod_{(r,s)\in \lambda_{a,b}\setminus \mu} x_{r,s} & {\rm if}\ (a,b)\in \lambda \end{matrix}\right.
\end{equation}
where in the second formula the sum extends over all sub-diagrams $\mu$ of $\lambda_{a,b}$. In \cite{BS}, the determinant of
the array $p_{a+i-1,b+j-1}(x_\cdot)$, $1\leq i,j\leq n_{a,b}$ pertaining to the square $S_{a,b}$ of $\lambda$ with NW corner $(a,b)$, was computed
to be equal to the ``leading term":
\begin{equation}\label{zdef} Z_{a,b}=\prod_{i=1}^{n_{a,b}} \prod_{(\al,\beta)\in \lambda_{a+i-1,b+i-1}} x_{\al,\beta}\ ,
\end{equation}
equal to the product of leading terms of
$p_{a+i-1,b+i-1}(x_\cdot)$ along the first diagonal. With the choice of restrictions \eqref{bsrestrict} which identify $\theta_{a,b}$ with $Z_{a,b}$,
and by uniqueness of the $T$-system solution,
we deduce that the polynomials $p_{a,b}(\theta_\cdot)$ defined by the $T$-system solution are identical to the polynomials
$p_{a,b}(x_\cdot)$ of \cite{BS}, and Theorem \ref{restrictoBS} follows.

Let us now give an alternative direct proof of this result, by comparing the expression
\eqref{BSp} to the restriction of the network expression of Theorem
\ref{thpath} for the solution of the $T$-system with steepest initial data stepped surface.
The first part of the formula \eqref{BSp}  is clear from the choice $\theta_{a,b}=1$ for  $(a,b)\in \lambda^*\setminus \lambda$. To
recover the second part, first note that there is a bijection between the sub-diagrams $\mu \subset \lambda_{a,b}$
and the paths from the leftmost vertex
to the rightmost vertex on the network ${\mathcal N}_{a,b}$. To identify the polynomials,
we simply have to check that the weight of each path,
multiplied by the rightmost face variable ($t_{1,j_1}\equiv \theta_{a,\lambda_a^*}=1$ here) reduces to
$\prod_{(r,s)\in \lambda_{a,b}\setminus \mu} x_{r,s}$, namely the product of $x$ variables under the path in $\lambda_{a,b}$.

To best compare the two settings, let us translate the network $L(j_0,j_1)$ globally by the vector by $(0,0,-2)$ in the $L_{FCC}$
representation (namely $k\to k-2$), so that the face labels match the positions of the corresponding boxes in $\lambda_{a,b}$.
This changes the local edge weight rules accordingly (by moving the face variables by two steps downwards).
In this new representation, the local edge weights of the path model can now be written in terms of the $x$ variables as:
$$  \raisebox{-1.3cm}{\hbox{\epsfxsize=14.cm \epsfbox{rulex.eps}}}$$
where we have shown the two possible cases of an up or down-pointing edge of the path, both with weight $a/b$, and represented
the weight in terms of the box variables $x$ as follows: in case (a) (up step), the weight $a/b$ is the inverse of the product of the $x$'s
in the dashed (blue) domain, while in case (b) (down step), the weight $a/b$ is the product of the $x$'s in the solid (green) domain.
We deduce that only boxes below the path delimiting $\mu$ in $\lambda_{a,b}$ contribute. Moreover, a given such box with variable $x$ receives a
contribution $x^{N_{\rm down}-N_{\rm up}}$, where $N_{\rm up}$ and $N_{\rm down}$ denote the total number of up/down steps of the path
that respectively belong to the left/right sector seen from the box as depicted below:
$$ \raisebox{-1.3cm}{\hbox{\epsfxsize=4.cm \epsfbox{rulebox.eps}}} $$
It is clear that we always have $N_{\rm down}-N_{\rm up}=1$ as the path always goes up one step less in the left sector
than it goes down in the right sector.
The total weight of the path delimiting $\mu$ in $\lambda_{a,b}$ is therefore the product over all the boxes below $\mu$ of the box variables $x$,
and the Theorem follows.

\section{3D Generalization}

\subsection{The general solution of the $T$-system}

So far we have concentrated on the solution $T_{j,k}=T_{1,j,k}$ of the $T$-system in the $i=1$ plane.
The general solution of the $T$-system gives access more generally to values of $T_{i,j,k}$ in other planes $i\geq 2$ as well.
In Ref.\cite{DF}, it was shown that such solutions are partition functions of families of $i$ non-intersecting paths on  the
same type of network as for $i=1$. More precisely, we first consider the base of the pyramid $\Pi_{i,j,k}$, which is a square
array of $T_{i+b-a,j+i+2-a-b}$, $a,b=1,2...,i$. We then construct all left and right projections of the points in this array,
say $\ell_1,...,\ell_i$ and $r_i,r_{i-1},...,r_1$ from left to right. Then the solution $T_{i,j,k}$ is given by the following:
\begin{thm}{\cite{DF}}
The solution $T_{i,j,k}$ of the $A_{\infty/2}$ $T$-system with initial data $(\bk,\bt)$ is equal to the partition function
of $i$ non-intersecting paths on the network $N(\ell_1,r_1)$ that start from the points $(\ell_a,k_{\ell_a})$ on the stepped surface $\bk$
and end at the points $(r_a,k_{r_a})$ on the stepped surface $\bk$, multiplied by the boundary term:
$ \prod_{a=2}^i t_{1,\ell_a}^{-1} \prod_{b=1}^i t_{1,r_a} $.
\end{thm}

\subsection{Pyramid of a partition}

Starting from a partition/Young diagram $\lambda=(\lambda_1,...,\lambda_N)$, we define its  {\it pyramid} $P_\lambda$ as the family
of partitions/Young diagrams $\lambda^{(i)}$, $i=1,2,...,k$, such that (i) $\lambda^{(1)}=\lambda$ (ii) $\lambda^{(i+1)}$
is obtained from $\lambda^{(i)}$ by removing its first row and column (iii) $\lambda^{(k)}=\emptyset$.

The centers of boxes of the pyramid $P_\lambda$ may be represented as the set of vertices
$(i,j,k)$ in $L_{FCC}$ such that the base of the pyramid $\Pi_{i,j,k}$ in the plane $i=1$ is entirely contained in $\lambda$.
In this correspondence, $\lambda^{(m)}$ is simply the intersection of the plane $i=m$ with this set of vertices. Another representation
of the pyramid $P_\lambda$ is as a strip decomposition of $\lambda$, by superimposing all the diagrams $\lambda^{(m)}$, with their $(1,1)$
box in the same position.
Finally, we define the extended pyramid $P_\lambda^*$ to be the pyramid of the extended Young diagram $\lambda^*$, namely
$P_\lambda^*=P_{\lambda^*}$.

\begin{example}
The pyramid of the partition $\lambda=(4,4,3)$ is  $\lambda^{(1)}=(4,4,3)$, $\lambda^{(2)}=(3,2)$, $\lambda^{(3)}=(1)$,
$\lambda^{(4)}=\emptyset$. The representation of $P_\lambda$ in $L_{FCC}$ and as a strip decomposition of $\lambda$ are respectively:
$$ \raisebox{-1.5cm}{\hbox{\epsfxsize=6cm \epsfbox{pyramid.eps}}} \quad {\rm and}\quad
\raisebox{-1.5cm}{\hbox{\epsfxsize=4cm \epsfbox{stripdecomp.eps}}}$$
\end{example}

\subsection{The family of Laurent polynomials for a pyramid}

The solution of the $A_{\infty/2}$ $T$-system within a pyramid $P_\lambda$ defined as above is entirely fixed by the
assignment of initial data on the ``roof" of the pyramid, defined by $P_\lambda^*\setminus P_\lambda$. Note that this roof is nothing but the
portion of the steepest stepped surface that determines the polynomials $p_{a,b}$ entirely. This leads to a natural extension of the family
of polynomials $\{p_{a,b}\}_{(a,b)\in \lambda}$ into a pyramid family $\{p_{a,b,m}\}$ with $1\leq m\leq k$ and
$(a,b)\in \lambda^{(m)}$, obtained by identification of the solution $T_{i,j,k}$ at the corresponding vertex of $P_\lambda\subset L_{FCC}$.

As a consequence of this definition, we may rewrite \eqref{wrons} as:

\begin{thm}
The pyramid polynomials $p_{a,b,m}(\theta_\cdot)$ associated to a Young diagram $\lambda$ are entirely determined by the determinant identity:
\begin{equation}\label{deterp} p_{a,b,m}(\theta_\cdot)=\det\left(\left( p_{a+i-1,b+j-1}(\theta_\cdot)\right)_{1\leq i,j,\leq m}\right) \end{equation}
where the array of points in the determinant corresponds to the base in the plane $i=1$ of the pyramid with apex at the center of the box
$(a,b)$ of $\lambda^{(m)}$ in the $L_{FCC}$ representation.
\end{thm}

The network interpretation of the solution of the $T$-system \cite{DF} allows to immediately interpret the pyramid polynomial $p_{a,b,m}$
as the partition function for $m$ non-intersecting paths on the network ${\mathcal N}_{a,b}$ associated to $\lambda_{a,b}$
and the steepest stepped surface, up to a multiplicative boundary factor, by direct application of the Lindstr\"om Gessel-Viennot Theorem
\cite{LGV1,LGV2}. These paths start/end at the points of
$\bk$ that correspond to the left/right projections of the array of points in the determinant \eqref{deterp}. On ${\mathcal N}_{a,b}$,
these are the left/right  projections of the top vertex of each box in the corresponding square of size $m$ with top box $(a,b)$.

\begin{example}
Let us consider $\lambda=(5,4,4,4,3)$ and the network $L(j_0,j_1)={\mathcal N}_{1,1}$ of Sect.\ref{networksec}.
The pyramid polynomial $p_{1,1,3}$
is equal to the determinant $\tiny \left\vert \begin{matrix} p_{1,1}& p_{1,2} & p_{1,3} \\
p_{2,1} & p_{2,2} & p_{2,3} \\
p_{3,1} & p_{3,2} & p_{3,3} \end{matrix}\right\vert$.
It is also proportional to the partition function of paths from the entry to the exit vertices marked
$1,2,3$ below:
$$ \raisebox{0.cm}{\hbox{\epsfxsize=16.cm \epsfbox{exonet.eps}}}  $$
where we have also represented a sample configuration of these three non-intersecting paths.
The entry/exit vertices of ${\mathcal N}_{a,b}$ are the left/right projections of the vertices at the top of the boxes in the corresponding square
(here shaded in blue).

The proportionality factor
is simply $a^{-1}b^{-1} c d e$, where the corresponding face variables are immediately above the entry points $2,3$ and exit points $1,2,3$.
\end{example}

\subsection{Generalized Bessenrodt-Stanley polynomials for a pyramid}

We may now restrict the pyramid Laurent polynomials $p_{a,b,m}(\theta_\cdot)$ attached to a partition $\lambda$ via the same
change of variables \eqref{bsrestrict} to box weights $x_{i,j}$. This leads us to the definition of the quantities:
\begin{equation}\label{BSpm}p_{a,b,m}(x_\cdot)=\det\left(\left( p_{a+i-1,b+j-1}(x_\cdot)\right)_{1\leq i,j,\leq m}\right) \end{equation}

We have:

\begin{thm}\label{genBS}
The pyramid polynomials $p_{a,b,m}(x_\cdot)$ \eqref{BSpm} have non-negative integer coefficients, and moreover
$p_{a,b,m}(x_\cdot)$ is the partition function for $m$ non-intersecting paths on the network ${\mathcal N}_{a,b}$ associated to $\lambda_{a,b}$,
from the $m$ left projections to the $m$ right projections of the vertices of the square of size $m$ with NW corner at $(a,b)$.
Alternatively, $p_{a,b,m}(x_\cdot)$ is the partition function for $m$ strictly nested partitions
$\emptyset\subset \mu_m\subset\mu_{m-1}\subset\cdots\subset\mu_1\subset\lambda_{a,b}$ with $\mu_i\subset\lambda_{a,b}^{(i)}$
inside $\lambda_{a,b}$, with the usual weights:
$$p_{a,b,m}(x_\cdot)=\sum_{\mu_i\subset\lambda_{a,b}^{(i)}\atop i=1,2,...,m}
\prod_{i=1}^m \prod_{(\al,\beta)\in \lambda_{a,b}\setminus\mu_i}x_{\al,\beta}$$
\end{thm}

\section{Conclusion/Discussion}

In this paper, we have expressed the polynomials of \cite{BS} as particular solutions of the octahedron recurrence
in a half-space with ``steepest" initial data surface attached to a fixed partition $\lambda$. This connection has allowed us to generalize these polynomials to the full pyramid $P_\lambda$, and to find alternative expressions involving paths on networks or dimers on bipartite graphs.

More generally, we may consider different initial data surfaces associated to the partition $\lambda$, and use the solutions of the corresponding
$T$-system to define different classes of polynomials attached to the boxes of $\lambda$. Another natural choice is to pick the stepped surface to be made of ``vertical walls" along the boundary of $\lambda$, namely with vertices alternating between two parallel planes with normal vector
$(0,1,1)$ or $(0,-1,1)$ in $L_{FCC}$. In the case of $\lambda=(5,5,5,5,3)$, the 3D FCC lattice view and the corresponding
stepped surface lozenge decomposition look like:
$$  \raisebox{-1.3cm}{\hbox{\epsfxsize=8.cm \epsfbox{lastloz2.eps}}} $$
Here the vertical wall stepped surface is represented in front, with green vertices.
The centers of the boxes of $\lambda$ are the blue vertices in the bottom plane ($i=1$).
In the lozenge decomposition of the stepped surface, we have only represented the lozenges that will contribute to the
solution within $\lambda$, and added as before triangles in the bottom row, with their bottom-most vertex assigned value $1$
(the $A_{\infty/2}$ boundary condition \eqref{plus}).
Note also that the boundary vertical walls intersect the plane $i=1$ along the boxes of $\lambda^*\setminus \lambda$.

The difference with the situation of the steepest stepped surface is subtle: in both cases, the walls are made uniquely of either $U$ type of $V$ type lozenges, but their arrangement (the order in which they come from left to right) is different, due to the rules \eqref{eqrules}.
We may now translate the lozenge decomposition into a network, which we deform in the same way as before to finally get:
$$   \raisebox{-1.3cm}{\hbox{\epsfxsize=16.cm \epsfbox{lastnet.eps}}}  $$
where we have indicated the correspondence between a sample row of face weights (green dots  in general)
with assigned values $t_{i,j}=a,b,c,...$, and the bottom outer faces by red dots (with assigned values $1$).
The edge weights in the network are
related to the face variables in the usual way \eqref{rulnet}, and all the horizontal edges receive the weight $1$.
The construction of the network looks more complicated, but again the solution at the box $(1,1)$ of $\lambda$ is the partition function for paths on this network, from the leftmost to the rightmost vertex. In fact, it is possible to deform the network to make it match the shape of the Young
diagram $\lambda$, at the expense of adding some extra edges as follows:
$$  \raisebox{-1.3cm}{\hbox{\epsfxsize=9.cm \epsfbox{netlast.eps}}}$$
where the up/down edge weights are related to the face variables in the usual way, while the new horizontal edges have weights as indicated in the medallion. The additional arrows (in red) split up each box of the strip decomposition $\{ \lambda^{(i)}\setminus\lambda^{(i+1)}\}_{i\in [2,k-1]}$ of
$\lambda$, where $\lambda^{(i)}$ is the $i$-th layer of the pyramid $P_\lambda$,  by connecting centers of box edges (we have shaded the strip
$\lambda^{(2)}\setminus\lambda^{(3)}$ in the above example). In particular all paths of red arrows are parallel. Note also that the first strip
$\lambda^{(1)}\setminus\lambda^{(2)}$ is not split.
Let us denote by ${\tilde {\mathcal N}}_{a,b}$
the network thus constructed out of the partition $\lambda_{a,b}$.

Having assigned fixed parameters $t_{i,j}$ to each
inner and outer face of the resulting network, we may associate a Laurent polynomial $q_{a,b,m}(t_\cdot)$ to the $(a,b)$ box of the $m$-th layer
$\lambda^{(m)}$ of the pyramid of $\lambda$, equal to the corresponding $T$-system solution with vertical wall
initial data stepped surface. Then we have:

\begin{thm}
The Laurent polynomial $q_{a,b,m}(t_\cdot)$ is the partition function of $m$ non-intersecting paths on ${\tilde {\mathcal N}}_{a,b}$, starting/ending
at the left/right projections of the top vertices of the boxes in the square with top box $(a,b)$ and size $m$, multiplied by the factor
$\prod_{\alpha=2}^m t_{1,\ell_\al}^{-1}\prod_{\beta=1}^m t_{1,r_\beta}$, where $\ell_\alpha$/$r_\alpha$ is the $j$ coordinate in the FCC lattice of the $\alpha$-th left/right projection of the points in the square of size $m$ with NW corner at $(a,b)$.
\end{thm}

\begin{example}
Let us consider the case $\lambda=(2,2)$. Let us assign the following initial values on the vertical walls:
$$\begin{matrix}
 & & T_{4,0,1}=\ell & & \\
& T_{3,-1,1}=i & T_{3,0,0}=j & T_{3,1,1}=k & \\
 & T_{2,-1,2}=f & T_{2,0,1}=g & T_{2,1,2}=h & \\
T_{1, -2, 2}= a & T_{1, -1, 1}= b & T_{1, 0, 0}= c & T_{1,1,1}=d & T_{1,2,2}=e
\end{matrix}$$
Then the network ${\tilde {\mathcal N}}_{1,1}$ reads, with the face variables or alternatively the edge weights:
$$  \raisebox{-1.3cm}{\hbox{\epsfxsize=10.cm \epsfbox{exlastnet.eps}}}$$
Let us first compute $q_{a,b}=q_{a,b,1}$ for the boxes for the Young diagram $\lambda$.
The quantities $q_{1,1}/e,q_{1,2}/e,q_{2,1}/d,q_{2,2}/d$ are the partition functions for paths on ${\tilde {\mathcal N}}_{1,1}$,
respectively from vertices $1\to 1$, $2\to 1$, $1\to 2$ and $2\to 2$. This gives:
$$ \begin{matrix} q_{1,1}=
\frac{a e}{c} + \frac{e f}{b d} + \frac{a e g}{b c d} + \frac{a h}{b d} + \frac{c f h}{
 b d g} + \frac{t}{y} + \frac{x z}{g y} & q_{1,2}=\frac{b e}{c} + \frac{e g}{c d} + \frac{h}{d} \\
 q_{2,1}= \frac{a d}{c} +  \frac{f}{b} +  \frac{a g}{b c} & q_{2,2}=\frac{b d}{c} + \frac{g}{c}
 \end{matrix} $$
 Finally the quantity $q_{1,1,2} b/(d e)$ is the partition function for pairs of non-intersecting paths from $1,2$ to $1,2$:
 $$ q_{1,1,2} = \frac{f h}{g} + \frac{b d t}{c y} + \frac{g t}{c y} +\frac{x z}{c y}+\frac{b d x z}{ c g y} $$
\end{example}

config: arxiv


TITLE: Integration of Erf function
QUESTION [3 upvotes]: Let $f(x) = \int^\sqrt{x}_1 e^{-t^2}dt$. Find $\int^1_0 \frac{f(x)}{
\sqrt{x}}dx$.
Could anyone give me any hint how to start? The Erf function $f(x)$ seems not to be easily integrated.

REPLY [2 votes]: Brevan Ellefsen's solution is the most straightforward and efficient. Here is an alternative solution.
\begin{equation}
f(x) = \int\limits_{1}^{\sqrt{x}} \mathrm{e}^{-t^{2}} dt
\label{eq:161108-1}
\tag{1}
\end{equation}
\begin{equation}
\int\limits_{0}^{1} \frac{f(x)}{\sqrt{x}} dx
\label{eq:161108-2}
\tag{2}
\end{equation}
We need the following result
\begin{equation}
\int \mathrm{erf}(x) dx = x\,\mathrm{erf}(x) + \frac{\mathrm{e}^{-x^{2}}}{\sqrt{\pi}}
\label{eq:161108-3}
\tag{3}
\end{equation}
Proof: Integrate by parts
\begin{align}
\int \mathrm{erf}(x) dx &= x\,\mathrm{erf}(x) -\frac{2}{\sqrt{\pi}} \int x\,\mathrm{e}^{-x^{2}} dx \\
&= x\,\mathrm{erf}(x) + \frac{\mathrm{e}^{-x^{2}}}{\sqrt{\pi}}
\end{align}
we used the substitution $u=x^{2}$.
Now we evaluate equation \eqref{eq:161108-1}
\begin{equation}
f(x) = \frac{\sqrt{\pi}}{2} \mathrm{erf}(x) \Big|_{1}^{\sqrt{x}} = \frac{\sqrt{\pi}}{2} [\mathrm{erf}(\sqrt{x}) - \mathrm{erf}(1)]
\label{eq:161108-4}
\tag{4}
\end{equation}
Substitute equation \eqref{eq:161108-4} into equation \eqref{eq:161108-2} and evaluate the following two integrals.
\begin{align}
I_{1} &= \int\limits_{0}^{1} \frac{\mathrm{erf}(\sqrt{x})}{\sqrt{x}} dx \\
&= 2\int\limits_{0}^{1} \mathrm{erf}(z) dz \\
&= 2\,\mathrm{erf}(1) + \frac{2}{\mathrm{e}\sqrt{\pi}} - \frac{2}{\sqrt{\pi}}
\end{align}
we used the substitution $z=\sqrt{x}$.
\begin{equation}
I_{2} = \int\limits_{0}^{1} \frac{1}{\sqrt{x}} dx = 2
\end{equation}
Putting all of the pieces together yields our final result
\begin{align}
\int\limits_{0}^{1} \frac{f(x)}{\sqrt{x}} dx
&= \frac{\sqrt{\pi}}{2} \left(2\,\mathrm{erf}(1) + \frac{2}{\mathrm{e}\sqrt{\pi}} - \frac{2}{\sqrt{\pi}} - 2\,\mathrm{erf}(1) \right) \\
&= \frac{1}{\mathrm{e}} - 1
\end{align}


TITLE: Finding round off error when computing determinant and estimating backward error
QUESTION [0 upvotes]: Consider the simple case for $A=\begin{bmatrix} a_{11}\ a_{12}\ a_{13}\\ a_{21}\ a_{22}\ a_{23}\\ a_{31}\ a_{32}\ a_{33}\end{bmatrix}$. The determinant is given by $det(A)=a_{11}a_{22}a_{33}+a_{12}a_{23}a_{31}+a_{13}a_{21}a_{32}-a_{13}a_{22}a_{31}-a_{12}a_{21}a_{33}-a_{11}a_{23}a_{32}$.
Find the round off error in evaluating $det(A)$ and use result to estimate backward error $\delta A$.
So, this is my starting point:
$fl(det(A))=det(A+\delta A)=a_{11}a_{22}a_{33}(1+\delta_1)(1+\delta_1')+a_{12}a_{23}a_{31}(1+\delta_2)(1+\delta_2')+a_{13}a_{21}a_{32}(1+\delta_3)(1+\delta_3')-a_{13}a_{22}a_{31}(1+\delta_4)(1+\delta_4')-a_{12}a_{21}a_{33}(1+\delta_5)(1+\delta_5')-a_{11}a_{23}a_{32}(1+\delta_6)(1+\delta_6')$,
And the reason for two errors is that we multiply twice in each grouping. But now to where I'm confused, how do I take care of the addition operator in my round off model so far, any suggestions?

REPLY [0 votes]: Error analysis of this type is tedious only when we do not use the correct tool for the job. The standard approach requires the user to name every single rounding error and track how the error terms develops as we complete the basic arithmetic operations. In reality, we have no need for names or exact formulas, but we will settle for an error bound that is so good that we can distinguish the good algorithms from the bad algorithms and identify the inputs that are problematic.
The key ingredient is the $\gamma$-factor used in Higham's textbook "Accuracy and stability of numerical algorithms". By definition we have $$\gamma_n = \frac{nu}{1 -nu}$$ where $u$ is the unit roundoff. It is clear that $$u \leq \gamma_1,$$ but the critical property satisfied by the $\gamma$-factors is the inequality $$\gamma_n + \gamma_n + \gamma_m \gamma_n \leq \gamma_{m+n}$$ where $m,n \in \mathbb{N}$ and $(m+n)u < 1$. The systematic use of $\gamma$-factors allows us to concentrate exclusively on the size of rounding errors. We will write $$r = \langle m \rangle$$ if and only if $$\exists \Theta \in \mathbb{R} \: : (r = 1 + \Theta \: \wedge \: |\Theta| \leq \gamma_m).$$ The following property is critical, namely
$$\Big[r = \langle m \rangle \: \wedge \: s = \langle n \rangle \Big] \quad \Rightarrow \quad rs = \langle m + n \rangle.$$ The standard model for floating point calculations, i.e., $$fl(x) = x(1+\delta), \quad |\delta| \leq u$$ will be weakened to $$\text{fl}(x) = x\langle 1 \rangle.$$
After these preparations we are now ready to address the original question. We will at all times use $\hat{x}$ to denote the computed value of $x$. Let us consider a sum of say $m$ floating point numbers, $x_i$. The standard algorithm has \begin{align} s_1 &= x_1 \\ s_j &= s_{j-1} + x_j. \end{align} It follows immediately that \begin{align} \hat{s}_1 &= x_1 \\ \hat{s}_j &= (\hat{s}_{j-1} + x_j. )\langle 1 \rangle \end{align} because each $x_j$ is a floating point number, so the only rounding errors are due to the additions. In the case of $m=6$ we find that
$$\hat{s}_6 = x_1 \langle 5 \rangle + x_2 \langle 5 \rangle + x_3 \langle 4 \rangle + x_4 \langle 3 \rangle + x_5 \langle 2 \rangle + x_6 \langle 1 \rangle.$$
We mention in passing that this pattern extends to the general case and that the terms that enter the calculation early are likely to make a large contribution to the absolute error. This is the reason why we should always start with the smallest terms when adding, say, positive numbers. Now, in the original problem every $x_j$ is really the computed product of three floating point numbers, say, $a_j, b_j, c_j$. It follows that $$x_j = a_jb_jc_j\langle 2 \rangle.$$ We can now conclude that the computed value $\hat{d}$ of the 3-by-3 determinant $d$ satisfies $$\hat{d} = a_1 b_1 c_1 \langle 7 \rangle + a_2b_2c_2 \langle 7 \rangle + a_3 b_3 c_3 \langle 6 \rangle + a_4 b_4 c_4 \langle 5 \rangle + a_5 b_5 c_5 \langle 4 \rangle + a_6b_6c_6 \langle 3 \rangle$$ assuming that the terms are added from left to right.


TITLE: What are the possible linking matrices of a quasi-positive link?
QUESTION [10 upvotes]: I was surprised recently to come across a 3-component link where the linking number of two of the components was negative. For a while I thought I had made a mistake, then I thought a little more and realized that there was no particular reason that the linking numbers had to be all positive.
The linking matrix I found was
$$\begin{pmatrix} * & 3 & 3 \\ 3 & * & -1 \\ 3 & -1 & * \end{pmatrix}.
$$
Here is the link. (I haven't attempted to find a quasi-positive representative yet, the proof it's quasi-positive was pretty indirect.)

REPLY [2 votes]: Any linking matrix appears as linking matrix of a strongly quasipositive link.
This follows from a result of Rudolph ("Constructions of Quasipositive Knots and Links, I") that any Seifert matrix appears as Seifert matrix of a strongly quasipositive link.


TITLE: Undecidable languages and mapping reducibility
QUESTION [3 upvotes]: I am using Sipser terminology here.
Can anyone give examples of languages A and B such that we can prove B is undecidable using A in a proof by contradiction but we A is not $\leq_m$ B.
An example of this is $E_{TM}$ as defined on page 89 of Sipser's Introduction to the Theory of Computation 2nd ed. We use $A_{TM}$ in the proof by contradiction but $A_{TM}$ is not mapping reducible to $E_{TM}$.
Thanks in advance.

REPLY [0 votes]: ATM is mapping reducable to ETM's compliment. Proving undecidablitiy can be done with either the original language, or it's compliment. This is not the case, for proving unrecognivability, however.


TITLE: How can I map the coordinate of a copied triangle in a parallelogram to the original triangle?
QUESTION [2 upvotes]: I've been reading the following article...
https://hbfs.wordpress.com/2010/10/05/random-points-in-a-triangle-generating-random-sequences-ii/
Which basically talks about how to generate a random point INSIDE of a triangle by:

Making a copy of the triangle
Transforming the copied triangle and joining the original triangle with the copied triangle to form a parallelogram.
Generating a random point within the parallelogram.
If the point is INSIDE of the COPIED triangle, map the point to the corresponding point in the ORIGINAL triangle.

I am currently on step 4 and I'm not understanding how exactly to transform the point into a point in the corresponding ORIGINAL triangle.
Could anyone help clarify how to accomplish this and what equation/formula is needed?

REPLY [0 votes]: Basically, do the same thing you did to create the parallelogram in the first place: reflect the point in the center of the parallelogram, which is the midpoint of the common edge of the two triangles. Referring back to the second diagram in my answer to your previous question, let $P$ be any point on the paralellogram and $M$ the midpoint of a diagonal (it doesn’t matter which one since they bisect each other). Then the point $P'=M-(P-M)$ is the corresponding point on the opposite half of the paralellogram. Notice that this is exactly the same formula that you used to compute the fourth vertex of the paralellogram from the vertices of the original triangle.


TITLE: What is the difference between a physical constant, a scalar, an invariant, and a conserved quantity?
QUESTION [2 upvotes]: I don't really know how to properly articulate this question. This question popped into my mind when pondering why the fact that a physical constant like the speed of light doesn't have an associated symmetry even though it's "conserved" in every frame of reference.

REPLY [7 votes]: A physical constant is a physical quantity that is generally believed to be both universal in nature and constant in time. Well-known examples include the speed of light (c), elementary charge (e), and Planck's constant (h). (More about physical constants here.)
A scalar (in the context of physics) is a physical quantity that can be described by a number and (generally) a unit of measurement. Examples include 41 lbs, 52 km/hr, and 96 degrees F. This is not to be confused with a vector, which includes both the quantity and direction. It should also be noted that a scalar is unchanged by rotations or reflections in Newtonian mechanics and unchanged by Lorentz transformations in relativity. (More about scalars in the context of physics here.)
A conserved quantity is a function of the dependent variables that is a constant (aka, conserved) along each trajectory of the system. Most laws of physics express some kind of conservation, meaning that conserved quantities are pretty common in mathematical models of real systems. As an example, any classical mechanics model will have energy as a conserved quantity as long as the forces involved are conservative. In the context of Noether's Theorem, the Noether charge and the Laplace-Runge-Lenz vector are both conserved quantities. If you look at this website about Noether's Theorem, conserved quantities are mentioned in more detail. (More about conserved quantities here.)
As for what you're pondering, I'm not sure I understand what you mean. If you could clarify what you mean by associated symmetry (sorry if that's a dumb question) that'd be helpful.
Hope this helps!

REPLY [4 votes]: A conserved quantity is a quantity whose value remains the same over time.
An invariant, or scalar quantity is a quantity whose value is the same in all reference frames.

These two properties are completely independent. Energy is conserved but not invariant. Mass (i.e. $E^2 - c^2 \mathbf{p}^2$) is invariant but not conserved. Charge is both, and lots of things are neither. All physical constants are invariant, otherwise they wouldn't be worth calling constants.
You are wondering if the invariance of the speed of light leads to a conserved quantity. The answer is no, because Noether's theorem deals with symmetries, not invariant quantities.
However, there is a deeper sense in which you are right. The invariance of the speed of light is one feature of Lorentz symmetry, and this symmetry does produce conserved quantities! Since Lorentz transformations include rotations, three of them are just angular momentum. The three boosts produce conserved quantities that are, heuristically, the "speed of the center of mass". A more detailed derivation can be found here.


TITLE: Find the generating set of $W=\{p \in \mathbb {P}_{3}(\mathbb{R}) \mid p(2)=0\}$
QUESTION [2 upvotes]: so i got stuck in this question. The purpose is to find a generating set for:
$$W=\{p \in \mathbb {P}_{3}(\mathbb{R}) \mid  p(2)=0\}$$
Where $ \mathbb {P}_{3}(\mathbb{R})$ is the vector space of the polynomials of degree three.
My idea was to write the polynomial in terms of a factor (x-2), so it would have the form:
$$p(x)=a_{o}+a_{1}(x-2)+a_{2}(x-2)^{2}+a_{3}(x-2)^{3}$$
So when x=2
$$p(2)= a_{o}=0$$
so the polynomal becomes
$$p(x)=a_{1}(x-2)+a_{2}(x-2)^{2}+a_{3}(x-2)^{3}$$
And the generating set would be
$$S=[(x-2),(x-2)^2,(x-2)^3]$$
But i'm not even a bit sure that it's right. I'd like to know what you guys have to say about it

REPLY [1 votes]: Your approach is good. Here I provide an alternative solution for the sake of curiosity.
Express $p\in W$ as $p(x) = a + bx + cx^{2} + dx^{3}$. Based on the given assumption, one has that
\begin{align*}
p(2) = a + 2b + 4c + 8d = 0
\end{align*}
Consequently, it results that
\begin{align*}
p(x) & = -(2b + 4c + 8d) + bx + cx^{2} + dx^{3}\\\\
& = b(x - 2) + c(x^{2} - 4) + d(x^{3} - 8)
\end{align*}
Finally, we conclude that $W = \text{span}\{x-2,x^{2}-4,x^{3}-8\}$, and we are done.
Hopefully this helps.


TITLE: Mean residual life: (improper) integration by parts involving p.d.f
QUESTION [0 upvotes]: Let a random variable $X$ be distributed with p.d.f $f(\cdot)$.
I want to derive the following equality for the mean residual life:
$$m(x)\equiv\frac{\int_{x}^{\infty}(z-x) f(z)dz}{1-F(x)}=\frac{\int_{x}^{\infty}1-F(z)dz}{1-F(x)}$$
Clearly, I can start by splitting the left-hand-side to get $\frac{\int_{x}^{\infty}z f(z)dz-x\int_{x}^{\infty} f(z)dz}{1-F(x)}=\frac{\left(\int_{x}^{\infty}z f(z)dz\right)-x(1-F(x))}{1-F(x)}$. From this it looks like all I need to do is integration by parts for $\int_{x}^{\infty}z f(z)dz$ with $u(z)=z$ and $v(z)=dF(z)$, but I don't see how this converges to the desired result.

REPLY [0 votes]: The mean residual life $m(x)$ at time $x$ of a system with lifetime $X$,
a nonnegative
random variable, is the expected lifetime beyond $x$ of a system that has
survived till time $x$, that is, $$m(x) =  E[X\mid X > x] - x.$$  Now,
the conditional pdf of $X$ given that $X > x$ is just
$\displaystyle \frac{f(z)}{P\{X > x\}}\mathbf 1_{\{z: z>x\}}
= \frac{f(z)}{1-F(x)}\mathbf 1_{\{z: z>x\}}$ and so
$$\begin{align}
m(x) &= E[X\mid X > x] -x\\
&= \int_x^{\infty}z\frac{f(z)}{1-F(x)}\mathrm dz - x\\
&= \int_x^{\infty}z\frac{f(z)}{1-F(x)}\mathrm dz - x\int_x^{\infty}\frac{f(z)}{1-F(x)}\mathrm dz\\
&= \int_x^{\infty}\frac{(z-x)f(z)}{1-F(x)}\mathrm dz.
\end{align}$$
The second equality uses the result that for a (integrable)
nonnegative random variable $Y$ with CDF $F_Y(y)$,
$$E[Y] = \int_0^\infty [1-F_Y(y)]\,\mathrm dy.$$
If you are unfamiliar with this
result, see, for example,
this question for a discussion
of the intuition behind this result and then read the complete proof.
The conditional CDF of $X$ given that $X > x$ is given by
$$F_{X\mid X>x}(z\mid X > x) = \frac{F(z)-F(x)}{1-F(x)}\mathbf 1_{\{z: z>x\}}$$
so that the complementary CDF has value
$\displaystyle \mathbf 1_{\{z: 0 < z < x\}} + \frac{1-F(z)}{1-F(x)}
\mathbf 1_{\{z: z>x\}}$ on the
positive real line.  The integral of the complementary CDF over the positive
real line gives
$$E[X \mid X > x] = x + \int_x^\infty \frac{1-F(z)}{1-F(x)}\mathrm dz$$
and since $m(x) =  E[X \mid X > x] - x$, the desired equality follows.


TITLE: Is this action a Hamilton's principal function?
QUESTION [2 upvotes]: In Ref. 1, in section 3, they wrote:
\begin{equation}
L'(q,\dot{q},\ddot{q},t)~=~L(q,\dot{q},\ddot{q},t)-\frac{dS(q,\dot{q},t)}{dt}.\tag{14}
\end{equation}
Then the Hamilton-Jacobi equation is
\begin{equation}
\frac{\partial S}{\partial t}~=~-H_0,\tag{27}
\end{equation}
where $$H_0~=~p\dot{q}+\pi\ddot{q}-L,\tag{28}$$ where
$$p~=~\dfrac{\partial S}{\partial q}\quad\text{and}\quad
\pi~=~\dfrac{\partial S}{\partial \dot{q}}.\tag{29}$$
I was confused because here the action is a function of $\dot{q}$ ! Then I read this answer by Qmechanic, and I had this question: is this action a Hamilton's principle function? If yes, in Hamilton's principal function $S(q,\alpha,t)$, the $\alpha$ is an integration constant. But here we have $S(q,\dot{q},t)$;  $\dot{q}$ is not an integration constant. If no, what is that action?
EDIT: I want to know if the function $S$ is considered as an action. If yes, I need an explanation on how an action could be a function of $\dot{q}$? And if no, how is this function related to the known action $S[q]$?
References:

B.M. Pimentel & R.G. Teixeira, Hamilton-Jacobi formulation for singular systems with second order Lagrangians, arXiv:hep-th/9512099.

REPLY [1 votes]: OP is asking about Ref. 1. This touches upon several topics:

Second-order Lagrangian formulations and their corresponding Ostrogradsky Hamiltonian formulation. This is discussed in e.g. this Phys.SE post, where it is explained how to reduce to first-order formulation in the non-singular case.
Singular Legendre transformations, and constraints. See e.g. Ref. 2 & 3.
Caratheodory’s method of equivalent Lagrangians, and its connection to Hamilton-Jacobi theory. This is explained in Ref. 4 in the first-order case.

Now let us return to OP's title question. Let us stress that the Hamilton's principal function $S$ and the off-shell action functional $S[q]$ are different objects. (For first-order Lagrangians, this is e.g. explained in my Phys.SE answers here & here.) In particular, eq. (14) is part of Caratheodory’s method of equivalent Lagrangians. The $S$ appearing in eq. (14) is Hamilton's principal function, not the off-shell action functional. It depends on velocities because the theory is of second order.
References:

B.M. Pimentel & R.G. Teixeira, Hamilton-Jacobi formulation for singular systems with second order Lagrangians, arXiv:hep-th/9512099.
P.A.M. Dirac, Lectures on QM, (1964).
M. Henneaux and C. Teitelboim, Quantization of Gauge Systems, 1994.
H.A. Kastrup, Canonical theories of Lagrangian dynamical systems in physics, Phys. Rep. 101 (1983) 1; Section 2.4.


TITLE: How to tell if a 2d point is within a set of Bézier curves?
QUESTION [3 upvotes]: I have a set of Bézier curves defined like pictured:

They make a closed shape like so:

Given a point $\left(x,y\right)$ I need to tell if it is inside this set of Bézier curves, each defined by four points.
Edit: pseudocode can be given too :)

REPLY [1 votes]: There are a few ways to do this:

Approximate each Bézier curve by a polyline. Then your problem becomes a point-in-polygon problem, which has been studied to death. The Wikipedia page on the subject describes two techniques: one based on firing rays and counting intersections, and the other based on winding numbers. Of course, the results will only be as accurate as your polyline approximation. If you want to avoid errors due to this approximation, you can apply the ray-firing algorithm directly to the original Bézier curves. You'll have to write (or find) a function to intersect a line with a Bézier curve. This involves solving a cubic equation. You can find relevant stuff here and here and here.
The fastest approach is to just render your shape into a bitmap (which you already know how to do, it appears), and see if the bitmap covers your point. So, specifically, you set the pixel at your test point to white, render the shape in black, and see if your point remains white. This way, you're using the GPU to do the bulk of the calculations, and that's what gives you the speed.

The above are general methods. Your particular case seems quite special, though -- the large yellow region appears to be bordered by four Bézier curves that have horizontal and vertical tangents. In testing the yellow region, you may be able to take advantage of this simplicity.


TITLE: I have a question about permutation.
QUESTION [0 upvotes]: I have the following question:
Determine the value of n from:
nP3 = 5 (4P2)
I don't know how I should begin to tackle this problem? Any tips/help would be appreciated.
permutations

REPLY [0 votes]: The RHS is $(5)\cdot \frac{4!}{(4-2)!} = (5)(12) = 60$
The LHS is $\frac{n!}{(n-3)!} = n(n-1)(n-2)$. So you need the product of three consecutive natural numbers to be $60$. An easy guess would give you $n=5$.
OK, to be a little more systematic, three consecutive naturals would comprise either even, odd, even (case 1) or odd, even, odd (case 2). In the first case, one even would be a multiple of $4$ (since alternate evens are multiples of $4$), which would make the product a multiple of $8$. But $60$ isn't a multiple of $8$. So case 2 must hold, and the middle number has to be even. Furthermore, the middle even must be a multiple of $4$ as $60$ is a multiple of $4$. And so we try the first positive multiple of $4$, namely $4$ itself as the middle number to get $(3)(4)(5) = 60$ as required, and we're done.
You can, of course, expand and solve the cubic but that's just unnecessary here.


TITLE: Show that there is $\xi$ s.t. $f(\xi)=f\left(\xi+\frac{1}{n}\right)$
QUESTION [3 upvotes]: Let $f:[0,1]\to\mathbb{R}$ be continuous and $f(0)=f(1)$. Show that for any integer $n\geqslant 2$, there is $\xi\in(0,1)$ s.t.$f(\xi)=f\left(\xi+\frac{1}{n}\right).$
I think this requires the intermediate value theorem somewhere.

REPLY [9 votes]: Fix $\delta = 1/n, n \in \mathbb{N}.$ Consider the continuous function $g_n(x) :[0,1-\delta] \to \mathbb{R} ; g_n(x) := f(x+\tfrac{1}{n}) - f(x)$ and suppose that $g_n(x) \neq 0$ on $I_0 := [0,1].$ Then by the intermediate value theorem, $g_n(x)$ does not change sign in $I_0.$ WLOG, if $g_n(x) > 0,$ then adding the $n$ inequalities,
$$
g_n(1-\tfrac{1}{n}) = f(1) - f(1-\tfrac{1}{n}) > 0,
$$
$$
g_n(1-\tfrac{2}{n}) = f(1-\tfrac{1}{n}) - f(1-\tfrac{2}{n}) > 0,
$$
$$
\cdots
$$
$$g_n(0) = f(\tfrac{1}{n}) - f(0) > 0,
$$
yields $f(1) > f(0),$ which contradicts the hypothesis that $f(1) = f(0).$
Thus there exists a point $x_n$ satisfying $f(x_n + \tfrac{1}{n}) = f(x_n).$


TITLE: Need to split 2n teams into n different games with no team meeting another team or playing a game more than once
QUESTION [2 upvotes]: I've found multiple similar questions, but none answering this case, and I can't manage to extrapolate from the other answers. The closest I've found is this one.
Here is my problem:
I have 10 different mini-games, and 20 teams. I also have (ideally) only 10 timeslots, or rounds. Every team needs to play every game exactly once, and every game they will be facing-off against another team.
I don't need every team to face every other team. Although, I would like them to never face the same team twice.
I've created a brute-force code which picks a random permutation of games for team 1, then picks games for every team after that, ensuring that everything remains valid (2 teams need to be at the same game in the same round). I then compute the amount of "unique encounters" (meaning a team facing off against another team they haven't seen before), and try to maximize that.
Ideally then, for 20 teams and 10 games, I'm looking for every team to have 10 unique encounters, so a total of 200 unique encounters.
I've managed to find perfect solutions for up to 10 teams and 5 games (example below), but the way I'm approaching the problem is so exponential that I haven't found a perfect solution for 12 teams and 6 games (best I've found is 70 uniques out of 72, so only 2 teams meeting twice), let alone for 20 teams and 10 games. The best I've found for 20 teams and 10 games is 182 uniques out of a possible 200.
Example for 10 teams and 5 games:
Best representation, with 50 uniques and no team meeting less than 5 opponents:
          Round 1 Round 2 Round 3 Round 4 Round 5
Team 1       g3      g0      g2      g4      g1
Team 2       g3      g1      g4      g2      g0
Team 3       g1      g3      g0      g2      g4
Team 4       g2      g4      g1      g3      g0
Team 5       g0      g3      g1      g4      g2
Team 6       g4      g1      g0      g3      g2
Team 7       g1      g4      g2      g0      g3
Team 8       g4      g2      g3      g0      g1
Team 9       g0      g2      g4      g1      g3
Team 10      g2      g0      g3      g1      g4

I believe the problem can be re-written as:
Need to select 2n different permutations of a set of n items such that every item is in every position exactly twice, i.e. no item is in the same position more than 2 times.
It's obviously not feasible to brute force this for 20 teams and 10 games, so I see that my approach isn't the right one. From the other answers I've seen that I should be using an approach similar to colored graphs, but I have absolutely no experience with those.
Any help would be greatly appreciated, be it only a solution table for 20 teams and 10 games, or an actual algorithm to compute a solution for any n number of games, or even a hint of what to look for in order to create this algorithm myself.
Thank you!

REPLY [2 votes]: Here is a schedule that works. Each row is a team, each column is a round, and the games are numbered $0$ to $9$.

${}$
R1
R2
R3
R4
R5
R6
R7
R8
R9
R10

T1
$0$
$8$
$9$
$5$
$7$
$6$
$3$
$1$
$2$
$4$

T2
$4$
$1$
$8$
$9$
$6$
$7$
$0$
$2$
$3$
$5$

T3
$1$
$5$
$2$
$8$
$9$
$0$
$7$
$3$
$4$
$6$

T4
$7$
$2$
$6$
$3$
$8$
$9$
$1$
$4$
$5$
$0$

T5
$2$
$7$
$3$
$0$
$4$
$8$
$9$
$5$
$6$
$1$

T6
$9$
$3$
$7$
$4$
$1$
$5$
$8$
$6$
$0$
$2$

T7
$8$
$9$
$4$
$7$
$5$
$2$
$6$
$0$
$1$
$3$

T8
$3$
$4$
$5$
$6$
$0$
$1$
$2$
$7$
$8$
$9$

T9
$6$
$0$
$1$
$2$
$3$
$4$
$5$
$8$
$9$
$7$

T10
$5$
$6$
$0$
$1$
$2$
$3$
$4$
$9$
$7$
$8$

T11
$0$
$6$
$5$
$9$
$3$
$8$
$7$
$4$
$1$
$2$

T12
$7$
$1$
$0$
$6$
$9$
$4$
$8$
$5$
$2$
$3$

T13
$8$
$7$
$2$
$1$
$0$
$9$
$5$
$6$
$3$
$4$

T14
$6$
$8$
$7$
$3$
$2$
$1$
$9$
$0$
$4$
$5$

T15
$9$
$0$
$8$
$7$
$4$
$3$
$2$
$1$
$5$
$6$

T16
$3$
$9$
$1$
$8$
$7$
$5$
$4$
$2$
$6$
$0$

T17
$5$
$4$
$9$
$2$
$8$
$7$
$6$
$3$
$0$
$1$

T18
$4$
$5$
$6$
$0$
$1$
$2$
$3$
$7$
$9$
$8$

T19
$1$
$2$
$3$
$4$
$5$
$6$
$0$
$8$
$7$
$9$

T20
$2$
$3$
$4$
$5$
$6$
$0$
$1$
$9$
$8$
$7$

I found this by taking an orthogonal pair of $10$ by $10$ Latin Squares, and concatenating them vertically. In general, if you have $n$ different mini-games, each of which takes $k$ players, then you can get a schedule for $nk$ players to each play all the games over $n$ rounds without repeating teammates by concatenating  together $k$ mutually orthogonal Latin squares. This known to be possible whenever $n$ is a prime power (and $k\le n-1$).


TITLE: Folium of Descartes
QUESTION [12 upvotes]: A colleague came to me with an interesting observation:
Consider the folium of Descartes, $$x^3+y^3=3axy$$ which upon implicit differentiation of the latter yields $$\frac{\mathrm dy}{\mathrm dx}=\frac{ay-x^2}{y^2-ax}$$
Now, the interesting observation is that if one considers the set of curves parametrized by $m\in\mathbb{R}$ $$ay-x^2=m(y^2-ax),$$ then all the curves intersect at a single point within the loop of the folium (namely, $(a,a)$).
Further experimentation yielded similar results for the family of curves $$x^n+y^n=naxy.$$  It is clear how this all "works," but what is unclear is
Why should these curves intersect?
Furthermore,
Is there a name to describe this behavior/phenomenon?
To clarify further, the point of intersection corresponds to the value where both the numerator and denominator in the derivative vanish (this also happens at the origin).  This is what is meant by how this "works."
Thanks!
Edit:  Added a picture to hopefully aid in my explanation.  (Curves correspond to $a=2, m=1, \frac12, -\frac{1}{2}$.)

Edit2: Fixed derivative formula.

REPLY [3 votes]: You are considering the pencil of conics generated by $ay-x^2$ and $y^2-ax$. Such a pencil will have 4 common points counted with multiplicity over an algebraically closed field. The common points can be found by elimination of one of the variables: for a point on $x=y^2/a$ then $0=ay-x^2=ay-y^4/a^2$. The solutions are $y=0$ and $y^3=a^3$. The solution $y=a$ gives $x=a$, the point mentioned in the problem. The value $y=0$, yields $x=0$. The other solutions are complex.
For the other curve mentioned the derivative will have a numerator $N$ of degree $m$ and denominator $D$ of degree $d$. In this case the (projective) pencil generated by the numerator $N$ and denominator $D$ is the family of curves $N+tD=0$ for varying $t$ together with the additional curve $D=0$. By Bezout's theorem there will be $md$ common points of the pencil


TITLE: Find conditions for a polynomial $p$ to be in a vector space $U$
QUESTION [0 upvotes]: Let $U = \operatorname{span}\{1+x, x + x^2, x^2-1\}$ and $p(x) = 2x^2 - 3x + m$.
Find all $m$ such that $p(x)$ lies in $U$.
This is a problem is my textbook. I don't understand very well how to do that.
Thanks :)

REPLY [2 votes]: note that $x^2+x-(x^2-1)=x+1$, so $U=\operatorname{span}\{x+1, x^2-1\}$, then first write $2x^2-3x=2(x^2-1)-3(x+1)+5$, and note that $U$ can not contain any complex numbers, so the only choice for $m$ is $m=-5$.


TITLE: Photons are faster than the speed of light because they travel in transversal waves?
QUESTION [2 upvotes]: This is my first time posting here, I am a school student who is just curious. So today I was wondering about how light works and how it travels, and this thought came to my mind:
Light is made of photons traveling in transversal waves, doesn't this mean that photons are moving in longer distances than light itself because photons don't move in a straight line, while taking the same time that light does to reach the same position, so does this mean that the speed of photons is actually greater than the speed of light?

REPLY [1 votes]: The electromagnetic field is transverse, because "its electric and magnetic fields rotate continuously around the beam axis during propagation". This statement from the Wikipedia reference refers to circular polarization. Light has a circular polarization when the spin of all photons points in the same direction. Linear polarization of the transverse wave involves an equal mix of photons with the opposite spin. The image from the article clearly shows how the transverse field is comprised of the photons flying straight: