# Integrating Edge-AI in Structural Health Monitoring domain ††thanks:
Citation: Authors. Title. Pages…. DOI:000000/11111.

Anoop Mishra
University of Nebraska
6001 Dodge Street
Omaha, Nebraska
USA - 68182
<EMAIL_ADDRESS>
Gopinath Gangisetti
University of Nebraska
6001 Dodge Street
Omaha, Nebraska
USA - 68182
<EMAIL_ADDRESS>
Deepak Khazanchi
University of Nebraska
6001 Dodge Street
Omaha, Nebraska
USA - 68182
<EMAIL_ADDRESS>

###### Abstract

Structural health monitoring (SHM) tasks like damage detection are crucial for
decision-making regarding maintenance and deterioration. For example, crack
detection in SHM is crucial for bridge maintenance as crack progression can
lead to structural instability. However, most AI/ML models in the literature
have low latency and late inference time issues while performing in real-time
environments. This study aims to explore the integration of edge-AI in SHM
domain for real-time bridge inspections. Based on edge-AI literature, its
capabilities will be valuable integration for a real-time decision support
system in SHM tasks such that real-time inferences can be performed on
physical sites. This study will utilize commercial edge-AI platforms, such as
Google Coral Dev Board or Kneron KL520, to develop and analyze the
effectiveness of edge-AI devices. Thus, this study proposes an edge AI
framework for the structural health monitoring domain. An edge-AI-compatible
deep learning model is developed to validate the framework to perform real-
time crack classification. The effectiveness of this model will be evaluated
based on its accuracy, the confusion matrix generated, and the inference time
observed in a real-time setting.

_K_ eywords Edge-AI $\cdot$ Neural networks $\cdot$ Quantization $\cdot$
Structural health monitoring $\cdot$ Cracks detection

##  1 Introduction

The increasing traffic loads and threat of structural fatigue make it crucial
to monitor the health condition of structural bridges. Structural Health
Monitoring (SHM) can play a key role in increasing the lifespan and
performance of bridges [1]. The optimal system for monitoring, managing, and
assessing the condition of bridges is required for performing tasks like
bridge maintenance and deterioration. Periodic and continuous monitoring via
bridge deck inspections is necessary for structural health monitoring (SHM)
[2, 3]. Advances in technology like wireless sensor networks and artificial
intelligence have allowed bridge structural health monitoring more effective.
In the past, AI approaches including machine learning, computer vision, and
robotics along with data mining and image processing techniques are utilized
to address the SHM challenges [4, 5, 6, 7]. Especially deep learning
approaches are broadly utilized in the past for detecting and segmenting
bridge components [8, 9, 10]. Results obtained through these computational
approaches have shown immense potential to support health monitoring tasks
such as crack detection, segmentation of bridge components, UAV inspection of
bridges, and damage detection for bridge structure [11, 4, 6, 7]. However,
real-time inferences in SHM, especially crack detection is challenging based
on several factors like a wide range of various complex backgrounds and crack-
like features.

Edge-AI allows a process for artificial intelligence inference and computation
on-device rather than on cloud servers or network connections. Edge-AI
optimizes the response time and accelerates AI computation when data is
generated and processed for inference on-device [12]. Zhou et al 2019 [12]
suggests that this ability of edge-AI platforms has advantages as follows-

  1. 1.

Increase security and privacy,

  2. 2.

Reduce need for data storage and bandwidth,

  3. 3.

Reduce latency,

  4. 4.

Increase stability

  5. 5.

Improves cost optimization for AI integration for dedicated tasks, and

  6. 6.

Improves real-time inference time

Figure 1: Proposed edge-AI framework in the structural health monitoring
domain

###  1.1 Research Goals and Proposed approach

In this research study, drawing from artificial intelligence (AI), neural
network process acceleration, and edge computing literature, the study aims to
investigate edge-AI integration in structural health monitoring tasks. The
objective is to develop a lightweight neural network model and to optimize
neural network response time performance in real time. To accomplish this, we
are utilizing Kneron KL520 platform which includes a neural processing unit
(NPU), an AI system-on-chip(SoC) hardware.

To address the inherent challenges for real-time inference an edge-AI
framework for SHM domain is proposed. This paper introduces a novel framework
to generate lightweight optimized models on the edge within the SHM domain.
Figure 1 describes the edge-AI-SHM framework. The framework design explains
that the neural network for edge-AI chips can be developed using an optimized
model that includes pruning, quantization, and weight clustering approach or
by on-device training where the transfer learning approach is used to fine-
tune the existing edge neural network model. Crack detection as an SHM task is
experimented on the Kneron KL520 platform to validate the proposed framework.
More details of the experiments can be found in section 2. In summary, the
technical contributions are as follows:

  1. 1.

Proposed a novel edge-AI framework for SHM domain.

  2. 2.

Developed and deployed the optimized CNN model for classifying cracks on image
data in a real-time setting

  3. 3.

Optimized the CNN inference time for identifying cracks from 3 seconds (mean)
to 20 milliseconds (mean)

This study will help researchers to practice all-on-device edge AI as a
technology for real-time applications and research purposes in the fields such
as robotics, smart surveillance, and automation in the domain of structural
health monitoring.

##  2 Methods

###  2.1 Dataset

The public crack dataset from Caglar et al. 2019 includes concrete building
crack images from METU campus buildings [13]. The dataset consists of two
class labels, i.e., “Positive” and “Negative”. Each class label contains 20000
images with a total of 40,000 images of cracks and non-cracks. The image
characteristics of the images describe that images contain 3 color channels
(RGB) with 227x227 dimensions. Figure 2 shows the sample positive cracks from
the dataset.

Figure 2: Sample images from positive class of the dataset from Caglar et al.
[13]

###  2.2 Kneron KL520

This study is using Kneron KL520 chip series to develop edge-AI based
optimized model. More details of Kneron KL520 can be found on this URL:
https://www.kneron.com/page/soc/. Based on [14], brief specifications of the
chip are as follows-

  1. 1.

Single-on-chip (SoC) design platform

  2. 2.

32MB SDRAM (16-bit LPDDR2-1066)

  3. 3.

Neural Processor Unit(NPU) for accelerating neural network process

  4. 4.

CPU: Two ARM Cortex-M4, one for system control and the other as a AI co-
process for NPU

  5. 5.

Maximum Frequency: 300 MHz

