11institutetext: University of Hamburg, Department of Informatics
Hamburg, Germany
11email<EMAIL_ADDRESS>
#  Analysing Cycloids using Linear Algebra

Rüdiger Valk

###### Abstract

Cycloids are particular Petri nets for modelling processes of actions or
events. They belong to the fundaments of Petri’s general systems theory and
have very different interpretations, ranging from Einstein’s relativity theory
and elementary information processing gates to the modelling of interacting
sequential processes. This article contains previously unpublished proofs of
cycloid properties using linear algebra.

###### Keywords:

S

tructure of Petri Nets, Cycloids, Linear Algebra, Cycles in the grafic
Structure

##  1 Introduction

Cycloids have been introduced by C.A. Petri in [3] in the section on physical
spaces, using as examples firemen carrying the buckets with water to
extinguish a fire, the shift from Galilei to Lorentz transformation and the
representation of elementary logical gates like Quine-transfers. Based on
formal descriptions of cycloids in [2] and [1] a more elaborate formalization
is given in [5].

Figure 1: Three sequential processes synchronized by single-bit channels,

Cycloids are structures that are defined with methods of discrete mathematics,
which makes proofs sometimes not very descriptive. It was therefore a great
step forward that a method was introduced in [6] that allows proofs to be
carried out with the help of linear algebra. This method is called _Cycloid
Algebra_. Three theorems are proved in this article using Cycloid Algebra,
namely a) on the equivalence of transitions with respect to the cycloid
folding, b) on isomorphisms of cycloids and c) on the minimal length of cycles
with respect to the grafic structure of a cyloid.

To give an application for the theory, as presented in this article, consider
a distributed system of a finite number of circular and sequential processes.
The processes are synchronized by uni-directional one-bit channels in such a
way that they behave like a circular traffic queue when folded together. To
give an example, Figure 1a) shows three such sequential circular processes,
each of length $7$. In the initial state the control is in position $1$, $3$
and $5$, respectively. The synchronization, realized by the connecting
channels, should be such as the three processes would be folded together. This
means, that the controls of $proc_{0}$ and $proc_{1}$ can make only one step
until the next process $proc_{2}$ makes a step itself, while the control of
$proc_{2}$ can make two steps until $proc_{0}$ makes a step. Following [6]
this behaviour is realized by the cycloid of Figure 1b) modelling the three
processes by the transition sequences $proc_{0}=$ [t1 t2 $\cdots$ t7], as well
as $proc_{1}=$ [t8 t9 $\cdots$ t14] and $proc_{2}=$ [ t15 t16 $\cdots$ t21].
The channels are represented by the safe places connecting these processes. By
this example the power of the presented theory is shown, since the rather
complex net is unambiguously determined by the parameters
$\mathcal{C}(\alpha,\beta,\gamma,\delta)=\mathcal{C}(4,3,3,3)$. A next
question could be, how to change the cycloid when the parameters of $\beta=3$
processes of process length $p=7$ should be changed to a different value, say
the double $p=14$. As will be explained in a forthcoming article, the theory
returns even three cycloids, namely $\mathcal{C}_{1}(4,3,10,3)$,
$\mathcal{C}_{2}(4,3,6,6)$ and $\mathcal{C}_{3}(4,3,2,9)$. However, as follows
from Theorem 3.2 these three solutions are isomorphic. The flexibilty of the
model is also shown by the following additional example. By doubling in
$\mathcal{C}(4,3,3,3)$ the value of $\beta$ we obtain the cycloid
$\mathcal{C}(4,6,3,3)$, which models a distributed system of three circular
sequential processes, each of length $p=10$. However, different to the
examples above, each process contains two  control tokens. Translated to the
distributed model, in the initial state each of the three sequential processes
contains two items, particularly $proc_{0}$ in positions $0$ and $5$ in the
circular queue of length $10$, $proc_{1}$ in positions $1$ and $6$ and
$proc_{2}$ in positions $3$ and $8$. The present article is part of a general
project to investigate all such features of cycloids to make them available
for Software Engineering.

We recall some standard notations for set theoretical relations. If
$R\subseteq A\\!\times\\!B$ is a relation and $U\subseteq A$ then
$R[U]:=\\{b\,|\,\exists u\in U:(u,b)\in R\\}$ is the _image_ of $U$ and $R[a]$
stands for $R[\\{a\\}]$. $R^{-1}$ is the _inverse relation_ and $R^{+}$ is the
_transitive closure_ of $R$ if $A=B$. Also, if $R\subseteq A\\!\times\\!A$ is
an equivalence relation then $[\\![a]\\!]_{R}$ is the _equivalence class_ of
the quotient $A/R$ containing $a$. Furthermore
$\mathord{\mathbb{missing}}{N}$, $\mathord{\mathbb{missing}}{N}_{+}$,
$\mathord{\mathbb{missing}}{Z}$ and $\mathord{\mathbb{missing}}{R}$ denote the
sets of integers, positive integer, integer and real numbers, respectively.
For integers: $a|b$ if $a$ is a factor of $b$. The $modulo$-function is used
in the form $a\,mod\,b=a-b\cdot\lfloor\frac{a}{b}\rfloor$, which also holds
for negative integers $a\in\mathord{\mathbb{missing}}{Z}$. In particular,
$-a\,mod\,b=b-a$ for $0<a\leq b$.

##  2 Petri Space and Cycloids

We define (Petri) nets as they will be used in this article.

######  Definition 1 ([5])

As usual, a net $\mathcal{N}=(S,T,F)$ is defined by non-empty, disjoint sets
$S$ of places and $T$ of transitions, connected by a flow relation
$F\subseteq(S\mathbin{\times}T)\cup(T\mathbin{\times}S)$ and $X:=S\cup T$. A
transition $t\in T$ is _active_ or _enabled_ in a marking $M\subseteq S$ if
$\;{}^{\mathord{{}^{\bullet}}}t\subseteq
M\,\land\,t^{\mathord{{}^{\bullet}}}\cap M=\emptyset$111With the condition
$t^{\mathord{{}^{\bullet}}}\cap M=\emptyset$ we follow Petri’s definition, but
with no impacts in this article.. In this case we obtain
$M\stackrel{{\scriptstyle t}}{{\rightarrow}}M^{\prime}$ if
$M^{\prime}=M\backslash^{\mathord{{}^{\bullet}}}t\cup
t^{\mathord{{}^{\bullet}}}$, where
${}^{\mathord{{}^{\bullet}}}x:=F^{-1}[x],\;x^{\mathord{{}^{\bullet}}}:=F[x]$
denotes the input and output elements of an element $x\in X$, respectively.
$\stackrel{{\scriptstyle*}}{{\rightarrow}}$ is the reflexive and transitive
closure of $\rightarrow$.

Figure 2:  a) Petri space, b) circular traffic queue and c) time orthoid.

Petri started with an event-oriented version of the Minkowski space which is
called Petri space now. Contrary to the Minkowski space, the Petri space is
independent of an embedding into
$\mathord{\mathbb{missing}}{Z}\times\mathord{\mathbb{missing}}{Z}$. It is
therefore suitable for the modelling in transformed coordinates as in non-
Euclidian space models. However, the reader will wonder that we will apply
linear algebra, for instance using equations of lines. This is done only to
determine the relative position of points. It can be understood by first
topologically transforming and embedding the space into
$\mathord{\mathbb{missing}}{R}\times\mathord{\mathbb{missing}}{R}$,
calculating the position and then transforming back into the Petri space.
Distances, however, are not computed with respect to the Euclidean metric, but
by counting steps in the grid of the Petri space, like Manhattan distance or
taxicab geometry.

For instance, the transitions of the Petri space might model the moving of
items in time and space in an unlimited way. To be concrete, a coordination
system is introduced with arbitrary origin (see Figure 2 a). The occurrence of
transition $t_{1,0}$ in this figure, for instance, can be interpreted as a
step of a traffic item (the token in the left input-place) in both space and
time direction. It is enabled by a gap or co-item (the token in the right
input-place). Afterwads the traffic item can make a new step by the occurrence
of transition $t_{2,0}$. By the following definition the places obtain their
names by their input transitions (see Figure 3 b).

Figure 3: a) Fundamental parallelogram of $\mathcal{C}(4,2,2,3)$ and b) Petri
space.

######  Definition 2 ([5])

