# CLIcK: A Benchmark Dataset of Cultural and Linguistic Intelligence in Korean

###### Abstract

Despite the rapid development of large language models (LLMs) for the Korean
language, there remains an obvious lack of benchmark datasets that test the
requisite Korean cultural and linguistic knowledge. Because many existing
Korean benchmark datasets are derived from the English counterparts through
translation, they often overlook the different cultural contexts. For the few
benchmark datasets that are sourced from Korean data capturing cultural
knowledge, only narrow tasks such as bias and hate speech detection are
offered. To address this gap, we introduce a benchmark of Cultural and
Linguistic Intelligence in Korean (CLIcK), a dataset comprising 1,995 QA
pairs. CLIcK sources its data from official Korean exams and textbooks,
partitioning the questions into eleven categories under the two main
categories of language and culture. For each instance in CLIcK, we provide
fine-grained annotation of which cultural and linguistic knowledge is required
to answer the question correctly. Using CLIcK, we test 13 language models to
assess their performance. Our evaluation uncovers insights into their
performances across the categories, as well as the diverse factors affecting
their comprehension. CLIcK offers the first large-scale comprehensive Korean-
centric analysis of LLMs’ proficiency in Korean culture and language. CLIcK is
publicly available at: https://github.com/rladmstn1714/CLIcK.

Keywords: Evaluation, Benchmark, Korean, Culture

CLIcK: A Benchmark Dataset of Cultural and Linguistic Intelligence in Korean

Eunsu Kim⋄, Juyoung Suk†, Philhoon Oh†, Haneul Yoo⋄, James Thorne†, Alice Oh⋄
---
⋄School of Computing, KAIST, Dajeon, South Korea
†GSAI, KAIST, Seoul, South Korea
{kes0317, scottsuk0306, philhoonoh, haneul.yoo<EMAIL_ADDRESS>,
<EMAIL_ADDRESS>

Abstract content

## 1\. Introduction

Recent advancements in Large Language Models (LLMs) have been significant,
particularly for a small group of high-resource languages including English.
In these languages, LLMs frequently attain or surpass human-level proficiency
in numerous Natural Language Processing (NLP) tasks that necessitate
comprehension of everyday life and the subtleties of linguistic nuances.
However, despite a concerted effort in developing Korean large-scale language
models, there remains a significant performance gap for benchmark tasks in the
Korean language. For example, KoGPT3-39B underperforms on the Korean HellaSwag
task Jang et al. (2022) by 20%, compared to similar scale English Falcon40B
model Almazrouei et al. (2023) in the original English version of the task
Zellers et al. (2019) even though human annotators can attain the same
performance. Instances that contain cultural and linguistic knowledge that
deviate from English and other well-represented languages are often
incorrectly answered by models.

Figure 1: Overview of the CLIcK dataset curation and categorization process.
Data is sourced from official exams and textbooks and validated by authors.
The dataset is categorized into Korean Culture and Korean Language, further
divided into 11 sub-categories.

Current Korean evaluation datasets for LLMs show significant limitations for
comprehensive assessment. Existing tasks are either too simple Ham et al.
(2020a); Park et al. (2021) or mainly derived from English benchmarks
111https://huggingface.co/spaces/upstage/open-ko-llm-leaderboard, failing to
capture the key aspects of the Korean language or culture. While several
Korean-centric datasets have been introduced, these typically target specific
tasks such as bias and hate speech detection Jin et al. (2023); Jeong et al.
(2022) and hence cannot support general LLM evaluation.

To bridge this resource gap, we construct and release CLIcK, a culturally-
aware evaluation benchmark dataset encompassing 1,995 instances across 11
categories representing facets of the Korean culture, ranging from everyday
life to specific subject areas, as well as Korean grammar and linguistics. To
ensure high quality, we collect and curate all samples from official
examinations and textbooks, which are then rigorously inspected and
categorized by four native speakers of Korean.

We subsequently evaluate five families of open-source LLMs with different
parameter sizes and two proprietary LLMs with CLIcK. The open-source models
exhibit especially low accuracies, ranging between 10% and 50%. Meanwhile,
proprietary LLMs like GPT-3.5 and Claude-2 outperform these but still perform
poorly in some categories. Notably, compared to the general population of
Korean test-takers, GPT-3.5 scores in the lowest 11th percentile, which
contrasts with its achievement in the top 13th percentile on the English
Scholastic Aptitude Test (SAT).

The primary contributions of our work include:

  * •

We construct and publicly release CLIcK, a benchmark dataset to evaluate LLMs’
cultural and linguistic understanding of Korean.

  * •

We provide a fine-grained categorization of the requisite knowledge to answer
each query in the dataset.

  * •

We empirically evaluate 13 model configurations on CLIcK, demonstrating the
limitations of LLMs and motivating further research on cultural and linguistic
benchmarks.

## 2\. Related Work

### 2.1. General English Benchmarks

The General Language Understanding Evaluation (GLUE) and SuperGLUE benchmarks
were established to evaluate models in a wide range of tasks such as sentiment
analysis, natural language inference, and question-answering Wang et al.
(2018, 2020). HellaSwag Zellers et al. (2019) and CosmoQA Huang et al. (2019)
further include commonsense reasoning for a more robust evaluation. However,
due to the rapid advancement in AI communities, achieving human-level state-
of-the-art performances on these datasets has become increasingly common
Martínez-Plumed et al. (2021). To properly evaluate the capabilities of models
in the era of LLMs, more challenging benchmarks have been introduced. For
example, MMLU Hendrycks et al. (2021) and AGIEval Zhong et al. (2023) consist
of questions originally designed for humans, while BIG-bench Srivastava et al.
(2023) aims to cover diverse topics, comprising 204 tasks to address the
limitations in LLMs.

### 2.2. Multilingual and Commonsense

To investigate how LMs can comprehend or generate text in other languages,
there have been efforts to construct multilingual datasets. For instance,
XGLUE Liang et al. (2020) encompasses 100 languages that can be employed for
both pre-training and evaluating cross-lingual tasks. XTREME Hu et al. (2020)
introduces an evaluation framework for cross-lingual benchmarks, while MEGA
Ahuja et al. (2023) focuses on assessing LLMs, providing 16 NLP datasets
ranging from low-resource to high-resource languages. In addition, datasets
that primarily focus on specific target languages, such as Chinese, Indian,
and African languages, have been introduced Huang et al. (2023); Doddapaneni
et al. (2023); Adebara et al. (2023).

The popularity of commonsense datasets has increased because they reflect a
wide array of sociocultural knowledge shared by humans Liu and Singh (2004).
These datasets incorporate everyday concepts, such as CommonsenseQA Talmor et
al. (2019), scientific knowledge like ARC Clark et al. (2018), and simple
arithmetic reasoning like GSM8KCobbe et al. (2021). These datasets can be seen
as a representation of general and practical knowledge that aligns with human
intentions. Consequently, certain datasets incorporate or employ translated
portions from English datasets Seo et al. (2022), potentially overlooking
subtle linguistic or cultural differences that may not be apparent to the
audience Tandon et al. (2018).

Lee et al. 2023a demonstrated that language models fail to capture biases in
different languages due to their cultural insensitivity, which can have
societal impacts Tamkin et al. (2021). Furthermore, Ma et al. 2022 emphasized
the importance of cultural background and showed that integrating cultural
knowledge can improve models performance. These findings illustrate the need
for cultural evaluation datasets. However, building a cultural evaluation
dataset from scratch is challenging since it entails significant time and
resources while relying on translated datasets fails to incorporate cultural
knowledge in different languages.

### 2.3. Korean Datasets

Previous benchmarks for Korean language models focused on specific tasks such
as paraphrase detection, natural language inference (NLI), machine reading
comprehension (MRC), and hate speech detection Yang et al. (2019); Ham et al.
(2020b); Lim et al. (2019); Moon et al. (2020). The Korean Language
Understanding Evaluation (KLUE) benchmark (Park et al., 2021), similar to
GLUE, introduced eight downstream tasks for the Korean language. However,
these benchmarks lacked tasks for advanced reasoning, which is inadequate for
LLM evaluation. Recently published Open Ko-LLM LeaderBoard 1 aimed to address
this issue; however, its closed-source nature and reliance on translations may
not fully represent the nuances of the Korean language context.

Contemporary benchmarks prioritize preserving linguistic and cultural nuances
of the target language in translation. For instance, Jin et al. (2023)
introduced the Korean Bias Benchmark for Question Answering (KoBBQ) based on
the original BBQ dataset (Parrish et al., 2022). KoBBQ first classified the
translations into 3 distinct categories: Simply-Translated, where translations
are appropriate for the Korean knowledge, Sample-Removed where translated
sentences are removed due to their lack of relevance to Korean cultural
context, and Target-Modified where target translations are adjusted to align
with Korean culture background. This classification adjusts knowledge
differences available in languages and reflects subtle cultural nuances in
Korean.

Recent efforts have revolved around creating authentic Korean datasets from
scratch. For instance, the Korean Offensive Language Dataset Jeong et al.
(2022) gathers toxic sentences from news articles and YouTube platforms, while
the Korean Balanced Evaluation of Significant Tasks Jang et al. (2022) is
entirely annotated by humans for five distinct tasks. The HAE-RAE Benchmark
Son et al. (2023) provides Korean Reading Comprehension datasets sourced from
the original Korean Corpus. However, these datasets are constrained to
specific tasks and may not be suitable for evaluating diverse topics related
to Korean cultural and linguistic knowledge. With the rapid growth of the
language model’s capacity, there is a growing need for fine-grained evaluation
to assess the cultural and commonsense knowledge within LLMs Ye et al. (2023).

In this paper, we introduce CLIcK comprising 1,995 questions that require a
wide range of Korean linguistic and cultural knowledge along with reasoning
capacity, which is close to real-world settings. Additionally, it directly
sources content from the original Korean Corpus, including six different
Korean native exams, ensuring cultural authenticity and facilitating
comparisons between models and human-level scores. Lastly, CLIcK provides
fine-grained evaluations of LLMs on eleven diverse topics, thereby
contributing to further research on the assessment of Korean cultural and
linguistic knowledge within LLMs.

## 3\. CLIcK Dataset

CLIcK contains 1,995 QA pairs, organized into two main categories and 11
subcategories of multiple-choice QA about Korean facts. Dataset statistics are
reported in Tables 1 and 2. The dataset is constructed in three stages: (1)
Data Collection(§ 3.1), (2) Data Validation(§ 3.2), and (3) Data
Categorization(§ 3.3), summarized in Figure 1.

Category | # of Samples
---|---
Textbook | Exams | Total
Korean Culture | Society | 284 | 25 | 309
Tradition | 161 | 61 | 222
History | 0 | 280 | 280
Law | 51 | 168 | 219
Politics | 79 | 5 | 84
Economy | 57 | 2 | 59
Geography | 39 | 92 | 131
Pop culture | 15 | 26 | 41
Korean Language | Textual | 0 | 285 | 285
Functional | 0 | 133 | 133
Grammar | 0 | 232 | 232
| Total | 1245 | 750 | 1995

Table 1: Statistics of CLIcK per categories. ‘From Textbook’ denotes data from
the KIIP textbook; ‘From Exams’ refers to data from official exams. ‘Number of
samples’ indicates unique QA pairs in the dataset.

Code | Subject | # of Samples
---|---|---
CSAT | Language | 226
| Geography | 30
TOPIK | Language | 237
PSE | Language | 14
| History | 189
PSAT | Constitution | 168
KHB | History | 47
Kedu | Language | 173
| Culture | 161

Table 2: Statistics of CLIcK per Exams. Code and Subject refer to the exam’s
codes and its utilized subjects.

### 3.1. Data Collection

To collect data, we employ two approaches: 1) following the AGIEval dataset
Zhong et al. (2023) to select questions from standardized Korean exams, and 2)
using GPT-4 to generate new questions based on textbooks. In this process, we
utilize six exams and one textbook related to Korean language and cultural
knowledge as sources (the genres of these resources are summarized in Table
3).

#### Selecting Questions from Exams

We obtain test data from six Korean examinations and receive permission from
the relevant institutions. Descriptions for each examination can be found in
Appendix A. We use Clova OCR222https://clova.ai/ocr/ to extract text from the
exams, excluding images and tables.

#### Generating Questions Using GPT-4

We use this approach to introduce novel cultural questions, which are not
covered in the exams. Building on established practices in question generation
(Zhou et al., 2017; Kurdi et al., 2019), we feed GPT-4 the full text of each
chapter from the KIIP textbook, prompting it to produce multiple-choice
questions, their corresponding choices and answers based strictly on the
book’s content. Each question was verified before inclusion in the dataset.
More detailed information on GPT-4 question generation, including used prompts
and procedures, can be found in Appendix B.

Source | Code | Type | Subject
---|---|---|---
| Korean Immigration
---
and Integration Program
KIIP | Textbook | Culture
| College Scholastic
---
Ability Test of Korea
CSAT | Exam |  | Language
---
Geography
| Test of Proficiency
---
in Korean
TOPIK | Exam | Language
| National Public Service
---
Examination - Grade 9
PSE | Exam |  | Language
---
History
Public Service Aptitude Test | PSAT | Exam | Constitution
Korean History Exam-Basic | KHB | Exam | History
| Test of Teaching Korean
---
as a Foreign Language
Kedu | Exam |  | Language
---
Culture

Table 3: Overview of data sources used in the CLIcK dataset, detailing each
source’s code, type (textbook or exam), and covered subjects related to Korean
language and culture.

### 3.2. Data Validation

