# Semantic Segmentation in Multiple Adverse Weather Conditions
with Domain Knowledge Retention

Xin Yang1, Wending Yan2, Yuan Yuan2, Michael Bi Mi2, Robby T. Tan1

###### Abstract

Semantic segmentation’s performance is often compromised when applied to
unlabeled adverse weather conditions. Unsupervised domain adaptation is a
potential approach to enhancing the model’s adaptability and robustness to
adverse weather. However, existing methods encounter difficulties when
sequentially adapting the model to multiple unlabeled adverse weather
conditions. They struggle to acquire new knowledge while also retaining
previously learned knowledge. To address these problems, we propose a semantic
segmentation method for multiple adverse weather conditions that incorporates
adaptive knowledge acquisition, pseudo-label blending, and weather composition
replay. Our adaptive knowledge acquisition enables the model to avoid learning
from extreme images that could potentially cause the model to forget. In our
approach of blending pseudo-labels, we not only utilize the current model but
also integrate the previously learned model into the ongoing learning process.
This collaboration between the current teacher and the previous model enhances
the robustness of the pseudo-labels for the current target. Our weather
composition replay mechanism allows the model to continuously refine its
previously learned weather information while simultaneously learning from the
new target domain. Our method consistently outperforms the state-of-the-art
methods, and obtains the best performance with averaged mIoU (%) of 65.7 and
the lowest forgetting (%) of 3.6 against 60.1 and 11.3 (Hoyer et al. 2023), on
the ACDC datsets for a four-target continual multi-target domain adaptation.

## Introduction

Image MIC on T1 $\rightarrow$ T1 after T2 $\rightarrow$ T1 after T3

Ground Truth  Ours on T1 $\rightarrow$ T1 after T2 $\rightarrow$ T1 after T3

Figure 1:  The illustration of our method, where the model adapts to each
target domain sequentially. MIC (Hoyer et al. 2023) fails to retain previously
learned knowledge, as its performance on the first target gradually
deteriorates, e.g., the sky and the side walk in Target 1 are disappearing
after the method learns Targets 2 and 3. Our method retain previously learned
knowledge while adapting to new targets.

Semantic segmentation methods face challenges in adverse weather conditions,
as these conditions significantly degrade images. Adapting models to multiple
adverse weather conditions in an unsupervised and successive manner causes
additional difficulties due to substantial domain gaps among various weather
conditions, and potentially leads to forgetting previously learned knowledge.

Continual unsupervised domain adaptation emerges as a potential solution to
address these challenges by adapting the model from the labeled source domain
to the unlabeled target domains in a sequential manner, e.g., ((Lin et al.
2022; Saporta et al. 2022)). However, these methods are designed to acquire
all information from the new target, without considering whether this
information might lead to a forgetting of previously learned knowledge.
Moreover, as mentioned in (Kalb and Beyerer 2023), domain shifts across
distinct adverse weather conditions are primarily induced by the deteriorated
information within low-level features extracted from the early convolutional
layers. Consequently, there is a necessity to develop a method that takes this
factor into consideration to effectively address the challenges posed by
adverse weather conditions in domain adaptation.

In this paper, we present a semantic segmentation method that sequentially
adapts the model to multiple unlabeled adverse weather domains, by
progressively learning a new domain at a time while retaining the previous
learned knowledge. Our method conceives three novel concepts: adaptive
knowledge acquisition, pseudo-label blending, and weather composition replay.

In contrast to single-target unsupervised domain adaptation, our sequential
domain adaptation aims to both learn from the new target and retain previously
acquired knowledge simultaneously. Because of this, our model needs to
identify potentially detrimental input regions that could introduce
significant domain gaps and lead to forgetting of previously learned knowledge
(Yang et al. 2022a; Kalb and Beyerer 2023). To achieve this, we introduce
adaptive knowledge acquisition by utilizing the previous model and class-wise
feature representations, resulting in a dynamic weighting map. This dynamic
weighting map acts as a constraint, preventing the current model from learning
potentially detrimental areas.

Various adverse weather conditions may exhibit similar degradation effects
(Kalb and Beyerer 2023; Li et al. 2023). For instance, both fog and the rain
veiling effect visually look alike. Based on this similarity, models trained
under different adverse weather conditions can collaborate to enhance learning
from the shared degradation patterns (Allen-Zhu and Li 2020). Motivated by
this idea, we propose a pseudo-label blending strategy. This involves
employing the previous model as an auxiliary model to identify images from the
new target that share similarities with those from the past targets. We then
involve the auxiliary model (i.e., the previous model) to enhance our learning
process in an ensemble manner. Note that, since we use a teacher-student
framework, the term ”previous model” refers to the previous teacher.

When operating in a sequential manner, we do not assume accessibility to the
images from previously learned targets. In such a scenario, to maintain the
previously acquired knowledge, we introduce a replay technique that serves as
a continuous reminder of the weather degradation patterns encountered in the
past. To implement this, we retain the weather information acquired from
different targets in the previous steps, Once a new target is introduced, for
each target image, we randomly augment each of the past weather information
instances and integrate them into random segments of the current target
images. Through training on these composite images, the model sustains and
revises its comprehension of various weather degradations over time, even when
direct access to previously learned target domain images is unavailable. In a
summary, our contributions are as follows:

  * •

We present an adaptive knowledge acquisition method that guides the model to
refrain from learning new contents that could potentially result in
forgetting.

  * •

We introduce the concept of incorporating the previous model into the current
learning process to enhance our method’s overall performance in an ensemble
manner.

  * •

To retain the past weather information, we propose a continuous replay of
previously learned weather degradation, by randomly augmenting and integrating
it into the present target images.

Our method consistently outperforms the state-of-the-art methods, and obtains
the best performance with averaged mIoU (%) of 65.7 and the lowest forgetting
(%) of 3.6 against 60.1 and 11.3 (Hoyer et al. 2023), on the ACDC datsets for
a four-target continual multi-target domain adaptation.

## Related Work

Unsupervised domain adaptation (UDA) has been explored extensively in recent
years, with many applications ranging from different vision tasks (Ganin and
Lempitsky 2015; Chen et al. 2018, 2021; Vu et al. 2019; Saito et al. 2019; Zou
et al. 2018; Li, Yuan, and Vasconcelos 2019). However, UDA settings are
limited to one source and one target, meaning that the trained domain adaptive
model can only work on a certain target domain and will fail if more target
domains are involved. Hence, some researchers start to explore methods to
adapt a model into multiple target domains (Peng et al. 2019; Chen et al.
2019; Yu, Hu, and Chen 2018; Gholami et al. 2020; Nguyen-Meidine et al. 2021;
Yao et al. 2022; Roy et al. 2021).

(Isobe et al. 2021; Saporta et al. 2021; Lee et al. 2022) adapt the model into
multi-target domains in a parallel way, where all the target domains are
involved in every iteration. (Isobe et al. 2021) maintains an expert model for
each target domain, they are trained on many augmented images and teach a
common student model via a knowledge distillation loss. (Saporta et al. 2021)
proposes two MTDA methods, Multi-Dis and MTKT. For each target, Multi-Dis uses
two types of domain classifiers, a source vs. target classifier and a target
vs. all the other targets classifier. MTKT has a target domain-specific
decoder, and a corresponding target-specific domain classifier for each target
domain, the knowledge learned from different decoders is passed to a common
decoder with knowledge distillation. (Lee et al. 2022) disentangles the input
images into semantic contents and style contents, they obtain source images in
target styles by swapping the contents. The drawbacks of the parallel
approaches are, (1) They need additional modules/images for every target
domain in every iteration, and the real-time memory consumption could be a
bottleneck when the number of target domains becomes larger. (2) Similar to
the single-target UDA model, when a new target domain is introduced, there is
no way to update a pretrained model, and hence a new model will need to be
trained from scratch with all the targets.

(Saporta et al. 2022) proposes a continual way to adapt a model to multiple
target domains, where the target domains are adapted through multiple steps,
and the model can be updated at any time when a new target domain is
introduced. The paper also points out that due to this problem, the continual
approach usually performs worse than the parallel approach.

Replay has been proven effective in addressing this preserving previously
learned knowledge for adverse weather conditions (Kalb and Beyerer 2023).
Existing replay techniques including storing representative exemplar images
(Rebuffi et al. 2017; Hayes et al. 2020; Kang, Park, and Han 2022) and
adversarially generating images in the style of previous domains (Shin et al.
2017). However, the weather degradation is closely coupled to the image’s
physics properties (e.g., depth) (Sindagi et al. 2020; Hu et al. 2021; Yang et
al. 2022b; Li et al. 2023), so the degradation in each image is unique and it
is hard to identify a representative exemplar image. Moreover, generating
synthetic weather degradation is still an unsolved problem (Sakaridis, Dai,
and Van Gool 2018; Anoosheh et al. 2019), and there does not exist a solution
to continuously generate different adverse weather conditions.

Figure 2:  Our architecture for adapting a model to $n$ adverse weather
conditions in $n$ steps in a sequential manner. The architecture consists of
several key components: (1) Adaptive knowledge acquisition, where the model is
guided to avoid learning the areas that could lead to a forgetting problem.
(2) Pseudo-label blending, where the previous teacher is involved for
enhancing the pseudo-label. (3) Weather composition replay, where the weather
vectors from previous steps are composed into the current target image for
revising on previously learned knowledge.

## Proposed Method

Our goal is to adapt our model sequentially to multiple adverse weather
conditions, focusing on one weather domain at a time, all the while retaining
the knowledge gained previously. This sequential learning is necessary since
we do not assume that once we have learned a domain, the data from that
particular domain is accessible. To achieve this goal, we begin by adapting
our model to an initial weather domain. Subsequently, we utilize the knowledge
gained from the first domain (previous domain), which includes the teacher
model and weather vectors, to aid the model’s adaptation to the second weather
domain (current domain). This process of acquiring and retaining knowledge is
iterated for each weather domain.

Fig. 2 shows our pipeline. We progressively adapt our model to $n$ distinct
adverse weather domains over $n$ steps. We feed the source images to the
student model in each step for supervised learning on semantic segmentation.
As for the target parts, from step $1$ to step $n-1$, our weather composition
replay extracts and preserves weather vectors for every previously encountered
target domain. Then, in step $n$, we compose the extracted weather vectors
into the current target image. This composite image is subsequently fed into
the student model for making predictions.

We combine pseudo-labels generated by both the current teacher model and the
previous teacher model to synergistically improve the quality of pseudo-
labels. Our adaptive knowledge acquisition assesses pixel-wise domain shifts
from both model-level and feature-level viewpoints. This dynamic reassessment
enables us to adjust the learning process to the current target image, helping
the model avoid incorporating detrimental information that may result in
significant forgetting.

### Adaptive Knowledge Acquisition

In this process of adaptive knowledge acquisition, we identify image regions
with significant domain shifts that could potentially trigger model
forgetting. Subsequently, we dynamically adjust the weighting of these areas,
ensuring that while acquiring new knowledge, the model can still retain past
knowledge.

#### Model-Level Adjustment

Following the standard unsupervised domain adaptation methods (Kennerley et
al. 2023; Hoyer et al. 2023), in each step $n$ (weather domain $n$), we obtain
a teacher model through the EMA (Exponential Moving Average) of a student
model. We then adapt the student model to the new target domain by learning
from the soft pseudo-labels generated by the teacher.

In this standard process, the student will quickly adapt to the new target
domain. However, certain images in the new target domain can result in
forgetting previous knowledge, especially for images that differ significantly
from those in the previous target domain. To mitigate this potential risk, we
incorporate the teacher model from a previous target domain as an auxiliary
model. This teacher model has not been exposed to the new target images during
training. We refer to this teacher model as _Previous-Teacher_.

Our Previous-Teacher makes a prediction for each image in the current step.
Consequently, the confidence of our Previous-Teacher in areas affected by the
new adverse weather degradation can be used as an indication of the degree of
the domain shift. Since, its confidence is low for areas that have never been
learned before. This allows our model to selectively learn from the new
target, avoiding harmful (low confidence) areas and thereby reducing the risk
of forgetting previously acquired knowledge (Kalb and Beyerer 2023). To
implement this idea, we define confidence as $q$:

$q(x)_{ij}=\max(g(x)_{ij}),$ (1)

where, $g$ is the model and $x$ is the input.

We compute a pixel-wise dynamic weighting mask for the model-level adjustment,
denoted as $M^{\rm mod}$, as follows:

$M^{\rm mod}_{ij}=(1-\alpha)q_{\rm cur}(x^{T})_{ij}+\alpha q_{\rm
pre}(x^{T})_{ij},$ (2)

where $x^{T}$ represents the target image, $q_{\rm pre}$ and $q_{\rm cur}$
represent the confidence scores from the previous teacher and the current
teacher, respectively. $\alpha$ is a parameter to control the weights of each
term, where it is large initially, and reduces along the number of iterations.
For regions where Previous-Teacher exhibits significant low confidence,
$M^{\rm mod}$ dynamically reduces the learning weight in those areas. As a
result, the model is encouraged to prioritize exploration in the regions that
are less likely to lead to forgetting. As the model progressively strengthens
its resilience to new weather degradations, the confidence $q_{\rm
cur}(x^{T})_{ij}$ in these challenging regions increases. Simultaneously, with
a decrease in the parameter $\alpha$, the model becomes more inclined to
adaptively learn from these areas.

