Greedily Partitioning the Natural Numbers into Sets Free of Arithmetic Progressions

NEW

Problem: Let $\mathbb N=\{0,1,2,\dots\}$. Define $b_0=0$ and, for $k\ge0,\ r\in\{0,1,2\}$,

Let

The paper’s “uniqueness in $T_0$” problem is naturally reconstructed as:

For every $n\in\mathbb N$ and every $j<b_n$, there is a unique $f\in T_0$ such that [ n-f-1\in T_j,\qquad n-2f-1\in T_j . ]

Here $T_0$ is the set of integers whose ternary expansion uses only $0,1$. This reconstruction is supported by the quoted sentence immediately following the definitions of the analogous functions $d(n,j)$ and $e(n,j)$ in Section II.

Result: The reconstructed conjecture is true. In fact, the following stronger simultaneous uniqueness statement holds.

Define witness sets

Then every one of these sets is a singleton.

Key recurrence:

This follows directly from $b_{3k+r}=\lfloor(3b_k+r)/2\rfloor$. In particular,

Also, each $T_i$ is free of nonconstant 3-term arithmetic progressions, by the standard minimal-counterexample argument used in the paper: if an arithmetic progression in some $T_i$ has common difference divisible by $3$, divide by $3$; otherwise its three terms have distinct residues mod $3$, contradicting the recurrence because the corresponding values $3b_k+r$ must all lie in $\{2i,2i+1\}$.

We prove singletonness by induction on $n$. The case $j=b_n$ for $\mathcal D_{n,j}$ gives only $d=0$, since any $d>0$ would create a 3-term progression in $T_j$.

For $j<b_n$, write $n=3k+r$, $j=3m+t$, with $r,t\in\{0,1,2\}$. If a witness lies in $T_0$, then it has the form $3q+s$, where $q\in T_0$ and $s\in\{0,1\}$. Reducing the two required memberships modulo $3$, using the displayed decomposition of the $T_i$’s, forces the following recursive witnesses:

For example, in the last-column case $(t,r)=(1,2)$, a candidate $f=3q+s$ must have $s=1$; then

so the conditions are exactly

i.e. $q\in\mathcal E_{k,2m}$. Hence $f=3\epsilon_{k,2m}+1$, uniquely by induction. The other entries are identical residue checks.

The lower terms are legitimate because $j<b_n$ implies

and the standard bound $b_k\le b_{k-1}+1$ handles the rows involving $k-1$.

Thus each upper witness set is forced to be a singleton built from a previously unique lower witness. Induction proves in particular that $\mathcal F_{n,j}$ is always a singleton. Therefore the required $f\in T_0$ exists and is unique.

Verification audit: the proof uses exactly the paper’s recurrence-defined $T_i$’s and $T_0$; allows $f=0$, as required by small cases such as $n=2,j=0$; imposes no extra positivity or nondegeneracy assumption; and proves the stated uniqueness for every $n$ and every $j<b_n$.

Citation: Source of the problem and notation: Joseph Gerver, James Propp, and Jamie Simpson, “Greedily Partitioning the Natural Numbers into Sets Free of Arithmetic Progressions,” Proc. Amer. Math. Soc. 102 (1988), 765–772. The uniqueness of $f$ in $T_0$ is stated there as unproved; the proof above supplies the resolution.