ifaamas [AAMAS ’21]Proc. of the 20th International Conference on Autonomous
Agents and Multiagent Systems (AAMAS 2021)May 3–7, 2021London, UKU. Endriss,
A. Nowé, F. Dignum, A. Lomuscio (eds.) 2021 2021 ??? University of Luxembourg
SnT - Interdisciplinary Centre for Security, Reliability and Trust

# Incentive Mechanism Design for Federated Learning: Hedonic Game Approach

Cengis Hasan<EMAIL_ADDRESS>
###### Abstract.

Incentive mechanism design is crucial for enabling federated learning. We deal
with clustering problem of agents contributing to federated learning setting.
Assuming agents behave selfishly, we model their interaction as a stable
coalition partition problem using hedonic games where agents and clusters are
the players and coalitions, respectively. We address the following question:
is there a family of hedonic games ensuring a Nash-stable coalition partition?
We propose the Nash-stable set which determines the family of hedonic games
possessing at least one Nash-stable partition, and analyze the conditions of
non-emptiness of the Nash-stable set. Besides, we deal with the decentralized
clustering. We formulate the problem as a non-cooperative game and prove the
existence of a potential game.

###### Key words and phrases:

Federated Learning, Hedonic Games, Optimal Clustering

##  1\. Introduction

Data protection is a major concern. If we do not trust someone withholding our
data, we may opt for federated learning by privately developing intelligent
systems to create privacy-preserving AI. Federated learning enables privacy-
preserving machine learning in a decentralized way Li et al. (2020). It is
used in situations where data is distributed among different agents and
training is impossible due to the difficulty to collect data centrally. All
data is kept on device while a shared (global) learning model is trained in
each device and aggregated (combined) centrally. Formally, we consider the
following setting: i) data owner agents which locally trains the shared
learning model, and ii) model aggregating entity (MAE) which combines learning
model of its own with the agents. MAE and agents contribute to the same shared
learning model. Federated learning has been identified as a distributed
machine learning framework which sees rapid advances and broad adoption in
next generation networking and edge systems Elgabli et al. (2020); Li et al.
(2020); by: Peter Kairouz and McMahan (2021); Zheng et al. (2020); Samarakoon
et al. (2018); Khan et al. (2020); Hosseinalipour et al. (2020); Yang et al.
(2020). Obviously, the motivation to implement federated learning is to reduce
the variance in a learned model by accessing more data.

A very crucial question is how would MAE motivate the agents to participate in
federated learning. Designing the mechanism of agents’ incentives can be
performed by utilizing various frameworks such game theory, auction theory,
etc Samarakoon et al. (2018). Any clustering among agents (players) being able
to make strategic decisions becomes a coalition formation game when the
players –for various individual reasons– may wish to belong to a relative
small coalition rather than the grand coalition–the set of all players.
Players’ moves from one to another coalition are governed by a set of rules.
Basically, an agent (player) will move to a new coalition when it may obtain a
better gain from this coalition. We shall not consider any permission
requirements, which means that a player is always accepted by a coalition to
which the player is willing to join. Based on those rules, the crucial
question in the game context is how a stable partition exists. This is
essential to enable federated learning.

We study the hedonic coalition formation game model of the agents and analyze
the Nash stability Hajduková (2006). A coalition formation game is called
hedonic if each player’s preferences over partitions of players depend only on
the members of his/her coalition. Finding a stable coalition partition is the
main question in a coalition formation game. We refer to Aziz and Brandl
(2012) discussing the stability concepts associated to hedonic conditions. In
the sequel, we concentrate on the Nash stability. The definition of the Nash
stability is quite simple: a partition of players is Nash stable whenever no
player deviates from its coalition to another coalition in the partition.

In this work, we deal with the following problem: having coalitions associated
with their gain, we seek the answer of how must the coalition gain be
allocated to the players in order to obtain a stable coalition partition.
Clearly, the fundamental question is to determine which gain allocation
methods may ensure a Nash-stable partition. Note that the answer of this
enables to find the family of hedonic games that possess at least one Nash-
stable partition of players. We first propose the definition of the Nash-
stable set which is the set of all possible allocation methods resulting in
Nash-stable partitions. We show that additively separable and symmetric gain
allocation always ensures Nash-stable partitions. Moreover, our work aims also
at finding the partitions in a decentralized setting which basically
corresponds to finding stable decentralized clustering. We model this problem
as a non-cooperative game and show that such a game is a potential game.

A recent work that considers the clustering of agents in the form of hedonic
games can be found in Donahue and J. Kleinberg (2021) where the authors study
the agents decisions to participate in federated learning setting in case of a
biased global model. In Lim et al. (2020) a federated learning based privacy-
preserving approach is proposed to facilitate collaborative machine learning
among multiple model owners in mobile crowdsensing. Another work in Kim (2020)
implements mechanism design and differential privacy where an objectives-first
approach is considered for designing incentives toward desired objectives; the
differential privacy can provide a theoretical guarantee for users’ privacy in
federated learning participation. In Le et al. (2021), an incentive mechanism
between a base station and mobile users as an auction game is formulated where
the base station is an auctioneer and the mobile users are the sellers. In
Ding et al. (2020), the authors consider a multidimensional contract-theoretic
approach on optimal incentive mechanism design, in the presence of users’
multi-dimensional private information including training cost and
communication delay. The work in Zhan and Zhang (2020) deals with a deep
reinforcement learning based approach to design the incentive mechanism and
find the optimal trade-off between model training time and parameter server’s
payment. The authors in Sarikaya and Ercetin (2020) analyze the influence of
heterogeneous clients on federated learning convergence, and propose an
incentive mechanism to balance the time delay of each iteration. For a recent
survey on mechanism design for federated learning, we refer to the paper in
Zhan et al. (5555).

##  2\. Motivation and Problem Description

Figure 1. Federated learning framework.

We consider a set of agents denoted $N=\\{1,2,\ldots,n\\}$ that can
participate in the federated learning setting, and a model aggregating entity
(MAE) which aggregates (combines) learning model of its own with the agents.
MAE and agents contribute in the same global learning model. The parameters of
learning model of MAE and agent $i$ are represented by
$\bm{\theta}_{\text{MAE}}=(\theta_{\text{MAE},1},\theta_{\text{MAE},2}\ldots,\theta_{\text{MAE},M})$
and $\bm{\theta}_{i}=(\theta_{i,1},\theta_{i,2},\ldots,\theta_{i,M})$,
respectively where $M$ is the number of trainable weights (variables) of the
learning model, and every agent $i$ has $m_{i}$ data samples. We also consider
that the communication link between MAE and agent $i$ can be characterized by
a probability of reliable transmission (e.g. low bit error rate) denoted
$p_{i}$. The vector of probabilities of reliable transmission of all agents is
shown by $\bm{p}=(p_{1},p_{2},\ldots,p_{n})$. If a cluster, say $S\subseteq
N$, of agents agree to be federated, then the aggregated (combined) learning
model is found by using an aggregation method which is given by

$(\bm{\theta}^{S};\bm{x})=\mathsf{A}(\bm{\theta}_{1},\bm{\theta}_{2},\ldots,\bm{\theta}_{n_{S}};\bm{x}),\quad(n_{S}=|S|)$
(1)

where $\mathsf{A}(\cdot)$ shows the aggregation function given
$\bm{\theta}_{1},\bm{\theta}_{2},\ldots,\bm{\theta}_{n_{S}}$ and
$\bm{x}=(x_{1},x_{2},\ldots,x_{n})$ in which $x_{i}=1$ if MAE receives
successfully information of $\bm{\theta}_{i}$. This is nothing more than
choosing agent $i$ with probability $p_{i}$.

###  2.1. Incentives of Agents

We assume that agents may not agree to be in the same cluster depending on
their preferences. Thus, we come up with the case where multiple disjoint
clusters may occur. In Figure 1, we illustrate such an example scenario in
which two disjoint clusters, i.e. $\\{1,2,3\\}$ and $\\{4,5\\}$, create two
different aggregated learning models, i.e.
$(\bm{\theta}^{\\{1,2,3\\}};\bm{x})$ and $(\bm{\theta}^{\\{4,5\\}};\bm{x})$,
respectively.

From the perspective of agents, we assume that MAE assigns a gain to all
possible clusters. Note that from the MAE point of view, this is the cost that
must be paid to the cluster. By this way, MAE evaluates the contribution to
the aggregated model. However, we shall formulate the problem using the “gain”
term due to the fact that from the agents point of view, this corresponds to
the earnings of the agents. Then, we come up with the question how to design
the incentives in order that the agents are willing to participate in
federated learning setting taking into account their preferences.

In this work, we consider the following linear aggregation method:

$(\bm{\theta}^{S};\bm{x})=\frac{\sum_{i\in
S}x_{i}m_{i}\bm{\theta}_{i}}{\sum_{i\in S}x_{i}m_{i}},\quad
x_{i}=\begin{cases}1,&\mbox{reception successful},\\\
0,&\mbox{otherwise}.\end{cases}$ (2)

which essentially corresponds to the weighted average of the learning models
within the cluster. Furthermore, we represent by
$\mathcal{L}(\bm{\theta}^{S};\bm{x})$ the loss of learning model given by
parameters $\bm{\theta}^{S}$. The expected value of loss function is given by

$\displaystyle\mathbb{E}_{\bm{x}}[\mathcal{L}(\bm{\theta}^{S})]=\sum_{\bm{x}\in\mathcal{X}}\mathcal{L}(\bm{\theta}^{S};\bm{x})\mathbb{P}[{\bm{x}}]$
(3) $\displaystyle\mathbb{P}[{\bm{x}}]=\prod_{i\in
N}p_{i}^{x_{i}}(1-p_{i})^{1-x_{i}}$ (4)

where $\mathcal{X}$ with $|\mathcal{X}|=2^{n}$ is the set of all possible
combinations of $\bm{x}$ vectors. On the other hand, given $\bm{x}$ and
cluster $S$, the loss of aggregated model due to $S$ is lower than the loss
averaged over the agents in $S$:

$\mathcal{L}(\bm{\theta}^{S};\bm{x})\leq\frac{\sum_{i\in
S}x_{i}\mathcal{L}(\bm{\theta}_{i})}{\sum_{i\in S}x_{i}}$ (5)

due to the fact that when the disjoint agents are merged, the amount of data
used to train the model increases which results in lower training error. If
two disjoint clusters $S$ and $T$, i.e. $S\cap T=\emptyset$, are federated,
then we denote the new parameters as $\bm{\theta}^{S\cup T}$. It is reasonable
to assume that the minimum of loss of $\bm{\theta}^{S\cup T}$ is lower than
the minimum of average loss of $\bm{\theta}^{S}$ and $\bm{\theta}^{T}$:

$\mathcal{L}(\bm{\theta}^{S\cup T};\bm{x})\leq\tfrac{\sum_{i\in
S}x_{i}}{\sum_{i\in S\cup
T}x_{i}}\mathcal{L}(\bm{\theta}^{S};\bm{x})+\tfrac{\sum_{i\in
T}x_{i}}{\sum_{i\in S\cup T}x_{i}}\mathcal{L}(\bm{\theta}^{T};\bm{x}),$ (6)

Moreover, we consider that there exists a communication cost, denoted $c$,
when MAE receives the learning model’s parameters’ data; note that this data
increases with the size of cluster. On the other hand, MAE earns a monetary
gain by utilizing the aggregated model and commits a monetary value which can
be paid to the agents. Then, the agents deduct the communication cost $c$ from
what they earn from MAE. We represent by $u$ the gain which assigns a real
value for every subset of $N$, i.e. $u:2^{N}\rightarrow\mathbb{R}$ where
$2^{N}$ is the collection of all possible non-empty subsets of $N$ and empty
set $\emptyset$, and we set $u(\emptyset)=0$. Thus, the gain of cluster $S\in
2^{N}$ is given by

$u(S)=f\left(\tfrac{1}{\mathbb{E}_{\bm{x}}[\mathcal{L}(\bm{\theta}^{S})]}\right)-c(S).$
(7)

where $f:\mathbb{R}\rightarrow\mathbb{R}$ can be a monotonically increasing
function and inversely proportional to
$\mathbb{E}_{\bm{x}}[\mathcal{L}(\bm{\theta}^{S})]$ meaning that the less loss
the more gain. Note that this is the monetary value that cluster $S$ earns.
Any agent $i$ can join a cluster if guaranteed to be paid at least
$u(i)=\pi_{i}$ which is the minimal price given by

$\pi_{i}=f\left(\tfrac{p_{i}}{\mathcal{L}(\bm{\theta}_{i})}\right).$ (8)

Note that $p_{i}$ is the second parameter which has an impact on the price
asked by the agent. It corresponds to the fact that as $p_{i}$ has a poor
value, the agent asks lower price to participate in the federation.

###  2.2. Optimal Clustering

Consider that MAE aims at finding the clustering that results in minimal cost.
Optimal clustering problem is defined through the agents $N$ and a
_clustering_ set $\Pi$ which partitions the agents’ set $N$ such that
$\bigcup_{S\in\Pi}S=N$. All clusters in $\Pi$ are disjoint clusters, i.e.,
$S\cap T=\emptyset$ for all $S,T\in\Pi$. Given $\mathcal{P}$, the set of all
possible clustering structures, the optimal clustering problem is to find a
clustering $\Pi\in\mathcal{P}$ which minimizes the objective while satisfying
the constraints of agents:

$\displaystyle\min_{\Pi\in\mathcal{P}}\sum_{S\in\Pi}u(S)\mbox{ subject to}$
$\displaystyle\sum_{i\in S}\pi_{i}\leq u(S),\quad\forall S\in\Pi,$ (9)

where the constraints in eq. (2.2) ensure that the demand of agents are
satisfied. The optimization only tells that the agents are guaranteed to be
paid their minimal price but not how much more if the gain of cluster allows
it.

###  2.3. Clustering under Selfishness

As agents can behave selfishly, the fundamental question is to find clusters
which are stable under selfishness. Let us consider that agent $i$ shall get
some monetary gain by joining cluster $S$ as following:

$\mbox{gain of agent }i=\pi_{i}+\phi_{i}^{S}$ (10)

where $\phi_{i}^{S}\in\mathbb{R}$ is the clustering gain of agent $i$ by
joining cluster $S$, and we set $\phi_{i}^{i}=0$ for all $i\in N$. Such a
setting enables to deal with the clustering gains. Thus, the fundamental
problem becomes to

> find clustering gains $\phi$ so that the agents agree not to change their
> cluster

Obviously, this is the stable clustering problem under selfishness where the
agents strategically decide to which cluster to join; thus, we can define the
problem as a coalition formation game. We then change the language of problem
formulation using game theoretic terms, i.e.

agents $\rightarrow$ players

cluster $\rightarrow$ coalition

clustering $\rightarrow$ partition

In the sequel, we deal with figuring out family of coalition formation games
that ensure stable clusterings.

