# Kolmogorov time hierarchy and novelty games

Ulysse Léchine, Thomas Seiller

► To cite this version:

Ulysse Léchine, Thomas Seiller. Kolmogorov time hierarchy and novelty games. 2024. hal-04539439

HAL Id: hal-04539439

https://hal.science/hal-04539439

Preprint submitted on 9 Apr 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Kolmogorov time hierarchy and novelty games

Ulysse Léchine, Thomas Seiller

► To cite this version:

Ulysse Léchine, Thomas Seiller. Kolmogorov time hierarchy and novelty games. 2025. hal-04539439v3

HAL Id: hal-04539439

https://hal.science/hal-04539439v3

Preprint submitted on 2 May 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Kolmogorov time hierarchy and novelty games

Ulysse Léchine

LIPN, IRIF

lechine@lipn.univ-paris13.fr

Thomas Seiller

CNRS

thomas.seiller@cnrs.fr

Abstract

In this paper we improve on the state-of-the-art time hierarchy for
time-bounded Kolmogorov complexity. More precisely, we prove that
there are infinitely many $n \in \mathbb{N}$ such that there are strings of size $n$
which are the output of programs of size $f = o(\log n)$ running in $o(2^f T)$
steps but are not the output of any program of size $f$ running in $T$ steps.
The previous gap was exponential in $2^f$. This result is established by
studying a new problem in combinatorics: a list $E$ of $pk$ numbers in
$[1; N]$ is shared evenly between $p$ players, who each get to output an
answer depending on their share of $E$. The players must establish
a communication-free strategy ensuring that one of them outputs a
number not belonging to $E$.

# 1 Introduction

The Kolmogorov complexity of a word $w \in \{0; 1\}^*$ is the size of the smallest program $p$ which prints $w$ and stops. This gives rise to a natural encoding of words: a word can be encoded/described by a program which prints it. To "decode" a program one just runs it until it stops, obtaining in this way the original word. But decoding those, i.e. running the programs, may take some time. We thus may consider time-bounded Kolmogorov complexity, where one restricts to programs of size $f(n)$ running in time $T(n)$.

It is known that allowing programs to have a larger size leads to encod-
ing strictly more words, meaning that for all $f$ there exists words having a
description of size $f + 10$ but no description of size $f$. Can this result be
extended when considering bounded time? For arbitrary $T$, are there words
which can be printed by programs running in $2T$ steps but not by programs
running in $T$ steps? Stated otherwise: if we denote by $[f, T](n)$ the set of
strings of length $n$ outputted by a program of length $f(n)$ running in time
$T(n)$ $^1$, how do $[f, T_1](n)$ and $[f, T_2](n)$ compare? More specifically: given
$\alpha > 0$, is $[f, \alpha T](n)$ strictly bigger than $[f, T](n)$? A first remark is that we
have to restrict our considerations to words of a given size, smaller than the

<footnote n="1">¹Actually running in $T(n)$ steps when simulated through a universal Turing Machine; this is detailed and discussed later.</footnote>
# Kolmogorov time hierarchy and Novelty games

ULYSSE LÉCHINE, Université Sorbonne Paris Nord, France

THOMAS SEILLER*, CNRS, France

In this paper we improve on the state-of-the-art time hierarchy for time-bounded Kolmogorov complexity. More precisely, we prove that there are infinitely many $n \in \mathbb{N}$ such that there are strings of size $n$ which are the output of programs of size $f = o(\log n)$ running in $o(2^f T)$ steps but are not the output of any program of size $f$ running in $T$ steps. The previous gap was in $O(2^f T)$. This result is established by studying a new problem in combinatorics – which we call novelty games: a list $E$ of $pk$ numbers in $[1; N]$ is shared evenly between $p$ players, who each get to output an answer depending on their share of $E$. The players must establish a communication-free strategy ensuring that one of them outputs a number not belonging to $E$.

CCS Concepts: • Theory of computation → Computational complexity and cryptography; • Mathematics of computing → Discrete mathematics.

Additional Key Words and Phrases: Kolmogorov Complexity, Time hierarchy, Combinatorial game

## 1 INTRODUCTION

The Kolmogorov complexity of a word $w \in \{0,1\}^*$ is the size of the smallest program $p$ that prints $w$ and stops. This gives rise to a natural encoding of words: a word can be encoded/described by a program that prints it. To "decode" a program, one just runs it until it stops, obtaining in this way the original word. But decoding those, i.e. running the programs, may take some time. We may thus consider the time-bounded Kolmogorov complexity, where one restricts to programs of size $f$ running in time $T$.

It is known that allowing programs to have a larger size leads to encoding strictly more words, meaning that for all $f$ there exist words having a description of size $f + 10$ but no description of size $f$. Can a similar result be obtained for time bounds? For arbitrary $T$, are there words which can be printed by programs running in $2T$ steps but not by programs running in $T$ steps? We note that it is important to restrict our considerations to words of a given size, smaller than the allotted time bound. Indeed, the question becomes trivial otherwise: with 2000 time steps, one can write the string $1^{1900}$, but this is not possible in 1800 time steps. We therefore fix a size for our outputs and only consider time bounds larger than this size. Generally stated, the question becomes: Let $f, T$ be two functions, if we denote by $[f,T](n)$ the set of strings of length $n$ outputted by a program of length $f(n)$ running in time $T(n)^1$, how do $[f, T_1](n)$ and $[f, T_2](n)$ compare?

This question, quoted in Li and Vitányi's reference textbook [15], is a very natural question to ask when it comes to time-bounded Kolmogorov complexity. It is similar to the time hierarchy theorem, a standard result in complexity theory which states that one can solve strictly more decision problems if one allows Turing machines to run for longer. It would seem at first glance that one could use the time hierarchy theorem to solve the problem

<footnote>*T. Seiller was partially supported by the ANR ANR-22-CE48-0003-01 project DYSCO.</footnote>

<footnote n="1">¹Actually running in $T(n)$ steps when simulated through a universal Turing Machine; this is detailed and discussed later.</footnote>
allotted time bound. Indeed, the question becomes trivial otherwise: with 2000 time steps one can write the string $1^{1900}$, but this is not possible in 1800 time steps. We therefore fix a size for our outputs and only consider time bounds larger than this size.

This open question, quoted in [6], is a very natural question to ask when it comes to time bounded Kolmogorov complexity. It is similar to the time hierarchy theorem, a standard result in complexity theory which states that one can solve strictly more decision problems if one allows Turing machines to run for longer. It would seem at first glance that one could use the time hierarchy theorem to solve the problem of the "Kolmogorov time hierarchy", but that line of reasoning has not proven successful.

In his thesis [8], Luc Longpré proves that<fnref n="2" />

$$ \exists_{\infty} n, [f, T](n) \subsetneq [f, c2^f T](n), $$

where $\subsetneq$ means “is included but not equal to”, and $\exists_{\infty} n$ means that this is true for an infinite number of values of $n$. This result establishes that with exponentially more time in the size of the programs one can prove that it is possible to output new strings. Whether one can lower that $2^{f(n)}$ exponential factor has been an open question since Longpré’s result. In this paper, we provide a (partial) positive answer.

Longpré proves his result using a standard diagonalization technique, considering a program running all programs of size $f$ (there are $2^f$ of them) for $T$ steps each, hence the $2^f T$ time factor, and outputting a string which is not the output of one of those programs. In order to improve on the result, we exploit the following idea: we want to consider several programs each running a fraction of those $2^f$ programs. These programs will therefore run for less long, allowing us to get a better bound in the theorem. Of course the problem now is that each of the program will only see a fraction of the possible outputs of programs of size $f$. How can one ensure that they can still output a new string?

We first notice that only one of those programs has to output a new string. The question can then be expressed as a new combinatorics problem presented in section 4, called novelty games, describing how they can coordinate to achieve that. We then establish a solution to this combinatorics problem which we then use to get a better Kolmogorov time hierarchy theorem than Longpré for size functions $f = o(\log(n))$. The factor $o(\log(n))$ is directly related to bounds on the solution we obtain for novelty games. Better bounds for novelty games would thus translate (modulo some technicalities) into a better bounded time hierarchy theorem. We call this method

<footnote n="2">²Longpré are also establishes variants of this theorem using space, which we do not mention in this paper.</footnote>
of the "Kolmogorov time hierarchy", but we prove that this line of reasoning cannot be successful in part 8.

In his PhD thesis [17], Luc Longpré gives a first answer by proving that with exponentially more time in the size of the programs, one can output new strings. His proof is based on a standard diagonalization argument.

**THEOREM 1 (TIME HIERARCHY FOR $K^t$ COMPLEXITY (EXPONENTIAL GAP) LONGPRE [17].)** Let $f, T$ be two reasonable functions (see definition 3.6) from $N$ to $N$ in $DTIME(T(n))$ additionally where $T(n) \ge n$ and $f(n) < n$ then<fnref n="2" />

$$ \exists_{\infty} n, [f, T](n) \subsetneq [f, O(2^{2f}T)](n), $$

If we have additionally that $f = \omega(\log(n))$ then

$$ \forall_{\infty} n, [f, T](n) \subsetneq [f, O(2^{2f}T)](n), $$

Whether one can lower this $2^{2f}(n)$ factor to some other subexponential factor has been an open question since Longpré's result. The purpose of this article is to provide a (partial) positive response.

**Results** In this paper we show the following result, using a technique we call *parallel diagonalization with advice*.

**THEOREM 2 (K^t HIERARCHY IN THE TM (RESP. RAM) MODEL).** Let $T$ and $f$ be reasonable and $VTC^3$ functions of $N \mapsto N$ in $DTIME(T(n))$ such that $T(n) \ge n \log(n)$ (resp. $T(n) > n$) and $f(n) = o(\log(n))$. Let $\alpha = \max(\frac{f^{2f}}{\log n}, \sqrt{f})$ then

$$ \exists_{\infty} n, [f, O(\alpha T)](n) \not\subsetneq [f, T](n). $$

We can check that $\alpha$ is indeed $o(2^f)$ for all $f = o(\log)$, thus establishing a better result than Longpré.

To establish theorem 2 we use a novel proof method which relies on a winning strategy for a novel problem we introduce called *novelty games*. In later sections, we establish several winning strategies for novelty games and obtain several upper bounds.

We now expose the intuitions behind our method to lower this gap and obtain $[f, \alpha T] > [f, T]$. Longpré proves his result using a standard diagonalization technique. Let us describe it at a high level: one considers a program (called *simulant*) that simulates the $2^f$ programs of size $f$ (called *simulees*) for $T$ steps each. This incurs the $2^f T$ time factor. The simulees may or may not output a string (called *outee*) during these $T$ steps. The simulant then outputs a string (called *outant*) which is different from all the outees (see figure 1).

In order to improve on Longpré's result, we exploit the following idea: what if we had $2^f/\alpha$ simulants each simulating only $\alpha$ simulees (see figure 2)? These simulants would run for $\alpha T$, allowing us to improve the end bound in the theorem. But since each simulant only knows a fraction of the outees, the difficulty now becomes ensuring that at least one outant is different from all the outees. To do so, the simulants would need to execute some kind of strategy to ensure one of them outputs an outant different from all outees. Establishing such a strategy is the main hurdle of our paper.

Forgetting the Kolmogorov setting for a moment, the question can be expressed as a new combinatorics problem presented in section 4, called *novelty games*. The problem goes as

<footnote n="2">²$\exists_{\infty} n$ means that there are infinitely many $n$, $\forall_{\infty} n$ means for all sufficiently large $n$</footnote>

<footnote n="3">³defined in definition 3.6 and definition 3.5</footnote>
"parallel diagonalization with advice": the epithet "parallel" is self explanatory, while "with advice" refers to the fact that we can give some additional information to the programs. We believe this technique may have implications elsewhere in complexity theory. The analysis of novelty games may also be of independent interest to researchers in combinatorics.

Kolmogorov time bounded complexity has been studied these recent years and used for breakthrough results in meta complexity [5] [7] [4], but not only [3] [9].

## 1.1 Outline

Here is a succinct outline of the paper. In section 2, we establish notations and provide some background on time-bounded kolmogorov complexity. Section 3 then provides a high level view of the paper and of our technique. The remaining sections then contain the technical material. We define the new combinatorial problem – which we call *novelty games* – in Section 4. We also prove general results and give winning strategies for these games on specific cases. In Section 5 we formally define the program in $[f, c2^fT](n)$ but not in $[f, T](n)$ assuming the existence of a general winning strategy for novelty games. We then present such a strategy in Section 6. The results are then combined in Section 7 to establish the main theorem of the paper. Lastly, Section 8 sketches some directions for future work.

# 2 Definitions

## 2.1 Notations and useful facts

We will use $\mathbb{N}$ to denote the set of integers. Intervals $\{N, N + 1, \dots, M\}$ will be denoted by $[N; M]$, and we will abusively write $[N]$ for $[1; N]$. We will write $\binom{[N]}{k}$ to denote the set of multisets of size at most $k$ included in $[1, N]$.

For a given set $\{0; 1\}$, we write $\{0; 1\}^*$ the set of strings, i.e. finite sequences of elements of $\textit{oi}$. Given $x$ and $y$ in $\{0; 1\}^*$, $|x|$ will denote the length of the string $x$, and we will write $xy$ the concatenation of the strings $x$ and $y$.

We will abusively speak of Turing machine as programs and vice versa. In the following we interchangeably view integers, programs and bitstrings as the same thing, meaning a bitstring represents an integer and a program and vice versa.

Time bounds will be written as $T$, while $\alpha$ and $f$ are *reasonable* functions of $\mathbb{N}^\mathbb{N}$ (see definition below). Functions $g$ and $h$ are *reasonable* slow growing functions (see definition below). We will often abusively write $T$, $f$, and $\alpha$ instead of $T(n)$, $f(n)$ and $\alpha(n)$.
<figure><img src="image_2.png" /><figcaption>Fig. 1. Longpré's construction</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>Fig. 2. Our construction</figcaption></figure>

follows (we put in parenthesis the related notions in our Kolmogorov problem): a list $E$ of $pk$ numbers (the outees) in $[1; N]$ (size of the outees) is shared evenly between $p$ players (the simulants), who each get to output an answer (an outant) in $[1; N]$ depending on their share of $E$. The players must establish a communication-free strategy ensuring that at least one of them outputs a number not belonging to $E$.

We establish in section 5 a solution to this combinatorics problem which we then use to get a better Kolmogorov time hierarchy theorem than Longpré when $f = o(\log(n))$. More precisely, we prove that for any reasonable function $f = o(\log(n))$, there exists a function $\alpha = o(2^f)$ such that $\exists_{\infty} n, [f, \alpha T](n) > [f, T](n)^4$ (where for two set $A$ and $B$, $A > B$ means $B \subseteq A$).

The bound $f = o(\log(n))$ and the associated $\alpha$ is directly related to bounds on the solution we obtain for novelty games. Better bounds for novelty games would thus translate (modulo some technicalities) into a better bounded time hierarchy theorem. The bounds come from the fact that $N$ must be bigger than $pk$ in order for a winning strategy to exist, how much bigger determines the bound. We show in Figure 3 the bounds established in this paper.

<table><caption>Fig. 3. Bounds on $\mathfrak{B}(p, k)$ for general values $p, k$</caption><thead><tr><th>Game</th><th>(p, k)</th><th>(p, k)</th></tr></thead><tbody><tr><td>Upper bound</td><td>(k<sup>p</sup>)<sup>k<sup>p</sup></sup></td><td>2<sup>5k<sup>p-1</sup></sup></td></tr><tr><td>Reference</td><td>theorem 17</td><td>theorem 36</td></tr></tbody></table>

<footnote n="4">⁴$A > B$ means $B \subset A \land B \neq A$</footnote>
As already mentioned, we write $\forall_{\infty} n, A(n)$ to express that $A(n)$ is true for all but finitely many $n$. We will also write $\exists_{\infty} n, A(n)$ to express that there are infinitely many $n$ such that $A(n)$.

Let $E_1(x) = 1^{|x|}0x$. Let $E_2(x) = E_1(|x|)x$. The proof of the following result can be found in [6].

**Theorem 1.** $E_2$ is a prefix code and $|E_2(x)| = x + 2\log(|x|) + 1$. $E_2$ being a prefix code means that $\forall x, y \in (\{0; 1\}^*)^2$ one can uniquely retrieve $x$ and $y$ from the string $E_2(x)y$.

We will consider that our encoding of programs is such that if a string is
outputted by a program of size $f$ it is also outputted by a program of size
$f + c$ for $c$ a universal constant.

We define $C^T(x)$ for $x$ a string in the same way as in Li and Vitanyi
[6] i.e. it is the length of the smallest description $p$ such that when $p$ is
interpreted by $U$ a universal Turing machine fixed in advance, $U$ prints $x$ in
less that $T$ steps.

Let $g, f$ be two integer functions we write $g = \tilde{O}(f)$ to mean $g = O(f * \text{polylog}(f))$

When we call a function $f$ reasonable we mean it in an informal way: "any
function not designed to explicitly break our theorem". A formal definition
most of the time looks like this: given a time bound $T$ a function $f$ is
reasonable if there exists $c \in \mathbb{R}$ computing $f(n)$ in less than $cT(n)$ steps
(equivalently $f \in \text{DTIME}(T)$). Example of reasonable functions are: usual
functions, composition of reasonable functions, $\log^*(n)$ (where $\log^*$ is the
iterated logarithm).

When we call a function slow-growing we informally mean that it tends
towards infinity and it does so really slowly (if $g$ is called slow growing one
may think $g = \sqrt{\log^*}$).

## 2.2 Kolmogorov related notions

We define Time-space bounded Kolmogorov complexity as it is usually de-
fined, for instance in the book of Li and Vitanyi [6, section 7.1.2], or in
Longpré [8].

**Definition 2.1** (Time-space bounded Kolmogorov complexity). Let $\phi$ be a
computable function from strings to strings. Let $T \in \mathbb{N}, x \in \{0; 1\}^*$. We
define $C_{\phi}^{T}(x) = \min\{|p|; \phi(p) \text{ outputs } x \text{ and stops in } T \text{ steps or less}\}$

**Theorem 2.** There exists a recursive function $\phi_0$ such that for every other
recursive function $\phi$, there is a constant $c$ such that $C_{\phi_0}^{ctlog(t)}(x) \le C_{\phi}^t(x)$ for
all $x$. The constant $c$ depends on $\phi$ only.
The method described above and represented in figure 2 we name "parallel diagonalization". In the figure 6 of section 2 we present an even more general way of diagonalizing which we call "parallel diagonalization with advice", the "advice" part refers to the fact that we can give some additional information to the programs. We believe this technique may have implications elsewhere in complexity theory. In part C we relate novelty games to the existence of *k*-paradoxical tournament, a known notion in the literature [8] and use this connection to find a second general strategy. A thorough analysis of novelty games may therefore be of independent interest to researchers in combinatorics.

**Context of the research** Our results are related to several recent work in the field of computational complexity.

First, time-bounded Kolmogorov complexity has seen a lot of study these recent years and used for breakthrough results in meta complexity [13] [16] [12], but not only [7] [18]. The results are many and have strong implications regarding existence of one-way functions among other things. In a recent result [14] it is shown that finding a witness to $K^t$ is as hard as evaluating $K^t$ (under some assumptions), it is somewhat surprising to know this but yet have little insights over existence of a time-bounded Kolmogorov hierarchy.

Second, in a recent paper [23], Vyas and Williams get a new time hierarchy for complexity classes with advice when the advice is bigger than $n$. To do so they study the MISSING-STRING problem defined as such: one gets as input a list of $KN$ strings of size $N$ and tries to output a string of size $N$ outside the list (see definition 3.7). More specifically, they come up with local circuits for MISSING-STRING. These circuits are local in the sense that any output gate can only probe $K \log(K)$ bits from the input gate (see fig. 4). While the starting problem is reminiscent of Novelty games, Vyas and Williams's result and the work presented here are, as far as we can tell, incomparable (see the differences between fig. 2 and fig. 4).

<figure><img src="image_4.png" /><figcaption>Fig. 4. Local circuit for MISSING-STRING</figcaption></figure>

Indeed, in [23] the authors derive a new time hierarchy theorem for TM with advice (THT/advice). This in turns provides directly a hierarchy for temporal bit-wise Kolmogorov complexity noted $Kb^t$ (see definition 8.5). It is interesting to see that the MISSING-STRING
Proof. You may find the proof in [6] □

The log factor in this theorem comes from the time overhead of the best known simulation by universal Turing machines.

**Definition 2.2 (Universal efficient Turing machine).** For any Turing machine $M$, $\#M \in \{0;1\}^*$ denotes a reasonable encoding of $M$. Let $U$ be a Turing machine. We say that $U$ is a universal efficient Turing machine if:

* the function $\phi_0$ defined by $U$ respects the condition of theorem 2, and