Although the device supports popular CNN models like VGG16, VGG19, MobileNet,
etc., but it has support for a limited set of operators to design a CNN
architecture. This restricts designing the model architecture specific to this
very device. All the details related to the operators can be found on the
website (https://www.kneron.com/page/soc/).

###  2.3 Neural network model architecture

This study aims to develop a cracks image classification model based on
Convolutional neural network (CNN) architecture. The model architecture
consists of an input layer of 224x224x3 dimension, 6 convolutions with max-
pooling layers, 2 dense layers, and an output layer with a Softmax activating
function. The development stack for this research study includes Python3 with
AI frameworks like Tensorflow lite, Keras, and ONNX for embedded model
conversion.

###  2.4 Experiments: Overview

####  2.4.1 Training:

The model training is designed based on training and validation sets, with a
split of 80-20 based on 40000 images. The training is iterated for 20 epochs.
The results of the training and validation accuracy are both very high, at
99.54% and 99.52% respectively. This means that the model is very accurate in
classifying the images of the training and validation data. Testing the
inference for the same 40000 images on simulation of the Kneron KL520 chip
resulted in 92.4% accuracy. The testing inference is discussed in section
2.4.3. Figure 3 shows the training performance of the developed model.

Figure 3: Training performance of the main model

####  2.4.2 Optimized model generation for Chip compability

To generate an optimized model and test it on the Kneron chip, there are two
major steps:

  1. 1.

Make sure the operators used in the original model are supported by the device
and convert the original model to ONNX file format for further use.

  2. 2.

Testing the model performance using simulation and getting a view of the
results before deploying the model to the device.

As mentioned in section 2.2, the edge device supports limited operators. The
softmax activation function is one of the operators not supported by the
Kneron NPU. Thus the softmax layer had to be removed before saving the model
for device format conversion.

ONNX conversion: ONNX is a file format for storing deep learning models. It is
useful for edge computing because it allows models to be deployed to devices
that may not have access to a full deep learning framework. ONNX also supports
a number of different hardware architectures, so models can be deployed to a
variety of devices.

Quantization: It is a process of transforming the number of bits that
represent a number. In deep learning, quantization is often used to reduce the
size and complexity of models, making them faster and more efficient. In this
study, the general model was transformed into an 8-bit model.

Before generating an optimized model that is supported by the device, the
following steps are required:

  1. 1.

Create an optimized onnx file by converting the model from several platforms.
Examine the onnx model for verifying operator compatibility. The onnx model is
then put to the test, and the output is compared to the original.

  2. 2.

Create a fixed-point file using the post-quantization approach on the main
(floating-point) model.

  3. 3.

Create a binary file in the nef format (npu executable format) format.

The flowchart in figure 5 describes the workflow for optimized model
development.

####  2.4.3 Kneron KL520 inference on test sample

For testing in a real-time setting, the host device (mainframe system with
camera capability) captures the image and sends the image to know for
inference. Before the image is sent for inference, the image is pre-processed
on the host device aligning with the input layer. Also, since the output layer
has a softmax activation function removed before NEF format conversion, the
post-processing of the raw output generated from KL520 is also done on the
host device. The testing sample includes a total of 355 images out of which
255 are of cracks class and 100 are of non-cracks. This test sample includes
images from the main dataset and also includes 100 images (both positive and
negative) collected manually for real-time testing. The testing accuracy
performance is impacted by the sample collected manually, as they belong to
different data distributions. They differ in cracks characteristics like
length and width, and also in background texture.

Testing performance:  The overall accuracy of the testing results is 92.4%,
which can be counted as imposing. The average inference time per image on the
device was 20 milliseconds including pre-processing and post-processing on the
host device. The Kneron KL520 chip provides an efficient AI computing
performance of 0.35 TOPS per watt. The confusion matrix can be seen in figure
4. The testing accuracy can be improved by utilizing on-device training by
retraining the model using transfer learning approach as proposed in the edge-
AI framework in figure 1.

Figure 4: Confusion matrix for testing sample

##  3 Conclusion

This study proposed a novel edge-AI framework for the tasks in the structural
health monitoring(SHM) domain to perform real-time inference on physical
sites. Following the proposed framework, a post-quantization optimized model
is developed having CNN architecture. The testing accuracy for the crack image
classification is 92.4%. The inference time is optimized from an average of 3
seconds to 20 milliseconds per image.

##  4 Acknowledgement

This research project belongs to the College of Information, Science and
Technology, University of Nebraska at Omaha.

## References

  * [1] Vahid Reza Gharehbaghi, Hashem Kalbkhani, Ehsan Noroozinejad Farsangi, TY Yang, Andy Nguyen, Seyedali Mirjalili, and Christian Málaga-Chuquitaype.  A novel approach for deterioration and damage identification in building structures based on stockwell-transform and deep convolutional neural network.  Journal of Structural Integrity and Maintenance, 7(2):136–150, 2022\.
  * [2] Zhenqing Liu, Yiwen Cao, Yize Wang, and Wei Wang.  Computer vision-based concrete crack detection using u-net fully convolutional networks.  Automation in Construction, 104:129–139, 2019.
  * [3] Yuan-Sen Yang, Chung-Ming Yang, and Chang-Wei Huang.  Thin crack observation in a reinforced concrete bridge pier test using image processing and analysis.  Advances in Engineering Software, 83:99–108, 2015.
  * [4] Arathi Reghukumar and L Jani Anbarasi.  Crack detection in concrete structures using image processing and deep learning.  In Advances in Electrical and Computer Technologies, pages 211–219. Springer, 2021.
  * [5] Majdi Flah, Itzel Nunez, Wassim Ben Chaabene, and Moncef L Nehdi.  Machine learning algorithms in civil structural health monitoring: a systematic review.  Archives of computational methods in engineering, 28(4):2621–2643, 2021.
  * [6] Aiping Guo, Ajuan Jiang, Jie Lin, and Xiaoxiao Li.  Data mining algorithms for bridge health monitoring: Kohonen clustering and lstm prediction approaches.  The Journal of Supercomputing, 76(2):932–947, 2020.
  * [7] Robin A Gandhi, Deepak Khazanchi, Daniel Linzell, Brian Ricks, and Chungwook Sim.  The hidden crisis: Developing smart big data pipelines to address grand challenges of bridge infrastructure health in the united states.  In Proceedings of the… International ISCRAM Conference, 2018.
  * [8] Xiaoning Cui, Qicai Wang, Jinpeng Dai, Yanjin Xue, and Yun Duan.  Intelligent crack detection based on attention mechanism in convolution neural network.  Advances in Structural Engineering, 24(9):1859–1868, 2021.
  * [9] Chenjun Tan, Nasim Uddin, and Yahya M Mohammed.  Deep learning-based crack detection using mask r-cnn technique.  In 9 th International Conference on Structural Health Monitoring of Intelligent Infrastructure, 2019.
  * [10] Qiaoning Yang, Si Jiang, Juan Chen, and Weiguo Lin.  Crack detection based on resnet with spatial attention.  Computers and Concrete, An International Journal, 26(5):411–420, 2020.
  * [11] Zhiming Zhang and Chao Sun.  Structural damage identification via physics-guided machine learning: a methodology integrating pattern recognition with finite element model updating.  Structural Health Monitoring, 20(4):1675–1688, 2021.
  * [12] Zhi Zhou, Xu Chen, En Li, Liekang Zeng, Ke Luo, and Junshan Zhang.  Edge intelligence: Paving the last mile of artificial intelligence with edge computing.  Proceedings of the IEEE, 107(8):1738–1762, 2019.
  * [13] FO Çağlar and R Özgenel.  Concrete crack images for classification.  Mendeley Data, 2, 2019.
  * [14] Kneron.  https://www.kneron.com/, 2023.

Figure 5: Flowchart for developing an optimized model to inference on Kneron
KL520


# Bounds on the density of smooth lattice coverings

Or Ordentlich  School of Computer Science and Engineering, Hebrew University
,  Oded Regev  Courant Institute of Mathematical Sciences, New York University
and  Barak Weiss  School of Mathematical Sciences, Tel Aviv University

(Date: August 31, 2024)

###### Abstract.

Let ${\mathcal{K}}$ be a convex body in ${\mathbb{R}}^{n}$, let $L$ be a
lattice with unit covolume, and let $\eta>0$. We say that ${\mathcal{K}}$ and
$L$ form an $\eta$-smooth cover if each point $x\in{\mathbb{R}}^{n}$ is
covered by $(1\pm\eta){\mathrm{vol}}({\mathcal{K}})$ translates of
${\mathcal{K}}$ by $L$. We prove that for any positive $\sigma$ and $\eta$,
asymptotically as $n\to\infty,$ for any ${\mathcal{K}}$ of volume
$n^{3+\sigma}$, one can find a lattice $L$ for which ${\mathcal{K}},L$ form an
$\eta$-smooth cover. Moreover, this property is satisfied with high
probability for a lattice chosen randomly, according to the Haar-Siegel
measure on the space of lattices. Similar results hold for random construction
A lattices, albeit with a worse power law, provided that the ratio between the
covering and packing radii of ${\mathbb{Z}}^{n}$ with respect to
${\mathcal{K}}$ is at most polynomial in $n$. Our proofs rely on a recent
breakthrough of Dhar and Dvir on the discrete Kakeya problem.

##  1\. Introduction

Let ${\mathrm{Conv}_{n}}$ denote the set of bounded convex subsets of
${\mathbb{R}}^{n}$ with nonempty interior. For a lattice
$L\subset\mathbb{R}^{n}$, convex set ${\mathcal{K}}\in{\mathrm{Conv}_{n}}$,
and a point $x\in\mathbb{R}^{n}$ we denote

$N(L,{\mathcal{K}},x){\,\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\,}\left|L\cap({\mathcal{K}}+x)\right|=\left|\left\\{y\in
L\ :\ x\in y-{\mathcal{K}}\right\\}\right|.$ (1)

The expectation of $N(L,{\mathcal{K}},x)$ when $x$ is drawn uniformly from a
fundamental domain for $L$ is
${\mathrm{vol}}({\mathcal{K}})/\mathrm{covol}(L)$; thus if we draw $x$
uniformly in a ball $B(0,T)$ with respect to some norm, the expectation of
$N(L,{\mathcal{K}},x)$ approaches
${\mathrm{vol}}({\mathcal{K}})/\mathrm{covol}(L)$, in the limit as
$T\to\infty$. Furthermore, we have that
$\frac{N(L,\alpha{\mathcal{K}},x)}{{\mathrm{vol}}(\alpha{\mathcal{K}})/\mathrm{covol}(L)}$
tends to $1$ as the dilation factor $\alpha$ grows, where the convergence is
uniform in $x$. It is therefore natural to ask, given
${\mathcal{K}}\in{\mathrm{Conv}_{n}}$ and a lattice
$L\subset{\mathbb{R}}^{n}$, whether the fraction
$\frac{N(L,{\mathcal{K}},x)}{{\mathrm{vol}}({\mathcal{K}})/\mathrm{covol}(L)}$
is nearly constant on ${\mathbb{R}}^{n}$. To that end we define the following
quantity:

######  Definition 1.1.

The _covering smoothness_ of a lattice $L\subset{\mathbb{R}}^{n}$ with respect
to a convex body ${\mathcal{K}}\in{\mathrm{Conv}_{n}}$ is defined as

$\displaystyle{\eta}({\mathcal{K}},L){\,\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\,}\sup_{x\in{\mathbb{R}}^{n}}\left|\frac{N(L,{\mathcal{K}},x)}{{\mathrm{vol}}({\mathcal{K}})/\mathrm{covol}(L)}-1\right|.$

Note that ${\eta}({\mathcal{K}},L)<1$ immediately implies that
$L+{\mathcal{K}}={\mathbb{R}}^{n}$. In this case the pair $(L,{\mathcal{K}})$
is said to be a covering. (The reverse statement is not true — there may be
points $x$ that are covered an exceptionally large number of times by
translates of ${\mathcal{K}}$.) As in the abstract, if
$\eta({\mathcal{K}},L)<\eta$ we say that the covering given by ${\mathcal{K}}$
and $L$ is $\eta$-smooth.

Let $\mu_{n}$ denote the Haar-Siegel measure; that is, the unique probability
measure on the space of lattices in ${\mathbb{R}}^{n}$ of unit covolume, which
is invariant under volume preserving linear transformations. Our main result
is that for every ${\mathcal{K}}\in{\mathrm{Conv}_{n}}$ whose volume is
polynomial in $n$, and for most lattices in ${\mathbb{R}}^{n}$, the covering
smoothness is small.

######  Theorem 1.2.

Let $n>25$, and let ${\mathcal{K}}\in{\mathrm{Conv}_{n}}$. Let
$\delta,\varepsilon\in(0,1)$, and assume ${\mathrm{vol}}({\mathcal{K}})\geq
c_{1}\left(\frac{1}{\varepsilon\delta}\right)^{6.5}n^{3}$, where
$c_{1}=2^{66}$. Then, for $L\sim\mu_{n}$ we have

$\displaystyle\Pr\left({\eta}({\mathcal{K}},L)\geq\varepsilon\right)<\delta.$
(2)

In particular, for any positive $\varepsilon,\sigma$,

$\displaystyle\sup_{{\mathcal{K}}\in{\mathrm{Conv}_{n}},{\mathrm{vol}}({\mathcal{K}})\geq
n^{3+\sigma}}\Pr\left(\eta({\mathcal{K}},L)\geq\varepsilon\right)\longrightarrow_{n\to\infty}0.$

We did not attempt to optimize the multiplicative constant $c_{1}$ in this
result, or similar constants $c_{i}$ in the sequel.

Theorem 1.2 and the remaining statements below might find applications in
computer science. Specifically, in lattice-based cryptography, smoothing a
lattice is a key idea used to hide secret information from an adversary
[MicciancioR07]. Typically, one considers smoothing by a Gaussian
distribution. However, for some applications it might be advantageous to
smooth using a convex body, since sampling from a convex body like a cube can
be more efficient. It should be noted that in many cryptographic applications,
closeness in $L_{1}$ is sufficient, and such $L_{1}$-smoothness results (in
fact, even $L_{2}$-smoothness) are often much easier to prove (see, e.g.,
[Debris23]); yet there are many cases where closeness in $L_{\infty}$ (as in
our results) leads to tighter results [BaiLRSSS18].

It is instructive to compare Theorem 1.2 with our previous work [ORW21] on
lattice coverings. Recall that for a lattice $L\subset{\mathbb{R}}^{n}$ of
covolume one, the covering density $\Theta({\mathcal{K}},L)$ is the minimal
volume of a dilate $\alpha{\mathcal{K}}$ such that $(L,\alpha{\mathcal{K}})$
is a covering. One of the results of [ORW21] is that

$\sup_{{\mathcal{K}}\in{\mathrm{Conv}_{n}}}\inf_{L\text{ of covolume
}1}\Theta({\mathcal{K}},L)$ (3)

grows at most quadratically in $n$ (prior to [ORW21] the best known bound, due
to Rogers [Rogers_bound], was superpolynomial). In fact, it was shown that for
any $\delta>0$, any $\sigma>0$, any large enough $n$ and any
${\mathcal{K}}\in{\mathrm{Conv}_{n}},$ if ${\mathrm{vol}}({\mathcal{K}})\geq
n^{2+\sigma}$ then the $\mu_{n}$-probability that $(L,{\mathcal{K}})$ is a
covering is at least $1-\delta.$ Fixing $\varepsilon\in(0,1)$, we deduce
easily from Theorem 1.2 the slightly weaker statement, in which $2+\sigma$ is
replaced with $3+\sigma$. That is, when
${\mathrm{vol}}({\mathcal{K}})>n^{2+\sigma}$, we know from [ORW21] that a
random $L$ gives a covering, and from Theorem 1.2 we know that when
${\mathrm{vol}}({\mathcal{K}})>n^{3+\sigma}$ a random $L$ gives an
$\varepsilon$-smooth covering. On the other hand, [CoxeterFewRogers] shows
that for ${\mathcal{K}}$ taken as the Euclidean ball and any lattice $L$ of
covolume $1$, $\eta({\mathcal{K}},L)\geq 1$ (and moreover, $(L,{\mathcal{K}})$
is not a covering) unless ${\mathrm{vol}}({\mathcal{K}})=\Omega(n)$.

While we intuitively expect covering to become smoother as we scale up
${\mathcal{K}}$, it turns out that in general
$\alpha\mapsto\eta(\alpha{\mathcal{K}},L)$ is not monotonically non-
increasing. To see this, take $L={\mathbb{Z}}^{n}$ and
${\mathcal{K}}=\left[0,1\right)^{n}$. Then
$\eta({\mathcal{K}},{\mathbb{Z}}^{n})=0$ yet for small $\varepsilon>0$,
$\eta((1+\varepsilon){\mathcal{K}},{\mathbb{Z}}^{n})=(2/(1+\varepsilon))^{n}-1$.
It is therefore natural to further define the following quantity for a lattice
$L\subset{\mathbb{R}}^{n}$ and ${\mathcal{K}}\in{\mathrm{Conv}_{n}}$,

$\displaystyle{\Phi}_{{\mathcal{K}},L}(\varepsilon){\,\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\,}\sup\left\\{\frac{{\mathrm{vol}}(\alpha{\mathcal{K}})}{\mathrm{covol}(L)}\
:\ \alpha>0\text{ satisfies
}{\eta}(\alpha{\mathcal{K}},L)>\varepsilon\right\\}.$

In particular, for a lattice $L\subset{\mathbb{R}}^{n}$ of unit covolume, we
have that ${\eta}(\alpha{\mathcal{K}},L)\leq\varepsilon$ for _all_ dilates
$\alpha{\mathcal{K}}$ of volume exceeding
${\Phi}_{{\mathcal{K}},L}(\varepsilon)$. We prove the following theorem.

######  Theorem 1.3.

Let $n>25$, and let ${\mathcal{K}}\in{\mathrm{Conv}_{n}}$. Let
$\delta,\varepsilon\in(0,1)$, and $c_{2}=2^{112}$. Then, for $L\sim\mu_{n}$ we
have

$\displaystyle\Pr\left({\Phi}_{{\mathcal{K}},L}(\varepsilon)\geq
c_{2}\left(\frac{1}{\varepsilon^{2}\delta}\right)^{6.5}n^{3}\right)<\delta.$
(4)

###  1.1. Construction A lattices

In many applications in electrical engineering and computer science, integer
lattices known as _construction A lattices_ are of interest [ConwaySloane,
loeliger97]. For a prime $p$ let ${\mathbb{F}}_{p}$ denote the field with $p$
elements. For $r\in\\{1,\ldots,n\\}$, let
${\mathrm{Gr}}_{n,r}({\mathbb{F}}_{p})$ denote the collection of subspaces of
dimension $r$ in ${\mathbb{F}}_{p}^{n}$, or equivalently, the rank-$r$
additive subgroups of ${\mathbb{F}}_{p}^{n}$. We can identify
${\mathbb{F}}_{p}$ with the residues $\\{0,\ldots,p-1\\}$, and thus identify
${\mathbb{F}}_{p}^{n}$ with the quotient ${\mathbb{Z}}^{n}/p{\mathbb{Z}}^{n}$.
We have a natural _reduction mod $p$_ homomorphism
$\pi_{p}:{\mathbb{Z}}^{n}\to{\mathbb{F}}_{p}^{n}$, which sends each coordinate
of $x\in{\mathbb{Z}}^{n}$ to its class modulo $p$. Any element
$S\in{\mathrm{Gr}}_{n,r}({\mathbb{F}}_{p})$ gives rise to a sub-lattice
$\pi_{p}^{-1}(S)\subset{\mathbb{Z}}^{n}$, which contains $p{\mathbb{Z}}^{n}$
as a subgroup of index $p^{r}$, and with $\pi_{p}^{-1}(S)/p{\mathbb{Z}}^{n}$
isomorphic as an abelian group to
$S\cong\prod_{1}^{r}{\mathbb{Z}}/p{\mathbb{Z}}$. The ensemble of lattices
obtained by drawing
$S\sim\mathrm{Uniform}({\mathrm{Gr}}_{n,r}({\mathbb{F}}_{p}))$ and setting
$L=\frac{1}{p}\cdot\pi_{p}^{-1}(S)$ is called the _random $(p,r)$ construction
A ensemble_111Some authors define the $(p,r)$ random construction $A$ ensemble
slightly differently, taking
$S^{\prime}=\mathrm{span}_{{\mathbb{F}}_{p}}(v_{1},\ldots,v_{r})$ and
$v_{1},\ldots,v_{r}\stackrel{{\scriptstyle
i.i.d.}}{{\sim}}\mathrm{Uniform}({\mathbb{F}}_{p}^{n})$ and
$L=\frac{1}{p}\cdot\pi_{p}^{-1}(S^{\prime})$. Since
$\Pr(S^{\prime}\notin{\mathrm{Gr}}_{n,r}({\mathbb{F}}_{p}))\leq p^{r-n}$ and,
moreover, $S^{\prime}$ is conditionally uniform on
${\mathrm{Gr}}_{n,r}({\mathbb{F}}_{p})$ under the event
$S^{\prime}\in{\mathrm{Gr}}_{n,r}({\mathbb{F}}_{p})$, we have that the total
variation distance between the distributions corresponding to the two
definitions is at most $p^{r-n}$. and such lattices are called _$(p,r)$
construction A lattices_.

Theorem 1.2 holds for any ${\mathcal{K}}\in{\mathrm{Conv}_{n}}$, with uniform
constants. However, if ${\mathcal{K}}$ is such that
$N({\mathcal{K}},{\mathbb{Z}}^{n},0)$ is large (for example
${\mathcal{K}}=\prod_{1}^{n-1}[\varepsilon^{-1},\varepsilon^{-1}]\times[-\varepsilon^{n-1},\varepsilon^{n-1}]$
for $\varepsilon$ small), it will not be smoothed by applying construction A,
unless $p$ and $r$ are large (depending on ${\mathcal{K}}$). Thus our results
for construction A lattices depend on ${\mathcal{K}}$. The dependence arises
via the ratio between the covering radius and packing radius of
${\mathcal{K}}$ with respect to ${\mathbb{Z}}^{n}$. Namely, for a convex body
${\mathcal{K}}\in{\mathrm{Conv}_{n}}$ and a lattice $L\subset{\mathbb{R}}^{n}$
we denote by $\mathrm{r}_{\text{cov},{\mathcal{K}}}(L)$ the infimum of
$\alpha$ for which $(L,\alpha{\mathcal{K}})$ is a covering, and by
$\mathrm{r}_{\text{pack},{\mathcal{K}}}(L)$ the supremum of $\alpha$ for which
$(L,\alpha{\mathcal{K}})$ is a packing, i.e., the translates
$\\{\ell+\alpha{\mathcal{K}}:\ell\in L\\}$ are disjoint. We denote by

$\displaystyle\rho_{{\mathcal{K}}}(L){\,\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\,}\frac{\mathrm{r}_{\text{cov},{\mathcal{K}}}(L)}{\mathrm{r}_{\text{pack},{\mathcal{K}}}(L)}$
(5)

the ratio between the covering and the packing radius. We show that for
${\mathcal{K}}\in{\mathrm{Conv}_{n}}$ for which both
${\mathrm{vol}}({\mathcal{K}})$ and $\rho_{\mathcal{K}}({\mathbb{Z}}^{n})$ are
polynomial in $n$, for a typical construction A lattice with adequately tuned
$p$, $r$, scaled to have unit covolume, the covering smoothness is small.

######  Theorem 1.4.

Let $n>25$, and let ${\mathcal{K}}\in{\mathrm{Conv}_{n}}$ and $b>0$ satisfy

$\displaystyle 0\leq b\leq\frac{n}{2\log_{2}n}\ \ \text{ and }\ \
\rho_{\mathcal{K}}({\mathbb{Z}}^{n})<n^{b}.$ (6)

Let $\delta,\varepsilon\in(0,1)$, and assume
${\mathrm{vol}}({\mathcal{K}})\geq
c_{3}\left(\frac{1}{\varepsilon\delta}\right)^{6}n^{3(1+2b)}$, where
$c_{3}=e\cdot 2^{33}$. Let $p$ be a prime number satisfying

$\displaystyle\frac{1024}{(\varepsilon\delta)^{2}}n^{1+2b}\leq
p\leq\frac{2048}{(\varepsilon\delta)^{2}}n^{1+2b},$ (7)

and $r=3+\left\lceil\frac{n}{\log p}\left(b\log n+\log 3\right)\right\rceil$.
Then, if $L$ is drawn from the $(p,r)$ random construction A ensemble (so that
$\mathrm{covol}(p^{r/n}L)=1$), we have

$\displaystyle\Pr\left({\eta}({\mathcal{K}},p^{r/n}L)\geq\varepsilon\right)<\delta\;.$

An important special case is the Euclidean ball, namely
${\mathcal{K}}=\mathcal{B}_{n}=\\{x\in{\mathbb{R}}^{n}\ :\ \|x\|_{2}\leq
1\\}$. It is well known (and easy to see) that

$\displaystyle\mathrm{r}_{\text{pack},\mathcal{B}_{n}}({\mathbb{Z}}^{n})$
$\displaystyle=\frac{1}{2}\ \ \ \ \text{ and }\ \
\mathrm{r}_{\text{cov},\mathcal{B}_{n}}({\mathbb{Z}}^{n})=\frac{\sqrt{n}}{2},$

which gives

$\displaystyle\rho_{\mathcal{B}_{n}}({\mathbb{Z}}^{n})=n^{1/2}.$

Thus, the following is an immediate consequence of Theorem 1.4.

######  Corollary 1.5.

Let $n>25$, and let $\delta,\varepsilon\in(0,1)$, and for $\alpha>0$, assume

${\mathrm{vol}}(\alpha\mathcal{B}_{n})\geq
c_{3}\left(\frac{1}{\varepsilon\delta}\right)^{6}n^{6},$

where $c_{3}=e\cdot 2^{33}$. Let $p$ be a prime number satisfying

$\displaystyle\frac{1024}{(\varepsilon\delta)^{2}}n^{2}\leq
p\leq\frac{2048}{(\varepsilon\delta)^{2}}n^{2},$

and $r=3+\left\lceil\frac{n}{\log p}\left(\frac{1}{2}\log
9n\right)\right\rceil$. Then if $L$ is drawn from the $(p,r)$ random
construction A ensemble (so that $\mathrm{covol}(p^{r/n}L)=1$), we have

$\displaystyle\Pr\left({\eta}(\alpha\mathcal{B}_{n},p^{r/n}L)\geq\varepsilon\right)<\delta\;.$

Similarly to the case where $L$ is drawn at random according to the
distribution $\mu_{n}$, we can also show that for $L$ drawn from the $(p,r)$
random construction A ensemble, for ${\mathcal{K}}\in{\mathrm{Conv}_{n}}$ with
$\rho_{{\mathcal{K}}}({\mathbb{Z}}^{n})$ polynomial in $n$, we have that with
high probability ${\Phi}_{{\mathcal{K}},L}(\varepsilon)$ is also polynomial in
$n$, provided that $p$ and $r$ are chosen adequately.

######  Theorem 1.6.

Let $n>25$, and let ${\mathcal{K}}\in{\mathrm{Conv}_{n}}$ and $b>0$ satisfy
(6). Let $\delta,\varepsilon\in(0,1)$, and $c_{4}=e\cdot 2^{57}$. Let $p$ be a
prime number satisfying

$\displaystyle\frac{2^{18}}{(\varepsilon^{2}\delta)^{2}}n^{3+2b}\leq
p\leq\frac{2^{19}}{(\varepsilon^{2}\delta)^{2}}n^{3+2b},$ (8)

and $r=3+\left\lceil\frac{n}{\log p}\left(b\log n+\log 3\right)\right\rceil$.
Then, if $L$ is drawn from the $(p,r)$ random construction A ensemble, we have

$\displaystyle\Pr\left({\Phi}_{{\mathcal{K}},L}(\varepsilon)>c_{4}\left(\frac{1}{\varepsilon^{2}\delta}\right)^{6}n^{9+6b}\right)\leq\delta.$
(9)

###  1.2. Non-lattice smooth coverings

If one relaxes the requirement that $L$ is a lattice, it is slightly more
complicated to define smooth covers, but much easier to construct them.

Let $L\subset{\mathbb{R}}^{n}$ be a discrete set (not necessarily a lattice).
We continue to use the notation $N(L,{\mathcal{K}},x)$ defined in (1). Let
$B(0,T)$ denote the ball of radius $T$ around the origin with respect to the
Euclidean norm, and define the asymptotic upper density of $L$ by

$D(L){\,\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\,}\limsup_{T\to\infty}\frac{|B(0,T)\cap
L|}{{\mathrm{vol}}(B(0,T))}.$ (10)

If the limit in (10) exists we will say that $L$ has an asymptotic density.
Note that lattices have an asymptotic density given by
$D(L)=\mathrm{covol}(L)^{-1}$. Now for ${\mathcal{K}}\in{\mathrm{Conv}_{n}}$,
and $L$ as above, we set

$\displaystyle{\eta}({\mathcal{K}},L){\,\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\,}\sup_{x\in{\mathbb{R}}^{n}}\left|\frac{N(L,{\mathcal{K}},x)}{{\mathrm{vol}}({\mathcal{K}})\,D(L)}-1\right|.$

With this notation we have:

######  Theorem 1.7.

For any $0<\varepsilon<1$, $n\geq 20$, and any
${\mathcal{K}}\in{\mathrm{Conv}_{n}}$ there is a discrete set
$L\subset{\mathbb{R}}^{n}$ which has an asymptotic density, satisfying

${\mathrm{vol}}({\mathcal{K}})D(L)\leq\frac{14}{\varepsilon^{2}}\left(n\log
n+n\log\frac{1280}{\varepsilon}+2\right)\ \ \text{ and }\ \
\eta({\mathcal{K}},L)<\varepsilon.$ (11)

We remark that the set $L$ constructed in the proof of Theorem 1.7 is
_periodic_ , i.e., consists of finitely many translates of a lattice in
${\mathbb{R}}^{n}$. We also remark that Theorem 1.7 can be derived by
modifying the proof of Erdős and Rogers [ErdosRogers], who proved a closely
related statement. For completeness, we include a proof in Section 3.5 that
follows the proof structure of our main theorem.

###  1.3. Acknowledgements

The authors are grateful to Bo’az Klartag for suggesting the question of
seeking smooth lattice coverings, to Manik Dhar and Ze’ev Dvir for sharing an
early draft of their result, and to Chris Peikert for useful comments. The
first author is supported by ISF 1641/21, the second author is supported by a
Simons Investigator Award from the Simons Foundation, and the third author is
supported by ISF 2019/19 and ISF-NSFC 3739/21.

##  2\. Techniques and Notation

The main results of this paper follow from the somewhat technical Theorem 3.4.
This result is derived in turn from a new result of Dhar and Dvir (Theorem
2.2), which is a crucial input to this paper. In this section we introduce
notations, give a brief overview of our approach, and state Theorem 2.2.

For a lattice $L\subset{\mathbb{R}}^{n}$ let
${\mathbb{T}}_{L}{\,\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\,}{\mathbb{R}}^{n}/L$
be the quotient torus, let $m_{L}$ be the Haar probability measure on
${\mathbb{T}}_{L}$, and let $\pi_{L}:{\mathbb{R}}^{n}\to{\mathbb{T}}_{L}$ be
the quotient map. Let $v_{1},\ldots,v_{n}$ be the generators of $L$ given by
the columns of $g$ so that the parallellepiped

${\mathcal{P}}_{L}=\left\\{\sum a_{i}v_{i}:\forall i,\ 0\leq a_{i}<1\right\\}$

is a fundamental domain for ${\mathbb{R}}^{n}/L$. Define the discrete ‘net’

${\mathcal{P}^{\mathrm{(disc)}}_{L}}{\,\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\,}\left\\{\sum
a_{i}v_{i}\in{\mathcal{P}}_{L}:a_{i}\in\left\\{0,\frac{1}{p},\ldots,1-\frac{1}{p}\right\\}\right\\}$
(12)

and set

$\frac{L}{p}{\,\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\,}\frac{1}{p}\cdot
L.$

Then the elements of ${\mathcal{P}^{\mathrm{(disc)}}_{L}}$ are coset
representatives for the inclusion $L\subset\frac{L}{p},$ and there is an
isomorphism (as abelian groups)
${\mathcal{P}^{\mathrm{(disc)}}_{L}}\cong{\mathbb{F}}_{p}^{n}.$

Next, we introduce a well-studied technique for randomly choosing lattices.
Given $L=g{\mathbb{Z}}^{n}$, where $g$ is an invertible $n\times n$ matrix,
and given $S\in{\mathrm{Gr}}_{n,r}({\mathbb{F}}_{p})$, we define the super-
lattice $L(S)\supset L$ as

$\displaystyle
L(S){\,\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\,}\frac{1}{p}\cdot
g\pi_{p}^{-1}(S).$ (13)

Notice that the scaled-up version $p^{r/n}\cdot L(S)$ of $L(S)$ is of the same
covolume as $L$. The assignment

$L\ \mapsto\
\left\\{p^{r/n}L(S):S\in{\mathrm{Gr}}_{n,r}({\mathbb{F}}_{p})\right\\}$ (14)

is a special case of the so-called Hecke correspondence. Note that the
individual lattice $L(S)$ also depends on the initial choice of $g$ for which
$L=g{\mathbb{Z}}^{n},$ but the collection on the right-hand side of (14) does
not. Also note that Construction A lattices are a special case of this
construction (up to scaling), starting with $L={\mathbb{Z}}^{n}$.

Given a convex body ${\mathcal{K}}$, our goal is to find a lattice for which
the covering smoothness is small. We will choose this lattice to be $L(S)$ for
a randomly chosen $S\in{\mathrm{Gr}}_{n,r}({\mathbb{F}}_{p})$ for some $r$ and
$p$, and where $L$ is a lattice for which we have a reasonable bound on
$\rho_{{\mathcal{K}}}(L)$. For instance, in the proof of Theorem 1.2, we will
take $L$ to be a randomly chosen lattice according to the Haar-Siegel measure
$\mu_{n}$, which has a small $\rho_{{\mathcal{K}}}$ (Proposition 3.6);
importantly, by [ORW21]*Proposition 2.1, $L(S)$ is also distributed according
to $\mu_{n}$ (up to scaling), as needed for the conclusion of Theorem 1.2.

By rescaling ${\mathcal{K}}$ we may assume that $L$ forms a packing with
respect to ${\mathcal{K}}$ and a covering with respect to the dilate
$\rho_{{\mathcal{K}}}(L){\mathcal{K}}$. Recall that our goal is to show that
the function

$\mathbb{T}_{L(S)}\to{\mathbb{N}},\ \ \ \ x\mapsto|(x+L(S))\cap{\mathcal{K}}|$
(15)

is uniformly close to a constant function. By a discretization procedure (see
Proposition 3.1), it will be sufficient to show that the restriction of the
function in (15) to $\mathcal{P}^{(\mathrm{disc})}_{L}$ is close to a constant
function. This uses the fact that $L$ is a covering with respect to
$\rho_{{\mathcal{K}}}(L){\mathcal{K}}$ and assumes that $p$ is chosen
sufficiently large with respect to $\rho_{{\mathcal{K}}}(L)$.

The final step in the proof is to reduce the problem to an analogous problem
in ${\mathbb{F}}_{p}^{n}$. Denoting by $A\subset{\mathbb{F}}_{p}^{n}$ the set
$\pi_{L}\big{(}\frac{L}{p}\cap{\mathcal{K}}\big{)}$ viewed as a subset of
${\mathbb{F}}_{p}^{n}$, we have that for any
$x\in\mathcal{P}^{(\mathrm{disc})}_{L}$,

$\displaystyle|(x+L(S))\cap{\mathcal{K}}|=\Big{|}\pi_{L}\Big{(}(x+L(S))\cap{\mathcal{K}}\Big{)}\Big{|}=|(x+S)\cap
A|\;,$ (16)

where the first equality uses the assumption that $L$ forms a packing with
respect to ${\mathcal{K}}$ (and so $\pi_{L}$ is injective on ${\mathcal{K}}$)
and on the right-hand side we think of $x$ as being in ${\mathbb{F}}_{p}^{n}$.
Thus our problem reduces to showing that a randomly chosen $S$ leads to a
smooth covering of ${\mathbb{F}}_{p}^{n}$ by the $S$-translates of $A$. This
is precisely the problem addressed by Dhar and Dvir.

To state their result we need the following discrete analogue of the covering
smoothness:

######  Definition 2.1.

Let $p$ be a prime number. The smoothness of a set
$S\subset{\mathbb{F}}_{p}^{n}$ with respect to a set
$A\subset{\mathbb{F}}_{p}^{n}$ is defined as

$\displaystyle{\eta_{{\mathbb{F}}_{p}}}(A,S){\,\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\,}\sup_{x\in{\mathbb{F}}_{p}^{n}}\left|\frac{|(x+S)\cap
A|}{|S|\cdot|A|\cdot p^{-n}}-1\right|.$

With this notation we have:222The precise statement given in [dd22]*Theorem
III.3 deals only with the smallest possible choice of
$r=3+n-\lfloor\log_{p}|A|\rfloor=\lceil 3+n-\log_{p}|A|\rceil$. However, any
larger choice of $r$ also works, since, as noted in [dd22], if a subspace $S$
is $\tau$-shift-balanced, and $S^{\prime}$ is a subspace containing $S$, then
$S^{\prime}$ is also $\tau$-shift-balanced.

######  Theorem 2.2 (Dhar and Dvir, Theorem III.3 in [dd22]).

Let $n\geq 5$, let $\delta,\tau\in(0,1)$ and let $p$ be a prime number
satisfying $p>64n/(\tau\delta)^{2}$. Let $A\subset{\mathbb{F}}_{p}^{n}$ and
let $4\leq r\leq n$ be an integer satisfying $r>3+n-\log_{p}|A|$. Then for
$S\sim\mathrm{Uniform}\left({\mathrm{Gr}}_{n,r}({\mathbb{F}}_{p})\right)$ we
have

$\displaystyle\Pr({\eta_{{\mathbb{F}}_{p}}}(A,S)>\tau)<\delta.$ (17)

To summarize, by (16) and the discretization argument, if the conclusion of
Theorem 2.2 holds with $A=\pi_{L}\big{(}\frac{L}{p}\cap{\mathcal{K}}\big{)}$,
then we obtain the desired result, namely, that with high probability, $L(S)$
is a smooth covering for ${\mathcal{K}}$ of density

$\frac{{\mathrm{vol}}({\mathcal{K}})}{\mathrm{covol}(L(S))}=p^{r}\frac{{\mathrm{vol}}({\mathcal{K}})}{\mathrm{covol}(L)}\;.$

Noting that $|A|\approx
p^{n}\frac{{\mathrm{vol}}({\mathcal{K}})}{\mathrm{covol}(L)}$ (Lemma 3.3) and
taking $r=3+n-\log_{p}|A|$ (ignoring here the technicality of $r$ having to be
an integer) we get a density of about $p^{3}$. Finally, we need to choose $p$
to satisfy the conditions of Theorem 2.2 and be large enough compared to
$\rho_{{\mathcal{K}}}(L)$ for the discretization argument to work.

We end this section by noting that improvements to Theorem 2.2 will yield
improvements in our results. We make this precise in Remark 3.7.

##  3\. Proofs of Main Results for Lattices

###  3.1. Discretization

For subsets $A,B\subset{\mathbb{R}}^{n}$ and $c\in{\mathbb{R}}$ we denote as
usual

$A+B{\,\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\,}\\{a+b:a\in A,b\in B\\},\
\ cA{\,\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\,}\\{ca:a\in A\\}.$

######  Proposition 3.1.

Let $L^{\prime}\subset\mathbb{R}^{n}$ be a discrete subset of
${\mathbb{R}}^{n}$ such that $L^{\prime}=-L^{\prime},$ let
${\mathcal{K}}\in{\mathrm{Conv}_{n}}$, and assume $0<\rho<1$ is such that
$L^{\prime}+\rho{\mathcal{K}}=\mathbb{R}^{n}$. Then for any
$x\in{\mathbb{R}}^{n}$ there are $y_{1},y_{2}\in L^{\prime}$ such that

$(1-\rho){\mathcal{K}}+y_{1}\subset{\mathcal{K}}+x\subset(1+\rho){\mathcal{K}}+y_{2}.$
(18)

###### Proof.

The convexity of ${\mathcal{K}}$ implies that for any positive $\alpha$ and
$\beta$ we have

$\displaystyle\alpha{\mathcal{K}}+\beta{\mathcal{K}}=(\alpha+\beta)\left\\{\frac{\alpha}{\alpha+\beta}k_{1}+\frac{\beta}{\alpha+\beta}k_{2}:k_{1},k_{2}\in{\mathcal{K}}\right\\}=(\alpha+\beta){\mathcal{K}}.$
(19)

For the containment on the right-hand side of (18), since
$L^{\prime}+\rho{\mathcal{K}}=\mathbb{R}^{n}$, for any $x\in\mathbb{R}^{n}$
there is $y_{2}\in L^{\prime}$ such that $x\in y_{2}+\rho{\mathcal{K}}$. Thus
if $y\in{\mathcal{K}}+x$ then
$y\in{\mathcal{K}}+\rho{\mathcal{K}}+y_{2}=(1+\rho){\mathcal{K}}+y_{2}.$

For the other containment, since
${\mathbb{R}}^{n}=-{\mathbb{R}}^{n}=-(L^{\prime}+\rho{\mathcal{K}})=L^{\prime}-\rho{\mathcal{K}}$,
there is $y_{1}\in L^{\prime}$ such that $x\in y_{1}-\rho{\mathcal{K}},$ and
thus $y_{1}\in x+\rho{\mathcal{K}}$. Now if $y\in(1-\rho){\mathcal{K}}+y_{1}$
then $y\in(1-\rho){\mathcal{K}}+\rho{\mathcal{K}}+x={\mathcal{K}}+x.$ ∎

As an immediate corollary we see that if $L^{\prime},\,{\mathcal{K}}$ and
$\rho$ satisfy the conditions of Proposition 3.1 and
$L\subset{\mathbb{R}}^{k}$ is a discrete subset, then:

  1. (1)

$\forall x\in\mathbb{R}^{n}\ \exists x^{\prime}\in L^{\prime}$ such that
$N(L,{\mathcal{K}},x)\leq N(L,(1+\rho){\mathcal{K}},x^{\prime})$;

  2. (2)

$\forall x\in\mathbb{R}^{n}\ \exists x^{\prime}\in L^{\prime}$ such that
$N(L,{\mathcal{K}},x)\geq N(L,(1-\rho){\mathcal{K}},x^{\prime})$.

Consequently, we have:

######  Lemma 3.2.

Let $L^{\prime},{\mathcal{K}}$ and $\rho$ satisfy the conditions of
Proposition 3.1 and let $L\subset\mathbb{R}^{n}$ be a discrete subset. Then:

  1. (1)

$\max_{x\in\mathbb{R}^{n}}N(L,{\mathcal{K}},x)\leq\max_{x^{\prime}\in
L^{\prime}}N(L,(1+\rho){\mathcal{K}},x^{\prime})$;

  2. (2)

$\min_{x\in\mathbb{R}^{n}}N(L,{\mathcal{K}},x)\geq\min_{x^{\prime}\in
L^{\prime}}N(L,(1-\rho){\mathcal{K}},x^{\prime})$.

The following standard lemma will be useful. We give the proof for lack of a
suitable reference.

######  Lemma 3.3.

Let $L\subset{\mathbb{R}}^{n}$ be a lattice and
${\mathcal{D}}\in{\mathrm{Conv}_{n}}$, and assume that
$L+\beta{\mathcal{D}}={\mathbb{R}}^{n}$ for some $\beta\in(0,1)$. Then

$\displaystyle(1-\beta)^{n}\frac{{\mathrm{vol}}({\mathcal{D}})}{\mathrm{covol}(L)}\leq|L\cap{\mathcal{D}}|\leq(1+\beta)^{n}\frac{{\mathrm{vol}}({\mathcal{D}})}{\mathrm{covol}(L)}.$
(20)

###### Proof.

Let
$N_{{\mathcal{D}}}{\,\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\,}L\cap{\mathcal{D}},$
and let $\mathcal{V}$ be a fundamental domain for $L$ contained in
$\beta{\mathcal{D}}$; that is, a measurable set such that for each
$x\in{\mathbb{R}}^{n}$ there is exactly one $\ell\in L$ for which
$x\in\ell+\mathcal{V}$. Such a fundamental domain exists since
$L+\beta{\mathcal{D}}={\mathbb{R}}^{n}$. Define the sets

$\displaystyle\mathcal{S}_{+}$
$\displaystyle{\,\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\,}N_{{\mathcal{D}}}+\mathcal{V}$
$\displaystyle\mathcal{S}_{-}$
$\displaystyle{\,\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\,}N_{{\mathcal{D}}}+(-\mathcal{V}).$

We have that
${\mathrm{vol}}(\mathcal{S}_{+})={\mathrm{vol}}(\mathcal{S}_{-})=|N_{{\mathcal{D}}}|\mathrm{covol}(L)$.
Thus, to establish (20), it suffices to show that

$\displaystyle\mathcal{S}_{+}$ $\displaystyle\subseteq(1+\beta){\mathcal{D}}$
$\displaystyle\mathcal{S}_{-}$ $\displaystyle\supseteq(1-\beta){\mathcal{D}}.$

The inclusion $\mathcal{S}_{+}\subseteq(1+\beta){\mathcal{D}}$ follows from
$N_{{\mathcal{D}}}\subset{\mathcal{D}}$,
$\mathcal{V}\subseteq\beta{\mathcal{D}}$ and the convexity of ${\mathcal{D}}$,
using (19). To see that $(1-\beta){\mathcal{D}}\subseteq\mathcal{S}_{-}$,
since $-\mathcal{V}$ is also a fundamental domain for $L$, for any
$x\in(1-\beta){\mathcal{D}}$ there is $y\in L$ such that $x\in y-\mathcal{V}$.
Thus, $y\in
x+\mathcal{V}\subset(1-\beta){\mathcal{D}}+\beta{\mathcal{D}}={\mathcal{D}}$,
and consequently $y\in N_{{\mathcal{D}}}$. ∎

###  3.2. From packing to smooth covering

Our analysis of $\eta({\mathcal{K}},L(S))$ (the covering smoothness of a
lattice, Definition 1.1) relies on the analysis of
$\eta_{{\mathbb{F}}_{p}}(A,S)$ (the analogous discrete smoothness, Definition
2.1), where $A$ is a discrete analogue of the projection of ${\mathcal{K}}$
modulo $L$, and $S$ is a randomly chosen subspace of
${\mathbb{F}}_{p}^{n}\cong{\mathcal{P}^{\mathrm{(disc)}}_{L}}$ of dimension
$r$, where $r$ will be carefully chosen.

We now derive our main technical statement from Theorem 2.2.

######  Theorem 3.4.

Let $n\geq 5$, let $\delta,\tau\in(0,1)$ and let $p$ be a prime number
satisfying $p>64n/(\tau\delta)^{2}$. Let $L\subset{\mathbb{R}}^{n}$ be a
lattice and let ${\mathcal{K}}\in{\mathrm{Conv}_{n}}$, and assume that there
is some real number $1<c<\frac{p}{2n}$ such that
$\big{(}L,\big{(}1+\frac{c}{p}\big{)}{\mathcal{K}}\big{)}$ is a packing and
$(L,c{\mathcal{K}})$ is a covering. Let $4\leq r\leq n$ be an integer
satisfying

$\displaystyle
r>3+\log_{p}\frac{\mathrm{covol}(L)}{{\mathrm{vol}}({\mathcal{K}})}+3c\,\frac{n}{p\log
p}\,,$ (21)

and let
$S\sim\mathrm{Uniform}\left({\mathrm{Gr}}_{n,r}({\mathbb{F}}_{p})\right)$.
Then

$\displaystyle\Pr\left({\eta}({\mathcal{K}},L(S))\geq\tau+8c\,\frac{n}{p}\right)<2\delta.$
(22)

###### Proof.

Set $\rho{\,\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\,}\frac{c}{p}$, so that
$\rho\in\left(0,\frac{1}{2n}\right)$ and $(\frac{L}{p},\rho{\mathcal{K}})$ is
a covering. Set
${\mathcal{D}}{\,\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\,}(1+\rho){\mathcal{K}}$
and
$\beta{\,\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\,}\frac{\rho}{1+\rho}$, so
that $\beta{\mathcal{D}}=\rho{\mathcal{K}}$ and we can apply the right-hand
side of (20) to obtain

$\displaystyle\left|\frac{L}{p}\cap(1+\rho){\mathcal{K}}\right|\leq(1+\beta)^{n}\cdot\frac{{\mathrm{vol}}({\mathcal{D}})}{\mathrm{covol}(\frac{L}{p})}=(1+2\rho)^{n}\frac{{\mathrm{vol}}({\mathcal{K}})}{\mathrm{covol}(L)}p^{n}.$
(23)

Similarly, by setting
${\mathcal{D}}{\,\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\,}(1-\rho){\mathcal{K}}$
and
$\beta{\,\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\,}\frac{\rho}{1-\rho}$, we
have

$\displaystyle(1-2\rho)^{n}\frac{{\mathrm{vol}}({\mathcal{K}})}{\mathrm{covol}(L)}p^{n}\leq\left|\frac{L}{p}\cap(1-\rho){\mathcal{K}}\right|.$
(24)

Write $L=g{\mathbb{Z}}^{n}$ and for any
$S\in{\mathrm{Gr}}_{n,r}({\mathbb{F}}_{p})$, define $L(S)$ by (13) and define
${\mathcal{P}^{\mathrm{(disc)}}_{L}}$ by (12), where the $v_{i}$ are the
columns of $g$. Denote by $A_{0}$ (respectively, $A_{1}$) the set of all
points in ${\mathcal{P}^{\mathrm{(disc)}}_{L}}$ covered by
$L+(1-\rho){\mathcal{K}}$ (respectively, $L+(1+\rho){\mathcal{K}}$), viewed as
elements of ${\mathbb{F}}_{p}^{n}$. Since $L$ forms a packing with respect to
$(1+\rho){\mathcal{K}}$ (and also with respect to $(1-\rho){\mathcal{K}}$),
the restriction of the projection $\pi_{L}:{\mathbb{R}}^{n}\to\mathbb{T}_{L}$
to $(1+\rho){\mathcal{K}}$ (and thus to $(1-\rho){\mathcal{K}}$) is injective.
Thus, by (23) and (24) we have

$\displaystyle(1-2\rho)^{n}\frac{{\mathrm{vol}}({\mathcal{K}})}{\mathrm{covol}(L)}p^{n}\leq|A_{i}|\leq(1+2\rho)^{n}\frac{{\mathrm{vol}}({\mathcal{K}})}{\mathrm{covol}(L)}p^{n},\
\ \ i=0,1,$ (25)

and each point in $A_{0}$ (or $A_{1}$) is covered exactly once.

For any $x\in{\mathcal{P}^{\mathrm{(disc)}}_{L}}$ we have that

$\displaystyle N(L(S),(1-\rho){\mathcal{K}},x)$ $\displaystyle=|(x+S)\cap
A_{0}|,$ $\displaystyle N(L(S),(1+\rho){\mathcal{K}},x)$
$\displaystyle=|(x+S)\cap A_{1}|,$

where, with some abuse of notation, on the left-hand side we treat $x$ as a
vector in ${\mathbb{R}}^{n}$ and on the right-hand side as an element of
${\mathbb{F}}_{p}^{n}\cong{\mathcal{P}^{\mathrm{(disc)}}_{L}}$. Let

$\displaystyle E_{0}$
$\displaystyle{\,\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\,}\left\\{S\in{\mathrm{Gr}}_{n,r}({\mathbb{F}}_{p})\
:\ {\eta_{{\mathbb{F}}_{p}}}(A_{0},S)>\tau\right\\}$ (26) $\displaystyle
E_{1}$
$\displaystyle{\,\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\,}\left\\{S\in{\mathrm{Gr}}_{n,r}({\mathbb{F}}_{p})\
:\ {\eta_{{\mathbb{F}}_{p}}}(A_{1},S)>\tau\right\\},$ (27)

and $E=E_{0}\cup E_{1}$. For all $S\in E^{c}$ and
$x\in{\mathcal{P}^{\mathrm{(disc)}}_{L}}$ we have

$\displaystyle N\left(L(S),(1-\rho){\mathcal{K}},x\right)$
$\displaystyle\geq(1-\tau)|S|\cdot|A_{0}|\cdot p^{-n}$
$\displaystyle\geq(1-\tau)\frac{|S|\cdot(1-2\rho)^{n}{\mathrm{vol}}({\mathcal{K}})}{\mathrm{covol}(L)}$
$\displaystyle=(1-\tau)(1-2\rho)^{n}\frac{{\mathrm{vol}}({\mathcal{K}})}{\mathrm{covol}(L(S))},$

and

$\displaystyle N(L(S),(1+\rho){\mathcal{K}},x)$
$\displaystyle\leq(1+\tau)|S|\cdot|A_{1}|\cdot p^{-n}$
$\displaystyle\leq(1+\tau)\frac{|S|\cdot(1+2\rho)^{n}{\mathrm{vol}}({\mathcal{K}})}{\mathrm{covol}(L)}$
$\displaystyle=(1+\tau)(1+2\rho)^{n}\frac{{\mathrm{vol}}({\mathcal{K}})}{\mathrm{covol}(L(S))}.$

Let $L^{\prime}=\frac{1}{p}L=L+{\mathcal{P}^{\mathrm{(disc)}}_{L}}$. By
assumption, $(L^{\prime},\rho{\mathcal{K}})$ is a covering. Thus, by part (2)
of Lemma 3.2 we have that for all $S\in E^{c}$,

$\displaystyle\min_{x\in\mathbb{R}^{n}}N(L(S),{\mathcal{K}},x)$
$\displaystyle\geq\min_{x^{\prime}\in
L^{\prime}}N\left(L(S),\left(1-\rho\right){\mathcal{K}},x^{\prime}\right)$
$\displaystyle=\min_{x^{\prime}\in{\mathcal{P}^{\mathrm{(disc)}}_{L}}}N(L(S),\left(1-\rho\right){\mathcal{K}},x^{\prime})$
$\displaystyle\geq(1-\tau)(1-2\rho)^{n}\frac{{\mathrm{vol}}({\mathcal{K}})}{\mathrm{covol}(L(S))},$
(28)

and

$\displaystyle\max_{x\in\mathbb{R}^{n}}N(L(S),{\mathcal{K}},x)$
$\displaystyle\leq\max_{x^{\prime}\in
L^{\prime}}N\left(L(S),\left(1+\rho\right){\mathcal{K}},x^{\prime}\right)$
$\displaystyle=\max_{x^{\prime}\in{\mathcal{P}^{\mathrm{(disc)}}_{L}}}N\left(L(S),\left(1+\rho\right){\mathcal{K}},x^{\prime}\right)$
$\displaystyle\leq(1+\tau)(1+2\rho)^{n}\frac{{\mathrm{vol}}({\mathcal{K}})}{\mathrm{covol}(L(S))}.$
(29)

Combining (28) and (29), we see that for any $S\in E^{c}$ we have

$\displaystyle{\eta}({\mathcal{K}},L(S))$
$\displaystyle=\sup_{x\in{\mathbb{R}}^{n}}\left|\frac{N(L(S),{\mathcal{K}},x)}{{\mathrm{vol}}({\mathcal{K}})/\mathrm{covol}(L(S))}-1\right|$
$\displaystyle\leq\max\left\\{1-(1-\tau)(1-2\rho)^{n},(1+\tau)(1+2\rho)^{n}-1\right\\}$
$\displaystyle\leq\max\left\\{\tau+(1-\tau)2\rho n,\tau+(1+\tau)4\rho
n\right\\}$ (30) $\displaystyle<\tau+8\rho n,$

where in (30) we have used the basic bounds (for $0<2\rho<1/n$)

$\displaystyle 1-(1-2\rho)^{n}$ $\displaystyle<2n\rho,$ (31)
$\displaystyle(1+2\rho)^{n}-1$ $\displaystyle<4n\rho.$

Thus, we have shown that

$\displaystyle{\eta}({\mathcal{K}},L(S))<\tau+8\rho n,\leavevmode\nobreak\
\leavevmode\nobreak\ \forall S\in E^{c}.$ (32)

Using our assumption on $r$ in (21) and the lower bound in (25), we have that
for $i=0,1$,

$\displaystyle r$
$\displaystyle>3+\log_{p}\frac{\mathrm{covol}(L)}{{\mathrm{vol}}({\mathcal{K}})}+\frac{3\rho
n}{\log p}$ $\displaystyle\geq
3+\log_{p}\left(\frac{p^{n}}{|A_{i}|}(1-2\rho)^{n}\right)+\frac{3\rho n}{\log
p}$ $\displaystyle=3+n-\log_{p}|A_{i}|+n\log_{p}(1-2\rho)+\frac{3\rho n}{\log
p}$ $\displaystyle\geq 3+n-\log_{p}|A_{i}|\;.$

Here, we have used the inequality

$-\log_{p}(1-2\rho)=\log_{p}\left(1+\frac{2\rho}{1-2\rho}\right)\leq\frac{1}{(1-2\rho)\log
p}\cdot 2\rho<\frac{3\rho}{\log p},$

where the last inequality follows from $\rho<1/2n$ and $n\geq 5$. Thus, we may
invoke Theorem 2.2 to obtain

$\displaystyle\Pr(S\in E_{i})<\delta,\ \ i=0,1,$

and therefore, by the union bound,

$\displaystyle\Pr(S\in E)<2\delta,$

establishing our claim. ∎

In the sequel we will use the following convenient consequence of Theorem 3.4.

######  Corollary 3.5.

Let $n>25$, $L\subset{\mathbb{R}}^{n}$ be a lattice with
$\mathrm{covol}(L)=1$, and $\delta,\tau\in(0,1)$. Also let
${\mathcal{K}}\in{\mathrm{Conv}_{n}}$ satisfy
$\rho_{{\mathcal{K}}}(L)\leq\bar{\rho}$ for some
$1\leq\bar{\rho}<\left(\frac{2}{\delta}\right)^{\frac{n}{2}}$ and
${\mathrm{vol}}({\mathcal{K}})>c_{5}\bar{\rho}^{6}\left(\frac{1}{\tau\delta}\right)^{6}n^{3}$,
where $c_{5}=e\cdot\left(128\right)^{3}$. Then, for any prime number $p$
satisfying

$\displaystyle\max\left\\{\frac{64\bar{\rho}^{2}n}{(\tau\delta)^{2}},\left((2.5)^{-n}\cdot{\mathrm{vol}}({\mathcal{K}})\right)^{1/3}\right\\}<p<(e^{-1}\cdot{\mathrm{vol}}({\mathcal{K}}))^{1/3},$
(33)

denoting $r=3+\left\lceil\frac{n\log 3\bar{\rho}}{\log p}\right\rceil$, we
have that for
$S\sim\mathrm{Uniform}\left({\mathrm{Gr}}_{n,r}({\mathbb{F}}_{p})\right)$ (so
that $\mathrm{covol}(p^{r/n}L(S))=1$),

$\displaystyle\Pr\left({\eta}({\mathcal{K}},p^{r/n}L(S))\geq
2\tau\right)<2\delta.$ (34)

We remark that the statement is not vacuous, i.e., there exists a prime number
$p$ satisfying (33). To see this, note that

$\displaystyle\frac{(e^{-1}\cdot{\mathrm{vol}}({\mathcal{K}}))^{1/3}}{\max\left\\{\frac{64\bar{\rho}^{2}n}{(\tau\delta)^{2}},((2.5)^{-n}\cdot{\mathrm{vol}}({\mathcal{K}}))^{1/3}\right\\}}$
$\displaystyle=$
$\displaystyle\min\left\\{\frac{(e^{-1}\cdot{\mathrm{vol}}({\mathcal{K}}))^{1/3}}{\frac{64\bar{\rho}^{2}n}{(\tau\delta)^{2}}},\frac{(e^{-1}\cdot{\mathrm{vol}}({\mathcal{K}}))^{1/3}}{((2.5)^{-n}\cdot{\mathrm{vol}}({\mathcal{K}}))^{1/3}}\right\\}\geq
2,$

and therefore, by Bertrand’s postulate, there must exist a prime number
satisfying (33). Recalling that
$p>\frac{64\bar{\rho}^{2}n}{(\tau\delta)^{2}}>(3\bar{\rho})^{2}$, it also
holds that $r<n$ since

$\displaystyle\frac{n\log 3\bar{\rho}}{\log p}\leq\frac{n\log
3\bar{\rho}}{2\log 3\bar{\rho}}=\frac{n}{2}.$

###### Proof of Corollary 3.5.

We show that with the parameters above, the conditions of Theorem 3.4 hold for
the lattice $p^{r/n}L$ with $c=3p^{\frac{1}{n}}\bar{\rho}^{2}$. To that end,
first note that
$p>\frac{64\bar{\rho}^{2}n}{(\tau\delta)^{2}}\geq\frac{64n}{(\tau\delta)^{2}}$
by definition. Furthermore, we have that

$\displaystyle\frac{8cn}{p}$
$\displaystyle=24\bar{\rho}^{2}p^{-(1-\frac{1}{n})}n$ $\displaystyle\leq
24\bar{\rho}^{2}\left(\frac{64\bar{\rho}^{2}n}{(\tau\delta)^{2}}\right)^{-(1-\frac{1}{n})}n$
$\displaystyle=\frac{24\bar{\rho}^{\frac{2}{n}}n^{1/n}}{64^{1-1/n}}(\tau\delta)^{2(1-\frac{1}{n})}$
$\displaystyle<\frac{\bar{\rho}^{\frac{2}{n}}}{2}(\tau\delta)^{2(1-\frac{1}{n})}$
$\displaystyle<\frac{\left(\bar{\rho}\delta^{\frac{n}{2}}\right)^{\frac{2}{n}}}{2}\tau$
$\displaystyle<\tau,$ (35)

and in particular, this implies that $c<\frac{p}{2n}$. Next we lower bound the
packing radius as

$\displaystyle\mathrm{r}_{\text{pack},{\mathcal{K}}}(p^{\frac{r}{n}}L)$
$\displaystyle=p^{\frac{r}{n}}\,\mathrm{r}_{\text{pack},{\mathcal{K}}}(L)\geq
p^{\frac{3}{n}}3\bar{\rho}\mathrm{r}_{\text{pack},{\mathcal{K}}}(L)\geq
3p^{\frac{3}{n}}\mathrm{r}_{\text{cov},{\mathcal{K}}}(L)$ $\displaystyle\geq
3p^{\frac{3}{n}}\left(\frac{1}{{\mathrm{vol}}({\mathcal{K}})}\right)^{\frac{1}{n}}=3\left(\frac{p^{3}}{{\mathrm{vol}}({\mathcal{K}})}\right)^{\frac{1}{n}}>\frac{3}{2.5}\stackrel{{\scriptstyle\eqref{eq:8cnbbound}}}{{>}}1+\frac{c}{p},$
(36)

and upper bound the covering radius as

$\displaystyle\mathrm{r}_{\text{cov},{\mathcal{K}}}(p^{\frac{r}{n}}L)$
$\displaystyle=p^{\frac{r}{n}}\,\mathrm{r}_{\text{cov},{\mathcal{K}}}(L)\leq
3p^{\frac{4}{n}}\mathrm{r}_{\text{cov},{\mathcal{K}}}(L)\bar{\rho}\leq
3p^{\frac{4}{n}}\bar{\rho}^{2}\mathrm{r}_{\text{pack},{\mathcal{K}}}(L)$
$\displaystyle\leq
3p^{\frac{4}{n}}\bar{\rho}^{2}\left(\frac{1}{{\mathrm{vol}}({\mathcal{K}})}\right)^{\frac{1}{n}}=3p^{\frac{1}{n}}\bar{\rho}^{2}\left(\frac{p^{3}}{{\mathrm{vol}}({\mathcal{K}})}\right)^{\frac{1}{n}}\leq
3p^{\frac{1}{n}}\bar{\rho}^{2}e^{-\frac{1}{n}}<c.$ (37)

Finally, we have that

$\displaystyle r$ $\displaystyle=\log_{p}\mathrm{covol}(p^{r/n}L)$
$\displaystyle=\log_{p}\frac{\mathrm{covol}(p^{r/n}L)}{{\mathrm{vol}}({\mathcal{K}})}+\log_{p}{\mathrm{vol}}({\mathcal{K}})$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:primelimits}}}{{\geq}}\log_{p}\frac{\mathrm{covol}(p^{r/n}L)}{{\mathrm{vol}}({\mathcal{K}})}+3+\log_{p}(e)$
$\displaystyle>3+\log_{p}\frac{\mathrm{covol}(p^{r/n}L)}{{\mathrm{vol}}({\mathcal{K}})}+3c\,\frac{n}{p\log
p},$

