arxiv: 2605.00194 · v1 · submitted 2026-04-30 · 💻 cs.FL · cs.DM· math.CO· math.PR

Recognition: unknown

The speed of convergence in greedy Galois games

Jeffrey Shallit

Authors on Pith no claims yet

Pith reviewed 2026-05-09 19:39 UTC · model grok-4.3

classification 💻 cs.FL cs.DMmath.COmath.PR

keywords Thue-Morse sequencegreedy algorithmconvergence speeddueling scenarioprobabilistic gamesautomatic sequences

0 comments

The pith

The greedy shooting sequence converges to the Thue-Morse sequence at a rate that is now explicitly determined as p approaches zero.

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

In the 2013 model of Cooper and Dutle, Alice and Bob shoot at each other in a greedy order where each shot goes to the player with the lower current chance of success, with each shot succeeding independently with probability p. The authors observed that the resulting sequence of shooters approaches the infinite Thue-Morse sequence when p is tiny, but left open how fast this happens. This note resolves the open problem by calculating the convergence speed. A reader would care because this gives a precise error term for how closely real games with small p follow the famous Thue-Morse pattern, which is known for its regularity properties in combinatorics.

Core claim

The paper establishes the precise speed at which the sequence generated by the greedy assignment rule in the probabilistic dueling game converges to the Thue-Morse sequence t as the parameter p tends to 0.

What carries the argument

The greedy algorithm assigning each shot to the player with the smaller current success probability, whose generated sequence converges to the Thue-Morse sequence.

Load-bearing premise

The sequence of shots generated by the greedy rule does converge to the Thue-Morse sequence when p is taken to zero.

What would settle it

A computation of the greedy sequence for a sequence of decreasing p values showing that the Hamming distance to the Thue-Morse prefix does not follow the stated convergence rate.

Figures

Figures reproduced from arXiv: 2605.00194 by Jeffrey Shallit.

**Figure 1.** Figure 1: Lq on the y-axis, 1/p = 1/(1 − q) on the x-axis. Lemma 2. Define Sn(q) = P 0≤j<n tjq j . Let m ≥ 1, r ≥ 0 be integers. Then Sm·2 r (q) = S2 r (q)Sm(q 2 r ). Proof. An easy induction shows that S2 r (q) = Q 0≤j<r(1 − q 2 j ) > 0 for r ≥ 0. For 0 ≤ n < m · 2 r , write n uniquely as n = a · 2 r + b, where 0 ≤ a < m and 0 ≤ b < 2 r . Clearly ta·2 r+b = ta tb, and so Sm2 r (q) = X 0≤i<m·2 r tiq i = X 0≤a<m X 0≤… view at source ↗

read the original abstract

In 2013 Cooper and Dutle invented a dueling scenario where Alice and Bob shoot at each other until one is hit. Each shot is successful with some fixed probability $p$, $0 < p < 1$. The shooting order is given by a greedy algorithm, where at each step a shot is assigned to the player whose current probability of success is smaller. Cooper and Dutle observed that as $p \rightarrow 0$, the resulting sequence of shots (by Alice or Bob) converges to the infinite Thue-Morse sequence t, but left the speed of convergence as an open problem. In this note we determine the speed of this convergence.

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.

Desk Editor's Note private letter to a colleague

Shallit gives the explicit rate at which the greedy Galois game sequence approaches the Thue-Morse word as p goes to zero.

read the letter

Shallit has worked out the speed of convergence for the sequence produced by the greedy Galois game to the infinite Thue-Morse sequence as the hit probability p tends to zero. Cooper and Dutle saw that the sequence converges but left the rate open; this note supplies the missing quantitative bound. The argument takes the earlier convergence result as given and then measures the discrepancies that remain for small but positive p, most likely by tracking how the greedy choice rule deviates from the Thue-Morse pattern on finite prefixes and showing how those deviations vanish at a specific rate. The full text is described as self-contained, with no internal gaps or circular steps, which is consistent with a short, focused note. The derivation appears to rest on standard properties of the Thue-Morse word and the greedy assignment rule rather than new machinery. That keeps the paper short and direct. The main limitation is its narrow scope: it does not explore extensions to other sequences, other greedy rules, or computational consequences, but that is reasonable for a note whose sole purpose is to settle one open question. No unstated assumptions or invented objects are flagged, and the citation pattern is appropriate. Readers already working on automatic sequences, overlap-free words, or probabilistic constructions on infinite words will find the explicit rate useful and easy to cite. For anyone outside that circle the paper is too specialized to be essential. It deserves a serious referee because it answers a stated open problem with what looks like a complete, checkable argument. I would send it out for review rather than desk-reject it.

