TITLE: Please show how to calculate the probability for outcomes of this Battle Royale scenario.
QUESTION [2 upvotes]: Please note: This is not about an isolated problem at all, but rather a way of quantifying and visualizing an obfuscated and confusing game theory related model in an easy to grasp manner. For that I require the assistance of math experts in probability, which I am not. If you are interested in helping ,please show how to calculate the probability of results for the following game scenario.
I hope someone finds this interesting. I appreciate your help, Thank you!
Edit: Forum members have enlightened me to the complexity of the scenario and I appreciate all of the comments.  I have made some edits in response to the comments..thank you.
Problem:
A Battle Royale/last person standing elimination match tournament.
Matches are comprised of 64 players per match, randomly populated.
Players compete in 1 on 1 encounters throughout the match. 1 player is eliminated in each encounter until there is 1 player left in the match- the last person standing.
A forum member asked how the match ups are decided. maybe it should be 64 players per match for simplicity sake with random matching of pairs for 5?? rounds.
At the end of each match points are awarded to the top 3 finishers as follows: 1st place =15 points, 2nd place = 8 points, 3rd thru 4th place = 4 points, and 5th thru 64th place =zero points.
There are two types of player:
Player type L and Player type H.
Player type L has no advantage over any other Player type L in an encounter and the outcome is 50/50 or a coin toss as to who wins.  However, Player L has a disadvantage in an encounter with Player H. Player type H has a 20x advantage in winning an encounter with Player L.
Player H has no advantage in an encounter with another Player type H, where the outcome is a 50/50 coin toss as to who wins. However, Player type H has a 20x advantage versus any Player type L in an encounter.
Each Player will play exactly 150 matches in the season.
A leader board reports every player’s accumulated points total score for the season.
There are 4,700,000 type L players
There are 300,000 type H players.
Without adding any other variables or complexity to the scenario above, what is the probability of the following expressed in 1 out of X  and or other terms:
That a type L player would finish the season in the top 500 ranks of points accumulated (out of 5,000,000)?
That the number 1 rank will be a type H?
That the number 500 rank will be a type H?
That the number 1 rank will be a type L?
Thank you very much in advance for your help.
Edit: This discussion has been productive and I realized that I needed to tweak the scenario a bit to better reflect the key elements of the real world situation. Comparing independent L and H distributions is interesting but as you noted L and H types are competing together in the same matches.   In my tweaked scenario H players make up about 6 percent of the total population. Also the advantage was way to low, so I adjusted it to 20x.
For the sake of simplifying a ballpark estimate, maybe the starting point is to calculate the probability of H and L obtaining points through either a first or second place win in a single typical (“mean”) match.  And then find a way to adjust for the probable deviations from the typical match in 150 matches.
What causes the results of a match to deviate from the “mean” other than the occurrence of no H player present in the match? How likely is it to have a match with no H player present? This seems like a way to come up with some ballpark probabilities for H or L appearing on the Leaderboard in the top 500, or the probability for H or L taking 1st place.

REPLY [0 votes]: This is not a full answer due to lack of time on my part to work out the details (so don't accept it), but this is an outline on how to get one.
First step
First, we only observe the outcome of a fixed player. Say that there are $N\in\mathbb N$ players (in your case, $N=30000000$). Number the players in arbitrary order from $1$ to $N$ and fix some $k\in\{1,\dots ,N\}$. The probability of winning in a given game for player $k$ depends only whether he himself is H or L, and on the number of H or L players in that game. Say that the player plays $g\in\mathbb N$ games in total (in your case, $g=150$). Let $B_1^{(k)},\dots, B_g^{(k)}$ denote  the points this player receives in games $1$ through $g$, respectively. The total number of points that player $k$ has at the end is $T^{(k)}_g \overset{\text{Def.}}=B_1^{(k)}+\dots+B_g^{(k)}$. From the modeling assumptions, the $B_1,\dots, B_g$ are independent and identically distributed. Furthermore, they only take finitely many values (in your case, for example, there are $4$ possible outcomes: One can get $0$, $4$, $8$ or $15$ points.)
From the Berry-Esseen estimates (see for example [1; Satz 15.51] for the formal statement, you may also find references using a search engine), if $(B_j^{(k)})_{j\in\mathbb N}$ is a sequence of iid real random variables satisfying $B_1^{(k)}\in L^3$ and $\mathsf V(B_1^{(k)})>0$, we have, with $T^{(k)}_g \overset{\text{Def.}}=B_1^{(k)}+\dots+B_g^{(k)}$, (and $\Phi(x)\overset{\text{Def.}}=\frac1{\sqrt{2\pi}}\int_{-\infty}^x\exp(-y^2/2)\,\mathrm dy$ denoting the CDF of the standard normal distribution)
$$\sup_{x\in\mathbb R}\left\lvert\mathsf P\left(\frac{T_g^{(k)}-\mathsf E(T_g^{(k)})}{\mathsf V(T_g^{(k)})}\le x\right)-\Phi(x)\right\rvert\le\frac{0.6\mathsf E(\lvert B_1^{(k)}\rvert^3)}{\mathsf V(B_1^{(k)})^{\frac 32}},$$
for all $g\in\mathbb N$.
Coming back to our case: Since $B_1^{(k)}$ takes finitely many values, it is clearly $L^3$. And it is also clear that $\mathsf V(B_1^{(k)})>0$.
Therefore, for $g$ large enough, Berry-Esseen gives that the CDF of $T_g^{(k)}$ is, "close" to the CDF of a normal distribution $\mathcal N(\mathsf E(T_g^{(k)}), \mathsf V(T_g^{(k)}))$.
Second step
You have to determine $\mathsf E(T_g^{(k)})$ and $\mathsf V(T_g^{(k)})$. Note that these two quantities only depend on whether player $k$ is of type H or type L. To determine $\mathsf E(T_g^{(k)})$ and $\mathsf V(T_g^{(k)})$, I recommend to first answer the following question ("the big question"): "What is the probability that a player of type L/H gets first/second/third/fourth place in a game of $64$ (or more, generally, $n$) players such that $k$ players other than the player himself are of H type?"
Denote by $h$ the total number of H players (in this case $h=29900000$) and let $l$ be the total number of L players (in this case $l=100000$).
Let $N^{(k)}$ denote the number of H-players in the first game of player $k$, where player $k$ is not counted should he be a H-player. Then, by the modeling assumption, $N^{(k)}$ is a random variable with hypergeometric distribution with population size $h+l$ and $h$ "success states" as well as $l$ "non-success states" and $63$ draws.
From the law of total expectation, we then get
$$\mathsf E(B_1^{(k)})=\sum_{j=0}^{63}\mathsf E(B_1^{(k)}\vert N^{(k)}=j)\frac{\binom{h}{j}\binom{l}{63-j}}{\binom{h+l}{63}}.$$
Once you answer the big question above (this can be done approximately using simulations and maybe even exactly using combinatorial arguments), you immediately get $\mathsf E(B_1^{(k)}\vert N^{(k)}=j)$, from which you can deduce the value of $\mathsf E(B_1^{(k)})$. Analogously, you can determine $\mathsf V(B_1^{(k)})$.
Third step
Without loss of generality we may assume that players $1,\dots, l$ are of L-type and players $l+1,\dots, l+h$ are of H-type.
We therefore have $E_L\overset{\text{Def.}}=\mathsf E(T_g^{(1)}=\dots=\mathsf E(T_g^{(l)})$, as well as $E_H\overset{\text{Def.}}=\mathsf E(T_g^{(l+1)}=\dots=\mathsf E(T_g^{(h)})$ and $V_L\overset{\text{Def.}}=\mathsf V(T_g^{(1)})=\dots=\mathsf V(T_g^{(l)})$, as well as $V_H\overset{\text{Def.}}=\mathsf V(T_g^{(l+1)})=\dots=\mathsf V(T_g^{(h)})$.
From the argument in the first step, the "top 1" (or "top 500") performance of L-type players is just the maximum ("500"-th biggest) of $l$ random variables that are $\mathcal N(E_L, V_L)$-distributed. These random variables are not independent (if one person looses, the other wins), however it seems like a useful approximation to at first assume that these are independent and to do the same for the H-type players.
The maximum of iid normal distributions hcan be tackled analytically, see for example this question and this question, or approximately using Monte-Carlo-type simulations.

References
[1] Achim Klenke, Wahrscheinlichkeitstheorie. 3. Auflage. Springer-Verlag Berlin/Heidelberg (2013).


TITLE: Finding the basis for the intersection of two subspaces
QUESTION [4 upvotes]: Find a basis for the intersection of the subspaces $X_1$ and $X_2$ of $\mathbb{R^4}$ where $$X_1=\text{span}\left\{ (1,1,0,0), (0,1,1,0), (0,0,1,1)\right\}$$
and $$X_2=\text{span}\left\{ (1,0,t,0), (0,1,0,t)\right\},$$ where $t\in \mathbb{R}$ is given.
Well, I know that if $v\in X_1\cap X_2$, then
$v=a(1,1,0,0)+ b(0,1,1,0)+ c(0,0,1,1)=d(1,0,t,0)+ m(0,1,0,t)$,
where $a, b, c, d, m \in \mathbb{R}$. Then
this implies that
$(0,0,0,0)=v-v=(a-d,a+b-m,b+c-dt,c-mt)$,
that is $$a-d=0$$ $$a+b-m=0$$ $$b+c-dt=0$$ $$c-mt=0.$$
Since $t\in \mathbb{R}$ is given, I have 5 unknowns and 4 equations. I can't solve this! Is there any other way to solve this problem??
Thank you!

REPLY [2 votes]: I like the answer given by @thanasissdr and I'll add a simple approach to complement his, which works in this case because the equations aren't too complicated.
You can very easily see that $a=d$ for the first equation, $c=mt$ from the fourth. Using these in the middle two gives you a simultaneous equation:
\begin{align}
&b+a-m=0\\
&b-at+mt=0
\end{align}
Subtracting the two gives that:
$$a(1+t)=m(1+t)$$
Now for $t\neq -1$ we can conclude that $a=m=d$ and $b=0$ and $c=at$
So $(a,b,c,d,m)=a(1,0,t,1,1)$ or since $v=d(1,0,t,0)+m(0,1,0,t)=a(1,1,t,t)$.
We can conclude that the intersection is one dimensional and taking $a=1$ say:
$$X_1\cap X_2=\operatorname{span}\{(1,1,t,t)\}$$
You can probably justify that five variables and four constraints suggests that there will be one free variable and hence a dimension $1$ space at the end.
Now for the case we excluded $t=-1$ we can see that if $X_1=\operatorname{span}\{e_1,e_2,e_3\}$ then $X_2=\operatorname{span}\{e_1-e_2,e_2-e_3\}$. So $X_2\subset X_1$ and hence $$X_1\cap X_2=X_2$$
Again you could justify this by noticing that when $t=-1$ using equations one and four we see that equations two and three are the same. So five unknowns and three constraints suggests the space will be $2$ dimensional.
Finally if you want to check dimensions you could use that
$$\dim(X_1+X_2)=\dim(X_1)+\dim(X_2)-\dim(X_1\cap X_2)$$
$\dim(X_1+X_2)=3,4$ only so $\dim(X_1\cap X_2)=1,2$ only.


TITLE: Is tutor essential for success in mathematics?
QUESTION [0 upvotes]: Everyone in my Pre-Calc - Calc I class is failing, except the kids who go tutor. They get top percentile ranks in the class. Should I drop maths all together so I don't have to invest in a tutor? I understand this is quite a subjective post, but I still do believe a solid answer lies here.

REPLY [1 votes]: For every chapter after the lecture you should sit down and try to attempt the problem sets.  Usually there will be an easier problem that the instructor has gone through in class that will lead you through most of the exercises.  When you get stuck go back and reread.
Find examples in the text chapters, which you also should read and  work through. Especially the problems the book does for you.   Go through those yourself and cover up the next step. Try to intuitively find the answer and verify if you're correct. When you get to the non solved problems they will usually be similar.
Do some reading online or download other lectures.  You live in such an amazing time that I would have killed for in college.  You can supplement any lectures with Kahn academy, iTunes U.   MIT Open Courseware etc.   There are lots of ways of explaining the same things and if one doesn't work for you chances are other methods might hit home.
These are the things I do as someone working independently on catching up for concepts useful in Algorithms for my software work.
Finally the thing I don't have that you should really take advantage of. Teacher availability at office hours (or over Lunch if it's HS).   Usually HS instructors are elated that someone cares enough to come by after school.  Professors even at large universities usually have very few visitors during office hours. Utilize these people once you've done the work above to go over the concepts that don't make sense.
Don't give up. If you do, you will kick yourself hard in years to come.  I still do. I'm 36 and finally in the field I want to be in after dropping to an easier major at 19.  It's the easy way out.  Put in the work now while you don't have other obligations and distractions.


TITLE: Sobolev inequality for fractional derivative
QUESTION [4 upvotes]: Let $f:\mathbb R^n \to \mathbb C$ be a nice function. We define the gradient of $f$ as
$$\nabla f(x)= (\frac{\partial f(x)}{\partial x_1},..., \frac{\partial f(x)}{\partial x_n})$$ for $x=(x_1,...,x_n)\in \mathbb R^n.$

My Question is: How to define the fractional gradient(derivative)? Dose it make sense to talk of $|\nabla  |^{\alpha} f     \    \    (\alpha \in \mathbb R)$?

We have the Sobolev embedding:  $\|u\|_{L^{p*}} \leq C \|\nabla u \|_{L^p}$ for $p<n$ and $p*=\frac{np}{n-p}.$

Can we use Sobolev embedding  to show: $\|u\|_{L^{\frac{2n^2(n+2)}{(n+4)(n-2)^2}}} \leq C_1 \||\nabla|^{4/n+2} u \|_{L^{\frac{2n^2(n+2)}{n^3-4n+16}}} (n\geq 3)$?

REPLY [1 votes]: Yes, it does make sense to talk about "fractional derivatives". The spaces you
are looking for are either fractional Sobolev spaces or Besov spaces. In this
case instead of gradients you have difference quotients.
For fractional Sobolev spaces $W^{s,p}(\mathbb{R}^{n})$ the subcritical case
is $s>0$, $1\leq p<n/s$. For you $s=\frac{4}{n+2}$ so you need
$$
p=\frac{2n^{2}(n+2)}{n^{3}-4n+16}<n/s=\frac{n(n+2)}{4}%
$$
which reduces to $8n<n^{3}-4n+16$, Solution is: $\left(  -4,2\right)
\cup\left(  2,\infty\right)  $ which holds for $n>2$. The critical exponent
becomes%
\begin{align*}
p_{s}^{\ast} &  :=\frac{np}{n-sp}=\frac{n\frac{2n^{2}(n+2)}{n^{3}-4n+16}%
}{n-\frac{4}{n+2}\frac{2n^{2}(n+2)}{n^{3}-4n+16}}\\
&  =\frac{2n^{2}(n+2)}{(n-2)^{2}(n+4)},
\end{align*}
as you wanted. The inequality would actually give you%
$$
\Vert u\Vert_{L^{p_{s}^{\ast}}(\mathbb{R}^{n})}\leq c\Vert u\Vert
_{W^{s,p}(\mathbb{R}^{n})},$$
namely on the right-hand side the full norm and not the seminorm.
For more info on fractional Sobolev spaces, take a look at Adams and Fournier
"Sobolev spaces", Burenkov "Sobolev spaces", Leoni "A First Course in Sobolev
Spaces", Mayza "Sobolev spaces" and then there are really a lot of books on
Besov spaces, Triebel is the bible but it is difficult to read. Take a look at
wikipedia for that.


TITLE: Diophantine equation of prime numbers
QUESTION [3 upvotes]: Determine all pairs of prime numbers $(p,q)$ that satisfy the equation
$p^3-q^3=pq^3-1$.
I can easily understand that
$p>q$, $q^3=p^2-p+1$, $q^3\equiv 1 \pmod{p}$, $p^3\equiv -1 \pmod{q}$.
But I don't know how to go on. (I know that p=19 and q=7 works)

REPLY [2 votes]: $p^2 - p + 1 = q^3$
$p(p-1) = (q-1)(q^2+q+1)$.
As you noticed, $p>q$, so $q-1$ is coprime with $p$. So $q-1|p-1$, or instead we can write
$k(q-1)=p-1$ and $kp=q^2 + q + 1$ for some integer $k>1$.
Get $p$ from the first equation and plug it to the second one:
$k(kq - k + 1) = q^2 + q + 1$
$q^2 + (1-k^2)q +1-k+k^2=0$
So $q$ can only be an integer if discriminant of above equation is a square:
$\Delta = k^4 - 6k^2 + 4k - 3$
But $(k^2 - 3)^2 < \Delta < (k^2 - 2)^2$ for $k>3$.
So we only need to consider $k=2, 3$. For $k=2$, $\Delta$ is not a square. For $k=3$, $\Delta=36$, the quadratic equation has solutions $q=1, 7$. $q=7$ gives $p=19$.
So the only solution for $p, q$ primes is $(19, 7)$.


text:
\begin{document}

\title{Tilted Halved Hexagons: Hexagons, Semi-hexagons, and Halved Hexagons Under One Roof}

\author{Tri Lai}
\address{Department of Mathematics, University of Nebraska -- Lincoln, Lincoln, NE 68588, U.S.A.}
\email{tlai3@unl.edu}
\thanks{This research was supported in part  by Simons Foundation Collaboration Grant (\# 585923).}

\subjclass[2010]{05A15,  05B45}

\keywords{perfect matchings, plane partitions, lozenge tilings}

\date{\today}

\dedicatory{}

\begin{abstract}
We investigate a new family of regions that is the universal generalization of three well-known region families in the field of enumeration of tilings: the quasi-regular hexagons, the semi-hexagons, and the halved hexagons. We prove a simple product formula for the number of tilings of these new regions. Our main result also yields the enumerations of two special classes of plane partitions with restricted parts.
\end{abstract}

\maketitle
\section{Introduction}\label{Sec:Intro}

One of the most well-known regions in the field of  enumeration of tilings is the `\emph{quasi-regular hexagon}',  a centrally symmetric hexagon with all $120^{\circ}$ angles. MacMahon's theorem \cite{Mac} on plane partitions fitting in an $(a\times b\times c)$-box yields an elegant product formula for the number of lozenge tilings of a quasi-regular hexagon $H_{a,b,c}$ of side-lengths $a,b,c,a,b,c$ \cite{DT} (in counter-clockwise order, starting from the north side\footnote{From now on we always list the side-lengths of a region in this order.}):
\begin{equation}\label{Maceq}
\M(H_{a,b,c})=\prod_{i=1}^{a}\prod_{j=1}^{b}\prod_{k=1}^{c}\frac{i+j+k-1}{i+j+k-2},
\end{equation}
where $\M(R)$ denotes the number of lozenge tilings in the region $R$. Here, a \emph{lozenge} (or \emph{unit rhombus}) is a union of any two unit equilateral triangles sharing an edge, and a \emph{lozenge tiling} of a region is a covering of the region by lozenges with no gaps or overlaps. See Figure \ref{Fig:3polar} (a) for an example of a quasi-regular hexagon and Figure \ref{Fig:3polar}(d) for a lozenge tiling.

\begin{figure}\centering
\includegraphics[width=12cm]{3polar.eps}
\caption{(a) A quasi-regular hexagon, (b) a dented semi-hexagon, (c) a halved hexagon, and (d,e,f) their tilings.}\label{Fig:3polar}
\end{figure}

Cohn, Larsen, and Propp \cite[Proposition 2.1]{CLP} generalized MacMahon's theorem by giving a one-to-one correspondence between lozenge tilings of a \emph{semi-hexagon} with dents on the base and semi-strict Gelfand--Tsetlin patterns \cite{GT}. The (dented) semi-hexagon $S_{a,b}(s_1,s_2,\dots,s_b)$ is  a trapezoidal region of side-lengths $a,b,a+b,b$ with  $b$ removed up-pointing unit triangles at the positions $s_1,s_2,\dots,s_b$ on the base, as they appear from left to right. These removed unit triangles are usually called the `\emph{dents}' of the region. See Figure \ref{Fig:3polar} (b)  and (e) for an example of a semi-hexagon and  a lozenge tiling of its; the black triangles indicate the unit triangles removed.
The lozenge tilings of the semi-hexagon $S_{a,b}(s_1,s_2,\dots,s_b)$ are also in bijection with the column-strict plane partitions (or, reverse semi-standard Young tableaux) with shape $(s_b-b,s_{b-1}-b+1,\dots,s_2-2,s_1-1)$. In particular, we have the following tiling formula:
\begin{equation}\label{CLPeq}
\M(S_{a,b}(s_1,s_2,\dots,s_b))=\prod_{1\leq i <j \leq a+b}\frac{s_{j}-s_{i}}{j-i}.
\end{equation}

R. Proctor  \cite[Corollary 4.1]{Proc} enumerated a certain class of staircase plane partitions that, in turn, are in bijection with the lozenge tilings of a quasi-regular hexagon with a maximal staircase cut off $P_{a,b,c}$ ($c\leq b$). We often called this  region  a `\emph{halved hexagon}.' See Figure \ref{Fig:3polar} (c)  for a halved hexagon (it is easy to see that $t=b-c$ in the picture) and Figure \ref{Fig:3polar}(f) for  a lozenge tiling of the halved hexagon. We have
\begin{equation}\label{Proctoreq}
\M(P_{a,b,c})=\prod_{i=1}^{a}\left[\prod_{j=1}^{b-c+1}\frac{a+i+j-1}{i+j-1}\prod_{j=b-c+2}^{b-a+i}\frac{2a+i+j-1}{i+j-1}\right],
\end{equation}
 where empty products are taken to be 1. It is worth noticing that when $b=c$, Proctor's formula gives the enumeration of the transpose-complementary plane partitions, one of the ten symmetry classes of plane partitions \cite{Stanley2}.

The above three tiling enumerations are three of the most popular results in the field of enumeration tilings. They have inspired many other results by various authors. It motivates us to find a universal generalization of the three regions: the quasi-regular hexagons, the semi-hexagons, and the halved hexagons. In this paper, we provide such a generalization and prove an exact tiling enumeration for it.

We consider a quasi-regular hexagon with side-lengths $x,$ $(l-1)k+t,$ $l,$ $x,$ $(l-1)k+t,$ $l$, then cut off a maximal \emph{$k$-staircase} whose $l$ steps have width $k$. When $k=1$, we have exactly a halved hexagon. When $k=0$, there is nothing cut off, the region is still a quasi-regular hexagon. When $k\geq 2$, we have new regions similar to the halved hexagons; however, the cut is tilted. We call the new regions \emph{$k$-halved hexagons} or \emph{tilted halved hexagons}. See Figure \ref{Fig:Tiltinghex} for several examples of the $k$-halved hexagons.

\begin{figure}\centering
\includegraphics[width=10cm]{Tiltinghex.eps}
\caption{The $k$-halved hexagons with no dents.}\label{Fig:Tiltinghex}
\end{figure}

We consider a more general situation when we allow some `dents' to appear on the staircase cut. We now start with a quasi-regular hexagon of side-lengths $x,$ $h(k+1)+(l-1)k+t,$ $l,$ $x,$ $h(k+1)+(l-1)k+t,$ $l$. We cut off a maximal $k$-staircase with $h+l$ steps. Label the staircase levels from the bottom to the top by $1,2,\dots,l+h$, for some non-negative integers $h,l$. We allow removing $h$ up-pointing unit triangles at certain corners of the staircase. Assume that the remaining steps have labels $a_1,a_2,\dots,a_l$ as they appear from bottom to the top. Denote by $H_{x,t,h}(a_1,a_2,\dots,a_l)$ the resulting region (see Figure \ref{Fig:Tiltinghalvehex2} for examples; the black triangles indicate the unit triangles removed). We still call this region a $k$-halved hexagon. When $k=t=x=0$, we get precisely the dented semi-hexagon in Cohn--Larsen--Propp's formula. It is worth noticing that Ciucu has investigated the dented halved hexagon (i.e., the case $k=1$) in \cite{Ciucu2}. However, as the author's knowledge, the cases when $k\geq 2$ have not been considered in the literature. The main theorem of this paper provides an exact tiling formula for the region $H_{x,t,h}(a_1,a_2,\dots,a_l)$.

\begin{figure}\centering
\setlength{\unitlength}{3947sp}

\begingroup\makeatletter\ifx\SetFigFont\undefined
\gdef\SetFigFont#1#2#3#4#5{
  \reset@font\fontsize{#1}{#2pt}
  \fontfamily{#3}\fontseries{#4}\fontshape{#5}
  \selectfont}
\fi\endgroup
\resizebox{!}{18cm}{
\begin{picture}(0,0)
\includegraphics{Tiltinghalvehex2.eps}
\end{picture}

\begin{picture}(12527,15695)(1225,-15144)

\put(1284,-4179){\makebox(0,0)[lb]{\smash{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_1$}
}}}}

\put(1276,-3466){\makebox(0,0)[lb]{\smash{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_2$}
}}}}

\put(1284,-2041){\makebox(0,0)[lb]{\smash{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_3$}
}}}}