where we have used the fact that $\frac{3cn}{p}<1$, due to (35), in the last
inequality. Therefore, the conditions of Theorem 3.4 apply to the lattice
$p^{r/n}L$ and the convex body ${\mathcal{K}}$, with
$c=3p^{\frac{1}{n}}\bar{\rho}^{2}$. Thus, for
$S\sim\mathrm{Uniform}\left({\mathrm{Gr}}_{n,r}({\mathbb{F}}_{p})\right)$, we
have that

$\displaystyle\Pr\left({\eta}({\mathcal{K}},p^{r/n}L(S))\geq\tau+8\frac{cn}{p}\right)<2\delta.$

The statement in (34) follows since $8\frac{cn}{p}<\tau$ by (35). ∎

To prove Theorem 1.2, we will also need the following auxiliary statement,
proved in §3.3. Recall that $\mu_{n}$ denotes the Haar-Siegel probability
measure.

######  Proposition 3.6.

For $L\sim\mu_{n}$, any convex body ${\mathcal{K}}\in{\mathrm{Conv}_{n}}$, and
any $\alpha>0$,

$\displaystyle\Pr(\rho_{{\mathcal{K}}}(L)\geq
2\cdot\alpha^{2})<3\cdot\left(\frac{2}{\alpha}\right)^{n}.$

