# Democratic sequences

Anne Bertrand Mathis  Université de Poitiers (France)
<EMAIL_ADDRESS>Anne Bertrand Mathis  Université de
Poitiers (France<EMAIL_ADDRESS>
# Algorithmic construction of a sequence taking values in a coutable alphabet
with frequency preset.

Anne Bertrand Mathis  Université de Poitiers (France)
<EMAIL_ADDRESS>Anne Bertrand Mathis  Université de
Poitiers (France<EMAIL_ADDRESS>
###### Abstract

Let $A=\left\\{a_{n};n\geq 1\right\\}$ be an enumerable alphabet, and let
$\left\\{\lambda_{n};\thinspace n\geq 1\right\\}$ be a sequence of positive
numbers such that $\sum_{n\geq 1}\lambda_{n}=1.$ We explain an algorithmic
construction of a sequence $\left(u_{n}\right)_{n\geq 1}$ on the alphabet $A$
in which each letter $a_{k}$ appears with the frequency
$\lambda_{k}=\lambda\left(a_{k}\right).$

Etant donné un alphabet fini ou dénombrable $A=\left\\{a_{n};n\geq 1\right\\}$
et une famille $\left\\{\lambda_{n};n\geq 1\right\\}$ de nombres positifs de
somme $1$ nous construisons de façon simple une suite
$\left(u_{n}\right)_{n\geq 1}$ à valeurs dans $A$ dans laquelle chaque lettre
$a_{k}$ apparaît avec la fréquence $\lambda_{k}=\lambda\left(a_{k}\right)$.

Keywords: Distribution of sequences ; Numeration ; Combinatorics $\idotsint
sur$un alphabet denombrable dont chaque lettre a une frequence donnee ; Number
Theory

Classification AMS : 11K99

##  1 Presentation of the method.

Method: Let $A$ be a finite or countable alphabet and
$\left(\lambda\left(a\right)\right)_{a\in A}$ a family of positive numbers
with sum $1.$ We order the alphabet $A$:
$A=\left\\{a_{1},a_{2},...a_{p},...\right\\}$ so that if $h$ is less than $k$
then $\lambda\left(a_{h}\right)\leq\lambda\left(a_{k}\right)$ ; $p$ is called
the index of $a_{p}.$

We arbitrarily choose the start $u_{1}...u_{k}$ of the sequence
$\left(u_{n}\right)_{n\geq 1}$ that we want to construct. It can be a single
letter $u_{1}.$ Let us assume the first $M$ terms $u_{1},...,u_{M}$ already
constructed. We call $M-$frequency of a letter $a\in A$ the number
$\lambda_{M}\left(a\right)=\frac{1}{M}\sum_{u_{n}=a,n\leq M}1$. We call
$M-$deficit of $a$ the number
$D_{M}\left(a\right)=\lambda\left(a\right)-\lambda_{M}\left(a\right)$ when
positive. If it is strictly positive we say that $a$ is late at step $M$ and
if $D_{M}\left(a\right)>$$D_{M}\left(b\right)$ we say that at step $M$ $a$ is
more late than $b$.

If $\lambda\left(a\right)-\lambda_{M}\left(a\right)$ is negative we say that
$a$ is ahead in step $M$. We then call $M-$excess de $a$ at step $M$ the
strictly positive number

$E_{M}\left(a\right)=\mid\lambda\left(a\right)-\lambda_{M}\left(a\right)\mid=\lambda_{M}\left(a\right)-\lambda\left(a\right).$

Once $u_{1},...,u_{M}$ determined we choose for $u_{M+1}$ that of the letters
wich is the most late or, if several present the same delay, the one wich has
the lowest index (we can also choose at random one of the most late letters,
they are in finite numbers). If none of the letters are late we choose
$a_{1}.$

Théorème 1\. Let $A$ be a finite or countable alphabet,
$\left(\lambda\left(a\right)\right)_{a\in A}$ a family of positive numbers
with sum $1,$ and let $\left(u_{n}\right)_{n\geq 1}$ be a constructed sequence
accorded to the method above.

Then any letter $a$ of the alphabet $A$ appears in the sequence
$\left(u_{n}\right)_{n\geq 1}$ with the frequency $\lambda\left(a\right)$ :

$\forall a\in A,\ \
\lim_{N\rightarrow\infty}\frac{1}{N}\sum_{{}_{\begin{array}[]{c}n\leq N\\\
u_{n}=a\end{array}}}1=\lambda\left(a\right)\text{~~}(1).$

This method is inspired by the work of Ville $\left[3\right]$.

The alphabet does not required to be countable, the condition $\sum_{a\in
A}\left(\lambda\left(a\right)\right)=1$ implies that only a countable amount
of letters have a stricly positive frequency.

Furthermore we can also start the sequence $\left(u_{n}\right)_{n\geq 1}$ with
a Joker $J$ of zero frequency wich will only appears once and has frequency
zero, this is what we do if we want the first terms of the sequence
$\left(u_{n}\right)_{n\geq 1}$ are not chosen arbitrarily (this will be the
case in the study of numeration sequences).

The proof of the theorem is simple when the number of letters is finite but if
the letters are in countable quantity the situation becomes complicated. Let
us state some lemmas.

Lemma 1. $a)$ For any integer entier $M$ the sum of the deficits of the
letters of $A$ is equal to the sum of the excesses of the letters of $A$.

$b)$ If there exists a letter $b$ in advance with $E_{M}\left(b\right)$
strictly positive then there exists a late letter $a$ with
$D_{M}\left(a\right)$ strictly positive and vice versa.

$c)$ The algebraic sum of the deficits and excesses of the letters of $A$ is
equal to zero:

$\sum_{a\in A}D_{M}\left(a\right)-\sum_{a\in A}E_{M}\left(a\right)=\sum_{a\in
A}\lambda\left(a\right)-\lambda_{M}\left(a\right)=0.$

Proof of assertion $c)$. Immediate from the definitions of deficits and
excesses: in fact the numbers of occurrences of the letters of the alphabet
between the step $1$ and $M$ is equal to $M$ therefore $\sum_{a\in
A}\frac{\lambda_{M}\left(a\right)}{M}=1=\sum_{a\in
A}\left(\lambda\left(a\right)\right)$ and $\sum_{a\in
A}D_{M}\left(a\right)-\sum_{a\in A}E_{M}\left(a\right)=\sum_{a\in
A}(\lambda\left(a\right)-\lambda_{M}\left(a\right))=0.$

Let us call the upper frequency of a letter $b$ the number
$\overline{\lambda}\left(b\right)=\limsup_{N\rightarrow\infty}\frac{1}{N}\sum
1$ where the sum is taken on on the integers $n\leq N$ such that $u_{n}=b$. We
also define the lower frequency of a letter. If the sequence
$\left(u_{n}\right)_{n\geq 1}$constructed according to the method indicated
does not satisfy condition $\left(1\right)$ it is because there exists one or
more letters $b$ belonging to $A$ wich do not admit $\lambda\left(b\right)$
for frequency. Therefore there exists ar least one letter $b$ whose upper
frequency $\overline{\lambda}\left(b\right)$ is strictly greater than
$\lambda\left(b\right)$ or a letter $b$ whoses lower frequency is strictly
less than $\underline{\lambda}$$\left(b\right)$. As the number of letters in
infinite we are not very sure that the two cases occur simultaneously.

Remark: perhaps the assertions in lemma $1$should only be valid after a
certain rank due to the selection of the first terms.

Proposition 1. For any letter of the alphabet $A$,
$\overline{\lambda}\left(b\right)\leq\lambda\left(b\right)$

Suppose that there exists a letter $b$ wich satisfies
$\overline{\lambda}\left(b\right)>\lambda\left(b\right)$.

Let us then write
$\overline{\lambda}\left(b\right)=\lambda\left(b\right)+f_{b}$ with of course
$f_{b}>0$. There exists a non-empty subset $B$ of $\mathbb{N}$ such that the
frequency of $b$ when $N$ tends to infinity while remaining in $B$ is equal to
$\overline{\lambda}\left(b\right)$ and we can find an integer $N_{0}$ such
that:

$\forall N>N_{0},N\in B,\ \
\lim_{N\rightarrow\infty}\frac{1}{N}\sum_{{}_{\begin{array}[]{c}n\leq N\\\
u_{n}=b\end{array}}}1>\bar{\lambda}\left(b\right)-\frac{f_{b}}{2}=\lambda\left(b\right)+\frac{f_{b}}{2}\text{~~}(2).$

As $b$ appears an infinite number of times in the sequence
$\left(u_{n}\right)_{n\geq 1}$ there exists an integer $n_{0}$ verifying
$\frac{1}{n_{0}-1}<\frac{f_{b}}{4}$ such that $u_{n_{0}}=b.$

Let $M>\max\left(N_{o},n_{0}\right)$ be an integer belonging to $B$. We
therefore have, according to $\left(2\right)$,

$\frac{1}{M}\sum_{{}_{\begin{array}[]{c}n\leq M\\\
u_{n}=b\end{array}}}1>\lambda\left(b\right)+\frac{f_{b}}{2}\text{~~}.$

Let’s go back to the las index $m$ less than or equal to M  such that
$u_{m}=b.$ This index $m$ is greater than or equal to $n_{0}.$ The number of
occurences of $b$ among the fist $m$ letters of the sequence
$\left(u_{n}\right)_{n\geq 1}$ is equal to the number of occurrences of $b$
among the first $M$ letters. As more $\frac{M}{m}$ is greater or equal to $1$
it comes:

