# Quantifying Character Similarity with Vision Transformers

Xinmei Yang1, Abhishek Arora2, Shao-Yu Jheng2, Melissa Dell${}^{2,3^{\ast}}$
1Renmin University; Beijing, China.
2Harvard University; Cambridge, MA, USA.
3National Bureau of Economic Research; Cambridge, MA, USA.
∗Corresponding author<EMAIL_ADDRESS>
###### Abstract

Record linkage is a bedrock of quantitative social science, as analyses often
require linking data from multiple, noisy sources. Off-the-shelf string
matching methods are widely used, as they are straightforward and cheap to
implement and scale. Not all character substitutions are equally probable, and
for some settings there are widely used handcrafted lists denoting which
string substitutions are more likely, that improve the accuracy of string
matching. However, such lists do not exist for many settings, skewing research
with linked datasets towards a few high-resource contexts that are not
representative of the diversity of human societies. This study develops an
extensible way to measure character substitution costs for OCR’ed documents,
by employing large-scale self-supervised training of vision transformers (ViT)
with augmented digital fonts. For each language written with the CJK script,
we contrastively learn a metric space where different augmentations of the
same character are represented nearby. In this space, homoglyphic characters -
those with similar appearance such as “O” and “0” - have similar vector
representations. Using the cosine distance between characters’ representations
as the substitution cost in an edit distance matching algorithm significantly
improves record linkage compared to other widely used string matching methods,
as OCR errors tend to be homoglyphic in nature. Homoglyphs can plausibly
capture character visual similarity across any script, including low-resource
settings. We illustrate this by creating homoglyph sets for 3,000 year old
ancient Chinese characters, which are highly pictorial. Fascinatingly, a ViT
is able to capture relationships in how different abstract concepts were
conceptualized by ancient societies, that have been noted in the
archaeological literature.

##  1 Introduction

Many quantitative analyses in the social sciences - as well as government and
business applications - require linking information from multiple datasets.
For example, researchers and governments link historical censuses, match hand-
written records from vaccination campaigns to administrative data, and de-
duplicate voter rolls. The sources to be linked often contain noise,
particularly when they were created with optical character recognition (OCR).
String matching methods are widely used to link entities across datasets, as
they are straightforward to implement off-the-shelf and can be scaled to
massive datasets Binette and Steorts (2022); Abramitzky et al. (2021).

Most simply, approximate string matching methods count the number of edits
(insertions, deletions, and substitutions) to transform one string into
another Levenshtein et al. (1966). Another common approach computes the
similarity between $n$-gram representations of strings, where $n$-grams are
all substrings of length $n$ Okazaki and Tsujii (2010).

In practice, not all string substitutions are equally probable, and efforts to
construct lists that vary their costs date back over a century. For example,
in 1918 Russell and Odell patented Soundex, a sound standardization toolkit
that accounts for the fact that census enumerators often misspelled names
according to their sound. Together with the updated New York State
Identification and Intelligence System Silbert (1970), it remains a bedrock
for linking U.S. historical censuses Abramitzky et al. (2021). Similarly,
Novosad (2018) adjusts Levenshtein distance to impose smaller penalties for
common alternative spellings in Hindi, and the FuzzyChinese package znwang25
(2020) uses strokes as the unit for $n$-grams substring representations, where
the strokes for a given character are drawn from an external database kfcd
(2015) covering a subset of the CJK script. Characters sharing strokes are
more likely to be matched.

Such methods can perform well in the contexts for which they are tailored but
are labor-intensive to extend to new settings, due to the use of hand-crafted
features. Low extensibility skews research with linked data - necessary to
examine intergenerational mobility, the evolution of firm productivity, the
persistence of poverty, and many other topics - towards a few higher resource
settings that are not representative of the diversity of human societies.

This study aims to preserve the advantages of string matching methods - simple
off-the-shelf implementation and high scalability - while developing an
extensible, self-supervised method for determining the relative costs of
character substitutions in databases created with OCR. OCR often confuses
characters with their homoglyphs, which have a similar visual appearance (e.g.
“0” and “O”). Incorporating character visual similarity into string matching
can thus plausibly improve record linkage. Homoglyphs can be constructed by
hand for small script sets such as Latin, as in a psychology literature on
literacy acquisition Simpson et al. (2013), but for a script such as CJK,
containing over 38,000 characters, this is infeasible.

Following a literature on self-supervision through simple data augmentation
for image encoders Grill et al. (2020); Chen et al. (2021); Chen and He
(2021), this study uses augmented digital fonts to contrastively learn a
metric space where different augmentations of a character have similar vector
representations. The resulting space can be used, with a reference font, to
measure the visual similarity of different characters. Figure 1 shows
representative examples of how the same characters are rendered very
differently across fonts. These different representations form positive
examples for the contrastively trained HOMOGLYPH model. This purely self-
supervised approach can be extended to any character set, but since creating
evaluation data for record linkage is costly, the study focuses on languages
written with CJK: Simplified and Traditional Chinese, Japanese, and Korean.

Figure 1: Character variation across fonts. This figure illustrates examples
of the same character rendered with different fonts. Augmentations of these
comprise positives in the HOMOGLYPH training data.

We train on augmentations of the same character - rather than paired data
across characters - because a self-supervised approach is more extensible.
Paired character similarity data are limited. Unicode maintains a set of
confusables - constructed with rule-based methods - but for CJK the only
confusables are structurally identical characters with different Unicode
codepoints. Despite a large post-OCR error correction literature Lyu et al.
(2021); Nguyen et al. (2021); van Strien. et al. (2020), there is also limited
ground truth data about the types of errors that OCR makes across
architectures, languages, scripts, layouts, and document contexts.

Using the cosine distance between two characters as the substitution cost
within a Levenshtein edit distance framework Levenshtein et al. (1966)
improves record linkage with 1950s firm level data about Japanese supply
chains Jinji Koshinjo (1954); Teikoku Koshinjo (1957), relative to other
string matching methods. The study also compares to end-to-end deep learning
methods for record linkage. While these methods can outperform string
matching, the data required for them are not always available and technical
requirements for implementation are higher, explaining why string matching
methods predominate in social science applications. Homoglyphic matching is a
cheap and extensible way to improve these predominant methods.

Because creating annotated ground truth data is costly, we provide additional
evaluations using synthetically generated data. We augment image renders of
place and firm names written with different fonts, for Simplified and
Traditional Chinese, Japanese, and Korean character sets. We then OCR two
different views of each entity with different OCR engines - EasyOCR and
PaddleOCR - that use very different architectures. The different augmentations
and OCR engines lead to different text string views of the same entity with
high frequency. We then link these using string matching methods. Homoglyphic
matching outperforms other widely used string matching techniques for all four
scripts. Our HomoglyphsCJK python package provides a simple, off-the-shelf
implementation.111Package available at
https://pypi.org/project/HomoglyphsCJK/.

Homoglyphs can be extended to any script. To explore this, we contrastively
train a HOMOGLYPH model for ancient Chinese characters, using a database that
provides views of the same character from different archaeological sites and
time periods Academia Sinica et al. (2023). Ancient characters are much more
pictorial than their more abstract, modern equivalents. Fascinatingly,
homoglyphs constructed with a ViT for the Shang Dynasty (1600 BC-1045 BC)
capture ways in which ancient Chinese society related abstract concepts that
have been noted in the archaeological literature (e.g. Wang (2003)).

The rest of this study is organized as follows: Section 2 develops methods for
learning character similarity and incorporating it into record linkage, and
Section 3 describes the evaluation datasets. Section 4 compares the
performance of homoglyphic edit distance to other string matching and neural
methods for record linkage. Section 5 examines extensibility by constructing
homoglyphs for ancient Chinese, Section 6 discusses the limitations of
homoglyphs, and Section 7 concludes.

##  2 Methods

###  2.1 The HOMOGLYPH model

The HOMOGLYPH model contrastively learns a mapping between character crops and
dense vector representations, such that crops of augmentations of the same
character are nearby. HOMOGLYPH is trained purely on digital fonts. Figure 1
shows variations of the same characters rendered with different fonts, which
form positive examples for training. Variations across fonts are non-trivial,
forcing the model to learn character similarities at varying levels of
abstraction.

Figure 2: Homoglyphs. This figure illustrates the five nearest neighbors in
the HOMOGLYPH embedding space for representative characters.

We use a DINO (Self-Distillation, No Labels) pre-trained ViT as the encoder
Caron et al. (2021). DINO ViT embeddings perform well as a nearest neighbor
classifier, making them well-suited for homoglyphic matching. The model is
trained using a Supervised Contrastive loss function Khosla et al. (2020), a
generalization of the InfoNCE loss Oord et al. (2018) that allows for multiple
positive and negative pairs for a given anchor:

$\sum_{i\in I}\frac{-1}{|P(i)|}\sum_{p\in
P(i)}\log\frac{\exp\left(\boldsymbol{z}_{i}\cdot\boldsymbol{z}_{p}/\tau\right)}{\sum_{a\in
A(i)}\exp\left(\boldsymbol{z}_{i}\cdot\boldsymbol{z}_{a}/\tau\right)}$ (1)

where $\tau$ is a temperature parameter (equal to 0.1), $i$ indexes a sample
in a “multiviewed" batch (in this case multiple fonts/augmentations of
characters with the same identity), $P(i)$ is the set of indices of all
positives in the multiviewed batch that are distinct from $i$, $A(i)$ is the
set of all indices excluding $i$, and $z$ is an embedding of a sample in the
batch. Training details are describe in the supplementary materials.

To compute characters’ similarity, we embed their image crops, created with a
reference font (Google Noto), and compute cosine similarity with a Facebook
Artificial Intelligence Similarly Search backend Johnson et al. (2019).

Figure 2 shows representative examples of characters and their five nearest
neighbors. Characters with similar vector representations have qualitatively
similar appearances.

HOMOGLYPH shares common elements with EfficientOCR Carlson et al. (2023), an
OCR architecture that learns to recognize characters by contrastively training
on character crops rendered with augmented digital fonts. Different
augmentations of a character provide positive examples. At inference time,
localized characters are OCR’ed by retrieving their nearest neighbor from an
index of exemplary character embeddings. The OCR application of contrastive
learning on character renders aims to retrieve the same character in an
offline index, whereas HOMOGLYPH measures similarity across characters. While
HOMOGLYPH shares the architecture of the EfficientOCR character recognizer, it
does not use the same model weights or training data as EffOCR (which does not
support Chinese or Korean and is also trained on labeled crops from historical
documents).

###  2.2 String Matching Methods

Dunn (1946) \- in one of the first treatments of record linkage - wrote: “Each
person in the world creates a Book of Life. This Book starts with birth and
ends with death. Its pages are made up of the records of the principal events
in life. Record linkage is the name given to the process of assembling the
pages of this Book into a volume.”

Edit distance metrics are widely used for this task e.g. Levenshtein et al.
(1966); Jaro (1989); Winkler (1990). Another common approach computes the
cosine similarity between $n$-gram representations of strings Okazaki and
Tsujii (2010).

There are a variety of ways that character-level visual similarity could be
incorporated into record linkage. We follow the literature modifying
Levenshtein distance, e.g. Novosad (2018), by using cosine distance in the
HOMOGLYPH space as the substitution cost. Insertion and deletion costs are set
to one. It is straightforward to scale the insertion and deletion costs using
parameters estimated on a validation set, but we focus on performance without
any tuned parameters to maintain a purely off-the-shelf, self-supervised
implementation.