###### Proof of Theorem 1.2 (assuming Proposition 3.6).

Let $L^{\prime}\sim\mu_{n}$. Recall from [ORW21]*Prop. 2.1 that for any fixed
prime $p$ and any $1\leq r\leq n$, if we sample $S$ according to the uniform
distribution on ${\mathrm{Gr}}_{n,r}({\mathbb{F}}_{p})$, statistically
independent of $L^{\prime}$, the lattice $L=p^{r/n}L^{\prime}(S)$ will also be
distributed according to $\mu_{n}$. Thus, for $L\sim\mu_{n}$ and any
$\tau\in(0,1)$,

$\displaystyle\Pr(\eta({\mathcal{K}},L)\geq
2\tau)=\Pr(\eta({\mathcal{K}},p^{r/n}L^{\prime}(S))\geq 2\tau).$

We proceed to upper bound the right hand side of the above expression, using
Corollary 3.5. Let
$\bar{\rho}=8\cdot\left(\frac{50}{\delta}\right)^{\frac{2}{n}}$ (note that
$\bar{\rho}<\left(\frac{2}{\delta}\right)^{\frac{n}{2}}$ for $n>25$), and let
$E$ be the set of all lattices $L^{\prime}$ with unit covolume for which
$\rho_{{\mathcal{K}}}(L^{\prime})<\bar{\rho}$. Applying Proposition 3.6 with
$\alpha=2\left(\frac{50}{\delta}\right)^{\frac{1}{n}}$, we have that
$\Pr(L^{\prime}\in E^{c})<0.06\delta$. Now, applying Corollary 3.5 with
$\delta^{\prime}=0.47\delta$, $\tau=\varepsilon/2$, we see that for any
${\mathcal{K}}\in{\mathrm{Conv}_{n}}$ with

