text:
\begin{document}

\title{Utility-Energy Efficiency Oriented User Association with Power Control in Heterogeneous Networks}
\author{
\IEEEauthorblockN{Xietian~Huang, Wei~Xu, Hong~Shen,  Hua~Zhang, and Xiaohu~You}\\

\vspace{-0.8cm}
\thanks{
Manuscript received July 30, 2017; revised November 17, 2017 and December 29, 2017; accepted January 05, 2018. This work of was supported in part by the Hong Kong, Macao and Taiwan Science \& Technology Cooperation Program of China (2016YFE0123100), NSFC (grant nos. 61471114, 61501110, 61571118), the Six Talent Peaks project in Jiangsu Province under GDZB-005, the Open Research Fund of the State Key Lab of ISN under ISN18-03, and the NSF of Jiangsu Province under BK20150635. The editor coordinating the review of this paper and approving it for publication was M. Assaad.
\textit{(Corresponding authors: Wei Xu, Hong Shen.)}

All authors are with the National Mobile Communications Research Laboratory (NCRL), Southeast University, Nanjing 210096, China. X. Huang and W. Xu are also with the State Key Laboratory of Integrated Services Networks, Xidian University, Xi'an 710071, China (e-mail: xthuang@seu.edu.cn; wxu@seu.edu.cn).

}

}

\maketitle

\newtheorem{mylemma}{Lemma}
\newtheorem{mytheorem}{Theorem}
\newtheorem{mypro}{Proposition}
\begin{abstract}

This letter investigates optimizing utility-energy efficiency (UEE), defined as the achieved network utility when consuming a unit of power, rather than a typical energy efficiency metric, in a heterogeneous network (HetNet). To tackle the nonconvexity of the problem due to integer constraints and coupled variables, we devise an alternating optimization algorithm. It applies Lagrangian dual analysis with auxiliary variables, which successfully transforms each subproblem to a convex one with efficient solutions. The proposed algorithm is consequently guaranteed to converge to a local optimum with noticeable performance gain via simulation verifications.
\end{abstract}

\begin{IEEEkeywords}
Utility-energy efficiency (UEE), user association, power control, heterogeneous network (HetNet), load balancing.
\vspace{-0.5cm}
\end{IEEEkeywords}

\IEEEpeerreviewmaketitle
\section{Introduction}
Heterogeneous network (HetNet) has recently become a research focus as an effective technology to improve spectrum efficiency (SE) \cite{Damnianovic2011A}. Different from traditional network, HetNet equips low-power small-cell base stations (SBSs) besides macro-cell base station (MBS), which makes the deployment more flexible while also comes with several challenges.

User association is a significant issue that needs to be reconsidered. Since the transmit power of MBS is much higher than that of SBS, most users tend to be associated with MBS via classical association schemes, leading to unbalanced load. In this way, MBS users are unlikely to reach high rate because they have to share the resource of MBS \cite{Ye2012User}. While the whole network can benefit by transferring some MBS users to lightly-loaded SBSs. Transmit power control is a further resource allocation problem directly related to user association \cite{Shen2014Distributed}. A proper setting of power can decrease the interference between different tiers of BSs, which strongly influences the achievable rate. Early works like \cite{Hanly1995An} have revealed the benefits of joint optimization of user association and power control.

With the increasing energy costs of wireless networks, energy efficiency (EE) has become an important metric in 5G \cite{Cui2016Optimal}. Generally, EE design maximizes the achieved rate evaluated by per unit power consumption. In practice, however, one ultimate metric that matters is the network utility instead of the raw theoretical rate. Therefore, we propose a utility-energy efficiency (UEE) metric. By exploiting the popular log-utility model, we formulate the joint optimization of association and power control by UEE maximization. Since the original problem is nonconvex, we propose an iterative algorithm by solving the association and power control problem alternately. Numerical results show that the proposed algorithm outperforms existing methods in terms of various metrics including UEE.

\section{System Model}\label{sec:system_model}
Consider a downlink HetNet consisting of $N_m$ MBSs and $N_s$ SBSs. Let $\mathbb{B}$ be the set of all BSs. $\mathbb{U}$ denotes the set of all users with size $N_u$. The received signal of user $i$ is
\vspace{-0.2cm}
\begin{equation}
y_{i}=\sum_{j\in \mathbb{B}}h_{ij}\sqrt{p_{j}}s_{j}+n_{i},\forall i\in \mathbb{U}, j\in \mathbb{B}
\vspace{-0.2cm}
\end{equation}
where $s_{j}$ is the transmit signal, $h_{ij}$ is the flat-fading channel gain, $n_{i}$ is the additive zero-mean Gaussian noise with variance $\sigma^{2}$, and $p_{j}$ denotes the transmit power. Assume that the BS has the global channel state information (CSI) for optimization and the channels vary slowly. Thus we can obtain the received signal-to-interference-plus-noise ratio (SINR) as

\begin{equation}\label{eq:SINR}
 \text{SINR}_{ij}=\frac{h_{ij}p_{j}}{\sum_{q\neq j}h_{iq}p_{q}+\sigma^{2} },\forall i\in \mathbb{U}, j\in \mathbb{B}.
\end{equation}

Denote binary variables $\{x_{ij}\}$ as the indicator of the association. If user $i$ is associated with BS $j$, then $x_{ij}\!=\!1$; otherwise $x_{ij}\!=\!0$. Although letting each user associate with more than one BS can avoid the combinatorial assignment issue \cite{Chien2016Joint}, it becomes difficult to implement multiple-BS association in practice \cite{Ye2012User}, when considering the synchronization and control signaling. Thus, we assume that each user can be associated with only one BS at a time. Denote $k_{j}$ as the number of users associated with BS $j$, i.e., $k_{j}\!=\!\sum_{i\in \mathbb{U}} x_{ij}$. The system bandwidth $W$ is reused by all BSs, and users associated with the same BS share the frequency resource. Our proposed algorithm considers a simple uniform resource allocation, thus the resource allocated to each user is $W/k_{j}$. The joint optimization of association and bandwidth allocation may achieve better performance at the expense of increased complexity, which is of great interest for further considerations.

According to the Shannon's formula, when user $i$ is associated with BS $j$, the achievable rate is characterized as
\begin{equation}\label{eq:rate}
 c_{ij}=(W/k_{j})\log(1+\text{SINR}_{ij}),\forall i\in \mathbb{U}, j\in \mathbb{B}.
\end{equation}

In downlink networks, EE is defined as the ratio of the sum rate to the total power consumption. However, maximizing system EE may result in extremely unfair throughput allocation. In practice, the network utility is more meaningful to subscribers. To preserve some degree of fairness, we consider optimizing the network UEE, i.e., maximizing the ratio of the sum utility rate to the power consumption. The logarithmic function is a typical utility function which is proven to achieve tradeoff between network throughput and fairness. Now we can formulate the UEE optimization problem by jointly finding the optimal association and power control strategies. It follows
\vspace{-0.2cm}
\begin{subequations}\label{eq:pro_X_P}
\begin{align}
\mathop{\max}_{\bm{X},\bm{k},\bm{p}}\quad\!\!
&\frac{\sum\limits_{i\in \mathbb{U}}\sum\limits_{j\in \mathbb{B}} x_{ij}\log c_{ij}}{\sum\limits_{j\in \mathbb{B}}p_{j}+P_c}\\
\textrm{s.t.}\quad\!\!
&0\leq p_{j}\leq P_{j}^{m},\; \forall j\in \mathbb{B}\\
&\small{\sum\limits_{j\in \mathbb{B}}} x_{ij} = 1, \; \forall i\in \mathbb{U}\\
&\small{\sum\limits_{i\in \mathbb{U}}} x_{ij} = k_{j}, \quad \small{\sum\limits_{j\in \mathbb{B}}} k_{j} = N_u\\
& x_{ij}\in \{0,1\}, \; \forall i\in \mathbb{U}, j\in \mathbb{B}
\end{align}
\end{subequations}
where $\bm{X}\!=\![x_{ij}]_{N_{u}\times (N_{s}+N_{m})}$ is the association matrix, $\bm{k}\!=\!\{k_{j}\}_{j\in \mathbb{B}}$ denotes the BS load, $\bm{p}\!=\!\{p_{j}\}_{j\in \mathbb{B}}$ is the transmit power vector, $P_{c}$ is a constant denoting the circuit power consumption, and $P_{j}^{m}$ is the maximum power constraint.

\section{UEE Oriented Resource Allocation}
Problem \eqref{eq:pro_X_P} is a typical nonlinear fractional programming and can be equivalently transformed via parametric programming \cite{Xu2015Robust}. Define the parametric subtractive problem as
\begin{equation}\label{eq:pro_eta}
 F(\eta)= \max\limits_{\bm{X},\bm{k},\bm{p}} \quad \sum\limits_{i\in \mathbb{U}}\sum\limits_{j\in \mathbb{B}} x_{ij}\log c_{ij}-\eta(\sum\limits_{j\in \mathbb{B}}p_{j}+P_c).
\end{equation}
The solution $\{\bm{X}^*,\bm{k}^*,\bm{p}^*\}$ to \eqref{eq:pro_X_P} is also optimal for \eqref{eq:pro_eta} for a certain $\eta^{*}\geq 0$ that satisfies $F(\eta^{*})= 0$. The optimal value of \eqref{eq:pro_X_P} is equal to $\eta^{*}$. For fixed $\eta$, problem \eqref{eq:pro_eta} has the form as
\begin{equation}\label{eq:pro_X_P_eta}
\mathop{\max}_{\bm{X},\bm{k},\bm{p}}\ \sum\limits_{i\in \mathbb{U}}\sum\limits_{j\in \mathbb{B}} x_{ij}\log c_{ij}-\eta \sum\limits_{j\in \mathbb{B}}p_{j},\; \textrm{s.t.}\;(4\text{b})-(4\text{e}).
\end{equation}

Problem \eqref{eq:pro_X_P_eta} is still a nonconvex mixed-integer problem and the optimum is difficult to find. Since the SINR only depends on transmit power, this problem will be relatively tractable if $\bm{p}$ is temporarily fixed. Thus, we first consider the association problem under fixed $\bm{p}$, and then deal with the power control with fixed $\bm{X}$. Joint optimization is conducted alternately.

\subsection{Optimal User Association with Fixed Power}
Given $\bm{p}$, and introducing $m_{ij}\triangleq \log\left(W\log\left(1+\text{SINR}_{ij}\right)\right)$, the user association problem can be equivalently rewritten as
\begin{equation}\label{eq:problem_X}
\mathop{\max}_{\bm{X},\bm{k}}\ \sum\limits_{i\in \mathbb{U}}\sum\limits_{j\in \mathbb{B}} x_{ij}m_{ij}-\sum\limits_{j\in \mathbb{B}}k_{j}\log k_{j},\; \textrm{s.t.}\;(4\text{c})-(4\text{e}).
\end{equation}

Problem \eqref{eq:problem_X} is generally complicated due to the binary-valued constraint (4e). We in the following first adopt the fractional user association relaxation, where $x_{ij}$ can take any real value in [0,1]. Later we will show that fortunately the relaxed problem generates optimal $x_{ij}^{*}$ as integers which is thus guaranteed as the optimum of original problem \eqref{eq:problem_X}.

The relaxed user association problem equals:
\begin{subequations}\label{eq:relaxation}
\begin{align}
\mathop{\max}_{\bm{X},\bm{k}}\quad\!\!
&\sum\limits_{i\in \mathbb{U}}\sum\limits_{j\in \mathbb{B}} x_{ij}m_{ij}-\sum\limits_{j\in \mathbb{B}}k_{j}\log k_{j}\\
\textrm{s.t.}\quad\!\!
&(4\text{c}),(4\text{d}),0\leq x_{ij}\leq 1.
\end{align}
\end{subequations}
\begin{mylemma}
Problem \eqref{eq:relaxation} is a convex problem.
\end{mylemma}
\begin{proof}
It is easy to prove the concavity of the objective function by checking its Hessian matrix which is diagonal with nonpositive elements, and all constraints are linear.
\end{proof}
To deal with \eqref{eq:problem_X}, a typical way is to solve convex problem \eqref{eq:relaxation} by interior-point method \cite{Boyd2004Convex} and then conduct rounding on $\bm{X}$. The optimality however may not be preserved in theory. Considering that the dimension of the variables in \eqref{eq:relaxation} is $(N_u\!+\!1)(N_m\!+\!N_s)$, the complexity of solving \eqref{eq:relaxation} by the standard interior-point method is $\mathcal{O}(N_u^3(N_m\!+\!N_s)^3)$ [8, p. 487, 569], which is generally high. Here, we adopt the Lagrangian dual decomposition analysis \cite{Palomar2006A} for achieving low-complexity and optimum guaranteed solutions. Introducing dual variables $\bm{\mu}\!=\!\{\mu_{j}\}_{j\in \mathbb{B}}$ and $\nu$, the Lagrangian function of \eqref{eq:relaxation} is
\vspace{-0.1cm}
\begin{align}\label{eq:lagfun}

  L(\bm{X},\bm{k},\bm{\mu},\nu)\!=\!&\sum\limits_{i\in \mathbb{U}}\sum\limits_{j\in \mathbb{B}} x_{ij}m_{ij}\!-\!\sum\limits_{j\in \mathbb{B}}k_{j}\log k_{j}\\
                 &\!-\!\sum\limits_{j\in \mathbb{B}}\mu_{j}(\sum\limits_{i\in \mathbb{U}}x_{ij}\!-\!k_{j})\!-\!\nu(\sum\limits_{j\in \mathbb{B}}k_{j}\!-\!N_u).\nonumber
\end{align}

