text:
\section{Lower Bounds on Information Extraction Capacity}

In this section, we present a lower bound on the information extraction capacity in terms of the optimal value of an optimization problem. We also discuss the characteristics of the feasible region. We derive improvements on the lower bound via a generalization of the optimization problem. Further, we also show that the lower bound based on this generalization is asymptotically tight.

We first define the optimization problem. Let $\Yscr \subseteq \Xscr$. Let $\Qscr = \{Q^{(0)},\hdots,Q^{(|\Qscr|)}\}$ be the set of all $|\Yscr| \times |\Yscr|$ permutation matrices and  $Q^{(0)} = \mathbf{I}$ be the identity matrix. For convenience, we assume that the permutation matrices are indexed by the symbols from $ \Yscr $. Consider the problem $\Oscr(\ut)$ as
  \begin{align}
\maxproblemsmall{$\Oscr(\ut) :$}
{\Yscr \subseteq \Xscr}
{\displaystyle  |\Yscr| }
{\begin{array}{r@{\ }c@{\ }l}
   \sum_{i,j \in \Yscr} Q(i,j)\ut(i,j)&<& 0 \quad \forall \;   Q \in \Qscr \setminus \{\mathbf{I}\}.
	\end{array}}         \non
\end{align}
Let $ \Gamma(\ut)  = \OPT(\Oscr(\ut)) $.

\begin{theorem} \label{thm:cap-lower-bound}
  For a sender with utility $ \ut $,
  \begin{align}
    \capacity \geq \Gamma(\ut). \non
  \end{align}
\end{theorem}
Notice that the problem $ \Oscr(\ut) $ is independent of the blocklength $ n $  and thus the lower bound $ \Gamma(\ut) $ is a single-letter condition. Computing $ \capacity $ requires the sequence of $ \{\alpha(\Gs^n)\}_{n \geq 1} $ corresponding to the sequence of sender graphs $ \{\Gs^n\}_{n \geq 1} $ induced by $ \ut $. Moreover, computation of the independence number of a generic graph can be intractable. We also show via the proof of the above theorem that for a fixed $ \Yscr $, the problem $ \Oscr(\ut) $ can be solved as a linear program. Thus, in this light, the above theorem provides a computationally efficient lower bound.

In the next part of this section, we present the proof of the Theorem~\ref{thm:cap-lower-bound}. First, consider the following uniform type class.
\begin{definition}\label{defn:Type-class-TKY}
Let $K \in \Nbb $ and $ \Yscr \subseteq \Xscr $. Define the set $ \TypeK $ as
\begin{align}
\TypeK = \curly{ x \in \Yscr^{K|\Yscr|} : P_x(i) = \frac{1}{|\Yscr|} \quad \forall \; i \in \Yscr}.  \non
\end{align}
\end{definition}
Thus, the set $ \TypeK $ is a set of all those sequences where every symbol from the set $ \Yscr $ occurs exactly $ K $ times.

Consider the  following lemma which is due to a simple application of Stirling's approximation (\cite{feller2008introduction}, Ch. 2). The proof is in the Appendix.
\begin{lemma}\label{lem:asymp-of-unif-type-class}
For  a sequence of sets $ \{\TypeK\}_{K \in \Nbb } $, $ \lim_{K \rarr \infty} |\TypeK|^{1/K|\Yscr|} = |\Yscr| $.
      \end{lemma}
      Using this lemma, the following result follows. The proof can be found in the Appendix.
\begin{lemma}\label{lem:suff-cond-for-lower-bnd}
	Consider a sender with utility $\ut$ and let $ \{\Gs^n\}_{n \geq 1} $ be the corresponding sequence of sender graphs. Let $ \Yscr \subseteq \Xscr $. Assume that for all $K \in \Nbb $, $\TypeK$ is an independent set in $\Gs^{K|\Yscr|}$. Then, $\capacity \geq |\Yscr|$.
\end{lemma}

The above lemma requires that we check for the independence of $\TypeK$ for all $ K $, for which we need to check whether $ \ut_{K|\Yscr|}(y,x) < 0$ for all distinct $x,y \in \TypeK$ and for all $ K $. Instead, we have the following sufficient condition in terms of the optimization problem $ \Oscr(\ut) $ to check for the independence of the set $ \TypeK $.
\begin{lemma}\label{lem:opt-p-Tkw-ind}
Let $ n, K \in \Nbb $. Consider a sender with  utility $ \ut$ and let $ \Gs^n $ be the corresponding sender graph. Let $ \Yscr \subseteq \Xscr $ be a set feasible for the problem $ \Oscr(\ut) $. Then,  $\TypeK$ is an independent set in the graph $\Gs^{K|\Yscr|}$.
\end{lemma}
\begin{proof}
Fix a $ K \in \Nbb $. For distinct sequences $x,y \in \TypeK$,
  \begin{align}
    \ut_{K|\Yscr|}(y,x) &= \sum_{k \in [K|\Yscr|]} \frac{\ut(y_k,x_k)}{K|\Yscr|} = \sum_{i,j \in \Yscr} P_{x,y}(i,j)\ut(i,j), \non
  \end{align}
where the joint type $ P_{x,y} $ satisfies
\begin{align}
\sum_{i \in \Yscr}P_{x,y}(i,j) = \sum_{j \in \Yscr}P_{x,y}(i,j) = \frac{1}{|\Yscr|}, \non
\end{align}
for all $ i,j \in \Yscr $.

 Using the Birkhoff-von Neumann theorem \cite{schrijver2003combinatorial},  $ P_{x,y} $ can be given as a convex combination of the permutation matrices $ \Qscr = \{Q^{(0)},\hdots,Q^{(|\Qscr|)}\} $, \ie,
  \begin{align}
    P_{x,y} = \frac{1}{|\Yscr|} \sum_{m} \alpha_m Q^{(m)}, \non
  \end{align}
  where $ \sum_{m}\alpha_m = 1$ and $ \alpha_m \geq 0 \;\forall \;m$. Since $ x $ and $ y $ are distinct, it follows that $ \alpha_0 < 1 $, where $ \alpha_0 $ corresponds to the coefficient of the identity matrix $ Q^{(0)} $. Thus,
  \begin{align}
    \ut_{K|\Yscr|}(y,x)
                         &= \sum_{i,j \in \Yscr} P_{x,y}(i,j)\ut(i,j) \non \\

    &=  \frac{1}{|\Yscr|} \sum_{m \in [|\Qscr|]} \alpha_m\sum_{i,j \in \Yscr}  Q^{(m)}(i,j)\ut(i,j). \non
  \end{align}
  Since $ \Yscr$ is feasible for $ \Oscr(\ut) $, the term $ \sum_{i,j \in \Yscr}  Q^{(m)}(i,j)\ut(i,j) $ is negative for all $ m \in [|\Qscr|] $.  Thus, $ \ut_{K|\Yscr|}(y,x) < 0 $ for all distinct $ x, y \in \TypeK $ and hence, $ \TypeK $ is an independent set in the graph $ \Gs^{K|\Yscr|} $.
\end{proof}

We now prove Theorem~\ref{thm:cap-lower-bound}. \\
\begin{proof}[\textit{of Theorem~\ref{thm:cap-lower-bound}}]
  	Consider a set $ \Yscr^* \in \arg \max_{\Yscr} \Oscr(\ut) $.  From Lemma~\ref{lem:opt-p-Tkw-ind}, it follows that $ T_{\Yscr^*}^K $ is an independent set in $ \Gs^{K|\Yscr^*|} $ for all $ K \in \Nbb $. Finally, Lemma~\ref{lem:suff-cond-for-lower-bnd}  gives that  $\capacity \geq |\Yscr^*| =  \Gamma(\ut) $.
\end{proof}

\begin{remark}
  1) For a fixed $ \Yscr$, the constraints of $ \Oscr(\ut) $ require that $    \sum_{i,j \in \Yscr} Q(i,j)\ut(i,j) $ is negative for all non-identity permutation matrices. Equivalently,  to check for the feasibility of $ \Yscr $, we can solve the following linear program
      \begin{align}
\maxproblemsmall{$ $}
{\alpha \in [0,1]^{|\Qscr|}}
{\displaystyle  \sum_{m \in [|\Qscr|]} \alpha_m\sum_{i,j \in \Yscr}  Q^{(m)}(i,j)\ut(i,j)}
{\begin{array}{r@{\ }c@{\ }l}
        \sum_{m}\alpha_m  &=& 1.
	\end{array}}         \non
      \end{align}

  and search for the optimal $ \alpha $. The extreme points will contain an optimal solution and due to Birkhoff-von Neumann theorem the extreme points in the above problem correspond to permutation matrices $ Q \in \Qscr $. Thus, if there exists a solution where the objective in the above problem is positive or if optimal occurs at $ \alpha^* $ where $ \alpha_0^* < 1 $, then the set $ \Yscr $ is not feasible for $ \Oscr(\ut) $. Since in  either of the cases it  implies $  \sum_{i,j \in \Yscr} Q(i,j)\ut(i,j)  \geq 0 $ for some  $ Q \in \Qscr, Q \neq \mathbf{I} $.

2) In the above procedure, we observed that if $ \Yscr $ is feasible for $ \Oscr(\ut) $, then the uniform type class $ \TypeK $ is an independent set in $ \Gs^{K|\Yscr|} $. We now present a formulation which will generalize the bound given by $ \Oscr(\ut) $.  Let $ P $  be some type in $ \Pscr(\Xscr) $. Define
      \begin{align}
\maxproblemsmall{$ \Tscr(P,\ut) : $}
{P_{X,Y} \in [0,1]^{q \times q}}
{\displaystyle  \sum_{i,j \in \Xscr} P_{X,Y}(i,j)\ut(i,j)  }
{\begin{array}{r@{\ }c@{\ }l}
        P_X &=& P_Y = P.
	\end{array}}         \non
      \end{align}

      The following lemma shows how the above problem $ \Tscr(P,\ut) $  generalizes the bound  $ \Gamma(\ut) $. The proof is in the Appendix.
\begin{lemma}\label{lem:generalize-O}
Consider a utility $ \ut $. Let $ P \in \Pscr(\Xscr) $ be a type such that  $ \OPT(\Tscr(P,\ut)) = 0 $ and the optimal occurs only at $ P_{X,Y}^*(i,i) = P(i) $ for all $ i \in \Xscr $. Then,
  \begin{align}
    \capacity \geq \exp(H(P)),\non
  \end{align}