#### Feature-Level Adjustment

While model-level adjustment focuses on utilizing teacher models to guide the
model’s learning, feature-level adjustment aims to utilize class-specific
feature representations to quantify the domain shift caused by weather
degradation.

When a model attempts to adapt to a new adverse weather domain, the low-level
features it extracts from the early convolutional layers are prone to
degradation due to the new weather conditions. Consequently, predictions
relying on these imprecise features could result in erroneous outcomes and
induce substantial domain shifts within the feature space. In contrast, a
model capable of accurately extracting information should avoid notable domain
shifts in the feature space. Therefore, we leverage this feature information
to assess the extent of domain shifts.

To implement this, we first define the feature representations. Based on the
ground-truth of a source image, we partition the feature maps for different
classes and calculate their average for each class, yielding class-wise source
feature vectors. We then compute the exponential moving average (EMA) of the
source feature vectors, denoted as $\rm SR$. Compared to the source feature
vectors, $\rm SR$ can filter out images that are different from the typical
source images, and thus can provide more representative features.

Similarly, we partition and calculate the average of the target feature maps
according to the corresponding pseudo-labels, resulting in target feature
vectors. As our objective involves dynamically assigning weights to each
target image, we directly employ the target feature vectors as the target
feature representation, denoted as $\rm TR$, for every image. Following this,
we construct a weighting map based on the distances between $\rm SR$ and $\rm
TR$:

$M^{\rm feat}=\max(0,1-\frac{({\rm TR}_{c_{1}}-{\rm
SR}_{c_{1}})^{2}}{\sum_{c=1}^{C}({\rm TR}_{c}-{\rm SR}_{c_{1}})^{2}}),$ (3)

where $c_{1}$ represents the predicted class, and $C$ is the number of all the
predicted classes. In this equation, we calculate the relative distance
between $\rm SR$ and $\rm TR$ for class $c_{1}$.

Intuitively, as shown in Fig. 2, within the feature space, for the target
feature representations of Class 1, if they closely resemble the source
feature representations of the same class, the domain shift is probably minor.
This implies that learning in these areas would result in lesser chances of
significant forgetting. Conversely, when we notice that the target feature
representations are considerably distant from the source feature
representations of the same class (as illustrated in Class 2 in the figure),
it indicates that the model might have captured degraded information from the
image. Training within these regions can lead to substantial alterations in
the feature space, potentially affecting the pretrained feature structures
(Hoyer, Dai, and Van Gool 2022; Su et al. 2023). In such scenarios, our
objective is to mitigate the possibility of forgetting by constraining the
model from learning based on this information.

### Pseudo-Label Blending

By integrating Previous-Teacher with the current teacher model, we can
effectively ensemble them to enhance the robustness of the pseudo-labels
(Allen-Zhu and Li 2020). We achieve this using both Previous-Teacher and its
target feature representations. First, we utilize both the Previous-Teacher
and the current teacher model to generate predictions for the current target
image. Based on the confidences of these predictions, we generate a binary
mask, denoted as $M^{\rm con}$, which indicates the regions where the
Previous-Teacher exhibit higher confidence compared to the current teacher,

$M^{\rm con}_{ij}=\begin{cases}1,&\text{if }q_{\rm pre}(x^{T})_{ij}>q_{\rm
cur}(x^{T})_{ij}\\\ 0,&\text{otherwise}\end{cases},$ (4)

As discussed in the feature-level adjustment, if Previous-Teacher demonstrates
greater robustness to an area than the current teacher for a specific image
segment, the corresponding extracted target feature representations should be
closer to the source feature representations. Hence, we also compute a
weighting map using the equation mentioned in Eq. (3), but using the target
feature representations generated from Previous-Teacher. We denote this
weighting map as $M^{\rm feat}_{\rm pre}$. We can then obtain the refined
pseudo-label, denoted as $p$.

$p(x^{T})_{ij}=\operatorname*{argmax}_{c}(q_{\rm cur}(x^{T})_{ijc}+M^{\rm
con}M^{\rm feat}_{\rm pre}q_{\rm pre}(x^{T})_{ijc}).$ (5)

We incorporate reliable predictions from the previously learned models into
the current learning process. This blending of pseudo-labels enables the model
to effectively learn the similar patterns in different targets, leveraging the
knowledge and expertise accumulated by both Previous-Teacher and the current
teacher model.

### Weather Composition Replay

Figure 3:  Examples of composing night and fog weather vectors into snow and
rain images, respectively.

We propose a replay technique utilizing the weather information obtained from
different weather domains. As mentioned in (Kalb and Beyerer 2023), the domain
shifts introduced by weather degradation can be captured in the frequency
domain by the amplitude spectrum. Hence, when adapting to a new target domain,
we begin by translating each new target image into the frequency domain, and
separate the amplitude from the phase. Although each target image may contain
some image-specific information, they are all subjected to the same adverse
weather conditions. By averaging the extracted amplitude, we can then suppress
image-specific information while preserving the weather vectors, in frequency
domain.

As illustrated in Fig. 2, once the weather vectors are extracted, we keep them
to future steps. In step $n$, we apply augmentations on the stored weather
vectors from step 1 to step $n-1$, and randomly inject them into the current
target images as follow:

$x^{T2}_{r}=M_{r}x^{T2}+(1-M_{r}){\rm iFT}(P^{T2},\sigma A^{T1}),$ (6)

where, $x^{T2}$ is the current target image, $x^{T2}_{r}$ is the composed
images for the model to learn, $P^{T2}$ and $A^{T1}$ represent the phase
component of the current image and the weather vectors of the previous domain,
respectively. $\sigma$ represents a randomly determined volume of $A^{T1}$,
where a larger volume indicates a stronger dominance of the previous weather
information in the area. $\rm iFT$ represents an inverse Fourier
Transformation to translate back the images from frequency domain. $M_{r}$
represents a random segment in that image, as augmenting a segment can be more
efficient than augmenting the whole image (Yun et al. 2019; Olsson et al.
2021). This process is repeated for each weather vector we obtained, for a
total of $n-1$ times.

This replay technique, utilizing the composed images, ensures that the model
continuously updates its understanding of adverse weather conditions while
retaining and refining its knowledge from past experiences.

---
Cityscapes$\rightarrow$Night$\rightarrow$Rain$\rightarrow$Fog$\rightarrow$Snow
Method |  | Forgetting
---
Prevention
Night | Rain | Fog | Snow |  | mIoU
---
Avg. $\uparrow$
| A.F.
---
$\downarrow$
MTKT (Saporta et al. 2021) | - | 21.5 | 39.4 | 48.8 | 38.7 | 37.1 | -
Multi-Dis (Saporta et al. 2021) | - | 20.5 | 38.5 | 43.6 | 36.8 | 34.8 | -
AdvEnt (Vu et al. 2019) | ✗ | 16.9 (-9.0) | 36.9 (-3.2) | 40.8 (-10.3) | 35.1 | 32.4 | 22.4
MuHDi (Saporta et al. 2022) | ✓ | 17.6 (-8.3) | 37.2 (-3.4) | 44.4 (-6.7) | 36.3 | 33.9 | 18.4
Ours (DeeplabV2) | ✓ | 24.0 (-1.9) | 42.0 (-1.3) | 50.8 (-1.1) | 44.0 | 40.2 | 4.3
MIC (Hoyer et al. 2023) | ✗ | 34.7 (-7.2) | 65.8 (-2.8) | 78.4 (-1.3) | 65.2 | 60.1 | 11.3
Ours (DAFormer) | ✓ | 39.0 (-2.9) | 70.6 (-0.9) | 80.4 (-0.2) | 72.6 | 65.7 | 3.6
Table 1: Quantitative results of Ours compare to the existing unsupervised
domain adaptation methods and continual multiple target domain adaptation
methods, evaluated against four targets, ACDC nighttime, rain, fog and snow.
Bold numbers are the best scores for different backbones. The mIoU (%) of each
target, the mIoU average of all the targets (the higher the better), and the
accumulated forgetting, A.F. (the lower the better) are presented. The number
in parentheses ’()’ indicates changes in performance, with a smaller number
indicating a more pronounced forgetting effect. Our method outperforms the
best existing method with forgetting prevention on DeeplabV2 backbone, by
$6.3$ mIoU (%) in average across all the targets, and $14.1$ in the
accumulated forgetting. As for the DAFormer backbone, our method outperforms
the best domain adaptation method by $5.6$ mIoU (%) in average across all the
targets, and $7.7$ in the accumulated forgetting.

## Experimental Results

In this section, we present a comprehensive evaluation of our method under
multiple adverse weather conditions in a sequential setting. We begin by
describing the datasets used in our experiments, followed by the architectures
and parameters employed. Next, we assess our model’s performance both
quantitatively and qualitatively, demonstrating its effectiveness in handling
diverse weather conditions. Lastly, we conduct ablation studies to evaluate
the importance of each factor in our method.

##### Datasets

We utilize Cityscapes (Cordts et al. 2016) as our source domain, consisting of
real-world street scene images captured under daytime, clear weather
conditions. For the target dataset, we employ ACDC (Sakaridis, Dai, and Van
Gool 2021), which contains real-world street scene images captured under four
adverse weather conditions: nighttime, rain, fog, and snow. In our
experiments, each of these four adverse weather conditions is treated as a
separate target, and our models are adapted to these targets sequentially.

##### Baseline Models

In our experiments, we conduct comparisons with the state-of-the-art
unsupervised domain adaptation method, MIC (Hoyer, Dai, and Van Gool 2022). To
ensure a fair comparison, we use the same architecture, DAFormer, in all
comparisons. Additionally, we employ identical optimization strategy,
including the number of epochs, batch sizes, domain adaptation techniques and
the pretrained backbone, as suggested in MIC.

Since our method is not limited by the model’s architecture, we also compare
it with two parallel and one continual general-purpose multiple target domain
adaptation methods, MTKT, Multi-Dis, and MuHDi (Saporta et al. 2021, 2022).
Note, for the parallel setting methods (Saporta et al. 2021), they learn all
the targets simultaneously, their models are not affected by the forgetting
problem. For the continual setting method (Saporta et al. 2022), it provides a
forgetting prevention technique, but this method is not designed specifically
for adverse weather conditions. Once again, to maintain fairness in the
comparison, we utilize the same architecture, DeeplabV2 (Chen et al. 2017),
and employ identical optimization strategy, domain adaptation techniques and
pretrained backbone, following (Saporta et al. 2022).

Regarding our method’s parameters, we initialize the value of $\alpha$ to be
$0.8$ and gradually decrease it to $0.2$ as the number of iterations
progresses. When injecting the previous weather information into the new
target image, we randomly generate $\sigma$ between $0.2$ and $1.2$, and the
sizes of the affected area are randomly selected in the target image, ranging
from one-third to half of the image size. All these parameters are decided
empirically.

##### Evaluation Metrics

Cityscapes and ACDC have the same segmentation class protocols, hence we apply
the same protocol in our evaluation. We use the percentage of Intersection
over Union (IoU %) as our evaluation metric for the effectiveness of the
knowledge acquisition from a new target, the higher the better ($\uparrow$).
As for the knowledge retention, we use Accumulated Forgetting, which is
calculated as follow,

$A.F.=\sum_{k=1}^{K-1}(mIoU_{k,k}-mIoU_{k,K}),$ (7)

where, $K$ is the number of targets. We adapt the model to $K$ targets in $K$
steps. $mIoU_{k,k}$ represents the initial performance of target $k$ at step
$k$, and $mIoU_{k,K}$ represents the final performance of target $k$ at the
last step, $K$. A smaller Accumulated Forgetting indicates a lesser degree of
forgetting in the model ($\downarrow$).

### Quantitative Results

We conduct experiments on four ACDC adverse weather conditions: nighttime,
rain, fog, and snow. As shown in Tab. 1, our models outperformed other methods
on all targets. Specifically, our models surpassed AdvEnt (Vu et al. 2019) and
MIC (Hoyer et al. 2023) by $8.2$ mIoU (%) and $5.6$ mIoU (%) in mIoU Avg., and
$18.1$ and $7.7$ in accumulated forgetting, respectively. The highest mIoU and
the smallest forgetting across all previous targets indicate the effectiveness
of our models’ knowledge acquisition and retention when adapting to different
targets.

We compared our method to MuHDi (Saporta et al. 2022), which offers a general-
purpose forgetting prevention technique for multiple targets. Our method
outperformed MuHDi by $6.3$ mIoU (%) in mIoU Avg. and $14.1$ in accumulated
forgetting. Moreover, while the parallel multiple target domain adaptation
methods do not suffer from the forgetting problem, our model still outperforms
their performance in mIoU Avg. by $3.1$ mIoU (%) and $5.4$ mIoU (%),
respectively. This highlights the importance of our method’s weather-specific
knowledge acquisition and retention.

