\section{Introduction}

\noindent Since the pioneering work of Tur\'an \cite{turan}, the study of Tur\'an-type problems has been playing a central role in the field of extremal combinatorics. In this work, we present an improved probabilistic lower bound for a hypergraph Tur\'an-type problem introduced by Brown, Erd\H{o}s and S\'os \cite{BES71} in 1973. We also show that this new bound provides improved constructions for several seemingly unrelated problems in coding theory, including Parent-Identifying Set Systems, uniform Combinatorial Batch Codes and optimal Locally Recoverable Codes.

Let us begin with some necessary notation. For an integer $r\ge 2$, an $r$-uniform hypergraph (henceforth an $r$-graph) $\mathcal{H}:=(V(\mathcal{H}),E(\mathcal{H}))$ can be viewed as a pair of vertices and edges, where the vertex set $V(\mathcal{H})$ is a finite set and the edge set $E(\mathcal{H})$ is a collection of $r$-subsets of $V(\mathcal{H})$. An $r$-graph is called {\it $\mathcal{H}$-free} if it contains no subhypergraph which forms a copy of $\mathcal{H}$. For a family $\mathscr{H}$ of $r$-graphs, the {\it Tur\'an number}, ${\rm{ex}}_r(n,\mathscr{H})$, is the maximum number of edges in an $r$-graph on $n$ vertices which is $\mathcal{H}$-free for every $\mathcal{H}\in\mathscr{H}$.

Throughout this paper, an $r$-graph $\mathcal{H}$ always stands for its edge set $E(\mathcal{H})$. The vertex set $V(\mathcal{H})$ is viewed as a subset of $[n]:=\{1,\ldots,n\}$. Given a finite set $X\subseteq[n]$, denote by $\binom{X}{r}$ the family of $\binom{|X|}{r}$ distinct $r$-subsets of $X$. Hence, $\mathcal{H}=E(\mathcal{H})\subseteq\binom{[n]}{r}$. We will frequently use the standard Bachmann-Landau notations $\Omega(\cdot),\Theta(\cdot),O(\cdot)$ and $o(\cdot)$, whenever the constants are not important.

For integers $r\ge 2,e\ge 2,v\ge r+1$, let $\mathscr{G}_r(v,e)$ be the family of all $r$-graphs formed by $e$ edges and at most $v$ vertices; that is,
$$\mathscr{G}_r(v,e)=\{\mathcal{H}\subseteq\binom{[v]}{r}:|\mathcal{H}|=e\}.$$
An $r$-graph $\mathcal{H}$ is called {\it $\mathscr{G}_r(v,e)$-free} if it does not contain a copy of any member of $\mathscr{G}_r(v,e)$, namely, the union of any $e$ distinct edges of $\mathcal{H}$ contains at least $v+1$ vertices. In the literature, such $r$-graphs are also termed {\it sparse} \cite{sparse}. As in the previous papers (see, e.g. \cite{AlonShapira}), we use the notation $f_r(n,v,e):={\rm{ex}}_r(n,\mathscr{G}_r(v,e))$.

Since the study of $f_r(n,v,e)$ for $e=2$ or $r=2$ has been quite extensive (see, e.g. \cite{Erdos1964,Erdosr=2,Rodlpacking}), we focus on the asymptotic behavior of $f_r(n,v,e)$ for fixed integers $r\ge 3,e\ge 3,v\ge r+1$ as $n\rightarrow\infty$.
It was shown in \cite{BES71} that in general
\begin{equation}\label{BESbound}
  \begin{aligned}
   \Omega(n^{\frac{er-v}{e-1}})=f_r(n,v,e)=O(n^{\lceil\frac{er-v}{e-1}\rceil}).
  \end{aligned}
\end{equation}

\noindent The lower bound in (\ref{BESbound}) is obtained by a standard probabilistic method (now known as the alteration method, see, e.g. \cite{alon2016probabilistic}), and the (naivest) upper bound follows from a double counting argument, which uses the simple fact that any set of $\lceil\frac{er-v}{e-1}\rceil$ vertices can be contained in at most $e-1$ distinct edges.

Observe that the exponent of $n$ in (\ref{BESbound}) is tight for $e-1\mid er-v$; however, for $e-1\nmid er-v$, in general it is a notoriously hard problem to determine the correct order of the exponent of $n$. In particular, for fixed $r>k\ge 2,e\ge 3$ and $v=e(r-k)+k+1$, the study of $f_r(n,e(r-k)+k+1,e)$ as $n\rightarrow\infty$ has attracted considerable attention since the work of \cite{BES71,MR323647}. It is easy to check by (\ref{BESbound}) that
\begin{equation}\label{previouslowerbound}
\begin{aligned}
  \Omega(n^{k-\frac{1}{e-1}})=f_r(n,e(r-k)+k+1,e)=O(n^k).
\end{aligned}
\end{equation}

The following conjecture remains widely open.
\begin{conjecture}[see, \cite{BES71,AlonShapira}]\label{conjecture}
  For fixed integers $r>k\ge 2, e\ge 3$,
  $$n^{k-o(1)}<f_r(n,e(r-k)+k+1,e)=o(n^k)$$ as $n\rightarrow\infty$.
\end{conjecture}

Conjecture \ref{conjecture} has been studied in depth for more than forty years. For example, the first case of the conjecture, i.e., when $r=3, k=2$ and $e=3$, was already highly nontrivial. It was not solved until Ruzsa and Szemer\'{e}di \cite{Ruzsa-Szemeredi} proved the (6,3)-theorem
$$n^{2-o(1)}<f_3(n,6,3)=o(n^2),$$
where the upper bound follows from the celebrated Regularity Lemma \cite{Szemeredi}, and the lower bound is based on Behrend's construction \cite{Behrend46} on 3-term arithmetic progression free sets. The study of $f_3(n,6,3)$ indicates that the resolution of Conjecture \ref{conjecture} may rely heavily on the regularity lemmas\footnote{which include, for example, the graph regularity lemma and the hypergraph regularity lemma, see, \cite{Conlon-Fox}} and Behrend-type constructions, which are among the most powerful tools in extremal combinatorics. Improvements of (\ref{BESbound}) on sporadic or less general parameters have been obtained in a line of other works \cite{EPR,AlonShapira,other2,other1,Rodl,ge2017sparse}. Currently, the upper bound part of Conjecture \ref{conjecture} is known to be true for all $r\ge k+1\ge e\ge 3$ \cite{ge2017sparse}, and the lower bound part holds for $k>r\ge 2$ \cite{AlonShapira} and $k=2,e\in\{4,5,7,8\}$ \cite{ge2017sparse}.

Despite the efforts of many researchers, the lower bound \eqref{previouslowerbound} implied by (\ref{BESbound}) remains the best possible for $e\ge 4, r>k\ge 3$ and $e\not\in\{3,4,5,7,8\}, r>k=2$. In the proposition below we slightly improve the lower bound of \eqref{previouslowerbound} by a $(\log n)^{\frac{1}{e-1}}$ factor.

\begin{proposition}\label{presentlowerbound}
  For fixed integers $r>k\ge 2, e\ge 3$,
  $$f_r(n,e(r-k)+k+1,e)=\Omega(n^{k-\frac{1}{e-1}}(\log n)^{\frac{1}{e-1}})$$
  as $n\rightarrow\infty$.
\end{proposition}

Proposition \ref{presentlowerbound} is in fact an easy consequence of the following more general result.

\begin{theorem}\label{sparseturannumber1
  For fixed integers $r\ge 3,e\ge 3, v\ge r+1$ satisfying $\gcd(e-1,er-v)=1$ and sufficiently large $n$, there exists an $r$-graph with
  $$\Omega(n^{\frac{er-v}{e-1}}(\log n)^{\frac{1}{e-1}})$$
  edges, which is simultaneously $\mathscr{G}_r(ir-     \lceil \frac{(i-1)(er-v)}{e-1}\rceil    ,i)$-free for every $2\le i\le e$. In particular, setting $i=e$ we have
  $$f_r(n,v,e)=\Omega(n^{\frac{er-v}{e-1}}(\log n)^{\frac{1}{e-1}}).$$
\end{theorem}

The proof of this theorem is presented in Section \ref{maintheorem}. To see that Proposition \ref{presentlowerbound} indeed follows from  Theorem \ref{sparseturannumber1}, it suffices to write $er-v=k(e-1)+q$ for some $1\le q\le e-2$ (we exclude $q=0$ since in that case the exponent of (\ref{BESbound}) is tight), then $\gcd(e-1,er-v)=1$ holds, for example, when $q=\pm1$ or $e-1$ is a prime. Proposition \ref{presentlowerbound} follows by setting  $q=-1$.

The proof of Theorem \ref{sparseturannumber1} relies on a novel application of the lower bound on the hypergraph independence number due to Duke, Lefmann, and R{\"o}dl \cite{indset2}, as stated in Section \ref{maintheorem}. Since in our proof we cannot get rid of the coprime condition, it remains an interesting question to determine whether this constraint is necessary. Moreover, we have the following open problem.

\begin{problem}\label{conjecture2}
  For which parameters $r,e,v$ satisfying $r\ge 3, e\ge 3, v\ge r+1$ and $e-1\nmid er-v$, there exist a constant $\epsilon>0$ such that for sufficiently large $n$, $$f_r(n,v,e)=\Omega(n^{\frac{er-v}{e-1}+\epsilon})?$$
\end{problem}

It is noteworthy that sparse hypergraphs have found many applications in theoretical computer science and coding theory, some of which are listed as follows:

\begin{itemize}
  \item $\mathscr{G}_3(6,3)$-free 3-graphs were used in PCP analysis and Linearity Testing \cite{PCPtesting}, Communication Complexity \cite{CommunicationComplexity}, Monotonicity Testing \cite{Monotonicitytesting} and Coded Caching Schemes \cite{codedcaching};

  \item $\mathscr{G}_r(er-r,e)$-free $r$-graphs can be used to construct Perfect Hash Families \cite{Shangguan16} and Parent-Identifying Set Systems (IPPSs for short);

  \item $r$-graphs which are simultaneously $\mathscr{G}_r(i-1,i)$-free for each $1\le i\le e$
were used to construct uniform Combinatorial Batch Codes \cite{batch1} (uniform CBCs for short);
and in particular, for $r=3$ they were used in a bitprobe model with three probes \cite{probes};

\item  $r$-graphs which are simultaneously $\mathscr{G}_r(ir-i,i)$-free for each $1\le i\le e$ were used to construct
optimal Locally Recoverable Codes \cite{LRC} (optimal LRCs for short).
\end{itemize}
In Section \ref{application-2} we will present the applications of Theorem \ref{sparseturannumber1} in the constructions of IPPSs, uniform CBCs and optimal LRCs.

The rest of this paper is organized as follows.
In Section \ref{maintheorem} we present the proof of our main result, namely Theorem \ref{sparseturannumber1}.
In Section \ref{application-1} we discuss the applications of Theorem \ref{sparseturannumber1} to two problems in extremal combinatorics, and in Section \ref{application-2} we present three applications of Theorem \ref{sparseturannumber1} to coding theory.

\section{Proof of the main result} \label{maintheorem}

\noindent To prove Theorem \ref{sparseturannumber1} we will make use of the following lemma of Duke, Lefmann, and R{\"o}dl \cite{indset2} (whose proof applied a result of \cite{inpset1}). Note that an {\it independent set} of an $r$-graph is a subset of vertices such that no $r$ elements form an edge, and an $r$-graph is said to be {\it linear} if any two distinct edges share at most one vertex.

\begin{lemma}[see Theorem 2, {\rm{\cite{indset2}}}]\label{indset}
  For all fixed $r\ge3$ there exists a constant $c>0$ depending only on $r$ such that every linear $r$-graph on $n$ vertices with average degree\footnote{The original theorem in \cite{indset2} has the condition `with maximum degree at most $d$'. However, since for any hypergraph with average degree at most $d$, there exists a subhypergraph of it which has at least half of its vertices and maximum degree at most $2d$, it is not hard to observe that the assertion of the original theorem works also with the condition `with average degree at most $d$', at the expense of a worse constant $c$.} at most $d$ has an independent set of size at least $cn(\frac{\log d}{d})^{\frac{1}{r-1}}.$
\end{lemma}

Recall that we view the parameters $v,e,r$ as constants, whereas $n$ tends to infinity. Since we are only interested in the asymptotic behavior we do not make an attempt to optimize any of the constants. The following two inequalities are well known (see, e.g. \cite{alon2016probabilistic}).

\vspace{5pt}

\noindent\textbf{Chernoff's inequality.}  Suppose $X_1,\ldots,X_n$ are independent random variables taking values in $\{0,1\}$. Let $X$ denote their sum and let $\mu={\rm{E}}[X]$ denote the sum's expected value. Then for any $\delta\in[0,1]$, $\Pr[X\le(1-\delta)\mu]\le e^{-\frac{\delta^2\mu}{2}}$.

\vspace{5pt}

\noindent\textbf{Markov's inequality.} If $X$ is a nonnegative random variable and $a>0$, then $\Pr[X\ge a]\le\frac{{\rm{E}}[X]}{a}$.

\vspace{5pt}

Below we present the proof of Theorem \ref{sparseturannumber1}.

\begin{proof}[\textbf{Proof of Theorem \ref{sparseturannumber1}}]
Set $p:=p(n)=\Theta(n^{-\frac{v-r}{e-1}+\epsilon})$ for some $\epsilon>0$, which will be made explicit later.
Generate an $r$-graph $\mathcal{H}_0\subseteq\binom{[n]}{r}$ by picking each member of $\binom{[n]}{r}$ independently with probability $p$.
Let $X$ denote the number of edges in $\mathcal{H}_0$.
Clearly,
   \begin{equation}\label{X}
     \begin{aligned}
       {\rm{E}}[X]=p\binom{n}{r}=\Theta(n^{\frac{er-v}{e-1}+\epsilon}).
     \end{aligned}
   \end{equation}

For  $2\le i\le e-1$, let $\mathscr{Y}_i$ be the collection of all $i$ distinct edges of $\mathcal{H}_0$
whose union contains at most $ir-f(i)$ vertices, where  $f(i)$ will be determined later.
Let $Y_i$ denote the size of $\mathscr{Y}_i$. Then
   \begin{equation}\label{Yi}
      \begin{aligned}
       {\rm{E}}[Y_i]=O(p^in^{ir-f(i)})=O(n^{\frac{i(er-v)}{e-1}+i\epsilon-f(i)}),
     \end{aligned}
   \end{equation}

\noindent where the first equality follows from the fact that there are at most $O(n^{ir-f(i)})$ ways to choose $i$ edges whose union contains at most $ir-f(i)$ vertices.

We say that $e$ distinct edges of $\mathcal{H}_0$ form a bad $e$-system if their union contains at most $v$ vertices. Clearly, two distinct bad $e$-systems can share at most $e-1$ edges.
For each $2\le i\le e-1$, let $\mathscr{Z}_i$ be the collection of the unordered pairs of bad $e$-systems which share precisely $i$ edges, and the union of those $i$ common edges contains at least $ir-f(i)+1$ vertices.
For $\{\mathcal{Z},\mathcal{Z}'\}\in \mathscr{Z}_i$, it is clear that $|E(\mathcal{Z})\cup E(\mathcal{Z}')|=2e-i$ and $|V(\mathcal{Z})\cup V(\mathcal{Z}')|\le 2v-(ir-f(i)+1).$
Let $Z_i$ denote the size of $\mathscr{Z}_i$. Then
   \begin{equation}\label{Zi}
      \begin{aligned}
       {\rm{E}}[Z_i]=O(p^{2e-i}n^{2v-(ir-f(i)+1)})=O(n^{f(i)+\epsilon(2e-i)-\frac{(i-2)(er-v)}{e-1}-1}),
     \end{aligned}
   \end{equation}

\noindent where the first equality follows from the fact that there are at most $O(n^{2v-(ir-f(i)+1)})$ ways to choose $2e-i$ edges whose union contains at most $2v-(ir-f(i)+1)$ vertices.
Lastly, let $W$ denote the number of bad $e$-systems in $\mathcal{H}_0$. Then
   \begin{equation}\label{W}
     \begin{aligned}
       {\rm{E}}[W]=O(p^en^v)=O(n^{\frac{er-v}{e-1}+e\epsilon}).
     \end{aligned}
   \end{equation}

   In order to apply Lemma \ref{indset}, we will bound from above the number of pairs of bad $e$-systems which share at least two edges, by picking $\epsilon$ and $f(i)$ so that
   \begin{equation*}\label{con}
       {\rm{E}}[Y_i]=o({\rm{E}}[X])\text{\quad and\quad}{\rm{E}}[Z_i]=o({\rm{E}}[X])
   \end{equation*}

   for each $2\le i\le e-1$ as $n\rightarrow\infty$.
   From (\ref{X}), (\ref{Yi}) and (\ref{Zi}), it is easy to see that ${\rm{E}}[Y_i]=o({\rm{E}}[X])$ if and only if
   \begin{equation}\label{condition1}
     f(i)>\epsilon(i-1)+\frac{(i-1)(er-v)}{e-1},
   \end{equation}
   and ${\rm{E}}[Z_i]=o({\rm{E}}[X])$ if and only if
   \begin{equation}\label{condition2}
     f(i)<\frac{(i-1)(er-v)}{e-1}-\epsilon(2e-i-1)+1.
   \end{equation}
      Let $ a=\min_{2\le i\le e-1}\left\{\frac{1}{i-1}\big(f(i)-\frac{(i-1)(er-v)}{e-1}\big),~\frac{1}{2e-i-1}\big(\frac{(i-1)(er-v)}{e-1}+1-f(i)\big)\right\}.$
   There is $\epsilon\in(0,a)$
   satisfying
  (\ref{condition1}) and (\ref{condition2}) if and only if for each $2\le i\le e-1$, there exists an integer $f(i)$ such that
 \begin{equation} \label{f(i)}
   \begin{aligned}
     \frac{(i-1)(er-v)}{e-1}<f(i)<\frac{(i-1)(er-v)}{e-1}+1.
   \end{aligned}
   \end{equation}
   Since $f(i)$ is an integer, (\ref{f(i)}) holds if and only if $e-1\nmid(i-1)(er-v).$

   It is easy to verify that those $e-2$ indivisibility conditions hold simultaneously if and only if $\gcd(e-1,er-v)=1.$
   Under this condition, it suffices to pick for each $2\le i\le e-1$,
   $$f(i)=\lceil \frac{(i-1)(er-v)}{e-1}\rceil$$ and an arbitrary $\epsilon\in(0,a)$
   (note that by the choices of $f(i)$ we have $a>0$).

   Applying Chernoff's inequality for $X$ and Markov's inequality for $Y_i,Z_i$ and $W$, it is easy to see that for each $2\le i\le e-1$ and sufficiently large $n$,
   $$\Pr[X<0.9{\rm{E}}[x]]<\frac{1}{2e},~\Pr[Y_i>2e{\rm{E}}[Y_i]]<\frac{1}{2e},~\Pr[Z_i>2e{\rm{E}}[Z_i]]<\frac{1}{2e},~\Pr[W>2e{\rm{E}}[W]]<\frac{1}{2e}.$$
   Therefore, with positive probability, there exists an $r$-graph $\mathcal{H}_0\subseteq\binom{[n]}{r}$ such that for each $2\le i\le e-1$,
   \begin{equation}\label{eq-new}
     X\ge 0.9 {\rm{E}}[X], ~Y_i\le 2e{\rm{E}}[Y_i],~Z_i\le 2e{\rm{E}}[Z_i],~W\le 2e{\rm{E}}[W].
   \end{equation}

   Fix such an $\mathcal{H}_0$. We construct a subhypergraph $\mathcal{H}_1$ of $\mathcal{H}_0$ as follows. For every $2\le i\le e-1$, remove from $\mathcal{H}_0$ one edge from each member of $\mathscr{Y}_i$, and one edge from $E(\mathcal{Z})\cup E(\mathcal{Z}')$ for each pair $\{\mathcal{Z},\mathcal{Z}'\}\in\mathscr{Z}_i$. It is not hard to check that $\mathcal{H}_1$ satisfies the following properties:

   \begin{itemize}
     \item [(i)] $|\mathcal{H}_1|=\Omega(n^{\frac{er-v}{e-1}+\epsilon})$;

     \item [(ii)] the number of bad $e$-systems contained in $\mathcal{H}_1$ is at most $O(p^en^v)=O(n^{\frac{er-v}{e-1}+e\epsilon})$;

     \item [(iii)] for each $2\le i\le e-1$, the union of any $i$ distinct edges in $\mathcal{H}_1$ contains more than $ir-f(i)$ vertices;
     \item [(iv)] any two bad $e$-systems in $\mathcal{H}_1$ can share at most one edge.
   \end{itemize}

Indeed, (i) is an easy consequence of the following calculation:
\begin{equation*}
  |\mathcal{H}_1|\ge|\mathcal{H}_0|-\sum_{i=2}^{e-1}|\mathscr{Y}_i|-\sum_{i=2}^{e-1}|\mathscr{Z}_i|\ge 0.9{\rm{E}}[X]-o({\rm{E}}[X])=\Omega({\rm{E}}[X]);
\end{equation*}
\noindent (ii) follows from \eqref{X}, (\ref{W}) and the observation that removing edges from $\mathcal{H}_0$ does not increase the number of bad $e$-systems; (iii) holds since according to our construction, $\mathcal{H}_1$ does not contain any member of $\mathscr{Y}_i$ for any $2\le i\le e-1$.
It remains to verify (iv).
Assume to the contrary that $\mathcal{H}_1$ still contains two bad $e$-systems that share $i$ edges for some $2\le i\le e-1$.
On one hand, if those $i$ edges are spanned by at least $ir-f(i)+1$ vertices, then the pair of such two bad $e$-systems must belong to $\mathscr{Z}_i$, which is a contradiction.
On the other hand, if those $i$ edges are spanned by at most $ir-f(i)$ vertices, then they must form a member of $\mathscr{Y}_i$, which is again a contradiction.

Next we construct an auxiliary $e$-graph $\mathcal{U}\subseteq\binom{E(\mathcal{H}_1)}{e}$ as follows:
   \begin{itemize}
     \item  the vertex set of $\mathcal{U}$ is formed by the edge set of $\mathcal{H}_1$;
     \item  $e$ vertices of $\mathcal{U}$ form an edge if and only if the corresponding $e$ $r$-edges in $\mathcal{H}_1$ form a bad $e$-system.
        \end{itemize}

     \noindent It is routine to check that the following hold:
     \begin{itemize}
       \item   $\mathcal{U}$ is linear (by (iv));
       \item  $\mathcal{U}$ has at least $\Omega(n^{\frac{er-v}{e-1}+\epsilon})$ vertices (by (i)) and at most $O(p^en^v)=O(n^{\frac{er-v}{e-1}+e\epsilon})$ edges (by (ii));
       \item  $d(\mathcal{U})$, the average degree of $\mathcal{U}$, is at most
       $d(\mathcal{U})=O(\frac{e\cdot |E(\mathcal{U})|}{|V(\mathcal{U})|})=O(n^{(e-1)\epsilon}).$
     \end{itemize}

     \noindent Lemma \ref{indset} therefore applies and $\mathcal{U}$ has an independent set of size at least
     \begin{equation*}\label{independent}
       \Omega\big(|V(\mathcal{U}|\cdot(\frac{\log d(\mathcal{U})}{d(\mathcal{U})})^{\frac{1}{e-1}}\big)=\Omega(n^{\frac{er-v}{e-1}}(\log n)^{\frac{1}{e-1}}).
     \end{equation*}

     Now the theorem follows from the following simple observation:
     every independent set $\mathcal{I}\subseteq V(\mathcal{U})$ corresponds to a $\mathscr{G}_r(v,e)$-free subhypergraph $\mathcal{H}_{\mathcal{I}}\subseteq\mathcal{H}_1$ with $|\mathcal{I}|$ edges; moreover, by (iii)
     $\mathcal{H}_{\mathcal{I}}$ is also $\mathscr{G}_r(ir-f(i),i)$-free for each $2\le i\le e-1$.
\end{proof}

The proof of Theorem \ref{sparseturannumber1} leads to the following proposition.

\begin{proposition}
    Let $s\ge 1, r\ge 3$ and $(v_i,e_i),1\le i\le s$ be fixed integers satisfying $v_i\ge r+1,e_i\ge 2$. Suppose further that $e_1\ge 3, \gcd(e_1-1,e_1r-v_1)=1$ and $\frac{e_1r-v_1}{e_1-1}<\frac{e_ir-v_i}{e_i-1}$ for $2\le i\le s$.

    Then there exists an $r$-graph with $\Omega(n^{\frac{e_1r-v_1}{e_1-1}}(\log n)^{\frac{1}{e_1-1}})$ edges which is $\mathscr{G}_r(v_i,e_i)$-free for each $1\le i\le s$.
\end{proposition}

\begin{proof}[Sketch of the proof]
With the notation of the previous proof, we generate an $r$-graph $\mathcal{H}_0\subseteq\binom{[n]}{r}$ by picking each element of $\binom{[n]}{r}$ independently with probability $p:=\Theta(n^{-\frac{v_1-r}{e_1-1}+\epsilon})$ for some small constant $\epsilon>0$. For $2\le i\le e$, let $X,Y_i,Z_i,W,f(i)$ and $a\in(0,1)$ be defined analogously to the proof of Theorem \ref{sparseturannumber1} but with respect to $v_1$ and $e_1$. Hence, the expected number of edges in $\mathcal{H}_0$ is ${\rm{E}}[X]=\Theta(n^{\frac{e_1r-v_1}{e_1-1}+\epsilon})$.
Moreover, for $2\le j\le s$, the expected number of bad $e_j$-systems contained in $\mathcal{H}_0$ is ${\rm{E}}[W_j]=\Theta(n^{v_j-\frac{e_j(v_1-r)}{e_1-1}+e_j\epsilon})$.

By assumption, it is clear that $\frac{v_j-r}{e_j-1}<\frac{v_1-r}{e_1-1}$ for each $2\le j\le s$. Let $b=\min_{2\le j\le s}~\{\frac{v_1-r}{e_1-1}-\frac{v_j-r}{e_j-1}\}$. Then for any $\epsilon\in(0,b)$ and $2\le j\le s$,
 \begin{equation*}
     (\frac{e_1r-v_1}{e_1-1}+\epsilon)-(v_j-\frac{e_j(v_1-r)}{e_1-1}+e_j\epsilon)=(e_j-1)(\frac{v_1-r}{e_1-1}-
     \frac{v_j-r}{e_j-1}-\epsilon)>0.
 \end{equation*}

 \noindent Choosing an arbitrary $\epsilon\in(0,\min\{a,b\})$, it is easy to check that for any $2\le i\le e$ and $2\le j\le s$,
 $${\rm{E}}[Y_i]=o({\rm{E}}[X]),~\quad{\rm{E}}[Z_i]=o({\rm{E}}[X])\text{\quad and\quad}{\rm{E}}[W_j]=o({\rm{E}}[X]).$$

 \noindent Similar to the previous proof, by applying Chernoff's inequality for $X$ and Markov's inequality for $Y_i,Z_i,W$ and $W_j$, one can show that with positive probability there exists an $r$-graph $\mathcal{H}_0\subseteq\binom{[n]}{r}$ such that
   \begin{equation*}
     X=\Omega({\rm{E}}[X]),~W=O({\rm{E}}[W]),~\Gamma=o({\rm{E}}[X])\text{~for every $\Gamma\in\{Y_i,Z_i,W_j:2\le i\le e,2\le j\le s\}$}.
   \end{equation*}

The rest of the proof follows fairly straightforwardly from the argument of the previous proof, hence is omitted.
\end{proof}

\section{Applications to two extremal problems}\label{application-1}

\noindent The probabilistic construction of Theorem \ref{sparseturannumber1} immediately implies new lower bounds for two hypergraph extremal problems, as stated below.

\subsection{$\mathscr{H}_r(q,e)$-free $r$-graphs}

\noindent Bujt\'{a}s and Tuza \cite{BujtasTuzaCBC} studied the following extremal problem which is related to the construction of uniform Combinatorial Batch Codes (see Subsection \ref{application-CBC} below).
An $r$-graph is said to be {\it $\mathscr{H}_r(q,e)$-free} if it is simultaneously $\mathscr{G}_r(i-q-1,i)$-free for every $1\le i\le e$.
In \cite{BujtasTuzaCBC} it was shown that for fixed integers $r\ge 3, e> q+r\ge 3$, $${\rm{ex}}_r(n,\mathscr{H}_r(q,e))=\Omega(n^{r-1+\frac{r+q}{e-1}}).$$

The following proposition is a direct consequence of Theorem \ref{sparseturannumber1}.

\begin{proposition} \label{universeconsequence1}
  For fixed integers $r\ge 3, e> q+r\ge 3$ with $\gcd(e-1,r+q)=1$,
  $${\rm{ex}}_r(n,\mathscr{H}_r(q,e))=\Omega(n^{r-1+\frac{r+q}{e-1}}(\log n)^{\frac{1}{e-1}})$$ as $n\rightarrow\infty$.
\end{proposition}

\begin{proof
  Apply Theorem \ref{sparseturannumber1} with $v=e-q-1$.
  Since for every $1\le i\le e$,
  \begin{equation*}
    \begin{aligned}
      &ir-\lceil\frac{(i-1)(er-e+q+1)}{e-1}\rceil=ir-(i-1)(r-1)-\lceil\frac{(i-1)(r+q)}{e-1}\rceil\ge i-q-1,\\

    \end{aligned}
  \end{equation*}
so there exists an $r$-graph with $\Omega(n^{\frac{er-e+q+1}{e-1}}(\log n)^{\frac{1}{e-1}})$ edges, which is  $\mathscr{G}_r(i-q-1,i)$-free for every $1\le i\le e$, as needed.
\end{proof}

\subsection{$r$-graphs with no short Berge cycles}

\noindent For integers $t\ge 3,r\ge 3$, a {\it Berge $t$-cycle} in an $r$-graph is a set of $t$ distinct vertices $v_1,\ldots,v_t$ associated with $t$ distinct\footnote{In the literature, some authors (see, e.g. \cite{Lazebnikgirth5}) require the edges in a Berge cycle to be distinct, while others (see, e.g. \cite{Jacquesbergesurvey}) do not. However, it is easy to show that if there are at least two distinct edges in the cycle, then a Berge cycle {\it without} distinctness contains a Berge cycle {\it with} distinctness. Since in this paper we only consider the length of a shortest Berge cycle, the definition with distinctness is more suitable for us.}
edges $A_1,\ldots,A_t$ such that $\{v_{i-1},v_i\}\subseteq A_i$ for $2\le i\le t$ and $\{v_1,v_t\}\subseteq A_1$.
An $r$-graph is said to be {\it $\mathscr{B}_t$-free} if it contains no Berge cycles of length at most $t$.
For $t=3$, the results of \cite{Ruzsa-Szemeredi,EPR} implied that for any $r\ge3$, $n^{2-o(1)}<{\rm{ex}}_r(n,\mathscr{B}_3)=o(n^2).$
For $t=4$, it was shown in \cite{Lazebnikgirth5} that for $r=3$, ${\rm{ex}}_3(n,\mathscr{B}_4)=\Theta(n^{\frac{3}{2}})$,
and in \cite{TimmonsGirth4} that for any $r\ge 4$, ${\rm{ex}}_r(n,\mathscr{B}_4)>n^{\frac{3}{2}-o(1)}.$
Recently, Xing and Yuan \cite{LRC} used $\mathscr{B}_t$-free $r$-graphs to construct optimal Locally Recoverable
Codes (see Subsection \ref{application-LRC} below) and they showed that (using the alteration method) for any $r\ge 3$ and $t\ge 5$,
$${\rm{ex}}_r(n,\mathscr{B}_t)=\Omega(n^{\frac{t}{t-1}}).$$
It is not hard to verify (see, e.g. Theorem 5.1 in \cite{LRC}) that an $r$-graph $\mathcal{H}$ is $\mathscr{B}_t$-free if and only if it is simultaneously $\mathscr{G}_r(ir-i,i)$-free for every $1\le i\le t$. Thus applying Theorem \ref{sparseturannumber1} with $v=tr-t$ and $e=t$ leads to the following result.

\begin{proposition}\label{universeconsequence2}
  For fixed integers $r\ge 3,t\ge 5$,
  $${\rm{ex}}_r(n,\mathscr{B}_t)=\Omega(n^{\frac{t}{t-1}}(\log n)^{\frac{1}{t-1}})$$
  as $n\rightarrow\infty$; or equivalently, there exists an $r$-graph with such number of edges, which is simultaneously $\mathscr{G}_r(ir-i,i)$-free for every $1\le i\le t$.
\end{proposition}

We remark that in \cite{LRC} the authors stated that in a private communication, Jacques Verstra\"ete suggested that a lower bound on ${\rm{ex}}_r(n,\mathscr{B}_t)$, which is exactly the same with Proposition \ref{universeconsequence2}, can also be proved by using the method of \cite{BohmanKeevashr=2,BohmanKeevashr=3} (which is rather involved).
Nevertheless, since \cite{LRC} stated this result (as well as Proposition \ref{xing-yuan} below) without a proof, we present it here as an easy consequence of Theorem \ref{sparseturannumber1}.

\section{Applications to coding theory}\label{application-2}

\noindent In this section we present three applications of Theorem \ref{sparseturannumber1} to coding theory.
\subsection{Parent-Identifying Set Systems}

\noindent
An $r$-graph $\mathcal{H}\subseteq\binom{[n]}{r}$ is said to be a {\it $t$-Parent-Identifying Set System} ($t$-IPPS for short),
denoted as $t$-${\rm{IPPS}}(r,|\mathcal{H}|,n)$, if for any $r$-subset $X\subseteq[n]$ which is contained in the union of at most $t$ edges of $\mathcal{H}$, it holds that
$$\cap_{\mathcal{P}\in P_t(X)}\mathcal{P}\neq\emptyset,$$ where $P_t(X)=\{\mathcal{P}\subseteq\mathcal{H}:|\mathcal{P}|\le t,~X\subseteq\cup_{A\in\mathcal{P}}A\}$.

IPPSs were introduced by Collins \cite{Collins09} as a technique to trace traitors in a secret sharing scheme.
Generally speaking, an {\it $(n,r)$-threshold secret sharing scheme}
has one {\it message} and $n$ {\it keys}
such that any set of at least $r$ keys can be used to decrypt this message but no set of fewer than $r$ keys can. Let $\mathcal{H}$ be a $t$-${\rm{IPPS}}(r,m,n)$ whose $n$ vertices and $m$ edges are indexed by the $n$ keys and the $m$ users, respectively.
Assume that there is a {\it data supplier} distributes the keys to the users such that
for $1\le i\le m$, the $i$th user
gets
the $r$ keys
which form the $i$th edge of $\mathcal{H}$.
Suppose a coalition of at most $t$ illegal users may collude by combining some of their keys to produce a new, unauthorized set $T$ of $r$ keys to decrypt this message. Then, by definition of a $t$-IPPS, upon capturing an unauthorized set $T$,
the data supplier is able to identify at least one illegal user who contributed to $T$.

For a $t$-${\rm{IPPS}}(r,m,n)$ with given $t,r$ and $n$, it was shown
by Gu and Miao \cite{Gu2018} that $$m=O(n^{\lceil\frac{r}{\lfloor t^2/4\rfloor+t}\rceil}).$$
Recently, Gu, Cheng, Kabatiansky and Miao \cite{Gu} showed that for fixed integers $t\ge 2,r\ge 3$, there exists a $t$-${\rm{IPPS}}(r,m,n)$ with
$$m=\Omega(n^{\frac{r}{\lfloor t^2/4\rfloor+t}}),$$
which implies that for $\lfloor t^2/4\rfloor+t\mid r$ the
upper bound in \cite{Gu2018} is tight up to a constant factor.
We slightly improve the lower bound of \cite{Gu} for some pairs of $r,t$.

\begin{proposition}\label{ipps}
  For fixed integers $t\ge 2,r\ge 3$ satisfying $\gcd(\lfloor t^2/4\rfloor+t,r)=1$, there exists a $t$-${\rm{IPPS}}(r,m,n)$ with
  $$m=\Omega(n^{\frac{r}{\lfloor t^2/4\rfloor+t}}(\log n)^{\frac{1}{\lfloor t^2/4\rfloor+t}})$$ as $n\rightarrow\infty$.
\end{proposition}

Proposition \ref{ipps} is proved by establishing a connection between IPPSs and sparse hypergraphs, as stated below.
Note that a similar observation with different phrasing was obtained independently in \cite{Gu}.

\begin{lemma}\label{link}
  Assume that $\mathcal{H}\subseteq\binom{[n]}{r}$ is a $\mathscr{G}_r(er-r,e)$-free $r$-graph with $e=\lfloor(t/2+1)^2\rfloor$. Then it is also
  a $t$-${\rm{IPPS}}(r,|\mathcal{H}|,n)$.
\end{lemma}

\begin{proof
\noindent  Assume towards contradiction that $\mathcal{H}$ is not a $t$-${\rm{IPPS}}(r,|\mathcal{H}|,n)$. Thus
  by definition there exists an $r$-subset $X\subseteq[n]$, which can be covered by at most $t$ edges of $\mathcal{H}$, such that $\cap_{\mathcal{P}\in P_t(X)}\mathcal{P}=\emptyset$.
  Let $m$ be the minimal positive integer such that there exist $\mathcal{P}_1,\ldots,\mathcal{P}_m\in\mathcal{P}_t(X)$ with $\cap_{i=1}^m \mathcal{P}_i=\emptyset$.
  By the minimality of $m$, it holds that for each $i\in[m]$, $$\cap_{j\in[m]\setminus\{i\}} \mathcal{P}_j\neq\emptyset.$$
  Without loss of generality, assume $A_i\in\cap_{j\in[m]\setminus\{i\}} \mathcal{P}_j$.
  Clearly, $A_i\not\in\mathcal{P}_i$ and moreover, for $1\le i\neq i'\le m$, $A_i\neq A_{i'}$.
  Let $\mathcal{A}:=\{A_1,\ldots,A_m\}$, then
  \begin{equation*}
    \begin{aligned}
      |\cup_{i=1}^m\mathcal{P}_i|=&|\mathcal{A}|+|\cup_{i=1}^m(\mathcal{P}_i\setminus\mathcal{A})|\\
      \le&m+\sum_{i=1}^m|\mathcal{P}_i\setminus\mathcal{A}|\\
      \le&m+m(t-m+1)\\
      \le&\lfloor(t/2+1)^2\rfloor,\\
    \end{aligned}
  \end{equation*}
  where the second inequality follows since    $|\mathcal{P}_i|\le t$ and $|\mathcal{P}_i\cap\mathcal{A}|=m-1$ for any $i\in[m]$.

  Let $\mathcal{B}:=\cup_{i=1}^m\mathcal{P}_i$. We claim that for each $x\in X$ there exist at least two distinct sets $B_i,B_j\in\mathcal{B}$ that contain it.
  Assume the opposite, then there exist $x\in X$ and $B\in\mathcal{B}$, such that $x$ belongs solely to $B$ but to no other set in $\mathcal{B}$; that is,
  $x\in B$ and $x\not\in\cup_{B'\in\mathcal{B}\setminus\{B\}}B'$.  This implies that  $B \in\mathcal{P}_i$ for any $i$, and  $\cap_{i=1}^m\mathcal{P}_i\neq \emptyset$, a contradiction.

Add to $\mathcal{B}$ arbitrary $\lfloor(t/2+1)^2\rfloor-|\mathcal{B}|\geq 0$ edges of $\mathcal{H}\setminus\mathcal{B}$. It is clear now that $\mathcal{B}$ contains exactly $\lfloor(t/2+1)^2\rfloor$ edges of $\mathcal{H}$ and

    \begin{equation*}
    \begin{aligned}
      |\cup_{B\in\mathcal{B}}B|\leq \lfloor(t/2+1)^2\rfloor r -r,
    \end{aligned}
  \end{equation*}
  where the inequality follows since each element of $X$ appears in at least two edges of $\mathcal{B}$.
	This violates the $\mathscr{G}_r(er-r,e)$-freeness of $\mathcal{H}$ for $e=\lfloor(t/2+1)^2\rfloor$, and the result follows.
\end{proof}

\begin{proof}[\textbf{Proof of Proposition \ref{ipps}}]

  Apply Lemma \ref{link} and Theorem \ref{sparseturannumber1} with $v=er-r$ and $e=\lfloor(t/2+1)^2\rfloor$.
\end{proof}

\subsection{Uniform Combinatorial Batch Codes}\label{application-CBC}

\noindent
An {\it $r$-uniform CBC} with parameters $m,e,n$, denoted as $r{\text{-}}(m,e,n)$-CBC, is an $r$-uniform {\it multihypergraph} (i.e., hypergraphs allowing repeated edges) $\mathcal{H}$ with $n$ vertices and $m$ edges, such that for every $1\le i\le e$, the union of any $i$ distinct edges contains at least $i$ vertices.
For integers $e>r\ge 3$, let $m(n,r,e)$ denote the maximum $m$ such that an $r{\text{-}}(m,e,n)$-CBC exists.

Uniform-CBCs can be applied to
the following scenario in a distributed database system, as illustrated by Balachandran and Bhattacharya \cite{batch1}. Assume that there are $m$
{\it data items} which are stored in $n$ {\it servers} and any data item is replicated across $r$
servers so that any $e$ of the $m$ data items can be retrieved by accessing $e$ servers and reading  exactly one data item from each.
Let $\mathcal{H}\subseteq\binom{[n]}{r}$ be an $r$-uniform multihypergraph whose $n$ vertices and $m$ edges are indexed by the servers and the data items, respectively. An {\it $\mathcal{H}$-based replication system} stores $m$ data items among $n$ servers as follows:
for $1\le i\le m$, the $i$th data item is stored in the $r$ servers which form the $i$th edge of $\mathcal{H}$\footnote{Since two distinct data items may be stored in the same set of $r$ servers, $\mathcal{H}$ is
allowed to have repeated edges.}.

Given an $\mathcal{H}$-based replication system,
the required retrieval condition on the servers and the data items can be expressed in a purely combinatorial way: every collection of at most $e$ distinct edges of $\mathcal{H}$ has a {\it system of distinct representatives} (SDR for short) from the $n$ vertices, where for any $e$ edges $\mathcal{A}=\{A_1,\ldots,A_e\}\subseteq\mathcal{H}$, an SDR of $\mathcal{A}$ is a set of $e$ {\it distinct} elements $\{x_1,\ldots,x_e\}\subseteq[n]$ such that $x_i\in A_i$ for each $1\le i\le e$.
Applying Hall's theorem \cite{hall1935representatives} one can infer that this holds if and only if $\mathcal{H}$ is $\mathscr{G}_r(i-1,i)$-free for every $1\le i\le e$.

Recall that an $r$-graph is said to be $\mathscr{H}_r(q,e)$-free if it is simultaneously $\mathscr{G}_r(i-q-1,i)$-free for every $1\le i\le e$.
Clearly, an $r{\text{-}}(m,e,n)$-CBC is equivalent to an $\mathscr{H}_r(0,e)$-free $r$-uniform multihypergraph with $n$ vertices and $m$ edges; consequently,

\begin{equation*}\label{batch}
  \begin{aligned}
    m(n,r,e)\ge {\rm{ex}}_r(n,\mathscr{H}_r(0,e)).
  \end{aligned}
\end{equation*}

\noindent For fixed integers $e> r\ge 3$, it was shown in \cite{paterson2009} that
$$m(n,r,e)=\Omega(n^{r-1+\frac{r}{e-1}}).$$

An easy application of Proposition \ref{universeconsequence1} suggests the following result.

\begin{proposition}\label{cbc}
For fixed integers $e> r\ge 3$ satisfying $\gcd(e-1,r)=1$,
  $$m(n,r,e)\ge {\rm{ex}}_r(n,\mathscr{H}_r(0,e))=\Omega(n^{r-1+\frac{r}{e-1}}(\log n)^{\frac{1}{e-1}})$$ as $n\rightarrow\infty$.
\end{proposition}

\subsection{Optimal Locally Recoverable Codes}\label{application-LRC}
\noindent
A {\it linear code} $\mathcal{C}$ of length $n$ defined on the finite field $\mathbb{F}_q$ is a subspace of  $\mathbb{F}_q^n$. The {\it minimum distance} of $\mathcal{C}$ is defined as $d(\mathcal{C}):=\min\{{\rm{wt}}(\pmb{x}):\pmb{x}\in\mathcal{C}\setminus\{\pmb{0}\}\}$, where ${\rm{wt}}(\pmb{x})$ is the number of nonzero coordinates of $\pmb{x}$. A {\it parity check matrix} of $\mathcal{C}$ is an $(n-k)\times n$ matrix $H$ such that $\pmb{x}\in\mathcal{C}$ if only if $H\cdot \pmb{x}^T=\pmb{0}.$

A linear code $\mathcal{C}\subseteq\mathbb{F}_q^n$ of dimension $k$ is called {\it Locally Recoverable Code} (or LRC for short) with {\it locality} $r$ if for any $i\in[n]$ there exists  $r$ other coordinates $i_1,...,i_r$ such that for any codeword $\pmb{x}=(x_1,\ldots,x_n)\in\mathcal{C}$,  $x_i$ can be recovered from   $x_{i_1},\ldots,x_{i_r}$.
We denote such a code by $(n,k,r)$-LRC. In \cite{LocalSingleton} it was shown that the minimum distance $d$ of an $(n,k,r)$-LRC satisfies $d\le n-k-\lceil\frac{k}{r}\rceil+2,$ and the code is called {\it optimal} if the bound is achieved with equality.

In order to reduce the complexity of the operations in the  finite field, it is desirable to define the LRCs over small enough fields. In other words, given the size of the underlying field, our goal is to construct the longest possible optimal-LRC.

Assume that $r+1\mid n$. Set $m:=\frac{n}{r+1}$ and let $I_m$  and $\textbf{1}$ be the identity matrix of order $m$, and the all $1$ row vector of length $r+1$, respectively. It is not hard to verify that a linear code $ \mathcal{C}$ with   parity check matrix of the form
\begin{equation}
\label{eq:8}
H=\left(\begin{matrix}
I_m\otimes \textbf{1}\\
A\\
\end{matrix}\right),
\end{equation}
\noindent where $ \otimes$ is the Kronecker product and $A$ is an $(n-k-m)\times n$ matrix, has locality $r$. Indeed, any symbol $x_i,i\in [n]$ of a codeoword $\pmb{x}\in\mathcal{C}$  can be recovered by $r$ other symbols since it satisfies a linear equation which has exactly  $r+1$ variables.

Xing and Yuan \cite{LRC} gave a construction of an optimal LRC for $r\ge d-2$ by carefully constructing the matrix $A$ in \eqref{eq:8}, as follows.
For a subset $A=\{\alpha_1,...,\alpha_{r+1}\}\subseteq \mathbb{F}_q$, let $V(A)$ be the $(d-2)\times (r+1)$ Vandermonde matrix with $\alpha_j^i$ as its $(i,j)$-entry.
The following result  was proved in \cite{LRC}.
\begin{lemma}[see Theorem 3.1, \cite{LRC}]\label{LRCsparse}
Let  $d\ge 11$ and $r\ge d-2$, and  let $\mathcal{C}\subseteq\mathbb{F}_q^n$ be a linear code with parity check matrix
\begin{equation*}
H=\left(\begin{matrix}
I_m\otimes \textbf{1}\\
V(A_1),...,V(A_m)\\
\end{matrix}\right),
\end{equation*}

 then $\mathcal{C}$ is an optimal $(n,k,r)$-LRC with minimum distance $d$ if and only if the family $\mathcal{A}:=\{A_1,\ldots,A_m\}\subseteq\binom{\mathbb{F}_q}{r+1}$ is $\mathscr{G}_{r+1}(ir,i)$-free for each $1\le i\le \lfloor\frac{d-1}{2}\rfloor$.
\end{lemma}
The following result (which is stated in \cite{LRC} without a  proof) follows by combining Lemma \ref{LRCsparse} and Proposition \ref{universeconsequence2}.

\begin{proposition}[see also Theorem 1.1, \cite{LRC}]\label{xing-yuan}
  Suppose that $d\ge 11$, $r\ge d-2$ and $r+1\mid n$, then there exists an optimal $(n,k,r)$-LRC over $\mathbb{F}_q$ with minimum distance $d$ and length $n=\Omega\big(q(q\log q )^{\frac{1}{\lfloor(d-3)/2\rfloor}}\big).$
\end{proposition}

\section*{Acknowledgements}

\noindent The research of Chong Shangguan and Itzhak Tamo was supported by ISF grant No. 1030/15 and NSF-BSF grant No. 2015814.
The authors would like to thank Prof. Yiwei Zhang for valuable comments on the first version of this manuscript.
They are also grateful to Yujie Gu for helpful discussions on Parent-Identifying Set Systems. Lastly, the authors want to express their gratitude to the two anonymous reviewers for their comments which are very helpful to the improvement of this paper.

{\small
\bibliographystyle{plain}


\section{Introduction}

Given a projective variety $X$ of dimension $n$ which is not rational, one can try to quantify how far it is from being rational. When $n = 1$, the natural invariant is the \textit{gonality} of a curve $C$, defined to be the smallest degree of a branched covering $C' \rightarrow \P^{1}$ (where $C'$ is the normalization of $C$). One generalization of gonality to higher dimensions is the \textit{degree of irrationality}, defined as:
\[ \irr(X) = \min \{ \delta > 0 \mid \exists \text{ a degree $\delta$ rational dominant map } X \dashrightarrow \P^{n} \}. \]
Recently, there has been significant progress in understanding the case of hypersurfaces of large degree (cf. \cite{Bastianelli17}, \cite{BCD14}, \cite{BDELU17}). The history behind the development of these ideas is described in \cite{BDELU17}. The results of \cite{Bastianelli17}, \cite{BCD14}, \cite{BDELU17} depend on the positivity of the canonical bundles of the varieties in question, so it is interesting to consider what happens in the $K_{X}$-trivial case. Our purpose here is to prove the somewhat surprising fact that the degree of irrationality of a very general polarized abelian surface is uniformly bounded above, independently of the degree of the polarization.

To be precise, let $A = A_{d}$ be an abelian surface carrying a polarization $L = L_{d}$ of type $(1, d)$ and assume that $\NS(A) = \mathbb{Z}[L]$. An argument of Stapleton \cite{Stapleton17} showed that there is a constant $C$ such that
\[ \irr(A) \leq C \cdot \sqrt{d} \]
for $d \gg 0$, and it was conjectured in \cite{BDELU17} that equality holds asymptotically. Our main result shows that this is maximally false:

\begin{thm}\label{thm:MT}
For an abelian surface $A = A_{d}$ with Picard number $\rho = 1$, one has
\[ \irr(A) \leq 4. \]
\end{thm}

We conjecture that in general equality holds. However, as far as we can see, the conjecture of \cite{BDELU17} for polarized K3 surfaces $(S_{d}, B_{d})$ of genus $d$ - namely, that there exist constants $C_{1}, C_{2}$ such that $C_{1} \cdot \sqrt{d} \leq \irr(S_{d}) \leq C_{2} \cdot \sqrt{d}$ for $d \gg 0$ - remains plausable.\footnote{In other words, $B_{d}$ is an ample line bundle on $S_{d}$ with $B_{d}^{2} = 2d - 2$.}

For an abelian variety $A$ of dimension $n$, it has been shown in \cite{AP92} that $\irr(A) \geq n+1$ (for $n = 2$, one can also see this via Lemma~\ref{lem:NMT}). When $n = 2$, Yoshihara proved that $\irr(A) = 3$ for abelian surfaces $A$ containing a smooth curve of genus 3 (cf. \cite{Yoshihara96}). On a related note, Voisin \cite{Voisin18} showed that the covering gonality of a very general abelian variety $A$ of dimension $n$ is bounded from below by $f(n)$, where $f(n)$ grows like $\log(n)$, and this lower bound was subsequently improved to $\lceil \frac{1}{2} n + 1 \rceil$ by Martin \cite{Martin19}.\footnote{Covering gonality is defined as the minimum integer $c>0$ such that given a general point $x \in A$, there exists a curve $C$ passing through $x$ with gonality $c$.}

In the proof of our theorem, assuming as we may that $L$ is symmetric, we consider the space $H^{0}(A, \O_{A}(2L))^{+}$ of even sections of $\O_{A}(2L)$. By imposing suitable multiplicities at the two-torsion points of $A$, we construct a subspace $V \subset H^{0}(A, \O_{A}(2L))^{+}$ which numerically should define a rational map from $A$ to a surface $S \subset \P^{N}$. Using bounds on the degree of the map and the degree of $S$, as well as projection from linear subspaces, we construct a degree 4 rational covering $A \dashrightarrow \P^{2}$. The main difficulty is to deal with the possibility that $\P_{\text{sub}}(V)$ has a fixed component; this approach was inspired in part by the work of Bauer in \cite{Bauer94}, \cite{Bauer99}.

\textbf{Acknowledgments.} I would like to thank my advisor Robert Lazarsfeld for suggesting the conjecture and for his encouragement and guidance throughout the formulation of the results in this paper. I would also like to thank Frederik Benirschke, Mohamed El Alami, Fran\c{c}ois Greer, Samuel Grushevsky, Ljudmila Kamenova, Yoon-Joo Kim, Radu Laza, John Sheridan, and Ruijie Yang for engaging in valuable discussions.

\section{Set-up}\label{SU}

Let $A = A_{d}$ be an abelian surface with $\rho(A) = 1$. Assume $\NS(A) \cong \mathbb{Z} [L]$ where $L$ is a polarization of type $(1, d)$ for some fixed $d \geq 1$, so that $L^{2} = 2d$ and $h^{0}(L) = d$. Let
\[ \iota: A \rightarrow A, \quad x \mapsto -x \]
be the inverse morphism, and let $Z = \{ p_{1}, \ldots, p_{16} \}$ be the set of two-torsion points of $A$ (fixed points of $\iota$). We may assume that $L$ is symmetric -- that is, $\iota^{\ast}\O_{A}(L) \cong \O_{A}(L)$ -- by replacing $L$ with a suitable translate. In particular, the cyclic group of order two acts on $H^{0}(A, \O_{A}(2L))$. The space of \textit{even} sections $H^{0}(A, \O_{A}(2L))^{+}$ of the line bundle $\O_{A}(2L)$ (sections $s$ with the property that $\iota^{\ast} s = s$) has dimension
\[ h^{0}(A, 2L)^{+} = 2d + 2 \]
(see \cite[Corollary 4.6.6]{BL04}). An even section of $\O_{A}(2L)$ vanishes to even order at any two-torsion point, so we need to impose at most
\[ 1 + 3 + \cdots + (2m-1) = m^{2} \]
conditions for every even section to vanish to order $2m$ at \underline{any} fixed point $p \in Z$ (see \cite{Bauer94} for more details).

Fix any integer solutions $a_{1}, \ldots, a_{16} \geq 0$ to the equation
\[ \sum_{i=1}^{16} a_{i}^{2} = 2d-2, \]
with $a_{15} = 0 = a_{16}$.\footnote{This assumption will be useful in Corollary~\ref{cor:SQ}. For larger values of $d$, note that there are many solutions.} This is possible by Lagrange's four-squares theorem. Let $V \subset H^{0}(A, \O_{A}(2L))^{+}$ be the space of even sections vanishing to order at least $2a_{i}$ at each point $p_{i}$, such that
\[ \dim V \geq 2d + 2 - \sum_{i=1}^{16} a_{i}^{2} \geq 4. \]
Let $\d = \P_{\text{sub}}(V) \subseteq \abs{2L}^{+}$ be the corresponding linear system of divisors, whose dimension is $N \coloneqq \dim \d \geq 3$. Write
\[ d_{i} \coloneqq \mult_{p_{i}} D \]
for a general divisor $D \in \d$, so that $d_{i} \geq 2a_{i}$.

\begin{remark}\label{rem:K}
From \cite[Section 4.8]{BL04}, it follows that sections of $V$ are pulled back from the singular Kummer surface $A/\iota$, so any divisor $D \in \d$ is symmetric, i.e. $\iota(D) = D$.
\end{remark}

Let $\varphi: A \dashrightarrow \P^{N}$ be the rational map given by the linear system $\d$ above, and write $S \coloneqq \overline{\Im(\varphi)}$ for the image of $\varphi$. Regardless of whether or not $\d$ has a fixed component, we find that:

\begin{prop}\label{prop:S}
$S \subset \P^{N}$ is an irreducible and nondegenerate surface.
\end{prop}

\begin{proof}

Suppose for the sake of contradiction that $\overline{\Im(\varphi)}$ is a nondegenerate curve $C$. Then $\deg C \geq 3$ since $N \geq 3$, and a hyperplane section of $C \subset \P^{N}$ pulls back to a divisor with at least three irreducible components. This contradicts the fact that any divisor $D (\sim_{lin} 2L) \in \d$ has at most two irreducible components since $\NS(A) = \mathbb{Z}[L]$. So the image of $\varphi$ is a surface. \qedhere

\end{proof}

\begin{lem}\label{lem:S}
Let $\varphi: X \dashrightarrow \P^{n}$ be a rational map from a surface $X$ to a projective space of dimension $n \geq 2$, and suppose that its image $S \coloneqq \overline{\Im(\varphi)} \subset \P^{n}$ has dimension 2. Let $\d$ be the linear system corresponding to $\varphi$ (assuming $\d$ has no base components). Then for any $D \in \d$,
\[ \deg \varphi \cdot \deg S \leq D^{2}. \]
\end{lem}

\begin{proof}
The indeterminacy locus of $\varphi$ is a finite set. \qedhere
\end{proof}

\section{Degree bounds}

We now study the numerical properties of the linear series $\d$ constructed above. Keeping the notation as in $\S$\ref{SU}:

\begin{lem}\label{lem:NFC8}
If $\d$ has no fixed components, then
\[ \deg \varphi \cdot \deg S \leq 8. \]
\end{lem}

\begin{proof}
By applying Proposition~\ref{prop:S} and blowing-up $A$ along the collection of two-torsion points $Z$ to resolve some of the base points of $\d$, we arrive at the diagram
\begin{center}
\begin{tikzcd}
\hat{A} \arrow[r, phantom, "\coloneqq"] &[-0.25in] \Bl_{Z}A \arrow[d, swap, "\pi"] \arrow[dr, dashed, "\psi"] & &[-0.25in] \\
& A \arrow[r, swap, dashed, "\varphi"] & S \arrow[r, phantom, "\subset"] & \P^{N}
\end{tikzcd}
\end{center}
The linear system corresponding to $\psi$ has no fixed components, so its divisors are of the form
\[ \hat{D} \sim_{lin} \pi^{\ast}D - \sum_{i=1}^{16} d_{i} E_{i}, \]
where $\hat{D}$ denotes the strict transform of $D$. By Lemma~\ref{lem:S} applied to $\psi$,
\begin{equation}\label{eq:D}
\deg \varphi \cdot \deg S = \deg \psi \cdot \deg S \leq \hat{D}^{2} = 4L^{2} - \sum_{i=1}^{16} d_{i}^{2} \leq 4 \Bigg(2d - \sum_{i=1}^{16} a_{i}^{2} \Bigg) = 8. \qedhere
\end{equation}

\end{proof}

The main work is to treat the case when $\d$ has a fixed divisor $F \not= 0$. In this situation, we may write:
\[ D = F + M \in \d \quad \text{and} \quad \d = F + \b, \]
where $F$ and $M$ are the fixed and movable components of $\d$, respectively. By definition, $\dim \d = \dim \b$. Note that $D \sim_{lin} 2L$ implies $F, M \sim_{alg} L$ for all $M \in \b$. Choose a general divisor $M \in \b$ and write
\[ m_{i} \coloneqq \mult_{p_{i}}M \quad \text{and} \quad f_{i} \coloneqq \mult_{p_{i}}F, \]
so that $d_{i} = m_{i} + f_{i} \geq 2a_{i}$ for all $i$. We claim that $F$ must be symmetric as a divisor. If not, then
\[ \iota(M) + \iota(F) = \iota(D) = D = M + F \quad \text{for all} \quad D \in \d. \]
This implies that $M = \iota(F)$ and $F = \iota(M)$ for all $M \in \b$, which would mean that $M$ must also be fixed, leading to a contradiction. Hence, $F$ must be symmetric, and likewise for all $M \in \b$.

We first need an intermediate estimate:

\begin{prop}\label{prop:E}
Assume $\d$ has a fixed component $F \not= 0$. Keeping the notation as above,
\[ \sum_{i=1}^{16} m_{i}^{2} \geq 2d - 8. \]
\end{prop}

\begin{proof}

The idea here is to use the Kummer construction to push our fixed curve $F$ onto a K3 surface and apply Riemann-Roch. This is analagous to a proof of Bauer's in \cite[Theorem 6.1]{Bauer99}. Consider the smooth Kummer K3 surface $K$ associated to $A$:
\begin{center}
\begin{tikzcd}
E \arrow[r, phantom, "\subset"] &[-0.3in] \hat{A} \arrow[d, swap, "\pi"] \arrow[r, "\gamma"] & \hat{A}/\{ 1, \sigma \} \arrow[r, phantom, "\eqqcolon"] &[-0.3in] K \\
Z \arrow[r, phantom, "\subset"] & A & &
\end{tikzcd}
\end{center}
where $\pi$ is the blow-up of $A$ along the collection of two-torsion points $Z$. Since the points in $Z$ are $\iota$-invariant, $\iota$ lifts to an involution $\sigma$ on $\hat{A}$ and the quotient $K$ is a smooth K3 surface. Let $E_{i}$ denote the exceptional curve over $p_{i} \in Z$, so that $E = \sum_{i=1}^{16}E_{i}$ is the exceptional divisor of $\pi$. Since $F$ is symmetric, its strict transform
\[ \hat{F} = \pi^{\ast}F - \sum_{i=1}^{16} f_{i} E_{i}, \]
descends to an irreducible curve $\bar{F} \subset K$. We claim that
\[ h^{0}(K, \O_{K}(\bar{F})) = 1. \]
In fact, if the linear system $\abs{\O_{K}(\bar{F})}$ were to contain a pencil, then this would give us a pencil of symmetric curves in $\abs{\O_{A}(F)}$ with the same multiplicities at the two-torsion points, which contradicts $F$ being a fixed component of $\d$.

From the exact sequence $0 \rightarrow \O_{K}(-\bar{F}) \rightarrow \O_{K} \rightarrow \O_{\bar{F}} \rightarrow 0$, it follows that $H^{i}(K, \O_{K}(\bar{F})) = 0$ for $i > 0$, so by Riemann-Roch
\[ 1 = h^{0}(K, \O_{K}(\bar{F})) = \chi(\O_{K}, \O_{K}(\bar{F})) = \frac{1}{2} (\bar{F})^{2} + 2 \]
and therefore $(\bar{F})^{2} = -2$. On the other hand, the equality
\[ -4 = 2 (\bar{F})^{2} = (\pi^{\ast}\bar{F})^{2} = (\hat{F})^{2} = F^{2} - \sum_{i=1}^{16}f_{i}^{2} = 2d - \sum_{i=1}^{16} f_{i}^{2} \]
combined with $\sum_{i=1}^{16} f_{i}m_{i} \leq \sum_{i=1}^{16} (\frac{d_{i}}{2})^{2}$ yields
\[ \sum_{i=1}^{16} d_{i}^{2} = \sum_{i=1}^{16} (f_{i}^{2} + m_{i}^{2} + 2 f_{i}m_{i}) \leq 2d+4 + \sum_{i=1}^{16} m_{i}^{2} + \frac{1}{2} \sum_{i=1}^{16} d_{i}^{2}. \]
After rearranging the terms, we find that
\[ \sum_{i=1}^{16} m_{i}^{2} \geq -2d - 4 + \frac{1}{2} \sum_{i=1}^{16} d_{i}^{2} \geq -2d - 4 + 2 \sum_{i=1}^{16} a_{i}^{2} \geq 2d - 8 \]
for a general divisor $D = F + M \in \d$, which is the desired inequality. \qedhere

\end{proof}

As an immediate consequence:

\begin{thm}\label{thm:FC8}
Assume $\d$ has a fixed component $F \not= 0$, and let $\b = \d - F$ be the linear system defining $\varphi: A \dashrightarrow S \subseteq \P^{N}$. Then
\[ \deg \varphi \cdot \deg S \leq 8. \]
\end{thm}

\begin{proof}
As we saw in the proof of Lemma~\ref{lem:NFC8},
\begin{equation}\label{eq:M}
\deg \varphi \cdot \deg S \leq M^{2} - \sum_{i=1}^{16} m_{i}^{2} \leq 2d - (2d - 8) = 8. \qedhere
\end{equation}
\end{proof}

\begin{cor}\label{cor:SQ}
There exists a 4-to-1 rational map $\varphi: A \dashrightarrow \P^{2}$.
\end{cor}

\begin{proof}

Recall that we chose the $a_{i}$ so that $a_{15} = 0 = a_{16}$. From Remark~\ref{rem:K}, it follows that $\varphi: A \dashrightarrow S \subset \P^{N}$ factors through the quotient $A \rightarrow A/\iota$, so $\deg \varphi$ must be even. The surface $S$ is nondegenerate, so $\deg S \geq 2$. By Lemma~\ref{lem:NMT} below, it is impossible for $S$ to be rational together with $\deg \varphi = 2$, so $\{ \deg \varphi = 2, \deg S = 2, 3 \}$ is ruled out by the classification of quadric and cubic surfaces (using the fact that $\rho(A) = 1$).

Together with the upper bound $\deg \varphi \cdot \deg S \leq 8$ given by Lemma~\ref{lem:NFC8} and Theorem~\ref{thm:FC8}, there are two possibilities:
\[ \{ \deg \varphi = 2, \deg S = 4 \} \quad \text{and} \quad \{ \deg \varphi = 4, \deg S = 2 \}. \]
Either of these imply equality throughout~\eqref{eq:D} or~\eqref{eq:M}, so that there is a morphism $\Bl_{Z}A \rightarrow S$ which fits into the diagram:
\begin{center}
\begin{tikzcd}
E_{i} \arrow[r, phantom, "\subset"] &[-0.3in] \Bl_{Z}A \arrow[d, swap, "\pi"] \arrow[r, "\gamma"] \arrow[rd] & K \arrow[d, "\alpha"] \arrow[r, phantom, "\supset"] &[-0.3in] G_{i} \\
& A \arrow[r, dashed, swap, "\varphi"] & S \arrow[r, phantom, "\subset"] & \P^{3}
\end{tikzcd}
\end{center}
where $K$ is the smooth Kummer K3 surface, $\gamma$ is a branched cover of degree 2, and $G_{i} \coloneqq \gamma(E_{i})$.

In the first case where $\deg \varphi = 2$ and $\deg S = 4$, from~\eqref{eq:D} and~\eqref{eq:M} it follows that $d_{15} = 0 = d_{16}$ or $m_{15} = 0 = m_{16}$. This implies that the curves $G_{15}, G_{16}$ are contracted and their images $q_{15}, q_{16}$ under $\alpha$ are double points on $S$ since $\alpha$ is a birational morphism. Projection from a general $(N-3)$-plane containing one but not both of the $q_{i}$ defines a rational map $A \dashrightarrow \P^{2}$ of degree 2 (if $q_{15}$ is a cone point of $S$, pick a general plane passing through $q_{16}$, and vice versa). In the second case where $\deg \varphi = 4$ and $\deg S = 2$, note that $S$ is rational. \qedhere

\end{proof}

This immediately leads to Theorem~\ref{thm:MT}. It is natural to ask what $\irr(A_{d})$ is equal to for a very general polarized abelian surface. At least one can see geometrically:

\begin{lem}\label{lem:NMT}
There are no rational dominant maps $A \dashrightarrow \P^{2}$ of degree 2.
\end{lem}
\begin{proof}
Suppose there exists such a map. We have the following diagram
\begin{center}
\begin{tikzcd}
& & A^{[2]} \arrow[r, "\Sigma"] &[-0.2in] A \\
A \arrow[r, dashed, "f"] & \P^{2} \arrow[r, dashed, swap, "h"] \arrow[ur, dashed, "g"] & K^{[2]}(A) \arrow[u, hook] \arrow[r, phantom, "\eqqcolon"] & \Sigma^{-1}(0)
\end{tikzcd}
\end{center}
where $g$ is the pullback map on 0-cycles and $A^{[2]}$ is the Hilbert scheme of 2 points on $A$. Since the rational map $\Sigma \circ g$ can be extended to a morphism, it must be constant. So $\overline{\Im(g)}$ is contained in a fiber $\Sigma^{-1}(0)$, which is a smooth Kummer K3 surface $K^{[2]}(A)$. Since $g$ is injective, it descends to an injective (and hence birational) map $h: \P^{2} \dashrightarrow K^{[2]}(A)$, yielding a contradiction.
\end{proof}