##  3\. Hedonic Game

A hedonic coalition formation game (in short, hedonic game) is given by a pair
$\langle N,\succ\rangle$, where
$\succ:=(\succeq_{1},\succeq_{2},\ldots,\succeq_{n})$ denotes the preference
profile, specifying for each player $i\in N$ his preference relation
$\succeq_{i}$, i.e. a reflexive, complete and transitive binary relation.

Given $\Pi$, called as coalition partition, and $i$, $S_{\Pi}(i)$ denotes the
set $S\in\Pi$ such that $i\in S$. Moreover, $\mathcal{P}$ is the set of all
possible coalition partitions over $N$. In its partition form, a coalition
formation game is defined on the set $N$ by associating a gain $u(S|\Pi)$ to
each subset of any partition $\Pi$ of $N$. The gain of a set is independent of
the other coalitions, and therefore, $u(S|\Pi)=u(S)$. The games of this form
are more restrictive but present interesting properties to reach a stability.
Practically speaking, this assumption means that the gain of a group is
independent of the other players outside the group. Hedonic games fall into
this category with an additional assumption:

######  Definition .

A coalition formation game is hedonic if

  * •

_the gain of any player depends solely on the members of the coalition to
which the player belongs_ , and

  * •

_the coalitions arise as a result of the preferences of the players over their
possible coalitions’ set_.

###  3.1. Preference Relation

The preference relation of a player can be defined over a _preference
function_. We consider the case where the preference relation is chosen to be
the gain allocated to the player in a coalition. Thus, player $i$ prefers the
coalition $S$ to $T$ iff,

$\phi_{i}^{S}\geq\phi_{i}^{T}\Leftrightarrow S\succeq_{i}T.$ (11)

###  3.2. The Nash Stability

The stability concepts for a hedonic game are various. In the literature, a
hedonic game could be individually stable, Nash stable, core stable, strict
core stable, Pareto optimal, strong Nash stable, or, strict strong Nash
stable. We refer to Aziz and Brandl (2012) for a thorough definition of these
different stability concepts. In this paper, we are only interested in the
Nash stability because the players do not cooperate to take their decisions
jointly.

######  Definition  (Nash Stability).

A partition of players is Nash-stable whenever no player has incentive to
unilaterally change its coalition to another coalition in the partition which
can be mathematically formulated as follows: partition $\Pi^{\text{NS}}$ is
said to be Nash-stable if no player can benefit from moving from his coalition
$S_{\Pi^{\text{NS}}}(i)$ to another existing coalition $T\in\Pi^{\text{NS}}$,
i.e.:

$S_{\Pi^{\text{NS}}}(i)\succeq_{i}T\cup i,\quad\forall
T\in\Pi^{\text{NS}}\cup\emptyset;\forall i\in N.$ (12)

which can be similarly defined over preference function as follows:

$\phi_{i}^{S_{\Pi^{\text{NS}}}(i)}\geq\phi_{i}^{T\cup i},\quad\forall
T\in\Pi^{\text{NS}}\cup\emptyset;\forall i\in N.$ (13)

Nash-stable partitions are immune to individual movements even when a player
who wants to change does not need permission to join or leave an existing
coalition Bogomonlaia and Jackson (2002).

######  Remark 3.0.

Stability concepts being immune to individual deviation are _Nash stability,
individual stability, contractual individual stability_. Nash stability is the
strongest within above. The notion of _core stability_ has been used already
in some models where immunity to coalition deviation is required Hajduková
(2006).

######  Remark 3.0.

In Barber and Gerber (2007), the authors propose some set of axioms which are
non-emptiness, symmetry pareto optimality, self-consistency; and they analyze
the existence of any stability concept that can satisfy these axioms. It is
proven that for any game $|N|>2$, there does not exist any solution which
satisfies these axioms.

###  3.3. Aggregated Learning Model Parameters

When a stable partition exists, then this means that all the players (agents)
are agreed to participate to federation. As a result of this, MAE utilizes the
following aggregation of learning model parameters:

$\bm{\theta}^{F}=w\bm{\theta}_{\text{MAE}}+(1-w)\frac{\sum_{i\in
N}x_{i}m_{i}\bm{\theta}_{i}}{\sum_{i\in N}x_{i}m_{i}}$ (14)

where $0\leq w\leq 1$ is a weighting parameter showing how much MAE favors the
aggregated learning model parameters of agents (players),
$\bm{\theta}_{\text{MAE}}$ shows the learning parameters of MAE’s local model.
In summary, we have the following procedure:

while Nash-stable partition $\Pi^{\text{NS}}$ exists

  1. 1.

Player (agent) $i$ sends information of $\bm{\theta}_{i}$, for all $i\in N$

  2. 2.

MAE calculates aggregated learning model parameters $\bm{\theta}^{F}$

end

Given $\bm{\theta}^{F}$, the expected value of loss function in federation can
be calculated as following:

$\displaystyle\mathbb{E}_{\bm{x}}[\mathcal{L}(\bm{\theta}^{F})]$
$\displaystyle=\sum_{\bm{x}\in\mathcal{X}}\mathcal{L}(\bm{\theta}^{F};\bm{x})\mathbb{P}[\bm{x}]$
$\displaystyle\geq\mathcal{L}(\mathbb{E}_{\bm{x}}[\bm{\theta}^{F};\bm{x}])\qquad(\text{Jensen's
inequality})$ (15)

where

$\mathbb{E}_{\bm{x}}[\bm{\theta}^{F};\bm{x}]=w\bm{\theta}_{\text{MAE}}+(1-w)\sum_{\bm{x}\in\mathcal{X}}\frac{\sum_{i\in
N}x_{i}m_{i}\bm{\theta}_{i}}{\sum_{i\in N}x_{i}m_{i}}\mathbb{P}[\bm{x}].$ (16)

Note that calculating $\mathbb{E}_{\bm{x}}[\mathcal{L}(\bm{\theta}^{F})]$ may
be more difficult than $\mathbb{E}_{\bm{x}}[\bm{\theta}^{F};\bm{x}]$.
Therefore, it can be also an option to define the gain of a cluster using
$\mathbb{E}_{\bm{x}}[\bm{\theta}^{F};\bm{x}]$ in eq. (7).

##  4\. The Nash-stable Set

As the gain $u$ associated with all possible coalitions are known, we are
interested in finding a gain distribution to ensure Nash stability. We thus
define an allocation method $\bm{\phi}\in\mathbb{R}^{\kappa}$ where
$\kappa=n2^{n-1}$ as following:

$\bm{\phi}=\\{\phi_{i}^{S}:\forall i\in S,\forall S\in 2^{N}\\}$ (17)

which directly sets up a preference profile. The set of all possible
allocation methods is denoted by $\mathcal{F}\subset\mathbb{R}^{\kappa}$. We
define the mapping $\mathsf{M}$, which for any allocation method $\bm{\phi}$,
it finds corresponding all possible Nash-stable partitions, i.e.
$\mathsf{M}(\bm{\phi})\subset\mathcal{P}$.

We define the Nash-stable set which includes all those allocation methods that
build the following set:

$\mathscr{N}_{\text{stable}}=\left\\{\bm{\phi}\in\mathbb{R}^{\kappa}:\exists\Pi\in\mathsf{M}(\bm{\phi})|S_{\Pi}(i)\succeq_{i}T\cup
i,\right.\\\ \left.\forall T\in\Pi\cup\emptyset;\forall i\in N\right\\}.$ (18)

Essentially, the Nash-stable set includes

> the family of hedonic games, each one having a different preference profile
> that derives from a different allocation method. Thus, before finding a
> Nash-stable partition, we need to find the hedonic game (i.e., an allocation
> method) for which a Nash-stable partition exists.

Let us define the set of constraints stemming from the preference function in
order to check if the Nash-stable set is non-empty. Due to the gain bound, for
any allocation method $\bm{\phi}$, we have

$\sum_{i\in S}(\pi_{i}+\phi_{i}^{S})\leq u(S),\quad\forall S\in 2^{N}$

called as budged balanced gain allocation which further can be given by

$\sum_{i\in
S}f\left(\tfrac{p_{i}}{\mathcal{L}(\bm{\theta}_{i})}\right)+\sum_{i\in
S}\phi_{i}^{S}\leq
f\left(\tfrac{1}{\mathbb{E}_{\bm{x}}[\mathcal{L}(\bm{\theta}^{S})]}\right)-c(S),\quad\forall
S\in 2^{N}.$ (19)

For simplicity, let us define marginal gain as following:

$\Delta_{\bm{\theta}}(S)=\begin{cases}f\left(\tfrac{1}{\mathbb{E}_{\bm{x}}[\mathcal{L}(\bm{\theta}^{S})]}\right)-c(S)-\sum_{i\in
S}f\left(\tfrac{p_{i}}{\mathcal{L}(\bm{\theta}_{i})}\right),&\forall S\in
2^{N}\setminus i,\\\ 0,&\forall i\in N.\end{cases}$ (20)

which results in the following constraints:

$\mathscr{C}_{\bm{\theta}}^{1}(\bm{\phi}):=\left\\{\sum_{i\in
S}\phi_{i}^{S}\leq\Delta_{\bm{\theta}}(S),\forall S\in 2^{N}\right\\}.$ (21)

which are the constraints that stem from budged balancedness. On the other
hand, for any $\bm{\phi}$, the constraints that ensure the Nash stability are
given by

$\mathscr{C}_{\bm{\theta}}^{2}(\bm{\phi}):=\left\\{\exists\Pi\in\mathsf{M}(\bm{\phi})\left|\phi_{i}^{S_{\Pi}(i)}\geq\phi_{i}^{T\cup
i},\forall T\in\Pi\cup\emptyset;\forall i\in N\right.\right\\},$ (22)

Based on these two constraints represented by
$\mathscr{C}_{\bm{\theta}}^{1}(\bm{\phi})$ and
$\mathscr{C}_{\bm{\theta}}^{2}(\bm{\phi})$, we can define the Nash-stable set.

$\mathscr{N}_{\text{stable}}(\bm{\theta})=\left\\{\bm{\phi}\in\mathbb{R}^{\kappa}:\mathscr{C}_{\bm{\theta}}^{1}(\bm{\phi})\mbox{
and }\mathscr{C}_{\bm{\theta}}^{2}(\bm{\phi})\right\\},$ (23)

Then, the non-emptiness of the Nash-stable set is crucial. The theorem below
states the necessary conditions about the non-emptiness of the Nash-stable
set:

The Nash-stable set can be non-empty.

###### Proof.

We can check if the Nash-stable set is non-empty by solving the following
optimization problem:

$\displaystyle\max_{\bm{\phi}}\sum_{S\in 2^{N}}\sum_{i\in S}\phi_{i}^{S}\mbox{
subject to }\mathscr{C}_{\bm{\theta}}^{1}(\bm{\phi})\mbox{ and
}\mathscr{C}_{\bm{\theta}}^{2}(\bm{\phi}).$

If there exists any feasible solution of this problem, then we conclude that
there is at least one allocation method which provides a Nash-stable
partition. ∎

However, searching in an exhaustive manner over the whole partitions is NP-
hard as the number of partitions grows according to the Bell number.
Typically, with only $10$ players, the number of partitions is as large as
$115,975$.

###  4.1. Superadditive Gain

If the gain function $u$ is superadditive, then it is trivial to check that
the marginal gain is also superadditive: $\Delta_{\bm{\theta}}(S\cup
T)\geq\Delta_{\bm{\theta}}(S)+\Delta_{\bm{\theta}}(T)$, for all possible $S$
and $T$ such that $S\cap T=\emptyset$. Due to eq. (19), we have

$\displaystyle\sum_{i\in S\cup T}\phi_{i}^{S\cup T}=\sum_{i\in
S}\phi_{i}^{S\cup T}+\sum_{i\in T}\phi_{i}^{S\cup
T}\leq\Delta_{\bm{\theta}}(S\cup T)$ $\displaystyle\sum_{i\in
S}\phi_{i}^{S}+\sum_{i\in
T}\phi_{i}^{T}\leq\Delta_{\bm{\theta}}(S)+\Delta_{\bm{\theta}}(T)$
$\displaystyle\Rightarrow\sum_{i\in S}\phi_{i}^{S\cup T}+\sum_{i\in
T}\phi_{i}^{S\cup T}\geq\sum_{i\in S}\phi_{i}^{S}+\sum_{i\in T}\phi_{i}^{T}.$

This result means that any player is better off in a larger coalition which
ultimately all players have the most gain in the grand coalition. This is
obvious from eq. (22) where for every player $i\in N$,
$\phi_{i}^{N}\geq\phi_{i}^{S}$ for all $S\in 2^{N}$.

###  4.2. Additively Separable and Symmetric Gain

Preferences of a player are _additively separable_ whenever the preference can
be stated with a function characterizing how a player prefers another player
in each coalition. This means that the player’s preference for a coalition is
based on individual preferences. This can be formalized as follows:

######  Definition .

The preferences of a player are said to be additively separable if there
exists a function $v_{i}:N\rightarrow\mathbb{R}$ such that

$\sum_{j\in S}v_{i}(j)\geq\sum_{j\in T}v_{i}(j)\Leftrightarrow
S\succeq_{i}T,\quad\forall S,T\in 2^{N}.$ (24)

$v_{i}(i)$ is normalized and set to $v_{i}(i)=0$. A profile of additively
separable preferences satisfies _symmetry_ if $v_{i}(j)=v_{j}(i)=v(i,j)$, for
all $i,j\in N$. The meaning of $v(i,j)$ is the mutual gain of player $i$ and
$j$ when they are in the same coalition. Let $\mathcal{V}(S)$ be the all
possible bipartite coalitions which can occur in coalition $S$ such that:

$\mathcal{V}(S):=\\{(i,j)\in S:j>i\\},\quad|S|\geq 2.$

We then define ${\bf v}\in\mathbb{R}^{|\mathcal{V}(N)|}$ which shall serve as
an allocation method to generate additively separable and symmetric
preferences:

${\bf v}=\left\\{v(i,j):\forall(i,j)\in\mathcal{V}(N)\right\\}$

and mapping $\mathsf{M}$ shall find all possible Nash-stable partitions,, i.e.
$\mathsf{M}({\bf v})\subset\mathcal{P}$. The constraints that define the Nash-
stable set are then defined over ${\bf v}$:

$\mathscr{C}_{\bm{\theta}}^{1}(\bm{\phi})\rightarrow\mathscr{C}_{\bm{\theta}}^{1}({\bf
v})\mbox{ and
}\mathscr{C}_{\bm{\theta}}^{2}(\bm{\phi})\rightarrow\mathscr{C}_{\bm{\theta}}^{2}({\bf
v})$

Further, note that the gain that player $i$ has in coalition $S$ is given by

$\displaystyle\pi_{i}+\phi_{i}^{S}=f\left(\tfrac{1}{\mathcal{L}(\bm{\theta}_{i})}\right)+\sum_{j\in
S}v(i,j)$ $\displaystyle\Rightarrow\phi_{i}^{S}=\sum_{j\in S}v(i,j)$ (25)