Image MIC (2023) Ours Ground Truth  Figure 4: Comparisons on the semantic
segmentation performance with MIC (Hoyer et al. 2023), Ours (DAFormer), and
ground truths on ACDC (Val.) under rainy, foggy, and snowy weather conditions
following sequential multitarget domain adaptation.

##### Without Source

In certain circumstances, access to the source data may not be available in
different steps. In this section, we evaluate our method when we can only
access the current target domain in each step. Since the source datasets are
inaccessible, we do not apply $M^{\rm feat}$ and $M^{\rm feat}_{\rm pre}$ in
this scenario. We use MIC as the baseline for comparison. Note, for both MIC
and our method without source, we provide a model finetuned on the source,
following (Kalb and Beyerer 2023). Both methods are required to adapt this
model to different adverse weather conditions. For AdvEnt backbone, it
requires the source dataset for domain adaptation, so models with this
backbone are not involved.

The results are presented in Tab. 2, with the absence of the source image
dataset, MIC’s accumulated forgetting increased significantly from $11.3$ (%)
to $23.9$ (%), by $12.6$ (%), where our model is less affected, with only an
increase of accumulated forgetting by $6.7$ (%).

---
Cityscapes$\rightarrow$Night$\rightarrow$Rain$\rightarrow$Fog$\rightarrow$Snow
Method | Night | Rain | Fog | Snow |  | mIoU
---
Avg. $\uparrow$
| A.F.
---
$\downarrow$
MIC (w/o) | 30.8 | 63.0 | 74.5 | 69.2 | 57.5 | 23.9
Ours (w/o) | 36.7 | 69.8 | 75.9 | 69.6 | 63.0 | 10.3
Table 2:  Quantitative comparisons between MIC (Hoyer et al. 2023) and our
method, both without source (w/o).
---
Cityscapes$\rightarrow$Night$\rightarrow$Rain$\rightarrow$Fog$\rightarrow$Snow
Method | mIoU Avg. $\uparrow$ | A.F. $\downarrow$
AdvEnt | 32.4 | 22.4
Blending | 34.0 | 19.6
Table 3: Ablation studies of knowledge acquisition with pseudo-label blending.
---
Cityscapes$\rightarrow$Night$\rightarrow$Rain$\rightarrow$Fog$\rightarrow$Snow
Progressive | Replay |  A.F. $\downarrow$
| Model
---
Level
| Feature
---
Level
|  |  | 22.4
✓ |  |  | 12.9
✓ | ✓ |  | 9.6
✓ | ✓ | ✓ | 4.5
Table 4: Ablation studies of our knowledge retention techniques, including
adaptive knowledge acquisition and weather composition replay.

### Qualitative Results

We first show our qualitative results of our knowledge acquisition ability in
Fig. 4, for a four-target sequential domain adaptation (on night, rain, fog,
and snow). We evaluate our best model Ours (DAFormer) against MIC, and the
ground truths semantic segmentation maps. We can see that our method can
predict more precise semantic segmentation maps, and also has fewer false
positives compared to MIC in all the target domains. More qualitative results
are provided in the supplementary materials.

### Ablation Studies

##### Knowledge Acquisition and Retention

We begin by evaluating the effectiveness of our adaptive knowledge acquisition
and weather composition replay techniques, as they are specifically designed
for both knowledge acquisition and knowledge retention. In Tab. 3, we report
the performance changes of four models: AdvEnt, AdvEnt with model-level
assistance, AdvEnt with both model-level and feature-level assistance, and
AdvEnt with adaptive knowledge acquisition and weather composition replay
techniques. All these models are trained to adapt to four adverse weather
conditions using source data, and it is evident that each component
contributes to preventing forgetting.

##### Pseudo-Label Blending

Pseudo-label blending is designed for exploring the similar patterns among
different targets to improve the knowledge acquisition on the current target.
We evaluate the knowledge acquisition with two approaches: AdvEnt and AdvEnt
with pseudo-label blending. The results are presented in Tab. 3. We can
observe that pseudo-label blending enhances the average mIoU across the four
targets, without causing additional forgetting issues.

Combining all our proposed techniques, we achieve an enhanced performance on
the new target, while retain the most knowledge from the previous targets.

## Conclusion

We have proposed a novel method that adapts a model to multiple unlabeled
adverse weather conditions sequentially. We use both model-level and feature-
level knowledge to assist the model avoid learning from the harmful contents
from the new target image that can lead to a forgetting of the previously
learned knowledge. To support our current learning process, we have also
proposed a method to involve the previously obtained model to jointly
improving the pseudo-labels for the current target. We propose a weather
composition replay technique, which compose the previously learned weather
information to the current target image, enabling the model learn from the
current target image while revising the previously learned weather
information. We train two models using our method on both DeeplabV2 and
DAFormer, respectively, to demonstrate that our method can be generalized to
different architectures. We evaluate these models on several benchmark adverse
weather conditions with different settings and found that our models
outperform many methods in different settings.

## References

  * Allen-Zhu and Li (2020) Allen-Zhu, Z.; and Li, Y. 2020.  Towards understanding ensemble, knowledge distillation and self-distillation in deep learning.  _arXiv preprint arXiv:2012.09816_.
  * Anoosheh et al. (2019) Anoosheh, A.; Sattler, T.; Timofte, R.; Pollefeys, M.; and Van Gool, L. 2019.  Night-to-day image translation for retrieval-based localization.  In _2019 International Conference on Robotics and Automation (ICRA)_ , 5958–5964. IEEE.
  * Chen et al. (2017) Chen, L.-C.; Papandreou, G.; Kokkinos, I.; Murphy, K.; and Yuille, A. L. 2017.  Deeplab: Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected crfs.  _IEEE transactions on pattern analysis and machine intelligence_ , 40(4): 834–848.
  * Chen et al. (2018) Chen, Y.; Li, W.; Sakaridis, C.; Dai, D.; and Van Gool, L. 2018.  Domain adaptive faster r-cnn for object detection in the wild.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 3339–3348.
  * Chen et al. (2021) Chen, Y.; Wang, H.; Li, W.; Sakaridis, C.; Dai, D.; and Van Gool, L. 2021.  Scale-aware domain adaptive faster r-cnn.  _International Journal of Computer Vision_ , 129(7): 2223–2243.
  * Chen et al. (2019) Chen, Z.; Zhuang, J.; Liang, X.; and Lin, L. 2019.  Blending-target domain adaptation by adversarial meta-adaptation networks.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2248–2257.
  * Cordts et al. (2016) Cordts, M.; Omran, M.; Ramos, S.; Rehfeld, T.; Enzweiler, M.; Benenson, R.; Franke, U.; Roth, S.; and Schiele, B. 2016.  The cityscapes dataset for semantic urban scene understanding.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 3213–3223.
  * Ganin and Lempitsky (2015) Ganin, Y.; and Lempitsky, V. 2015.  Unsupervised domain adaptation by backpropagation.  In _International conference on machine learning_ , 1180–1189. PMLR.
  * Gholami et al. (2020) Gholami, B.; Sahu, P.; Rudovic, O.; Bousmalis, K.; and Pavlovic, V. 2020.  Unsupervised multi-target domain adaptation: An information theoretic approach.  _IEEE Transactions on Image Processing_ , 29: 3993–4002.
  * Hayes et al. (2020) Hayes, T. L.; Kafle, K.; Shrestha, R.; Acharya, M.; and Kanan, C. 2020.  Remind your neural network to prevent catastrophic forgetting.  In _European Conference on Computer Vision_ , 466–483. Springer.
  * Hoyer, Dai, and Van Gool (2022) Hoyer, L.; Dai, D.; and Van Gool, L. 2022.  Daformer: Improving network architectures and training strategies for domain-adaptive semantic segmentation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 9924–9935.
  * Hoyer et al. (2023) Hoyer, L.; Dai, D.; Wang, H.; and Van Gool, L. 2023.  MIC: Masked image consistency for context-enhanced domain adaptation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 11721–11732.
  * Hu et al. (2021) Hu, X.; Zhu, L.; Wang, T.; Fu, C.-W.; and Heng, P.-A. 2021.  Single-image real-time rain removal based on depth-guided non-local features.  _IEEE Transactions on Image Processing_ , 30: 1759–1770.
  * Isobe et al. (2021) Isobe, T.; Jia, X.; Chen, S.; He, J.; Shi, Y.; Liu, J.; Lu, H.; and Wang, S. 2021\.  Multi-target domain adaptation with collaborative consistency learning.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 8187–8196.
  * Kalb and Beyerer (2023) Kalb, T.; and Beyerer, J. 2023.  Principles of Forgetting in Domain-Incremental Semantic Segmentation in Adverse Weather Conditions.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 19508–19518.
  * Kang, Park, and Han (2022) Kang, M.; Park, J.; and Han, B. 2022.  Class-incremental learning by knowledge distillation with adaptive feature consolidation.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , 16071–16080.
  * Kennerley et al. (2023) Kennerley, M.; Wang, J.-G.; Veeravalli, B.; and Tan, R. T. 2023.  2PCNet: Two-Phase Consistency Training for Day-to-Night Unsupervised Domain Adaptive Object Detection.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 11484–11493.
  * Lee et al. (2022) Lee, S.; Choi, W.; Kim, C.; Choi, M.; and Im, S. 2022.  ADAS: A Direct Adaptation Strategy for Multi-Target Domain Adaptive Semantic Segmentation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 19196–19206.
  * Li et al. (2023) Li, M.; Xie, B.; Li, S.; Liu, C. H.; and Cheng, X. 2023.  VBLC: Visibility Boosting and Logit-Constraint Learning for Domain Adaptive Semantic Segmentation under Adverse Conditions.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 37, 8605–8613.
  * Li, Yuan, and Vasconcelos (2019) Li, Y.; Yuan, L.; and Vasconcelos, N. 2019.  Bidirectional learning for domain adaptation of semantic segmentation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 6936–6945.
  * Lin et al. (2022) Lin, H.; Zhang, Y.; Qiu, Z.; Niu, S.; Gan, C.; Liu, Y.; and Tan, M. 2022.  Prototype-guided continual adaptation for class-incremental unsupervised domain adaptation.  In _Computer Vision–ECCV 2022: 17th European Conference, Tel Aviv, Israel, October 23–27, 2022, Proceedings, Part XXXIII_ , 351–368. Springer.
  * Nguyen-Meidine et al. (2021) Nguyen-Meidine, L. T.; Belal, A.; Kiran, M.; Dolz, J.; Blais-Morin, L.-A.; and Granger, E. 2021.  Unsupervised multi-target domain adaptation through knowledge distillation.  In _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision_ , 1339–1347.
  * Olsson et al. (2021) Olsson, V.; Tranheden, W.; Pinto, J.; and Svensson, L. 2021.  Classmix: Segmentation-based data augmentation for semi-supervised learning.  In _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision_ , 1369–1378.
  * Peng et al. (2019) Peng, X.; Huang, Z.; Sun, X.; and Saenko, K. 2019.  Domain agnostic learning with disentangled representations.  In _International Conference on Machine Learning_ , 5102–5112. PMLR.
  * Rebuffi et al. (2017) Rebuffi, S.-A.; Kolesnikov, A.; Sperl, G.; and Lampert, C. H. 2017.  icarl: Incremental classifier and representation learning.  In _Proceedings of the IEEE conference on Computer Vision and Pattern Recognition_ , 2001–2010.
  * Roy et al. (2021) Roy, S.; Krivosheev, E.; Zhong, Z.; Sebe, N.; and Ricci, E. 2021.  Curriculum graph co-teaching for multi-target domain adaptation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 5351–5360.
  * Saito et al. (2019) Saito, K.; Ushiku, Y.; Harada, T.; and Saenko, K. 2019.  Strong-weak distribution alignment for adaptive object detection.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 6956–6965.
  * Sakaridis, Dai, and Van Gool (2018) Sakaridis, C.; Dai, D.; and Van Gool, L. 2018.  Semantic foggy scene understanding with synthetic data.  _International Journal of Computer Vision_ , 126: 973–992.
  * Sakaridis, Dai, and Van Gool (2021) Sakaridis, C.; Dai, D.; and Van Gool, L. 2021.  ACDC: The adverse conditions dataset with correspondences for semantic driving scene understanding.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 10765–10775.
  * Saporta et al. (2022) Saporta, A.; Douillard, A.; Vu, T.-H.; Pérez, P.; and Cord, M. 2022.  Multi-Head Distillation for Continual Unsupervised Domain Adaptation in Semantic Segmentation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 3751–3760.
  * Saporta et al. (2021) Saporta, A.; Vu, T.-H.; Cord, M.; and Pérez, P. 2021.  Multi-target adversarial frameworks for domain adaptation in semantic segmentation.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 9072–9081.
  * Shin et al. (2017) Shin, H.; Lee, J. K.; Kim, J.; and Kim, J. 2017.  Continual learning with deep generative replay.  _Advances in neural information processing systems_ , 30.
  * Sindagi et al. (2020) Sindagi, V. A.; Oza, P.; Yasarla, R.; and Patel, V. M. 2020.  Prior-based domain adaptive object detection for hazy and rainy conditions.  In _Computer Vision–ECCV 2020: 16th European Conference, Glasgow, UK, August 23–28, 2020, Proceedings, Part XIV 16_ , 763–780. Springer.
  * Su et al. (2023) Su, W.; Han, Z.; He, R.; Wei, B.; He, X.; and Yin, Y. 2023.  Neighborhood-based credibility anchor learning for universal domain adaptation.  _Pattern Recognition_ , 142: 109686.
  * Vu et al. (2019) Vu, T.-H.; Jain, H.; Bucher, M.; Cord, M.; and Pérez, P. 2019.  Advent: Adversarial entropy minimization for domain adaptation in semantic segmentation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2517–2526.
  * Yang et al. (2022a) Yang, L.; Zhuo, W.; Qi, L.; Shi, Y.; and Gao, Y. 2022a.  St++: Make self-training work better for semi-supervised semantic segmentation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 4268–4277.
  * Yang et al. (2022b) Yang, Y.; Wang, C.; Liu, R.; Zhang, L.; Guo, X.; and Tao, D. 2022b.  Self-augmented unpaired image dehazing via density and depth decomposition.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , 2037–2046.
  * Yao et al. (2022) Yao, C.-H.; Gong, B.; Qi, H.; Cui, Y.; Zhu, Y.; and Yang, M.-H. 2022.  Federated multi-target domain adaptation.  In _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision_ , 1424–1433.
  * Yu, Hu, and Chen (2018) Yu, H.; Hu, M.; and Chen, S. 2018.  Multi-target unsupervised domain adaptation without exactly shared categories.  _arXiv preprint arXiv:1809.00852_.
  * Yun et al. (2019) Yun, S.; Han, D.; Oh, S. J.; Chun, S.; Choe, J.; and Yoo, Y. 2019.  Cutmix: Regularization strategy to train strong classifiers with localizable features.  In _Proceedings of the IEEE/CVF international conference on computer vision_ , 6023–6032.
  * Zou et al. (2018) Zou, Y.; Yu, Z.; Kumar, B.; and Wang, J. 2018.  Unsupervised domain adaptation for semantic segmentation via class-balanced self-training.  In _Proceedings of the European conference on computer vision (ECCV)_ , 289–305.


