#  Time-Varying Optimization with Optimal Parametric Function

Mohsen Amidzadeh, Member, IEEE
Department of Information and Communications Enginnering, Aalto University,
Finland
<EMAIL_ADDRESS>M. Amidzadeh is with the Department of Communication
and Networking, Aalto University, Finland<EMAIL_ADDRESS>
###### Abstract

In this paper, we consider a class of nonlinear constrained optimization
problems. We formulate this problem as a time-varying optimization using
continuous-time parametric functions and derive a dynamical system for
tracking the optimal solution. We then re-parameterize the dynamical system to
express it based on a linear combination of the parametric functions. Calculus
of variations is applied to optimize the parametric functions, such that the
optimality distance of the solution is minimized. Accordingly, an iterative
dynamic algorithm is devised to find the solution with an efficient
convergence rate. We benchmark the performance of the proposed algorithm with
the prediction-correction method (PCM) from the optimality and computational
complexity point-of-views. The results show that the devised algorithm can
compete with PCM for the optimization problem of interest.

###### Index Terms:

Time-varying optimization problem, functional optimization problem,
prediction-correction method, optimality distance, dynamical system.

##  I Introduction

Time-Varying Optimization (TVO) problems represent a parametric optimization
when the objective, the constraints, or both are parameterized based on
continuously-varying functions. It is exploited to find the optimal solution
trajectory of the continuous-time optimization problems. In addition, for the
optimization problem with the optimal solution being known for one setting,
TVO can be used to extrapolate the solution into target settings.

TVO is studied in the context of parametric programming [1, 2, 3, 4, 5], where
the optimization problem is parametrized using continuous parameters. In [3],
the authors develop prediction-correction methods to solve nonlinear
constrained TVO problems. Their approach tracks a trajectory path with some
convergence guarantees. A path-following procedure has been presented in [4]
to trace a solution path of a parametric nonlinear problem. The authors
utilize quadratic programming as a tracking procedure and derive some
convergence properties for their approach. In [5], the authors leverage a
path-following method to track the solution of parametric nonlinear
constrained programs using a semi-smooth barrier function.

TVO can be also considered as an extension of time-invariant optimization
problems [6, 7, 8, 9, 10]. In [6], a discrete-time prediction-correction
approach has been proposed to minimize unconstrained time-varying functions.
They analyze the asymptotic tracking error to ensure convergence of the
solution. In [7], the authors present prediction-correction methods to track
the optimal solution trajectory, in the primal space, with a bounded
asymptotical error. Then, in [8], an interior-point method is developed for
optimization problems with time-varying cost and constraint functions. The
authors formulate a continuous-time dynamical system to track the optimal
solution with asymptotical tracking error being bounded. In [9], prediction-
correction methods have been devised, in the dual space, to track the
solutions of time-varying linearly constrained problems.

When it comes to the approach for solving TVO problems, the prediction-
correction scheme [6, 7, 11, 9, 12, 13, 14], as a promising tracking
algorithm, should be addressed. It constitutes a dynamic-tracking procedure or
predictor step to trace the solution trajectory over time, and a Newton-based
iterative method or corrector step to adjust the error of predictions.
Substantial efforts have been made to analyze the convergence of prediction-
correction approaches and ensure the boundedness of tracking error [7, 8, 11].

In this paper, we study a class of nonlinear constrained optimization problems
whose optimal solution is known for a setting, and the optimal solution is
aimed at a target one. We then exploit the notion of TVO to reformulate the
problem based on parametric programming. We then explore a set of parametric
functions such that the optimality distance is optimized. In contrast to the
works based on the prediction-correction methods, we focus on a functional
optimization problem to expedite the convergence rate. In the other words,
this paper differs from those prediction-correction approaches, in the sense
that the parametric functions are designed to minimize the optimality distance
of the solution instead of correcting the predictions.

The main contributions of this paper are listed as:

  * •

We re-express a class of nonlinear constrained optimization problems as a
time-varying optimization problem with continuous-time parametric functions.
We then use a re-parametrization trick to represent the corresponding
dynamical system based on a linear combination of the parametric functions.

  * •

We then globally optimize the parametric functions using a functional
optimization problem, and devise an iterative algorithm with the optimality
distance of the solutions being minimized. We call the devised algorithm
Optimal Parametric Time-Varying Optimization (OP-TVO).

  * •

We compare OP-TVO with a prediction-correction method from the optimality and
computational complexity perspectives.

Notations: In this paper, we use lower-case $a$ for scalars, bold-face lower-
case a for vectors and bold-face uppercase A for matrices. Further,
$\textbf{A}^{\top}$ is the transpose of A, $\|\textbf{a}\|$ is the euclidean
norm of a, $\boldsymbol{\nabla}_{\textbf{a}}g(\cdot)$ and
$\boldsymbol{\nabla}^{2}_{\textbf{a}}g(\cdot)$ are the gradient vector and
Hessian matrix of multivariate function $g(\textbf{a})$ with respect to
(w.r.t.) vector a, respectively. We show the components of a $n$-dimensional
column vector $\boldsymbol{a}$ using the notation
$\boldsymbol{a}=[a_{1},\ldots,a_{n}]^{\top}$. Further, $\\{a_{n}\\}_{1}^{N}$
collects the components of vector $\boldsymbol{a}$ from $n=1$ to $n=N$. We use
I, 1 and 0 to denote the identity matrix, all-ones and all-zeros vectors,
respectively. We use $\dot{\boldsymbol{a}}(\theta)$ to represent the
derivative of $\boldsymbol{a}(\theta)$ w.r.t. $\theta$.

##  II Problem Statement

This paper considers a class of nonlinear constrained optimization problems.
The problem includes an objective function
$f(\cdot):\mathbb{R}^{N}\rightarrow\mathbb{R}$, vector-valued constraint
functions
$\boldsymbol{h}_{m}(\cdot)=[h_{m,1},\ldots,h_{m,N}]^{\top}(\cdot):\mathbb{R}^{N}\rightarrow\mathbb{R}^{N}$
and the optimization variables $\boldsymbol{x}_{m}\in\mathbb{R}^{N}$ for
$m\in\\{1,\ldots,M\\}$. As such, the problem under study is:

$\displaystyle P_{0}:\qquad$
$\displaystyle\min_{\\{\boldsymbol{x}_{m}\\}_{1}^{M}}~{}\sum_{m=1}^{M}a_{m}f(\boldsymbol{x_{m}})$
$\displaystyle~{}~{}~{}s.t.\quad\sum_{m=1}^{M}\boldsymbol{h}_{m}(\boldsymbol{x}_{m})=\boldsymbol{u},$
(1)

where $\boldsymbol{u}\in\mathbb{R}^{N}$. We assume that the optimal solution
of Problem $P_{0}$ is known for the given non-zero parameters $a_{m}=p_{0,m}$
with $m\in\\{1,\ldots,M\\}$. However, the optimal solution is unknown and
desired for the target parameters $a_{m}=p_{\tau,m}$.

Note that this type of optimization problem arises, e.g., in distributed
optimizations as well as in multi-agent systems with cost functions
controlling agent-specific variables $\boldsymbol{x}_{m}$.

The aim is thus to express $P_{0}$ based on a TVO problem with parametric
functions, and devise a path-following method with convergence rate being
optimized. To optimize it, we follow a functional optimization to design the
parametric functions. As such, we parameterize $\\{a_{m}\\}_{1}^{M}$ with the
parametric functions $\\{b_{m}(\theta)\\}_{1}^{M}$ and parameter
$\theta\in\mathbb{R}^{+}\cup\\{0\\}$, so that

$\displaystyle\\!\\!\lim_{\theta\rightarrow
0}b_{m}(\theta)=p_{0,m},\qquad\lim_{\theta\rightarrow\tau}b_{m}(\theta)=p_{e,m},$
(2)

for $m\in\\{1,\ldots,M\\}$. Note that such parametric function as presented in
(2) is not unique. We then consider the following TVO problem

$\displaystyle P_{1}(\theta):\qquad\boldsymbol{x}^{*}(\theta)=\>$
$\displaystyle\underset{\\{\boldsymbol{x}_{m}(\theta)\\}_{1}^{M}}{\mathrm{argmin}}~{}\sum_{m=1}^{M}b_{m}(\theta)f\big{(}\boldsymbol{x_{m}}(\theta)\big{)}$
$\displaystyle~{}~{}~{}s.t.\quad\sum_{m=1}^{M}\boldsymbol{h}_{m}\big{(}\boldsymbol{x}_{m}(\theta)\big{)}=\boldsymbol{u},$
(3)

where
$\boldsymbol{x}(\theta)=[\boldsymbol{x}_{1}^{\top},\ldots,\boldsymbol{x}_{M}^{\top}]^{\top}(\theta)$.
As declared, we assume that the solution of $P_{1}(\theta)$ for $\theta=0$ is
given, and the solution at target $\theta=\tau>0$ is aimed.

A naive approach to find the solution of $P_{1}(\theta)$ is to use a Newton-
based iterative algorithm. However, this approach suffers from the low
convergence rate and its solution optimality depends on a step-length
parameter.

Instead, we develop a time-varying approach to exploit the information of
optimal solution of $P_{1}(0)$. We thus formulate a continuous-time dynamical
system

$\displaystyle\dot{\boldsymbol{x}}_{m}(\theta)=\boldsymbol{\phi}_{m}\big{(}\boldsymbol{x}(\theta),\theta\big{)}\\!:~{}\mathbb{R}^{\rm
NM}\times\mathbb{R}^{+}\cup\\{0\\}\to\mathbb{R}^{N},$ (4)

with optimal trajectory solution denoted by $\boldsymbol{x}^{*}(\cdot)$. We
then devise an iterative approach to predict $\boldsymbol{x}^{*}(\cdot)$ by
$\boldsymbol{x}(\cdot)$ so that the optimality distance
$\|\boldsymbol{x}(\theta)-\boldsymbol{x}^{*}(\theta)\|$ is minimized for
$\theta\to\tau$. Note that (4) shows a set of ODEs which should be solved with
initial condition $\boldsymbol{x}(0)$ to give the target point
$\boldsymbol{x}(\tau)$. As such, we intend to jointly solve TVO
$P_{1}(\theta)$ and design $\\{b_{m}(\theta)\\}_{1}^{M}$ such that the
optimality distance is optimized.

Let the following assumptions hold for TVO $P_{1}(\theta)$.

Assumption 1: The objective function $f(\cdot)$ and constraints
$\boldsymbol{h}_{m}(\cdot)$ are twice continuously differentiable with respect
to (w.r.t.) $\boldsymbol{x}_{m}$.

Assumption 2: The matrices $\\{\boldsymbol{\rm Jh}_{m}\\}_{1}^{M}$ are
invertible for $\theta\in[0,\tau]$, where $\boldsymbol{\rm
Jh}_{m}\in\mathbb{R}^{N\times N}$ is the transpose of Jacobian matrix of
$\boldsymbol{h}_{m}(\cdot)$ w.r.t. $\boldsymbol{x}_{m}(\theta)$.

##  III  ODEs associated with TVO $P_{1}(\theta$)

For the dynamical system (4), we have:

######  Proposition 1.

The solution of Karush–Kuhn–Tucker conditions of problem $P_{1}(\theta)$ for
$\theta\in[0,\tau]$ can be found by the dynamical system (4) with:

$\displaystyle\boldsymbol{\phi}_{m}\big{(}\boldsymbol{x}(\theta),\theta\big{)}=$
$\displaystyle~{}-\Big{(}b_{m}(\theta)\nabla_{m}^{2}f+\sum_{n=1}^{N}\lambda_{n}\nabla^{2}_{m}h_{m,n}\Big{)}^{-1}\boldsymbol{\rm
Jh}_{m}\Big{(}\boldsymbol{\dot{\lambda}}-\frac{\dot{b}_{m}(\theta)}{b_{m}(\theta)}\boldsymbol{\lambda}\Big{)},$
(5)