We compare matching with homoglyphic edit distance to a variety of other
methods. The first comparison is to classic Levenshtein distance (insertions,
deletions, and substitutions are all equally costly), to isolate the effect of
varying the substitution cost. We also compare to the popular Simstring
package, which uses a variety of similarity metrics (Jaccard, cosine, and Dice
similarity), computed with 2-gram substrings Okazaki and Tsujii (2010). The
third comparison is to FuzzyChinese, a widely used package that uses strokes
or characters as the fundamental unit for n-gram substring representations (we
use the default 3-grams). These are compared using the TF-IDF vectors. The
strokes in each character are drawn from an external database kfcd (2015)
covering a subset of the CJK script.

##  3 Evaluation Datasets

To our knowledge, there are not widely used benchmarks for evaluating record
linkage for the CJK script. Hence, we develop evaluation data. First, we link
a dataset on the customers and suppliers of major Japanese firms, drawn from a
1956 Japanese firm publication Jinji Koshinjo (1954), to a firm index of
around 7,000 firms. The index is from the same publication but written in a
different font. Supply chains are fundamental to the transmission of economic
shocks Acemoglu et al. (2016, 2012), agglomeration Ellison et al. (2010), and
economic development Hirschman (1958); Myrdal and Sitohang (1957); Rasmussen
(1956); Bartelme and Gorodnichenko (2015); Lane (2022). Supply chains are
challenging to study historically, as they require accurate record linkage.
This makes them a particularly relevant test case for downstream applications.

Firm names are localized with LayoutParser Shen et al. (2021) and then OCR’ed
twice, to shed light on whether errors tend to be homoglyphic in popular
vision-only OCR and vision-language sequence-to-sequence OCR. We employ two
widely used, open-source OCR engines: PaddleOCR and EasyOCR. EasyOCR uses a
convolutional recurrent neural network (CRNN) Shi et al. (2016), with learned
embeddings from a vision model serving as inputs to a learned language model.
PaddleOCR abandons language modeling, dividing text images into small patches,
using mixing blocks to perceive inter- and intra-character patterns, and
recognizing text by linear prediction Du et al. (2022). Neither engine
localizes individual characters.

In a second exercise, we use the dataset examined in Arora et al. (2023),
which links the same customer-supplier list to a firm directory containing
over 70,000 firms Teikoku Koshinjo (1957). Examining this dataset allows a
comparison of string matching methods to the OCR-free vision only methods and
multimodal methods from Arora et al. (2023). This dataset was created with
EfficientOCR Carlson et al. (2023) and cannot be re-created with EasyOCR or
PaddleOCR because the directory is written vertically, which these engines do
not support. We would expect EfficientOCR’s character retrieval framework to
make homoglyphic errors. Performance across datasets created by three highly
diverse OCR architectures is important to extensibility, since database
collections have also been constructed with diverse OCR architectures.

Because creating ground truth data for record linkage is costly, we use
synthetically generated data for a third set of evaluations. We render place
and firm names using different digital fonts and image augmentations,
conducting separate experiments for Traditional Chinese, Simplified Chinese,
Japanese, and Korean. For Simplified Chinese, Japanese, and Korean, we draw
placenames from the Geonames database Geonames (2023). Because Traditional
Chinese placenames in Geonames are rare, we instead draw from a list of
Taiwanese firms, as Taiwan - unlike Mainland China - still uses Traditional
Chinese Taiwan Ministry of Economic Affairs (2023). We randomly select two
image crops of each entity name, and OCR them using EasyOCR and PaddleOCR.
Anywhere from 40% (Simplified Chinese) to 88% (Traditional Chinese) of OCR’ed
string pairs differ between the two OCR engines. We limit the evaluation
dataset to pairs where the two string representations differ.222The sample
size is 20,162 for Simplified Chinese, 66,943 for Traditional Chinese, 86,470
for Japanese, and 48,809 for Korean.

##  4 Results

| OCR Engines
---|---
Method | Paddle | Easy | Paddle | Easy
| to Easy | to Paddle | to Paddle | to Easy
Homoglyphic | 0.808 | 0.753 | 0.844 | 0.728
distance |  |  |  |
Levenshtein | 0.766 | 0.697 | 0.807 | 0.693
distance |  |  |  |
Simstring | 0.762 | 0.662 | 0.787 | 0.673
(cosine) |  |  |  |
Simstring | 0.763 | 0.663 | 0.788 | 0.673
(dice) |  |  |  |
Simstring | 0.763 | 0.663 | 0.788 | 0.673
(jaccard) |  |  |  |
FuzzyChinese | 0.690 | 0.567 | 0.717 | 0.554
(stroke) |  |  |  |
FuzzyChinese | 0.533 | 0.445 | 0.559 | 0.464
(character) |  |  |  |

Table 1: Baseline Matching Results: Historical Japanese Data. This table
reports accuracy using a variety of different methods for linking Japanese
firms from supply chain records to a horizontally written firm directory. The
four columns report results when (1) PaddleOCR is used to OCR the firm list
and EasyOCR the directory, (2) EasyOCR is used to OCR the firm list and
PaddleOCR the directory, (3) PaddleOCR is used to OCR both lists, (4) EasyOCR
is used to OCR both lists.

Homoglyphic edit distance outperforms the other string matching methods in all
three evaluation exercises - across different OCR engines and languages -
typically by an appreciable margin. This illustrates that homoglyphic errors
in OCR are common and can be captured with self-supervised vision
transformers.

Our first evaluation exercise - with linked Japanese supply chain data - aims
to elucidate whether homoglyphic matching is as helpful for linking datasets
created with vision-language OCR as for linking datasets created with vision-
only OCR, and whether it can similarly be useful for linking datasets created
with different OCR architectures. We hence separately consider results linking
PaddleOCR’ed customers and suppliers to the EasyOCR’ed firm index, vice versa,
as well as linking when both are OCR’ed by either PaddleOCR or EasyOCR.
Homoglyphic edit distance outperforms other string matching methods and does
so by a similar margin (around 4 percentage points higher accuracy) regardless
of the OCR architecture used. FuzzyChinese has the weakest performance, as
expected, since many Japanese characters are not covered in their stroke
dictionary.

Method | Accuracy
---|---
Panel A: String-Matching
Homoglyphic distance | 0.824
Levenshtein distance | 0.731
Simstring (cosine) | 0.748
Simstring (dice) | 0.752
Simstring (jaccard) | 0.752
FuzzyChinese (stroke) | 0.735
FuzzyChinese (character) | 0.618
Panel B: Neural Methods
Self-Supervised Multimodal Linking | 0.849
Supervised Vision-Only Linking | 0.878
Supervised Multimodal Linking | 0.945

Table 2: Comparisons to fully neural record linkage methods: This table links
Japanese firms from supply chain records to an extensive firm directory.
String matching methods are reported in Panel A. End-to-end neural methods are
reported in Panel B.

The primary objective of our second evaluation is to compare homoglyphic
matching to the OCR-free vision-only and end-to-end multimodal frameworks
developed in Arora et al. (2023), using customer-supplier data linked to an
extensive index of 70K Japanese firms. Homoglyphic distance outperforms all
other string matching methods, with a matching accuracy of 82%. The Arora et
al. (2023) self-supervised multimodal record linkage model - which employs
language-image contrastive pre-training on firm image crop-OCR text pairs
(following Radford et al. (2021)) - outperforms homoglyphic distance, with 85%
matching accuracy. The supervised multimodal model outperforms by a wider
margin (95% accuracy). These methods avoid the OCR information bottleneck by
using crops from the original document images. Moreover, the language model
can understand different ways of writing the same firm name (e.g., using
different terms for corporation).

The Arora et al. (2023) supervised vision-only approach, which contrastively
trains different views of the same firm’s image crops to have similar
representations, also outperforms homoglyphic matching (88% accuracy). While
homoglyphs do not fully eliminate the OCR information bottleneck, they do
significantly reduce it relative to widely used string matching methods (e.g.
75% accuracy with the Simstring package), with the advantage of not requiring
labeled data or image crops.

|  |  | Simplified | Traditional
---|---|---|---|---
| Japanese | Korean | Chinese | Chinese
Homoglyphic | 0.456 | 0.292 | 0.476 | 0.465
distance |  |  |  |
Levenshtein | 0.396 | 0.188 | 0.375 | 0.407
distance |  |  |  |
Simstring | 0.376 | 0.247 | 0.425 | 0.383
(cosine) |  |  |  |
Simstring | 0.380 | 0.248 | 0.426 | 0.385
(dice) |  |  |  |
Simstring | 0.380 | 0.248 | 0.426 | 0.385
(jaccard) |  |  |  |
FuzzyChinese | 0.168 | 0.000 | 0.473 | 0.372
(stroke) |  |  |  |
FuzzyChinese | 0.230 | 0.110 | 0.137 | 0.197
(character) |  |  |  |

Table 3: Matching Results: Synthetic Data. This table reports accuracy linking
synthetic paired data generated by OCR’ing location and firm names - rendered
with augmented digital fonts - with two different OCR engines.

HOMOGLYPH complements end-to-end deep neural methods. The Arora et al. (2023)
methods cannot be used when researchers lack access to the original document
images. Moreover, researchers often lack the compute or technical requirements
to work with image data, whereas the vast majority of quantitative social
science researchers are comfortable processing strings. On the language side,
there are many contexts where using a language model may contribute little.
Person or location names - for instance - don’t contain much natural language
relative to firm names. String matching methods remain the most widely used
because they are simple and cheap to use off-the-shelf, and there are contexts
where more sophisticated methods may not be feasible or offer large
incremental gains. HOMOGLYPH is an extensible way to improve string matching
when linking OCR’ed datasets.

Figure 3: Error analysis. Panel A shows representative errors from homoglyphic
matching. Panel B shows representative cases that homoglyphic matching gets
correct. The ground truth string is shown in column (1). PaddleOCR is used to
OCR the query images (column (2)) and EasyOCR is used to OCR their
corresponding keys (column (3)). Columns (4) through (7) give the selected
match to the query using different string matching methods, with the correct
match shown in column (3). Bold characters differ from the query.

Finally, Table 3 reports results with the synthetically generated record
linkage dataset, to elucidate the performance of homoglyphic matching across
languages using the CJK script. Homoglyphs outperform other string matching
methods. The only case where the performance of another method is similar is
Simplified Chinese, where the FuzzyChinese package using stroke level
$n$-grams performs similarly. The stroke dictionary that underlies
FuzzyChinese was crafted for Simplified Chinese, yet homoglyphs can perform
similarly with self-supervised methods. On Traditional Chinese, which
proliferates in historical documents, homoglyphic edit distance offers a nine
percentage point accuracy advantage over FuzzyChinese, illustrating the
extensibility advantages of self-supervised methods. The accuracy rates are
rather low, but this must be interpreted in the context of the dataset, which
only includes paired records where the OCR differs.

Figure 3 provides an error analysis for the synthetic record linkage exercise.
The ground truth string is shown in the first column, PaddleOCR is used to OCR
the query (column 2) and EasyOCR is used to OCR the key and provides the
correct match (column 3). The matches selected from the key by different
string matching methods are shown in columns (4) through (7).

