# CodeMind: A Framework to Challenge Large Language Models
for Code Reasoning

Changshu Liu  Shizhuo Dylan Zhang  Reyhaneh Jabbarvand

###### Abstract

Solely relying on test passing to evaluate Large Language Models (LLMs) for
code synthesis may result in unfair assessment or promoting models with data
leakage. As an alternative, we introduce CodeMind, a framework designed to
gauge the code reasoning abilities of LLMs. CodeMind currently supports three
code reasoning tasks: Independent Execution Reasoning (IER), Dependent
Execution Reasoning (DER), and Specification Reasoning (SR). The first two
evaluate models to predict the execution output of an arbitrary code or code
the model could correctly synthesize. The third one evaluates the extent to
which LLMs implement the specified expected behavior.

Our extensive evaluation of nine LLMs across five benchmarks in two different
programming languages using CodeMind shows that LLMs fairly follow control
flow constructs and, in general, explain how inputs evolve to output,
_specifically for simple programs and the ones they can correctly synthesize_.
However, their performance drops for code with higher complexity, non-trivial
logical and arithmetic operators, non-primitive types, and API calls.
Furthermore, we observe that, while correlated, specification reasoning
(essential for code synthesis) does not imply execution reasoning (essential
for broader programming tasks such as testing and debugging): ranking LLMs
based on test passing can be different compared to code reasoning111The
reasoning of LLMs and humans exhibit fundamental differences due to distinct
nature of their cognitive processes. Our conclusions on the extent of code
reasoning abilities of LLMs do not imply human-like reasoning.

<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>

Department of Computer Science

University of Illinois at Urbana-Champaign, Illinois, US

##  1 Introduction

Large Language Models (LLMs) have shown exceptional programming abilities,
specifically when instruction-tuned or prompted through Chain- or Tree-of-
Thoughts (CoT (Wei et al., 2022b) or ToT (Yao et al., 2023)) and in-context
learning (Wei et al., 2022a; Garg et al., 2022). However, several studies
suggest that LLMs struggle to generalize this exceptional ability,
specifically when the dataset becomes more complex (Du et al., 2023; Jimenez
et al., 2023), or the task requires understanding code, rather than natural
language (Pan et al., 2023; Min et al., 2023). This is mainly because LLMs are
trained to associate code synthesis with natural language specifications,
i.e., reason how to combine code constructs similar to examples they have seen
while satisfying requirements explained in the specification.

To illustrate how code reasoning tasks can evaluate LLMs, Figure 1-a shows a
code synthesized by GPT-3.5 given natural language specification. The code
constructs corresponding to the specification are highlighted with matching
colors. Due to the ambiguity in the natural language, this code returns the
smallest number in the list rather than the number at the index equal to the
value of the smallest number. As a result, for a given input $[2,5,4,3]$, the
code returns 2 instead of 4, and the assertion fails.

Figure 1: An example illustrating the importance of evaluating LLMs on code
reasoning

One way to assess the inductive code reasoning of LLMs is to include specific
expected program behavior and check whether the generated code can reproduce
that behavior. This entails a level of code reasoning, which we refer to as
Specification Reasoning (SR). Figure 1-b shows the new specification and the
corresponding generated code. Executing the code given the specified input-
output pair results in a test pass, indicating the ability of GPT-3.5 to
understand the given specification and generate a correct code.

Including test data in prompts has been a known practice to improve the
performance of models in programming tasks (Chen et al., 2022; Zhong et al.,
2022; Shi et al., 2022; Zhang et al., 2023). However, it is a weak proxy for
code reasoning as it still involves the association of code and natural
language. A deeper level of code reasoning is reasoning about execution output
given an input, which we call Execution Reasoning (ER). This task challenges
LLMs more, requiring them to reason about code without any natural language
cross reference. Figure 1-c shows the CoT reasoning of GPT-3.5 in response to
the ER task. Even though the model could generate a code that produced the
expected output (and is correct if validated through testing), it cannot
correctly reason about the code execution given the same inputs to predict the
output.

To automate code reasoning assessment, we propose CodeMind. CodeMind currently
offers three inductive code reasoning tasks: Independent Execution Reasoning
(IER) and Dependent Execution Reasoning (DER) assess if LLMs can reason about
how given inputs evolve to output for any arbitrary code (IER) or only the
code that it correctly synthesized. Specification Reasoning (SR) evaluates the
extent to which LLMs can reason and implement the specified behavior.

Using CodeMind, we performed a large-scale ground theory study to assess LLMs
for code reasoning. We selected _nine_ models, including both general-purpose
and Code LLMs and prompted them for IER, DER, and SR tasks on _5395_ programs
written in Java and Python .These programs are from _five_ programming
benchmarks, namely HumanEval (Chen et al., 2021), MBPP (Odena et al., 2021),
CRUXEval (Gu et al., 2024) CodeNet (Puri et al., 2021), and Avatar (Ahmad et
al., 2021). We observe that:

(1) LLMs have a good grasp of code constructs, likely due to alignment with
concepts in the natural language specification. The instruction-tuned models
can explain the code statement by statements and follow the execution of the
programs in general. LLM code reasoning abilities, however, are limited to
simple programs. Furthermore, models such as GPT-3.5 and MagicCoder (Wei et
al., 2023), although they correctly explain what the code does, may fail to
keep track of data flow and correctly reason about execution output. Open-
source LLMs that have achieved comparable effectiveness as GPT models in code
synthesis (Wei et al., 2023; Roziere et al., 2023; Luo et al., 2023) are
behind them with a _huge gap_ concerning code reasoning (section 5).

(2) LLMs can reason about test data in the specification, even if deceptive,
and bring that into the reasoning process for code synthesis (section 7).
However, their reasoning is bottlenecked by their inherent limitation. They
achieve a higher performance reasoning about the code they can correctly
synthesize (section 6).

(3) On a dataset with complex programs, there is _a negligible to no
correlation_ between the ranking of models based on code synthesis—generating
a code that passes all tests—and code reasoning performance (section 6). This
necessitates CodeMind tasks and metrics to complement the evaluation of LLMs
for code.

(4) Nested code constructs, complex conditional predicates and loop
conditions, non-trivial arithmetic and logic operators, and API invocations
can significantly challenge LLMs for code reasoning (section 8).

Our contributions are (1) CodeMind framework for code reasoning that formally
defines three inductive code reasoning tasks. CodeMind is open-source
(CodeMind, 2024) and accepts contributions from researchers to integrate more
code reasoning tasks into it; (2) a large-scale ground-theory evaluation of
LLMs for code reasoning using CodeMind; and (3) a comprehensive, in-depth
analysis of results that offers a catalog of root causes negatively impacting
the abilities of LLMs for code reasoning. This catalog would be a valuable
guideline for developing better benchmarks that truly evaluate the programming
abilities of LLMs.

##  2 Related Work

A large body of work has assessed LLMs for reasoning tasks of different
modalieties (Deshpande et al., 2021; Wu et al., 2023; Miceli-Barone et al.,
2023; Bubeck et al., 2023; Wang et al., 2023; Imani et al., 2023; Luo et al.,
2023; Huang et al., 2023; Valmeekam et al., 2022; Min et al., 2023), including
natural language, visual data, math, logic, and code. CodeMind is more closely
related to the very recent studies focusing on code reasoning (La Malfa et
al., 2024; Gu et al., 2024; Zhang et al., 2024).

CRUXEval benchmark is a concurrent work investigating the problem of code
reasoning abilities of LLMs using a dataset of simple programs generated by
CodeLlama (34B) with test cases (Gu et al., 2024). They evaluated a series of
LLMs on CRUXEval for input and output prediction tasks. Compared to CRUXEval,
CodeMind proposes more inductive code reasoning tasks, includes more programs
with a variety of levels of complexity, and controls between code synthesis
and reasoning tasks by evaluating LLMs using the same program. CodeMind is
also equipped with a static analysis pipeline to enable in-depth examination
and drawing informed conclusions.

La Malfa et al. (2024) evaluate LMs to predict variable values at each code
statement. Our experiments are larger compared to them: more programs with a
diverse distribution of complexity and different programming languages, and
more studied LLMs. We also offer more code reasoning tasks and present a
cross-analysis of code synthesis and reasoning abilities.

Zhang et al. (2024) investigate transformers’ ability to learn or infer the
recursive patterns from input and output pairs. They conclude that due to the
inherent limitations of transformers, they may fail to learn recursion and
instead find shortcut algorithms to reason about how outputs are related to
inputs. Compared to this work, we evaluate LLMs regardless of architecture and
training data but from the program perspective. We show LLMs can follow
recursion but usually lose track of data flow due to the inability to
correctly reason about loop conditions.

##  3 CodeMind

Program specification defines a function $S:S_{I}\rightarrow S_{O}$, where
$S_{I}$ is a set of all possible inputs to the program and $S_{O}$ is a set of
corresponding outputs. A code synthesized based on the implementation is
usually a function $C:C_{I}\rightarrow C_{O}$. We define a program to be
correct with respect to specification, if it satisfies all the following
conditions:

$C_{I}\subseteq S_{I}$, $C_{O}\subseteq S_{O}$, $\forall i\in C_{I},C(i)=S(i)$

This entails the models to reason about how inputs evolve to a given output
through implementation (execution reasoning) and implements a code such that
it generates correct outputs for a given input (specification reasoning).

###  3.1 Execution Reasoning

Considering the aforementioned formalization, we define two execution
reasoning tasks as follows.

Definition 1: Independent Execution Reasoning (IER). Given a program
$C:C_{I}\rightarrow C_{O}$ and set of inputs $\hat{I}=\\{i|i\in C_{I}\\}$, LLM
$L$ can correctly reason about code execution if $\hat{o}=C(\hat{I})$, where
$\hat{o}=L(\hat{I})$ is the predicted output by $L$. Note that in this task,
we do not deal with specification, so we can assess LLMs for any arbitrary
code that we have ground-truth pairs of $\langle\hat{I},\hat{o}\rangle$.

