# Towards Efficient Convolutional Neural Networks with Structured Ternary
Patterns

Christos Kyrkou Author Accepted Manuscript. Final version appears in
Transactions on Neural Networks and Learning Systems.
(https://doi.org/10.1109/TNNLS.2024.3380827)The author is with the KIOS
Research and Innovation Center of Excellence, University of Cyprus, Nicosia,
Cyprus (email: kyrkou.christos@ucy.ac.cy))

###### Abstract

High efficiency deep learning models are necessary to facilitate their use in
devices with limited resources but also to improve resources required for
training. Convolutional neural networks typically exert severe demands on
local device resources and this conventionally limits their adoption within
mobile and embedded platforms. This paper presents work towards utilizing
static convolutional filters generated from the space of local binary patterns
and Haar features to design efficient convolutional neural network
architectures. These are referred to as Structured Ternary Patterns (STeP) and
can be generated during network initialization in a systematic way instead of
having learnable weight parameters thus reducing the total weight updates. The
ternary values require significantly less storage and with the appropriate low
level implementation, can also lead to inference improvements. The proposed
approach is validated using four image classification datasets, demonstrating
that common network backbones can be made more efficient and provide
competitive results. It is also demonstrated that it is possible to generate
completely custom STeP-based networks that provide good trade-offs for on-
device applications such as Unmanned Aerial Vehicle based aerial vehicle
detection. The experimental results show that the proposed method maintains
high detection accuracy while reducing the trainable parameters by 40-80%.
This work motivates further research towards good priors for non-learnable
weights that can make deep learning architectures more efficient without
having to alter the network during or after training.

###### Index Terms:

Deep Learning, Convolutional Neural Networks, Haar Features, Local Binary
Patterns, Object Detection

††publicationid: pubid:

##  I Introduction

Deep learning (DL) and artificial intelligence (AI) are rapidly being deployed
in on-device scenarios, such as autonomous driving, robotic systems, and
unmanned aerial vehicles [1]. This proliferation can be attributed to several
factors, including privacy concerns, the need for real-time decision-making,
and the necessity to address connectivity limitations. Despite the adoption of
deep learning models in mobile applications, achieving consistently high-
performance inference on mobile and embedded platforms remains a formidable
challenge, primarily due to the substantial computational requirements
involved. In pursuit of enabling on-device AI capabilities, researchers are
constantly seeking strategies aimed at enhancing the computational efficiency
of inference processes [2].

Thus, the community has strived to identify fundamental components suitable
for utilization in deep learning algorithms, specifically convolutional neural
networks (ConvNets). Techniques such as network pruning and parameter
compression/quantization are increasingly gaining prominence as strategies to
facilitate the deployment of deep learning models within fixed-point
pipelines, as shown in [3]. However, not all existing network architectures
readily accommodate quantization, as this transformation may introduce a
significant accuracy gap when compared to their floating-point counterparts.
Furthermore, it can be challenging to anticipate the a priori impact of
optimization techniques on both accuracy and the ensuing computational
complexity. Consequently, in many instances, the training process becomes more
intricate, necessitating iterative refinement.

Figure 1: Basic STeP Block: Filters are composed of center symmetric local
binary patterns (CS-LBP) and Haar-structured features (HSF). Both use ternary
values necessitating only addition/subtraction operations.

This work explores the utilization of Structured Ternary Patterns (STeP) as
ConvNet weights, approximating Haar features and center-symmetric local binary
patterns, as a viable alternative to full-precision trainable weights. Thus
establishing a competitive baseline for efficient convolutional neural
networks utilizing ternary values ($[-1,0,1]$). The primary objective is to
enable direct training with these structured weights, leading to the creation
of streamlined models, which hold the potential for efficiency improvements in
both inference and training processes. The present work introduces a method
for the pre-generation of such structured ternary patterns, which can be
seamlessly integrated into existing neural networks (e.g., ResNet) or employed
to construct efficient custom ConvNets for on-device applications. The key
advantages of this approach are summarized as follows:

• Does not necessitate any change to existing training procedures or post-
retraining.
• Reduces the number of learnable parameters, thereby enabling the utilization
of larger batches due to the reduced storage requirements during the backward
propagation phase.
• Mitigates the storage demands for weights by utilizing lower-precision
ternary values.
• Offers the potential for multiplier-free operations in the case of ternary
weight kernels.

Results for classification and object detection tasks, across various datasets
demonstrate the effectiveness of the approach. The proposed method achieves a
substantial reduction in the number of trainable parameters, ranging from
$40-80\%$ while experiencing only a marginal average accuracy reduction of
$3.1\%$, achieved by utilizing ternary weights instead of floating-point
parameters. When combined with a compact model architecture, it yields models
that are $40\times$ times smaller in size while maintaining competitive
performance. These parameter savings are accompanied by comparable accuracy
results and do not necessitate post-training network modifications.

##  II Related Work

###  II-A Binarized Neural Networks

Works such as [4] demonstrate a methodology that utilizes full-precision
latent weights during the training process to accumulate gradients.
Subsequently, these accumulated gradients are employed to compute the
corresponding binary weights. Building upon this foundation, other studies
have extended the exploration of various properties, including scaling
factors, for binarized networks [5]. Binary weight neural networks exhibit an
advantageous compression ratio; however, they often incur a substantial
sacrifice in accuracy when compared to baseline full-precision networks.
Techniques like those introduced in [6] and [7] necessitate additional
training for weight quantization, typically restricting weights to fixed-point
representations. Alternatively, rather than training a full-precision network
followed by quantization/binarization, alternative research avenues delve into
the design of binary architectures. For instance, the work in [8] dissects
convolutional kernels into binary basis functions, generating filters as a
linear combination of orthogonal binary codes in real-time. This
transformation in computation, however, does not alleviate the count of
learnable parameters. In a similar fashion, [9] introduces local binary
convolutional networks that replace traditional convolutional layers with a
learnable module inspired by local binary patterns. This approach necessitates
learning pivot point locations and incorporates a non-linear thresholding
operation, which can influence the flow of gradients. Similarly, [10]
implements the local binary operator as a sampling operation. This involves
learning the points to generate multiple output channels, each equipped with
its own binary output code. Finally, [11] demonstrates the benefits of
software-hardware codesign for extremely sparse networks with binary
connections for image classification. Such accelerators can also be utilized
for the proposed work as well. Despite the promising advantages that binary
networks offer over their full-precision counterparts, vanilla binary networks
frequently suffer from substantial accuracy degradation, as highlighted in
[4]. Furthermore, existing schemes fail to reduce the overall number of
learnable parameters and necessitate gradient tracking for all parameters, as
pointed out in [12].

###  II-B Quantization of Neural Networks

Quantization, in general, is a method employed to map input values from a
large, often continuous set to output values within a smaller, often finite
set. Examples of quantization techniques include rounding and truncation [3].
Within the context of neural networks, quantization plays a pivotal role in
enabling the conversion of network weights and activation functions from
floating-point operations to fixed-point or mixed-precision operations. This
transition not only reduces the model’s storage footprint and memory
consumption but also enhances both latency and power efficiency [13].
Traditionally, uniform quantization, where all layers of the network share the
same bit-width, has been utilized [14]. More recently, adaptive deployment
strategies, which involve varying the bitwidth of weights and intermediate
activations, have emerged as an alternative approach [15]. [16] demonstrates
optimal bitwidth assignment for weight and activation quantization of deep
convolutional neural networks using dynamic programming. Similarly, [17]
focuses on image super-resolution applications using dynamic thresholds for
quantization. Ternary quantized networks have been demonstrated for federated
learning settings in [18]. It is worth noting that while quantization
techniques offer substantial benefits, they are often accompanied by a
noticeable decline in model accuracy, necessitating re-training in many cases
[19]. Nevertheless, these techniques can be applied independently of the
weight and architectural modifications proposed in this paper, potentially
yielding further improvements. This synergy is elaborated further in Section
IV-B.

###  II-C Efficient Neural Networks

One critical aspect of designing efficient neural networks pertains to their
architectural considerations. A multitude of works have tackled this
challenge, with a primary focus on architectural and layer modifications aimed
at optimizing the size and speed of deep learning models [20]. Notably,
experts in the field have sought to engineer lightweight, parameter-efficient
networks, introducing significant changes at both the micro- and macro-
architecture levels [21]. These architectural adjustments encompass various
techniques, such as the decomposition of convolutional layers, as exemplified
by Wang et al. [22], who advocated splitting a $3\times 3$ kernel into two
consecutive layers employing $1\times 3$ and $3\times 1$ kernels,
respectively. Another innovation, demonstrated by Koonce et al. [23], involves
the utilization of ”fire modules” that employ 1x1 convolutions to compress
parameters efficiently. Additionally, the introduction of ”bottleneck” blocks
has gained attention, as seen in MobileNetV2 [24], which employs two
convolutional layers with a $1\times 1$ kernel to reduce the dimensionality of
features processed by larger filters (e.g., $3\times 3$). This concept is
further refined in Ma et al.’s work [25], where convolutional layers are
decomposed into a sequence of smaller, independent layers using grouped
convolutions. EfficientNet, introduced by Tan et al. [26], stands as a notable
convolutional neural network architecture and scaling method. It adopts a
compound coefficient to uniformly scale the depth, width, and resolution
dimensions of the network, thereby achieving efficiency across various
dimensions. Another noteworthy innovation is the ”ghost modules,” as
introduced by Han et al. [27]. These modules are designed to generate more
features while using fewer parameters, thereby enhancing network efficiency.
It is important to note that architectural modifications can be seamlessly
integrated with other techniques to further enhance the overall efficiency of
neural networks.

##  III Proposed Approach

Figure 2: (left) Parametrization of the CS-LBP features. (right)
Parametrization of Rectangular Haar Features with two boxes.

###  III-A Generating Static Structured Patterns