$\frac{1}{m}\sum_{{}_{\begin{array}[]{c}n\leq m\\\
u_{n}=b\end{array}}}1=\text{~~}\frac{1}{m}\sum_{{}_{\begin{array}[]{c}u_{n}=b\\\
n\leq
M\end{array}}}1=\frac{M}{m}\left(\frac{1}{M}\sum_{{}_{\begin{array}[]{c}n\leq
M\\\
u_{n}=b\end{array}}}1\text{~~}\right)>\lambda\left(b\right)+\frac{f_{b}}{2}\text{~~}\text{~~}$

Let’s look at what happens at step $m-1.$ Let us show that at this step $b$
was already in advance. The number of occurrences of $b$ when $n\leq m-1$ is
equal to the number of occurrences of $b$ betweens steps $1$ and $m$, minus
$1$. Therefore

$\frac{1}{m-1}\sum_{{}_{\begin{array}[]{c}n\leq m-1\\\
u_{n}=b\end{array}}}1=\frac{1}{m-1}\left(\left(\sum_{{}_{\begin{array}[]{c}n\leq
m\\\
u_{n}=b\end{array}}}1\right)-1\right)\geq\frac{1}{m}\left(\sum_{{}_{\begin{array}[]{c}n\leq
m\\\ u_{n}=b\end{array}}}1\right)-\frac{1}{m-1}\geq$

$\geq\lambda\left(b\right)+\frac{f_{b}}{2}-\frac{1}{m-1}.$

As $m$ is greater than or equal to $n_{0}+1,$ $\frac{1}{m-1}$ is smaller than
$\frac{f}{4}$ and at the step $m-1$ the letter $b$ admits an excess of at
least $\frac{f_{b}}{2}-\frac{f_{b}}{4}$$=\frac{f_{b}}{4}$.

The sum of deficits ans excesses being zero at each step according to Lemma
$1,$ it exists at step $m-1$ a letter $a$ such that $D_{m-1}\left(a\right)$ is
strictly positive. So the letter $b$ could not be chosen at this step, this it
impossible so no letter can have an upper density
$\overline{\lambda}\left(b\right)$ greater than
$\lambda\left(b\right)$$\boxempty$.

It remains to show that no letter admits a lower frequency strictly lower than
its assigned frequency.

Proposition 2 All letter of the alphabet appears at least once in the sequence
$\left(u_{n}\right)_{n\geq 1}.$

We will assume in the following that the letters of the alphabet are ordered
by decreasing frequency:
$i<j\Rightarrow\lambda\left(a_{i}\right)\leq\lambda\left(a_{j}\right)$.

Lemma 2. The deficit at step $M$ of a letter $a$ is always strictly smaller
than $\lambda\left(a\right).$ Therefore the sum of the deficits of all the
letters is at most $1.$

Proof of lemma $2$. At step $M$ the deficit $D_{M}\left(a\right)$ of the
letter $a$ is equal to $\lambda\left(a\right)-\lambda_{M}\left(a\right)$ when
his term is positive; as $\lambda_{M}\left(a\right)$ is always positive or
zero, this term is therefore always less than or equal to
$\lambda\left(a\right)$ and so the sum of the deficit is at most $1.$

Lemme 3. Suppose that at a step $M$ the deficit of the letter $b$ is greater
or equal to $g$ ; then no letter $a$ with $\lambda\left(a\right)<g$ can
proceed to this step $M$.

Prof of lemma $3$. According to lemma $2$ the deficit of $a$ would then be
less than or equal to $\lambda\left(a\right),$ wich is strictly less than the
deficit of $b$, $a$ cannot pass.

Proof of Proposition $2.$

Suppose there is a letter $a_{i}$ wich never pass. It is this letter that we
will consider. It is assumed that
$\lambda\left(a_{1}\right)\geq\lambda\left(a_{2}\right)\geq...\geq\lambda\left(a_{i}\right)\geq\lambda\left(a_{i+1}\right)....$.
.

Suppose that if several letters admit the same frequency as $a_{i}$ their
indices are $i-k,...i-1,i$. None of the letters $a_{j}$ such that
$\lambda\left(a_{j}\right)<\lambda\left(a_{i}\right)$ can pass, therefore none
of the letters $a_{i+1},a_{i+2},...$ will pass because
$\lambda\left(a_{i+1}\right)<\lambda\left(a_{i}\right)$ and so tight now.
Therefore all their excess are equal to zero and their deficits are all
strictly lower than their assigned frequency according to Lemma $2$.

Let $N_{0}$ be such that if $N\geq N_{0}$ the sum of the excesses of the
letters $a_{1},a_{2},...,a_{i-k},...a_{i}$ is less than
$\frac{1}{4}\lambda\left(a_{i}\right)$. These letters are finite in number so
proposition $1$ ensures the existence of $N_{0}$.

Lemma $1a$ show that as long as $a_{i},a_{i+1}...$ have never passed the sum
of the excess of letters $a_{1},a_{2},...,a_{i-k},...,a_{i-1}$ is equal to the
sum of their deficits increased by the sum of the deficits of the letters
$a_{i+1},a_{i+2},...$ . The sum of these deficits is therefore less than
$\frac{1}{4}\lambda\left(a_{i}\right)$, so after step $N_{0}$ the deficits of
the letters $a_{1},a_{2},...,a_{i-k},...,a_{i-1}$ cannot be greater than
$\frac{1}{4}\lambda\left(a_{i}\right)$.

For $N>N_{0}$ the sum of excesses is less than
$\frac{1}{4}\lambda\left(a_{i}\right)$, so no letter can have a deficit
greater than $\frac{1}{4}\lambda\left(a_{i}\right)$ at step $N.$ But if
$a_{i}$ never pass his deficit tend to $\lambda\left(a_{i}\right)$ as $N$ goes
to infinity. This is impossible so $a_{i}$ appears in the sequence.

The following lemma is obvious:

Lemma $4$ Whe the letter $a_{i}$ passes for the first time to stage $N_{i}$
all the other letters have a deficit less or equal to
$\lambda\left(a_{i}\right).$

Proposition $3.$ No letter $a$ can admit a lower frequency strictly smaller
than its assigned frequency : $\forall a\in A$,
$\underline{\lambda}\left(a\right)$ $\geq\lambda\left(a\right).$

Lemma $5$. For any integer $M$ and any letter $b,$ $\mid
D_{M+1}\left(b\right)-D_{M}\left(b\right)\mid\leq\frac{1}{M+1}$ each time
these two quantities are defined.

Proof of lemma $5$. When we add a $b$ to step $M$ the deficit of $b$ decreases
of $\frac{(number\thinspace of\thinspace b\thinspace between\thinspace
1\thinspace and\thinspace M)+1}{M+1}-\frac{number\thinspace of\thinspace
b\thinspace beyween\thinspace 1\thinspace and\thinspace
M}{M}=\frac{M-number\thinspace of\thinspace b\thinspace between\thinspace
1\thinspace and\thinspace M}{M(M+1)}$ wich is smaller than $\frac{1}{M+1}$.
When we add a letter different from $b$ the variation of the deficit is less
than $\frac{number\leavevmode\nobreak\ of\leavevmode\nobreak\
b}{M}-\frac{number\leavevmode\nobreak\ of\leavevmode\nobreak\
b}{M+1}=\frac{number\leavevmode\nobreak\ of\leavevmode\nobreak\ b}{M(M+1)}$
who is also less than $\frac{1}{M+1}$.

Proof of proposition $3$. Let $B$ be the set of numbers $\gamma$ de
$\left]0,1\right]$ such that there exists $a_{\gamma}$ whose lower frequency
is strictly lower than $\lambda\left(a_{\gamma}\right)$ :
$\underline{\lambda}\left(a_{\gamma}\right)$
$=\lambda\left(a_{\gamma}\right)-\gamma$. As the sum of the frequencies is
equal to $1$, the number of letters whose frequency exceed a fixed number $d$
is finite and $B$ cannot admit an accumulation point except perhaps zero $0$ :
if $B$ is non-empty $B$ admits a maximum element $c$ so there exist at least
one letter $a_{c}$ such that $\underline{\lambda}\left(a_{c}\right)$
$=\lambda\left(a_{c}\right)-c$ and perhaps a finite number of such letters.