$\displaystyle{\mathrm{vol}}({\mathcal{K}})$
$\displaystyle>\left(\frac{2}{0.47}\right)^{6}c_{5}\bar{\rho}^{6}\left(\frac{1}{\varepsilon\delta}\right)^{6}n^{3}$
$\displaystyle=\left(\frac{2}{0.47}\right)^{6}\cdot 8^{6}\cdot
50^{\frac{12}{n}}\cdot
c_{5}\cdot\left(\frac{1}{\delta}\right)^{\frac{12}{n}}\left(\frac{1}{\varepsilon\delta}\right)^{6}n^{3},$
(38)

there is a prime number $p$ and an integer $3<r<n$ for which

$\displaystyle\Pr\left(\eta({\mathcal{K}},p^{r/n}L^{\prime}(S))\geq\varepsilon\leavevmode\nobreak\
|\leavevmode\nobreak\ L^{\prime}\in E\right)<0.94\delta.$

In particular, this holds for any ${\mathcal{K}}\in{\mathrm{Conv}_{n}}$ with
${\mathrm{vol}}({\mathcal{K}})>c_{1}\left(\frac{1}{\varepsilon\delta}\right)^{6.5}n^{3}$,
since $c_{1}\left(\frac{1}{\varepsilon\delta}\right)^{6.5}n^{3}$ is greater
than the right hand side of (38). Our claim now follows since

