\section{Introduction}
This note and \cite{joshi17-legendre}, grew out of my attempts to understand Ulmer's remarkable construction of rational points on the Legendre elliptic curve over ${\mathbb{F}_q}(t)$ after his insightful colloquium talk at the University of Arizona (on March 1,2017). While \cite{joshi17-legendre} was mostly about constructing rational points on Legendre elliptic curves, this paper describes other methods of constructing elliptic and hyperelliptic curves with rational points.

The beginning of this construction method dates back to around 1989. I discovered this construction for $K={\mathbb Q}$  and genus one in 1989. In 1988 Don Zagier taught a course on Gross-Zagier Theorem at the Tata Institute of Fundamental Research and around that time, and in response to  a question posed by C.~S.~Dalawat during one coffee-table conversation, I wrote down the following elliptic  curve
\begin{equation}\label{eq:orig}
E: y^2=x^3+x+d^2
\end{equation}
\renewcommand{\thefootnote}{\fnsymbol{footnote}}
which I showed for any integer $d\geq 3$  (note that the discriminant $4+27d^4$ is obviously never zero) has rank at least one by showing that the manifest point $(0,d)$ has infinite order (for any $d\geq 3$). This is immediate from the Lutz-Nagell Theorem: the point is not of order two as $d\neq 0$ and so it has order at least three and in which case $d^2$ must divide $4+27d^4$ which it cannot  as this implies $d^2|4$, so $d\leq2$ which contradicts our hypothesis on $d$.
Moreover by a simple search, this curve also has rank at least one for $d=\pm1,\pm2$ and hence it has rank at least one for all $0\neq d\in{\mathbb Z}$.
Two curves associated with $d,d'\in{\mathbb Q}^*$,  are  $\bar{\Q}$-isomorphic if and only if $d/d'$ is a fourth root of unity. In particular this is not a family of twists of any elliptic curve over ${\mathbb Q}$.

The following table of values shows the ranks of these curves for  $3\leq d\leq 100$\footnote{This data has been computed recently using \cite{sage}, my own computations, for a more modest range of  values ($d\leq 20$), in 1989--92 were carried out with a patchwork of small search programs, with many stretches of manual and symbolic computations as well, were written mostly in PASCAL for VAX and CYBER ``mainframes'' which were owned by the Tata Institute at the time. When John Cremona's `mwrank' became available I was able to extend these computations.}. Apart from curves of rank one and two, there are curves of rank three and one of rank four for $d=82$ which is striking as the coefficients of this curve $y^2=x^3+x+82^2=x^3+x+6724$ are not too big for a curve of this rank.
\begin{center}
	\begin{tabular}{|c|l|}
		\hline rank & $d$  \\
		\hline 1  & $5, 12, 17, 32, 35, 36, 39, 40, 41, 42, 48, 49, 52, 54, 55,\cdots$ \\
		\hline 2  & $3, 6, 7, 8, 9, 10, 11, 13, 15, 16, 19, 20, 22, 24, 25, 26, 27, 28, 29, 30,\cdots$ \\
		\hline 3  &  $14, 18, 21, 23, 31, 44, 57, 68, 69, 74, 78, 79,\cdots$ \\
		\hline 4  & $82,\cdots$ \\
		\hline
	\end{tabular}
\end{center}
For $d=82$ the four generators are of the Mordell-Weil group are $(0 : 82 : 1), (12 : 92 : 1), (60 : 472 : 1), (465/4 : 10049/8 : 1)$.

A few days after I discovered (\ref{eq:orig}), I found the curve
\begin{equation}\label{eq:orig2}
E: y^2=(x-a)(x-b)(x-c)+d^2
\end{equation}
which has six manifest points $(a,\pm d),(b,\pm d),(c,\pm d)$, and   for a suitable set of choices of $a,b,c,d$, the points  $(a,d),(b,d)$ have infinite order and are linearly independent in the Mordell-Weil group  (note that the three points $(a,d),(b,d),(c,d)$ are on the line $y=d$ and so there is one relation between these three points (a variant of \eqref{eq:orig2} with rank at least two) is described in my paper with Pavlos Tzermias \cite{joshi99}). I did not publish my results but I did share them with some of my colleagues (notably with C.~S.~Dalawat who had raised the question) and also described them in my correspondence with C.~B.~Khare but I did not think about these issues for the next few years, except to observe, when Kolyvagin's work became available, that my examples also provided families of $L$-functions with analytic ranks $\geq 1$ and $\geq 2$ respectively.

After I writing the present note I found that in recent elliptic curve literature, special cases of \eqref{eq:orig2} have been studied. For example taking $a=0,b=m,c=-m$ gives the curve (of rank at least two)
$$y^2=x^3-m^2x+d^2,$$
studied by \cite{fujita17}, while in \cite{izadi17} this special case is studied with a view to rank three sub-families. Let me also say that by mentioning above history of \eqref{eq:orig} and \eqref{eq:orig2} it is not my intent to claim any priority over these  authors (or others who may have found this equation too);  they, too,   discovered   independently that these curves have interesting properties.

Here is brief description of the new results which grew out of my attempts to understand Doug Ulmer's remarkable construction of explicit rational points in characteristic $p>0$: in Theorem~\ref{th:orig-2} I show that a variant of \eqref{eq:orig} also provides families of elliptic curves over any number field with a rational point of infinite order defined over that field. In Theorem~\ref{th:orig-2} I show that a variant of \eqref{eq:orig2} provides two rational points, both of infinite order, defined over any given number field. These examples are  well-adapted for studying the conjecture of \cite{denef80} thanks to a result of \cite{poonen02} (see Conjecture~\ref{con:denef}).

In Theorem~\ref{th:joshi-tzermias-2}, which is a variant of the result of \cite{joshi99}, I provide examples of infinite families of hyperelliptic curves defined over any given number field with many rational points and Jacobian rank at least as large as the genus.

In Theorem~\ref{th:main0} I provide a general method for constructing hyperelliptic curves with rational points over large fields. This has a number of consequences. For instance in Theorem~\ref{th:symmetric} I  construct hyperelliptic curves over number fields with about $4g$ rational points over finite extensions of large degree (about $g^g$)--it is in this context that I stumbled upon the result of \cite{osada87} (for other uses of this result see \cite{joshi17-legendre}); a variant of this  constructs hyperelliptic curves over ${\mathbb Q}$ with rational points over a finite extension with Galois group $A_n$ for all odd $n$ (see Theorem~\ref{th:An}); and curves over ${\mathbb{F}_q}(t)$ with points over a finite extension of ${\mathbb{F}_q}(t)$ with Galois group equal to ${\rm PGL}(n,{\mathbb{F}_q})$ (see Theorem~\ref{th:pgl}); and also curves over  ${\mathbb F}_2(t)$ with rational points over a finite extension of ${\mathbb F}_2(t)$ with Galois group equal to Mathieu group $M_{24}$ (see Theorem~\ref{th:m24}). There are other examples possible but I believe this list is already quite interesting; except for the Mathieu Group case, in all other cases one has an infinite family of curves of these types.

I do not claim that my examples break any records and I certainly do not claim that my methods or examples  are optimal in any way but I do hope to convince the reader that the examples which I describe here are remarkable for their simplicity, and versatility and that they will be useful to any student of rational points on curves and can be the starting point for other investigations. For example, one natural problem which suggests itself is that these higher genus curves could be used to test Minhyong Kim's conjecture that there is some higher dimensional Selmer variety in which the image of these points spans a proper subspace. Number of other conjectures are also included here which are based on my computations.

Conjecture~\ref{con:main} is a somewhat optimistic conjecture which predicts that the rational points constructed in the hyperelliptic curve examples of Theorem~\ref{th:main0} have infinite order. Some numerical evidence for this is provided in \ref{ss:examples} and Conjecture~\ref{con:main} is proved in some cases in Theorem~\ref{th:main1}.

In Subsection~\ref{ss:cubic} I return to elliptic curves again and provide examples of elliptic curves over ${\mathbb Q}$ with two rational points over ``simplest cubic fields'' (see \cite{shanks74} for this terminology). Using methods of Theorem~\ref{th:main1}  I show that these two points are linearly independent in the Mordell-Weil group in many cases (see Theorem~\ref{th:main2}). In Conjecture~\ref{con:orthogonality} I state a general conjecture about these curves which I found experimentally.   I provide a number of numerical examples illustrating this conjecture.

It is a pleasure to thank Douglas Ulmer for conversations and correspondence and for his colloquium talk which led to this paper (and \cite{joshi17-legendre}). I would also like to take this opportunity to thank C.~S.~Dalawat for asking  questions which led me to construct the curves \eqref{eq:orig} and \eqref{eq:orig2} a long time ago. It is a pleasure to thank Tanmoy Bhattacharya for many hours of tutorials on programming on VAX and CYBER he provided me in 1987--88 which made my computations on \eqref{eq:orig} possible. Thanks are also due to Kapil Paranjape for many conversations about elliptic curves and programming on VAX/CYBER during that period.

\numberwithin{equation}{subsection}

\section{Elliptic Curves}
\renewcommand{\wp}{\mathfrak{p}}
\newcommand{\mathfrak{q}}{\mathfrak{q}}
\newcommand{\O_K}{\mathcal{O}_K}
\subsection{Elliptic curves with a point of infinite order over a given number field}
In this section, I provide a simple construction of an elliptic curve over every number field with Mordell-Weil group of rank at least one over this number field.  Let $K$ be any number field, $\O_K$ be the ring of integers of $K$. For prime ideals $\wp,\mathfrak{q}\neq0$ of $\O_K$ let $p$ (resp. $q$) be the corresponding primes of ${\mathbb Z}$ lying below $\wp$ (resp. $\mathfrak{q}$).

\begin{theorem}\label{th:orig-2}
Let $K$ be any number field as above and $\wp,\mathfrak{q}$ be non-zero prime ideals of $\O_K$ not lying over $(2)\subset {\mathbb Z}$, with residue fields of prime order $p$ (resp. $q$) and $q>p+1+2\sqrt{p}$. Let $0\neq d\in \O_K$ be chosen so that
\begin{enumerate}[label={\bf(\arabic{*})}]
\item\label{th:orig-2:hyp-1} $K={\mathbb Q}(d)$,
\item\label{th:orig-2:hyp-2} $16(4+27d^4)\not\in\wp$,
\item\label{th:orig-2:hyp-3} $d\in\mathfrak{q}$.
\end{enumerate}
Then
\begin{enumerate}[label={\bf(\arabic{*})}]
\item $P=(0,d)$ is a point of infinite order on the elliptic curve $$E:y^2=x^3+x+d^2,$$
\item  neither $E$ nor $P$ can be defined over any proper subfield contained in $K$.
\item for $d,d'\in\O_K$, the corresponding curves are isomorphic over $\bar{\Q}$ if and only if $d=d'\zeta_4$ for some fourth root of unity $\zeta_4$.
\item In particular if $d\neq d'\zeta_4$ for any fourth root of unity, then the corresponding curves are not twists of each other.
\end{enumerate}
\end{theorem}

\begin{proof}
First let me show that the hypothesis of the theorem are satisfied infinitely often. By the proof of the primitive element theorem one sees that there exits (infinitely many) $d_1\in\O_K$ such $K={\mathbb Q}(d_1)$. So suppose one has chosen a $d_1\in\O_K$ such that $K={\mathbb Q}(d_1)$. Then note that any rational integer multiple of $d_1$ has the same property. It is well-known that for any number field there is a set of primes ideals of density one  with prime residue fields (see By Lemma~\ref{le:density-lemma}). So there are infinitely many prime ideals $\wp,\mathfrak{q}$ which satisfy the residue field hypothesis of the theorem.  Choose  primes $\wp,\mathfrak{q}$ lying over odd rational primes $p,q$ such that $q>p+1+2\sqrt{p}$ and $\O_K/\wp={\mathbb F}_p,\O_K/\mathfrak{q}={\mathbb{F}_q}$. Choose an integer $0\neq a\in{\mathbb Z}$ such that $a\in\wp\cap\mathfrak{q}=\wp\mathfrak{q}$. Let $d=ad_1$. Then $K={\mathbb Q}(d)$, $d\in\mathfrak{q}$ and $-16(4+27d^4)\not\in\wp$ (otherwise $4\in\wp$). Thus there is an infinite set of $(d,\wp,\mathfrak{q})$ which satisfy all the hypothesis of the theorem.  Note further that if $16(4+27d^4)\not\in\wp$ then $16(4+27d^4)\neq0$ so $E$ is always an elliptic curve! Note that $E$ has good reduction at $\wp$ as the discriminant is not contained in $\wp$ by hypothesis and as $d\in\mathfrak{q}$ but $\mathfrak{q}\not|2$ so $\mathfrak{q}$ also does not divide the discriminant $16(4+27d^4)$ of $E$. In particular one sees, as $d\in\O_K$,  that the equation for $E$ is also minimal at $\wp$ and $\mathfrak{q}$.

