# Finitely generated dyadic convex sets

K. Matczak1 1 Faculty of Civil Engineering, Mechanics and Petrochemistry in
Płock
Warsaw University of Technology
09-400 Płock, Poland  ,  A. Mućka2 2 Faculty of Mathematics and Information
Sciences
Warsaw University of Technology
00-662 Warsaw, Poland  and  A.B. Romanowska3 3 Faculty of Mathematics and
Information Sciences
Warsaw University of Technology
00-662 Warsaw, Poland<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
(Date: March 2023)

###### Abstract.

Dyadic rationals are rationals whose denominator is a power of $2$. We define
_dyadic $n$-dimensional convex sets_ as the intersections with $n$-dimensional
dyadic space of an $n$-dimensional real convex set. Such a dyadic convex set
is said to be a _dyadic $n$-dimensional polytope_ if the real convex set is a
polytope whose vertices lie in the dyadic space. Dyadic convex sets are
described as subreducts (subalgebras of reducts) of certain faithful affine
spaces over the ring of dyadic numbers, or equivalently as commutative,
entropic and idempotent groupoids under the binary operation of arithmetic
mean.

The paper contains two main results. First, it is proved that, while all
dyadic polytopes are finitely generated, only dyadic simplices are generated
by their vertices. This answers a question formulated in an earlier paper.
Then, a characterization of finitely generated subgroupoids of dyadic convex
sets is provided, and it is shown how to use the characterization to determine
the minimal number of generators of certain convex subsets of the dyadic
plane.

###### Key words and phrases:

dyadic rational numbers, dyadic affine space, dyadic convex set, dyadic
polytope, commutative binary mode, generating dyadic polytopes

###### 2010 Mathematics Subject Classification:

20N02, 08A05, 52B11, 52A01

_Please cite as_ : Matczak, K.; Mućka, A.; Romanowska, A. B.; Finitely
generated dyadic convex sets; Internat. J. Algebra Comput. 33 (2023), no. 3,
585–615.

##  1\. Introduction

The objects we study belong to both algebra and geometry. As algebras, they
have one binary operation which is idempotent, commutative and entropic. As
geometric objects, they are subsets of certain affine spaces.

Recall that _dyadic rationals_ are rationals whose denominator is a power of
$2$. They form the principal ideal subdomain $\mathbb{D}=\mathbb{Z}[1/2]$ of
the ring $\mathbb{R}$ of real numbers. The affine spaces of interest are
certain faithful affine spaces over the ring $\mathbb{D}$ (or affine
$\mathbb{D}$-spaces), i.e., idempotent reducts of certain faithful
$\mathbb{D}$-modules. Affine spaces over the ring $\mathbb{R}$ (_affine
$\mathbb{R}$-spaces_) may be described as abstract algebras with uncountably
many binary affine combinations indexed by the elements of $\mathbb{R}$.
Affine $\mathbb{D}$-spaces are subreducts (subalgebras of reducts) of affine
$\mathbb{R}$-spaces. The fact that $\mathbb{D}$ is a linearly ordered
commutative ring with a nontrivial open unit interval makes it possible to
define convex subsets of affine $\mathbb{D}$-spaces in a reasonable way. For a
given dimension $n$, a subset $D$ of $\mathbb{D}^{n}$ is called a _geometric
dyadic convex set_ (or briefly a _dyadic convex set_) if it is the
intersection of a convex subset of $\mathbb{R}^{n}$ with the space
$\mathbb{D}^{n}\subseteq\mathbb{R}^{n}$. Such sets are also described as being
_convex relative to $\mathbb{D}$_ (cf. for instance [1].) Then _dyadic
polytopes_ are defined as dyadic convex sets obtained as the intersection of
dyadic spaces with real polytopes whose vertices are contained in the dyadic
space. In particular, _dyadic polygons_ are the intersections of the dyadic
plane with real polygons spanned by vertices in the dyadic plane. The one-
dimensional analogs are _dyadic intervals_. In this paper the name of a dyadic
interval will be always used to denote an interval which is a dyadic polytope.