On the other hand, due to the symmetry property of mutual gain, we have the
following:

$\sum_{i,j\in S}v(i,j)=2\sum_{(i,j)\in\mathcal{V}(S)}v(i,j).$

For example, if $S=(1,2,3)$, then $\sum_{i,j\in
S}v(i,j)=2[v(1,2)+v(1,3)+v(2,3)]$.

Additively separable and symmetric preferences always admit a Nash-stable
partition. Therefore, constraints in $\mathscr{C}^{2}_{\bm{\theta}}({\bf v})$
are always satisfied Hajduková (2006).

Based on this theorem, we only need to satisfy the constraints given by
$\mathscr{C}_{\bm{\theta}}^{1}({\bf v})$. Thus, we define the Nash-stable set
which generates additively separable and symmetric preferences
$\mathscr{N}_{\text{stable}}^{\text{A}}(\bm{\theta})\subset\mathscr{N}_{\text{stable}}(\bm{\theta})$
as following:

$\mathscr{N}_{\text{stable}}^{\text{A}}(\bm{\theta})=\Bigg{\\{}{\bf
v}\in\mathbb{R}^{|\mathcal{V}(N)|}:\underbrace{\sum_{(i,j)\in\mathcal{V}(S)}v(i,j)\leq\tfrac{\Delta_{\bm{\theta}}(S)}{2},\forall
S\in 2^{N}}_{\mathscr{C}^{1}_{\bm{\theta}}({\bf v})}\Bigg{\\}}$ (26)

Finding the values of $v(i,j)$ in eq. (26) satisfying
$\mathscr{C}_{\bm{\theta}}^{1}({\bf v})$ conditions can be done
straightforward. However, we propose to formulate as an optimization problem
for finding the values of $v(i,j)$. A feasible solution of the following
linear program guarantees the non-emptiness of
$\mathscr{N}_{\text{stable}}^{\text{A}}(\bm{\theta})$:

$\displaystyle\max_{{\bf v}}\sum_{(i,j)\in\mathcal{V}(N)}v(i,j)\mbox{ subject
to }$
$\displaystyle\sum_{(i,j)\in\mathcal{V}(S)}v(i,j)\leq\tfrac{\Delta_{\bm{\theta}}(S)}{2},\quad\forall
S\in 2^{N},$ (27)

where note that any feasible solution ${\bf v}^{*}$ is upper bounded by
$\sum_{(i,j)\in\mathcal{V}(N)}v^{*}(i,j)\leq{\Delta_{\bm{\theta}}(N)}/{2}$.
Furthermore, the coalition partition that stems from ${\bf v}^{*}$ is given by
$\Pi^{\text{NS}}\in\mathsf{M}({\bf v}^{*})$ which is Nash-stable.

##  5\. Decentralized Clustering

In this section, we study finding a Nash-stable partition in a decentralized
setting which corresponds to finding stable decentralized clustering. We, in
fact, model the problem of finding a Nash-stable partition as a non-
cooperative game.

A hedonic coalition formation game is equivalent to a non-cooperative game.
Denote as $\Sigma$ the set of strategies. We assume that the number of
strategies is equal to the number of players, i.e. $|\Sigma|=n$. This is
sufficient to represent all possible choices. Indeed, the players that select
the same strategy are interpreted as a coalition. For example, if every player
chooses different strategies, then this corresponds to the coalition partition
comprised of singletons.

Consider the best-reply dynamics where in a particular step, only one player
chooses its best strategy. A strategy tuple is represented as
$\bm{\sigma}=\\{\sigma_{1},\sigma_{2},\ldots,\sigma_{n}\\}$, where
$\sigma_{i}\in\Sigma$ is the strategy of player $i$. In every step, only one
dimension is changed in $\bm{\sigma}$. We further define

$\displaystyle S_{\bm{\sigma}}(i)=\\{j\in N:\sigma_{i}=\sigma_{j}\\}$ (28)
$\displaystyle\Pi(\bm{\sigma})=\\{S_{\bm{\sigma}}(i),\forall i\in N\\}$ (29)

the set of players that share the same strategy with player $i$ and partition
of players with respect to strategy tuple $\bm{\sigma}$. Thus, note that
$\cup_{i\in N}S_{\bm{\sigma}}(i)=N$ for each step. The gain of player $i$ in
case of strategy tuple $\bm{\sigma}$ is represented by $\phi_{i}(\bm{\sigma})$
which verifies the following relation:

$\phi_{i}(\bm{\sigma})\geq\phi_{i}(\bm{\sigma}^{\prime})\Leftrightarrow
S_{\bm{\sigma}}(i)\succeq_{i}S_{\bm{\sigma}^{\prime}}(i),$ (30)

Any sequence of strategy tuple in which each strategy tuple differs from the
preceding one in only one coordinate is called a path, and a unique deviator
in each step strictly increases the gain he receives is an improvement path.
Obviously, any maximal improvement path which is an improvement path that can
not be extended is terminated by stability.

###  5.1. Equilibrium Analysis

The Nash equilibrium is defined as following:

$\sigma_{i}^{\text{NE}}\in\arg\max_{\sigma_{i}\in\Sigma}\phi_{i}(\sigma_{i},\sigma_{-i}),\quad\forall
i\in N.$ (31)

essentially corresponding to a Nash-stable partition in the original hedonic
game, which is given by

$\displaystyle S_{\bm{\sigma}^{\text{NE}}}(i)=\\{j\in
N:\sigma^{\text{NE}}_{i}=\sigma_{j}\\},\quad\forall i\in N$
$\displaystyle\Pi^{\text{NE}}=\\{S_{\bm{\sigma}^{\text{NE}}}(i),\forall i\in
N\\}.$ (32)

In the sequel, we prove that the additively separable and symmetric gains
result in a potential game where all the players have incentive to change
their strategy according to a single global function called as potential
function.

Any additively separable and symmetric gain results in a potential game with
potential function:

$P_{{\bf
v}}(\bm{\sigma})=\sum_{S\in\Pi(\bm{\sigma})}\sum_{(i,j)\in\mathcal{V}(S)}v(i,j).$
(33)

###### Proof.

A non-cooperative game is a potential game whenever there exists a function
$P_{{\bf v}}$ such that:

$P_{{\bf v}}(\sigma_{i},\sigma_{-i})-P_{{\bf
v}}(\sigma^{\prime}_{i},\sigma_{-i})=\phi(\sigma_{i},\sigma_{-i})-\phi(\sigma^{\prime}_{i},\sigma_{-i})$

where $(\sigma_{i},\sigma_{-i})=\bm{\sigma}$ and $\sigma_{-i}$ shows the
strategies of the players other than $i$. This means that when player $i$
switches from strategy $\sigma_{i}$ to $\sigma^{\prime}_{i}$ the difference of
its gain can be given by the difference of a function $P$. We choose the
following potential function:

$P_{{\bf
v}}(\bm{\sigma})=\sum_{S\in\Pi(\sigma)}\sum_{(i,j)\in\mathcal{V}(S)}v(i,j)$
(34)

Let us denote as $i\in S$ and $i\not\in S^{\prime}$ the coalitions when player
$i$ switches from strategy $\sigma_{i}$ to $\sigma^{\prime}_{i}$,
respectively. Potential function is given as following before and after
switching

$\displaystyle P_{{\bf
v}}(\sigma_{i},\sigma_{-i})=\sum_{(i,j)\in\mathcal{V}(S)}v(i,j)+\sum_{(k,j)\in\mathcal{V}(S^{\prime})}v(k,j)$
$\displaystyle+\sum_{T\in\Pi(\bm{\sigma})\setminus\\{S,S^{\prime}\\}}\sum_{(k,j)\in\mathcal{V}(T)}v(k,j)$
$\displaystyle P_{{\bf
v}}(\sigma^{\prime}_{i},\sigma_{-i})=\sum_{(k,j)\in\mathcal{V}(S\setminus
i)}v(k,j)+\sum_{(k,j)\in\mathcal{V}(S^{\prime}\cup i)}v(k,j)$
$\displaystyle+\sum_{T\in\Pi(\sigma)\setminus\\{S,S^{\prime}\\}}\sum_{(k,j)\in\mathcal{V}(T)}v(k,j)$

where note that we have $S\rightarrow S\setminus i$ and $S^{\prime}\rightarrow
S^{\prime}\cup i$ after switching. Thus, we have

$\displaystyle P_{{\bf v}}(\sigma_{i},\sigma_{-i})-P_{{\bf
v}}(\sigma^{\prime}_{i},\sigma_{-i})=$
$\displaystyle\sum_{(i,j)\in\mathcal{V}(S)}v(i,j)+\sum_{(k,j)\in\mathcal{V}(S^{\prime})}v(k,j)$
$\displaystyle-\sum_{(k,j)\in\mathcal{V}(S\setminus
i)}v(k,j)-\sum_{(k,j)\in\mathcal{V}(S^{\prime}\cup i)}v(k,j)=$
$\displaystyle\sum_{j\in S}v(i,j)-\sum_{j\in S^{\prime}\cup i}v(i,j)$

On the other hand, the gain shift before and after strategy switch is given by

$\displaystyle\phi(\sigma_{i},\sigma_{-i})-\phi(\sigma^{\prime}_{i},\sigma_{-i})=\sum_{j\in
S}v(i,j)-\sum_{j\in S^{\prime}\cup i}v(i,j)$

which concludes the proof that $P_{{\bf v}}(\sigma_{i},\sigma_{-i})-P_{{\bf
v}}(\sigma^{\prime}_{i},\sigma_{-i})=\phi(\sigma_{i},\sigma_{-i})-\phi(\sigma^{\prime}_{i},\sigma_{-i})$.
∎

In a potential game, a Nash equilibrium shall result in an optimum in
potential $P_{{\bf v}}$. Therefore,
$\bm{\sigma}^{*}\in\arg\max_{\bm{\sigma}}P_{{\bf v}}(\bm{\sigma})$ corresponds
to a coalition partition $\Pi(\sigma^{*})\in\mathsf{M}({\bf v})$ which is
Nash-stable.

##  6\. Conclusions

We analyzed stable clustering problem in federated learning setting. Clusters
are made up of the agents contributing to federated learning. We considered
that every agent is better off when switching from one cluster to another one.
We modeled the decisions of agents in the framework hedonic games which is a
widely used cooperative game model for this type of problems. A fundamental
question in hedonic games is to analyze the conditions how stable coalition
partitions can occur. We studied the existence of stable coalition partitions
by introducing the Nash-stable set, and analyzed the existence of
decentralized coalition partitions.

As future work, it may be interesting to do stability analysis for different
stability notions, to study other types of preference profiles ensuring Nash
stability. On the other hand, it is essential to do experiments with real data
and specific learning models as well as realistic gain and communication cost
functions.

## References

  * (1)
  * Aziz and Brandl (2012) H. Aziz and F. Brandl. 2012\.  Existence of stability in hedonic coalition formation games. In _Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2012)_.
  * Barber and Gerber (2007) S. Barber and A. Gerber. 2007.  A note on the impossibility of a satisfactory concept of stability for coalition formation games.  _Economics Letters_ 95 (2007), 85–90.
  * Bogomonlaia and Jackson (2002) A. Bogomonlaia and M. Jackson. 2002.  The stability of hedonic coalition structures.  _Games and Economic Behavior_ 38 (jan 2002), 201–230.
  * by: Peter Kairouz and McMahan (2021) Edited by: Peter Kairouz and H. Brendan McMahan. 2021.  Advances and Open Problems in Federated Learning.  _Foundations and Trends in Machine Learning_ 14, 1 (2021), –.  https://doi.org/10.1561/2200000083
  * Ding et al. (2020) Ningning Ding, Zhixuan Fang, and Jianwei Huang. 2020\.  Incentive Mechanism Design for Federated Learning with Multi-Dimensional Private Information. In _2020 18th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOPT)_. 1–8.
  * Donahue and J. Kleinberg (2021) K. Donahue and booktitle=AAAI 2021 J. Kleinberg. 2021\.  Model-sharing Games: Analyzing Federated Learning Under Voluntary Participation.
  * Elgabli et al. (2020) Anis Elgabli, Jihong Park, Amrit S Bedi, Mehdi Bennis, and Vaneet Aggarwal. 2020.  GADMM: fast and communication efficient framework for distributed machine learning.  _Journal of Machine Learning Research_ 21, 76 (2020), 1–39.
  * Hajduková (2006) J. Hajduková. 2006\.  Coalition formation games: A survey.  _International Game Theory Review_ 8, 4 (2006), 613–641.
  * Hosseinalipour et al. (2020) S. Hosseinalipour, C. G. Brinton, V. Aggarwal, H. Dai, and M. Chiang. 2020.  From Federated to Fog Learning: Distributed Machine Learning over Heterogeneous Wireless Networks.  _IEEE Communications Magazine_ 58, 12 (2020), 41–47.  https://doi.org/10.1109/MCOM.001.2000410
  * Khan et al. (2020) L. U. Khan, S. R. Pandey, N. H. Tran, W. Saad, Z. Han, M. N. H. Nguyen, and C. S. Hong. 2020.  Federated Learning for Edge Networks: Resource Optimization and Incentive Mechanism.  _IEEE Communications Magazine_ 58, 10 (2020), 88–93.  https://doi.org/10.1109/MCOM.001.1900649
  * Kim (2020) Sungwook Kim. 2020\.  Incentive Design and Differential Privacy Based Federated Learning: A Mechanism Design Perspective.  _IEEE Access_ 8 (2020), 187317–187325.  https://doi.org/10.1109/ACCESS.2020.3030888
  * Le et al. (2021) Tra Huong Thi Le, Nguyen H. Tran, Yan Kyaw Tun, Minh N. H. Nguyen, Shashi Raj Pandey, Zhu Han, and Choong Seon Hong. 2021\.  An Incentive Mechanism for Federated Learning in Wireless Cellular network: An Auction Approach.  _IEEE Transactions on Wireless Communications_ (2021), 1–1.  https://doi.org/10.1109/TWC.2021.3062708
  * Li et al. (2020) T. Li, A. K. Sahu, A. Talwalkar, and V. Smith. 2020\.  Federated Learning: Challenges, Methods, and Future Directions.  _IEEE Signal Processing Magazine_ 37, 3 (2020), 50–60.  https://doi.org/10.1109/MSP.2020.2975749
  * Lim et al. (2020) Wei Yang Bryan Lim, Zehui Xiong, Chunyan Miao, Dusit Niyato, Qiang Yang, Cyril Leung, and H. Vincent Poor. 2020.  Hierarchical Incentive Mechanism Design for Federated Machine Learning in Mobile Networks.  _IEEE Internet of Things Journal_ 7, 10 (2020), 9575–9588.  https://doi.org/10.1109/JIOT.2020.2985694
  * Samarakoon et al. (2018) S. Samarakoon, M. Bennis, W. Saad, and M. Debbah. 2018\.  Federated Learning for Ultra-Reliable Low-Latency V2V Communications. In _2018 IEEE Global Communications Conference (GLOBECOM)_. 1–7.  https://doi.org/10.1109/GLOCOM.2018.8647927
  * Sarikaya and Ercetin (2020) Yunus Sarikaya and Ozgur Ercetin. 2020.  Motivating Workers in Federated Learning: A Stackelberg Game Perspective.  _IEEE Networking Letters_ 2, 1 (2020), 23–27.  https://doi.org/10.1109/LNET.2019.2947144
  * Yang et al. (2020) K. Yang, T. Jiang, Y. Shi, and Z. Ding. 2020\.  Federated Learning via Over-the-Air Computation.  _IEEE Transactions on Wireless Communications_ 19, 3 (2020), 2022–2035.  https://doi.org/10.1109/TWC.2019.2961673
  * Zhan and Zhang (2020) Yufeng Zhan and Jiang Zhang. 2020.  An Incentive Mechanism Design for Efficient Edge Learning by Deep Reinforcement Learning Approach. In _IEEE INFOCOM 2020 - IEEE Conference on Computer Communications_. 2489–2498.  https://doi.org/10.1109/INFOCOM41043.2020.9155268
  * Zhan et al. (5555) Y. Zhan, J. Zhang, Z. Hong, L. Wu, P. Li, and S. Guo. 5555.  A Survey of Incentive Mechanism Design for Federated Learning.  _IEEE Transactions on Emerging Topics in Computing_ 1 (mar 5555), 1–1.  https://doi.org/10.1109/TETC.2021.3063517
  * Zheng et al. (2020) S. Zheng, C. Shen, and X. Chen. 2020.  Design and Analysis of Uplink and Downlink Communications for Federated Learning.  _IEEE Journal on Selected Areas in Communications_ (2020), 1–1.  https://doi.org/10.1109/JSAC.2020.3041388