Suppose $P=(0,d)$ is a point of finite order $m>1$. Then $m\geq 3$: for if $2P=0$ then by \cite[Lutz-Nagell Theorem]{silverman-arithmetic} one has $d=0$ which is not the case by my assumptions on $d$. If $(q,m)=1$ then reducing modulo $\mathfrak{q}$ one sees (by \cite[Chap 7, Proposition 3.1]{silverman-arithmetic}) that $E[m]\into E(\O_K/\mathfrak{q})$ and image of $P$ which is $(0,0)\bmod{\mathfrak{q}}$ is of order two on the reduction $y^2=x^3+x\bmod{\mathfrak{q}}$. So again $m=2$ or $(q,m)=q>1$. As $m\neq 2$, let $m=q^an$ with $(q,n)=1$ then $Q=nP$ is a point of order $q^a\geq q$. Now reducing modulo $\wp$ and noting that $E[q^a]\into E(\O_K/\wp)$ one sees that
$$q\leq|E[q^a]|\leq |E(\O_K/\wp)|\leq p+1+2\sqrt{p}$$
 which is a contradiction as $q>p+1+2\sqrt{p}$. So $P$ has infinite order in $E(K)$.

Now suppose $d,d'\in K$ then the corresponding  curves are isomorphic over $\bar{\Q}$ if and only if they have the same $j$-invariants. Using the formula for $j$-invariants one sees that this means $$\frac{4}{16(4+27d^4)}=\frac{4}{16(4+27d^{'4})}$$ from which the last claim follows. In particular one sees that curves for $d$ and $d'$ are not twists of each other if $d\neq d'\zeta_4$ for any fourth-root of unity $\zeta_4$.
\end{proof}

The following lemma is certainly well-known (see \cite{lang-algebraic}) and ensures that for any number field $K$ there are infinitely many $\wp,\mathfrak{q}$ satisfying the hypothesis of the theorem.

\begin{lemma}\label{le:density-lemma}
Let $K/{\mathbb Q}$ be a number field. Then the set of primes $\wp\subset\O_K$ of $\O_K$  such that $\O_K/\wp={\mathbb F}_p$ is of Dirichlet density one in $K$.
\end{lemma}

\subsection{A numerical example}
Here is a numerical example illustrating the constructions of Theorem~\ref{th:orig-2}.
\newcommand{\exd}{\sqrt{-647}}
Let $K={\mathbb Q}(\exd)$ then class number of $K$ is $h_K=23$. Let $\wp=\left(29,\frac{7+\exd}{2}\right)$ and $\mathfrak{q}=\left(67,\frac{31+\exd}{2}\right)$ both are prime ideals. Then clearly $67>29+1+2\sqrt{29}$. Choose $d=98+\exd=67+2\left(\frac{31+\exd}{2}\right)\in\mathfrak{q}$ and one checks that $-16(4+27d^4)\not\in\wp$. Then according to the theorem
$$E:y^2=x^3+x+d^2=x^3+x+\left(98+\exd\right)^2$$
has a rational point $P=(0,d)=\left(0,98+\exd\right)$ of infinite order. One finds using \cite{sage} that torsion of $E(K)$ is zero and the N\'eron-Tate height of $P$ is $\hat{h}(P)\approx3.54047$. Thus $P$ is non-torsion (as predicted by the theorem).

\subsection{Elliptic curves  with two points of infinite order over a given number field}
Let me also mention the following variant of Theorem~\ref{th:orig-2} which will be used in the following subsection.
\begin{theorem}\label{th:orig-3}
Let $K$ be any number field as above and $\wp,\mathfrak{q}$ be non-zero prime ideals of $\O_K$ not lying over $(2)\subset {\mathbb Z}$, with residue fields of order $p$ (resp. $q$) and $q>p+1+2\sqrt{p}$. Let $0\neq d,\beta\in \O_K$ be chosen so that
\begin{enumerate}[label={\bf(\arabic{*})}]
\item\label{th:orig-3:hyp-1} $K={\mathbb Q}(d)={\mathbb Q}(\beta)$,
\item\label{th:orig-3:hyp-2} $16(-4\beta^6+27d^4)\not\in\wp$,
\item\label{th:orig-3:hyp-3} $d\in\mathfrak{q}$,
\item\label{th:orig-3:hyp-4} $\beta\not\in\wp$,
\item\label{th:orig-3:hyp-5} $\beta\not\in\mathfrak{q}$.
\end{enumerate}
Then
\begin{enumerate}[label={\bf(\arabic{*})}]
\item $P=(0,d)$ is a point of infinite order on the elliptic curve $$E:y^2=x^3-\beta^2 x+d^2,$$
\item $Q=(\beta,d)$ is also a point of infinite order on $E$, and
\item  neither $E$ nor $P,Q$ can be defined over any proper subfield contained in $K$.
\end{enumerate}
\end{theorem}
Note that the equation $E:y^2=x^3-\beta^2 x+d^2=x(x-\beta)(x+\beta)+d^2$ is special case of \eqref{eq:orig2} and as mentioned earlier, for $K={\mathbb Q}$,  Mordell-Weil ranks of the  curves $y^2=x^3-\beta^2x+d^2$ have been recently considered by \cite{fujita17} and \cite{izadi17}; they provide sub-families of these curves with ranks three and four. The proof of Theorem~\ref{th:orig-2} is similar to the proof of Theorem~\ref{th:orig-3} and is left to the reader.

\subsection{Another numerical example}
\renewcommand{\exd}{\sqrt{94546}}
Here is a numerical example illustrating the constructions of Theorem~\ref{th:orig-3}.
Let $K={\mathbb Q}(\exd)$ then class number of $K$ is $h_K=80$. Let $\wp=\left(29,8+\exd\right)$ and $\mathfrak{q}=\left(67,3+\exd\right)$ both are prime ideals. Then clearly $67>29+1+2\sqrt{29}$. Choose $d=5905-265\exd\in\mathfrak{q}$ and $\beta=-104-195\exd$. Then  one checks that $-16(4(-\beta^2)^3+27d^4)\not\in\wp$  and that one has $\beta\not\in\wp\mathfrak{q}$. Then according to the theorem
$$E:y^2=x^3-\beta^2x+d^2=x^3-(3595122466+40560\exd) x+\left(5905-265\exd\right)^2$$
has two rational points $$P=(0,d)=\left(0,5905-265\exd\right), Q=(\beta,d)=(-104-195\exd,5905-265\exd).$$  One finds using \cite{sage} that torsion of $E(K)$ is zero and the N\'eron-Tate height pairing for  $P,Q$ is
\begin{equation}
\begin{pmatrix}
 10.6548595059767  & -5.32742744032818\\
-5.32742744032818 & 10.9147767670134
\end{pmatrix}
\end{equation}
whose determinant is $\approx87.9139298596650$. Thus $P,Q$ are both non-torsion and linearly independent (as predicted by the theorem).

