# Creativity in Machine Learning

Martin Thoma
E-Mail<EMAIL_ADDRESS>
###### Abstract

Recent machine learning techniques can be modified to produce creative
results. Those results did not exist before; it is not a trivial combination
of the data which was fed into the machine learning system. The obtained
results come in multiple forms: As images, as text and as audio.

This paper gives a high level overview of how they are created and gives some
examples. It is meant to be a summary of the current work and give people who
are new to machine learning some starting points.

##  I Introduction

According to [Gad06] creativity is “the ability to use your imagination to
produce new ideas, make things etc.” and imagination is “the ability to form
pictures or ideas in your mind”.

Recent advances in machine learning produce results which the author would
intuitively call creative. A high-level overview over several of those
algorithms are described in the following.

This paper is structured as follows: Section II introduces the reader on a
very simple and superficial level to machine learning, Section III gives
examples of creativity with images, Section IV gives examples of machines
producing textual content, and Section V gives examples of machine learning
and music. A discussion follows in Section VI.

##  II Basics of Machine Learning

The traditional approach of solving problems with software is to program
machines to do so. The task is divided in as simple sub-tasks as possible, the
subtasks are analyzed and the machine is instructed to process the input with
human-designed algorithms to produce the desired output. However, for some
tasks like object recognition this approach is not feasible. There are way to
many different objects, different lighting situations, variations in rotation
and the arrangement of a scene for a human to think of all of them and model
them. But with the internet, cheap computers, cameras, crowd-sourcing
platforms like Wikipedia and lots of Websites, services like Amazon Mechanical
Turk and several other changes in the past decades a lot of data has become
available. The idea of machine learning is to make use of this data.

A formal definition of the field of Machine Learning is given by Tom Mitchel
[Mit97]:

> A computer program is said to learn from experience $E$ with respect to some
> class of tasks $T$ and performance measure $P$, if its performance at tasks
> in $T$, as measured by $P$, improves with experience $E$.

This means that machine learning programs adjust internal parameters to fit
the data they are given. Those computer programs are still developed by
software developers, but the developer writes them in a way which makes it
possible to adjust them without having to re-program everything. Machine
learning programs should generally improve when they are fed with more data.

The field of machine learning is related to statistics. Some algorithms
directly try to find models which are based on well-known distribution
assumptions of the developer, others are more general.

A common misunderstanding of people who are not related in this field is that
the developers don’t understand what their machine learning program is doing.
It is understood very well in the sense that the developer, given only a pen,
lots of paper and a calculator could calculate the same result as the machine
does when he gets the same data. And lots of time, of course. It is not
understood in the sense that it is hard to make predictions how the algorithm
behaves without actually trying it. However, this is similar to expecting from
an electrical engineer to explain how a computer works. The electrical
engineer could probably get the knowledge he needs to do so, but the amount of
time required to understand such a complex system from basic building blocks
is a time-intensive and difficult task.

$\Sigma$ $\varphi$$\tiny x_{0}$$\tiny x_{1}$$\tiny x_{2}$$\tiny x_{3}$$\tiny
x_{n}$$w_{0}$$w_{1}$$w_{2}$$w_{3}$$w_{n}$$\vdots$ (a) Example of an artificial
neuron unit. $x_{i}$ are the input signals and $w_{i}$ are weights which have
to get learned. Each input signal gets multiplied with its weight, everything
gets summed up and the activation function $\varphi$ is applied.

(b) A visualization of a simple feed-forward neural network. The 5 input nodes
are red, the 2 bias nodes are gray, the 3 hidden units are green and the
single output node is blue.

Figure 1: Neural networks are based on simple units which get combined to
complex networks.

An important group of machine learning algorithms was inspired by biological
neurons and are thus called artificial neural networks. Those networks are
based on mathematical functions called artificial neurons which take
$n\in\mathbb{N}$ numbers $x_{1},\dots,x_{n}\in\mathbb{R}$ as input, multiply
them with weights $w_{1},\dots,w_{n}\in\mathbb{R}$, add them and apply a so
called activation function $\varphi$ as visualized in 1(a). One example of
such an activation function is the sigmoid function
$\varphi(x)=\frac{1}{1+e^{-x}}$. Those functions act as building blocks for
more complex systems as they can be chained and grouped in layers as
visualized in 1(b). The interesting question is how the parameters $w_{i}$ are
learned. This is usually done by an optimization technique called gradient
descent. The gradient descent algorithm takes a function which has to be
derivable, starts at any point of the surface of this error function and makes
a step in the direction which goes downwards. Hence it tries to find a minimum
of this high-dimensional function.

There is, of course, a lot more to say about machine learning. The interested
reader might want to read the introduction given by Mitchell [Mit97].

##  III Image Data

Applying a simple neural network on image data directly can work, but the
number of parameters gets extraordinary large. One would take one neuron per
pixel and channel. This means for
$$500\text{\,}\frac{\mathrm{px}}{}$\times$500\text{\,}\frac{\mathrm{px}}{}$$
RGB images one would get $750000$ input signals. To approach this problem, so
called Convolutional Neural Networks (CNNs) were introduced. Instead of
learning the full connection between the input layer and the first hidden
layer, those networks make use of convolution layers. Convolution layers learn
a convolution; this means they learn the weights of an image filter. An
additional advantage is that CNNs make use of spacial relationships of the
pixels instead of flattening the image to a stream of single numbers.

An excellent introduction into CNNs is given by [Nie15].

###  III-A Google DeepDream

The gradient descent algorithm which optimizes most of the parameters in
neural networks is well-understood. However, the effect it has on the
recognition system is difficult to estimate. [MOT15] proposes a technique to
analyze the weights learned by such a network. A similar idea was applied by
[VKMT13].

For example, consider a neural network which was trained to recognize various
images like bananas. This technique turns the network upside down and starts
with random noise. To analyze what the network considers bananas to look like,
the random noise image is gradually tweaked so that it generates the output
“banana”. Additionally, the changes can be restricted in a way that the
statistics of the input image have to be similar to natural images. One
example of this is that neighboring pixels are correlated.

Another technique is to amplify the output of layers. This was described in
[MOT15]:

> We ask the network: “Whatever you see there, I want more of it!” This
> creates a feedback loop: if a cloud looks a little bit like a bird, the
> network will make it look more like a bird. This in turn will make the
> network recognize the bird even more strongly on the next pass and so forth,
> until a highly detailed bird appears, seemingly out of nowhere.

Figure 2: Aurelia aurita Figure 3: DeepDream impression of Aurelia aurita

The name “Inceptionism” in the title of [MOT15] comes from the science-fiction
movie “Inception” (2010). One reason it might be chosen is because neural
networks are structured in layers. Recent publications tend to have more and
more layers [HZRS15]. The used jargon is to say they get “deeper”. As this
technique as published by Google engineers, the technique is called Google
DeepDream.

It has become famous in the internet [Red]. Usually, the images are generated
in iterations and in each iteration it is zoomed into the image.
Images and videos published by the Google engineers can be seen at [goo15].
Figure 2 shows the original image from which Figure 3 was created with the
deep dream algorithm.

###  III-B Artistic Style Imitation

A key idea of neural networks is that they learn different representations of
the data in each layer. In the case of CNNs, this can easily be visualized as
it was done in various papers [ZF14]. Usually, one finds that the network
learned to build edge detectors in the first layer and more complex structures
in the upper layers.

(a) Original Image

(b) Style image

(c) The artistic style of Van Gogh’s “Starry Night” applied to the photograph
of a Scottish Highland Cattle.

Figure 4: The algorithm takes both, the original image and the style image to
produce the result.

Gatys, Ecker and Bethge showed in [GEB15] that with a clever choice of
features it is possible to separate the general style of an image in terms of
local image appearance from the content of an image. They support their claim
by applying the style of different artists to an arbitrary image of their
choice.

This artistic style imitation can be seen itself as creative work. An example
is given by Figure 4. The code which created this example is available under
[Joh16].

Something similar was done by [SPB+14], where the style of a portrait
photograph was transferred to another photograph. A demo can be seen on
[Shi14].

###  III-C Drawing Robots

Patrick Tresset and Frédéric Fol Leymarie created a system called AIKON
(Automatic IKONic drawing) which can automatically generated sketches for
portraits [TL05]. AIKON takes a digital photograph, detects faces on them and
sketches them with a pen-plotter.

Tresset and Leymaire use $k$-means clustering [KMN+02] to segment regions of
the photograph with similar color which, in turn, will get a similar shading.

Such a drawing robot could apply machine learning techniques known from
computer vision for detecting the human. It could apply self-learning
techniques to draw results most similar to the artists impression of the
image. However, the system described in [TL05] seems not to be a machine
learning computer program according to the definition by Tom Mitchell [Mit97].

##  IV Text Data

Digital text is the first form of natural communication which involved
computers. It is used in the form of chats, websites, on collaborative
projects like Wikipedia, in scientific literature. Of course, it was used in
pre-digital times, too: In newspaper, in novels, in dramas, in religious texts
like the bible, in books for education, in notes from conversations.

This list could be continued and most of these kinds of texts are now
available in digital form. This digital form can be used to teach machines to
generate similar texts.

