pith. sign in

arxiv: 2605.05455 · v2 · 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-12 02:33 UTC · model grok-4.3

classification 🧮 math.CO
keywords affine Tic-Tac-Toepositional gamesthreshold phenomenaRamsey theoryfinite geometryMaker-Breaker gamesFourier analysis
0
0 comments X

The pith

For fixed n and q, affine Tic-Tac-Toe on F_q^m has a finite threshold T(n,q) above which the first player always wins.

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

The paper introduces an affine-space version of Tic-Tac-Toe in which two players claim points of the vector space F_q^m and the first to occupy every point of some n-dimensional affine subspace wins. It proves that for any fixed n and q the outcome is always either a first-player win or a draw, and that once a first-player win appears for some dimension m it persists for all larger m. The resulting threshold function T(n,q) is shown to be finite by invoking the Graham-Leeb-Rothschild affine Ramsey theorem, and is bounded above by 2^{n+1} when q=2 via a Fourier-analytic argument with inductive lifting. A reader would care because the result gives a clean interface between strong positional games, finite geometry, and Ramsey theory, together with concrete lower bounds such as T(n,q) at least n+2 for n at least 2.

Core claim

Every (m,n)_q-game is either a first-player win or a draw, and the property of being a first-player win is monotone non-decreasing in the ambient dimension m. This yields a threshold T(n,q) such that the game is a draw for all m below T(n,q) and a first-player win for all m at or above T(n,q). The threshold is finite by the affine/vector-space Ramsey theorem of Graham, Leeb and Rothschild; general lower bounds follow from the Erdős-Selfridge criterion, while the binary case satisfies the explicit upper bound T(n,2) ≤ 2^{n+1} by a direct Fourier-analytic argument combined with inductive lifting. Several small values are determined exactly, including T(1,q)=2 for q in {2,3,4} and T(2,2)=4, and

What carries the argument

The threshold T(n,q) induced by monotonicity of the first-player-win property, established via strategy stealing together with a blocking-set interpretation of the second player's moves.

If this is right

  • For every m at or above T(n,q) the first player possesses a winning strategy.
  • T(n,q) is at least n+2 for every n at least 2, obtained from explicit geometric pairing strategies.
  • In the binary case the threshold satisfies the concrete upper bound T(n,2) at most 2 to the power n+1.
  • Exact thresholds are known in small cases: T(1,q) equals 2 for q equals 2, 3 or 4, and T(2,2) equals 4.

Where Pith is reading between the lines

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

  • The same monotonicity argument may apply to other strong positional games whose winning sets are affine subspaces or other linear structures.
  • Quantitative versions of the Graham-Leeb-Rothschild theorem would immediately yield concrete numerical estimates for T(n,q) beyond the binary upper bound.
  • The Fourier-analytic method used for q=2 might extend to small prime-power fields, potentially improving the general lower bounds obtained from Erdős-Selfridge.

Load-bearing premise

That strategy stealing plus a blocking-set view of the second player's responses forces every instance to be either a first-player win or a draw, with the win property non-decreasing in ambient dimension m.

What would settle it

An explicit second-player pairing or blocking strategy that forces a draw for some m larger than the claimed T(n,q), or a counterexample showing that the affine Ramsey theorem fails to guarantee a monochromatic n-flat in the coloring induced by play on arbitrarily large spaces.

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 manuscript introduces the (m,n)_q Tic-Tac-Toe game on the finite affine space F_q^m, in which two players alternately claim points and the first to occupy all points of an n-dimensional affine subspace wins. For fixed n and q, the authors use strategy stealing together with a blocking-set interpretation to prove that every such game is either a first-player win or a draw and that the first-player-win property is monotone in the ambient dimension m. This yields a well-defined threshold T(n,q). Finiteness of T(n,q) follows from the Graham-Leeb-Rothschild affine Ramsey theorem; general lower bounds are obtained from the Erdős-Selfridge criterion for Maker-Breaker games. In the binary case an explicit upper bound T(n,2) ≤ 2^{n+1} is derived via Fourier analysis combined with an inductive lifting argument. Exact values are computed for several small instances (T(1,q)=2 for q=2,3,4 and T(2,2)=4) and geometric lower bounds T(n,q) ≥ n+2 (n≥2) are established via pairing strategies.

