#  The difference vectors for convex sets and a resolution of the geometry
conjecture

Salihah Alwadani, Heinz H. Bauschke, Julian P. Revalski, and Xianfu Wang
Mathematics, University of British Columbia, Kelowna, B.C. V1V 1V7, Canada.
E-mail<EMAIL_ADDRESS>Mathematics, University of British Columbia,
Kelowna, B.C. V1V 1V7, Canada. E-mail<EMAIL_ADDRESS>Institute of
Mathematics and Informatics, Bulgarian Academy of Sciences, Acad. G. Bonchev
str., Block 8, 1113 Sofia, Bulgaria. E-mail<EMAIL_ADDRESS>Mathematics, University of British Columbia, Kelowna, B.C. V1V 1V7, Canada.
E-mail<EMAIL_ADDRESS>
(May 28, 2021 (version accepted for publication))

###### Abstract

The geometry conjecture, which was posed nearly a quarter of a century ago,
states that the fixed point set of the composition of projectors onto nonempty
closed convex sets in Hilbert space is actually equal to the intersection of
certain translations of the underlying sets.

In this paper, we provide a complete resolution of the geometry conjecture.
Our proof relies on monotone operator theory. We revisit previously known
results and provide various illustrative examples. Comments on the numerical
computation of the quantities involved are also presented.

2020 Mathematics Subject Classification: Primary 47H09; Secondary 47H05,
47H10, 90C25

Keywords: Attouch-Théra duality, circular right shift operator, convex sets,
cycle, fixed point set, monotone operator theory, projectors

##  1 Introduction

###  1.1 Fixed points of compositions of projectors

Throughout,

$X$ is a real Hilbert space (1)

and

$C_{1},\ldots,C_{m}$ are nonempty closed convex subsets of $X$, (2)

with projectors $P_{C_{1}},\ldots,P_{C_{m}}$ which we also write more simply
as $P_{1},\ldots,P_{m}$, and with $m\in\\{2,3,\ldots,\\}$. We define the fixed
point sets of the cyclic compositions by

$F_{m}:=\operatorname{Fix}(P_{m}\cdots
P_{1}),F_{m-1}:=\operatorname{Fix}(P_{m-1}\cdots
P_{1}P_{m}),\ldots,F_{1}:=\operatorname{Fix}(P_{1}P_{m}\cdots P_{2}).$ (3)

Compositions of projectors are often employed in projection methods. This is a
vast area which we will not summarize here; however, we refer the reader to
[17] as a starting point as well as the very recent paper [19].

###  1.2 The geometry conjecture, difference vectors, and cycles

The geometry conjecture, formulated first in 1997 (see [9, Conjecture 5.1.6]),
states that there exists a list of vectors $v_{1},\ldots,v_{m}$ in $X$ such
that

$v_{1}+v_{2}+\cdots+v_{m}=0$ (4)

and

$F_{m}=C_{m}\cap(C_{m-1}+v_{m-1})\cap\cdots\cap(C_{1}+v_{1}+\cdots+v_{m-1}),$
(5)

and analogously for $F_{m-1},\ldots,F_{1}$. These vectors form the tuple
$(v_{1},\ldots,v_{m})$ of difference vectors and they are sometimes also
referred to as displacement vectors or gap vectors.

This conjecture is known to be true when $m=2$ or $C_{1}\cap
C_{2}\cap\cdots\cap C_{m}\neq\varnothing$; see [9, Subsection 5.1]. The
following is known when all sets $F_{i}$ are nonempty: let $f_{1}\in F_{1}$,
and set $f_{2}:=P_{2}f_{1},f_{3}:=P_{3}f_{2},\ldots,f_{m}:=P_{m}f_{m-1}$; we
shall refer to the tuple $(f_{1},\ldots,f_{m})$ as a cycle. (Cycles are of
interest even when $C_{1},\ldots,C_{m}$ are all hyperplanes — see [15, Chapter
8] and [16, Chapter 50].) Setting

$v_{1}=f_{2}-f_{1},\;v_{2}=f_{3}-f_{2},\;\ldots,\;v_{m-1}=f_{m}-f_{m-1},\;v_{m}=f_{1}-f_{m},$
(6)

which turns out to be independent of the cycle chosen, makes 4 true and yields
“one half” of 5, namely: $F_{m}\subseteq
C_{m}\cap(C_{m-1}+v_{m-1})\cap\cdots\cap(C_{1}+v_{1}+\cdots+v_{m-1})$ and
analogously for $F_{m-1},\ldots,F_{1}$ (see [9, Theorem 5.1.2]). However, this
description is not fully satisfying — it is only _implicit_ in the sense it
was not known what the difference vectors are when the fixed point sets
$F_{i}$ are empty. The sole exception to this mystery was the case when $m=2$
which allowed for the _explicit_ description of the two difference vectors by

$P_{\overline{C_{2}-C_{1}}}(0),P_{\overline{C_{1}-C_{2}}}(0);$ (7)

see [7, Lemmas 2.1 and 2.3]. Note that this description is _not_ based on the
fixed point sets $F_{1},F_{2}$. In this particular case, these fixed point set
have the beautiful description (see [18, Theorem 2])

$F_{1}=\big{\\{}{x\in
C_{1}}~{}\big{|}~{}{d_{C_{2}}(x)=\inf\|C_{1}-C_{2}\|}\big{\\}},F_{2}=\big{\\{}{x\in
C_{2}}~{}\big{|}~{}{d_{C_{1}}(x)=\inf\|C_{1}-C_{2}\|}\big{\\}};$ (8)

moreover, the cycles $(f_{1},f_{2})$ are precisely the minimizers of the
bivariate function

$X\times
X\to\mathbb{R}\colon(x_{1},x_{2})\mapsto\|x_{1}-x_{2}\|+\iota_{C_{1}}(x_{1})+\iota_{C_{2}}(x_{2}),$
(9)

where $d_{S}$ and $\iota_{S}$ denote the distance and indicator function of a
subset $S$ of $X$, respectively. (See [18], [7], [8], and [9] for much more on
the case when $m=2$.) A referee also pointed out that when $m=2$ and
$F_{1}=F_{2}=\varnothing$ one cannot expect uniqueness of the difference
vectors as one may simply separate the sets even further.

The case when $m\geq 3$ is very interesting: The _negative_ result of Baillon,
Combettes, and Cominetti (see [5, Theorem 2.3]) states that when $X$ is at
least two-dimensional, then there is _no_ function $\varphi$ such that the
cycles are precisely the minimizers of the function
$\varphi(x_{1},\ldots,x_{m})+\iota_{C_{1}}(x_{1})+\cdots+\iota_{C_{m}}(x_{m})$.
(When $m=2$, we can pick $\varphi(x_{1},x_{2})=\|x_{1}-x_{2}\|$ or even the
differentiable function
$\varphi(x_{1},x_{2})=\tfrac{1}{2}\|x_{1}-x_{2}\|^{2}$. For results on
underrelaxed projectors, see also [6] and [21].) Even when cycles exist, the
“meaning” of the distance vector was not understood.

###  1.3 Aim and outline of this paper

_The aim of this paper is to settle the geometry conjecture in the
affirmative._ The resolution depends on key results from monotone operator
theory and yields a formula for the difference vectors.

The remainder of this paper is organized as follows. In Section 2, we
reformulate cycles and difference vectors in a product space using Attouch-
Théra duality. The proof of the geometry conjecture is then presented in
Section 3 (see Theorem 3.4). The cases $m=2,m=3$ are investigated in Sections
4 and 5. Numerical considerations are presented in Sections 6 and 7. The paper
concludes with a summary and perspectives for future work in Section 8.

Notation is largely from [11] to which we also refer for background material
on projections, convex analysis, and monotone operator theory. For valuable
references on monotone operator theory see, e.g., [13], [14], [24], and [25].

##  2 The displacement of the circular right shift operator

###  2.1 Product space and Attouch-Théra duality

From now on, we will also work in the product space

${\mathbf{X}}:=X^{m}$ (10)

in which we set

${\mathbf{C}}:=C_{1}\times\cdots\times
C_{m}\;\;\text{and}\;\;{\boldsymbol{\Delta}}:=\big{\\{}{(x,\ldots,x)\in{\mathbf{X}}}~{}\big{|}~{}{x\in
X}\big{\\}}.$ (11)

It is well known that the projectors onto these sets are given by

$P_{{\mathbf{C}}}(x_{1},\ldots,x_{m})=\big{(}P_{1}x_{1},\ldots,P_{m}x_{m}\big{)}$
(12)

and

$P_{{\boldsymbol{\Delta}}}(x_{1},\ldots,x_{m})=\frac{1}{m}\Big{(}\sum_{i=1}^{m}x_{i},\ldots,\sum_{i=1}^{m}x_{i}\Big{)}$
(13)

respectively (see, e.g., [11, Proposition 29.4 and Proposition 26.4(iii)]).
Next, we define the circular right-shift operator

${\mathbf{R}}\colon{\mathbf{X}}\to{\mathbf{X}}\colon(x_{1},x_{2},\ldots,x_{m})\mapsto(x_{m},x_{1},x_{2},\ldots,x_{m-1}).$
(14)

Recall (see Section 1.2) that $\mathbf{z}=(z_{1},\ldots,z_{m})\in{\mathbf{X}}$
is a cycle if $z_{1}=P_{1}z_{m}$, $z_{2}=P_{2}z_{1}$, …, $z_{m}=P_{m}z_{m-1}$,
which can be elegantly reformulated in ${\mathbf{X}}$ as the fixed point
equation

$\mathbf{z}=P_{{\mathbf{C}}}({\mathbf{R}}\mathbf{z}).$ (15)

Denote the (possibly empty) set of all cycles by

${\mathbf{Z}}:=\operatorname{Fix}(P_{\mathbf{C}}{\mathbf{R}}).$ (16)

In passing, we note that if $Q_{i}\colon(x_{1},\ldots,x_{m})\to x_{i}$, then
$F_{i}=Q_{i}({\mathbf{Z}})$. Because
$P_{\mathbf{C}}=(\operatorname{Id}+N_{\mathbf{C}})^{-1}$, where
$N_{\mathbf{C}}$ denotes the normal cone operator of ${\mathbf{C}}$, it
follows that 15 is equivalent to
${\mathbf{R}}\mathbf{z}\in(\operatorname{Id}+N_{\mathbf{C}})(\mathbf{z})$ and
to

$0\in
N_{{\mathbf{C}}}(\mathbf{z})+(\operatorname{Id}-{\mathbf{R}})(\mathbf{z}).$
(17)

We view this last inclusion sum problem as primal (Attouch-Théra) problem for
the pair $(N_{\mathbf{C}},\operatorname{Id}-{\mathbf{R}})$. (See [4] and [10]
for more on Attouch-Théra duality.) In view of the linearity of
${\mathbf{R}}$, the Attouch-Théra dual problem simplifies to

$0\in
N_{{\mathbf{C}}}^{-1}(\mathbf{y})+(\operatorname{Id}-{\mathbf{R}})^{-1}(\mathbf{y}).$
(18)

If $\mathbf{z}$ is any cycle; equivalently, a solution to the primal problem
17, then a direct computation (or [10, Proposition 2.4(iii)]) shows that
$N_{{\mathbf{C}}}(\mathbf{z})\cap-(\operatorname{Id}-{\mathbf{R}})(\mathbf{z})$
is a nonempty subset of dual solutions. Even better, both $N_{{\mathbf{C}}}$
and $\operatorname{Id}-{\mathbf{R}}$ are _paramonotone_ in the sense of Iusem
[22] by, e.g., [11, Example 22.4(i) and Example 22.9]. It thus follows from
[10, Theorem 5.3] that

$(\forall\mathbf{z}\in{\mathbf{Z}})\quad{\mathbf{R}}\mathbf{z}-\mathbf{z}\text{~{}is
the \emph{unique} solution of \lx@cref{creftype~refnum}{e:ATdual}}$ (19)

and that

$\text{if $\mathbf{y}$ solves \lx@cref{creftype~refnum}{e:ATdual},
then~{}~{}}{\mathbf{Z}}=N_{\mathbf{C}}^{-1}(\mathbf{y})\cap-(\operatorname{Id}-{\mathbf{R}})^{-1}(\mathbf{y})\neq\varnothing$
(20)