The most simple language model which is of use is an $n$-gram model. This
model makes use of sequences of the length $n$ to model language. It can be
used to get the probability of a third word, given the previous two words.
This way, a complete text can be generated word by word. Refinements and
extensions to this model are discussed in the field of Natural Language
Processing (NLP).

However, there are much more sophisticated models. One of those are character
predictors based on Recurrent Neural Networks (RNNs). Those character
predictors take a sequence of characters as input and predict the next
character. In that sense they are similar to the $n$-gram model, but operate
on a lower level. Using such a predictor, one can generate texts character by
character. If the model is good, the text can have the correct punctuation.
This would not be possible with a word predictor.

Character predictors can be implemented with RNNs. In contrast to standard
feed-forward neural networks like multilayer Perceptrons (MLPs) which was
shown in 1(b), those networks are trained to take their output at some point
as well as the normal input. This means they can keep some information over
time. One of the most common variant to implement RNNs is by using so called
Long short-term memory (LSTM) cells [HS97].

Recurrent networks apply two main ideas in order to learn: The first is called
unrolling and means that an recurrent network is imagined to be an infinite
network over time. At each time step the recurrent neurons get duplicated. The
second idea is weight sharing which means that those unrolled neurons share
the same weight.

###  IV-A Similar Texts Generation

Karpathy trained multiple character RNNs on different datasets and gave an
excellent introduction [Kar15b]. He trained it on Paul Graham’s essays, all
the works of Shakespeare, the Hutter Prize [hut]
$100\text{\,}\frac{\mathrm{MB}}{}$ dataset of raw Wikipedia articles, the raw
LaTeX source file of a book about algebraic stacks and geometry and Linux C
code.

With that training data, the models can generate similar texts. New works
which look like Shakespeare plays, new Wikipedia articles, new Linux code and
new papers about algebraic geometry can thus automatically be generated. At a
first glance, they do look authentic. The syntax was mostly used correctly,
the formatting looks as expected, the sentences are grammatically correct.
However, when one looks at the broader context it is easy to recognize that
the algorithm has no insight in what it is doing. It does match patterns
really well, but it fails to follow a central theme. In the context of C code
this means that new variables are introduced, but not used. At the same time,
variables which were not declared are used. In the context of Shakespear plays
this means that a lot of new characters are introduced, but they don’t speak
with each other or about each other.

The code used to generate these examples is available and ready to use through
[Kar15a]. A couple of examples are in Appendix A.

###  IV-B Chatbots

Chatbots are computer programs which participate in chat rooms as autonomous
agents. This means they have similar permissions and possibilities as usual
human users have, but users can trigger a set of commands to make the bot give
them valuable information or features.

A special category of chatbots are such bots which actively participate in the
conversation, which is usually not the case. One of the earliest programs in
this category is ELIZA, a bot created by Joseph Weizenbaum in the 1960s
[Wei76]. This program had a set of patterns implemented to which it would
reply in a seemingly smart way in a psychologists fashion. This means quite
often the program would simply repeat the last sentence and add something
meaningless like “How do you feel about it?”. According to [Cur14], Weizenbaum
once found his secretary — who was aware of the fact that this is a computer
program — chatting with the machine. When he looked over her shoulder, she
asked him “would you mind leaving the room”.

Today, much more sophisticated chatbots exist. They make use of the vast
amount of data which is available by millions of Wikipedia articles, chat
protocols, websites, help desk protocols, subtitles of movies as well as the
astonishing increase in computing power to train RNNs and language models
similar to the ones described before.

Interesting results like the following were obtained by [VL15]:

> Human: what is the purpose of life ?
> Machine: to serve the greater good .
> Human: what is the purpose of living ?
> Machine: to live forever .

##  V Audio Data

Common machine learning tasks which involve audio data are speech recognition,
speaker identification, identification of songs. This leads to some less-
common, but interesting topics: The composition of music, the synthesizing of
audio as art. While the composition might be considered in Section IV, we will
now investigate the work which was done in audio synthesization.

###  V-A Emily Howell

David Cope created a project called “Experiments in Musical Intelligence”
(short: EMI or Emmy) in 1984 [Cop87]. He introduces the idea of seeing music
as a language which can be analyzed with natural language processing (NLP)
methods. Cope mentions that EMI was more useful to him, when he used the
system to “create small phrase-size textures as next possibilities using its
syntactic dictionary and rule base” [Cop87].

In 2003, Cope started a new project which was based on EMI: Emily Howell
[Cop13]. This program is able to “creat[e] both highly authentic replications
and novel music compositions”. The reader might want to listen to [Cop12] to
get an impression of the beauty of the created music.

According to Cope, an essential part of music is “a set of instructions for
creating different, but highly related self-replications”. Emmy was programmed
to find this set of instructions. It tries to find the “signature” of a
composer, which Cope describes as “contiguous patterns that recur in two or
more works of the composer”.

The new feature of Emily Howell compared to Emmy is that Emily Howell does not
necessarily remain in a single, already known style.

Emily Howell makes use of association network. Cope emphasizes that this is
not a form of a neural network. However, it is not clear from [Cop13] how
exactly an association network is trained. Cope mentions that Emily Howell is
explained in detail in [Cop05].

###  V-B GRUV

Recurrent neural networks — LSTM networks, to be exact — are used in [NV15]
together with Gated Recurrent Units (GRU) to build a network which can be
trained to generate music. Instead of taking notes directly or MIDI files,
Nayebi and Vitelli took raw audio waveforms as input. Those audio waveforms
are feature vectors given for time steps $0,1,\dots,t-1,t$. The network is
given those feature vectors $X_{1},\dots,X_{t}$ and has to predict the
following feature vector $X_{t+1}$. This means it continues the music. As the
input is continuous, the problem was modeled as a regression task. Discrete
Fourier Transformation (DFT) was used on chunks of length $N$ of the music to
obtain features in the frequency domain.

An implementation can be found at [VN15] and a demonstration can be found at
[Vit15].

###  V-C Audio Synthesization

Audio synthesization is generating new audio files. This can either be music
or speech. With the techniques described before, neural networks can be
trained to generate music note by note. However, it is desirable to allow
multiple notes being played at the same time.

This idea and some others were applied by Daniel Johnson. He wrote a very good
introduction into neural networks for music composition which explains those
ideas [Joh15b]. Example compositions are available there, too. He also made
the code for his Biaxial Recurrent Neural Network available under [Joh15a].

##  VI Discussion

What does these examples mean for our understanding of creativity? Does it
influence how much we value art? Could we define art and creativity better
after having those and similar results?

I think we might readjust our understanding of creativity just like we
adjusted our understanding of algorithmically hard problems after Deep Blue
won against the reigning world chess champion Garry Kasparov in 1997.

However, by now it is obvious that machine learning algorithms cannot compete
with human artists. Today’s state of the art algorithms which are purely based
on machine learning don’t follow a central theme. They lack the ability to
plan. Although clever algorithms were implemented for composing music, it
seems as if there is still a lot of supervision involved.