IER evaluates LLMs for any arbitrary code for general inductive code
reasoning, which requires knowing code constructs, arithmetic and logic
operations, and control flow. However, even for human developers, reasoning
about their developed code is easier than any arbitrary code. Furthermore, as
a self-consistency (Min et al., 2023) measurement, LLMs should be able to
reason about the code they can correctly synthesize. This demands to have the
following execution reasoning task.

Definition 2: Dependent Execution Reasoning (DER). Given a specification
$S:S_{I}\rightarrow S_{O}$, a program $C:C_{I}\rightarrow C_{O}$ generated by
LLM $L$, and set of inputs $\hat{I}=\\{i|i\in C_{I},C(i)=S(i)\\}$, LLM $L$ can
correctly reason about code execution if $\hat{o}=C(\hat{I})$, where
$\hat{o}=L(\hat{I})$ is the predicted output by $L$. The assumption here is
that when LLM $L$ generates code $C$ that passes the test
$\langle\hat{I},\hat{o}\rangle$, it be able to predict $\hat{o}$ correctly.

###  3.2 Specification Reasoning

In addition to inductive execution reasoning, a model should understand
specification to synthesize a correct code. We formally define the
specification reasoning task as follows.

Definition 3: Specification Reasoning (SR). Given a specification
$S:S_{I}\rightarrow S_{O}$, an arbitrary $\langle i,o\rangle$ specified in the
prompt along with the natural language specification, where $i\in S_{I},o\in
S_{O},S(i)=o$, and program $C:C_{I}\rightarrow C_{O}$ generated by LLM $L$,
the LLM can correctly reason about specification if $C(i)=S(i)$. In other
words, LLM $L$ should be able to pass a test with $\langle i,o\rangle$, when
they are explicitly specified in the prompt.

Table 1: CRR performance of subject LLMs on IER task through CoT prompting. We highlight the top three best-performing models with red (1), green (2), and blue (3). Dataset |  Programming Language | # Subjects | General LLMs | Code LLMs
---|---|---|---|---
GPT-4 | GPT-3.5 | Llama 2 | Mistral | CodeLlama | DeepSeekCoder | MagicCoder | StarCoder | WizardCoder
MBPP | Python | 408 | 80.88% | 71.32% | 45.59% | 31.37% | 42.40% | 57.84% | 59.80% | 43.63% | 46.08%
HumanEval | Python | 162 |  79.01% | 64.20% | 30.86% | 32.72% | 45.06% | 41.98% | 52.47% | 38.89% | 40.12%
CruxEval | Python | 800 | 80.50% | 65.13% | 25.38% | 34.13% | 37.75% | 44.38% | 46.50% | 35.50% | 35.88%
CodeNet | Python | 1914 | 70.43% | 49.06% | 18.97% | 17.35% | 27.95% | 26.65% | 33.28% | 26.28% | 24.87%
Java | 1939 | 71.17% | 51.93% | 23.99% | 18.15% | 28.52% | 32.13% | 36.46% | 29.34% | 29.35%
Avatar | Python | 86 | 52.33% | 39.53% | 24.42% | 16.28% | 23.26% | 18.60% | 24.42% | 19.77% | 24.42%
Java | 86 | 48.84% | 34.88% | 23.26% | 11.63% | 27.91% | 23.26% | 24.42% | 13.95% | 13.95%
Total | Java and Python | 5395 | 72.60% | 54.24% | 24.26% | 21.54% | 30.40% | 33.85% | 38.68% | 30.14% | 29.99%

###  3.3 Evaluating Code Reasoning

We measure the performance of models in code reasoning for a given code with
the Correct Reasoning Score (CRS), which is $1$ if the model can correctly
reason about the code and $0$ otherwise. We also introduce the Correct
Reasoning Rate (CRR) metric, a collective metric that measures how much a
given LLM can reason about multiple programs in a benchmark. We calculate CRR
for a set of $m$ programs in benchmark $P$ as:

$CRR(P)=\dfrac{\sum\limits_{i=1}^{m}\llbracket CRS(p_{i}\in
P)=1\rrbracket}{m}$

##  4 Experimental Setup

Our study includes nine LLMs and $5395$ programs in Java and Python
programming languages from five programming datasets. We explain the details
of LLMs and program selection below.

Subject LLMs. We chose nine pre-trained or instruction-tuned models, covering
both general-purpose and Code LLMs. Our choice was limited to computing
resources, so we selected models with less than $20$B parameters that
outperform the rest for programming tasks. Our subject LLMs are GPT-4 (OpenAI,
2023b), GPT-3.5 (OpenAI, 2023a), Llama 2 (13B) (Touvron et al., 2023), Mistral
(Jiang et al., 2023), CodeLlama (13B, instruction-tuned)(Roziere et al.,
2023), StarCoder (15.5B)(Li et al., 2023), WizardCoder (15B, instruction-
tuned)(Xu et al., 2023), MagicCoder (7B)(Wei et al., 2023) (instruction-
tuned), DeepSeekCoder (6.7B)(Bi et al., 2024). We followed the best practices
and customized the prompt templates per each model (all prompts are publicly
available for further investigation (CodeMind, 2024)). Except for the GPT
models, we set the temperature to zero to ensure the reproducibility of the
results. Our code is open-source to users for using CodeMind for other models
and temperatures.

Subject Programs. Our criteria for selecting subject programs were the
existence of test data (inputs and corresponding expected output) and
implementations of the same program in multiple programming languages (to
investigate its impact on code reasoning). From several existing benchmarks
(Wang et al., 2022; Athiwaratkun et al., 2022; Chen et al., 2021; Liu et al.,
2023; Gu et al., 2024; Zheng et al., 2023; Cassano et al., 2022; Jimenez et
al., 2023; Du et al., 2023; Odena et al., 2021; Puri et al., 2021; Ahmad et
al., 2021), we chose the programs in HumanEval (Chen et al., 2021), MBPP
(Odena et al., 2021), CodeNet (Puri et al., 2021), Avatar (Ahmad et al.,
2021), and CruxEval (Gu et al., 2024). We chose Java and Python versions of
the programs as they are more prominently used programming languages.
HumanEval and MBPP are well-known benchmarks for code synthesis. CodeNet and
Avatar are code translation benchmarks. CRUXEval is a benchmark of relatively
simple Python programs generated by CodeLlama (34B) to evaluate input
prediction and output prediction of LLMs.

Figure 2: Complexity distribution of the subject programs in terms of
Cyclomatic Complexity (CC) and Line of Code (LoC)

Figure 2 shows the complexity distribution of the programs in terms of
Cyclomatic Complexity, $CC$ (Gill & Kemerer, 1991), and Lines of Code (LoC).
$CC$ measures the number of independent execution paths in the program control
flow graph (CFG). The metric is computed for a class as $CC=E-N+2P$, where $E$
and $N$ are the number of edges and nodes in the CFG, respectively, and $P$ is
the number of methods in the class. In general, a higher $CC$ indicates a more
complex program.

For code reasoning tasks, the model should reason which execution path to take
for a given input to predict the output. So, the higher number of independent
paths makes it unlikely for the model to succeed by chance. $CC$ might be
correlated with the number of lines in the program, but more lines do not
cause higher $CC$. For example, a program with $10$ lines and no conditional
or loop constructs only has one execution path, while a program with $8$ lines
and two nested conditional statements has $3$ or $4$ execution paths,
depending on the conditional predicates.

##  5 LLM Evaluation on IER

Figure 3: Impact of CC on CRR performance of LLMs in IER

To evaluate the performance of LLMs on the IER task, we promoted them under
two settings: direct answering and CoT. For direct answering, we prompted each
model to predict the output of given inputs. Under the CoT setup, we first
instruct the models to simulate the execution step by step by predicting the
output value after execution of each statement. We then ask the model to
predict the output of given inputs. In both settings, the prompt contains one
in-context example for two purposes: introducing the IER task and instructing
the response formatting.

Given that IER only requires an arbitrary code and corresponding ground-truth
pair of $\langle\hat{I},\hat{o}\rangle$ (section 3.1), we prompted the LLMs
using all $5395$ subject programs in this experiment. Table 1 shows the result
of this experiment through CoT prompting. From these results, we observe that:

Table 2: CRR performance of subject LLMs on DER task through CoT prompting. We highlight the top three best-performing models with red (1), green (2), and blue (3). Dataset | # Subjects | Task | General LLMs | Code LLMs
---|---|---|---|---
GPT-4 | GPT-3.5 | Mistral | CodeLlama | DeepSeekCoder | MagicCoder | StarCoder | WizardCoder
MBPP | 408 | Synthesis | $86.52\%$ | $80.39\%$ | 43.36% | 56.86% | 72.30% | 70.34% | 44.85% | 61.03%
Reasoning | 82.62% | 79.20% | 43.50% | 43.53% | 63.39% | 69.34% | 56.83% | 48.19%
CRR Improvement cf. IER | $1.74\%\uparrow$ | $7.88\%\uparrow$ | $11.89\%\uparrow$ | $1.13\%\uparrow$ | $5.15\%\uparrow$ | $9.54\%\uparrow$ | $13.20\%\uparrow$ | $2.11\%\uparrow$
HumanEval | 162 | Synthesis | 87.65% | 69.75% | 52.47% | 67.90% | 81.48% | 79.62% | 48.15% | 72.46%
Reasoning | 80.28% | 74.63% | 34.12% | 35.45% | 54.55% | 53.49% | 58.97% | 59.50%
CRR Improvement cf. IER | $1.27\%\uparrow$ | $10.70\%\uparrow$ | $1.4\%\uparrow$ | $9.61\%\downarrow$ | $12.57\%\uparrow$ | $1.02\%\uparrow$ | $20.08\%\uparrow$ | $19.38\%\uparrow$

  * •

GPT models outperform others on the IER task, with large margins of $33.92\%$
(GPT-4) and $15.56$ (GPT-3.5) from the best open-source model. Among the open-
source models, except for the Avatar dataset, MagicCoder outperforms others
with an average margin of $4.83\%$.

  * •