where

$\displaystyle\boldsymbol{\lambda}=-b_{m}(\theta)\boldsymbol{\rm
Jh}_{m}^{-1}\nabla_{m}f,~{}~{}~{}~{}~{}{\rm for}~{}~{}m\in\\{1,\ldots,M\\},$
(6)

and $\boldsymbol{\dot{\lambda}}$ is obtained using

$\displaystyle\sum_{m=1}^{M}\boldsymbol{\rm
Jh}_{m}^{\top}\>\dot{\boldsymbol{x}}_{m}(\theta)=\boldsymbol{0}.$ (7)

###### Proof.

Please refer to the Appendix. ∎

According to (1), the dynamical system
$\\{\boldsymbol{\phi}_{m}(\cdot,\cdot)\\}_{1}^{M}$ has been formulated based
on a nonlinear combination of two parametric functions, ${b}_{m}(\theta)$ and
$\dot{b}_{m}(\theta)$. In the sequel, we use a decomposition trick to express
the dynamical system as a linear combination of one parametric function.

###  III-A Reparameterizing based on a Decomposition

We introduce the parametric functions

$\displaystyle c_{m}(\theta):=\dfrac{\dot{b}_{m}(\theta)}{b_{m}(\theta)}\qquad
m\in\\{1,\ldots,M\\},$ (8)

which should satisfy
$\int_{0}^{\tau}c_{m}(\theta)d\theta=\log\Big{(}\dfrac{p_{e,m}}{p_{0,m}}\Big{)}:=\psi_{m}$
based on (2). We then have:

######  Theorem 1.

The dynamical system (1) can be re-parameterized based on the following linear
combination of $\\{c_{m}(\theta)\\}_{1}^{M}$:

$\displaystyle\dot{\boldsymbol{x}}(\theta)=\boldsymbol{\phi}\big{(}\boldsymbol{x}(\theta),\theta\big{)}=\boldsymbol{\Gamma}(\theta)\>\boldsymbol{c}(\theta),$
(9)

where
$\boldsymbol{\phi}(\cdot,\cdot)=[\boldsymbol{\phi}_{1}^{\top},\ldots,\boldsymbol{\phi}_{M}^{\top}]^{\top}(\cdot,\cdot)$,

$\displaystyle\boldsymbol{\Gamma}(\theta)$
$\displaystyle=\begin{pmatrix}\boldsymbol{\gamma}_{11}&\ldots&\boldsymbol{\gamma}_{1M}\\\
\vdots&\vdots&\vdots\\\
\boldsymbol{\gamma}_{N1}&\ldots&\boldsymbol{\gamma}_{NM}\end{pmatrix}~{}\in~{}\mathbb{R}^{\rm
NM\times M},$ $\displaystyle\boldsymbol{\gamma}_{nm}$
$\displaystyle=-G_{n}^{-1}\bigg{(}\Big{(}\sum_{k=1}^{M}D_{k}\Big{)}^{-1}D_{m}-\delta_{nm}\boldsymbol{I}\bigg{)}\boldsymbol{1},$
$\displaystyle G_{n}$ $\displaystyle={\rm
diag}(\boldsymbol{v})^{-1}\boldsymbol{\rm
Jh}_{n}^{-1}\>\bigg{(}\nabla_{n}^{2}f+\sum_{j=1}^{N}\nabla_{n}^{2}h_{n,j}\bigg{)},$
$\displaystyle D_{m}$ $\displaystyle=\boldsymbol{\rm
Jh}_{m}^{\top}\>G_{m}^{-1},$

for $n\in\\{1,\ldots,N\\}$ and $m\in\\{1,\ldots,M\\}$ with

$\displaystyle\boldsymbol{v}=-\boldsymbol{\rm Jh}_{m}^{-1}\>\nabla_{m}f.$ (10)

###### Proof.

We introduce $N$-by-$N$ matrices $\\{G_{m}\\}_{1}^{M}$ and exploit the
following decomposition:

$\displaystyle
b_{m}(\theta)\nabla_{m}^{2}f+\sum_{n=1}^{N}\lambda_{n}\nabla^{2}_{m}h_{m,n}=\boldsymbol{\rm
Jh}_{m}\>{\rm diag}(\boldsymbol{\lambda})G_{m}.$ (11)

Then, we get:

$\displaystyle G_{m}={\rm diag}(\boldsymbol{v})^{-1}\boldsymbol{\rm
Jh}_{m}^{-1}\>\Big{(}\nabla_{m}^{2}f+\sum_{n=1}^{N}v_{n}\nabla_{m}^{2}h_{m,n}\Big{)},$
(12)

for which we used $\boldsymbol{\lambda}=b_{m}(\theta)\boldsymbol{v}$ based on
(6) and (10). Equation (12) shows that $G_{m}$ is notably independent of
parametric function $b_{n}(\theta)$. Now, by plugging (11) into (1), we
obtain:

$\displaystyle\dot{\boldsymbol{x}}_{n}(\theta)=-G_{n}^{-1}{\rm
diag}(\boldsymbol{\lambda})^{-1}\big{(}\dot{\boldsymbol{\lambda}}-c_{n}(\theta)\boldsymbol{\lambda}\big{)},$

and according to (7), we get:

$\displaystyle\boldsymbol{\dot{\lambda}}=\boldsymbol{\lambda}\>\Big{(}\sum_{k=1}^{M}D_{k}\Big{)}^{-1}\sum_{m=1}^{M}D_{m}c_{m}(\theta)\>\boldsymbol{1},$

which together reads:

$\displaystyle\dot{\boldsymbol{x}}_{n}(\theta)=-G_{n}^{-1}\bigg{(}\Big{(}\sum_{k=1}^{M}D_{k}\Big{)}^{-1}\sum_{m=1}^{M}D_{m}c_{m}(\theta)-c_{n}(\theta)\boldsymbol{I}\bigg{)}\boldsymbol{1}.$

Based on the definition of $\boldsymbol{\gamma}_{nm}$, we thus obtain:

$\displaystyle\dot{\boldsymbol{x}}_{n}(\theta)$
$\displaystyle=\sum_{m=1}^{M}\boldsymbol{\gamma}_{nm}c_{m}(\theta),~{}~{}~{}n\in\\{1,\ldots,N\\},$

which proves the statement. ∎

Note that the dynamical system (9) depends only on $\boldsymbol{c}(\cdot)$ and
not on $\boldsymbol{b}(\cdot)$. Further, considering that
$\boldsymbol{\Gamma}(\cdot)$ does not depend on $\boldsymbol{c}(\cdot)$, a
linear parametric expression w.r.t. $\boldsymbol{c}(\cdot)$ has been obtained
for the dynamical system. It enables us to design $\boldsymbol{c}(\cdot)$ such
that the optimality distance is optimized. Having $\boldsymbol{c}(\cdot)$
being designed, we then get:
$b_{m}(\theta)=p_{0,m}\exp\big{(}\int_{0}^{\theta}c_{m}(\xi)d\xi\big{)}$ based
on (2) and (8).

##  IV Optimality Distance

Equation (9) shows a set of ODEs that is intricate to precisely solve due to
highly non-linearity w.r.t. $\theta$. However, one approach is to use the
Euler method [15] to approximate $\boldsymbol{x}(\cdot)$ by
$\hat{\boldsymbol{x}}(\cdot)$ based on a sequential manner:

$\displaystyle\\!\\!\\!\\!\hat{\boldsymbol{x}}(\theta)=\hat{\boldsymbol{x}}(\theta-\Delta\theta)+\Delta\theta\>\hat{\dot{\boldsymbol{x}}}(\theta-\Delta\theta),\qquad\theta\in(0,\tau],$
(13)

where $\Delta\theta$ is the incremental step and
$\hat{\dot{\boldsymbol{x}}}(\theta)=\boldsymbol{\phi}\big{(}\hat{\boldsymbol{x}}(\theta),\theta\big{)}$.
For this method, the optimality distance $O_{d}$ is upper-bounded by:

$\displaystyle\\!\\!\\!O_{d}=\|\hat{\boldsymbol{x}}(\tau)-\boldsymbol{x}(\tau)\|\leq\frac{\Delta\theta^{2}}{2}\sum_{j=1}^{L}\|\ddot{\boldsymbol{x}}(\tau-j\Delta\theta)\|+\mathcal{O}(L\Delta\theta^{3}),$

where $\tau=L\Delta\theta$. This shows that optimality distance is limited by
order of $\Delta\theta^{2}$. However, based on (13) another upper-bound can be
found as follows:

$\displaystyle
O_{d}=\left\|\int_{0}^{\tau}\big{(}\dot{\boldsymbol{x}}(\theta)-\hat{\boldsymbol{m}}\big{)}d\theta\right\|\leq\int_{0}^{\tau}\|\dot{\boldsymbol{x}}(\theta)-\hat{\boldsymbol{m}}\|d\theta,$
(14)

where

$\hat{\boldsymbol{m}}=\frac{1}{L}\sum_{j=1}^{L}\hat{\dot{\boldsymbol{x}}}(\tau-j\Delta\theta).$

By minimizing the upper-bound presented in (14), we can minimize the
optimality distance.

##  V Optimality Distance Minimization

We consider the following functional optimization problem (FOP) to jointly
design the parametric functions $\boldsymbol{c}(\cdot)$ and find the optimum
solution $\boldsymbol{x}(\cdot)$:

$\displaystyle
J_{1}:\qquad\min_{\boldsymbol{x}(\cdot),\boldsymbol{c}(\cdot)}~{}$
$\displaystyle\int_{0}^{\tau}\|\dot{\boldsymbol{x}}(\theta)-\hat{\boldsymbol{m}}\|^{2}d\theta$
$\displaystyle s.t.~{}~{}~{}$
$\displaystyle\dot{\boldsymbol{x}}(\theta)=\boldsymbol{\Gamma}(\theta)\>\boldsymbol{c}(\theta),$
$\displaystyle s.t.~{}~{}~{}$
$\displaystyle\int_{0}^{\tau}\boldsymbol{c}(\theta)d\theta=\boldsymbol{\psi}.$
(15)

By solving FOP $J_{1}$, we can achieve the optimal solution
$\boldsymbol{x}(\theta)$ which minimizes the optimality distance $O_{d}$,
based on (14). To solve (V), we constitute the Hamiltonian $\mathcal{H}$ as:

$\mathcal{H}=\|\dot{\boldsymbol{x}}(\theta)-\hat{\boldsymbol{m}}\|^{2}+\boldsymbol{w}(\theta)^{\top}\big{(}\dot{\boldsymbol{x}}(\theta)-\boldsymbol{\Gamma}(\theta)\>\boldsymbol{c}(\theta)\big{)}+\boldsymbol{\lambda}^{\top}\Big{(}\boldsymbol{c}(\theta)-\frac{1}{\tau}\boldsymbol{\psi}\Big{)},$

where $\boldsymbol{w}(\theta)$ is the co-state variables and
$\boldsymbol{\lambda}$ is the Lagrange multiplier. Using calculus of
variations, the functional solution of (V) is obtained by:

