# MalAlgoQA: A Pedagogical Approach for Evaluating Counterfactual Reasoning
Abilities

Naiming Liu
Rice University
<EMAIL_ADDRESS>
&Shashank Sonkar11footnotemark: 1
Rice University
<EMAIL_ADDRESS>
Myco Le
Rice University
<EMAIL_ADDRESS>
&Richard Baraniuk
Rice University
<EMAIL_ADDRESS>
First two authors contributed equally.

###### Abstract

This paper introduces MalAlgoQA, a novel dataset designed to evaluate the
counterfactual reasoning capabilities of Large Language Models (LLMs) through
a pedagogical approach. The dataset comprises mathematics and reading
comprehension questions, each accompanied by four answer choices and their
corresponding rationales. We focus on the incorrect answer rationales, termed
"malgorithms", which highlights flawed reasoning steps leading to incorrect
answers and offers valuable insights into erroneous thought processes. We also
propose the Malgorithm Identification task, where LLMs are assessed based on
their ability to identify corresponding malgorithm given an incorrect answer
choice. To evaluate the model performance, we introduce two metrics: Algorithm
Identification Accuracy (AIA) for correct answer rationale identification, and
Malgorithm Identification Accuracy (MIA) for incorrect answer rationale
identification. The task is challenging since state-of-the-art LLMs exhibit
significant drops in MIA as compared to AIA. Moreover, we find that the chain-
of-thought prompting technique not only fails to consistently enhance MIA, but
can also lead to underperformance compared to simple prompting. These findings
hold significant implications for the development of more cognitively-inspired
LLMs to improve their counterfactual reasoning abilities, particularly through
a pedagogical perspective where understanding and rectifying student
misconceptions are crucial. The data and code can be found at
https://github.com/luffycodes/MalAlgoQA-Dataset.

##  1 Introduction

Counterfactual reasoning refers to the ability to consider alternative
scenarios and infer the cause of an event based on hypothetical situations. It
is a fundamental aspect of human cognition that plays a crucial role in
problem-solving, decision-making, and learning [5, 13, 14]. Although large
language models (LLMs) have demonstrated remarkable performance in various
natural language processing tasks, their ability to engage in counterfactual
reasoning remains relatively underexplored. Counterfactual reasoning requires
a degree of hypothetical and abstract thinking, which poses a significant
challenge for current LLMs, as they are generally trained to predict outcomes
based on facts, rather than imagining alternative scenarios that might not be
explicitly present in the training data [3, 9, 19].

Question Each side of a square is 3 inches long. A student increases the
length of each side by 3 inches. The area of the new square is how many times
the area of the original square?

Answer Choices (A) 9 (Rationale: Squared the change in the length.) (B) 2
(Rationale: Calculated the relationship between the sides.) (C) 3 (Rationale:
Used the change in the length.) (D) 4 (Rationale: Calculated the area of the
original square: $3\times 3=9$ and the area of the new square with each side
length increased by 3 inches: $6\times 6=36$. Then determined that the area of
the new square is 4 times the area of the original square.)

Table 1: An example question from the MalAlgoQA dataset illustrating the
Malgorithm Identification task. Each answer choice is associated with a
rationale, representing the reasoning process that led to that answer. The
task for the model is to correctly identify the rationale given a particular
answer choice. For incorrect answer choices, the corresponding rationales are
malgorithms, representing flawed reasoning processes and thereby evaluating
the counterfactual reasoning abilities of LLMs.

To fill this gap, we introduce MalAlgoQA, a novel dataset designed to evaluate
the counterfactual reasoning capabilities of LLMs through a pedagogical
approach with multiple-choice question answering. MalAlgoQA consists of a
diverse set of 807 mathematics and 290 reading comprehension questions
spanning various grade levels (3-11), content classifications (e.g., algebra,
geometry, number & operations), and Depth of Knowledge levels (DOK) (1-3)
[25]. Each question is accompanied by a set of answer choices and their
associated rationales, which we term "malgorithms" (inspired by the concept of
"mal-rules" proposed by [11]). Malgorithms represent the flawed reasoning that
leads to an incorrect answer, revealing the underlying thought process that
causes a student to arrive at the incorrect conclusion.

With MalAlgoQA, we propose the Malgorithm Identification task, which involves
identifying the rationale behind the selection of a particular answer choice.
When the given answer choice is correct, a model needs to employ causal
reasoning to determine the rationale or algorithm that justified the correct
selection. On the other hand, when the given answer choice is incorrect, the
task demands counterfactual reasoning, as the model must identify the flawed
reasoning or malgorithm that led to the selection of an incorrect option. In
this case, the model must consider hypothetical scenarios and reason about the
cause of an incorrect choice, which may not align with the facts. To
illustrate the Malgorithm Identification task, consider a simple question:
"What is 1 + 2 × 3 + 4?" with choices A. 11, B. 13, and C. 21. The rationales
are: "Worked left to right" (corresponding to choice B), "Applied PEASMD rule
instead of PEMDAS" (corresponding to choice C), and "Applied PEMDAS rule"
(corresponding to the correct choice A). Given an answer choice, the model
should identify the rationale explaining that choice.

In order to evaluate model performance, we introduce two key metrics:
Algorithm Identification Accuracy (AIA), which measures accuracy in
identifying the rationale behind a given correct answer. Malgorithm
Identification Accuracy (MIA), of particular interest, evaluates the model’s
counterfactual causal reasoning abilities by quantifying accuracy in
identifying the rationale behind an incorrect answer. Our experiments reveal
that GPT-4o [10], a state-of-the-art LLM, achieves an AIA of $95.7\%$,
demonstrating its proficiency in this task. However, when it comes to MIA,
GPT-4o’s performance drops significantly, with an accuracy of only $66.1\%$.
This pattern, where accuracy is higher for correct answer rationales and lower
for incorrect answer rationales, is consistent across other language models,
such as LLaMA-3-70B [1] and GPT-3.5 [18]. It emphasizes the challenge of
counterfactual reasoning for LLMs, especially on finding the underlying
rationale behind incorrect answer choices.

Our experiments also reveal an unexpected result that Chain-of-Thought (CoT)
prompting not only fails to consistently enhance MIA, it sometimes even
underperforms compared to simple prompting. For example, GPT-4o achieves an
MIA of 68.6% with CoT prompting compared to 82.8% with simple prompting for
Reading. These results suggest that the reasoning steps provided by CoT
prompting can be detrimental for robust counterfactual reasoning.

Our experiments reveal a decline in LLM performance with increasing DOK and
grade level, highlighting challenges in handling complex questions and deep
reasoning for the Malgorithm identification task. Probability emerges as the
most challenging content area, while geometry is the least. This trend
underscores the struggle of LLMs to sustain high performance as cognitive
demands escalate.

Additionally, our experiments indicate that LLMs performance declines as the
DOK and grade level increases, suggesting that the complexity of the questions
and the depth of reasoning pose greater challenges for the Malgorithm
identification task. Among the content areas, Probability proves to be the
most difficult for LLMs, with Geometry being the least. This pattern shows
that as the cognitive demands of the tasks increase, LLMs struggle more to
maintain high performance levels. Overall, our findings further emphasize the
need for research and development of models that can effectively engage in
counterfactual reasoning.

##  2 Dataset: MalAlgoQA

We introduce MalAlgoQA, a real-world dataset consisting of multiple-choice
questions in both mathematics and reading comprehension for students in grade
3 through 11. The dataset is designed to evaluate the counterfactual reasoning
abilities of LLMs through the task of analyzing the rationales and reasons
behind incorrect answer choices, a process we refer to as “Malgorithm
identification". The MalAlgoQA dataset provides valuable resources to assess
the counterfactual reasoning capabilities of LLMs through a pedagogical
approach.

###  2.1 Dataset Overview

MalAlgoQA comprises two multiple-choice question sets: a mathematics and a
reading comprehension question set. The mathematics question set contains 807
questions, while the reading comprehension question set has 290 questions.
Each question is associated with four answer choices, as well as their
corresponding rationales. Reading question set also provides a passage for
each question. Table 1 provides an example of math question, with more
examples available in B, C. Additionally, the dataset provides rich metadata
including the grade level, content classification, and Depth of Knowledge
(DOK) level for each question.

####  2.1.1 Grade Levels

The questions in MalAlgoQA span across multiple grade levels, ranging from
Grade 3 to Grade 11. As illustrated in Table 2, the distribution of questions
for both mathematics and reading comprehension subsets is balanced across
different grade levels.

Grade Level | Math | Reading
---|---|---
3 | 132 | 45
4 | 120 | 47
5 | 94 | 33
6 | 140 | 41
7 | 159 | 35
8 | 128 | 42
10 | - | 47
11 | 34 | -
Table 2: Distribution of questions across grade levels.

####  2.1.2 Content Classifications

The mathematics questions set are categorized into five content
classifications: Number & Operation, Algebra, Geometry & Measurement, Data
Analysis, and Data Analysis & Probability. The reading comprehension questions
are divided into two content classifications: Informational Text and
Literature. Table 3 presents an overview of the distribution across content
classifications for both question sets.

Math Content Classifications
---
Classification | Questions
Algebra | 315
Number & Operation | 312
Geometry & Measurement | 122
Probability | 44
Data Analysis | 14
Reading Content Classifications
Classification | Questions
Informational Text | 190
Literature | 100
Table 3: Distribution of questions across content classifications.

####  2.1.3 Depth of Knowledge (DOK) Levels

Each question in MalAlgoQA is annotated with a DOK level, which indicates the
cognitive complexity of the question. The DOK levels are derived from Norman
L. Webb’s taxonomy [25] and range from I to III, with higher levels
representing increased cognitive complexity. Table 4 shows the distribution of
questions across DOK levels for both question sets.

DOK Level | Math | Reading
---|---|---
I | 349 | 37
II | 434 | 203
III | 24 | 50
Table 4: Distribution of questions across DOK levels.

###  2.2 Question and Rationale Characteristics

The questions in MalAlgoQA vary in length and complexity. The average length
of mathematics questions is 122 characters, while the average length of
reading comprehension questions is 104 characters. Reading comprehension
questions are accompanied by passages, which have an average length of 5783
characters. Each answer choice is associated with an rationale, which provide
explanations for the correct and incorrect answer choices. The average length
of answer rationales for mathematics questions is 227 characters, while the
average length of answer rationales for reading comprehension questions is
1699 characters.

##  3 Methodology

In this section, we present the task formulation for Malgorithm
Identification, which aims to evaluate the performance of LLMs by identifying
the relationship between answer choices and their underlying rationales.

###  3.1 Definitions and Task Formulation

Let $Q=\\{q_{1},q_{2},...,q_{n}\\}$ be a set of multiple-choice questions,
where each question $q_{i}$ has a set of answer choices
$C_{i}=\\{c_{i1},c_{i2},c_{i3},c_{i4}\\}$ and a set of rationales
$R_{i}=\\{r_{i1},r_{i2},r_{i3},r_{i4}\\}$ corresponding to each answer choice.
The rationale can be thought of as a chain of reasoning steps, where each step
represents a part of the thought process leading to the selection of an answer
choice.

⬇

CoT Prompt for Malgorithm Identification:

System: Provide step-by-step reasoning to determine the answer rationale that
corresponds to the given choice for the question. Then, provide your answer in
the specified JSON format.

Question: {question}

Choice: {choice}

Answer Rationales:

{formatted_rationales}

Given the question and answer rationales, determine which answer rationale
corresponds to the given choice for the question.

Provide step-by-step reasoning. Show the steps.

And then provide your answer in the following JSON format:

{{

"Correct Choice": "[A/B/C/D]"

}}

Table 5: Prompt for the Malgorithm Identification experiment, where the LLM
identifies the relationship between answer choices and rationales in a
multiple-choice question-answering setting. The task involves identifying a
"malgorithm", a rationale that represents flawed reasoning leading to an
incorrect answer choice. The prompt provides the question, an answer choice
(either correct or incorrect), and all rationales, asking the LLM to identify
the rationale corresponding to the given choice. The highlighted sentence
instructs the model to provide step-by-step reasoning, an instruction added
for the Chain-of-Thought prompting strategy.

##### Malgorithm

We introduce the term "malgorithm" to describe a rationale that contains a
combination of correct reasoning steps and one or more flawed steps, which we
call "mal-rules,". These "mal-rules" lead to incorrect answer choices. The
term "mal-rule" is derived from the cognitive error literature [4, 23, 11],
which refers to the flawed or incorrect rules that students may apply when
solving problems, resulting in systematic errors. In our context, a malgorithm
is a reasoning chain that consists of both correct rules and mal-rules, with
the presence of mal-rules ultimately leading to the selection of an incorrect
answer choice.

Formally, let $R_{i}^{correct}\subseteq R_{i}$ be the set of rationales that
correspond to correct answer choices for question $q_{i}$, and let
$R_{i}^{incorrect}\subseteq R_{i}$ be the set of rationales that correspond to
incorrect answer choices. A rationale $r_{ij}\in R_{i}^{incorrect}$ is
considered a malgorithm if it contains a combination of correct reasoning
steps and one or more mal-rules that lead to the selection of an incorrect
answer choice.

##### Malgorithm Identification Task