A $Petri\;space$ is defined by the net $\mathcal{PS}_{1}:=(S_{1},T_{1},F_{1})$
where $S_{1}=S^{\rightarrow}_{1}\cup
S^{\leftarrow}_{1},\;S^{\rightarrow}_{1}=$
$\mathinner{\\{s^{\rightarrow}_{\xi,\eta}\,|\,\xi,\eta\in\mathord{\mathbb{missing}}{Z}\\}},$
$\;S^{\leftarrow}_{1}=\mathinner{\\{s^{\leftarrow}_{\xi,\eta}\,|\,\xi,\eta\in\mathord{\mathbb{missing}}{Z}\\}},S^{\rightarrow}_{1}\cap
S^{\leftarrow}_{1}=\emptyset$, $T_{1}=$
$\mathinner{\\{t_{\xi,\eta}\,|\,\xi,\eta\in\mathord{\mathbb{missing}}{Z}\\}},F_{1}=$
$\mathinner{\\{(t_{\xi,\eta},s^{\rightarrow}_{\xi,\eta})\,|\,\xi,\eta\in\mathord{\mathbb{missing}}{Z}\\}}\cup\mathinner{\\{(s^{\rightarrow}_{\xi,\eta},t_{\xi+1,\eta})\,|\,\xi,\eta\in\mathord{\mathbb{missing}}{Z}\\}}\cup$
$\mathinner{\\{(t_{\xi,\eta},s^{\leftarrow}_{\xi,\eta})\,|\,\xi,\eta\in\mathord{\mathbb{missing}}{Z}\\}}\cup\mathinner{\\{(s^{\leftarrow}_{\xi,\eta},t_{\xi,\eta+1})\,|\,\xi,\eta\in\mathord{\mathbb{missing}}{Z}\\}}$
(cutout in Figure 3 b). $S^{\rightarrow}_{1}$ is the set of _forward places_
and $S^{\leftarrow}_{1}$ the set of _backward places_.
${}^{\rightarrow\kern-4.54996pt^{\bullet}}\,t_{\xi,\eta}:=s^{\rightarrow}_{\xi-1,\eta}$
is the forward input place of $t_{\xi,\eta}$ and in the same way
${}^{\leftarrow\kern-3.5pt^{\bullet}}t_{\xi,\eta}:=s^{\leftarrow}_{\xi,\eta-1}$,
$t_{\xi,\eta}^{\rightarrow\kern-4.54996pt^{\bullet}}:=s^{\rightarrow}_{\xi,\eta}$
and
$t_{\xi,\eta}^{\leftarrow\kern-3.5pt^{\bullet}}:=s^{\leftarrow}_{\xi,\eta}$
(Figure 3 b).

In two steps, by a twofold folding with respect to time and space, Petri
defined the cyclic structure of a cycloid. One of these steps is a folding $f$
with respect to space with $f(i,k)=f(i+\alpha,k-\beta)$, fusing all points
$(i,k)$ of the Petri space with $(i+\alpha,k-\beta)$ where
$i,k\in\mathord{\mathbb{missing}}{Z},\alpha,\beta\in\mathord{\mathbb{missing}}{N}_{+}$
([3], page 37). While Petri gave a general motivation, oriented in physical
spaces, we interpret the choice of $\alpha$ and $\beta$ by our model of
traffic queues.

We assume that our model of a circular traffic queues has six slots containing
two items $a_{0}$ and $a_{1}$ as shown in Figure 2 b). These are modelled in
Figure 2 a) by the tokens in the forward input places of $t_{1,0}$ and
$t_{3,-1}$. The four co-items (the empty slots in Figure 2 b) ) are
represented by the tokens in the backward input places of $t_{1,0},t_{2,0}$
and $t_{3,-1},t_{4,-1}$. By the occurrence of $t_{1,0}$ and $t_{2,0}$ the
first item can make two steps, as well as the second item by the transitions
$t_{3,-1}$ and $t_{4,-1}$, respectively. Then $a_{1}$ has reached the end of
the queue and has to wait until the first item is leaving its position. Hence,
we have to introduce a precedence restriction between the transitions
$t_{1,0}$ and $t_{5,-1}$. This is done by fusing the transitions $t_{5,-1}$
and the left-hand follower $t_{1,1}$ of $t_{1,0}$ , which are marked by a
cross in Figure 2 a). This is implemented by the dotted arc in the same
figure. To determinate $\alpha$ and $\beta$ we set $(5,-1)=(1+\alpha,1-\beta)$
which gives $5=1+\alpha$ or $\alpha=4$ and $-1=1-\beta$ or $\beta=2$. By the
equivalence relation $t_{\xi,\eta}\equiv t_{\xi+4,\eta-2}$ we obtain the
structure in Figure 2 c). The resulting still infinite net is called a _time
orthoid_ ([3], page 37), as it extends infinitely in temporal future and past.
The second step is a folding with $f(i,k)=f(i+\gamma,k+\delta)$ with
$\gamma,\delta\in\mathord{\mathbb{missing}}{N}_{+}$ reducing the system to a
cyclic structure also in time direction. As shown in [6] an equivalent cycloid
for the traffic queue of Figure 2 b) has the parameters
$(\alpha,\beta,\gamma,\delta)=(4,2,2,2)$. To keep the example more general, in
Figure 3 a) the values $(\alpha,\beta,\gamma,\delta)=(4,2,2,3)$ are chosen. In
this representation of a cycloid, called _fundamental parallelogram_ , the
squares of the transitions as well as the circles of the places are omitted.
All transitions with coordinates within the parallelogram belong to the
cycloid including those on the lines between $O,Q$ and $O,P$, but excluding
those of the points $Q,R,P$ and those on the dotted edges between them. All
parallelograms of the same shape, as indicated by dotted lines outside the
fundamental parallelogram are fused with it.

######  Definition 3 ([5])

A _cycloid_ is a net $\mathcal{C}(\alpha,\beta,\gamma,\delta)=(S,T,F)$,
defined by parameters
$\alpha,\beta,\gamma,\delta\in\mathord{\mathbb{missing}}{N}_{+}$, by a
quotient [4] of the Petri space $\mathcal{PS}_{1}:=(S_{1},T_{1},F_{1})$ with
respect to the equivalence relation $\mathord{\equiv}\subseteq
X_{1}\mathbin{\times}X_{1}$ with $X_{1}=S_{1}\cup T_{1}$,
$\mathord{\equiv}[S^{\rightarrow}_{1}]\subseteq
S^{\rightarrow}_{1},\mathord{\equiv}[S^{\leftarrow}_{1}]\subseteq
S^{\leftarrow}_{1},\mathord{\equiv}[T_{1}]\subseteq T_{1},$
$x_{\xi,\eta}\equiv x_{\xi+m\alpha+n\gamma,\,\eta-m\beta+n\delta}$ for all
$\xi,\eta,m,n\in\mathord{\mathbb{missing}}{Z}$ , $X=X_{1}/_{\equiv}$,
$[\\![x]\\!]_{\equiv}\mathbin{F}[\\![y]\\!]_{\equiv}\>\Leftrightarrow\exists\,{x^{\prime}\in[\\![x]\\!]_{\equiv}}\,\exists\,y^{\prime}\in[\\![y]\\!]_{\equiv}:\,x^{\prime}F_{1}y^{\prime}$
for all $x,y\in X_{1}$. The matrix $\mathbf{A}=\begin{pmatrix}\alpha&\gamma\\\
-\beta&\delta\end{pmatrix}$ is called the matrix of the cycloid. Petri denoted
the number $|T|$ of transitions as the area $A$ of the cycloid and proved in
[3] its value to $|T|=A=\alpha\delta+\beta\gamma$ which equals the determinant
$A=det(\mathbf{A})$. The embedding of a cycloid in the Petri space is called
_fundamental parallelogram_ (see Figure 3 a).

##  3 Equivalence and Isomorphisms

For proving the equivalence of two points in the Petri space the following
procedure222The algorithm is implemented under http://cycloids.de. is useful.

######  Theorem 3.1 ([6])

Two points $\vec{x}_{1},\vec{x}_{2}\in X_{1}$ are equivalent
$\vec{x}_{1}\equiv\vec{x}_{2}$ if and only if for the difference
$\vec{v}:=\vec{x_{2}}-\vec{x_{1}}$ the parameter vector
$\pi(\vec{v})=\frac{1}{A}\cdot\mathbf{B}\cdot\vec{v}$ has integer values,
where $A$ is the area and $\mathbf{B}=\begin{pmatrix}\delta&-\gamma\\\
\beta&\alpha\end{pmatrix}$.
In analogy to Definition 3 we obtain
$\vec{x}_{1}\equiv\vec{x}_{2}\Leftrightarrow$
$\exists\;m,n\in\mathord{\mathbb{missing}}{Z}:\vec{x_{2}}-\vec{x_{1}}=\mathbf{A}\begin{pmatrix}m\\\
n\end{pmatrix}$.