$\displaystyle\begin{cases}\nabla_{\boldsymbol{c}(\theta)}\mathcal{H}=2\boldsymbol{\Gamma}(\theta)^{\top}\Big{(}\boldsymbol{\Gamma}(\theta)\boldsymbol{c}(\theta)-\hat{\boldsymbol{m}}-\frac{1}{2}\boldsymbol{w}(\theta)\Big{)}+\boldsymbol{\lambda}=0\vspace{6pt},\\\
\nabla_{\boldsymbol{x}(\theta)}\mathcal{H}-\frac{d}{d\theta}\nabla_{\dot{\boldsymbol{x}}(\theta)}\mathcal{H}\\\
\qquad~{}\quad=\boldsymbol{w}(\theta)^{\top}~{}\nabla_{\boldsymbol{x}(\theta)}\boldsymbol{\Gamma}(\theta)~{}\boldsymbol{c}(\theta)+2\ddot{\boldsymbol{x}}(\theta)+\dot{\boldsymbol{w}}(\theta)=0,\vspace{6pt}\\\
\dot{\boldsymbol{x}}(\theta)-\boldsymbol{\Gamma}(\theta)\>\boldsymbol{c}(\theta)=0,\qquad\quad\int_{0}^{\tau}\boldsymbol{c}(\theta)d\theta-\boldsymbol{\psi}=0.\end{cases}$
(16)

The conditions (16) are intricate to solve. Further, an estimation of
$\boldsymbol{\hat{m}}$ is needed in advance. This motivates us to devise an
iterative algorithm to find the solution of $J_{1}$.

In this regard, we perform an iterative algorithm as follows: In the
beginning, we initialize $\boldsymbol{c}(\cdot)$ such that
$\int_{0}^{\tau}\boldsymbol{c}(\theta)d\theta=\boldsymbol{\psi}$. Then, we
repeatedly follow two consecutive steps till the algorithm converges. These
are the Prediction and Parametral-tuning steps. In the prediction step of this
iterative approach, we sequentially solve (13) using (9), and based on
recently updated $\boldsymbol{c}(\cdot)$ in order to predict
$\boldsymbol{x}(\theta)$ for $\theta\in(0,\tau]$. In the parametral-tuning
step, we minimize the functional objective
$\int_{0}^{\tau}\|\dot{\boldsymbol{x}}(\theta)-\hat{\boldsymbol{m}}\|^{2}d\theta$
w.r.t. $\boldsymbol{c}(\cdot)$ with $\hat{\boldsymbol{m}}$ being obtained
based on the solution of prediction step. As declared, we execute these two
steps till the convergence. We call this algorithm Optimal Parametric Time-
Varying Optimization (OP-TVO).

More specifically, we consider the following FOP, in the second step of OP-
TVO, to optimize the parametric functions $\boldsymbol{c}(\cdot)$:

$\displaystyle\\!J_{2}:\quad\min_{\boldsymbol{c}(\cdot)}~{}$
$\displaystyle\int_{0}^{\tau}\Big{\|}\boldsymbol{\Gamma}(\theta)\>\boldsymbol{c}(\theta)-\hat{\boldsymbol{m}}\Big{\|}^{2}d\theta+\mu\int_{0}^{\tau}\boldsymbol{c}(\theta)^{\top}\boldsymbol{c}(\theta)d\theta$
$\displaystyle s.t.~{}~{}$
$\displaystyle\int_{0}^{\tau}\boldsymbol{c}(\theta)d\theta=\boldsymbol{\psi}~{},$
(17)

where the term
$\int_{0}^{\tau}\boldsymbol{c}(\theta)^{\top}\boldsymbol{c}(\theta)d\theta$ is
additional added to regulate the smoothness of $\boldsymbol{c}(\theta)$ w.r.t.
$\theta$, and $0<\mu\ll 1$ is the regulation coefficient.

######  Proposition 2.

The globally optimal solution of $J_{2}$ is obtained by:

$\displaystyle\boldsymbol{c}(\theta)=\boldsymbol{\Pi}^{-1}(\theta)\left(\boldsymbol{\Gamma}(\theta)^{\top}\hat{\boldsymbol{m}}-\boldsymbol{\lambda}\right),$
(18)

where

$\displaystyle\boldsymbol{\Pi}(\theta)=\boldsymbol{\Gamma}(\theta)^{\top}\boldsymbol{\Gamma}(\theta)+\mu\boldsymbol{I},$
$\displaystyle\boldsymbol{\lambda}=\left(\int_{0}^{\tau}\boldsymbol{\Pi}^{-1}(\theta)d\theta\right)^{-1}\left(\int_{0}^{\tau}\boldsymbol{\Pi}^{-1}(\theta)\boldsymbol{\Gamma}(\theta)^{\top}d\theta\>\hat{\boldsymbol{m}}-\boldsymbol{\psi}\right).$

###### Proof.

Considering that the dynamical system (9) has been expressed based on a linear
combination of parametric functions $\boldsymbol{c}(\cdot)$, $J_{2}$ is a
convex FOP. This implies that the globally optimal solution of $J_{2}$ can be
found by applying the Euler-Lagrange equation on $J_{2}$ [16]. We thus get:

$\displaystyle\begin{cases}\boldsymbol{\Gamma}(\theta)^{\top}(\boldsymbol{\Gamma}(\theta)\>\boldsymbol{c}(\theta)-\hat{\boldsymbol{m}})+\mu\boldsymbol{c}(\theta)+\boldsymbol{\lambda}&=0,\vspace{4
pt}{}\\\
\int_{0}^{\tau}\boldsymbol{c}(\theta)d\theta-\boldsymbol{\psi}&=0~{}.\end{cases}$
(19)

By solving (19), the statement follows. ∎

Input: Optimal solution $\boldsymbol{x}(0)$.

Outputs: Optimal solution $\boldsymbol{x}(\tau)$ and parametric functions
$\boldsymbol{c}(\cdot)$.

Initialization:

Initialize $\boldsymbol{c}(\cdot)$ so that
$\int_{0}^{\tau}\boldsymbol{c}(\theta)d\theta=\boldsymbol{\psi}$.

Set $\rm flag=1$ and $\rm iter=0$.

while  _$\rm flag$_ do

iter = iter+1.

Prediction step:

Predict $\boldsymbol{x}(\theta)$ for $\theta\in(0,\tau]$ using (13) and (9)
and based on updated $\boldsymbol{c}(\cdot)$.

Parametral-tuning step:

Update $\boldsymbol{c}(\cdot)$ using (18) and based on predicted
$\boldsymbol{x}(\theta)$ with $\theta\in(0,\tau]$.

if  _Convergence_ then

$\rm flag=0$.

end if

end while

Algorithm 1 Optimal Parametric Time-Varying Optimization (OP-TVO)

Algorithm 1 shows the pseudo-code of OP-TVO. For each iteration (${\rm
iter}$), the prediction and parametral-tuning steps are performed to jointly
predict the optimal solution $\boldsymbol{x}^{*}(\tau)$ and design the
parametric functions $\boldsymbol{c}(\cdot)$. We also need a metric for the
convergence to stop the algorithm. For this, we track the value of
$\hat{O}_{d}:=$
${\sum}_{j=1}^{L}\Big{\|}\boldsymbol{\phi}\Big{(}\hat{\boldsymbol{x}}(\tau-j\Delta\theta),\tau-j\Delta\theta\Big{)}-\hat{\boldsymbol{m}}\Big{\|}^{2}$
as an estimation of the optimality distance. We thus consider that the
algorithm has converged if the value of $\hat{O}_{d}$ lies below a threshold
$O_{\rm th}$.

##  VI Numerical Results and Discussion

To evaluate the devised algorithm OP-TVO, we compare it with a Prediction-
Correction Method (PCM) [6], as well as with a Benchmark solution being
obtained with an extremely small incremental step $\Delta\theta=10^{-6}$,
regardless of its computational complexity. Note that, we consider this
Benchmark as the optimal solution, by which we can compute the optimality
distance $O_{d}$. These algorithms have been performed using Matlab R2022a on
a $8\times 1.70$ GHz Intel Core i5-10310U Processor, equipped with 16 GB of
memory and 12 Mbytes of data cache.

We then consider the constrained optimization problem $E_{1}$ [17, 18], and
change the constraints to add non-linearity to the problem.

$\displaystyle E_{1}:\qquad$
$\displaystyle\min_{\\{\boldsymbol{x}_{m}\\}_{1}^{M}}~{}~{}\sum_{m=1}^{M}a_{m}\operatorname{erfc}\left(\gamma_{0}\dfrac{x_{m,1}}{\sqrt{2^{\frac{0.1}{x_{m,2}}}-1}}\right)$
$\displaystyle~{}~{}s.t.~{}~{}~{}\sum_{m=1}^{M}\log(1+x_{m,1})=L,$
$\displaystyle~{}~{}s.t.~{}~{}~{}\sum_{m=1}^{M}x_{m,2}^{2}=1,$

where the optimization variables are
$\boldsymbol{x}_{m}=[x_{m,1},x_{m,2}]^{\top}$ for $m\in\\{1,\ldots,M\\}$,
$M=100$, $a_{m}=m^{-\tau}/\sum_{m=1}^{M}m^{-\tau}$, $\tau=3$ and
$\gamma_{0}=40$. For $E_{1}$, it can be verified that the optimal solution
when $a_{m}=\frac{1}{M}$ is obtained as:

$x_{m,1}=\exp(L/M-1),~{}~{}x_{m,2}=\sqrt{1/M},\quad m\in\\{1,\ldots,M\\}.$

Therefore, we constitute a TVO problem exactly as $E_{1}$ but with parametric
functions $\\{b_{m}(\theta)\\}_{1}^{M}$ replacing $\\{a_{m}\\}_{1}^{M}$ such
that:

$b_{m}(0)=\frac{1}{M},\quad b_{m}(\tau)=a_{m},\quad m\in\\{1,\ldots,M\\}.$

We further use the re-parametrizing functions $\boldsymbol{c}(\cdot)$ with
$c_{m}(\theta):=\dfrac{\dot{b}_{m}(\theta)}{b_{m}(\theta)}$. We then apply
Algorithm 1 with hyper-parameters $\mu=10^{-7}$, $O_{\rm th}=10^{-5}$ and
$\Delta\theta=10^{-2}$ to find the optimal solution.

Figures 1 and 2 illustrate the trajectory solutions
$\\{\boldsymbol{x}_{m}(\theta)\\}_{1}^{M}$, being obtained by Algorithm 1, as
a function of $\theta$ for different iterations. For the first iteration, the
trajectory solutions portray a highly nonlinear behavior. However, as the
number of iteration increases, this non-linearity reduces. When the algorithm
converges (3rd iteration), the linear curvature of the trajectory solutions
indicates that a precise solution with minimal optimality distance has been
obtained.

Figure 1: Trajectory Solutions for $x_{m,1}$ with $m\in\\{1,8,15\\}$.  Figure
2: Trajectory Solutions for $x_{m,2}$ with $m\in\\{20,30,100\\}$.

We also apply a PCM on Problem $E_{1}$ to obtain the solution. To have a fair
comparison, we adjust the hyper-parameter $\Delta\theta$ for PCM such that the
corresponding optimal value is almost equal to the Algorithm 1. As such, we
need to decrease it by $1\times 10^{-4}$.

TABLE I: Performance Result of Algorithm OP-TVO and PCM. Approach |  | Optimal Value
---
| Elapsed Time [s]
---
| $O_{d}$
---
| $\hat{O}_{d}$
---
${\tt Benchmark}$ | $5.6089\times 10^{-7}$ | 2066 | 0.0 | N/A
PCM | $5.6086\times 10^{-7}$ | 271 | 0.00135 | N/A
${\tt\mbox{OP-TVO},}$ iter=1 | $3.2443\times 10^{-5}$ | 3 | 0.8291 | N/A
iter=2 | $5.6088\times 10^{-7}$ | 52 | 5.132$\times 10^{-4}$ | 0.228
iter=3 | $5.6088\times 10^{-7}$ | 105 | 5.130$\times 10^{-4}$ | 2.68$\times 10^{-6}$
iter=4 | $5.6088\times 10^{-7}$ | 160 | 5.130$\times 10^{-4}$ | 2.14$\times 10^{-6}$