Suppose there is only one letter, $a_{c}$, such that
$\underline{\lambda}(a_{c})$$=\lambda\left(a_{c}\right)-c$. Let $P$ be the
(finite) set of letters $a$ such that
$\lambda\left(a\right)-$$\underline{\lambda}(a)$$\in\left]0,c\right[$ and let
$b$ be the maximum of the quantities $\underline{\lambda}(a)$ for $a\in P$. So
$b<c$. Let $Q$ be the set of letters whose frequency is greater or equal to
$b$ and such that $\underline{\lambda}(a)=\lambda\left(a\right)$(and is also
equal to $\bar{\lambda}(a)$, see Proposition $1$); Q is finite because the sum
of the frequencies is $1.$

There exists an integer $N_{0}$ such that for all $N>N_{0}$, for any letter
$w$ in $P\cup Q,$ the deficit $D_{N}\left(w\right)$ of the letter $w$ is less
than $b+\frac{c-b}{2}$, those of $P$ because their defects have an upper limit
at most $b$ and those of the finite set $Q$ because if $N$ is large enough
they are closed of their assigned frequency
($\underline{\lambda}(a)=\lambda\left(a\right)=\bar{\lambda}(a)$ if $a\in Q$
and $Q$ is finite, use proposition $1$).

Let us place ourselve at a step $N_{i}$ with $N_{i}>N_{0}$ where the letter
$a_{i}$ with $\lambda\left(a_{i}\right)<\frac{b}{2}$ passes for the first
time, and such that the deficit of $a_{c}$ exceed the value $c-\frac{c-b}{20}$
at a step between steps $N_{i}$ et $N_{i+1}$ (such $N_{i}$ exist because the
sequence $N_{i}$ tends toward infinity). The letter $a_{c}$ admits at step
$N_{i}$ a deficit lower than $\frac{b}{2}$ accrding to lemma $4$.The deficit
of $a_{c}$ must therefore increase between $N_{i}$ et $N_{i+1},$ very
gradually due to lemme $5$.

Suppose that at step $M\in\left[N_{i},N_{i+1}\right]$ the deficit of $a_{c}$
is between $c-\frac{c-b}{10}$ and $c-\frac{c-b}{20}$ ; then the letter $a_{c}$
must pass because no other lette has a greater deficit (lemma $3)$, and it
passes until the deficit of $a_{c},$ wich decrease, returns under
$c-\frac{c-b}{20}$ ; this deficit will therefore never be able to rise to
exceed $c-\frac{c-b}{20}$. So the hypothesis is impossible, there cannot be a
single letter such that the deficit of this letter $a_{c}$ admits upper limit
$c$; so the letter $a_{c}$ cannot have a lower frequency
$\underline{\lambda}\left(a_{c}\right)$ $=\lambda\left(a_{c}\right)-c$.

Now look at the case where the maximum $c$ of
$\lambda\left(a\right)-\underline{\lambda}\left(a\right)$ is reached for
several letters, and where all the deficits of the other letters are smaller
than a common value $b<c$. The sets $B,$$P,$$Q$ and the numbers $b<$ $c$ are
defined as above and let $R$ designates the finite set of letters $a$ of the
alphabet such that $\underline{\lambda}\left(a\right)=\lambda\left(a\right)-c$
of $R$.

We also choose for $N_{i}$ an integer as lardge as necessary wich represents
the first passage of a letter $a_{i}$ of assigned frequency less than the
common value $b$ and such that at least one of the letters of $R$ such that
$\underline{\lambda}\left(a\right)=\lambda\left(a\right)-c$ has a deficit
exceeding $c-\frac{c-b}{20}$ at a step between steps $N_{i}$ and
$N_{i+1}$(such $N_{i}$ must exist). Letters of $P$ and $Q$ always have
deficits less than $b+\frac{c-b}{2}$ for all $N>N_{i}$. At least one of the
letters of $R$, say $w,$ see his deficit starting from very low ( lemma $4$)
and slowly rising to $c-\frac{c-b}{20}$; it passes if no letter has a greater
deficit. The only letters wich can have a greater deficit are those of $R$,
with $\underline{\lambda}\left(a\right)=\lambda\left(a\right)-c$ so
$\lambda\left(a\right)>c$ and are in number $k$ such that $\sum_{a\in
R}\lambda\left(a\right)<1$ and then $kc<1$. If one letter of $R$ passes his
deficit decreases and the deficits of the others letters of $R$ increase (see
the proof of lemma $5$); when a letter pass his defect decreases of $\nu$ and
the sum of the other deficits increases but increases less than $\nu$ (because
all the excesses decrease and the lemma $1$ ). As long as this phenomen lasts,
no letter acquires excess and all letters in excess see their excess diminish;
as the sum of excesses is equal to the sum of deficits, the sum of deficits
decreases. No letter can see his deficit decrease much because this cause
other letters to pass and this deficit decreases a little each time. The
existence of such $N_{i}$ is impossible and no letter can verify
$\underline{\lambda}(a)=\lambda\left(a\right)-c$ if $c$ is the maximum
conceivable value. But in fact it means that no letter cans verify
$\underline{\lambda}(a)<\lambda\left(a\right)$. The theorem is proved.

##  2 Examples and applications.

###  2.1 Approximation of measures on the torus $\mathbb{R}/\mathbb{Z}$ by
measures associated with sequences $(\beta^{n})_{n\geq 1}$ modulo one.

Here we shall use only finite alphabets in theorem 1, but the consequences
(the very lardge variety of measures on the torus $\mathbb{R}/\mathbb{Z}$
associated with the exponential sequences $\left\\{\beta^{n}\right\\}_{n\geq
1}$ when $\beta$ travels$\left]1,\infty\right[$) is interesting.

Given a real number $x,$ let $\left\\{x\right\\}$ denotes his fractional part
and $\delta_{y}$ denotes the Dirac measure at point $y$.

A sequence $\left(u_{n}\right)_{n\geq 1}$ of reals numbers is said to be
distributed according to the probability measure $\nu$ on the torus if the
sequence of measures
$\nu_{N}=\frac{1}{N}\left(\delta_{\left\\{u_{1}\right\\}}+...+\delta_{\left\\{u_{N}\right\\}}\right)$
weakly converge toward $\nu.$ In general a sequences does not admit a
distribution measure but there always exists a set of measures that we call be
associated with this sequence: we say that the measure $\gamma$ is associated
with the sequence $\left(u_{n}\right)_{n\geq 1}$ if it exists an infinite
subset $B$ of $\mathbb{N}$ such that
$\gamma=\lim_{\begin{array}[]{c}N\rightarrow\infty\\\ N\in
B\end{array}}\frac{1}{N}\left(\delta_{\left\\{u_{1}\right\\}}+...+\delta_{\left\\{u_{n}\right\\}}\right).$

Théorem 2. Let $\mu$ be a probability measure on the torus. then there exists
a sequences of real numbers $\left\\{\beta_{k}\right\\}_{k\geq 1}$and for all
$k$ a measure $\mu_{k}$ associated with the sequence
$\left(\left\\{\beta_{k}^{n}\right\\}\right)_{n\geq 1}$ such that $\mu$ is the
weak limit of the sequence of measures $\mu_{k}$.

In other words the set of associated measure of sequences
$\left(\left\\{\beta^{n}\right\\}\right)_{n\geq 1}$is dense in the set of
probabilities measures on the torus (in the sense of weak convergence).

Remark: For almost all $\beta>1$ the sequence $(\beta)_{n>0}^{n}$ is uniformly
distributed modulo one. The incriminated $\beta_{k}$ are generally part of the
exceptional set.

Proof : We will use the following idea:

Proposition 4 $\left[1\right]$ Given a sequence $\left(I_{m}\right)_{m\geq 1}$
of closed intervals $I_{m}$ of the of the torus $\mathbb{R}/\mathbb{Z}$ , of
the same length (or of length gteater than a positive number $c$), there
exists a real number $\beta$ such that for all $m\geq 1$, $\beta^{m}$ belongs
to $I_{m}.$

Proof of the Theorem. Let us fix a measure $\mu$ on the torus; if she has
atoms let $(y_{n})_{n\geq 1}$ be these atoms; they are finite or countably in
number.

Fix an integer $k,$then let us divide the torus into a finite numbers of
intervals $I_{1}^{k},I_{2}^{k},...,I_{p_{k}}^{k}$whose union is the entire
torus and whose possible intersections two by two are reduced at their ends.
We choose their lengths greater than a number $c_{k}>0$ and such that no atom
$y_{i}$, if any, is one of the ends of the intervals. For any integer $i$ less
than or equal to $p_{k}$ we set
$\lambda^{k}\left(i\right)=\mu\left(I_{i}^{k}\right).$ The choice of the
$(I_{i}^{k})_{i=1,...,p_{k}}$ guarantees that the sum of the
$\lambda^{k}\left(i\right)$ is equal to$1$.

Still for this fixed $k$ apply the theorem $1$ to the alphabet
$I_{1}^{k},I_{2}^{k},...,I_{p_{k}}^{k}$, assigning to $I_{i}^{k}$ the
frequence $\lambda^{k}\left(i\right)=\mu\left(I_{i}^{k}\right)$; construct
with the Theorem $1$ a sequence of intervals $(u_{n}^{k})_{n\geq 1}$where
$u_{n}^{k}$ is an interval belonging to the alphabet
$I_{1}^{k},I_{2}^{k},...I_{p_{k}}^{k}$;$u_{n}^{k}$ take the value $I_{i}^{k}$
with the frequence $\lambda^{k}\left(i\right)$.

According to the proposition $4$ there exists a real number $\beta_{k}$ such
that, for all $n,$ $\left\\{\beta_{k}^{n}\right\\}$ falls in the interval
$u_{n}^{k}$. The sequence $(\left\\{\beta_{k}^{n}\right\\})_{n\geqslant 1}$
does not always admit a distribution measure but she always has an associated
measure $\nu_{k}$; as $(u_{n})=I_{i}^{k}$ with the frequency
$\lambda^{k}\left(i\right)=\mu\left(i\right)$, for all interval
$I_{1}^{k},I_{2}^{k},...,I_{p_{k}}^{k}$,
$\nu_{k}\left(I_{i}^{k}\right)=\mu\left(I_{i}^{k}\right)$ (recall that the
intervals $I_{1}^{k},I_{2}^{k},...I_{p_{k}}^{k}$ are disjoints relatively to
the measure $\mu$).

Let us increase $k$ and choose the $I_{1}^{k},I_{2}^{k},...I_{p_{k}}^{k}$ so
that the limit of the $\sigma-$algebra generated by the set
$\left\\{I_{1}^{k},I_{2}^{k},...,I_{p_{k}}^{k}\right\\}$give rise to the
Borelians of the torus, it then comes that
$\lim_{k\rightarrow\infty}\nu_{k}=\mu$.

###  2.2 Numeration.

Let $\beta$ be an integer; we shall take $\beta=10$ but $\beta$ could be any
integer. Let $(u_{n})_{n\geq 1}$ be a sequence wich begins with a Joker
$u_{1}=J$ ($J$ is a symbol wich is only encoutered there, it correspond to
zero: no digit has yet grow but zero is part of the sequence of numeration in
base $10).$ Then we look at the sequence of expansions of the integers in base
$10$ and we write $u_{N}=a_{i}$ if to go from $N-1$ to $N$ we increase of $1$
the $i-th$ digit starting from the right (that of the $10^{i-1}$) or we make
it appears if there was none $10^{i-1}$ before (and all the digits on the
right of the $(i-1)th$ digit goes to zero).The beginning of the sequence is

$u_{1}u_{2}u_{3}u_{4}u_{5}u_{6}u_{7}u_{8}u_{9}u_{10}u_{11}u_{12}u_{13}u_{14}u_{15}u_{16}u_{17}u_{18}u_{19}u_{20}u_{21}u_{22}...u_{101}...u_{111}u_{112}u_{113}...$$=Ja_{1}a_{1}a_{1}a_{1}a_{1}a_{1}a_{1}a_{1}a_{1}a_{2}a_{1}a_{1}a_{1}a_{1}a_{1}a_{1}a_{1}a_{1}a_{1}a_{2}a_{1}...a_{3}a_{1}a_{1}a_{1}a_{1}a_{1}a_{1}a_{1}a_{1}a_{1}a_{2}a_{1}a_{1}...$

We obtain the same sequence by constructing the democratic sequence starting
with a Joker (step $1)$ and such that the democratic process begin at step $2$
with the alphabet $\left(a_{n}\right)_{n\geqslant 1}$with frequency
$\frac{9}{10}$ for the symbol $a_{1}$, $(\frac{9}{10})\frac{1}{10}$ for
$a_{2}$, $(\frac{9}{10})\frac{1}{10^{2}}$ for $a_{3}$,…
$(\frac{9}{10})\frac{1}{10^{n-1}}$for $a_{n}$ and so on; the $n$\- th digit
appears $10$ time less than the$(n-1)$th.

This is also an automatic sequence: let $(a_{n})n\geq 1$ an alphabet, let
$\sigma$ be the morphism $a_{1}\rightarrow a_{1}...a_{1}a_{2}$ ,
$a_{2}\rightarrow a_{1}...a_{1}a_{3},$ and more generally $a_{n}\rightarrow
a_{1}...a_{1}a_{n+1}$ (nine $a_{1}$ at each time). Let
$\left(u_{n}\right)_{\geq 1}$ be the fix point of the substitution $\sigma$
starting with $a_{1}$ and let $a_{i}$ represent “the $i$\- th digit is growing
at step $n$ if and only if $u_{n}=a_{i}$. The democratic sequence is equal to
the sequence beginning with the Joker followed by the fixed point.

Proposition 4. Let $A=(a_{1},a_{2}....a_{n}...)$ an enumerable alphabet, and
let
$\frac{1}{k}(1-\frac{1}{k}),$$\frac{1}{k^{2}}(1-\frac{1}{k})$,…$\frac{1}{k^{n}}(1-\frac{1}{k})$,…a
sequence of numbers with sum $1.$ Let $\left(u_{n}\right)_{n\geq 1}$be the
associated democratic sequence beginning by a Joker. If $u_{n}=i,$ the $i-th$
digit is growing at the step $n.$

You can easily check it in the case where $\beta$ is an integer; we conjecture
it for all $\beta>1$ (see $\left[2\right]$ for numeration in non integer
base).

In the case where this would be true for all $\beta>1,$ maybe it would help to
prove another conjecture: does the $\beta-$shift is the symbolic system with
entropy $log\beta$ having the minimum of $n-$words? (this is true for
$\beta\in\mathbb{N}$ ).

There is also an inteesting problem : is the convergence toward the right
frequencies fast? That might have an impact on the previous question.

Bibliographie

$\left[1\right]$A. Bertrand Mathis. Sur les parties fractionnaires des suites
$(\beta^{n})_{n\geq 1}$, Uniform Distribution Theory 14 n°2 (2019),69 -72.

$\left[2\right]$A. Bertrand-Mathis. Comment écrire les nombres entiers dans
une base qui n’est pas entière. Acta Math.Hungar. 54( 1989) n°3-4 237-241.

$\left[3\right]$J.A. Ville. Etude critique de la notion de collectif, Thèse,
Faculté des Sciences de Paris, 1939.


# Regex in a Time of Deep Learning: The Role of an Old Technology in Age
Discrimination Detection in Job Advertisements

Anna Pillar1,2, Kyrill Poelmans2, Martha Larson1
1Radboud University, Netherlands
2Textmetrics, Netherlands
<EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS>
###### Abstract

Deep learning holds great promise for detecting discriminatory language in the
public sphere. However, for the detection of illegal age discrimination in job
advertisements, regex approaches are still strong performers. In this paper,
we investigate job advertisements in the Netherlands. We present a qualitative
analysis of the benefits of the ‘old’ approach based on regexes and
investigate how neural embeddings could address its limitations.

##  1 Introduction

Age discrimination is often related to work and it starts in the pre-hiring
phase with job advertisements. Each year, thousands of job descriptions in the
Netherlands contain age discrimination, which is illegal under Dutch law
Fokkens et al. (2018).

The state of the art in detection of illegal age discrimination in Dutch job
ads uses regular expressions (regex) Fokkens et al. (2018). This ‘old’
approach works surprisingly well because illegal age discrimination uses
predictable vocabulary, and keywords such as ‘age’ are quite reliable
indicators. However, individual sentences from job ads suggest that neural
embedding approaches, with their ability to capture semantics, could also be
helpful, e.g., ‘Given our own advancing years, it would be just lovely to have
a younger soul join us.’

The contribution of this paper is a qualitative analysis of the role that
regex should continue to play in detecting illegal age discrimination, now
that the language technology community has moved towards deep learning
approaches. Since regexes offer explainable decisions, we do not seek to
abandon the regex approach, but rather to understand its potential compared
with the potential of neural embeddings. Because it is known that the regex
approach can suffer from low recall Fokkens et al. (2018), our main focus is
on understanding false positives (i.e., cases of discrimination that the
detector misses).

In this paper, we report the essential findings on illegal age discrimination
detection in Dutch job ads of a larger study Pillar (2022), which contains
further analysis. After a brief introduction to age discrimination (Sec. 2)
and the regex approach of Fokkens et al. (2018) (Sec. 3), we present two
analyses. The first (Sec. 4) investigates the regex approach, which is
currently the state of the art. The second (Sec. 5) looks at whether and how
neural embeddings could complement regexes in the future.

Our analyses make use of the Job Digger dataset, which contains 1.2 million
Dutch job advertisements collected by a Dutch company, Job Digger, and made
available to us for use in our study. Job Digger had created the dataset by
carrying out a large scale crawl of internet job postings in the Netherlands
in 2014. The comprehensiveness of this crawl ensures that our dataset is
representative of the full spectrum of possible Dutch job ads.

Our investigation reveals that the regex approach is more difficult to improve
upon than one might think. The final section of the paper (Sec. 6) provides an
outlook and discusses how researchers in the future should seek to leverage
both regexes and neural embeddings for explainable detection of illegal age
discrimination.

##  2 Background and Related Work

Age discrimination is defined as bias and prejudice against people based on
their age and ageism is one of the three big ‘isms’, next to sexism and racism
Butler (1969). In practice, age discrimination predominantly targets older
people Bytheway (2005). Ageism is in this sense unique among ‘isms’ because,
in the natural course of life, in-group members become out-group members
Jönson (2013). However, despite the fact that it threatens everyone, ageism is
difficult to fight. It is culturally acceptable Gendron et al. (2016) and
people are unaware of it (Palmore, 2001). In the Netherlands, concern about
age discrimination has grown recently, mainly in employment Andriessen et al.
(2014).

Age discrimination occurs in two main forms (Voss et al., 2018). _Objective
Ageism_ is defined through legal frameworks that protect the vulnerable group
from discrimination. _Subjective Ageism_ (or _Perceived Ageism_) is bias and
discrimination that does not fall under a legal definition.

In the Netherlands, the Dutch Equal Treatment Act regarding age discrimination
at the workplace prohibits discrimination in the context of work, including
job advertisements. The law defines two forms of discrimination: Direct
discrimination involves an explicit mention of the age of the candidate, e.g.,
‘You are younger than 30 years’. Indirect discrimination, involves
formulations that imply age, e.g., specifically recruit students (who, in the
Netherlands, characteristically are young).

The literature on age discrimination detection in job ads is surprisingly
limited. The work closest to ours studied the relationship between stereotypes
in English-language job ads and in hiring Burn et al. (2019). It implemented
an age discrimination detector for job ads, but focused on stereotypes, which
are not necessarily illegal. In contrast, we study detection of discriminatory
statements that are explicitly defined, and prohibited, by law.

##  3 Regex Baseline

The state of the art in the detection of age discrimination in Dutch job ads
Fokkens et al. (2018) uses a list of keywords to detect objective ageism. The
keywords were identified by manually reading a large number of job ads. They
were selected because they were judged to be indicative of illegal
discrimination when used in certain contexts.

Appendix A contains the keyword list with a sample sentence from a job ad for
each keyword. The keywords form the basis of a set of regular expressions,
which Fokkens et al. (2018) constructed with the aim of covering all possible
contexts in which each keyword could be discriminatory. The importance of
context is illustrated by the following example. The sentences, ‘You will be
responsible for young students’ contains both the words ‘young’ and ‘student’,
but is not discriminatory because the words describe the job and not the
candidate. Fokkens et al. (2018) published a set of these regexes on
GitHub111https://github.com/cltl/AgeDiscriminationBaseline. They discovered
that regexes perform best if they allow a certain amount of flexibility by
including the white card character .{0,30}, e.g.,
‘you\s+are\s+a\s+.{0,30}student’. They report that such flexible regexes
achieve a high precision (94.5%), but a somewhat low recall (75.7%) on their
test set.

##  4 Role of the Regex Baseline

In this section, we discuss our first qualitative analysis, which aimed to
reveal both the potential and the inherent weaknesses of the regex approach.

###  4.1 Data and Annotation

We created a representative dataset large enough to yield interesting insights
but small enough to be hand annotated by sampling ca. 3,000 sentences from the
Job Digger dataset. About half of the sentences we sampled were selected to
contain one keyword, but to not match any regexes. The inclusion of a large
number of these sentences improved the chance that we could gain insight into
how the inherent weaknesses of regexes might contribute to false positives. We
consider a weakness ‘inherent’ if it relates to expressiveness or
generalizabilty of the regexes themselves, rather than to the exact keywords
we are using. As much as possible, we sampled evenly over the keywords. About
a third of our sample sentences were chosen to match a regex. The samples in
the remaining ca. 10% of the dataset did not include a keyword.

The data set was annotated for age discrimination by a group of seven
annotators with good familiarity with Dutch law, who were split into two
teams. Each sample was annotated by two annotators, one from each team. The
inter-annotator agreement (Cohen’s Kappa) between teams reflected substantial
agreement ($\kappa=0.61$). Samples on which the annotators disagreed or where
one was unsure were not included in our dataset, leaving a total of 2,195
annotated samples for analysis.

###  4.2 Approach and Findings

We conducted our analysis by inspecting sample sentences by hand and
investigating two levels: (1) at a general level across all keywords (2) at a
keyword level, focused on the false negatives associated with each keyword. We
report our findings organized into a set of insights:

General sentence length and structure Across the keywords, we found variation
in sentence length and structural complexity, from bullet points such as ‘-
Age up to 27 years’ to verbose sentences such as ‘We are looking for man and
especially also for women, who know the shop floor inside out, and are between
50 and 70 years of age.’ The regexes in our list were too elaborate to capture
the bullets and too narrow to capture the verbose sentences. This observation
points to an inherent limitation of regexes. Our analysis also revealed a
certain number of frequent formulation for which a regex missing keywords or a
missing formulation could easily be added.

Keyword-specific issues When looking at the sample sentences of individual
keywords we found that the issue of sentence length and structure occurred
across keywords, but was a particular issue for certain keywords,
specifically, ‘young’ (jong) and ‘age’ (leeftijd). This observation suggests
that not all keywords should be handled the same.

Keyword context At the keyword level, we found that for ‘young’ (jong) and
‘recent graduate’ (schoolverlater), the discrimination is determined by the
context in which they are used. As mentioned above, if these keywords are used
to describe the job and not the candidate, they are not discriminatory. We
found that the formulations used were very open. There seemed to be no
frequent formulation that could be added to the regexes to cover the variety
of the samples in which the context was not captured by the regexes, causing a
false negative.

Keywords associated with discrimination We observed that some keywords seem to
be associated with discrimination, but did not themselves directly express
discrimination. For example, the keyword ‘extra money’ (bijverdienen) as used
in the sentence ‘Have you recently completed your degree and would like to
earn a earn a little extra money?’ is not causing the sentence to be
discriminatory. Rather, the reference to ‘recent graduation’ makes the
sentence discriminatory. This observation suggests that better modeling of
context can improve the performance of regexes.

Limited non-discriminatory usage Certain keywords, such as, e.g., ‘recent
graduate’, just discussed, mainly occur in discriminatory sentences. However,
in 3 out of 114 samples with the keyword ‘recent graduate’, it was actually
used in a non-discriminatory way. This observation suggests that regexes
should be designed to capture the non-discriminatory contexts. If a sentence
containing a keyword does not match a ‘non-discriminatory regex’ then it can
be considered discriminatory.

##  5 Role of Neural Embeddings

In this section, we discuss our second qualitative analysis, which aimed to
discover how neural embeddings can potentially complement regex.

Since the issue of missing keywords was already raised by Fokkens et al.
(2018), we focus on another property of regexes that Sec. 4 revealed to be an
issue for detection of illegal age discrimination: they cannot capture
discrimination when it is phrased using different syntax but expresses similar
semantics. This inflexibility becomes particularly important when we consider
the importance of modeling the broader context of a keyword within a sentence.

###  5.1 Approach and findings

Our analysis consisted of manual inspection of a large number of sentence
embedding clusters. We trained ALBERT word embeddings Lan et al. (2020) on 5
million sentences drawn from the Job Digger dataset. The training was done
from scratch with the MLM learning task. To create sentence embeddings, we
averaged the word embeddings of the component words, following common
practice.

Our hope was that in the sentence embedding space, we would observe a
separation between discriminatory and non-discriminatory sentences, since
these express different semantics. However, when we visualized our samples
using t-SNE Van Der Maaten and Hinton (2008), we did not observe clear
discriminating and non-discriminatory clusters. We concluded that a standardly
trained semantic space cannot easily capture age discrimination and turned to
analyze if neural embeddings could capture useful differences in keyword
context.

Figure 1: An excerpt of the plot of the embeddings of sentences containing the
keyword ‘between’. Orange: discriminatory, Blue: non-discriminatory

For each keyword, we selected the sentences in our annotated data set that
contained it and visualized them with t-SNE. In most cases, the discriminatory
and non-discriminatory sentences were not well separated. However, there were
a few cases that are worth further discussion222Full interactive plots for all
keywords can be found at https://github.com/Textmetricslab/Regex-in-a-Time-of-
Deep-Learning.

Keyword ‘between’ Good separation was observed for the keyword ‘between’, as
can be seen in Fig. 1. The discriminatory sentences include: ‘You are
preferably aged between 17 and 20 years.’ and ‘Are you the person we are
looking for and are you are aged between 16 and 19 years?’ The cluster in the
lower part of the plot consists of samples that use the word ‘between’ to give
information about the work time and are not discriminatory: ‘You will be
working between 10 and 25 hours per week, from Monday to Sunday’ and ‘Total
work time per week is between 8 and 12 hours’.

It is interesting to note that all discriminatory samples contain a number
followed by the word ‘age’ and non-discriminatory samples contain a number
followed by either ‘hour’ or its abbreviation. This means that in this case,
regexes could have also distinguished these two contexts.

Keyword ‘experience’ Another interesting example was the keyword ‘experience’,
which is discriminatory if it limits the years of experience (e.g., ‘you have
a maximum of 5 years of experience’), but not if it specifies the minimum
years of experience needed. When we visualized the sentences containing the
keyword ‘experience’, we observed no separation between these two cases.
However, we did see a cluster of non-discriminatory samples that all stated
that salary would be based on experience, which is non-discriminatory.
Possibly, regexes based ‘salary’-related keywords also could capture the
difference between these contexts.

Keyword ‘old’ The keyword ‘old’ also yielded an interesting observation. A
cluster of sentences containing ‘old’ all directly address candidates and
mentioned an desired age, e.g.,: ‘Are you enthusiastic, like to (physically)
work and are you between 18 and 30 years old?’; ‘You are minimally 23 years
old.’; and ‘Are you between 18 and 26 years old?’. However, the cluster also
contained the sentence ‘Are you badass commercial, entrepreneurial, a builder,
mobile, never too old to learn, do you go for freedom, are you studious, is
hierarchy something you are allergic for and are you often smarter than your
boss?’. It fits the general style of directly addressing the candidate (‘Are
you…‘) and also contains the word ‘old’. However, the usage of ‘old’ in this
context is not discriminatory but rather part of a description of the
candidates attitude.

In sum, our qualitative analysis leads us to conclude that neural embeddings
do not offer a silver-bullet solution to improving detection of illegal age
discrimination over what is already possible using regexes. We did not uncover
evidence that suggests that it would be worthwhile to trade in the
explainability of the regex approach for benefits offered by using sentence
embeddings.

##  6 Conclusion and Outlook

In this paper, we have investigated the contribution of regexes to the task of
automatically detecting illegal age discrimination in Dutch job ads. We have
found there is potential to improve the recall of the regex lists of Fokkens
et al. (2018), which constitute the current state of the art, not only by
adding keywords, but also by creating additional regexes.

Future work should investigate a simple approach based on rule mining, which
was not explored by Fokkens et al. (2018). In Pillar (2022), we report an
exploration of automating the generation of regular expressions using active
learning and genetic programming, but more work is necessary if these
directions are to yield fruit.

The results of our analysis suggest that there is little to be gained in using
neural embeddings directly in age discrimination detectors. Instead, neural
embeddings could have a role in the discover of new keywords and new regexes,
extending a simple rule mining approach. Using neural embeddings in this way
would allow us to continue to benefit from the explainability of the regex
approach.

The results of our qualitative study are not dependent on particular keywords,
writing styles, or special properties of the Dutch language. For this reason,
we expect that our findings can be reproduced using other datasets and in
other languages. In fact, regex has been successfully used for general
discrimination detection in Indonesian job ads Ningrum et al. (2020).
Reproduction of our study will confirm and extend our findings, ensuring that
the ‘old’ technology of regex is not discarded for a task for which it is well
suited.

##  7 Acknowledgment

We want to thank everyone involved in the annotation of the dataset used in
this research. Their work made our investigations possible.

## References

  * Andriessen et al. (2014) Iris Andriessen, Henk Fernee, and Karin Wittebrood. 2014.  Ervaren discriminatie in Nederland.  Technical report, Sociaal en Cultureel Planbureau.
  * Burn et al. (2019) Ian Burn, Patrick Button, Luis Felipe Munguia Corella, and David Neumark. 2019.  Older workers need not apply? Ageist language in job ads and age discrimination in hiring.  Technical report, National Bureau of Economic Research.
  * Butler (1969) Robert N Butler. 1969.  Age-ism: Another form of bigotry.  _The Gerontologist_ , 9(4):243–246.
  * Bytheway (2005) Bill Bytheway. 2005.  Ageism and age categorization.  _Journal of social Issues_ , 61(2):361–374.
  * Fokkens et al. (2018) Antske Fokkens, Camiel Beukeboom, and Emailisa Maks. 2018.  Leeftijdsdiscriminatie in vacatureteksten: Een geautomatiseerde inhoudsanalyse naar verboden leeftijd-gerelateerd taalgebruik in vacatureteksten.  Technical report, Het College voor de Rechten van de Mens.
  * Gendron et al. (2016) Tracey L Gendron, E Ayn Welleford, Jennifer Inker, and John T White. 2016.  The language of ageism: Why we need to use words carefully.  _The Gerontologist_ , 56(6):997–1006.
  * Jönson (2013) Håkan Jönson. 2013.  We will be different! Ageism and the temporal construction of old age.  _The Gerontologist_ , 53(2):198–204.
  * Lan et al. (2020) Zhenzhong Lan, Mingda Chen, Sebastian Goodman, Kevin Gimpel, Piyush Sharma, and Radu Soricut. 2020.  ALBERT: A lite BERT for self-supervised learning of language representations.  In _International Conference on Learning Representations (ICLR 2020)_.
  * Ningrum et al. (2020) Panggih Kusuma Ningrum, Tatdow Pansombut, and Attachai Ueranantasun. 2020.  Text mining of online job advertisements to identify direct discrimination during job hunting process: A case study in Indonesia.  _PLOS ONE_ , 15(6):e0233746.
  * Palmore (2001) Erdman Palmore. 2001.  The ageism survey: First findings.  _The Gerontologist_ , 41(5):572–575.
  * Pillar (2022) Anna Pillar. 2022.  Detection of age discrimination: Semi-automatic detection of age discrimination in dutch job advertisements through automatic regex generation.  Master’s thesis, Radboud University.
  * Van Der Maaten and Hinton (2008) Laurens Van Der Maaten and Geoffrey Hinton. 2008.  Visualizing data using t-SNE.  _Journal of Machine Learning Research_ , 9(86):2579–2605.
  * Voss et al. (2018) Peggy Voss, Ehud Bodner, and Klaus Rothermund. 2018.  Ageism: The relationship between age stereotypes and age discrimination.  In Liat Ayalon and Clemens Tesch-Römer, editors, _Contemporary Perspectives on Ageism_ , pages 11–31. Springer International Publishing, Cham.

Table 1: (Appendix A) The list of discriminatory keywords from Fokkens et al.
(2018) used in our work, each illustrated with a sentence from our dataset
that was annotated as discriminatory (translated from Dutch).

DIRECT DISCRIMINATION
---
Keyword | Sample Sentence
young |  | For several companies in the Alkmaar region we are looking for young,
---
motivated candidates who can be deployed flexibly.
| young part
---
(of a team)
| In this role you will be part of a young and dynamic team who are jointly
---
responsible for the design and realization of infrastructure projects up
to ± €6 Million.
fit into a young team | We work with a young team, where you will definitely fit in!
age | Age range 20 - 25 years;
Given the age structure of our team, we prefer a young colleague.
age from to |  | We ask boys and girls aged 16 - 25 years who are full of energy and
---
like to promote this gym!
age to |  | Are you enthusiastic, eager to learn, entrepreneurial and in the age
---
group up to 22 years?
age from | Age from 30 years, we have a big preference for 45 +
old |  | Are you enthusiastic, do you like to work and are you between 18
---
and 30 years old?
in-between | You are between 18 and 25 years old;
at least | We are looking for full-time hospitality professionals, at least 25 years old
INDIRECT DISCRIMINATION
job | Are you a graduate looking for your first-ever job?
side-job | Are you looking for an interesting job in addition to your studies?
earn money |  | Have you just finished school or just graduated and want to earn
---
some extra money before you go on vacation?
experience |  | Experience: You have a college education and have 1 to 3 years of
---
working experience in the media and/or IT industry.
education | You are following the HBO education Construction?
| recent
---
graduate
| For one of our clients we are looking for serious, enthusiastic recent
---
graduated who want to be trained as logistics employees.
step | Are you eager to learn and looking for the first step in your career?
Are you ready for the second step in your career?
study |  | This job is excellent to combine with your studies and is a great
---
addition to your CV!
start |  | For our client, we are looking for an enthusiastic and spirited starter
---
for the position of Online Marketer.
lesson schedule | With great regularity we have on-call jobs that fit perfectly with your class schedule.


# THERMO-MECHANICAL LEVEL-SET TOPOLOGY OPTIMIZATION OF A LOAD CARRYING BATTERY
PACK FOR ELECTRIC AIRCRAFT

Alexandre T.R. Guibert1 Murtaza Bookwala1 Ashley Cronk2 Y. Shirley Meng3 and
H. Alicia Kim1,2 1: Structural Engineering Department
Jacobs School of Engineering
University of California San Diego
Matthews Lane, La Jolla, CA 92093, USA
<EMAIL_ADDRESS>http://m2do.ucsd.edu/

2: Materials Science and Engineering Department
Jacobs School of Engineering
University of California San Diego
Matthews Lane, La Jolla, CA 92093, USA
<EMAIL_ADDRESS>http://smeng.ucsd.edu/

3: Pritzker School of Molecular Engineering
The University of Chicago
5801 S Ellis Avenue, Chicago, 60637, Illinois, USA
<EMAIL_ADDRESS>https://voices.uchicago.edu/smeng/

###### Abstract

A persistent challenge with the development of electric vertical take-off and
landing vehicles (eVTOL) to meet flight power and energy demands is the mass
of the load and thermal management systems for batteries. One possible
strategy to overcome this problem is to employ optimization techniques to
obtain a lightweight battery pack while satisfying structural and thermal
requirements. In this work, a structural battery pack with high-energy-density
cylindrical cells is optimized using the level-set topology optimization
method. The heat generated by the batteries is predicted using a high-fidelity
electrochemical model for a given eVTOL flight profile. The worst-case
scenario for the battery’s heat generation is then considered as a source term
in the weakly coupled steady-state thermo-mechanical finite element model used
for optimization. The objective of the optimization problem is to minimize the
weighted sum of thermal compliance and structural compliance subjected to a
volume constraint. The methodology is demonstrated with numerical examples for
different sets of weights. The optimized results due to different weights are
compared, discussed, and evaluated with thermal and structural performance
indicators. The optimized pack topologies are subjected to a transient thermal
finite element analysis to assess the battery pack’s thermal response.

###### keywords:

Multiphysics topology optimization, level-set method, structural battery pack,
electrochemical model, electric vehicles

Alexandre T.R. Guibert, Murtaza Bookwala, Ashley Cronk, Y. Shirley Meng, and
H. Alicia Kim

##  1 Introduction

The aerospace sector is undergoing a significant transformation due to the
emergence of electric aircraft and the advancement of urban air mobility (UAM)
concepts. One of the solutions to UAM is the electric Vertical Take-Off and
Landing (eVTOL) vehicles, which have the potential to alleviate ground traffic
congestion and provide a secure and environmentally friendly alternative to
conventional individual transportation. However, eVTOL vehicles pose
fundamental engineering challenges such as noise control and power
requirements. To make eVTOL vehicles a viable transportation option, there is
a crucial need to enhance their power density while ensuring safety by
carefully designing the vehicles’ battery packs. By utilizing topology
optimization, it is possible to optimize the distribution of materials in a
battery pack with the objective of improving the structural and thermal
performance while minimizing its weight which ultimately contributes to the
overall efficiency of the aircraft. This can eliminate a mechanical and
thermal load management system which is otherwise needed, thus reducing the
mass and volume budget. Therefore, the integration of topology optimization in
the development of eVTOL vehicles presents a promising opportunity to move
closer to a sustainable and efficient form of UAM.

In this work, we present a methodology for the multiphysics optimization of a
battery pack for electric aircraft using the level set method. The volumetric
heat generation rate from the batteries is estimated using an electrochemical
model and the worst-case scenario is considered for design optimization. The
electrochemical model, heat transfer model, and elasticity model are
introduced in Section 2.1, 2.2, and 2.3 respectively. The level-set topology
optimization method and the optimization problem and workflow are discussed in
Section 3. The methodology is demonstrated with numerical examples in Section
4.

##  2 Multiphysics model

###  2.1 High fidelity electrochemical model

The cell behavior is modeled using the Doyle Fuller Newman (DFN) model [1, 2,
3, 4] which describes the electrochemical response of lithium-ion cells. It is
solved for the electric potentials and lithium-ion concentration distribution
in a cell given some electric loads such as an applied current, voltage, or
power. The DFN model in its one-dimensional version assumes that the
charge/discharge process is mainly unidirectional, i.e, only the effects from
one current collector to another are considered. It also assumes that the
solid particles are spherical. The lithium-ion diffusion in these particles is
considered by having a pseudo second dimension associated with the particles’
radius. The governing equations for the DFN model are the following:

  1. 1.

Molar conservation in the electrolyte,

  2. 2.

Solid state Fickian diffusion in the the solid particles,

  3. 3.

Charge conservation in the electrolyte and in the particles based on Ohm’s
law,

  4. 4.

Intercalation kinetics based on the Butler-Volmer equation which effectively
couples the macro dimension and the pseudo dimension.

The DFN model is implemented using the open-source library PyBaMM [5, 6, 7].

###  2.2 Heat transfer model

The governing equation for the steady-state thermal model considering thermal
conduction only is,

$\nabla\cdot(\kappa\nabla T)+Q=0\,,$ (1)

where $\kappa$ is the thermal conductivity, $T$ is the temperature, and $Q$ is
the volumetric heat generation rate. The latter is determined by the
electrochemical model by adding the volumetric heat generation due to Ohmic
heating $Q_{Ohm}$ from the electrical resistance of the cell, irreversible
heating from the electrochemical reactions $Q_{rxn}$, and reversible heating
due to entropic changes $Q_{rev}$. The heat transfer model is implemented
using the finite element method and automatic differentiation software, FEniCS
and DOLFIN [8, 9, 10].

###  2.3 Elasticity model

The governing equation of the linear elasticity problem is,

$\nabla\cdot\boldsymbol{\sigma}(\boldsymbol{u})+\boldsymbol{b}=0\,,$ (2)

where $\boldsymbol{b}$ is the body force, $\boldsymbol{u}$ is the
displacement, and $\boldsymbol{\sigma}$ is the Cauchy stress tensor. The
temperature distribution solved by the heat transfer model resulting in
thermal strain $\varepsilon_{T}$,

$\varepsilon_{T}=\alpha\Delta T\,,$ (3)

where $\alpha$ is the coefficient of thermal expansion and $\Delta T$ is the
temperature increase, that is, $\Delta T=T-T_{ref}$ where $T_{ref}$ is the
reference temperature. The constitutive law then becomes,

$\boldsymbol{\sigma}=\mathbb{C}:(\boldsymbol{\varepsilon}-\varepsilon_{T}\boldsymbol{1})\,,$
(4)

where $\mathbb{C}$ is the elastic constitutive tensor, $\boldsymbol{1}$ is the
unit tensor, and $\boldsymbol{\varepsilon}$ is the strain tensor defined as
$\boldsymbol{\varepsilon}=\frac{1}{2}(\nabla\boldsymbol{u}+\nabla\boldsymbol{u}^{\top})$.
The linear elasticity model is implemented in its weak form using FEniCS and
DOLFIN [8, 9, 10].

##  3 Topology optimization

###  3.1 Level-set topology optimization

The optimized design is described by an implicit function
$\phi(\boldsymbol{x})$ such that

$\begin{cases}\phi({\bf x})\geq 0,{\bf x}\in\Omega\\\ \phi({\bf x})=0,{\bf
x}\in\Gamma\\\ \phi({\bf x})<0,{\bf x}\not\in\Omega\end{cases}$ (5)

where $\Omega$ is the solid domain such that $\Omega\subset\mathcal{D}$ where
$\mathcal{D}$ is the design domain and $\mathcal{D}\setminus\Omega$ is the
void domain. The boundary of the solid domain is $\Gamma$ described by the
zero level-set. The design is iteratively updated by the discretized Hamilton-
Jacobi equation,

$\phi^{k+1}_{i}=\phi^{k}_{i}-\Delta t|\nabla\phi^{k}_{i}|V_{n,i}\,,$ (6)

where $k$ is the iteration number, $i$ is a boundary point, $\Delta t$ is the
pseudo time-step, and $V_{n}$ is the design velocity normal to $\Gamma$ [11,
12]. The finite element analysis is carried out on a fixed grid, i.e., a non-
conforming mesh is used. Thus, as the design evolves, the zero level-set cuts
finite elements such that for a given element some nodes of that element might
be inside the optimized design and some might be outside. To address this
issue, the following material interpolation scheme is used,

$\begin{split}\kappa_{e}=\left(\gamma_{min}(1-\gamma_{e})+\gamma_{e}\right)\kappa\,,\\\
E_{e}=\left(\gamma_{min}(1-\gamma_{e})+\gamma_{e}\right)E\,,\end{split}$ (7)

where $\gamma_{e}$ is the fraction of the element where $\phi({\bf x})>0$, and
$\gamma_{min}$ is a small value, taken as $10^{-4}$ for this study, to ensure
that the stiffness and conductivity matrices are non-singular. The
optimization is implemented using ParaLeSTO [13] which is a modular open-
source level-set topology optimization code [14, 15].

###  3.2 Optimization workflow and formulation

The objective function of the optimization problem $\mathcal{J}$ is the
weighted sum of the normalized thermal and structural compliance, i.e.,

$\mathcal{J}({\gamma},{T}({\gamma}),{\bf u}({\gamma}))\triangleq
k_{1}\frac{C_{S}}{C_{S0}}+k_{2}\frac{C_{T}}{C_{T0}}\,,$ (8)

where $C_{S}$ and $C_{T}$ are the structural compliance and thermal compliance
defined as

$\begin{split}C_{S}=\boldsymbol{F}_{S}^{\top}\boldsymbol{U}\,,\\\
C_{T}=\boldsymbol{F}_{T}^{\top}\boldsymbol{T}\,,\\\ \end{split}$ (9)

where $\boldsymbol{F}_{T}$ and $\boldsymbol{F}_{S}$ are the thermal force
vector and structural force vector respectively. The normalization factors
$C_{S0}$ and $C_{T0}$ are reinitialized every 5 iterations. Moreover, let
$k\equiv k_{1}=1-k_{2}$. Thus, Eq.(8) becomes

$\mathcal{J}({\gamma},{T}({\gamma}),{\bf
u}({\gamma}))=k\frac{C_{S}}{C_{S0}}+(1-k)\frac{C_{T}}{C_{T0}}\,.$ (10)

Additionally, the volume for the optimized part is constrained such that a
fraction $\xi$ of the design domain is prescribed. Finally, the optimization
problem to be solved can be expressed as

$\displaystyle{\rm Minimize}$
$\displaystyle\mathcal{J}({\gamma},{T}({\gamma}),{\bf u}({\gamma}))$
$\displaystyle{\rm w.r.t.}$ $\displaystyle{\gamma}$ (11) $\displaystyle{\rm
subject~{}to}$
$\displaystyle\operatorname{Vol}(\Omega)\leq\xi\operatorname{Vol}(\mathcal{D})$
$\displaystyle{\cal R}_{1}({\gamma},{T}({\gamma}))=0$ $\displaystyle{\cal
R}_{2}({\gamma},{\bf u}({\gamma}))=0$

where ${\cal R}_{1}$ and ${\cal R}_{2}$ are the residuals of the thermal and
elasticity models respectively. The optimization workflow is presented in
Fig.1.

Figure 1: Optimization workflow

##  4 Numerical results

###  4.1 Set up and boundary conditions

The LG CHEM INR21700-M50L cell is used for its high energy density and the
properties are taken from [16]. The power profile is computed using [17] where
the energy is taken as 17.8 Wh [18]. The power profile, the voltage profile
obtained with the electrochemical model, and the estimated volumetric heat
generation rate are presented in Fig.2.

(a) Power profile

(b) Voltage profile

(c) Heat generation from power profile

Figure 2: Electrochemical response of 21700 cells for a given power profile

A 3x2 configuration with a spacing of 5 mm between the cells is chosen for the
battery pack. The cells are 70 mm in height with a diameter of 21 mm. The pack
is cooled at the top and bottom assuming a constant fixed temperature.
Structurally the pack is analogous to a cantilever beam with one side fixed
and the other subjected to a traction load of 15 N/mm2. The boundary
conditions and the geometry are presented in Fig.3.

(a) Geometry of the problem

(b) Boundary conditions

Figure 3: Geometry and boundary conditions for the numerical examples where
only Dirichlet boundary conditions and non-zero Neumann boundary conditions
are given

The battery pack is discretized with 48x32x40 linear hexahedra elements
leading to a total of 265,188 degrees of freedom. The material properties for
the study are given in Table 1.

Table 1: Properties for the thermo-mechanical analysis Property | Aluminum | Cell
---|---|---
Thermal conductivity $\kappa$ [W/m.K] | 220.0 | 1.25
Young’s modulus $E$ [GPa] | 68.0 | 1.5
Poisson’s ratio $\nu$ [-] | 0.32 | 0.2
Thermal expansion $\alpha$ [K-1] | 21x10-6 | 10x10-6

###  4.2 Optimization results

The following weights are investigated $k=$ 1.0, 0.9, 0.7, 0.5, 0.3. The
convergence history for the thermal and structural compliance for the 5 cases
is given in Fig.4. First, the volume constraint is met, and then the objective
is gradually minimized until it reaches the minimum bound. The jump at
iteration 100 is caused by a modification in the move limit value, which
limits the amount of change allowed from one iteration to the next. The
optimization results for 3 selected cases are presented in Fig.5. As the value
of $k$ is decreased, we observe a shift in the topology between the cells -
from a stiffener-like structure to one consisting of elements that resemble
beams. Additionally, more material is allocated towards the ends of the
batteries to facilitate their connection to the heat sinks. Finally, the
maximum displacement and maximum temperature of the final design as a function
of the weights given to each compliance are given in Fig.6. Once thermal
compliance is taken into account, a significant reduction in the normalized
maximum temperature is observed. However, as the value of $k$ continues to
decrease, the decrease in maximum temperature becomes less pronounced. This
trend is similar to what is observed in the convergence plot shown in Fig.4.

(a) Structural compliance convergence history

(b) Thermal compliance convergence history

Figure 4: Convergence history of structural and thermal compliances for
different values of $k$. Note that the jump at iteration 100 is due to a
reduction of the move limit value

(a) top view $k$ = 0.3

(b) top view $k$ = 0.5

(c) top view $k$ = 1.0

(d) front view $k$ = 0.3

(e) front view $k$ = 0.5

(f) front view $k$ = 1.0

(g) isometric view $k$ = 0.3

(h) isometric view $k$ = 0.5

(i) isometric view $k$ = 1.0

Figure 5: Optimization results for selected cases

(a) Maximum displacement

(b) Maximum temperature

Figure 6: Maximum displacement and temperature of the final design normalized
by the maximum state of the initial design as a function of $k$

###  4.3 Transient response of the battery pack

The effective volumetric heat capacity $\rho c_{p}$ is taken as 1,767,574
J.m-3.K-1 and 2,430,000 J.m-3.K-1 for the cell and the pack, respectively [16,
19, 20]. The optimized topologies are analyzed using a transient heat
conduction model implemented using FEniCS. An implicit Euler scheme that is
unconditionally stable is chosen for the time discretization. The temperature
time history and temperature distribution are presented in Fig.7. The maximum
temperatures during take-off and landing do not appear to be significantly
affected by thermal compliance considerations. These phases are short and the
steady state is not reached. The overall maximum temperature does not seem to
be much reduced when considering the topology optimized for steady-state
considerations. Consequently, it seems worthwhile to consider transient heat
conduction topology optimization specifically for takeoff and landing or for
the entire flight but that is beyond the scope of this study. On the other
hand, in the cruise segment where steady-state is reached, considering thermal
compliance in the optimization formulation leads to a reduction of more than
10 % of the maximum temperature. Such a reduction could mitigate battery
degradation. More research is needed to quantify this effect.

Figure 7: Maximum temperature time history normalized by the maximum
temperature time history for $k=1$

##  5 Conclusions

In this study, we presented a methodology for conducting thermo-mechanical
level-set topology optimization of a load-carrying battery pack in an eVTOL
and employed an electrochemical model to predict heat generation from the
batteries based on a given flight profile. A multi-objective function that
considered both thermal and structural compliance was minimized. We
demonstrated the approach for several cases and analyzed them using a
transient heat conduction model. The methodology can be adapted and reused for
different power profiles, boundary conditions, and pack configurations. In the
future, we plan to expand our research to encompass various power profiles and
boundary conditions, examine degradation and different battery chemistries,
and increase the scale of the thermo-mechanical model.

## Acknowledgements

The authors acknowledge the support from NASA under award No. 80NSSC21M0070.

## References

  * Doyle et al. [1993] M. Doyle, T. F. Fuller, and J. Newman.  Modeling of galvanostatic charge and discharge of the lithium/polymer/insertion cell.  _Journal of the Electrochemical society_ , 140(6):1526–1533, 1993.  10.1149/1.2221597.
  * Ai et al. [2019] W. Ai, L. Kraft, J. Sturm, A. Jossen, and B. Wu.  Electrochemical thermal-mechanical modelling of stress inhomogeneity in lithium-ion pouch cells.  _Journal of The Electrochemical Society_ , 167(1):013512, 2019.  10.1149/2.0122001JES.
  * Timms et al. [2021] R. Timms, S. G. Marquis, V. Sulzer, C. P. Please, and S. J. Chapman.  Asymptotic Reduction of a Lithium-ion Pouch Cell Model.  _SIAM Journal on Applied Mathematics_ , 81(3):765–788, 2021.  10.1137/20M1336898.
  * Deshpande et al. [2012] R. Deshpande, M. Verbrugge, Y.-T. Cheng, J. Wang, and P. Liu.  Battery cycle life prediction with coupled chemical degradation and fatigue mechanics.  _Journal of the Electrochemical Society_ , 159(10):A1730, 2012.  10.1149/2.049210jes.
  * Sulzer et al. [2021] V. Sulzer, S. G. Marquis, R. Timms, M. Robinson, and S. J. Chapman.  Python Battery Mathematical Modelling (PyBaMM).  _Journal of Open Research Software_ , 9(1):14, 2021.  10.5334/jors.309.
  * Andersson et al. [2019] J. A. E. Andersson, J. Gillis, G. Horn, J. B. Rawlings, and M. Diehl.  CasADi – A software framework for nonlinear optimization and optimal control.  _Mathematical Programming Computation_ , 11(1):1–36, 2019.  10.1007/s12532-018-0139-4.
  * Harris et al. [2020] C. R. Harris, K. J. Millman, S. J. van der Walt, R. Gommers, P. Virtanen, D. Cournapeau, E. Wieser, J. Taylor, S. Berg, N. J. Smith, et al.  Array programming with NumPy.  _Nature_ , 585(7825):357–362, 2020.  10.1038/s41586-020-2649-2.
  * Alnæs et al. [2015] M. Alnæs, J. Blechta, J. Hake, A. Johansson, B. Kehlet, A. Logg, C. Richardson, J. Ring, M. E. Rognes, and G. N. Wells.  The fenics project version 1.5.  _Archive of Numerical Software_ , 3(100), 2015.
  * Logg and Wells [2010] A. Logg and G. N. Wells.  Dolfin: Automated finite element computing.  _ACM Transactions on Mathematical Software (TOMS)_ , 37(2):1–28, 2010.
  * Logg et al. [2012] A. Logg, K.-A. Mardal, and G. Wells.  _Automated solution of differential equations by the finite element method: The FEniCS book_ , volume 84.  Springer Science & Business Media, 2012.
  * Dunning and Kim [2015] P. D. Dunning and H. A. Kim.  Introducing the sequential linear programming level-set method for topology optimization.  _Structural and Multidisciplinary Optimization_ , 51:631–643, 2015.
  * Sivapuram et al. [2016] R. Sivapuram, P. D. Dunning, and H. A. Kim.  Simultaneous material and structural optimization by multiscale topology optimization.  _Structural and multidisciplinary optimization_ , 54:1267–1281, 2016.
  * Kambampati and Jauregui [2023] S. Kambampati and C. M. Jauregui.  Paralesto, Feb. 2023.  URL https://doi.org/10.5281/zenodo.7613753.
  * Hyun et al. [2022] J. Hyun, C. Jauregui, H. A. Kim, and A. Neofytou.  On development of an accessible and non-intrusive level-set topology optimization framework via the discrete adjoint method.  In _AIAA SCITECH 2022 Forum_ , page 2548, 2022.
  * Guibert et al. [2023] A. T. Guibert, J. Hyun, A. Neofytou, and H. A. Kim.  Implementation of a plug-and-play reusable level-set topology optimization framework via comsol multiphysics.  In _AIAA SCITECH 2023 Forum_ , page 1675, 2023.
  * Chen et al. [2020] C.-H. Chen, F. Brosa Planella, K. O’Regan, D. Gastol, W. D. Widanage, and E. Kendrick.  Development of Experimental Techniques for Parameterization of Multi-scale Lithium-ion Battery Models.  _Journal of The Electrochemical Society_ , 167(8):080534, 2020.  10.1149/1945-7111/ab9050.
  * Yang et al. [2021] X.-G. Yang, T. Liu, S. Ge, E. Rountree, and C.-Y. Wang.  Challenges and key requirements of batteries for electric vertical takeoff and landing aircraft.  _Joule_ , 5(7):1644–1659, 2021.
  * Batemo [2022] Batemo.  Lg chem inr21700-m50l, Oct 2022.  URL https://www.batemo.de/products/batemo-cell-library/lg-chem-inr21700-m50l/.
  * O’Regan et al. [2022] K. O’Regan, F. B. Planella, W. D. Widanage, and E. Kendrick.  Thermal-electrochemical parameters of a high energy lithium-ion cylindrical battery.  _Electrochimica Acta_ , 425:140700, 2022.
  * Steinhardt et al. [2022] M. Steinhardt, J. V. Barreras, H. Ruan, B. Wu, G. J. Offer, and A. Jossen.  Meta-analysis of experimental results for heat capacity and thermal conductivity in lithium-ion batteries: A critical review.  _Journal of Power Sources_ , 522:230829, 2022.