10.4 The (3v - 2u)‐Construction

In this section we present a recursive construction that starts with an SQS (v) (V = { 1 , 2 , . . . , v } , B) that contains an S Q S ( u ) ( V = { v - u + 1 , . . . , v } , B ) and produces an SQS(3v - 2u)(V B where V = { 1 , . . . , U } ( { 1 , 2 , , v - u } × {1, 2, 3}). This result was originally obtained by Hartman, but here we present a simplified proof due to Lenz, who made use of the Stern‐Lenz Lemma.

It will simplify notation to define g = v - u for the rest of this chapter. Notice that if 1 ≤ ag then a naturally corresponds to 3 symbols in V namely ( a , 1 ) , ( a , 2 ) and ( a , 3 ) ; and if g + 1 ≤ av then symbol a in the SQS(v) ...

Get Design Theory, 2nd Edition now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.