We scrutinize transcribed exams for OCR errors and validate the GPT-4
generated questions according to the following criteria:  1\. Questions are
solely based on the given text.
2\. Information in Questions remains consistent over time.
3\. Questions should centrally relate to Korea.
4\. Questions should be objective and free from bias. By checking the first
criterion, we ensure that questions originate exclusively from the textbook’s
content, eliminating any influence of GPT-4’s internal knowledge.
Additionally, the fourth criterion helps maintain dataset objectivity by
excluding instances connected to subjective beliefs or biases, like gender,
politics, or international relations.

#### Human Annotation

Four of the authors, who are Korean native speakers, validated to ensure its
relevance and quality. Validation checks are categorized into three types;
valid, needs modification, and invalid, with the following process:

  1. 1.

Initially, three annotators reviewed each sample. If two or more annotators
considered a sample invalid, it was discarded. 15.9% of the data was labeled
invalid by one annotator. Samples that needed modification were revised by one
of the annotators.

  2. 2.

For the remaining invalid and modified samples, a second round of annotation
was conducted by three annotators. After this phase, 3.9% of the initial set
still had discrepancies.

  3. 3.

The four annotators involved in the previous steps discuss the disagreements.
Only samples with unanimous agreement between all four annotators are included
in the dataset.

Following the validation process, the initial dataset, which consisted of
1,985 samples, was reduced to 1,245 samples, accounting for 62.9% of the
original dataset.

### 3.3. Data Categorization

For each instance, we provide fine-grained annotation of which aspects of
Cultural and Linguistic intelligence are required to answer the question.
Summary statistics are presented in Table 1.

#### Cultural Intelligence

We adopt eight subcategories based on the KIIP textbook. The primary chapters
of the KIIP basic textbook encompass Society, Culture, Politics, Economy, Law,
History, and Geography. Within the Culture chapter, there are subsections on
Tradition and Pop Culture. We label each instance with respect to its cultural
knowledge with one of the following labels: Society, Tradition, Pop Culture,
Politics, Economy, Law, History, and Geography.

#### Linguistic Intelligence

We follow definitions of linguistic knowledge from Bachman and Palmer (1996).
Specifically, we annotate instances for Textual Knowledge, which concerns
organizing utterances into coherent texts with cohesion and rhetorical
structures; Functional Knowledge, focusing on the communicative roles of
language, especially ideational, manipulative, heuristic, and imaginative
functions; and Grammatical Knowledge, addressing the organization of
utterances with an emphasis on vocabulary, syntax, and phonology/graphology.
We exclude the socio-linguistic knowledge category in our work because it is
largely subsumed by our annotations in the Cultural Intelligence category.

#### Specific Procedures

Because questions generated from the textbook already align to Cultural
Intelligence categories, we do not require further annotation for these
instances. Similarly, for exams that focus on a single subject (e.g. History),
no additional categorization is performed. For the CSAT-Korean exam, problems
are categorized into speaking, writing, language, media, literature, and
reading. In terms of our defined categories, speaking and writing correspond
to Functional knowledge, language aligns with Grammar knowledge, and both
literature and reading are associated with Textual knowledge. Other Korean
Language exams offer solutions detailing the problem’s category. Based on this
information, a single annotator validates the label assignment.

## 4\. Evaluation

We evaluate the capabilities of established language models using our CLIcK
dataset. We compare a range of models which have a variety of exposure to the
Korean language (detailed in Table 4). For API-based LLMs, we conduct
experiments between September and October of 2023.

#### Prompt Types

Our prompts are derived from Jin et al. (2023). Following Izacard et al.
(2023), we apply cyclic permutation for each question to mitigate option’s
order effects in the prompt to the language model. We report the average over
three different wordings of the prompt. Depending on whether the question
requires the model to read background information, we prompt the model with
context (type 1) or without context (type 2) according to the examples which
are provided below.

Type | Model
---|---
| API-based
---
LLMs
| GPT-3.5-turbo, Claude-2
---
Open-source LMs | Multilingual | Korean-specialized
| LLaMA2-chat
---
(7B,13B)
| LLaMA2-Ko(7B)333
---
KULLM-v2 (Lee et al., 2023b)
KoAlpaca444
Polyglot-Ko (Ko et al., 2023)
(1.3B,3.8B,5.8B,12.8B)

Table 4: Model Selection for Our Experiment. The numbers in parentheses
indicate the parameters for models.

https://huggingface.co/beomi/llama-2-ko-7b

https://github.com/Beomi/KoAlpaca

Type 1: Sample with Context
주어진 맥락을 천천히 읽고, 질문에 대한 적절한 정답을 A, B, C, D 중에 골라 알파벳 하나로 답하시오.
(Read the given context, and choose the correct answer to the question from
options A, B, C, or D. Respond with a single alphabet.)

맥락 (Context): {CONTEXT}
질문 (Question): {QUESTION}
보기 (Options):
A: {A}, B: {B}, C: {C}, D: {D}
정답 (Answer): Type 2: Sample without Context
주어진 질문을 천천히 읽고, 적절한 정답을 A, B, C, D 중에 골라 알파벳 하나로 답하시오.
(Read the given Question, and choose the correct answer from options A, B, C,
or D. Respond with a single alphabet.)

질문 (Question): {QUESTION}
보기 (Options):
A: {A}, B: {B}, C: {C}, D: {D}
정답 (Answer):

#### Evaluation Methodology

We adopt the evaluation methodology from MMLU, which also aligns with
prevalent LLM evaluation frameworks such as EleutherAI lm-harness
555https://github.com/EleutherAI/lm-evaluation-harness and OpenAI Evals
666https://github.com/openai/evals. For open-source models, we examine the
output probabilities of option ID tokens (A/B/C/D or A/B/C/D/E) concatenated
with the option string, selecting the most probable answer as the model
prediction. For API-based LLMs (GPT-3.5-turbo and Claude-2), the evaluation
involves comparing the generated response with the labeled answer. Here, the
decoding temperature is set to 0. Though our prompt directly asks the model to
output only the option ID, we notice that these models may at times produce
verbose responses. Therefore, we adopt the acceptance criteria from Jin et al.
(2023), allowing answers that: i) mention only one alphabet from the given
options, ii) exactly match a term provided in the options, iii) include
specific expressions clearly intended to convey the answer, such as ‘the
answer is -’, or iv) present the answer distinctly as per conditions i) to
iii), followed by further explanation. Responses that don’t meet these
conditions are considered as out-of-option answers.

| Polyglot-Ko | KULLM | KoAlpaca | LLaMA-Ko | LLaMA | GPT-3.5 | Claude2
---|---|---|---|---|---|---|---
1.3B | 3.8B | 5.8B | 12.8B | 5.8B | 12.8B | 5.8B | 12.8B | 7B | 7B | 13B
Korean Culture | History | 26.30 | 24.71 | 25.52 | 24.43 | 26.48 | 25.07 | 26.05 | 25.84 | 26.38 | 30.75 | 30.73 | 31.32 | 35.00
Geography | 30.18 | 28.72 | 29.06 | 30.12 | 27.21 | 28.66 | 28.53 | 30.01 | 33.21 | 23.10 | 25.20 | 45.42 | 43.30
Law | 38.44 | 40.16 | 40.70 | 43.44 | 41.67 | 41.90 | 40.67 | 40.13 | 40.02 | 45.13 | 44.12 | 55.31 | 57.09
Politics | 30.53 | 32.00 | 27.74 | 27.15 | 26.96 | 22.68 | 23.42 | 28.79 | 36.03 | 27.31 | 26.43 | 47.75 | 60.89
Society | 34.69 | 34.31 | 35.95 | 37.37 | 35.95 | 37.37 | 33.33 | 36.44 | 32.10 | 39.48 | 40.93 | 60.48 | 62.43
Tradition | 32.48 | 34.01 | 34.97 | 33.96 | 35.86 | 34.63 | 32.80 | 35.45 | 33.60 | 33.88 | 36.12 | 50.16 | 52.10
Economy | 42.54 | 42.62 | 42.25 | 45.03 | 43.86 | 44.08 | 43.35 | 43.79 | 45.32 | 45.83 | 46.27 | 47.59 | 53.62
Pop culture | 29.77 | 33.68 | 32.64 | 29.59 | 33.60 | 32.76 | 34.02 | 32.63 | 27.20 | 33.45 | 36.41 | 68.61 | 59.56
Average | 32.71 | 32.90 | 33.14 | 33.40 | 33.79 | 33.51 | 32.33 | 33.80 | 33.26 | 35.44 | 36.22 | 49.30 | 51.72
Korean Language | Textual | 23.44 | 23.57 | 23.27 | 22.96 | 24.52 | 24.65 | 23.07 | 24.19 | 26.75 | 24.73 | 24.29 | 53.19 | 55.86
Functional | 23.77 | 21.67 | 22.64 | 19.84 | 20.06 | 19.38 | 24.76 | 20.50 | 26.31 | 27.04 | 30.50 | 32.62 | 32.88
Grammar | 21.87 | 21.79 | 23.64 | 23.05 | 24.69 | 25.67 | 24.03 | 22.05 | 23.04 | 29.32 | 26.52 | 38.85 | 43.95
Average | 22.88 | 22.38 | 23.27 | 22.24 | 23.50 | 23.78 | 23.87 | 22.42 | 25.69 | 27.17 | 26.71 | 42.32 | 45.39

Table 5: Accuracy of the models by category. The highest accuracy for each
category is in bold. The top-performing open-source models are marked in blue.

#### Evaluation Metric

Our primary evaluation metric is accuracy. We report the average accuracy over
the entire dataset. As we prompt the model 3 times and adopt cyclic
permutation for each instance, the total number of experiments per instance is
$3N$, where $N$ denotes the “number of options”. Instance accuracy is computed
as:

$p_{\text{accuracy}}=\frac{\text{count}(\text{correct answers})}{3N}$ (1)

### 4.1. Experimental Results

We present comprehensive results of evaluating 13 LLMs with CLIcK in Table 5.
We find that open-source models with fewer than 13B parameters generally
exhibit a low accuracy in the range of 10-50%. While Claude-2 and GPT-3.5
surpass those smaller models in most categories, their performance remains
similar in History, Economy, and Functional Knowledge. Claude-2 outperforms
GPT-3.5 in all categories except Geography and Pop Culture.

Factor | F | p
---|---|---
Model Scale | 0.33 | .57
Korean corpus | 0.30 | .59
Table 6: Results from the ANOVA Test considering two factors. The columns ‘F’
and ‘p’ represent the F-value and p-value, respectively. ‘Korean corpus’
refers to the supplemental Korean dataset used during training.

#### Model Scale

We use the ANOVA test on Polyglot-Ko, KULLM, KoAlpaca, LLaMA models to assess
sensitivity to number of parameters. Test statistics are reported in Table 6.
We find that model scale does not have a statistically significant impact on
accuracy ($F_{1,43}=0.33,p=.57$).

#### Korean Corpus Scale

While the KULLM and KoAlpaca models are fine-tuned with additional Korean
corpora based on the Polyglot-Ko models, and the LLaMa-Ko model is a Korean-
specialized version of LLaMA, our findings in Table 6 suggest that additional
training on Korean datasets doesn’t significantly enhance their comprehension
of Korean culture and language($F_{1,54}=0.30,p=.59$). In fact, the accuracy
is even lower than that of their base models. It’s notable that llama-2 chat,
despite deriving only 0.06% of its training data from Korean sources,
outperforms most Korean-specialized models by a small margin.

Our results reveal that despite their extensive pretraining on vast datasets
and large scales, GPT-3.5-turbo and Claude-2 perform similarly to open-source
models in specific categories like History, Economy, and Functional knowledge.
The results and analysis in this section give insights that simply amassing
more data and enlarging the model size (currently common practices in LM) may
not be the optimal solution for enhancing the cultural intelligence of
Language Models in non-English languages.

## 5\. Discussion

### 5.1. Difficulty Analysis

#### Overall Difficulty

To measure the challenging problems within our dataset, we first define the
difficulty by the number of problems with an accuracy below the random
selection threshold ($1/N$), where $N$ denotes the number of choices belonging
to questions. If the accuracy of the models is below this threshold, we mark
it as a challenging problem for a model and vice versa. As depicted in Figure
2, open-source models, such as Polyglot-Ko, KULLM, KoAlpaca, LLaMa2-Ko, and
LLaMa2-chat, have difficulty with over 60% of our dataset, with a shared
difficulty spanning 35.5%. LLMs like GPT-3.5 and Claude-2 face challenges with
over 30%, sharing 12.6% of problems. Only in 0.6% of the data were none of the
models able to find the correct solution. This emphasizes the CLIcK dataset’s
inherent complexity.

Figure 2: Portions of challenging samples encountered by models of varying
sizes. The sky-blue bar represents the shared portion of KULLM, KoAlpaca, and
LLaMa2-chat, while the gray bar corresponds to GPT-3.5 and Claude-2.

#### Qualitative Study

We analyze the tendencies of the models by examining all samples they perform
well on and those they don’t. We observe no discernible trends that are
specific to each category, and observe a wide range of performance across
samples derived from the same category and source, even though they have
similar levels of difficulty. For example, Problem 1 and Problem 2 are
questions from the Korean society category, derived from KIIP textbook, and
both inquire about Korean-specific matters.  Problem 1
질문 (Question): {한국 정부의 주택 정책이 아닌 것은?
(What is not the Korean government’s housing policy?)}
A: {국민임대주택(National rental housing)}
B: {공공임대주택(Public rental housing)}
C: {보금자리주택(Bogeumjari house/Nest house)}
D: {단기경매주택(Short auction house)}
정답 (Answer): {단기경매주택(Short auction house)} Problem 2
질문 (Question): {남편이 아내의 오빠를 어떻게 부르는가?
(How does a husband call his wife’s older brother?)}
A: {처형(Cheohyeong/Sister-in-law)}
B: {처제(Cheoje/Sister-in-law)}
C: {처남(Cheonam/Brother-in-law)}
D: {형님(Hyeongnim/Older brother-in-law)}
정답 (Answer): {형님(Hyeongnim/Older brother-in-law)} Problem 2 asks about the
everyday life of Korean society, whereas problem 1 seeks more professional
information, making problem 1 appear more challenging. However, all 13 models
achieved 100% accuracy on Problem 1, yet none correctly answered Problem 2.
Therefore, 1) there is less alignment between the model’s perceived difficulty
and those by humans, and 2) such cultural and linguistic intelligence contexts
are challenging for the model to comprehend.