It is readily to find that the convex problem in \eqref{eq:relaxation} satisfies the Slater's condition, which means that strong duality holds \cite{Boyd2004Convex}. Therefore, primal problem \eqref{eq:relaxation} can be equivalently solved by solving the dual problem.

The optimal $k_{j}^{*}$ can be obtained by letting $\frac{\partial L(\cdot)}{\partial k_{j}}\!=\!0$. Then by rewriting the Lagrangian function and removing irrelevant items, the optimization problem on $\bm{X}$ is simplified as
\vspace{-0.1cm}
\begin{equation}
\max\limits_{\bm{X}}\ \sum\limits_{i\in \mathbb{U}}\sum\limits_{j\in \mathbb{B}}x_{ij}(m_{ij}-\mu_{j}),\;\textrm{s.t.}\;(4\text{c}),0\leq x_{ij}\leq 1.
\end{equation}
The objective function is upper bounded by
\vspace{-0.1cm}
\begin{equation}\label{eq:analysis}
\sum\limits_{i\in \mathbb{U}}\sum\limits_{j\in \mathbb{B}}x_{ij}(m_{ij}-\mu_{j})\leq \sum\limits_{i\in \mathbb{U}}\max\limits_{j\in \mathbb{B}}(m_{ij}-\mu_{j}).
\end{equation}
If there exists one feasible $x_{ij}$ making (11) achieve with equality, it is exactly the optimal solution to (10). Intuitively, we find a feasible solution as given by
\vspace{-0.1cm}
\begin{equation}\label{eq:opt_X}
x_{ij}^{*}\!=\!
\begin{cases}
1, &\text{if}\; j \!=\! j^{(i)}\\
0, &\text{if}\; j \!\neq\! j^{(i)},
\end{cases}
\text{where}\;j^{(i)}\!=\!\arg\;\max\limits_{q\in \mathbb{B}}(m_{iq}\!-\!\mu_{q}).
\end{equation}
We find that although the binary constraint is relaxed in \eqref{eq:relaxation}, the optimal $x_{ij}^{*}$ is fortunately either 0 or 1 which exactly satisfies constraints in \eqref{eq:problem_X}. Thus, the optimum obtained by solving dual problem is in fact optimal to original problem \eqref{eq:problem_X}.

The dual variables are iteratively updated as
\vspace{-0.1cm}
\begin{equation}\label{eq:opt_u}
\mu_{j}^{(t+1)}=\mu_{j}^{(t)}-\delta^{(t)}({\rm e}^{\mu_{j}^{(t)}-\nu^{(t)}-1}-\sum\limits_{i\in \mathbb{U}}x_{ij}^{(t)})
\end{equation}
\vspace{-0.1cm}
\begin{equation}\label{eq:opt_v}
\nu^{(t)}=(\log \sum\limits_{j\in \mathbb{B}}{\rm e}^{\mu_{j}^{(t)}-1})/N_u
\vspace{-0.2cm}
\end{equation}
where $\delta^{(t)}$ is the step size.

The Lagrangian dual method follows our engineering intuitions. Regard $\mu_j$ as the price of BS $j$ and $m_{ij}$ as the utility rate if user $i$ is associated with BS $j$. When choosing the BS, each user considers maximizing the utility rate minus the price according to \eqref{eq:opt_X}, while each BS updates its price to balance load via \eqref{eq:opt_u}, which indicates the law of supply and demand. If the service demand of users $\sum_{i\in \mathbb{U}}x_{ij}^{(t)}$ is larger than the total supply amount ${\rm e}^{\mu_{j}^{(t)}-\nu^{(t)}-1}$ of BS $j$, it increases the price.

\subsection{Power Control Method}\label{sec:power control}
Given the optimized association, we then focus on power optimization. With fixed $\bm{X}$ and introducing auxiliary variables $\bm{\lambda}=\{\lambda_{ij}\}_{i\in \mathbb{U},j\in \mathbb{B}}$, the power control problem equals to
\begin{subequations}\label{eq:pro_P_lam1}
\begin{align}
\mathop{\max}_{\bm{p},\bm{\lambda}}\quad\!\!
&\sum\limits_{i\in \mathbb{U}}\sum\limits_{j\in \mathbb{B}} x_{ij}\log\left(\log\left(1+\lambda_{ij}\right)\right)-\eta\sum\limits_{j\in \mathbb{B}}p_{j}\\
\textrm{s.t.}\quad\!\!
&(4b),\ \frac{h_{ij}p_{j}}{\sum_{q\neq j}h_{iq}p_{q}+\sigma^{2}}\geq \lambda_{ij},\; \forall i\in \mathbb{U}, j\in \mathbb{B}.
\end{align}
\end{subequations}

