Generator-offset property: Difference between revisions

Line 144:

We don’t know which P’s have preimage Q and which P’s have preimage R, but we now do know that Σ2 has one more R than Σ3, and thus that:

Λ2 is λβ μβ’, 2 <= μ <= ceil(n/2).

Λ2 is λβ μβ’, 2 ≤ μ ≤ ceil(n/2).

Λ3 is a (λ±1)β (μ∓1)β’ mos.

Line 156:

Λ3 = γ ( ditto ) γ

Since, by our assumption, Λ3 has two γ’s in a row, Λ3 must have more γ than γ’, so μ - 1 < n/2. Since Λ3 is a mos, μ - 1 >= 1. So we have 2 <= μ <= ceil(n/2).

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

We have three cases to consider:

Line 189:

[Case 3: μ = anything else from 3 to floor(n/2).

Λ2 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 Λ3 has a chunk of γs of that same size. Λ3 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 (Λ3 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 Λ3 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 Λ3 is a mos. We thus have the following cases:

Λ2 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 Λ3 has a chunk of γs of that same size. Λ3 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 (Λ3 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 Λ3 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 Λ3 is a mos. We thus have the following cases:

BEGIN CASEBLOCK 3.x: [ Here chunk of Λ2 means chunk of β, and chunk of Λ3 means chunk of γ.

[Case 3.1: (x, y) = (floor(n/μ), 2*floor(n/μ) - 1)

[Case 3.1: (x, y) = (floor(n/μ), 2*floor(n/μ) − 1)

Since y-x = floor(n/μ) - 1 and floor(n/μ) >= 2, we have: x = floor(n/μ) = 2 and y-x = 1; hence y = 2*floor(n/μ) - 1 = 3. The chunk in Λ3 whose size is 3 is made from two chunks in Λ2 of size 1. (So Λ2 has chunks of size 1 and 2, and Λ3 has chunks of size 2 and 3.)

Since y − x = floor(n/μ) − 1 and floor(n/μ) ≥ 2, we have: x = floor(n/μ) = 2 and y − x = 1; hence y = 2*floor(n/μ) − 1 = 3. The chunk in Λ3 whose size is 3 is made from two chunks in Λ2 of size 1. (So Λ2 has chunks of size 1 and 2, and Λ3 has chunks of size 2 and 3.)

Λ2 has two consecutive chunks of size 1. Since chunk sizes form a mos, Λ2 has more chunks of size 1 than it has chunks of size 2.

Use “w[i:j]” to denote the slice of the cyclic word w that includes both endpoints. Λ2 has only two chunks of size 1, Λ2[n-1:n-1] and Λ2[1:1], since otherwise Λ3 would have a chunk of size 1 within Λ3[1:n-1]. Thus Λ2 has exactly one chunk of size 2. Thus Λ2 = ββ’βββ’ββ’ and Λ3 = γγ’γγγ’γγ. Thus we have:

Use “w[i:j]” to denote the slice of the cyclic word w that includes both endpoints. Λ2 has only two chunks of size 1, Λ2[(n − 1):(n − 1)] and Λ2[1:1], since otherwise Λ3 would have a chunk of size 1 within Λ3[1:n − 1]. Thus Λ2 has exactly one chunk of size 2. Thus Λ2 = ββ’βββ’ββ’ and Λ3 = γγ’γγγ’γγ. Thus we have:

1 2 3 4 5 6 7

Line 215:

End Case 3.1]

[Case 3.2: (x, y) = (floor(n/μ) + 1, 2*floor(n/μ) - 1).

[Case 3.2: (x, y) = (floor(n/μ) + 1, 2*floor(n/μ) − 1).

Impossible: y = 2*floor(n/μ) - 1 can only occur if Λ3 has chunks of size floor(n/μ) - 1 and floor(n/μ), which contradicts the size of x.

Impossible: y = 2*floor(n/μ) − 1 can only occur if Λ3 has chunks of size floor(n/μ) − 1 and floor(n/μ), which contradicts the size of x.

End Case 3.2]

[Case 3.3: (x, y) = (floor(n/μ) + 1, 2*floor(n/μ))

Impossible: y = 2*floor(n/μ) can only occur if Λ3 has chunks of size floor(n/μ) - 1 and floor(n/μ), which contradicts the size of x.

Impossible: y = 2*floor(n/μ) can only occur if Λ3 has chunks of size floor(n/μ) − 1 and floor(n/μ), which contradicts the size of x.

End Case 3.3]

The remaining cases are all impossible because they imply y - x >= 2:

The remaining cases are all impossible because they imply y − x ≥ 2:

[Case 3.4:(x, y) = (floor(n/μ) + 1, 2*floor(n/μ) + 1)]

[Case 3.4: (x, y) = (floor(n/μ) + 1, 2*floor(n/μ) + 1)]

[Case 3.5: (x, y) = (floor(n/μ) + 1, 2*floor(n/μ) + 2)]

@@ Line 144: / Line 144: @@
 We don’t know which P’s have preimage Q and which P’s have preimage R, but we now do know that Σ2 has one more R than Σ3, and thus that:
-Λ2 is λβ μβ’, 2 <= μ <= ceil(n/2).
+Λ2 is λβ μβ’, 2 ≤ μ ≤ ceil(n/2).
 Λ3 is a (λ±1)β (μ∓1)β’ mos.
@@ Line 156: / Line 156: @@
   Λ3 = γ ( ditto ) γ
-Since, by our assumption, Λ3 has two γ’s in a row, Λ3 must have more γ than γ’, so μ - 1 < n/2. Since Λ3 is a mos, μ - 1 >= 1. So we have 2 <= μ <= ceil(n/2).
+Since, by our assumption, Λ3 has two γ’s in a row, Λ3 must have more γ than γ’, so μ &minus; 1 < n/2. Since Λ3 is a mos, μ &minus; 1 ≥ 1. So we have 2 ≤ μ ≤ ceil(n/2).
 We have three cases to consider:
@@ Line 189: / Line 189: @@
 [Case 3: μ = anything else from 3 to floor(n/2).
-Λ2 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 Λ3 has a chunk of γs of that same size. Λ3 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 (Λ3 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 Λ3 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 Λ3 is a mos. We thus have the following cases:
+Λ2 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 Λ3 has a chunk of γs of that same size. Λ3 also has a chunk that goes over n and loops back around, which must be of size y = at least 2*(floor(n/μ) &minus; 1) + 1 (Λ3 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 Λ3 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 Λ3 is a mos. We thus have the following cases:
 BEGIN CASEBLOCK 3.x: [ Here chunk of Λ2 means chunk of β, and chunk of Λ3 means chunk of γ.
-[Case 3.1: (x, y) = (floor(n/μ), 2*floor(n/μ) - 1)
+[Case 3.1: (x, y) = (floor(n/μ), 2*floor(n/μ) &minus; 1)
-Since y-x = floor(n/μ) - 1 and floor(n/μ) >= 2, we have: x = floor(n/μ) = 2 and y-x = 1; hence y = 2*floor(n/μ) - 1 = 3. The chunk in Λ3 whose size is 3 is made from two chunks in Λ2 of size 1. (So Λ2 has chunks of size 1 and 2, and Λ3 has chunks of size 2 and 3.)
+Since y &minus; x = floor(n/μ) &minus; 1 and floor(n/μ) ≥ 2, we have: x = floor(n/μ) = 2 and y &minus; x = 1; hence y = 2*floor(n/μ) &minus; 1 = 3. The chunk in Λ3 whose size is 3 is made from two chunks in Λ2 of size 1. (So Λ2 has chunks of size 1 and 2, and Λ3 has chunks of size 2 and 3.)
 Λ2 has two consecutive chunks of size 1. Since chunk sizes form a mos, Λ2 has more chunks of size 1 than it has chunks of size 2.
-Use “w[i:j]” to denote the slice of the cyclic word w that includes both endpoints. Λ2 has only two chunks of size 1, Λ2[n-1:n-1] and Λ2[1:1], since otherwise Λ3 would have a chunk of size 1 within Λ3[1:n-1]. Thus Λ2 has exactly one chunk of size 2. Thus Λ2 = ββ’βββ’ββ’ and Λ3 = γγ’γγγ’γγ. Thus we have:
+Use “w[i:j]” to denote the slice of the cyclic word w that includes both endpoints. Λ2 has only two chunks of size 1, Λ2[(n &minus; 1):(n &minus; 1)] and Λ2[1:1], since otherwise Λ3 would have a chunk of size 1 within Λ3[1:n &minus; 1]. Thus Λ2 has exactly one chunk of size 2. Thus Λ2 = ββ’βββ’ββ’ and Λ3 = γγ’γγγ’γγ. Thus we have:
 2  3 4 5  6 7
@@ Line 215: / Line 215: @@
 End Case 3.1]
-[Case 3.2: (x, y) = (floor(n/μ) + 1, 2*floor(n/μ) - 1).
+[Case 3.2: (x, y) = (floor(n/μ) + 1, 2*floor(n/μ) &minus; 1).
-Impossible: y = 2*floor(n/μ) - 1 can only occur if Λ3 has chunks of size floor(n/μ) - 1 and floor(n/μ), which contradicts the size of x.
+Impossible: y = 2*floor(n/μ) &minus; 1 can only occur if Λ3 has chunks of size floor(n/μ) &minus; 1 and floor(n/μ), which contradicts the size of x.
 End Case 3.2]
 [Case 3.3: (x, y) = (floor(n/μ) + 1, 2*floor(n/μ))
-Impossible: y = 2*floor(n/μ) can only occur if Λ3 has chunks of size floor(n/μ) - 1 and floor(n/μ), which contradicts the size of x.
+Impossible: y = 2*floor(n/μ) can only occur if Λ3 has chunks of size floor(n/μ) &minus; 1 and floor(n/μ), which contradicts the size of x.
 End Case 3.3]
-The remaining cases are all impossible because they imply y - x >= 2:
+The remaining cases are all impossible because they imply y &minus; x ≥ 2:
-[Case 3.4:(x, y) = (floor(n/μ) + 1, 2*floor(n/μ) + 1)]
+[Case 3.4: (x, y) = (floor(n/μ) + 1, 2*floor(n/μ) + 1)]
 [Case 3.5: (x, y) = (floor(n/μ) + 1, 2*floor(n/μ) + 2)]