\section{Что пишет Арнольд}

В брошюре 2002 года <<Что такое математика>>~\cite{arnold2002} Владимир Игоревич Арнольд пишет:

\begin{quotation}

Математическая строгость часто оказывается труднопреодолимым препятствием даже
и для хороших математиков.  Следующий пример заимствован из замечательной
классической книги Р.~Куранта и Г.~Роббинса <<Что такое математика?>> (недавно
переизданной на русском языке).

Речь идет о применении топологии.  Пусть на катящейся по горизонтальному
рельсовому пути платформе установлена перпендикулярно рельсам закрепленная
горизонтальная ось, над которой возвышается способный вращаться вокруг этой оси
<<перевернутый маятник>> (стержень).

Утверждается, что \emph{каков бы ни был заданный закон движения платформы \textup(в
течение промежутка времени от нуля до единицы\textup), начальное положение
\textup{<<}маятника\textup{>>} можно выбрать так, что он в конечный момент времени не
будет горизонтален} (Хасслер Уитни).

Авторы доказывают это так. Если исходное положение маятника~--- горизонтально
лежачее, вперед по ходу, то таким оно и останется.  Если же исходное
положение~--- горизонтально лежачее, но назад по ходу, то и это сохранится.

Рассмотрим теперь произвольное начальное положение.  Конечное положение
определяется начальным.  Эта непрерывная функция принимает оба значения
<<вперед>> и <<назад>>.  По теореме топологии она принимает и промежуточные
значения, что и требовалось доказать.

Некоторое время назад мне передали просьбу от проф.~Роббинса (Курант к тому
времени уже умер) постараться исправить это <<ошибочное доказательство>>.  Дело
в том, что никакой непрерывной функции <<конечное состояние при данном
начальном состоянии>> тут сразу не видно:  ее нужно еще точно определить
(с каким-то учетом влияния возможных ударов о платформу), и нужно \emph{доказать}
ее непрерывность.  Я~слышал, что американские математики, пытавшиеся всё это
сделать, написали (неизвестное мне) сочинение с ошибочными промежуточными
утверждениями и доказательствами, так что вопрос о <<маятнике>> и сегодня,
видимо,  остается открытым\footnote
{Дискуссия об этой задаче Х.~Уитни опубликована: B.~E.~Blank.
Book review: What is mathematics? /\!/ Notices of the Amer. Math.
Soc. 2001. Vol.~48, No.~11. P. 1325--1329;
L.~Gillman. Book review: What is mathematics? /\!/ Amer.~Math.~Monthly.
1998. Vol. 105,
No. 5. P.~485--488; J.~E.~Littlewood. Littlewood's miscellany.
Cambridge Univ. Press, 1986. P.~32--35.    (\emph{Примечание В.\,И.\,Арнольда}. Видимо, в последней ссылке Арнольд имеет в виду~\cite{littlewood1953}.)}.

\end{quotation}

Арнольд возвращается к этому вопросу в 2009 году в другой брошюре, <<Математическое понимание природы. Очерки удивительных физических явлений и их понимания математиками (с рисунками автора)>>~\cite{arnold2009}, где пишет:

\begin{quotation}

\emph{На горизонтальных рельсах стоит платформа, на которой укреплена перпендикулярно рельсам
горизонтальная ось вращения <<перевёрнутого маятника>>, который может свободно вращаться
в \textup(параллельной рельсам\textup) вертикальной плоскости. Платформа движется по закону
$x=f(t)$ \textup(где $f$~--- гладкая на отрезке $[0, T]$ функция времени\textup).}

\emph{Доказать, что существует такое начальное состояние маятника} $$\alpha(0)=\varphi,\quad \frac{d\alpha}{dt}\,(0)=0,$$
\emph{что он не упадёт на платформу за всё время~$T$ её движения.}

\begin{center}
\includegraphics[scale=.9]{19-1.eps}
\end{center}

\textbf{Решение (Куранта)}.  Если $\varphi=0$, то $\alpha(t)=0$ всегда, и~если $\varphi=\pi$,
то $\alpha(t)=\pi$ при всех~$t$.

Из непрерывной зависимости решения (гладкого) дифференциального уравнения от начального условия~$\varphi$
заключаем, по теореме о~промежуточном значении, что между начальными условиями
$\alpha(0)=0$ и~$\alpha(0)=\pi$ существует такое значение $\alpha(0)=\varphi$, что
$\alpha(t)$ при $0\le t \le T$ заключено строго между $0$~и~$\pi$, так что маятник не падает.
$$
\includegraphics[scale=.9]{19-2.eps}
$$

\textbf{Замечание}.
Многие возражали против этого (ошибочного) доказательства, так как, даже если бы была
определена непрерывная функция $\alpha(\mskip2mu\cdot\mskip2mu, T)$, начального положения~$\varphi$, из её отличия
от нуля и~$\pi$ при начальном условии ${\cdot}=\varphi$ не следует отличие угла~$\alpha$ от~$0$ и~от~$\pi$
во все промежуточные значения моменты времени, $0<t<T$.

Вероятно, можно было бы рассмотреть разумное обобщение рассуждений Куранта, в~котором значения функции
$\alpha (\varphi,\mskip-3mu t)$ определены естественным продолжением после моментов удара о~платформу
(где $\alpha(\varphi, t){=}0$ или~$\pi$). Но в~литературе такое обобщение отсутствует, и~строгое доказательство приведённой гипотезы Куранта неизвестно.

Различные возражения к~различным попыткам обосновать вывод
Куранта опубликовали  Дж.\,Литтлвуд и другие (например,
некоторые из <<контрпримеров>> к~одному из таких обоснований
оказались недействительными, если скорость $df/dt$ меньше
скорости света).

Но я~не видел разумного анализа этой задачи с~учётом ударов.

Описанная теорема была помещена Курантом в~замечательный
элементарный учебник: Курант и~Роббинс <<Что такое
математика?>>, со ссылкой на Уитни.

\end{quotation}

Попытки разобраться в этом деле (в связи с подготовкой переиздания книги Куранта и Роббинса) показали, что тут довольно забавная и запутанная история с участием известных математиков.

\section{Что написано у Куранта и Роббинса}

Первое издание книги <<Что такое математика?>> Куранта и Роббинса~\cite{courant-robbins} вышло на английском языке в 1941 году. В 1947 году вышел его русский перевод под редакцией В.\,Л.\,Гончарова, сделанный по первому и второму английским изданиям (1941 и 1943).

Действительно, обсуждаемая Арнольдом задача рассматривается в разделе VI.6.2  (2-е издание, с.~352; 3-е издание, с.~347). Авторы пишут (приводим текст по русским изданиям, которые в этой части практически не отличаются друг от друга, разве что небольшой отмеченной ниже стилистической правкой, несколькими запятыми и обозначением угла $\alpha$ на рисунке):

\begin{quotation}
$^*$ \textbf{2. Применение к одной механической проблеме.}
Мы закончим эту главу рассмотрением одной, на первый взгляд трудной, механической проблемы, которая, однако, решается очень просто посредством соображений, связанных с непрерывностью. (Проблема была предложена Г.~У\,и\,т\,н\,и.)

Предположим, что поезд на протяжении некоторого конечного промежутка времени проходит прямолинейный отрезок пути от станции $A$ до станции $B$. Вовсе не предполагается, что движение происходит с постоянной скоростью или с постоянным ускорением. Напротив, поезд может двигаться как угодно: с ускорениями, с замедлениями; не исключены даже мгновенные остановки или частично даже движение в обратном направлении, прежде чем в итоге поезд придет на станцию $B$. Но так или иначе движение поезда на протяжении всего временн\'oго промежутка считается известным заранее; другими словами, считается заданной функция $s=f(t)$, где $s$~--- расстояние поезда от станции $A$, а $t$~--- время, отсчитываемое от момента отправления поезда. К полу одного из вагонов прикреплен на шарнире тяжелый стержень, который без трения может вращаться вокруг оси, параллельной осям вагонов, вперед и назад --- от пола до пола. (Мы допускаем, что, прикоснувшись к полу, он в дальнейшем останется на нем лежать, если ему не случится <<подпрыгнуть>> снова.) [\eng{(If it does touch the floor, we assume that it remains on the floor henceforth; this will be the case if the rod does not bounce.)}\footnote{В английском тексте, как видим, явно указано, что стержень предполагается приклеивающимся к полу при контакте --- а не просто что он будет лежать на полу, <<если ему не случится подпрыгнуть>>.})]

Вопрос заключается в следующем: \emph{возможно ли в момент отхода поезда поместить стержень в такое начальное положение, т.\,е.~дать ему такой угол наклона, чтобы на протяжении всего пути он не прикоснулся к полу, будучи предоставлен воздействию движения поезда и силы собственной тяжести}?

На первый взгляд может показаться совершенно невероятным, чтобы при наперед определенной схеме движения поезда взаимодействие силы тяжести и сил реакции было способно обеспечить требуемое равновесие стержня при единственном условии --- надлежащем выборе начального положения. Но мы сейчас установим, что такое начальное положение всегда существует.

К счастью, доказательство не подразумевает точного знания законов механики. (Исходя из этих законов, решить задачу было бы чрезвычайно трудно.) Достаточно принять только одно допущение физического содержания: \emph{последующее движение стержня зависит непрерывно от его начального положения}; в частности, если при данном начальном положении стержень во время пути упадет на пол в одну из сторон, то при всяком начальном положении, достаточно мало отличающемся от данного, он не упадет на пол в противоположную сторону.

\begin{center}
\includegraphics[scale=1]{figure-175-old.eps}\\
Рис.~175. Проблема Уитни.
\end{center}

Обратим теперь внимание на то, что во всякий момент времени положение стержня характеризуется углом $\alpha$, который он делает с полом [1966 г.; в издании 2001 г. и позже: <<составляет с полом>>]. Углам $\alpha=0^\circ$ и $\alpha=180^\circ$ соответствуют два противоположных горизонтальных (лежачих) положения. Обозначим через $x$ значение угла $\alpha$ в начальном положении стержня. Доказательство нашего утверждения будет косвенное, в соответствии с чисто экзистенциальным характером самой проблемы. Допустим, что \emph{всегда},  т.\,е.~при любом начальном положении стержня, стержень непременно упадет или в одну, или в другую сторону, так что $\alpha$ примет значение или $0^\circ$, или $180^\circ$. Определим тогда функцию $f(x)$ согласно условию:  [1966 г.;  издании 2001 года <<определим тогда функцию $f(x)$ так:>>] $f(x)=+1$ или $-1$, смотря по тому, упадет ли стержень в сторону, соответствующую углу $\alpha=0^\circ$ или углу $\alpha=180^\circ$. Свойства функции $f(x)$ таковы: она задана в интервале $0\le x\le 180^\circ$, непрерывна в нем, и притом $f(0)=+1$, \,$f(180)=-1$. Отсюда, по теореме Больцано, следует, что при каком-то промежуточном значении $x$ ($0^\circ<x<180^\circ$) должно выполняться равенство $f(x)=0$. А это противоречит тому, что функция $f(x)$ может принимать только значения $+1$ и $-1$. Значит, приходится отвергнуть сделанное допущение, согласно которому стержень упадет на пол при каком угодно начальном его положении.

