pith. sign in

arxiv: 2605.05455 · v3 · pith:FCS5YOBVnew · submitted 2026-05-06 · 🧮 math.CO

Thresholds for Tic-Tac-Toe on Finite Affine Spaces

Luca Bastioni , Alessandro Giannoni , Javier Lobillo-Olmedo This is my paper

Pith reviewed 2026-05-25 06:24 UTC · model grok-4.3

classification 🧮 math.CO
keywords affine tic-tac-toefinite affine spacespositional gamesstrategy stealingmaker-breaker gamesramsey theorythresholdsblocking sets
0
0 comments X

The pith

The (m,n)_q affine Tic-Tac-Toe game has a finite threshold T(n,q) separating draws from first-player wins.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper defines an affine generalization of Tic-Tac-Toe on the points of the finite vector space F_q^m, where a player wins by claiming every point of some n-dimensional affine subspace. It proves that second-player wins cannot occur, by viewing occupied points as blocking sets and invoking strategy stealing. Because the first-player win property is monotone in the ambient dimension m, the outcome is governed by a single threshold T(n,q): draws below it and first-player wins at or above it. The authors establish that T(n,q) is finite for every fixed n and q by appealing to the Graham-Leeb-Rothschild affine Ramsey theorem, and they supply concrete upper and lower bounds in several cases, including an exponential upper bound when q equals 2.

Core claim

Using strategy stealing and a blocking-set interpretation, we show that every (m,n)_q-game is either a first-player win or a draw, and that the property of being a first-player win is monotone in m. This yields a threshold T(n,q): the game is a draw for m<T(n,q) and a first-player win for m≥T(n,q). We prove that this threshold is finite by applying the affine/vector-space Ramsey theorem of Graham, Leeb and Rothschild, and we obtain general lower bounds from the Erdős-Selfridge criterion for Maker-Breaker games.

What carries the argument

The blocking-set interpretation of game positions, which enables strategy stealing to exclude second-player wins and establish monotonicity in m.

If this is right

  • The outcome of every (m,n)_q-game is completely determined by comparison of m with the single finite number T(n,q).
  • T(n,q) is finite for every fixed n and q.
  • T(n,2) is at most 2^{n+1}.
  • T(1,q) equals 2 when q is 2, 3 or 4, and T(2,2) equals 4.
  • Pairing strategies supply the lower bound T(n,q) at least n+2 whenever n is at least 2.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same monotonicity-plus-strategy-stealing pattern may produce thresholds in other positional games whose winning sets admit a blocking-set description.
  • The Fourier-analytic upper bound for the binary case indicates that analytic methods could tighten bounds when q is a prime power.
  • Exact computation of small T(n,q) values would allow direct comparison with known Ramsey numbers in affine spaces.
  • The Erdős-Selfridge lower-bound technique used here extends routinely to other Maker-Breaker games on affine geometries.

Load-bearing premise

The blocking-set interpretation of the game positions permits a direct application of strategy stealing to rule out second-player wins.

What would settle it

An explicit second-player winning strategy for some (m,n)_q-game with m greater than or equal to the claimed T(n,q), or a pair of dimensions m1 < m2 where the outcome for m2 is a draw while the outcome for m1 is a first-player win.

Figures

Figures reproduced from arXiv: 2605.05455 by Alessandro Giannoni, Javier Lobillo-Olmedo, Luca Bastioni.