On the datasets with samples in both Java and Python, all the models
experience a performance drop (average drop of $2.91\%$ in CodeNet and
$2.33\%$ in Avatar). This is likely because Java enforces a stricter syntax
and typing system than Python, making the code execution reasoning harder.

  * •

Compared to direct answering, CoT prompting, under which the models articulate
the execution process verbally before predicting the output, results in
$5.24\%$ improvement in the IER performance of the models on average. However,
the less-than-ideal accuracy of (open-source) models, even with CoT prompting,
demands a fundamental change.

  * •

Moving down in the table, the models face greater challenges in IER, i.e.,
reasoning about the execution on CodeNet and Avatar programs, compared to
MBPP, HumanEval, and CRUXEval. One potential reason is the complexity of such
programs as demonstrated in Figure 2. A detailed breakdown of the model’s
performance (Figure 3) shows a strong negative correlation Spearman’s Rank
Order Correlation (ROC) (Spearman, 1961) between CC and CRR. between CRR and
CC, confirming that models struggle more in IER for a more complex code. At
the same time, some models, namely Llama 2, CodeLlama, MagicCoder, StarCoder,
and WizardCoder, achieve a lower performance on CRUXEval compared to
HumanEval, which are less complex regarding both LoC and CC. This entails a
further better understanding of what factors other than CC impact the CRR
performance of the models (section 8).

##  6 LLM Evaluation on DER

We seek to address the critical question of how effectively the model can
correctly reason about the correct programs it has generated. This evaluation
requires us to align code synthesis and code reasoning tasks together. Our
pipeline for evaluating DER consists of three steps: (1) following the best
practices, we prompted subject LLMs for code synthesis; (2) we ran the
synthesized program against existing tests; and (3) for the programs with test
pass, we prompted the model for code execution reasoning using the chosen test
input and under CoT style. Note that we also removed the comments from the
synthesized code for fairness. We excluded the programs from CRUXEval,
CodeNet, and Avatar, since these datasets are not designed for code synthesis
and lack proper program specifications. Also, we could not reproduce the code
synthesis results of Llama 2 and excluded that from subject LLMs. Similar to
IER experiments, we set the temperature to zero to account for the non-
determinism and reproducibility of the results. As a result of this design
decision, our synthesis results might be different from existing leaderboards.

Table 2 shows the results of this experiment. GPT models still outperform
open-source models on the DER task, with a margin of $17.97$ (GPT-4) and
$13.13$ (GPT-3.5) from the best open-source model. Compared to IER, the gap
between GPT models and open-source models has been reduced. We can also
observe that the models achieve $6.84\%$ higher CRR on average in the DER task
(except CodeLlama on HumanEval), compared to IER.

Before concluding the models are more competent in the execution reasoning
when evaluated on the programs they correctly synthesize, we compared the
programs in this experiment with those in IER experiment. If true, lower
complexity might be the root cause of higher CRR on the DER task. Figure 4
shows the CC distribution of the programs in MBPP and HumanEval, compared to
that generated by subject LLMs. We can observe that the synthesized code, if
not more complex, is no less than the ground-truth programs in these datasets.
Consequently, we confirm that models reason better on a code they correctly
synthesize. However, there is still a considerable gap between the code
synthesis and reasoning abilities of the LLM, specifically on open-source
models.

Figure 4: CC distribution of the programs synthesized by LLMs compared to the
original programs in the HumanEval (top) and MBPP (bottom) datasets

Given that code synthesis and reasoning are unified in DER, we first computed
the Spearman’s ROC between the rank of models based on numbers in the
Synthesis row and Reasoning row for each dataset. The results show a strong
positive correlation on MBPP ($\rho=0.85$), but a negligible correlation on
HumanEval ($\rho=0.17$). These results communicate a strong message: the
ranking of LLMs based on their code synthesis abilities (pass@k) could be
significantly different than their reasoning abilities on the same code. This
necessitates a framework such as CodeMind that promotes other evaluation
aspects of LLMs for code.

Table 3: Performance of LLMs on SR task. Symbol $\downarrow$ indicates a drop from the previous setting (row above), and $\uparrow$ indicates an increase from the previous setting (row above). Dataset | Setting | General LLMs | Code LLMs
---|---|---|---
GPT-4 | GPT-3.5 | Mistral | CodeLlama | DeepSeekCoder | MagicCoder | StarCoder | WizardCoder
MBPP | With Test | 90.69% | 85.05% | 50.74% | 63.73% | 78.68% | 75.25% | 51.47% | 67.89%
No Test | 72.13% $\downarrow$ | 78.87% $\downarrow$ | 48.28% $\downarrow$ | 53.68% $\downarrow$ | 67.65% $\downarrow$ | 69.61% $\downarrow$ | 41.67% $\downarrow$ | 52.21% $\downarrow$
Misleading Test | 68.14% $\downarrow$ | 74.02% $\downarrow$ | 50.74% $\uparrow$ | 59.07% $\uparrow$ | 68.63% $\uparrow$ | 67.40% $\downarrow$ | 40.20% $\downarrow$ | 58.09% $\uparrow$
HumanEval | With Test | 91.98% | 74.07% | 57.41% | 70.37% | 87.04% | 81.48% | 56.17% | 76.54%
No Test | 88.27% $\downarrow$ | 70.37% $\downarrow$ | 54.32% $\downarrow$ | 65.43% $\downarrow$ | 82.10% $\downarrow$ | 80.86% $\downarrow$ | 38.89% $\downarrow$ | 76.54%
Misleading Test | 83.95% $\downarrow$ | 65.43% $\downarrow$ | 53.70% $\downarrow$ | 61.73% $\downarrow$ | 79.63% $\downarrow$ | 74.69% $\downarrow$ | 27.04% $\downarrow$ | 66.05% $\downarrow$

##  7 Evaluation on SR

Specification Reasoning (SR) offers a novel perspective in understanding the
code synthesis process of LLMs, particularly in how they leverage input-output
specifications. To evaluate the abilities of LLMs for SR, we prompt LLMs for
code synthesis under the following three settings:

Figure 5: CRR of top five best-performing LLMs per specific code constructs
across all datasets. We abbreviate the tags with B (Basic), F (For), I (If),
NI (Nested If), NL (Nested Loop), S (Switch), T (Try), and W (While)

(1) Natural language specification with one ground-truth input-output. Under
this setting, we randomly select one of the existing tests and add that to the
specification. We validate the synthesized code using only this test.

(2) Natural language specification with no input-output. We remove the test
added to the specification in the previous setting and re-prompt LLMs for code
synthesis. We validate the synthesized code using only the test from the
previous setting. Intuitively, if including test data can help LLMs in code
synthesis, we observe a drop in LLMs’ performance.

(3) Natural language specification with misleading input-output. We mutate the
expected output of the test from the first setting and add it to the
specification. We validate the synthesized code using the original test. The
mutation changes the expected output to a value that does not align with the
specification. For example, if the expected output is True, mutation changes
it to False. Similarly, if the expected output is a positive integer, we
mutate it to a negative one with a large difference. Intuitively, due to the
divergence with natural language specification, misleading input-output should
further drop LLMs’ performance.

We followed a similar setup for this experiment as the one in section 6;
performed this experiment only on MBPP and HumanEval programs. _We also pre-
processed the prompts from HumanEval, which initially contained input-output
samples._ The results in Table 3 show that the performance of LLMs in code
synthesis is, on average, $7.36\%$ higher with test data included in the
specification. Introducing deceptive tests in the specification detrimentally
affects the LLMs’ performance in code synthesis compared to a legitimate test
($10\%$ performance drop on average). However, compared to No Test cases, the
performance drop across all the models and programs is only $2.65\%$ on
average. Regardless, these results showcase the ability of LLMs to reason and
utilize the test data in the specification.

Figure 6: Impact of loop length in Java programs (CodeNet and Avatar) on LLMs’
performances

##  8 In-Depth Analysis of Results

We further analyzed the IER results, which evaluate the general ability of
LLMs in code reasoning. In the first step, we wanted to see if LLMs know how
different code constructs work. Without knowing the logic of each code
construct, reasoning about code execution is impossible. To that end, we
tagged each of $5395$ programs based on code constructs used in their
implementation with the following labels: For, While, If, Try, Switch, Nested
Loop, Nested If, and Basic. A program tagged with a Basic label has no special
code construct. Next, we clustered the programs per tag and computed the CRR
of LLMs for each cluster. Figure 5 shows the results of this analysis for the
top five best-performing LLMs. We can observe that models handle conditional
statements better than recursion, except for Try-Catch or Try-Except
statements. Furthermore, when it comes to nested constructs, the CRR values
notably drop. Impact of Loop Properties. Given that models struggle the most
with recurring constructs, we focused the programs with For, While, and Nested
Loop tags at the next step. We hypothesize this struggle is due to the loop’s
length or determining the loop’s length. The former questions whether it is
harder for the model to track the program’s data flow as loops get longer. The
latter questions the abilities of models to reason about how many times a code
block should be repeated, regardless of how long the length would be.

Figure 6 plots the distribution of correct versus incorrect cases and CRR
values per each loop length in Java programs. Sub-figure labels show the ROC
coefficients between the loop length and CRR. We can observe a moderate to
strong negative correlation between the loop length and CRR of the models,
i.e., CRR decreases as the loop length increases. By manually investigating
the incorrect IER cases, we also noticed that LLMs mostly failed to reason
about loop conditions correctly. Without knowing loop conditions and the
number of iterations, it is impossible to reason about the execution
correctly. Furthermore, we found cases where, although the model could reason
about loop conditions and the number of iterations, it lost track of data flow
in the loop, thereby predicting output incorrectly.

(a) Java

(b) Python

Figure 7: Performances of LLMs on code with different types of outputs. Type
Match(TM) means the ratio of predicted output that is in the same type as the
expected output (ground truth). Value Match(VM) means the CRR on the code with
a certain type of output.

In the code snippet below (p03059 from CodeNet (Java)), the loop condition
depends on a constant variable (c) and variable (time), whose value changes
inside the loop.

⬇

Input: 3 5 7, Expected Output:10

int a, b, c = sc.nextInt();