Given a question $q_{i}$, an answer choice $c_{ij}$ (either correct or
incorrect), and the set of rationales $R_{i}$, the LLM must identify the
rationale $r_{ik}$ that corresponds to the given answer choice $c_{ij}$. If
the given answer choice is incorrect, the corresponding rationale is a
malgorithm containing a combination of correct reasoning steps and one or more
mal-rules.

###  3.2 Evaluation Metrics

To gain a comprehensive understanding of the LLMs performance in the
Malgorithm Identification task, we use two key metrics:

1\. Algorithm Identification Accuracy (AIA): This metric measures the model’s
ability to identify the rationale or algorithm that aligns with a correct
answer choice. Essentially, AIA evaluates how well the model recognizes and
follows a chain of reasoning steps that lead to the correct answer choice.

2\. Malgorithm Identification Accuracy (MIA): This metric measures the model’s
ability to identify the flawed reasoning or malgorithm that aligns with an
incorrect answer choice. Specifically, MIA evaluates the model’s capacity to
identify faulty reasoning chains that contain a combination of correct steps
and one or more mal-rules, which ultimately lead to a wrong answer.

These metrics are crucial for analyzing reasoning abilities the LLMs. AIA is
essential for understanding the models’ thought processes behind correct
problem-solving strategies. In contrast, MIA evaluates the model’s ability
identifying flawed reasoning and counterfactual logic that lead to incorrect
answers. The combination of AIA and MIA enables us to analyze the models’
performance in both causal and counterfactual reasoning.

##  4 Experiments

LLM | Subject | Num Shots | Prompting | MCQ | AIA | MIA
---|---|---|---|---|---|---
GPT 4o | Reading | 0 | Simple | 95.86 | 98.23 | 82.80
0 | CoT | 95.52 | 97.88 | 68.63
LLaMA3-70B | Reading | 0 | Simple | 89.45 | 95.72 | 60.00
0 | CoT | 89.27 | 94.60 | 58.40
GPT-3.5 | Reading | 0 | Simple | 84.83 | 95.05 | 13.98
0 | CoT | 81.66 | 85.82 | 8.61
LLaMA3-8B | Reading | 0 | Simple | 73.96 | 89.62 | 19.89
0 | CoT | 78.05 | 89.52 | 15.47
GPT 4o | Math | 0 | Simple | 90.11 | 92.06 | 62.82
5 | Simple |  | 90.61 | 64.99
0 | CoT | 97.61 | 95.65 | 66.10
5 | CoT |  | 95.49 | 65.10
LLaMA3-70B | Math | 0 | Simple | 73.83 | 94.31 | 50.22
5 | Simple |  | 93.65 | 48.31
0 | CoT | 90.72 | 95.47 | 55.32
5 | CoT |  | 95.89 | 50.6
GPT 3.5 | Math | 0 | Simple | 52.85 | 77.08 | 35.8
5 | Simple |  | 76.85 | 34.61
0 | CoT | 82.53 | 86.28 | 14.74
5 | CoT |  | 81.87 | 17.06
LLaMA3-8B | Math | 0 | Simple | 45.79 | 75.29 | 34.81
5 | Simple |  | 80.32 | 38.41
0 | CoT | 70.68 | 83.07 | 27.05
5 | CoT |  | 83.05 | 31.39
Table 6: Performance results of different Large Language Models (LLMs) on the
Malgorithm Identification task, presented separately for Reading and Math
subjects. The results are organized according to the type of prompting (Simple
or CoT), and the number of shots (0 or 5). The metrics evaluated include
Multiple-Choice Question (MCQ) accuracy, Algorithm Identification Accuracy
(AIA), and Malgorithm Identification Accuracy (MIA). AIA measures the model’s
ability to identify the correct rationale or algorithm that aligns with the
given correct answer choice, whereas MIA measures the model’s ability to
identify the flawed reasoning or malgorithm that aligns with the given
incorrect answer choice. It can be observed that achieving higher scores in
MIA is generally more challenging than AIA, highlighting the complexity of
counterfactual reasoning tasks.

Subject | Grade | GPT 4o | LLaMA3-70B
---|---|---|---
Math | 3 | 67.00 | 44.26
4 | 65.93 | 54.13
5 | 66.52 | 46.97
6 | 67.80 | 58.84
7 | 64.50 | 57.49
8 | 62.96 | 42.44
11 | 53.68 | 41.03
| average | 65.10 | 50.60

Subject | Grade | GPT 4o | LLaMA3-70B
---|---|---|---
Reading | 3 | 73.81 | 65.18
4 | 68.89 | 60.71
5 | 69.47 | 45.68
6 | 58.62 | 50.00
7 | 63.46 | 80.22
8 | 80.67 | 62.00
10 | 64.96 | 46.83
| average | 68.63 | 58.40

Table 7: Grade-level performance distribution (MIA) for GPT-4o and LLaMA3-70B
models using Chain-of-Thought prompting (few-shot for Math, zero-shot for
Reading). Grades with above-average performance are underlined.

###  4.1 Experimental Setup

We conducted experiments on the Malgorithm Identification task with four
state-of-the-art LLMs: GPT-4o, GPT-3.5, LLaMA3-70B and LLaMA3-8B.111The
specific models we use are GPT-4o: gpt-4o-2024-05-13, GPT-3.5:
gpt-3.5-turbo-0125, LLaMA3-70B: Meta-LLaMA3-70B-Instruct, LLaMA3-8B: Meta-
LLaMA3-8B-Instruct To evaluate the LLMs performance, we use AIA and MIA
metrics (described in section 3.2).

For each model, we evaluated with four experimental settings: (1) Simple
prompting, where the LLMs are prompted to provide only the final answer; (2)
Chain-of-Thought (CoT) prompting, where the LLMs are prompted to provide step-
by-step reasoning and show the intermediate steps before giving the final
answer, as shown in Table 5; (3) Zero-shot learning, where the LLMs are
provided without any additional examples; (4) Few-shot learning, where the
LLMs are provided with a small number of examples demonstrating the desired
reasoning process, in addition to the standard prompts. Due to context length
constraints, we conducted few-shot experiments only on the Math dataset.

###  4.2 Effectiveness of CoT Prompting

In contrast to simple prompting strategies, Chain-of-Thought prompting
requires intermediate reasoning steps that guide the model towards the final
answer. CoT has demonstrated success in enhancing the reasoning capabilities
of language models across various tasks [27, 7]. Nevertheless, its
effectiveness in identifying flawed reasoning behind incorrect answers remain
unexplored. Our objective is to determine whether the additional reasoning
steps provided by CoT prompting could enhance the models ability to identify
malgorithms, which is crucial for assessing models’ robustness in
counterfactual reasoning and understanding student mistakes.

In Table 6, we observe that for GPT-4o, Simple prompting performs similarly to
CoT prompting in detecting malgorithms for Math (65.10 vs 64.99). However, in
Reading dataset, Simple prompting significantly outperforms CoT prompting in
identifying malgorithms (82.80 vs 68.63). In terms of AIA, CoT prompting
generally performs as well or better than Simple prompting across both
subjects.. For LLaMA3-70B, Simple prompting shows better MIA than CoT
prompting across both Math (50.6 vs 48.31) and Reading (60.0 vs 58.4), while
AIA results remain relatively comparable.

The results demonstrates that while CoT prompting could help the
identification of correct algorithms, its additional reasoning steps are not
necessarily beneficial for recognizing flawed reasoning when the given answer
choice is incorrect. One possible explanation is that the structured nature of
CoT prompting might constrain the model’s ability to explore alternative
scenarios and reason about the cause of the incorrect choice. For
counterfactual reasoning, the model needs to consider possibilities that
deviate from the correct reasoning path, and the intermediate steps in CoT
prompting may inadvertently anchor the model to a specific line of thought,
making it harder to identify the flawed reasoning behind incorrect choices.
Furthermore, the models’ training data may not have sufficient examples of
flawed reasoning patterns, making it challenging for the models to generate
appropriate intermediate reasoning steps that lead to the identification of
malgorithms, even with CoT prompting. These findings underscore the importance
of malgorithm identification, which evaluates LLMs on incorrect answer choices
to enhance their robustness in counterfactual reasoning.

###  4.3 Comparison of LLMs

Table 6 shows that malgorithm detection remains a challenging task, even for
GPT-4o. This difficulty indicates room for improvement in counterfactual
reasoning with LLMs. Although GPT-4o achieve over 95 in answering the
multiple-choice questions in MalAlgoQA, the MIA performance drops below 70.
This decline suggests that the underlying issue lies in counterfactual
reasoning capabilities of the models instead of the complexity of the
questions.

Furthermore, larger models such as GPT-4o and LLaMA3-70B significantly
outperform smaller ones in the MIA task, while in the AIA task, performance
levels are comparable across model sizes. For instance, in the Math subject
with zero-shot CoT prompting, GPT-4o scored 66.10 compared to 14.74 from
GPT-3.5, showcasing the large disparity. In contrast, for the AIA task, GPT-4o
achieved a score of 95.65 with zero-shot CoT prompting, only marginally better
than GPT-3.5’s 86.28. This suggests that the AIA task is less dependent on
model size. The MIA task, which requires models to delve deeper into the
underlying rationale of incorrect choices, showcases the emergent abilities of
large language models [26]. This indicates that counterfactual reasoning tasks
are more solvable with the enhanced capabilities of larger models.

Additionally, smaller models obtain more substantial gains with few-shot
learning, especially for the MIA performance. This result suggests that for
the task of malgorithm identification, smaller models could benefit more from
additional context.

##  5 Discussions

Figure 1: An illustration of MIA performance across different Grades and DOK
levels for Math and Reading question sets. The top number represents MIA
performance and the bottom number represents question counts. DOK I and II are
selected for Math and DOK II and III for Reading. (best viewed in colors).

##### Performance across Grade Levels

Table 7 analyzes the MIA performance of GPT-4o and LLaMA3-70B models across
different grade levels in math and reading datasets. Both models consistently
show a decline in performance with increasing grade levels, with LLaMA3-70B
exhibiting some unexpected variability, particularly excelling in Grade 8 of
the reading dataset. These results highlight the increasing challenges in
tackling malgorithm identification task as the questions becomes more
complicated.

##### Performance across DOK

Figure 1 presents a comprehensive overview of performance across DOK levels
for various Grade using MIA score from GPT 4o with CoT prompting strategy. The
pattern indicates that as the DOK level and Grade increases, MIA performance
tends to decline, especially highlighted by the comparison between the top-
left cell (dark green) and bottom-right cell (dark red). Similarly, in the
Reading dataset, performance at DOK Level III drops to 33.33 for Grade 7. This
trend further emphasizes the inherent difficulty in evaluating the malgorithms
of questions that require deeper understanding and analytical thinking.

##### Performance across Content Classifications

Figure 2 illustrates the performance of LLMs in detecting malgorithms across
five math contents and two reading content classifications. For the math
dataset, Geometry consistently yields the highest performance across all
models, suggesting that even for malgorithm identification, structural content
like Geometry is easier for LLMs to handle as compared to numerical content.
On the other hand, Probability appears to be more challenging content,
reflecting the inherent difficulty of LLMs in probabilistic reasoning. For the
reading dataset, GPT-4o and LLaMA3-70B excel at Informational Text, while
smaller models like GPT-3.5 and LLaMA3-8B perform better with Literature. This
observation suggests that larger models are better at processing structured,
factual content, whereas smaller models are more efficient with narrative,
context-rich material.

Figure 2: An illustration of MIA performance for LLMs across five math content
classifications (Number & Operation, Algebra, Geometry & Measurement, Data
Analysis, Probability) and two reading content classifications (Informational
Text, Literature).

##  6 Related Works

Counterfactual reasoning is a cognitive process that involves considering
alternative scenarios to understand causality, which has gained increasing
attentions with the advent of artificial intelligence. Pearl’s foundational
work on causal inference [12] has established a theoretical framework for
understanding counterfactuals, which has been applied to various domains,
including fairness, interpretability, and robustness in machine learning [8,
17, 24].

In the field of NLP, counterfactual reasoning is crucial for tasks that
require understanding hypothetical scenarios and the causal relationships
between events. However, most existing NLP models focus on predictive tasks
rather than for hypothetical reasoning [3, 2, 6]. While several datasets have
been created to evaluate different aspects of reasoning in language models,
relatively few focus explicitly on counterfactual reasoning. For instance, the
bAbI dataset [28] includes tasks that require basic forms of logical
reasoning, while the SQuAD dataset [15] focuses on reading comprehension.
However, these datasets do not emphasize counterfactual scenarios. Recent
efforts like the COPA dataset [16] and the CQA dataset [22] have introduced
questions that require commonsense reasoning, which often involves
understanding causal relationships. Nonetheless, these datasets are not
explicitly designed to test counterfactual reasoning. To address this gap, we
introduce MalAlgoQA, a novel dataset specifically designed to evaluate the
counterfactual causal reasoning capabilities of LLMs through a pedagogical
approach with multiple-choice question answering format.