$\set{u_{\varepsilon}-v_{\varepsilon}}$ converges to $0$ strongly in
$L^{q}(\Omega;\mathbb{R}^{N})$ for all $q\in[1,p)$. Therefore,

$\lim_{\varepsilon\to
0}\int_{\Omega_{1,\varepsilon}\setminus\tilde{\Omega}_{1,\varepsilon}}\lvert
v_{\varepsilon}(x)\rvert^{p}\mathrm{d}x=0.$

Let now $\set{\varepsilon_{n}}$ be such that

$\limsup_{\varepsilon\to
0}\tilde{\mathscr{F}}_{1,\varepsilon}(v_{\varepsilon})=\lim_{n\to+\infty}\tilde{\mathscr{F}}_{1,\varepsilon_{n}}(v_{\varepsilon_{n}}).$

By Lemma 4.4, we obtain the desired limsup inequality:

$\limsup_{\varepsilon\to
0}\mathscr{F}_{1,\varepsilon}(v_{\varepsilon})=\limsup_{\varepsilon\to
0}\tilde{\mathscr{F}}_{1,\varepsilon}(v_{\varepsilon})=\lim_{n\to+\infty}\tilde{\mathscr{F}}_{1,\varepsilon_{n}}(v_{\varepsilon_{n}})\\\
\leq\lim_{n\to+\infty}\tilde{\mathscr{F}}_{1,\varepsilon_{n}}(u_{\varepsilon_{n}})\leq\limsup_{\varepsilon\to
0}\tilde{\mathscr{F}}_{1,\varepsilon}(u_{\varepsilon})\leq\mathscr{F}_{1}(u).$

∎

##  7\. Admissible differential constraints

In what follows we deepen our analysis of constant rank operators. We
investigate the existence of Sobolev potentials for $\mathscr{A}$-free maps
and of extension operators on perforated domains. In particular, we prove
Theorems 2.8 and 2.9.

In contrast to the previous sections, here we take into account also
differential operators of order greater than $1$: we treat the broader class
of linear, $k$-th order, homogeneous differential operators with constant
coefficients. To fix the notation, given $k,N,M\in\mathbb{N}\setminus\set{0}$,
we consider linear maps $A^{(i)}\colon\mathbb{R}^{N}\to\mathbb{R}^{M}$ for all
$d$-dimensional multi-indices $i$ with $\lvert i\rvert=k$ and we focus on the
operators whose action on a function $u\colon\mathbb{R}^{N}\to\mathbb{R}^{M}$
is given by

$\mathscr{A}u\coloneqq\sum_{\lvert i\rvert=k}A^{(i)}\partial_{i}u.$

Recall that if $i\coloneqq(i_{1},\dots,i_{d})\in\mathbb{N}^{d}$ is a multi-
index, then

$\partial_{i}u(x)\coloneqq\frac{\partial^{\lvert
i\rvert}u}{\partial_{i_{1}}x_{1}\cdots\partial_{i_{d}}x_{d}}(x).$

We keep in place the constant rank condition, which currently reads: there
exists $r\in\mathbb{N}$ such that the rank of $\mathbb{A}[\omega]$ equals $r$
for all $\omega\in\mathbb{R}^{d}\setminus\set{0}$, where

$\mathbb{A}[\omega]\coloneqq\sum_{\lvert i\rvert=k}\omega^{i}A^{(i)}$

is the symbol of $\mathscr{A}$ and
$\omega^{i}=\Pi_{j=1}^{d}\omega_{j}^{i_{j}}$ if $i=(i_{1},\dots,i_{d})$ is a
multi-index. Note that when $k=1$ we recover the setting of Subsection 2.2. As
before, we say that a map $u$ is $\mathscr{A}$-free in $\Omega$ if
$\mathscr{A}u=0$ in $W^{-k,p}(\Omega;\mathbb{R}^{M})$.

###  7.1. Existence of potentials

This subsection is devoted to the proof of Theorem 2.8. Loosely speaking, our
goal is to prove that, given an operator $\mathscr{A}$ of constant rank, there
exists a second differential operator $\mathscr{B}$ such that any
$\mathscr{A}$-free map $u\in L^{p}$ satisfies $u=\mathscr{B}w$ for a suitable
Sobolev function $w$. When such a relation holds, we will say for brevity that
$w$ is a potential for $u$ and that $\mathscr{B}$ is a potential for
$\mathscr{A}$. We are able to prove existence of potentials for those
functions that are $\mathscr{A}$-free on a certain class of subsets of
$\mathbb{R}^{d}$, which we introduce in the next definition.

######  Definition 7.1.

Let $\mathscr{A}$ be a homogeneous operator of order $k$. An open set
$\Omega\subset\mathbb{R}^{d}$ is an $\mathscr{A}$-extension domain if there
exist $\mathsf{E}_{\mathscr{A}}\colon L^{p}(\Omega;\mathbb{R}^{N})\to
L^{p}(\mathbb{R}^{d};\mathbb{R}^{N})$ and $c>0$ such that the following holds:
for all $u\in L^{p}(\Omega;\mathbb{R}^{N})$ such that $\mathscr{A}u=0$ in
$W^{-k,p}(\Omega;\mathbb{R}^{M})$, we have

  1. (1)

${\mathsf{E}}_{\mathscr{A}}u=u$ a.e. in $\Omega$,

  2. (2)

$\lVert\mathsf{E}_{\mathscr{A}}u\|_{L^{p}(\mathbb{R}^{d};\mathbb{R}^{N})}\leq
c\lVert u\|_{L^{p}(\Omega;\mathbb{R}^{N})}$, and

  3. (3)

$\mathscr{A}(\mathsf{E}_{\mathscr{A}}u)=0$ on $\mathbb{R}^{d}$.

Analogous definitions concerning extensions of sequences that are
(asimptotically) $\mathscr{A}$-free are found in [44, Definition 1.4] and [43,
Lemma 2.8] (i.e. Lemma 3.3 above), while the reader is referred to Section 7.2
below for a more detailed discussion on extension problems. We also refer to
[53] for a related study in the stochastic setting. It is important to notice
that the property of being an $\mathscr{A}$-extension domain carries some
topological consequences.

######  Remark 7.2 (On the topology of $\mathscr{A}$-extension domains).

The requirements of Definition 7.1 may act as implicit restrictions on the
topology of the set $\Omega$, according to the specific choice of
$\mathscr{A}$. Let us consider, for instance, the case in which $d=3$,
$\mathscr{A}$=curl, and $\Omega=\mathbb{R}^{3}\setminus\mathbb{R}e_{3}$,
$\set{e_{1},e_{2},e_{3}}$ being the canonical basis in $\mathbb{R}^{3}$. We
assume by contradiction that $\Omega$ is an $\mathscr{A}$-extension domain.
Then, if for every $x=(x_{1},x_{2},x_{3})\in\Omega$ we let

$u(x_{1},x_{2},x_{3})\coloneqq\left(-\frac{x_{2}}{x_{1}^{2}+x_{2}^{2}},\frac{x_{1}}{x_{1}^{2}+x_{2}^{2}},0\right),$

we find that ${\rm curl}\,u=0$ almost everywhere in $\Omega$, whence ${\rm
curl}\,(\mathsf{E}_{\mathscr{A}}u)=0$ in $\mathbb{R}^{3}$, if
$\mathsf{E}_{\mathscr{A}}$ is the extension operator in Definition 7.1 for
$\mathscr{A}=\mathrm{curl}$. This fact, in turn, yields a potential $w$ such
that $\mathsf{E}_{\mathscr{A}}u=\nabla w$ in $\mathbb{R}^{3}$ and, from the
requirement that $\mathsf{E}_{\mathscr{A}}u=u$ on $\Omega$, we conclude that
$u=\nabla w$ on $\Omega$. This leads to a contradiction, for the field $u$ is
not conservative.

For the proof of Theorem 2.8 we rely heavily on some recent contributions by
B. Raiţă and coauthors, who established existence of potentials for
$\mathscr{A}$-free smooth maps and Korn-type inequalities for constant rank
operators. Further related bibliographical comments are provided when we
discuss Propositions 7.4 and 7.5 below. Before dealing with the proof, we
pinpoint here that Theorem 2.8 constitutes a sufficient condition for
Assumption 1 to hold:

######  Corollary 7.3.

Assume that $\mathscr{A}$ is a first order operator satisfying the assumptions
of Theorem 2.8 and that the unit cube $Q$ is an $\mathscr{A}$-extension
domain. Then, for any open set $\Omega^{\prime}\subset\Omega$, the space
$U_{0}(\Omega^{\prime})$ in (2.5) is characterized as follows:

$U_{0}(\Omega^{\prime})=\Bigg{\\{}u\in
L^{p}(\Omega;L^{p}_{\mathrm{per}}(\mathbb{R}^{d};\mathbb{R}^{N})):u=0\text{ if
}y\in D_{1},\\\ \mathscr{A}_{y}u=0\text{ in
}W^{-1,p}(\mathbb{T}^{d};\mathbb{R}^{M})\text{ for a.e.
}x\in\Omega^{\prime},\text{ and }\int_{Q}u(x,y)\,\mathrm{d}y=0\text{ for a.e.
}x\in\Omega^{\prime}\Bigg{\\}}.$ (7.1)

###### Proof.

For the desired equality to hold, we just need to prove that

$U_{0}(\Omega^{\prime})\subset\Bigg{\\{}u\in
L^{p}(\Omega;L^{p}_{\mathrm{per}}(\mathbb{R}^{d};\mathbb{R}^{N})):u=0\text{ if
}y\in D_{1},\\\ \mathscr{A}_{y}u=0\text{ in
}W^{-1,p}(\mathbb{T}^{d};\mathbb{R}^{M})\text{ for a.e.
}x\in\Omega^{\prime},\text{ and }\int_{Q}u(x,y)\,\mathrm{d}y=0\text{ for a.e.
}x\in\Omega^{\prime}\Bigg{\\}}.$

Let us fix $u\in U_{0}(\Omega^{\prime})$. Theorem 2.8 grants that for a.e.
$x\in\Omega^{\prime}$ there exists $w_{x}\in
W^{\ell,p}_{\mathrm{per}}(\mathbb{R}^{d};\mathbb{R}^{M})$ such that
$u(x,\cdot)=\mathscr{B}_{y}w_{x}$ a.e. in $Q$. To the aim of defining a
measurable selection of the maps $\set{w_{x}}_{x\in\Omega^{\prime}}$, we
exploit Proposition 3.1.

We first observe that for every $u\in
L^{p}(\Omega;L^{p}_{\mathrm{per}}(\mathbb{R}^{d};\mathbb{R}^{N}))$ and
$x\in\Omega^{\prime}$ the set

$W(x)\coloneqq\Set{w\in
W^{\ell,p}_{\mathrm{per}}(\mathbb{R}^{d};\mathbb{R}^{M}):\mathscr{B}_{y}w(y)=u(x,y)\text{
for a.e. }y\in\mathbb{R}^{d}}$

is either empty or a closed (and hence complete) subspace of
$W^{\ell,p}_{\mathrm{per}}(\mathbb{R}^{d};\mathbb{R}^{M})$. Besides, being
$x\mapsto u(x,\,\cdot\,)\in
L^{p}_{\mathrm{per}}(\mathbb{R}^{d};\mathbb{R}^{N})$ measurable, then for
every open set $O\subset
W^{\ell,p}_{\mathrm{per}}(\mathbb{R}^{d};\mathbb{R}^{M})$, the set

$\Set{x\in\Omega^{\prime}:W(x)\cap O\neq\emptyset}$

is measurable as well. It follows that the multifunction $x\mapsto W(x)$
admits a measurable selection, which we denote by $w(x,\,\cdot\,)$.

Summing up, we recovered a measurable function $w$ from $\Omega^{\prime}$ to
$W^{\ell,p}_{\mathrm{per}}(\mathbb{R}^{d};\mathbb{R}^{M})$ with the property
that $u=\mathscr{B}_{y}w$ for almost every $x\in\Omega^{\prime}$ and
$y\in\mathbb{R}^{d}$. We conclude that

$\int_{Q}u(x,y)\,\mathrm{d}y=\sum_{\lvert
i\rvert=\ell}B^{(i)}\int_{Q}\partial_{y^{i}}w(x,y)\,\mathrm{d}y=0,$

where the latter inequality follows from the periodicity of $w$ in its second
variable. ∎

We devote the remainder of the section to the proof of Theorem 2.8 and to the
pertaining tools. We first highlight that B. Raiţă [66] has recently pointed
out that the kernel of the symbol of _any_ constant rank operator coincides
with the image of the symbol of a suitable operator $\mathscr{B}$, and that
the latter is actually a potential for $\mathscr{A}$ when tools from Fourier
analysis are applicable. Precisely, we have:

######  Proposition 7.4 (Theorem 1 and Lemma 2 in [66]).