###### Proof

For
$\vec{x}_{1}:=(\xi_{1},\eta_{1}),\vec{x}_{2}:=(\xi_{2},\eta_{2}),\vec{v}:=\vec{x}_{2}-\vec{x}_{1}$
from Definition 3 we obtain in vector form:
$\vec{x}_{1}\equiv\vec{x}_{2}\Leftrightarrow\exists\,m,n\in\mathord{\mathbb{missing}}{Z}:\begin{pmatrix}\xi_{2}\\\
\eta_{2}\end{pmatrix}=\begin{pmatrix}\xi_{1}+m\alpha+n\gamma\\\
\eta_{1}-m\beta+n\delta\end{pmatrix}$ $\Leftrightarrow$
$\exists\,m,n\in\mathord{\mathbb{missing}}{Z}:$
$\vec{v}=\begin{pmatrix}\xi_{2}-\xi_{1}\\\
\eta_{2}-\eta_{1}\end{pmatrix}=\begin{pmatrix}m\alpha+n\gamma\\\
-m\beta+n\delta\end{pmatrix}=\begin{pmatrix}\alpha&\gamma\\\
-\beta&\delta\end{pmatrix}\begin{pmatrix}m\\\
n\end{pmatrix}=\mathbf{A}\begin{pmatrix}m\\\ n\end{pmatrix}$ $\Leftrightarrow$
$\begin{pmatrix}m\\\ n\end{pmatrix}=\mathbf{A}^{-1}\vec{v}$
$\in\mathord{\mathbb{missing}}{Z}\times\mathord{\mathbb{missing}}{Z}$ . It is
well-known that $\mathbf{A}^{-1}=\frac{1}{det(\mathbf{A})}\mathbf{B}$ if
$det(\mathbf{A})>0$ (see any book on linear algebra). The condition
$det(\mathbf{A})=A=\alpha\delta+\beta\gamma>0$ is satisfied by the definition
of a cycloid. ∎

Since constructions of cycloids may result in different but isomorphic forms
the following theorem is important. A method using linear algebra together
with the matrices $\mathbf{A}$ in Definition 3 or $\mathbf{B}$ in Definition
3.1 is called a _Cycloid Algebra_ method. We give here a proof using this
approach, which was not yet known when the article [5] had been published.

######  Theorem 3.2 ([5])

The following cycloids are net isomorphic (Definition 1) to
$\mathcal{C}(\alpha,\beta,\gamma,\delta)$:
a) $\mathcal{C}(\alpha,\beta,\gamma-\alpha,\delta+\beta)$ if $\gamma>\alpha$,
b) $\mathcal{C}(\alpha,\beta,\gamma+\alpha,\delta-\beta)$ if $\delta>\beta$.
c) $\mathcal{C}(\beta,\alpha,\delta,\gamma)$. (The $symmetric\;cycloid$ of
$\mathcal{C}(\alpha,\beta,\gamma,\delta)$.)

###### Proof

In all the three cases we give a bijection on the Petri space, which is a
congruence with respect to equivalence. Let be
$\mathcal{C}=\mathcal{C}(\alpha,\beta,\gamma,\delta)$ with matrix $\mathbf{A}$
(Definition 3) and the vector
$\overrightarrow{mn}:=(m,n)\in\mathord{\mathbb{missing}}{Z}^{2}$.
a) and b): The bijection is the identity map and we prove that the equivalence
relation of
$\mathcal{C}_{1}=\mathcal{C}_{1}(\alpha,\beta,\gamma\pm\alpha,\delta\mp\beta)$
with matrix $\mathbf{A}_{1}=\begin{pmatrix}\alpha&\;\gamma\pm\alpha\\\
-\beta&\;\delta\mp\beta\end{pmatrix}$ remains unchanged:
$\mathbf{A}_{1}\cdot\overrightarrow{mn}=\mathbf{A}\cdot\overrightarrow{mn}+\begin{pmatrix}0&\;\;\pm\alpha\\\
0&\;\;\mp\beta\end{pmatrix}\cdot\overrightarrow{mn}=\mathbf{A}\cdot\overrightarrow{mn}+\begin{pmatrix}\pm
n\cdot\alpha\\\ \mp
n\cdot\beta\end{pmatrix}=\mathbf{A}\cdot\overrightarrow{mn}+\mathbf{A}\cdot\begin{pmatrix}\pm
n\\\ 0\end{pmatrix}=$ $\mathbf{A}\cdot\begin{pmatrix}m\pm n\\\
n\end{pmatrix}$. Hence, the by Theorem 3.1 b) the equivalence relations of
$\mathcal{C}$ and $\mathcal{C}_{1}$ are the same, since $m$ and $n$ are
integers iff $m\pm n$ and $n$ are integers.
c): We denote $\mathcal{C}_{2}=\mathcal{C}_{2}(\beta,\alpha,\delta,\gamma)$
with matrix $\mathbf{A}_{2}=\begin{pmatrix}\beta&\;\delta\\\
-\alpha&\gamma\end{pmatrix}$. Using the sets $X$ and $X_{2}$ of $\mathcal{C}$
and $\mathcal{C}_{2}$, respectively (Definition 1), the isomorphism is defined
by $\varphi(x_{\xi,\eta}):=x_{\eta+\beta,\xi-\alpha}$. Obviously, $\varphi$ is
injective and surjective.
In the following we use the indices as coordinates of thge points in the Petri
space and write
$\varphi\begin{pmatrix}\xi\\\ \eta\end{pmatrix}=\begin{pmatrix}\eta+\beta\\\
\xi-\alpha\end{pmatrix}$. It remains to prove that $\varphi$ is a congruence,
i.e.

$\begin{pmatrix}\xi\\\ \eta\end{pmatrix}\equiv\begin{pmatrix}\xi_{1}\\\
\eta_{1}\end{pmatrix}\;\Rightarrow\;\varphi\begin{pmatrix}\xi\\\
\eta\end{pmatrix}\equiv\varphi\begin{pmatrix}\xi_{1}\\\ \eta_{1}\end{pmatrix}$

For the precondition of this implication we have by Theorem 3.1 b)
$\begin{pmatrix}\xi\\\ \eta\end{pmatrix}\equiv\begin{pmatrix}\xi_{1}\\\
\eta_{1}\end{pmatrix}\;\Leftrightarrow\;\begin{pmatrix}\xi-\xi_{1}\\\
\eta-\eta_{1}\end{pmatrix}=\mathbf{A}\begin{pmatrix}m\\\
n\end{pmatrix}=\begin{pmatrix}\alpha\cdot m+\gamma\cdot n\\\ -\beta\cdot
m+\delta\cdot n\end{pmatrix}$ for some $m,n\in\mathord{\mathbb{missing}}{Z}$.
We use this term to prove the conclusio: $\varphi\begin{pmatrix}\xi\\\
\eta\end{pmatrix}\equiv\varphi\begin{pmatrix}\xi_{1}\\\
\eta_{1}\end{pmatrix}\;\Leftrightarrow\;\begin{pmatrix}\eta+\beta\\\
\xi-\alpha\end{pmatrix}-\begin{pmatrix}\eta_{1}+\beta\\\
\xi_{1}-\alpha\end{pmatrix}=\begin{pmatrix}\eta-\eta_{1}\\\
\xi-\xi_{1}\end{pmatrix}=$ $\mathbf{A}_{2}\begin{pmatrix}m^{\prime}\\\
n^{\prime}\end{pmatrix}=\begin{pmatrix}\beta\cdot m^{\prime}+\delta\cdot
n^{\prime}\\\ -\alpha\cdot m^{\prime}+\gamma\cdot n^{\prime}\end{pmatrix}$ for
some $m^{\prime},n^{\prime}\in\mathord{\mathbb{missing}}{Z}$. Using the
precondition the conclusio holds by setting $m^{\prime}:=-m$ and
$n^{\prime}:=n$.