The proposed approach involves the generation of convolutional filter weights
based on structured patterns that are known to exhibit exceptional performance
in computer vision tasks, such as in the domains of face and pedestrian
detection [28, 29]. The utilization of predetermined binary/ternary filters
offers several notable advantages, primarily the potential reduction of memory
and computational requirements during both training and inference phases.
Specifically, this approach leverages two well-established pattern extractors:
Local Binary Patterns (LBPs) [30, 31] and Haar-like features [32, 33]. LBPs
have proven their versatility across a broad spectrum of applications for
constructing robust visual object detection systems. In this research, Center-
Symmetric Local Binary Patterns (CS-LBP) [30, 34] are utilized, which exhibit
enhanced resilience to flat regions and a heightened ability to capture
gradient information compared to the original LBP formulation (as employed in
[9]), all without necessitating the use of any thresholds. Moreover, the
approach introduces the incorporation of Haar-based features, which had a
seminal impact on real-time object detection [32]. This integration represents
a novel exploration within this context. Herein, these two distinct feature
families are synergistically employed as the foundation for generating
convolutional kernels that possess specific structural patterns. Notably,
these kernels only necessitate ternary representation values of $[-1,0,1]$,
thus making them especially efficient in terms of computation and memory,
requiring only addition/subtraction for the ternary weight kernels.

Other approaches, such as [35], share a common foundation inspired by the
original Local Binary Pattern (LBP) formulation. However, they diverge in
their approach by randomly initializing the convolutional kernel values within
the range of $[-1,0,1]$ while imposing only sparsity constraints and lacking
structural considerations. In contrast to the stochastic initialization
utilized in [35], the proposed methodology explores a more structured
parameter space. Specifically, weights from the spaces of Center-Symmetric
Local Ternary Patterns (CS-LBP) and Haar-Structured Features (HSF) are sampled
to attain a more principled and discriminative representation.

Algorithm 1 Generate CS-LBP Features

1: Inputs:  number of channels: $k$, width: $w$, height: $h$, output filters:
$f$

2: Output:  Initialized kernels

3: function Generate_CS_LBP($weights$):

4: $weights$ $\leftarrow$ Tensor($h,w,k,f$)

5: for every weight_matrix in layer do

6: length$\leftarrow$ RandomInt(0,4)

7: for i $\rightarrow$ [0,…length] do

8: $s$ $\leftarrow$ RandomFromSet($[-1,0,1]$)

9: $i*\leftarrow i$ %Opposite value index

10: weight_matrix[i] $\leftarrow$ $s$

11: weight_matrix[i*] $\leftarrow$ $-s$

12: end for

13: UPDATE $weights$ with $weight\\_matrix$

14: end for

15: return $weights$

Algorithm 2 Generate Rectangular Haar Features

1: Inputs:  number of channels: $k$, width: $w$, height: $h$, output filters:
$f$

2: Output:  Initialized kernels

3: function Generate_CS_LBP($weights$):

4: $weights$ $\leftarrow$ Tensor($h,w,k,f$)

5: for every weight_matrix in layer do

6: $r\leftarrow$ RandomInt(1,4) %Number of rectangles

7: for $i$ 2 to r do

8: $p_{i}\leftarrow$ [RandomInt(0,$w$-1),RandomInt(0,$h$-1)]

9: $l_{i}^{w}\leftarrow$ RandomInt(0,$w$-1)

10: $l_{i}^{h}\leftarrow$ RandomInt(0,$h$-1)

11: $s_{i}$ $\leftarrow$ RandomFromSet($[-1,1]$)

12: weight_matrix[$p_{i}$:$l_{i}^{w}$,$p_{i}$:$l_{i}^{h}$] $\leftarrow$
$s_{i}$

13: end for

14: UPDATE $weights$ with $weight\\_matrix$

15: end for

16: return $weights$

(a) Center-symmetric local ternary weights of size $3\times 3$.

(b) Haar-based ternary weights of size $5\times 5$

Figure 3: Illustration of static generated ternary features by specifying
different parameters.

CS-LBP patterns rely on the differences between diagonal center-symmetric
pairs of kernel values, as illustrated in Fig. 2, and are closely related to
the gradient operator. They are adept at detecting corners and edges while
remaining unaffected by the central location of the patterns. Additionally,
CS-LBP patterns can take on zero values, making them inherently more sparse.
HSF filters, on the other hand, operate by considering differences between
rectangular regions, as depicted in Fig. 2. Values belonging in the same
region are accumulated together, enabling them to detect more abstract
patterns and flat regions. The specific type of Haar feature, along with the
random design of its location and weight for each rectangular region, allows
for a high degree of adaptability in capturing diverse features and textures.

The generated patterns undergo convolution with the input tensor, utilizing a
methodology akin to the conventional convolution operator. Notably, this
approach offers the added advantage of restricting operations solely to
addition and subtraction. The computation of each feature is shown in Eq. 1
and 2. The computation of each feature happens as shown in Eq. 1 and 2. In the
context of CS-LBP $N$ denotes the count of pairs of opposing elements within
the kernel, $s_{i}$ signifies the sign associated with each such pair, and
$a_{i}$ is a binary indicator denoting whether a given pair contributes to the
kernel or not. Conversely, for the case of HSF $M$ represents the total number
of elements in the kernel and $s_{i}$ characterizes the sign assigned to each
individual element in the kernel.

$\displaystyle CS-LBP=\sum_{i=1}^{N}{a_{i}(s_{i}x_{1}^{i}-s_{i}x_{2}^{i})}$
(1)

$\displaystyle HSF=\sum_{i=1}^{M}{s_{i}x^{i}}$ (2)

Features are generated prior to training in a channel-wise fashion through
parameterization of distinct properties within each feature space, as
illustrated in Fig. 2. The weights for CS-LBP are computed by iteratively
sampling values from the interval $[-1,1]$ for half of the weight locations
and subsequently inverting the sign for the mirrored locations, as depicted in
Fig. 2. Haar features are constructed based on the number of rectangles within
the feature, typically ranging from 2 to 4 (Alg. 2, Line 4). The top-left
position of these rectangles is randomly selected within the weight matrix,
and their side lengths are sampled uniformly according to provided parameters
(Alg. 2, Lines 6-8). It is important to note that these values are adjusted to
ensure compatibility with the size of the weight matrix; however, for the sake
of clarity, the specific adjustments are omitted. The detailed procedures for
generating these features are outlined in Alg. 2 and Alg. 1, respectively. In
these algorithms, the kernels are initially initialized with zero values and
are subsequently modified in accordance with the defined procedures. This
approach yields a diverse set of features capable of processing both coarse
and fine-grained patterns, as shown in Fig. 3.

###  III-B Networks Composed of Structured Ternary Patterns

Basic Block: The proposed approach is capable of generating weight patterns
based on underlying data structures, which can be utilized to construct a
fundamental building block referred to as STeP (Structured Ternary Pattern).
This block can be seamlessly integrated into both classification and detection
networks. The formation of this block involves an initial step of calculating
outputs from the convolution process using both CS-LBP weights and HAAR
features. Subsequently, these outputs can be combined either through element-
wise addition or via a $1\times 1$ convolution operation, which itself can
have weight values within the range of $[-1,1]$. Furthermore, the block
incorporates pooling, normalization, and activation functions after the
feature fusion process. This primary block can be directly integrated into
standard ConvNet architectures to replace computationally expensive
operations.

Custom network: The primary objective of the basic block is to facilitate the
construction of custom networks that incorporate the STeP block. In the
context of these custom networks, batch normalization and LeakyReLU
activations are employed within the STeP block. During the testing phase, it
is possible to optimize the LeakyReLU activation function by zeroing out its
negative components and rounding the positive values to the nearest integer.
This refinement serves to enhance the model’s hardware compatibility and
efficiency. Consequently, the CS-LBP/HSF block can consistently be delegated
to a hardware accelerator for streamlined processing, while also reducing the
computational load on the CPU. Additionally, a detection layer can be
incorporated into the architecture to perform tasks such as bounding box
regression and object classification. It’s important to note that non-binary
operations, such as batch normalization with scaling and shifting, remain in
floating-point precision. Similarly, the activation functions have not
undergone any alterations.

##  IV Experiments and Results

The conducted experiments encompass both classification and detection tasks,
with the primary objective of demonstrating the versatile utility of the STeP
blocks. Specifically, this research seeks to establish that these STeP blocks
can serve a dual purpose: 1) enhancing the computational efficiency of pre-
existing network architectures by seamlessly integrating STeP blocks in lieu
of traditional components, and 2) empowering the creation of custom neural
networks tailored for real-world applications, thereby achieving a balance
between competitive accuracy and efficiency improvements.

###  IV-A Image Classification

TABLE I: Comparison of Classification Networks

Model | Type | Trainable | Non Trainable | Acc-C10 | Acc-C100 | Acc-ImgN16 | Acc-Tiny200 | Memory† | Reduction†
---|---|---|---|---|---|---|---|---|---
Family |  | Parameters† | Parameters† | (%) | (%) | (%) | (%) | (MB) | (%)
VGG-16 | STeP(Prop.) | $1,652,490$ | $13,934,754$ | $90.4$ | $66.6$ | $81.1$ | $54.0$ | $10.1$ | $82.8$
[36] | Original | $14,728,266$ | $-$ | $94.0$ | $74.2$ | $85.3$ | $62.2$ | $58.9$ | $-$
| Rand. Binary | $13,578$ | $14,710,464$ | $61.8$ | $35.6$ | $61.3$ | $24.1$ | $1.89$ | $96.7$
ResNet50 | STeP(Prop.) | $13,463,114$ | $11,318,976$ | $94.8$ | $77.9$ | $91.2$ | $68.1$ | $56.6$ | $39.8$
[37] | Original | $23,520,842$ | $-$ | $95.4$ | $78.0$ | $88.2$ | $69.2$ | $94.1$ | $-$
| Rand. Binary | $12,201,866$ | $11,318,976$ | $90.7$ | $67.6$ | $78.5$ | $57.9$ | $51.6$ | $45.1$
MobileNet | STeP(Prop.) | $1,268,858$ | $1,091,810$ | $91.4$ | $69.1$ | $89.6$ | 57.0 | $5.3$ | $37.3$
V2 | Original | $2.360.668$ | $-$ | $94.3$ | $72.8$ | $91.0$ | 60.6 | $9.4$ | -
[24] | Rand. Binary | $859,034$ | $1,437,888$ | $69.1$ | $59.4$ | $70.1$ | 48.9 | $3.6$ | $61.7$
EfficientNet | STeP(Prop.) | $1,932,806$ | $1,644,578$ | $88.9$ | $63.4$ | $83.5$ | 53.0 | $8.1$ | $45.3$
B0 | Original | $3,598,598$ | $-$ | $91.4$ | $69.8$ | $85.6$ | 58.7 | $14.3$ | -
[26] | Rand. Binary | $1,932,806$ | $1,563,938$ | $82.0$ | $55.7$ | $33.5$ | 51.1 | $7.9$ | $44.7$