Let $\mathscr{A}$ be a linear homogeneous differential operator on
$\mathbb{R}^{d}$ with constant coefficients. Then, $\mathscr{A}$ is of
constant rank if and only if there exists a linear homogeneous differential
operator $\mathscr{B}$ on $\mathbb{R}^{d}$ with constant coefficients such
that

$\ker\mathbb{A}[\omega]=\operatorname{im}\mathbb{B}[\omega]\quad\text{for all
}\omega\in\mathbb{R}^{d}\setminus\set{0},$ (7.2)

where $\mathbb{A}$ and $\mathbb{B}$ are the symbols of $\mathscr{A}$ and
$\mathscr{B}$, respectively.

Moreover, suppose that $\mathscr{A}$ and $\mathscr{B}$ are, respectively,
operators from $\mathbb{R}^{N}$ to $\mathbb{R}^{M}$ and from $\mathbb{R}^{M}$
to $\mathbb{R}^{N}$. If (7.2) holds, then, for all
$u\in\mathscr{S}(\mathbb{R}^{d};\mathbb{R}^{N})$ such that $\mathscr{A}u=0$,
there exists $w\in\mathscr{S}(\mathbb{R}^{d};\mathbb{R}^{M})$ such that
$u=\mathscr{B}w$.

Observe that if the operator $\mathscr{B}$ satisfies (7.2), then it is in turn
of constant rank; precisely, $\mathrm{rank}\,\mathbb{B}[\omega]=N-r$ if
$\mathrm{rank}\,\mathbb{A}[\omega]=r$ for all
$\omega\in\mathbb{R}^{d}\setminus\set{0}$. Proposition 7.4 builds a unified
framework that encompasses some well-studied special cases, such as the one of
the curl and of the divergence. Results in the same spirit had been previously
obtained by J. Van Schaftingen [75, Proposition 4.2] for elliptic operators,
which correspond to the subclass of operators with full rank.

A second relevant finding related to constant rank operators was obtained by
A. Guerra & B. Raiţă [50], who showed that this class is exactly the one in
which a sort of Korn inequality holds. To state their result, we need to
introduce the _projection_ $\mathsf{\Pi}_{\mathscr{A}}$ associated with the
operator $\mathscr{A}$. For $u\in\mathscr{S}(\mathbb{R}^{d};\mathbb{R}^{N})$,
it is defined as

$\mathsf{\Pi}_{\mathscr{A}}u(x)\coloneqq\big{(}\mathcal{F}^{-1}(\mathbb{P}_{\mathscr{A}}\mathcal{F}u)\big{)}(x),$
(7.3)

where $\mathcal{F}$ and $\mathcal{F}^{-1}$ are the Fourier transform and its
inverse (see (3.4)), and the map

$\mathbb{P}_{\mathscr{A}}\colon\mathbb{R}^{d}\setminus\set{0}\to\mathrm{Lin}(\mathbb{R}^{N};\mathbb{R}^{N})$

associates to each $\omega\in\mathbb{R}^{d}\setminus\set{0}$ the orthogonal
projection operator onto $\ker\mathbb{A}[\omega]$. Here and in the rest of the
paper, $\mathrm{Lin}(V;W)$ is the set of linear operators from the vector
space $V$ to the vector space $W$. We have:

######  Proposition 7.5 (Korn-type inequality for constant rank operators
[50]).

Let $p\in(1,\infty)$ and let $\mathscr{A}$ be a linear, $k$-th order,
homogeneous differential operator with constant coefficients. Then,
$\mathscr{A}$ is of constant rank if and only if there exists $c\coloneqq
c(d,p)$ such that

$\lVert\nabla^{k}(\phi-\mathsf{\Pi}_{\mathscr{A}}\phi)\|_{L^{p}(\mathbb{R}^{d};\mathbb{R}^{N\times
d^{k}})}\leq
c\lVert\mathscr{A}\phi\|_{L^{p}(\mathbb{R}^{d};\mathbb{R}^{M})}\quad\text{for
all }\phi\in C_{\mathrm{c}}^{\infty}(\mathbb{R}^{d};\mathbb{R}^{N}).$

For future use, we remark that the conclusion remains valid when
$\phi\in\mathscr{S}(\mathbb{R}^{d};\mathbb{R}^{N})$, as the Fourier analysis
on which the proof is based is still viable in this case, or even when
$\phi\in W^{k,p}(\mathbb{R}^{d};\mathbb{R}^{N})$, by approximation. The
sufficiency of the constant rank condition had been already observed in the
literature, see for instance the bibliography in [50] or the paper by D.
Gustafson [52], where a proof for first order operators is given.

To the purpose of constructing Sobolev potentials for $\mathscr{A}$-free
fields, we first need to extend the projection operator
$\mathsf{\Pi}_{\mathscr{A}}$ in (7.3) to nonsmooth maps. We invoke the
following result by T. Kato [54], which we present in a form due to F. Murat:

######  Lemma 7.6 (Lemma 3.7 in [62]).

Let $\mathscr{A}$ be a linear, $k$-th order, homogeneous differential operator
with constant coefficients and constant rank. Then, the operator
$\mathsf{\Pi}_{\mathscr{A}}$ in (7.3) can be extended to a bounded linear
operator from $L^{p}(\mathbb{R}^{d};\mathbb{R}^{N})$ to
$L^{p}(\mathbb{R}^{d};\mathbb{R}^{N})$.

In the proof of the lemma the constant rank assumption is fundamental. Indeed,
it ensures that the map $\omega\mapsto\mathbb{P}_{\mathscr{A}}[\omega]$
introduced above is analytic on $\mathbb{R}^{d}\setminus\set{0}$ (see [62]);
this, in combination with the $0$-homogeneity of $\mathbb{P}_{\mathscr{A}}$,
allows the use of S.G. Mikhlin’s Multipliers Theorem (cf. Corollary 3.10).

######  Remark 7.7 (Self-adjointness of the projection operator).

As a consequence of Parseval’s formula and of the self-adjointness of
$\mathbb{P}_{\mathscr{A}}$, by density there holds

$\int_{\mathbb{R}^{d}}\mathsf{\Pi}_{\mathscr{A}}u\cdot
v\,\mathrm{d}{x}=\int_{\mathbb{R}^{d}}u\cdot\mathsf{\Pi}_{\mathscr{A}}v\,\mathrm{d}{x}\quad\text{for
all }u,v\in L^{p}(\mathbb{R}^{d};\mathbb{R}^{N}).$ (7.4)

We next clarify why $\mathsf{\Pi}_{\mathscr{A}}$ is entitled to be named
projection: Lemma 7.9 below shows that for an $L^{p}$-function $u$ one has
that $\mathscr{A}(\mathsf{\Pi}_{\mathscr{A}}u)=0$, and that
$\mathsf{\Pi}_{\mathscr{A}}u=u$ if $\mathscr{A}u=0$. We premise the
instrumental notion of _Moore-Penrose generalized inverse_ $\Lambda^{\dagger}$
of a linear map $\Lambda$.

######  Lemma 7.8 (Properties of the generalized inverse [50, 20]).

Given the map $\Lambda\in\mathrm{Lin}(\mathbb{R}^{N};\mathbb{R}^{M})$, we let
$\Lambda^{\dagger}\in\mathrm{Lin}(\mathbb{R}^{M};\mathbb{R}^{N})$ be defined
as

$\Lambda^{\dagger}\coloneqq\left(\Lambda\lfloor_{(\ker\Lambda)^{\perp}}\right)^{-1}\circ\mathbb{P}_{\operatorname{im}\Lambda},$

where $(\ker\Lambda)^{\perp}=\operatorname{im}\Lambda^{\ast}$ is the
orthogonal complement of the kernel of $\Lambda$ and
$\mathbb{P}_{\operatorname{im}\Lambda}$ is the orthogonal projection on the
image of $\Lambda$. Then, the following hold:

  1. (1)

$\Lambda^{\dagger}$ is the unique element in
$\mathrm{Lin}(\mathbb{R}^{M};\mathbb{R}^{N})$ such that
$\Lambda^{\dagger}\circ\Lambda=\mathbb{P}_{\operatorname{im}\Lambda^{\ast}}$
and $\Lambda\circ\Lambda^{\dagger}=\mathbb{P}_{\operatorname{im}\Lambda}$.

  2. (2)

Let $\mathbb{A}\colon O\to\mathrm{Lin}(\mathbb{R}^{N};\mathbb{R}^{M})$ be a
smooth map on the open set $O\subset\mathbb{R}^{d}$. If
$\mathrm{rank}\,\mathbb{A}[\omega]$ is constant for all $\omega\in O$, then
the map $O\ni\omega\mapsto(\mathbb{A}[\omega])^{\dagger}$ is locally bounded
and smooth.

  3. (3)

If $\mathscr{A}$ is a linear, $k$-th order, homogeneous differential operator
with constant coefficients, then the map
$\omega\mapsto(\mathbb{A}[\omega])^{\dagger}$ is $(-k)$-homogeneous.

We can now characterize the properties of the projection
$\mathsf{\Pi}_{\mathscr{A}}$. Note that they are comparable to the ones
presented by I. Fonseca & S. Müller [46, Lemma 2.14] for the periodic setting.
We also refer to [58, Subsection 2.8] for an alternative projection operator
on the unit torus for which no null-average conditions are imposed.

######  Lemma 7.9.

Let $\mathscr{A}$ be a linear, $k$-th order, homogeneous differential operator
with constant coefficients and constant rank. For every $u\in
L^{p}(\mathbb{R}^{d};\mathbb{R}^{N})$, there holds:

  1. (1)

For all $\psi\in C_{c}^{1}(\mathbb{R}^{d};\mathbb{R}^{M})$, we have
$\mathsf{\Pi}_{\mathscr{A}}(\mathscr{A}^{\ast}\psi)=0$ and, as a consequence,
$\mathscr{A}(\mathsf{\Pi}_{\mathscr{A}}u)=0$.

  2. (2)

If $h=0$ and $u\in L^{p}(\mathbb{R}^{d};\mathbb{R}^{N})$, or if
$h=1,\dots,k-1$ and $u\in W^{h,p}(\mathbb{R}^{d};\mathbb{R}^{N})$, there
exists a constant $c\coloneqq c(p,h)>0$ such that

$\lVert\nabla^{h}(u-\mathsf{\Pi}_{\mathscr{A}}u)\|_{L^{p}(\mathbb{R}^{d};\mathbb{R}^{N\times
d^{h}})}\leq
c\lVert\mathscr{A}u\|_{W^{-(k-h),p}(\mathbb{R}^{d};\mathbb{R}^{N})}.$ (7.5)

In particular, when $\mathscr{A}u=0$ in $\mathbb{R}^{d}$, then
$\mathsf{\Pi}_{\mathscr{A}}u=u$ a.e.

###### Proof.

When $u\in\mathscr{S}(\mathbb{R}^{d};\mathbb{R}^{N})$, the facts that
$\mathscr{A}(\mathsf{\Pi}_{\mathscr{A}}u)=0$ and
$\mathsf{\Pi}_{\mathscr{A}}u=u$ if $\mathscr{A}u=0$ are simple consequences of
(7.3). To extend these properties to the case of a nonsmooth $u$, we regard
$\psi\in C_{c}^{1}(\Omega;\mathbb{R}^{M})$ as a Schwartz function on the whole
space and we find

$\mathsf{\Pi}_{\mathscr{A}}(\mathscr{A}^{\ast}\psi)=\mathcal{F}^{-1}\big{(}\mathbb{P}_{\mathscr{A}}(\mathbb{A}^{\ast}\mathcal{F}\psi)\big{)}=0,$

because the image of $\mathbb{A}^{\ast}[\omega]$ is orthogonal to
$\ker\mathbb{A}[\omega]$ for all $\omega\in\mathbb{R}^{d}$. It follows by
(7.4) that

$\int_{\mathbb{R}^{d}}\mathsf{\Pi}_{\mathscr{A}}u\cdot\mathscr{A}^{\ast}\psi\,\mathrm{d}{x}=\int_{\mathbb{R}^{d}}u\cdot\mathsf{\Pi}_{\mathscr{A}}\mathscr{A}^{\ast}\psi\,\mathrm{d}{x}=0$

and statement (1) holds.

We now turn to point (2). We argue for $h=0$ as the case $h>0$ is analogous.
We consider at first $u\in\mathscr{S}(\mathbb{R}^{d};\mathbb{R}^{N})$ and we
compute the Fourier transform of $u-\mathsf{\Pi}_{\mathscr{A}}u$. Setting
$\hat{u}=\mathcal{F}u$, we find

$\hat{u}[\omega]-\mathbb{P}_{\mathscr{A}}[\omega]\hat{u}[\omega]=\mathbb{P}_{\operatorname{im}\mathbb{A}[\omega]^{\ast}}\hat{u}[\omega]=\mathbb{A}[\omega]^{\dagger}\big{(}\mathbb{A}[\omega]\hat{u}[\omega]\big{)}\quad\text{for
all }\omega\in\mathbb{R}^{d},$

where in the latter inequality we exploited statement (1) in Lemma 7.8.

Since $\mathbb{A}$ is $k$-homogeneous and $\mathbb{A}^{\dagger}$ is
$(-k)$-homogeneous, we infer by Corollary 3.10 that
$\mathbb{A}^{\dagger}\mathbb{A}$ is an $L^{p}$-Fourier multiplier. Therefore,
the operator $\mathsf{T}$ defined for
$u\in\mathscr{S}(\mathbb{R}^{d};\mathbb{R}^{N})$ as
$\mathsf{T}u\coloneqq\mathcal{F}^{-1}(\hat{u}-\mathbb{P}_{\mathscr{A}}\hat{u})$
can be extended to a bounded linear operator from
$L^{p}(\mathbb{R}^{d};\mathbb{R}^{N})$ to
$L^{p}(\mathbb{R}^{d};\mathbb{R}^{N})$, which we still denote by $\mathsf{T}$.

For every $u\in\mathscr{S}(\mathbb{R}^{d};\mathbb{R}^{N})$ we write

$\displaystyle\mathcal{F}(\mathsf{T}u)[\omega]$
$\displaystyle=\mathbb{A}^{\dagger}[\omega]\big{(}\mathcal{F}(\mathscr{A}u)[\omega]\big{)}$
$\displaystyle=(1+\lvert\omega\rvert^{2})^{k/2}\mathbb{A}^{\dagger}[\omega]\big{(}(1+\lvert\omega\rvert^{2})^{-k/2}\mathcal{F}(\mathscr{A}u)[\omega]\big{)},$

whence, by the $(-k)$-homogeneity of $\mathscr{A}^{\dagger}$, Mikhlin’s
Multipliers Theorem yields

$\|\mathsf{T}u\|_{L^{p}(\Omega;\mathbb{R}^{N})}\leq
c\|(I-\Delta)^{-k/2}(\mathscr{A}u)\|_{L^{p}(\Omega;\mathbb{R}^{N})}.$

