Generator-offset property: Difference between revisions
| Line 68: | Line 68: | ||
Then the scale is SGA. | Then the scale is SGA. | ||
==== Proof ==== | ==== Proof ==== | ||
Assume that ''k'' is even. (If ''k'' is not even, invert the generator.) On some tonic p we have a chain of ceil(''n''/2) generators and on some other note ''p' '' (not on the first chain) we'll have floor(''n''/2) generators. We have ''k'' ceil(''n''/2) notes on ''p'' and ''k'' floor(''n''/2) notes on ''p' '' = ''p'' + offset. | Assume that ''k'' is even. (If ''k'' is not even, invert the generator.) On some tonic p we have a chain of ceil(''n''/2) generators and on some other note ''p' '' (not on the first chain) we'll have floor(''n''/2) generators. We have ''k''*ceil(''n''/2) notes on ''p'' and ''k''*floor(''n''/2) notes on ''p' '' = ''p'' + offset. | ||
We must have gcd(''k'', ''n'') = 1. If not, since ''n'' is odd, gcd(''k'', ''n'') is an odd number at least 3, and the ''k''-steps must form more than 2 parallel chains. | We must have gcd(''k'', ''n'') = 1. If not, since ''n'' is odd, gcd(''k'', ''n'') is an odd number at least 3, and the ''k''-steps must form more than 2 parallel chains. | ||
By modular arithmetic we have rk mod n = k/2 iff r = ceil(n/2) mod n. (Since gcd(2, ''n'') = 1, 2 is multiplicatively invertible mod ''n'', and we can multiply both sides by 2 to check this | By modular arithmetic we have ''rk'' mod ''n'' = ''k''/2 iff ''r'' = ceil(''n''/2) mod ''n''. (Since gcd(2, ''n'') = 1, 2 is multiplicatively invertible mod ''n'', and we can multiply both sides by 2 to check this: we get (''n'' + 1)k = ''nk + k = k'' (mod ''n''), which is true.) This proves that the offset, which must be reached after ceil(''n''/2) generator steps, is a ''k''/2-step. (If the offset wasn't reached in ceil(n/2) steps, the two generator chains either wouldn't be disjoint or wouldn't have the assumed lengths.) <math>\square</math> | ||
== Open conjectures == | == Open conjectures == | ||