text:
\section{Introduction}\label{sec:intro}
This article is concerned about the following constrained convex minimization problem, which captures a surprisingly broad set of problems in various disciplines \cite{Bertsekas1989b,Chandrasekaranm2012,McCoy2014,Wainwright2014}:
\begin{equation}\label{eq:separable_convex}
  f^{\star} := \min_\xb\left\{ f(\xb): \Ab\xb = \bb, \xb\in\Xc \right \},
\end{equation}
where $f : \R^n \to \R\cup\set{+\infty}$ is a proper, closed and convex function; $\Xc \subseteq\R^n$ is a nonempty, closed and convex set; and $\Ab\in\R^{m\times n}$ and $\bb\in\R^m$ are known.
In the sequel, we develop efficient numerical methods to approximate an optimal solution $\xb^\star$ to \eqref{eq:separable_convex} and rigorously characterize how common structural assumptions on \eqref{eq:separable_convex} affect the efficiency of the methods.

\subsection{Scalable numerical methods for \eqref{eq:separable_convex} and their limitations}
In principle, we can obtain high accuracy solutions to \eqref{eq:separable_convex} through an equivalent unconstrained problem \cite{Boyd2004,Nocedal2006}. For instance, when $\Xc$ is absent and $f$ is smooth, we can eliminate the linear constraint $\Ab\xb = \bb$ by using a projection onto the null-space of $\Ab$ and then applying well-understood smooth minimization techniques. Whenever available, we can also exploit barrier representations of the constraints $\Xc$ and avoid non-smooth $f$ via reformulations, such as \emph{lifting}, as in the interior point method  using {disciplined convex programming} \cite{Boyd2004,Grant2004,Nemirovski2008,Nesterov2004}. While the resulting smooth and unconstrained problems are simpler than \eqref{eq:separable_convex} in theory, the numerical efficiency of the overall strategy severely  suffers  from the curse-of-dimensionality as well as the loss of the numerical structures in the original formulation.

Alternatively, we can obtain low- or medium-accuracy solutions when we augment the objective $f(\xb)$ with simple penalty functions on the constraints. For instance, we can solve
\begin{equation}\label{eq: aug}
  \min_\xb\left\{ f(\xb) + (\rho/2)\|\Ab\xb - \bb\|_2^2 ~:~ \xb\in\Xc \right \},
\end{equation}
where $\rho>0$ is a penalty parameter.
Despite the fundamental difficulties in choosing the penalty parameter, this approach enhances our computational capabilities as well as numerical robustness since we can apply modern proximal gradient, alternating direction, and primal-dual methods. Intriguingly, the scalability of virtually all these solution algorithms rely on three key structures that stand out among many others:

\paragraph{Structure 1 (\textbf{Decomposability}): } We say that the constrained problem \eqref{eq:separable_convex} is $p$-\textit{decomposable} if the objective function $f$ and the feasible set $\Xc$ can be represented as follows
\begin{equation}\label{eq:separable_structure}
f(\xb) := \sum_{i=1}^pf_i(\xb_i), ~~\textrm{and}~~ \Xc := \prod_{i=1}^p\Xc_i,
\end{equation}
where $\xb_i\in\R^{n_i}$, $\Xc_i\in\R^{n_i}$, $f_i : \R^{n_i}\to\R\cup\set{+\infty}$ is proper, closed and convex for $i=1,\dots, p$, and $\sum_{i=1}^pn_i = n$.
Decomposability immediately supports parallel and distributed implementations in synchronous hardware architectures. This structure arises naturally in linear programming, network optimization, multi-stages models and distributed systems \cite{Bertsekas1989b}. With decomposability, the problem \eqref{eq:separable_convex} is also referred to as a monotropic convex program \cite{Rockafellar1985}.

\paragraph{Structure 2 (\textbf{Proximal tractability}):} Unconstrained problems can still pose significant difficulties in numerical optimization when they include non-smooth terms. However, many non-smooth problems (e.g., of the form \eqref{eq: aug}) can be solved nearly as efficiently as smooth problems, provided that the computation of the proximal operator is \textbf{tractable}\footnote{It can be solved in a closed form, low computational cost or polynomial time.} \cite{Beck2009,Parikh2013,Rockafellar1976b}:
\begin{equation}\label{eq: prox}
  \mathrm{prox}_{\lambda f}(\xb) := \mathrm{arg}\min_{\zb\in\Xc}\set{ f(\zb) + (1/(2\lambda))\Vert\zb - \xb\Vert_2^2},
\end{equation}
where $\lambda>0$ is a constant. While the proximal operators simply use $\Xc = \mathbb{R}^n$ in the canonical setting, we employ \eqref{eq: prox} to do away with the $\Xc$-feasibility of the algorithmic iterates. Many smooth and non-smooth functions  support efficient proximal operators \cite{Chandrasekaranm2012,Combettes2005,McCoy2014,Wainwright2014}.
Clearly, decomposability proves useful in the computation of \eqref{eq: prox}.

\paragraph{Structure 3 (\textbf{Special function classes}):} Often times, the function $f$ in \eqref{eq:separable_convex} or the individual terms $f_i$ in \eqref{eq:separable_structure} possess additional properties that can enhance numerical efficiency. Table \ref{eq: structured properties} highlights common properties that are typically (but not necessarily) associated with function smoothness. These structures provide iterative algorithms with analytic upper and lower bounds on the objective (or its gradient), and aid the theoretical design of their iterations as well as their practical step-size and momentum parameter selection \cite{Beck2009,Boyd2004,Nesterov2004,Nocedal2006,Tran-Dinh2013a}.
\begin{table}[!ht]
\begin{center}
\caption{Special convex function classes. In the optimization literature, we refer to $L,\sigma$, and $\nu$ as the Lipschitz, strong convexity, and barrier parameters, respectively.}\label{eq: structured properties}
\vskip0.25cm
\begin{tabular}{c|l|c} \toprule
\textbf{Class}   &  \textbf{Name}              &  \textbf{Property} \\
                             &      &  $\xb, \yb \in \dom{f}, ~\vb \in\mathbb{R}^n, 0\leq \sigma \leq L <+\infty$ \\ \cmidrule{1-3}
$\mathcal{F}_L$    & Lipschitz gradient     &  $\norm{\nabla f(\xb) - \nabla f(\yb)}_{*} \leq L \norm{\xb-\yb} $\\ \cmidrule{1-3}
$\mathcal{F}_\sigma$  & Strong convexity   & $\frac{\sigma}{2}\norm{\xb-\yb}^2 + f(\xb) + \nabla f(\xb)^T(\yb-\xb)  \leq f(\yb)$\\ \cmidrule{1-3}
$\mathcal{F}^2$    & Standard self-concordant     &  $\abs{\varphi^{\prime\prime\prime}(t)} \leq 2 \varphi^{\prime\prime}(t)^{3/2}$: $\varphi(t) = f(\xb+t\mathbf{v}),~ t\in\mathbb{R}$\\ \cmidrule{1-3}
$\mathcal{F}^{2,\nu}$ &  Self-concordant barrier &$\mathcal{F}^2$ and  $\sup_{\vb \in\mathbb{R}^n}\set{2\nabla{f}(\xb)^T\vb - \norm{\vb}_{\xb}^2} \leq \nu$ \\ \bottomrule
\end{tabular}
\end{center}
\end{table}

On the basis of these structures, we can design algorithms featuring a full spectrum of (nearly) dimension-independent, global convergence rates for composite convex minimization problems with well-understood analytical complexities \cite{Beck2009,Nesterov2004,Nesterov2007,Nesterov2011c,Tran-Dinh2013a}. Unfortunately, the scalable, penalty-based approaches above invariably feature one or both of the following two drawbacks which blocks their full impact.

\paragraph{Limitation 1 (\textbf{Non-ideal convergence characterizations}):} Ideally, the convergence characterization of an algorithm for solving \eqref{eq:separable_convex} must establish rates  both on absolute value of the  primal objective residual $\abs{f(\xb^k)-f^\star}$ as well as the primal feasibility of its linear constraints $\Vert\Ab\xb^k-\bb\Vert$, simultaneously on its iterates $\xb^k\in\mathcal{X}$.  The constraint feasibility  is critical so that the primal convergence rate has any significance. Rates on weighted primal objective residual and feasibility gap is not necessarily meaningful since \eqref{eq:separable_convex} is a constrained problem and $f(\xb^k)-f^\star$ can easily be negative at all times as compared to the unconstrained setting where we trivially have $f(\xb^k)-f^\star\ge 0$.

Table \ref{tbl: convergence} demonstrates that the convergence results for some existing methods are far from ideal.
Most algorithms have guarantees in the ergodic sense (i.e., on the averaged history of iterates without any weight) \cite{Chambolle2011,He2012a,He2012,Ouyang2014,Shefi2014,Wang2013a} with non-optimal rates, which diminishes the practical performance; they rely on special function properties to improve convergence rates on the function and feasibility \cite{Ouyang2013,Ouyang2014}, which reduces the scope of their applicability; they provide rates on dual functions \cite{Goldstein2012}, or a weighted primal residual and feasibility score \cite{Shefi2014}, which does not necessarily imply convergence on the absolute value of the primal residual or the feasibility; or they obtain convergence rate on the gap function value sequence composed both the primal and dual variables via variational inequality and gap function characterizations \cite{Chambolle2011,He2012a,He2012}, where the rate is scaled by a diameter parameter which is not necessary bounded.\footnote{We refer to the standard ADMM (see, e.g., \cite{Boyd2011}) and not the parallel ADMM variant or multi-block ADMM, which can have convergence guarantees given additional assumptions. }
\begin{table}[ht!]
\newcommand{\cell}[1]{{\!\!\!}#1{\!\!\!}}
\begin{center}
\caption{Illustrative convergence guarantees for solving \eqref{eq:separable_convex} under the proximal tractability assumption. Note that most convergence rate results in the table are in the ergodic or \emph{averaged} sense, where $\widehat{\xb}^k = k^{-1}\sum_{i=1}^k \xb^i$.}\label{tbl: convergence}
\vskip0.25cm

\begin{tabular}{p{3.4cm}|p{3.4cm}|p{5.5cm}|c}\hline\hline
\cell{Method name} & \cell{Assumptions} &  \cell{Convergence }  & \cell{\!\! References\!\!} \\ \hline\hline
\cell{ADMM} & \cell{$\le 2$-decomposable} & \cell{ $\mathcal{O}(1/k)$ on the joint $(\xb^k,\yb^k)$ using a gap function} & \cell{\cite{Chambolle2011,He2012a,He2012}} \\\hline
\cell{Decomposition method} &  \cell{$p$-decomposable}                           & \cell{$f(\widehat{\xb}^k)-f^{\star} + r\Vert\Ab\widehat{\xb}^k-\bb\Vert_2\le \mathcal{O}(1/k)$ ($r > 0$)} & \cell{\cite{Shefi2014}} \\ \hline
\cell{[Fast] ADMM} & \cell{ $\le 2$-decomposable  and $f_1$ or $f_2\in\mathcal{F}_{\mu}$} & \cell{ $\mathcal{[O}(1/k^2)] ~\mathcal{O}(1/k)$ on the dual-objective } & \cell{\cite{Goldstein2012}} \\ \hline
\cell{Bregman ADMM} & \cell{$\le 2$-decomposable}  & \cell{$f(\widehat{\xb}^k)-f^{\star}\le \mathcal{O}(1/k) $ and $\Vert\Ab\widehat{\xb}^k-\bb\Vert_2 \le \mathcal{O}(1/\sqrt{k})$} & \cell{\cite{Wang2013a}} \\\hline
\cell{Fast Linearized ADMM} & \cell{ $\le 2$-decomposable and $f_1$ or $f_2\in\mathcal{F}_{L}$  } &  \cell{$f(\widehat{\xb}^k)-f^{\star}\le \mathcal{O}(1/k)$ and $\Vert\Ab\widehat{\xb}^k-\bb\Vert_2\le \mathcal{O}(1/k)$} & \cell{\cite{Ouyang2014}} \\  \hline
\cell{Primal-Dual Hybrid Gradient (PDHG)} & \cell{Saddle point problem} & \cell{$\mathcal{O}(1/k)$ based on gap function values composed both primal-dual variables} & \cell{\cite{Goldstein2013}} \\ \hline\hline
\cell{[Inexact] augmented Lagrangian method} & \cell{$\le 2$-decomposable} & \cell{$\abs{f(\xb^k)-f^{\star}}\le \mathcal{O}(1/k^2)$ and $\Vert\Ab\xb^k-\bb\Vert_2\le \mathcal{O}(1/k^2)$ (\emph{non-ergodic})}&  \emph{This work}\\\hline
\cell{{Decomposition methods} [Inexact] 1P2D and 2P1D} &  \cell{$p$-decomposable}     & \cell{$\abs{f(\xb^k)-f^{\star}}\le \mathcal{O}(1/k)$ and $\Vert\Ab\xb^k-\bb\Vert_2\le \mathcal{O}(1/k)$ (\emph{non-ergodic})} & \emph{This work} \\ \cmidrule{2-3}
 &  \cell{ $p$-decomposable and $f_i\in\mathcal{F}_{\sigma}$   }  & \cell{$\abs{f(\xb^k)-f^{\star}}\le \mathcal{O}(1/k^2)$,  $\Vert\Ab\xb^k-\bb\Vert_2\le \mathcal{O}(1/k^2)$, and $\Vert \xb^k-\xb^\star \Vert_2\le \mathcal{O}(1/k)$ (\emph{non-ergodic})} &  \\ \hline
\cell{{New ADMM} and its preconditioned variants} &  \cell{$\leq 2$-decomposable}     & \cell{$\abs{f(\xb^k)-f^{\star}}\le \mathcal{O}(1/k)$ and $\Vert\Ab\xb^k-\bb\Vert_2\le \mathcal{O}(1/k)$ (\emph{non-ergodic})} & \emph{This work} \\
\hline\hline
\end{tabular}

\end{center}
\end{table}

\paragraph{Limitation 2 (\textbf{Computational inflexibility}):}  Recent theoretical developments customize algorithms to exploit special function classes for scalability. We have indeed moved away from the black-box model of optimization, which forms the foundation of the interior point method's flexibility, where, for instance, we restrict ourselves to compute solely the values and the (sub)gradients of the objective and the constraints at a point.

Unfortunately, specialized algorithms requires knowledge of function class parameters, do not address the full scope of \eqref{eq:separable_convex} (e.g., with self-concordant functions or fully non-smooth decompositions), and often have complicated algorithmic implementations with backtracking steps, which create computational bottlenecks. Moreover, these issues are further compounded by their penalty parameter selection, such as $\rho$ in \eqref{eq: aug} (cf., \cite{Boyd2011} for an extended discussion), which can significantly decrease numerical efficiency, as well as the inability to handle $p$-decomposability in an optimal fashion, which rules out parallel architectures for their computation.

\subsection{Our contributions}
To this end, we address the following two questions in this paper: ``Is it possible to efficiently solve \eqref{eq:separable_convex} using only the proximal tractability assumption with global convergence guarantees?'' and
``Can we actually characterize the convergence rate of the primal objective residual and primal feasibility gap separately?''
 The answer is indeed positive provided that there exists a solution in a bounded primal feasible set $\Xc$.

 Surprisingly, we can still exploit favorable function classes, such as $\mathcal{F}_L$ and  $\mathcal{F}_\sigma$ when available, optimally exploit $p$-decomposability and its special $2$-decomposable sub-case, and have a penalty parameter-free black-box optimization method.
The second question is also important since in primal-dual framework, trade-off between the primal objective residual and the primal feasibility gap is crucial, which makes algorithm numerically stable, see, e.g., \cite{Goldstein2013} for numerical examples.

To achieve the desiderata, we unify primal-dual methods \cite{Bertsekas1996d,Rockafellar1976a}, smoothing \cite{Nesterov2005c,Rockafellar1976a}, and the excessive gap function technique introduced in \cite{Nesterov2005d} in convex optimization.

\paragraph{\textbf{Primal-dual methods}:}
Primal-dual methods rely on strong duality in convex optimization \cite{Rockafellar1970} and are also related to many other methods for solving  saddle points, monotone inclusions and variational inequalities \cite{Facchinei2003}.
In our approach, we reformulate the optimality condition of \eqref{eq:separable_convex} as a mixed-variational inequality and use the  gap function as our main tool to develop the algorithms.

\paragraph{\textbf{Smoothing}:}
Smoothing techniques are widely used in optimization to replace non-smooth functions with differentiable approximations. In this work, we describe two smoothing strategies for the dual function of  \eqref{eq:separable_convex} in the Lagrange formulation based on Bregman distances and the augmented Lagrangian technique. We show that the augmented Lagrangian smoother preserves convergence properties for the algorithm to solve \eqref{eq:separable_convex} and feature a convergence rate independent of the spectral norm of $\Ab$. In addition, the Bregman smoother allows us to handle $p$-decomposability by only relying on the proximal tractability assumption.

\paragraph{\textbf{Excessive gap function}:}
Excessive gap technique was introduced by Nesterov in \cite{Nesterov2005d} and has been used to develop primal-dual solution methods for solving nonsmooth unconstrained problems.
In this paper, we exploit the same excessive gap idea but in a structured form for a variational inequality characterizing the optimality condition of  \eqref{eq:separable_convex}.
We then combine these three existing techniques in order to develop a unified primal-dual framework for solving \eqref{eq:separable_convex} and analyze the convergence of its algorithmic instances under mild assumptions.

Our specific theoretical and practical contributions are as follows:

$\mathrm{i)}$~We present a unified primal-dual framework for solving constrained convex optimization problems of the form \eqref{eq:separable_convex}.
This framework covers augmented Lagrangian method \cite{Lan2013b,Nedelcu2014}, (preconditioned) ADMM \cite{Chambolle2011}, proximal-based decomposition \cite{Chen1994} and decomposition method \cite{TranDinh2012a} as special cases, which we make explicit in Section \ref{sec: explicit}.