# Residues in Pascal’s Triangle mod $p$ are Asymptotically Evenly Distributed

Connor Lane

###### Abstract

Fix a prime $p$ and define $T_{p}(n)$ to be the number of nonzero residues in
the $n$th row of pascal’s triangle mod $p$, and define $\phi_{p}(n)$ to be the
number of nonzero residues in the first $n$ rows of pascal’s triangle mod $p$.
We generalize these to sequences $T_{\chi}(n)$ and $\phi_{\chi}(n)$ for a
Dirichlet character $\chi$ of modulus $p$. We prove many properties of these
sequences that generalize those of $T_{p}(n)$ and $\phi_{p}(n)$. These allow
us to prove the main result of the paper: define $A_{n}(r)$ to be the number
of occurrences of $r$ in the first $n$ rows of Pascal’s triangle mod $p$. We
show that for all primes $p$ and nonzero residues $r$,
$A_{n}(r)\sim\frac{1}{p-1}\phi_{p}(n)$. We also discuss the distribution of
$A_{p}(r)$.

##  1 Introduction

The problem of the structure of Pascal’s triangle mod $p$ has a long history,
starting with the following theorem of Lucas [Fin47]. Suppose $n$ has $p$-ary
expansion $\overline{n_{k}n_{k-1}\ldots n_{0}}$ and $m$ has $p$-ary expansion
$\overline{m_{k}m_{k-1}\ldots m_{0}}$. Then

$\binom{n}{m}\equiv\prod_{j=0}^{k}\binom{n_{j}}{m_{j}}\mod{p}.$

This reduces computation of $\binom{n}{m}\mod{p}$ to computing
$\binom{n_{j}}{m_{j}}\mod{p}$, where $n_{j},m_{j}<p$. Motivated by this, we
define

######  Definition 1.1.

The fundamental domain of pascal’s triangle mod $p$ is the first $p$ rows of
the triangle.

Next, we introduce some notation:

  1. 1.

$p$ is a fixed prime unless otherwise specified. Function definitions are
always defined in terms of the choice of $p$, even if not explicitly
specified.

  2. 2.

$T_{p}(n)$ is the number of nonzero residues in the $n$th row of Pascal’s
triangle mod $p$.

  3. 3.

$\phi_{p}(n)$ is the number of nonzero residues in the first $n$ rows of
Pascal’s triangle mod $p$.

  4. 4.

$a_{n}(r)$ is the number of occurrences of $r$ in the $n$th row of Pascal’s
triangle mod $p$, where the triangle is understood to start at the zeroeth
row.

  5. 5.

$A_{n}(r)=\sum_{u=0}^{n-1}a_{n}(r)$ is the number of occurences of $r$ in the
first $n$ rows of Pascal’s triangle mod $p$.

  6. 6.

$\chi$ is always a Dirichlet character with modulus $p$.

One recent result is the following theorem of [Bra+19]

######  Theorem 1.2.

Suppose $p$ is a prime and $r$ is a nonzero residue mod $p$. Then as $k$ goes
to infinity,

$A_{p^{k}}(r)\sim\frac{\phi_{p}(p^{k})}{p-1}$

However, their theorem says nothing of the behavior of $A_{n}(r)$ in between
prime powers. This is what our improvement of their theorem wishes to do.

######  Theorem 1.3.

Suppose $p$ is a prime and $r$ is a nonzero residue mod $p$. Then as $n$ goes
to infinity,

$A_{n}(r)\sim\frac{\phi_{p}(n)}{p-1}.$

This theorem can be refined to be stronger, however it requires even more
concepts introduced in later sections. It can also be greatly be improved by
focusing on a particular prime.

In section 2, we introduce two sequences determined by a Dirichlet character
$\chi$, $T_{\chi}(n)$ and $\phi_{\chi}(n)$, which roughly correspond to
$a_{n}(r)$ and $A_{n}(r)$, however, they obey some very nice identities. Then
in section 3 we prove some asymptotic bounds on the behavior of
$\phi_{\chi}(n)$ based on behavior in the fundamental domain. Then, in section
4 we analyze the fundamental domain using a mixture of heuristic methods and
concrete bounds. Finally in section 5 we combine the results of section 3 and
section 4 to prove theorem 1.3, and we discuss some conjectures.

##  2 The functions $T_{\chi}(n)$ and $\phi_{\chi}(n)$

For a fixed prime $p$ let $a_{n}(r)$ be the number of occurrences of $r$ in
the $n$th row of Pascal’s triangle mod $p$. We define $T_{\chi}(n)$

$T_{\chi}(n)=\sum_{j=0}^{n}\chi\\!\left(\\!\binom{n}{j}\\!\right)=\sum_{i=1}^{p-1}\chi(i)a_{n}(i)$

######  Proposition.

Let $n$ have $p$-ary expansion $n=\overline{n_{k}\ldots n_{0}}$, then

$T_{\chi}(n)=\prod_{j=0}^{k}T_{\chi}(n_{j})$ (1)

###### Proof.

This is a restatement of the primary result of [GW92]. If $g$ is a generator
of $(\mathbb{Z}/p\mathbb{Z})^{\times}$, and $a_{n}(r)$ is the number of
occurences of $r$ in the $n$th row of Pascal’s triangle mod $p$. We define the
polynomial $R_{n}(x)$, where

$R_{n}(x)=\sum_{i=0}^{p-2}x^{i}a_{n}(g^{i}).$

then, using our notation, they showed

$R_{n}(x)\equiv\prod_{j=0}^{k}R_{n_{k}}(x)\mod x^{p-1}-1$

We know $\chi(g^{n})=\chi(g)^{n}$, so it follows that
$R_{n}(\chi(g))=T_{\chi}(n)$, and since $\chi(g)^{p-1}-1=0$, the result
follows. ∎

By considering partial sums of $T_{\chi}(n)$, we define $\phi_{\chi}(n)$:

$\phi_{\chi}(n)=\sum_{u=0}^{n-1}T_{\chi}(u).$

We remark that if $\chi_{0}$ is the principal character mod $p$, then
$\phi_{\chi_{0}}(n)=\phi_{p}(n)$, which has been heavily studied in the
literature. It equals the number of nonzero residues in the first $n$ rows of
Pascal’s triangle mod $p$. Among other things, it has been shown that if
$\theta=\log_{p}(\phi_{p}(p))$, then
$\alpha=\limsup(\tfrac{\phi_{p}(n)}{n^{\theta}})$ and
$\beta=\liminf(\tfrac{\phi_{p}(n)}{n^{\theta}})$ both exist, with $\alpha=1$
and $1>\beta>0.5$ [Har77, Wil98]. These theorems are made possible by certain
recursive formulas for $\phi_{p}(n)$, the following lemma generalizes these
fractal properties to arbitrary $\phi_{\chi}(n)$.

######  Lemma 2.1.

  1. 1.

For all nonegative integers $m,k$ we have
$\phi_{\chi}(mp^{k})=\phi_{\chi}(m)\phi_{\chi}(p^{k})$

  2. 2.

Furthermore, for all nonnegative $n<p^{k}$, we have
$\phi_{\chi}(mp^{k}+n)=\phi_{\chi}(mp^{k})+T_{\chi}(m)\phi_{\chi}(n)$

###### Proof.

First, we show 1. Let $m,k\in\mathbb{N}$, then we have

$\displaystyle\phi_{\chi}(mp^{k})=$
$\displaystyle\sum_{u=0}^{mp^{k}-1}T_{\chi}(u)$ $\displaystyle=$
$\displaystyle\sum_{u_{1}=0}^{m-1}\sum_{u_{2}=0}^{p^{k}-1}T_{\chi}(u_{1}p^{k}+u_{2})$
$\displaystyle=$
$\displaystyle\sum_{u_{1}=0}^{m-1}\sum_{u_{2}=0}^{p^{k}-1}T_{\chi}(u_{1})T_{\chi}(u_{2})$
$\displaystyle=$
$\displaystyle\sum_{u_{1}=0}^{m-1}T_{\chi}(u_{1})\sum_{u_{2}=0}^{p^{k}-1}T_{\chi}(u_{2})$
$\displaystyle=$ $\displaystyle\phi_{\chi}(m)\phi_{\chi}(p^{k})$

Note that in the third line we use the fact that the last $k$ digits of
$u_{1}p^{k}+u_{2}$ are exactly the digits of $u_{2}$ and all other digits are
the digits of $u_{1}$. This completes the proof of part 1. The proof of part 2
is similar

$\displaystyle\phi_{\chi}(mp^{k}+n)=$
$\displaystyle\sum_{u=0}^{mp^{k}+n-1}T_{\chi}(u)$ $\displaystyle=$
$\displaystyle\sum_{u=0}^{mp^{k}-1}T_{\chi}(u)+\sum_{u=0}^{n-1}T_{\chi}(mp^{k}+u)$
$\displaystyle=$
$\displaystyle\phi_{\chi}(mp^{k})+T_{\chi}(m)\sum_{u=0}^{n-1}T_{\chi}(u)$
$\displaystyle=$ $\displaystyle\phi_{\chi}(mp^{k})+T_{\chi}(m)\phi_{\chi}(n).$

Where we use the fact that the last $k$ digits of $mp^{k}+u$ are exactly the
digits of $u$. This concludes the proof of part 2. ∎

Next, we let $A_{n}(r)$ be the number of occurrences of the residue $r$ in the
first $n$ rows of pascal’s triangle mod $p$. We note that $\phi_{\chi}(n)$ can
be written in terms of $A_{n}(r)$:

$\phi_{\chi}(n)=\sum_{u=0}^{n-1}T_{\chi}(n)=\sum_{u=0}^{n-1}\sum_{r=1}^{p-1}\chi(r)a_{u}(r)=\sum_{r=1}^{p-1}\sum_{u=0}^{n-1}\chi(r)a_{u}(r)=\sum_{p=1}^{n-1}\chi(r)A_{u}(r).$

More interestingly, we can actually compute $A_{n}(r)$ in terms of
$\phi_{\chi}(n)$.

######  Lemma 2.2.

Let $n$ be a nonnegative integer; then,

$A_{n}(r)=\frac{1}{p-1}\sum_{\chi}\overline{\chi}(r)\phi_{\chi}(n).$

###### Proof.

Let $s$ be an integer such that $sr\equiv 1\mod p$. Then
$\overline{\chi}(r)=\chi(s)$ and

$\displaystyle\frac{1}{p-1}\sum_{\chi}\overline{\chi}(r)\phi_{\chi}(n)=$
$\displaystyle\frac{1}{p-1}\sum_{\chi}\sum_{t=1}^{p-1}\chi(s)\chi(t)A_{n}(t)=\frac{1}{p-1}\sum_{t=1}^{p-1}\sum_{\chi}\chi(st)A_{n}(t)$
$\displaystyle=$
$\displaystyle\frac{1}{p-1}\sum_{t=1}^{p-1}\begin{cases}(p-1)A_{n}(t)&\text{if
}st\equiv 1\mod p\\\ 0&\text{otherwise}\end{cases}$ $\displaystyle=$
$\displaystyle A_{n}(r).$