Panel A shows cases where homoglyphic edit distance selects an incorrect
match. This typically occurs when the OCR’ed text has a similar visual
appearance to another firm in the index, showing the limits of homoglyphs to
fully close the OCR information bottleneck. Panel B shows cases where
homoglyphic edit distance selects a correct match, avoiding the wrong strings
chosen by other methods through exploiting character visual similarity.

##  5 Extending Homoglyphs

While this study focuses on the modern CJK script, HOMOGLYPH can be extended
to any character set. As a proof of concept, we explore its extensibility to
ancient Chinese characters. Like other early forms of human writing, ancient
Chinese scripts are highly pictorial relative to modern characters.

Using an existing database of grouped ancient characters from different
archaeological sites and periods that correspond to the same concept Academia
Sinica et al. (2023), we contrastively learn a metric space where the
representations of different views of ancient characters denoting the same
concept are nearby. We train on 25,984 character views, as well as the
corresponding modern augmented fonts. The dataset includes characters from the
Shang Dynasty (1600 BC-1045 BC), the Western Zhou (1045 BC-771 BC), the Spring
and Autumn Warring States Era (770 BBC -221 BC), and the Qin-Han Dynasties
(221BC - circa third century).333We exclude images from the Shuowen Jiezi - a
book on ancient characters - limiting to the most reliable character renders,
which were drawn from archaeological sites. To illustrate homoglyphs, we
create a reference set for the Shang Dynasty, randomly choosing one character
for each concept.

Figure 4 shows representative examples of homoglyphs, consisting of a
character and its five nearest neighbors. The modern character descendant -
taken from the database - as well as a short description of the ancient
concept are provided. The description draws upon Li (2012) as well.

Figure 4: Ancient Homoglyphs. This figure shows homoglyph sets constructed for
ancient Chinese, with the descendant modern Chinese character and a
description of the character’s ancient meaning.

The homoglyph sets are able to capture related abstract concepts noted in the
archaeological literature. The first line shows that the concepts of writing,
law, learning, and morning (“recording the sun”) are homoglyphs, and the
second line shows that characters for different types of officials are
homoglyphs, as are characters denoting “joining.” The final line shows that
history and government official are homoglyphs - underscoring the central role
of the government in constituting history - as are characters denoting
conquest, tying up, and city center (denoted by a prisoner to be executed by
the government, which occurred in the city center).

Not all concepts within each set are related, but many of the connections
above have been noted in an archaeological literature examining how ancient
peoples conceptualized the world (e.g. Wang (2003)). That these meanings can
be captured using vision transformers is a fascinating illustration of the
relationship between images, written language, and meaning in ancient
societies.

##  6 Limitations

Using homoglyphs for string matching inherits the well-known limitations of
string matching. In some cases, OCR destroys too much information for record
linkage to be feasible with the resulting strings. Even with clean OCR,
sometimes language understanding is necessary to determine the correct match.
Homoglyphs do not address other types of string substitutions, like those that
result from enumerator misspellings, although in principle a similar
contrastive approach could also be developed to quantify other types of string
substitutions.

More sophisticated methods have been developed as alternatives to string
matching. For example, Ventura et al. (2015) use a random forest classifier
trained on labeled data to disambiguate authors of U.S. patents, applying
clustering to the resulting dissimilarity scores to enforce transitivity.
Arora et al. (2023) use multimodal methods that combine the image crops of
entities and their OCR and also develop a vision-only OCR free linkage method.
Bayesian methods have also been used, e.g. Sadinle (2014, 2017). They offer
the advantage of uncertainty quantification - another well-known limitation of
string matching - but do not scale well.

While these methods can offer advantages, they are not always applicable.
Researchers may lack access to the original document images, or may lack the
compute or technical resources to process images, limiting the use of OCR-free
or multimodal approaches. Language models are unlikely to be useful in linking
individual names, a common application. Labeled data may be infeasibly costly
to create at a sufficient scale for training supervised models. Finally,
researchers in disciplines like social science often lack familiarity with
machine learning methods, but most are familiar with off-the-shelf string
matching packages. String matching methods are also cheap to scale to massive
datasets. Simple string matching algorithms are often preferred by
practitioners and can be the most suitable tool given the constraints.

##  7 Conclusion

Homoglyphic edit distance significantly improves string matching accuracy on
OCR’ed documents, by integrating information about character similarity from
purely self-supervised vision transformers. It can be implemented using a
simple, off-the-shelf string matching package.444Package available at
https://pypi.org/project/HomoglyphsCJK/. Learning homoglyphs through self-
supervised vision transformers is hhighly extensible, including to low
resource settings and settings with many characters. By improving record
linkage in such settings - where handcrafted features used to improve record
linkage are not available - research on important questions requiring linked
data can become more representative of the diversity of human societies.

## Supplementary Materials

##  S-1 HOMOGLYPH Model Details

###  S-1.1 Encoder

For both of our applications, we use a DINO pre-trained Caron et al. (2021)
vision transformer (ViT) as the encoder. Our implementation of the ViT comes
from the Pytorch Image Models library (timm) Wightman (2019). Specifically, we
use the vit_base_patch16_224.dino model that corresponds to the official DINO-
pretained ViT-base model with a patch size of 16 and with input resolution of
$224^{2}$. The pretrained checkpoint does not have a classification head.

###  S-1.2 Loss function

We use Supervised Contrastive loss Khosla et al. (2020) as our training
objective, as implemented in the PyTorch Metric Learning library Musgrave et
al. (2020), where the temperature parameter is set to 0.1.

###  S-1.3 Data Augmentation

We deploy several image augmentations, using transformations provided in the
Torchvision library TorchVision (2016). These include Affine transformation
(only slight translation and scaling allowed), Random Color Jitter, Random
Autocontrast, Random Gaussian Blurring, and Random Grayscale. Additionally, we
pad the character to make the image square while preserving the aspect ratio
of the character render. We do not use common augmentations like Random
Cropping or Center Cropping, to avoid destroying too much information.

For augmenting the skeleton of the rendered character itself, we use a variety
of digital fonts to render the images. We use 27 fonts for Simplified Chinese,
17 fonts for Traditional Chinese (for both string matching and ancient
Chinese), 62 fonts for Korean, and 14 fonts for Japanese.

##  S-2 Application-specific details

###  S-2.1 Record Linkage

####  S-2.1.1 Data

For each script, the dataset consists of images of characters from the
corresponding script rendered with different fonts and augmented during
training. The number of characters for each script seen during training is
given in Table S-1. Each character can be considered a "class" to which its
digital renders belong. Characters do not need to be seen during training to
be considered at inference time, an advantage if users wish to expand the
homoglpyph sets (e.g. because an OCR engine uses a different character set).
We illustrate this empirically by expanding the character set to characters
covered by the three OCR engines we explore that were not included in our
character ranges used initially for training.

Script | Training | Inference
---|---|---
Japanese | 17,963 | 17,963
Simplified Chinese | 6,621 | 7,806
Traditional Chinese | 8,415 | 8,628
Korean | 3,686 | 3,729
Total | 36,685 | 38,126
Table S-1: Training and Inference Sizes. This table shows the training and
inference sizes for different language scripts.

####  S-2.1.2 Batching

Without hard-negative mining

Let $\mathcal{B}$ denote the batch size. A batch consists of $m$ views of
$\dfrac{\mathcal{B}}{m}$ classes sampled without replacement. When all the
views for a class are utilized, all images are replaced and the sampling
process without replacement starts again. “Views” of a character are augmented
digital renders using the fonts and transformations described above.

One training epoch is defined as seeing all characters and their m views
exactly once.

With hard-negative mining
We find $k$ nearest neighbors of each character (or class) on a checkpoint
trained without hard negatives. We do this by rendering all characters with a
“reference font - Noto Serif CJK font (Tc/Sc/Jp/Ko)” depending upon the script
and finding $k$ nearest neighbors using the above checkpoint.

We create batches as before, but this time, randomly intersperse all hard
negative sets (of size k) in the batches.

One training epoch is now defined as seeing all characters and their m views
and additionally, all characters and their hard negative sets (composed of
$k-1$ neighbors) and their m views exactly once.

Table S-2 contains the number of epochs we trained each model for.

Model | lr | weight decay | T_0 | T_mult | Epochs
---|---|---|---|---|---
Japanese - (No HN) | 2e-5 | 5e-3 | 1 | 2 | 100
distance |  |  |  |  |
Japanese - (HN) | 2e-5 | 5e-3 | 1 | 2 | 30
distance |  |  |  |  |
Simplified Chinese - (No HN) | 2e-5 | 5e-3 | 1 | 2 | 30
distance |  |  |  |  |
Simplified Chinese - (HN) | 2e-5 | 5e-3 | 1 | 2 | 30
distance |  |  |  |  |
Traditional Chinese - (No HN) | 2e-5 | 5e-3 | 1 | 2 | 30
distance |  |  |  |  |
Traditional Chinese - (HN) | 2e-5 | 5e-3 | 1 | 2 | 30
distance |  |  |  |  |
Korean - (No HN) | 2e-5 | 5e-3 | 1 | 2 | 60
distance |  |  |  |  |
Korean - (HN) | 2e-5 | 5e-3 | 1 | 2 | 30
distance |  |  |  |  |
Ancient Chinese - (No HN) | 2e-5 | 5e-3 | 300 | 1 | 200
distance |  |  |  |  |
Ancient Chinese - (HN) | 2e-5 | 5e-3 | 300 | 3 | 24
distance |  |  |  |  |

Table S-2: Training Hyperparameters. This table reports the training
hyperparameters used for the models. The lr stands for learning rate, weight
decay represents the weight decay factor, T_0 is the number of steps until the
first restart of the learning rate scheduler, T_mult denotes the factor by
which T_0 is multiplied at each restart, and Epochs indicates the total number
of training epochs. Parameters not mentioned here use PyTorch defaults. HN
denotes offline hard-negative mining.

####  S-2.1.3 Model Validation

We split the characters into an 80-10-10 train-val-test set. We embed the
validation images and find the nearest neighbor among the embeddings of
digital renders of the universe of characters in the script, rendered with the
reference font described above. The top-1 retrieval accuracy is used as the
validation metric for the selection of the best checkpoint. We see a peak
validation accuracy of 90% for Japanese, 98% for Korean, 91% for Traditional
Chinese, and 91% for Simplified Chinese.

####  S-2.1.4 Other training details

CJK glyphs are similar across the scripts. To converge faster, for the rest of
the languages, we initialize the weights of the encoder with the checkpoint
used for the HOMOGLYPH encoder for Japanese - the script with the largest
number of characters. We use AdamW Loshchilov and Hutter (2019) as the
optimizer and Cosine Annealing with Warm Restarts Loshchilov and Hutter (2016)
as the learning rate schedule. We use the standard Pytorch implementation for
both. The relevant hyperparameters are listed in Table S-2. We stop training
the models once the validation accuracy stagnates and the checkpoint with the
best validation accuracy is chosen as the encoder for each script.

###  S-2.2 Homoglyph Sets

We allow for the expansion of the character set beyond what is seen in
training because different OCR engines use different character dictionaries (a
list of characters supported by the engine). We take the union of characters
from the character dictionaries of PaddleOCR, EasyOCR, and EfficientOCR. For
each script, we render all its characters using the script’s reference font
and embed them using the script-specific HOMOGLYPH encoder. For each
character, we then find 800-nearest neighbours (measured by Cosine Similarity
between the embeddings) among the set of all renders in the reference set. We
store these as a look-up dictionary that contains, for each character in a
script, its 800 neighbors and its Cosine Similarity with all of them. This
look-up dictionary is used in our modified Levenshtein distance implementation
to modify the substitution cost. The dictionaries are available in our GitHub
repository Yang et al. (2023).