† Numbers calculated based on the architecture generated for the CIFAR-10
dataset. They are very similar for other datasets.

To assess the effectiveness of the proposed approach, experiments are
conducted using four distinct classification datasets. The CIFAR-10 dataset
(referred to as C-10) [38] consists of $32\times 32$ RGB images, containing
50,000 images for training and 10,000 images for testing, distributed across
ten classes. The CIFAR-100 dataset (referred to as C-100) encompasses a more
complex classification task, comprising 100 distinct classes. This dataset
consists of 600 images per class, divided into 500 training images and 100
testing images, all with a resolution of $32\times 32$ pixels. In addition,
the Tiny-ImageNet dataset (referred to as Tiny200), it also utilized, which
serves as a subset of the larger ImageNet dataset [39]. Tiny200 contains
100,000 images distributed across 200 classes, with each class containing 500
images. These images have been resized to $64\times 64$ pixels, offering a
balance between image quality and computational complexity. Lastly, the
Imagenet-16111https://zenodo.org/record/8027520 dataset (referred to as
ImgN16) is another subset of the renowned ImageNet dataset. It features a more
compact classification task with 16 distinct classes. Notably, ImgN16
maintains the original image resolutions, which are typically resized to
$224\times 224$ pixels for standard ImageNet evaluations. Collectively, these
datasets provide a comprehensive evaluation set, encompassing a wide range of
class counts and image resolutions, thereby enabling a thorough assessment of
the proposed approach.

Four prominent network architectures in the field of computer vision are used
in the evaluation with distinct characteristics and performance. The models
considered are the ResNet50 [37], MobileNetV2 [24], EfficientNet [26], and
VGG16 [36] which provide a comprehensive assessment across different design
philosophies and trade-offs. The comparative analysis also encompasses three
distinct weight generation settings. The original model utilizing weight
initialization and update through backpropagation, models initialized with
random binary weights, and models utilizing the STeP block with structured
ternary weights.

It is worth noting that not all network blocks were converted to non-learnable
ternary values. The changes concerned mainly the spatial kernels. Bottleneck
layers applied to shortcut connections, squeeze and excitation layers, and the
final classification layer weights were not converted for the purposes of
these experiments. This is left as additional area of investigation, while
benefits are still tangible even with partial modification.

All networks are trained from scratch for $200$ epochs, with a starting
learning rate of $0.1$ and weight decay of $5\times 10^{-4}$, and a cosine
annealing scheduler. An initial batch size of 128 is used. Where feasible for
the binary/STeP models larger batch sizes are applied. During the training
process, the data are augmented with random padding and crop to standard size,
as well as random horizontal flipping as per standard practice.

Figure 4: STeP network architecture used for object detection.

The results, as presented in Table I, showcase the notable enhancements in
model characteristics arising from the proposed methodology. It is noteworthy
that the VGG-16 network exhibits the most substantial reduction in learnable
parameters, primarily owing to its utilization of traditional convolution
layers. Consequently, employing ternary values for storage leads to a $82\%$
reduction in storage size. As anticipated, the random binary weight model
demonstrates the most significant reduction in learnable parameters; however,
this improvement is accompanied by consistently diminished accuracy across all
datasets. On average, the proposed approach demonstrates a commendable average
reduction of approximately $56.1\%$ in learnable parameters and a noteworthy
average memory reduction of approximately $50.8\%$ across various models.

With regard to attainable accuracy across all datasets, it is noteworthy that
while random binary patterns exhibit competitive performance in certain
instances, the STeP block consistently demonstrates superior performance
across all experimental scenarios. More precisely, the STeP models exhibit
only an average accuracy degradation of $3.1\%$ compared to the full-precision
model, whereas the random binary models experience an average accuracy
reduction of $20.2\%$. Notably, when examining specific cases, we find that
the STeP model derived from ResNet even manages to yield a slight improvement
in accuracy for the Imagenet-16 dataset. This phenomenon can be attributed to
the reduced number of learned parameters, which mitigates overfitting to some
extent. Conversely, in the same case, the random binary model experiences a
significant decline of over $9\%$ compared to the original model. Across
various model architectures, it is evident that STeP variants consistently
deliver robust performance. Notably, the ResNet network experiences the least
reduction in performance, primarily due to its larger number of trainable
parameters. Even for datasets with larger image dimensions, such as
Imagenet-16 and TinyImagenet, the STeP-based performance remains consistent.
Also, compared to more complex approaches for creating efficient neural
networks [40], the proposed approach demonstrates improved performance on C-10
and C-100, and is extensible to object detection as well while it does not
require iterative training.

TABLE II: Comparison of Detection Networks

Backbone | Trainable | Non Trainable Param. | mAP | IoU | Memory(MB)
---|---|---|---|---|---
STeP-Det (Proposed) | $232,492$ | $3,738,560$ | $0.68$ | $0.63$ | $1.6$
LBC-Net [9] | $455,326$ | $3,507,648$ | $0.61$ | $0.48$ | $2.2$
MobileNet [41] | $3,477,342$ | $-$ | $0.681$ | $0.55$ | $13.9$
MobileNetV2[24] | $3,568,670$ | $-$ | $0.69$ | $0.59$ | $14.2$
DarkNet-19 [42] | $15,770,510$ | $-$ | $0.7$ | $0.61$ | $63.0$

Figure 5: Detection results on aerial images for the application of vehicle
detection using STeP-Det.

###  IV-B Object Detection

The second evaluation scenario illustrates the potential for further
enhancements by optimizing the architecture and extending upon the proposed
STeP block. In this experiment, the focus is on aerial vehicle detection using
Unmanned Aerial Vehicles (UAVs), which serves as a quintessential example of
an on-device AI application where the utility of lightweight models is
particularly evident [43].

A comparative analysis is conducted involving a network architecture comprised
of successive STeP blocks, benchmarked against other lightweight networks
featuring ImageNet-pretrained backbones, such as MobileNets [24, 41] and
Darknet-19 [42], as well as a network with LBP convolutional layers from [35].
For the evaluation a dataset comprising approximately $\sim 1500$ aerial
images is used, with $\sim 1000$ images allocated for training and $\sim 500$
for testing, all of which are standardized to a size of $320\times 320$
pixels. The test dataset consists of approximately $\sim 3800$ vehicle
instances. The training process extends to $300$ epochs, with an initial
learning rate set to $5\times 10^{-3}$. Cosine annealing is employed in
conjunction with the Adam optimizer [44]. Throughout the training phase, both
photometric and geometric augmentations are applied to alleviate overfitting.
The chosen loss function closely resembles the one utilized in [42]. Model
performance is evaluated using well-established metrics, including Mean
Average Precision (mAP) and Intersection-over-Union (IoU). The architecture of
the STeP network adheres to the standard ConvNet structure, as illustrated in
Figure 4. It features an increasing number of filters with increasing depth
and utilizes a combination of striding and average pooling to reduce feature
map dimensions. Notably, all convolutional layers integrate the STeP block
with ternary patterns. While more sophisticated architectural variations are
conceivable, they remain a subject of future research investigation.

An overall comparison is presented in Table II. As observed from the table,
the model employing the proposed backbone consistently achieves a competitive
mAP score comparable to networks with significantly higher numbers of
parameters. Furthermore, it exhibits superior accuracy compared to the
baseline LBC-Net, while also attaining a substantially improved Intersection
over Union (IoU) score, rivaling that of much larger networks. Notably, both
memory usage and parameter count remain significantly lower in comparison to
other network architectures. This overall analysis underscores the efficiency
of the proposed approach. With a markedly reduced number of trainable
parameters ($<<10^{6}$) and a conventional network structure, it demonstrates
the capability to effectively detect very fine-grained and small dense
objects, as shown in Fig. 5. This accomplishment is particularly noteworthy,
given that the task of detecting such objects is widely recognized as
challenging, even for more complex network architectures [43].

Overall, the combination of Haar and CS-LBP features yields a diverse set of
features that can effectively maintain network performance, while concurrently
reducing the computational/storage requirements. Furthermore, the advantages
stem without necessitating any modifications to the training procedure.

##  V Conclusion and Future Work

This work has demonstrated the effectiveness of utilizing structured ternary
patterns, a combination of local binary patterns and Haar features, as a
foundation for competitive networks in resource-constrained on-device AI
applications. The proposed approach has yielded promising results and has
demonstrated performance comparable to that of fully trainable convolutional
networks, as validated by the experiments. Distinguishing itself from much of
the related work on compression techniques, the proposed method enables direct
learning of efficient models. The use of a large number of static parameters
in the model offers significant advantages for updating model parameters
during deployment and facilitating more efficient federated learning
approaches.

Future research should prioritize the enhancement of both feature and
architectural spaces to further optimize designs for maximum efficiency.
Additionally, it is imperative to delve deeper into the training process to
formulate an optimized training strategy tailored to networks of this nature.
Given the reduced number of trainable parameters, consideration should be
given to adopting smaller learning rates and potentially extending the number
of training epochs. Finally, with the recent trend in using Neural
Architecture Search, it would be worthwhile to build a search space based on
structured ternary patterns and formulate an automated network design process
that also encodes efficiency measures.

## Acknowledgements

This work is supported by the European Union Horizon 2020 Teaming, KIOS CoE,
No. 739551 and from the Government of the Republic of Cyprus through the
Deputy Ministry of Research, Innovation, and Digital Policy.
The author gratefully acknowledges the support of NVIDIA Corporation with the
donation of a A6000 GPU used for this research.