Where we use orthogonality of characters to simplify the sum over Dirichlet
characters mod $p$. ∎

This makes $A_{n}(r)$ significantly easier to study, as it is reduced to
studying $\phi_{\chi}(n)$, a sequence that is much more well-behaved.

##  3 Properties of $\phi_{\chi}(n)$

We begin by fixing a prime $p$ and character $\chi$ of modulus $p$. We define
$\theta_{\chi}=\log_{p}(\phi_{\chi}(p))$, and we take the principal branch of
the logarithm.

Next, we define a certain technical condition that the theorems of this
section rely upon. Further discussion of this condition can be found in
section 4.

######  Definition 3.1.

A character $\chi$ is called row-regular if for all $0\leq b<p$, we have
$|T_{\chi}(b)|<|\phi_{\chi}(p)|$.

We now prove a theorem about $\phi_{\chi}(n)$ for row-regular characters
$\chi$.

######  Theorem 3.2.

Fix a row-regular character $\chi$. Then we have
$|\phi_{\chi}(n)|=O(n^{\theta_{\chi}})$. Moreover, if we define
$\alpha=\limsup(|\phi_{\chi}(n)/n^{\theta_{\chi}})|$, then $\alpha$ exists and
is greater than or equal to $1$.

###### Proof.

We first define a sequence of positive real numbers $\\{\alpha_{k}\\}_{k>0}$
as follows

$\alpha_{k}=\max\left\\{\left|\frac{\phi_{\chi}(n)}{n^{\theta_{\chi}}}\right|:p^{k-1}<n\leq
p^{k}\right\\}$

It is clear that, if it exists,
$\lim_{k\rightarrow\infty}(\alpha_{k})=\alpha$. We will show that
$\alpha_{k+1}\in[\alpha_{k},\alpha_{k}+|\phi_{\chi}(p)|\alpha_{1}q^{k})$ for
some $|q|<1$. First, we will show that $\alpha_{k+1}\geq\alpha_{k}$. Select
$p^{k-1}<n\leq p^{k}$ such that
$|\phi_{\chi}(n)/n^{\theta_{\chi}}|=\alpha_{k}$. Then since $p^{k}<np\leq
p^{k+1}$, we can use lemma 2.1 part 1 to show

$\alpha_{k+1}\geq\left|\frac{\phi_{\chi}(pn)}{(pn)^{\theta_{\chi}}}\right|=\left|\frac{\phi_{\chi}(p)\phi_{\chi}(p)}{p^{\theta_{\chi}}n^{\theta_{\chi}}}\right|=\left|\frac{\phi_{\chi}(p)\phi_{\chi}(n)}{\phi_{\chi}(p)n^{\theta_{\chi}}}\right|=\left|\frac{\phi_{\chi}(n)}{n^{\theta_{\chi}}}\right|=\alpha_{k}.$

Next, we can show that
$\alpha_{k+1}-\alpha_{k}\leq|\phi_{\chi}(p)|\alpha_{1}q^{k}$. We consider some
$n$ such that $p^{k}<n\leq p^{k+1}$ and
$|\phi_{\chi}(n)/n^{\theta_{\chi}}|=\alpha_{k+1}$, and write $n=pm+b$ for
$p^{k-1}<m\leq p^{k}$ and $0\leq b<p$. Then using both parts of lemma 2.1 we
see that

$\displaystyle\alpha_{k+1}=$
$\displaystyle\left|\frac{\phi_{\chi}(pm+b)}{n^{\theta_{\chi}}}\right|$
$\displaystyle\leq$
$\displaystyle\frac{1}{|(mp)^{\theta_{\chi}}|}\left|\phi_{\chi}{p}\phi_{\chi}(m)+\phi_{\chi}(b)T_{\chi}(m)\right|$
$\displaystyle\leq$
$\displaystyle\frac{1}{|(mp)^{\theta_{\chi}}|}\big{(}|\phi_{\chi}(p)||\phi_{\chi}(m)|+|\phi_{\chi}(b)||T_{\chi}(m)|\big{)}$

Since $b<p$, we know that $|\phi_{\chi}(b)|<\alpha_{1}|p^{\theta_{\chi}}|$. We
also use the fact that $|\phi_{\chi}(p)|=|p^{\theta_{\chi}}|$.

$\displaystyle\alpha_{k+1}<$
$\displaystyle\frac{|\phi_{\chi}(m)|}{|m^{\theta_{\chi}}|}+\frac{\alpha_{1}|T_{\chi}(m)|}{|m^{\theta_{\chi}}|}$
$\displaystyle\leq$
$\displaystyle\alpha_{k}+\frac{\alpha_{1}|T_{\chi}(m)|}{|(p^{k-1})^{\theta_{\chi}}|}.$

The proof of the theorem would follow if we can bound
$|T_{\chi}(m)|/(m^{k-1})^{\theta_{\chi}}$. This is quite straight forward, but
we will factor out to a lemma so we can reference it later.

######  Lemma 3.3.

Let $m<p^{k}$ be a nonnegative integer and $\chi$ a row regular character.
Then there exists some real number $0<q<1$ independent of $m$ such that

$\left|\frac{T_{\chi}(m)}{m^{\phi_{\chi}}}\right|\leq q^{k}$

###### Proof.

Since $m$ is a $k$ digit number, we can use equation 1 to write
$|T_{\chi}(m)|=\prod_{j=0}^{k-1}|T_{\chi}(m_{j})|$, where $m_{j}$ are the
$p$-ary digits of $m$. simply maximising each entry in the product, we have
$|T_{\chi}(m)|\leq\prod_{j=0}^{k-1}\max\\{|T_{\chi}(t)|:0\leq
t<p\\}=(\max\\{|T_{\chi}(t)|:0\leq t<p\\})^{k}$. With this in mind, we let
$q=\max\\{|T_{\chi}(t)|:0\leq t<p\\}/\phi_{\chi}(p)$, and row-regularity
implies $q<1$. This gives

$\left|\frac{T_{\chi}(n)}{n^{\theta_{\chi}}}\right|\leq\left|\frac{\max\\{|T_{\chi}(t)|:0\leq
t<p\\})^{k}}{(p^{k})^{\theta_{\chi}}}\right|=\left|\frac{\max\\{|T_{\chi}(t)|:0\leq
t<p\\})^{k}}{\phi_{\chi}(p)^{k}}\right|\leq q^{k}.$

Which is what we wanted to show. ∎

Using lemma 3.3, we obtain

$\displaystyle\alpha_{k+1}<$
$\displaystyle\alpha_{k}+|p^{\theta_{\chi}}|\alpha_{1}\frac{T_{\chi}(n)}{n^{\theta_{\chi}}}$
$\displaystyle=$ $\displaystyle\alpha_{k}+|\phi_{\chi}(p)|\alpha_{1}q^{k}.$

This completes the proof that
$\alpha_{k+1}\in[\alpha_{k},\alpha_{k}+|\phi_{\chi}(p)|\alpha_{1}q^{k})$ for
some $|q|<1$. Since the geometric series
$\prod_{k=0}^{\infty}|\phi_{\chi}(p)|\alpha_{1}q^{k}$ converges, we have that
${\alpha_{k}}$ is bounded and $\lim_{k\rightarrow\infty}\alpha_{k}$ converges
by monotone convergence theorem. This means that
$\alpha=\limsup(\phi_{\chi}(n)/n^{\theta_{\chi}})$ exists. In particular, this
implies that $\phi_{\chi}(n)=O(n^{\theta_{\chi}})$

To show that $\alpha\geq 1$, we simply note that
$\phi_{\chi}(p^{k})/(p^{k})^{\theta_{\chi}}=1$ for all $k$ by a simple
application of lemma 2.1. ∎

Next, we generalize a theorem of [Ste89] about the behavior of
$\phi_{\chi_{0}}$ to arbitrary row-regular characters. We define the following
function:

$\psi_{\chi}(n)=\frac{\phi_{\chi}(n)}{n^{\theta}_{\chi}}.$

Theorem 3.2 implies that $\psi_{\chi}(n)=O(1)$, and lemma 2.1 implies
$\psi_{\chi}(pn)=\psi_{\chi}(n)$. Using this formula, we canonically extend
the domain of $\psi_{\chi}$ to
$D=\\{{n}/{p^{k}}:n\in\mathbb{Z}^{>0},k\in\mathbb{Z}^{\geq 0}\\}$. We remark
that $D$ is dense in $\mathbb{R}^{>0}$, so if we show that $\psi_{\chi}$ is
continuous on $D$, we get a canonical extension to $\mathbb{R}^{>0}$. Indeed,
we will prove

######  Theorem 3.4.

Let $\chi$ be a row-regular character. Then $\psi_{\chi}(x)$ is uniformly
continuous on subsets bounded away from $0$.

###### Proof.

We will prove uniform continuity in the set $[1,\infty)$, and uniform
continuity in sets bounded away from $0$ will follow by using the fact that
$\psi_{\chi}(x)=\psi_{\chi}(px)$

For nonnegative integers $a,r,k$ with $k<p^{r-a}$ and a positive integer $n$,
we will bound the difference $\psi_{\chi}(p^{r}n+k)-\psi_{\chi}(p^{r}n)$
uniformly in $r$. Expanding definitions and applying 2.1 we obtain

$\displaystyle\left|\psi_{\chi}(p^{r}n+k)-\psi_{\chi}(p^{r}n)\right|=$
$\displaystyle\left|\frac{\phi_{\chi}(p^{r}n+k)}{(p^{r}n+k)^{\theta_{\chi}}}-\frac{\phi_{\chi}(p^{r}n)}{(p^{r}n)^{\theta_{\chi}}}\right|$
$\displaystyle=$
$\displaystyle\left|\frac{\phi_{\chi}(p^{r}n)}{(p^{r}n+k)^{\theta_{\chi}}}+\frac{T_{\chi}(n)\phi_{\chi}(k)}{(p^{r}n+k)^{\theta_{\chi}}}-\frac{\phi_{\chi}(p^{r}n)}{(p^{r}n)^{\theta_{\chi}}}\right|$
$\displaystyle\leq$
$\displaystyle\left|\frac{\phi_{\chi}(p^{r}n)}{(p^{r}n+k)^{\theta_{\chi}}}-\frac{\phi_{\chi}(p^{r}n)}{(p^{r}n)^{\theta_{\chi}}}\right|+\left|\frac{T_{\chi}(n)\phi_{\chi}(k)}{(p^{r}n+k)^{\theta_{\chi}}}\right|$

We will bound each of these terms separately. The 2nd term is easier to bound,
so we will do it first. Using 3.2, we obtain

$\left|\frac{T_{\chi}(n)\phi_{\chi}(k)}{(p^{r}n+k)^{\theta_{\chi}}}\right|\leq\left|\frac{T_{\chi}(n)\alpha
k^{\theta_{\chi}}}{(p^{r}n)^{\theta_{\chi}}}\right|\leq\left|\frac{T_{\chi}(n)\alpha(p^{r-a})^{\theta_{\chi}}}{(p^{r}n)^{\theta_{\chi}}}\right|=\left|\frac{T_{\chi}(n)}{(p^{a}n)^{\theta_{\chi}}}\right|.$

Using lemma 3.3, we bound $|T_{\chi}(n)/n^{\theta_{\chi}}|\leq
q^{\log_{p}(n)}=O(1/n^{\omega_{\chi}})$ for some $1\geq\omega_{\chi}>0$. (We
may be able to obtain a $\omega_{\chi}\geq 1$ for some characters, but it will
be of convenience later to restrict it to be less than $1$, and the equation
is still true in that case.) This gives the bound that the second term is
$O(n^{-\omega_{\chi}}p^{-a})$ uniformly in $r$.

Next we bound the first term. To this end, we prove the following general
lemma

######  Lemma 3.5.

Let $a,b$ be positive real numbers with $b<a$, and $\theta\in\mathbb{C}$ have
positive real part. Then

$\left|\frac{1}{(a+b)^{\theta}}-\frac{1}{a^{\theta}}\right|=O\left(\frac{b}{a^{1+\theta}}\right).$

###### Proof.

Some elementary algebra yields

$\left|\frac{1}{(a+b)^{\theta}}-\frac{1}{a^{\theta}}\right|=\left|\frac{1^{\theta}-\left(1+\frac{b}{a}\right)^{\theta}}{(a+b)^{\theta}}\right|\leq\left|\frac{1-(1+\frac{b}{a})^{\theta}}{a^{\theta}}\right|.$

We then use the generalized binomial theorem to expand
$(1+\frac{a}{b})^{\theta}$.