$\mathrm{ii)}$~We prove the convergence and establish rates for three variants (cf., Theorem \ref{th:convergence_A1}) of our algorithmic framework without any need to select a penalty parameter.
An important result is the convergence rate in a non-ergodic sense of both primal objective residual $\abs{f(\bar{\xb}^k) - f^{\star}} \leq \mathcal{O}(1/k^{\alpha})$ and the primal feasibility gap $\Vert\Ab\bar{\xb}^k - \bb\Vert \leq \mathcal{O}(1/k^{\alpha})$, where $\alpha = 1$ or $2$. Our rates are considered optimal given our particular assumptions (cf., Table \ref{tbl: convergence}).

$\mathrm{iii)}$~We consider an inexact variant of our algorithmic framework for the special case of $2$-decomposability, which allows one to solve the subproblems up to given predetermined accuracy so that it still maintains the same worst-case analytical complexity as in the exact case provided that the accuracy of solving the subproblems is controlled appropriately. This variant allows us to handle $2$-decomposability with only proximal tractability assumption.

$\mathrm{iv)}$~We show how special function classes can be exploited and describe their convergence implications.

Our characterization is radically different from existing results such as in \cite{Beck2014,Chambolle2011,Deng2012,He2012a,He2012,Ouyang2014,Shefi2014}.
We clarify the importance of this result in Section \ref{sec:algorithm} as well as Section \ref{sec: explicit} in the context of existing convergence results for ADMM and its variants. For the $p$-decomposability, the variants corresponding to our Bregman smoothing technique can be implemented in a fully parallel and distributed manner, where the feasibility guarantee acts as a consensus rate. In special case, where $p = 2$, we propose a strategy to enhance the practical convergence rate by trading off the objective residual with the feasibility gap.

On the computational front, we test our algorithms on several well-studied numerical problems using both synthetic and real-world data, compare them to other existing state-of-the-art methods, and provide open-source code for each application. We also discuss the update of the smoothness parameters in order to enhance the performance of the algorithms by trading-off between the optimality gap and the feasibility gap. Numerical results show the advantages of our methods on several numerical tests.

\subsection{Related work}
Due to the generality of \eqref{eq:separable_convex}, there has been an explosion of interest in the convex optimization in developing solution algorithms for it. Unfortunately, it is impossible to provide a comprehensive summary of the ever-expanding literature in any reasonable space. Hence, this subsection attempts to relate some important algorithmic frameworks for solving \eqref{eq:separable_convex} to our work with selected, representative citations in each.

\paragraph{\textbf{Methods-of-multipliers/primal-dual methods}:}
One of the oldest primal-dual methods for solving \eqref{eq:separable_convex} is the method-of-multipliers (MoM), which is based on Lagrange dualization \cite{Bertsekas1996d}.
Without further assumptions on $f$ and $\Xc$, the dual step of this method can be viewed as a subgradient iteration, which features a provably slow convergence rate, i.e., $\mathcal{O}(1/\sqrt{k})$, where $k$ is the iteration count. MoM is also known to be  sensitive to the step-size selection rules for damping the search direction.

In order to overcome the difficulty of nonsmoothness in the dual function, several attempts have been made. For instance, we can add either a proximal term or an augmented term to the Lagrange function of \eqref{eq:separable_convex}  to smooth the dual function \cite{Chen1994,Hamdi2005a,Hamdi2005,Necoara2008,Nedelcu2014,Rockafellar1976a}. Intriguingly,
while the specific methods studied in \cite{Chen1994,Hamdi2005a,Hamdi2005,Rockafellar1976a} are quite borad, no global convergence rate has been established so far.

The works in \cite{Necoara2008,Nedelcu2014}  provide convergence rates by applying Nesterov's accelerated scheme to the dual problem of \eqref{eq:separable_convex}. In recent paper \cite{Shefi2014}, the authors shows that the method proposed in \cite{Chen1994} has convergence rate $\mathcal{O}(1/k)$. However, this convergence rate is a joint between the objective residual and the primal feasibility gap, i.e., $f(\xb^k) - f^{\star} + r\Vert\Ab\xb^k - \bb\Vert_2 \leq \mathcal{O}(1/k)$ for $r  > 0$ given. We note that this convergence rate on the weighted measure does not imply the convergence rate of  $\abs{ f(\xb^k) - f^{\star}}$ and  $\Vert\Ab\xb^k - \bb\Vert_2$ separately in  constrained optimization.

In \cite{Esser2010a} the author studies several variants of the primal-dual algorithm and presented several applications in image processing. Convergence analysis of these variants are also presented in \cite{Esser2010a}, however the global convergence rate has not been provided. In \cite{Goldstein2013}, the authors describe a primal-dual hybrid gradient (PDHG) algorithm, which can be considered as a variant of the same primal-dual algorithm.

In \cite{Goldstein2013}, the authors also studied several heuristic strategies to update the parameters, and show that the convergence rate of this algorithm is $\mathcal{O}(1/k)$ in an ergodic sense with respect to a VIP gap function values.

\paragraph{\textbf{Methods from monotone inclusions and variational inequalities}:}
The optimality condition of \eqref{eq:separable_convex} can be viewed as a monotone inclusion or a mixed variational inequality (VIP) corresponding to both the primal and dual variables $[\xb, \yb] \in \Xc\times\R^m$. As a result, we can leverage algorithms from these two respective fields to solve \eqref{eq:separable_convex} \cite{Chambolle2011,Facchinei2003,He2012a,He2012}.
For instance, the work in \cite{Chambolle2011} exploit the idea from variational inequality proposed in \cite{Nemirovskii2004,Nesterov2007a}.
Splitting methods including Douglas-Rachford and predictor-corrector methods considered \cite{Combettes2005,Condat2012,Eckstein1992,He2012b,Odonoghue2012a} also belong to this direction.
However, since monotone inclusions or variational inequalities are much more general than \eqref{eq:separable_convex}, using methods tailored for optimization purposes may be more efficient in practice for solving the specific optimization problem \eqref{eq:separable_convex}.