Referee Report

0 major / 1 minor

Summary. The paper resolves an open question from Cooper and Dutle (2013) by determining the speed at which the sequence of shots generated by the greedy algorithm in their probabilistic dueling game converges to the infinite Thue-Morse sequence t as the success probability p tends to 0.

Significance. If the claimed rate is derived rigorously, the result would close the open problem on quantitative convergence in this greedy construction and contribute to the literature on limits of morphic words and automatic sequences under probabilistic perturbations. The work is self-contained, takes the prior convergence observation as given, and introduces no new free parameters or ad-hoc axioms.

minor comments (1)

Abstract: the claim that the speed 'is determined' is stated without any indication of the explicit rate, asymptotic form, or proof strategy, which reduces the abstract's utility for readers.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive evaluation of the manuscript, for recognizing that it resolves the open question from Cooper and Dutle (2013), and for recommending minor revision. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity; derivation builds on external prior observation

full rationale

The paper cites Cooper and Dutle (2013) for the fact that the greedy shooting sequence converges to the Thue-Morse sequence as p approaches 0, treating this as an established external observation rather than deriving it internally. It then proceeds to analyze the rate of convergence under the greedy rule. No steps reduce by construction to self-defined quantities, fitted inputs renamed as predictions, or load-bearing self-citations. The central claim on convergence speed follows from direct examination of the algorithm's limiting behavior and is independent of the cited convergence result itself.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the prior convergence result from Cooper and Dutle and standard mathematical analysis of sequences; no free parameters or invented entities are indicated in the abstract.

axioms (1)

domain assumption The greedy sequence converges to the Thue-Morse sequence as p -> 0
This is the observation from Cooper and Dutle that the paper builds upon.

pith-pipeline@v0.9.0 · 5400 in / 1013 out tokens · 50598 ms · 2026-05-09T19:39:57.503725+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

10 extracted references

[1]

Allouche and H

J.-P. Allouche and H. Cohen. Dirichlet series and curious infinite products.Bull. London Math. Soc.17(1985), 531–538

1985
[2]

Allouche and J

J.-P. Allouche and J. Shallit. The ubiquitous Prouhet-Thue-Morse sequence. In C. Ding. T. Helleseth, and H. Niederreiter, eds.,Sequences and Their Applications: Proceedings of SETA ’98. Springer-Verlag, 1999, pp. 1–16

1999
[3]

J. D. Barrow. Rowing and the same-sum problem have their moments.Am. J. Phys. 78(2010), 728–732

2010
[4]

S. J. Brams and M. S. Ismail. Making the rules of sports fairer.SIAM Review60(2018), 181–202. 6

2018
[5]

S. J. Brams and A. D. Taylor.The Win-Win Solution: Guaranteeing Fair Shares to Everybody. Norton, New York, 1999

1999
[6]

Large language model, accessed throughhttps://chatgpt.com, conversation with the author, April 28 2026

OpenAI Global, LLC.ChatGPT, GPT-5.5 Thinking. Large language model, accessed throughhttps://chatgpt.com, conversation with the author, April 28 2026

2026
[7]

Cooper and A

J. Cooper and A. Dutle. Greedy Galois games.Amer. Math. Monthly120(2013), 441–451

2013
[8]

Palacios-Huerta

I. Palacios-Huerta. Tournaments, fairness and the Prouhet-Thue-Morse sequence.Eco- nomic Inquiry50(2012), 848–849

2012
[9]

J. Shallit. The ubiquitous Thue-Morse sequence. Talk for the Prison Mathematics Project, March 14 2022. Available athttps://cs.uwaterloo.ca/ ~shallit/Talks/ piday3.pdf

2022
[10]

N. J. A. Sloane et al. The On-Line Encyclopedia of Integer Sequences. Electronic resource. Available athttps://oeis.org. 7