## References

  * [Cop87] D. Cope, “Experiments in music intelligence (emi),” 1987. [Online]. Available: http://hdl.handle.net/2027/spo.bbp2372.1987.025
  * [Cop05] ——, _Computer models of musical creativity_. MIT Press Cambridge, 2005.
  * [Cop12] ——, “Emily howell fugue,” YouTube, Oct. 2012. [Online]. Available: https://www.youtube.com/watch?v=jLR-_c_uCwI
  * [Cop13] ——, “The well-programmed clavier: Style in computer music composition,” _XRDS: Crossroads, The ACM Magazine for Students_ , vol. 19, no. 4, pp. 16–20, 2013. [Online]. Available: http://dl.acm.org/citation.cfm?id=2460444
  * [Cur14] A. Curtis, “Now then,” BBC, Jul. 2014. [Online]. Available: http://www.bbc.co.uk/blogs/adamcurtis/entries/78691781-c9b7-30a0-9a0a-3ff76e8bfe58
  * [Gad06] A. Gadsby, Ed., _Dictionary of Contemporary English_. Pearson Education Limited, 2006.
  * [GEB15] L. A. Gatys, A. S. Ecker, and M. Bethge, “A neural algorithm of artistic style,” _arXiv preprint arXiv:1508.06576_ , 2015. [Online]. Available: http://arxiv.org/abs/1508.06576
  * [goo15] “Inceptionism: Going deeper into neural networks,” Google Photos, Jun. 2015. [Online]. Available: https://goo.gl/Bydofw
  * [HS97] S. Hochreiter and J. Schmidhuber, “Long short-term memory,” _Neural computation_ , vol. 9, no. 8, pp. 1735–1780, 1997. [Online]. Available: http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=6795963
  * [hut] “50’000 euro prize for compressing human knowledge.” [Online]. Available: http://prize.hutter1.net/
  * [HZRS15] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” _arXiv preprint arXiv:1512.03385_ , 2015. [Online]. Available: http://arxiv.org/abs/1512.03385
  * [Joh15a] D. Johnson, “Biaxial recurrent neural network for music composition,” GitHub, Aug. 2015. [Online]. Available: https://github.com/hexahedria/biaxial-rnn-music-composition
  * [Joh15b] ——, “Composing music with recurrent neural networks,” Personal Blog, Aug. 2015\. [Online]. Available: http://www.hexahedria.com/2015/08/03/composing-music-with-recurrent-neural-networks/
  * [Joh16] J. Johnson, “neural-style,” GitHub, Jan. 2016. [Online]. Available: https://github.com/jcjohnson/neural-style
  * [Kar15a] A. Karpathy, “char-rnn,” GitHub, Nov. 2015. [Online]. Available: https://github.com/karpathy/char-rnn
  * [Kar15b] ——, “The unreasonable effectiveness of recurrent neural networks,” Personal Blog, May 2015. [Online]. Available: http://karpathy.github.io/2015/05/21/rnn-effectiveness/
  * [KMN+02] T. Kanungo, D. Mount, N. Netanyahu, C. Piatko, R. Silverman, and A. Wu, “An efficient k-means clustering algorithm: analysis and implementation,” _Pattern Analysis and Machine Intelligence, IEEE Transactions on_ , vol. 24, no. 7, pp. 881–892, Jul 2002.
  * [Mit97] T. M. Mitchell, _Machine learning_ , ser. McGraw Hill series in computer science. McGraw-Hill, 1997.
  * [MOT15] A. Mordvintsev, C. Olah, and M. Tyka, “Inceptionism: Going deeper into neural networks,” googleresearch.blogspot.co.uk, Jun. 2015. [Online]. Available: http://googleresearch.blogspot.de/2015/06/inceptionism-going-deeper-into-neural.html
  * [Nie15] M. A. Nielsen, _Neural Networks and Deep Learning_. Determination Press, 2015. [Online]. Available: http://neuralnetworksanddeeplearning.com/chap6.html#introducing_convolutional_networks
  * [NV15] A. Nayebi and M. Vitelli, “GRUV: Algorithmic music generation using recurrent neural networks,” 2015. [Online]. Available: http://cs224d.stanford.edu/reports/NayebiAran.pdf
  * [Red] “Deepdream,” Reddit. [Online]. Available: https://www.reddit.com/r/deepdream/
  * [Shi14] Y. Shih, “Style transfer for headshot portraits,” YouTube, Jun. 2014. [Online]. Available: https://www.youtube.com/watch?v=Hj5lGFzlubU
  * [SPB+14] Y. Shih, S. Paris, C. Barnes, W. T. Freeman, and F. Durand, “Style transfer for headshot portraits,” _ACM Transactions on Graphics (TOG)_ , vol. 33, no. 4, p. 148, 2014. [Online]. Available: http://dl.acm.org/citation.cfm?id=2601137
  * [TL05] P. Tresset and F. F. Leymarie, “Generative portrait sketching,” in _Proceedings of VSMM_ , 2005, pp. 739–748.
  * [Vit15] M. Vitelli, “Algorithmic music generation with recurrent neural networks,” YouTube, Jun. 2015. [Online]. Available: https://youtu.be/0VTI1BBLydE
  * [VKMT13] C. Vondrick, A. Khosla, T. Malisiewicz, and A. Torralba, “Hoggles: Visualizing object detection features,” in _Computer Vision (ICCV), 2013 IEEE International Conference on_. IEEE, 2013, pp. 1–8. [Online]. Available: http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6751109
  * [VL15] O. Vinyals and Q. Le, “A neural conversational model,” _arXiv preprint arXiv:1506.05869_ , Jul. 2015. [Online]. Available: http://arxiv.org/abs/1506.05869v2
  * [VN15] M. Vitelli and A. Nayebi, “GRUV,” Aug. 2015. [Online]. Available: https://github.com/MattVitelli/GRUV
  * [Wei76] J. Weizenbaum, _Computer Power and Human Reason: From Judgement to Calculation_. W.H.Freeman & Co Ltd, 1976\.
  * [ZF14] M. D. Zeiler and R. Fergus, “Visualizing and understanding convolutional networks,” in _Computer Vision–ECCV 2014_. Springer, 2014, pp. 818–833.

## Glossary

CNN

    Convolutional Neural Network
DFT

    Discrete Fourier Transformation
GRU

    Gated Recurrent Units
LSTM

    Long short-term memory
MLP

    multilayer Perceptron
NLP

    Natural Language Processing
RNN

    Recurrent Neural Network

##  Appendix A Automatically generated Texts

The following texts were generated by [Kar15a] and published by Karpathy on
[Kar15b]. This is meant to be a copy for convenience and the case that the
website is not reachable.

###  A-A Shakespeare

    PANDARUS:
    Alas, I think he shall be come approached and the day
    When little srain would be attain’d into being never fed,
    And who is but a chain and subjects of his death,
    I should not sleep.

    Second Senator:
    They are away this miseries, produced upon my soul,
    Breaking and strongly should be buried, when I perish
    The earth and thoughts of many states.

    DUKE VINCENTIO:
    Well, your wit is in the care of side and that.

    Second Lord:
    They would be ruled after this chamber, and
    my fair nues begun out of the fact, to be conveyed,
    Whose noble souls I’ll have the heart of the wars.

    Clown:
    Come, sir, I will make did behold your worship.

    VIOLA:
    I’ll drink it.

###  A-B Wikipeda

    Naturalism and decision for the majority of Arab countries’ capitalide was grounded
    by the Irish language by [[John Clair]], [[An Imperial Japanese Revolt]], associated
    with Guangzham’s sovereignty. His generals were the powerful ruler of the Portugal
    in the [[Protestant Immineners]], which could be said to be directly in Cantonese
    Communication, which followed a ceremony and set inspired prison, training. The
    emperor travelled back to [[Antioch, Perth, October 25|21]] to note, the Kingdom
    of Costa Rica, unsuccessful fashioned the [[Thrales]], [[Cynth’s Dajoard]], known
    in western [[Scotland]], near Italy to the conquest of India with the conflict.
    Copyright was the succession of independence in the slop of Syrian influence that
    was a famous German movement based on a more popular servicious, non-doctrinal
    and sexual power post. Many governments recognize the military housing of the
    [[Civil Liberalization and Infantry Resolution 265 National Party in Hungary]],
    that is sympathetic to be to the [[Punjab Resolution]]
    (PJS)[http://www.humah.yahoo.com/guardian.
    cfm/7754800786d17551963s89.htm Official economics Adjoint for the Nazism, Montgomery
    was swear to advance to the resources for those Socialism’s rule,
    was starting to signing a major tripad of aid exile.]]

###  A-C Linux Code, 1

    /*
     * Increment the size file of the new incorrect UI_FILTER group information
     * of the size generatively.
     */
    static int indicate_policy(void)
    {
      int error;
      if (fd == MARN_EPT) {
        /*
         * The kernel blank will coeld it to userspace.
         */
        if (ss->segment < mem_total)
          unblock_graph_and_set_blocked();
        else
          ret = 1;
        goto bail;
      }
      segaddr = in_SB(in.addr);
      selector = seg / 16;
      setup_works = true;
      for (i = 0; i < blocks; i++) {
        seq = buf[i++];
        bpf = bd->bd.next + i * search;
        if (fd) {
          current = blocked;
        }
      }
      rw->name = "Getjbbregs";
      bprm_self_clearl(&iv->version);
      regs->new = blocks[(BPF_STATS << info->historidac)] | PFMR_CLOBATHINC_SECONDS << 12;
      return segtable;
    }