###  2.2 $(\operatorname{Id}-{\mathbf{R}})^{-1}$ and the skew operator
${\mathbf{T}}$

Recall the definition of the circular right shift operator ${\mathbf{R}}$ (see
14). By [2, Proposition 2.4], we have

$P_{\boldsymbol{\Delta}}=\frac{1}{m}\sum_{k=0}^{m-1}{\mathbf{R}}^{k}.$ (21)

Now define

${\mathbf{T}}=\frac{1}{2m}\sum_{k=1}^{m-1}(m-2k){\mathbf{R}}^{k},$ (22)

which is a _skew_ (hence maximally monotone) linear operator on
${\mathbf{X}}$, i.e.,

${\mathbf{T}}^{*}=-{\mathbf{T}}$ (23)

with

${\operatorname{ran}}\,{\mathbf{T}}\subseteq{\boldsymbol{\Delta}}^{\perp}$
(24)

(see [2, Proposition 3.2(ii)&(iii)]). Then [2, Theorem 3.3] states that

$(\operatorname{Id}-{\mathbf{R}})^{-1}=\tfrac{1}{2}\operatorname{Id}+N_{{\boldsymbol{\Delta}}^{\perp}}+{\mathbf{T}}.$
(25)

This form of $(\operatorname{Id}-{\mathbf{R}})^{-1}$ makes it clear that this
operator is _strongly monotone_ with constant $\tfrac{1}{2}$ which implies
that

the dual problem 18 has at most one solution (26)

which is consistent with 19. (A feature of Attouch-Théra duality is that
either both primal and dual have solutions or they both don’t. It is possible
that there is no cycle and hence no dual solution; see Section 5.2.2.)

We now collect some useful identities.

######  Proposition 2.1.

We have
$P_{\boldsymbol{\Delta}}{\mathbf{R}}={\mathbf{R}}P_{\boldsymbol{\Delta}}=P_{\boldsymbol{\Delta}}$
and hence
$P_{{\boldsymbol{\Delta}}^{\perp}}{\mathbf{R}}={\mathbf{R}}-P_{\boldsymbol{\Delta}}$.

Proof. Recalling 21, we observe that
$P_{\boldsymbol{\Delta}}{\mathbf{R}}={\mathbf{R}}P_{\boldsymbol{\Delta}}$.
Furthermore,

$\displaystyle{\mathbf{R}}P_{\boldsymbol{\Delta}}=\frac{1}{m}\sum_{k=0}^{m-1}{\mathbf{R}}^{k+1}=\frac{1}{m}\sum_{k=1}^{m}{\mathbf{R}}^{k}=\frac{1}{m}\sum_{k=0}^{m-1}{\mathbf{R}}^{k}=P_{\boldsymbol{\Delta}}$
(27)

because ${\mathbf{R}}^{m}={\mathbf{R}}^{0}=\operatorname{Id}$. It follows that
$P_{{\boldsymbol{\Delta}}^{\perp}}{\mathbf{R}}=(\operatorname{Id}-P_{\boldsymbol{\Delta}}){\mathbf{R}}={\mathbf{R}}-P_{\boldsymbol{\Delta}}$
. $\hfill\quad\blacksquare$

For the remainder of this section, let us abbreviate

${\mathbf{Q}}:=\frac{1}{m}\sum_{k=1}^{m-1}k{\mathbf{R}}^{k}.$ (28)

Clearly, ${\mathbf{Q}}$ commutes with ${\mathbf{R}}$, and hence also with
$P_{\boldsymbol{\Delta}}$ by 21.

######  Proposition 2.2.

$2{\mathbf{Q}}P_{\boldsymbol{\Delta}}=(m-1)P_{\boldsymbol{\Delta}}$.

Proof. Using Proposition 2.1, we see that

$\displaystyle{\mathbf{Q}}P_{\boldsymbol{\Delta}}$
$\displaystyle=\frac{1}{m}\sum_{k=1}^{m-1}k{\mathbf{R}}^{k}P_{\boldsymbol{\Delta}}=\frac{1}{m}\sum_{k=1}^{m-1}kP_{\boldsymbol{\Delta}}=\frac{1}{m}\frac{(m-1)m}{2}P_{\boldsymbol{\Delta}}=\frac{m-1}{2}P_{\boldsymbol{\Delta}}$
(29)

as claimed. $\hfill\quad\blacksquare$

######  Proposition 2.3.

$-{\mathbf{Q}}(\operatorname{Id}-{\mathbf{R}})=P_{{\boldsymbol{\Delta}}^{\perp}}$.

Proof. Using 28 and 21, we obtain

$\displaystyle-m{\mathbf{Q}}(\operatorname{Id}-{\mathbf{R}})$
$\displaystyle=({\mathbf{R}}-\operatorname{Id})(m{\mathbf{Q}})=({\mathbf{R}}-\operatorname{Id})\sum_{k=1}^{m-1}k{\mathbf{R}}^{k}$
(30a)
$\displaystyle=\sum_{k=1}^{m-1}k{\mathbf{R}}^{k+1}-\sum_{k=1}^{m-1}k{\mathbf{R}}^{k}=\sum_{k=2}^{m}(k-1){\mathbf{R}}^{k}-\sum_{k=1}^{m-1}k{\mathbf{R}}^{k}$
(30b)
$\displaystyle=(m-1){\mathbf{R}}^{m}+\Big{(}\sum_{k=2}^{m-1}\big{(}(k-1)-k\big{)}{\mathbf{R}}^{k}\Big{)}-{\mathbf{R}}$
(30c)
$\displaystyle=(m-1)\operatorname{Id}-\Big{(}\sum_{k=2}^{m-1}{\mathbf{R}}^{k}\Big{)}-{\mathbf{R}}$
(30d)
$\displaystyle=m\operatorname{Id}-\sum_{k=0}^{m-1}{\mathbf{R}}^{k}=m\operatorname{Id}-mP_{\boldsymbol{\Delta}}=mP_{{\boldsymbol{\Delta}}^{\perp}},$
(30e)

which completes the proof. $\hfill\quad\blacksquare$

We are now ready for the main result of this section which will play a key
role in subsequent sections.

######  Theorem 2.4.

We have

$\tfrac{1}{2}\operatorname{Id}+{\mathbf{T}}=\tfrac{m}{2}P_{\boldsymbol{\Delta}}-{\mathbf{Q}}$
(31)

and

$\big{(}\tfrac{1}{2}\operatorname{Id}+{\mathbf{T}}\big{)}^{-1}=\operatorname{Id}-{\mathbf{R}}+2P_{\boldsymbol{\Delta}}.$
(32)

Proof. Using 22, 21, and 28, we have

$\displaystyle{\mathbf{T}}$
$\displaystyle=\frac{1}{2m}\sum_{k=1}^{m-1}(m-2k){\mathbf{R}}^{k}=\frac{1}{2}\sum_{k=1}^{m-1}{\mathbf{R}}^{k}-\frac{1}{m}\sum_{k=1}^{m-1}k{\mathbf{R}}^{k}=\frac{1}{2}\Big{(}-\operatorname{Id}+mP_{\boldsymbol{\Delta}}\Big{)}-{\mathbf{Q}}$
(33)

which gives 31.

Next, using 31, Proposition 2.1, Proposition 2.2, and Proposition 2.3, we
obtain

$\displaystyle\big{(}\tfrac{1}{2}\operatorname{Id}+{\mathbf{T}}\big{)}\big{(}\operatorname{Id}-{\mathbf{R}}+2P_{\boldsymbol{\Delta}})$
$\displaystyle=\big{(}\tfrac{m}{2}P_{\boldsymbol{\Delta}}-{\mathbf{Q}}\big{)}\big{(}\operatorname{Id}-{\mathbf{R}}+2P_{\boldsymbol{\Delta}})$
(34a)
$\displaystyle=\tfrac{m}{2}\big{(}P_{\boldsymbol{\Delta}}-P_{\boldsymbol{\Delta}}{\mathbf{R}}\big{)}+mP_{\boldsymbol{\Delta}}-{\mathbf{Q}}(\operatorname{Id}-{\mathbf{R}})-2{\mathbf{Q}}P_{\boldsymbol{\Delta}}$
(34b)
$\displaystyle=mP_{\boldsymbol{\Delta}}+P_{{\boldsymbol{\Delta}}^{\perp}}-(m-1)P_{\boldsymbol{\Delta}}=P_{\boldsymbol{\Delta}}+P_{{\boldsymbol{\Delta}}^{\perp}}$
(34c) $\displaystyle=\operatorname{Id}.$ (34d)

This verifies 32 and thus completes the proof. $\hfill\quad\blacksquare$

######  Corollary 2.5.

We have

$\big{(}\tfrac{1}{2}\operatorname{Id}+T\big{)}^{-1}|_{{\boldsymbol{\Delta}}^{\perp}}=(\operatorname{Id}-{\mathbf{R}})|_{{\boldsymbol{\Delta}}^{\perp}},$
(35)

Proof. From 32, we have
$\big{(}\tfrac{1}{2}\operatorname{Id}+T\big{)}^{-1}|_{{\boldsymbol{\Delta}}^{\perp}}=(\operatorname{Id}-{\mathbf{R}}+2P_{\boldsymbol{\Delta}})|_{{\boldsymbol{\Delta}}^{\perp}}=(\operatorname{Id}-{\mathbf{R}})|_{{\boldsymbol{\Delta}}^{\perp}}$.
$\hfill\quad\blacksquare$

##  3 The proof of the geometry conjecture

Armed with 25, write the operator from the dual problem 18 as

$N_{\mathbf{C}}^{-1}+(\operatorname{Id}-{\mathbf{R}})^{-1}=N_{\mathbf{C}}^{-1}+\tfrac{1}{2}\operatorname{Id}+N_{{\boldsymbol{\Delta}}^{\perp}}+{\mathbf{T}}.$
(36)

This operator is in general not maximally monotone. On the other hand,
$N_{\mathbf{C}}^{-1}+N_{{\boldsymbol{\Delta}}^{\perp}}=N_{{\mathbf{C}}}^{-1}+N_{{\boldsymbol{\Delta}}}^{-1}=\partial\sigma_{\mathbf{C}}+\partial\sigma_{\boldsymbol{\Delta}}\subseteq\partial\sigma_{{\mathbf{C}}+{\boldsymbol{\Delta}}}$,
where $\sigma_{\mathbf{S}}$ denotes the support function of a subset
$\mathbf{S}$ of ${\mathbf{X}}$. Altogether, instead of working with 36, which
has no solution if there are no cycles, we propose to work with the the
_enlarged_ dual problem featuring the _maximally and strongly monotone_
operator

$\tfrac{1}{2}\operatorname{Id}+{\mathbf{T}}+\partial\sigma_{{\mathbf{C}}+{\boldsymbol{\Delta}}}.$
(37)

Using, e.g., [11, Proposition 22.11(ii)], the corresponding inclusion problem
always has a unique zero, which we denote by $\mathbf{y}\in{\mathbf{X}}$:

$0\in\tfrac{1}{2}\mathbf{y}+{\mathbf{T}}\mathbf{y}+\partial\sigma_{{\mathbf{C}}+{\boldsymbol{\Delta}}}(\mathbf{y}).$
(38)

(In fact, $\mathbf{y}$ is the resolvent of the maximally monotone operator
$2{\mathbf{T}}+2\partial\sigma_{{\mathbf{C}}+{\boldsymbol{\Delta}}}$,
evaluated at $0$.) Note that, using [11, Proposition 6.49 and Example 11.2]
$\mathbf{y}\in\operatorname{dom}\partial\sigma_{{\mathbf{C}}+{\boldsymbol{\Delta}}}\subseteq\operatorname{dom}\sigma_{{\mathbf{C}}+{\boldsymbol{\Delta}}}=\operatorname{dom}(\sigma_{{\mathbf{C}}}+\sigma_{{\boldsymbol{\Delta}}})=\operatorname{dom}\sigma_{\mathbf{C}}\cap\operatorname{dom}\sigma_{\boldsymbol{\Delta}}\subseteq(\operatorname{rec}{\mathbf{C}})^{\ominus}\cap(\operatorname{rec}{\boldsymbol{\Delta}})^{\ominus}$;
thus,