## References

  * [1] C. Kyrkou, “$\text{C}^{3}\text{Net}$: End-to-end deep learning for efficient real-time visual active camera control,” _Journal of Real-Time Image Processing_ , vol. 18, no. 4, pp. 1421–1433, 08 2021. [Online]. Available: https://doi.org/10.1007/s11554-021-01077-z
  * [2] Q. Zhang, M. Zhang, M. Wang, W. Sui, C. Meng, J. Yang, W. Kong, X. Cui, and W. Lin, “Efficient deep learning inference based on model compression,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) Workshops_ , June 2018.
  * [3] A. Ignatov, G. Malivenko, R. Timofte, S. Chen, X. Xia, Z. Liu, Y. Zhang, F. Zhu, J. Li, X. Xiao, Y. Tian, X. Wu, C. Kyrkou, Y. Chen, Z. Zhang, Y. Peng, Y. Lin, S. Dutta, S. D. Das, N. A. Shah, H. Kumar, C. Ge, P.-L. Wu, J.-H. Du, A. Batutin, J. P. Federico, K. Lyda, L. Khojoyan, A. Thanki, S. Paul, and S. Siddiqui, “Fast and accurate quantized camera scene detection on smartphones, mobile ai 2021 challenge: Report,” in _2021 IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW)_ , 2021, pp. 2558–2568.
  * [4] M. Courbariaux, I. Hubara, D. Soudry, R. El-Yaniv, and Y. Bengio, “Binarized neural networks: Training deep neural networks with weights and activations constrained to+ 1 or-1,” _arXiv preprint arXiv:1602.02830_ , 2016.
  * [5] M. Rastegari, V. Ordonez, J. Redmon, and A. Farhadi, “Xnor-net: Imagenet classification using binary convolutional neural networks,” in _Computer Vision – ECCV 2016_ , B. Leibe, J. Matas, N. Sebe, and M. Welling, Eds. Cham: Springer International Publishing, 2016, pp. 525–542.
  * [6] P. Nayak, D. Zhang, and S. Chai, “Bit efficient quantization for deep neural networks,” in _2019 Fifth Workshop on Energy Efficient Machine Learning and Cognitive Computing - NeurIPS Edition (EMC2-NIPS)_ , 2019, pp. 52–56.
  * [7] A. Abdolrashidi, L. Wang, S. Agrawal, J. Malmaud, O. Rybakov, C. Leichner, and L. Lew, “Pareto-optimal quantized resnet is mostly 4-bit,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) Workshops_ , June 2021, pp. 3091–3099.
  * [8] V. W.-S. Tseng, S. Bhattacharya, J. F. Marqués, M. Alizadeh, C. Tong, and N. D. Lane, “Deterministic binary filters for convolutional neural networks,” in _Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI-18_. International Joint Conferences on Artificial Intelligence Organization, 7 2018, pp. 2739–2747.
  * [9] F. Juefei-Xu, V. Boddeti, and M. Savvides, “Local binary convolutional neural networks,” in _2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_. Los Alamitos, CA, USA: IEEE Computer Society, jul 2017, pp. 4284–4293. [Online]. Available: https://doi.ieeecomputersociety.org/10.1109/CVPR.2017.456
  * [10] J.-H. Lin, J. Lazarow, Y. Yang, D. Hong, R. K. Gupta, and Z. Tu, “Local binary pattern networks,” in _2020 IEEE Winter Conference on Applications of Computer Vision (WACV)_ , 2020, pp. 814–823.
  * [11] P. Wang, F. Li, G. Li, and J. Cheng, “Extremely sparse networks via binary augmented pruning for fast image classification,” _IEEE Transactions on Neural Networks and Learning Systems_ , vol. 34, no. 8, pp. 4167–4180, 2023.
  * [12] C. Zhu, S. Han, H. Mao, and W. J. Dally, “Trained ternary quantization,” _arXiv preprint arXiv:1612.01064_ , 2016.
  * [13] T. Liang, J. Glossner, L. Wang, S. Shi, and X. Zhang, “Pruning and quantization for deep neural network acceleration: A survey,” _Neurocomputing_ , vol. 461, pp. 370–403, 2021.
  * [14] B. Jacob, S. Kligys, B. Chen, M. Zhu, M. Tang, A. Howard, H. Adam, and D. Kalenichenko, “Quantization and training of neural networks for efficient integer-arithmetic-only inference,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2018, pp. 2704–2713.
  * [15] Q. Jin, L. Yang, and Z. Liao, “Adabits: Neural network quantization with adaptive bit-widths,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2020, pp. 2146–2156.
  * [16] W. Fei, W. Dai, C. Li, J. Zou, and H. Xiong, “General bitwidth assignment for efficient deep convolutional neural network quantization,” _IEEE Transactions on Neural Networks and Learning Systems_ , vol. 33, no. 10, pp. 5253–5267, 2022.
  * [17] K. Li, N. Wang, J. Xin, X. Jiang, J. Li, X. Gao, K. Han, and Y. Wang, “Local means binary networks for image super-resolution,” _IEEE Transactions on Neural Networks and Learning Systems_ , pp. 1–11, 2022.
  * [18] J. Xu, W. Du, Y. Jin, W. He, and R. Cheng, “Ternary compression for communication-efficient federated learning,” _IEEE Transactions on Neural Networks and Learning Systems_ , vol. 33, no. 3, pp. 1162–1176, 2022.
  * [19] S. Ghamari, K. Ozcan, T. Dinh, A. Melnikov, J. Carvajal, J. Ernst, and S. Chai, “Quantization-guided training for compact tinyml models,” _arXiv preprint arXiv:2103.06231_ , 2021.
  * [20] G. Menghani, “Efficient deep learning: A survey on making deep learning models smaller, faster, and better,” _ACM Computing Surveys_ , vol. 55, no. 12, pp. 1–37, 2023.
  * [21] Z. Li, F. Liu, W. Yang, S. Peng, and J. Zhou, “A survey of convolutional neural networks: Analysis, applications, and prospects,” _IEEE Transactions on Neural Networks and Learning Systems_ , vol. 33, no. 12, pp. 6999–7019, 2022.
  * [22] R. J. Wang, X. Li, and C. X. Ling, “Pelee: A real-time object detection system on mobile devices,” _Advances in neural information processing systems_ , vol. 31, 2018.
  * [23] B. Koonce and B. Koonce, “Squeezenet,” _Convolutional Neural Networks with Swift for Tensorflow: Image Recognition and Dataset Categorization_ , pp. 73–85, 2021.
  * [24] M. Sandler, A. Howard, M. Zhu, A. Zhmoginov, and L.-C. Chen, “Mobilenetv2: Inverted residuals and linear bottlenecks,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , June 2018.
  * [25] N. Ma, X. Zhang, H.-T. Zheng, and J. Sun, “Shufflenet v2: Practical guidelines for efficient cnn architecture design,” in _Proceedings of the European conference on computer vision (ECCV)_ , 2018, pp. 116–131.
  * [26] M. Tan and Q. V. Le, “Efficientnet: Rethinking model scaling for convolutional neural networks,” _CoRR_ , vol. abs/1905.11946, 2019. [Online]. Available: http://arxiv.org/abs/1905.11946
  * [27] K. Han, Y. Wang, Q. Tian, J. Guo, C. Xu, and C. Xu, “Ghostnet: More features from cheap operations,” in _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , 2020, pp. 1580–1589.
  * [28] A. B. Shetty, Bhoomika, Deeksha, J. Rebeiro, and Ramyashree, “Facial recognition using haar cascade and lbp classifiers,” _Global Transitions Proceedings_ , vol. 2, no. 2, pp. 330–335, 2021, international Conference on Computing System and its Applications (ICCSA- 2021). [Online]. Available: https://www.sciencedirect.com/science/article/pii/S2666285X21000728
  * [29] S. Zhang, C. Bauckhage, and A. B. Cremers, “Informed haar-like features improve pedestrian detection,” in _2014 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_. Los Alamitos, CA, USA: IEEE Computer Society, jun 2014, pp. 947–954. [Online]. Available: https://doi.ieeecomputersociety.org/10.1109/CVPR.2014.126
  * [30] Y. Zheng, C. Shen, R. Hartley, and X. Huang, “Pyramid center-symmetric local binary/trinary patterns for effective pedestrian detection,” in _Computer Vision – ACCV 2010_ , R. Kimmel, R. Klette, and A. Sugimoto, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011, pp. 281–292.
  * [31] C. Kyrkou, C.-S. Bouganis, T. Theocharides, and M. M. Polycarpou, “Embedded hardware-efficient real-time classification with cascade support vector machines,” _IEEE Transactions on Neural Networks and Learning Systems_ , vol. 27, no. 1, pp. 99–112, 2016.
  * [32] P. Viola and M. Jones, “Rapid object detection using a boosted cascade of simple features,” in _Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. CVPR 2001_ , vol. 1, 2001, pp. I–I.
  * [33] C. Kyrkou and T. Theocharides, “A flexible parallel hardware architecture for adaboost-based real-time object detection,” _IEEE Transactions on Very Large Scale Integration (VLSI) Systems_ , vol. 19, no. 6, pp. 1034–1047, 2011\.
  * [34] C. Kyrkou, T. Theocharides, C.-S. Bouganis, and M. Polycarpou, “Boosting the hardware-efficiency of cascade support vector machines for embedded classification applications,” _International Journal of Parallel Programming_ , vol. 46, no. 6, pp. 1220–1246, 12 2018.
  * [35] F. Juefei-Xu, V. N. Boddeti, and M. Savvides, “Local binary convolutional neural networks,” in _2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2017, pp. 4284–4293.
  * [36] K. Simonyan and A. Zisserman, “Very deep convolutional networks for large-scale image recognition,” in _International Conference on Learning Representations_ , 2015.
  * [37] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in _2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2016, pp. 770–778.
  * [38] A. Krizhevsky, G. Hinton _et al._ , “Learning multiple layers of features from tiny images,” 2009.
  * [39] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei, “Imagenet: A large-scale hierarchical image database,” in _2009 IEEE conference on computer vision and pattern recognition_. Ieee, 2009, pp. 248–255.
  * [40] H. Salehinejad and S. Valaee, “Edropout: Energy-based dropout and pruning of deep neural networks,” _IEEE Transactions on Neural Networks and Learning Systems_ , vol. 33, no. 10, pp. 5279–5292, 2022.
  * [41] A. G. Howard, M. Zhu, B. Chen, D. Kalenichenko, W. Wang, T. Weyand, M. Andreetto, and H. Adam, “Mobilenets: Efficient convolutional neural networks for mobile vision applications,” _arXiv preprint arXiv:1704.04861_ , 2017.
  * [42] J. Redmon and A. Farhadi, “Yolo9000: Better, faster, stronger,” in _2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , July 2017, pp. 6517–6525.
  * [43] R. Makrigiorgis, N. Hadjittoouli, C. Kyrkou, and T. Theocharides, “Aircamrtm: Enhancing vehicle detection for efficient aerial camera-based road traffic monitoring,” in _2022 IEEE/CVF Winter Conference on Applications of Computer Vision (WACV)_ , 2022, pp. 3431–3440.
  * [44] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” in _3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings_.


