# An Effective Data Creation Pipeline to Generate High-quality Financial
Instruction Data for Large Language Model

Ziao Wang  Jianning Wang  Junda Wu  Xiaofeng Zhang111Corresponding author.
Email<EMAIL_ADDRESS>School of Computer Science and Technology,
Harbin Institute of Technology, Shenzhen, China
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

At the beginning era of large language model, it is quite critical to generate
a high-quality financial dataset to fine-tune a large language model for
financial related tasks. Thus, this paper presents a carefully designed data
creation pipeline for this purpose. Particularly, we initiate a dialogue
between an AI investor and financial expert using ChatGPT and incorporate the
feedback of human financial experts, leading to the refinement of the dataset.
This pipeline yielded a robust instruction tuning dataset comprised of 103k
multi-turn chats. Extensive experiments have been conducted on this dataset to
evaluate the model’s performance by adopting an external GPT-4 as the judge.
The promising experimental results verify that our approach led to significant
advancements in generating accurate, relevant, and financial-style responses
from AI models, and thus providing a powerful tool for applications within the
financial sector.

##  1 Introduction

In recent years, the abilities of pre-trained language models have experienced
significant enhancements, with instruction-tuning playing a pivotal role in
these advancements. Despite these improvements, a critical gap remains in the
application of these models within the financial sector, i.e., inaccurate or
irrelevant responses from these models could lead to significant financial
implications, underscoring the importance of enhancing their performance for
financial tasks.

In the literature, several approaches have been proposed Taori et al. (2023);
Xu et al. (2023) to generate instruction data to fine-tune a large language
model on the down-stream task. Although these approaches well employed the
SOTA LLMs like GPT-4 OpenAI (2023), the quality of the generated data are not
suitable for financial related tasks. To cope with these challenges, this
paper introduces a novel data creation pipeline designed for these high-stakes
domains. The cornerstone of our approach is to leverage the in-context
learning ability of contemporary large language models Wei et al. (2023); Chen
et al. (2022) and supplement it with a high-quality corpus sourced directly
from the financial domain, such as financial reports. This allows us to
provide both real-world information and processed knowledge, thereby improving
the model’s ability to generate accurate and relevant responses.

Figure 1: An illustrating example of the data collection pipeline.

As illustrated in Figure 1, our approach begins with a high-quality corpus
such as a financial report. Using ChatGPT’s strong in-context learning
ability, we simulate a dialogue between an investor and a financial expert.
The generated questions are clustered and then shown to human financial
experts for refinement and feedback. This process helps in pruning low-quality
or non-financial style questions, which are then sampled to continue the data
collection pipeline. Our method resulted in a dataset consisting of 103k
multi-turn chats, which was used for instruction tuning on open-sourced
language models such as LLama Wei et al. (2023). We further conducted
comprehensive tests on the models’ performance on financial tasks, including a
GPT-4 evaluation with specifically created questions. The contributions of
this paper are summarized as follows:

  * •

We design a novel data creation pipeline specifically designed for high-stakes
domains, such as finance, and we generate a high-quality instruction tuning
dataset consisting of 103k multi-turn chats.

  * •

We automatically generate a set of high quality financial questions which
could be used to comprehensively evaluate the model performance.

  * •

We trained a large language model using this dataset and extensively evaluated
the model performance. Both the dataset as well as the questions will be
released later for public use.

##  2 Related Work

Instruction tuning has emerged as a fundamental component in the advancement
of pre-trained language models. The large language models such as GPT-3 and
ChatGPT have achieved substantial enhancements using this technique. The
underlying idea is to align the model’s behavior with human values in a
specific domain by utilizing an instructional dataset.

#### Instruction-tuning on LLM

Ouyang et al. (2022) introduced InstructGPT, designed to comply with
instructions presented in natural language and produce useful responses. The
model performance exceeded that of GPT-3 after tuning under the instruction,
substantiating the beneficial impact of instruction tuning. Databricks (2023)
presented Dolly, an instruction-tuned large language model. Dolly was trained
on a dataset amalgamated from various sources, including the InstructGPT
dataset by OpenAI and a fresh dataset crafted by Databricks. This new dataset
encompasses instructions and outputs from real-world tasks undertaken by data
scientists and engineers. Dolly exhibited outstanding capabilities in tasks
that necessitated understanding and generating intricate text, alongside
following instructions. Köpf et al. (2023) proposed a large-scale dataset,
OpenAssistant Conversations, intended to expedite the advancement of aligned
language models. This dataset is the product of a crowdsourcing endeavor and
includes over 1.5 million messages from an excess of 10,000 contributors. The
authors also showcased the results of a user preference study, which
established that a model, Pythia-12B, fine-tuned on this dataset, represents a
formidable rival to OpenAI’s gpt-3.5-turbo model. Chiang et al. (2023) is an
open-source chatbot that was fine-tuned on user-shared dialogues gathered from
ShareGPT by using the LLaMA model Wei et al. (2023) and has demonstrated a
promising performance.

#### Automatic collection of instruction tuning data

The automated collection of instruction tuning data is of crucial
significance, considering the high costs and potential human bias associated
with crowdsourcing. Wang et al. (2022) proposed an innovative method termed
‘self-instruct’, leveraging a large language model to generate a diverse range
of instructions and associated inputs and outputs, thereby constructing a
novel training dataset. Taori et al. (2023) introduced Alpaca, a model fine-
tuned from Meta’s LLaMA Wei et al. (2023) 7B model, which was trained on 52K
instruction-following demonstrations created using text-davinci-003. The
authors postulate that Alpaca exhibits many behaviors akin to OpenAI’s text-
davinci-003, yet remains remarkably compact and is both cost-effective and
simple to reproduce. Xu et al. (2023) put forward a proposition to employ
ChatGPT to engage in dialogues with itself, consequently creating a novel
dataset for training.

Existing methodologies for automatically collecting instructional datasets
often employ a question seed as an initiation point. However, the answers are
purely generated based on the capabilities of the large language models in
use. This approach has a significant limitation as these models cannot
generate accurate factual knowledge autonomously. Our method proposes an
advancement in this regard, leveraging the powerful in-context learning
capabilities of Large Language Models (LLMs). We further enhance the quality
of generated data by enforcing adherence to knowledge derived from high-
quality corpora. This proposed approach facilitates a more nuanced and
accurate generation of responses, representing a significant step forward in
the instruction-tuning of pre-trained language models.

##  3 The Proposed Data Collection Pipeline

In this section, we detailed the proposed data collection pipeline. Our data
collection process consists of four main steps: (1) selecting a high-quality
corpus, (2) simulating dialogues, (3) expert revision on questions and (4)
sampling and augmenting the dataset. Through these steps, we were able to
construct a rich dataset that effectively bridges the gap between LLMs and the
specific requirements of the financial domain.

###  3.1 Data Source

Our collection pipeline begins with the integration of a high-quality corpus.
As our objective is to create a dataset pertinent to the Chinese financial
domain, we therefore decided to utilize the Brokerage Research Reports, which
we hereafter refer to as ‘financial reports’. These reports are authored by
financial professionals and embody a high standard of accuracy and expertise.
Furthermore, these reports are publically accessible, offering a robust and
readily available resource for our data collection efforts
222http://data.eastmoney.com/report/.

###  3.2 Simulating Dialogues

Once the corpus was selected, we employed the in-context learning ability of
ChatGPT to simulate an investor-financial expert conversation. We used the
content of the financial reports as the context for the dialogue. The model
was prompted to emulate an investor’s perspective, asking insightful questions
based on the information presented in the financial reports. Subsequently, it
responded to these queries from a financial expert’s viewpoint, utilizing the
facts and figures given in the report. An illustrative example of the deigned
prompt and the resulting conversation is respectively shown in the upper and
bottom part of Figure 1.

###  3.3 Expert Revision

After conducting the dialogue simulation, we compiled a list of questions
generated by the model. To ensure the diversity and quality of the data
collected, we implemented a two-stage expert review process.

In the first stage, the questions were grouped based on their thematic
similarity using a text clustering algorithm. Representative questions from
each cluster were sampled and passed to a panel of five financial experts to
evaluate the breadth of financial topics covered by the data. The experts were
tasked with determining whether the questions adequately covered a wide range
of financial topics. If any categories of financial topics were absent from
the clusters, the experts were instructed to contribute questions in those
areas. This process allowed us to identify any prevalent themes or concerns,
ensuring that our final dataset encompassed a comprehensive range of financial
discussions.

Theme: Risk and Investment Opportunities
---
What are the risk factors and future development prospects of [Company Name]?
What are the operational pressures and risks that the [Company Name] is facing
in the short term?
Which sectors will experience the most stable growth in the future business
development of the [Company Name]?
Theme: Company Financial Status
Will the [Company Name] raise funds for expansion? What will be the scale of
the expansion?
What is [Company Name]’s production capacity globally?
In Q4, what is the expected growth in shipments for [Company Name]?
Theme: New Energy Industry
What do you think is the impact of new energy vehicle production and sales
data on the lithium sector?
What role do you think the control of domestic lithium resources will play in
ensuring supply chain security for the future new energy industry?
The rising price of lithium resources, what kind of impact will it have on
China’s lithium battery industry and electric vehicle industry?
Table 1: Illustration of themes and questions through clustering process.

In the second stage, questions were randomly sampled and presented to a team
of financial experts for refinement. Their task was to identify and eliminate
any questions that were irrelevant, misleading, or inconsistent with typical
financial discourse. Any questions identified as such, as well as those with a
high degree of similarity (greater than 99%), were removed. This step was
crucial in ensuring the relevance and quality of our final dataset. As shown
in Table 1, we have, for the sake of illustration, randomly selected three
themes and typical questions within these themes. To enhance readability, we
have translated these examples into English.

###  3.4 Sampling and Data Augmentation

After the expert revision process, a random sample of the refined questions
was selected to be re-entered into the data collection pipeline. These
questions were used to stimulate further dialogues with the model, effectively
expanding the size and diversity of our dataset. This process of sampling and
augmentation was repeated multiple times.

The final result of our data collection process was a robust dataset of 103k
multi-turn chats and the statistics of the collected dataset are reported in
Table 2. The topic distribution of the collected dataset is shown in Figure 2.
This dataset served as a resource for instruction tuning, enabling the model
to generate precise and relevant responses when faced with financial queries.

| Mean | Q-5% | Q-95%
---|---|---|---
# dialog turns | 4.0 | 3.0 | 6.0
# words per question | 13.9 | 7.6 | 23.5
# words per answer | 78.3 | 46.9 | 116.9
# words per dialog | 714.5 | 426.0 | 1067.8
Table 2: Statistics of our collected dataset, ‘Q’ refers to quantile Figure 2:
Topic distribution of the collected dataset

##  4 Experiments

To systematically measure the impact of our data creation pipeline, we fine-
tuned state-of-the-art language models using our constructed dataset. The
following sub-sections shows the details of our experiments.

|  | xstory-cloze-zh | xnli-zh | pawsx-zh | xcopa-zh | xwinograd-zh
---|---|---|---|---|---|---
llama | llama-7b | 0.5493 | 0.3622 | 0.4910 | 0.5620 | 0.6369
llama-7b-lora | 0.5612 | 0.3491 | 0.4965$\uparrow$ | 0.584 | 0.6429
llama-7b-finetune | 0.5608 | 0.3633$\uparrow$ | 0.4872 | 0.5902 | 0.6348
llama-13b | 0.5652 | 0.3445 | 0.4520 | 0.5840 | 0.7003
llama-13b-lora | 0.5917 | 0.3403 | 0.4540 | 0.6021 | 0.6838
llama-13b-finetune | 0.593 | 0.3421 | 0.4605 | 0.6120 | 0.6846
llama-30b | 0.5857 | 0.3351 | 0.4590 | 0.6220 | 0.7123
llama-30b-lora | 0.6267$\uparrow$ | 0.3463 | 0.4606 | 0.6358$\uparrow$ | 0.7149$\uparrow$
vicuna | vicuna-7b | 0.6029 | 0.3796$\uparrow$ | 0.5205 | 0.594 | 0.5675
vicuna-7b-lora | 0.5996 | 0.3477 | 0.5285$\uparrow$ | 0.5900 | 0.5992
vicuna-7b-finetune | 0.6014 | 0.3500 | 0.4700 | 0.5860 | 0.5933
vicuna-13b | 0.6208$\uparrow$ | 0.3445 | 0.4485 | 0.6180 | 0.6131
vicuna-13b-lora | 0.6016 | 0.3548 | 0.4561 | 0.6180 | 0.6448
vicuna-13b-finetune | 0.6028 | 0.3448 | 0.4606 | 0.6199$\uparrow$ | 0.6468$\uparrow$
Table 3: Automatic evaluation results before and after instruction-tuning. Within each group (either llama or vicuna), the highest scores are indicated by the $\uparrow$ symbol. The highest score across all methods, irrespective of the group, is highlighted in bold. llama-7b | llama-13b | llama-30b | llama-7b-lora | llama-13b-lora | llama-30b-lora | gpt-3.5
---|---|---|---|---|---|---
1.73 | 2.09 | 3.18 | 6.59 | 6.82 | 7.36 | 8.09
Table 4: Everage GPT-4 evaluation socres.

###  4.1 Model Setup and Tuning

We performed experiments on both foundational language models, such as LLama
Wei et al. (2023), and instruction-tuned models like Vicuna Chiang et al.
(2023). The key difference between these two models lies in the additional
tuning that Vicuna incorporates. Vicuna is tuned on top of LLama using
instructional dialogs, which already equips it with the ability to follow
instructions in common scenarios. In our experiments, we utilized models of
varying sizes—7B, 13B, and 30B. The experiments were designed to ascertain:
(1) whether tuning our collected dataset can enhance model performance on
financial tasks; (2) whether the tuned model can maintain performance on
common tasks; and (3) which model, once tuned, demonstrates superior
performance.

To ensure a comprehensive examination, we applied both fine-tuning and delta-
tuning methods in our study. For delta-tuning, we utilized the LoRa technique,
with parameters ‘r’ and ‘alpha’ both set to 8. We configured the dropout rate
to be 0.05 and applied the LoRa module to the Q and V matrices in the
attention layer. The learning rate was uniformly set at 2e-5 for both tuning
methods, and we employed AdamW as our optimizer. The maximum tokens were
configured at 2048 for the model.

###  4.2 Evaluation

We employed automatic evaluation methods to evaluate the model performance on
general tasks. Additionally, we specifically designed a GPT-4 evaluation on
standard financial questions to assess the model’s proficiency in financial
tasks. The automatic evaluation include several tasks, given as

  * •

XStoryCloze Lin et al. (2022) is a multilingual dataset used to assess
commonsense reasoning in the areas of story comprehension, story generation,
and script learning. In this test, a system is tasked with selecting the
appropriate ending for a four-sentence story.

  * •

pawsx Yang et al. (2019) is cross-lingual dataset used to evaluate models’
ability to identify paraphrases. Each pair of sentences in the dataset has
varying levels of paraphrasing, making it challenging for models to
distinguish between them accurately.

  * •

xnli Conneau et al. (2018) is a benchmark dataset and evaluation task for
cross-lingual sentence understanding, designed to overcome the limitations of
language-specific models by extending the MultiNLI corpus to 15 languages,
facilitating research in low-resource cross-language transfer and multilingual
sentence understanding.

  * •

