Generator-offset property: Difference between revisions

For (4), assume ''S'' is ''a''X ''b''Y ''b''Z, a odd. If ''b'' = 1, there’s nothing to prove. So assume ''b'' > 1. Suppose for the sake of contradiction that Y’s and Z’s don't alternate perfectly. Assume that the perfect generator of ''a''X 2''b''W is ''i''X + ''j''W with ''j'' ≥ 2. (If ''j'' = 1, we can invert the generator to make ''j'' ≥ 2, since ''b'' > 1.)

# (a) the preimage of the perfect generator with the maximum number of Y’s (at least 2 more than the # of Z's)

# (b) the preimage of the perfect generator with the maximum number of Z’s (at least 2 more than the # of Y's)

# (c) the preimage of the perfect generator with an intermediate number of Y’s and Z’s between (a) and (b)

# (d) (the preimage of) the imperfect generator, having a different number of X’s than (a), (b), and (c).  

Suppose for sake of contradiction that only one size of ''k''-step (α, β, γ) in ''S'' projects to P in ''S''₁. Then projecting to ''S''₂ shows that ''S''₂'s generator is the ''k''-step (α + γ)*(a~c) + βb, and Σ₂'s imperfect generator is located at index ''n'', like Σ₁'s imperfect generator is. Then ''S''₁ and ''S''₂ are the same mode of the same mos pattern (up to knowing which step size is the bigger one). Assume the L of ''S''₁ (it could be s, but it doesn’t matter) is the result of identifying b and c, and all instances of s in ''S''₁ come from a. Then the steps of ''S''₂ corresponding to the L of ''S''₁ must be either all b’s or all a~c’s, thus these steps are all b’s in ''S'' (otherwise they would be identified with the a, against the assumption that ''S''₁ and ''S''₂ are the same mos pattern and mode). So ''S'' has only two step sizes (a and b), contradicting the assumption that ''S'' has exactly three step sizes.

Only two sizes of ''k''-steps of ''S'' can project to P in ''S''₁, for if there are three sizes of ''k''-steps (α, β, γ), (α, β’, γ’), (α, β’’, γ’’) in ''S'' that project to P, then β, β’ and β’’ are three distinct values. Thus these would project to three different ''k''-steps in ''S''₃, contradicting the mos property of ''S''₃.

Suppose Q = (α, β, γ) ≠ R = (α, β’, γ’) are the two ''k''-steps in ''S'' that project to P. Then T = (α’, β’’, γ’’) projects to I. Here the values in each component differ by at most 1, and α ≠ α’. Then the cyclic word Λ₁ formed by the a-components of the ''k''-steps in P is α...αα’. Since Σ₂ is a single-period mos pattern of βb + (''n'' − β)(a~c) and β’a + (''n'' − β’)(a~c), the cyclic word Λ₂ = the pattern of β and β’ must be a single-period mos. Similarly, Λ₃ = the pattern of γ and γ’ is a single-period mos.

Suppose Λ₂ is the mos λβ μβ’. Then Λ₃ is the mos (λ ± 1)γ (μ ∓ 1)γ’. Since neither Λ₂ nor Λ₃ are multimosses, and at least one of μ and (μ ∓ 1) are even, it is now immediate that ''n'' is odd.

Either β’’ = β or β’’ = β’. Assume β’’ = β’. Then γ’’ = γ, and Λ₃ is (λ + 1)γ (μ − 1)γ’. Also assume that the first ''k''-step in Σ is Q. Then we have:

  Λ₁ = α …      α α’

  Λ₂ = β W(β, β’) β’

  Λ₃ = γ W(γ, γ’) γ

Since, by our assumption, Λ₃ has two γ’s in a row, Λ₃ must have more γ than γ’, so μ &minus; 1 < ''n''/2. Since Λ₃ is a mos, μ &minus; 1 ≥ 1. So we have 2 ≤ μ ≤ ceil(''n''/2).

'''Case 1''': μ = 2, i.e. Λ₂ is the mos (''n'' &minus; 2)β 2β’.

  Λ₁ = α … α α  α … α  α’

  Λ₂ = β … β β’ β … β  β’

  Λ₃ = γ … γ γ’ γ … γ  γ

# the stack has one T and does not contain any R (since it’s more than ''f'' &minus; 1 generators away).

'''Case 2:''' μ ≥ ceil(''n''/2), i.e. Λ₂ has fewer β than β’.

Since Λ₃ has more β than β’, Λ₂ is floor(''n''/2)β ceil(''n''/2)β’, and Λ₃ is ceil(''n''/2)γ floor(''n''/2)γ’. There is a unique mode of ceil(''n''/2)γ floor(''n''/2)γ’ that both begins and ends with γ, namely γγ’γγ’…γγ’γ. Thus Λ₂ is ββ’ββ’…ββ’β’. It is now easy to see that if the number of ''k''-steps stacked is odd, then there are two sizes that do not contain T and one size that contains T; if the number of ''k''-steps stacked is even, then there is one size that does not contain T and two sizes that contain T. Hence ''S'' is SV3.

Λ₂ has a chunk of βs (after the first β’) of size ''x'' = either floor(''n''/μ) (≥ floor(''n''/floor(''n''/2)) = 2) or ceil(''n''/μ) (= floor(''n''/μ) + 1). Hence Λ₃ has a chunk of γs of that same size. Λ₃ also has a chunk that crosses index ''n'', which must be of size ''y'' = at least 2*(floor(''n''/μ) &minus; 1) + 1 (Λ₃ might have chunks of size floor(''n''/μ) &minus; 1 and floor(''n''/μ) instead) = 2*floor(''n''/μ) &minus; 1, and at most 2*(floor(''n''/μ) + 1) + 1 = 2*floor(''n''/μ) + 3 (if Λ₃ has chunks of size floor(''n''/μ) and ceil(''n''/μ)). The difference between the chunk sizes is ''y'' &minus; ''x'', which must be 0 or 1, since Λ₃ is a mos. We thus have the following subcases: (In the following, chunk of Λ₂ means chunk of β, and chunk of Λ₃ means chunk of γ.)

Use ''w''[''i'' : ''j''] to denote the slice of the cyclic word ''w'' that includes both endpoints, i.e. the word ''w''[''i''] ''w''[''i'' + 1] ... ''w''[''j''] where indices are taken to be elements of '''Z'''/''n'''''Z'''. Λ₂ has only two chunks of size 1, Λ₂[(''n'' &minus; 1) : (''n'' &minus; 1)] and Λ₂[1 : 1], since otherwise Λ₃ would have a chunk of size 1 within Λ₃[1 : (''n'' &minus; 1)]. Thus Λ₂ has exactly one chunk of size 2. Thus Λ₂ = ββ’βββ’ββ’ and Λ₃ = γγ’γγγ’γγ. Thus we have:

  Λ₁ = α α  α α α  α α’

  Λ₂ = β β’ β β β’ β β’

  Λ₃ = γ γ’ γ γ γ’ γ γ