In plane geometry, a shear mapping is a linear map that displaces each point
in a fixed direction, by an amount proportional to its signed distance from
the line that is parallel to that direction and goes through the
origin333https://en.wikipedia.org/wiki/Shear_mapping. For a cycloid
$\mathcal{C}(\alpha,\beta,\gamma,\delta)$ the corners of its fundamental
parallelogram have the coordinates $O=\begin{pmatrix}0\\\
0\end{pmatrix},P=\begin{pmatrix}\alpha\\\
-\beta\end{pmatrix},R=\begin{pmatrix}\alpha+\gamma\\\
\delta-\beta\end{pmatrix}$ and $Q=\begin{pmatrix}\gamma\\\
\delta\end{pmatrix}$. Comparing them with the corners
$O^{\prime},P^{\prime},R^{\prime},Q^{\prime}$ of the transformed cycloid
$\mathcal{C}(\alpha,\beta,\gamma+\alpha,\delta-\beta)$ of Theorem 3.2 b) we
observe $O^{\prime}=O,P^{\prime}=P,Q^{\prime}=\begin{pmatrix}\gamma+\alpha\\\
\delta-\beta\end{pmatrix}=R$ and the lines $\overline{Q,R}$ and
$\overline{Q^{\prime},R^{\prime}}$ are the same. Therefore the second is a
shearing of the first one. This is shown in Figure444The figure has been
designed using the tool http://cycloids.adventas.de. 4 for the cycloids
$\mathcal{C}(2,3,2,8),\mathcal{C}(2,3,4,5)$ and $\mathcal{C}(2,3,6,2)$.

Figure 4: A shearing from $\mathcal{C}(2,3,2,8)$ to $\mathcal{C}(2,3,6,2)$.

When applying the equivalences of Theorem 3.2 the parameters $\gamma$ and
$\delta$ are changed which leads to the following definition of
$\gamma\delta$-reduction equivalence.

######  Lemma 1 ([5])

For any cycloid $\mathcal{C}(\alpha,\beta,\gamma,\delta)$ there is a minimal
cycle containing the origin $O$ in its fundamental parallelogram
representation.

##  4 The Minimal Length of a Cycle

For the next Theorem from [5], we give a proof which follows the same concept,
but is general and more formal. The version from [5] does not cover all cases,
but the special case for $\gamma=\delta$ is still valid (see case c) of the
following theorem). This subcase was important for the applications to regular
cycloids in [6]. Part a) of the theorem applies the Cycloid Algebra (Theorem
3.1). The minimization over two parameters $i$ and $j$ is reduced to one
parameter by showing a dependance of to $i$ from $j$ in part b). By
restricting to particular cases in the remaining cases no minimum operator is
needed.

###### Theorem 4.1

The minimal length of a cycle of a cycloid
$\mathcal{C}=\mathcal{C}(\alpha,\beta,\gamma,\delta)$ is
$cyc(\alpha,\beta,\gamma,\delta)=cyc$, where

  * a)

$cyc=min\\{u+v\;|\begin{pmatrix}u\\\
v\end{pmatrix}=\mathbf{A}\cdot\begin{pmatrix}i\\\
j\end{pmatrix},\;i\in\mathord{\mathbb{missing}}{Z},\;j\in\mathord{\mathbb{missing}}{N},\;u\geq
0,\;v\geq 0\\}$

  * b)

$cyc=min\\{j\cdot(\gamma+\delta)+i\cdot(\alpha-\beta)\;|\;j\in\mathord{\mathbb{missing}}{N},\>i=\left\\{\begin{array}[]{lll}\lfloor\frac{j\cdot\delta}{\beta}\rfloor&\textrm{if}&\alpha\leq\beta\\\
-\lfloor\frac{j\cdot\gamma}{\alpha}\rfloor&\textrm{if}&\alpha>\beta\end{array}\right\\}\\}$
The value of $j$ is bounded: $j\leq\frac{A}{\gamma}$ if $\alpha\leq\beta$ and
$j\leq\frac{A}{\delta}$ otherwise.

  * c)

$cyc=\gamma+\delta+\;\left\\{\begin{array}[]{lll}\lfloor\frac{\delta}{\beta}\rfloor(\alpha-\beta)&\textrm{if}&\alpha\leq\beta\;\;\textrm{and}\;\;\gamma\geq\delta\\\
-\lfloor\frac{\gamma}{\alpha}\rfloor(\alpha-\beta)&\textrm{if}&\alpha>\beta\;\;\textrm{and}\;\;\gamma\leq\delta\end{array}\right\\}$

  * d)

$cyc=\gamma+\frac{\delta}{\beta}\cdot\alpha=\frac{A}{\beta}\;\;\textrm{if}\;\;\alpha\leq\beta\;\;\textrm{and}\;\;\mathcal{C}\;\;\textrm{is
regular}\;\;(\textrm{i.e.}\;\;\beta|\delta)$

  * e)

$cyc=\delta+\frac{\gamma}{\alpha}\cdot\beta=\frac{A}{\alpha}\;\;\textrm{if}\;\;\alpha>\beta\;\;\textrm{and}\;\;\mathcal{C}\;\;\textrm{is
co-regular}\;\;(\textrm{i.e.}\;\;\alpha|\gamma)$

###### Proof

a) With respect to paths and cycles in the fundamental parallelogram and by
Lemma 1 it is sufficient to consider paths starting in the origin $O$. Such a
cycle of the cycloid corresponds to a path with positive length from $O$ to an
equivalent point $\vec{x}$ in the Petri space. From Theorem 3.1 we obtain with
$\vec{x_{2}}=\vec{x}$ and $\vec{x_{1}}=(0,0)$ the necessary and suffient
condition
$\exists\;i,j\in\mathord{\mathbb{missing}}{Z}:\vec{x}=\mathbf{A}\cdot\begin{pmatrix}i\\\
j\end{pmatrix}$ with $\lnot(i=0\land j=0)$. If $\vec{x}=\begin{pmatrix}u\\\
v\end{pmatrix}$ then $u+v>0$ is the length of the path from the origin $O$ to
the endpoint of $\vec{x}$. $u+v$ should be a minimum to obtain $cyc$. However,
some choices of $\vec{x}$ can be excluded. There is no path from $O$ to
$(u,v)$ if $u<0$ or $v<0$. Therefore $j\leq 0$ can be excluded in
$\begin{pmatrix}u\\\ v\end{pmatrix}=\mathbf{A}\cdot\begin{pmatrix}i\\\
j\end{pmatrix}=\begin{pmatrix}\alpha&\gamma\\\
-\beta&\delta\end{pmatrix}\cdot\begin{pmatrix}i\\\
j\end{pmatrix}=\begin{pmatrix}i\cdot\alpha+j\cdot\gamma\\\
-i\cdot\beta+j\cdot\delta\end{pmatrix}$. This is true by the following proof
by contradiction: assume $j\leq 0$.
Case 1: If $i\geq 0$ then $v=-i\cdot\beta+j\cdot\delta<0$ in contradiction to
the condition $v\geq 0$.
Case 2: If $i<0$ then $u=i\cdot\alpha+j\cdot\gamma<0$ in contradiction to the
condition $u\geq 0$.

b) We first consider the case $\alpha\leq\beta$ and prove
$\lfloor\frac{j\cdot\delta}{\beta}\rfloor$ if $\gamma\geq\delta$. Denote the
cutpoint of the line $\overline{QR}$ with the $\xi$-axis by $A_{1}$ (the line
cannot be in parallel to the $\xi$-axis). Next, in a similar way, for $j\geq
1$ the endpoint of the vector $j\cdot(\gamma,\delta)$ is denoted by $Q_{j}$,
including $Q_{1}=Q$. (See Figure 5 for the cases $j\in\\{1,2,3\\}$.)
Furthermore we name the cutpoint of the line through $Q_{j}$ and the endpoint
of $j\cdot(\gamma,\delta)+(\alpha,-\beta)$ with the $\xi$-axis by $A_{j}$. On
this line the points $\vec{x}=j\cdot\begin{pmatrix}\gamma\\\
\delta\end{pmatrix}+i\cdot\begin{pmatrix}\alpha\\\
-\beta\end{pmatrix}=\begin{pmatrix}u\\\ v\end{pmatrix}$ are situated which
define the value of $cyc=u+v$. By the condition $v\geq 0$ we obtain
$j\cdot\delta-i\cdot\beta\geq 0$ which is

$i\leq\frac{j\cdot\delta}{\beta}$ (1)

