Shifted Templates Improve Schur Number Lower Bounds

Schur numbers ask for the largest interval $[1,p]$ that can be colored with $k$ colors without a monochromatic solution to $x+y=z$. Exact values are known only through $S(5)=160$, so progress for larger $k$ often comes from recursive constructions: start with a known sum-free coloring, expand it by a structured template, and prove the expansion preserves the sum-free property. This paper extends Rowley-style S-templates by changing how the template reuses colors from the base partition. The payoff is a better two-color-step recurrence than Abbott and Hanson’s classical bound.

Core Contribution

The new object is a shifted S-template. In an ordinary S-template, cells marked with a special label in row $\alpha$ inherit the color of the same row in the base coloring, $g(\alpha)$. The shifted version allows such a cell to inherit from a neighboring or otherwise shifted row, $g(\alpha+d)$, where $d$ belongs to a controlled set of allowed shifts. That small change matters because the ordinary labels and shifted labels draw from disjoint color sources: ordinary labels introduce the new colors, while shifted labels reuse base colors. More freedom in the reused base colors lets the authors build a width-10 template with two new colors and a tail of length 2, yielding

This improves the same-step Abbott-Hanson recurrence $S(k+2) \geq 9S(k)+4$, and it is strong enough to update the catalogued lower bounds for two concrete Schur numbers.

Technical Approach

The construction starts from a valid coloring $g:[1,p]\to[1,k]$ and replaces each input integer $\alpha$ by a row of width $q$. The main block has size $pq$; a cell at position $x=(\alpha-1)q+u$ receives either a new color $k+i$ from an ordinary label $A_i$, or an old base color $g(\alpha+d)$ from a shifted special label $P_d$. A finite tail can then be appended after the main block if the sums touching that tail are separately checked.

The main proof obligation is to prevent any monochromatic triple after expansion. The authors reduce this to a finite template condition. When two main-block entries add, the resulting row index is governed by $\gamma=\alpha+\beta-1+\epsilon$, where $\epsilon$ is the column carry. They classify rows by whether their allowed shifts are near the lower boundary, middle, or upper boundary of the base partition. For a bounded shift set $\Delta=\{-n,\ldots,n\}$ and sufficiently large $p$, only $2n+1$ row types need to be checked rather than every possible base-row index.

That reduction supports two formal statements. The multiplication theorem says an admissible template of width $q$ adding $r$ new colors gives $S(k+r)\geq qS(k)$. The tail theorem adds a checked suffix of length $t$, giving $S(k+r)\geq qS(k)+t$. These theorems separate the infinite family argument from the finite admissibility search.

Results and Analysis

The computational search is reported as SAT over shifted S-templates. Table I shows that with shifts $\Delta=\{-1,0,1\}$, the case $r=2,q=10$ is satisfiable, while $r=2,q=11$ is unsatisfiable for the tested shift ranges up to $\{-3,\ldots,3\}$. For $r=3,q=34$, the solver reports UNSAT for $\Delta=\{-2,\ldots,2\}$ and a 20-hour timeout for $\Delta=\{-3,\ldots,3\}$. The useful constructive result is therefore not a broad family of larger templates, but one explicit width-10 shifted template with tail $Q=(A,B)$.

Using Theorem 2 with $q=10$, $r=2$, and $t=2$, the paper obtains $S(k+2)\geq 10S(k)+2$. Instantiating this with known lower bounds gives $S(8)\geq 10\cdot536+2=5,362$ and $S(13)\geq 10\cdot203,828+2=2,038,282$. Those replace previously listed lower bounds of 5,286 and 2,011,290. The absolute gains are modest, but they are clean improvements from a short template and a finite verification argument.

Caveats

The evidence is strongest for the displayed recurrence and the two derived bounds. The broader shifted-template search is less conclusive: larger shift sets and more new colors quickly hit encoding size and runtime limits. The conclusion says the authors expect $r\geq4$ to be prohibitive, with relevant widths such as $q\geq112$ and $q\geq381$ making the encoding size scale beyond the already difficult $r=3$ case. The method is a useful expansion of the template toolkit, not a route to exact Schur numbers by itself.