Note that introducing $\bm{\lambda}$ helps to transform the objective function into concave. Since each user is associated with one BS, there exists only one $j$ such that $x_{ij}\!=\!1$ for user $i$. Let $\mathbb{U}_j\!=\!\{i\in \mathbb{U}|x_{ij}\!=\!1\}$ denote the set of users associated with BS $j$. For convenience, we use $\bm{\lambda^{'}}\!=\!\{\lambda_{i}\}_{i\in \mathbb{U}_j}$ to replace $\bm{\lambda}$. Then problem \eqref{eq:pro_P_lam1} can be further reformulated as
\begin{subequations}\label{eq:pro_P_lam2}
\begin{align}
\mathop{\max}_{\bm{p},\bm{\lambda^{'}}}\quad\!\!
&\sum\limits_{j\in \mathbb{B}}\sum\limits_{i\in \mathbb{U}_j} \log\left(\log\left(1+\lambda_{i}\right)\right)-\eta\sum\limits_{j\in \mathbb{B}}p_{j}\\
\textrm{s.t.}\quad\!\!
&(4b),\ \frac{h_{ij}p_{j}}{\sum_{q\neq j}h_{iq}p_{q}+\sigma^{2}}\geq \lambda_{i},\; \forall j\in \mathbb{B}, i\in \mathbb{U}_j.
\end{align}
\end{subequations}

Introducing auxiliary variables ${\rm e}^{\rho_{j}}\triangleq p_j$ and ${\rm e}^{\theta_{i}}\triangleq \lambda_{i}$, the nonconvex constraints in (16) thus become convex as
\begin{equation}
 {\rm e}^{\theta_{i}-\rho_{j}+\beta_{i}}+\sum_{q\neq j}{\rm e}^{\theta_{i}-\rho_{j}+\rho_{q}+\gamma_{iq}} \leq 1
 \vspace{-0.2cm}
\end{equation}
where $\beta_{i} \triangleq \log\left( \frac{\sigma^{2}}{h_{ij}}\right)$ and $\gamma_{iq} \triangleq \log\left(\frac{h_{iq}}{h_{ij}}\right)$ are constants. Further, by defining $\omega_i \triangleq \theta_{i}-\rho_{j}+\beta_{i}$ and $s_{ijq} \triangleq \theta_{i}-\rho_{j}+\rho_{q}+\gamma_{iq}$, problem \eqref{eq:pro_P_lam2} is reformulated as
\begin{subequations}\label{eq:pro_rho_theta}
\begin{align}
\mathop{\max}_{\bm{\rho},\bm{\theta},\bm{\omega},\bm{s}}\quad\!\!
&\sum\limits_{j\in \mathbb{B}} \sum\limits_{i\in \mathbb{U}_j} \log\left(\log\left(1+{\rm e}^{\theta_{i}}\right)\right)-\eta\sum\limits_{j\in \mathbb{B}}{\rm e}^{\rho_{j}}\\
\textrm{s.t.}\quad\!\!
&\rho_{j}\leq \log \left(P_{j}^{m}\right), \; \forall j\in \mathbb{B} \\
&{\rm e}^{\omega_i}\!+\!\sum_{q\neq j}{\rm e}^{s_{iq}} \leq 1, \; \forall j\in \mathbb{B}, i\in \mathbb{U}_j \\
&\omega_i\!=\!\theta_{i}\!-\!\rho_{j}\!+\!\beta_{i}, \; \forall j\in \mathbb{B}, i\in \mathbb{U}_j \\
&s_{ijq}\!=\!\theta_{i}\!-\!\rho_{j}\!+\!\rho_{q}\!+\!\gamma_{iq}, \, \forall j\in \mathbb{B}, i\in \mathbb{U}_j, q \neq j
\end{align}
\end{subequations}
where $\bm{\rho}=\{\rho_{j}\}_{j\in \mathbb{B}}$, $\bm{\theta}=\{\theta_{i}\}_{i\in \mathbb{U}_j}$, $\bm{\omega}=\{\omega_{i}\}_{i\in \mathbb{U}_j}$, and $\bm{s}=\{s_{ijq}\}_{j\in \mathbb{B}, i\in \mathbb{U}_j, q\neq j\in \mathbb{B}}$.

\IncMargin{1em}
\begin{algorithm}
    Initialize the parameter $\eta=0$, and a small $\varsigma>0$\;
    \Repeat{$\varsigma^{*}\leq \varsigma$}
            {Initialize any feasible $\bm{p}$\;
                \Repeat{\text{convergence}}
                {Solve association problem (7) with fixed $\bm{p}$\;
                 Solve power control problem (15) with fixed $\bm{X}$\;
                }
                Calculate $\varsigma^{*}\!=\!\sum\limits_{i\in \mathbb{U}}\sum\limits_{j\in \mathbb{B}} x_{ij}\log c_{ij}\!-\!\eta(\sum\limits_{j\in \mathbb{B}}p_{j}\!+\!P_c)$\;
                Update $\eta\!=\!(\sum\limits_{i\in \mathbb{U}}\sum\limits_{j\in \mathbb{B}} x_{ij}\log c_{ij})/(\sum\limits_{j\in \mathbb{B}}p_{j}\!+\!P_c)$\;
            }
   Output optimal $\bm{X}^*$ and $\bm{p}^*$\;
    \caption{IUAPC Algorithm\label{al1}}
\end{algorithm}
\DecMargin{1em}

Problem \eqref{eq:pro_rho_theta} is convex because the objective function is concave and the constraints are either linear or convex. Thus, the globally optimal solution can be obtained by, e.g., the interior-point method. We stress that efficient solutions to this specific problem can be acquired by exploiting the dual method \cite{Yang2017Fair}. Details are given in the Appendix.

Thus far, we are ready to present the iterative user association and power control (IUAPC) algorithm in \textbf{Algorithm 1}. Since the objective value increases with global optimum found in each iteration and it has a finite upper bound, the overall iterative algorithm is guaranteed to converge \cite{Xu2015Robust}\cite{Wang2012Joint}. Besides, the solution can be a local optimum following the proof in \cite{Xu2015Robust}. For our proposed algorithm, the total complexity amounts to $\mathcal{O}(N_u(N_m\!+\!N_s)(\log_2(1/\epsilon_0)\!+\!N_m\!+\!N_s))$, where $\epsilon_0$ is the accuracy of bisection search. Our proposed algorithm is centralized, which can be more suitable for applications, e.g., in the cloud radio access network (CRAN). The main signaling overhead for implementation is the exchange of channel information which is proportional to $N_u(N_m\!+\!N_s)$.

\begin{table}[t!]

\scriptsize

\setlength{\belowcaptionskip}{-10pt}
  \centering
  \caption{Simulation Parameters}\label{TABLE:parameter}
    \begin{tabular}{|c|c|c|c|}
  \hline

  Channel bandwidth & 10 MHz & Cell radius & 500 m \\
  \hline
  Max power of MBS & -27 dBm/Hz & Number of MBS & 1 \\
  \hline
  Max power of SBS & -47 dBm/Hz & Number of SBS & 3 \\
  \hline
  Circuit constant power & 1 W  & Number of users & 30 \\
  \hline

\end{tabular}
\end{table}

\begin{figure}[t!]
\setlength{\abovecaptionskip}{-5pt}
\centering
\includegraphics[width = 3.0in]{fig1.eps}
\caption{The percentage of MBS/SBS users for different association methods.}
\label{Fig:user percentage}
\vspace{-0.3cm}
\end{figure}
\begin{table}[t!]

\scriptsize

\newcommand{\tabincell}[2]{\begin{tabular}{@{}#1@{}}#2\end{tabular}}
\setlength{\belowcaptionskip}{-10pt}
  \centering
  \caption{Average UEE Comparison of Different Algorithms}\label{TABLE:UEE}
  \begin{tabular}{|c|c|c|c|c|}\hline
    & \tabincell{c}{Proposed \\ algorithm} & \tabincell{c}{Max-SINR \\ with power control} & \tabincell{c}{Max-SINR \\ with max power} \\ \hline
UEE & 35.392 & 29.982 & 1.490 \\ \hline
\end{tabular}
\end{table}

\section{Numerical Results}\label{sec:simulation}
In this section, we evaluate the performance of the proposed algorithm via simulation. Consider a downlink 2-tier HetNet with simulation parameters listed in Table \ref{TABLE:parameter}. The pathloss is modelled as $128.1+37.6\log_{10}d$(km), and the shadow fading is log-normally distributed as $\mathcal{N}(0,\sigma^2)$ where $\sigma=8$dB.

Fig. 1 compares the percentage of MBS/SBS users for different association methods. Note that the “SINR” in the Max-SINR association is evaluated with only large-scale channel fading, which is the same as the Max-SNR association in \cite{Chien2016Joint}. For the Max-SINR association, the MBS is overloaded with more than $90\%$ users, while the proposed association achieves balanced load. We also evaluate the performance of our iterative algorithm by comparing with existing methods. In our test, the number of iterations required for the convergence of outer loop is 5, and the optimal $\eta$ is obtained as 35.392. For a fixed $\eta$, the inner loop converges with 2 iterations. Table II compares the average UEE, and Fig. \ref{Fig:CDF2} plots the cumulative distribution function (CDF) of data rates. Our proposed algorithm is shown to perform well in terms of user fairness and throughput. Note that the Max-SINR with power control, which implements our proposed power control with traditional Max-SINR association, outperforms the Max-SINR with max power, proving the significance of power control to improve EE. Moreover, it has been observed that the proposed algorithm achieves near-global optimum via numerical exhaustive search under some small-scale test cases.

\section{Conclusion}\label{sec:conclusion}
In this letter, we jointly considered the user association and power control for HetNets. We formulated a UEE maximization problem and proposed an efficient algorithm. Results demonstrated the validity of our proposed algorithm. Note that the proposed algorithm can be readily extended to a massive MIMO scenario with subtle changes by scaling the SINR. Furthermore, to achieve better performance, the joint optimization with bandwidth allocation is of our future research interest.

\appendix
The dual method is implemented by iteratively solving the primal variables with fixed dual variables, and updating the dual variables with given optimization variables. First, we obtain the Lagrangian function of convex problem \eqref{eq:pro_rho_theta} as
\begin{align*}
\tag{19}
  &L(\bm{\rho},\bm{\theta},\bm{\omega},\bm{s},\bm{a},\bm{b},\bm{\zeta},\bm{\chi})\nonumber\\
                =&\sum\limits_{j\in \mathbb{B}}\sum\limits_{i\in \mathbb{U}_j} \log\left(\log\left(1+{\rm e}^{\theta_{i}}\right)\right)-\eta\sum\limits_{j\in \mathbb{B}}{\rm e}^{\rho_{j}}\nonumber\\
                 &-\sum\limits_{j\in \mathbb{B}}\sum\limits_{i\in \mathbb{U}_j}a_{i}({\rm e}^{\omega_i}+\sum_{q\neq j}{\rm e}^{s_{ijq}}-1)\nonumber\\
                 &-\sum\limits_{j\in \mathbb{B}}b_{j}\left(\rho_{j}-\log P_{j}^{m}\right)-\sum\limits_{j\in \mathbb{B}}\sum\limits_{i\in \mathbb{U}_j}\zeta_{i}(\omega_i-\theta_{i}+\rho_{j}-\beta_{i})\nonumber\\
                 &-\sum\limits_{j\in \mathbb{B}}\sum\limits_{i\in \mathbb{U}_j}\sum\limits_{q\in \mathbb{B}, q\neq j}\chi_{ijq}(s_{ijq}-\theta_{i}+\rho_{j}-\rho_{q}-\gamma_{iq})\nonumber
\end{align*}
where $\bm{a}=\{a_{i}\}_{i\in \mathbb{U}_j}$, $\bm{b}=\{b_{j}\}_{j\in \mathbb{B}}$, $\bm{\zeta}=\{\zeta_{i}\}_{i\in \mathbb{U}_j}$, and $\bm{\chi}=\{\chi_{ijq}\}_{j\in \mathbb{B}, i\in \mathbb{U}_j, q\neq j\in \mathbb{B}}$ are dual variables associated with the corresponding constraints of \eqref{eq:pro_rho_theta}. Then the optimal solution to convex problem \eqref{eq:pro_rho_theta} should satisfy
\setcounter{equation}{19}
\begin{align}

\label{eq:partial_rho}  &\frac{\partial L}{\partial \rho_{j}}\!=\!-\eta {\rm e}^{\rho_{j}}-b_{j}-\sum\limits_{i\in \mathbb{U}_j}\zeta_{i}-\sum\limits_{i\in \mathbb{U}_j}\sum\limits_{q\in \mathbb{B}, q\neq j}\chi_{ijq}\\ \nonumber
&\quad\quad\quad+\sum\limits_{q\in \mathbb{B}, q\neq j}\sum\limits_{i\in \mathbb{U}_q}\chi_{iqj}=0, \\
\label{eq:partial_theta} &\frac{\partial L}{\partial \theta_{i}}\!=\!\frac{{\rm e}^{\theta_{i}}}{\left(1+{\rm e}^{\theta_{i}}\right)\log\left(1+{\rm e}^{\theta_{i}}\right)}+\zeta_{i}+\sum\limits_{q\in \mathbb{B}, q\neq j}\chi_{ijq} =0, \\
\label{eq:partial_omega} &\frac{\partial L}{\partial \omega_{i}}\!=\!-a_{i}{\rm e}^{\omega_i}\!-\!\zeta_{i}\!=\!0,\ \frac{\partial L}{\partial s_{ijq}}\!=\!-a_{i}{\rm e}^{s_{ijq}}\!-\!\chi_{ijq}\!=\!0.
\end{align}

In each iteration, we can calculate the primary variables with given Lagrangian multipliers. Define function $f(x)=\frac{{\rm e}^x}{(1+{\rm e}^x)\log(1+{\rm e}^x)}$, which is strictly decreasing by checking its first-order derivative. Denote $f^{-1}(x)$ as the inverse function of $f(x)$. From \eqref{eq:partial_rho}--\eqref{eq:partial_omega}, we obtain
\begin{align}
& \rho_{j}(t\!+\!1)\!=\!-\log \eta + \nonumber \\
&\quad \quad \quad \; \log(\!-\!b_{j}(t)\!\!-\!\!\sum\limits_{i\in \mathbb{U}_j}\zeta_{i}(t)\!\!-\!\!\sum\limits_{q\neq j}(\sum\limits_{i\in \mathbb{U}_j}\chi_{ijq}(t)\!\!-\!\!\sum\limits_{i\in \mathbb{U}_q}\chi_{iqj}(t))), \nonumber \\

& \theta_{i}(t\!+\!1)\!=\!f^{-1}(-\zeta_{i}(t)\!-\!\sum\limits_{q\in \mathbb{B}, q\neq j}\chi_{ijq}(t)),  \nonumber \\
\label{eq:omega} & \omega_{i}(t\!+\!1)\!=\!\log(-\zeta_{i}(t)/a_{i}(t)),\, s_{ijq}(t\!+\!1)\!=\!\log(-\chi_{ijq}(t)/a_{i}(t)). \nonumber
\end{align}

Alternately, the dual variables are updated as follows:

\begin{equation}
\left\{
         \begin{array}{lr}
         a_{i}(t\!+\!1)\!=\!\left[a_{i}(t)\!+\!\delta^{(t)}\left({\rm e}^{\omega_i(t)}\!+\!\sum_{q\neq j}{\rm e}^{s_{ijq}(t)}\!-\!1\right)\right]^+\nonumber \\
         b_{j}(t\!+\!1)\!=\!\left[b_{j}(t)\!+\!\delta^{(t)}\left(\rho_{j}(t)\!-\!\log P_{j}^{m}\right)\right]^+ \nonumber\\
         \zeta_{i}(t\!+\!1)\!=\!\zeta_{i}(t)\!+\!\delta^{(t)}\left(\omega_i(t)\!-\!\theta_{i}(t)\!+\!\rho_{j}(t)\!-\!\beta_{i}\right)\\
         \chi_{ijq}(t\!\!+\!\!1)\!\!=\!\! \chi_{ijq}(t)\!+\!\delta^{(t)}\left(s_{ijq}(t)\!\!-\!\!\theta_{i}(t)\!\!+\!\!\rho_{j}(t)\!\!-\!\!\rho_{q}(t)\!\!-\!\!\gamma_{iq}\right)\nonumber
         \end{array}
    \right.
\end{equation}
where $\delta^{(t)}$ is the step size and $[x]^+$ returns $\max\{x$, $0\}$.
\begin{figure}[t!]
\setlength{\abovecaptionskip}{-5pt}
\centering
\includegraphics[width = 3.2in]{fig2.eps}
\caption{The CDF of data rates under different schemes.}
\label{Fig:CDF2}
\vspace{-0.5cm}
\end{figure}


TITLE: Simple question about the supremum of lebesgue integrals
QUESTION [3 upvotes]: Do we have the following equality?
Let $h$ be measurable and non-negative, $f$ another measurable function and $g$ a step-function, then:
$$\sup_g\left\{\int_X(fg)\,d\mu:0\leq g\leq h\right\}=\sup_g\left\{\int_Xg\,d\mu:0\leq g\leq fh\right\} $$
This seems obvious to me but I want to make sure that this is correct.
Any reasoning for an answer is welcome!

REPLY [1 votes]: Let $\mathcal{S}$ denote the set of simple finite measurable functions. That is, if $g \in \mathcal{S}$, then we have measurable sets $E_1, \cdots, E_n$ and positive real values $a_1, \cdots a_n$ such that
$$
g=\sum_{j=1}^n a_j \chi_{E_j}
$$
Now, observe that one of your sets it is actually the integral of $fh$, since by definition
$$
\int_X fh \ d\mu =\sup_{g \in \mathcal{S}} \left\{ \int_X g \ d\mu : 0 \leq g\leq fh\right\}
$$
$\bullet$ On one side, since $h$ is measurable and non-negative, it is a well known fact that there exist an increasing sequence on $\mathcal{S}$ converging to $h$, i.e. $\{\varphi_n\}\subset \mathcal{S}$ such that $\varphi_n \nearrow h$. Then we have one side of inequality between your sets because
$$
\sup_{g \in \mathcal{S}} \left\{ \int_X fg \ d\mu : 0 \leq g\leq h\right\} \geq \lim_{n \to \infty} \int_X f\varphi_n \ d\mu = \int_X fh \ d\mu
$$
where the inequality follows by the definition of supremum and the equality by the Monotone Convergence Theorem (MCT).
$\bullet$ On the other hand, to get the other side of the inequality assuming that $f$ is also non-negative, we find $\{ \psi_n \}_n \subset \mathcal{S}$ such that $\psi_n \nearrow f$. Applying a couple of times the MCT, using that $\{ \psi_n\}$ is an increasing sequence (IS), and that  that $\psi_n \geq 0$ (since $\psi_n \in \mathcal{S}$) (+), we get
\begin{align}
\sup_{g \in \mathcal{S}} \left\{ \int_X fg \ d\mu : 0 \leq g\leq h\right\} & \overset{(MCT)}{=} \sup_{g \in \mathcal{S}} \left\{ \lim_{n \to \infty} \int_X \psi_n g \ d\mu : 0 \leq g\leq h\right\} \\
& \overset{(IS)}{=} \lim_{n \to \infty} \sup_{g \in \mathcal{S}} \left\{ \int_X \psi_n g \ d\mu : 0 \leq g\leq h\right\} \\
& \overset{(+)}{=} \lim_{n \to \infty} \sup_{g \in \mathcal{S}} \left\{ \int_X \psi_n g \ d\mu : 0 \leq \psi_n g\leq \psi_n h\right\} \ \ \ \ \ \text{note here that $\psi_ng \in \mathcal{S}$} \\
& \leq \lim_{n \to \infty} \sup_{p \in \mathcal{S}} \left\{ \int_X p \ d\mu : 0 \leq p \leq \psi_n h\right\} \\
& \overset{def}{=} \lim_{n \to \infty}  \int_X \psi_n h \ d\mu \\
& \overset{(TMC)}{=} \int_X fh \ d\mu
\end{align}
Then indeed the other inequality holds and hence your claims follows.


TITLE: Strain energy stored in the rod
QUESTION [2 upvotes]: Question:
A uniform rod of length l, young's modulus Y and cross section A, placed on a smooth horizontal table, is pulled by a force F applied parallel to the rod at one end. The other end of the rod is free. Find the strain energy stored in the rod.
My attempt:
If the table was rough(i.e.,had friction), the static friction force would have adjusted itself to match the external force F and hence two equal and opposite forces would have caused stress to occur in the rod. But here the table is smooth, so I don't know what other force will oppose the external force and how stress will be produced.
I'm not sure of this but if I assume that atomic force of attraction would oppose the external force and the rod is reduced to the center of mass(at a distance of $\frac{l}{2}$), the following strain energy would be stored in the rod:-
$$U=\frac{1}{2Y}(stress)^2A\frac{l}{2}$$
$$U=\frac{1}{2Y}(\frac{F}{A})^2A\frac{l}{2}$$
$$U=\frac{F^2l}{4YA}$$
The answser is given as $U=\frac{F^2l}{6YA}$

REPLY [0 votes]: I can’t stand that this still hasn’t been solved in five years. Lol

The rod is being accelerated. The tension $T=\frac{z}{L}F$.
Set mass per unit length $q:= m/L$ , $a = F/ m$
A small section $dz$:
$$F’ = ma = qadz = \frac{m}{L}~ \frac{F}{m} ~ dz~ = ~\frac{F}{L} ~ dz$$
Check (accelerating force from differential tension):
$$F’ = T_R-T_L = dT = \frac{dz}{L} F$$
Strain energy in $dz$: $U_{dz}= \frac{T^2dz}{2YA}$
$$U=\int_{0}^L  \frac{T^2dz}{2YA}= \frac{F^2}{2L^2YA} \int_{0}^L  z^2dz$$
$$= \frac{F^2}{2L^2YA} \frac{L^3}{3} = \frac{F^2L}{6YA}$$
Which is the Answer Given


TITLE: What is the relation between topological entropy and Lyapunov exponent?
QUESTION [0 upvotes]: In this post, topological entropy is defined. In this book, the notion of Lyapunov exponent for, let's say a self-diffeomorphism from a smooth, closed Riemannian manifold to itself, is defined (in terms of the eigenvalues/singular values of the Jacobian matrix).
How are they related? Is the topological entropy of a self-diffeo $T: M \to M$ simply the maximum Lyapunov exponent over all $x \in M$?
Thanks in advance.
UPDATE: Is this true: The topological entropy of $T = \tilde{\Phi}_{t=1}$, and therefore $\xi$, is the sup over all measures on $M$ that $T$ leaves invariant of the integral over $M$ of the sum of the positive Lyapunov exponents of $T$, $\displaystyle \sup_{\nu \in \text{ Invar}(T)} \int_{M} \sum_{i=1}^{k}\lambda_k(x,v)\ d\nu$?

REPLY [2 votes]: Trying to understand what your notation means, in general you only have
$$
h(f)\le \sup_{\nu} \int_{M} \sum_{i=1}^{k(x)}\lambda_{k(x)}(x)\ d\nu(x)
$$
(really it is a bad idea to use $h$ for the map). This follows from the Margulis–Ruelle inequality.
The supremum runs over all $f$-invariant probability measures and the sum is over all positive Lyapunov exponents $\lambda_1(x)\le\cdots \le\lambda_{k(x)}(x)$ (unfortunately $k(x)$ may indeed depend on $x$).
But if $f$ is a $C^{1+\alpha}$ diffeomorphism and $\nu$ is absolutely continuous with respect to the volume, then
$$
h_\nu(f)= \int_{M} \sum_{i=1}^{k(x)}\lambda_{k(x)}(x)\ d\nu(x).
$$
This is Pesin's entropy formula. Therefore, under the same assumptions,
$$
h(f)\ge \int_{M} \sum_{i=1}^{k(x)}\lambda_{k(x)}(x)\ d\nu(x),
$$
although you cannot add a supremum in general. However, if $\nu$ is also a measure of maximal entropy you obtain
$$
h(f)= \int_{M} \sum_{i=1}^{k(x)}\lambda_{k(x)}(x)\ d\nu(x)
$$
and so also
$$
h(f)= \sup_{\nu} \int_{M} \sum_{i=1}^{k(x)}\lambda_{k(x)}(x)\ d\nu(x).
$$
Of course, all depends exactly on what you are assuming. Up to some technicalities on the $C^{1+\alpha}$  assumption this is the most general answer that you can get under general assumptions.


TITLE: Determining the number of values required to find the probabilities of a set of values
QUESTION [0 upvotes]: Im trying to estimate when a random function with a set number of events will trend to its probability values and a ballpark on how much data I need to collect will help.
Is there an equation that says:
Given X number of possible events in a set; you can determine the probability of each event in that set using Y number of outcomes?
For example; if you had 2 possible events E1 and E2, you could need at least Y outcomes to statistically estimate the probability of both E1 and E2?
Is there any significance between probabilities in a set that would affect Y? For example, you would expect more outcomes are required to show that E1 has a probability of 2% than if it was 50%.

REPLY [0 votes]: The usual equation for sample size is
  $$ n =  (z^*/m)^2 p(1-p)$$
where $m$ is the desired "margin of error" and $z^*$ is a factor close to 2. So, for small $p$ you need smaller $n$ to get the same absolute margin of error.


TITLE: Dealing with questions on vectors and matrices with variables
QUESTION [1 upvotes]: I'm running into a lot of questions on linear algebra lately where, instead of using constant numbers in matrices and vectors (these are questions which I have no problems in answering), they use a mix of constants and a variable a. I'm finding these difficult to answer. For example:
For each value of a, find the rank and nullity of the matrix, v1=(a,a,a), v2=(0,1,2) v3=(1,0,-1). I understand rank and nullity but again, I'm thrown off by what is being asked regarding a. If a=0 then the rank is 2 and nullity is 1, correct? Then if a>0, we need to perform additional row operations to reduce to row echelon form. But this can't be done with a variable? I'm mostly having trouble with how I could express the answer correctly considering the inclusions of the variable a. I'm only used to answering LA questions on problems with constants so this has thrown me off.
In general, how can I deal with questions of this type?

REPLY [0 votes]: Let's say we are interested in the matrix whose rows are $v_1, v_2, v_3$ (it doesn't really matter as $\mathrm{rank} A = \mathrm{rank} A^T$ so we could as well put them as columns). Thus,
$$ A = \begin{pmatrix} a & a & a \\ 0 & 1 & 2 \\ 1 & 0 & -1 \end{pmatrix}. $$
Instead of handling immediately the case where $a \neq 0$ and $a = 0$, I suggest that you delay it by replacing the third row with the first row, leading to
$$ A' = \begin{pmatrix} 1 & 0 & -1 \\ 0 & 1 & 2 \\ a & a & a \end{pmatrix}. $$
By subtracting $a \times $ the first row from the third row, we obtain
$$ A'' =  \begin{pmatrix} 1 & 0 & -1 \\ 0 & 1 & 2 \\ 0 & a & 2a \end{pmatrix}.$$
Continuing with the second row, we subtract $a \times $ the second row from the third row and obtain
$$ A '' = \begin{pmatrix} 1 & 0 & -1 \\ 0 & 1 & 2 \\ 0 & 0 & 0 \end{pmatrix}. $$
Now it is clear that $A''$ has rank two no matter what $a$ is. In general, you won't be able to avoid case analysis but you can delay it so that expressions involving the parameter will appear only in the last rows which will make the analysis easier.


TITLE: Find the required probability.
QUESTION [0 upvotes]: Two balls are drawn from an urn containing $m$ balls numbered from $1$ to $m$ . The first ball is kept if it is numbered 1 and returned to the urn otherwise. What is the probability that the second ball drawn is numbered 2?

REPLY [1 votes]: You can add up the two cases. The first gives $\frac{1}{m}\frac{1}{m-1}$, since the first ball is kept. The second gives $\frac{m-1}{m}\frac{1}{m}$. Hence the probability is
$$ P = \frac1m\left(\frac{1}{m-1}+\frac{m-1}{m}\right) = \frac{1}{m}+\frac{1}{m^2(m-1)}. $$


text:
\setcounter{figure}{0}
\renewcommand{\thefigure}{D\arabic{figure}}

\section{Our results on MNIST} \label{sec:appx_mnist}

We consider all 10 classes of MNIST. To decompose the images, we choose Daubechies-1 wavelet basis. More information about the data is presented in Appendix~\ref{sec:appx_data}. We also use $m=100$ which satisfies the full rank requirement for all classes.

{\bf Patterns in the dataset.}
Again, we use the Higher Order GSVD as our spectral decomposition method. Figure~\ref{fig:mnist_rightbasis} shows the images reconstructed from the first 9 columns of the right basis, $V$.

\begin{figure}[H]
  \centering
   \includegraphics[width=0.08\linewidth]{fig_rightb_1.png}
   \includegraphics[width=0.08\linewidth]{fig_rightb_2.png}
   \includegraphics[width=0.08\linewidth]{fig_rightb_3.png}
   \includegraphics[width=0.08\linewidth]{fig_rightb_4.png}
   \includegraphics[width=0.08\linewidth]{fig_rightb_5.png}
   \includegraphics[width=0.08\linewidth]{fig_rightb_6.png}
   \includegraphics[width=0.08\linewidth]{fig_rightb_7.png}
   \includegraphics[width=0.08\linewidth]{fig_rightb_8.png}
   \includegraphics[width=0.08\linewidth]{fig_rightb_10.png}
  \caption{Images reconstructed from individual columns of the right basis $V$.}
  \label{fig:mnist_rightbasis}
\end{figure}

{\bf Singular values and association of patterns to classes.}
Figure~\ref{fig:mnist_singulars1} shows the first 20 singular values for all classes, and Figure~\ref{fig:mnist_singulars2} shows the second 20 singular values, i.e., singular values 21 through 40.

\begin{figure}[H]
     \centering
     \begin{subfigure}[b]{0.44\textwidth}
         \centering
         \includegraphics[width=.7\linewidth]{fig_mnist_singulars.png}
         \caption{Singular values 1 through 20}
         \label{fig:mnist_singulars1}
     \end{subfigure}
     \hspace{-1.8cm}
     \begin{subfigure}[b]{0.48\textwidth}
        \centering
        \includegraphics[width=.7\linewidth]{fig_mnist_singulars_2.png}
         \caption{Singular values 21 through 40}
         \label{fig:mnist_singulars2}
     \end{subfigure}
        \caption{Log of singular values for all classes of MNIST. Some singular values are dominant for a particular class and some of them are dominant for more than one class.}
        \label{fig:mnist_singulars}
\end{figure}

{\bf Interpreting the patterns.}
Consider the images for columns 7 and 8 of right basis, reconstructed in Figure~\ref{fig:mnist_rightbasis}. One could rationalize that they represent distinctive features for classes of 4,7, and 9, because those patterns have a vertical stroke at the bottom of image and they all have some vague content at the center. Looking at the singular values (columns 7 and 8 in Figure~\ref{fig:mnist_singulars2}), reveals that the dominant singular values are exactly those digits (4, 7, and 9).

Let's consider the 32nd singular value which seems to be relatively similar for all classes, i.e., the column 32 in Figure~\ref{fig:mnist_singulars2}. The image reconstructed from the 32nd column of right basis, $V$, is shown in Figure~\ref{fig:mnist_rightbasis2} (left), which seems to be a general basis, not distinctive for any particular digit. Now, lets' consider the 50th column in $V$ where its reconstruction is shown in Figure~\ref{fig:mnist_rightbasis2} (right). The dominant singular values for this class are classes 5 and 8, which seems to correspond to the distinctive patterns one would expect for digits 5 and 8.

\begin{figure}[H]
  \centering
   \includegraphics[width=0.1\linewidth]{fig_rightb_32.png}
   \includegraphics[width=0.1\linewidth]{fig_rightb_50.png}
  \caption{Images reconstructed from individual columns of the right basis $V$.}
  \label{fig:mnist_rightbasis2}
\end{figure}

{\bf Left basis interpretation.}
Now, let's consider the left basis for digit 1. The three images with the largest norm in the left basis are shown in Figure~\ref{fig:mnist_notsimple}. On the other hand, the images with the smallest norm in the left basis are shown in Figure~\ref{fig:mnist_simple}. Clearly, the simple images that one would consider straightforward to reconstruct or classify are the ones with small norm in left basis, and vice versa.

\begin{figure}[H]
     \centering
     \begin{subfigure}[b]{0.49\textwidth}
      \centering
       \includegraphics[width=0.18\linewidth]{fig_simple_cl2_tr5843.png}
       \includegraphics[width=0.18\linewidth]{fig_simple_cl2_tr51545.png}
       \includegraphics[width=0.18\linewidth]{fig_simple_cl2_tr4503.png}
      \caption{}
      \label{fig:mnist_notsimple}
     \end{subfigure}

     \begin{subfigure}[b]{0.49\textwidth}
      \centering
       \includegraphics[width=0.18\linewidth]{fig_simple_cl2_tr17665.png}
       \includegraphics[width=0.18\linewidth]{fig_simple_cl2_tr2319.png}
       \includegraphics[width=0.18\linewidth]{fig_simple_cl2_tr16931.png}
      \caption{}
      \label{fig:mnist_simple}
     \end{subfigure}
        \caption{\textbf{(a)} Images that have the largest norm in left basis are made from many patterns and seem atypical. \textbf{(b)} Images that have a small norm in left basis are simple to reconstruct from the patterns.}
        \label{fig:mnist_simple_complex}
\end{figure}

config: arxiv

file: 2006.09879/patterns in image classification/a4-mnist.tex


TITLE: Voronoi relevant vectors VS shortest vector
QUESTION [0 upvotes]: Let $L$ be an $n$-dimensional lattice with its Voronoi cell $\mathcal{V}$ is then defined as the set $\{x\in \mathbb R^n:|x|\le |x-v|, \mbox{ for all }v\in L\}$. A vector $v$ is called a Voronoi relevant vector if the hyperplane $\{x:\in \mathbb R^n:\langle x,v \rangle=|v|^2/2\}$ has an intersection with an $(n-1)$-dimensional face of $\mathcal{V}$.
If we take an arbitrary point $\lambda \in L$ that is not Voronoi relevant, can we always find a Voronoi relevant vector $v$ such that $||v|| < ||\lambda||$?

REPLY [0 votes]: No. In your picture, take $\lambda = (3/4)v$.
Your choice of vocabulary is a little confusing. Among other things, when you use roman letters for vectors, I expect $\lambda$ to be a scalar.
Here is what I think you mean.
You have a Voronoi tessellation determined by a set $L$ of points one of which is the origin. The cell $S$ containing the origin has facets each of which is part of a hyperplane $H_v$  perpendicular to and bisecting some other vector $v \in L$. Those particular vertices $v$ are what you call "Voronoi relevant". They are the ones you have to look at to determine $S$.
Let $w$ be any nonzero vector. Then the ray $\alpha w$ meets the boundary of $S$ at some facet $H_v$ (perhaps more than one), Since $v/2$ is the  point on $H_v$ nearest the origin, you know
$$
| w | < |v/2| \iff w \in \text{ the interior of } S.
$$
If $w \not\in S$ then $|w| > |v/2|$ but you cannot guarantee any inequality stronger than that.


TITLE: About proof of theorem on topology
QUESTION [1 upvotes]: Theorem. If a convergent sequence in a metric space has infinitely many distinct points, then its limit is a limit point of the set of points of the sequence.

In the previous image is the proof of a theorem, may question is about the information used to reach absurd, is told that since x is in the sequence, the sequence should have only finitely many distinct a points, but this necessarily true? If we have like all {$x_n$} being distinct a points, for example n being negative integers, and all {$x_n$} being x, for all n being natural numbers, this is a convergent serie with limit x, and with infinitely many diferentes points, even do the aforementioned proof keep being true?
How may I proof it?

REPLY [0 votes]: (I). An equivalent, and often useful, way of saying that $(x_n)_n$ converges to $x$ in a metric space  $(X,d)$ is that for every nbhd $U$ of $x,$ the set $\{n:x_n\not \in U\}$ is finite:
(i). If $(x_n)_n$ converges to $x,$ and $U$ is  a nbhd of $x,$ then $B_d(x,r)\subset U$ for some $r>0.$  And there exists $n_0$ such that $\forall n>n_0\; ( d(x,x_n)<r) .$ So $$\{n:x_n\not \in U\}\subset \{n:x_n \not \in B_d(x,r)\subset \{n:n\leq n_0\}.$$
(ii). If $\{n: x_n\not \in U\}$ is finite for every nbhd  $U$ of $x$ then for every $r>0$ the finite set $\{n:x_n\not \in  B_d(x,r)\}$ is a subset of $\{n:n\leq n_0\}$ for some $n_0\in \mathbb N.$  So there exists $n_0$ such that $\forall n>n_0 \;(x_n\in B_d(x,r)).$ Equivalently there exists $n_0\in \mathbb N $  such that $\forall n>n_0\;(d(x,x_n)<r).$
(II). Let $(x_n)_n$ converge to $x,$ such that $A=\{x_n: n\in \mathbb N\}$ is infinite.
If $U$ is any nbhd of $x$ then $\{n:x_n\not \in U\}$ is finite, so take $n_0$ such that $\forall n>n_0\;(x_n\in U).$
Since $A$ is infinite and $B=\{x_n:n\leq n_0\}$ is finite, the set $A$ \ $B=\{x_n:n>n_0\}$ is infinite so there exists some $n_1>n_0$   with $x_{n_1}\ne x.$ But $x_{n_1}\in \{x_n:n>n_0\}\subset U.$  Therefore every nbhd $U$ of $x$ contains a member of $A$ that is not equal to $x. $ Equivalently, $x$ belongs to the closure of $\{x_n:x_n\ne x\}.$


TITLE: Decomposition of edges of eulerian graph into maximum number of cycles
QUESTION [1 upvotes]: I'm interested in the following problem.
Given an eulerian graph $G=(V,E)$, we are to find a partition of its edges $C_1, C_2, \ldots, C_k$ ($\cup_i C_i=E$ and $i \neq j \leftrightarrow C_i \cap C_j = \varnothing$), such that each $C_i$ forms a simple cycle in $G$ and $k$ is maximum possible.
In other words, we are to cover every edge of an eulerian graph with a maximum number of edge-disjoint simple cycles.
Is this problem well-known? Is there a known approach to solve it?

REPLY [1 votes]: A special case of your problem - checking if there is an edge-partition of the graph into triangles - is shown to be NP-complete in this paper, where it is the $n=3$ case of the more general problem of edge-partitioning a graph into copies of $K_n$.
(If such an edge-partition exists, then it's definitely the best solution: any other way to partition the graph into cycles will use fewer cycles. So in some cases, solving your problem is at least as hard as solving the triangle edge-partition problem.)
This doesn't say much about how to solve the problem, but it does say that we shouldn't look for a polynomial-time algorithm. Maybe some sort of standard dealing-with-brute-force-search approaches such as branch-and-bound would work.


TITLE: Value of $\sum_{r= 0}^{2019}\sum_{k=0}^{r}(-1)^k.(k+1).(k+2).\binom{2021}{r-k} $
QUESTION [2 upvotes]: What is tried was : $\newcommand{\bbx}[1]{\,\bbox[8px,border:1px groove navy]{\displaystyle{#1}}\,}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\mc}[1]{\mathcal{#1}}
 \newcommand{\mrm}[1]{\mathrm{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$
\begin{align}
&\mbox{Note that inside summation is }\quad\left.
\sum_{k = 0}^{r}\pars{-1}^{k}\pars{k + 1}\pars{k + 2}{2021 \choose r - k}
\right\vert_{\ 2021\ >\ 3} =
\left.\partiald[2]{}{x}\sum_{k = 0}^{r}{2021 \choose r - k}x^{k + 2}
\right\vert_{\ x\ =\ -1}
\end{align}  , now how to simplfiy the summation part which needs to be double differentiated or there is some other method to solve for that summation value too ?

REPLY [4 votes]: In seeking to evaluate
$$\sum_{r=0}^n \sum_{k=0}^r
(-1)^k (k+1) (k+2) {n+2\choose r-k}$$
we write
$$2 \sum_{r=0}^n [z^r] (1+z)^{n+2}
\sum_{k=0}^r {k+2\choose 2} (-1)^k z^k.$$
The coefficient extractor enforces the range of the inner sum:
$$2 \sum_{r=0}^n [z^r] (1+z)^{n+2}
\sum_{k\ge 0} {k+2\choose 2} (-1)^k z^k
\\ = 2 \sum_{r=0}^n [z^r] (1+z)^{n+2}
\frac{1}{(1+z)^3}
= 2 \sum_{r=0}^n [z^r] (1+z)^{n-1}
\\ = 2 \sum_{r=0}^n {n-1\choose r}
= 2 \times 2^{n-1} = 2^n$$
where we have used $n\ge 1,$ for $n=0$ we find $2[z^0] (1+z)^{-1} = 2.$
Addendum. We may also change the order of summation as asked in the
comments to get
$$2 \sum_{k=0}^n {k+2\choose 2} (-1)^k
\sum_{r=k}^n {n+2\choose r-k}
= 2 \sum_{k=0}^n {k+2\choose 2} (-1)^k
\sum_{r=0}^{n-k} {n+2\choose r}
\\ = 2 \sum_{k=0}^n {k+2\choose 2} (-1)^k
[z^{n-k}] \frac{1}{1-z} (1+z)^{n+2}
\\ = 2 [z^n] \frac{1}{1-z} (1+z)^{n+2}
\sum_{k=0}^n {k+2\choose 2} (-1)^k z^k.$$
We once more have a coefficient extractor enforcing the upper limit
of the sum and we find
$$2 [z^n] \frac{1}{1-z} (1+z)^{n+2}
\sum_{k\ge 0} {k+2\choose 2} (-1)^k z^k
= 2 [z^n] \frac{1}{1-z} (1+z)^{n+2} \frac{1}{(1+z)^3}
\\ = 2 [z^n] \frac{1}{1-z} (1+z)^{n-1}
= 2 \sum_{r=0}^{n-1} {n-1\choose r} = 2 \times 2^{n-1} = 2^n.$$
Here we see that keeping the original order of the two summations was
the better method moreover no new features appeared on changing the
order.


TITLE: Real Analysis Sets example
QUESTION [1 upvotes]: The problem: Come up with an example of sets
$A$, and $B$ in $\mathbb{R}^2$ such that $A \subset B$, $A \neq B$, and the boundary points of $A$, $bd(A) = B$.
Here is what I think. I was going to set $A = \{ \bar{u} \in \mathbb{R}^2 | \|u \| =1 \} $ and $B = \{ \bar{u} \in \mathbb{R}^2 | \| u \| \leq 1 \}$ but I cannot think of good examples.
Can someone give me some hints please? Try not to solve the problem!
Thank you very much!!

REPLY [0 votes]: Take $B = \{ \bar{u} \in \mathbb{R}^2 | \|u \| =1 \}$ and remove any countable number of points you wish from $B$ to get $A$.
By countable, I mean finite or countably infinite.


text:
\section{Computational Study}\label{sec:computational_study}

In this section, we empirically evaluate the proposed approximation schemes. The goal is to understand their practical performance for different classes of instances and compare them with the following trivial assortment families: \emph{(i)} all suppliers appear in the menu of each consumer, denoted by $V^N$; \emph{(ii)} a randomly generated assortment, denoted by $R_1$, where each pair consumer-supplier is included independently with probability $1/2$ (for the cardinality constrained problem, we limit the size); and (iii) a randomly generated assortment, denoted by $R_2$, where each pair consumer-supplier is included independently with probability $1/2$ and whose size is determined by the solution of the main algorithm that is being analized.

\subsection{Instance Design and Implementation}
We restrict our attention to MNL models, namely, we consider consumers and suppliers who follow the multinomial logit model. In Table~\ref{table:instances}, we detail the generation of the public scores; recall from Section~\ref{sec:related_work} the notation $v_{ij}$ for consumer $i$'s public scores and, analogously, denote $u_{ji}$ for supplier $j$'s public scores. Overall, we consider the following models:
\begin{enumerate}
\item Instances {\easyinst} serve the purpose of validating the approach described for easy-to-match consumers of Section~\ref{sec:easytomatch}, Algorithm~\ref{theorem:main_general1}. Concerning the suppliers, we consider them to follow the MNL model with public scores less than 1. To solve the submodular welfare problem, we implement the standard greedy algorithm instead of the continuous version; as mentioned in Section~\ref{sec:easytomatch}, the guarantee in this case worsens to $1/4$.
\item Through the remaining instances, inspired by the ones simulated in~\citep{ashlagi_etal19} for non-easy-to-match consumers, we analyze the methodologies described in Section~\ref{sec:general_case}. In particular, instances {\etaleasy} and {\general} allow us to see the effect of having consumers with the same and different scores for the suppliers, respectively, while instances {\generalcard}  highlight the value of Algorithm~\ref{alg:cardinality} under cardinality constraints. For the cardinality budget, we consider $K_i = K$ for all $i\in N$ with $K\in\{5,10,25\}$.
\end{enumerate}

 For each set of instances, we consider $m=100$ suppliers, revenues $r_j=1$ for all $j\in V$ (max-cardinality objective) and 25 random instances for each $n \in \lbrace 50,75,100,125,150,200 \rbrace$, where $n$ is the number of consumers. Since the objective function corresponds to the expected cardinality of the matching, we obtain the empirical average by running 1,000 simulations for each tested assortment family. Also, given that our results are in expectation with respect to the randomization of the rounding techniques, we sample 10 solutions in each instance and we average their expected cardinality objective.  Finally, as in \citep{ashlagi_etal19}, we consider the relaxation of Problem \ref{eq:aux_problem} as upper bound for the true optimal value of our problem. We also provide a second upper bound obtained from the solutions of the concave problems \eqref{eq:mnlmnl_concave_unconstrained} and \eqref{eq:mnl_concave_card}, which is possible since suppliers follow the MNL model; recall the discussion in Section \ref{sec:heuristic}. Both bounds were computed in practice by considering their conic reformulations; \eqref{eq:mnlmnl_concave_unconstrained} and \eqref{eq:mnl_concave_card} have no integrality requirements, so the conic formulation is equivalent.

 To summarize, for each set of instances, we tested the following:
 \begin{itemize}
 \item For the instances \easyinst, we tested our main Algorithm \ref{alg:easy_to_match} (with the standard greedy) and also Algorithm \ref{alg:mnl_concave_unconstrained}, which is the heuristic for the MNL-MNL model discussed in Section \ref{sec:heuristic}. We also obtain both upper bounds and the three benchmarks: $V^N$, $R_1$ and $R_2$, where the size $R_2$ is determined by the greedy solution.
 \item For the instances \etaleasy \ and \general, we tested our main Algorithm \ref{alg:lp_unconstrained} and also Algorithm \ref{alg:mnl_concave_unconstrained}, which is the heuristic described in Section \ref{sec:heuristic}. We also obtain both upper bounds and the three benchmarks: $V^N$, $R_1$ and $R_2$, where the size $R_2$ is determined by the rounded solution obtained from Algorithm \ref{alg:lp_unconstrained}.
\item For the instances \generalcard, we tested our main Algorithm \ref{alg:cardinality} and also Algorithm \ref{alg:mnl_mnl_cardinality}. We only compute the upper bound given by Problem \eqref{eq:mnl_concave_card} and, since we have cardinality constraints, we only consider $R_1$ as a benchmark.
 \end{itemize}

\begin{table}[ht]
    \centering
    \caption{Summary of the instances.}
\label{table:instances}
\begin{tabular}{|l|HHccc|}\hline

 Set of instances & $|N|$ & $|V|$ & Consumers' scores & Suppliers' scores & $K_i$\\ \hline
\easyinst &$\lbrace 50,75,100,125,150,200 \rbrace$ & 100 & $v_{i0}=1$, $v_{ij}$&$u_{j0}=1$,$u_{ji}$&\\
& & & $V_{ij} \sim \mathcal{U}(1,5)$&$U_{ji} \sim \mathcal{U}(0.01,1)$ &\\\hdashline

\etaleasy & $\lbrace 50,75,100,125,150,200 \rbrace$ & 100 &$v_{i0}=1$, $v_{ij}=\frac{1}{1+z_j}$ & $u_{j0}=\frac{1}{1+w_j}$,$u_{ji}=1$ &\\
    &                                         &     &$Z_{j} \sim Exp(\lambda_v), \lambda_v\in \{1,10\} $ & $W_j\sim Exp(\lambda_0), \lambda_0\in \{1,10\}$&\\\hdashline
\general  & $\lbrace 50,75,100,125,150,200 \rbrace$ & 100 &$v_{i0}=1$,$v_{ij}=\frac{1}{1+z_{ij}}$ & $u_{j0}=\frac{1}{1+w_j}$,$u_{ji}=1$ &\\
     &                                         &     &$Z_{ij} \sim Exp(\lambda_v), \lambda_v\in \{1,10\} $ & $W_j\sim Exp(\lambda_0), \lambda_0\in \{1,10\}$&\\ \hdashline
\generalcard  & 200  & 100 & \multicolumn{2}{c}{{\general} with $\lambda_v=\lambda_0=1$} & $\lbrace 5,10,25\rbrace$\\ \hline
\end{tabular}
\end{table}

\subsection{Discussion of Results}

Figure~\ref{fig:easytomatch} and the associated Table~\ref{tab:easytomatchconsumers} in Appendix \ref{sec:tables} allow us to evaluate Algorithm~\ref{alg:easy_to_match} and Algorithm \ref{alg:mnl_concave_unconstrained} when consumers are easy-to-match. These results immediately show that our algorithm achieves  non-trivial assortments as it is able to steadily  provide significantly better results than $V^N$, $R_1$ and $R_2$. Moreover, the gap with the upper bound is much lower than the approximation guarantee given by Theorem~\ref{theorem:main_general1}. Observe that this gap is even closer when we consider the upper bound given by Problem \eqref{eq:mnlmnl_concave_unconstrained} and the solution obtained by Algorithm \ref{alg:mnl_concave_unconstrained}. Assortments $V^N$ and  $R_1$ have almost the same performance, which may suggest that the objective function does not variate much when the assortments are relatively dense. For this type of instances, the sparse assortments given by Algorithm~\ref{alg:easy_to_match} and  Algorithm \ref{alg:mnl_concave_unconstrained} perform much better; recall, for example, that Algorithm~\ref{alg:easy_to_match} outputs assortments of size at most 1. However, not every sparse assortment performs well as shown by the weak performance of $R_2$.

\begin{figure}[h]
     \centering
\includegraphics[scale=0.5]{easytomatch1.eps}
    \caption{Comparison for {\easyinst}.}
      \label{fig:easytomatch}
\end{figure}

Figures~\ref{fig:etaleasy} and \ref{fig:etal_general}, with their associated Tables~\ref{tab:etaleasy} and~\ref{tab:general} in Appendix \ref{sec:tables}, enable the empirical evaluation of Algorithm~\ref{alg:lp_unconstrained} and Algorithm \ref{alg:mnl_concave_unconstrained}. Here, we observe that when  consumers have different choice models, the assortments computed by our method have a smaller gap with respect to the upper bound; for example, see Figures \ref{fig:etaleasy}~(a) and \ref{fig:etal_general}~(a). Additionally, it can be concluded that when consumers are non easy-to-match, showing all suppliers is generally a good strategy. This behavior may be explained by the fact that the objective function does not variate much under dense assortments.

Observe in Figures~\ref{fig:etaleasy} that the performance of Algorithm~\ref{alg:lp_unconstrained} does not improve after $n=100$. One possible explanation for this behavior is that the optimal solution of \eqref{eq:main_lp} is attained when $z^*_j = 1$ for all $j\in V$. Namely, if $n\geq 100$, then any sufficiently dense assortment family will
satisfy $z_j\geq 1$ for all $j\in V$. This implies that \eqref{eq:main_lp} has multiple optimal solutions, but in the experiments, the LP \eqref{eq:main_lp} outputs the sparsest one, whose performance does not change with $n>100$. In other words, the objective $\min\{1,z_j\}$ ``saturates fast'' as $z_j$ approaches to 1. On the other hand, Algorithm \ref{alg:mnl_concave_unconstrained} does not have this behavior. This is because the objective function in Problem \eqref{eq:mnlmnl_concave_unconstrained} is of the form $z_j/(z_j+q_j)$ which ``smoothly'' approaches to 1 as $z_j$ grows, contrasting $\min\{1,z_j\}$. Therefore, the smooth objective is able to differentiate between dense and sparse solutions when $z_j\geq 1$. We can see a similar behavior in Figures \ref{fig:etal_general}.

\begin{figure}
\centering
\begin{tabular}{cc}
\hspace{-3.5em}\includegraphics[scale=0.45]{easyetal1.eps}&
\includegraphics[scale=0.45]{easyetal2.eps}\\
(a) & (b) \\
\includegraphics[scale=0.45]{easyetal3.eps}&
\includegraphics[scale=0.45]{easyetal4.eps}\\
(c) & (d)
\end{tabular}
\caption{Comparison for {\etaleasy}. Parameters: (a) $\lambda_v=\lambda_0 =1$; (b) $\lambda_v=1, \lambda_0 =10$; (c) $\lambda_v=10, \lambda_0 =1$; (d) $\lambda_v=\lambda_0 =10$. }
\label{fig:etaleasy}
\end{figure}

\begin{figure}
\centering
\begin{tabular}{cc}
\hspace{-3.5em}\includegraphics[scale=0.45]{general1.eps} &
\includegraphics[scale=0.45]{general2.eps}\\
(a) & (b) \\
\includegraphics[scale=0.45]{general3.eps} &
\includegraphics[scale=0.45]{general4.eps}\\
(c) & (d)
\end{tabular}
\caption{Comparison for {\general}. Parameters: (a) $\lambda_v=\lambda_0 =1$; (b) $\lambda_v=1, \lambda_0 =10$; (c) $\lambda_v=10, \lambda_0 =1$; (d) $\lambda_v=\lambda_0 =10$.}
\label{fig:etal_general}
\end{figure}

\begin{figure}
     \centering
     \begin{tabular}{cc}
   \hspace{-3.5em}  \includegraphics[scale=0.45]{general_card1.eps} &
\includegraphics[scale=0.45]{general_card2.eps}\\
(a) & (b) \\
\multicolumn{2}{c}{
\includegraphics[scale=0.45]{general_card3.eps} }\\
\multicolumn{2}{c}{(c) }
\end{tabular}
    \caption{Comparison for {\generalcard}. Budgets: (a) $K_i = 5$; (b) $K_i = 10$; (c) $K_i = 25$. }
      \label{fig:general_card}
\end{figure}

Note that the trend of the experiments for {\etaleasy} and {\general} does not change for different combinations of $\lambda_v$ and $\lambda_0$: as the number of consumers increases, $V^N$ as well as $R_1$ are likely to be a good choice. For this reason, we restricted to one combination of values for $\lambda_v$ and $\lambda_0$ for the experiments presented in Figure~\ref{fig:general_card} and the associated Table~\ref{tab:generalcard} in Appendix \ref{sec:tables}. Contrary to the unconstrained case, a random assortment  is not anymore likely to result in a good assortment. Under this case, the value of Algorithms~\ref{alg:cardinality} and  \ref{alg:mnl_mnl_cardinality} are highlighted. In these experiments, we can observe the effect of the size of the assortment family. Note that when $K_i = 5$, the random solution is significantly worse compared to our algorithm. However, when $K_i = 25$, this gap shrinks which may imply that for large cardinality budgets, the structure of the menu is not particularly relevant. This does not imply that the quality with respect to the optimal assortment family is good, but the difference in value among dense assortments is not considerable.

Detailed results of our simulations are presented in Tables~\ref{tab:easytomatchconsumers}-\ref{tab:generalcard} in Appendix \ref{sec:tables}, where average and standard deviation values for the expected number of matchings are provided.


TITLE: Inducing a model structure using a cosimplicial object
QUESTION [7 upvotes]: In a recent paper, Hiroshi Kihara induced a model structure on the category of diffeological spaces. He generates the classes of fibrations, cofibrations, and weak equivalences by constructing a functor $d:\Delta \to \mathcal{D}$ (where $\mathcal{D}$ is the category of diffeological spaces, and $\Delta$ is the simplex category), horns $\Lambda^p_k$ are constructed as smooth deformation retracts of the cells $\Delta^p$. Weak equivalences are those maps $f:X \to Y$ so that the $d$-nerve $N_d(f) = \mathcal{D}(d-,f)$ is a weak equivalence of simplicial sets, and using the set of horn inclusions $\Lambda^p_k \to \Delta^p$ as the generating cofibrations.
Based on the results claimed in this arxiv preprint, it seems like he is using the nerve of the functor $d: \Delta \to \mathcal{D}$ to transfer the model structure from simplicial sets to differential objects. This makes me think that there is some notion of a "good enough" cosimplicial object that induces a model structure on a category (somewhat similar to how tangent category can be encoded as a nice functor from $\mathsf{Weil}^{op}$ into a cartesian closed category $\mathcal{E}$).

REPLY [6 votes]: A somewhat general statement along these lines would be as follows. Suppose $\mathcal{D}$ is a cartesian closed locally presentable category and $d : \Delta \to \mathcal{D}$ is a cosimplicial object with associated geometric realization adjunction $|{\cdot}| : \mathrm{sSet} \to \mathcal{D}$, satisfying the following properties.

The maps $|\Lambda^n_k| \to |\Delta^n|$ have retracts for each $n \ge 1$ and $0 \le n \le k$.
Then $\mathrm{Sing} X$ is a fibrant simplicial set for any $X \in \mathcal{D}$, so every object will be fibrant in the transferred model structure.

The functor $|{\cdot}|$ preserves finite products.
Then $X^{|\Delta^1|}$ is a path object for $X = X^{|\Delta^0|}$, for any $X \in \mathcal{D}$.

This is enough to ensure that the transferred model structure exists, as described on the nLab.
In fact, this is essentially how Quillen originally constructed the classical model structure on Top--except that the category of all topological spaces does not quite satisfy most of these conditions; but it comes close enough for similar arguments to go through.
Of course condition 1 (and to a lesser extent, condition 2) is far from formal, and the kinds of model structures produced in this way are rather special.
As a trivial example, the Yoneda embedding $\Delta \to \mathrm{sSet}$ doesn't satisfy condition 1 (otherwise it would be automatic!) but obviously the model category structure on $\mathrm{sSet}$ can still be transferred across the identity functor.
We can be somewhat more precise about which model categories can be constructed by a variation of the above argument. Condition 1 is equivalent to every object of the transferred model structure being fibrant, because if $|\Lambda^n_k|$ is fibrant then the acyclic cofibration $|\Lambda^n_k| \to |\Delta^n|$ must have a retraction. Condition 2 is basically meant to ask for a simplicial structure on $\mathcal{D}$ to use for building path objects. One way to get this, not necessarily the only one, is for $\mathcal{D}$ to be cartesian closed and set $K \otimes X = |K| \times X$, and ask for $|{\cdot}|$ to preserve finite products. So, the model categories that can be built in this way are the simplicial ones transferred along a simplicial adjunction $\mathrm{sSet} \rightleftarrows \mathcal{D}$ with every object fibrant.
Having looked at the referenced paper more closely, it seems that the geometric realization functor considered there does not preserve finite products. Instead the acyclicity condition is checked in another way using deformation retracts, analogous to Lemma 2.4.8 in Mark Hovey's book. I'm not aware of a general framework for this kind of argument but it does seem relatively formal as well.


TITLE: Definition of "equally likely" in statistical mechanics
QUESTION [2 upvotes]: The text I am currently reading (Concepts in Thermal Physics by Blundell) states that,

A system will appear to choose a macroscopic configuration which maximizes the number of microstates.

And that this idea is based on the following assumption:

Each one of the possible microstates of a system is equally likely to occur.

I have trouble understanding what it precisely means for two microstates to be "equally likely." I have a guess as to what it means but I am not sure. My guess was that, given that the system changes its microstate continuously in time, the system spends equal time in each microstate in the long run. So in this case, "equally likely" implies equal long-term frequency for each of the microstates. This would imply that the macrostate that the system spends the most time in is the one that contains the greatest number of microstates. Is this correct meaning of "equally likely" in this context? If not, what does it precisely mean for each one of the possible microstates to be equally likely?

REPLY [2 votes]: Suppose you have a box of volume $V$ filled with a mol of an ideal gas with internal energy $E$. This defines the macrostate of your system, or intuitively, how your system looks in a macroscopic scale. However, we still don't know how it looks in a microscopic scale, i.e., we don't know how the $\sim 10^{23}$ particles over there are behaving individually. There are many different possibilities, which are the microstates of the system. For example, at time $t = t_0$ they could have positions $x_i$ and velocities $v_i$, where the index runs over all the particles. This is one particular microstate. However, the macrostate would be the same if particle $i=1$ had position $x_2$ and velocity $v_2$ while particle $i=2$ had $x_2$ and $v_2$ (I'm assuming things are classical and indistinguishable for simplicity). So which is the correct microstate?
From a macroscopic point of view, we don't know. All we can do is attribute what is the probability of the system being in each possible microstate. The principle you stated implies that both microstates I exemplified are equally likely to be the actual microstate. We don't know which is the right microstate, and all the possible ones are equally likely.
The system moving towards the largest number of microstates is then not only a change of microstates, but also a change of macrostate. If I mix my gas with another box of gas at different temperature or something, the system will reach equilibrium at the macrostate with the most possible microstates. We still won't know what is the right microstate, being able only to attribute probabilities.
Essentially, as OP pointed out in the comments, the idea is that since we do not know which microstate is the correct one, we assign equal probabilities to all of them.
Now, this does have a bit of nuance. Is it always valid to do this? In fact, it depends on the information you have about your system. Instead of an ideal gas, let us pick a generic gas. If the energy is fixed, then all available microstates should have the very same internal energy and there is no reason to prefer one of them over the other ones. We call this the microcanonical ensemble. On the other hand, suppose temperature (which is related to the expectation value of energy) is fixed. In this situation, there could be states with more internal energy than others, as long as the temperature stays the same (for the ideal gas, this won't happen because the energy is proportional to temperature, but let us consider a more general scenario). In this situation, it can be more likely for microstates with lower internal energy to occur, so we won't pick all probabilities to be the same. Instead, they are given by a Boltzmann distribution. This is known as the canonical ensemble.
The key point is that since we do not know what is the true microstate, we can only assign probabilities. We do this according to the information we have (or according to the experimental conditions, if you prefer). For fixed energy, all microstates should have the very same probability of being the true microstate, so they are, in this sense, equally likely.


TITLE: Example of an infinite number of vectors in general position in $\mathbb{R}^n$?
QUESTION [2 upvotes]: We say that a set of vectors in $\mathbb{R}^n$ are in general position if any $n$ of them are linearly indpendent. I am looking for an explicit construction of an infinite set of vectors in $\mathbb{R}^n$ in general position that can be (relatively) easily proved to be so. By 'explicit' I mean in particular that I would like to avoid any application of the Axiom of Choice. So an answer such as "delete all vectors contained in hyperplanes spanned by any $n-1$ of the previously chosen vectors, then pick a vector from the remainder and repeat" is not acceptable.
For $n = 2$, I came up with the following pretty simple construction. For simplicity, let us identify $\mathbb{R}^2$ with the set of complex numbers $\mathbb{C}$ in the usual way. Let $\alpha$ be an irrational number, say $\alpha = \sqrt{2}$. Consider the following set of points on the unit circle:
$$
S = \{e^{i2\pi \alpha k } \colon k \in \mathbb{Z} \}.
$$
Since these are all points on the unit circle, the only way for them not to be in general position is if two are the same or if one is the negative of the other. Suppose the later (the proof in the former case is similar). Then, for some distinct integers $k_1$ and $k_2$, we have
$$
e^{i2\pi \alpha k_1} = - e^{i2\pi \alpha k_2} = e^{i\pi} e^{i2\pi \alpha k_2} = e^{i2\pi (\alpha k_2 + 1/2)}.
$$
Thus $e^{i2\pi (\alpha(k_1 - k_2) -1/2)} = 0$ which implies that $\alpha(k_1 - k_2) -1/2$ is an integer, a contradiction to the irrationality of $\alpha$.
Is there an easy way to generalise this argument to higher dimensions (with a relatively easy proof)? Or is there some other easy construction?

REPLY [7 votes]: Here's an easy enough construction of uncountably many such vectors. For $x \in \Bbb R$, define $v_x \in \Bbb R^n$ to be
$$
v_x = (1,x,x^2,\dots,x^{n-1}).
$$
Any $n$ (distinct) such vectors are linearly independent. To see that this is the case, it suffices to note that for any $x_1,\dots,x_n$, the matrix whose rows are $v_{x_1},\dots,v_{x_n}$ is a Vandermonde matrix with distinct rows and is therefore invertible.


TITLE: The image of a continuous mapping on a connected metric space is connected: ($\epsilon - \delta$) proof
QUESTION [1 upvotes]: I've seen entirely set-theoretical solutions to this proof, but not many based on epsilon-delta arguments. I tried writing one, but am not sure whether my arguments hold.
Theorem: The image of a continuous mapping on a connected metric space is connected.
Proof: Let $\mathrm{(X,d_1)}$, $\mathrm{(Y,d_2)}$ be metric spaces, where $\mathrm X$ is a connected space, and let $f:\mathrm{X} \rightarrow \mathrm{Y}$ be a continuous mapping.
Assume that $f[\mathrm{X}] = \mathrm{P \cup G}$, where $\mathrm{P,G}$ are nonempty, disjoint, open sets.
$\mathrm{P}$ and $\mathrm{G}$ are disjoint $\Rightarrow \exists r>0$ such that $\mathrm{B(x,r)}\cap\mathrm{G} = \emptyset\space \forall x\in \mathrm{P}$.
$f$ is continuous $\Rightarrow$ $\forall \epsilon>0,\space\exists \delta>0$ so that if $d_1(x,y)<\delta \Rightarrow d_2(f(x),f(y))<\epsilon = \frac{r}{2}$ for all $x\in f^{-1}[\mathrm{P}], y\in f^{-1}[\mathrm G]$
$\Rightarrow \exists\epsilon < r \space\forall r>0 \Rightarrow\nexists \mathrm{B(x,r)}\cap\mathrm{G} = \emptyset$, which contradicts the assumption that $\mathrm{P,G}$ are disjoint and open.
$\Rightarrow \mathrm{P,G}$ are closed and not disjoint.
Now, there are a few questions I have: I tried using a point inside the open ball such that the distance between the point and the set G was minimised, and tried to show that $r < \epsilon$, but couldn't make it work, no matter what I tried. Is it viable?
Also, I feel like the proof is a bit cluttered, like something could be cleaned up, and concluding that P,G must be closed and disjoint, I feel like it should be phrased differently for clarity.

REPLY [1 votes]: I'm afraid your proof doesn't work.  Let $Y = \Bbb R$ with the usual metric, let $P$ be the negative reals and let $G$ be the positive reals (so there's a "hole" at $0$ that disconnects $P$ and $G$).  It's not true that there is some $r$ that uniformly separates $P$ and $G$ (in other words, there's no $r$ that works for all $x \in P$, though for each $x \in P$ there is an $r$ that works).
But the statement is true in general, not just for metric spaces, and it's a pretty easy consequence of the definition of continuous in a general topological space:

A function $f:X \rightarrow Y$ is continuous if $U \subseteq Y$ open in  $Y\Rightarrow f^{-1}(U)$ open in $X$.


TITLE: Let $f(x,y)=x^3+x(y^3+1) +e^{y-1}$. Let $(x_0,y_0)=(2,1)$.
QUESTION [1 upvotes]: 4 parts to the question
(a) Compute $\frac{\partial{f}}{\partial{x}}(2,1)$ and $\frac{\partial{f}}{\partial{y}}(2,1)$ \begin{aligned} \end{aligned}
(b)compute $f(2,1)$\begin{aligned} \end{aligned}
(c) Use a linear approxomation to estimate the change in $f$ if $x$ is increased by $0.2$ and $y$ is increased by $0.3$\begin{aligned} \end{aligned}
(d) Suppose that $x$ is increased by $0.2$. Use a linear approximation to estimate how much y should be decreased so that $f$ remains the same.\begin{aligned} \end{aligned}
Part (a):
\begin{aligned}\frac{\partial{f}}{\partial{x}}=3x^2 + y^3 + 1 \end{aligned}
\begin{aligned}\frac{\partial{f}}{\partial{y}}=3xy^2-e^{y-1}\end{aligned}
\begin{aligned}\frac{\partial{f}}{\partial{x}}(2,1)=3*(3)^2 + 1^3+1 = 29\end{aligned}
\begin{aligned}\frac{\partial{f}}{\partial{y}}(2,1)=2(1)^2-e^{1-1}=1\end{aligned}
Part (b):
\begin{aligned}f(2,1)= 2^3+2(1^3+1)+e^{1-1}=13\end{aligned}
Part (c):\begin{aligned} L(x,y)= f(2,1) + f_x(2,1)(x-2) +f_y(2,1)(y-1)\end{aligned}
\begin{aligned} L(x,y)= 13 + 29(x-2) + 1(y-1) \end{aligned}
\begin{aligned} L(x,y)= 13 + 29x - 58 + y - 1 \end{aligned}
\begin{aligned} L(x,y)= 29x + y - 46 \end{aligned}
\begin{aligned} L(2.2,1.3) = 29(2.2)+ 1.3 -46 = 19.1\end{aligned}
part (d) \begin{aligned} 19.1=29(2.2) + 1.3 - a - 46 \end{aligned}
just solve for a and you have the answer.
Am I correct in these solutions?

REPLY [1 votes]: In part (a) you wrote:
$$\frac{\partial f}{\partial x} = 3x^3 + y^3 + 1$$
$$\frac{\partial f}{\partial y}= 3xy^2 - e^{y - 1}$$
But it should be:
$$\frac{\partial f}{\partial x} = 3x^2 + y^3 + 1$$
$$\frac{\partial f}{\partial y}= 3xy^2 + e^{y - 1}$$

(b) is correct and in (c) and (d) I think they want you to use the formula:
$$\Delta f\approx \frac{\partial f}{\partial  x} \Delta x + \frac{\partial f}{\partial y} \Delta y \ \ \ (1)$$
Try to use this and then edit you question and show what you did, and then I can see if you made it correctly.

In part (C) you got the partial derivatives at $(2,1)$ wrong because you used the wrong formula for the darivatives:
$$f_x(2,1) = 3 \cdot 2^2 + 1^3 + 1 = 14$$
$$f_y(2,1) = 3\cdot 2 \cdot 1^2 + e^{1-1}=7$$
I don't quite understand what you tried to do with that $L$ function and why you defined it the way you did. In the exercise they said: "$x$  is increased by $0.2$ and $y$ is increased by $0.3$". This means that $\Delta x = 0.2$ and $\Delta y = 0.3$. Now, If you just plug these values in formula (1) you get:
$$\begin{align}
\Delta f & \approx f_x(2,1) \Delta x +  f_y(2,1) \Delta y\\
\\
& \approx 14 \cdot 0.2 + 7 \cdot 0.3 = 4.9
\end{align}$$
So you conclude that: $\Delta f \approx 4.9$ and this is what they asked you to calculate.

In (D) You just do the same but you solve for $\Delta y$:
You want $\Delta y = 0$ because you don't want it do change, so you solve:
$$\begin{align}
f_x(2,1) \cdot 0.2 +  f_y(2,1) \Delta y = 0
\end{align}$$
and so you end up with $\Delta y = -0.4$
And this is the answer that you want.


TITLE: Solve $\lim_{x \rightarrow e} \frac{e-x}{\ln x -1}$ without using L'Hopital's rule
QUESTION [1 upvotes]: I tried:
$$\lim_{x \rightarrow e} \frac{e-x}{\ln x -1} = \frac{e-x}{\ln(x)-\ln(e)} = \frac{e-x}{\ln(\frac{x}{e})} = ???$$
What do I do next? I think I could use $\lim \frac{\log_a x}{x} = 0, a>1$, but I'm not sure how.

REPLY [0 votes]: $$\lim_{x\to e} \frac{e-x}{\ln x-1} = -\lim_{x\to e}\frac{1}{\frac{\ln x-1}{x-e}} = -\lim_{x\to e}\frac{1}{\ln(\frac{x}{e})^{\frac{1}{x-e}}} = -\lim_{x\to e}\frac{1}{\ln{\bigg({\big(1+\frac{x-e}{e}\big)}^{\frac{e}{x-e}}\bigg)^{\frac{x-e}{e}\cdot\frac{1}{x-e}}}} = -\frac{1}{\ln e^{\frac{1}{e}}} = -e$$
With the well-known $$\lim_{f(x)\to 0}(1+f(x))^\frac{1}{f(x)} = e$$


TITLE: Question on percentages.
QUESTION [1 upvotes]: Cost of packing of mangoes is 40% of cost of fresh mangoes. Price of
  mangoes is increased by 30% but the cost of packing of mangoes is
  decreased by 50%. If cost of packed mangoes is equal to sum of cost of
  fresh mangoes and packing of mangoes then, find what is the percentage
  change in the cost of packed mangoes.

Let M be the cost of mangoes.
Initial cost:
$$=M+\frac{4}{10}M$$
Cost after revision:
$$\frac{13}{10}M+\frac{1}{2}\frac{4}{10}M$$
I get the answer as $\frac{50}{7} percent$, however the anwer is $\frac{15}{7}percent$.

REPLY [1 votes]: It is not clear at all how to interpret the decreasing of the cost of packing of mangoes, indeed if it is referred to the present price of mangoes we obtain

$\frac{13}{10}M+\frac{1}{2}\frac{4}{10}\frac{13}{10}M=1.56M$

then the increase in cost would be

$\frac{0.16}{1.4}=\frac{80}7\%$


TITLE: Proof of convergence of $\sum_{n=1}^{\infty}\frac{(-1)^{\lfloor n\sqrt{2}\rfloor}}{n}$
QUESTION [2 upvotes]: I had this task long long time ago in a calculus class. I remember it had a very elegant solution using nice property of $\text{Spec}(\sqrt{2})$,
where
$$
\text{Spec}(\alpha)=\{\lfloor\alpha n\rfloor\,:\,n=1,2,3,\ldots\}.
$$
I wasn't able to recreate the solution so I asked this question here.
Thanks to zwim I was able to recall the original solution. See my answer below.

REPLY [0 votes]: Thanks to zwim I was able to recreate original solution which was beautiful. I just wanted recall that solution because it uses nice property from

Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren, Concrete mathematics: a foundation for computer science., Amsterdam: Addison-Wesley Publishing Group. xiii, 657 p. (1994). ZBL0836.00001, Section 3.2, Page 77.

Define a multiset of integers $\text{Spec}(\alpha)$:
$$
\text{Spec}(\alpha)=\{\lfloor\alpha n\rfloor\,:\,n=1,2,3,\ldots\}.
$$
Define a function $f(x)$ for positive real $x$:
$$
f(x)=\sum_{0<n<x}(-1)^{\lfloor n\sqrt{2}\rfloor}.
$$
There is a beautiful proof in "Concrete Mathematics" that $\text{Spec}(\sqrt{2})$ and $\text{Spec}(2+\sqrt{2})$ form a disjoint partition of the set of positive integers, thus
$$
\sum_{0<n\sqrt{2}<x}(-1)^{\lfloor n\sqrt{2}\rfloor}
+\sum_{0<n(2+\sqrt{2})<x}(-1)^{\lfloor n(2+\sqrt{2})\rfloor}
=
\sum_{0<n< \lceil x\rceil}(-1)^n\in\{-1,0\}.
$$
Since $(-1)^{\lfloor n(2+\sqrt{2})\rfloor}=(-1)^{\lfloor n\sqrt{2}\rfloor}$ we get
$$
f\left(\frac{x}{\sqrt{2}}\right)+f\left(\frac{x}{2+\sqrt{2}}\right)\in\{-1,0\},
$$
which leads to inequality:
$$
-1\le f((1+\sqrt{2})x)+f(x)\le 0
$$
for all positive real $x$.
Now, by induction over $k=0,1,2,\ldots$ one can prove such claim:
$$
0<x<(1+\sqrt{2})^k \implies |f(x)|\le k.
$$
As mentioned in https://artofproblemsolving.com/community/c7h39398p245740 (link provided by zwim)
using the Abel transform we conclude that our series converges if and only if the series $\sum_{n\geqslant 1}\frac {f(n+1)}{n(n+1)}$ converges and, in case of convergence, they converge to the same sum.
It is enough to show that $|f(x)|=O(\log x)$ - which we did.


TITLE: Using hyperreals to express the interval of uniform convergence of $x^n$ in a closed form
QUESTION [4 upvotes]: The sequence of functions $f_n: E \rightarrow \mathbb{R}$ where $f(x) = x^n$ converges uniformly to $ g(x) = 0 $ for $E = [0,1-\varepsilon]$, $\forall \varepsilon > 0$. Yet, it doesn't converge uniformly for $[0,1)$, the supremum of all $E$.
Is it possible to use infinitesmials to express the interval of uniform convergence in a closed form? If not, why not? If it is possible to do this, isn't this a great advantage of the hyper reals?

REPLY [1 votes]: Here's how I interpret your question:
Can we find a hyperreal number $h > 0$ such that the sequence $f_n^\star$ converges uniformly to the zero function on the hyperreal interval $[0,1-h)$ but does not converge uniformly to the zero function on $[0,1-h')$ for any $h' < h$?
No such hyperreal exists.
It's clear that there is no real number r > 0 such that the sequence f_n converges uniformly to the zero function
on the real interval $[0,1-r)$ but does not converge uniformly to zero on $[0,1-r')$ for any $r' < r$.
Applying the Transfer principle to the sentence asserting the non-existence of real numbers satisfying this property yields a sentence asserting that there cannot be a hyperreal number with this property either.


TITLE: Does hyperbolic geometry actually take place on a hyperboloid?
QUESTION [2 upvotes]: Spherical geometry can be very easily seen in action on a sphere: if I drew on a ball, I would find triangles with sums of angles greater than 180 degrees, and parallel lines that intersect. If I were to draw on one of these
would I get the properties of hyperbolic geometry such as 5 squares meeting at a corner?

REPLY [6 votes]: No.
Hyperbolic geometry is geometry on a surface of constant negative Gaussian curvature. The hyperboloid has positive curvature, so the natural geometry on that surface isn't hyperbolic geometry.
There are models of the hyperbolic plane that use the hyperboloid. But they come with their own metric, their own way of how to compute angles and distances, which isn't the same as when you just measure them on a hyperboloid in 3D Euclidean space. Due to this I'm considering the hyperboloid model one of many models, all of which depict some properties quite naturally while contradicting intuition for some other properties. The tradeoffs make some models particularly well suited for particular tasks.
There is no way to get the complete infinite hyperbolic plane embedded into 3D Euclidean space. There exist several finite surfaces of constant negative curvature, such as the Tractricoid or Amsler's surface, but they don't have the right global structure. They either close in on themselves or end at a rim in places where the actual hyperbolic plane would continue. So these are local models are best, useful for small figures but misleading for the overall structure.
My PhD thesis has some illustrations of different models in section 2.1.


TITLE: Prove $\lim_{n\to\infty}x_n=2$ Given $\lim_{n \to \infty} x_n^{x_n} = 4$
QUESTION [4 upvotes]: Given a sequence $\{x_n\}_{n=1}^\infty$ of positive numbers, satisfying $\lim_{n \to \infty} x_n^{x_n} = 4$, prove $\lim_{n\to\infty}x_n=2$.
My attampt:
from $\lim_{n \to \infty} x_n^{x_n} = 4$ we know $\exists n_0\in\mathbb{N}:\forall n\ \geq n_0: |x_n^{x_n} -4| < \epsilon$ so
$|x_n-2| = \frac{|x_n^2-4|}{|x_n+2|} \leq |x_n^2-4| \leq |x_n^{x_n} -4| <\epsilon$
Which completes the proof if correct.
Is it?

REPLY [0 votes]: The function $f: \left[ 0,\infty \right) \to \left[ 0,\infty \right)$ given by $f(x)=x^x$ is continuous but not monotone on that interval. For example it attains the value $\frac57$ twice, see Wolfram Alpha's solution to $x^x=\frac57$ (they find $x\approx 0.530036$ and $x\approx 0.226742$).
You should restrict $f$ to an interval on which it is injective. Then argue that the inverse $f^{-1}$ of this restriction of $f$ is continuous. Then use the usual connection between continuous functions and convergent sequences. (You show that if necessary you can skip a finite number of terms from $\{ x_n \}$ to assume that $\{ x_n \}$ is within the required domain.)


TITLE: Isomorphism between quotient submodules
QUESTION [1 upvotes]: Let $A$ be a commutative ring with $1$ and let $M,N$ be $A$-modules. Let $I$ be an ideal of $A$.
How do we show the following isomorphism?
$(M \otimes_{A} N)/(I \cdot (M \otimes_{A} N)) \cong M/(IM) \otimes_{A/I} N/(IN)$
What confuses me is how to pass from tensoring with respect $A$ to tensoring with respect $A/I$.

REPLY [1 votes]: There is one sensible way to define maps $$\phi:(M \otimes_{A} N)/(I \cdot (M \otimes_{A} N)) \to M/(IM) \otimes_{A/I} N/(IN)$$ and $$\psi:
M/(IM) \otimes_{A/I} N/(IN) \to (M \otimes_{A} N)/(I \cdot (M \otimes_{A} N)).$$
Indeed, you should check that maps exist such that $$\phi(\overline{m\otimes n})=\overline m\otimes\overline n$$ and $$\psi(\overline m\otimes\overline n)=\overline{m\otimes n}$$ for all $m\in M$ and all $n\in N$; here the overlines mean coset with respect to the relevant submodule.
Once you have done that, show that $\phi\circ\psi$ and $\psi\circ\phi$ are both identities.


TITLE: Regular Graphs and Isomorphism
QUESTION [11 upvotes]: I would like to ask whether there is an already published result on that:
We take all possible different paths between each pair of nodes of two connected regular (with degree $d$ let's say, and number of nodes $n$) graphs and write down their lengths. Of course this number of distinct paths is exponential. My  question is, if we sort the lengths and compare them (the lists obtained by the two graphs) and they are exactly the same, can we say that the two graphs are isomorphic?
Of course, even if this is a result we cannot use it to reply for Graph Isomorphism, since the number of distinct paths is exponential, as said
By distinct paths, I refer to paths having at least one different node, obviously.
Thanks in priori for your help.

REPLY [6 votes]: I believe the answer to your question is "no" because an equivalent condition would imply a polynomial time solution to GI.
For $A$, the adjacency matrix of the graph $G$, note that the number of paths from $i$ to $j$ of length $k$ is $(A^k)_{i, j}$ (with repetition of vertices and edges allowed).  For two graphs $G_1$ and $G_2$ (with adjacency matrices $A_1$ and $A_2$) and $k \ge 1$, if you sorted the elements of $A_1^k$ and $A_2^k$ then in order for $G_1$ to be isomorphic to $G_2$, it is a necessary condition that the lists be identical for all $k$.
I believe your conjecture is equivalent to:
If the sorted lists of elements of $A_1^k$ and $A_2^d$ are identical for $k = 1$ to $n - 1$ (upperbound on the longest path with non-repeating vertices) then $G_1$ and $G_2$ are isomorphic.
So to solve GI, one only has to perform $n - 1$ multiplications of $n \times n$ matrices (and a little extra time to sort and compare $n^2$ elements).  This would take less than $n^4$ time.
I admit two possible flaws in my argument.  First, it is totally possible that GI has a polynomial time algorithm and that we just discovered it together, just now (hooray, we're famous!).  I find this highly unlikely.  Second (and much more probable), what I've proposed is not actually equivalent to your conjecture.
Final thought.  Have you tried this out for all, say, 3-regular graphs for size 8 or so?  I would think that if your conjecture is false, that there should be a counter example in 3-regular graphs of fairly small size.

REPLY [6 votes]: Since you're only comparing the lengths of the paths (and in the meantime forgetting what pair of nodes they correspond to if I understood you well), I think that very similar graphs should provide a counterexample : in the end you're just counting the number of paths of a fixed length and independently of the vertices they link. For example I think these graphs are a counterexample : http://www.mathe2.uni-bayreuth.de/markus/REGGRAPHS/GIF/06_3_3-2.gif and http://www.mathe2.uni-bayreuth.de/markus/REGGRAPHS/GIF/06_3_3-1.gif
If I'm not mistaken (counting paths is tedious), they both have 9 paths of length 1, 18 paths of length 2, 48 paths of length 3, 30 paths of length 4 and 36 paths of length 5


TITLE: General equation for projection of regular grid onto a line?
QUESTION [1 upvotes]: I have a regular grid of points in $xy$, say a square grid, and I want to make an orthonogal projection onto a line through the origin, with slope $\tan \alpha$:

I would like to derive a mathematical expression for the positions of the projected points on the line.
Can I write down a general expression for the orthogonal projection matrix of a bunch of points onto a straight line of known slope and intercept?

REPLY [1 votes]: Yes.
First you should determine the unit vector describing  the line of projection.
In your case it is $v=[\cos \alpha \ \  \sin \alpha]^T$.
And now every point $P$ described by the vector $p$ can be projected to the line with the projection matrix $vv^T$ to the vector  $p_p=vv^Tp$.
If you have bunch of points use simply matrix constructed from column vectors describing these points
$[p_{p1} \ \ p_{p2} \   \  \dots \ \ p_{pn}]=vv^T[p_1  \ \ p_2 \ \  \dots   \ \ p_n]$.


TITLE: Mixture with a strange free energy curve
QUESTION [1 upvotes]: I have the following energy landscape for a binary mixture with a specie $1$ of volume fraction $\phi$ (it is composed for example of colloids) and a specie $2$ of volume fraction $1-\phi$ (for example water). The black curve is showing the free-energy and the blue line is showing that there will be an instable region with a binodal and a spinodal.
I know that the particles of the specie 1 attract each other, but can't deform too much, so they have a minimum of free energy at a certain $\phi_0 \neq \{0, 1\}$. So I assume there is a term in the free energy that looks like : $f_{attraction}\sim \phi^2(-1+(\phi/\phi_0)^2)$
There should also be a term from the entropy of the kind $f_{entropy}\sim \phi \ln(\phi)+(1-\phi)\ln(1-\phi)$.
But I miss something since I don't manage to get that kind of curve (the free energy is the black curve) :

What effect could I add ? The main thing I don't understand is why at small $\phi$ making $\phi$ higher would increase the free energy !?
I'm welcoming any idea, or reference, or even if you saw that kind of free-energy curve before where it was.

REPLY [3 votes]: You seem to be arguing towards a form for $f_{\text{attraction}}$ based on interactions between particles of one species, but in discussing this you need to consider the balance between all the interactions: 1-1 vs 1-2 and 2-2. This is discussed in many textbooks on physical chemistry and thermodynamics; also online, for example here. A simple approach is regular solution theory, where the entropy of mixing is assumed ideal, but the enthalpy terms are nonzero (and hence, nonideal). Curves similar to the one you draw arise naturally using this approach.
As I pointed out in my answer to your earlier question a common form for the non-ideal excess free energy of mixing is (in your current notation)
$$
f_\text{excess} = K\phi(1-\phi).
$$
This is an enthalpic term: the physical justification is that it should depend on the product of the concentrations of both species (since it represents an interaction between them). If you make $K$ a positive constant, this will give you a "hump" in your overall free energy curve, favouring phase separation. This is what you want. It comes from a weighted combination of the various interactions, involving the mole fractions.
You can tweak this in several ways. Firstly, you can add the non-mixing contributions to the free energy, which vary linearly with $\phi$, namely $f_2\phi + f_1(1-\phi)$, taking $\phi$ to be the mole fraction of species 2. Here $f_1$ and $f_2$ are basically the chemical potentials of the pure species. This will remove the symmetry about $\phi=1/2$ and give you the slope in your diagram.
Secondly, if you want to make the non-ideal enthalpy term more interesting, you can use a more complicated form than $K\phi(1-\phi)$.
One common approach you can play with is to multiply that function by a polynomial in $(1-2\phi)$ like this
$$
f_\text{excess} = \phi(1-\phi) \sum_{n=0}^3 K_n (1-2\phi)^n
$$
with suitably chosen coefficients $K_n$.
In Atkins Physical Chemistry (7th edition, but I guess also in other editions), at the end of the chapter on simple mixtures, he sets a few problems based on fits to actual data,
using this form.
By keeping the $\phi(1-\phi)$ term as a multiplying factor,
you guarantee that the mixing enthalpy term will vanish when
either of the mole fractions goes to zero, as it must.
On your last point, as I pointed out in my earlier answer, none of these non ideal enthalpy terms will give you a free energy curve which increases with $\phi$ at small $\phi$. The entropy of mixing term is
$$
f_\text{entropy} = \phi\ln\phi + (1-\phi)\ln(1-\phi) .
$$
If you differentiate this with respect to $\phi$ you get
$$
\frac{d f_\text{entropy}}{d\phi} = \ln\phi - \ln(1-\phi)
$$
so the gradient is $-\infty$ at $\phi\rightarrow 0$
and $+\infty$ at $\phi\rightarrow 1$.
The extra enthalpy terms are well behaved in these limits.
You may need to look closely to see the variation close to the edges of the plot,
but definitely the entropy of mixing term wins. $f$ must initially decrease as $\phi$ increases from zero, but the initial decrease may change to an increase while $\phi$ is still quite small.
Finally, to illustrate, here is a curve that is reasonably similar to what you want,
based on the above formulae with $f_1=-0.02$, $f_2=0.02$ and $K=2.5$:
$$
f = 0.02\phi - 0.02(1-\phi) +2.5\phi(1-\phi) + \phi\ln\phi + (1-\phi)\ln(1-\phi) .
$$