Applications of MalAlgoQA for personalized education: The use of LLMs in
classrooms [20, 21], for instance, could profoundly influence the learning
experiences of students. While LLMs can provide personalized learning support
and instant feedback, their inability to accurately identify and address
student misconceptions, as highlighted by our study, could potentially
reinforce incorrect understanding or reasoning. However, the transparency of
LLMs’ decision-making process is a crucial ethical consideration. If LLMs are
to be trusted educational aids, it is critical for students, teachers, and
parents to understand the reasoning behind the LLMs’ responses. Our work with
the MalAlgoQA dataset is a significant step towards understanding and
addressing these ethical considerations. By examining the counterfactual
causal reasoning abilities of LLMs, we can assess their readiness for use in
educational settings and contribute to the ongoing discourse surrounding the
ethical deployment of AI in education. However, we acknowledge that this is a
complex, multifaceted issue that requires continuous exploration, vigilance,
and open dialogue among researchers, educators, policymakers, and society at
large.

##  7 Conclusion and Future Works

This paper presents MalAlgoQA, a novel dataset designed to critically evaluate
the counterfactual reasoning capabilities of LLMs through a pedagogical
prespective. Additionally, we introduce the Malgorithm Identification task
along with associated metrics for its evaluation. Our findings underscore the
need for ongoing research and development the ability to identify malgorithms,
particularly for educational applications where recognizing flawed reasoning
processes is essential. Notably, our study also challenges the efficacy of the
chain-of-thought prompting technique in enhancing counterfactual causal
reasoning, advocating for further investigation into suitable prompting
techniques for robust malgorithm identification. In the future, we plan to
expand the MalAlgoQA dataset to cover a broader range of subjects and
reasoning complexities. We also aim to explore different training
methodologies and architectural modifications to LLMs that may enhance their
ability to engage in counterfactual causal reasoning, ultimately contributing
to the development of more cognitively-aligned language models.

## Acknowledgments

This work was supported by NSF grants 1842378, ONR grant N0014-20-1-2534,
AFOSR grant FA9550-22-1-0060, and a Vannevar Bush Faculty Fellowship, ONR
grant N00014-18-1-2047.

## References

  * [1] AI@Meta.  Llama 3 model card.  2024\.
  * [2] E. M. Bender, T. Gebru, A. McMillan-Major, and M. Shmitchell.  On the dangers of stochastic parrots: Can language models be too big?  Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, pages 610–623, 2021.
  * [3] R. Bommasani, D. A. Hudson, E. Adeli, R. Altman, S. Arora, S. von Arx, M. S. Bernstein, J. Bohg, A. Bosselut, E. Brunskill, et al.  On the opportunities and risks of foundation models.  arXiv preprint arXiv:2108.07258, 2021.
  * [4] J. S. Brown and K. VanLehn.  Repair theory: A generative theory of bugs in procedural skills.  Cognitive science, 4(4):379–426, 1980.
  * [5] R. M. J. Byrne.  Counterfactual thought.  Annual Reviews, 2016.
  * [6] R. Ceraolo, D. Kharlapenko, A. Reymond, R. Mihalcea, M. Sachan, B. Schölkopf, and Z. Jin.  Causalquest: Collecting natural causal questions for ai agents.  arXiv preprint arXiv:2405.20318, 2024.
  * [7] T. Kojima, S. S. Gu, M. Reid, Y. Matsuo, and Y. Iwasawa.  Large language models are zero-shot reasoners.  Advances in neural information processing systems, 35:22199–22213, 2022.
  * [8] M. J. Kusner, J. Loftus, C. Russell, and R. Silva.  Counterfactual fairness.  In Advances in Neural Information Processing Systems, pages 4066–4076, 2017.
  * [9] N. Liu, S. Sonkar, Z. Wang, S. Woodhead, and R. G. Baraniuk.  Novice learner and expert tutor: Evaluating math reasoning abilities of large language models with misconceptions.  arXiv preprint arXiv:2310.02439, 2023.
  * [10] OpenAI.  Gpt-4 technical report, 2023.
  * [11] S. J. Payne and H. R. Squibb.  Algebra mal-rules and cognitive accounts of error.  Cognitive science, 14(3):445–481, 1990.
  * [12] J. Pearl.  Causality.  Cambridge University Press, 2009.
  * [13] J. Pearl.  The seven tools of causal inference, with reflections on machine learning.  Communications of the ACM, 62(3):54–60, 2019.
  * [14] E. Rafetseder, R. Cristi-Vargas, and J. Perner.  Counterfactual reasoning in children.  Journal of Experimental Child Psychology, 204:105054, 2021.
  * [15] P. Rajpurkar, J. Zhang, K. Lopyrev, and P. Liang.  Squad: 100,000+ questions for machine comprehension of text.  arXiv preprint arXiv:1606.05250, 2016.
  * [16] M. Roemmele, C. A. Bejan, and A. S. Gordon.  Choice of plausible alternatives: An evaluation of commonsense causal reasoning.  In 2011 AAAI Spring Symposium Series, 2011.
  * [17] S. Russell and P. Norvig.  Evidence, decision, and causality.  Artificial Intelligence: A modern approach, pages 645–658, 2018.
  * [18] J. Schulman, B. Zoph, C. Kim, J. Hilton, J. Menick, J. Weng, J. Uribe, L. Fedus, L. Metz, M. Pokorny, et al.  Chatgpt: Optimizing language models for dialogue, 2022.
  * [19] S. Sonkar and R. G. Baraniuk.  Deduction under perturbed evidence: Probing student simulation (knowledge tracing) capabilities of large language models.  In LLM@ AIED, pages 26–33, 2023.
  * [20] S. Sonkar, X. Chen, M. Le, N. Liu, D. Basu Mallick, and R. Baraniuk.  Code soliloquies for accurate calculations in large language models.  In Proceedings of the 14th Learning Analytics and Knowledge Conference, pages 828–835, 2024.
  * [21] S. Sonkar, N. Liu, D. Mallick, and R. Baraniuk.  CLASS: A Design Framework for Building Intelligent Tutoring Systems Based on Learning Science principles.  In Findings of the Association for Computational Linguistics: EMNLP 2023, pages 1941–1961, Singapore, Dec. 2023.
  * [22] A. Talmor, J. Herzig, N. Lourie, and J. Berant.  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, pages 4149–4158, 2019.
  * [23] K. VanLehn.  Mind bugs: The origins of procedural misconceptions.  MIT press, 1990.
  * [24] S. Wachter, B. Mittelstadt, and C. Russell.  Counterfactual explanations without opening the black box: Automated decisions and the gdpr.  Harvard Journal of Law & Technology, 31(2):841–887, 2018.
  * [25] N. L. Webb.  Depth-of-knowledge levels for four content areas.  https://ossucurr.pbworks.com/w/file/fetch/49691156/Norm%20web%20dok%20by%20subject%20area.pdf, 2002.  Accessed: 2023-06-14.
  * [26] J. Wei, Y. Tay, R. Bommasani, C. Raffel, B. Zoph, S. Borgeaud, D. Yogatama, M. Bosma, D. Zhou, D. Metzler, et al.  Emergent abilities of large language models.  arXiv preprint arXiv:2206.07682, 2022.
  * [27] J. Wei, X. Wang, D. Schuurmans, M. Bosma, F. Xia, E. Chi, Q. V. Le, D. Zhou, et al.  Chain-of-thought prompting elicits reasoning in large language models.  Advances in neural information processing systems, 35:24824–24837, 2022.
  * [28] J. Weston, A. Bordes, S. Chopra, and T. Mikolov.  Towards ai-complete question answering: A set of prerequisite toy tasks.  In arXiv preprint arXiv:1502.05698, 2015.

##  Appendix A Additional Analysis

###  A.1 Grade vs DOK for different content classifications

Figure 3: An image of MIA performance across different Grades and DOK levels
for various Content Classifications for Math question sets. The top number
represents MIA performance and the bottom number represents question counts.
The data analysis and probability classifications are combined together for
illustration. (best viewed in colors).

Figure 4: An image of MIA performance across different Grades and DOK levels
for two Content Classifications for Reading question sets. The top number
represents MIA performance and the bottom number represents question counts
(best viewed in colors).

Figures 3 and 4 illustrate the relationships between grade levels, DOK for
different content classifications in math and reading question sets. In
mathematics, Number & Operation and Algebra questions demonstrate relatively
consistent performance, with higher DOK levels often showing better results.
For instance, MIA performance for Number & Operation peaks in lower grades and
declines in higher grades, particularly Grade 7. This trend suggests
increasing complexity in numerical operations as grade levels increases. On
the other hand, Geometry & Measurements, Data Analysis and Probability exhibit
high variability, with strong MIA performance in some grades but gaps in
others. In reading, performance for Informational Text is generally consistent
across grades, peaking in Grade 8, with lower DOK levels typically yielding
higher MIA performance. Literature shows high variability, reflecting the
varying complexity of literary analysis tasks. Notably, content
classifications in mathematics show more consistent patterns across grades
compared to reading ones.

###  A.2 Performance across Grade level and Content Classifications

Figure 5: An illustration of MIA performance across different Grades and
Content Classifications for Math and Reading question sets. The top number
represents MIA performance and the bottom number represents question counts
(best viewed in colors).

Figure 5 shows the relationship between grade levels and content
classifications for math and reading question sets. In mathematics question
set, Algebra demonstrates relatively consistent performance across all grades,
with the number of algebra questions increasing significantly in higher
grades, peaking at 191 data points in Grade 8. Number & Operation exhibits a
gradual decline in MIA performance from lower to higher grades. In contrast,
Data Analysis and Probability, Geometry & Measurement classifications show
varied MIA performance across grade levels. For instance, Data Analysis and
Probability demonstrates exceptionally high performance in Grade 6 (81.82),
albeit with relatively few data points (22). In reading question set, MIA
performance for both Informational Text and Literature classifications
fluctuates across grades without much correlation. Informational Text achieves
a significant peak in MIA performance for Grade 8, while Literature questions
in Grade 5 demonstrate exceptionally high performance. This variability could
be attributed to differences in text complexity or question difficulty at
different grade levels for the Malgorithm Identification problem.

###  A.3 Performance across Questions

Figure 6: The distribution of GPT4-o performance in identifying malgorithms
across question levels for math and reading question sets. The x-axis
represents the number of correctly identified malgorithms per question,
ranging from 0 to 3.

We can find the performance of LLMs in identifying malgorithms across each
question in both mathematics and reading comprehension sets in Figure 6. The
number of questions increases as we progress from 0 to 3 correctly identified
malgorithms per question. This pattern suggests that LLMs are more likely to
identify multiple malgorithms correctly rather than missing all or most of
them. However, despite this positive trend, it is crucial to note that LLMs’
overall performance on this task remains suboptimal. The presence of the
significant number of questions at the 0 and 1 levels across both domains
indicates room for improvement. In mathematics, the combined number of
questions with 0 or 1 correctly identified malgorithms is comparable to those
with 3 correct identifications. Similarly, in reading comprehension, while
there is a clearer upward trend, the number of questions with 0 or 1 correct
identifications remains considerable. These findings underscore the need for
further research of LLMs’ counterfactual reasoning capabilities in malgorithm
identification across various question types and subject areas.

##  Appendix B Examples of Mathematics dataset

We provide five examples, one per content classifications, of question,
choices and their corresponding rationales in Table 8 and 9.

⬇

Math Question Set Example 1:

Content Classification: Number & Operation

Question: What number is subtracted from 1,000 to result in a difference of
421?

Answer and Rationales:

A: 421

Rationale A: Selects the result of subtraction.

B: 579

Rationale B: 1000 - 421 = 579

C: 621

Rationale C: Rounded the hundreds place and added the tens and ones place.
1000 - 400 = 600; 600 + 21 = 621

D: 689

Rationale D: Rounded in hundreds, tens and ones place. 1000 - 400 = 600; 100 -
20 = 80; 10 - 1 = 9; 600 + 80 + 9 = 689

Math Question Set Example 2:

Content Classification: Algebra

Question: Anne bought a calculator that cost 30. She received 10% off her
purchase and then was charged 6% tax. What was the total amount that Anne
paid?

Answer and Rationales:

A: 21.20

Rationale A: Subtracted 10 from 30, then added 6%.

B: 25.38

Rationale B: Subtracted 10% of the price from 30 then subtracted 6%.

C: 28.62

Rationale C: Subtracted 10% of the price from 30 and then added 6%.

D: 28.80

Rationale D: Calculated tax based on original price, then subtracted the 3.

Math Question Set Example 3:

Content Classification: Geometry and Measurement

Question: Which side lengths form a right triangle?

Answer and Rationales:

A: 2 cm, 4 cm, 8 cm

Rationale A: Multiplied the 2 smaller sides to get the longest side.

B: 4 cm, 5 cm, 6 cm

Rationale B: Selected side with constant difference between the sides.

C: 5 cm, 12 cm, 13 cm

Rationale C: 5^2 + 12^2 = 13^2

D: 9 cm, 16 cm, 25 cm

Rationale D: Added the 2 smaller sides to get the longest side.

Table 8: Examples of Mathematics question set.

⬇

Math Question Set Example 4:

Content Classification: Data Analysis

Question: Mrs. Castillo recorded the number of students in each grade 5
classroom.

24 28 25 24 29

What is the mean of the data?

Answer and Rationales:

A: 24

Rationale A: Chose the mode.

B: 25

Rationale B: Chose the median. {24, 24, 25, 28, 29}

C: 26