Совершенно ясно, что приведенное доказательство носит чисто теоретический характер, потому что не дает решительно никаких указаний на то, как определить искомое положение стержня. Вместе с тем, даже если бы такое положение и могло быть вычислено теоретически с абсолютной точностью, практически оно было бы бесполезно вследствие своей неустойчивости. Так, например, в предельном случае, если поезд неподвижен в течении всего <<путешествия>>, решение совершенно очевидно: $x=90^\circ$; но всякий, кто пытался уравновесить иголку в стоячем положении на гладкой горизонтальной поверхности, понимает, насколько это решение практически нереально. Тем не менее с математической точки зрения приведенное доказательство имеет неоспоримый интерес.

\end{quotation}

\section{Математические подробности}

Проявив занудство (возможно, с элементами бурбакизма), легко восполнить пробелы в изложении Куранта и Роббинса. Но сначала скажем подробнее, в чём состоят эти пробелы (используя базовые сведения об обыкновенных дифференциальных уравнениях).

Движение стержня описывается дифференциальным уравнением (одномерным, второго порядка). Неизвестной функцией является зависимость угла $\alpha$ от времени. Сила, действующая на стержень, складывается из силы инерции (связанной с движением поезда) и силы тяжести. Вместе с силами реакции стержня, позволяющими ему лишь вращаться вокруг оси, они определяют угловое ускорение стержня. Начальное условие говорит, что изначально стержень неподвижен (угловая скорость равна нулю), образуя угол $\alpha$ с горизонтом.

Теорема о непрерывной зависимости решения дифференциального уравнения от начальных условий гарантирует, что значение решения в конце пути поезда (как и в произвольный момент момент времени) является непрерывной функцией от начальных условий. Проблема, отмеченная Арнольдом, состоит в том, что прямо так сослаться на теорему нельзя. Если мы, следуя Куранту и Роббинсу, считаем, что после касания пола стержень <<прилипает>> к нему, то в этот момент дифференциальное уравнение уже не описывает процесс (и вообще ускорение бесконечно, а скорость имеет разрыв, когда стержень с ненулевой скоростью ударяется о пол). Можно убрать пол и рассмотреть движение на всей окружности возможных положений стержня. Тогда уравнение сохраняет силу всегда, но (как правильно отмечает Арнольд) из того, что в конце движения стержень вертикален (или находится в каком-то ином положении выше горизонтали), не следует, что он в процессе движения не опускался ниже горизонтали. Кто знает --- может быть, он даже сделал несколько оборотов, перед тем как вернуться в вертикальное положение.

Как восполнить эти пробелы? Будем, как и предлагалось, рассматривать уравнение на всей окружности (считая, что стержень не ударяется о пол, а может проделать целый оборот). Кроме того, мы можем считать, что задан закон движения платформы при всех $t\ge 0$ (некоторая гладкая функция), и достаточно доказать, что существует начальное условие, при котором решение на всей полуоси $t\ge 0$ остаётся в верхней полуплоскости (в интервале $\pm \pi/2$ от верхнего положения).  Здесь стоит отметить, что стандартные результаты про гладкое уравнение на компактном многообразии гарантируют, что при любом начальном условии решение продолжается на всю полупрямую $t\ge 0$.

Начальное положение в верхней полуплоскости (с нулевой скоростью) будем называть левым (правым), если исходящая из него траектория пересекает горизонтальную полуплоскость первый раз слева (соответственно справа).   Понятие <<первого раза>> определено корректно (если вообще есть пересечение с горизонтальной плоскостью): множество моментов горизонтального положения замкнуто, и среди них есть первый (точная нижняя грань этого множества ему принадлежит). Этот первый момент может быть либо левым, либо правым.  Получаем два множества $L$ и $R$ начальных положений.

Заметим, что оба множества $L$ и $R$ непусты. В самом деле, функция $f(t)$ в окрестности нуля имеет ограниченную вторую производную, и потому сила инерции, действующая на маятник, ограничена. Следовательно, если начальное положение маятника достаточно близко к горизонтальному, то силы инерции недостаточно, чтобы противодействовать гравитации, и маятник начнёт двигаться вниз и пересечёт горизонталь (с той стороны, где он находился изначально).

Осталось показать, что оба множества $L$ и $R$ открыты, и затем воспользоваться связностью интервала $(0,\pi)$. Почему, скажем, множество $L$ открыто? Пусть $\alpha_0$~--- некоторый элемент $L$,  и $\alpha(t)$~--- соответствующее решение. Пусть $\tau$~--- первый момент горизонтального положения, тогда $\alpha(\tau)=\pi$. На интервале $[0,\tau]$ расстояние от $\alpha(t)$ до другого горизонтального положения ($\alpha=0$) отделено от нуля, поэтому при всех достаточно близких начальных условиях по теореме о непрерывной зависимости (решения как функции от начального условия и момента времени) решение не попадает в правое горизонтальное положение на промежутке $[0,\tau]$. По той же теореме при достаточно близких к $\alpha_0$ начальных условиях решение будет близко к $\pi$ в момент времени $\tau$. Поскольку ускорение тележки ограничено в окрестности отрезка $[0,\tau]$ (и вообще на любом конечном отрезке), то отсюда следует, что при достаточно близких к $\alpha_0$ начальных условиях решение либо уже пересечёт горизонталь слева, либо окажется в таком положении, где это неминуемо. Поэтому эти близкие положения все лежат в $L$, что и требовалось доказать.

\section{Исторические подробности}

\subsection{Пересказ Литлвуда}

Книга Куранта и Роббинса вышла в 1941 году. В 1953 году выходит книга Литлвуда <<Математическая смесь>>~\cite{littlewood1953}, которая в 1962 году была опубликована по-русски в переводе В.\,И.\,Левина. Литлвуд упоминает задачу Уитни, ссылаясь на Куранта и Роббинса. Приведём соответствующий кусок в русском переводе (вполне соответствующем оригиналу):

\begin{quotation}
Стержень шарнирно прикреплён к полу железнодорожного вагона и предоставлен самому себе; тогда существует малая, но отличная от нуля, вероятность того, что он не упадет в течение двух недель: вероятность равна примерно $1:10^{10^5}$. (Поезд не предполагается <<идеальным>>: например, он отправляется со станции Кингс Кросс в 3.15, проходит через туннель, где он 5 минут стоит, а затем, после ряда дальнейших остановок, прибывает в Кембридж в 5.35. Я припоминаю, что мне сообщили, что гений, впервые задавший этот вопрос, не был в состоянии ответить на него.)  [I seem to remember being told that the genius who asked the original question was unable to answer it.] Доказательство имеется в КР [имеется в виду книга Куранта и Роббинса], с.~421--423 [в русском переводе указываются страницы по русскому изданию 1947 года, в английском оригинале Литтлвуд говорит о с.~319].

{\Large$*$} Иной способ доказательства (с разумной свободой интерпретации) состоит в следующем. Рассмотрим начальное положение стержня в относительном покое, составляющее угол $\theta$ с \emph{левым} горизонтальным положением. Пусть $S$ будет множество начальных $\theta$, при которых стержень рано или поздно упадет налево. Основной факт при очень слабых предположениях относительно обстоятельств путешествия и взаимосвязи поезда и стержня (нам нет необходимости детально устанавливать эти предположения) состоит в том, что \emph{множество $S$ открыто}. Пусть $\theta_0$ --- точная верхняя грань углов $\theta$ из $S$. Тогда $\theta_0$ не входит в $S$, и из начального положения $\theta_0$ стержень не упадет налево. Если же он упадет направо, то он сделает это и для всех $\theta$, несколько меньших $\theta_0$; однако это неверно, так как некоторые (в действительности все) из этих $\theta$ принадлежат $S$. Таким образом, из положения $\theta_0$ стержень никогда не упадет. А для некоторого, достаточно малого угла вокруг $\theta_0$ он не упадет в течение двух недель.

Поучительно рассмотреть, почему из этого рассуждения не вытекает, что стержень, соответствующим образом установленный в начальный момент, не будет отклоняться, скажем, более чем на $0{,}5^\circ$ от исходного положения. {\Large$*$}

Это рассуждение моментально убеждает математика. Из всех возможных вариантов избранный мною представляется наиболее подходящим для объяснения любителю. [This argument is instantly convincing to the mathematician. Of possible variants the one chosen seems best suited to be interpreted to the amateur.]

 [Далее Литлвуд предлагает вариант такого более подробного истолкования для <<любителей>>. Для начала он обсуждает понятие точной верхней грани, мы пропускаем этот кусок.]

Предположим, что в начальный момент стержень находится в состоянии относительного покоя и образует угол $\theta$ с \emph{левой} горизонталью; назовем это <<начальным положением $\theta$>>. Рассмотрим множество $S$ начальных положений $\theta$, из которых стержень рано или поздно упадет налево. Если это происходит с ним при каком-нибудь $\theta$, то то же самое будет \emph{иметь место для для всех достаточно близких по обе стороны начальных положений}; любое положение $\theta$, принадлежащее к $S$, находится, следовательно, внутри целого сектора значений $\theta$, принадлежащих к $S$ (на математическом языке: <<$S$ открыто>>). Этот интуитивный факт, на котором все основано, имеет место при весьма общих условиях, уточнять которые нет необходимости. [This intuitive fact, on which everything turns, depends on very slight assumptions, and we need not try ro state them in detail.]

Пусть $\theta_0$ будет \emph{т.\,в.\,г.} [точной верхней гранью] множества~$S$. Тогда $\theta_0$ не будет элементом $S$, так как в противном случае значения $\theta$, находящиеся справа от $\theta_0$ и достаточно близкие к нему, также принадлежали бы к $S$, и $\theta_0$ не могло бы быть \emph{в.\,г.} [верхней гранью]  множества~$S$. Итак, стержень при начальном положении $\theta_0$ не упадет налево. Но, с другой стороны, если он упадет направо, то он будет падать направо и при \emph{всех} достаточно близких начальных положениях $\theta$ слева от $\theta_0$ (принцип <<открытости>>), так что никакое из этих начальных положений не может быть элементом $S$; но это означает, что $\theta_0$ может быть сдвинуто влево, оставаясь при этом \emph{в.\,г.}~$S$, что противоречит свойству (2) \emph{т.\,в.\,г.} [минимальности]. Следовательно, из исходного положения $\theta_0$ стержень никогда не упадет. А из достаточно малого сектора вокруг $\theta_0$ он не упадет в течении двух недель.

Аналогичный результат верен и при замене обычного шарнира сферическим (позволяющим стержню наклоняться во все стороны). Но в этом случае нам пришлось бы ссылаться уже на значительно более сложную <<теорему о неподвижной точке>> (КР, стр.~335) [в оригинале ссылка на с.~321 английского издания].

\end{quotation}

Ни здесь, ни в другом месте книги Литлвуд не объясняет, каким образом получена оценка длины интервала углов, позволяющего стержню не падать в течение двух недель ($1: 10^{10^5}$). Также не очень понятно, на какого гения намекает Литлвуд
(Уитни?). Можно ещё отметить, что рассуждение (начиная с утверждения об открытости, принятого без доказательства), проведено весьма отчётливо и тут трудно к чему-нибудь придраться даже педанту.

\subsection{Изменение текста Курантом и Роббинсом}