From the definition of $\mathsf{T}$ and the characterization of $W^{-k,p}$
recalled in Subsection 3.3, (7.5) follows for
$u\in\mathscr{S}(\mathbb{R}^{d};\mathbb{R}^{N})$. The general assertion is
then obtained by density. ∎

Eventually, we are able to establish the existence of potentials in a
nonsmooth setting and prove the first main result of this section. We will use
the following variant of Poincaré-Wirtinger’s inequality, which can be derived
as a corollary of Rellich-Kondrachov’s Theorem.

######  Lemma 7.10.

Let $\Omega\subset\mathbb{R}^{d}$ be a bounded, connected, open set with
Lipschitz boundary. There exists a constant $c>0$ such that for every $u\in
W^{\ell,p}(\Omega;\mathbb{R}^{N})$

$\lVert u-\mathsf{\Pi}_{\nabla^{\ell}}u\|_{L^{p}(\Omega;\mathbb{R}^{N})}\leq
c\lVert\nabla^{\ell}u\|_{L^{p}(\Omega;\mathbb{R}^{N\times d^{\ell}})},$ (7.6)

where $\mathsf{\Pi}_{\nabla^{\ell}}$ is the projection on the kernel of the
operator $\nabla^{\ell}$.

###### Proof of Theorem 2.8.

Let us fix $u\in L^{p}(\Omega;\mathbb{R}^{N})$ satisfying $\mathscr{A}u=0$ in
$W^{-k,p}(\Omega;\mathbb{R}^{M})$. Since we postulate that $\Omega$ is an
$\mathscr{A}$-extension domain, there exists an operator
$\mathsf{E}_{\mathscr{A}}\colon L^{p}(\Omega;\mathbb{R}^{N})\to
L^{p}(\mathbb{R}^{d};\mathbb{R}^{N})$ as in Definition 7.1. In particular, if
we let $\tilde{u}\coloneqq\mathsf{E}_{\mathscr{A}}u$, then $\tilde{u}$ is
$\mathscr{A}$-free on $\mathbb{R}^{d}$.

As a first step, we approximate $\tilde{u}$ by maps in the image of
$\mathscr{B}$. By the definition of the projection
$\mathsf{\Pi}_{\mathscr{A}}$, there exist a sequence
$\set{u_{k}}\subset\mathscr{S}(\mathbb{R}^{d};\mathbb{R}^{N})$ such that

$u_{k}\to\tilde{u}\quad\text{and}\quad\tilde{u}_{k}\coloneqq\mathsf{\Pi}_{\mathscr{A}}u_{k}\to\mathsf{\Pi}_{\mathscr{A}}\tilde{u}\quad\text{strongly
in }L^{p}(\mathbb{R}^{d};\mathbb{R}^{N}).$

By construction, the functions $\tilde{u}_{k}$ belong to
$\mathscr{S}(\mathbb{R}^{d};\mathbb{R}^{N})$ and, in view of Proposition 7.4,
we recover a sequence
$\set{w_{k}}\subset\mathscr{S}(\mathbb{R}^{d};\mathbb{R}^{N})$ such that
$\tilde{u}_{k}=\mathscr{B}w_{k}$. Therefore, recalling that
$\mathsf{\Pi}_{\mathscr{A}}\tilde{u}=\tilde{u}$ because $\tilde{u}$ is
$\mathscr{A}$-free, we deduce

$\mathscr{B}w_{k}\to\tilde{u}\quad\text{strongly in
}L^{p}(\mathbb{R}^{d};\mathbb{R}^{N}).$ (7.7)

Next, we proceed by applying Proposition 7.5: since $\mathscr{B}$ has constant
rank,

$\left\|\nabla^{\ell}\big{(}w_{k}-\mathsf{\Pi}_{\mathscr{B}}w_{k}\big{)}\right\|_{L^{p}(\mathbb{R}^{d};\mathbb{R}^{M})}\leq
c\lVert\tilde{u}_{k}\|_{L^{p}(\mathbb{R}^{d};\mathbb{R}^{N})},$

where $\ell$ is the order of $\mathscr{B}$. Note that the right-hand side is
uniformly bounded in $k$ because $\set{\tilde{u}_{k}}$ is convergent in
$L^{p}(\Omega;\mathbb{R}^{N})$ by (7.7). As a consequence, inequality (7.6)
yields a function $w\in W^{\ell,p}(\Omega;\mathbb{R}^{M})$ such that (up to
subsequences)

$\tilde{w}_{k}\coloneqq
w_{k}-\mathsf{\Pi}_{\mathscr{B}}w_{k}-\mathsf{\Pi}_{\nabla^{\ell}}\big{(}w_{k}-\mathsf{\Pi}_{\mathscr{B}}w_{k}\big{)}\to
w\quad\text{strongly in }L^{p}(\Omega;\mathbb{R}^{M}).$

Since the functions $w_{k}$ are smooth, the equality
$\mathscr{B}w_{k}=\mathscr{B}\tilde{w}_{k}$ holds pointwise and we deduce from
(7.7) that, for all $\phi\in C_{\mathrm{c}}^{\infty}(\Omega;\mathbb{R}^{N})$,

$\begin{split}\int_{\Omega}u(y)\cdot\phi(y)\,\mathrm{d}y=\lim_{k\to+\infty}\int_{\Omega}\tilde{w}_{k}\cdot\mathscr{B}^{\ast}\phi(y)\,\mathrm{d}y=\int_{\Omega}w(y)\cdot\mathscr{B}^{\ast}\phi(y)\,\mathrm{d}y,\end{split}$

where $\mathscr{B}^{\ast}$ is the adjoint of $\mathscr{B}$. The conclusion is
then achieved. ∎

######  Remark 7.11.

Let $u\in L^{p}(\Omega;\mathbb{R}^{N})$ be an $\mathscr{A}$-free map and let
$w\in W^{\ell,p}(\Omega;\mathbb{R}^{M})$ be a potential for $u$ in the sense
of Theorem 2.8. Then, there exist constants $c_{0},c_{1}>0$ such that

$\frac{1}{c_{0}}\lVert u\|_{L^{p}(\Omega;\mathbb{R}^{N})}\leq\lVert
w\|_{W^{\ell,p}(\Omega;\mathbb{R}^{N})}\leq c_{1}\lVert
u\|_{L^{p}(\Omega;\mathbb{R}^{N})}.$ (7.8)

The first inequality easily follows from the identity $u=\mathscr{B}w$.
Conversely, keeping in force the notations in the proof of Theorem 2.8, we
have

$\left\|\tilde{w}_{k}\right\|_{W^{\ell,p}(\Omega;\mathbb{R}^{M})}\leq
c_{1}\lVert\tilde{u}_{k}\|_{L^{p}(\mathbb{R}^{d};\mathbb{R}^{N})},$

for a suitable $c_{1}>0$, whence, by taking the limit $k\to+\infty$ and
recalling requirement (2) in Definition 7.1, the second estimate in (7.8) is
achieved.

###  7.2. $\mathscr{A}$-free extensions

The $\Gamma$-convergence analysis that we developed in Sections 4 – 6 is
grounded on the splitting argument contained in Lemma 4.3, which in turn
requires Assumption 2. For the reader’s convenience, we recall the latter
here:

######  Assumption 2 ($\mathscr{A}$-free extension).

There exists an $\varepsilon$-independent constant $c>0$ and a sequence of
operators $\set{\mathsf{E}_{\mathscr{A}}^{\varepsilon}}$, with
$\mathsf{E}_{\mathscr{A}}^{\varepsilon}\colon L^{p}(\Omega;\mathbb{R}^{N})\to
L^{p}(\Omega;\mathbb{R}^{N})$ such that the following holds: for all $u\in
L^{p}(\Omega;\mathbb{R}^{N})$ such that $\mathscr{A}u=0$ in
$W^{-1,p}(\Omega;\mathbb{R}^{N})$

  1. (1)

${\mathsf{E}}_{\mathscr{A}}^{\varepsilon}u=u$ a.e. in
$\Omega_{1,\varepsilon}$,

  2. (2)

$\lVert\mathsf{E}_{\mathscr{A}}^{\varepsilon}u\|_{L^{p}(\Omega;\mathbb{R}^{N})}\leq
c\lVert u\|_{L^{p}(\Omega_{1,\varepsilon};\mathbb{R}^{N})}$,

  3. (3)

$\mathscr{A}(\mathsf{E}_{\mathscr{A}}^{\varepsilon}u)=0$ on $\Omega$, and

  4. (4)

if $\set{u_{\varepsilon}}\subset L^{p}(\Omega;\mathbb{R}^{N})$ is
$p$-equiintegrable, then
$\set{\mathsf{E}_{\mathscr{A}}^{\varepsilon}u_{\varepsilon}}\subset
L^{p}(\Omega;\mathbb{R}^{N})$ is also $p$-equiintegrable.

We begin by comparing the above requirements with similar ones that are
already available in the literature.

######  Remark 7.12 (On Assumption 2).

Assumption 2 above is quite close to [44, Definition 1.4]. The main
differences consist in: 1) the fact that the extension operator here is
assumed to exist on a periodically perforated domain, with constants
independent of the periodicity parameter $\varepsilon$; 2) the fact that the
existence of an extended $p$-equiintegrable sequence here is only required
when starting from a sequence that also had $p$-equiintegrability properties.
We refer to [44] for a general discussion on the connections between the
existence of extension operators from an open set to a bigger surrounding
domain, and the theory of DiPerna-Majda measures.

A notion $\mathscr{A}$-free extension domain was also considered in [56,
Definition 4.4]. There, however, no $p$-equiintegrability conditions are
prescribed. As pointed out in [56, Section 4.2], such extension results are,
in general, non-trivial. Additionally, they depend both on the topology of the
set and on the operator $\mathscr{A}$ under consideration. In particular, no
such $\mathscr{A}$-free extension is possible when $\mathscr{A}$ is the
operator associated to the Cauchy-Riemann system, not even in the case of very
regular sets $\Omega$.

In contrast to the classical cases of the curl and of higher-order gradients
(see the examples at the end of this section), we did not manage to ensure
that for a general operator $\mathscr{A}$ the whole Assumption 2 holds.
Nevertheless, as Theorem 2.9 shows, we are able to identify conditions on the
operator $\mathscr{A}$ which are sufficient for properties (1)–(3) of
Assumption 2 to be fulfilled. Note that this assumption is designed to tackle
the periodically perforated structure appearing in our problem. The first step
to prove properties (1)–(3) is thus to start from the simpler scenario in
which the parameter $\varepsilon$ is neglected. In this respect, we establish
the following:

######  Theorem 7.13 (Existence of $\mathscr{A}$-free extensions).

Let $D,O\subset\mathbb{R}^{d}$ be open sets such that $D$ is connected, $O$ is
bounded, and $\partial D\cap\bar{O}$ is a Lipschitz boundary. Let also
$\mathscr{A}$ be a linear, $k$-th order, homogeneous differential operator
with constant coefficients and constant rank, and let $\mathscr{B}$ be a
linear, $\ell$-th order, homogeneous differential operator with constant
coefficients such that (7.2) holds. We further assume that

  * •

for all $\mathscr{A}$-free $u\in L^{p}(D;\mathbb{R}^{N})$ there exists $w\in
W^{\ell,p}(D;\mathbb{R}^{M})$ satisfying $u=\mathscr{B}w$;

  * •

there exists a constant $c>0$ such that

$\lVert\nabla^{\ell}(w-\mathsf{\Pi}_{\mathscr{B}}w)\|_{L^{p}(D;\mathbb{R}^{N\times
d^{\ell}})}\leq c\lVert\mathscr{B}w\|_{L^{p}(D;\mathbb{R}^{M})}\quad\text{for
all }w\in W^{\ell,p}(D;\mathbb{R}^{N}).$ (7.9)

Then, there exist a map

${\mathsf{E}}_{\mathscr{A}}\colon L^{p}(D;\mathbb{R}^{N})\to
L^{p}(O;\mathbb{R}^{N})$

and a constant $c\coloneqq c(d,p,\mathscr{A},D,O)$ such that, for all $u\in
L^{p}(D;\mathbb{R}^{N})$ with $\mathscr{A}u=0$ in $W^{-k,p}(D\cap
O;\mathbb{R}^{N})$,

  1. (1)

${\mathsf{E}}_{\mathscr{A}}u=u$ a.e. in $D\cap O$,

  2. (2)

$\lVert\mathsf{E}_{\mathscr{A}}u\|_{L^{p}(O;\mathbb{R}^{N})}\leq c\lVert
u\|_{L^{p}(D;\mathbb{R}^{N})}$, and

  3. (3)

$\mathscr{A}(\mathsf{E}_{\mathscr{A}}u)=0$ on $O$.

Here, as before, $\mathsf{\Pi}_{\mathscr{B}}$ is the projection on the kernel
of $\mathscr{B}$, see (7.3) and Lemma 7.6. Note that, owing once more to
Corollary 3.10, one can prove that $\mathsf{\Pi}_{\mathscr{B}}$ is bounded
from $W^{\ell,p}$ to itself.

We will comment on the relationships between the previous theorem and the
theory developed above at the end of this section, see Remark 7.16. For the
moment being, let us just highlight that the hypothesis concerning existence
of potentials for $\mathscr{A}$-free fields on $D$ enables us to recast the
problem in terms of extension of Sobolev maps. For the latter, an adaptation
of well-established arguments yields the following:

######  Lemma 7.14 (cf. Lemma 2.6 in [1]).

Let $D,O\subset\mathbb{R}^{d}$ be open sets. If $D$ is connected, $O$ is
bounded, and $\partial D\cap\bar{O}$ is a Lipschitz boundary, there exist a
bounded linear map

${\mathsf{E}}\colon W^{\ell,p}(D;\mathbb{R}^{N})\to
W^{\ell,p}(O;\mathbb{R}^{N})$

and a constant $c\coloneqq c(d,p,D,O)$ such that

  1. (1)

${\mathsf{E}}u=u$ a.e. in $D\cap O$,

  2. (2)

$\lVert\mathsf{E}u\|_{L^{p}(O;\mathbb{R}^{N})}\leq c\lVert
u\|_{L^{p}(D;\mathbb{R}^{N})}$, and

  3. (3)

$\lVert\nabla^{\ell}(\mathsf{E}u)\|_{L^{p}(O;\mathbb{R}^{N\times
d^{\ell}})}\leq c\lVert\nabla^{\ell}u\|_{L^{p}(D;\mathbb{R}^{N\times
d^{\ell}})}$.

###### Proof.

The proof follows the same lines of [1, Lemma 2.6]. Note that, in order to
recover item (3) when $\ell>1$, Poincaré’s inequality has to be replaced with
(7.6). ∎

We are now in a position to prove the first main result of this section.

###### Proof of Theorem 7.13.

Let us fix $u\in L^{p}(D;\mathbb{R}^{N})$ such that $\mathscr{A}u=0$. The
current assumptions grant that there is a Sobolev potential $w\in
W^{\ell,p}(D;\mathbb{R}^{M})$ for $u$, i.e. $u=\mathscr{B}w$, and that it
satisfies