Table I compares the performance results of PCM, Benchmark and OP-TVO. The
second column shows the optimal values that these approaches achieve, the
third column indicates the elapsed time, in seconds, that lasts for them to be
performed, and the fourth and fifth columns show the optimality distance
$O_{d}$ and its estimation $\hat{O}_{d}$, respectively.

According to the values of $\hat{O}_{d}$, OP-TVO converges after three
iterations. It can be seen that OP-TVO with ${\rm iter}=3$ outperforms PCM
from the computational complexity perspective as it converges within 105
seconds while PCM converges after 271 seconds. Furthermore, the optimality
distance $O_{d}$ of OP-TVO with ${\rm iter}=3$ is superior to the optimality
distance of PCM. It implies that OP-TVO gives a more accurate solution than
PCM. These results depict that OP-TVO can find the optimal solution with lower
computational complexity and better performance precision.

##  VII Conclusion

In this paper, we reformulated a class of nonlinear constrained optimization
problems based on a time-varying optimization with some parametric functions.
We then leveraged a re-parametrization trick to find a dynamical system being
linearly expressed with respect to the parametric functions. To minimize the
optimality distance of the solution, being traced by a dynamical system, we
utilized a functional minimization problem. As such, an iterative algorithm
was devised to find the solution trajectory with optimal optimality distance.
Based on the results, the proposed algorithm outperforms the prediction-
correction method from the optimality distance and convergence rate
perspectives.

## References

  * [1] J. Guddat, F. G. Vazquez, and H. T. Jongen, _Parametric Optimization: Singularities, Pathfollowing and Jumps_. Chichester, U.K.: Wiley, 1990.
  * [2] Q. T. Dinh, C. Savorgnan, and M. Diehl, “Adjoint-based predictor-corrector sequential convex programming for parametric nonlinear optimization,” _SIAM J. Optim._ , vol. 22, no. 4, p. 1258–1284, 2012.
  * [3] V. Kungurtsev and M. Diehl, “Sequential quadratic programming methods for parametric nonlinear optimization,” _Computational Optimization and Applications,_ , vol. 59, no. 3, pp. 475–509, Feb. 2014.
  * [4] V. Kungurtsev and J. Jäschke, “A predictor-corrector path-following algorithm for dual-degenerate parametric optimization problems,” _SIAM J. Optim._ , vol. 27, no. 1, p. 538–564, 2017.
  * [5] D. Liao-McPherson, M. M. Nicotra, and I. V. Kolmanovsky, “A semismooth predictor corrector method for real-time constrained parametric optimization with applications in model predictive control,” in _2018 IEEE Conference on Decision and Control (CDC)_ , 2018, pp. 3600–3607.
  * [6] S. Andrea, M. Aryan, K. Alec, L. Geert, and A. Ribeiro, “A class of prediction-correction methods for time-varying convex optimization,” _IEEE Transactions on Signal Processing_ , vol. 64, no. 17, pp. 4576–4591, 2016.
  * [7] A. Simonetto and E. Dall’Anese, “Prediction-correction algorithms for time-varying constrained optimization,” _IEEE Transactions on Signal Processing_ , vol. 65, no. 20, pp. 5481–5494, 2017.
  * [8] M. Fazlyab, S. Paternain, V. M. Preciado, and A. Ribeiro, “Prediction-correction interior-point method for time-varying convex optimization,” _IEEE Transactions on Automatic Control_ , vol. 63, no. 7, pp. 1973–1986, 2018.
  * [9] A. Simonetto, “Dual prediction–correction methods for linearly constrained time-varying convex programs,” _IEEE Transactions on Automatic Control_ , vol. 64, no. 8, pp. 3355–3361, 2019.
  * [10] A. Simonetto, E. Dall’Anese, S. Paternain, G. Leus, and G. B. Giannakis, “Time-varying convex optimization: Time-structured algorithms and applications,” _Proceedings of the IEEE_ , vol. 108, no. 11, pp. 2032–2048, 2020.
  * [11] D. Guo, X. Lin, Z. Su, S. Sun, and Z. Huang, “Design and analysis of two discrete-time ZD algorithms for time-varying nonlinear minimization,” _Numer. Algorithms_ , vol. 77, no. 1, p. 23–36, 2018.
  * [12] S. Paternain, M. Morari, and A. Ribeiro, “Real-time model predictive control based on prediction-correction algorithms,” in _2019 IEEE 58th Conference on Decision and Control (CDC)_ , 2019, pp. 5285–5291.
  * [13] N. Bastianello, A. Simonetto, and R. Carli, “Prediction-correction splittings for nonsmooth time-varying optimization,” in _2019 18th European Control Conference (ECC)_ , 2019, pp. 1963–1968.
  * [14] A. Bernstein, E. Dall’Anese, and A. Simonetto, “Online primal-dual methods with measurement feedback for time-varying convex optimization,” _IEEE Transactions on Signal Processing_ , vol. 67, no. 8, pp. 1978–1991, 2019.
  * [15] A. Iserles, _A First Course in the Numerical Analysis of Differential Equations_ , 2nd ed., ser. Cambridge Texts in Applied Mathematics. Cambridge University Press, 2008.
  * [16] A. Seierstad and K. Sydsaeter, “Sufficient conditions in optimal control theory,” _International Economic Review_ , vol. 18, no. 2, pp. 367–391, 1977\.
  * [17] M. Amidzade, H. Al-Tous, O. Tirkkonen, and G. Caire, “Cellular network caching based on multipoint multicast transmissions,” in _Proc. IEEE Glob. Commun. Conf. (GLOBECOM)_ , Dec. 2020, pp. 1–6.
  * [18] ——, “Cellular traffic offloading with optimized compound single-point unicast and cache-based multipoint multicast,” in _IEEE Wireless Commun. and Net. Conf. (WCNC)_ , 2022, pp. 2268–2273.

Proof of Proposition 1.

We constitute the Lagrangian function, and obtain the Karush–Kuhn–Tucker
conditions which read:

$\displaystyle\begin{cases}b_{m}(\theta)\nabla_{m}f+\boldsymbol{\rm
Jh}_{m}\boldsymbol{\lambda}=\boldsymbol{0},\vspace{5 pt}\\\
\sum_{m=1}^{M}\boldsymbol{h_{m}}(\boldsymbol{x}_{m})-\boldsymbol{u}=\boldsymbol{0},\end{cases}$
(20)

where $\boldsymbol{\lambda}$ is the Lagrange multiplier. By considering
Assumption 1 and taking derivative of the recent conditions w.r.t. $\theta$,
we get:

$\displaystyle\\!\\!\\!\\!\\!\\!\begin{cases}\dot{b}_{m}(\theta)\nabla_{m}f+\Big{(}b_{m}(\theta)\nabla_{m}^{2}f+{\sum}_{j=1}^{N}\lambda_{j}\nabla_{m}^{2}h_{m,j}\Big{)}\dot{\boldsymbol{x}}_{n}(\theta)\vspace{-3
pt}\\\ \qquad\qquad\quad+\boldsymbol{\rm
Jh}_{m}\dot{\boldsymbol{\lambda}}=\boldsymbol{0},\vspace{7 pt}\\\
\qquad\sum_{m=1}^{M}\boldsymbol{\rm
Jh}_{m}^{\top}\dot{\boldsymbol{x}}_{m}=\boldsymbol{0},\end{cases}$ (21)

By combining (20) and (21) and considering Assumption 2, the statement
follows.


# On a combinatorial problem in the Secret Santa ritual

Alexander Steinicke  Montanuniversität Leoben, Austria  Markus Penz  Max
Planck Institute for the Structure and Dynamics of Matter, Hamburg, Germany
Basic Research Community for Physics, Leipzig, Germany  Bine Penz  SalTo
Vocale Chor, Salzburg, Austria

###### Abstract

_English._ The Secret Santa ritual, where in a group of people every member
presents a gift to a randomly assigned partner, poses a combinatorial problem
when considering the probabilities involved in the formation of pairs, where
two persons exchange gifts mutually. We give different possible derivations
for such probabilities by counting fixed-point-free permutations with certain
numbers of 2-cycles.

_German._ Das vorweihnachtliche Wichtel-Spiel, bei dem in einer Gruppe von
Personen jedes Mitglied einem zufällig zugeordneten, anderen Mitglied ein
Geschenk überreicht, wirft ein kombinatorisches Problem auf, wenn die
Wahrscheinlichkeiten für das Auftreten von Paaren, wo zwei Personen sich
gegenseitig beschenken, berücksichtigt werden. Wir geben verschiedene
Ableitungen für solche Wahrscheinlichkeiten an, indem fixpunktfreie
Permutationen mit einer bestimmten Anzahl von 2-Zyklen gezählt werden.

This work is dedicated to the public domain. (CC0)

##  I Introduction

This christmas eve one of the authors put forward a combinatorial problem that
originates from a gift-exchange ritual that in this case was practiced in her
choir _SalTo Vocale_ consisting of $N=20$ persons. The ritual is commonly
known as “Secret Santa” wiki-secret-santa , or “Wichteln” in German. The
version we treat here is played as follows: In a group of $N$ people everyone
is randomly assigned a partner to whom at a special event a small gift is
presented. Now there is of course the possibility that the person assigned to
someone is just the one who has picked the other in return. Such a
constellation will be referred to as a _pair_. The question raised by members
of the choir was then: How large is the probability that at least three pairs
are formed, a situation that actually had occurred that year. In order to give
a full answer to the question, we will translate it into a problem of
permutation groups, then find the total number of possible configurations in a
Secret Santa ritual of $N\geq 2$ persons, and finally count the number of
configurations with a given number of pairs. We will see that the correct
answer is given by the number of fixed-point-free permutations $F_{N}$ of $N$
elements and the related number of fixed-point-free permutations with a
certain number of 2-cycles.

##  II Fixed-point-free permutations

Let the participating persons be represented by the numbers
$\\{1,2,\ldots,N\\}$m then the modeling of admissible configuration in a
Secret Santa ritual is given by the fixed-point-free permutations
(derangements), since nobody can pick themselves. For $N=2$ there is obviously
only one possible configuration consisting of one pair, $1\mapsto 2,2\mapsto
1$, or $(21)$ in canonical cycle notation with the largest element always in
front. For $N=3$ the possible configurations are $(312)$ and $(321)$ and pairs
are impossible. Now since pairs are equivalent to 2-cycles the transformation
of the initial question into group theoretical/combinatorial terms is already
achieved.

In counting the number of fixed-point-free permutations $F_{N}$ within the set
of all permutations of $N$ elements $S_{N}$, we first define the set of
permutations that include a fixed-point mapping $(j)$, $S_{N,j}\subseteq
S_{N}$. An intersection of $k$ such sets has $k$ given fixed-points, so it
will still contain $(N-k)!$ elements, and one has $N\choose k$ possibilities
of choosing the fixed-points. By the inclusion-exclusion principle one thus
has wiki-derangement

$|S_{N,1}\cup\cdots\cup S_{N,N}|=\sum_{k=1}^{N}(-1)^{k+1}{N\choose
k}(N-k)!=\sum_{k=1}^{N}(-1)^{k+1}\frac{N!}{k!}.$ (1)

Now clearly the number of fixed-point-free permutations is the total number of
permutations minus the above result, so

$|F_{N}|=N!-\sum_{k=1}^{N}(-1)^{k+1}\frac{N!}{k!}=\sum_{k=0}^{N}(-1)^{k}\frac{N!}{k!}.$
(2)

Extending the sum to infinity gives a direct relation to Euler’s $e$,

$|F_{N}|=\sum_{k=0}^{\infty}(-1)^{k}\frac{N!}{k!}-\sum_{k=N+1}^{\infty}(-1)^{k}\frac{N!}{k!}=\frac{N!}{e}-R_{N}(-1).$
(3)