int amount = 0, time = a;

for(int i = 2; time <= c + 0.5; i++){

amount += b;

time = a * i;

}

println(amount);

All models failed in IER of this relatively simple program. Looking at the CoT
analysis, GPT-3.5 knows the loop condition and can reason about all the
variable values in the first and second iterations. However, it stays in the
loop for one more. StarCoder cannot correctly reason about loop condition and
iterates the code block six times. MagicCoder CoT only explains the code
(correct explanation) without communicating how it reasons about variables.

⬇

GPT-3.5, Predicted Output:15

Analysis: Enters for loop and iterates from 2 onwards

until the value of time exceeds c + 0.5. In first

iteration, amount becomes 5 and time becomes 6. In

second iteration, amount becomes 10 and time becomes

9. In third iteration, amount becomes 15 and time

becomes 12. 12 is greater than 7+0.5, loop<EMAIL_ADDRESS>
StarCoder, Predicted Output:105

Analysis: It enters a for loop and it iterates from 2

to 7 to check each integer i in this range. In each

iteration, the value of i is passed to variable time.

The condition is@ met when i is 2,3,4,5,6 and 7.

MagicCoder, Predicted Output:15

Enters for loop and iterates from 2 to infinity. Inside

the loop, it adds the value of b to variable amount.

Then it calculates new value of time by multiplying a

with current iteration i. The loop continues until time

is greater than c+0.5. After the loop finishes, print

the final value of amount as output, which is 15.

The loop condition is simple in the code snippet below (p02994 from CodeNet
(Java)). Consequently, most models correctly reasoned about the number of
iterations.

⬇

Input: 5 2, Expected Output: 18

int n = scanner.nextInt();

int l = scanner.nextInt();

List<Integer> diff = new ArrayList<Integer>();

for(int i = 1; i < n+1; i++) {

int value = l+i-1;

if(value < 0) {value = value * -1;}

diff.add(value);

}

removeK = diff.indexOf(Collections.min(diff)) + 1;

println(n*l + n*(n+1)/2 - n - (l+ removeK -1));

Still, some LLMs struggled to reason about code execution inside the loop
correctly. CodeLlama can correctly reason about the number of loop iterations
but fails to calculate the values in the diff array, resulting in a wrong
output. MagicCoder can also correctly reason about loop length, and similar to
the previous example, correctly explain what the code does. However, it cannot
predict the output correctly (predicted output is 10), preventing us from
judging if it understands the code as well as it explains it.

⬇

CodeLlama, Predicted Output:24

Analysis: In the given inputs n is 5 and l is 2. The

sequence of numbers from 1 to 5 is [1,2,3,4,5]. The

differences between l and each number in the sequence

are [1,0,1,2,3]. The smallest difference is 0 at index

1. So, the index 1 is removed from the sequence. The

new sequence becomes [1,3,4,5]. The sum of the original

sequence [1,2,3,4,5] and the new sequence [1,3,4,5] is

calculated as (5*2+5*(5+1)/2-5-(2+1-1))=15+15-5-2=24.

Impact of if-else Properties. Our manual investigations reveal that LLMs
struggle with conditional constructs for two reasons: (1) confusion about
branches and (2) wrong reasoning about conditional predicates. Concerning the
former, we observed that LLMs sometimes struggle to recognize conditional
statements. For example, regardless of which branch to take, they always go
into both “if” and “else” branches to reason about execution. However, such
cases rarely happen, and in most cases, LLMs struggle to analyze the
conditional predicates correctly, take the wrong branch, and predict the
output incorrectly.

Impact of Math and Logic Operators. Knowing how the math and logic operators
work is essential to reasoning how inputs evolve into output through
execution. The observations from previous analyses also underscore their
importance to reason about the program control flow. Our manual investigation
of failed IER cases shows the prevalence of arithmetic and logic operators in
programs, with the former dominating the number of the latter. LLMs struggled
more to reason about bitwise operators (e.g., >>>, $\wedge$, >>, <<, |, and
$\&$) compared to arithmetic (e.g., + and -) and comparison operators (e.g.,
>, <).

The code snippet below is from MBPP (task 311) and contains several arithmetic
and logic operators.

⬇

Input: 10, Expected Output:14

def set_left_most_unset_bit(n):

if not (n & (n + 1)): return n

pos, temp, count = 0, n, 0

while temp:

if not (temp & 1): pos = count

count += 1

temp>>=1

return (n | (1 << (pos)))

StarCoder, Predicted Output:10

Analysis: The variable n is initialized to 10. The code

checks if n is a power of 2. If it is, the code returns

n. If it is not, the code calculates the position of

the leftmost unset bit. The code then returns the

result of n | (1 << (pos)).

StarCoder, while failing to predict the output, correctly knows how most
operators work. For example, it can reason that the bitwise AND of n and n+1
is used to determine whether integer n is a power of 2. It can also reason
that the loop condition checks if the least significant bit of n is set to 0.
However, it seemingly cannot understand the meaning of the return statement
(setting the least significant bit to 1), hence failing to predict the correct
output.

Impact of Output Types. We categorized programs based on the output types and
checked (1) if LLMs were able to correctly predict the type of output (Type
Match) and (2) if they could correctly reason about the values of output
(Value Match). We identified seven types in subject programs, namely Int
(e.g., $2$), Decimal(e.g., $2.34$), String (e.g., ”CodeMind”), Binary (e.g.,
True or False), List (e.g., [1,3,4,7]), and Tuple (Python-specific, e.g.,
(2,7)). Figure 7 shows the details of these results. In summary, LLMs achieve
a high Type Match ($>80\%$), although they struggled to predict the correct
value (Value Match). Among different types, it is harder for the models to
predict the values of outputs with Tuple/List and Decimal types.

Tuples and Lists consist of multiple items, and every single one of them may
change during the program execution. As a result, it is unsurprising that
models struggle to track the flow of inputs through potentially different
execution paths and reason about a complex output as a whole. Additionally,
given that manipulation of such types involves API calls, e.g., min(), next(),
charAt(), reasoning about changes requires LLMs know how the APIs work, which
is an additional effort.

##  9 Concluding Remarks

In this paper, we discussed the necessity of code reasoning tasks as an
alternative to evaluate LLMs for programming tasks. We introduced CodeMind, a
framework that supports several code reasoning tasks, and used CodeMind in a
large-scale grounded theory study to evaluate state-of-the-art LLMs for code
reasoning. Our results demonstrate that LLMs, in general, know how code
constructs work and are capable of reasoning about program specification and
following how inputs evolve to output through execution. However, their
ability is limited as the code becomes more complex, i.e., has more complex
control- or data flow, contains non-primitive types, and invokes API calls. We
also observe that specification reasoning, which is essential to generate a
code from a given program specification, does not mean models can also reason
about code execution. We are considering two future directions based on this
work. First, we plan to add more code reasoning tasks to CodeMind, e.g.,
variable reasoning and code optimization reasoning. Furthermore, we want to
augment CodeMind with a benchmark that can challenge LLMs’ code reasoning to a
greater extent compared to the existing benchmarks.