Rationale C: (24 + 28 + 25 + 24 + 29) / 5 = 130/5 = 26

D: 29

Rationale D: Chose the greatest number.

Math Question Set Example 5:

Content Classification: Probability

Question: Ms. Collier had a deck of cards. There were stars on 1/4 of the
cards in the deck. After randomly picking a card and returning it to the deck
100 times, the expected result and relative frequency of picking a card with a
star were equal. In the first 50 cards she picked, she got a star 10 times.
How many times did Ms. Collier get a star in the second 50 cards she picked?

Answer and Rationales:

A: 10

Rationale A: Chose the number of times a star is picked in the 1st 50 cards
drawn.

B: 13

Rationale B: Calculated 50 * 1/4 = 12.5 and then rounded to 13.

C: 15

Rationale C: Correct. 100 * 1/4 = 25 cards w/ stars. 25 - 10 = 15

D: 25

Rationale D: Calculated 100 * 1/4 = 25 cards w/ stars.

Table 9: Examples of Mathematics question set.

##  Appendix C Examples of Reading Comprehension dataset

We provide two examples of passage, question, choices and their corresponding
rationales in Table 10 and 11.

⬇

Reading Question Set Example 1:

Content Classification: Literature

Passage: Blueberries

1 You ought to have seen what I saw on my way

2 To the village, through Patterson’s pasture to-day:

3 Blueberries as big as the end of your thumb,

4 Real sky-blue, and heavy, and ready to drum

5 In the cavernous pail of the first one to come!

6 And all ripe together, not some of them green

7 And some of them ripe! You ought to have seen!

...

Question: In lines 1-7, the speaker expresses great surprise about the ...?

Answer and Rationales:

A: large pails of blueberries.

Rationale A: Some readers might find this option plausible because the speaker
mentions the “cavernous pail of the first one to come" (line 5). However, this
mention of the pail is referring to the pail into which the lucky picker who
first stumbles across this crop will put the “Blueberries as big as the end of
your thumb" (line 3). The speaker does not express surprise that pickers are
bringing large pails.

B: number of blueberry pickers.

Rationale B: Some readers might choose this option because the phrase “the
first one to come" in line 5 refers to a blueberry picker. However, although
the speaker is predicting success for anyone who comes to pick the
blueberries, the speaker is not expressing surprise that there are no pickers
yet. Based on the speaker’s description of how big, blue, and ripe the berries
are (“as big as the end of your thumb, Real sky-blue, and heavy, and ready"
(lines 3 and 4)), the berries are undisturbed, and no one has discovered them
except for the speaker.

C: ripeness of the blueberries.

Rationale C: The speaker describes “big as the end of your thumb" (line 3)
blueberries that are “Real sky-blue, and heavy," (line 4) and “all ripe
together" (line 6). The speaker repeats, “You ought to have seen" in lines 1
and 7 to convey surprise.

D: size of new blueberry bushes.

Rationale D: This option might seem plausible because the size of the
blueberries and their bushes are described. The first speaker draws attention
to size when describing the blueberries as “big as the end of your thumb"
(line 3). In line 13, the second speaker exclaims, “Why, there hasn’t been
time for the bushes to grow." This line implies that the bushes must be small,
so it is surprising that the blueberries they produce are numerous and “as big
as the end of your thumb." Although lines 1-7 address the blueberries, the
speaker does not mention the bushes on which they grow in those lines.

Table 10: Example 1 of Reading question set.

⬇

Reading Question Set Example 2:

Content Classification: Informational Text

Passage: Creating Codes: Grace Hopper and the Computer Compiler

1 The computer screen freezes. No matter what or how often you click, the
hourglass or rotating circle (that symbol that insists, “I’m working on it!")
spins away. You want to shake the screen. Someone next to you says, “I think
you found a bug."

...

Question: What is the main purpose of paragraph 1?

Answer and Rationales:

A: To demonstrate the importance of the subject

Rationale A: Although some readers may conclude that the frozen computer
screen in paragraph 1 demonstrates how important computer programming is
currently, the paragraph describes a familiar feeling of frustration rather
than detailing the more serious consequences that could result from
programming mistakes.

B: To help readers make a connection with the topic

Rationale B: The paragraph describes a person facing a frozen computer screen
that many readers have probably experienced in order to help readers make a
personal connection to the topic. By describing this common situation, the
reader’s interest is engaged. So, when the article continues on to discuss
Hopper’s contribution to programming and how she helped solve some of the
early computer bugs, readers feel more connected with the topic.

C: To give background information about the subject

Rationale C: Although introductions often provide background information, and
some readers may conclude that explaining a computer bug is background
information for the article, the topic of the article focuses not on computer
bugs but on Hopper’s contributions to computer programming.

D: To provide readers with a brief summary of the topic

Rationale D: Although the main topic of the article is Hopper’s contribution
to computer programming and paragraph 1 mentions computers, paragraph 1
describes a common situation in order to raise interest among readers. It
describes a person having computer problems rather than summarizing Hopper’s
contributions to computer programming.

Table 11: Example 2 of Reading question set


# A Note on the LogRank Conjecture in Communication Complexity

Vince Grolmusz<EMAIL_ADDRESS>Eötvös University, H-1117 Budapest,
Hungary

###### Abstract

The LogRank conjecture of Lovász and Saks from 1988 is the most famous open
problem in the communication complexity theory. The statement is as follows:
Suppose that two players intend to compute a Boolean function $f(x,y)$ when
$x$ is known for the first and $y$ for the second player, and they may send
and receive messages encoded with bits, then they can compute $f(x,y)$ with
exchanging $(\log\hbox{\rm rank}(M_{f}))^{c}$ bits, where $M_{f}$ is a Boolean
matrix, determined by function $f$. The problem is widely open and very
popular, and it has resisted numerous attacks in the last 35 years. The best
upper bound is still exponential in the bound of the conjecture.
Unfortunately, we cannot prove the conjecture, but we present a communication
protocol with $(\log\hbox{\rm rank}(M_{f}))^{c}$ bits, which computes a –
somewhat – related quantity to $f(x,y)$. The relation is characterized by a
representation of low-rank, multi-linear polynomials modulo composite numbers.
This result of ours may help to settle this long-time open conjecture.

##  1 Introduction

###  1.1 Communication Games

Two-player communication games were first defined by Yao in 1979 [1]: There
are two players, Alice and Bob, and a Boolean function

$f:\\{0,1\\}^{N}\times\\{0,1\\}^{N}\to\\{0,1\\},$

and two Boolean sequences, $x,y\in\\{0,1\\}^{N}$. Alice knows the value of
$x$, Bob the value of $y$, and they want to compute collaboratively the value
of $f(x,y)$. The local computational power of the players are unlimited, and
the cost of the collaborative computation is the number of bits exchanged
between the parties. Function $f$ is computed by the players if one of them
knows $f(x,y)$, and the other knows that the first player knows [2].

Clearly, any $f$ can be computed by $N$ bits of communication: Alice tells $x$
to Bob at cost $N$, and Bob computes $f(x,y)$ for free. This is the trivial
protocol for computing $f$.

We say that the players follow a communication protocol for computing $f$,
where the protocol prescribes that in each step, what message a player should
send to the other for a given message history and input. The cost of a
protocol, computing $f(x,y)$, is the maximum number of bits communicated,
taken for all $x$ and $y$ inputs.

The communication complexity of Boolean function $f$ is the minimum cost of
protocols, which compute $f$. The communication complexity of $f$ is denoted
by $\kappa(f)$ [2]. For a more formal introduction and examples, we refer to
[2, 3].

The communication games and communication complexity have become a central
field of theoretical computer science, hundreds of publications (e.g., [4, 5,
6, 7, 8] and numerous books [3, 9, 10] have been appeared on the topic. For
example, difficult-to-handle areas, such as Boolean circuit complexity,
applied communication games for gaining upper- and lower bounds [11, 12, 13,
14, 15, 16, 17, 10, 18].

One of the main questions is finding general upper- and lower bounds for the
communication complexity of $f$. To describe the bounds, we need to define the
communication matrix of the function $f$:

######  Definition 1.

The communication matrix of $f:\\{0,1\\}^{N}\times\\{0,1\\}^{N}\to\\{0,1\\}$
is a $2^{N}\times 2^{N}$ 0-1 matrix $M_{f}$, where its rows corresponds to the
different $x\in\\{0,1\\}^{N}$ values, the columns to the different
$y\in\\{0,1\\}^{N}$ values, and in the position of row $x$ and column $y$ is
the value of $f(x,y)\in\\{0,1\\}$. Let $\hbox{\rm rank}(M_{f})$ denote the
matrix rank over the rational field. Let $\log$ denote the logarithm base 2,
and $\ln$ the natural logarithm.

A general lower bound, which implies that for most of the natural
communications problems (e.g., the identity function or the set disjointness)
the trivial protocol is optimal, was proved by Mehlhorn and Schmidt in 1982:

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

$\kappa(f)\geq\log\hbox{\rm rank}(M_{f}).$

The most famous open problem in communication complexity is the LogRank
conjecture of Lovász and Saks from 1988:

######  Conjecture 2 ([20]).

There exists a constant $c>0$, such that

$\kappa(f)\leq(\log\hbox{\rm rank}(M_{f}))^{c}.$

The 35-year-old conjecture is widely open today, inspiring numerous theorems
and approaches even in the last few years [21, 22, 23, 24, 25, 26, 27].

The best published upper bound of Lovett [8] is still exponentially far from
the conjectured upper bound:

$\kappa(f)=O\left(\sqrt{\hbox{\rm rank}(M_{f})}\log\hbox{\rm
rank}{M_{f}}\right).$

We note that the LogRank conjecture can be formulated with the terms of graph
theory as a relation between the rank of the adjacency matrix and the
chromatic number of a graph [20, 8], without even mentioning communication
games.

###  1.2 Polynomial representations modulo composite numbers

We will need some definitions and theorems from [28, 29]:

Let $g:\\{0,1\\}^{n}\to\\{0,1\\}$ be a Boolean function and let $m$ be a
positive integer. Barrington, Beigel and Rudich [30] gave the following
definition:

######  Definition 2.

The polynomial $P$ with integer coefficients weakly represents Boolean
function $g$ modulo $m$ if there exists an $S\subset\\{0,1,2,...,m-1\\}$ such
that for all $x\in\\{0,1\\}^{n}$,

$g(x)=0\Longleftrightarrow\big{(}P(x)\bmod{m}\big{)}\in S.$

Here $(a\bmod{m})$ denotes the smallest non-negative $b\equiv a\bmod{m}$.

We are interested in the smallest degree polynomials representing $g$. Since
$g$ is Boolean, we may assume that $P$ is multilinear (since $x_{i}^{2}=x_{i}$
over $\\{0,1\\}^{n}$).

Let $\hbox{OR}_{n}:\\{0,1\\}^{n}\to\\{0,1\\}$ denote the $n$–variable OR-
function:

$\hbox{OR}_{n}(x_{1},x_{2},\ldots,x_{n})=\cases{0,\hbox{ if
}x_{1}=x_{2}=\cdots=x_{n}=0\cr 1\hbox{ otherwise.}}$

If polynomial $P$ weakly represents ORn modulo a prime $p$ then we may assume
that for $x\in\\{0,1\\}^{n}$,

$P(x)=0\bmod{p}\iff x=(0,0,...,0).$

Then

$1-P^{p-1}(1-x_{1},1-x_{2},...,1-x_{n})$

is clearly the $n$-variable AND function with a unique multi-linear form

$x_{1}x_{2}x_{3}...x_{n}.$

Therefore, the degree of $P$ is at least $n/(p-1)$.

Tardos and Barrington [31] showed that the same conclusion holds if $p$ is a
prime power.

However, Barrington, Beigel and Rudich [30] proved that the conclusion fails
for composite moduli with at least two prime divisors:

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

There exists an explicitly constructible polynomial $P$ of degree $O(n^{1/r})$
which weakly represents $OR_{n}$ modulo
$m=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}...p_{r}^{\alpha_{r}}$, where the
$p_{i}$’s are distinct primes.

An explicit example of such a non-trivial polynomial mod 6 is given in the
Appendix.

We have applied the polynomial of Theorem 3 in [32] for falsifying a long-
standing conjecture for the size of set systems with restricted intersections
and also for giving new explicit Ramsey-graph constructions, among other
applications for set systems and codes described in [33, 34, 35, 36, 37, 38].

In [32] we have reproduced a short proof of Theorem 3 of [30], and we have
proved the following

######  Corollary 4.

Let $m=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}...p_{r}^{\alpha_{r}}$. Then there
exists an explicitly constructible polynomial $P^{\prime}$ with $n$ variables
and of degree $O(n^{1/r})$ which is equal to 0 on
$x=(0,0,\ldots,0)\in\\{0,1\\}^{n}$, it is nonzero mod $m$ for all other
$x\in\\{0,1\\}^{n}$, and for all $x\in\\{0,1\\}^{n}$ and for all
$i\in\\{1,\ldots,r\\}$, $P(x)\equiv 0\pmod{p_{i}^{\alpha_{i}}}$ or $P(x)\equiv
1\pmod{p_{i}^{\alpha_{i}}}$.

Using the results of [32], we have found a remarkable application for
elementary symmetric polynomials in [28].