# Coordination Sequences of Periodic Structures are Rational via Automata
Theory

Eryk Kopczyński
Institute of Informatics, University of Warsaw

(February 18, 2022)

###### Abstract

We prove the conjecture of Grosse-Kunstleve et al. that coordination sequences
of periodic structures in $n$-dimensional Euclidean space are rational. This
has been recently proven by Nakamura et al.; however, our proof is a
straightforward application of classic techniques from automata theory.

Keywords: coordination sequences, periodic structures, rational generating
functions

##  1 Introduction

A periodic graph is a graph $(V,E)$ with a free action of ${\mathbb{Z}}^{d}$
on $V$, such that $V/{\mathbb{Z}}^{d}$ is finite, and such that for every
$\\{u,w\\}\in E$ and $g\in{\mathbb{Z}}^{d}$, we have $\\{gu,gw\\}\in E$. A
coordination sequence of such a graph and vertex $v_{0}\in V$ is
$(c_{0},c_{1},c_{2},\ldots)$ such that $c_{i}$ is the number of vertices $v\in
V$ such that the length of the shortest path from $v_{0}$ to $v$ equals $i$.

From the paper by Chaim Goodman-Strauss and Neil Sloane 2019 we have learned
about the conjecture of Grosse-Kunstleve _et al._ (1996) that the generating
functions of coordination sequences are rational, which was open even in
dimension 2. The generating function of a sequence
$(c_{0},c_{1},c_{2},\ldots)$ is defined as $q(z)=\sum_{z\geq 0}c_{i}z^{i}$;
see e.g. Graham _et al._ (1989) for an introduction to generating functions.
The following conditions are equivalent for polynomially bounded sequences:

  * •

the generating function $q(z)$ is rational, i.e., $q(z)=p_{1}(z)/p_{2}(z)$
where $p_{1}$ and $p_{2}$ are polynomials,

  * •

the sequence $c_{k}$ can be computed using linear recursion: there exist
$b_{1},\ldots,b_{t}\in{\mathbb{R}}$ and $k_{0}$ such that for $k>k_{0}$ we
have $c_{k}=\sum_{i=1}^{t}b_{i}c_{k-i}$,

  * •

the sequence $c_{k}$ is quasi-polynomial, i.e., we have $c_{k}=\sum
a_{i}(k)k^{i}$, where $a_{i}(k)$ is a periodic function.

In this paper, we prove that this conjecture is a rather simple consequence of
known techniques in automata theory. The paper by Goodman-Strauss and Sloane
(2019) studies coordination sequences in specific two-dimensional cases, and
contains a beautiful bibliography on coordination sequences. Coordination
sequences have been found in specific cases by O’Keeffe (1991), Eon (2002),
Shutov and Maleev (2019), Shutov and Maleev (2020). This conjecture has been
recently proven by Nakamura _et al._ (2021), however, we believe that our
simple proof is still insightful, as it shows another strong connection
between apparently unrelated fields of crystallography and automata theory. In
particular, we believe that recent research in the computational aspects of
Parikh images Kopczynski and To (2010); Chistikov and Haase (2016) may prove
useful in crystallography. Previously, strong connections were known between
automata theory and periodic structures in hyperbolic geometry Epstein _et
al._ (1992). In Euclidean geometries, translations are commutative, so (in the
2D case) any translation by a vector in ${\mathbb{Z}}^{2}$ can be written as
$a^{n}b^{m}$ where $a$ and $b$ are two translations corresponding to the
periods. In the case of hyperbolic geometry, we also can use a finite number
of generators, but this time, the order matters, so the structure of a similar
representation (word) is more complex. Formal language theory, and
specifically the theory of finite automata, provides a framework to deal with
such representations. The tools for the Euclidean case are also provided by
automata theory: the Parikh image of a set of words is a subset of
${\mathbb{Z}}^{d}$ which contains the information about the possible numbers
of occurences of every generator, abstracting from their order.

Our proof is based on the fact that, given a periodic graph, we can create a
finite automaton $A$ such that the Parikh image of $A$ is the set of all
$(x_{1},\ldots,x_{n},z)$ such that there is a vertex $v$ of $V$ at coordinates
$(x_{1},\ldots,x_{n})$ and that the length of the shortest path from $v_{0}$
to $v$ is at most $z$. By the Parikh theorem Parikh (1966), this set is
semilinear. It is known that every semilinear set has an unambiguous
representation as a union of disjoint unambiguous linear sets Eilenberg and
Schützenberger (1969); Ito (1969); Chistikov and Haase (2016). If
$S\subseteq{\mathbb{Z}}^{d}$ is an unambiguous linear set, the generating
function $\sum_{(x_{1},\ldots,x_{n},d)\in S}z^{d}$ is rational, therefore, the
generating function of every semilinear set is rational.

The rest of the paper provides the necessary definitions and details of the
proof.

##  2 Semilinear sets

Let ${\mathbb{N}}=\\{0,1,2,3,\ldots\\}$. A linear set is a set
$A\subset{\mathbb{Z}}^{d}$ of form
$L(b,a_{1},\ldots,a_{k})=\\{b+a_{1}n_{1}+a_{2}n_{2}+\ldots+a_{k}n_{k}:n_{1},\ldots,n_{k}\in{\mathbb{N}}\\}$.
A linear set $L(b,a_{1},\ldots,a_{k})$ is unambiguous iff every $x\in
L(b,a_{1},\ldots,a_{k})$ can be written in the form
$b+a_{1}n_{1}+a_{2}n_{2}+\ldots+a_{k}n_{k}$ in exactly one way.

A semilinear set $A\subseteq{\mathbb{Z}}^{d}$ is a union of linear sets.

Example. Consider the set $A:\\{(a,b)\in{\mathbb{N}}^{2}:a=b=0\vee(a,b\geq
2\wedge 2|a+b\\}$. This set is a semilinear set, since it is a union of
$\\{(0,0)\\}=L((0,0))$ and $A_{2}=L((2,2),(2,0),(1,1),(0,2))$. The set $A_{2}$
is not unambiguous, since e.g. $(4,4)$ can be represented in two ways, as
$(2,2)+(2,0)+(0,2)$ or $(2,2)+(1,1)+(1,1)$. However, $A_{2}$ can be written as
a union of two unambiguous linear sets, for example,
$A_{2}=L((2,2),(2,0),(0,2))\cup L((3,3),(2,0),(0,2))$. Therefore, $A$ is a
disjoint union of three unambiguous linear sets.

See Hopcroft and Ullman (1979); Kozen (1997) for an introduction to automata
theory. A (non-deterministic) finite automaton (NFA) over ${\mathbb{Z}}^{d}$
is a tuple $A=\\{Q,I,F,\delta\\}$, where $Q$ is a finite set of states,
$I\subseteq Q$ is the set of initial states, $F\subseteq Q$ is the set of
final states, and $\delta\subseteq Q\times{\mathbb{Z}}^{d}\times Q$ is the
(finite) set of transitions. For $(s,a,t)=d\in\delta$, we call $s=s(d)$ the
source state of $d$, $t=t(d)$ the target state of $d$, and $a=a(d)$ the output
of $d$.

A run of the finite automaton $A$ of length $k>0$ is a sequence
$r=(r_{1},\ldots,r_{k})\in\delta^{k}$ (for some $k$) such that $s(r_{1})\in
I$, $s(r_{i+1})=t(r_{i})$ for $i=1,\ldots,k-1$, and $t(r_{k})\in F$. An empty
run (of length $k=0$) is also allowed if $I\cap F\neq\emptyset$ (intuitively,
such runs start in an initial state and end in the same state without taking
any transitions). The Parikh image of a run $r$, denoted $\Psi(r)$, is
$\sum_{i=1}^{k}a(r_{i})$. The Parikh image of an automaton $A$, denoted
$\Psi(A)$, is the set of Parikh images of all its runs. We use the following
fact:

######  Theorem 1 (Parikh’s Theorem, Parikh (1966)).

The Parikh image of a NFA is a semilinear set.

Note: in this paper $\delta\subseteq Q\times{\mathbb{Z}}^{d}\times Q$. The
usual convention in automata theory is to take $\delta\subseteq
Q\times\Sigma\times Q$, where $\Sigma$ is a finite alphabet
$\Sigma=\\{a_{1},\ldots,a_{d}\\}$, and the Parikh image of a run is defined as
a vector $v\in{\mathbb{N}}^{d}$ such that $v_{i}$ is the number of transitions
labeled with $a_{i}$. Our convention generalizes the usual convention – just
take $a_{i}$ to be the $i$-th unit vector. However, it is straightforward to
generalize Parikh’s Theorem to our setting Kopczynski and To (2010). Indeed,
our finite automaton can be seen as an automaton over the finite alphabet
$\Sigma=\\{a_{1},\ldots,a_{m}\\}$ where $a_{i}$ are the vectors appearing as
outputs. By the usual Parikh’s theorem, the Parikh’s image of $A$,
$\Psi_{1}(M)$, is a semilinear subset of ${\mathbb{N}}^{m}$. Let
$\phi:{\mathbb{N}}^{m}\rightarrow{\mathbb{Z}}^{k}$ be given as
$\phi(n_{1},\ldots,n_{m})=\sum_{i=1,\ldots,m}a_{i}n_{i}$. The Parikh image in
our sense, $\Psi(M)$, can then be written as $\phi(\Psi(m))$. Since $\phi$ is
linear, it maps semilinear sets to semilinear sets.

Parikh images and semilinear sets are a widely studied topic in automata
theory; see Chistikov and Haase (2016) for a recent reference. The following
characterization of semilinear sets will be useful:

######  Theorem 2 (Eilenberg and Schützenberger (1969); Ito (1969); Chistikov
and Haase (2016)).

Every semilinear set can be represented as a union of disjoint unambiguous
linear sets.

Let $\pi_{i}:{\mathbb{Z}}^{d}\rightarrow{\mathbb{Z}}$ be the projection on the
$i$-th coordinate. For a set $S\subseteq{\mathbb{Z}}^{d}$ such that
$\pi_{i}(s)\geq 0$ for all $s\in S$, let $q_{i}(S)(z)=\sum_{s\in
S}z^{\pi_{i}(s)}$, that is, the generating function of the sequence $(a_{n})$
where $a_{n}$ is the number of elements of $S$ such that $\pi_{i}(s)=a_{n}$.