Next we derive an expression for $i$ in dependance of $j$ by proving that
increasing the value of $i$ does not increase the distance to the origin
(while the condition $\eta\geq 0$ is not violated when going $\beta$ steps in
direction $-\eta$).

Figure 5: Referenced in the proof of Theorem 4.1.

More precisely, for any $\xi\geq 0,\eta\geq 0$ we have to prove
$d(O,\begin{pmatrix}\xi\\\ \eta\end{pmatrix})\geq d(O,\begin{pmatrix}\xi\\\
\eta\end{pmatrix}+\begin{pmatrix}\alpha\\\ -\beta\end{pmatrix})$ under the
condition $\eta-\beta\geq 0$. This follows from $\alpha\leq\beta$ by
$0\geq\alpha-\beta\;\Rightarrow\;\xi+\eta\geq\xi+\alpha+\eta-\beta\;\Rightarrow\;|\xi+\eta|\geq|\xi+\alpha|+|\eta-\beta|\;\Rightarrow\;d(O,\begin{pmatrix}\xi\\\
\eta\end{pmatrix})\geq d(O,\begin{pmatrix}\xi+\alpha\\\
\eta-\beta\end{pmatrix})$. By choosing the maximal value of $i$ under the
inequality (1) we obtain $i=\lfloor\frac{j\cdot\delta}{\beta}\rfloor$.
Therefore the candidates to compute $cyc$ are the endpoints of the vectors

$\vec{x}{{}_{j}}=j\cdot\begin{pmatrix}\gamma\\\
\delta\end{pmatrix}+\lfloor\frac{j\cdot\delta}{\beta}\rfloor\cdot\begin{pmatrix}\alpha\\\
-\beta\end{pmatrix}\;\;\;\;\;\;(j\in\mathord{\mathbb{missing}}{N}).$ (2)

The distance from the origin $O$ to $\vec{x}{{}_{j}}$ is
$d(O,\vec{x}{{}_{j}})=$
$j\cdot(\gamma+\delta)+\lfloor\frac{j\cdot\delta}{\beta}\rfloor\cdot(\alpha-\beta)$.
For the alternative case $\alpha>\beta$ we look at the symmetric cycloid
$\mathcal{C}(\beta,\alpha,\delta,\gamma)$ (by interchanging $\alpha$ and
$\beta$, as well as $\gamma$ and $\delta$), which is net isomorphic (Theorem
3.2 c) and therefore has a minimal cycle of the same length. Equation (2) is
replaced by Equation (3 ):

$\vec{x}{{}_{j}}=j\cdot\begin{pmatrix}\delta\\\
\gamma\end{pmatrix}+\lfloor\frac{j\cdot\gamma}{\alpha}\rfloor\cdot\begin{pmatrix}\beta\\\
-\alpha\end{pmatrix}\;\;\;\;\;\;(j\in\mathord{\mathbb{missing}}{N}).$ (3)

and we obtain
$d(O,\vec{x}{{}_{j}})=j\cdot(\gamma+\delta)+\lfloor\frac{j\cdot\gamma}{\alpha}\rfloor\cdot(\beta-\alpha)$
in case of $\alpha>\beta$.

To derive the bound we start with the observation that the length of a cycle
is bounded by the number $A$ of transitions. In the case $\alpha\leq\beta$ it
follows with respect to the minimal value of $j$:

$cyc=j\cdot(\gamma+\delta)+\lfloor\frac{j\cdot\delta}{\beta}\rfloor\cdot(\alpha-\beta)\leq
A$ which transforms to
$j\cdot\delta-\lfloor\frac{j\cdot\delta}{\beta}\rfloor\cdot\beta+j\cdot\gamma+\lfloor\frac{j\cdot\delta}{\beta}\rfloor\cdot\alpha=(j\cdot\delta)\;mod\;\beta+j\cdot\gamma+\lfloor\frac{j\cdot\delta}{\beta}\rfloor\cdot\alpha\leq
A$. Since
$(j\cdot\delta)\;mod\;\beta+\lfloor\frac{j\cdot\delta}{\beta}\rfloor\cdot\alpha\
\geq 0$ we obtain $j\cdot\gamma\leq A$ and $j\leq\frac{A}{\gamma}$. The result
for the case $\alpha\geq\beta$ is proved in a similar way.

c) We prove $j=1$ in case b) of the theorem under the the additional condition
$\gamma\geq\delta$. From $\vec{x}{{}_{j}}\geq(0,0)$ we deduce from Equation
(2):

$j\cdot\delta-\lfloor\frac{j\cdot\delta}{\beta}\rfloor\cdot\beta\geq 0$ (4)

The endpoints of the vectors $\vec{x}{{}_{j}}$ are denoted by $C_{j}$ in
Figure 5. The path from the origin $O$ to $\vec{x}{{}_{j}}$ has the length
$cyc_{j}:=j\cdot(\gamma+\delta)+\lfloor\frac{j\cdot\delta}{\beta}\rfloor\cdot(\alpha-\beta)$
and we next prove $cyc_{j}\geq cyc_{1}$ which shows that $j=1$ is the optimal
solution for $cyc$. This is done by the inequality
$cyc_{j}-cyc_{1}=j\cdot(\gamma+\delta)+\lfloor\frac{j\cdot\delta}{\beta}\rfloor\cdot(\alpha-\beta)-(\gamma+\delta+\lfloor\frac{\delta}{\beta}\rfloor\cdot(\alpha-\beta))=$
$(j-1)\cdot\gamma+(j\cdot\delta-\lfloor\frac{j\cdot\delta}{\beta}\rfloor\cdot\beta)-\delta+(\lfloor\frac{j\cdot\delta}{\beta}\rfloor\cdot\alpha-\lfloor\frac{\delta}{\beta}\rfloor\cdot\alpha)+\lfloor\frac{\delta}{\beta}\rfloor\cdot\beta\geq\\\
(j-1)\cdot\gamma-\delta\geq\gamma-\delta\geq 0$.
The second summand in the second line is not negative due to the inequality
(4). This holds obviously for the fourth summand
$\lfloor\frac{j\cdot\delta}{\beta}\rfloor\cdot\alpha-\lfloor\frac{\delta}{\beta}\rfloor\geq
0$. In the last inequalities $j>0$ and $\gamma\geq\delta$ is used. It remains
to prove that negative values of $i$ are not needed to compute $cyc$ in the
cases under review. In the same way as before the inequality
$d(O,\begin{pmatrix}\xi\\\ \eta\end{pmatrix})\leq d(O,\begin{pmatrix}\xi\\\
\eta\end{pmatrix}-\begin{pmatrix}\alpha\\\ -\beta\end{pmatrix})$ is proved.
This shows, that adding the vector $-(\alpha,-\beta)$ to $(\gamma,\delta)$
cannot decrease the distance from the origin. The cases for $j>1$ is are
similar.
For the alternative case $\alpha>\beta$ and $\delta\geq\gamma$ we look at the
symmetric cycloid $\mathcal{C}(\beta,\alpha,\delta,\gamma)$ (by interchanging
$\alpha$ and $\beta$, as well as $\gamma$ and $\delta$).
d) If $\beta|\delta$ then Equation (2) becomes
$\vec{x}{{}_{j}}=j\cdot\begin{pmatrix}\gamma\\\
\delta\end{pmatrix}+\frac{j\cdot\delta}{\beta}\cdot\begin{pmatrix}\alpha\\\
-\beta\end{pmatrix}=\begin{pmatrix}j\cdot\gamma+j\cdot\frac{\delta}{\beta}\cdot\alpha\\\
j\cdot\delta+j\cdot\frac{\delta}{\beta}\cdot(-\beta)\end{pmatrix}=j\cdot\begin{pmatrix}\gamma+\frac{\delta}{\beta}\cdot\alpha\\\
0\end{pmatrix}$.
Since all the points for different $j$ are on the $\xi$-axis, for $j=1$ we
obtain a minimal value of $cyc=\gamma+\frac{\delta}{\beta}\cdot\alpha$.
e) Again, for the alternative case $\alpha>\beta$ and $\alpha|\gamma$ we look
at the symmetric cycloid.