$\displaystyle\Pr\left(\eta({\mathcal{K}},L)\geq\varepsilon\right)$
$\displaystyle=\Pr\left(\eta({\mathcal{K}},p^{r/n}L^{\prime}(S))\geq\varepsilon\right)$
$\displaystyle\leq\Pr(L^{\prime}\in
E^{c})+\Pr\Big{(}\eta({\mathcal{K}},p^{r/n}L^{\prime}(S))\geq\varepsilon\leavevmode\nobreak\
|\leavevmode\nobreak\ L^{\prime}\in E\Big{)}$
$\displaystyle<0.06\delta+0.94\delta.$

∎

######  Remark 3.7.

Improved bounds in Theorem 2.2 will result in tighter upper bounds on the
minimal required volume for smooth covering. Specifically, assume the
following holds: for $n$ large enough, $\delta,\tau\in(0,1)$ any prime
$p>p^{*}$ and any $A\subset{\mathbb{F}}_{p}^{n}$ and
$r>m_{*}+(n-\log_{p}|A|)$, the conclusion of Theorem 2.2 holds. Then, roughly
speaking, the proof we give for Theorem 1.2, with simple modifications, shows
that there is a constant $c>0$, such that (2) holds for any convex body
${\mathcal{K}}$ for which ${\mathrm{vol}}({\mathcal{K}})\geq
c\cdot(p_{*})^{m_{*}}$, as long as $p_{*}=\Omega(n)$.

On the other hand, it follows from [CoxeterFewRogers] that there exists
${\mathcal{K}}\in{\mathrm{Conv}_{n}}$ with volume $\Omega(n)$ such that
$\eta({\mathcal{K}},L)\geq 1$ for all unit covolume lattices. This gives an
obvious bound on the extent to which Theorem 1.2 can be improved. Namely, if
one can prove that (17) holds for fixed $0<\delta,\tau<1$, $p_{*}\asymp n$ and
$m_{*}$ arbitrarily close to $1$, this will show that the lower bound in
[CoxeterFewRogers] is essentially tight, and is attained for a “typical”
lattice (and even for $\eta<1$, i.e., with smooth covering).

For the proof of Theorem 1.4 we will also need the following statement, proved
in §3.4.

######  Lemma 3.8.

For any lattice $L\subset{\mathbb{R}}^{n}$, convex set
${\mathcal{K}}\in{\mathrm{Conv}_{n}}$, and positive integer $m$, we have

$\displaystyle\eta(m{\mathcal{K}},L)\leq\eta({\mathcal{K}},L).$

###### Proof of Theorem 1.4 (assuming Lemma 3.8).

Let

$M=c_{5}\cdot
4^{6}\cdot\left(\frac{1}{\varepsilon\delta}\right)^{6}n^{3(1+2b)}=c_{3}\left(\frac{1}{\varepsilon\delta}\right)^{6}n^{3(1+2b)},$

so that by assumption we have ${\mathrm{vol}}({\mathcal{K}})\geq M$. By Lemma
3.8, replacing ${\mathcal{K}}$ if necessary with $\frac{1}{a}{\mathcal{K}}$
for some integer $a\geq 2$, we may further assume
${\mathrm{vol}}({\mathcal{K}})\in[M,2^{n}M)$. We apply Corollary 3.5 with
$L={\mathbb{Z}}^{n}$, $\bar{\rho}=n^{b}$, $\delta^{\prime}=\delta/2$ and
$\tau=\epsilon/2$. It is straightforward to verify that $p$ satisfies (33) for
${\mathrm{vol}}({\mathcal{K}})\in[M,2^{n}M)$, and the conditions on
${\mathrm{vol}}({\mathcal{K}})$ and $r$ also trivially hold. Thus, recalling
that $p^{r/n}L(S)=p^{r/n}{\mathbb{Z}}^{n}(S)$ is distributed as a lattice
drawn from the $(p,r)$ random construction A ensemble, we obtain the required
statement. ∎

###  3.3. High probability bounds on $\rho_{\mathcal{K}}(L)$

In this subsection we will give a simple proof of Proposition 3.6. The first
results showing the existence of a global constant $c>0$, independent of the
dimension $n$, such that for any ${\mathcal{K}}\in{\mathrm{Conv}_{n}}$ there
is a lattice $L$ such that $\rho_{{\mathcal{K}}}(L)<c$, are due to Butler
[Butler] and Bourgain [Bourgain]. The probability (with respect to the Siegel-
Haar measure) that a randomly chosen lattice satisfies
$\rho_{{\mathcal{K}}}(L)<c$ was not discussed in these papers. Using
[ORW21]*Cor. 1.6 together with the bound
${\mathrm{vol}}({\mathcal{K}}-{\mathcal{K}})\leq{\mathrm{vol}}(4{\mathcal{K}})$
proved in [RogersShepard57], one sees that
$\Pr\left(\rho_{{\mathcal{K}}}(L)>4+o(1)\right)$ vanishes exponentially fast
with $n$. However, we can give a much simpler proof, albeit with a worse
constant. Note that the value of the constant has small effect on the bounds
we obtain for the covering smoothness.

###### Proof of Proposition 3.6.

We will derive a high-probability lower bound on
$\mathrm{r}_{\text{pack},{\mathcal{K}}}(L)$ and a high-probability upper bound
on $\mathrm{r}_{\text{cov},{\mathcal{K}}}(L)$. Assume without loss of
generality that ${\mathrm{vol}}({\mathcal{K}})=1$. Denote

$N^{*}(L,{\mathcal{K}},x){\,\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\,}\left|((L\setminus\\{0\\})-x)\cap{\mathcal{K}}\right|=\left|\left\\{y\in
L\setminus\\{0\\}\ :\ x\in y-{\mathcal{K}}\right\\}\right|.$

For lower bounding $\mathrm{r}_{\text{pack},{\mathcal{K}}}(L)$, let
${\mathcal{K}}_{0}=\frac{1}{2\alpha}{\mathcal{K}}$ and let
$N^{*}(L,{\mathcal{K}}_{0}-{\mathcal{K}}_{0},0)$ be the number of non-zero
points of the lattice $L$ in ${\mathcal{K}}_{0}-{\mathcal{K}}_{0}$. By
Siegel’s theorem [SiegelFormula], we have

$\mathbb{E}[N^{*}(L,{\mathcal{K}}_{0}-{\mathcal{K}}_{0},0)]={\mathrm{vol}}({\mathcal{K}}_{0}-{\mathcal{K}}_{0}).$

Thus, by Markov’s inequality,