######  Theorem 3.

If $S$ is a semilinear set such that $\pi_{i}(s)\geq 0$ for all $s\in S$, the
generating function $q_{i}(S)$ is rational.

###### Proof.

If $S=L(b,a_{1},\ldots,a_{k})$ is an unambiguous linear set, every element of
$S$ can be written as $b+\sum_{j=1..k}n_{j}a_{j}$ in exactly one way, so we
have

$\displaystyle q_{i}(S)$ $\displaystyle=$
$\displaystyle\sum_{n_{1},\ldots,n_{k}\in{\mathbb{N}}}z^{\pi_{i}\left(b+\sum_{j}n_{j}a_{j}\right)}=\sum_{n_{1},\ldots,n_{k}\in{\mathbb{N}}}z^{\pi_{i}(b)}\prod_{j=1..k}z^{\pi_{i}(n_{j}a_{j})}=$
$\displaystyle=$ $\displaystyle
z^{\pi_{i}(b)}\prod_{j=1}^{k}\sum_{n_{j}\in{\mathbb{N}}}z^{n_{j}\pi_{i}(a_{j})}=z^{\pi_{i}(b)}/\prod_{j=1}^{k}(1-z^{\pi_{i}(a_{j})}).$

In general, by Theorem 2, $S$ has an unambiguous representation
$S=S_{1}\cup\ldots\cup S_{k}$ where $S_{i}$ are disjoint unambiguous linear
sets, and thus, $q_{i}(S)=\sum_{j}q_{i}(S_{j})$. ∎

##  3 Periodic graphs

Given the definition of a periodic graph presented in the introduction, let
$\\{v_{1},\ldots,v_{m}\\}=V_{0}\subseteq V$ be a set containing exactly one
element from every orbit of the action of ${\mathbb{Z}}^{d}$. We will prove
the following:

######  Theorem 4.

For $v_{0}\in V_{0}$ and $i\in\\{1,\ldots,m\\}$, the set $C(v_{0},i)$ of
$\\{(x_{1},\ldots,x_{d},y)\in{\mathbb{Z}}^{d}\times{\mathbb{N}}\\}$ such that
there exists a path from $v_{0}$ to $(x_{1},\ldots,x_{d})v_{i}\in G$ of length
at most $y$ is a semilinear set.

###### Proof.

We will construct a NFA $A$ such that $\Psi(A)=C(v_{0},i)$.

Our set of states will be $Q=V_{0}$.

Our set of initial states will be $I=\\{v_{0}\\}$.

Our set of final states will be $F=\\{v_{i}\\}$.

Every orbit of edges contains exactly one edge from some $v_{s}\in V_{0}$ to
$v^{\prime}_{t}\in V$, which can be written as $(x_{1},\ldots,x_{d})v_{t}$ for
some $v_{t}\in V_{0}$. For every orbit of edges we include a transition $d$
such that $s(d)=v_{s}$, $t(d)=v_{t}$, and $a(d)=\\{x_{1},\ldots,x_{d},1\\}$.

For every $v_{s}\in V_{0}$ we also include a transition $d$ such that
$s(d)=t(d)=v_{s}$ and $a(d)=\\{0,\ldots,0,1\\}$.

It is straightforward to show that $(x_{1},\ldots,x_{d},y)\in\Psi(A)$ iff
there is a path from $v_{0}$ to $T_{1}^{x_{i}}T_{2}^{x_{2}}\ldots
T_{d}^{x_{d}}v_{i}\in G$ of length at most $y$, which proves the theorem. ∎

Figure 1: Figure 1. A periodic graph, and its automaton

See Figure 1 for an example periodic graph with $m=3$ orbits, and a diagram of
the NFA from the proof of Theorem 4. We have $V_{0}=\\{v_{1},v_{2},v_{3}\\}$.
Translations work as follows: $u_{i}=(1,0)v_{i}$, $w_{i}=(0,1)v_{i}$. In the
diagram in Figure 1, a transition from $v_{i}$ to $v_{j}$ with output $a$ is
depicted as an arrow from $v_{i}$ to $v_{j}$ labelled $a$.

######  Corollary 5.

The generating function of the coordination sequence of a periodic graph
$(V,E)$ starting from $v_{0}$ is rational.

###### Proof.

By Theorem 3, the generating function $q_{d+1}(C(v_{0},i))$ is rational. To
count only paths of maximal length exactly $y$, we need to divide this
generating function by $1/(1-z)$. Therefore, the generating function of the
coordination sequence of $V$ from $v_{0}$ is rational. ∎

Acknowledgments. This work has been supported by the National Science Centre,
Poland, grant UMO-2019//35/B/ST6/04456. We are grateful to the anonymous
referees for their suggestions which improved this paper.

## References

  * (1)
  * Chistikov and Haase (2016) Chistikov, D. and Haase, C. (2016).  In _43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy_ , edited by I. Chatzigiannakis, M. Mitzenmacher, Y. Rabani and D. Sangiorgi, vol. 55 of _LIPIcs_ , pp. 128:1–128:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.ICALP.2016.128

  * Eilenberg and Schützenberger (1969) Eilenberg, S. and Schützenberger, M. (1969).  _Journal of Algebra_ , 13(2), 173–191.
https://www.sciencedirect.com/science/article/pii/0021869369900702

  * Eon (2002) Eon, J.-G. (2002).  _Acta Crystallographica Section A: Foundations of Crystallography_ , 58(1), 47–53.
  * Epstein _et al._ (1992) Epstein, D. B. A., Paterson, M. S., Cannon, J. W., Holt, D. F., Levy, S. V. and Thurston, W. P. (1992).  _Word Processing in Groups_.  USA: A. K. Peters, Ltd.
  * Goodman-Strauss and Sloane (2019) Goodman-Strauss, C. and Sloane, N. J. A. (2019).  _Acta Crystallographica Section A_ , 75(1), 121–134.
https://onlinelibrary.wiley.com/doi/abs/10.1107/S2053273318014481

  * Graham _et al._ (1989) Graham, R. L., Knuth, D. E. and Patashnik, O. (1989).  _Concrete Mathematics: A Foundation for Computer Science_.  Reading: Addison-Wesley.
  * Grosse-Kunstleve _et al._ (1996) Grosse-Kunstleve, R. W., Brunner, G. O. and Sloane, N. J. A. (1996).  _Acta Crystallographica Section A_ , 52(6), 879–889.
https://doi.org/10.1107/S0108767396007519

  * Hopcroft and Ullman (1979) Hopcroft, J. E. and Ullman, J. D. (1979).  _Introduction to Automata Theory, Languages, and Computation_.  Reading, Massachusets, USA: Adison-Wesley Publishing Company.
  * Ito (1969) Ito, R. (1969).  _J. Comput. Syst. Sci._ 3(2), 221–231.
https://doi.org/10.1016/S0022-0000(69)80014-0

  * Kopczynski and To (2010) Kopczynski, E. and To, A. W. (2010).  In _Proceedings of the 2010 25th Annual IEEE Symposium on Logic in Computer Science_ , LICS ’10, pp. 80–89. Washington, DC, USA: IEEE Computer Society.
http://dx.doi.org/10.1109/LICS.2010.21

  * Kozen (1997) Kozen, D. C. (1997).  _Automata and Computability_.  Berlin, Heidelberg: Springer-Verlag, 1st ed.
  * Nakamura _et al._ (2021) Nakamura, Y., Sakamoto, R., Mase, T. and Nakagawa, J. (2021).  _Acta Crystallographica Section A_ , 77(2), 138–148.
https://doi.org/10.1107/S2053273320016769

  * O’Keeffe (1991) O’Keeffe, M. (1991).  _Zeitschrift für Kristallographie_ , 196(1-4), 21–38.
https://doi.org/10.1524/zkri.1991.196.14.21

  * Parikh (1966) Parikh, R. (1966).  _J. ACM_ , 13(4), 570–581.
  * Shutov and Maleev (2019) Shutov, A. and Maleev, A. (2019).  _Zeitschrift für Kristallographie – Crystalline Materials_ , 234, 291–299.
  * Shutov and Maleev (2020) Shutov, A. and Maleev, A. (2020).  _Zeitschrift für Kristallographie - Crystalline Materials_ , 235(4-5), 157–166.
https://doi.org/10.1515/zkri-2020-0002


# Constraining quantum fluctuations of spacetime foam from BBN

S. Das1<EMAIL_ADDRESS>G. Lambiase2,3<EMAIL_ADDRESS>E.C. Vagenas4
<EMAIL_ADDRESS>1Theoretical Physics Group and Quantum Alberta,
Department of Physics and Astronomy, University of Lethbridge, 4401 University
Drive, Lethbridge, Alberta, T1K 3M4, Canada.  2Dipartimento di Fisica ”E.R.
Caianiello” Università di Salerno, I-84084 Fisciano (Sa), Italy,  3INFN -
Gruppo Collegato di Salerno, Italy.  4Theoretical Physics Group, Department of
Physics, Kuwait University, P.O. Box 5969, Safat 13060, Kuwait

###### Abstract

A possibility to describe quantum gravitational fluctuations of the spacetime
background is provided by virtual $D$-branes. These effects may induce a tiny
violation of the Lorentz invariance (as well as a possible violation of the
equivalence principle). In this framework, we study the formation of light
elements in the early Universe (Big Bang Nucleosynthesis). By using the Big
Bang Nucleosynthesis observations, We infer an upper bound on the topological
fluctuations in the spacetime foam vacuum $\sigma^{2}$, given by
$\sigma^{2}\lesssim 10^{-22}$.

###### pacs:

04.50.-h, 04.60.Bc

##  I Introduction

Formulating a quantum theory of gravity is one of the most important
challenges of the modern approaches aimed to unify all fundamental
interactions. These studies have clearly shown that spacetime must have a non-
trivial topology near the Planck scale. After the Wheeler wheeler  suggestion
that spacetime may have a foam-like structure, the study of quantum
fluctuations of the spacetime background have received a lot of interest
hawking80 ; hawking82 ; ellis84 ; ellis92 ; garay1 ; garay2 ; ellis99 ;
ellis99_1 .

