Generator-offset property: Difference between revisions
m →Proof: Clean up abuse/unclear use of "preimage" |
|||
| Line 158: | Line 158: | ||
We have three cases to consider: | We have three cases to consider: | ||
Case 1 | ===== Case 1 ===== | ||
Λ<sub>2</sub> is the mos (n − 2)β 2β’. | |||
For Λ<sub>2</sub> to be a mos, the first, and only, occurrence of R must be at either f = floor(n/2) or ceil(n/2). We may assume that it is at f; otherwise flip the chain and reindex the words to start at 2f. | For Λ<sub>2</sub> to be a mos, the first, and only, occurrence of R must be at either f = floor(n/2) or ceil(n/2). We may assume that it is at f; otherwise flip the chain and reindex the words to start at 2f. | ||
| Line 175: | Line 176: | ||
In this case S has two chains of Qs, one with floor(n/2) notes and and one with ceil(n/2) notes. Every instance of Q must be a k-step, since by '''Z'''-linear independence Q = αa + βb + γc is the only way to write Q in the basis (a, b, c); so S is well-formed with respect to Q. Thus S also satisfies the generator-offset property with generator Q. | In this case S has two chains of Qs, one with floor(n/2) notes and and one with ceil(n/2) notes. Every instance of Q must be a k-step, since by '''Z'''-linear independence Q = αa + βb + γc is the only way to write Q in the basis (a, b, c); so S is well-formed with respect to Q. Thus S also satisfies the generator-offset property with generator Q. | ||
===== Case 2 ===== | |||
Λ<sub>2</sub> has fewer β than β’. | |||
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, thus S satisfies the generator-offset property. | ||
===== Case 3 ===== | |||
μ = anything else from 3 to floor(n/2). | |||
Λ<sub>2</sub> 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 Λ<sub>3</sub> has a chunk of γs of that same size. Λ<sub>3</sub> also has a chunk that goes over n and loops back around, which must be of size y = at least 2*(floor(n/μ) − 1) + 1 (Λ<sub>3</sub> might have chunks of size floor(n/μ) − 1 and floor(n/μ) instead) = 2*floor(n/μ) − 1, and at most 2*(floor(n/μ) + 1) + 1 = 2*floor(n/μ) + 3 (if Λ<sub>3</sub> has chunks of size floor(n/μ) and ceil(n/μ)). The difference between the chunk sizes is y − x, which must be 0 or 1, since Λ<sub>3</sub> is a mos. We thus have the following cases: | Λ<sub>2</sub> 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 Λ<sub>3</sub> has a chunk of γs of that same size. Λ<sub>3</sub> also has a chunk that goes over n and loops back around, which must be of size y = at least 2*(floor(n/μ) − 1) + 1 (Λ<sub>3</sub> might have chunks of size floor(n/μ) − 1 and floor(n/μ) instead) = 2*floor(n/μ) − 1, and at most 2*(floor(n/μ) + 1) + 1 = 2*floor(n/μ) + 3 (if Λ<sub>3</sub> has chunks of size floor(n/μ) and ceil(n/μ)). The difference between the chunk sizes is y − x, which must be 0 or 1, since Λ<sub>3</sub> is a mos. We thus have the following cases: | ||