Table S-1 contains the number of characters that were used to prepare these
sets for each script.

###  S-2.3 Implementing the Modified Levenshtein distance

We use a standard algorithm to calculate Levenshtein distance that uses
dynamic programming Wagner and Fischer (1974). The space and time complexity
of the algorithm is $\mathcal{O}(mn)$ where $m$ and $n$ are the lengths of the
two strings that are being compared.

We modify this algorithm by switching the standard substitution cost $\lambda$
between two characters $a$ and $b$ with
$\lambda*(1-CosineSimilarity(u(a),u(b))$. Here $u(a)$ and $u(b)$ are the
embeddings of the HOMOGLYPH encoder for the script to which $a$ and $b$
belong. $\lambda$ is a tunable hyperparameter but for simplicity, we fix it as
1 for the results shown in the paper. We also fixed the addition and deletion
cost as 1 but in the implementation provided in our package and our GitHub
repository, the costs are tunable hyperparameters.

###  S-2.4 Ancient Chinese Homoglyphs

####  S-2.4.1 Data

The source database Academia Sinica et al. (2023) from which we collect the
ancient Chinese character crops contains 5,024 concepts, comprised of 25,984
character renderings. Each of these concepts is mapped to a modern character.
This enables us to insert digital renders of these modern characters using the
same fonts as above (for traditional Chinese) to create more variation. A
"class" in this case comprises a character cluster - with both ancient crops
and modern digital renders forming the positive samples for a class.

We slightly modify the data augmentation scheme for this application to
account for the wide variation in writing styles across centuries. We allow
for a slight ($-10$ to $+10$ degree) rotation and also add more
transformations tailored to this use case - Random Equalize, Random Posterize,
Random Solarize, Random Inversion and Random Erase (randomly erase 0-5% of the
image). We apply all augmentations to the digital renders but only apply
Random Affine transformation and Random Inversion to the ancient crops.

####  S-2.4.2 Batching

We use the same sampling and batching process as we did for the modern
homoglyph models. The only difference is in how the hard-negative sets are
defined. Instead of one nearest neighbor per concept, for each ancient crop
within a concept cluster, we find $k$ nearest neighbors. This gives us as many
nearest neighbor sets (hard-negative sets) as ancient crops in our dataset.
This allows us to account for the fact that the homoglyphs of a character may
differ across different historical periods, spanning millennia.

####  S-2.4.3 Model Validation

We split the character clusters into train and validation sets (90-10). We
then transfer modern renders of the characters from the validation set to the
train set. After this, we randomly transfer 50% of validation images to
training. Only ancient characters remain in the validation set. We then make a
reference set by embedding all the modern renders of our character (using the
reference font Noto Serif CJK Tc). We use top-1 accuracy as our validation
metric which is defined as the proportion of correct retrievals of the
corresponding modern render to each ancient image in the validation set.
During training, the model reached a peak validation accuracy of 50%
demonstrating the difficult nature of this task. We use this metric for
selecting the best checkpoint for our encoder.

####  S-2.4.4 Other training details

We again use the AdamW optimizer and Cosine Annealing with Warm Restarts as
the learning rate schedule. Relevant Hyperparameters are listed in Table S-2.
We stop training when validation accuracy stagnates.

####  S-2.4.5 Creation of Ancient Chinese Homoglyphs

The creation of homolgyph sets is analogous to the case of modern characters.
Instead of using digital renders from a particular font as the "reference
set", we look at the five nearest neighbors of ancient characters within a
period. We illustrate homoglyphs using The Shang Dynasty period (1600 BC-1045
BC), the most ancient.

## References

  * Abramitzky et al. (2021) Ran Abramitzky, Leah Boustan, Katherine Eriksson, James Feigenbaum, and Santiago Pérez. 2021.  Automated linking of historical data.  _Journal of Economic Literature_ , 59(3):865–918.
  * Academia Sinica et al. (2023) Institute of History Academia Sinica, Philology, and Institute of Information Science Academia Sinica. 2023.  Xiaoxuetang yanbian database.
  * Acemoglu et al. (2016) Daron Acemoglu, Ufuk Akcigit, and William Kerr. 2016.  Networks and the macroeconomy: An empirical exploration.  _Nber macroeconomics annual_ , 30(1):273–335.
  * Acemoglu et al. (2012) Daron Acemoglu, Vasco M Carvalho, Asuman Ozdaglar, and Alireza Tahbaz-Salehi. 2012\.  The network origins of aggregate fluctuations.  _Econometrica_ , 80(5):1977–2016.
  * Arora et al. (2023) Abhishek Arora, Xinmei Yang, Shao Yu Jheng, and Melissa Dell. 2023.  Linking representations with multimodal contrastive learning.  _arXiv preprint arXiv:2304.03464_.
  * Bartelme and Gorodnichenko (2015) Dominick Bartelme and Yuriy Gorodnichenko. 2015.  Linkages and economic development.  Technical report, National Bureau of Economic Research.
  * Binette and Steorts (2022) Olivier Binette and Rebecca C Steorts. 2022.  (almost) all of entity resolution.  _Science Advances_ , 8(12):eabi8021.
  * Carlson et al. (2023) Jacob Carlson, Tom Bryan, and Melissa Dell. 2023.  Efficient ocr for building a diverse digital history.  _arXiv preprint arXiv:2304.02737_.
  * Caron et al. (2021) Mathilde Caron, Hugo Touvron, Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski, and Armand Joulin. 2021.  Emerging properties in self-supervised vision transformers.  _arXiv preprint arXiv:2104.14294_.
  * Chen and He (2021) Xinlei Chen and Kaiming He. 2021.  Exploring simple siamese representation learning.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 15750–15758.
  * Chen et al. (2021) Xinlei Chen, Saining Xie, and Kaiming He. 2021.  An empirical study of training self-supervised vision transformers.  _arXiv preprint arXiv:2104.02057_.
  * Du et al. (2022) Yongkun Du, Zhineng Chen, Caiyan Jia, Xiaoting Yin, Tianlun Zheng, Chenxia Li, Yuning Du, and Yu-Gang Jiang. 2022.  Svtr: Scene text recognition with a single visual model.  _arXiv preprint arXiv:2205.00159_.
  * Dunn (1946) Halbert L Dunn. 1946.  Record linkage.  _American Journal of Public Health and the Nations Health_ , 36(12):1412–1416.
  * Ellison et al. (2010) Glenn Ellison, Edward L Glaeser, and William R Kerr. 2010.  What causes industry agglomeration? evidence from coagglomeration patterns.  _American Economic Review_ , 100(3):1195–1213.
  * Geonames (2023) Geonames. 2023.  Geonames.
  * Grill et al. (2020) Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre H Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Daniel Guo, Mohammad Gheshlaghi Azar, et al. 2020.  Bootstrap your own latent: A new approach to self-supervised learning.  _arXiv preprint arXiv:2006.07733_.
  * Hirschman (1958) Albert O Hirschman. 1958.  _The strategy of economic development._ Yale Univ. Press, New Haven, Conn.
  * Jaro (1989) Matthew A Jaro. 1989.  Advances in record-linkage methodology as applied to matching the 1985 census of tampa, florida.  _Journal of the American Statistical Association_ , 84(406):414–420.
  * Jinji Koshinjo (1954) Jinji Koshinjo. 1954.  _Nihon shokuinrokj_.  Jinji Koshinjo.
  * Johnson et al. (2019) Jeff Johnson, Matthijs Douze, and Hervé Jégou. 2019.  Billion-scale similarity search with gpus.  _IEEE Transactions on Big Data_ , 7(3):535–547.
  * kfcd (2015) kfcd. 2015.  chaizi.  https://github.com/kfcd/chaizi.
  * Khosla et al. (2020) Prannay Khosla, Piotr Teterwak, Chen Wang, Aaron Sarna, Yonglong Tian, Phillip Isola, Aaron Maschinot, Ce Liu, and Dilip Krishnan. 2020.  Supervised contrastive learning.  _arXiv preprint arXiv:2004.11362_.
  * Lane (2022) Nathan Lane. 2022.  Manufacturing revolutions: Industrial policy and industrialization in south korea.  _Available at SSRN 3890311_.
  * Levenshtein et al. (1966) Vladimir I Levenshtein et al. 1966.  Binary codes capable of correcting deletions, insertions, and reversals.  In _Soviet physics doklady_ , volume 10, pages 707–710. Soviet Union.
  * Li (2012) Xueqin Li, editor. 2012.  _Zi Yun (The Origin of Characters)_.  Tianjin Ancient Works Publishing House, Tianjin.
  * Loshchilov and Hutter (2016) Ilya Loshchilov and Frank Hutter. 2016.  SGDR: stochastic gradient descent with restarts.  _CoRR_ , abs/1608.03983.
  * Loshchilov and Hutter (2019) Ilya Loshchilov and Frank Hutter. 2019.  Decoupled weight decay regularization.
  * Lyu et al. (2021) Lijun Lyu, Maria Koutraki, Martin Krickl, and Besnik Fetahu. 2021.  Neural ocr post-hoc correction of historical corpora.  _Transactions of the Association for Computational Linguistics_ , 9:479–483.
  * Musgrave et al. (2020) Kevin Musgrave, Serge Belongie, and Ser-Nam Lim. 2020.  Pytorch metric learning.
  * Myrdal and Sitohang (1957) Gunnar Myrdal and Paul Sitohang. 1957.  Economic theory and under-developed regions.  _Regional Studies_.
  * Nguyen et al. (2021) Thi Tuyet Hai Nguyen, Adam Jatowt, Mickael Coustaty, and Antoine Doucet. 2021.  Survey of post-ocr processing approaches.  _ACM Comput. Surv._ , 54(6).
  * Novosad (2018) Paul Novosad. 2018.  Masala merge.  https://github.com/paulnov/masala-merge.
  * Okazaki and Tsujii (2010) Naoaki Okazaki and Jun’ichi Tsujii. 2010.  Simple and efficient algorithm for approximate dictionary matching.  In _Proceedings of the 23rd International Conference on Computational Linguistics (Coling 2010)_ , pages 851–859.
  * Oord et al. (2018) Aaron van den Oord, Yazhe Li, and Oriol Vinyals. 2018.  Representation learning with contrastive predictive coding.  _arXiv preprint arXiv:1807.03748_.
  * Radford et al. (2021) Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. 2021.  Learning transferable visual models from natural language supervision.  In _International Conference on Machine Learning_ , pages 8748–8763. PMLR.
  * Rasmussen (1956) Poul Nørregaard Rasmussen. 1956.  _Studies in inter-sectoral relations_ , volume 15.  E. Harck.
  * Sadinle (2014) Mauricio Sadinle. 2014.  Detecting duplicates in a homicide registry using a bayesian partitioning approach.  _The Annals of Applied Statistics_ , 8(4):2404–2434.
  * Sadinle (2017) Mauricio Sadinle. 2017.  Bayesian estimation of bipartite matchings for record linkage.  _Journal of the American Statistical Association_ , 112(518):600–612.
  * Shen et al. (2021) Zejiang Shen, Ruochen Zhang, Melissa Dell, Benjamin Charles Germain Lee, Jacob Carlson, and Weining Li. 2021.  Layoutparser: A unified toolkit for deep learning based document image analysis.  _International Conference on Document Analysis and Recognition_ , 12821\.
  * Shi et al. (2016) Baoguang Shi, Xiang Bai, and Cong Yao. 2016.  An end-to-end trainable neural network for image-based sequence recognition and its application to scene text recognition.  _IEEE transactions on pattern analysis and machine intelligence_ , 39(11):2298–2304.
  * Silbert (1970) Jeffrey M Silbert. 1970.  The world’s first computerized criminal-justice information-sharing system-the new york state identification and intelligence system (nysiis).  _Criminology_ , 8:107.
  * Simpson et al. (2013) Ian C Simpson, Petroula Mousikou, Juan Manuel Montoya, and Sylvia Defior. 2013.  A letter visual-similarity matrix for latin-based alphabets.  _Behavior research methods_ , 45:431–439.
  * Taiwan Ministry of Economic Affairs (2023) Taiwan Ministry of Economic Affairs. 2023.  Registered factory directory.
  * Teikoku Koshinjo (1957) Teikoku Koshinjo. 1957.  _Teikoku Ginko Kaisha Yoroku_.  Teikoku Koshinjo.
  * TorchVision (2016) TorchVision. 2016.  Torchvision: Pytorch’s computer vision library.  https://github.com/pytorch/vision.
  * van Strien. et al. (2020) Daniel van Strien., Kaspar Beelen., Mariona Coll Ardanuy., Kasra Hosseini., Barbara McGillivray., and Giovanni Colavizza. 2020.  Assessing the impact of ocr quality on downstream nlp tasks.  In _Proceedings of the 12th International Conference on Agents and Artificial Intelligence - Volume 1: ARTIDIGH,_ , pages 484–496. INSTICC, SciTePress.
  * Ventura et al. (2015) Samuel L Ventura, Rebecca Nugent, and Erica RH Fuchs. 2015.  Seeing the non-stars:(some) sources of bias in past disambiguation approaches and a new public tool leveraging labeled records.  _Research Policy_ , 44(9):1672–1701.
  * Wagner and Fischer (1974) Robert A. Wagner and Michael J. Fischer. 1974.  The string-to-string correction problem.  _J. ACM_ , 21(1):168–173.
  * Wang (2003) Guowei Wang. 2003.  Shishi (deciphering "history").  In _Guantan Gjilin_. Hebei Education Publishing House, Shijiazhuang.
  * Wightman (2019) Ross Wightman. 2019.  Pytorch image models.  https://github.com/rwightman/pytorch-image-models.
  * Winkler (1990) William E Winkler. 1990.  _String comparator metrics and enhanced decision rules in the Fellegi-Sunter model of record linkage._ ERIC.
  * Yang et al. (2023) Xinmei Yang, Abhishek Arora, Shao-Yu Jheng, and Melissa Dell. 2023.  Codebase for quantifying character similarity with vision transformers.  https://github.com/dell-research-harvard/Quantifying-Character-Similarity.
  * znwang25 (2020) znwang25. 2020.  fuzzychinese.  https://github.com/znwang25/fuzzychinese.


* Pecora et al. (2019) Pecora, F., Pucci, F., Lapenta, G., Burgess, D., & Servidio, S. 2019, Sol. Phys., 294, 114, doi: 10.1007/s11207-019-1507-6
  * Pekünlü et al. (2002) Pekünlü, E. R., Bozkurt, Z., Afsar, M., Soydugan, E., & Soydugan, F. 2002, MNRAS, 336, 1195, doi: 10.1046/j.1365-8711.2002.05849.x
  * Pereira et al. (2012) Pereira, T. M. D., De Pontieu, B., & Carlsson, M. 2012, ApJ, 759, 18, doi: 10.1088/0004-637X/759/1/18
  * Pereira et al. (2014) Pereira, T. M. D., De Pontieu, B., Carlsson, M., et al. 2014, ApJ, 792, L15, doi: 10.1088/2041-8205/792/1/L15
  * Perez & Chandran (2013) Perez, J. C., & Chandran, B. D. G. 2013, ApJ, 776, 124, doi: 10.1088/0004-637X/776/2/124
  * Pezzi et al. (2019) Pezzi, O., Perrone, D., Servidio, S., et al. 2019, ApJ, 887, 208, doi: 10.3847/1538-4357/ab5285
  * Prasad et al. (2021) Prasad, A., Srivastava, A. K., & Wang, T. J. 2021, Sol. Phys., 296, 20, doi: 10.1007/s11207-021-01764-x
  * Provornikova et al. (2018) Provornikova, E., Ofman, L., & Wang, T. 2018, Advances in Space Research, 61, 645, doi: 10.1016/j.asr.2017.07.042
  * Raouafi & Stenborg (2014) Raouafi, N. E., & Stenborg, G. 2014, ApJ, 787, 118, doi: 10.1088/0004-637X/787/2/118
  * Raymond et al. (2014) Raymond, J. C., McCauley, P. I., Cranmer, S. R., & Downs, C. 2014, ApJ, 788, 152, doi: 10.1088/0004-637X/788/2/152
  * Rempel (2014) Rempel, M. 2014, ApJ, 789, 132, doi: 10.1088/0004-637X/789/2/132
  * Roberts (2010) Roberts, D. A. 2010, ApJ, 711, 1044, doi: 10.1088/0004-637X/711/2/1044
  * Roberts & Ofman (2019) Roberts, D. A., & Ofman, L. 2019, Sol. Phys., 294, 153, doi: 10.1007/s11207-019-1548-x
  * Rouppe van der Voort et al. (2015) Rouppe van der Voort, L., De Pontieu, B., Pereira, T. M. D., Carlsson, M., & Hansteen, V. 2015, ApJ, 799, L3, doi: 10.1088/2041-8205/799/1/L3
  * Sagdeev & Galeev (1969) Sagdeev, R. Z., & Galeev, A. A. 1969, Nonlinear Plasma Theory
  * Sakao et al. (2007) Sakao, T., Kano, R., Narukage, N., et al. 2007, Science, 318, 1585, doi: 10.1126/science.1147292
  * Samanta et al. (2015) Samanta, T., Pant, V., & Banerjee, D. 2015, ApJ, 815, L16, doi: 10.1088/2041-8205/815/1/L16
  * Samanta et al. (2018) Samanta, T., Tian, H., & Prasad Choudhary, D. 2018, ApJ, 859, 158, doi: 10.3847/1538-4357/aabf37
  * Samanta et al. (2019) Samanta, T., Tian, H., Yurchyshyn, V., et al. 2019, Science, 366, 890, doi: 10.1126/science.aaw2796
  * Sarkar et al. (2016) Sarkar, S., Pant, V., Srivastava, A. K., & Banerjee, D. 2016, Sol. Phys., 291, 3269, doi: 10.1007/s11207-016-1019-6
  * Sharma et al. (2020) Sharma, A., Tripathi, D., Erdélyi, R., Gupta, G. R., & Ahmed, G. A. 2020, A&A, 638, A6, doi: 10.1051/0004-6361/201936667
  * Shoda et al. (2019) Shoda, M., Suzuki, T. K., Asgari-Targhi, M., & Yokoyama, T. 2019, ApJ, 880, L2, doi: 10.3847/2041-8213/ab2b45
  * Shoda & Yokoyama (2016) Shoda, M., & Yokoyama, T. 2016, ApJ, 820, 123, doi: 10.3847/0004-637X/820/2/123
  * Shoda & Yokoyama (2018) —. 2018, ApJ, 859, L17, doi: 10.3847/2041-8213/aac50c
  * Shoda et al. (2018) Shoda, M., Yokoyama, T., & Suzuki, T. K. 2018, ApJ, 853, 190, doi: 10.3847/1538-4357/aaa3e1
  * Sigalotti et al. (2007) Sigalotti, L. D. G., Mendoza-Briceño, C. A., & Luna-Cardozo, M. 2007, Sol. Phys., 246, 187, doi: 10.1007/s11207-007-9077-4
  * Singh et al. (2011) Singh, J., Hasan, S. S., Gupta, G. R., Nagaraju, K., & Banerjee, D. 2011, Sol. Phys., 270, 213, doi: 10.1007/s11207-011-9732-7
  * Singh et al. (2002) Singh, J., Sakurai, T., Ichimoto, K., Suematsu, Y., & Takeda, A. 2002, PASJ, 54, 793, doi: 10.1093/pasj/54.5.793
  * Soler et al. (2011) Soler, R., Terradas, J., Verth, G., & Goossens, M. 2011, ApJ, 736, 10, doi: 10.1088/0004-637X/736/1/10
  * Srivastava et al. (2017) Srivastava, A. K., Shetye, J., Murawski, K., et al. 2017, Scientific Reports, 7, 43147, doi: 10.1038/srep43147
  * Stein (1967) Stein, R. F. 1967, Sol. Phys., 2, 385, doi: 10.1007/BF00146490
  * Straus et al. (2015) Straus, T., Fleck, B., & Andretta, V. 2015, A&A, 582, A116, doi: 10.1051/0004-6361/201525805
  * Su (2014) Su, J. T. 2014, ApJ, 793, 117, doi: 10.1088/0004-637X/793/2/117
  * Su et al. (2012) Su, J. T., Liu, Y., Shen, Y. D., Liu, S., & Mao, X. J. 2012, ApJ, 760, 82, doi: 10.1088/0004-637X/760/1/82
  * Sych & Nakariakov (2014) Sych, R., & Nakariakov, V. M. 2014, A&A, 569, A72, doi: 10.1051/0004-6361/201424049
  * Sych et al. (2009) Sych, R., Nakariakov, V. M., Karlicky, M., & Anfinogentov, S. 2009, A&A, 505, 791, doi: 10.1051/0004-6361/200912132
  * Sych et al. (2020) Sych, R., Zhugzhda, Y., & Yan, X. 2020, ApJ, 888, 84, doi: 10.3847/1538-4357/ab5a78
  * Terradas et al. (2010) Terradas, J., Goossens, M., & Verth, G. 2010, A&A, 524, A23, doi: 10.1051/0004-6361/201014845
  * Thurgood et al. (2014) Thurgood, J. O., Morton, R. J., & McLaughlin, J. A. 2014, ApJ, 790, L2, doi: 10.1088/2041-8205/790/1/L2
  * Tian et al. (2021) Tian, H., Harra, L., Baker, D., Brooks, D. H., & Xia, L. 2021, Sol. Phys., 296, 47, doi: 10.1007/s11207-021-01792-7
  * Tian et al. (2011a) Tian, H., McIntosh, S. W., & De Pontieu, B. 2011a, ApJ, 727, L37, doi: 10.1088/2041-8205/727/2/L37
  * Tian et al. (2011b) Tian, H., McIntosh, S. W., De Pontieu, B., et al. 2011b, ApJ, 738, 18, doi: 10.1088/0004-637X/738/1/18
  * Tian et al. (2011c) Tian, H., McIntosh, S. W., Habbal, S. R., & He, J. 2011c, ApJ, 736, 130, doi: 10.1088/0004-637X/736/2/130
  * Tian et al. (2012) Tian, H., McIntosh, S. W., Wang, T., et al. 2012, ApJ, 759, 144, doi: 10.1088/0004-637X/759/2/144
  * Tian et al. (2014) Tian, H., DeLuca, E. E., Cranmer, S. R., et al. 2014, Science, 346, 1255711, doi: 10.1126/science.1255711
  * Tiwari et al. (2019) Tiwari, A. K., Morton, R. J., Régnier, S., & McLaughlin, J. A. 2019, ApJ, 876, 106, doi: 10.3847/1538-4357/ab164b
  * Tomczyk & McIntosh (2009) Tomczyk, S., & McIntosh, S. W. 2009, ApJ, 697, 1384, doi: 10.1088/0004-637X/697/2/1384
  * Tomczyk et al. (2007) Tomczyk, S., McIntosh, S. W., Keil, S. L., et al. 2007, Science, 317, 1192, doi: 10.1126/science.1143304
  * Ugarte-Urra & Warren (2011) Ugarte-Urra, I., & Warren, H. P. 2011, ApJ, 730, 37, doi: 10.1088/0004-637X/730/1/37
  * van Ballegooijen & Asgari-Targhi (2016) van Ballegooijen, A. A., & Asgari-Targhi, M. 2016, ApJ, 821, 106, doi: 10.3847/0004-637X/821/2/106
  * van Ballegooijen & Asgari-Targhi (2017) —. 2017, ApJ, 835, 10, doi: 10.3847/1538-4357/835/1/10
  * Van Doorsselaere et al. (2016) Van Doorsselaere, T., Antolin, P., Yuan, D., Reznikova, V., & Magyar, N. 2016, Frontiers in Astronomy and Space Sciences, 3, 4, doi: 10.3389/fspas.2016.00004
  * Van Doorsselaere et al. (2020a) Van Doorsselaere, T., Li, B., Goossens, M., Hnat, B., & Magyar, N. 2020a, ApJ, 899, 100, doi: 10.3847/1538-4357/aba0b8
  * Van Doorsselaere et al. (2008) Van Doorsselaere, T., Nakariakov, V. M., & Verwichte, E. 2008, ApJ, 676, L73, doi: 10.1086/587029
  * Van Doorsselaere et al. (2011) Van Doorsselaere, T., Wardle, N., Del Zanna, G., et al. 2011, ApJ, 727, L32, doi: 10.1088/2041-8205/727/2/L32
  * Van Doorsselaere et al. (2020b) Van Doorsselaere, T., Srivastava, A. K., Antolin, P., et al. 2020b, Space Sci. Rev., 216, 140, doi: 10.1007/s11214-020-00770-y
  * Velli (1993) Velli, M. 1993, A&A, 270, 304
  * Verdini et al. (2019) Verdini, A., Grappin, R., & Montagud-Camps, V. 2019, Sol. Phys., 294, 65, doi: 10.1007/s11207-019-1458-y
  * Verdini et al. (2010) Verdini, A., Velli, M., Matthaeus, W. H., Oughton, S., & Dmitruk, P. 2010, ApJ, 708, L116, doi: 10.1088/2041-8205/708/2/L116
  * Verth et al. (2010) Verth, G., Terradas, J., & Goossens, M. 2010, ApJ, 718, L102, doi: 10.1088/2041-8205/718/2/L102
  * Verwichte et al. (2010) Verwichte, E., Marsh, M., Foullon, C., et al. 2010, ApJ, 724, L194, doi: 10.1088/2041-8205/724/2/L194
  * Wang et al. (2018a) Wang, F., Deng, H., Li, B., et al. 2018a, ApJ, 856, L16, doi: 10.3847/2041-8213/aab4f3
  * Wang (2011) Wang, T. 2011, Space Sci. Rev., 158, 397, doi: 10.1007/s11214-010-9716-1
  * Wang et al. (2007) Wang, T., Innes, D. E., & Qiu, J. 2007, ApJ, 656, 598, doi: 10.1086/510424
  * Wang & Ofman (2019) Wang, T., & Ofman, L. 2019, ApJ, 886, 2, doi: 10.3847/1538-4357/ab478f
  * Wang et al. (2012) Wang, T., Ofman, L., & Davila, J. M. 2012, in Astronomical Society of the Pacific Conference Series, Vol. 456, Fifth Hinode Science Meeting, ed. L. Golub, I. De Moortel, & T. Shimizu, 91
  * Wang et al. (2013) Wang, T., Ofman, L., & Davila, J. M. 2013, ApJ, 775, L23, doi: 10.1088/2041-8205/775/1/L23
  * Wang et al. (2015) Wang, T., Ofman, L., Sun, X., Provornikova, E., & Davila, J. M. 2015, ApJ, 811, L13, doi: 10.1088/2041-8205/811/1/L13
  * Wang et al. (2018b) Wang, T., Ofman, L., Sun, X., Solanki, S. K., & Davila, J. M. 2018b, ApJ, 860, 107, doi: 10.3847/1538-4357/aac38a
  * Wang et al. (2021) Wang, T., Ofman, L., Yuan, D., et al. 2021, Space Sci. Rev., 217, 34, doi: 10.1007/s11214-021-00811-0
  * Wang (2016) Wang, T. J. 2016, Washington DC American Geophysical Union Geophysical Monograph Series, 216, 395, doi: 10.1002/9781119055006.ch23
  * Wang et al. (2009) Wang, T. J., Ofman, L., Davila, J. M., & Mariska, J. T. 2009, A&A, 503, L25, doi: 10.1051/0004-6361/200912534
  * Weberg et al. (2018) Weberg, M. J., Morton, R. J., & McLaughlin, J. A. 2018, ApJ, 852, 57, doi: 10.3847/1538-4357/aa9e4a
  * Weberg et al. (2020) —. 2020, ApJ, 894, 79, doi: 10.3847/1538-4357/ab7c59
  * Withbroe (1988) Withbroe, G. L. 1988, ApJ, 325, 442, doi: 10.1086/166015
  * Yang et al. (2020a) Yang, Z., Tian, H., Tomczyk, S., et al. 2020a, Science China Technological Sciences, 63, 2357, doi: 10.1007/s11431-020-1706-9
  * Yang et al. (2020b) Yang, Z., Bethge, C., Tian, H., et al. 2020b, Science, 369, 694, doi: 10.1126/science.abb4462
  * Yuan et al. (2011) Yuan, D., Nakariakov, V. M., Chorley, N., & Foullon, C. 2011, A&A, 533, A116, doi: 10.1051/0004-6361/201116933
  * Yuan et al. (2016) Yuan, D., Su, J., Jiao, F., & Walsh, R. W. 2016, ApJS, 224, 30, doi: 10.3847/0067-0049/224/2/30
  * Yuan et al. (2014) Yuan, D., Sych, R., Reznikova, V. E., & Nakariakov, V. M. 2014, A&A, 561, A19, doi: 10.1051/0004-6361/201220208
  * Yurchyshyn et al. (2012) Yurchyshyn, V., Kilcik, A., & Abramenko, V. 2012, arXiv e-prints, arXiv:1207.6417.  https://arxiv.org/abs/1207.6417
  * Zavershinskii et al. (2019) Zavershinskii, D. I., Kolotkov, D. Y., Nakariakov, V. M., Molevich, N. E., & Ryashchikov, D. S. 2019, Physics of Plasmas, 26, 082113, doi: 10.1063/1.5115224
  * Zhao et al. (2016) Zhao, J., Felipe, T., Chen, R., & Khomenko, E. 2016, ApJ, 830, L17, doi: 10.3847/2041-8205/830/1/L17
  * Zhao et al. (2015) Zhao, J. S., Voitenko, Y., Guo, Y., Su, J. T., & Wu, D. J. 2015, ApJ, 811, 88, doi: 10.1088/0004-637X/811/2/88
  * Zhugzhda et al. (1983) Zhugzhda, I. D., Locans, V., & Staude, J. 1983, Sol. Phys., 82, 369, doi: 10.1007/BF00145575
  * Zhugzhda (1984) Zhugzhda, Y. D. 1984, Pisma v Astronomicheskii Zhurnal, 10, 51
  * Zhugzhda & Sych (2014) Zhugzhda, Y. D., & Sych, R. A. 2014, Astronomy Letters, 40, 576, doi: 10.1134/S1063773714090059
  * Zimovets & Nakariakov (2015) Zimovets, I. V., & Nakariakov, V. M. 2015, A&A, 577, A4, doi: 10.1051/0004-6361/201424960


# Factorials and powers, a minimality result, revisited

David E. Radford
Department of Mathematics, Statistics
and Computer Science (m/c 249)
851 South Morgan Street
University of Illinois at Chicago
Chicago, Illinois 60607-7045

###### Abstract

Let $a>1$. Then $a^{n}<n!$ for some positive integer $n$. There are several
numerical sequences associated with the study of the smallest such integer
which are studied in [2] and [3]. Here we continue the examination of one of
them.

††2020 Mathematics Subject Classification: 11B65, 05A10. Key words and
phrases: Factorials and powers.

##  0 Introduction

Let $a>1$ be a fixed real number. Then $a^{\ell}\leq\ell!$ for some positive
integer $\ell$. Let $n_{a}$ be the smallest such integer. Now
$\displaystyle{\frac{n}{e}<a\leq\frac{n+1}{e}}$ for some $n\geq 2$. Let
$\sigma_{n}$ be the largest integer $\ell$ such that $n+(\ell-1)\leq
e\sqrt[n]{n!}\;$. Then $n_{a}=n-\sigma_{n}+r$, where $r\in\\{1,2,3\\}$, by [2,
Theorem 3].

The sequence $\sigma_{1},\sigma_{2},\sigma_{3}\ldots\;$ is increasing and
seems to increase very slowly. For example, $\sigma_{n}=15$ when $n=10^{12}$.
This and other examples are found in the discussion at the end of [2, §6]. In
this paper we show how to narrow $\sigma_{n}$ to one of two possibilities when
$n\geq 4$ using very simple estimates. We also examine the growth rate of the
sequence.

##  1 A basic sequence associated with factorials

In this section we draw heavily from the material of [2]. First we describe
basic functions and some of the results found therein which are needed for
this paper.

Let $x>0$. These basic functions which we use here are the four

$L(x)=\displaystyle{\pi^{\frac{1}{2x}}}e^{\frac{1}{(12x+1)x}},\;\;R(x)=\pi^{\frac{1}{2x}}e^{\frac{1}{12x^{2}}},\;\;P(x)=x^{\frac{1}{x}},\;\;\mbox{and}\;\;T(x)=xP(x)$

which are positive valued and infinitely differentiable. For a function $F(x)$
set $a_{F}(x)=(F(x)-1)x$. Then $\displaystyle{F(x)=1+\frac{a_{F}(x)}{x}}$. It
is easy to see that $\lim_{x\,\longrightarrow\,\infty}F(x)=1$, where $F(x)$ is
any one of the first three of the four functions mentioned at the beginning of
this paragraph. For any one of these three, limit statement suggests that it
is natural to study $F(x)$ in terms of $a_{F}(x)$.

Let $n\geq 1$. An important estimate for us is Robbins’ improvement [4] on
Sterling’s approximation of factorials. It is equivalent to

$\frac{1}{2}L(n)T(2n)<e\sqrt[n]{n!}<\frac{1}{2}R(n)T(2n)$

which is (2) of [2]. The previous expression is a very minor reformulation of
Robbins’ result. The form of Robbins’ result most useful to us here is

$L(n)P(2n)<e\left(\frac{\sqrt[n]{n!}}{n}\right)<R(n)P(2n).$ (1)

The results of [2, §5] apply to the sequence $T_{1},T_{2},T_{3},\ldots\;$
whose terms are $T_{i}=e\sqrt[i]{i!}\;$ for all $i\geq 1$. Therefore, as
$\sigma_{1}=2$,

$2=\sigma_{1}\leq\sigma_{2}\leq\sigma_{3}\leq\cdots$ (2)

by [2, (26)] and

$\sigma_{i+1}=\sigma_{i}\;\;\ \mbox{or}\;\;\sigma_{i+1}=\sigma_{i}+1$ (3)

for all $i\geq 1$ by [2, (27)].

As $n+\sigma_{n}-1\leq e\sqrt[n]{n!}<n+\sigma_{n}$, it follows that

$\frac{\sigma_{n}}{n}-\frac{1}{n}\leq
e\left(\frac{\sqrt[n]{n!}}{n}\right)-1<\frac{\sigma_{n}}{n}.$

These inequalities yield

$L(n)P(2n)-1<\frac{\sigma_{n}}{n}<R(n)P(2n)-1+\frac{1}{n}$ (4)

by (1). Set ${\mathcal{L}}(x)=L(x)P(2x)$ and ${\mathcal{R}}(x)=L(x)P(2x)$.
Then (4) can be reformulated

$a_{{\mathcal{L}}(n)}<\sigma_{n}<a_{{\mathcal{R}}(n)}+1.$ (5)

For functions $f(x)$ and $g(x)$, note that

$\displaystyle{a_{fg}(x)=\frac{a_{f}(x)a_{g}(x)}{x}+a_{f}(x)+a_{g}(x)}=a_{f}(x)g(x)+a_{g}(x).$

Let $p(x)=P(2x)$. Then

$a_{\mathcal{L}}(x)-a_{p}(x)=a_{L}(x)P(2x),$ (6)
$a_{\mathcal{R}}(x)-a_{p}(x)=a_{R}(x)P(2x),$ (7)

and therefore

$a_{\mathcal{R}}(x)-a_{\mathcal{L}}(x)=(a_{R}(x)-a_{L}(x))P(2x).$ (8)

###### Lemma 1

Let $x>0$. Then:

  1. (a)

$a_{\mathcal{R}}(x)>a_{\mathcal{L}}(x)>a_{p}(x)>0$.

  2. (b)

$a_{\mathcal{L}}(x)-a_{p}(x)$ and $a_{\mathcal{R}}(x)-a_{p}(x)$ are strictly
decreasing functions on $[e/2,\infty)$.

  3. (c)

$\displaystyle{\lim_{x\,\longrightarrow\,\infty}(a_{\mathcal{L}}(x)-a_{p}(x))=\lim_{x\,\longrightarrow\,\infty}(a_{\mathcal{R}}(x)-a_{p}(x))=\frac{\ln\pi}{2}}$.

  4. (d)

$\lim_{x\,\longrightarrow\,\infty}(a_{\mathcal{R}}(x)-a_{\mathcal{L}}(x))=0$.

Proof: First of all $R(x)>L(x)>1$. This means $a_{R}(x)>a_{L}(x)>0$. Since
$p(x)>1$ also, part (a) follows by (6) and (8). Now $a_{L}(x)$ and $a_{R}(x)$
are strictly decreasing functions on $((\ln\pi/2),\infty)$ by [2, Proposition
2(a)]. It was shown in [2, §1] that $P(x)$ is strictly decreasing on
$[e,\infty)$. Part (b) now follows by (6) and (7). Since
$\lim_{x\,\longrightarrow\,\infty}a_{L}(x)=\lim_{x\,\longrightarrow\,\infty}a_{R}(x)=\displaystyle{\frac{\ln\pi}{2}}$,
which follows by [2, Proposition 2(b)], and
$\lim_{x\,\longrightarrow\,\infty}P(x)=1$, part (c) now follows by (6) and (7)
and part (d) by (8). $\Box$

Let $n_{1}<n_{2}<n_{3}<\ldots\;$ be the sequence defined by
$\sigma_{1}=\cdots=\sigma_{1}$ and
$\sigma_{n_{i}+1}=\sigma_{n_{i}}+1=\cdots=\sigma_{n_{i+1}}$ for $i\geq 1$.
Then $n_{1},n_{2},\ldots\;$ mark the positions in
$\sigma_{1},\sigma_{2},\sigma_{3},\ldots\;$ just before changes of term value.
We are interested in the ratio $\displaystyle{\frac{n_{i+1}}{n_{i}}}$.

Set $\delta(x)=a_{\mathcal{R}}(x)-a_{\mathcal{L}}(x)$, let $i\geq 1$, and set
$d(i)=\max\\{\delta(n_{i+1}),\delta(n_{i})\\}$. Then $d(i)>0$ by part (a) of
Lemma 1 and $\lim_{i\,\longrightarrow\,\infty}d(i)=0$ by part (d) of the same.
Let $c=\sigma_{n_{i+1}}=\sigma_{n_{i}}+1$. Then

$a_{\mathcal{L}}(n_{i})+1<c<a_{\mathcal{R}}(n_{i})+2\;\;\mbox{and}\;\;a_{\mathcal{L}}(n_{i+1})<c<a_{\mathcal{R}}(n_{i+1})+1$

by (5). Therefore
$|a_{\mathcal{L}}(n_{i+1})-(a_{\mathcal{L}}(n_{i})+1)|<d(i)$, or equivalently

$1-d(i)<a_{\mathcal{L}}(n_{i+1})-a_{\mathcal{L}}(n_{i})<1+d(i).$ (9)

Thus the sequence of positive terms
$a_{\mathcal{L}}(n_{1})<a_{\mathcal{L}}(n_{2})<a_{\mathcal{L}}(n_{3})<\ldots\;$
is eventually strictly increasing,

$\lim_{i\,\longrightarrow\,\infty}(a_{\mathcal{L}}(n_{i+1})-a_{\mathcal{L}}(n_{i}))=1,$
(10)

and thus

$\lim_{i\,\longrightarrow\,\infty}\left(\frac{a_{\mathcal{L}}(n_{i+1})}{a_{\mathcal{L}}(n_{i})}\right)=1.$
(11)

We find estimates for $a_{\mathcal{L}}(x)$ and $a_{\mathcal{R}}(x)$ which
connect them to $\ln(2x)$. At this point we assume
$\displaystyle{x\geq\frac{e}{2}}$. Set
$\displaystyle{\alpha=\frac{\ln\pi}{2}}$. Observe that
$\displaystyle{\frac{e}{2}>\alpha>\frac{1}{2}}$. Now
$\displaystyle{R(x)<1+\frac{1}{x}}$ for all $\displaystyle{x\geq\frac{e}{2}}$
by [2, Corollary 1] as $x>1$. Next we note
$\displaystyle{P(2x)<\frac{2x}{2x-\ln(2x)}=1+\frac{\ln(2x)}{2x-\ln(2x)}}$
which follows by [2, Lemma 1] as $2x>1$. Therefore

$R(x)P(2x)-1<\left(1+\frac{1}{x}\right)\left(1+\frac{\ln(2x)}{2x-\ln(2x)}\right)-1=\frac{2x+x\ln(2x)}{x(2x-\ln(2x))}$

which means that $a_{\mathcal{R}}(x)<\ln(2x)QR(x)$, where

$QR(x)=\left(\frac{2}{\ln(2x)}+1\right)\left(\frac{x}{2x-\ln(2x)}\right).$

Now $QR(x)$ is the product of two positive valued strictly decreasing
functions, since $\displaystyle{x>\frac{e}{2}}$; therefore $QR(x)$ is of the
same type. It is easy to see that
$\lim_{x\,\longrightarrow\,\infty}QR(x)=\displaystyle{\frac{1}{2}}$.

By parts (a) and (b) of [2, Proposition 2] it follows that
$\displaystyle{L(x)>1+\frac{\alpha}{x}}$, since $x>\alpha$, and by [2, Lemma
1] we have $\displaystyle{P(2x)>1+\frac{\ln(2x)}{2x}}$, since $2x>1$. One can
easily show that

$L(x)P(2x)-1>\frac{1}{x}\left(\alpha+\left(x+\alpha\right)\frac{\ln(2x)}{2x}\right)$

which means that $a_{\mathcal{L}}(x)>\ln(2x)QL(x)$, where

$QL(x)=\frac{\alpha}{\ln(2x)}+\frac{1}{2}\left(1+\frac{\alpha}{x}\right).$

It is clear that $QL(x)$ is a positive valued strictly decreasing function,
since $2x>1$, and that
$\displaystyle{\lim_{x\,\longrightarrow\,\infty}QL(x)=\frac{1}{2}}$. We have
shown that

$\ln(2x)QL(x)<a_{\mathcal{L}}(x),a_{\mathcal{R}}(x)<\ln(2x)QR(x)$ (12)

Note that (5) and (12) imply

$\ln(2n)QL(n)<\sigma_{n}<\ln(2n)QR(n)+1$ (13)

for all $n\geq 2$. We consider the difference between these estimates for
$\sigma_{n}$ by examining the difference between $\ln(2x)QR(x)$ and
$\ln(2x)QR(x)$. Let $D(x)=\ln(2x)QR(x)-\ln(2x)QL(x)$. Since

$\ln(2x)QR(x)=\frac{2x+x\ln(2x)}{2x-\ln(2x)}=1+\frac{(1+x)\ln(2x)}{2x-\ln(2x)}$
(14)

and

$\ln(2x)QL(x)=\alpha+\ln(2x)\left(\frac{x+\alpha}{2x}\right),$ (15)

it follows that

$D(x)=(1-\alpha)\left(\frac{2x}{2x-\ln(2x)}\right)+\left(\frac{x+\alpha}{2x-\ln(2x)}\right)\left(\frac{\ln(2x)}{\sqrt{2x}}\right)^{2}.$

Since $\displaystyle{\lim_{x\,\longrightarrow\,\infty}\frac{\ln x}{x^{a}}=0}$
for all $a>0$, we have
$\displaystyle{\lim_{x\,\longrightarrow\,\infty}D(x)=1-\frac{\ln\pi}{2}}$.
Observe that the parenthesized quotients in the preceding equation for $D(x)$
are all positive valued functions on $[e/2,\infty)$, the first two strictly
decreasing there and the third on $[e^{2}/2,\infty)$, and finally that
$1-\alpha>0$. Collecting results:

###### Proposition 1

Let $QL(x)$, $QR(x)$, and $D(x)$ be defined on $[e/2,\infty)$ as above. They
are positive valued and:

  1. (a)

$QL(x)$ and $QR(x)$ strictly decreasing on $[e/2,\infty)$ and $D(x)$ is
strictly decreasing on $[e^{2}/2,\infty)$.

  2. (b)

$\displaystyle{\lim_{x\,\longrightarrow\,\infty}QL(x)=\lim_{x\,\longrightarrow\,\infty}QR(x)=\frac{1}{2}}$

  3. (c)

$\displaystyle{\lim_{x\,\longrightarrow\,\infty}D(x)=1-\frac{\ln\pi}{2}}$.

$\Box$

###### Corollary 1

For $D(x)$, $QL(n)$, and $QR(n)$:

  1. (a)

$D(x)<1$ for all $x\geq 3.92466$.

  2. (b)

Let $n\geq 4$. Then there are at most two integers $\ell$ in the open interval
$(\ln(2n)QL(n),\;\ln(2n)QR(n)+1)$ and the integer $\sigma_{n}$ is such an
$\ell$.

$\Box$

Proof: One can show $D(3.92465)>1>D(3.92466)$ and $3.92466>e^{2}/2$. Thus part
(a) follows by parts (a) and (c) Proposition 1. As for part (b), note that the
difference between $\ln(2n)QR(n)+1$ and $\ln(2n)QL(n)$ is $D(n)+1$. Thus if
$n\geq 4$ then $D(n)+1<2$ by part (a). At this point (12) completes the proof
of part (b). $\Box$

Apropos of part (a) of Corollary 1, as $0.57236<1-\alpha<0.57237$, it follows
that $1.57236<D(x)+1<2$ for all $x\geq 3.92466$. Thus the length of the
interval of part (b) is greater than $1.57236$ and less than $2$. By part (a)
of Proposition 1, the length of the interval
$[a_{{\mathcal{L}}(n)},\;a_{{\mathcal{R}}(n)}+1]$ is greater than $1$. This
interval, implicit in (5), is contained in the one of part (b) by (12); thus
its length is less than $2$ when $n\geq 4$.

We examine how frequently increase in term value occurs in the sequence
$\sigma_{1},\sigma_{2},\sigma_{3},\ldots\;$. Recall its properties described
in (2) and (3). Note that value increase occurs infinitely often since
$\lim_{x\,\longrightarrow\,\infty}\sigma_{n}=\infty$ by (13) and that
$\displaystyle{\lim_{x\,\longrightarrow\,\infty}QL(x)=\frac{1}{2}}$.

Let $i\geq 1$. Set $n(i)=n_{i+1}-n_{i}$. Then

$\sigma_{n_{i+1}+1}=\sigma_{n_{i+1}+1}=\sigma_{n_{i+1}}+1=\sigma_{n_{i}}+2.$

Therefore

$\ln(2n_{i})QL(n_{i})+2<\sigma_{n_{i}}+2<\ln(2(n_{i+1}+1))QR(n_{i+1}+1)+1$

by (13). This means

$\ln(2n_{i})QL(n_{i})+1<\ln(2(n_{i+1}+1))QR(n_{i+1}+1)$ (16)

or

$\ln(2n_{i})QL(n_{i})<F(n_{i+1}+1),$ (17)

where

$F(x)=(1+x)\left(\frac{\ln(2x)}{2x-\ln(2x)}\right)$

for $x>0$, by (14).

At this point we assume $x\geq 1/2$. When $y=\ln(2x)$ then $y\geq 0$ and
$e^{y}=2x$. From this point on we assume $y\geq 0$. Let

$G(y)=\left(1+\frac{e^{y}}{2}\right)\left(\frac{y}{e^{y}-y}\right)=\frac{1}{2}\left(\frac{2y+ye^{y}}{e^{y}-y}\right).$

Then $F(x)=G(\ln(2x))$. Observe that

$\lim_{y\,\longrightarrow\,\infty}(G(y)-\frac{1}{2}y)=0$ (18)

and

$G^{\prime}(y)=\frac{e^{y}GN(y)}{2(e^{y}-y)^{2}},$

where $GN(y)=e^{y}-(y^{2}+2y-2)$. By considering the first, second, and third
derivatives of $GN(y)$ one can show that $GN(y)$ is strictly increasing on
$[y_{0},\infty)$, where $1.67834<y_{0}<1.67845=r$. As $QN(r)>0$, it follows
that $F(x)$ is strictly increasing on $[e^{r}/2,\infty)$. Note that
$2.6784>e^{r}/2$.

We return to (17) and consider $\ln(2x)QL(x)$ in terms of $y=\ln(2x)$ as we
did $F(x)$. Let

$H(y)=\alpha\left(1+\frac{y}{e^{y}}\right)+\frac{y}{2}=\frac{1}{2}\left(\frac{(\ln\pi)(y+e^{y})+ye^{y}}{e^{y}}\right).$

Then $\ln(2x)QL(x)=H(\ln(2x))$. Observe that

$\lim_{y\,\longrightarrow\,\infty}(H(y)-\frac{1}{2}(y+\ln\pi))=0$ (19)

and

$H^{\prime}(y)=\frac{1}{2}\left(\frac{e^{y}-y+1}{e^{y}}\right).$

It is easy to see that $H(y)$ is strictly increasing on $[0,\infty)$.

Observe that

$\lim_{y\,\longrightarrow\,\infty}(G(y+a)-H(y))=\displaystyle{\frac{1}{2}\left(a-\ln\pi\right)})$
(20)

