Generator-offset property: Difference between revisions
m →Proof |
|||
| Line 149: | Line 149: | ||
where W is a word in two letters, of length n − 2. | where W is a word in two letters, of length n − 2. | ||
===== Case analysis ===== | |||
Since, by our assumption, Λ<sub>3</sub> has two γ’s in a row, Λ<sub>3</sub> must have more γ than γ’, so μ − 1 < n/2. Since Λ<sub>3</sub> is a mos, μ − 1 ≥ 1. So we have 2 ≤ μ ≤ ceil(n/2). | Since, by our assumption, Λ<sub>3</sub> has two γ’s in a row, Λ<sub>3</sub> must have more γ than γ’, so μ − 1 < n/2. Since Λ<sub>3</sub> is a mos, μ − 1 ≥ 1. So we have 2 ≤ μ ≤ ceil(n/2). | ||
We have three cases to consider: | We have three cases to consider: | ||
| Line 175: | Line 175: | ||
Since Λ<sub>3</sub> has more β than β’, Λ<sub>2</sub> is floor(n/2)β ceil(n/2)β’, and Λ<sub>3</sub> 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 Λ<sub>2</sub> 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. | Since Λ<sub>3</sub> has more β than β’, Λ<sub>2</sub> is floor(n/2)β ceil(n/2)β’, and Λ<sub>3</sub> 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 Λ<sub>2</sub> 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. | ||
In this case we have Σ = QRQR…QRT, thus S satisfies the generator-offset property. | In this case we have Σ = QRQR…QRT, and S is well-formed with respect to the generator Q + R, thus S satisfies the generator-offset property. | ||
'''Case 3:''' 3 ≤ μ ≤ floor(n/2). | '''Case 3:''' 3 ≤ μ ≤ floor(n/2). | ||