# Synthetic projective lines, geometric closure and AB-sets

Koen Thas  Ghent University, Department of Mathematics, Krijgslaan 281, S25,
B-9000, Ghent, Belgium<EMAIL_ADDRESS>
###### Abstract.

In this note, we introduce a new approach to abstract “synthetic” projective
lines. We discuss various aspects of our approach, and compare these aspects
with the classical one. A number of intriguing questions arise. Amongst these
aspects, we discuss geometric closures, and introduce automorphism-blocking
sets. We also construct a number of (counter) examples in infinite cases.

###### Key words and phrases:

Projective line, axiomatic projective plane, embedding, automorphism,
representation

###### Contents

  1. 1 Introduction
  2. 2 Some initial definitions
  3. 3 Synthetic projective lines
  4. 4 Orbits and lines
  5. 5 Categorical setting
  6. 6 Extensions and embeddings
  7. 7 Geometric closure
  8. 8 Rigid projective lines, realization and AB-sets

##  1\. Introduction

There exists a long and rich history in defining the concept of a projective
line, both over coordinatizing algebraic structures and combinatorially. The
classical approach is to consider a field (or division ring) $k$, and define
the projective line $\mathbb{P}^{1}(k)$ over $k$ as the geometry of the vector
lines in the $2$-dimensional (left or right, in case of a division ring)
vector space $V(2,k)$. (One can see the line as the set $k\cup\\{\infty\\}$,
which comes with the natural $3$-transitive action of $\mathsf{PGL}_{2}(k)$,
extended with field automorphisms.) This local viewpoint is a property we want
to incorporate in our approach.

### Some known approaches

One first, naive synthetic approach is the rather “flat” incidence-geometrical
way in which one sees a line as a set of points $\Omega$, which then comes
with the automorphism group $\mathsf{Sym}(\Omega)$. This is obviously not what
we want: their is no projective aspect whatsoever, and the automorphism group
is boring. Buekenhout [1], under the influence of the school of Libois, took
an entire different turn, and modeled projective lines after projective lines
seen as subgeometries of Desarguesian projective spaces $\mathbb{P}^{n}(k)$
(with $k$ a field). More specifically, he molded the geometry by using
specific automorphisms (which in the Desarguesian examples are induced by
central collineations in the line stabilizers in $\mathsf{P\Upgamma
L}_{n+1}(k)$), as such creating an interesting geometric object which comes
with an interesting automorphism group. We recall Buekenhout’s definition. A
projective line is a set $\mathcal{L}$ of cardinality $\geq 3$, satisfying the
following axioms:

  * (a)

Each $p,q\in\mathcal{L}$, comes with a group $\lambda(p,q)$ whose elements are
called central collineations with center $p$ and axis $q$. Note that $q$ need
not be distinct from $p$. The group $\lambda(p,q)$ acts on $\mathcal{L}$ as
follows: it fixes $p$ and $q$, and if an element fixes a point
$r\not\in\\{p,q\\}$, then it is the identity. The action is faithful, and each
$\lambda(p,q)$ is a subgroup of $\mathrm{Aut}(\mathcal{L})$.

  * (b)

If $p\neq q$, then $\lambda(p,q)$ and $\lambda(q,p)$ commute with each other.

  * (c)

For any $\gamma\in\lambda(r,s)$ and any $p,q$, we have
$\gamma\lambda(p,q)\gamma^{-1}=\lambda(\gamma(p),\gamma(q))$.

  * (d)

The composite of two collineations with center $p$ (possibly with different
axes) is again a collineation with center $p$, and dually the composite of two
collineations with axis $q$ (possibly with different centers) is again a
collineation with axis $q$. Thus we have two groups
$\lambda(p)=\cup_{q}\lambda(p,q)$ and $\lambda(q)=\cup_{p}\lambda(p,q)$.

A projective line is Desarguesian if in addition $\lambda(p,q)$ acts (sharply)
transitively on $\mathcal{L}\setminus\\{p,q\\}$. In this approach, any set is
a projective line (by putting all $\lambda(p,q)=\\{\mathrm{id}\\}$). The
natural examples are the lines $U$ in any (not necessarily Desarguesian)
projective plane $\mathcal{P}$: if $u$ and $v$ are points of $U$, then let
$\lambda(u,v)$ be induced by the group of central collineations of
$\mathcal{P}$ with center $u$ and axis some line $V$ incident with $v$ where
$V$ varies over these lines. Buekenhout’s theory is just one of many quite
similar approaches which endow a set with specific permutations modeled after
lines in certain classes of projective planes. Still, it only models the
automorphism groups of projective lines (in projective planes), and not the
geometry. In our approach, projective lines will come with an embedding; this
viewpoint includes a geometric theory, a relative angle and heavily restricted
automorphism groups.

One other way to see projective lines in the incidence-geometrical context is
through Tits’s theory of (split) BN-pairs, in this case of dimension $1$.
Unfortunately this is essentially an approach to classical lines, and if $U$
is a line in a projective line $\mathcal{P}$, then if $H$ is the group induced
on $\mathrm{Aut}(\mathcal{P})_{U}$, the permutation group $(H,U)$ (where we
see $U$ as a point set) is generically not reached by a (split) BN-pair of
rank $1$, since the latter are always doubly transitive. We feel that this
approach also lacks an underlying geometry, and in this paper we want to take
quite a different view on the subject which entertains both more geometry and
more general automorphism groups.

######  Remark 1.1.

One of the most interesting viewpoints is the algebro-geometric approach,
which puts a Zariski topology on the set of prime ideals of a commutative ring
(this defines the geometry), and then comes with a sheaf of rings. For our
purposes, especially the geometrical (topological) aspect is very interesting,
and the structure of the commutative ring endows the projective line with a
highly nontrivial geometry. We give two examples. Consider the real projective
line $\mathsf{Proj}(\mathbb{R}[x,y])$. Its prime ideals (closed points) are
generated by either polynomials of degree $1$ or irreducible polynomials of
degree $2$. Those of degree $1$, such as $(x-a)$ gives a “classical rational
point” ($(1,a)$) and those of the second type, such as $(x^{2}+1)$ “become”
two rational points $(x+i)$ ($(1,i)$) and $(x-i)$ ($(1,-i)$) in the projective
line $\mathsf{Proj}(\mathbb{C}[x,y])$, and
$\mathsf{Gal}(\mathbb{C}/\mathbb{R})$ acts transitively on these “conjugate
points.” Second example: consider the algebro-geometric projective line
$L=\mathsf{Proj}({\mathbb{F}_{q}}[x,y])$, where $\mathbb{F}_{q}$ is any finite
field. Its closed points are the “usual” points, but it contains much more
information. Let $x$ be any of its closed points (which we regard as the point
at infinity), and consider the affine line
$L\setminus\\{x\\}=\mathsf{Spec}(\mathbb{F}_{q}[x])$. Let
$f(x)\in\mathbb{F}_{q}[x]$ be an irreducible polynomial of degree $m$. Then
the point corresponding to the prime ideal $(f(x))$ defines $m$ different
points in $\mathbb{F}_{q^{m}}\cong\mathbb{F}_{q}[x]/(f(x))$ on which the
Galois group $\mathsf{Gal}(\mathbb{F}_{q^{m}}/\mathbb{F}_{q})$ acts
transitively. In some sense, the affine line
$\mathsf{Spec}(\overline{\mathbb{F}_{q}}[x])$ contains the same information
(and its Galois group captures the information of all the separate finite
Galois groups).

### The present paper

In this paper, a projective line comes with a full imbedding in an axiomatic
projective plane, and morphisms between lines must take the embeddings into
account. But there is more: if $U$ is a line in a projective plane
$\mathcal{P}$, then the actual projective line is determined by a point $x$
not incident with $U$, and that line consists of the data
$\mathcal{L}=(\mathcal{P},U,x)$. The points of the line $\mathcal{L}$ are
given by the lines incident with $x$, and automorphism must respect the
structure of the plane, while fixing $U$ and $x$. We compare two approaches:
the “projective” approach in which $U$ itself is defined as a line, and the
aforementioned “affine” approach, which looks at the line from the viewpoint
of $x$. In the Desarguesian case, those approaches are essentially the same,
but in general they are very different. Generically, what one sees locally
from the point $x$ depends on the location of $x$, and only when there is an
automorphism of the plane which fixes $U$ while carrying $x$ to another point
$x^{\prime}$, the local geometries will be the same. On the other hand, it
could be that nonisomorphic lines in this formalism define the exact same
automorphism group as a permutation group, and that is different in the
synthetic approached we mentioned (where the isomorphism class of the line is
determined by the isomorphism class of the permutation group it defines).

Our main viewpoint is essentially the following. If one wants to define
abstract synthetic projective planes $\Upgamma$, one cannot use an embedding
into a higher-dimensional projective space such as a $3$-space (2), since the
classical Veblen-Young result states that such as space is isomorphic to a
space $\mathbb{P}^{3}(\dj)$ which is defined over a division ring $\dj$. But
since planes do not have this property, we can and will use embeddings of
lines in axiomatic planes (1) to do the job.