The Planck-size topological fluctuations imply that the (quantum
gravitational) vacuum behaves as a non-trivial medium. This occurs, for
example, in the framework of string theory amelino97  and of the canonical
approach to quantum gravity pullin ; yu . The underlying idea of Ref.
amelino97  is that the quantum gravitational fluctuations in the vacuum get
modified by the passage of an energetic particle, inducing recoil effects
described by back reaction effects on the propagating particle ellis00 .
Although present technologies preclude any possibility to probe quantum
gravity effects, it has been suggested in Ref. amelino98  that Gamma-Ray
Bursts (GRBs) might offer the possibility to test the theories at Planck
energies. The idea is that the origin of GRBs at a cosmological distance and
their high energies may make them sensitive to the dispersion scales that are
comparable with the Planck scales amelino98 . In addition, the quantum
fluctuations of spacetime may have had relevant consequences during the early
Universe. In fact, the CPT-violating aspects of brane Universe models may
induce an asymmetry between particles and antiparticles, allowing to explain
the observed Baryon Asymmetry nickEPJC .

In this contribution, we investigate the foamy structure of the gravitational
background, referring in particular to the Ellis-Mavromatos-Nanopoulos-Volkov
(EMNV) model ellis00a , and its role on the formation of light elements during
the primordial phase of the Universe evolution (Big Bang Nucleosynthesis).
Big-Bang Nucleosynthesis (BBN) represents an important epoch during the
evolution of the Universe. During this period, the primordial light elements
formed leaving imprints on their abundance today. Thanks to the advancements
in measurements and theoretical predictions of the abundances of light
elements, BBN has become a powerful cosmological probe for testing the early
Universe. BBN has hence no trivial consequences on any physics scenario beyond
the Standard Models of particle physics and cosmology Capozziello:2017bxm ;
Barrow:2020kug ; Asimakis:2021yct . The latter may alter the course of the
events at that era with respect to the standard theories, and therefore such a
probe provides strong constraints.

The rest of the paper is structured as follows. In section 2, we present the
EMNV model and provide a formula that connects the baryon density parameter
with the quantum fluctuations mass scale. In section 3, we provide bounds on
the quantum fluctuations mass scale using today’s primordial abundances of
light elements which were produced in the BBN era. In section 4, we conclude
and briefly present our results.

##  II The EMNV model

The basic idea of the EMNV model is that the recoil effect of a $D$-brane
struck by particles (bosons ellis99 ; ellis99_1 ; ellis00  or fermions
ellis00a ), induces an energy dependence of the off-diagonal terms of the
background metric, $G_{0i}\sim u_{i}$, where $u_{i}\sim E/M_{s}\ll 1$ ($u_{i}$
is the average recoil velocity of the generic $D$-brane ellis00a  and $E$ is
the energy of the particle scattering off the $D$-brane, and $M_{s}$
characterizes the quantum fluctuations scale). The consequence of the off-
diagonal term in the metric tensor implies the breaking of the Lorentz
invariance ellis00a . For a $D$-dimensional spacetime, one has
$G_{ij}=\delta_{ij}$, $G_{00}=-1$, and $G_{0i}\sim u_{i\,\parallel}$,
$i,j=1,\ldots,D-1$ (here $u_{i\,\parallel}$ is the recoil (parallel) velocity
of the $D$-particle). Moreover, the metric induces a variation of the light
velocity $\delta c/c\sim-E/M_{s}$. The capture and splitting of the open
string and its interaction with the $D$-particle, and the recoil of the
latter, gives rise to a local effective spacetime metric distortion ellis99 ;
ellis99_1 ; Bernabeu:2006av

$ds^{2}=g_{\mu\nu}dx^{\mu}dx^{\nu}=(\eta_{\mu\nu}+G_{\mu\nu})dx^{\mu}dx^{\nu}~{}.$
(II.1)

The dispersion relation of a particle (neutrino) propagating on the deformed
isotropic spacetime reads
$g_{\mu\nu}p^{\mu}p^{\nu}=(\eta_{\mu\nu}+G_{\mu\nu})p^{\mu}p^{\nu}=-m^{2}\,\Rightarrow\,E^{2}-2E{\vec{p}}\cdot
u_{\parallel}-{\vec{p}}^{2}-m^{2}=0$, where $m$ is the mass of the particle.
Taking into consideration this on-shell condition and taking the average
$\ll\dots\gg$ over $D$-particle populations with the stochastic processes
($\ll u_{i\,\parallel}\gg=0$, $\ll
u_{i\,\parallel}u_{j\,\parallel}\gg=\sigma^{2}\delta_{ij}$), one gets the
average neutrino and anti-neutrino energies in the $D$-foam background

$\ll
E_{\nu,\overline{\nu}}\gg=\sqrt{p^{2}+m_{\nu}^{2}}\left(1+\frac{1}{2}\sigma^{2}\right)\mp\frac{1}{2}\frac{M_{s}}{g_{s}}\,\sigma^{2}~{}.$
(II.2)

Here it is assumed that the recoil-velocities fluctuation strengths are the
same for particle and antiparticle sectors (the asymmetric scenario has been
studied in Bernabeu:2006av ). As we can see, the local violation of Lorentz
symmetry (LV) induced by the recoil velocities of the $D$-particles, induced a
CPT violation too, since the dispersion relations between particles and
antiparticles are different, generating a matter-antimatter lepton asymmetry

$\ll
n-{\overline{n}}\gg=g_{d.o.f.}\int\frac{d^{3}p}{(2\pi)^{3}}\ll[f(E)-f(\overline{E})]\gg$
(II.3)

where $f(E,\mu)=\frac{1}{{\rm exp}[(E-\mu)/T]\,\pm\,1}$, $E^{2}={\bf
p}^{2}+m^{2}$, and $g_{d.o.f.}$ denotes the number of degrees of freedom of
relativistic neutrinos. Assuming that $\sigma^{2}$ is constant (independent of
space and of the (anti)neutrino energy), one can get $\Delta
n_{\nu}\simeq\frac{g_{d.o.f.}}{\pi^{2}}\,T^{3}\left(\frac{M_{s}\sigma^{2}}{g_{s}\,T}\right)\,>\,0$.
Notice that the CPT term, i.e., $-\frac{1}{2}\frac{M_{s}}{g_{s}}\sigma^{2}$,
in the dispersion relation of the neutrino comes with the right sign
(_“loss”_) guaranteeing the excess of particles over antiparticles. The
resulting lepton asymmetry reads

$\eta=\frac{\Delta
n_{\nu}}{n_{\gamma}}\sim\frac{315}{2\pi^{4}}\frac{\text{GeV}}{T}\left(\frac{M_{s}}{\text{GeV}}\,\frac{\sigma^{2}}{g_{s}}\,\right)~{}.$
(II.4)

Observations of the CMB radiation [1] , predictions of BBN [2]  (and the
absence of intense radiation from matter–antimatter annihilation [3] ),
implies that the observed baryon number asymmetry today is

$\eta=(6.04\pm 0.08)\times 10^{-10}\,.$ (II.5)

Such a value remains constant from early times till today. For later reasons,
one introduces the baryon density parameter $\eta_{10}$ defined as epjp52 ;
epjp53

$\eta_{10}\equiv 10^{10}\eta\equiv 10^{10}\frac{\Delta n_{\nu}}{n_{\gamma}}$
(II.6)

with $\eta_{10}$ to be determined. From (II.4) and (II.6) one gets

$\frac{M_{s}}{\text{GeV}}\frac{\sigma^{2}}{g_{s}}=10^{-13}\frac{2\pi^{4}}{315}\frac{T_{BBN}}{\text{MeV}}\,\eta_{10}$
(II.7)

where $T_{BBN}\sim 1$MeV is the temperature at which the BBN processes are
effective.

##  III Primordial light element $\\{{}^{4}He,D,Li\\}$

We will now derive the bound on the scale $M_{s}$ by analyzing the effects of
the primordial abundances of light elements, i.e., Deuterium ${}^{2}H$, Helium
${}^{4}He$, and Lithium ${}^{7}Li$, using the asymmetry given by (II.4). In
this analysis, the baryon-antibaryon asymmetry, here indicated with
$\eta_{10}$, plays a crucial role epjp52 ; epjp53 . Since we are interested in
deviations from the standard cosmological model, hereafter we shall assume
three generations of neutrinos so that we set $N_{\nu}=3$, which means $Z=1$
(corresponding to the standard cosmological model) in the equations below. We
follow the Refs. batt ; kavuk . The relevant processes are here recalled:

  * •

${}^{4}He$ abundance \- The production of Helium ${}^{4}He$ is generated by
the production of ${}^{2}H$ through a neutron and a proton. Consequently, the
formed Deuterium converts into ${}^{3}He$ and Tritium. The best fit of the
primordial ${}^{4}He$ abundance is epjp57 ; epjp58

$Y_{p}=0.2485\pm
0.0006+0.0016\left[\left(\eta_{10}-6\right)+100\left(Z-1\right)\right]$
(III.8)

The standard result of BBN for the ${}^{4}He$ fraction is recovered for $Z=1$
and $\eta_{10}=6$, so in General Relativity (GR) one gets
$(Y_{p})|_{GR}=0.2485\pm 0.0006$. However, observations of the Helium
${}^{4}He$ give the abundance $0.2449\pm 0.0040$ jcap2020 . So employing the
observational constraint and the Helium abundance given in (III.8) for $Z=1$,
we obtain

$0.2449\pm 0.0040=0.2485\pm 0.0006+0.0016\left(\eta_{10}-6\right)~{}.$ (III.9)

From the above equations, one infers the constraint

$5.65\lesssim\eta_{10}\lesssim 5.9~{}.$ (III.10)

  * •

${}^{2}H$ abundance \- Deuterium ${}^{2}H$ is produced by the reaction
$n+p\rightarrow{}^{2}H+\gamma$. The best fit gives the Deuterium abundance
epjp52

$y_{Dp}=2.6(1\pm 0.06)\left(\frac{6}{\eta_{10}-6(Z-1)}\right)^{1.6}~{}.$
(III.11)

The values $Z=1$ and $\eta_{10}=6$ yield the result in GR, thus the Deuterium
abundance will be $y_{Dp}|_{GR}=2.6\pm 0.16$. Equation (III.11) and the
observational constraint on deuterium abundance $y_{Dp}=2.55\pm 0.03$ jcap2020
give (for $Z=1$)