## References

  * Ahmad et al. (2021) Ahmad, W. U., Tushar, M. G. R., Chakraborty, S., and Chang, K.-W.  Avatar: A parallel corpus for java-python program translation.  _arXiv preprint arXiv:2108.11590_ , 2021.
  * Athiwaratkun et al. (2022) Athiwaratkun, B., Gouda, S. K., Wang, Z., Li, X., Tian, Y., Tan, M., Ahmad, W. U., Wang, S., Sun, Q., Shang, M., et al.  Multi-lingual evaluation of code generation models.  _arXiv preprint arXiv:2210.14868_ , 2022.
  * Bi et al. (2024) Bi, X., Chen, D., Chen, G., Chen, S., Dai, D., Deng, C., Ding, H., Dong, K., Du, Q., Fu, Z., et al.  Deepseek llm: Scaling open-source language models with longtermism.  _arXiv preprint arXiv:2401.02954_ , 2024.
  * Bubeck et al. (2023) Bubeck, S., Chandrasekaran, V., Eldan, R., Gehrke, J., Horvitz, E., Kamar, E., Lee, P., Lee, Y. T., Li, Y., Lundberg, S., et al.  Sparks of artificial general intelligence: Early experiments with gpt-4.  _arXiv preprint arXiv:2303.12712_ , 2023.
  * Cassano et al. (2022) Cassano, F., Gouwar, J., Nguyen, D., Nguyen, S., Phipps-Costin, L., Pinckney, D., Yee, M.-H., Zi, Y., Anderson, C. J., Feldman, M. Q., et al.  Multipl-e: A scalable and extensible approach to benchmarking neural code generation.  _arXiv preprint arXiv:2208.08227_ , 2022.
  * Chen et al. (2022) Chen, B., Zhang, F., Nguyen, A., Zan, D., Lin, Z., Lou, J.-G., and Chen, W.  Codet: Code generation with generated tests.  _arXiv preprint arXiv:2207.10397_ , 2022.
  * Chen et al. (2021) Chen, M., Tworek, J., Jun, H., Yuan, Q., de Oliveira Pinto, H. P., Kaplan, J., Edwards, H., Burda, Y., Joseph, N., Brockman, G., Ray, A., Puri, R., Krueger, G., Petrov, M., Khlaaf, H., Sastry, G., Mishkin, P., Chan, B., Gray, S., Ryder, N., Pavlov, M., Power, A., Kaiser, L., Bavarian, M., Winter, C., Tillet, P., Such, F. P., Cummings, D., Plappert, M., Chantzis, F., Barnes, E., Herbert-Voss, A., Guss, W. H., Nichol, A., Paino, A., Tezak, N., Tang, J., Babuschkin, I., Balaji, S., Jain, S., Saunders, W., Hesse, C., Carr, A. N., Leike, J., Achiam, J., Misra, V., Morikawa, E., Radford, A., Knight, M., Brundage, M., Murati, M., Mayer, K., Welinder, P., McGrew, B., Amodei, D., McCandlish, S., Sutskever, I., and Zaremba, W.  Evaluating large language models trained on code, 2021.
  * CodeMind (2024) CodeMind.  Artifact website.  https://github.com/Intelligent-CAT-Lab/CodeMind, 2024.
  * Deshpande et al. (2021) Deshpande, R., Chen, J., and Lee, I.  Rect: A recursive transformer architecture for generalizable mathematical reasoning.  In _NeSy_ , pp. 165–175, 2021.
  * Du et al. (2023) Du, X., Liu, M., Wang, K., Wang, H., Liu, J., Chen, Y., Feng, J., Sha, C., Peng, X., and Lou, Y.  Classeval: A manually-crafted benchmark for evaluating llms on class-level code generation.  _arXiv preprint arXiv:2308.01861_ , 2023.
  * Garg et al. (2022) Garg, S., Tsipras, D., Liang, P. S., and Valiant, G.  What can transformers learn in-context? a case study of simple function classes.  _Advances in Neural Information Processing Systems_ , 35:30583–30598, 2022.
  * Gill & Kemerer (1991) Gill, G. K. and Kemerer, C. F.  Cyclomatic complexity density and software maintenance productivity.  _IEEE transactions on software engineering_ , 17(12):1284–1288, 1991.
  * Gu et al. (2024) Gu, A., Rozière, B., Leather, H., Solar-Lezama, A., Synnaeve, G., and Wang, S. I.  Cruxeval: A benchmark for code reasoning, understanding and execution.  _arXiv preprint arXiv:2401.03065_ , 2024.
  * Huang et al. (2023) Huang, K.-H., Zhou, M., Chan, H. P., Fung, Y. R., Wang, Z., Zhang, L., Chang, S.-F., and Ji, H.  Do lvlms understand charts? analyzing and correcting factual errors in chart captioning.  _arXiv preprint arXiv:2312.10160_ , 2023.
  * Imani et al. (2023) Imani, S., Du, L., and Shrivastava, H.  Mathprompter: Mathematical reasoning using large language models.  _arXiv preprint arXiv:2303.05398_ , 2023.
  * Jiang et al. (2023) Jiang, A. Q., Sablayrolles, A., Mensch, A., Bamford, C., Chaplot, D. S., Casas, D. d. l., Bressand, F., Lengyel, G., Lample, G., Saulnier, L., et al.  Mistral 7b.  _arXiv preprint arXiv:2310.06825_ , 2023.
  * Jimenez et al. (2023) Jimenez, C. E., Yang, J., Wettig, A., Yao, S., Pei, K., Press, O., and Narasimhan, K.  Swe-bench: Can language models resolve real-world github issues?  _arXiv preprint arXiv:2310.06770_ , 2023.
  * La Malfa et al. (2024) La Malfa, E., Weinhuber, C., Torre, O., Lin, F., Cohn, A., Shadbolt, N., and Wooldridge, M.  Code simulation challenges for large language models.  _arXiv preprint arXiv:2401.09074_ , 2024.
  * Li et al. (2023) Li, R., Allal, L. B., Zi, Y., Muennighoff, N., Kocetkov, D., Mou, C., Marone, M., Akiki, C., Li, J., Chim, J., Liu, Q., Zheltonozhskii, E., Zhuo, T. Y., Wang, T., Dehaene, O., Davaadorj, M., Lamy-Poirier, J., Monteiro, J., Shliazhko, O., Gontier, N., Meade, N., Zebaze, A., Yee, M.-H., Umapathi, L. K., Zhu, J., Lipkin, B., Oblokulov, M., Wang, Z., Murthy, R., Stillerman, J., Patel, S. S., Abulkhanov, D., Zocca, M., Dey, M., Zhang, Z., Fahmy, N., Bhattacharyya, U., Yu, W., Singh, S., Luccioni, S., Villegas, P., Kunakov, M., Zhdanov, F., Romero, M., Lee, T., Timor, N., Ding, J., Schlesinger, C., Schoelkopf, H., Ebert, J., Dao, T., Mishra, M., Gu, A., Robinson, J., Anderson, C. J., Dolan-Gavitt, B., Contractor, D., Reddy, S., Fried, D., Bahdanau, D., Jernite, Y., Ferrandis, C. M., Hughes, S., Wolf, T., Guha, A., von Werra, L., and de Vries, H.  Starcoder: may the source be with you!, 2023.
  * Liu et al. (2023) Liu, J., Xia, C. S., Wang, Y., and Zhang, L.  Is your code generated by chatgpt really correct? rigorous evaluation of large language models for code generation.  _arXiv preprint arXiv:2305.01210_ , 2023.
  * Luo et al. (2023) Luo, H., Sun, Q., Xu, C., Zhao, P., Lou, J., Tao, C., Geng, X., Lin, Q., Chen, S., and Zhang, D.  Wizardmath: Empowering mathematical reasoning for large language models via reinforced evol-instruct.  _arXiv preprint arXiv:2308.09583_ , 2023.
  * Miceli-Barone et al. (2023) Miceli-Barone, A. V., Barez, F., Konstas, I., and Cohen, S. B.  The larger they are, the harder they fail: Language models do not recognize identifier swaps in python.  _arXiv preprint arXiv:2305.15507_ , 2023.
  * Min et al. (2023) Min, M. J., Ding, Y., Buratti, L., Pujar, S., Kaiser, G., Jana, S., and Ray, B.  Beyond accuracy: Evaluating self-consistency of code large language models with identitychain.  _arXiv preprint arXiv:2310.14053_ , 2023.
  * Odena et al. (2021) Odena, A., Sutton, C., Dohan, D. M., Jiang, E., Michalewski, H., Austin, J., Bosma, M. P., Nye, M., Terry, M., and Le, Q. V.  Program synthesis with large language models.  In _n/a_ , pp. n/a, n/a, 2021.  n/a.
  * OpenAI (2023a) OpenAI.  Chatgpt: Optimizing language models for dialogue.  _https://openai.com/blog/chatgpt_ , 2023a.
  * OpenAI (2023b) OpenAI.  Gpt-4 technical report.  _https://arxiv.org/abs/2303.08774_ , 2023b.
  * Pan et al. (2023) Pan, R., Ibrahimzada, A. R., Krishna, R., Sankar, D., Wassi, L. P., Merler, M., Sobolev, B., Pavuluri, R., Sinha, S., and Jabbarvand, R.  Understanding the effectiveness of large language models in code translation.  _arXiv preprint arXiv:2308.03109_ , 2023.
  * Puri et al. (2021) Puri, R., Kung, D., Janssen, G., Zhang, W., Domeniconi, G., Zolotov, V., Dolby, J., Chen, J., Choudhury, M., Decker, L., Thost, V., Buratti, L., Pujar, S., and Finkler, U.  Project codenet: A large-scale ai for code dataset for learning a diversity of coding tasks.  2021\.
  * Roziere et al. (2023) Roziere, B., Gehring, J., Gloeckle, F., Sootla, S., Gat, I., Tan, X. E., Adi, Y., Liu, J., Remez, T., Rapin, J., et al.  Code llama: Open foundation models for code.  _arXiv preprint arXiv:2308.12950_ , 2023.
  * Shi et al. (2022) Shi, F., Fried, D., Ghazvininejad, M., Zettlemoyer, L., and Wang, S. I.  Natural language to code translation with execution.  _arXiv preprint arXiv:2204.11454_ , 2022.
  * Spearman (1961) Spearman, C.  The proof and measurement of association between two things.  1961\.
  * Touvron et al. (2023) Touvron, H., Martin, L., Stone, K., Albert, P., Almahairi, A., Babaei, Y., Bashlykov, N., Batra, S., Bhargava, P., Bhosale, S., et al.  Llama 2: Open foundation and fine-tuned chat models.  _arXiv preprint arXiv:2307.09288_ , 2023.
  * Valmeekam et al. (2022) Valmeekam, K., Olmo, A., Sreedharan, S., and Kambhampati, S.  Large language models still can’t plan (a benchmark for llms on planning and reasoning about change).  _arXiv preprint arXiv:2206.10498_ , 2022.
  * Wang et al. (2023) Wang, K., Ren, H., Zhou, A., Lu, Z., Luo, S., Shi, W., Zhang, R., Song, L., Zhan, M., and Li, H.  Mathcoder: Seamless code integration in llms for enhanced mathematical reasoning.  _arXiv preprint arXiv:2310.03731_ , 2023.
  * Wang et al. (2022) Wang, S., Li, Z., Qian, H., Yang, C., Wang, Z., Shang, M., Kumar, V., Tan, S., Ray, B., Bhatia, P., et al.  Recode: Robustness evaluation of code generation models.  _arXiv preprint arXiv:2212.10264_ , 2022.
  * Wei et al. (2022a) Wei, J., Tay, Y., Bommasani, R., Raffel, C., Zoph, B., Borgeaud, S., Yogatama, D., Bosma, M., Zhou, D., Metzler, D., et al.  Emergent abilities of large language models.  _arXiv preprint arXiv:2206.07682_ , 2022a.
  * Wei et al. (2022b) Wei, J., Wang, X., Schuurmans, D., Bosma, M., Xia, F., Chi, E., Le, Q. V., Zhou, D., et al.  Chain-of-thought prompting elicits reasoning in large language models.  _Advances in Neural Information Processing Systems_ , 35:24824–24837, 2022b.
  * Wei et al. (2023) Wei, Y., Wang, Z., Liu, J., Ding, Y., and Zhang, L.  Magicoder: Source code is all you need.  _arXiv preprint arXiv:2312.02120_ , 2023.
  * Wu et al. (2023) Wu, Z., Qiu, L., Ross, A., Akyürek, E., Chen, B., Wang, B., Kim, N., Andreas, J., and Kim, Y.  Reasoning or reciting? exploring the capabilities and limitations of language models through counterfactual tasks.  _arXiv preprint arXiv:2307.02477_ , 2023.
  * Xu et al. (2023) Xu, C., Sun, Q., Zheng, K., Geng, X., Zhao, P., Feng, J., Tao, C., and Jiang, D.  Wizardlm: Empowering large language models to follow complex instructions.  _arXiv preprint arXiv:2304.12244_ , 2023.
  * Yao et al. (2023) Yao, S., Yu, D., Zhao, J., Shafran, I., Griffiths, T. L., Cao, Y., and Narasimhan, K.  Tree of thoughts: Deliberate problem solving with large language models.  _arXiv preprint arXiv:2305.10601_ , 2023.
  * Zhang et al. (2024) Zhang, D., Tigges, C., Zhang, Z., Biderman, S., Raginsky, M., and Ringer, T.  Transformer-based models are not yet perfect at learning to emulate structural recursion.  _arXiv preprint arXiv:2401.12947_ , 2024.
  * Zhang et al. (2023) Zhang, K., Wang, D., Xia, J., Wang, W. Y., and Li, L.  Algo: Synthesizing algorithmic programs with generated oracle verifiers.  _arXiv preprint arXiv:2305.14591_ , 2023.
  * Zheng et al. (2023) Zheng, Q., Xia, X., Zou, X., Dong, Y., Wang, S., Xue, Y., Shen, L., Wang, Z., Wang, A., Li, Y., et al.  Codegeex: A pre-trained model for code generation with multilingual benchmarking on humaneval-x.  In _Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_ , pp. 5673–5684, 2023.
  * Zhong et al. (2022) Zhong, M., Liu, G., Li, H., Kuang, J., Zeng, J., and Wang, M.  Codegen-test: An automatic code generation model integrating program test information.  _arXiv preprint arXiv:2202.07612_ , 2022.