(1) $\mbox{line}\ \xrightarrow[]{\leavevmode\hbox to14.18pt{\vbox
to14.18pt{\pgfpicture\makeatletter\hbox{\hskip 7.09111pt\lower-7.09111pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{6.89111pt}{0.0pt}\pgfsys@curveto{6.89111pt}{3.8059pt}{3.8059pt}{6.89111pt}{0.0pt}{6.89111pt}\pgfsys@curveto{-3.8059pt}{6.89111pt}{-6.89111pt}{3.8059pt}{-6.89111pt}{0.0pt}\pgfsys@curveto{-6.89111pt}{-3.8059pt}{-3.8059pt}{-6.89111pt}{0.0pt}{-6.89111pt}\pgfsys@curveto{3.8059pt}{-6.89111pt}{6.89111pt}{-3.8059pt}{6.89111pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}\ \mbox{plane}\
\xrightarrow[]{\leavevmode\hbox to14.18pt{\vbox
to14.18pt{\pgfpicture\makeatletter\hbox{\hskip 7.09111pt\lower-7.09111pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{6.89111pt}{0.0pt}\pgfsys@curveto{6.89111pt}{3.8059pt}{3.8059pt}{6.89111pt}{0.0pt}{6.89111pt}\pgfsys@curveto{-3.8059pt}{6.89111pt}{-6.89111pt}{3.8059pt}{-6.89111pt}{0.0pt}\pgfsys@curveto{-6.89111pt}{-3.8059pt}{-3.8059pt}{-6.89111pt}{0.0pt}{-6.89111pt}\pgfsys@curveto{3.8059pt}{-6.89111pt}{6.89111pt}{-3.8059pt}{6.89111pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}\
\mathbb{P}^{3}(\dj)$

In sections 2–3–4–5, we essentially develop and discuss a number of aspects of
the category of projective lines both in the finite and infinite case, and we
show that the infinite case is quite different (through the construction of
counter examples to theorems which hold true in the finite case). In section 6
we discuss extensions and embeddings (of lines into lines). This motivates us
to consider geometric closures in section 7. In the final section, which might
well be the section with the most applications in its own right, we introduce
and discuss AB-sets in order to construct rigid lines and rigid planes. Such
geometries block the automorphisms of the ambient geometry in a precise way,
and can be studied outside the category of axiomatic projective planes. The
paper is complemented by a number of natural problems and questions which
arise, and this aspect is one of our main motivations.

##  2\. Some initial definitions

A point-line incidence structure
$\Upgamma=(\mathcal{P},\mathcal{L},\mathbf{I})$ (where $\mathcal{P}$ and
$\mathcal{L}$ are the point set and line set, and $\mathbf{I}$. is a symmetric
incidence relation) is a projective plane if it satisfies the following
axioms:

  * (a)

any two distinct points are incident with one unique line;

  * (b)

any two distinct lines are incident with one unique point;

  * (c)

there exist four distint points of which no three are incident with the same
line.

Each projective plane has an order $N$; any of its points are then incident
with $N+1$ lines and any line is incident with $N+1$ points.

A point-line incidence structure
$\Upgamma=(\mathcal{P},\mathcal{L},\mathbf{I})$ (where $\mathcal{P}$ and
$\mathcal{L}$ are the point set and line set, and $\mathbf{I}$. is a symmetric
incidence relation) is an affine plane if it satisfies the following axioms:

  * (a)

any two distinct points are incident with one unique line;

  * (b)

if $A$ is a line and $a$ is a point not incident with $A$, then $a$ is
incident with a unique line $B$ which does not meet $A$;

  * (c)

there exist three distint points of which no three are incident with the same
line.

Automorphisms and isomorphisms of and between projective and affine planes are
defined in the standard way [8]. By $\mathrm{Aut}(\Upgamma)$, we denote the
automorphism group of a geometry $\Upgamma$.

If $\Upgamma$ is a projective plane and $U$ is any line of $\Upgamma$, then by
deleting the line $U$ and the points incident with $U$, one obtains an affine
plane $\Upgamma_{U}$. On the other hand, if $\mathcal{A}$ is an affine plane,
then there exists a projective plane $\mathcal{P}$ and a line $V$ in
$\mathcal{P}$ such that $\mathcal{P}_{V}$ is isomorphic to $\mathcal{A}$. The
couple $(\mathcal{P},V)$ is unique up to isomorphism with respect to this
property. Any automorphism of $\mathcal{P}$ which fixes $V$ induces an
automorphism of $\mathcal{P}_{V}$, and every automorphism of $\mathcal{A}$
defines an automorphism of $\mathcal{P}$ which fixes $V$. If $\mathcal{A}$ is
an affine plane, then by $\overline{\mathcal{A}}$ we denote its projective
completion.

##  3\. Synthetic projective lines

We are guided by the analogy between vector spaces (over division rings) and
axiomatic affine planes with a distinguished point (which we compare to the
zero vector). So consider any axiomatic affine plane $\mathcal{A}$, and fix
one arbitrary point $\omega$. Based on the discussion in section 2, we define
the projective line $(\mathcal{A},\omega)$ as the set of lines
$\mathcal{L}_{\omega}$ of $\mathcal{A}$ incident with $\omega$. Note that we
do not consider $\mathcal{L}_{\omega}$ merely as a set: it comes with an
embedding in $\mathcal{A}$. The definition of the automorphism group of
$(\mathcal{A},\omega)$ clearly illustrates this viewpoint.

###  3.1. Automorphism group

An automorphism of $(\mathcal{A},\omega)$ is an element $\alpha$ of
$\mathrm{Aut}(\mathcal{A})_{\omega}$, taking into account that
$\alpha=\alpha^{\prime}$ in $\mathrm{Aut}(\mathcal{A},\omega)$ with
$\alpha,\alpha^{\prime}\in\mathrm{Aut}(\mathcal{A})_{\omega}$ if and only if
they induce the same action on $\mathcal{L}_{\omega}$. It follows that

(2) $\mathrm{Aut}(\mathcal{A},\omega)\ \cong\
\mathrm{Aut}(\mathcal{A})_{\omega}/N$

with $N$ the kernel of the action of $\mathrm{Aut}(\mathcal{A})_{\omega}$ on
$\mathcal{L}_{\omega}$—that is, the group of homologies with center $\omega$
and axis the line at infinity of $\mathcal{A}$.

The notion of isomorphism is now obvious: we say that two synthetic lines
$(\mathcal{A},\omega)$ and $(\mathcal{A},\omega^{\prime})$ are isomorphic if
there exists an isomorphism of planes

(3) $\gamma:\ A\ \mapsto A^{\prime}$

such that $\gamma(\omega)=\omega^{\prime}$.

In section 5 we will formally define the category of projective lines.

###  3.2. Projective planes versus affine planes

One could also consider the variation of the definition of synthetic
projective line, in which the affine plane $\mathcal{A}$ is replaced by a
projective plane $\mathcal{P}$. In that case, we could also dualize the
definition, and see a projective type line as a line of a projective plane,
which comes with an automorphism group which is induced by the group of the
plane.

We prefer the affine approach, on the one hand because of the vector space
analogy, and on the other hand because it depends on the location of the base
point (relative to the line at infinity, which is a natural model for the
line). Also, a number of very interesting problems arise in the affine
approach, and these are among our motivations to study the problem. In fact,
the very problems which arise when comparing the affine approach to the
projective approach already are very promising, as we will see in this
section. Let us remark that if $(\mathcal{A},\mu)$ is a projective line
($\mathcal{A}$ an affine plane), then the embeddings

(4) $(\mathcal{A},\mu)\ \hookrightarrow\ \mathcal{A}\ \hookrightarrow\
\overline{\mathcal{A}}$

implies that $\mathrm{Aut}(\mathcal{A},\mu)$ is a subgroup of
$\mathrm{Aut}(\overline{\mathcal{A}},\mu)$.

The main two questions we ask are the following. Let $\mathcal{P}$ be a
projective plane, and consider, in the same way as above, the synthetic line
(projective version) $(\mathcal{P},\mu)$ and
$\mathrm{Aut}(\mathcal{P})_{\mu}/N$, with $N$ the kernel of the action of
$\mathrm{Aut}(\mathcal{P})_{\mu}$ on the lines incident with $\mu$. For each
line $U$ in $\mathcal{P}$ which is not incident with $\mu$ we can consider the
synthetic line $(\mathcal{P}_{U},\mu)$, with $\mathcal{P}_{U}$ the affine
plane arising from deleting $U$.

######  Question 3.1 (Inheritance).

Is
$\mathrm{Aut}(\mathcal{P})_{\mu}/N=\bigcup_{U\mathop{\not\mathbf{I}}\mu}\Big{(}{\mathrm{Aut}(\mathcal{P})}_{U,\mu}\Big{/}M_{U}\Big{)}$,
with $M_{U}$ the kernel of the action of ${\mathrm{Aut}(\mathcal{P})}_{U,\mu}$
on the lines incident with $\mu$.

In other words: can we recover each automorphism of the projective type line
$(\mathcal{P},\mu)$ from some automorphism of an affine type line
$(\mathcal{P}_{U},\mu)$?

We will construct counter examples in the infinite case, which will indicate
that many counter examples exist. In the finite case, many counter examples
exist as well, and we will explain some thoughts on that matter. A second,
highly related but altogether different question which we need to understand
is the following:

######  Question 3.2 (Generation).

Is
$\mathrm{Aut}(\mathcal{P})_{\mu}/N=\Big{\langle}\Big{(}{\mathrm{Aut}(\mathcal{P})}_{U,\mu}\Big{/}M_{U}\Big{)}\
|\ U\mathop{\not\mathbf{I}}\mu\Big{\rangle}$, with $M_{U}$ the kernel of the
action of ${\mathrm{Aut}(\mathcal{P})}_{U,\mu}$ on the lines incident with
$\mu$.

Here we ask whether each automorphism of the projective type line
$(\mathcal{P},\mu)$ is generated by automorphisms of affine type lines
$(\mathcal{P}_{U},\mu)$.

###  3.3. Some general remarks

We first recall the next theorem:

######  Theorem 3.3 (Hughes and Piper [8], Theorem 13.3).

An automorphism of a finite projective plane has an equal number of fixed
points and lines.

Now any automorphism $\alpha\in\mathrm{Aut}(\mathcal{P})$ which fixes $\mu$,
also fixes some line $M$. If $M$ is not incident with $\mu$, then $\alpha$, as
an automorphism of $(\mathcal{P},\mu)$, is inherited from an automorphism of
$(\mathcal{P}_{M},\mu)$. But theoretically, automorphisms which only fix a
flag of $\mathcal{P}$, or more generally which fix $m<0$ lines on a point
$\mathcal{U}$ and $n>0$ points on exactly one these lines (and no other lines
and points), could exist, and would not be inherited. (Call such automorphisms
“of projective origin.”) We will now construct counter examples which work
both in the finite and infinite case for Desarguesian planes, and more
generally for semifield planes. In the next subsection, we will construct a
rather different class of counter examples.

Call a projective plane $\mathcal{P}$ a semifield plane if there exists a flag
$(x,Y)$ for which $x$ is a translation point (with translation group $T(x)$),
and $Y$ a translation line (with translation group $T(Y)$). Now let $t\in
T(Y)^{\times}$ be such that it fixes the point $u\neq x$ on $Y$ linewise (an
element of $T(Y)$ which is not an $(x,Y)$-elation has this property). Let
$\widetilde{y}$ be an element in $T(x)^{\times}$ which does not fix $Y$
pointwise (again, any element which is not an $(x,Y)$-elation is such an
element). Note that $T(Y)\cap T(x)$ is precisely the complete group of all
$(x,Y)$-elations. Then obviously $t\widetilde{t}$ fixes the flag $(x,Y)$ and
no other points and lines.

For Desarguesian projective planes, the converse is also true in case of
linear automorphisms. For, let $(x,Y)$ be a flag in such a plane
$\mathcal{P}$, and let $\alpha$ be a linear automorphism fixing $x$, $Y$ and
no other points and lines. Suppose $\alpha$ induces the (linear) automorphism
$\alpha_{Y}$ on $Y$; then it is easy to see that $T(x)$ contains an element
$\widehat{\alpha}$ which induces $\alpha_{1}$. In the same way, if
$\alpha_{x}$ is the linear automorphism induced by $\alpha$ on the lines
incident with $x$, we take an element $\widetilde{\alpha}$ in $T(Y)$ which
induces $\alpha_{x}$ on these lines. Now consider
$\epsilon:=\alpha(\widehat{\alpha}\widetilde{\alpha})^{-1}$; this is an
automorphism which fixes $x$ linewise and $Y$ pointwise, so $\epsilon\in
T(x)\cap T(Y)\leq\langle T(x),T(Y)\rangle=T(x)T(Y)$. It follows that $\alpha$
is also contained in $T(x)T(Y)$. If $\alpha$ is not linear, this might depend
on the field over which the plane is defined. Suppose that $\mathcal{P}$ is
finite and defined over $\mathbb{F}_{q}$, with $q=p^{h}$ and $p$ a prime.
Suppose that $(p,h)=1$, so that $p$ does not divide
$|\texttt{Gal}(\mathbb{F}_{q}/\mathbb{F}_{p})|$. As the order of $\alpha$ must
be a power of $p$ (otherwise we have more fixed points and fixed lines), and
since $[\mathsf{P\Upgamma
L}_{3}(q):\mathsf{PGL}_{3}(q)]=h=|\mathsf{Gal}(\mathbb{F}_{q}/\mathbb{F}_{p})|$,
it follows that $\alpha$ is linear.

###  3.4. Infinite case

In the infinite case, we need a different approach. For, suppose that $\gamma$
is an automorphism of the infinite projective plane $\mathcal{P}$. Let
$\mathcal{P}=\\{x_{i}\ |\ i\in\mathcal{I}\\}$ be the set of points of the
plane, and $\mathcal{L}=\\{M_{i}\ |\ i\in\mathcal{I}\\}$ be the set of lines.
Let $A$ be an incidence matrix for $\mathcal{P}$ ($a_{ij}=1$ if and only if
$x_{i}$ is incident with $M_{j}$, otherwise it is $0$). Define a matrix
$P=(p_{ij})$ as follows: $p_{ij}=1$ if $x_{i}^{\gamma}=x_{j}$; (otherwise $0$)
and define a matrix $L=(l_{ij})$ in a similar way: $l_{ij}=1$ if
$l_{i}^{\gamma}=l$ (otherwise $0$). Note that $P$ and $L$ are infinite
permutation matrices. Now consider
$(PA)_{ij}=\sum_{k\in\mathcal{I}}p_{ik}a_{kj}=:a_{uj}$, where $u$ is uniquely
determined by the fact that $p_{iu}=1$: $x_{i}^{\gamma}=x_{u}$. Next, we look
at the $(i,j)$-entry $(AL)_{ij}$ of $AL$, which is given by
$\sum_{k\in\mathcal{I}}a_{ik}l_{kj}=a_{iv}$, where $v$ is uniquely determined
by the fact that $M_{v}^{\gamma}=M_{j}$. Now $a_{uj}=1$ if and only if
$x_{u}\mathbf{I}M_{j}$ if and only if
$x_{u}^{\gamma^{-1}}\mathbf{I}M_{j}^{\gamma^{-1}}$ if and only if
$x_{i}\mathbf{I}M_{v}$ if and only if $a_{iv}=1$, implying that

(5) $PA\ =\ AL.$

In the finite case one now easily concludes that $P$ and $L$ have the same
trace, translated into the fact $\gamma$ has the same number of fixed points
as fixed lines. But in the infinite case this is essentially where the story
ends. In the next subsection, we construct counter examples to Theorem 3.3 in
the infinite case.

### Counter examples

Consider the Fano plane $\Pi$, and let $(x,M)$ be an anti-flag. Let $\alpha$
be an automorphism of $\Pi$ of order $3$ which fixes $x$, $M$ and no other
point or line, so that point-orbits and line-orbits of $\langle\alpha\rangle$
which do not contain $x$ nor $L$ all have size $3$ (and note that such
automorphisms exist). Now remove $M$ and the points incident with $M$ (which
form one point-orbit) to obtain a point-line configuration $\mathcal{C}$
(affine plane of order $2$), and $\alpha$ induces an automorphism of
$\mathcal{C}$ which we denote by $\alpha_{0}$.

We now perform a free construction on $\mathcal{C}$ to obtain a countably
infinite free projective plane $\overline{\mathcal{C}}$. Put
$\mathcal{C}=\mathcal{C}_{0}$. In step one, we add new points to
$\mathcal{C}_{0}$ for each pair of nonconcurrent lines in $\mathcal{C}_{0}$ to
obtain $\mathcal{C}_{1}$. In the next step, we add new lines for each pair of
noncollinear points to obtain $\mathcal{C}_{2}$. And so on. The free plane
$\overline{\mathcal{C}}$ is

(6) $\cup_{i\in\mathbb{N}}\mathcal{C}_{i}.$

In each step, we also construct an automorphism of the newly obtained point-
line configuration. This is easy. For instance, one we have constructed
$\mathcal{C}_{1}$, the new points naturally form an orbit of size $3$ (by
looking at the image of the lines) and we obtain $\alpha_{1}$. The same is
true for $\mathcal{C}_{2}$, and we obtain $\alpha_{2}$. By induction, we
obtain that each $\alpha_{i}$ is well defined, and its “union”
$\overline{\alpha}$ is an automorphism of $\overline{\mathcal{C}}$ which fixes
the point $x$, and all other points and lines live in orbits of
$\langle\overline{\alpha}\rangle$ of size $3$. (Note that if the new line $N$
is added in stage $\mathcal{C}_{m}$, then it only contains two points which
both live in separate orbits of size $3$, so that $N$ cannot be fixed, and it
lives in an $\langle\alpha\rangle$-orbit of size $3$.)

So there are no fixed lines.

Note that the automorphism $\overline{\alpha}$ cannot be inherited by some
affine type projective line automorphism based at $x$:

######  Theorem 3.4.

The automorphism $\overline{\alpha}$ defines a nontrivial automorphism of the
projective type line $(\overline{\mathcal{C}},x)$ which is not inherited by
any affine type line automorphism.

Proof. Suppose there is some line $U$ in $\overline{\mathcal{C}}$ not incident
with $x$, so that there is an automorphism of $\overline{\mathcal{C}}_{U}$
(which we see as an automorphism of $\overline{\mathcal{C}}$ which fixes $U$)
which induces $\overline{\alpha}$ on the lines of $\overline{\mathcal{C}}$
incident with $x$. Then $\beta:=\overline{\alpha}\gamma^{-1}$ is a central
collineation of $\overline{\mathcal{C}}$ with center $x$. Now let $\Delta$ be
a triangle with sides $A,B,C$, such that $x$ is not incident with $A,B$ and
$C$. Then $A,B,C,A^{\beta},B^{\beta},C^{\beta}$ define a Desargues
configuration $\mathcal{D}$. Now $\mathcal{D}$ is a finite point-line
configuration with three points per line and three lines per point, so by
definition the configuration is confined. By Heartshorne [3], it follows that
$\mathcal{D}^{\overline{\alpha}}$ is a subgeometry of the begin configuration
$\mathcal{C}_{0}$, which is the contradiction we were seeking. So
$\overline{\alpha}$ indeed defines a nontrivial automorphism of the projective
type line $(\overline{\mathcal{C}},x)$ which is not inherited by any affine
type line automorphism in $\overline{\mathcal{C}}$. $\blacksquare$

Applied to Question 3.1, Theorem 3.4 yields counter examples in the infinite
case.

Of course, this method immediately generalizes to the following theorem (using
the same notation).

######  Theorem 3.5.

Let $\Pi$ be a finite projective plane, and let $(x,M)$ be an anti-flag.
Suppose $\alpha$ is an automorphism of $\Pi$ which fixes $x$, $M$ and no other
points nor lines. Remove $M$ and its points to obtain the affine plane
$\mathcal{C}$, and free construct the projective plane
$\overline{\mathcal{C}}$. Then $\overline{\alpha}$ is an automorphism of
$\overline{\mathcal{C}}$ which fixes $x$, and no other points and lines of
$\overline{\Pi}$. $\blacksquare$

###  3.5. Group theoretical discussion

On the abstract group-theoretical level, we pose the following related
problem.

######  Question 3.6.

Let $(H,X)$ be a permutation group. When is $H$ generated by (all) its
subgroups $H_{x}$, where $H_{x}$ is the stabilizer of $x\in X$.

In [10] it is shown that if $H$ is transitive on $X$, then it will be
generated by its point-stabilizers if and only if it does not have a proper
system of imprimitivity upon which it acts sharply transitively. The proof is
very simple: let $N$ be the normal subgroup of $H$ generated by all the point-
stabilizers $H_{x}$. If $N\neq H$, then clearly $N$ cannot act transitively on
$X$ (as it contains point-stabilizers). If $\Omega$ is an $N$-orbit, then
$H_{\Omega}$ and $N$ act transitively on $\Omega$, so that $H_{\Omega}=NH_{x}$
for some $x\in\Omega$. So $H_{\Omega}=N$, and $H_{\Omega}$ fixes all
$N$-orbits. Conversely, let $\mathcal{B}$ be a proper system of imprimitivity
upon which $H$ acts sharply transitively, and let $K$ ($\neq H$) be the kernel
of this action. Let $x\in X$, and let $\Omega$ be the block in $\mathcal{B}$
containing $x$. Then $H_{x}\leq H_{\Omega}=K$. As $K$ is a normal subgroup of
$H$, and as all point-stabilizers are conjugate to $H_{x}$, it follows that
$K$ is the subgroup of $H$ generated by all point-stabilizers.

##  4\. Orbits and lines

Many nonisomorphic synthetic projective lines can arise from one and the same
plane $\mathcal{P}$, and the isomorphism classes are obviously determined
precisely by the orbits of $\mathrm{Aut}(\mathcal{P})$ on the set
$\mho(\mathcal{P})$ of anti-flags in $\mathcal{P}$. Rigid planes (see also
section 8), for example, yield the maximal number of nonisomorphic projective
lines. Here is the extremal case on the other end of the spectrum.

######  Theorem 4.1.

Let $\mathcal{P}$ be a finite projective plane. Then all lines
$(\mathcal{P}_{U},\omega)$ (with $U$ a line in $\mathcal{P}$ and $\omega$ not
incident with $\omega$) are isomorphic if and only if $\mathcal{P}$ is
Desarguesian.

Proof. Obviously this is the case if and only if $\mathcal{P}$ acts
transitively on anti-flags. In that case, it follows from Ostrom and Wagner
[12] (see also Cameron and Kantor [2]). $\blacksquare$

In the infinite case, no such conclusion can hold due to model-theoretic
considerations. In [20] Tent shows the following theorem (which we only state
for projective planes, but which she obtains for all generalized polygons). We
refer to her paper for the notational use.

######  Theorem 4.2 (Tent [20]).

There exists a countable projective plane $\Upgamma$ which is not isomorphic
to $\mathbb{P}^{2}(\dj)$ for any division ring $\dj$, which contains all
finite (known and unknown) projective planes (up to isomorphism). Its
automorphism group $\mathrm{Aut}(\Upgamma)$ acts transitively on all finitely
generated $\mathcal{L}_{3}$-structures (in $\Upgamma$) of given isomorphism
type. In particular,

  * (a)

$\mathrm{Aut}(\Upgamma)$ is a group with a BN-pair;

  * (b)

$\mathrm{Aut}(\Upgamma)$ acts highly transitively on (all lines incident with)
every point, and on (all point incident with) every line;

  * (c)

if $\upgamma=(x_{0},x_{1},\ldots,x_{6}=x_{0})$ is a $6$-cycle in the incidence
graph of $\Upgamma$, then the elementwise stabilizer of $\upgamma$ acts highly
transitively on $\Upgamma_{1}(x_{1})\setminus\\{x_{0},x_{2}\\}$ (and obviously
$x_{1}$ is arbitrary in this context).

Here, $\Upgamma_{1}(x_{1})$ denotes the set of vertices adjacent to (and
different from) $x_{1}$ (in the incidence graph).

The fact that $\mathrm{Aut}(\Upgamma)$ is a group with a BN-pair translates
into the fact that its acts transitively on the ordered triangles in
$\Upgamma$. As a by-product, it acts transitively on the anti-flags, so that
$\Upgamma$ is a nonclassical projective plane for which all projective lines
$(\Upgamma^{U},\omega)$ (where $(\omega,U)$ is any anti-flag in $\Upgamma$)
are isomorphic, where $\mathcal{A}=\Upgamma^{U}$ is the affine plane obtained
by deleting the line $U$.

Projective planes $\mathcal{P}$ in which all projective-type projective lines
$(\mathcal{P},\omega)$ are isomorphic are precisely those planes with a point-
transitive automorphism group. In the finite case, there are several long-
standing conjectures which imply that such planes are Desarguesian. In the
infinite case such results cannot be true, as we have seen in Theorem 4.2.

Note that if we fix some line $U$ in a projective plane $\mathcal{P}$, the
isomorphism class of $(\mathcal{P},\omega)$, with $\omega$ a point not on $U$
solely depends on the point-orbits of $\mathrm{Aut}(\mathcal{P})_{U}$. So one
line in the plane $\mathcal{P}$ can define many nonisomorphic affine-type
projective lines. In general, this relative viewpoint is very different than
in the case of “classical” projective lines.

##  5\. Categorical setting

Define the category $\wp$ as follows. Its object class $\mathrm{ob}(\wp)$
consists of synthetic projective lines $(\mathcal{A},\omega)$, and a morphism

(7) $f:\ (\mathcal{A},\omega)\ \mapsto\
(\mathcal{A}^{\prime},\omega^{\prime})$

is simply a morphism of affine planes (points are mapped to points, lines to
lines, incidence is preserved, parallel classes are sent to parallel classes)
for which $f(\omega)=\omega^{\prime}$.

###  5.1. Compatible automorphisms

Note that there is no hope that automorphisms $\upgamma$ of
$(\mathcal{A},\omega)$ survive the following diagram:

$(\mathcal{A},\omega)$$(\mathcal{A}^{\prime},\omega^{\prime})$$\mathrm{Aut}(\mathcal{A},\omega)$$\mathrm{Aut}(\mathcal{A}^{\prime},\omega^{\prime})$$\upgamma$$\widetilde{\upgamma}$

Only automorphisms $\alpha$ of $\mathcal{A}$ “commuting with $\upgamma$” have
an interpretation as an automorphism on $\upgamma(\mathcal{A})$: if
$X,Y\in\upgamma^{-1}(Z)$ for each $Z$, point or line in
$\upgamma(\mathcal{A})$, then
$X^{\alpha},Y^{\alpha}\in\upgamma^{-1}(\widehat{Z})$, where
$\widehat{Z}=X^{\alpha\upgamma}$. Call such automorphisms $\alpha$ compatible
if both $\alpha$ and $\alpha^{-1}$ have this property. (When the order of
$\alpha$ is finite, as we will see below, $\alpha^{-1}$ automatically has this
property if $\alpha$ does.) But is easy to construct “noncompatible
automorphisms,” as we will show now. We first recall a result of Pasini [14]
on epimorphisms of generalized polygons, which generalizes an older result of
Skornjakov [18] and Hughes [7] (the latter two handling the case of projective
planes).

######  Theorem 5.1 (Skornjakov–Hughes–Pasini [18, 7, 14]).

Let $\alpha$ be a morphism from a thick (possibly infinite) generalized
$m$-gon $\mathcal{E}$ to a thick (possibly infinite) generalized $m$-gon
$\mathcal{E}^{\prime}$, with $m\geq 3$. If $\alpha$ is surjective, then either
$\alpha$ is an isomorphism, or each element in $\mathcal{E}^{\prime}$ has an
infinite fiber in $\mathcal{E}$.

Thas and Thas handle the “thin case” in [19]:

######  Theorem 5.2 (Thas and Thas [19]).

Let $\Phi$ be an epimorphism of a thick projective plane $\mathcal{P}$ onto a
thin projective plane $\Delta$ of order $(1,1)$. Then exactly two classes of
epimorphisms $\Phi$ occur (up to a suitable permutation of the points of
$\Delta$), and they are described as follows.

  * (a)

The points of $\Delta$ are $\overline{a},\overline{b},\overline{c}$, with
$\overline{a}\sim\overline{b}\sim\overline{c}\sim\overline{a}$, and put
$\Phi^{-1}(\overline{x})=\widetilde{X}$, with
$\overline{x}\in\\{\overline{a},\overline{b},\overline{c}\\}$.

Let $(\widetilde{A},\widetilde{B})$, with
$\widetilde{A}\neq\emptyset\neq\widetilde{B}$, be a partition of the set of
all points incident with a line $L$ of $\mathcal{P}$. Let $\widetilde{C}$
consist of the points not incident with $L$. Furthermore,
$\Phi^{-1}(\overline{a}\overline{b})=L$, $\Phi^{-1}(\overline{b}\overline{c})$
is the set of all lines distinct from $L$ but incident with a point of
$\widetilde{B}$ and $\Phi^{-1}(\overline{a}\overline{c})$ is the set of all
lines distinct from $L$ but incident with a point of $\widetilde{A}$.

  * (b)

The dual of (a).

Consider any thick projective plane $\mathcal{P}$, and let $\alpha$ be a
nontrivial automorphism of $\mathcal{P}$ (this is an assumption). Then there
is some line $U$ which is not fixed by $\alpha$. Let $a$ and $b$ be different
points of $\mathcal{P}$ on $U$, and suppose that $a^{\alpha}\not\mathbf{I}U$
while $b^{\alpha}\mathbf{I}U$ (note that such couples $(a,b)$ exist: just let
$b$ be the point which maps onto $U\cap U^{\alpha}$). Now let
$\upgamma:\mathcal{P}\mapsto\mathcal{P}^{\prime}$ be a morphism of projective
planes, where $\upgamma(\mathcal{P})=:\Delta$ is any triangle in
$\mathcal{P}^{\prime}$. Construct $\upgamma$ in such a way that
$\\{U\\}=\upgamma^{-1}(V)$, where $V$ is a side of $\Delta$, and such that $a$
and $b$ are contained in the same point-fiber of $\upgamma$. Then $a^{\alpha}$
and $b^{\alpha}$ are not contained in the same point-fiber of $\upgamma$, so
$\alpha$ and $\upgamma$ are not compatible (once one descends to the
appropriate affine planes).

######  Observation 5.3.

Let $C(\upgamma)\subseteq\mathrm{Aut}(\mathcal{P})$ be such that each element
of $C(\upgamma)$ is compatible with the given morphism of planes
$\upgamma:\mathcal{P}\mapsto\mathcal{P}^{\prime}$. Then $C(\upgamma)$ is a
subgroup of $\mathrm{Aut}(\mathcal{P})$, and
$\upgamma^{-1}C(\upgamma)\upgamma\cong C(\upgamma)$ is an automorphism group
of $\mathcal{P}^{\prime}$.

Proof. Let both $\alpha$ and $\beta$ be compatible with $\upgamma$, and take
$X,Y\in\upgamma^{-1}(Z)$ for some element $Z=X^{\upgamma}$ in
$\upgamma(\mathcal{P})$. Then
$X^{\alpha},Y^{\alpha}\in\upgamma^{-1}(X^{\alpha\upgamma})$, so
${(X^{\alpha})}^{\beta},{(Y^{\alpha})}^{\beta}\in\upgamma^{-1}\Big{(}{(X^{\alpha})}^{\beta\gamma}\Big{)}$.
As $\alpha^{-1}\in C(\upgamma)$ for each $\alpha\in C(\upgamma)$, it follows
that $C(\upgamma)$ is a subgroup of $\mathrm{Aut}(\mathcal{P})$. The second
part is straightforward (note that if $X\in\upgamma^{-1}(Z)$, then
$X^{\alpha\gamma}$ is independent of the choice of $X$ in the fiber, so
elements of $\upgamma^{-1}C(\upgamma)\upgamma\cong C(\upgamma)$ are well
defined). $\blacksquare$

###  5.2. Morphisms and sublines

Note that if $\gamma:\ (\mathcal{A},\omega)\ \mapsto\
(\mathcal{A}^{\prime},\omega^{\prime})$ is a morphism, then
$\gamma(\mathcal{A},\omega)$ is a (possibly degenerate) “subline” of
$(\mathcal{A}^{\prime},\omega^{\prime})$. This follows from the fact that
$\gamma(\overline{\mathcal{A}})$ (where $\overline{\mathcal{A}}$ is a
projective closure of $\mathcal{A}$ and $\gamma(\overline{\mathcal{A}})$ its
natural image) is a (possibly degenerate) projective plane (if $U,V$ are
distinct lines in $\gamma(\overline{\mathcal{A}})$, then if
$U^{\prime}\in\gamma^{-1}(U)$ and $V^{\prime}\in\gamma^{-1}(V)$, the image of
$U^{\prime}\cap V^{\prime}$ under $\gamma$ is an intersection point of $U$ and
$V$).

##  6\. Extensions and embeddings

Let $(A,\omega)$ be a synthetic projective line. We say that
$(A^{\prime},\omega^{\prime})$ is an extension of $(A,\omega)$, or that
$(A,\omega)$ is a subline of $(A^{\prime},\omega^{\prime})$ if there is an
injective morphism

(8) $\rho:\ A\ \mapsto A^{\prime}$

such that $\rho(\omega)=\omega^{\prime}$. Since $A\cong\rho(A)$, we can see
$A$ as a subplane of $A^{\prime}$. Note that there is no reason to think that
$\mathrm{Aut}(\mathcal{A},\omega)$ is a subgroup of
$\mathrm{Aut}(\mathcal{A}^{\prime},\omega^{\prime})$. In general, we expect
these groups to be unrelated, although, for example, in case $\mathcal{A}$ is
a Desarguesian plane over $\mathbb{F}_{q}$ and $\mathcal{A}^{\prime}$ a
Desarguesian plane over $\mathbb{F}_{q^{n}}$, $n\geq 1$, we indeed have a
natural inclusion of subgroups.

###  6.1. Desarguesian sublines

In the classical context, the notion of subline coincides with a line over a
subfield.

######  Theorem 6.1.

Let $(A,\omega)$ be a subline of $(A^{\prime},\omega^{\prime})$, where
$A^{\prime}=\mathbb{A}^{2}(\mathbb{F}_{q})$ is a Desarguesian affine plane
over $\mathbb{F}_{q}$. Then $U$ (line of infinity of $\rho(A)$) is a line
defined over a subfield of $\mathbb{F}_{q}$, that is, a projective of
$U^{\prime}$ (line of infinity of $A^{\prime}$) in the classical sense.

Proof. Let $\rho:\ A\ \mapsto A^{\prime}$ be an injective morphism such that
$\rho(\omega)=\omega^{\prime}$. We have that $\rho(A)$ is a subplane of
$A^{\prime}\cong\mathbb{A}^{2}(\mathbb{F}_{q})$, so $\rho(A)^{U}$ is a
projective subplane of
${A^{\prime}}^{U^{\prime}}\cong\mathbb{P}^{2}(\mathbb{F}_{q})$. It follows
immediately that $\rho(A)^{U}\cong\mathbb{P}^{2}(\ell)$ with $\ell$ some
subfield of $\mathbb{F}_{q}$, and the statement follows. $\blacksquare$

###  6.2. Self-embeddings

Note that in the infinite case, we can easily “self-embed” projective lines.
Here is an example.

Consider the classical plane $\mathbb{P}^{2}(\ell)$, $\ell$ a field. We work
with homogeneous coordinates $(x:y:z)$. Let $U$ be the line $z=0$, and let
$\omega$ be the point $(0,0,1)$. Note that each isomorphism of fields
$\alpha:\ell\cong\ell^{\prime}$ gives rise to an isomorphism of planes sending
$(0,0,1)$ to $(0,0,1)$ and sending $z=0$ to $z=0$; “the” isomorphism is given
by

(9) $(a,b,c)\mapsto(a^{\alpha},b^{\alpha},c^{\alpha}).$

Now put $\ell=k(x_{1},x_{2},x_{3},\ldots)$, and define $\alpha$ by acting as
the identity on $k$, and sending

(10) $x_{1}\ \mapsto\ x_{2}\ \mapsto\ x_{3}\ \mapsto\cdots$

Then $\ell=k(x_{1},x_{2},\ldots)$ is sent to
$\ell^{\prime}=k(x_{2},x_{3},\ldots)$, giving rise to a strict embedding of
$(\mathbb{P}^{2}(\ell^{\prime})_{U},\omega)\cong(\mathbb{P}^{2}(\ell)_{U},\omega)$
in $(\mathbb{P}^{2}(\ell)_{U},\omega)$.

###  6.3. Remark

More generally, let $\gamma$ be an isomorphism of $L=(\mathcal{A},\omega)$
onto $L^{\prime}=(\mathcal{A}^{\prime},\omega^{\prime})$ while $L^{\prime}\neq
L$ is a subline of $L$. Using the sequence

(11) $\cdots\ \mapsto\ L^{\gamma^{-2}}\ \mapsto\ L^{\gamma^{-1}}\ \mapsto\ L\
\mapsto\ L^{\gamma}\ \mapsto\ L^{\gamma^{2}}\ \mapsto\cdots$

one can now construct larger lines through the union / direct limit of this
system. We want to explore this idea a little further in the next section.

###  6.4. Field analogy

Considering Theorem 6.1, there obviously is an interesting analogy between
line extensions and field extensions. Note that any line $(\mathcal{A},\mu)$
is embedded in (many) other lines: just add an extra point $x$ to
$\overline{\mathcal{A}}$, and construct the free closure of
$\overline{\mathcal{A}}\cup\\{x\\}$ to obtain a projective plane $\Upgamma$.
If $U$ is the line at infinity of $\mathcal{A}$, then $(\Upgamma_{U},\mu)$ is
an extension of $(\mathcal{A},\mu)$. In the next section, we will make some
further remarks on the aforementioned analogy.

##  7\. Geometric closure

Call a line $(\mathcal{A},\omega)$ finite if $\mathcal{A}$ is finite. Call an
affine plane $\mathcal{A}$ set-like if its collections of points and lines are
sets; otherwise it is class-like. We use the same terminology for lines.

Let $(\mathcal{A},\omega)$ be a set-like synthetic projective line, and let
$C(\mathcal{A},\omega)$ be the category of all set-like synthetic projective
lines which contain $(\mathcal{A},\omega)$. (Note that all the planes have the
same line at infinity.) In a natural way we can make $C(\mathcal{A},\omega)$
into a direct system (by taking natural embeddings as connection morphisms).
If $(\mathcal{B},\omega)$ and $(\mathcal{C},\omega)$ are elements of
$C(\mathcal{A},\omega)$, then the free completion of
$\mathcal{B}^{U}\cup\mathcal{C}^{U}$ (where $U$ is the common line at
infinity) defines an upper bound of both lines after removing $U$. We call
$\overline{(\mathcal{A},\omega)}:=\varinjlim{C(\mathcal{A},\omega)}$ the
geometric closure of $(\mathcal{A},\omega)$. Note that
$\overline{(\mathcal{A},\omega)}$ is a class-like line, and that
$\overline{\mathcal{A}}$ (the obtained affine plane) also is class-like.

Note that if $(\mathcal{B},\omega)\in C(\mathcal{A},\omega)$, we have that

(12) $\overline{(\mathcal{A},\omega)}\ =\ \overline{(\,B,\omega)},$

showing a striking similarity with the notion of algebraic closure. Also note
that $\overline{(\mathcal{A},\omega)}$ has the same line at infinity as
$(\mathcal{A},\omega)$.

However, geometric closures of lines of type $\mathbb{P}^{2}(k)$ are obviously
much “larger” than lines of type $\mathbb{P}^{2}(\overline{k})$, where
$\overline{k}$ is an algebraic closure of $k$. We could modify the
construction by restricting $C(\mathcal{A},\omega)$ as follows:

  * •

If $(\mathcal{A},\omega)$ is finite, only consider finite and countable
extensions of $(\mathcal{A},\omega)$.

  * •

If $(\mathcal{A},\omega)$ is not finite, we only consider extensions
$(\mathcal{B},\omega)$ such that $\mathcal{A}$ and $\mathcal{B}$ have the same
order.

Even in the modified variation, if we would start from
$(\mathbb{A}^{2}(\mathbb{F}_{q}),\omega)$, then

(13) $\overline{(\mathbb{A}^{2}(\mathbb{F}_{q}),\omega)}\ \not\cong\
(\mathbb{A}^{2}(\overline{\mathbb{F}_{q}}),\omega).$

This is easy to see: $C(\mathbb{A}^{2}(\mathbb{F}_{q}),\omega)$ contains
nonclassical planes; just freely complete $\mathbb{A}^{2}(\mathbb{F}_{q})^{U}$
and an extra point, and remove $U$ again: we obtain an element in
$C(\mathbb{A}^{2}(\mathbb{F}_{q}),\omega)$ which is not a subline of
$(\mathbb{A}^{2}(\overline{\mathbb{F}_{q}}),\omega)$. On the other hand,
$\overline{(\mathbb{A}^{2}(\mathbb{F}_{q}),\omega)}$ contains
$(\mathbb{A}^{2}(\overline{\mathbb{F}_{q}}),\omega)$ as a subline.

######  Question 7.1.

Can one geometrically define a notion of geometric closure which coincides
with the notion of algebraic closure for finite Desarguesian lines?

The following variation is equally interesting.

######  Question 7.2.

Can one geometrically define a notion of geometric closure which coincides
with the notion of algebraic closure for finite Desarguesian planes?

Here the term “geometrically” must be interpreted at a synthetic-geometrical
level (and not algebro-geometric). One way to approach the problem is to
consider $\mathbb{P}^{2}(\overline{\mathbb{F}_{q}})$ for the finite field
$\mathbb{F}_{q}$, and use the fact that $\overline{\mathbb{F}_{q}}$ is the
union of its finite subfields, noting that for each positive integer $n\neq
0$, $\overline{\mathbb{F}_{q}}$ contains one unique subfield isomorphic to
$\mathbb{F}_{p^{n}}$, with $q$ a power of the prime $p$.

##  8\. Rigid projective lines, realization and AB-sets

The following question is natural.

######  Question 8.1.

Let $G$ be a given abstract group. Does there exist a projective or affine
type projective line for which $G$ is isomorphic to the full automorphism
group?

Typically we are interested in (multiply) transitive groups (think of groups
with a BN-pair of rank $1$ or even general $2$-transitive groups), but also in
the other side of the spectrum: the trivial group. Before passing to the
latter case, we will make some remarks about some specific transitive
examples. We first introduce a specification of Question 8.1. Let $\mathbb{P}$
be a projective line in any of the other theories (vector spacial, split BN-
pairs of rank $1$, algebro-geometric / topological, etc.), and suppose
$\mathrm{Aut}(\mathbb{P})$ is its automorphism group in that theory. Can we
find a projective-type or affine-type projective line which defines equivalent
permutation groups? We call lines such $\mathbb{P}$ realizable.

### Sharply $2$-transitive groups

In the finite case, synthetic lines with a sharply $2$-transitive automorphism
group can hardly be realized upon accepting the prime power conjecture. We
first recall the next theorem from Zassenhaus (cf. [15, Theorem 20.3]).

######  Theorem 8.2.

If $(H,X)$ is a finite sharply $2$-transitive permutation group, then $|X|$ is
a prime power $q$, and either $H$ acts as a one-point-stabilizer in
$\mathbf{P\Upgamma L}_{2}(q)$ in its natural action on the projective line
$\mathbb{P}^{1}(\mathbb{F}_{q})$, or
$q\in\\{5^{2},7^{2},11^{2},23^{2},29^{2}\\}$.

It follows that if $(H,X)$ is a finite (faithful) sharply $2$-transitive
permutation group, then $|X|$ is a prime power, so if $(\mathcal{A},\omega)$
is a finite projective line with a sharply $2$-transitive automorphism group,
where $\mathcal{A}$ has order $N$, then $N+1=p^{m}$ for some prime $p$ and
positive integer $m$. If the prime power conjecture would be true, we end up
with couples $(N,N+1)$ where both entries are prime powers. It is well known
that for such couples either $N$ or $N+1$ are powers of $2$, and if
$(N,N+1)\neq(8,9)$, the other one is a prime number. In the infinite case
there is much more elbow room.

### The general linear groups

Obviously, the groups $\mathsf{P\Gamma L}_{2}(\dj)$, with $\dj$ a division
ring, are realizable.

### Highly transitive lines

Let $\Upgamma$ be the plane constructed by Tent as in Theorem 4.2. Then for
any point $\omega$, we have that $\mathrm{Aut}(\Upgamma,\omega)$ acts highly
transitively on the points of $(\Upgamma,\omega)$. Now let $U$ be any line of
$\Upgamma$, and $v$ any point not incident with $U$. As
$\mathrm{Aut}(\Upgamma)$ is a group with a BN-pair, it follows that
$\mathrm{Aut}(\Upgamma)_{(U,v)}$ acts $2$-transitively on the lines incident
with $v$. Let $\mathcal{A}$ be the affine plane obtained by deleting $U$ from
$\Upgamma$. Then by Theorem 4.2(c), it follows that
$\mathrm{Aut}(\mathcal{A},v)$ acts highly transitively on the points of
$(\mathcal{A},v)$.

We now pass to the other side of the spectrum.

###  8.1. Rigid lines

Call a projective line $(\mathcal{A},\omega)$ rigid if its automorphism group
is the trivial group. This immediately translates into the fact that
$\mathrm{Aut}(\mathcal{A})_{\omega}$ is a subgroup of the group of homologies
of $\mathcal{A}$ with center $\omega$ (and axis the line at infinity).
Although it is a wide-open question whether finite rigid projective planes
exist, we will show that as a direct corollary of known results, finite (and
infinite) rigid affine and projective type lines exist. Especially in the
finite case, this is particularly interesting.

###  8.2. Kantor’s translation planes

In [9], Kantor constructed infinite classes of finite translation planes
$(\pi,U,T)$ of which the full automorphism group $\mathrm{Aut}(\pi)$ coincides
with the translation group $T$ (and hence have kernel isomorphic to
$\mathbb{F}_{2}$). More precisely, we have such planes for each prime power
$q=2^{h}$ with $h$ odd, composite and $h\geq 3$. For each point $\omega$ in
$\pi\setminus T$, $(\pi_{U},\omega)$ defines a rigid projective line. The line
$U$ itself defines a projective type projective line (it is the only line in
$\pi$ with this property).

The following problem might be interesting:

######  Problem 8.3.

Study affine planes $\mathcal{A}$ (with line at infinity $U$) which yield a
non-rigid projective type line $U$, but for every point $\omega$ a rigid
projective line $(\mathcal{A},\omega)$.

This translates into the fact that $\mathrm{Aut}(\mathcal{A})$ is nontrivial
and does not fix every parallel class, but if
$\alpha\in\mathrm{Aut}(\mathcal{A})$ fixes an affine point, then all parallel
classes are fixed.

###  8.3. Rigid planes, symmetry breaking and AB-sets

Obviously it is much harder to produce rigid projective (and affine) planes
than rigid lines. Note that a rigid projective plane yields a rigid affine
plane after deleting any line; the projective completion of a rigid affine
plane is not necessarily rigid though (the Kantor planes of the previous
section are finite examples). In this subsection we have a closer look at an
easy construction of infinite rigid projective planes through so-called “AB-
sets.”

It is an open question as to whether finite rigid projective planes exist. In
the infinite case, things are very different: Mendelsohn [11] showed that for
every group $G$, there is a projective plane $\mathcal{P}$ such that its full
automorphism group is isomorphic to $G$. The case $G=\\{\mathrm{id}\\}$ yields
rigid projective planes, and hence for every anti-flag $(a,A)$ in such a plane
$\mathcal{P}$, we have that $(\mathcal{P}_{A},a)$, respectively
$(\mathcal{P},A)$, is a rigid affine type, respectively projective type,
projective line.

It is not hard to construct infinite rigid projective planes, and so we will
describe a procedure with which one can do this.

  * •

Start with a point-line geometry $\Upgamma$ which does not violate the axioms
of a projective plane. (In this context, it will be most convenient to have
$\Upgamma$ finite.)

  * •

Leave away a point-line subconfiguration $\mathcal{C}$ of $\Upgamma$ such that
the new geometry $\Upgamma\setminus\mathcal{C}=:\mathcal{C}_{0}$ is confined
and rigid.

  * •

Free complete $\mathcal{C}_{0}$ to obtain a rigid projective plane
$\overline{\mathcal{C}_{0}}$.

Why is the plane $\overline{\mathcal{C}_{0}}$ rigid? First note that if an
automorphism of $\overline{\mathcal{C}_{0}}$ fixes $\mathcal{C}_{0}$
elementwise, then by its very definition, $\overline{\mathcal{C}_{0}}$ is
fixed elementwise by the completion of $\alpha$. Now let $\gamma$ be an
automorphism of $\overline{\mathcal{C}_{0}}$; then $\mathcal{C}_{0}^{\gamma}$
is also confined, so by [3] we must have
$\mathcal{C}_{0}^{\gamma}\leq\mathcal{C}_{0}$. As $\mathcal{C}_{0}$ is finite
by definition, it follows that $\gamma$ induces an automorphism, hence the
identity, on $\mathcal{C}_{0}$.

We propose to define automorphism-blocking sets (“AB-sets”) as follows. With
$\Upgamma$ a point-line geometry, we say that $\mathcal{C}$ is an
automorphism-blocking set of $\Upgamma$ (or that $\mathcal{C}$ blocks the
automorphisms of $\Upgamma$, or that it breaks the symmetry of $\Upgamma$), if
the following conditions are satisfied:

  * AB1

every automorphism of $\Upgamma\setminus\mathcal{C}$ extends to an
automorphism of $\Upgamma$;

  * AB2

the elementwise stabilizer $\mathrm{Aut}(\Upgamma)_{[\mathcal{C}]}$ of
$\mathcal{C}$ in $\mathrm{Aut}(\Upgamma)$ is trivial;

  * AB3

$\mathrm{Aut}(\Upgamma)_{\mathcal{C}}=\mathrm{Aut}(\Upgamma)_{[\mathcal{C}]}$.

Note that (AB1) is very natural: many interesting subgeometries of many point-
line geometries meet this property. Famous example: let $\mathcal{C}$ be a
line plus all its points in any projective plane $\Upgamma$: then all
automorphisms of the affine plane $\Upgamma\setminus\mathcal{C}$ extend
uniquely to automorphisms of the projective completion $\Upgamma$. Clearly AB-
sets survive the procedure described above if the complements are confined:
let $\beta$ be an automorphism of $\Upgamma\setminus\mathcal{C}$; then by
(AB1) it extends to an automorphism $\overline{\gamma}$ of $\Upgamma$. Since
$\overline{\gamma}$ stabilizes $\Upgamma\setminus\mathcal{C}$, it also
stabilizes $\mathcal{C}$, so by (AB3), it fixes $\mathcal{C}$ elementwise. By
(AB2), $\overline{\gamma}$ is trivial, so $\gamma$ also is. So what we want to
construct infinite rigid projective planes, is AB-sets for which the
complement is confined.

######  Remark 8.4.

We strongly suspect that (general, minimal and maximal) AB-sets (in various
types of geometries) are interesting in their own right to study. Note that
they are subgeometries which see the geometry of the ambient geometry, but
don’t see its symmetry.

###  8.4. Examples

There are may interesting AB-sets (with confined complement), starting from
various interesting geometries. We provide some classes of examples, starting
from Kantor’s planes (cf. subsection 8.2).

### In Kantor planes

Let $\mathcal{P}$ be a projective Kantor plane of order $N=2^{n}$ with
translation line $U$. Let $\mathcal{C}=(\\{u\\},\emptyset,\mathbf{I})$ be the
subgeometry defined by the point $u$ which is not incident with $U$. Then
obviously all automorphisms of $\mathcal{P}\setminus\\{u\\}$ extend to
automorphisms of $\mathcal{P}$, but
$\mathrm{Aut}(\mathcal{P})_{\\{u\\}}=\\{\mathrm{id}\\}$ since
$\mathrm{Aut}(\mathcal{P})$ acts sharply transitively on the points not
incident with $U$. Since $\mathcal{P}\setminus\mathcal{C}$ is confined, it
follows that the free completion of $\mathcal{P}\setminus\mathcal{C}$ is a
rigid projective plane. Many other AB-sets can obviously be found in Kantor
planes.

Note that in general (say, in geometries with more symmetry), AB-sets usually
are much more complicated to find, and will need a good understanding of the
fixed elements structures of elements in automorphism groups.

### From rigid ovals

Let $\mathcal{P}$ be a finite projective plane of order $N\geq 3$, and let
$\mathcal{O}$ be a rigid oval in $\mathcal{P}$ (a set of $N+1$ points no three
of which are collinear, for which $\mathrm{Aut}(\mathcal{P})_{\mathcal{O}}$
induces the identity on $\mathcal{O}$). Then $\mathcal{O}$ is an AB-set in
$\mathcal{P}$ and $\mathcal{P}\setminus\mathcal{O}$ is confined. For, let
$\gamma$ be an automorphism of $\mathcal{P}\setminus\mathcal{O}$. We only have
to show that $\alpha$ naturally defines an action on $\mathcal{O}$. So let
$U,V$ be two different lines which meet in a point $x\in\mathcal{O}$; if
$U^{\gamma}$ and $V^{\gamma}$ do not meet in a point of $\mathcal{O}$, then
$U^{\gamma}\cap V^{\gamma}=\\{v\\}$ with $v$ a point in
$\mathcal{P}\setminus\mathcal{O}$. But then $v^{\gamma^{-1}}$ must be a point
of $U\cap V$, while it is not a point of $\mathcal{O}$, contradiction. It
follows that the action on $\mathcal{O}$ is well defined, and so $\gamma$
extends to an automorphism $\overline{\gamma}$ of $\mathcal{P}$. Finally, let
$\alpha\in\mathrm{Aut}(\mathcal{P})_{\mathcal{O}}$. As $\mathcal{O}$ is rigid,
it fixes every point of $\mathcal{O}$. Now let $u$ be a point of
$\mathcal{P}\setminus\mathcal{O}$, and let $U,V$ be two different lines on $u$
which meet $\mathcal{O}$. If $U$ or $V$ is a tangent line of $\mathcal{O}$ at
a point $w$ of $\mathcal{O}$, then obviously it is fixed (tangent lines are
unique); if $U$ or $V$ meet $\mathcal{O}$ in distinct points, then obviously
it is also fixed. So $u$ is also fixed, and $\alpha$ is the identity. It
follows that $\mathcal{O}$ is an AB-set.

The principle used here is very interesting: starting from a simple rigid
structure, one constructs a more complex one. Of course, rigid ovals form just
one set of rigid objects which yield AB-sets and hence rigid planes. One could
also have started from rigid geometric hyperplanes in finite generalized
quadrangles and use Pralle’s theory of affine quadrangles [16] to show that
these form AB-sets.

### Rigid towers

As soon as one has constructed one rigid plane $\Upgamma_{0}$, it is easy to
construct a countable “tower” of rigid planes: take away one point $x_{0}$,
and freely construct the rigid plane
$\Upgamma_{1}:=\overline{\Upgamma\setminus\\{x\\}}$; now take away one point
$x_{1}$ in $\Upgamma_{1}$ to construct
$\Upgamma_{2}:=\overline{\Upgamma_{1}\setminus\\{x_{1}\\}}$, etc.:

(14) $\Upgamma_{0}\ \subset\ \Upgamma_{1}\ \subset\ \Upgamma_{2}\ \ \subset\
\cdots$

## References

  * [1] F. Buekenhout. Foundations of one dimensional projective geometry based on perspectivities, Abh. Math. Sem. Univ. Hamburg 43 (1975), 21–29.
  * [2] P. J. Cameron and W. M. Kantor. 2-Transitive and antiflag transitive collineation groups of finite projective spaces, J. Algebra 60 (1979), 384–422.
  * [3] R. Heartshorne. Foundations of Projective Geometry, Ishi Press, 2009.
  * [4] C. H. Hering, W. M. Kantor and G. M. Seits, Finite groups with a split BN-pair of Rank $1$, J. Algebra 20 (1972), 435–475.
  * [5] J. W. P. Hirschfeld. Projective Geometries over Finite Fields, Oxford Mathematical Monographs, Oxford Science Publications, The Clarendon Press, Oxford University Press, New York, 1979. xii+474 pp.
  * [6] J. W. P. Hirschfeld and J. A. Thas. General Galois Geometries, Oxford Mathematical Monographs, Oxford Science Publications, The Clarendon Press, Oxford University Press, New York, 1991. xiv+407 pp.
  * [7] D. R. Hughes. On homomorphisms of projective planes, 1960 Proc. Sympos. Appl. Math. Vol. 10, pp. 45–52, American Mathematical Society, Providence, R.I.
  * [8] D. R. Hughes and F. C. Piper. Projective Planes, Graduate Texts in Mathematics, Vol. 6. Springer–Verlag, New York–Berlin, 1973. x+291 pp.
  * [9] W. M. Kantor. Projective planes of order $q$ whose collineation groups have order $q^{2}$, J. Algebraic Combin. 3 (1994), 405–425.
  * [10] MathOverflow. Generation of permutation groups by fixed elements subgroups,
https://mathoverflow.net/questions/394384/generation-of-permutation-groups-by-
fixed-elements-subgroups.

  * [11] E. Mendelsohn. Every group is the collineation group of some projective plane, J. Geom. 2 (1972), 97–106.
  * [12] Ostrom and Wagner. On projective and affine planes with transitive collineation groups, Math. Z. 71 (1959), 189–199.
  * [13] G. Paolini. The class of non-Desarguesian projective planes is Borel complete, Proc. Amer. Math. Soc. 146 (2018), 4927–4936
  * [14] A. Pasini. The nonexistence of proper epimorphisms of finite thick generalized polygons, Geom. Dedicata 15 (1984), 389–397.
  * [15] D. Passman. Permutation Groups. Math. Lect. Notes Ser., W. A. Benjamin, Inc., Amsterdam–New York, 1968.
  * [16] H. Pralle. Affine generalized quadrangles — an axiomatization, Geom. Dedicata (2001) 84, 1–23.
  * [17] E. .E. Shult. On a class of doubly transitive groups, Illinois J. Math. 16 (1972), 434–445.
  * [18] L. A. Skornjakov. On homomorphisms of projective planes and $T$-homomorphisms of ternary rings, Math. Sbornik 43 (1957), 285–294.
  * [19] J. A. Thas and K. Thas. Epimorphisms of generalized polygons A: the planes, quadrangles and hexagons, preprint (2021), 18 pp.
  * [20] K. Tent. Free polygons, twin trees, and CAT(1)-spaces, Pure Appl. Math, Quart. 7 (2011), 1037–1052.
  * [21] K. Thas. Virtual motives for synthetic geometries, A. Definition and properties of $K_{0}(\mathcal{Q}_{\ell})$, preprint (2021), 56 pp.


# Towards Modelling and Verification of Social Explainable AI

Damian Kurpiewski,1,3 Wojciech Jamroga,1,2 and Teofil Sidoruk1,4
1Institute of Computer Science, Polish Academy of Sciences, Warsaw, Poland
2Interdisciplinary Centre for Security, Reliability, and Trust, SnT,
University of Luxembourg
3Faculty of Mathematics and Computer Science, Nicolaus Copernicus University,
Toruń, Poland
4Faculty of Mathematics and Information Science, Warsaw University of
Technology, Warsaw, Poland
<EMAIL_ADDRESS>{d.kurpiewski<EMAIL_ADDRESS>

###### Abstract

Social Explainable AI (SAI) is a new direction in artificial intelligence that
emphasises decentralisation, transparency, social context, and focus on the
human users. SAI research is still at an early stage. Consequently, it
concentrates on delivering the intended functionalities, but largely ignores
the possibility of unwelcome behaviours due to malicious or erroneous
activity. We propose that, in order to capture the breadth of relevant
aspects, one can use models and logics of strategic ability, that have been
developed in multi-agent systems. Using the STV model checker, we take the
first step towards the formal modelling and verification of SAI environments,
in particular of their resistance to various types of attacks by compromised
AI modules.

##  1 INTRODUCTION

Elements of artificial intelligence have become ubiquitous in daily life,
being involved in social media, car navigation, recommender algorithms for
music and films, and so on. They also provide back-end solutions to many
business processes, resulting in a huge societal and economical impact. The
idea of _Social Explainable AI (SAI)_ represents an interesting new direction
in artificial intelligence, which emphasises decentralisation, human-
centricity, and explainability [31, 7]. This is in line with the trend to move
away from classical, centralised machine learning, not only for purely
technical reasons such as scalability constraints, but also to meet the
growing ethical expectations regarding transparency and trustworthiness of
data storage and computation [9, 26]. The aim is also to put the human again
in the spotlight, rather than concentrate on the technological infrastructure
[6, 32, 11].

SAI is a new concept, and a subject of ongoing research. It still remains to
be seen if it delivers AI solutions that are effective, transparent, and
mindful of the user. To this end, it should be extensively studied not only in
the context of its intended properties, but also the possible side effects of
interaction that involves AI components and human users in a complex
environment. In particular, we should carefully analyse the possibilities of
adversarial misuse and abuse of the interaction, e.g., by means of
impersonation or man-in-the-middle attacks [8, 12]. In those scenarios, one or
more nodes of the interaction network are taken over by a malicious party that
tries to disrupt communication, corrupt data, and/or spread false information.
Clearly, the design of Social AI must be resistant to such abuse; otherwise it
will be sooner or later exploited. While the topic of adversarial attacks on
machine learning algorithms has recently become popular [13, 18, 20], the
research on SAI has been focused only on its expected functionalities. This is
probably because SAI communities are bound to be conceptually,
computationally, and socially complex. A comprehensive study of their possible
_unintended_ behaviors is a highly challenging task.

Here, we propose that _formal methods for multi-agent systems_ [33, 29]
provide a good framework for multifaceted analysis of Social Explainable AI.
Moreover, we put forward a new methodology for such studies, based on the
following hypotheses:

  1. 1.

It is essential to formalise and evaluate multi-agent properties of SAI
environments. In particular, we must look at the properties of interaction
between SAI components that go beyond joint, fully orchestrated action towards
a common predefined goal. This may include various relevant functionality and
safety requirements. In particular, we should assess the impact of adversarial
play on these requirements.

  2. 2.

Many of those properties are underpinned by _strategic ability_ of agents and
their groups to achieve their goals [27, 2, 4]. In particular, many
functionality properties refer to the ability of legitimate users to complete
their selected tasks. Conversely, safety and security requirements can be
often phrased in terms of the inability of the “bad guys” to disrupt the
behavior of the system.

  3. 3.

Model checking [5] provides a well-defined formal framework for the analysis.
Moreover, existing model checking tools for multi-agent systems, such as MCMAS
[24] and STV [23] can be used to formally model, visualise, and analyse SAI
designs with respect to the relevant properties.

  4. 4.

Conversely, SAI can be used as a testbed for cutting-edge methods of model
checking and their implementations.

In the rest of this paper, we make the first step towards formal modelling,
specification, and verification of SAI. We model SAI by means of _asynchronous
multi-agent systems (AMAS)_ [16], and formalise their properties using
formulas of temporal-strategic logic $\mathbf{ATL_{\mathrm{}}^{*}}$ [2, 28].
For instance, one can specify that a malicious AI component can ensure that
the remaining components will never be able to build a global model of desired
quality, even if they all work together against the rogue element.
Alternatively, strategies of the “good” modules can be considered, in order to
check whether a certain threshold of non-compromised agents is sufficient to
prevent a specific type of attack. Finally, we use the STV model checker [23]
to verify the formalised properties against the constructed models. The
verification is done by means of the technique of _fixpoint approximation_ ,
proposed and studied in [17].

Note that this study does _not_ aim at focused in-depth verification of a
specific machine learning procedure, like in [34, 3, 19, 1]. Our goal is to
represent and analyse a broad spectrum of interactions, possibly at the price
of abstraction that leaves many details out of the formal model.

The ideas, reported here, are still work in progress, and the results should
be treated as preliminary.

##  2 SOCIAL EXPLAINABLE AI

The framework of _Social Explainable AI, or SAI_ [31, 7, 11] aims to address
several drawbacks inherent to the currently dominant AI paradigm. In
particular, today’s state of the art machine learning (ML)-based AI systems
are typically centralised. The sheer scale of Big Data collections, as well as
the complexity of deep neural networks that process them, mean that
effectively these AI systems act as opaque black boxes, non-interpretable even
for experts. This naturally raises issues of privacy and trustworthiness,
further exacerbated by the fact that storing an ever-increasing amount of
sensitive data in a single, central location might eventually become
unfeasible, also for non-technical reasons such as local regulations regarding
data ownership.

In contrast, SAI envisions novel ML-based AI systems with a focus on the
following aspects:

  * •

Individuation: a “Personal AI Valet” (PAIV) associated with each individual,
acting as their proxy in a complex ecosystem of interacting PAIVs;

  * •

Personalisation: processing data by PAIVs via explainable AI models tailored
to the specific characteristics of individuals;

  * •

Purposeful interaction: PAIVs build global AI models or make collective
decisions starting from the local models by interacting with one another;

  * •

Human-centricity: AI algorithms and PAIV interactions driven by quantifiable
models of the individual and social behaviour of their human users;

  * •

Explainability by design: extending ML techniques through quantifiable human
behavioural models and network science analysis.

The current attempts at building SAI use _gossip learning_ as the ML regime
for PAIVs [30, 14, 15]. An experimental simulation tool to assess the
effectiveness of the process and functionality of the resulting AI components
is available in [25]. In this paper, we take a different path and focus on the
multi-agent interaction in the learning process. We model the network of PAIVs
as an _asynchronous multi-agent system (AMAS)_ , and formalise its properties
as formulas of _alternating-time temporal logic (
$\mathbf{ATL_{\mathrm{}}^{*}}$)_. The formal framework is introduced in
Section 3. In Section 4, we present preliminary multi-agent models of SAI, and
show several attacks that can be modelled that way. Finally, we formalise
several properties, and conduct model checking experiments in Section 5.

##  3 WHAT AGENTS CAN ACHIEVE

In this section, we introduce the formalism of Asynchronous Multi-agent
Systems (AMAS) [16], as well as the syntax and semantics of Alternating-time
Temporal Logic $\mathbf{ATL_{\mathrm{}}^{*}}$ [2, 28], which allows for
specifying relevant properties of SAI models, in particular the _strategic
ability_ of agents to enforce a goal.

###  3.1 Asynchronous MAS

AMAS can be thought of as networks of automata, where each component
corresponds to a single agent.

######  Definition 1 (AMAS [16]).

An _asynchronous multi-agent system_ (AMAS) consists of $n$ agents
$\mathcal{A}=\\{{1,\dots,n}\\}$, each associated with a 7-tuple
$A_{i}=(L_{i},\iota_{i},Evt_{i},R_{i},T_{i},\mathit{PV}_{i},V_{i})$, where:

  * •

$L_{i}=\\{l_{i}^{1},\ldots,l_{i}^{n_{i}}\\}\neq\emptyset$ is a finite set of
_local states_ ;

  * •

$\iota_{i}\in L_{i}$ is an _initial local state_ ;

  * •

$Evt_{i}=\\{e_{i}^{1},\ldots,e_{i}^{m_{i}}\\}\neq\emptyset$ a finite set of
_events_ ;

  * •

$R_{i}:L_{i}\to 2^{Evt_{i}}\setminus\\{\emptyset\\}$ is a _repertoire of
choices_ , assigning available subsets of events to local states;

  * •

$T_{i}:L_{i}\times Evt_{i}\rightharpoonup L_{i}$ is a (partial) _local
transition function_ such that $T_{i}(l_{i},e)$ is defined iff $e\in
R_{i}(l_{i})$. That is, $T_{i}(l,e)$ indicates the result of executing event
$e$ in state $l$ from the perspective of agent $i$;

  * •

$\mathit{PV}_{i}$ is a set of the agent’s _local propositions_ , with
$\mathit{PV}_{j}$, $\mathit{PV}_{k}$ (for $j\neq k\in\mathcal{A})$ assumed to
be disjoint;

  * •

$V_{i}:L_{i}\rightarrow\mathcal{P}({\mathit{PV}_{i}})$ is a _valuation
function_.

Furthermore, we denote:

  * •

by $Evt=\bigcup_{i\in\mathcal{A}}Evt_{i}$, the set of all events;

  * •

by $L=\bigcup_{i\in\mathcal{A}}L_{i}$, the set of all local states;

  * •

by $Agent(e)=\\{{i\in\mathcal{A}\mid e\in Evt_{i}}\\}$, the set of all agents
which have event $e$ in their repertoires;

  * •

by $\mathit{PV}=\bigcup_{i\in\mathcal{A}}\mathit{PV}_{i}$ the set of all local
propositions.

The _model_ of an AMAS provides its execution semantics with asynchronous
interleaving of private events and synchronisation on shared ones.

######  Definition 2 (Model).

The _model_ of an AMAS is a 5-tuple $\mathit{M}=(\mathcal{A},S,\iota,T,V)$,
where:

  * •

$\mathcal{A}$ is the set of _agents_ ;

  * •

$S\subseteq L_{1}\times\ldots\times L_{n}$ is the set of _global states_ ,
including all states reachable from $\iota$ by $T$ (see below);

  * •

$\iota=(\iota_{1},\dots,\iota_{n})\in S$ is the _initial global state_ ;

  * •

$T:S\times Evt\rightharpoonup S$ is the _global transition function_ , defined
by $T(s_{1},e)=s_{2}$ iff $T_{i}(s_{1}^{i},e)=s^{i}_{2}$ for all $i\in
Agent(e)$ and $s_{1}^{i}=s^{i}_{2}$ for all $i\in\mathcal{A}\setminus
Agent(e)$ (where $s_{j}^{i}\in L_{i}$ is agent $i$’s local component of
$s_{j}$);

  * •

$V:S\rightarrow 2^{\mathit{PV}}$ is the _global valuation function_ , defined
as $V(l_{1},\dots,l_{n})=\bigcup_{i\in\mathcal{A}}V_{i}(l_{i})$.

###  3.2 Strategic Ability

Linear and branching-time temporal logics, such as $\mathbf{LTL}$ and
$\mathbf{CTL^{\star}}$ [10], have long been used in formal verification. They
enable to express properties about _how_ the state of the system will (or
should) evolve over time. However, in systems that involve autonomous agents,
whether representing human users or AI components it is usually of interest
_who_ can direct its evolution a particular way.

$\mathbf{ATL_{\mathrm{}}^{*}}$ [2] extends temporal logics with _strategic
modalities_ that allow for reasoning about such properties. The operator
$\langle\\!\langle{A}\rangle\\!\rangle_{{}_{\\!\mathit{}}}\gamma$ says that
agents in group (coalition) $A$ have a _strategy_ to enforce property
$\gamma$. That is, as long as agents in $A$ select events according to the
strategy, $\gamma$ will hold no matter what the other agents do.
$\mathbf{ATL_{\mathrm{}}^{*}}$ has been one of the most important and popular
agent logics in the last two decades.

######  Definition 3 (Syntax of $\mathbf{ATL_{\mathrm{}}^{*}}$).

The language of $\mathbf{ATL_{\mathrm{}}^{*}}$ is defined by the grammar:

$\varphi::=\mathsf{{p}}\mid\neg\varphi\mid\varphi\wedge\varphi\mid\langle\\!\langle{A}\rangle\\!\rangle_{{}_{\\!\mathit{}}}\gamma$,

$\gamma::=\varphi\mid\neg\gamma\mid\gamma\land\gamma\mid\mathrm{X}\,\gamma\mid\gamma\,\mathrm{U}\,\gamma$,

where $\mathsf{{p}}\in\mathit{PV}$ and $A\subseteq\mathcal{A}$. The
definitions of Boolean connectives and temporal operators $\mathrm{X}\,$
(“next”) and $\,\mathrm{U}\,$ (“strong until”) are standard; remaining
operators $\,\mathrm{R}\,$ (“release”), $\mathrm{G}\,$ (“always”), and
$\mathrm{F}\,$ (“sometime”) can be derived as usual.

Various types of strategies can be defined, based on the state information and
memory of past states available to agents [28]. In this work, we focus on
_imperfect information, imperfect recall strategies_.

######  Definition 4 (Strategy).

A _memoryless imperfect information strategy_ for agent $i\in\mathcal{A}$ is a
function $\sigma_{i}\colon L_{i}\to 2^{Evt_{i}}\setminus\emptyset$ such that
$\sigma_{i}(l)\in R_{i}(l)$ for each local state $l\in L_{i}$. A _joint
strategy_ $\sigma_{A}$ of coalition $A\subseteq\mathcal{A}$ is a tuple of
strategies $\sigma_{i}$, one for each agent $i\in A$.

The outcome set of a strategy collects all paths consistent with it, i.e. that
may occur when the coalition follows the chosen strategy, while opposing
agents choose freely from their protocols.

######  Definition 5 (Outcome).

The _outcome_ of strategy $\sigma_{A}$ in global state $s\in S$ of model
$\mathit{M}$, denoted by $out_{\mathit{M}}(s,\sigma_{A})$, is the set of all
paths $\pi=s_{0}e_{0}s_{1}e_{1}\dots$, such that $\pi\in
out_{\mathit{M}}(s,\sigma_{A})$ iff $s_{0}=s$, and for each $j\geq 0$
$\begin{cases}e_{j}\in\sigma_{A}(s_{j}^{i})&\text{for every agent }i\in
Agent(e_{j})\cap A,\\\ e_{j}\in\bigcup R_{i}(s_{j}^{i})&\text{for every agent
}i\in Agent(e_{j})\setminus A,\end{cases}$

where $s^{i}$ denotes the local component $l_{i}$ of $s$.

######  Definition 6 (Asynchronous semantics of $\mathbf{ATL_{\mathrm{}}^{*}}$
[16]).

The asynchronous semantics of the strategic modality in
$\mathbf{ATL_{\mathrm{}}^{*}}$ is defined by the following clause:

$\mathit{M},s\models\langle\\!\langle{A}\rangle\\!\rangle_{{}_{\\!\mathit{}}}\gamma$
iff there is a strategy $\sigma_{A}$ such that
$out_{\mathit{M}}(s,\sigma_{A})\neq\emptyset$ and, for each path $\pi\in
out_{\mathit{M}}(s,\sigma_{A})$, we have $\mathit{M},\pi\models\gamma$.

The remaining clauses for temporal operators and Boolean connectives are
standard, see [10].

##  4 MODELS

|  ⬇ Agent AI1:  init: start %% —Phase1: Gathering data—
start_gathering_data: start -> gather gather_data: gather -[AI1_data<2]>
gather [AI1_data+=1]  %% 1: Incomplete data stop_gathering_data: gather
-[AI1_data < 1]> data_ready [AI1_data=0, AI1_data_completion=1]  %% 2:
Complete data stop_gathering_data: gather -[1 <= AI1_data < 2]> data_ready
[AI1_data=0, AI1_data_completion=2]  %% 3: Too much data stop_gathering_data:
gather -[2 <= AI1_data]> data_ready [AI1_data=0, AI1_data_completion=3]
skip_gathering_data: start -> data_ready %% —Phase2: Learning (building local
model)—  start_learning: data_ready -> learn keep_learning: learn
-[AI1_information < 2]> learn [AI1_information+=AI1_data_completion]  %% 1:
Incomplete model stop_learning: learn -[AI1_information < 1 and
AI1_model_quality > 0]> educated [AI1_information=0, AI1_model_status=1,
AI1_model_quality-=1]  stop_learning: learn -[AI1_information < 1 and
AI1_model_quality <= 0]> educated [AI1_information=0, AI1_model_status=1]  %%
2: Complete model stop_learning: learn -[1 <= AI1_information < 2 and
AI1_model_quality < 2]> educated [AI1_information=0, AI1_model_status=2,
AI1_model_quality+=1]  stop_learning: learn -[1 <= AI1_information < 2 and
AI1_model_quality >= 2]> educated [AI1_information=0, AI1_model_status=2]  %%
3: Overtrained model stop_learning: learn -[2 <= AI1_information and
AI1_model_quality > 0]> educated [AI1_information=0, AI1_model_status=3,
AI1_model_quality-=1]  stop_learning: learn -[2 <= AI1_information and
AI1_model_quality <= 0]> educated [AI1_information=0, AI1_model_status=3]
skip_learning: data_ready -> sharing %% —Phase3: Sharing local models—
start_sharing: educated -> sharing %% Share local model and get average
quality of both models %% receive left shared share_3_with_1: sharing ->
sharing2 [AI1_model_quality=%AI3_model_quality]  %% send right shared
share_1_with_2: sharing2 -> sharing3 end_sharing: sharing3 -> end %% —Phase4:
End—  wait: end -> end repeat: end -> learn
---
|
$q_{0}$$q_{1}$$q_{2}$$q_{3}$$q_{4}$$q_{5}$$q_{6}$$q_{7}$$q_{8}$$start\\_gathering$$\mathsf{{[AI1\\_data<1]}}$
$stop\\_gathering$ $\mathsf{{AI1\\_data=0,AI1\\_completion=1}}$
$\mathsf{{[1<=AI1\\_data<2]}}$
$stop\\_gathering$$\mathsf{{AI1\\_data=0,AI1\\_completion=2}}$$\mathsf{{[2<=AI1\\_data]}}$
$stop\\_gathering$$\mathsf{{AI1\\_data=0,AI1\\_completion=3}}$$skip\\_gathering$$start\\_learning$$\mathsf{{[AI1\\_info<1\land
AI1\\_mqual>0]}}$
$stop\\_learning$$\mathsf{{AI1\\_info=0,AI1\\_mstatus=1,AI1\\_mqual-=1}}$$\mathsf{{[AI1\\_info<1\land
AI1\\_mqual\leq 0]}}$
$stop\\_learning$$\mathsf{{AI1\\_info=0,AI1\\_mstatus=1}}$$\mathsf{{[1\leq
AI1\\_info<2\land AI1\\_mqual<2]}}$
$stop\\_learning$$\mathsf{{AI1\\_info=0,AI1\\_mstatus=2,AI1\\_mqual+=1}}$$\mathsf{{[1\leq
AI1\\_info<2\land AI1\\_mqual\geq 2]}}$
$stop\\_learning$$\mathsf{{AI1\\_info=0,AI1\\_mstatus=2}}$$\mathsf{{[2\leq
AI1\\_info\land AI1\\_mqual>0]}}$
$stop\\_learning$$\mathsf{{AI1\\_info=0,AI1\\_mstatus=3,AI1\\_mqual-=1}}$$\mathsf{{[2\leq
AI1\\_info\land AI1\\_mqual\leq 0]}}$
$stop\\_learning$$\mathsf{{AI1\\_info=0,AI1\\_mstatus=3}}$$skip\\_learning$$start\\_sharing$$share\\_3\\_with\\_1$$\mathsf{{AI1\\_mqual=\%AI3\\_mqual}}$$share\\_1\\_with\\_2$$end\\_sharing$$repeat$$\mathsf{{[AI1\\_data<2]}}$
$gather\\_data$ $\mathsf{{AI1\\_data+=1}}$ $\mathsf{{[AI1\\_info<2]}}$
$keep\\_learning$$\mathsf{{AI1\\_info+=AI1\\_completion}}$$wait$
---
Figure 1: Specification and graphical representation of the honest AI agent
Figure 2: Visualization of honest AI in STV

The first step towards the verification of the interaction between agents in
Social Explainable AI is a thorough and detailed analysis of the underlying
protocol. We begin by looking into the actions performed and the messages
exchanged by the machines that take part in the learning phase. Then, when we
can grasp the whole overview of the system, we can start designing multi-agent
models. Usually, the system is too detailed to be modelled as it is. In that
case, we create the abstract view of the system.

###  4.1 Agents

In this work, we focus on the learning phase of the protocol. We model each
machine equipped with an AI module as a separate agent. The local model of an
AI agent consists of three phases: the data gathering phase, the learning
phase and the sharing phase.

Data gathering phase. In this phase, the agent is able to gather the data
required for the learning phase. The corresponding action can be performed
multiple times, each time increasing the local variable that represents the
amount of data gathered. At the end of this phase, the amount of gathered data
is analysed and, depending on the exact value, the agent’s preparation is
marked as incomplete, complete or too much data. From this phase the agent
goes directly to the learning phase.

Learning phase. The agent can use the previously gathered data to train his
local AI model. The effectiveness of the training depends on the amount of
data gathered. Excessive data means that the model can be easily overtrained,
while insufficient data may lead to more iterations required to properly train
the model. The training action can be performed multiple times each time
increasing the local variable related to the quality of the model. At the end
of this phase the internal AI model can end to be overtrained, undertrained or
properly trained. After this phase the agent is required to share his model
with other agents.

⬇ Agent Mim:  init: start shared share_1_with_mim: start -> start
[Mim_model_quality=AI1_model_quality]  shared share_mim_with_1: start -> start
shared share_2_with_mim: start -> start [Mim_model_quality=AI2_model_quality]
shared share_mim_with_2: start -> start

Figure 3: Specification of the Man in the Middle agent

$q_{0}$$\mathsf{{Mim\\_model\\_quality=AI1\\_model\\_quality}}$$share\\_1\\_with\\_mim$$share\\_2\\_with\\_mim$$\mathsf{{Mim\\_model\\_quality=AI2\\_model\\_quality}}$$share\\_mim\\_with\\_1$$share\\_mim\\_with\\_2$

Figure 4: Graphical representation of Man in the Middle

Sharing phase. Agents share their local AI models with each other following a
simple sharing protocol. This protocol is based on the packet traversal in the
ring topology. Each agent receives the model from the agent with previous ID
and sends his model to the agent with next ID, while the last agent shares his
model with the first agent to close the ring. In order to avoid any deadlocks,
each agent with odd ID first receives the model and then sends his own, and
each agent with even ID first sends his own model and then receives the model
from the agent before him.

When receiving the model, the agent can either accept it or reject it, and his
decision is based on the quality of the model being shared. After accepting
the model, the agent merges it with his own and the resulting model quality is
the maximum of the two.

After the sharing phase, the agent can go back to the learning phase to
further train his model.

To formalize the details of the procedure, we have utilised the open-source
experimental model checker STV [23], which was used e.g. to model and verify
the real-world voting protocol Selene [22]. Figure 1 presents the STV code
specifying the behavior of the honest AI component (left) and its detailed
representation as an AMAS (right). Figure 2 shows the visualization of the
component, produced by the tool.

###  4.2 Attacks

The model described in Section 4.1 reflects the ideal scenario in which each
agent is honest and directly follows the implemented protocol. Of course, it
is known to not always be the case. One of the machines can malfunction, which
can result in taking actions not permitted in the protocol. On the other hand,
the malicious software can also infect one of the agents, forcing him to
function improperly. In our work we research two possible scenarios of the
attack: the man in the middle attack and the impersonator attack.

Man in the middle. Let us assume that there exists another, dishonest agent.
We will call him the intruder. This agent does not participate in the data
gathering or learning phases, but he is particularly interested in the sharing
phase. The intruder can intercept any model that is being sent by one of the
honest agents and then pass it to any other agent. The STV code for the man-
in-the-middle attacker is presented in Figure 3, and its graphical
representation in Figure 4.

⬇ Agent AI2:  init: start set_quality_0: start -> set_quality
[AI2_model_quality=0]  set_quality_1: start -> set_quality
[AI2_model_quality=1]  set_quality_2: start -> set_quality
[AI2_model_quality=2]  shared share_2_with_3: set_quality -> sharing shared
share_1_with_2: sharing -> start

Figure 5: Specification of the Impersonator agent Figure 6: Graphical
representation of Impersonator in STV Figure 7: Model of SAI with one honest
agent Figure 8: Model of SAI with two honest agents

Impersonator. In this scenario, one of the AI agents is infected with
malicious code that results in unwanted behavior. The agent cannot participate
in the data gathering or learning phases, but can share his model with others
following the sharing protocol. The difference between the honest agent and
the impersonator is that the latter can fake the quality of his local AI
model, hence tricking the next agent into accepting it. The STV code and its
visualization for Impersonator are presented in Figures 5 and 6.

##  5 EXPERIMENTS

The STV tool can be used to combine the modules presented in Figures 1–6, and
generate the global model of interaction. We present the output in Figures 7
(for the system with only one honest AI agent) and 8 (for two honest agents).
The models can provide invaluable insights into the structure of possible
interactions in the system. Still, a detailed visual scrutiny is possible only
in the simplest cases due to the state-space and transition-space explosion.

In more complex instances, we can use STV to attempt an automated verification
of strategic-temporal requirements. Since model checking of strategic ability
is hard for scenarios with partial observability ($\mathbf{{NP}}$-hard to
undecidable, depending on the precise syntax and semantics of the
specification language), exact verification is infeasible. Instead, we use the
technique of _fixpoint approximation_ , proposed in [17], and implemented in
STV. In what follows, we summarise the experimental results obtained that way.

Models and formulas. The scalable class of models has been described in detail
in Section 4. In the model checking experiments, have used two variants of the
system specification, one with a possible impersonation attack, and the other
one with the possibility of a man-in-the-middle attack. In each case, we
verified the following formulas:

  * •

$\phi_{1}\equiv\langle\\!\langle{I}\rangle\\!\rangle_{{}_{\\!\mathit{}}}\mathrm{G}\,(shared_{p}\rightarrow(\bigwedge_{i\in[1,n]}mqual_{i}\leq
k))$

  * •

$\phi_{2}\equiv\langle\\!\langle{I}\rangle\\!\rangle_{{}_{\\!\mathit{}}}\mathrm{G}\,(shared_{p}\rightarrow(\bigvee_{i\in[1,n]}mqual_{i}\leq
k))$

Formula $\phi_{1}$ checks whether the Intruder has a strategy to ensure that
all honest agents will not achieve quality greater than $k$, while the formula
$\phi_{2}$ checks whether the same is possible for at least one agent.

Configuration of the experiments. The experiments have been conducted with the
latest version of STV [21]. The test platform was a server equipped with
ninety-six 2.40 GHz Intel Xeon Platinum 8260 CPUs, 991 GB RAM, and 64-bit
Linux.

Results. We present the verification results in Figures 9 and 10. #Ag
specifies the scalability factor, namely the number of agents in the system.
#st and #tr report the number of global states and transitions in the
resulting model of the system, and Gen. gives the time of model generation.
Verif. $\phi_{1}$ and Verif. $\phi_{2}$ present the verification time and its
output for formulas $\phi_{1}$ and $\phi_{2}$, respectively. All times are
given in seconds. The timeout was set to 8 hours.

Discussion of the results. In the experiments, we were able to verify models
of SAI for up to 5 agents. The verification outcome was conclusive in all
cases, i.e., the model checker always returned a concrete answer (True or
False). This means that we successfully model-checked systems for up to almost
a billion transitions, which is a serious achievement for an
$\mathbf{{NP}}$-hard verification problem. In all cases, formula $\phi_{1}$
turned out to be false. That is, both impersonation and man-in-the-middle
attacks can disrupt the learning process and prevent some agents from
obtaining good quality PAIVs. At the same time, $\phi_{2}$ was true in all
cases. Thus, the design guarantees that at least one good quality PAIV will be
achieved, even in the presence of the attacks.

#Ag #st #tr Gen. Verif. $\phi_{1}$ Verif. $\phi_{2}$ $2$ $886$ $2007$ $<0.1$
$<0.1$/False $<0.1$/True $3$ $79806$ $273548$ $28$ $151$/False $202$/True $4$
$6538103$ $29471247$ $1284$ $5061$/False $5102$/True $5$ $93581930$
$623680431$ $7845$ $25828$/False $25916$/True $6$ timeout

Figure 9: Verification results for the Impersonator attack scenario

#Ag #st #tr Gen. Verif. $\phi_{1}$ Verif. $\phi_{2}$ $3$ $23966$ $67666$ $12$
$21$/False $33$/True $4$ $4798302$ $20257664$ $875$ $3810$/False $3882$/True
$5$ $71529973$ $503249452$ $5688$ $19074$/False $20103$/True $6$ timeout

Figure 10: Verification results for Man in the Middle

##  6 CONCLUSIONS

In this paper, we present our work in progress on formal analysis of Social
Explainable AI. We propose that formal methods for multi-agent systems provide
a good framework for multifaceted analysis of SAI environments. As a proof of
concept, we demonstrate simple multi-agent models of SAI, prepared with the
model checker STV. Then, we use STV to formalize and verify two variants of
resistance to impersonation and man-in-the-middle attacks, with very promising
results. Notably, we have been able to successfully model-check systems for up
to almost a billion transitions – a considerable achievement for an
$\mathbf{{NP}}$-hard verification problem.

## ACKNOWLEDGEMENTS

The work was supported by NCBR Poland and FNR Luxembourg under the PolLux/FNR-
CORE project STV (POLLUX-VII/1/2019), and the CHIST-ERA grant CHIST-
ERA-19-XAI-010 by NCN Poland (2020/02/Y/ST6/00064). The work of Damian
Kurpiewski and Teofil Sidoruk was also supported by the CNRS IEA project
MoSART.

## REFERENCES

  * [1] Michael E. Akintunde, Elena Botoeva, Panagiotis Kouvaros, and Alessio Lomuscio.  Formal verification of neural agents in non-deterministic environments.  Auton. Agents Multi Agent Syst., 36(1):6, 2022.
  * [2] Rajeev Alur, Thomas A. Henzinger, and Orna Kupferman.  Alternating-time Temporal Logic.  Journal of the ACM, 49:672–713, 2002.
  * [3] Ben Batten, Panagiotis Kouvaros, Alessio Lomuscio, and Yang Zheng.  Efficient neural network verification via layer-based semidefinite relaxations and linear cuts.  In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021, pages 2184–2190. ijcai.org, 2021.
  * [4] N. Bulling, V. Goranko, and W. Jamroga.  Logics for reasoning about strategic abilities in multi-player games.  In J. van Benthem, S. Ghosh, and R. Verbrugge, editors, Models of Strategic Reasoning. Logics, Games, and Communities, volume 8972 of Lecture Notes in Computer Science, pages 93–136. Springer, 2015.
  * [5] E.M. Clarke, T.A. Henzinger, H. Veith, and R. Bloem, editors.  Handbook of Model Checking.  Springer, 2018.
  * [6] Marco Conti and Andrea Passarella.  The internet of people: A human and data-centric paradigm for the next generation internet.  Comput. Commun., 131:51–65, 2018.
  * [7] Pierluigi Contucci, Janos Kertesz, and Godwin Osabutey.  Human-ai ecosystem with abrupt changes as a function of the composition.  PLOS ONE, 17(5):1–12, 05 2022.
  * [8] Danny Dolev and Andrew Chi-Chih Yao.  On the security of public key protocols.  IEEE Trans. Inf. Theory, 29(2):198–207, 1983.
  * [9] Georgios Drainakis, Konstantinos V. Katsaros, Panagiotis Pantazopoulos, Vasilis Sourlas, and Angelos Amditis.  Federated vs. centralized machine learning under privacy-elastic users: A comparative analysis.  In Proceedings of NCA, pages 1–8. IEEE, 2020.
  * [10] E.A. Emerson.  Temporal and modal logic.  In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume B, pages 995–1072. Elsevier, 1990.
  * [11] Andrew Fuchs, Andrea Passarella, and Marco Conti.  Modeling human behavior part I - learning and belief approaches.  CoRR, abs/2205.06485, 2022.
  * [12] Dieter Gollmann.  Computer Security (3. ed.).  Wiley, 2011.
  * [13] Ian J. Goodfellow, Patrick D. McDaniel, and Nicolas Papernot.  Making machine learning robust against adversarial inputs.  Commun. ACM, 61(7):56–66, 2018.
  * [14] István Hegedüs, Gábor Danner, and Márk Jelasity.  Gossip learning as a decentralized alternative to federated learning.  In Proceedings of IFIP DAIS, volume 11534 of Lecture Notes in Computer Science, pages 74–90. Springer, 2019.
  * [15] István Hegedüs, Gábor Danner, and Márk Jelasity.  Decentralized learning works: An empirical comparison of gossip learning and federated learning.  J. Parallel Distributed Comput., 148:109–124, 2021.
  * [16] W. Jamroga, W. Penczek, T. Sidoruk, P. Dembiński, and A. Mazurkiewicz.  Towards partial order reductions for strategic ability.  Journal of Artificial Intelligence Research, 68:817–850, 2020.
  * [17] Wojciech Jamroga, Michał Knapik, Damian Kurpiewski, and Łukasz Mikulski.  Approximate verification of strategic abilities under imperfect information.  Artificial Intelligence, 277, 2019.
  * [18] Mazaher Kianpour and Shao-Fang Wen.  Timing attacks on machine learning: State of the art.  In Intelligent Systems and Applications - Proceedings of IntelliSys Volume 1, volume 1037 of Advances in Intelligent Systems and Computing, pages 111–125. Springer, 2019.
  * [19] Panagiotis Kouvaros and Alessio Lomuscio.  Towards scalable complete verification of relu neural networks via dependency-based branching.  In Proceedings of IJCAI, pages 2643–2650. ijcai.org, 2021.
  * [20] Ram Shankar Siva Kumar, Magnus Nyström, John Lambert, Andrew Marshall, Mario Goertzel, Andi Comissoneru, Matt Swann, and Sharon Xia.  Adversarial machine learning-industry perspectives.  In IEEE Security and Privacy Workshops, pages 69–75. IEEE, 2020\.
  * [21] Damian Kurpiewski.  STV – StraTegic Verifier. code repository, 2022.  https://github.com/blackbat13/stv.
  * [22] Damian Kurpiewski, Wojciech Jamroga, Lukasz Masko, Lukasz Mikulski, Witold Pazderski, Wojciech Penczek, and Teofil Sidoruk.  Verification of Multi-agent Properties in Electronic Voting: A Case Study.  In Proceedings of AiML 2022, 2022.
  * [23] Damian Kurpiewski, Witold Pazderski, Wojciech Jamroga, and Yan Kim.  STV+Reductions: Towards practical verification of strategic ability using model reductions.  In Proceedings of AAMAS, pages 1770–1772. ACM, 2021.
  * [24] Alessio Lomuscio, Hongyang Qu, and Franco Raimondi.  MCMAS: An open-source model checker for the verification of multi-agent systems.  International Journal on Software Tools for Technology Transfer, 19(1):9–30, 2017.
  * [25] Valerio Lorenzo, Chiara Boldrini, and Andrea Passarella.  SAI simulator for social AI gossiping, 2022.  https://zenodo.org/record/5780042.
  * [26] Abdul-Rasheed Ottun, Pramod C. Mane, Zhigang Yin, Souvik Paul, Mohan Liyanage, Jason Pridmore, Aaron Yi Ding, Rajesh Sharma, Petteri Nurmi, and Huber Flores.  Social-aware federated learning: Challenges and opportunities in collaborative data training.  IEEE Internet Computing, pages 1–7, 2022.
  * [27] M. Pauly.  A modal logic for coalitional power in games.  Journal of Logic and Computation, 12(1):149–166, 2002.
  * [28] Pierre-Yves Schobbens.  Alternating-time logic with imperfect recall.  Electronic Notes in Theoretical Computer Science, 85(2):82–93, 2004\.
  * [29] Y. Shoham and K. Leyton-Brown.  Multiagent Systems - Algorithmic, Game-Theoretic, and Logical Foundations.  Cambridge University Press, 2009.
  * [30] Social AI gossiping. Micro-project in Humane-AI-Net.  Project website, 2022.  https://www.ai4europe.eu/research/research-bundles/social-ai-gossiping.
  * [31] Social Explainable AI, CHIST-ERA.  Project website, 2021–24.  http://www.sai-project.eu/.
  * [32] Mustafa Toprak, Chiara Boldrini, Andrea Passarella, and Marco Conti.  Harnessing the power of ego network layers for link prediction in online social networks.  CoRR, abs/2109.09190, 2021.
  * [33] G. Weiss, editor.  Multiagent Systems. A Modern Approach to Distributed Artificial Intelligence.  MIT Press: Cambridge, Mass, 1999.
  * [34] Min Wu, Matthew Wicker, Wenjie Ruan, Xiaowei Huang, and Marta Kwiatkowska.  A game-based approximate verification of deep neural networks with provable guarantees.  Theor. Comput. Sci., 807:298–329, 2020.