#### Why Do Models Struggle?

As mentioned in § 4, we conducted a total of $3N$ experiments for each problem
sample, utilizing three different prompts and through cyclic permutation. The
model’s uncertainty on each sample, calculated using normalized Shannon
entropy Shannon (1948), is defined as follows:

$\text{Uncertainty score}=\text{$-$}\frac{1}{\log
N}{\sum_{i\in\text{options}}p_{i}\log p_{i}}$ $\text{where}\quad
p_{i}=\frac{\text{count}(\text{i})}{3N}$ (2)

and $i$ represents each option.

The score is normalized between 0 and 1, considering varying numbers of total
options. A score nearer to 0 implies high consistency, whereas one near 1
indicates almost random selection. For each model’s challenging problem, as
defined at the beginning of § 5.1, we calculate an uncertainty to analyze the
reasons behind their low accuracy on our dataset.

The plot in Figure 3 illustrates the uncertainty scores of various models.
Smaller models (polyglot 1.3B, 3.8B) tend to randomly select answers without
consistency, and as the size increases (12.8B, 5.8B), they tend to choose
wrong answers consistently. In other words, models are not getting our dataset
wrong because they are unsure of the answer, but they choose specific wrong
answers at a high rate. Upon analyzing GPT-3.5 and Claude-2, we observe an
ambiguous pattern, as their mean and median uncertainty scores both
approximate 0.5.

Figure 3: Box-and-whisker plot of uncertainty score of challenging samples
across the models. ‘x’ marks the mean, and the horizontal bar represents the
median. For Polyglot and LLaMa, consistency rises with increasing model scale.
Polyglot 1.3B has a median near 1, while LLaMa’s median is closer to 0.

### 5.2. Comparisons to Human Level

We compare model accuracy to human performance on exams. Since our dataset
does not encompass the actual score distribution for the problems, a simple
score conversion,the ratio of correctly answered questions, is applied to
facilitate a comparative analysis. We utilize exam statistics from CSAT
Korean, TOPIK and Kedu for Korean Culture to assess the models’ performances
against actual exam takers.

#### CSAT Korean

An average is taken of the statistics spanning from 2017 to 2020, a total of
five years. The CSAT is divided into tiers from 1 (best) to 9 (worst). The
Polyglot-Ko(12.8B), KULLM(5.8B, 12.8B), and KoAlpaca(12B) models performed at
the 9th level, corresponding to the lowest 4% of Korean high school seniors
(3rd-year students). The remaining models are at the 8th grade level,
representing the lowest 11%.

#### TOPIK

TOPIK is evaluated on an absolute scale, with levels ranging from 1 to 6, with
higher being better. Claude-2 achieved a level 6, implying it can perform
language functions required for specialized research or professional tasks
relatively accurately and fluently. While it doesn’t reach the proficiency of
a native speaker, it doesn’t face difficulties in functional performance or
expressing meanings. GPT-3.5 achieved a level 5, indicating it can
appropriately differentiate language use depending on formal and informal, as
well as spoken and written contexts. The other models score too low and fall
outside the measurement range.

#### Kedu for Korean Culture

We analyze data over a five-year, from 2014 to 2018. All model results fall
below the average of participants, which stood at 49.9% correct answers.
Claude-2 and GPT-3.5 are lower than the average by about 10%, scoring 39.1%
and 37.0%, respectively. Meanwhile, other models lagged by more than 20%
compared to the average.

## 6\. Conclusion

We introduced CLIcK, A Benchmark Dataset of Cultural and Linguistic
Intelligence in Korean. CLIcK emerges as a uniquely Korean-centric dataset
sourced from Korean examinations and textbooks. The dataset is categorized
into two main category and 11 sub-categories, which enable fine-grained and
Korean-centric evaluation. Through our analyses and experiments, we observed
that five open-source models struggle with over 60% of the data. Proprietary
LLMs outperform these models yet still require further improvement.
Interestingly, simply scaling up the model or fine-tuning it with additional
Korean corpora doesn’t guarantee enhanced Korean linguistic and cultural
knowledge of models. This implies that models find it challenging to
understand non-English linguistic and cultural intelligence, highlighting the
need for more tailored methods in further research.

## Ethics Statement

This work presents CLIcK dataset, a free and open evaluation benchmark of
cultural and linguistic intelligence in Korean. Our dataset contains multiple-
choice QAs with four or five choices. The data sources are publicly available
exams and published articles from the Korean government, and we receive
official permission from the related agencies. We scrutinize all samples in
the dataset to ensure that no personally identifiable information or sensitive
content is included. Furthermore, we have made our best effort to deliver
Korean culture correctly by 1) generating samples from reliable grounds and 2)
iteratively validating samples.

## Acknowledgements

This project was funded by Institute of Information communications Technology
Planning Evaluation (IITP) grant funded by the Korea government(MSIT) (No.
2022-0-00184, Development and Study of AI Technologies to Inexpensively
Conform to Evolving Policy on Ethics).

## Bibliographical References

##

  * Almazrouei et al. (2023) Ebtesam Almazrouei, Hamza Alobeidli, Abdulaziz Alshamsi, Alessandro Cappelli, Ruxandra Cojocaru, Mérouane Debbah, Étienne Goffinet, Daniel Hesslow, Julien Launay, Quentin Malartic, Daniele Mazzotta, Badreddine Noune, Baptiste Pannier, and Guilherme Penedo. 2023.  The falcon series of open language models.
  * Bachman and Palmer (1996) L.F. Bachman and A.S. Palmer. 1996.  _Language Testing in Practice: Designing and Developing Useful Language Tests_.  Language applied linguistic. OUP Oxford.
  * Izacard et al. (2023) Gautier Izacard, Patrick Lewis, Maria Lomeli, Lucas Hosseini, Fabio Petroni, Timo Schick, Jane Dwivedi-Yu, Armand Joulin, Sebastian Riedel, and Edouard Grave. 2023.  Atlas: Few-shot learning with retrieval augmented language models.  _Journal of Machine Learning Research_ , 24(251):1–43.
  * Ko et al. (2023) Hyunwoong Ko, Kichang Yang, Minho Ryu, Taekyoon Choi, Seungmu Yang, Jiwung Hyun, Sungho Park, and Kyubyong Park. 2023.  A technical report for polyglot-ko: Open-source large-scale korean language models.
  * Kurdi et al. (2019) Ghader Kurdi, Jared Leo, Bijan Parsia, Uli Sattler, and Salam Al-Emari. 2019.  A systematic review of automatic question generation for educational purposes.  _International Journal of Artificial Intelligence in Education_ , 30:121–204.
  * Lee et al. (2023a) Nayeon Lee, Chani Jung, and Alice Oh. 2023a.  Hate speech classifiers are culturally insensitive.  In _Proceedings of the First Workshop on Cross-Cultural Considerations in NLP (C3NLP)_ , pages 35–46, Dubrovnik, Croatia. Association for Computational Linguistics.
  * Lee et al. (2023b) SeungJun Lee, Taemin Lee, Jeongwoo Lee, Yoona Jang, and Heuiseok Lim. 2023b.  Kullm: Learning to construct korean instruction-following large language models.  In _Annual Conference on Human and Language Technology_ , pages 196–202. Human and Language Technology.
  * Liu and Singh (2004) Hugo Liu and Push Singh. 2004.  Conceptnet—a practical commonsense reasoning tool-kit.  _BT technology journal_ , 22.
  * Ma et al. (2022) Weicheng Ma, Samiha Datta, Lili Wang, and Soroush Vosoughi. 2022.  EnCBP: A new benchmark dataset for finer-grained cultural background prediction in English.  In _Findings of the Association for Computational Linguistics: ACL 2022_ , pages 2811–2823, Dublin, Ireland. Association for Computational Linguistics.
  * Martínez-Plumed et al. (2021) Fernando Martínez-Plumed, Pablo Barredo, Seán Ó hÉigeartaigh, and José Hernández-Orallo. 2021.  Research community dynamics behind popular ai benchmarks.  _Nature Machine Intelligence_ , 3(7):581–589.
  * Shannon (1948) Claude Elwood Shannon. 1948.  A mathematical theory of communication.  _The Bell System Technical Journal_ , 27:379–423.
  * Tamkin et al. (2021) Alex Tamkin, Miles Brundage, Jack Clark, and Deep Ganguli. 2021.  Understanding the capabilities, limitations, and societal impact of large language models.
  * Tandon et al. (2018) Niket Tandon, Aparna S. Varde, and Gerard de Melo. 2018.  Commonsense knowledge in machine intelligence.  _SIGMOD Rec._ , 46(4):49–52.
  * Ye et al. (2023) Seonghyeon Ye, Doyoung Kim, Sungdong Kim, Hyeonbin Hwang, Seungone Kim, Yongrae Jo, James Thorne, Juho Kim, and Minjoon Seo. 2023.  Flask: Fine-grained language model evaluation based on alignment skill sets.
  * Zhou et al. (2017) Qingyu Zhou, Nan Yang, Furu Wei, Chuanqi Tan, Hangbo Bao, and M. Zhou. 2017.  Neural question generation from text: A preliminary study.  _ArXiv_ , abs/1704.01792.

## Language Resource References

