List-encoding CCDM: A Nonlinearity-tolerant Shaper Aided by Energy Dispersion Index

Kaiquan Wu, Student Member, IEEE, Gabriele Liga, Member, IEEE, Alireza Sheikh, Member, IEEE, Yunus Can Gültekin, Member, IEEE, Frans M. J. Willems, Life Fellow, IEEE, and Alex Alvarado, Senior Member, IEEE
This work is supported by the Netherlands Organisation for Scientific Research via the VIDI Grant ICONIC (project number 15685). The work of Alex Alvarado is supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 757791). The work of G. Liga is supported by the EuroTechPostdoc programme under the European Union’s Horizon 2020 research and innovation programme (Marie Skłodowska-Curie grant agreement No. 754462).
The authors are with the Information and Communication Theory Lab, Signal Processing Systems Group, Department of Electrical Engineering, Eindhoven University of Technology, Eindhoven 5600 MB, The Netherlands (e-mails: {k.wu, g.liga, a.sheikh, f.m.j.willems, y.c.g.gultekin, a.alvarado}@tue.nl).
A. Sheikh is with imec, Holst Centre, High Tech Campus 31, 5656 AE Eindhoven, The Netherlands (email: alireza.sheikh@imec.nl).

Preprint, August 27, 2024
Shell et al.: Bare Demo of IEEEtran.cls for IEEE Journals

Recently, a metric called energy dispersion index (EDI) was proposed to indicate the nonlinear interference (NLI) induced by correlated symbols during optical transmission. In this paper, we propose a new shaper architecture to decrease the EDI of transmitted symbols and thus, increase the signal-to-noise ratio (SNR).
We call this shaper the list-encoding constant-composition distribution matcher (L-CCDM). L-CCDM consists of an additional EDI selecting module, which is compatible with standard probabilistic amplitude shaping (PAS) architecture. Numerical results obtained from a multi-span multi-channel system show that when compared to standard CCDM with 256-ary quadrature amplitude modulation (256QAM), the proposed architecture offers an effective SNR gain of $0.35$ dB, an achievable information rate gain of $0.22$ bit/4D-symbol, or equivalently an $8\%$ reach extension.

Constant-Composition Distribution Matching, Fiber Nonlinearities, Probabilistic Amplitude Shaping.

§ INTRODUCTION

Probabilistic amplitude shaping (PAS) <cit.> has attracted wide attention in the domain of fiber optical communications. Numerous studies about PAS have been carried out in simulation <cit.>, experiments <cit.> and field trials <cit.>. PAS realizes probabilistic shaping by means of an amplitude shaper. One popular amplitude shaper is the constant-composition distribution matcher (CCDM) <cit.>. Other well-known shapers include multiset-partition distribution matcher (MPDM) <cit.>, product distribution matcher (PDM) <cit.>, and enumerative sphere shaping (ESS) <cit.>.

Tailored to the additive white Gaussian noise (AWGN) channel, the aforementioned amplitude shapers were initially designed for the purpose of generating nonuniformly distributed amplitudes. However, unlike the AWGN channel, in the nonlinear fiber channel, nonlinear interactions among the transmitted symbols occur. These interactions lead to nonlinear interference (NLI) noise. As a result, the AWGN-optimal PAS usually enhances the NLI with respect to uniform signaling <cit.>. Therefore, NLI-tolerant shaping architectures, which improve power efficiency and also combat the NLI penalty, are of great interest.

The amplitude shaper determines the probability distribution as well as the temporal structure of the transmitted symbols. For the design of NLI-tolerant amplitude shapers, one approach is to optimize the probability distribution of input symbols, while assuming the symbols to be independent identically distributed (i.i.d.). With the advent of the enhanced Gaussian noise (EGN) model, the fourth standardized moment (a.k.a. kurtosis) of transmitted symbols has been widely accepted as a metric that indicates the NLI magnitude <cit.>. In <cit.>, an optimized probability mass function for a nonlinear fiber channel is designed taking kurtosis into account. In <cit.>, symbol sequences having low kurtosis are generated to mitigate the NLI.

Instead of optimizing distributions, one can manipulate the temporal structure of the symbol sequences, with the goal of reducing the NLI. This follows from the fact that the transmitted symbols that have certain temporal structures could exert great influence on the NLI <cit.>. A straightforward approach for improving the NLI tolerance with this temporal approach was to use short shaping blocklengths <cit.>. This nonlinear shaping gain enabled by short shaping blocklengths was intuitively attributed to the fact that the generated symbol sequences have fewer clusters of identical symbols <cit.>. However, a guiding principle for the temporal structure of symbol sequence was missing. Recently, we proposed in <cit.> a metric called energy dispersion index (EDI) to accurately indicate the NLI of correlated symbol sequences, where strong correlation between EDI and effective signal-to-noise ratio (SNR) was reported. The main contribution of the current paper is to propose the first NLI-tolerant signaling scheme designed based on the EDI.

In this paper, we first review PAS and CCDM as well as EDI in Sec. <ref>. Then, in Sec. <ref>, an amplitude shaper referred to as list-encoding CCDM (L-CCDM) is proposed. By exploiting the EDI diversity of the symbol sequences, L-CCDM improves NLI tolerance through EDI selection. In Sec. <ref>, the numerical results based on a multi-channel multi-span system show that with 256-ary quadrature amplitude modulation (256QAM), L-CCDM offers an effective SNR gain of $0.35$ dB with respect to CCDM. This SNR gain translates into an $8\%$ reach extension. Finally, conclusions are drawn in Sec. <ref>.

§ PRELIMINARIES

§.§ PAS and CCDM

Block diagram of PAS at the transmitter using 1D symbol mapping, where $\jmath$ is the imaginary unit. L-CCDM is to be placed at the dashed blue area.

Fig. <ref> displays a standard PAS architecture. The top and bottom branches show the generation of shaped pulse amplitude modulation (PAM) symbols for in-phase and quadrature dimensions of QAM symbols, respectively. This PAS structure corresponds to the so-called “1D symbol mapping strategy” <cit.>. For each branch, the generation of shaped PAM symbols, relying on an amplitude shaper and a systematic forward error correction (FEC) engine, can generally be described as follows. A sequence of information bits go through the amplitude shaper to yield nonuniformly distributed amplitudes. Next, the bits that represent these amplitudes, along with the top sequence of information bits, are fed into the FEC engine. The parity bits of the FEC codewords and the top sequence of information bits are transformed into sign bits, i.e., using $(0,1)\to(+1,-1)$. PAM symbols are generated by combining these signs with the amplitudes. Finally, two sequences of PAM symbols are assigned as the real and imaginary parts of a sequence of QAM symbols.

The amplitude sequences in the CCDM codebook $\mathcal{C}$ have a constant amplitude composition. Given an amplitude set $\mathcal{A}$ and blocklength $n$, the number of amplitudes $a$ for each codeword is a constant denoted by $n_{a}$, and thus, $n = \sum_{a\in\mathcal{A}} n_{a}$. For any CCDM codeword $\boldsymbol{A} = (A_1, A_2, \dotsc, A_n)$, the empirical amplitude distribution is fixed to be $\Prob_{A}(a)=n_{a}/n$ for $a\in\mathcal{A}$.

The shaping rate is defined as $R_s \triangleq k/n$ bits per amplitude (bit/amplitude). A finite-blocklength amplitude shaper will cause a non-zero rate loss. Let $H(\Prob_{A})$ denote the entropy of $\Prob_{A}$. Then the rate loss (in bits per amplitude) is defined in <cit.> as

\begin{equation}
\label{RateLoss}
R_{L} \triangleq H(\Prob_{A})-\frac{k}{n}.
\end{equation}

Window energy sequence $[G_{1+W/2}^W,G_{2+W/2}^W,\ldots,G_{n-W/2}^W]$ based on the symbol sequence $[X_1,X_2,\ldots,X_n]$.