To illustrate part c) of Theorem 4.1 consider the cycloid
$\mathcal{C}(1,1,4,1)$. The points $\vec{x}=j\cdot\begin{pmatrix}\gamma\\\
\delta\end{pmatrix}+i\cdot\begin{pmatrix}\alpha\\\
-\beta\end{pmatrix}=\begin{pmatrix}4\\\
1\end{pmatrix}+i\cdot\begin{pmatrix}1\\\ -1\end{pmatrix}=\begin{pmatrix}u\\\
v\end{pmatrix}$ are $\begin{pmatrix}5\\\ 0\end{pmatrix}$ and
$\begin{pmatrix}4\\\ 1\end{pmatrix}$ for $i=1$ and $i=0$, respectively, both
resulting in $cyc=u+v=5$. On the other side for the values $i=-1,-2,-3,-4$ we
obtain $\begin{pmatrix}3\\\ 2\end{pmatrix}$, $\begin{pmatrix}2\\\
3\end{pmatrix}$, $\begin{pmatrix}1\\\ 4\end{pmatrix}$ and $\begin{pmatrix}0\\\
5\end{pmatrix}$, respectively, with the same result for $cyc$. Hence
$i=\lfloor\frac{\delta}{\beta}\rfloor=\lfloor\frac{1}{1}\rfloor=1$ is
suffient. The cases for $j>1$ are similar.

The pattern of Figure 5 is derived from the cycloid $\mathcal{C}(1,2,5,3)$.
The point $C_{3}$ is computed by the following formula, as derived in the
preceeding proof: $\vec{x}{{}_{3}}=3\cdot\begin{pmatrix}\gamma\\\
\delta\end{pmatrix}+\lfloor\frac{3\cdot\delta}{\beta}\rfloor\cdot\begin{pmatrix}\alpha\\\
-\beta\end{pmatrix}=3\cdot\begin{pmatrix}5\\\
3\end{pmatrix}+\lfloor\frac{3\cdot 3}{2}\rfloor\cdot\begin{pmatrix}1\\\
-2\end{pmatrix}=\begin{pmatrix}19\\\ 1\end{pmatrix}$, leading to $cyc_{3}=20$.
The calues for $C_{2}$ and $C_{1}=R$ are $\begin{pmatrix}13\\\ 0\end{pmatrix}$
and $\begin{pmatrix}6\\\ 1\end{pmatrix}$, respectively.

For the cycloid $\mathcal{C}(2,8,1,4)$ we obtain $cyc=5$ by Theorem 4.1 c).
However, using $\mathbf{A}\cdot\begin{pmatrix}i\\\
j\end{pmatrix}=\begin{pmatrix}2&1\\\ -8&4\end{pmatrix}\cdot\begin{pmatrix}1\\\
2\end{pmatrix}=\begin{pmatrix}4\\\ 0\end{pmatrix}$ we obtain $cyc=4$, giving a
counter-example to part c) of the theorem.

##  5 Conclusion

Using _Cycloid Algebra_ a new proof for some important net isomorphisms of
cycloids and the problem of equivalence is derived. By the same method also a
new proof for the minimal length of a cycloid cycle is obtained, which extends
the formula from [5]. This approach makes proofs simpler, as otherwise more
complicated and combinatorial methods were used.

## References

  * [1] Fenske, U.: Petris Zykloide und Überlegungen zur Verallgemeinerung. Diploma Thesis (2008)
  * [2] Kummer, O., Stehr, M.O.: Petri’s Axioms of Concurrency - a Selection of Recent Results. In: Application and Theory of Petri Nets 1997. Lecture Notes in Computer Science, vol. 1248, pp. 195 – 214. Springer-Verlag, Berlin (1997)
  * [3] Petri, C.A.: Nets, Time and Space. Theoretical Computer Science (153), 3–48 (1996)
  * [4] Smith, E., Reisig, W.: The semantics of a net is a net – an exercise in general net theory. In: Voss, K., Genrich, J., Rozenberg, G. (eds.) Concurrency and Nets. pp. 461–479. Springer-Verlag, Berlin (1987)
  * [5] Valk, R.: Formal Properties of Petri’s Cycloid Systems. Fundamenta Informaticae 169, 85–121 (2019)
  * [6] Valk, R.: Circular Traffic Queues and Petri’s Cycloids. In: Application and Theory of Petri Nets and Concurrency. Lecture Notes in Computer Science, vol. 12152, pp. 176 – 195. Springer-Verlag, Berlin (2020)


# Thin Lenses and Thin Cameras

Wubin Pang
Department of Electrical and Computer Engineering
Duke University
Durham, NC 27705
<EMAIL_ADDRESS>
&David J. Brady
Wyant College of Optical Sciences
University of Arizona
Tucson, Az 85721
<EMAIL_ADDRESS>

###### Abstract

Cassegrain designs can be used to build thin lenses. We analyze the
relationships between system thickness and aperture sizes of the two mirrors
as well as FoV size. Our analysis shows that decrease in lens thickness
imposes tight constraint on the aperture and FoV size. To mitigate this
limitation, we propose to fill the gaps between the primary and the secondary
with high index material. The Gassegrain optics cuts the track length into
half and high index material reduces ray angle and height, consequently the
incident ray angle can be increased, i.e., the FoV angle is extended. Defining
telephoto ratio as the ratio of lens thickness to focal length, we achieve
telephoto ratios as small as 0.43 for a visible Cassegrain thin lens and 1.20
for an infrared Cassegrain thin lens. To achieve an arbitrary FoV coverage, we
present an strategy by integrating multiple thin lenses on one plane with each
unit covering a different FoV region. To avoid physically tilting each unit,
we propose beam steering with metasurface. By image stitching, we obtain wide
FoV images.

The need for thin cameras has progressively grown as camera applications in
mobile and wearable devices has exploded over the past 20 years. Several
technological advances have driven the miniaturization of camera modules, such
as shrinkage of pixel pitch, complex surface figures, new plastic materials
and many others. Among all factors, down-scaled pixel pitch is the main drive
which also leads to downsized image sensor format and reduced sensor cost. At
present, pixel size of image sensors in mobile devices is approaching $1\mu
m$. Due to small pixel pitch, high angular resolution can be realized with
small focal length, thus the thickness of the camera modules is reduced
accordingly. Downscaled pixel size has its own tradeoffs. Firstly, small pixel
size yields degraded dynamic range and increased noise level, which results in
low signal to noise ratio (SNR) and leads to degenerated image quality.
Moreover, the pixel size cannot be below the diffraction limited spot size.

Recently, several groups have demonstrated thin optical elements based on
metamaterials [1, 2, 3], geometric phase modulation [4] or diffractive
elements [5]. However, while thin lenses are necessary for thin cameras, thin
optics are not sufficient to produce thin optical systems. Naively, a thin
lens with focal length $F$ still requires that the camera thickness be greater
than $F$, no matter how thin the lens is. Previous thin camera design
strategies focus on folded optics [6, 7, 8], multiaperture sampling [9, 10,
11] and coded apertures [12].

All these efforts have demonstrated useful concepts and successful ideas in
producing thin imagers. Nonetheless, each one by itself also suffers from
major flaws and is inadequate to create competitive thin cameras. For example,
while an n-folded optic reduces track length by a factor of n, the field of
view (FoV) of folded optics is very limited. This is due to delicate ray path
steered by multiple mirrors, where even a slight change of ray angle could
result in stopped or strayed ray tracing. The field angle of a folded optics
is generally less than $10^{\circ}$. Therefore, it is common to see folded
optics being used only as telescopes for astrophotography and aerial
surveillance. Other approaches include multiapture sampling strategies using
super-resolution or pixel braiding for achieving desired resolution with
microlens arrays of tiny focal length. Super-resolution relies on image
parallax existing on different channels. The pixel braiding strategy draws
inspiration from compound eyes of insects, a pitch difference between the
lenslets and the corresponding pitch is necessary and high resolution image is
reconstructed through electronic stitching or pixel braiding. Despite somewhat
enhanced spatial resolution, the total bandwidth product under multiaperture
scheme is unsatisfactory and total pixel counts is currently less than one
megapixel.

Instantaneous field of view (e.g. resolution) is fundamentally tied to focal
length, specifically ${\rm ifov}=\delta/F$, where $\delta$ is the pixel pitch.
This means that the goal of the system is to maximize focal length. The
relative success of a thin lens method can be evaluated by using the telephoto
ratio. The telephoto ratio originally is based on the telephoto design defined
as the ratio between the physical length and the focal length, i.e., $L/f$.
Judging from this criterion, today’s miniaturized lenses barely gain any
advancement in terms of reducing the telephoto ratio. Through our review on
existing thin camera methods, we find the folded optics is the only approach
which keeps the long focal length while doing thickness reduction. The problem
of narrow FoV could be solved by multi-camera strategy, as this strategy has
already become a standard measure in mobile phone industry. This letter
explores optical designs that combine folded optics with camera arrays to
produce thin cameras with wide FoV coverage.