follows by (18) and (19). We examine (20) in detail when $a\geq 0$.

Let $z=y+a$ as a matter of convenience for calculations. Then $e^{z}=Ae^{y}$,
where $A=e^{a}$. It is not hard to see that

$G(z)-H(y)=\frac{1}{2}\left(\frac{A(a-\ln\pi)e^{2y}+B(a,y)e^{y}+C(a,y)}{(e^{z}-z)e^{y}}\right),$

where

$B(a,y)=y^{2}+(2+a+(\ln\pi)(1-A))y+a(2+\ln\pi)$

and

$C(a,y)=y(y+a)(\ln\pi).$

Since $B(a,y)$ and $C(a,y)$ are quadratics whose graphs open upward, for some
$c>0$ it follows that $B(a,y)$, $C(a,y)>0$ for all $y\geq c$. Hence if
$a\geq\ln\pi$ then $G(y+a)-H(y)>0$ for $y\geq c$.

Suppose $a<\ln\pi$. Then $G(y+a)-H(y)<0$ eventually. Observe that
$G(y+a)-H(y)<0$ if and only if

$\frac{B(a,y)}{e^{y}}+\frac{C(a,y)}{e^{2y}}<A(\ln\pi-a).$ (21)

Now $0\leq a<\ln\pi$ by assumption. Therefore $1\leq A<\pi$. We replace
$B(a,y)$ and $C(a,y)$ by over estimates
$B_{0}(y)=y^{2}+(2+\ln\pi)y+(\ln\pi)(2+\ln\pi)$ and
$C_{0}(y)=y(y+\ln\pi)(\ln\pi)$ respectively. Therefore(21) holds for $y$ if