##

  * Adebara et al. (2023) Ife Adebara, AbdelRahim Elmadany, Muhammad Abdul-Mageed, and Alcides Alcoba Inciarte. 2023.  Serengeti: Massively multilingual language models for africa.
  * Ahuja et al. (2023) Kabir Ahuja, Harshita Diddee, Rishav Hada, Millicent Ochieng, Krithika Ramesh, Prachi Jain, Akshay Nambi, Tanuja Ganu, Sameer Segal, Maxamed Axmed, Kalika Bali, and Sunayana Sitaram. 2023.  Mega: Multilingual evaluation of generative ai.
  * Clark et al. (2018) Peter Clark, Isaac Cowhey, Oren Etzioni, Tushar Khot, Ashish Sabharwal, Carissa Schoenick, and Oyvind Tafjord. 2018.  Think you have solved question answering? try arc, the ai2 reasoning challenge.
  * Cobbe et al. (2021) Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. 2021.  Training verifiers to solve math word problems.  _arXiv preprint arXiv:2110.14168_.
  * Doddapaneni et al. (2023) Sumanth Doddapaneni, Rahul Aralikatte, Gowtham Ramesh, Shreya Goyal, Mitesh M. Khapra, Anoop Kunchukuttan, and Pratyush Kumar. 2023.  Towards leaving no indic language behind: Building monolingual corpora, benchmark and models for indic languages.
  * Ham et al. (2020a) Jiyeon Ham, Yo Joong Choe, Kyubyong Park, Ilji Choi, and Hyungjoon Soh. 2020a.  KorNLI and KorSTS: New benchmark datasets for Korean natural language understanding.  In _Findings of the Association for Computational Linguistics: EMNLP 2020_ , pages 422–430, Online. Association for Computational Linguistics.
  * Ham et al. (2020b) Jiyeon Ham, Yo Joong Choe, Kyubyong Park, Ilji Choi, and Hyungjoon Soh. 2020b.  Kornli and korsts: New benchmark datasets for korean natural language understanding.
  * Hendrycks et al. (2021) Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and Jacob Steinhardt. 2021.  Measuring massive multitask language understanding.  In _International Conference on Learning Representations (ICLR)_.
  * Hu et al. (2020) Junjie Hu, Sebastian Ruder, Aditya Siddhant, Graham Neubig, Orhan Firat, and Melvin Johnson. 2020.  Xtreme: A massively multilingual multi-task benchmark for evaluating cross-lingual generalization.
  * Huang et al. (2019) Lifu Huang, Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi. 2019.  Cosmos QA: Machine reading comprehension with contextual commonsense reasoning.  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 2391–2401, Hong Kong, China. Association for Computational Linguistics.
  * Huang et al. (2023) Yuzhen Huang, Yuzhuo Bai, Zhihao Zhu, Junlei Zhang, Jinghan Zhang, Tangjun Su, Junteng Liu, Chuancheng Lv, Yikai Zhang, Jiayi Lei, Yao Fu, Maosong Sun, and Junxian He. 2023.  C-eval: A multi-level multi-discipline chinese evaluation suite for foundation models.
  * Jang et al. (2022) Myeongjun Jang, Dohyung Kim, Deuk Sin Kwon, and Eric Davis. 2022.  KoBEST: Korean balanced evaluation of significant tasks.  In _Proceedings of the 29th International Conference on Computational Linguistics_ , pages 3697–3708, Gyeongju, Republic of Korea. International Committee on Computational Linguistics.
  * Jeong et al. (2022) Younghoon Jeong, Juhyun Oh, Jongwon Lee, Jaimeen Ahn, Jihyung Moon, Sungjoon Park, and Alice Oh. 2022.  KOLD: Korean offensive language dataset.  In _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing_ , pages 10818–10833, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
  * Jin et al. (2023) Jiho Jin, Jiseon Kim, Nayeon Lee, Haneul Yoo, Alice Oh, and Hwaran Lee. 2023.  Kobbq: Korean bias benchmark for question answering.
  * Liang et al. (2020) Yaobo Liang, Nan Duan, Yeyun Gong, Ning Wu, Fenfei Guo, Weizhen Qi, Ming Gong, Linjun Shou, Daxin Jiang, Guihong Cao, Xiaodong Fan, Ruofei Zhang, Rahul Agrawal, Edward Cui, Sining Wei, Taroon Bharti, Ying Qiao, Jiun-Hung Chen, Winnie Wu, Shuguang Liu, Fan Yang, Daniel Campos, Rangan Majumder, and Ming Zhou. 2020.  XGLUE: A new benchmark dataset for cross-lingual pre-training, understanding and generation.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 6008–6018, Online. Association for Computational Linguistics.
  * Lim et al. (2019) Seungyoung Lim, Myungji Kim, and Jooyoul Lee. 2019.  Korquad1.0: Korean qa dataset for machine reading comprehension.
  * Moon et al. (2020) Jihyung Moon, Won Ik Cho, and Junbum Lee. 2020.  BEEP! Korean corpus of online news comments for toxic speech detection.  In _Proceedings of the Eighth International Workshop on Natural Language Processing for Social Media_ , pages 25–31, Online. Association for Computational Linguistics.
  * Park et al. (2021) Sungjoon Park, Jihyung Moon, Sungdong Kim, Won Ik Cho, Ji Yoon Han, Jangwon Park, Chisung Song, Junseong Kim, Youngsook Song, Taehwan Oh, Joohong Lee, Juhyun Oh, Sungwon Lyu, Younghoon Jeong, Inkwon Lee, Sangwoo Seo, Dongjun Lee, Hyunwoo Kim, Myeonghwa Lee, Seongbo Jang, Seungwon Do, Sunkyoung Kim, Kyungtae Lim, Jongwon Lee, Kyumin Park, Jamin Shin, Seonghyun Kim, Lucy Park, Lucy Park, Alice Oh, Jung-Woo Ha (NAVER AI Lab), and Kyunghyun Cho. 2021.  Klue: Korean language understanding evaluation.  In _Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks_ , volume 1. Curran.
  * Parrish et al. (2022) Alicia Parrish, Angelica Chen, Nikita Nangia, Vishakh Padmakumar, Jason Phang, Jana Thompson, Phu Mon Htut, and Samuel Bowman. 2022.  BBQ: A hand-built bias benchmark for question answering.  In _Findings of the Association for Computational Linguistics: ACL 2022_ , pages 2086–2105, Dublin, Ireland. Association for Computational Linguistics.
  * Seo et al. (2022) Jaehyung Seo, Seounghoon Lee, Chanjun Park, Yoonna Jang, Hyeonseok Moon, Sugyeong Eo, Seonmin Koo, and Heuiseok Lim. 2022.  A dog is passing over the jet? a text-generation dataset for Korean commonsense reasoning and evaluation.  In _Findings of the Association for Computational Linguistics: NAACL 2022_ , pages 2233–2249, Seattle, United States. Association for Computational Linguistics.
  * Son et al. (2023) Guijin Son, Hanwool Lee, Suwan Kim, Huiseo Kim, Jaecheol Lee, Je Won Yeom, Jihyu Jung, Jung Woo Kim, and Songseong Kim. 2023.  Hae-rae bench: Evaluation of korean knowledge in language models.
  * Srivastava et al. (2023) Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam R. Brown, and et al. 2023.  Beyond the imitation game: Quantifying and extrapolating the capabilities of language models.
  * Talmor et al. (2019) Alon Talmor, Jonathan Herzig, Nicholas Lourie, and Jonathan Berant. 2019.  CommonsenseQA: A question answering challenge targeting commonsense knowledge.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4149–4158, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Wang et al. (2020) Alex Wang, Yada Pruksachatkun, Nikita Nangia, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R. Bowman. 2020.  Superglue: A stickier benchmark for general-purpose language understanding systems.
  * Wang et al. (2018) Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel Bowman. 2018.  GLUE: A multi-task benchmark and analysis platform for natural language understanding.  In _Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP_ , pages 353–355, Brussels, Belgium. Association for Computational Linguistics.
  * Yang et al. (2019) Yinfei Yang, Yuan Zhang, Chris Tar, and Jason Baldridge. 2019.  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. Association for Computational Linguistics.
  * Zellers et al. (2019) Rowan Zellers, Ari Holtzman, Yonatan Bisk, Ali Farhadi, and Yejin Choi. 2019.  HellaSwag: Can a machine really finish your sentence? In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 4791–4800, Florence, Italy. Association for Computational Linguistics.
  * Zhong et al. (2023) Wanjun Zhong, Ruixiang Cui, Yiduo Guo, Yaobo Liang, Shuai Lu, Yanlin Wang, Amin Saied, Weizhu Chen, and Nan Duan. 2023.  Agieval: A human-centric benchmark for evaluating foundation models.

## Appendix

##  Appendix A Exam Description

#### College Scholastic Ability Test of Korea (CSAT)

777https://www.suneung.re.kr/

CSAT, endorsed by Korean universities, assesses scholastic aptitude based on
the Korean high school curriculum and is administered annually by the Korean
Ministry of Education.

#### Test of Proficiency in Korean (TOPIK)

888https://www.topik.go.kr/

TOPIK measures and evaluates the proficiency of learners of Korean as a second
language.

#### National Public Service Examination - Grade 9 (PSE)

999https://www.gosi.kr/

PSE evaluates the knowledge and abilities of individuals who wish to work in
the public sector. We use the history section and the language section which
assesses proficiency in grammar, vocabulary, and reading comprehension.

#### Public Service Aptitude Test (PSAT)

9 PSAT assesses the aptitudes essential for performing public duties at a
higher standard than the PSE. Our study focuses on the Korean Constitution
section of the PSAT subjects.

#### Korean History Exam (KHE)

101010https://www.historyexam.go.kr

KHE measures the historical literacy of Korean citizens.

#### Test of Teaching Korean as a Foreign Language (Kedu)

111111https://www.q-net.or.kr

Kedu certifies individuals aspiring to teach Korean to overseas Koreans or
foreigners. It covers both Korean language and culture.

#### The Korean Immigration and Integration Program (KIIP)

121212https://www.immigration.go.kr

KIIP assists foreigners in integrating into Korean society. We use the basic
level KIIP textbook and generate QA pairs using

##  Appendix B Question Generation Using GPT-4

We employed the GPT-4 language model for the generation of multiple-choice
questions, focusing on content extracted from the Korean Integration and
Immigration Program (KIIP) textbooks. The process involved several key steps
to ensure the generation of high-quality, relevant educational questions.

#### Text extraction

We extracted text from the KIIP textbooks to serve as the basis for our
question generation. To manage this extensive textual data effectively, the
extracted text was split into smaller, manageable chunks. This splitting was
accomplished using a RecursiveCharacterTextSplitter from Langchain. The
parameters for this splitter were chosen based on initial experiments to
balance between maintaining textual coherence and ensuring manageable chunk
sizes for processing.

#### Prompt

The core of our question generation process involved prompting GPT-4 with a
specific structure to ensure that the questions generated were diverse,
relevant, and adhered to a specific format. The prompt used for GPT-4 was as
follows:

Original Korean Prompt
---
| 다음 제시문을 읽고 4지 선다 문제 10개를 만들어줘.
---
문제를 만들 때 내용은 겹치지 않게 하고 형식은 다음을 포함한
json 형식으로 만들어줘. question_id는 {current_cnt}부터 시작해서
1부터 증가해줘.
"cite": 제시문에서 문제를 만드는 데 사용한 문장
"question_id": {문제 번호}
"question": {문제}
"choices": {보기}
"answer": {답}
"제시문": {content}

English Translated Prompt
---
| Read the following passage and create 10 multiple-choice
---
questions based on it.
Ensure that the content of each question does not overlap and format
them in JSON format including the following elements.
The question_id should start from {current_cnt} and increase by 1 there-
after.
"cite": The sentence from the passage used to create the question
"question_id": {Question number}
"question": {Question}
"choices": {Options}
"answer": {Answer}
"Passage": {content}

This prompt was designed to instruct GPT-4 to produce a set of 10 multiple-
choice questions for each text chunk, each with a unique question identifier
("question_id"). The format of the prompt ensured that the questions did not
overlap in content and were presented in a structured JSON format. This format
included a citation from the text ("cite"), the question itself ("question"),
multiple choices ("choices"), and the correct answer ("answer"). This citation
was not just for referencing purposes but also served a vital role in the
validation process. It allowed human reviewers to quickly ascertain the
validity of the generated question and to confirm that the provided answer was
indeed correct according to the textbook content.

#### Verification

As a final step in the process, any instances generated by GPT-4 that did not
conform to the specified format were identified and removed.


# A characterization of local nilpotence for dimension two polynomial
derivations

###### Abstract.

Let ${\Bbbk}$ be an algebraically closed field. We prove that a polynomial
${\Bbbk}$-derivation $D$ in two variables is locally nilpotent if and only if
the subgroup of polynomial ${\Bbbk}$-automorphisms which commute with $D$
admits elements whose degree is arbitrary big.

Ivan Pan111Research of I. Pan was partially supported by ANII and PEDECIBA, of
Uruguay.

##  1\. introduction

Let ${\Bbbk}$ be a field of characteristic 0. A well known result of
Rentschler (see [Re1968]) says that a polynomial derivation
$D:{{\Bbbk}[x,y]}\to{{\Bbbk}[x,y]}$ (over ${\Bbbk}$) is locally nilpotent,
i.e. for any polynomial $f$ one has $D^{n}f=0$ for some $n\geq 1$, if and only
if $D$ is conjugate to a derivation of the form $u(x)\partial_{y}$, by means
of a suitable polynomial automorphism $\varphi\in{\rm
Aut_{\Bbbk}({{\Bbbk}[x,y]})}$. If ${\rm Aut}(D)$ denotes the isotropy subgroup
of $D$ with respect to the natural conjugation action of ${\rm
Aut_{\Bbbk}({{\Bbbk}[x,y]})}$ on the set ${\rm Der}_{\Bbbk}({{\Bbbk}[x,y]})$
of ${\Bbbk}$ derivations, we deduce that $D$ being locally nilpotent implies
${\rm Aut}(D)$ is conjugate to a subgroup of the form