Here we used the notation $R_{N}(-1)$ for the remainder term of a Taylor
expansion of $N!\,e^{x}$ around 0 at $x=-1$. Since the Taylor coefficients are
simply $(-1)^{k}N!$, by the Remainder Estimation Theorem we have
$|R_{N}(-1)|\leq(N+1)^{-1}\leq 1/3$ for all $N\geq 2$. Accordingly, (3) is
always the integer closest to $N!/e$, or by using the floor function,

$|F_{N}|=\left\lfloor\frac{N!}{e}+\frac{1}{2}\right\rfloor,\quad N\geq 2.$ (4)

##  III Fixed-point-free permutations having at least one $2$-cycle

In this section we will only address permutations with at least one 2-cycle
(one pair or more), which yields already part of the answer. We present three
ways to calculate the number of fixed-point-free permutations with at least
one 2-cycle, $P_{N}\subseteq S_{N}$, providing explicit formulas.

###  III.1 Cycle-types of permutations

First, let us define the set of possible types of a permutation,

$T_{N}=\left\\{(a_{1},\ldots,a_{N})\,\middle|\,a_{i}\geq
0,\sum\nolimits_{i=1}^{N}ia_{i}=N\right\\}.$ (5)

We say that a permutation $\sigma\in S_{N}$ is of type
$a=(a_{1},\ldots,a_{N})\in T_{N}$ if $\sigma$ consists of $a_{i}$ cycles of
length $i$ (cycles of length $i=1$ just describe fixed-points, $i=2$ are the
desired pairs).

The number of permutations of a given type can be calculated easily: For any
permutation of type $a\in T_{N}$ we have $N$ open positions to fill with the
elements $\\{1,\dotsc,N\\}$ where the slots are structured according to the
given type. If for example $N=7$ and $a=(0,2,1,0,0,0,0)$ then the slots are
like $(**)(**)(*{*}*)$. Now there are $N!$ ways how to interchange the slots,
but many such variants will describe the same permutation and we have to get
rid of those ambiguities. First, one can commute the $a_{1}$ cycles of length
1, the $a_{2}$ cycles of length 2 and so on, giving $a_{1}!\cdot\ldots\cdot
a_{N}!$ such possibilities. Then inside each of the $a_{i}$ cycles of length
$i$ one can write any of the $i$ elements in the beginning (canonical cycle
notation with the largest element in front is not employed here), giving again
$1^{a_{1}}\cdot\ldots\cdot N^{a_{N}}$ different possibilities of equivalent
notation. Hence, the number of permutations of type $a$ is
$N!/(1^{a_{1}}\cdot\ldots\cdot N^{a_{N}}\cdot a_{1}!\cdot\ldots\cdot a_{N}!)$.

To answer our initial question, we get a first formula by summing over all
permutations having zero $1$-cycles and at least one $2$-cycle: The size of
the set of these permutations, which we denote by $P_{N}$, is thus given by

$|P_{N}|=\sum_{\begin{subarray}{c}a\in T_{N}\\\ a_{1}=0\\\ a_{2}\geq
1\end{subarray}}\frac{N!}{1^{a_{1}}\cdot\ldots\cdot N^{a_{N}}\cdot
a_{1}!\cdot\ldots\cdot a_{N}!}.$ (6)

Alas, for practical purposes this formula is complicated since the problem is
just transferred into finding all the types considered in the sum. To find out
how many there are, we note that since every type considered in the sum in (6)
fulfills $N=\sum_{i=2}^{N}ia_{i}$ (taking $a_{1}=0$ into account), this also
gives an (increasing) partition of $N$ into integers $\geq 2$. According to
the previous example we would thus have the partition $7=2+2+3$. Taking also
$a_{2}\geq 1$ into account such a partition of $N$ must include at least one
$2$, so we start by considering the possible partitions of $N-2$ instead. All
constituents of the partition of $N-2$ have to be greater or equal to $2$. For
$2\leq v_{1}\leq\dotsb\leq v_{k-1}\leq N-2$ let $(v_{1},\dotsc,v_{k-1})$ be
such a partition of $N-2$ into exactly $k-1$ numbers (one has already been
accounted for). Mapping
$(v_{1},\dotsc,v_{k-1})\mapsto(v_{1}-2,\dotsc,v_{k-1}-2)$ delivers a partition
of $N-2-2(k-1)=N-2k$ into at most $k-1$ constituents. On the other hand,
having a partition of $N-2k$ into at most $k-1$ constituents,
$(u_{1},\dotsc,u_{k-1})$ with $0\leq u_{1}\leq\dotsb\leq u_{k-1}\leq N-2k$, by
mapping $(u_{1},\dotsc,u_{k-1})\mapsto(u_{1}+2,\dotsc,u_{k-1}+2)$ we obtain a
partition of $N-2$ into exactly $k-1$ constituents. This one-to-one relation
between partitions of $N-2$ into exactly $k-1$ constituents that are greater
or equal to $2$ and the partitions of $N-2k$ into at most $k-1$ constituents
enables us to count them. In the example $2+2+3$ is mapped to a partition of
$7-2\cdot 3=1$ which is arguably simple and tells us that there is only a
single allowed partition of $7$ into three constituents greater or equal than
$2$. The possible number $k$ of constituents in any partition that meets our
requirements can never exceed $\lfloor\frac{N}{2}\rfloor$, since each single
constituent is $\geq 2$. This whole maneuver is meaningful because the number
of partitions of $N$ into _at most_ $k$ constituents is given by the partition
functionwiki-partition-function  $p_{k}(N)$. So finally the number of summands
in (6) is given by the formula

$\sum_{k=2}^{\lfloor\frac{N}{2}\rfloor}p_{k-1}(N-2k)+1.$ (7)

Leaving the investigation of cycle types of permutations, next we look for
another way to find an expression for our quantity $|P_{N}|$ which is
hopefully easier to compute.

###  III.2 A recursion for $|P_{N}|$

We can find a way to enumerate the elements of $P_{N}$ by simply looking at a
single number, say $N$. There are various, mutually exclusive possibilities
for $N$: Either $N$ is part of a $2$-cycle, or $N$ is part of a $k$-cycle for
exactly one $k$ with $3\leq k\leq N-2$. Note here, that no $N-1$ cycle is
allowed, otherwise there would be a fixed-point, which we don’t want.
Concentrating on the first possibility, if $N$ in our permutation in $P_{N}$
is part of a $2$-cycle, then there are $N-1$ possibilities for the other
element of this $2$-cycle. The remaining $N-2$ elements may form an arbitrary
permutation without a fixed-point, which can be done in $|F_{N-2}|$ ways. So,
there must be $|F_{N-2}|\cdot(N-1)$ permutations in $P_{N}$ such that $N$ is
in a $2$-cycle. In the other circumstances, where $N$ belongs to some
$k$-cycle, $3\leq k\leq N-2$, there are $\binom{N-1}{k-1}$ possibilities to
choose the remaining $k-1$ elements of the cycle, forming $(k-1)!$ different
cycles. The rest of the same permutation apart from this cycle must again be
fixed-point-free and have at least one $2$-cycle, giving us $|P_{N-k}|$
possibilities. Summing up all those possibilities (which exhaust the set
$P_{N}$) we get that for $N\geq 2$,

$\displaystyle|P_{N}|$
$\displaystyle=\sum_{k=3}^{N-2}\binom{N-1}{k-1}(k-1)!\cdot|P_{N-k}|+|F_{N-2}|\cdot(N-1)$
(8)
$\displaystyle=\sum_{k=2}^{N-3}|P_{k}|\cdot\frac{(N-1)!}{k!}+|F_{N-2}|\cdot(N-1),$

which is the first recursion for $|P_{N}|$, since we know that
$|P_{0}|=|P_{1}|=0$. Using this recursion to calculate $|P_{N+1}|$ we
immediately get that $|P_{2}|=1$ (which is what we expected) and, for $N\geq
4$,

$\displaystyle|P_{N}|$
$\displaystyle=(N-1)\sum_{k=2}^{N-4}|P_{k}|\frac{(N-2)!}{k!}+|P_{N-3}|(N-1)(N-2)+|F_{N-2}|\cdot(N-1)$
(9)
$\displaystyle=(N-1)\left(|P_{N-1}|-|F_{N-3}|\cdot(N-2)\right)+|P_{N-3}|\cdot(N-1)(N-2)+|F_{N-2}|\cdot(N-1).$

We calculate the expression $|F_{N-2}|\cdot(N-1)-|F_{N-3}|\cdot(N-2)(N-1)$ to
get

$\displaystyle(N-1)!\sum_{k=0}^{N-2}\frac{(-1)^{k}}{k!}-(N-1)!\sum_{k=0}^{N-3}\frac{(-1)^{k}}{k!}=(N-1!)\frac{(-1)^{N-2}}{(N-2)!}=(-1)^{N}(N-1),$
(10)

and hereby obtain the recursion for $|P_{N}|$,

$\displaystyle|P_{N}|=(N-1)\left(|P_{N-1}|+|P_{N-3}|\cdot(N-2)+(-1)^{N}\right),$
(11)

which already seems quite practical to calculate some values of $|P_{N}|$:

$N$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
---|---|---|---|---|---|---|---|---|---|---|---
$|P_{N}|$ | 0 | 0 | 1 | 0 | 3 | 20 | 105 | 714 | 5845 | 52632 | 525105

Although formula (11) looks simpler, in order to find a compact expression for
$|P_{N}|$, we will use the seemingly more cumbersome form (8). Note that
because of $|P_{0}|=|P_{1}|=0$ we can write the first equality of (8) as

$|P_{N}|=\sum_{k=0}^{N}\frac{(N-1)!}{(N-k)!}\cdot|P_{N-k}|\cdot\chi_{k\geq
3}+|F_{N-2}|\cdot(N-1),$ (12)

where $\chi_{k\geq 3}=1$ if $k\geq 3$ and $0$ if $k\in\\{0,1,2\\}$. In the
following, we will now use the technique of generating functions of sequences,
where sequences $(f_{n})_{n\geq 0}$ are represented by their according formal
power series $\sum_{n=0}^{\infty}f_{n}x^{n}$ (see e.g. Chapter 3 in the book
of M. Bóna bona ). In order to apply this machinery, we multiply both sides of
the recursion (12) with $x^{N}/(N-1)!$ and sum over $N=2,\ldots,\infty$ to get

$\sum_{N=2}^{\infty}|P_{N}|\cdot\frac{x^{N}}{(N-1)!}=\sum_{N=2}^{\infty}\sum_{k=0}^{N}\frac{x^{N}}{(N-k)!}\cdot|P_{N-k}|\cdot\chi_{k\geq
3}+\sum_{N=2}^{\infty}|F_{N-2}|\cdot(N-1)\frac{x^{N}}{(N-1)!}.$ (13)

Recognizing that the first sum on the right hand side can be started from
$N=0$ because of $|P_{0}|=|P_{1}|=0$ and then can be rewritten as a Cauchy
product, we find

$\displaystyle x\sum_{N=1}^{\infty}|P_{N}|\cdot\frac{x^{N-1}}{(N-1)!}$
$\displaystyle=\left(\sum_{N=0}^{\infty}|P_{N}|\frac{x^{N}}{N!}\right)\cdot\left(\sum_{N=0}^{\infty}\chi_{N\geq
3}\cdot x^{N}\right)+\sum_{N=2}^{\infty}|F_{N-2}|\frac{x^{N}}{(N-2)!}$ (14)
$\displaystyle=\left(\sum_{N=0}^{\infty}|P_{N}|\frac{x^{N}}{N!}\right)\cdot\frac{x^{3}}{1-x}+x^{2}\sum_{N=0}^{\infty}|F_{N}|\frac{x^{N}}{N!}$
$\displaystyle=\left(\sum_{N=0}^{\infty}|P_{N}|\frac{x^{N}}{N!}\right)\cdot\frac{x^{3}}{1-x}+x^{2}\left(\sum_{N=0}^{\infty}\sum_{k=0}^{N}\frac{(-1)^{k}}{k!}x^{N}\right)$
$\displaystyle=\left(\sum_{N=0}^{\infty}|P_{N}|\frac{x^{N}}{N!}\right)\cdot\frac{x^{3}}{1-x}+x^{2}\left(\sum_{N=0}^{\infty}\frac{(-x)^{N}}{N!}\right)\cdot\left(\sum_{N=0}^{\infty}x^{N}\right)$
$\displaystyle=\left(\sum_{N=0}^{\infty}|P_{N}|\frac{x^{N}}{N!}\right)\cdot\frac{x^{3}}{1-x}+\frac{x^{2}e^{-x}}{1-x}.$