$\mathbf{y}\in(\operatorname{rec}{\mathbf{C}})^{\ominus}\cap{\boldsymbol{\Delta}}^{\perp}.$
(39)

Now define

$\mathbf{e}:=-\tfrac{1}{2}\mathbf{y}-{\mathbf{T}}\mathbf{y}\in{\boldsymbol{\Delta}}^{\perp},$
(40)

where $\mathbf{e}\in{\boldsymbol{\Delta}}^{\perp}$ because
$\mathbf{y}\in{\boldsymbol{\Delta}}^{\perp}$ (see 39) and
${\operatorname{ran}}\,{\mathbf{T}}\subseteq{\boldsymbol{\Delta}}^{\perp}$
(see 24). Note that
$-\mathbf{e}=(\tfrac{1}{2}\operatorname{Id}+{\mathbf{T}})\mathbf{y}$. Hence 35
yields

$\mathbf{y}=(\operatorname{Id}-{\mathbf{R}})(-\mathbf{e})={\mathbf{R}}\mathbf{e}-\mathbf{e}.$
(41)

Note that 38 is equivalent to
$\mathbf{e}\in\partial\sigma_{{\mathbf{C}}+{\boldsymbol{\Delta}}}(\mathbf{y})=\partial\iota^{*}_{{\mathbf{C}}+{\boldsymbol{\Delta}}}(\mathbf{y})$,
and hence also to

$\mathbf{y}\in N_{\overline{{\mathbf{C}}+{\boldsymbol{\Delta}}}}(\mathbf{e}),$
(42)

where the superscript “$\mbox{}^{*}$” denotes Fenchel conjugation. We pause
here to record the following result which provides a certificate for
$\mathbf{y}$:

######  Proposition 3.1.

(a characterization of $\mathbf{y}$) The unique solution to 38 is the unique
vector $\mathbf{y}$ satisfying the following:

$\mathbf{y}\in{\boldsymbol{\Delta}}^{\perp},\;\;-\tfrac{1}{2}\mathbf{y}-{\mathbf{T}}\mathbf{y}\in\overline{{\mathbf{C}}+{\boldsymbol{\Delta}}},\;\;\text{and}\;\;(\forall\mathbf{c}\in{\mathbf{C}})\;\left\langle{\mathbf{c}},{\mathbf{y}}\right\rangle\leq-\tfrac{1}{2}\|\mathbf{y}\|^{2}.$
(43)

Proof. As seen, $\mathbf{y}$ solves 38 if and only if 42 holds with
$\mathbf{e}$ defined in 40. The latter condition is equivalent to
$\mathbf{e}=-\tfrac{1}{2}\mathbf{y}-{\mathbf{T}}\mathbf{y}\in\overline{{\mathbf{C}}+{\boldsymbol{\Delta}}}$
and
$(\forall(\mathbf{c},\mathbf{d})\in{\mathbf{C}}\times{\boldsymbol{\Delta}})$
$\langle{\mathbf{y}},{\mathbf{c}+\mathbf{d}+\tfrac{1}{2}\mathbf{y}+{\mathbf{T}}\mathbf{y}}\rangle\leq
0$. Because $\mathbf{y}\in{\boldsymbol{\Delta}}^{\perp}$ (see 39) and
${\mathbf{T}}$ is skew (see 23), the last condition is indeed equivalent to
43. $\hfill\quad\blacksquare$

Combining 40 and 42, we deduce that

$\mathbf{e}\in{\boldsymbol{\Delta}}^{\perp}\cap\overline{{\mathbf{C}}+{\boldsymbol{\Delta}}}.$
(44)

(This last intersection
${\boldsymbol{\Delta}}^{\perp}\cap\overline{{\mathbf{C}}+{\boldsymbol{\Delta}}}$
need not be a singleton as we can see by studying the case when
$C_{1}=C_{2}=\cdots=C_{m}=X$ and hence ${\mathbf{C}}={\mathbf{X}}$, in which
case the intersection is ${\boldsymbol{\Delta}}^{\perp}$.)

######  Theorem 3.2.

With $\mathbf{y}$ and $\mathbf{e}$ as defined in 38 and 40 respectively, the
set of cycles is given by

$\displaystyle{\mathbf{Z}}$
$\displaystyle=N_{\mathbf{C}}^{-1}(\mathbf{y})\cap(\mathbf{e}+{\boldsymbol{\Delta}})$
(45a)
$\displaystyle=\mathbf{e}+\big{(}{\boldsymbol{\Delta}}\cap({\mathbf{C}}-\mathbf{e})\big{)}.$
(45b)

Proof. First,
${\mathbf{C}}\subseteq\overline{{\mathbf{C}}+{\boldsymbol{\Delta}}}$ because
$0\in{\boldsymbol{\Delta}}$. Hence $(\forall\mathbf{c}\in{\mathbf{C}})$
$\left\langle{\mathbf{y}},{\mathbf{c}-\mathbf{e}}\right\rangle\leq 0$ by 42.
It follows that

$\sigma_{{\mathbf{C}}}(\mathbf{y})\leq\left\langle{\mathbf{y}},{\mathbf{e}}\right\rangle=-\tfrac{1}{2}\|\mathbf{y}\|^{2},$
(46)

where the equality follows from 23 and 40.

Next, $\mathbf{y}$ might even solve the original dual 18 in which case
${\mathbf{Z}}$ is given by 20. Whether or not this is the case, we _always_
have, using 25, 40, and 39,

$\displaystyle
N_{\mathbf{C}}^{-1}(\mathbf{y})\cap-(\operatorname{Id}-{\mathbf{R}})^{-1}(\mathbf{y})$
$\displaystyle=N_{\mathbf{C}}^{-1}(\mathbf{y})\cap\big{(}-\tfrac{1}{2}\mathbf{y}-{\mathbf{T}}\mathbf{y}-N_{{\boldsymbol{\Delta}}^{\perp}}(\mathbf{y})\big{)}$
(47a)
$\displaystyle=N_{{\mathbf{C}}}^{-1}(\mathbf{y})\cap(\mathbf{e}+{\boldsymbol{\Delta}}).$
(47b)

Altogether, this yields 45a.

Now let $\mathbf{x}\in{\mathbf{X}}$ and set
$\mathbf{d}:=\mathbf{x}-\mathbf{e}$. Then, using 45a, 39, and 46, we have the
equivalences

$\displaystyle\mathbf{x}\in{\mathbf{Z}}$
$\displaystyle\Leftrightarrow\mathbf{x}\in
N_{\mathbf{C}}^{-1}(\mathbf{y})\cap(\mathbf{e}+{\boldsymbol{\Delta}})$ (48a)
$\displaystyle\Leftrightarrow\mathbf{y}\in
N_{\mathbf{C}}(\mathbf{x})\text{~{}and~{}}\mathbf{x}-\mathbf{e}\in{\boldsymbol{\Delta}}$
(48b) $\displaystyle\Leftrightarrow\mathbf{y}\in
N_{\mathbf{C}}(\mathbf{d}+\mathbf{e})\text{~{}and~{}}\mathbf{d}\in{\boldsymbol{\Delta}}$
(48c)
$\displaystyle\Leftrightarrow\mathbf{d}\in{\boldsymbol{\Delta}},\,\mathbf{d}+\mathbf{e}\in{\mathbf{C}},\text{~{}and~{}}(\forall\mathbf{c}\in{\mathbf{C}})\;\;\left\langle{\mathbf{y}},{\mathbf{c}-(\mathbf{d}+\mathbf{e})}\right\rangle\leq
0$ (48d)
$\displaystyle\Leftrightarrow\mathbf{d}\in{\boldsymbol{\Delta}},\,\mathbf{d}+\mathbf{e}\in{\mathbf{C}},\text{~{}and~{}}(\forall\mathbf{c}\in{\mathbf{C}})\;\;\left\langle{\mathbf{y}},{\mathbf{c}-\mathbf{e}}\right\rangle\leq
0$ (48e)
$\displaystyle\Leftrightarrow\mathbf{d}\in{\boldsymbol{\Delta}}\cap({\mathbf{C}}-\mathbf{e})\text{~{}and~{}}\sigma_{\mathbf{C}}(\mathbf{y})\leq\left\langle{\mathbf{y}},{\mathbf{e}}\right\rangle$
(48f)
$\displaystyle\Leftrightarrow\mathbf{x}-\mathbf{e}\in{\boldsymbol{\Delta}}\cap({\mathbf{C}}-\mathbf{e}),$
(48g)

and this gives 45b. $\hfill\quad\blacksquare$

######  Corollary 3.3.

The following hold:

  1. (i)

(orthogonal decomposition of ${\mathbf{Z}}$)
$P_{{\boldsymbol{\Delta}}^{\perp}}({\mathbf{Z}})\subseteq\\{\mathbf{e}\\}$ and
$P_{{\boldsymbol{\Delta}}}({\mathbf{Z}})={\boldsymbol{\Delta}}\cap({\mathbf{C}}-\mathbf{e})$.

  2. (ii)

${\mathbf{Z}}\neq\varnothing\Leftrightarrow\mathbf{e}\in{\mathbf{C}}+{\boldsymbol{\Delta}}$.

  3. (iii)

If $\mathbf{e}\in{\mathbf{C}}+{\boldsymbol{\Delta}}$, say
$\mathbf{e}=\mathbf{c}+\mathbf{d}$, where $\mathbf{c}\in{\mathbf{C}}$ and
$\mathbf{d}\in{\boldsymbol{\Delta}}$, then $\mathbf{c}\in{\mathbf{Z}}$.

  4. (iv)

If $\mathbf{z}\in{\mathbf{Z}}$, then
$\mathbf{e}=P_{{\boldsymbol{\Delta}}^{\perp}}\mathbf{z}\in({\mathbf{C}}+{\boldsymbol{\Delta}})\cap{\boldsymbol{\Delta}}^{\perp}$.

Proof. (i): Recall that $\mathbf{e}\in{\boldsymbol{\Delta}}^{\perp}$ by 40.
Clearly,
${\boldsymbol{\Delta}}\cap({\mathbf{C}}-\mathbf{e})\subseteq{\boldsymbol{\Delta}}$.
Using 45b, we obtain an orthogonal decomposition of ${\mathbf{Z}}$, with
${\boldsymbol{\Delta}}^{\perp}$ component
$P_{{\boldsymbol{\Delta}}^{\perp}}({\mathbf{Z}})\subseteq\\{\mathbf{e}\\}$ and
$P_{{\boldsymbol{\Delta}}}({\mathbf{Z}})={\boldsymbol{\Delta}}\cap({\mathbf{C}}-\mathbf{e})$.
(ii): Indeed, using 45b, we have ${\mathbf{Z}}\neq\varnothing$
$\Leftrightarrow$
${\boldsymbol{\Delta}}\cap({\mathbf{C}}-\mathbf{e})\neq\varnothing$
$\Leftrightarrow$ $(\exists\,\mathbf{c}\in{\mathbf{C}})$
$\mathbf{c}-\mathbf{e}\in{\boldsymbol{\Delta}}$ $\Leftrightarrow$
$\mathbf{e}\in{\mathbf{C}}+{\boldsymbol{\Delta}}$. (iii): Indeed,
$\mathbf{c}-\mathbf{e}=-\mathbf{d}\in({\boldsymbol{\Delta}}\cap({\mathbf{C}}-\mathbf{e}))$
and so
$\mathbf{c}\in\mathbf{e}+({\boldsymbol{\Delta}}\cap({\mathbf{C}}-\mathbf{e}))={\mathbf{Z}}$
using 45b. (iv): Using (i) and 40, we obtain
$\mathbf{e}=P_{{\boldsymbol{\Delta}}^{\perp}}\mathbf{z}=\mathbf{z}-P_{{\boldsymbol{\Delta}}}\mathbf{z}\in({\mathbf{Z}}-{\boldsymbol{\Delta}})\cap{\boldsymbol{\Delta}}^{\perp}\subseteq({\mathbf{C}}+{\boldsymbol{\Delta}})\cap{\boldsymbol{\Delta}}^{\perp}$.
$\hfill\quad\blacksquare$