Дополнительную путаницу в истории вопроса создаёт различие в текстах разных изданий Куранта и Роббинса~\cite{courant-robbins}. Мы уже приводили русский перевод, который во всех изданиях следует первому английскому изданию 1941 года. И хотя в английских изданиях текст про задачу Уитни был позже изменён (в издании 1948 года он уже другой), русский текст в последующих переизданиях остался практически неизменным~--- несмотря на заверения А.\,Н.\,Колмогорова в предисловии ко второму русскому изданию, что перевод <<был выправлен и пополнен по последнему английскому (1948) и немецкому (1962) изданиям>>. Тот же самый изменённый текст был вопроизведён в переиздании 1996 года с участием Стьюарта (о комментариях которого смотри ниже). Приводим для справки этот изменённый текст (потому что часть критики Арнольда и других авторов может относиться к нему).

\begin{quotation}

[Формулировка задачи и комментарии к ней оставлены почти без изменений. Начиная с абзаца <<К счастью\ldots>>, изменённый текст выглядит так:] \eng{Paradoxical as this assertion might seem at first sight, it can be proved easily once one concentrates on its essentially topological character.}

\eng{No detailed knowlegde of the laws of dynamics is needed; only the following simple assumption of the physical nature need be granted: \emph{The motion of the rod depends continuously on its initial position}. Let us characterize the initial position of the rod by the initial angle $x$ which it makes with the floor, and by $y$ the angle which the rod makes with the floor at the end of the journey, when the train reaches the point $B$. If the rod has fallen to the floor we have either $y=0$ or $y=\pi$. For a given initial position $x$ the end position $y$ is, according to our assumption, uniquely determined as a function $y=g(x)$ which is continuous and has the values $y=0$ for $x=0$ and $y=\pi$ for $x=\pi$ (the latter assertion simply expressing that the rod will remain flat on the floor if it starts in this position). Now we recall that $g(x)$, as a continuous function in the interval $0\le x\le \pi$, assumes all the values $y$, e.g. for the value $y=\pi/2$, there exists a specific value of $x$ such that $g(x)=y$; in particular, there exists an initial position for which the end position of the rod at $B$ is perpendicular to the floor.  (Note: in this argument it should not be forgotten that the motion of the train is fixed once for all.)}

\eng{Of course, the reasoning is entirely theoretical. If the journey is of long duration or if the train schedule, expressed by $s=f(t)$, is very erratic, then the range of the initial positions $x$ for which the end position $g(x)$ differs from $0$ or $\pi$ will be exceedingly small, as is known to anyone who has tried to balance a needle upright on a plate for an appreciable time. Still, our reasoning should be of value even to a practical mind inasmuch as it shows how qualitative results in dynamics may be obtained by simple arguments without technical manipulation.}

\end{quotation}

Разница с первоначальным вариантом изложения (см. русский перевод выше) состоит в том, что раньше предлагалось предположить, что стержень всегда падает и рассмотреть функцию с двумя значениями на всех начальных положениях. Непрерывность этой функции означает, что прообразы этих значений открыты, то есть множество тех начальных углов, когда стержень падает влево (или вправо), открыто. Теперь же утверждается безо всяких предположений, что конечное положение стержня (при движении с прилипанием к горизонтали) будет непрерывно зависеть от начальных условий. Это тоже верно, но требует чуть более сложного обоснования (ссылки на теорему о непрерывной зависимости от начального условия тут мало, потому что рассматриваемый вариант движения с прилипанием не соответствует никакому дифференциальному уравнению). Это обоснование также опирается на отмеченный нами выше ключевой факт: попадание в малую зону у горизонтали уже гарантирует скорое попадание на горизонталь (и прилипание), и включает в себя доказательство открытости зон прилипания как часть.

Мне не удалось найти точный момент замены текста (и уж тем более никаких объяснений мотивов такого <<удачного ухудшения>>, если воспользоваться выражением Литлвуда из~\cite{littlewood1953}). Дополнительную путаницу создаёт и то обстоятельство, что перепечатка текста Куранта и Роббинса про задачу Уитни (с заголовком <<\eng{The lever of Mahomet}>> --- видимо, с намёком на одноимённый гроб) в хрестоматии Ньюмана~\cite{courant-robbins-newman} в 1960 году, много позже издания 1948 года с новым текстом, следует оригинальному изданию 1941 года (почему --- не знаю).

\subsection{Разъяснения Бромана}

В 1957 году на 13 Скандинавском математическом конгрессе в Хельсинки Арне Броман сделал доклад, опубликованный в 1958 году~\cite{broman1958}. В этой публикации, со ссылкой на Куранта и Роббинса, формулируется задача Уитни (с требованием доказать, что существует начальное положение, при котором в конце пути стержень будет вертикальным). Приводится решение по Куранту и Роббинсу (в изменённом варианте, с непрерывной зависимостью от начального положения без предположения об обязательном падении).

Далее автор отмечает, что
<<\eng{However, the physical assumption in the solution of Courant -- Robbins seems a bit hazardous}>>, и делает сноску к этому предложению:  <<\eng{In saying this, we do not intend to criticize the interesting and well-written book by Courant and Robbins. They have included the problem to get an application of the mentioned theorem on continuous functions.}>> После этого автор переходит к обоснованию непрерывности этой самой функции. Сначала он удаляет ограничения на горизонтали:  <<\eng{We now remove for a while the stops for the rod in the horizontal position so that the rod can revolve all around the point $O$. Then the final angle $\beta$, considered as a function $\beta=\beta(\alpha)$ of the initial angle $\alpha$, is obviously defined and continuous for all real~$\alpha$.}>> Таким образом, можно утверждать, что найдётся начальное условие, при котором свободный от горизонтальных ограничений стержень окажется по окончании пути в верхнем положении. Но (как и указывал Арнольд), этого мало --- нужно дополнительно, чтобы стержень всегда оставался в верхней полуплоскости.

Чтобы восполнить этот пробел в рассуждении, Броман замечает, что первое же приближение к горизонтали на достаточно малое расстояние влечёт её пересечение, и рассматривает множество начальных условий, при которых такое пересечение имеет место слева или не имеет места вовсе, но конечное положение находится слева от вертикали. Он устанавливает, что это множество открыто (опираясь на сделанное замечание), и отсюда выводит требуемый результат.

Наконец, в последнем разделе своей статьи он замечает, что если поезд после приезда в  $B$ навсегда останавливается, то существует такое начальное положение, при котором стержень никогда не коснётся пола (это замечание было уже у Куранта и Роббинса в качестве упражнения).

В качестве примечания 9 Броман приводит немного другое рассуждение (со ссылкой на М.\,Тидемана): в нём дифференциальное уравнение модифицируется так, чтобы стержень, коснувшись пола, продолжал двигаться вниз и не мог сделать полного оборота, но с сохранением достаточной гладкости для применения теоремы о непрерывной зависимости от начальных условий.

\subsection{Критика Постона и её пересказ Стьюартом}

С 1958 года и до 1976 года казалось, что недоразумения с задачей Уитни исчерпаны, и те, кого (вопреки надежде Литлвуда) исходное рассуждение не убеждает, могут обратиться к разъяснениям Бромана. По крайней мере, я не видел никаких публикаций в этот период, авторы которых требовали бы дополнительных разъяснений или выдвигали возражения.

Однако в 1976 году появилась статья Постона в малодоступном издании~\cite{poston1976}. Мне не удалось добыть её текста, но о её содержании можно судить по краткому пересказу самого Постона в его другой статье (см. примечание к описанию статьи~\cite{poston1976}): <<\eng{Certainly there are instances where continuous systems beget discontinuity --- indeed, an interesting case where Courant and Robbins [4] appeal inappropriately to the Intermediate Value Theorem is analysed in [16]}>> (где [16] --- эта самая малодоступная заметка~\cite{poston1976}), и по подробному пересказу в издании Куранта и Роббинса 1996 года~\cite{courant-robbins-stewart}. Это издание вышло с изменениями Стьюарта --- точнее сказать, не с изменениями (поскольку основная часть книги была воспроизведена по предыдущим изданиям), а с дополнениями. Одно из этих дополнений (с.~505 и далее) посвящено задаче Уитни. Стьюарт пишет:

\begin{quotation}
\eng{There is one place where arguably Courant and Robbins made a mistake, although by adding further conditions is it possible to save their argument. Paradoxically, the flaw in their proof is most easily detected if we employ the topological approach to dynamics that their argument was intended to advocate.}

[Далее следует пересказ условия задачи Уитни и решения, опирающегося (после изменений, о которых мы говорили) на непрерывную зависимость конечного положения от начального условия. После этого Стьюарт пишет:]

\eng{The difficulty is that the continuity assumption made in the above discussion is arguably not justified. The problem is not the intricacies of Newton's laws of motion, but those ``absorbing boundary conditions'': if the rod hits the floor, then it stays there. In order to see why the boundary conditions cause trouble, we introduce a topological picture of the possible motions of the system. This approach, known as as \emph{phase portrait}, goes back to Poincar\'e. The idea is to draw a kind of space-time diagram of the motion, not just for a single initial position of the rod, but for many different positions---in principle, all of them. The position of the rod is an angle between $0^\circ$ and $360^\circ$, and we can graph this in the horizontal direction (see Fig.~294). Let time run in the vertical direction. Note that the left and right hand edges of this picture should be identified because $0^\circ=360^\circ$: conceptually, the rectangle is rolled into a cylinder.
\begin{center}
\includegraphics[width=0.7\textwidth]{courant-robbins1996pict.pdf}\\
Fig.~294. Possible history of the moving rod for different initial conditions. (a)~Without boundary conditions. (b)~What happens when the boundary conditions are imposed.
\end{center}
}

\eng{Now, the path is space and time of the angle that determines the position of the rod forms some curve that runs up the cylinder --- what Albert Einstein called a ``world-line''. Different initial angles lead to different curves. The laws of dynamics show that these curves vary continuously---provided the boundary conditions are not enforced. Without these conditions the rod is free to turn a full $360^\circ$---there is no floor to prevent it turning all the way round. A possible history is shown in Fig.~294a, and here the final position does depend continuously upon the initial position.}

\eng{However, when the absorbing boundary conditions are put back (Fig.~294b), the final position need \emph{not} depend continuously on the initial one. Curves that just graze the left-hand boundary can swing all the way over to the right. Indeed, in this particular picture \emph{all} initial conditions end up on the floor: contrary to what Courant and Robbins claim, there is no choice that keeps the rod off the floor throughout the motion.}