xcopa Ponti et al. (2020) and xwinograd Tikhonov and Ryabinin (2021) are both
multilingual datasets to evaluate the causal commonsense reasoning ablility of
the models.

Instruction: Currently, Shangji CNC’s main business is the manufacturing and
sales of monocrystalline silicon. However, the company has recently invested
in silicon material business. Does this mean that the company is expanding its
business scope?
---
LLaMA-7b: Hello, I am an artificial intelligence assistant.
LLaMA-13b: We have started researching the silicon industry. We will release
more information about this project.
LLaMA-30b: I know you want to ask: ”Currently, the main business of Shangji
CNC is the manufacturing and sales of monocrystalline silicon. However, the
company has recently invested in silicon material business. Does this mean
that the company is expanding its business scope?”
LLaMA-7b-lora: Of course, the company is expected to gain more market space by
expanding its business areas. According to our analysis, the company has
started accelerating the promotion of silicon material business and making it
one of the new key businesses. In addition, the company can also expand its
business areas through cooperation, acquisition and other means to enhance its
strength and market position.
LLaMA-13b-lora: UpTech CNC has started to expand into the silicon material
industry and has entered into a partnership. From a future development
perspective, the silicon material industry is expected to become an important
support point, which will also play an important role in the company’s long-
term development.
LLaMA-30b-lora: Yes, Shangji CNC has begun to expand its business scope. The
company’s latest investment project is a silicon material production line,
which is expected to become one of the high-growth markets in the future. In
addition, the company holds multiple subsidiaries including Shanghai Huake
Optoelectronics and Shanghai Huake Microsystems, which can also provide more
business options.
Instruction: The maturity level of the industrial chain for photovoltaic
curtain walls and photovoltaic roofs, how are they?
LLaMA-7b: Hello, I am an artificial intelligence assistant. May I ask how can
I assist you?
LLaMA-13b: We can report that in 2017, the industrial chain maturity of
China’s photovoltaic curtain walls and photovoltaic roofs was high.
LLaMA-30b: I know you want to learn about the price changes in the automotive
industry.
LLaMA-7b-lora: Since 2019, the industrial chain of photovoltaic curtain walls
and photovoltaic roofs has been widely recognized in the global market.
Currently, some large domestic companies are conducting research and
development and will begin production in the future. In addition, as both
photovoltaic curtain walls and photovoltaic roofs are emerging technologies,
it is necessary to continuously improve research and development capabilities
and innovation while accelerating product transformation.
LLaMA-13b-lora: Currently, the industrial chains of both photovoltaic curtain
walls and photovoltaic roofs are expanding. The industrial chain of
photovoltaic curtain walls has formed a certain degree of complete automation,
while the photovoltaic roof is still under construction, but many companies
have started research and development as well as production.
LLaMA-30b-lora: Currently, the industrial chains of photovoltaic curtain walls
and photovoltaic roofs are both in an incomplete state of maturity. In terms
of photovoltaic curtain walls, parts such as panels, cells, modules have
formed a relatively complete industrial chain while other parts still need
further improvement. For example, products like photovoltaic press machines
and packaging equipment still have room for efficiency improvement. At the
same time, more research and experimentation is needed for the installation
engineering of photovoltaic curtain walls to ensure controllability and safety
during the installation process. As for photovoltaic roofs, building
components and installation engineering also need further improvement.
Table 5: Case study, generation results of different models, the language has
been translated into English.

###  4.3 Automatic Evaluation Results

The results in Table 3 showcase the performance of the Large Language Models
LLAMA-7b, LLAMA-13b, and LLAMA-30b, with and without LORA tuning. Key
takeaways include:

  * •

LORA tuning consistently boosts performance across all tasks, emphasizing its
effectiveness in enhancing Chinese language comprehension and generation.

  * •

Generally, larger models perform better, but the relationship isn’t linear.
Model performance also relies on factors like tuning technique and dataset
specifics.

  * •

LORA-tuned models significantly excel in the reasoning tasks of XCOPA and
XWinograd, indicating their robust reasoning capabilities in Chinese after
being fine-tuned on our dataset.

Though our dataset concentrates on Chinese financial data, it could be
effectively generalized to a variety of Chinese language understanding tasks.
It’s pertinent to mention that our tuning approach potentially endows the
model with more general language skills beneficial across various domains, not
just finance. We anticipate these models to particularly excel at finance-
specific tasks in Chinese, so we further assess this expectation with a GPT-4
evaluation on finance-related questions curated by experts, which will be
discussed in the subsequent section.

###  4.4 GPT-4 Evaluation Results

Our assessment of model performance on finance-specific tasks employed 100
expert-curated questions, with GPT-4 serving as the judge (with scores ranging
from 1 to 10). The results, presented in Table 4, shed light on how our models
react to these finance-related queries. The observations from the table show:

  * •

Even without LORA tuning, an increase in the size of the model (from LLAMA-7b
to LLAMA-30b) results in better scores, demonstrating the advantage of larger
model sizes.

  * •

With the application of LORA tuning, the scores experience a substantial
uplift. This boost underlines the effectiveness of the LORA tuning approach,
even in a finance-specific context.

  * •

Though the LORA-tuned LLAMA models perform significantly better than their
non-tuned counterparts, they still trail behind the GPT-3.5. This suggests
there remains potential for further improvement and optimization in our
methods to bridge the gap.

In summary, these results reaffirm the beneficial impact of our collected
dataset in financial domain.

###  4.5 Case Study

Table 5 provides a sample of cases chosen randomly from the GPT-4 evaluation
process, offering an intuitive comparison of response generation before and
after tuning on our curated dataset. It becomes evident that the untuned LLaMA
models struggle to produce content relevant to these queries. In contrast, the
LORA-tuned variants, benefitting from our dataset, deliver pertinent and
increasingly detailed responses. This comparison underscores the effectiveness
of our instruction-tuning process.

##  5 Discussion

Our findings demonstrate the significance of domain-specific data collection
and subsequent model tuning. Fine-tuning and delta-tuning methods,
particularly with LORA, can effectively improve the model’s comprehension and
generation capabilities within the financial domain. It’s important to note
that our dataset, even while focusing on Chinese financial data, effectively
generalizes to a variety of Chinese language understanding tasks. Our study
further suggests that not only the quantity but also the quality of data
matters. Our approach of subjecting the data to rigorous examination by
financial experts ensured its relevance and quality, which in turn enhanced
the effectiveness of the model tuning.

However, even though our dataset significantly improved the performance of
LLAMA models, there remains a gap when compared to GPT-3.5, as evidenced by
the GPT-4 evaluation results. It suggests that further optimization and
improvement strategies should be explored. One direction could be to increase
the diversity of the data collection by incorporating more complex financial
dialogues or by incorporating feedback from the financial domain users during
the model tuning phase. Another direction could be to refine the tuning
techniques to better accommodate the specifics of the financial domain.

##  6 Conclusion

In this study, we presented an approach for improving the financial knowledge
of large language models, focusing on Chinese financial discourse. We
collected a dataset of financial questions, refined them with expert input,
and then used them for model tuning. The experimental results confirm the
effectiveness of our approach in enhancing the model’s ability to handle
financial queries. It also highlights the potential of the delta-tuning
technique, such as LORA, in model performance enhancement. This work
contributes to the ongoing discussion on the ways to enhance the capability of
AI models in domain-specific tasks, particularly in the financial sector.
Further research should focus on identifying other potential strategies for
improving the performance of AI in financial services, such as refining tuning
techniques or incorporating real-time user feedback. Despite the remaining
challenges, this study paves the way for large language models to play an
increasingly valuable role in financial services and applications.

## References

  * Chen et al. [2022] Mingda Chen, Jingfei Du, Ramakanth Pasunuru, Todor Mihaylov, Srini Iyer, Veselin Stoyanov, and Zornitsa Kozareva.  Improving In-Context Few-Shot Learning via Self-Supervised Training.  In _Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 3558–3573. Association for Computational Linguistics, 2022.  doi: 10.18653/v1/2022.naacl-main.260.  URL https://aclanthology.org/2022.naacl-main.260.
  * Chiang et al. [2023] Wei-Lin Chiang, Zhuohan Li, Zi Lin, Ying Sheng, Zhanghao Wu, Hao Zhang, Lianmin Zheng, Siyuan Zhuang, Yonghao Zhuang, Joseph E. Gonzalez, Ion Stoica, and Eric P. Xing.  Vicuna: An open-source chatbot impressing gpt-4 with 90%* chatgpt quality, March 2023.  URL https://lmsys.org/blog/2023-03-30-vicuna/.
  * Conneau et al. [2018] Alexis Conneau, Ruty Rinott, Guillaume Lample, Adina Williams, Samuel Bowman, Holger Schwenk, and Veselin Stoyanov.  XNLI: Evaluating cross-lingual sentence representations.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 2475–2485, Brussels, Belgium, October-November 2018. Association for Computational Linguistics.  doi: 10.18653/v1/D18-1269.  URL https://aclanthology.org/D18-1269.
  * Databricks [2023] Databricks.  Free dolly: Introducing the world’s first truly open instruction-tuned llm, 2023.  URL https://www.databricks.com/blog/2023/04/12/dolly-first-open-commercially-viable-instruction-tuned-llm.
  * Köpf et al. [2023] Andreas Köpf, Yannic Kilcher, Dimitri von Rütte, Sotiris Anagnostidis, Zhi-Rui Tam, Keith Stevens, Abdullah Barhoum, Nguyen Minh Duc, Oliver Stanley, Richárd Nagyfi, Shahul ES, Sameer Suri, David Glushkov, Arnav Dantuluri, Andrew Maguire, Christoph Schuhmann, Huu Nguyen, and Alexander Mattick.  Openassistant conversations – democratizing large language model alignment, 2023.
  * Lin et al. [2022] Xi Victoria Lin, Todor Mihaylov, Mikel Artetxe, Tianlu Wang, Shuohui Chen, Daniel Simig, Myle Ott, Naman Goyal, Shruti Bhosale, Jingfei Du, Ramakanth Pasunuru, Sam Shleifer, Punit Singh Koura, Vishrav Chaudhary, Brian O’Horo, Jeff Wang, Luke Zettlemoyer, Zornitsa Kozareva, Mona Diab, Veselin Stoyanov, and Xian Li.  Few-shot learning with multilingual generative language models.  In _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing_ , pages 9019–9052, Abu Dhabi, United Arab Emirates, December 2022. Association for Computational Linguistics.  URL https://aclanthology.org/2022.emnlp-main.616.
  * OpenAI [2023] OpenAI.  Gpt-4 technical report, 2023.
  * Ouyang et al. [2022] Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul Christiano, Jan Leike, and Ryan Lowe.  Training language models to follow instructions with human feedback, 2022\.
  * Ponti et al. [2020] Edoardo Maria Ponti, Goran Glavaš, Olga Majewska, Qianchu Liu, Ivan Vulić, and Anna Korhonen.  XCOPA: A multilingual dataset for causal commonsense reasoning.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 2362–2376, Online, November 2020\. Association for Computational Linguistics.  doi: 10.18653/v1/2020.emnlp-main.185.  URL https://aclanthology.org/2020.emnlp-main.185.
  * Taori et al. [2023] Rohan Taori, Ishaan Gulrajani, Tianyi Zhang, Yann Dubois, Xuechen Li, Carlos Guestrin, Percy Liang, and Tatsunori B. Hashimoto.  Stanford alpaca: An instruction-following llama model.  https://github.com/tatsu-lab/stanford_alpaca, 2023.
  * Tikhonov and Ryabinin [2021] Alexey Tikhonov and Max Ryabinin.  It’s All in the Heads: Using Attention Heads as a Baseline for Cross-Lingual Transfer in Commonsense Reasoning.  In _Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021_ , pages 3534–3546, Online, August 2021. Association for Computational Linguistics.  doi: 10.18653/v1/2021.findings-acl.310.  URL https://aclanthology.org/2021.findings-acl.310.
  * Wang et al. [2022] Yizhong Wang, Yeganeh Kordi, Swaroop Mishra, Alisa Liu, Noah A. Smith, Daniel Khashabi, and Hannaneh Hajishirzi.  Self-instruct: Aligning language model with self generated instructions, 2022.
  * Wei et al. [2023] Jerry Wei, Jason Wei, Yi Tay, Dustin Tran, Albert Webson, Yifeng Lu, Xinyun Chen, Hanxiao Liu, Da Huang, Denny Zhou, and Tengyu Ma.  Larger language models do in-context learning differently, 2023.  URL http://arxiv.org/abs/2303.03846.
  * Xu et al. [2023] Canwen Xu, Daya Guo, Nan Duan, and Julian McAuley.  Baize: An open-source chat model with parameter-efficient tuning on self-chat data.  _arXiv preprint arXiv:2304.01196_ , 2023.
  * Yang et al. [2019] Yinfei Yang, Yuan Zhang, Chris Tar, and Jason Baldridge.  PAWS-X: A cross-lingual adversarial dataset for paraphrase identification.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 3687–3692, Hong Kong, China, November 2019. Association for Computational Linguistics.  doi: 10.18653/v1/D19-1382.  URL https://aclanthology.org/D19-1382.


Signs of the Second Coefficients of Hecke Polynomials

[2020]Primary 11F25; Secondary 11F72 and 11F11.

E. Ross]Erick Ross
[E. Ross]School of Mathematical and Statistical Sciences, Clemson University, Clemson, SC, 29634

H. Xue]Hui Xue
[H. Xue]School of Mathematical and Statistical Sciences, Clemson University, Clemson, SC, 29634

Let $T_m(N, k, \chi)$ be the $m$-th Hecke operator of level $N$, weight $k \geq 2$, and nebentypus $\chi$, where $N$ is coprime to $m$.  We first show that for any given $m \geq 1$, the second coefficient of the characteristic polynomial of $T_m(N, k, \chi)$ is nonvanishing for all but finitely many triples $(N,k,\chi)$. Furthermore, for $\chi$ trivial and any fixed $m$, we determine the sign of the second coefficient for all but finitely many pairs $(N,k)$. Finally, for $\chi$ trivial and $m=3,4$, we compute the sign of the second coefficient for all pairs $(N,k)$.

§ INTRODUCTION

Let $k\ge2$, $N\ge1$ be integers and let $\chi$ be a Dirichlet character modulo $N$ such that $\chi(-1) = (-1)^k$. The space of cuspforms of level $N$, weight $k$, and nebentypus $\chi$ is denoted by $S_k(\Gamma_0(N),\chi)$ <cit.>. For $m \geq 1$, let $T_m(N,k,\chi)$ be the $m$-th Hecke operator  on $S_k(\Gamma_0(N),\chi)$ <cit.>.  When the character $\chi$ is trivial, we will drop $\chi$ and simply write $T_m(N,k)$ and $S_k(\Gamma_0(N))$, respectively.
Several interesting questions about these Hecke operators $T_m(N, k, \chi)$ have been studied.  For instance, let