At long last, we define

${\mathbf{v}}:={\mathbf{R}}^{*}\mathbf{e}-\mathbf{e}\in{\boldsymbol{\Delta}}^{\perp},$
(49)

where ${\mathbf{v}}\in{\boldsymbol{\Delta}}^{\perp}$ because
${\operatorname{ran}}\,(\operatorname{Id}-{\mathbf{R}}^{*})={\operatorname{ran}}\,(\operatorname{Id}-{\mathbf{R}})={\boldsymbol{\Delta}}^{\perp}$
by [12, Theorem 2.2(iv)]. Also 41 yields

${\mathbf{v}}={\mathbf{R}}^{*}\mathbf{e}-\mathbf{e}=-{\mathbf{R}}^{*}({\mathbf{R}}\mathbf{e}-\mathbf{e})=-{\mathbf{R}}^{*}\mathbf{y},$
(50)

which in turn gives

$\mathbf{y}=-{\mathbf{R}}{\mathbf{v}}.$ (51)

Because ${\mathbf{R}}^{*}$ is the circular _left_ shift, 49 and 51 yield

$\displaystyle{\mathbf{v}}$
$\displaystyle=(e_{2}-e_{1},e_{3}-e_{2},\ldots,e_{m}-e_{m-1},e_{1}-e_{m}),\text{where
$\mathbf{e}=(e_{1},\ldots,e_{m})$}$ (52a)
$\displaystyle=(-y_{2},-y_{3},\ldots,-y_{m-1},-y_{1}),\text{where
$\mathbf{y}=(y_{1},\ldots,y_{m})$.}$ (52b)

We are now ready for our main result.

######  Theorem 3.4.

(the geometry conjecture is true) The vector ${\mathbf{v}}$ defined in 49 (see
also 52) is the sought-after difference vector (see Section 1.2).

Proof. We must verify 5.

First, let $z_{m}\in F_{m}$. Then $z_{m}$ is the $m$th component of some cycle
$\mathbf{z}$. Obviously, $\mathbf{z}\in{\mathbf{C}}$. By 45b, there exists
$x\in X$ such that

$z_{1}=e_{1}+x,z_{2}=e_{2}+x,\ldots,z_{m-1}=e_{m-1}+x,z_{m}=e_{m}+x.$ (53)

Hence

$\displaystyle z_{m}$ $\displaystyle\in C_{m}$ (54a) $\displaystyle z_{m}$
$\displaystyle=e_{m}+x=(e_{m-1}+x)+(e_{m}-e_{m-1})=z_{m-1}+v_{m-1}\in
C_{m-1}+v_{m-1}$ (54b) $\displaystyle z_{m}$
$\displaystyle=(e_{m-2}+x)+(e_{m-1}-e_{m-2})+(e_{m}-e_{m-1})\in
C_{m-2}+v_{m-2}+v_{m-1}$ (54c) $\displaystyle\;\;\vdots$ (54d) $\displaystyle
z_{m}$ $\displaystyle\in C_{1}+v_{1}+v_{2}+\cdots+v_{m-1}.$ (54e)

We deduce that

$F_{m}\subseteq
C_{m}\cap(C_{m-1}+v_{m-1})\cap\cdots\cap(C_{1}+v_{1}+\cdots+v_{m-1}).$ (55)

We now tackle the converse inclusion. Let

$c_{m}\in
C_{m}\cap(C_{m-1}+v_{m-1})\cap\cdots\cap(C_{1}+v_{1}+\cdots+v_{m-1}).$ (56)

So there exist $c_{1}\in C_{1},\ldots,c_{m}\in C_{m}$ such that

$\displaystyle c_{m}$ $\displaystyle=c_{m-1}+v_{m-1}$ (57a)
$\displaystyle=c_{m-2}+v_{m-2}+v_{m-1}$ (57b) $\displaystyle\;\;\vdots$ (57c)
$\displaystyle=c_{2}+v_{2}+\cdots+v_{m-1}$ (57d)
$\displaystyle=c_{1}+v_{1}+v_{2}+\cdots+v_{m-1}.$ (57e)

It follows that $c_{m-1}=c_{m-2}+v_{m-2}$, $\ldots$, $c_{2}=c_{1}+v_{1}$, and
$c_{1}=c_{m}+v_{m}$ (because $c_{m}=c_{1}+v_{1}+v_{2}+\cdots
v_{m-1}=c_{1}-v_{m}$). Setting $\mathbf{c}:=(c_{1},\ldots,c_{m})$, we rewrite
this as $\mathbf{c}={\mathbf{R}}\mathbf{c}+{\mathbf{R}}{\mathbf{v}}$. Using
49,
$\mathbf{c}={\mathbf{R}}\mathbf{c}+{\mathbf{R}}({\mathbf{R}}^{*}\mathbf{e}-\mathbf{e})={\mathbf{R}}\mathbf{c}+\mathbf{e}-{\mathbf{R}}\mathbf{e}$.
Hence $(\operatorname{Id}-{\mathbf{R}})(\mathbf{c}-\mathbf{e})=0$ and thus
$\mathbf{c}-\mathbf{e}\in\ker(\operatorname{Id}-{\mathbf{R}})={\boldsymbol{\Delta}}$.
It follows that
$\mathbf{c}-\mathbf{e}\in{\boldsymbol{\Delta}}\cap({\mathbf{C}}-\mathbf{e})$
and now 45b yields

$\mathbf{c}=\mathbf{e}+(\mathbf{c}-\mathbf{e})\in\mathbf{e}+\big{(}{\boldsymbol{\Delta}}\cap({\mathbf{C}}-\mathbf{e})\big{)}={\mathbf{Z}}.$
(58)

Therefore,

$c_{m}\in F_{m}$ (59)

which completes the proof of the geometry conjecture!
$\hfill\quad\blacksquare$

##  4 The case when $m=2$

Throughout this section, we assume that $m=2$.

###  4.1 Revisiting known results

It is instructive to revisit this case even if we know the answer already;
moreover, we will discover a new formula for the difference vector
${\mathbf{v}}$. By 14 and 22, ${\mathbf{R}}^{*}={\mathbf{R}}$ and
${\mathbf{T}}=0$. Hence 38 turns into
$0\in\tfrac{1}{2}\mathbf{y}+\partial\sigma_{{\mathbf{C}}+{\boldsymbol{\Delta}}}(\mathbf{y})$
$\Leftrightarrow$
$0\in\tfrac{1}{2}\mathbf{y}+N_{\overline{{\mathbf{C}}+{\boldsymbol{\Delta}}}}^{-1}(\mathbf{y})$
$\Leftrightarrow$ $-\tfrac{1}{2}\mathbf{y}\in
N_{\overline{{\mathbf{C}}+{\boldsymbol{\Delta}}}}^{-1}(\mathbf{y})$
$\Leftrightarrow$ $\mathbf{y}\in
N_{\overline{{\mathbf{C}}+{\boldsymbol{\Delta}}}}(-\tfrac{1}{2}\mathbf{y})$
$\Leftrightarrow$
$\tfrac{1}{2}\mathbf{y}\in(\operatorname{Id}+N_{\overline{{\mathbf{C}}+{\boldsymbol{\Delta}}}})(-\tfrac{1}{2}\mathbf{y})$
$\Leftrightarrow$
$-\tfrac{1}{2}\mathbf{y}=P_{\overline{{\mathbf{C}}+{\boldsymbol{\Delta}}}}(\tfrac{1}{2}\mathbf{y})$
$\Leftrightarrow$
[$-\tfrac{1}{2}\mathbf{y}\in\overline{{\mathbf{C}}+{\boldsymbol{\Delta}}}$ and
$(\forall(\mathbf{c},\mathbf{d})\in{\mathbf{C}}\times{\boldsymbol{\Delta}})$
$\langle{\mathbf{c}+\mathbf{d}-(-\tfrac{1}{2}\mathbf{y})},{\tfrac{1}{2}\mathbf{y}-(-\tfrac{1}{2}\mathbf{y})}\rangle\leq
0$ ] $\Leftrightarrow$ [$\mathbf{y}\in
2\overline{({\boldsymbol{\Delta}}-{\mathbf{C}})}$ and
$(\forall(\mathbf{c},\mathbf{d})\in{\mathbf{C}}\times{\boldsymbol{\Delta}})$
$\langle{2(\mathbf{d}-\mathbf{c})-\mathbf{y})},{0-\mathbf{y}}\rangle\leq 0$ ]
$\Leftrightarrow$

$\mathbf{y}=P_{2\overline{({\boldsymbol{\Delta}}-{\mathbf{C}})}}(0).$ (60)

By 40,

$\mathbf{e}=-\tfrac{1}{2}\mathbf{y}-0\mathbf{y}=-\tfrac{1}{2}P_{2\overline{({\boldsymbol{\Delta}}-{\mathbf{C}})}}(0)=P_{-\overline{({\boldsymbol{\Delta}}-{\mathbf{C}})}}(0)=P_{\overline{{\mathbf{C}}+{\boldsymbol{\Delta}}}}(0).$
(61)

Finally, by 49,

${\mathbf{v}}=-{\mathbf{R}}^{*}\mathbf{y}=-{\mathbf{R}}\mathbf{y}.$ (62)

We now express these quantities also in the underlying space $X$. We claim
that

$\mathbf{y}\overset{?}{=}\big{(}P_{\overline{C_{2}-C_{1}}}(0),P_{\overline{C_{1}-C_{2}}}(0)\big{)}{=}\big{(}P_{\overline{C_{2}-C_{1}}}(0),-P_{\overline{C_{2}-C_{1}}}(0)\big{)}.$
(63)

Set $y:=P_{\overline{C_{2}-C_{1}}}(0)$. Then $y\leftarrow c_{2,n}-c_{1,n}$,
where $(c_{1,n},c_{2,n})_{n\in{\mathbb{N}}}$ is a sequence in $C_{1}\times
C_{2}$. Now for every ${n\in{\mathbb{N}}}$,
$c_{2,n}-c_{1,n}=2(\tfrac{1}{2}(c_{1,n}+c_{2,n})-c_{1,n})$ and
$c_{1,n}-c_{2,n}=2(\tfrac{1}{2}(c_{1,n}+c_{2,n})-c_{2,n})$, so

$\big{(}c_{2,n}-c_{1,n},c_{1,n}-c_{2,n}\big{)}\in
2({\boldsymbol{\Delta}}-{\mathbf{C}})$ (64)

which implies $(y,-y)\in 2\overline{({\boldsymbol{\Delta}}-{\mathbf{C}})}$.
Next, let us take
$(\mathbf{c},\mathbf{d})\in{\mathbf{C}}\times{\boldsymbol{\Delta}}$, say
$\mathbf{c}=(c_{1},c_{2})\in C_{1}\times C_{2}$ and $\mathbf{d}=(x,x)$ for
some $x\in X$. Then

$\displaystyle\left\langle{2(\mathbf{d}-\mathbf{c})-(y,-y)},{{\boldsymbol{0}}-(y,-y)}\right\rangle$
$\displaystyle=\left\langle{2(x-c_{1},x-c_{2})-(y,-y)},{(-y,y)}\right\rangle$
(65a)
$\displaystyle=\left\langle{(2x-2c_{1}-y,2x-2c_{2}+y)},{(-y,y)}\right\rangle$
(65b)
$\displaystyle=\left\langle{2x-2c_{1}-y},{-y}\right\rangle+\left\langle{2x-2c_{2}+y},{y}\right\rangle$
(65c) $\displaystyle=\left\langle{2c_{2}-2c_{1}-2y},{-y}\right\rangle$ (65d)
$\displaystyle=2\left\langle{(c_{2}-c_{1})-y},{0-y}\right\rangle$ (65e)
$\displaystyle\leq 0$ (65f)

by definition of $y$. We have verified

$\mathbf{y}=\big{(}P_{\overline{C_{2}-C_{1}}}(0),P_{\overline{C_{1}-C_{2}}}(0)\big{)}.$
(66)

It follows (by 61 and 66) that