\paragraph{\textbf{Augmented Lagrangian and alternating direction methods}:}
Augmented Lagrangian (AL) methods have come to offer an important computational perspective on a broad class of constrained convex problems of the form \eqref{eq:separable_convex}. In this setting, we first define the Lagrangian function associated with the linear constraint $\Ab\xb = \bb$ of \eqref{eq:separable_convex}  as $\mathcal{L}(\xb, \yb) := f(\xb) + \yb^T(\Ab\xb-\bb)$.
Then, we introduce the augmented Lagrangian function:  $\mathcal{L}_{\gamma}(\xb, \yb) := \mathcal{L}(\xb, \yb) + (\gamma/2)\norm{\Ab\xb - \bb}^2_2$ for a given penalty parameter $\gamma > 0$.
Classical augmented Lagrangian method \cite{Bertsekas1989b} solving \eqref{eq:separable_convex} produces a sequence $\set{(\xb^k, \yb^k)}_{k\geq 0}$ starting from $(\xb^0, \yb^0)\in\Xc\times\R^m$ as
\begin{equation}\label{eq:aug_Lag_alg}
\left\{\begin{array}{ll}
\xb^{k+1} &:= \mathrm{arg}\min_{\xb\in\Xc}\mathcal{L}_{\gamma}(\xb, \yb^k),\\
\yb^{k+1} &:= \yb^k + \gamma (\Ab\xb^{k+1} - \bb),
\end{array}\right.
\end{equation}
Under a suitable choice of $\gamma$, it is well-known that method \eqref{eq:aug_Lag_alg} converges to a global optimal $(\xb^{\star}, \yb^{\star})$ of \eqref{eq:separable_convex} at  $\mathcal{O}(1/k)$ rate under mild assumptions, i.e., $\mathcal{L}(\xb^k, \yb^k) - \mathcal{L}(\xb^{\star}, \yb^{\star}) \leq \mathcal{O}(1/k)$.
In fact, this method can be accelerated by applying Nesterov's accelerating scheme \cite{Nesterov2004} to obtain $\mathcal{O}(1/k^2)$ convergence rate.

Within the class of augmented Lagrangian methods, perhaps the most famous variant is the alternating direction method of multipliers (ADMM), which appears in many guises in the literature.
This method has been recognized as a special case of Douglas-Rachford splitting algorithm applying to its optimality condition \cite{Boyd2011,Eckstein1992,Goldstein2012}.
In ADMM, given that $f$ and $\Xc$ are separable with $p = 2$. This case also covers the composite minimization problem of the form $\min_{\xb_1 \in\R^{n_1}}f_1(\xb_1) + f_2(\Ab\xb_1)$, where both $f_1$ and $f_2$ are convex. By using a slack variable, we can reformulate the composite problem into  \eqref{eq:separable_convex} as $\min_{\xb \in\R^n}f_1(\xb_1) + h(\xb_2)$ subject to $\Ab\xb_1 = \xb_2$.
In the ADMM context,  the first problem in \eqref{eq:aug_Lag_alg} can be solved iteratively as
\begin{equation}\label{eq:alternate_step}
\left\{\begin{array}{ll}
\xb^{k+1}_1 &\!\!\!:= \displaystyle\mathrm{arg}\!\!\!\min_{\xb_1\in\Xc_1}\Big\{f_1(\xb_1) + (\yb^k)^T\Ab_1\xb_1 + (\gamma/2)\norm{\Ab_1\xb_1 - \xb_2^k  }_2^2\Big\},\\
\xb^{k+1}_2 &\!\!\!:= \displaystyle\mathrm{arg}\!\!\!\min_{\xb_2\in\Xc_2}\Big\{f_2(\xb_2) + (\yb^k)^T\Ab_2\xb_2 + (\gamma/2)\norm{\Ab_1\xb_1^{k+1} -\xb_2  }_2^2\Big\}.
\end{array}\right.
\end{equation}
The main computational difficulty of ADMM is the $\xb_1$-update problem (i.e., the first subproblem) in \eqref{eq:alternate_step}. Indeed, we have to numerically solve this step in general except when $\Ab^T\Ab$  is efficiently diagonalizable. Interestingly, the diagonalization step in many cases can be done via Fourier Transform. Many notable applications support this feature, such as matrix completion where $\Ab$ models sub-sampled matrix entries, image deblurring where $\Ab$ is a convolution operator, and total variation regularization where $\Ab$ is a differential operator with periodic boundary conditions. We can also circumvent this computational  difficulty by using a preconditioned ADMM variant \cite{Chambolle2011}.

ADMM is one of the most popular method in practice. However, its efficiency depends significantly on the choice of the penalty parameter $\gamma$. Unfortunately, theoretical guarantee for choosing this parameter is still an open problem and is not yet well-understood.
When $f_1$ is strongly convex, we can drop the quadratic term in the first line of \eqref{eq:alternate_step} in order to obtain an alternating minimization algorithm (AMA) \cite{Tseng1991a}. This method turns out to be a forward-backward splitting algorithm for its optimality inclusion \cite{Goldstein2012}.

\paragraph{\textbf{A note on \cite{Nesterov2005c}}:}
We note that the approach presented in this paper builds upon the excessive gap idea in \cite{Nesterov2005c}. Technically, we use the same idea but in a much structured fashion, whereby we enforce a particular linear form in preserving the excessive gap as shown in Definition 3.2. This particular structure is key in obtaining our convergence rates.

Moreover, since our problem setting \eqref{eq:separable_convex} is different from the general minmax formulation considered in \cite{Nesterov2005d}, there are still several differences between our algorithmic framework and the methods studied in \cite{Nesterov2005d} as a result of the excessive gap technique.
First, we use augmented Lagrangian functions and Bregman distances for smoothing the dual problem of \eqref{eq:separable_convex}.
Second, we consider the Lagrangian primal-dual formulation for \eqref{eq:separable_convex} where we do not have the boundedness of the feasible set of the dual variable. In this case the key estimate \cite[estimate (3.3)]{Nesterov2005c} does not apply to our setting.
Third, we update all algorithmic parameters simultaneously and do not need an odd-even switching strategy \cite[Method 1: b) and c)]{Nesterov2005d}.
Four, we do not assume that the objective function $f$ of \eqref{eq:separable_convex} has Lipschitz gradient which is required in \cite{Nesterov2005d}.
Note that there are several important applications, where this assumption simply does not hold \cite{McCoy2014}.
Fifth, our method is applied to the constrained problem \eqref{eq:separable_convex}, which requires the feasibility gap characterization as opposed to unconstrained problems where we only need to worry about   the primal-dual optimality.

\subsection{Paper organization}
The rest of this paper is organized as follows. In the next section, we recall basic concepts, and introduce a mixed-variational inequality formulation of \eqref{eq:separable_convex}.
In Section \ref{sec:smoothing}, we propose two key smoothing techniques for \eqref{eq:separable_convex}, called the Bregman  and augmented Lagrangian smoothing techniques.
We also provide a formal definition for  the excessive gap function from \cite{Nesterov2005c} and further investigate its properties.
Section \ref{sec:algorithm} presents the main primal-dual algorithmic framework for solving \eqref{eq:separable_convex} and its convergence theory.
Section \ref{sec:variants} specifies different instances of our algorithmic framework for \eqref{eq:separable_convex} under given assumptions.
Section \ref{sec:existing_methods} makes further connections to existing methods in the literature.
Section \ref{sec:impl_issues} is devoted to implementation issues and Section \ref{sec:num_results} presents numerical simulations.
The appendix provides detail proofs of the theoretical results in the main text.


TITLE: Show that this Dirichlet problem can only have a maximum of one solution
QUESTION [2 upvotes]: Let $f: \mathbb{R} \times \overline{U}$ be a function such that
$f\mid_\mathbb{R}$ is continuously differentiable and
$f\mid_\overline{U}$ is continuous.
Further let $\frac{\partial }{\partial u} f(u,y) \geq0$ for every $(u,y) \in \mathbb{R} \times U$
Show that the problem
$\Delta u=f(u,y)$ in $U$,
and $u=u_D$ on the boundary of $U$
has at most one Solution.
I am stuck on this problem for a few days now, and can't figure out how to solve it.
In most of my attempts I tried to use the maximum principle.

REPLY [1 votes]: Suppose that $u,v \in C^2(U) \cap C^0(\overline U)$ solve $$\Delta u=f(u,x), \text{ in } U \qquad u=g \text{ on } \partial U .$$ Let $w:=u-v$. If $w\not\equiv 0$ then there exists some point $x\in U$ such that $w(x)\neq 0$. Without loss of generality, we may assume there exists $x \in U$ such that $w(x)>0$. Let $V:= \{x \in U \text{ s.t. } w(x)>0\}$ which is non-empty and open since $u$ and $v$ are continuous. Then for each $x\in V$, \begin{align*}
\Delta w &= f(u,x)-f(v,x) \\
&= \int_{v(x)}^{u(x)} \frac{\partial f}{\partial z}(z,x) \, dz \\
&\geqslant 0.
\end{align*} Hence, $w$ is subharmonic in $V$. Since $u$ and $v$ agree on $\partial U$, we have that $w=0$ on $\partial V$. By the maximum principle, $$\max_{\overline V} w = \max_{\partial V} w =0. $$ This is a contradiction with the definition of $V$.


TITLE: How do I prove this statement about winding numbers and continuous maps?
QUESTION [0 upvotes]: I have the following problem:

Let $D$ be a disk with boundary circle $C$ and let $f:D\rightarrow \mathbb{R}^2$ be a continuous map. Suppose $P\in \mathbb{R}^2\setminus f(C)$ and the winding number of the restriction $f|_C$ of $f$ to $C$ around $P$ ia not zero. Show that there is a point $Q\in D$ such that $f(Q)=P$

I wanted to prove this by contradiction, i.e. let us assume that $f:D\rightarrow \mathbb{R}^2$ is a continuous map and $C\subset D$ be the boundary circle. Then we can restrict f to $$f|_C:C\rightarrow \mathbb{R}^2$$ which is also continous. Let $P$ be as above s.t. the winding number of $f|_C$ is non zero, i.e. $W(f|_C,P)=W(\gamma,P)\neq 0$ where $$\gamma:[a,b]\rightarrow \mathbb{R}^2$$ is a conitnuous loop and $$\gamma=\phi\circ f|_C$$ with $\phi:[a,b]\rightarrow C$. Now I assume also that forall $Q\in D, f(Q)\neq P$. Since $C\subset D$ we have that also for all $Q\in C, f|_C(Q)\neq P$. Since $\gamma$ is continuous and $[a,b]$ is compact also $\gamma([a,b])$ is compact, but this means that also $f|_C(C)$ is compact.
Now I want to lead this to a contradiction, but I somehow don't see how to procede, could someone help me and show me how I can go further?
Thanks a lot

