# Precoder Design for Orthogonal Space-Time Block Coding based Cognitive Radio
with Polarized Antennas

Abdelwaheb Marzouki, Xin Jin
Institut Mines-Telecom, Telecom SudParis, CNRS Samovar UMR 5157, France
{abdelwaheb.marzouki<EMAIL_ADDRESS>
###### Abstract

The spectrum sharing has recently passed into a mainstream Cognitive Radio
(CR) strategy. We investigate the core issue in this strategy: interference
mitigation at Primary Receiver (PR). We propose a linear precoder design which
aims at alleviating the interference caused by Secondary User (SU) from the
source for Orthogonal Space-Time Block Coding (OSTBC) based CR. We resort to
Minimum Variance (MV) approach to contrive the precoding matrix at Secondary
Transmitter (ST) in order to maximize the Signal to Noise Ratio (SNR) at
Secondary Receiver (SR) on the premise that the orthogonality of OSTBC is
kept, the interference introduced to Primary Link (PL) by Secondary Link (SL)
is maintained under a tolerable level and the total transmitted power
constraint at ST is satisfied. Moreover, the selection of polarization mode
for SL is incorporated in the precoder design. In order to provide an analytic
solution with low computational cost, we put forward an original precoder
design algorithm which exploits an auxiliary variable to treat the
optimization problem with a mixture of linear and quadratic constraints.
Numerical results demonstrate that our proposed precoder design enable SR to
have an agreeable SNR on the prerequisite that the interference at PR is
maintained below the threshold.

###### Index Terms:

Cognitive radio, precoder design, orthogonal space-time block coding,
polarized antennas.

##  I Introduction

Cognitive Radio (CR) is an encouraging technology to combat the spectrum
scarcity. In order to further enhance the spectrum utilization, the spectrum
sharing strategy that Primary Users (PUs) and Secondary Users (SUs) coexist in
licensed bands as long as PUs are preserved from the interference caused by
SUs attracts much research efforts. Such a strategy is tantamount to a multi-
user system in which the inter-user interference mitigation is the core.
Various inter-user interference mitigation techniques for spectrum sharing CR
systems have been put forward. They can be roughly grouped into two
categories: power allocation [1]-[3] and precoding in Multiple-Input Multiple-
Output (MIMO) CR systems [4]-[7].

Space Time Block Coding (STBC) exploits time and space diversity in MIMO
systems so as to heighten the reliability of the message signal. Orthogonal
STBC (OSTBC) are contrived in such a fashion that the vectors of coding matrix
are orthogonal in both time and space dimensions. This feature yields a simple
linear decoding at the receiver side so that no complex matrix
manipulation—Singular Value Decomposition (SVD), for instance, is required for
recovering the information bit from the gathered received symbols. Numerous
precoding techniques have been mooted for unstructured codes. However, these
techniques cannot be applied to OSTBC which should forcibly preserve a special
space-time structure. The precoding design for OSTBC CR systems attracts less
attention in previous work. Such previous work in [7] was based on the Maximum
Likelihood (ML) space-time decoder, whereas the ML decoder is a nonlinear
method. Inspired by Minimum Variance (MV) receiver applied for OSTBC multi-
access systems [8] which used a weight matrix at the receiver side to quell
the inter-user interference, we make use of MV approach to design a precoding
matrix at Secondary Transmitter (ST).

The precoding matrix at ST is designed to comply with the needs in our CR
system: maximizing the Signal to Noise Ratio (SNR) at Secondary Receiver (SR)
on the premise that the orthogonality of OSTBC is kept, the interference
introduced to Primary Link (PL) by Secondary Link (SL) is maintained under a
tolerable level and the total transmitted power constraint at ST is satisfied.

The classic MV beamforming [9], [10] built an optimization problem which
includes only one linear constraint, that cannot administer to the needs in
our CR system. On the other hand, some precoder designs for CR systems [6]
introduced a mixture of linear and quadratic constraints to the optimization
problem which leads to iterative solutions with high computational complexity.
For the purpose of contriving a precoder that applies to our CR system and
provides an analytic solution with low computational cost, we moot an original
precoder design algorithm: we first take advantage of an optimization problem
which includes one linear constraint with the objective of preserving the
orthogonality of OSTBC and making SL introduce minimal interference to PL for
different combinations of the polarization mode at ST and SR. This
optimization problem provides an analytic solution in terms of an auxiliary
variable which is the system gain on SL. Then we regulate this auxiliary
variable using the quadratic constraints evoked by the transmitted power
budget at ST and the maximum tolerable interference at Primary Receiver (PR).
The polarization mode at ST and SR are conclusively settled on based upon the
maximization criteria of SNR at SR.

The rest of the paper is organized as follows. The system model and OSTBC are
presented in Section II. In Section III, we introduce the proposed precoder
design for OSTBC based CR with polarized antennas. We report the numerical
results and provide insights on the expected performance in Section IV.
Finally, we give the conclusion in Section V.

##  II System Descriptions

We consider a CR system that consists of one SL which exploits OSTBC and one
PL. ST and PT are only allowed to communicate with their peers. ST or PT is
equipped with $N_{t}$ antennas and SR or PR is equipped with $N_{r}$ antennas.
The antennas in the same array have identical polarization mode. On each link,
the transmit antenna array or the receive antenna array is able to switch its
polarization mode between vertical mode $V$ and horizontal mode $H$. We denote
by $qt$ and $qr$, respectively, the transmit antenna array’s polarization mode
and the receive antenna array’s polarization mode.

###  II-A System Model

In this paper, we exploit 3GPP Spatial Channel Model (SCM) [11]. The space
channel impulse response between a pair of antennas $u$ and $s$ of path $n$
can be expressed as a function in terms of the polarization channel response
and the geometric configuration of the antennas at both sides of the link:

$H_{u,s,n}\left(\chi_{BS}^{\left(v\right)},\chi_{BS}^{\left(h\right)},\chi_{MS}^{\left(v\right)},\chi_{MS}^{\left(h\right)},\theta_{n,m,AoD},\theta_{n,m,AoA}\right)$
(1)

where $\chi_{BS}^{\left(v\right)}$ is the BS antenna complex response for the
V-pol component, $\chi_{BS}^{\left(h\right)}$ is the BS antenna complex
response for the H-pol component, $\chi_{MS}^{\left(v\right)}$ is the MS
antenna complex response for the V-pol component, $\chi_{MS}^{\left(h\right)}$
is the MS antenna complex response for the H-pol component, $\theta_{n,m,AoD}$
is the Angle of Departure (AOD) for the $m$th subpath of the $n$th path and
$\theta_{n,m,AoA}$ is the Angle of Arrival (AOA) for the $m$th subpath of the
$n$th path.

We assume that the system is operated over a frequency-flat channel with
$N_{path}$ paths and each path contains only one subpath. For a point to point
communication link, the baseband input-output relationship at time-slot $t$ is
expressed as:

$\mathbf{y}\left(t\right)=\sqrt{\frac{\rho}{N_{t}}}\mathbf{H}^{qt,qr}\mathbf{x}\left(t\right)+\mathbf{n}\left(t\right)$
(2)

where $\rho$ is the SNR at each receive antenna, $\mathbf{x}\left(t\right)$ is
a $N_{t}\times 1$ size transmitted signal vector which satisfies
$E\left\\{\mathbf{x}\left(t\right)\mathbf{x^{\mathit{H}}}\left(t\right)\right\\}=N_{t}$,
$\mathbf{n}_{j}(t)$ is a $N_{r}\times 1$ size complex Gaussian noise vector at
receiver with zero-mean and unit-variance and $\mathbf{H}^{qt,qr}$ is the
$N_{r}\times N_{t}$ channel matrix for the specified $qt$ and $qr$ with the
entry

$H_{u,s}^{qt,qr}=\sum_{n=1}^{N_{path}}H_{u,s,n}\left(\chi_{BS}^{\left(x\neq
qt\right)}=0,\,\chi_{MS}^{\left(y\neq qr\right)}=0\right)$ (3)

where $x,y\in\left\\{V,\,H\right\\}$. $\mathbf{H}^{qt,qr}$ has unit variance
and satisfies
$E\left\\{\mathrm{tr\left(\mathbf{\mathbf{H}^{\mathit{qt,qr}}}\mathbf{\mathbf{H}^{\mathit{qt,qr}}}^{\mathrm{\mathit{H}}}\right)}\right\\}=N_{t}N_{r}$.

Assuming that the channel is constant from $t=1$ to $t=T$, then Equation (2)
can be extended into:

$\mathbf{Y}=\sqrt{\frac{\rho}{N_{t}}}\mathbf{\mathbf{H}^{\mathit{qt,qr}}}\mathbf{X}+\mathbf{N}$
(4)

where $\mathbf{Y}=\left[\mathbf{y}(1),\ldots,\mathbf{y}(T)\right]$,
$\mathbf{X}=\left[\mathbf{x}(1),\ldots,\mathbf{x}(T)\right]$ and
$\mathbf{N}=\left[\mathbf{n}\left(1\right),\ldots,\mathbf{n}\left(T\right)\right]$.

###  II-B Orthogonal Space-Time Block Coding

If $\mathbf{X}$ is OSTBC matrix, then $\mathbf{X}$ has a linear representation
in terms of complex information symbols prior to space-time encoding
$s_{k},\,k=1,\ldots,K$ [12]:

$\mathbf{X}=\sum_{k=1}^{K}\left(\mathbf{C}_{k}\mathrm{Re}\left\\{s_{k}\right\\}+\mathbf{D}_{k}\mathrm{Im}\left\\{s_{k}\right\\}\right)$
(5)

where $\mathbf{C}_{k}$ and $\mathbf{D}_{k}$ are $N_{t}\times T$ code matrices
[13].

OSTBC matrix has the following unitary property:

$\mathbf{X}\mathbf{X}^{H}=\left(\sum_{k=1}^{K}\left|s_{k}\right|^{2}\right)\mathbf{I}_{N_{t}\times
N_{t}}$ (6)

In order to represent the relationship between the original symbols and the
received signal by multiplication of matrices, we introduce the “underline”
operator [13] to rewrite Equation (2) as:

$\mathbf{\underline{Y}}=\mathbf{\mathcal{\mathbb{\mathcal{H}}}}^{qt,qr}\mathbf{A}\mathbf{\mathrm{\mathbf{\underline{s}}}}+\underline{\mathbf{N}}$
(7)

where $\mathbf{s}=\left[s_{1},\ldots,s_{K}\right]$ is the data stream which is
QPSK modulated in this paper,
$\mathbb{\mathcal{H}}^{qt,qr}=\left[\begin{array}[]{cc}\mathrm{Re}\left\\{\mathbf{I}_{T}\otimes\mathbf{H}^{qt,qr}\right\\}&\mathrm{-Im}\left\\{\mathbf{I}_{T}\otimes\mathbf{H}^{qt,qr}\right\\}\\\
\mathrm{Im}\left\\{\mathbf{I}_{T}\otimes\mathbf{H}^{qt,qr}\right\\}&\mathrm{Re}\left\\{\mathbf{I}_{T}\otimes\mathbf{H}^{qt,qr}\right\\}\end{array}\right]$
is the equivalent channel matrix with the specified polarization mode,
$\mathbf{A}=\left[\underline{\mathbf{C}_{1}},\ldots,\underline{\mathbf{C}_{k}},\underline{\mathbf{D}_{1}},\ldots,\underline{\mathbf{D}_{k}}\right]$
is the OSTBC compact dispersion matrix and the “underline” operator for any
matrix $\mathbf{P}$ is defined as:

$\underline{\mathbf{P}}\triangleq\left[\begin{array}[]{c}\mathrm{vec}\left\\{\mathrm{Re}\left(\mathbf{P}\right)\right\\}\\\
\mathrm{vec}\left\\{\mathrm{Im}\left(\mathbf{P}\right)\right\\}\end{array}\right]$
(8)

where $\mathrm{vec}\left\\{\bullet\right\\}$ is the vectorization operator
stacking all columns of a matrix on top of each other.

The earliest OSTBC scheme which is well known as Alamouti’s code was proposed
in [14]. Alamouti’s code gives full diversity in the spatial dimension without
data rate loss. The transmission matrix of Alamouti’s code $C_{2}$ is given
as:

$C_{2}=\left[\begin{array}[]{cc}s_{1}&s_{2}\\\
-s_{2}^{*}&s_{1}^{*}\end{array}\right]$ (9)

In [15], Alamouti’s code was extended for more antennas. For instance, four
antennas, the transmission matrix of the half rate code $C_{4}$ is given as:

$C_{4}=\left[\begin{array}[]{cccc}s_{1}&s_{2}&s_{3}&s_{4}\\\
-s_{2}&s_{1}&-s_{4}&s_{3}\\\ -s_{3}&s_{4}&s_{1}&-s_{2}\\\
-s_{4}&-s_{3}&s_{2}&s_{1}\\\ s_{1}^{*}&s_{2}^{*}&s_{3}^{*}&s_{4}^{*}\\\
-s_{2}^{*}&s_{1}^{*}&-s_{4}^{*}&s_{3}^{*}\\\
-s_{3}^{*}&s_{4}^{*}&s_{1}^{*}&-s_{2}^{*}\\\
-s_{4}^{*}&-s_{3}^{*}&s_{2}^{*}&s_{1}^{*}\end{array}\right]$ (10)

##  III Precoder for OSTBC based CR with Polarized Antennas

We design a precoding matrix at ST which acts on the entry of the OSTBC
compact dispersion matrix and has no influence on the codes’ structure. Our
precoder design relies on the equivalent transmit correlation matrix on the
link between ST and PR (SPL). This matrix can be estimated easily by SU in the
sensing step and enables our precoder design to regulate the interference
introduced by SL to PL.

###  III-A Constraints from SL

With the precoding operation, the received signal at SR for the specified
polarization mode at ST and SR can be expressed as:

$\underline{\mathbf{Y_{\mathit{ST,SR}}^{\mathit{qt,qr}}}}=\sqrt{\frac{\rho_{SR}}{N_{t}}}\mathbb{\mathcal{H}}_{ST,SR}^{qt,qr}\mathbf{W}^{qt,qr}\mathbf{A}\mathbf{\underline{s}}+\underline{\mathbf{N}}$
(11)

where $\rho_{SR}$ is the SNR at each receive antenna of SR,
$\mathbb{\mathcal{H}}_{ST,SR}^{qt,qr}$ is the SL equivalent channel matrix
with the specified polarization mode at ST and SR,
$\mathbf{\mathbf{W}^{\mathit{qt,qr}}}$ is the precoding matrix for the
specified polarization mode at ST and SR.

A straightforward approach to estimate the transmitted signal from ST is using
the following soft output detector:

$\displaystyle\mathbf{\underline{\hat{s}}}$ $\displaystyle=$
$\displaystyle\mathbf{A}^{T}\mathbb{\mathcal{H}}_{ST,SR}^{qt,qr^{T}}\underline{\mathbf{Y_{\mathit{ST,SR}}^{\mathit{qt,qr}}}}$
$\displaystyle=$
$\displaystyle\sqrt{\frac{\rho_{SR}}{N_{t}}}\mathbf{A}^{T}\mathbb{\mathcal{H}}_{ST,SR}^{qt,qr^{T}}\mathbb{\mathcal{H}}_{ST,SR}^{qt,qr}\mathbf{\mathbf{W}^{\mathit{qt,qr}}}\mathbf{A}\mathbf{\underline{s}}+\mathbf{A}^{T}\mathbb{\mathcal{H}}_{ST,SR}^{qt,qr^{T}}\underline{\mathbf{N}}$

The OSTBC structure conservation puts forward the following constraint:

$\mathbf{A}^{T}\mathbb{\mathcal{H}}_{ST,SR}^{qt,qr^{T}}\mathbb{\mathcal{H}}_{ST,SR}^{qt,qr}\mathbf{\mathbf{W}^{\mathit{qt,qr}}}\mathbf{A}=\alpha^{qt,qr}\mathbf{I}_{2K}$
(13)

where $\alpha^{qt,qr}$ is the system gain on SL for the specified polarization
mode at ST and SR which will be adjusted to satisfy the other constraints.

Additionally, the transmitted power budget at ST induces another constraint:

$P_{t}^{qt,qr}\leq P_{tmax}$ (14)

where
$P_{t}^{qt,qr}=\frac{\rho_{SR}}{N_{t}}\mathrm{tr}\left(\mathbf{W^{\mathit{qt,qr}}}^{T}\mathbf{W}^{qt,qr}\right)$
and $P_{tmax}$ are, respectively, the transmitted power for the specified
polarization mode at ST and SR and the maximum transmitted power at ST.

###  III-B Constraints from PL

The received signal at PR from ST is deemed as baleful signal by PL and can be
expressed as:

$\underline{\mathbf{Y_{\mathit{ST,PR}}^{\mathit{qt,qr^{\prime}}}}}=\sqrt{\frac{\rho_{PR}}{N_{t}}}\mathbb{\mathcal{H}}_{ST,PR}^{qt,qr^{\prime}}\mathbf{W}^{qt,qr}\mathbf{A}\mathbf{\underline{s}}+\underline{\mathbf{N}}$
(15)

where $\rho_{PR}$ is the SNR at each receive antenna of PR and
$\mathbb{\mathcal{H}}_{ST,PR}^{qt,qr^{\prime}}$ is the equivalent channel
matrix for the specified polarization mode at ST and PR.

The interference power introduced by SL to PL for the specified polarization
mode at ST and PR can be calculated as:

$\displaystyle P_{ST,PR}^{qt,qr^{\prime}}$ $\displaystyle=$
$\displaystyle\mathrm{tr}\left[E\left(\mathbf{\underline{\mathbf{\mathbf{Y_{\mathit{ST,PR}}^{\mathit{qt,qr^{\prime}}}}}}}\,\mathbf{\underline{\mathbf{\mathbf{Y_{\mathit{ST,PR}}^{\mathit{qt,qr^{\prime}}}}}}}^{H}\right)\right]$
$\displaystyle=$
$\displaystyle\frac{\rho_{SR}}{N_{t}}\mathrm{tr}\left(\mathbf{W^{\mathit{qt,qr}}}^{T}R_{\mathit{PR,ST}}^{\mathit{qt,qr^{\prime}}}\mathbf{W}^{qt,qr}\right)$

where
$\mathcal{R_{\mathit{PR,ST}}^{\mathit{qt,qr^{\prime}}}}=E\left(\mathbb{\mathcal{H}}_{PR,ST}^{qt,qr^{\prime}T}\mathbb{\mathcal{H}}_{PR,ST}^{qt,qr^{\prime}*}\right)$
is the equivalent transmit correlation matrix on SPL for the specified
polarization mode at ST and PR. The maximum tolerable interference power
$\eta$ at PR evokes the following constraint:

$P_{ST,PR}^{qt,qr^{\prime}}\leq\eta$ (17)

###  III-C Minimum Variance Algorithm

SU can dominate the configuration of the precoding matrix and the polarization
mode on SL, while SU has no eligibility to select the polarization mode on PL.
Our algorithm is based on an optimization problem which includes one linear
constraint with the objective of preserving the orthogonality of OSTBC and
making SL introduce minimal interference to PL for different combinations of
the polarization mode at ST and SR. This optimization problem provides an
analytic solution in terms of an auxiliary variable which is the system gain
on SL. Then this auxiliary variable is regulated by using the quadratic
constraints evoked by the transmitted power budget at ST and the maximum
tolerable interference at PR. The polarization mode at ST and SR are
conclusively settled on based upon the maximization criteria of SNR at SR.

Such an optimization problem that includes one linear constraint is described
as follow:

$\left(\widehat{\mathbf{W^{\mathit{qt,qr}}}},\,\widehat{qt},\,\widehat{qr}\right)=\arg\min_{\mathbf{W^{\mathit{qt,qr}}},\,qt,\,qr}\frac{\rho_{SR}}{N_{t}}\mathrm{tr}\left(\mathbf{W^{\mathit{qt,qr}}}^{T}\mathcal{R_{\mathit{PR,ST}}^{\mathit{qt,qr^{\prime}}}}\mathbf{W^{\mathit{qt,qr}}}\right)$
(18)

$\mathrm{subject}\;\mathrm{to}:\;\mathrm{tr}\left(\mathbf{A}^{T}\mathbb{\mathcal{H}}_{ST,SR}^{qt,qr^{T}}\mathbb{\mathcal{H}}_{ST,SR}^{qt,qr}\mathbf{\mathbf{W^{\mathit{qt,qr}}}}\mathbf{A}\mathit{\mathrm{-}}\alpha^{qt,qr}\mathbf{I}_{2K}\right)=0$
(19)

We exploit the method of Lagrange multipliers to find
$\widehat{\mathbf{W^{\mathit{qt,qr}}}}$ for each combination of the
polarization mode at ST and SR. The Lagrangian function can be written as:

$\displaystyle
L\left(\mathbf{\mathbf{W^{\mathit{qt,qr}}}},\,\mathbf{\mathbf{\boldsymbol{\Lambda}}}\right)$
$\displaystyle=$
$\displaystyle\frac{\rho_{SR}}{N_{t}}\mathrm{tr}\left(\mathbf{\mathbf{W^{\mathit{qt,qr}}}}^{T}\mathcal{R_{\mathit{PR,ST}}^{\mathit{qt,qr^{\prime}}}}\mathbf{\mathbf{W^{\mathit{qt,qr}}}}\right)$
$\displaystyle-\mathrm{tr}\left(\mathbf{\mathbf{\boldsymbol{\Lambda}}}^{T}\left(\mathbf{A}^{T}\mathcal{R_{\mathrm{\mathit{ST,SR}}}^{\mathit{qt,qr}}}\mathbf{\mathbf{W^{\mathit{qt,qr}}}}\mathbf{A}\mathit{\mathrm{-}}\alpha^{qt,qr}\mathbf{I}_{2K}\right)\right)$
(20)

where
$\mathcal{R_{\mathrm{\mathit{ST,SR}}}^{\mathit{qt,qr}}}=\mathbb{\mathcal{H}}_{ST,SR}^{qt,qr^{T}}\mathbb{\mathcal{H}}_{ST,SR}^{qt,qr}$
and $\boldsymbol{\Lambda}$ is a $2K\times 2K$ size matrix of Lagrange
multipliers.

By differentiating the Lagrange function with respect to
$\mathbf{\mathbf{W^{\mathit{qt,qr}}}}$ and equating it to zero, we obtain an
analytic solution in terms of $\alpha^{qt,qr}$ which is expressed as:

$\widehat{\mathbf{W^{\mathit{qt,qr}}}}=\alpha^{qt,qr}\mathcal{R_{\mathit{PR,ST}}^{\mathit{qt,qr^{\prime}}}}^{-1}\mathcal{R_{\mathrm{\mathit{ST,SR}}}^{\mathit{qt,qr}}}\mathbf{A}\mathbf{Q^{\mathit{qt,qr}}}\mathbf{A}^{T}$
(21)

where
$\mathbf{Q^{\mathit{qt,qr}}}=\left(\mathbf{A}^{T}\mathcal{R_{\mathrm{\mathit{ST,SR}}}^{\mathit{qt,qr}}}\left(R_{\mathit{PR,ST}}^{\mathit{qt,qr^{\prime}}}\right)^{-1}\mathbf{A}\right)^{-1}$.

The estimated interference power at PR can be expressed in terms of
$\alpha^{qt,qr}$ as:

$\widehat{P_{ST,PR}^{qt,qr}}=\frac{\rho_{SR}\left(\alpha^{qt,qr}\right)^{2}\mathrm{tr}\left(\mathbf{Q^{\mathit{qt,qr}}}\right)}{N_{t}}$
(22)

The estimated SNR at SR can be written in terms of $\alpha^{qt,qr}$ as:

$\widehat{SNR_{ST,PR}^{qt,qr}}=\frac{\rho_{SR}\left(\alpha^{qt,qr}\right)^{2}\gamma^{qt,qr}}{N_{t}}$
(23)

where

$\displaystyle\gamma^{qt,qr}=$
$\displaystyle\mathrm{tr}\left(\mathbf{Q^{\mathit{qt,qr}}}\mathbf{A}^{T}\left(\mathcal{R_{\mathrm{\mathit{ST,SR}}}^{\mathit{qt,qr}}}R_{\mathit{PR,ST}}^{\mathit{qt,qr^{\prime}}}{}^{-1}\right)^{2}\mathcal{R_{\mathrm{\mathit{ST,SR}}}^{\mathit{qt,qr}}}\mathbf{AQ^{\mathit{qt,qr}}}\right)$
(24)

.

The estimated transmit power at ST in terms of $\alpha^{qt,qr}$ is given by:

$\widehat{P_{t}^{qt,qr}}=\frac{\rho_{SR}\left(\alpha^{qt,qr}\right)^{2}\delta^{qt,qr}}{N_{t}}$
(25)

where

$\delta^{qt,qr}=\mathrm{tr}\left(\mathbf{Q}^{qt,qr}\mathbf{A}^{T}\mathcal{R_{\mathrm{\mathit{ST,SR}}}^{\mathit{qt,qr}}}\left(R_{\mathit{PR,ST}}^{\mathit{qt,qr^{\prime}}}\right)^{-2}\mathcal{R_{\mathrm{\mathit{ST,SR}}}^{\mathit{qt,qr}}}\mathbf{AQ}^{qt,qr}\right)$
(26)

We derive $\alpha^{qt,qr}$ by substituting $\widehat{P_{t}^{qt,qr}}$ and
$\widehat{P_{ST,PR}^{qt,qr}}$ into Equation (14) and Equation (17) which
indicate the transmitted power budget constraint and the maximum tolerable
interference constraint:

$\alpha^{qt,qr}=\min\left(\sqrt{\frac{N_{t}}{\delta^{qt,qr}}},\,\sqrt{\frac{N_{t}\eta}{\rho_{SR}\mathrm{tr}\left(\mathbf{Q^{\mathit{qt,qr}}}\right)}}\right)$
(27)

Therefore the estimated SNR at SR can be determined as:

$\widehat{SNR_{ST,PR}^{qt,qr}}=\min\left(\frac{\rho_{SR}}{\delta^{qt,qr}},\frac{\eta}{\mathrm{tr}\left(\mathbf{Q}^{\mathit{qt,qr}}\right)}\right)\gamma^{qt,qr}$
(28)

Based upon the maximization criteria of SNR at SR, Finally, we destine the
estimated polarization mode of ST and SR as:

$\left(\widehat{qt},\widehat{qr}\right)=\arg\max_{qt,qr}\left[\min\left(\frac{\rho_{SR}}{\delta^{qt,qr}},\frac{\eta}{\mathrm{tr}\left(\mathbf{Q}^{qt,qr}\right)}\right)\gamma^{qt,qr}\right]$
(29)

##  IV Numerical Results

For the purpose of validating our proposed precoding design algorithm, we
simulated our CR system using the proposed precoder design algorithm and
measure the SNR at SR by using varying maximum transmitted power at ST and a
reasonable interference threshold at PR.

We firstly carried out our simulation with Alamouti’s code at ST for different
combinations of $qt$ and $qr$ on SL under different multipath scenarios. Then,
we executed our simulation with different codes for different number of
transmit antennas at ST based upon a determinate combination of $qt$ and $qr$
on SL and multipath scenario. In both simulation scenarios, the Signal to
Interference plus Noise Ratio (SINR) threshold to perceive the received signal
at PR was chosen equal to $0\mathrm{dB}$ and the Cross-polar Discrimination
(XPD) was set to $8\mathrm{dB}$. The channel matrix on each link was modeled
according to 3GPP SCM. Since the status of polarization at PR $qr^{\prime}$ is
normally unidentified for SU, the equivalent transmit correlation matrix on
SPL becomes random. This thereby results in a random SNR at SR. In our
simulation, we calculated the SNR at SR in terms of the polarization tilt
angle at PR by introducing a rotation matrix to the equivalent transmit
correlation matrix on SPL. We assumed that the polarization tilt angle at PR
follows a continuous uniform distribution between $0$ and $\frac{\pi}{2}$.
Then we sampled uniformly over the range of the polarization tilt angle at PR
and calculated the SNR at SR for each sample of tilt angle. Finally, we worked
out an average the SNR at SR to evaluate the system performance.

###  IV-A Performance Analysis of Polarization Diversity

We simulated a CR system, where ST is equipped with 2 antennas, SR is equipped
with 1 antenna and PR is equipped with 2 antennas. We observe the variation of
the average SNR at SR for different combinations of $qt$ and $qr$ on SL as the
transmit power at ST increases. First, we set SL channel as a 2-path frequency
flat fading channel and SPL channel as a single path frequency flat fading
channel. The variation tendencies in this scenario were depicted in Fig.1.
Then we reset SPL channel as a 4-path frequency flat fading channel and the
corresponding variation tendencies were shown in Fig.2. The average SNR at SR
for a large number of samples leads to the smooth curves. As the transmit
power at ST increases, the average SNR at SR of all different combinations of
$qt$ and $qr$ on SL exhibit uptrend in both scenarios and linear increase is
obtained when $P_{maxSU}/P_{noise}$ are below $15\mathrm{dB}$ in both
scenarios, where $P_{noise}$ denotes the noise power at SR. The mismatch of
$qt$ and $qr$ on SL induces a $15\mathrm{dB}$ gap between the matched modes
and the mismatched modes when the average SNR at SR has linear increase in the
first scenario. When we enhanced the number of paths in SPL channel, the
average SNR at SR for the mismatched modes was declined by $6\mathrm{dB}$ and
the gap was enlarged in the second scenario.

Figure 1: Average SNR at SR versus $P_{maxSU}/P_{noise}$ for different
polarization mode on SL under single path scenario Figure 2: Average SNR at SR
versus $P_{maxSU}/P_{noise}$ for different polarization mode under four paths
scenario

###  IV-B Performance Analysis of Transmit Antennas Diversity

In the second simulation, we aimed to observe the average SNR at SR by using
different number of transmit antennas. In the first circumstance, 2 transmit
antennas and Alamouti’s code $C_{2}$ were utilized at ST. In the second
circumstance, 4 transmit antennas and the half rate code $C_{4}$ were utilized
at ST. In both circumstances, we set $qt=V$ and $qr=V$. SR is equipped with 1
antenna and PR is equipped with 4 antennas. The number of paths is chosen
equal to 2 on SL and 6 on SPL.

For the case of 2 transmit antennas at ST, the SNR at SR reaches the
saturation point at $20\mathrm{dB}$ when $P_{maxSU}/P_{noise}$ achieves
$40\mathrm{dB}$. Compare to the previous results in Fig. 1 and 2, the SNR at
SR reaches the saturation point faster due to the increase in number of paths
on the SPL. However, the increase in number of antennas will significantly
delay the arrival of the saturation point even the number of paths on the SPL
is also increased. For the case of 4 transmit antennas at ST, the SNR at SR
reaches the saturation point at $65\mathrm{dB}$ when $P_{maxSU}/P_{noise}$
achieves $100\mathrm{dB}$.

Figure 3: Average SNR at SR versus $P_{maxSU}/P_{noise}$ for different number
of transmit antennas at ST

##  V Conclusions

A linear precoder design which aims at alleviating the interference at PR for
OSTBC based CR has been introduced. One of the principal contributions is to
endow the conventional prefiltering technique with the excellent features of
OSTBC in the context of CR. The prefiltering technique has been optimized for
the purpose of maximizing the SNR at SR on the premise that the orthogonality
of OSTBC is kept, the interference introduced to PL by SL is maintained under
a tolerable level and the total transmitted power constraint is satisfied.
Numeral Results have shown that polarization diversity contributes to achieve
better SNR at SR, moreover, the increase in number of antennas will
significantly delay the arrival of the saturation point for the SNR at SR.

## Acknowledgements

This research is supported by SACRA project (FP7-ICT-2007-1.1, European
Commission-249060).

## References

  * [1] Y.-C. Liang, K.-C. Chen, G.-Y. Li, P. Mahonen, ”Cognitive Radio Networking and Communications: An Overview,” IEEE Trans. Vehicular Technology, vol. 60, no. 7, pp. 3386-3407, Sept. 2011.
  * [2] A. Hoang, Y. Liang, and M. Islam, “Power control and channel allocation in cognitive radio networks with primary users’ cooperation,” IEEE Trans. Mobile Comput., vol. 9, no. 3, pp. 348–360, Mar. 2010.
  * [3] R.-C. Xie, F.-R. Yu, H. Ji, “Dynamic Resource Allocation for Heterogeneous Services in Cognitive Radio Networks With Imperfect Channel Sensing,” IEEE Trans. Vehicular Technology, vol. 61, no. 2, pp. 770 - 780, Feb. 2012.
  * [4] R. Prasad and A. Chockalingam, “Precoder Optimization in Cognitive Radio with Interference Constraints,” in Proc. IEEE ICC 2011.
  * [5] M. Jung, K. Hwang, and S. Choi, “Interference Minimization Approach to Precoding Scheme in MIMO-Based Cognitive Radio Networks,” IEEE Commun. Lett., vol. 15, no. 8, pp. 789-791, Aug. 2011.
  * [6] K. T. Phan, S. A. Vorobyov, N. D. Sidiropoulos, and C. Tellambura, “Spectrum sharing in wireless networks: A QoS-aware secondary multicast approach with worst user performance optimization,” in Proc. IEEE SAM’08, Jul. 2008, pp. 23–27.
  * [7] A. Punchihewa, V.-K. Bhargava, C. Despins, “Linear Precoding for Orthogonal Space-Time Block Coded MIMO-OFDM Cognitive Radio,” IEEE Trans. Commun., vol. 59, no. 3, pp. 767-779, Mar. 2011.
  * [8] S. Shahbazpanahi, M. Beheshti, A. B. Gershman, M. GharaviAlkhansari, and K. M. Wong, “Minimum variance linear receivers for multiaccess MIMO wireless systems with space–time block coding,” IEEE Trans. Signal Process., vol. 52, no. 12, pp. 3306–3313, Dec. 2004\.
  * [9] R. G. Lorenz and S. P. Boyd, “Robust minimum variance beamforming,” IEEE Trans. Signal Process., vol. 53, no. 5, pp. 1684–1696, May 2005.
  * [10] C. D. Richmond, “Capon algorithm mean squared error threshold SNR prediction and probability of resolution,” IEEE Trans. Signal Process., vol. 53, no. 8, pp. 2748–2764, Aug. 2005
  * [11] 3GPP TR 25.996 V10.0.0, “Spatial channel model for MIMO simulations,” www.3gpp.org, Mar. 2011.
  * [12] R. L. G. Cavalcante and I. Yamada, “Multiaccess interference suppression in OSTBC-MIMO systems by adaptive projected subgradient method,” IEEE Trans. Signal Process., vol. 56, no. 3, pp. 1028–1042, Mar. 2008.
  * [13] M. Gharavi-Alkhansari and A. B. Gershman, “Constellation space invariance of orthogonal space–time block codes,” IEEE Trans. Inf. Theory, vol. 51, no. 1, pp. 331–334, Jan. 2005.
  * [14] S. M. Alamouti, “A simple transmit diversity technique for wireless communications,” IEEE J. Sel. Areas Commun., vol. 16, no. 8, pp. 1451–1458, Oct. 1998.
  * [15] V. Tarokh, H. Javarkhani and Calderbank, “Space-time block codes from orthogonal designs,” IEEE Transactions on Information Theory, vol. 45, no. 5, July 1999, pp. 1456-1467.


# The uniform Gardner conjecture and rounding Borel flows

Matthew Bowen  Department of Mathematics and Statistics, McGill University,
805 Sherbrooke St W., H3A 0B9 Montreal, Canada<EMAIL_ADDRESS>,  Gábor Kun  Alfréd Rényi Institute of Mathematics, H-1053 Budapest,
Reáltanoda u. 13-15., Hungary  Institute of Mathematics, Eötvös Lóránd
University, Pázmány Péter sétány 1/c, H-1117 Budapest, Hungary
<EMAIL_ADDRESS>and  Marcin Sabok  Department of Mathematics and Statistics,
McGill University, 805 Sherbrooke St W., H3A 0B9 Montreal, Canada
<EMAIL_ADDRESS>
###### Abstract.

We study groups which satisfy Gardner’s equidecomposition conjecture for
uniformly distributed sets. We prove that an amenable group has this property
if and only if it does not admit
$(\mathbb{Z}/2\mathbb{Z})*(\mathbb{Z}/2\mathbb{Z})$ as a quotient by a finite
subgroup. Our technical contribution is an algorithm for rounding Borel flows
for actions of amenable groups.

The first and the third authors are partly funded by the NSERC Discovery Grant
RGPIN-2020-05445, NSERC Discovery Accelerator Supplement RGPAS-2020-00097 and
NCN Grant Harmonia 2018/30/M/ST1/00668. The second author’s work on the
project leading to this application has received funding from the European
Research Council (ERC) under the European Union’s Horizon 2020 research and
innovation programme (grant agreement No. 741420), from the ÚNKP-20-5 New
National Excellence Program of the Ministry of Innovation and Technology from
the source of the National Research, Development and Innovation Fund, from the
János Bolyai Scholarship of the Hungarian Academy of Sciences and from
Lendület grant no. 2022-58.

##  1\. Introduction

Let $\Gamma$ be a group acting on a standard probability space $X$. Two sets
$A,B\subseteq X$ are $\Gamma$-equidecomposable if there are finite partitions
$A=\bigcup_{i=1}^{k}A_{i},B=\bigcup_{i=1}^{k}B_{i}$ and group elements
$\gamma_{1},\dots,\gamma_{k}\in\Gamma$ such that $A_{i}=\gamma_{i}B_{i}$ holds
for every $1\leq i\leq k$. An equidecomposition is measurable if the sets in
the partitions are measurable. We recommend Máthé [Mát18] as a survey on
measurable equidecompositions.

The most famous open question on equidecompositions was Tarski’s circle
squaring problem [Tar25]. Laczkovich solved this positively [Lac90], but his
construction was not measurable, which left the measurable circle squaring
problem open for decades. This was only recently solved by Grabowski, Máthé
and Pikhurko [GMP17], who found a measurable equidecomposition [GMP17], and
Marks and Unger [MU17] found a Borel equidecomposition. The measurable circle
squaring also can be deduced from the result of the authors [BKS21] on the
existence of measurable perfect matchings in hyperfinite bipartite graphings.
Recently, Máthé, Noel and Pikhurko [MNP22] managed to find a circle squaring
with Jordan measurable pieces which are Boolean combinations of $F_{\sigma}$
sets.

The Banach-Tarski paradox [BT24] shows that any two bounded subsets of
$\mathbb{R}^{3}$ with nonempty interior are equidecomposable. Von Neumann
[vN29] introduced amenable groups in order to explain this paradox. This is
the largest class of groups where the existence of an equidecomposition may
imply the existence of a measurable equidecomposition. Gardner made the
following conjecture.

######  Conjecture 1.1.

[Gar91] Consider two bounded measurable sets $A,B\subseteq\mathbb{R}^{n}$ and
an amenable group of isometries $\Gamma$. If $A$ and $B$ are
$\Gamma$-equidecomposable then they admit a measurable equidecomposition.

Gardner’s conjecture would directly imply measurable circle squaring by the
resulf of Laczkovich [Lac90]. Note that Gardner’s conjecture does not require
that the isometries in the measurable equidecomposition are in $\Gamma$. The
second author has found an example of an amenable group of isometries $\Gamma$
and two measurable sets admitting a $\Gamma$-equidecomposition but no
measurable $\Gamma$-equidecomposition; the example is a modification of
Laczkovich’s construction [Lac88]. This example shows that in general the
group of isometries admitting an equidecomposition may not admit a measurable
equidecomposition. However, in this note we prove that this holds for
sufficiently equidistributed sets (we call them $\Gamma$-uniform, motivated by
[Lac92]); the only counterexamples are the groups admitting the infinite
dihedral group (i.e., $(\mathbb{Z}/2\mathbb{Z})*(\mathbb{Z}/2\mathbb{Z})$) as
a quotient by a finite subgroup.

Recall that given a Borel graph $G$ and a set $F\subseteq V(G),$ the boundary
of $F$ is $\partial F:=\\{x\in F:\exists y\in V(G)\setminus F\textnormal{ with
}(x,y)\in E(G)\\}.$ A set $F$ is $\varepsilon$-Følner if $|\partial
F|<\varepsilon|F|$ for every finite $F\subset V(G)$.

######  Definition 1.2.

Given a free pmp action of a finitely generated amenable group
$\Gamma\curvearrowright(X,\mu)$ and $A\subseteq X$, we say that $A$ is
$\Gamma$-uniform if there exists $\varepsilon>0$ such that for every
$\varepsilon$-Følner set $F$ contained in an orbit of the action, $|A\cap
F|\geq\varepsilon|F|$ holds.

Note that in the above definition, the property of being $\Gamma$-uniform does
not depend on the choice of the generating set of the group $\Gamma$, but the
constant $\varepsilon$ might. Motivated by Gardner’s conjecture we consider
the following property.

######  Definition 1.3.

An amenable group $\Gamma$ satisfies the uniform Gardner property if whenever
$\Gamma\curvearrowright(X,\mu)$ is a free pmp action, $A,B\subseteq X,$ and
$A,B$ are $\Gamma$-uniform and $\Gamma$-equidecomposable, then $A$ and $B$
admit a measurable $\Gamma$-equidecomposition.

Now we state our main result.

######  Theorem 1.4.

Let $\Gamma$ be a finitely generated amenable group. $\Gamma$ satisfies the
uniform Gardner property if and only if it does not admit
$(\mathbb{Z}/2\mathbb{Z})*(\mathbb{Z}/2\mathbb{Z})$ as a quotient by a finite
subgroup.

Marks and Unger [MU17] used a bounded integral-valued Borel flow in the
Schreier graph induced by finitely many translations to find an
equidecomposition of equidistributed sets. Our main technical contribution is
a simple Borel algorithm for rounding flows that applies beyond the case of
graphs arising from $\mathbb{Z}^{d}$ actions. It relies on the notion of
connected toasts (see Definition 2.3), which were introduced by the authors in
[BKS21]. They are known to exist a.e. in all one-ended hyperfinite graphings,
as well as in Borel actions of $\mathbb{Z}^{d}$. By a recent result of the
first author, Poulin and Zomback [BPZ22] they also exist in Borel actions of
polynomial growth groups.

######  Theorem 1.5.

Consider a locally finite Borel graph $G$, a bounded integral Borel function
$f:V(G)\mapsto\mathbb{Z}$ and a Borel $f$-flow $\phi$. Assume that $G$ admits
a Borel connected toast. Then $G$ has an integral Borel $f$-flow $\psi$ such
that $|\phi-\psi|<3$ holds everywhere.

In particular, this implies that every locally finite one-ended hyperfinite
graphing that admits a (not necessarily measurable) bounded real valued
$f$-flow also admits a bounded integral measurable $f$-flow.

##  2\. Definitions, notations

In this paper we will work with both Borel graphs, i.e., graphs whose vertex
set is a Polish space $X$ and whose edge set is a Borel subset of $X^{2},$ and
with graphings, which are probability measure preserving Borel graphs. We use
the standard graph theoretical notation and refer to $X$ as $V(G)$ and denote
the set of edges by $E(G)$.

A locally finite connected graph is one-ended if after the removal of any
finite subset of vertices it has exactly one infinite connected component. A
locally finite infinite connected graph is two-ended if it is not one-ended
and after the removal of any finite subset of vertices it has at most two
infinite connected components. For every amenable group, its Cayley graph is
either one-ended or two-ended, and the latter is true if and only if the group
is virtually $\mathbb{Z}$. We write Ends($\Gamma$) for the set of ends of the
group $\Gamma$.

We consider flows only on locally finite directed Borel graphs (to avoid
imposing conditions such as absolute convergence of the sum of the flow at
vertices of infinite degree). Given a locally finite directed Borel graph, a
function $f:V(G)\rightarrow\mathbb{Z}$ and a function
$c:E(G)\rightarrow\mathbb{N},$ we say that a function
$\phi:E(G)\rightarrow\mathbb{R}$ is an $f$-flow bounded by $c$ if
$\phi(x,y)\leq c(x,y)$ for each edge $(x,y)\in E(G)$, $\phi(x,y)=-\phi(y,x)$
and $\sum_{y\in N(x)}\phi(x,y)=f(x)$ for every $x\in V(G)$.

For hyperfinite graphings the existence of a real valued measurable $f$-flow
a.e. is equivalent to the existence of a not necessarily measurable $f$-flow,
and this fact is implicit in the work of [Weh92], [Lac96] and [CS].

######  Proposition 2.1.

Let $G$ be a locally finite hyperfinite graphing,
$f:V(G)\rightarrow\mathbb{Z}$ a measurable function and $\phi$ an $f$-flow
bounded by the integral capacity $c$. Then $G$ admits a measurable $f$-flow
$\psi$ bounded by $c$.

See [BKS21] Lemma 2.4 for a proof of the nearly identical fact with fractional
matchings taking the place of flows. We include the proof for flows for the
sake of completeness.

###### Proof of Lemma 2.1.

Using the hyperfiniteness of $G$, take a sequence of measurable partitions
$\mathcal{C}_{n}$ of measurable subsets $X_{n}\subseteq X$ into finite subsets
such that $\nu(X_{n})\geq 1-\frac{1}{2^{n}}$. We use this to construct a
sequence of measurable functions that are $f$-flows on elements of
$\mathcal{C}_{n}$. For each element $F$ of $\mathcal{C}_{n}$ choose the
lexicographically least integral function $\varphi_{n}(F)$ on the edges in $F$
which can be extended to a $f$-flow bounded by $c$. For each $n$, take the
union of all $\varphi_{n}(F)$ for $F\in\mathcal{C}_{n}$. This gives a function
which is a measurable $f$-flow on the vertices that are in the interior of a
cell in $\mathcal{C}_{n}$ for all but finitely many $n$. This sequence has a
weakly convergent subsequence in $L^{2}(E(G))$, and the limit satisfies the
conditions of the lemma. ∎

We will also use the following basic lemma about finite graphs.

######  Lemma 2.2.

Let $G$ be a finite, connected graph and $P\subseteq V(G)$ a subset of even
size. Then there exists a spanning subgraph $H$ of $G$ such that every vertex
of $P$ has odd degree in $H$, and every vertex of $V(G)\setminus P$ has even
degree in $H$.

###### Proof.

We prove by induction on the size of $P$. If $P=\emptyset$ then $H$ can be the
edgeless spanning subgraph. Else choose two different vertices $s,t\in P$. Let
$L$ denote a path connecting $s$ and $t$. By induction, there exists a
spanning subgraph $H^{\prime}$ of $G$ such that the degree of the vertices in
$P\setminus\\{s,t\\}$ is odd, and the degree of the other vertices is even in
$H^{\prime}$. Let $E(H)$ be the symmetric difference of $E(L)$ and
$E(H^{\prime})$. ∎

###  2.1. Connected toasts

The following definition [BKS21] refines the notion of a toast (see [GJKS18,
Definition 2.9], [GJKS15, Definition 4.1]), coined by Miller and motivated by
the work of Conley and Miller [CM16]. In particular, a toast is any tiling
that satisfies Properties (1) and (2) of the definition below.

######  Definition 2.3.

Given a Borel graph $G$, we say that a Borel collection $\mathcal{T}$ of
finite connected subsets of $V(G)$ is a connected toast if it satisfies

  1. (1)

$\bigcup_{K\in\mathcal{T}}E(K)=E(G)$,

  2. (2)

for every pair $K,L\in\mathcal{T}$ either $(K\cup N(K))\cap L=\emptyset$ or
$K\cup N(K)\subseteq L$, or $L\cup N(L)\subseteq K$,

  3. (3)

for every $K\in\mathcal{T}$ the induced subgraph on
$K\setminus\bigcup_{K\supsetneq L\in\mathcal{T}}L$ is connected.

The proof of Theorem 1.4 will use the following result on connected toasts.

######  Proposition 2.4.

[BKS21] Any locally finite, one-ended hyperfinite graphing admits a connected
toast a.e.

In order to find Borel flows and equidecompositions we will need connected
toasts everywhere. The following lemma provides this for actions of
$\mathbb{Z}^{d}$, which is enough for most geometric applications including
circle squaring. Recently, the first author, Poulin and Zomback [BPZ22]
generalized this to every one-ended polynomial growth group using the ideas of
this proof. We include the proof for $\mathbb{Z}^{d}$.

######  Proposition 2.5.

The Schreier graph of any free Borel action of $\mathbb{Z}^{d}$, for $d\geq
2$, admits a connected toast.

###### Proof.

Recall that a $k$-toast in a Borel graph $G$ is a Borel collection
$\mathcal{T}$ of finite connected subsets of $V(G)$ such that
$\bigcup_{K\in\mathcal{T}}E(K)=E(G)$, and for every pair $K,L\in\mathcal{T}$
either $(N^{k}(K)\cup K)\cap L=\emptyset$ or $K\cup N^{k}(K)\subseteq L$, or
$L\cup N^{k}(L)\subseteq K$. By the result of Gao, Jackson, Krohne, and Seward
(see [MU17, Theorem 5.5]), any free Borel $\mathbb{Z}^{d}$ action admits a
$k$-toast $\mathcal{T}$ such that the boundary of each $K\in\mathcal{T}$ is
visible from infinity (i.e., $K$ has no holes). Note that $\mathcal{T}$
satisfies Properties (1) and (2) of Definition 2.3, and we claim that it also
satisfies Property (3) as long as $k>2.$ To see this, we will use a result of
Deuschel and Pisztora [DP96, Lemma 2.1(i)] which says that if a finite,
connected set $H\subset\mathbb{Z}^{d}$ has no holes, then $N^{2}(H)\setminus
H$ is connected. Thus, since each $K\in\mathcal{T}$ has no holes, the set
$N^{2}(K)\setminus K$ is connected, and so for every $L\in\mathcal{T}$ the
induced subgraph on $L\setminus\bigcup_{L\supsetneq K\in\mathcal{T}}K$ is
connected, as any path through smaller tiles $K$ can be rerouted through
$N^{2}(K)\setminus K$. ∎

##  3\. Integral Borel flows using Borel tilings

In this section we give a short algorithm that allows us to convert bounded
real-valued Borel flows into bounded integral Borel flows, assuming that the
graph admits a connected toast. This is applicable to finding Borel
equidecompositions. Namely, as shown by Marks and Unger in [MU17], the
existence of bounded integral Borel flows can be used to prove
equidecomposition results using tilings such as the Gao–Jackson tilings [GJ15]
for actions of $\mathbb{Z}^{d}$. In the next section we will use these ideas
to prove our results on measurable equidecompositions.

We state the theorem below in the setting of Borel graphs that admit a
connected toast and Borel real-valued flow, as it applies to graphs for which
such connected toasts can be found. In particular, the main obstacle towards
using Theorem 3.1 to produce Borel equidecompositions lies with finding Borel
real-valued flows.

######  Theorem 3.1.

Consider a locally finite Borel graph $G$, a bounded integral Borel function
$f:V(G)\mapsto\mathbb{Z}$ blue and a Borel $f$-flow $\phi$. Assume that $G$
admits a Borel connected toast. Then there is an integral Borel $f$-flow
$\psi$ such that $|\phi-\psi|<3$.

###### Proof.

The theorem follows from the two lemmas below.

######  Lemma 3.2.

Consider a locally finite Borel graph $G$, a bounded integral Borel function
$f:V(G)\mapsto\mathbb{Z}$ and a Borel $f$-flow $\phi$. Assume that $G$ admits
a Borel connected toast. Then there is a dyadic-valued Borel $f$-flow $\psi$
such that $|\phi-\psi|<1$.

###### Proof.

Let $\mathcal{T}$ be a Borel connected toast and let
$\mathcal{M}_{1}\subset\mathcal{T}$ denote the family of minimal sets (ordered
by containment), $\mathcal{M}_{2}$ denote the family of minimal sets in
$\mathcal{T}\setminus\mathcal{M}_{1}$ etc. Obviously
$\mathcal{T}=\cup_{k=1}^{\infty}\mathcal{M}_{k}$. We define a sequence of
flows recursively. Set $\psi_{1}=\phi$. Assume that $\psi_{k}$ is a Borel
$f$-flow, $\psi_{k}$ is dyadic-valued on $\bigcup_{K\in\mathcal{M}_{k-1}}E(K)$
and $|\psi_{k}-\phi|<1$. Choose a set $K\in\mathcal{M}_{k+1}$. While there
exists an $L\subset K,L\in\mathcal{M}_{k}$ where the value of the flow is not
dyadic choose a cycle $C$ in $L\cup(K\setminus\bigcup\mathcal{M}_{k})$ such
that the value of the flow on the edges of $C$ in $L$ is not dyadic. We can
find such a cycle, since $K\setminus\bigcup\mathcal{M}_{k}$ is connected and
there is no vertex of degree one in $\bigcup\mathcal{M}_{k}$ in the spanning
subgraph of non-dyadic edges. Add a circuit to the flow that is constant on
this (oriented) cycle and zero elsewhere in such a way that after adding this
circuit at least one edge on the cycle becomes dyadic and if we are at step
$n$ of the whole construction, then the constant is smaller than
$\frac{1}{2^{n}}$. After each step, the number of edges in $L$ where the value
of the flow is dyadic increases. Hence the process will finish in at most
$|E(K)|$ steps for every $K$. The resulting $f$-flow $\psi_{k+1}$ can be Borel
and it is close enough: $|\phi-\psi_{k+1}|<1$ as the added circuits were small
enough. Note that the value of the flow does not change once it becomes
dyadic, hence the sequence $\psi_{k}$ will stabilize for every edge. The limit
$\psi$ satisfies the conditions of the lemma. ∎

######  Lemma 3.3.

Consider a locally finite Borel graph $G$, an integral bounded Borel function
$f:V(G)\mapsto\mathbb{Z}$ and a dyadic-valued Borel $f$-flow $\phi$. Assume
that $G$ admits a Borel connected toast. Then there is an integral Borel
$f$-flow $\psi$ such that $|\phi-\psi|<2$.

###### Proof.

The proof is similar to the previous one. Let $\mathcal{T}$ be a Borel
connected toast and let $\mathcal{M}_{1}\subseteq\mathcal{T}$ denote the
family of minimal sets, $\mathcal{M}_{2}$ denote the family of minimal sets in
$\mathcal{T}\setminus\mathcal{M}_{1}$ etc. We define a sequence of flows
recursively, starting with $\psi_{1}=\phi$. Assume that $\psi_{k}$ is a Borel
$f$-flow and $\psi_{k}$ is integral on $\bigcup_{K\in\mathcal{M}_{k-1}}E(K)$.
Consider a tile $K\in\mathcal{M}_{k+1}$. Let $2^{l}$ be the largest
denominator of the flow value over every edge in $\bigcup_{L\subseteq
K,L\in\mathcal{M}_{k}}E(L)$. If $l>0$ then consider the set $P$ of vertices in
$K\setminus\bigcup\mathcal{M}_{k}$ that have an odd number of neighbors in
$\bigcup_{L\subseteq K,L\in\mathcal{M}_{k}}L$ such that the value of the flow
on the corresponding edge has denominator $2^{l}$. Using Lemma 2.2 applied to
$P$ and $K\setminus\bigcup\mathcal{M}_{k}$, we get a subgraph $H_{K}$ on $K$
such that for every vertex in $K\setminus\bigcup\mathcal{M}_{k}$ its degree is
even if and only if the vertex does not belong to $P$. Taking the union of
$H_{K}$ with the graph spanned by the vertices with at least one endvertex in
$\bigcup_{L\subseteq K,L\in\mathcal{M}_{k}}V(L)$, where the denominator of the
flow is equal to $2^{l}$, we get a graph whose vertices have all even degree.
This graph partitions into a family of edge-disjoint cycles that covers every
edge in $\bigcup_{L\subset K,L\in\mathcal{M}_{k}}E(L)$ with the flow value of
denominator $2^{l}$ exactly once, and no other edge in $\bigcup_{L\subset
K,L\in\mathcal{M}_{k}}E(L)$. Choose an orientation of every cycle and add
$2^{-l}$ to the value of the flow on these cycles. Now the largest denominator
of the flow values in $\bigcup_{L\subset K,L\in\mathcal{M}_{k}}E(L)$ is at
most $2^{l-1}$. Continue this until every edge in
$\bigcup_{L\in\mathcal{M}_{k}}E(L)$ becomes integral. The resulting $f$-flow
$\psi_{k+1}$ can be constructed to be Borel, since the cycles and their
orientations can be chosen in a Borel way. The value of the flow does not
change once it becomes integral, hence the sequence $\psi_{k}$ will stabilize
for every edge. Consider an edge $e\in E(K)$ and the smallest $k$ for which
there exists $K\in\mathcal{M}_{k}$ such that $e\in E(K)$. Note that
$\psi_{k+1}(e)=\psi_{k+2}(e)=\dots$, and $\phi(e)=\psi_{k-1}(e)$.
$|\psi_{k-1}(e)-\psi_{k}(e)|<1$, since the value of the flow at $e$ can change
by less than $\sum_{l=1}^{\infty}2^{-l}$. Similarly,
$|\psi_{k}(e)-\psi_{k+1}(e)|<1$. Hence the limit
$\psi=\lim_{n\rightarrow\infty}\psi_{n}$ satisfies the conditions of the
lemma. ∎

∎

If we are interested in measurable rather than Borel flows (as we will be in
the next section), we can use the above Theorem to deduce the following more
general result on obtaining measurable integral flows from (possibly) non-
measurable ones.

######  Corollary 3.4.

Let $G$ be a locally finite one-ended hyperfinite graphing and
$f:V(G)\rightarrow\mathbb{Z}$ an integral bounded measurable function. If $G$
admits a (not necessarily measurable) real-valued bounded $f$-flow then $G$
admits an integral bounded measurable $f$-flow.

###### Proof.

Such graphings admit connected toasts a.e. by Proposition 2.4. Moreover, by
Proposition 2.1 the existence of a (not necessarily measurable) bounded real
valued $f$-flow implies the existence of a measurable bounded real valued
$f$-flow. These facts together with Theorem 3.1 give the desired result. ∎

In particular, the above result applies to the Schreier graph of any free pmp
action of a finitely generated amenable group that is not virtually
$\mathbb{Z}.$

##  4\. The uniform Gardner conjecture and the infinite dihedral group

In this section we prove Theorem 1.4. As mentioned in the introduction, the
positive part of our result will follow from Theorem 3.4 and ideas from Marks
and Unger’s Borel circle squaring proof [MU17]. In the negative direction, the
novelty is the identification of
$(\mathbb{Z}/2\mathbb{Z})*(\mathbb{Z}/2\mathbb{Z})$ as essentially the only
group that does not satisfy this strengthening of the Gardner conjecture.

We now show that the only groups without the uniform Gardner property are
those groups which admit $(\mathbb{Z}/2\mathbb{Z})*(\mathbb{Z}/2\mathbb{Z})$
as a finite quotient. Recall that an action of an infinite group is totally
ergodic if every element of infinite order acts ergodically.

######  Lemma 4.1.

Let $(\mathbb{Z}/2\mathbb{Z})*(\mathbb{Z}/2\mathbb{Z})\curvearrowright X$ be a
free pmp totally ergodic action. There is no measurable choice of an end
$e:X\to\mathrm{Ends}((\mathbb{Z}/2\mathbb{Z})*(\mathbb{Z}/2\mathbb{Z}))$ which
is invariant under the action.

###### Proof.

Suppose for a contradiction that
$e:X\to\mathrm{Ends}((\mathbb{Z}/2\mathbb{Z})*(\mathbb{Z}/2\mathbb{Z}))$ is a
measurable invariant choice of end. Write $\alpha,\beta$ for the generators of
$(\mathbb{Z}/2\mathbb{Z})*(\mathbb{Z}/2\mathbb{Z})=\langle\alpha,\beta|\alpha^{2}=\beta^{2}=1\rangle$.
Then for every $x\in X$, the function $e$ induces a choice of one of the
generators $\alpha,\beta$ pointing from $x$ in the direction of $e(x)$. Write
$A\subseteq X$ for the set of points which choose $\alpha$ and $B\subseteq X$
for the set of points which choose $\beta$. Note that $A$ and $B$ are
measurable since $e$ was measurable. Also, they alternate on every orbit,
namely $\alpha A=B$ and $\beta B=A$. Then both $A$ and $B$ are invariant under
$\alpha\beta$. However, since every element of infinite order acts
ergodically, the sets $A$ and $B$ should have measure one or zero, which is
impossible, since $\alpha$ and $\beta$ are measure-preserving. ∎

######  Lemma 4.2.

Suppose that $\Gamma$ admits
$(\mathbb{Z}/2\mathbb{Z})*(\mathbb{Z}/2\mathbb{Z})$ as a quotient by a finite
normal subgroup and $\Gamma\curvearrowright X$ is a free pmp totally ergodic
action. Then there are two measurable $\Gamma$-uniform sets of the same
measure in $X$ which are $\Gamma$-equidecomposable but not measurably
$\Gamma$-equidecomposable.

###### Proof.

Let $\Delta\lhd\Gamma$ be finite such that
$\Gamma/\Delta=(\mathbb{Z}/2\mathbb{Z})*(\mathbb{Z}/2\mathbb{Z})$. Write
$X^{\prime}=X/\Delta$. Let $G$ be the Schreier graph of the action of $\Gamma$
on $X$ and let $G^{\prime}$ be the Schreier graph of the action of
$(\mathbb{Z}/2\mathbb{Z})*(\mathbb{Z}/2\mathbb{Z})=\langle\alpha,\beta|\alpha^{2}=\beta^{2}=1\rangle$
on $X^{\prime}$. Let $A^{\prime}\subseteq X^{\prime}$ be a maximal Borel set
which is an independent set in $G^{\prime}$. Note that on each orbit of
$(\mathbb{Z}/2\mathbb{Z})*(\mathbb{Z}/2\mathbb{Z})$, the set $A^{\prime}$ has
gaps of size either $1$ or $2$. Find a Borel set $B^{\prime}$ that picks
exactly one point in each of the gaps left by $A^{\prime}$.

Let $A\subseteq X$ be a Borel set meeting each $\Delta a^{\prime}$ in exactly
one point for every $a^{\prime}\in A^{\prime}$, and let $B\subseteq X$ be a
Borel set meeting each $\Delta b^{\prime}$ in exactly one point for every
$b^{\prime}\in B$. Note that the sets $A$ and $B$ have the same positive
measure and are $\Gamma$-uniform.

To see that $A$ and $B$ are not measurably $\Gamma$-equidecomposable, we first
argue about $A^{\prime}$ and $B^{\prime}$.

######  Claim 4.3.

$A^{\prime}$ and $B^{\prime}$ are not measurably
$(\mathbb{Z}/2\mathbb{Z})*(\mathbb{Z}/2\mathbb{Z})$-equidecomposable.

###### Proof.

Indeed, suppose that such a measurable
$(\mathbb{Z}/2\mathbb{Z})*(\mathbb{Z}/2\mathbb{Z})$-equidecomposition exists.
Then using such an equidecomposition, we can form a measurable bounded integer
$G^{\prime}$-flow $\psi$ for the function
$\chi_{A^{\prime}}-\chi_{B^{\prime}}$. Such a flow induces a measurable
perfect matching between $A^{\prime}$ and $B^{\prime}$ by matching $x\in
A^{\prime}$ to the point in $B^{\prime}$ that is on the side of the edge
$(x,y)$ adjacent to $x$ for which $\psi(x,y)>0$. Now, a measurable perfect
matching between $A^{\prime}$ and $B^{\prime}$ leads to a measurable invariant
choice of an end for this action. Namely, the matching restricted to every
orbit separately has to match every point $x\in A^{\prime}$ to the point $y\in
B^{\prime}$ such that the direction from $x$ to $y$ determines one of the
ends. This choice of an end does not depend on $x\in A^{\prime}$, so it is
invariant under the action. As we assume that the action is totally ergodic,
we get a contradiction with Lemma 4.1. ∎

Now, the above claim gives that there is no $\Gamma$-equidecomposition between
$A$ and $B$ because such an equidecomposition would lead to a measurable
$(\mathbb{Z}/2\mathbb{Z})*(\mathbb{Z}/2\mathbb{Z})$-equidecomposition between
$A^{\prime}$ and $B^{\prime}$. ∎

######  Corollary 4.4.

If $\Gamma$ admits $(\mathbb{Z}/2\mathbb{Z})*(\mathbb{Z}/2\mathbb{Z})$ as a
quotient by a finite normal subgroup then $\Gamma$ does not have the uniform
Gardner property.

###### Proof.

This follows directly from Lemma 4.2 by considering a totally ergodic action
of $\Gamma$. ∎

Now we deal with groups which have the uniform Gardner property.

######  Proposition 4.5.

Let $\Gamma$ be an amenable group. If $\Gamma$ is one-ended or has a finite
normal subgroup $\Delta\lhd\Gamma$ with $\Gamma/\Delta=\mathbb{Z}$, then it
has the uniform Gardner property.

###### Proof.

Suppose $\Gamma\curvearrowright X$ is a free Borel action and $A,B\subseteq X$
are measurable, $\Gamma$-uniform and equidecomposable. Let $c$ be a constant
witnessing that $A$ and $B$ are $\Gamma$-uniform.

Note that if $\Gamma/\Delta=\mathbb{Z}$ for a finite normal subgroup
$\Delta\lhd\Gamma$, then any free action $\Gamma\curvearrowright X$ admits a
measurable choice of an end in any orbit. Since $A$ and $B$ are
equidecomposable, there exists an integral $(\chi_{A}-\chi_{B})$-flow bounded
by $1$. We can also get a measurable, integral $(\chi_{A}-\chi_{B})$-flow
$\psi$ bounded by $4$ in the one-ended case by Corollary 3.4.

By the result of Conley, Jackson, Kerr, Marks, Seward and Tucker-Drob
[CJK+18], we can choose a tiling $\mathcal{T}$ of the space with
$\frac{c}{4}$-Følner sets. Since $A$ and $B$ are $\Gamma$-uniform, we have
$|T\cap A|,|T\cap B|\geq c|T|$ for every tile $T\in\mathcal{T}$.

For every pair of tiles $T,S\in\mathcal{T}$ which are adjacent put $\psi(S,T)$
to be the sum of all $\psi(e)$ for edges $e$ starting at a point in $S$ and
ending at a point in $T$. Note that for each tile $T\in\mathcal{T}$ we have
that $|A\cap T|,|B\cap T|$ are bigger than the sum of $\psi(T,S)$ for all
tiles $S$ adjacent to $T$. Therefore, we can move points in a measurable way
from $A$ and $B$ between the tiles as indicated by $\psi$, so after that in
each tile there will be the same number of points from $A$ and $B$. Any
measurable choice of bijections in the tiles gives a measurable
equidecomposition. ∎

Finally, we prove Theorem 1.4.

###### Proof of Theorem 1.4.

Any infinite amenable group has one or two ends (see for instance [Poé74,
Théorème 10 and Chapitre V]). First note that in the one-ended case $\Gamma$
does not admit $(\mathbb{Z}/2\mathbb{Z})*(\mathbb{Z}/2\mathbb{Z})$ as a
quotient by a finite subgroup and it satisfies the uniform Gardner property by
Proposition 4.5.

Thus, we only focus on the two-ended case. If $\Gamma$ has two ends then by
[SW79, Theorem 5.12] it has a finite normal subgroup $\Delta$ such that
$\Gamma/\Delta$ is either isomorphic to $\mathbb{Z}$ or to
$(\mathbb{Z}/2\mathbb{Z})*(\mathbb{Z}/2\mathbb{Z})$. If
$\Gamma/\Delta=\mathbb{Z}$, then we are done again by Proposition 4.5. In the
second case, Corollary 4.4 implies the theorem. ∎

## References

  * [BKS21] Matthew Bowen, Gabor Kun, and Marcin Sabok, _Perfect matchings in hyperfinite graphings_ , arXiv preprint arXiv:2106.01988 (2021).
  * [BPZ22] Matthew Bowen, Antoine Poulin, and Jenna Zomback, _One-ended spanning trees and definable combinatorics_ , arXiv preprint arXiv:2210.14300 (2022).
  * [BT24] S. Banach and A. Tarski, _Sur la décomposition des ensembles de points en parties respectivement congruentes_ , Fund. Math 6 (1924), no. 1, 244–277.
  * [CJK+18] Clinton T. Conley, Steve C. Jackson, David Kerr, Andrew S. Marks, Brandon Seward, and Robin D. Tucker-Drob, _Følner tilings for actions of amenable groups_ , Math. Ann. 371 (2018), no. 1-2, 663–683.
  * [CM16] Clinton T. Conley and Benjamin D. Miller, _A bound on measurable chromatic numbers of locally finite Borel graphs_ , Math. Res. Lett. 23 (2016), no. 6, 1633–1644.
  * [CS] Tomasz Cieśla and Marcin Sabok, _Measurable Hall’s theorem for actions of abelian groups_ , preprint, arXiv:1903.02987.
  * [DP96] Jean-Dominique Deuschel and Agoston Pisztora, _Surface order large deviations for high-density percolation_ , Probab. Theory Related Fields 104 (1996), no. 4, 467–482.
  * [Gar91] R. J. Gardner, _Measure theory and some problems in geometry_ , Atti Sem. Mat. Fis. Univ. Modena 39 (1991), no. 1, 51–72.
  * [GJ15] Su Gao and Steve Jackson, _Countable abelian group actions and hyperfinite equivalence relations_ , Invent. Math. 201 (2015), no. 1, 309–383.
  * [GJKS15] S. Gao, S. Jackson, E. Krohne, and B Seward, _Forcing constructions and countable borel equivalence relations_ , preprint, 2015, available at https://itservices.cas.unt.edu/ sgao/pub/pub.html.
  * [GJKS18] by same author, _Continuous combinatorics of abelian group actions_ , preprint, arXiv:1803.03872.
  * [GMP17] Łukasz Grabowski, András Máthé, and Oleg Pikhurko, _Measurable circle squaring_ , Ann. of Math. (2) 185 (2017), no. 2, 671–710.
  * [Lac88] Miklós Laczkovich, _Closed sets without measurable matching_ , Proc. Amer. Math. Soc. 103 (1988), no. 3, 894–896.
  * [Lac90] by same author, _Equidecomposability and discrepancy; a solution of Tarski’s circle-squaring problem_ , J. Reine Angew. Math. 404 (1990), 77–117.
  * [Lac92] by same author, _Uniformly spread discrete sets in ${\bf R}^{d}$_, J. London Math. Soc. (2) 46 (1992), no. 1, 39–57.
  * [Lac96] by same author, _Decomposition using measurable functions_ , C. R. Acad. Sci. Paris Sér. I Math. 323 (1996), no. 6, 583–586.
  * [Mát18] András Máthé, _Measurable equidecompositions_ , Proceedings of the International Congress of Mathematicians—Rio de Janeiro 2018\. Vol. III. Invited lectures, World Sci. Publ., Hackensack, NJ, 2018, pp. 1713–1731.
  * [MNP22] András Máthé, Jonathan A Noel, and Oleg Pikhurko, _Circle squaring with pieces of small boundary and low borel complexity_ , arXiv preprint arXiv:2202.01412 (2022).
  * [MU17] Andrew S. Marks and Spencer T. Unger, _Borel circle squaring_ , Ann. of Math. (2) 186 (2017), no. 2, 581–605.
  * [Poé74] Valentin Poénaru, _Groupes discrets_ , Lecture Notes in Mathematics, Vol. 421, Springer-Verlag, Berlin-New York, 1974.
  * [SW79] Peter Scott and Terry Wall, _Topological methods in group theory_ , Homological group theory (Proc. Sympos., Durham, 1977), London Math. Soc. Lecture Note Ser., vol. 36, Cambridge Univ. Press, Cambridge-New York, 1979, pp. 137–203.
  * [Tar25] Alfred Tarski, _Probléme 38_ , Fund. Math. 7 (1925).
  * [vN29] John von Neumann, _Zur allgemeinen theorie des masses_ , Fund. Math. 13 (1929), no. 1, 73–116.
  * [Weh92] Friedrich Wehrung, _Injective positively ordered monoids. I, II_ , J. Pure Appl. Algebra 83 (1992), no. 1, 43–82, 83–100.