###  A-D Linux Code, 2

    /*
     *  Copyright (c) 2006-2010, Intel Mobile Communications.  All rights reserved.
     *
     *   This program is free software; you can redistribute it and/or modify it
     * under the terms of the GNU General Public License version 2 as published by
     * the Free Software Foundation.
     *
     *        This program is distributed in the hope that it will be useful,
     * but WITHOUT ANY WARRANTY; without even the implied warranty of
     *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
     *
     *  GNU General Public License for more details.
     *
     *   You should have received a copy of the GNU General Public License
     *    along with this program; if not, write to the Free Software Foundation,
     *  Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
     */

    #include <linux/kexec.h>
    #include <linux/errno.h>
    #include <linux/io.h>
    #include <linux/platform_device.h>
    #include <linux/multi.h>
    #include <linux/ckevent.h>

    #include <asm/io.h>
    #include <asm/prom.h>
    #include <asm/e820.h>
    #include <asm/system_info.h>
    #include <asm/setew.h>
    #include <asm/pgproto.h>

    #define REG_PG    vesa_slot_addr_pack
    #define PFM_NOCOMP  AFSR(0, load)
    #define STACK_DDR(type)     (func)

    #define SWAP_ALLOCATE(nr)     (e)
    #define emulate_sigs()  arch_get_unaligned_child()
    #define access_rw(TST)  asm volatile("movd %%esp, %0, %3" : : "r" (0));   \
      if (__type & DO_READ)

    static void stat_PC_SEC __read_mostly offsetof(struct seq_argsqueue, \
              pC>[1]);

    static void
    os_prefix(unsigned long sys)
    {
    #ifdef CONFIG_PREEMPT
      PUT_PARAM_RAID(2, sel) = get_state_state();
      set_pid_sum((unsigned long)state, current_state_str(),
               (unsigned long)-1->lr_full; low;
    }


#  Six proofs of the Fáry–Milnor theorem

Anton Petrunin and Stephan Stadler

###### Abstract

We survey known proofs of the Fáry–Milnor theorem; it states that any
nontrivial knot makes at least two full turns.

## INTRODUCTION.

The following problem was posed by Karol Borsuk [4].

Show that the total curvature of any nontrivial knot is at least
$4{\cdot}\pi$.

It is known by many proofs based on different ideas. We sketch several
solutions, one solution per section; each can be read independently.

This problem also has a number of refinements and generalizations; in
particular, a strict inequality holds — this is the famous _Fáry–Milnor
theorem_. However, for the sake of simplicity, we stick to the original
formulation.

In order to continue, we need to agree on a definition of knot and explain
what a _nontrivial knot_ is. Despite the intuitive idea of a knot as a _cyclic
rope_ , the simplest formal definition uses polygonal curves. It turns out
that this definition is also best suited for our purposes.

A _knot_ (more precisely, a _tame knot_) is a simple closed polygonal curve in
the Euclidean space $\mathbb{R}^{3}$ (_simple_ means _no self-intersections_).

The solid triangle with vertices $a$, $b$, and $c$ will be denoted by
$\text{\char 115}abc$. It is defined as the convex hull of the points $a$,
$b$, and $c$; the points $a$, $b$, and $c$ are assumed to be distinct, but
they might lie on one line.

We define a _triangular isotopy_ of a knot to be the generation of a new knot
from the original one by means of the following two operations:

  * •

Assume $[p,q]$ is an edge of the knot and $x$ is a point such that the solid
triangle $\text{\char 115}pqx$ has no common points with the knot except for
the edge $[p,q]$. Then we can replace the edge $[p,q]$ with the two adjacent
edges $[p,x]$ and $[x,q]$.

  * •

We can also perform the inverse operation. That is, if for two adjacent edges
$[p,x]$ and $[x,q]$ of a knot the triangle $\text{\char 115}pqx$ has no common
points with the knot except for the points on the edges $[p,x]$ and $[x,q]$,
then we can replace $[p,x]$ and $[x,q]$ by one edge $[p,q]$.

Polygons that arise from one another by a finite sequence of triangular
isotopies are called _isotopic_. A knot that is not isotopic to a triangle
(that is, a simple polygonal curve with three vertices) is called
_nontrivial_.

Figure 1: Trefoil knot.

The trefoil knot shown on Figure 1 gives a simple example of a nontrivial
knot. A proof that it is nontrivial can be found in any textbook on knot
theory. The most elementary and visual proof is based on the so-called
_tricolorability_ of knot diagrams [1, Section 1.5].

The total curvature of a smooth curve is usually defined as the integral of
its curvature. For polygons, it is defined as the sum of its external angles.
It is well known that the total curvature of a curve cannot be smaller than
the total curvature of an inscribed polygonal curve (see, for example, [14]).
In fact, the total curvature of a curve can be defined as the least upper
bound on the total curvature of inscribed polygonal curves [2, 18]. This
definition agrees with the definition given for smooth curves, and it makes
sense for any simple curve. The total curvature of a curve $\alpha$ will be
denoted by $\Phi(\alpha)$.

All this leads to the following reformulation which we are going to prove.

######  Main theorem.

$\Phi(\alpha)\geqslant 4{\cdot}\pi$ for any nontrivial knot $\alpha$.

##  1 Milnor–Fenner.

One of the first solutions to the problem was found by John Milnor [12]. In
this section, we present an amusing interpretation of his proof found by
Stephen Fenner [10]. Just like the original version, it is based on the
following sufficient condition for the triviality of a knot.

######  Proposition 1.

Assume that a height function $(x,y,z)\to z$ has only one local maximum on a
simple closed polygonal curve $\alpha$ and all the vertices of the polygonal
curve are at different heights. Then $\alpha$ is a trivial knot.

The proof is a straightforward construction of a triangular isotopy.

###### Proof.

Let $\alpha=p_{1}\dots p_{n}$. We can assume that $n\geqslant 4$; otherwise
the statement is trivial. Note that the height function also has a unique
local minimum, and $\alpha$ can be divided into two arcs from the min-vertex
to the max-vertex with a monotonic height function.

Consider the three vertices with the largest height; they have to include the
max-vertex and two more. Note that these three vertices are consecutive in the
polygonal curve; without loss of generality, we can assume that they are
$p_{n-1}$, $p_{n}$, and $p_{1}$.

Note that the solid triangle $\text{\char 115}p_{n-1}p_{n}p_{1}$ does not
intersect any edge of $\alpha$ except the two adjacent edges $[p_{n-1},p_{n}]$
and $[p_{n},p_{1}]$; see Figure 3. Indeed, if $\text{\char
115}p_{n-1}p_{n}p_{1}$ intersects $[p_{1},p_{2}]$, then, since $p_{2}$ lies
below $\text{\char 115}p_{n-1}p_{n}p_{1}$, the edge $[p_{1},p_{2}]$ must
intersect $[p_{n-1},p_{n}]$; the latter is impossible since $\alpha$ is
simple.

The same way, one can show that $\text{\char 115}p_{n-1}p_{n}p_{1}$ cannot
intersect $[p_{n-2},p_{n-1}]$. The remaining edges lie below $\text{\char
115}p_{n-1}p_{n}p_{1}$, hence they cannot intersect this triangle.

Applying a triangular isotopy to $\text{\char 115}p_{n-1}p_{n}p_{1}$ we get a
simple closed polygonal curve $\alpha^{\prime}=\nobreak p_{1}\dots p_{n-1}$
which is isotopic to $\alpha$.

Since all the vertices $p_{i}$ have different heights, the assumption of the
proposition holds for $\alpha^{\prime}$.

Repeating this procedure $n-3$ times we get a triangle. Hence $\alpha$ is a
trivial knot. ∎

[t(-0mm),b(0mm),r(4mm),l(0mm)]asy/Ui(1) [l]24.5,10;$v_{i}$ [lt]22,5;$v_{i-1}$
[tl]18,10.5;$\varphi_{i}$ [br]5,21;$U_{i}$

Figure 2: Triangular isotopy.

Figure 3: Spherical slice.

###### Proof of the main theorem.

Let $\alpha=p_{1}\dots p_{n}$ be a nontrivial polygonal knot. Denote by
$v_{i}$ the unit vector in the direction of $p_{i+1}-p_{i}$; we assume that
$p_{n}=p_{0}$.

Consider the set $U_{i}$ formed by all unit vectors $u$ such that
$\measuredangle(u,v_{i})\geqslant\tfrac{\pi}{2}$ and
$\measuredangle(u,v_{i-1})\leqslant\tfrac{\pi}{2}$; see Figure 3. Note that
$u\in\nobreak U_{i}$ if and only if the function $x\mapsto\langle u,x\rangle$
has a local maximum at $p_{i}$ on $\alpha$; here $\langle\ ,\ \rangle$ denotes
the scalar product.

Let us choose $(x,y,z)$-coordinates in the space so that the $z$-axis points
in the direction of $u$. Then according to Proposition 1, the function
$p\mapsto\langle u,p\rangle$ has at least two local maxima on $\alpha$. It
follows that the sets $U_{1},\dots,U_{n}$ cover each point on the unit sphere
$\mathbb{S}^{2}$ twice.

Recall that $\mathop{\rm area}\nolimits\mathbb{S}^{2}=4{\cdot}\pi$. Observe
that $\varphi_{i}=\measuredangle(v_{i-1},v_{i})$ is the external angle of
$\alpha$ at $p_{i}$. Note that $U_{i}$ is a slice of the sphere between two
meridians meeting at angle $\varphi_{i}$, therefore $U_{i}$ occupies a
$\tfrac{\varphi_{i}}{2{\cdot}\pi}$ portion of the whole sphere; so,
$2{\cdot}\varphi_{i}=\mathop{\rm area}\nolimits U_{i}$. Since the sets
$U_{1},\dots,U_{n}$ cover $\mathbb{S}^{2}$ twice, we get

$\Phi({\alpha})=\varphi_{1}+\dots+\varphi_{n}=\tfrac{1}{2}\cdot(\mathop{\rm
area}\nolimits U_{1}+\dots+\mathop{\rm area}\nolimits
U_{n})\geqslant\tfrac{2}{2}\cdot\mathop{\rm
area}\nolimits\mathbb{S}^{2}=4{\cdot}\pi.$

∎

##  2 Fáry.

In this section, we sketch the solution of István Fáry [9] which was published
before Milnor’s proof.

We start with Crofton-type formulas for total curvature [18, Proposition 4.1].
Given a curve $\alpha$ in $\mathbb{R}^{3}$ and a unit vector $u$, denote by
$\alpha_{u^{\perp}}$ and $\alpha_{u}$ the projections of $\alpha$ to the plane
perpendicular to $u$ and the line parallel to $u$, respectively. Let us denote
by $\overline{f(u)}$ the average value of $f(u)$ for a function
$f\colon\mathbb{S}^{2}\to\mathbb{R}$.

######  Crofton-type formula 2.

Let $\alpha$ be a polygonal curve in $\mathbb{R}^{3}$. Then

$\displaystyle\Phi({\alpha})$
$\displaystyle=\overline{\Phi({\alpha_{u^{\perp}}})}=\overline{\Phi({\alpha_{u}})}.$

###### Proof.

Observe that it is sufficient to check the identities for $\alpha$ made of two
edges. Denote its external angle by $\varphi$, so $\Phi({\alpha})=\varphi$.
Observe that each term in the formula is proportional to $\varphi$. Therefore,
it is sufficient to consider the case $\varphi=\pi$.

In other words, we can assume that $\alpha$ is made of two edges that turn in
the opposite direction. Note that the same holds for $\alpha_{u^{\perp}}$ if
$u$ is not parallel to an edge of $\alpha$. Similarly, the same holds for
$\alpha_{u}$ if $u$ is not perpendicular to an edge of $\alpha$. Therefore,
$\Phi({\alpha_{u^{\perp}}})=\Phi({\alpha_{u}})=\pi$ for almost all
$u\in\mathbb{S}^{2}$. In particular,
$\overline{\Phi({\alpha_{u^{\perp}}})}=\overline{\Phi({\alpha_{u}})}=\pi$
which proves the statement. ∎

The original version of Milnor’s proof used the identity
$\Phi({\alpha})=\overline{\Phi({\alpha_{u}})}$; in Fenner’s version of the
proof, it was hidden under the rug.

Fáry’s proof is based on the identity
$\Phi({\alpha})=\overline{\Phi({\alpha_{u^{\perp}}})}$ and the following
inequality for total curvature. Suppose $\alpha=p_{1}\dots p_{n}$ is a simple
closed polygonal curve in $\mathbb{R}^{3}$ and $o\notin\alpha$. Let us define
the _angular length_ of $\alpha$ with respect to $o$ as the sum

$\Psi_{o}(\alpha)=\measuredangle p_{1}op_{2}+\dots+\measuredangle
p_{n-1}op_{n}+\measuredangle p_{n}op_{1}.$

######  Proposition 3.

For any simple closed polygonal curve and any $o\notin\alpha$, we have

$\Psi_{o}(\alpha)\leqslant\Phi({\alpha}).$

Figure 4: Definitions of angles.

###### Proof.

Let $\alpha=p_{1}\dots p_{n}$; for each $i$, set

$\displaystyle\varphi_{i}$ $\displaystyle=\pi-\measuredangle
p_{i-1}p_{i}p_{i+1},$ $\displaystyle\psi_{i}$ $\displaystyle=\measuredangle
p_{i-1}op_{i},$ $\displaystyle\theta_{i}$ $\displaystyle=\measuredangle
op_{i}p_{i+1};$

see Figure 4. Here we assume that the indices are taken modulo $n$; in
particular, $p_{n}=\nobreak p_{0}$.

Note that $\varphi_{i}$ is the external angle at $p_{i}$; therefore

$\Phi({\alpha})=\varphi_{1}+\dots+\varphi_{n}.$

The directions of $p_{i}-p_{i-1}$, $o-p_{i}$, and $p_{i+1}-p_{i}$ make angles
$\psi_{i}+\theta_{i-1}$, $\theta_{i}$, and $\varphi_{i}$ to each other.
Applying the triangle inequality for these angles, we get

$\varphi_{i}\geqslant\psi_{i}+\theta_{i-1}-\theta_{i}.$

Summing up, we get

$\varphi_{1}+\dots+\varphi_{n}\geqslant\psi_{1}+\dots+\psi_{n},$

and the result follows. ∎

###### Proof of the main theorem.

Consider a projection $\alpha_{u^{\perp}}$ of the knot $\alpha$ to a plane in
_general position_ (this time it means that the self-intersections of the
projection are at most double points and the projection of each edge is not
degenerate). The closed polygonal curve $\alpha_{u^{\perp}}$ divides the plane
into domains, one of which is unbounded, denoted by $U$, and the others are
bounded.

Figure 5: Projection of an unknot.

Figure 6: Projection of a knot.

First, note that all domains can be colored in a chessboard order; that is,
they can be colored in black and white in such a way that domains with common
borderline get different colors [1, Exercise 2.27]. If the unbounded domain is
colored white and every other domain is colored black (see Figure 6), then one
can untie the knot by flipping these domains one by one.111It is instructive
to give a formal proof of the last statement; that is, show that if there is
only one white region, then $\alpha$ is trivial.

Therefore, there is a white bounded domain; denote it by $D$ (see Figure 6).
The domain $D$ cannot adjoin $U$, since they have the same color. Fix a point
$o$ in this domain.

Since any ray from $o$ crosses $\alpha_{u^{\perp}}$ twice, we get
$\Psi_{o}(\alpha_{u^{\perp}})\geqslant 4{\cdot}\pi$; that is, the angular
length of $\alpha_{u^{\perp}}$ with respect to $o$ is at least $4{\cdot}\pi$.
By Proposition 3, we have

$\Phi({\alpha_{u^{\perp}}})\geqslant 4{\cdot}\pi.$

This is true for any $u$ in general position. The remaining directions
contribute nothing to the average value. It remains to apply the Crofton-type
formula $\Phi({\alpha})=\overline{\Phi({\alpha_{u^{\perp}}})}$. ∎

##  3 Pannwitz–Hopf–Schmitz–Denne.

Fáry’s paper [9] is ended with the following note: “I just received a letter
from Mr. Borsuk, which says that Theorem 3 (our main theorem) has been proved
independently by Mr. H. Hopf. It uses the theorem of Miss Pannwitz, which
ensures that for any knot there is a line that crosses it at least in four
points.” This proof is the subject of this section.

The main step in the proof is the existence of the so-called _alternated
quadrisecant_ of a knot $\alpha$; that is, there is a line $\ell$ that shares
with $\alpha$ four points $a$, $b$, $c$, and $d$ that appear on $\ell$ in the
same order and have cyclic order $a$, $c$, $b$, $d$ on $\alpha$. See Figure 7.

Figure 7: Alternated quadrisecant.

The question about the existence of a quadrisecant was posed by Otto Toeplitz
and answered by Erika Pannwitz for tame knots in _general position_ [13]. She
only proved the existence of a quadrisecant, but the existence of an
alternated quadrisecant can be extracted from her proof. Elizabeth Denne had
generalized this result to all knots [6, 7]. But for us tame knots in general
position will be sufficient; namely, we need the following.

######  Proposition 4.

Any nontrivial knot $\alpha$ in general position admits an _alternated
quadrisecant_.

The precise meaning of general position will be clear from the proof; what is
important is that any knot is arbitrarily close to a knot in general position.

###### Proof of the main theorem modulo Proposition 4.

Let $\alpha=p_{1}\dots p_{n}$ be a knot in general position. Suppose $a$, $b$,
$c$, and $d$ be the points as in the definition of an alternated quadrisecant.
Then $acbd$ is an inscribed quadrangle with all external angles equal to
$\pi$. Therefore, $\Phi({abcd})=4{\cdot}\pi$.

Since the total curvature of an inscribed polygonal curve cannot be larger
than the total curvature of the original curve, we get that
$\Phi({\alpha})\geqslant\nobreak 4{\cdot}\pi$.

Finally, for any knot $\beta=q_{1}\dots q_{n}$ there is an arbitrarily close
knot $\alpha=\nobreak p_{1}\dots p_{n}$ in general position; in particular,
for any $\varepsilon>0$ we can assume that
$\Phi({\beta})>\Phi({\alpha})-\varepsilon$. It follows that
$\Phi({\beta})>4{\cdot}\pi-\varepsilon$ for any positive $\varepsilon$ — hence
the result. ∎

In the proof of the proposition, we will use the following characterization of
the trivial knot.

######  Lemma 5.

A knot $\alpha$ is trivial if there exists a piecewise linear map $F$ from the
disc $\mathbb{D}$ to $\mathbb{R}^{3}$ such that the restriction of $F$ to the
boundary $\partial\mathbb{D}=\mathbb{S}^{1}$ is a degree-one map to $\alpha$
and $F$ does not map interior points of $\mathbb{D}$ to $\alpha$.

This statement can be deduced from the loop theorem — a heavy weapon of
3-dimensional topology. For those who are familiar with the loop theorem, it
would be an exercise; otherwise, we suggest taking it for granted. In the
following proof, we follow closely the presentation of Carsten Schmitz [16]
and the original argument of Erika Pannwitz.

###### Proof of Proposition 4.

We may assume that $\alpha$ comes with a 1-periodic piecewise linear
parametrization by $\mathbb{R}$; so the space of oriented chords of $\alpha$
can be identified with the open cylinder $\mathbb{S}^{1}\times(0,1)$, where
$\mathbb{S}^{1}=\mathbb{R}/\mathbb{Z}$. Namely, we assume that a pair
$(x,y)\in\mathbb{S}^{1}\times(0,1)$ corresponds to the oriented chord with the
ends at $\alpha(x)$ and $\alpha(x+y)$.

Choose a pair $(x,y)\in\mathbb{S}^{1}\times(0,1)$. Let us denote by $r(x,y)$
the ray that starts at $\alpha(x)$ and goes in the direction opposite to
$\alpha(x+y)$; see Figure 9. We write $(x,y)\in\nobreak C_{3}$ if $r(x,y)$
crosses $\alpha$ at another point.

The points $\alpha(x)$ and $\alpha(x+y)$ divide the knot into two open arcs
$\alpha|_{(x,x+y)}$ and $\alpha|_{(x+y,x+1)}$. If $(x,y)\in\nobreak C_{3}$ and
$r(x,y)$ crosses the second arc, then we write $(x,y)\in C_{3}^{+}$; if it
crosses the first arc, then $(x,y)\in\nobreak C_{3}^{-}$. Note that
$C_{3}^{+}\cup C_{3}^{-}=\nobreak C_{3}$.

Figure 8: Ray $r(x,y)$.

Figure 9: Colored set.

Observe that if $C_{3}^{+}$ and $C_{3}^{-}$ intersect, then the proposition
follows. In general, the set $C_{3}^{\pm}$ is not closed; denote by
$\bar{C}_{3}^{\pm}$ its closure. Suppose

$\bar{C}_{3}^{+}\cap\bar{C}_{3}^{-}=\varnothing.$

Note that in this case there is a large $n$ such that any
$\tfrac{1}{n}\times\tfrac{1}{n}$-square in $\mathbb{S}^{1}\times(0,1)$ does
not intersect both $\bar{C}_{3}^{+}$ and $\bar{C}_{3}^{-}$. Let us cut
$\mathbb{S}^{1}\times(0,1)$ into $n^{2}$ such squares; each square is a closed
subset of $\mathbb{S}^{1}\times(0,1)$. Color the union of squares that
intersect $\bar{C}_{3}^{+}$; see Figure 9. Note that every square in the
lowest row is colored and that we did not color squares in the upper row.
Further, the boundary of the colored set contains a simple curve
$t\mapsto(x(t),y(t))$ that cuts the cylinder $\mathbb{S}^{1}\times(0,1)$ into
two cylinders.

Note that $(x(t),y(t))\notin\bar{C}_{3}^{\pm}$ for any $t\in\mathbb{S}^{1}$
and the curve $t\mapsto(x(t),y(t))$ runs along coordinate lines. Consider the
one-parameter family of line segments in $r(x(t),y(t))$ that start at
$\alpha(x(t))$ and end on the surface of a large cube that contains $\alpha$
in its interior. In this way we obtain a piecewise linear annulus that
connects the curve $t\mapsto\alpha(x(t))$ to a curve on the surface of the
cube. The latter curve can be contracted by a piecewise linear disc in the
surface of the cube. It might have self-intersection, but it cannot contains
points of $\alpha$.

Observe that $t\mapsto\alpha(x(t))$ defines a degree-one map
$\mathbb{S}^{1}\to\nobreak\alpha$. Applying Lemma 5, we get the result.

It remains to show that if $\alpha=p_{1}\dots p_{n}$ is in general position,
then

$C_{3}^{+}\cap C_{3}^{-}=\varnothing\quad\text{implies
that}\quad\bar{C}_{3}^{+}\cap\bar{C}_{3}^{-}=\varnothing.$

Assume $C_{3}^{+}\cap C_{3}^{-}=\varnothing$ and
$(x,y)\in\bar{C}_{3}^{+}\cap\bar{C}_{3}^{-}$. Denote by $\ell$ the line
containing $\alpha(x)$ and $\alpha(x+y)$. Checking the following statements is
straightforward, but requires patience:

  * •

$\alpha(x)$ is a vertex, so $\alpha(x)=p_{i}$ for some $i$ and $\ell$ contains
$p_{i}$;

  * •

$\ell$ lies in the plane spanned by $p_{i-1}$, $p_{i}$, and $p_{i+1}$;

  * •

$\ell$ does not contain edge $[p_{i-1},p_{i}]$, nor $[p_{i},p_{i+1}]$;

  * •

$\ell$ has at least 3 points of intersection with $\alpha$.

Finally, if $\alpha$ is in general position, the line $\ell$ with the
described properties does not exist. ∎

##  4 Alexander–Bishop.

Here we sketch the proof given by Stephanie Alexander and Richard Bishop [3].
This proof was designed to work for more general ambient spaces. As a result,
it is more elementary.

In the proof, we construct a total-curvature-decreasing deformation of a given
knot into a doubly covered bigon. The statement follows since the latter has
total curvature $4{\cdot}\pi$.

###### Proof of the main theorem..

Let $\alpha=p_{1}\dots p_{n}$ be a nontrivial knot; that is, one cannot get a
triangle from $\alpha$ by applying a sequence of triangular isotopies defined
in the introduction.

If $n=3$ the polygonal curve $\alpha$ is a triangle. Therefore, by definition,
$\alpha$ is a trivial knot — there is nothing to show.

Consider the smallest $n$ for which the statement fails; that is, there is a
nontrivial knot $\alpha=\nobreak p_{1}\dots p_{n}$ such that

$\Phi({\alpha})<4{\cdot}\pi.$ $None$

We use the indices modulo $n$; that is, $p_{0}=p_{n}$, $p_{1}=p_{n+1}$, and so
on. Without loss of generality, we may assume that $\alpha$ is in _general
position_ ; this time it means that no four vertices of $\alpha$ lie on one
plane.

Set $\alpha_{0}=\alpha$. If the solid triangle $\text{\char
115}p_{0}p_{1}p_{2}$ intersects $\alpha_{0}$ only in the two adjacent edges,
then applying the corresponding triangular isotopy, we get a knot
$\alpha^{\prime}_{0}$ with $n-1$ edges that is inscribed in $\alpha_{0}$.
Therefore,

$\Phi({\alpha_{0}})\geqslant\Phi({\alpha_{0}^{\prime}}).$

On the other hand, by minimality of $n$,

$\Phi({\alpha_{0}^{\prime}})\geqslant 4{\cdot}\pi,$

which contradicts $({*})$.

Figure 10: Construction of $w_{1}$.

Let $w^{\prime}_{1}$ be the first point on the edge $[p_{1},p_{2}]$ such that
the line segment $[p_{0},w^{\prime}_{1}]$ intersects $\alpha_{0}$, say at
$y_{1}$.

Choose a point $w_{1}$ on $[p_{1},p_{2}]$ a bit before $w^{\prime}_{1}$.
Denote by $x_{1}$ the point on $[p_{0},w_{1}]$ that minimizes the distance to
$y_{1}$. In this way we get a closed polygonal curve $\alpha_{1}=\nobreak
w_{1}p_{2}\dots p_{n}$ with two marked points $x_{1}$ and $y_{1}$; see Figure
10. Denote by $m_{1}$ the number of edges in the arc $x_{1}w_{1}\dots y_{1}$
of $\alpha_{1}$.

Note that $\Phi({\alpha_{0}})\geqslant\Phi({\alpha_{1}})$, and $\alpha_{1}$ is
isotopic to $\alpha_{0}$; in particular, $\alpha_{1}$ is a nontrivial knot.
Moreover, the point $w_{1}$ can be chosen so that $\alpha_{1}$ is in general
position.

Now let us repeat the procedure for the adjacent edges $[w_{1},p_{2}]$ and
$[p_{2},p_{3}]$ of $\alpha_{1}$. If the solid triangle $\text{\char
115}w_{1}p_{2}p_{3}$ intersects $\alpha_{1}$ only at these two adjacent edges,
then we get a contradiction the same way as before. Otherwise, we get a new
knot $\alpha_{2}=\nobreak w_{1}w_{2}p_{3}\dots p_{n}$ with two more marked
points $x_{2}$ and $y_{2}$. Denote by $m_{2}$ the number of edges in the
polygonal curve $x_{2}w_{2}\dots y_{2}$.

Note that the points $x_{1},x_{2},y_{1},y_{2}$ cannot appear on $\alpha_{2}$
in the same cyclic order; otherwise the polygonal curve $x_{1}x_{2}y_{1}y_{2}$
can be made to be arbitrarily close to a doubly covered bigon which again
contradicts $({*})$.

Therefore, we can assume that the arc $x_{2}w_{2}\dots y_{2}$ lies inside the
arc $x_{1}w_{1}\dots y_{1}$ in $\alpha_{2}$ and therefore $m_{1}>m_{2}$.

Continuing this procedure we get a sequence of polygonal curves
$\alpha_{i}=\nobreak w_{1}\dots\nobreak w_{i}p_{i+1}\dots\nobreak p_{n}$ with
marked points $x_{i}$ and $y_{i}$ such that the number of edges $m_{i}$ from
$x_{i}$ to $y_{i}$ decreases as $i$ increases. Clearly $m_{i}>1$ for any $i$
and $m_{1}<n$. Therefore, it requires fewer than $n$ steps to arrive at a
contradiction. ∎

##  5 Ekholm–White–Wienholtz.

In this section, we discuss a solution of the problem based on the theorem of
Tobias Ekholm, Brian White, and Daniel Wienholtz [8]. This theorem was a
breakthrough in minimal surface theory at the time. Yet it was based on an
elementary idea that we are going to explain.

We start with a polygonal curve $\alpha$ with total curvature less than
$4{\cdot}\pi$; show that an area-minimizing disc spanned by $\alpha$ has no
self-intersections, and therefore $\alpha$ has to be a trivial knot. So in a
way the equation for area-minimizing surfaces solves our problem; we only need
to understand it.

The main hero in this proof is the so-called extended monotonicity theorem. We
will also apply the Douglas–Rado theorem on the existence of area-minimizing
discs and reuse the inequality between total curvature and angular length from
Fáry’s proof; see Proposition 3.

The image of a map from a domain of $\mathbb{R}^{2}$ to $\mathbb{R}^{3}$ will
be called a _surface_ ; it might have self-intersections and singularities,
but we assume it is reasonable, say locally Lipschitz [21]; so we can talk
about its area. A point on the surface might refer to a point in
$\mathbb{R}^{3}$, or to the corresponding point in the domain of parameters in
$\mathbb{R}^{2}$; it should be easy to infer from the context.

We denote by $\mathbb{D}$ the closed disc in the plane. A surface defined by a
map $f\colon\mathbb{D}\to\mathbb{R}^{3}$ will be called a _disc_. The
restriction $f|_{\partial\mathbb{D}}$ as well as its image can be referred to
as the _boundary_ of the disc.

A disc $\Sigma$ is called area-minimizing if it has the smallest area among
the discs with the given boundary. The following statement about area-
minimizing discs is easy to believe, but not easy to prove; see [20].

######  Theorem 6 (Douglas–Rado).

Given a simple closed polygonal curve $\alpha$ in $\mathbb{R}^{3}$, there is
an area-minimizing disc $\Sigma$ with boundary $\alpha$; it is a smooth
surface, possibly with self-intersections and isolated singularities.
Moreover, if $\Sigma$ has no self-intersections, then it is an embedded smooth
surface with no singularities (in this case $\alpha$ is a trivial knot).

Choose a disc $\Sigma$ in $\mathbb{R}^{3}$ with boundary $\alpha$. Given a
point $o\notin\alpha$, let us consider the _collared_ $\Sigma$ with respect to
$o$; it is a new surface that will be denoted by $\hat{\Sigma}_{o}$; it
includes $\Sigma$ and the _collar_ formed by all rays that start at points of
$\alpha$ and go in the direction opposite to $o$; see Figure 11. Note that
$\hat{\Sigma}_{o}$ admits a natural parametrization by the whole plane.

Figure 11: Surface and its collar.

######  Theorem 7 (extended monotonicity).

Let $\Sigma$ be an area-minimizing disc with boundary $\alpha$. Given a point
$o\notin\alpha$, consider the function

$W_{o}(r)=\mathop{\rm area}\nolimits(\hat{\Sigma}_{o}\cap\bar{B}_{r}(o)),$

where $\bar{B}_{r}(o)$ denotes the ball of radius $r$ centered at $o$. Then
$r\mapsto\nobreak\frac{W_{o}(r)}{r^{2}}$ is a nondecreasing function.
Moreover,

(a)
$\lim_{r\to\infty}\frac{W_{o}(r)}{r^{2}}=\tfrac{1}{2}\cdot\Psi_{o}(\alpha)$,
where $\Psi_{o}(\alpha)$ denotes the angular length of $\alpha$ with respect
to $o$; see Section 2;

(b) if $o\in\Sigma$, then $\lim_{r\to 0}\frac{W_{o}(r)}{r^{2}}\geqslant\pi$.

The classical monotonicity theorem states that the function
$r\mapsto\frac{W_{o}(r)}{r^{2}}$ is monotonic while $r$ is smaller than the
distance from $o$ to $\alpha$. The stated version is due to Brian White [19].
The same statement holds for minimal surfaces [8]; its proof requires a deeper
dive into differential geometry. At the same time, the original formulation
admits a generalization to a wider class of ambient spaces [17].

###### Proof.

Denote by $\lambda_{o}(r)$ the curve of intersection of the sphere $\partial
B_{r}(o)$ with $\hat{\Sigma}_{o}$; set $\ell(r)=\nobreak\mathop{\rm
length}\nolimits[\lambda_{o}(r)]$. Observe that

$W_{o}^{\prime}(r)\geqslant\ell(r)$

for almost all $r$. (Formally speaking, this inequality follows from the so-
called _coarea formula_.)

Set $\Delta_{r}=\hat{\Sigma}_{o}\cap\bar{B}_{r}(o)$; it is a surface bounded
by $\lambda_{o}(r)$. Let $\tilde{\Delta}_{r}$ be the cone over
$\lambda_{o}(r)$ with the center at $o$. Note that $\tilde{\Delta}_{r}$
differs from $\Delta_{r}$ only inside $\Sigma$. Since $\Sigma$ is area-
minimizing, we get that

$\mathop{\rm area}\nolimits\tilde{\Delta}_{r}\geqslant\mathop{\rm
area}\nolimits\Delta_{r}$ $None$

for any $r>0$. Observe that

$\displaystyle\mathop{\rm area}\nolimits\Delta_{r}$ $\displaystyle=W_{o}(r),$
$\displaystyle\mathop{\rm area}\nolimits\tilde{\Delta}_{r}$
$\displaystyle=\tfrac{1}{2}\cdot r\cdot\ell(r).$

Applying $({*}{*})$, we get

$r\cdot\ell(r)\geqslant 2\cdot W_{o}(r).$

Therefore,

$r\cdot W_{o}^{\prime}(r)\geqslant 2\cdot W_{o}(r)$

for almost all $r$. If $W_{o}$ is smooth, then this inequality implies the
main statement. In general, $(\frac{W_{o}(r)}{r^{2}})^{\prime}\geqslant 0$
holds almost everywhere, and this is enough to conclude the monotonicity of
$r\mapsto\nobreak\frac{W_{o}(r)}{r^{2}}$ since $W_{o}$ is nondecreasing.

(a). Observe that up to a fixed error we have that $W_{o}(r)$ is the area of
the ball of radius $r$ in the cone over $\alpha$ with the tip at $o$. It
follows that $\frac{W_{o}(r)}{r^{2}}$ approaches the area of the unit ball in
this cone as $r\to\infty$ — hence the result.

(b). The statement is evident for smooth points of $\Sigma$. Since smooth
points are dense in $\Sigma$, and $o\mapsto W_{o}(r)$ is a continuous
function, the main part of the theorem implies that $W_{o}(r)\geqslant\pi\cdot
r^{2}$ for _any_ point $o\in\Sigma$ — hence the result. ∎

###### Proof of the main theorem.

Suppose that $\Phi({\alpha})<4{\cdot}\pi$. Consider an area-minimizing surface
$\Sigma$ with the boundary $\alpha$; it exists by the Douglas–Rado theorem. If
$\Sigma$ has no self-intersections, then $\alpha$ is a trivial knot.

Suppose $\Sigma$ has a self-intersection at a point $o$. In this case, the
intersection $B_{r}(o)\cap\nobreak\Sigma$ is covered by two or more small
area-minimizing subdiscs of $\Sigma$. By Theorem 7(b), we get

$\lim_{r\to 0}\frac{W_{o}(r)}{r^{2}}\geqslant 2{\cdot}\pi.$

Applying the main statement in the monotonicity theorem, we get
$\frac{W_{o}(r)}{r^{2}}\geqslant\nobreak 2{\cdot}\pi$ for any $r>0$. By
Theorem 7(b) and Proposition 3 in Fáry’s proof, we get

$\Phi({\alpha})\geqslant\Psi_{o}(\alpha)\geqslant
2\cdot\frac{W_{o}(r)}{r^{2}}\geqslant 4{\cdot}\pi$

— a contradiction. ∎

##  6 Cantarella–Kuperberg–Kusner–Sullivan.

The following proof is due to Jason Cantarella, Greg Kuperberg, Robert Kusner,
and John Sullivan [5]; this is the only proof in our collection that uses knot
theory a bit beyond the basic definitions.

Figure 12: First and second hulls of a trefoil.

Choose a polygonal curve $\alpha=\nobreak p_{1}\dots p_{n}$. Suppose a plane
$\Pi$ is in general position; that is, it does not contain vertices of
$\alpha$. Let us denote by $\mathop{\rm cross}\nolimits_{\alpha}(\Pi)$ the
number of intersections of $\Pi$ and $\alpha$. Extend the function
$\Pi\mapsto\nobreak\mathop{\rm cross}\nolimits_{\alpha}(\Pi)$ to the minimal
upper semicontinuous function defined for all planes; in other words,
$\mathop{\rm cross}\nolimits_{\alpha}(\Pi)$ is the maximal integer $k$ such
that there is a generic plane $\Pi^{\prime}$ arbitrarily close to $\Pi$ that
intersects $\alpha$ at $k$ points. The number $\mathop{\rm
cross}\nolimits_{\alpha}(\Pi)$ will be called the _crossing number_ of $\Pi$.
Note that the crossing number is always even, and it cannot exceed $n$.

It is easy to see that the _convex hull_ $h_{1}(\alpha)$ of $\alpha$ can be
defined in the following way: $x\in h_{1}(\alpha)$ if $\mathop{\rm
cross}\nolimits_{\alpha}(\Pi)\geqslant\nobreak 2$ for any plane $\Pi$
containing $x$. This observation suggests the following definition of the
_second hull_ : $x\in h_{2}(\alpha)$ if $\mathop{\rm
cross}\nolimits_{\alpha}(\Pi)\geqslant 4$ for any plane $\Pi$ containing $x$.
See Figure 12.

######  Theorem 8.

The second hull of any nontrivial knot $\alpha$ has a nonempty interior.

Recall that _spherical polygonal curve_ is defined as a concatenation of a
finite number of great-circle arcs on the unit sphere. To show that Theorem 8
implies the main theorem, we will apply the spherical Crofton formula: for any
spherical polygonal curve $\gamma$ we have

$\mathop{\rm length}\nolimits\gamma=\pi{\cdot}\overline{n},$ $None$

where $\overline{n}$ denotes the average number of intersections of $\gamma$
with equators. To prove this formula, check it for an arc and sum it up for
all edges of $\gamma$.

###### Proof of the main theorem modulo Theorem 8.

Choose a point $o\in h_{2}(\alpha)$; we can assume that $o\notin\alpha$.
Consider the radial projection $\alpha^{*}$ of $\alpha$ to the unit sphere
centered at $o$; observe that

$\mathop{\rm length}\nolimits\alpha^{*}=\Psi_{o}(\alpha),$

where $\Psi_{o}(\alpha)$ denotes the angular length of $\alpha$ with respect
to $o$; see Section 2.

By Proposition 3, it is sufficient to show that

$\mathop{\rm length}\nolimits\alpha^{*}\geqslant 4{\cdot}\pi.$ $None$

Since $o$ is in the second hull, $\alpha^{*}$ crosses every equator in general
position at least 4 times. It follows that the average number of crossings is
at least 4. Applying
$(\smash{\raisebox{-2.58334pt}{\begin{tabular}[]{@{}cc@{}}\lx<EMAIL_ADDRESS>*&*\end{tabular}}})$, we get
$(\smash{\raisebox{-2.58334pt}{\begin{tabular}[]{<EMAIL_ADDRESS>*&*\end{tabular}}})$. ∎

Suppose that a plane $\Pi$ divides a knot $\alpha$ into two arcs, one on each
side; in particular, $\Pi$ intersects $\alpha$ at two points, say $p$ and $q$.
Then we can create two knots $\alpha_{1}$ and $\alpha_{2}$ by joining the ends
of the two arcs by the line segment $[p,q]$. In this case, we say that
$\alpha$ is a _connected sum_ of $\alpha_{1}$ and $\alpha_{2}$.

######  Claim 9.

Suppose that a knot $\alpha$ is a connected sum of knots $\alpha_{1}$ and
$\alpha_{2}$. If at least one of the knots $\alpha_{1}$ or $\alpha_{2}$ is
nontrivial, then so is $\alpha$.

This claim has an amusing proof via the so-called _infinite swindle_ [11]; see
also [15]. It also follows by additivity of knot genus [1, Section 4.3].

Suppose $\beta$ is a polygonal curve _inscribed_ in $\alpha$; that is, the
vertices of $\beta$ lie on $\alpha$ and they appear in the same cyclic order
on $\alpha$ and $\beta$. If a plane in general position intersects an edge of
$\beta$, then it intersects the corresponding arc of $\alpha$. Therefore, we
get the following.

######  Observation 10.

If a polygonal line $\beta$ is inscribed in $\alpha$, then

$h_{2}(\beta)\subset\nobreak h_{2}(\alpha).$

###### Proof of Theorem 8.

Assume the contrary; let $\alpha$ be a nontrivial polygonal knot with the
smallest number of vertices, say $n$, such that $h_{2}(\alpha)$ has an empty
interior. It is easy to see that $n\geqslant 6$; in fact, any simple space
5-gon is a trivial knot.

Suppose $\Pi$ is a plane in general position that divides $\alpha$ into two
arcs; thus it defines a decomposition of $\alpha$ into a connected sum of two
knots $\alpha_{1}$ and $\alpha_{2}$. By the observation, $h_{2}(\alpha_{1})$
and $h_{2}(\alpha_{2})$ have empty interiors. It follows that one of these
knots, say $\alpha_{1}$, is trivial; therefore, the other, respectively
$\alpha_{2}$, is isotopic to $\alpha$. Indeed, if $n_{1}$ and $n_{2}$ denote
the number of vertices in $\alpha_{1}$ and $\alpha_{2}$, then
$n_{1}+n_{2}=n+4$. If both knots are nontrivial, then $n_{1}\geqslant 6$ and
$n_{2}\geqslant 6$. Therefore, $n_{1}<n$ and $n_{2}<n$, which contradicts the
minimality of $n$.

The open half-space $H$ bounded by $\Pi$ and containing
$\alpha_{2}\setminus\Pi$ will be called _essential_. Intuitively, an essential
half-space cuts off a trivial knot of $\alpha$. (A half-space containing all
of $\alpha$ will be considered essential as well.) A rather straightforward
application of Claim 9 implies that if $H^{\prime}$ is another essential half-
space for $\alpha$, then it is also essential for $\alpha_{2}$; see Figure 13.
It follows that the intersection of all essential half-spaces, say $W$, has
nonempty interior — roughly speaking, it has to contain the region where the
knotting of $\alpha$ takes place.

Figure 13: Two essential half-spaces.

Finally observe that if $\mathop{\rm cross}\nolimits_{\alpha}(\Pi)=2$ for a
plane $\Pi$ in general position, then $\Pi$ bounds an essential half-space. It
follows that if a plane in general position intersects $W$, then it has
crossing number at least 4, so $h_{2}(\alpha)\supset W$ — hence the result. ∎

  * ACKNOWLEDGMENT.

We wish to thank anonymous referees for their thoughtful reading and
insightful suggestions. The first author was partially supported by the NSF
grant DMS-2005279, the Simons Foundation grant #584781, and Minobrnauki, grant
#075-15-2022-289. The second author was partially supported by DFG grant SPP
2026.

## References

  * 1. Adams. C. (1994). The knot book. An elementary introduction to the mathematical theory of knots. New York: W. H. Freeman and Company.
  * 2. Aleksandrov, A. D., Reshetnyak, Yu. G. (1988). Rotation of a curve in an $n$-dimensional Euclidean space. Siberian Math. J. 29(1): 1–16.
  * 3. Alexander, S., Bishop, R. (1998). The Fary–Milnor theorem in Hadamard manifolds. Proc. Amer. Math. Soc. 126(11): 3427–3436.
  * 4. Borsuk, K. (1947). Sur la courbure totale des courbes fermées. Ann. Soc. Polon. Math. 20: 251–265.
  * 5. Cantarella, J., Kuperberg, G., Kusner, R., Sullivan, J. (2003). The second hull of a knotted curve. Amer. J. Math. 125(6): 1335–1348.
  * 6. Denne, E. (2004). Alternating quadrisecants of knots. PhD dissertation. University of Illinois Urbana-Champaign, USA.
  * 7. Denne, E. (2016). Quadrisecants and essential secants of knots: with applications to the geometry of knots. arXiv: 1608.02608 [math.GT].
  * 8. Ekholm, T., White, B., Wienholtz, D. (2002). Embeddedness of minimal surfaces with total boundary curvature at most $4\pi$. Ann. of Math. (2). 155(1): 209–234.
  * 9. Fáry, I. (1949). Sur la courbure totale d’une courbe gauche faisant un nœud. Bull. Soc. Math. France. 77: 128–138.
  * 10. Fenner, S. The total curvature of a knot (long). www.ics.uci.edu/~eppstein/junkyard/knot-curvature.html.
  * 11. Mazur, B. C. (1961). On embeddings of spheres. Acta Math. 105: 1–17.
  * 12. Milnor, J. (1950). On the total curvature of knots. Ann. of Math. (2). 52: 248–257.
  * 13. Pannwitz, E. (1933). Eine elementargeometrische Eigenschaft von Verschlingungen und Knoten. Math. Ann. 108(1): 629–672.
  * 14. Petrunin, A., Zamora Barrera, S. (2021). What is differential geometry: curves and surfaces. arXiv: 2012.11814 [math.HO].
  * 15. Poénaru, V. (2007). What is . . . an infinite swindle? Notices Amer. Math. Soc. 54(5): 619–622.
  * 16. Schmitz, C. (1998). The theorem of Fáry and Milnor for Hadamard manifolds. Geom. Dedicata. 71(1): 83–90.
  * 17. Stadler, S. (2021). The structure of minimal surfaces in CAT(0) spaces. J. Eur. Math. Soc. (JEMS). 23(11): 3521–3554.
  * 18. Sullivan, J. (2008). Curves of finite total curvature. In: Discrete differential geometry. Oberwolfach Semin. Vol. 38. Basel: Birkhäuser, pp. 137–161.
  * 19. White, B. (1996). Half of Enneper’s surface minimizes area. Geometric analysis and the calculus of variations. Int. Press, Cambridge, MA, 361–367.
  * 20. White, B. (2013). Lectures on Minimal Surface Theory. arXiv: 1308.3325 [math.DG].
  * 21. Lipschitz continuity — Wikipedia, The Free Encyclopedia.