be the discriminant function,
which is the unique normalized cuspform of weight $12$, level one, and trivial nebentypus.  Lehmer <cit.> conjectured that $\tau(m)\neq0$ for all $m\geq1$. Let $\Tr T_m(N, k)$ denote the trace of $T_m(N, k)$ on the space $S_k(\Gamma_0(N))$. The Lehmer Conjecture can then be reinterpreted as follows: $\Tr T_m(1, 12) \neq 0$ for all $m\geq 1$. More broadly, Rouse <cit.> gave the Generalized Lehmer Conjecture, which predicts that $\Tr T_m(N,k)\neq0$ for even $k\geq 16$ or $k=12$ and $\gcd(m,N)=1$. He also proved this result for $m=2$. Recently, the nonvanishing of $\Tr T_{3}(1,k)$ was also established in <cit.>.

Now, let us write the characteristic polynomial for $T_m(N,k,\chi)$, the so-called Hecke polynomial,

\begin{align}
T_m(N,k,\chi)(x)=x^n - a_1(m,N,k,\chi) x^{n-1} + a_2(m,N,k,\chi) x^{n-2} - \cdots + (-1)^n a_n(m,N,k,\chi),
\end{align}

where $n=\dim S_k(\Gamma_0(N),\chi)$.
Here, we will refer to $a_i(m,N,k,\chi)$ as the $i$-th coefficient of the Hecke polynomial.
To ease notation we will simply write $a_i(m,N,k)$
if $\chi$ is trivial.
Using this notation, the Generalized Lehmer Conjecture concerns the nonvanishing of the first coefficient $a_1(m,N,k)$ of $T_m(N,k)(x)$. One may also consider the nonvanishing of the other coefficients,

in particular the second coefficient, $a_2(m,N,k,\chi)$.
Most recently, for trivial characters $\chi$, Clayton et al. <cit.> computed the complete list of pairs $(N,k)$ for which the second coefficient of $T_2(N,k)(x)$ vanishes. In this paper,  we shall first extend the results of <cit.> to study the nonvanishing of $a_2(m,N,k,\chi)$ for general $m$, $N$, $k$, and $\chi$. More precisely, we have the following result.

Let $m \geq 1$ be fixed. Suppose $\gcd(N,m)=1$, $k \geq 2$, and $\chi$ is a Dirichlet character modulo $N$ such that $\chi(-1) = (-1)^k$. Then $a_2(m,N,k,\chi)$ vanishes for only finitely many triples $(N,k,\chi)$.

When $\chi$ is trivial, we also explicitly determine the sign of the second coefficient.

Let $m \geq 1$ be fixed. Suppose $\gcd(N,m)=1$ and $k \geq 2$ is even.

$(1)$: If $m$ is not a perfect square, then $a_2(m,N,k)$ is negative for all but finitely many pairs $(N,k)$.

$(2)$: If $m$ is a perfect square, then $a_2(m,N,k)$ is positive for all but finitely many pairs $(N,k)$.

We show these two theorems by first expressing $a_2(m,N,k,\chi)$ in terms of traces of various Hecke operators (Lemma <ref>). These traces can each be evaluated by the Eichler-Selberg trace formula (<ref>).  From this formula, we can then identify the dominant terms for these traces, coming from the Hecke operators with perfect square index (Lemma <ref>).  This allows us to determine the asymptotic growth of $a_2(m,N,k,\chi)$, which then yields Theorems <ref> and <ref>.

In fact, our method is effective: for any given $m$, these exceptional pairs can be computed explicitly. As an illustratation of the two cases in Theorem <ref>,
when $\chi$ is trivial and $m=3,4$, we carry out the details to compute all the exceptional pairs.

Suppose that $\gcd(N,3)=1$ and that $k \geq 2$ is even.
Then  $a_2(3,N,k)$ is positive or zero only for the pairs $(N,k)$ given in Table <ref>.

Suppose that $\gcd(N,4)=1$ and that $k \geq 2$ is even.
Then  $a_2(4,N,k)$ is negative or zero only for the pairs $(N,k)$ given in <cit.>.

The paper is organized as follows. In Section <ref>, following the idea in <cit.>, we express the second coefficient $a_2(m,N,k,\chi)$ in terms of traces of Hecke operators. We also state the Eichler-Selberg trace formula to compute these traces. Section <ref> is preparatory and establishes estimates on certain terms in the Eichler-Selberg trace formula. In Section <ref>, we prove Theorems <ref> and <ref>. In Sections <ref> and <ref> we apply the techniques developed in Section <ref> to the cases of $m=3$ and $m=4$, and prove Theorems <ref> and <ref>, respectively. Section <ref> discusses some related questions.

§ SECOND COEFFICIENTS IN TERMS OF TRACES

Following <cit.>, we first derive a formula for $a_2(m,N,k,\chi)$  in terms of traces of Hecke operators.

For convenience of notation, let $T_m$ denote $T_m(N,k,\chi)$. Then

\begin{align}
a_2(m,N,k,\chi) = \frac{1}{2} \lrb{ \left(\Tr T_m\right)^2 - \sum_{d \mid m} \chi(d) d^{k-1} \Tr T_{m^2/d^2} }. \end{align}

Let $\lambda_1 \ldots \lambda_n$ be the eigenvalues of $T_m$. By the definition of characteristic polynomial, we have

\begin{align}
&= \sum_{1 \leq i < j \leq n} \lambda_i \lambda_j \\
&= \frac12 \lrb{ \lrp{ \sum_{1 \leq i \leq n} \lambda_i }^2 - \sum_{1 \leq i \leq n} \lambda_i^2 } \\
&= \frac12 \lrb{ (\Tr T_m)^2 - \Tr T_m^2 }.
\end{align}

On the other hand, recall the following formula  <cit.> for Hecke operators:

$$ T_m^2 = \sum_{d\mid m} \chi(d) d^{k-1}  T_{m^2/d^2} .$$

\begin{align}
a_2(m,N,k,\chi) &= \frac12 \lrb{ (\Tr T_m)^2 - \Tr T_m^2 }  \\
&= \frac12 \lrb{ (\Tr T_m)^2 - \sum_{d \mid m} \chi(d) d^{k-1} \Tr T_{m^2/d^2} },
\end{align}

as desired.

Next, we state the Eichler-Selberg trace formula in order to give an explicit formula for the traces appearing in Lemma <ref>.  Let $m \geq 1$, $N \geq 1$, $k \geq 2$, and $\chi$ be a Dirichlet character modulo $N$ such that $\chi(-1) = (-1)^k$. From <cit.>, and borrowing some notation from <cit.>, the Eichler-Selberg trace formula is given by

\begin{equation} \label{eqn:eichler-selberg-trace-formula}
\Tr T_m(N,k,\chi) = A_{1,m} - A_{2,m} - A_{3,m} + A_{4,m} ,
\end{equation}

\begin{align}
\label{eqn:A1m-formula}
A_{1,m} &= \chi(\sqrt{m}) \frac{k-1}{12} \psi (N) m^{k/2-1},  \\
\label{eqn:A2m-formula}
A_{2,m} &= \frac{1}{2} \sum_{t^2 < 4m} U_{k-1}(t,m) \sum_{n}  h_w \lrp{ \frac{t^2-4m}{n^2} } \mu (t,n,m), \\
\label{eqn:A3m-formula}
A_{3,m} &= \frac{1}{2} \sum_{d|m} \min(d,m/d)^{k-1} \sum_{\tau} \phi ( \gcd(\tau, N / \tau )) \chi(y_{\tau}), \\
\label{eqn:A4m-formula}
A_{4,m} &= \begin{dcases}
\sum_{\substack{c|m \\ (N, m/c) = 1}} c & \text{if $k=2$ and $\chi = \chi_0$},\\
0 & \text{if $k>2$ or $\chi \neq \chi_0$} .\\
\end{dcases}
\end{align}

Here, we have the following notation.

* $\chi(\sqrt{m})$ is interpreted as $0$ if $m$ is not a perfect square.

* $\psi (N) = \lrb{\, \SL{2}(\ZZ) \, : \, \Gamma_0 (N) \,} = N \prod_{p|N} \lrp{ 1 + \frac{1}{p} }$.

* The outer summation in $A_{2,m}$ runs over all $t \in \ZZ$ such that $t^2 < 4m$. Note that the terms corresponding to $t=t_0$ and $t=-t_0$ coincide.

* $U_{k-1}(t,m)$ denotes the Lucas sequence of the first kind. In particular, $U_{k-1}(t,m) = \frac{\rho^{k-1} - \bar{\rho}^{k-1}}{\rho - \bar{\rho}}$ where $\rho, \bar{\rho}$ are the two roots of the polynomial $X^2-tX+m$.

* The inner summation in $A_{2,m}$ runs through all positive integers $n$ such that $n^2 \, | \, (t^2 -4m)$ and $\frac{t^2-4m}{n^2} \equiv 0,1 \pmod{4}$.

* $h_w \lrp{ \frac{t^2-4m}{n^2} }$ is the weighted class number of the imaginary quadratic order with discriminant $\frac{t^2-4m}{n^2}$. This is the usual class number, divided by $2$ (respectively $3$) if the discriminant is $-4$ (respectively $-3$). For our purposes, the first few of them are given explicitly in Table <ref> below.