$\mathbf{e}=-\tfrac{1}{2}\mathbf{y}=-\tfrac{1}{2}\big{(}P_{\overline{C_{2}-C_{1}}}(0),P_{\overline{C_{1}-C_{2}}}(0)\big{)}=\tfrac{1}{2}\big{(}P_{\overline{C_{1}-C_{2}}}(0),P_{\overline{C_{2}-C_{1}}}(0)\big{)}$
(67)

and (by 62 and 66)

${\mathbf{v}}=-{\mathbf{R}}\mathbf{y}=-\big{(}P_{\overline{C_{1}-C_{2}}}(0),P_{\overline{C_{2}-C_{1}}}(0)\big{)}=\big{(}P_{\overline{C_{2}-C_{1}}}(0),P_{\overline{C_{1}-C_{2}}}(0)\big{)}=\mathbf{y}.$
(68)

Hence

$v_{1}=P_{\overline{C_{2}-C_{1}}}(0)\;\;\text{and}\;\;v_{2}=P_{\overline{C_{1}-C_{2}}}(0)=-v_{1}$
(69)

and this is completely consistent with the known theory exposed in Section 1.2
(see 7)! Along our journey, we have thus discovered a new identity for
${\mathbf{v}}$ by combining 60 with 68 which we record in the following
result.

######  Proposition 4.1.

${\mathbf{v}}=\big{(}P_{\overline{C_{2}-C_{1}}}(0),P_{\overline{C_{1}-C_{2}}}(0)\big{)}=P_{2\overline{{\boldsymbol{\Delta}}-{\mathbf{C}}}}(0)=2P_{\overline{{\boldsymbol{\Delta}}-{\mathbf{C}}}}(0)$.

###  4.2 Two lines

It is instructive to consider two general lines in $X$, given by

$C_{1}=c_{1}+\mathbb{R}u_{1},\;C_{2}=c_{2}+\mathbb{R}u_{2},\quad\text{where}\;\;c_{1}\perp
u_{1},\;c_{2}\perp u_{2},\;\text{and}\;\|u_{1}\|=\|u_{2}\|=1$ (70)

because we will obtain descriptions of ${\mathbf{Z}}$, ${\mathbf{v}}$,
$\mathbf{y}$, and $\mathbf{e}$. We start by noting that for every
$i\in\\{1,2\\}$,

$(\forall x\in X)\;\;P_{i}(x)=c_{i}+\left\langle{u_{i}},{x}\right\rangle
u_{i}.$ (71)

Let $\mathbf{z}=(z_{1},z_{2})\in C_{1}\times C_{2}$. Then
$z_{1}=c_{1}+\rho_{1}u_{1}$ and $z_{2}=c_{2}+\rho_{2}u_{2}$ for some
$\rho_{1},\rho_{2}$ in $\mathbb{R}$. Now assume that $\mathbf{z}$ is actually
a cycle. Then $z_{2}=P_{2}P_{1}z_{2}$, i.e.,

$\displaystyle c_{2}+\rho_{2}u_{2}$ $\displaystyle=z_{2}$ (72a)
$\displaystyle=P_{2}P_{1}z_{2}$ (72b)
$\displaystyle=c_{2}+\left\langle{u_{2}},{P_{1}z_{2}}\right\rangle u_{2}$
(72c)
$\displaystyle=c_{2}+\left\langle{u_{2}},{c_{1}+\left\langle{u_{1}},{z_{2}}\right\rangle
u_{1}}\right\rangle u_{2}$ (72d)
$\displaystyle=c_{2}+\big{(}\left\langle{u_{2}},{c_{1}}\right\rangle+\left\langle{u_{1}},{z_{2}}\right\rangle\left\langle{u_{2}},{u_{1}}\right\rangle\big{)}u_{2}$
(72e)
$\displaystyle=c_{2}+\big{(}\left\langle{u_{2}},{c_{1}}\right\rangle+\left\langle{u_{1}},{c_{2}+\rho_{2}u_{2}}\right\rangle\left\langle{u_{2}},{u_{1}}\right\rangle\big{)}u_{2}$
(72f)
$\displaystyle=c_{2}+\big{(}\left\langle{u_{2}},{c_{1}}\right\rangle+\left\langle{u_{1}},{c_{2}}\right\rangle\left\langle{u_{2}},{u_{1}}\right\rangle+\rho_{2}\left\langle{u_{1}},{u_{2}}\right\rangle\left\langle{u_{2}},{u_{1}}\right\rangle\big{)}u_{2};$
(72g)

equivalently,

$\rho_{2}\big{(}1-\left\langle{u_{1}},{u_{2}}\right\rangle^{2}\big{)}=\left\langle{c_{1}},{u_{2}}\right\rangle+\left\langle{u_{1}},{u_{2}}\right\rangle\left\langle{u_{1}},{c_{2}}\right\rangle.$
(73)

The theory bifurcates from here as we will see in the following subsections.

####  4.2.1 The lines are parallel

Let’s first assume that the two lines $C_{1},C_{2}$ are parallel;
equivalently, $\left\langle{u_{1}},{u_{2}}\right\rangle^{2}=1$. Without loss
of generality, $u_{2}=u_{1}=:u$. Then _every_ $\rho_{2}$ in $\mathbb{R}$
solves 73. It then follows that the set of cycles is

${\mathbf{Z}}=(c_{1},c_{2})+\mathbb{R}(u,u).$ (74)

Moreover, using 6, 68, and 67, we obtain

${\mathbf{v}}=(c_{2}-c_{1},c_{1}-c_{2})=\mathbf{y}\;\;\text{and}\;\;\mathbf{e}=\tfrac{1}{2}(c_{1}-c_{2},c_{2}-c_{1}).$
(75)

####  4.2.2 The lines are not parallel

Now we assume that $C_{1},C_{2}$ are not parallel. Then
$\left\langle{u_{1}},{u_{2}}\right\rangle^{2}<1$ and solving 73 for $\rho_{2}$
yields

$\rho_{2}:=\frac{\left\langle{u_{2}},{c_{1}}\right\rangle+\left\langle{u_{1}},{u_{2}}\right\rangle\left\langle{u_{1}},{c_{2}}\right\rangle}{1-\left\langle{u_{1}},{u_{2}}\right\rangle^{2}}$
(76)

and analogously

$\rho_{1}:=\frac{\left\langle{u_{1}},{c_{2}}\right\rangle+\left\langle{u_{1}},{u_{2}}\right\rangle\left\langle{u_{2}},{c_{1}}\right\rangle}{1-\left\langle{u_{1}},{u_{2}}\right\rangle^{2}}.$
(77)

Hence the set of cycles ${\mathbf{Z}}$ has only one element, namely

$\mathbf{z}=(z_{1},z_{2})=(c_{1}+\rho_{1}u_{1},c_{2}+\rho_{2}u_{2});$ (78)

and ${\mathbf{v}}=(z_{2}-z_{1},z_{1}-z_{2})=\mathbf{y}$ and
$\mathbf{e}=-\tfrac{1}{2}{\mathbf{v}}$ which we don’t expand as the
expressions don’t simplify.

##  5 The case when $m=3$

Throughout this section, we assume that $m=3$. Then the matrix representations
for ${\mathbf{T}}$ (see 22) is

${\mathbf{T}}=\frac{1}{6}\begin{pmatrix}0&0&1\\\ 1&0&0\\\
0&1&0\end{pmatrix}-\frac{1}{6}\begin{pmatrix}0&1&0\\\ 0&0&1\\\
1&0&0\end{pmatrix}=\frac{1}{6}\begin{pmatrix}[r]0&-1&1\\\ 1&0&-1\\\
-1&1&0\end{pmatrix}$ (79)

and thus

$-\tfrac{1}{2}\operatorname{Id}-{\mathbf{T}}=\frac{1}{6}\begin{pmatrix}[r]-3&1&-1\\\
-1&-3&1\\\ 1&-1&-3\end{pmatrix}.$ (80)

Thanks to 80, Proposition 3.1, 40, and 52, we obtain the following result:

######  Theorem 5.1.

Let $\mathbf{y}=(y_{1},y_{2},y_{3})\in{\mathbf{X}}=X^{3}$. Then $\mathbf{y}$
is the unique solution of 38 if and only if all of the following hold:

$y_{1}+y_{2}+y_{3}=0,$ (81)

there exist sequences $(c_{1,n})_{n\in{\mathbb{N}}}$ in $C_{1}$,
$(c_{2,n})_{n\in{\mathbb{N}}}$ in $C_{2}$, $(c_{3,n})_{n\in{\mathbb{N}}}$ in
$C_{3}$, and $(x_{n})_{n\in{\mathbb{N}}}$ in $X$ such that

$\displaystyle c_{1,n}+x_{n}$
$\displaystyle\to\tfrac{1}{6}\big{(}-3y_{1}+y_{2}-y_{3}\big{)},$ (82a)
$\displaystyle c_{2,n}+x_{n}$
$\displaystyle\to\tfrac{1}{6}\big{(}-y_{1}-3y_{2}+y_{3}\big{)},$ (82b)
$\displaystyle c_{3,n}+x_{n}$
$\displaystyle\to\tfrac{1}{6}\big{(}y_{1}-y_{2}-3y_{3}\big{)},$ (82c)

and $(\forall(c_{1},c_{2},c_{3})\in C_{1}\times C_{2}\times C_{3})$

$\left\langle{y_{1}},{c_{1}}\right\rangle+\left\langle{y_{2}},{c_{2}}\right\rangle+\left\langle{y_{3}},{c_{3}}\right\rangle\leq-\tfrac{1}{2}\big{(}\|y_{1}\|^{2}+\|y_{2}\|^{2}+\|y_{3}\|^{2}\big{)}.$
(83)

If $\mathbf{y}=(y_{1},y_{2},y_{3})$ satisfies all these conditions, then

$\mathbf{e}=(e_{1},e_{2},e_{3})=\tfrac{1}{6}\big{(}-3y_{1}+y_{2}-y_{3},-y_{1}-3y_{2}+y_{3},y_{1}-y_{3}-3y_{3}\big{)}$
(84)

and

${\mathbf{v}}=-(y_{2},y_{3},y_{1})$ (85)

are the vectors from 40 and 49, respectively.

Note that if ${\mathbf{v}}=(v_{1},v_{2},v_{3})$, then we can obtain
$\mathbf{y}$ through 51:

$\mathbf{y}=-{\mathbf{R}}{\mathbf{v}}=-(v_{3},v_{1},v_{2}).$ (86)

Moreover, if desired, we can find $\mathbf{e}$ by combining 40 and 79.

###  5.1 Three lines

Let us consider three lines, which can be treated similar to two lines (see
Section 4.2). (For brevity, we will omit full details on the somewhat tedious
algebraic manipulations.) We assume that

$C_{1}=c_{1}+\mathbb{R}u_{1},\;C_{2}=c_{2}+\mathbb{R}u_{2},\;C_{3}=c_{3}+\mathbb{R}u_{3},$
(87)

where

$c_{1}\perp u_{1},\;c_{2}\perp u_{2},\;c_{3}\perp
u_{3}\;\;\text{and}\;\;\|u_{1}\|=\|u_{2}\|=\|u_{3}\|=1.$ (88)

####  5.1.1 All three lines are parallel

Let’s first assume that all lines are parallel; equivalently,
$\left\langle{u_{3}},{u_{2}}\right\rangle\left\langle{u_{2}},{u_{1}}\right\rangle\left\langle{u_{1}},{u_{3}}\right\rangle=1$.
Without loss of generality, $u:=u_{1}=u_{2}=u_{3}$. Then the set of cycles is

${\mathbf{Z}}=(c_{1},c_{2},c_{3})+\mathbb{R}(u,u,u)$ (89)

and thus the difference vector is

${\mathbf{v}}=(c_{2}-c_{1},c_{3}-c_{2},c_{1}-c_{3}).$ (90)

In Figure 1, we visualize this case for three lines in $\mathbb{R}^{3}$.

Figure 1: Visualization of the cycles and the difference vectors for three
parallel lines in $\mathbb{R}^{3}$. See Section 5.1.1 for details.

####  5.1.2 Not all three lines are parallel

The case when not all lines are parallel corresponds to
$\left\langle{u_{3}},{u_{2}}\right\rangle\left\langle{u_{2}},{u_{1}}\right\rangle\left\langle{u_{1}},{u_{3}}\right\rangle<1$.
Then the set of cycles ${\mathbf{Z}}$ consists is a singleton containing