Folded optics are traditionally used in building astronomical telescopes for
achieving long focal length within limited track length. The limited FoV and
severe central obscuration make it unsuitable in customer camera production
where at least FoVs above $10^{\circ}$ are required. As cameras with compact
form factor are in high demands, in 2007 Ford et al. proposed to build
ultrathin cameras using folding optics and named this strategy as "origami
optics"[13, 14]. In origami optics, the light path is reflected off annular
mirrors by multiple times and the whole system are fabricated on a monolithic
substrate. In comparison with the sequential layout, the thickness of the
folded lenses is reduced by a factor of $n$, where $n$ denotes the number of
folds.

As mentioned before, folded optics tends to have narrow FoV and small
effective aperture due to obscuration. Here we discuss about Cassegrain
systems. Cassegrain system is the simplest and earliest folded optics dating
back to 1672. It consists of two mirrors, a primary and a secondary. The
primary is a concave mirror which converges and reflects the incoming beams
off to the secondary. The secondary is usually a convex mirror which reflects
off the beams onto the image sensor plane. The combination of a positive
primary and a negative secondary also makes a telephoto style benefiting a
reduced track length even further. The occlusion of the secondary mirror
results in an annular aperture which causes MTF curves to fall off over middle
frequency band.

Figure 1: Cross-section of a folding Cassegrain system.

Assuming a Cassegrain lens with major parameters as shown in Fig.1, the radii
of the curvature of the primary and the secondary are $R_{1}$ and $R_{2}$ and
the aperture diameters are $D_{1}$ and $D_{2}$, respectively. The separation
between the two mirrors is $d$. The top ray from the edge field angle $\theta$
is reflected off the primary, in order for the top ray to connect with the
secondary, the diameter of the secondary must comply to the constraint

$D_{2}\geq D_{1}-2(\frac{D_{1}}{R_{1}}-\theta)d$ (1)

Since the diameter of the secondary cannot be larger than that of the primary,
thereby the field angle $\theta<D_{1}/R_{1}$. Commonly the aperture of a
mirror is far smaller than its radius of the curvature. Consequently, the
upper limit for the FoV is rather small. Notably, this limitation here only
accounts for the clearance of light path on the secondary, when aberration is
considered as will be in real design works, the upper limit will be even
lower.

Also noticing that $D_{1}/R_{1}-\theta$ should be positive, simple
rearrangement of the terms in inequation.1 relates this limitation to a
constraint on the lens thickness $d$

$d\geq\frac{D_{1}-D_{2}}{2(\frac{D_{1}}{R_{1}}-\theta)}$ (2)

Inequation2 explicitly shows the relationship among the lens thickness $d$,
aperture diameters of the two mirrors $D_{1},D_{2}$ and FoV angle $\theta$.
Specifically, to make thin lenses or to reduce $d$, we must either increase
the size of the secondary mirror $D_{2}$ resulting in reduced light throughput
or decrease the field angle $\theta$, i.e. making narrow FoV. To summarize,
the folding optics provides reduced track length $d\approx f/N$ with decreased
light throughput and FoV angle.

To overcome this limitation, we can insert more optical elements and employ
complex surface figures, such as the even-aspheric surface. By adding
refractive elements, we create a catadioptric design style. The extra elements
provide more degrees of freedom for ray path manipulation and aberration
control. Here we show a design example of a miniaturized catadioptric lens
aiming for miniature camera applications. For this design, we have a $20mm$
focal length, F/2 aperture, and $17^{\circ}$ full FoV. The working wavelength
in over $486nm-656nm$ visible band. The optical layout and important
dimensions are illustrated in Fig.2. The design consists of two cemented
doublets, each doublet has a mirror surface for ray path folding. The total
track length of this design is $7mm$, which leads to a telephoto ratio of
0.35. The MTF curves are shown in Fig.3.

Figure 2: Layout of a catadioptric miniature lens design. Figure 3: MTF curves
of the catadioptric design.

Making a catadioptric design is fairly effective in increasing lens aperture
and FoV. However, the achieved lens tack length (z-height) is not ideal, since
a cellphone case can only accept lens z-height less than $5mm$. we still need
to find approaches to reduce the telephoto ratio even further.

To solve the problem, we propose to fill the air space between the two mirrors
with material of high refractive index. According to Snell’s law, ray angle is
inversely proportional to the refractive index of the medium
$\theta\propto\frac{1}{n}$. By filling the air space with high index material,
the ray angles could be reduced by a factor of $\frac{1}{n}$. As demonstrated
in Fig.4(a), with air gap, the growing field angle causes a portion of the ray
bundle to stray away from the secondary mirror while the remaining rays
interfere with the aperture of primary mirror. In contrast, as shown in
Fig.4(b), with high index material, the ray angle is reduced thereby ray beams
trace through the system smoothly and interference free. With reduced ray
angle, not only the off-axis aberration is decreased, but also the lower
boundary for the thickness $d$ gets pushed to a even lower value as we replace
the field angle $\theta$ with $\theta/n$ in Eqn.2. One would worry about
problems of increased weight and expense associated with the use of high index
materials. But noticing that the volume of the material is proportionate to
the thickness of the optics $d$, which is compressed by application of the
material. Moreover, the method proposed here is targeting for miniaturized
lens systems and the problems of material weight and cost are rendered
insignificant.

Figure 4: Effective aperture size and field of view of folded
lenses.(a)Without high index filling in, high angle rays are difficult to be
confined or not to intersect with other rays.(b)With high index filling in,
ray paths are easy to be bounded and controlled.

To drive home our point, we show a concrete design example in which we fill
LASF35 (Nd=2.02,Vd=29.06), an optical glass from SCHOTT catalog, into the gap
between the primary and the secondary of a Cassegrain system. Fig.5(a) shows
the layout of the system. The two-mirror system contains three aspheric
optical surfaces, the first one is refractive in the front, the others are two
mirror surfaces. The image plane is in contact with the back side of the
primary mirror for avoiding total internal reflection. Here are the three key
specifications of the system: focal length $f=7mm$, outer aperture is $5mm$
and inner aperture is $1.6mm$, field of view: $FoV=3^{\circ}$. The track
length of the system is $L=3mm$ resulting in a telephoto ratio of $T\approx
0.43$. For the annular aperture, the outer diameter is $5mm$, the inner
diameter is $1.6mm$, hence the effective diameter is $4.74mm$. The modulation
transfer function (MTF) curves measuring the imaging performance are shown in
Fig.5(b). The system achieves diffraction limited performance. Because of the
fill into of high index material,the cut-off frequency lies at about
1170cycles/mm.

Figure 5: A Cassegrain lens design using high index material filling in.(a)
Layout of the lens design.(b) MTF curves of the lens design.

The index of refraction of natural materials can rarely reach 2 for visible
spectral region, while it can be above 4 for the infrared region. Naturally,
we apply our method in an lens design for infrared imagers. In our second
example, a Cassegrain system is used in infrared imaging. The gap between the
primary and the secondary is filled with germanium $(n=4.0243\ {\rm at}\
\lambda=4\mu m\ and\ n=4.0032\ {\rm at}\ \lambda=10\mu m)$. The layout of the
system is shown in Fig.6(a). The focal length is $5mm$, outer aperture is
$5mm$, the obscuration diameter is $1.6mm$ and the field of view (FoV) is 10
degrees, the total track length is $6mm$ which gives a telephoto ratio of
$1.27$. The MTF curves in Fig.6(b) show diffraction limited performance.

Figure 6: A infrared Cassegrain system with a substrate made of
germanium.(a)Layout of the lens design.(b) MTF curves of the lens design.

For normal optical materials, high refractive index often indicates high
dispersion and absorption. New metamaterials can generate artificial high
index over a wide spectrum band with well controlled dispersion and reasonable
light efficiency[15]. High reflectivity on the interface of high index
difference could be solved by anti-reflection coatings.

Undoubtedly, high index material filling also adds to the weight and material
cost for the imagers. This is impractical for large folded lenses and
unacceptable for huge astronomical telescopes which accounts for most usage of
folded lenses currently. However, as we bring folded lenses into developing
miniaturized cameras for mobile platforms, the side effects of extra weight
and cost are totally insignificant.