* $\displaystyle \mu (t,n,m) = \frac{\psi (N)}{\psi (N/N_n)} \sideset{}{'} \sum_{c \!\! \mod N} \chi(c)$, where $N_n = \gcd(N,n)$, and the primed summation runs through all elements $c$ of $(\ZZ / N \ZZ)^{\times}$ which lift to solutions of $c^2-tc+m \equiv 0 \pmod{NN_n}$.

* The outer summation for $A_{3,m}$ runs through all positive divisors $d$ of $m$. Note that the terms corresponding to $d=d_0$ and $d=m/d_0$ coincide.

* The inner summation for $A_{3,m}$ runs over all positive divisors $\tau$ of $N$ such that $\gcd(\tau, N/\tau)$ divides $\gcd(N/N_{\chi}, d-m/d)$. Here $N_{\chi}$ is the conductor of $\chi$.

* $\phi$ is the Euler totient function.

* $y_{\tau}$ is the unique integer modulo $\lcm(\tau, N/\tau)$ determined by the congruences $y_{\tau} \equiv d \pmod{\tau}$ and $y_{\tau} \equiv \frac{m}{d} \pmod{\frac{N}{\tau}}$.

* $\chi_0$ denotes the trivial character modulo $N$.

* Throughout, remember that $\chi$ is a character modulo $N$, so $\chi(a) = 0$ if $\gcd(a,N) > 1$, even in the trivial character case.

[Weighted class numbers; <cit.>, <cit.>]

\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
n & -3 & -4 & -7 & -8 & -11 & -12 & -15 & -16 & -19 & -20 & -23 \\
\hline
h_w(n) & \frac{1}{3} & \frac{1}{2} & 1 & 1 & 1 & 1 & 2 & 1 & 1 & 2 & 3 \\
\hline \hline
n & -24 & -27 & -28 & -31 & -32 & -35 & -36 & -39 & -40 & -43 & -44 \\
\hline
h_w(n) & 2 & 1 & 1 & 3 & 2 & 2 & 2 & 4 & 2 & 1 & 3 \\
\hline \hline
n & -47 & -48 & -51 & -52 & -55 & -56 & -59 & -60 & -63 & -64 & -67 \\
\hline
h_w(n) & 5 & 2 & 2 & 2 & 4 & 4 & 3 & 2 & 4 & 2 & 1 \\
\hline
\end{array}

§ ESTIMATES ON TERMS IN THE TRACE FORMULA

In this section we give estimates on the $A_{i,m}$ trace terms (<ref>), (<ref>), (<ref>), and (<ref>).
First, we introduce some arithmetic functions  that will be used to express these estimates.

Recall that $\psi(N) = N \prod_{p|N} \lrp{ 1 + \frac{1}{p} }$, and let $\omega(N)$ denote the number of distinct prime divisors of $N$. Define

\begin{align*}
\theta_1(N) := \frac{2^{\omega(N)} \sqrt{N} }{\psi(N)},
\qquad
\theta_2(N) := \frac{(2^{\omega(N)})^2}{\psi(N)},
\qquad
\theta_3(N) := \frac{2^{\omega(N)}}{\psi(N)}.
\end{align*}

Then each $\theta_i(N) \rightarrow 0$ as $N \rightarrow \infty$.

In particular, we have the bounds given in the following table.

\begin{array}{|c|c|c|c|c|c|c|c|}
\hline
\displaystyle N \geq & 1 & 43 & 571 & 8,\!800 & 150,\!000 & 2,\!700,\!000 & 63,\!000,\!000  \\
\hline
\displaystyle \theta_1(N) \leq & 1.00 & 0.465 & 0.257 & 0.133 & 0.0607 & 0.0265 & 0.0106  \\
\hline
\displaystyle \theta_2(N) \leq & 1.34 & 0.445 & 0.149 & 0.0424 & 0.00941 & 0.00189 & 0.000314  \\
\hline
\displaystyle \theta_3(N) \leq & 1.00 & 0.0556 & 0.00926 & 0.00133 & 0.000147 & 0.000015 &  0.000015 \\
\hline
\end{array}

Note that every prime other than $2,3,5,7$ is $\geq 8$. Thus $\omega(N) \leq 4 + \log_8(N)$ and so $2^{\omega(N)} \leq 2^{4 + \log_8(N)} \leq 16 \cdot N^{1/3}$. Since $\psi(N) \geq N$, it is clear that

$$\theta_1(N) = \frac{2^{\omega(N)} \sqrt{N} }{\psi(N)}, \ \ \ \theta_2(N) = \frac{(2^{\omega(N)})^2}{\psi(N)}, \ \ \ \theta_3(N) = \frac{2^{\omega(N)}}{\psi(N)} \ \ \longrightarrow 0 \ \text{ as } \ N \longrightarrow \infty.$$

To prove the specific numerical bounds given above, we will first show that

\begin{equation} \label{eqn:three-numerical-theta-bounds}
\theta_1(N) \leq 0.0106,\ \theta_2(N) \leq 0.000314, \ \theta_3(N) \leq 0.000015
\end{equation}

for all $N \geq 584,\!000,\!000$. Then we will verify each of the claimed bounds in the table by exhaustive computer check over all $N < 584,\!000,\!000$.

Let $p_n$ denote the $n$-th prime number, and let $P_n := p_1\cdots p_n$.

For all $N$ with $\omega(N) \geq 9$, we show that $\theta_i(N) \leq \theta_i(P_9)$.
For such $N$, let $N=q_1^{e_1} \cdots q_m^{e_m}$ be its prime factorization. Then

\begin{align*}
\frac{\psi(N)}{\sqrt{N}} &= \frac{ (q_1+1)q_1^{e_1-1} \cdots (q_m+1)q_m^{e_m-1} }{q_1^{e_1/2} \cdots q_m^{e_m/2}} \\
&\geq \frac{ (q_1+1) \cdots (q_m+1) }{q_1^{1/2} \cdots q_m^{1/2}} \\
&\geq \frac{ (p_1+1) \cdots (p_m+1) }{p_1^{1/2} \cdots p_m^{1/2}} \qquad \qquad \qquad \lrp{ \text{since $\frac{x+1}{x^{1/2}}$ is increasing for $x \geq 1$} } \\
% &= \frac{ (p_{1}+1) \cdots (p_9+1) }{p_{1}^{1/2} \cdots p_9^{1/2}} \cdot  \frac{ (p_{10}+1) \cdots (p_m+1) }{p_{10}^{1/2} \cdots p_m^{1/2}}  \\
&= \frac{\psi(P_9)}{\sqrt{P_9}}  \frac{ (p_{10}+1) \cdots (p_m+1) }{p_{10}^{1/2} \cdots p_m^{1/2}}  \\
&\geq \frac{\psi(P_9)}{\sqrt{P_9}}  2^{m-9} .
\end{align*}

This means that
\theta_1(N) = \frac{2^m \sqrt{N}}{\psi(N)}
\leq \frac{2^m \sqrt{P_9}}{2^{m-9} \psi(P_9)}  = \theta_1(P_9) \leq 0.0106

By an identical argument,
\psi(N) \geq 4^{m-9} \psi(P_9)
which means that
\theta_2(N) \leq \theta_2(P_9) \leq 0.000314
\theta_3(N) \leq \theta_3(P_9) \leq 0.000015
This verifies the three bounds in (<ref>) for all $N$ with $\omega(N) \geq 9$.

For $N$ with $\omega(N) \leq 8$ and $N \geq 584,\!000,\!000$, we have

θ_1(N)    = 2^ω(N) √(N)/ψ(N)       ≤2^8 √(N)/N       ≤0.00915 ,

θ_2(N)    = (2^ω(N))^2/ψ(N)       ≤2^16/N       ≤0.000314 ,

θ_3(N)    = 2^ω(N)/ψ(N)       ≤2^8/N       ≤0.000015 .

This verifies the three bounds in (<ref>) for all $N$ with $N \geq 584,\!000,\!000$.

Then via exhaustive computer check over all $N < 584,\!000,\!000$, we obtain the claimed bounds from the table. See <cit.> for the code.

Next, we bound the inner summation for $A_{2,m}$ in (<ref>).

For $t,n,m$ given in (<ref>),

\lrabs{U_{k-1}(t,m) \cdot \mu(t,n,m) } \leq 2 \psi(n) 2^{\omega(N)} m^{(k-1)/2}.

Recall that $m \geq 1$, $t \in \ZZ$ such that $4m-t^2 > 0$, and $n \geq 1$ such that $n^2 \, | \, (t^2 -4m)$ and $\frac{t^2-4m}{n^2} \equiv 0,1 \, \pmod{4}$. And recall that $U_{k-1}(t,m) = \frac{\rho^{k-1} - \bar{\rho}^{k-1}}{\rho - \bar{\rho}}$ where $\rho, \bar{\rho}$ are the two roots of the polynomial $X^2-tX+m$. Finally, recall that $\displaystyle \mu (t,n,m) = \frac{\psi (N)}{\psi (N/N_n)} \sideset{}{'} \sum_{c \!\! \mod N} \chi(c)$, where $N_n = \gcd(N,n)$, and the primed summation runs through all elements $c$ of $(\ZZ / N \ZZ)^{\times}$ which lift to solutions of $c^2-tc+m \equiv 0 \, \pmod{NN_n}$.

\begin{equation} \label{eqn:U-mu-factors}
\lrabs{U_{k-1}(t,m) \cdot \mu(t,n,m) } = \lrabs{ \frac{\rho^{k-1} - \bar{\rho}^{k-1}}{\rho - \bar{\rho}} } \cdot \frac{\psi(N)}{\psi(N/N_n)} \cdot \lrabs{  \sideset{}{'} \sum_{c \!\!\! \mod N} \chi(c) } .
\end{equation}

We give bounds on each of these three factors.

First, since

$$\lrabs{\rho} = \sqrt{m} \qquad \text{and} \qquad \lrabs{\rho - \bar{\rho}} = \sqrt{4m-t^2} ,$$

we have

\begin{equation} \label{eqn:U-mu-bound1}
\lrabs{ \frac{\rho^{k-1} - \bar{\rho}^{k-1}}{\rho - \bar{\rho}} } \leq \frac{ \lrabs{\rho^{k-1}} + \lrabs{\bar{\rho}^{k-1} } }{ \lrabs{ \rho - \bar{\rho} } } = \frac{2 m^{(k-1)/2}}{\sqrt{4m-t^2}} .
\end{equation}

Second, note that for every prime $p \mid N$, we will either have $p \mid N_n$ or $p \mid N/N_n$. Thus

\begin{align}
\psi(N) &= N \prod_{p|N} \lrp{1 + \frac{1}{p} } \\
&\leq N_n \prod_{p|N_n} \lrp{1 + \frac{1}{p} } \cdot N/N_n \prod_{p|N/N_n} \lrp{1 + \frac{1}{p}} \\
&= \psi(N_n) \psi(N/N_n) ,
\end{align}

which yields

\begin{equation} \label{eqn:U-mu-bound2}
\frac{\psi(N)}{\psi(N/N_n)} \leq \psi(N_n) \leq \psi(n)  ,
\end{equation}

where the second inequality comes from the fact that $N_n \mid n$.

Third, note for every term $c$ in the sum of (<ref>), $c^2-tc+m \equiv 0 \pmod{NN_n}$ means that $c^2-tc+m \equiv 0 \pmod{N}$ as well. By <cit.>, the congruence $x^2-tx+m \equiv 0 \pmod{N}$ has at most $2^{\omega(N)} \sqrt{4m-t^2}$ solutions. Thus

\begin{equation} \label{eqn:U-mu-bound3}
\lrabs{  \sideset{}{'} \sum_{c \!\!\! \mod N} \chi(c) } \leq 2^{\omega(N)} \sqrt{4m-t^2} .
\end{equation}

Combining the bounds (<ref>), (<ref>), and (<ref>), we obtain

\lrabs{U_{k-1}(t,m) \cdot \mu(t,n,m) } \leq 2 \psi(n) 2^{\omega(N)} m^{(k-1)/2} ,

which completes the proof.

Next, we bound the inner summation for $A_{3,m}$ in (<ref>).

$$ \Sigma(N,m,d) := \sum_\tau \phi(\gcd(\tau, N/\tau)) \chi(y_{\tau})

denote the inner summation for $A_{3,m}$ in (<ref>).

$$\lrabs{\Sigma(N,m,d)} \leq
\begin{cases}
\lrabs{d-\frac md} \cdot 2^{\omega(N)} & \text{if } d \neq \sqrt{m}, \\
\sqrt{N} \cdot 2^{\omega(N)} & \text{in general.}
\end{cases}

Recall that the summation $\sum_{\tau}$  runs over all positive divisors $\tau$ of $N$ such that $\gcd(\tau,N/\tau)$ divides $\gcd(N/N_{\chi}, d-m/d)$. Additionally, $y_{\tau}$ is the unique integer modulo $\lcm(\tau, N/\tau)$ determined by the congruences $y_{\tau} \equiv d \pmod{\tau}$ and $y_{\tau} \equiv m/d \pmod{N/\tau}$.

Let $h := |d - \frac{m}{d}|$. Then

\begin{align}
\lrabs{\Sigma(N,m,d)} &= \lrabs{\sum_{\substack{\tau \mid N \\  (\tau, N/\tau) \mid (h,N/N_{\chi})}} \phi(\gcd(\tau, N/\tau)) \chi(y_{\tau})} \\
&\leq \sum_{\substack{\tau \mid N \\  (\tau, N/\tau) \mid (h,N/N_{\chi})}} \phi(\gcd(\tau, N/\tau)) \\
&\leq \sum_{\substack{\tau \mid N \\  (\tau, N/\tau) \mid h}} \phi(\gcd(\tau, N/\tau)) \\
&= \sum_{\delta\mid h} \ \sum_{\substack{\tau \mid N \\ (\tau, N/\tau)=\delta}} \phi(\delta) \\
&= \sum_{\delta \mid h} \phi(\delta) \cdot \#\{\tau \mid N \ \colon \ \gcd(\tau, N/\tau)=\delta\} .
\end{align}

In the case of $d \neq \sqrt{m}$, we have $h\neq 0$, and so using Lemma <ref> below, we have

\begin{align}
\lrabs{\Sigma(N,m,d)}
&\leq \sum_{\delta \mid h} \phi(\delta) \cdot \#\{\tau|N \ \colon \ \gcd(\tau, N/\tau)=\delta\} \\
&\leq \sum_{\delta \mid h} \phi(\delta) \cdot 2^{\omega(N)} \\
&= h \cdot 2^{\omega(N)}.
\end{align}

Here, we used the well-known formula
$\sum_{\delta \mid h} \phi(\delta) = h$.

In the general case, write $N = DM^2$ where $D$ is squarefree. Then for any $\delta$ such that $\gcd(\tau, N/\tau) = \delta$ for some $\tau$, note $\delta \mid \tau$ and $\delta \mid N/\tau$ imply $\delta^2 \mid N$, which means that $\delta \mid M$.
Hence by Lemma <ref> again,

\begin{align}
\lrabs{\Sigma(N,m,d)}
&\leq \sum_{\delta \mid h} \phi(\delta) \cdot \#\{\tau \mid N \ \colon \ (\tau, N/\tau)=\delta\} \\
&\leq \sum_{\delta \mid M} \phi(\delta) \cdot \#\{\tau \mid N \ \colon \ (\tau, N/\tau)=\delta\} \\
&\leq \sum_{\delta \mid M} \phi(\delta) \cdot 2^{\omega(N)} \\
&= M \cdot 2^{\omega(N)} \\
&\leq \sqrt{N} \cdot 2^{\omega(N)},
\end{align}

which completes the proof.

Let $N$ and $\delta$ be positive integers. Then

$$\#\{\tau \mid N \ \colon \ \gcd(\tau, N/\tau)=\delta\} \leq 2^{\omega(N)} .$$

Without loss of generality, we can assume that $\delta \mid N$ (otherwise, the inequality holds trivially).
Consider the possible $\tau$ that would yield $\gcd(\tau, N/\tau)=\delta$.
For each prime $p \mid N$,
let $v_p(\cdot)$ denote $p$-adic valuation, and let $r_p := v_p(\delta)$.  Note that $\gcd(\tau, N/\tau)=\delta$ precisely for $\tau$ such that $v_p(\gcd(\tau,N/\tau)) = r_p$ for each $p \mid N$. On the other hand, $v_p( \gcd(\tau,N/\tau)) = r_p$ means that either $v_{p}(\tau) = r_p$ and $v_p(N/\tau) \geq r_p$, or $v_p(N/\tau) = r_p$ and $v_{p}(\tau) \geq r_p$. This yields only two possible values for $v_{p}(\tau)$: $r_p$ and $v_{p}(N) - r_p$. Thus, since there are at most two possible options for $v_{p}(\tau)$ for each prime $p \mid N$, we have that $\#\{\tau \mid N \ \colon \ \gcd(\tau, N/\tau)=\delta\} \leq  2^{\omega(N)}$.

§ PROOF OF THEOREMS <REF> AND <REF>

In this section, we will show Theorems <ref> and <ref>. We split the proof into the case when $m$ is not a perfect square (Proposition <ref>), and the case when $m$ is a perfect square (Proposition <ref>).

Recall what big $O$ notation means in terms of two variables $N$ and $k$. A function $f(N,k)$ is $O(g(N,k))$ if there exists a constant $C$ such that $\lrabs{f(N,k)} \leq C \cdot g(N,k)$ for $N+k$ sufficiently large.
In other words, for any fixed value of $N$, this can be interpreted as big $O$ notation with respect to $k$, and for any fixed value of $k$, this can be interpreted as big $O$ notation with respect to $N$.

Now, we give a bound on the trace $\Tr T_m(N,k,\chi)$ when $m$ is not a perfect square.

Let $m\ge1$ be fixed such that $m$ is not a perfect square. For all $N \geq 1$, $k \geq 2$, and $\chi$ a Dirichlet character modulo $N$ with $\chi(-1) = (-1)^k$, we have

$$\Tr T_m(N,k,\chi) =  O(2^{\omega(N)} m^{k/2}) .$$

We examine each of the $A_{i,m}$ terms in (<ref>) separately.

First, since $m$ is not a perfect square and $\chi(\sqrt{m})=0$, we have that $A_{1,m} = 0$ by (<ref>).

Second, observe that all the $t$ and $n$ from (<ref>) are bounded by the fixed value of $2\sqrt{m}$. Thus by Lemma <ref>,

$$\lrabs{U_{k-1}(t,m) \cdot \mu(t,n,m) } = O(2^{\omega(N)} m^{k/2}) ,$$

so by (<ref>)

\begin{align*}
A_{2,m} &= \frac{1}{2} \sum_{t^2 < 4m} \sum_{n}  h_w \lrp{ \frac{t^2-4m}{n^2} }  U_{k-1}(t,m) \mu(t,n,m) \\
&= O(2^{\omega(N)} m^{k/2}) .
\end{align*}

Third, since $m$ is not a perfect square, only the first case of Lemma <ref> applies. Thus each inner summation $\Sigma(N,m,d)$ for $A_{3,m}$ is $O(2^{\omega(N)})$. And also note that $\min(d,m/d) \leq m^{1/2}$. So by (<ref>),

\begin{align*}
A_{3,m} &= \frac{1}{2} \sum_{d|m} \min(d,m/d)^{k-1} \Sigma(N,m,d) \\
&= O(2^{\omega(N)} m^{k/2}).
\end{align*}

Fourth, $A_{4,m} \leq \sum_{c\mid m} c = O(1)$ by (<ref>).

Combining the above bounds, we obtain

\begin{align*}
\Tr T_m(N,k,\chi) &= A_{1,m} - A_{2,m} - A_{3,m} + A_{4,m} \\
&=  O(2^{\omega(N)} m^{k/2}) ,
\end{align*}

which completes the proof.

Next, we estimate the trace $\Tr T_m(N,k,\chi)$ when $m$ is a perfect square.

Let $m$ be fixed such that $m$ is a perfect square. Then for all $N \geq 1$, $k \geq 2$, and $\chi$ a Dirichlet character modulo $N$ with $\chi(-1) = (-1)^k$, we have

$$\Tr T_m(N,k,\chi) = \chi(\sqrt{m}) \frac{k-1}{12} \psi(N) m^{k/2-1} + O(\sqrt{N} 2^{\omega(N)} m^{k/2}).$$

We examine each of the $A_{i,m}$ terms in (<ref>) separately.

First, $A_{1,m} = \chi(\sqrt{m}) \frac{k-1}{12} \psi(N) m^{k/2-1}$ from (<ref>).

Second, like in the previous Lemma, $A_{2,m} = O(2^{\omega(N)} m^{k/2})$.

Third, from Lemma <ref>, each inner summation $\Sigma(N,m,d)$ in $A_{3,m}$ is $O(\sqrt{N} 2^{\omega(N)})$. So by (<ref>) and the fact that $\min(d,m/d) \leq m^{1/2}$,

\begin{align*}
A_{3,m} &= \frac{1}{2} \sum_{d|m} \min(d,m/d)^{k-1} \Sigma(N,m,d) \\
&= O(\sqrt{N} 2^{\omega(N)} m^{k/2}).
\end{align*}

Fourth, we have $A_{4,m} = O(1)$ by (<ref>).

Combining the above bounds, we obtain

\begin{align*}
\Tr T_m(N,k,\chi) &= A_{1,m} - A_{2,m} - A_{3,m} + A_{4,m} \\
&= \chi(\sqrt{m}) \frac{k-1}{12} \psi(N) m^{k/2-1} + O(\sqrt{N} 2^{\omega(N)} m^{k/2}),
\end{align*}

concluding the proof.

Next, we prove Theorems <ref> and <ref> in the case when $m$ is not a perfect square.

Let $m \geq 1$ be fixed and not a perfect square. Suppose that $\gcd(N,m)=1$, $k \geq 2$, and $\chi$ is a Dirichlet character modulo $N$ with $\chi(-1) = (-1)^k$. Then  $a_2(m,N,k,\chi)$ is nonvanishing for all but finitely many triples $(N,k,\chi)$.
Furthermore, when $\chi$ is trivial,
$a_2(m,N,k)$ is negative for all but finitely many pairs $(N,k)$.

By Lemma <ref>, we have

\begin{align*}
&= \frac{1}{2} \lrb{ (\Tr T_m)^2 - \sum_{d \mid m} \chi(d) d^{k-1} \Tr T_{m^2/d^2} }.
\end{align*}

Now, observe that every term inside the sum has $m^2/d^2$ a perfect square. Thus for each term in the sum, we have by Lemma <ref>,

\begin{align*}
&~~\chi(d) d^{k-1} \Tr T_{m^2/d^2} \\
&=\chi(d) d^{k-1}
\lrb{
\chi \lrp{\sqrt{\frac{m^2}{d^2}}} \frac{k-1}{12} \psi(N) \lrp{\frac{m^2}{d^2}}^{k/2-1} + O\left( \sqrt{N} 2^{\omega(N)} \lrp{\frac{m^2}{d^2}}^{k/2} \right)
} \\
&=\chi(d) d^{k-1}
\lrb{
\chi \lrp{\frac{m}{d}} \frac{k-1}{12} \psi(N) \frac{m^{k-2}}{d^{k-2}} + O\left( \sqrt{N} 2^{\omega(N)} \frac{m^k}{d^k} \right)
} \\
&=\chi(m) d \,\frac{k-1}{12} \psi(N) m^{k-2} + O(\sqrt{N} 2^{\omega(N)} m^k) .
\end{align*}

This yields

\begin{align*}
a_2(m,N,k,\chi) &= \frac{1}{2} \lrb{ (\Tr T_m)^2  - \sum_{d \mid m} \chi(d) d^{k-1} \Tr T_{m^2/d^2} } \\
&= \frac{1}{2} \lrb{ (\Tr T_m)^2  - \sum_{d \mid m} \lrb{
\chi(m) d \,\frac{k-1}{12} \psi(N) m^{k-2} + O(\sqrt{N} 2^{\omega(N)} m^k)
} } \\
&= \frac{1}{2} \lrb{ (\Tr T_m)^2  -
\chi(m) \frac{k-1}{12} \psi(N) m^{k-2} \sigma_1(m) + O(\sqrt{N} 2^{\omega(N)} m^k)
} .
\end{align*}

Since $m$ is not a perfect square, we apply Lemma <ref> to $\Tr T_m$ and obtain

\begin{align}
&= \frac{1}{2} \lrb{ O(2^{\omega(N)} m^{k/2})^2  -
\chi(m) \frac{k-1}{12} \psi(N) m^{k-2} \sigma_1(m) - O(\sqrt{N} 2^{\omega(N)} m^k)
} \\
&= \frac{1}{2} \lrb{ -
\chi(m) \frac{k-1}{12} \psi(N) m^{k-2} \sigma_1(m) + O(\sqrt{N} 2^{\omega(N)} m^k)
} \\
&= \frac{\psi(N) m^{k-2} \sigma_1(m)}{2} \lrb{
- \chi(m) \frac{k-1}{12}
+ O(\theta_1(N))
} . \label{eqn:main-theorem-not-perfect-square-final-eqn}
\end{align}

Here we used the fact that $2^{\omega(N)} = O(\sqrt{N})$ (from the proof of Lemma <ref>) and the definition $\theta_1(N) = \frac{\sqrt{N} 2^{\omega(N)}}{\psi(N)}$ (also from Lemma <ref>).

Now, $\gcd(m,N)=1$ means that $\lrabs{\chi(m)} = 1$, and hence  $\lrabs{\chi(m) \frac{k-1}{12}} \geq \frac{1}{12}$ for all $k \geq 2$. But for sufficiently large $N$ (independent of $k$), the $O(\theta_1(N))$ term will be $< \frac{1}{12}$ in magnitude since $\theta_1(N) \longrightarrow 0$ according to Lemma <ref>. Thus $a_2(m,N,k,\chi)$  will be nonvanishing for sufficiently large $N$.

This leaves only finitely many $N$ to check. For these values of $N$, the $O(\theta_1(N))$ term will be bounded by a constant. So for $k$ sufficiently large, $\lrabs{-\chi(m) \frac{k-1}{12}} = \frac{k-1}{12}$ will be larger than that constant, and $a_2(m,N,k,\chi)$ will be nonvanishing.

This shows that $a_2(m,N,k,\chi)$ is nonvanishing for all but finitely many triples $(N,k,\chi)$.

Furthermore, note that when $\chi$ is trivial, $a_2(m,N,k)$ will be real. In this case, the expression inside the brackets of (<ref>) becomes $- \frac{k-1}{12} + O(\theta_1(N))$. So in particular, $a_2(m,N,k)$ will be negative for all but finitely many pairs $(N,k)$.

Finally, we prove Theorems <ref> and <ref> in the case when $m$ is a perfect square.

Let $m \geq 1$ be fixed and a perfect square. Suppose that $\gcd(N,m)=1$, $k \geq 2$, and $\chi$ is a Dirichlet character modulo $N$ with $\chi(-1) = (-1)^k$. Then $a_2(m,N,k,\chi)$ is nonvanishing for all but finitely many triples $(N,k,\chi)$.
Furthermore, when $\chi$ is trivial,
$a_2(m,N,k)$ is positive for all but finitely many pairs $(N,k)$.

By the same argument as in Proposition <ref>,

\begin{align*}
a_2(m,N,k,\chi) &= \frac{1}{2} \lrb{ (\Tr T_m)^2  -
\chi(m) \frac{k-1}{12} \psi(N) m^{k-2} \sigma_1(m) + O(\sqrt{N} 2^{\omega(N)} m^k) } .
\end{align*}

Then using the fact that $\sqrt{N} 2^{\omega(N)} = O\lrp{\psi(N)}$ from Lemma <ref>, this yields

\begin{align}
a_2(m,N,k,\chi) &= \frac{1}{2} \lrb{ (\Tr T_m)^2  + O(k \psi(N) m^k) }.
\end{align}

Since $m$ is a perfect square, we apply Lemma <ref> to $\Tr T_m$, and we have

\begin{align*}
(\Tr T_m)^2 &= \lrp{  \chi(\sqrt{m}) \frac{k-1}{12} \psi(N) m^{k/2-1} + O(\sqrt{N} 2^{\omega(N)} m^{k/2})  }^2  \\
&= \chi(m) \frac{(k-1)^2}{144} \psi(N)^2 m^{k-2} + O\lrp{k \psi(N) m^{k/2} \cdot  \sqrt{N} 2^{\omega(N)} m^{k/2}} + O\lrp{\sqrt{N} 2^{\omega(N)} m^{k/2}}^2 \\
&= \chi(m) \frac{(k-1)^2}{144} \psi(N)^2 m^{k-2} + O\lrp{k \psi(N)  \sqrt{N} 2^{\omega(N)} m^k} .
\end{align*}

Here, we again used the fact that $\sqrt{N} 2^{\omega(N)} = O\lrp{\psi(N)}$.

\begin{align}
a_2(m,N,k,\chi) &= \frac{1}{2} \lrb{ (\Tr T_m)^2  + O(k \psi(N) m^k) } \\
&= \frac{1}{2} \lrb{ \chi(m) \frac{(k-1)^2}{144} \psi(N)^2 m^{k-2} + O\lrp{k \psi(N)  \sqrt{N} 2^{\omega(N)} m^k}
}  \\
&= \frac{k \psi(N)^2 m^{k-2}}{2} \lrb{
\chi(m) \frac{(k-1)^2}{144k} + O(\theta_1(N))
}. \label{eqn:main-theorem-perfect-square-final-eqn}
\end{align}

Now, $\lrabs{\chi(m) \frac{(k-1)^2}{144k}} \geq \frac{1}{288}$ for all $k \geq 2$. But for sufficiently large $N$, the $O(\theta_1(N))$ term will be $< \frac{1}{288}$ in magnitude, according to Lemma <ref>. Thus $a_2(m,N,k,\chi)$  will be nonvanishing for sufficiently large $N$.

Again, this leaves only finitely many $N$ to check. For these values of $N$, the $O(\theta_1(N))$ term will be bounded by a constant, by Lemma <ref>. So for $k$ sufficiently large, $\lrabs{\chi(m) \frac{(k-1)^2}{144k}} = \frac{(k-1)^2}{144k}$ will be larger than that constant, and $a_2(m,N,k,\chi)$ will be nonvanishing.

This shows that $a_2(m,N,k,\chi)$ is nonvanishing for all but finitely many triples $(N,k,\chi)$.

Furthermore, note that when $\chi$ is trivial, the expression inside the brackets of (<ref>) becomes $\frac{(k-1)^2}{144k} + O(\theta_1(N))$. So in particular, $a_2(m,N,k)$ will be positive for all but finitely many pairs $(N,k)$.

Propositions <ref> and <ref> combine to imply Theorems <ref> and <ref>.

In these two proofs, we needed $\gcd(m,N)=1$ to use the fact that $\lrabs{\chi(m)} = 1$.
It is worth noting that this is the first place that we need this coprimality assumption. In particular, all of the trace bounds given above still work even when $\gcd(m,N) > 1$.

Note that all of the bounds given here are explicitly computable. So in Section <ref>, we compute all of these bounds for $m=3$, and give the complete list of pairs $(N,k)$ for which $a_2(3,N,k)$ is positive or zero. In Section <ref>, we compute the bounds for $m=4$, and give the complete list of pairs $(N,k)$ for which $a_2(4,N,k)$ is negative or zero.

§ PROOF OF THEOREM <REF>

In this section, we show Theorem <ref>: for $N$ coprime to $3$ and $k \geq 2$ even, $a_2(3,N,k)$ is positive or zero only for the pairs $(N,k)$ given in Table <ref>.

Observe that in the notation of Lemma <ref>, for $\gcd(N,3)=1$ and $k \geq 2$ even, we have

\begin{equation} \label{eqn:a2-coeff-T3}
a_2(3,N,k) = \frac{1}{2} \lrb{ (\Tr T_3)^2 - \Tr T_9 -3^{k-1} \Tr T_1 }.
\end{equation}

We bound the terms of (<ref>) separately in the following three lemmas.
Each of these bounds will be expressed in terms of the $\theta_i(N)$ defined in Lemma <ref>.

Let $N \geq 1$ and $k \geq 2$ be even. Then

\begin{align*}
\frac{(\Tr T_3)^2}{\psi(N) 3^k }
&\leq  \frac{448 + 160\sqrt{3}}{27} \theta_2(N).
\end{align*}

We examine each of the $A_{i,3}$ terms from (<ref>) separately.

First, by (<ref>),

$$A_{1,3} = \chi_0(\sqrt{3}) \frac{k-1}{12} \psi (N) 3^{k/2-1} = 0.$$

Second, by (<ref>) (recalling that the $t=t_0$ and $t=-t_0$ terms coincide) and Table <ref>,

\begin{align}
A_{2,3} = &\frac{1}{2} \sum_{t^2 < 12} U_{k-1}(t,3) \sum_{n}  h_w \lrp{ \frac{t^2-12}{n^2} } \mu (t,n,3) \\
= &\frac{1}{2} U_{k-1}(0,3) \sum_{n}  h_w \lrp{ \frac{-12}{n^2} } \mu(0,n,3) \\
&+ U_{k-1}(1,3)  \sum_{n}  h_w \lrp{ \frac{-11}{n^2} } \mu (1,n,3) \\
&+ U_{k-1}(2,3) \sum_{n}  h_w \lrp{ \frac{-8}{n^2} } \mu (2,n,3) \\
&+ U_{k-1}(3,3) \sum_{n}  h_w \lrp{ \frac{-3}{n^2} } \mu (3,n,3) \\
= &\frac{1}{2} U_{k-1}(0,3) \lrb{ h_w(-12) \mu(0,1,3) + h_w(-3) \mu(0,2,3) } \\
&+ U_{k-1}(1,3) \lrb{ h_w(-11) \mu (1,1,3) } \\
&+ U_{k-1}(2,3) \lrb{ h_w(-8) \mu(2,1,3) } \\
&+ U_{k-1}(3,3) \lrb{ h_w(-3) \mu(3,1,3) } \\
= &\frac{1}{2} U_{k-1}(0,3) [ \mu(0,1,3) + \frac{1}{3} \mu(0,2,3) ] \\
&+U_{k-1}(1,3) [ \mu (1,1,3) ] \\
&+U_{k-1}(2,3) [ \mu(2,1,3) ] \\
&+U_{k-1}(3,3) [ \frac{1}{3} \mu(3,1,3) ].
\end{align}

So by Lemma <ref>,

\begin{align}
\lrabs{A_{2,3}} &\leq  \, 2^{\omega(N)} 3^{(k-1)/2}\cdot 2 \lrb{\frac12 \lrp{1 + \frac{1}{3} \cdot 3} + (1) + (1) + \lrp{\frac13 } } \\
&= \frac{20}{3 \sqrt{3}} 2^{\omega(N)} 3^{k/2}.
\end{align}

Third, by (<ref>) (recalling that the $d=d_0$ and $d=m/d_0$ terms coincide) and Lemma <ref>,

\begin{align}
A_{3,3} &= \frac{1}{2} \sum_{d|3} \min(d,3/d)^{k-1} \Sigma(N,3,d) \\
&= \Sigma(N,3,1)  \\
&\leq  |-2| \cdot 2^{\omega(N)} \\
&= 2\cdot 2^{\omega(N)}.
\end{align}

Fourth, by (<ref>),

\begin{align}
A_{4,3}  &\leq \sum_{c\mid 3} c \ =  1+3=4.
\end{align}

Now, note that $A_{3,3}$ and $A_{4,3}$ here are both positive and $\leq 4 \cdot 2^{\omega(N)}$. So putting all this together, we obtain

\begin{align}
|\Tr T_3 | &= |A_{1,3} - A_{2,3} - A_{3,3} + A_{4,3} | \\
&\leq |A_{2,3}| + |A_{3,3} - A_{4,3} | \\
&\leq \frac{20}{3\sqrt{3}} \cdot 2^{\omega(N)} 3^{k/2} + 4 \cdot 2^{\omega(N)} \\
&\leq \frac{20}{3\sqrt{3}} \cdot 2^{\omega(N)} 3^{k/2} + \frac{4}{3} \cdot 3^{k/2}\,2^{\omega(N)} \\
&= \lrp{\frac{20}{3\sqrt{3}} + \frac43}  2^{\omega(N)} 3^{k/2}  ,
\end{align}

which yields

\begin{align}
\frac{(\Tr T_3)^2}{\psi(N) 3^k }
&\leq   \frac{\lrp{\frac{20}{3\sqrt{3}} + \frac43}^2  (2^{\omega(N)})^2 3^k}{\psi(N) 3^k} \\
&= \frac{448 + 160\sqrt{3}}{27} \theta_2(N) ,
\end{align}

as desired.

Next, we bound the $\Tr T_9$ term from (<ref>).

Let $N \geq 1$ with $\gcd(N,3)=1$ and $k \geq 2$ be even. Then

\begin{align}
\lrabs{\frac{\Tr T_9 - A_{1,9}}{\psi(N) 3^k}}
&\leq \frac{65}{6} \theta_3(N) + \frac{1}{6} \theta_1(N) ,
\end{align}

$$A_{1,9} = \frac{k-1}{108} \psi(N) 3^k .$$

We examine each of the $A_{i,9}$ terms from (<ref>) separately.

First, by (<ref>),

\begin{align}
A_{1,9} &= \chi_0(\sqrt{9}) \frac{k-1}{12} \psi (N) 9^{k/2-1} = \frac{k-1}{108} \psi (N) 3^k ,
\end{align}

as claimed.

Second, similarly to the proof of Lemma <ref>, we compute

\begin{align}
A_{2,9} = &\frac{1}{2} \sum_{t^2 < 36} U_{k-1}(t,9) \sum_{n}  h_w \lrp{ \frac{t^2-36}{n^2} } \mu (t,n,9) \\
= &\frac{1}{2} U_{k-1}(0,9) \sum_{n}  h_w \lrp{ \frac{-36}{n^2} } \mu(0,n,9) \\
&+U_{k-1}(1,9) \sum_{n}  h_w \lrp{ \frac{-35}{n^2} } \mu(1,n,9) \\
&+U_{k-1}(2,9) \sum_{n}  h_w \lrp{ \frac{-32}{n^2} } \mu(2,n,9) \\
&+U_{k-1}(3,9) \sum_{n}  h_w \lrp{ \frac{-27}{n^2} } \mu(3,n,9) \\
&+U_{k-1}(4,9) \sum_{n}  h_w \lrp{ \frac{-20}{n^2} } \mu(4,n,9) \\
&+U_{k-1}(5,9) \sum_{n}  h_w \lrp{ \frac{-11}{n^2} } \mu(5,n,9) \\
= &\frac{1}{2} U_{k-1}(0,9) \lrb{ h_w(-36)\mu(0,1,9) + h_w(-4)\mu(0,3,9) } \\
&+U_{k-1}(1,9) \lrb{ h_w(-35)\mu(1,1,9) } \\
&+U_{k-1}(2,9) \lrb{ h_w(-32) \mu(2,1,9) + h_w(-8)\mu(2,2,9) } \\
&+U_{k-1}(3,9) \lrb{ h_w(-27)\mu(3,1,9) + h_w(-3)\mu(3,3,9) } \\
&+U_{k-1}(4,9) \lrb{ h_w(-20) \mu(4,1,9) } \\
&+U_{k-1}(5,9) \lrb{ h_w(-11) \mu(5,1,9) } \\
= &\frac{1}{2} U_{k-1}(0,9) [ 2\mu(0,1,9) + \frac{1}{2} \mu(0,3,9) ] \\
&+U_{k-1}(1,9) \lrb{ 2\mu(1,1,9) } \\
&+U_{k-1}(2,9) \lrb{ 2\mu(2,1,9) + \mu(2,2,9) } \\
&+U_{k-1}(3,9) [ \mu(3,1,9) + \frac{1}{3} \mu(3,3,9) ] \\
&+U_{k-1}(4,9) \lrb{ 2\mu(4,1,9) } \\
&+U_{k-1}(5,9) \lrb{ \mu(5,1,9) }.
\end{align}

So by Lemma <ref>,

\begin{align}
|A_{2,9}| \leq & \, 2^{\omega(N)} 9^{(k-1)/2} \cdot 2 \lrb{\frac12 \left(2+\frac{1}{2}\cdot 4\right) + (2) + (2 + 3) + \left(1 + \frac13\cdot 4 \right) + (2) + (1) } \\
=&  \frac{86}{9}\cdot 2^{\omega(N)} 3^k .
\end{align}

Third, by (<ref>) and Lemma <ref>,

\begin{align}
A_{3,9} &= \frac{1}{2} \sum_{d|9} \min(d,9/d)^{k-1} \Sigma(N,9,d) \\
&=  \Sigma(N,9,1) + \frac{1}{2} \cdot3^{k-1} \Sigma(N,9,3)  \\
&\leq  |-8|\cdot  2^{\omega(N)} + \frac{1}{2}\cdot 3^{k-1} \sqrt{N} 2^{\omega(N)} \\
&= \frac{1}{6}\cdot 3^k \sqrt{N} 2^{\omega(N)} + 8 \cdot 2^{\omega(N)} .
\end{align}

Fourth, by (<ref>),

\begin{align}
A_{4,9}  &\leq \sum_{c|9} c \ =  1+3+9=13 .
\end{align}

Now, note that $A_{3,9}$ and $A_{4,9}$ here are both positive and $\leq \frac{1}{6} \cdot 3^k \sqrt{N} 2^{\omega(N)} + \frac{23}{2} \cdot 2^{\omega(N)}$.
So putting this all together, we obtain

\begin{align}
\lrabs{\Tr T_9 - A_{1,9}}
&= \lrabs{- A_{2,9} - A_{3,9} + A_{4,9}} \\
&\leq \lrabs{A_{2,9}} + \lrabs{A_{3,9} - A_{4,9}} \\
&\leq \frac{86}{9}\cdot 2^{\omega(N)} 3^k + \frac{1}{6}\cdot 3^k \sqrt{N} 2^{\omega(N)} + \frac{23}{2}\cdot 2^{\omega(N)} \\
&\leq \frac{86}{9}\cdot 2^{\omega(N)} 3^k + \frac{1}{6}\cdot 3^k \sqrt{N} 2^{\omega(N)} + \frac{23}{18}\cdot 3^k 2^{\omega(N)} \\
&= \frac{65}{6}\cdot 2^{\omega(N)} 3^k + \frac{1}{6}\cdot 3^k \sqrt{N} 2^{\omega(N)} ,
\end{align}

which yields

\begin{align}
\lrabs{\frac{\Tr T_9 - A_{1,9}}{\psi(N) 3^k}}
&\leq \frac{65}{6} \theta_3(N) + \frac{1}{6} \theta_1(N),
\end{align}

as desired.

Finally, we bound the $\Tr T_1$ term from (<ref>).

Let $N \geq 1$ and $k \geq 2$ be even. Then

$$\lrabs{\frac{\Tr T_1 - A_{1,1}}{\psi(N)}} \leq \frac{5}{3} \theta_3(N) + \frac{1}{2} \theta_1(N), $$

$$A_{1,1} = \frac{k-1}{12} \psi(N) .$$

We examine each of the $A_{i,1}$ terms from (<ref>) separately.

First, by (<ref>),

\begin{align}
A_{1,1} &= \chi_0(\sqrt{1}) \frac{k-1}{12} \psi (N) 1^{k/2-1} = \frac{k-1}{12} \psi (N) ,
\end{align}

as claimed.

Second, by (<ref>),

\begin{align}
A_{2,1} =& \frac{1}{2} \sum_{t^2 < 4} U_{k-1}(t,1) \sum_{n}  h_w \lrp{ \frac{t^2-4}{n^2} } \mu (t,n,1) \\
=& \frac{1}{2} U_{k-1}(0,1) \sum_{n}  h_w \lrp{ \frac{-4}{n^2} } \mu(0,n,1)
+ U_{k-1}(1,1) \sum_{n}  h_w \lrp{ \frac{-3}{n^2} } \mu(1,n,1) \\
=& \frac{1}{2} U_{k-1}(0,1) h_w \lrp{ -4 } \mu(0,1,1)  + U_{k-1}(1,1) h_w \lrp{ -3 } \mu(1,1,1) \\
=& \frac{1}{2} \cdot \frac{1}{2} U_{k-1}(0,1) \mu(0,1,1)  + \frac{1}{3} U_{k-1}(1,1) \mu(1,1,1).
\end{align}

So by Lemma <ref>,

\begin{align}
\lrabs{A_{2,1}} \leq \frac{1}{4} \cdot 2 \cdot 2^{\omega(N)} + \frac{1}{3} \cdot 2 \cdot 2^{\omega(N)} = \frac{7}{6}\cdot 2^{\omega(N)} .
\end{align}

Third, by (<ref>) and Lemma <ref>,

\begin{align}
A_{3,1} &= \frac{1}{2} \sum_{d|1} \min(d,1/d)^{k-1} \Sigma(N,1,d) \\
&=  \frac{1}{2} \Sigma(N,1,1)  \\
&\leq \frac{1}{2} \sqrt{N} 2^{\omega(N)} .
\end{align}

Fourth, by (<ref>),

$$A_{4,1} \leq \sum_{c|1} c \ = 1 .$$

Now, note that $A_{3,1}$ and $A_{4,1}$ are both positive and $\leq \frac{1}{2} \sqrt{N} 2^{\omega(N)} + \frac{1}{2} \cdot 2^{\omega(N)}$. So putting all this together, we obtain

\begin{align}
\lrabs{\Tr T_1 - A_{1,1}}
&= \lrabs{ -A_{2,1} - A_{3,1} + A_{4,1} }  \\
&\leq  \lrabs{A_{2,1}} + \lrabs{A_{3,1} - A_{4,1}} \\
&\leq  \frac{7}{6}\cdot 2^{\omega(N)} + \frac{1}{2} \sqrt{N} 2^{\omega(N)} + \frac{1}{2}\cdot 2^{\omega(N)} \\
&=  \frac{5}{3}\cdot 2^{\omega(N)} + \frac{1}{2} \sqrt{N} 2^{\omega(N)} ,
\end{align}

which yields

\begin{align}
\lrabs{\frac{\Tr T_1 - A_{1,1}}{\psi(N)}} &\leq \frac{5}{3} \theta_3(N) + \frac{1}{2} \theta_1(N),
\end{align}

completing the proof.

Note that $\Tr T_1$ is just the dimension of $S_k(\Gamma_0(N))$. So Lemma <ref> is just a dimension estimate. And in fact, one can also derive the bounds in this lemma from the dimension formula given in <cit.>.

We are now ready to prove Theorem <ref>.

Suppose that $\gcd(N,3)=1$ and that $k \geq 2$ is even.
Then the second coefficient $a_2(3,N,k)$ is positive or zero only for the pairs $(N,k)$ given in Table <ref>.

By (<ref>) and Lemmas <ref> and <ref>,

\begin{align}
&\ \ \ \  a_2(3,N,k)\\
&= \frac{1}{2} \lrb{ (\Tr T_3)^2 - \Tr T_9 - 3^{k-1} \Tr T_1 } \\
&= \frac{1}{2} \lrb{ (\Tr T_3)^2 - A_{1,9} - \lrp{\Tr T_9 - A_{1,9}} - 3^{k-1} A_{1,1} - 3^{k-1} \lrp{\Tr T_1 - A_{1,1} } } \\
&= \frac{1}{2} \lrb{- \frac{k-1}{108} \psi(N) 3^k - \frac{k-1}{12} \psi(N) 3^{k-1} + (\Tr T_3)^2 - \lrp{\Tr T_9 - A_{1,9}} - 3^{k-1} \lrp{\Tr T_1 - A_{1,1} } } \\
&= \frac{\psi(N) 3^k}{2} \lrb{ - \frac{k-1}{27} + \frac{(\Tr T_3)^2}{\psi(N) 3^k } - \lrp{ \frac{\Tr T_9 - A_{1,9}}{\psi(N) 3^k}  } - \frac{1}{3} \lrp{ \frac{\Tr T_1 - A_{1,1}}{\psi(N)}  } } \\
&= \frac{\psi(N) 3^k}{2} \lrb{- \frac{k-1}{27} + E(N,k) } , \label{eqn:a2-3-final-eqn}
\end{align}

where $E(N,k)$ denotes the three error terms above. In particular, from Lemmas <ref>, <ref>, and <ref>,

\begin{align}
\lrabs{E(N,k)} &= \lrabs{  \frac{(\Tr T_3)^2}{\psi(N) 3^k } - \lrp{ \frac{\Tr T_9 - A_{1,9}}{\psi(N) 3^k}  } - \frac{1}{3} \lrp{ \frac{\Tr T_1 - A_{1,1}}{\psi(N)} }  }   \\
&\leq  \frac{448 + 160\sqrt{3}}{27} \theta_2(N)  +  \lrp{\frac{65}{6} \theta_3(N) + \frac{1}{6} \theta_1(N)} + \frac{1}{3} \lrp{\frac{5}{3} \theta_3(N) + \frac{1}{2} \theta_1(N)} \\
&=  \frac{448 + 160\sqrt{3}}{27} \theta_2(N)  +  \frac{205}{18} \theta_3(N) + \frac{1}{3} \theta_1(N) .
\end{align}

For $N \geq 63,\!000,\!000$, we have the bounds  $\theta_1(N) \leq 0.0106$, $\theta_2(N) \leq 0.000314$, and $\theta_3(N) \leq 0.000015$ given in Lemma <ref>.

\begin{align}
\lrabs{E(N,k)} &\leq \frac{448 + 160\sqrt{3}}{27} 0.000314  +  \frac{205}{18} 0.000015 + \frac{1}{3} 0.0106 \\
&\leq 0.0122 ,
\end{align}

which is $< \frac{k-1}{27}$ for all $k \geq 2$. By (<ref>), this shows that $a_2(3,N,k) < 0$ for $N \geq 63,\!000,\!000$ and $k \geq 2$.

Utilizing the table in Lemma <ref>, an identical argument using $2,\!700,\!000$, $150,\!000$, $8,\!800$, $571$, $43$, and $1$ as the bounds for $N$, shows that $a_2(3,N,k) < 0$ for $N \geq 2,\!700,\!000, k \geq 4$; $N \geq 150,\!000, k \geq 10$; $N \geq 8,\!800,\ k \geq 34$; $N \geq 571, k \geq 116$; $N \geq 43, k \geq 346$; and $N \geq 1, k \geq 1290$.

We then check the finite number of cases left by computer, which yields the complete list given in Table <ref>. See <cit.> for the code.

\begin{equation}
\setlength{\arraycolsep}{2.5mm}
\begin{array}{|c|c|c||c|c|c||c|c|c||c|c|c|}
\hline
\multicolumn{12}{|c|}{\makecell{
\text{All pairs $(N,k)$ for which $a_2(3,N,k)$ is positive or zero,} \\
\text{ along with $\dim S_k(\Gamma_0(N))$ and the actual value of $a_2(3,N,k)$.}
}} \\
\hline
(N,k) & \dim & a_2 & (N,k) & \dim & a_2 & (N,k) & \dim & a_2 & (N,k) & \dim & a_2 \\
\hline
\hline
(1,2) & 0 & 0 & (8,2) & 0 & 0 & (4,6) & 1 & 0 & (4,8) & 2 & 144 \\
\hline
(1,4) & 0 & 0 & (10,2) & 0 & 0 & (5,4) & 1 & 0 & (22,2) & 2 & 1 \\
\hline
(1,6) & 0 & 0 & (13,2) & 0 & 0 & (5,6) & 1 & 0 & (28,2) & 2 & 4 \\
\hline
(1,8) & 0 & 0 & (16,2) & 0 & 0 & (7,4) & 1 & 0 & (34,2) & 3 & 0 \\
\hline
(1,10) & 0 & 0 & (25,2) & 0 & 0 & (8,4) & 1 & 0 & (40,2) & 3 & 4 \\
\hline
(1,14) & 0 & 0 & (1,12) & 1 & 0 & (11,2) & 1 & 0 & (64,2) & 3 & 0 \\
\hline
(2,2) & 0 & 0 & (1,16) & 1 & 0 & (14,2) & 1 & 0 & (38,2) & 4 & 3 \\
\hline
(2,4) & 0 & 0 & (1,18) & 1 & 0 & (17,2) & 1 & 0 & (44,2) & 4 & 0 \\
\hline
(2,6) & 0 & 0 & (1,20) & 1 & 0 & (19,2) & 1 & 0 & (56,2) & 5 & 0 \\
\hline
(4,2) & 0 & 0 & (1,22) & 1 & 0 & (20,2) & 1 & 0 & (67,2) & 5 & 1 \\
\hline
(4,4) & 0 & 0 & (1,26) & 1 & 0 & (32,2) & 1 & 0 & (80,2) & 7 & 0 \\
\hline
(5,2) & 0 & 0 & (2,8) & 1 & 0 & (49,2) & 1 & 0 & (140,2) & 19 & 0 \\
\hline
(7,2) & 0 & 0 & (2,10) & 1 & 0 & (2,12) & 2 & 63504 & (280,2) & 41 & 0 \\
\hline
\end{array}
\end{equation}

Now, in the case of $m=2$, Clayton et al. <cit.> already gave the complete list of $(N,k)$ for which $a_2(2,N,k)$ vanishes. But for completeness, we extend their result slightly and give the complete list of $(N,k)$ for which $a_2(2,N,k)$ is positive or zero. We forgo repeating all of the exact same details for the $m=2$ case, and just give the corresponding bounds that our method would yield.

Suppose that $\gcd(N,2)=1$ and that $k \geq 2$ is even.
Then the second coefficient $a_2(2,N,k)$ is positive or zero only for the pairs $(N,k)$ given in Table <ref>.

From Lemma <ref>, we have

\begin{equation} \label{eqn:a2-coeff-T2}
a_2(2,N,k) = \frac{1}{2} \lrb{ (\Tr T_2)^2 - \Tr T_4 - 2^{k-1} \Tr T_1 }.
\end{equation}

Then by an identical method as in Lemmas <ref>, <ref>, and <ref>, we obtain the bounds

\begin{equation}
\begin{alignedat}{6}
\frac{(\Tr T_2)^2}{\psi(N) 2^k }
&\leq  \frac{41 + 24\sqrt{2}}{4} \theta_2(N), &&&& \\
\lrabs{\frac{\Tr T_4 - A_{1,4}}{\psi(N) 2^k}}
&\leq \frac{17}{2} \theta_3(N) + \frac{1}{4} \theta_1(N), && \qquad \text{where} \qquad && A_{1,4} = \frac{k-1}{48} \psi(N) 2^k , \\
\lrabs{\frac{\Tr T_1 - A_{1,1}}{\psi(N)}}
&\leq \frac{5}{3} \theta_3(N) + \frac{1}{2} \theta_1(N), && \qquad \text{where} \qquad  && A_{1,1} = \frac{k-1}{12} \psi(N) .
\end{alignedat}
\end{equation}

As done in Theorem <ref>, combining these three bounds gives

\begin{align}
a_2(2,N,k) &= \frac{\psi(N) 2^k}{2} \lrb{- \frac{k-1}{16} + E(N,k) } ,
\end{align}

\begin{align}
\lrabs{E(N,k)} &\leq  \frac{41 + 24\sqrt{2}}{4} \theta_2(N)  +  \frac{28}{3} \theta_3(N) + \frac{1}{2} \theta_1(N) .
\end{align}

This yields $a_2(2,N,k) <0$ for $N \geq 2,\!700,\!000, k \geq 2$; $N \geq 150,\!000, k \geq 6$; $N \geq 8,\!800,\ k \geq 16$; $N \geq 571, k \geq 50$; $N \geq 43, k \geq 148$; and $N \geq 1, k \geq 562$.

We then check the finite number of cases left by computer, which yields the complete list given in Table <ref>. See <cit.> for the code.

\begin{equation}
\setlength{\arraycolsep}{2.5mm}
\begin{array}{|c|c|c||c|c|c||c|c|c||c|c|c|}
\hline
\multicolumn{12}{|c|}{\makecell{
\text{All pairs $(N,k)$ for which $a_2(2,N,k)$ is positive or zero,} \\
\text{ along with $\dim S_k(\Gamma_0(N))$ and the actual value of $a_2(2,N,k)$.}
}} \\
\hline
(N,k) & \dim & a_2 & (N,k) & \dim & a_2 & (N,k) & \dim & a_2 & (N,k) & \dim & a_2 \\
\hline
\hline
(1,2) & 0 & 0 & (7,2) & 0 & 0 & (1,26) & 1 & 0 & (17,2) & 1 & 0 \\
\hline
(1,4) & 0 & 0 & (9,2) & 0 & 0 & (3,6) & 1 & 0 & (19,2) & 1 & 0 \\
\hline
(1,6) & 0 & 0 & (13,2) & 0 & 0 & (3,8) & 1 & 0 & (21,2) & 1 & 0 \\
\hline
(1,8) & 0 & 0 & (25,2) & 0 & 0 & (5,4) & 1 & 0 & (27,2) & 1 & 0 \\
\hline
(1,10) & 0 & 0 & (1,12) & 1 & 0 & (5,6) & 1 & 0 & (49,2) & 1 & 0 \\
\hline
(1,14) & 0 & 0 & (1,16) & 1 & 0 & (7,4) & 1 & 0 & (37,2) & 2 & 0 \\
\hline
(3,2) & 0 & 0 & (1,18) & 1 & 0 & (9,4) & 1 & 0 & (33,2) & 3 & 0 \\
\hline
(3,4) & 0 & 0 & (1,20) & 1 & 0 & (11,2) & 1 & 0 & (57,2) & 5 & 0 \\
\hline
(5,2) & 0 & 0 & (1,22) & 1 & 0 & (15,2) & 1 & 0 & \multicolumn{3}{c|}{~} \\
\hline
\end{array}
\end{equation}

§ PROOF OF THEOREM <REF>

In this section, we show Theorem <ref>: for $N$ coprime to $4$ and $k \geq 2$ even, $a_2(4,N,k)$ is negative or zero only for the pairs $(N,k)$ given in <cit.>.

Observe that in the notation of Lemma <ref>, for $\gcd(N,4)=1$ and $k \geq 2$ even, we have

\begin{equation} \label{eqn:a2-coeff-T4}
a_2(4,N,k) = \frac{1}{2} \lrb{ (\Tr T_4)^2 - \Tr T_{16} - 2^{k-1} \Tr T_4 - 4^{k-1} \Tr T_1 }.
\end{equation}

We bound the four terms of (<ref>) separately in Lemmas <ref> - <ref>.

Let $N \geq 1$ with $\gcd(N,4)=1$ and $k \geq 2$ be even such that $\frac{k-1}{48} \geq 7 \theta_3(N) + \frac14 \theta_1(N) $.

\begin{align*}
\frac{(\Tr T_4)^2}{(k-1) 4^k \psi(N)^2 }
&\geq \frac{k-1}{2304} - \frac{7}{24} \theta_3(N) - \frac{1}{96} \theta_1(N).
\end{align*}

We examine each of the $A_{i,4}$ terms from (<ref>) separately.

First, by (<ref>),

$$A_{1,4} = \chi_0(\sqrt{4}) \frac{k-1}{12} \psi (N) 4^{k/2-1} = \frac{k-1}{48} \psi (N) 2^k .$$

Second, summing over $t$ with $t^2<16$ and positive $n$ such that $n^2\mid (t^2-16)$ and $(t^2-16)/n^2\equiv 0,1\pmod{4}$, we get

\begin{align}
A_{2,4} = &\frac{1}{2} \sum_{t^2 < 16} U_{k-1}(t,4) \sum_{n}  h_w \lrp{ \frac{t^2-16}{n^2} } \mu (t,n,4) \\
= &\frac{1}{2} U_{k-1}(0,4) [ \mu(0,1,4) + \frac12 \mu(0,2,4) ] \\
&+ U_{k-1}(1,4) \lrb{ 2 \mu (1,1,4) } \\
&+ U_{k-1}(2,4) [ \mu(2,1,4) + \frac13 \mu(2,2,4) ] \\
&+ U_{k-1}(3,4) \lrb{ \mu(3,1,4) }.
\end{align}

So by Lemma <ref>,

\begin{align}
\lrabs{A_{2,4}} &\leq  \, 2^{\omega(N)} 4^{(k-1)/2}\cdot 2 \lrb{\frac12 \lrp{1 + \frac{1}{2} \cdot 3} + (2) + \lrp{1+\frac{1}{3} \cdot 3} + \lrp{ 1 } } \\
&= \frac{25}{4} \cdot 2^{k} \, 2^{\omega(N)} .
\end{align}

Third, by (<ref>) (recalling that the $d=d_0$ and $d=m/d_0$ terms coincide) and Lemma <ref>,

\begin{align}
A_{3,4} &= \frac{1}{2} \sum_{d|4} \min(d,4/d)^{k-1} \Sigma(N,4,d) \\
&= \Sigma(N,4,1) + \frac12 \cdot 2^{k-1} \Sigma(N,4,2)  \\
&\leq  |-3| \cdot 2^{\omega(N)} + \frac12 \cdot 2^{k-1} \sqrt{N} 2^{\omega(N)}\\
&= 3\cdot 2^{\omega(N)} + \frac14\cdot  2^k \sqrt{N} 2^{\omega(N)}.
\end{align}

Putting this all together, and using the fact that $A_{4,16}\ge0$, we obtain

\begin{align}
\Tr T_4 &= A_{1,4} - A_{2,4} - A_{3,4} + A_{4,4}  \\
&\geq A_{1,4} - |A_{2,4}| - A_{3,4} \\
&\geq \frac{k-1}{48} \psi(N) 2^k - \frac{25}{4}\cdot  2^k \,2^{\omega(N)} - 3 \cdot 2^{\omega(N)} - \frac14 \cdot 2^k \sqrt{N} 2^{\omega(N)} \\
&\geq \frac{k-1}{48} \psi(N) 2^k - \frac{25}{4}\cdot  2^k \, 2^{\omega(N)} - \frac34\cdot  2^k \, 2^{\omega(N)} - \frac14 \cdot 2^k \sqrt{N} 2^{\omega(N)} \\
&= \psi(N) 2^k \lrp{ \frac{k-1}{48} - 7 \theta_3(N) - \frac14 \theta_1(N) } .
\end{align}

Thus if $\frac{k-1}{48} \geq  7 \theta_3(N) + \frac14 \theta_1(N)$, then we have

\begin{align}
\frac{(\Tr T_4)^2}{(k-1) 4^k \, \psi(N)^2}
&\geq   \frac{  \lrp{ \frac{k-1}{48} - 7 \theta_3(N) - \frac14 \theta_1(N) }^2  }{k-1} \\
&\geq   \frac{  \lrp{ \frac{k-1}{48}}^2 - 2 \frac{k-1}{48} \lrp{ 7 \theta_3(N) + \frac14 \theta_1(N) }  }{k-1} \\
&=   \frac{k-1}{2304} - \frac{7}{24} \theta_3(N) - \frac{1}{96} \theta_1(N),   \\
\end{align}

as desired.

Next, we bound the $\Tr T_{16}$ term from (<ref>).

Let $N \geq 1$ with $\gcd(N,4)=1$ and $k \geq 2$ be even. Then

\begin{align}
\frac{\Tr T_{16}}{(k-1) 4^k \, \psi(N)^2}
&\leq \frac{4309}{192N} .
\end{align}

We examine each of the $A_{i,16}$ terms from (<ref>) separately.

First, by (<ref>),

\begin{align}
A_{1,16} &= \chi_0(\sqrt{16}) \frac{k-1}{12} \psi (N) 16^{k/2-1} = \frac{k-1}{192} \psi (N) 4^k .
\end{align}

Second, summing over $t$ with $t^2<64$ and positive $n$ such that $n^2\mid (t^2-64)$ and $(t^2-64)/n^2\equiv 0,1\pmod{4}$, we get

\begin{align}
A_{2,16} = &\frac{1}{2} \sum_{t^2 < 64} U_{k-1}(t,16) \sum_{n}  h_w \lrp{ \frac{t^2-64}{n^2} } \mu (t,n,16) \\
% = &\frac{1}{2} U_{k-1}(0,16) \sum_{n}  h_w \lrp{ \frac{-64}{n^2} } \mu(0,n,16) \\
%  &+U_{k-1}(1,16) \sum_{n}  h_w \lrp{ \frac{-63}{n^2} } \mu(1,n,16) \\
%  &+U_{k-1}(2,16) \sum_{n}  h_w \lrp{ \frac{-60}{n^2} } \mu(2,n,16) \\
%  &+U_{k-1}(3,16) \sum_{n}  h_w \lrp{ \frac{-55}{n^2} } \mu(3,n,16) \\
%  &+U_{k-1}(4,16) \sum_{n}  h_w \lrp{ \frac{-48}{n^2} } \mu(4,n,16) \\
%  &+U_{k-1}(5,16) \sum_{n}  h_w \lrp{ \frac{-39}{n^2} } \mu(5,n,16) \\
%  &+U_{k-1}(6,16) \sum_{n}  h_w \lrp{ \frac{-28}{n^2} } \mu(6,n,16) \\
%  &+U_{k-1}(7,16) \sum_{n}  h_w \lrp{ \frac{-15}{n^2} } \mu(7,n,16) \\
%  = &\frac{1}{2} U_{k-1}(0,16) \lrb{ h_w(-64) \mu(0,1,16) + h_w(-16) \mu(0,2,16) + h_w(-4) \mu(0,4,16) }   \\
%  &+U_{k-1}(1,16) \lrb{ h_w(-63) \mu(1,1,16) + h_w(-7) \mu(1,3,16) } \\
%  &+U_{k-1}(2,16) \lrb{ h_w(-60) \mu(2,1,16) + h_w(-15) \mu(2,2,16) } \\
%  &+U_{k-1}(3,16) \lrb{ h_w(-55) \mu(3,1,16) } \\
%  &+U_{k-1}(4,16) \lrb{ h_w(-48) \mu(4,1,16) + h_w(-12) \mu(4,2,16) + h_w(-3) \mu(4,4,16) } \\
%  &+U_{k-1}(5,16) \lrb{ h_w(-39) \mu(5,1,16)} \\
%  &+U_{k-1}(6,16) \lrb{ h_w(-28) \mu(6,1,16) + h_w(-7) \mu(6,2,16) } \\
%  &+U_{k-1}(7,16) \lrb{ h_w(-15) \mu(7,1,16) } \\
= &\frac{1}{2} U_{k-1}(0,16) [ 2 \mu(0,1,16) + \mu(0,2,16) + \frac12 \mu(0,4,16) ]   \\
&+U_{k-1}(1,16) \lrb{ 4 \mu(1,1,16) +  \mu(1,3,16) } \\
&+U_{k-1}(2,16) \lrb{ 2 \mu(2,1,16) + 2 \mu(2,2,16) } \\
&+U_{k-1}(3,16) \lrb{ 4 \mu(3,1,16) } \\
&+U_{k-1}(4,16) [ 2 \mu(4,1,16) + \mu(4,2,16) + \frac13 \mu(4,4,16) ] \\
&+U_{k-1}(5,16) \lrb{ 4 \mu(5,1,16)} \\
&+U_{k-1}(6,16) \lrb{ \mu(6,1,16) + \mu(6,2,16) } \\
&+U_{k-1}(7,16) \lrb{ 2 \mu(7,1,16) } .
\end{align}

Thus,  by Lemma <ref>,

\begin{align}
|A_{2,16}| \leq & \, 2^{\omega(N)} 16^{(k-1)/2} \cdot 2 \Bigg[ \frac12 \lrp{2 + 3 + \frac12 \cdot 6} + (4 + 4) + (2 + 2\cdot 3) \\
& \qquad\qquad\qquad\qquad + (4) + \lrp{2 + 3 + \frac13 \cdot 6} + (4) + \lrp{1+3} + (2) \Bigg] \\
=&  \frac{41}{2}\cdot 2^{\omega(N)} 4^k .
\end{align}

Third, by (<ref>),

\begin{align}
A_{4,16}  &\leq \sum_{c | 16} c \ =  1+2+4+8+16=31 .
\end{align}

Putting this all together, and using the fact that $A_{3,16}\ge0$, we obtain

\begin{align}
\Tr T_{16}
&= A_{1,16} - A_{2,16} - A_{3,16} + A_{4,16} \\
&\leq  A_{1,16} + \lrabs{A_{2,16}} + A_{4,16} \\
&\leq \frac{k-1}{192} \psi(N) 4^k + \frac{41}{2} \cdot2^{\omega(N)} 4^k + 31 \\
&\leq \frac{k-1}{192} \psi(N) 4^k + \frac{41}{2} \psi(N) 4^k (k-1) + \frac{31}{16} \psi(N) 4^k (k-1) \\
&=  \frac{4309}{192}\cdot \psi(N) 4^k (k-1).
\end{align}

This yields

\begin{align}
\frac{\Tr T_{16}}{(k-1) 4^k \psi(N)^2}
\leq \frac{4309}{192 \psi(N)}
\leq \frac{4309}{192N},
\end{align}

as desired.

Let $N \geq 1$ with $\gcd(N,4)=1$ and $k \geq 2$ be even.

\begin{align*}
\frac{\Tr T_4}{(k-1) 2^k \psi(N)^2 }
&\leq \frac{385}{48N}.
\end{align*}

We examine each of the $A_{i,4}$ terms from (<ref>) separately.

From the computations in the proof of Lemma <ref>, we have

\begin{align} A_{1,4} = \frac{k-1}{48} \psi (N) 2^k \qquad
\text{and}\qquad
\lrabs{A_{2,4}} &\leq  \frac{25}{4} 2^{k} \, 2^{\omega(N)} .
\end{align}

Also, by (<ref>),

\begin{align}
A_{4,4}  &\leq \sum_{c\mid 4} c \ =  1+2+4=7.
\end{align}

Putting all this together, and noticing that $A_{3,4}\ge0$, we obtain

\begin{align}
\Tr T_4 &= A_{1,4} - A_{2,4} - A_{3,4} + A_{4,4}  \\
&\leq A_{1,4} + |A_{2,4}| + A_{4,4} \\
&\leq \frac{k-1}{48} \psi(N) 2^k + \frac{25}{4} \cdot 2^k \,2^{\omega(N)} + 7 \\
&\leq \frac{k-1}{48} \psi(N) 2^k + \frac{25}{4}\cdot 2^k \psi(N)(k-1) + \frac{7}{4}\cdot 2^k \psi(N)(k-1) \\
&=\frac{385}{48}\cdot  \psi(N) 2^k (k-1) .
\end{align}

This yields

\begin{align}
\frac{\Tr T_4}{(k-1) 2^k \, \psi(N)^2}
\leq   \frac{  385  }{48 \psi(N)}
\leq   \frac{385}{48N} ,
\end{align}

as desired.

Let $N \geq 1$ and $k \geq 2$ be even. Then

$$\frac{\Tr T_1}{(k-1)\psi(N)^2} \leq \frac{9}{4N}. $$

We examine each of the $A_{i,1}$ terms from (<ref>) separately.

By the calculations in the proof of Lemma <ref>, we have

\begin{align}
A_{1,1} = \frac{k-1}{12} \psi (N), \qquad
\lrabs{A_{2,1}} \leq \frac{7}{6} 2^{\omega(N)} ,\qquad
\text{and} \qquad
A_{4,1} \leq   1 . \end{align}

Putting all this together, and noticing that $A_{3,1}\ge0$, we obtain

\begin{align}
\Tr T_1 &= A_{1,1} - A_{2,1} - A_{3,1} + A_{4,1} \\
&\leq  A_{1,1}  + \lrabs{A_{2,1}} + A_{4,1}  \\
&\leq  \frac{k-1}{12} \psi(N) + \frac{7}{6} 2^{\omega(N)} + 1 \\
&\leq  \frac{k-1}{12} \psi(N) + \frac{7}{6} \psi(N)(k-1) + \psi(N)(k-1) \\
&=  \frac94 \cdot \psi(N) (k-1) ,
\end{align}

which yields

\begin{align}
\frac{\Tr T_1}{(k-1)\psi(N)^2}
\leq \frac{9}{4\psi(N)}
\leq \frac{9}{4N},
\end{align}

completing the proof.

We are now ready to prove Theorem <ref>.

Suppose that $\gcd(N,4)=1$ and that $k \geq 2$ is even.
Then  $a_2(4,N,k)$ is negative or zero only for the pairs $(N,k)$ given in <cit.>.

Assume that the condition $\frac{k-1}{48} \geq 7 \theta_3(N) + \frac14 \theta_1(N)$ from Lemma <ref> is satisfied. Then by (<ref>) and Lemma <ref>,

\begin{align}
&\ \ \ \  a_2(4,N,k)\\
&= \frac{1}{2} \lrb{ (\Tr T_4)^2 - \Tr T_{16} - 2^{k-1} \Tr T_4 - 4^{k-1} \Tr T_1 } \\
&= \frac{(k-1)4^k \psi(N)^2}{2}
\lrb{
\frac{(\Tr T_4)^2}{ (k-1)4^k \psi(N)^2 }
\frac{\Tr T_{16}}{ (k-1)4^k \psi(N)^2 } -
\frac12 \frac{\Tr T_4}{(k-1)2^k \psi(N)^2}
\frac14 \frac{\Tr T_1}{ (k-1) \psi(N)^2}
} \\
&\geq \frac{(k-1)4^k \psi(N)^2}{2} \Bigg[
\frac{k-1}{2304} - \frac{7}{24} \theta_3(N) - \frac{1}{96} \theta_1(N)
\frac{\Tr T_{16}}{ (k-1)4^k \psi(N)^2 } \\
& \qquad\qquad\qquad\qquad\qquad\qquad
\frac12 \frac{\Tr T_4}{(k-1)2^k \psi(N)^2}
\frac14 \frac{\Tr T_1}{ (k-1) \psi(N)^2} \Bigg] \\
&= \frac{(k-1)4^k \psi(N)^2}{2} \lrb{ \frac{k-1}{2304} - E(N,k) },
\label{eqn:a2-4-final-eqn}
\end{align}

where $E(N,k)$ denotes the five error terms above. In particular, from Lemmas <ref>, <ref>, and <ref>,

\begin{align}
E(N,k) &=
\frac{7}{24} \theta_3(N)
+ \frac{1}{96} \theta_1(N)
+ \frac{\Tr T_{16}}{ (k-1)4^k \psi(N)^2 }
+ \frac12 \frac{\Tr T_4}{(k-1)2^k \psi(N)^2}
+ \frac14 \frac{\Tr T_1}{ (k-1) \psi(N)^2} \\
\frac{7}{24} \theta_3(N)
+ \frac{1}{96} \theta_1(N)
+ \frac{4309}{192N}
+ \frac12 \cdot \frac{385}{48N}
+ \frac14 \cdot \frac{9}{4N} \\
&= \frac{7}{24} \theta_3(N)
+ \frac{1}{96} \theta_1(N)
+ \frac{1729}{64N}.
\end{align}

For $N \geq 2,\!700,\!000$, we have the bounds  $\theta_1(N) \leq 0.0265$ and $\theta_3(N) \leq 0.000015$ given in Lemma <ref>. Note for such $N$, the condition $\frac{k-1}{48} \geq 7 \theta_3(N) + \frac14 \theta_1(N)$ from Lemma <ref> is satisfied for all $k \geq 2$.

\begin{align}
E(N,k) &\leq \frac{7}{24} \cdot 0.000015
+ \frac{1}{96} \cdot 0.0265
+ \frac{1729}{64 \cdot 2,\!700,\!000}  \\
&\leq 0.000291,
\end{align}

which is $< \frac{k-1}{2304}$ for all $k \geq 2$. By (<ref>), this shows that $a_2(4,N,k) > 0$ for $N \geq 2,\!700,\!000$ and $k \geq 2$.

Utilizing the table in Lemma <ref>, an identical argument using $150,\!000$, $8,\!800$, $571$, $43$, and $1$ as the bounds for $N$, shows that $a_2(4,N,k) > 0$ for $N \geq 150,\!000, k \geq 4$; $N \geq 8,\!800,\ k \geq 14$; $N \geq 571, k \geq 124$; $N \geq 43, k \geq 1498$; and $N \geq 1, k \geq 62942$.

We then check the finite number of cases left by computer, which yields the complete list given in <cit.>. (The table contains $164$ pairs, and was too large to include here.)  See <cit.> for the code.

Now, the same methods here would also work for the perfect square case of $m=1$. But this would just be proving a result that is already known. $T_1(N,k)$ is just the identity operator, so $a_2(1,N,k)$ will be positive precisely for the pairs $(N,k)$ for which $\dim S_k(\Gamma_0(N)) \geq 2$. And the complete list of pairs $(N,k)$ where $\dim S_k(\Gamma_0(N)) = 0 \text{ or }1$, was already computed in <cit.>

§ DISCUSSION

We first make some observations about the proofs of Propositions <ref> and <ref>. One of the last steps in these two proofs was to show that for any given $(m,N,\chi)$, the $a_2$ coefficient is nonvanishing for sufficiently large $k$. It is worth noting that is also what one would expect from the well-known Skolem-Mahler-Lech theorem <cit.>. For any fixed $(m,N,\chi)$, $\Tr T_m(N,k,\chi)$ satisfies a linear recurrence in $k$; this fact follows from the Eichler-Selberg trace formula (<ref>). So by Lemma <ref>, $a_2(m,N,k,\chi)$ also satisfies a linear recurrence in $k$. Thus by Skolem-Mahler-Lech, one would expect that for any given $(m,N,\chi)$, $a_2(m,N,k,\chi)$ only vanishes for finitely many $k$.

Now, one might ask if the same result holds including $m$ as well, i.e. if $a_2(m,N,k,\chi)$ only vanishes for finitely many $(m,N,k,\chi)$. It turns out this is not true for a trivial reason. When $\dim S_k(\Gamma_0(N),\chi) < 2$, the characteristic polynomial for $T_m(N,k,\chi)$ will have degree less than $2$. Thus the second coefficient will neccessarily be $0$ for all $m$ in this case.

So one might instead ask if $a_2(m,N,k,\chi)$ vanishes only for finitely many $(m,N,k,\chi)$ when we restrict to the case of $\dim S_k(\Gamma_0(N),\chi) \geq 2$. It turns out this is not true either. For example, $S_2(\Gamma_0(23))$ has dimension $2$. And the two Hecke eigenforms for $S_2(\Gamma_0(23))$ both happen to have $43$rd Fourier coefficient vanish <cit.>. Thus for any $m$ with exactly one factor of $43$, these two eigenforms will both have $m$-th Fourier coefficient vanish. So for such $m$, $T_{m}(23,2)$ will have two eigenvalues of $0$, and hence will have characteristic polynomial $x^2$. This gives an infinite family of vanishing $a_2$ coefficients.

One could also ask if the result still holds if we allow $N$ not coprime to $m$. In fact, this appears to not be true either. For example, it appears that for $j \geq 2$, all the eigenvalues of $T_3(3^j,4)$ vanish. This would give an infinite family of $N$ for which $a_2(3,N,4)$ vanishes. One can find many other similar examples.

Next, we make some remarks about Table <ref>, Table <ref>, and <cit.>.
In principle, one could run the same computations for general character $\chi$ and calculate the finitely many triples $(N,k,\chi)$ for which $a_2(m,N,k,\chi)$ vanishes.
However, the number of $(N,k,\chi)$ to check makes this computationally infeasible.
Even with only considering trivial character, we used the Clemson University PALMETTO cluster, and it took several hours to check all the possible pairs $(N,k)$.

Additionally, observe that many of the entries in these three tables come from $(N,k)$ for which $\dim S_k(\Gamma_0(N))$ is $0$ or $1$ (so the $a_2$ coefficient trivially vanishes).
For $m=2$, $32$ out of $35$ entries in Table <ref> come from $(N,k)$ for which $\dim S_k(\Gamma_0(N)) = 0 \text{ or }1$. All of the remaining $3$ nontrivial entries have $a_2$ coefficient vanish.
For $m=3$, $38$ out of $52$ entries in Table <ref> come from $(N,k)$ for which $\dim S_k(\Gamma_0(N)) = 0 \text{ or }1$. Of the remaining $14$ nontrivial entries, $7$ have positive $a_2$ coefficient and $7$ have vanishing $a_2$ coefficient.
For $m=4$, $32$ out of $164$ entries in <cit.> come from $(N,k)$ for which $\dim S_k(\Gamma_0(N)) = 0 \text{ or }1$. Of the remaining $132$ nontrivial entries, $129$ have negative $a_2$ coefficient and $3$ have vanishing $a_2$ coefficient.

Looking at the $(N,k)$ given in these three tables, one might ask if $a_2(m,N,k)$ is non-trivially vanishing (i.e. is vanishing when $\dim S_k(\Gamma_0(N)) \geq 2$) only for $k = 2$. In fact, this is not true: for $m=7, N=12, k=4$, $a_2(7,12,4) = 0$. However this is the only counter-example that we could find, and we speculate that it is the only such counter-example.

One might also ask if the $a_2$ coefficient never non-trivially vanishes in the level one case. In fact, a more general result was conjectured in <cit.>.

Let $m \geq 1$, $k \geq 2$ be even, and $n = \dim S_k(\Gamma_0(1))$.
Write the characteristic polynomial for $T_m(1,k)$ as

$$T_m(1,k)(x) = x^n - a_1(m,1,k) x^{n-1} + a_2(m,1,k) x^{n-2} - \ldots + (-1)^n a_n(m,1,k).$$

Then $a_i(m,1,k) \neq 0$ for $1 \leq i \leq n$.