REPLY [2 votes]: The disk $D$ is contractible: fix a point $c \in C \subset D$ and let $F_t(x) : [0, 1] \times D \to D$ be a deformation retraction of $D$ onto $c$ which fixes $c$ at all times $t$. Then the restriction $F_t \rvert_{C}$ of $F_t$ to the boundary circle $C$ is a deformation retraction of $C$ in $D$ onto $c$. That is the same thing as a based homotopy of the loop $F_0 \rvert_{C}$ which ends at the constant loop at $c$.
This means that the composite $f \circ F_0 \rvert_C$ is a based homotopy of $f(C)$ which contracts $f(C)$ to the single point $f(c)$. Finally, we know that the winding number of a loop about a point $P$ is a homotopy invariant of the loop provided that the homotopy does not pass through $P$ (see e.g. here).
So, in the situation of your problem assume that $P \not \in f(D)$. Then the winding numbers $W(f\rvert_C, P)$ and $W([c], P)$ are equal by the explicit homotopy $f \circ F_f \rvert_C$ which we have just constructed (where $[c]$ is the constant loop which stays at $c$). But of course $W([c], P) = 0$, so we conclude that $W(f\rvert_C, P) = 0$ as well. This proves the contrapositive of your claim. (We don't need contradiction here.)

If you're finding the explicit homotopy $F_t$ hard to visualize, by convexity of the disk $D$ we can just spaghetti shlooop up the disk to the point $C$ by (here we think of $D$ as the unit disk in $\mathbb{R}^2$ with $x, c \in \mathbb{R}^2$ vectors of norm $\leq 1$)
$$
F_t(x) := (1 - t) x + t c.
$$


TITLE: Roots of polynomial outside a vertical strip of $\mathbb C$
QUESTION [2 upvotes]: Let $P(z)$ be an arbitrary polynomial with real coefficients. I'd like to guarantee that all roots of $P$ have real parts outside the interval $(0, 1)$. Is there some simple condition on P that will ensure that?
Let me illustrate further. If $P$ were known to only have real roots, a simple condition would (almost tautologically) be “P does not change sign on $(0, 1)$”. For the general case that $P$ has complex roots, is there some condition that will guarantee that no root $z_i$ satisfies $0 < \mathrm{Re}\, z_i < 1$?
Note that I'm looking for a sufficient condition. That is, I don't need to characterize the class of all polynomials that fulfill the stated condition; a “reasonably” large subclass of that class may be enough for me.

REPLY [3 votes]: This is a nontrivial task, and the best approach may depend on how the polynomial is specified (i.e., what kind of structure it has). In principle, the Routh–Hurwitz theorem can answer the question, as it gives the number of roots in the positive half plane $\{z:\operatorname{Re}z>0\}$. Your problem amounts to determining whether this number is the same for $P$ and for $P(z+1)$.
The related Routh–Hurwitz stability criterion is easier to check in practice, and provides a sufficient condition: if the criterion holds, there are no roots with positive real part, and in particular with real part between $0$ and $1$.
Finally, since Alex S mentioned Rouché's theorem, I'll point to the post How many roots of a polynomial have positive real part? for an example of its usage in this context.


TITLE: Order topology on $\mathbb{N}$ is discret topology?
QUESTION [2 upvotes]: Let $\mathbb{N}=\{0,1,2,\dotso\}$ and $(\mathbb{N},<)$ with the usual ordering $<$. Let $\tau_<$ be the order topology with regards to $<$. Then $\tau_<$ is the discrete topology (topology of all subsets) on $\mathbb{N}$.

I am asked to proof this, but I doubt that this is correct...
A base of the order topology is given by: $\mathcal{O}=\{(u,v)|u,v\in X, u<v\}\cup\{(-\infty, u), (u,\infty)|u\in X\}\cup\{X\}$
That means for $V\in\tau_<$ there is for every $v\in V$ a $U\in\mathcal{O}$ such that $v\in U\subseteq V$.
We want to show, that $\tau_<=\tau_{disc}$, so every subset of $\mathbb{N}$ is open.
Clearly it sufficies to show, that $\{n\}$ is open for every $n\in\mathbb{N}$.
For $n\neq 0$ this is obviously true, since $\{n\}=(n-1,n+1)$.
But I do not see, why $\{0\}$ should be an open set, with regards to $\tau_<$.
The only elements of $\mathcal{O}$ which contain $0$ are the sets $(-\infty, n)$ with $n>0$.
But with these we do not get equality.
So there is no chance to get $\{0\}=\bigcup \mathcal{U}$ where $\mathcal{U}\subset\mathcal{O}$. So $\{0\}$ should not be open. In fact no subset of $\mathbb{N}$ which has $0$ as an element should be open. So $\tau_<\neq\tau_{disc}$
Or am I missing something?
Thanks in advance.

REPLY [4 votes]: I think the confusion comes from the notation of your open rays as $(n,\infty)$ and $(-\infty,n)$. I personally find the following notation less confusing:
Define ${x\!\!\uparrow}=\{y\in X\mid y>x\}$ and ${x\!\!\downarrow}=\{y\in X\mid y<x\}$, then the set $\mathcal B=\{{x\!\!\uparrow}\mid x\in X\}\cup\{{x\!\!\downarrow}\mid x\in X\}$ forms a subbase for the order topology. You could get an open interval $(a,b)$ by taking the intersection of ${a\!\!\uparrow}\cap {b\!\!\downarrow}$.
Now for $X=\mathbb N$ it should become clear that $\{0\}={1\!\!\downarrow}$.


TITLE: In Heisenberg's group, why if $e^{tX}$ is upper triangular, then $X$ is strictly upper triangular?
QUESTION [6 upvotes]: To find the Lie algebra of the Heisenberg group $H$, which we know to consist of upper triangular matrices, we see that exponentials of all strictly upper triangular matrices are in $H$. I do not get the following could you explain?
"On the other hand if $X$ is any matrix such that $e^{tX}$ is upper triangular, then all the entries of $X=\frac{d}{dt}|_{t=0}e^{tX}$ which are on or below diagonal must be zero so that $X$ is upper triangular"
Thus the Lie algebra of the Heisenberg group is the space of all $3\times 3$ real
matrices which are strictly upper triangular.

REPLY [12 votes]: Suppose you know that $e^{tX}$ is in the Heisenberg group for all $t$. Then this means that
$$e^{tX} = \left(\begin{array}{ccc} 1 & a(t) & b(t) \\ 0 & 1 & c(t) \\ 0 & 0 & 1 \end{array}\right)$$
where $a(t),b(t),c(t)$ are smooth functions. Now if you take the derivative of $e^{tX}$ at $t = 0$, you are taking the derivative of the individual components of the matrix on the right. This means that
$$\frac{d}{dt}e^{tX}\bigg|_{t = 0}  = X =\left(\begin{array}{ccc} \frac{d}{dt}1 & a'(0) & b'(0) \\ 0 & \frac{d}{dt}1 & c'(0) \\ 0 & 0 & \frac{d}{dt}1 \end{array}\right) = \left(\begin{array}{ccc} 0 & a'(0) & b'(0) \\ 0 & 0 & c'(0) \\ 0 & 0 & 0\end{array}\right).$$
$a'(0), b'(0)$ and $c'(0)$ are just real numbers and the calculation above shows that $X$ is strictly upper triangular.


text:
\begin{document}

\begin{abstract}
Let $\F$ be an arbitrary field. We consider a  commutative, non-associative, $4$-dimensional algebra $\M$ of the rock, the paper and the scissors with unit  over $\F$ and we prove that the image over $\M$ of every non-associative multilinear polynomial over $\F$ is a vector space. The same question we consider for two subalgebras: an algebra of the rock, the paper and the scissors without unit, and an algebra of trace zero elements with zero scalar part. Moreover in this paper we consider the questions of possible evaluations of homogeneous polynomials on these algebras.
\end{abstract}

\maketitle
\begin{flushright}
Dedicated to the 80-th anniversary of A.V. Mikhalev
\end{flushright}

\section{Introduction}
The study of images of polynomials evaluated on algebras is one of the most important branches of  modern algebra.
Similar questions for word maps in groups were considered in \cite{Bre,GKP}. Waring type problems for groups were investigated by Shalev \cite{Sha1,Sha2,Sha3}. Similar questions for matrix rings were investigated by Bre\v{s}ar (\cite{Bre}). A good survey describing these and other references can be found in \cite{BMRY}.

One of the central conjectures regarding possible evaluations of multilinear polynomials on matrix algebras was attributed to Kaplansky and formulated by L'vov in \cite{Dn}:
\begin{conj}[L'vov-Kaplansky] \label{kapl}Let $p$ be a non-commutative multilinear polynomial. Then the
set of values of $p$ on the matrix algebra $M_n(K)$ over an infinite field $K$ is a vector
space.
\end{conj}

It is well-known (\cite{BMR1,BMR2,BMR3,BMR4,M1,M2,BMRY}) that this conjecture can be reformulated as follows:
\begin{conj} If $p$ is a multilinear polynomial evaluated on the matrix ring
$M_n (K)$, then $\Image p$ is either $\{0\}, K, \ssl_n (K),$ or $M_n (K).$ Here $K$ indicates the set
of scalar matrices and $\ssl_n (K)$ is the set of  matrices with trace equal to zero.
\end{conj}

When $n=2$, for the case of $K$ being quadratically closed it was proved in \cite{BMR1}, and in \cite{M1} it was proved for the case of $K=\R$, and an interesting result was obtained for arbitrary fields.

For $n>2$ this question was considered in \cite{BMR2,BMR3,BMRY} and partial results were obtained.
In \cite{M2} the same question was considered for the algebra of quaternions with the Hamilton multiplication and it was shown that any evaluation of a multilinear polynomial  is a vector space. In the same paper it was said that this question is interesting only for simple algebras, since for non-simple algebras it may be answered negatively. Indeed, this conjecture fails for the Grassmann algebra.

Nevertheless, there is an interest in the investigation of this question for non-simple algebras: for some of them the Kaplansky question can be answered positively. For example, if we consider the $8$-dimensional algebra $M_2(K) \oplus M_2(K)$ (which is not simple) then it is easy to see that the evaluation of any multilinear polynomial is a pair of its evaluations on $M_2(K)$ and thus, the only possible multilinear evaluations are vector spaces:
$$ \{0\}, K\oplus K, \ssl_2 (K)\oplus\ssl_2(K), \ \text{or}\  M_2 (K)\oplus M_2(K).$$

In this paper we consider a non-simple algebra, defined in Section \ref{prel}. Unlike the previous results regarding this area, this algebra is non-associative and commutative and, although  we consider non-associative commutative evaluations, the answer to the L'vov-Kaplansky conjecture for this algebra is positive.

Previously, non-associative algebras (in particular the algebra of Cayley numbers) were considered in \cite{ZSSS}. The question of possible
multilinear non-associative evaluations was considered in \cite{BMR4} where the Kaplansky conjecture was considered for Lie polynomials.

In \cite{BMR1,BMR2,BMR3,BMR4,M1,M2,BMRY} the question of possible semi-homogeneous evaluations was investigated, and here we consider such a question as well. Unfortunately, we have not succeeded to answer it. However, in Section \ref{homogen} we formulate interesting conjectures and discuss them.

\section{Preliminaries}\label{prel}

Let $(X,\cdot)$ be a finite monad i.e $X$ is a finite set together with a binary operation $\cdot$ for which there is a unit element with respect to~$\cdot$.
Let $\F$ be an arbitrary field and denote by $M_{ \F}(X)$ the free vector space over  $\F$ with basis set $X$. By extending multiplication from  $X$ to $M_{ \F}(X)$ bilinearly, we obtain a non-associative algebra with unit. We call $M_{ \F}(X)$ the monad algebra of $X$ over $\F$.\newline

We now consider the monad $X=\{1,R,P,S\}$ with multiplication defined as follows: multiplication is commutative, $1$ serves as the unit element, all elements of $X$ are idempotent and  $R\cdot P =P$, $P\cdot S =S$ and $S\cdot R =R$. This monad is the well known rock- paper- scissors magma, where each element is idempotent and the product is the winner in one of the most well-known games.\newline
In what follows, we shall write $\M:=M_{\F}(X)$. It follows that $\M$ is a commutative, non-associative, $4$-dimensional algebra with unit over $\F$.\newline
When evaluating polynomials on non-associative algebras, we must consider non-associative polynomials. A non-associative polynomial over a field $\F$ is, intuitively, a polynomial over $\F$ in which the placing of brackets in each monomial matters.
For instance, the polynomials:
$$
p_1(x_1,x_2,x_3,x_4)=x_1(x_2(x_3x_4)),\
p_2(x_1,x_2,x_3,x_4)=(x_1x_2)(x_3x_4)
$$
are considered to be  different non-associative polynomials.\newline

Let $\A$ be a non-associative algebra over a field $\F$ and let $p(x_1,x_2,\dots,x_m)$ be a non-associative polynomial over $\F$.\newline
The associated polynomial function is denoted by $\Tilde{p}$. \newline
The image of $p$ over $\A$, $\Image _{\A}(p)$, is the evaluation of the associated polynomial function $\Tilde{p}$ on the  algebra $\A$. Usually the choice of the algebra is evident, and we write simply $\Image p$.

A non-associative polynomial over a field $\mathbb{F}$ is called  multilinear

if it is linear with respect to each of the variables. This means in  particular, that each variable appears exactly once in each monomial.

For $x=x_01+aP+bR+cS \in\M$, we define
the scalar part of $x$ to be $\Sc(x):=x_0$ and
the trace of $x$ to be $\trace(x):=x_0+a+b+c$.\newline
It is obvious that $ \Sc\colon {\M}\rightarrow \F$ and $ \trace \colon {\M}\rightarrow \F$ are linear functions on the vector space ${\M}$.
Moreover, they also respect multiplication on ${\M}$ i.e for $x,y \in {\M}$:
\begin{equation*}
 \Sc(x \cdot y)=\Sc(x)\Sc(y)
 \end{equation*}
\begin{equation*}
\trace(x \cdot y)=\trace(x)\trace(y)
 \end{equation*}
Therefore, both functions $\Sc(*)$ and $\trace(*)$ are homomorphisms from $\M$ to $\F$.

We denote by $\M_{0}$ the set of elements of $\M$ with zero trace and zero scalar part.\newline
It follows that $\M_{0}$ is a two dimensional subspace of $\M$, and moreover, it is an ideal and a subalgebra of $\M$.

\section{Main Theorem}
\begin{theorem}\label{main}
Let $\F$ be an arbitrary field. If $p(x_1,x_2,\dots,x_m)$ is a  multilinear commutative non-associative  polynomial with coefficients in $\F$, then the evaluation of $p$ over $\M$ is either:
\begin{enumerate}
\item $\{0\}$;
\item $\left<P+R\omega+S\omega^2\right>$;
\item $\left<P+R\omega^2+S\omega\right>$;
\item ${\M}_{0}$;
\item $\M$.
\end{enumerate}
\end{theorem}
By $\omega$ we denote $1$ if $\Char\F=3$, and a primitive cube root of $1$ otherwise (if such an element exists in $\F$). If such element $\omega$ does not exist in $\F$, options (2) and (3) are impossible. As well-known, this element ($\omega$) satisfies $\omega^2+\omega+1=0$. In particular, such an element exists in $\CC$, although it does not exist in  $\R$.
We will use the following basic fact from linear algebra:
\begin{lemma}[\cite{M1}, Lemma~3]\label{2 dim lemma}
Let $L$  be a vector space over a field $\F$ and suppose that  $f\colon L\times \cdots \times L\rightarrow L$  is a multilnear map. Assume that  $\Image(f)$ contains two  vectors which are not proportional. Then $\Image(f)$ contains a two dimensional subspace. In particular, if $\Image(f)$  is contained in a  two dimensional subspace $M$, then $\Image(f)=M$.
\end{lemma}
\begin{rem}\label{lowdim}
As a consequence, one can immediately conclude from Lemma \ref{2 dim lemma}, that the image set of any multilinear map (in particular of a multilinear polynomial) is either a vector space or at least a $3$-dimensional set. By the dimension of an image set, we  mean the dimension of its Zariski closure. Note that a polynomial image is not necessarily Zariski closed.
\end{rem}
Let us first prove the following Lemma:
\begin{lemma}\label{lemma-vec}
Let $\F$ be an arbitrary field. If $p(x_1,x_2,\dots,x_m)$ is a  multilinear commutative non-associative  polynomial with coefficients in $\F$, then the evaluation of $p$ over $\M$ is either:
\begin{enumerate}
\item $\{0\}$;
\item some one-dimensional vector space;
\item ${\M}_{0}$;
\item $\M$.
\end{enumerate}
\end{lemma}

\begin{proof}
Since  $p(x_1,\dots,x_m)$ is multilinear, it is a linear combination of monomials such that, in each monomial, every variable $x_i$ appears exactly once.
Let the coefficients of the monomials of $p$ be  $c_1,\dots,c_d$. Suppose that $c:=\sum\limits_{i=1}^{d}c_i\neq 0$. let $a\in \M$. Then $a=\Tilde{p}(c^{-1}\cdot a,1,\dots,1)$ and thus $\Image(p)=\M$.\newline
Thus, suppose that $c=0$. If $a\in \Image(p)$, then there exist elements  $a_1,\dots,a_m \in \M$ such that $a=\Tilde{p}(a_1,\dots,a_m)$. Since $\F$ is commutative and associative with respect to multiplication  and $ \trace$ and $\Sc$ are linear and respect multiplication, it follows that \begin{equation*}
  \trace(a)=\trace(a_1)\cdots \trace(a_m) \cdot \sum_{i=1}^{d}c_i=0
\end{equation*}
and similarly $\Sc(a)=0$.
Hence, $\Image(p)$ is contained in $\M_{0}$. Note that $\dim\ \M_0=2$. Thus, according to Remark \ref{lowdim}, $\Image p$ is a vector space: either $2$-dimensional (and thus coincides with $\M_{0}$), or of dimension $1$ or $0$. In the last case $p$ is a PI.
\end{proof}

We now give the proof of Theorem \ref{main}:
\begin{proof}
In view of Lemma \ref{lemma-vec}, we have to classify $1$-dimensional images. Consider the linear map $\varphi:\M\rightarrow\M$ defined as follows:
$$1\mapsto 1,\ P\mapsto R, R\mapsto S, S\mapsto P.$$
It is not difficult to see that this map respects multiplication and thus is an automorphism of $\M$.
Therefore, if $p(x_1,\dots,x_m)$ is a multilinear polynomial evaluated on $\M$, then for any values of $x_i$ we have  $$\varphi(p(x_1,\dots,x_m))=
p(\varphi(x_1),\dots,\varphi(x_m)).$$
Hence, if $\Image p$ is a $1$-dimensional vector space spanned by an element $x=aP+bR+cS\in\M_0$, $\varphi(x)$ should be proportional to $x$ i.e it should span the vector space. Note that $\varphi(aP+bR+cS)=cP+aR+bS$. Thus, $\frac{c}{a}=\frac{a}{b}=\frac{b}{c}$ and it is not difficult to see that this ratio can be only a cube root of $1$. If $\Char\F=3$, the only element in $\F$ satisfying this property is $1$ and thus, $\Image p=\left<P+R+S\right>$. If $\Char\F\neq 3$ and $\omega\in\F$, there are three elements satisfying this property: $1,\omega$ and $\omega^2$. However, the option $a=b=c$ is impossible since $\trace(P+R+S)=3$ and this is not an element of $\M_0$.
\end{proof}
\section{Examples}

The most important thing to understand is whether or not polynomials with such images exist. Of course, it is very simple to construct an example of a polynomial whose image set is $\M$: one can take $p(x)=x$, or any other multilinear polynomial with nonzero sum of coefficients.

It is not difficult to see that the set $\M_0$ can also be achieved, for instance, as the image of the polynomial $g(x,y,z)=(xy)z-(xz)y.$ Indeed, its image contains the element
$g(P,R,S)=(PR)S-P(RS)=PS-PR=S-P$ and thus, by Theorem \ref{main}, $\Image g=\M_0$.
Unfortunately, we have not succeeded in constructing examples of multilinear polynomials with $1$-dimensional images. However, most likely they exist. Polynomial identities exist as well. Indeed, the computation shows that the polynomial $f(x,y,z,t)=(xy)(zt)-(xz)(yt)$ evaluated on $\M_0$ is a PI (in Lemma~\ref{pi0}, we prove this for the case $\Char\F\neq 3$. However, this is true for arbitrary fields and can be easily checked by basis element evaluations. For example, one can take  the elements $P-R$ and $R-S$ as a basis for $\M_0$ and check all $16$ evaluations). We can take four polynomials with image sets $\M_0$ and put them instead of $x,y,z$ and $t$ inside $f$:
$x=g(x_1,x_2,x_3),\ y=g(y_1,y_2,y_3),\ z=g(z_1,z_2,z_3)$ and $t=g(t_1,t_2,t_3)$. As a result, we obtain a multilinear polynomial in $12$ variables which is a commutative non-associative polynomial identity of the algebra $\M$. Of course, $12$ is not the minimal possible degree for polynomial identities of $\M$.

\section{PI algebras}
Moreover, any finite dimensional commutative non-associative/non-commutative associative/non-commutative non-associative algebra is a PI algebra with nontrivial multilinear PI (i.e. PI of the same type as a type of an algebra).
Indeed, let us compute the number of possible multilinear monomials of degree $m$: the number of associative non-commutative monomials is $m!$, the number of non-associative non-commutative monomials is $m!\cdot C_{m-1},$ where $C_{m-1}=\frac{1}{m} \binom{2m-2}{m-1}$ is a Catalan number.
In our case, we are interested in multilinear non-associative commutative monomials. Each monomial has exactly $m-1$ multiplications and for each of them we can change places of the multipliers. Thus, there are exactly $2^{m-1}$ different non-commutative non-associative monomials, corresponding to each commutative non-associative monomial, and therefore, the number of commutative non-associative monomials is  $m!\cdot C_{m-1}\cdot 2^{1-m}.$
If our algebra is finite dimensional, let $d$ be its dimension, $A=\left<E_1,\dots, E_d\right>$. In this case, a nonzero multilinear polynomial $p(x_1,\dots,x_m)$ is a PI if and only if its evaluations on all sets of basis elements $E_i$ is zero. We have exactly $d^m$ such evaluations, each of them has $d$ coordinates, and therefore, we have a system of $d^{m+1}$ linear equations, where the unknowns are the coefficients of $p$. The number of unknowns is the number of possible monomials. Hence, the existence of a PI follows from existence of a number $m$, such that the number of monomials  is larger than $d^{m+1}$. Remember, that for each $m$, these numbers (depending on the type of algebra) are $m!,\ m!\cdot C_{m-1}$, and $m!\cdot C_{m-1}2^{m-1}.$ For large $m$, these numbers exceed $d^{m+1}$ and thus, such  an $m$ exists.

\section{Subalgebras, good basis, automorphisms and polynomial identities}
Let us consider the algebra $\M_0$ separately. Unlike $\M$,  this is a simple algebra, i.e it does not contain any non-trivial ideals. In this section we assume that $\Char\F\neq 3$ and $\omega\in \F$. The second condition can be achieved if instead of the field $\F$, we consider either its algebraic closure or its extension $\F[\omega]$.
In this case, $\M_0$ has the following basis (called "the good basis"):
$$U=\frac{1+2\omega}{3}\left(P+R\omega+S\omega^2\right),$$
$$V=\frac{1+2\omega^2}{3}\left(P+R\omega^2+S\omega \right).$$
Note that the condition $\Char\F\neq 3$ is important:  if $\Char\F=3$ these elements $U$ and $V$ are not well defined.
A simple computation shows that $$U^2=V,\ V^2=U, \ \text{and}\ UV(=VU)=0.$$
The automorphism $\varphi$ of order $3$ defined in the proof of Theorem \ref{main}, induces an automorphism of $\M_0$:
$\varphi(U)=\omega^2 U,\ \varphi(V)=\omega V.$
\begin{rem}
There is another important automorphism $\psi$ of $\M_0$: $U\mapsto V,\ V\mapsto U$. This automorphism cannot be extended to $\M$. Nevertheless, if $\F=K[\omega]$ for some subfield $K$ which does not contain $\omega$, this automorphism can be extended from $\M_0(K)$ to $\M(\F)$ considered as an algebra over $K$: $U\mapsto V,\ V\mapsto U, \omega\mapsto\omega^2,\omega^2\mapsto\omega.$ The second two evaluations define the conjugation automorphism of $\F$ preserving $K$. In the usual basis $\{1,P,R,S\}$ of $\M$ it leaves basic elements and conjugates field coefficients only. The order of $\psi$ is $2$.

Note that not every field $\F$ containing $\omega$ can be presented as $K[\omega]$. For instance, the field $\F_7$ has an element $\omega=2\in\F_7$ but does not have any subfields at all.

\end{rem}

Now we are ready to prove a lemma about polynomial identities of $\M_0$:
\begin{lemma}\label{pi0}
The polynomial $f(x,y,z,t)=(xy)(zt)-(xz)(yt)$ is a PI of $\M_0$.
\end{lemma}
\begin{proof}
Consider the evaluations of $f(x,y,z,t)$ on the basis elements $U$ and $V$: for such evaluations, a product of two different elements equals zero, and a product of the type $(xy)(zt)$ is not zero when $x=y$, $z=t$ and $xy=zt$, which happens if and only if $x=y=z=t$. However, in this case $(xy)(zt)=(xz)(yt)$ and therefore $f$ is PI.
\end{proof}
\begin{rem}
Note that if a multilinear polynomial $p(x_1,\dots,x_m)$ has a $1$-dimensional image, i.e. either $<U>$ or $<V>$,
it is PI of $\M_0$.
Indeed, its evaluation on $\M_0$ must either coincide with its evaluation on $\M$ or it must be $\{0\}$. However, it should be invariant under the automorphism $\psi$, which is possible only in the case that $p$ is PI of $\M_0$. Nevertheless, this  does not imply that such a polynomial does not exist: even in the case  $\F=K[\omega]$, where  $\psi$ can be extended to $\M$, we need to conjugate elements of $\F$, and this will change the coefficients of the polynomial $p$. The problem considering the  existence  of such polynomials remains being open.
\end{rem}
The possible multilinear evaluations on $\M_0$ are described in
\begin{theorem}
Let $\F$ satisfy $\Char\F\neq 3$. If $p(x_1,x_2,\dots,x_m)$ is a  multilinear commutative non-associative  polynomial with coefficients in $\F$, then the evaluation of $p$ over ${\M}_0$ is either:
\begin{enumerate}
\item $\{0\}$;
\item ${\M}_{0}$;
\end{enumerate}
\end{theorem}
\begin{proof}
Indeed, there are no $1$-dimensional multilinear evaluations since, if $\Image p=<aU+bV>$, $aU+bV$ must be proportional to $\varphi(aU+bV)=a\omega^2 U+b\omega V$ which is possible only if one of the coefficients $a$ or $b$ equals zero. However, this is also impossible, since in this case, $\Image p$ is not invariant under $\psi$.
\end{proof}
Another important subalgebra of $\M$ is the  subalgebra $\tilde{\M}$: the rock-paper-scissors without unit, i.e. the kernel of the homomorphism $\Sc$. Here we take the three element basis $U,V$ (which were already defined) and $W=\frac{1}{3}(P+R+S)$.
In this case,
$$W^2=W,\ WU=\frac{1+2\omega}{3}U,\ \text{and}\  WV=\frac{1+2\omega^2}{3}V.$$
The problem as to whether a multilinear evaluation  on $\tilde\M$ must be a vector space, remains being open. However, we can prove the following:
\begin{lemma}\label{tilde}
Let $\F$ satisfy $\Char\F\neq 3$. If $p(x_1,x_2,\dots,x_m)$ is a  multilinear commutative non-associative  polynomial with coefficients in $\F$, then the evaluation of $p$ over $\tilde\M$ is either:
\begin{enumerate}
\item $\{0\}$;
\item $\left<U\right>$;
\item $\left<V\right>$;
\item $\left<W\right>$;
\item ${\M}_{0}=\left<U,V\right>$;
\item $\left<U,W\right>$;
\item $\left<V,W\right>$;
\item Zariski dense in $\tilde\M$.
\end{enumerate}
\end{lemma}

\begin{proof}
According to Lemma \ref{2 dim lemma}, $\Image p$ must be either a vector space or at least $3$-dimensional.

If the  dimension  of $\Image p$ is no more than $2$, it is a vector space. If $\dim\Image p= 0$, then $p$ is PI and we have the case (1). If $\dim\Image p=1$, $\Image p$ is a line which is invariant under the automorphism $\varphi$, and we have one of the cases (2)-(4). If $\dim\Image p= 2$, we have a two-dimensional subspace invariant under $\varphi$.
Consider some evaluation of $p$: $q=aU+bV+cW$ with at least two nonzero coefficients
$a,b,c\in\F$.
Note that $\varphi(U)=\omega^2 U, \varphi(V)=\omega V, \varphi(W)=W.$ Thus, the elements $\varphi(q)=a\omega^2 U+b\omega V+cW$ and $\varphi^2(q)=a\omega U+ b\omega^2 V+cW$ belong to the image of $p$. The linear span of these three elements is the linear span of the basis elements $\{U,V,W\}$.

 In particular, we obtain that one of the coefficients of $q$ must zero, and the ($2$-dimensional) image of $p$ contains a plane spanned by two basis elements (and thus coincides with it).
Therefore, we have one of the cases (5)-(7).
Finally, if $\dim\Image p= 3$,  the image is a Zariski dense subset, and we have the case (8).
\end{proof}

Note that not all these options are possible:
\begin{theorem}
Let $\F$ satisfy $\Char\F\neq 3$. If $p(x_1,x_2,\dots,x_m)$ is a  multilinear commutative non-associative  polynomial with coefficients in $\F$, then the evaluation of $p$ over $\tilde\M$ is either:
\begin{enumerate}
\item $\{0\}$;
\item $\left<U\right>$;
\item $\left<V\right>$;
\item ${\M}_{0}=\left<U,V\right>$;
\item Zariski dense in $\tilde\M$.
\end{enumerate}
\end{theorem}
\begin{proof}
Options $(4),(6)$ and $(7)$ in Lemma \ref{tilde} are impossible since if the sum of coefficients of $p$ is $c\neq 0$, the element $p(I,I,I,\dots,I)=cI$ belongs to the image of $p$, for $I$ being arbitrary idempotent of $\tilde M$. In particular, $P,R$ and $S$ are idempotents. In this case the linear span of $\Image p$ must be equal to $\tilde M$, which does not hold for these three cases.
\end{proof}

Unfortunately, the question of possibility of cases $(2)$ and $(3)$  remains being open. The other problem is, whether or not the polynomial in the last case  must be surjective.

\section{Semi-homogeneous polynomials}\label{homogen}
In this section, we have more questions than answers. Nevertheless, we  can definitely  claim the following: the evaluation of any such polynomial should be invariant with respect to the automorphism $\varphi$.
We have a conjecture:
\begin{conj}\label{conj-1var}
Any homogeneous polynomial in one variable with nonzero sum of coefficients, has a Zariski dense image set.
\end{conj}
This is an interesting question to study. Indeed, considering monomials depending on one variable, there are different monomials of the same degree. For instance, the monomial $(x^2)^2$ is not the same as $x(x(x^2))$. Not only as monomials are they different: they also have different evaluations.
For example, if $x=P+R-2S$ then  $(x^2)^2=9(R-P)$ and
 $x(x(x^2))=9(P-R)$. Of course, if $\Char\F=2$, this is the same. The case $\Char \F=2$ can be considered separately. In  particular, for $\F=\F_2$ being the field of two elements, the evaluations of $(x^2)^2$ and $x(x(x^2))$ coincide for every $x$. Moreover, evaluations of any two monomials in one variable of equal degree coincide, which makes the monomial function $x^d$ being well defined.

If Conjecture \ref{conj-1var} holds, we can conclude the following:
\begin{conj}
Let $p(x_1,\dots, x_m)$ be any semi-homogeneous polynomial evaluated on $\M$ of degree $d$, and suppose that the field $\F$ is closed under  $d$-roots. Then the image set of $p$ satisfies one of the following conditions:
\begin{enumerate}
\item $\Image p=\{0\}$;
\item $\Image p$=$\left<P+R\omega+S\omega^2\right>$;
\item $\Image p$=$\left<P+R\omega^2+S\omega\right>$;
\item $\Image p$ is Zariski dense in ${\M}_{0}$;
\item $\Image p$ is Zariski dense in $\M$.
\end{enumerate}
\end{conj}
This conjecture follows from the previous one:
if the sum of the coefficients is not zero, we can consider the polynomial $q(x)=p(x,x,\dots,x)$, which according to Conjecture \ref{conj-1var}, has a Zariski dense image set  in $\M$, and its image is a subset of the image of $p$.
If the sum of the coefficients is zero, then, as we know,both $\Sc(p)$ and $\trace(p)$ vanish on each evaluation and hence $\Image p\subseteq\M_0$. The image of any semi-homogeneous polynomial is a cone, and  therefore, there are three options:The image is $2$-dimensional and its Zariski closure is $\M_0$; The image  is $1$-dimensional and its image is one of the two possible lines; The image is $0$-dimensional, and in this case, $p$ should be a PI.
Note that if conjecture \ref{conj-1var} does not hold, then there is one more possible option for the $1$-dimensional image: the line $\left<P+R+S\right>$.

\section{Conclusion}
Questions related to the evaluations of multilinear and homogeneous polynomials are actual and applicable. This work continues series of works \cite{BMR1,BMR2,BMR3,BMR4,M1,M2,BMRY}.

config: arxiv


TITLE: How to show that any nontrivial valuation on the field of rational numbers is equivalent to some p-adic valuation?
QUESTION [1 upvotes]: I have started with a nontrivial valuation v on Q. Suppose V is the corresponding valuation ring. I want to show that V is equal to the valuation ring of some p-adic valuation for some prime p. Then by definition of equivalence this will hold. For this I use the fact that as v is nontrivial valuation so there must exist atleast one prime p such that 1/p is not in V. From this I can show that V⊆Vp where Vp is the valuation ring of the p-adic valuation on Q which is precisely the set of rationals with denominator  not divisible by p. But am stuck with the other way inclusion. Can anybody suggest to proceed furthur?

REPLY [1 votes]: I don't know how you obtained $O_v\subset \Bbb{Z}_{(p)}$.
$O_v\subsetneq \Bbb{Q}$.
$v(1)=0$ gives that $v(n)\ge 0$ thus $\Bbb{Z}\subset O_v$.
There is some $p$ such that $v(p)>0$ because otherwise $O_v=\Bbb{Q}$.
$m_v\cap \Bbb{Z}$ is a prime ideal containing $p$ thus it is $(p)$ and hence $O_v$ contains $\Bbb{Z}_{(p)}$.
For any $a\in \Bbb{Q}-\Bbb{Z}_{(p)}$, $\Bbb{Z}_{(p)}[a]=\Bbb{Q}$, thus $O_v=\Bbb{Z}_{(p)}$.


text:
\begin{document}

\maketitle

\begin{abstract}
We propose a new model of asynchronous batch codes that allow for
parallel recovery of information symbols from a coded database in an asynchronous manner, i.e. when
different queries take different time to process. Then, we show that the graph-based batch codes studied by
\vit{Rawat \emph{et al.}} are asynchronous. Further, we demonstrate that hypergraphs
of Berge girth at least 4, respectively at least 3, yield graph-based asynchronous batch codes,
respectively private information retrieval (PIR) codes.
We prove the hypergraph-theoretic proposition that the
maximum number of hyperedges in a hypergraph of a fixed Berge girth equals
the quantity in a certain generalization of the hypergraph-theoretic
(6,3)-problem, first posed by Brown, Erd\H os and S\'os. We then
apply the constructions and bounds by Erd\H os, Frankl and R\"odl
about this generalization of the (6,3)-problem, known as the (3$r$-3,$r$)-problem,
to obtain batch code constructions and bounds on the redundancy of the graph-based asynchronous batch and PIR codes.
Finally, we show that the optimal redundancy $\rho(k)$ of graph-based asynchronous batch codes of dimension $k$
with the query size $t=3$ is $2\sqrt{k}$. Moreover, for a general fixed value of $t \ge 4$,
$\rho(k) = O\left({k}^{1/(2-\epsilon)}\right)$ for any small $\epsilon>0$.
For a general value of $t \ge 4$, $\lim_{k \rightarrow \infty} \rho(k)/\sqrt{k} = \infty$.

\renewcommand{\thefootnote}{\fnsymbol{footnote}}
\footnotetext{The work of Ago-Erik Riet is supported by the Estonian Research Council grant PSG114.
The work of Vitaly Skachek is supported by the Estonian Research Council grant PRG49.
The work of Eldho K. Thomas is supported by the
European Regional Development Fund through Mobilitas Pluss grant MOBJD246.}
\end{abstract}

\begin{IEEEkeywords}
primitive linear multiset batch codes, private information retrieval codes, extremal hypergraph theory, Tur\'an theory, packing designs.
\end{IEEEkeywords}

\vspace{-1ex}
\section{Introduction}

Batch codes were originally proposed by Ishai \emph{et al.}~\cite{Ishai} for load balancing in distributed systems.
One particular class of batch codes that we are interested in is linear (computational) batch codes~\cite{Lipmaa, dimakis-batch, Zhang-Skachek, Vardy} where the data is viewed as elements of a finite field written as a vector, and it is encoded using a linear transformation of that vector.

Codes for private information retrieval (or PIR codes, in short) were proposed by Fazeli, Vardy and Yaakobi~\cite{Fazeli}. It was suggested therein to emulate standard private information retrieval protocols using a special layer (code) which maps between the requests
of the users and the data which is actually stored in the database.

Linear batch codes and PIR codes have many similarities with locally-repairable codes~\cite{dimakis-survey},
which are used for repair of lost data
in distributed data storage systems. The main difference, however, is that in locally-repairable codes, it is
coded symbols that are to be repaired, while in batch codes and PIR codes it is information symbols that are to be restored~\vit{\cite{skachek}}.

\section{Notation and Preliminaries}

\subsection{Batch and PIR Codes}

We denote by $\nn$ the set of natural numbers. For $n \in \nn$, define $[n] \triangleq \{1, 2, \cdots, n\}$.

The notation $\bldI$ is used for an identity matrix.
In this work, we consider only (primitive, multiset) batch codes as defined in~\cite{Vardy}.
\begin{definition}[\hspace{-0.1ex}\cite{Vardy}]
\label{batch}
An $(n,k, t)$ batch code $\code$ over a finite alphabet $\Sigma$ is defined by
an encoding mapping $\Csf \; : \; \Sigma^k \rightarrow \Sigma^n$, and a decoding mapping $\Dsf \; : \; \Sigma^n \times [k]^t\rightarrow \Sigma^t$, such that
\begin{enumerate}
\item
For any $\bldx \in \Sigma^k$ and

$i_1, i_2, \cdots, i_t \in [k] \; $,

\[
\Dsf\left(\bldy=\Csf(\bldx), i_1, i_2, \cdots, i_t\right) = (x_{i_1}, x_{i_2}, \cdots, x_{i_t}). \; \]
\item
The symbols in the query $(x_{i_1}, x_{i_2}, \cdots, x_{i_t})$ can be reconstructed from
$t$ respective pairwise disjoint recovery sets of symbols of $\bldy$ (the symbol $x_{i_\ell}$ is reconstructed from the $\ell$-th recovery set for each $\ell$, $1 \le \ell \le t$).
\end{enumerate}
\label{def:batch}
\end{definition}

Let $\ff = \ff_q$ be a finite field with $q$ elements, where $q$ is a prime power,
and $\code$ be a linear $[n,k]$ code over $\ff$. Denote the redundancy $\rho \triangleq n-k$.
For a \emph{linear batch code}, the encoding of $\Csf$ is given as a multiplication
by a $k \times n$ generator matrix $\bldG$ over $\ff$ of an information vector $\bldx \in \ff^k$,
\begin{equation}
\bldy = \bldx \cdot \bldG \; ;~~ \bldy \in \ff^n .
\label{def:linear}
\end{equation}
A \emph{linear batch code} with the parameters $n$, $k$ and $t$ over $\ff_q$, where $t$ is a number of queried symbols, is denoted as an \emph{$[n,k,t]_q$-batch code}.

\begin{definition}[\hspace{-0.1ex}\cite{Fazeli}]
\emph{Linear PIR codes} are defined similarly to linear primitive multiset batch codes, with a difference that the supported queries are of the form $(x_i, x_i, \cdots, x_i), \; i \in [k],$
(and not $(x_{i_1}, x_{i_2}, \cdots, x_{i_t}), \; i_1, i_2, \cdots, i_t \in [k]$ as in batch codes).
\end{definition}

In what follows we only consider linear PIR codes. \vit{For constructions of PIR codes see, for example,~\cite{Lin, Vajha}.}

\subsection{Graphs and Hypergraphs}

Let $W^{(r)}$, $r \ge 2$, denote the set of all unordered $r$-tuples of distinct elements of the set $W$.

A \emph{graph} $G(V,E)$ consists of a finite set $V$, called the \emph{vertex set} and a finite set $E\subseteq V^{(2)}$ of pairs of vertices, called the \emph{edge set}. The graph $G(V,E)$ is \emph{bipartite} with \emph{bipartition} (or \emph{parts}) $(A,B)$ if $A\cup B=V$, $A\cap B = \varnothing$, and $|A\cap e|=1$ and $|B\cap e| = 1$ for every edge $e\in E$. We denote the bipartite graph with distinguished parts $A$ and $B$ as $G(A,B,E)$ where we call $A$ the \emph{left part} and $B$ the \emph{right part}. A \emph{$b$-cycle} in a graph $G(V,E)$ is a cyclic sequence of $b$ vertices and $b$ edges, alternatingly between vertices and edges, such that each edge consists precisely of the two vertices on each side of it in the sequence. A bipartite graph $G(A,B,E)$ is \emph{left-regular} if all \emph{left degrees} $\d (a)\triangleq |\{e\in E\, : \, a\in e\} |$, where $a\in A$, are equal.

A \emph{hypergraph} $\mathcal{G}(V,E)$ consists of a finite set $V$ of vertices and a finite collection $E$ of subsets of $V$, called (hyper)edges. The hypergraph is \emph{$r$-uniform}, or an \emph{$r$-graph}, if each hyperedge consists of the same number $r$ of vertices, that is, $E \subseteq V^{(r)}$. Thus, a graph can be viewed as $2$-uniform hypergraph.
A \emph{Berge cycle} in a hypergraph is a sequence $(e_1,v_1,e_2,v_2,\ldots,v_b,e_{b+1})$ where $e_1,e_2,\ldots,e_b$ are distinct hyperedges, $v_1,v_2,\ldots,v_b$ are distinct vertices, $v_{i-1}, v_i\in e_i$ for all $i$ (we have taken all indices modulo $b$ when defining the sequence) and $e_1=e_{b+1}$.

A hypergraph is \emph{Berge-disconnected} if its vertex set $V$ can be partitioned into two non-empty sets $V=V_1\cup V_2$ such that, for each hyperedge $e$, either $e\cap V_1=\varnothing$ or $e\cap V_2=\varnothing$; it is \emph{Berge-connected} if it is not disconnected. A hypergraph has \emph{Berge girth} equal $k$ if (a) it contains a Berge cycle with $k$ hyperedges; (b) it contains no Berge cycles with fewer than $k$ hyperedges. If a subset of vertices is allowed several (a finite number of) times as a hyperedge, we have a multihypergraph.
We note that a multi-$r$-graph for $r\geq 2$ with Berge girth at least 3 is necessarily a simple hypergraph, i.e.~no subset of vertices appears as an edge several times.

The following definition of the correspondence between bipartite graphs and (multi)hypergraphs will be instrumental.
\begin{definition}
\label{def:correspondence}
With a (multi)hypergraph $\mathcal{G}(V,E)$ one can associate the bipartite \emph{incidence graph} $G(E,V,I)$ with left part $E$ and right part $V$ where $\{e,v\}$ is an edge, i.e.~$\{e, v\}\in I$ in $G$ if and only if $v\in e$ in $\mathcal{G}$. By going backwards, given a bipartite graph $G(E,V,I)$ we construct a (multi)hypergraph $\mathcal{G}(V,E)$ by identifying each $e\in E$ with the set $\{v\in V\,|\,\{e,v\}\in I\}$.
\end{definition}
Therefore, multihypergraphs are in one-to-one correspondence with bipartite graphs.
A multihypergraph is Berge-connected if and only if its incidence graph is connected; there is a one-to-one correspondence between Berge cycles with $k$ hyperedges in the multihypergraph and cycles of length $2k$ in the incidence graph.

An $r$-graph $\mathcal{G}'(V',E')$ is a \emph{sub-$r$-graph} of an $r$-graph $\mathcal{G}(V,E)$ if $V'\subseteq V$ and $E'\subseteq \{e\in E \,|\, e\subseteq V'\}$. We say that the sub-$r$-graph is \emph{induced} by the vertex set \vit{$V'$, if in addition, we have} $E'= \{e\in E \,|\, e\subseteq V'\}$. Similarly we say that a subset of hyperedges $E'$ \emph{induces} the vertex set $\bigcup_{e\in E'} e$.

\subsection{Graph-based Batch and PIR Codes}
Let $\code$ be an $[n, k, t]_q$ batch (PIR) code defined by a systematic encoding matrix $\bldG = \left[ \bldI | \bldA \right]$.

Take $\bldy \in \code$. The symbols of $\bldy$ corresponding to the systematic part of $\bldG$ are called information
symbols, and the remaining symbols are called parity symbols. The following bipartite graph representation was proposed
in~\cite{dimakis-batch}: let $G(A,B,E)$ be a bipartite graph, where $A$ is the set of the information symbols,
$B$ is the set of the parity symbols, and
$E = \Big\{ \{ u, v \} : u \in A, v\in B, u \mbox{ participates in parity } v \Big\}$.
\vspace{-1ex}
\begin{theorem}(\hspace{-0.1ex}\cite[Theorem 1 and Lemma 2]{dimakis-batch})
\label{theorem1-dimakis}
Let $\code$ be an $[n, k]$ systematic code represented by the bipartite graph $G(A, B, E)$.
Assume that there exists an \emph{induced subgraph} $H(A, B', E')$ of $G$, that is, $B' \subseteq B$ and $E' = \{e\in E \, :\, |e\cap B'|=1 \}$, such that:
\begin{itemize}
\item[(i)] Each node in $A$ has degree at least $t-1$ in the bipartite graph $H$.
\item[(ii)] The graph $H$ has girth $\ge 8$ (respectively, $\ge 6$).
\end{itemize}
Then, $\code$ is an $[n, k, t]$ batch code (respectively, PIR code).
\end{theorem}

It follows from Theorem~\ref{theorem1-dimakis} that constructions of left-regular bipartite graphs  without short cycles yield constructions of batch and PIR codes.
In what follows, we use this approach in order to construct \vit{batch and PIR codes with good parameters}.
Specifically, we use known constructions of good hypergraphs, which can be
mapped to bipartite graphs without short cycles, in order to construct good codes.

\section{Asynchronous batch codes}

In this section, we introduce a new special family of batch codes, termed \emph{asynchronous batch codes}.
Assume that $\code$ is a linear $[n, k, t]$ batch code as in Definition \ref{batch}, used for retrieving a batch of $t$ symbols $(x_{\ell_1}, x_{\ell_2}, \cdots, x_{\ell_t})$, $\ell_{i} \in [k]$, in parallel from a coded database that consists of $n$ servers, such that at most one symbol is retrieved from each server. To this end assume that the response time of servers for different requests varies, and thus some symbol $x_{\ell_j}$ (w.l.o.g.) can be retrieved faster then the other symbols. In asynchronous retrieval mode, once $x_{\ell_j}$ was retrieved, it is possible to
retrieve any other request $x_{\ell_{t+1}}$, $\ell_{t+1} \in [k]$, in parallel to retrieving of $(x_{\ell_1}, x_{\ell_2}, \cdots, x_{\ell_{j-1}}, x_{\ell_{j+1}}, \cdots, x_{\ell_t})$, without reading more than one symbol from each server. In that way, the asynchronous batch codes support (asynchronous) retrieval of $t$ symbols in parallel. We proceed with a formal definition.

\begin{definition}
An asynchronous (linear primitive multiset) $[n, k, t]$ batch code $\code$ is a (linear primitive multiset) batch code with the additional property that for any legal query $(x_{\ell_1}, x_{\ell_2}, \cdots, x_{\ell_t})$, for all $\ell_{i} \in [k]$,
it is always possible to replace $x_{\ell_j}$ by some $x_{\ell_{t+1}}$, $\ell_{t+1} \in [k]$, such that
$x_{\ell_{t+1}}$ is retrieved from the servers not used for retrieval of $x_{\ell_1}, x_{\ell_2}, \cdots, x_{\ell_{j-1}}, x_{\ell_{j+1}}, \cdots, x_{\ell_t}$, without reading more than one symbol from each server.
\end{definition}

\vit{
\begin{example}
Consider the systematic $[8,4,3]_2$ batch code $\code$ generated by the matrix
\[
\bldG \; = \; \left(
\begin{matrix}
1&0&0&0&1&0&1&0 \\
0&1&0&0&1&0&0&1 \\
0&0&1&0&0&1&1&0  \\
0&0&0&1&0&1&0&1
\end{matrix}
\right) \; .
\]
The query $(x_1,x_1,x_1)$ can be retrieved from the following disjoint sets of symbols:
$x_1 = y_1, \; x_1 = y_2 + y_5 \; , x_1 = y_3 + y_7\; . $

Assume that the first queried symbol $x_1$ has already been retrieved (while the last two queries are still being served), and the new query $x_2$ has arrived. Then, we can use the recovery $x_2 = y_4 + y_8$ for the newcomer $x_2$, without affecting the recovery sets of the other two queries.

It can be shown that for any initial selection of the recovery sets, and for any finished query and new query,
there is always a way to select disjoint recovery sets. Therefore, $\code$ is an asynchronous $[8,4,3]_2$ batch code.
\end{example}
}

It is straightforward to see that any asynchronous $[n, k, t]$ batch code is an $[n, k, t]$ batch code. The opposite, however, does not always hold.

\begin{example}
Consider batch codes, which are obtained by taking simplex codes as suggested in \cite{WKC2015}.

For example, $\code$, formed by the matrix
\[
\bldG = \left(
\begin{matrix}
1&0&0&1&1&0&1 \\
0&1&0&1&0&1&1 \\
0&0&1&0&1&1&1
\end{matrix}
\right)
\]
is a $[7,3,4]_2$ batch code. Assume that the query $(x_1, x_1, x_1, x_1)$ was submitted by the users. Then, one copy of $x_1$
is retrieved from $y_1$, and for each of the remaining three copies of $x_1$, at least two symbols of $\bldy$ have to be used.
Assume that the query that uses $y_1$ was served, but the remaining queries are still being served.
If the next query $x_2$ arrives, it is impossible to serve it without accessing one of the servers containing
$y_2, \cdots, y_7$ at least twice. Therefore, $\code$ is not an asynchronous $[7,3,4]_2$ batch code.
\end{example}

It turns out, that the conditions in Theorem~\ref{theorem1-dimakis} yield asynchronous batch codes. More formally:

\begin{theorem}
\label{thrm-asynchronous}
Let $\code$ be an $[n, k]$ systematic code represented by the bipartite graph $G(A, B, E)$.
Assume that there exists an \emph{induced subgraph} $H(A, B', E')$ of $G$, that is, $B' \subseteq B$ and $E' = \{e\in E \, :\, |e\cap B'|=1 \}$, such that:
\begin{itemize}
\item[(i)] Each node in $A$ has degree at least $t-1$ in the bipartite graph $H$.
\item[(ii)] The graph $H$ has girth at least 8.
\end{itemize}
Then, $\code$ is an {\bf asynchronous} $[n, k, t]$ batch code.
\end{theorem}
The omitted proof follows from \vit{\cite[Lemma 2]{dimakis-batch}}:
\begin{lemma}
\label{lemma3-dimakis}
Let $\code$ be an $[n, k]$ systematic code represented by the bipartite graph $G(A, B, E)$.
Assume that there exists an \emph{induced subgraph} $H(A, B', E')$ of $G$, that is, $B' \subseteq B$ and $E' = \{e\in E \, :\, |e\cap B'|=1 \}$, such that:
\begin{itemize}
\item[(i)] Each node in $A$ has degree at least $t-1$ in the bipartite graph $H$.
\item[(ii)] The graph $H$ has girth at least 8.
\end{itemize}
Then, each message symbol has at least $t$ disjoint repair group (including the group formed by the information symbol itself). Moreover, for any $i,j \in [k]$, $i \neq j$, any one of the disjoint repair groups for the message symbol $x_i$ has common symbols
with at most one of the disjoint repair groups for the message symbol $x_j$.
\end{lemma}

\begin{definition}
An asynchronous $[n,k,t]$ batch code, which can be represented as in Theorem~\ref{thrm-asynchronous}, is called a {\bf graph-based asynchronous} batch code.
\end{definition}

\section{Case $t=3$}
In this section, we start by considering a simple case $t=3$. We derive a tight upper bound on
the optimal redundancy of graph-based asynchronous batch codes.

\begin{theorem}
Let $\code$ be a graph-based asynchronous $[n,k,t \ge 3]$ batch code.
Then, its redundancy is $\rho \ge 2\sqrt{k}$.
\end{theorem}

\begin{proof}
Let $\hat{G} = (A, B, \hat{E})$ be a bipartite graph that corresponds to the code $\code$.
Then, the girth of $\hat{G}$ is $\ge 8$, and $\d(a) \ge 2$ for $a \in A$.
Also, $k=|A|$, $n-k=|B|$, and $t \ge 3 $.

First, we delete edges of $\hat{G}$ such that after deletion $\d(a)=2$ for $a \in A$, and denote the new graph $G$ (note that we change the code). We construct a new (non-bipartite) graph, $G' = (V', E')$, from $G$, by following the correspondence in
Definition~\ref{def:correspondence}. Since the left degree of $G$ is 2, the result is indeed a graph (rather than hypergraph).
Specifically, take $V' = B$. For each $u \in A$,
replace $u$ and two edges $\{u, v_1\}$ and $\{u, v_2\}$ incident with it by a new edge $e_u = \{ v_1, v_2 \}$.
The construction implies that there is a cycle of length $2t$ in $G$ if and only if there is a cycle of length $t$ in $G'$.
Thus, $G$ has girth $\ge 8$ if and only if $G'$ has girth $\ge 4$.

By Mantel's Theorem~\cite{mantel} (see also: Tur\'an's Theorem~\cite{turan}), this implies that the number of edges $|E'|$  satisfies $ |E'| \le |V'|^2/4 \; .$
Since $|A| = k$ and $|B| = n-k$, we obtain that $|V'| = n-k$ and $|E'| = k$. Therefore, the redundancy $\rho = n-k \ge 2\sqrt{k}$.
The redundancy of the original code is at least as large.
\end{proof}

This bound is in fact tight.
For example, consider a complete bipartite graph $G'$ with a vertex set $V' = A' \cup B'$, $A' \cap B' = \varnothing$, $|A'| = |B'|$. This graph has $|V'|^2/4$ edges in total, and girth 4. Moreover, this graph has the largest possible
number of edges for any girth-4 graph with $|V'|$ vertices, as seen by Mantel's Theorem~\cite{mantel}.

Next, we convert this graph into a bipartite graph $G$
by using the inverse of the above mapping. Namely, each edge is replaced
by a triple ``edge, vertex, edge''.  We obtain that $G$ is a left regular bipartite graph of left degree 2 with $|A| = |V'|^2/4$ and $|B| = |V'|$. The graph $G$ has girth 8 and hence it yields an asynchronous batch code having length $n = |V'|^2/4+ |V'|$, number of information symbols $k=|V'|^2/4$, redundancy $\rho = 2\sqrt{k}=|V'|$, and $t=3$.

We remark that the lower bound $\rho \ge \sqrt{2k} + O(1)$ on the optimal redundancy of PIR codes (for $t\ge 3$)
was recently obtained by Rao and Vardy in~\cite{Rao-Vardy}, and their result implies the same lower bound on the redundancy
of linear batch codes. Moreover, they show that this bound is tight for PIR codes. In this section,
we showed a tighter lower bound $\rho \ge 2\sqrt{k}$ for graph-based asynchronous batch codes (for all $t \ge 3$), and presented an explicit construction of asynchronous batch codes for $t = 3$ that attain this bound. As we show in the sequel,
for graph-based asynchronous batch codes with $t > 3$ the lower bound on $\rho$ can be further tightened.
We consider a modified code also for general $t$.

\section{Hypergraph Theory}
In their 1973 papers, Brown, Erd\H os and S\'os~\cite{brown1}, \cite{brown2} pose the following extremal combinatorial problems on $r$-graphs.

\begin{problem}
Let $f^{(r)}(\eta;\kappa,s)$ denote the smallest $m$ such that every $r$-graph on $\eta$ vertices with $m$ edges contains at least one sub-$r$-graph on $\kappa$ vertices with $s$ edges. What are the bounds on $f^{(r)}(\eta;\kappa,s)$ for fixed $r$, $\kappa$ and $s$?
\end{problem}

Observe that $F^{(r)}(\eta;\kappa,s) \triangleq f^{(r)}(\eta;\kappa,s)-1$ is the maximum size (number of edges) of an $r$-graph \vit{with no set of $\kappa$ vertices containing} $s$ or more hyperedges. The resolution of the case $f^{(3)}(\eta;6,3)$, known as the $(6,3)$-problem, by Ruzsa and Szemer\'edi~\cite{ruzsa} is a classical result in extremal combinatorics. Erd\H os, Frankl and R\"odl~\cite{erdos} extended this result to any fixed $r$, also giving an easier construction for the lower bound, solving the so-called $(3r-3,3)$-problem. There are various later generalisations of~\cite{ruzsa} and~\cite{erdos}, see for example~\cite{alon} and the references therein, and the survey~\cite{furedi}.

In what follows, we show that finding the maximum number of hyperedges of a hypergraph with a given Berge girth is essentially a generalization of the $(6,3)$-problem for 3-graphs, called the $(\kappa r- \kappa, \kappa)$ problem for $r$-graphs in this terminology. Then, we apply the resolution of the $(3r-3,3)$ problem by~\cite{erdos} to batch codes.

\begin{theorem}\label{berge girth}
Let $B^{(r)}(\eta,\kappa)$ be the maximum number of hyperedges in an $r$-graph with $\eta$ vertices and Berge girth at least $\kappa+1$. Then $F^{(r)}(\eta;\kappa r- \kappa, \kappa) = B^{(r)}(\eta,\kappa)$.
\end{theorem}

We prove this theorem in Lemmas~\ref{help}-\ref{kappa_lemma}.

\begin{lemma}\label{help}
For a Berge-connected hypergraph $\mathcal{G}(V,E)$ with $|V|\geq 2$ we have:

\begin{enumerate}
\item $\sum_{e\in E} (|e|-1) \geq |V|-1.$
\item $\mathcal{G}(V,E)$ contains no Berge cycles (is a Berge tree) if and only if
$\sum_{e\in E} (|e|-1) = |V|-1$.
\item
$\mathcal{G}(V,E)$ contains exactly one Berge cycle if and only if $\sum_{e\in E} (|e|-1) = |V|.$
\end{enumerate}
\end{lemma}
Lemma \ref{help} can be proved using properties of the incidence graphs, the proof is omitted.

\begin{definition}
\label{def:condition}
A hypergraph \emph{satisfies the $(\kappa r-\kappa,\kappa)$-condition} if no set of $\kappa r-\kappa$ of its vertices contains $\kappa$ or more hyperedges.
\end{definition}
\begin{comment} As we shall see, an $r$-graph satisfying the $(\kappa r-\kappa,\kappa)$-condition can be modified to additionally have Berge girth at least $\kappa+1$ while keeping the same number of hyperedges; an $r$-graph of Berge girth at least $\kappa+1$ already satisfies the $(\kappa r-\kappa,\kappa)$-condition.
\end{comment}
\begin{lemma}
\label{girth_lemma}
An $r$-graph of Berge girth at least $\kappa+1$ satisfies the $(\kappa r-\kappa,\kappa)$-condition.
\end{lemma}

\begin{proof}
Consider any $\kappa$ hyperedges of this graph. They induce no Berge cycle. For each of the Berge-connected components (maximal connected subhypergraphs) $\graph'(V',E')$ of the hypergraph induced by these $\kappa$ hyperedges, we have $\sum_{e\in E'} (|e|-1) = |V'|-1$ by Condition 2 of Lemma~\ref{help}, therefore $\sum_{e\in E} (|e|-1) = \kappa(r-1) = |V|-c$ for the hypergraph induced by these $\kappa$ hyperedges, where $c\geq 1$ is the number of Berge-connected components. Therefore the number of vertices induced by these $\kappa$ hyperedges is $\kappa(r-1)+c > \kappa r-\kappa$. Thus the hypergraph satisfies the $(\kappa r-\kappa,\kappa)$-condition.
\end{proof}

\begin{lemma}
An $r$-graph that satisfies the $(\kappa r-\kappa,\kappa)$-condition can be changed (its hyperedges can be re-wired) so that it still has the same number of hyperedges, still satisfies the $(\kappa r-\kappa,\kappa)$-condition and has Berge girth at least $\kappa+1$.
\label{kappa_lemma}
\end{lemma}

\begin{proof}
If an $r$-graph satisfies the $(\kappa r-\kappa,\kappa)$-condition, then from Definition~\ref{def:condition} the total number of vertices used by any $\kappa$ hyperedges is at least $\kappa(r-1)+1$. Consider two cases.

Case 1: $\;$ If the graph induced by these hyperedges were connected, by Condition 2 of Lemma~\ref{help} it contains no Berge cycles. In that case, there is no cycle with $\le \kappa$ hyperedges.

Case 2: $\;$ If the graph induced by these hyperedges were disconnected, consider a Berge-connected component which has some small Berge-cycles. This component has fewer than $\kappa$ hyperedges, since otherwise there are $\kappa$ of its connected hyperedges  violating the $(\kappa r-\kappa,\kappa)$-condition.

Next, take a vertex $v$ in two adjacent hyperedges $e$ and $e'$ of a cycle of $\le \kappa$ hyperedges, and re-wire $e$ by deleting $v$ from it, and adding into $e$ another vertex from outside the connected component.
This procedure strictly reduces the number of connected components with less than $\kappa$ hyperedges (an isolated vertex is a connected component by itself), therefore we can only repeat it a finite number of times, and eventually, we will have no Berge cycles on $\kappa$ or fewer hyperedges (see Lemma~\ref{help}).
\end{proof}

\section{PIR codes from hypergraphs of girth $\ge 3$}
\begin{definition}
A $\tau-(\eta,r,\lambda)$ packing design is an $r$-graph of $\eta$ vertices (called points) and of edges (called blocks) such that each $\tau$-tuple of vertices (points) is contained in at most $\lambda$ edges (blocks).
\end{definition}

Consider an $r$-graph $\graph(V,E)$, where $V$ is a point set and $E$ is a block set, $|V|=\eta$.
$\graph(V,E)$ of Berge girth at least 3 is equivalently an \emph{$2-(\eta,r,1)$ packing design}. The maximum size (number of blocks) $D(\eta,r)$ of a packing design, is upper-bounded by the well-known improved 1st and 2nd Johnson bounds~\cite{johnson2}, see also~\cite{mills}.

It follows from Keevash' result on the existence of designs~\cite{keevash}, which uses pseudorandomness arguments, that for all large enough $\eta$, there is a packing design attaining either the improved 1st or 2nd Johnson bound (see also~\cite{horsley} referring to an earlier version of~\cite{keevash}).

\vit{An interesting special case is when} each pair of points is contained in a unique block. \vit{In that case we} obtain a \emph{Steiner 2-design}, also known as a combinatorial \emph{$2-(\eta,r,1)$ block design}, or a \emph{$(\eta,r,1)$-BIBD (balanced incomplete block design)}. Compared to packing designs, Steiner 2-designs are much more rare, as they are simultaneously covering designs. Fazeli, Vardy and Yaakobi~\cite{Fazeli} use Steiner 2-designs to construct PIR codes. The construction works verbatim if one starts with a packing design. Following Wilson~\cite{wilson1}-\cite{wilson3},~\cite{Fazeli} obtain asymptotic redundancy of PIR codes $\rho = \Theta(\sqrt{k})$. Wilson in~\cite{wilson1}-\cite{wilson3}
 is concerned only with the asymptotics, while concrete packing designs will produce concrete PIR codes.

\begin{comment}
For very small values of $r$, the existing constructions giving packing designs are quite good. Generally,
in these cases such $\eta$ that Steiner 2-designs exist, are quite frequent.
For example, start with any number of parity symbols, and build a Steiner 2-design on a subset containing almost all parity symbols (while ignoring the other parity symbols; see, for example,~\cite{mills}).
By ignoring a small number $\eta-\eta'$ of parity symbols, we obtain an optimal graph-based PIR code with ${\eta'\choose 2} / {r\choose 2}$ information symbols and $\eta$ parity symbols.
\vit{
We obtain constructions of families of PIR codes with $k$ information symbols, whose redundancy $\rho = \rho(k)$ is close to a solution of the equation:
${\rho \choose 2} \Big/ {r \choose 2} = k $.
In particular, $\rho = \Theta(\sqrt{k})$.
}
\end{comment}

\section{Batch codes from hypergraphs of girth $\ge 4$}

Bounds and constructions for $r$-graphs $\mathcal{G}(V,E)$ on $\eta$ vertices of Berge girth at least 4

can be given via the $(3r-3,3)$-problem in the language of the $(6,3)$-problem, as seen from Theorem~\ref{berge girth}.

Bounds apply directly, while constructions may need to be modified slightly to lose small Berge cycles.

In~\cite{erdos}, Erd\H os, Frankl and R\"odl address precisely the $(3r-3,3)$-problem for $r \ge 3$. By modifying the construction of Behrend~\cite{behrend},

they construct $r$-graphs on $\eta$ vertices with the number of hyperdges asymptotically greater than $\eta^{2-\epsilon}$ for any
$\epsilon > 0$.
The construction produces hypergraphs of Berge girth at least 4. The authors prove an upper bound $o(\eta^2)$ on the maximum number of hyperedges, using an early version of the Szemer\'edi's Regularity Lemma (see~\cite{komlos} and~\cite{skokan}).

\begin{comment}
We shall explain the construction of Erd\H os, Frankl and R\"odl to obtain large $r$-graphs of Berge girth at least 4, giving rise to primitive multiset linear batch codes, with the aim to make the construction more accessible.

First, Erd\H os, Frankl and R\"odl prove the following Lemma, with the proof closely related to Behrend's original construction of large 3AP-free sets.

\begin{lemma}
There exists a set of positive integers $A\subseteq \{1,2,\ldots, n\}$ not containing three terms of any arithmetic progression of length $r$ and such that $$|A|\geq \frac{n}{e^{c\log r \sqrt{\log n}}}$$ for some absolute constant $c>0$.
\end{lemma}

\begin{proof}
Omitted. Please see the articles of Erd\H os, Frankl and R\"odl~\cite{erdos} and Behrend~\cite{behrend} for more details.
\end{proof}

Erd\H os, Frankl and R\"odl~\cite{erdos} construct an $\lfloor n/r \rfloor$-by-$r$ rectangular grid of vertices, and lines of cardinality $r$, intersecting each column, are hyperedges. The set of `slopes' is restricted to a set $A$ satisfying the previous Lemma, so that the hypergraph will have Berge girth at least 4, see~\cite{erdos} for more details. However, the hypergraph would still have Berge girth at least 3 if we do not restrict the set of slopes, thus giving rise to a slightly better PIR code than the obtained batch code.
\end{comment}

By mapping the hypergraph $\mathcal{G}(V,E)$ constructed in~\cite{erdos} back onto $G(E,V,I)$,
and by using notations for batch codes, we obtain a bipartite graph with $(n-k)^{2-\epsilon}$ left vertices and $n-k$ right vertices of girth $8$. The corresponding graph-based asynchronous batch code has $k = (n-k)^{2-\epsilon}$, and so its redundancy is bounded from above by $\rho(k) = n - k =
O\left({k}^{1/(2-\epsilon)}\right)$ for any $\epsilon>0$, and for any fixed $t$.

We note that the upper bound in~\cite{erdos} similarly yields the lower bound
\begin{equation}
\lim_{k \rightarrow \infty} \left( {\rho(k)}/{\sqrt{k}} \right) \rightarrow \infty \;
\label{eq:optimal_redundancy}
\end{equation}
for the optimal redundancy $\rho(k)$ of the graph-based asynchronous codes, for any fixed $t \ge 4$.

We compare these results with their counterparts in~\cite{Vardy}, where it was shown that
for any $t \ge 5$ the optimal redundancy of general (multiset primitive) linear batch codes behaves as $O(\sqrt{k} \log k)$,
while for $t \in \{3,4\}$ the corresponding redundancy is $O(\sqrt{k})$.
It is worth mentioning that for $t=4$ there is a gap between the optimal redundancy $O(\sqrt{k})$
of the codes studied in~\cite{Vardy} and the lower bound~(\ref{eq:optimal_redundancy}) for the graph-based asynchronous batch codes. It remains an open question what is the exact asymptotics of the optimal redundancy for the graph-based asynchronous batch codes for $t \ge 5$, and whether the lower bound~(\ref{eq:optimal_redundancy})
actually matches the upper bound $O(\sqrt{k} \log k)$ obtained in~\cite{Vardy},
or there is a gap between the optimal redundancy of these two families of codes.


TITLE: Split hateful people into groups that can exist in harmony (color a graph)
QUESTION [3 upvotes]: There are 51 people. Each person hates exactly 3 other people (who may or may not reciprocate). We need to split them into $n$ groups so that all groups exist in harmony.

What is min $n$?

Edit
We need to find $n$ such that, whatever the graph, $n$ groups will be enough to accomplish our goal. I see it was not clear initially.
Attempt
Tried to prove $n=5$ by considering 1 parent and 3 children of a node. Hence 1(parent)+3(children)+1(self) = 5. But this solution fails to consider other parents

REPLY [2 votes]: Phrase this as a coloring problem: we are trying to find a proper coloring of a graph whose vertices are the people, with an edge between two people whenever one of them hates the other.
This graph is $6$-degenerate: in any subgraph, there is a vertex of degree at most $6$. We can see this because the average degree in any subgraph is at most $6$ (if there are $n$ vertices in the subgraph, then there are at most $3n$ edges) and there must always be a vertex whose degree is at most the average degree.
A $k$-degenerate graph can be colored with $k+1$ colors, so this $6$-degenerate graph can be colored with $7$ colors: that is, we can separate the $51$ people into $7$ harmonious groups. We can do this recursively:

Pick some person involved in at most $6$ conflicts (that is, who is hated by at most $3$ people) and set them aside.
Partition the remaining $50$ people into $7$ harmonious groups using this same algorithm.
Put the person we set aside into a group that they have no conflicts with; this is possible because they have at most $6$ conflicts and we have $7$ groups.

This is best possible, since (as pointed out in the comments) the graph could contain a $K_7$: if among the first $7$ people numbered $1,2,3,4,5,6,7$, person $i$ hates $\{i+1,i+2,i+3\} \bmod 7$, then no two of these can be in the same group together. So we can't do better than $7$ groups.
A more general result can be found in this question.