$\frac{B_{0}(y)}{e^{y}}+\frac{C_{0}(y)}{e^{2y}}<A(\ln\pi-a).$ (22)

Let $\ell$ be a non-negative and let $m$ be a positive integer. Then
$\displaystyle{\frac{y^{\ell}}{e^{my}}}$ is strictly decreasing on
$\displaystyle{[\frac{\ell}{m},\infty)}$. Hence the left hand side of the
inequality of (22) is a strictly decreasing function on $[2,\infty)$.
Therefore if $c\geq 2$ and (22) holds for $y=c$ then (21) holds for all $y\geq
c$.

Let $a=\ln 3$. Then $0<a<\ln\pi$. One can show that (22) does not hold for
$y=6.06520$ and does hold for $y=6.06521$. Consequently (21) holds for all
$y\geq 6.06521$ when $a=\ln 3$; hence

$G(y+\ln 3)<H(y)$ (23)

for all $y\geq 6.06521$ and, as $215.30654<e^{6.06521}/2<215.30655$, we have
shown that

$F(3x)<\ln(2x)QL(x)$ (24)

for all $x\geq 215.30655$. Therefore

$F(3n_{i})<\ln(2n_{i})QL(n_{i})<F(n_{i+1}+1)$ (25)

for all $n_{i}\geq 216$. Assume $n_{i}$ satisfies the preceding inequality.
Since $F(x)$ is strictly increasing on $[2.7684,\infty)$, it follows that
$3n_{i}<n_{i+1}+1$ and therefore $3n_{i}\leq n_{i+1}$.