$\displaystyle\left|\frac{T_{\chi}(n)\phi_{\chi}(k)}{(p^{r}n+k)^{\theta_{\chi}}}\right|\leq$
$\displaystyle\left|\frac{1-(1+\frac{b}{a})^{\theta}}{a^{\theta}}\right|$
$\displaystyle=$
$\displaystyle\left|\frac{1-\sum_{n=0}^{\infty}\binom{\theta}{n}\left(\frac{b}{a}\right)^{n}}{a^{\theta}}\right|$
$\displaystyle=$
$\displaystyle\left|\frac{-\sum_{n=1}^{\infty}\binom{\theta}{n}\left(\frac{b}{a}\right)^{n}}{a^{\theta}}\right|$
$\displaystyle=$ $\displaystyle O\left(\frac{b}{a^{\theta+1}}\right).$

Which is what we wanted to show. ∎

We now return to bounding the first term. Since $a\geq 0$, we know that
$k<p^{r}n$, so we can apply lemma 3.5 to the denominator of the first term.

$\displaystyle\left|\frac{\phi_{\chi}(p^{r}n)}{(p^{r}n+k)^{\theta_{\chi}}}-\frac{\phi_{\chi}(p^{r}n)}{(p^{r}n)^{\theta_{\chi}}}\right|=$
$\displaystyle|\phi_{\chi}(p^{r}n)|\left|\frac{1}{(p^{r}n+k)^{\theta_{\chi}}}-\frac{1}{(p^{r}n)^{\theta_{\chi}}}\right|$
$\displaystyle\leq$
$\displaystyle|(p^{r}n)^{\theta_{\chi}}|\left|\frac{1}{(p^{r}n+k)^{\theta_{\chi}}}-\frac{1}{(p^{r}n)^{\theta_{\chi}}}\right|$
$\displaystyle=$
$\displaystyle|(p^{r}n)^{\theta_{\chi}}|O\left(\frac{k}{(p^{r}n)^{\theta_{\chi}+1}}\right)$
$\displaystyle=$ $\displaystyle
O\left(\frac{p^{r-a}}{(p^{r}n)}\right)=O\left(\frac{1}{np^{a}}\right).$

Where for the last inequality, we use the fact that $n$ is a positive integer
to bound it by $1$.

Combining this with the bound on the first term, we obtain a bound that goes
to $0$ as $a$ goes to infinity

$\left|\psi_{\chi}(p^{r}n+k)-\psi_{\chi}(p^{r}n)\right|=O\left(\frac{1}{n^{\omega_{\chi}}p^{a}}\right)+O\left(\frac{1}{np^{a}}\right)=O\left(\frac{1}{n^{\omega_{\chi}}p^{a}}\right).$

Let $x_{0}=\frac{n}{p^{b}}\geq 1$. If $0\leq x-x_{0}<p^{1-b}$, we will bound
$\psi_{\chi}(x)-\psi_{\chi}(x_{0})$ in such a way that it goes to $0$ as $b$
goes to infinity. This will be the last ingredient needed for uniform
continuity.

Since $x_{0}\geq 1$, we obtain $n\geq p^{b}$. Further, we write
$x-x_{0}=k/(p^{b-1+r})$ with $k<p^{r}$. using the fact that
$\psi_{\chi}(x)=\psi_{\chi}(px)$, we see that

$|\psi_{\chi}(x)-\psi_{\chi}(x_{0})|=\left|\psi_{\chi}\left(n+\frac{k}{p^{1+r}}\right)-\psi_{\chi}(n)\right|=|\psi_{\chi}(p^{1+r}n+k)-\psi_{\chi}(p^{1+r}n)|=O\left(\frac{1}{n^{\omega_{\chi}}p}\right)=O\left(\frac{1}{p^{b\omega_{\chi}}}\right).$

Finally, we move towards uniform continuity. Let $x_{0}\geq 1$. And let
$|x-x_{0}|<\frac{1}{p^{b}}$. Define $y_{0}=\frac{k}{p^{b}}$ to be an element
of $\frac{1}{p^{b}}\mathbb{Z}$ such that $y_{0}<x_{0},x$ and
$|y_{0}-x|<\frac{1}{p^{b-1}}$ and $|y_{0}-x_{0}|<\frac{1}{p^{b-1}}$. Then the
bounds above imply that

$|\psi_{\chi}(x)-\psi_{\chi}(x_{0})|=|\psi_{\chi}(y_{0})-\psi_{\chi}(x)|+|\psi_{\chi}(y_{0})-\psi_{\chi}(x_{0})|=2O\left(\frac{1}{p^{b\omega_{\chi}}}\right)$

Since the right side goes to $0$ uniformly in $x_{0}$ as $a\rightarrow\infty$,
it follows that $\psi_{\chi}(x)$ is uniformly continuous in $[1,\infty)$.
Uniform continuity on sets bounded away from $0$ follows as mentioned in the
beginning of the proof. ∎

We also have a near-inverse of theorem 3.2, that only leaves out a tiny edge
case. To do this, we introduce a new definition.

######  Definition 3.6.

A row-dominant character $\chi$ is a character $\chi$ of modulus $p$ such that
there is a $b<p$ such that $|T_{\chi}(n)|>|\phi_{\chi}(p)|$.

######  Remark 3.1.

A character $\chi$ would be neither row-regular or row-dominant if there is a
$0\leq b<p$ such that $|T_{\chi}(b)|=|\phi_{\chi}(p)|$, but there is no $0\leq
b<p$ such that $|T_{\chi}(b)|>|\phi_{\chi}(p)|$.

######  Theorem 3.7.

If $\chi$ is a row-dominant character, then $\phi_{\chi}(n)$ is not
$O(n^{\theta_{\chi}})$.

###### Proof.

Suppose for the sake of contradiction that $\phi_{\chi}(n)$ is
$O(n^{\theta_{\chi}})$. Then let $b$ be the integer such that $0\leq b<p$ and
$|T_{\chi}(b)|>|\phi_{\chi}(p)|$ whose existence is guaranteed by row-
dominance. Now define the integer sequence
$\\{n_{k}\\}_{k>0}=(\sum_{j=0}^{k-1}bp^{j})$. We then compute
$\phi_{\chi}(n_{k}+1)-\phi_{\chi}(n_{k})$

$\phi_{\chi}(n_{k}+1)-\phi_{\chi}(n_{k})=T_{\chi}(n_{k})=\prod_{i=0}^{k-1}T_{\chi}(b)=T_{\chi}(b)^{k}$

Where in the last equality we use equation 1. Therefore

$\displaystyle\frac{\phi_{\chi}(n_{k}+1)}{(p^{k})^{\theta_{\chi}}}-\frac{\phi_{\chi}(n_{k})}{(p^{k})^{\theta_{\chi}}}=$
$\displaystyle\frac{T_{\chi}(b)^{k}}{(p^{k})^{\theta_{\chi}}}$
$\displaystyle\left|\frac{\phi_{\chi}(n_{k}+1)}{(p^{k})^{\theta_{\chi}}}\right|+\left|\frac{\phi_{\chi}(n_{k})}{(p^{k})^{\theta_{\chi}}}\right|\geq$
$\displaystyle\left|\frac{T_{\chi}(b)^{k}}{(p^{k})^{\theta_{\chi}}}\right|.$