We cancel $x$ and denote $p(x)=\sum_{N=0}^{\infty}|P_{N}|x^{N}/N!$, which
leads us to the ordinary differential equation

$\frac{\mathrm{d}}{\mathrm{d}x}p(x)=p(x)\cdot\frac{x^{2}}{1-x}+\frac{xe^{-x}}{1-x},\quad
p(0)=0,$ (15)

which can be solved by the formula of variation of constants, using the
integral $\int_{0}^{x}y^{2}/(1-y)\,\mathrm{d}y=-x^{2}/2-x-\log(1-x)$ that
holds for $x<1$, to end up with

$\displaystyle p(x)$
$\displaystyle=\exp\left(-\frac{x^{2}}{2}-x-\log(1-x)\right)\int_{0}^{x}\frac{ye^{-y}}{1-y}\cdot\exp\left(\frac{y^{2}}{2}+y+\log(1-y)\right)\,\mathrm{d}y$
(16) $\displaystyle=\frac{e^{-x^{2}/2-x}}{1-x}\int_{0}^{x}y\cdot
e^{y^{2}/2}\,\mathrm{d}y=\frac{e^{-x}}{1-x}-\frac{e^{-x^{2}/2-x}}{1-x}.$

The series expansion of the resulting function above can be written
(multiplying out the Cauchy products) as

$\sum_{N=0}^{\infty}|P_{N}|\frac{x^{N}}{N!}=p(x)=\sum_{N=0}^{\infty}\sum_{k=0}^{N}\frac{(-1)^{k}}{k!}x^{N}-\sum_{N=0}^{\infty}\sum_{k=0}^{N}\sum_{j=0}^{k}\frac{(-1)^{k-j}(-1)^{j/2}}{(k-j)!\,\frac{j}{2}!\,2^{j/2}}\chi_{2\mathbb{N}}(j)\cdot
x^{N}.$ (17)

Here $\chi_{2\mathbb{N}}$ denotes the characteristic function of the even
numbers. From this we obtain the explicit formula for $|P_{N}|$ term by term

$\displaystyle|P_{N}|=N!\sum_{k=0}^{N}\frac{(-1)^{k}}{k!}-N!\sum_{k=0}^{N}\frac{(-1)^{k-j}(-1)^{j/2}}{(k-j)!\,\frac{j}{2}!\,2^{j/2}}\chi_{2\mathbb{N}}(j).$
(18)

It is no mere coincidence that the first sum here is $|F_{N}|$ as we will also
see in the next section, where we achieve the same result in (25) with a
different method.

###  III.3 A further method to obtain $|P_{N}|$ and asymptotic results

The formula for $|P_{N}|$ found in the end of the last paragraph is explicit
and ready to use for further mathematical treatment, which we will do in this
section. Before however, we will use a theorem from enumerative combinatorics
which leads to a quick way to compute the expression for $|P_{N}|$. The key
idea in this section is to look at the set of permutations that have no fixed-
points and neither possess $2$-cycles. The cardinality of this set can be
obtained via Theorem 4.34 from the combinatorics book of M. Bónabona  (and
equals the second summand of (18)).

######  Theorem.

Let $M$ be any set of positive integers and let $g_{M}(n)$ be the number of
permutations of length $n$ whose cycle lengths are all elements of $M$. Then

$G_{M}(x)=\sum_{N=0}^{\infty}g_{M}(N)\frac{x^{N}}{N!}=\exp\left(\sum_{k\in
M}\frac{x^{k}}{k!}\right).$ (19)

In the case of permutations having cycle lengths strictly larger than $2$, the
set $M$ must be $\\{3,4,\dotsc\\}$. Hence,

$G_{\geq 3}(x)=\exp\left(\sum_{k=3}^{\infty}\frac{x^{k}}{k!}\right),$ (20)

by the above theorem. With the Taylor-series expansion
$-\log(1-x)=\sum_{k=1}^{\infty}\frac{x^{k}}{k!}$ that holds for $-1\leq x<1$,
we get

$G_{\geq
3}(x)=\exp\left(-\log(1-x)-x-\frac{x^{2}}{2}\right)=\frac{\exp\left(-x-\frac{x^{2}}{2}\right)}{1-x}.$
(21)

We now use the series expansion of the exponential and the geometric series to
arrive at

$G_{\geq
3}(x)=\left(\sum_{k=0}^{\infty}x^{k}\right)\left(\sum_{k=0}^{\infty}(-1)^{k}\frac{x^{k}}{k!}\right)\left(\sum_{k=0}^{\infty}\frac{(-1)^{k}x^{2k}}{2^{k}k!}\right).$
(22)

Multiplying out the appearing Cauchy products and simplifying the arising sums
we get that the coefficient $g_{\geq 3}(N)$ from (19) equals

$g_{\geq
3}(N)=N!\sum_{k=0}^{N}\sum_{j=0}^{k}\frac{(-1)^{k-j}(-1)^{j/2}}{(k-j)!\,\frac{j}{2}!\,2^{j/2}}\chi_{2\mathbb{N}}(j).$
(23)

The inner sum can be further contracted to

$g_{\geq
3}(N)=N!\sum_{k=0}^{N}(-1)^{k}\sum_{j=0}^{\lfloor\frac{k}{2}\rfloor}\frac{(-1)^{j}}{(k-2j)!\,j!\,2^{j}}.$
(24)

To find the number $|P_{N}|$ we now just have to subtract the obtained
quantity from the number of all permutations without fixed-points (2), so

$|P_{N}|=|F_{N}|-g_{\geq 3}(N).$ (25)

Having obtained a decent formula, we are ready to calculate the asymptotic
probability to have at least one pair: We know that there are overall
$|F_{N}|$ possible Secret Santa configurations. The relative part of
configurations where at least one pair exchanges gifts is then
$|P_{N}|/|F_{N}|$ which equals

$\frac{|P_{N}|}{|F_{N}|}=1-\frac{g_{\geq 3}(N)}{|F_{N}|}.$ (26)

In the limit $N\to\infty$ the two sums of (23) can be split into a Cauchy
product again and one has

$\lim_{N\to\infty}\frac{g_{\geq
3}(N)}{N!}=\left(\sum_{k=0}^{\infty}\frac{(-1)^{k}}{k!}\right)\left(\sum_{k=0}^{\infty}\frac{(-1)^{k/2}}{\frac{k}{2}!\,2^{k/2}}\chi_{2\mathbb{N}}(k)\right).$
(27)

That means in the asymptotics of (26) the $|F_{N}|$ given by (2) cancels and
we are left with

$\lim_{N\to\infty}\frac{|P_{N}|}{|F_{N}|}=1-\sum_{k=0}^{\infty}\frac{(-1)^{k/2}}{\frac{k}{2}!\,2^{k/2}}\chi_{2\mathbb{N}}(k)=1-e^{-1/2}\approx
0.393.$ (28)

If the whole world plays Secret Santa, we can expect at least one gift-
exchanging with a probability of about 40%. As one can see in Fig. 1
convergence is really fast.

Figure 1: probability for at least one pair

##  IV Fixed-point-free permutations with exactly $k$ $2$-cycles

Going back to the initial question, we are not only interested in the number
of configurations in Secret Santa that admit at least one pair, but in the
number where exactly $k$, $0\leq k\leq\lfloor\frac{n}{2}\rfloor$, pairs
exchange gifts. The set of fixed-point-free permutations of $N$ elements that
have exactly $k$ $2$-cycles will be called $P_{N}^{k}$. This will lead us then
to a final answer. Now how big are the probabilities that such things happen?
Let us tackle this question with a similar strategy as when we investigated
permutations of a given cycle type. We can think about a permutation being
split up into $k$ $2$-cycles and the remaining ($2$-cycle-free) permutation.
In choosing the first element of the first $2$-cycle there are $N$
possibilities, for the second element of the first $2$-cycle there are $N-1$
possibilities, for the first element of the second $2$-cycle then $N-2$
possibilities and so on, until we have $(N-(2k-1))$ possibilities left for the
second element of the $k$-th $2$-cycle. In each one of the $k$ $2$-cycles any
of its two elements can be written first, so there are $2^{k}$ ways to
describe the same $2$-cycles. Moreover, due to the commutativity of cycles
there are $k!$ ways that the $2$-cycles just constructed can be arranged
equivalently. Summarizing, we have

$\frac{N(N-1)\dotsm(N-(2k-1))}{2^{k}k!}=\frac{N!}{(N-2k)!2^{k}k!}$ (29)

ways to form $k$ $2$-cycles with $2k$ of the $N$ numbers. For the remaining
permutation of $N-2k$ elements without $1$\- or $2$-cycles, there are $g_{\geq
3}(N-2k)$ possibilities, with $g_{\geq 3}$ from (23). Hence, the number of
fixed-point-free permutations with exactly $k$ $2$-cycles is

$|P_{N}^{k}|=\frac{N!}{(N-2k)!2^{k}k!}\cdot g_{\geq
3}(N-2k)=\frac{N!}{2^{k}k!}\sum_{m=0}^{N-2k}\sum_{j=0}^{m}\frac{(-1)^{m-j}(-1)^{j/2}}{(m-j)!\,\frac{j}{2}!\,2^{j/2}}\chi_{2\mathbb{N}}(j).$
(30)

In the above formula we can correctly check that $|P_{N}^{0}|=g_{\geq 3}(N)$,
the number of fixed-point-free permutations with no (exactly zero) $2$-cycles.
Hence, the probability to have exactly $k$ pairs that exchange presents is
$|P_{N}^{k}|/|F_{N}|$. With the same type of manipulations that lead to (28)
we arrive at the asymptotic probability

$\lim_{N\to\infty}\frac{|P_{N}^{k}|}{|F_{N}|}=\frac{\left(\frac{1}{2}\right)^{k}e^{-1/2}}{k!}.$
(31)

This shows that, asymptotically, the probability that exactly $k$ pairs draw
each other follows a Poisson distribution with parameter $\frac{1}{2}$. In the
very case that $3$ pairs of people exchange gifts when playing Secret Santa
with a high number of persons, we get a small probability of approximately
$0.013$.

We can (via e.g. the Skorohod representationskorohod-representation ) assume
that there are (discrete) random variables $(X_{N})_{N\geq 2}$ (the question
is not very interesting for $N=0$ or $1$) converging almost surely to a random
variable $X$, where $\mathbb{P}(X_{N}=k)=|P_{N}^{k}|/|F_{N}|$ and
$\mathbb{P}(X=k)=e^{-1/2}/(2^{k}k!)$. Thus the random variable $X_{N}$
describes the number of pairs found playing Secret Santa with $N$ players and
$X$ describes the same for the limiting case (which would correspond to
playing it with infinitely many players). Let us estimate for $s\in\mathbb{R}$
the expectation

