Consider the *arithmetic progression game*, a two-player game of
perfect information, in which the players take turns playing
natural numbers, or finite sets of natural numbers, all distinct,
and the first player wins if there is a sufficiently long
arithmetic progression amongst her numbers. This question grows out
of Haoran Chen's question, A game on the
integers, and my answer
there.

We have a natural parameterized family of such games, depending on the number of integers each player is allowed to play on each move and the desired length of the winning arithmetic progression.

Specifically, for positive-valued functions $f,g$ on the natural numbers and natural number $n$, let $G(f,g,n)$ be the game in which

- Player A is allowed to play $f(i)$ many numbers on move $i$.
- Player B is allowed to play $g(i)$ many numbers on move $i$.
- Player A wins if she can form an arithmetic progression of length $n$ using her numbers.

All the integers played must be distinct.

Generalizing, let $G(f,g,\omega)$ be the game where player A aims in infinite play to create an infinite arithmetic progression in her set, and let $G(f,g,{<}\omega)$ be the game in which she wins by creating a set with arbitrarily large finite arithmetic progressions.

The original game at the other question was $G(1,k,5)$, with $k$ constant.

It is not difficult to see that all the games $G(f,g,n)$ are determined, meaning that one of the players has a winning strategy. After all, for finite $n$ the game $G(f,g,n)$ is an open game and therefore determined; and the infinitary games $G(f,g,\omega)$ and $G(f,g,<\omega)$ have winning conditions of complexity $\Sigma^0_2$ and $\Pi^0_2$, respectively, and all such games are determined because they are very low in the Borel hierarchy.

In my answer at the other question, I had made several observations.

Player A wins the game $G(1,k,n)$, where player A plays one number on each move and player B plays at most a constant $k$ many numbers. The winning strategy for A is simply to play the smallest available number, which will ensure that set A has positive density, with proportion $1/(k+1)$ in any initial segment, and all such sets with positive density contain arbitrarily long arithmetic progressions by Szemerédi's theorem.

Thus, actually, player A wins $G(f,k,<\omega)$ for any $f$ and any $k$, and all with the same strategy.

A generalization of this argument adapts to show that if $g=O(f)$, then player A wins $G(f,g,n)$ and indeed $G(f,g,<\omega)$, since this hypothesis ensures that she can play a set with positive density, which will therefore have arbitrarily long finite arithmetic progressions.

Meanwhile, a diagonal argument shows that player B wins $G(f,1,\omega)$ for any $f$, the game where player A is aiming to produce an infinite arithmetic progression, since player B can block the $n^{th}$ progression with a single number at step $n$.

Thus, player B also wins $G(f,g,\omega)$ for any functions $f$ and $g$.

Meanwhile, player B also wins $G(1,<\omega,3)$, since at each move player B can play all the numbers up to double the largest current number. This will prevent A from making three numbers in arithmetic progression.

Indeed, a more refined version of this argument shows that player B wins $G(1,i-1,3)$, using the function $g(i)=i-1$, since at move $i$, player A has added one new number, which creates $i-1$ pairs with earlier numbers, and player B can block each of those pairs from continuing to an arithmetic progression of length $3$ by playing $i-1$ many blocking moves.

I have a number of questions.

**Question 1.** How quickly can player A win the game $G(1,k,n)$,
where $k$ is constant? Is the
always-play-the-smallest-available-number strategy in any sense
close to (or far from) optimal?

**Question 2.** Does the game $G(1,k,n)$ have finite game value?
That is, can we bound the length of play in advance, where the
bound depends only on $k$ and $n$ and not on the particular moves
of player B?

I presume the answer is yes, but note that not every open game has a finite game value.

**Question 3.** For which functions $g$ does player A win
$G(1,g,n)$?

Above I argued that player A wins $G(1,g,3)$ for constant $g$, and player B wins for $g(i)=i-1$. For $n=3$, that bound seems likely close to optimal, since if player B ever fails to block a number, then player A can win. But of course, perhaps some of the numbers to be blocked had already been blocked at earlier stages of play. So the answer seems to be somewhere between the constant functions and the predecessor function.

**Question 4.** Can one show that every unbounded function $g$
enables player B to win $G(1,g,n)$ for some sufficiently large $n$?

**Question 5.** How much of the analysis carries over to the
corresponding *geometric progression* games? That is, the games
where player A aims to create geometric integer progressions.

I don't know if there is a geometric progression analogue of Szemerédi's theorem, but meanwhile, some of the other arguments do generalize.