Using (1) one can show that $\sigma_{1}=\cdots=\sigma_{3}=2$,
$\sigma_{4}=\cdots=\sigma_{54}=3$, $\sigma_{55}=\cdots=\sigma_{458}=4$,
$\sigma_{459}=\cdots=\sigma_{3480}=5$, and
$\sigma_{3481}=\cdots=\sigma_{25867}=6$, and
$\sigma_{25868}=\cdots=\sigma_{191351}=7$, and $\sigma_{191352}=8$. Thus
$n_{1}=3$, $n_{2}=54$, $n_{3}=458$, $n_{4}=3480$, $n_{5}=25867$, and
$n_{6}=191351$. Observe that

We have shown in particular that:

###### Corollary 2

$3n_{i}\leq n_{i+1}$, in particular $\displaystyle{\frac{n_{i+1}}{n_{i}}\geq
3}$, for all $i\geq 1$. $\Box$

There is an interesting relationship between [2, Proposition 3] and the
corollary. Let $n\geq 1$ and $S_{n}=T_{n+1}-T_{n}$, where
$T_{n}=e\sqrt[n]{n!}\;$ is defined just after (1). Write
$\displaystyle{S_{n}=1+\frac{a(n)}{n}}$. Then
$\displaystyle{\lim_{n\,\longrightarrow\,\infty}a(n)=\frac{1}{2}}$ by [3,
Theorem 1(d)]. Let $\displaystyle{a=\frac{1}{2}}$. Suppose that
$\displaystyle{S_{n}<1+\frac{a}{n}}$ for all $n\geq 1$. If this is the case
then [2, Proposition 3] implies Corollary 2 as well.