$\mathbf{z}=(z_{1},z_{2},z_{3})=(c_{1}+\rho_{1}u_{1},c_{2}+\rho_{2}u_{2},c_{3}+\rho_{3}u_{3}),$
(91)

where

$\displaystyle\rho_{1}$
$\displaystyle:=\frac{\left\langle{u_{1}},{c_{3}}\right\rangle+\left\langle{u_{1}},{u_{3}}\right\rangle\left\langle{u_{3}},{c_{2}}\right\rangle+\left\langle{u_{1}},{u_{3}}\right\rangle\left\langle{u_{3}},{u_{2}}\right\rangle\left\langle{u_{2}},{c_{1}}\right\rangle}{1-\left\langle{u_{3}},{u_{2}}\right\rangle\left\langle{u_{2}},{u_{1}}\right\rangle\left\langle{u_{1}},{u_{3}}\right\rangle},$
(92a) $\displaystyle\rho_{2}$
$\displaystyle:=\frac{\left\langle{u_{2}},{c_{1}}\right\rangle+\left\langle{u_{2}},{u_{1}}\right\rangle\left\langle{u_{1}},{c_{3}}\right\rangle+\left\langle{u_{2}},{u_{1}}\right\rangle\left\langle{u_{1}},{u_{3}}\right\rangle\left\langle{u_{3}},{c_{2}}\right\rangle}{1-\left\langle{u_{3}},{u_{2}}\right\rangle\left\langle{u_{2}},{u_{1}}\right\rangle\left\langle{u_{1}},{u_{3}}\right\rangle},$
(92b) $\displaystyle\rho_{3}$
$\displaystyle:=\frac{\left\langle{u_{3}},{c_{2}}\right\rangle+\left\langle{u_{3}},{u_{2}}\right\rangle\left\langle{u_{2}},{c_{1}}\right\rangle+\left\langle{u_{3}},{u_{2}}\right\rangle\left\langle{u_{2}},{u_{1}}\right\rangle\left\langle{u_{1}},{c_{3}}\right\rangle}{1-\left\langle{u_{3}},{u_{2}}\right\rangle\left\langle{u_{2}},{u_{1}}\right\rangle\left\langle{u_{1}},{u_{3}}\right\rangle},$
(92c)

and

${\mathbf{v}}=(z_{2}-z_{1},z_{3}-z_{2},z_{1}-z_{3}).$ (93)

In Figure 2, we visualize this case for three lines in $\mathbb{R}^{3}$.

Figure 2: Visualization of the cycle and the difference vectors for three
lines in $\mathbb{R}^{3}$ that are not parallel. See Section 5.1.2 for
details.

###  5.2 An example featuring the epigraph of the exponential function

In this section, we specialize further to

$X=\mathbb{R}^{2}.$ (94)

Inspired by [20, Section 3], we will present three sets in the Euclidean plane
and consider two different orderings. The sets are the epigraph of the
exponential function,

$\operatorname{epi}(\exp)=\big{\\{}{(\xi,\eta)\in\mathbb{R}^{2}}~{}\big{|}~{}{\exp(\xi)\leq\eta}\big{\\}}=\operatorname{gra}(\exp)+(\\{0\\}\times\mathbb{R}),$
(95)

along with the two horizontal lines

$\mathbb{R}\times\\{0\\}\;\;\text{and}\;\;\mathbb{R}\times\\{1\\}.$ (96)

In the following we describe two orderings, one leading to the presence of
cycles, the other to their absence. The case when there are cycles is depicted
in Figure 3.

Figure 3: Visualization of the case of two lines and the epigraph of the
exponential function where there are cycles. See Section 5.2 for details.

####  5.2.1 An ordering with cycles

In this section, we assume that

$C_{1}=\mathbb{R}\times\\{0\\},\;\;C_{2}=\mathbb{R}\times\\{1\\},\;\;C_{3}=\operatorname{epi}(\exp).$
(97)

Now set

$\mathbf{y}=(y_{1},y_{2},y_{3})=\big{(}(0,1),(0,-1),(0,0)\big{)}.$ (98)

We claim that 98 satisfies the characterization provided by Theorem 5.1.

Clearly, $y_{1}+y_{2}+y_{3}=(0+0+0,1-1+0)=(0,0)$ and so 81 holds.

Next, set $c_{1,n}\equiv(0,0)\in C_{1}$, $c_{2,n}\equiv(0,1)\in C_{2}$,
$c_{3,n}\equiv(0,1)=(0,\exp(0))\in C_{3}$, and
$x_{n}\equiv(0,-\tfrac{2}{3})\in X$. Then

$\displaystyle c_{1,n}+x_{n}$
$\displaystyle\equiv(0,-\tfrac{2}{3})=\tfrac{1}{6}\big{(}-3(0,1)+(0,-1)-(0,0)\big{)}=\tfrac{1}{6}\big{(}-3y_{1}+y_{2}-y_{3}\big{)},$
(99a) $\displaystyle c_{2,n}+x_{n}$
$\displaystyle\equiv(0,\tfrac{1}{3})=\tfrac{1}{6}\big{(}-(0,1)-3(0,-1)+(0,0)\big{)}=\tfrac{1}{6}\big{(}-y_{1}-3y_{2}+y_{3}\big{)},$
(99b) $\displaystyle c_{3,n}+x_{n}$
$\displaystyle\equiv(0,\tfrac{1}{3})=\tfrac{1}{6}\big{(}(0,1)-(0,-1)-3(0,0)\big{)}=\tfrac{1}{6}\big{(}y_{1}-y_{2}-3y_{3}\big{)},$
(99c)

and thus 82 holds.

Now let $c_{1}=(\gamma_{1},0)\in C_{1}$, $c_{2}=(\gamma_{2},1)\in C_{2}$, and
$c_{3}=(\gamma_{3},\exp(\gamma_{3})+\delta_{3})\in C_{3}$, where
$\\{\gamma_{1},\gamma_{2},\gamma_{3}\\}\subseteq\mathbb{R}$, and
$\delta_{3}\in\mathbb{R}_{+}$. Then

$\displaystyle\left\langle{y_{1}},{c_{1}}\right\rangle+\left\langle{y_{2}},{c_{2}}\right\rangle+\left\langle{y_{3}},{c_{3}}\right\rangle$
(100a)
$\displaystyle=\left\langle{(0,1)},{(\gamma_{1},0)}\right\rangle+\left\langle{(0,-1)},{(\gamma_{2},1)}\right\rangle+\left\langle{(0,0)},{(\gamma_{3},\exp(\gamma_{3})+\delta_{3})}\right\rangle$
(100b) $\displaystyle=-1$ (100c)
$\displaystyle=-\tfrac{1}{2}\big{(}1+1+0\big{)}$ (100d)
$\displaystyle=-\tfrac{1}{2}\big{(}\|(0,1)\|^{2}+\|(0,-1)\|^{2}+\|(0,0)\|^{2}\big{)}$
(100e)
$\displaystyle=-\tfrac{1}{2}\big{(}\|y_{1}\|^{2}+\|y_{2}\|^{2}+\|y_{3}\|^{2}\big{)}.$
(100f)

and thus 83 holds (even with equality).

Next, using 84 and 85, we obtain

$\displaystyle\mathbf{e}$
$\displaystyle=(e_{1},e_{2},e_{3})=\big{(}(0,-\tfrac{2}{3}),(0,\tfrac{1}{3}),(0,\tfrac{1}{3})\big{)}$
(101a) $\displaystyle{\mathbf{v}}$
$\displaystyle=(v_{1},v_{2},v_{3})=\big{(}(0,1),(0,0),(0,-1)\big{)}.$ (101b)

The vector ${\mathbf{v}}$ allows us to find the fixed point sets
$F_{1},F_{2},F_{3}$ (see 3) via Theorem 3.4. For instance,

$\displaystyle F_{3}$
$\displaystyle=C_{3}\cap(C_{2}+v_{2})\cap(C_{1}+v_{1}+v_{2})$ (102)
$\displaystyle=\operatorname{epi}(\exp)\cap(\mathbb{R}\times\\{1\\}+(0,0))\cap(\mathbb{R}\times\\{0\\}+(0,1))$
(103)
$\displaystyle=\operatorname{epi}(\exp)\cap(\mathbb{R}\times\\{1\\})\cap(\mathbb{R}\times\\{1\\})$
(104) $\displaystyle=\mathbb{R}_{-}\times\\{1\\},$ (105)

which can also be seen geometrically.

####  5.2.2 An ordering without cycles

In this section, we assume that

$C_{1}=\mathbb{R}\times\\{1\\},\;\;C_{2}=\mathbb{R}\times\\{0\\},\;\;C_{3}=\operatorname{epi}(\exp),$
(106)

which is nearly the same set up as in the last — the crucial difference is
that $C_{1}$ and $C_{2}$ were interchanged! Now set

$\mathbf{y}=(y_{1},y_{2},y_{3})=\big{(}(0,-1),(0,1),(0,0)\big{)}.$ (107)

We claim that 107 satisfies the characterization provided by Theorem 5.1.

Clearly, $y_{1}+y_{2}+y_{3}=(0+0+0,-1+1+0)=(0,0)$ and so 81 holds.