We will need the following definition from [29] with small changes to describe
the result:

######  Definition 3.

Let $m$ be a composite number with prime-factorization
$m=p_{1}^{e_{1}}p_{2}^{e_{2}}\cdots p_{\ell}^{e_{\ell}}$. Let $\mathbb{Z}_{m}$
denote the ring of integers modulo $m$ and $\mathbb{Z}$ the integers. Let $f$
be a multi-linear polynomial of $n$ variables over the integers:

$f(x_{1},x_{2},\ldots,x_{n})=\sum_{\alpha\in\\{0,1\\}^{n}}a_{\alpha}x^{\alpha},$

where $a_{\alpha}\in\mathbb{Z}$,
$x^{\alpha}=\prod_{i=1}^{n}x_{i}^{\alpha_{i}}$. Then we say that

$g(x_{1},x_{2},\ldots,x_{n})=\sum_{\alpha\in\\{0,1\\}^{n}}b_{\alpha}x^{\alpha},$

is an

  * 1.

alternative representation of $f$ modulo $m$, if

$\forall\alpha\in\\{0,1\\}^{n}\ \ \exists j\in\\{1,2,\ldots,\ell\\}:$
$a_{\alpha}\equiv b_{\alpha}\pmod{p_{j}^{e_{j}}};$

  * 2.

0-a-strong representation of $f$ modulo $m$, if it is an alternative
representation, and furthermore, if for some $i$, $a_{\alpha}\not\equiv
b_{\alpha}\pmod{p_{i}^{e_{i}}},$ then $b_{\alpha}\equiv
0\pmod{p_{i}^{e_{i}}};$

  * 3.

1-a-strong representation of $f$ modulo $m$, if it is an alternative
representation, and furthermore, if for some $i$, $a_{\alpha}\not\equiv
b_{\alpha}\pmod{p_{i}^{e_{i}}},$ then $a_{\alpha}\equiv 0\pmod{m};$

That is for modulus 6; in the alternative representation, each coefficient is
correct, either modulo 2 or modulo 3, but not necessarily both.

In the 0-a-strong representation, the 0 coefficients are always correct both
modulo 2 and 3; the non-zeroes are allowed to be correct either modulo 2 or 3,
and if they are not correct modulo one of them, say 2, then they should be 0
mod 2. Consequently, the coefficient 1 can be represented by 1, 3, or 4, but
nothing else.

In the 1-a-strong representation, the non-zero coefficients of $f$ are correct
for both moduli in $g$, but the zero coefficients of $f$ can be non-zero
either modulo 2 or modulo 3 in $g$, but not both.

######  Remark 5 ([29]).

The 1-a-strong representations of polynomial $f$ can be written in the form
modulo $m$:

$f+p_{1}^{e_{1}}g_{1}+p_{2}^{e_{2}}g_{2}+\cdots+p_{\ell}^{e_{\ell}}g_{\ell},$

where the $g_{i}$ have no monomials in common with each other, nor with $f$.

######  Example 6 ([29]).

Let $m=6$, and let $f(x_{1},x_{2},x_{3})=x_{1}x_{2}+x_{2}x_{3}+x_{1}x_{3}$,
then $g(x_{1},x_{2},,x_{3})=3x_{1}x_{2}+4x_{2}x_{3}+x_{1}x_{3}$ is a
0-a-strong representation of $f$ modulo 6;
$g(x_{1},x_{2},,x_{3})=x_{1}x_{2}+x_{2}x_{3}+x_{1}x_{3}+3x_{1}^{2}+4x_{2}$ is
a 1-a-strong representation of $f$ modulo 6;
$g(x_{1},x_{2},,x_{3})=3x_{1}x_{2}+4x_{2}x_{3}+x_{1}x_{3}+3x_{1}^{2}+4x_{2}$
is an alternative representation modulo 6.

######  Remark 7.

Clearly, the 1-a-strong representation of $f$ is not unique. Suppose that

  * (i)

all coefficients of $f$ and $f^{\prime}$ are either 1 or -1 mod $m$, and

  * (ii)

$g$ is a 1-a-strong representation of $f$ and also of $f^{\prime}$, where
$f,f^{\prime}$ and $g$ are multilinear, homogeneous degree-$d$ polynomials,
that is, every monomials of $f,f^{\prime}$ and $g$ are degree $d$,

then $f=f^{\prime}$ modulo $m$. Clearly, one can set the monomials of $f$ or
$f^{\prime}$ to 1 one by one, and the $p_{i}$-multiplied monomials need to be
0 in $g$ because of homogeneity.

We have proved in [28] and stated in this form in [29] the following

######  Theorem 8 ([28]).

Let the prime factorization of positive integer $m$ be
$m=p_{1}^{e_{1}}p_{2}^{e_{2}}\cdots p_{\ell}^{e_{\ell}}$, where $\ell>1$. Then
a degree-2 0-a-strong representation of the second elementary symmetric
polynomial

$S_{n}^{2}(x,y)=\sum_{i,j\in\\{1,2,\ldots,n\\}\atop{i\neq j}}x_{i}y_{j},$
$None$

modulo $m$:

$\sum_{i,j\in\\{1,2,\ldots,n\\}\atop{i\neq j}}a_{ij}x_{i}y_{j}$ $None$

can be computed as the following product with coefficients from
$\mathbb{Z}_{m}$:

$\sum_{j=1}^{t}\left(\sum_{i=1}^{n}b^{\prime}_{ij}x_{i}\right)\left(\sum_{i=1}^{n}c^{\prime}_{ij}y_{i}\right)$

where $t=\exp(O(\sqrt[\ell]{\log n(\log\log n)^{\ell-1}})).$ Moreover, this
representation satisfies that $\forall i\neq j:a_{ij}=a_{ji}$.

∎

Now we need the main theorem from [29]:

######  Theorem 9 ([29], Theorem 6).

Let $m=p_{1}^{e_{1}}p_{2}^{e_{2}}\cdots p_{\ell}^{e_{\ell}}$, where $\ell>1$,
and $p_{1},p_{2},\ldots,p_{\ell}$ are primes. Then a degree-2, 1-a-strong
representation of the dot-product
$f(x_{1},x_{2},\ldots,x_{n},y_{1},y_{2},\ldots,y_{n})=\sum_{i=1}^{n}x_{i}y_{i}$
can be computed with $t+1=\exp(O(\sqrt[\ell]{\log n(\log\log n)^{\ell-1}}))$
multiplications of the form

$\sum_{j=1}^{t+1}\left(\sum_{i=1}^{n}b_{ij}x_{i}\right)\left(\sum_{i=1}^{n}c_{ij}y_{i}\right),$
$None$

where all coefficients are integers.

The proof is immediate by subtracting the 0-a-strong representation of
$S_{n}^{2}(x,y)$ from $(x_{1}+x_{2}+\ldots+x_{n})(y_{1}+y_{2}+\ldots+y_{n})$
[29].

An explicit example for the $b_{ij}$ and $c_{i}j$ coefficients, with
$m=6,n=16,t+1=13$ can be found in the Appendix.

##  2 The LogRank Protocol

Here, we describe our protocol. Let $m=p_{1}p_{2}\ldots p_{\ell}$ be the
product of the first $\ell$ primes. Then $m=e^{(1+o(1))\ell\ln\ell}$, by the
estimation of the first Chebyshev number [39]. Let $\ell=\lfloor\log\log
n\rfloor$. Then $m$ can be given with less than $(\log\log n)^{c}$ bits, with
a $0<c$.

The value $t$ satisfies

$t\leq\exp(O((\log n)^{1/\ell}\log\log n))\leq\exp(c_{1}\log\log n)\leq(\log
n)^{c_{1}},$

with a positive $c_{1}$.

Now suppose that we have a Boolean function
$F:\\{0,1\\}^{N}\times\\{0,1\\}^{N}\to\\{0,1\\}$, with a 0-1 communication
matrix $M_{F}$ with $\hbox{\rm rank}(M_{F})=n$ over the rationals, $n\leq N$.
By the definition of the rank, one may choose $n$ linearly independent 0-1
columns of $M_{F}$, let the $N\times n$ 0-1 matrix $X$ contain these columns.
Then there exists an $n\times N$ rational matrix $Y$, such that $M_{F}=XY$.

Note that each entry of $M_{F}$ is a dot product of a length-$n$ row of $X$
and a length-$n$ column of $Y$. Now, by Theorem 9, the 1-a-strong
representation of this dot product can be computed modulo $m$ as a sum (3):

$\sum_{j=1}^{t+1}\left(\sum_{i=1}^{n}b_{ij}x_{i}\right)\left(\sum_{i=1}^{n}c_{ij}y_{i}\right),$

where all coefficients are integers modulo $m$. Now, Alice can compute
privately for $j=1,2,\ldots t+1$ the mod $m$ values of sums

$\left(\sum_{i=1}^{n}b_{ij}x_{i}\right)$

and can communicate each with $(\log\log n)^{c}$ bits. Since $t<(\log
n)^{c_{1}}$, the total communication of Alice is polylogarithmic in the rank
$n$.

Now, Bob, knowing the values of $y_{1},y_{2},\ldots,y_{n}$ can privately
compute the sum (3), without further communication.

##  3 Remarks and Conclusion

In the previous section we have presented a protocol, which computed a value
with $(\log\hbox{\rm rank}(M_{F}))^{c_{2}}$ communication, with a positive
constant $c_{2}$ which is substituted in the 1-a-strong representation $g$
modulo $m=p_{1}p_{2}\ldots p_{\ell}$ of the dot-product polynomial
$f=\sum_{i=1}^{n}x_{i}y_{i}$:

$g(x,y)=\sum_{i=1}^{n}x_{i}y_{i}+p_{1}g_{1}(x,y)+p_{2}g_{2}(x,y)+\ldots+p_{\ell}g_{\ell}(x,y).$
$None$

Note that the ”surplus” terms in (4) are zero modulo for at least one of the
prime divisors of $m$. Note also that there is no common monomial (i.e.,
$x_{i}y_{j}$) in the dot-product and among the $g_{i}$ polynomials.

######  Remark 10.

We do not know how to eliminate the surplus terms with the $g_{i}$ polynomials
from $(4)$ with a log-rank bounded additional communication. One can imagine
numerous possible approaches, for example, substituting a prime $p_{i},1\leq
i\leq\ell$ for all or just a subset of 1’s in the $x_{i}$’s, and repeating the
protocol; or repeating the protocol above for 0-1 rows instead of 0-1 columns,
or repeating the protocol above for overlaying subsets of indices
$i=1,2,\ldots,n$ several times.

######  Remark 11.

As we described in [29], Theorem 9 has numerous applications in representing
the matrix product with very few multiplications or the hyperdense coding of
numbers, vectors or matrices. We also note that our definition and use of the
term ”hyperdense coding” [40] precede the quantum-computational use of an
unrelated but identically named term of [41, 42] by more than 9 years.

## Funding

VG was partially funded by the Ministry of Innovation and Technology of
Hungary from the National Research, Development and Innovation Fund, financed
under the ELTE TKP 2021-NKTA-62 funding scheme.

## Competing interests

The author declares no competing interests.