We end this paper with comments about the sequence
$n_{1},n_{2},n_{3},\ldots\;\;$. First of all

$\sigma_{n_{\ell}}=\ell+1$ (26)

for all $\ell\geq 1$, which follows by induction on $\ell$. Suppose that
$n\geq 4$ and set $\sigma_{n}=\ell+1$. Then $\sigma_{n}=\sigma_{n_{\ell}}$ by
(26). Thus $\ell\geq 2$, as $n\geq 4$, and therefore $n>n_{\ell-1}$ as
$\sigma_{n}>\sigma_{n_{\ell-1}}$. On closer scrutiny the quotients
$\displaystyle{\frac{n_{i+1}}{n_{i}}}$ seem to form a nice pattern. A few
calculations

$\displaystyle{\frac{n_{2}}{n_{1}}=18},\;\;\displaystyle{8.48<\frac{n_{3}}{n_{2}}<8.49},\;\;\displaystyle{7.59<\frac{n_{4}}{n_{3}}<7.6},$
$\displaystyle{7.43<\frac{n_{5}}{n_{4}}<7.44},\;\;\mbox{and}\;\;\displaystyle{7.39<\frac{n_{6}}{n_{5}}<7.40}$

suggest

###### Conjecture 1

The sequence
$\displaystyle{\frac{n_{2}}{n_{1}},\frac{n_{3}}{n_{2}},\frac{n_{4}}{n_{3}},\ldots\;}$
of quotients is strictly decreasing and
$\displaystyle{\lim_{n\,\longrightarrow\,\infty}\frac{n_{i+1}}{n_{i}}=e^{2}}$.

## References

  * [1] Mathworks, Inc. (2020). MATLAB R2020b _www.mathworks.com_
  * [2] Radford, David E. (2021). Factorials and powers, a minimality result, _preprint_ pp. 1–22.
  * [3] Radford, David E. (2021). The gamma function and a certain sequence of differences, _preprint_ pp. 1–14.
  * [4] Robbins, Herbert (1955). A Remark on Sterling’s Formula, _The American Mathematical Monthly_ 62, pp. 26–29.