[L-CCDM in the PAS transmitter.
[L-CCDM in the PAS receiver.
[EDI vs. flipping bit number $v$.
(a) Block diagram of L-CCDM in the PAS transmitter. Given $v$ flipping bits, each CCDM outputs $2^v$ possible amplitude codewords. Two sets of $2^v$ amplitudes codewords yield $2^{2v}$ candidate QAM symbol blocks. The corresponding optimal amplitude codewords $\boldsymbol{a}^*_{I}$ and $\boldsymbol{a}^*_{Q}$ are chosen for transmission. (b) Block diagram of the L-CCDM receiver. Given estimated amplitude codewords $\hat{\boldsymbol{a}}^*_{I}$ and $\hat{\boldsymbol{a}}^*_{Q}$, L-CCDM discard the decoded $v$ flipping bits and output $k-v$ decoded information bits. (c) EDI vs. flipping bit number $v$, when the flipping bits in L-CCDM ($n=180$, $R_s=1.85$, $W=10$) are appended as the prefix and the suffix of the binary inputs, respectively.

§.§ Energy Dispersion Index

EDI was designed to be a moving window statistic that measures the windowed energy fluctuation in a sequence of symbols $\boldsymbol{X}=[\ldots,X_i,X_{i+1},\ldots]$. For a given window length $W$ ($W$ is an even natural number), let $G_{i}^{W}$ denote the sum of $W+1$ symbol energies centered around the symbol $X_i$, i.e., $\WE_{i}\triangleq \sum_{j=i-W/2}^{i+W/2} |X_{j}|^2$. Based on this windowed energy process, EDI is defined as the ratio of the variance of the windowed energy to the mean of the windowed energy, both averaged over $i = 1, 2,\cdots, n$ <cit.>, i.e.,

\begin{equation}\label{EDI}
\Psi \triangleq\frac{\AvgVar{\WE}}{\AvgExp{\WE}},
\end{equation}

\begin{align}
\AvgExp{\WE} &\triangleq \frac{1}{n} \sum_{i=1}^{n}  \Exp{\WE_i}, \label{AvgExpWe}\\
\AvgVar{\WE} &\triangleq  \frac{1}{n} \sum_{i=1}^{n} \Var{\WE_i}. \label{AvgVarWe}
\end{align}

The expressions in (<ref>)–(<ref>) show that EDI takes non-i.i.d. symbols into account.

In general, with a proper window length, the lower the EDI of transmitted symbols, the less NLI is to be induced <cit.>.
EDI classifies phase-shift keying (PSK) as one of the “best” NLI-tolerant modulation formats, since the total energy within the window is always the same, yielding zero energy variations. For QAM modulation formats, if the transmitted symbols $\boldsymbol{X}$ are i.i.d., the EDI is simply determined by average symbol energy and kurtosis <cit.>. For the more general case of non-i.i.d. QAM symbols, EDI is also dependent on the window length $W$ since the correlations between symbols within the window can vary for different $W$.

In the case of non-i.i.d. QAM symbols, an accurate indication of the NLI magnitude is obtained by EDI with an optimized window length $W$. However, <cit.> shows that the EDI is relatively insensitive to the $W$, which means that it can still show the general impact of the energy variations on the NLI without the optimization of $W$.

EDI in (<ref>) describes the asymptotic energy variation behavior of the transmitted symbol sequences. In practice, we are more interested in the NLI-tolerance of one realization of symbol sequence, and thus the EDI of an individual sequence should be measured. Fig. <ref> shows that given a realization of windowed energy sequence $\boldsymbol{G}=\boldsymbol{g}=[g_{1+W/2}^W,g_{2+W/2}^W,\ldots,g_{n-W/2}^W]$ is obtained based on a realization of an $n$-length symbol sequence $\boldsymbol{X}=\boldsymbol{x}=[x_1,x_2,\ldots,x_n]$. Note that the window length $W$ should be smaller than the blocklength $n$. Then, given $\boldsymbol{g}$, the EDI $\hat{\Psi}$ can be estimated numerically as

\begin{equation}
\label{EDIEst}
\hat{\Psi}(\boldsymbol{x}) \triangleq \frac{\TVar{\WE}}{\TExp{\WE}},
\end{equation}

where $\TExp{\WE}$ is the estimated windowed energy mean, i.e.,

\begin{equation}
\label{WndMeanEst}
\TExp{\WE} = \frac{\sum_{i=1+W/2}^{n-W/2}g_{i}^W}{n-W},
\end{equation}

and $\TVar{\WE}$ is the estimated windowed energy variance, i.e.,

\begin{equation}
\label{WndVarEst}
\TVar{\WE} = \frac{\sum_{i=1+W/2}^{n-W/2}(g_{i}-\TExp{\WE})^2}{n-W-1}.
\end{equation}

§ LIST-ENCODING CCDM

In this section, we will introduce L-CCDM as a method to generate QAM symbol sequences with low EDI. The amplitude sequence codebook $\mathcal{C}$ of a standard CCDM with blocklength $n$ and shaping rate $R_s = k/n$ consists of $2^k$ amplitudes codewords. Even for small $n$, e.g., $n\geq 16$ and $R_s \geq 1.5$, there are usually $2^k \geq 2^8$ sequences with a wide variety of temporal structures, and thus, also potentially large EDI variations. Therefore, it is reasonable to assume that some of the codewords are more beneficial to NLI fiber transmission than the others. Based on this observation of EDI diversity in the codebook, a straightforward approach to realize NLI mitigation is to select and use a subset of NLI-tolerant (low-EDI) symbol sequences.

§.§ Principle

In the PAS architecture using 1D symbol mapping as shown in Fig. <ref>, the proposed L-CCDM replaces the amplitude shapers with red inputs and outputs.
Fig. <ref>(a) displays the block diagram of L-CCDM at the transmitter. L-CCDM is built based on standard CCDMs, and it selects amplitude codewords that generate low-EDI symbol sequences.
For any given $k-v$ bit input sequence of a CCDM, we insert $v$ flipping bits.
As flipping bit changes between 0 and 1, CCDM produces $2^v$ candidate amplitude sequences from its codebook depending on the values of these flipping bits. Therefore, the shaping rate of L-CCDM is thus $R_s=(k-v)/n$.
We note that this can be done by using a single CCDM $2^v$ times, or using $2^v$ CCDMs at once.

We denote these candidate sequences at the outputs of CCDMs in Fig. <ref> by $\boldsymbol{a}^{i}_{I}=[a^{i}_{I,1},a^{i}_{I,2},\ldots,a^{i}_{I,n}]$ and $\boldsymbol{a}^{j}_{Q}=[a^{j}_{Q,1},a^{j}_{Q,2},\ldots,a^{j}_{Q,n}]$ for the in-phase and quadrature branches, respectively, where $i, j = 1, 2,\dotsc, 2^v$.

Then L-CCDM generates $2^{2v}$ QAM symbol sequence candidates considering all possible combinations of $\boldsymbol{a}^{i}_{I}$ and $\boldsymbol{a}^{j}_{Q}$.
Since these candidates will only be used to compute EDIs, this generation requires no sign bits from the systematic FEC engine.

As a result, these “pseudo” QAM symbol sequence candidates are given as $\boldsymbol{x}_{i,j}=\boldsymbol{a}_{I}^{i}+\jmath\boldsymbol{a}_{Q}^{j}$.
We denote the set of $2^{2v}$ QAM symbol sequence candidates by $\mathcal{S}=\{\boldsymbol{x}_{i,j}: (i,j)\in\{1,2,\ldots,2^v\}^2\}$.

Next, the EDIs of all the candidate symbol blocks are measured, and L-CCDM chooses the “best” candidate $\boldsymbol{x}^{*}$ that has the smallest EDI, i.e.,

\begin{equation}
\boldsymbol{x}^{*} = \argmin_{\boldsymbol{x}\in \mathcal{S}} \hat{\Psi}(\boldsymbol{x}).
\end{equation}

Finally, the selected QAM symbol block $\boldsymbol{x}^{*}=\boldsymbol{a}^{*}_{I}+\jmath\boldsymbol{a}^{*}_{Q}$ determines the output amplitude codewords $\boldsymbol{A}_{I}=\boldsymbol{a}^{*}_{I}$ and $\boldsymbol{A}_{Q}=\boldsymbol{a}^{*}_{Q}$, which are later processed by standard PAS procedure as explained in Fig. <ref>. Fig. <ref>(b) shows that at the receiver, the only modification required is to merely discard the flipping bits after the standard CCDM decoding of estimated amplitude codewords $\hat{\boldsymbol{a}}^*_{I}$ and $\hat{\boldsymbol{a}}^*_{Q}$. With minor changes on the PAS architecture, L-CCDM generates symbol blocks with lower EDI than that of the corresponding CCDM.

L-CCDM is designed to only improve the blockwise EDI, i.e., symbols from previous and future codewords are not taken into account when computing the EDI. One drawback of L-CCDM is therefore that inter-block effects are neglected. However, such inter-block effects are expected to be marginal if the blocklength is relatively large.

§.§ Flipping Bits Insertion and Rate Loss

The QAM symbol sequence candidates are desired to be as different as possible in terms of their EDI, in order to maximize the gains in NLI-tolerance that we can obtain.
A CCDM indexes constant composition sequences using a lexicographical ordering for both its input and output <cit.>.

As a result, compared to the bits at the end of the binary input, flipping the bits at the beginning is more important in changing the temporal structure of two candidate amplitude codewords.
In the next example, we will show that appending the flipping bits to the binary inputs as a prefix is more efficient to reduce EDI using L-CCDM.

A Mapping Example of CCDM's Input and Output.

Bits Input     Amplitudes Output

$1111111111$     $7553331111$

$\vdots$      $\vdots$

$1000000000$     $3153153117$

$\vdots$      $\vdots$

$0000000001$     $1111333575$

$0000000000$     $1111333557$

Example: Given a CCDM with $k=10$, $n=10$, and amplitude composition $[4, 3, 2, 1]$ for the amplitudes $\{1,3,5,7\}$, the mapping between the binary inputs and amplitude codewords is shown in Table <ref>. For $v=1$ flipping bit, if $k-v=9$ information bits are all zeros, the two amplitude codewords corresponding to bit sequences $[0,\ldots,0,B]$, $B\in\{0,1\}$ only differ two amplitudes at the end. By comparison, the two amplitude codewords corresponding to $[B,0,\ldots,0]$ have more difference. Fig. <ref>(c) also clearly shows that when $n=180$, with respect to the suffix approach, the prefix approach reduces the EDI as $v$ increases. For $v=4$ flipping bits, the average EDI obtained with the prefix approach is $1.65$ dB less that the suffix approach.

The inserted flipping bits cause an additional rate loss with respect to standard CCDM. The rate loss of L-CCDM is

\begin{equation} \label{RateLoss2}
R_{L}^{\textrm{List}}  = \underbrace{H(\Prob_{A})- \frac{k}{n}}_{\text{Eq.~\eqref{RateLoss}}}
+ \underbrace{\frac{v}{n}}_{\text{Flipping bit loss}},
\end{equation}

which includes an extra rate loss term $v/n$ that accounts for the effect of flipping bits. Note that $R_{L}$ in (<ref>) can be seen as a special case of $R_{L}^{\textrm{List}}$ when $v=0$.

In L-CCDM, $v$ and $n$ can be used to trade performance for complexity or vice versa.
For example, for a fixed $v$, if $n$ is large enough, the additional rate loss $v/n$ of L-CCDM in (<ref>) is negligible.
However, increasing $n$ typically causes an increased complexity in shaping and deshaping <cit.>.
On the other hand, for a fixed $n$, using more flipping bits means more QAM symbol sequence candidates to select among and a possibly larger reduction in average EDI.
This increase in $v$, however, requires extra $2^v-1$ CCDM encoding instances.
The EDI measurement also requires some computational power.
Therefore, the parameters of L-CCDM should be chosen carefully in order to reach a favorable trade-off between performance and complexity.

Simulation Parameters.

Parameter     Value

Modulation     $256$QAM

Polarization     Single

Center wavelength ($\lambda$)      1550 nm

Symbol rate     $32$ GBd

WDM spacing ($\Delta f$)     $50$ GHz

# WDM channels ($N_{\mathrm{ch}}$)     11

Pulse shape     Root-raised cosine

Pulse roll-off     $10\% $

Span length     $80$ km

Fiber loss     $0.2$ dB/km

Dispersion parameter ($D$)     $17$ ps/nm/km

Nonlinear parameter ($\gamma$)     $1.37$ 1/W/km

EDFA noise figure     $6$ dB

Oversampling factor     $2$

Parameters of 256QAM Uniform Signaling and PAS.

Parameter     2c|Uniform     4cPAS
$R_c$     $2/3$     $3/5$     4c$4/5$
$R_s$     2c|-     2.2     2.3     2.4     2.5
Total $R$ (bit/4D-sym)     $9.6$     $10.7$     $9.6$     $10$     $10.4$     $10.8$
Info. Rate (Gbps)     $307$     $342$     $307$     $320$     $333$     $346$

Performance analysis of L-CCDM and standard CCDM ($n=1800$) at $1600$ km. The 256QAM symbol sequences are generated by PAS using standard CCDM ($v=0$) or L-CCDM ($v=1,2,\ldots,4$ with window length $W=100$). (a) Effective SNR vs. launch power, where the inset shows EDI $\hat{\Psi}$ vs. $v$. (b) For $v=0$ and $v=4$, the scatter of per-shaping block effective SNR vs. EDI, and the insets further show the histogram of per-shaping block effective SNR and EDI. (c) AIR vs. launch power. (d) BER vs. launch power. The filled triangles in (a), (c) for $v=0,4$ correspond to the same triangle points as shown in Fig. <ref>(a)–(b).

§ NUMERICAL ANALYSIS

§.§ Simulation Setup

The performance of PAS using 256QAM with standard CCDM or L-CCDM is analyzed in a multi-span wavelength division multiplexing (WDM) optical communication system. The key parameters of the fiber simulation are displayed in Table <ref>. The simulation is implemented by using the split-step Fourier method. The channel of interest is situated in the center of the WDM band. All channels use the same signaling scheme, and the signal on each channel is independently generated with the root-raised cosine pulse shaping. After propagation over each span of standard single-mode fiber, the attenuation is compensated by an Erbium-doped fiber amplifier (EDFA). At the receiver, the channel of interest is filtered with a matched filter, and chromatic dispersion compensation.

The binary low-density parity check codes from the DVB-S2 standard <cit.> with codeword length $64800$ is used as the FEC code.
At the receiver, 50 decoding iterations are realized. The number of flipping bits $v=0$ corresponds to standard CCDM. Shaping blocklengths from $n=180$ to $n=5400$ are evaluated. We choose window length $W=100$ and note that the EDI measurement is insensitive to the value of $W$.
At most $v=4$ flipping bits are considered, which generates up to $16$ amplitude sequence candidates and cause an extra rate loss of $2.22\times10^{-3}$ bit/amplitude, and thus, the complexity increase is not too much.
To make a fair comparison between different values of $v$ <cit.>, Maxwell-Boltzmann distribution $\Prob_{A}$ with slightly larger entropy $H(\Prob_{A})$ is used by L-CCDM to cover the additional rate loss due to flipping bits $v/n$, such that L-CCDM has the same shaping rate $R_s=(k-v)/n$ as that $R_s=k/n$ of standard CCDM, see (<ref>) and (<ref>).
For example, at $n=1800$, to achieve $R_s= 2.4$ bit/amplitude, CCDM and L-CCDM ($v=4$) have $H(\Prob_{A})=2.4189$ and $2.4205$ bits, respectively. Table <ref> shows the parameters for uniform signaling and PAS that achieve various rates.

To quantify the performance improvement obtained with L-CCDM, we evaluated the effective SNR, achievable information rate (AIR) and end-to-end bit-error rate (BER).
Regarding AIR, we used “finite-blocklength" bit-metric decoding (BMD) rate (bit/4D-sym) as the figure of merit for 256QAM PAS, which accounts for the rate loss $R^{\textrm{List}}_{L}$ in (<ref>) as  <cit.>)

\begin{equation} \label{AIRN}
\mathrm{AIR}_{\mathrm{n}}=4\left[H(X)-\sum_{i=1}^{4} H\left(B_{i} \mid Y\right)\right]-  4R^{\textrm{List}}_{L},
\end{equation}

where $B_{i}$ is a random variable representing the $i$-th binary label of the 16PAM symbol, and $Y$ is the received symbol.

§.§ Performance at Fixed Transmission Distance

Fig. <ref>(a) displays effective SNR vs. launch power at the transmission distance of $1600$ km for $n=1800$.
The total transmission rate is fixed at $R=10.4$ bit/4D-symbol with $R_s= 2.4$ bit/amplitude.
The inset figure shows that the EDI of transmitted symbols indeed decreases when more flipping bits are used. While the EDI of standard CCDM ($v=0$) is $-0.66$ dB, L-CCDM suppresses the EDI down to $-4.03$ dB at $v=4$.
This decrease in EDI results in an effective SNR gain of $0.35$ dB. The optimal launch power for L-CCDM with $v=4$ is $-3.5$ dBm, which is $0.5$ dB higher than that of CCDM.

Fig. <ref>(b) further visualizes how the effective SNR is improved by L-CCDM.
Compared with CCDM, L-CCDM with $v=4$ on average pick $1/16$ NLI-tolerant amplitude sequences from codebook. To keep the same shaping rate, L-CCDM has to use a composition with slightly larger entropy than that of CCDM, and thus a larger amplitude sequence codebook. This allows L-CCDM to move the EDI distribution to a lower level, as shown in the top-right histogram inset.
As a result, the per-block effective SNR cloud of L-CCDM is located around a higher SNR value and is more concentrated, which can also be observed from the bottom left histograms inset.

In Fig. <ref>(c), it can be seen that the AIR curves almost follow the same behaviour as the SNR curves in (a). This indicates that most of the effective SNR gains by L-CCDM translate into AIR gains, and the flipping rate loss is negligible. With $v=4$, the AIR gains can be up to $0.22$ bit/4D-symbol.
Fig. <ref>(d) shows that thanks to the NLI reduction, L-CCDM outperforms standard CCDM in terms of BER. From $-4.25$ dBm to $-3$ dBm, L-CCDM with $v=3,4$ achieves BER below $1\times10^{-4}$.

Performance analysis of L-CCDM ($v=4$) and standard CCDM ($v=0$) at $1600$ km. The 256QAM symbol sequences are generated by PAS using standard CCDM or L-CCDM ($W=100$) with blocklengths $n\in\{180,200,300,600,900,1080,1350,1620,1800,2025,2700,5400\}$. (a) Effective SNR vs. blocklength $n$, where the inset shows the corresponding EDI $\hat{\Psi}$ vs. $n$. (b) AIR vs. blocklength $n$. The filled triangles in (a)–(b) for $v=0,4$ correspond to the same triangle points as shown in Fig. <ref>(a), (c).

§.§ Blocklength-dependency

As mentioned in Sec. III, the parameters of L-CCDM should be carefully chosen to reach a favorable trade-off between the effective SNR gains and rate loss.
Here, we consider the performance of L-CCDM for various blocklengths $n$.
The results for each blocklength are obtained at the optimal launch power.
Fig. <ref>(a) shows the blocklength-dependent effective SNR at $1600$ km.
This blocklength-dependency has been investigated for CCDM in <cit.>.
We show here that L-CCDM also exhibits a similar blocklength-dependent behaviour, except that the effective SNR is increased by approximately $0.38$ dB for all values of $n$ considered here.
Larger $n$ yields lower effective SNR for both CCDM and L-CCDM, and we attribute this to the increase in the corresponding EDIs, which is self-evident in the inset figure of Fig. <ref>(a). Since sequences with lower EDI are selected, L-CCDM generally generates higher SNR than standard CCDM, and these effective SNR gains become slightly larger in the long blocklength regime. Fig. <ref>(b) shows that even with the additional rate loss of flipping bits in (<ref>), the AIR of L-CCDM benefits from the increased NLI-tolerance with gains up to $0.23$ bit/4D-sym at the optimum blocklength $n = 1350$ with respect to that of CCDM.
For other blocklengths, Fig. <ref>(b) shows that the AIR gains of L-CCDM decrease (i) because for shorter blocklengths, flipping bit rate loss $v/n$ in (<ref>) becomes significant, and (ii) for longer blocklengths effective SNR decreases.

AIR vs. transmission distance for 256QAM. The parameters of PAS using standard CCDM and L-CCDM as well as uniform 256QAM are shown in Table <ref>.

§.§ Reach Increase

Fig. <ref> shows the AIR at various transmission distances for PAS using L-CCDM or CCDM (both with $n=1800$), and uniform signaling, respectively.
Fig. <ref> also shows the distance where the BER of uniform signaling and PAS is below $10^{-4}$ (indicated by markers).
All of the results are obtained at the corresponding optimal launch powers.
The transmission rate of uniform 256QAM is adjusted by changing the FEC code rate $R_c$, whilst the transmission rate of PAS is adjusted by changing shaping rate $R_s$, as can be seen in Table <ref>.
At the transmission rate of $R=9.6$ bit/4D-symbol (yielding an information rate of $307$ Gbps), in addition to the $480$ km reach extension brought by standard CCDM over uniform signaling, L-CCDM with $v=4$ provides $160$ km additional transmission distance, which corresponds to a reach extension of $8\%$.

§ CONCLUSIONS

In this paper, list-encoding CCDM (L-CCDM) was proposed to mitigate some of the NLI generated during optical fiber transmission.
L-CCDM selects NLI-tolerant channel input sequences from a set of candidate symbol sequences by measuring their energy dispersion index (EDI).
Simulation results show that L-CCDM improves nonlinear shaping gains considerably, providing a $0.35$ dB increase in effective SNRs. The architecture of L-CCDM used in this paper can be generalized to different amplitude shapers (e.g., enumerative sphere shaping), and to different mapping strategies. In general, the architecture of L-CCDM is easy to implement, and its EDI selector module can be directly plugged into existing PAS architectures. L-CCDM showed potential for exploiting EDI in designing NLI-tolerant signaling schemes.


# On Dehn functions for family of polycyclic groups

KRISHNENDU GONGOPADHYAY  and  LOKENATH KUNDU  Indian Institute of Science
Education and Research (IISER) Mohali, Knowledge City, Sector 81, SAS Nagar,
Punjab 140306, India<EMAIL_ADDRESS>Indian Institute of Science
Education and Research (IISER) Mohali, Knowledge City, Sector 81, SAS Nagar,
Punjab 140306, India<EMAIL_ADDRESS>
###### Abstract.

In this note, we initiate the concept of Dehn functions for a family of finite
groups. We investigate the Dehn function for some specific families of finite
polycyclic groups. We also consider related notions of spherical Dehn function
and mean Dehn function for family of finite simple cyclic groups.

###### Key words and phrases:

Dehn function, family of finite groups, Dihedral group, polycyclic groups

###### 2020 Mathematics Subject Classification:

Primary 20F65; Secondary 05E16, 20E07

##  1\. Introduction

The Dehn functions estimate complexity of the word problem in finitely
presented groups. It was originally proposed by computer scientists Madlener
and Otto to delineate the complexity of the word problem for groups, cf. [6].
It was simultaneously introduced by Gromov as a geometric invariant for
finitely presented groups [7]. An intriguing outcome of this study is the
assertion that a group is hyperbolic if and only if it possesses a linear Dehn
function, cf. [7].

Moreover, it is widely acknowledged that a finitely presented group achieves a
solvable word problem precisely when its Dehn function is upper-bounded by a
recursive function [6]. This link between the Dehn function and the
decidability of the word problem emphasizes the significance of this invariant
in the study of finitely presented groups.

Another quasi-isometry invariant property of any finitely generated group,
akin to the Dehn function, is the growth of a group. The asymptotic behavior
of the growth function and the Dehn function remains independent of the
generating set for any group. In [2], Black introduced the concept of the
growth function for a family of finite groups, which is strictly dependent on
the generating sets. Analogous to the notion of ‘the growth of a family of
finite groups’, we define the Dehn function for a family of finite groups as
follows.

Recall that a family of finite groups
$(\mathcal{G},\mathcal{S})=(G_{i},S_{i})$, where each $G_{i}=\langle S_{i}\ |\
R_{i}\rangle$, is called a $K-$bounded family if the cardinality of $S_{i}$ is
less than or equal to $K$ for all $i$. Specifically, this implies that
$|S_{i}|\leq K$ holds for every index $i$ in the family. A word $w$ is
considered null-homotopic in the $K-$bounded family of finite groups
$(\mathcal{G},\mathcal{S})=(G_{i},S_{i})$ if it represents identity in a group
$G_{i}$ for some index $i$.

Consider a $K-$bounded family of finite groups
$(\mathcal{G},\mathcal{S})=(G_{i},S_{i})$ characterized by the minimal
relation set and the minimal length relators under the usual word metric. The
minimal length of the relators refers to the length of the word that is
minimal and null-homotopic. The minimal relation set is defined such that no
relator word can be derived from another through reduction or induction to the
empty word, and no relator word is cyclically conjugated to another relator
word.

######  Definition 1.1.

The Dehn function for a family of finite groups
$(\mathcal{G},\mathcal{S})=(G_{i},S_{i})$ is defined as:

(1.1)
$\delta_{(\mathcal{G},\mathcal{S})}(n)=\displaystyle\sup_{(G_{i},S_{i})}\delta_{(G_{i},S_{i})}(n),$

where $\delta_{(G,S)}(n)$ is the Dehn function for the group $G$.

The Dehn function of a family of finite groups is also contingent on
generating sets, mirroring the growth function of a family of finite groups.
We demonstrate this by a concrete example, see Example2.3.

We now describe the specific family of polycyclic groups whose Dehn function
will be investigated.

  * G1.

Family of finite cyclic groups of prime orders including all potential
generating sets.

  * G2.

A family of finite polycyclic groups consisting of the following polycyclic
groups:

$\large\\{x_{1}^{i},x_{2}^{i},\dots,x_{n}^{i}~{}\large|~{}R\large\\}$

where the $R$ consists of the following relations.

    1. (1)

$(x^{i}_{l})^{r_{l}^{i}}=1;~{}l=1,2,\dots,n$

    2. (2)

$(x_{l}^{i})^{s_{i}}=(x^{i}_{l+1})^{a_{l,l+1}}\dots(x^{i}_{n})^{a_{i,n}};~{}1\leq
l\leq n,~{}0\leq s_{i}\leq\infty$

    3. (3)

$(x^{i}_{j})^{-1}x^{i}_{l}x^{i}_{j}=(x^{i}_{j+1})^{b_{l,j,j+1}}\dots(x^{i}_{n})^{b_{l,j,n}};~{}1\leq
j<l\leq n$

    4. (4)

$x^{i}_{j}x^{i}_{l}(x^{i}_{j})^{-1}=x^{i}_{l};~{}1\leq j<l\leq n$.

  * G3.

A family of finite polycyclic groups whose members are

$\begin{split}(H_{p},X_{p})~{}=(\langle
a,b~{}|~{}bab^{-1}=a^{p+1},~{}a^{p^{2}},b^{p}\rangle,\\{a,b\\}).\end{split}$

In this context, we have the following theorems:

######  Theorem 1.2.

The following holds.

  * 1.

The family $G1$ exhibits a linear Dehn function.

  * 2.

The family $G2$ exhibits a quadratic Dehn function.

  * 3.

The family $G3$ exhibits an exponential Dehn function.

Note that the Dihedral group $D_{2n}$, or simply $D_{n}$, are polycyclic for
$n=2^{k}$. However, this family is not included in the above theorem. We
investigate the Dehn function for the family of Dihedral groups $D_{2n}$ and
prove the following. This theorem is independent of the generating sets.

######  Theorem 1.3.

The Dehn function for the family of finite Dihedral groups exhibits linear
growth.

Moreover, we introduce the concepts of the mean Dehn function and the
spherical mean Dehn function for a family of finite groups, see Section 4.
Such concepts are investigated for a group at several places in the
literature, e.g. [5], We have observed the following for the family of cyclic
groups.

######  Theorem 1.4.

Both the mean and the spherical Dehn functions for the family of finite simple
cyclic groups exhibit linear growth.

The paper is organized as follows. Section 2 revisits essential concepts and
introduces key preliminary objects. Theorem 1.2 and Theorem 1.3 are
established in Sections 3. In Section 4, Theorem 1.4 has been proven.

###  1.1. Acknowledgements

The authors acknowledge support from the SERB core research grant
CRG/2022/003680 during the course of this work.

Kundu is thankful to Dr. Manish Kumar Pandey, Dr. Anirban Bose, and Mr. Isif
Iqbal for their support and encouragement.

###  1.2. Competing Interest

We declare that there are no competing interests associated with this
manuscript.

##  2\. Preliminaries

In this section, we establish certain notations and revisit essential
background information that will be employed consistently in the subsequent
discussions within this document.

###  2.1. Dehn function of a group

Consider a finitely generated group $G$ with the presentation $G=\langle
S~{}|~{}R\rangle,$ implying that $G$ is isomorphic to the quotient group
$F(S)/N,$ where $F(S)$ represents the free group generated by the set $S,$ and
$N$ is a normal subgroup of the free group $F(S)$. The elements in $R$ consist
of cyclically reduced words, and every generator in $N$ is a conjugate of an
element in $R.$ If a reduced word $w$ in the free group $F(S)$ signifies the
identity in $G$, we declare that $w$ is null-homotopic, denoted as $w\equiv 1$
in $G$. Furthermore, this implies that $w$ belongs to $N=\langle\langle
R\rangle\rangle.$ The area of any null-homotopic word is defined in the
following way:

######  Definition 2.1.

(Area of null-homotopic words) If $w$ is equivalent to $1$ in the group $G,$
then $w$ can be expressed as the product
$\displaystyle\prod_{i=1}^{d}g_{i}r_{i}^{\pm 1}g_{i}^{-1},$ where each $r_{i}$
belongs to the set $R.$ The area of $w$ is defined by the expression:

(2.1) $Area(w)=\min\\{d~{}|~{}w=\displaystyle\prod_{i=1}^{d}g_{i}r_{i}^{\pm
1}g_{i}^{-1}\\}.$

The Dehn function quantifies the complexity of the word problem for any given
group, and its definition is as follows:

######  Definition 2.2.

The Dehn function for a group $G$, denoted as
$\delta_{(G,S)}:\mathbb{N}\rightarrow\mathbb{N}$, is defined as:

(2.2) $\displaystyle\delta_{(G,S)}(n)=\sup\\{Area(w)~{}|~{}|w|\leq
n,~{}w\equiv 1\\}.$

Here, $S$ is any generating set for $G$, and $|w|$ represents the word length
of an element $w\in F(S)$.

The Dehn function for any group has been computed up to a certain equivalence
relation, and this equivalence relation is defined as follows:

Two functions, $f$ and $g$, defined on the interval $[0,\infty)$, are
considered equivalent if $f\preceq g$ and $g\preceq f$. Here, $f\preceq g$
holds if and only if there exist positive constants $a,b,c,d,e$ such that
$f(x)\leq a\cdot g(bx)+cx+d$ for all $x\in[0,\infty)$. If $f$ and $g$ are two
such equivalent functions, we denote this relationship as $f\sim g$. The Dehn
function $\delta_{(G,S)}(n)$ is independent of generating sets up to the above
equivalence relation for any group $G=\langle S~{}|~{}R\rangle.$

###  2.2. Dehn function for a family

In this section, we give an example to illustrate that the Dehn function for a
family of finite groups depends on the choice of a generating set.

######  Example 2.3.

Consider a family of finite groups
$\\{(\mathbb{Z}_{p}\times\mathbb{Z}_{q})\\}$ where $p$ and $q$ are two
distinct primes. We examine the Dehn function of the family
$\\{(\mathbb{Z}_{p}\times\mathbb{Z}_{q})\\}$ for two different generating sets
of $\mathbb{Z}_{p}\times\mathbb{Z}_{q}.$ First, we consider
$(\mathcal{G},\mathcal{S})=(\mathbb{Z}_{p}\times\mathbb{Z}_{q},\mathcal{S}).$
Here, $\mathbb{Z}_{p}\times\mathbb{Z}_{q}=\langle S_{pq}|R_{pq}\rangle$ where
$S_{pq}=\\{a_{pq}\\}$ and $R_{pq}=\\{a_{pq}^{pq}\\}.$ Next, we consider
$(\mathcal{G},\overline{\mathcal{S}})=(\mathbb{Z}_{p}\times\mathbb{Z}_{q},\overline{\mathcal{S}}).$
Here,
$\mathbb{Z}_{p}\times\mathbb{Z}_{q}=\langle\overline{S}_{pq}|\overline{R}_{pq}\rangle$
where $\overline{S}_{pq}=\\{x,y\\}$ and
$\overline{R}_{pq}=\\{x^{p},y^{q},~{}xyx^{-1}y^{-1}\\}.$

Now, concerning the generating set $S_{pq}$, we find that

(2.3) $\delta_{(\mathbb{Z}_{p}\times\mathbb{Z}_{q},\mathcal{S}_{pq})}(n)\sim
n.$

Thus,

(2.4)
$\delta_{(\mathcal{G},\mathcal{S})}(n)=\displaystyle\sup_{(\mathbb{Z}_{p}\times\mathbb{Z}_{q},\mathcal{S}_{pq})}\delta_{(\mathbb{Z}_{p}\times\mathbb{Z}_{q},\mathcal{S}_{pq})}(n)\sim
n.$

Therefore, it is at most linear.

Now, we compute the Dehn function for the family
$\\{(\mathbb{Z}_{p}\times\mathbb{Z}_{q})\\}$ with respect to the second
generating set $\overline{S}_{pq}.$ Specifically, the Dehn function
$\delta_{(\mathbb{Z}_{p}\times\mathbb{Z}_{q},\overline{S}_{pq})}$ for a word
like $x^{n}y^{n}x^{-n}y^{-n}$ is equivalent to $n^{2}.$ For any fixed $n$, we
can always find a prime number $p$ such that $4n<p<q$. Hence, the Dehn
function is

(2.5) $\delta_{(\mathbb{Z}_{p}\times\mathbb{Z}_{q},\overline{S}_{pq})}(n)\sim
n^{2},~{}\forall~{}n.$

Therefore,

(2.6) $\delta_{(\mathcal{G},\overline{\mathcal{S}})}(n)\sim n^{2}.$

Consequently, the Dehn function of an infinite family of finite groups is
dependent on generating sets.

Interestingly, the inclusion of null-homotopy words in the generating sets
makes the Dehn function as large as possible. The following example
illustrates this.

######  Example 2.4.

Let us consider the family of finite simple cyclic groups
$(\mathcal{G},\mathcal{S})$ with $2-$bounded generating set consisting the
following groups

$\mathbb{Z}_{p}=\langle X_{p}~{}|~{}R_{p}\rangle.$

Where $X_{p}=\\{a,s\\},$ and
$R_{p}=\\{s^{p},~{}a^{k},~{}s^{-1}asa^{-2}\\},~{}5\leq p<k,~{}k\text{ is a
prime, and }k\nmid 2^{p}-1.$ A straight forward computation shows that
$a\equiv_{\mathbb{Z}_{p}}1$. Consider the null-homotopic word
$w=as^{-n}as^{n}a^{-1}s^{-n}a^{-1}s^{n}\in R_{p}~{}\forall~{}p\geq 5.$ The
area of the word $w$ is equivalent to $2^{n}$ whenever $2n<<p.$ Hence

(2.7)
$\delta_{(\mathcal{G},\mathcal{S})}(n)=\displaystyle\sup_{(\mathbb{Z}_{p},X_{p})}\delta_{(\mathbb{Z}_{p},X_{p})}(n)\sim
2^{n}.$

Hence the Dehn function of the family $(\mathcal{G},\mathcal{S})$ is at least
exponential as null-homotopy words exist in the generating set. Due to this,
we shall exclude null-homotopic words in the generating sets.

###  2.3. Polycyclic groups

######  Definition 2.5.

A group $G$ is said to be a polycyclic group if there exists a descending
chain of subgroups $G=G_{1}\geq G_{2}\geq\dots\geq G_{n+1}=\\{1\\}$ such that
$G_{i+1}$ is normal in $G_{i}$ and $G_{i}/G_{i+1}$ is cyclic. Such a chain of
subgroups is known as a polycyclic series, and the integer $n$ is attributed
as the polycyclic length of the group $G$.

Given that the quotient group $G_{i}/G_{i+1}$ is cyclic, it follows that there
exists an element $x_{i}$ in the group $G$ such that the coset $x_{i}G_{i+1}$
generates the entire quotient group $G_{i}/G_{i+1}$. Let the order of the
coset $x_{i}G_{i+1}$ be denoted as $r_{i}$. The resulting sequence
$(r_{1},r_{2},\dots,r_{n})$ is commonly referred to as the sequence of
relative orders. Additionally, the sequence of elements
$(x_{1},x_{2},\dots,x_{n})$ is recognized as a polycyclic sequence.

######  Definition 2.6.

A presentation $\langle x_{1},x_{2},\dots,x_{n}|R\rangle$ of a group $G$ is
said to be a polycyclic presentation if there exists a sequence
$(s_{1},s_{2},\dots,s_{n})$ with $s_{i}\in\\{0,1,2\dots\\}$ and integers
$a_{i,k},b_{i,j,k},c_{i,j,k}$ such that $R$ consists of the following
relations:

(2.8) $\begin{split}x_{i}^{s_{i}}&=x_{i+1}^{a_{i,i+1}}\dots
x_{n}^{a_{i,n}};~{}1\leq i\leq n,~{}0\leq s_{i}\leq\infty\\\
x_{j}^{-1}x_{i}x_{j}&=x_{j+1}^{b_{i,j,j+1}}\dots x_{n}^{b_{i,j,n}},~{}1\leq
j<i\leq n\\\ x_{j}x_{i}x_{j}^{-1}&=x_{j+1}^{c_{i,j,j+1}}\dots
x_{n}^{c_{i,j,n}},~{}1\leq j<i\leq n\end{split}$

If $G$ is defined by such a polycyclic presentation then $G$ is a $PC-$group.

For further elucidation on polycyclic groups, please consult the reference
[1].

##  3\. Dehn functions for Polycyclic and Dihedral Families

###  3.1. Proof of Theorem 1.2

  * •

G1 exhibits a linear Dehn Function.

We will examine the following two scenarios:

    * Case 1.

Now, let’s examine the family of finite cyclic groups
$(\mathcal{G},\mathcal{S})$ consisting of the following $1-$bounded generated
groups $(\mathbb{Z}_{p},X_{p})=(\langle
a_{p}~{}|~{}a_{p}^{p}\rangle,\\{a_{p}\\}).$ Thus $\mathbb{Z}_{p}=\langle
X_{p}~{}|~{}R_{p}\rangle$ where $X_{p}=\\{a_{p}\\}$ and
$R_{p}=\\{a_{p}^{p}\\}.$ Hence

(3.1) $Area(a_{1}^{n})=\left\\{\begin{array}[]{@{}l@{\thinspace}l}0&:\text{ if
}n<p\\\ k&:\text{ if }n=k.p,~{}k=1,2,\dots\\\ \end{array}\right.$

So, $\delta_{(\mathbb{Z}_{p},X_{p})}(n)\sim n.$ Hence

(3.2)
$\begin{split}\delta_{(\mathcal{G},\mathcal{S})}(n)&=\displaystyle\sup_{(\mathbb{Z}_{p},X_{p})}\delta_{(\mathbb{Z}_{p},X_{p})}(n)\Rightarrow\delta_{(\mathcal{G},\mathcal{S})}(n)\sim
n.\end{split}$

    * Case 2.

Now we consider any $K-$bounded family of finite cyclic groups
$(\mathcal{G},\mathcal{S})=(\mathbb{Z}_{p},S_{p})$ where
$\mathbb{Z}_{p}=\langle S_{p}~{}|~{}R_{p}\rangle,$ and $|S_{p}|\leq K.$ Let
$S_{p}=\\{a_{1},a_{1}^{m_{1}},\dots,a_{1}^{m_{l-1}}|~{}l\leq K\\}$ and
$R_{p}=\\{a_{1}^{p},(a_{1}^{m_{1}})^{p},\dots,(a_{1}^{m_{l-1}})^{p}\\}.$ So,

(3.3)
$Area((a_{1}^{m_{i}})^{n})=\left\\{\begin{array}[]{@{}l@{\thinspace}l}0&:\text{
if }n<p\\\ k&:\text{ if }n=k.p,~{}1\leq i\leq
l-1,~{}k=1,2,\dots\end{array}\right.$

Also,

(3.4) $Area((a_{1})^{n})=\left\\{\begin{array}[]{@{}l@{\thinspace}l}0&:\text{
if }n<p\\\ k&:\text{ if }n=k.p,~{}1\leq i\leq
l-1,~{}k=1,2,\dots\end{array}\right.$

Hence the Dehn function of the family of finite simple cyclic groups

(3.5)
$\begin{split}\delta_{(\mathbb{Z}_{p},S_{p})}(n)&=\displaystyle\sup_{(\mathbb{Z}_{p},S_{p})}\delta_{(\mathbb{Z}_{p},S_{p})}\sim
n.\end{split}$

This demonstrates that the Dehn function of the family of finite groups is
$\delta_{(\mathbb{Z}_{p},S_{p})}(n)\sim n.$

  * •

G2 exhibits a quadratic Dehn Function.

Let us consider an $n-$generated family of finite polycyclic groups of
$(\mathcal{G},\mathcal{S})=(G_{i},S_{i})~{}\forall~{}i\in I$, consisting of
the groups $G_{i}=\langle
S_{i}|R_{i}\rangle,~{}\text{where}~{}S_{i}=\\{x^{i}_{1},x^{i}_{2},\dots,x^{i}_{n}\\},$
and $R_{i}$ consists of the following words:

(3.6) $\begin{split}(x^{i}_{l})^{r_{l}^{i}}&=1;~{}l=1,2,\dots,n\\\
(x_{l}^{i})^{s_{i}}&=(x^{i}_{l+1})^{a_{l,l+1}}\dots(x^{i}_{n})^{a_{i,n}},~{}1\leq
l\leq n,~{}0\leq s_{i}\leq\infty\\\
(x^{i}_{j})^{-1}x^{i}_{l}x^{i}_{j}&=(x^{i}_{j+1})^{b_{l,j,j+1}}\dots(x^{i}_{n})^{b_{l,j,n}};~{}1\leq
j<l\leq n\\\ x^{i}_{j}x^{i}_{l}(x^{i}_{j})^{-1}&=x^{i}_{l};~{}1\leq j<l\leq
n\end{split}$

Here $I$ is an indexing set. Now
$a_{l,l+1},~{}b_{l,j,j+1}\in\mathbb{Z}~{}\forall~{}l=1,2,\dots,n,~{}1\leq
j<l\leq n.$ So, the normal closure $\langle\langle R\rangle\rangle$ of $R$
contains words of the form
$x^{i}_{j}x^{i}_{l}(x^{i}_{j})^{-1}(x^{i}_{l})^{-1}.$ Hence
$(x^{i}_{j})^{n}(x^{i}_{l})^{n}(x^{i}_{j})^{-n}(x^{i}_{l})^{-n}\in\langle\langle
R\rangle\rangle$ whenever $n<\min\\{r^{i}_{l}|~{}l=1,2,\dots,n\\}.$ The
expression

$Area((x^{i}_{j})^{n}(x^{i}_{l})^{n}(x^{i}_{j})^{-n}(x^{i}_{l})^{-n})=n^{2},$

hence the Dehn function $\delta_{(\mathcal{G},\mathcal{S})}(n)\geq n^{2}$.
Therefore, this group will possess a Dehn function of at least quadratic
complexity.

  * •

G3 exhibits an exponential Dehn Function.
For this part of the theorem, we will examine the following group family
$(\mathcal{H},~{}\mathcal{X})$ consisting of the following groups:

$\begin{split}(H_{p},X_{p})=(\langle
a,b~{}|~{}bab^{-1}=a^{p+1},~{}a^{p^{2}},b^{p}\rangle,\\{a,b\\}).\end{split}$

each of order $p^{3}$ for a prime $p.$ Now we consider the word
$W:=ab^{n}ab^{-n}a^{-1}b^{n}a^{-1}b^{-n}$ in $H_{p}~{}\forall~{}p,~{}n<p.$ The
area of the word $Area(W)=(p+1)^{n}.$ So, the Dehn function

$\delta_{(\mathcal{H},\mathcal{X})}(n)=\displaystyle\sup_{(H_{p},X_{p})}\delta_{(H_{p},X_{p})}\geq
2^{n}.$

So the Dehn function of the family of polycyclic groups could be greater than
the exponential function. It can be seen from the following argument that the
above family exhibits an exponential Dehn function.

Let $W$ be a null-homotopic word in $(\mathcal{H},~{}\mathcal{X})=(\langle
a,b~{}|~{}bab^{-1}=a^{p+1},~{}a^{p^{2}},b^{p}\rangle,\\{a,b\\})$. If $W$
contains any letter $b^{\pm 1}$, so there must be a subword $b^{\pm 1}ub^{\mp
1},~{}u\in\\{a,a^{-1}\\}$ or $b^{\mp p-1}.$ We only focus when the first case
happens. It follows that there exists a null sequence for $W$ which begins by
replacing $b^{\pm 1}ub^{\mp 1}$ with a suitable power of $a.$ We’ll keep doing
this until all pairs of $b^{\pm 1}$ are matched and eliminated. Then, we
simplify the remaining word using only $a$ and $a^{-1}$ until it becomes
empty. Summing the applications of a relator moves we use along the way gives
our exponential upper bound. So $\delta_{(H_{p},X_{p})}(n)=2^{n}.$

This completes the proof. ∎

###  3.2. Proof of Theorem 1.3.

We will examine the following scenarios:

  * Case 1.

Consider the family $(\mathcal{G},\mathcal{S})$ of dihedral groups with a
$2-$bounded generating set. This family consists of groups

(3.7) $\displaystyle(D_{2(n+1)},S_{n+1})$ $\displaystyle=(\langle
s,r|~{}s^{2},~{}r^{n+1},~{}srsr^{-n}\rangle,\\{s,r\\})~{}\forall~{}n\geq 2$

So $D_{2(n+1)}=\langle S_{n+1}|R_{n+1}\rangle,$ then $S_{n+1}=\\{s,r\\}$ and
$R_{n+1}=\\{s^{2},r^{n+1},srsr^{-n}\\}.$ Consider the elements
$r^{k(n+1)},~{}s^{2k},~{}sr^{k(n+1)}s,~{}rs^{2k}r,~{}sr^{k}sr^{-nk},~{}sr^{k}sr^{k}sr^{-nk}sr^{-nk}\\\
\text{ which belong to }\langle\langle R\rangle\rangle,$ where $\langle\langle
R\rangle\rangle$ denotes the normal closure of $R$.

The area for the expressions
$r^{k(n+1)},~{}s^{2k},~{}sr^{k(n+1)}s,~{}rs^{2k}r^{n}$ can be easily
achievable through straightforward mathematical calculations. Furthermore, the
$Area(sr^{k}sr^{-nk})\leq k$ and $Area(sr^{k}sr^{k}sr^{-nk}sr^{-nk})\leq 2k$
for all $n.$ These cases are elucidated by the following diagrams,
specifically for $n=4,~{}k=2.$

(a) Area of $sr^{k}sr^{-nk}$ in $D_{2(n+1)}$ for $n=4$, and $k=2.$ (b) Area of
$sr^{k}sr^{k}sr^{-nk}sr^{-nk}$ in $D_{2(n+1)}$ for $n=4$, and $k=2.$

This suggests that the function $\delta_{D_{2(n+1)}}(k)$ asymptotically
behaves as $k~{}i.e.\\\ ~{}\delta_{D_{2(n+1)}}(k)\sim k.$ Hence

(3.8) $\displaystyle\delta_{(\mathcal{G},\mathcal{S})}(k)$
$\displaystyle=\sup_{(D_{2(n+1)},S_{n+1})}\delta(D_{2(n+1)},S_{n+1})(k)$
$\displaystyle\delta_{(D_{2(n+1)},S_{n+1})}(k)$ $\displaystyle\sim k.$

  * Case 2.

Consider the family of dihedral groups:

(3.9) $\displaystyle(\mathcal{G},\mathcal{S})$
$\displaystyle=(D_{2(n+1)},S_{n+1})\text{ where }$
$\displaystyle(D_{2(n+1)},S_{n+1})$ $\displaystyle=(\langle
s,sr~{}|~{}s^{2},~{}(sr)^{2},~{}(ssr)^{n+1}\rangle,\\{s,sr\\})~{}\forall~{}n\geq
2$

So, if $D_{2(n+1)}=\langle S_{n+1}|R_{n+1}\rangle,$ then $S_{n+1}=\\{s,sr\\}$
and $R_{n+1}=\\{s^{2},(sr)^{2},(ssr)^{n+1}\\}.$ Examine the elements
$r^{k(n+1)},~{}s^{2k},~{}sr^{k(n+1)}s,~{}rs^{2k}r,~{}sr^{k}sr^{-nk},~{}sr^{k}sr^{k}sr^{-nk}sr^{-nk}$,
all of which pertain to the group $\langle\langle R\rangle\rangle$, wherein
$\langle\langle R\rangle\rangle$ signifies the normal closure of the set $R$.
Using a similar line of reasoning as in Case 1, we will obtain:

(3.10) $\displaystyle\delta_{(D_{2(n+1)},S_{n+1})}(k)$ $\displaystyle\sim k$
$\displaystyle\delta_{(\mathcal{G},\mathcal{S})}(k)$
$\displaystyle=\sup_{(D_{2(n+1)},S_{n+1})}\delta_{(D_{2(n+1)},S_{n+1})}(k)$
$\displaystyle\Rightarrow\delta_{(\mathcal{G},\mathcal{S})}(k)$
$\displaystyle\sim k~{}\forall~{}n.$

Now we consider any $K-$ generated family of dihedral groups

(3.11) $\displaystyle D_{2(n+1)}$ $\displaystyle=\langle
S_{n+1}~{}|~{}R_{n+1}\rangle$ $\displaystyle=\langle
s^{k},sr^{i},r^{j}|~{}1\leq i,j\leq
n+1,~{}k\in\\{0,1\\},~{}s^{2}=1,~{}(sr^{i})^{2}=1,~{}$
$\displaystyle(r^{j})^{\frac{n+1}{\gcd(j,n+1)}}=1,~{}sr^{i}s=r^{-i}\rangle.$

So, $S_{n+1}=\\{s^{k},sr^{i},r^{j}\\},$ and $|\\{s^{k},sr^{i},r^{j}\\}|\leq
K,~{}1\leq i,j\leq n+1,~{}k\in\\{0,1\\},$ and
$R_{n+1}=\\{s^{2},~{}(sr^{i})^{2},~{}(r^{j})^{\frac{n+1}{\gcd(j,n+1)}},~{}sr^{i}s=r^{-i}\\}.$
Since the set $S_{n+1}$ generates $D_{2(n+1)},$ so one of the following will
certainly occur:

  * Case 1.

Let $s\in S_{n+1}.$ Then atleast $sr^{l}\in S_{n+1}$ or $r^{l}\in S_{n+1}$
where $\gcd(l,n+1)=1$.

  * Case 2.

Let $s\notin S_{n+1}.$ Then there should be $sr^{i},r^{j}\in S$ such that
$i+j\equiv 0~{}(mod~{}(n+1)),$ and $r^{l}\in S_{n+1}$ where $\gcd(l,n+1)=1.$

In either case
$sr^{k}sr^{-nk},~{}sr^{k}sr^{k}sr^{-nk}sr^{-nk}\in\langle\langle
R_{n+1}\rangle\rangle.$ According to our earlier arguments, the Dehn function
$\delta_{(\mathcal{G},\mathcal{S})}(k)\sim~{}k.$

Nest we examine a special family of dihedral groups

(3.12) $\displaystyle(\mathcal{G},\mathcal{S})$
$\displaystyle=(D_{4n},S_{4n})\text{ consisting of }$
$\displaystyle(D_{4n},S_{4n})$ $\displaystyle=(\langle
s,r,t|s^{2},r^{n},t^{2},(sr)^{2},[s,t],[r,t]\rangle,\\{s,r,t\\})~{}\text{where
}n\text{ is an odd number. }$

The established result is that $D_{4n}\cong D_{2n}\times\mathbb{Z}_{2}$ for
any odd number $n.$ So,

(3.13) $\begin{split}D_{4n}&=\langle S|R\rangle\\\
\Rightarrow&S=\\{s,r,t\\},~{}R=\\{s^{2},r^{n},t^{2},(sr)^{2},[s,t],[r,t]\\}.\end{split}$

It is our only task now to examine the area of the words of the form
$w=r^{k}tr^{-k}t^{-1}\in R.$ The area of such a word is $k.$ Therefore,
$\delta_{(D_{4n},S_{4n})}(n)\sim n.$ Hence
$\delta_{(\mathcal{G},\mathcal{S})}(k)\sim k.$

This shows that the Dehn function for the family of dihedral groups
consistently demonstrates linear growth. ∎

##  4\. Mean Dehn function And Spherical mean Dehn functions of A Family

###  4.1. Mean Dehn function and spherical Mean Dehn function of a family of
finite groups

Consider a group $G$ given by $\langle X~{}|~{}R\rangle$. For any positive
integer $n$, we define the sets as follows:

(4.1) $B_{G}(n)=\\{w~{}|~{}|w|\leq n,~{}w\equiv_{G}1~{}\\},\newline
S_{G}(n)=\\{w~{}|~{}|w|=n,~{}w\equiv_{G}1~{}\\}.$

######  Definition 4.1.

(Mean Dehn function) The mean Dehn function of $G$ with respect to the
presentation $G=\langle X~{}|~{}R\rangle$ is expressed as:

(4.2) $\delta_{mean}(n)=\frac{\displaystyle\sum_{w\in
B_{G}(n)}Area(w)}{|B_{G}(n)|}$

######  Definition 4.2.

(Spherical Mean Dehn function) The spherical mean Dehn function of $G$ with
respect to the presentation $G=\langle X~{}|~{}R\rangle$ is defined as

(4.3) $\delta_{smean}(n)=\frac{\displaystyle\sum_{w\in
S_{G}(n)}Area(w)}{|S_{G}(n)|}.$

If $|S_{G}(n)|=0$ then we understand $\delta_{smean}(n)=0.$

The mean Dehn function and spherical mean Dehn function are contingent on the
choice of generating sets. For further information, refer to [5].

The concept of mean Dehn function and spherical mean Dehn function can be
extended to a family of finite groups
$(\mathcal{G},\mathcal{S})=(G_{i},S_{i})$ as follows:

(4.4) $\displaystyle
B_{(\mathcal{G},\mathcal{S})}(n):=\cup_{G_{i}}B_{G_{i}}(n),~{}|B_{(\mathcal{G},\mathcal{S})}(n)|=\sum_{G_{i}}|B_{G_{i}}(n)|.$
$\displaystyle
S_{(\mathcal{G},\mathcal{S})}(n):=\cup_{G_{i}}S_{G_{i}}(n),~{}|S_{(\mathcal{G},\mathcal{S})}(n)|=\sum_{G_{i}}|S_{G_{i}}(n)|.$

######  Definition 4.3.

(Mean Dehn function of a family of finite groups) If the
$|B_{(\mathcal{G},\mathcal{S})}(n)|<\infty,$ then the mean Dehn function of a
family of finite $(\mathcal{G},\mathcal{S})$ groups is defined as

(4.5)
$\delta_{mean}^{{(\mathcal{G},\mathcal{S})}}(n)=\frac{\displaystyle\sum_{w\in
B_{(\mathcal{G},\mathcal{S})}(n)}Area(w)}{|B_{(\mathcal{G},\mathcal{S})}(n)|}$

######  Definition 4.4.

If the $|S_{(\mathcal{G},\mathcal{S})}(n)|<\infty,$ then the spherical mean
Dehn function of a family of finite groups $(\mathcal{G},\mathcal{S})$ is
defined as

(4.6)
$\delta_{smean}^{(\mathcal{G},\mathcal{S})}(n)=\frac{\displaystyle\sum_{w\in
S_{(\mathcal{G},\mathcal{S})}(n)}Area(w)}{|S_{(\mathcal{G},\mathcal{S})}(n)|}$

If $|S_{(\mathcal{G},\mathcal{S})}(n)|=0$ then
$\delta_{smean}^{(\mathcal{G},\mathcal{S})}(n)=0.$

######  Remark 4.5.

It is evident from the definition that the mean Dehn function and spherical
mean Dehn function are specifically defined in cases where only finitely many
occurrences of $|B_{G_{i}}(n)|$ and $|S_{G_{i}}(n)|$ exhibit non-zero values
within the sets $|B_{(\mathcal{G},\mathcal{S})}(n)|$ and
$|S_{(\mathcal{G},\mathcal{S})}(n)|$, respectively.

###  4.2. Proof of Theorem 1.4.

  * •

The mean Dehn function of the family of a finite simple cyclic group is
linear. Let $n$ be a positive integer and
$\phi(n)=\\{p_{1},p_{2},\dots,p_{l}\\}$ be the collection of all primes that
less than or equal to $n.$ Consider the family of finite simple cyclic groups
$(\mathcal{G},\mathcal{S})=(\mathbb{Z}_{p},S_{p})$ where $S_{p}=\\{a_{p}\\}$
and $\mathbb{Z}_{p}=\langle a_{p}|~{}a_{p}^{p}\rangle.$
Now $p_{1}\in\phi(n).$ Let $\mathbb{Z}_{p_{1}}=\langle
a_{p_{1}}|~{}a_{p_{1}}^{p_{1}}\rangle$. So
$B_{\mathbb{Z}_{p_{1}}}(n)=\\{~{}a^{p_{1}},~{}a^{2.p_{1}},\dots,a^{\lfloor\frac{n}{p_{1}}\rfloor.p_{1}}~{}\\}$.
Hence $|B_{\mathbb{Z}_{p_{1}}}(n)|=\lfloor\frac{n}{p_{1}}\rfloor.$ Similarly
$|B_{\mathbb{Z}_{p_{j}}}(n)|=\lfloor\frac{n}{p_{j}}\rfloor,~{}2\leq j\leq l.$
Now the area

(4.7) $\begin{split}\displaystyle\sum_{w\in
B_{\mathbb{Z}_{p_{1}}}(n)}Area(w)&=Area(a_{p_{1}}^{p_{1}})~{}+~{}Area(a_{p_{1}}^{2.p_{1}})~{}+\dots+~{}Area(a_{p_{1}}^{p_{1}.\lfloor\frac{n}{p_{1}}\rfloor})\\\
&=1+2+\dots+\lfloor\frac{n}{p_{1}}\rfloor.\end{split}$

So, $\displaystyle\sum_{w\in
B_{(\mathcal{Z}_{p},S_{p})}(n)}Area(w)=(1+2+\dots+\lfloor\frac{n}{p_{1}}\rfloor)+(1+2+\dots+\lfloor\frac{n}{p_{2}}\rfloor)+\dots+(1+2+\dots+\lfloor\frac{n}{p_{l}}\rfloor).$
Now the mean Dehn function of the family of finite simple cyclic group is

(4.8)
$\begin{split}\delta_{mean}^{(\mathbb{Z}_{p},S_{p})}(n)&=\frac{\displaystyle\sum_{w\in
B_{(\mathcal{Z}_{p},S_{p})}(n)}Area(w)}{|B_{(\mathbb{Z}_{p},S_{p})}(n)|}\\\
&=\frac{(1+2+\dots+\lfloor\frac{n}{p_{1}}\rfloor)+(1+2+\dots+\lfloor\frac{n}{p_{2}}\rfloor)+\dots+(1+2+\dots+\lfloor\frac{n}{p_{l}}\rfloor)}{\lfloor\frac{n}{p_{1}}\rfloor+\lfloor\frac{n}{p_{2}}\rfloor+\dots+\lfloor\frac{n}{p_{l}}\rfloor}\\\
&\sim n.\end{split}$

This shows that the mean Dehn function for any $K-$bounded family of finite
simple cyclic groups also demonstrates linear growth.

  * •

The spherical mean Dehn function for a family of finite simple cyclic groups
is linear. Let $n\in\mathbb{N},$ and $D(n)=\\{p_{1},p_{2},\dots,p_{l}\\}$ be
set of all prime divisors of $n.$ So,

(4.9)
$\begin{split}S_{\mathbb{Z}_{p_{1}}}(n)&=\\{w~{}|~{}|w|=n,~{}w\equiv_{\mathbb{Z}_{p_{1}}}1\\}\\\
&=\\{a^{p_{1}.\frac{n}{p_{1}}}\\}\\\ \text{ So,
}&|S_{\mathbb{Z}_{p_{1}}}(n)|=1\\\ \text{ and, }&Area_{w\in
S_{\mathbb{Z}_{p_{1}}}(n)}(w)=\frac{n}{p_{1}}.\\\ \text{ So,
}\delta_{smean}^{(\mathcal{G},\mathcal{S})}(n)&=\frac{Area_{w\in
S_{\mathbb{Z}_{p_{1}}}}(n)+Area_{w\in
S_{\mathbb{Z}_{p_{2}}}}(n)+\dots+Area_{w\in S_{\mathbb{Z}_{p_{l}}}}(n)}{l}\\\
&=\frac{\frac{n}{p_{1}}+\frac{n}{p_{2}}\dots+\frac{n}{p_{l}}}{l}\\\ &\sim
n.\end{split}$

Similarly, if we examine any $K-$bounded family of finite simple cyclic
groups, then

$\delta_{smean}^{(\mathcal{G},\mathcal{S})}(n)\sim n.$

This completes the proof. ∎

## References

  * [1] Eamonn O’Brien: Polycyclic groups, https://www.icts.res.in/sites/default/files/1284624569notes.pdf (2010).
  * [2] Sarah Black: Asymptotic growth of finite groups J. Algebra. 209, 402–428 (1998).
  * [3] T Riley: Dehn functions. in: Office hours with a geometric group theorist, 146–175. Princeton University Press, Princeton, NJ, 2017
  * [4] T Riley: What is Dehn function? https://pi.math.cornell.edu/~riley/papers/What_is_a_Dehn_function/What_is_a_Dehn_function.pdf
  * [5] O. Bogopolski, E. Ventura: The mean Dehn functions of abelian groups representations. J. Group Theory 11 (2008), no.4, 569-586.
  * [6] K. Madlener and F. Otto, Pseudonatural algorithms for the word problem for finitely presented monoids and groups, J. Symbolic Comput. 1, no. 4, 383–418, 1985.
  * [7] M. Gromov, Asymptotic invariants of infinite groups, in: Geometric Group Theory. Vol. 2, London Math. Soc. Lecture Note Ser. 182, Cambridge University, Cambridge (1993), 1–295, (Sussex) 1991.