$\displaystyle\Pr(N^{*}(L,{\mathcal{K}}_{0}-{\mathcal{K}}_{0},0)$
$\displaystyle\neq 0)=\Pr(N^{*}(L,{\mathcal{K}}_{0}-{\mathcal{K}}_{0},0)\geq
1)$
$\displaystyle\leq\mathbb{E}[N^{*}(L,{\mathcal{K}}_{0}-{\mathcal{K}}_{0},0)]$
$\displaystyle={\mathrm{vol}}({\mathcal{K}}_{0}-{\mathcal{K}}_{0})$
$\displaystyle\leq{\mathrm{vol}}(4{\mathcal{K}}_{0})=\left(\frac{4}{2\alpha}\right)^{n},$
(39)

where the last inequality in (39) follows from [RogersShepard57]*Theorem 1.
Now, since $N^{*}(L,{\mathcal{K}}_{0}-{\mathcal{K}}_{0},0)=0$ implies that $L$
forms a packing with respect to ${\mathcal{K}}_{0}$, we see that

$\displaystyle\Pr\left(\mathrm{r}_{\text{pack},{\mathcal{K}}}(L)\leq\frac{1}{2\alpha}\right)\leq\left(\frac{2}{\alpha}\right)^{n}.$
(40)

Recall that $m_{L}$ denotes the Haar measure on
$\mathbb{T}_{L}=\mathbb{R}^{n}/L$. For the upper bound on the covering radius
recall the basic fact (see, e.g., [ORW21]*Lemma 2.5) that

$m_{L}\left(\pi_{L}\left(\frac{\alpha}{2}{\mathcal{K}}\right)\right)>\frac{1}{2}\
\implies\ \mathrm{r}_{\text{cov},{\mathcal{K}}}(L)\leq\alpha.$

It therefore only remains to upper bound
$\Pr\big{(}m_{L}(\pi_{L}({\mathcal{K}}_{1}))\leq 1/2\big{)}$, where
${\mathcal{K}}_{1}=\frac{\alpha}{2}{\mathcal{K}}$. We do this by showing that
$\mathbb{E}[m_{L}(\pi_{L}({\mathcal{K}}_{1}))]$ is close to $1$. We begin by
noting that

$\displaystyle m_{L}(\pi_{L}({\mathcal{K}}_{1}))$
$\displaystyle=\int_{x\in{\mathcal{K}}_{1}}\frac{1}{|(x+L)\cap{\mathcal{K}}_{1}|}dx$
$\displaystyle=\int_{x\in{\mathcal{K}}_{1}}\frac{1}{1+N^{*}(L,{\mathcal{K}}_{1},-x)}dx.$

Since the function $t\mapsto\frac{1}{1+t}$ is convex in the regime $t>0$, we
can apply Jensen’s inequality and obtain

$\displaystyle\mathbb{E}[m_{L}(\pi_{L}({\mathcal{K}}_{1}))]$
$\displaystyle=\mathbb{E}\left[\int_{x\in{\mathcal{K}}_{1}}\frac{1}{1+N^{*}(L,{\mathcal{K}}_{1},-x)}dx\right]$
$\displaystyle=\int_{x\in{\mathcal{K}}_{1}}\mathbb{E}\left[\frac{1}{1+N^{*}(L,{\mathcal{K}}_{1},-x)}\right]dx$
(41)
$\displaystyle\geq\int_{x\in{\mathcal{K}}_{1}}\frac{1}{1+\mathbb{E}\left[N^{*}(L,{\mathcal{K}}_{1},-x)\right]}dx$
(42)
$\displaystyle=\int_{x\in{\mathcal{K}}_{1}}\frac{1}{1+{\mathrm{vol}}({\mathcal{K}}_{1})}dx$
(43)
$\displaystyle=\frac{{\mathrm{vol}}({\mathcal{K}}_{1})}{1+{\mathrm{vol}}({\mathcal{K}}_{1})},$
(44)

where (41) follows from Fubini’s Theorem, (42) from Jensen’s inequality and
(43) from Siegel’s summation formula. Let

$P_{e}=\Pr\left(m_{L}(\pi_{L}({\mathcal{K}}_{1}))\leq\frac{1}{2}\right).$

Since $m_{L}(\pi_{L}({\mathcal{K}}_{1}))\leq 1$ we have that

$\displaystyle\mathbb{E}[m_{L}(\pi_{L}({\mathcal{K}}_{1}))]\leq\frac{P_{e}}{2}+(1-P_{e})=1-\frac{P_{e}}{2}.$

Combining this with (44), we obtain

$P_{e}\leq
2\left(1-\frac{{\mathrm{vol}}({\mathcal{K}}_{1})}{1+{\mathrm{vol}}({\mathcal{K}}_{1})}\right)<\frac{2}{{\mathrm{vol}}({\mathcal{K}}_{1})}.$

Thus,

$\displaystyle\Pr(\mathrm{r}_{\text{cov},{\mathcal{K}}}(L)\geq\alpha)<2\cdot\left(\frac{2}{\alpha}\right)^{n}.$
(45)

Combining (40) and (45) we obtain the claimed result. ∎

###  3.4. On the monotonicity of $\alpha\mapsto\eta(\alpha{\mathcal{K}},L)$

As mentioned above, the mapping $\alpha\mapsto\eta(\alpha{\mathcal{K}},L)$ is
not monotonically non-increasing in general. Nevertheless, Lemma 3.8, stated
above, shows that for dilates by positive integers, the covering smoothness
can only decrease. We can exploit this fact to establish Theorems 1.3 and 1.6,
which show that for any ${\mathcal{K}}\in{\mathrm{Conv}_{n}}$ with
sufficiently large (polynomial) volume, a typical lattice has small
$\eta(\alpha{\mathcal{K}},L)$ for all $\alpha\geq 1$. We first provide the
proof of Lemma 3.8, and then leverage this result and prove Theorems 1.3 and
1.6.

###### Proof of Lemma 3.8.

We can write

$N(L,m{\mathcal{K}},x)=N\left(\frac{L}{m},{\mathcal{K}},\frac{x}{m}\right)=\sum_{a}N\left(L,{\mathcal{K}},\frac{x}{m}-a\right)\;,$

where the sums runs over all coset representatives $a$ for the inclusion
$L\subset\frac{L}{m}$. We therefore have

$\displaystyle{\eta}(m{\mathcal{K}},L)$
$\displaystyle=\sup_{x\in{\mathbb{R}}^{n}}\left|\frac{N(L,m{\mathcal{K}},x)}{{\mathrm{vol}}(m{\mathcal{K}})/\mathrm{covol}(L)}-1\right|$
$\displaystyle=\sup_{x\in{\mathbb{R}}^{n}}\left|m^{-n}\sum_{a}\Big{(}\frac{N(L,{\mathcal{K}},x/m-a)}{{\mathrm{vol}}({\mathcal{K}})/\mathrm{covol}(L)}-1\Big{)}\right|$
$\displaystyle\leq
m^{-n}\sup_{x\in{\mathbb{R}}^{n}}\sum_{a}\left|\frac{N(L,{\mathcal{K}},x/m-a)}{{\mathrm{vol}}({\mathcal{K}})/\mathrm{covol}(L)}-1\right|$
$\displaystyle\leq
m^{-n}\sum_{a}\sup_{x\in{\mathbb{R}}^{n}}\left|\frac{N(L,{\mathcal{K}},x/m-a)}{{\mathrm{vol}}({\mathcal{K}})/\mathrm{covol}(L)}-1\right|={\eta}({\mathcal{K}},L)\;.$

∎

Using this weak monotonicity property, we now show that if a lattice $L$
smoothly covers ${\mathbb{R}}^{n}$ with respect to $\alpha_{i}{\mathcal{K}}$
for all $\alpha_{i}$ in a dense enough net in $[1,2)$, it must smoothly cover
${\mathbb{R}}^{n}$ with respect to $\alpha{\mathcal{K}}$ for all $\alpha\geq
1$.

######  Lemma 3.9.

Let $n\in{\mathbb{N}}$ and $0<\varepsilon<1$. Let
$\beta=\frac{\varepsilon}{8n}$ and $I=\left\lceil\frac{\log
2}{\log(1+\beta)}\right\rceil$. Define $\alpha_{i}=(1+\beta)^{i}$ for all
$i=0,1,\ldots,I$, such that $\alpha_{0}=1$, and $\alpha_{I}\geq 2$. For a
lattice $L\subset{\mathbb{R}}^{n}$ and ${\mathcal{K}}\in{\mathrm{Conv}_{n}}$
assume that ${\eta}(\alpha_{i}{\mathcal{K}},L)\leq\varepsilon/2$ for all
$i=0,1,\ldots,I$. Then ${\eta}(\alpha{\mathcal{K}},L)<\varepsilon$ for all
$\alpha\geq 1$.

###### Proof.

Note that for any $\alpha\in[1,2)$ there is $i\in\\{1,\ldots,I\\}$ such that
$\alpha_{i-1}\leq\alpha\leq\alpha_{i}$. We therefore have that for any
$x\in{\mathbb{R}}^{n}$,

$\displaystyle\frac{N(L,\alpha{\mathcal{K}},x)}{{\mathrm{vol}}(\alpha{\mathcal{K}})/\mathrm{covol}(L)}$
$\displaystyle\leq\frac{{\mathrm{vol}}(\alpha_{i}{\mathcal{K}})}{{\mathrm{vol}}(\alpha{\mathcal{K}})}\frac{N(L,\alpha_{i}{\mathcal{K}},x)}{{\mathrm{vol}}(\alpha_{i}{\mathcal{K}})/\mathrm{covol}(L)}$
$\displaystyle\leq(1+\beta)^{n}\left(1+\frac{\varepsilon}{2}\right)<(1+\varepsilon),$

where in the last inequality we used the fact that $(1+\beta)^{n}\leq e^{\beta
n}\leq 1+2\beta n=1+\frac{\varepsilon}{4}$, which follows since $e^{t}<1+2t$
for $t<1/2$. Similarly,

$\displaystyle\frac{N(L,\alpha{\mathcal{K}},x)}{{\mathrm{vol}}(\alpha{\mathcal{K}})/\mathrm{covol}(L)}$
$\displaystyle\geq\frac{{\mathrm{vol}}(\alpha_{i-1}{\mathcal{K}})}{{\mathrm{vol}}(\alpha{\mathcal{K}})}\frac{N(L,\alpha_{i-1}{\mathcal{K}},x)}{{\mathrm{vol}}(\alpha_{i-1}{\mathcal{K}})/\mathrm{covol}(L)}$
$\displaystyle\geq(1+\beta)^{-n}\left(1-\frac{\varepsilon}{2}\right)>(1-\varepsilon),$

where, as above, in the last inequality we used the fact that
$(1+\beta)^{-n}\geq\frac{1}{1+2\beta n}\geq 1-2\beta
n=1-\frac{\varepsilon}{4}$. Thus, ${\eta}(\alpha{\mathcal{K}},L)<\varepsilon$
for all $\alpha\in[1,2)$. Finally, for any $\alpha\geq 1$ there is a positive
integer $m$ such $\alpha^{\prime}=\alpha/m\in[1,2)$, and thus, by Lemma 3.8,
${\eta}(\alpha{\mathcal{K}},L)<\varepsilon$. ∎

###### Proof of Theorem 1.3.

Assume
${\mathrm{vol}}({\mathcal{K}})=c_{2}\left(\frac{1}{\varepsilon^{2}\delta}\right)^{6.5}n^{3}$.
Let

$\beta=\frac{\varepsilon}{8n}\text{ and }I=\left\lceil\frac{\log
2}{\log(1+\beta)}\right\rceil\leq\frac{8n}{\varepsilon}-1.$

Define $\alpha_{i}=(1+\beta)^{i}$ for all $i=0,1,\ldots,I$ and note that

$\displaystyle\alpha_{i}^{n}\geq e^{\frac{\varepsilon}{9}i}.$ (46)

Indeed,

$\displaystyle(1+\beta)^{n}=\left(1+\frac{\varepsilon}{8n}\right)^{n}=e^{n\log(1+\frac{\varepsilon}{8n})}\geq
e^{n\frac{\varepsilon/8n}{1+\varepsilon/8n}}=e^{\frac{\varepsilon/8}{1+\varepsilon/8n}}>e^{\frac{\varepsilon/8}{9/8}}=e^{\frac{\varepsilon}{9}}.$

For all $i=0,1,\ldots,I$ we apply Theorem 1.2 with
$\varepsilon^{\prime}=\varepsilon/2$ and
$\delta_{i}=\frac{\delta\varepsilon}{64}\cdot e^{-\frac{\varepsilon}{60}i}$
and ${\mathcal{K}}_{i}=\alpha_{i}{\mathcal{K}}$. Noting that

$\displaystyle
c_{1}\left(\frac{1}{\varepsilon^{\prime}\delta_{i}}\right)^{6.5}n^{3}$
$\displaystyle<(128)^{6.5}c_{1}\left(\frac{1}{\varepsilon^{2}\delta}\right)^{6.5}e^{\frac{\varepsilon}{9}i}n^{3}\stackrel{{\scriptstyle\eqref{eq:alphaibound}}}{{<}}\alpha_{i}^{n}c_{2}\left(\frac{1}{\varepsilon^{2}\delta}\right)^{6}n^{3}\leq{\mathrm{vol}}({\mathcal{K}}_{i}),$

the theorem implies that

$\displaystyle\Pr\left({\eta}(\alpha_{i}{\mathcal{K}},L)\geq\frac{\varepsilon}{2}\right)<\delta_{i},\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \forall i=0,1,\ldots,I.$ (47)

Let $E$ be the set of all unit covolume lattices such that
${\eta}(\alpha_{i}{\mathcal{K}},L)<\varepsilon/2$ for all $i=0,1,\ldots,I$. By
the union bound and (47), we have that