## References

  * Yao [1979] Andrew C. Yao.  Some complexity questions related to distributed computing.  In _Proc. 11th Ann. ACM Symp. Theor. Comput._ , pages 209–213, 1979.
  * Lovász [1989] László Lovász.  Communication complexity: a survey.  In B. Korte, L. Lovász, H.J. Prömel, and A. Schrijver, editors, _Paths, Flows, and VLSI-Layout_ , pages 235–265. Springer, 1989\.
  * Kushilevitz and Nisan [1997] Eyal Kushilevitz and Noam Nisan.  _Communication Complexity_.  Cambridge University Press, 1997.
  * Nisan [1993] Noam Nisan.  The communication complexity of threshold gates.  In V.T. Sós D. Miklós and T. Szőnyi, editors, _Combinatorics, Paul Erdős is Eighty, Volume I._ , pages 301–315. János Bolyai Mathematical Society, Budapest, 1993.
  * Nisan and Wigderson [1994] Noam Nisan and Avi Wigderson.  On rank vs. communication complexity.  In _Proc. 35th Ann. IEEE Symp. Found. Comput. Sci._ , pages 831–836, 1994.
  * Babai et al. [1992] László Babai, Noam Nisan, and Márió Szegedy.  Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs.  _J. Comput. System Sci._ , 45:204–232, 1992.
  * Grolmusz [1994] Vince Grolmusz.  The BNS lower bound for multi-party protocols is nearly optimal.  _Inform. and Comput._ , 112(1):51–54, 1994.
  * [8] Shachar Lovett.  Communication is bounded by root of rank.  _J. ACM_ , 63(1):1–9.  URL https://doi.org/10.1145/2724704.
  * Rao and Yehudayoff [2020] Anup Rao and Amir Yehudayoff.  _Communication Complexity_.  Cambridge University Press, 2020.  doi: 10.1017/9781108671644.
  * Karchmer [1989] Mauricio Karchmer.  _Communication complexity_.  ACM doctoral dissertation award. MIT Press, 1989.  ISBN 9780262111430.
  * Håstad and Goldmann [1991] Johan Håstad and Mikael Goldmann.  On the power of the small-depth threshold circuits.  _Comput. Complexity_ , 1:113–129, 1991.
  * Grolmusz [1998a] Vince Grolmusz.  A lower bound for depth-3 circuits with mod m gates.  _Inform. Proc. Lett._ , 67:87–90, 1998a.
  * Grolmusz [1998b] Vince Grolmusz.  A degree-decreasing lemma for (mod q,mod p) circuits.  In _Proc. ICALP’98, Aalborg, Denmark, LNCS 1443_ , pages 215–222, 1998b.
  * Grolmusz [1995a] Vince Grolmusz.  Separating the communication complexities of MOD m and MOD p circuits.  _J. Comput. System Sci._ , 51(2):307–313, 1995a.  also in Proc. 33rd Ann. IEEE Symp. Found. Comput. Sci., 1992, pp. 278–287.
  * Grolmusz [1995b] Vince Grolmusz.  On the weak $\mathop{\bmod}m$ representation of Boolean functions.  _Chicago Journal of Theoretical Computer Science_ , 1995(2), July 1995b.
  * Grolmusz and Tardos [2000] Vince Grolmusz and Gábor Tardos.  Lower bounds for (MOD p-MOD m) circuits.  _SIAM Journal on Computing_ , 29(4):1209–1222, 2000.  also appeared in 39th IEEE FOCS, pp. 279-289.
  * Grolmusz [1999] Vince Grolmusz.  Harmonic analysis, real approximation, and the communication complexity of Boolean functions.  _Algorithmica_ , 23(4):341–353, 1999.
  * Karchmer et al. [1994] Mauricio Karchmer, Ilan Newman, Michael E. Saks, and Avi Wigderson.  Non-deterministic communication complexity with few witness.  _Journal of Computer and System Sciences_ , 49:247–257, 1994.  URL https://doi.org/10.1016/S0022-0000(05)80049-2.
  * Mehlhorn and Schmidt [1982] Kurt Mehlhorn and E.M. Schmidt.  Las Vegas is better than determinism in VLSI and distributive computing.  In _Proc. 14th Ann. ACM Symp. Theor. Comput._ , pages 330–337, 1982.
  * Lovász and Saks [1988] László Lovász and Michael Saks.  Lattices, Möbius functions, and communication complexity.  In _Proc. 29th Ann. IEEE Symp. Found. Comput. Sci._ , pages 81–90, 1988.
  * [21] Noah Singer and Madhu Sudan.  Point-hyperplane incidence geometry and the log-rank conjecture.  _ACM Transactions on Computation Theory_ , 14(2):1–16.  doi: 10.1145/3543684.
  * [22] Hsin-Lung Wu.  On the communication complexity of AND functions.  _IEEE Transactions on Information Theory_ , 67(7):4929–4935.  doi: 10.1109/tit.2021.3052836.
  * [23] Anna Gál and Ridwan Syed.  Upper bounds on communication in terms of approximate rank.  In _Computer Science – Theory and Applications_ , pages 116–130. Springer International Publishing.  doi: 10.1007/978-3-030-79416-3˙7.
  * [24] Alexander Knop, Shachar Lovett, Sam McGuire, and Weiqiang Yuan.  Log-rank and lifting for AND-functions.  In _Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing_. ACM.  doi: 10.1145/3406325.3450999.
  * [25] Arkadev Chattopadhyay, Nikhil S. Mande, and Suhail Sherif.  The log-approximate-rank conjecture is false.  _Journal of the ACM_ , 67(4):1–28.  doi: 10.1145/3396695.
  * [26] Gillat Kol, Shay Moran, Amir Shpilka, and Amir Yehudayoff.  Approximate nonnegative rank is equivalent to the smooth rectangle bound.  _Computational Complexity_ , 28(1):1–25.  doi: 10.1007/s00037-018-0176-4.
  * [27] Makrand Sinha and Ronald de Wolf.  Exponential separation between quantum communication and logarithm of approximate rank.  In _2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)_. IEEE.  doi: 10.1109/focs.2019.00062.
  * Grolmusz [2003a] Vince Grolmusz.  Computing elementary symmetric polynomials with a sub-polynomial number of multiplications.  _SIAM Journal on Computing_ , 32(6):1475–1487, 2003a.
  * Grolmusz [a] Vince Grolmusz.  Modular representations of polynomials: Hyperdense coding and fast matrix multiplication.  _IEEE Transactions on Information Theory_ , 54(8):3687–3692, a.  doi: 10.1109/tit.2008.926346.
  * Barrington et al. [1994] David A. Mix Barrington, Richard Beigel, and Steven Rudich.  Representing Boolean functions as polynomials modulo composite numbers.  _Comput. Complexity_ , 4:367–382, 1994.  Appeared also in Proc. 24th Ann. ACM Symp. Theor. Comput., 1992.
  * Tardos and Barrington [1998] Gábor Tardos and David A. Mix Barrington.  A lower bound on the MOD 6 degree of the OR function.  _Comput. Complex._ , 7:99–108, 1998.
  * Grolmusz [2000] Vince Grolmusz.  Superpolynomial size set systems with restricted intersections mod 6 and explicit Ramsey graphs.  _Combinatorica_ , 20:1–14, 2000.
  * Grolmusz [2002a] Vince Grolmusz.  Set-systems with restricted multiple intersections.  _The Electronic Journal of Combinatorics_ , 9(R8), 2002a.
  * Grolmusz [2002b] Vince Grolmusz.  Constructing set-systems with prescribed intersection sizes.  _Journal of Algorithms_ , 44:321–337, 2002b.
  * Grolmusz [2003b] Vince Grolmusz.  A note on explicit Ramsey graphs and modular sieves.  _Combinatorics, Probability and Computing_ , 12(5-6):565–569, 2003b.  doi: 10.1017/s0963548303005698.
  * Grolmusz [2006a] Vince Grolmusz.  Co-orthogonal codes.  _Designs, Codes and Cryptography_ , 38(3):363–372, 2006a.  doi: 10.1007/s10623-005-1495-4.
  * Grolmusz [2001] Vince Grolmusz.  A degree-decreasing lemma for ${({M}{O}{D}_{q}-{M}{O}{D}_{p})}$ circuits.  _Discrete Mathematics and Theoretical Computer Science_ , 4(2):247–254, 2001.  URL https://www.emis.de/journals/DMTCS/volumes/abstracts/dm060103.abs.html.
  * Grolmusz [2006b] Vince Grolmusz.  Pairs of codes with prescribed hamming distances and coincidences.  _Designs, Codes and Cryptography_ , 41(1):87–99, 2006b.  doi: 10.1007/s10623-006-0016-4.
  * [39] Godfrey H. Hardy and Edward M. Wright.  _An introduction to the theory of numbers (5. ed.)_.  Clarendon Press.  ISBN 978-0-19-853171-5.
  * Grolmusz [b] Vince Grolmusz.  Hyperdense coding modulo 6 with filter-machines.  cs.CC/0306049, b.  URL http://arxiv.org/abs/cs/0306049.
  * [41] Sándor Imre.  Quantum hyperdense coding for distributed communications.  abs/1210.2856.  URL http://arxiv.org/abs/1210.2856.
  * Bebrov [2019] Georgi Bebrov.  On the hyperdense coding and proposal of hyperdense coding quantum secure communication protocol.  In _Quantum Information and Measurement (QIM) V: Quantum Technologies_ , page T5A.49. Optica Publishing Group, 2019.  doi: 10.1364/QIM.2019.T5A.49.  URL https://opg.optica.org/abstract.cfm?URI=QIM-2019-T5A.49.

##  4 Appendix

Here we give an example for a polynomial what we have presented in [32]:

######  Example 12 ([32]).

Let $m=6$, and let

$G_{1}(x)=\sum^{2^{3}-1}_{j=1}(-1)^{j+1}s_{j}(x),$

and

$G_{2}(x)=\sum^{3^{2}-1}_{j=1}(-1)^{j+1}s_{j}(x).$

Then

$P(x)=3G_{1}(x)+4G_{2}(x)$

weakly represents $OR_{71}$ modulo 6, and its degree is only 8.

######  Example 13.

Here we give an explicit example for the coefficients in Theorem 9 (3).

Let $m=6,n=16,t+1=13$ and let $B$ be a $16\times 13$ matrix, $C$ be a
$13\times 16$ matrix mod 6, then $A=BC$ mod 6 is a $16\times 16$ matrix with
1’s in the main diagonal and 0’s either mod 2 or mod 3 or both outside the
main diagonal:

$B=\left[\begin{array}[]{ccccccccccccc}1&0&1&1&4&1&4&4&3&1&4&4&4\\\ \vskip
6.0pt plus 2.0pt minus 2.0pt\cr 1&1&0&4&1&4&1&3&4&4&1&3&3\\\ \vskip 6.0pt plus
2.0pt minus 2.0pt\cr 1&1&4&0&1&4&3&1&4&4&3&1&3\\\ \vskip 6.0pt plus 2.0pt
minus 2.0pt\cr 1&4&1&1&0&3&4&4&1&3&4&4&4\\\ \vskip 6.0pt plus 2.0pt minus
2.0pt\cr 1&1&4&4&3&0&1&1&4&4&3&3&1\\\ \vskip 6.0pt plus 2.0pt minus 2.0pt\cr
1&4&1&3&4&1&0&4&1&3&4&4&4\\\ \vskip 6.0pt plus 2.0pt minus 2.0pt\cr
1&4&3&1&4&1&4&0&1&3&4&4&4\\\ \vskip 6.0pt plus 2.0pt minus 2.0pt\cr
1&3&4&4&1&4&1&1&0&4&3&3&3\\\ \vskip 6.0pt plus 2.0pt minus 2.0pt\cr
1&1&4&4&3&4&3&3&4&0&1&1&1\\\ \vskip 6.0pt plus 2.0pt minus 2.0pt\cr
1&4&1&3&4&3&4&4&3&1&0&4&4\\\ \vskip 6.0pt plus 2.0pt minus 2.0pt\cr
1&4&3&1&4&3&4&4&3&1&4&0&4\\\ \vskip 6.0pt plus 2.0pt minus 2.0pt\cr
1&3&4&4&1&4&3&3&4&4&1&1&3\\\ \vskip 6.0pt plus 2.0pt minus 2.0pt\cr
1&4&3&3&4&1&4&4&3&1&4&4&0\\\ \vskip 6.0pt plus 2.0pt minus 2.0pt\cr
1&3&4&4&3&4&1&3&4&4&1&3&1\\\ \vskip 6.0pt plus 2.0pt minus 2.0pt\cr
1&3&4&4&3&4&3&1&4&4&3&1&1\\\ \vskip 6.0pt plus 2.0pt minus 2.0pt\cr
1&4&3&3&4&3&4&4&1&3&4&4&4\end{array}\right]$

$C=\left[\begin{array}[]{cccccccccccccccc}1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1\\\
\vskip 6.0pt plus 2.0pt minus 2.0pt\cr-1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&-1\\\
\vskip 6.0pt plus 2.0pt minus 2.0pt\cr 0&-1&0&0&0&0&0&0&0&0&0&0&0&0&-1&0\\\
\vskip 6.0pt plus 2.0pt minus 2.0pt\cr 0&0&-1&0&0&0&0&0&0&0&0&0&0&-1&0&0\\\
\vskip 6.0pt plus 2.0pt minus 2.0pt\cr 0&0&0&-1&0&0&0&0&0&0&0&0&0&1&1&1\\\
\vskip 6.0pt plus 2.0pt minus 2.0pt\cr 0&0&0&0&-1&0&0&0&0&0&0&-1&0&0&0&0\\\
\vskip 6.0pt plus 2.0pt minus 2.0pt\cr 0&0&0&0&0&-1&0&0&0&0&0&1&0&0&1&1\\\
\vskip 6.0pt plus 2.0pt minus 2.0pt\cr 0&0&0&0&0&0&-1&0&0&0&0&1&0&1&0&1\\\
\vskip 6.0pt plus 2.0pt minus 2.0pt\cr 0&0&0&0&0&0&0&-1&0&0&0&-1&0&-1&-1&-2\\\
\vskip 6.0pt plus 2.0pt minus 2.0pt\cr 0&0&0&0&0&0&0&0&-1&0&0&1&0&1&1&2\\\
\vskip 6.0pt plus 2.0pt minus 2.0pt\cr 0&0&0&0&0&0&0&0&0&-1&0&-1&0&-1&0&-1\\\
\vskip 6.0pt plus 2.0pt minus 2.0pt\cr 0&0&0&0&0&0&0&0&0&0&-1&-1&0&0&-1&-1\\\
\vskip 6.0pt plus 2.0pt minus 2.0pt\cr
0&0&0&0&0&0&0&0&0&0&0&0&-1&-1&-1&-1\end{array}\right]$