\eng{This error in Courant and Robbins' reasoning was first pointed out by Tim Poston in 1976, but it is still not widely known. The continuity assumption can be resuscitated by imposing extra con[s]traints on the motion, for example a perfectly level track, no springs on the train, and so forth. But it seems more instructive, as an exercise in the application of topology to dynamics, to understand why the absorbing boundary conditions destroy continuity.}

\end{quotation}

С математической точки зрения Стьюарт пишет правильно: действительно, добавление поглощающих границ нарушает непрерывность, и действительно в предположении о том, что поезд движется горизонтально и не имеет рессор, непрерывность может быть обоснована.  Примерно такой же (но чуть менее подробный) текст можно найти в книге Стьюарта~\cite{stewart1989}, где он, однако, не упоминает о том, что в предположениях Куранта и Роббинса непрерывность несложно доказать, а говорит лишь, что <<\eng{the continuity assumption is not justified}>> (и приводит тот же рисунок траекторий без граничных условий и с ними).

Однако и то верно, что у Куранта и Роббинса эти дополнительные предположения были сделаны, а утверждение о непрерывности (для этого, а не более общего случая) было сформулировано без обоснования (и это было явно указано). То, что для негоризонтального пола (поглощающих границ под произвольным углом) утверждение будет неверно, отмечал ещё Литлвуд (абзац <<Поучительно рассмотреть>>  в приведённой выше цитате). В такой ситуации говорить об <<ошибке в рассуждении Куранта и Роббинса>>, как это делают Стьюарт и Постон (см. его цитату в~\cite{gillman1998}), кажется несколько чрезмерным.

Похоже, что впоследствии и сам Стьюарт пришёл к такому заключению. По крайней мере, такое впечатление создаётся при чтении отчёта о его лекции в 2009 году~\cite{stewart2009}:

\begin{quote}
\eng{Professor Stewart’s lecture, entitled \emph{The Strange Case of the Courant -- Robbins Train}, centered around a problem that he said had been bothering him for 40 years. It concerns a train and how its motion, and the influence of gravity, would affect a rod pivoted on the floor. In their 1941 book \emph{What is Mathematics?} Richard Courant and Herbert Robbins asked if it were possible to place the rod in such a position that, if it is released when the train starts, it will not fall to the floor during the entire journey. Although this appears to be a complex problem in mechanics, they asserted that the answer is a simple yes and avoided the complexities of mechanics using a simple application of the concept of continuity. With his trademark geniality and witty presentation skills, Professor Stewart carefully guided the audience through his concern: does the concept of continuity actually apply in this situation? By considering boundary conditions and floors of railway carriages which slanted towards the middle, he showed that in fact Courant and Robbins were correct to assume continuity in the particular case where the carriage has a flat floor although the proof of continuity actually does require a careful analysis of the underlying mechanics. But this is not always the case for other shaped floors.}
\end{quote}

\subsection{Рецензии на новое издание}

Выход нового издания книги Куранта и Роббинса с дополнениями Стьюарта был замечен  рецензентами. В 1998 году в \emph{Americal Mathematical Monthly} была опубликована рецензия Леонарда Гиллмана~\cite{gillman1998}. В ней приводится формулировка задачи и излагаются возражения Стьюарта со ссылкой на Постона. (Гиллману, в отличие от меня, удалось получить текст статьи Постона~\cite{poston1976} --- ему его прислал Мартин Гарднер!) Реакция Постона Гиллману тоже кажется чрезмерной (он отмечает, что <<\eng{Poston's term is `wrong'}>>, p.~488); далее он, со ссылкой на Радина (Charles Radin, частное сообщение) намечает отсутствующее у Куранта и Роббинса рассуждение. Радин также использует ключевое соображение о том, что приблизившись к полу достаточно близко, стержень непременно столкнётся с ним (видимо, в тексте опечатка в знаке неравенства для~$t'$):

\begin{quote}
\eng{First we prove: For any given physical setup and itinerary $x(t)$, there is an $\epsilon>0$ such that, if $H(t)<\epsilon$ and $V(t)$ is either zero or directed toward the floor, then $H(t')\le H(t)$ for $t'<t<T$. This follows almost immediately from noticing that when the rod is almost at the floor, the angular acceleration of the rod produced by the bounded horizontal acceleration of the train must be smaller in magnitude that the vertical acceleration caused by gravity; the net acceleration must then be directed toward the floor, and if the angular verlocity is also directed toward the floor the conclusion follows.}
\end{quote}

Далее он объясняет (примерно так же, как и Броман), почему из этого соображения вытекает непрерывность.

В другой рецензии (Брайн Бланк~\cite{blank2001}, \emph{Notices of the AMS}) рецензент с сожалением отмечает, что изменения в издании 1996 года по сравнению с предыдущими минимальны:

\begin{quote}
\eng{All the old figures are there. Even the original typesetting has been preserved --- quite a welcome change from the homogenized TEX of the present. Closer inspection, however, reveals something less welcome: the new edition is by and large a photographic reproduction. I could not find even one change in it. Stewart rationalizes this in his preface: ``not a single word or symbol had to be deleted from this new edition.'' Really? After half a century could we not have had a correction to the name of Mr. Arch medes (p. 400)?}
\end{quote}

Рецензент также упоминает критику Стьюарта и объяснения Гиллмана:

\begin{quote}
\eng{Stewart relates a challenge to the basic continuity assumption that underlies the solution given by Courant and Robbins. Ironically, that challenge itself relies on the assumption that the train can move in a way that is physically impossible, as Gillman has pointed out in his review [5].}
\end{quote}

(Здесь [5] --- это рецензия Гиллмана~\cite{gillman1998}.)

\subsection{После Арнольда}

После публикаций книг Арнольда (который, кстати, даёт ссылку на рецензии Гиллмана и Бланка, но никак их не комментирует), интерес к задаче Уитни снова вырос, и появилось несколько сравнительно недавних публикаций~\cite{polekhin2014,polekhin2014a,zubelevich2015,bolotin-kozlov2015,srzednicki2017}.

И.\,Ю.\,Полехин в статье 2014 года~\cite{polekhin2014}, приведя формулировку задачи Уитни из русского издания Куранта и Роббинса, пишет:
\begin{quote}
Положительный ответ на этот вопрос [о начальном положении, когда стержень не коснётся пола] дается самими авторами. Тем не менее, предложенное доказательство использует предположение о том, что движение стержня зависит непрерывным образом от начальных условий. Данное предположение кажется естественным, и подобное действительно верно для широкого класса механических систем, но в случае, когда считается, что, коснувшись пола, стержень вечно остается горизонтальным, непрерывная зависимость от начальных данных становится менее очевидной. В частности, эта неполнота доказательства была отмечена Арнольдом при обсуждении данной задачи [2]. В настоящей работе приводится строгое обоснование существования решения без падений (в том числе для случая решения, определенного на бесконечном полуинтервале времени), основанное на применении топологического метода Важевского.
\end{quote}
Здесь [2] --- это книга Арнольда~\cite{arnold2002}. Само рассуждение, насколько я могу судить (работ Важевского я не читал, и в изложении Полехина много формул), следует схеме Бромана и Гиллмана. Помимо этого, доказывается, что для случая периодического движения поезда существует периодическое решение для стержня, при котором он никогда не касается пола.

В английском варианте~\cite{polekhin2014a} Полехин описывает ситуацию так:
\begin{quote}
\eng{This shortcoming of the original proof} [из книги Куранта и Роббинса]  \eng{was mentioned and briefly commented by Arnold in his book [Arn] which also includes short overview of the articles related to the matter. Yet detailed consideration of the issue of whether original prove} [опечатка: вероятно, должно быть `proof'] \eng{is full and correct or not is beyond the objective of the paper. In the first section, application of the topological Wa\.zewski principle to the above problem is considered. This method allows us to prove existence of solutions without falling (even on an infinite time interval), including solutions with zero initial velocity of inverted pendulum.}
\end{quote}
Здесь [Arn] --- та же книга Арнольда~\cite{arnold2002}. Полехин упоминает статьи, цитируемые Арнольдом, включая рецензии Гиллмана и Бланка, но никак не комментирует связи своего рассуждения с приводимым Гиллманом рассуждением Радина, и осторожно пишет про <<\eng{issue of whether original proof is full and correct or not}>>. Статья Бромана~\cite{broman1958} также не упоминается.

Есть ещё одна публикация примерно того же времени, посвящённая задаче Уитни и её обобщениям~\cite{zubelevich2015} --- её автор Олег Зубелевич, изложив условие задачи Уитни, пишет:
\begin{quote}

\eng{The authors} [Курант и Роббинс] \eng{gave positive answer to this question. Their argument was informal. V. Arnold in [1] considered this problem as open. The complete solution to the problem has been given by I. Polekhin in his Ph.D. thesis (unpublished), see also [3]. He solved the problem by direct application of results from [4]. In this article we prove simple and general theorem which implies particularly that there are continuum never-falling solutions to Whitney’s problem, we also believe that this theorem describes many other such a type effects.}
\end{quote}
Здесь [1] --- та же книга Арнольда 2002 года, [3] --- публикация Полехина~\cite{polekhin2014a}, а [4] --- статья~\cite{srzednicki2005} (где непосредственно задача Уитни не упоминается). Один из авторов последней статьи, Роман Сшедницки, в 2017 году опубликовал заметку~\cite{srzednicki2017}, в которой рассказывает об истории задачи Уитни (и из которой я узнал о существовании работы Бромана~\cite{broman1958}, в частности). Он пишет:

\begin{quote}
\eng{In the book ``What is Mathematics?'' Richard Courant and Herbert Robbins presented a solution of a Whitney’s problem of an inverted pendulum on a railway carriage moving on a straight line. Since the appearance of the book in 1941 the solution was contested by several distinguished mathematicians. The first formal proof based on the idea of Courant and Robbins was published by Ivan Polekhin in 2014. Polekhin also proved a theorem on the existence of a periodic solution of the problem provided the movement of the carriage on the line is periodic. In the present paper we slightly improve the Polekhin’s theorem by lowering the regularity class of the motion and we prove a theorem on the existence of a periodic solution if the carriage moves periodically on the plane.}
\end{quote}

Однако, говоря о статье Бромана~\cite{broman1958}, Сшедницки довольно загадочно пишет <<\eng{He presented a comprehensive argument supporting the Courant and Robbins’ solution, although his proof lacks of formal rigor at some details}>> --- не указывая, однако, что же это за такие детали. Упомянув возражения Арнольда в~\cite{arnold2009} (<<\eng{At that time Arnold had still objections towards the correctness of the solution from [CR]}>>), он пишет:

\begin{quote}
\eng{Finally, in 2014, 73 years from the announcement of the Whitney’s problem, in the paper [P1] Ivan Polekhin provided a short rigorous proof of the Courant and Robbins’s solution based on the Wa\.zewski retract theorem. Other proofs were published in [BK] and [Zu].}
\end{quote}

Здесь [P1] --- это статьи Полехина~\cite{polekhin2014,polekhin2014a}, [BK] --- это статья Болотина и Козлова~\cite{bolotin-kozlov2015},  а [Zu] --- статья Зубелевича~\cite{zubelevich2015}. В статье~\cite{bolotin-kozlov2015} (после формулировки некоторых общих результатов) упоминается задача Уитни, ситуация с которой описывается так:

\begin{quote}
Утверждение о существовании движений перевернутого маятника без падений сформулировано Уитни и обсуждается в книге [2]. Доказательство основано на несуществовании ретракции отрезка на его границу. Критические замечания В. И. Арнольда [5] стимулировали появление полных доказательств теоремы Уитни (с указанием условий ее справедливости) [3], [4].
\end{quote}

Здесь [2] --- это книга Куранта и Роббинса, несуществование ретракции --- теорема о промежуточных значениях, [5] --- книга~\cite{arnold2002}, а [3] и [4] --- соответственно~\cite{polekhin2014} и~\cite{zubelevich2015}. Не вполне ясно, считают ли авторы~\cite{bolotin-kozlov2015} доказательства Бромана из~\cite{broman1958} или Радина из~\cite{gillman1998} неполными и если да, то в чём их неполнота.

В заключение скажу ещё о своём разговоре с Сабиром Меджидовичем Гусейн-Заде на одной из летних школ в Дубне, где я услышал о возражениях Арнольда по поводу рассуждения в Куранте и Роббинсе. Арнольд был тогда ещё жив, но подойти к нему с этим я (как и многие другие) боялся. Вместо этого я настойчиво просил Гусейн-Заде послушать, как я представлял себе доказательство Куранта -- Роббинса (примерно в том же духе, как написано выше), и сказать мне отчётливо, правильно ли это рассуждение. Вежливый Сабир Меджидович меня выслушал и сказал, что ошибки в рассуждении не видит (но, кажется, с Арнольдом это после не обсуждал, как и я).


\section{Introduction}

Innovation in materials is the key driver for many recent technological advances. From clean energy \cite{Tabor2018Accelerating} to the aerospace industry \cite{Gibson2010review} or drug discovery \cite{Chen2018rise}, research in chemical and materials science is constantly pushed forward to develop compounds and formulae with novel applications, lower cost and better performance. Conventional methods for the discovery of new materials start from a well-defined set of substances from which properties of interest are derived. Then, intensive research on the relationship between structures and properties is performed. The gained insights from this procedure lead to incremental improvements in the compounds and the cycle is restarted with a new search space to be explored. This trial-and-error approach to innovation often leads to costly and incremental steps towards the development of new technologies and in occasion relies on serendipity for leap progress. Materials development may require billions of dollars in investments \cite{DiMasi2016Innovation} and up to 20 years to be deployed to the market \cite{DiMasi2016Innovation,Tabor2018Accelerating}.

Despite the challenges associated with such direct approaches, they have not prevented data-driven discovery of materials from happening. High-throughput materials screening \cite{Shoichet2004Virtual,Greeley2006Computational,Alapati2006Identification,Setyawan2011High,Subramaniam2008Virtual,Armiento2011Screening,Jain2011high,Curtarolo2013high,Pyzer-Knapp2015What,Gomez-Bombarelli2016Design} and data mining \cite{Morgan2004High,Ortiz2009Data,Yu2012Identification,Yang2012search,Lin2012silico,Mounet2018Two} have been responsible for several breakthroughs in the last two decades \cite{Potyrailo2011Combinatorial,Jain2016Computational}, leading to the establishment of the Materials Genome Initiative \cite{NSTC2011Materials} and multiple collaborative projects around the world build around databases and analysis pipelines \cite{Curtarolo2012AFLOWLIB.ORG,Calderon2015AFLOW,Jain2013Commentary,Saal2013Materials}. Automated, scalable approaches leverage from data sets in the thousands to millions of simulations to offer a cornucopia of insights on materials composition, structure and synthesis.

Developing materials with the inverse perspective departs from these traditional methods. Instead of exhaustively deriving properties from structures, the performance parameters are chosen beforehand and unknown materials satisfying these requirements are inferred. Hence, innovation in this setting is achieved by reverting the mapping between structures and their properties. Unfortunately, this approach is even harder than the conventional one. Inverting a given Hamiltonian is not a well-defined problem, and the absence of a systematic exploratory methodology may result in delays, or outright failure, of the discovery cycle of materials \cite{Sanchez-Lengeling2018Inverse}. Furthermore, another major obstacle to the design of arbitrary compounds is the dimensionality of the missing data for known and unknown compounds \cite{Zunger2018Inverse}. As an example, the breadth of accessible drug-like molecules can be on the order of $10^{60}$ \cite{Polishchuk2013Estimation,Virshup2013Stochastic}, rendering manual searches or enumerations through the chemical space an intractable problem. In addition, molecules and crystal structures are discrete objects, which hinders automated optimization, and computer-generated candidates must follow a series of hard (valence rules, thermal stability) and soft (synthetic accessibility, cost, safety) constraints that may be difficult to state in explicit form. As the inverse chemical design holds great promise for economic, environmental and societal progress, one can ask how to rationalize the exploration of unknown substances and accelerate the discovery of new materials.

\subsection{Early inverse design strategies for materials}

The inverse chemical design is usually posed as an optimization problem in which molecular properties are extremized with respect to given parameters \cite{Joback1989Designing}. This concept splits the inverse design problem in two parts: (i) efficiently sampling materials from an enormous configuration space, and (ii) searching for global maxima in their properties \cite{Kuhn1996Inverse} corresponding to minima in their potential energy surface \cite{Wales1999Global,Schoen2001Determination}. Early approaches towards the inverse materials design used chemical intuition to address (i), narrowing down and navigating the space of structures under investigation with probabilistic methods \cite{Gani1983Molecular,Marder1991Approaches,Holmblad1996Designing,Kuhn1996Inverse,Sigmund1997Design,Wolverton1997Invertible}. Nevertheless, even constrained spaces can be too large to be exhaustively enumerated. Especially in the absence of an efficient exploratory policy, this discovery process demands considerable computational resources and time. Several different strategies are required to simultaneously navigate the chemical space and evaluate the properties of the materials under investigation.

Monte Carlo methods resort to statistical sampling to avoid enumerating a space of interest. When combined with simulated annealing  \cite{Metropolis1953Equation}, for example, they become adequate to locate extrema within property spaces. In physics, reverse Monte Carlo methods have long been developed to determine structural information from experimental data \cite{Kaplow1968Atomic,Gerold1987determination,McGreevy1988Reverse}. However, the popularization of similar methods to \textit{de novo} design of materials is more recent. Wolverton \textit{et al.~} \cite{Wolverton1997Invertible} employed such methods to aid the design of alloys and avoid expensive enumeration of compositions and Franceschetti and Zunger \cite{Franceschetti1999inverse} improved the idea to design Al$_x$Ga$_{1-x}$As and Ga$_x$In$_{1-x}$P superlattices with a tailored band gaps. They started with configurations sampled using Monte Carlo, relaxed the atomic positions using valence-force-field methods and calculated their band gap by fast diagonalization of pseudopotential hamiltonians. Through this practical process, they predicted superlattices with optimal band gaps after analyzing less than $10^4$ compounds among $\sim 10^{14}$ structures \cite{Franceschetti1999inverse}.

Other popular techniques for multidimensional optimization that also involve a stochastic component are genetic algorithms (GAs) \cite{Holland1992Adaptation}. Based on evolution principles, GAs refine specific parameters of a population that improve a targeted property. In materials design, GAs have been vastly employed in the inverse design of small molecules \cite{Judson1993Conformational,Glen1995genetic}, polymers \cite{Venkatasubramanian1994Computer,Venkatasubramanian1995Evolutionary}, drugs \cite{Parrill1996Evolutionary,Schneider2000De}, biomolecules \cite{Gordon1999Branch,Reetz2004Asymmetric}, catalysts \cite{Wolf2000evolutionary}, alloys \cite{Johannesson2002Combined,Dudiy2006Searching}, semiconductors \cite{Piquini2008Band,dAvezac2012Genetic,Zhang2013Genetic}, and photovoltaic materials \cite{Yu2012Inverse}. Furthermore, evolution-inspired approaches have been used as a general modeling tool to predict stable structures \cite{Brodmeier1994Application,Woodley1999prediction,Glass2006USPEXEvolutionary,Oganov2006Crystal,Froemming2009Optimizing,Vilhelmsen2014genetic} and Hamiltonian parameters \cite{Hart2005Evolutionary,Blum2005Using}. Many more applications of GAs in materials design are still being demonstrated after decades of its inception \cite{Virshup2013Stochastic,Rupakheti2015Strategy,Reymond2015Chemical,Le2016Discovery,Jennings2019Genetic}.

Monte Carlo and evolutionary algorithms are interpretable and often produce powerful implementations. The combination of sampling and optimization is a great improvement over random searches or full enumeration of a chemical space. Nonetheless, they still correspond to discrete optimization techniques in a combinatorial space, and require individual evaluation of their properties at every step. This discrete form hinders chemical interpolations and the definition of property gradients during optimization processes, thus retaining a flavor of ``trial-and-error'' in the computational design of materials, rather than an invertible structure-property mapping. One of the first attempts to use a continuous representation on the molecular design was performed by Kuhn and Beratan \cite{Kuhn1996Inverse}. The authors varied coefficients in linear combination of atomic orbitals while keeping the energy eigenvalues fixed to optimize linear chains of atoms. Later, Lilienfeld \textit{et al.~} \cite{Lilienfeld2005Variational} generalized the discrete nature of atoms by approximating atomic numbers by continuous functions and defining property gradients with respect to this ``alchemical potential''. They used this theory to design ligands for proteins \cite{Lilienfeld2005Variational} and tune electronic properties of derivatives of benzene \cite{Marcon2007Tuning}. A similar strategy was proposed by Wang \textit{et al.~} \cite{Wang2006Designing} around the same time. Instead of atomic numbers, a linear combination of atomic potentials was used as a basis for optimizations in property landscapes. Following the bijectiveness between potential and electronic density in the Hohenberg-Kohn theory \cite{Hohenberg1964Inhomogeneous}, nuclei-electrons interaction potentials were employed as quasi-invertible representations of molecules. Potentials resulting from optimizations with property gradients can be later interpolated or approximated by a discrete molecular structure whose atomic coordinates give rise to a similar potential. Over the years, the approach was further refined within the tight-binding framework \cite{Xiao2008Inverse,Balamurugan2008Exploring} and gradient-directed Monte Carlo method \cite{Keinan2007Designing,Hu2008gradient}, its applicability demonstrated in the design of molecules with improved hyperpolarizability \cite{Wang2006Designing,Keinan2007Designing,Xiao2008Inverse} and acidity \cite{Vleeschouwer2012Inverse}.

Despite these promising approaches, many challenges in inverse chemical design remain unsolved. Monte Carlo and genetic algorithms share the complexity of discrete optimization methods over graphs, particularly exacerbated by the rugged property surfaces. They rely on stochastic steps that struggle to capture the interrelated hard and soft constraints of chemical design: converting a single into a double bond may produce a formally valid, but impractical and unacceptable molecule depending on chemical context. On the other hand, a compromise between validity and diversity of the chemical space is difficult to achieve with continuous representations. Lastly, finding optimal points in the 3D potential energy surface that produce a desired output is still not the same as molecular optimization, since the generated ``atom cloud'' may not be a local minimum, stable enough in operating conditions, or synthetically attainable. An ideal inverse chemical design tool would offer the best of the two worlds: an efficient way to sample valid and acceptable regions of the chemical space; a fast method to calculate properties from given structures; a differentiable representation for a wide spectrum of materials; and the capacity to optimize them using property gradients. Furthermore, it should operate on the manifold of synthetically accessible, stable compounds. This is where modern machine learning (ML) algorithms come into play.

\subsection{Deep learning and generative models}

Deep learning (DL) is emerging as a promising tool to address the inverse design of many different applications. Particularly through generative models, algorithms in DL push forward how machines understand real data. Roughly speaking, the role of a generative model is to capture the underlying rules of a data distribution. Given a collection of (training) data points $\{X_i\}$ in a space $\mathcal{X}$, a model is trained to match the data distribution $P_X$ by means of a generative process $P_G$ in such a way that generated data $Y \sim P_G$ resembles the real data $X \sim P_X$. Earlier generative models such as Boltzmann Machines \cite{Hinton1986Learning,Hinton1983Optimal}, Restricted Boltzmann Machines \cite{Smolensky1986Information}, Deep Belief Networks \cite{Hinton2006Fast} or Deep Boltzmann Machines \cite{Salakhutdinov2009Deep} were the first to tackle the problem of learning probability distributions based on training examples. Their lack of flexibility, tractability and generalizing ability, however, rendered them obsolete in favor of more modern ones \cite{Goodfellow2016Deep}.

Current generative models have been successful in learning and generating novel data from different types of real-world examples. Deep neural networks trained on image datasets are able to produce realistic-looking house interiors, animals, buildings, objects and human faces \cite{Karras2017Progressive,Goodfellow2014Generative}, as well as embed pictures with artistic style \cite{Gatys2015Neural} or enhance it with super-resolution \cite{Ledig2016Photo}. Other examples include convincing text \cite{Bowman2015Generating,Xu2015Show}, music \cite{Mehri2016SampleRNN}, voices \cite{Oord2016WaveNet} and videos \cite{Vondrick2016Generating} synthesized by such networks. Most interesting is the creation of novel data conditioned on latent features, which allows tuning models with vector and arithmetic operations in a property space \cite{Radford2015Unsupervised,Engel2017Latent}. The adaptable architectures of these models also enable straightforward training procedures based on backpropagation \cite{LeCun2015Deep}. Within the DL framework, a proper loss function drives gradients so that the generative model, typically parameterized by a neural network, learns to minimize the distance between the two distributions.

Among the popular architectures for generating data from deep neural networks, the Variational Auto-Encoder (VAE) \cite{Kingma2013Auto} is a particularly robust architecture. It couples inference and generation by mapping data to a manifold conditioned to implicit data descriptors. To do so, the model is trained to learn the identity function while constrained by a dimensional bottleneck called latent space (see Fig. \ref{fig:gen_models}a). In this scheme, data is first encoded to a probability distribution $Q_\phi (\mathbf{z}|X)$ matching a given prior distribution $P_z(\mathbf{z})$, where $\mathbf{z}$ is called latent vector. Then, a sample from the latent space is reconstructed with the generative algorithm $P_\theta (X|\mathbf{z})$. In the VAE \cite{Kingma2013Auto}, outcomes of both processes are parameterized by $\phi$ and $\theta$ to maximize a lower bound for the log-likelihood of the output with respect to the input data distribution. The VAE objective is, therefore,

\begin{equation}
\mathcal{L}(\theta, \phi) = - D_{KL} \left( Q_\phi(\mathbf{z}|X) || P_z(\mathbf{z}) \right) + \mathbb{E}_{z \sim Q_\phi} \left[ \log P_\theta (X|\mathbf{z})\right].
\end{equation}

\noindent The encoder is regularized with a divergence term $D_{KL}$, while the decoder is penalized by a reconstruction error $\log P_\theta (X|\mathbf{z})$, usually in the form of mean-squared or cross entropy losses. This maximization can then be performed by stochastic gradient ascent.

The probabilistic nature of VAE manifolds approximately accounts for many complex interactions between data points. Although functional in many cases, the modeled data distribution does not always converge to real data distributions \cite{Arjovsky2017Wasserstein}. Furthermore, Kullback-Leibler or Jensen-Shannon divergences cannot be analytically computed for an arbitrary prior, and most works are restricted to Gaussian distributions. Avoiding high-variance methods to determine this regularizing term is also an important concern. Recently, this limitation was simplified by employing the Wasserstein distance as a penalty for the encoder regularization \cite{Arjovsky2017Wasserstein,Tolstikhin2017Wasserstein}. As a result, richer latent representations are computed more efficiently within Wasserstein Auto-Encoders, resulting in disentanglement, latent shaping, and improved reconstruction \cite{Rubenstein2018Latent,Arjovsky2017Wasserstein,Tolstikhin2017Wasserstein}.

Another approach to generative models are the Generative Adversarial Networks (GANs) \cite{Goodfellow2014Generative}. Recognized by their sharp reconstructions, GANs are constructed by making two neural networks compete against each other until a Nash equilibrium is found. One of the networks is a deterministic generative model. It applies a non-linear set of transformations to a prior probability distribution $P_z$ in order to match the real data distribution $P_X$. Interestingly, the generator (or actor) only receives the prior distribution as input, and has no contact with the real data whatsoever. It can only be trained through a second network, called discriminator or critic. The latter tries to distinguish real data $X \sim P_X$ from fake data $Y = G(\mathbf{z}) \sim P_G$, as depicted in Fig. \ref{fig:gen_models}b. The objective of the critic is to perfectly distinguish between $P_X$ and $P_G$, thus maximizing the prediction accuracy. On the other hand, the generator tries to fool the discriminator by creating data points that look like real data points,  minimizing the prediction accuracy of the critic. Consequently, the complete GAN objective is written as \cite{Goodfellow2014Generative}

\begin{equation}
\min_G \max_D V(D, G) = \mathbb{E}_{X \sim P_X} \left[ \log D(X) \right] + \mathbb{E}_{\mathbf{z} \sim P_z} \left[ \log \left(1 - D(G(\mathbf{z}))\right) \right].
\end{equation}

Despite the impressive results from GANs, their training process is highly unstable. The min-max problem requires a well-balanced training from both networks to ensure non-vanishing gradients and convergence to a successful model. Furthermore, GANs do not reward diversity of generated samples and the system is prone to mode collapse. There is no reason why the generated distribution $P_G$ should have the same support of the original data $P_X$, and the actor produces only a handful of different examples which are realistic enough. This does not happen for the VAE, since the log-likelihood term gives an infinite loss for a generated data distribution with a disjoint support with respect to the original data distribution. Several different architectures have been proposed to address these issues among GANs \cite{Mirza2014Conditional,Chen2016InfoGAN,Arjovsky2017Wasserstein,Che2016Mode,Odena2016Conditional,Mao2016Least,Hjelm2017Boundary,Zhao2016Energy,Nowozin2016f,Donahue2016Adversarial,Berthelot2017BEGAN,Gulrajani2017Improved,Yi2017DualGAN}. Although many of them may be equivalent to a certain extent \cite{Lucic2017Are}, steady progress is being made in this area, especially through more complex ways of approximating data distributions, such as with f-divergence \cite{Nowozin2016f} or optimal transport \cite{Arjovsky2017Wasserstein,Gulrajani2017Improved,Berthelot2017BEGAN}.

Other models such as the auto-regressive PixelRNN \cite{Oord2016Pixel} and PixelCNN \cite{Oord2016Conditional,Salimans2017PixelCNN++} have also been successful as generators of images \cite{Oord2016Pixel,Oord2016Conditional,Salimans2017PixelCNN++}, video \cite{Kalchbrenner2016Video}, text \cite{Kalchbrenner2016Neural} and sound \cite{Oord2016WaveNet}. Differently from VAE and GANs, these models approximate the data distribution by a tractable factorization $P_X$. For example, in an $n \times n$ image, the generative model $P(X)$ is written as \cite{Oord2016Pixel}

\begin{equation}
P(X) = \prod_{i=1}^{n^2} P\left(x_i | x_1, \ldots, x_{i-1} \right),
\end{equation}

\noindent where each $x_i$ is a pixel generated by the model (see Fig. \ref{fig:gen_models}c). These models with explicit distributions yield samples with very good negative log-likelihood and diversity \cite{Oord2016Pixel}. The model evaluation is also straightforward, given the explicit computation of $P(X)$. As a drawback, however, these models rely on the sequential generation of data, which is a slow process. A diagram of the architectures of the three generative models here discussed is seen in Fig. \ref{fig:gen_models}.

\begin{figure}[tb]
\centering
\includegraphics[width=\linewidth]{Figures/gen_models.png}
\caption{Schematic diagrams for three popular generative models: (a) VAE, (b) GAN, and (c) auto-regressive.}
\label{fig:gen_models}
\end{figure}

\subsection{Generative models meet chemical design}

Apart from their numerous aforementioned applications, generative models are also attracting attention in chemistry and materials science. DL is being employed not only for the prediction and identification of properties of molecules, but also to generate new chemical compounds \cite{LeCun2015Deep}. In the context of inverse design, generative models provide benefits such as: generating complex samples from simple probability distributions; providing meaningful latent representations, over which optimizations can be performed; and the ability to perform inference when coupled to supervised models. Therefore, unifying generative models with chemical design is a promising venue to accelerate innovation in chemistry and related fields.

To go beyond the limitations of traditional inverse design strategies, an ideal way to discover new materials should satisfy some requisites \cite{Gomez-Bombarelli2018Automatic}. To be a completely hands-free model, the model should be data-driven, thus avoiding fixed libraries and expensive labeling. It is also desirable that it outputs as many potential molecules as possible under a subset of interest, which means that the model needs a powerful generator coupled with a continuous representation for molecules. Furthermore, such a representation should be interpretable, allowing a correct description of structure-property relationships within molecules. If, additionally, the model is differentiable, it would be possible to optimize certain properties using gradient techniques and, later, look for molecules satisfying such constraints.

The development of such a tool is currently a priority for ML models in chemistry and for the inverse chemical design. It relies primarily on two decisions: which model to use and how to represent a molecule in a computer-friendly way. Following our brief introduction to the early inverse design strategies and main generative models in the literature, we describe which molecular representations are possible.

In quantum mechanics, a molecular system is represented by a wavefunction that is a solution of the Schr\"odinger equation for that particular molecule. To derive most properties of interest, the spatial wavefunction is enough. Computing such a representation, however, is equivalent to solving an (approximate) version of the Schr\"odinger equation itself. Many methods for theoretical chemistry, such as Hartree-Fock \cite{Hartree1928Wave,Fock1930Naherungsmethode} or Density Functional Theory \cite{Hohenberg1964Inhomogeneous,Kohn1965Self}, represent molecules using wavefunctions or electronic densities and obtain other properties from it. Solving quantum chemical calculations is computationally demanding in many cases, though. The idea with many ML methods is not only to avoid these calculations, but also to make a generalizable model that highlight different aspects of chemical intuition. Therefore, we should look for other representations for chemical structures.

Thousands of different descriptors are available for chemical prediction methods \cite{Todeschini2000Handbook}. Several relevant features for ML have demonstrated their capabilities for predicting properties of molecules, such as fingerprints \cite{Rogers2010Extended}, bag-of-bonds \cite{Hansen2015Machine}, Coulomb matrices \cite{Rupp2012Fast}, deep tensor neural networks train on the distance matrix\cite{Schuett2017Quantum}, many-body tensor representation \cite{Huo2017Unified}, SMILES strings \cite{Weininger1988SMILES}, and graphs \cite{Kearnes2016Molecular,Duvenaud2015Convolutional,Gilmer2017Neural}. Not all representations are invertible for human interpretation, however. To teach a generative model how to create a molecule, it may suffice for it to produce a fingerprint, for example. However, how can one map any possible fingerprint to a molecule is an extra step of complexity equivalent to the generation of libraries. This is undesirable in a practical generative model. In this chapter, we focus on two easily interpretable representations, SMILES strings and molecular graphs, and how generative models perform with these representations. Examples of these two forms of writing a molecule are shown in Fig. \ref{fig:representations}.

\begin{figure}[htb]
\centering
\includegraphics[width=.8\linewidth]{Figures/graph_vs_smiles.png}
\caption{Two popular ways of representing a molecule using: (a) SMILES strings converted to one-hot encoding; or (b) a graph derived from the Lewis structure.}
\label{fig:representations}
\end{figure}

\section{Chemical generative models}

\subsection{SMILES representation}

SMILES (Simplified Molecular Input Line Entry System) strings have been widely adopted as representation for molecules \cite{Weininger1988SMILES}. Through graph-to-text mapping algorithms, it determines atoms by atomic number and aromaticity, and can capture branching, cycles, ionization, etc. The same molecule can be represented by multiple SMILES strings, and thus a canonical representation is typically chose, although some works leverage non-canonical strings as a data augmentation and regularization strategy. Although SMILES are inferior to the more modern InChI (International Chemical Identifier) representation in their ability to address key challenges in representing molecules as strings such as tautomerism, mesomerism and some forms of isomerism, SMILES follow a much simpler syntax that has proven easier to learn for ML models.

Since SMILES rely on a sequence-based representation, natural language processing (NLP) algorithms in deep learning can be naturally extended to them. This allows the transferability of several architectures from the NLP community to interpret the chemical world. Mostly, these systems make use of recurrent neural networks (RNNs) to condition the generation of the next character on the previous ones, creating arbitrarily long sequences character by character \cite{Goodfellow2016Deep}. The order of the sequence is very relevant to generate a valid molecule, and observation of such restrictions can be typically incorporated in RNNs with long short-term memory cells (LSTM) \cite{Hochreiter1997Long}, gated recurrent units (GRUs) \cite{Chung2014Empirical}, or stack-augmented memory \cite{Popova2018Deep}.

A simple form of generating molecules using only RNN architectures is to extensively train them with valid SMILES from a database of molecules. This requires post-processing analyses, as it resembles traditional library generation. As a proof of concept, Ikebata \textit{et al.~} \cite{Ikebata2017Bayesian} used SMILES strings to design small organic molecules by employing Bayesian sampling with sequential Monte Carlo. Ertl \textit{et al.~} \cite{Ertl2017silico} instead generated molecules using LSTM cells and later employed them in a virtual screening for properties.

Generating libraries, however, is not enough for the automatic discovery of chemical compounds. Asking an RNN-based model to simply create SMILES strings does not improve on the rational exploration of the chemical space. In general, the design of new molecules is also oriented towards certain properties, like solubility, toxicity and drug-likeness \cite{Gomez-Bombarelli2018Automatic}, which are not necessarily incorporated in the training process of RNNs. In order to skew the generation of molecules and better investigate a subset of the chemical space, Segler \textit{et al.~} \cite{Segler2018Generating} used transfer-learning to first train the RNN on a whole dataset of molecules and later fine-tune the model towards the generation of molecules with physico-chemical properties of interest. This two-part approach allows the model to first learn the grammar inherent to SMILES to then create new molecules based only on the most interesting ones. In line with this depth-search, Gupta \textit{et al.~} \cite{Gupta2017Generative} demonstrated the application of transfer learning to grow molecules from fragments. This technique is particularly useful for drug discovery \cite{Chen2018rise, Ching2018Opportunities}, in which the search of the chemical space usually begins from a known substructure with certain desired functionalities.

Recently, the usage of reinforcement learning (RL) to generate molecules with certain properties became popular among generative models. Since the representation of a molecule using SMILES requires the generator to output a sequence of characters, each decision can be considered as an action. The successful completion of a valid SMILES string is associated with a reward, for example, and undesired features in the sequence are penalized. Jaques \textit{et al.~} \cite{Jaques2017Sequence} used RL to impose a structure on sequence generation, avoiding repeating patterns not only in SMILES strings but also in text and music. By penalizing large rings, short sequences of characters and long, monotonous carbon chains, they were able to increase the number of valid molecules their model produced. Olivecrona \textit{et al.~} \cite{Olivecrona2017Molecular} demonstrated the usage of augmented episodic likelihood and traditional policy gradient methods to tune the generation of molecules from an RNN. Their method achieved 94\% of validity on generating molecules sampled from a prior distribution. It was also taught to avoid functional groups containing sulfur and to generate structures similar to a given structure or with certain target activities. Similarly, Popova \textit{et al.~} \cite{Popova2018Deep} designed molecules for drugs using a stack-augmented RNN. It demonstrated improved capacity to capture the grammar of SMILES while using RL to tune their synthetic accessibility, solubility, inhibition and other properties.

As the degree of abstraction grows in the molecule design, more complex generative models are proposed to explore the chemical space. VAEs, for example, can include a direct mapping between structures and properties and vice-versa. Its joint training with an encoder and a decoder is capable of approximating very complex data distributions using a real-valued and compressed representation, which is essential for improving the search for chemical compounds. Since the latent space is meaningful, the generator learns to associate patterns in the latent space with properties of the real data. After both the encoding and the decoding networks are jointly trained, the generative model can be decoupled from the inference step and latent variables then become the field for exploration. Therefore, VAEs map the original chemical space to a continuous, differentiable space conveying all the information about the original molecules, over which optimization can be performed. Additionally, conditional generation of molecules based on properties is made possible without hand-made constraints in SMILES, semi-supervised methods can be used to tune the model with relevant properties. This approach is closer to the model of an ideal, automatic, chemical generative model as discussed earlier.

Constructed over RNNs as both encoder and decoder, G\'omez-Bombarelli \textit{et al.~} \cite{Gomez-Bombarelli2018Automatic} trained a VAE on prediction and reconstruction tasks for molecules extracted from the QM9 and ZINC datasets. The latent space allowed not only sampling of molecules but also interpolations, reconstruction, and optimization using a Gaussian process predictor trained on the latent space (Fig. \ref{fig:vae_smiles}).  Kang and Cho \cite{Kang2018Conditional} used partial annotation on molecules to train a semi-supervised VAE to decrease the error for property prediction and to generate molecules conditioned on targets. It can also be enhanced in combination with other dimensionality reduction algorithms \cite{Sattarov2019De}. Within the chemical world, VAEs based on sequences also show promise for investigating proteins \cite{Sinai2017Variational}, learning chemical interactions between molecules \cite{Kwon2017DeepCCI}, designing organic light-emitting diodes \cite{Kim2018Deep} and generating ligands \cite{Mallet2019Leveraging,Lim2018Molecular}.

\begin{figure}[tb]
\centering
\includegraphics[width=.7\linewidth]{Figures/GomezBombarelli2016automatic.png}
\caption{Variational Auto-Encoder for chemical design. The architecture in (a) allows for property optimization in the latent space, as depicted in (b). Figure reproduced from \cite{Gomez-Bombarelli2018Automatic}.}
\label{fig:vae_smiles}
\end{figure}

In the field of molecule generation, GANs usually appear associated with RL. To fine-tune the generation of long SMILES strings, Guimaraes \textit{et al.~} \cite{Guimaraes2017Objective} employed a Wasserstein GAN \cite{Arjovsky2017Wasserstein} with a stochastic policy that increased the diversity, optimized the properties and maintained the drug-likeness of the generated samples. Sanchez-Langelin \textit{et al.~} \cite{Sanchez-Lengeling2017Optimizing} and Putin \textit{et al.~} \cite{Putin2018Reinforced} further improved upon this work to bias the distribution of generated molecules towards a goal. In addition, Mendez-Lucio \textit{et al.~} \cite{Mendez-Lucio2018De} used a GAN to generate molecules conditioned on gene expression signatures, which is particularly useful to create active compounds towards a certain target. Similarly to what is done with molecules, Killoran \textit{et al.~} \cite{Killoran2017Generating} employed a GAN to create realistic samples of DNA sequences from a small subset of configurations. The model was also tuned to design DNA chains adapted to protein binding and look for motifs representing functional roles. Adversarial training was also employed in the discovery of drugs for using molecular fingerprints as opposed to a reversible representation \cite{Kadurin2017druGAN,Kadurin2017cornucopia,Blaschke2018Application} and SMILES \cite{Polykovskiy2018Entangled}. However, avoiding the unstable training and mode collapse while generating molecules is still a hindrance for the usage of GANs in chemical design.

Although SMILES have proved to be a reliable representation for molecule generation, their sequential nature imposes some constraints to the architectures being learned. Forcing an RNN to implicitly learn their linguistic rules poses additional difficulties to the model under training. Additionally, decoding a sequence of generated characters into a valid molecule is especially difficult. In \cite{Gomez-Bombarelli2018Automatic}, the rate of success when decoding molecules depended on the proximity of the latent point to the valid molecule, and could be as low as 4\% for random points on the latent space. Although RL is as an alternative to reward the generation of valid molecules \cite{Jaques2017Sequence,Guimaraes2017Objective,Sanchez-Lengeling2017Optimizing}, other architecture changes can also circumvent this difficulty. Techniques to generate valid sequences imported from NLP studies include: using revision to improve the outcome of sequences \cite{Mueller2017Sequence}; adding a validator to the decoder to generate more valid samples \cite{Janet2018Accelerating}; introducing a grammar within the VAE to teach the model the fundamentals of SMILES strings \cite{Kusner2017Grammar}; using compiler theory to constrain the decoder to produce syntactically and semantically correct data \cite{Dai2018Syntax}; and using machine translation methods to convert between representations of sequences and/or grammar \cite{Winter2019Learning}.

Validity of generated sequences, however, is not the only thing that makes working with SMILES difficult. The sequential representation cannot represent similarity between molecules within edit distances \cite{Jin2018Junction} and a single molecule may have several different SMILES strings \cite{Bjerrum2017SMILES,Alperstein2019All}. The trade-off between processing this representation with text-based algorithms and discarding its chemical intuition calls for other approaches in the study and design of molecules.

\subsection{Molecular graphs}

An intuitive way of representing molecules is by means of its Lewis structure, computationally translated as a molecular graph. Given a graph $\mathcal{G} = \left(\mathcal{V}, \mathcal{E}\right)$, the atoms are represented as nodes $v_i \in \mathcal{V}$ and chemical bonds as edges $(v_i, v_j) \in \mathcal{E}$. Then, nodes and edges are decorated with labels indicating the atom type, bond type and so on. Many times, hydrogen atoms are treated implicitly for simplicity, since their presence can be inferred from traditional chemistry rules.

One of the first usages of graphs with DL for property prediction treated molecules as undirected cyclic graphs further processed using RNNs \cite{Lusci2013Deep}. Using graph convolutional networks \cite{Bruna2013Spectral}, Duvenaud \textit{et al.~} \cite{Duvenaud2015Convolutional} demonstrated the usage of machine-learned fingerprints to achieve better prediction of properties on neural networks. This approach started with a molecular graph and led to fixed-size fingerprints after several graph convolutions and a graph pooling layers. Kearnes \textit{et al.~} \cite{Kearnes2016Molecular} and Coley \textit{et al.~} \cite{Coley2017Convolutional} also evaluated the flexibility and promise of learned fingerprints from graph structures, especially because models could learn how to associate its chemical structure to their properties. Later, Gilmer \textit{et al.~} \cite{Gilmer2017Neural} unified graph convolutions as message-passing neural networks for quantum chemistry predictions, achieving DFT accuracy within their predictions of quantum properties, interpreting molecular 3D geometries as graphs with distance-labelled edges. Many more studies have explored the representative power of graphs within prediction tasks \cite{Hop2018Geometric,Yang2019Are}. These frameworks paved the way for using graph-based representations of molecules, especially because of their proximity with chemistry and geometrical interpretation.

The generation of graphs is, however, non-trivial, especially because of the challenges imposed by graph isomorphism. As in SMILES strings, one way to generate molecular graphs is by sequentially adding nodes and edges to the graph. The sequential nature of decisions over graphs have already been implemented using an RNN \cite{You2018GraphRNN} for arbitrary graphs. Specifically for a small subset of graphs corresponding to valid molecules, Li \textit{et al.~} \cite{Li2018Multi} used a decoder policy to improve the outcomes of the model. The conditional generation of graphs allowed for molecules to be created with improved drug-likeness, synthetic accessibility, as well as allowed scaffold-based generations from a template (Fig. \ref{fig:graphs}a). Similar procedure was adopted by Li \textit{et al.~} \cite{Li2018Multi}, in which a graph-generating decision process using RNNs was proposed for molecules. These node-by-node generation rely on the ordering of nodes in the molecular graph and thus suffer with random permutations of the nodes.

\begin{figure}[tb]
\centering
\includegraphics[width=\linewidth]{Figures/graphs.png}
\caption{Generative models for molecules using graphs. (a) Decision process for sequential generation of molecules from \cite{Li2018Multi}. (b) Junction Tree VAE for molecular graphs \cite{Jin2018Junction}. Figures reproduced from \cite{Li2018Multi,Jin2018Junction}.
\label{fig:graphs}}
\end{figure}

In the VAE world, several methods have been proposed to deal with the problem of directly generating graphs from a latent code \cite{Kipf2016Variational,Simonovsky2018GraphVAE,Grover2018Graphite,Samanta2018Designing,Liu2018Constrained}. However, when working with reconstructions, the problem of graph isomorphism cannot be addressed without expensive calculations \cite{Simonovsky2018GraphVAE}. Furthermore, graph reconstructions suffer from validity and accuracy \cite{Simonovsky2018GraphVAE}, except when these constraints are enforced in the graph generation process \cite{Samanta2018Designing,Liu2018Constrained,Ma2018Constrained}. Currently, one of the most successful approaches to translate molecular graphs into a meaningful latent code while avoiding node-by-node generation is the Junction Tree Variational Auto-Encoder (JT-VAE) \cite{Jin2018Junction}. In this framework, the molecular graph is first decomposed into a vocabulary of subpieces extracted from the training set, which include rings, functional groups and atoms (see Fig. \ref{fig:graphs}b). Then, the model is trained to encode the full graph and the tree structure resulting from the decomposition into two latent spaces. A two-part reconstruction process is necessary to recover the original molecule from the two vector representations. Remarkably, the JT-VAE achieves 100\% of validity when generating small molecules, as well as 100\% of novelty when sampling the latent code from a prior. Moreover, a meaningful latent space is also seen for this method, which is essential for optimization and the automatic design of molecules. The authors later improve over the JT-VAE with graph-to-graph translation and auto-regressive methods towards molecular optimization tasks \cite{Jin2019Learning, Jin2019Multi}.

Other auto-regressive approaches combining VAE and sequential graph generation have been proposed to generate and optimize molecules. Assouel \textit{et al.~} \cite{Assouel2018DEFactor} introduced a decoding strategy to output arbitrarily large molecules based on their graph representation. The model, named DEFactor, is end-to-end differentiable, dispenses retraining during the optimization procedure and achieved high reconstruction accuracy ($>80\%)$ even for molecules with about 25 heavy atoms. Despite the restrictions on node permutations, DEFactor allows the direct optimization of the graph conditioned to properties of interest. This and other similar models also allow the generation of molecules based on given scaffolds \cite{Lim2019Scaffold}.

Auto-regressive methods for molecules have also been reported with the use of RL. Zhou \textit{et al.~} \cite{Zhou2018Optimization} created a Markov decision process to produce molecules with targeted properties through multi-objective RL. Similarly to what is done with graphs, this strategy adds bonds and atoms sequentially. However, as the actions are restricted to chemically valid ones, the model scores 100\% of validity in the generated compounds. The optimization process forgoes pre-training and allows flexibility in the choice of the importances for each objectives. As a follow-up to this work, the same group reports the usage of this generation scheme as a decoder in a RL-enhanced VAE for molecules \cite{Kearnes2019Decoding}.

In line with the usage of sequences of actions to create graphs, several groups have been working on different ways to represent and generate graphs through sequences. One approach is to split a graph in permutation-invariant N-gram path sets \cite{Liu2018N}, in analogy with NLP with atoms as words and molecules as sentences. This representation performs competitively with message-passing neural networks in classification and regression tasks. The combination of strings and graph methods is also seen in the work of Krenn \textit{et al.~} \cite{Krenn2019SELFIES}, which developed a sequence representation for general-purpose graphs. Their scheme shows high robustness against mutations in sequences and outperforms other representations (including SMILES strings) in terms of diversity, validity, and reconstruction accuracy when employed in sequence-based VAEs.

The adversarial generation of graphs is still very incipient, and few models of GANs with graphs have been demonstrated \cite{Guo2018Deep,Bojchevski2018NetGAN,Xiong2019DynGraphGAN}. De Cao and Kipf \cite{DeCao2018MolGAN} demonstrated MolGAN, a GAN trained with RL for generating molecular graphs, but their system is too prone to mode collapse. The output structure can be made discrete by differentiable processes such as Gumbel-softmax \cite{Jang2016Categorical,Kusner2016GANS}, but balancing the adversarial training with molecular constraints requires more study. P\"olsterl and Wachinger \cite{Poelsterl2019Likelihood} builds on MolGAN by adding an adversarial training to avoid calculating the reconstruction loss and extending the graph isomorphism network \cite{Xu2018How} to multigraphs. Further improvements include the approach from Maziarka \textit{et al.~} \cite{Maziarka2019Mol}, which relies on the latent space of a pretrained JT-VAE to produce and optimize molecules, and the work of Fan and Huang \cite{Fan2019Labeled}, which aims to generate labeled graphs.

While the combination of DL with graph theory and molecular design seems promising, large room for improvement is available in the field of graph generation. Outputting an arbitrary graph is still an open problem and scalability to larger graphs is still an issue for graphs \cite{Gilmer2017Neural}. Comparing graph isomorphism is a class-NP problem, and the measure of similarity between two graphs usually resort to expensive kernels or edit distances \cite{Neuhaus2007Bridging}, as are other problems with reconstruction, ordering and so on \cite{Li2018Learning}. In some cases, a distance metric can be defined for such data structures \cite{Schieber2017Quantification,Choi2018Comparing} or a set of networks can be trained to recognize similarity patterns within graphs \cite{Ktena2017Distance}. Furthermore, adding attention to graphs could also help in classification tasks \cite{Do2018Attentional} or in the extraction of structure-property relationships \cite{Ryu2018Deeply}, and specifying grammar rules for graph reconstruction may lead to improved results in molecular validity and stereochemistry \cite{Kajino2018Molecular}.

\section{Challenges and outlook for generative models}

The use of deep generative models is a powerful approach for teaching computers to observe and understand the real world. Far from being just a big-data crunching tool, DL algorithms can provide insights that augment human creativity \cite{Kalchbrenner2016Neural}. Completely evaluating a generative model is difficult \cite{Theis2015note}, since we lack an expression for the statistical distribution being learned. Nevertheless, by approximating real-life data with an appropriate representation, we are embedding intuition in the machine's understanding. In a sense, this is what we do, as human beings, when formulating theoretical concepts on chemistry, physics and many other fields of study. Furthering our limited ability to probe the inner workings of deep neural networks will allow us to transform learned embeddings into logical rules.

In the field of chemical design, generative models are still in their infancy (see timeline summary in Fig. \ref{fig:summary}). While many achievements have been reported for such models, all of them share many challenges before a ``closed loop'' approach can be effectively implemented. Some of the trials are still inherent to all generative models: the generalization capability of a model, its power to make inferences on the real world, and capacity to bring novelty to it. In the chemical space, originality can be translated as the breadth and quality of possible molecules that the model can generate. To push forward the development of new technologies, we want our generative models to explore further regions of the chemical space in search of new solutions to current problems and extrapolate the training set, avoiding mode collapses or na\"ive interpolations. At the same time, we want it to capture rules inherent to the synthetically accessible space. Finally, we want to critically evaluate the performance of such models. Several benchmarks are being developed to assess the evolution of chemical generative models, providing quantitative comparisons beyond the mere prediction of solubility or drug-likeness \cite{Preuer2018Frechet,Polykovskiy2018Molecular,Wu2018MoleculeNet,Brown2019GuacaMol}.

\begin{figure}[tb]
\centering
\includegraphics[width=\linewidth]{Figures/summary.png}
\caption{Summary and timeline of current generative models for molecules. Newer models are located in the bottom of the diagram. Figures reproduced from \cite{Guimaraes2017Objective,Li2018Learning,DeCao2018MolGAN,Gomez-Bombarelli2018Automatic,Kusner2017Grammar,Jin2018Junction}.}
\label{fig:summary}
\end{figure}

The ease of navigation throughout the chemical space alone is not enough to determine a good model, however. Tailoring the generation of valid molecules for certain applications such as drug design \cite{Segler2018Generating} is also an important task. It reflects how well a generative model focus on the structure-property relationships for certain applications. This interpretation leads to even more powerful understandings of chemistry, and is closely tied to Gaussian processes \cite{Gomez-Bombarelli2018Automatic}, Bayesian optimization \cite{Haese2018PHOENICS}, and virtual screening.

In the generation process, outputting an arbitrary molecule is still an open problem and is closely conditioned to the representation. While SMILES have been demonstrated useful to represent molecules, graphs are able to convey real chemical features in it, which is useful for learning properties from structures. However, three-dimensional atomic coordinates should be considered for decoding as well. Recent works are going well beyond the connectivity of a molecule to provide equilibrium geometries of molecules using generative models \cite{Gebauer2018Generating,Noe2018Boltzmann,Gebauer2019Symmetry,Joergensen2019Atomistic,Mansimov2019Molecular}. This is crucial to bypass expensive sampling of low-energy configurations from the potential energy surface of molecules. We should expect advances not only on decoding and generating graphs from latent codes, but also in invertible molecular representations in terms of sequences, connectivity and spatial arrangement.

Finally, as the field of generative models advances, we should expect even more exciting models to design molecules. The normalizing-flow based Boltzmann Generator \cite{Noe2018Boltzmann} and GraphNVP \cite{Madhawa2019GraphNVP} are examples of models based on more recent strategies. Furthermore, the use of generative models to understand molecules in an unsupervised way advances along with the inverse design, from coarse-graining \cite{Wang2018Machine,Wang2018Coarse} and synthesizability of small molecules \cite{Bradshaw2019Generative,Bradshaw2019Model} to genetic variation in complex biomolecules \cite{Riesselman2018Deep}.

In summary, generative models hold promise to revolutionize the chemical design. Not only they allow optimizations or learn directly from data, but also bypass the necessity of a human supervising the generation of materials. Facing the challenges among these models is essential for accelerating the discovery cycle of new materials and, perhaps, improvement of the human understanding of the nature.

\begin{acknowledgement}
D.S.-K. acknowledges the MIT Nicole and Ingo Wender Fellowship and the MIT Robert Rose Presidential Fellowship for financial support. R.G.-B. thanks MIT DMSE and Toyota Faculty Chair for support.
\end{acknowledgement}

\bibliographystyle{spphys}