\put(1291,-631){\makebox(0,0)[lb]{\smash{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_4$}
}}}}

\put(7636,-4749){\makebox(0,0)[lb]{\smash{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_1$}
}}}}

\put(2875,-13293){\makebox(0,0)[lb]{\smash{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_1$}
}}}}

\put(8444,-11321){\makebox(0,0)[lb]{\smash{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_1$}
}}}}

\put(7216,-2627){\makebox(0,0)[lb]{\smash{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_2$}
}}}}

\put(9067,-10263){\makebox(0,0)[lb]{\smash{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_2$}
}}}}

\put(1653,-9056){\makebox(0,0)[lb]{\smash{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_2$}
}}}}

\put(9464,-9558){\makebox(0,0)[lb]{\smash{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_3$}
}}}}

\put(6804,-489){\makebox(0,0)[lb]{\smash{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_3$}
}}}}

\put(1240,-7601){\makebox(0,0)[lb]{\smash{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_3$}
}}}}
\end{picture}}
\caption{The $k$-halved hexagons with dents on the staircase cut.}\label{Fig:Tiltinghalvehex2}
\end{figure}

We use the Pochhammer symbol $(x)_n$ in our formula
\begin{equation}\label{poch}
(x)_n:=
\begin{cases}
x(x+1)(x+2)\dotsc(x+n-1) &\text{if $n>0$;}\\
1 &\text{if $n=0$;}\\
\frac{1}{(x-1)(x-2)(x-3)\dotsc(x+n)} &\text{if $n<0$.}
\end{cases}
\end{equation}

We also use the following function:
\begin{align}\label{phieq}
\Phi_{k}((a_i)_{i=1}^{l}; t,x,h)&=\prod_{i=1}^{l}\frac{(x+h+l+1-a_i)_{t+(k+1)a_i-l-k}}{(h+l+1-a_i)_{t+(k+1)a_i-l-k}}\notag\\
&\times \prod_{j=1}^{k-1}\prod_{i=1}^{\lfloor \frac{l+k-j}{k+1}\rfloor}\frac{((k+1)(x+h)+t+k(k+1)i+(j-1)k-(k+1)(k-1))_{j}}{((k+1)h+t+k(k+1)i+(j-1)k-(k+1)(k-1))_{j}}\notag\\
&\times \prod_{i=1}^{\lfloor \frac{l}{k+1}\rfloor}\frac{((k+1)(x+h)+t+k(k+1)i-k+1)_{(k+1)l+k-(k+1)^2i}}{((k+1)h+t+k(k+1)i-k+1)_{(k+1)l+k-(k+1)^2i}},
\end{align}
where empty products are taken to be 1. By definition, we have  $\Phi_{k}((a_i)_{i=1}^{l}; t,0,h)=1$.

We are now ready to state our main theorem:
\begin{thm}\label{mainthm} For non-negative integers $x,t,h,l$ and a sequence  $\textbf{a}=(a_i)_{i=1}^{l}$ of positive integers between $1$ and $h+l$ , we have
\begin{align}\label{maineq}
\M(H_{x,t,h}(a_1,a_2,\dots,a_l))=\Phi_{k}((a_j)_{j=1}^{l}; t,x,h)\prod_{i=1}^{l}\Phi_{k}((a_j)_{j=1}^{i}; t,a_{i+1}-a_{i}-1,a_{i+1}-i-1),
\end{align}
where $a_{l+1}=l+h+1$ by convention.
\end{thm}

\begin{figure}\centering
\includegraphics[width=8cm]{lozengeorientation.eps}
\caption{Three orientations of the lozenges.}\label{Fig:orientation}
\end{figure}