$\lVert\nabla^{\ell}(w-\mathsf{\Pi}_{\mathscr{B}}w)\|_{L^{p}(D;\mathbb{R}^{M\times
d^{\ell}})}\leq c\lVert u\|_{L^{p}(D;\mathbb{R}^{N})}.$ (7.10)

If $\mathsf{E}$ is the extension operator in Lemma 7.14, we set

${\mathsf{E}_{\mathscr{A}}}u\coloneqq\mathscr{B}\big{(}{\mathsf{E}}(w-\mathsf{\Pi}_{\mathscr{B}}w)\big{)}.$

By construction, then, ${\mathsf{E}}_{\mathscr{A}}u=u$ almost everywhere in
$D\cap O$. Additionally, $\mathscr{A}(\mathsf{E}_{\mathscr{A}}u)=0$ on $O$ by
the definition of $\mathscr{A}$-free maps and (7.2).

To conclude, we need to show that
$\lVert{\mathsf{E}_{\mathscr{A}}}u\|_{L^{p}(O;\mathbb{R}^{N})}\leq c\lVert
u\|_{L^{p}(D;\mathbb{R}^{N})}$. By the definition of
${\mathsf{E}_{\mathscr{A}}}u$, we have

$\lVert{\mathsf{E}_{\mathscr{A}}}u\|_{L^{p}(O;\mathbb{R}^{N})}=\lVert\mathscr{B}\big{(}{\mathsf{E}}(w-\mathsf{\Pi}_{\mathscr{B}}w)\big{)}\|_{L^{p}(O;\mathbb{R}^{N})}\leq
c\lVert\nabla^{\ell}\big{(}{\mathsf{E}}(w-\mathsf{\Pi}_{\mathscr{B}}w)\big{)}\|_{L^{p}(O;\mathbb{R}^{M\times
d^{\ell}})},$

$c$ being a constant depending on $\mathscr{B}$ (and hence on $\mathscr{A}$).
Thanks to Lemma 7.14, we obtain a bound in terms of the potential of $u$:

$\lVert{\mathsf{E}_{\mathscr{A}}}u\|_{L^{p}(O;\mathbb{R}^{N})}\leq
c\lVert\nabla^{\ell}(w-\mathsf{\Pi}_{\mathscr{B}}w)\big{)}\|_{L^{p}(D;\mathbb{R}^{M\times
d^{\ell}})}$

for some $c\coloneqq c(d,p,\mathscr{A},D,O)$. The conclusion is achieved by
combining the above inequality with (7.10). ∎

Arguing as in the proof of Theorem 7.13, we ground our study in the case of
perforated domains on the seminal result in [1] about the extension of Sobolev
functions. In what follows, we say that a set $D$ is $Q$-periodic if $D+z=D$
for every $z\in\mathbb{Z}^{d}$ and we use the notation $\varepsilon D$ for the
$\varepsilon$-homotetic set $\varepsilon D\coloneqq\set{\varepsilon x:\,x\in
D}$.

######  Proposition 7.15 (cf. Theorem 2.1 in [1] and references therein).

Let $D\subset\mathbb{R}^{d}$ be a $Q$-periodic, connected, open set such that
$\partial D$ is Lipschitz and $\mathbb{R}^{d}\setminus D$ is disconnected.
Then, there exists a constant $c\coloneqq c(d,p,D)$, independent of
$\varepsilon$ and $\Omega$, as well as a sequence of operators
$\set{{\mathsf{E}}^{\varepsilon}}$, with ${\mathsf{E}}^{\varepsilon}\colon
W^{\ell,p}(\Omega\cap\varepsilon D;\mathbb{R}^{N})\to
W^{\ell,p}(\Omega;\mathbb{R}^{N})$ such that

  1. (1)

${\mathsf{E}}^{\varepsilon}u=u$ a.e. in $\Omega\cap\varepsilon D$,

  2. (2)

$\lVert\mathsf{E}^{\varepsilon}u\|_{L^{p}(\Omega;\mathbb{R}^{N})}\leq c\lVert
u\|_{L^{p}(\Omega\cap\varepsilon D;\mathbb{R}^{N})}$, and

  3. (3)

$\lVert\nabla^{\ell}(\mathsf{E}^{\varepsilon}u)\|_{L^{p}(\Omega;\mathbb{R}^{N\times
d^{\ell}})}\leq c\lVert\nabla^{\ell}u\|_{L^{p}(\Omega\cap\varepsilon
D;\mathbb{R}^{N\times d^{\ell}})}$.

We point out that the above proposition is proven in [1] for $\ell=1$. We omit
the proof in the case $\ell>1$ as it is a direct adaptation of [1, Proof of
Theorem 2.1]. Thanks to the previous result, we obtain that points (1)–(3) of
Assumption 2 are satisfied for an operator $\mathscr{A}$ as soon as it admits
a potential for which a Korn-type inequality holds. Note that it is
fundamental that we start from fields $u$ which are $\mathscr{A}$-free in the
whole set $\Omega$: in principle, the existence of a potential would be false
if we worked with maps that are $\mathscr{A}$-free just on the perforated set
$\Omega_{1,\varepsilon}$, cf. Remark 7.2.

###### Proof of Theorem 2.9.

Let $u\in L^{p}(\Omega;\mathbb{R}^{N})$ be an $\mathscr{A}$-free map and let
$w\in W^{\ell,p}(\Omega;\mathbb{R}^{M})$ be its potential. So,
$u=\mathscr{B}w$ and

$\lVert\nabla^{\ell}(w-\mathsf{\Pi}_{\mathscr{B}}w)\|_{L^{p}(\Omega_{1,\varepsilon};\mathbb{R}^{N\times
d^{\ell}})}\leq c\lVert u\|_{L^{p}(\Omega_{1,\varepsilon};\mathbb{R}^{N})},$
(7.11)

for a constant $c$ independent of $\varepsilon$. The proof now follows the one
of Theorem 7.13, the main change being the use of Proposition 7.15 instead of
Lemma 7.14. ∎

In light of our analysis, existence of potentials and of extension operators
turn out to be almost equivalent; a key role in this respect is played by
(7.9). We elaborate on this point in the next remark.

######  Remark 7.16 (Relations between existence of potentials and of
extension operators).

Let us compare the main results of the current section.

We let the operator $\mathscr{A}$ be as above, notably we assume that it has
constant rank. Thanks to Theorem 2.8, we know that if $D\subset\mathbb{R}^{d}$
is a bounded, connected, open set with Lipschitz boundary which is also an
$\mathscr{A}$-extension domain in the sense of Definition 7.1, then
$\mathscr{A}$-free maps on $D$ admit potentials. In short, for the class of
operators under consideration and for sufficiently ‘nice’ open sets $D$, it
holds

$D\text{ is an $\mathscr{A}$-extension domain}\implies\text{existence of
potentials for $\mathscr{A}$-free fields on }D.$ (7.12)

Conversely, if $D\subset\mathbb{R}^{d}$ is an open bounded set with Lipschitz
boundary such that all $\mathscr{A}$-free fields on $D$ admit Sobolev
potentials through the operator $\mathscr{B}$ and if for the latter (7.9)
holds, then $D$ is an $\mathscr{A}$-extension domain. Indeed, by a slight
adaptation of the proof, a variant of Theorem 7.13 for the case
$O=\mathbb{R}^{d}$ can be established. Schematically, again for sufficiently
‘nice’ open sets $D$, we have

$\left.\begin{aligned} \text{existence of potentials for $\mathscr{A}$-free
fields on }D\\\ \text{Korn-type inequality for $\mathscr{B}$ on
}D\end{aligned}\right\\}\implies D\text{ is an $\mathscr{A}$-extension
domain}.$

All in all, we see that, given a constant rank operator $\mathscr{A}$ and a
bounded, connected, open set with Lipschitz boundary $D$, the existence of
Sobolev potentials for $\mathscr{A}$-free maps on $D$ and the existence of an
$\mathscr{A}$-free extension operator from $D$ to $\mathbb{R}^{d}$ are nearly
equivalent. More specifically, they would actually be equivalent as soon as we
knew that the generalised Korn inequality (7.9) holds when $D$ is a ‘nice’
open set and $\mathscr{B}$ is a constant rank operator. In conclusion, we
believe that investigations about the validity of (7.9) constitute a very
interesting line of research.

We conclude with a parade of examples.

######  Example 7.17 (Higher-order gradients).

For $k\in\mathbb{N}\setminus\set{0}$, let $\mathscr{A}=\nabla^{k}$. Then,
Assumptions 1 and 2 are simple consequences of the fact that the kernel of
$\mathscr{A}$ coincides with the space of polynomials with degree smaller or
equal than $k-1$.

######  Example 7.18 (Curl).

For the choice $\mathscr{A}=\mathrm{curl}$, we have (classically) $d=N=M=3$
and

$\mathrm{curl}\,u=\sum_{i=1}^{3}A^{(i)}\frac{\partial u}{\partial x_{i}},$

with

$A^{(1)}\coloneqq\begin{pmatrix}0&0&0\\\ 0&0&-1\\\ 0&1&0\end{pmatrix},\quad
A^{(2)}\coloneqq\begin{pmatrix}0&0&1\\\ 0&0&0\\\ -1&0&0\end{pmatrix},\quad
A^{(3)}\coloneqq\begin{pmatrix}0&-1&0\\\ 1&0&0\\\ 0&0&0\end{pmatrix}.$

The symbol of $\mathrm{curl}$ is then

$\mathbb{A}[\omega]=\begin{pmatrix}0&-\omega_{3}&\omega_{2}\\\
\omega_{3}&0&-\omega_{1}\\\ -\omega_{2}&\omega_{1}&0\end{pmatrix}$

and $\mathrm{rank}\,\mathrm{\mathbb{A}}[\omega]=2$ for all
$\omega\in\mathbb{R}^{d}\setminus\set{0}$.

It is easy to check that Assumption 1 holds. Besides, all the conditions in
Assumption 2 are fulfilled too (see e.g. M. Cherdantsev and K. Cherednichenko
[22]; as for point (4), note that reflections, dilations, and patching by
partitions of unity preserve $p$-equiintegrability).

######  Example 7.19 (The $\mathrm{curl\,curl}$ operator).

Let $d=M=N=3$ and, for all $i,j=1,2,3$, let $E^{(i,j)}$ be the matrix whose
entries all $0$, but for the one in position $(i,j)$, which equals $1$. We
consider the operator $\mathscr{A}={\rm curl\,curl}$, defined as

$\mathrm{curl\,curl}\,u\coloneqq\sum_{i,j=1}^{3}A^{(i,j)}\frac{\partial^{2}u}{\partial
x_{j}\partial x_{i}},$

where $A^{(i,i)}=-E^{(i+1,i+1)}-E^{(i+2,i+2)}$ (the indices are computed
modulo $3$) and $A^{(i,j)}=E^{(i,j)}$. The symbol of this operator is

$\mathbb{A}[\omega]=\begin{pmatrix}-\omega^{2}_{2}-\omega^{2}_{3}&\omega_{1}\omega_{2}&\omega_{1}\omega_{3}\\\
\omega_{1}\omega_{2}&-\omega^{2}_{1}-\omega^{2}_{3}&\omega_{2}\omega_{3}\\\
\omega_{1}\omega_{3}&\omega_{3}\omega_{3}&-\omega^{2}_{1}-\omega^{2}_{2}\end{pmatrix}$

and $\mathrm{rank}\,\mathrm{\mathbb{A}}[\omega]=2$ for all
$\omega\in\mathbb{R}^{d}\setminus\set{0}$.

When $\Omega\subset\mathbb{R}^{3}$ is a bounded and simply connected domain
with Lipschitz boundary, we have that $\mathscr{A}u=0$ if and only if
$u=\mathscr{B}w$ for a suitable potential $w$, where $\mathscr{B}$ is the
symmetric gradient $\mathscr{B}w\coloneqq(\nabla w+(\nabla
w)^{\mathsf{t}})/2$. As a result, Assumption 1 is satisfied. Additionally, as
a corollary of a recent result by F. Cagnetti & al. [16, Theorem 1.1], every
such $\Omega$ is a $\mathrm{curl\,curl}$-extension domain.

######  Example 7.20 (Divergence).

Let us choose $\mathscr{A}=\operatorname{div}$, $\operatorname{div}$ being the
standard divergence operator on $\mathbb{R}^{d}$. Then, $N=d$, $M=1$, and

$\operatorname{div}u=\sum_{i=1}^{d}e_{i}^{\mathsf{t}}\cdot\frac{\partial
u}{\partial x_{i}},$

where, for $i=1,\dots,d$, $e_{i}$ is the $i$-th element of the canonical basis
of $\mathbb{R}^{d}$ and $e_{i}^{\mathsf{t}}$ is its transpose. The symbol of
$\operatorname{div}$ is

$\mathbb{A}[\omega]=\sum_{i=1}^{d}\omega_{i}e_{i}^{\mathsf{t}},$

thus $\mathrm{\mathbb{A}}[\omega]=1$ for all
$\omega\in\mathbb{R}^{d}\setminus\set{0}$. For what concerns Assumption 1 and
the existence of extension operators, we resort to a result by T. Kato & al.,
which we present in a simplified setting:

######  Proposition 7.21 (Extensions and potentials for divergence-free vector
fields [55]).

Let $\Omega\subset\mathbb{R}^{d}$ be a bounded and simply connected set with
Lipschitz boundary. Then, the following holds:

  1. (1)

$\Omega$ is a $\operatorname{div}$-extension domain in the sense of Definition
7.1.

  2. (2)

For every $u\in L^{p}(\Omega;\mathbb{R}^{d})$ such that
$\operatorname{div}u=0$ in $\Omega$, there exists $w\in
W^{1,p}(\Omega;\mathrm{Antisym}(d\times d))$ satisfying

$u=\mathrm{Div}\,w\coloneqq\sum_{j,i}\frac{\partial w_{i,j}}{\partial
x_{i}}e_{j}\quad\text{in }\Omega,$

where $\mathrm{Antisym}(d\times d)$ is the space of $d\times d$ antisymmetric
matrices. Besides, $w$ can be selected in such a way that the map $u\mapsto w$
from $L^{p}(\Omega;\mathbb{R}^{d})$ to $W^{1,p}(\Omega;\mathbb{R}^{d})$ is
linear and bounded.

It is interesting to notice that the authors of [55] derive item (2) from (1),
that is, they prove an implication of the form (7.12).

## Acknowledgements

We acknowledge support from the Austrian Science Fund (FWF) projects F65, V
662, Y1292, from the FWF-GAČR project I 4052/19-29646L, and from the OeAD-WTZ
project CZ04/2019 (MŠMTČR 8J19AT013).

