[#P101194] Density of losing positions in the subtract-a-cube game

Problem. Two players alternately remove a positive perfect cube of tokens from a single pile; the player unable to move loses. Let \(L(N)\) be the number of losing starting positions \(n \le N\). Does \(L(N)/N \to 0\) as \(N \to \infty\)?

Agent access

Work in ChatGPT

The agent reads this problem's research brief and asks you before it saves anything to TheoremDB.

Definitions and notation

1Problem setup

Remark 1. The allowed moves are 1, 8, 27, 64, 125, and so on.

Definition 1. A position is losing (a P-position) when its Sprague-Grundy value is 0.

2What counts as a solution

Prove that the density of losing positions tends to zero, or prove that it does not.

1Status

Saved packet · July 24, 2026

What counts as a solution

Saved solution (Subtract-a-cube losing positions have density zero). The losing positions form a cube-difference-free set, so the polynomial Szemerédi theorem forces their natural density to be zero.^[1]

Resolution argument

Let \(C\) be the set of P-positions. Two elements of \(C\) cannot differ by a positive cube, since the larger position could move to the smaller one. Suppose \(C\) had positive upper density. Bergelson and Leibman's polynomial extension of Szemerédi's theorem, applied to \(p(t)=t^3\), would give \(x,y\in C\) and \(t\geq 1\) with \(x-y=t^3\). This contradicts the defining property of P-positions. Therefore \(\limsup_{N\to\infty}|C\cap[1,N]|/N=0\), and the nonnegative ratios converge to zero.

The argument settles the database question. It applies more generally when the legal moves are the positive values of an integer-valued intersective polynomial with zero constant term.

1Packet records

Show recorded summaries

Record	Kind	Assessment
The losing positions form a cube-difference-free set, so the polynomial Szemerédi theorem forces their natural density to be zero.	Result	Evidence: Supported Backed by a cited source or by evidence short of a proof.
claim · Proposition 1 The losing positions form a cube-difference-free set, so the polynomial Szemerédi theorem forces their natural density to be zero.^[1] Relevance to this problem This records a result, observation, or conjecture used to assess the target problem. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state established Scope the full set of losing positions in the normal-play subtract-a-cube game Sources Reference 1 Argument Let \(C\) be the set of P-positions. Two elements of \(C\) cannot differ by a positive cube, since the larger position could move to the smaller one. Suppose \(C\) had positive upper density. Bergelson and Leibman's polynomial extension of Szemerédi's theorem, applied to \(p(t)=t^3\), would give \(x,y\in C\) and \(t\geq 1\) with \(x-y=t^3\). This contradicts the defining property of P-positions. Therefore \(\limsup_{N\to\infty}\|C\cap[1,N]\|/N=0\), and the nonnegative ratios converge to zero. The argument settles the database question. It applies more generally when the legal moves are the positive values of an integer-valued intersective polynomial with zero constant term. Open full record →
Density zero leaves a quantitative problem: estimate the number of subtract-a-cube P-positions through \(N\).	Trace	Outcome: Open Evidence: Conjectured Proposed as likely true. No argument is recorded.
attempt · Route 1 Density zero leaves a quantitative problem: estimate the number of subtract-a-cube P-positions through \(N\).^[2] Relevance to this problem This records a line of attack on the target problem, including what it establishes and where it stops. Evidence ConjecturedProposed as likely true. No argument is recorded. Record state open strategy Scope No narrower scope recorded Sources Reference 2 What happened Maximality gives an elementary lower bound. Every heap up to \(N\) is either a P-position or a P-position plus one of the \(\lfloor N^{1/3}\rfloor\) positive cubes, so \(L(N)+1\geq (N+1)/(\lfloor N^{1/3}\rfloor+1)\). Thus \(L(N)=\Omega(N^{2/3})\). The polynomial difference theorem gives \(L(N)=o(N)\). Sharpening that gap for this particular greedy set is the natural successor question. Its literature status still needs a specialist search. Related: Proposition 1 · Artifact 1 Open full record →
Exact dynamic programming finds 21,912 positive P-positions through 200,000 and a density of 0.10956 at the endpoint.	Artifact	Evidence: Executable material Executable source is recorded. Inspect its inputs and instructions before attempting a replay.
artifact · Artifact 1 Exact dynamic programming finds 21,912 positive P-positions through 200,000 and a density of 0.10956 at the endpoint. Relevance to this problem This supplies a computation, dataset, or executable check used to assess the target problem. Evidence Executable materialExecutable source is recorded. Inspect its inputs and instructions before attempting a replay. Record state available Scope every starting heap size from 0 through 200000 File research/candidate-screening/multi2.py Details The program computes every Sprague-Grundy value in increasing heap order using all positive cubes at most the current heap size. The P-position counts are 1,684 through 10,000, 6,815 through 50,000, 13,002 through 100,000, and 21,912 through 200,000. The first positive P-positions are 2, 4, 6, 9, 11, 13, 15, 18, 20, 22, 24, and 34. The maximum Grundy value in the range is 20, first reached at 167,122. The sweep is finite evidence for the rate of decay. The density-zero claim above follows from the cited theorem. Related: Proposition 1 Open full record →
No records match these filters.

Notes and companion material

Screened in the same sweep as the triangular version. The two behave very differently in the computed range, which is the reason both are recorded.

Original intake status. Status not established. No literature search was performed. Record this as a candidate question, not as a known open problem.

No literature search was carried out.
Because cubes have counting function N^(1/3) rather than N^(1/2), any argument that settles the square case need not transfer, and the observed densities differ by an order of magnitude.

Recorded example 1. The first losing positions are 2, 4, 6, 9, 11, 13, 15, 18, 20, 22, 24, 34.

Computational notes

Exact Sprague-Grundy computation for all n up to 200000. Density of losing positions: 0.16840 up to 10000, 0.13630 up to 50000, 0.13002 up to 100000, 0.10956 up to 200000. Total losing positions up to 200000: 21912. Maximum Grundy value observed: 20.

How the 3 records connect

The overview places each record once. The relation list includes shared dependencies and names both ends of each link.

ProblemDensity of losing positions in the subtract-a-cube game

All 3 recorded relations between these records and the problem

2See also

Density of losing positions in the subtract-a-triangular gamecombinatorial game theory
Smallest-prime-factor formula for a coprime splitting gamecombinatorial game theory
A gap of 50 in square-diagonal Wythoff Nimcombinatorial game theory

Contribute to this problem

Cite this problem statement

Cite the original sources separately.

Plain text

“Density of losing positions in the subtract-a-cube game.” TheoremDB. P101194. Problem statement; statement text SHA-256 f56dfcd67c514aba687a1675ec761b6b1c673896ecd9bc9952874ca78826650b. https://theoremdb.org/statement/?ref=P101194

BibTeX

@misc{theoremdb-problem-f56dfcd67c514aba687a1675ec761b6b1c673896ecd9bc9952874ca78826650b,
  title = {{Density of losing positions in the subtract-a-cube game}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 f56dfcd67c514aba687a1675ec761b6b1c673896ecd9bc9952874ca78826650b},
  url = {https://theoremdb.org/statement/?ref=P101194}
}

Plain text: Built Markdown snapshot

This problem includes 3 records joined by 3 typed links, sourced from doi.org^[1], current as of July 24, 2026.

1Lean verification

Lean formalization needed

A solution has been submitted and awaits independent review.

Open TheoremDB Researcher

Upload a Lean project archive

Once Lean accepts the draft, you can submit it while target review is pending. Your submission request is saved and continues after approval. Private checks stay private until you choose to submit.

1References

Packet source. Vitaly Bergelson and Alexander Leibman, “Polynomial extensions of van der Waerden’s and Szemerédi’s theorems,” Journal of the American Mathematical Society 9 (1996), 725–753. Section 0.2, p. 726. ↗ open copy ↗journal article · primary source · checked 2026-07-28Source use: citation only.The polynomial recurrence theorem implies that every positive-density set has two elements differing by a nonzero cube.Also cited at Bergelson and Leibman, Polynomial extensions of van der Waerden's and Szemerédi's theorems, JAMS 9 (1996), section 0.2, page 726.Source named by the research packet.
Antal Balog, János Pelikán, János Pintz, and Endre Szemerédi, “Difference sets without κ-th powers,” Acta Mathematica Hungarica 65 (1994), 165–187. Quantitative bounds for sets whose difference sets avoid perfect powers. ↗journal article · secondary source · checked 2026-07-28Source use: citation only.Provides quantitative context beyond the qualitative density-zero conclusion.Also cited at Quantitative direction informed by Balog, Pelikán, Pintz, and Szemerédi, Difference sets without k-th powers, 1994.

Original question generated by an agent and screened by exact computation.

[#P101194] Density of losing positions in the subtract-a-cube game

1Problem setup

2What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

2See also

1Lean verification

What the formal work covers

1References

Discussion

Report comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Sign in to follow

Report a problem

1Problem setup

2What counts as a solution

1StatusSolution submittedNot Lean-verified

1Packet records

Recent contributions

Computational notes

2See also

1Lean verification

What the formal work covers

1References

Add a comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance

1Status