Next, set $(\forall{n\in{\mathbb{N}}})$ $c_{1,n}=(-n,1)\in C_{1}$,
$c_{2,n}=(-n,0)\in C_{2}$, $c_{3,n}=(-n,\exp(-n)\in C_{3}$, and
$x_{n}=(n,-\tfrac{1}{3})\in X$. Then

$\displaystyle c_{1,n}+x_{n}$
$\displaystyle\equiv(0,\tfrac{2}{3})=\tfrac{1}{6}\big{(}-3(0,-1)+(0,1)-(0,0)\big{)}=\tfrac{1}{6}\big{(}-3y_{1}+y_{2}-y_{3}\big{)},$
(108a) $\displaystyle c_{2,n}+x_{n}$
$\displaystyle\equiv(0,-\tfrac{1}{3})=\tfrac{1}{6}\big{(}-(0,-1)-3(0,1)+(0,0)\big{)}=\tfrac{1}{6}\big{(}-y_{1}-3y_{2}+y_{3}\big{)},$
(108b) $\displaystyle c_{3,n}+x_{n}$ $\displaystyle=(0,\exp(-n)-\tfrac{1}{3})$
$\displaystyle\to(0,-\tfrac{1}{3})=\tfrac{1}{6}\big{(}(0,-1)-(0,1)-3(0,0)\big{)}=\tfrac{1}{6}\big{(}y_{1}-y_{2}-3y_{3}\big{)},$
(108c)

and thus 82 holds.

Now let $c_{1}=(\gamma_{1},1)\in C_{1}$, $c_{2}=(\gamma_{2},0)\in C_{2}$, and
$c_{3}=(\gamma_{3},\exp(\gamma_{3})+\delta_{3})\in C_{3}$, where
$\\{\gamma_{1},\gamma_{2},\gamma_{3}\\}\subseteq\mathbb{R}$, and
$\delta_{3}\in\mathbb{R}_{+}$. Then

$\displaystyle\left\langle{y_{1}},{c_{1}}\right\rangle+\left\langle{y_{2}},{c_{2}}\right\rangle+\left\langle{y_{3}},{c_{3}}\right\rangle$
(109a)
$\displaystyle=\left\langle{(0,-1)},{(\gamma_{1},1)}\right\rangle+\left\langle{(0,1)},{(\gamma_{2},0)}\right\rangle+\left\langle{(0,0)},{(\gamma_{3},\exp(\gamma_{3})+\delta_{3})}\right\rangle$
(109b) $\displaystyle=-1$ (109c)
$\displaystyle=-\tfrac{1}{2}\big{(}1+1+0\big{)}$ (109d)
$\displaystyle=-\tfrac{1}{2}\big{(}\|(0,-1)\|^{2}+\|(0,1)\|^{2}+\|(0,0)\|^{2}\big{)}$
(109e)
$\displaystyle=-\tfrac{1}{2}\big{(}\|y_{1}\|^{2}+\|y_{2}\|^{2}+\|y_{3}\|^{2}\big{)}.$
(109f)

and thus 83 holds (again with equality).

Next, using 84 and 85, we obtain

$\displaystyle\mathbf{e}$
$\displaystyle=(e_{1},e_{2},e_{3})=\big{(}(0,\tfrac{2}{3}),(0,-\tfrac{1}{3}),(0,-\tfrac{1}{3})\big{)}$
(110a) $\displaystyle{\mathbf{v}}$
$\displaystyle=(v_{1},v_{2},v_{3})=\big{(}(0,-1),(0,0),(0,1)\big{)}.$ (110b)

The vector ${\mathbf{v}}$ allows us to find the fixed point sets
$F_{1},F_{2},F_{3}$ (see 3) via Theorem 3.4. For instance,

$\displaystyle F_{3}$
$\displaystyle=C_{3}\cap(C_{2}+v_{2})\cap(C_{1}+v_{1}+v_{2})$ (111)
$\displaystyle=\operatorname{epi}(\exp)\cap(\mathbb{R}\times\\{0\\}+(0,0))\cap(\mathbb{R}\times\\{1\\}+(0,-1))$
(112)
$\displaystyle=\operatorname{epi}(\exp)\cap(\mathbb{R}\times\\{0\\})\cap(\mathbb{R}\times\\{0\\})$
(113) $\displaystyle=\varnothing,$ (114)

which again can also be seen geometrically.

##  6 Finding the difference vectors for $m\leq 5$ by Banach

In this section, we discuss an iterative technique to compute $\mathbf{y}$
(given by 38) which can be used to obtain the difference vector ${\mathbf{v}}$
via 52. Note that 38 is equivalent to

$-\tfrac{1}{2}\mathbf{y}-{\mathbf{T}}\mathbf{y}\in
N_{\overline{{\mathbf{C}}+{\boldsymbol{\Delta}}}}^{-1}(\mathbf{y}).$ (115)

In this section, let us abbreviate

${\mathbf{P}}:=P_{\overline{{\mathbf{C}}+{\boldsymbol{\Delta}}}},$ (116)

which is a projector and hence _firmly nonexpansive_. It follows that
$\operatorname{Id}-{\mathbf{P}}$ is also firmly nonexpansive, hence
_nonexpansive_ ($1$-Lipschitz continuous). This allows us to rewrite 115 as
$\mathbf{y}\in
N_{\overline{{\mathbf{C}}+{\boldsymbol{\Delta}}}}(-\tfrac{1}{2}\mathbf{y}-{\mathbf{T}}\mathbf{y})$
$\Leftrightarrow$
$\mathbf{y}+(-\tfrac{1}{2}\mathbf{y}-{\mathbf{T}}\mathbf{y})\in(\operatorname{Id}+N_{\overline{{\mathbf{C}}+{\boldsymbol{\Delta}}}})(-\tfrac{1}{2}\mathbf{y}-{\mathbf{T}}\mathbf{y})$
$\Leftrightarrow$
$-\tfrac{1}{2}\mathbf{y}-{\mathbf{T}}\mathbf{y}={\mathbf{P}}(\tfrac{1}{2}\mathbf{y}-{\mathbf{T}}\mathbf{y})$
$\Leftrightarrow$
$(\tfrac{1}{2}\mathbf{y}-{\mathbf{T}}\mathbf{y})-\mathbf{y}={\mathbf{P}}(\tfrac{1}{2}\mathbf{y}-{\mathbf{T}}\mathbf{y})$
$\Leftrightarrow$

$(\operatorname{Id}-{\mathbf{P}})(\tfrac{1}{2}\mathbf{y}-{\mathbf{T}}\mathbf{y})=\mathbf{y}.$
(117)

Because we know already that $\operatorname{Id}-{\mathbf{P}}$ is nonexpansive,
we can solve 117 by the Banach contraction principle as long as the inner
operator

$\tfrac{1}{2}\operatorname{Id}-{\mathbf{T}}$ (118)

is a nice Banach contraction, i.e., Lipschitz continuous with a constant
strictly less than $1$! We can determine the operator norm of 118 by analyzing
the corresponding matrix in $\mathbb{R}^{m\times m}$. Recall that the singular
values are the square roots of the (necessarily nonnegative) eigenvalues of
the symmetric matrix associated with
$(\tfrac{1}{2}\operatorname{Id}-{\mathbf{T}})^{*}(\tfrac{1}{2}\operatorname{Id}-{\mathbf{T}})$.
The operator norm is the largest singular value. All this can be found using a
symbolic algebra package such as SageMath (or Maple or Mathematica); see Table
1 which provides the squared singular values (with multiplicity) as well as
the desired operator norm.

$m$ | eigenvalues of $(\tfrac{1}{2}\operatorname{Id}-{\mathbf{T}})^{*}(\tfrac{1}{2}\operatorname{Id}-{\mathbf{T}})$ | $\|\tfrac{1}{2}\operatorname{Id}-{\mathbf{T}}\|$
---|---|---
2 |  $\tfrac{1}{4}$ (twice) | $\tfrac{1}{2}=0.5$
3 |  $\tfrac{1}{3}$ (twice), $\tfrac{1}{4}$ | $\tfrac{1}{\sqrt{3}}\approx 0.58$
4 |  $\tfrac{1}{2}$ (twice), $\tfrac{1}{4}$ (twice) | $\tfrac{1}{\sqrt{2}}\approx 0.71$
5 |  $\tfrac{1}{2}+\tfrac{1}{2\sqrt{5}}$ (twice), $\tfrac{1}{2}-\tfrac{1}{2\sqrt{5}}$ (twice), $\tfrac{1}{4}$ | $\sqrt{\tfrac{1}{2}+\tfrac{1}{2\sqrt{5}}}\approx 0.85$
6 |  $1$ (twice), $\tfrac{1}{3}$ (twice), $\tfrac{1}{4}$ (twice) | $1$
Table 1: Computing the operator norm of 118.

Therefore, when $m\leq 5$, then the fixed point equation 117 can theoretically
be solved by the Banach contraction mapping principle. (When $m\geq 7$, the
operator norm $\|\tfrac{1}{2}\operatorname{Id}-{\mathbf{T}}\|$ appears to be
always strictly larger than $1$.) Unfortunately, we do not know of an explicit
formula for the projector defined in 116. In practice, one may appeal to
_Seeger’s algorithm_ [23] for computing ${\mathbf{P}}$, which we record now:

######  Fact 6.1.

(Seeger’s algorithm) Given

$\mathbf{x}\in{\mathbf{X}},\;\text{and}\;\mathbf{d}_{0}\in{\mathbf{X}},$
(119a) generate sequences $(\mathbf{c}_{n})_{n\geq 1}$ and
$(\mathbf{d}_{n})_{n\geq 1}$ iteratively via
$\mathbf{c}_{n}:=P_{\mathbf{C}}(\mathbf{x}-\mathbf{d}_{n-1}),\quad\mathbf{d}_{n}:=P_{\boldsymbol{\Delta}}(\mathbf{x}-\mathbf{c}_{n}).$
(119b) Then $\mathbf{c}_{n}+\mathbf{d}_{n}\to
P_{\overline{{\mathbf{C}}+{\boldsymbol{\Delta}}}}(\mathbf{x})={\mathbf{P}}(\mathbf{x}).$
(119c)

##  7 Finding the difference vectors by forward-backward

In this section, we sketch another approach to numerically compute the
difference vectors. We begin by revisiting 38 as a _primal_ problem:

######  Proposition 7.1.

We interpret

$0\in
N_{\overline{{\mathbf{C}}+{\boldsymbol{\Delta}}}}^{-1}(\mathbf{y})+\big{(}\tfrac{1}{2}\operatorname{Id}+{\mathbf{T}}\big{)}(\mathbf{y}),$
(120)

which is 38 and for which the solution $\mathbf{y}$ is unique, as an Attouch-
Théra primal problem for the pair
$(N_{\overline{{\mathbf{C}}+{\boldsymbol{\Delta}}}}^{-1},\tfrac{1}{2}\operatorname{Id}+{\mathbf{T}})$.
Then $\tfrac{1}{2}\operatorname{Id}+{\mathbf{T}}$ is $\tfrac{1}{2}$-strongly
monotone and $(\tfrac{1}{2}\operatorname{Id}+{\mathbf{T}})^{-1}$ is
$\tfrac{1}{2}$-cocoercive. Moreover, the Attouch-Théra dual problem of 120 is

$0\in
N_{\overline{{\mathbf{C}}+{\boldsymbol{\Delta}}}}(\mathbf{x})+\big{(}\tfrac{1}{2}\operatorname{Id}+{\mathbf{T}}\big{)}^{-1}(\mathbf{x}),$
(121)

and the solution set of 121 is the singleton

$\\{\mathbf{e}\\}={\boldsymbol{\Delta}}^{\perp}\cap\operatorname{Fix}(P_{\overline{{\mathbf{C}}+{\boldsymbol{\Delta}}}}{\mathbf{R}}).$
(122)

Proof. Because ${\mathbf{T}}$ is skew (see 23), it follows that
$\tfrac{1}{2}\operatorname{Id}+{\mathbf{T}}$ is $\tfrac{1}{2}$-strongly
monotone. By [11, Example 22.7],
$(\tfrac{1}{2}\operatorname{Id}+{\mathbf{T}})^{-1}$ is
$\tfrac{1}{2}$-cocoercive. Because ${\mathbf{T}}$ is linear, the Attouch-Théra
dual of 120 with respect to the pair
$(N_{\overline{{\mathbf{C}}+{\boldsymbol{\Delta}}}}^{-1},\tfrac{1}{2}\operatorname{Id}+{\mathbf{T}})$
is indeed 121. We can pass from $\mathbf{y}$, the unique solution of 120, to
the set of solutions of 121 via
$N_{\overline{{\mathbf{C}}+{\boldsymbol{\Delta}}}}^{-1}(\mathbf{y})\cap-\big{(}\tfrac{1}{2}\operatorname{Id}+{\mathbf{T}}\big{)}(\mathbf{y})$
(see [10, Proposition 2.4]). Because ${\mathbf{T}}$ is single-valued, this
implies that the _unique_ solution to 121 is

$\mathbf{x}=N_{\overline{{\mathbf{C}}+{\boldsymbol{\Delta}}}}^{-1}(\mathbf{y})\cap-\big{(}\tfrac{1}{2}\operatorname{Id}+{\mathbf{T}}\big{)}(\mathbf{y})=-\tfrac{1}{2}\mathbf{y}-{\mathbf{T}}\mathbf{y}=\mathbf{e},$
(123)

where we used 40 for the last equality. Now consider 121 again. We rewrite
this, using 123, 32 and 40 as

$0\in
N_{\overline{{\mathbf{C}}+{\boldsymbol{\Delta}}}}(\mathbf{e})+\big{(}\operatorname{Id}-{\mathbf{R}}+2P_{\Delta}\big{)}(\mathbf{e})=N_{\overline{{\mathbf{C}}+{\boldsymbol{\Delta}}}}(\mathbf{e})+(\operatorname{Id}-{\mathbf{R}})(\mathbf{e}),$
(124)

or as
$\mathbf{e}=P_{\overline{{\mathbf{C}}+{\boldsymbol{\Delta}}}}({\mathbf{R}}\mathbf{e})\in\overline{{\mathbf{C}}+{\boldsymbol{\Delta}}}$
which yields 122. $\hfill\quad\blacksquare$

######  Theorem 7.2.

Let $\gamma\in\left]0,1\right[$, let $\mathbf{x}_{0}\in{\mathbf{X}}$, and
generate a sequence $(\mathbf{x}_{n})_{n\in{\mathbb{N}}}$ via

$\displaystyle\mathbf{x}_{n+1}$
$\displaystyle=P_{\overline{{\mathbf{C}}+{\boldsymbol{\Delta}}}}\big{(}\mathbf{x}_{n}-\gamma(\tfrac{1}{2}\operatorname{Id}+{\mathbf{T}})^{-1}\mathbf{x}_{n}\big{)}$
(125a)
$\displaystyle=P_{\overline{{\mathbf{C}}+{\boldsymbol{\Delta}}}}\big{(}(1-\gamma)\mathbf{x}_{n}+\gamma{\mathbf{R}}\mathbf{x}_{n}-2\gamma
P_{\boldsymbol{\Delta}}\mathbf{x}_{n}\big{)}.$ (125b)

Then

$\mathbf{x}_{n}\to\mathbf{e},$ (126)
${\mathbf{R}}\mathbf{x}_{n}-\mathbf{x}_{n}-2P_{{\boldsymbol{\Delta}}}\mathbf{x}_{n}\to\mathbf{y},$
(127)

and

${\mathbf{R}}^{*}\mathbf{x}_{n}-\mathbf{x}_{n}\to{\mathbf{v}}.$ (128)

Proof. Set ${\mathbf{A}}:=N_{\overline{{\mathbf{C}}+{\boldsymbol{\Delta}}}}$.
Also set ${\mathbf{B}}:=(\tfrac{1}{2}\operatorname{Id}+{\mathbf{T}})^{-1}$,
which is $\beta$-cocoercive, with $\beta=\tfrac{1}{2}$, by Proposition 7.1.
Then $\gamma\in\left]0,2\beta\right[$. Now set
$\delta:=2-\gamma/(2\beta)=2-\gamma>1$ and $\lambda:=\lambda_{n}\equiv 1$.
Then $\lambda_{n}(\delta-\lambda_{n})\equiv\delta-1>0$ and thus
$\sum_{n\in\mathbb{N}}\lambda_{n}(\delta-\lambda_{n})=+\infty$. We now apply
[11, Theorem 26.14] on the forward-backward algorithm applied to the problem
121. Note that 125a is precisely the forward-backward algorithm with the
parameters just defined because of [11, Remark 26.15] and
$\mathbf{x}_{n+1}=J_{\gamma{\mathbf{A}}}(\mathbf{x}_{n}-\gamma{\mathbf{B}}\mathbf{x}_{n})$.
The alternative formula 125b follows from 32. Using [11, Theorem
26.14(i)&(ii)] and Proposition 7.1, we have
$\mathbf{x}_{n}\>{\rightharpoonup}\>\mathbf{e}$ and

${\mathbf{B}}\mathbf{x}_{n}=\big{(}\tfrac{1}{2}\operatorname{Id}+{\mathbf{T}}\big{)}^{-1}\mathbf{x}_{n}\to\big{(}\tfrac{1}{2}\operatorname{Id}+{\mathbf{T}}\big{)}^{-1}\mathbf{e}=-\mathbf{y}.$
(129)

(The fact that ${\mathbf{B}}\mathbf{x}_{n}\to-\mathbf{y}$ and not $\mathbf{y}$
stems from the fact that the dual problem in [11, Chapter 26] differs from the
one in this paper by a negative sign.) Now 129 and 32 yield 127. Next, 129 and
the fact that ${\mathbf{T}}$ is continuous and single-valued yields

$\mathbf{x}_{n}=\big{(}\tfrac{1}{2}\operatorname{Id}+{\mathbf{T}}\big{)}\big{(}\tfrac{1}{2}\operatorname{Id}+{\mathbf{T}}\big{)}^{-1}\mathbf{x}_{n}\to\big{(}\tfrac{1}{2}\operatorname{Id}+{\mathbf{T}}\big{)}\big{(}\tfrac{1}{2}\operatorname{Id}+{\mathbf{T}}\big{)}^{-1}\mathbf{e}=\mathbf{e}$
(130)

and so 126 is verified. Finally, to check 128, apply the continuous operator
${\mathbf{R}}^{*}-\operatorname{Id}$ to 130 and recall 49.
$\hfill\quad\blacksquare$

######  Remark 7.3.

Theorem 7.2 is a powerful result for computing
$\mathbf{e},\mathbf{y},{\mathbf{v}}$ as _strong_ limits of sequence. As in
Section 6, the numerical difficulty lies in the computation of
$P_{\overline{{\mathbf{C}}+{\boldsymbol{\Delta}}}}$; however, Seeger’s
algorithm (see 6.1) may be used to approximate this projection.

######  Remark 7.4.

Theorem 7.2 allows for flexibility of the parameter
$\gamma\in\left]0,1\right[$. Perhaps the most natural choice is

$\gamma=\frac{1}{2};$ (131)

however, let us point out an intriguing other choices, namely

$\gamma=\frac{m}{m+2}.$ (132)

With the latter choice and 21, the inner (forward) operator in 125b turns into

$\displaystyle(1-\gamma)\operatorname{Id}+\gamma{\mathbf{R}}-2\gamma
P_{\boldsymbol{\Delta}}$
$\displaystyle=\frac{2}{m+2}\operatorname{Id}+\frac{m}{m+2}{\mathbf{R}}-\frac{2m}{m+2}P_{\boldsymbol{\Delta}}$
(133a)
$\displaystyle=\frac{2}{m+2}\operatorname{Id}+\frac{m}{m+2}{\mathbf{R}}-\frac{2m}{m+2}\frac{1}{m}\sum_{k=0}^{m-1}{\mathbf{R}}^{k}$
(133b)
$\displaystyle=\frac{m-2}{m+2}{\mathbf{R}}-\frac{2}{m+2}\sum_{k=2}^{m-1}{\mathbf{R}}^{k},$
(133c) which is Lipschitz continuous with constant $3(m-2)/(m+2)$ because
${\mathbf{R}}$ is an isometry.

We point out the cases when $m=2$ and $m=3$, for which $\gamma=1/2$ and
$\gamma=3/5$ respectively, and 133 turns into

$\text{\rm\big{[}$m=2$ and
$\gamma=\tfrac{1}{2}$\big{]}}\;\;\Rightarrow\;\;(1-\gamma)\operatorname{Id}+\gamma{\mathbf{R}}-2\gamma
P_{\boldsymbol{\Delta}}\equiv 0\text{\rm~{}is $0$-Lipschitz }$ (134)

and

$\text{\rm\big{[}$m=3$ and
$\gamma=\tfrac{3}{5}$\big{]}}\;\;\Rightarrow\;\;(1-\gamma)\operatorname{Id}+\gamma{\mathbf{R}}-2\gamma
P_{\boldsymbol{\Delta}}=\tfrac{1}{5}{\mathbf{R}}-\tfrac{2}{5}{\mathbf{R}}^{2}\text{\rm~{}is
$\tfrac{3}{5}$-Lipschitz.}$ (135)

Note that 134 looks at first puzzling because then 125b turns into
$\mathbf{x}_{n+1}=P_{\overline{{\mathbf{C}}+{\boldsymbol{\Delta}}}}(0)$ and so
126 yields $\mathbf{e}=P_{\overline{{\mathbf{C}}+{\boldsymbol{\Delta}}}}(0)$;
however, we already observed this directly in 61.

##  8 Conclusion and future work

Using the framework of monotone operator theory, we resolved the geometry
conjecture completely. We obtained alternative descriptions of the set of
cycles ${\mathbf{Z}}$. We also sketched numerical approaches for the
computation of the difference vector ${\mathbf{v}}$ by using Seeger’s
algorithm.

Turning to future research, it is desirable to devise algorithms for computing
${\mathbf{v}}$ without having to employ Seeger’s algorithm. Moreover, it is
interesting to extend the results in this paper from projectors to
(underrelaxed) projectors or even proximal mappings. We have taken steps in
this direction, and initial progress appears to be quite promising [3].

## Acknowledgments

The authors thank two referees and the editor for careful reading, thoughtful
comments, and suggestions which significantly improved the presentation of the
results. HHB and XW are supported by the Natural Sciences and Engineering
Research Council of Canada.

## References

  * [1]
  * [2] S. Alwadani, H.H. Bauschke, J.P. Revalski, and X. Wang, Resolvents and Yosida approximations of displacement mappings of isometries, _Set-Valued and Variational Analysis_ , in press. https://link.springer.com/article/10.1007%2Fs11228-021-00584-2
  * [3] S. Alwadani, H.H. Bauschke, and X. Wang, Attouch-Théra duality, generalized cycles and gap vectors, _SIAM Journal on Optimization_ , in press.
  * [4] H. Attouch and M. Théra, A general duality principle for the sum of two operators, _Journal of Convex Analysis_ 3 (1996), 1–24.
  * [5] J.-B. Baillon, P.L. Combettes, and R. Cominetti, There is no variational characterization of the cycles in the method of periodic projections, _Journal of Functional Analysis_ 262 (2012), 400–408.
  * [6] J.-B. Baillon, P.L. Combettes, and R. Cominetti, Asymptotic behavior of compositions of underrelaxed nonxpansive operators, _Journal of Dynamics and Games_ 1 (2014), 331–346.
  * [7] H.H. Bauschke and J.M. Borwein, Dykstra’s alternating projection algorithm for two sets, _Journal of Approximation Theory_ 79 (1994), 418–443.
  * [8] H.H. Bauschke and J.M. Borwein, On the convergence of von Neumann’s alternating projection algorithm for two sets, _Set-Valued Analysis_ 1 (1993), 185–212.
  * [9] H.H. Bauschke, J.M. Borwein, and A.S. Lewis, The method of cyclic projections for closed convex sets in Hilbert space, _Contemporary Mathematics_ 104 (1997), 1–38.
  * [10] H.H. Bauschke, R.I. Boţ, W.L. Hare, and W.M. Moursi, Attouch-Théra duality revisited: paramonotonicity and operator splitting, _Journal of Approximation Theory_ 164 (2012), 1065–1084.
  * [11] H.H. Bauschke and P.L. Combettes, _Convex Analysis and Monotone Operator Theory in Hilbert Spaces_ , second edition, Springer, 2017.
  * [12] H.H. Bauschke, V. Martín-Márquez, S.M. Moffat, and X. Wang, Compositions and convex combinations of asymptotically regular firmly nonexpansive mappings are also asymptotically regular, _Fixed Point Theory and Applications_ 2012:53. https://fixedpointtheoryandapplications.springeropen.com/articles/10.1186/1687-1812-2012-53
  * [13] H. Brézis, _Operateurs Maximaux Monotones et Semi-Groupes de Contractions dans les Espaces de Hilbert_ , North-Holland/Elsevier, 1973.
  * [14] R.S. Burachik and A.N. Iusem, _Set-Valued Mappings and Enlargements of Monotone Operators_ , Springer-Verlag, 2008.
  * [15] C.L. Byrne, _Signal Processing_ , A K Peters, 2005.
  * [16] C.L. Byrne, _Applied Iterative Methods_ , A K Peters, 2008.
  * [17] Y. Censor and M. Zaknoon, Algorithms and convergence results of projection methods for inconsistent feasibility problems: A review, _Pure and Applied Functional Analysis_ 3 (2018), 565–586. http://www.ybook.co.jp/online2/oppafa/vol3/p565.html
  * [18] W. Cheney and A.A. Goldstein, Proximity maps for convex sets, _Proceedings of the AMS_ 10 (1959), 448–450.
  * [19] P.L. Combettes and J.-C. Pesquet, Fixed point strategies in data science, _IEEE Transactions on Signal Processing_ , in press.
  * [20] A.R. De Pierro, From parallel to sequential projection methods and vice versa in convex feasibility: results and conjectures, in _Inherently Parallel Algorithms in Feasibility and Optimization and their Applications_ , D. Butnariu, Y. Censor and S. Reich (editors), Elsevier, 2001, pp. 369–379.
  * [21] R. Cominetti, V. Roshchina, and A. Williamson, A counterexample to De Pierro’s conjecture on the convergence of under-relaxed cyclic projections, _Optimization_ 68 (2019), 3–12.
  * [22] A.N. Iusem, On some properties of paramonotone operators, _Journal of Convex Analysis_ 5 (1998), 269–278.
  * [23] A. Seeger, Alternating projection and decomposition with respect to two convex sets, _Mathematica Japonica_ 47 (1998), 273–280. See also the preprint version https://mathfiles.kfupm.edu.sa/data/files/mathonly/TechnicalReportsData/172.pdf
  * [24] S. Simons, _Minimax and Monotonicity_ , Springer-Verlag, 1998\.
  * [25] S. Simons, _From Hahn-Banach to Monotonicity_ , Springer-Verlag, 2008\.