$\displaystyle\Pr(L\notin E)$
$\displaystyle\leq\sum_{i=0}^{I}\delta_{i}=\frac{\delta\varepsilon}{64}\sum_{i=0}^{I}e^{-\frac{\varepsilon}{60}i}<\frac{\delta\varepsilon}{64}\sum_{i=0}^{\infty}e^{-\frac{\varepsilon}{60}i}=\frac{\delta\varepsilon}{64}\frac{1}{1-e^{-\frac{\varepsilon}{60}}}$
$\displaystyle\leq\frac{\delta\varepsilon}{64}\left(1+\frac{60}{\varepsilon}\right)<\delta,$

where we have used the fact that $e^{-x}\leq\frac{1}{1+x}$ for $x\geq 0$. Our
claim now follows by applying Lemma 3.9. ∎

###### Proof of Theorem 1.6.

Assume
${\mathrm{vol}}({\mathcal{K}})=c_{4}\left(\frac{1}{\varepsilon^{2}\delta}\right)^{6}n^{9+6b}$.
Let $\beta=\frac{\varepsilon}{8n}$ and $I=\left\lceil\frac{\log
2}{\log(1+\beta)}\right\rceil\leq\frac{8n}{\varepsilon}-1$. Define
$\alpha_{i}=(1+\beta)^{i}$ for all $i=0,1,\ldots,I$. For all $i=0,1,\ldots,I$
we apply Theorem 1.4 with $\varepsilon^{\prime}=\varepsilon/2$ and
$\delta^{\prime}=\delta/(I+1)$ and
${\mathcal{K}}^{\prime}=\alpha_{i}{\mathcal{K}}$. Noting that
$\varepsilon^{\prime}\delta^{\prime}\geq\frac{\varepsilon^{2}\delta}{16n}$ and
that

$\displaystyle
c_{3}\left(\frac{1}{\varepsilon^{\prime}\delta^{\prime}}\right)^{6}n^{3(1+2b)}\leq
c_{4}\left(\frac{1}{\varepsilon^{2}\delta}\right)^{6}n^{9+6b}\leq{\mathrm{vol}}({\mathcal{K}}^{\prime}),$

the theorem implies that

$\displaystyle\Pr({\eta}(\alpha_{i}{\mathcal{K}},p^{r/n}L)\geq\varepsilon/2)<\frac{\delta}{I+1},\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \forall i=0,1,\ldots,I.$ (48)

Let $E$ be the set of all $(p,r)$ construction A lattices such that

${\eta}(\alpha_{i}{\mathcal{K}},p^{r/n}L)<\frac{\varepsilon}{2},\ \ \text{ for
}i=0,1,\ldots,I.$

By the union bound and (48), we have that $\Pr(L\notin E)<\delta$. Our claim
now follows by applying Lemma 3.9. ∎

###  3.5. Non-lattice smooth coverings

In this subsection we will prove Theorem 1.7. The proof follows the same
outline and notation as the proof of Theorem 3.4. In the previous sections we
started with a lattice $L$ with a reasonable $\rho_{{\mathcal{K}}}(L)$ and
constructed from it a denser lattice $L(S)$ by choosing
$S\subset{\mathbb{F}}_{p}^{n}$ to be a subspace. The work of Dhar and Dvir
[dd22] was then used to show that for any subset $A\in{\mathbb{F}}_{p}^{n}$,
and a randomly uniform subspace $S\in{\mathbb{F}}_{p}^{n}$, if $p$ is
sufficiently large and $\frac{|S|\cdot|A|}{p^{n}}>p^{3}$, then
$\eta_{{\mathbb{F}}_{p}}(A,S)$ is small with high probability. This was then
leveraged for showing that under suitable conditions a randomly chosen
subspace $S$ will yield a lattice $L(S)$ such that $L(S)+{\mathcal{K}}$
smoothly covers ${\mathbb{R}}^{n}$. Note that if
$S\subset{\mathbb{F}}_{p}^{n}$ is not a subspace, the discrete set $L(S)$, as
given in (13) is not a lattice, but is nevertheless well defined, and has
asymptotic density $\frac{|S|}{\mathrm{covol}(L)}$. Furthermore, recall that
the definition of $\eta_{{\mathbb{F}}_{p}}(A,S)$ does not require $S$ to be a
subspace. For a random set $S$ (rather than a random subspace, as in [dd22]),
controlling the tail of $\eta_{{\mathbb{F}}_{p}}(A,S)$ is a significantly
simpler task. The following result easily follows from large deviation theory.

######  Lemma 3.10.

Let $n,m$ be positive integers, $p$ be a prime number and let
$\delta,\tau\in(0,1)$. Let $S$ be a set of $m$ points identically distributed
independently uniformly over ${\mathbb{F}}_{p}^{n}$. Then, for any set
$A\subset{\mathbb{F}}_{p}^{n}$, we have that if
$\frac{m|A|}{p^{n}}>\frac{3}{\tau^{2}}\left(n\log
p-\log\frac{\delta}{2}\right)$, then

$\displaystyle\Pr({\eta_{{\mathbb{F}}_{p}}}(A,S)\geq\tau\leavevmode\nobreak\
\text{or}\leavevmode\nobreak\ |S|\neq m)\leq\delta+m^{2}p^{-n}.$

The lemma follows easily from the following well-known large deviations bound,
see e.g., [MitzenmacherUpfal17]*Corollary 4.6.

######  Proposition 3.11 (Chernoff bound).

For any $\eta\in(0,1)$ and any $m$ identically distributed independent
Bernoulli random variables $Y_{1},\dots,Y_{m}$, the sum
$Y{\,\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\,}\sum_{i=1}^{m}Y_{i}$
satisfies

$\Pr\left(\left|Y-\mu\right|\geq\eta\mu\right)\leq
2e^{-\frac{\eta^{2}\mu}{3}},$ (49)

where $\mu{\,\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\,}\mathbb{E}(Y).$

###### Proof of Lemma 3.10.

Let $X_{i}\stackrel{{\scriptstyle
i.i.d}}{{\sim}}\mathrm{Uniform}({\mathbb{F}}_{p}^{n})$ for $i=1,\ldots,m$, and
$S=\\{X_{1},\ldots,X_{m}\\}$. For any $x\in{\mathbb{F}}_{p}^{n}$ let $Y_{i,x}$
be the indicator of the event that $x+X_{i}\in A$. We clearly have that the
random variables $\\{Y_{i,x}\\}_{i=1}^{m}$ are i.i.d. Bernoulli with
$\Pr(Y_{i,x}=1)=\frac{|A|}{p^{n}}$. Thus, $Y_{x}=\sum_{i=1}^{m}Y_{i,x}$
satisfies the conditions of Proposition 3.11, and applying it with
$\mu=\mathbb{E}(Y_{x})=\frac{m|A|}{p^{n}}$ and $\eta=\tau$, gives that if
$\frac{m|A|}{p^{n}}>\frac{3}{\tau^{2}}\left(n\log
p-\log\frac{\delta}{2}\right)$ then

$\displaystyle\Pr$ $\displaystyle\left(\left|\frac{|(x+S)\cap
A|}{m\cdot|A|p^{-n}}-1\right|\geq\tau\right)$
$\displaystyle=\Pr(|Y_{x}-\mu|\geq\tau\mu)\leq
2e^{-\frac{\tau^{2}}{3}\frac{3}{\tau^{2}}\left(n\log
p-\log\frac{\delta}{2}\right)}=\delta\cdot p^{-n}.$

Applying the union bound, this implies that

$\displaystyle\Pr\left(\max_{x\in{\mathbb{F}}_{p}^{n}}\left|\frac{|(x+S)\cap
A|}{m\cdot|A|p^{-n}}-1\right|\geq\tau\right)\leq\delta.$

Finally, noting that

$\displaystyle\Pr(|S|\neq m)\leq\sum_{1\leq i<j\leq
m}\Pr(X_{i}=X_{j})=\binom{m}{2}p^{-n}<m^{2}p^{-n},$

and applying the union bound again, we obtain the claimed result. ∎

###### Proof of Theorem 1.7.

Let ${\mathcal{K}}\in{\mathrm{Conv}_{n}}$,
$\frac{320n}{\tau}<p<\frac{640n}{\tau}$ be a prime number for some
$\tau\in(0,1)$ to be chosen later, and $c=40$. Let $L$ be a lattice so that
$(L,(1+\frac{c}{p}){\mathcal{K}})$ is a packing and $(L,c{\mathcal{K}})$ is a
covering. Such a lattice exists by Proposition 3.6. Note further, that for
such a lattice we have that
$\frac{\mathrm{covol}(L)}{{\mathrm{vol}}({\mathcal{K}})}<c^{n}=40^{n}$. Denote
$\rho=\frac{c}{p}<\frac{\tau}{8n}$, such that in particular
$0<\rho<\frac{1}{2n}$. We follow the derivations in the proof of Theorem 3.4
up to equation (32), where instead of assuming
$S\in{\mathrm{Gr}}_{n,r}({\mathbb{F}}_{p})$, we assume
$S\subset{\mathbb{F}}_{p}^{n}$ is an arbitrary subset of $m$ points in
${\mathbb{F}}_{p}^{n}$. This derivation does not rely on $S$ being a subspace
and therefore holds verbatim, where the only difference is that we replace the
definitions of the sets $E_{0}$ and $E_{1}$ from (26) and (27) with

$\displaystyle E_{0}$
$\displaystyle{\,\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\,}\left\\{S\in\mathcal{R}_{m,n}({\mathbb{F}}_{p})\
:\ {\eta_{{\mathbb{F}}_{p}}}(A_{0},S)>\tau\right\\},$ $\displaystyle E_{1}$
$\displaystyle{\,\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\,}\left\\{S\in\mathcal{R}_{m,n}({\mathbb{F}}_{p})\
:\ {\eta_{{\mathbb{F}}_{p}}}(A_{1},S)>\tau\right\\},$

where
$\mathcal{R}_{m,n}({\mathbb{F}}_{p})=\\{S\subset{\mathbb{F}}_{p}^{n}\leavevmode\nobreak\
:\leavevmode\nobreak\ |S|=m\\}$. We therefore have that

$\displaystyle{\eta}({\mathcal{K}},L(S))\leq\tau+8\rho n\leq
2\tau,\leavevmode\nobreak\ \leavevmode\nobreak\ \forall S\in E^{c}.$ (50)

We proceed to upper bound $\Pr(S\in E)$ for the case where $S$ consists of $m$
points drawn i.i.d. from the uniform distribution over ${\mathbb{F}}_{p}^{n}$.
By (25), we have that for $i=0,1$

$\displaystyle\frac{|A_{i}|}{p^{n}}\geq(1-2\rho)^{n}\frac{{\mathrm{vol}}({\mathcal{K}})}{\mathrm{covol}(L)}\geq(1-2n\rho)\frac{{\mathrm{vol}}({\mathcal{K}})}{\mathrm{covol}(L)}\geq\left(1-\frac{\tau}{4}\right)\frac{{\mathrm{vol}}({\mathcal{K}})}{\mathrm{covol}(L)},$
(51)

where the second inequality is due to (31), and the third follows since
$\rho<\frac{\tau}{8n}$. Thus, by Lemma 3.10, for any $\delta\in(0,1)$, if

$\displaystyle\left(1-\frac{\tau}{4}\right)\cdot{\mathrm{vol}}({\mathcal{K}})\cdot\frac{m}{\mathrm{covol}(L)}>\frac{3}{\tau^{2}}\left(n\log
p-\log\frac{\delta}{2}\right)$ (52)

then $\Pr(E_{i})<\delta+m^{2}p^{-n}$ for $i=1,2$. We take $\tau=\varepsilon/2$
and $\delta=2e^{-2}$ and choose

$\displaystyle m$
$\displaystyle=\left\lceil\frac{\mathrm{covol}(L)}{{\mathrm{vol}}({\mathcal{K}})}\frac{1}{\left(1-\frac{\varepsilon}{8}\right)}\frac{12}{\varepsilon^{2}}\left(n\log
p+2\right)\right\rceil$
$\displaystyle<\frac{\mathrm{covol}(L)}{{\mathrm{vol}}({\mathcal{K}})}\frac{14}{\varepsilon^{2}}\left(n\log
p+2\right)$

to be the smallest integer satisfying the above constraint, so that
$\Pr(E)\leq 2\delta+2{m}^{2}p^{-n}=4e^{-2}+2{m}^{2}p^{-n}$. Recalling that
$\frac{\mathrm{covol}(L)}{{\mathrm{vol}}({\mathcal{K}})}<40^{n}$ and that
$\frac{640n}{\varepsilon}\leq p\leq\frac{1280n}{\varepsilon}$ we see that

$\displaystyle m^{2}p^{-n}$ $\displaystyle\leq
40^{2n}\frac{14^{2}}{\varepsilon^{4}}\left(n\log\frac{2560n}{\varepsilon}\right)^{2}\left(\frac{640n}{\varepsilon}\right)^{-n}$
$\displaystyle<40^{2n}\frac{14^{2}}{\varepsilon^{4}}\left(\frac{2560n^{2}}{\varepsilon}\right)^{2}\left(\frac{640n}{\varepsilon}\right)^{-n}$
$\displaystyle<\left(\frac{40^{2}}{640}\right)^{n}\left(\frac{n}{\varepsilon}\right)^{-(n-6)}(14\cdot
2560)^{2}$

and this is smaller than $0.08$ for all $n\geq 20$, and so $\Pr(E)\leq
4e^{-2}+2m^{2}p^{-n}<1$ for all $n\geq 20$. We therefore see that there exists
a discrete set $L(S)$ with asymptotic density
$D(L(S))=\frac{m}{\mathrm{covol}(L)}$ such that

$\displaystyle{\mathrm{vol}}({\mathcal{K}})D(L(S))<\frac{14}{\varepsilon^{2}}\left(n\log
p+2\right)$ (53)

and $\eta({\mathcal{K}},L(S))<\varepsilon$. Recalling that
$p<\frac{1280n}{\varepsilon}$, we obtain the claimed result. ∎

## References