Significance. The work sits at the interface of strong positional games, finite geometry, and Ramsey theory. The strategy-stealing-plus-blocking-set argument cleanly establishes monotonicity without invoking explicit Ramsey numbers, while the direct appeal to the Graham-Leeb-Rothschild theorem supplies a short proof of finiteness. The Fourier-analytic bound for q=2 and the exact small-case determinations provide concrete, checkable results. These contributions are likely to stimulate further research on geometric Maker-Breaker games and on threshold phenomena in higher-dimensional affine spaces.

minor comments (3)
  1. [§2.1] §2.1: the definition of an affine n-flat is given in vector-space language, but a short parenthetical remark recalling that every affine subspace is a translate of a linear subspace would help readers who are not specialists in finite geometry.
  2. [§4.3] §4.3, proof of Theorem 4.5: the inductive lifting step is described concisely; adding one or two sentences that explicitly verify how a winning strategy on an m-dimensional subspace extends when extra moves are available outside it would improve readability without lengthening the argument.
  3. [Table 1] Table 1: the column headings for the small-case computations could be clarified by adding a footnote that the entries are obtained by exhaustive computer search for the listed (m,n,q) triples.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive and constructive report, including the clear summary of our contributions and the recommendation for minor revision. We appreciate the recognition that the strategy-stealing-plus-blocking-set argument establishes monotonicity cleanly, that the appeal to the Graham-Leeb-Rothschild theorem gives a short finiteness proof, and that the Fourier-analytic upper bound together with the exact small-case computations are concrete and checkable. Since the report contains no specific major comments, we have no point-by-point responses to provide at this stage. We will address any minor editorial or typographical suggestions in the revised version.

Circularity Check

0 steps flagged

No significant circularity; derivation relies on external theorems and direct arguments

full rationale

The paper establishes monotonicity and the win/draw dichotomy via standard strategy-stealing plus an explicit blocking-set argument that does not reduce to any fitted quantity or self-definition. Finiteness of T(n,q) is obtained by direct invocation of the external Graham-Leeb-Rothschild affine Ramsey theorem, which is an independent result on colorings of AG(m,q) and does not depend on the game outcome. Lower bounds come from the external Erdős-Selfridge Maker-Breaker criterion. The binary upper bound T(n,2)≤2^{n+1} is derived from a self-contained Fourier-analytic estimate combined with an inductive lifting construction whose steps are spelled out without reference to prior fitted values or self-citations. No load-bearing step equates a claimed prediction to its own input by construction, and all cited results are external or directly verifiable.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on standard external theorems from Ramsey theory and positional games; no new free parameters, invented entities, or ad-hoc axioms are introduced in the abstract description.

axioms (2)
  • standard math The affine/vector-space Ramsey theorem of Graham, Leeb and Rothschild holds and applies to colorings arising from the game.
    Invoked to prove finiteness of T(n,q).
  • domain assumption Strategy stealing applies directly to show the game cannot be a second-player win.
    Standard assumption in impartial positional games.

pith-pipeline@v0.9.0 · 5623 in / 1735 out tokens · 69229 ms · 2026-05-12T02:33:05.839915+00:00 · methodology

Review history (2 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.

  • IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear
    ?
    unclear

    Relation between the paper passage and the cited Recognition theorem.

    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)... We prove that this threshold is finite by applying the affine/vector-space Ramsey theorem of Graham, Leeb and Rothschild

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. 27

    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]

    Bryce Frederickson and Liana Yepremyan. Vector space ramsey numbers and weakly sidorenko affine configurations.Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications, pages 450–456, 2023

    work page 2023

  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

    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. 28

    work page 2006