$\displaystyle\mathbb{E}\left(e^{sX_{N}}\right)$
$\displaystyle=\sum_{k=0}^{\infty}e^{sk}\frac{|P_{N}^{k}|}{|F_{N}|}=\sum_{k=0}^{\infty}\frac{e^{sk}}{2^{k}k!\sum_{m=0}^{N}\frac{(-1)^{m}}{m!}}\sum_{m=0}^{N-2k}\sum_{j=0}^{m}\frac{(-1)^{m-j}(-1)^{j/2}}{(m-j)!\,\frac{j}{2}!\,2^{j/2}}\chi_{2\mathbb{N}}(j)$
$\displaystyle\leq\sum_{k=0}^{\infty}\frac{e^{sk}}{2^{k}k!\frac{1}{3}}\sum_{m=0}^{\infty}\sum_{j=0}^{m}\frac{\chi_{2\mathbb{N}}(j)}{(m-j)!\,\frac{j}{2}!\,2^{j/2}}=3\sum_{k=0}^{\infty}\frac{e^{sk}}{2^{k}k!}\sum_{m=0}^{\infty}\frac{1}{m!}\sum_{m=0}^{\infty}\frac{1}{2^{m}m!}$
$\displaystyle=3\sum_{k=0}^{\infty}\frac{e^{sk}\cdot e\cdot
e^{\frac{1}{2}}}{2^{k}k!}=3e^{e^{s/2}+\frac{3}{2}},$ (32)

where for the inequality we used that the double sum can be estimated by the
infinite series adding up the absolute value of the summands. We further used
that the Leibniz partial sums $\sum_{m=0}^{N}\frac{(-1)^{m}}{m!}$ for $N\geq
2$ are always larger than the one for the smallest odd $N\geq 2$, which is
$1-1+\frac{1}{2}-\frac{1}{6}=\frac{1}{3}$. Therefore, $\sup_{N\geq
2}\mathbb{E}\left(e^{sX_{N}}\right)<\infty$ for all $s\in\mathbb{R}$ and by
dominated convergence we get that all (even the exponential) moments of
$X_{N}$ converge to the moments of $X$ that are those of a Poisson
distribution with parameter $\tfrac{1}{2}$. The expected number of $2$-cycles
in the long run is then just the parameter of the Poisson distribution, which
is $\frac{1}{2}$.

The final answer is still due: How large is the probability for three _or
more_ pairs? In this case we just have to eliminate the configurations with
exactly zero, one, or two pairs. This is now an easy task applying the above
result, and we get

$\lim_{N\to\infty}\frac{|F_{N}|-|P_{N}^{0}|-|P_{N}^{1}|-|P_{N}^{2}|}{|F_{N}|}=1-\left(1+\frac{1}{2}+\frac{1}{8}\right)e^{-1/2}=1-\frac{13\,e^{-1/2}}{8}\approx
0.014$ (33)

In the case of the choir $N=20$ persons and the probability from (33) is
already equal to the asymptotic one up to 7 digits after the comma. This fast
convergence rate is visible in Fig. 2, where also the peak of probability for
$N=6$ is revealed.

Figure 2: probability for at least three pairs

## References

  * (1) Secret Santa. In _Wikipedia_. Retrieved Dec 26, 2019, from https://en.wikipedia.org/wiki/Secret_Santa
  * (2) Derangement. In _Wikipedia_. Retrieved Dec 26, 2019, from https://en.wikipedia.org/wiki/Derangement
  * (3) Partition function (number theory). In _Wikipedia_. Retrieved Jan 23, 2020, from https://en.wikipedia.org/wiki/Partition_function_(number_theory)
  * (4) M. Bóna, Introduction to Enumerative Combinatorics. McGrawHill, New York, 2007.
  * (5) Skorohod’s representation theorem. In _Wikipedia_. Retrieved Feb 7, 2020, from https://en.wikipedia.org/wiki/Skorokhod%27s_representation_theorem


# A free-group valued invariant of free knots

Vassily Olegovich Manturov111Moscow Institute of Physics and Technology, Kazan
Federal University, Northeastern University (China), vomanturov @ yandex.ru

###### Abstract

The aim of the present paper is to construct series of invariants of free
knots (flat virtual knots, virtual knots) valued in free groups (and also free
products of cyclic groups)

AMS MSC: 57M25, 57M27, 57M05, 57M07, 20F36

Keywords: Knot, Virtual Knot, Group, Parity, Word, Invariant, Picture,
Cylinder, Legendrian, Transverse, Word, Conjugacy.

##  1 Introduction. Preliminaries

Knots are encoded by Gauss diagrams modulo Reidemeister moves. For classical
knots one imposes the planarity restriction on the set of Gauss diagrams. Once
we forget planarity, we get virtual knots. Gauss diagrams have all chords
endowed with two bits of information: local writhe number and the direction
from one point (“over”) to the other point (“under”). If we abandon these two
bits of information, we get arbitrary Gauss diagrams modulo the three
Reidemeister moves as depicted in Fig. 1, top.

Figure 1: Gauss diagrams and Reidemeister moves

The other way to encode Gauss diagrams is to use $1$-component framed
$4$-graphs. For more details, see [5]. In the bottom part of Fig. 1 we show
the Reidemeister moves in the language of framed $4$-graphs.

One can also define long free knots by breaking a framed $4$-graph at a point
and pulling the two ends to the infinity; certainly, for long knots it is not
allowed to perform moves over the infinity.

We shall often switch from free knots to long free knots; the main advantage
of free knots is the presence of a reference point; one can naturally see that
if we associate a word to a free knot, we can associate a cyclic word to a
(compact free knot); yet another advantage of free knots is the possibilities
to fix some “coordinate system” which allows to “justify” the names of
letters; actually, for compact free knots the word associated to letters will
be sometimes well defined only up to some remaining letters, which is some
outer automorphism of the group in question; for long free knots there is no
such problem.

Here by components of a framed $4$-graph we mean unicursal curves. The same
can be used to define free links: we take similar (Gauss) chord diagrams with
many core circles and arbitrary framed $4$-graphs modulo Reidemeister moves.

Free knots (initially introduced by Turaev [9]) under the name of homotopy
classes of Gauss words were first conjectured to be trivial; it was disproved
in [5], see also [2].

The parity theory turns out to be a very powerful tool in the study of free
knots and links, and in [5] (and later in [3], [7]) we demonstrated the
following features of parity.

  1. 1.

One can construct picture-valued invariants of free knots (by pictures we mean
linear combinations of free knot diagrams)

  2. 2.

There is an invariant called parity bracket, $[\cdot]$, which for some free
knot diagrams $K$ gives us

$[K]=K.$

  3. 3.

The above formula gives rise to the following principle: if a diagram is
complicated enough then it realises itself. The simplest variant of this
principle is: If all crossings of the diagram $K$ are odd and there is no way
to apply the second decreasing move to $K$ then any diagram $K^{\prime}$
equivalent to $K$ admits a smoothing which is identical to $K$.

  4. 4.

We often see that locally minimal free knot diagrams (those which do not admit
decreasing Reidemeister moves) are globally minimal in a strong sense (e.g.,
are contained in any equivalent diagrams).

  5. 5.

Such results can be partially extended to the realm of cobordisms: if free
knots can be capped by some “folded” disc then they can be capped by a disc in
a simple way; for more details see [1].

  6. 6.

Knots with parity behave like links: one can explicitly construct $2$-fold
coverings over free/flat/virtual/pseudo/quasi knots by links. [3].

Actually, the parity appears whenever one has some additional
“${\mathbb{Z}}_{2}$-homology” condition: roughly speaking, one has “even” and
“odd” homology classes associated to crossings in a certain way.

The property “if a diagram is complicated enough then it realises itself”
makes free knots similar to free groups (see [7]). Indeed, if we have a free
group $F^{n}$ in generators, say, $a_{1},\cdots,a_{n}$, then for any reduced
word $W$ any word $W^{\prime}$ equivalent to $W$ contains $W$ as a “subword”,
i.e., $W$ can be obtained from $W^{\prime}$ by iterative cancellation of some
pairs of $a_{j}a_{j}^{-1}$ or $a_{j}^{-1}a_{j}$.

Hence, there is an obvious analogy between free knots and free words; here we
have:

  1. 1.

Reductions $\Longleftrightarrow$ second decreasing Reidemeister moves;

  2. 2.

Reduced words $\Longleftrightarrow$ minimal representatives of diagrams.

Certainly, the above correspondence is not $1\longleftrightarrow 1$. We want
to exploit this correspondence in both directions: we try to study groups by
using knots and knots by using groups.

Here we concentrate on the

  1. 1.

Free knots $\to$ elements of a free group;

  2. 2.

(Compact) free knots $\to$ conjugacy classes of a free group.

The general plan to be realised for topological problems is as follows:

  1. 1.

First, we look at some “homological” conditions;

  2. 2.

These conditions allow one to get a certain “labels”
$l_{1},l_{2},\cdots,l_{n}$;

  3. 3.

Construct the free group $\mathbb{Z}_{l_{1}}*\cdots*\mathbb{Z}_{l_{n}}$ or the
free product $\mathbb{Z}_{2}*\cdots*\mathbb{Z}_{n}$ of generators
$a_{1},\cdots,a_{n}$ corresponding to $l_{1}\cdots l_{n}$.

  4. 4.

Try to prove that when we apply equivalence (say, Reidemeister moves) to the
initial topological objects (say, knots) then different generators in the
image do not commute.

In fact, the last step is the most complicated one. Actually, it is not too
difficult to grasp some homological information for crossings so that the two
crossings related by the second Reidemeister move are cancelled as follows:

$a_{i}a_{i}^{-1}=1.$

Having some non-trivial homological information, one can avoid writing down
generators corresponding to the first Reidemeister moves: if there were such
generators, say, $a_{j}$, they would give rise to the painful 222Actually, the
relation $a_{j}^{2}$ is less painful, but sometimes we may count say, only
left ends and not right chord ends relation

$a_{j}=1.$

The hardest problem here is the existence of the third Reidemeister move. It
gives rise to the some transformation of a word in three places.

Figure 2: Transformation of a word in three places

In each of these three places the word is transformed by the commutativity
relation $a_{j}a_{i}=a_{i}a_{j}$ which does not allow one to construct a
genuine free group invariant.

In the present paper, we shall show the very first instance how this
difficulty can be overcome and how one can get

  1. 1.

From homology to homotopy;

  2. 2.

From free abelian groups to free groups.

In the present paper, we shall construct various types of letters which are
all due to the existence of just one source of homological information, the
Gaussian parity, which exists for free knots.

This paper is one of the series of papers having the goal to study classical
objects (knots, links, their cobordisms) by using virtual knot methods. This
is in some sense “the last piece of the whole puzzle”: we get invariants of
free knots. The first pieces of the puzzle will start from classical knots and
transform them to “virtual” objects having non-trivial parity etc.

Here we note that knots in the cylinder already possess enough structure to
use virtual knot theory methods; on the other hand, cylinders naturally appear
in the study of classical knots and links (For more details, see [7]).

###  1.1 The structure of the paper

The paper is organised as follows. In Section 2, we construct (some old) the
invariants of free knots valued in free groups and prove its invariance.

Also, we informally discuss various ways of generalisation for this invariant.

In Section 3, we calculate the main example which shows that free knots can
give rise to “highly non-commutative” words in the free group.

We conclude the paper by a discussion of further directions like cobordisms
and Legendrian knots.

###  1.2 Acknowledgements

The author is grateful to Kim Seongjeong, Kim Sera and L.Kauffman and J.Wu for
various fruitful discussions.

This work was funded by the development program of the Regional Scientific and
Educational Mathematical Center of the Volga Federal District, agreement N
075-02-2020.

##  2 The construction of the invariants.
The invariance proof

In the present section, we describe the whole procedure how to construct the
invariant of free knots valued in free groups. To make the process clear and
accessible for other types of parities (say, homological), we describe it
step-by step.

  1. 1.

The first step will consist in construction of some integer-valued invariant
which can be reduced to some count: we count the number of chords which are
“non-trivial” by some reasons.

  2. 2.