$2.88\pm 0.22=2.6(1\pm 0.06)\left(\frac{6}{\eta_{10}}\right)^{1.6}~{}.$
(III.12)

One then gets the constraint

$5.88626\lesssim\eta_{10}\lesssim 6.25264~{}.$ (III.13)

It is noteworthy that such a constraint partially overlaps the helium
abundance (III.10).

  * •

${}^{7}Li$ abundance \- The parameter $\eta_{10}$, defined in (II.6), although
successfully fits the abundances of $D$ and ${}^{4}He$, it does not fit the
observations of ${}^{7}Li$. This is referred in literature as the Lithium
problem theory ). The ratio of the expected value of ${}^{7}Li$ abundance in
GR and the observed one is in the range theory ; theory42

$\frac{Li|_{GR}}{Li|_{obs}}\in[2.4-4.3]~{}.$ (III.14)

The numerical best fit for ${}^{7}Li$ abundance is (for $Z=1$) epjp52

$y_{Li}=4.82(1\pm 0.1)\left[\frac{\eta_{10}-3(Z-1)}{6}\right]^{2}=4.82(1\pm
0.1)\left[\frac{\eta_{10}}{6}\right]^{2}~{}.$ (III.15)

Employing the observational constraint on Lithium abundance, i.e.,
$y_{Li}=1.6\pm 0.3$ jcap2020 , one gets the constraint

$3.28457\lesssim\eta_{10}\lesssim 3.59177~{}.$ (III.16)

It is evident that such range of values does not overlap with the constraints
on ${}^{2}H$ abundance, i.e., Eq. (III.13), and on ${}^{4}He$ abundance, i.e.,
Eq. (III.10).

The constraints derived for the three abundances are reported in Fig. 1. It is
obvious that the overlapping ranges of ${}^{2}H$ and ${}^{4}He$ correspond to
the value $\eta_{10}\sim 5.9$ (orange region). This value does not overlap
with the ${}^{7}Li$ range, which means that the Lithium problem cannot be
solved in the framework of the spacetime foam. However, this is not a
conclusive result since the eventual modifications of Einstein’s equations
have not been considered in the present paper, as well as the possibility that
the quantum fluctuation parameter $\sigma^{2}$ is not universal.

Inserting the overlapping value of $\eta_{10}$ into (II.7) for
$T_{BBN}\lesssim 1$MeV and using spacetime foam parameter $M_{s}/g_{s}\sim
M_{P}$ ($M_{P}\sim 10^{19}$GeV is the Planck mass) Nick2 , one obtains

$\frac{M_{s}}{g_{s}}\sigma^{2}\sim 3.6\times
10^{-13}\text{GeV}\quad\to\quad\sigma^{2}\lesssim 10^{-22}~{}.$ (III.17)

Therefore, we have inferred the upper bound on the dimensionless stochastic
variable $\sigma^{2}$, which expresses the fluctuations of the recoil velocity
of the $D$-branes.

Figure 1: In this figure we report the bounds for $\\{{}^{4}He$, $D,Li\\}$,
Eqs. (III.10), (III.13), and (III.16), respectively. The orange region is
obtained from the overlapping of (III.10) and (III.13). As we can see, the
Lithium region, given by (III.16), does not overlap, so the Lithium problem
cannot be solved or ameliorated by taking into account the spacetime foam
model.

##  IV Conclusions

The BBN era, which occurred during the hot and expanding early Universe, has
left an observable imprint in the abundance of primordial light elements.
Precision observations and high-accuracy predictions of these elements provide
an important test of the standard cosmological model (based on General
Relativity) and allow probing of non-standard cosmological and particle
physics scenarios. In this framework, we have used the BBN sensitivity to
obtain a bound on the dimensionless stochastic variable $\sigma^{2}$
expressing the fluctuations of D-branes recoil velocity. Results give
$\sigma^{2}\lesssim 10^{-22}$ for $M_{s}/g_{s}\sim M_{P}$. A follow-up of the
present work is to investigate physical scenarios related to spacetime foam
where the BBN constraints are properly taken into account, or consider the
general case in which the quantum fluctuation parameter $\sigma^{2}$ is not
universal nickEPJC .

###### Acknowledgements.

The authors would like to thank N. Mavromatos for useful correspondences and
fruitful comments. This work was supported by the Natural Sciences and
Engineering Research Council of Canada.

## References

  * (1) J. A. Wheeler, Relativity, Groups and Topology, Eds. B. S. DeWitt and C. M. DeWitt (Gordon and Breach, New York, 1964).
  * (2) S. W. Hawking, D. N. Page and C. N. Pope, Nucl. Phys. B 170, 283-306 (1980).
  * (3) S. W. Hawking, Commun. Math. Phys. 87, 395-415 (1982).
  * (4) J. R. Ellis, J. S. Hagelin, D. V. Nanopoulos and M. Srednicki, Nucl. Phys. B 241, 381 (1984).
  * (5) J. R. Ellis, N. E. Mavromatos and D. V. Nanopoulos, Phys. Lett. B 293, 37-48 (1992) [arXiv:hep-th/9207103 [hep-th]].
  * (6) L. J. Garay, Phys. Rev. D 58, 124015 (1998) [arXiv:gr-qc/9806047 [gr-qc]].
  * (7) L. J. Garay, Phys. Rev. Lett. 80, 2508-2511 (1998) [arXiv:gr-qc/9801024 [gr-qc]].
  * (8) J. R. Ellis, N. E. Mavromatos and D. V. Nanopoulos, Gen. Rel. Grav. 32, 127-144 (2000) [arXiv:gr-qc/9904068 [gr-qc]].
  * (9) J. R. Ellis, N. E. Mavromatos and D. V. Nanopoulos, Gen. Rel. Grav. 31, 1257-1262 (1999) [arXiv:gr-qc/9905048 [gr-qc]].
  * (10) G. Amelino-Camelia, J. R. Ellis, N. E. Mavromatos and D. V. Nanopoulos, Int. J. Mod. Phys. A 12, 607-624 (1997) [arXiv:hep-th/9605211 [hep-th]].
  * (11) R. Gambini and J. Pullin, Phys. Rev. D 59, 124021 (1999) [arXiv:gr-qc/9809038 [gr-qc]].
  * (12) H. W. Yu and L. H. Ford, Phys. Rev. D 60, 084023 (1999) [arXiv:gr-qc/9904082 [gr-qc]].
  * (13) J. R. Ellis, K. Farakos, N. E. Mavromatos, V. A. Mitsou and D. V. Nanopoulos, Astrophys. J. 535, 139-151 (2000) [arXiv:astro-ph/9907340 [astro-ph]].
  * (14) G. Amelino-Camelia, J. R. Ellis, N. E. Mavromatos, D. V. Nanopoulos and S. Sarkar, Nature 393, 763-765 (1998) [arXiv:astro-ph/9712103 [astro-ph]].
  * (15) N. E. Mavromatos, EPJ Web Conf. 70, 00083 (2014) [arXiv:1210.0211 [hep-ph]].
  * (16) J. R. Ellis, N. E. Mavromatos, D. V. Nanopoulos and G. Volkov, Gen. Rel. Grav. 32, 1777-1798 (2000) [arXiv:gr-qc/9911055 [gr-qc]].
  * (17) S. Capozziello, G. Lambiase and E. N. Saridakis, Eur. Phys. J. C 77, no.9, 576 (2017) [arXiv:1702.07952 [astro-ph.CO]].
  * (18) J. D. Barrow, S. Basilakos and E. N. Saridakis, Phys. Lett. B 815, 136134 (2021) [arXiv:2010.00986 [gr-qc]].
  * (19) P. Asimakis, S. Basilakos, N. E. Mavromatos and E. N. Saridakis, Phys. Rev. D 105, no.8, 084010 (2022) [arXiv:2112.10863 [gr-qc]].
  * (20) J. Bernabeu, N. E. Mavromatos and S. Sarkar, Phys. Rev. D 74, 045014 (2006) [arXiv:hep-th/0606137 [hep-th]].
  * (21) P. A. R. Ade et al. [Planck], Astron. Astrophys. 594, A13 (2016) [arXiv:1502.01589 [astro-ph.CO]].
  * (22) N. Aghanim et al. [Planck], Astron. Astrophys. 641, A6 (2020) [erratum: Astron. Astrophys. 652, C4 (2021)] [arXiv:1807.06209 [astro-ph.CO]].
  * (23) A. G. Cohen, A. De Rujula and S. L. Glashow, Astrophys. J. 495, 539-549 (1998) [arXiv:astro-ph/9707087 [astro-ph]].
  * (24) G. Steigman, Adv. High Energy Phys. 2012, 268321 (2012) [arXiv:1208.0032 [hep-ph]].
  * (25) V. Simha and G. Steigman, JCAP 06, 016 (2008) [arXiv:0803.3465 [astro-ph]].
  * (26) S. Bhattacharjee and P. K. Sahoo, Eur. Phys. J. Plus 135, no.4, 350 (2020) [arXiv:2004.04684 [physics.gen-ph]].
  * (27) N. Katırcı and M. Kavuk, Eur. Phys. J. Plus 129, 163 (2014) [arXiv:1302.4300 [gr-qc]].
  * (28) J. P. Kneller and G. Steigman, New J. Phys. 6, 117 (2004) [arXiv:astro-ph/0406320 [astro-ph]].
  * (29) G. Steigman, Ann. Rev. Nucl. Part. Sci. 57, 463-491 (2007) [arXiv:0712.1100 [astro-ph]].
  * (30) B. D. Fields, K. A. Olive, T. H. Yeh and C. Young, JCAP 03, 010 (2020) [erratum: JCAP 11, E02 (2020)] [arXiv:1912.01132 [astro-ph.CO]].
  * (31) S. Boran and E. O. Kahya, Adv. High Energy Phys. 2014, 282675 (2014) [arXiv:1310.6145 [astro-ph.CO]].
  * (32) B. D. Fields, Ann. Rev. Nucl. Part. Sci. 61, 47-68 (2011) [arXiv:1203.3551 [astro-ph.CO]].
  * (33) N. E. Mavromatos, J. Phys. Conf. Ser. 283, 012022 (2011) [arXiv:1010.5399 [gr-qc]].