\begin{figure}\centering
\setlength{\unitlength}{3947sp}

\begingroup\makeatletter\ifx\SetFigFont\undefined
\gdef\SetFigFont#1#2#3#4#5{
  \reset@font\fontsize{#1}{#2pt}
  \fontfamily{#3}\fontseries{#4}\fontshape{#5}
  \selectfont}
\fi\endgroup
\resizebox{!}{9cm}{
\begin{picture}(0,0)
\includegraphics{Tiltinghalfhex5.eps}
\end{picture}

\begin{picture}(14990,9188)(571,-14414)

\put(3172,-8787){\makebox(0,0)[lb]{\smash{{\SetFigFont{14}{16.8}{\rmdefault}{\bfdefault}{\updefault}{\color[rgb]{0,0,0}$a_1=1$}
}}}}

\put(4297,-8374){\makebox(0,0)[lb]{\smash{{\SetFigFont{14}{16.8}{\rmdefault}{\bfdefault}{\updefault}{\color[rgb]{0,0,0}$a_2=2$}
}}}}

\put(5218,-8137){\makebox(0,0)[lb]{\smash{{\SetFigFont{14}{16.8}{\rmdefault}{\bfdefault}{\updefault}{\color[rgb]{0,0,0}$a_3=3$}
}}}}

\put(6343,-7665){\makebox(0,0)[lb]{\smash{{\SetFigFont{14}{16.8}{\rmdefault}{\bfdefault}{\updefault}{\color[rgb]{0,0,0}$a_4=4$}
}}}}

\put(3683,-13807){\makebox(0,0)[lb]{\smash{{\SetFigFont{14}{16.8}{\rmdefault}{\bfdefault}{\updefault}{\color[rgb]{0,0,0}$a_1=1$}
}}}}

\put(5831,-13157){\makebox(0,0)[lb]{\smash{{\SetFigFont{14}{16.8}{\rmdefault}{\bfdefault}{\updefault}{\color[rgb]{0,0,0}$a_2=3$}
}}}}

\put(6854,-12862){\makebox(0,0)[lb]{\smash{{\SetFigFont{14}{16.8}{\rmdefault}{\bfdefault}{\updefault}{\color[rgb]{0,0,0}$a_3=4$}
}}}}

\put(8900,-12094){\makebox(0,0)[lb]{\smash{{\SetFigFont{14}{16.8}{\rmdefault}{\bfdefault}{\updefault}{\color[rgb]{0,0,0}$a_4=6$}
}}}}
\end{picture}}
\caption{The bijection between tilings and partitions in the proof of Corollary \ref{cor1}.}\label{Fig:Tiltinghalfhex5}
\end{figure}

\begin{figure}\centering
\includegraphics[width=10cm]{Tiltinghalfhex4.eps}
\caption{The bijection between tilings and partitions in the proof of Corollary \ref{cor2}. The upper plane partition has two rows of length $0$, while the lower partition has one row of length $0$. }\label{Fig:Tiltinghalfhex4}
\end{figure}

In the sake of clarity, we classify the lozenges into three types based on their orientations, as in Figure \ref{Fig:orientation}. In particular, each lozenge tiling may have one of three orientations: \emph{left}, \emph{right}, and \emph{vertical}.

Similarly to the case of MacMahon's, Cohn--Larsen--Propp's, and Proctor's formulas above, our main theorem also implies new enumerative results of certain classes of plane partitions.

\begin{cor}\label{cor1}Assume that $x,t,h,l$ are non-negative integers and  $\textbf{a}=(a_i)_{i=1}^{l}$ is a sequence of positive integers between $1$ and $h+l$.
Then the number of plane partitions of shape $(t+(k+1)a_l-k-l, t+(k+1)a_{l-1}-k-(l-1),\dots,t+(k+1)a_2-k-2,t+(k+1)a_1-k-1)$, whose parts in the $i$-th row are at least $a_{l-i+1}-l+i$ and at most $x+h$, is equal to
\[\Phi_{k}((a_j)_{j=1}^{l}; t,x,h)\prod_{i=1}^{l}\Phi_{k}((a_j)_{j=1}^{i}; t,a_{i+1}-a_{i}-1,a_{i+1}-i-1).\]
\end{cor}

\begin{proof}
We reflect the region $H_{x,t,h}(a_1,a_2,\dots,a_l)$ over the bisector of its $120^{\circ}$ lower-left angle and get a region like the ones on the left-hand side of Figure \ref{Fig:Tiltinghalfhex5}. See the upper-left picture is for the case $k=2, h=0$, and the lower-left picture for the case $k=2, h=2$. Each tiling of the resulting region can be encoded uniquely as a family of $l$ disjoint lozenge paths consisting of juxtaposing right and vertical lozenges (indicated by the ones with a dotted line in the middle). All lozenges outside these paths are left lozenges. The $i$-th path (ordered from bottom to top) starts at the position $a_i$ on the zigzag side and ends at the position $i$ on the northwest side of the region. We label a right lozenge in the $i$-th path by $i+x$, where $x$ is the number of the vertical lozenges before it as we travel along the path from right to left. For example, the first lozenge path on the upper-left picture of Figure \ref{Fig:Tiltinghalfhex5} has three right lozenges labeled by $1,2,4$, from right to left; the first lozenge path on the lower-left picture has three right lozenges labeled by $1,3,5$. It is easy to see that the $i$-th lozenge path has exactly $t+(k+1)a_i-k-i$ labeled lozenges.

Consider a partition $\lambda$ of shape $(t+(k+1)a_l-k-l, t+(k+1)a_{l-1}-k-(l-1),\dots,t+(k+1)a_2-k-2,t+(k+1)a_1-k-1)$ whose parts in the $j$-th row record the labels of along the $(l-j+1)$-th lozenge path, for $j=1,2,\dots,l$ (see the right pictures in Figure \ref{Fig:Tiltinghalfhex5}). It is easy to see that the resulting plane partition satisfies all the assumptions of the corollary. One could also verify that this mapping is reversible, so is a bijection. The corollary now follows from Theorem \ref{mainthm}.
\end{proof}

Next, we consider the a different class of plane partitions. Our plane partitions  are of shape $\lambda=(\lambda_1,\lambda_2,\dots,\lambda_h)$ (where $\lambda_1\geq \lambda_2\geq \cdots \lambda_n \geq 0$) and satisfy the following three properties:
\begin{enumerate}
\item  the parts are at most $h+k(h+l)$;
\item the $j$-th part from the right in each row is at least $kj$;
\item the different between the $j$-th and $(j+1)$-th parts in each row (if both are defined) is at least $(\lambda_{i}-\lambda_{i+1})k$.
\end{enumerate}

\begin{cor}\label{cor2}
The number of plane partitions of shape $\lambda=(\lambda_1,\lambda_2,\dots,\lambda_h)$ satisfying the properties (1), (2), (3) above
is  equal to
\[\prod_{i=1}^{l}\Phi_{k}((a_j)_{j=1}^{i}; 0,a_{i+1}-a_{i}-1,a_{i+1}-i-1),\]
where  $\{a_1<a_2<\dots<a_{l}\}$ is the complement of  the set $\{\lambda_{i}+i\}_{i=1}^{h}$, i.e.
\[\{a_1,a_2,\dots,a_l\}=\{1,2,\dots, h+l\}-\{\lambda_{i}+i\}_{i=1}^{h},\]
and where $a_{l+1}=h+l+1$ by convention.
\end{cor}

\begin{proof}
 We reflect the region $H_{0,0,h}(a_1,a_2,\dots,a_l)$ over a vertical line and rotate the resulting region $120^{\circ}$ clockwise. This way, we get a region like the ones  on the left-hand side of Figure \ref{Fig:Tiltinghalfhex4} (see the top picture for the case of $k=0$, and the bottom picture for the case $k=2$). There are $l+h$ horizontal steps on the staircase base of  the region; the positions of the steps with no dent are $a_1,a_2,\dots,a_l$ (ordered from left to right). Assume that  $\{b_1,b_2,\dots,b_h\}$ is the complement of $\{a_1,a_2,\dots,a_l\}$. Its means that $b_1,\dots,b_h$ correspond to the positions of the $h$ dents. We now can encode each tiling of the region by a family of $h$ disjoint lozenge paths consisting of juxtaposing right and vertical lozenges as in the previous corollary. The  paths start at the positions of the dents on the base and end at the northwest side of the region. More precisely, the $j$-th path starts from the $b_j$-dent and contains  exactly $b_j-j$ right lozenges, for $j=1,2,\dots,h$. Each right lozenge in the path is labeled by the number of vertical lozenges before it, as we travel along the path from right to left. For example, in the lower-left picture of Figure \ref{Fig:Tiltinghalfhex4},  the first lozenge path has no right lozenge (as $b_1-1=0$), and the second path has $2$ right lozenges (as $b_2-2=2$) labeled by $3,5$, from right to left.

Consider the plane partition of shape $\lambda=(b_h-h,b_{h-1}-(h-1),\dots,b_1-1)$, whose $j$-th row records the labels along the $(h-j+1)$-th lozenge path, for $j=1,2,\dots,h$. It is easy to see that the resulting plane partition satisfies properties (1)--(3). This way, we have just created a mapping from the lozenge tilings of the region $H_{0,0,h}(a_1,a_2,\dots,a_l)$ to these plane partitions. It is easy to see that this mapping is a bijection, and the corollary follows from Theorem \ref{mainthm} again.
\end{proof}

It is worth noticing that,  when $k=0$, the proof Corollary \ref{cor2} provides a bijection between lozenge tilings of a semi-hexagon  in Cohn--Larsen--Propp's formula and column-strict plane partitions.

\section{Proof of the main theorem}\label{Sec:Proof}

A \emph{forced lozenge} of a tile-able region $R$ is the lozenge that is contained in any tilings. The removal of forced lozenges does not change the number of tilings. A \emph{perfect matching} of a graph is a collection of disjoint edges that cover all vertices of the graph. There is a natural bijection between tilings of a region on the triangular lattice and perfect matchings of its \emph{(planar) dual graph} (the graph whose vertices are the unit triangles in the region and whose edges connect precisely two unit triangles sharing an edge). We use the notation $\M(G)$ for the number of perfect matchings of the graph $G$.

E. H. Kuo \cite{Kuo} proved the following \emph{graphical condensation}, often mentioned as `\emph{Kuo condensation}.' This is the key to our proof.

\begin{lem}[Theorem 2.1 in \cite{Kuo}]\label{Kuolem}
Let $G=(V_1,V_2,E)$ be a plane bipartite graphs in which $|V_1|=|V_2|$. Let vertices $u,$ $v,$ $w,$ and $s$ appear in a cyclic order on a face of $G$. If $u,w \in V_1$ and $v,s\in V_2$, then
\begin{align}\label{Kuoeq}
\M(G)\M(G-\{u,v,w,s\})=\M(G-\{u,v\})\M(G-\{w,s\})+\M(G-\{u,s\})\M(G-\{v,w\}).
\end{align}
\end{lem}

\begin{figure}\centering
\setlength{\unitlength}{3947sp}

\begingroup\makeatletter\ifx\SetFigFont\undefined
\gdef\SetFigFont#1#2#3#4#5{
  \reset@font\fontsize{#1}{#2pt}
  \fontfamily{#3}\fontseries{#4}\fontshape{#5}
  \selectfont}
\fi\endgroup
\resizebox{!}{7cm}{
\begin{picture}(0,0)
\includegraphics{Tiltinghalfhex6.eps}
\end{picture}

\begin{picture}(10394,7550)(1623,-7582)

\put(1644,-3264){\makebox(0,0)[lb]{\smash{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_3$}
}}}}

\put(7546,-4299){\makebox(0,0)[lb]{\smash{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_1$}
}}}}

\put(7448,-3214){\makebox(0,0)[lb]{\smash{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_2$}
}}}}

\put(7036,-1076){\makebox(0,0)[lb]{\smash{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_3$}
}}}}

\put(2026,-5342){\makebox(0,0)[lb]{\smash{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_1$}
}}}}

\put(1801,-4299){\makebox(0,0)[lb]{\smash{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_2$}
}}}}
\end{picture}}
\caption{Obtaining a smaller region by removing forced lozenges in the cases (a) $a_l<l+h$ and (b) $a_1>1$.}\label{Fig:Tiltinghalfhex6}
\end{figure}

\begin{figure}\centering
\setlength{\unitlength}{3947sp}

\begingroup\makeatletter\ifx\SetFigFont\undefined
\gdef\SetFigFont#1#2#3#4#5{
  \reset@font\fontsize{#1}{#2pt}
  \fontfamily{#3}\fontseries{#4}\fontshape{#5}
  \selectfont}
\fi\endgroup
\resizebox{!}{15cm}{
\begin{picture}(0,0)
\includegraphics{Tiltinghalfhex7b.eps}
\end{picture}

\begin{picture}(9329,14051)(814,-14028)

\put(5978,-8511){\makebox(0,0)[lb]{\smash{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_4$}
}}}}

\put(5957,-4737){\makebox(0,0)[lb]{\smash{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_1$}
}}}}

\put(5537,-2615){\makebox(0,0)[lb]{\smash{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_2$}
}}}}

\put(5125,-477){\makebox(0,0)[lb]{\smash{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_3$}
}}}}

\put(1647,-4832){\makebox(0,0)[lb]{\smash{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_1$}
}}}}

\put(1340,-3828){\makebox(0,0)[lb]{\smash{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_2$}
}}}}

\put(1136,-2765){\makebox(0,0)[lb]{\smash{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_3$}
}}}}

\put(931,-1702){\makebox(0,0)[lb]{\smash{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_4$}
}}}}

\put(829,-580){\makebox(0,0)[lb]{\smash{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_5$}
}}}}

\put(6748,-12651){\makebox(0,0)[lb]{\smash{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_1$}
}}}}

\put(6489,-11641){\makebox(0,0)[lb]{\smash{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_2$}
}}}}

\put(6285,-10578){\makebox(0,0)[lb]{\smash{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_3$}
}}}}
\end{picture}}
\caption{Several special cases of the region $H_{x,t,h}(a_1,a_2,\dots,a_l)$.}\label{Fig:Tiltinghalfhex7}
\end{figure}

\begin{figure}\centering
\setlength{\unitlength}{3947sp}

\begingroup\makeatletter\ifx\SetFigFont\undefined
\gdef\SetFigFont#1#2#3#4#5{
  \reset@font\fontsize{#1}{#2pt}
  \fontfamily{#3}\fontseries{#4}\fontshape{#5}
  \selectfont}
\fi\endgroup

\resizebox{!}{22cm}{
\begin{picture}(0,0)
\includegraphics{Tiltinghalfhex8.eps}
\end{picture}

\begin{picture}(10375,23895)(1216,-23150)

\put(1996,-4621){\makebox(0,0)[lb]{\smash{{\SetFigFont{14}{16.8}{\familydefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_1$}
}}}}

\put(1441,-1449){\makebox(0,0)[lb]{\smash{{\SetFigFont{14}{16.8}{\familydefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_2$}
}}}}

\put(1231,-369){\makebox(0,0)[lb]{\smash{{\SetFigFont{14}{16.8}{\familydefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_3$}
}}}}

\put(6943,-4611){\makebox(0,0)[lb]{\smash{{\SetFigFont{14}{16.8}{\familydefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_1$}
}}}}

\put(2218,-12523){\makebox(0,0)[lb]{\smash{{\SetFigFont{14}{16.8}{\familydefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_1$}
}}}}

\put(7153,-12493){\makebox(0,0)[lb]{\smash{{\SetFigFont{14}{16.8}{\familydefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_1$}
}}}}

\put(2398,-20916){\makebox(0,0)[lb]{\smash{{\SetFigFont{14}{16.8}{\familydefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_1$}
}}}}

\put(7310,-20923){\makebox(0,0)[lb]{\smash{{\SetFigFont{14}{16.8}{\familydefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_1$}
}}}}

\put(6350,-1416){\makebox(0,0)[lb]{\smash{{\SetFigFont{14}{16.8}{\familydefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_2$}
}}}}

\put(1625,-9343){\makebox(0,0)[lb]{\smash{{\SetFigFont{14}{16.8}{\familydefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_2$}
}}}}

\put(6523,-9358){\makebox(0,0)[lb]{\smash{{\SetFigFont{14}{16.8}{\familydefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_2$}
}}}}

\put(1835,-17743){\makebox(0,0)[lb]{\smash{{\SetFigFont{14}{16.8}{\familydefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_2$}
}}}}

\put(6748,-17728){\makebox(0,0)[lb]{\smash{{\SetFigFont{14}{16.8}{\familydefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_2$}
}}}}

\put(6140,-366){\makebox(0,0)[lb]{\smash{{\SetFigFont{14}{16.8}{\familydefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_3$}
}}}}

\put(1423,-8271){\makebox(0,0)[lb]{\smash{{\SetFigFont{14}{16.8}{\familydefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_3$}
}}}}

\put(6328,-8263){\makebox(0,0)[lb]{\smash{{\SetFigFont{14}{16.8}{\familydefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_3$}
}}}}

\put(6552,-16659){\makebox(0,0)[lb]{\smash{{\SetFigFont{14}{16.8}{\familydefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_3$}
}}}}

\put(1622,-16659){\makebox(0,0)[lb]{\smash{{\SetFigFont{14}{16.8}{\familydefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_3$}
}}}}
\end{picture}}
\caption{Using Kuo condensation to obtain a recurrence for tiling numbers of the $H$-type regions.}\label{Fig:Tiltinghalfhex8}
\end{figure}

We are now ready to prove our main theorem.

\begin{proof}[Proof of Theorem \ref{mainthm}]
Fix some nonnegative integer $k$. We prove identity (\ref{maineq}) by induction on the statistic $p:=x+t+l+(k+2)h$ of the region $H_{x,t,h}(a_1,a_2,\dots,a_l)$. In the rest of this proof, we say that an $H$-type region $A$ is ``smaller" than an $H$-type region $B$ if the $p$-statistic of $A$ is smaller than the $p$-statistic of $B$.

The base case is the case when $l =0$. If $l=0$, identity  (\ref{maineq}) becomes ``$1=1$," as our region has exactly one tiling (see Figure \ref{Fig:Tiltinghalfhex7}(c)), and the expression on the right-hand side of (\ref{maineq}) is precisely $1$.

For induction step, we assume that $l>0$ and that identity  (\ref{maineq}) holds for any $H$-type region with $p$-statistic strictly smaller than $x+t+l+(k+2)h$.

We can assume that $a_1=1$ and $a_{l}=h+l$. Indeed, if $a_l<h+l$, then we can remove forced lozenges in the $(k+1)(l+h-a_{l})$ top rows of the region $H_{x,t,h}(a_1,a_2,\dots,a_l)$ to get a smaller $H$-type region, namely $H_{x+l+h-a_{l}, t, a_{l}-l}(a_1,a_2,\dots,a_l)$   (see the region restricted by the bold contour in Figure \ref{Fig:Tiltinghalfhex6}(a)).  If $a_1>1$, we can also get a smaller $H$-type region as in Figure \ref{Fig:Tiltinghalfhex6}(b). The new region is precisely $H_{x, t+(k+1)(a_1-1), h+1-a_1}(1,a_2-a_1+1,a_3-a_1+1,\dots,a_l-a_1+1)$. Then  (\ref{maineq}) holds by the induction hypothesis, when $a_l<l+h$ or $a_1>1$.

Next, if $x=h=0$, then our identity  (\ref{maineq}) becomes ``$1=1$." Our region has only one tiling (see Figure \ref{Fig:Tiltinghalfhex7}(a)), and our tiling formula is simply to $1$.  If $x=0$ and $h>0$, we obtain a smaller region by removing forced lozenges as in Figure \ref{Fig:Tiltinghalfhex7}(b). If $t=0$ (we are assuming that $a_1=1$), then we can also remove forced lozenges along the base to get a smaller region (see Figure \ref{Fig:Tiltinghalfhex7}(d)). It means that (\ref{maineq}) holds in the situations when at least one of $x$ and $t$ is equal to $0$.

\medskip

In the rest of the proof, we assume that  $x,l,t>0,$  and that $a_1=1,a_{l}=h+l$.

We now apply Kuo's Lemma \ref{Kuolem} to the dual graph $G$ of the region $H=H_{x,t,h}(a_1,a_2,\dots,a_l)$ with the four vertices $u,v,w,s$ chosen as in Figure \ref{Fig:Tiltinghalfhex8}(b) (the four vertices are  indicated by the corresponding unit triangles of the same label in $H$). More precisely,  the $u$- and $v$-triangles are the shaded unit triangles at the upper-right corner of the region, and the $w$- and $s$-triangles are the shaded unit triangles at lower-right corner. We get the recurrence
\begin{align}\label{Grecurrence}
\M(G)\M(G-\{u,v,w,s\})=\M(G-\{u,v\})\M(G-\{w,s\})+\M(G-\{u,s\})\M(G-\{v,w\}).
\end{align}

Next, we will convert recurrence (\ref{Grecurrence}) into a recurrence for the tiling numbers of $H$-type regions. To do so, we will write each matching number in (\ref{Grecurrence}) as the tiling number of some $H$-type region. The task for the first matching number is obvious. By definition, we have:
\begin{equation}\label{eq1}
\M(G)=\M(H_{x,t,h}(a_1,a_2,\dots,a_l)).
\end{equation}

Let us consider the second matching number, i.e., $\M(G-\{u,v,w,s\})$. We consider the region  corresponding to the graph $G-\{u,v,w,s\}$ as shown in Figure \ref{Fig:Tiltinghalfhex8}(b). The removal of the $u$-, $v$-, $w$-, and $s$-triangles yields  some forced lozenges on the top, the northeast, the southeast, and the base of the region. By removing these forced lozenges, we get a new $H$-type region, namely $H_{x,t-1,h}(a_1,\dots,a_{l-1})$ (see the region restricted by the bold contour). As the removal of forced lozenges does not  change the tiling number, we get
\begin{equation}\label{eq2}
\M(G-\{u,v,w,s\})=\M(H_{x,t-1,h}(a_1,\dots,a_{l-1})).
\end{equation}
By considering forced lozenges, as in Figures \ref{Fig:Tiltinghalfhex8}(c)--(f), we get respectively the following identities:
\begin{equation}\label{eq3}
\M(G-\{u,v\})=\M(H_{x,t,h}(a_1,\dots,a_{l-1})),
\end{equation}
\begin{equation}\label{eq4}
\M(G-\{w,s\})=\M(H_{x,t-1,h}(a_1,\dots,a_{l})),
\end{equation}
\begin{equation}\label{eq5}
\M(G-\{u,s\})=\M(H_{x+1,t-1,h}(a_1,\dots,a_{l-1})),
\end{equation}
\begin{equation}\label{eq6}
\M(G-\{v,w\})=\M(H_{x-1,t,h}(a_1,\dots,a_{l})).
\end{equation}

By (\ref{eq1})--(\ref{eq6}), we can convert recurrence (\ref{Grecurrence}) into the following recurrence:
\begin{align}
\M(H_{x,t,h}(a_1,\dots,a_{l}))\M(H_{x,t-1,h}(a_1,\dots,a_{l-1}))&=\M(H_{x,t,h}(a_1,\dots,a_{l-1}))\M(H_{x,t-1,h}(a_1,\dots,a_{l}))\notag\\
&+\M(H_{x+1,t-1,h}(a_1,\dots,a_{l-1}))\M(H_{x-1,t,h}(a_1,\dots,a_{l})).
\end{align}

Our remaining  job is to show that the tiling formula on the right-hand side of (\ref{maineq}) also satisfies this recurrence. Then the theorem follows from the induction principle. In particular, if we denote by $f_{x,t,h}(a_1,\dots,a_{l-1})$ this tiling formula, we need to verify that
\begin{align}\label{Feq1}
f_{x,t,h}(a_1,\dots,a_{l})f_{x,t-1,h}(a_1,\dots,a_{l-1})&=f_{x,t,h}(a_1,\dots,a_{l-1})f_{x,t-1,h}(a_1,\dots,a_{l})\notag\\
&+f_{x+1,t-1,h}(a_1,\dots,a_{l-1})f_{x-1,t,h}(a_1,\dots,a_{l}).
\end{align}
Equivalently
\begin{align}\label{Feq2}
\frac{f_{x,t,h}(a_1,\dots,a_{l-1})}{f_{x,t,h}(a_1,\dots,a_{l})}\cdot \frac{f_{x,t-1,h}(a_1,\dots,a_{l})}{f_{x,t-1,h}(a_1,\dots,a_{l-1})}+\frac{f_{x+1,t-1,h}(a_1,\dots,a_{l-1})}{f_{x,t-1,h}(a_1,\dots,a_{l-1})}\frac{f_{x-1,t,h}(a_1,\dots,a_{l})}{f_{x,t,h}(a_1,\dots,a_{l})}=1.
\end{align}
Consider the first term on the left-hand side of (\ref{Feq2}). All the $\Phi$-factors in this term cancel out, except for the ones involving $x$:
\begin{align}\label{Feq3}
\frac{f_{x,t,h}(a_1,\dots,a_{l-1})}{f_{x,t,h}(a_1,\dots,a_{l})}\cdot \frac{f_{x,t-1,h}(a_1,\dots,a_{l})}{f_{x,t-1,h}(a_1,\dots,a_{l-1})}=\frac{\Phi_{k}((a_j)_{j=1}^{l-1}; t,x,h)\Phi_{k}((a_j)_{j=1}^{l}; t-1,x,h)}{\Phi_{k}((a_j)_{j=1}^{l-1}; t-1,x,h)\Phi_{k}((a_j)_{j=1}^{l}; t,x,h)}.
\end{align}
 By definition of the $\Phi$-function, one could simplify the right-hand side of (\ref{Feq3}) to
\begin{align}
\frac{\Big((k+1)(l+h-1)+t\Big)\Big((k+1)(x+h+l-1)+t)\Big)}{\Big((k+1)(x+l+h-1)+t\Big)\Big(x+t+k(l-1)+(k+1)h\Big)}.
\end{align}
It means that the first term on left-hand side of  (\ref{Feq2}) reduces to
\begin{align}\label{Feq4}
\frac{f_{x,t,h}(a_1,\dots,a_{l-1})}{f_{x,t,h}(a_1,\dots,a_{l})}\cdot \frac{f_{x,t-1,h}(a_1,\dots,a_{l})}{f_{x,t-1,h}(a_1,\dots,a_{l-1})}=\frac{\Big((k+1)(l+h-1)+t\Big)\Big((k+1)(x+h+l-1)+t)\Big)}{\Big((k+1)(x+l+h-1)+t\Big)\Big(x+t+k(l-1)+(k+1)h\Big)}.
\end{align}

Similarly, one could simply the the second term on left-hand side of (\ref{Feq2}) as
\begin{align}\label{Feq5}
\frac{f_{x+1,t-1,h}(a_1,\dots,a_{l-1})}{f_{x,t-1,h}(a_1,\dots,a_{l-1})}\frac{f_{x-1,t,h}(a_1,\dots,a_{l})}{f_{x,t,h}(a_1,\dots,a_{l})}&=\frac{\Phi_{k}((a_j)_{j=1}^{l-1}; t-1,x+1,h)\Phi_{k}((a_j)_{j=1}^{l}; t,x-1,h)}{\Phi_{k}((a_j)_{j=1}^{l-1}; t-1,x,h)\Phi_{k}((a_j)_{j=1}^{l}; t,x,h)}\\
&=\frac{x\Big((k+1)x+(k+1)h+t\Big)}{\Big((k+1)(x+l+h-1)+t\Big)\Big(x+t+k(l-1)+(k+1)h\Big)}.
\end{align}
The identity  (\ref{Feq2}) now becomes
\begin{align}
&\frac{\Big((k+1)(l+h-1)+t\Big)\Big((k+1)(x+h+l-1)+t)\Big)}{\Big((k+1)(x+l+h-1)+t\Big)\Big(x+t+k(l-1)+(k+1)h\Big)}\notag\\
&\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad+\frac{x\Big((k+1)x+(k+1)h+t\Big)}{\Big((k+1)(x+l+h-1)+t\Big)\Big(x+t+k(l-1)+(k+1)h\Big)}=1,
\end{align}
which is a true identity. This finishes the proof of our theorem.
\end{proof}

\section{Several open questions}\label{Sec:Q}
We conclude this paper by a couple of open questions.

\medskip

As there exist elegant $q$-analogs of MacMahon's tiling formula (also by MacMahon \cite{Mac}), Cohn--Larsen--Propp's formula (in the language of column-strict plane partitions, see, e.g., \cite[pp. 374--375]{Stanley}), and Proctor formula (see \cite{LR20}), one should expect for a $q$-analog of our main theorem, at least for the case with no dents.
\
\\

\textbf{Open Problem 1.} Find a $q$-analog of Theorem \ref{maineq}.
\
\\

It is well-known that the weighted enumerations of tilings of a quasi-regular hexagon and a semi-hexagon can be written as a Schur polynomial. The weighted enumeration of tilings of the halved hexagon can also be written in terms of the symplectic characters (see, e.g.,  \cite{AF}).
\
\\

\textbf{Open Question 2.}  Is there any symmetric function that counts the weighted tilings of the $k$-halved hexagons?

\bibliographystyle{plain}
\bibliography{Tiltinghex}

\end{document}

config: arxiv


TITLE: Inclusion-Exclusion Principle Math Problem
QUESTION [0 upvotes]: Suppose a school with 120 students offers yoga and karate. If the number of students taking yoga alone is twice the number taking karate (possibly, karate and yoga), if 25 more students study neither skill than study both skills, and if 75 students take at least one skill, then how many students study yoga?

REPLY [1 votes]: Let $A$ and $B$ be the set of students taking yoga and karate respectively. We have
$$|A \setminus B|=2|B|\\|(A\cup B)^c|=|A \cap B|+25\\|A\cup B|=75$$
Also, $|(A\cup B)^c|+|A\cup B|=120.$ Therefore, $|(A\cup B)^c|=120-75=45$.
Hence, $|A\cap B|=45-25=20.$
Now $$|A|=|A \setminus B|+|A\cap B|=2|B|+20$$
Also, $$75=|A\cup B|=|A\setminus B|+|B|=3|B|.$$Therefore, $|B|=25.$ It follows that $|A|=70.$


TITLE: Products in Categories of Manifolds
QUESTION [3 upvotes]: I'm curious about which (categorical) products exist in the categories of topological manifolds with continuous mappings/smooth manifolds with smooth mappings. Here is what I have so far:
Finite products exist in both categories and are given by the cartesian product of the underlying sets equipped with the product topology. Products of Hausdorff spaces are Hausdorff, at most countable products of second-countable spaces are second-countable and charts on the product are given by products of charts on the factors. In the smooth case, the products of charts from the respective $C^{\infty}$-atlases form again a $C^{\infty}$-atlas.
Lemma: If $M,N$ are top. manifolds of dimension $m,n$ respectively and $m>n$, there is no continuous injection $M\rightarrow N$.
Proof: Assume $f\colon M\rightarrow N$ is a continuous injection. Pick $p\in M$ and pick a chart $\psi\colon V\rightarrow\psi(V)$ of $N$ about $f(p)$. Then $f^{-1}(V)$ is open, hence contains a chart domain $U$ about $p$ with corresponding chart $\varphi\colon U\rightarrow\varphi(U)$ of $M$. Then $\psi\circ f\circ\varphi^{-1}$ is a continuous injection from $\varphi(U)$ into $\psi(V)$, but after post-composing with the inclusion $\psi(V)\subseteq\mathbb{R}^n\subseteq\mathbb{R}^m$, invariance of domain implies that $\psi(V)\times\{0\}^{m-n}$ is open in $\mathbb{R}^m$, which is a contradiction.
Next, I claim that if $(M_i)_{i\in I}$ is an infinite collection of manifolds, infinitely many of which have positive dimension (and none of which are empty), then their product doesn't exist. Suppose, to the contrary, that $(P,(\pi_i)_{i\in I})$ is their product. Let $J\subseteq I$ be a finite subset and consider the product (which exists by the preceding paragraph) $(\prod_{j\in J}M_j,(p_j\colon\prod_{j\in J}M_j\rightarrow M_j)_{j\in J})$. Pick arbitrary morphisms $p_i\colon\prod_{j\in J}M_j\rightarrow M_i$ for all $i\in I\setminus J$ (constant ones do the job in either category, since $M_i$ is non-empty). Together, these factor as a morphism $f\colon\prod_{j\in J}M_j\rightarrow P$ satisfying $\pi_j\circ f=p_j$ for all $j\in J$. Consider an arbitrary object $C$ and morphisms $r,s\colon C\rightarrow\prod_{j\in J}M_j$ such that $f\circ r=f\circ s$. Then, for every $j\in J$, $p_j\circ r=\pi_j\circ f\circ r=\pi_j\circ f\circ s=p_j\circ s$, so, by a property of products, $r=s$. That is, $f$ is a monomorphisms, hence injective (for the same reason as in $\mathbf{Set}$, since singletons are manifolds). The Lemma now implies $\sum_{j\in J}\dim(M_j)=\dim(\prod_{j\in J}M_j)\le\dim(P)$ for all finite subsets $J\subseteq I$, but since there are infinitely many $M_i,i\in I$ with positive dimension, this is impossible.
On the other hand, if $(M_i)_{i\in I}$ is an infinite collection of manifolds and all but finitely many of the $M_i,i\in I$ are singletons, I claim their product exists. More precisely, if $M_{i_1},...,M_{i_n}$ are the finitely many non-singletons among the $M_i,i\in I$, I claim the product is given by $\prod_{j=1}^nM_{i_j}$ with the usual projections $p_j\colon\prod_{j=1}^nM_{i_j}\rightarrow M_{i_j}$ for $j=1,...,n$ and the unique maps $\prod_{j=1}^nM_{i_j}\rightarrow M_i$ for $i\in I\setminus \{i_1,...,i_n\}$. This is essentially obvious, because singletons are terminal in either category.
Question: First of all, is all of the above correct? Second of all, what can we say about the existence of a product for an infinite family of manifolds, only finitely many of which have positive dimension and infinitely many of which are not singletons, in either category?
Edit: I had forgotten and just recalled that we usually do consider the empty set a manifold. The empty set is initial in either category. If a collection $(M_i)_{i\in I}$ contains the empty manifold, its product exists and is given by the empty set with the only possible maps for the obvious reasons. My above argument for non-existence fails in case one of the $M_i,i\in I$ is empty at the stage of picking an arbitrary morphism into $M_i$.
Edit 2: Here is an argument for the remaining case: Let $(M_i)_{i\in I}$ be a collection of manifolds, none of which are empty, only finitely many of which have positive dimension and for which not all but finitely many of them are singletons. Assume the product $(P,(\pi_i)_{i\in I})$ of the family exists in $\mathcal{C}$ and let $(\prod_{i\in I}M_i,(p_i)_{i\in I})$ be their cartesian product with the corresponding projections, i.e. their product in $\mathbf{Set}$. By the universl property, there exists a map $f\colon P\rightarrow\prod_{i\in I}M_i$, such that $p_i\circ f=\pi_i$ for all $i\in I$. Let $x,y\in P$ such that $f(x)=f(y)$. Let $\overline{x},\overline{y}\colon\{\ast\}\rightarrow P$ be the morphisms in $\mathcal{C}$ mapping $\ast$ to $x,y$ respectively. Then $f\circ\overline{x}=f\circ\overline{y}$, hence $\pi_i\circ\overline{x}=p_i\circ f\circ\overline{x}=p_i\circ f\circ\overline{y}=\pi_i\circ\overline{y}$ for all $i\in I$, hence $\overline{x}=\overline{y}$ and thus $x=y$, i.e. $f$ is injective. Let $(x_i)_{i\in I}\in\prod_{i\in I}M_i$. For each $i\in I$, let $\overline{x_i}\colon\{\ast\}\rightarrow M_i$ be the morphism in $\mathcal{C}$ mapping $\ast$ to $x_i$. By the universal property, this factors as a map $\varphi\colon\{\ast\}\rightarrow P$, which satisfies $p_i\circ f\circ\varphi=\pi_i\circ\varphi=\overline{x_i}$ for all $i\in I$, i.e. $f(\varphi(\ast))=(x_i)_{i\in I}$, thus $f$ is surjective. So, by transport of structure, we may WLOG assume that $P=\prod_{i\in I}M_i$ (as sets).
The continuity of the maps $\pi_i\colon\prod_{i\in I}M_i\rightarrow M_i$ immediately forces the topology on $P$ to be at least as fine as the product topology. The hypotheses imply that infinitely many ofthe $M_i,i\in I$ are discrete and non-trivial, hence the product topology on $\prod_{i\in I}M_i$ has uncountably many connected components. But the number of connected components behaves monotonically with respect to fineness of topologies, so that $P$ also has uncountably many connected components, contradicting secound-countability.

REPLY [4 votes]: What you wrote seems correct.
Your second question is then about products where you have infinitely many discrete manifolds, and only a finite number of positive dimension manifolds.
Since products are associative, and you know the product of a finite number of manifolds exists, you are reduced to the product of discrete manifolds.
Of course, since the point is a manifold, if you have such a product, then its underlying set will be the usual cartesian product of the sets.
Therefore if infinitely many of them aren't singletons, then your product is necessarily uncountable. I will prove that it's discrete, which will be a contradiction with second countability.
Indeed, let $M$ be a manifold. Then if $M$ has positive dimension, it receives a non constant smooth/continuous map $\mathbb R\to M$. But of course, in the case of a product of discrete manifolds, any map $\mathbb R\to \prod_i X_i$ must be constant, since its projection on any $X_i$ is constant.
It follows that $\prod_i X_i$ must have dimension $0$ and be uncountable: absurd.
EDIT : Here's how to conclude for the general case where you have infinitely many discrete manifolds with more than one point and finitely many positive dimensional manifolds; let's call the positive dimensional ones $M_1,...,M_n$ and $(X_i)$ the other ones. Let's call $P$ a product of these. Recall that the underlying set of $P$ is the usual product $M_1\times ... \times M_n \times \prod_i X_i$. Now fix $m\in M_1\times...\times M_n$, and consider $(x_i)\in \prod_i X_i$ (here I'm talking about the cartesian products of sets)
Then, any map $\mathbb R\to P$ which hits $(m,(x_i))$ must have its $X_i$-coordinates $x_i$, because the projection $P\to X_i$ is continuous, and the latter is discrete. In other words, if $(x_i)\neq (y_i)$, $(m,(x_i))$ and $(m,(y_i))$ are in different connected components of $P$. In particular, $P$ has at least $|\prod_i X_i|$ connected components, which is too much for a manifold.


TITLE: A diophantine equation of coprime integers
QUESTION [1 upvotes]: I conjecture that for two coprime integers $a$ and $b$, for any integer $n$ coprime to $a$ and $b$ they exist integers $x$ and $y$ such that

$ax + by = n$
$a,b,x,y,n$ are pairwise coprime

I am having problems to prove it, specially with the second condition, although numerical experimentation seems to support it. Bezout's identity doesn't guarantee it, and the only cases I have been able to identify that for sure holds for any $a,b,x,y,n$ are $x=\pm 1$ and $y=\pm 1$ for $n=\pm (a\pm b)$. I believe it could be a good starting point for some kind of inductive argument, but I have not been able to make it work in a way that guarantees the second condition.
Any help or hint to prove this conjecture, or some counterexample to it, would be welcomed.
Thanks!

REPLY [1 votes]: We can assume without loss of generality that $\ n>0\ $, since if $\ a,b,x,y,n\ $ satisfy all the given conditions, then so do $\ a,$$\,b,$$\,{-}x,$$\,{-}y,$$\,{-}n\ $.
Using the extended Euclidean algorithm we can find integers $\ x_0,y_0\ $ such that
$$
x_0a+ y_0b=1\ .
$$
The integer $\ x_0\ $ must be relatively prime to $\ b\ $, and $\ y_0\ $ must be relatively prime to $\ a\ $.  From the Chinese remainder theorem, it follows that there exists an integer $\ t\ $ such that
\begin{align}
t&\equiv -b^{-1}\pmod{n}\ \ , \ \ \ \ \text{ and}\\
t&\equiv b^{-1}(nx_0-1)\pmod{a}\ .
\end{align}
Let
\begin{align}
x=&nx_0-tb - kabn\ , \ \ \text{ and}\\
y=&ny_0+at+ka^2n\
\end{align}
where $\ k $ is an integer which remains to be chosen. But whatever the value of $\ k\ $,
$$
xa+yb=n\ ,
$$
$\ x\ $ is relatively prime to $\ b\ $, and $\ y\ $ is relatively prime to $\ a\ $,
\begin{align}
x&\equiv1\pmod{n}\ ,\text{ and}\\
x&\equiv1\pmod{a}\ ,\\
y&\equiv ny_0+at\equiv -b^{-1}a \pmod{n}\ .
\end{align}and hence $\ x\ $ is relatively prime to $\ a\ $ and $\ n\ $ and $\ y\ $ is relatively prime to $\ n\ $.  Since $\ a\ $ and $\ n\ $ are relatively prime to $\ b\ $ there is an integer $\ k\ $ such that
$$
y=y_0+at+ka^2n\equiv1\pmod{b}\ .
$$
Therefore, if we choose this $\ k\ $ in the equations for $\ x\ $ and $\ y\ $ above, then $\ y\ $ will be relatively prime to $\ b\ $ and the integers $\ a,b,x,y,n\ $ will satisfy all the given conditions.


TITLE: When does a Riemaniann metric form a coercive quadratic form?
QUESTION [1 upvotes]: Let
$
A=
 \begin{pmatrix}
  g^{11} & g^{12} & \cdots & 0& 0 \\
  g^{21} & g^{22} & \cdots & 0&0 \\
  \vdots  & \vdots  & \ddots & \vdots &\vdots \\
 0 & 0 & \cdots &1 &  0\\
  0 & 0 & \cdots&0&  1
 \end{pmatrix}$\
where $g^{ij}$ are the components of the inverse of a Riemannian metric $g_{ij}$
Given $\Phi=(\phi_{1},\phi_{2}....\phi_{n},\phi)$ where $\phi_{m}=\frac{\partial\phi}{\partial x^{m}}$ is the "energy" defined as:
$$E=\int\Phi^{T}A\Phi$$
Is $E$ a coercive quadratic form (i.e.,$\int\Phi^{T}A\Phi\ge\int\mu\Phi^{T}\Phi$ for $\mu\in\mathbb{R}^{+}$ )?
If not, which are the geometrical conditions on $g_{ij}$ such that this is satisfied?
This question arises from the fact that this is a key condition in symmetric hyperbolic systems in order to prove energy inequalities. Also, I am aware that second order linear wave equations can be rewritten as first order systems.
However, it is not clear to me that this "energy" is coercive.

REPLY [2 votes]: A Riemannian metric (or its "inverse" metric) is by definition a positive definite quadratic form. In finite dimensions this immediately guarantees that the eigenvalues have a lower bound and that the form is coercive. There is nothing to prove here.


text:
\begin{document}

\maketitle

\noindent
This is the \LaTeX\ package \pkg{dblfloatfix} which solves two problems:

\renewcommand*{\theenumi}{\alph{enumi}}
\renewcommand*{\labelenumi}{\theenumi)}
\begin{enumerate}
\item floats in a \opt{twocolumn} document come out in the right order and
\item allowed float positions are now \texttt{[tbp]}.
\end{enumerate}

It may be distributed and/or modified under the
conditions of the \LaTeX\ Project Public License, either version~1.3c
of this license or (at your option) any later version.
The latest version of this license is in\\
\url{http://www.latex-project.org/lppl.txt}

\section*{Usage:}

This package redefines internals of the \LaTeX\ kernel by merging
the code of the packages \pkg{fixltx2e} (the \pkg{fix2col} part) and \pkg{stfloats}.

If either of the packages \pkg{stfloats} or \pkg{fix2col} are loaded you will
get an error message and your document will probably not be able
to compile. So don't load them!

When the new output routine for \LaTeX3 is done, this package will
be obsolete. The sooner the better\ldots

If you're using the \pkg{subfigure} package this package will provide a
fix for \cmd{\end@dblfloat} by Steven Cochran (the author of \pkg{subfigure}).

\end{document}


TITLE: Quartiles with many zeroes
QUESTION [0 upvotes]: I am trying to evaluate a data set with 194 columns where there are many zeroes for several variables.
Namely, variable a: 85 zeroes, variable b: 81 zeroes and variable c: 114 zeroes.
My question is now, WHETHER I CAN IGNORE THOSE ZEROES in the calculation of quartiles or whether it would give a more meaningful result if the zeroes were included in the calculation (even though for e.g. c that would mean more than 50 % zeroes!!!).
For example: imagine having ten values: 0,1,4,6,0,0,8,9,0,0. Including zeroes would mean that Q1 <= 0; 0 < Q2 < 0.5; 0.5 < Q3 < 6.5. Excluding zeroes would mean that Q1 <= 2.5; 2.5 < Q2 < 6 ; 6 < Q3 < 8.5. Both are possible - which is more correct?
:)
Thanks for your help!!

REPLY [3 votes]: To decide whether to ignore the zeros, you have to know what the zeros mean.
For example, maybe the zeros mean "information not available", and do not really mean that the value is zero.  For example, maybe the values are temperatures, but your table contains "0" when the temperature was not measured.  In that case it would not make sense to include them in the quartiles.
On the other hand, maybe the zero values really mean a result of zero.  For example, maybe the numbers are reporting how many times a certain thing happened, and the zeros indicate the cases where it happened zero times.  In this case you should include the zeros in your analysis.


TITLE: Physical Relation in Maxwells Equations of quantity between as well as fundamental forces
QUESTION [0 upvotes]: Recently learnt about Maxwells Equations, am wondering what is the physical relation between electric field E and magnetic field B. It would help if the physical meanings are related to the mathematical symbols of the equations.
Additionally E is related to a fundamental force like the gravitational forces g but what really is B?
So g is related by F=mg as the gravitational force, and E is related by F=qE of the electric force, why would B be part of the Lorentz force?

REPLY [0 votes]: If you were thinking about both $F_g$ and $F_e$ for a point mass or point charge went as $r^{-2}$. Sure, it's the well know connection.
However, notice that $F_{em}=q(E+\frac{1}{c} v\times B)$, so if you classify $F_g$ and $F_e$ as the "same" according to their simple mathematical structure without thinking, you'd classify $F_m$ as another set of equation.
Further, they were written in low energy limit. In orthodox physics, gravity was in GR and EM was was in the form of relativistic constrain, no where to be close to what you meant "fundamental". Also, notice that $E$ field could be written as scalar potential and written as the sum over Laurent series basis$\{r^i\}_{i=-\infty}^\infty$, again, no where to be near your form of "fundamental". If you written $E$ field in 3 vector or 4 vector complex form, you probably won't ask this question because then $EM$ directly arise from the wave solutions.


text:
\section{Efficient Nonmyopic Approximation}
\label{section:method}
We propose to adapt two ideas in related literature to achieve efficient and nonmyopic approximation of \eqref{eq:bellman_equation}.
\subsection{Achieving Nonmyopia via Non-Adaptive Approximation}
Inspired by recent advances in nonmyopic active search \cite{jiang2017efficient, jiang2018efficient}, we propose to use the optimal batch utility with the remaining budget as batch size to approximate the adaptive future utility:
\begin{align}
        v_k(x \given \data)
        &=
        v_1(x \given \data)
        +
        \E_y[ \max_{x'} v_{k-1}(x' \given \data_1 ) ]  \nonumber  \\
        & \Downarrow   \nonumber    \\
        v_k(x \given \data)
        &\approx
        v_1(x \given \data)
        +
        \E_y[ \max_{X} V^{k-1}_1(X \given \data_1 ) ].  \label{eq:ensbo}
\end{align}
Comparing the above two equations closely, we replaced the adaptive value function $v_{k-1}$ by the non-adaptive value function $V^{k-1}_1$ with batch size $k-1$ and lookahead horizon 1, and pretend the second step is no longer a single point $x'$, but a set of points $X$ with $|X| = k-1$.
Note \eqref{eq:ensbo} can also be seen as a two-step lookahead utility where the second step is a batch with batch size being the remaining budget.

Mathematically, \eqref{eq:ensbo} is a much tighter lower bound of the true objective \eqref{eq:bellman_equation} than existing one- or two-step lookahead, or existing heuristic methods such as \glasses \cite{gonzalez2016glasses} (more discussion in related work).

\subsection{Achieving Efficiency via One-Shot Optimization}
A naive implementation of \eqref{eq:ensbo} is to draw a set of $m$ samples $y^{(i)} \drawn \Pr(y\given x, \data), i=1,\dots, m$, and acquire a set of realizations of $\data_1$: $\data_1^{(i)} = \data \cup \{(x, y^{(i)}\}, i=1,\dots,m$.
For each $\data^{(i)}_1$, we update the \gp posterior $\Pr(Y\given X, \data^{(i)}_1) $
and optimize
$X^{(i)} = \argmax_{X} V^{k-1}_1(X \given \data^{(i)}_1)$.
Then $v_k(x\given \data)$ can be approximated via sample average:
\begin{equation}
    v_k(x \given \data)
    \approx
    v_1(x\given \data)
    +
    \frac{1}{m} \sum_{i=1}^m V^{k-1}_1(X^{(i)} \given \data^{(i)}_1).  \label{eq:ensbo-sample-average}
\end{equation}
We can use any black-box optimization such as DIRECT or CMA-ES (covariance matrix adaptation evolution strategy) to optimize \eqref{eq:ensbo-sample-average}.
It is also possible to adapt the envolope theorem-based technique introduced in \cite{wu2019practical} to optimize \eqref{eq:ensbo-sample-average} with gradient-based methods. However, this is still very expensive since every evaluation of \eqref{eq:ensbo-sample-average} involves solving $m$ high dimensional optimization problems.

Inspired by recent advances in efficient implementation of the Knowledge Gradient acquisition function \cite{balandat2019botorch}, we propose a similar one-shot optimization technique for optimizing \eqref{eq:ensbo}.
The key idea is to move the max outside the expectation, and optimize $x$ and $X^{(i)}$'s jointly.
That is, we solve the following optimization problem
\begin{align}
    \max_{x, X^{(1)}, \dots, X^{(m)} }
    v_1(x\given \data)
    +
    \frac{1}{m} \sum_{i=1}^m V^{k-1}_1(X^{(i)} \given \data^{(i)}_1).  \label{eq:one-shot-ensbo}
\end{align}
Let $b=k-1$.
By moving the max outside the expectation, we turned a $d$ dimensional optimization of a very expensive objective (recall each evaluation involves $m$ optimizations of dimension $b\times d$) into a $d + m\times b \times d$ dimensional optimization where the objective is relatively easy to evaluate.

We claim that mathematically this is an equivalent optimization.
It can be understood by the simple relation
$\max_{a,b} g(a, b) = \max_a \max_b g(a,b)$.
But the joint optimization is more efficient since we don't need to solve an expensive optimization problem to get the gradient w.r.t. $a$.


TITLE: Calculate the following series limit: $\lim_{n \to \infty} (\frac{n}{n+3})^\sqrt{n(1+n)}$
QUESTION [1 upvotes]: Calculate the following series limit: $$\lim_{n \to \infty} \left(\frac{n}{n+3}\right)^\sqrt{n(1+n)}$$
I'm struggling with this limit problem. I changed over to this form: $e^{\sqrt{n(1+n)}\ln(\frac{n}{n+3})}$ but I'm not sure how to continue from here, tried using Lhopital but it just ended up being nasty maybe I used it too early?

REPLY [3 votes]: It is:
$$\lim_{n \to \infty} \left(\frac{n}{n+3}\right)^\sqrt{n(1+n)}=\lim_{n \to \infty} \left(1+\frac{3}{n}\right)^{-\sqrt{n(1+n)}}=\lim_{n \to \infty} \left[\left(1+\frac{3}{n}\right)^{\frac{n}{3}}\right]^{-\frac{3\sqrt{n(1+n)}}{n}}=e^{-3}.$$


TITLE: How calculate the indefinite integral $\int\frac{1}{x^3+x+1}dx$
QUESTION [5 upvotes]: How do I calculate the following indefinite integral?
$$\int\frac{1}{x^3+x+1}dx$$

Approach:
$x^3+x+1=(x-a)(x^2+ax+c)$ where
$a:$ real solution of the equation $a^3+a+1=0$
$c:$ real solution of the equation $c^3-c^2+1=0$
Then $$\int\frac{1}{x^3+x+1}dx=\int\frac{1}{(x-a)(x^2+ax+c)}dx=\int\frac{A}{(x-a)}dx+\int\frac{Bx+C}{(x^2+ax+c)}dx$$

REPLY [16 votes]: Starting with the root from my previous comment,
$$a=-\frac2{\sqrt3}\sinh\left(\frac13\sinh^{-1}\frac{3\sqrt3}2\right)$$
We can factor the denominator as $x^3+x+1=(x-a)(x^2+ax+a^2+1)$. Then the partial fractions expansion reads
$$\frac1{x^3+x+1}=\frac{A}{x-a}+\frac{Bx+C}{x^2+ax+a^2+1}$$
We can find $A$ by multiplying both sides by $(x-a)$ and taking the limit:
$$A=\lim_{x\rightarrow a}\frac{x-a}{x^3+x+1}=\frac1{3a^2+1}$$
by L'Hopital's rule. If we observe that
$$\begin{align}\left(3a^2+1\right)\left(6a^2-9a+4\right) & =\left(18a-27\right)\left(a^3+a+1\right)+31 \\
 & =31\end{align}$$
It follows that
$$A=\frac{6a^2-9a+4}{31}$$
Then if we multiply through by $(x^3+x+1)$ and compare coefficients of like powers of $x$ we find that
$$\begin{align}B & =\frac{-6a^2+9a-4}{31} \\
C & =\frac{18a^2+4a+12}{31}\end{align}$$
So
$$\begin{align}\frac1{x^3+x+1} & =\frac1{31}\left\{\frac{6a^2-9a+4}{x-a}+\frac{-\left(6a^2-9a+4\right)x+18a^2+4a+12}{x^2+ax+a^2+1}\right\} \\
 & =\frac1{31}\left\{\frac{6a^2-9a+4}{x-a}+\frac{\left(-3a^2+\frac92a-2\right)(2x+a)+\frac{27}2a^2+3a+9}{x^2+ax+a^2+1}\right\}\end{align}$$
Now all our integrals are elementary and we find
$$\int\frac1{x^3+x+1}dx=\frac1{31}\left\{\left(6a^2-9a+4\right)\ln|x-a|-\left(3a^2-\frac92a+2\right)\ln\left(x^2+ax+a^2+1\right)+\frac{\left(27a^2+6a+18\right)}{\sqrt{3a^2+4}}\tan^{-1}\left(\frac{2x+a}{\sqrt{3a^2+4}}\right)\right\}+C$$
Numerical integration confirms this result.


TITLE: Is there a flaw in the theory of fractional calculus?
QUESTION [8 upvotes]: Let's talk about the function $f(x)=x^n$.
It's derivative of $k^{th}$ order can be expressed by the formula:
$$\frac{d^k}{dx^k}x^n=\frac{n!}{(n-k)!}x^{n-k}$$
Similarly, the $k^{th}$ integral (integral operator applied $k$ times) can be expressed as:
$$\frac{n!}{(n+k)!}x^{n+k}$$
According the the Wikipedia article https://en.wikipedia.org/wiki/Fractional_calculus, we can replace the factorial with the Gamma function to get derivatives of fractional order.
So, applying the derivative of half order twice to $\frac{x^{n+1}}{n+1}+C$, should get us to $x^n$.
Applying the half-ordered derivative once gives:
$$\frac{d^{1/2}}{{dx^{1/2}}}\left(\frac{x^{n+1}}{n+1}+Cx^0\right)=\frac{1}{n+1}\frac{\Pi(n+1)}{\Pi(n+1/2)}x^{n+1/2}+C\frac{1}{\Pi(-1/2)}x^{-1/2}$$
where $\Pi(x)$ is the generalization of the factorial function, and $\Pi(x)=\Gamma(1+x)$
Again, applying the half-ordered derivative gives:
$$\frac{1}{n+1}\frac{\Pi(n+1)}{\Pi(n)}x^n+\frac{C}{\Pi(-1)}x^{-1}=x^n$$
which works fine because $\frac{C}{\Pi(-1)}\rightarrow 0$. So, the derivative works good but that's not the case with fractional-ordered integration.
Applying the half-ordered integral operator twice to $x^n$ should give us $\frac{x^{n+1}}{n+1}+C$. Applying the half-ordered integral once means finding a function whose half-ordered derivative is $x^n$. So, applying it once gives:
$$\frac{\Pi(n)}{\Pi{(n+1/2)}}x^{n+1/2}+C\frac{1}{\Pi(-1/2)}x^{-1/2}$$
Again, applying the half ordered derivative to this function should give a function whose half-ordered derivative is this function. So, again applying the half-integral operator gives:
$$\frac{x^{n+1}}{n+1}+C+C'\frac{1}{\Pi(-1/2)}x^{-1/2}\neq \frac{x^{n+1}}{n+1}+C$$
where $C'$ is another constant. So, why does this additional term containing $C'$ get introduced? Is the theory of fractional derivatives flawed? Is there any way to get a single constant $C$ in the end by applying the half-integral operator two times?

REPLY [1 votes]: One way to deal with these constants is to change from indefinite integration to definite integration.  For example, the Riemann-Liouville integral may be used:
$$D^{-\alpha}_af(x)=\frac1{\Gamma(\alpha)}\int_a^xf(t)(x-t)^{\alpha-1}\ dt$$
Now our constant of integration is controlled by $a$, and there will exist some $a$ such that
$$D^{-1}_a\frac d{dx}f(x)=f(x)$$


TITLE: A simple question about probability
QUESTION [0 upvotes]: Assume that on average, only $1$ in $80$ calls made by a teleseller can he/she approaches a potential client. So
1.) what is the probability that a teleseller fails to approach any potential client in $1000$ calls made,and
2.) what is the least number of calls that a teleseller has to make in order to give a probability greater than 0.9 of approaching at least one potential client
I have tried to solve the first part with poisson but not sure whether Poisson model is suitable for this cases. For the second one, i have no idea how to get the number of calls

REPLY [1 votes]: Yes, a Poisson model is appropriate here-you have many low probability events.  For 1) we have $\lambda=1000\cdot \frac 1{80}=12.5$  What is P(0)?  For 2) you need to find $\lambda$ so that $P(0) \lt 0.1$, then convert that into the number of calls.


TITLE: Is $(\mathbb{Z}^+ \times \mathbb{Z}^+, *) \simeq (A, \cdot)$ where $A$ is the set of all numbers that are the product of 2 and 3
QUESTION [0 upvotes]: EDIT: Binary Structures not groups
Is $(\mathbb{Z}^+ \times \mathbb{Z}^+, *) \simeq (A, \cdot)$ where $A$ is the set of all numbers the are the product of 2 and 3 and $*$ is defined as $(a,b) * (c,d) = (a+c, b+d)$  The products must contains at least one 2 and one 3 in order to be in $A$
Seems like $A$ is equivalent to $6\mathbb{Z}^{nonzero}$
I think it isn't isomorphic because I'm not finding a one-to-one map but I could be wrong. Neither have an identity element and both are commutative so they seem to share structural properties.
If I make $\phi: \mathbb{Z}^+ \times \mathbb{Z}^+ \to A$  defined by $\phi(x,y)=6xy, x=a+c \,\text{and}\, y = b+d$ then its definitely not one-to-one.
maybe there is a one-to-one mapping i am missing though.

REPLY [1 votes]: The map $(n,m) \mapsto 2^n 3^m$ from $(\mathbb{N}^2,+)$ to $(\mathbb{N}^{\ast}, \times)$ is an injective homomorphism of semigroups with identity.
From  $(\mathbb{Z}^2,+)$ to $(\mathbb{Q}^{\ast}, \times)$ it is an injective homomorphism of groups.
Now, restrict the co-domain to the image (and chose the one you want in your context that is not completely clear).


TITLE: Known techniques to compute flat cohomology after base change
QUESTION [3 upvotes]: Let $f$ be some homogenous polynomial of degree $d>2$.
Let $X = \operatorname{Proj} (k[x,y,z]/(f))$ where $k$ is algebraically closed field of characteristic $p >0$.
Now let $R$ be a $k$-algebra. I'm interested in the computation of $H^1(X \times_{spec(k)} spec(R),\mathbb{Z}/p\mathbb{Z})$. The usual way is to start with the Artin-schreir sequence
$$0 \to  \mathbb{Z}/p\mathbb{Z} \to \mathbb{G}_a \to \mathbb{G}_a \to 0$$
So, we get
$$ 0 \to  H^0(X \times_{spec(k)} spec(R), \mathbb{Z}/p\mathbb{Z}) \to R \to R \to H^1(X \times_{spec(k)} spec(R),\mathbb{Z}/p\mathbb{Z}) \to H^1(X , \mathbb{G}_a) \otimes R \to H^1(X , \mathbb{G}_a) \otimes R \to $$
If the map from $R \to R$ is surjective ( as when $R=k$) then  $H^1(X \times_{spec(k)} spec(R),\mathbb{Z}/p\mathbb{Z}) = \operatorname{ker}( H^1(X , \mathbb{G}_a) \otimes R \to H^1(X , \mathbb{G}_a) \otimes R$.
Is there any known way to handle cases when the map  $R \to R$ is  is not surjective or any other technique to compute $ H^1(X \times_{spec(k)} spec(R),\mathbb{Z}/p\mathbb{Z})$?

REPLY [5 votes]: First of all, there's no need to use flat cohomology here. By Theorem III.3.9 in Milne's Etale Cohomology, the canonical map $H^i_{\mathrm{et}}(X, G) \rightarrow H^i_{\mathrm{fppf}}(X, G)$ is an isomorphism when $G$ is a sheaf represented by a smooth group scheme over $X$. In particular, this works for the constant group $\mathbf{Z}/p\mathbf{Z}$ and the vector group $\mathbf{G}_a$ (which is just the quasi-coherent sheaf $\mathscr{O}_X$ and thus its flat cohomology is isomorphic to its Zariski cohomology). For $H^1$ at least, this boils down to the statement that torsors for smooth group schemes always have sections over an étale cover.
Furthermore, the Artin-Schreier sequence is an exact sequence of étale sheaves, so we have, for any $R$:
$$
0 \rightarrow R/\mathscr{F}(R) \rightarrow H^1_{\mathrm{et}}(X_R, \mathbf{Z}/p\mathbf{Z}) \rightarrow (\ker \mathscr{F} \colon H^1_{\mathrm{Zar}}(X, \mathscr{O}_X) \rightarrow H^1_{\mathrm{Zar}}(X, \mathscr{O}_X))\otimes_k R \rightarrow 0
$$
On the other hand, $X \rightarrow \mathrm{Spec}(k)$ is proper, so we can use the proper base change theorem - note that unlike the smooth base change theorem, this works for any (locally constant) abelian torsion sheaf without a hypothesis that the torsion orders are units. Let $\pi \colon X \rightarrow \mathrm{Spec}(k)$ and $f \colon \mathrm{Spec}(R) \rightarrow \mathrm{Spec}(k)$ be the structure morphisms. Then the proper base change theorem tells us that the canonical map $$f^* R^1 \pi_* \mathbf{Z}/p\mathbf{Z} \rightarrow R^1 (\pi_R)_* \mathbf{Z}/p\mathbf{Z}$$ is an isomorphism. (Note that the pullback of the constant sheaf $\mathbf{Z}/p\mathbf{Z}$ from $X$ to $X_R$ is still this constant sheaf). Now the étale sheaf on the left is the constant sheaf on $\mathrm{Spec}(R)_{\mathrm{et}}$ associated to the cohomology group $$H^1_\mathrm{et}(X, \mathbf{Z}/p\mathbf{Z}) = \ker \mathscr{F} \colon H^1_{\mathrm{Zar}}(X, \mathscr{O}_X) \rightarrow H^1_{\mathrm{Zar}}(X, \mathscr{O}_X)$$
Finally, we have a Leray spectral sequence $$E_2^{p, q} = H^p_{\mathrm{et}}(\mathrm{Spec}(R), R^q (\pi_R)_* \mathbf{Z}/p\mathbf{Z}) \implies H^{p+q}_{\mathrm{et}}(X_R, \mathbf{Z}/p\mathbf{Z})$$
Now, we have an exact sequence of low-degree terms:
$$
0 \rightarrow H^1_{\mathrm{et}}(\mathrm{Spec}(R), \mathbf{Z}/p\mathbf{Z}) \rightarrow H^1_{\mathrm{et}}(X_R, \mathbf{Z}/p\mathbf{Z}) \rightarrow  H^1_{\mathrm{et}}(X, \mathbf{Z}/p\mathbf{Z})^{\pi_0(\mathrm{Spec}(R))} \rightarrow H^2_{\mathrm{et}}(\mathrm{Spec}(R), \mathbf{Z}/p\mathbf{Z}) \rightarrow H^2_{\mathrm{et}}(X_R, \mathbf{Z}/p\mathbf{Z})
$$
This should let you compute $H^1(X_R, \mathbf{Z}/p\mathbf{Z})$ as long as you know a bit about $\mathrm{Spec}(R)$ and understand how $\mathscr{F}$ acts on the $k$-vector space $H^1_{\mathrm{Zar}}(X, \mathscr{O}_X)$.
(note that the above arguments do not work for $\mathbf{Z}/p\mathbf{Z}$ replaced by $\mu_p$, since the étale and flat cohomologies of this non-smooth group scheme differ. However, the Kummer sequence is exact in the flat topology, so you get some information. I wouldn't expect flat cohomology of something like this to play nearly as nicely with base change, and suspect it's very hard to say anything in a reasonable level of generality).


TITLE: How can we show that the function $\sum\limits_{m\in\mathbb{Z}}\frac{1}{1+(x+2\pi m)^2}$ is bounded?
QUESTION [1 upvotes]: How can we show that the function $\sum\limits_{m\in\mathbb{Z}}\frac{1}{1+(x+2\pi m)^2}$ is bounded from above as a function of $x$?

REPLY [3 votes]: First you have to convince yourself that, as a function in $x$, the sum is $2\pi$-periodic. i.e. the function
$$f(x) := \sum\limits_{m\in\mathbb{Z}}\frac{1}{1+(x+2\pi m)^2}.$$
This means that you only need to consider the values the sum takes for $x \in [0,2\pi]$, since $f(\mathbb R) = f([0, 2\pi])$ from the periodicity.
With this constraint on $x$, you can get away with assuming the "worst case scenario": that each of the denominators of the summands is as small as possible; and then compare to a simple convergent sequence that you should know!


TITLE: Evaluate $g^{(51)}(0)$ of $g(x)=\int_{1}^{x^2}\left(\cos(t)-1\right)^6t^8\,dt$
QUESTION [4 upvotes]: Consider $g:\mathbb{R}\to\mathbb{R}$ defined by:

$$g(x)=\int_{1}^{x^2}\left(\cos(t)-1\right)^6t^8\,dt$$

Show that $g\in C^{\infty}(\mathbb{R})$ and then evaluate $g^{(51)}(0)$
Since $f(t)=\left(\cos(t)-1\right)^6t^8 \in C^{\infty}(\mathbb{R})$ basically because of $\cos(t)$, and since $g(x)$ is Riemann-integrable on every $[1, x^2] \in \mathbb{R}$, we have that $g'(x) = (f(x^2))f'(x^2)$ is $C^{\infty}(\mathbb{R})$ in turn.
Furthermore $g^{(51)}(0)=0$, because we have that $\frac{g^{(51)}(0)}{51!}=k\,\,$ s.t. $\,\,k\in \mathbb{R}$ and $k$ is the coefficient of the $51^{th}$ grade term of the Taylor series of $g(x)$ centred in $0$, which is $0$ (as all of the odd grade terms).
Am I right?

REPLY [2 votes]: Here is a discussion which shows at what derivative orders there will be nonzero $
g^{(n)}(x=0)
$.
Let $f(t)=\left(\cos(t)-1\right)^6t^8 $ and $F(t)$ its antiderivative. Then $g(x) = F(x^2) - F(1)$, $g'(x) = 2 x F'(x^2) = 2 x f(x^2)$. Going further,
$$g''(x) = 2  f(x^2) + (2 x)^2 f'(x^2)\\
g'''(x) =  12 x f'(x^2)+ (2 x)^3 f''(x^2)\\
g^{(4)}(x) = 12  f'(x^2) + 24 x^2 (f'(x^2) +f''(x^2))  + (2 x)^4 f^{(3)}(x^2)\;  .\\
$$
I.e. the only terms which could possibly contribute to $g^{(n)}(x=0) $ are the leading derivatives of $f(t)$. Let's look at those.
Notice $f(x^2=0) = 0$, $f'(x^2=0) = 0$ etc.  We have to look for derivatives of $f$ which are not zero at $x=0$.
Let $f(t)=a(t) \cdot b(t) = \left(\cos(t)-1\right)^6 \cdot t^8 $. Then by repeated application of the product rule,
$$
f^{(n)}(t)= \sum_{k=0}^n {\binom{n}{k}} a^{(n-k)}(t)b^{(k)}(t)
$$
As $b(t) = t^8$, the only nonzero value of $b^{(k)}(0)$ appears at $k =8$ where $b^{(k)}(0) = 8!$. We have $a(t) = \left(\cos(t)-1\right)^6 = 2^6 \sin^{12}(t/2)$. That  means we need to take at least the twelfth derivative of $a(t)$ before we get $a(0) \ne 0$. So for $n \ge 20$, we have
$$
f^{(n)}(t)= 8! {\binom{n}{8}} a^{(n-8)}(t)
$$
The mth derivative $a^{(m)}(t=0)$ will be determined, by repeated application of the chain rule, only by the one term proportional to $\cos^{12}(t/2)$ since all other terms have factors  $\sin^k(t/2)$ which make them zero as $t =0$. Since we need to generate this term by repeated differentiation of $a(t) = 2^6 \sin^{12}(t/2)$, we have that all $a^{(m)}(t=0)$ for odd $m$  since then no such isolated term $\cos^{12}(t/2)$ will occur. As $m = n-8$, we can state that for odd $n$, $
f^{(n)}(t=0)= 0
$.
Now let's return to the derivatives of $g$ which we started to evaluate at the top. It is clear that for all odd $n$,  $
g^{(n)}(x=0) = 0
$ since all terms will have factors of $x$. For the even $n$,   $
g^{(n)}(x)
$ will have a leading term with  $
f^{(-1+n/2)}(x^2)
$. As we have seen that these factors will become nonzero only at the 20th, 22nd, 24th derivative etc., we finally obtain that  $
g^{(n)}(x=0) \ne 0
$ will be obtained for all $n = 42 + 4\, k$ with  $k \in \cal{N}_0$.
For obtaining the value of $
g^{(n)}(x=0)$, let's look at the first nonzero case at $n=42$. From the discussion of the first few derivatives of $g(x)$ above, we have that $
g^{(42)}(x=0)
$ is determined only by $
g^{(42)}(x=0) = c_{42} \cdot f^{(20)}(t=0)
$. Now $
f^{(20)}(t=0) = 8! {\binom{20}{8}} a^{(12)}(t=0) = 8!  {\binom{20}{8}} 2^{-6} \cdot 12!
$.
The factor $ c_{42}$ is more difficult. We have to sum up the number of all ways to arrive from $g'(x) = 2 x f(x^2)$ at $g^{(42)}(x) = c_{42} \cdot f^{(20)}(x^2) + \cdots$. The following thought experiment helps in determining the factor. Set $f(z) = z^{20}$. Then $f^{(20)}(z) = 20! $ and  $f^{(n)}(z) = 0 $  for $n \ge 21$. So we have $g^{(42)}(x=0) = c_{42} \cdot f^{(20)}(z = x^2=0) + \cdots = 20! c_{42} $. On the other hand, with this setting we have $g'(x) = 2 x^{41}$ and hence  $g^{(42)}(x) = 2 \cdot 41!$. Hence $c_{42} = 2 \frac{41!}{20!}$.
Compare that by the same method, $c_{2} = 2 \frac{1!}{0!} = 2$ and $c_{4} = 2 \frac{3!}{1!} = 12$ as we have already established.
In total, we have $
g^{(42)}(x=0) =  2 \frac{41!}{20!} 8!  {\binom{20}{8}} 2^{-6} \cdot 12! =  2^{-5} 41! \simeq 1.0454\cdot 10^{48}
$.
I have checked that this result is indeed true by direct computation of $
g^{(42)}(x=0) $ with Matlab help.


TITLE: Extension of measure on sigma-algebra
QUESTION [7 upvotes]: Suppose $\mu:\mathcal{F}\rightarrow[0,\infty)$ be a countable additive measure on a $\sigma$-algebra $\mathcal{F}$ over a set $\Omega$. Take any $E\subseteq \Omega$. Let $\mathcal{F}_{E}:=\sigma(\mathcal{F}\cup\{E\})$. Then, PROVE there is a countable additive measure $\nu:\mathcal{F}_{E}\rightarrow [0,\infty)$ such that $\nu(A)=\mu(A)$ for any $A\in\mathcal{F}$. I already know the measure extension theorem. But it is based on algebra and the extension is only about $\sigma(\mathcal{F})$. Can someone give me hint? Or how can I make use of measure extension theorem.

REPLY [1 votes]: I will also assume that the measure is a probability measure - This doesn't really matter. Let $a = \text{sup} \{\mu(K) : K \subseteq E, K \in \mathcal{F}\}$. Let $K \subseteq E, K \in \mathcal{F}$ be such that $\mu(K) = a$. Note that $\mathcal{F}_E = \{(A \cap E) \bigcup (B \cap E^c) : A, B \in \mathcal{F}\}$. Put $\nu((A \cap E) \bigcup (B \cap E^c)) = $ $\mu(A \cap K) + \mu(B \cap K^c)$. Now check.


TITLE: Ways to put numbered balls in boxes no box being empty
QUESTION [5 upvotes]: I know the formula for putting $n$ identical balls in $r$ different boxes such that each box has at least 1 ball, but what is the formula for putting $n$ different balls in $r$ different boxes, no box being empty?
Thanks!

REPLY [0 votes]: K distinct balls are K! distinct vectors of identical balls. K identical balls can be distributed in N distinct boxes such that no box is empty in (K-1)C (N-1) ways. The arrangement to distribute K! distinct balls in N boxes is  K!*(K-1)C(N-1)


TITLE: The integer $c_n$ in $(1+4\sqrt[3]2-4\sqrt[3]4)^n=a_n+b_n\sqrt[3]2+c_n\sqrt[3]4$
QUESTION [9 upvotes]: For non-negative integer $n$, write
$$(1+4\sqrt[3]2-4\sqrt[3]4)^n=a_n+b_n\sqrt[3]2+c_n\sqrt[3]4$$
where $a_n,b_n,c_n$ are integers. For any non-negative integer $m$, prove or disprove
$$2^{m+2}|c_n\iff2^m|n$$
So far I have
 $$\left[\begin{array}{c}a_n\\b_n\\c_n\end{array}\right]=\left[\begin{array}{ccc}1&-8&8\\4&1&-8\\-4&4&1\end{array}\right]\left[\begin{array}{c}a_{n-1}\\b_{n-1}\\c_{n-1}\end{array}\right].$$

REPLY [1 votes]: Seems to me that this is a $2$-adic question. Our given number, let’s call it $\rho$ for convenience, is of the form $1+4z$, and we’re looking at its multiplicative properties. But, calling $R=\mathbb Z_2(\root 3\of 2\,)$, the multiplicative group $1+4R$ is isomorphic (via the $2$-adic logarithm) to an open subgroup of the additive group $R^+$. Thus $1+4R$ is a free $\mathbb Z_2$-module of rank three. Clearly $1+4$, $1+4\root3\of2$, and $1-4\root3\of2^2$ form a basis of our multiplicative module, just look at their logarithms. Notice also that $(1+4\root3\of2)(1-4\root3\of2^2\,)=\rho-32$, and this means that $\rho^n$ is very close to $(1+4\root3\of2\,)^n(1-4\root3\of2^2)^n$, $2$-adically speaking. But we know the exact $2$-adic valuation of $ (1+4\root3\of2\,)^n-1$ and of
$ (1-4\root3\of2^2)^n-1$, for any $n\ge1$:
$$
v\left[(1+4\root3\of2\,)^n-1\right]=v(n)+2+\frac13\>,\>
v\left[(1-4\root3\of2^2)^n-1\right]=v(n)+2+\frac23\,.
$$
The desired result follows, after a few details are supplied.
EDIT:
Rather than replace the unnecessarily complicated and (probably) confusing explanation above, let me give a clearer argument. The desired result follows from the fact that for $z\in R$, we have the congruence $(1+4z)^n\equiv1+4nz\pmod{8n}$, using $z=\root3\of2-\root3\of2^2$. Although this can be proved directly from the Binomial Theorem, it’s quicker and easier to see it by using the explicit isomorphism between the multiplicative group $1+4R$ and the additive group $4R$ given by the logarithm and exponential. We have:
$$
\log(1+4z)=4\left[z-2z^2+\frac{16z^3}3+\cdots\right]
$$
and
$$
\exp(4z)=1+4\left[z+2z^2+\frac{8z^3}3+\cdots\right]\,,
$$
where the two series shown in brackets are inverses of each other, and the logarithmic one clearly has all coefficients $2$-adic integers, indeed all beyond the first are divisible by $2$. As a result, the same is true for the exponential series. So you see that in the original notation, $b_n\equiv 4n\pmod{8n}$ and $c_n\equiv-4n\pmod{8n}$.


TITLE: Fourier Transform of Fractional Laplacian
QUESTION [1 upvotes]: I'm trying to solve a PDE with a spectral method.
The PDE has a fractional Laplacian... $\Delta^s$.
In regards to a numerical implementation, will the "s" term simply become the exponent of the "differentiation matrices".
$\widehat{(-\Delta)^s f}(\xi) = |\xi|^{2s} \hat f(\xi).$
Or is it not so simple?

REPLY [0 votes]: The equation there is just the standard definition of fractional Laplacian in terms of the Fourier transform. See for instance the surverys
https://arxiv.org/abs/1104.4345
https://arxiv.org/abs/1712.03347
The subject of numerical methods for equations involving the fractional Laplacian is of course very broad and an area of active research. See for instance the paper
https://arxiv.org/abs/1712.03347
for an approach based on the finite element method.


TITLE: Finding the matrix representation of a linear operator $T$ for $T(f(x))=2(f(x))-f'(x)$ in $\mathbb{P}_2(\mathbb{R})$
QUESTION [1 upvotes]: Using the standard basis $\{1,x,x^2\}$ gives me a matrix however it doesn't work when working towards Jordan Canonical Form with the matrix.  What I get is
$\begin{pmatrix}
2  \\
0 \\
0\end{pmatrix}\begin{pmatrix}
-1  \\
2 \\
0\end{pmatrix}\begin{pmatrix}
0  \\
-2 \\
2\end{pmatrix}$
 as my columns.  Where did I make a mistake?

REPLY [0 votes]: Your matrix representation for the operator $T$ is correct. This operator has 2 as eigenvalue with algebraic multiplicity 3, but geometric multiplicity 1. In other words: the eigenspace has dimension one and the matrix is not diagonalizable. Thus the Jordan normal form is:
$$
\begin{pmatrix} 2 & 1 & 0 \\ 0 & 2 & 1 \\ 0 & 0 & 2 \end{pmatrix}.
$$


TITLE: Parallel surface to paraboloid
QUESTION [0 upvotes]: I have the equation for a paraboloid
$z=x^2+y^2$
I need to obtain a parallel surface, Does anyone know what is the procedure to determine it?

REPLY [0 votes]: Just add a normal vector of desired length.
The equation of the surface is
$$g\colon (x,y)\mapsto \bigl(x,y,f(x,y)\bigr),$$
the normal vector is the cross product of the derivatives in respect to $x$ and $y$, namely
$$n=\begin{pmatrix}1\\0\\f_x\end{pmatrix}
\times\begin{pmatrix}0\\1\\f_y\end{pmatrix}
=\begin{pmatrix}-f_x\\-f_y\\1\end{pmatrix},$$
its length is $\sqrt{f_x^2+f_y^2+1}$.  Now define for any real number $\epsilon$ the $\epsilon$-parallel surface $g_{\epsilon}$ of $g$ by
$$g_{\epsilon}(x,y)=g(x,y)+\epsilon\cdot\frac{n(x,y)}{\|n(x,y)\|}$$
In our case $f(x,y)=x^2+y^2$.  The normal vector here is $(-2x,-2y,1)$, its length is $\sqrt{4x^2+4y^2+1}$, hence
$$g_{\epsilon}(x,y)=\begin{pmatrix}x\\y\\x^2+y^2\end{pmatrix}
+\frac{\epsilon}{\sqrt{4x^2+4y^2+1}}
\begin{pmatrix}-2x\\-2y\\1\end{pmatrix}$$
will be the parallel surface in oriented distance $\epsilon$.

First picture with $\epsilon=2$, second with $\epsilon=10$, where weird things are going on.


TITLE: Some gamma function questions...
QUESTION [2 upvotes]: I have shown that $\Gamma(a+1)=a\Gamma(a)$ for all $a>0$.
But I'd also like to show the following 2 things:
1) Using the previous fact, I'd like to show that $\lim_{a \to 0^{+}}a\Gamma(a) = \Gamma(1)=1$
The second equality is obvious, but how about the limit equality?
2) Using 1) then, I'd like to calculate $\int_{0}^{\infty} {{e^{-x}-e^{-3x}}\over{x}}$. The suggestion is to, using the first two facts above, calculate
$$\lim_{a \to 0^{+}}\int_{0}^{\infty} x^{a}{{e^{-x}-e^{-3x}}\over{x}}$$.
I can sort of prove 1), provided I am allowed to switch the $a$ limit and the $M$ limit outside the integral (we replace the upper limit $\infty$ with $M$ and take the limit as $M \to \infty$ using the MCT.) However, though I get the correct answer of $1$, it seems fishy that I am allowed to switch the limits like this.
Number 2) I have no idea.

REPLY [1 votes]: Here is the solution to part (2) using the Gamma function and the result of part (1):
$$\int_0^\infty x^a \frac{e^{-x}-e^{-3x}}{x}dx  = \int_0^\infty x^{a-1}e^{-x}dx-\int_0^\infty x^{a-1}e^{-3x}dx.$$
For the second integral on the RHS, make the change of variables $u = 3x$ to obtain
$$\int_0^\infty x^a \frac{e^{-x}-e^{-3x}}{x}dx  = \int_0^\infty x^{a-1}e^{-x}dx-3^{-a}\int_0^\infty u^{a-1}e^{-u}dx.$$
Using the definition of the Gamma function,
$$\int_0^\infty x^a \frac{e^{-x}-e^{-3x}}{x}dx  = (1-3^{-a})\Gamma(a) = \frac{1-3^{-a}}{a}a\Gamma(a).$$
From part (1) we have $\lim_{a \rightarrow 0+} a\Gamma(a) = 1$, and using L'Hospital's rule we know that
$$\lim_{a \rightarrow 0+}\frac{1-3^{-a}}{a} = \log(3)$$
Therefore
$$\lim_{a \rightarrow 0+}\int_0^\infty x^a \frac{e^{-x}-e^{-3x}}{x}dx  =  \lim_{a \rightarrow 0+}\frac{1-3^{-a}}{a} \lim_{a \rightarrow 0+} a\Gamma(a) = \log(3).$$


TITLE: Element distinctness in O(n) time?
QUESTION [21 upvotes]: We all know that element distinctness in the comparison based model cannot be done in $o(n\log n)$ time. However, on a word-RAM, one can possibly achieve better.
Of course, if one assumes the existence of a perfect hash function that can be computed in linear time, we get a linear time algorithm for element distinctness: just keep hashing the numbers one by one and return 1 if there is a collision.
However, there are two issues: 1) most constructions of perfect hash functions that I could find used randomness and 2) I cannot find a discussion of the pre-processing time anywhere, i.e., the time required to decide what hash function one is going to use based on the input set of numbers.
Fredman et al.'s "Storing a sparse table with $O(1)$ worst case access time" does resolve the first issue by providing a hash function with $O(1)$ access time in the worst case, but says nothing about the second issue.
So to sum up, here's what I want:
Design an algorithm that given a set $S$ of $n$ numbers (each number being $w$ bits long) on a word-RAM with word length $w$, finds a hash function $h:S\rightarrow \{1, \ldots , m\}$ in $O(n)$ time, where $m = O(n)$. The function $h$ should have the property that for any $j \in \{1, \ldots , m\}$, the number of elements of $S$ that map to $j$ is a constant and computing $h(i)$ should take $O(1)$ time in a "reasonable" word-RAM model, i.e., the model should not allow "exotic" functions on words to be evaluated in $O(1)$ time.
I will also like to know if there are algorithms to solve element distinctness on the word-RAM that do not use hash functions at all.

REPLY [1 votes]: That is exactly what the FKS paper you mention do - and it takes linear time (in expectation). See page 5 here for the analysis... http://www1.icsi.berkeley.edu/~luby/PAPERS/pairwise.ps