The second step will give rise to the invariant valued in the infinite
dihedral 333there is a natural bijection between the elements of the group
below and the elements of the infinite dihedral group group which we write
down as: $G=\langle
a,b,b^{\prime}|a^{2}=b^{2}=(b^{\prime})^{2}=1,ab=b^{\prime}a\rangle.$

  3. 3.

The third step will give rise to an invariant valued in a group of exponential
growth. The key ingredient is the possibility to get rid of the relations
$b^{2}=b^{\prime-2}$ by renaming letters and rewriting words. 444Actually,
this procedure can be accurately defined by using wreath products of groups
with ${\mathbb{Z}}_{2}$ but we don’t want to give much detail in this short
note.

###  2.1 The first step

Let $K$ be a Gauss diagram; we say that two chords $c,c^{\prime}$ are linked
if the endpoints of $c$ alternate with the endpoints of $c^{\prime}$.
Sometimes we shall write $\langle c,d\rangle=1\in{\mathbb{Z}}_{2}$ if $c,d$
are linked and $\langle c,d\rangle=0\in{\mathbb{Z}}_{2}$, otherwise.

A chord $c$ is even if the number of chords it is linked with, is even, and
odd if it is odd.

Now, the reader can immediately see that:

  1. 1.

the chord does not change its parity when a Reidemeister-3 move is applied;

  2. 2.

if two chords are cancelled by a Reidemeister-2 move then they have the same
parity;

  3. 3.

A chord taking part in the first Reidemeister move is even.

  4. 4.

The number of odd chords of a Gauss diagram is even.

Let $K$ be an oriented long knot diagram. We enumerate the endpoints as they
appear according to the orientation; we say that an odd chord is of the first
type if it is linked with evenly many even chords and of the second type
otherwise.

Moreover, we say that an odd chord is of the first sort if both points are in
odd positions and it is linked with evenly many even chords or if both
endpoints of it are even and it is linked with oddly many even chords.

Otherwise we say that the odd chord is of the second sort.

Actually, one can make a distinction between various even chords by
introducing the notion of hierarchy where odd chords are of hierarchy $0$,
even chords of the first type are of hierarchy $2$ and other even chords of
type $2$ have hierarchy $n$, where $n\in\\{2,3,\cdots\\}\cup\\{\infty\\}$.
[12].

The results of the present paper can be definitely extended if we use more
information about the hierarchy, but here the type will be sufficient.

Figure 3: The main example and the corresponding word in the group $G$

Now, we define $l$ to be twice 555We take twice the number of chords in order
to agree with [6] the number of odd chords of the first sort minus twice the
number of odd chords of the second sort.

######  Theorem 1.

If $K_{1}$, $K_{2}$ represent the same long free knot then
$l(K_{1})=l(K_{2})$. If two long free knots are obtained from some free knot
$K$ by breaking it at two different points then $l(K_{1})=\pm l(K_{2})$.

The proof follows from the step-by-step check of the Reidemeister moves. For
more details, see [6].

Note that the here $l$ is nothing but just bare count (if we deal with compact
knots, not long ones, we get just relative signs).

###  2.2 The second step

Now, we undertake an attempt to encode the above information about the bare
count of odd chords by means of a (non-abelian) group. Let $K$ be a long Gauss
diagram. We create the word $\phi(K)$ by using the following rule: we follow
the orientation of $K$ and whenever we meet an even chord, we write $a$, when
we have an odd chord, we write $b$ for ends of chords of the first type or
$b^{\prime}$ for ends of chords of the second type see Fig.4 below.

Figure 4: A long free knot $K$ and the word
$babababb^{\prime}ab^{\prime}ab^{\prime}ab^{\prime}$

######  Theorem 2.

If $K_{1},K_{2}$ are equivalent as long free knots then
$\phi(K_{1})=\phi(K_{2})$ in $G$.

###### Proof.

One just has to check that the first Reidemeister move gives: $aa=1$, the
second Reidemeister move gives $aa=1$ or $bb=1$ or $b^{\prime}b^{\prime}=1$;
finally, the third Reidemeister move gives rise to three substitutions each of
which is either identical or $ab=b^{\prime}a$ or $ab^{\prime}=ba$. ∎

Hence, we see that the information from a group obtained here is not stronger
than just the invariant $l$.

Indeed, when we look at the Cayley graph of the group ${\mathbb{Z}}$, one can
see that the group has a natural bijection (which is an isomorphism on finite
index subgroups) with the infinite dihedral group. However, the number $l$ now
turns into a geometrical interpretation as the distance in the Cayley graph.
666Indeed, look at the bottom part of Fig. 4; Having a word, we can consider
the odd letters $b$ and $b^{\prime}$ as steps to the right/ to the left; the
letter a moves a point from the bottom line to the top line. Hence, any word
in $a,b,b^{\prime}$ with evenly many instances of a gives rise to some element
$(bb^{\prime})^{k}or(b^{\prime}b)^{k}$ which in turn can be considered as a
horisontal shift by $\pm 2k.$

###  2.3 The third step

Let us write more carefully at the map constructed on the second step. Can it
be enhanced? In fact, we are very much restricted in our attempt to write down
all maps in terms of groups and group homomorphisms.

The letters b and b’ are treated in two different ways: one way is to count
them by $\pm 1$ according to the sort; the other way is to keep track of the
existence of ′ to have a word in $G$.

We can reconciliate these two approaches as follows.

Actually, we may treat $b$ in different positions differently; to describe
this completely from the algebraic point of view, one should use lots of
wreath products and more elaborate machinery; we want to omit it for the first
short paper.

However, one can consider the following group

$G^{\prime}=\langle a,b,b^{\prime}|a^{2}=1,ab=(b^{\prime})^{-1}a.\rangle$

Note that unlike $G$, the group $G^{\prime}$ has exponential growth, and
$b,b^{\prime}$ do not commute.

Now, the invariant

$\psi(K)$

is obtained from $\phi(K)$ by using the rule:

replace all letters $b^{\prime}$ in even positions with $(b^{\prime})^{-1}$
and replace $b$ in even positions with $b^{-1}$.

######  Remark 1.

Actually, we can go even a bit further and get rid of the relation $a^{2}=1$
if we pass from any  even chords to special even chords, but for our purposes
(exponential growth) it suffices just to work with $G^{\prime}$.

######  Theorem 3.

If two long knots $K_{1}$ and $K_{2}$ are equivalent then
$\psi(K_{1})=\psi(K_{2})$ as elements of the group $G^{\prime}$.

###### Proof.

The proof follows from the direct check of the Reidemeister moves (actually,
this is a minor modification of Theorem 2). ∎

Looking at Fig. 4, we readily see that for the knot $K$ given there we have

$\psi(K)=bababab(b^{\prime})^{-1}a(b^{\prime})^{-1}a(b^{\prime})^{-1}a(b^{\prime})^{-1}$

##  3 An example

Let us consider the free knot $K$ given in Fig. 4.

The invariant $l=\pm 8$ says that it is not trivial and it is not slice
because if has four chords of the first sort (if we look at the compact knot,
we say that we have four chords of the same sort), so they can not be
cancelled by means of Reidemeister moves and can not be spanned by a disc. On
the Cayley graph these eight chord ends sum up and give $8$; this number $8$
is invariant 777There are various cobordism obstructions which originate from
the count of some “odd things” with writhe numbers serving signs [4], however,
here odd chords themselves have other signs coming from other reasonings; the
reader can readily expand these invariant for the case of virtual knots. .

The group $G$ actually gives the same information: though it is not abelian,
it has an abelian group of finite index, hence the only information one can
get in this group is just $(bb^{\prime})^{k}$ (in our case $k=4$).

From the construction of the group $G^{\prime}$ we immediately get the
following theorem.

######  Theorem 4.

Let $K_{1},K_{2}$ be two long free knots. Then for the connected sum
$\psi(K_{1}{\\#}K_{2})=\psi(K_{1})\cdot\lambda\psi(K_{2})$, where $\lambda$ is
some automorphism of the group $G^{\prime}$.

Here one can naturally see that the invariant $\psi$ can easily detect

  1. 1.

Free knot invertibility;

  2. 2.

Any sorts of free knot mutations.

Of course, having this done for free knots, we have lots of consequences for
virtual knots. Certainly, the next goal will be to do the same for classical
knots and for knots in $3$-manifolds.

##  4 Further directions

Here we sketch some directions of further investigation we are undertaking
now. In each of the problems we highlight the main problem which seems to be
tractable by using the approach given in the present paper.

  1. 1.

First, it is rather obvious that free knots almost never commute. Indeed, the
group $G^{\prime}$ is non-abelian; to show that for long knots $K_{1},K_{2}$
we have $K_{1}{\\#}K_{2}\neq K_{2}{\\#}K_{1}$ we have to look carefully at the
group $G^{\prime}$ constructed above.

  2. 2.

Certainly, the groups constructed here can be enhanced by large if we use not
only parity but also parity hierarchy; one can construct invariants of free
knots valued in free products of groups whose generators are “responsible for”
the existence of certain “sub-knot structures”.

  3. 3.

The invariant $l$ (counted with $\pm$ sign) is certainly a sliceness
obstruction for free knots but it can’t say anything about the slice genus of
free knots. The problem is that having a non-zero value of $l$ (say, $l=8$)
and applying cut-and-paste techniques, we can “roughly” split $8$ into the sum
$4+4$ and then paste $4$ with $-4$ and get $0$.

Having groups which are close to free groups one can use commutator length
techniques and estimate from below the number of operations one needs to cut
the word into, in order to compose a trivial element.

  4. 4.

The approach given here gives a lot for virtual objects (upgrades from free
knots to virtual knots can be done straightforwardly).

We expect to have invariants for classical knots. This is to be done in a
sequel of the present paper.

The key idea is to concentrate on knots inside the cylinder; this will give
rise to parities, indices and other non-trivial structures. As a result, we
expect maps (not necessarily homomorphic) from classical knots to free groups.

## References

  * [1] D.A.Fedoseev, V.O. Manturov, A sliceness criterion for odd free knots, Sb. Math., 210:10 (2019), 1493–1509.
  * [2] A.Gibson, Homotopy invariants of Gauss words, Mathematische Annalen, ISSN 0025-5831, Vol. 349, No. 4, 2011.
  * [3] D.P.Ilyutko, V.O.Manturov, I.M.Nikonov, Parity and Patterns in Low-Dimensional Topology, Cambridge Science Publishers, 2015.
  * [4] L.H.Kauffman, A self-linking invariant of virtual knots, Fund. Math.,184, 2004, P. 135-158.
  * [5] V.O.Manturov, Parity in Knot Theory, Sb. Math., 201:5 (2010), 693–733
  * [6] V.O.Manturov, Parity and cobordism of free knots,Sb. Math., 203:2 (2012), 196–223.
  * [7] V.O.Manturov, D.A.Fedoseev, S.Kim, I.M.Nikonov, Invariants and Pictures, World Scientific, 2020.
  * [8] V.O.Manturov, Additional gradings in the Khovanov homology for thickened surfaces, Doklady Mathematics, 2008\. Vol. 77. No. 3. P. 368-370.
  * [9] V.G.Turaev, Topology of words , Proc. Lond. Math. Soc. (3), 95:2, (2007), 360–412.
  * [10] O.V.Manturov, V.O.Manturov, Free knots and Groups, Journal of Knot Theory and Its Ramifications. 2010. Vol. 19. No. 2. P. 181-186.
  * [11] V.O.Manturov, I.M.Nikonov, On Braid Groups and $G_{n}^{k}$ groups, J. Knot Theory and Its Ramifications, 2015\.
  * [12] M.V.Zenkina, The parity hierarchy and new invariants of knots in thickened surfaces, Journal of Knot Theory and Its Ramifications, 2013 , Vol. 22, No. 4., 1340001.