Figure 2.1
Figure 2.1. Figure 2.1: Example of winning lines in (2, 1)3 passing through a given square While (2, 1)3 recovers and enriches the familiar childhood game, higher-dimensional instances quickly become more intriguing. Consider for instance the game (4, 2)3. The board consists of 34 = 81 points, which can be visualized as a 3 × 3 array of 3 × 3 boards, corresponding to the decomposition F 4 3 ∼= F 2 3 × F 2 3 . 5 [PITH_FULL_IMAG… view at source ↗
Figure 2.2
Figure 2.2. Figure 2.2: A winning game position for player Blue in (4 [PITH_FULL_IMAGE:figures/full_fig_p006_2_2.png] view at source ↗
read the original abstract

We introduce an affine version of Tic-Tac-Toe played on the finite affine space $\mathbb{F}_q^m$. Two players alternately claim points, and the first player to occupy all points of an affine subspace of dimension $n$ wins. We call this the $(m,n)_q$-game. For fixed $n$ and $q$, we study how the outcome depends on the ambient dimension $m$. Using strategy stealing and a blocking-set interpretation, we show that every $(m,n)_q$-game is either a first-player win or a draw, and that the property of being a first-player win is monotone in $m$. This yields a threshold $T(n,q)$: the game is a draw for $m<T(n,q)$ and a first-player win for $m\ge T(n,q)$. We prove that this threshold is finite by applying the affine/vector-space Ramsey theorem of Graham, Leeb and Rothschild, and we obtain general lower bounds from the Erd\H{o}s-Selfridge criterion for Maker-Breaker games. In the binary case, we give a direct Fourier-analytic argument, combined with an inductive lifting method, which shows that \[ T(n,2)\le 2^{n+1}. \] We also determine several small cases, including $T(1,q)=2$ for $q\in\{2,3,4\}$ and $T(2,2)=4$, and we prove geometric lower bounds from explicit pairing strategies, such as $T(n,q)\ge n+2$ for every $n\ge 2$. Our results place affine Tic-Tac-Toe at the interface of strong positional games, finite geometry and Ramsey theory for finite affine spaces.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper defines the (m,n)_q-game as Tic-Tac-Toe on the affine space F_q^m in which players alternately claim points and the first to fully occupy an n-dimensional affine subspace wins. It proves via strategy stealing and a blocking-set interpretation that every such game is a first-player win or a draw, establishes monotonicity of the first-player-win property in m (yielding a threshold T(n,q)), shows the threshold is finite by the Graham-Leeb-Rothschild theorem, derives general lower bounds from the Erdős-Selfridge criterion, proves the explicit upper bound T(n,2) ≤ 2^{n+1} by a Fourier-analytic argument plus inductive lifting, determines exact small values including T(1,q)=2 for q=2,3,4 and T(2,2)=4, and obtains geometric lower bounds T(n,q) ≥ n+2 for n≥2.

Significance. If the central arguments hold, the work cleanly places a natural family of strong positional games at the interface of Maker-Breaker theory, finite geometry, and affine Ramsey theory. The monotonicity argument and the resulting threshold existence are noteworthy; the concrete bound T(n,2)≤2^{n+1} together with the exact small-case determinations supply falsifiable predictions and explicit constants that strengthen the contribution.

minor comments (3)
  1. [§1] §1 (introduction): the blocking-set reformulation that enables strategy stealing is invoked without an explicit definition of the blocking set for an arbitrary position; a short paragraph or diagram would clarify the reduction.
  2. [§4] The inductive lifting step used to obtain T(n,2)≤2^{n+1} is described only at a high level in the abstract and §4; a one-sentence outline of the base case and the lifting map would improve readability.
  3. [Table 1] Table 1 (small cases): the entry for T(2,2)=4 should include a one-line justification or reference to the explicit pairing strategy that establishes the matching lower bound.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful summary of our manuscript, the positive assessment of its significance at the interface of positional games and affine Ramsey theory, and the recommendation of minor revision. No specific major comments or requested changes appear in the report.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The derivation relies on the standard strategy-stealing argument (applied via the blocking-set reformulation) together with the external Graham-Leeb-Rothschild theorem to establish finiteness of T(n,q). Monotonicity is shown by a direct embedding of an (m,n)_q-game into an (m+1,n)_q-game. Lower bounds invoke the external Erdős-Selfridge criterion and an explicit pairing strategy; the binary-case upper bound is obtained by a self-contained Fourier-analytic argument plus inductive lifting. No step reduces a claimed prediction to a fitted parameter, no self-citation is load-bearing, and all supporting theorems are independent external results. The paper is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on two external combinatorial theorems and the strategy-stealing principle; no new free parameters or postulated entities are introduced.

axioms (2)
  • standard math Graham-Leeb-Rothschild affine/vector-space Ramsey theorem
    Invoked to prove that T(n,q) is finite for every fixed n and q.
  • standard math Erdős-Selfridge criterion for Maker-Breaker games
    Used to obtain general lower bounds on T(n,q).

pith-pipeline@v0.9.0 · 5855 in / 1389 out tokens · 47610 ms · 2026-05-25T06:24:16.404646+00:00 · methodology

Review history (3 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages

  1. [1]

    Positional games.Combinatorics, Probability and Computing, 14:649–696, 2005

    J´ ozsef Beck. Positional games.Combinatorics, Probability and Computing, 14:649–696, 2005

    work page 2005

  2. [2]

    Cambridge University Press, 2008

    J´ ozsef Beck.Combinatorial Games: Tic-Tac-Toe Theory, volume 114 ofEncyclopedia of Mathematics and its Applications. Cambridge University Press, 2008

    work page 2008

  3. [3]

    Berlekamp, John H

    Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy.Winning Ways for Your Math- ematical Plays. Volume 1. A K Peters, Natick, MA, 2nd edition, 2001

    work page 2001

  4. [4]

    A. E. Brouwer and A. Schrijver. The blocking number of an affine space.Journal of Combi- natorial Theory, Series A, 24(2):251–253, 1978

    work page 1978

  5. [5]

    Carroll and Steven T

    Maureen T. Carroll and Steven T. Dougherty. Tic-tac-toe on a finite plane.Mathematics Magazine, 77(4):260–274, 2004

    work page 2004

  6. [6]

    On-line ramsey numbers.SIAM Journal on Discrete Mathematics, 23(4):1954– 1963, 2009

    David Conlon. On-line ramsey numbers.SIAM Journal on Discrete Mathematics, 23(4):1954– 1963, 2009

    work page 1954

  7. [7]

    Online ramsey numbers and the subgraph query problem

    David Conlon, Jacob Fox, Andrey Grinshpun, and Xiaoyu He. Online ramsey numbers and the subgraph query problem. In Imre B´ ar´ any, Gyula O. H. Katona, and Attila Sali, editors, Building Bridges II: Mathematics of L´ aszl´ o Lov´ asz, volume 28 ofBolyai Society Mathematical Studies, pages 159–194. Springer, 2019

    work page 2019

  8. [8]

    Lev, and P´ eter P´ al Pach

    Ernie Croot, Vsevolod F. Lev, and P´ eter P´ al Pach. Progression-free sets inZn 4 are exponentially small.Ann. of Math. (2), 185(1):331–337, 2017

    work page 2017

  9. [9]

    Huggan, Rehan Malik, and Trent G

    Peter Danziger, Melissa A. Huggan, Rehan Malik, and Trent G. Marbach. Tic-tac-toe on an affine plane of order 4.Australasian Journal of Combinatorics, 82(1):21–30, 2022

    work page 2022

  10. [10]

    Ellenberg and Dion Gijswijt

    Jordan S. Ellenberg and Dion Gijswijt. On large subsets ofF n q with no three-term arithmetic progression.Ann. of Math. (2), 185(1):339–343, 2017

    work page 2017

  11. [11]

    Vector space ramsey numbers and weakly sidorenko affine configurations.The Quarterly Journal of Mathematics, 76(1):77–94, 2025

    Bryce Frederickson and Liana Yepremyan. Vector space ramsey numbers and weakly sidorenko affine configurations.The Quarterly Journal of Mathematics, 76(1):77–94, 2025. Published online 17 December 2024

    work page 2025

  12. [12]

    Harary’s generalized ticktacktoe

    Martin Gardner. Harary’s generalized ticktacktoe. InThe Colossal Book of Mathematics, pages 493–503. W. W. Norton, New York, 1st edition, 2001

    work page 2001

  13. [13]

    Graham, Klaus Leeb, and Bruce L

    Ronald L. Graham, Klaus Leeb, and Bruce L. Rothschild. Ramsey’s theorem for a class of categories.Advances in Mathematics, 8(3):417–433, 1972

    work page 1972

  14. [14]

    Finite field models in additive combinatorics

    Ben Green. Finite field models in additive combinatorics. InSurveys in Combinatorics 2005, volume 327 ofLondon Mathematical Society Lecture Note Series, pages 1–27. Cambridge Uni- versity Press, Cambridge, 2005

    work page 2005

  15. [15]

    Hales and Robert I

    Alfred W. Hales and Robert I. Jewett. Regularity and positional games.Transactions of the American Mathematical Society, 106:222–229, 1963

    work page 1963

  16. [16]

    On off-diagonal ramsey numbers for vector spaces overF 2

    Zach Hunter and Cosmin Pohoata. On off-diagonal ramsey numbers for vector spaces overF 2. Mathematical Proceedings of the Cambridge Philosophical Society, 179(2):503–518, 2025. 31

    work page 2025

  17. [17]

    On subsets of finite abelian groups with no 3-term arithmetic progressions

    Roy Meshulam. On subsets of finite abelian groups with no 3-term arithmetic progressions. Journal of Combinatorial Theory, Series A, 71(1):168–172, 1995

    work page 1995

  18. [18]

    Osborne and Ariel Rubinstein.A Course in Game Theory

    Martin J. Osborne and Ariel Rubinstein.A Course in Game Theory. MIT Press, Cambridge, MA, 1994

    work page 1994

  19. [19]

    Vu.Additive Combinatorics, volume 105 ofCambridge Studies in Advanced Mathematics

    Terence Tao and Van H. Vu.Additive Combinatorics, volume 105 ofCambridge Studies in Advanced Mathematics. Cambridge University Press, 2006. 32

    work page 2006