* for all Turing machines $M$ and strings $x$, $U(< \#M, x>) = M(x)$ where $< \#M, x> = E_2(\#M)x$.

In the following we fix $U$ to be a universal efficient Turing machine. We will abusively treat $U$ as a program when necessary.

**Definition 2.3 (Universal time-space bounded Kolmogorov complexity).** Let $T \in \mathbb{N}^2$, $w \in \{0;1\}^*$. We define $C^T(w)$ as

$$ \min\{|p| \mid U(p) =_t w\}, $$

where $U(p) =_t w$ means that $U$ computes $w$ on input $p$ in at most $t$ steps.

*Remark 1.* Note that here $p$ is treated as the encoding of a pair consisting of a machine and its input. The size of a program is actually the size of the encoding of the program and its input.

*Remark 2.* For a string $w$, $C^T$ is less than $f$ if there is a program $p$ of size less than $f$ whose running time when simulated by $U$ is less than $T$. This should be opposed to: a program $p$ of size less than $f$ whose "real" running time is less than $T$. As a consequence, the log factor caused by the simulation is already taken into account when considering the time-Kolmogorov complexity of a string. In section 1 and 3 we abusively did not make that difference, but this will become important when we formalize the proof in section 7. In a first reading this difference may be ignored.

For a second reading, let us add some details. When we simulate $\alpha$ distinct programs for $T$ steps in section 5 and 7, we need to simulate them for $T$ steps and not $T \log T$. Because of the tightness of our result, the small speeding factor we achieve would be overshadowed by this $\log T$ factor if it were not already built in the definition of time-bounded Kolmogorov complexity. Let us note that this is not a specificity of our approach, as Longpré result also uses this fact.

**Definition 2.4 (Class of time-space bounded Kolmogorov complexity with fixed size).** Let $T, f$ be functions from $\mathbb{N}$ to $\mathbb{N}$, and $n \in \mathbb{N}$. We define

$$ [f, T](n) = \{w; |w| = n \land C^{T(n)}(w) \le f(n)\}. $$

Longpré denotes this class by $[f(n), T(n)]$ instead.
problem and Novelty Games both imply two similar but incomparable time-hierarchy
theorems for Kolmogorov complexity. We stress that these time-hierarchy theorems are
indeed incomparable: in section 8 we show that results for $Kb^t$ do not imply results for $K^t$.
Our results are thus not contained in [23]. We summarize the links between the problem in
figure 5.

<figure><img src="image_5.png" /><figcaption>Fig. 5. Links with MISSING-STRING</figcaption></figure>

Lastly, the MISSING STRING problem and novelty games are also reminiscent of the
range avoidance problem. The Range Avoidance (AVOID) problem is: given a Boolean circuit
$C: \{0,1\}^n \rightarrow \{0,1\}^m$ for some stretch $m > n$, find an element $y \in \{0,1\}^m$ outside the range of
C. Ren, Santhanam and Wang [21] showed some implications over the complexity of AVOID,
and a fast algorithm was recently given [10] for AVOID for circuits of $NC^3$. Since the AVOID
problem is morally a compressed version of the MISSING-STRING problem, we may draw
inspiration to investigate a compressed version of Novelty games.

**Plan of the paper** Here is a succinct outline of this paper. Section 2 provides a high level view of the paper and of our techniques. Formal definitions and notations are introduced in section 3. The remaining sections then contain the technical material. In Section 4 we define the new combinatorial problem – which we call *novelty games*. We also prove general results and give winning strategies for these games on specific cases. In Section 5 and section C we present two different winning strategy for novelty games. That of section 5 is the one we actually use for our result and describe in section 2, the one from section C is a completely different approach which is interesting in its own right and may foster new ideas. In Section 6 we formally define the programs used to show $[f, o(2^f)T](n) > [f, T](n)$. The results are then combined in Section 7 to establish the main theorem of the paper. Lastly, Section 8 shows that our result cannot be derived from a time hierarchy theorem, treats the case of $rK^t$ and sketches some directions for future work.

The appendix contains the original proof of Longpré (section A), strategies for specific $p$ and $k$ (section B), an additional strategy for any $(p, k)$ mentioned earlier (section C) and finally technical results about reasonable functions (section D).

## 2 HIGH-LEVEL DESCRIPTION

We now expose the results and techniques of the paper with more details, while keeping to a
high-level description. Further technical details are found in later sections.

**Objective.** Our goal is to study the question

$$ \exists_{\infty} n, [f(n), T(n)] \subsetneq [f(n), \alpha T(n)] \text{ ?} $$
In this paper we sometimes consider slow growing functions, the slower they grow the better, but we need those functions to exceed $K^{T(n)}(n)$ for infinitely many $n$. We prove in the next theorem that for $T(n) = 2n$ and for infinitely many $n$, $K^{2n}(n)$ is less than $\log^*\log^*(n)$. Thus most reasonable slow growing functions exceed $K^{T(n)}(n)$ infinitely many times.

**Theorem 3.** $\forall c \in \mathbb{N}, \exists_{\infty} n \in \mathbb{N}, K^{2n}(n) + c \le \log^*(\log^*(n))$.

*Proof.* Taking $c = 0$ the proof being similar for any $c$: consider the sequence $n_0 = 2, n_k = 2^{n_{k-1}}$. $n_k = (\log^*)^{-1}(k)$. $n_k$ is of size $n_{k-1}$ and can be printed in time $2n_{k-1}$ by a program of size $k = \log^*(n)$. So we have a small and fast program to print $n_k = (\log^*)^{-1}(k)$ by composing the program twice we can print $n'_k = (\log^*)^{-1}(\log^*)^{-1}(k)$ in time $2n'_k$ with a program of size $k$. $\square$

# 3 Goal and general strategy

**High level description of the paper.** Our goal is to study the question

$$ \exists_{\infty} n, [f(n), T(n)] \subsetneq [f(n), \alpha T(n)]? $$

Longpré has shown

$$ \exists_{\infty} n, [f(n), T(n)] \subsetneq [f(n), c2^{f(n)}T(n)]. $$

The proof of Longpré follows a standard diagonalization argument. One considers a program $p(n)$ which runs all programs of size $f(n)$ for $T(n)$ steps (this takes time $2^f T$), and then outputs a string of length $n$ which was not the output of any of the $2^f$ enumerated programs. Intuitively, the program $p$ is of size $K^{T(n)}(n) + O(1)$ since we just gave its description (the term $O(1)$) and instead of giving $n$ as an input we can give it a representation of $n$ decodable in $T(n)$ steps (the term $K^{T(n)}(n)$). As a consequence the stronger result we obtain is in fact

$$ \exists_{\infty} [f(n), T(n)] \subsetneq [K^{T(n)}(n) + O(1), c2^{f(n)}T(n)], $$

since $K^{T(n)}(n) + O(1)$ is significantly lower than $f(n)$ for any reasonable functions $f$ and $T$, and infinitely many $n$. When $f$ is bigger than $\log(n) + c$, one can change the quantifier $\exists_{\infty}$ to $\forall_{\infty}$, since $K^{T(n)}(n) < \log n + c$ for some $c \in \mathbb{N}$.

**One try variant.** Our idea to prove

$$ [f(n), T(n)] \subsetneq [f(n), \alpha T(n)] $$

is to do the following: instead of running every program of size $f$ for $T$ steps (which takes time $2^f T$), we only run $\alpha$ of them for $T$ steps. First we
Longpré has shown

$$ \exists_{\infty} n, [f(n), T(n)] \subsetneq [f(n), c2^{2f(n)}T(n)]. $$

The proof of Longpré follows a standard diagonalization argument. One considers a simulant $p(n)$ which runs all simulees of size $f(n)$ or less for $T(n)$ steps (this takes time $2^{f+1}T$), and then outputs a string of length $n$ which was not the outee of any of the $2^{f+1}$ simulees. The simulant $p(n)$ can be made of size $K^{T(n)}(n) + O(1)$ since we just gave its description (the term $O(1)$) and instead of giving $n$ as an input we can give it a representation of $n$ decodable in $T(n)$ steps (the term $K^{T(n)}(n)$). As a consequence, the stronger result we obtain is in fact

$$ \exists_{\infty} [f(n), T(n)] \subsetneq [K^{T(n)}(n) + O(1), c2^{2f(n)}T(n)], $$

When $f$ is bigger than $\log(n) + c$, one can change the quantifier $\exists_{\infty}$ to $\forall_{\infty}$, since $K^{T(n)}(n) < \log n + c$ for some $c \in \mathbb{N}$.

**Neologisms for simulating programs** Before going any further and in order to simplify reading we introduce the following nomenclature: programs which simulate other programs are called *simulants*, their output is called *outant*. Programs which are being simulated are called *simulees*, their output is called *outee*.

**Our method using parallel diagonalization. (One-try variant)** We restate here the idea given in section 1 described by figure 2. Our idea for proving

$$ [f(n), T(n)] \subsetneq [f(n), \alpha T(n)] $$

is to do the following: instead of running every simulee of size $\le f$ for $T$ steps (which takes time $2^{f+1}T$), we only run $\alpha$ of them for $T$ steps. First we divide the set of $2^{f+1}$ simulee of size $f$ into chunks of size $\alpha$, these chunks are called $C_i$ for $i \in [0, 2^{f+1}/\alpha]$. We then consider $2^{f+1}/\alpha$ simulants $(p_i)_{i \in [2^{f+1}/\alpha]}$. Simulant $p_i$ will run all the simulees of chunk $C_i$ for $T$ steps: some of those may stop before $T$ steps and we store their outputs (there are at most $\alpha$ such outees). Call those outputs $c_i^1, c_i^2, \dots$. Then each program $p_i$ will look at these outees and produce an outant which hopefully is not the output of any program of size $f$ (not only the outees of chunk $C_i$). Now of course this is where the difficulty of the approach lies: each simulant $p_i$ only knows a fraction of the possible outputs of programs of size $f$, and there is no reason to think that it can output something new. However, we only need one of those programs to output something new. To that effect, the programs will play a collective game - called novelty game - ensuring that at least one of them outputs a "new" string. The second task of our programs, after computing the values $c_i^j$, is thus to apply a *strategy* ensuring that one of them succeeds in outputting a new string. As a consequence, the computation of the strategy itself should be feasible within the chosen time bounds.

As a technical note, instead of considering multiple programs $p_i$ we will have one global program$^5$ $p$ taking as input a description of $n$ decodable in $2n$ steps noted $\#n$ and $i, n$ tells it which size we are currently looking at and $i$ tells it to run the $i$-th chunk of size $\alpha$ of simulees of size $f(n)$.

Simulant $p(\#n, i)$ is of approximate size $K^{2n}(n) + f - \log \alpha$, this is smaller than $f$ for infinitely many $n$ (which is what we need) for any function $\alpha$ such that $\log \alpha$ grows faster than $K^{2n}(n)$. We may even have some leeway which allows us to cram in some additional information

<footnote>$^5$This adds some uniformity to the programs which is not formally needed and might hinder the approach. Without uniformity, one may give additional advice to the programs, for instance information about the inputs of the other programs (hence the terminology of parallel diagonalization with advice).</footnote>
divide the set of $2^f$ programs of size $f$ into chunks of size $\alpha$, these chunks are called $C_i$ for $i \in [0, 2^f/\alpha]$. We then consider $2^f/\alpha$ programs $(p_i)_{i \in [2^f/\alpha]}$. Program $p_i$ will run all the programs of chunk $C_i$ for $T$ steps: some of those may stop before $T$ steps and we remember their outputs (there are at most $\alpha$ such outputs). Call those outputs $c_i^1, c_i^2, \dots$. Then each program $p_i$ will look at these outputs and produce a new string which hopefully is not the output by *any* program of size $f$ (not only the ones of chunk $C_i$). Now of course this is where the difficulty of the approach lies: each program $p_i$ only knows a fraction of the possible outputs of programs of size $f$, and there is no reason to think that it can output something new. However, we only need *one* of those programs to output something new. To that effect, the programs will play a collective game ensuring that at least one of them outputs a "new" string. The second task of our programs, after computing the values $c_i^j$, is thus to apply a strategy ensuring that one of them succeeds in outputting a new string. Note that this might be possible because the programs *collectively* know all the outputs of programs of size $f$ running for $T$ steps.

In this paper, instead of considering multiple programs $p_i$ we will have one global program $^3p$ taking as input $n$ and $i$, $n$ tells it which size we are currently looking at and $i$ tells it to run the $i$-th chunk of size $\alpha$ programs of size $f(n)$. These programs are of approximate size $\log n + \log(2^f/\alpha) \approx \log n + f - \alpha$. This has to be smaller than $f$ in order to be of any use. To reduce the size we also apply a trick and give a description of $n$ decodable in $T(n)$ steps noted $\#^T n$: the programs are then of approximate size $K^{T(n)}(n) + f - \alpha$. For any reasonable increasing function $\alpha$ growing to infinity, this is smaller than $f$ for an infinite number of $n$, that is because $\liminf K^{T(n)}(n)$ grows incredibly slowly as shown in theorem 3. We even have a bit of leeway which allows us to cram in some additional information which we'll use in the multiple tries variants.

As for the running time, simulating $\alpha$ programs for $T$ steps takes $\alpha T$ steps in total. We then have to apply our strategy on the $\alpha$ inputs. The strategy needs to be described, which adds some extra size to program $p$. When the strategies are uniform this only adds $O(1)$ bits of size. Running this strategy also adds some extra running time which depends on the precise strategy we implement. In general, this extra time could be greater than $\alpha T$ and forbid us to conclude. However, in practice, it turns out that this is not the limiting factor.

Regardless of size and time constraint, it is not clear at all at this stage that a strategy allowing this proof technique even exists. We will first rephrase

<footnote>^3Actually this adds some uniformity to the programs which is not formally needed and might hinder the approach. Without uniformity, one may give additional advice to the programs, for instance information about the inputs of the other programs (hence the terminology of parallel diagonalization with advice).</footnote>
which we'll use in the multiple tries variants. Functions which grow faster than $K^{2n}(n)$ will be introduced as *reasonable functions* in definition 3.6. The reasonability condition for a function is merely technical and not stringent at all.

As for the running time, simulating $\alpha$ programs for $T$ steps takes $\alpha T$ steps in total. We then have to apply our strategy on the $\alpha$ inputs. The strategy needs to be described, which adds some extra size to program $p$. Running this strategy also adds some extra running time. Depending upon our strategy, this extra time could be greater than $\alpha T$ and forbid us from concluding.

**Novelty games** Regardless of size and time constraint, it is not clear for now that a strategy may even exist. For this reason, we have abstracted the underlying combinatorial problem to be studied separately. We will first explain again its statement and then how it relates to our initial problem and the simulants.

We start from an initial list $E \subset [1; N]$ of size $pk$. We then partition this list $E$ into sets of size $k$ which are given to $p$ distinct players. Each of the $p$ players may produce an answer depending only on these $k$ inputs given to them. Their answer must be an element of $[N]$. The players collectively win if at least one of the answers given by the players is not in the initial set $E$. The first question is thus: is there a strategy that players can apply which can make them win for all possible initial list $E$? Note that while the players may agree on a common deterministic strategy, no communication is allowed between them during the process. The instance of this game with $p$ players each receiving $k$ numbers is noted $G^N(p, k)$. We call this family of games *novelty games*, and we describe them in more details in section 4.

We now relate novelty games to our parameters in the Kolmogorov setting. Each of the $p$ players represents a simulant, therefore we will expect that $p = 2^{f+1}/\alpha$. Each player retrieves at most $\alpha$ outees, and thus $k = \alpha$. The answer of each simulant is an outant of $\{0, 1\}^n$, and thus $N = 2^n$. The list $E$ should be understood as the set of all outees of size $n$ of simulees of size $f$ or less which we are trying to parallelize against, thus $|E| \le 2^{f+1}$. We will pick the worst case and simply consider that $|E| = 2^{f+1}$.

*Remark 1.* The combinatorial approach disregards any restriction on the number of bits necessary to describe the strategy and the running time of the strategy. As a consequence, once we will have a winning strategy, we will need to be careful of these aspects in order to properly use it in the context of proving our result about time-bounded Kolmogorov complexity classes.

*Remark 2.* Achieving a winning strategy for any list $E$ is more than what is needed for our specific problem. Indeed, for the intended application for time-bounded Kolmogorov complexity, one only needs a winning strategy for games in which the initial list is composed of the outputs of the programs of size $\le f(n)$ running for $T(n)$ steps. However, we do not know of a way of taking advantage of this fact.

*Remark 3.* The bound $[N]$ is really important. Our simulant *must* answer a bitstring of size $n$ (recall the definition of $[f, T](n)$). We are given $f(n)$ and $\alpha(n)$, which determine the number $p(n)$ of players and the number $k(n)$ of inputs. Now it may be that the game $G^N(p(n), k(n))$ has a solution when $N$ is very large but not when $N$ is small$^6$. But for our purpose we need $N$ to be less than $2^n$. This leads us to an analysis in section 4 of the bound $\mathfrak{B}(p, k)$ which is

<footnote>$^6$We will establish later in the paper that the game is indeed easier when $N$ gets large.</footnote>
the expected outcome of the strategy as a purely combinatorics problem. We start from an initial list $E \subset [1; N]$, where $N$ is to be thought of as all the possible strings of size $n$, therefore $N = 2^n$. Here $E$ should be understood as the set of outputs of size $n$ of all the programs of size $f$ running for less than $T$ steps, and therefore$^4 |E| = 2^f$. Then we divide this list $E$ into chunks of size $k$ and give those to $p$ players. Here $k$ is to be thought of as $\alpha$ ($k = \alpha$), and $p$ as the number of different programs (one per chunk), hence $p = \frac{|E|}{\alpha} = \frac{2^f}{\alpha}$. Each of the $p$ players may produce an answer depending only on their $k$ inputs. Their answer must be an element of $[N]$. The players collectively win if at least one of the answers given by the players is not in $E$. The question is, for the game $G^N(p, k)$ with $p$ player having $k$ numbers each answering in $[N]$, is there a strategy the players can apply which will work no matter the initial list $E$. Note here that each player has its own strategy, and no communications are allowed between players during the process.

**Remark 3.** The combinatorial approach disregards any restriction on the number of bits necessary to describe the strategy and the running time of the strategy. As a consequence, once we will have a winning strategy, we will need to take care of these aspects in order to use it for proving our result about time-bounded Kolmogorov complexity classes.

**Remark 4.** At this point it is not clear that a strategy even exists. Also, achieving a winning strategy for any list $E$ is more than what is needed for our specific problem. Indeed, for the intended application for time-bounded Kolmogorov complexity, we only need a winning strategy when the initial list is composed of the outputs of the programs of size $f(n)$ running for $T(n)$ steps.

**Remark 5.** The bound $[N]$ is really important. Our programs must answer a bitstring of size $n$ (recall the definition of $[f, T](n)$) i.e. an integer in $[N]$. We are given $f(n)$ and $\alpha(n)$ which determine the number $p(n)$ of players and the number $k(n)$ of inputs. Now it may be that the game $G^N(p(n), k(n))$ has a solution when $N$ is very large but not when $N$ is small$^5$. But for our purpose we need $N$ to be less than $2^n$. This leads us to an analysis in section 4 of the bound $\mathfrak{B}(p, k)$ which is the smallest $N$ for which game $G^N(p, k)$ has a solution. This bound $\mathfrak{B}(p, k)$ proves to be the crux and the limiting factor of our results.

**Multiple tries variant.** Up until this point we have considered that the $i$-th chunk of $\alpha$ programs was attributed to program $p(n, i)$ of size $\approx K^T(n) + f - \alpha$. As mentioned earlier, we have some leeway on the size of our programs, so we can relax the setting to provide some extra information to

<footnote>$^4$To be more precise, this should be an inequality since there may be repeats or programs that do not stop. But we just consider the worst case here.</footnote>

<footnote>$^5$We will establish later in the paper that the game is indeed easier when $N$ gets large.</footnote>
the smallest N for which game $G^N(p, k)$ has a solution. This bound $\mathfrak{B}(p, k)$ proves to be the crux and the limiting factor of our results.

**Winning strategy for Novelty Games: a first example** The full description of the winning strategy we use to establish the result may be found in section 5.

We give here an intuition of the construction when there are three players who each have two numbers (called inputs), this case generalizing well. Suppose you have three players called Alice, Bob and Charlie, and note their respective inputs $a_1, a_2, b_1, b_2, c_1$ and $c_2$. We will write the respective outputs of these three players A, B, and C. The crux of the problem is to find a strategy which prevents the following situation from happening: A is an input of Bob (either $b_1$ or $b_2$), B is an input of Charlie (either $c_1$ or $c_2$), and C is an input of Alice (either $a_1$ or $a_2$). In short, we wish to avoid 3-cycles in the "input-output" graph of the players.

Reasoning ad absurdum and assuming this situation happens, each player may assume that one of their input is another player's output. Then, by encoding information about his inputs into his output, each player can *effectively* transmit some information about its inputs to another player (even though there is no actual communication). We thus devise a winning strategy - which we describe next - that is the same for all players.

Let us take Alice as an example: she will first write her two inputs as 7-digits number in base 15. Since she has two inputs, she gets a total of at most 14 different digits. Her output will also be a 7-digits number in base 15, with the last digit taken to be different from the 14 digits that appear in her inputs. This in particular prevents Alice from answering one of her own input. The 6 remaining digits of her output will be composed of the 3 last digits from her first input and the 3 last digits from her second input. The idea now is that if Bob - who uses the same strategy - turns out to have Alice's output as one of his inputs, then Bob's output contains some of the digits of Alice's input. In particular the 3 last digits from each of Alice's input. Consequently the last digit of Bob's output which will be different from his own 14 digits will also be different from the last digits of Alice's inputs. This prevents Bob's output from being equal to an input of Alice.

By analyzing the strategy one step further, one can similarly conclude that in the case where Alice's output is an input of Bob, and Bob's output is an input of Charlie, then Charlie's output may not equal Alice's input.

**A general winning strategy for Novelty Games** This small example of winning strategy can in fact be generalized to give a general winning strategy. We now give a high-level description of this general strategy, which is properly described and proven to be winning in section 5 <fnref n="7" />.

Suppose we are now in the context of the novelty game with $p$ players each receiving $k$ numbers. Consider $T$ the complete $k$-ary tree of depth $p$, and let $V(T)$ denote the set of (roughly) $k^p$ vertices of $T$. We consider a bijection between elements $\{0, 1\}^n$ and functions $V(T) \to [k^p] := \{1, \dots, k^p\}$ (notice thus that $2^n \approx (k^p)^{k^p}$). Such a bijection can be done by achieved by writing a binary string in base $k^p$ and labeling the nodes of the tree with the obtained in a breadth-first manner. We abusively write $x$ the function associated to the string $x \in \{0, 1\}^n$. Then each player's strategy on input $(x_1, \dots, x_k) \in (\{0, 1\}^n)^k$ will output a function $y: V(T) \to [k^p]$ such that $y(r) = \min\{\ell \mid \ell \notin \bigcup_{i=1}^k \{x_i(v) \mid v \in V(T)\}\}$, where $r$ is the root of $T$. That is, the root value is defined to be different from all the values of vertices.

<footnote n="7">⁷We thank the anonymous reviewer of a previous version of this work, who provided a first version of this description.</footnote>
our programs. We present here one way of using this extra information. We will now consider replacing $p(n, i)$ by a program $p(\#^T n, i, j)$. This program is the $j$-th program attributed to the $i$-th chunk of $\alpha$ programs. It has an additional input $j$ in $[1; 2^\alpha/g]$, where $g$ is any reasonable slow growing function. The size of $p(\#^T n, i, j)$ is therefore approximately $K^T(n) + f - \alpha + \alpha - \log(g) \approx K^T(n) + f - \log(g)$, which is smaller than $f$ for infinitely many $n$. As for the one-try variant, the program $p(\#^T n, i, j)$ runs the $i$-th chunk of programs of size $f(n)$ for $T(n)$ steps but can then give an answer which depends on $j$.

Expressed using our combinatorics problem, each player can now propose $m$ answers instead of giving out a unique answer. The players collectively win the game if one of the answers of one of the players is not in the initial list $E$. This game is denoted by $\mathcal{G}^N(p, k, m)$.

For the moment, we have not been able to use the ability to use multiple tries to improve on our solution for the one try variant, and we only came up with basic theorems. We nevertheless mention it since it is a natural extension of the underlying combinatorics problem. It may also be a way forward to lower the bound $\mathfrak{B}(p, k, m)$ presented in section 4.

# 4 Novelty games

In this section, we introduce the combinatorial game behind our technique, under the name of *Novelty games*.

We remind the reader that $\binom{[N]}{k}$ denotes the set of all multisets included in $[1, N]$ of size at most $k$.

## 4.1 Definition

**Definition 4.1.** We now define the game $\mathcal{G}^N(p, k, m)$.

* There are $p$ players.

* Player $i$ receives a multiset $A_i \in \binom{[N]}{k}$; elements of $A_i$ are called inputs.

* Each player has $m$ tries.

* On each try a player answers an element of $[1; N]$

An *occurrence* of the game $\mathcal{G}^N(p, k, m)$ is a specific family $(A_i)_{i=1}^p$.

A *strategy* $\mathcal{S}^N(p, k, m)$ for $\mathcal{G}^N(p, k, m)$ is a family of functions $(s_i)_{i=1,...,p}$ where

$$s_i: \binom{[N]}{k} \times [m] \rightarrow [N].$$

The players collectively win the occurrence $(A_i)_{i=1}^p$ of $\mathcal{G}^N(p, k, m)$ if there exists a pair $(i, j) \in [p] \times [m]$ such that $s_i(A_i, j) \notin \cup_{i=1}^p A_i$.
Moreover, we will let $y(v) := x_i(\text{parent}(v))$ for each vertex $v$ in the $i$-th subtree of $r$. Let us now write $F(x_1, \dots, x_k)$ the output $y$ of a player.

The key property to ensure that this defines a winning strategy is the following. If $y = F(x_1, \dots, x_k)$, then for every $i$, there exists a vertex $v$ at depth 1 (in particular, a non-root vertex $v$) such that $x_i(r) = y(v)$, where $r$ denotes the root of $T$. Repeating this observation, we see that if $x$ is an antecedent of $y$ through $p$ repeated applications of the function $F$, there exists some non-root vertex $v$ at depth $p$ such that $x_i(r) = y(v)$.

To prove that the strategy specified by $F$ is a winning strategy, we then need to show that for every set $(x_i^j)_{i \in [k], j \in [p]}$ of inputs to the $p$ players, there exists $j \in [p]$ such that $F(x_1^j, \dots, x_k^j) \notin \{x_i^{j'} \mid i \in [k], j' \in [p]\}$. To obtain a contradiction, we assume that for every $j \in [p]$, there exists $(i, j')$ such that we have $F(x_1^j, \dots, x_k^j) = x_i^{j'}$, i.e. that the output of player $j$ is one of player $j'$ inputs. We can now consider the directed graph on $p$ vertices where an edge $(j, j')$ is drawn for each vertex $j$ whose output is an input of $j'$. Every vertex of this graph has out-degree at least 1, and thus the graph contains a cycle of length at most $p$, say without loss of generality $(1, 2, \dots, m, 1)$ with $m \le p$. Then, for some $i$, $x_i^1$ is obtained by repeatedly applying $F$ at most $p$ times, thus $x_i^1$ is its own antecedent though at most $p$ repeated applications of the function $F$. But by the key property above, there exists some non-root $v$ such that $x_i^1(v) = x_i^1(r)$. This contradicts the definition of $F$, since the root value is defined to be different from all the non-root values.

The last step to conclude that this winning strategy can be used to establish our result for Kolmogorov time hierarchy is to check that this strategy can be implemented efficiently by the players. This does not raise any complicated issues.

**Multiple tries variant.** Up until this point we have considered that simulants $p(\#n, i)$ of size $\approx K^{2n}(n) + f - \log \alpha$. As stated before, we only need the program to be of size $f$ or less, and since all reasonable$^8$ functions $\alpha$ are much bigger than $K^{2n}(n)$, we can provide some extra information (advice) to our programs. This technique can be thought of as parallel diagonalization with advice. We present here one way of using this extra information$^9$.

We consider simulants $p(\#^T n, i, j)$. These are to be thought of as the $j$-th simulant attributed to the $i$-th chunk of $\alpha$ simulees. Input $j$ is in $[1; \alpha/g]$, where $g$ is any reasonable slow growing function. The size of $p(\#^T n, i, j)$ is therefore approximately $K^T(n) + f - \log \alpha + \log \alpha - \log(g) \approx K^T(n) + f - \log(g)$, which is smaller than $f$ for infinitely many $n$ when $\log(g)$ is reasonable. The program $p(\#^T n, i, j)$ runs the $i$-th chunk of $\alpha$ programs of size $\le f(n)$ for $T(n)$ steps and then outputs an outant which depends on $j$. You may see figure 6.

Expressed using our combinatorics problem, each player can now propose $m$ answers instead of giving out a unique answer. The players collectively win the game if one of the answers of one of the players is not in the initial list $E$. This game is denoted by $G^N(p, k, m)$.

For the moment, we have not been able to use the ability to use multiple tries to improve on our solution for the one try variant, and we only came up with basic theorems. We nevertheless mention it since it is a natural extension of the underlying combinatorics problem. It might also allow us to lower the bound $\mathfrak{B}(p, k, m)$ presented in section 4.

<footnote>$^8$see definition 3.6</footnote>

<footnote>$^9$this may not be the only meaningful way to use this extra information, for instance we simulants could simulate a different chunk of simulees depending on $j$. The way we present here naturally extends novelty games.</footnote>
A winning strategy for $G^N(p, k, m)$ is a strategy such that all occurrences of the game are won.

Notations 1. When $m = 1$, we may write $G^N(p, k)$ instead of $G^N(p, k, 1)$. We may sometimes drop the superscript and subscript altogether when they are not relevant or clear from the context.

When all players have the same strategy, i.e. when $\mathcal{S} = (s_i)_{i=1}^p$ is such that there exists a function $s$ with $s_i = s$ for all $i = 1, \dots, p$, we say that $\mathcal{S}^M(p, k, m)$ is *oblivious*.

**Definition 4.2.** We define $\mathfrak{B}(p, k, m)$ as the smallest integer $N$ such that there exists a winning strategy for the game $G^M(p, k, m)$.

We note that $\mathfrak{B}(p, k, m)$ is well defined, as proven in section 6.2. Establishing an estimate of $\mathfrak{B}(p, k, m)$ in general remains an open question.

**4.2 General remarks about Novelty games**

**Sets.** The first remark is that one may only consider sets of size exactly $k$ instead of multisets of size at most $k$. This is because the hardest case for the strategy is when each player has $k$ different numbers. Indeed, suppose there exists a strategy $\mathcal{S}$ winning in all occurrences of the game for which players have a set of size $k$ (or, equivalently, a multiset of size $k$ without repetitions). Then one can easily construct a winning strategy for all multisets: when the considered multiset have less than $k$ distinct numbers, it suffices to change repeated occurrences by arbitrary new ones and if you still don't have $k$ values you can add arbitrary numbers to reach $k$. One can can apply the strategy $\mathcal{S}$ on the resulting set. A routine check suffices to show that this strategy is winning.

In the following, we will therefore always assume that inputs are pairwise distinct, and that we may add arbitrary new inputs so that sets have size exactly $k$.

We also note that inputs are not ordered, since we work with sets and not tuples. But we may suppose, if need be, that they are by choosing an arbitrary order relation.

The next theorem states that the existence of strategy for inputs in $[1; N]$ implies the existence of a strategy for inputs in $[1; M]$ for all $M \ge N$. This motivates the definition of $\mathfrak{B}$.

**Theorem 4.** Let $M, N \in \mathbb{N}$ such that $M \ge N$. If $G^N(p, k, m)$ has a winning strategy then so does $G^M(p, k, m)$

*Proof.* We treat the case $M = N+1$ and then we can conclude by induction. Let $\mathcal{S}$ be a winning strategy for $G^N(p, k, m)$. We define a strategy $\mathcal{S}'$ for the game $G^M(p, k, m)$ as follows. If $M$ is not an input of strategy $\mathcal{S}'$, then
<figure><img src="image_6.png" /></figure>

Winning condition:
$\exists a, \exists b, \forall c, x_a^b \neq y_c$

<caption>Fig. 6. Multiple tries setting</caption>

# 3 DEFINITIONS

## 3.1 Tools and notations

**Notations** We will use $\mathbb{N}$ to denote the set of integers. Intervals $\{N, N + 1, \dots, M\}$ will be denoted by $[N; M]$, and we will abusively write $[N]$ for $[1; N]$. We will write $(\begin{smallmatrix} [N] \\ k \end{smallmatrix})$ to denote the set of multisets of size at most $k$ included in $[1, N]$.

For a given set $\{0, 1\}$, we write $\{0, 1\}^*$ the set of strings, i.e. finite sequences of elements of $\{0, 1\}$. Given $x$ and $y$ in $\{0, 1\}^*$, $|x|$ will denote the length of the string $x$, and we will write $xy$ the concatenation of the strings $x$ and $y$.

We write $f = \omega(g)$ to mean that $\lim_{+\infty} \frac{f}{g} = +\infty$.

We will abusively speak of Turing machine as programs and vice versa. In the following we interchangeably view integers, programs and bitstrings as the same thing, meaning a bitstring represents an integer and a program and vice versa. $M$ denotes a TM and $\#M$ a straightforward$^{10}$ description of $M$. The output of program $p(x)$ is noted Out($p(x)$).

We write $\forall_{\infty} n, A(n)$ to express that $A(n)$ is true for all but finitely many $n$. We will also write $\exists_{\infty} n, A(n)$ to express that there are infinitely many $n$ such that $A(n)$.

Given two sets $S$ and $R$ we write $S \subsetneq R$ if $S$ is included but not equal to $R$, we may also write with the same meaning $R > S$.

The function $\log^*(n)$ is defined recursively as

$$ \log^* n = \begin{cases} 0 & \text{if } n \le 1, \\ 1 + \log^*(\log_2 n) & \text{if } n > 1. \end{cases} $$

**Naming conventions** Time bounds will be written as $T$, program size bounds as $f$ and time factor as $\alpha$. Since any word of size $n$ is output by a program of size $n + c$ and you need at least $n$ steps to write it, in order to have interesting theorems we will consider that $f \le n \le T$. We will often drop the input of functions and for instance abusively write $T$, $f$, and $\alpha$ instead of $T(n)$ $f(n)$ and $\alpha(n)$. Function $g$ will denote a slow growing function to infinity.

In order to alleviate any ambiguity we introduce the following notations: $p$ will denote a program. $\#n$ will denote a representation of $n \in \mathbb{N}$, i.e. a program which outputs $n$, some additional requirement may be required of the representation (size and running time). $p(x)$ denotes the program $p$ launched on input $x$ ($x$ is a placeholder name), in particular $|p(x)|$ denotes the size of program $p$ launched on $x$, so it is of size $|p| + |x| + O(\log p)$ (see theorem 4). Out($p(x)$) denotes the output of program $p$ launched on $x$.

<footnote>$^{10}$number of tapes, transition function... with no information compression</footnote>
each player simply runs $\mathfrak{S}$. Otherwise, the player replaces $M$ by $N$ and runs the strategy $\mathfrak{S}$ on the resulting set. One easily checks that $\mathfrak{S}'$ is a winning strategy for $\mathcal{G}^M(p, k, m)$ since the output of $\mathfrak{S}'$ is in $[N] \subset [M]$. $\square$

**Theorem 5.** For all $p, k, m$ in $\mathbb{N}$, and all $a, b, c, d$ in $[0, 1]^3$,

$$ \mathfrak{B}(p - a, k - b, m + c) \leq \mathfrak{B}(p, k, m). $$

*Proof.* This is proven by noticing that a strategy for the game $\mathcal{G}^M(p, k, m)$ is also a strategy for $\mathcal{G}^M(p - a, k - b, m + c)$: it suffices to add $b$ random inputs, apply the strategy on those (since there are less players, the strategy determines a map for each player – and the maps $s_i$ for $i = p - a + 1, \dots, p$ are unused), and guess $c$ arbitrary additional outputs. $\square$

We believe establishing recurrent relations between values of $\mathfrak{B}$ is hard when varying the number of players, numbers, tries or the size of the set of inputs. For instance, it is not even clear how the inequality of theorem 5 can be made strict.

We now start by proving a simple lower bound on $\mathfrak{B}$.

**Theorem 6.** For all $p, k, m \in \mathbb{N}$, $\mathfrak{B}(p, k, m) \geq pk + 1$.

*Proof.* It is easy to realise that there are no winning strategy if $N = pk$: if for all $i \in [1; p]$, player $i$ has as inputs $[(i - 1)k + 1; ik]$, then the set of all inputs is equal to $[1; pk]$ and no player may output a new number. $\square$

Another easy result to establish is that if one allows for enough tries, the value of $\mathfrak{B}$ can be determined (and is low).

**Theorem 7.** For all $p, k \in \mathbb{N}$, $\mathfrak{B}(p, k, k) = pk + 1$.

*Proof.* Let $N = pk + 1$. Each player calls its inputs $i_1, \dots, i_k$. On its $j$-th try each player does this: if $i_j + 1 \leq N$ it answers $i_j + 1$ otherwise it outputs 1. Its routine to check that this is a winning strategy. $\square$

The study of multiple tries has proven to be hard. Apart from quite obvious results, we have not found ways to improve on the results we obtain in the one-try variant. We therefore leave the following question for future work.

*Question 1.* Can one find a better bound for $\mathfrak{B}(p, k, k - 1)$ than $\mathfrak{B}(p, k, 1)$?

We summarise the results of this paper in fig. 1. The proof are scattered in the paper.
## Tools

**Definition 3.1 (Prefix-free codes).** We define functions $E_1$ and $E_2$ from $\{0, 1\}^* \to \{0, 1\}^*$ as $E_1(x) = 1^{|x|}0x$ and $E_2(x) = E_1(|x|)x$.

**THEOREM 3 (PREFIX FREE CODE [15]).** $E_2$ is a prefix code and $|E_2(x)| = |x| + 2\log(|x|) + 1$. $E_2$ is being a prefix code means that $\forall x, y \in (\{0, 1\}^*)^2$ one can uniquely retrieve $x$ and $y$ from the string $E_2(x)y$.

**Definition 3.2 (Encoding of tuples).** Let $x, y, z \in \{0, 1\}^*$. We define $\langle x, y \rangle \stackrel{\text{def}}{=} E_2(x)y$ and $\langle x, y, z \rangle \stackrel{\text{def}}{=} E_2(x)E_2(y)z$. This definition is naturally extended to any number of bitstrings inside $\langle \cdot, \cdot \rangle$.

## 3.2 Kolmogorov related notions

**Defining temporal Kolmogorov complexity** We define time-bounded Kolmogorov complexity as it is usually defined, for instance in the book of Li and Vitanyi [15, section 7.1.2], or in Longpré [17].

Let $M$ be a Turing machine and $s$ a bitstring, let us denote

$$K_M^T(s) = \min\{|p|; M(p) = s \text{ and } M(p) \text{ stops in less than } T \text{ steps}\}$$

We can show that there exists an efficient universal Turing machine $U$ such that

$$\exists c, \forall w \in \{0, 1\}^*, K_U^{ct \log t}(w) \le K_M^t(w)$$

We thus have a robust notion up to a log-factor slowdown. We fix an efficient universal Turing machine $U$ and we formally define $K^t$ complexity

**Definition 3.3 (Universal time-space bounded Kolmogorov complexity).** Let $T \in \mathbb{N}$, $w \in \{0, 1\}^*$. We define $K^T(w)$ as

$$\min\{|\#M, x\}|; U(\langle \#M, x \rangle) = w \text{ in } T \text{ steps or less}\},$$

We remind the reader that $M$ denotes a Turing machine (or program), and $\#M$ is its description. Notice that the definition of $K^t$ complexity is based on the running time of the universal Turing machine, i.e. the number of simulated steps. Also note that the input received by the Turing machine $U$ is treated as the encoding of a pair consisting of a machine and its input

We next state a theorem useful for bounding the $K^t$ complexity of our strings.

**THEOREM 4 ($K^t$ COMPLEXITY OF AN OUTPUT).** Let $p, x, y \in \{0, 1\}^*$, if program $p$ on input $x$ outputs $y$ in $t$ steps then for a $c \in \mathbb{R}$, $K^{ct \log t}(y) < |p| + |x| + O(\log(|p|))$

**PROOF.** $U(\langle p, x \rangle)$ outputs $y$ in $ct \log t$ steps and $|\langle p, x \rangle| \le |p| + 2\log|p| + 1 + |x|$

□

Finally we introduce the object of study of this chapter : we define the set $[f, T](n)$ as the set of strings of length $n$ output by a program of length $f(n)$ running in time $T(n)$ (when simulated through $U$).

**Definition 3.4 (Class of time-space bounded Kolmogorov complexity with fixed size).** Let $T, f$ be functions from $\mathbb{N}$ to $\mathbb{N}$, and $n \in \mathbb{N}$. We define

$$[f, T](n) = \{w \in \{0, 1\}^*; |w| = n \land K^{T(n)}(w) \le f(n)\}.$$

Note that Longpré denotes this class by $[f(n), T(n)]$ instead.
<table><caption>(a) Bounds for general values p, k</caption><thead><tr><th>Game</th><th>(p, k, 1)</th><th>(p, k, i)</th><th>(p, k, k)</th></tr></thead><tbody><tr><td>Upper bound</td><td>(<i>k</i><sup><i>p</i></sup>)<i>k</i><sup><i>p</i></sup></td><td>(<i>k</i><sup><i>p</i></sup>)<i>k</i><sup><i>p</i></sup></td><td><i>pk</i> + 1</td></tr><tr><td>Reference</td><td>section 6.2</td><td>section 6.2</td><td>section 4.2</td></tr></tbody></table>

<table><caption>(b) Bounds for specific values</caption><thead><tr><th>Game</th><th>(2, 2, 1)</th><th>(1, k, 1)</th><th>(p, 1, 1)</th></tr></thead><tbody><tr><td>Upper bound</td><td>9</td><td><i>k</i> + 1</td><td><i>p</i> + 1</td></tr><tr><td>Reference</td><td>section 4.4</td><td>section 4.2</td><td>section 4.2</td></tr></tbody></table>

Figure 1: Results of the paper

## 4.3 Novelty games for Kolmogorov complexity

If we want to prove that $[f, \alpha T](n) \not\subseteq [f, T](n)$, We are interested in studying game $\mathcal{G}^N(p, k, m)$ where:

* $p = 2^f/\alpha$;

* $k = \alpha$;

* $m = k/g$ where g is any reasonable slow growing function;

* $N = 2^n$.

Our bound $\mathfrak{B}(p, k, m)$ should be less than $N$ because a program must answer a string of size $n$ (i.e. an integer of $[N]$). This gets us to analyze when:

$$ \mathfrak{B}(p, k, m) < N \Leftrightarrow \exists g : \mathbb{N} \to \mathbb{N}, \forall n, \mathfrak{B} \left( \frac{2^{f(n)}}{\alpha(n)}, \alpha(n), \frac{\alpha(n)}{g(n)} \right) \le 2^n. $$

Reminding the reader that $f, T$ and $\alpha$ are all functions of $n$, we are thus particularly interested in analysis of the bound $\mathfrak{B}(p(n), k(n), m(n))$ in which $p(n), k(n)$, and $m(n)$ are functions going to infinity and $m(n) = k(n)/g(n)$ where $g(n)$ is a very slowly growing function. $p(n)$ must go to infinity as there is one player per chunk of programs to be simulated and the number of chunks grows with $n$. We have no formal argument establishing that $k(n)$ should go to infinity: each player could have a constant number of inputs as $n$ grows, but this would require to refine the size analysis of our programs, at the very least. Likewise - with no size analysis refinements - $g(n)$ has to grow towards infinity, however the slower $g$ grows the more tries for each player.

*Remark 6.* This subsection was meant to give precise links between our Kolmogorov problem and values for novelty games. But we believe analysing novelty game $\mathfrak{B}^N(p, k, m)$ for any $p, k, m$ is the right way forward.
**Prefix-free Kolmogorov complexity** We mention as a clarification for the educated reader that we do *not* deal in this paper with prefix free complexity, despite the notation *K* sometimes used for this notion. However, we have no reason to believe our techniques wouldn't hold for prefix free complexity.

**RAM model** The notions of Kolmogorov complexity and time bounded Kolmogorov com-
plexity can be adapted simply to RAM machine rather than Turing machine. In this case
since simulation through the universal RAM machine bears only a constant slowdown we
can bypass all technical considerations over simulation time.

**Reasonable functions** For technical reasons we need our functions not to be pathological, in particular we need them to be easy to compute, growing to infinity and doing so faster than $K^{2n}(n)$. This is to ensure that we can find infinitely many $n$ of very low $K^t$ complexity. To that end introduce the notions of very-time-computable functions and reasonable functions. The notion of reasonable function is so lenient that for a first time reading the reader may skip this paragraph and consider that all increasing functions growing to infinity are reasonable.

**Definition 3.5** (Very-time-computable functions). Let $f$ be a function from $N \mapsto N$, $f$ is very-time-computable (VTC) if there exists a machine *M* in DTIME($f(n) + n$) such that $\forall n, M(n) = f(n)$.

The usual notion of time computability is not suitable to functions $f < n$ hence our new definition 3.5. Next is our definition controlling the growth rate of our functions.

**Definition 3.6** (Reasonable functions). A function $f: N \mapsto N$ is reasonable if $f$ is computable and $\forall c, \exists \infty n, c K^{2n}(n) \le f(n)$

In appendix D we study reasonable functions. We have a slightly different definition of
reasonable functions in the appendix than in definition 3.6, but no matter since the different
definitions are shown to be equivalent. Reasonability imposes a certain growth rate for our
function but this condition is not stringent at all: as shown in theorem 6 $\log^*$ is a reasonable
function. For this chapter we only need the following fact whose proof is in the appendix:

**THEOREM 5 (VTC FUNCTIONS AND REASONABILITY).** If *f* is VTC and increasing and going to infinity then *f* is reasonable.

In the rest of the paper all considered functions are considered to be VTC and increasing
and going to infinity and reasonable.

THEOREM 6 (GROWTH RATE OF $K^{2n}$). $\forall c \in \mathbb{N}, \exists \infty n \in \mathbb{N}, cK^{2n}(n) \le \log^*(n)$.

**MISSING-STRING problem** We introduce the MISSING-STRING problem and efficient (deterministic-non-parallel) algorithms for it as we will need them in proofs later. Before being acquainted with [24] we originally called this problem OUTSIDE as the goal is to find a word outside a list of words.

**Definition 3.7 (MISSING-STRING<sub>k,n</sub>.)** An instance of MISSING-STRING<sub>k,n</sub> where $k < 2^n$ is given by $k$ elements $y_1, \dots, y_k \in \{0, 1\}^n$. A solution to this instance is an element $y \in \{0, 1\}^n$ such that $\forall i, y_i \neq y_i$.

**THEOREM 7 (MISSING-STRING<sub>k,n</sub> ∈ DTIME(nk²)).** MISSING-STRING<sub>k,n</sub> can be solved in time O(nk²) by a multi-tape Turing Machine
## 4.4 Resolution of $G(2, 2)$ case

This partial solution was chronologically the first to be proposed, by Corentin Henriet. We chose to present it since the strategy is different from the ones presented in the next sections and it provides interesting bounds.

This strategy is oblivious. We will thus define the single map $s$ used by both players. The strategy is winning as long as $N \ge 9$, showing that $\mathfrak{B}(2, 2, 1) \le 9$ (much better than the general bound obtained in section 5, which gives 216). In this specific case, we can also prove that $\mathfrak{B}(2, 2, 1) > 5$ (to be compared to 4 – the general lower bound obtained in theorem 6).

**Definition 4.3 (Strategy $s$).** We intuitively understand our inputs as being on a "clock" from 1 to $N$, i.e. the successor of $N$ is 1. Let $(x, y)$ be our inputs ordered such that the distance between $x$ and $y$ is less than the distance from $y$ to $x$ when read in the clockwise direction. If $y = x + 1$ or $y = x + 2$, then $s(x, y) = x - 2$, otherwise we define $s(x, y) = x + 1$.

**Theorem 8.** $\mathfrak{B}(2, 2, 1) \le 9$.

*Proof.* The proof consists in verifying that $s$ is a winning strategy. This is done by checking every possible scenario. $\square$

**Theorem 9.** $\mathfrak{B}(2, 2, 1) > 5$.

*Proof.* This is easily checked by pen and paper search. $\square$

While this strategy provides good bounds, we have not found a way to generalise it to more players or larger sets. The next section presents a general strategy for the 2-players case.

## 4.5 Graph strategies

This line of reasoning, and the corresponding winning strategy for $G(2, k, 1)$ was first obtained by Dmitriy Kunisky.

We first recall the definition of colored graphs and establish some useful notations.

**Definition 4.4 (Colored graphs).** Let $p \in \mathbb{N}$. A $p$-colored graph is a triple $(V, E, C)$ where $V$ is a set of vertices, $E \subseteq \{(x, y) \in V^2 \mid x \neq y\}$ is a set of edges, and $C: E \rightarrow [p]$ a coloring function mapping every edge to a color (an element of $[1; p]$).

The graph is said to be complete when $E = \{(x, y) \in V^2 \mid x \neq y\}$. We will moreover write $G_i = (V, E_i)$ the graph induced by selecting the edges of a given color $i$, i.e. $w \in E_i \Leftrightarrow w \in E \land C(w) = i$. Given $u, v \in V$, we write $u \sim v$ when $\{u; v\} \in E$; in this case we say that $u$ and $v$ are neighbors. We moreover write $u \stackrel{i}{\sim} v$ when $u \sim v$ and $C(\{u; v\}) = i$.
**PROOF.** For each $y \in \{0,1\}^n$ check if $\forall i, y \neq y_i$ if that is the case output $y$. Checking for one $y$ takes $kn$ time (words have $n$ bits here), since this happens for at most $k+1$ steps this problem is in $DTIME(nk^2)$. $\square$

In the following we prove that MISSING-STRING$_{k,n}$ is an easier problem than sorting, thus any sorting algorithm on multi-tape Turing machines would yield faster algorithms for MISSING-STRING$_{k,n}$. Using fusion sort we may show that sorting $k$ numbers of size $n$ on a multi-tape TM can be done in $O(nk \log(k))$.

**THEOREM 8 (SORTING IS IN $O(nk \log(k))$ ([20])]**. Sorting a list of size $[y_1, \dots, y_k]$ where $\forall i \le k, y_i \in \{0,1\}^n$ can be done in time $O(nk \log k)$ by a TM.

Using radix sort it might be possible to show that sorting can be performed in $O(n^2k)$ (see [20])

**LEMMA 1 (MISSING-STRING IS EASIER THAN SORTING).** Let $f$ be the function such that the problem of sorting $k$ numbers of $\{0,1\}^n$ is in $DTIME(f(k,n))$ then MISSING-STRING$_{k,n} \in DTIME(f(k,n))$

**PROOF.** Let $y_1, \dots, y_k$ be an instance of MISSING-STRING$_{k,n}$, sort the $y_i$, then check for gaps of more than 1 in the sorted list, output any number within this gap. $\square$

**THEOREM 9 (MISSING-STRING$_{k,n} \in DTIME(nk \log k))**. MISSING-STRING$_{k,n}$ can be solved in time $O(nk \log(k))$ by a multi-tape Turing Machine

**PROOF.** Direct application of theorem 8 and lemma 1. $\square$

In the RAM model everything is much easier.

**THEOREM 10.** In the RAM model MISSING-STRING$_{k,n}$ can be solved in time $O(kn)$.

**PROOF.** Let $y_1, \dots, y_k$ be an instance of MISSING-STRING$_{k,n}$, create an array $l$ of size $k$ containing only 0; for each $y_i$, if $y_i \le k$ do $l[y_i] = 1$ (where $y_i$ is interpreted as a number in $[0; 2^n - 1]$). Traverse list $l$ until you find an index $j$ such that $l[i] = 0$, output $j$. $\square$

# 4 NOVELTY GAMES

In this section, we introduce the combinatorial game behind our technique, under the name of *Novelty games*.

We remind the reader that $\binom{[N]}{k}$ denotes the set of all multisets included in $[1, N]$ of size at most $k$.

## 4.1 Definition

**Definition 4.1** ($G^N(p, k, m)$). The game $G^N(p, k, m)$ is defined as follows.

* There are $p$ players.

* Player $i$ receives a multiset $A_i \in \binom{[N]}{k}$; elements of $A_i$ are called inputs.

* Each player has $m$ tries.

* On each try a player answers an element of $[1; N]$.

An instance of the game $G^N(p, k, m)$ is a specific family $(A_i)_{i=1}^p$.

A strategy $\mathcal{S}$ for $G^N(p, k, m)$ is a family of functions $(s_i)_{i=1,...,p}$ where

$$s_i : \binom{[N]}{k} \times [m] \to [N].$$
We will now define a property of colored graphs which will be used later to define a winning strategy.

**Definition 4.5** ((*p*, *k*)-set property). Let *p*, *k* ∈ N. A *p*-colored graph *G* = (*V*, *E*, *C*) is said to have the (*p*, *k*)-set property if for every subset of vertex *A* ⊆ *V* of size *k* and every color *i* ∈ [1; *p*], the vertices in *A* have a mutual neighbor *v* in *G*<sub>*i*</sub>, i.e. such that for all *a* ∈ *A*, *a* ≁ *v*.

We will now explain how the (p, k)-set property ensures that one can
define a strategy for p players and sets of size k from a p-colored graph.
The intuition is the following: each input will correspond to a vertex, each
player will correspond to a color, and a player will use the (p, k)-set property
instantiated on its color to produce an output.

We now recall the notion of polychromatic cycle that will be useful to
discuss winning strategies.

**Definition 4.6 (Polychromatic cycles).** Let $p \in \mathbb{N}$ and $G = (V, E, C)$ be a $p$-colored graph. A cycle $c$ of $G$ is said to be polychromatic if edges in $c$ have pairwise different colors.

Note that a polychromatic cycle does not necessarily use all colors. The non-existence of polychromatic cycles will ensure that the strategy will be winning (i.e that no all player's answer are an input of another one). For the interested reader, graphs with no polychromatic cycles have been studied here [2, 1].

**Definition 4.7 (Good graphs).** Let $p, k \in \mathbb{N}$, and let $G$ be a $p$-colored graph. We say that $G$ is $(p, k)$-good if it has the $(p, k)$-set property and has no polychromatic cycles.

We now formally describe the strategy induced by a (p, k)-good graph
G = (V, E, C) with V = [1; N]. The map s_i^G : ([N])_k \to [N] defining the
strategy of the i-th player is defined as s_i^G(A) = y where y is any vertex
(for instance, the smallest) such that \forall x \in A, x \stackrel{i}{\sim} y. Such a y always exists
thanks to the (p, k)-set property. We can then establish that the absence of
polychromatic cycles implies that this strategy is winning.

**Theorem 10.** Let $p, k \in \mathbb{N}$ and let $G$ be a $p$-colored graph with $N$ vertices. If $G$ is $(p, k)$-good, the strategy $\mathcal{G} = (s_i^G(A))_{i \in [1; p]}$ is winning for the game $G^N(p, k, 1)$.

*Proof.* Suppose the strategy is not winning. Then there exists an occurence
$A_1, \dots, A_p$ of the game for which the strategy fails (here $A_i$ denotes the set of
inputs of player $i$). Consider a graph $H$ where the vertices are players $P_1$ to
$P_p$, with a directed edge from $P_i$ to $P_j$ if the answer of player $i$, i.e. $s_i^G(A_i)$,
belongs to the set of inputs $A_j$ of player $j$. By assumption, there exists a
The players collectively win the instance $(A_i)_{i=1}^p$ of $\mathcal{G}^N(p, k, m)$ if there exists a pair $(i, j) \in [p] \times [m]$ such that $s_i(A_i, j) \notin \cup_{i=1}^p A_i$.

A winning strategy for $\mathcal{G}^N(p, k, m)$ is a strategy such that all instances of the game are won.

When $m = 1$, we may write $\mathcal{G}^N(p, k)$ instead of $\mathcal{G}^N(p, k, 1)$. We may sometimes drop the $N$ and write $\mathcal{G}(p, k)$

**Definition 4.2 (Oblivious strategy).** When all players have the same strategy, i.e. when $\mathcal{S} = (s_i)_{i=1}^p$ is such that there exists a function $s$ with $s_i = s$ for all $i = 1, \dots, p$, we say that $\mathcal{S}^M(p, k, m)$ is *oblivious*.

We purposefully use the term oblivious rather than uniform to avoid confusion with uniformity in the computable sense.

**Definition 4.3 (B(p, k, m))**. We define $\mathfrak{B}(p, k, m)$ as the smallest integer $N$ such that there exists a winning strategy for game $\mathcal{G}^N(p, k, m)$.

We note that $\mathfrak{B}(p, k, m)$ is always less than $+\infty$, as proven in section 5.2. Establishing an estimate of $\mathfrak{B}(p, k, m)$ in general is open.

**4.2 General remarks about Novelty games**

**Sets.** The first remark is that one may only consider sets of size exactly $k$ instead of multisets of size at most $k$. This is because the hardest case for the strategy is when each player has $k$ different numbers. Indeed, suppose there exists a strategy $\mathcal{S}$ winning in all instances of the game for which players have a set of size $k$ (or, equivalently, a multiset of size $k$ without repetitions). Then one can easily construct a winning strategy for all multisets: when the considered multiset have less than $k$ distinct numbers, you may always add arbitrary numbers to have $k$ of them. One can apply the strategy $\mathcal{S}$ on the resulting set. A routine check suffices to show that this strategy is winning.

In the following, we will therefore always assume that inputs are pairwise distinct, and that we may add arbitrary new inputs so that sets have size exactly $k$.

We also note that inputs are not ordered, since we work with sets and not tuples. But we may suppose, if need be, that they are by choosing an arbitrary order relation.

The next theorem states that the existence of strategy for inputs in $[1; N]$ implies the existence of a strategy for inputs in $[1; M]$ for all $M \ge N$. This motivates the definition of $\mathfrak{B}$.

**THEOREM 11.** Let $M, N \in \mathbb{N}$ such that $M \ge N$. If $\mathcal{G}^N(p, k, m)$ has a winning strategy then so does $\mathcal{G}^M(p, k, m)$.

**PROOF.** We treat the case $M = N + 1$ and then we can conclude by induction. Let $\mathcal{S}$ be a winning strategy for $\mathcal{G}^N(p, k, m)$. We define a strategy $\mathcal{S}'$ for the game $\mathcal{G}^M(p, k, m)$ as follows. If $M$ is not an input of a player, then this player simply runs $\mathcal{S}$. Otherwise, each player replaces $M$ by $N$ and runs the strategy $\mathcal{S}$ on the resulting set. One easily checks that $\mathcal{S}'$ is a winning strategy for $\mathcal{G}^M(p, k, m)$ since the output of $\mathcal{S}'$ is in $[1; N] \subset [1; M]$. $\square$

Next theorem proves the intuitive result that having more players, more inputs and less tries makes the game harder.

**THEOREM 12.** For all $p, k, m \in \mathbb{N}$, and all $a, b, c \in \{0, 1\}^3$,

$$ \mathfrak{B}(p - a, k - b, m + c) \le \mathfrak{B}(p, k, m). $$
cycle in this graph (otherwise the strategy is winning on this occurrence). But one can check that a cycle in $H$ implies the existence of a polychromatic cycle in $G$, leading to a contradiction. □

The last step is now to show that (2, k)-good graphs exist. We will then discuss, in subsection 4.5.2, the unlikely existence of (p, k)-good graphs for $p > 2$ and $k \ge 2$.

### 4.5.1 Graph strategies for (2, k)

**Theorem 11.** For any $k \in \mathbb{N}$, there exists a (2, k)-good graph.

*Proof.* We will prove that there exists an undirected uncolored graph $G = (V, E)$ such that for every $A \in \binom{[N]}{k}$:

* $\exists a, \forall x \in A, x \sim a$;

* $\exists b, \forall x \in A, x \sim b$.

This is sufficient to prove the existence of a (2, k)-good graph by converting every edge to a 1-colored edge and adding a 2-colored edge for every pair of vertices $x \neq y$ such that $x \sim y$. Note that this graph has no polychromatic cycles of size 2 since two vertices cannot be simultaneously neighbors and non-neighbors.

We now prove the existence of such graphs using the probabilistic method. Let $G$ be an Erdős-Rényi graph with edge probability $\frac{1}{2}$ on the vertex set $[1; N]$. Then, the probability $\mathbb{P}[G$ is $k$-good] goes to 1 as $N$ goes to $\infty$:

$\mathbb{P}[G$ is not $k$-good]

$$ \le \mathbb{P}[\text{some } i_1, \dots, i_k \in [N] \text{ have no mutual neighbor}] + \mathbb{P}[\text{some } i_1, \dots, i_k \in [N] \text{ have no mutual non-neighbor}] $$

$$ \le 2 \cdot \mathbb{P}[\text{some } i_1, \dots, i_k \in [N] \text{ have no mutual neighbor}] $$

$$ \le 2 \binom{N}{k} \mathbb{P}[1, \dots, k \text{ have no mutual neighbor}] $$

$$ \le 2 \binom{N}{k} \left(1 - \frac{1}{2k}\right)^{N-k} $$

$$ \le 2 \exp \left( k \log N - \frac{N-k}{2k} \right) $$

Note we used symmetry to deduce the second inequality. □

For large values of $k$, we have that $2 \exp(k \log N - \frac{N-k}{2k})$ is less than 1 when $N = O(k^3 2^k)$. The general bound of section 6 gives a worse bound $O(2^{k^2 \log k})$.
PROOF. This is proven by noticing that a strategy for the game $G^M(p, k, m)$ is also a strategy for $G^M(p-a, k-b, m+c)$: it suffices to add $b$ inputs arbitrarily, apply the strategy on those (since there are less players, the strategy determines a map for each player – and the maps $s_i$ for $i = p-a+1, \dots, p$ are unused), and guess $c$ arbitrary additional outputs. $\square$

We believe establishing recurrent relations between values of $\mathfrak{B}$ is hard when varying the number of players, numbers, tries or the size of the set of inputs. For instance, it is not even clear how the inequality of theorem 12 can be made strict.

We now start by proving a simple lower bound on $\mathfrak{B}$.

THEOREM 13 (TRIVIAL LOWER BOUND ON $\mathfrak{B}$). For all $p, k, m \in \mathbb{N}$, $\mathfrak{B}(p, k, m) \ge pk + 1$.

PROOF. It is easy to realise that there are no winning strategy if $N = pk$: if for all $i \in [1; p]$, player $i$ has as inputs $[(i-1)k+1; ik]$, then the set of all inputs is equal to $[1; pk]$ and no player may output a new number. $\square$

Another easy result to establish is that if one allows for enough tries, the value of $\mathfrak{B}$ can be determined (and is low).

THEOREM 14. For all $p, k \in \mathbb{N}$, $\mathfrak{B}(p, k, k) = pk + 1$.

PROOF. Let $N = pk + 1$. Each player calls its inputs $i_1, \dots, i_k$. On its $j$-th try each player does this: if $i_j + 1 \le N$ it answers $i_j + 1$ otherwise it outputs 1. It's routine to check that this is a winning strategy. $\square$

The study of multiple tries has proven to be hard. Apart from quite obvious results, we have not found ways to improve on the results we obtain in the one-try variant. We therefore leave the following question for future work.

**Question 1.** Can we find a better bound for $\mathfrak{B}(p, k, k-1)$ than $\mathfrak{B}(p, k, 1)$?

We summarize the results of this paper in fig. 7. There may be several results for the same game as we establish it in different manners throughout the paper.

<table><caption>(a) Bounds for general values $p, k$</caption><thead><tr><th>Game</th><th>(p, k)</th><th>(p, k)</th><th>(p, k, k)</th></tr></thead><tbody><tr><td>Upper bound</td><td>(k<sup>p</sup>)<sup>k<sup>p</sup></sup></td><td>2<sup>5k<sup>p-1</sup></sup></td><td>pk + 1</td></tr><tr><td>Reference</td><td>theorem 17</td><td>theorem 36</td><td>theorem 14</td></tr></tbody></table>

<table><caption>(b) Bounds for specific values</caption><thead><tr><th>Game</th><th>(2, 2)</th><th>(2, 2)</th><th>(1, k)</th><th>(p, 1)</th><th>(2, k)</th><th>(2, k)</th></tr></thead><tbody><tr><td>Upper bound</td><td>9</td><td>7</td><td>k + 1</td><td>p + 1</td><td>k<sup>3</sup>2<sup>k</sup></td><td>O(k<sup>2</sup>2<sup>k</sup>)</td></tr><tr><td>Reference</td><td>theorem 24</td><td>fig. 11</td><td>theorem 14</td><td>theorem 14</td><td>section B.2</td><td>section C</td></tr></tbody></table>

Fig. 7. Bound on $\mathfrak{B}(p, k, m)$ (when $m=1$ it is omitted)

**Key lemma for establishing winning strategies for $G^N(p, k, 1)$** We now introduce a lemma which we will use to show that our strategies are winning. At its core the lemma states the following : Given a strategy $\mathcal{S}$, draw an edge between player $i$ and $j$ if player $i$'s answer belongs to the set of inputs of player $j$. If there is no cycle in this graph then the strategy is winning.
**Size and running time of the graph strategy.** If we want to use a strategy based on graphs in the programs of section 5 to show $[f, \alpha T] \subsetneq [f, T]$, we need a succinct description of such graphs. Indeed, the program needs to be of size less than $f$. Note however that we have only demonstrated the existence of a (2, $k$)-good graph thanks to the probabilistic method. The best we can naively do is then to hardcode those graphs in the strategy. This would make the strategy really large in terms of bits (close to $N^2 = 2^{2n}$), but our programs can never be bigger than $f < n$ bits. Another approach is to let the programs find those graphs by itself: every program $p(\#^T, i)$ enumerates and tests graphs in ascending lexicographic order until it finds a good graph, and then use it for its strategy. While this strategy takes $O(1)$ bits to describe, it takes at least $2^n$ steps to run implying that one could only establish bounds for $T > 2^n$.

We also hint (but not formally prove) at a method of constructing (2, $k$)-good graphs without using probability theory. We briefly describe such a potential graph using the notion of pseudorandom *Paley graph* from number theory. A Paley graph is a graph $G$ on a prime number $p \equiv 1 \mod 4$ of vertices. Vertices of $G$ are identified with integers modulo $p$, and there exists an edge $i \sim j$ if and only if $i - j$ is congruent to a square modulo $p$, i.e. if and only if $\exists k, i - j = k^2 \mod p$. The condition $p \equiv 1 \mod 4$ ensures that the relation $\sim$ is symmetric.

Finding a mutual neighbor of $x_1, \dots, x_k$ then amounts to solving the system of equations $\{y - x_i = z_i^2\}$ in variables $y, z_1, \dots, z_k$. One may check, using character sum estimates, that many integers $y$ satisfying these equations exist, for any choice of $z_1, \dots, z_k$, as long as $p$ is sufficiently large.

### 4.5.2 Graph Strategies for $(p, k)$

In the previous section, we established the existence of winning strategies for the games $G^N(2, k, 1)$, defined from colored graphs. Can we generalise the approach to obtain winning strategies for all games $G^N(p, k, 1)$? If we were to follow the same method, we would need the existence of $(p, k)$-good graphs. Unfortunately, we have not been able to prove or disprove the existence of such graphs for $p > 2$. However, we can establish that their are no complete $(p, k)$-good graphs (note that the (2, $k$)-good graphs we came up with are complete).

**Definition 4.8.** A $p$-colored graph $G$ is said to be connected for color $i$ if there is a $i$-colored path between any two vertices in $G$

**Theorem 12.** (Proven in [2]) Let $G$ be a complete $p$-colored graph. If $G$ has no polychromatic cycles, then $G$ is connected for at most 2 colors.

**Theorem 13.** There are no complete $(p, k)$-good graphs for $p > 2$ and $k \ge 2$.
**LEMMA 2.** Let $\mathfrak{S} = (s_i)_{i=1,...,p}$ be a strategy for game $\mathcal{G}^N(p, k, 1)$. Let $A_i$ be the inputs of player i. Define $H(A_1,...,A_p) = (V, E)$ as a directed graph where $V = \{[1;p]\}$ and $i \to j$ if and only if the answer of player i, belongs to the set of inputs $A_j$ of player j, i.e. $(i, j) \in E$ if and only if $s_i(A_i) \in A_j$. We claim that if for all inputs $A_1,...,A_p$ there are no cycle in $H(A_1,...,A_p)$ then $\mathfrak{S}$ is winning.

**PROOF.** If $\mathfrak{S}$ is not winning on input $A_1,...,A_p$ then it is by definition because no answer of any player is outside $\cup_{j=1}^p A_j$. Thus in graph $H(A_1,...,A_p)$ for all vertices $i$, there exists a $j$ such that $i \to j$. We claim that since all vertices have at least one outgoing edge there must be a directed cycle in $H$. Indeed we can find a cycle by starting from any vertex and performing a depth-first search, this DFS never reaches a dead end (because all vertices have an outgoing edge) and at some point we will visit a previously visited vertex. Thus there is a cycle in $H$. $\square$

We believe answering the following question may lead to some insight about novelty games.

**Question 2.** Is the converse implication of lemma 2 true when $N = \mathfrak{B}(p, k, 1)$ ?

Note that if $N > \mathfrak{B}(p, k, 1)$ we may trivially come up with counter examples to the converse of Lemma 2.

**4.3 Relation between novelty games and time hierarchy for $K^t$**

In this section we establish links between $\mathfrak{B}$ and the best result we may get in order to show that $\exists_{\infty} n, [f, \alpha T](n) \notin [f, T](n)$. We ignore for now implementations of specific strategies (in particular running time and size). We remind the reader that the goal is to have $\alpha = o(2^f)$, and hopefully show the conjecture for all $f < n$. All of this leads us to studying game $\mathcal{G}^N(p, k, m)$ where:

* $p = 2^f / \alpha$;

* $k = \alpha$;

* $m = k/g$ where $g$ is any reasonable increasing function (thought of as slow growing);

* $N = 2^n$.

Our bound $\mathfrak{B}(p, k, m)$ should be less than $N$ because a program must answer a string of size $n$ (i.e. an integer of $[N]$). We are thus interested in the regime where $\alpha, f$ (or alternatively $(p, k, m)$ with the above equalities) are such that :

$$ \mathfrak{B}(p, k, m) < N \Leftrightarrow \exists g \text{ reasonable and increasing, } \exists_{\infty} n, \mathfrak{B} \left( \frac{2^{f(n)}}{\alpha(n)}, \alpha(n), \frac{\alpha(n)}{g(n)} \right) \le 2^n. $$

Restricting our views to the one try setting, we make some hypothesis on the form of $\mathfrak{B}(p, k)$ from least to most likely, and see what is the best $\alpha$ and $f$ we may get (we disregard all potential problems with running time and size of the winning strategy).

(1) **Hypothesis $\mathfrak{B}(p, k) \le (pk)^c$ for $c \in \mathbb{R}$**. We may establish the theorem for $f < \frac{n}{c}$ and any reasonable $\alpha$.

(2) **Hypothesis $\mathfrak{B}(p, k) \le p^k$**. For any $\alpha$ reasonable we may establish the theorem for $f < \frac{n}{\alpha}$.

(3) **Hypothesis $\mathfrak{B}(p, k) \le k^p$**. We may establish the theorem when $2^f < an$. For $f = \omega(\log(n))$ this may only lead to a slight improvement when compared with Longpré's result.
*Proof.* Let $G = (V, E, C)$ be a complete $(p, k)$-good graph. Then for any color $i$ and any two vertices $u, v \in V$, there exists $w \in V$ such that $u \stackrel{i}{\sim} w$ and $v \stackrel{i}{\sim} w$. This implies that $u$ and $v$ are connected for every color. Whenever there are $p \ge 3$ colors, this contradicts Theorem 12 □

**Can graph strategies be salvaged?** Graph strategies are an interesting approach, and they provide – in the case $p=2$ –, better bounds that the general strategy defined below. However it is unclear if $(p, k)$-good graphs exist. An approach would be to get rid of them altogether and try to understand what kind of graphs we could be used for the multiple tries setting. Surely, such graphs would have less stringent requirements (but which requirements this is remains unclear at the moment). Another approach would be to consider uncolored but *directed* graphs instead of colored undirected graphs, requiring the following properties:

* there exists no cycles of length less than $p$;

* for any set $i_1, \dots, i_k$ there exists a vertex $b$ such that $\forall j \in [1; k], i_j \to b$ (i.e. there exists a directed edge of source $i_j$ and target $b$).

If we could prove the existence of such graphs, it could be used to define a winning strategy for the game $\mathcal{G}(p, k, 1)$. Indeed, every player would answer a common “directed” neighbor of its $k$-inputs using the second property. The fact that the strategy is winning would then directly follow from the first property. However, the existence of such graphs also remains an open question at the moment.

# 5 Formal description and analysis of the programs

Recall that we want in the end to show that $[f, \alpha T] \not\subseteq [f, T]$. The functions $f(n)$, $\alpha(n)$ and $T(n)$ are all supposed to be in $\text{DTIME}(T(n))$, i.e. there is a program which computes them in $O(T(n))$ steps and which can be hardcoded into any program for a cost of $O(1)$ bits. We also suppose that $\alpha$ is less than $K^{T(n)}(n)$ for infinitely many $n$; as established by theorem 3, this is not a stringent condition.

In the following, we will often drop the arguments of the functions and write, for instance, $f$ instead of $f(n)$. We also suppose w.l.o.g. that $T(n) > n$ and $f < n$. Indeed, if $T(n) < n$, then it is not possible to write any string of length $n$ in the allocated time, and if $f \ge n$ then all inputs have a description of size bounded by $f$ and there are no gap in the hierarchy. We also assume for simplicity that $2^f$ is divisible by $\alpha$.

We will in the end only be interested in values of $n$ for which there exists a program $\#^T n$ outputting $n$ in $T$ steps or less, and such that $\alpha(n) > K^T(n)$. A careful reading of the proof of theorem 3 ensures the existence of infinitely many such $n$.
# 5 GENERAL STRATEGY FOR $G(p, k)$

We now exhibit an oblivious strategy for any number of players and inputs. We start by detailing the (3,2) case which is naturally generalized to any $(p, k)$.

The strategy exposed in this section is the one used for proving the results of part 7. Another general strategy, of independent interest, can be found in appendix B.2.

## 5.1 Strategy for (3,2)

We expose a strategy for game $G^N(3,2)$ when $N = 15^7$, the reason for such a $N$ will be made apparent later. All players will execute function $F_{(3,2)}: N^2 \to N$ defined in 5.2. We will see inputs as number in base $m = 15$.

**Definition 5.1 (Writing in base $m$).** Let $x \in N$, $m \in \mathbb{N}$, $x = \overline{x_k \dots x_2 x_1}^m$, where the $x_i \in [0; m-1]$ are uniquely defined to satisfy $x = \sum_{i=0}^{k-1} x_{i+1} \cdot m^i$. We may drop the $\overline{m}$ if we specify the base beforehand.

**Definition 5.2** $(F_{(3,2)})$. The function $F_{(3,2)}$ is defined on $[0, 15^7]$ as follows:

Let $x, y \in N$, let $x_7x_6x_5x_4x_3x_2x_1$ and $y_7y_6y_5y_4y_3y_2y_1$ denote their representation in base 15.

$$F_{(3,2)}(x, y) \stackrel{\text{def}}{=} \overline{x_3x_2y_3y_2x_1y_1v^{15}} \quad (1)$$

$$= x_{3.15^6} + x_{2.15^5} + y_{3.15^4} + y_{2.15^3} + x_{1.15^2} + y_{1.15} + v \quad (2)$$

where $v \in \{0, \dots, 14\}$ is the smallest number such that $\forall i \in [1; 7], v \neq x_i$ and $v \neq y_i$

Note that by definition $F_{(3,2)}(x, y)$ is necessarily different from $x$ and $y$. And $v$ in the definition exists because $m = 15$. $v$ could have been taken to be any number different from all $x_i$ and $y_i$, not necessarily the minimum.

**THEOREM 15.** *The function $F_{(3,2)}$ provides an oblivious winning strategy for 3 players with 2 inputs.*

**PROOF.** We will denote by $a, b$ the numbers given to player 1, by $c, d$ the numbers given to player 2, and by $e, f$ the numbers given to player 3. The goal is to show that if each player applies the function $F_{(3,2)}$ then they always collectively win the game.

As in the definition above, we write $a = a_7a_6a_5a_4a_3a_2a_1$ the base 15 representation of $a$, $b = b_7b_6b_5b_4b_3b_2b_1$ the base 15 representation of $b$, etc.

If $F_{(3,2)}(a, b)$ is different from $c, d, e, f$, the players have won the game. Suppose now that we are in the case where $F_{(3,2)}(a, b) \in \{c, d, e, f\}$. Without loss of generality, we can suppose that $F_{(3,2)}(a, b) = c$. We have in particular that: $c_1 \neq a_i$ for all $i \in [1, 7]$, $c_1 \neq b_i$ for all $i \in [0, 6]$, $c_3 = a_1$, $c_6 = a_2$, and $c_7 = a_3$.

We now consider the result produced by player 2, that is $F_{(3,2)}(c, d)$. Once again, if this value is different from $a, b, e, f$ then the game is won. If this is not the case, there are two cases.

The first case is $F_{(3,2)}(c, d) \in \{a, b\}$. We now show that this is impossible. By definition, $F_{(3,2)}(c, d)$ is different modulo 15 from all $c_i$ ($i \in [1, 7]$), but $c_2$ is the remainder modulo 15 of $b$ and $c_3$ is the remainder modulo 15 of $a$. Hence the value of $F_{(3,2)}(c, d)$ modulo 15 is different from the values of $a, b$ modulo 15.

The second case is $F_{(3,2)}(c, d) \in \{e, f\}$. Without loss of generality, we suppose $F_{(3,2)}(c, d) = e$. We will now have to show that $F_{(3,2)}(e, f) \notin \{a, b, c, d\}$. Let us write $z = z_7z_6z_5z_4z_3z_2z_1$ the representation of $F_{(3,2)}(e, f)$ in base 15. By definition of $F_{(3,2)}$, $z_1 \neq e_i$ for all $i \in [1, 7]$. But since $F_{(3,2)}(c, d) = e$ and $F_{(3,2)}(a, b) = c$, we have the following properties: $e_2 = d_1$, $e_3 = c_1$,
For the moment, we will assume that for all $p, k, m, N \in \mathbb{N}$, we have a strategy (not necessarily winning) $\mathfrak{S}^N(p, k, m) = (\sigma_i^N(p, k, m))_{i \in [p]}$ for the game $\mathcal{G}^N(p, k, m)$, where $\sigma_i^N$ is the map defining the strategy for player $i$. The following definition of programs does not depend on the specific strategy considered, but it should be clear that their analysis will be dependent on this choice.

## 5.1 One try variant

We formally define the program which is intended to output a string in $[f, \alpha T](n)$ and not in $[f, T](n)$ when the strategy $\mathfrak{S}^N(p, k, 1)$ is winning. We then proceed with the size and running time analyses.

**Definition of the program $p$** The program $p$ takes as input two strings of $\{0; 1\}^*$:

* $^{\#T}n$ is taken to be the smallest program outputting $n$ in $T(n)$ steps or less;

* $i$ which is the number of the chunk of programs to be run: it ranges between 1 and $2^f/\alpha$.

The program $p(\#n^T, i)$ then performs the following computations:

1. It runs the program $^{\#T}n$ until it stops. We call $n$ its output.

2. It computes $f(n)$, $T(n)$, and $\alpha(n)$.

3. It creates an empty list $l$ which will be used to store the outputs.

4. For $j$ ranging from 0 to $\alpha - 1$, it simulates the program number $(i - 1)\frac{2^f}{\alpha} + j$ running for $T(n)$ simulation steps$^6$: if this program outputs a value before stopping, it adds the output to the list $l$.

5. It runs the strategy $\sigma_i^N(\frac{2^f(n)}{\alpha(n)}, \alpha(n), 1)$, where $N = 2^n$ and $m$ is the size of list $l$, on inputs $l[0], l[1], \dots, l[m-1]$, and outputs the result.

**Size analysis.** We now analyze the size of $p(\#Tn, i)$:

* $^{\#T}n$ is of size $K^T(n)$ (by definition);

* $i$ is an integer in $[1; 2^f/\alpha]$, hence it is of size $f - \log(\alpha)$.

* $(\#Tn, i)$ can be uniquely described by a string of size $K^T(n)+\log(K^T(n))+f - \log(\alpha)$ from theorem 1;

<footnote>$^6$On the universal Turing machine used to define our Kolmogorov complexity</footnote>
$e_6 = c_2 = b_1$, $e_7 = c_3 = a_1$. Thus $z_1$ is different from $a_1$, $b_1$, $c_1$, and $d_1$. This proves that $F_{(3,2)}(e, f) \neq a, b, c, d$, and therefore the game is won. □

The function behind the strategy can be explained informally as follows. We call antecedent of $x$ any $a$ such that $\exists b, F(a, b) = x$. Given two arguments $x, y$, we make it so that their digits when written in base $m$ correspond to the remainders modulo $m$ of their antecedents through $F$. Here $m$ will be chosen to be equal to 15, as explained below. Remind that by lemma 2 we need no cycles of size $\le 3$ to appear, i.e. player 1 answering an input of player 2, player 2 answering an input of player 3 and player 3 answering an input of player 1. Thus we keep track of the values of such remainder up to depth-2 antecedents (i.e. antecedents of antecedents). For instance, $x$ will be written as $x = x_7x_6x_5x_4x_3x_2x_1$ in base $m$, and we understand:

* $x_2, x_3$ as the remainders of the antecedents of $x$,

* $x_4, x_5$ as the remainders of the antecedents of $x_2$,

* $x_6, x_7$ as the remainders of the antecedents of $x_3$.

Similarly, we suppose the writing of $y = y_7y_6y_5y_4y_3y_2y_1$ to keep track of the remainders modulo $m$ of the antecedents of $y$.

The function $F_{(3,2)}$ then just implements this notion of keeping track of the antecedents, while producing a fresh value modulo $m$. More precisely, given $x = x_7x_6x_5x_4x_3x_2x_1$ and $y = y_7y_6y_5y_4y_3y_2y_1$, the function $F$ will pick a value $v \notin \{x_1, \dots, x_7, y_1, \dots, y_7\}$. Since there are 14 values in the latter set, choosing $m = 15$ ensures that this is always possible. The function is then defined as

$$F_{(3,2)}(x_7x_6x_5x_4x_3x_2x_1, y_7y_6y_5y_4y_3y_2y_1) = x_3x_2y_3y_2x_1y_1v.$$

Figure 8 should clarify the definition of $F_{(3,2)}$.
• the program $p$ is of size $O(1)$.

We conclude that $p(\#^T n, i)$ is of size $K^T(n) + f - \log(\alpha) + O(1)$. This is strictly less than $f(n)$ for infinitely many values of $n$ (for any reasonable function $\alpha$ see theorem 3).

**Running time analysis.** The steps 1 to 4 take time $\alpha T$ to compute. The running time of step 5 depends on the specific strategy $\mathcal{S}^N(2^f/\alpha, \alpha)$ we choose to implement. Hopefully this running time can be kept in $O(\alpha T)$, otherwise we cannot (directly) conclude.

**Correctness analysis.** Suppose that the strategy $\mathcal{S}^{2^n}(\frac{2^{f(n)}}{\alpha(n)}, \alpha(n))$ used in the program is a winning strategy for the game $\mathcal{G}^{2^n}(\frac{2^{f(n)}}{\alpha(n)}, \alpha(n))$. Let $\#n$ be a program outputting $n$. Then, by construction, there exists $i \in [1, 2^f/\alpha]$ such that $p(\#n, i)$ outputs a number of size $n$ which is not the output of any program of size $f$ in less than $T$ steps.

**Conclusion** Size and running time analysis are meant to prove that the output of $p(\#^T n, i)$ is in $[f, \alpha T](n)$. Correctness analysis shows that for at least one $i$, $p(\#^T n, i)$ is not in $[f, T](n)$. Thus showing $[f, T](n) \subsetneq [f, \alpha T](n)$.

## 5.2 Multiple tries variant

Let $g$ be a very slow-growing reasonable function computable in $T(n)$ steps, such as $g = \sqrt{\log^*}()$. The multiple tries setting is quite similar to the one try setting, except that we will have an additional input $j$ indicating which try is computed. We formally define the program which is intended to output a string in $[f, \alpha T](n)$ and not in $[f, T](n)$ when the strategy $\mathcal{S}^N(p, k, m)$ is winning.

**Definition of the program p.** The program $p$ now takes as input three strings of $\{0; 1\}^*$:

• $\#^t n$ as in the one-try case;

• $i$ as in the one-try case;

• an integer $j$ ranging in $[1; \alpha/g]$.

The program $p(\#n, i)$ then performs the following computations.

1. It follows the steps 1, 2, 3, and 4 of the program defined for the one try variant.

2. It runs the strategy $\sigma_i^N(\frac{2^{f(n)}}{\alpha(n)}, \alpha(n), j)$, where $N = 2^n$ and $m$ is the size of list $l$, on inputs $l[0], l[1], \dots, l[m-1]$, and output the $j$-th answer.
<figure><img src="image_7.png" /><figcaption>Fig. 8. Construction tree for $F_{(3,2)}$</figcaption></figure>
**Size analysis.** We analyze the size of $p(\#^T n, i)$:

• $\#^T n$ can be chosen to be of size $K^T(n)$ (by definition);

• $i$ is of size $f - \log(\alpha)$;

• $j$ is of size $\log(\alpha) - \log(g)$;

• $(\#^T n, i)$ can be uniquely described by a string of size $O(K^T(n)) + f - \log \alpha$;

• the program $p$ is of size $O(1)$.

As a consequence, $p(\#^T n, i)$ is of size $O(K^T(n)) + f - \log(\alpha) + O(1)$.

**Running time and correctness.** The analysis is similar to the one try case.

# 6 General Strategy for (p, k)

We will now exhibit a general strategy. This is an oblivious$^7$ strategy: the same function is used by all players. Intuitively, we will be using the remainder of arguments modulo some large enough number $m$ to ensure disjointness. The strategy however remains involved as it requires to keep track of the remainders modulo $m$ of antecedents.

We will start by detailing the (3,2) case before generalising to any pair $(p,k)$.

## 6.1 Strategy for (3,2)

The function $M^2 \to M$ behind the strategy can be explained informally as follows. Given two arguments $x, y$, we will suppose their digits when written in base $m$ correspond to the remainders modulo $m$ of their antecedents through $F$. Here $m$ will be chosen to be equal to 15, as explained below. Since we need to ensure that no cycles of size $\le 3$ appear, we will need to keep track of the values of such remainder up to depth-2 antecedents (i.e. antecedents of antecedents). For instance, $x$ will be written as $x = x_7x_6x_5x_4x_3x_2x_1$ in base $m$, and we understand:

• $x_2, x_3$ as the remainders of the antecedents of $x$ through $F$,

• $x_4, x_5$ as the remainders of the antecedents of $x_2$ through $F$,

• $x_6, x_7$ as the remainders of the antecedents of $x_3$ through $F$.

<footnote>$^7$We chose not to use the term *uniform* as to not create confusion with the uniformity of computability theory</footnote>
<figure><img src="image_8.png" /><figcaption>Fig. 9. Construction for $F_{(4,k)}$</figcaption></figure>

## 5.2 General strategy for (p,k)

We now expose the general strategy. The construction follows the (3,2) case of figure 8. The reader may look at figure 9 to see further generalization. Coming up with a formal strategy from figure 9 is then just a matter of counting how many digits we need to keep track of antecedent. This then leads to a base $m$ big enough so that $v$ can be different from all those digits. Once we have these two ingredients we know $N$ the smallest integer such that our inputs live in $[1; N]$ and our strategy works.

Let us explain the construction in plain English: the main insight of the strategy was to book-keep the remainders modulo $m$ of the potential antecedents up to depth 2. For general $(p, k)$, we will therefore keep track of the remainders of potential antecedents up to depth $p-1$. This means that for each of the $k$ arguments, we will need values modulo $m$ of the potential $1 + k + k^2 + k^3 + \cdots + k^{p-1}$ antecedents. Since there are $k$ arguments, this means that we will be manipulating $k(1 + k + k^2 + k^3 + \cdots + k^{p-1})$ values modulo $m$, and produce a fresh value. This implies that $m$ should be greater or equal to $1 + k(1 + k + k^2 + k^3 + \cdots + k^{p-1}) = \frac{k^{p+1}-1}{k-1}$.
Similarly, we suppose the writing of $y = y_7y_6y_5y_4y_3y_2y_1$ to keep track of the remainders modulo $m$ of the antecedents of $y$.

The function $F_{(3,2)}$ then just implements this notion of keeping track of the antecedents, while producing a fresh value modulo $m$. More precisely, given $x = x_7x_6x_5x_4x_3x_2x_1$ and $y = y_7y_6y_5y_4y_3y_2y_1$, the function $F$ will pick a value $\nu \notin \{x_1, \dots, x_7, y_1, \dots, y_7\}$. Since there are 14 values in the latter set, choosing $m = 15$ ensures that this is always possible. The function is then defined as

$$F_{(3,2)}(x_7x_6x_5x_4x_3x_2x_1, y_7y_6y_5y_4y_3y_2y_1) = x_3x_2y_3y_2x_1y_1\nu.$$

The following illustration should clarify the definition of $F_{(3,2)}$.

<figure><img src="image_2.png" /></figure>

**Definition 6.1.** The function $F_{(3,2)}$ is defined on $[0, 15^7]$ as follows:

$$F_{(3,2)}(x, y) = x_3 \cdot 15^6 + x_2 \cdot 15^5 + y_3 \cdot 15^4 + y_2 \cdot 15^3 + x_1 \cdot 15^2 + y_1 \cdot 15 + \nu,$$

where $x = \sum_{i=0}^{6} x_{i+1} \cdot 15^i$, $y = \sum_{i=0}^{6} y_{i+1} \cdot 15^i$, and $\nu \in \{0, \dots, 14\}$ does not belong to $\{x_i | i = 1, \dots, 7\} \cup \{y_i | i = 1, \dots, 7\}$.

Note that by definition $F_{(3,2)}(x, y)$ is necessarily different from $x$ and $y$.

**Theorem 14.** The function $F_{(3,2)}$ provides a uniform winning strategy for 3 players with 2 numbers.
Now, since we need to book-keep $1 + k + k^2 + k^3 + \cdots + k^{p-1} = \frac{k^p-1}{k-1}$ antecedents, we need to work with numbers with $\frac{k^p-1}{k-1}$ digits and thus:

$$N \geq m^{\frac{k^p-1}{k-1}} \geq \left( \frac{k^{p+1}-1}{k-1} \right)^{\frac{k^p-1}{k-1}}.$$

We will here suppose that $N$ is minimal, i.e. the above inequality is in fact an equality. We introduce the notation $k^{(d)} = \frac{k^d-1}{k-1}$; by convention, we define $k^{(0)} = 0$. Notice $k^{(d)}$ is the number of nodes of a $k$-ary tree of depth $d$. Suppose given arguments $x_i \in [0, N]$. We write those in base $m = \frac{k^{p+1}-1}{k-1}$ as follows:

$$x_i = \sum_{d=0}^{p-1} \sum_{c=0}^{k^d-1} x_i(d, c) m^{k^{(d)}+c}.$$

As a quick sanity check this does have $k^{(p)}$ digits as $\sum_{d=0}^{p-1} \sum_{c=0}^{k^d-1} 1 = k^{(p)}$, and it's routine to check that $m^{k^{(d)}+c}$ does iterate through every $m^i$ for $i \in [0; k^{(p)}-1]$. As a matter of a fact $x_i(d, c)$ corresponds to the $c$-th digit at depth $d$ of the tree as illustrated in figure 9.

The definition of $F_{(p,k)}$ then simply generalizes the definition of $F(3, 2)$ given above.

**Definition 5.3** ($F_{(p,k)}$). For any $p, k$ we define the function $F_{(p,k)}$ as follows:

$$F_{(p,k)}(x_0, \dots, x_{k-1}) = v + \sum_{d=1}^{p-1} \sum_{i=0}^{k-1} \sum_{c=0}^{k^d-1} x_i(d-1, c) m^{i \cdot k^{(d-1)} + c},$$

where $v$ is a value different from all $x_i(d, c)$ (say the smallest one for a deterministic function).

Let us explain the formula: to construct $F_{(p,k)}(x_0, \dots, x_{k-1})$ one simply reads the nodes of figure 9 in a Breadth First Search (BFS) way and interprets the labels as digits in base $m$.

We first establish the following lemma. Consider the case of applying $F_{(p,k)}$ iteratively on one of its outputs. I.e. given an $x$, choose arbitrary values $y_1, \dots, y_{k-1}$ and compute $x_1 = F_{(p,k)}(x, y_1, \dots, y_{k-1})$ (or $F_{(p,k)}$ applied to any permutation of this tuple). Iterate this process $i$ times and consider the output $x_i$. The lemma shows that if $i < p$, then $x_i$ must be different from $x$.

**LEMMA 3.** Consider the strategy $F_{(p,k)}$ defined above. Given an element $x$, define the set of $i$-antecedents of $x$ inductively:

* the set $F_{(p,k)}^{(-1)}(x)$ of 1-antecedents of $x$ is defined as the set of $y$ such that there exists $0 \le j \le k-1$ and a tuple $(x_0, \dots, x_{k-1})$ such that $x_j = y$ and $F_{(p,k)}(x_0, \dots, x_{k-1}) = x$.

* the set $F_{(p,k)}^{(-i+1)}(x)$ of $i+1$-antecedents of $x$ is defined as the union

$$F_{(p,k)}^{(-i+1)}(x) = \bigcup_{y \in F_{(p,k)}^{(-1)}(x)} F_{(p,k)}^{(-i)}(y).$$

Then for all integers $1 < i \le p$, $x \notin F_{(p,k)}^{(-i)}(x)$.

**PROOF.** The proof mainly consists in establishing the following claim: if $y \in F_{(p,k)}^{(-i)}(y)$ for $1 < i \le p$, then $y \ne x \bmod m$. This is a direct consequence of the following claim.

**Claim.** If $y \in F_{(p,k)}^{(-i)}(x)$ for $i < p$, the value of $y \bmod m$ is equal to one of the digits of $x$ when written in base $m$.
*Proof.* We will denote by $a, b$ the numbers given to player 1, by $c, d$ the numbers given to player 2, and by $e, f$ the numbers given to player 3. The goal is to show that if each player applies the function $F_{(3,2)}$ then they always collectively win the game.

As in the definition above, we write $a = a_6a_5a_4a_3a_2a_1a_0$ the base 15 representation of $a$, $b = b_6b_5b_4b_3b_2b_1b_0$ the base 15 representation of $b$, etc.

If $F_{(3,2)}(a, b)$ is different from $c, d, e, f$, the players have won the game. Suppose now that we are in the case where $F_{(3,2)}(a, b) \in \{c, d, e, f\}$. Without loss of generality, we can suppose that $F_{(3,2)}(a, b) = c$. In particular: $c_0 \neq a_i$ for all $i \in [0, 6]$, $c_0 \neq b_i$ for all $i \in [0, 6]$ $c_2 = a_0$, $c_5 = a_1$, and $c_6 = a_2$. We now consider the result produced by player 2, that is $F_{(3,2)}(c, d)$. Once again, if this value is different from $a, b, e, f$ then the game is won. If this is not the case, there are two cases.

The first case is $F_{(3,2)}(c, d) \in \{a, b\}$. We now show that this is impossible. By definition, $F_{(3,2)}(c, d)$ is different modulo 15 from all $c_i$ ($i \in [0, 6]$), but $c_1$ is the remainder modulo 15 of $b$ and $c_2$ is the remainder modulo 15 of $a$. Hence the value of $F_{(3,2)}(c, d)$ modulo 15 is different from the values of $a, b$ modulo 15.

The second case is $F_{(3,2)}(c, d) \in \{e, f\}$. Without loss of generality, we suppose $F_{(3,2)}(c, d) = e$. We will now have to show that $F_{(3,2)}(c, d) \notin \{a, b, c, d\}$. Let us write $z = z_6z_5z_4z_3z_2z_1z_0$ the representation of $F_{(3,2)}(c, d)$ in base 15. By definition of $F_{(3,2)}$, $z_0 \neq e_i$ for all $i \in [0, 6]$. But since $F_{(3,2)}(c, d) = e$ and $F_{(3,2)}(a, b) = c$, one has the following properties: $e_1 = d_0$, $e_2 = c_0$, $e_5 = c_1 = b_0$, $e_6 = c_2 = a_0$. Thus $z_0$ is different from $a_0$, $b_0$, $c_0$, and $d_0$. This proves that $F_{(3,2)}(e, f) \neq a, b, c, d$, and therefore the game is won. $\square$

## 6.2 General strategy for (p,k)

We now expose the general strategy. The construction follows the (3, 2) case just described. In that case, the main insight of the strategy was to book-keep the remainders modulo $m$ of the potential antecedents up to depth 2. For general $(p, k)$, we will therefore keep track of the potential antecedents up to depth $p-1$. This means that for each of the $k$ arguments, we will need values modulo $m$ of the potential $1+k+k^2+k^3+\cdots+k^{p-1}$ antecedents. Since there are $k$ arguments, this means that we will be manipulating $k(1+k+k^2+k^3+\cdots+k^{p-1})$ values modulo $m$, and produce a fresh value. This implies that $m$ should be greater or equal to $1+k(1+k+k^2+k^3+\cdots+k^{p-1}) = \frac{k^{p+1}-1}{k-1}$.

Now, since we need to book-keep $1+k+k^2+k^3+\cdots+k^{p-1} = \frac{k^p-1}{k-1}$ antecedents, we will require that:

$$M \ge \left( \frac{k^{p+1}-1}{k-1} \right)^{\frac{k^p-1}{k-1}}.$$
This claim is established by a simple induction: the definition of $F_{(p,k)}$ was established exactly to possess this property.

A consequence of this claim is that no cycles of size $\le p$ exist, i.e. for $i \le p$, no sequence of antecedents $y_i, y_{i-1}, \dots, y_1, y_0$ of a given $x$ exists, where $y_{i+1} \in F_{(p,k)}^{(-1)}(y_i)$ such that $y_0 = x$. Suppose this is the case. Then each $y_m$ is an antecedent of $y_1$, namely a $i-1$ antecedent. By the previous claim (note that $i-1 < p$), $y_1$ contains the remainder $r$ modulo $m$ of $y_i$. But by definition of $F_{(p,k)}$, the remainder modulo $m$ of $x$ (which can be written $F_{(p,k)}(u_1, \dots, u_k)$ with some $u_k = y_1$) is different from any digits of $y_1$; it is therefore different from $r$, leading to a contradiction to the fact that $y_i = x$. $\square$

**THEOREM 16.** *The oblivious strategy defined by the function $F_{(p,k)}$ is winning.*

*PROOF.* The previous result (lemma 3) establishes that no cycle of size $\le p$ exist when considering the antecedents relation of $F_{(p,k)}$. More precisely, let us consider $i \le p$ sequences $s_j = (x_1^j, \dots, x_k^j)$ of tuples such that each $s_j$ ($j < i$) contains one element $x_{ui}^j$ such that $x_{ui}^j = F_{(p,k)}(s_i) \notin s_1$. If the function $F_{(p,k)}$ is used as a strategy by all the players in the game $(p, k)$, this translates as the fact that there cannot exist any cycle of length $i \le p$ between the inputs and outputs of different players. More formally: for any family of player inputs $A_i$, one defines a graph on $\{1, \dots, p\}$ with an edge from $j_1$ to $j_2$ if and only if $F_{(p,k)}(A_{j_1}) \in A_{j_2}$. Then lemma 3 shows that this graph never contains cycles of length $\le p$. By lemma 2, this is enough to establish that the strategy induced by $F_{(p,k)}$ is winning for the game $(p, k)$. $\square$

Based on this general strategy and previous bound computations at the beginning of section 5.2, one can establish the following result.

**THEOREM 17.** $\mathfrak{B}(p, k, 1) \le \left( \frac{k^{p+1}-1}{k-1} \right)^{\frac{k^p-1}{k-1}}$.

We will instead use the bound of corollary 1 which is easier to manipulate.

**COROLLARY 1.** For large values of $p$ and $k$, $\mathfrak{B}(p, k, 1) \le (k^p)^{k^p}$.

# 6 FORMAL DESCRIPTION AND ANALYSIS OF THE PROGRAMS

Here we describe and analyze formally the programs used to show $[f, \alpha T] \not\subseteq [f, T]$. The functions $f, \alpha$ and $T$ are all assumed to be VTC, increasing and going to infinity and reasonable as per definition 3.5 and 3.6.

In the following, we will often drop the arguments of the functions and write, for instance, $f$ instead of $f(n)$. We also suppose WLOG that $T(n) > n$ and $f < n$. Indeed, if $T(n) < n$, then it is not possible to write any string of length $n$ in the allocated time, and if $f \ge n$ then all inputs have a description of size bounded by $f$ and there are no gaps in the hierarchy. We also assume for simplicity that $2^{f+1}$ is divisible by $\alpha$.

For all $p, k, m, N \in \mathbb{N}$, we have a winning strategy $\mathfrak{S}^N(p, k, m) = (\sigma_i^N(p, k, m))_{i \in [p]}$ for the game $\mathfrak{G}^N(p, k, m)$, where $\sigma_i^N$ is the map defining the strategy for player $i$. The following definition of programs does not depend on the specific strategy considered, but it should be clear that their analysis will be dependent on this choice.

## 6.1 One try variant

We formally define the program which is intended to output a string in $[f, \alpha T](n)$ and not in $[f, T](n)$ with strategy $\mathfrak{S}^N(p, k, 1)$. We then proceed with the size and running time analyses.
We will here suppose that $M$ is minimal, i.e. the above inequality is in fact an equality. We introduce the notation $k^{(d)} = \frac{k^{d-1}}{k-1}$; by convention, we define $k^{(0)} = 0$. Suppose given arguments $x_i \in [0, M]$. We write those in base $m = \frac{k^{p+1}-1}{k-1}$ as follows:

$$x_i = \sum_{d=0}^{p-1} \sum_{c=0}^{k^{d}-1} x_i(d, c)m^{k^{(d)}+c}.$$

The definition of $F_{(p,k)}$ then simply generalises the definition of $F(3, 2)$ given above.

**Definition 6.2.** For any $p, k$ we define the function $F_{(p,k)}$ as follows:

$$F_{(p,k)}(x_0, \dots, x_{k-1}) = \mu + \sum_{d=1}^{p-1} \sum_{i=0}^{k-1} \sum_{c=0}^{k^{d-1}-1} x_i(d-1, c)m^{i \cdot k^{(d-1)} + c},$$

where $\mu$ is a value different from all $x_i(d, c)$ (say the smallest one for a deterministic function).

Following the proof of Theorem 14, one can establish that the strategy is winning, leading to the following result.

**Theorem 15.** $\mathfrak{B}(p, k, 1) \le \left(\frac{k^{p+1}-1}{k-1}\right)^{\frac{k^p-1}{k-1}}$.

**Corollary 1.** For large values of $p$ and $k$, $\mathfrak{B}(p, k, 1) \le (k^p)^{k^p}$.

# 7 Results

We now combine the program of section 5 and the general strategy described in section 6.2 for the game $\mathcal{G}^N(p, k, 1)$ with $N = (k^p)^{(k^p)}$. We obtain in this way the following result which improves on the result by Longpré that $\exists_{\infty} n[f, 2^f T](n) \not\subseteq [f, T](n)$.

**Theorem 16.** Let $T$ and $f$ be functions of $\mathbb{N} \mapsto \mathbb{N}$ in $\text{DTIME}(T(n))$ such that $T(n) \ge n$ and $f(n) = o(\log(n))$. Let $\alpha = \frac{f2^f}{\log n}$. Then:

$$\exists c \in \mathbb{R}, \exists_{\infty} n, [f, c\alpha T](n) \not\subseteq [f, T](n).$$

*Proof.* The proof consists of two parts. First, we analyze the bound $\mathfrak{B}(p, k)$ which will give us the restrictions on $f$ and $\alpha$. We will then check that there are programs implementing the general strategy and having the proper size and running time.

Let us recall that that we need $\mathcal{B}(p, k) = (k^p)^{(k^p)}$ to be bounded above by $2^n$. Here we have:
**Algorithm 1 Program $p(\langle\#n, i\rangle)$**

1: **Input:** $\langle \#n, i \rangle$ a string from $\{0, 1\}^*$ (encoding $\langle\rangle$ from definition 3.2) where:
   $\#n \in \{0, 1\}^*$ – the smallest program outputting $n$ in $2n$ steps or less
   $i \in \{0, 1\}^{f+1-\log(\alpha)}$ – the chunk number, ranging from 1 to $\frac{2^{f+1}}{\alpha}$

2: **Procedure:**

3: Run $\#n$ as a program and call $n$ its output

4: Compute $f(n)$, $T(n)$, and $\alpha(n)$

5: Create an empty list $l$ to store outees

6: **for** $j = 0$ to $\alpha - 1$ **do**

7: Simulate program number $(i - 1)\alpha + j$ for $T(n)$ simulation steps

8: **if** it outputs a value of size $n$ **then**

9: Add the output to list $l$

10: **end if**

11: **end for**

12: **Output:** Run the strategy $\sigma_i^N(\frac{2^f(n)}{\alpha(n)}, \alpha(n), 1)$ on $l$ (seen as a multiset) where $N = 2^n$, and output the answer.

**Size analysis.** We now analyze the size of $p(\#n, i)$:

* $\#n$ is of size $K^{2n}(n)$ (by definition);

* $i$ is an integer in $[1; 2^{f+1}/\alpha]$, hence it is of size $f + 1 - \log(\alpha)$.

* $\langle \#n, i \rangle$ is of size $K^{2n}(n) + f - \log(\alpha) + O(\log(K^{2n}(n)))$ from definition 3.2;

* the program $p$ is of size $O(1)$ if the strategy $\mathfrak{S}$ is describable in $O(1)$ bits (this is the case of the strategy of section 5.2).

Thus for large $n$, $p(\langle\#n, i\rangle)$ is of size less than $2K^{2n}(n) + f - \log(\alpha) + O(1)$. Since $\alpha$ is VTC and increasing and going to infinity we have that $\log(\alpha)$ is reasonable per theorem 40. Hence $2K^{2n}(n) + f - \log(\alpha) + O(1)$ is strictly less than $f(n)$ for infinitely many values of $n$.

**Running time analysis.** Steps 3 to 11 take $O(\alpha T)$ steps to compute. The running time of step 12 depends on the specific strategy $\mathfrak{S}^N(2^f/\alpha, \alpha)$ we choose to implement. Hopefully this running time can be kept in $O(\alpha T)$, we assume it for now.

**Correctness analysis.** Suppose that the strategy $\mathfrak{S}^N(\frac{2^f(n)}{\alpha(n)}, \alpha(n))$ used in the program is a winning strategy for the game $\mathfrak{G}^N(\frac{2^f(n)}{\alpha(n)}, \alpha(n))$. Let $\#n$ be a program outputting $n$. Then, by construction, there exists $i \in [1, 2^f/\alpha]$ such that Out($p(\langle \#n, i \rangle)$) is a string of size $n$ which is not the output of any program of size $f$ in less than $T$ steps.

**Conclusion** Size and running time analysis are meant to prove that Out($p(\langle\#n, i\rangle)$) is in $[f, \alpha T](n)$. Correctness analysis shows that for at least one $i$, Out($p(\langle\#n, i\rangle)$) is not in $[f, T](n)$. Thus showing $[f, T](n) \subsetneq [f, \alpha T](n)$.

## 6.2 Multiple-tries variant

The multiple tries setting is quite similar to the one try setting, except that we will have an additional input $j$ indicating which try is computed. We formally define the program which is intended to output a string in $[f, \alpha T](n)$ and not in $[f, T](n)$ when the strategy
• $p = 2^f / \alpha$

• $k = \alpha$

• $pk = 2^f$

• We need $(k^p)^{kp} \le 2^n$

We can then compute:

$$ (k^p)^{kp} \le 2^n \qquad \Leftrightarrow \qquad (1) $$

$$ k^p p \log(k) \le n \qquad \Leftrightarrow \qquad (2) $$

$$ \alpha^{2^f / \alpha} 2^f / \alpha \log(\alpha) \le n \qquad \Leftrightarrow \qquad (3) $$

$$ 2^f / \alpha \log \alpha + f - \log \alpha + \log \log \alpha \le \log n \qquad \Leftrightarrow \qquad (4) $$

This implies that $f(n)$ must be in $o(\log n)$. Under this assumption, taking any $\alpha \ge \frac{f2^f}{\log n}$ makes the inequality hold. We thus set $\alpha = \frac{f2^f}{\log n}$<fnref n="8" />. Note that $\alpha = o(2^f)$ which is necessary to improve on the result of Longpré.

Now, consider the programs $p(\#^T n, i)$ from section 5 implementing the one-try strategy from section 6.2, with $f = o(\log(n))$ and $\alpha = \frac{f2^f}{\log n}$. We recall that $i$ ranges in $[1; 2^f / \alpha]$ and that $\#^T n$ is the smallest program outputting $n$ in $T(n)$ steps. The infinite sequence of $(n_j)_{j \in \mathbb{N}}$ we consider are all the values of $n$ such that $K^{\#^T}(n) < \log \log n$ in ascending order. This is indeed an infinite sequence by Theorem 3. We now claim that:

1. $\forall j \in \mathbb{N}$, $p(\#^T n_j, i)$ is of size $\le f(n_j)$;

2. with a proper implementation of the strategy of section 4.5.2, $p(\#^T n_j, i)$ runs in $c\alpha T(n_j)$ for all $j \in \mathbb{N}$;

3. for all $j \in \mathbb{N}$, there exists $i \in [2^{f(n_j)} / \alpha(n_j)]$, such that no program of size $f(n_j)$ running for $T(n_j)$ steps outputs a string equal to the output of $p(\#^T n_j, i)$; moreover the output of $p(\#^T n_j, i)$ is of size $n_j$.

Once those 3 points are established, the theorem will be proven.

<footnote n="8">⁸Actually in all generality we should just take $\alpha = o(2^f)$, because when $f$ grows too slowly for instance $f = \log \log n$, $\alpha$ as defined here takes non sensical value. The “issue” is that we have to take a specific function $\alpha$ in order to perform size and running time analysis, so we picked one which worked for “most” $f = o(\log(n))$. For slower growing $f$ we could just adjust the $\alpha$.</footnote>
$\mathfrak{S}^N(p, k, m)$ is winning. In the following $g$ is a function such that $g$ and $\log g$ are VTC and reasonable, $g$ is thought of as slowly growing (take for instance $g = \log^*$)

<caption>**Algorithm 2 Program $p(E_2(#n)ij)$**</caption>

1. **Input:** $E_2(#n)ij$ A string from $\{0, 1\}^*$ where: $E_2$ from definition 3.1
   $\#n \in \{0, 1\}^*$ – the smallest program outputting $n$ in $2n$ steps or less
   $i \in \{0, 1\}^{f+1-\log(\alpha)}$ – the chunk number, ranging from 1 to $\frac{2^{f+1}}{\alpha}$
   $j \in \{0, 1\}^{\log(\alpha)-\log(g)}$ – the try's number, ranging in $[1; \alpha/g]$.

2. **Procedure:**

3. Retrieve `$\#n$` from $E_2(#n)ij$

4. Run `$\#n$` as a program and call $n$ its output

5. Compute $f(n)$, $T(n)$, and $\alpha(n)$

6. Retrieve $i$ and $j$ from $E_2(#n)ij$ (possible since we know $f(n)$ and $\alpha(n)$)

7. Create an empty list $l$ to store outees

8. **for** $k = 0$ to $\alpha - 1$ **do**

9. Simulate program number $(i - 1)\alpha + k$ for $T(n)$ simulation steps

10. **if** it output a value of size $n$ **then**

11. Add the output to list $l$

12. **end if**

13. **end for**

14. **Output:** Run the strategy $\sigma_i^N(\frac{2^{f(n)}}{\alpha(n)}, \alpha(n), j)$ on $l$ (seen as a multiset) where $N = 2^n$.

**Size analysis.** We analyze the size of $p(E_2(#n)ij)$:

* `$\#n$` is of size $K^{2n}(n)$ (by definition);

* $i$ is of size $f - \log(\alpha)$;

* $j$ is of size $\log(\alpha) - \log(g)$;

* $E_2(#n)ij$ is of size $\le 2K^{2n}(n) + f - \log \alpha + O(1)$;

* the program $p$ is of size $O(1)$.

As a consequence, $p(E_2(#n)ij)$ is of size less than $2K^{2n}(n) + f - \log(g) + O(1)$. By reasonability of $\log(g)$ this is $\le f(n)$ for infinitely many $n$.

**Running time and correctness.** The analysis is similar to the one try case.

# 7 RESULTS

We now combine the program of section 6 and the general strategy described in section 5.2 for the game $\mathcal{G}^N(p, k, 1)$ with $N = (k^p)^{(k^p)}$. We obtain in this way the following result which improves on the result by Longpré.

THEOREM 18 ($K^t$ HIERARCHY IN THE TM MODEL). We place ourselves in the TM model. Let $T$ and $f$ be VTC and increasing and going to infinity and reasonable functions of $N \mapsto N$ in $DTIME(T(n))$ such that $T(n) \ge n \log(n)$ and $f(n) = o(\log(n))$. Let $\alpha = \max(\frac{f^2 f}{\log n}, \sqrt{f})$. Then:

$$ \exists c \in \mathbb{R}, \exists_{\infty} n, [f, c\alpha T](n) \not\subseteq [f, T](n) $$

Or abusively:

$$ \exists_{\infty} n, [f, O(\alpha T)](n) \not\subseteq [f, T](n). $$
**Size of the program.** We first check that our program is of size less than $f(n_i)$ for all $n_i$.

It has the same structure as the program described in section 5 and the strategy of section 6.2 may be described in $c$ bits. Therefore the size of $p$ is

$$K^T(n) + f - \log(\alpha) + c = K^T(n) + \log(f) - \log \log n + c,$$

which is less than $f(n)$ for infinitely many values of $n$.

**Running time of the program.** We check that our program runs in time less than $c\alpha T(n)$ for all $n_i$. In particular this involves checking that one can implement the strategy of section 6.2 in time $O(\alpha T)$.

* Retrieving $n_j$ from $\#^T n_j$ is done in $T(n_j)$ for all $n_j$ by definition.

* computing $f(n_j)$, $T(n_j)$ is done in $cT(n_j)$ steps by supposition. One can check that it is also possible to compute $\alpha(n_j)$ in $cT(n_j)$ steps.

* Simulating the execution of the $i$-th chunk of size $\alpha$ of programs of size $f$ i.e. getting the $\alpha$ inputs for our strategy takes a time $\alpha T$ as explained in section 5.

* Lastly, we describe an efficient implementation of the strategy described in 6.2. First we must convert every input in base $m = k^p = o(n)$. Notice that the strategy works if we take base $m \leftarrow 2^{\lceil \log m \rceil}$, and converting a binary number to a base $2^k$ can be done "for free".

Computing our answer is then done in two steps. First, we compute all digits (in base $m$) of our answer except for the last one by looking at the digits of the inputs in base $m$. This takes time $O(\alpha n) = O(\alpha T)$ because $T > n$. Second, we compute the last digit of the output by keeping track of every digits of the $\alpha$ inputs in a table of size $m = o(n)$ (there are $m$ possible values for the last digit). This takes time $\alpha n$ which is $o(\alpha T)$. Thus the whole program is computed in time less than $O(\alpha T)$.

**Correctness.** We follow the same outline as in paragraph correctness of section 5. Call $e_{i,j}$ the output of $p(\#^T n_j, i)$. $e_{i,j}$ is an integer of $[N_j] = [2^{n_j}]$ by definition of program $p$, i.e. a bitstring of size $n_j$. We proved in section 6.2 that $\mathbb{G}^{N_j}(\frac{2^f}{\alpha}, \alpha, 1)$ is winning, by construction this entails that there exists an $i \in [2^f/\alpha]$ such that $e_{i,j}$ is not the output of any program of size $f$ running for $T$ steps.

□
$T(n)$ being greater than $n \log n$ comes from the running time of the strategy

PROOF. The proof consists of two parts. First, we analyze the bound $\mathfrak{B}(p, k)$ which will give us the restrictions on $f$ and $\alpha$. We will then check that there are programs implementing the general strategy and having the proper size and running time.

Let us recall that the outants are strings of $\{0, 1\}^n$ which we identify to integers of $[N]$, thus we need $N = \mathfrak{B}(p, k) = (k^p)^{(k^p)}$ to be bounded above by $2^n$. Here we have:

* $p = 2^{f+1}/\alpha$

* $k = \alpha$

* $pk = 2^{f+1}$

* We need $(k^p)^{k^p} \le 2^n$

We can then compute:

$$ (k^p)^{k^p} \le 2^n \quad \Leftrightarrow \quad k^p p \log(k) \le n \quad \Leftrightarrow \quad \alpha^{2^{f+1}/\alpha} 2^{f+1}/\alpha \log(\alpha) \le n \quad \Leftrightarrow \quad 2^{f+1}/\alpha \log \alpha + f + 1 - \log \alpha + \log \log \alpha \le \log n \quad \Leftrightarrow $$

This inequality may only be satisfied if $f(n) = o(\log n)$. Under this assumption, taking any $\alpha \ge \frac{f2^f}{\log n}$ makes the inequality hold. We actually set $\alpha = \max(\frac{f2^f}{\log n}, \sqrt{f})$. Note that $\alpha$ and $\log(\alpha)$ are VTC and increasing to infinity and thus reasonable by theorem 5. The $\max(\cdot, \sqrt{f})$ is necessary as we need $\alpha$ to be reasonable even when $f = o(\log \log(n))$, the square-root may be replaced by some other function. Note that $\alpha = o(2^f)$ which is necessary to improve on the result of Longpré.

Now, consider the programs $p(\langle \#n, i \rangle)$ from subsection 6.1, with $f = o(\log(n))$ and $\alpha = \frac{f2^f}{\log n}$. We recall that $i$ ranges in $[1; 2^{f+1}/\alpha]$ and that $\#n$ is the smallest program outputting $n$ in $2n$ steps. The infinite sequence of $(n_j)_{j \in \mathbb{N}}$ we consider are all the values of $n$ such that $3K^{2n}(n) < \log(\alpha(n))$ in ascending order. This is an infinite sequence by reasonability of $\log(\alpha)$ (one can check that $\alpha$ is VTC and increasing and going to infinity and apply theorem 40). We now claim that:

(1) **Size of the program** $\forall_{\infty}j, \forall i, p(\langle \#n_j, i \rangle)$ is of size $\le f(n_j)$.

(2) **Running time of the program** with a proper implementation of the strategy of section B.2.2, $p(\langle \#n_j, i \rangle)$ runs in $c\alpha T(n_j)$ for all $j \in \mathbb{N}$.

(3) **Correctness** for all $j \in \mathbb{N}$, there exists $i \in [2^{f(n_j)}/\alpha(n_j)]$, such that no program of size $f(n_j)$ running for $T(n_j)$ steps outputs a string equal to **Out**($p(\langle \#n_j, i \rangle)$); moreover **Out**($p(\langle \#n_j, i \rangle)$) is of size $n_j$.

Once those 3 points are established, it follows that $\forall j \in \mathbb{N}$, **Out**($p(\langle \#n_j, i \rangle)$) $\in [f, c\alpha T](n_j) \setminus [f, T](n_j)$, and thus $\exists_{\infty}n, [f, O(\alpha T)](n) \not\subseteq [f, T](n)$.

**Size of the program.** We first check that $\forall_{\infty}j, \forall i, p(\langle \#n_j, i \rangle)$ is of size less than $f(n_j)$. Our program has the same structure as the program described in section 6 and the strategy of section 5.2 may be described in $O(1)$ bits. Therefore the size of $p(\langle \#n_j, i \rangle)$ is less than

$$ 2K^{2n_j}(n_j) + f - \log(\alpha) + c $$

By definition of the $n_j$ this is less than $f(n_j)$ for all but finitely many $j$.
## 8 Additional details and musings for future work

We now sketch a promising way to reason about winning strategies for nov- elty games. This could be used either to construct new ones, or establish better lower bounds for $\mathfrak{B}(p, k, m)$. The idea is to study the smallest number of antecedents any element $y$ in the image of $f: \binom{[N]}{k} \to [N]$ may have.

**Notations 2.** Given a sequence $(x_i) \in \mathbb{N}^k$, an element $x \in \mathbb{N}$ and some $j \in [1; k]$, we will denote by $(\hat{x}_i^j(x))$ the sequence such that $\hat{x}_i^j(x) = x$ if $i = j$ and $\hat{x}_i^j(x) = x_i$ otherwise.

**Definition 8.1 (Antecedents).** Let $f$ be a function, $\binom{[N]}{k} \to [N]$. We define $\mathcal{A}_f(y)$ as the set

$$ \mathcal{A}_f(y) = \{x \mid \exists (x_i) \in [N]^k, \exists j \in [1; k], f(\hat{x}_1^j(x), \dots, \hat{x}_k^j(x)) = y\}. $$

The set $\mathcal{A}_f(y)$ contains all values of $x$ such that there is a way to complete $x$ with other numbers in order to produce $y$ by the function $f$. Said differently: $\mathcal{A}_f(y) = \bigcup_{B \in f^{-1}(y)} B$.

We naturally extend the definition to apply to sets of number. Let $B \subset [N]$, then $\mathcal{A}_f(B) = \bigcup_{y \in B} \mathcal{A}_f(y)$. Thus we can write $\mathcal{A}_f^i(B) = \mathcal{A}_f^{i-1}(\mathcal{A}_f(B))$.

**Definition 8.2 (Non self-hitting (NSH) functions).** Let $f$ be a function $\binom{[N]}{k} \to [N]$. We say that $f$ is non self-hitting if $\forall B \in \binom{[N]}{k}, f(B) \notin B$.

It is easy to prove that we need only consider strategies which are non self hitting.

**Theorem 17.** If there is a winning strategy for the game $\mathcal{G}(p, k, m)$, then there is a strategy with no self hitting functions winning for game $\mathcal{G}(p, k, m)$.

As a consequence, all considered functions from now on will be supposed to be non-self hitting.

**Theorem 18 (Equivalence theorem for (2, k)).** Let $f$ be an NSH function $\binom{[N]}{k} \to [N]$. Then there exists $g$ such that $(f, g)$ is a valid strategy for the game $\mathcal{G}(2, k, 1)$ if and only if

$$ \forall x_1, \dots, x_k \in [N]^k, \bigcup_{i=0}^{n} \mathcal{A}_f(x_i) \neq [N]. $$

*Proof.* For the right to left implication, it is clear that if the property is satisfied then there exists a function $g$ such that

$$ \forall x_1, \dots, x_k, g(\{x_1, \dots, x_k\}) \in [N] \setminus \bigcup_{i=0}^{n} \mathcal{A}_f(x_i). $$
**Running time of the program.** We check that our program runs in time less than $c\alpha T(n_j)$ for all $n_j$. In particular this involves checking that one can implement the strategy of section 5.2 in time $O(\alpha T)$.

* Retrieving $n_j$ from $\#n_j$ is done in $\le 2n_j \le 2T(n_j)$ steps for all $j$ by definition.

* Computing $f(n_j), T(n_j)$ is done in $\le T(n_j)$ steps by supposition on $f$ and $T$. One can check that it is also possible to compute $\alpha(n_j)$ in $O(T(n_j))$ steps.

* Simulating the execution of the $i$-th chunk of size $\alpha$ of programs of size $f$ i.e. getting the $\alpha$ inputs for our strategy takes time $O(\alpha T)$ as explained in section 6.

* Lastly, we describe an efficient implementation of the strategy described in 5.2. First we have $\alpha$ inputs written in base 2 which we must convert base $m \ge k^p = o(n)$. Notice that the strategy works if we take base $m = 2^{\lceil \log k^p \rceil}$, and converting a binary number to a base $2^m$ can be done "for free" by considering chunks of size $m$. Thus we set $m = 2^{\lceil \log k^p \rceil} \le 2k^p$

In the strategy we receive $\alpha$ inputs which are bitstrings of size $n$ that we view as numbers of $k^p$ digits written in base $m$. We call our inputs $x^1, \dots, x^\alpha$ and denote by $x_j^i$ the $j$-th digit of $x^i$ in base $m$. We call the output of our strategy $y$; $y$ written in base $m$ is of the form $y = x_{j_1}^{i_1} \dots x_{j_K}^{i_K} v$ where $x_{j_l}^{i_l}$ are digits of our inputs taken according to the strategy and $v$ is chosen to be different from all $x_j^i \forall i, j \in [k^p]$. We represent our inputs in figure 10.

To compute the digits $x_{j_l}^{i_l}$ we have to do a BFS on the tree described in figure 9. This can be done in $O(\alpha n \log(\alpha n)) = O(\alpha \log(n)) = O(\alpha T)$.

To compute $v$ we have to solve MISSING-STRING$_{log(m),\alpha m}$, using theorem 7 and the fact that $m \log m = O(n)$ this can be done in time $O(n\alpha(\log(m) + \log(\alpha))) \le O(n\alpha \log n) = O(\alpha T)$.

**Correctness.** This follows from the argument outlined in paragraph correctness of section 6.1, and by the fact that $\mathbb{S}^{2n_j}(\frac{2^{f(n_j)+1}}{\alpha(n_j)}, \alpha(n_j), 1)$ is winning. $\square$

Note several things about our result:

* In the proof the only part which makes our result $\exists_\infty$ instead of $\forall_\infty$ is that $f = o(\log(n))$ for all other $f$ the result would be $\forall_\infty$.

* When $f$ is not in $DTIME(T)$, the result may still stand with adjustments. For instance, we can indicate the value $f(n)$ to $p$ for a cost of $\log f(n)$ bits.

* Our results hold under oracles.

**THEOREM 19 (K^i HIERARCHY IN THE RAM MODEL).** Let $T$ and $f$ be increasing VTC functions going to infinity of $N \mapsto N$ in $DTIME(T(n))$ such that $T(n) \ge n$ and $f(n) = o(\log(n))$. Let $\alpha = \max(\frac{f^2f}{\log n}, \sqrt{f})$. Then:

$$ \exists c \in \mathbb{R}, \exists_\infty n, [f, c\alpha T](n) \not\subseteq [f, T](n) $$

Or abusively:

$$ \exists_\infty n, [f, O(\alpha T)](n) \not\subseteq [f, T](n). $$

**PROOF.** The proof is the same as in the TM case. The part which differs is checking that we can implement the strategy in time $O(n\alpha)$. This presents no significant issue. $\square$
To prove the converse implication, suppose there exists $x_1, \dots, x_k$ such that $\bigcup_{i=0}^n \mathcal{A}_f(x_i) = [N]$, and call $a = g(\{x_1, \dots, x_k\})$. We know $a$ belongs to $\bigcup_{i=0}^n \mathcal{A}_f(x_i)$ and we can w.l.o.g. that it belongs to $\mathcal{A}_f(x_1)$. Then there exists a set $B$ of size $k$ such that $a \in B$ and $f(B) = x_1$. Therefore, the strategy fails on $(B, \{x_1, \dots, x_k\})$, leading to a contradiction. $\square$

**Corollary 2.** Let $f$ be an NSH function $(\binom{[N]}{k}) \to [N]$. If

$$ \forall x_1, \dots, x_k \in [N]^k, \bigcup_{i=0}^{n} |\mathcal{A}_f(x_i)| < \frac{N}{k}, $$

then there exists $g$ such that $(f, g)$ is a valid strategy for the game $\mathcal{G}(2, k, 1)$.

Following this line of thought, our idea to establish lower bounds for $\mathfrak{B}$ is to study a subclass of strategies on which it is easier to reason and then claim that any winning strategy can be reduced to a function of this subclass (in the case where we want to prove lower bounds).

We have just seen that only NSH functions need to be considered. If we restrict to oblivious strategies, the analysis should be easier. Lastly we can only consider strategies having many symmetries. The strategy we described for the game $\mathcal{G}(2, 2, 1)$ and for $\mathcal{G}(p, k, 1)$ are functions with lots of symmetries. One way to encapsulate this notion of symmetry was the notion of balanced functions, although it is clear that the notion may be too lenient. Indeed, the winning strategies we have found so far do much more than just being balanced. As such for future work we expect that an analysis of oblivious-NSH-balanced strategies could lead to progress, whether for establishing new strategies or lower bounds on $\mathfrak{B}$

**Definition 8.3 (Balanced functions).** A function $f: (\binom{[N]}{k}) \to [N]$ is balanced if

$$ \forall y \in [N], \left| |\mathcal{A}_f(y)| - \frac{1}{N} \binom{N}{k} \right| \le 1. $$

A strategy is said to be balanced if the functions for players are all balanced functions.

**Musings** Here are some additional thoughts and results we expect to hold, but have not yet formally established.

* When $f$ is not time-constructible in $T$, the result may still stand with adjustements. For instance, we can indicate the value $f(n)$ to $p$ for a cost of $\log f(n)$ bits.

* We believe we can show that $\mathfrak{B}(2, k) \ge 3k + 1$.

* Our results hold under oracles.
<figure><img src="image_9.png" /><figcaption>Fig. 10. Binary representation of our inputs in the strategy.</figcaption></figure>

# 8 ADDITIONAL LINKS AND MUSINGS FOR FUTURE WORK

## 8.1 Links with the time hierarchy theorem with advice

For completeness and potential future work, we show in this subsection what the time hierarchy (for Turing machine with advice) implies about a hierarchy for temporal Kolmogorov complexity. It turns out we get a hierarchy, but for a different notion of Kolmogorov complexity (see definition 8.5). We also show that the result of theorem 18 is indeed not easily obtainable from an analysis of the time hierarchy theorem. Lastly we mention recent advancements in the domain.

A function $g \in \{0,1\}^* \to \{0,1\}$ is said to be computable in time $T$ with advice of size $f$ if there is a Turing machine which can compute $g$ in time $O(T)$ when given an advice string of size $f(n)$ for inputs of size $n$ (the advice is the same for every string $x$). We define complexity classes with advice in the following standard way.

**Definition 8.1 (DTIME($T$)/$f$).** Let $T, f \in \mathbb{N} \mapsto \mathbb{N}$, a function $g: \{0,1\}^* \to \{0,1\}$ is in $DTIME(T)/f$ if there exists a TM $M$ such that:

$$ \exists c \in \mathbb{N}, \forall n, \exists a \in \{0,1\}^{f(n)}, \forall x \in \{0,1\}^n, M(x, a) = g(x) \text{ in } cT(n) \text{ steps or fewer} $$

By folklore results we have time hierarchy theorems for complexity classes with small amounts of advice.

**THEOREM 20 (TIME HIERARCHY THEOREM FOR COMPLEXITY CLASSES WITH ADVICE [22]).** Let $T: \mathbb{N} \mapsto \mathbb{N}$ be a time computable function such that $T(n) \ge n$ and $\alpha: \mathbb{N} \mapsto \mathbb{N}$ be an increasing function computable in $DTIME(T(n))$ such that $\alpha(n) \stackrel{\infty}{\to} \infty$ and $\alpha$ is VTC then: $DTIME(\alpha T \log T) \not\subseteq DTIME(T)/n$

**PROOF.** Let $M$ be the TM defined as such : For all $n \in \mathbb{N}$ and all inputs $x \in \{0,1\}^n$, $M$ simulate the advice-taking TM $N \stackrel{\text{def}}{=} M_{|x|}$ on input $x$ and advice $x$ for $\alpha T(n)$ steps ; if there was any output $M$ reverses it, otherwise $M$ outputs 1. This simulation can be done in $c_N \alpha T \log T$ where $c$ only depends on the TM being simulated. Thus $M \in DTIME(\alpha T \log T)$.
• We believe theorem 2 can be formulated in the case of the game $\mathcal{G}(p, k, 1)$ as follows. Let $f$ be an NSH function $(^{[N]}_k) \to [N]$. If

$$ \forall x_1, \dots, x_k \in [N]^k, \bigcup_{i=0}^{n} |\mathcal{A}_f(x_i)| < \frac{N}{k^p}, $$

then there are functions $g_1, \dots, g_{p-1}$, such that $\mathcal{S} = (g_1, \dots, g_{p-1}, f)$ is a winning strategy.

• We believe the best upper bound for $\mathfrak{B}(p, k, 1)$ is of the order $k^p$.

• It should be methodically checked if the technique of parallel diagonalization with advice can lead to class separation in complexity theory

## References

[1] Atif Abueida, James Lefevre, and Mary Waterhouse. Equitable edge colored steiner triple systems. *The Australasian Journal of Combinatorics* [electronic only], 50, 06 2011.

[2] N. G. Bate. Complete graphs without polychromatic circuits. *Discret. Math.*, 46(1):1–8, 1983.

[3] Lijie Chen, Zhenjian Lu, Igor C. Oliveira, Hanlin Ren, and Rahul Santhanam. Polynomial-time pseudodeterministic construction of primes. In *64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023*, pages 1261–1270. IEEE, 2023.

[4] Shuichi Hirahara. Non-black-box worst-case to average-case reductions within np. In *2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)*, pages 247–258, 2018.

[5] Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, and Igor C. Oliveira. A duality between one-way functions and average-case symmetry of information. In Barna Saha and Rocco A. Servedio, editors, *Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023*, pages 1039–1050. ACM, 2023.

[6] Ming Li and Paul M. B. Vitányi. *An Introduction to Kolmogorov Complexity and Its Applications, 4th Edition*. Texts in Computer Science. Springer, 2019.

[7] Yanyi Liu and Rafael Pass. On one-way functions and kolmogorov complexity, 2020.
Consider TM $N \in \text{DTIME}(T)/n$ with advice sequence $(a_n)_{n \in \mathbb{N}}$, note that $a_n$ is a string of size $n$. We have that on all input $N$ can be computed in exactly less than $dT$ steps for a specific $d$. Consider $n$ an integer such that $n$ (in binary) is a representation of $N$ and $c_N T \alpha \log T(n) > dT(n)$. Such $n$ do exist. Now consider $x = a_n$, we have that $M(x) = M(a_n) = \neg M_{|x|}(x, x) = \neg N(a_n, a_n)$. Thus $M \neq N$ for all $N \in \text{DTIME}(T)/n$. $\square$

In order to relate these notions to $K^t$ complexity we introduce the following.

**Definition 8.2** (Truth table of a function $tt(f)$). Let $f: \{0,1\}^n \mapsto \{0,1\}$, we define $tt(f)$ as the string of size $2^n$ being equal to the truth table of $f$. Formally

$$ \forall i \in [0; 2^n - 1], tt(f)_i = f(i) $$

where $i$ is interpreted as its binary representation over $n$ bits in $f(i)$.

**Definition 8.3** ($f_n$). Given a function $f \in \{0,1\}^* \mapsto \{0,1\}$, we define $f_n$ as the function $f$ restricted to $\{0,1\}^n$

Next we defined an alternate definition of Kolmogorov complexity. We relate it to the usual notion in lemma 4.

**Definition 8.4** ($Kb^t$ Bit-wise temporal Kolmogorov complexity$^{11}$). Let $x \in \{0,1\}^*$ and $t \in \mathbb{N}$, we define $Kb^t$ as:

$$ Kb^t(x) \stackrel{\text{def}}{=} \min\{|p| \in \{0,1\}^* | \forall i \in [0, |x|-1], U(\langle p, i \rangle) = x_i \text{ in less than } t \text{ steps}\} $$

where $U(\langle p, i \rangle)$ is meant as program $p$ running on input $i$ as simulated by $U$ an efficient universal TM.

With this new notion of Kolmogorov complexity we can define its associated class.

**Definition 8.5** ($[f, T]_b$). Let $f, T$ be two functions of $\mathbb{N} \mapsto \mathbb{N}$ then we define

$$ [f, T]_b(n) \stackrel{\text{def}}{=} \{x \in \{0,1\}^n | Kb^{T(n)}(x) \leq f(n)\} $$

We may drop the $n$ sometimes and write $[f, T]_b$.

Note that contrary to $[f, T]$ it makes sense to consider functions $T < n$ for $[f, T]_b$. For instance $\forall n, 0^n \in [O(1), O(1)]_b$. We will still restrict ourselves to function $f \leq n$ however, for similar reasons to the case $[f, T]$.

Relating definition 8.5 and 3.4 note that we have the following inclusions.

**LEMMA 4** (COMPARISON BETWEEN THE TWO KOLMOGOROV CLASSES $[f, T]_b$ AND $[f, T]$). For all $T, f$ functions of $\mathbb{N} \mapsto \mathbb{N}$ computable in $\text{DTIME}(T)$ we have:

$$ \forall n \in \mathbb{N}, [f, T]_b(n) \subset [f + 2K^{T(n)}(n) + O(1), O(nT)](n) $$

and

$$ \forall n \in \mathbb{N}, [f, T](n) \subset [f + O(1), T + n]_b(n) $$

With the precision that the "big $O(\cdot)$" mean that there exists a constant such that this is true.

<footnote n="11">¹¹This may have another name in the literature.</footnote>
[8] Luc Longpré. *Resource Bounded Kolmogorov Complexity, A Link between Computational Complexity & Information Theory*. PhD thesis, Cornell University, USA, 1986.

[9] Zhenjian Lu and Igor C. Oliveira. Theory and applications of probabilistic kolmogorov complexity. *Bull. EATCS*, 137, 2022.
PROOF. $[f, T](n) \subset [f + O(1), T + n]_b(n)$ : If $x$ can be printed in time $T$ by a program of size $f$, then so can a singular bit of $x$ (with some minor time and program adjustments).

$[f, T]_b(n) \subset [f + 2K^{T(n)}(n) + O(1), O(nT)](n)$ : Take $x \in [T, f]_b(n)$, there is by definition a program $p$ of size $f$ which given an index prints the corresponding bit of $x$ in time $T$ (through the simulation of a universal TM). Consider program $p'$ which takes as input a representation of $n$ decodable in $T(n)$ steps, and then runs $p$ for every bit $i \in [0; n - 1]$ to retrieve $x$. This takes time $O(nT)$ and program $p'$ is of size less than $f + 2K^{T(n)}(n) + O(1)$ (the factor 2 takes care of tuples encoding). $\square$

We can now give an alternative definition of $\text{DTIME}(T)/f$ which relates it to $\text{Kb}$.

LEMMA 5 (ALTERNATE DEFINITION OF $\text{DTIME}(T)/f$). Let $f, T$ two functions of $N \mapsto N$, let

$$A \stackrel{\text{def}}{=} \bigcup_{c \in \mathbb{N}} \text{DTIME}(T)/(f+c)$$

and

$$B \stackrel{\text{def}}{=} \{g : \{0,1\}^* \mapsto \{0,1\} \mid \exists c \in \mathbb{N}, \forall n \in \mathbb{N}, \text{Kb}^{cT(n)}(tt(g_n)) \le f(n) + c\}$$

then

$$A = B.$$

PROOF.

$$A \subset B$$

Let $g \in \text{DTIME}(T)/f$ then it is computed by a Turing machine $M \in \text{DTIME}(T(n))$ and with advice bits sequence $\alpha_n$ such that $\forall n, \alpha_n \le f(n) + c$ thus we have $|\langle M, \alpha_n \rangle| \le O(1) + f(n)$ and $M$ runs in time less than $cT(n)$. Ergo for a certain $c, \text{Kb}^{cT(n)}(tt(g_n)) \le f(n) + c$.

$$B \subset A$$

Let $g \in B$, consider $\alpha_n$ the program of size $\le f(n) + c$ which computes $g_n$ in $cT(n)$ steps or less, i.e. $\forall i \in \{0,1\}^n, \alpha(i) = tt(g_n)_i$. The result follows immediately. $\square$

Thus a function of $g \in \text{DTIME}(T)/f + O(1)$ can be seen as a sequence of function $(g_n : \{0,1\}^n \mapsto \{0,1\})_{n \in \mathbb{N}}$ which verify $\exists c \in \mathbb{N}, \forall n \in \mathbb{N}, \text{Kb}^{cT(n)}(tt(g_n)) \le f(n) + c$.

THEOREM 21 (HIERARCHY FOR $\text{Kb}^t$). Let $f, T$ two functions from $N \mapsto N$ such that $f(n) = o(\log(n))$ and $\alpha$ a VTC function growing to infinity, then

$$\exists c \in \mathbb{N}, \exists \infty n, [c, c\alpha T \log T]_b(n) \not\subset [f, T]_b(n)$$

PROOF. Let $T$ be a time computable function, and $\alpha$ a VTC function growing to infinity, then by theorem 20 there exists a function $g \in \text{DTIME}(\alpha T \log T)$ and $g \notin \text{DTIME}(T)/n$.

* $g \in \text{DTIME}(\alpha T \log T)$ entails by lemma 5

$$\exists d, \forall n, \text{Kb}^{d\alpha T \log T(n)}(tt(g_n)) \le d$$

2$^n$ is the size of $tt(g_n)$

$$\Rightarrow \exists d, \forall n, tt(g_n) \in [d, d\alpha T \log T(n)]_b(2^n)$$

In the rest of the proof we fix $d$ a witness to property $(*)$.
• $g \notin \text{DTIME}(T)/n$ entails

$$ \forall c, g \notin \text{DTIME}(T(n))/o(n) + c $$

$$ \begin{array}{rcl} & \boxed{\text{by lemma 5}} & \\ \Rightarrow & \forall c, \exists_{\infty} n, Kb^{cT(n)}(tt(g_n)) > o(n) + c. & \\ & \Rightarrow \forall c, \exists_{\infty} n, tt(g_n) \notin [o(n) + c, cT(n)]_b(2^n) & \end{array} $$

Combining both results we get:

$$ \begin{array}{rcl} & \exists_{\infty} n, tt(g_n) \in [d, d\alpha T \log T(n)]_b(2^n) \setminus [o(n) + c, cT(n)]_b(2^n) & \\ & \boxed{\text{replacing } 2^n \text{ by } n} & \\ \Rightarrow & \exists_{\infty} n, [d, d(\alpha T \log(T)) \circ \log]_b(n) \notin [o(\log), T \circ \log]_b(n) & \\ & \boxed{\text{replacing } T \circ \log \text{ by } T} & \\ \Rightarrow & \exists_{\infty} n, [d, d(\alpha T \log(T))]_b(n) \notin [o(\log), T]_b(n) & \end{array} $$

Which proves the theorem.

□

**Time hierarchy theorem may not give bounds for a $K^t$ hierarchy.** Theorem 21, which is quite simple to prove, is to be compared with theorem 18. It would seem that by combining lemma 4 and theorem 21 we can get a hierarchy for regular Kolmogorov classes $[f, T]$ à la theorem 18 but that is not the case. The reason is that a $n$ time factor appears when writing $[T, f]_b \subset [2^n T, f + O(K^{2^n}(n))]$ and $n$ is bigger than $2^f$ when $f = o(\log)$ so we don't get any improvements when compared with Longpré's result. The reason that $f$ is $o(\log(n))$ stems from the fact that our THT theorem holds for advice of size $\le n$.

**Recent advancement in the time hierarchy theorem (THT) with advice** As mentioned section 1, in paper [24] the authors come up with better local algorithms for the MISSING-STRING problem (the problem we call MISSING-STRING in definition 3.7) and derive a better THT with advice. They also show various implications of the existence of better algorithms for the MISSING-STRING problem. Their approach seems very related to ours.

**Question 3.** How can we relate the analysis of games $G(p, k, n)$ to the analysis of the MISSING-STRING problem on circuits ? To that of the THT with advice ?

## 8.2 Results for $rK^t$ (random Kolmogorov complexity

We now briefly analyze establishing a hierarchy for random Kolmogorov time complexity, denoted in the literature by $rK^t$ and defined as follows :

$$ rK^t(x) \stackrel{\text{def}}{=} \min_{M \in \text{RTM}} \left\{ |M| \mid M(\epsilon) \text{ outputs } x \text{ in } t(|x|) \text{ steps with probability } \ge \frac{2}{3} \right\} $$

Let us define the associated sets $[f, T]_r(n) \stackrel{\text{def}}{=} \{x \in \{0, 1\}^n; rK^T(x) < f\}$. It turns out that even showing an equivalent of Longpré's result, namely $[f, 2^f T]_r > [f, T]_r$ seems hard, for the same reason that establishing a time hierarchy for BPP is hard. We mention that hierarchy theorems have been established for BPP with advice in [6, 9, 19], which may prove useful.
In the meanwhile we can establish the following naive result : $[f, 2^{f+T}T]_r > [f, T]_r$. We can establish it by considering a program $p$ which diagonalizes against all random programs of size $f$ running for $T$ steps by simulating them on all possible random choices (hence the factor $2^T$). We can adapt the technique of part 7 to show that $\exists_{\infty} n, [f, \alpha 2^T T]_r(n) > [f, T]_r(n)$ when $f = o(\log)$ and for some $\alpha = o(2^f)$.

## 8.3 Establishing lower bounds for any strategy

We now sketch a promising way to reason about winning strategies for novelty games. This could be used either to construct new ones, or establish lower bounds for $\mathfrak{B}(p, k, m)$. The idea is to study the smallest number of antecedents any element $y$ in the image of $f: ([N])_k \to [N]$ may have. The hope is that by analyzing such restrictions we get lower bounds on $N$.

**Definition 8.6** ($(\hat{x}_i^j(x))$). Given a sequence $(x_i)_{i \in k} \in \mathbb{N}^k$, an element $x \in \mathbb{N}$ and some $j \in [1; k]$, we will denote by $(\hat{x}_i^j(x))$ the sequence such that $\hat{x}_i^j(x) = x$ if $i = j$ and $\hat{x}_i^j(x) = x_i$ otherwise.

The following definition was introduced with different notations in section 5.2. We use this notation now as it is more fitting.

**Definition 8.7** (Antecedents of a function $\mathcal{A}_f(x)$). Let $f$ be a function, $([N])_k \to [N]$. We define $\mathcal{A}_f(y)$ as the set

$$ \mathcal{A}_f(y) = \{x \mid \exists (x_i) \in [N]^k, \exists j \in [1; k], f(\hat{x}_1^j(x), \dots, \hat{x}_k^j(x)) = y\}. $$

The set $\mathcal{A}_f(y)$ contains all values of $x$ such that there is a way to complete $x$ with other numbers in order to produce $y$ by the function $f$. Said differently: $\mathcal{A}_f(y) = \bigcup_{B \in f^{-1}(y)} B$.

We naturally extend the definition to apply to sets of number.

**Definition 8.8** ($\mathcal{A}_f^i(B)$). Let $B \subset [N]$, then $\mathcal{A}_f(B) = \bigcup_{y \in B} \mathcal{A}_f(y)$.

We define $\mathcal{A}_f^i(B) = \mathcal{A}_f(B)$ and for any $i \in \mathbb{N}^*$, $\mathcal{A}_f^i(B) = \mathcal{A}_f^{i-1}(\mathcal{A}_f(B))$.

If $B = \{x\}$ we abusively write $\mathcal{A}_f^i(x)$ instead of $\mathcal{A}_f^i(\{x\})$.

**Definition 8.9** (Non self-hitting (NSH) functions). Let $f$ be a function $([N])_k \to [N]$. We say that $f$ is non self-hitting if $\forall B \in ([N])_k, f(B) \notin B$.

It is easy to prove that we need only consider strategies which are non self hitting.

**THEOREM 22.** *If there is a winning strategy for the game $\mathcal{G}(p, k, m)$, then there is a strategy with no self hitting functions winning for game $\mathcal{G}(p, k, m)$.*

As a consequence, all considered functions from now on will be supposed to be non-self hitting.

**THEOREM 23 (EQUIVALENCE THEOREM FOR (2, k))**. Let $f$ be an NSH function $([N])_k \to [N]$, there exists $g$ such that $(f, g)$ is a valid strategy for the game $\mathcal{G}(2, k, 1)$ if and only if

$$ \forall x_1, \dots, x_k \in [N]^k, \bigcup_{i=0}^{n} \mathcal{A}_f(x_i) \neq [N]. $$

**PROOF.** For the right to left implication, it is clear that if the property is satisfied then there exists a function $g$ such that

$$ \forall x_1, \dots, x_k, g(\{x_1, \dots, x_k\}) \in [N] \setminus \bigcup_{i=0}^{n} \mathcal{A}_f(x_i). $$
To prove the converse implication, suppose there exists $x_1, \dots, x_k$ such that $\bigcup_{i=0}^n \mathcal{A}_f(x_i) = [N]$, and call $a = g(\{x_1, \dots, x_k\})$. We know $a$ belongs to $\bigcup_{i=0}^n \mathcal{A}_f(x_i)$ and we can WLOG suppose that it belongs to $\mathcal{A}_f(x_1)$. Then there exists a set $B$ of size $k$ such that $a \in B$ and $f(B) = x_1$. Therefore, the strategy fails on instance $(B, \{x_1, \dots, x_k\})$, leading to a contradiction. $\square$

**COROLLARY 2.** Let $f$ be an NSH function $(\binom{[N]}{k}) \to [N]$. If

$$ \forall x_1, \dots, x_k \in [N]^k, \bigcup_{i=0}^n |\mathcal{A}_f(x_i)| < \frac{N}{k}, $$

then there exists $g$ such that $(f,g)$ is a valid strategy for the game $\mathcal{G}(2, k, 1)$.

Following this line of thought, our idea to establish lower bounds for $\mathfrak{B}$ is to study a subclass of strategies on which it is easier to reason and then claim that any winning strategy can be reduced to a function of this subclass. To that end we introduce balanced function, a balanced function is a function whose every image has the same number of antecedents.

**Definition 8.10 (Balanced functions).** A function $f: (\binom{[N]}{k}) \to [N]$ is balanced if

$$ \forall y \in [N], \left| \mathcal{A}_f(y) - \frac{1}{N} \binom{N}{k} \right| \le 1. $$

A strategy is said to be balanced if the functions for players are all balanced functions.

The strategy we described for the game $\mathcal{G}(2, 2, 1)$ and for $\mathcal{G}(p, k, 1)$ are functions which on top of being NSH, oblivious and balanced have lots more symmetries. Thus we may have to consider additional symmetries to our functions in order to establish lower bounds efficiently. We leave the following questions for future work:

**Question 4.** (1) Can we reduce our analysis of general winning strategies to winning strategies with many symmetries ?

(2) For game $\mathcal{G}(p, k)$ and for a certain function $h$, can we get lower bounds for functions with many symmetries of the form

$$ \forall x_1, \dots, x_k \in [N]^k, \bigcup_{i=0}^n |\mathcal{A}_f^p(x_i)| < h(N, k, p) ? $$
REFERENCES

[1] A. Abueida, J. Lefevre, and M. Waterhouse. Equitable edge colored steiner triple systems. *The Australasian Journal of Combinatorics* [electronic only], 50, 06 2011.

[2] S. Arora and B. Barak. *Computational Complexity: A Modern Approach*. Cambridge University Press, 2006.

[3] N. G. Bate. Complete graphs without polychromatic circuits. *Discret. Math.*, 46(1):1–8, 1983.

[4] B. Brandt. On translations of quadratic residues. *Journal of the Minnesota Academy of Science*, 62:7–7, 1997.

[5] B. Brandt. Supplement to "on translations of quadratic residues". *Journal of the Minnesota Academy of Science*, 64:16–17, 1999.

[6] H. Buhrman, L. Fortnow, and R. Santhanam. Unconditional lower bounds against advice. volume 16, pages 195–209, 07 2009.

[7] L. Chen, Z. Lu, I. C. Oliveira, H. Ren, and R. Santhanam. Polynomial-time pseudodeterministic construction of primes. In *64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023*, Santa Cruz, CA, USA, November 6-9, 2023, pages 1261–1270. IEEE, 2023.

[8] P. Erdös. On a problem in graph theory. *The Mathematical Gazette*, 47(361):220–223, 1963.

[9] L. Fortnow and R. Santhanam. Hierarchy theorems for probabilistic polynomial time. In *45th Annual IEEE Symposium on Foundations of Computer Science*, pages 316–324, 2004.

[10] K. Gajulapalli, A. Golovnev, S. Nagargoje, and S. Saraogi. Range avoidance for constant-depth circuits: Hardness and algorithms, 2023.

[11] R. L. Graham and J. H. Spencer. A constructive solution to a tournament problem. *Canadian Mathematical Bulletin*, 14(1):45–48, 1971.

[12] S. Hirahara. Non-black-box worst-case to average-case reductions within np. In *2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)*, pages 247–258, 2018.

[13] S. Hirahara, R. Ilango, Z. Lu, M. Nanashima, and I. C. Oliveira. A duality between one-way functions and average-case symmetry of information. In B. Saha and R. A. Servedio, editors, *Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023*, Orlando, FL, USA, June 20-23, 2023, pages 1039–1050. ACM, 2023.

[14] S. Hirahara, V. Kabanets, Z. Lu, and I. C. Oliveira. Exact Search-To-Decision Reductions for Time-Bounded Kolmogorov Complexity. In R. Santhanam, editor, *39th Computational Complexity Conference (CCC 2024)*, volume 300 of *Leibniz International Proceedings in Informatics (LIPIcs)*, pages 29:1–29:56, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.

[15] M. Li and P. M. B. Vitányi. *An Introduction to Kolmogorov Complexity and Its Applications*, 4th Edition. Texts in Computer Science. Springer, 2019.

[16] Y. Liu and R. Pass. On one-way functions and kolmogorov complexity, 2020.

[17] L. Longpré. *Resource Bounded Kolmogorov Complexity, A Link between Computational Complexity & Information Theory*. PhD thesis, Cornell University, USA, 1986.

[18] Z. Lu and I. C. Oliveira. Theory and applications of probabilistic kolmogorov complexity. *Bull. EATCS*, 137, 2022.

[19] K. Pervyshev. Time hierarchies for computations with a bit of advice. *Electron. Colloquium Comput. Complex.*, TR05, 2005.

[20] R. Reischuk. *Einführung in die Komplexitätstheorie*. Leitfäden und Monographien der Informatik. Teubner, Stuttgart, 1990.

[21] H. Ren, R. Santhanam, and Z. Wang. On the range avoidance problem for circuits. In *2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)*, pages 640–650, 2022.

[22] R. Santhanam and R. Williams. On uniformity and circuit lower bounds. *computational complexity*, 23(2):177–205, 2014.

[23] N. Vyas and R. Williams. On Oracles and Algorithmic Methods for Proving Lower Bounds. In Y. Tauman Kalai, editor, *14th Innovations in Theoretical Computer Science Conference (ITCS 2023)*, volume 251 of *Leibniz International Proceedings in Informatics (LIPIcs)*, pages 99:1–99:26, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.

[24] N. Vyas and R. Williams. On oracles and algorithmic methods for proving lower bounds. In *14th Innovations in Theoretical Computer Science Conference (ITCS 2023)*. Schloss-Dagstuhl-Leibniz Zentrum für Informatik, 2023.
A OMITTED PROOFS

We present next the full proof of theorem 1

PROOF. We adapt slightly the proof of Longpré. The proof is made by diagonalization
like in the usual proof of the time hierarchy theorem [2]. Here follows a sketch of the proof

We will construct a program *p* (remember we conflate programs with their binary representation) which takes as input a representation of *n* ∈ N which is decodable in time 2*n* noted *#n*. I.e. *#n* ∈ {0, 1}* is a program which runs in 2*n* steps and outputs *n*. We intend *p* to be such that **Out**(*p*(*#n*)) ∉ [*f*, *T*](*n*) but **Out**(*p*(*#n*)) ∈ [*f*, 2*f* *T*](*n*). Here is what program *p*(*#n*) does :

(1) Compute the values n, f(n), T(n)

(2) Iterate over all programs of size $\le f(n)$ and simulates them for $T(n)$ simulation steps on the universal Turing machine $U$. These $2^{f+1}$ such programs are called $(h_i)_{i \in [0;2^n]}$ and the program stores the output $y_i$ of $h_i$ if there was any and if $|y_i| = n$. Notice that there are at most $2^{f+1}$ such $y_i$ (the $y_i$ are all the elements of $[f, T](n)$)

(3) Output a word in {0, 1}^n different from all y_i

**Correctness:** By construction **Out**(*p*(*#n*)) cannot be in [*f*, *T*](*n*).

**Running time analysis:** Let us analyze the running time of $p(#n)$ :

- step 1 runs in time $O(T(n))$

- step 2 in time $O(2^{f(n)}T(n))$

- step 3 in time $O(n2^{2f(n)}) = O(T(n)2^{2f(n)})$ by theorem 7.

So the total running time is $O(2^{2f(n)}T(n))$.

**Size analysis:** We have that $|p(#n)| \le |p| + \log(|p|) + |#n| \le K^{2T}(n) + O(1)$. Because $f \in \text{DTIME}(T)$ where $T > f$ we have by theorem 39 that $\exists_{\infty} n, |p(#n)| \le K^{2n}(n) + O(1) \le f(n)$.

If we know that $f \ge c \log(n)$ then $\forall_{\infty} |p(#_{2T}n)| \le K^{2n}(n) + O(1) \le \log(n) + O(1) \le f(n)$.

**Conclusion:** By correctness analysis $\forall n$, **Out**(*p*(*#n*)) cannot be in [*f*, *T*](*n*), by running time and size analysis $\exists_{\infty} n$, **Out**(*p*(*#n*)) ∈ [*f*, 2*2*^*T*](*n*). Thus $\exists_{\infty} n$, [*f*, 2*2*^*T*](*n*) > [*f*, *T*](*n*).

If additionally we have that $f = \omega(\log(n))$ then $\forall_{\infty} n$, [$f, 2^{2^f}T$]($n$) > [$f, T$]($n$).

□

B STRATEGIES FOR $\mathcal{G}(p, k)$ FOR SPECIFIC $p$ AND $k$

B.1 Resolution of $\mathcal{G}(2, 2)$ case

This partial solution was chronologically the first to be proposed, by Corentin Henriet during
informal exchanges. We choose to present it since the strategy is different from the ones
presented in the next sections and it provides better bounds than in the general case.

This strategy is oblivious. We will thus define the single map *s* used by both players. The strategy is winning as long as *N* ≥ 9, showing that ℬ(2, 2, 1) ≤ 9 (much better than the general bound obtained in section 6, which gives 216). In this specific case, we can also prove that ℬ(2, 2, 1) > 5 (to be compared to 4 – the general lower bound obtained in theorem 13).

**Definition B.1 (Strategy s).** We intuitively understand our inputs as being on a "clock" from 1 to *N*, i.e. the successor of *N* is 1. Let (x, y) be our inputs ordered such that the distance
between $x$ and $y$ is less than the distance from $y$ to $x$ when read in the clockwise direction.
If $y = x + 1$ or $y = x + 2$, then $s(x, y) = x - 2$, otherwise we define $s(x, y) = x + 1$.

**THEOREM 24.** $\mathfrak{B}(2, 2, 1) \le 9$.

*PROOF.* The proof consists in verifying that $s$ is a winning strategy. This is done by checking every possible scenario. $\square$

**THEOREM 25.** $\mathfrak{B}(2, 2, 1) > 5$.

*PROOF.* This is easily checked by pen and paper search. $\square$

While this strategy provides good bounds, we have not found a way to generalise it to more players or larger sets. The next section presents a general strategy for the 2-players case.

## B.2 Graph strategies

This line of reasoning, and the corresponding winning strategy for $\mathcal{G}(2, k, 1)$ was first obtained by Dmitriy Kunisky during informal exchanges.

We first define colored *undirected graphs*. These colored graphs have their *edges* colored with no restriction.

**Definition B.2 (Colored graphs).** Let $p \in \mathbb{N}$. A $p$-colored graph is a triple $(V, E, C)$ where $V$ is a set of vertices, $E \subseteq \{(x, y) \in V^2 \mid x \neq y\}$ is a set of edges, and $C: E \to [p]$ a coloring function mapping every edge to a color (an element of $[1; p]$).

The graph is said to be complete when $E = \{(x, y) \in V^2 \mid x \neq y\}$. We will moreover write $G_i = (V, E_i)$ the graph induced by selecting the edges of a given color $i$, i.e. $w \in E_i \Leftrightarrow w \in E \land C(w) = i$. Given $u, v \in V$, we write $u \sim v$ when $\{u; v\} \in E$; in this case we say that $u$ and $v$ are neighbors. We moreover write $u \stackrel{i}{\sim} v$ when $u \sim v$ and $C(\{u; v\}) = i$.

We will now define a property of colored graphs which will be used later to define a winning strategy.

**Definition B.3** ($(p, k)$-set property). Let $p, k \in \mathbb{N}$. A $p$-colored graph $G = (V, E, C)$ is said to have the $(p, k)$-set property if for every subset of vertex $A \subseteq V$ of size $k$ and every color $i \in [1; p]$, the vertices in $A$ have a mutual neighbor $v$ in $G_i$, i.e. such that for all $a \in A$, $a \stackrel{i}{\sim} v$.

We will now explain how the $(p, k)$-set property ensures that one can define a strategy for $p$ players and sets of size $k$ from a $p$-colored graph. The intuition is the following: each input will correspond to a vertex, each player will correspond to a color, and a player will use the $(p, k)$-set property instantiated on its color to produce an answer.

We now recall the notion of polychromatic cycle that will be useful to discuss winning strategies.

**Definition B.4 (Polychromatic cycles).** Let $p \in \mathbb{N}$ and $G = (V, E, C)$ be a $p$-colored graph. A cycle $c$ of $G$ is said to be polychromatic if no two edges of $c$ have the same color.

Note that a polychromatic cycle does not necessarily use all colors. The non-existence of polychromatic cycles will ensure that the strategy will be winning (i.e that no all player's answer are an input of another one). For the interested reader, graphs with no polychromatic cycles have been studied here [1, 3].

**Definition B.5 (Good graphs).** Let $p, k \in \mathbb{N}$, and let $G$ be a $p$-colored graph. We say that $G$ is $(p, k)$-good if it has the $(p, k)$-set property and has no polychromatic cycles.
We now formally describe the strategy induced by a (p, k)-good graph G = (V, E, C) with V = [1; N]. The map $s_i^G : ([N]) \to [N]$ defining the strategy of the i-th player is defined as $s_i^G(A) = y$ where y is any vertex (for instance, the smallest) such that $\forall x \in A, x \stackrel{i}{\sim} y$. Such a y always exists thanks to the (p, k)-set property. We can then establish that the absence of polychromatic cycles implies that this strategy is winning.

**THEOREM 26 (GOOD GRAPHS MAKE WINNING STRATEGIES).** Let $p, k \in \mathbb{N}$ and let G be a $p$-colored graph with $N$ vertices. If G is $(p, k)$-good, the strategy $\mathcal{G} = (s_i^G(A))_{i \in [1; p]}$ is winning for the game $G^N(p, k, 1)$.

**PROOF.** Suppose the strategy is not winning. Then there exists an instance $A_1, \dots, A_p$ of the game for which the strategy fails (here $A_i$ denotes the set of inputs of player $i$). Consider a graph $H$ where the vertices are players $P_1$ to $P_p$, with a directed edge from $P_i$ to $P_j$ if the answer of player $i$, i.e. $s_i^G(A_i)$, belongs to the set of inputs $A_j$ of player $j$. By lemma 2 there is a cycle in $H$.

One can then check that a cycle in $H$ implies the existence of a polychromatic cycle in $G$, leading to a contradiction. We show it for case ($p = 3, k = 2$), the general case being directly derived from it:

Call $P_1, P_2$ and $P_3$ the players, call $\{a, b\}, \{c, d\}, \{e, f\}$ their respective inputs. Suppose WLOG that in $H$ we have cycle $P_1 \to P_2 \to P_3 \to P_1$. We can assume WLOG that $s_1^G(\{a, b\}) = c$, $s_2^G(\{c, d\}) = e$, $s_3^G(\{e, f\}) = a$. By construction of the strategy this means that $a \stackrel{1}{\sim} c \stackrel{1}{\sim} b$, $c \stackrel{2}{\sim} e \stackrel{2}{\sim} d$, $e \stackrel{3}{\sim} a \stackrel{2}{\sim} f$. We spot the polychromatic cycle $a \stackrel{1}{\sim} c \stackrel{2}{\sim} e \stackrel{3}{\sim} a$, which is a contradiction. $\square$

The last step is now to show that (2, k)-good graphs exist. We will then discuss, in subsection B.2.2, the unlikely existence of (p, k)-good graphs for p > 2 and k ≥ 2.

### B.2.1 Graph strategies for (2, k).

**THEOREM 27 (EXISTENCE OF (2,k)-GOOD GRAPHS).** For any $k \in \mathbb{N}$, there exists a (2, k)-good graph.

**PROOF.** We will prove that there exists an undirected uncolored graph $G = ([N], E)$ such that for every $A \in (\binom{[N]}{k})$:

* $\exists a, \forall x \in A, x \sim a$;

* $\exists b, \forall x \in A, x \not\sim b$.

This is sufficient to prove the existence of a (2, k)-good graph by converting every edge to a 1-colored edge and adding a 2-colored edge for every pair of vertices $x \neq y$ such that $x \not\sim y$. Note that this graph has no polychromatic cycles of size 2 since two vertices cannot be simultaneously neighbors and non-neighbors.
We now prove the existence of such graphs using the probabilistic method. Let $G$ be an Erdős-Rényi graph with edge probability $\frac{1}{2}$ on the vertex set $[1; N]$. We have that :

$\mathbb{P}[G \text{ is not } k\text{-good}]$

$$ \leq \mathbb{P}[\text{some } i_1, \dots, i_k \in [N] \text{ have no mutual neighbor}] $$

$$ + \mathbb{P}[\text{some } i_1, \dots, i_k \in [N] \text{ have no mutual non-neighbor}] $$

by symmetry

$$ \leq 2 \cdot \mathbb{P}[\text{some } i_1, \dots, i_k \in [N] \text{ have no mutual neighbor}] $$

$$ \leq 2 \binom{N}{k} \mathbb{P}[1, \dots, k \text{ have no mutual neighbor}] $$

$$ \leq 2 \binom{N}{k} \left(1 - \frac{1}{2k}\right)^{N-k} $$

$$ \leq 2 \exp \left( k \log N - \frac{N-k}{2k} \right) \xrightarrow{N \to \infty} 0 $$

Thus for large enough $N$ there thus exist $(2, k)$-good graphs with $N$ vertex $\square$

We also get a bound on the size of $N$.

**COROLLARY 3.** $\mathfrak{B}(2, k) < 13k^3 2^k$

**PROOF.** Looking more closely at the proof of theorem 27 we notice that $2 \exp(k \log N - \frac{N-k}{2k})$ is less than 1 when $N \ge 13k^3 2^k$. $\square$

We note that the bound of section 5 gives a worse bound of $O(2^{2k^2 \log k})$.

**Size and running time of the graph strategy.** If we want to use a strategy based on graphs in the programs of section 6 to show $[f, \alpha T] \subsetneq [f, T]$, we need a succinct description of such graphs. Indeed, the program needs to be of size less than $f$. Note however that we have only demonstrated the existence of a $(2, k)$-good graph thanks to the probabilistic method. The best we can naively do is then to hardcode those graphs in the strategy. This would make the strategy really large in terms of bits (close to $N^2 = 2^{2n}$), but our programs can never be bigger than $f < n$ bits. Another approach is to let the programs find those graphs by itself: every program $p(\#^T, i)$ enumerates and tests graphs in ascending lexicographic order until it finds a good graph, and then use it for its strategy. While this strategy takes $O(1)$ bits to describe, it takes at least $2^n$ steps to run implying that one could only establish bounds for $T > 2^n$.

**Payley graphs** We now hint at a method of constructing $(2, k)$-good graphs without using probability theory. This notion is developed in section C. We briefly describe such a potential graph using the notion of pseudorandom *Paley graph* from number theory. A Paley graph is a graph $G$ on a prime number $p \equiv 1 \pmod 4$ of vertices. Vertices of $G$ are identified with integers modulo $p$, and there exists an edge $i \sim j$ if and only if $i - j$ is congruent to a square modulo $p$, i.e. if and only if $\exists k, i - j = k^2 \pmod p$. The condition $p \equiv 1 \pmod 4$ ensures that the relation $\sim$ is symmetric.

Finding a mutual neighbor of $x_1, \dots, x_k$ then amounts to solving the system of equations $\{y - x_i = z_i^2\}$ in variables $y, z_1, \dots, z_k$. One may check, using character sum estimates, that
many integers $y$ satisfying these equations exist, for any choice of $z_1, \dots, z_k$, as long as $p$ is sufficiently large.

**B.2.2** *Unlikely existence of undirected graph strategies for (p, k).* We now turn our attention to (p,k)-good graphs. Unfortunately, we have not been able to prove or disprove the existence of such graphs for $p > 2$. However, we can establish that their are no complete (p,k)-good graphs (note that the (2,k)-good graphs we came up with are complete).

**Definition B.6 (Complete graph).** A *p*-colored graph *G* is said to be complete if there is a (colored) edge between any two vertices.

**Definition B.7 (Connectivity for color i).** A *p*-colored graph *G* is said to be connected for color *i* if there is a *i*-colored path between any two vertices in *G*

**THEOREM 28** (([3]))). Let *G* be a complete *p*-colored graph. If *G* has no polychromatic cycles, then *G* is connected for at most 2 colors.

**THEOREM 29.** There are no complete $(p, k)$-good graphs for $p > 2$ and $k \ge 2$.

**PROOF.** Let $G = (V, E, C)$ be a complete $(p, k)$-good graph. Then for any color $i$ and any two vertices $u, v \in V$, there exists $w \in V$ such that $u \sim_i w$ and $v \sim_i w$. This implies that $u$ and $v$ are connected for every color. Whenever there are $p \ge 3$ colors, this contradicts Theorem 28. $\square$

Graph strategies provide, in the case $p = 2$, better bounds than the general strategy defined below. However it is unclear if $(p, k)$-good graphs exist.

**Question 5.** Do $(p, k)$-good graphs exist ?

**Salvaging graph strategies with directed colored graphs** Until now we have only looked at undirected graph, in section C we consider colored and *directed* graphs with the following properties:

* there exists no polychromatic cycles;

* $k$-to-$1$: for any color $i$ and for any set $v_1, \dots, v_k$ there exists a vertex $b$ such that $\forall j \in [1; k], v_j \xrightarrow{i} b$.

Such graphs can be used to define a winning strategy for the game $G(p, k, 1)$ similarly to the undirected case : player $i$ answers a common directed neighbor for color $i$ of its $k$-inputs using the second property. The fact that the strategy is winning follows from the first property (the proof follows that of theorem 26). The existence of such graphs is settled positively in section C, this in turns gives winning - non-oblivious strategies.

**Oblivious graph strategies** As a superfluous question we make the following remark : if we wanted to have oblivious strategies we could disregard colors, every player would then work with the same underlying graph. We precise the kind of graph we think of to devise oblivious strategies in the next question. Note that we do not know if such graphs exist.

**Question 6.** Let $p, k > 3$, does there finite directed graphs $G = (V, E)$ such that no cycles of length less than $p$ exist and for any set $i_1, \dots, i_k \in V$ there exists a vertex $b$ such that $\forall j \in [1; k], (i_j, b) \in E$ ?
# C WINNING STRATEGY FOR $G(p, k)$ USING GRAPH STRATEGIES

At the end of the section B.2, we mentioned two potential leads for producing graph strategies. The first is the use of Paley graphs, i.e. graphs defined from a prime number $p$ such that $p = 3 \mod 4$ and such that the set of vertices is $[0, 1, \dots, p-1]$ and with an edge $(i, j)$ if and only if $j - i$ is a square modulo $p$. As we will see, these graphs do provide concrete constructions of graph strategies for the games $(2, k)$. This is obtained by simply noticing the relationship between those game and an old problem in combinatorics: the existence of $k$-paradoxical tournaments.

The literature does not provide a generalisation to the $(p, k)$ games for $p > 2$ though. But we will show how to construct strategies for such games by using a second idea which was mentioned in section B.2, namely the possibility of considering coloured directed graphs, where each color provides a strategy for a different player.

## C.1 Winning strategies from directed colored graphs

We extend the definitions of section B.2 to directed graphs in a very straightforward fashion.

**Definition C.1 (Multi-edges-directed-colored graph).** A $p$ colored directed graph $G = (V, E, c)$ is given by a set of vertices $V$, a multi-set of edges $E$ (meaning there can be multiple edges between two vertices) and a function $c: E \mapsto [1; p]$ which gives the color of each edges

We consider multi-edged graphs as the theorem also hold with them. From now on all considered graphs are colored and directed unless specified otherwise.

**Definition C.2** ($(p, k)$-good colored graphs). A graph $G = (V, E, c)$ with $p$ colors is said to be $(p, k)$-good if:

* (non-cyclic property): there are no polychromatic (directed) cycles of length smaller or equal to $p$;

* (k-to-1 property): For all colors $i \in [1, p]$, and any set of $k$ vertices $v_1, \dots, v_k$, there exists a vertex $w$ such that $\forall j \in [1; k], v_j \xrightarrow{i} w$.

We now formally describe the strategy induced by a $(p, k)$-good graph.

**Definition C.3 (Graph strategy).** Given $G = (V, E, c)$ a $(p, k)$-good graph. For all $i \in [1, p]$ the map $s_i^G : \binom{[N]}{k} \mapsto [N]$ defining the strategy of the $i$-th player is defined as $s_i^G(A) = y$ where $y$ is any vertex (for instance, the smallest) such that $\forall x \in A, x \xrightarrow{i} y$. Such a $y$ always exists because $G$ is $(p, k)$-good.

**THEOREM 30** ($(p, k)$-GOOD GRAPHS MAKE WINNING STRATEGIES). Let $p, k \in \mathbb{N}$ and let $G$ be a $p$-colored graph with $N$ vertices. If $G$ is $(p, k)$-good, the strategy $\mathcal{S} = (s_i^G(A))_{i \in [1; p]}$ is winning for the game $G^N(p, k, 1)$.

*PROOF.* This follows exactly the proof of theorem 26 □

## C.2 $k$-paradoxical tournaments

We will now relate the problem of finding efficient strategies to some known results in combinatorics.

We first consider the 2 players case, and arbitrary $k$. If we suppose that a pair of winning strategies for both players are equal and given by a directed graph, then this graph needs to satisfy two properties:

* the non-cyclic property: there are no cycles of length smaller or equal to 2;
• the $k$-to-1 property: given any set of $k$ vertices $v_1, \dots, v_k$, there exists a vertex $c$ such that $c$ is covered by all of the vertices $v_i$, i.e. for all $i$ there exists an edge $v_i \to c$.

Suppose given such a graph $G$, and consider the opposite graph $G^o$ defined on the same set of vertices but with reversed edges. Then this graph still satisfies the non-cyclic property: there are no loops (i.e. edges from a vertex $v$ to itself) and no cycles of length 2, i.e. if there exists an edge from $v$ to $w$ then there are no edges from $w$ to $v$. These kind of graphs are related to the notion of tournament studied in combinatorics, i.e. a graph with exactly one directed edge between two given vertices.

The $k$-to-1 property then translates as: for all set of $k$ vertices $v_1, \dots, v_k$, there exists a vertex $c$ such that $w$ dominates all the $v_i$. I.e. for all $i$ there exists an edge $c \to v_i$. This property is known in the literature about tournaments: a tournament satisfying this condition is called $k$-paradoxical.

It should then be clear that a $k$-paradoxical tournament defines a winning strategy (by taking the opposite graph). For the converse, note that while tournaments are defined as graphs with exactly one directed edge between two given vertices, we only ask that there is at most one. But this does not hinder the equivalence: if one has a winning strategy such that no edge exists between two vertices $v$ and $w$, then extending this graph by a vertex, say, from $v$ to $w$ gives a new graph also defining a winning strategy. Indeed, the $k$-to-1 property is preserved, and no loop or 2-cycle are created by adding this new edge. As a consequence, the opposite graph of a winning strategy can also be completed into a $k$-paradoxical tournament. This establishes the following proposition.

**PROPOSITION 31.** Let $G$ be a directed graph. It defines a winning strategy for the game (2,$k$) if and only if its opposite graph $G^o$ can be completed in a $k$-paradoxical tournament, that is one can add edges to $G^o$ in order to make it a $k$-paradoxical tournament.

A corollary of this is the following theorem.

**THEOREM 32.** *Writing ParadoxT($k$) the size (number of vertices) of the smallest $k$-paradoxical tournament, we have*

$$ \mathcal{B}(2, k, 1) \leq \text{ParadoxT}(k). $$

The question of determining ParadoxT($k$) has been studied by several authors. Erdös [8] showed by a probabilistic argument that ParadoxT($k$) < $O(k^22^k)$. More precisely, Erdös shows that if $k > 2$ and $n$ satisfies $\binom{n}{k}(1 - 2^{-k})^{n-k} < 1$, there exists a $k$-paradoxical tournament of size $n$.

**Concrete construction using Payley graphs** A concrete construction of a $k$-paradoxical tournaments was established by Graham and Spencer [11] using Paley graphs (or Paley tournaments).

**Definition C.4 (Paley graphs).** The Paley graph $P_p$ where $p$ is a prime such that $p = 3 \mod 4$ is the graph with vertices $\{0, 1, \dots, p - 1\}$ which has an edge from $v$ to $w$ whenever $w - v$ is a square modulo $p$, i.e. $\exists u, w - v = u^2 \mod p$.

Graham and Spencer showed that Payley graphs can be used to devise $k$-paradoxical tournament.

**THEOREM 33 ([11]).** Let $p, k \in \mathbb{N}$, if $p > k^2 2^{k-2}$ is a prime number such that $p = 3 \mod 4$, then the Paley graph $P_p$ is $k$-paradoxical.
Since the number $p$ needs to be a prime number such that $p = 3 \mod 4$, this gives the following upper bound (based on results from number theory).

**COROLLARY 4.** $\forall k \in \mathbb{N}$, $\text{ParadoxT}(k) < O(k^2 4^k)$

Though a larger upper bound, it has the merit of providing a concrete construction of the graph.

Lastly, from the perspective of number theory, Brandt [4, 5] investigated translations of quadratic residues and asked the exact question (though in other terms) of the existence of a Paley graph which is a $k$-paradoxical tournament. While he did not establish upper bounds, he provided an argument showing that $\text{ParadoxT}(k+1) \ge 2\text{ParadoxT}(k)+1$. This implies that$^{12}$ $\text{ParadoxT}(k) \ge \frac{3}{2}\cdot 2^k + 1$.

### C.3 Coloured graphs

So, a natural question is: what about the case of more than 3 players? To provide a strategy for three players, we would need a $k$-paradoxical tournament without cycles of length 3 (note that the definition of tournament already excludes length 2 and 1 cycles). More generally, a strategy for $p$ players would correspond to finding a $k$-paradoxical tournament without cycles of length lesser or equal to $p$. To our knowledge, the question of the existence of such tournaments has not been answered in the literature, and may very well not have a positive answer.

**A small lower bound for $G(3, 2)$.** But the story does not end here. The following construction proposed to the second author by Peter Selinger allows to build winning strategies for 3 players based on the optimal graph strategy for (2, 2) (given by the Paley graph $P_7$). The resulting strategy is not given by a directed graph, but a coloured directed graph (the colour representing the different players): in particular, the strategy is not oblivious (i.e. it is not the same strategy for all players). In that case, a winning strategy for $(p, k)$ is given by a coloured graph with $p$ colours such that each colour has the $k$-to-1 property and in which there are no polychromatic cycles as per definition C.3.

Suppose given the graph $G$ defining a winning strategy for (2, 2). Note that it can be checked that the Paley graph $P_7$ (Figure 11) is in fact optimal as an (uncolored, directed) graph strategy. This is done by a simple counting argument: if such a graph would exist with 6 vertices, it would have a $6 \times 6$ adjacency matrix $M$ with at most 15 non-zero coefficients (because we require $\text{Tr}(M) = \text{Tr}(M^2) = 0$ to avoid loops and length 2 cycles). One can then check by hand that the graph could not cover all size 3 subsets of 6 elements. For instance, the matrix could have five lines with exactly three non-zero elements: in that case it covers only 5 out of the 20 subsets of size 3 among the 6 elements.

Now consider the following graph $G^{(2,3)}$:

* the set of vertices is $V \times V$, where $V$ is the set of vertices of $G$;

* edges coloured 1 are given by $(a, b) \to (a', b')$ if and only if $a \to a'$ and $b \to b'$ are edges in $G$;

* edges coloured 2 are given by $(a, b) \to (a', b')$ if and only if $a \to a'$ and $b \to b'$ is an edge in $G$;

* edges coloured 3 are given by $(a, b) \to (a', b')$ if and only if either $a = a'$ and $b \neq b'$, or $a \neq a'$ and $b = b'$.

Let us show that this new graph has the required properties:

<footnote>$^{12}$Using that $\text{ParadoxT}(2) = 7$.</footnote>
<figure><img src="image_10.png" /><figcaption>Fig. 11. The Paley graph $P_7$ providing the optimal winning graph strategy for $G(2, 2, 1)$.</figcaption></figure>

• by assumption, the strategies defined by colours 1 and 2 satisfy the 2-to-1 property;

• the strategy defined by the edges coloured 3 satisfy the 2-to-1 property: given two pairs $(a, b)$ and $(a', b')$, the vertices $(a, b')$ and $(a', b)$ are covered by both elements;

• there are no polychromatic cycles of length 1: this is clear from the definitions;

• there are no polychromatic cycles of length 2:

– if there exists a path $(a, b) \xrightarrow{c} (a', b') \xrightarrow{c'} (a'', b'')$ with $c$ and $c'$ taken as colours in $\{1, 2\}$ then this would imply the existence of 2-cycles in the initial graph $G$, which is a contradiction;

– if there exists a path $(a, b) \xrightarrow{c} (a', b') \xrightarrow{c'} (a'', b'')$ with either $c \in \{1, 2\}$ and $c' = 3$, or $c = 3$ and $c' \in \{1, 2\}$, then this would imply the existence of a 1-cycle in $G$, since 3-coloured edges keep one of the components invariants;

• There are no polychromatic cycles of length 3: since 3-coloured edges leave on component invariant, such a cycle would imply the existence of a 2-cycle in the initial graph $G$.

As a consequence, we get the following uppoer bound for $\mathcal{B}(3, 2, 1)$.

**THEOREM 34.** *Since the graph $G^{(2,3)}$ gives a winning strategy, we have $\mathcal{B}(3, 2, 1) \le 49$.*

We note that this bound is much lower than the one given by the general strategy from section 5. Can the construction be generalised to larger values of $k$, and most importantly to larger values of $p$? We show in the next section that it is possible.

### C.4 General coloured graph strategies

To establish a general strategy based on coloured graphs, we will first establish two lemmas that will generalise the properties of the construction we just explained to go from a two player strategy to a three players strategy. The first lemma is quite natural. It shows that if $G$ is a directed graph with the $k$-to-1 property, then the product graph $G \times G \times \cdots \times G$ also has the $k$-to-1 property. This easily shows that if a coloured graph has the $k$-to-1 property, then the coloured product graph $G \times G \times \cdots \times G$ also has the $k$-to-1 property: when restricting the product graph to a colour $i$, we recover the product graph of $G$ restricted to the colour $i$.

**LEMMA 6 (THE $k$-TO-1 PROPERTY IS STABLE UNDER GRAPH-PRODUCT OPERATIONS).**
Let $G = (V, E)$ be a graph with the $k$-to-1 property, define the product graph $G' = (V^k, E')$ where $(x_1, \dots, x_k), (y_1, \dots, y_k) \in E'$ $iif \forall j \le k, (x_j, y_j) \in E$. We have that $G'$ verifies the $k$-to-1 property.

**PROOF.** Let $(x_i^1, \dots, x_i^k)_{1 \le i \le k}$ be a family of $k$ vertices of $G'$, the superscript $j$ denotes the $j$-th coordinate and the subscript $i$ the vertex number $i$. We will show that there exist