$A=BC=\left[\begin{array}[]{cccccccccccccccc}1&0&0&-3&0&-3&-3&-2&0&-3&-3&-2&-3&-2&-2&-3\\\
\vskip 6.0pt plus 2.0pt minus 2.0pt\cr
0&1&-3&0&-3&0&-2&-3&-3&0&-2&-3&-2&-3&-3&-2\\\ \vskip 6.0pt plus 2.0pt minus
2.0pt\cr 0&-3&1&0&-3&-2&0&-3&-3&-2&0&-3&-2&-3&-3&-2\\\ \vskip 6.0pt plus 2.0pt
minus 2.0pt\cr-3&0&0&1&-2&-3&-3&0&-2&-3&-3&0&-3&-2&-2&-3\\\ \vskip 6.0pt plus
2.0pt minus 2.0pt\cr 0&-3&-3&-2&1&0&0&-3&-3&-2&-2&-3&0&-3&-3&-2\\\ \vskip
6.0pt plus 2.0pt minus 2.0pt\cr-3&0&-2&-3&0&1&-3&0&-2&-3&-3&-2&-3&0&-2&-3\\\
\vskip 6.0pt plus 2.0pt minus
2.0pt\cr-3&-2&0&-3&0&-3&1&0&-2&-3&-3&-2&-3&-2&0&-3\\\ \vskip 6.0pt plus 2.0pt
minus 2.0pt\cr-2&-3&-3&0&-3&0&0&1&-3&-2&-2&-3&-2&-3&-3&0\\\ \vskip 6.0pt plus
2.0pt minus 2.0pt\cr 0&-3&-3&-2&-3&-2&-2&-3&1&0&0&-3&0&-3&-3&-2\\\ \vskip
6.0pt plus 2.0pt minus 2.0pt\cr-3&0&-2&-3&-2&-3&-3&-2&0&1&-3&0&-3&0&-2&-3\\\
\vskip 6.0pt plus 2.0pt minus
2.0pt\cr-3&-2&0&-3&-2&-3&-3&-2&0&-3&1&0&-3&-2&0&-3\\\ \vskip 6.0pt plus 2.0pt
minus 2.0pt\cr-2&-3&-3&0&-3&-2&-2&-3&-3&0&0&1&-2&-3&-3&0\\\ \vskip 6.0pt plus
2.0pt minus 2.0pt\cr-3&-2&-2&-3&0&-3&-3&-2&0&-3&-3&-2&1&0&0&-3\\\ \vskip 6.0pt
plus 2.0pt minus 2.0pt\cr-2&-3&-3&-2&-3&0&-2&-3&-3&0&-2&-3&0&1&-3&0\\\ \vskip
6.0pt plus 2.0pt minus 2.0pt\cr-2&-3&-3&-2&-3&-2&0&-3&-3&-2&0&-3&0&-3&1&0\\\
\vskip 6.0pt plus 2.0pt minus
2.0pt\cr-3&-2&-2&-3&-2&-3&-3&0&-2&-3&-3&0&-3&0&0&1\end{array}\right]$

If we take the dot product of column $j$ of $B$ each with
$(x_{1},x_{2},\ldots,x_{n})$ then we will get the $t+1$ left sums of (3):

$\left(\sum_{i=1}^{n}b_{ij}x_{i}\right)$

If we take the dot product of row $j$ of $C$ each with
$(x_{1},x_{2},\ldots,x_{n})$ then we will get the $t+1$ right sums of (3):

$\left(\sum_{i=1}^{n}c_{ij}y_{i}\right)$

Now, clearly, in (3) one can get coefficient of $x_{u}y_{v}$ by computing the
dot product of row $u$ of $B$ with column $v$ of $C$; that is, matrix $A$
describes the coefficients of the mod 6 representation of the dot product

$f(x_{1},x_{2},\ldots,x_{n},y_{1},y_{2},\ldots,y_{n})=\sum_{i=1}^{n}x_{i}y_{i}$:
all the elements of the main diagonal are 1, and the others are 0 mod 2 or mod
3 or both.

For readers wishing to experiment with these matrices, a Maple worksheet can
be accessed at https://grolmusz.pitgroup.org/?attachment_id=1840


Bimeromorphic geometry of LCK manifolds
Liviu Ornea111Liviu Ornea is partially supported by Romanian Ministry of
Education and Research, Program PN-III, Project number PN-III-P4-ID-
PCE-2020-0025, Contract 30/04.02.2021, Misha Verbitsky222Misha Verbitsky is
partially supported by the HSE University Basic Research Program, FAPERJ
SEI-260003/000410/2023 and CNPq - Process 310952/2021-2.
Keywords: Locally conformally Kähler, global Kähler potential, bimeromorphism,
minimal model, normal variety. 2010 Mathematics Subject Classification: 32H04,
53C55

Abstract

A locally conformally Kähler (LCK) manifold is a complex manifold $M$ which
has a Kähler structure on its cover, such that the deck transform group acts
on it by homotheties. Assume that the Kähler form is exact on the minimal
Kähler cover of $M$. We prove that any bimeromorphic map
$M^{\prime}\rightarrow M$ is in fact holomorphic; in other words, $M$ has a
unique minimal model. This can be applied to a wide class of LCK manifolds,
such as the Hopf manifolds, their complex submanifolds and to OT manifolds.

###### Contents

  1. 1 Introduction
  2. 2 Preliminaries
    1. 2.1 LCK manifolds
    2. 2.2 LCK manifolds with potential
  3. 3 Bimeromorphisms of LCK manifolds
    1. 3.1 Normal varieties
    2. 3.2 Fundamental group and holomorphic maps
    3. 3.3 Manifolds bimeromorphic to an LCK manifold

##  1 Introduction

The notion of a minimal model is central in birational algebraic geometry
since the XIX-th centiry. In 1901, Castelnuovo proved his famous contraction
criterion, establishing that any birational contraction of smooth surfaces
contracts rational curves of self-intersection (-1). This is when the theory
of minimal surfaces was born: a surface is minimal if it cannot be contracted.
Jointly with his student Enriques, Castelnuovo classified minimal surfaces in
a series of works which extended into 1920-ies.

Kodaira extended the minimal model theory from projective surfaces to complex
surfaces, showing that most results of Castelnuovo and Enriques apply also to
compact complex surfaces.

The minimal model program, due to Shigefumi Mori, generalizes the Castelnuovo-
Enriques minimal model theory from surfaces to projective manifolds in higher
dimension. Its version for Kähler threefolds was more recently completed by
Höring and Peternell ([HP]). However, for non-Kähler complex manifolds in
dimension $>2$, not much is known about their bimeromorphic geometry.

The simplest species of non-Kähler manifolds are LCK (locally conformally
Kähler) manifolds. These are complex manifolds which admit a Kähler covering
$\tilde{M}{\>\longrightarrow\>}M$, with the deck transform group acting by
homotheties. For compact $M$, this geometry is sharply distinct from the
Kähler geometry. Indeed, by Vaisman’s theorem ([V2]), a compact LCK manifold
does not admit a Kähler metric, unless the deck transform acts on $\tilde{M}$
by isometries.

Surprizingly, the minimal model program for LCK manifolds (at least, for a
significantly large class of LCK manifolds) is much simpler comparing with the
Kähler or even projective manifolds. Let $M^{\prime}$ be a compact complex
variety bimeromorphic to an LCK manifold $M$ which belongs to two major
subclasses of LCK manifolds, LCK manifolds with potential or OT manifolds
(Subsection 2.2). Then the map $M^{\prime}\dashrightarrow M$ is holomorphic.

In other words, $M$ has a unique minimal model.

The proof is complex-geometric in nature, not using any of the state of the
art results of birational and bimeromorphic geometry. However, it seems to be
possible to deduce this result from the weak factorization theorem ([M,
Theorem 5-1-1]).

Our proof works even in a bigger generality: let $M$ be a compact complex
manifold, and $\tilde{M}$ its covering. If $\tilde{M}$ admits a Kähler form
which is exact, then any bimeromorphic map $M^{\prime}\dashrightarrow M$ is
holomorphic (3.3).

##  2 Preliminaries

We present briefly the notions we need from locally conformally Kähler
geometry. For more details examples and an up to date account of the results,
please see [OV4].

###  2.1 LCK manifolds

Locally conformal Kähler manifolds were defined by Izu Vaisman in [V1]. In
this paper, we shall not need the orginal definition, but the following
equivalent one:

Definition 2.1: ([V2, Remark 2.9]) A Hermitian manifold $(M,I,\omega)$ is
called Locally Conformally Kähler if it admits a Kähler cover
$(\tilde{M},I,\tilde{\omega})$ with deck group $\Gamma$ acting by homotheties
with respect to the Kähler metric.

The Hermitian form $\omega$ is then called an LCK form.

Definition 2.2:  Let $(M,I,\omega)$ be LCK. The very definition implies the
existence of a group morphism $\chi:\ \pi_{1}(M)\to{\mathbb{R}}^{>0}$, given
by $\chi(\gamma)=\frac{\gamma^{*}\tilde{\omega}}{\tilde{\omega}}$ for each
$\gamma\in\pi_{1}(M)$ viewed as a deck transformation of the Kähler universal
cover. This group morphism is called the homothety character.

Definition 2.3:  Let $(M,I,\omega)$ be an LCK manifold and $\chi$ the
associated homothety character. The minimal Kähler cover of $(M,I,\omega)$ is
the Kähler cover associated to $\ker\chi\subset\pi_{1}(M)$.

Example 2.4:  Let $\gamma:\;{\mathbb{C}}^{n}{\>\longrightarrow\>}C^{n}$ be an
invertible holomorphic contraction with apex in 0. Then the quotient
$H=\frac{{\mathbb{C}}^{n}\setminus 0}{\langle\gamma\rangle}$ is called a Hopf
manifold. All Hopf manifolds are LCK. For the case
$\gamma\in\operatorname{GL}(n,{\mathbb{C}})$ (when we speak about “linear Hopf
manifolds”), the proof was given gradually, in a series of papers: [GO, OV1,
OV2]; for non-linear contractions, the proof appeared only recently, in [OV5].

Example 2.5: Almost all the Inoue surfaces ([I]) are LCK ([T, B]). The
Oeljeklaus-Toma (OT) manifolds, which are higher dimensional generalizations
of the Inoue surface $S^{0}$ are LCK. For details, see [OV4, Chapter 22].

###  2.2 LCK manifolds with potential

Definition 2.6: Let $(M,I,\omega)$ be an LCK manifold. It is called LCK with
potential if:

(i)

The Kähler form $\tilde{\omega}$ has a smooth, positive Kähler potential:
$\tilde{\omega}=dd^{c}\varphi$, with
$\varphi:\tilde{M}{\>\longrightarrow\>}{\mathbb{R}}^{>0}$, and

(ii)

The deck group acts by positive homotheties with respect to the potential:
$\gamma^{*}\varphi=c_{\gamma}\varphi$, with $c_{\gamma}\in{\mathbb{R}}^{>0}$,
for all $\gamma\in\Gamma$.

By abuse of terminology, we say that “$\omega$ has potential $\varphi$”.

Remark 2.7:  In general, a differential form $\eta$ on $\tilde{M}$ with the
property that $d^{*}\eta=c_{\gamma}\eta$, $c\in{\mathbb{R}}$,
$\gamma\in\Gamma$, is called automorphic. In particular, for an LCK manifold,
the Kähler form $\tilde{\omega}$ on a Kähler covering is always automorphic.

Remark 2.8: The Kähler forms on the universal covers of Inoue surfaces $S^{0}$
and the Oeljeklaus-Toma manifolds do have positive, global potentials.
However, these are not automorphic in the sense of 2.2 (see [OT], [OV4,
Chapter 22]).

Proposition 2.9:  All smooth submanifolds of an LCK manifold with potential
are LCK manifolds with potential.

Example 2.10: All Hopf manifolds (2.1) are LCK with potential ([OV1, OV2,
OV5]). All non-Kähler elliptic surfaces are LCK with potential ([B, VVO]).

2.2 admits the following partial converse:

Theorem 2.11: ([OV1, OV3]) Let $(M,I,\omega)$ be a compact LCK manifold with
potential, $\dim_{\mathbb{C}}M\geqslant 3$. Then $(M,I)$ admits a holomorphic
embedding to a linear Hopf manifold.

In conclusion, if we restrict to complex dimension at least 3, we can say that
compact LCK manifolds with potential are smooth submanifolds of linear Hopf
manifolds. If the Global Spherical Shell (GSS) conjecture (also called the
Kato conjecture) is true, the same holds for dimension 2 ([OV3]).

##  3 Bimeromorphisms of LCK manifolds

###  3.1 Normal varieties

We shall need a result about normal varieties in the analytic category. Recall
that a complex variety $X$ is called normal if any locally bounded meromorphic
function on an open subset $U\subset X$ is holomorphic ([D, Definition
II.7.4]).

Proposition 3.1:  Let $Z$ be a normal variety, and
$\varphi:\;Z_{1}{\>\longrightarrow\>}Z$ a holomorphic, closed map such that
$\varphi^{-1}(z)$ is finite for all $z$ and bijective in a general point. Then
$\varphi^{-1}$ is holomorphic.

Proof: For proper morphisms of algebraic varieties, this statement serves as
one of the definitions of normality: $Z$ is normal if any finite, birational,
regular map $Z_{1}{\>\longrightarrow\>}Z$ is an isomorphism.

When $f$ is bijective, this statement can be found in [R, Prop. 14.7] or in
[GLS, Theorem 1.102].