In smartphones, major manufactures increasingly compete to integrate more
camera units in their devices. Array cameras are also popular in security,
surveillance, automation, virtual reality (VR) and augmented reality (AR).
Lens arrays achieve wide angle FoV by pointing each lens unit to a different
viewing angle and produce panoramas by stitching sub-image from different
channels. Currently steering lens units requires physical tilt so that the
optical axis is aiming at the targeted viewing direction. For a thin camera of
greater lateral dimension than longitudinal dimension, tilting the camera
could cause increase in thickness and difficulty in system assembling. As
shown in the US. patent[16], a part of the aperture is clipped off for
preserving the required array thickness. Alternatively, a curved mount could
be implemented as shown in many other practices. Lens tilting complicates the
mechanical design as well as assembly procedure, sometimes also adds extra
thickness to the array.

To avoid all the inconvenience associated with lens tilting, method of
granting the camera units with deflected view is required. One would imagine
that glass wedges could do the work by changing direction of the incoming beam
of light. However, glass wedges incur chromatic aberration and also add on
significant extra thickness. Diffracting elements can also be used to skew the
view, but also introduce chromatic aberration as well as decrease light
efficiency as light is being divided into different orders. Meanwhile,
metasurface, as a hot research topic in which considerable progress has been
made, provides a solution for pointing camera units in different directions
without having to physically tilt the camera unit.

The advancement in matesurfaces and high index material of wide band and low
dispersion offers new opportunities for the thin lens research and
development. In order to tilt the optical axis of a lens, a linear phase
modulation should be applied to the incoming light. A meta-surface with phase
modulation function expressed as $e^{i\frac{2\pi}{\lambda}(\alpha x+\beta y)}$
would bend a skewed ray with direction vector
$(\alpha,\beta,\sqrt{1-\alpha^{2}-\beta^{2}})$ into the new direction in
parallel with the optical axis with direction vector as $(0,0,1)$. Since the
modulation is linear, it does not introduce any aberrations.

Figure 7: Meta-pointers.(a) Metasurface make a column of lens arrays to point
to different directions without having to tilt the constituent lens units. (b)
A 2D lens array of flat formation achieves extensive field of view using meta-
surface.

"Meta tilting" is especially advantageous for systems of being wider in
lateral dimension than in axial dimension. This is the case for our Cassegrain
Visible system shown in fig.5. As shown in Fig.7(a), an row of five lens units
achieves a total $15^{\circ}\times 3^{\circ}$ field of view with a specified
phase modulation simulating a meta-surface attached to the first surface of
each lens unit. The Fig.7.(b) illustrates an extension from one row to a two
dimensional array of cameras consisting of nineteen camera units in a
triangular formation. These metasurfaces can be made as detachable patches,
therefore, the center viewing direction of each channel can be changed by
replacing the front metasurface patch easily.

To summarize, thin lenses are desirable in many application scenarios. They
extends the accessibility of cameras, reduces camera size and weight and
facilitates portable and wearable devices. Currently, majority of thin lenses
are only a result from down-scaled normal sized lenses, which is mainly
enabled by smaller semiconductor pixel pitch and sensor formats. Though this
leads to a shortened track length, it also results in decreased transverse
dimensions and reduced light flux. Negative effects include reduced dynamic
range and degraded SNR, with which image quality suffers. Therefore, superior
solutions for thin lens should seek to preserve the lens focal length and
aperture size. Folded optics represented by Cassegrain system provides a valid
solution for building compact camera modules with long focal length and large
aperture size. The problems of narrow FoV and aperture obcuration associated
with the folded optics can be mitigated by the employment of high index
materials. By filling the air gap with high index material, beams of light can
be easily confined inside the system space and ray blockage and stray light is
effective prevented. The two Cassegrain systems in our design example section,
one in visible region and the other in infrared region, demonstrate the
effectiveness of our approach. Ultimately, to be able to realize thin cameras
of real wide FoV, we suggest employing a simplest possible metasurface which
only needs to generate linear phase modulations. By attaching or clipping such
a surface to the front of a imaging system, the boresight of the optics can be
changed. When our suggested metasurface is combined with array cameras, all
the array units could be assembled on a flat formation with parallel axial
orientations. This tilt free camera steering method essentially provides a way
to building wide angle array cameras without having to surrender the
accomplished thickness in each constituent unit.

## References

  * [1] Mohammadreza Khorasaninejad, Wei Ting Chen, Robert C Devlin, Jaewon Oh, Alexander Y Zhu, and Federico Capasso.  Metalenses at visible wavelengths: Diffraction-limited focusing and subwavelength resolution imaging.  Science, 352(6290):1190–1194, 2016.
  * [2] Shuming Wang, Pin Chieh Wu, Vin-Cent Su, Yi-Chieh Lai, Mu-Ku Chen, Hsin Yu Kuo, Bo Han Chen, Yu Han Chen, Tzu-Ting Huang, Jung-Hsi Wang, et al.  A broadband achromatic metalens in the visible.  Nature nanotechnology, 13(3):227, 2018.
  * [3] Patrice Genevet, Federico Capasso, Francesco Aieta, Mohammadreza Khorasaninejad, and Robert Devlin.  Recent advances in planar optics: from plasmonic to dielectric metasurfaces.  Optica, 4(1):139–152, 2017.
  * [4] Michael J Escuti, Jihwan Kim, and Michael W Kudenov.  Controlling light with geometric-phase holograms.  Optics and Photonics News, 27(2):22–29, 2016.
  * [5] Peng Wang, Nabil Mohammad, and Rajesh Menon.  Chromatic-aberration-corrected diffractive lenses for ultra-broadband focusing.  Scientific reports, 6:21545, 2016.
  * [6] Eric J. Tremblay, Ronald A. Stack, Rick L. Morrison, and Joseph E. Ford.  Ultrathin cameras using annular folded optics.  Appl. Opt., 46(4):463–471, Feb 2007.
  * [7] Daniel L Marks, Nathan Hagen, Mark Durham, and David J Brady.  Wide-field compact catadioptric telescope spanning 0.7–14 $\mu$m wavelengths.  Applied optics, 52(18):4334–4342, 2013.
  * [8] Sue Tallon.  A pocket camera with many eyes.  IEEE Spectrum, 53(11):34–40, 2016.
  * [9] Jun Tanida, Tomoya Kumagai, Kenji Yamada, Shigehiro Miyatake, Kouichi Ishida, Takashi Morimoto, Noriyuki Kondou, Daisuke Miyazaki, and Yoshiki Ichioka.  Thin observation module by bound optics (tombo): concept and experimental verification.  Applied optics, 40(11):1806–1813, 2001.
  * [10] Kartik Venkataraman, Dan Lelescu, Jacques Duparré, Andrew McMahon, Gabriel Molina, Priyam Chatterjee, Robert Mullis, and Shree Nayar.  Picam: An ultra-thin high performance monolithic camera array.  ACM Transactions on Graphics (TOG), 32(6):166, 2013.
  * [11] Mohan Shankar, Rebecca Willett, Nikos Pitsianis, Timothy Schulz, Robert Gibbons, Robert Te Kolste, James Carriere, Caihua Chen, Dennis Prather, and David Brady.  Thin infrared imaging systems through multichannel sampling.  Applied optics, 47(10):B1–B10, 2008.
  * [12] M Salman Asif, Ali Ayremlou, Aswin Sankaranarayanan, Ashok Veeraraghavan, and Richard G Baraniuk.  Flatcam: Thin, lensless cameras using coded aperture and computation.  IEEE Transactions on Computational Imaging, 3(3):384–397, 2016\.
  * [13] Eric J Tremblay, Ronald A Stack, Rick L Morrison, and Joseph E Ford.  Ultrathin cameras using annular folded optics.  Applied optics, 46(4):463–471, 2007.
  * [14] Eric J Tremblay, Ronald A Stack, Rick L Morrison, Jason H Karp, and Joseph E Ford.  Ultrathin four-reflection imager.  Applied optics, 48(2):343–354, 2009.
  * [15] Sajan Shrestha, Adam C Overvig, Ming Lu, Aaron Stein, and Nanfang Yu.  Broadband achromatic dielectric metalenses.  Light: Science & Applications, 7(1):85, 2018.
  * [16] Daniel Marks, David Jones Brady, and Nathan Adrian Hagen.  Apparatus comprising a compact catadioptric telescope, November 29 2016\.  US Patent 9,507,129.