## References

  * [1] E. Acerbi, V. Chiadò Piat, G. Dal Maso, D. Percivale.  An extension theorem from connected sets and homogenization in general periodic domains.  Nonlinear Analysis, 18(5) (1992), 481–486.
  * [2] G. Allaire.  Homogenization and two-scale convergence.  SIAM J. Math. Anal. 23 (6) (1992), 1482–1518.
  * [3] A. Arroyo-Rabasa.  Relaxation and optimization for linear-growth convex integral functionals under PDE constraints.  J. Funct. Anal. 7 (2017), 2388–2427.
  * [4] A. Arroyo-Rabasa, G. De Philippis, F. Rindler.  Lower semicontinuity and relaxation of linear-growth integral functionals under PDE constraints.  Adv. Calc. Var. 13(3) (2018), 219–255.
  * [5] J.-L. Auriault. Effective macroscopic description for heat conduction in periodic composites. Int. J. Heat Mass Transf. 26 (1983), 861–869.
  * [6] M. Baía, M. Chermisi, J. Matias, P. M. Santos.  Lower semicontinuity and relaxation of signed functionals with linear growth in the context of $\mathscr{A}$-quasiconvexity.  Calc. Var. Partial Differential Equations, 47(3-4) (2013), 465–498.
  * [7] N. Bakhvalov, G. Panasenko.  Homogenization: Averaging Processes in Periodic Media.  Kluwer, Dordrecht (1989).
  * [8] M. Barchiesi. Toughening by Crack Deflection in the Homogenization of Brittle Composites with Soft Inclusions. Arch. Ration. Mech. Anal. 227 (2018), 749–766.
  * [9] M. Barchiesi, G. Lazzaroni, C.I. Zeppieri. A bridging mechanism in the homogenization of brittle composites with soft inclusions. SIAM J. Math. Anal. 48 (2016).
  * [10] B. Benešová, M. Kružík. Weak lower semicontinuity of integral functionals and applications. SIAM Rev. 59(4) (2017), 703–766
  * [11] G. Bouchitté, B. Schweizer. Cloaking of small objects by anomalous localized resonance. Quart. J. Mech. Appl. Math. 63 (2010), 437–463.
  * [12] A. Braides. Gamma-Convergence for Beginners. Oxford Lecture Series in Mathematics and its Applications, 22, Oxford University Press (2002).
  * [13] A. Braides, I. Fonseca, G. Leoni.  $\mathscr{A}$-quasiconvexity: relaxation and homogenization.  ESAIM Control Optim. Calc. Var. 5 (2000), 539–577.
  * [14] A. Braides, A. Garroni. Homogenization of periodic nonlinear media with stiff and soft inclusions. Math. Models Methods Appl. Sci. 5 (1995), 543–564.
  * [15] A. Braides, M. Solci. Multi-scale free-discontinuity problems with soft inclusions. Boll. Unione Mat. Ital. 9 (2013), 29–51.
  * [16] F. Cagnetti, A. Chambolle, M. Perugini, L. Scardia. An extension result for generalised special functions of bounded deformation. J. Convex Anal., to appear.
  * [17] F. Cagnetti, L. Scardia. An extension theorem in $SBV$ and an application to the homogenization of the Mumford–Shah functional in perforated domains. Journal de Mathématiques Pures et Appliquées, 95 (2011), 349–381,
  * [18] M. Camar-Eddine, L. Pater.  Homogenization of high-contrast and non symmetric conductivities for non periodic columnar structures.  Networks & Heterogeneous Media, 8(4) (2013), 913–941.
  * [19] M. Camar-Eddine, P. Seppecher. Determination of the closure of the set of elasticity functionals. Arch. Ration. Mech. Anal. 170 (2003), 211–245.
  * [20] S.L. Campbell, C.D. Meyer. Generalized Inverses of Linear Transformations. Society for Industrial and Applied Mathematics, 2009.
  * [21] C. Castaing, M. Valadier. Convex Analysis and Measurable Multifunctions, Lecture Notes in Mathematics, Vol.580, Springer-Verlag, Berlin, 1977.
  * [22] M. Cherdantsev, K. D. Cherednichenko. Two-scale $\Gamma$-convergence of integral functionals and its application to homogenisation of nonlinear high contrast periodic composites. Arch. Ration. Mech. Anal. 204 (2012), 445–478.
  * [23] M. Cherdantsev, K. Cherednichenko, S. Neukamm.  High contrast homogenisation in nonlinear elasticity under small loads.  Asymptotic Anal. 104 (2017), 67–102.
  * [24] K. Cherednichenko, S. Cooper.  Homogenization of the system of high-contrast Maxwell equations.  Mathematika, 61(2) (2015), 475–500.
  * [25] E. Chiodaroli, E. Feireisl, O. Kreml, E. Wiedemann.  $\mathscr{A}$-free rigidity and applications to the compressible Euler system.  Annali di Matematica Pura ed Applicata (1923 -), 196 (2017), 1557–1572.
  * [26] S. Conti, S. Müller, M. Ortiz. Data-Driven Finite Elasticity. Arch. Ration. Mech. Anal. 237 (2020), 1–33.
  * [27] F. Christowiak, C. Kreisbeck. Homogenization of layered materials with rigid components in single-slip finite crystal plasticity. Calc. Var. Partial Differential Equations, 56 (2018): 75.
  * [28] F. Christowiak, C. Kreisbeck. Asymptotic rigidity of layered structures and its application in homogenization theory. Arch. Ration. Mech. Anal. 235 (2020), 51–98.
  * [29] D. Cioranescu, A. Damlamian, G. Griso. The periodic unfolding method in homogenization. SIAM J. Math. Anal. 40(4) (2008), 1585-–1620.
  * [30] D. Cioranescu, A. Damlamian, G. Griso. Periodic unfolding and homogenization. C. R. Math. Acad. Sci. Paris, 335(1) (2002), 99–-104.
  * [31] D. Cioranescu, P. Donato.  An Introduction to Homogenization, Oxford University Press, Oxford (1999).
  * [32] B. Dacorogna.  Direct Methods in the Calculus of Variations.  Springer-Verlag, New York (1989).
  * [33] B. Dacorogna.  Weak Continuity and Weak Lower Semicontinuity of Nonlinear Functionals, volume 922 of Lecture Notes in Mathematics.  Springer-Verlag, Berlin-New York (1982).
  * [34] B. Dacorogna, I. Fonseca.  A-B quasiconvexity and implicit partial differential equations.  Calc. Var. Partial Differential Equations, 14(2) (2002), 115–149.
  * [35] G. Dal Maso.  An Introduction to $\Gamma$-Convergence.  Progress in Nonlinear Differential Equations and their Applications, 8\. Birkhäuser Boston Inc., Boston, MA (1993).
  * [36] G. Dal Maso. Generalised functions of bounded deformation. J. Eur. Math. Soc. (JEMS), 15 (2013), 1943–1997.
  * [37] E. Davoli, R. Ferreira, C. Kreisbeck. Homogenization in BV of a model for layered composites in finite crystal plasticity. Adv. Calc. Var. (2019), to appear.
  * [38] E. Davoli, I. Fonseca.  Homogenization of integral energies under periodically oscillating differential constraints.  Calc. Var. Partial Differential Equations, 55(3) (2016), 1–60.
  * [39] E. Davoli, I. Fonseca.  Periodic homogenization of integral energies under space-dependent differential constraints.  Port. Math. 73(4) (2016), 279–317.
  * [40] E. Davoli, I. Fonseca.  Relaxation of $p$-growth integral functionals under space-dependent differential constraints.  In: Trends in Applications of Mathematics to Mechanics. Springer INdAM Series, 27, (2018)
  * [41] E. Davoli, I. Fonseca, P. Liu. Adaptive image processing: first order PDE constraint regularizers and a bilevel training scheme. Preprint arXiv 1902.01122.
  * [42] R. Ferreira, I. Fonseca, R. Venkatraman. Homogenization of quasi-crystalline functionals via two-scale-cut-and-project convergence. Preprint arXiv 2005.13356.
  * [43] I. Fonseca, S. Krömer.  Multiple integrals under differential constraints: two-scale convergence and homogenization.  Indiana Univ. Math. J. 59(2) (2010), 427–457.
  * [44] I. Fonseca, M. Kružík.  Oscillations and concentrations generated by $\mathscr{A}$-free mappings and weak lower semicontinuity of integral functionals.  ESAIM Control Optim. Calc. Var. 16(2) (2010), 472–502.
  * [45] I. Fonseca, G. Leoni, S. Müller.  $\mathscr{A}$-quasiconvexity: weak-star convergence and the gap.  Ann. Inst. H. Poincaré Anal. Non Linéaire, 21(2) (2004), 209–236.
  * [46] I. Fonseca, S. Müller.  $\mathscr{A}$-quasiconvexity, lower semicontinuity, and Young measures.  SIAM J. Math. Anal. 30(6) (1999), 1355–1390.
  * [47] F. Gmeineder, B. Raiţă.  Embeddings for $\mathbb{A}$-weakly differentiable functions on domains.  J. Funct. Anal. 277(12) (2019), 108278.
  * [48] F. Gmeineder, B. Raiţă, J. Van Schaftingen. On limiting trace inequalities for vectorial differential operators. Indiana Univ. Math. J., to appear.
  * [49] L. Grafakos, Classical Fourier Analysis, 2nd ed., Graduate Texts in Mathematics, vol. 249, Springer, New York (2008).
  * [50] A. Guerra, B. Raiţă.  On the necessity of the constant rank condition for $L^{p}$ estimates.  Compt. Rend. Math. 358(9-10) (2020), 1091–1095. Preprint arXiv 2007.00484v1.
  * [51] A. Guerra, B. Raiţă, M. R. I. Schrecker. Compensated compactness: continuity in optimal weak topologies. Preprint arXiv: 2007.00564.
  * [52] D. Gustafson.  A generalized Poincaré inequality for a class of constant coefficient differential operators.  Proc. Amer. Math. Soc. 139 (2011), 2721–2728.
  * [53] M. Heida. Stochastic homogenization on randomly perforated domains. Preprint arXiv 2001.10373.
  * [54] T. Kato.  On a Coerciveness Theorem by Schulenberger and Wilcox.  Indiana Univ. Math. J. 24(10) (1975), 979–985.
  * [55] T. Kato, M. Mitrea, G. Ponce, M. Taylor.  Extension and Representation of Divergence-free Vector Fields on Bounded Domains.  Mathematical Research Letters, 7(5) (2000), 643–650.
  * [56] J. Krämer, S. Krömer, M. Kružík, G. Pathó.  $\mathscr{A}$-quasiconvexity at the boundary and weak lower semicontinuity of integral functionals.  Adv. Calc. Var. 10(1) (2017), 49–67.
  * [57] C. Kreisbeck, S. Krömer.  Heterogeneous thin films: combining homogenization and dimension reduction with directors.  SIAM J. Math. Anal. 48(2) (2016), 785–820.
  * [58] C. Kreisbeck, F. Rindler.  Thin-film limits of functionals on $\mathscr{A}$-free vector fields.  Indiana Univ. Math. J. 64(5) (2015), 1383–1423.
  * [59] J. Kristensen and B. Raiţă. Oscillation and concentration in sequences of PDE constrained measures. Preprint arXiv:1912.09190
  * [60] J. Matias, M. Morandotti, P. M. Santos.  Homogenization of functionals with linear growth in the context of $\mathcal{A}$-quasiconvexity.  Appl. Math. Optim. 72(3) (2015), 523–547.
  * [61] S. G. Mikhlin.  Multidimensional singular integrals and integral equations,  Pergamon Press, Oxford (1965).
  * [62] F. Murat.  Compacité par compensation: condition nécessaire et suffisante de continuité faible sous une hypothèse de rang constant.  Ann. Scuola Norm. Sup. Pisa Cl. Sci. (4), 8(1) (1981), 69–102.
  * [63] G. Nguetseng. A general convergence result for a functional relate to the theory of homogenization. SIAM J. Math. Anal. 20(3) (1989), 608–623.
  * [64] X. Pellet, L. Scardia, C.I. Zeppieri. Homogenization of high-contrast Mumford-Shah energies. SIAM J. Math. Anal. 51 (2019), 1696–1729.
  * [65] J. B. Pendry, D. Schurig, D. R. Smith. Controlling electromagnetic fields. Science, 312 (2006), 1780–1782.
  * [66] B. Raiţă.  Potentials for $\mathcal{A}$-quasiconvexity.  Calc. Var. Partial Differential Equations 58 (2019): 105.
  * [67] B. Raiţă. $L^{1}$-estimates for constant rank operators. Preprint arXiv: 1811.10057.
  * [68] B. Raiţă. Critical $L^{p}$-differentiability of $BV_{A}$-maps and canceling operators. Trans. Amer. Math. Soc. 372 (2019), 7297–7326.
  * [69] B. Raiţă and A. Skorobogatova. Continuity and canceling operators of order $n$ on $R^{n}$. Calc. Var. Partial Differential Equations 59 (2020): 85.
  * [70] P. M. Santos.  $\mathscr{A}$-quasi-convexity with variable coefficients.  Proc. Roy. Soc. Edinburgh Sect. A, 134(6) (2004), 1219–1237.
  * [71] L. Scardia. Damage as $\Gamma$-limit of microfractures in anti-plane linearized elasticity. Math. Models Methods Appl. Sci. 18 (2008), 1703–1740.
  * [72] L. Scardia. Damage as the $\Gamma$-limit of microfractures in linearized elasticity under the non-interpenetration constraint. Adv. Calc. Var. 3 (2010), 423–458.
  * [73] V.P. Smyshlyaev. Propagation and localization of elastic waves in highly anisotropic periodic composites via two-scale homogenization. Mech. Mater. 41 (2009), 434–447.
  * [74] E. M. Stein, T. S. Murphy. Harmonic analysis: real-variable methods, orthogonality, and oscillatory integrals, Princeton University Press, Princeton (1993).
  * [75] J. Van Schaftingen.  Limiting Sobolev inequalities for vector fields and canceling linear differential operators.  J. Eur. Math. Soc. 15(3) (2013), 877–921.
  * [76] M. Šilhavý.  A variational approach to nonlinear electro-magneto-elasticity: Convexity conditions and existence theorems.  Math. Mech. Solids 23(6) (2018), 907–928.
  * [77] A. Visintin. Some properties of two-scale convergence. Atti Accad. Naz. Lincei Cl. Sci. Fis. Mat. Natur. Rend. Lincei (9) Mat. Appl. 15(2) (2004), 93–107.
  * [78] A. Visintin. Towards a two-scale calculus. ESAIM Control Optim. Calc. Var. 12(3) (2006), 371–397.
  * [79] V.V. Zhikov. On an extension of the method of two-scale convergence and its applications. Sb. Math. 191 (2000), 973–1014.
  * [80] V. Zhikov, S. Kozlov, O. Oleinik.  Homogenization of Differential Operators.  Springer, Berlin, (1995).