Real convex sets are described algebraically as certain barycentric algebras,
subsets of $\mathbb{R}^{n}$ closed under operations of weighted means with
weights from the open unit interval $I^{\circ}=\,]0,1[$ of $\mathbb{R}$.
Similarly, dyadic convex sets may be described as subsets of $\mathbb{D}^{n}$
closed under weighted means with weights from the open dyadic unit interval
$I^{\circ}\cap\mathbb{D}$. However, as shown already by Ježek and Kepka [5],
the operations determined by $I^{\circ}\cap\mathbb{D}$ are all generated by
the single arithmetic mean operation

$x\circ y:=xy\underline{1/2}=\frac{1}{2}(x+y).$

The arithmetic mean is an idempotent, commutative and entropic operation. This
fact allows one to define dyadic convex sets equivalently as groupoids with
the algebraic structure of a commutative binary mode (or briefly
$\mathcal{CB}$-modes), i.e. algebras with one binary idempotent, commutative
and entropic operation. Such algebras have a well developed theory. (See e.g.
[6, 7, 8, 9, 10, 11, 16, 17].)

Affine spaces and their subreducts, as well as $\mathcal{CB}$-modes, belong to
the class of _modes_ , idempotent and entropic algebras. (For the general
theory of modes, see the monographs [16, 17].)

Dyadic and real convex sets share many properties. However, there are also
essential differences. For example, real convex sets are characterized as
cancellative barycentric algebras (see [17, Thm. 5.8.6], but not all
cancellative $\mathcal{CB}$-modes are dyadic convex sets (see [9, § 5], [4, §
1.2].) While real intervals belong to only finitely many isomorphism classes
of barycentric algebras, there are infinitely many pairwise non-isomorphic
dyadic intervals. As a subgroupoid of $(\mathbb{D},\circ)$, each nontrivial
interval of $\mathbb{D}$ is isomorphic to some dyadic interval
$\mathbb{D}_{k}=[0,k]$, where $k$ is an odd positive integer. Two such
intervals are isomorphic precisely when their right hand ends are equal [11, §
3].

The problem of locating generating elements of dyadic polygons was first
considered in [11]. While real intervals which are polytopes are minimally
generated by their two ends, the dyadic intervals are minimally generated by
$2$ or $3$ elements. The interval $\mathbb{D}_{1}$ is generated by $0$ and
$1$, and for $k>1$, the interval $\mathbb{D}_{k}$ is generated by three, but
no fewer, elements. For each $d\in\mathbb{D}$, the dyadic intervals
$[d,d+2^{n}]$ are isomorphic to $\mathbb{D}_{1}$, and the dyadic intervals
$[d,d+k2^{n}]$ are isomorphic to $\mathbb{D}_{k}$. More generally, it was
shown that each dyadic triangle is finitely generated, and then that each
dyadic polygon is finitely generated. However, the methods used in that paper
were not sufficient to determine the exact minimal number of generators.
Moreover, the following question was left open: Are all dyadic polytopes
finitely generated? (See [11, Problem 1.1].) The question arose in connection
with our investigations of quasivarieties of $\mathcal{CB}$-modes [9, 10] and
of duality for dyadic polytopes [7, 8]. A related question asks whether
finitely generated subgroupoids of $(\mathbb{D}^{n},\circ)$ are isomorphic to
dyadic polytopes. A partial answer was then given in [7]: It was shown that
each finitely generated subgroupoid of $(\mathbb{D},\circ)$ is isomorphic to a
dyadic interval.

In this paper we provide an affirmative solution to the problem formulated in
[11], and show that each dyadic polytope is finitely generated (Theorem 3.4).
However, there are some other subsets of $\mathbb{D}^{n}$, closed under the
operation $\circ$, which are not isomorphic to dyadic polytopes but are
finitely generated (Example 4.1). To characterize finitely generated
subgroupoids of $\mathbb{D}^{n}$, we introduce a new class of so-called
semipolytopes. A _semipolytope_ is a subgroupoid of a dyadic polytope such
that both have the same vertices and the same interior (Definition 4.2). The
main result, Theorem 5.1, states that a subgroupoid $(D,\circ)$ of the
groupoid $(\mathbb{D}^{n},\circ)$ is finitely generated precisely when it is
isomorphic to a semipolytope. This result is then used in the final section to
calculate the minimal number of generators of certain polygons and
semipolygons.

All dyadic convex sets are considered in this paper as $\mathcal{CB}$-modes.
We use notation, terminology and conventions similar to those of [17] and the
previously referenced papers. In particular, the reader may wish to consult
the papers [4], [7] and [11]. For more details and information on affine
spaces, convex sets and barycentric algebras, we also refer the reader to the
monographs [16, 17] and the recent survey [15]. For convex polytopes, see the
first two chapters of [2].

##  2\. Subsets of dyadic affine spaces

In this section we recall and augment the basic facts concerning dyadic affine
spaces and dyadic convex sets provided in [4], [9] and [11].

###  2.1. Dyadic affine spaces

First recall that affine spaces over a commutative ring $R$ (_affine
$R$-spaces_), where $R$ is $\mathbb{R}$ or $\mathbb{D}$, can be considered as
the reducts $(A,\underline{R})$ of $R$-modules $(A,+,R)$, where
$\underline{R}$ is the set of binary affine combinations

(2.1) $ab\,\underline{r}=a(1-r)+br\,$

for all $r\in R$ and $a,b\in A$. (See [17, § 5.3, § 6.3].) In particular,
affine spaces over the ring $\mathbb{D}$ (affine $\mathbb{D}$-spaces) are
considered here as algebras $(A,\underline{\mathbb{D}})$ with the set
$\underline{\mathbb{D}}=\\{\underline{d}\mid d\in\mathbb{D}\\}$ of basic
operations. The class of all affine $R$-spaces forms a variety [3].

In this paper, we are especially interested in subreducts of certain faithful
affine $\mathbb{D}$-spaces. (Recall that in a faithful affine
$\mathbb{D}$-space, the two operations $\underline{d}$ and $\underline{e}$ for
$d\neq e\in\mathbb{D}$ are different.) By results of [9] and [4], it follows
that one of the minimal quasivarieties of affine $\mathbb{D}$-spaces is the
quasivariety $\mathsf{Q_{A}}(\mathbb{D})$ of affine $\mathbb{D}$-spaces,
generated by the affine $\mathbb{D}$-space $\mathbb{D}$. Finitely generated
members of $\mathsf{Q_{A}}(\mathbb{D})$ are free affine $\mathbb{D}$-spaces on
finitely many generators. The free affine $\mathbb{D}$-space on $n+1$
generators, for $n=0,1,\dots$, is $\mathbb{D}^{n}$. The number $n$ is called
the _dimension_ of the affine $\mathbb{D}$-space $\mathbb{D}^{n}$. The set of
elements of the free affine $\mathbb{D}$-space $(x_{0},\dots,x_{n})\mathbb{D}$
on $n+1$ generators $x_{0},\dots,x_{n}$ is given as

$(x_{0},\dots,x_{n})\mathbb{D}=\Big{\\{}x_{0}r_{0}+\dots+x_{n}r_{n}\,\Big{|}\,r_{i}\in\mathbb{D},\sum_{i=0}^{n}r_{i}=1\Big{\\}}.$

(See [14].) All members of $\mathsf{Q_{A}}(\mathbb{D})$ are faithful. Note,
however, that there are faithful affine $\mathbb{D}$-spaces not contained in
$\mathsf{Q_{A}}(\mathbb{D})$, as for example the affine space
$\mathbb{D}\times\mathbb{D}/(3)\cong\mathbb{D}\times\mathbb{Z}_{3}$. 111In
this context, the explanation given in [4, 10, 7] may require further
clarification.

Unlike the case of the affine $\mathbb{R}$-space $\mathbb{R}^{n}$, the affine
$\mathbb{D}$-space $\mathbb{D}^{n}$ contains infinitely many $n$-dimensional
affine $\mathbb{D}$-subspaces. First note that nontrivial subspaces of the
affine $\mathbb{D}$-space $\mathbb{D}$ have the form

$m\mathbb{D}=\\{md\mid d\in\mathbb{D}\\}$

for some positive integer $m$. Note also that $2^{k}\mathbb{D}=\mathbb{D}$ and
$2^{k}(2l+1)\mathbb{D}=(2l+1)\mathbb{D}$.

Nontrivial affine subspaces of affine $\mathbb{D}$-spaces $\mathbb{D}^{n}$ for
$n\geq 2$ are more difficult to describe. First note that

$m_{1}\mathbb{D}\times\dots\times m_{n}\mathbb{D},$

where $m_{1},\dots,m_{n}$ are positive integers, are $n$-dimensional subspaces
of the affine $\mathbb{D}$-spaces $\mathbb{D}^{n}$. Then, for $1\leq k\leq n$,
the products

$m_{i_{1}}\mathbb{D}\times\dots\times m_{i_{k}}\mathbb{D},$

are $k$-dimensional subspaces of $\mathbb{D}^{n}$, and hence are isomorphic to
the affine $\mathbb{D}$-space $\mathbb{D}^{k}$. However, there exist other
affine subspaces of $\mathbb{D}^{n}$. Examples are given by proper subspaces
of dyadic lines in $\mathbb{D}^{n}$. For example, the set $\\{(3d,3d)\mid
d\in\mathbb{D}\\}$ is a subspace of the dyadic line $\\{(d,d)\mid
d\in\mathbb{D}\\}$, a one-dimensional subspace of $\mathbb{D}^{2}$.

Let $X$ be a subset of a finite-dimensional affine $\mathbb{D}$-space $A$ from
the quasivariety $\mathsf{Q_{A}}(\mathbb{D})$. Then the _affine
$\mathbb{D}$-hull_ $\mathrm{aff}_{\mathbb{D}}(X)$ of $X$ is the intersection
of all the affine subspaces of $A$ that contain $X$. The _affine
$\mathbb{R}$-hull_ $\mathrm{aff}_{\mathbb{R}}(X)$ is the intersection of the
all affine $\mathbb{R}$-spaces containing $X$.

###  2.2. Dyadic convex sets

######  Definition 2.1.

[4] A subgroupoid $(B,\circ)$ of the reduct $(A,\circ)$ of an affine
$\mathbb{D}$-space $A$ from $\mathsf{Q_{A}}(\mathbb{D})$ is called an
_algebraic dyadic convex subset of_ $A$ (or briefly an _algebraic dyadic
convex set_).

Isomorphic copies of algebraic dyadic convex sets form a (minimal)
subquasivariety $\mathsf{Q}(\mathbb{D})$ of the variety $\mathcal{CBM}$ of
$\mathcal{CB}$-modes [9, § 3].

######  Definition 2.2.

[4, 11] An algebraic dyadic convex subset of $\mathbb{D}^{n}$ is _geometric_
if it is the intersection of a convex subset $C$ of $\mathbb{R}^{n}$ with the
subspace $\mathbb{D}^{n}$.

Not all algebraic dyadic convex sets are geometric. For example, $3\mathbb{D}$
is an algebraic but not a geometric dyadic convex set. If not otherwise
indicated, the term “dyadic convex set” will normally be used to denote
geometric dyadic convex sets. It is often convenient to use the subspace
topology on a dyadic subspace of $\mathbb{R}^{n}$ coming from the Euclidean
topology on $\mathbb{R}^{n}$. We use this topology when speaking about closed
or open dyadic convex sets.

######  Definition 2.3.

If $C\in\mathsf{Q}(\mathbb{D})$, and $\mathrm{aff}_{\mathbb{D}}(C)$ is of
finite dimension $n$, then we say that $C$ is _finite-dimensional_ , and that
its _dimension_ $\dim(C)$ equals $n$.

If $C$ is an algebraic dyadic convex subset of an affine $\mathbb{D}$-space
$\mathbb{D}^{n}$, then the _convex $\mathbb{R}$-hull_
$\mathrm{conv}_{\mathbb{R}}(C)$ of $C$ in $\mathbb{R}^{n}$ is the intersection
of all convex subsets of $\mathbb{R}^{n}$ containing $C$. Then
$\mathrm{conv}_{\mathbb{R}}(C)$ may be considered as the subalgebra generated
by $C$ in the real convex set $(\mathbb{R}^{n},\underline{I}^{\circ})$ , where
$\underline{I}^{\circ}$ is the set of operations $\underline{r}$ defined by
(2.1) for $r\in I^{\circ}$. The _convex $\mathbb{D}$-hull_
$\mathrm{conv}_{\mathbb{D}}(C)$ of $C$ in $\mathbb{D}^{n}$ is the intersection
of $\mathrm{conv}_{\mathbb{R}}(C)$ with $\mathbb{D}^{n}$,

(2.2)
$\mathrm{conv}_{\mathbb{D}}(C)=\mathrm{conv}_{\mathbb{R}}(C)\cap\mathbb{D}^{n},$

and is obviously geometric. An algebraic $n$-dimensional convex subset $C$ of
an affine space $\mathbb{D}^{n}$, where $n$ is a positive integer, is a
geometric dyadic convex subset of $\mathbb{D}^{n}$ precisely if

(2.3) $C=\mathrm{conv}_{\mathbb{D}}(C),$

or in other words, if $C$ consists of all dyadic points of the real convex set
generated by $C$. The convex $\mathbb{R}$-hull of a subset $X$ of
$\mathbb{D}^{n}$ is defined similarly as for (algebraic) dyadic convex sets.

The _relative interior_ $\mathrm{int}(C)$ of an algebraic convex subset $C$ of
$\mathbb{D}^{n}$ (or briefly the _interior_ of $C$) is the intersection with
$\mathrm{aff}_{\mathbb{D}}(C)$ of the relative interior of
$\mathrm{conv}_{\mathbb{R}}(C)$ in the affine $\mathbb{R}$-hull of $C$. The
elements of $\mathrm{int}(C)$ are called _interior points_ of $C$. Note that
if $C$ is geometric and $n$-dimensional, then
$\mathrm{aff}_{\mathbb{D}}(C)=\mathbb{D}^{n}$.

######  Definition 2.4.

[11] A _dyadic $n$-dimensional polytope_ is the intersection with the dyadic
space $\mathbb{D}^{n}$ of an $n$-dimensional real polytope whose vertices lie
in the dyadic space.

Dyadic polytopes are obviously geometric. If $P$ is a dyadic $n$-dimensional
polytope, then there is a real $n$-dimensional polytope $C$ with dyadic
vertices such that

$P=C\cap\mathbb{D}^{n}.$

Hence

$C=\mathrm{conv}_{\mathbb{R}}(P),$

and then,

$P=C\cap\mathbb{D}^{n}=\mathrm{conv}_{\mathbb{R}}(P)\cap\mathbb{D}^{n}.$

On the other hand, by (2.2) and (2.3),

(2.4)
$P=\mathrm{conv}_{\mathbb{R}}(P)\cap\mathbb{D}^{n}=\mathrm{conv}_{\mathbb{D}}(P).$

The vertices of the (real) polytope $\mathrm{conv}_{\mathbb{R}}(P)$ are
contained in $P$, and will be referred to as to the vertices of $P$.

###  2.3. Walls

For a barycentric algebra $(C,\underline{I}^{o})$, which is a convex set, a
subset $A$ of $C$ is a _wall_ , if

$\forall\ a,b\in C\,,\ \forall\,\ r\in I^{o}\,,\ ab\underline{r}\in A\
\Leftrightarrow\ a\in A\mbox{ and }b\in A.$

Similarly, for a dyadic convex set $(C,\circ)$, a subset $A$ of $C$ is a
_wall_ , if

$\forall\ a,b\in C\,,\ a\circ b\in A\ \Leftrightarrow\ a\in A\mbox{ and }b\in
A.$

(See e.g. [16, §3.3] and [17, Def. 1.1.9].) Note that in the case of real
polytopes, the geometric concept of a face (see e.g. [2, §5, §7]) and the
algebraic concept of a wall describe the same subsets of a polytope. The
$0$-dimensional faces of a real $n$-dimensional polytope $P$ are its vertices,
and the $1$-dimensional faces are the edges. The maximal (thus
$(n-1)$-dimensional) faces are also called the _facets_ of $P$. The proper
faces of a polytope are polytopes of smaller dimension, and each face of $P$
considered as a barycentric algebra is generated by some vertices of $P$. The
_boundary_ of $P$ in the affine hull of $P$ is the difference between $P$ and
its interior, and is the union of the proper faces of $P$.

Using the algebraic definition of a wall, one can easily extend the geometric
concept of a face of a real polytope to the case of a dyadic polytope. This
extension preserves the basic properties of faces of real polytopes. In
particular, walls of a dyadic polytope may be described as follows.

Let $P$ be an $n$-dimensional dyadic polytope and let
$C=\mathrm{conv}_{\mathbb{R}}(P)$. First note that by (2.4),

(2.5) $P=C\cap\mathbb{D}^{n},$

i.e. $P$ consists of all dyadic points of the real polytope $C$. Moreover, the
dyadic polytope $P$ and the real polytope $C$ have the same (dyadic) vertices.

######  Proposition 2.5.

Let $P$ be an $n$-dimensional dyadic polytope and let
$C=\mathrm{conv}_{\mathbb{R}}(P)$. Then the intersection of $P$ with a wall of
$C$ is a wall of $P$.

###### Proof.

Let $W$ be a wall of $C$. To show that $W\cap P$ is a wall of $P$, let
$d_{1},d_{2}$ be any elements of $P$. Then $d=d_{1}\circ d_{2}\in W\cap P$,
precisely when $d_{1},d_{2}\in W\cap P$. Thus $W\cap P$ is a wall of $P$. ∎

We will show that the only walls of a dyadic polytope $P$ are those described
in Proposition 2.5.

######  Lemma 2.6.

If $P$ is a one-dimensional dyadic polytope, then $P$ is a dyadic interval and
has precisely three non-empty walls, two zero-dimensional walls and one
improper one-dimensional wall $P$.

###### Proof.

A one-dimensional dyadic polytope $P$ is a dyadic interval, as described in
Section 1. Up to isomorphism, $P$ is an interval $\mathbb{D}_{k}$ of
$\mathbb{D}\subseteq\mathbb{R}$, for some odd positive integer $k$. Then
$C=\mathrm{conv}_{\mathbb{R}}(\mathbb{D}_{k})$ is the real interval with
vertices $0$ and $k$. Each of the vertices $0$ and $k$ forms a $0$-dimensional
wall of $\mathbb{D}_{k}$ and of $C$. We will show that $\mathbb{D}_{k}$ has
only one more wall which coincides with $\mathbb{D}_{k}$.

Let $d$ be any dyadic element of $C$ different from $0$ and $k$. We are
looking for the smallest wall $W$ of $\mathbb{D}_{k}$ containing $d$. First
note that for each $x$ in $\mathbb{D}$, the reflection $x_{d}=2d-x$ of $x$ in
$d$ is also a dyadic number and $x\circ x_{d}=d$. If both $x$ and $x_{d}$
belong to $\mathbb{D}_{k}$, then $x$ and $x_{d}$ belong to $W$. In particular,
if $d=k/2$, then each $x\in\mathbb{D}_{k}$ belongs to $W$, and $W$ coincides
with $\mathbb{D}_{k}$.

Let $d$ be different from $0,k/2$ and $k$. We will show that $k/2\in W$, which
implies that $W$ coincides with $\mathbb{D}_{k}$. Without loss of generality
it suffices to consider the case where $0<d<k/2$. First let $k/4\leq d<k/2$.
Then $k/2\leq 2d$, and for each $0\leq x\leq d$, we have $d=x\circ x_{d}$.
Hence $x,x_{d}\in W$. It follows that the dyadic interval $[0,2d]$ is
contained in $W$. In particular $k/2\in W$. Now let $0<d<k/4$. Then there is a
positive integer $i$ such that $2^{i}d<k/2<2^{i+1}d<k$. Similarly as before
one shows that the dyadic intervals $[0,2d]$, and then
$[0,4d],\dots,[0,2^{i+1}d]$ are contained in $W$. Obviously, the last interval
$[0,2^{i+1}d]$ contains $k/2$. ∎

If $C$ is the smallest real polytope containing a dyadic polytope $D$, then we
say that $D$ generates $C$. In other words, $C$ is generated by $D$ as a
barycentric algebra.

######  Proposition 2.7.

Let $P$ be an $n$-dimensional dyadic polytope and let
$C=\mathrm{conv}_{\mathbb{R}}(P)$. Then for each $k$-dimensional wall $W$ of
$P$, where $k\leq n$, the real polytope
$\overline{W}:=\mathrm{conv}_{\mathbb{R}}(W)$ is a wall of $C$ generated by
$W$, and $W=\overline{W}\cap P$.

###### Proof.

Let $W$ be a wall of $P$, $\overline{W}=\mathrm{conv}_{\mathbb{R}}(W)$, and
$F$ be the wall of $C$ generated by the wall $W$. Note that

$W\subseteq\overline{W}=\mathrm{conv}_{\mathbb{R}}(W)\subseteq F\subseteq
C=\mathrm{conv}_{\mathbb{R}}(P).$

The proof is by induction on the dimension of a wall of $P$. If $\dim(W)=0$,
then $W$ consists of one element, which is a vertex of both $F$ and $P$. If
$\dim(W)=1$, then $W\subseteq\overline{W}\subseteq F$, and all three
$W,\overline{W}$ and $F$ are one-dimensional. Moreover $F$ is a real interval
with dyadic ends, which are vertices of $P$ and $C$, containing the dyadic
interval $F\cap P$ of all dyadic points of $F$. By Proposition 2.5, $F\cap P$
is a wall of $P$. By Lemma 2.6, $F\cap P$ has two $0$-dimensional walls and
one improper wall $F\cap P$. In particular each point of $W$, different from a
vertex, generates $F\cap P$ as a wall of $P$. It follows that $W=F\cap
P=F\cap\mathbb{D}$, and $F=\overline{W}$.

Now assume that the statement of Proposition holds for all walls of dimension
smaller than $k<n$. We will show that it holds for $k$. So let $W$ be a wall
of $P$ of dimension $k$. Define $\overline{W}$ and $F$ as before. Note that
$F$ is a real polytope with dyadic vertices, and $F\cap P$ is a dyadic
polytope with the same vertices as $F$.

Let $d\in F\cap P$. We are looking for a smallest wall of $F\cap P$ containing
$d$.

If $d$ generates a wall $U$ of $P$ contained in $F$ of dimension smaller than
$k$, then by induction hypotheses, $U=\overline{U}\cap P$, where
$\overline{U}=\mathrm{conv}_{\mathbb{R}}(U)$ is a wall of $F$. So assume that
$d$ is an interior point of $F$. Recall that each interior point of $F$
generates the wall $F$. (See [2, Thm. 5.6].) Indeed, proper walls of $F$ do
not contain interior points of $F$. Moreover, $W,\overline{W}$ and $F$ are
$k$-dimensional. Let $x$ be any dyadic point of $F\cap P$ and assume that its
reflection $x_{d}$ in $d$ also belongs to $F\cap P$. Since $W$ is a wall of
$P$ and $d=x\circ x_{d}$, it follows that if $d\in W$, then both $x$ and
$x_{d}$ also belong to $W$. Consider the real line $l_{d}$ through $d$ and
$x$. Then an argument similar to that in the proof of Lemma 2.6 shows that
each dyadic interval contained in $l_{d}\cap P$ is contained in $W$. In
particular, if $l_{d}\cap P$ contains a vertex of $P$, then this vertex
belongs to $W$. It follows that any dyadic point of $F\cap P$ belongs to $W$,
and hence $W=F\cap P=F\cap\mathbb{D}$, and $F=\overline{W}$. ∎

######  Corollary 2.8.

Each wall of a dyadic polytope is also a dyadic polytope.

###### Proof.

By Propositions 2.5 and 2.7, a wall $W$ of an $n$-dimensional dyadic polytope
$P$ is the intersection with $\mathbb{D}^{n}$ of the real polytope, namely the
wall $F$ of $C$ generated by $W$. ∎

Propositions 2.5 and 2.7 show that there is a one-to-one correspondence
between walls of $P$ and walls of $C$, and for each wall $W$ of $P$, one has
$W=\overline{W}\cap P$. In particular, $W$ and $\overline{W}$ have the same
(dyadic) vertices. It follows that the walls of $P$ are determined by the
vertices of $P$ they contain. Proper walls of $P$ are polytopes of a dimension
smaller than the dimension of $P$. Note as well that the lattices of walls of
$P$ and $C=\mathrm{conv}_{\mathbb{R}}(P)$ are isomorphic. Recall that dyadic
subspaces of $\mathbb{R}^{n}$ are considered in this paper as topological
spaces with the subspace topology coming from the Euclidean topology on
$\mathbb{R}^{n}$. Then similarly as in the case of real polytopes, the
(relative) interior of a dyadic polytope $P$ consists of the points of $P$
which are not contained in the proper walls of $P$, and the boundary of $P$
(in its affine $\mathbb{D}$-hull) is the difference between $P$ and its
interior.

Corollary 2.8 may be extended to some algebraic dyadic convex sets. Let $D$ be
an $n$-dimensional algebraic dyadic convex set such that
$E=\rm{conv}_{\mathbb{D}}(D)$ is a (dyadic) polytope. In this case, each wall
$W$ of $D$ is the intersection with $D$ of the wall of $E$ generated by $W$.
The proof is similar as in the case of dyadic polytopes, with $\mathbb{D}$
replaced by $\rm{aff}_{\mathbb{D}}(D)$ and $C$ replaced by $E$. Note that the
vertices of $E$ belong to $D$, and the set of all these vertices is contained
in each set of generators of $D$. If $D$ has $k$ vertices, then $k\geq n+1$.
Note as well that $D$, $\mathrm{conv}_{\mathbb{D}}(D)$ and
$\mathrm{conv}_{\mathbb{R}}(D)$ have the same dimension.

######  Example 2.9.

To illustrate the concepts introduced above, consider the points
$A=(0,0),B=(3,0)$ and $C=(0,1)$ of the plane
$\mathbb{D}^{2}\subseteq\mathbb{R}^{2}$. The closed real triangle $T_{r}$ with
vertices $A$, $B$ and $C$ is a real polytope generated (as the barycentric
algebra) by these vertices. The dyadic triangle
$T_{d}=T_{r}\cap\mathbb{D}^{2}$ is a dyadic polytope with vertices $A$, $B$
and $C$, and with $\mathrm{conv}_{\mathbb{R}}(T_{d})=T_{r}$. It consists of
all dyadic points contained in $T_{r}$. Let us note that $A$, $B$ and $C$ are
not sufficient to generate $T_{d}$ (as a groupoid under the operation
$\circ$), since $A$ and $B$ generate only the dyadic points $(a,0)$ with $a$
divisible by $3$. However, $T_{d}$ is generated by $A$, $B$, $C$ and
$D=(1,0)$. (See [11, Cor. 7.5].) On the other hand, $A$, $B$ and $C$ generate
the (algebraic) dyadic convex subset $T_{a}$ of $3\mathbb{D}\times\mathbb{D}$,
which is not geometric.

All the three triangles have the same vertices, which form $0$-dimnesional
walls. The real intervals $[A,B],[B,C],[A,C]$ are the proper nontrivial walls
of $T_{r}$. Similarly, the dyadic intervals $[A,B],[B,C],[A,C]$ are the proper
nontrivial walls of $T_{d}$. The proper nontrivial walls of $T_{a}$ are
obtained as the intersections of the corresponding walls of $T_{d}$ with
$T_{a}$. Note as well, that the open real or dyadic triangle $ABC$ has no
vertices, is not a polytope and has no nontrivial proper walls. The dyadic
open triangle $ABC$ is geometric. On the other hand, the open dyadic triangle
$ABC$ together with the dyadic interval $[A,C]$ is also geometric, is not a
polytope, but has two vertices $A$ and $C$, and three proper walls $A$, $C$
and $[A,C]$.

###  2.4. Simplices

Examples of dyadic polytopes generated by their vertices are given by some
models of finitely generated free commutative binary modes. First recall that
in affine geometry, a (real) $n$-dimensional simplex is usually defined as a
polytope with $n+1$ affinely independent vertices. It is known that proper
faces of a simplex are simplices of smaller dimension [2, Thm. 12.1, Thm.
12.2]. It was shown by W. Neumann [13] that the free barycentric algebra on
$n+1$ generators is the $n$-dimensional simplex with its vertices as free
generators. The elements of the free barycentric algebra $X\mathcal{B}$ on
$X$, where $X=\\{x_{0},x_{1},\dots,x_{n}\\}$, are described as follows

$\Big{\\{}x_{0}r_{0}+\dots+x_{n}r_{n}\,\Big{|}\,r_{i}\in I,\
\sum_{i=0}^{n}r_{i}=1\Big{\\}}.$

Here $I=[0,1]$ is the closed unit interval of $\mathbb{R}$. (See [14, L. 6.1,
L. 6.2]).

If $S$ is an $n$-dimensional real simplex with dyadic vertices
$x_{0},\dots,x_{n}$, then the subgroupoid of $(S,\circ)$ generated by these
vertices is called an _$n$ -dimensional algebraic dyadic simplex_. Its
elements form the set

(2.6)
$\Big{\\{}x_{0}r_{0}+\dots+x_{n}r_{n}\,\Big{|}\,r_{i}\in\mathbb{D}_{1}=I\cap\mathbb{D},\
\sum_{i=0}^{n}r_{i}=1\Big{\\}}.$

Note that such a simplex is not necessarily geometric. As proved in [14, L.
6.1, L. 6.2], the free commutative binary mode $X\mathcal{CBM}$ on a set
$X=\\{x_{0},\dots,x_{n}\\}$ is isomorphic with the $\underline{1/2}$-reduct
generated by $X$ of the free affine $\mathbb{D}$-space $X\mathbb{D}$ on $X$.
The elements of $X\mathcal{CBM}$ are described by (2.6).

It was shown earlier in [5] and [16, §4.4] that by taking the elements

(2.7) $e_{0}=(0,\dots,0),e_{1}=(1,0,\dots,0),\dots,e_{n}=(0,\dots,0,1)$

as the generators $x_{i}$ in (2.6), one obtains the (geometric) dyadic simplex
$\mathbf{S}_{n}$ free in the variety $\mathcal{CBM}$. The simplex
$\mathbf{S}_{n}$ is a dyadic polytope, and a subreduct of the real simplex
$\mathbf{S}_{n}^{r}$ with the same vertices. The proper faces of
$\mathbf{S}_{n}$ are polytopes of smaller dimension. While each algebraic
dyadic simplex is isomorphic to some $\mathbf{S}_{n}$, not all of them are
geometric. An example is given by the dyadic simplex generated by
$e_{0}=(0,\dots,0),e^{\prime}_{1}=(3,0,\dots,0),\dots,e^{\prime}_{n}=(0,\dots,0,3)$.
In fact, any affinely independent set of points of $\mathbb{D}^{n}$ generates
an algebraic dyadic simplex. We will use the name _algebraic dyadic simplex_
for a groupoid isomorphic to some $\mathbf{S}_{n}$, while reserving the name
_dyadic simplex_ for geometric dyadic simplices.

######  Lemma 2.10.

[4, L. 2.2] Each $n$-dimensional algebraic dyadic convex set, where
$n=1,2,\dots$, contains an $n$-dimensional subgroupoid isomorphic to the
dyadic simplex $\mathbf{S}_{n}$.

######  Corollary 2.11.

Each $n$-dimensional geometric dyadic convex set $C$, where $n=1,2,\dots$,
contains infinitely many geometric subgroupoids isomorphic to the dyadic
simplex $\mathbf{S}_{n}$.

###### Proof.

First note that, for each $k\in\mathbb{Z}$, the elements
$e^{\prime}_{i}=(1/2^{k})e_{i}$, where $i=0,1,\dots,n$, generate a geometric
dyadic simplex $S^{\prime}_{n}$. For any interior point $a$ of $C$, there is
$k\in\mathbb{Z}$ such that all $a^{\prime}_{i}=a+e^{\prime}_{i}$ belong to $C$
and generate a geometric dyadic simplex, the translate of $S^{\prime}_{n}$. ∎

For a positive integer $n$, let $C$ be an $n$-dimensional algebraic dyadic
convex set. Take $k>n$. We say that $C$ is _$k$ -generated_ if $C$ is
minimally generated by a set of $k$ generators. Thus $C$ has a $k$-element set
of generators, but not a smaller one.

######  Lemma 2.12.

Let $C$ be an $n$-dimensional algebraic dyadic convex set, for
$0<n\in\mathbb{Z}$. Then $C$ is isomorphic to $\mathbf{S}_{n}$ if and only if
it is $(n+1)$-generated, or equivalently, it is generated by its $n+1$
vertices.

###### Proof.

We already know that if $C$ is isomorphic to a simplex $\mathbf{S}_{n}$, then
it is $(n+1)$-generated and that its vertices form a minimal set of
generators.

We will show that each $n$-dimensional $(n+1)$-generated algebraic dyadic
convex set $C$ is isomorphic to $\mathbf{S}_{n}$. This is certainly true for
$n=1$: a one-dimensional $2$-generated convex set is isomorphic to
$\mathbb{D}_{1}=\mathbf{S}_{1}$. Let $n\geq 1$. Consider an $n$-dimensional
convex set $C$ minimally generated by the set $X=\\{x_{0},\dots,x_{n}\\}$.
Note that $X$ is affinely independent. (Otherwise $\dim(C)$ would be less than
$n$.) The generators of $C$ generate a real $n$-dimensional $(n+1)$-generated
polytope, which is obviously a real simplex. Since $\mathbf{S}_{n}^{r}$ is a
free barycentric algebra, the mapping

$e_{0}\mapsto x_{0},\,e_{1}\mapsto x_{1},\dots,e_{n}\mapsto x_{n}$

extends uniquely to the isomorphism between the barycentric algebras
$\mathbf{S}_{n}^{r}$ and $\mathrm{conv}_{\mathbb{R}}(C)$. This isomorphisms
restricts to the isomorphism between the dyadic convex sets $\mathbf{S}_{n}$
and $C$. ∎

Note that the convex sets of Lemma 2.12 isomorphic to $\mathbf{S}_{n}$ are not
necessarily geometric. On the other hand, if $1<i\in\mathbb{Z}$, then
$n$-dimensional and $(n+i)$-generated convex subsets of $\mathbb{D}^{n}$ are
not necessarily isomorphic. Examples are given by the dyadic $3$-generated
intervals, and by the (geometric) triangles on $\mathbb{D}^{2}$ with vertices
$(-1,0),(0,1)$ and $(0,2k+1)$ for positive integers $k$, which are all
generated by four (but not fewer) elements, and no two of which are isomorphic
[11, §4].

######  Corollary 2.13.

For $0<n\in\mathbb{Z}$, an $n$-dimensional and $(n+1)$-generated algebraic
dyadic convex set $C$ is a geometric simplex precisely if $C$ coincides with
its convex $\mathbb{D}$-hull $\mathrm{conv}_{\mathbb{D}}(C)$.

###  2.5. Further comments

In this paper, dyadic polytopes and their subgroupoids are considered as
subreducts of their affine $\mathbb{D}$-hulls. After introducing coordinate
axes in such a space, a given polytope will be located in the corresponding
$\mathbb{D}$-module by providing the coordinates of its vertices. An
$n$-dimensional affine $\mathbb{D}$-space may be considered as a subreduct of
the $n$-dimensional real space $\mathbb{R}^{n}$. The free generators of the
dyadic simplex $\mathbf{S}_{n}$ given by (2.7) are also free generators of the
free affine $\mathbb{D}$-space $\mathbb{D}^{n}$ and of the free affine
$\mathbb{R}$-space $\mathbb{R}^{n}$.

Finally, recall that automorphisms of the affine $\mathbb{D}$-space
$\mathbb{D}^{n}$ form the $n$-dimensional affine group
$\mathrm{GA}(n,\mathbb{D})$ over the ring $\mathbb{D}$, the group generated by
the linear group $\mathrm{GL}(n,\mathbb{D})$ and the group of translations of
the space $\mathbb{D}^{n}$. Moreover, each element of the affine group
$\mathrm{GA}(n,\mathbb{D})$ is also an automorphism of the groupoid
$(\mathbb{D}^{n},\circ)$, and transforms any polytope in $\mathbb{D}^{n}$ onto
an isomorphic polytope. On the other hand, each automorphism of a nontrivial
$n$-dimensional polytope extends to an automorphism of the affine
$\mathbb{D}$-space $\mathbb{D}^{n}$. Indeed, by Corollary 2.11, any such
polytope contains the free simplex $\mathbf{S}_{n}$, with vertices generating
the affine hull of the simplex and the polytope. Isomorphisms of such
polytopes in $\mathbb{D}^{n}$ will be considered as restrictions of
automorphisms of the affine space $\mathbb{D}^{n}$.

##  3\. Generating dyadic polytopes

It was shown in [11] that all dyadic intervals, all dyadic triangles, and more
generally all dyadic polygons, are finitely generated. In this section we will
show that the same holds for all dyadic polytopes.

Recall that dyadic polytopes, and in particular dyadic intervals, are
geometric. The following basic lemma is a direct consequence of the results of
[7, §3].

######  Lemma 3.1.

Let $a,b,c\in\mathbb{D}$ with $a<b<c$. If one of the dyadic intervals $[a,b]$
or $[b,c]$ forms a dyadic simplex, then the groupoid generated by
$\\{a,b,c\\}$ coincides with the dyadic interval $[a,c]$.

###### Proof.

If the interval $[a,b]$ is a dyadic simplex, then it is isomorphic to the
dyadic interval $[0,1]$. Let $\iota\colon[a,b]\rightarrow[0,1]$ be the
required isomorphism assigning $0$ to $a$ and $1$ to $b$. The mapping $\iota$
extends uniquely to the affine space isomorphism
$\bar{\iota}\colon\mathbb{D}\rightarrow\mathbb{D}$ which assigns

$d=\frac{c-a}{b-a}=\frac{2k+1}{2^{n}}\in\mathbb{D}$

to $c$. The image $\bar{\iota}([a,c])$ is generated as a groupoid by
$\\{0,1,d=\frac{2k+1}{2^{n}}\\}$. Let $h$ be the isomorphism between
$\bar{\iota}([a,c])$ and the subgroupoid $H$ generated by
$\\{0,2^{n},2k+1\\}$. By [7, Cor. 3.9], the groupoid $H$ coincides with the
interval $[0,2k+1]$. Now consider the isomorphism $\overline{i}h$ between
$[a,c]$ and $H$. Then note that $(\overline{i}h)^{-1}$ takes $2k+1$ to $c$,
$2^{n}$ to $b$ and $0$ to $a$. Hence $[a,c]=\langle\\{a,b,c\\}\rangle$.

If $[b,c]$ is a simplex, then we take the isomorphism
$\iota\colon[b,c]\rightarrow[0,1]$ assigning $0$ to $c$ and $1$ to $b$. The
remaining part of the proof goes similarly to the proof of the first part. ∎

######  Lemma 3.2 (The Density Lemma).

Let $A\neq B\in\mathbb{D}^{n}\subset\mathbb{R}^{n}$. Let $l(A,B)$ be the line
in the affine $\mathbb{R}^{n}$-space $\mathbb{R}^{n}$ going through $A$ and
$B$. Then for any two points $C_{1}$ and $C_{2}$ of $l(A,B)$, there is a point
$D$ of $l(A,B)$ belonging to $\mathbb{D}^{n}$ and located between $C_{1}$ and
$C_{2}$.

###### Proof.

Let $A=(a_{1},\ldots,a_{n})$ and $B=(b_{1},\ldots,b_{n})$. The line $l(A,B)$
is described by the equations

$x_{i}=(b_{i}-a_{i})t+a_{i}$

for $i=1,\dots,n$. Let $C_{1}$ and $C_{2}$ be any points of $l(A,B)$, $C_{1}$
with coordinates $(b_{i}-a_{i})t_{1}+a_{i}$ and $C_{2}$ with coordinates
$(b_{i}-a_{i})t_{2}+a_{i}$ for some $t_{1},t_{2}\in\mathbb{R}$. There exists a
dyadic number $d$ lying between $t_{1}$ and $t_{2}$. Then the point $D$ with
coordinates $(b_{i}-a_{i})d+a_{i}$ belongs to $\mathbb{D}^{n}$ and is located
between $C_{1}$ and $C_{2}$. ∎

For an illustration of the following lemma, see Figure 1.

######  Lemma 3.3.

Let $P$ be an $n$-dimensional dyadic polytope, and let $\mathbf{S}$ be an
$n$-dimensional (geometric) simplex contained in $P$. Then for any interior
point $A$ of $P$ not contained in $\mathbf{S}$, there exists a point $B$ in a
maximal wall of $P$ and a point $C$ in $\rm{int}(\mathbf{S})$ such that $A$
belongs to the intersection $l(B,C)\cap P$ of the (real) line $l(B,C)$ through
$B$ and $C$ and $P$.

$A$$B$$C$$R_{3}$$R_{4}$$W_{1}$$C_{2}$$R_{1}$$R_{2}$$C_{1}$ Figure 1.

###### Proof.

We consider $P$ as a subset of $\mathbb{D}^{n}$ and $\mathbb{R}^{n}$ as
explained earlier. Let $Q=\mathrm{conv}_{\mathbb{R}}(P)$. Take
$C_{1}\in\mathrm{int}(\mathbf{S})$. There is a maximal wall $W$ of $Q$ such
that the real line $l(A,C_{1})$ through $A$ and $C_{1}$ has just one point of
intersection $R_{1}$ with $W$. Note that $R_{1}$ is not necessarily a member
of $\mathbb{D}^{n}$. The wall $W$ generates the hyperplane
$H=\mathrm{aff}_{\mathbb{R}}(W)$ in $\mathbb{R}^{n}$. Let
$W_{1}=(d_{1},\dots,d_{n})\neq R_{1}$ be one of the vertices of $W$. Since the
vertices of $W$ belong to $\mathbb{D}^{n}$, there is a vector
$v=(v_{1},\dots,v_{n})$ with dyadic coordinates such that the hyperplane $H$
is described by the equation

$\sum_{i=1}^{n}v_{i}(x_{i}-d_{i})=0.$

The point $R_{1}$ is the intersection of the hyperplane $H$ and the line
$l(A,C_{1})$ given by the equations

$x_{i}=(c_{i}-a_{i})t+a_{i},$

where $i=1,\dots,n$, $A=(a_{1},\dots,a_{n})$ and $C_{1}=(c_{1},\dots,c_{n})$.
Hence $R_{1}$ has rational coordinates ${r_{i}}/{s_{i}}$, as the solutions of
a system of linear equations with dyadic and hence rational coefficients.

The line $l(W_{1},R_{1})$ has the equations

$x_{i}=(\frac{r_{i}}{s_{i}}-d_{i})t+d_{i},$

and contains the dyadic point $D\neq W_{1}$ obtained for $t$ equal to the
least common multiple of all the $s_{i}$.

Recall that $C_{1}$ belongs to $\mathrm{int}(\mathbf{S})$ and $\mathbf{S}$ is
contained in the real simplex
$\mathbf{S}^{r}=\mathrm{conv}_{\mathbb{R}}(\mathbf{S})$. Choose a point
$R_{2}$ of $l(W_{1},R_{1})=l(W_{1},D)$ different from $R_{1}$ such that the
line $l(R_{2},A)$ has a nonempty intersection $C_{2}$ with
$\mathrm{int}(\mathbf{S}^{r})$. Since the line $l(W_{1},R_{1})$ contains two
dyadic points, it follows by the Density Lemma 3.2, that there is a dyadic
point $B$ located between $R_{1}$ and $R_{2}$. The (real) line $l(A,B)$
through $A$ and $B$ has a non-empty intersection with
$\mathrm{int}(\mathbf{S}^{r})$. Let $R_{3}$ and $R_{4}$ be any two different
real points in $l(A,B)\cap\mathrm{int}(\mathbf{S}^{r})$. Again by Density
Lemma, there is a dyadic point $C$ located between $R_{3}$ and $R_{4}$. ∎

######  Theorem 3.4.

Each $n$-dimensional dyadic polytope is finitely generated.

###### Proof.

The proof is by induction on $n$. Suppose that $P$ is a (nontrivial)
$n$-dimensional dyadic polytope. If $n=1$, then $P$ is a dyadic interval, and
by the results of [11], it is (minimally) generated by $2$ or $3$ generators.

Now let $n>1$. Assume that the theorem holds for all polytopes of dimension
smaller than $n$. Let the dimension of $P$ be $n$. The polytope $P$ contains
finitely many $(n-1)$-dimensional walls, say $W_{1},\dots,W_{r}$. By the
induction hypothesis, each of them is finitely generated. Moreover, by
Corollary 2.11, the polytope $P$ contains infinitely many geometric
$n$-dimensional simplices. Let $\mathbf{S}$ be one of them. Obviously, each
point of $\mathbf{S}$ is generated by the vertices of $\mathbf{S}$.

We will show that any point $A$ of $P$, contained neither in any of the walls
$W_{1},\dots,W_{r}$, nor in the simplex $\mathbf{S}$, is generated by the
generators of these walls and the generators of the simplex. By Lemma 3.3,
there is a point $B$ in a maximal wall $W_{i}$ and a point $C$ in the interior
$\rm{int}(\mathbf{S})$ of $\mathbf{S}$ such that the interval with ends $B$
and $C$ contains $A$. Without loss of generality, assume that this interval is
$[B,C]$. Consider the (geometric) subset $\mathbf{S}\cap[B,C]$ of the line
$l(A,B)$. By Corollary 2.11, this subset contains a one-dimensional simplex,
say $[D,C]$, with $D$ between $A$ and $C$. Note that the points $D$ and $C$
are generated by the generators of the simplex $\mathbf{S}$, and the point $B$
is generated by the generators of $W_{i}$. By Lemma 3.1, the points $B,C$ and
$D$ generate the whole interval $[B,C]$ containing the point $A$. It follows
that the polytope $P$ is generated by the finite number of the generators of
$W_{1},\dots,W_{r}$ and of the simplex $\mathbf{S}$. ∎

######  Remark 3.5.

Recall from Section 2 that each $n$-dimensional polytope $P$ is the union of
its maximal walls and the interior $\rm{int}(P)$ of $P$. The proof of Theorem
3.4 shows that $P$ is generated by the generators of these walls and $n+1$
vertices of an $n$-dimensional geometric simplex $\mathbf{S}$ contained in
$P$. As the maximal walls are $(n-1)$-dimensional polytopes themselves, the
proof provides a recursive method of finding generators of $P$. When the
generators of the maximal walls have already been determined, it suffices to
take the generators of the maximal walls and the vertices of $\mathbf{S}$ as
the generators of $P$.

As was shown in [7, §3], a finite number of distinct elements of the dyadic
line $\mathbb{D}$ generate a convex subset isomorphic to a dyadic interval, a
one-dimensional dyadic polytope. However, the relation between the finitely
generated subgroupoids of the groupoid $(\mathbb{D}^{n},\circ)$ and the
$n$-dimensional polytopes for $n>1$ has not yet been established. We discuss
this relationship in the following section.

##  4\. Finitely generated subgroupoids of $\mathbb{D}^{n}$

We already know that each finitely generated subgroupoid of $\mathbb{D}$ is
isomorphic to a dyadic interval. We would like to know if every finitely
generated subgroupoid of $\mathbb{D}^{n}$ is isomorphic to a dyadic polytope.
The following example shows that if $n>1$, then the situation may be more
complicated.

######  Example 4.1.

Consider the following four elements of the plane $\mathbb{D}^{2}$:

$A_{0}=(0,0),\,A_{1}=(1,3),\,A_{2}=(3,0),\,A_{3}=(1,1).$

(See Figure 2.)

$1$$1$$3$$A_{3}$$A_{2}$$3$$A_{0}$$A_{1}$ Figure 2.

We are looking for the groupoid $G$ generated by these elements. First note
that each triple of them generates an (algebraic) dyadic simplex. However two
of these simplices, the one generated by $A_{0},A_{1},A_{2}$ and the one
generated by $A_{0},A_{2},A_{3}$, do not contain all the points of the
interval $[A_{0},A_{2}]$, e.g. the points $(1,0)$ and $(2,0)$. It follows that
these simplices are not geometric. The other two triples generate geometric
dyadic simplices. This can be shown by providing automorphisms of the dyadic
plane $\mathbb{D}^{2}$ taking three of the corresponding generators to the
points $(0,0),(1,0),(0,1)$, which are known to be the free generators of the
dyadic simplex $\mathbf{S}_{2}$. For example, (right) multiplication by the
dyadic matrix

$M_{1}=\begin{bmatrix}-\tfrac{1}{2}&\tfrac{3}{2}\\\
\tfrac{1}{2}&-\tfrac{1}{2}\\\ \end{bmatrix}\,,$

with determinant equal to $-1/2$, provides an automorphism of the affine
$\mathbb{D}$-space $\mathbb{D}^{2}$ which takes $A_{0}$ to $(0,0)$, $A_{1}$ to
$(1,0)$ and $A_{3}$ to $(0,1)$. Similarly, translation by $(-1,-1)$ followed
by the automorphism given by the matrix

$M_{2}=\begin{bmatrix}\frac{1}{4}&\frac{1}{2}\\\ \frac{1}{2}&0\\\
\end{bmatrix}\,,$

with determinant equal to $-1/4$, takes the points $A_{1}$, $A_{2}$, $A_{3}$
to the points $(0,0),(1,0),(0,1)$. In particular, the points
$A_{0},A_{1},A_{2},A_{3}$ generate all the points of the (closed) dyadic
triangles $A_{0}A_{1}A_{3}$ and $A_{1}A_{2}A_{3}$.

We will show that the (dyadic) points of the interior of the triangle
$A_{0}A_{2}A_{3}$ are generated by the points $A_{0},A_{1},A_{2},A_{3}$. Let
$B$ be any point of the interior of the triangle $A_{0}A_{2}A_{3}$. The dyadic
line $l(A_{0},B)$ through the points $A_{0}$ and $B$ has a nonempty
intersection with the triangle $A_{1}A_{2}A_{3}$. By Corollary 2.11, this
intersection contains a closed interval $[C,D]$, with $C$ between $B$ and $D$,
which is a (geometric) dyadic simplex. By Lemma 3.1, the points $A_{0},C,D$
generate the dyadic interval $[A_{0},D]$, containing the point $B$, hence also
generated by the points $A_{0},C,D$.

Finally, recall that not all the points of the interval $[A_{0},A_{2}]$ are
generated by $A_{0}$ and $A_{2}$. It follows that the groupoid $G$ consists of
the whole interior of the triangle $A_{0}A_{1}A_{2}$, the dyadic intervals
$[A_{0},A_{1}]$ and $[A_{1},A_{2}]$, and the proper subgroupoid of the
interval $[A_{0},A_{2}]$ generated by its ends, and consisting of the points
$(d,0)$ with $0\leq d\leq 3$ with $d$ divisible by $3$. Hence the groupoid $G$
is not a dyadic triangle.

The groupoid $G$ of Example 4.1 is a finitely generated subgroupoid of
$(\mathbb{D}^{2},\circ)$, but it is not a dyadic polytope. Furthermore, the
groupoid $G$ is not isomorphic to any dyadic polytope. To see this, observe
first that since
$\mathrm{int}(A_{0}A_{1}A_{2})\cup]A_{0}A_{1}]\cup[A_{1}A_{2}[$ is geometric,
it follows that the affine $\mathbb{D}$-hull of $G$ is the whole plane
$\mathbb{D}^{2}$, and its convex $\mathbb{D}$-hull $\rm{conv}_{\mathbb{D}}(G)$
is the (closed) dyadic triangle with vertices $A_{0},A_{1},A_{2}$. Recall from
Section 2 that an algebraic convex set $C$ is geometric precisely when it
coincides with its convex $\mathbb{D}$-hull. Clearly, $G$ and
$\rm{conv}_{\mathbb{D}}(G)$ differ.

We will show, however, that finitely generated finite-dimensional algebraic
dyadic convex sets are not far from being polytopes.

######  Definition 4.2.

A subgroupoid $D$ of a dyadic polytope $C$ is called a _semipolytope_ if $C$
and $D$ have the same vertices and $D\,\cap\,\rm{int}(C)=\rm{int}(C)$.

In particular, $C=\rm{conv}_{\mathbb{D}}(D)$. Thus the interiors of $C$ and
$D$ coincide. Obviously, a semipolytope is an algebraic dyadic convex set.

######  Remark 4.3.

In [12], the concept of a _quasipolytope_ in an affine $\mathbb{R}$-space was
introduced. This is a convex set $A$ whose closure $\overline{A}$ in the
affine $\mathbb{R}$-space it generates is a polytope. Note that $A$ does not
need to contain the vertices of $\overline{A}$. Now define a real
semipolytope, similarly as in the dyadic case. Such real semipolytopes are
simply polytopes. On the other hand, quasipolytopes may be defined in the
dyadic case as well. (We consider the usual Euclidean topology on
$\mathbb{R}^{n}$, and then restrict it to $\mathbb{D}^{n}$.) Each dyadic
semipolytope is a quasipolytope. However, dyadic quasipolytopes are not
necessarily semipolytopes. Examples are provided by open polytopes (interiors
of polytopes). Note also that the topological closures of geometric dyadic
convex sets admit a purely algebraic description [4].

######  Example 4.4.

The groupoid $G$ of Example 4.1 is a semipolytope. It has the same interior as
the (closed) triangle $A_{0}A_{1}A_{2}$ and the same vertices.

######  Example 4.5.

Consider the semipolytope $S$ in the plane $\mathbb{D}^{2}$ consisting of the
interior of the triangle with vertices $A_{0}=(0,0)$, $A_{1}=(0,1)$ and
$A_{2}=(9,0)$, the sides $A_{0}A_{1}$ and $A_{1}A_{2}$, and the subgroupoid
$G$ of the side $A_{0}A_{2}$ consisting of the pairs $(d,0)$ with $d$
divisible by $3$ (and generated by the points $A_{0},A_{2}$ and $D=(3,0)$).
The convex $\mathbb{D}$-hull of $S$ is the (closed) triangle
$A_{0}A_{1}A_{2}$. Choose the point $E=(1,1/2)$ of $S$. Since the points
$A_{0},E,A_{1}$ generate the triangle $A_{0}EA_{1}$, Corollary 2.13 implies
that $A_{0}EA_{1}$ is geometric. Using this fact, one may show (as in Example
4.1) that each interior point of $S$ is generated by the points
$A_{0},A_{1},A_{2}$ and $E$. Hence $S$ is finitely generated by five points
$A_{0},A_{1},A_{2},D,E$. (See Figure 3.) Note that $G$ forms a wall of $S$,
which is not a polytope in $\mathbb{D}^{2}$. Neither is it a polytope in the
$x$-axis, which is a subspace of $\mathbb{D}^{2}$. However, $G$ is a polytope
in its affine $\mathbb{D}$-hull, which consists of the elements $(d,0)$ of the
$x$-axis with $d$ divisible by $3$.

$1$$1$$A_{1}$$A_{2}$$9$$D$$3$$A_{0}$$E$ Figure 3.

######  Example 4.6.

Consider again the semipolytope $S$ of Example 4.5 and the dyadic triangle
$A_{0}A_{1}A_{2}$ with vertices $A_{0},A_{1},A_{2}$. Note that the matrix

$\begin{bmatrix}5&0\\\ 0&3\end{bmatrix}$

provides an isomorphism $\kappa$ from $\mathbb{D}^{2}$ with the dyadic
triangle $A_{0}A_{1}A_{2}$ as its subgroupoid onto the subspace

$\\{(5d,0)\mid d\in\mathbb{D}\\}\times\\{(0,3d)\mid
d\in\mathbb{D}\\}=5\mathbb{D}\times 3\mathbb{D}$

of $\mathbb{D}^{2}$. Then note that $5\mathbb{D}\times 3\mathbb{D}$ is the
affine $\mathbb{D}$-hull of $\kappa(A_{0}A_{1}A_{2})$. The image
$\kappa(A_{0}A_{1}A_{2})$ is an algebraic dyadic convex subset of the affine
$\mathbb{D}$-space $\mathbb{D}^{2}$ and isomorphic to the dyadic triangle
$A_{0}A_{1}A_{2}$. The image $\kappa(S)$ is a finitely generated algebraic
dyadic convex subset of $\mathbb{D}^{2}$ isomorphic to the semipolytope $S$,
but is not a semipolytope.

Note that the walls of the semipolytopes in $\mathbb{D}^{2}$ of Examples 4.1
and 4.5 are also semipolytopes; not necessarily in $\mathbb{D}^{2}$, but
relative to their affine $\mathbb{D}$-hulls. We will see that this is a
property of general semipolytopes. First note that if $S$ is a semipolytope in
$\mathbb{D}$, then it is an interval, and hence a polytope. Note however that
a polytope in $m\mathbb{D}$ for odd $m\neq 1$ is not a polytope in
$\mathbb{D}$. A two-dimensional semipolytope $S$ in $\mathbb{D}^{2}$ has the
same interior as its convex $\mathbb{D}$-hull $\mathrm{conv}_{\mathbb{D}}(S)$.
The walls of $S$ are subgroupoids of some dyadic lines in $\mathbb{D}^{2}$,
but they are not necessarily geometric. More generally, $0$-dimensional walls
of an $n$-dimensional semipolytope $S$ are the vertices of $S$ and
$1$-dimensional walls are the intersections of $S$ with the edges of
$\mathrm{conv}_{\mathbb{D}}(S)$. An $n$-dimensional semipolytope $S$ has the
same interior as its convex $\mathbb{D}$-hull $\mathrm{conv}_{\mathbb{D}}(S)$,
and this interior is obviously geometric. However, the walls of $S$ are
subgroupoids of some affine subspaces of $\mathbb{D}^{n}$, and do not need to
be geometric.

Let $C$ be an algebraic dyadic convex subset of an $n$-dimensional subspace
$A$ of $\mathbb{D}^{n}$. Then the _convex $A$-hull_ $\mathrm{conv}_{A}(C)$ of
$C$ in $A$ is the intersection of $\mathrm{conv}_{\mathbb{R}}(C)$ with $A$,

$\mathrm{conv}_{A}(C)=\mathrm{conv}_{\mathbb{R}}(C)\cap A.$

Since $\mathrm{aff}_{\mathbb{D}}(C)$ is a subspace of $\mathbb{D}^{n}$, it
follows that

(4.1) $\displaystyle\mathrm{conv}_{\mathrm{aff}_{\mathbb{D}}(C)}(C)$
$\displaystyle=\mathrm{conv}_{\mathbb{R}}(C)\cap\mathrm{aff}_{\mathbb{D}}(C)$
$\displaystyle=\mathrm{conv}_{\mathbb{D}}(C)\cap\mathrm{aff}_{\mathbb{D}}(C).$

######  Proposition 4.7.

Let $S$ be an $n$-dimensional semipolytope. Then the following hold.

  * (a)

A subset $W$ of $S$ is a wall of $S$ if and only if it is the intersection
with $S$ of a wall of the convex $\mathbb{D}$-hull
$\mathrm{conv}_{\mathbb{D}}(S)$ of $S$.

  * (b)

Each wall $W$ of $S$ is a semipolytope in the affine $\mathbb{D}$-hull
$\mathrm{aff}_{\mathbb{D}}(W)$ of $W$.

###### Proof.

$(\rm a)$ First note that $S$ and $\mathrm{conv}_{\mathbb{D}}(S)$ have the
same vertices and the same interior, and by the last remarks of Section $2.3$,
the walls of $\mathrm{conv}_{\mathbb{D}}(S)$ are determined by the vertices
they contain. If $W^{\prime}$ is a wall of $\mathrm{conv}_{\mathbb{D}}(S)$,
then $W^{\prime}\cap S$ is a wall of $S$. On the other hand, if $W$ is a wall
of $S$, then $W=S\cap F$, where $F$ is the wall of
$\mathrm{conv}_{\mathbb{D}}(S)$ determined by the vertices of $W$.

$(\rm b)$ Let $A:=\mathrm{aff}_{\mathbb{D}}(W)$ be the affine
$\mathbb{D}$-hull of $W$. Note that, by (4.1),
$\mathrm{conv}_{A}(W)=\mathrm{conv}_{\mathbb{D}}(W)\cap A$. Hence
$\mathrm{int}(\mathrm{conv}_{A}(W))=\mathrm{int}(W)$, and obviously
$\mathrm{conv}_{A}(W)$ and $W$ have the same vertices. ∎

######  Definition 4.8.

Consider an $n$-dimensional subspace $A$ of $\mathbb{D}^{n}$.

  1. (a)

A _dyadic $n$-dimensional polytope in $A$_ or _$A$ -polytope_ is the
intersection with the space $A$ of an $n$-dimensional real polytope whose
vertices lie in the space $A$.

  2. (b)

A subgroupoid $D$ of a dyadic polytope $C$ in $A$ is called a _semipolytope in
$A$_ or an _$A$ -semipolytope_ if $C$ and $D$ have the same vertices and the
same (relative) interiors. Thus a semipolytope is a semipolytope in
$\mathbb{D}^{n}$.

In what follows, we are mostly interested in finitely generated algebraic
dyadic convex sets. Note that such sets are finite-dimensional, since their
affine $\mathbb{D}$-hulls are finitely generated.

######  Lemma 4.9.

Let $C$ be a finitely generated algebraic dyadic convex set with the
$n$-dimensional affine $\mathbb{D}$-hull $A$, a subspace of $\mathbb{D}^{n}$.
Then the following hold.

  * (a)

The walls of $C$ are the intersections with $C$ of the walls of
$\mathrm{conv}_{A}(C)$.

  * (b)

The union of the maximal walls of $C$ generates a subgroupoid of the groupoid
$C$.

  * (c)

The equality $\rm{int}(C)=\rm{int}(\mathrm{conv}_{A}(C))$ holds.

  * (d)

The dyadic convex sets $C$, $\mathrm{conv}_{A}(C)$,
$\mathrm{conv}_{\mathbb{D}}(C)$ and the real convex set
$\mathrm{conv}_{\mathbb{R}}(C)$ share the same vertices.

  * (e)

The convex $A$-hull $\mathrm{conv}_{A}(C)$ of $C$ is an $A$-polytope, and
hence its walls are also $A$-polytopes.

  * (f)

The dyadic convex set $C$ is a semipolytope in $A$.

###### Proof.

$(\rm a)$ and $(\rm b)$ are obvious, while $(\mathrm{c})$ follows directly
from the fact that $A=\rm{aff}_{\mathbb{D}}(C)$.

$(\rm d)$ Since $C$ is finitely generated, it follows that the barycentric
algebra $\mathrm{conv}_{\mathbb{R}}(C)$ is also finitely generated. Hence it
is a real polytope. Its vertices belong to $C$, to $\mathrm{conv}_{A}(C)$, and
to $\mathrm{conv}_{\mathbb{D}}(C)$.

$(\rm e)$ Since $\mathrm{conv}_{\mathbb{R}}(C)$ is a real polytope, it follows
that
$\mathrm{conv}_{\mathbb{D}}(C)=\mathrm{conv}_{\mathbb{R}}(C)\cap\mathbb{D}^{n}$
is a dyadic polytope. Then, by (4.1) and $(\rm d)$, $\mathrm{conv}_{A}(C)$ is
a polytope in $A$.

$(\rm f)$ This follows directly by $(\rm c),(\rm d)$ and $(\rm e)$. ∎

######  Proposition 4.10.

Each finitely generated algebraic dyadic convex set is isomorphic to a
semipolytope.

###### Proof.

Let $C$ be an algebraic convex subset of $\mathbb{D}^{p}$ generated by a
finite set $X=\\{x_{0},x_{1},\cdots,x_{r}\\}$. Let
$A=\mathrm{aff}_{\mathbb{D}}(C)$ with $\dim A=n\leq p$ and $n\leq r$.

By Lemma 4.9, $C$ is a semipolytope in $A$. Moreover, $C$,
$\mathrm{conv}_{A}(C)$, $\mathrm{conv}_{\mathbb{D}}(C)$ and
$\mathrm{conv}_{\mathbb{R}}(C)$ have the same set $V$ of vertices contained in
$X$. Moreover, $\rm{int}(C)=\rm{int}(\mathrm{conv}_{A}(C))$.

By Lemma 2.10, $C$ contains an $n$-dimensional algebraic simplex $\mathbf{S}$
isomorphic as a groupoid to the (geometric) dyadic simplex $\mathbf{S}_{n}$.
The simplex $\mathbf{S}$ is also contained in $A=\rm{aff}_{\mathbb{D}}(C)$,
and its vertices $s_{0},\dots,s_{n}$ freely generate the affine
$\mathbb{D}$-space $A$, which is a subspace of $\mathbb{D}^{n}$ (isomorphic to
$\mathbb{D}^{n}$) and the affine $\mathbb{R}$-space $\mathbb{R}^{n}$.

On the other hand, the space $\mathbb{D}^{n}$ contains the dyadic simplex
$\mathbf{S}_{n}$. Its vertices $e_{0},\dots,e_{n}$ freely generate the
groupoid $\mathbf{S}_{n}$, the affine $\mathbb{D}$-space $\mathbb{D}^{n}$, and
the affine $\mathbb{R}$-space $\mathbb{R}^{n}$.

The bijective mapping $\iota\colon s_{i}\mapsto e_{i}$ assigning the vertices
of $\mathbf{S}$ to the vertices of $\mathbf{S}_{n}$ extends uniquely to the
authomorphism $\overline{\overline{\iota}}$ of the affine $\mathbb{R}$-space
$\mathbb{R}^{n}$, restricting to the isomorphism $\overline{\iota}$ between
the affine $\mathbb{D}$-spaces $A$ and $\mathbb{D}^{n}$. The authomorphism
$\overline{\overline{\iota}}$ restricts to the groupoid isomorphism between
$\mathrm{conv}_{A}(C)$ and its image
$\overline{\iota}(\mathrm{conv}_{A}(C))=\overline{\overline{\iota}}(\mathrm{conv}_{A}(C))$
in $\mathbb{D}^{n}$.

Our aim is to prove that $\overline{\iota}(C)$ is a semipolytope, which
implies that $C$ is isomorphic to a semipolytope.

First note that $\overline{\iota}(C)$ is a subgroupoid of
$\overline{\iota}(\mathrm{conv}_{A}(C))$. Since $\overline{\iota}$ is an
isomorphism, it follows by Lemma 4.9, (d) and (c), that $\overline{\iota}(C)$
and $\overline{\iota}(\mathrm{conv}_{A}(C))$ have the same vertices and the
same (relative) interiors. It remains to show that
$\overline{\iota}(\mathrm{conv}_{A}(C))$ is a dyadic polytope. By (2.4), this
means that

(4.2)
$\overline{\iota}\big{(}\mathrm{conv}_{A}(C)\big{)}=\mathrm{conv}_{\mathbb{R}}\big{(}\overline{\iota}(\mathrm{conv}_{A}(C))\big{)}\cap\mathbb{D}^{n}.$

The inclusion
$\overline{\iota}\big{(}\mathrm{conv}_{A}(C)\big{)}\subseteq\mathrm{conv}_{\mathbb{R}}\big{(}\overline{\iota}(\mathrm{conv}_{A}(C))\big{)}\cap\mathbb{D}^{n}$
follows by (4.1). To show that the reverse inclusion holds as well, first
observe that

(4.3)
$\mathrm{conv}_{\mathbb{R}}\big{(}\overline{\iota}(\mathrm{conv}_{A}(C))\big{)}=\overline{\overline{\iota}}\big{(}\mathrm{conv}_{\mathbb{R}}(C)\big{)}.$

Now let
$x\in\mathrm{conv}_{\mathbb{R}}\big{(}\overline{\iota}(\mathrm{conv}_{A}(C))\big{)}\cap\mathbb{D}^{n}=\overline{\overline{\iota}}\big{(}\mathrm{conv}_{\mathbb{R}}(C)\big{)}\cap\mathbb{D}^{n}$.
Then $x=\sum a_{i}e_{i}$ for some $a_{i}\in\mathbb{D}$. Hence
$\overline{\iota}^{-1}(x)=\sum a_{i}s_{i}\in A$ and
$\overline{\iota}^{-1}(x)\in\mathrm{conv}_{\mathbb{R}}(C)$. Therefore
$\overline{\iota}^{-1}(x)\in\mathrm{conv}_{A}(C)$, and consequently,
$x\in\overline{\iota}(\mathrm{conv}_{A}(C))$. Hence
$\overline{\iota}(\mathrm{conv}_{A}(C))$ is a dyadic polytope. ∎

Our aim is to prove that all semipolytopes are finitely generated. First we
will need some additional information concerning real convex polytopes. Let
$C$ be an $(n+1)$-dimensional convex polytope in the affine $\mathbb{R}$-space
$\mathbb{R}^{n+1}$ with vertex set $V=\\{x_{0},\dots,x_{k}\\}$, where $k>n$,
and with the set $\mathrm{W}$ of $n$-dimensional walls $W_{1},\dots,W_{r}$.
Choose one interior point $y_{i}$ from each wall $W_{i}$, and call it an
_anchor_ on $W_{i}$. Let $Y$ be the set $\\{y_{1},\dots,y_{r}\\}$ of all
anchors. The anchors $y_{i}$ generate the subpolytope
$P=\rm{conv}_{\mathbb{R}}(Y)$ of $C$, which will be called an _inner polytope_
of $C$. (For an example, see Figure 4.) Note that an inner polytope has the
same dimension as the polytope $C$.

$x_{0}$$x_{1}$$x_{4}$$x_{3}$$x_{2}$$y_{1}$$y_{2}$$y_{3}$$y_{4}$$y_{5}$$x_{1}$$x_{4}$$x_{3}$$x_{2}$
Figure 4.

If $S$ is an $n$-dimensional semipolytope in an $m$-dimensional dyadic space
with $n\leq m$, then without loss of generality, we will consider $S$ as a
semipolytope in the $n$-dimensional dyadic space that forms the dyadic affine
hull of $S$.

Let $S$ be a (nontrivial) $n$-dimensional semipolytope in the space
$\mathbb{D}^{n}$. It is a subgroupoid of its convex $\mathbb{D}$-hull
$S_{d}:=\mathrm{conv}_{\mathbb{D}}(S)$, which is in turn a subgroupoid of its
convex $\mathbb{R}$-hull $S_{r}=\mathrm{conv}_{\mathbb{R}}(S)$. Recall that
$S$, $S_{d}$ and $S_{r}$ have the same vertices. Choose a set of anchors of
the maximal walls of the (real) polytope $S_{r}$, belonging to the
semipolytope $S$. The anchors generate the inner polytope $P_{r}$ of $S_{r}$.
The intersection $P:=P_{r}\cap S$ is a (dyadic) subpolytope of $S$, and is
called an _inner polytope_ of $S$. By Proposition 4.7, the walls of $S$ are
the intersections of the walls of $S_{r}$ with $S$, and each one is a
semipolytope in its affine $\mathbb{D}$-hull.

Now it remains to show that all semipolytopes are finitely generated. We start
with an extension of Lemma 3.3.

######  Lemma 4.11.

Let $S$ be an $n$-dimensional semipolytope, and let $P$ be an inner polytope
of $S$. Then for any interior point $A$ of $S$ not contained in $P$, there
exists a point $B$ in a maximal wall of $S$ and a point $C$ in $\rm{int}(P)$
such that $A$ belongs to the intersection $l(B,C)\cap S$ of the (real) line
$l(B,C)$ through $B$ and $C$ and $S$.

###### Proof.

The proof is very similar to the proof of Lemma 3.3, with the polytope $P$
replaced by the semipolytope $S$, and the simplex $\mathbf{S}$ replaced by the
inner polytope $P$ of $S$. The only difference concerns the location of the
point $B$, which can be obtained as follows. Let
$k(W_{1},R_{1})=l(W_{1},R_{1})\cap\rm{aff}_{\mathbb{D}}(W)$. Let $\iota\colon
k(W_{1},R_{1})\rightarrow\rm{aff}_{\mathbb{D}}(W)$ be an isomorphism of affine
$\mathbb{D}$-spaces and let $\overline{\iota}\colon
l(W_{1},R_{1})\rightarrow\mathbb{R}$ be its extension to the affine
$\mathbb{R}$-space isomomorhism. By the Density Lemma 3.3, there is a point
$B^{\prime}$ of $\rm{aff}_{\mathbb{D}}(W)$ located between
$\overline{\iota}(R_{1})$ and $\overline{\iota}(R_{2})$. Then
$B=\iota^{-1}(B^{\prime})$ is a point of $\rm{aff}_{\mathbb{D}}(W)$ located
between $R_{1}$ and $R_{2}$. ∎

######  Proposition 4.12.

Each semipolytope is finitely generated.

###### Proof.

Let $S$ be a (nontrivial) $n$-dimensional semipolytope in the space
$\mathbb{D}^{n}$. The proof is by induction on $n$. If the dimension of $S$ is
$1$, then its convex $\mathbb{D}$-hull $S_{d}:=\mathrm{conv}_{\mathbb{D}}(S)$
is an interval, and by results of [11], it is (minimally) generated by $2$ or
$3$ elements. In this case, the semipolytope $S$ and the polytope $S_{d}$
coincide.

Now assume that the result holds for all dimensions less or equal to $n$.
Consider a semipolytope $S$ of dimension $n+1$ with vertices
$\\{x_{0},x_{1},\dots,x_{k}\\}$, where $k>n$, but minimally generated by a
possibly bigger set of generators containing the set of all vertices. The
walls of $S$ are intersections of the walls of the polytope $S_{d}$ with the
semipolytope $S$, and $S$ has a finite number of walls. By Proposition 4.7,
all proper nontrivial walls of $S$ (each of dimension not greater than $n$)
are semipolytopes in their affine $\mathbb{D}$-hulls. By the induction
hypothesis, they are finitely generated.

Now choose (dyadic) anchors $y_{1},\dots,y_{r}$ of the maximal walls
$W_{1},\dots,W_{r}$ of $S$, and consider the corresponding inner polytope $P$
of $S$. Recall that, by the induction hypothesis, all maximal proper walls are
finitely generated, and by Theorem 3.4, $P$ is also finitely generated. We
will show that each point of $S$, not contained in a maximal proper wall
$W_{i}$ or in the inner polytope $P$, is generated by an element of a maximal
proper wall and two elements of the inner polytope $P$. The proof is similar
to the last part of the proof of Theorem 3.4. Let $A$ be an interior point of
$S$ not contained in the inner polytope $P$. By Lemma 4.11, there is a point
$B$ in a maximal wall $W_{i}$ of $S$ and a point $C$ in $\rm{int}(P)$ such
that $A$ belongs to the intersection $l(B,C)\cap S$ of the (real) line
$l(B,C)$ through $B$ and $C$ and $S$. Without loss of generality assume that
$A$ belongs to the interval $[B,C]$. Then, by Corollary 2.11, the intersection
$P\cap l(B,C)$ contains a point $D$, with $D$ between $A$ and $C$, such that
the interval $[D,C]$ is a one-dimensional (geometric) simplex. By Lemma 3.1,
the points $B,C$, and $D$ generate the whole dyadic interval $[B,C]$ of the
line $l(B,C)$ containing the point $A$. Recall that the points $C$ and $D$ are
generated by the generators of $P$, and the point $B$ is generated by the
generators of the wall $W_{i}$. It follows that the semipolytope $S$ is
generated by the finite number of generators of the finite number of maximal
proper walls $W_{i}$ and the finite number of generators of the polytope $P$.
∎

##  5\. Main result

The results obtained in the previous sections may be summarized by the
following theorem.

######  Theorem 5.1.

A subgroupoid $(D,\circ)$ of the groupoid $(\mathbb{D}^{n},\circ)$ is finitely
generated precisely if it is isomorphic to a semipolytope.

######  Remark 5.2.

Recall that each $n$-dimensional semipolytope $S$ is the standard sum of an
inner polytope $P$ and outer subsemipolytopes $P_{i}$ determined by $P$. The
proof of Theorem 5.1 shows that each point of $S$ contained in any of the
$P_{i}$, but not contained in a maximal proper wall or in the inner polytope
$P$, is generated by an element of a maximal proper wall of $S$ and two
elements of the inner polytope $P$. As the maximal walls and the inner
polytope $P$ are all finitely generated, the proof provides a recursive method
of finding generators of $S$. To generate the semipolytope $S$, it is enough
to take the generators of all the maximal walls, and of the polytope $P$.

The following example shows that there are geometric dyadic convex sets, with
a finite number of vertices, which are not finitely generated.

######  Example 5.3.

Consider the unit disc in the real plane, and its intersection $U$ with the
dyadic plane. The boundary of the unit disc is the circle given by the
equation $x^{2}+y^{2}=1$. Note that the points $(-1,0)$, $(0,-1)$, $(1,0)$ and
$(0,1)$ belong to the circle. For any dyadic point $(j/2^{m},k/2^{n})$ of the
circle, with say $0<m\leq n$, and odd integers $j$ and $k$, we have

(5.1) $k^{2}=2^{2(n-m)}(2^{2m}-j^{2}).$

(The case when $0<n\leq m$, will be similar.) Note that the left-hand side of
(5.1) is odd. If $m\neq n$, then the right-hand side of (5.1) is even. If
$m=n$, then $j^{2}+k^{2}=2^{2n}$. Let $j=2a+1$ and $k=2b+1$. Then
$1/2(j^{2}+k^{2})=2(a^{2}+a+b^{2}+b)+1=2^{2n-1}$. This holds only if $n=1/2$,
again a contradiction. Consequently, the unique dyadic points belonging to the
circle are $(-1,0)$, $(0,-1)$, $(1,0)$ and $(0,1)$. It follows that $U$
consists of the dyadic points of the interior of the real unit disc and these
four points. The four points generate the geometric square contained in $U$.
But no finite set of elements of $U$ generates the full set of points of $U$
not contained in the square.

##  6\. Counting the number of generators

In this concluding section, we will illustrate how to use the main results of
the paper to find a minimal set of generators of some semi-polygons, and
estimate their number.

In [11], it was shown that all dyadic polygons (and in particular all
intervals and triangles) are finitely generated. However, the methods we used
in the proof did not provide an efficient way to find a minimal set of
generators, or to calculate their number. In this section we will show how to
use the results of the previous sections to solve such problems. In
particular, we will show how to find a minimal set of generators of dyadic
triangles and semipolytopes closing to triangles, i.e. semipolytopes with
dyadic triangles as their closure. We will call such semipolytopes
_semitriangles_.

We already know that finitely generated (algebraic) convex subsets of the
dyadic line $\mathbb{D}$ are isomorphic to intervals, and that each dyadic
interval is minimally generated by $2$ or $3$ elements. As shown in [11], each
nontrivial interval of $\mathbb{D}$ is isomorphic to some dyadic interval
$\mathbb{D}_{k}=[0,k]$, where $k$ is an odd positive integer. Two such
intervals are isomorphic precisely when their right hand ends are equal. Any
set of generators must contain the vertices. If $k\neq 1$, then to generate
$\mathbb{D}_{k}$, one more generator is needed. This can be the number $1$,
for example. As semipolytopes in $\mathbb{D}$ coincide with polytopes, we do
not need to consider them separately.

###  6.1. Dyadic triangles and polygons

Now let us consider dyadic triangles. Dyadic triangles were classified in
[11], with some improvements given in [8]. First recall the following lemma.

######  Lemma 6.1.

[11, L. 5.2] Each dyadic triangle is isomorphic to a triangle $ABC$ contained
in the first quadrant, with one vertex, say $A$, located at the origin, and
with the vertices $B$ and $C$ having non-negative integer coordinates. (See
Figure 5.)

$n$$i$$j$$m$$G$$A$$B$$C$ Figure 5.

The integers $i,j,m,n$ in Figure 5 may be chosen so that $0\leq i<m$, $0\leq
n<j$, and with odd $\gcd\\{i,m\\}$ and $\gcd\\{j,n\\}$. Such a triangle will
be denoted $T_{i,j,m,n}$.

To provide a more detailed description of triangles $ABC$ located as in Lemma
6.1, we need some further definitions. An interval of $\mathbb{D}$ is of _type
$k$_ if it is isomorphic to $\mathbb{D}_{k}$. A dyadic triangle has _boundary
type_ $(r,s,t)$, where $r,s,t$ are odd positive integers, if its sides have
respective types $r,s$ and $t$. A dyadic triangle $ABC$ (as described in Lemma
6.1) is of _right_ type if its shorter sides lie on the coordinate axes. It is
determined uniquely up to isomorphism by its boundary type. In particular, if
the types of the shorter sides are $m$ and $j$, then the hypotenuse is of type
$\gcd\\{m,j\\}$. (See [11, § 4].) A dyadic triangle $ABC$ is of _hat_ type if
$C$ lies on the $x$-axis. Note that a hat triangle is the union of two right
triangles $ABD$ and $BDC$, where $D$ is the projection of $B$ onto the
$x$-axis.

When a vertex $A$ of a dyadic triangle located at the origin is already
chosen, the triangle $ABC$ described in Lemma 6.1, may come in one of the
three types described in the following proposition.

######  Proposition 6.2.

[11, § 5,§ 6],[8, § 1] Each dyadic triangle $ABC$ contained in the first
quadrant, with $A$ located at the origin, is isomorphic to a triangle
$T_{i,j,m,n}$ of precisely one of the three following types:

  * (a)

right triangles $T_{0,j,m,0}$ with $j$ and $m$ odd and $j\leq m$;

  * (b)

hat triangles $T_{i,j,m,0}$ with $0<i\leq m/2$, odd $j>1$, and
$\gcd\\{i,j\\}\neq j$;

  * (c)

other triangles, such that neither of $i,n$ is zero, and moreover $j\leq m$,
$\gcd\\{i,j\\}\notin\\{i,j,1\\}$ and $\gcd\\{m,n\\}\notin\\{m,n,1\\}$.

For a fixed vertex $A$, the triangles $T_{i,j,m,n}$ described in Proposition
6.2 are sometimes called _representative triangles_ , of types (a), (b) and
(c), respectively.

As we will now restrict our attention to dyadic convex sets, we may sometimes
drop the adjective “dyadic” when it is clear from the context.

######  Remark 6.3.

Proposition 6.2 provides a classification, up to $\mathbb{D}$-module
automorphism of the plane $\mathbb{D}^{2}$, of dyadic triangles with one
chosen vertex located at the origin. Let us call such triangles _pointed
triangles_. For each dyadic triangle $T$, there are three pointed translated
triangles isomorphic to $T$. By Lemma 6.1 and Proposition 6.2, each one of
these is then isomorphic to the corresponding representative triangle located
as shown in Lemma 6.1. Note, however, that one of the three representative
triangles of a triangle $T$ may be of type (c), while another may be of the
hat type (b).

To see this, consider a triangle $T_{i,j,m,n}$ of type (c). Recall that the
conditions provided in Proposition 6.2(c) guarantee that the points $B$ and
$C$ are not axial. This means that there is no $\mathbb{D}$-module
automorphism of the plane $\mathbb{D}^{2}$ which maps any of these points to a
point on one of the axes. (See [11, Lemma 4.11].) To make the calculations
easier, assume additionally that $j>i$ and $m>n$. Now translate the triangle
$ABC$ by the vector $(-i,-j)$ to obtain the triangle with vertices
$(-i,-j),(0,0),(m-i,n-j)$, then use the symmetry with respect to the axis
$Ox$, and finally use the isomorphism of the plane $\mathbb{D}^{2}$ given by
the matrix

$\begin{bmatrix}1&0\\\ 1&1\end{bmatrix}\,.$

One obtains the triangle with vertices $A^{\prime}=(j-i,j),B^{\prime}=(0,0)$
and $C^{\prime}=(m-n+j-i,j-n)$. The triangle $A^{\prime}B^{\prime}C^{\prime}$
is contained in the first quadrant, and is not a right triangle. However it
may be of type (b) or (c). Indeed, if $B=(i,j)=(12,15)$ and $C=(m,n)=(15,12)$,
then $A^{\prime}=(j-i,j)=(3,15)$ and $C^{\prime}=(m-n+j-i,j-n)=(6,3)$, and
both points $A^{\prime}$ and $C^{\prime}$ are axial. So for each of these
vertices, one can find an affine space automorphism taking it to a point of an
axis. For example the automorphism given by the matrix

$\begin{bmatrix}1&1\\\ 0&-2\end{bmatrix}$

maps the triangle $A^{\prime}B^{\prime}C^{\prime}$ onto the triangle with
vertices $A^{\prime\prime}=(3,-27),\\\
B^{\prime\prime}=(0,0),C^{\prime\prime}=(6,0)$. Then the symmetry with respect
to the $x$-axis maps the triangle
$A^{\prime\prime}B^{\prime\prime}C^{\prime\prime}$ onto the triangle with
vertices $(3,27),(0,0),\\\ (6,0)$. The latter triangle is isomorphic to the
representative hat triangle $T_{1,9,2,0}$ with vertices
$A^{o}=(1,9),B^{o}=(0,0),C^{o}=(2,0)$.

However, if $B=(10,25)$ and $C=(15,9)$, then $A^{\prime}=(15,25)$ and
$C^{\prime}=(21,16)$, which are not axial. Hence also the (representative)
triangle $A^{\prime}B^{\prime}C^{\prime}$ is of type (c).

The triangles obtained are illustrated on Figures 6, 7 and 8.

$B=(12,15)$$C=(15,12)$$3$$3$$A$$A^{\prime}=(3,15)$$C^{\prime}=(6,3)$$3$$3$$B^{\prime}$
Figure 6.
$3$$9$$B^{\prime\prime}$$C^{\prime\prime}=(6,0)$$A^{\prime\prime}=(3,-27)$$1$$3$$B^{o}$$C^{o}=(2,0)$$A^{o}=(1,9)$
Figure 7.
$B=(10,25)$$C=(15,9)$$5$$5$$A$$A^{\prime}=(15,25)$$C^{\prime}=(21,16)$$5$$5$$B^{\prime}$
Figure 8.

The method used in the proof of Theorem 3.4 shows how to find generators of
any representative triangle $T=T_{i,j,m,n}$. One needs generators of the sides
and generators of any two-dimensional simplex $\mathbf{S}$ contained in $T$.
Each side of the triangle $T$ is an interval, and so is generated by $2$ or
$3$ elements (two vertices and possibly one additional generator), and the
simplex has three generators. In fact, we do not need all three generators of
the simplex. As one of the vertices of $\mathbf{S}$, we can take any point $E$
in the interior of $T$ which is a barycentric combination of all three
vertices of $T$. Sometimes, even less number of generators is sufficient. If
$T$ is a right triangle, then the minimal set of generators of its sides
provides a minimal set of generators of the triangle. Hence the minimal number
of generators of a right triangle lies between $3$ and $6$. For example, the
right triangle $T=T_{0,3,3,0}$ is minimally generated by the vertices and
three additional points $(0,1),\,(1,0)$ and $(2,1)$ (see Figure 9).

$1$$1$$0$$(3,0)$$(0,3)$ Figure 9.

The hat triangle with vertices $(-1,0),(0,1),(0,3)$ is minimally generated by
its vertices and the point $(0,1)$. On the other hand, seven generators are
sufficient to generate the hat triangle of the next example.

######  Example 6.4.

The hat triangle $T=T_{3,15,6,0}$ is minimally generated by the vertices and
four additional points $(1,5),(5,5),(1,0)$ and $(1,1)$ (see Figure 10).

$1$$5$$(1,1)$$0$$(6,0)$$(3,15)$ Figure 10.

For polygons, one may use a similar method as in the case of general dyadic
triangles. A polygon $P$ is generated by the generators of its sides and two
generators of a (right) simplex $\mathbf{S}$ chosen similarly as in the case
of dyadic triangles.

######  Example 6.5.

Consider the polygon $P$ with the vertices of the triangle of Example 6.4 and
one additional vertex $(3,-1)$. Then the points $(0,0),(1,0),(6,0)$ and
$(3,-1)$ generate the triangle with vertices $(0,0),(6,0),(3,-1)$ and the
polygon $P$ is minimaly generated by the generators of the hut triangle and
the vertex $(3,-1)$.

###  6.2. Dyadic semitriangles

Next we consider semitriangles, i.e. semi-polytopes closing to triangles.
Without lose of generality, we assume that a semitriangle $S$ is a
_representative semitriangle_ , with a representative triangle $T=T_{i,j,m,n}$
as its closure. The one-dimensional walls of $S$ will be called its _sides_. A
semitriangle $S$ which is not a polytope has at least one side which is not an
interval. Each side of $S$ is isomorphic to an interval; hence it is generated
by $2$ or $3$ elements. (Recall that a minimal set of generators of $S$ must
contain the minimal set of generators of the sides.) To find the remaining
generators of $S$, one may use the method described in the proof of
Proposition 4.12. Since anchors belong to the sides of $S$, they are generated
by the generators of the sides. So we only need to add the remaining
generators of the inner polytope $P$ of $S$. Since $P$ is a dyadic triangle,
the minimal number of its generators may be found using the method described
in section 6.1. As we have seen in Example 4.1, it is sometimes possible to
find a smaller set of generators of a semitriangle. We will show that, as in
the case of triangles, each semitriangle is generated by the generators of its
maximal walls and generators of a two-dimensional simplex contained in it.

For any representative semitriangle $S$ in the plane $\mathbb{D}^{2}$, and any
point $E$ in the interior of $S$ which is a barycentric combination of the
three vertices of $S$, let $\mathbf{S}$ be a right two-dimensional simplex
contained in $S$ with shorter sides parallel to the axes intersecting at $E$.
The following lemma is a version of Lemma 3.3, formulated for semitriangles
instead of polytopes.

######  Lemma 6.6.

Let $S$ be a (representative) semitriangle. Then for any interior point $A\in
S$ there exist a point $B$ on a side of $S$, a right (geometric) simplex
$\mathbf{S}$ as described above, and a point $C$ in $\rm{int}(\mathbf{S})$,
such that $A$ belongs to the intersection $l(B,C)\cap S$ of $S$ and the (real)
line $l(B,C)$ through $B$ and $C$.

###### Proof.

First note that each side of $S$ is contained in a real line going through two
(dyadic) vertices of $S$. By the Density Lemma 3.2, for any two points of this
line there is a dyadic point located between them. We will show that such a
point may be located on the appropriate side of $S$. Without loss of
generality assume that a side $W$ of $S$ is contained in the (real) line $l$
given by an equation $y=ax$ for some dyadic number $a$, and going through the
vertices of $W$. Note that there is a positive odd number $m$ such that $l\cap
S=\\{(d,ad)\mid d\in m\mathbb{D}\\}$. Now if $R_{1}=(r,ar)$ and $R_{2}=(s,as)$
are any two distinct points of $l$ with $r<s$, then there are natural numbers
$k$ and $n$ such that $r<km/2^{n}<s$. So if the points $R_{1}$ and $R_{2}$ lie
between the vertices of $S$, then the point $B=(km/2^{n},akm/2^{n})$ belongs
to the side of $S$. Let $\mathbf{S}$ be a right two-dimensional simplex
contained in $S$ with shorter sides parallel to the axes, as described above,
and such that the real line $l(A,B)$ has a nonempty intersection with
$\mathrm{int}(\mathbf{S}_{r})$. By the Density Lemma, there is a point $C$ on
the line $l(A,B)$ located between any two (real) points of
$l(A,B)\cap\mathrm{int}(\mathbf{S}_{r})$. ∎

######  Corollary 6.7.

Each semitriangle is generated by the generators of the sides and two vertices
of a two-dimensional right simplex contained in the semitriangle.

Note that if $S$ is a (representative) semitriangle closing to a right
triangle $ABC$ with the interval $[A,C]$ as the side of $S$, then $S$ is
generated by the generators of the sides and only one additional generator of
a right simplex $\mathbf{S}$ with one of its shorter sides on the $x$-axis. We
have a similar situation if $S$ is a semitriangle closing to a hat triangle.

######  Example 6.8.

Consider the semitriangle $S$ closing the hat triangle of Example 6.4
consisting of the interior of the hat triangle, the whole interval joining
$(0,0)$ and $(6,0)$, the subgroupoid generated by $(0,0)$ and $(3,15)$, and
the subgroupoid generated by $(6,0)$ and $(3,15)$. Then $S$ is generated by
the three vertices and the points $(1,0)$ and $(1,1)$.

### Acknowledgement

The authors are grateful to anonymous referees for helpful comments on an
earlier version of this paper.

## References

  * [1] G. Bergman, On lattices of convex sets in $\mathbb{R}^{n}$, Algebra Unversalis 53 (1975) 357–395.
  * [2] A. Brøndsted, An Introduction to Convex Polytopes, Springer Verlag, New York, 1983.
  * [3] B. Csákány, Varieties of affine modules, Acta Sci. Math. 37 (1975) 3–10.
  * [4] G. Czédli, A. Romanowska, Generalized convexity and closure conditions, Int. J. of Algebra and Computation 23 (2013) 1805–1835.
  * [5] J. Ježek, T. Kepka, Free commutative idempotent abelian groupoids and quasigroups, Acta Univ. Carolin. Math. Phys. 17 (1976) 13–19.
  * [6] J. Ježek, T. Kepka, em Medial Groupoids, Academia, Praha, 1983.
  * [7] K. Matczak, A. Mućka, A. Romanowska, Duality for dyadic intervals, Int. J. of Algebra and Computation, 29 (2019) 41–60.
  * [8] K. Matczak, A. Mućka, A. Romanowska, Duality for dyadic triangles, Int. J. of Algebra and Computation, 29 (2019) 61–83.
  * [9] K. Matczak, A. Romanowska, Quasivarieties of cancellative commutative binary modes, Studia Logica 78 (2004) 321–335.
  * [10] K. Matczak, A. Romanowska, Irregular quasivarieties of commutative binary modes, Int. J. of Algebra and Computation 15 (2005) 699–715.
  * [11] K. Matczak, A. Romanowska, J.D.H. Smith, Dyadic polygons, Int. J. of Algebra and Computation 21 (2011) 387–408.
  * [12] A. Mućka, A. Romanowska, Duality for quasi-polytopes, Journ. of the Australian Math. Society 101 (2016), 95–117.
  * [13] W.D. Neumann, On the quasivariety of convex subsets of affine spaces, Arch. Math. 21 (1970), 11–16.
  * [14] K. Pszczoła, A. Romanowska, J.D.H. Smith, Duality for some free modes, Discuss. Math. Gen. Algebra Appl. 23 (2003), 45–62.
  * [15] A. Romanowska, Convex sets and barycentric algebras, in: Nonassociative mathematics and its applications, 243-–259, Contemp. Math. 721, Amer. Math. Soc., Providence, RI, 2019.
  * [16] A.B. Romanowska, J.D.H. Smith, Modal Theory, Heldermann Verlag, Berlin, 1985.
  * [17] A.B. Romanowska, J.D.H. Smith, Modes, World Scientific, Singapore, 2002.