$J_{u}=\\{(\alpha x+\beta,\gamma
y+P(x);\alpha,\gamma\in{\Bbbk}^{*},\beta\in{\Bbbk},P\in{\Bbbk}[x],u(\alpha
x+\beta)/u(x)=\gamma\\},$

for some $u\in{\Bbbk}[x]$; here we write $\varphi=(f,g)\in{\rm
Aut_{\Bbbk}({{\Bbbk}[x,y]})}$ to mean $\varphi(x)=f$ and $\varphi(y)=g$.

On the other hand, we consider on ${\rm Aut_{\Bbbk}({{\Bbbk}[x,y]})}$ the so-
called _inductive topology_ defined by the filtration
${\mathbb{A}}_{1}\subset{\mathbb{A}}_{2}\subset\cdots\subset{\mathbb{A}}_{d}\subset\cdots$,
where ${\mathbb{A}}_{d}=\\{(f,g);\deg f,\deg g\leq d\\}$. If ${\Bbbk}$ is
algebraically closed, we see that ${\mathbb{A}}_{i}$ is an affine variety for
any $i$ and the subgroup above is an _infinite dimension algebraic group_ in
the sense of [Sha1981] or [Ka1979]. Following this last reference, we conclude
that ${\rm Aut}(u(x)\partial_{y})$ doesn’t satisfy the property of acting
algebraically on ${{\Bbbk}[x,y]}$ as an (usual) algebraic group. Indeed, as
shown there for a subgroup of ${\rm Aut_{\Bbbk}({{\Bbbk}[x,y]})}$ that
property is equivalent to being closed (which ${\rm Aut}(D)$ does for any
derivation $D$: see [BaPa2019, Cor. 2.2]) and having bounded degree.

The aim of the present note is to prove that that holds true exclusively for
locally nilpotent derivations. More precisely, we have the following
characterization of the local nilpotence property whose proof relies strongly
on the results of [BaPa2019].

######  Theorem 1.1.

Let $D$ be a nonzero derivation of ${\Bbbk}[x,y]$ where ${\Bbbk}$ is a field
algebraically closed of characteristic 0. Then the following assertions are
equivalent:

$(a)$ $D$ is locally nilpotent;

$(b)$ for every $d$ there exists $(f,g)\in{\rm Aut}(D)$ such that $\deg f\geq
d$ or $\deg g\geq d$;

$(c)$ ${\rm Aut}(D)$ is not an algebraic subgroup of ${\rm
Aut}({\Bbbk}[x,y])$;

$(d)$ ${\rm Aut}(D)$ is an infinite dimensional algebraic subgroup of ${\rm
Aut}({\Bbbk}[x,y])$.

Note that whereas $(b)$ and $(c)$ are equivalent and both are a consequence of
$(d)$ the converse is not, _a priori_ , necessarily true because
${\mathbb{Z}}$ is not an algebraic subgroup of ${\Bbbk}$. Moreover, since
conjugating is a homeomorphism which respects the degree’s boundedness, then
from Rentchler’s result we deduce that $(a)$ implies $(d)$. Thus we only need
to prove that $(b)$ implies $(a)$.

Notice also that Theorem 1.1 says that ${\rm Aut}(D)$ is an algebraic group
when $D$ is not locally nilpotent and then one may ask what kind of such a
group corresponds to the conjugation class of a non locally nilpotent
derivation.

Finally, we observe that Theorem 1.1 doesn’t hold true for dimension 3 or
higher (Example 2.4) even though assertion $(b)$ does for any locally
nilpotent derivation $D$ ([BaVe2020, Remark 3]).

######  Remark 1.2.

What we observe here about ${\rm Aut}(D)$ recalls what happens with the
isotropy of another action of ${\rm Aut_{\Bbbk}({{\Bbbk}[x,y]})}$. Indeed, it
makes one think of the natural action of that group on the set of reduced
principal ideals of height 1 (i.e. algebraic plane curves) where the isotropy
of such an ideal $(f)$ is not an algebraic group if and only if its generator
$f\in{{\Bbbk}[x,y]}$ may be transformed into an element in ${\Bbbk}[x]$ by
means of an automorphism (see [BlSt2015] and references therein). In other
words, the ideal generated by such an $f$ would correspond in our research to
a locally nilpotent derivation. Moreover, when $n>2$ the phenomena observed in
Example 2.4 matches the one described in [BlSt2015, Ex. 3.16].

##  2\. The proof

We denote $\rm{\mathbb{e}}(D)$ the number of $D$-stable reduced principal
ideals of height 1. If $(h)$ is such a principal $D$-stable ideal, then
$D(h)=\lambda h$ for some $\lambda\in{{\Bbbk}[x,y]}$ and we say $h$ is a
_eigenvector_ of $D$ and $\lambda$ is its (corresponding) _eigenvalue_. In the
case where $h$ is an eigenvector which is reduced, i.e. square-free, we will
also say that $D$ stabilizes the curve of equation $h=0$. Notice that
$\rm{\mathbb{e}}(D)=0$ implies that the _kernel_ $\ker D$ of $D$ is equal to
${\Bbbk}$.

Two elements $f_{1},f_{2}\in{{\Bbbk}[x,y]}$ are said to be _equivalent_ if
there is $\varphi\in{\rm Aut_{\Bbbk}({{\Bbbk}[x,y]})}$ such that
$\varphi(f_{1})=f_{2}$. In the case where $f_{1}$ is equivalent to $x$ we say
it is _rectifiable_.

We keep all notations introduced in the precedent section. If
$\varphi=(f,g)\in{\rm Aut_{\Bbbk}({{\Bbbk}[x,y]})}$, we denote $\deg\varphi$
the greatest degree of $f$ and $g$ and call it the _degree_ of $\varphi$;
notice that we have a degree function $\deg:{\rm
Aut_{\Bbbk}({{\Bbbk}[x,y]})}\to{\mathbb{N}}$ which verifies
$\deg\varphi\psi\leq\deg\varphi\deg\psi$.

######  Lemma 2.1.

Let $D\in{\rm Der}_{\Bbbk}({{\Bbbk}[x,y]})$ be a nonzero derivation and assume
${\rm Aut}(D)$ to be a non-algebraic group. Then one of the following
assertions holds

$(a)$ $0<\rm{\mathbb{e}}(D)<\infty$, all irreducible eigenvector is
rectifiable and $D$ is conjugate to a derivation of the form
$a\partial_{x}+b\partial_{y}$ where either $ab\neq 0$ and $x\in{{\Bbbk}[x,y]}$
divides $a$ or $a=0$ and $b\in{\Bbbk}[x]$.

$(b)$ $\rm{\mathbb{e}}(D)=\infty$ and $D$ is conjugate to a derivation of the
form $b(x)\partial_{y}$.

$(c)$ $\rm{\mathbb{e}}(D)=\infty$, $\ker(D)={\Bbbk}$ and $D$ stabilizes the
members of a pencil of rational curves.

$(d)$ $\rm{\mathbb{e}}(D)=0$.

###### Proof.

We assume $\rm{\mathbb{e}}(D)\neq 0$ and prove that one of the assertions
$(a),(b)$ or $(c)$ holds.

First suppose $0<\rm{\mathbb{e}}(D)<\infty$. By [BaPa2019, Thm. A] all
irreducible eigenvector is rectifiable. Then there is $\varphi\in{\rm
Aut_{\Bbbk}({{\Bbbk}[x,y]})}$ such that $\varphi
D\varphi^{-1}=a\partial_{x}+b\partial_{y}$ admits $x\in{{\Bbbk}[x,y]}$ as an
eigenvector. Hence $x$ divides $a$. From [BaPa2019, Thm. B] we deduce the
assertion $(a)$ holds in this case.

Next suppose $\rm{\mathbb{e}}(D)=\infty$. If $\ker D\neq{\Bbbk}$, the
references already cited imply we are in the situation of assertion $(b)$.
Analogously, if $\ker D={\Bbbk}$, then [BaPa2019, Thms. D] implies we are as
in assertion $(c)$ which completes the proof. ∎

We consider the compactifications $X={\Bbbk}^{2}\cup B$ of ${\Bbbk}^{2}$,
where $B$ is the union of at most two curves isomorphic to ${\mathbb{P}}^{1}$:
either $X={\mathbb{F}}_{n},n\geq 1$, where ${\mathbb{F}}_{n}$ is the $n^{th}$
Nagata-Hirzebruch surface and $B$ is the union of a fiber and the $(-n)$-curve
in that surface or $X={\mathbb{P}}^{2}$ is the projective plane, with
$B=L_{\infty}$ the line at infinity with respect to the affine chart
${\Bbbk}^{2}$. We denote by ${\rm Aut}(X,B)$ the group of automorphisms of $X$
which leave $B$ invariant.

######  Proposition 2.2.

Let $D\in{\rm Der}_{\Bbbk}({{\Bbbk}[x,y]})$ be a nonzero derivation and assume
${\rm Aut}(D)$ to be a non-algebraic group. If $\rm{\mathbb{e}}(D)\neq 0$,
then $D$ is locally nilpotent.

###### Proof.

By Lemma 2.1 we know $D$ satisfies $(a)$, $(b)$ or $(c)$ therein. Moreover, in
case (b) the assertion is obvious. Let us consider the case (c), and denote
$\Lambda$ a pencil of rational curves whose members are stable under $D$. From
[BaPa2019, Pro. 2.10, Cor. 2.12] we deduce that up to conjugation ${\rm
Aut}(D)$ may be thought of as either a subgroup of ${\rm
Aut}({\mathbb{F}}_{n},B)$, for some $n$, or one of ${\rm
Aut}({\mathbb{P}}^{2},L_{\infty})$, where in the second case $\Lambda$ turns
out to be a pencil composed by lines passing through a point $p\in
L_{\infty}$. Without loss of generality we assume
${\Bbbk}^{2}\subset{\mathbb{P}}^{2}$ via the embedding $(x,y)\mapsto(1:x:y)$,
with $L_{\infty}=(x_{0}=0)$ and $p=(0:0:1)$.

Since ${\rm Aut}({\mathbb{F}}_{n},B)$ is an algebraic group then ${\rm
Aut}(D)$ is necessarily as in the second case, hence ${\rm Aut}(D)$ is
contained in the so-called _de Jonquières Group_

${\rm J({{\Bbbk}[x,y]})}:=\\{(\alpha x+\beta,\gamma
y+P(x);\alpha,\beta\in{\Bbbk}^{*},\gamma\in{\Bbbk},P\in{\Bbbk}[x]\\}.$

Moreover, since a general member of $\Lambda$ corresponds in ${\Bbbk}^{2}$ to
a line of equation $x-\beta=0$, for a general $\beta\in{\Bbbk}$, we conclude
that if $D=a\partial_{x}+b\partial_{y}$, then $x-\beta$ divides
$D(x-\beta)=a$, for any $\beta$. Hence $a=0$ and $D=b(x,y)\partial_{y}$. Thus
the assertion is consequence of [BaPa2019, Thm. B].

Now, assume we are as in the assertion (a) of Lemma 2.1. Up to conjugation we
may assume $D=x^{\ell}a(x,y)\partial_{x}+b(x,y)\partial_{y}$, where we may
suppose $a\neq 0$ and $x$ does not divide $a$ because $a=0$ and
$b\in{\Bbbk}[x]$ leads to the required conclusion.

We have a homomorphism ${\rm Aut}(D)\to{\rm Per(E)}$, where $E$ is the set of
prime principal ideals of ${{\Bbbk}[x,y]}$ which are $D$-stable and ${\rm
Per(E)}$ denotes the finite group of permutations of $E$. Hence the principal
ideal $x{{\Bbbk}[x,y]}$ belongs to $E$. Since the degree function $\deg:{\rm
Aut_{\Bbbk}({{\Bbbk}[x,y]})}\to{\mathbb{N}}$ is not bounded on ${\rm Aut}(D)$
we deduce it is not bounded on the kernel $K$ of that homomorphism, so $K$ is
not an algebraic group. Note that an element $\varphi=(f,g)\in K$ verifies
$\varphi(x)/x\in{\Bbbk}^{*}$, hence $f=\alpha x$ for some
$\alpha\in{\Bbbk}^{*}$. Since the jacobian of $\varphi$ is constant we deduce
$g=\gamma y+P(x)$ for some $\gamma\in{\Bbbk}^{*}$ and $P\in{\Bbbk}[x]$. In
other words $K$ is contained in the subgroup of ${\rm J({{\Bbbk}[x,y]})}$
whose elements fix the ideal generated by $x$. More explicitly, if
$\varphi=(\alpha x,\gamma y+P(x))\in K$, then

$\left\\{\begin{array}[]{l}\alpha^{\ell-1}a(\alpha x,\gamma y+P(x))=a(x,y)\\\
b(\alpha x,\gamma y+P(x))=\gamma
b(x,y)+x^{\ell}a(x,y)P^{\prime}(x).\end{array}\right.$ (1)

On the other hand, since $K$ is not an algebraic group we deduce it contains a
sequence $(\varphi_{n})_{n\geq 1}$ of elements such that the corresponding
sequence of degrees $(\deg\varphi_{n})_{n\geq 1}$ is increasing. We will show
in several steps this implies $a=0$ which yields a contradiction and
terminates the proof. Write $\varphi_{n}=(\alpha_{n}x,\gamma_{n}y+P_{n}(x))$,
$n\geq 1$.

First we observe that $a$ does not depend on $y$. Indeed, write
$a=\sum_{i=0}^{d}a_{i}(x)y^{i}$, $d\geq 0$. Since $\deg P_{n}$ increases with
$n$, if $d>0$ we see that the top equality in (1) implies $\deg P_{n}(x)^{d}$
is bounded, hence $d=0$.

Second, by an analogous reasoning the bottom equality in (1) gives
$b=b_{0}(x)+b_{1}(x)y$, where $b_{1}\neq 0$, and then that equality is
equivalent to the following two ones

$\displaystyle b_{0}(\alpha x)+b_{1}(\alpha x)P(x)$ $\displaystyle=$
$\displaystyle\gamma b_{0}(x)+x^{\ell}a(x)P^{\prime}(x),$ (2) $\displaystyle
b_{1}(\alpha x)$ $\displaystyle=$ $\displaystyle b_{1}(x).$ (3)

Now write

$a=\sum_{i=0}^{r}A_{i}x^{i},\ b_{1}=\sum_{i=0}^{s}B_{i}x^{i},$

where $A_{r}B_{s}\neq 0$. If $P=P_{n}=\sum_{i=0}^{m}p_{i}x^{i}$ for some $n\gg
0$, we deduce

$m=m_{n}=\alpha_{n}^{s}B_{s}A_{r}^{-1}.$

Hence we may suppose $\alpha_{n}^{s}\neq 1$ because $m_{n}$ increases with
$n$, and so $s=\deg b_{1}>0$. From (3) we deduce $\alpha=1$, a contradiction
which finishes the proof. ∎

Now we treat the case $(d)$ of Lemma 2.1. We have the following result valid
over an arbitrary field of characteristic zero which together with Proposition
2.2 readily leads Theorem 1.1.

######  Proposition 2.3.

Let $D$ be a derivation such that $\rm{\mathbb{e}}(D)=0$. Then ${\rm Aut}(D)$
is finite.

###### Proof.

If ${\Bbbk}={\mathbb{C}}$ is the field of complex numbers, the result is a
straightforward consequence of [CMP2019, Thm. A]. Denote by $\ell$ the order
of ${\rm Aut}(D)$ in that case. It suffices to prove that if
$F=\\{\varphi_{1},\ldots,\varphi_{n}\\}$ is a subset of ${\rm Aut}(D)$ in the
general case, then $n\leq\ell$.

In fact, inspired by the proof of [DeKa2009, Prop. 1.4] we consider the
extension ${\Bbbk}_{0}$ of ${\mathbb{Q}}$ obtained by adjoining the
coefficients of $D(x),D(y)$, $\varphi_{i}(x)$, $\varphi_{i}(y)$, $i=\ldots,n$.
Then $D$ and all of the $\varphi_{i}^{\prime}$s restraint to give a derivation
and suitable automorphisms
$D_{0},\varphi_{i0}:{\Bbbk}_{0}[x,y]\to{\Bbbk}_{0}[x,y]$, $i=1\ldots,n$, such
that $\varphi_{i0}D=D\varphi_{i0}$ for all $i$. Since ${\Bbbk}_{0}$ is
isomorphic to a subfield of ${\mathbb{C}}$ we may suppose
${\Bbbk}_{0}\subset{\mathbb{C}}$, and then all these maps extend to
${\mathbb{C}}[x,y]$ from which the assertion follows. ∎

######  Example 2.4.

Theorem 1.1 doesn’t hold true for $n>2$. Indeed, let
$D=\sum_{i=1}^{n}a_{i}\partial_{x_{i}}$ be a derivation of
$B={\Bbbk}[x_{1},\ldots,x_{n}]$, where $a_{1},\ldots,a_{n-1}$ don’t depend on
$x_{1},x_{n}$ and $a_{n}=0$. Then $D$ induces a derivation in
$A={\Bbbk}[x_{2},\ldots,x_{n-1}]$. If $a_{2},\ldots,a_{n-1}$ are general
enough to ensure $D$ is not locally nilpotent as derivation in $A$, then it is
so also as derivation in $B$. However, ${\rm Aut}(D)$ contains the
automorphisms of the form

$(x_{1}+p(x_{n}),\ldots,x_{n-1},x_{n}),\ p\in{\Bbbk}[x_{n}],$

hence it contains elements defined by polynomials of arbitrary degree.

## References

  * [BaPa2019] R. Baltazar and I. Pan, _On the Automorphism Group of a polynomial differential ring in two variables_ , arxiv preprint at https://arxiv.org/abs/1910.05278, to appear in Journal of Algebra.
  * [BaVe2020] R. Baltazar and M. Veloso, _On Isotropy group of Danielewski surfaces_ , arxiv preprint at https://arxiv.org/abs/2004.11748, to appear in Communications in Algebra.
  * [BlSt2015] J. Blanc and I. Stampfli, _Automorphisms of the plane preserving a curve_ , Algebraic Geometry 2 (2) (2015) 193–213.
  * [CMP2019] G. Cousin, L. G. Mendes and I. Pan, _Birational geometry of foliations associated to simple derivations_ , Bull. Soc. Math. de France, t. 147, fasc. 4 (2019), 607-638.
  * [DeKa2009] D. Daigle, Sh. Kaliman, _A Note on Locallly Nilpotent Derivations and Variables of $k[X,Y,Z]$_, Canad. Math. Bull. Vol. 52 (4), 2009 pp. 535–543.
  * [Ka1979] T. Kambayashi, _Automorphism Group of a Polynomial Ring and Algebraic Group Action on an Affine Space_ , J. of Algebra, 60 (1979), pp. 439-451 .
  * [Ku] S. Kumar, Kac-Moody groups, their flag varieties and representation theory, Progress in Mathematics, 204, Birkhaüser Boston, Inc., Boston, MA, 2002.
  * [MePa2016] L.G. Mendes and I. Pan, _On plane polynomial automorphisms commuting with simple derivations_ , Journal of Pure and Applied Algebra Volume 221, Issue 4 (2017), pp. 875-882.
  * [Re1968] R. Rentschler, _Opérations du groupe additif sur le plan affine_ , C. R. Acad. Sc. Paris, Vol. 267 (1968) pp. 384-387.
  * [Sha1981] I. R. Shafarevich _On some infinite dimensional algebraic groups. II_ , Izv. Akad. Nauk SSSR Ser. Mat. 45 (1) (1981), pp. 214-226, 240.
  * [vdE] A. van den Essen, _Polynomial Automorphisms and the Jacobian Conjecture_ , Progress in Mathematics, Vol. 190, Birkhäuser (2000).


#  On the Statistics of the Number of Fixed-Dimensional Subcubes in a Random
Subset of the n-Dimensional Discrete Unit Cube

Svante Janson  Department of Mathematics, Uppsala University, PO Box 480,
SE-751 06 Uppsala, Sweden  svante.janson [At] math [Dot] uu [Dot] se
http://www.math.uu.se/$\sim$svante/ ,  Blair Seidler  Department of
Mathematics, Rutgers University (New Brunswick), Piscataway NJ 08854, USA
blair [At] math [Dot] rutgers [Dot] edu and  Doron ZEILBERGER  Department of
Mathematics, Rutgers University (New Brunswick), Piscataway, NJ 08854, USA
zeilberg [At] math [Dot] rutgers [Dot] edu

(Date: Feb. 17, 2023)

###### Abstract.

This paper consists of two independent, but related parts. In the first part
we show how to use symbolic computation to derive explicit expressions for the
first few moments of the number of implicants that a random Boolean function
has, or equivalently the number of fixed-dimensional subcubes contained in a
random subset of the $n$-dimensional cube. These explicit expressions suggest,
but do not prove, that these random variables are always asymptotically
normal.

The second part presents a full, human-generated proof, of this asymptotic
normality, first proved by Urszula Konieczna.

###### 2000 Mathematics Subject Classification:

Accompanied by Maple package SMCboole.txt, available from
http://www.math.rutgers.edu/$\sim$zeilberg/mamarim/mamarimhtml/subcubes.html.

##  1\. Introduction

###  1.1. Motivation

Recall that an _implicant_ of a Boolean function in $n$ variables,
$f(x_{1},\dots,x_{n})$ is a pure disjunction

$\displaystyle x_{i_{1}}^{a_{1}}\,\wedge\,x_{i_{2}}^{a_{2}}\wedge\dots\wedge
x_{i_{r}}^{a_{r}},$ (1.1)

that implies it. Here $1\leq i_{1}<\dots i_{r}\leq n$,
$a_{1},\dots,a_{r}\in\\{0,1\\}$, $z^{1}=z$, and $z^{0}=\bar{z}$ (the negation
of $z$).

Fix $r$ and let $n$ vary. We are interested in the statistical distribution of
the random variable number of implicants of length $n-r$ in a uniformly-at-
random Boolean function of $n$ variables. Clearly, when $r=0$ it is nothing
but the good old (fair) binomial distribution with $2^{n}$ fair coin-tosses,
$B(\frac{1}{2},2^{n})$.

Equivalently, for a random subset of the $n$-dimensional cube, we are
interested in the statistical distribution of the number of $r$-dimensional
subcubes properly contained in it.

We would like to have explicit expressions, in $n$, for the $k^{th}$ moment of
this random variable, for as many as possible $r$ and $k$. This turns out to
be a challenging symbolic-computational problem that we will address in the
first part of this paper.

In the second part we consider asymptotics as ${n\to\infty}$. It was proved by
Urszula Konieczna [3] that for each fixed $r$, this distribution is
asymptotically normal. We will reprove this by a somewhat different method
which leads to a simple proof.

###  1.2. Our Random Variables

The _sample space_ is the set of subsets of $\\{0,1\\}^{n}$, that has
cardinality $2^{2^{n}}$.

Let’s define our random variables formally. For a (uniformly-at-) random
subset $S$, of $\\{0,1\\}^{n}$, and _fixed_ $r$, define the random variable

$\displaystyle X_{r}(S):=\text{ number of }r\text{-dimensional subcubes of
}S.$ (1.2)

For example, if $n=3$ and

$\displaystyle S=\\{000,001,010,011,100,111\\},$ (1.3)

we have

$\displaystyle X_{0}(S)=6,\quad X_{1}(S)=6,\quad X_{2}(S)=1,\quad X_{3}(S)=0.$
(1.4)

We would like to get, for as many pairs $(k,r)$ as possible, explicit
expressions in $n$, for the $k$-th moment of $X_{r}$, i.e. for

$\displaystyle f_{kr}(n):=\operatorname{\mathbb{E}{}}[{X_{r}}^{k}](n).$ (1.5)

##  2\. Explicit Expressions for Moments of the Number of Low-Dimensional
Subcubes in a Random Subest of the $n$-dimensional cube

###  2.1. The Expectation and Variance

The first moment, aka expectation, aka mean, aka average, is easy, using
linearity of expectation.

For any specific subcube $C$ of $\\{0,1\\}^{n}$, define the atomic random
variable, $X_{C}$, on subsets, $S$, of $\\{0,1\\}^{n}$ as follows.

$\displaystyle X_{C}(S)\,=\,\begin{cases}1,&\text{if}\quad C\subset S;\\\
0,&\text{otherwise}.\end{cases}$ (2.1)

Let $\mathcal{C}(n,r)$ be the set of all ${\binom{n}{r}}2^{n-r}$
$r$-dimensional subcubes of $\\{0,1\\}^{n}$. Then, of course,

$\displaystyle X_{r}(S)\,=\,\sum_{C\in\mathcal{C}(n,r)}X_{C}(S).$ (2.2)

Applying the expectation functional and using the linearity of expectation, we
get that the average, let’s call it $\mu_{r}(n)$, is

$\displaystyle\mu_{r}(n)=\operatorname{\mathbb{E}{}}[X_{r}]\,=\,\operatorname{\mathbb{E}{}}\left[\sum_{C\in\mathcal{C}(n,r)}X_{C}\right]\,=\,\sum_{C\in\mathcal{C}(n,r)}\operatorname{\mathbb{E}{}}[X_{C}].$
(2.3)

Now the probability that a random subset of $\\{0,1\\}^{n}$ contains an
$r$-dimensional subcube $C$ is $\left(\frac{1}{2}\right)^{2^{r}}$, since for
each of its vertices, the chance of it belonging to $S$ is $\frac{1}{2}$, and
by independence the probability that all its $2^{r}$ vertices belong to $S$ is
indeed $\frac{1}{2^{2^{r}}}$. The probability that $X_{C}(S)=0$ is of course
$1-\left(\frac{1}{2}\right)^{2^{r}}$, hence

$\displaystyle\operatorname{\mathbb{E}{}}[X_{C}]=1\cdot\left(\frac{1}{2}\right)^{2^{r}}\,+\,0\cdot\left(1-\left(\frac{1}{2}\right)^{2^{r}}\right)\,=\,\left(\frac{1}{2}\right)^{2^{r}}.$
(2.4)

Going back to equation (2.3) we have

$\displaystyle\mu_{r}(n)\,=\,\sum_{C\in\mathcal{C}(n,r)}\operatorname{\mathbb{E}{}}[X_{C}]=\,\sum_{C\in\mathcal{C}(n,r)}\frac{1}{2^{2^{r}}}=|\mathcal{C}(n,r)|\cdot\frac{1}{2^{2^{r}}}=\frac{{\binom{n}{r}}2^{n-r}}{2^{2^{r}}}.$
(2.5)

In a beautiful paper, Thanatipanonda [5] derived an explicit expression for
the general second moment, for every $r$-dimensional cube.

Thanatipanoda’s General Formula for the Second Moment:

$\displaystyle\operatorname{\mathbb{E}{}}[X_{r}^{2}]\,=\,\sum_{i=0}^{r}\frac{n!2^{n-i}}{i!(r-i)!^{2}(n-2r+i)!2^{2^{r+1}}}\cdot(2^{2^{i}}-1)\,+\,\frac{[{\binom{n}{r}}2^{n-r}]^{2}}{2^{2^{r+1}}},$
(2.6)

from which immediately follows, using
$[\operatorname{\mathbb{E}{}}(X_{r}-\mu_{r}(n))^{2}]=\operatorname{\mathbb{E}{}}[X_{r}^{2}]-\mu_{r}(n)^{2}$,
the following formula.

Thanatipanoda’s General Formula for the Variance:

$\displaystyle\text{Var}(X_{r})=\sum_{i=0}^{r}\frac{n!2^{n-i}}{i!(r-i)!^{2}(n-2r+i)!2^{2^{r+1}}}\cdot(2^{2^{i}}-1).$
(2.7)

Note that the variance is a polynomial in $(n,2^{n})$ of degree $2r$ in $n$
and degree $1$ in $2^{n}$.

###  2.2. Higher Moments

####  2.2.1. Edges

Thanatipanonda was unable to get such a general formula for higher moments,
but did get $\operatorname{\mathbb{E}{}}[X_{1}^{3}]$, from which he
immediately deduced that the third central moment (or third-moment-about-the-
mean) of $X_{1}$ is

$\displaystyle\operatorname{\mathbb{E}{}}[(X_{1}-\mu_{1}(n))^{3}]\,=\,\frac{3n^{3}2^{n}}{64}.$
(2.8)

Using the symbolic-computational algorithms to be described in the next
section, we managed to derive the following explicit formulas

$\displaystyle\operatorname{\mathbb{E}{}}[(X_{1}-\mu_{1}(n))^{4}]=\frac{n2^{n}}{1024}\big{(}$
$\displaystyle 12n^{3}2^{n}+12n^{2}2^{n}+40n^{3}$
$\displaystyle+3n2^{n}-48n^{2}+12n-16\big{)},$ (2.9)

$\displaystyle\operatorname{\mathbb{E}{}}[(X_{1}-\mu_{1}(n))^{5}]=\frac{5n^{3}2^{n}}{1024}\left(6n^{2}2^{n}+3n2^{n}+4n^{2}-24n+8\right),$
(2.10)

$\displaystyle\operatorname{\mathbb{E}{}}[(X_{1}-$
$\displaystyle\mu_{1}(n))^{6}]=$
$\displaystyle\frac{n2^{n}}{32768}\cdot\big{(}$ $\displaystyle
120n^{5}\left(2^{n}\right)^{2}+180n^{4}\left(2^{n}\right)^{2}+1920n^{5}2^{n}+90n^{3}\left(2^{n}\right)^{2}$
$\displaystyle-840n^{4}2^{n}-1792n^{5}+15n^{2}\left(2^{n}\right)^{2}-360n^{3}2^{n}-5280n^{4}$
$\displaystyle-300n^{2}2^{n}+3840n^{3}-240n2^{n}+3840n^{2}-6720n+4864\big{)}.$
(2.11)

It follows that the scaled moments about the mean for the third, fourth,
fifth, and sixth moments, converge, as $n\rightarrow\infty$, to $0,3,0,15$
respectively, the respective moments of the normal distribution, indicating
that the random variable $X_{1}$ (the number of edges contained in $S$) is
probably asymptotically normal. To fully prove asymptotic normality, of
course, we need to prove it for all moments, not just for the first six.

####  2.2.2. Squares

We only managed to get explicit expressions for the third and fourth moments
for $X_{2}$.

$\displaystyle\operatorname{\mathbb{E}{}}[(X_{2}-\mu_{2}(n))^{3}]\,=\,\frac{2^{n}n\left(n-1\right)}{32768}\left(9n^{4}+6n^{3}+21n^{2}-16n-34\right),$
(2.12)

$\displaystyle\operatorname{\mathbb{E}{}}[(X_{2}-\mu_{2}(n))^{4}$
$\displaystyle]=$
$\displaystyle\frac{2^{n}n\left(n-1\right)}{4194304}\cdot\big{(}$
$\displaystyle
12n^{6}2^{n}+12n^{5}2^{n}+520n^{6}+24n^{4}2^{n}-24n^{5}-12n^{3}2^{n}+1272n^{4}$
$\displaystyle-9n^{2}2^{n}-840n^{3}-27n2^{n}-5232n^{2}-2768n+240\big{)}.$
(2.13)

####  2.2.3. 3-dimensional cubes

We only managed to get an explicit expression for the third moment for
$X_{3}$.

$\displaystyle\operatorname{\mathbb{E}{}}[(X_{3}-\mu_{3}(n))^{3}]=\quad\quad$
$\displaystyle\frac{2^{n}n\left(n-1\right)\left(n-2\right)}{2415919104}\big{(}$
$\displaystyle 14n^{6}+24n^{5}+479n^{4}+2046n^{3}$
$\displaystyle+6779n^{2}+15444n-23112\big{)}.$ (2.14)

###  2.3. Our Method

Obviously we did not derive these formulas by hand. We had to teach our
computer how to find them. It also uses linearity of expectation, but with
higher moments things get very complicated. Recall that

$\displaystyle X_{r}(S)\,=\,\sum_{C\in\mathcal{C}(n,r)}X_{C}(S).$ (2.15)

Hence, the $k$-th moment is

$\displaystyle\operatorname{\mathbb{E}{}}\left[(X_{r})^{k}\right]$
$\displaystyle=\operatorname{\mathbb{E}{}}\Big{[}\Big{(}\sum_{C\in\mathcal{C}(n,r)}X_{C}(S)\Big{)}^{k}\Big{]}$
$\displaystyle=\sum_{[C_{1},\dots,C_{k}]\in\mathcal{C}(n,r)^{k}}\operatorname{\mathbb{E}{}}[X_{C_{1}}X_{C_{2}}\cdots
X_{C_{k}}].$ (2.16)

So we sum over all $({\binom{n}{r}}2^{n-r})^{k}$ members of
$\mathcal{C}(n,r)^{k}$. Since the product $X_{C_{1}}(S)X_{C_{2}}(S)\cdots
X_{C_{k}}(S)=1$ if each of $C_{1},C_{2},\dots,C_{k}$ is properly included in
$S$ (i.e. if each vertex in $C_{1}\cup C_{2}\cup\dots C_{k}$ belongs to $S$),
and $0$ otherwise, the contribution, or weight, due to each such term is

$\displaystyle\text{Weight}([C_{1},C_{2},\dots,C_{k}])=\operatorname{\mathbb{E}{}}\left[X_{C_{1}}X_{C_{2}}\cdots
X_{C_{k}}\right]=\frac{1}{2^{|C_{1}\cup C_{2}\cup\dots C_{k}|}}.$ (2.17)

####  2.3.1. Data Structure

Every $r$-dimensional subcube of $\\{0,1\\}^{n}$ has the form

$\displaystyle
C=\\{(x_{1},\dots,x_{n})\in\\{0,1\\}^{n}\,|\,x_{i_{1}}=\alpha_{i_{1}},\dots,x_{i_{n-r}}=\alpha_{i_{n-r}}\\},$
(2.18)

for some $1\leq i_{1}<i_{2}<\dots<i_{n-r}\leq n$ and
$(\alpha_{i_{1}},\dots\alpha_{i_{n-r}})\in\\{0,1\\}^{n-r}$. A good way to
represent it on a computer is as a row-vector of length $n$, in the alphabet
$\\{0,1,*\\}$, where the entries corresponding to $i_{1},i_{2},\dots,i_{n-r}$
have $\alpha_{i_{1}},\dots.\alpha_{i_{n-r}}$ respectively and the remaining
$r$ entries are filled with wild cards, denoted by $*$.

For example, if $n=7$ and $r=3$, the $3$-dimensional cube

$\displaystyle\\{(x_{1},\dots,x_{7})\in\\{0,1\\}^{7}\,|\,x_{2}=1,x_{4}=1,x_{5}=0,x_{7}=1\\},$
(2.19)

is represented by

$\displaystyle*1*10*1.$ (2.20)

We are trying to find a weighted count of ordered $k$-tuples of
$r$-dimensional subcubes. The natural data structure for these is the set of
$k$ by $n$ matrices in the ‘alphabet’ $\\{0,1,*\\}$ where every row has
exactly $r$ ‘wildcards’, *.

Let’s call this set of matrices, that correspond to $\mathcal{C}(n,r)^{k}$,
$\mathcal{C}(n,r,k)$.

For any specific, numeric $n$, there are ‘only’ $(2^{n-r}{\binom{n}{r}})^{k}$
of these matrices, and for each and every one of them one can find the
cardinality of the union of the corresponding subcubes, let’s call it $v$, and
add to the running sum $\frac{1}{2^{v}}$. But we want to do it for symbolic
$n$, i.e. for ‘all’ $n$. We will soon see how, for each specific (numeric) $r$
and $k$ this can be done in principle, but only for relatively small $r$ and
$k$ in practice. But let’s try and push it as far we can. An interesting
consequence of our algorithm is the precise degree in $n$ and $2^{n}$ of the
expression for $\operatorname{\mathbb{E}{}}[X_{r}^{k}](n)$.

####  2.3.2. The Kernel

A key object in our approach is the kernel. Given a $k\times n$ matrix $M$ in
the alphabet $\\{0,1,*\\}$ let’s call a column active if it contains at least
one ‘$*$’. Note that the matrix has exactly $k\cdot r$ ‘$*$’s, hence the
number of active columns, let’s call it $a$, is between $r$ and $k\cdot r$.
111More generally, if we want to find an expression for the mixed moment
$\operatorname{\mathbb{E}{}}[X_{r_{1}}\cdots X_{r_{k}}]$ the number of active
columns is between $\max(r_{1},\dots,r_{k})$ and $r_{1}+\dots+r_{k}$. The
kernel of $M$ is the submatrix of $M$ consisting of its active columns.

Let $\mathcal{C}_{a}(n,r,k)$ be the subset of $\mathcal{C}(n,r,k)$ matrices
with exactly $a$ active columns. We will call such a matrix in canonical form
if the active columns are occupied by the $a$ leftmost columns (i.e. its
kernel is contiguous starting in the first column). Let’s denote by
$\overline{\mathcal{C}}_{a}(n,r,k)$ the set of such matrices in canonical
form. Obviously, there are ${\binom{n}{a}}$ ways to choose which of the $n$
columns are active and hence

$\displaystyle\text{Weight}(\mathcal{C}(n,r,k))\,=$
$\displaystyle\,\sum_{a=r}^{rk}\text{Weight}(\mathcal{C}_{a}(n,r,k))$
$\displaystyle=$
$\displaystyle\sum_{a=r}^{rk}{\binom{n}{a}}\,\text{Weight}(\overline{\mathcal{C}}_{a}(n,r,k)).$
(2.21)

For any set, $S$, $\text{Weight}(S)$ is the sum of the weights of its members.
Note that this has degree $rk$ in $n$.

It remains to do a weighted-count, where every matrix gets ‘credit’ $1/2^{v}$,
where $v$ is the cardinality of the union of the corresponding subcubes
represented by the $k$ rows, for the set $\overline{\mathcal{C}}_{a}(n,r,k)$,
of matrices in canonical form. Note that there are only finitely many choices
for the $a$ leftmost columns, i.e. the set of $k\times a$ matrices in the
alphabet $\\{0,1,*\\}$ with the property that every column has at least one
‘$*$’, and every row has exactly $r$ ‘$*$’s. These can be divided into
equivalence classes obtained by permuting rows and columns and transposing $0$
and $1$ in any given column. Once these are sorted into equivalence classes,
one needs only examine one representative, and then multiply the weight by the
cardinality of the class.

But what about the $n-a$ rightmost columns? There are $2^{k(n-a)}$ possible
submatrices; the alphabet here is $\\{0,1\\}$. Almost all of these have
distinct rows, more precisely,

$\displaystyle{\binom{2^{n-a}}{k}}k!$ (2.22)

of them, and these will produce the smallest possible weight in conjunction
with any kernel. The other extreme is that all the rows of the submatrix
consisting of the $n-a$ rightmost columns are identical, and then there are
only $2^{n-a}$ choices to fill them in.

In general, every such member of $\overline{\mathcal{C}}_{a}(n,r,k)$,
determines a set partition of the set of rows $\\{1,\dots,k\\}$, where two
rows are roomates if they have the same last $n-a$ entries. If that set-
partition has $m$ members $1\leq m\leq k$, then the number of choices of
assigning different $0-1$ vectors of length $n-a$ to each of the parts of the
set-partition is

$\displaystyle{\binom{2^{n-a}}{m}}m!.$ (2.23)

Now for each $a$ and for each set-partition, we let the computer generate the
finite set of $k\times a$ matrices in the alphabet $\\{0,1,*\\}$. Each of the
members of the set partition has its own submatrix, and we ask our computer to
kindly find the number of vertices in the corresponding union of subcubes
corresponding to each member of the examined set partition. Since they are
disjoint, we add them up, getting $v$ for that particular pair (matrix, set-
partition), giving credit $1/2^{v}$.

####  2.3.3. Implementation

All this is implemented in the Maple package SMCboole.txt, available from:
https://sites.math.rutgers.edu/~zeilberg/tokhniot/SMCboole.txt

In particular ‘Moms(A,n);’, for any list of non-negative integers
$A=[r_{1},\dots r_{k}]$ gives you the mixed moment
$\operatorname{\mathbb{E}{}}[X_{r_{1}}\cdots X_{r_{k}}]$. For example, to get
the third moment of the number of edges (i.e. $1$-dimensional subcubes) type
Moms([1,1,1],n); , which very quickly returns:

$\displaystyle\frac{2^{n}n^{2}\left(\left(2^{n}\right)^{2}n+12\,2^{n}n+6\,2^{n}+24n\right)}{512}.$
(2.24)

To get the third moment of the number of squares (i.e. $2$-dimensional
subcubes), type Moms([2,2,2],n); , getting

$\displaystyle\frac{2^{n}n\left(n-1\right)}{2097152}\cdot\bigg{(}$
$\displaystyle\left(2^{n}\right)^{2}n^{4}-2\left(2^{n}\right)^{2}n^{3}+48\,2^{n}n^{4}+\left(2^{n}\right)^{2}n^{2}$
$\displaystyle+576n^{4}+24\,2^{n}n^{2}+384n^{3}-72\,2^{n}n$
$\displaystyle+1344n^{2}-1024n-2176\bigg{)}.$ (2.25)

The third moment of the number of $3$-dimensional cubes takes a bit longer,
and we were unable to compute the fourth moment of the number of
$3$-dimensional cubes; it took too much time and too much space.

More informative for statistical purposes are the central moments,
$\operatorname{\mathbb{E}{}}[(X_{r}-\mu_{r}(n))^{k}]$, that Maple easily
derives, using linearity of expectation from the pure moments. The function
call for this is MOMrk(r,k,n); where r and k are numeric but $n$ is a symbol
denoting the dimension of the ambient cube.

To get the explicit expression given above for the third through sixth moments
for the number of edges, the third and fourth moments for the number of
squares, and the third moment for the number of $3$-dimensional subcube (all
about the mean) we typed:

MOMrk(1,3,n); , MOMrk(1,4,n); , MOMrk(1,5,n); , MOMrk(1,6,n); ,

MOMrk(2,3,n); , MOMrk(2,4,n); ,

MOMrk(3,3,n);

respectively. To our chagrin, ‘MOMrk(3,4,n);’ took too long.

####  2.3.4. Consequence of the algorithm

: The $k$-th moment of $X_{r}$ is a bivariate polynomial in $(n,2^{n})$ of
degree $k\,r$ in $n$ and degree $k$ in $2^{n}$ .

This raises the theoretical possibility (in God’s computer) of finding these
expressions by pure brute force. The generic polynomial in $(n,2^{n})$ of
degree $kr$ in $n$ and degree $k$ in $2^{n}$ has $(1+kr)(1+k)$ ‘degrees of
freedom’. So using undetermined coefficients we need to generate a table of
$\operatorname{\mathbb{E}{}}[X_{r}^{k}](n)$ for $1\leq n\leq(1+kr)\cdot(1+k)$.
After gathering the data, we use linear algebra to solve a system of
$(1+kr)\cdot(1+k)$ equations with that many unknowns. For each specific
$n=n_{1}$ there are ‘only’ $2^{2^{n_{1}}}$ subsets, and for each of them we
can ask how many $r$-dimensional subcubes do they contain, raise it to the
$k$-th power and take the average. Alas, $2^{2^{5}}$ is already big enough, so
only God’s computer, with practically infinite time and space, can carry this
brute force approach.

##  3\. Asymptotic Normality

As said in the introduction, asymptotic normality of $X_{r}$ was proved by
Urszula Konieczna [3]. The random variable $X_{r}$ depends on $n$, and for
emphasis, we denote it in the sequel by $X_{n,r}$. We may then state the
result as follows, where $N(0,1)$ denotes the standard normal distribution.

######  Theorem 3.1 ([3]).

For every fixed $r\geq 0$, we have as ${n\to\infty}$

$\displaystyle\frac{X_{n,r}-\mu_{r}(n)}{\sqrt{\operatorname{Var}(X_{n,r})}}\overset{\mathrm{d}}{\longrightarrow}N(0,1)$
(3.1)

with convergence in distribution and of all moments.

As already noted at the very beginning of this paper, the case $r=0$ is well
known, since then the variables $X_{C}$ are independent and this becomes an
instance of the central limit theorem for binomial variables, known since a
pamphlet by de Moivre in 1733. (This case can be used as a sanity check in the
arguments below.)

The proof in [3] is based on the method of moments. We will in this section
survey how a variation of this method, based on cumulants and dependency
graphs leads to a quick proof with almost no calculations.

######  Remark 3.2.

Urszula Konieczna [3] considered a more general case where each subcube
appears with probability $p\in(0,1)$, where $p=p(n)$ may depend on $n$, and
showed asymptotic normality for a large range of $p(n)$. A special case, not
including the case $p=\frac{1}{2}$ treated here, was earlier shown by Karl
Weber [6]. This extension can also be treated by the method below, but for
simplicity we continue to consider only the case $p=\frac{1}{2}$ discussed in
Section 2.

The aim is thus to show that the leading terms in the expressions for the
central moments $\operatorname{\mathbb{E}{}}[(X_{n,r}-\mu_{r}(n))^{k}]$ are
what we would expect from a normal distribution, or, more formally, that the
scaled central moments

$\displaystyle\operatorname{\mathbb{E}{}}\left[\left(\frac{X_{n,r}-\mu_{r}(n)}{\sqrt{\operatorname{Var}(X_{n,r})}}\right)^{k}\right]$
(3.2)

converge as ${n\to\infty}$ to the corresponding moment
$\operatorname{\mathbb{E}{}}[Z^{k}]$ of a standard normal random variable $Z$,
for every fixed $r\geq 0$ and $k\geq 1$. Then, the random variables $X_{n,r}$
are asymptotically normal by the method of moments.

We thus want to find the leading term of the moment (3.2). In Section 2, we
computed the central moments from the pure moments. This involves massive
cancellation of high-order terms, and is less suitable for a (human) proof for
general $k$.

As a first step, we may modify (2.3) and instead expand the central moment as

$\displaystyle\operatorname{\mathbb{E}{}}\bigl{[}(X_{n,r}-\mu_{r}(n))^{k}\bigr{]}$
$\displaystyle=\sum_{[C_{1},\dots,C_{k}]\in\mathcal{C}(n,r)^{k}}\operatorname{\mathbb{E}{}}\bigl{[}(X_{C_{1}}-\mu)\cdots(X_{C_{k}}-\mu)\bigr{]},$
(3.3)

where $\mu=\operatorname{\mathbb{E}{}}[X_{C}]$ is given by (2.4). Note that
two variables $X_{C_{1}}$ and $X_{C_{2}}$ are independent if $C_{1}\cap
C_{2}=\emptyset$. In particular, for $k=2$, all such terms in the sum in (3.3)
vanish; this leaves only $\Theta(n^{2r}2^{n})$ terms of the
$\Theta\bigl{(}n^{2r}2^{2n}\bigr{)}$ terms in the full sum, or in (2.3), which
is reflected in the leading terms in (2.6) and (2.7).

For higher moments, we can obtain a further reduction by considering cumulants
(also called semiinvariants) instead of moments. We describe this briefly,
referring to e.g. [4] or [2, pp. 145--149] for details. In general, if $Y$ is
a random variable with moments $m_{k}:=\operatorname{\mathbb{E}{}}[Y^{k}]$ and
moment generating function $\sum_{k=0}^{\infty}m_{k}t^{k}/k!$, then the
cumulants $\varkappa_{k}=\varkappa_{k}(Y)$ are the coefficients of the
generating function

$\displaystyle\sum_{k=1}^{\infty}\varkappa_{k}\frac{t^{k}}{k!}:=\log\left(\sum_{k=0}^{\infty}m_{k}\frac{t^{k}}{k!}\right).$
(3.4)

(The generating functions can be regarded as formal power series.) Moreover,
this generalizes to mixed cumulants $\varkappa_{k}(Y_{1},\dots,Y_{k})$ of
several random variables. This means that there are algebraic relations: each
cumulant $\varkappa_{k}$ is a polynomial in the moments $m_{\ell}$ of order
$\ell\leq k$, and conversely, and this generalizes to mixed cumulants and
moments. For example, $\varkappa_{1}=m_{1}=\operatorname{\mathbb{E}{}}Y$, and
$\varkappa_{2}=m_{2}-m_{1}^{2}=\operatorname{Var}(Y)$, and the mixed cumulant
$\varkappa(Y_{1},Y_{2})=\operatorname{\mathbb{E}{}}[Y_{1}Y_{2}]-\operatorname{\mathbb{E}{}}[Y_{1}]\operatorname{\mathbb{E}{}}[Y_{2}]$,
the covariance of $Y_{1}$ and $Y_{2}$.

A convenient property of cumulants is that a normal distribution
$N(\mu,\sigma^{2})$ has moment generating function $\exp\bigl{(}\mu
t+\tfrac{\sigma^{2}}{2}t^{2}\bigr{)}$, and thus by (3.4) cumulants
$\varkappa_{k}=0$ for $k\geq 3$. Consequently, to show that a normalized
sequence of random variables is asymptotically normal, it suffice to show that
each cumulant $\varkappa_{k}$ with $k\geq 3$ converges to 0.

The mixed cumulants are multilinear, and thus we have an analog of (2.3) and
(3.3):

$\displaystyle\varkappa_{k}\bigl{(}X_{n,r}\bigr{)}$
$\displaystyle=\varkappa\bigl{(}X_{n,r},\dots,X_{n,r}\bigr{)}$
$\displaystyle=\sum_{[C_{1},\dots,C_{k}]\in\mathcal{C}(n,r)^{k}}\varkappa\bigl{(}X_{C_{1}},\dots,X_{C_{k}}\bigr{)}.$
(3.5)

We can here reduce the number of terms in the sum by a general property of
cumulants: If there is a partition $\\{1,\dots,k\\}=I\cup J$ into two non-
empty sets $I$ and $J$ such the two families of random variables $(Y_{i}\mid
i\in I)$ and $(Y_{j}\mid j\in J)$ are independent of each other, then the
mixed cumulant $\varkappa(Y_{1},\dots,Y_{k})=0$. (Informally, this means that
the $k$th cumulant $\varkappa_{k}(X_{n,r})$ can be seen as some kind of
measure of $k$th order dependencies in the sum (2.2), with lower order
dependencies removed.)

As noticed above, each of our variables $X_{C}$ is independent of most of the
others. We need to keep track of not just pairwise independence, but also
independence between families of such variables; it is then convenient to use
the notion of dependency graphs.

######  Definition.

Let $(Y_{\alpha})_{\alpha\in\mathcal{A}}$ be a family of random variables,
with some arbitrary index set $\mathcal{A}$. A dependency graph for this
family is a graph $\Gamma$ with vertex set $\mathcal{A}$, such that if $I$ and
$J$ are two disjoint subsets of $\mathcal{A}$ such that there is no edge in
$\Gamma$ with one endpoint in $I$ and the other in $J$, then the two families
$(Y_{\alpha}\mid\alpha\in I)$ and $(Y_{\beta}\mid\beta\in J)$ are independent
of each other.

######  Lemma 3.3.

Let $\Gamma(n,r)$ be the graph with vertex set $\mathcal{C}(n,r)$ and an edge
between two distinct cubes $C,C^{\prime}\in\mathcal{C}(n,r)$ iff $C\cap
C^{\prime}\neq\emptyset$. Then $\Gamma(n,r)$ is a dependency graph for the
family $(X_{C}\mid C\in\mathcal{C}(n,r))$.

###### Proof.

Let $I$ and $J$ be disjoint subsets of $\mathcal{C}(n,r)$ with no edge between
$I$ and $J$. Then $V_{I}:=\bigcup_{C\in I}C$ and $V_{J}:=\bigcup_{C\in J}C$
are two disjoint subsets of $\\{0,1\\}^{n}$. Thus the two random sets $S\cap
V_{I}$ and $S\cap V_{J}$ are independent. Since the random variables
$(X_{C}\mid C\in I)$ only depend on $S\cap V_{I}$, and similarly for $J$, it
follows that the families $(X_{C}\mid C\in I)$ and $(X_{C}\mid C\in J)$ are
independent. ∎

We can now use the dependency graphs $\Gamma(n,r)$ and the machinery above to
estimate cumulants of $X_{n,r}$ and show that
$\varkappa_{k}\bigl{(}X_{n,r}\bigr{)}=o\bigl{(}(\operatorname{Var}X_{n,r})^{k/2}\bigr{)}$
as ${n\to\infty}$ for every fixed $r\geq 0$ and $k\geq 3$. However, we do not
have to do these calculations, since they already have been done under general
hypotheses, leading to convergence theorems that are easy to apply in
situations like ours where there is a rather sparse dependency graph. We use
here the following theorem, taken (with minor changes in notation) from [1,
Theorem 2, with moment convergence by its proof and Theorem 1]. See e.g. [2,
Theorems 6.18 and 6.20] for some related theorems (proved by the same cumulant
method) that also can be used to show Theorem 3.1, and [2, Theorem 6.33] for
another related theorem (proved by a different method) that also yields the
asymptotic normality in Theorem 3.1 (but not immediately moment convergence).

######  Theorem 3.4 ([1]).

Suppose that, for each $n$, $(Y_{n,\alpha}\mid\alpha\in\mathcal{A}_{n})$ is a
family of bounded random variables: $|Y_{n,\alpha}|\leq A_{n}$. Let
$N_{n}:=|\mathcal{A}_{n}|$. Suppose further that $\Gamma_{n}$ is a dependency
graph for this family, and let $M_{n}$ be the maximal degree of $\Gamma_{n}$
(assuming this is not $0$, in which case we let $M_{n}:=1$). Let
$W_{n}=\sum_{i\in\mathcal{A}_{i}}Y_{n,i}$ and
$\sigma^{2}_{n}:=\operatorname{Var}(W_{n})$. If there exists a positive
integer $m$ such that

$\displaystyle(N_{n}/M_{n})^{1/m}M_{n}A_{n}/\sigma_{n}\to 0\qquad\text{as
${n\to\infty}$},$ (3.6)

then

$\displaystyle\bigl{(}W_{n}-\operatorname{\mathbb{E}{}}W_{n}\bigr{)}/\sigma_{n}\overset{\mathrm{d}}{\longrightarrow}N(0,1)\qquad\text{as
${n\to\infty}$},$ (3.7)

with convergence in distribution and with all moments.

###### Proof of Theorem 3.1.

Fix $r\geq 0$. We let $c_{1},c_{2},c_{3}$ denote unimportant positive
constants that may depend on $r$, but not on $n$.

We use Theorem 3.4, with $Y_{n,C}:=X_{C}$ for
$C\in\mathcal{A}_{n}:=\mathcal{C}(n,r)$, so $W_{n}=X_{n,r}$. We use Lemma 3.3
and take the dependency graph $\Gamma_{n}=\Gamma(n,r)$. Then

$\displaystyle N_{n}=|\mathcal{C}(n,r)|=\binom{n}{r}2^{n-r}\leq n^{r}2^{n},$
(3.8)

and, by (2.7) (where $i=0$ yields the leading term),

$\displaystyle\sigma^{2}_{n}:=\operatorname{Var}(X_{n,r})\geq
c_{1}n^{2r}2^{n}.$ (3.9)

Furthermore, we may take

$\displaystyle A_{n}:=1.$ (3.10)

Moreover, from the definition of the graph $\Gamma(n,r)$ follows that it is
regular, with degree

$\displaystyle M_{n}\leq 2^{r}\binom{n}{r}\leq c_{2}n^{r}.$ (3.11)

We choose $m=3$ in Theorem 3.4. (This is the standard case, which corresponds
to the method of moment without extra arguments, see the proof in [1].) Then
(3.8)–(3.11) yield

$\displaystyle(N_{n}/M_{n})^{1/m}M_{n}A_{n}/\sigma_{n}=N_{n}^{1/3}M_{n}^{2/3}A_{n}/\sigma_{n}\leq
c_{3}\frac{n^{r}2^{n/3}}{n^{r}2^{n/2}}\to 0$ (3.12)

as ${n\to\infty}$, so (3.6) holds. Consequently, Theorem 3.4 applies and shows
Theorem 3.1. ∎

##  4\. Conclusion

In the first part, we demonstrated the power of computers to automatically
derive complicated explicit expressions, all polynomials in $n$ and $2^{n}$,
for low moments of the random variable number of fixed-size implicants of a
Boolean function of $n$ variable, or equivalently, the number of fixed-
dimensional subcubes of a random subset of the $n$-dimensional unit cube.
These implied that the scaled first few moments for low-dimensional subcubes
tend, as $n$ goes to infinity, to those of the Normal Distribution,
suggesting, but by no means proving, that for each fixed dimension, this
random variable is asymptotically normal.

In the second part, we demonstrated the power of human ingenuity, and the
traditional lore of probability and statistics, by presenting a simple proof
of asymptotic normality, first proved in [3].

## References

  * [1] Svante Janson, Normal convergence by higher semiinvariants with applications to sums of dependent random variables and random graphs. _Annals of Probability_ 16 (1988), 305--312.
  * [2] Svante Janson, Tomasz Łuczak and Andrzej Ruciński, _Random Graphs_. Wiley, New York, 2000.
  * [3] Urszula Konieczna, Asymptotic normality of subcubes in random subgraphs of the $n$-cube. _Discrete Mathematics_ 121 (1993), 117--122.
  * [4] V. P. Leonov and Albert Nikolaevich Shiryaev, On a method of semi-invariants. _Teor. Veroyatnost. i Primenen_ 4 (1959), 342--355. (Russian.) English transl: _Theor. Probability Appl._ 4 (1959), 319--329.
  * [5] Thotsaporn Aek Thanatipanonda, Reviews of Symbolic Moment Calculus, arXiv:2003.11749. https://arxiv.org/abs/2003.11749
  * [6] . Karl Weber, Poisson convergence in the $n$-cube. _Math. Nachr._ 131 (1987), 49--57.