# Improved Lower Bounds for Property B

Karl Grill  Daniel Linzmayer
Institute of Statistics and Mathematical Methods in Economics
TU Wien

###### Abstract

If an $n$-uniform hypergraph can be 2-colored, then it is said to have
property B. Erdős (1963) was the first to give lower and upper bounds for the
minimal size $\mathbf{m}(n)$ of an $n$-uniform hypergraph without property B.
His asymptotic upper bound $O(n^{2}2^{n})$ still is the best we know, his
lower bound $2^{n-1}$ has seen a number of improvements, with the current best
$\Omega$ $(2^{n}\sqrt{n/\log(n)})$ established by Radhakrishnan and Srinivasan
(2000). Cherkashin and Kozik (2015) provided a simplified proof of this
result, using Pluhár’s (2009) idea of a random greedy coloring. In the present
paper, we use a refined version of this argument to obtain improved lower
bounds on $\mathbf{m}(n)$ for small values of $n$. We also study
$\mathbf{m}(n,v)$, the size of the smallest $n$-hypergraph without property B
having $v$ vertices.

##  1 Introduction

We consider an $n$-uniform hypergraph $H=(V,E)$ with vertex set $V$ of
cardinality $|V|=v$ and edge set

$E\subseteq\\{A\subseteq V:|A|=n\\}.$

$H$ is said to have property B if it is 2-colorable, i.e., if its vertices can
be colored with two colors (traditionally called “red” and “blue”) in such a
way that no edge is monochromatic.

We let $\mathbf{m}(n)$ denote the smallest number of edges that an $n$-uniform
hypergraph without property B must have, and $\mathbf{m}(n,v)$ the smallest
number of edges in a hypergraph with $v$ vertices that does not have property
B.

The exact values of $\mathbf{m}(n)$ are only known for $n=1,2,3,4$ so far. For
$n=5$ and higher only bounds for the true solution are known[13]. Brute force
calculation quickly reaches its limits due to the quickly increasing
complexity of the problem for increasing $n$.

Erdős and Hajnal [9] presented the first upper bound
$m(p)\leq\genfrac{(}{)}{0.0pt}{1}{2n-1}{n}.$ Erdős [10], using the
probabilistic method, obtained the bounds

$2^{n-1}\leq\mathbf{m}(n)\leq(1+o(1))e\log(2)n^{2}2^{n-2}.$ (1)

His upper bound is still the best asymptotic result available, though some
improvements have been made for small $n$ by constructive means.

In [8], for even $v=O(n)$, he proves the bounds

$\frac{\genfrac{(}{)}{0.0pt}{1}{v}{n}}{2\genfrac{(}{)}{0.0pt}{1}{v/2}{n}}\leq\mathbf{m}(n,v)\leq
2v\frac{\genfrac{(}{)}{0.0pt}{1}{v}{n}}{2\genfrac{(}{)}{0.0pt}{1}{v/2}{n}}.$
(2)

This actually holds for any even $v>2n$, but for $v>n^{2}/2$ this is worse
than (1), which is obtained for $v=n^{2}/2$. So, for any $v$, we have upper
and lower bounds for $\mathbf{m}(n,v)$ that differ only by a factor of order
$O(n^{2})$. This is still quite big, but its polynomial growth is slower than
the exponential growth of the bounds on $\mathbf{m}(n,v)$, a fact that will be
important in our later considerations.

As for the lower bound, Goldberg and Russell[11] observed that for the
smallest $v$ with $\mathbf{m}(n,v)\leq m$, a hypergraph with $v$ vertices
achieving this bound must have the property that every pair of vertices is
contained in some edge, which, by Schoenheim’s bound, implies

$m\geq\lceil\frac{v}{n}\lceil\frac{v-1}{n-1}\rceil\rceil.$ (3)

Together with the random coloring bound

$\mathbf{m}(n,v)\geq\frac{\genfrac{(}{)}{0.0pt}{1}{v}{n}}{\genfrac{(}{)}{0.0pt}{1}{\lfloor
v/2\rfloor}{n}+\genfrac{(}{)}{0.0pt}{1}{\lceil v/2\rceil}{n}},$ (4)

this gives

$\mathbf{m}(n)\geq\min_{v}\max\left(\lceil\frac{v}{n}\lceil\frac{v-1}{n-1}\rceil\rceil,\left\lceil\frac{\genfrac{(}{)}{0.0pt}{1}{v}{n}}{\genfrac{(}{)}{0.0pt}{1}{\lfloor
v/2\rfloor}{n}+\genfrac{(}{)}{0.0pt}{1}{\lceil
v/2\rceil}{n}}\right\rceil\right).$ (5)

Beck [2, 3] used a recoloring of a random coloring and succeeded in proving
$2^{-n}\mathbf{m}(n)\to\infty$. Later Spencer [16] strengthened and simplified
Beck’s argument. This idea was carried further by Radhakrishnan and Srinivasan
[17], yielding the best lower bound currently known

$\mathbf{m}(n)=\Omega(2^{n}\sqrt{n/\log(n)}).$

Cherkashin and Kozik [4] gave a simpler proof of this result, using the greedy
coloring approach introduced by Pluhár [14]. We study this approach in more
detail in the next section.

Many of these results generalize to more than two colors. The survey article
by Raigorodskii and Cherkashin [15] gives an account of various results along
with their proofs.

##  2 Greedy Coloring

Pluhár [14] introduced a greedy coloring procedure: one starts with all
vertices red and arranges them in random order. Then one looks at the vertices
in sequence, changing the color of a vertex to blue if it is the last one in
an otherwise all-red edge.

By the nature of this algorithm, no monochromatic red edge can occur, and it
is obvious that for a two-colorable hypergraph there is an ordering of the
vertices for which the greedy algorithm yields a proper coloring. As the
dependence of this procedure on the number of vertices is a bit of a nuisance,
Pluhár [14] introduced the notion of assigning independent, uniformly $[0,1]$
distributed weights to the vertices and arranging them in increasing order of
their weights.

Using this idea, he obtained a simpler proof of the fact that
$\mathbf{m}(n)2^{-n}\to\infty$, although his result was weaker than that of
Radhakrishnan and Srinivasan. The next step was performed by Cherkashin and
Kozik [4]. They utilized the random greedy coloring method to construct a
simpler proof for Radhakrishnan and Srinivasan’s asymptotic result.

The central idea is the following: greedy coloring can only fail if it
produces a blue edge. By the nature of the coloring procedure, the first
vertex in this edge must be the last vertex in some other (otherwise red)
edge. Thus, the probability that coloring fails can be estimated above by the
probability that some vertex is the last one in some edge and the first in
some other at the same time. We call such a vertex critical. Given that there
is a vertex with weight $x$, we can bound the conditional probability that it
is critical by each of the three probabilities that it is the last vertex in
some edge, that it is the first in some edge, or that both hold at the same
time. This yields the estimate

$\mathbb{P}(\mbox{Greedy coloring
fails})\leq\int_{0}^{1}\min(mnx^{n-1},mn(1-x)^{n-1},\gamma
x^{n-1}(1-x)^{n-1})dx,$ (6)

where $m$ is the number of edges, and $\gamma$ is the number of ordered pairs
of edges that have exactly one vertex in common. In some cases, one can find
good estimates for $\gamma$, but most of the time we have to make do with the
trivial bound $\gamma\leq m(m-1)$. It is easily seen that the right-hand side
of (6) is the minimum of

$2mx^{n}+\gamma\int_{x}^{1-x}u^{n-1}(1-u)^{n-1}du$ (7)

If this is less than $1$, then there is a positive probability that greedy
coloring succeeds, and so $\mathbf{m}(n)>m$. Cherkashin and Kozik [4] weaken
this by applying the inequalities $u(1-u)\leq 1/4$ and $\gamma\leq m^{2}$ to
obtain Radhakrishnan and Srinivasan’s [17] result; Aglave et al. [1] reduce
the case $n=5$, $m=28$ to $v=23$, as all other values of $v$ are ruled out by
(3) and (4). They improve the upper bound on $\gamma$ to $\gamma\leq 670$,
which is enough to give a value less than $1$ in equation (7), proving
$\mathbf{m}(5)\geq 29$.

We go back to considering $\mathbf{m}(n,v)$ with its explicit dependence on
the number of vertices $v$. As a consequence, instead of the continuous
distribution of the weights, we can work directly with the discrete
distribution of the random permutation. By the same reasoning that led us to
(6), we can get an upper bound for the probability $p$ that there is a
critical vertex:

$p\leq\sum_{k=0}^{v}p(k),$

where $p(k)$ denotes the probability that the vertex in position $k$ is
critical; this can be estimated above by