\subsection{On Denef's conjecture}
In \cite{poonen02} it  was  shown that a conjecture of \cite{denef80} on Diophantine definability of ${\mathbb Z}\subset \mathcal{O}_L$ follows from a conjecture about elliptic curves of rank one. Specifically it was  shown that  for  number fields $K\subset L$,  if there exists an elliptic curve over $K$ which has rank exactly equal to one over $K$ and $L$ then there exists a Diophantine definition of $\O_K$ over $\mathcal{O}_L$. In particular these works imply that Hilbert's Tenth problem is undecidable over $\mathcal{O}_L$ (if such an elliptic curve is found for suitable number fields $K$, see \cite{poonen02} and \cite{shlapentokh08}. The condition that the rank is one was later replaced by  the condition that there is an elliptic curve over $K$ such that the ranks over $L$ and $K$ coincide and this number is positive (see \cite{shlapentokh08}). In \cite{mazur10} this conjectured existence of rank preserving elliptic curves of positive rank is proved under a certain parity conjecture (also see  \cite{murty15} for related results based on analytic considerations notably for totally real fields).

Theorem~\ref{th:orig-2} and Theorem~\ref{th:orig-3}, which produce a rich supply of elliptic curves over any given number field with an explicit points of infinite order, reduce the question of finding rank preserving elliptic curves of positive rank (and hence  Hilbert's Tenth Problem for $\mathcal{O}_L$)  to the following more concrete assertions (see Conjectures~\ref{con:denef}, \ref{con:denef2} and \ref{con:denef3}) which may perhaps be accessible. At any rate proof of these conjectures, for a given $K$ and $L$, implies that $\O_K$ has a Diophantine definition in $\mathcal{O}_L$.  In particular under the hypothesis of Theorem~\ref{th:orig-2} one has positivity of the rank (for the elliptic curves I construct). So rank positivity hypothesis in \cite{shlapentokh08} holds for these curves. Since Theorem~\ref{th:orig-2} provides an abundance of curves over a given number field $K$ with positive rank and an explicit point, it seems reasonable to expect that for any finite cyclic extension $L/K$ there is at least one (and possibly infinitely many) of these curves which preserve their ranks over $L$.  I provide here two explicit versions of this conjecture--the second may be more difficult to prove (but for more on this see \cite{mazur10}):
\begin{conj}\label{con:denef}
Let $K\subset L$ be a cyclic extension of prime degree of number fields and suppose $\sqrt{-1}\not\in L$. Then there exists a $0\neq d\in\O_K$ satisfying the hypothesis \ref{th:orig-2:hyp-1}--\ref{th:orig-2:hyp-3} of Theorem~\ref{th:orig-2} such that the point $(0,d)$ on $E:y^2=x^3+x+d^2$
is of infinite order and generates $E(L)\tensor{\mathbb Q}$.
\end{conj}

\begin{remark}
Let me remark that the restriction to cyclic extensions of prime degree in the above conjecture comes from the observation of \cite{mazur10}.
Secondly if $i=\sqrt{-1}\in L$ then there is another rational point $(i,d)$ and this is often linearly independent of $(0,d)$. For example for $y^2=x^3+x+49$, the points $P=(0,7)$ and $Q=(i,7)$ are linearly independent.
\end{remark}

\begin{conj}\label{con:denef2}
Let $K\subset L$ be a pair of number fields. Then there exists a $0\neq d\in\O_K$ satisfying the hypothesis \ref{th:orig-2:hyp-1}--\ref{th:orig-2:hyp-3} of Theorem~\ref{th:orig-2} such that ${\rm rk}(E(L))={\rm rk}(E(K))\geq 1$.
\end{conj}

To avoid the hypothesis $\sqrt{-1}\not\in L$ consider more generally the curve $y^2=x^3+\alpha x+d^2$. This has a rational point $P=(0,d)$ and the proof of Theorem~\ref{th:orig-2} also shows that this point is of infinite order (assuming for instance that $\alpha\not\in\mathfrak{q}$). This curve also has another manifest point: $(\sqrt{-\alpha},d)$ and this point is also of infinite order in $E(K)$ if and only if $\sqrt{-\alpha}\in K$. Given number fields $K\subset L$ it is certainly possible to choose $\alpha\in K$ such that $\sqrt{-\alpha}$ is not in $L$. On the other hand by choosing $\alpha=-\beta^2$ suitably  one sees from Theorem~\ref{th:orig-3} that $(\beta,d)$ is a $K$-rational point of infinite order.  So the more general version of the conjecture is the following conjecture.

\begin{conj}\label{con:denef3}
Let $K\subset L$ be an extension of number fields. Then there exists an $\alpha\in\O_K$ and $0\neq d$ in $\O_K$ satisfying the hypothesis \ref{th:orig-2:hyp-1}--\ref{th:orig-2:hyp-3} of Theorem~\ref{th:orig-2} such that
$$1\leq {\rm rk}(E(K))={\rm rk}(E(L))\leq 2.$$
\end{conj}

\section{Hyperelliptic Curves}\label{se:high-genus}
\subsection{Hyperelliptic Curves over any number field with Jacobian of rank at least $g$}
In 1999 during the Arizona Winter School, where Coleman-Chabauty methods were being applied to specific genus two curves, I showed my example (\eqref{eq:orig}) to Pavlos Tzermias, (both of us were post-doctoral faculty at Arizona at the time) and suggested that we could try and study the genus two case and see if we could prove that the point $(0,d)$ has infinite order in the Jacobian of that curve. This led to our paper \cite{joshi99} where we proved substantially more than either of us had initially hoped to prove. We showed that for any odd prime $p\geq 5$ and any integers $a_1,\ldots,a_p$ representing the $p$ distinct residue classes modulo $p$ the curve:
\begin{equation}\label{eq:joshi-tzermias}
y^2=(x-a_1)\cdots (x-a_p)+p^2d^2
\end{equation}
has at least $2p$ or about $4g$ rational points $(a_i,\pm pd)$ and its Jacobian has Mordell-Weil  rank at least $g$ over ${\mathbb Q}$. This example, despite its simplicity and generality, has largely been forgotten in the Coleman-Chabauty method and rational points literature (at least as far as I can tell). Note that in \cite{joshi99} we did not use Coleman-Chabauty method to compute ranks--rather we turned the method on its head and proved that ranks must be ``large'' as we have more rational points than allowed by Coleman-Chabauty bound. Our paper also has a genus one variant of \eqref{eq:orig2} with rank at least two.   It is amusing to note that  for $d=1$ in \eqref{eq:orig} one gets the curve $y^2=x^3+x+1$ which also has rank one (though this needs more work than Lutz-Nagell Theorem argument which I sketched above) this genus one curve is the quotient of the genus two curve $y^2=x^6+x^2+1$, with the solution $(1/2,9/8)$, which occurs in the work of Diophantus and one finds a complete list of rational points on  it in J.~L.~Wetherell's  thesis  (see \cite{wetherell99}). During AWS 1999, Wetherell explained his approach to rational points on the Diophantus curve using Coleman-Chabauty method and my work with Tzermias was to some extent prompted by Wetherell's lectures.

Here is a variant of \cite{joshi99} which provides a family of curves of genus $g=(p-1)/2\geq 2$ for a positive density of odd primes $p\geq 5$, over any number field, and with a collection of about $4g$ points which generate a subgroup of rank at least $g$.

\begin{theorem}\label{th:joshi-tzermias-2}
Let $K/{\mathbb Q}$ be any number field. Let $\wp$ be a  prime of $\O_K$ lying over an unramified rational prime $p\geq 5$. Let $\O_K/\wp={\mathbb F}_q$, so $q=p^m$ for some $m\geq 1$. Let $a_1,\ldots,a_q\in\O_K$ belong to the $q$ distinct residue classes modulo $\wp$. Let $0\neq d\in\wp$ and suppose that $K={\mathbb Q}(a_1,\ldots,a_p,d)$. Consider the hyperelliptic curve
$$C:y^2=(x-a_1)\ldots (x-a_q)+d^2.$$
Then
\begin{enumerate}[label={\bf(\arabic{*})}]
\item  $C$ has $2q+1$ $K$-rational points given by $(a_i,\pm d)$ and $\infty$,
\item  its Jacobian $J$ has $K$-rank at least $g$.
\item Moreover this curve cannot be defined over a subfield of $K$.
\item In particular for a set of primes $p\geq 5$ of positive density, there is a family of curves of genus $g=\frac{p-1}{2}$ which is defined over $K$ and such that the Mordell-Weil rank is at least $g$.
\end{enumerate}
\end{theorem}
\begin{proof}
The proof is same as the one given in \cite{joshi99} I recall it here for convenience: suppose if possible that the rank of $J(K)$ is at most $g-1$. By construction there are at least $2q+1$ $K$-rational points given by $\infty$ and $(a_i,\pm d)$. The latter reduce to $(\alpha,0)$ for every $\alpha\in\O_K/\wp={\mathbb F}_q$. So modulo $\wp$ the curve, which is now given by $y^2=x^q-x$, has exactly $q+1$ rational points over ${\mathbb F}_q=\O_K/\wp$.   On the other hand,  as the genus of the curve is $\frac{q-1}{2}$, and by our supposition the rank is at most $g-1$, so by \cite{coleman85} the number of $K$-rational points  $$2q+1\leq \#C(K)\leq2g-2+\#C(\O_K/\wp)=q-1-2+q+1=2q-2.$$ So one has arrived at a contradiction. Hence the  rank of $J(K)$ is at least $g$.

The assumption that the field generated by $a_1,\ldots,a_q,d$ is $K$ ensures that the points are not all defined over a subfield of $K$. The last assertion follows from Lemma~\ref{le:density-lemma} upon considering primes $\wp$ such that $\O_K/\wp={\mathbb F}_p$.
\end{proof}

\begin{remark}
In \cite{joshi99} we showed that for $K={\mathbb Q}$ if the polynomial $(x-a_1)\cdots (x-a_p)+d^2$ is irreducible then the rank is at least $2g$. It seems reasonable that some version of this result  of \cite{joshi99} also holds for any number field $K$. In fact ranks  can be even higher than $2g$ (in this situation). For instance in \cite{gallegos} it is shown that the curve ($K={\mathbb Q}$, $p=5$ and $g=2$ for this example)
$$y^2=(x + 19)(x + 20)(x + 21)(x + 22)(x + 23) + 20^2$$
has Jacobian of ${\mathbb Q}$-rank at least five.
\end{remark}

\subsection{Hyperelliptic curves  with points over fields of large degree}
I describe a  method which provides an interesting collection of rational points on higher genus curves. Let $K$ be a field of characteristic $p\neq 2$ ($p=0$ is allowed). If $C/K$ is a smooth, projective curve, let $J_C=Jac(C)$ be the Jacobian of $C$ and if $C(K)\neq \emptyset$, then embed $C\into J$ by in the usual way one of the $K$-rational points. I construct curves over small global fields with points over rather large fields (typically the examples I construct have genus $g$ and have points at least $4g$ rational points over fields of degree $\approx g^g$ and these points are not defined over any proper sub-extension which is Galois over the base-field). My constructions are based on the following simple idea and provides curves over ${\mathbb Q}$ with rational points over fields of very large degrees in comparison with their genus.

For a finite group $G$, let $m(G)$ be the minimum of dimensions of ${\mathbb Q}$-rational, faithful representations of $G$ on a ${\mathbb Q}$-vector space.
\begin{theorem}\label{th:main0}
Let $f(X)\in K[X]$ be an irreducible polynomial of odd degree  with splitting field $L_f/K$. Suppose that for  some  $d\in K^*$ the polynomial
$$g(X)=
f(X)+d^2
$$
has distinct roots.
Then
\begin{enumerate}[label={\bf(\arabic{*})}]
\item\label{th-points-1} Let $f(u)=0$ be a root of $f(X)$. Then $(u,\pm d)$ is an $L$-rational point on $$C:y^2=g(X).$$
\item\label{th-points-2} In particular $|C(L)|\geq 2\deg(f)\geq 4g+2$.
\item\label{th-points-3} If ${\rm Gal}(L_f/K)$ is a simple group then $L_f$ is the smallest Galois extension of $K$ over which $(u,\pm d)$ is defined.
\item\label{th-points-4-trans} Moreover ${\rm Gal}(L_f/K)$ acts transitively on the $\deg(f)$ points $P=(u,d)$ where $u$ runs through the roots of $f(X)=0$.
\item\label{th-points-5-rank} Suppose for one root $u$, $P=(u,d)$ is non-torsion in $J(L_f)$, then rank of the subgroup of $J_C(L_f)$ generated by these points
is at least  $m({\rm Gal}(L_f/K))$.
\end{enumerate}
\end{theorem}
\begin{proof}
Let $u$ be a root of $f(X)$, let $G={\rm Gal}(L_f/K)$. Then clearly $P_\pm=(u,\pm d)$ is in $C(L_f)$. Genus of $C$ satisfies $\deg(f)=2g+1$. So $|C(L_f)|\geq 2\deg(f)+1=4g+2$. If $G$ is simple then there are no nontrivial quotients of $G$. So $L_f$ is the smallest Galois extension of $K$ over which $(u,\pm d)$ are defined. Since $f$ is irreducible, $G$ acts transitively on the roots of $f(X)$ in $L_f$ and this induces a transitive action of $G$ on the $\deg(f)$ points $(u,d)$ where $u$ runs through the roots of $f(X)$. If one $(u,d)$ is torsion then by the transitivity of Galois action all of them are torsion. So if one of them is non-torsion the so are all of them. In particular $G$ acts on a non-zero ${\mathbb Q}$-vector space. Further as $G$ is simple this action is faithful (the trivial action is not transitive). Hence the subspace generated by these points is at least as big as $m(G)$.

The transitivity of the action of $G={\rm Gal}(L_f/K)$ follows from the fact that $G$ action on the roots of $f(X)$ is transitive by the irreducibility of $f(X)$.

Now suppose $P=(u,d)$ is non-torsion in $J_C(L_f)$ then by the Galois action this is true for all the roots $u$ of $f(X)$. So $G$ acts on the non-zero vector space generated by these points. Thus the span of these points in $J_C(L)\tensor{\mathbb Q}$ is of dimension at least $m(G)$.
\end{proof}

\subsection{Hyperelliptic Curves over ${\mathbb Q}$ with points over large extensions}
Here are some consequences of this simple idea.

In \cite{osada87} it was shown that there exists infinitely many trinomials $X^n+aX^s+b\in{\mathbb Q}[X]$ whose Galois group is $S_n$. An explicit example of such a polynomial was also given in \cite{osada87}: $X^n-X-1$ has Galois group $S_n$.
\begin{theorem}\label{th:symmetric}
Let $f(X)=X^n+aX^s+b\in{\mathbb Q}[x]$ for $n\geq 5$. Let $L/{\mathbb Q}$ be the splitting field of $f(X)$ and assume that ${\rm Gal}(L/{\mathbb Q})=S_n$. Let $g(X)=f(X)+d^2$. Then there exist infinitely many $d\in {\mathbb Z}$ is  such that $g(X)$ has distinct roots.  Then
\begin{enumerate}[label={\bf(\arabic{*})}]
\item ${\rm Gal}(L/{\mathbb Q})=S_n$ and
\item $|C(L)|\geq 2n$ and hence
\item $|C(L)|>\frac{\log([L:K])}{\log\log([L:K])}$
\end{enumerate}
\end{theorem}

\begin{proof}
The discriminant of $g$ is a polynomial in $d$. So the existence of infinitely many $d$ is clear. Hence $C$ is a nonsingular for such $d$. Now suppose $n$ is sufficiently large then one can use Stirling's estimate for $n!=[L:K]$ to get the last assertion.
\end{proof}

In \cite{hermez01} one finds the construction of explicit polynomials of the form $X^n+aX^m+b\in{\mathbb Q}[X]$ whose Galois group over ${\mathbb Q}$ is the Alternating group $A_n$. So one may use this to produce hyperelliptic curves with primitive points.
\begin{theorem}\label{th:An}
Let $f(X)=X^n+aX^m+b\in{\mathbb Q}[X]$ be a polynomial whose splitting field $L_f/{\mathbb Q}$ has ${\rm Gal}(L_f/{\mathbb Q})=A_n$ and $n\geq 7$. Suppose $d\in{\mathbb Q}$ is chosen so that $g(X)=f(X)+d^2$ has distinct roots. Then $C:Y^2=g(X)$ has an $L_f$-primitive point $P=(u,\pm d)\in C(L)$. Moreover $|C(L)|\geq 4g+2$.
\end{theorem}

\subsection{Hyperelliptic curves over function fields}
The method I have described here is also applicable to curves over function fields. Here is a very small sample of the sort of results one can prove. In \cite{abhyankar97} Abhyankar constructed trinomial equations over $K={\mathbb F}_q(t)$ with large Galois groups. One can use Theorem~\ref{th:main0} to these polynomials and obtain hyperelliptic curves with many points over highly non-abelian extensions of $\fq(t)$
\begin{theorem}\label{th:pgl}
Let $p$ be an odd prime, and $q$ be a power of $p$. Let $m\geq 2$ be an integer. Let $\langle m-1\rangle=\frac{q^m-1}{q-1}$. Let $K={\mathbb{F}_q}(t)$ and let $L_f/K$ be the splitting field of $U^{\langle m-1\rangle}+U+t\in K[U]$. Suppose $d\in K^*$ be such that $g(X)=f(X)+d^2$ has distinct roots and let  $C:Y^2=g(X)$. Then
\begin{enumerate}[label={\bf(\arabic{*})}]
\item ${\rm Gal}(L_f/K)=PGL(m,{\mathbb{F}_q})$,
\item $|C(L)|\geq 2\frac{q^m-1}{q-1}$.
\end{enumerate}
\end{theorem}

For $p=2$ one obtains, using \cite{conway10}, the following
\begin{theorem}\label{th:m24}
Let $p$ be an odd prime, and $q$ be a power of $p$. Let $m\geq 2$ be an integer. Let $\langle m-1\rangle=\frac{q^m-1}{q-1}$. Let $K={\mathbb{F}_q}(t)$ and let $L_f/K$ be the splitting field of $U^{\langle m-1\rangle}+U+t\in K[U]$. Suppose $\alpha,d\in K^*$ be such that $g(X)=f(X)+d(d+\alpha)$ has distinct roots and let  $C:Y^2+\alpha Y=g(X)$. Then
\begin{enumerate}[label={\bf(\arabic{*})}]
\item ${\rm Gal}(L_f/K)=M_{24}$ (Mathieu Group),
\item $|C(L)|\geq 48$,
\item $L$ is the smallest Galois extension of $K$ which contains $(u,d)$ where $u$ is any root of $U^{\langle m-1\rangle}+U+t=0$.
\end{enumerate}
\end{theorem}

\subsection{The rank conjecture}
Let $C/K$ be a  one of the curves described in the preceding sections (in particular $C$ is hyperelliptic, equipped with a $K$-rational point). Let $J_C=Jac(C)$ be the Jacobian of this curve and embed $C\into J_C$ using a $K$-rational point $P_0=\infty$. Now suppose $L/K$ is a finite Galois extension and $C(L)\neq C(K)$. Suppose $P\in C(L)$. I say that $P$ is an $L$-\emph{primitive point} if $L/K$ is the smallest Galois extension of $K$ over which $P$ is defined.

Note that all the examples constructed in this subsections are of curves equipped with primitive points:  the condition of Theorem~\ref{th:main0}\ref{th-points-3} says that $P=(u,\pm d)$ is an $L_f$-primitive point.

I make the following very optimistic conjecture (and even more optimistic if one wants to remove the hyperelliptic condition):
\begin{conj}\label{con:main}
Let $C/K$ be a smooth, projective, hyperelliptic curve of genus $g\geq 1$.  Suppose $C$ has a $K$-rational point $P_0$ and $C$ is embedded in $J_C$ using this $K$-rational point. Suppose $L/K$ is a finite Galois extension  with $G={\rm Gal}(L/K)$ and $P\in C(L)$ is an $L$-primitive point. If $G$ is a nonabelian almost simple group and $|G|$ is sufficiently large then $P$ is non-torsion in $J_C(L)$; in particular $$\dim J_C(L)\tensor{\mathbb Q}\geq
m({\rm Gal}(L/K)).$$
\end{conj}

A particular case of the conjecture is the following conjecture.
\begin{conj}\label{con:main-osada-polynomial}
Let $n\geq 5$ be an odd integer. Let $0\neq d\in{\mathbb Z}$ be an integer chosen such that $g(X)=X^n-X-1+d^2\in{\mathbb Q}[X]$ has distinct roots. Let
$C/{\mathbb Q}$ be a smooth, projective, hyperelliptic curve of genus $g\geq 2$ defined by $Y^2=g(X)$ and  embed in $C\into J_C$ using the tautological point at $\infty$.
Let $L_f/{\mathbb Q}$ be the splitting field of $f(X)=X^n-X-1$.

Then for any root $u$ of $f(X)=0$, the $L_f$-rational point  is non-torsion in $J_C(L)$ and in particular $$\dim J_C(L_f)\tensor{\mathbb Q}\geq
	m({\rm Gal}(L_f/{\mathbb Q}))=n-1.$$
\end{conj}

\subsection{Two numerical examples of the Conjecture}\label{ss:examples}
Here are two concrete example of  Conjecture~\ref{con:main}:
\begin{example}
Consider $f(X)=x^5-x-1\in{\mathbb Q}[X]$ and $g(X)=f(x)+7^2$ (so $d=7$). By \cite{osada87} the Galois group of $f(X)$ (over ${\mathbb Q}$) is $S_5$. The curve $C:Y^2=g(X)=X^5-X-1+7^2$ has genus $g=2$ and the curve has rational points $(u,\pm 7)$ over the splitting field $L_f$ of $f(X)$ where $u$ is any root of $X^5-X-1=0$. To check if $(u,7)$ is non-torsion it is sufficient to work in the field ${\mathbb Q}(u)$ obtained by attaching one root $u$ of $f(X)$ (this is of degree five). One can calculate (using \cite{sage}) multiples of this point in the Jacobian of $C$ and as far as I see the points $(u,7)\in C(L_f)$ are non-torsion in the Jacobian of $C$. So $J_C(L_f)\tensor{\mathbb Q}$ is equipped with a faithful, ${\mathbb Q}$-rational representation of $S_5$ and hence has ${\mathbb Q}$-rank at least four.
\end{example}

\begin{example}
Here is a genus three example with a non-abelian simple group. It is well-known that the polynomial $f(x)=x^7-7x+3$ has as its Galois group over ${\mathbb Q}$ the unique simple group of order $168$ (isomorphic to $PSL(2,7)$). Consider the curve $C:y^2=x^7-7x+3+11^2$ so $d=11$ is chosen such that the polynomial on the right has distinct roots. Let $L/{\mathbb Q}$ be the splitting field of $x^7-7x+3$. Then ${\rm Gal}(L/{\mathbb Q})=PSL(2,7)$ is simple of order $168$. By construction $C(L)$ has at least $14$ points given by $(u,\pm d)$ where $u$ is any root of $x^7-7x+3$. One expects that the rank of $J_C(L)$ is at least $6$ as this is the dimension of the smallest faithful ${\mathbb Q}$-rational representation of ${\rm Gal}(L/{\mathbb Q})=PSL(2,7)$. By computing with \cite{sage} one checks that by adjoining any root $u$ of $f(x)$ to ${\mathbb Q}$, the point $(u,11)$ is not of order $\leq 100$ over ${\mathbb Q}(u)$ and it is quite reasonable to expect that this point is not torsion and hence $J_C(L)\tensor Q$ has ${\mathbb Q}$-rank at least six.
\end{example}

\subsection{Proof of the rank conjecture in some cases}
Let me now prove Conjecture~\ref{con:main} in some cases.
\begin{theorem}\label{th:main1}
Let $f(X)\in{\mathbb Z}[X]$ be a monic irreducible polynomial of odd degree $n\geq 5$ and with Galois group $G={\rm Gal}(L_f/{\mathbb Q})$ which is either simple or  $G=S_n$. Let $L_f$ be a  splitting field of $f(X)$. Suppose $\wp$ is a non-zero prime ideal in $L_f$ not lying over $(2)\subset {\mathbb Z}$. Suppose that $d\in L_f$ is such that
\begin{enumerate}[label={\bf(\arabic{*})}]
\item $d\in\wp$,
\item $g(X)=f(X)+d^2\in L_f[X]$ is irreducible, and
\item $g(X)\cong f(X)\bmod{\wp}$ has distinct roots,
\item let $C: Y^2=g(X)=f(X)+d^2$ be the hyperelliptic curve over $L_f$ defined by $g(X)$,
\item embed $C\into J=J_C$ using $\infty\in C(L_f)$.
\end{enumerate}
Then
\begin{enumerate}[label={\bf(\arabic{*})}]
\item for any root $u$ of $f(X)=0$, $C$ has $L_f$-rational points $(u,\pm d)$,
\item for each $u$, these points are of infinite order in the Jacobian $J$ of $C$,
\item and $J(L_f)$ has rank at least $m(G)$ (resp. $n-1=2g$ if $G=S_n$).
\end{enumerate}
\end{theorem}
\begin{proof}
The proof is by methods of \cite{joshi99}. By Theorem~\ref{th:main0} it suffices to prove that the listed points are not torsion in the Jacobian. As $d\in\wp$ and $g(X)\cong f(X)\bmod{\wp}$ has distinct roots, the images of these points modulo $\wp$ generate a subgroup of the $2$-torsion of this curve modulo $\wp$ (and so the torsion order is prime to the residue characteristic of $\wp$). In particular the $n$ points $(u,d)$  are of order at most two in the Jacobian. But $J[2]$ is generated by the $2g+1=n$ Weierstrass points of $C$ which correspond to the roots of the polynomial $g(X)$. As $g(X)$ is irreducible (over $L_f$),  no two torsion point of $J$ is defined over $L_f$. So the listed points are of infinite order in $J(L_f)$. If $G$ is simple then by Theorem~\ref{th:main0} the rank is at least $m(G)$. So now assume $G=S_n$. As the action of $G={\rm Gal}(L_f/{\mathbb Q})$ on the points $n\geq 5$ points $(u,d)$ is transitive,  this action cannot factor through $S_n/A_n={\mathbb Z}/2$. So the representation of $G$ on $J(L_f)\tensor{\mathbb Q}\neq 0$ is faithful and as $m(S_n)=n-1$ for $n\geq 5$, the rank of $J(L_f)$ is at least $\geq  n-1=2g$ if $G=S_n$ as was claimed.
\end{proof}

\subsection{Elliptic Curve variant with points over simplest cubic fields}\label{ss:cubic}
My next example, a variant of both \eqref{eq:orig} and the equation in Theorem~\ref{th:main0}, is inspired by \cite{shanks74} and provides a simple example of the abelian group case of the preceding examples. One can combine methods of \cite{shanks74} with those outlined above to produce elliptic curves over ${\mathbb Q}$ with three rational points defined over the ``simplest cubic fields'' constructed in \cite{shanks74}. Briefly the construction is as follows. Suppose $a$ is a positive integer and $$f(X)=X^3-(aX^2+(a+3)X+1).$$ Let $L_f$ be the splitting field of $f(X)\in{\mathbb Z}[X]$. In \cite{shanks74} it is shown that ${\rm Gal}(L_f/{\mathbb Q})\isom A_3={\mathbb Z}/3$ and these fields are called simplest cubic fields. If $\rho$ is any root of $f(X)$ then other roots of $f(X)$ are $\rho_2=-1/(1+\rho), \rho_3=-1/(1+\rho_2)$. Moreover $\rho,\rho_2,\rho_3$ are fundamental units in $L_f$.

Now consider the elliptic curves $E: Y^2=f(X)+d^2$. Then this has $L_f$-rational points $(\rho,\pm d),(\rho_2,\pm d)$ and $(\rho_3,\pm d)$.

Here two numerical examples.

Let $a=50$ then $L_f/{\mathbb Q}$ has class number $h=19$. Choose $d=50$ then the torsion subgroup of $E(L_f)$ is trivial (as can be computed using \cite{sage}) so these points are necessarily of infinite order and one finds the height pairing matrix for the two $L_f$-rational points $P=(u,50)$ and $Q=(-1/(1+u),50)$:
\begin{equation}
\begin{pmatrix}
	3.49761746081572 & -1.74880873040786\\
	-1.74880873040786 & 3.49761746081572
\end{pmatrix}
\end{equation}
whose determinant is approximately $9.17499592665226$.

Now set $R=(\rho_3,50)$ and $P_1=P+R,P_2=P-R$. Then the height pairing matrix of $P_1,P_2$ is
\begin{equation}
\begin{pmatrix}
	3.49761746081572 & 0.000000000000000\\
	0.000000000000000 & 10.4928523824472
\end{pmatrix}
\end{equation}
So the rank of $E(L_f)$ is at least two and $P_1,P_2$ are orthogonal with respect to the height pairing.

Here is the second example.

Now let $a=36$ then $L_f/{\mathbb Q}$ has class number $h=12$ (this case is not included in the tables in \cite{shanks74}). Now choose $d=a=36$ then the torsion subgroup of $E(L_f)$ is trivial (as can be computed using \cite{sage}) so these points are necessarily of infinite order and one finds the height pairing matrix for the two $L_f$-rational points $P_1=P+Q$ and $P_2=P-Q$ where $P=(u,36)$ and $Q=(-1/(1+u),36)$
\begin{equation}
\begin{pmatrix}
  2.49439281440290 &  8.88178419700125\times 10^{-16}\\
8.88178419700125\times 10^{-16} &     7.48317844320869
\end{pmatrix}
\end{equation}
So the rank of $E(L_f)$ is at least two and $P_1,P_2$ are orthogonal with respect to the height pairing.

Hence it seems reasonable to conjecture that for any positive integers $a>2$ such that $g(X)=f(X)+a^2$ has distinct roots the rank of $E(L_f)$ is at least two and the  points $P_1,P_2$ as constructed above provide an orthogonal basis for the ${\mathbb Q}$-vector space spanned by the points $P,Q,R$ in $E(L_f)$.

In fact it seems reasonable to expect that for any positive integers $a,d$ such that $f(X)+d^2$ has distinct roots, the curve $E$ has rank at least two over the cubic (galois) extension $L_f/{\mathbb Q}$. Then $P_1=P+Q,P_2=P-Q$ as above are orthogonal for the height pairing. Let me also note that the hypothesis $a,d\in{\mathbb Z}$ cannot be relaxed as the following example shows.

Let $a=745, d=u^2 - u - 3$ (both chosen randomly by SAGE) then the height pairing matrix for $P_1,P_2$ is
$$
\begin{pmatrix}
6.40170943412354 & -1.10204026919419\\
-1.10204026919419 & 17.0158570702399
\end{pmatrix}
$$
So orthogonality of $P_1,P_2$  is certainly false if one takes $d\in L_f$ (in fact $d=u^2-u-3$ is an algebraic integer). Moreover $P,Q$ are not orthogonal either and orthogonality also fails if one chooses $a\in{\mathbb Q}$ but not in ${\mathbb Z}$ and hence orthogonality seems to require $a\in{\mathbb Z}$ and $d\in{\mathbb Q}$.

Here is what I can prove using methods of \cite{joshi99}.

\begin{theorem}\label{th:main2}
Let $a\geq 1$ be an integer and let $f(X)=X^3-(aX^2+(a+3)X+1)$ with roots $\rho,\rho_2,\rho_3$. Let $L_f$ be its splitting field over ${\mathbb Q}$. Suppose $\wp$ is a non-zero prime ideal in $L_f$ not lying over $(2)\subset {\mathbb Z}$. Suppose that $d\in L_f$ is such that
\begin{enumerate}[label={\bf(\arabic{*})}]
\item $d\in\wp$,
\item $g(X)=f(X)+d^2\in L_f[X]$ is irreducible, and
\item $g(X)\cong f(X)\bmod{\wp}$ has distinct roots.
\end{enumerate}
Then
\begin{enumerate}[label={\bf(\arabic{*})}]
\item $E$ has $L_f$-rational points $P_1=(\rho,\pm d),P_2=(\rho_2,\pm d), P_3=(\rho_3,\pm d)$,
\item each of these points is of infinite order,
\item and $E(L_f)$ has rank at least two.
\end{enumerate}
\end{theorem}
\begin{proof}
The proof is similar to that of Theorem~\ref{th:main1} and is left to the reader.
\end{proof}

\begin{conj}\label{con:orthogonality}
Let $a\geq 1$ be any integer and $0\neq d\in{\mathbb Q}$ such that $f(X)+d^2$ has distinct roots. In the notation of  Theorem~\ref{th:main2} and with $P_1=(\rho,d,1), P_2=(\rho_2,d,1), P_3=(\rho_3,d,1)$ and $P_i+P_j$, $P_i-P_j$, (for $1\leq i\neq j\leq 3$) are always orthogonal for the canonical height pairing on the Mordell-Weil  group $E(L_f)$. In particular $E(L_f)$ has rank at least two.
\end{conj}

Let me remark that orthogonality is immediate if one proves that $P_1,P_2,P_3$ span a vector space of dimension two (note that $P_1,P_2,P_3$ satisfy one linear relation $P_1+P_2+P_3=O$) upon observing that $P_1,P_2,P_3$ have the same N\'eron-Tate height (as they are conjugate).
\bibliographystyle{plain}


\section{Introduction}

\let\thefootnote\relax\footnotetext{2010 Mathematics Subject Classification 46L53, 60G70.} \footnote{Key words: Boolean independence, log-logistic distributions, extreme values, max stable laws.} In extreme value theory, instead of the sum of independent random variables, one deals with their max.  In \cite{Arous-Voiculescu}, looking for an analogue of extreme value theory in free probability, the Ando max was used. The Ando max \cite{Ando} of two noncommutative random variables, i.e. hermitian operators, amounts to replacing the operators by the projection-valued process, indexed by $\mathbb{R}$, where to each $t\in \mathbb{R}$ we associate the spectral projection for $(-\infty, t]$ and take the min of the projections.

In this note we want to pursue the same idea with Boolean independence \cite{Speicher}, \cite{Speicher-Woroudi}. In the free setting the free max-stable laws turned out to fall into 3 families \cite{Arous-Voiculescu} as in the classical framework. Actually, in the free case, the max-stable laws resulted in generalized Pareto laws, coinciding surprisingly with precisely those limit laws which were found in Peaks over Thresholds in \cite{Balkema} (concerning this coincidence see \cite{Grela-Nowak}). Due to special features of Boolean independence related to units, it turns out that in this framework the question should be naturally restricted to positive noncommutative random variables. Instead of three families of limit laws there is only one family of Boolean max-stable laws and again, like with free independence, these laws have also been found in the classical framework, they are Dagum laws (see \cite{Kleiber}), which appear typically in wealth distributions.

In addition to this introduction, this paper has three more sections. In section 2 we give preliminaries about Boolean independence (see for instance \cite{Bercovici}, \cite{Chackraborty-Hazra}, \cite{Speicher}, \cite{Speicher-Woroudi}), our choices between equivalent approaches, the Ando max and a discussion about the reasons for restricting the study of Boolean max-convolution to non-negative variables (or some equivalent class).

In section 3 we compute the distribution of the Ando max of Boolean independent projections and from this result develop the Boolean max-convolution. We show that the semigroup on $[0, 1]$ with the operation coming from operations on Boolean independent projections is isomorphic to $[0,1]$ endowed with multiplication, which is the semigroup underlying classical extreme value theory. This isomorphism will be of great help and should be compared to the fact that in the case of free extreme value theory \cite{Arous-Voiculescu} there are useful homomorphisms between the semigroups on $[0, 1]$, but not such a perfect fit as an isomorphism.

Section 4 uses the results of the preceding section to determine the Boolean max-stable laws and their domain of attraction. In essence, in view of the isomorphism of semigroup laws on $[0, 1]$ found in section 3, this amounts to transfers of classical results to the Boolean setting, with some restrictions. The main restriction is that the laws should be supported on $[0, \infty)$ and this singles out Fr\'echet laws in the classical framework. When transferred to Boolean probability these become Dagum distributions, which are also called log-logistic distributions. Thus, also in the Boolean framework the max-stable laws have also a history in classical probability.

Concluding, we would like to mention some of the developments around the free extreme values of \cite{Arous-Voiculescu} (see \cite{Georges-Duvillard}, \cite{Grela-Nowak}, \cite{Hazra-Maulik}) which suggest similar questions for Boolean extremes.

\section{Preliminary Considerations}

The noncommutative probability framework we use, that of hermitian operators on a Hilbert space (actually their spectral scales), is equivalent to using von Neumann algebras, but since this is a quite short paper, this seemed the best for our purpose.

Thus, noncommutative random variables will be hermitian operators $T= T^*$ on some Hilbert space $\mathcal{H}$, endowed with a state vector $\xi \in \mathcal{H}$, $\norm{\xi} =1$, which gives the expectation functional  $\phi(T) = \langle T\xi, \xi\rangle$. We can encode the same data as a projection-valued process $\mathbb{R}  \ni t \mapsto E(T; (-\infty, t])$, which to each $t$ associates the spectral projection of $T$ for $(-\infty, t]$. Here, $E(T; (-\infty, t])$ is an increasing function of $t$, which is right semicontinuous with respect to the strong operator topology. That $T$ is bounded means that there are $t_0 < t_1$ so that $E(T; (-\infty, t_0]) =0$ and $E(T; (-\infty, t_1]) = I$. This works also for unbounded selfadjoint variables which will correspond to scales of spectral projections $[-\infty, \infty] \ni t \mapsto E(T; (\-\infty, t])$, which are increasing, right continuous and $E(T; (-\infty, t])$ is equal to 0 if $t=-\infty$ and equal to $I$ if $t= \infty$. There is an additional condition at $+\infty$, $\lim_{t\to +\infty} E(T; (-\infty, t]) = I$, that is, continuity at +$\infty$.

A noncommutative random variable $a$ that is given by such a  scale has distribution function $$F_a(t) = \langle E(a; (-\infty, t])\xi, \xi \rangle \hspace{.1cm}, \hspace{.1cm} t\in \mathbb{R}$$
and its distribution is the probability measure $\mu_a$ on $\mathbb{R}$ with this distribution function, that is, $\mu_a((-\infty, t]) = F_a(t)$. The spectral max $a\vee b$ of $a$ and $b$ is given by the scale $E(a\vee b; (-\infty, t]) = E(a; (-\infty, t])\wedge E(b; (-\infty, t])$ where for two hermitian projections $P, Q$ by $P\wedge Q$ we denote the orthogonal projection onto the intersection of their ranges
$$(P\wedge Q) (\mathcal{H}) = P(\mathcal{H})\wedge Q(\mathcal{H}). $$
Boolean independence of two families of bounded noncommutative random variables $(X_{\iota})_{\iota \in I}, (Y_j)_{j \in J}$ on some $(\mathcal{H}, \xi)$ can be described as follows. There exists $(X'_\iota)_{\iota \in I}$ on $(\mathcal{H}', \xi')$, and $(Y_j'')_{j\in J}$ on $(\mathcal{H}'', \xi'')$, with the same noncommutative moments with respect to $\xi'$ and $\xi''$ respectively, such that if we consider $(\mathcal{H}''', \xi''')$, where $\mathcal{H}'''= (\mathcal{H}'\ominus \mathbb{C}\xi') \oplus (\mathcal{H}''\ominus \mathbb{C}\xi'') \oplus \mathbb{C}\xi'''$, and identifying isometries $$V': \mathcal{H}'\to \mathcal{H}''',  V'': \mathcal{H}''\to \mathcal{H}''',$$ so that $V'\restriction (\mathcal{H}' \ominus \mathbb{C}\xi')$ and $V''\restriction (\mathcal{H}''\ominus \mathbb{C}\xi'')$ are the identity in the respective space, while $V'\xi'= V''\xi''= \xi'''$. Then, the joint distribution of $(X_\iota, Y_j, \iota\in I, j \in J)$ on $(\mathcal{H}, \xi)$ is the same as the joint distribution of $(\tilde{X_\iota}, \tilde{Y_j}, \iota \in I, j \in J )$ on $(\mathcal{H}''', \xi''')$, where $\tilde{X_\iota} = V'X_\iota' V'^*$ and $\tilde{Y_j} = V''X_j'' V''^*$. One feature of this construction is that if we construct Boolean independent algebras on $(\mathcal{H}''', \xi''')$ from $\mathcal{A}$ on $(\mathcal{H}', \xi')$ and $\mathcal{B}$ on $(\mathcal{H}'', \xi'')$, then, $V'\mathcal{A}V'^*$ and $V''\mathcal{B}V''^*$ do not contain the identity operator on $\mathcal{H}'''$, even if $\mathcal{A} \ni I_{\mathcal{H}'}$, $\mathcal{B} \ni I_{\mathcal{H}''}$. The same works for unbounded noncommutative random variables by using their spectral scales instead of the operators, but it must be noted that spectral scales from $\mathcal{H}', \mathcal{H}''$ to $\mathcal{H}'''$ do not transform by simply putting the $\sim$ on the projections. Actually we have the following:
\begin{itemize}
\item If $t < 0$ then
$$E(\tilde{X'}, (-\infty, t]) = V'E(X'; (-\infty, t]) V'^*.$$
\item While if $t\geq 0$ then
$$E(\tilde{X'}; (-\infty, t]) = V' E(X'; (-\infty, t])V'^*+P_{\mathcal{H}''\ominus \mathbb{C}\xi'''}.$$
\end{itemize}
Similar formulae hold for the $\tilde{Y''}$. Clearly, if $X' \geq 0$ then the formulae are uniform. Also if $P', P''$ are projections on $\mathcal{H}', \mathcal{H}''$ then $\tilde{P'}\wedge \tilde{P''} \leq P_{\mathbb{C}\xi}$ so $\tilde{P'}\wedge \tilde{P''}$ is either 0 or $P_{\mathbb{C}\xi}$ and $\langle \tilde{P'} \wedge \tilde{P''}\xi, \xi \rangle \in \{0, 1\}$. On the other hand $(\tilde{P'}+P_{\mathcal{H}'\ominus \mathbb{C}\xi'}) \wedge (\tilde{P''}+P_{\mathcal{H}''\ominus \mathbb{C}\xi''})$ is no longer such a trivial quantity.

Also observe that the joint distribution of the $(\tilde{X_{\iota}'}, \tilde{Y_j''}, \iota\in I, j\in J)$ is the same for all choices of $X'_\iota$, $Y_j''$ replicating our initial joint distribution.

The conclusion of this discussion is that if we have two noncommutative random variables, replacing them with Boolean independent $\tilde{X}, \tilde{Y}$ ``copies in distribution" on another Hilbert space, the spectral max works well for nonnegative random variables $X\geq 0, Y \geq 0$ when we can choose $\tilde{X}\geq 0, \tilde{Y}\geq 0$.

In the following, we will use the Boolean additive convolution (\cite{Bercovici}, \cite{Speicher-Woroudi}). If $X, Y$ are bounded noncommutative random variables which are Boolean independent, then the distribution of $X+Y$ can be computed out of the distribution of $X$ and $Y$ by Boolean convolution. The formula for computing this is as follows. If $\mu$ is a probability measure on $\mathbb{R}$ with compact support, let $G_\mu(z) = \int\frac{d \mu(t)}{z-t}$  be its Cauchy transform, where $z\in \mathbb{C}\setminus \text{supp}(\mu)$, and let
$$K_\mu(z) = -\frac{1}{G_\mu(z)}+z. $$
Then the equality
$$K_{\mu_{X+Y}} = K_{\mu_X}+K_{\mu_Y},$$
allows to recover $G_{\mu_{X+Y}}$ from which $\mu_{X+Y}$ is obtained, by a standard procedure, using boundary values of the imaginary part from the upper half plane.

\section{The spectral max of Boolean independent projections and Boolean max convolution}

In view of the discussion in the preceding section, if $P$ is a projection, its distribution function is given by
$$F_P(t) = \begin{cases}0 & \text{if } t< 0 \\ p & \text{if } 0\leq t < 1 \\ 1 & \text{if } 1\leq t \end{cases}$$
where $p = \phi(I-P) = 1-\langle P\xi, \xi \rangle= \langle (I-P)\xi, \xi\rangle$. To find the formulae for Boolean max convolution we need to find these formulae for projections and this in turn can be done using additive Boolean convolution.

\begin{lemma}
\label{lemmaphisup}
Let $P, Q$ be Boolean independent projections on $(\mathcal{H}, \xi)$ so that $\phi(P) = 1-p$, $\phi(Q) = 1-q$. Then $\phi (P\vee Q) = 1-r$ where
$$r^{-1}-1 =(p^{-1}-1)+(q^{-1}-1).$$
\end{lemma}

\begin{proof}
We have $E(P\wedge Q; \{0\}) = E(P+Q; \{0\})$ and $\phi(E(P+Q); \{0\})$ will be computed using Boolean additive convolution. We have
$$G_P(z)= \frac{p}{z}+\frac{1-p}{z-1} = \frac{z-p}{z(z-1)}$$
$$K_P(z) = -\frac{z(z-1)}{z-p}+z = \frac{z(1-p)}{z-p}$$
and similar formulae for $Q$.
$$K_{P+Q}(z) = z \left( \frac{1-p}{z-p}+\frac{1-q}{z-q} \right).$$
Then we have
$$G_{P+Q}(z) = \frac{1}{z-K_{P+Q}(z)} = \frac{1}{z}\cdot \frac{1}{1-\frac{1-p}{z-p}-\frac{1-q}{z-q}}.$$
Hence
$$r= \lim_{z\to 0} z G_{P+Q}(z) = \lim_{z\to 0} \frac{1}{1-\frac{1-p}{z-p}-\frac{1-q}{z-q}} = \frac{1}{p^{-1}+q^{-1}-1}.$$
This implies
$$r^{-1}-1 = (p^{-1}-1)+(q^{-1}-1).$$
\end{proof}
The preceding lemma defines a semigroup structure on $[0, 1]$, the operation of which we shall denote by $\minbool$, the symbol which should correspond to Boolean min convolution, which we will  consider only as an operation on $[0,1]$. So if $x, y \in [0, 1]$ then $(x\minbool y)^{-1}-1 = (x^{-1}-1)+(y^{-1}-1)$. Since, when dealing with classical independence the semigroup structure at which one arrives is multiplication $\cdot$ on $[0, 1]$, it is clearly important to compare the two. As the next lemma shows the result of the comparison is quite pleasing.
\begin{lemma}
\label{lemmachiiso}
The semigroups $([0, 1], \minbool)$ and $([0, 1], \cdot)$ are isomorphic. The map $\chi: [0, 1] \to [0, 1]$ given by $$\chi(x) = \exp(1-x^{-1})$$ is an isomorphism which is also an order preserving homeomorphism. The inverse isomorphism, which is also order-preserving is given by $$\chi^{-1}(y) =(1-\log(y))^{-1}.$$
\end{lemma}

The proof of the previous lemma is straightforward and will be omitted.

From Lemma \ref{lemmaphisup} and the discussion in Section 2, the following definition is natural.

\begin{definition}
If $F_1, F_2$ are distribution functions on $[0, \infty)$ then their Boolean max-convolution is defined by
$$(F_1 \maxbool F_2)(t) = F_1(t) \minbool F_2(t).$$
\end{definition}

\begin{lemma}
\label{lemmamaxbooldist}
If $X\geq 0, Y \geq 0$ are Boolean independent noncommutative random variables on $(\mathcal{H}, \xi)$ then
$$F_{X \vee Y} (t) = F_X \maxbool F_Y(t). $$
The noncommutative random variables may be unbounded and in such case they are identified with their spectral scales.
\end{lemma}

\begin{proof}
Since $X\vee Y$ amounts to $E(X\vee Y; [0, t])= E(X; [0, t])\wedge E(Y; [0, t])$ where $t\geq 0$, $X\geq 0$, $Y\geq 0$ and $E(X; [0, t])$ , $E(Y; [0, t])$ the lemma follows immediately from the preceding results.
\end{proof}

\section{The transfer from classical to Boolean of max convolutions}

Let $\Delta_+$ denote the set of distribution functions for positive random variables, that is, functions $F: [0, \infty)\to [0,1]$ which are increasing, right continuous and which satisfy $\lim_{t\uparrow \infty} F(t)=1$. On $\Delta_+$ we consider the classical max convolution, which is just the multiplication $(F,G)\mapsto FG$ and the Boolean max convolution $(F, G) \mapsto F\maxbool G$ which for each $t\in [0, \infty)$ is given by $(F\maxbool G)(t) = F(t)\minbool G(t)$. In view of Lemma \ref{lemmachiiso}, the map $X: \Delta_+ \to \Delta_+$, where $X(F)= \chi \circ F$, or in other words, $X(F) = \exp(1-F^{-1})$, is an isomorphism. Hence, it is a bijection, preserves pointwise convergences and for every $F$ and $G$ it satisfies
$$X(F)\cdot X(G) = X(F\maxbool G).$$
The inverse map $X^{-1}: \Delta_+\to \Delta_+$ is given by $X^{-1}(F) = (1-\log(F))^{-1}$. This map has the property that $X^{-1}(F\cdot G) = X^{-1}(F) \maxbool X^{-1}(G)$.

In addition to these properties we also have that replacing $F(t)$ by $F(at)$ for some $a > 0$ corresponds to the same operation on $X(F)$ or $X^{-1}(F)$, that is
$$X(F(a \cdot )) = (X(F))(a\cdot )\hspace{.1cm} \text{ and } \hspace{.1cm} X^{-1}(F(a \cdot)) = (X^{-1}(F)) (a \cdot).$$
In view of the fact that this are the operations which we use to define max stable laws, whether classical or Boolean, we can use this correspondence to transfer classical results to Boolean results, the main restriction being that the spectral max on the max-convolution when we deal with Boolean independence will be restricted to nonnegative random variables, or equivalently, we will be restricted to distribution functions in $\Delta_+$.

The definition of max-stable laws for the Boolean setting will not include shifts in the limit process, because this would mean using the ``constant" noncommutative random variable $I$ on $(\mathcal{H},\xi)$ and we prefer to avoid the technical problems that arise from considering Boolean independent copies of it. The downside of this will be that we will have to keep in mind which shifted limit laws may arise.

\begin{definition}
A distribution function $F\in \Delta_+$ is a Boolean max-stable distribution function if for some $G\in \Delta_+$ there are constants $a_n > 0$, $n\in \mathbb{N}$ so that
$$(\underbrace{G\maxbool \cdots \maxbool G}_{n})(a_nt) \to F(t),$$
for all $t\geq 0$.
\end{definition}

The facts related to the transfer that were previously discussed yield the following result.

\begin{theorem}
A distribution $F\in \Delta_+$ is Boolean max-stable if and only if $X(F) (t) = \exp (-\lambda t^{-\alpha})$ for some $\lambda > 0$ and $\alpha > 0$.
\end{theorem}

\begin{proof}
Suppose $G^{\maxbool n} (a_n \cdot ) \to F(\cdot)$ and let $K = X(G)$ and $H= X(F)$. It follows that $K^n(a_n\cdot ) \to H(\cdot)$. Hence $H(\cdot)$ is classical max-stable and its support is in $[0, \infty)$. So $H(t) = \exp(-\lambda(t-\mu)^{-\alpha})$ if $x\geq \mu$ where $\mu \geq 0$, $\lambda > 0$, $\alpha > 0$ and $H\restriction_{[0, \mu]} = 0$ by the classical result of extreme value theory (see \cite{Resnick}, Prop. 0.3.). By the proof of Prop. 0.3. in \cite{Resnick} we must have $H^n(t) = H(n^{-\theta} t)$ for some $\theta \in \mathbb{R}$. This implies that $n(t-\mu)^{-\alpha} = (n^{-\theta} t -\mu)^{-\alpha}$, that is $n^{-\frac{1}{\alpha}}t-n^{-\frac{1}{\alpha}} \mu= n^{-\theta}t-\mu$ so that we must have $\mu=0$.

On the other hand, if $H(t) = \exp (-\lambda t^{-\alpha})$, $H(t) = \lim_{n\to \infty} K^n(a_nt)$ for some $K$ and $a_n$'s, for instance $K=H$ and $a_n = n^{-\frac{1}{\alpha}}$.
\end{proof}

Using $X^{-1}$ we get from this the Boolean max-stable laws explicitly.

\begin{corollary}
\label{Dagum}
$F\in \Delta_+$ is a Boolean max-stable law if and only if $$F(t) = (1+\lambda t^{-\alpha})^{-1}$$ where $\lambda > 0$ and $\alpha > 0$.
\end{corollary}

The distribution appearing in Corollary \ref{Dagum} is known as a Dagum distribution or log-logistic distribution. Among other applications, the Dagum distribution is used in models of wealth distribution.

The transfer between classical and Boolean max-stable laws, which we fortunately posses, also gives results on domains of attraction.

\begin{definition}
A distribution function $G\in \Delta_+$ is in the Boolean-max domain of attraction of $F\in \Delta_+$ if for some sequence of $a_n > 0$, $n\in \mathbb{N}$ we have $G^n(a_n \cdot) \to F(\cdot)$ as $n\to \infty$.
\end{definition}

The classical correspondents of the Dagum laws (viewed as Boolean max-stable laws) are Fr\'echet laws and their classical domains of attraction are known without using shifts (see Prop. 1. 11. in \cite{Resnick}, a classical result of Gnedenko). The condition for a distribution function $K \in \Delta_+$, to be in the domain of attraction of a Fr\'echet distribution, is that $1-K$ has to be regularly varying of exponent $-\alpha$, that is
$$\lim_{t\to +\infty} \frac{1-K(tx)}{1-K(t)} = x^{-\alpha},$$
for all $x > 0$. This gives immediately the following result.

\begin{corollary}
$G\in \Delta_+$ is in the Boolean domain of attraction of $F(t) = (1+t^{-\alpha})^{-1}$ if and only if $1-\exp(1-G^{-1})$ is regularly varying of exponent $-\alpha$.
\end{corollary}

The condition on $G$ in the corollary is early seen to be equivalent to $1-G$ being regularly varying of index $-\alpha$. Indeed, since
$$\lim_{t\to \infty} \left(1-(G(t))^{-1} \right) = \lim_{t\to \infty} \left( 1- (G(tx))^{-1} \right) =0 $$
and $\lim_{y\to 0} (\exp y-1) / y =1$, the condition on $G$ is equivalent to
$$\lim_{t\to \infty} \frac{1-(G(tx))^{-1}}{1-(G(t))^{-1}}= x^{-\alpha}.$$
Thus, like shown in \cite{Arous-Voiculescu} for free max-convolution, also for Boolean max-convolution, a Bercovici-Pata type coincidence of the domains of attraction with the classical domains of attractions takes place.

\begin{corollary}
A distribution function $F$ is in the max-Boolean domain of attraction of the Dagum distribution function $(1+t^{-\alpha})^{-1}$ if and only if $1-F$ is regulary varying of index $-\alpha$.
\end{corollary}


\section{Introduction}

In active machine learning, a learner is able to query an oracle in order to obtain information that is expected to improve performance.  Theoretical and empirical results show that active learning can speed acquisition for
a variety of learning tasks \citep[see][for a review]{Settles2012}.  Although impressive, most work on active machine learning has focused
on relatively simple types of information requests (most often a request for a supervised label).
In contrast, humans often learn by asking far richer questions which more directly target the
critical parameters in a learning task.  A human child might ask ``Do all dogs have long tails?" or
``What is the difference between cats and dogs?" \citep{Chouinard2007}.
A long term goal of artificial intelligence (AI) is to develop algorithms with a similar capacity to learn by asking rich questions. Our premise is that we can make progress toward this goal by better understanding human question asking abilities in computational terms~\citep[cf.][]{Gureckis2012}.

To that end, in this paper, we propose a new computational framework that explains how people construct rich and interesting queries within in a particular domain.
A key insight is to model questions as programs that, when executed on the state of a possible world, output an answer.
For example, a program corresponding to ``Does John prefer coffee to tea?'' would return \texttt{True} for all possible world states where this is the correct answer and \texttt{False} for all others.
Other questions may return different types of answers. For example ``How many sugars does John take in his coffee?'' would return a number 0, 1, 2, etc. depending on the world state. Thinking of questions as syntactically well-formed programs recasts the problem of question asking as one of \emph{program synthesis}. We show that this powerful formalism offers a new approach to modeling question asking in humans and may eventually enable more human-like question asking in machines.

We evaluate our model using a data set containing natural language questions asked by
human participants in an information-search game \citep{Rothe2016}. Given an ambiguous situation or context, our model can predict what questions human learners will ask by capturing constraints in how humans construct
semantically meaningful questions. The method successfully predicts the frequencies of human questions given a game context, and can also synthesize novel human-like questions that were not present in the training set.

\section{Related work}
Contemporary active learning algorithms can query for labels or causal interventions~\citep{Settles2012}, but they lack the representational capacity to consider a richer range of queries, including those expressed in natural language.  AI dialog systems are designed to ask questions, yet these systems are still far from achieving human-like question asking. Goal-directed dialog systems \citep{Young2013,Bordes2016}, applied to tasks such as booking a table at a restaurant, typically choose between a relatively small set of canned questions (e.g., ``How can I help you?'', ``What type of food are you looking for?''), with little genuine flexibility or creativity. Deep learning systems have also been developed for visual ``20 questions'' style tasks \citep{Strub2017}; although these models can produce new questions, the questions typically take a stereotyped form (``Is it a person?'', ``Is it a glove?'' etc.). More open-ended question asking can be achieved by non-goal-driven systems trained on large amounts of natural language dialog, such as the recent progress demonstrated in \citep{Serban2016a}. However, these approaches cannot capture intentional, goal-directed forms of human question asking.

Recent work has probed other aspects of question asking. The Visual Question Generation (VQG) data set \citep{Mostafazadeh2016} contains images paired with interesting, human-generated questions. For instance, an image of a car wreck might be paired with the question, ``What caused the accident?'' Deep neural networks, similar to those used for image captioning, are capable of producing these types of questions after extensive training~\citep{Mostafazadeh2016,Vijayakumar2016,Jain2017}. However, they require large datasets of images paired with questions, whereas people can ask intelligent questions in a novel scenario with no (or very limited) practice, as shown in our task below. Moreover, human question asking is robust to changes in task and goals, while state-of-the-art neural networks do not generalize flexibly in these ways.

\section{The question data set}
Our goal was to develop a model of context-sensitive, goal-directed question asking in humans, which falls outside the capabilities of the systems described above.  We focused our analysis on a data set we collected in \citep{Rothe2016}, which consists of 605 natural language questions asked by 40 human players to resolve an ambiguous game situation (similar to ``Battleship'').\footnote{\url{https://github.com/anselmrothe/question_dataset}}  Players were individually presented with a game board consisting of a 6$\times$6 grid of tiles.  The tiles were initially turned over but each could be flipped to reveal an underlying color.  The player's goal was to identify as quickly as possible the size, orientation, and position of ``ships" (i.e., objects composed of multiple adjacent tiles of the same color)~\citep{Gureckis2009}.
Every board had exactly three ships which were placed in non-overlapping but otherwise random locations.  The ships were identified by their color \emph{S = \{Blue, Red, Purple\}}.
All ships had a width of 1, a length of \emph{N = \{2, 3, 4\}} and orientation \emph{O = \{Horizontal, Vertical\}}.  Any tile that did not overlap with a ship displayed a null ``water'' color (light gray) when flipped.

After extensive instructions about the rules and purpose of the game and a number of practice rounds \citep[see][]{Rothe2016}, on each of 18 target contexts players were presented with a partly revealed game board (similar to Figure~\ref{fig:battleship}B and \ref{fig:battleship}C) that provided ambiguous information about the actual shape and location of the ships.  They were then given the chance to ask a natural-language question about the configuration.  The player's goal was to use this question asking opportunity to gain as much information as possible about the hidden game board configuration.  The only rules given to players about questions was that they must be answerable using one word (e.g., true/false, a number, a color, a coordinate like A1 or a row or column number) and no combination of questions was allowed.
The questions were recorded via an HTML text box in which people typed what they wanted to ask.
A good question for the context in Figure~\ref{fig:battleship}B is ``Do the purple and the red ship touch?'', while ``What is the color of tile A1?'' is not helpful because it can be inferred from the revealed game board and the rules of the game (ship sizes, etc.) that the answer is ``Water'' (see Figure~\ref{fig:results-questions} for additional example questions).

Each player completed 18 contexts where each presented a different underlying game board and partially revealed pattern.
Since the usefulness of asking a question depends on the context, the data set consists of 605 question-context pairs $\langle q, c \rangle$, with 26 to 39 questions per context.\footnote{Although each of the 40 players asked a question for each context, a small number of questions were excluded from the data set for being ambiguous or extremely difficult to address computationally \citep[see][]{Rothe2016}.}  The basic challenge for our active learning method is to predict which question $q$ a human will ask from the given context $c$ and the overall rules of the game.  This is a particularly challenging data set to model because of the the subtle differences between contexts that determine if a question is potentially useful along with the open-ended nature of human question asking.

\begin{figure}[tb]
	\centering
	\includegraphics[width=0.8\linewidth]{figures/battleship.pdf}
	\caption{The Battleship game used to obtain the question data set by Rothe et al. \citep{Rothe2016}. (A) The hidden positions of three ships \emph{S = \{Blue, Red, Purple\}} on a game board that players sought to identify. (B) After observing the partly revealed board, players were allowed to ask a natural language question. (C) The partly revealed board in context 4.}
	\label{fig:battleship}
\end{figure}

\section{A probabilistic model of question generation}
Here we describe the components of our probabilistic model of question generation. Section \ref{comp_and_comp} describes two key elements of our approach, compositionality and computability, as reflected in the choice to model questions as programs. Section \ref{q_grammar} describes a grammar that defines the space of allowable questions/programs. Section \ref{prob_gen} specifies a probabilistic generative model for sampling context-sensitive, relevant programs from this space. The remaining sections cover optimization, the program features, and alternative models (Sections \ref{opt}-\ref{alt_models}).

\subsection{Compositionality and computability} \label{comp_and_comp}
The analysis of the data set \cite{Rothe2016} revealed that many of the questions in the data set share similar concepts organized in different ways.
For example, the concept of ship size appeared in various ways across questions:
\begin{itemize}[noitemsep,nolistsep]
\item ``How long is the blue ship?''
\item ``Does the blue ship have 3 tiles?''
\item ``Are there any ships with 4 tiles?''
\item ``Is the blue ship less then 4 blocks?''
\item ``Are all 3 ships the same size?''
\item ``Does the red ship have more blocks than the blue ship?''
\end{itemize}
As a result, the first key element of modeling question generation was to recognize the \emph{compositionality} of these questions.
In other words, there are conceptual building blocks (predicates like \texttt{size(x)} and \texttt{plus(x,y)}) that can be put together to create the meaning of other questions (\texttt{plus(size(Red), size(Purple))}).
Combining meaningful parts to give meaning to larger expressions is a prominent approach in linguistics \citep{jacobson2014book}, and compositionality more generally has been an influential idea in cognitive science \citep{Fodor1988,Marcus2003,Lake2016}.

The second key element is the \emph{computability} of questions.
We propose that human questions are like programs that when executed on the state of a world output an answer.
For example, a program that when executed looks up the number of blue tiles on a hypothesized or imagined Battleship game board and returns said number corresponds to the question ``How long is the blue ship?''.  In this way, programs can be used to evaluate the potential for useful information from a question by executing the program over a set of possible or likely worlds and preferring questions that are informative for identifying the true world state. This approach to modeling questions is closely related to formalizing question meaning as a partition over possible worlds \citep{Groenendijk1984}, a notion used in previous studies in linguistics \citep{CraigeRoberts1996} and psychology \citep{Hawkins2015}. Machine systems for question answering have also fruitfully modeled questions as programs \citep{Wang2015,Johnson2017}, and computational work in cognitive science has modeled various kinds of concepts as programs \citep{Piantadosi2012,Goodman2014,LakeScience2015}. An important contribution of our work here is that it tackles \emph{question asking} and provides a method for \emph{generating} meaningful questions/programs from scratch.

\subsection{A grammar for producing questions} \label{q_grammar}
To capture both compositionality and computability, we represent questions in a simple programming language, based on lambda calculus and LISP.
Every unit of computation in that language is surrounded by parentheses, with the first element being a function and all following elements being arguments to that function (i.e., using prefix notation).
For instance, the question ``How long is the blue ship?'' would be represented by the small program \texttt{(size Blue)}.
More examples will be discussed below.
With this step we abstracted the question representation from the exact choice of words while maintaining its meaning.
As such the questions can be thought of as being represented in a ``language of thought'' \citep{Fodor1975}.

Programs in this language can be combined as in the example \texttt{(> (size Red) (size Blue))}, asking whether the red ship is larger than the blue ship.
To compute an answer, first the inner parentheses are evaluated, each returning a number corresponding to the number of red or blue tiles on the game board, respectively.
Then these numbers are used as arguments to the \texttt{>} function, which returns either True or False.

A final property of interest is the \emph{generativity} of questions, that is, the ability to construct novel expressions that are useful in a given context.
To have a system that can generate expressions in this language we designed a grammar that is context-free with a few exceptions, inspired by \citep{Piantadosi2012}.
The grammar consists of a set of rewrite rules, which are recursively applied to grow expressions.
An expression that cannot be further grown (because no rewrite rules are applicable) is guaranteed to be an interpretable program in our language.

To create a question, our grammar begins with an expression that contains the start symbol \texttt{A}
and then rewrites the symbols in the expression by applying appropriate grammatical rules until no symbol can be rewritten.
For example, by applying the rules A $\rightarrow$ N, N $\rightarrow$ (size S), and S $\rightarrow$ Red, we arrive at the expression \texttt{(size Red)}.
Table SI-1 (supplementary materials) shows the core rewrite rules of the grammar.
This set of rules is sufficient to represent all 605 questions in the human data set.

To enrich the expressiveness and conciseness of our language we added lambda expressions, mapping, and set operators (Table SI-2, supplementary material).
Their use can be seen in the question ``Are all ships the same size?'', which can be conveniently represented by \texttt{(= (map ($\lambda$ x (size x)) (set Blue Red Purple)))}.
During evaluation, \texttt{map} sequentially assigns each element from the \texttt{set} to \texttt{x} in the $\lambda$-part and ultimately returns a vector of the three ship sizes.
The three ship sizes are then compared by the \texttt{=} function.
Of course, the same question could also be represented as \texttt{(= (= (size Blue) (size Red)) (size Purple))}.

\subsection{Probabilistic generative model} \label{prob_gen}
An artificial agent using our grammar is able to express a wide range of questions.
To decide which question to ask, the agent needs a measure of question usefulness.
This is because not all syntactically well-formed programs are informative or useful.
For instance, the program \texttt{(> (size Blue) (size Blue))} representing the question ``Is the blue ship larger than itself?'' is syntactically coherent.
However, it is not a useful question to ask (and is unlikely to be asked by a human) because the answer will always be \texttt{False} (``no''), no matter the true size of the blue ship.

We propose a probabilistic generative model that aims to predict which questions people will ask and which not.
Parameters of the model can be fit to predict the frequency that humans ask particular questions in particular context in the data set by \citep{Rothe2016}.
Formally, fitting the generative model is a problem of density estimation in the space of question-like programs, where the space is defined by the grammar. We define the probability of question $x$ (i.e., the probability that question $x$ is asked) with a log-linear model.
First, the \emph{energy} of question $x$ is the weighted sum of question features
\begin{equation} \label{eq:energy}
\mathcal{E}(x) = \theta_1 f_1(x) + \theta_2 f_2(x) + ... + \theta_K f_K(x),
\end{equation}
where $\theta_k$ is the weight of feature $f_k$ of question $x$.
We will describe all features below.
Model variants will differ in the features they use.
Second, the energy is related to the probability by
\begin{equation} \label{eq:energy_prob}
p(x;\bm\theta) = \frac{
	\exp(-\mathcal{E}(x))
}{
	\sum_{x \in X} \exp(-\mathcal{E}(x))
}
= \frac{
	\exp(-\mathcal{E}(x))
}{
	Z
},
\end{equation}
where $\bm\theta$ is the vector of feature weights, highlighting the fact that the probability is dependent on a parameterization of these weights, $Z$ is the normalizing constant, and $X$ is the set of all possible questions that can be generated by the grammar in Tables SI-1 and SI-2 (up to a limit on question length).\footnote{We define $X$ to be the set of questions with 100 or fewer functions.} The normalizing constant needs to be approximated since $X$ is too large to enumerate.

\subsection{Optimization} \label{opt}
The objective is to find feature weights that maximize the likelihood of asking the human-produced questions. Thus, we want to optimize
\begin{equation}
\operatorname*{arg\,max}_{\bm\theta} \,
\sum_{i = 1}^{N} \text{log}\,p(d^{(i)}; \bm\theta),
\end{equation}
where $D = \{d^{(1)},...,d^{(N)}\}$ are the questions (translated into programs) in the human data set.
To optimize via gradient ascent, we need the gradient of the log-likelihood with respect to each $\theta_k$, which is given by
\begin{equation}
\label{eq:gradient}
\frac{\partial \text{log}\,p(D;\bm\theta)}{\partial \theta_k}= N \, \mathbb{E}_{x \sim D}[f_k(x)] - N \, \mathbb{E}_{x \sim P_\theta}[f_k(x)].
\end{equation}
The term $\mathbb{E}_{x \sim D}[f_k(x)] = \frac{1}{N}\sum_{i=1}^{N}f_k(d^{(i)})$ is the expected (average) feature values given the empirical set of human questions.
The term $\mathbb{E}_{x \sim P_\theta}[f_k(x)] = \sum_{x \in X} f_k(x) p(x;\bm\theta)$ is the expected feature values given the model.
Thus, when the gradient is zero, the model has perfectly matched the data in terms of the average values of the features.

Computing the exact expected feature values from the model is intractable, since there is a very large number of possible questions (as with the normalizing constant in Equation~\ref{eq:energy_prob}).
We use importance sampling to approximate this expectation. To create a proposal distribution, denoted as $q(x)$, we use the question grammar as a probabilistic context free grammar with uniform distributions for choosing the re-write rules.

The details of optimization are as follows. First, a large set of 150,000 questions is sampled in order to approximate the gradient at each step via importance sampling.\footnote{We had to remove the rule L $\rightarrow$ (draw C) from the grammar and the corresponding 14 questions from the data set that asked for a demonstration of a colored tile. Although it is straightforward to represent those questions with this rule, the probabilistic nature of \texttt{draw} led to exponentially complex computations of the set of possible-world answers.} Second, to run the procedure for a given model and training set, we ran 100,000 iterations of gradient ascent at a learning rate of 0.1. Last, for the purpose of evaluating the model (computing log-likelihood), the importance sampler is also used to approximate the normalizing constant in Eq. \ref{eq:energy_prob} via the estimator $Z \approx \mathbb{E}_{x\sim q}[\frac{p(x;\bm\theta)}{q(x)}]$.

\subsection{Question features} \label{features}
We now turn to describe the question features we considered (cf. Equation~\ref{eq:energy}), namely two features for informativeness, one for length, and four for the answer type.

\textbf{Informativeness.} Perhaps the most important feature is a question's informativeness, which we model through a combination of Bayesian belief updating and Expected Information Gain (EIG). To compute informativeness, our agent needs to represent several components: A belief about the current world state, a way to update its belief once it receives an answer, and a sense of all possible answers to the question.\footnote{We assume here that the agent's goal is to accurately identify the current world state. In a more general setting, the agent would require a cost function that defines the helpfulness of an answer as a reduced distance to the goal.} In the Battleship game, an agent must identify a single hypothesis $h$ (i.e., a hidden game board configuration) in the space of possible configurations $H$ (i.e., possible board games). The agent can ask a question $x$ and receive the answer $d$, updating its hypothesis space by applying Bayes' rule, $p(h|d;x) \propto p(d|h;x)p(h)$. The prior $p(h)$ is specified first by a uniform choice over the ship sizes, and second by a uniform choice over all possible configurations given those sizes. The likelihood  $p(d|h;x) \propto 1$ if $d$ is a valid output of the question program $x$ when executed on $h$, and zero otherwise.

The Expected Information Gain (EIG) value of a question $x$ is the expected reduction in uncertainty about the true hypothesis $h$, averaged across all possible answers $A_x$ of the question
\begin{equation}
\mathit{EIG}(x) = \sum_{d \in A_x}  p(d;x) \Big[ I[p(h)] - I[p(h|d;x)] \Big],
\end{equation}
\noindent
where $I[\cdot]$ is the Shannon entropy. Complete details about the Bayesian ideal observer follow the  approach we used in~\citep{Rothe2016}.  Figure~\ref{fig:results-questions} shows the EIG scores for the top two human questions for selected contexts.

\begin{figure}[tb]
	\centering
	\includegraphics[width=1\linewidth]{figures/freq_vs_energy_m1.pdf}
	\caption{Out-of-sample model predictions regarding the frequency of asking a particular question. The y-axis shows the empirical question frequency, and x-axis shows the model's energy for the question (Eq. \ref{eq:energy}, based on the full model). The rank correlation $\rho$ is shown for each context.}
	\label{fig:freq_vs_energy_loglik}
\end{figure}

In addition to feature $f_\text{EIG}(x) = \text{EIG}(x)$, we added a second feature $f_\text{EIG=0}(x)$, which is 1 if EIG is zero and 0 otherwise, to provide an offset to the linear EIG feature.
Note that the EIG value of a question always depends on the game context.
The remaining features described below are independent of the context.

\textbf{Complexity.} Purely maximizing EIG often favors long and complicated programs (e.g., polynomial questions such as \texttt{size(Red)+10*size(Blue)+100*size(Purple)+...}).
Although a machine would not have a problem with answering such questions, it poses a problem for a human answerer. Generally speaking, people prefer concise questions and the rather short questions in the data set reflect this. The probabilistic context free grammar provides a measure of complexity that favors shorter programs, and we use the log probability under the grammar $f_\text{comp}(x) = -\log q(x)$ as the complexity feature.

\textbf{Answer type.} We added four features for the answer types Boolean, Number, Color, and Location. Each question program belongs to exactly one of these answer types (see Table SI-1).
The type Orientation was subsumed in Boolean, with \texttt{Horizontal} as \texttt{True} and \texttt{Vertical} as \texttt{False}. This allows the model to capture differences in the base rates of question types (e.g., if people prefer true/false questions over other types).

\textbf{Relevance}. Finally, we added one auxiliary feature to deal with the fact that the grammar can produce syntactically coherent programs that have no reference to the game board at all (thus are not really questions about the game; e.g., \texttt{(+ 1 1)}). The ``filter'' feature $f_\emptyset(x)$ marks questions that refer to the Battleship game board with a value of 1 (see the $^b$ marker in Table SI-1) and 0 otherwise.\footnote{The features $f_\emptyset(x)$ and $f_\text{EIG=0}(x)$ are not identical. Questions like \texttt{(size Blue)} do refer to the board but will have zero EIG if the size of the blue ship is already known.}

\subsection{Alternative models} \label{alt_models}
To evaluate which features are important for human-like question generation, we tested the full model that uses all features, as well as variants in which we respectively lesioned one key property.
The \emph{information-agnostic} model did not use $f_\text{EIG}(x)$ and $f_\text{EIG=0}(x)$ and thus ignored the informativeness of questions.
The \emph{complexity-agnostic} model ignored the complexity feature.
The \emph{type-agnostic} model ignored the answer type features.

\section{Results and Discussion}

\begin{wraptable}[12]{R}{0.41\textwidth}
	\centering
    \vspace{-12pt}
	\caption{Log likelihoods of model variants averaged across held out contexts.}
	\label{tbl:loglik_models}
	\vspace{1em}
	\begin{tabular}{lr}
		\toprule
		Model & LL\\
		\midrule
		Full & -1400.06\\
		Information-agnostic & -1464.65\\
		Complexity-agnostic & -22993.38\\
		Type-agnostic & -1419.26\\
		\bottomrule
	\end{tabular}
\end{wraptable}

The probabilistic model of question generation was evaluated in two main ways. First, it was tasked with predicting the distribution of questions people asked in novel scenarios, which we evaluate quantitatively. Second, it was tasked with generating genuinely novel questions that were not present in the data set, which we evaluate qualitatively. To make predictions, the different candidate models were fit to 15 contexts and asked to predict the remaining one (i.e., leave one out cross-validation).\footnote{For computational reasons we had to drop contexts~1 and~2, which had especially large hypothesis spaces. However, we made sure that the grammar was designed based on the full set of contexts (i.e., it could express all questions in the human question data set).} This results in 64 different model fits (i.e., 4 models $\times$ 16 fits).

First, we verify that compositionality is an essential ingredient in an account of human question asking. For any given context, about 15\% of the human questions did not appear in any of the other contexts. Any model that attempts to simply reuse/reweight past questions will be unable to account for this productivity (effectively achieving a log-likelihood of $-\infty$), at least not without a much larger training set of questions.  The grammar over programs provides one account of the productivity of the human behavior.

Second, we compared different models on their ability to quantitatively predict the distribution of human questions. Table~\ref{tbl:loglik_models} summarizes the model predictions based on the log-likelihood of the questions asked in the held-out contexts. The full model -- with learned features for informativeness, complexity, answer type, and relevance -- provides the best account of the data. In each case, lesioning its key components resulted in lower quality predictions. The complexity-agnostic model performed far worse than the others, highlighting the important role of complexity (as opposed to pure informativeness) in understanding which questions people choose to ask. The full model also outperformed the information-agnostic and type-agnostic models, suggesting that people also optimize for information gain and prefer certain question types (e.g., true/false questions are very common). Because the log-likelihood values are approximate, we bootstrapped the estimate of the normalizing constant $Z$ and compared the full model and each alternative. The full model's log-likelihood advantage over the complexity-agnostic model held in 100\% of the bootstrap samples, over the information-agnostic model in 81\% of samples, and over type-agnostic model in 88\%.

Third, we considered the overall match between the best-fit model and the human question frequencies.  Figure~\ref{fig:freq_vs_energy_loglik} shows the correlations between the energy values according to the held-out predictions of the full model (Eq. \ref{eq:energy}) and the frequencies of human questions (e.g., how often participants asked ``What is the size of the red ship?" in a particular context). The results show very strong agreement for some contexts along with more modest alignment for others, with an average Spearman's rank correlation coefficient of 0.64. In comparison, the information-agnostic model achieved 0.65, the complexity-agnostic model achieved -0.36, and the type-agnostic model achieved 0.55. One limitation is that the human data is sparse (many questions were only asked once), and thus correlations are limited as a measure of fit. However, there is, surprisingly, no correlation at all between question generation frequency and EIG alone \cite{Rothe2016}, again suggesting a key role of question complexity and the other features.

Last, the model was tasked with generating novel, ``human-like'' questions that were not part of the human data set. Figure~\ref{fig:results-questions} shows five novel questions that were sampled from the model, across four different game contexts. Questions were produced by taking five weighted samples from the set of programs produced in Section \ref{opt} for approximate inference, with weights determined by their energy (Eq. \ref{eq:energy_prob}). To ensure novelty, samples were rejected if they were equivalent to any human question in the training data set or to an already sampled question. Equivalence between any two questions was determined by the mutual information of their answer distributions (i.e., their partitions over possible hypotheses), and or if the programs differed only through their arguments (e.g. \texttt{(size Blue)} is equivalent to \texttt{(size Red)}). The generated questions in Figure~\ref{fig:results-questions} demonstrate that the model is capable of asking novel (and clever) human-like questions that are useful in their respective contexts. Interesting new questions that were not observed in the human data include ``Are all the ships horizontal?" (Context 7), ``What is the top left of all the ship tiles?" (Context 9), ``Are blue and purple ships touching and red and purple not touching (or vice versa)?" (Context 9), and ``What is the column of the top left of the tiles that have the color of the bottom right corner of the board?" (Context 15). The four contexts were selected to illustrate the creative range of the model, and the complete set of contexts is shown in the supplementary materials.

\section{Conclusions}
People use question asking as a cognitive tool to gain information about the world. Although people ask rich and interesting questions, most active learning algorithms make only focused requests for supervised labels. Here were formalize computational aspects of the rich and productive way that people inquire about the world. Our central hypothesis is that active machine learning concepts can be generalized to operate over a complex, compositional space of programs that are evaluated over possible worlds. To that end, this project represents a step toward more capable active learning machines.

There are also a number of limitations of our current approach.  First, our system operates on semantic representations rather than on natural language text directly, although it is possible that such a system can interface with recent tools in computational linguistics to bridge this gap \citep[e.g.,][]{Wang2015}. Second, some aspects of our grammar are specific to the Battleship domain. It is often said that some knowledge is needed to ask a good question, but critics of our approach will point out that the model begins with substantial domain knowledge and special purpose structures. On the other hand, many aspects of our grammar are domain general rather than domain specific, including very general functions and programming constructs such as logical connectives, set operations, arithmetic, and mapping. To extend this approach to new domains, it is unclear exactly how much new knowledge engineering will be needed, and how much can be preserved from the current architecture. Future work will bring additional clarity as we extend our approach to different domains.

From the perspective of computational cognitive science, our results show how people balance informativeness and complexity when producing semantically coherent questions. By formulating question asking as program generation, we provide the first predictive model to date of open-ended human question asking.

\section*{Acknowledgments}
We thank Chris Barker, Sam Bowman, Noah Goodman, and Doug Markant for feedback and advice. This research was supported by NSF grant BCS-1255538, the John Templeton Foundation “Varieties of Understanding” project, a John S. McDonnell Foundation Scholar Award to TMG, and the Moore-Sloan Data Science Environment at NYU.

\begin{figure*}[tb]
	\centering
	\includegraphics[width=0.98\linewidth]{figures/figure3questions_outline.pdf}
     \caption{Novel questions generated by the probabilistic model. Across four contexts, five model questions are displayed, next to the two most informative human questions for comparison. Model questions were sampled such that they are not equivalent to any in the training set. The natural language translations of the question programs are provided for interpretation. Questions with lower energy are more likely according to the model.}
	\label{fig:results-questions}
\end{figure*}

\clearpage

\bibliographystyle{abbrv}