Now, by our assumption, for sufficiently large $n$ we have
$|\phi_{\chi}(n)/(n^{\theta_{\chi}})|\leq\alpha$ for some real number
$\alpha$. We also note that
$|\phi_{\chi}(n_{k}+1)/(p^{k})^{\theta_{\chi}}|\leq|(\phi_{\chi}(n_{k}+1)/(n_{k}+1)^{\theta_{\chi}}|\leq\alpha$
for sufficiently large $k$. This means we have

$\displaystyle
2\alpha\geq\left|\frac{T_{\chi}(b)}{(p^{k})^{\theta_{\chi}}}\right|\geq\Bigr{|}\frac{T_{\chi}(b)}{\phi_{\chi}(p)^{k}}\Bigr{|}.$

However, since $|T_{\chi}(b)|>|\phi_{\chi}(p)|$, the right hand side of the
above equation is unbounded, so it cannot be bounded by $2\alpha$. This is a
contradiction, so $\phi_{\chi}(n)$ is not $O(n^{\theta_{\chi}})$.

∎

There is one more theorem on the growth rate of $\phi_{\chi}(n)$. This one
allows us to bound the growth rate of $\phi_{\chi}(n)$ for non-row-regular
characters $\chi$. To do this, we will define the real number $\rho_{\chi}$

$\rho_{\chi}=\max\\{\mathfrak{R}(\log_{p}(T_{\chi}(b))):0\leq b<p\\}.$

######  Theorem 3.8.

Let $\chi$ be not row-regular and let $\varepsilon>0$. then
$\phi_{\chi}(n)=O(n^{\rho_{\chi}+\varepsilon})$.

###### Proof.

This proof follows an outline very similar to 3.2. We define a sequence
$\\{\alpha_{k}\\}_{k>0}$ as

$\alpha_{k}=\max\left\\{\left|\frac{\phi_{\chi}(n)}{n^{\rho_{\chi}+\varepsilon}}\right|:p^{k-1}<n\leq
p^{k}\right\\}$

We will show that
$\alpha_{k+1}\leq\alpha_{k}+p^{\rho_{\chi}+\varepsilon}\alpha_{1}q^{k}$ for
$q<1$. We consider some $n$ such that $p^{k}<n\leq p^{k+1}$ and
$|\phi_{\chi}(n)/n^{\rho_{\chi}+\varepsilon}|=\alpha_{k+1}$, and write
$n=pm+b$ for $p^{k-1}<m\leq p^{k}$ and $0\leq b<p$. Then using both parts of
lemma 2.1 we see that

$\displaystyle\alpha_{k+1}=$
$\displaystyle\left|\frac{\phi_{\chi}(pm+b)}{n^{\rho_{\chi}+\varepsilon}}\right|$
$\displaystyle\leq$
$\displaystyle\frac{1}{(pm)^{\rho_{\chi}+\varepsilon}}\left|\phi_{\chi}(p)\phi_{\chi}(m)+\phi_{\chi}(b)T_{\chi}(m)\right|$
$\displaystyle\leq$
$\displaystyle\frac{1}{(pm)^{\rho_{\chi}+\varepsilon}}\big{(}|\phi_{\chi}(p)||\phi_{\chi}(m)|+|\phi_{\chi}(b)||T_{\chi}(m)|\big{)}.$

Since $b\leq p$ we know
$\frac{\phi_{\chi}(b)}{p^{\rho_{\chi}+\varepsilon}}\leq\alpha_{1}$.
Furthermore, since $\chi$ is not row regular,
$\frac{\phi_{\chi}(p)}{p^{\rho_{\chi}+\varepsilon}}\leq 1$. Therefore

$\displaystyle\alpha_{k+1}\leq$
$\displaystyle\frac{|\phi_{\chi}(m)|}{m^{\rho_{\chi}+\varepsilon}}+\alpha_{1}\frac{|T_{\chi}(m)|}{m^{\rho_{\chi}+\varepsilon}}$
$\displaystyle\leq$
$\displaystyle\alpha_{k}+\alpha_{1}\frac{T_{\chi}(m)}{(p^{k-1})^{\rho_{\chi}+\varepsilon}}$

Since $m$ is a $k$ digit number, we can use 1 to write
$|T_{\chi}(m)|=\prod_{j=0}^{k-1}|T_{\chi}(d_{j})|$, where $d_{j}$ are the
$p$-ary digits of $m$. Taking the largest possible value of $|T_{\chi}(m)|$,
we maximise each entry in the product to get
$|T_{\chi}(m)|\leq\prod_{j=0}^{k-1}\max\\{|T_{\chi}(t)|:0\leq
t<p\\}=(\max\\{|T_{\chi}(t)|:0\leq t<p\\})^{k}$. With this in mind, we let
$q=\max\\{|T_{\chi}(t)|:0\leq t<p\\}/(p^{\rho_{\chi}+\varepsilon})$, and the
definition of $\rho_{\chi}$ implies $q<1$. This gives

$\displaystyle\alpha_{k+1}\leq$
$\displaystyle\alpha_{k}+|p^{\rho_{\chi}+\varepsilon}|\alpha_{1}\frac{(\max\\{|T_{\chi}(t)|:0\leq
t<p\\})^{k}}{(p^{k})^{\rho_{\chi}+\varepsilon}}$ $\displaystyle\leq$
$\displaystyle\alpha_{k}+p^{\rho_{\chi}+\varepsilon}\alpha_{1}q^{k}.$

Therefore
$\alpha_{k+1}\leq\alpha_{k}+p^{\rho_{\chi}+\varepsilon}\alpha_{1}q^{k}$. Since
the geometric series
$\sum_{k=1}^{\infty}p^{\rho_{\chi}+\varepsilon}\alpha_{1}q^{k}$ converges,
$\\{\alpha_{k}\\}$ must have an upper bound, which means that
$\phi_{\chi}(n)=O(n^{\rho_{\chi}+\varepsilon})$. ∎

The behavior of $\phi_{\chi}(n)$ for row-dominant characters $\chi$ is
extremely erratic, as some portions of it (for example the $n_{k}$ discussed
in 3.7) grow faster than $O(n^{\theta_{\chi}})$, whereas other parts (like
$p^{k}$) grow like $O(n^{\theta_{\chi}})$. However, as the previous theorem
described, these are also the slowest growing $\phi_{\chi}(n)$, as
$\rho_{\chi}\leq 1$ in general. So they do not have a significant contribution
to the formula in lemma 2.2.

##  4 Row-Regularity and the Fundamental Domain of Pascal’s Triangle mod $p$

Thanks to Lucas’ theorem and the result of [GW92], study of Pascal’s triangle
mod $p$ can be reduced to understanding of it’s fundamental domain, that is
$\tbinom{n}{m}\text{ mod }p$ for $n,m<p$. Therefore, strong understanding of
the fundamental domain leads to strong understanding of the entire triangle.
This can be seen in the relative simplicity of the theory of nonzero residues
in Pascal’s triangle mod $p$, which largely relies on the fact that the it is
easy to see if a residue in the fundamental domain is nonzero. If $n,m<p$ then
$\tbinom{n}{m}\equiv 0\text{ mod }p$ if and only if $m>n$.

With this in mind, a reasonable place to look to make progress would be by
studying the fundamental domain. However, our knowledge of the fundamental
domain is largely conjectural. Roughly, the fundamental domain looks like
this:

$1$ |  |  |  |  |  |
---|---|---|---|---|---|---
$1$ | $1$ |  |  |  |  |
$1$ | $?$ | $1$ |  |  |  |
$\vdots$ | $\vdots$ | $\ddots$ | $\ddots$ |  |  |
$1$ | $?$ | $?$ | $\ddots$ | $1$ |  |
$1$ | $?$ | $?$ | $\ldots$ | $?$ | $1$ |
$1$ | $-1$ | $1$ | $\ldots$ | $1$ | $-1$ | $1$

There are $1$s running down two sides, and alternative $1$s and $-1$s on the
bottom side of the triangle. Inside the triangle, there appears to be a
roughly even distribution of each nonzero residue class. This suggests the
following conjecture of [Bra+19]:

######  Conjecture 4.1.

As the prime modulus $p$ goes to infinity, the following asymptotics hold:

  * •

$A_{p}(1)\sim 3p$

  * •

$A_{p}(-1)\sim p$

  * •

If $r\neq-1,0,1$, then $A_{p}(r)\sim\tfrac{p}{2}$

We wish to make a heuristic argument to motivate this conjecture and other
conjectures about the fundamental domain. In particular, let $n,m<p-1$ with
$m<n$, $m\neq n$. We wish to model the value of $\binom{n}{m}\text{ mod }p$ as
a random variable $X_{n,m}$ taking values in $\\{1,2,\ldots p-1\\}$ with
probability $\frac{1}{p-1}$. We assume that $X_{n_{1},m_{1}}$ and
$X_{n_{2},m_{2}}$ are independent unless $n_{1}=n_{2}$ and $m_{1}=m_{2}$ or
$m_{1}=n_{1}-m_{2}$, in which case they are always equal.

Using this, we can motivate conjecture 4.1.

######  Theorem 4.2.

Under the assumptions of the above random model, conjecture 4.1 holds with
probability $1$.

###### Proof.

Let $\mathbbold{1}_{k}(x)$ be the function that returns $1$ when $k=x$ and $0$
otherwise. Then we have

$A_{p}(r)=\sum_{n=0}^{p-1}\sum_{m=0}^{n}\mathbbold{1}_{r}\left(\binom{n}{m}\right).$

The behavior for $n=p-1$, $m=n$ or $m=0$ is entirely predictable, so we
consider the inside of the triangle. Since there is no inside of the triangle
for $p=2,3$, we assume $p>3$ for the rest of this proof. Using our random
model, we define a random variable $Y$ that determines the influence of the
unpredictable inner region.

$Y=\sum_{n=2}^{p-2}\sum_{m=1}^{n-1}\mathbbold{1}_{r}(X_{n,m})=2\sum_{n=2}^{p-2}\sum_{m=1}^{\lfloor(n-1)/2\rfloor}\mathbbold{1}_{r}(X_{n,m})+\sum_{n=1}^{\lfloor(p-2)/2\rfloor}\mathbbold{1}_{r}(X_{2n,n})$

The first sum is a binomial distribution with probability $\frac{1}{p-1}$ and
$\frac{(p-3)^{2}}{4}$ trials. The second sum is a binomial distribution with
probability $\frac{1}{p-1}$ and $\frac{p-3}{2}$ trials. Therefore, for any
$r\neq 0$, we have

$\displaystyle\mathbb{E}[Y]=$
$\displaystyle\frac{1}{p-1}\left(2\frac{(p-3)^{2}}{4}+\frac{p-3}{2}\right)=\frac{p^{2}-5p+6}{2p-2}\sim\frac{p}{2}$
$\displaystyle\text{Var}[Y]=$
$\displaystyle\frac{p-2}{(p-1)^{2}}\left(4\frac{(p-3)^{2}}{4}+\frac{p-3}{2}\right)=\frac{2p^{3}-15p^{2}+37p-30}{2p^{2}-4p+2}\sim\frac{p}{2}$

Adding back in the adjustments for the outside of the triangle, we have
$\mathbb{E}[A_{p}(1)]=\mathbb{E}[Y]+2p-1+(p+1)/2\sim 3p$,
$\mathbb{E}[A_{p}(-1)]=\mathbb{E}[Y]+(p-1)/2\sim p$, and if $r\neq-1,0,1$, we
have $\mathbb{E}[A_{p}(r)]=\mathbb{E}[Y]\sim p/2$. Since the standard
deviation $\sigma_{A_{p}(r)}=\sigma_{Y}\sim\sqrt{p/2}=o(p)$, it follows that
4.1 holds with probability $1$. ∎

Next, we turn our attention to predicting the behavior of $\phi_{\chi}(p)$
using the same probabilistic model. We begin essentially the same way as the
previous theorem, as we have the identity

$\phi_{\chi}(p)=\sum_{n=0}^{p-1}\sum_{m=0}^{n}\chi\\!\left(\\!\binom{n}{m}\\!\right).$

We once again ignore the border of the triangle as it is entirely predictable,
and define a random variable $Y$ that determines the influence of the inside.

$Y=\sum_{n=2}^{p-2}\sum_{m=1}^{n-1}\chi(X_{n,m})=2\sum_{n=2}^{p-2}\sum_{m=1}^{\lfloor(n-1)/2\rfloor}\chi(X_{n,m})+\sum_{n=1}^{\lfloor(p-2)/2\rfloor}\chi(X_{2n,n}).$

We now reduce to the case where $\chi$ is nonprincipal. We see that
$\chi(X_{n,m})$ is a random variable with mean $\mathbb{E}[\chi(X_{n,m})]=0$.
This gives us the mean $\mathbb{E}[Y]=0$. For the variance of $Y$, We have
that $\text{Var}[\chi(X_{n,m})]=1$. Further, each of the distinct
$\chi(X_{n,m})$ in the sums are uncorrelated as they are independent. This
gives us the variance

$\text{Var}[Y]=4\left(\frac{(p-3)^{2}}{4}\right)+\frac{p-3}{2}=\frac{2p^{2}-11p+15}{2}\sim
p^{2}.$

Adding back the predictable component, for a nonprincipal even character
$\chi$, we have that $\mathbb{E}[\phi_{\chi}(p)]=\mathbb{E}[Y]+3p=3p$, for an
odd character, we have $\mathbb{E}[\phi_{\chi}(p)]=\mathbb{E}[Y]+2p+1\sim 2p$.

This probabilistic model implies that many characters should be row regular
(as a character is certainly row regular if $\phi_{\chi}(p)>p$.) However, the
high variance implies that there should be many non-row-regular characters.
These predictions turn out to fit the data quite nicely.

If we compute $\phi_{\chi}(p)/p$ for $\chi\neq\chi_{0}$ and $p<100$ (see
section 6), and plot them on the complex plane, we see this picture:

Red: $\phi_{\chi}(p)/p$ for $\chi(-1)=-1$. Blue: $\phi_{\chi}(p)/p$ for
$\chi(-1)=1$.

And we see that most values tend to be around $2$ and $3$, though there is
relatively large variance. Computation also yields the following result:

######  Proposition.

Not all characters $\chi$ are row-regular.

###### Proof.

Let $p=37$ and $\chi(2)=e^{\frac{20\pi i}{36}}$. Then a computer calculation
(see section 6) shows

$\phi_{\chi}(p)=33e^{\frac{20\pi i}{36}}-3e^{\frac{16\pi
i}{36}}-8e^{\frac{12\pi i}{36}}-21e^{\frac{8\pi i}{36}}-18e^{\frac{4\pi
i}{36}}\approx 33.7472651243456+2.96112697681136i.$

Whereas

$T_{\chi}(36)=37.$

∎

######  Remark 4.1.

This is also the smallest non-row-regular character. It is also row-dominant.

Now, we turn our attention to bounding $\phi_{\chi}(p)$, for nonprincipal
character $\chi$, as this will ultimately allow us to prove 1.3. First, we’ll
demonstrate a trivial bound.

######  Lemma 4.3.

For a prime $p$ and nonprincipal character $\chi$, we have
$|\phi_{\chi}(p)|<\frac{p(p+1)}{2}$.

###### Proof.

Let $g$ be a generator of $(\mathbb{Z}/p\mathbb{Z})^{\times}$. The definition
of $\phi_{\chi}(n)$ and the triangle inequality tell us

$\displaystyle|\phi_{\chi}(p)|=\left|\sum_{n=0}^{p-1}\sum_{m=0}^{n}\chi\\!\left(\\!\binom{n}{m}\\!\right)\right|\leq$
$\displaystyle\left|\chi\\!\left(\\!\binom{0}{0}\\!\right)+\chi\\!\left(\\!\binom{1}{g}\right)\\!\right|+\sum_{n=1}^{p-1}\sum_{\begin{subarray}{c}m=0\\\
m\neq 1\\\ \text{if
}n=g\end{subarray}}^{n}\left|\chi\\!\left(\\!\binom{n}{m}\\!\right)\right|$
$\displaystyle<$ $\displaystyle
2+\left(\frac{p(p+1)}{2}-2\right)=\frac{p(p+1)}{2}.$

The one step here that requires further consideration is the strict
inequality. $\chi(\tbinom{0}{0})=\chi(1)=1$, and
$\chi(\tbinom{g}{1})=\chi(g)\neq 1$ because $\chi(g)=1$ would imply that
$\chi$ is principal. Therefore they have different arguments, so the triangle
inequality becomes strict. ∎

Next, we prove an extremely weak (but nontrivial) upper bounds for
$|\phi_{\chi}(p)|$ that is an $O(p\sqrt{p})$ improvement on the trivial bound.

######  Theorem 4.4.

Fix a prime $p$ and nonprincipal character $\chi$. Then

$\phi_{\chi}(p)\leq\frac{p^{2}-2p\lfloor\sqrt{p}\rfloor+\sqrt{p}\lfloor\sqrt{p}\rfloor^{2}+p+\sqrt{p}\lfloor\sqrt{p}\rfloor+\lfloor\sqrt{p}\rfloor^{2}-2\sqrt{p}+\lfloor\sqrt{p}\rfloor}{2}.$

###### Proof.

We begin with a formula for $\phi_{\chi}(p)$:

$|\phi_{\chi}(p)|=\sum_{n=0}^{p-1}\sum_{m=0}^{p-1}\chi\\!\left(\\!\binom{m}{n}\\!\right).$

Now we apply the triangle inequality and separate this sum in to four parts,
which we will analyze separately.

$|\phi_{\chi}(p)|\leq\left|\sum_{m=0}^{p-1}\chi\\!\left(\\!\binom{m}{0}\\!\right)\right|+\left|\sum_{m=0}^{p-1}\chi\\!\left(\\!\binom{m}{1}\\!\right)\right|+\sum_{n=2}^{\lfloor\sqrt{p}\rfloor}\left|\sum_{m=0}^{p-1}\chi\\!\left(\\!\binom{m}{n}\\!\right)\right|+\sum_{n=\lfloor\sqrt{p}\rfloor+1}^{p-1}\left|\sum_{m=0}^{p-1}\chi\\!\left(\\!\binom{m}{n}\\!\right)\right|.$

For the first sum, $\binom{m}{0}=1$ for all $m$, so the first term becomes
$p$. In the second term, we note that $\binom{m}{1}=m$, so the sum is $0$ by
orthogonality of Dirichlet characters. In the third sum, we note that
$\binom{m}{n}$ is a degree $n$ polynomial with exactly $n$ distinct roots mod
$p$, so the conditions of the Weil bounds [Sch76] for character sums of
polynomials are met. This gives us
$\left|\sum_{m=0}^{p-1}\chi\left(\binom{m}{n}\right)\right|\leq n\sqrt{p}$.
Finally, for the final term we know that $\binom{m}{n}=0$ for $m<n$, and since
$|\chi(q)|=1$, so by the triangle inequality we have
$\left|\sum_{m=0}^{p-1}\chi\left(\binom{m}{n}\right)\right|\leq\sum_{m=0}^{p-1}\left|\left(\binom{m}{n}\right)\right|\leq
q-n$. Combining these together, we get

$\displaystyle\phi_{\chi}(p)\leq$ $\displaystyle
p+\sum_{n=2}^{\lfloor\sqrt{p}\rfloor}n\sqrt{p}+\sum_{n=\lfloor\sqrt{p}\rfloor+1}^{p-1}(p-n)$
$\displaystyle=$ $\displaystyle
p+\sqrt{p}\frac{\lfloor\sqrt{p}\rfloor(\lfloor\sqrt{p}\rfloor+1)}{2}-\sqrt{p}+\frac{(p-\lfloor\sqrt{p}\rfloor-1)(p-\lfloor\sqrt{p}\rfloor)}{2}$
$\displaystyle=$ $\displaystyle\frac{p^{2}-2\lfloor\sqrt{p}\rfloor
p+\sqrt{p}\lfloor\sqrt{p}\rfloor^{2}+p+\sqrt{p}\lfloor\sqrt{p}\rfloor+\lfloor\sqrt{p}\rfloor^{2}-2\sqrt{p}+\lfloor\sqrt{p}\rfloor}{2}$

∎

We can simplify the inequality to a form that looks nicer with $x-1<\lfloor
x\rfloor\leq x$.

######  Corollary 4.5.

We have the weaker but nicer looking inequality

$\phi_{\chi}(p)<\frac{p^{2}-p\sqrt{p}+5p-\sqrt{p}}{2}.$

###### Proof.

We start with 4.4 and use $x-1<\lfloor x\rfloor\leq x$.

$\displaystyle\phi_{\chi}(p)\leq$
$\displaystyle\frac{p^{2}-2p\lfloor\sqrt{p}\rfloor+\sqrt{p}\lfloor\sqrt{p}\rfloor^{2}+p+\sqrt{p}\lfloor\sqrt{p}\rfloor+\lfloor\sqrt{p}\rfloor^{2}+\lfloor\sqrt{p}\rfloor}{2}$
$\displaystyle<$
$\displaystyle\frac{p^{2}-2p(\sqrt{p}-1)+\sqrt{p}^{3}+p+\sqrt{p}^{2}+\sqrt{p}^{2}-2\sqrt{p}+\sqrt{p}}{2}$
$\displaystyle=$ $\displaystyle\frac{p^{2}-p\sqrt{p}+5p-\sqrt{p}}{2}.$

∎

These bounds are clearly not very strong, as suggested by the diagram on page
10. However, to improve this bound we would need a much better understanding
of the behavior of the fundamental domain.

##  5 Conclusion

We now have the necessary knowledge to prove the strongest version of theorem
1.3

###### Proof of theorem 1.3.

Using lemma 2.2 we write

$A_{n}(r)=\frac{1}{p-1}\sum_{\chi}\overline{\chi(r)}\phi_{\chi}(n).$

Next, we bring out the $\chi=\chi_{0}$ term and use theorem 3.2 on the row
regular terms and theorem 3.8 on the non-row-regular terms.

$A_{n}(r)=\frac{\phi_{\chi_{0}}}{p-1}+\frac{1}{p-1}\left(\sum_{\chi\text{
rr}}O(n^{\theta_{\chi}})+\sum_{\chi\text{
nrr}}O(n^{\rho_{\chi}+\varepsilon})\right).$

Where the first sum is over row-regular pairs and the second is over non-row-
regular pairs. Now, if we define
$\vartheta_{\varepsilon}=\max(\\{\mathfrak{R}(\log_{p}(\phi_{\chi}(p))):\chi\neq\chi_{0}\\}\cup\\{1+\varepsilon\\})$,
then this reduces to

$A_{n}(r)=\frac{\phi_{\chi_{0}}}{p-1}+O(n^{\vartheta_{\varepsilon}}).$

We know $\phi_{\chi}(n)$ for row-regular pairs is
$O(n^{\vartheta_{\varepsilon}})$ by construction and theorem 3.2. For the non-
row-regular characters, $\phi_{\chi}(n)$ is also
$O(n^{\vartheta_{\varepsilon}})$ by theorem 3.8 since $T_{\chi}(b)<p$.

But by lemma 4.3, we know that
$\vartheta_{\epsilon}<\log_{p}(\frac{p(p+1)}{2})$ for sufficiently small
epsilon. Furthermore, [Wil98] showed that there are real $\alpha,\beta$ such
that $\beta n^{\log_{p}(\frac{p(p+1)}{2})}\phi_{\chi_{0}}(n)\leq\alpha
n^{\log_{p}(\frac{p(p+1)}{2})}$. So we have

$\displaystyle A_{n}(r)=$
$\displaystyle\frac{\phi_{\chi_{0}}(n)}{p-1}+o(\phi_{\chi_{0}}(n))$
$\displaystyle A_{n}(r)\sim$
$\displaystyle\frac{\phi_{\chi_{0}}(n)}{p-1}=\frac{\phi_{p}(n)}{p-1}.$

∎

For a fixed prime $p$, the formula
$A_{n}(r)=\frac{\phi_{p}(n)}{p-1}+O(n^{\vartheta_{\varepsilon}})$ is
significantly better than simply theorem 1.3, though it requires knowledge of
the fundamental domain of that prime (specifically calculating it’s
$\vartheta_{\varepsilon}$.) On the other hand, theorem 4.4 gives a slight
improvement to theorem 1.3’s bound that applies to all primes. Finally, we
finish with some conjectures.

Our first conjecture is inspired by the probabilistic calculations done in
section 4.

######  Conjecture 5.1.

Let $A_{p}=\\{\phi_{\chi}(p):\chi(-1)=1,\chi\neq\chi_{0}\\}$ and
$B_{p}=\\{\phi_{\chi}(p):\chi(-1)=-1\\}$. Let $\mu_{A_{p}}$ and $\mu_{B_{p}}$
be the means of $A_{p}$ and $B_{p}$, then as $p$ goes to infinity,

$\mu_{A_{p}}\sim 3p\qquad\mu_{B_{p}}\sim 2p$

######  Remark 5.1.

While this is inspired by the probabilistic calculations done in 4, it’s not
clear that this follows with probability $1$ under those assumptions. One
would wish to use the central limit theorem, but that requires the assumption
that $\phi_{\chi}(p)$ are independent for distinct $\chi$. However, this is
not the case. Indeed, if $\chi$ is an injection from $\mathbb{Z}/p\mathbb{Z}$
to $\mathbb{C}$, then the value of $\phi_{\chi}(p)$ determines the value of
$\phi_{\psi}(p)$ for any other character $\psi$.

Once again inspired by the probabilistic calculations, we suspect that the
value of $\phi_{\chi}(p)$ has quite a lot of variance, which would suggest
that $|\phi_{\chi}(p)|<p$ quite often, which gives many opportunities for
$\chi$ to be row dominant. This heuristic argument along with some numerical
evidence suggest the following conjecture.

######  Conjecture 5.2.

There are infinitely many row-dominant characters.

## Acknowledgements

I would like to thank Professor All for his feedback.

## References

  * [Bra+19] David M. Bradley et al.  “On the Relative Frequency of Residue Classes in PASCAL’S Triangle Modulo a Prime”  In _Fractals_ 27.6, 2019, pp. 1950098–21  DOI: 10.1142/S0218348X19500981
  * [Fin47] N.. Fine  “Binomial Coefficients Modulo a Prime”  In _The American Mathematical Monthly_ 54.10 Mathematical Association of America, 1947, pp. 589–592  URL: http://www.jstor.org/stable/2304500
  * [GW92] Richard Garfield and Herbert S Wilf  “The distribution of the binomial coefficients modulo p”  In _Journal of Number Theory_ 41.1, 1992, pp. 1–5  DOI: https://doi.org/10.1016/0022-314X(92)90078-4
  * [Har77] Heiko Harborth  “Number of Odd Binomial Coefficients”  In _Proceedings of the American Mathematical Society_ 62.1 American Mathematical Society, 1977, pp. 19–22  URL: http://www.jstor.org/stable/2041936
  * [Sch76] Wolfgang M. Schmidt  “Character sums and exponential sums”  In _Equations over Finite Fields An Elementary Approach_ Berlin, Heidelberg: Springer Berlin Heidelberg, 1976, pp. 38–91  DOI: 10.1007/BFb0080440
  * [Ste89] Alan H. Stein  “Binomial coefficients not divisible by a prime”  In _Number Theory_ Berlin, Heidelberg: Springer Berlin Heidelberg, 1989, pp. 170–177
  * [Wil98] Brad Wilson  “Asymptotic behavior of Pascal’s triangle modulo a prime”  In _Acta Arithmetica_ 83.2, 1998, pp. 105–116  URL: http://eudml.org/doc/207108

##  6 Appendix

All code is written in python with the Sagemath library. They were run on my
personal laptop (Lenovo ThinkPad P1 Gen 4). The numerical calculations should
not be seen as significant numerical research, and are instead simple programs
to create small visualizations and compute small counterexamples.

Code to plot $\phi_{\chi}(p)/p$ for $p<100$:

⬇

1def tri(p):

2 A = []

3 for i in range(p):

4 A += [[]]

5 for j in range(p):

6 if i == 0 and j == 0:

7 A[i] += [1]

8 elif i == 0:

9 A[i] += [0]

10 elif j == 0:

11 A[i] += [1]

12 else:

13 A[i] += [(A[i - 1][j - 1] + A[i - 1][j]) % p]

14

15 return A

16

17D = []

18E = []

19for n in range(1, 30):

20 p = nth_prime(n)

21 B = tri(p)

22 for chi in DirichletGroup(p):

23 C = []

24 for i in range(p):

25 C += [[]]

26 for j in range(p):

27 C[i] += [chi(B[i][j])]

28 sum = 0

29 for i in range(p):

30 for j in range(p):

31 sum += C[i][j]

32 if (sum != p * (p + 1) / 2):

33 if (chi(p - 1) == -1):

34 D += [sum / p]

35 else:

36 E += [sum / p]

37

38G = list_plot(D,size=5,color=’red’)

39P = list_plot(E,size=5,color=’blue’)

40P + G

Code to check for non-row-regular characters $\chi$.

⬇

1def tri(p):

2 A = []

3 for i in range(p):

4 A += [[]]

5 for j in range(p):

6 if i == 0 and j == 0:

7 A[i] += [1]

8 elif i == 0:

9 A[i] += [0]

10 elif j == 0:

11 A[i] += [1]

12 else:

13 A[i] += [(A[i - 1][j - 1] + A[i - 1][j]) % p]

14

15 return A

16

17for n in range(1,50):

18 p = nth_prime(n)

19 print(p)

20 B = tri(p)

21 row_regular = true

22 for chi in DirichletGroup(p):

23 C = []

24 for i in range(p):

25 C += [[]]

26 for j in range(p):

27 C[i] += [chi(B[i][j])]

28 sum = 0

29 Tsum = []

30 for i in range(p):

31 Tsum += [0]

32 for j in range(p):

33 sum += C[i][j]

34 Tsum[i] += C[i][j]

35

36 for i in range(p):

37 if abs(Tsum[i]) >= abs(sum):

38 print(chi,i)

39 row_regular = false

A search of the first 50 primes yields the following table of non-row-regular
characters. We note that if $\chi$ is not row regular, $\overline{\chi}$ is
also not row-regular, so we only include one character in each conjugacy pair.

$p$ | $\chi$
---|---
$37$ | $\chi(2)=e^{\frac{20\pi i}{36}}$
$47$ | $\chi(5)=e^{\frac{36\pi i}{46}}$
$97$ | $\chi(5)=e^{\frac{44\pi i}{96}}$
$97$ | $\chi(5)=e^{\frac{92\pi i}{96}}$
$101$ | $\chi(2)=e^{\frac{56\pi i}{100}}$
$109$ | $\chi(6)=e^{\frac{96\pi i}{108}}$
$113$ | $\chi(3)=e^{\frac{16\pi i}{112}}$
$131$ | $\chi(2)=e^{\frac{48\pi i}{130}}$
$137$ | $\chi(3)=e^{\frac{24\pi i}{136}}$
$139$ | $\chi(2)=e^{\frac{52\pi i}{138}}$
$139$ | $\chi(2)=e^{\frac{64\pi i}{138}}$
$p$ | $\chi$
---|---
$149$ | $\chi(2)=e^{\frac{52\pi i}{148}}$
$149$ | $\chi(2)=e^{\frac{120\pi i}{148}}$
$149$ | $\chi(2)=e^{\frac{136\pi i}{148}}$
$151$ | $\chi(6)=e^{\frac{24\pi i}{150}}$
$157$ | $\chi(5)=e^{\frac{60\pi i}{156}}$
$157$ | $\chi(5)=e^{\frac{64\pi i}{156}}$
$163$ | $\chi(2)=e^{\frac{52\pi i}{162}}$
$173$ | $\chi(2)=e^{\frac{152\pi i}{172}}$
$199$ | $\chi(3)=e^{\frac{116\pi i}{198}}$
$223$ | $\chi(3)=e^{\frac{56\pi i}{222}}$
$223$ | $\chi(3)=e^{\frac{76\pi i}{222}}$