$\sum_{k=0}^{v}p(k)\leq\sum_{k=0}^{v}\frac{1}{v}\min\left(mn\frac{\genfrac{(}{)}{0.0pt}{1}{k-1}{n-1}}{\genfrac{(}{)}{0.0pt}{1}{v-1}{n-1}},mn\frac{\genfrac{(}{)}{0.0pt}{1}{v-k}{n-1}}{\genfrac{(}{)}{0.0pt}{1}{v-1}{n-1}},\gamma\frac{\genfrac{(}{)}{0.0pt}{1}{k-1}{n-1}\genfrac{(}{)}{0.0pt}{1}{v-k}{n-1}}{\genfrac{(}{)}{0.0pt}{1}{v-1}{n-1}\genfrac{(}{)}{0.0pt}{1}{v-n}{n-1}}\right).$
(8)

It may be worth noting that for $v\to\infty$, the right-hand side of (8)
converges to (6) and, of course, the three terms in the minimum are bounds for
the probabilities that $k$ is the last vertex in some edge, the first in some
edge, or both.

In equation (8), the first term in the minimum is smaller than the second for
$k<\lfloor(v+1)/2\rfloor$, and if the smaller of these is not greater than the
third, then the right-hand side evaluates as

$m\frac{\genfrac{(}{)}{0.0pt}{1}{\lfloor
v/2\rfloor}{n}+\genfrac{(}{)}{0.0pt}{1}{\lceil
v/2\rceil}{n}}{\genfrac{(}{)}{0.0pt}{1}{v}{n}},$

so we can only get an improvement over (4), if, for some $k<(v+1)/2$, we have

$\gamma\genfrac{(}{)}{0.0pt}{0}{v-k}{n-1}<mn\genfrac{(}{)}{0.0pt}{0}{v-n}{n-1}.$

As long as we do not have a better estimate than $\gamma\leq m(m-1)$, (2)
implies that we need

$\genfrac{(}{)}{0.0pt}{0}{v-1}{n-1}<n\genfrac{(}{)}{0.0pt}{0}{v-n}{n-1},$ (9)

which in turn implies $v>\frac{n^{2}}{\log(n)}(1+o(1))$.

We can make some slight improvements to our estimate of $\gamma$: on one hand,
if we know that a certain pair of vertices is contained in $r$ edges, then
obviously

$\gamma\leq m(m-1)-r(r-1),$

and another upper bound is obtained by counting the pairs that have a certain
vertex in common: let $l_{i}$ denote the number of occurrences of vertex $i$,
and $r_{i}$ the maximum frequency of a pair $\\{i,j\\},j\neq i$. Then

$\gamma\leq\sum_{i=1}^{v}\left(l_{i}(l_{i}-1)-r_{i}(r_{i}-1)\right).$

Using these ideas, we calculated lower bounds, letting $n$ vary in the range
$5$ to $9$, and $v$ from $2n+1$ to $200$. In fact, in tune with our
considerations in (9), we observe that, for small values of $v$, our bound and
the Goldberg-Russell bound (5) agree. For $n=5$, we get improved lower bounds
for $17\leq v\leq 25$.

For these calculations and those mentioned below, we use small C programs. As
all the probabilities in question, apart from the continuous Cherkashin-Kozik
bound (7) are rational, we can perform exact calculations using an appropriate
bignum library, we chose GNU libgmp. Multiplying with a common denominator, we
can work with integers, which yields a considerable improvement of efficiency
over rational number computations.

For other values of $n$, too, this procedure gives us improved lower bounds
for $\mathbf{m}(n)$. We summarize these bounds for small values of $n$
together with those obtained from Cherkashin and Kozik’s [4] continuous
procedure, that is independent of $v$, and the basic estimate by Goldberg and
Russell [11] in table 1. For the sake of completeness, we have also included
the best known upper bounds as reported in [1].

$n$ | $5$ | $6$ | $7$ | $8$ | $9$
---|---|---|---|---|---
Goldberg and Russell [11] | 28 | 51 | 94 | 174 | 328
Cherkashin and Kozik [4] | 27 | 57 | 119 | 248 | 516
Discrete greedy eq. (8) | 30 | 62 | 126 | 259 | 533
Current upper bound [1] | 51 | 147 | 421 | 1212 | 2401
Table 1: First lower bounds

It should be mentioned that, although we get improved lower bounds for some
finite values of $n$, this approach does not change the asymptotic result. As
a matter of fact, the sum in (8), properly normalized, converges to the
integral in (6).

##  3 Locking a vertex in place

We consider a particular pair of edges that have only one vertex in common.
The probability that this pair becomes critical with their common point in
position $k$ evaluates as

$\frac{\genfrac{(}{)}{0.0pt}{1}{k-1}{n-1}\genfrac{(}{)}{0.0pt}{1}{v-k}{n-1}}{v\genfrac{(}{)}{0.0pt}{1}{v-1}{n-1}\genfrac{(}{)}{0.0pt}{1}{v-n}{n-1}}.$

This takes its maximum for $k=\lceil v/2\rceil$. Thus, it seems plausible that
we might be able to improve our estimates by locking a vertex with a small
degree in place there. So, let $l$ denote the smallest degree of a vertex, and
let us put the associated vertex in position $v_{1}=\lceil v/2\rceil$. There
are $l$ edges that contain the selected vertex, and $m-l$ that don’t. By the
pigeon-hole principle, we know that

$\frac{v-1}{n-1}\leq l\leq\frac{mn}{v}:$

for the lower bound, remember that we assume that all pairs $\\{i,j\\}$ with
$j\neq i$ be contained in some edge, so $l(n-1)\geq v-1$, and on the other
hand, the sum of all $v$ vertex degrees is $mn$, so $lv\leq mn$.

This assumption changes our bounds for the various probabilities, e.g., for
$k<v_{1}$ we have

$p_{1}(k)=n(m-l)\frac{\genfrac{(}{)}{0.0pt}{1}{k-1}{n-1}}{(v-1)\genfrac{(}{)}{0.0pt}{1}{v-2}{n-1}},$
$p_{2}(k)=n(m-l)\frac{\genfrac{(}{)}{0.0pt}{1}{v-k-1}{n-1}}{(v-1)\genfrac{(}{)}{0.0pt}{1}{v-2}{n-1}}+nl\frac{\genfrac{(}{)}{0.0pt}{1}{v-k-1}{n-2}}{(v-1)\genfrac{(}{)}{0.0pt}{1}{v-2}{n-2}},$
$p_{3}(k)=(m-l)(m-l-1)\frac{\genfrac{(}{)}{0.0pt}{1}{k-1}{n-1}\genfrac{(}{)}{0.0pt}{1}{v-k-1}{n-1}}{(v-1)\genfrac{(}{)}{0.0pt}{1}{v-2}{n-1}\genfrac{(}{)}{0.0pt}{1}{v-n-1}{n-1}}+(m-l)l\frac{\genfrac{(}{)}{0.0pt}{1}{k-1}{n-1}\genfrac{(}{)}{0.0pt}{1}{v-k-1}{n-2}}{(v-1)\genfrac{(}{)}{0.0pt}{1}{v-2}{n-1}\genfrac{(}{)}{0.0pt}{1}{v-n-1}{n-2}}$

as upper bounds for the probabilities that the vertex in position $k$ is last
in some edge, first in some edge, or both.

As it turns out, this approach serves to improve our lower bounds to
$\mathbf{m}(5)\geq 31$, $\mathbf{m}(6)\geq 63$, $\mathbf{m}(7)\geq 127$,
$\mathbf{m}(8)\geq 261$ and $\mathbf{m}(9)\geq 537$.

We can go further and fix more than one vertex in the center spots.
Unfortunately, this quickly gets complicated, as we have to control the
numbers of edges that contain a particular subset of the selected vertices,
which amounts to $2^{s}-1$ numbers for $s$ selected vertices. In the case
$s=2$, we need to control the numbers $l_{1}$, $l_{2}$ and $l_{12}$ of edges
containing only the first selected vertex, only the second, or both. This is
still simple enough to carry out the calculations for all combinations of $n$
and $v$ that we considered in the previous section. In this way, we obtain the
improvements $\mathbf{m}(7)\geq 128$ and $\mathbf{m}(8)\geq 262$.

The case $s=3$ affords working with the seven numbers $l_{A}$ of edges
containing exactly the (non-empty) subset $A$ of $\\{1,2,3\\}$. We apply this
to selected combinations of $n$, $m$, and $v$. This by itself is enough to
give us $\mathbf{m}(5)\geq 32$. For $n=6$ and above, we do not get an
immediate improvement. For $n=6$, we need to check the values of $v$ from $39$
to $42$. It turns out that our upper bound for the probability that greedy
coloring fails is less than $1$ for all cases except $L_{1}=L_{2}=9$ and
$L_{12}\geq 2$ (we use $L_{A}$ to denote the number of edges that contain $A$
as a subset, so, for example $L_{1}=l_{1}+l_{12}+l_{13}+l_{123}$, which equals
the degree of vertex $1$). The sum of all vertex degrees is $6\cdot 63=378$
and every vertex degree is at least $9$, amounting for a total of at least
$39\cdot 9=351$. This only leaves room for at most $23$ vertices with a degree
greater than $9$. So, at least $16$ vertices must have a degree equal to $9$.
If we pick one of those, call it $1$, the sum of the numbers of pairs
involving it is 45. Every such pair must occur at least once, leaving at most
$6$ pairs that can occur more than once. Thus, we can find another vertex of
degree $9$, call it $2$, such that the pair $(1,2)$ has only one occurrence.
Choosing these two vertices as the marked ones, we get $L_{1}=L_{2}=9$ and
$L_{12}=1$. For these parameters, the greedy algorithm succeeds with positive
probability, and we arrive at $\mathbf{m}(6)\geq 64$. Similar arguments work
for eliminating $n=8,m=262$ and $n=9,m=537$, so we can summarize

######  Theorem 1.

We have the lower bounds