By [GLS, Lemma 1.54], for any proper map
$\varphi:\;Z_{1}{\>\longrightarrow\>}Z$ such that $\varphi^{-1}(z)$ is always
finite, there exist an open neighbourhood $U_{z}$ for each $z\in Z$ such that
$\varphi^{-1}(U_{z})$ is a disjoint union of open subsets $V_{1},...,V_{n}$;
each of these would give a coordinate neighbourhood for some
$z_{i}\in\varphi^{-1}(z)$.

Since $\varphi$ is bijective in a general point, the number of open subsets
obtained by application of this lemma is just 1; this implies that $\varphi$
is bijective, and [GLS, Theorem 1.102] can be applied.

###  3.2 Fundamental group and holomorphic maps

Proposition 3.2:  Let $\varphi:\;M\dashrightarrow M_{1}$ be a bimeromorphic
map of compact complex connected manifolds, and $X\subset M\times M_{1}$ the
closure of its graph.111By definition of a meromorphic morphism, $X$ is a
complex subvariety of $M\times M_{1}$. Then the natural projections
$X{\>\longrightarrow\>}M$ and $X{\>\longrightarrow\>}M_{1}$ induce
isomorphisms of the fundamental groups.

Proof. Step 1: Denote by $\tilde{X}$ the resolution of singularities of $X$.
By [K1, §7.8.1], the bimeromorphic holomorphic maps
$\tilde{X}{\>\longrightarrow\>}M_{1}$ and $\tilde{X}{\>\longrightarrow\>}M$
induce isomorphisms on the fundamental groups.

Step 2: We show that the variety $X$ is normal. By definition, a normal
variety is one where all locally bounded meromorphic functions are
holomorphic. Note that the projections from $X$ to $M$ and to $M_{1}$ are
bimeromorphic; this allows us to interpret the meromorphic functions on $X$ as
meromorphic functions on $M$ and $M_{1}$. Any locally bounded meromorphic
function $f$ on $X$ defines a locally bounded meromorphic function on the
manifolds $M$ and $M_{1}$, which are smooth and hence normal. Therefore, $f$
is holomorphic on $M$ and on $M_{1}$. This implies that $f$ is the pullback of
a holomorphic function on $M$ and on $M_{1}$, hence it is holomorphic on
$X\subset M\times M_{1}$.

Step 3: The composition of the maps
$\pi_{1}(\tilde{X}){\>\longrightarrow\>}\pi_{1}(X){\>\longrightarrow\>}\pi_{1}(M)$
(respectively
$\pi_{1}(\tilde{X}){\>\longrightarrow\>}\pi_{1}(X){\>\longrightarrow\>}\pi_{1}(M_{1})$)
is an isomorphism by Step 1. Therefore, to show that
$\pi_{1}(X){\>\longrightarrow\>}\pi_{1}(M_{1})$ (respectively
$\pi_{1}(X){\>\longrightarrow\>}\pi_{1}(M)$) is an isomorphism, it would
suffice to show that the natural map
$\pi_{1}(\tilde{X}){\>\longrightarrow\>}\pi_{1}(X)$ is surjective.

Let $M^{\circ}\subset M$ be the complement of the exceptional set of
$\varphi$. Clearly, the graph of
$\varphi{\left|{}_{{\phantom{|}\\!\\!}_{M^{\circ}}}\right.}$ is dense and
Zariski open in $X$.

Let $U\subset Z$ be a Zariski open subset in a normal complex variety. Then
the natural map $\pi_{1}(U){\>\longrightarrow\>}\pi_{1}(Z)$ is surjective
([SGA1, IX, Cor. 5.6], [C1, §1.3], or [K2, Lemma 3.3]).

We apply this argument to $M^{\circ}\subset X$ and
$M^{\circ}\subset\tilde{X}$, and obtain that the natural maps
$\pi_{1}(M^{\circ}){\>\longrightarrow\>}\pi_{1}(\tilde{X})$ and
$\pi_{1}(M^{\circ}){\>\longrightarrow\>}\pi_{1}(X)$ are surjective. Then the
natural map $\pi_{1}(\tilde{X}){\>\longrightarrow\>}\pi_{1}(X)$ is also
surjective.

###  3.3 Manifolds bimeromorphic to an LCK manifold

Let $\chi:\;\pi_{1}(M){\>\longrightarrow\>}{\mathbb{R}}^{>0}$ be the homothety
character of the LCK structure on $M$ (2.1); it is a homomorphism from the
deck transform group of $\tilde{M}$ to ${\mathbb{R}}^{>0}$ taking a map
$\Psi:\;\tilde{M}{\>\longrightarrow\>}\tilde{M}$ to the scale factor
$\frac{\Psi^{*}\tilde{\omega}}{\tilde{\omega}}$.

For our main result, we use the following proposition.

Proposition 3.3:  Let $(M,\omega)$ be a compact LCK manifold,
$(\tilde{M},\tilde{\omega})$ its minimal Kähler cover (2.1), and $Z\subset M$
a subvariety of positive dimension. Assume that the Kähler form
$\tilde{\omega}$ is exact. Then the image of $\pi_{1}(Z)$ in $\pi_{1}(M)$
contains an infinite cyclic subgroup.

Proof: Denote by $\tilde{Z}\subset\tilde{M}$ the cover of $Z$ obtained by the
homotopy lifting lemma. If the image of $\pi_{1}(Z)$ in $\pi_{1}(M)$ is
finite, the variety $\tilde{Z}$ is compact. This is impossible, because
$\tilde{Z}$ admits a Kähler form $\tilde{\omega}$ which is exact, hence
$0=\int_{\tilde{Z}}\tilde{\omega}^{\dim_{\mathbb{C}}Z}=\operatorname{Vol}(\tilde{Z})>0$;
a contradiction. By the same argument, the Kähler form $\tilde{\omega}$
restricted to $\tilde{Z}$ is not the pullback of a Kähler form on $Z$. This
implies that the deck transform group acts on
$(\tilde{Z},\tilde{\omega}{\left|{}_{{\phantom{|}\\!\\!}_{\tilde{Z}}}\right.})$
by non-trivial homotheties, implying that
$\chi(\pi_{1}(Z))\subset{\mathbb{R}}^{>0}$ is non-trivial.

Consider an element $\gamma\in\pi_{1}(Z)$ such that
$\chi(\gamma)\in{\mathbb{R}}^{>0}\backslash 1$. Then $\gamma$ is of infinite
order; its image in $\pi_{1}(M)$ is also of infinite order, because $\chi$ is
factorized through $\pi_{1}(M)$.

Theorem 3.4:  Let $M$, $M_{1}$ be compact complex manifolds and
$\varphi:\;M_{1}\dashrightarrow M$ a bimeromorphism. Assume that $M$ is an LCK
manifold, and $(\tilde{M},\tilde{\omega})$ its minimal Kähler cover; assume
also that the Kähler form $\tilde{\omega}$ on $\tilde{M}$ is exact. Then
$\varphi$ is holomorphic.

Proof. Step 1: Let $X\subset M\times M_{1}$ be the graph of $\varphi$. By
definition, $X$ is a complex subvariety of $M\times M_{1}$ which projects to
$M$ and $M_{1}$ bijectively in a general point. We denote by
$\sigma:\;X{\>\longrightarrow\>}M$, $\sigma_{1}:\;X{\>\longrightarrow\>}M_{1}$
the projection maps. To prove 3.3, we need to show that $\sigma_{1}^{-1}(z)$
is finite for all $z\in M_{1}$. Then 3.3 follows from 3.1, because $M_{1}$ is
smooth, and therefore normal.

Step 2: Assume, on the contrary, that for some $z\in M_{1}$, its preimage
$Z_{1}:=\sigma_{1}^{-1}(z)$ is positive-dimensional. Since the projection of
$M\times M_{1}$ to $M$ is bijective on the set $M\times\\{z\\}$, the set
$Z_{1}$ projects to $M$ holomorphically and bijectively. Let $Z\subset M$ be
the image of $Z_{1}$ in $M$. By Remmert’s proper mapping theorem ([D, §8.2]),
$Z$ is a complex subvariety in $M$.

Step 3: By 3.3, the image of $\pi_{1}(Z)$ in $\pi_{1}(M)$ contains an infinite
order cyclic subgroup. Therefore, its image in $\pi_{1}(X)=\pi_{1}(M)$ also
contains an infinite order cyclic subgroup. This is impossible, because
$\pi_{1}(X)=\pi_{1}(M)=\pi_{1}(M_{1})$, and the projection of $Z$ to $M_{1}$
is a point.

Since the above proof did not use the full strength of LCK geometry the same
argument can be used to prove the following result, which might be
independently useful.

Theorem 3.5:  Let $M$, $M_{1}$ be compact complex manifolds and
$\varphi:\;M_{1}\dashrightarrow M$ a bimeromorphism. Assume that $M$ admits a
cover which admits an exact Kähler form. Then $\varphi$ is holomorphic.

Acknowledgements: We thank Florin Ambro and Marian Aprodu for very useful
discussions and for bibliographical hints. We are most of all grateful to
Victor Vuletescu for finding an error in an early version of the paper.

## References

  * [B] F. A. Belgun, On the metric structure of non-Kähler complex surfaces, Math. Ann. 317 (2000), 1-40.
  * [C1] Campana, F., On twistor spaces of the class C, J. Differential Geom. 33 (1991), no. 2, 541-549.
  * [D] J.-P. Demailly, Complex analytic and differential geometry, https://www-fourier.ujf-grenoble.fr/~demailly/manuscripts/agbook.pdf
  * [GO] P. Gauduchon, L. Ornea, Locally conformally Kähler metrics on Hopf surfaces, Ann. Inst. Fourier (Grenoble) 48 (1998), 1107-1128.
  * [GLS] G.-M. Greuel, C. Lossen, E. I. Shustin, Introduction to singularities and deformations, Springer Monographs in Mathematics, Springer, 2007.
  * [HP] A. Höring, Th. Peternell, Bimeromorphic geometry of Kähler threefolds, Algebraic geometry: Salt Lake City 2015, 381-402, Proc. Sympos. Pure Math., 97.1, Amer. Math. Soc., Providence, RI, 2018.
  * [I] Ma. Inoue, On surfaces of class $VII_{0}$, Invent. Math., 24 (1974), 269-310
  * [K1] J. Kollár, Shafarevich maps and plurigenera of algebraic varieties, Invent. Math. 113, (1993) 177-215.
  * [K2] J. Kollár, Fundamental groups of rationally connected varieties. Dedicated to William Fulton on the occasion of his 60th birthday, Michigan Math. J. 48 (2000), 359-368.
  * [M] K. Matsuki, Lectures on factorization of birational maps, arxiv:0002084.
  * [OT] K. Oeljeklaus, M. Toma, Non-Kähler compact complex manifolds associated to number fields, Ann. Inst. Fourier 55, no. 1 (2005), 1291-1300.
  * [OV1] L. Ornea, M. Verbitsky, Locally conformal Kähler manifolds with potential, Math. Ann. 348 (2010), 25-33.
  * [OV2] L. Ornea, M. Verbitsky, Locally conformally Kähler metrics obtained from pseudoconvex shells, Proc. Amer. Math. Soc. 144 (2016), 325-335.
  * [OV3] L. Ornea, M. Verbitsky, Embedding of LCK manifolds with potential into Hopf manifolds using Riesz-Schauder theorem, “Complex and Symplectic Geometry”, Springer INdAM series, 2017, 137-148.
  * [OV4] L. Ornea, M. Verbitsky, Principles of locally conformally Kähler geometry, arXiv:2208.07188.
  * [OV5] L. Ornea, M. Verbitsky, Non-linear Hopf manifolds are locally conformally Kähler , arXiv:2202.12398.
  * [R] R. Remmert, Local theory of complex spaces, in Encyclopedia of Mathematical Sciences, vol. 74, 7-96, Springer, 1994.
  * [SGA1] A. Grothendieck, Revétements étales et groupe fondamental, LNM 224, Springer, 1971.
  * [T] F. Tricerri, Some examples of local ly conformal Kähler manifolds, Rend. Sem. Mat., Torino 40, No.1 (1982), 81-92.
  * [V1] I. Vaisman, On locally conformal almost Kähler manifolds, Israel J. Math. 24 (1976), 338-351.
  * [V2] I. Vaisman, On locally and globally conformal Kähler manifolds, Trans. Amer. Math. Soc., 262 (1980), 533-542.
  * [VVO] M. Verbitsky, V. Vuletescu, L. Ornea Classification of non-Kähler surfaces and locally conformally Kähler geometry, Russian Math. Surv. 76 (2021), 261-290. arxiv:1810.05768.

Liviu Ornea
University of Bucharest, Faculty of Mathematics and Informatics,
14 Academiei str., 70109 Bucharest, Romania, and:
Institute of Mathematics “Simion Stoilow” of the Romanian Academy,
21, Calea Grivitei Str. 010702-Bucharest, Romania
<EMAIL_ADDRESS><EMAIL_ADDRESS>
Misha Verbitsky
Instituto Nacional de Matemática Pura e Aplicada (IMPA)
Estrada Dona Castorina, 110
Jardim Botânico, CEP 22460-320
Rio de Janeiro, RJ - Brasil
also:
Laboratory of Algebraic Geometry,
Faculty of Mathematics, National Research University Higher School of
Economics, 6 Usacheva Str. Moscow, Russia
<EMAIL_ADDRESS><EMAIL_ADDRESS>