where $ H(P) $ is the $ q $-ary entropy of $ P $ and $ \exp $ is with respect to the base $ q $.
\end{lemma}
Clearly, taking $ P $ to be a uniform type with support over a set $ \Yscr $, the above lemma yields the bound given in Theorem~\ref{thm:cap-lower-bound}.
However, the following lemma shows that this bound is not stronger than $ \Gamma(\ut) $. The proof can be found in the Appendix.
\begin{lemma}\label{lem:Ou'-not-better}
Consider a utility $ \ut $. Let $ P \in \Pscr(\Xscr) $ be a type such that  $ \OPT(\Tscr(P,\ut)) = 0 $ and the optimal occurs only at $ P_{X,Y}^*(i,i) = P(i) $ for all $ i \in \Xscr $. Then, $ \Gamma(\ut) \geq |\supp(P)|$.
\end{lemma}
\end{remark}

It can be observed that $ \Tscr(P,\ut) $ is an \textit{Optimal Transport Problem} (\cite{ambrosio2008gradient}, Ch. 6) where the optimization is over joint distributions $ P_{X,Y} $ whose marginals are equal to $ P $. Intuitively, this problem asks for an optimal way of relative distribution of weights $ P_{X,Y} $ keeping the  marginals $ P_X $ and $ P_Y $ as $ P $.
The hypothesis of Lemma~\ref{lem:generalize-O} requires that the type $ P $ should be such that the optimal rearrangement is $ P_{X,Y}^*(i,i) = P(i) $ for all $ i \in \Xscr $.

\subsection{Lower bounds through feasible sets of $ \Oscr(\ut) $}

In this section, we provide a characterization of the sets that are feasible for the problem $ \Oscr(\ut) $.
Consider the following definition of a negative-weight chain.
\begin{definition}[Negative-weight chain]\label{defn:neg-wt-cycle}
A sequence of distinct symbols  $ i_0,i_1 ,\hdots, i_{K-1} \in \Yscr $ form a negative-weight chain if
  \begin{align}
    \ut(i_1,i_0) + \ut(i_2,i_1) + \hdots + \ut(i_0,i_{K-1}) < 0. \non
  \end{align}
\end{definition}
Notice that the chain in the above definition is a closed-chain since the first and last symbols are the same. For brevity, we describe a closed-chain as simply a chain.

The following proposition characterizes the feasible sets of $ \Oscr(\ut) $ in terms of negative-weight chains.
\begin{proposition}[Characterization of feasible region of $ \Oscr(\ut) $]\label{prop:i1-i2-condi-for-Y}
  A set $ \Yscr \subseteq \Xscr $ is feasible for $ \Oscr(\ut) $ if and only if  any sequence of distinct symbols $ i_0,i_1 ,\hdots, i_{K-1} \in \Yscr $ form a negative-weight chain.

\end{proposition}
\begin{proof}
  Suppose a set $ \Yscr \subseteq \Xscr $ is such that any sequence of distinct symbols $ i_0,i_1 ,\hdots, i_{K-1} \in \Yscr $ form a negative-weight chain. We show that $ \Yscr $ is feasible for $ \Oscr(\ut) $.

  Consider a permutation matrix $ Q \in \Qscr \setminus \{\mathbf{I}\} $.
  For this permutation matrix $ Q $, define a permutation $ \pi : \Yscr \rarr \Yscr $ as $ i = \pi(j) $  if and only if $ Q(i,j) = 1 $.

  Now, a permutation can be decomposed into disjoint cycles. Thus, a permutation $ \pi : \Yscr \rarr \Yscr $ can be represented as
\begin{align}
  (i_0^1  \hdots i_{K_1-1}^1) \hdots (i_0^M  \hdots i_{K_M-1}^M), (v_1)  \hdots (v_R), \label{eq:decom-in-disjoint-cycles}
\end{align}
where $ i_k^j, v_k \in \Yscr $ are all distinct symbols and $ M ,K_m, R \in \Nbb, K_m \geq 2 \;\forall \;m $, are such that $ \sum_{m \in [M]}K_m + R = |\Yscr| $.  The above arrangement represents that for all $ m \in [M] $, the symbols $ \{i_0^m,\hdots,i_{K_m-1}^m \} $ form cycles where $ \pi(i_k^m) = i_{(k+1) \mbox{mod }K_m}^m$. Further,  $ \pi(v_k) = v_k $ for all $ k \in [R]$.

Using this  representation in  \eqref{eq:decom-in-disjoint-cycles}, we write
\begin{align}
  & \sum_{i,j \in \Yscr}  Q(i,j)\ut(i,j) =  \sum_{j \in \Yscr}  \ut(\pi(j),j) \non \\
  &= \ut(i_1^1,i_0^1) + \ut(i_2^1,i_1^1) + \hdots + \ut(i_0^1,i_{K_1-1}^1) + \hdots \non \\
  & + \ut(i_1^M,i_0^M) + \ut(i_2^M,i_1^M) + \hdots + \ut(i_0^M,i_{K_M-1}^M) \non \\
  &< 0. \non
\end{align}
The last inequality follows since any sequence of distinct symbols from the set $ \Yscr $ form a negative-weight chain. The above relation is true for all permutation matrices $ Q \in \Qscr \setminus \{\mathbf{I}\}$.  Hence, the set $ \Yscr $ is feasible for $ \Oscr(\ut) $.

Suppose the set $ \Yscr $ is feasible for $ \Oscr(\ut) $. Take distinct symbols $ i_0,i_1 ,\hdots, i_{K-1} \in \Yscr $  for some $ K \in [|\Yscr|], \; K \geq 2 $ and choose a permutation $ \pi' : \Yscr \rarr \Yscr $ such that  $ i_0,i_1 ,\hdots, i_{K-1} $ form a cycle as $ \pi'(i_{k}) = i_{(k+1) \mbox{mod} K}$. The rest of the symbols are mapped to themselves. Let $ Q^{\pi'} $ be the corresponding permutation matrix. Observe that $ Q^{\pi'} $ is not an identity matrix. Then, it follows from feasibility of $ \Yscr $ that
\begin{align}
  &\sum_{i,j \in \Yscr }Q^{\pi'}(i,j)\ut(i,j) \non \\
  &=   \ut(i_1,i_0) + \ut(i_2,i_1) + \hdots + \ut(i_0,i_{K-1}) < 0, \non
\end{align}
and hence the symbols form a negative-weight chain. Since the symbols were chosen arbitrarily, this holds for all sequences of distinct symbols from the set $ \Yscr $. This completes the proof.
\end{proof}

In the above proposition, the expression
\begin{align}
    \ut(i_1,i_0) + \ut(i_2,i_1) + \hdots + \ut(i_0,i_{K-1}) \non
\end{align}
 is (upon scaling) the utility obtained by the sender when the observed sequence is  $ (i_0i_1\hdots i_{K-1}) $ and the sequence recovered by the receiver is $ (i_1i_2\hdots i_{K-1}i_0) $, \ie, the receiver recovers the symbol $ i_1 $ in place of $ i_0 $, and so on for $ i_1,i_2 ,\hdots, i_{K-1} $. Intuitively, the symbols form a \textit{chain of lies} created by the sender represented as
 \begin{align}
i_0 \rarr i_1 \rarr \hdots \rarr i_{K-1} \rarr i_0. \non
 \end{align}
   The above theorem shows that a set $ \Yscr $ is feasible for $ \Oscr(\ut) $ if and only if the utility obtained is negative for all possible chains of lies that can be formed from the symbols of the set $ \Yscr $.

An immediate corollary is as follows.
\begin{corollary}\label{corr:ind-set-feas-for-O}
  If $ \Yscr $ is an independent set in $ \Gs $, then $ \Yscr $ is feasible for $ \Oscr(\ut) $. Also, $ \Gamma(\ut) \geq \alpha(\Gs) $.
\end{corollary}
\begin{proof}
  If $ \Yscr $ is an independent set in $ \Gs $, then for all distinct symbols $ i,j \in \Yscr $, $ \ut(i,j) < 0 $. Thus, $ \Yscr $ is feasible for $ \Oscr(\ut) $. Taking $ \Yscr $ to be any of the largest independent sets of $ \Gs $, it follows that $ \Gamma(\ut) \geq \alpha(\Gs) $.
\end{proof}

Thus, the above corollary generalizes the preliminary bound of $ \alpha(\Gs) $ given in Section IV-B. In the latter sections, we shall see that in general $ \Gamma(\ut) $ may be greater than $ \alpha(\Gs) $.

We now present some results using the symmetric part of the utility.
\begin{definition}[Symmetric part of a utility]\label{defn:symm-part-util}
For a given utility $ \ut $, let $ \utsym $ be the symmetric part defined as
\begin{align}
  \utsym(i,j) = \frac{1}{2}(\ut(i,j) + \ut(j,i)). \non
\end{align}
\end{definition}
We denote the sender graph induced by $ \utsym $ as $ \Gsym $.
The following corollary shows that all feasible sets of $ \Oscr(\ut) $ are also independent sets in the symmetric graph $ \Gsym $.

\begin{corollary}\label{coro:Y-is-ind-set}
If a set $ \Yscr $ is feasible for $ \Oscr(\ut) $, then $ \Yscr $ is an independent set in $ \Gsym $ induced by the symmetric part $ \utsym $. Thus, $ \Gamma(\ut) \leq \alpha(\Gsym) $.
\end{corollary}
\begin{proof}
  If $ \Yscr $ is feasible for $ \Oscr(\ut) $, then
 \begin{align}
    \ut(i_2,i_1) + \ut(i_1,i_2)  < 0 \quad \forall \;  i_1, i_2 \in \Yscr, i_1 \neq i_2. \non
  \end{align}
This implies that for all distinct symbols $ i_1,i_2 \in \Yscr $, we have $ \utsym(i_1,i_2) = \utsym(i_2,i_1) < 0 $.  Thus, $ \Yscr $ is an independent set in $ \Gsym $. The upper bound on $ \Gamma(\ut) $ is now obvious.
\end{proof}
Since the feasibility of $ \Yscr $ requires that the sum utility is negative for all tuples of symbols $ i_1,\hdots,i_K $, not all independent sets of $ \Gsym $ can be feasible for the problem $ \Oscr(\ut) $.

The above  result also suggests a sufficient condition for $ \Gamma(\ut) = \alpha(\Gs) $.
\begin{corollary}
If $ \ut $   is symmetric then $ \Gamma(\ut) = \alpha(\Gs) $.
\end{corollary}
\begin{proof}
The claim follows from   Corollary~\ref{corr:ind-set-feas-for-O} and Corollary~\ref{coro:Y-is-ind-set}.
\end{proof}

Having discussed few characteristics of the set $ \Yscr $, we now discuss a computational approach that can be used to check for the feasibility of a set $ \Yscr$.
\subsubsection{Algorithmic approach to determine the feasibility of  a set for $ \Oscr(\ut) $}

Given a set of vertices $ \Yscr $, its feasibility for $ \Oscr(\ut) $ can be checked using the Bellman-Ford algorithm in the following way. Define a weighted directed graph $ \bar{\Gs} $ with vertices $ \Xscr $ induced by $ \ut $ where every vertex is connected to every other vertex and the edge from a vertex $ i $ to $ j $ has weight $ \ut(j,i) $. Define a utility $ \ut' = - \ut $ and let the directed graph induced by $ \ut' $ be denoted as $ \Gs' $. Suppose we have a set $ \Yscr $ that is feasible for the problem $ \Oscr(\ut) $. Then, from the characterization of feasible region of $ \Oscr(\ut) $, it implies that there is no zero or positive-weight directed cycle in the subgraph of $ \bar{\Gs} $ induced by  $ \Yscr $. Equivalently, there is no negative-weight or zero-weight directed cycle in the subgraph of $ \Gs' $ induced by $ \Yscr $. We use this observation as follows.

 The Bellman-Ford algorithm (\cite{cormen2009introduction}, Ch. 26), determines the shortest paths to all vertices in a directed graph from a given source vertex. It is also known that the algorithm detects whether the graph has a negative-weight directed cycle in the graph, in which case there may not exist a shortest path between two vertices. Suppose there is no zero-weight directed cycle in the graph $ \Gs' $. Then, this algorithm can be used to check for the feasibility of a given $ \Yscr $ in the following manner.
\begin{itemize}
\item Given a set $ \Yscr $ consider the subgraph of $ \Gs' $ induced by the vertices $ \Yscr $
\item Apply the Bellman-Ford algorithm on this subgraph
\item If the algorithm detects a negative-weight directed cycle in the subgraph, then the set $ \Yscr $ is not feasible for $ \Oscr(\ut) $. Otherwise, $ \Yscr $ is feasible for $ \Oscr(\ut) $.

\end{itemize}

In the worst case, we need to check feasibility of all subsets of $ \Xscr $ in order to determine the optimal $ \Yscr $. However, the total number of subsets of  $ \Xscr $ may be very large which may make this procedure impractical.  In the Section V-C, we present a method of \textit{capping} the utility that may make it simpler to choose a candidate $ \Yscr $. Nevertheless, the above method is still independent of the blocklength $ n $ and is thus an effective tool to derive a lower bound for the capacity.

\subsection{Approaching the capacity via a hierarchy of lower bounds}

In this section, we use a generalized form of $ \Oscr(\ut) $ to derive a series of lower bounds which approach the capacity.

Recall the optimization problem $ \Oscr(\ut) $. Let $\Yscr_n \subseteq \Xscr^n$. Let $\Qscr = \{Q^{(0)},\hdots,Q^{(|\Qscr|)}\}$, $Q^{(0)} = \mathbf{I}$ be the set of all $|\Yscr_n| \times |\Yscr_n|$ permutation matrices. For convenience, we assume that the permutation matrices are indexed by sequences from $ \Yscr_n $. Consider the problem $\Oscr(\ut_n)$ as
  \begin{align}
\maxproblemsmall{$\Oscr(\ut_n) :$}
{\Yscr_n \subseteq \Xscr^n}
{\displaystyle  |\Yscr_n| }
{\begin{array}{r@{\ }c@{\ }l}
   \sum_{x,z \in \Yscr_n} Q(x,z)\ut_n(x,z)&<& 0 \quad \forall \;   Q \in \Qscr \setminus \{ \mathbf{I}\}.
	\end{array}}         \non
\end{align}
Let $\Gamma(\ut_n) = \OPT(\Oscr(\ut_n)) $.  The following theorem is a generalization of Theorem~\ref{thm:cap-lower-bound}.
\begin{theorem}\label{thm:generalized-lower-bound-Oun}
Let $n \in \Nbb $.  For a sender with utility $ \ut $,
  \begin{align}
    \capacity \geq \Gamma(\ut_n)^{1/n}. \non
  \end{align}
\end{theorem}
\begin{proof}
  Observe that Lemma~\ref{lem:opt-p-Tkw-ind} and Lemma~\ref{lem:asymp-of-unif-type-class} do not impose any specific structure for the set $ \Xscr $. In particular, in place of the  set $ \Xscr $ we can consider its $n$-fold Cartesian product $ \Xscr^n $ and the results will hold.

Let $ K \in \Nbb. $  Consider a set $ \Yscr_n $ that  maximizes $ \Oscr(\ut_n) $.  Following Definition~\ref{defn:Type-class-TKY}, we define a type class $ T_{\Yscr_n}^{K} $ which consists of sequences constructed by concatenating sequences from $ \Yscr_n $, each appearing exactly $ K $ times. This construction gives sequences of length  $ nK|\Yscr_n| $. Analogous to Lemma~\ref{lem:opt-p-Tkw-ind} it follows that $ T_{\Yscr_n}^{K} $  is an independent set in $ \Gs^{nK|\Yscr_n|} $ for all $ K \in \Nbb $. Consequently, the capacity is bounded as
  \begin{align}
\capacity = \lim_{K \rarr \infty} \alpha(\Gs^{nK|\Yscr_n|})^{\frac{1}{nK|\Yscr_n|}} \geq   \lim_{K \rarr \infty}  \Big(|T_{\Yscr_n}^{K}|^{\frac{1}{ K|\Yscr_n|}}\Big)^{1/n}. \non
  \end{align}
Analogous to Lemma~\ref{lem:asymp-of-unif-type-class}, we use  Stirling's approximation to determine $ \lim_{K \rarr \infty}|T_{\Yscr_n}^{K}|^{1/ K|\Yscr_n|} $. Notice that $ |T_{\Yscr_n}^{K}| $ is now given as $  |T_{\Yscr_n}^{K}| = (K |\Yscr_n|)!/(K!)^{|\Yscr_n|}$.  Thus,
  \begin{align}
\capacity  \geq   \lim_{K \rarr \infty}  \Big(|T_{\Yscr_n}^{K}|^{\frac{1}{ K|\Yscr_n|}}\Big)^{1/n} = |\Yscr_n|^{1/n} = \Gamma(\ut_n)^{1/n}. \non
  \end{align}

\end{proof}

Although  $ \Gamma(\ut_n)^{1/n} $ generalizes the single-letter lower bound $ \Gamma(\ut) $, the above result does not claim that it improves on the latter. The following results show that there is indeed a sub-sequence of $\{\Gamma(\ut_n)^{1/n}\}_{n \geq 1} $ which is not only an increasing sequence of lower bounds on $ \capacity $ but also that they approach $ \capacity$.

First, consider a multiplicative property of $ \Gamma(\ut_n) $ analogous to Lemma~\ref{lem:alphaGmn-geq-GmGn}. The proof can be found in the Appendix.

   \begin{lemma} \label{lem:gamma-m+n-gamma-m-times-n}
Let $ m,n \in \Nbb $. For any utility $ \ut $,
     \begin{align}
       \Gamma(\ut_{m+n}) \geq \Gamma(\ut_{m})\Gamma(\ut_{n}). \non
     \end{align}

   \end{lemma}

   A corollary of the above result suggests a sub-sequence along which we can progressively improve the lower bound.
   \begin{corollary}
     Let $ n \in \Nbb $. Then,
     \begin{align}
 \Gamma(\ut_{2n})^{1/2n}  \geq \Gamma(\ut_n)^{1/n}. \non
     \end{align}
   \end{corollary}

The above corollary, together with  Theorem~\ref{thm:generalized-lower-bound-Oun}, demonstrates a method to  get an increasing sequence of lower bounds on $ \capacity $. Evidently, one may wonder what the limit of this sequence may be.  The following result shows that the limit is  equal to $ \capacity $.
   \begin{theorem}
     For any utility $ \ut $,
     \begin{align}
       \lim_{n \rarr \infty} \Gamma(\ut_n)^{1/n} = \capacity. \non
     \end{align}
   \end{theorem}
   \begin{proof}
   Since $ \capacity $ is the limit of $ \alpha(\Gs^n)^{1/n} $,  given a $ \delta > 0$, there exists a large enough $ N $ such that
       \begin{align}
\alpha(\Gs^n) \geq \capacity^{n(1 - \delta)} \quad \forall \; n \geq N. \non
       \end{align}
From Corollary~\ref{corr:ind-set-feas-for-O}, it follows that all independent sets of $ \Gs^n $ are feasible for $ \Oscr(\ut_n) $. Thus, $ \Gamma(\ut_n) \geq \alpha(\Gs^n) $. The limit of the $n$-th root along with  Theorem~\ref{thm:generalized-lower-bound-Oun} gives
              \begin{align}
\capacity^{1 - \delta} \leq \lim_{n \rarr \infty} \Gamma(\ut_n)^{1/n}  \leq \capacity.\non
              \end{align}
               Since this holds for arbitrary $ \delta > 0 $, the claim follows.
   \end{proof}

\subsection{Lower bound using auxiliary utilities}
The structure of the problem offers the opportunity to bound utility $ \ut $ to approximate $ \capacity $ better. One such possibility is to reduce the utility to a function which takes just two values. The following lemma suggests one such simplification that can be used to bound $ \capacity $.
\begin{lemma} \label{lem:umax-lower-bnd}
  Consider a utility $\ut$ and define the following quantities.
  \begin{align}
    \ut_{\max}^+ &= \max_{i,j: \ut(i,j) \geq 0} \ut(i,j), \quad      \ut_{\max}^- = \max_{i,j: \ut(i,j) < 0} \ut(i,j). \non
  \end{align}
  Define utility $\ut^{\max} $ as
  \begin{align}
    \ut^{\max}(i,j) &= \left\{
                       \begin{array}{c l}
                         \ut_{\max}^+  & \;\mbox{if} \;\;    \ut(i,j) \geq 0 \\
              \ut_{\max}^-  & \;\mbox{if} \;\;    \ut(i,j) < 0
                       \end{array}\right..  \non
  \end{align}
  Then,
  \begin{align}
 \capacity \geq     \Xi(\ut^{\max}). \non
  \end{align}
\end{lemma}
\begin{proof} Let $ n \in \Nbb $ and $ (\Gs^{\max})^n $ be the sender graph for $ \ut^{\max} $. For any pair of sequences $ x, y \in \Xscr^n $, $ \ut_n(y,x) $ is given as
  \begin{align}
    & n\ut_n(y,x) \non \\
      &= \sum_{k : \ut(y_k,x_k) \geq 0} \ut(y_k,x_k) + \sum_{k : \ut(y_k,x_k) < 0} \ut(y_k,x_k) \non \\
                 &\leq \sum_{k : \ut(y_k,x_k) \geq 0} \ut_{\max}^+ + \sum_{k : \ut(y_k,x_k) < 0} \ut_{\max}^- \non \\

    &= n\ut^{\max}_n(y,x). \non
  \end{align}

Now if $ x,y $ are adjacent in the graph $ \Gs^n $, then $ \ut_n(y,x) \geq 0 $ or $ \ut_n(x,y) \geq 0 $. This gives that $ \ut_n^{\max}(y,x) \geq 0 $ or $\ut_n^{\max}(x,y) \geq 0 $.    Thus,  $  \Gs^n$ is a subgraph of $(\Gs^{\max})^n $ and hence $  \alpha((\Gs^{\max})^n)    \leq \alpha(\Gs^n) $. Taking the limit of the $n$-th root, the claim follows.
\end{proof}

Notice that the  $ \ut^{\max} $ is such that $ \ut^{\max}(i,j) = a $ or $ -b $ where $ a,b \geq 0 $. This structure can be used to determine the feasible sets of $ \Oscr(\ut) $.  The following result helps in determining a class of feasible sets using the  structure of $ \ut^{\max} $.

  \begin{corollary}
    Consider a utility $ \ut $ and let $ \ut_{\max}^+ $ and $ \ut_{\max}^-  $ be as defined in Lemma~\ref{lem:umax-lower-bnd}.  Let $ |\ut_{\max}^-| > 0 $ and $ \beta =  \ut_{\max}^+/ |\ut_{\max}^-| $.  Let $ I \subseteq \Xscr $ be a set such that for any sequence of distinct symbols $ i_0,\hdots,i_{K-1} \in I $,  there exists a pair of symbols  $ i_j,i_k $, $ k = (j+1)\mbox{mod}\; K$,  such that $ \ut(i_k,i_j) < 0 $. Further suppose,
    \begin{align}

         \Big|\{ (i_k,i_j) : k  = (j+1)\mbox{mod}\; K, \ut(i_k,i_j) \geq 0 \} \Big|    < 1/ \beta. \non
    \end{align}
     Then,  $ \capacity \geq |I| $.
  \end{corollary}
  \begin{proof}
    Consider a distinct sequence of symbols $ i_0,i_1 ,\hdots, i_{K-1} \in I $. Then,

  \begin{align}

      &\ut(i_1,i_0) + \ut(i_2,i_1) + \hdots + \ut(i_0,i_{K-1}) \non \\
    & = \sum_{(i,j): \ut(i,j) < 0} \ut(i,j)  + \sum_{(i,j): \ut(i,j) \geq 0} \ut(i,j) \non \\

    &\leq |\ut_{\max}^-| \times \non \\
    &\Big( -1 +  \beta \big|\{ (i_k,i_j) : k= (j+1)\mbox{mod}\; K, \ut(i_k,i_j) \geq 0 \} \big| \Big) \non \\
    &< |\ut_{\max}^-|(-1+1) = 0. \non
  \end{align}

  Since $ i_0,i_1 ,\hdots, i_{K-1} \in I, i_l \neq i_m $ were arbitrary, this holds for all such symbols from $ I $. Using Proposition~\ref{prop:i1-i2-condi-for-Y}, it follows that the set $ I $ is feasible for $ \Oscr(\ut) $.
  \end{proof}
The hypothesis of the above corollary states that the set $ I $ is such that given any sequence of symbols from the set, there always exists a negative-weight edge in the chain formed by the symbols. Further, the number of positive-weight edges along the chain are bounded by the number $ 1/\beta $. Clearly, for $ \beta = 1 $, $ I $ has to be an independent set in $ \Gs $.

Recall the symmetric part of $ \ut $ given in Definition~\ref{defn:symm-part-util}. The following lemma gives a lower bound in terms of the capacity of a function of this symmetric part.   The utility $ \ut $ can be split into a unique symmetric and anti-symmetric part as $ \ut = \utsym + \ut^{\mathsf{Asym}} $.  Consider the definition of a utility $ \ut^{\sf inc} $ as
  \begin{align}
    \ut^{\sf inc}(i,j)     &= \utsym(i,j) + |\ut^{\mathsf{Asym}}(i,j)| \quad \forall \; i,j \in \Xscr. \label{eq:ut_inc-defn}
  \end{align}

  $ \ut^{\sf inc} $ is constructed by \textit{incrementing} the symmetric part of $ \ut $ by $ |\ut^{\mathsf{Asym}}| $.  The following lemma shows that the capacity of $ \ut^{\sf inc} $ is a lower bound on $ \capacity $
  \begin{lemma} \label{lem:lower-bnd-with-symm-util}
 Consider a utility $ \ut $  and let $ \ut^{\sf inc} $ be defined as \eqref{eq:ut_inc-defn}.  Then,
     \begin{align}
       \capacity \geq  \Xi(\ut^{\sf inc}). \non
     \end{align}
   \end{lemma}
   \begin{proof}
     The utility $ \ut $ can be written as $ \ut = \ut^{\sf inc} + \ut' $, where

$ \ut' $ is given as
     \begin{align}
       \ut'(i,j) &= \ut^{\mathsf{Asym}}(i,j) - |\ut^{\mathsf{Asym}}(i,j)|. \non

     \end{align}

It follows that $ \ut'(i,j) \leq 0 $ for all $ i,j \in \Xscr $.

Let $ n \in \Nbb $ and let the  sender graph corresponding to $ \ut_n^{\sf inc} $ be denoted as $ (\Gs^{\sf inc})^n $. Consider distinct sequences $ x,y \in \Xscr^n $ that are adjacent in $ \Gs^n $. Suppose $ \ut_n(y,x) \geq 0 $. Then, $ \ut_n^{\sf inc}(y,x) + \ut_n'(y,x) \geq 0 $  and since   $ \ut'(i,j)\leq 0 $ for all $ i,j $, it follows that  $ \ut_n^{\sf inc}(y,x) \geq 0 $. Thus,  $ x,y $ are adjacent in $ (\Gs^{\sf inc})^n $, which gives   $ \alpha(\Gs^n) \geq  \alpha ((\Gs^{\sf inc})^n) $ and hence $ \capacity \geq \Xi(\ut^{\sf inc}) $.
   \end{proof}

In the next section, we will discuss an upper bound in terms of the capacity of only the symmetric part of the utility.

\section{Upper Bounds on Information Extraction Capacity}

In this section, we derive upper bounds on the information extraction capacity of the sender. We show that the Shannon capacity of the sender graph corresponding to the symmetric part of the utility is an upper bound on the capacity. We also discuss a class of utilities  where the upper bound is given by the Shannon capacity of the sender graph itself.

First, consider the following upper bound for any utility $ \ut $.
   \begin{lemma} \label{lem:symm-util-upper-bnd}
     Consider a utility $ \ut $ and let $ \utsym $ be its symmetric part.  Then,
     \begin{align}
       \capacity \leq \Xi(\utsym). \non
     \end{align}
   \end{lemma}
   \begin{proof}
Let $ n \in \Nbb $.     Consider distinct sequences $ x,y \in  \Xscr^n $ which are adjacent in $ (\Gsym)^n $. Thus,  $ \utsym_n(y,x) = \utsym_n(x,y) =  (\ut_n(y,x) + \ut_n(x,y))/2 \geq  0 $, which gives that either $ \ut_n(y,x) \geq 0 $  or $ \ut_n(x,y) \geq 0 $. In either case, $ x,y $ are  adjacent in $ \Gs^n $ and hence $ (\Gsym)^n$ is a subgraph of $\Gs^n $. This gives $ \alpha(\Gs^n) \leq  \alpha((\Gsym)^n) $. The claim follows by taking the limit of the $n$-th root.
   \end{proof}

   \begin{remark}
   Lemma~\ref{lem:lower-bnd-with-symm-util} and Lemma~\ref{lem:symm-util-upper-bnd}  together give that the capacity is sandwiched as
\begin{align}
 \Xi(\utsym + |\ut^{\mathsf{Asym}}|) \leq  \capacity \leq \Xi(\utsym). \non
\end{align}
These bounds suggest that unless $ \ut^{\mathsf{Asym}} \equiv 0 $, $  \capacity \leq \Xi(\utsym) $. However, in the latter discussions we will see a counterexample where $   \capacity = \Xi(\utsym) $ even when $ \ut \neq \utsym $ (refer Example~\ref{eg:u-usym-cap-equal}).
\end{remark}

If the utility is symmetric, then the following upper bound holds.
\begin{theorem} \label{thm:symmetric-utility-bnd}
Consider a sender with a symmetric utility $\ut$ and let $ \Gs $  be the corresponding sender graph. Then,
    \begin{align}
\capacity \leq \Theta(\Gs). \non
    \end{align}

  \end{theorem}
  \begin{proof}
Let $ n \in \Nbb $. Consider the graph $ \Gs^{\boxtimes n} $ derived by taking the $n$-fold strong product of $ \Gs $. Consider a distinct pair of sequences $ x,y \in \Xscr^n $ that are adjacent in $ \Gs^{\boxtimes n} $. Then, for all $ k \in [n] $, either $x_k = y_k $ or $ x_k, y_k$ are  adjacent in $ \Gs $. Thus,
\begin{align}
\ut_n(y,x) = \frac{1}{n}\sum_{y_k \neq x_k} \ut(y_k,x_k) \geq 0. \non
\end{align}
Hence, $ x, y $  are adjacent in $ \Gs^n $ as well, which gives $ \Gs^{\boxtimes n}$ is a subgraph of $\Gs^n $. Thus, $ \alpha(\Gs^n)\leq \alpha(\Gs^{\boxtimes n})$ and taking the limit of the $n$-th root, the claim follows.
\end{proof}
Putting the above results together, the following result follows.
\begin{theorem}\label{thm:upper-bnd-Shannon-cap-symm}
  Consider a sender with a utility $ \ut $ and let $ \utsym $ be its symmetric part. Let $ \Gsym $ be the sender graph corresponding to $ \utsym $. Then,
  \begin{align}
    \capacity \leq \Theta(\Gsym). \non
  \end{align}
\end{theorem}
\begin{proof}
  The result follows from Lemma~\ref{lem:symm-util-upper-bnd} and Theorem~\ref{thm:symmetric-utility-bnd}.
\end{proof}

As with the lower bound, the above theorem provides an upper bound which is independent of the blocklength $ n $ and depends only on the single letter utility $ \ut $. We can observe that the symmetric part of the utility plays a recurring role in the characterization of the bounds on the capacity. Recall that in Corollary~\ref{coro:Y-is-ind-set}, we derived a characterization of the feasible sets of the problem $ \Oscr(\ut) $ in terms of the symmetric sender graph and showed that $ \Gamma(\ut) \leq \alpha(\Gsym) $.

We now present another class of utilities where the capacity is bounded above by the Shannon capacity of the sender graph.
  \begin{theorem}\label{thm:posi-diff-greater}
Consider a sender with utility  $\ut$ given as
    \begin{align}
      \ut(i,j) = \left\{\begin{array}{c l}
                            a  & \mbox{if} \;\; \ut(i,j) \geq 0 \\
                            -b  & \mbox{if} \;\; \ut(i,j) < 0
      \end{array}\right., \non
    \end{align}
    where $a,b > 0$ and $a \geq b$. Let $ \Gs $ be the corresponding sender graph.  Then,
    \begin{align}
\capacity \leq \Theta(\Gs). \non
    \end{align}
  \end{theorem}
  \begin{proof}
Let $ n \in \Nbb $. We prove the result by showing that if distinct sequences $ x,y \in \Xscr^n $ are not adjacent in $ \Gs^n $, then $ x, y $ are not adjacent in $ \Gs^{\boxtimes n} $.

    Let $ x, y $ be not adjacent in $ \Gs^n $. Then, $ \ut_n(y,x) < 0 $ and $ \ut_n(x,y) < 0 $. Since, $b \leq a$, it follows that
    \begin{align}
      \Big|\{k : \ut(y_k,x_k) = -b\}\Big| > \frac{n}{2}, \;\; \Big|\{k : \ut(x_k,y_k) = -b\}\Big| > \frac{n}{2}. \non
    \end{align}
 This implies that there is some $k$ such that $\ut(y_k,x_k) = \ut(x_k,y_k) = -b$ and hence  $x_k, y_k $  are not adjacent in $ \Gs $. It follows that $ x, y  $ are not adjacent in $ \Gs^{\boxtimes n} $ as well.  This gives that $  \alpha(\Gs^n) \leq \alpha(\Gs^{\boxtimes n}) $.
 The claim follows by taking the limit.
  \end{proof}

The utility defined in the above theorem is such that the \textit{incentive} for lying is greater than the \textit{penalty} for lying. Intuitively, a sender with utility as above has higher tendency to lie about its information, since it can offset its penalty of lying by gaining appropriate incentive. With this one can appreciate why the information extraction capacity for such a sender is in general strictly less than $ q. $

  The above theorem and Theorem~\ref{thm:symmetric-utility-bnd} characterized the utilities for which the capacity is bounded above by $ \Theta(\Gs) $. In the Section VI-B, we will discuss cases where the capacity is exactly equal to $ \Theta(\Gs) $.

\subsection{Upper bounds using auxiliary utilities}

As in Section V-C, we simplify the utility to obtain an upper bound on the capacity.
\begin{lemma} \label{lem:umin-upper-bnd}
  Consider a utility $ \ut $ and define the following quantities.
  \begin{align}
     \ut_{\min}^+ = \min_{i,j: \ut(i,j) \geq 0} \ut(i,j), \quad \ut_{\min}^- = \min_{i,j: \ut(i,j) < 0} \ut(i,j). \non
  \end{align}
  Define utility  $\ut^{\min}$ as
  \begin{align}
      \ut^{\min}(i,j)  &= \left\{
                       \begin{array}{c l}
                         \ut_{\min}^+  & \;\mbox{if} \;\;    \ut(i,j) \geq 0 \\
              \ut_{\min}^-  & \;\mbox{if} \;\;    \ut(i,j) < 0 \\
                       \end{array}\right.. \non
     \end{align}
  Then,
  \begin{align}
 \capacity  \leq \Xi(\ut^{\min}). \non
  \end{align}
\end{lemma}
\begin{proof} Let $ n \in \Nbb $ and let $ (\Gs^{\min})^n $ be the sender graph corresponding to $ \ut^{\min} $. For any pair of sequences $ x, y \in \Xscr^n $, $ \ut_n(y,x) $ is given as
    \begin{align}
 &n\ut_n(y,x)  \non \\%= \sum_{k : \ut(y_k,x_k) \geq 0} \ut(y_k,x_k) + \sum_{k : \ut(y_k,x_k) < 0} \ut(y_k,x_k) \non \\

                 &\geq    \sum_{k : \ut(y_k,x_k) \geq 0} \ut^{\min}(y_k,x_k) + \sum_{k : \ut(y_k,x_k) < 0} \ut^{\min}(y_k,x_k) \non \\
      &=n \ut^{\min}_n(y,x). \non
    \end{align}
Thus,  $     (\Gs^{\min})^n \subseteq \Gs^n $ and hence $ \alpha(\Gs^n) \leq  \alpha((\Gs^{\min})^n) $. Taking the limit of the $n$-th root, the claim follows.
\end{proof}

Using Theorem~\ref{thm:posi-diff-greater}, we have the following upper bound on the capacity in terms of Shannon capacity of $ \Gs^{\min} $.
\begin{corollary}
Consider a utility $ \ut $ and let $ \ut_{\min}^+ $ and $ \ut_{\min}^-  $ be as defined in Lemma~\ref{lem:umin-upper-bnd}. Let $ \Gs^{\min} $ be the sender graph corresponding to $ \ut^{\min} $.   Let $ |\ut_{\min}^-| > 0 $ and $  \ut_{\min}^+/ |\ut_{\min}^-| \geq 1$. Then,
  \begin{align}
    \capacity \leq \Theta(\Gs^{\min}). \non
  \end{align}
  \end{corollary}
  \begin{proof}
    Since $  \ut_{\min}^+/ |\ut_{\min}^-| \geq 1 $, $ \ut^{\min} $ is of the form given in Theorem~\ref{thm:posi-diff-greater}. Thus, $ \Xi(\ut^{\min}) \leq \Theta(\Gs^{\min}) $.
  \end{proof}

\subsection{When is $ \capacity = \Theta(\Gs) = \alpha(\Gs)$ ?}

In the earlier section, we discussed  upper bounds  on the information extraction capacity. A natural question that follows is that under what conditions the capacity is exactly characterized? In this section, we mention few cases of utility where the information extraction capacity is equal to the Shannon capacity of the induced sender graph.

\begin{theorem}\label{thm:exact-charac-of-capa}
  Consider a utility $ \ut $ and let $ \Gs $ be the corresponding sender graph. Then,
       \begin{align}
\capacity = \Theta(\Gs)  = \alpha(\Gs) \non
     \end{align}
if any of the following hold:
  \begin{enumerate}

     \item $ \ut $ is symmetric and $ \Gs $ is a perfect graph.

\item	$ \ut $ is of the form given in  Theorem~\ref{thm:posi-diff-greater} and  $ \Gs $ is a perfect graph.
\end{enumerate}

\end{theorem}
\begin{proof}
  \begin{enumerate}

    \item Follows from Theorem~\ref{thm:symmetric-utility-bnd} and the fact that for a perfect graph, $ \Theta(\Gs) = \alpha(\Gs) $ \cite{lovasz1979shannon}.

      \item  Follows from Theorem~\ref{thm:posi-diff-greater} and the fact that for a perfect graph, $ \Theta(\Gs) = \alpha(\Gs) $.
  \end{enumerate}
\end{proof}

\section{Illustrative Examples and Counterexamples}

In this section, we discuss certain examples where we use the optimization problem discussed in Section V to derive lower bounds on the information extraction capacity. We also discuss a case where we use the bounding techniques for exact computation of the capacity.

Recall the definition of a positive-edges cycle in Definition~\ref{defn:pos-wt-cycle}. The following lemma demonstrates that it is necessary that a set $ \Yscr $ does not contain a positive-edges cycle for it to be feasible for $ \Oscr(\ut)$.
\begin{lemma} \label{lem:direc-cycle-LP-neg}
	Consider a sender with utility $ \ut $ and let $ \Gs $ be the corresponding sender graph. Consider a $ \Yscr $ which contains a positive-edges cycle. Then,  $ \Yscr $ is  not feasible for $ \Oscr(\ut) $.
\end{lemma}
\begin{proof}
  Since there  exists a positive-edges cycle in $ \Yscr $, there is a sequence of distinct symbols  $ i_0,i_1 ,\hdots, i_{K-1} \in \Yscr $ such that
  \begin{align}
    \ut(i_l,i_m) \geq 0 \quad \forall \; \; l = (m+1) \mbox{mod}\; K. \non
  \end{align}
  Clearly, this means that the set $ \Yscr $ does not satisfy the condition given in Proposition~\ref{prop:i1-i2-condi-for-Y}.
\end{proof}

Suppose there exists a subset of vertices that do not form such a cycle. The following theorem that gives a sufficient condition for the set to be feasible for $ \Oscr(\ut) $.

\begin{theorem} \label{thm:suff-cond-for-pos-LP}
	Consider a sender with utility $\ut$ and let $\Gs$ be the corresponding sender graph. Suppose there exists a set $ \Yscr $ such that there is no positive-edges cycle in the sub-graph induced by $ \Yscr $ and
	\begin{align}
	&\min_{i,j \in \Yscr: \ut(i,j) < 0} |\ut(i,j)| > (|\Yscr|-1)  \max_{i,j \in \Yscr: \ut(i,j) \geq 0} \ut(i,j). \label{eq:least-pos-gre-max-neg}
	\end{align}
	Then,  $ \capacity \geq |\Yscr| $.
\end{theorem}
\begin{proof}
  Let $ i_0,\hdots,i_{K-1} $ be distinct symbols from $ \Yscr $.   Since there is no positive-edges cycle in $ \Yscr $, there is at least one pair of $ (i_k,i_j) $, $ k > j $  such that  $ \ut(i_k,i_j) < 0 $. Then,
  \begin{align}
    &\ut(i_1,i_0) + \ut(i_2,i_1) + \hdots + \ut(i_0,i_{K-1}) \non \\
    &\leq \min_{i,j \in \Yscr: \ut(i,j) < 0} |\ut(i,j)| + (|\Yscr|-1)\max_{i,j \in \Yscr: \ut(i,j) \geq 0} \ut(i,j) \non \\

    &< 0. \non
  \end{align}
  Since $ i_0,\hdots,i_{K-1} $ were arbitrary, using Proposition~\ref{prop:i1-i2-condi-for-Y}, it follows that $ \Yscr $ is feasible for $ \Oscr(\ut) $.
\end{proof}

Theorem~\ref{thm:suff-cond-for-pos-LP} gives a sufficient condition in terms of the negative and positive values of $ \ut(i,j) $ for a set $ \Yscr $ to be feasible for $ \Oscr(\ut) $. However, this condition is not a necessary condition as demonstrated by the following example.
\begin{examp}\label{eg:least-gain-max-lying-gain-countereg}
Let $ \ut : \Xscr \times \Xscr \rarr \Real$ be given as
	\begin{align}
	\ut = \round{   \begin{array}{c c c }
		0 & 2 & -2   \\
		-4 &  0 & 1  \\
		-4 &  -4 &  0  \\
		\end{array}}, \non
	\end{align}
        where $ \ut(i,j) $ is given by the $ (i,j)\th$ entry in the above matrix. We show that $ \Xscr $ is feasible for $ \Oscr(\ut) $.

        Clearly,
\begin{align}
\min_{i,j \in \Xscr: \ut(i,j) < 0} |\ut(i,j)| = 2 = \max_{i,j \in \Xscr: \ut(i,j) \geq 0}|\ut(i,j)|. \non
\end{align}
 However, it can be observed that $ \Xscr $ is feasible for $ \Oscr(\ut) $. This is because the maximum of $ \sum_{i,j \in \Xscr} Q(i,j) \ut(i,j) $, where $ Q \in \Qscr \setminus \{\mathbf{I}\} $, occurs at
	\begin{align}
	Q = \round{   \begin{array}{ c c c }
		0 & 1 & 0   \\
		0 &  0 & 1  \\
		1 &  0 &  0  \\
		\end{array}}, \non
	\end{align}
	which is $ \sum_{i,j \in \Xscr} Q(i,j) \ut(i,j) = -1 $.
\end{examp}

Using Theorem~\ref{thm:suff-cond-for-pos-LP}, the following example shows that $\capacity$ can be maximum even when the base sender graph $ \Gs $ is a complete graph.
\begin{examp}
Let $\ut : \{0,1,2\} \times \{0,1,2\} \rarr \Real $ and consider the  following form of $ \ut $,
	\begin{align}
	\ut = \round{   \begin{array}{c c c }
		0 & 1 & 1   \\
		-4 &  0 & 1  \\
		-4 &  -4 &  0  \\
		\end{array}}. \non
	\end{align}
	In the graph $\Gs$ there is an edge between $(0,1)$, $(0,2)$ and $(1,2)$. This follows since
	\begin{align}
	\ut(0,1), \ut(0,2), \ut(1,2) > 0. \non
	\end{align}
	Thus, $ \Gs $ is a $3$-cycle graph and hence is a complete graph. It can be easily observed that there is no positive-edges cycle in the graph. This is because for chain $ i \rarr j \rarr i $,  either $ \ut(i,j) < 0 $ or $ \ut(j,i) < 0 $. Further, for all chains $ i \rarr j \rarr k  \rarr i $,  either $ \ut(j,i) < 0 $ or $ \ut(k,j) < 0 $ or $ \ut(i,k) < 0 $. Also, the largest weight of a chain in $ \Gs $  is $ -4 + 1 + 1 = -2 $.

        Finally, $\min_{i,j : \ut(i,j) < 0} |\ut(i,j)| = 4 > (3-1) \max_{i,j : \ut(i,j) \geq 0}\ut(i,j) = 2$. Thus, the conditions of Theorem~\ref{thm:suff-cond-for-pos-LP} are satisfied and hence $ \Xscr $ is feasible for $ \Oscr(\ut) $ and hence $ \capacity = q $.
\end{examp}

We find this example to be quite surprising -- even though $ \Gs $ is a complete graph, the rate of information extraction is the maximum it can be. The main lesson to be drawn from it is that the \textit{magnitude} of the gains or losses from truth-telling or lying determine the amount of information that can be extracted; the base sender graph $ \Gs $ only considers the sign of these quantities.

\subsection{Exact computation of $ \capacity $}
The following example uses the lower bounds and the upper bounds to exactly compute the capacity.
\begin{examp}\label{eg:u-usym-cap-equal}
        Consider a $ \ut $ on $ \Xscr = \{ 0,1,2,3,4\} $ as
  \begin{align}
    \ut(i,j) = \left(
    \begin{array}{ c c c c c }
      0  &  -1 & -1 & -1 & -1  \\
       1 &  0 & -1  & -1 & -1  \\
      -1 & 1  & 0  & -1  & -1  \\
      -1 & -1 &  1 & 0   & -1   \\
      1 & -1 & -1 & 1    &  0
    \end{array}\right). \non
  \end{align}

  We show that $ \capacity = \sqrt{5} $.

  It can be observed that the base graph $ \Gs $ is a pentagon. This is because  $ i,j $ are adjacent if and only if $ |j-i| \mbox{mod}\; 5 = 1 $.  Also, the graph does not  contain a positive-edges cycle since $ \ut(0,4) = -1 $.

Further, the graph $ \Gsym $ induced by the symmetric part $ \utsym $ is also a pentagon graph since $ \utsym(i,j) = (\ut(i,j)+\ut(j,i))/2 = 0 $ if and only if  $ i, j $ are adjacent in $ \Gs $ or $ i = j $. For all other $ i,j $ not adjacent in $ \Gsym $, $ \utsym(i,j) < 0 $. Thus, from Theorem~\ref{thm:generalization-shannon-cap}, it follows that  $ \Xi(\utsym) = \Theta(\Gsym) = \sqrt{5} $.

  We now compute $ \capacity $. From the problem  $ \Oscr(\ut) $, we only get a lower bound on $ \capacity $  since $ \Gamma(\ut) = 2 $. However, consider $ \Oscr(\ut_2) $ and the set $ \{00,12,24,31,43\} $. Let $ x,y $ be a distinct pair of sequences from $ \{00,12,24,31,43\} $. It follows that either $ \ut(x_k,y_k) = -1 $ or  $ \ut(y_k,x_k) = -1 $ and hence, $ \ut_2(x,y) \leq 0 $. Furthermore, $ \ut_2(x,y) = 0 $ if and only if $ x_1 = (y_1 + 1) \mbox{mod} \;5 $ and $ x_2 = (y_2 + 2) \mbox{mod} \;5  $. From this it is easy to observe that all sets of distinct sequences from the set $ \{00,12,24,31,43\} $  form a negative-weight chain and using a result analogous to Proposition~\ref{prop:i1-i2-condi-for-Y} for $2$-length sequences, we get that $ \{00,12,24,31,43\} $ is feasible for $ \Oscr(\ut_2) $  and hence
  \begin{align}
\capacity \geq \Gamma(\ut_2)^{1/2} = \sqrt{5}. \non
  \end{align}
The upper and lower bounds together give that $ \capacity = \sqrt{5} $.
\end{examp}

config: arxiv


TITLE: Knot Invariants from Twisted Quantum Doubles
QUESTION [12 upvotes]: In "Topological Gauge Theories and Group Cohomology", Dijkgraaf and Witten construct a 3-manifold invariant from a finite group $G$ and 3-cocycle $\omega$. I would think there is also an associated knot invariant, coming in particular from the twisted quantum double $D^\omega(G)$, but haven't been able to find a place where it is explicitly described or computed.
If it exists, could someone point me to the right reference? I would be interested in both a general construction and a specific example, for instance computing it in the case of $\mathbb{Z}_n$.

REPLY [4 votes]: You may be interested in this paper by Chen.
One of the simplest nontrivial knot invariants is the number of "Fox n-colorings", which count homomorphisms of the knot group to a dihedral group $D_{2n}$ sending the meridians to reflections. This count can be interpreted as a value in a Dijkgraaf-Witten theory on the knot complement. Chen's paper computes those invariants in the nontwisted case in terms of the representation category of the quantum double $D(D_{2n})$ and gives a nice formula for the number of colorings of a rational link.
I tried computing values of the twisted invariant, but it turns out that these are equal to the untwisted invariants times a power of $i$ depending on the writhe.
It may be possible that something more intersting happens with a more complicated group: $D_{2n} = \mathbb{Z}_2 \ltimes \mathbb{Z}_n$ is the simplest possible case where you get interesting homomorphism counts, and I'd be curious what happens in the twisted (and untwisted) case for other semidirect products. In particular, the twisting that actually affects the DW invariants seems to mostly involve the $\mathbb{Z}_2$ part, which has few interesting cocycles.


TITLE: What is the best built-in optimizer in Matlab for this problem?
QUESTION [0 upvotes]: I need to optimize
$$\sum_{j=1}^p\frac{\sigma^2 \alpha_j^2}{\sigma^2+\delta_j^2\alpha_j^2}-\frac{\left(\displaystyle\sum_{j=1}^p \displaystyle\frac{\sigma^2 ( \delta_j^2 \alpha^2 - \theta\alpha_j)}{\sigma^2+\delta_j^2\alpha_j^2}\right)^2}{(p^2\sigma^2+p \theta^2) - \displaystyle\sum_{j=1}^p \frac{(\sigma^2+\theta \delta_j\alpha_j)^2}{\sigma^2+\delta_j^2\alpha_j^2}}$$
it terms of $\alpha$ where

$\alpha$ is a vector of four parameters,
$\sigma$ is a constant,
$\delta$ is the product of $\alpha$ and another vector which is fixed in value, and
$\theta$ is the sum of the $\delta$'s.

I think fminunc would be most suitable given the problem in non-linear, and I don't want to use any constraints (unless I have to).
Just wondered if fminunc is indeed most suited to my problem?
In the Matlab documentation, you are invited to use a table to choose the best solver (link); it seems to suggest quadprog but doesn't even mention fminunc?
Thanks

REPLY [0 votes]: For this problem you are interested in unconstrained optimization and you have a smooth nonlinear problem objective (assuming that the denominator does not blow up). From the table in the Matlab documentation, you have two choices: either fminunc or fminsearch are appropriate. (Also, the table indicates that quadprog is appropriate but only for a quadratic objective.)


text:
\begin{document}

\begin{abstract}
We establish the vanishing viscosity limit of viscous Burgers-Vlasov equations for one dimensional kinetic model about interactions between a viscous fluid
and dispersed particles by using compensated compactness technique and the evolution of level sets arguments.
The limit we obtained is exactly a finite-energy weak solution to the inviscid  equations.
\end{abstract}
\maketitle

\medskip

\noindent {\bf 2010 AMS Classification}:  76T10, 35F20, 35Q35, 35Q72,  45K05, 82D05.
\medskip

\noindent {\bf Key words}: vanishing viscosity limit, two phase flow, Vlasov equation, Burgers equation, finite-energy weak solution.

\section{Introduction}

In this note we consider the  vanishing viscosity limit of the following viscous Burgers-Vlasov equations:
\begin{equation}\label{e:vis-burgers-vlasov}
\left\{
\begin{array}{ll}
\displaystyle u_t+uu_x=\eps u_{xx}+\int_\R fvdv-u\int_\R fdv,  \\
\displaystyle f_t+v f_x+(f(u-v))_v=0,
\end{array}
\right.
\end{equation}
with the  initial data
\begin{equation}\label{e:initial}
u(x, 0)=u_0(x), \quad f(x, v, 0)=f_0(x, v),
\end{equation}
such that
\begin{equation}\label{e:uf0-asymptoic}
\lim_{x\rightarrow\pm\infty}u_0(x)=u^{\pm},  \quad \lim_{x, v\rightarrow\pm\infty}f_0(x, v)=0,
\end{equation}
with $u^{\pm}$ being constant states and allowed to be different, here $u(x, t)$ is the bulk velocity of the viscous gas at position $x\in\R$ and time $t\geq0$. $f(x, v, t)$ is the distribution function of the particles occupying at time $t$, the position $x$ with velocity $v\in\R$. $\eps\in (0, \eps_0)$ with some $0<\eps_0<1$ is the viscosity of the gas.

The system \eqref{e:vis-burgers-vlasov} is related to a kinetic model of a two-phase flow in which a dispersed phase interacts with a kind of viscous gas. Such model arises in the description of various combustion phenomena, e.g. diesel engines. The model reads
\begin{equation}\label{e:model}
\left\{
\begin{array}{ll}
\displaystyle \rho_g(u_t+uu_x-\eps u_{xx})=E_d,  \\
\displaystyle f_t+v f_x+(F_df)_v=0,
\end{array}
\right.
\end{equation}
here $\rho_g$ is the density of the gas. The force term $E_d$ describing the exchange of impulse between the gas and the particles has a close relation with the drag force $F_d$ describing the friction of the viscous fluid in the droplets. The relation can be seen from the following formulas:
\begin{equation}\label{e:efd}
\begin{split}
&E_d=\mathcal{C}(r)\rho_p(u_p-u), \quad F_d=\mathcal{C}(r)(u(x, t)-v),\\
&\rho_p=\frac{4\pi}{3}\rho_lr^3\int_\R f(x, v, t)dv,\quad
\rho_p u_p=\frac{4\pi}{3}\rho_lr^3\int_\R f(x, v, t)vdv.
\end{split}
\end{equation}
In \eqref{e:efd},  $\rho_l$ is the density of liquid. $\mathcal{C}(r)$ is a constant depending on the radius $r$ of the droplets. In  \eqref{e:model}, the viscous Burgers' equation, i.e. the first equation models the evolution of viscous gas, while the Vlasov like equation, i.e. the second equation describes the evolution of the dispersed phase. Derivation of the model can be found in \cite{Will85}. Further information about our assumptions on \eqref{e:model} can also be found in \cite{G01, DR99}. We remark that when all the constants in $E_d/\rho_g$ and $F_d$  are all assumed to be 1, then \eqref{e:model} becomes \eqref{e:vis-burgers-vlasov}.

As for the well-posedness results of \eqref{e:vis-burgers-vlasov} or \eqref{e:model}, global existence and uniqueness of classical solutions to the  Cauchy problem with regular initial data  have been considered in \cite{DR99}. Global existence of weak solutions with finite energy is studied in \cite{G01}. Other complicated models of interactions between fluid-kinetic models, such as incompressible/compressible Euler/Navier-Stokes equations coupled with Vlasov/-Fokker-Planck equation are studied in \cite{RS96-1, RS96-2, Y13, MV07} and reference therein. Asymptotic problems like hydrodynamic limit and stratified limit of \eqref{e:model} are also considered in \cite{G01}, and one can see  \cite{BMP07, NPS01, GJ04-1, GJ04-2, Ja00-C, Ja00-P, MV08} for  asymptotic problems of other models related to Vlasov equations.  For the vanishing viscosity limit of Navier-Stokes equations, $L^p$ compensated compactness framework of $2\times2$ system of conservation laws is applied  to  yield the result in \cite{CP10}, which is also used in \cite{GL16}.

Our goal is to show that when $\eps\rightarrow0,$ smooth solutions to \eqref{e:vis-burgers-vlasov}-\eqref{e:initial} converge to a finite-energy weak solution to the following zero-viscosity equations:
\begin{equation}\label{e:burgers-vlasov}
\left\{
\begin{array}{ll}
\displaystyle u_t+uu_x=\int_\R fvdv-u\int_\R fdv,  \\
\displaystyle f_t+v f_x+(f(u-v))_v=0.
\end{array}
\right.
\end{equation}
The relative total energy for \eqref{e:burgers-vlasov} is denoted as
\begin{equation*}
E[u, f]:=\displaystyle\frac{1}{2}\int_\R (u-\bar{u})^2dx+\frac{1}{2}\int_\R\!\int_\R f(1+v^2)dvdx,
\end{equation*}
where  smooth monotone function $\bar{u}(x)$ is constructed as
\begin{equation}\label{e:ubar}
\bar{u}=
\begin{cases}
u^+, \quad &x\geq L_0;\\
\text{monotone}, \quad &-L_0<x<L_0;\\
u^-, \quad &x\leq -L_0
\end{cases}
\end{equation}
with $L_0>0$ large. As we can see from the formula, the relative total energy is the sum of the kinetic energy of the fluid and the particle (in statistic sense). In the paper we denote $[0, \infty)$  as $\R_+$,  $\R^2=\R\times\R.$  Finite-energy weak solutions to \eqref{e:burgers-vlasov} are defined as follows.
\begin{definition}\label{d:energy-solution}
Let $(u_0, f_0)$ be  given initial data with relative finite energy with respect to the end-states $(u^{\pm}, 0)$ at infinity, i.e. $E[u_0, f_0]\leq E_0<\infty.$ For any $T\in\R_+,$ a pair of functions $u:\R\times[0, T]\rightarrow\R,$ $f:\R^2\times[0, T]\rightarrow\R_+$ is called a \textit{finite-energy weak solution} of Cauchy problem \eqref{e:burgers-vlasov} and \eqref{e:initial}-\eqref{e:uf0-asymptoic} if the following holds:
\begin{itemize}
\item[(1)] There is a bounded function $C(E_0, t)$ defined on $\R_+\times[0, T]$, which is continuous in $t$ for each $E\in\R_+$ such that for a.e. $t>0,$
\begin{equation}\label{e:energyineq}
E[u, f](t)+\int_0^t\!\!\!\int\!\!\!\int f(u-v)^2dvdxds\leq C(E_0, t).
\end{equation}
\item[(2)] For any $\phi\in C^1_c(\R\times[0, T)),$
\begin{equation}\label{e:burgersweak}
\int_\R\phi(x, 0)u_0(x)dx+\int_0^T\!\!\!\int_\R\left(u\phi_t+\frac{1}{2}u^2 \phi_x+\phi\int_\R f(v-u)dv\right)dxdt=0,
\end{equation}
and for any $\varphi\in C^1_c((\R^2\times[0, T)),$
\begin{equation}\label{e:vlasovweak}
\int_\R\!\!\int_\R\varphi(x, v, 0)f_0(x, v)dxdv+\int_0^T\!\!\!\int_\R\!\!\int_\R f\varphi_t+ fv\varphi_x+f(u-v)\varphi_vdvdxdt=0.
\end{equation}

\item[(3)]The initial data is achieved in the sense of distributions.
\end{itemize}
\end{definition}
In fact, our general idea on the definition of finite-energy weak solution is that under the condition that the initial total energy is finite the desired solution to \eqref{e:burgers-vlasov} shall also enjoys the finite-energy property, i.e. \eqref{e:energyineq} and satisfies the equations \eqref{e:burgers-vlasov} in weak sense, i.e. \eqref{e:burgersweak} and \eqref{e:vlasovweak}.

Now we are ready to state our main result.
\begin{theorem}\label{t:vanshing-limit}
Let the initial smooth functions $(u_0^\eps, f_0^\eps)$ satisfying the following conditions:
\begin{itemize}
\item[(i)] There exists $E_0>0$ such that $E[u_0^\eps, f_0^\eps]\leq E_0<\infty.$
\item[(ii)] It holds that
 \begin{align*}
 (u_0^\eps(x), f_0^\eps(x, v))\rightarrow(u_0(x), f_0(x, v)) \text{ as }\eps\rightarrow 0
 \end{align*}
 in the sense of distributions with $f_0\geq0.$
\end{itemize}
Let $(u^\eps, f^\eps)$ be the solution to the Cauchy problem \eqref{e:vis-burgers-vlasov} with initial data $(u_0^\eps, f_0^\eps)$ for any fixed $\eps>0.$ Then when $\eps\rightarrow 0$, there exists $(u, f)$ with $u(x, t)\in L^4_{loc}(\R\times[0, T])$ and $ f(x, v, t)\in L^\infty([0, T], (1+v^2)L^1(\R^2))$, which is  a finite-energy weak solution to the Cauchy problem \eqref{e:burgers-vlasov} and \eqref{e:initial}-\eqref{e:uf0-asymptoic} in the sense of Definition \ref{d:energy-solution}, along with corresponding subsequences of $u^\eps$ and $ f^\eps $ (still denoting as $(u^\eps, f^\eps)$) such that
\begin{align*}
&u^\eps\rightarrow u \text{ stongly in } L^r_{loc}(\R\times[0, T]), \text{ for } 1\leq r\leq 4, \text{ as } \eps\rightarrow 0,\\
&f^\eps\rightharpoonup f\text{ weakly in }  L^\infty([0, T], L^1(\R^2)), \text{ as } \eps\rightarrow 0.
\end{align*}

\end{theorem}

Our strategy of proving Theorem \ref{t:vanshing-limit} is to apply $L^p$ compactness framework for scalar conservation laws and study the evolution of level sets after obtaining uniform basic energy estimate and uniform $L^4_{loc}$ estimate. Regarding on the $L^p$ compactness framework for scalar conservation laws,  it is first used in \cite{S82} and then in \cite{Lu92} with some improvement. The compactness framework is also generalized for more models in \cite{YZZ98}. In the present paper, our key difficulty is the estimate of $L^4_{loc}$ boundedness of $u^\eps$, which is obtained by making full use of the flux term of Burgers' equation. To show the $L^1$ weak convergence of $f^\eps$, our technique is studying the evolution of level sets, which is also utilized to handle the convergence of approximate solutions to Vlasov-Possion equations in \cite{ACF17}, but here our novel idea is that estimate the level sets through characteristic map and our key observation is that the Jacobian of the characteristic map is uniformly bounded as time grows.

In the present paper, we denote $\int=\int_\R.$ $C$  is a constant independent of $\eps$ but may vary line to line, $C(\cdot)$ denotes a constant depending on the parameters in the bracket. The rest of the paper is organised as follows. Section \ref{s:uniform} is devoted to show the uniform estimates and the proof of Theorem \ref{t:vanshing-limit} is provided in Section \ref{s:proof}.

\section{Uniform eistimates}\label{s:uniform}

Consider the Cauchy problem \eqref{e:vis-burgers-vlasov} with initial conditions
\begin{align*}
u^\eps(x, 0)=u_0^\eps(x),\quad f^\eps(x, v, 0)=f_0^\eps(x, v)\geq0
\end{align*}
satisfying (i) and (ii) in Theorem \ref{t:vanshing-limit}. When the viscosity $\eps$ is fixed, $u_0^\eps\in C^1(\R)$, $f^\eps_0\in C^1_c(\R^2),$ according to Theorem 2.1 in \cite{DR99}, one is able to obtain the global existence and uniqueness of a smooth solution $(u^\eps, f^\eps)$ with $f^\eps\geq0.$  On the other hand, in Section 4 of \cite{G01}, the author also gained a global weak solution to \eqref{e:vis-burgers-vlasov} when initial data $(u_0^\eps, f^\eps_0)$ only enjoys finite energy property and $f_0^\eps\in (L^1\cap L^2)(\R^2)$. Here, the smooth functions  $(u_0^\eps, f^\eps_0)$  in Theorem \ref{t:vanshing-limit} are regular, and we can also cut off $f_0^\eps$ with smooth function supported in $\{(x, v)||x|+|v|\leq\frac{1}{\eps}\}$ (still denote $f_0^\eps$) to make $f_0^\eps$ compact supported and it still satisfies (i) and (ii). Additionally, the initial data satisfies \eqref{e:uf0-asymptoic},  thus it is not hard to derive that
\begin{equation}\label{e:uf-asymptoic}
\lim_{x\rightarrow\pm\infty}u^\eps(x, t)=u^{\pm},  \quad \lim_{x, v\rightarrow\pm\infty}f^\eps(x, v, t)=0.
\end{equation}
Therefore, for smooth functions $(u_0^\eps, f^\eps_0)$ given in Theorem \ref{t:vanshing-limit} as initial data, for any fixed $\eps>0$, there always exists a unique smooth solution to Cauchy problem \eqref{e:vis-burgers-vlasov} and \eqref{e:initial}-\eqref{e:uf0-asymptoic}  satisfying \eqref{e:uf-asymptoic}.

We now establish two uniform estimates for solutions $(u^\eps, f^\eps)$ with respect to the viscosity coefficient $\eps>0,$  which plays key role in our proof. For simplicity, we drop the upper index $\eps$ in this section.

\subsection{Energy estimate}

With the help of the partial dissipative effect of the source terms in \eqref{e:vis-burgers-vlasov}, for the relative total energy $E[u, f]$, we have the following lemma.
\begin{lemma}\label{l:basic-energy}
Let $E[u_0, f_0]\leq E_0<\infty$ with positive constant $E_0$ independent of $\eps.$ Then there exists a constant $C=C(E_0, t, \bar{u})$ such that
\begin{equation*}
\sup_{\tau\in[0, t]}E[u, f](\tau)+\int_0^t\!\!\!\int\!\!\!\int f(v-u)^2dvdxd\tau+\int_0^t\!\!\!\int\!\eps |u_x|^2 dxd\tau\leq C.
\end{equation*}
\end{lemma}
\begin{proof}
A direct calculation gives
\begin{align*}
\frac{d E}{dt}&=\frac{d}{dt}\int\frac{1}{2}(u-\bar{u})^2dx+\frac{d}{dt}\int\!\!\!\int\frac{1}{2}f(1+v^2)dxdv\\
&=\int(u-\bar{u})u_t dx+\int\!\!\!\int\frac{1}{2}(1+v^2) f_tdxdv.
\end{align*}
Due to
\begin{align*}
u_t=\eps u_{xx}+\int f(v-u)dv-uu_x,
\end{align*}
using \eqref{e:uf-asymptoic} and integration by parts, we have
\begin{align*}
\int(u-\bar{u})u_t dx&=\int(u-\bar{u})\eps u_{xx} dx-\int(u-\bar{u})uu_xdx+\int\!\!\!\int f(u-\bar{u})(v-u)dvdx\\
&=I_1+I_2+I_3,
\end{align*}
where
\begin{align*}
I_1&=-\!\!\int\eps(u_x-\bar{u}_x)u_x dx,\\
I_2&=-\!\!\int(u-\bar{u})uu_x,\\
I_3&=\int\!\!\int f(u-\bar{u})(v-u)dvdx.
\end{align*}
We then bound the three terms $I_i, i=1, 2, 3$ one by one.
Note that from \eqref{e:ubar}, one is easy to see that $\bar{u}_x$ is bounded and compact supported in $[-L_0, L_0],$  thus we have
\begin{equation}\label{e:i1}
I_1\leq-\int\eps |u_x|^2dx+\eps\int_{-L_0}^{L_0}|\bar{u}_x||u_x|dx\leq-\frac{1}{2}\int\eps |u_x|^2dx+C.
\end{equation}
Similarly, for $I_2$, we have
\begin{equation}\label{e:i2}
\begin{split}
I_2&=-\int[(u-\bar{u})^2(u-\bar{u})_x+\bar{u}_x(u-\bar{u})^2+(u-\bar{u})\bar{u}(u-\bar{u})_x+(u-\bar{u})\bar{u}\bar{u}_x]dx\\
&=-\int[(u-\bar{u})^2(u-\bar{u})_x+\frac{1}{2}\bar{u}_x(u-\bar{u})^2+(u-\bar{u})\bar{u}\bar{u}_x]dx\\
&\leq C\int|u-\bar{u}|^2dx+C\\
&\leq CE+C,
\end{split}
\end{equation}
and
\begin{equation}\label{e:i3}
\begin{split}
I_3&=\int\!\!\!\int fu(v-u)dvdx-\int\!\!\!\int \bar{u}f(v-u)dvdx\\
&\leq\int\!\!\!\int fu(v-u)dvdx+\frac{1}{2}\int\!\!\!\int f(v-u)^2dvdx+C\int\!\!\!\int fdvdx.
\end{split}
\end{equation}
Furthermore, using
$$f_t=-(fv)_x-(f(u-v))_v$$
and \eqref{e:uf-asymptoic} we gain
\begin{equation}\label{e:f1}
\begin{split}
\int\!\!\!\int\frac{1}{2}(1+v^2) f_tdxdv&=-\int\!\!\!\int\frac{1}{2}(1+v^2) [(fv)_x+(f(u-v))_v]dxdv\\
&=\int\!\!\!\int fv(u-v)dvdx.
\end{split}
\end{equation}
Putting \eqref{e:i1}, \eqref{e:i2}, \eqref{e:i3} and \eqref{e:f1} together gives
\begin{align*}
\frac{d E}{dt}\leq CE+C-\frac{1}{2}\int\eps |u_x|^2dx -\frac{1}{2}\int\!\!\!\int f(u-v)^2dvdx.
\end{align*}
Then directly application of Gronwall's inequality contributes to the lemma.
\end{proof}

\subsection{Higher integrability of velocity}

Although by Lemma \ref{l:basic-energy}, one has $u\in L^2,$ we require much higher regularity of $u$. Taking value of the flux term in Burgers' equation, we improve the regularity of $u$ to be $L^4_{loc}$.
\begin{lemma}\label{l:u-l4local}
Let $E[u_0, f_0]\leq E_0<\infty$ with positive constant $E_0$ independent of $\eps.$ Then for any compact set $K\subset\R$ and all $t>0$, there exists a constant $C=C(E_0, K, \bar{u}, t),$ independent of $\eps$ such that
\begin{align*}
\int_0^t\int_K u^4dxd\tau\leq C.
\end{align*}
\end{lemma}
\begin{proof}
 Let $\va$ be an arbitrary smooth compactly supported function such that $\va|_K=1$ and $0\leq\va\leq1.$ Motivated by the proof of Lemma 3.3 in \cite{CP10}, multiplying the viscous Burgers' equation by $\va$ and then integrating with respect to space variable over $(-\infty, x)$, we gain
\begin{align*}
\frac12u^2\va=&\eps u_x\va-\left(\int_{-\infty}^x u\va dy\right)_t+\int_{-\infty}^x
\left(\frac{1}{2}u^2\va_x-\eps u_x\va_x\right)dy\\
&+\int_{-\infty}^x\!\!\va\int f(v-u)dvdy.
\end{align*}
Multiply the above equation by $u^2\va$ and use the viscous Burgers' equation to get
\begin{align*}
\frac12u^4\va^2&=\eps u^2u_x\va^2-\left(u^2\va\int_{-\infty}^xu\va dy\right)_t+2\eps uu_{xx}\va\int_{-\infty}^xu\va dy\\
&\quad-2u^2u_x\va\int_{-\infty}^xu\va dy+2u\va\int f(v-u)dv\int_{-\infty}^xu\va dy\\
&\quad +u^2\va\int_{-\infty}^x
\left(\frac{1}{2}u^2\va_x-\eps u_x\va_x\right)dy+u^2\va\int_{-\infty}^x\!\!\va\int f(v-u)dvdy.
\end{align*}
Integrating over $\R\times(0, t)$ gives

\begin{align*}
\frac12\int_0^t\!\!\int u^4\va^2dxd\tau=\sum_{i=1}^5J_i,
\end{align*}
with
\begin{align*}
J_1&=\int_0^t\!\!\int\left[\eps u^2u_x\va^2
+2\eps uu_{xx}\va\int_{-\infty}^xu\va dy-u^2\va\int_{-\infty}^x\eps u_x\va_xdy\right]dxd\tau,\\
J_2&=\int\left(u_0^2\va\int_{-\infty}^xu_0\va dy\right)dx-\int\left(u^2\va\int_{-\infty}^xu\va dy\right)dx,\\
J_3&=\int_0^t\!\!\int\left[\frac{1}{2}u^2\va\int_{-\infty}^xu^2\va_xdy
-2u^2u_x\va\int_{-\infty}^xu\va dy\right]dxd\tau,\\
J_4&=\int_0^t\!\!\int\left[2u\va\int f(v-u)dv\int_{-\infty}^xu\va dy\right]dxd\tau,\\
J_5&=\int_0^t\!\!\int\left(u^2\va\int_{-\infty}^x\!\!\va\int f(v-u)dvdy\right)dxd\tau.
\end{align*}
In the following, we will estimate $J_i, i=1,\cdots, 5$ one by one.
For $J_1, $ an application of integration by parts yields
\begin{align*}
J_1=&\int_0^t\!\!\int\eps u^2u_x\va^2dxd\tau-\int_0^t\!\!\int\left(
u^2\va\int_{-\infty}^x\eps u_x\va_xdy\right)dxd\tau\\
&-\int_0^t\!\!\int\left(2\eps u_x^2\va\int_{-\infty}^xu\va dy+2\eps u^2u_x\va^2+2\eps uu_x\va_x\int_{-\infty}^xu\va dy\right)dxd\tau,\\
\leq&\delta\int_0^t\!\!\int u^4\va^2 dxd\tau+C(\delta, E_0, K, \bar{u}, t)\int_0^t\!\!\int\eps |u_x|^2 dxd\tau\\
\leq&\delta\int_0^t\!\!\int u^4\va^2 dxd\tau+C(\delta, E_0, K,  \bar{u}, t)
\end{align*}
with small $\delta$ to be determined, where we have used H\"older's inequality, Lemma \ref{l:basic-energy}  and
\begin{align*}
\left|\int_{\infty}^xu\va dy\right|\leq\int (u-\bar{u})^2dx+C(K, \bar{u})\leq C(E_0, K, \bar{u}).
\end{align*}
Again applying basic energy estimate and H\"older's inequality to $J_2$ and $J_3$, we have
\begin{align*}
J_2+J_3\leq \delta\int_0^t\!\!\int u^4\va^2 dxd\tau+C(\delta, E_0, K, \bar{u}, t).
\end{align*}
For $J_4$, the following inequality
\begin{align*}
\int fu^2dv\leq2\int f(v-u)^2 dv+2\int fv^2dv
\end{align*}
implies
\begin{align*}
\int_0^t\!\!\int\!\!\int fu^2 dvdxd\tau\leq C(E_0, \bar{u}, t).
\end{align*}
Thus we have
\begin{align*}
\int_0^t\!\!\int\left|u\int f(v-u)dv\right|dxd\tau
&\leq\int_0^t\!\!\int\left(\int fu^2dv\right)^{\frac{1}{2}}\left(\int f(v-u)^2 dv\right)^{\frac{1}{2}}dxd\tau\\
&\leq  C(E_0, \bar{u},  t),
\end{align*}
which then gives $J_4\leq C(E_0,  K, \bar{u}, t).$
Similarly, we can derive
\begin{align*}
\left|\int f(v-u)dv\right|\leq \left(\int fdv\right)^{\frac{1}{2}}\left(\int f(v-u)^2 dv\right)^{\frac{1}{2}}.
\end{align*}
Hence we gain $J_5\leq C(E_0, K, \bar{u}, t).$  Collecting all the estimates of $J_i, i=1, \cdots, 5$ and taking $\delta\leq\frac{1}{16} $ yield the lemma.
\end{proof}

\section{Vanishing viscosity limit}\label{s:proof}

In this section, we will use the estimates in Section \ref{s:uniform} to establish the convergence of $(u^\eps, f^\eps),$ whose limit is just a finite-energy weak solution to Cauchy problem \eqref{e:burgers-vlasov} and \eqref{e:initial}-\eqref{e:uf0-asymptoic}. Based on the uniform estimates Section \ref{s:uniform}, we get the following:
\begin{align}
&\sup_{\tau\in[0, t]}E[u^\eps, f^\eps](\tau)\leq C, \label{eq:total-energy} \\
&\int_0^t\!\!\!\int\!\!\!\int f^\eps(v-u^\eps)^2dvdxd\tau,\label{eq:fvu-bound}\\
&\int_0^t\!\!\!\int\!\eps |u^\eps_x|^2 dxd\tau\leq C, \label{eq:u-vis-bound}\\
&\int_0^t\int_K (u^\eps)^4dxd\tau\leq C, \text{ for any compact set } K\subset\R. \label{eq:u-l4-local-bound}
\end{align}
We then divide the proof into three subsections. In Section \ref{s:limit-f} and Section \ref{s:limit-u}, we will apply the uniform estimates \eqref{eq:u-vis-bound}, \eqref{eq:u-l4-local-bound}  and \ref{eq:total-energy} to show the convergence of $f^\eps$ and $u^\eps$ respectively. In Section \ref{s:limit-equation} we will prove the obtained limit is our desired solution.

\subsection{Limit of  distribution function}\label{s:limit-f}

To show $f^\eps$ is weakly compact in $L^1(\R^2),$ a.e. $t\in[0, T],$ one can study the  evolution of  level sets of $f^\eps(x, v, t)$ and $f_0^\eps(x, v),$ which is motivated by Steps 1-3 in the proof of Theorem 2.7 in \cite{ACF17 }. For our case, the estimate on the level sets is done through the characteristic map. Our key observation is that the Jacobian of the characteristic map remains uniformly bounded as time grows.

Assume $|\{f_0=k\}|=0$ for every $k\in\mathbb{N}.$ (Otherwise one can consider $\tau+k$ in place of $k$  for some $\tau\in(0, 1).$)  From the strong convergence of $f_0^\eps,$ one could deduce that when $\eps\rightarrow0,$
\begin{align*}
f_0^{\eps, k}=:\mathbf{1}_{\{k\leq f_0^\eps<k+1\}}f_0^\eps\rightarrow f_0^k:=\mathbf{1}_{\{k\leq f_0<k+1\}}f_0 \text{ in } L^1(\R^2) \text{ for any } k\in\mathbb{N},
\end{align*}
where $\mathbf{1}_A$ is the characteristic function of set $A.$ We shall also analyze the evolution of corresponding level sets of $f^\eps(x, v, t)$.  In fact, for Vlasov equation
$$f^\eps_{t}+(f^\eps v)_{x}+(f^\eps (u^\eps-v))_{v}=0$$
with $u^\eps$ being a smooth function,  the equation can be rewritten as
\begin{equation*}
f^\eps_{t}+vf^\eps_{x}+(u^\eps-v)f^\eps_{v}=f^\eps,  \quad  f^\eps(x, v, 0)=f^\eps_{0}(x,v),
\end{equation*}
which has a unique smooth solution
\begin{equation}\label{e:f}
\displaystyle f^\eps(x,v,t)=f^\eps_{0}(X^\eps(0; x,v,t), V^\eps(0; x,v,t))e^t,
\end{equation}
where  $X(s;x,v,t), V(t;x,v,t)$ are backward characteristic curves satisfying
\begin{align}
&\frac{dX^\eps(s;x,v,t)}{ds}=V^\eps(s;x,v,t), \quad  X^\eps(t;x,v,t)=x; \label{e:x} \\
&\frac{dV^\eps(s;x,v,t)}{ds}=u^\eps(s,X^\eps(s;x,v,t))-V^\eps(s;x,v,t), \quad  V^\eps(t;x,v,t)=v. \label{e:v}
\end{align}
It is not hard to see that $X^\eps, V^\eps$ are well-defined from the theory of ordinary differential equation (ODE). From \eqref{e:x} and \eqref{e:v}, one is able to show that the Jacobian $J(t)=\det \nabla_{x, v}(X^\eps, V^\eps)$ of the map $\mathcal{J}(s):(x, v)\mapsto(X^\eps, V^\eps)$ is nonnegative and satisfies the following ODE
\begin{equation*}
\left\{
\begin{array}{ll}
\displaystyle \frac{d J(t)}{dt}=J(t)\text{div}_{x, v}(X^\eps, V^\eps)=-J(t),\\
\displaystyle J(t)=1,
\end{array}
\right.
\end{equation*}
so $J(\tau)=e^{t-\tau}$ for any $\tau\in [0, t].$  For any $t>0,$ noting \eqref{e:f}, set
\begin{align*}
f^{\eps, k}(x, v, t)= e^t\mathbf{1}_{\{k\leq f^\eps_0 \circ \mathcal{J}(0)<k+1\}}f^\eps_0\circ\mathcal{J}(0).
\end{align*}
Then we have $f^{\eps, k}$ is a weak solution to the Vlasov equation and
\begin{align*}
\int\!\!\int f^{\eps, k}dvdx=&\int\!\!\int e^t\mathbf{1}_{\{k\leq f^\eps_0 \circ \mathcal{J}(0)<k+1\}}f^\eps_0\circ\mathcal{J}(0) dvdx\\
=&\int\!\!\int e^t\mathbf{1}_{\{k\leq f^\eps_0<k+1\}}f^\eps_0 J(0)^{-1}dV^\eps dX^\eps\\
=&\int\!\!\int f^{\eps, k}_0 dV^\eps dX^\eps,
\end{align*}
hence for any $t>0, $
$$\|f^{\eps, k}(x, v, t)\|_{L^1(\R^2)}=\|f^{\eps, k}_0(x, v)\|_{L^1(\R^2)}.$$
It is easy to find that $0\leq f^{\eps, k}\leq (k+1)e^T, $ thus up to subsequences, for any $k\in\mathbb{N}.$
\begin{align*}
f^{\eps, k}\rightharpoonup f^k \text{ weakly* in  } L^{\infty}(\R^2\times[0, T]), \text{ as } \eps\rightarrow0.
\end{align*}
Similar to \cite{ACF17 }, one can use the test function $\phi(t)\mathbf{1}_K\text{sign}(f^k)(x, v, t)$ for any compact subset $K\subset\R^2$ and any $\phi\in C_c^\infty(\R_+)$ in the above weak convergence to show
$$\|f^{k}(x, v, t)\|_{L^1(\R^2)}\leq\|f^{k}_0(x, v)\|_{L^1(\R^2)}$$
for almost all $t$. We define
\begin{align*}
f(x, v, t):=\sum_{k=0}^\infty f^k(x, v, t), \text{ for } (x, v, t)\in\R^2\times[0, T],
\end{align*}
then it is easy to derive
$$\|f\|_{L^1(\R^2)}\leq\sum_{k=0}^\infty \|f^{k}(x, v, t)\|_{L^1(\R^2)}\leq \sum_{k=0}^\infty\|f^{k}_0(x, v)\|_{L^1(\R^2)}=\|f_0\|_{L^1(\R^2)}.$$
We then prove
\begin{equation}\label{e:f-convergent}
f^{\eps}\rightharpoonup f \text{ weakly in  } L^{\infty}([0, T], L^1(\R^2)), \text{ as } \eps\rightarrow0.
\end{equation}
In fact, for any $\va\in L^{\infty}(\R^2),$ we derive
\begin{align*}
&\left|\int\!\!\int \va(f^\eps-f)dxdv\right|=\left|\sum_{k=0}^\infty\int\!\!\int \va(f^{\eps, k}-f^k)dxdv\right|\\
\leq&\left|\sum_{k=0}^{k_0-1}\int\!\!\int \va(f^{\eps, k}-f^k)dxdv\right|+\sum_{k=k_0}^\infty\int\!\!\int |\va||f^{\eps, k}|dxdv+
\sum_{k=k_0}^\infty\int\!\!\int |\va||f^k|dxdv.
\end{align*}
The first term converges to zero as $\eps\rightarrow0$ due to the weak convergence of $f^{\eps, k}$ for any finite $k_0.$ The last two terms can be estimated by
\begin{align*}
&\sum_{k=k_0}^\infty\int\!\!\int |\va||f^{\eps, k}|dxdv+
\sum_{k=k_0}^\infty\int\!\!\int |\va||f^k|dxdv\\
\leq &\|\va\|_{L^\infty(\R^2)}\left(\|f_0^\eps\mathbf{1}_{\{f_0^\eps\geq k_0\}}\|_{L^1(\R^2)}+\|f_0\mathbf{1}_{\{f_0\geq k_0\}}\|_{L^1(\R^2)}\right),
\end{align*}
which converges to zero as $k_0\rightarrow\infty$ thanks to the fact that  $f^{\eps}_0$ and $f_0$ are bounded in $L^1(\R^2)$.
Finally, we obtain \eqref{e:f-convergent}.

\subsection{Limit of velocity}\label{s:limit-u}

To show the convergence of $u^\eps$, we will utilize the $L^p$ compactness framework for Burgers' equation. Thus we first recall
a proposition on such framework, which is resulting from \cite{Lu92}. The framework is shown mainly by div-curl lemma and compactness of some entropies for Burgers' equation.
\begin{proposition}\label{p:framework}
Let $u^\eps(x, t)$ satisfy the following two conditions:
\begin{itemize}
\item[(C1)] $u^\eps(x, t)$ is uniformly bounded in $L^p_{loc}(\R\times[0, T])$ for some $p>2$;
\item[(C2)] Both $\partial_t I_n(u^\eps(x, t))+\partial_x F_n(u^\eps(x, t))$ and  $\partial_t F_n(u^\eps(x, t))+\partial_x\Phi_n(u^\eps(x, t))$ lie in a compact set of $H^{-1}_{loc}(\R\times[0, T])$ with respect to $\eps$ for any $n\in\mathbb{N},$ where
\begin{align*}
&I_n(u)=\begin{cases}u, &\text{ when } |u|\leq n,\\
0, &\text{ when } |u|\geq 2n,
\end{cases}
\text{ and } I_n\in C^2(\R), \quad |I_n(u)|\leq |u|, \quad |I_n'(u)|\leq 2,\\
&F_n(u)=\int_0^u I_n'(s)sds, \quad \Phi_n(u)=\int_0^u F'_n(s)sds.
\end{align*}
\end{itemize}
Then there exists a subsequence (still denoted $u^\eps$) such that $u^\eps\rightarrow u$ almost everywhere and strongly in $L^r_{loc}(\R\times[0, T])$ for all $1\leq r\leq p.$
\end{proposition}
With such $L^p$ framework, we only need to verify (C1)-(C2) to show the convergence of $u^\eps.$ It is easy to see from \eqref{eq:u-l4-local-bound}, we have
$$ u^\eps\in L^4_{loc}(\R\times[0, T]),$$
thus (C1) is satisfied by $u^\eps(x, t)$ for $p=4.$

To verify (C2), we also require an important lemma: Murat's lemma, which is useful in proving compactness of some sequences.
\begin{lemma}\label{l:murat} (Murat's Lemma \cite{Chen86, Tar79})
Let $\Omega\in\mathbb{R}^n$ be a open bounded subset, $D_1$ be a compact
set in $W^{-1,a}_{loc}(\Omega) $, $D_2$ be a bounded set in $W_{loc}^{-1,b}(\Omega)$ for some constants $a, b$ satisfying
$1<a\leq2<b.$. Furthermore, let $D_0\subset\mathcal{D}(\Omega)$ such that $D_0\subset D_1\cap D_2.$  Then there exists $D_*$, a compact set in $H^{-1}_{loc}(\Omega)$ such
that $D_0\subset D_* $.
\end{lemma}
Then we turn to verify (C2). Noting that both  $I_n(u) $ and $F_n(u)$ are $C^2$ compact supported functions of $u,$  one gets
\begin{equation}
\label{e:w-1-bound}
\left.\begin{array}{ll}
\partial_t I_n(u^\eps(x, t))+\partial_x F_n(u^\eps(x, t)),\\
\partial_t F_n(u^\eps(x, t))+\partial_x\Phi_n(u^\eps(x, t))
\end{array}
\right\}\text{ are bounded in } W^{-1, \infty}_{loc}(\R\times[0, T]).
\end{equation}
Furthermore, from
\begin{align*}
\partial_t F_n(u^\eps)+\partial_x\Phi_n(u^\eps)&=\eps u^\eps_{xx} F_n'(u^\eps)+F_n'(u^\eps)\int\!\! f^\eps(v-u^\eps)dv\\
&=(\eps u^\eps_xF'_n(u^\eps))_x-\eps (u^\eps_x)^2 F''_n(u^\eps)+F_n'(u^\eps)\int\!\! f^\eps(v-u^\eps)dv,
\end{align*}
along with $|F_n'(u^\eps)|\leq |I'_n(u^\eps)u^\eps|\leq C(n),$  and $|F_n''(u^\eps)|\leq C(n),$  one can derive
\begin{equation}
\label{e:w-1-alpha-1}
\partial_t F_n(u^\eps)+\partial_x\Phi_n(u^\eps) \text{ is compact in } W^{-1, \alpha}_{loc}(\R\times[0, T]) \text{ for some } \alpha\in(1, 2).
\end{equation}
Indeed, using $\sqrt{\eps}u_x^\eps\in L^2(\R\times[0, T])$  and $|F_n'(u^\eps)|\leq C(n),$ we get $(\eps u^\eps_xF'_n(u^\eps))_x$ is compact in $H^{-1}_{loc}(\R\times[0, T]).$ Employing Lemma \ref{l:basic-energy} we also have
$$-\eps (u^\eps_x)^2 F''_n(u^\eps)+F_n'(u^\eps)\int\!\! f^\eps(v-u^\eps)dv\in L^1(\R\times[0, T]),$$
 which also implies that it is compact in
$W^{-1, \alpha}_{loc}(\R\times[0, T])$ for some $\alpha\in(1, 2)$ by embedding theorem and Schauder theorem, so we obtain \eqref{e:w-1-alpha-1}.  Similarly, one can also gain
\begin{equation}
\label{e:w-1-alpha-2}
\partial_t I_n(u^\eps)+\partial_x F_n(u^\eps)\text{ is compact in } W^{-1, \alpha}_{loc}(\R\times[0, T]) \text{ for some } \alpha\in(1, 2).
\end{equation}
Combining with \eqref{e:w-1-bound}, \eqref{e:w-1-alpha-1} and \eqref{e:w-1-alpha-2}, applying Murat's Lemma (see Lemma \ref{l:murat}), one gets (C2). Therefore, applying Proposition \ref{p:framework} to $u^\eps,$  one can seek a $u(x, t)\in L^4_{loc}(\R\times[0, T])$ and a subsequence of $u^\eps$ (still denoted as $u^\eps$) such that
\begin{align*}
&u^\eps\rightarrow u \text{ a.e. } \R\times[0, T],\\
&u^\eps\rightarrow u \text{ stongly in } L^r_{loc}(\R\times[0, T]), \text{ as } \eps\rightarrow 0, \text{ for } 1\leq r\leq4.
\end{align*}

\subsection{Limit of equations and conclusions}\label{s:limit-equation}

Before taking limit of equations and proving that $(u, f)$ is a weak solution of the Cauchy problem  \eqref{e:burgers-vlasov} and \eqref{e:initial}-\eqref{e:uf0-asymptoic}, we shall  first get  the convergences of nonlinear terms in the equations: $\int f^\eps dv$, $\int f^\eps vdv$ and $u^\eps\int f^\eps dv.$

\textit{(1) Convergence $~~~~\displaystyle\!\!\int f^\eps vdv\rightarrow\int fvdv$.}   From energy estimate and the lower  semi-continuity of kinetic energy, we deduce that
\begin{align}\label{e:fvenergy}
\int\!\!\int v^2f dxdv\leq\liminf_{\eps\rightarrow0}\int\!\!\int v^2f^\eps dxdv\leq C.
\end{align}
Let $\chi(s)=\mathbf{1}_{[-1, 1]}(s).$  For any $\va\in C_c^\infty(\R),$ for any  $L>0$,  inspired by \cite{ACF17},  we observe that
\begin{align*}
\int\left(\int f^\eps vdv-\int fvdv\right)\va dx=&\int\!\!\int (f^\eps-f)v\chi(\frac{v}{L})\va dvdx\\
&+\int\!\!\int (f^\eps v(1-\chi(\frac{v}{L}))\va dvdx\\
&-\int\!\!\int fv(1-\chi(\frac{v}{L}))\va dvdx.
\end{align*}
The first term in the right hand side converges to 0 due to the weak convergence of $f^\eps$ to $f$ in $L^1(\R^2).$ Thanks to \eqref{e:fvenergy}, the remained two terms can be estimated  as
\begin{align*}
\left|\int\!\!\int (f^\eps v(1-\chi(\frac{v}{L}))\va dvdx\right|\leq\frac{\|\va\|_{L^\infty}}{L}\int\!\!\int f^\eps v^2 dvdx\leq \frac{C\|\va\|_{L^\infty}}{L},\\
\left|\int\!\!\int (fv(1-\chi(\frac{v}{L}))\va dvdx\right|\leq\frac{\|\va\|_{L^\infty}}{L}\int\!\!\int f v^2 dvdx\leq \frac{C\|\va\|_{L^\infty}}{L}.
\end{align*}
Letting $L$ go to infinity, we can get
\begin{align*}
\int f^\eps vdv\rightharpoonup \int fvdv  \text{ weakly in } L^\infty([0, T], L^1(\R)).
\end{align*}

\textit{(2) Convergence  $~~\!\!\int f^\eps dv\rightarrow \!\!\int fdv$.}  Similar to Step 1, we can get
\begin{align*}
\int f^\eps dv\rightharpoonup \int fdv  \text{ weakly in } L^\infty([0, T], L^1(\R)).
\end{align*}

\textit{(3) Convergence  $~~\displaystyle u^\eps\!\!\int f^\eps dv\rightarrow u\!\!\int fdv$.}  We easily get from the energy estimate that for any $T\in\R_+,$
\begin{align*}
\int_0^T\!\!\int (u^\eps)^2 \!\!\int f^\eps dxdv\leq 2\int_0^T\!\!\int\!\!\int v^2f^\eps dxdv+2\int_0^T\!\!\int\!\!\int (u^\eps-v)^2 f^\eps dxdv\leq C.
\end{align*}
Due to the semicontinuity  of the integral functional and the strong compactness of $u^\eps$ and weak compactness of $~~\displaystyle\!\!\int f^\eps dv,$ one also gets
\begin{align}\label{e:fuenergy}
\int_0^T\!\!\int u^2\!\!\int f dxdv\leq\liminf_{\eps\rightarrow0}\int_0^T\!\!\int (u^\eps)^2\!\!\int  f^\eps dxdv\leq C.
\end{align}
Following  the same strategy of proving the convergence of $~~\displaystyle\!\!\int vf^\eps dv,$  denoting $\chi(s)=\mathbf{1}_{[-1, 1]}(s),$  we gain for any $\va\in C^\infty_c(\R\times(0, T)),$ for arbitrary $L>0,$
\begin{align*}
&\int_0^T\!\!\!\int\left(u^\eps\int f^\eps dv-u\int fdv\right)\va dxdt\\
=&\int_0^T\!\!\int\!\!\int \left(u^\eps\chi(\frac{u^\eps}{L})\int f^\eps dv-u\chi(\frac{u}{L})\int fdv\right)\va dvdx\\
&+\int_0^T\!\!\int\!\!\int u^\eps f^\eps (1-\chi(\frac{u^\eps}{L})\va dvdx\\
&-\int_0^T\!\!\int\!\!\int fu(1-\chi(\frac{u}{L})\va dvdx.
\end{align*}
For the first term in the right hand side of the above integrals, since we have uniform bounds on the integrands, by Dominated Convergence Theorem it converges to 0 as $\eps\rightarrow0.$    The last two terms  can be estimated through \eqref{e:fuenergy} as before,
\begin{align*}
\left|\int_0^T\!\!\!\int\!\!\int f^\eps u^\eps(1-\chi(\frac{u^\eps}{L})\va dvdx\right|\leq\frac{\|\va\|_{L^\infty}}{L}\int_0^T\!\!\!\int\!\!\int f^\eps (u^\eps)^2 dvdx\leq \frac{C\|\va\|_{L^\infty}}{L},\\
\left|\int_0^T\!\!\!\int\!\!\int fu(1-\chi(\frac{u}{L})\va dvdx\right|\leq\frac{\|\va\|_{L^\infty}}{L}\int_0^T\!\!\!\int\!\!\int f u^2 dvdx\leq \frac{C\|\va\|_{L^\infty}}{L},
\end{align*}
both of which go to 0 upon letting  $L\rightarrow\infty.$

Now we are in a position to show $(u, f)$ is a finite-energy weak solution to Cauchy problem \eqref{e:burgers-vlasov} and \eqref{e:initial}-\eqref{e:uf0-asymptoic}.

\textit{(1) Weak solutions.} It suffices to show \eqref{e:burgersweak} and \eqref{e:vlasovweak} hold for $(u, f).$ Here we only show \eqref{e:burgersweak} by the uniform estimate  \eqref{eq:u-vis-bound}, since \eqref{e:vlasovweak} can be verified similarly.  Multiplying the first equation in \eqref{e:vis-burgers-vlasov} by $\phi\in C^\infty_c(\R\times[0, T))$, integrating over $\R\times[0, T]$, and employing integration by parts we obtain
\begin{align*}
&\int_\R\phi(x, 0)u^\eps_0(x)dx+\int_0^T\!\!\!\int_\R\left(u^\eps\phi_t+\frac{1}{2}(u^\eps)^2 \phi_x+\phi\int_\R f^\eps(v-u^\eps)dv\right)dx\\
&\qquad -\eps\int_0^T\!\!\!\int u^\eps_x\phi_x dxdt=0,
\end{align*}
For the last term in the left hand side, it follows from \eqref{eq:u-vis-bound} that
\begin{align*}
\left|\eps\int_0^T\!\!\!\int u^\eps_x\phi_x dxdt\right|\leq\sqrt{\eps}\left(\int_0^T\!\!\!\int\eps (u^\eps_x)^2dxdt\right)^{\frac{1}{2}}\left(\int_0^T\!\!\!\int\phi_x^2dxdt\right)^{\frac{1}{2}}\leq C\sqrt{\eps},
\end{align*}
which goes to 0 by letting $\eps\rightarrow0.$  The convergence of the other terms have already obtained, thus we have \eqref{e:burgersweak}. Hence, the obtained limit  $(u, f)$ is a weak solution to \eqref{e:burgers-vlasov}.

\textit{(2) Finite energy.} We also show the obtained limit functions also enjoy the finite energy property. Obviously, from  almost everywhere convergence of $u^\eps$ to $u$ and Lemma \ref{l:basic-energy}, we have
$$u^\eps-\bar{u}\rightarrow u-\bar{u} \text{ strongly in } L^2(\R).$$
Hence by the convexity of energy we gain
\begin{align*}
\int(u-\bar{u})^2dx\leq\liminf_{\eps\rightarrow0}\int(u^\eps-\bar{u})^2dx\leq C.
\end{align*}
Besides,
\begin{align*}
\int_0^T\!\!\!\int\!\!\!\int f(u-v)^2dvdxdt\leq 2\int_0^T\!\!\!\int\!\!\!\int fu^2dvdxdt+2\int_0^T\!\!\!\int\!\!\!\int fv^2dvdxdt\leq C.
\end{align*}
Combing with \eqref{e:fvenergy}, we gain \eqref{e:energyineq}.

Therefore, $(u, f)$ is a finite-energy weak solution to Cauchy problem \eqref{e:burgers-vlasov} and \eqref{e:initial}-\eqref{e:uf0-asymptoic}. Besides, it is easy to verify (3) in Definition \ref{d:energy-solution} for $(u, f)$ by the smoothness and compactness conditin (ii) of $(u_0^\eps, f_0^\eps)$ in Theorem \ref{t:vanshing-limit}. The proof of Theorem \ref{t:vanshing-limit} is then completed.

\section*{Acknowledgments}
The research of the W. Cao is supported by ERC Grant Agreement No. 724298 and
he also thanks for the hospitality of Max-Plank Institute for Mathematics in the Sciences.
The work of T. Wang is partially supported by the NNSFC  grant No. 11601031.

\bigskip