$\mathbf{m}(5)\geq 32,\mathbf{m}(6)\geq 64,\mathbf{m}(7)\geq
128,\mathbf{m}(8)\geq 263,\mathbf{m}(9)\geq 538.$

##  4 The case $v=2n+1$

The case $v=2n+1$ is interesting, because it is the smallest number of
vertices for which $\mathbf{m}(n,v)$ is not known for all values of $n$, and
because of its close relation with other covering questions. In particular, de
Vries[6] showed that the Goldberg-Russell lower bound

$v(n,2n+1)\geq\frac{\genfrac{(}{)}{0.0pt}{1}{2n+1}{n}}{n+2}$

is attained if and only if the associated hypergraph is a $(n-1,n,2n+1)$
Steiner system, i.e., if every $n-1$-subset of $V$ is contained in exactly one
of the hyperedges. It is worth noting that this lower bound is $C_{n+1}/2$,
where $C_{n}$ denotes the $n$-th Catalan number. $C_{n}$ is known to be odd
iff $n$ is of the form $n=2^{k}-1$[5], so we find that for $n=2^{k}-2$ the
lower bound $C_{n+1}/2$ is not an integer, so it cannot be attained. De Vries’
result, combined with the well-known fact that a $(3,4,v)$-Steiner system
exists iff $v\equiv 4,6\pmod{6}$ [12], even gives that
$\mathbf{m}(n,2n+1)>C_{n+1}/2$ if $n\not\equiv 3,5\pmod{6}$. For particular
values of $n$, we can push this a bit further:

######  Theorem 2.

For $n=2^{k}-2$, $k\geq 3$

$\mathbf{m}(n,2n+1)\geq(C_{n+1}+3)/2,$

and for $n=2^{r}(2^{2k}+1)-2$, $r,k\geq 1$, in particular for $n=2^{2k+1}$,
$k\geq 1$,

$\mathbf{m}(n,2n+1)\geq C_{n+1}/2+3.$

For the proof, we exploit our analysis for the greedy algorithm with one and
two fixed vertices. We let

$m_{0}=\frac{C_{n+1}}{2}=\frac{(2n+1)!}{n!(n+2)!}$

and

$L_{0}=\frac{m_{0}n}{2n+1}=\frac{(2n)!}{(n-1)!(n+2)!}=\frac{1}{n-1}\genfrac{(}{)}{0.0pt}{1}{2n}{n-2}==\frac{1}{n+2}\genfrac{(}{)}{0.0pt}{1}{2n}{n-1}.$

The last two terms show that the denominator in the representation of $L_{0}$
as a reduced fraction is a common divisor of $n-2$ and $n+1$. By our
assumptions, $n-1$ is not a multiple of $3$, so $L_{0}$ is an integer.

Let us now look at a hypergraph with $m=m_{0}+x$ edges. A critical vertex can
only occur in position $n$, $n+1$, or $n+2$.

If we lock a vertex with minimal degree $L_{1}$ (we will call it “1” in the
future) in position $n+1$, we can bound the probability that $n$ is critical
by the probability that it is the last in some edge, which in turn is bounded
by

$\frac{m-L_{1}}{\genfrac{(}{)}{0.0pt}{1}{2n}{n}},$

and the same bound applies to the probability that $n+2$ is critical.
Similarly, the probability that $n+1$ is critical is bounded by

$\frac{L_{1}\genfrac{(}{)}{0.0pt}{1}{n}{n-1}}{\genfrac{(}{)}{0.0pt}{1}{2n}{n-1}}.$

From these, we obtain the upper bound

$\frac{(n!)^{2}(2m+L_{1}(n-1))}{(2n)!}$

for the probability that there is a critical vertex.

The pigeonhole principle implies

$L_{1}\leq\frac{mn}{2n+1}=\frac{(m_{0}+x)n}{2n+1}=L_{0}+\frac{xn}{2n+1}.$

For $x\leq 2$ this upper bound is less then $L_{0}+1$, so we obtain $L_{1}\leq
L_{0}$. For $L_{1}<L_{0}$, our upper bound for the probability of a critical
vertex is at most

$1+\frac{(n!)^{2}(2x+1-n)}{(2n)!}<1,$

so we are left with the case $L_{1}=L_{0}$. We lock the vertex with the second
largest degree $L_{2}$ (call it “2”) in position $n+2$. We let $L_{12}$ denote
the number of edges containing both vertices 1 and 2. There are
$l_{1}=L_{1}-L_{12}$ edges containing vertex 1 but not 2, $l_{2}=L_{2}-L_{12}$
containing vertex 2 alone, and $l_{0}=m-L_{1}-L_{2}+L_{12}$ edges containing
neither 1 nor 2. We get upper bounds

$\frac{l_{0}}{\genfrac{(}{)}{0.0pt}{1}{2n-1}{n}}$

and

$\frac{l_{2}}{\genfrac{(}{)}{0.0pt}{1}{2n-1}{n-1}}$

for the probabilities that $n$ resp. $n+2$ are critical. For $n+1$, we have
the two upper bounds

$\frac{l_{1}n}{\genfrac{(}{)}{0.0pt}{1}{2n-1}{n-1}}$

and

$\frac{l_{1}}{\genfrac{(}{)}{0.0pt}{1}{2n-1}{n-1}}+\frac{L_{12}(n-1)}{\genfrac{(}{)}{0.0pt}{1}{2n-1}{n-2}}.$

Thus, the probability that there is a critical vertex is at most

$\frac{n!(n-1)!(l_{0}+l_{2}+\min(nl_{1},l_{1}+L_{12}(n+1)))}{(2n-1)!}=$
$\frac{n!(n-1)!(2m+(n-1)L_{1}-2n|L_{12}-L_{12}^{0}|)}{2(2n-1)!}=$
$1+\frac{n!(n-1)!(x-n|L_{12}-L_{12}^{0}|)}{(2n-1)!},$

where we have put

$L_{12}^{0}=\frac{L_{0}(n-1)}{2n}=\frac{m_{0}(n-1)}{2(2n+1)}=\frac{(2n-1)!}{(n-2)!(n+2)!}.$

By theorem 2.1 in [5], the multiplicity of $2$ as a factor of $C_{n}$ is one
less than the number of digits $1$ in the binary representation of $n+1$. From
this, we can conclude that $L_{12}^{0}$ is not an integer, but $4L_{12}^{0}$
is. Thus $|L_{12}-L_{12}^{0}|\geq 1/4$, and we get an upper bound less than
$1$ for the probability that a critical vertex exists.

##  5 Conclusion

We were able to obtain improved lower bounds for $\mathbf{m}(n)$ and
$\mathbf{m}(n,v)$ for selected values of $n$ and $v$, in particular we could
improve the lower bound $\mathbf{m}(5)\geq 29$ from [1] to $\mathbf{m}(5)\geq
32$.

We hope that our method can be extended to obtain an improvement of the
asymptotic lower bound. To this end, we would need to let the number of fixed
vertices go to infinity as $n$ increases. In order to still obtain
sufficiently small upper bounds for the probabilities of criticality, this
needs to be combined with a tight control of the joint occurrences of the
selected vertices.

##  6 Acknowledgements

We are very gratefully to Prof. Cherkashin for his valuable remarks and
suggestions.

## References

  * [1] Aglave, S., Amarnath, V.A., Shannigrahi, S. Singh, S., “Improved Bounds for Uniform Hypergraphs without Property B”, Australasian Journal of Combinatorics, Volume 76(1) (2020), 73–86.
  * [2] Beck, J. “On a Combinatorial Problem of P. Erdős and L. Lovász”, Discrete Mathematics 17 (1977), 127–131.
  * [3] Beck, J. “On 3-chromatic Hypergraphs”, Discrete Mathematics, 24(2) (1978), 127–137.
  * [4] Cherkashin, D., Kozik, J., “A note on random greedy coloring of uniform hypergraphs”, Random Structures and Algorithms 47 (3) (2015), 407–413.
  * [5] Deutsch, E., Sagan, B.E., “Congruences for Catalan and Motzkin numbers and related sequences”, J. Number Theory 117 (2006), 191–215. doi:10.1016/j.jnt.2005.06.005.
  * [6] de Vries, H.L., “On property B and on Steiner systems”, Math. Z. 153(2) (1977), 153–159, doi:10.1007/BF01179788.
  * [7] Erdős, P., “On a combinatorial problem”, Nordisk Mat. Tidskrift 11 (1963), 5–10.
  * [8] Erdős, P., “On a combinatorial problem III”, Canad. Math. Bull.12 (4) (1969),413–416. doi:10.4153/CMB-1969-051-5.
  * [9] Erdős, P, and Hajnal, A. “A Property of a Family of Sets”, Acta Math. Hung. 12(1) (1961), 87–123, doi:10.1007/BF02066676.
  * [10] Erdős, P., and Spencer, J., “Probabilistic Methods in Combinatorics”, Akadémiai Kiadó, Budapest, 1974.
  * [11] Goldberg, M.K., and Russell, H.C., “Toward computing m(4)”, Ars Combin. 39(1995), 139–148.
  * [12] Hanani, M. “On Quadruple Systems”, Canad. J. Math. 12 (1960), 145–157.
  * [13] P. Østergård, R.J., “On the minimum size of 4-uniform hypergraphs without property B”, Discrete Appl. Math. 163 (2) (2014), 199–204.
  * [14] Pluhár, A., “Greedy colorings of uniform hypergraphs”, Random Structures and Algorithms 35 (2009) 216–221. doi:10.1002/rsa.20267.
  * [15] Raigorodskii, A.M., and Cherkashin, D.D., ‘Extremal problems in hypergraph coloring”, Russian Math. Surveys 75:1 (2020), 89–146, doi:10.1070/RM9905.
  * [16] Spencer, J. “Coloring $n$-Sets Red and Blue”, J. Comb. Theory Ser. A 30 (1981), 112–113, doi:10.1016/0097-3165(81)90045-5.
  * [17] Radhakrishnan, J,. and Srinivasan, A., “Improved bounds and algorithms for hypergraph 2-coloring”, Random Structures Algorithms 16(1) (2000), 4–32.